1/*
2 * Copyright (c) 2003, 2010, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.  Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26package com.sun.java.util.jar.pack;
27
28import java.io.ByteArrayOutputStream;
29import java.io.IOException;
30import java.io.InputStream;
31import java.io.OutputStream;
32import static com.sun.java.util.jar.pack.Constants.*;
33
34/**
35 * Adaptive coding.
36 * See the section "Adaptive Encodings" in the Pack200 spec.
37 * @author John Rose
38 */
39class AdaptiveCoding implements CodingMethod {
40    CodingMethod headCoding;
41    int          headLength;
42    CodingMethod tailCoding;
43
44    public AdaptiveCoding(int headLength, CodingMethod headCoding, CodingMethod tailCoding) {
45        assert(isCodableLength(headLength));
46        this.headLength = headLength;
47        this.headCoding = headCoding;
48        this.tailCoding = tailCoding;
49    }
50
51    public void setHeadCoding(CodingMethod headCoding) {
52        this.headCoding = headCoding;
53    }
54    public void setHeadLength(int headLength) {
55        assert(isCodableLength(headLength));
56        this.headLength = headLength;
57    }
58    public void setTailCoding(CodingMethod tailCoding) {
59        this.tailCoding = tailCoding;
60    }
61
62    public boolean isTrivial() {
63        return headCoding == tailCoding;
64    }
65
66    // CodingMethod methods.
67    public void writeArrayTo(OutputStream out, int[] a, int start, int end) throws IOException {
68        writeArray(this, out, a, start, end);
69    }
70    // writeArrayTo must be coded iteratively, not recursively:
71    private static void writeArray(AdaptiveCoding run, OutputStream out, int[] a, int start, int end) throws IOException {
72        for (;;) {
73            int mid = start+run.headLength;
74            assert(mid <= end);
75            run.headCoding.writeArrayTo(out, a, start, mid);
76            start = mid;
77            if (run.tailCoding instanceof AdaptiveCoding) {
78                run = (AdaptiveCoding) run.tailCoding;
79                continue;
80            }
81            break;
82        }
83        run.tailCoding.writeArrayTo(out, a, start, end);
84    }
85
86    public void readArrayFrom(InputStream in, int[] a, int start, int end) throws IOException {
87        readArray(this, in, a, start, end);
88    }
89    private static void readArray(AdaptiveCoding run, InputStream in, int[] a, int start, int end) throws IOException {
90        for (;;) {
91            int mid = start+run.headLength;
92            assert(mid <= end);
93            run.headCoding.readArrayFrom(in, a, start, mid);
94            start = mid;
95            if (run.tailCoding instanceof AdaptiveCoding) {
96                run = (AdaptiveCoding) run.tailCoding;
97                continue;
98            }
99            break;
100        }
101        run.tailCoding.readArrayFrom(in, a, start, end);
102    }
103
104    public static final int KX_MIN = 0;
105    public static final int KX_MAX = 3;
106    public static final int KX_LG2BASE = 4;
107    public static final int KX_BASE = 16;
108
109    public static final int KB_MIN = 0x00;
110    public static final int KB_MAX = 0xFF;
111    public static final int KB_OFFSET = 1;
112    public static final int KB_DEFAULT = 3;
113
114    static int getKXOf(int K) {
115        for (int KX = KX_MIN; KX <= KX_MAX; KX++) {
116            if (((K - KB_OFFSET) & ~KB_MAX) == 0)
117                return KX;
118            K >>>= KX_LG2BASE;
119        }
120        return -1;
121    }
122
123    static int getKBOf(int K) {
124        int KX = getKXOf(K);
125        if (KX < 0)  return -1;
126        K >>>= (KX * KX_LG2BASE);
127        return K-1;
128    }
129
130    static int decodeK(int KX, int KB) {
131        assert(KX_MIN <= KX && KX <= KX_MAX);
132        assert(KB_MIN <= KB && KB <= KB_MAX);
133        return (KB+KB_OFFSET) << (KX * KX_LG2BASE);
134    }
135
136    static int getNextK(int K) {
137        if (K <= 0)  return 1;  // 1st K value
138        int KX = getKXOf(K);
139        if (KX < 0)  return Integer.MAX_VALUE;
140        // This is the increment we expect to apply:
141        int unit = 1      << (KX * KX_LG2BASE);
142        int mask = KB_MAX << (KX * KX_LG2BASE);
143        int K1 = K + unit;
144        K1 &= ~(unit-1);  // cut off stray low-order bits
145        if (((K1 - unit) & ~mask) == 0) {
146            assert(getKXOf(K1) == KX);
147            return K1;
148        }
149        if (KX == KX_MAX)  return Integer.MAX_VALUE;
150        KX += 1;
151        int mask2 = KB_MAX << (KX * KX_LG2BASE);
152        K1 |= (mask & ~mask2);
153        K1 += unit;
154        assert(getKXOf(K1) == KX);
155        return K1;
156    }
157
158    // Is K of the form ((KB:[0..255])+1) * 16^(KX:{0..3])?
159    public static boolean isCodableLength(int K) {
160        int KX = getKXOf(K);
161        if (KX < 0)  return false;
162        int unit = 1      << (KX * KX_LG2BASE);
163        int mask = KB_MAX << (KX * KX_LG2BASE);
164        return ((K - unit) & ~mask) == 0;
165    }
166
167    public byte[] getMetaCoding(Coding dflt) {
168        //assert(!isTrivial()); // can happen
169        // See the isCodableLength restriction in CodingChooser.
170        ByteArrayOutputStream bytes = new ByteArrayOutputStream(10);
171        try {
172            makeMetaCoding(this, dflt, bytes);
173        } catch (IOException ee) {
174            throw new RuntimeException(ee);
175        }
176        return bytes.toByteArray();
177    }
178    private static void makeMetaCoding(AdaptiveCoding run, Coding dflt,
179                                       ByteArrayOutputStream bytes)
180                                      throws IOException {
181        for (;;) {
182            CodingMethod headCoding = run.headCoding;
183            int          headLength = run.headLength;
184            CodingMethod tailCoding = run.tailCoding;
185            int K = headLength;
186            assert(isCodableLength(K));
187            int ADef   = (headCoding == dflt)?1:0;
188            int BDef   = (tailCoding == dflt)?1:0;
189            if (ADef+BDef > 1)  BDef = 0;  // arbitrary choice
190            int ABDef  = 1*ADef + 2*BDef;
191            assert(ABDef < 3);
192            int KX     = getKXOf(K);
193            int KB     = getKBOf(K);
194            assert(decodeK(KX, KB) == K);
195            int KBFlag = (KB != KB_DEFAULT)?1:0;
196            bytes.write(_meta_run + KX + 4*KBFlag + 8*ABDef);
197            if (KBFlag != 0)    bytes.write(KB);
198            if (ADef == 0)  bytes.write(headCoding.getMetaCoding(dflt));
199            if (tailCoding instanceof AdaptiveCoding) {
200                run = (AdaptiveCoding) tailCoding;
201                continue; // tail call, to avoid deep stack recursion
202            }
203            if (BDef == 0)  bytes.write(tailCoding.getMetaCoding(dflt));
204            break;
205        }
206    }
207    public static int parseMetaCoding(byte[] bytes, int pos, Coding dflt, CodingMethod res[]) {
208        int op = bytes[pos++] & 0xFF;
209        if (op < _meta_run || op >= _meta_pop)  return pos-1; // backup
210        AdaptiveCoding prevc = null;
211        for (boolean keepGoing = true; keepGoing; ) {
212            keepGoing = false;
213            assert(op >= _meta_run);
214            op -= _meta_run;
215            int KX = op % 4;
216            int KBFlag = (op / 4) % 2;
217            int ABDef = (op / 8);
218            assert(ABDef < 3);
219            int ADef = (ABDef & 1);
220            int BDef = (ABDef & 2);
221            CodingMethod[] ACode = {dflt}, BCode = {dflt};
222            int KB = KB_DEFAULT;
223            if (KBFlag != 0)
224                KB = bytes[pos++] & 0xFF;
225            if (ADef == 0) {
226                pos = BandStructure.parseMetaCoding(bytes, pos, dflt, ACode);
227            }
228            if (BDef == 0 &&
229                ((op = bytes[pos] & 0xFF) >= _meta_run) && op < _meta_pop) {
230                pos++;
231                keepGoing = true;
232            } else if (BDef == 0) {
233                pos = BandStructure.parseMetaCoding(bytes, pos, dflt, BCode);
234            }
235            AdaptiveCoding newc = new AdaptiveCoding(decodeK(KX, KB),
236                                                     ACode[0], BCode[0]);
237            if (prevc == null) {
238                res[0] = newc;
239            } else {
240                prevc.tailCoding = newc;
241            }
242            prevc = newc;
243        }
244        return pos;
245    }
246
247    private String keyString(CodingMethod m) {
248        if (m instanceof Coding)
249            return ((Coding)m).keyString();
250        return m.toString();
251    }
252    public String toString() {
253        StringBuilder res = new StringBuilder(20);
254        AdaptiveCoding run = this;
255        res.append("run(");
256        for (;;) {
257            res.append(run.headLength).append("*");
258            res.append(keyString(run.headCoding));
259            if (run.tailCoding instanceof AdaptiveCoding) {
260                run = (AdaptiveCoding) run.tailCoding;
261                res.append(" ");
262                continue;
263            }
264            break;
265        }
266        res.append(" **").append(keyString(run.tailCoding));
267        res.append(")");
268        return res.toString();
269    }
270
271/*
272    public static void main(String av[]) {
273        int[][] samples = {
274            {1,2,3,4,5},
275            {254,255,256,256+1*16,256+2*16},
276            {0xfd,0xfe,0xff,0x100,0x110,0x120,0x130},
277            {0xfd0,0xfe0,0xff0,0x1000,0x1100,0x1200,0x1300},
278            {0xfd00,0xfe00,0xff00,0x10000,0x11000,0x12000,0x13000},
279            {0xfd000,0xfe000,0xff000,0x100000}
280        };
281        for (int i = 0; i < samples.length; i++) {
282            for (int j = 0; j < samples[i].length; j++) {
283                int K = samples[i][j];
284                int KX = getKXOf(K);
285                int KB = getKBOf(K);
286                System.out.println("K="+Integer.toHexString(K)+
287                                   " KX="+KX+" KB="+KB);
288                assert(isCodableLength(K));
289                assert(K == decodeK(KX, KB));
290                if (j == 0)  continue;
291                int K1 = samples[i][j-1];
292                assert(K == getNextK(K1));
293            }
294        }
295    }
296//*/
297
298}
299