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
26 package com.sun.java.util.jar.pack;
27
28 import java.io.ByteArrayOutputStream;
29 import java.io.IOException;
30 import java.io.InputStream;
31 import java.io.OutputStream;
32 import 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 */
39 class 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 }