| /* |
| * Copyright (c) 2003, 2010, Oracle and/or its affiliates. All rights reserved. |
| * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| * |
| * This code is free software; you can redistribute it and/or modify it |
| * under the terms of the GNU General Public License version 2 only, as |
| * published by the Free Software Foundation. Oracle designates this |
| * particular file as subject to the "Classpath" exception as provided |
| * by Oracle in the LICENSE file that accompanied this code. |
| * |
| * This code is distributed in the hope that it will be useful, but WITHOUT |
| * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| * version 2 for more details (a copy is included in the LICENSE file that |
| * accompanied this code). |
| * |
| * You should have received a copy of the GNU General Public License version |
| * 2 along with this work; if not, write to the Free Software Foundation, |
| * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
| * |
| * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
| * or visit www.oracle.com if you need additional information or have any |
| * questions. |
| */ |
| |
| package com.sun.java.util.jar.pack; |
| |
| import java.io.ByteArrayOutputStream; |
| import java.io.IOException; |
| import java.io.InputStream; |
| import java.io.OutputStream; |
| import static com.sun.java.util.jar.pack.Constants.*; |
| |
| /** |
| * Adaptive coding. |
| * See the section "Adaptive Encodings" in the Pack200 spec. |
| * @author John Rose |
| */ |
| class AdaptiveCoding implements CodingMethod { |
| CodingMethod headCoding; |
| int headLength; |
| CodingMethod tailCoding; |
| |
| public AdaptiveCoding(int headLength, CodingMethod headCoding, CodingMethod tailCoding) { |
| assert(isCodableLength(headLength)); |
| this.headLength = headLength; |
| this.headCoding = headCoding; |
| this.tailCoding = tailCoding; |
| } |
| |
| public void setHeadCoding(CodingMethod headCoding) { |
| this.headCoding = headCoding; |
| } |
| public void setHeadLength(int headLength) { |
| assert(isCodableLength(headLength)); |
| this.headLength = headLength; |
| } |
| public void setTailCoding(CodingMethod tailCoding) { |
| this.tailCoding = tailCoding; |
| } |
| |
| public boolean isTrivial() { |
| return headCoding == tailCoding; |
| } |
| |
| // CodingMethod methods. |
| public void writeArrayTo(OutputStream out, int[] a, int start, int end) throws IOException { |
| writeArray(this, out, a, start, end); |
| } |
| // writeArrayTo must be coded iteratively, not recursively: |
| private static void writeArray(AdaptiveCoding run, OutputStream out, int[] a, int start, int end) throws IOException { |
| for (;;) { |
| int mid = start+run.headLength; |
| assert(mid <= end); |
| run.headCoding.writeArrayTo(out, a, start, mid); |
| start = mid; |
| if (run.tailCoding instanceof AdaptiveCoding) { |
| run = (AdaptiveCoding) run.tailCoding; |
| continue; |
| } |
| break; |
| } |
| run.tailCoding.writeArrayTo(out, a, start, end); |
| } |
| |
| public void readArrayFrom(InputStream in, int[] a, int start, int end) throws IOException { |
| readArray(this, in, a, start, end); |
| } |
| private static void readArray(AdaptiveCoding run, InputStream in, int[] a, int start, int end) throws IOException { |
| for (;;) { |
| int mid = start+run.headLength; |
| assert(mid <= end); |
| run.headCoding.readArrayFrom(in, a, start, mid); |
| start = mid; |
| if (run.tailCoding instanceof AdaptiveCoding) { |
| run = (AdaptiveCoding) run.tailCoding; |
| continue; |
| } |
| break; |
| } |
| run.tailCoding.readArrayFrom(in, a, start, end); |
| } |
| |
| public static final int KX_MIN = 0; |
| public static final int KX_MAX = 3; |
| public static final int KX_LG2BASE = 4; |
| public static final int KX_BASE = 16; |
| |
| public static final int KB_MIN = 0x00; |
| public static final int KB_MAX = 0xFF; |
| public static final int KB_OFFSET = 1; |
| public static final int KB_DEFAULT = 3; |
| |
| static int getKXOf(int K) { |
| for (int KX = KX_MIN; KX <= KX_MAX; KX++) { |
| if (((K - KB_OFFSET) & ~KB_MAX) == 0) |
| return KX; |
| K >>>= KX_LG2BASE; |
| } |
| return -1; |
| } |
| |
| static int getKBOf(int K) { |
| int KX = getKXOf(K); |
| if (KX < 0) return -1; |
| K >>>= (KX * KX_LG2BASE); |
| return K-1; |
| } |
| |
| static int decodeK(int KX, int KB) { |
| assert(KX_MIN <= KX && KX <= KX_MAX); |
| assert(KB_MIN <= KB && KB <= KB_MAX); |
| return (KB+KB_OFFSET) << (KX * KX_LG2BASE); |
| } |
| |
| static int getNextK(int K) { |
| if (K <= 0) return 1; // 1st K value |
| int KX = getKXOf(K); |
| if (KX < 0) return Integer.MAX_VALUE; |
| // This is the increment we expect to apply: |
| int unit = 1 << (KX * KX_LG2BASE); |
| int mask = KB_MAX << (KX * KX_LG2BASE); |
| int K1 = K + unit; |
| K1 &= ~(unit-1); // cut off stray low-order bits |
| if (((K1 - unit) & ~mask) == 0) { |
| assert(getKXOf(K1) == KX); |
| return K1; |
| } |
| if (KX == KX_MAX) return Integer.MAX_VALUE; |
| KX += 1; |
| int mask2 = KB_MAX << (KX * KX_LG2BASE); |
| K1 |= (mask & ~mask2); |
| K1 += unit; |
| assert(getKXOf(K1) == KX); |
| return K1; |
| } |
| |
| // Is K of the form ((KB:[0..255])+1) * 16^(KX:{0..3])? |
| public static boolean isCodableLength(int K) { |
| int KX = getKXOf(K); |
| if (KX < 0) return false; |
| int unit = 1 << (KX * KX_LG2BASE); |
| int mask = KB_MAX << (KX * KX_LG2BASE); |
| return ((K - unit) & ~mask) == 0; |
| } |
| |
| public byte[] getMetaCoding(Coding dflt) { |
| //assert(!isTrivial()); // can happen |
| // See the isCodableLength restriction in CodingChooser. |
| ByteArrayOutputStream bytes = new ByteArrayOutputStream(10); |
| try { |
| makeMetaCoding(this, dflt, bytes); |
| } catch (IOException ee) { |
| throw new RuntimeException(ee); |
| } |
| return bytes.toByteArray(); |
| } |
| private static void makeMetaCoding(AdaptiveCoding run, Coding dflt, |
| ByteArrayOutputStream bytes) |
| throws IOException { |
| for (;;) { |
| CodingMethod headCoding = run.headCoding; |
| int headLength = run.headLength; |
| CodingMethod tailCoding = run.tailCoding; |
| int K = headLength; |
| assert(isCodableLength(K)); |
| int ADef = (headCoding == dflt)?1:0; |
| int BDef = (tailCoding == dflt)?1:0; |
| if (ADef+BDef > 1) BDef = 0; // arbitrary choice |
| int ABDef = 1*ADef + 2*BDef; |
| assert(ABDef < 3); |
| int KX = getKXOf(K); |
| int KB = getKBOf(K); |
| assert(decodeK(KX, KB) == K); |
| int KBFlag = (KB != KB_DEFAULT)?1:0; |
| bytes.write(_meta_run + KX + 4*KBFlag + 8*ABDef); |
| if (KBFlag != 0) bytes.write(KB); |
| if (ADef == 0) bytes.write(headCoding.getMetaCoding(dflt)); |
| if (tailCoding instanceof AdaptiveCoding) { |
| run = (AdaptiveCoding) tailCoding; |
| continue; // tail call, to avoid deep stack recursion |
| } |
| if (BDef == 0) bytes.write(tailCoding.getMetaCoding(dflt)); |
| break; |
| } |
| } |
| public static int parseMetaCoding(byte[] bytes, int pos, Coding dflt, CodingMethod res[]) { |
| int op = bytes[pos++] & 0xFF; |
| if (op < _meta_run || op >= _meta_pop) return pos-1; // backup |
| AdaptiveCoding prevc = null; |
| for (boolean keepGoing = true; keepGoing; ) { |
| keepGoing = false; |
| assert(op >= _meta_run); |
| op -= _meta_run; |
| int KX = op % 4; |
| int KBFlag = (op / 4) % 2; |
| int ABDef = (op / 8); |
| assert(ABDef < 3); |
| int ADef = (ABDef & 1); |
| int BDef = (ABDef & 2); |
| CodingMethod[] ACode = {dflt}, BCode = {dflt}; |
| int KB = KB_DEFAULT; |
| if (KBFlag != 0) |
| KB = bytes[pos++] & 0xFF; |
| if (ADef == 0) { |
| pos = BandStructure.parseMetaCoding(bytes, pos, dflt, ACode); |
| } |
| if (BDef == 0 && |
| ((op = bytes[pos] & 0xFF) >= _meta_run) && op < _meta_pop) { |
| pos++; |
| keepGoing = true; |
| } else if (BDef == 0) { |
| pos = BandStructure.parseMetaCoding(bytes, pos, dflt, BCode); |
| } |
| AdaptiveCoding newc = new AdaptiveCoding(decodeK(KX, KB), |
| ACode[0], BCode[0]); |
| if (prevc == null) { |
| res[0] = newc; |
| } else { |
| prevc.tailCoding = newc; |
| } |
| prevc = newc; |
| } |
| return pos; |
| } |
| |
| private String keyString(CodingMethod m) { |
| if (m instanceof Coding) |
| return ((Coding)m).keyString(); |
| return m.toString(); |
| } |
| public String toString() { |
| StringBuilder res = new StringBuilder(20); |
| AdaptiveCoding run = this; |
| res.append("run("); |
| for (;;) { |
| res.append(run.headLength).append("*"); |
| res.append(keyString(run.headCoding)); |
| if (run.tailCoding instanceof AdaptiveCoding) { |
| run = (AdaptiveCoding) run.tailCoding; |
| res.append(" "); |
| continue; |
| } |
| break; |
| } |
| res.append(" **").append(keyString(run.tailCoding)); |
| res.append(")"); |
| return res.toString(); |
| } |
| |
| /* |
| public static void main(String av[]) { |
| int[][] samples = { |
| {1,2,3,4,5}, |
| {254,255,256,256+1*16,256+2*16}, |
| {0xfd,0xfe,0xff,0x100,0x110,0x120,0x130}, |
| {0xfd0,0xfe0,0xff0,0x1000,0x1100,0x1200,0x1300}, |
| {0xfd00,0xfe00,0xff00,0x10000,0x11000,0x12000,0x13000}, |
| {0xfd000,0xfe000,0xff000,0x100000} |
| }; |
| for (int i = 0; i < samples.length; i++) { |
| for (int j = 0; j < samples[i].length; j++) { |
| int K = samples[i][j]; |
| int KX = getKXOf(K); |
| int KB = getKBOf(K); |
| System.out.println("K="+Integer.toHexString(K)+ |
| " KX="+KX+" KB="+KB); |
| assert(isCodableLength(K)); |
| assert(K == decodeK(KX, KB)); |
| if (j == 0) continue; |
| int K1 = samples[i][j-1]; |
| assert(K == getNextK(K1)); |
| } |
| } |
| } |
| //*/ |
| |
| } |
