001: /*
002: * Copyright 2003-2005 Sun Microsystems, Inc. All Rights Reserved.
003: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004: *
005: * This code is free software; you can redistribute it and/or modify it
006: * under the terms of the GNU General Public License version 2 only, as
007: * published by the Free Software Foundation. Sun designates this
008: * particular file as subject to the "Classpath" exception as provided
009: * by Sun in the LICENSE file that accompanied this code.
010: *
011: * This code is distributed in the hope that it will be useful, but WITHOUT
012: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
013: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
014: * version 2 for more details (a copy is included in the LICENSE file that
015: * accompanied this code).
016: *
017: * You should have received a copy of the GNU General Public License version
018: * 2 along with this work; if not, write to the Free Software Foundation,
019: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
020: *
021: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
022: * CA 95054 USA or visit www.sun.com if you need additional information or
023: * have any questions.
024: */
025:
026: package com.sun.java.util.jar.pack;
027:
028: import java.util.*;
029: import java.io.*;
030:
031: /**
032: * Adaptive coding.
033: * See the section "Adaptive Encodings" in the Pack200 spec.
034: * @author John Rose
035: * @version 1.12, 05/05/07
036: */
037: class AdaptiveCoding implements Constants, CodingMethod {
038: CodingMethod headCoding;
039: int headLength;
040: CodingMethod tailCoding;
041:
042: public AdaptiveCoding(int headLength, CodingMethod headCoding,
043: CodingMethod tailCoding) {
044: assert (isCodableLength(headLength));
045: this .headLength = headLength;
046: this .headCoding = headCoding;
047: this .tailCoding = tailCoding;
048: }
049:
050: public void setHeadCoding(CodingMethod headCoding) {
051: this .headCoding = headCoding;
052: }
053:
054: public void setHeadLength(int headLength) {
055: assert (isCodableLength(headLength));
056: this .headLength = headLength;
057: }
058:
059: public void setTailCoding(CodingMethod tailCoding) {
060: this .tailCoding = tailCoding;
061: }
062:
063: public boolean isTrivial() {
064: return headCoding == tailCoding;
065: }
066:
067: // CodingMethod methods.
068: public void writeArrayTo(OutputStream out, int[] a, int start,
069: int end) throws IOException {
070: writeArray(this , out, a, start, end);
071: }
072:
073: // writeArrayTo must be coded iteratively, not recursively:
074: private static void writeArray(AdaptiveCoding run,
075: OutputStream out, int[] a, int start, int end)
076: throws IOException {
077: for (;;) {
078: int mid = start + run.headLength;
079: assert (mid <= end);
080: run.headCoding.writeArrayTo(out, a, start, mid);
081: start = mid;
082: if (run.tailCoding instanceof AdaptiveCoding) {
083: run = (AdaptiveCoding) run.tailCoding;
084: continue;
085: }
086: break;
087: }
088: run.tailCoding.writeArrayTo(out, a, start, end);
089: }
090:
091: public void readArrayFrom(InputStream in, int[] a, int start,
092: int end) throws IOException {
093: readArray(this , in, a, start, end);
094: }
095:
096: private static void readArray(AdaptiveCoding run, InputStream in,
097: int[] a, int start, int end) throws IOException {
098: for (;;) {
099: int mid = start + run.headLength;
100: assert (mid <= end);
101: run.headCoding.readArrayFrom(in, a, start, mid);
102: start = mid;
103: if (run.tailCoding instanceof AdaptiveCoding) {
104: run = (AdaptiveCoding) run.tailCoding;
105: continue;
106: }
107: break;
108: }
109: run.tailCoding.readArrayFrom(in, a, start, end);
110: }
111:
112: public static final int KX_MIN = 0;
113: public static final int KX_MAX = 3;
114: public static final int KX_LG2BASE = 4;
115: public static final int KX_BASE = 16;
116:
117: public static final int KB_MIN = 0x00;
118: public static final int KB_MAX = 0xFF;
119: public static final int KB_OFFSET = 1;
120: public static final int KB_DEFAULT = 3;
121:
122: static int getKXOf(int K) {
123: for (int KX = KX_MIN; KX <= KX_MAX; KX++) {
124: if (((K - KB_OFFSET) & ~KB_MAX) == 0)
125: return KX;
126: K >>>= KX_LG2BASE;
127: }
128: return -1;
129: }
130:
131: static int getKBOf(int K) {
132: int KX = getKXOf(K);
133: if (KX < 0)
134: return -1;
135: K >>>= (KX * KX_LG2BASE);
136: return K - 1;
137: }
138:
139: static int decodeK(int KX, int KB) {
140: assert (KX_MIN <= KX && KX <= KX_MAX);
141: assert (KB_MIN <= KB && KB <= KB_MAX);
142: return (KB + KB_OFFSET) << (KX * KX_LG2BASE);
143: }
144:
145: static int getNextK(int K) {
146: if (K <= 0)
147: return 1; // 1st K value
148: int KX = getKXOf(K);
149: if (KX < 0)
150: return Integer.MAX_VALUE;
151: // This is the increment we expect to apply:
152: int unit = 1 << (KX * KX_LG2BASE);
153: int mask = KB_MAX << (KX * KX_LG2BASE);
154: int K1 = K + unit;
155: K1 &= ~(unit - 1); // cut off stray low-order bits
156: if (((K1 - unit) & ~mask) == 0) {
157: assert (getKXOf(K1) == KX);
158: return K1;
159: }
160: if (KX == KX_MAX)
161: return Integer.MAX_VALUE;
162: KX += 1;
163: int unit2 = 1 << (KX * KX_LG2BASE);
164: int mask2 = KB_MAX << (KX * KX_LG2BASE);
165: K1 |= (mask & ~mask2);
166: K1 += unit;
167: assert (getKXOf(K1) == KX);
168: return K1;
169: }
170:
171: // Is K of the form ((KB:[0..255])+1) * 16^(KX:{0..3])?
172: public static boolean isCodableLength(int K) {
173: int KX = getKXOf(K);
174: if (KX < 0)
175: return false;
176: int unit = 1 << (KX * KX_LG2BASE);
177: int mask = KB_MAX << (KX * KX_LG2BASE);
178: return ((K - unit) & ~mask) == 0;
179: }
180:
181: public byte[] getMetaCoding(Coding dflt) {
182: //assert(!isTrivial()); // can happen
183: // See the isCodableLength restriction in CodingChooser.
184: ByteArrayOutputStream bytes = new ByteArrayOutputStream(10);
185: try {
186: makeMetaCoding(this , dflt, bytes);
187: } catch (IOException ee) {
188: throw new RuntimeException(ee);
189: }
190: return bytes.toByteArray();
191: }
192:
193: private static void makeMetaCoding(AdaptiveCoding run, Coding dflt,
194: ByteArrayOutputStream bytes) throws IOException {
195: for (;;) {
196: CodingMethod headCoding = run.headCoding;
197: int headLength = run.headLength;
198: CodingMethod tailCoding = run.tailCoding;
199: int K = headLength;
200: assert (isCodableLength(K));
201: int ADef = (headCoding == dflt) ? 1 : 0;
202: int BDef = (tailCoding == dflt) ? 1 : 0;
203: if (ADef + BDef > 1)
204: BDef = 0; // arbitrary choice
205: int ABDef = 1 * ADef + 2 * BDef;
206: assert (ABDef < 3);
207: int KX = getKXOf(K);
208: int KB = getKBOf(K);
209: assert (decodeK(KX, KB) == K);
210: int KBFlag = (KB != KB_DEFAULT) ? 1 : 0;
211: bytes.write(_meta_run + KX + 4 * KBFlag + 8 * ABDef);
212: if (KBFlag != 0)
213: bytes.write(KB);
214: if (ADef == 0)
215: bytes.write(headCoding.getMetaCoding(dflt));
216: if (tailCoding instanceof AdaptiveCoding) {
217: run = (AdaptiveCoding) tailCoding;
218: continue; // tail call, to avoid deep stack recursion
219: }
220: if (BDef == 0)
221: bytes.write(tailCoding.getMetaCoding(dflt));
222: break;
223: }
224: }
225:
226: public static int parseMetaCoding(byte[] bytes, int pos,
227: Coding dflt, CodingMethod res[]) {
228: int op = bytes[pos++] & 0xFF;
229: if (op < _meta_run || op >= _meta_pop)
230: return pos - 1; // backup
231: AdaptiveCoding prevc = null;
232: for (boolean keepGoing = true; keepGoing;) {
233: keepGoing = false;
234: assert (op >= _meta_run);
235: op -= _meta_run;
236: int KX = op % 4;
237: int KBFlag = (op / 4) % 2;
238: int ABDef = (op / 8);
239: assert (ABDef < 3);
240: int ADef = (ABDef & 1);
241: int BDef = (ABDef & 2);
242: CodingMethod[] ACode = { dflt }, BCode = { dflt };
243: int KB = KB_DEFAULT;
244: if (KBFlag != 0)
245: KB = bytes[pos++] & 0xFF;
246: if (ADef == 0) {
247: pos = BandStructure.parseMetaCoding(bytes, pos, dflt,
248: ACode);
249: }
250: if (BDef == 0 && ((op = bytes[pos] & 0xFF) >= _meta_run)
251: && op < _meta_pop) {
252: pos++;
253: keepGoing = true;
254: } else if (BDef == 0) {
255: pos = BandStructure.parseMetaCoding(bytes, pos, dflt,
256: BCode);
257: }
258: AdaptiveCoding newc = new AdaptiveCoding(decodeK(KX, KB),
259: ACode[0], BCode[0]);
260: if (prevc == null) {
261: res[0] = newc;
262: } else {
263: prevc.tailCoding = newc;
264: }
265: prevc = newc;
266: }
267: return pos;
268: }
269:
270: private String keyString(CodingMethod m) {
271: if (m instanceof Coding)
272: return ((Coding) m).keyString();
273: return m.toString();
274: }
275:
276: public String toString() {
277: StringBuffer res = new StringBuffer(20);
278: AdaptiveCoding run = this ;
279: res.append("run(");
280: for (;;) {
281: res.append(run.headLength).append("*");
282: res.append(keyString(run.headCoding));
283: if (run.tailCoding instanceof AdaptiveCoding) {
284: run = (AdaptiveCoding) run.tailCoding;
285: res.append(" ");
286: continue;
287: }
288: break;
289: }
290: res.append(" **").append(keyString(run.tailCoding));
291: res.append(")");
292: return res.toString();
293: }
294:
295: /*
296: public static void main(String av[]) {
297: int[][] samples = {
298: {1,2,3,4,5},
299: {254,255,256,256+1*16,256+2*16},
300: {0xfd,0xfe,0xff,0x100,0x110,0x120,0x130},
301: {0xfd0,0xfe0,0xff0,0x1000,0x1100,0x1200,0x1300},
302: {0xfd00,0xfe00,0xff00,0x10000,0x11000,0x12000,0x13000},
303: {0xfd000,0xfe000,0xff000,0x100000}
304: };
305: for (int i = 0; i < samples.length; i++) {
306: for (int j = 0; j < samples[i].length; j++) {
307: int K = samples[i][j];
308: int KX = getKXOf(K);
309: int KB = getKBOf(K);
310: System.out.println("K="+Integer.toHexString(K)+
311: " KX="+KX+" KB="+KB);
312: assert(isCodableLength(K));
313: assert(K == decodeK(KX, KB));
314: if (j == 0) continue;
315: int K1 = samples[i][j-1];
316: assert(K == getNextK(K1));
317: }
318: }
319: }
320: //*/
321:
322: }
|