AdaptiveCoding.java

/*
 * 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 au.net.zeus.util.jar.pack;

import java.io.ByteArrayOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import static au.net.zeus.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));
            }
        }
    }
//*/

}