/*

 * 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.IOException;

import java.io.InputStream;

import java.io.OutputStream;

import java.util.HashMap;

/**

 * Define the conversions between sequences of small integers and raw bytes.

 * This is a schema of encodings which incorporates varying lengths,

 * varying degrees of length variability, and varying amounts of signed-ness.

 * @author John Rose

 */

class Coding implements Constants, Comparable, CodingMethod, Histogram.BitMetric {

    /*

      Coding schema for single integers, parameterized by (B,H,S):

      Let B in [1,5], H in [1,256], S in [0,3].

      (S limit is arbitrary.  B follows the 32-bit limit.  H is byte size.)

      A given (B,H,S) code varies in length from 1 to B bytes.

      The 256 values a byte may take on are divided into L=(256-H) and H

      values, with all the H values larger than the L values.

      (That is, the L values are [0,L) and the H are [L,256).)

      The last byte is always either the B-th byte, a byte with "L value"

      (<L), or both.  There is no other byte that satisfies these conditions.

      All bytes before the last always have "H values" (>=L).

      Therefore, if L==0, the code always has the full length of B bytes.

      The coding then becomes a classic B-byte little-endian unsigned integer.

      (Also, if L==128, the high bit of each byte acts signals the presence

      of a following byte, up to the maximum length.)

      In the unsigned case (S==0), the coding is compact and monotonic

      in the ordering of byte sequences defined by appending zero bytes

      to pad them to a common length B, reversing them, and ordering them

      lexicographically.  (This agrees with "little-endian" byte order.)

      Therefore, the unsigned value of a byte sequence may be defined as:

      <pre>

        U(b0)           == b0

                           in [0..L)

                           or [0..256) if B==1 (**)

        U(b0,b1)        == b0 + b1*H

                           in [L..L*(1+H))

                           or [L..L*(1+H) + H^2) if B==2

        U(b0,b1,b2)     == b0 + b1*H + b2*H^2

                           in [L*(1+H)..L*(1+H+H^2))

                           or [L*(1+H)..L*(1+H+H^2) + H^3) if B==3

        U(b[i]: i<n)    == Sum[i<n]( b[i] * H^i )

                           up to  L*Sum[i<n]( H^i )

                           or to  L*Sum[i<n]( H^i ) + H^n if n==B

      </pre>

      (**) If B==1, the values H,L play no role in the coding.

      As a convention, we require that any (1,H,S) code must always

      encode values less than H.  Thus, a simple unsigned byte is coded

      specifically by the code (1,256,0).

      (Properly speaking, the unsigned case should be parameterized as

      S==Infinity.  If the schema were regular, the case S==0 would really

      denote a numbering in which all coded values are negative.)

      If S>0, the unsigned value of a byte sequence is regarded as a binary

      integer.  If any of the S low-order bits are zero, the corresponding

      signed value will be non-negative.  If all of the S low-order bits

      (S>0) are one, the the corresponding signed value will be negative.

      The non-negative signed values are compact and monotonically increasing

      (from 0) in the ordering of the corresponding unsigned values.

      The negative signed values are compact and monotonically decreasing

      (from -1) in the ordering of the corresponding unsigned values.

      In essence, the low-order S bits function as a collective sign bit

      for negative signed numbers, and as a low-order base-(2^S-1) digit

      for non-negative signed numbers.

      Therefore, the signed value corresponding to an unsigned value is:

      <pre>

        Sgn(x)  == x                               if S==0

        Sgn(x)  == (x / 2^S)*(2^S-1) + (x % 2^S),  if S>0, (x % 2^S) < 2^S-1

        Sgn(x)  == -(x / 2^S)-1,                   if S>0, (x % 2^S) == 2^S-1

      </pre>

      Finally, the value of a byte sequence, given the coding parameters

      (B,H,S), is defined as:

      <pre>

        V(b[i]: i<n)  == Sgn(U(b[i]: i<n))

      </pre>

      The extremal positive and negative signed value for a given range

      of unsigned values may be found by sign-encoding the largest unsigned

      value which is not 2^S-1 mod 2^S, and that which is, respectively.

      Because B,H,S are variable, this is not a single coding but a schema

      of codings.  For optimal compression, it is necessary to adaptively

      select specific codings to the data being compressed.

      For example, if a sequence of values happens never to be negative,

      S==0 is the best choice.  If the values are equally balanced between

      negative and positive, S==1.  If negative values are rare, then S>1

      is more appropriate.

      A (B,H,S) encoding is called a "subrange" if it does not encode

      the largest 32-bit value, and if the number R of values it does

      encode can be expressed as a positive 32-bit value.  (Note that

      B=1 implies R<=256, B=2 implies R<=65536, etc.)

      A delta version of a given (B,H,S) coding encodes an array of integers

      by writing their successive differences in the (B,H,S) coding.

      The original integers themselves may be recovered by making a

      running accumulation of sum of the differences as they are read.

      As a special case, if a (B,H,S) encoding is a subrange, its delta

      version will only encode arrays of numbers in the coding's unsigned

      range, [0..R-1].  The coding of deltas is still in the normal signed

      range, if S!=0.  During delta encoding, all subtraction results are

      reduced to the signed range, by adding multiples of R.  Likewise,

.     during encoding, all addition results are reduced to the unsigned range.

      This special case for subranges allows the benefits of wraparound

      when encoding correlated sequences of very small positive numbers.

     */

    // Code-specific limits:

    private static int saturate32(long x) {

        if (x > Integer.MAX_VALUE)   return Integer.MAX_VALUE;

        if (x < Integer.MIN_VALUE)   return Integer.MIN_VALUE;

        return (int)x;

    }

    private static long codeRangeLong(int B, int H) {

        return codeRangeLong(B, H, B);

    }

    private static long codeRangeLong(int B, int H, int nMax) {

        // Code range for a all (B,H) codes of length <=nMax (<=B).

        // n < B:   L*Sum[i<n]( H^i )

        // n == B:  L*Sum[i<B]( H^i ) + H^B

        assert(nMax >= 0 && nMax <= B);

        assert(B >= 1 && B <= 5);

        assert(H >= 1 && H <= 256);

        if (nMax == 0)  return 0;  // no codes of zero length

        if (B == 1)     return H;  // special case; see (**) above

        int L = 256-H;

        long sum = 0;

        long H_i = 1;

        for (int n = 1; n <= nMax; n++) {

            sum += H_i;

            H_i *= H;

        }

        sum *= L;

        if (nMax == B)

            sum += H_i;

        return sum;

    }

    /** Largest int representable by (B,H,S) in up to nMax bytes. */

    public static int codeMax(int B, int H, int S, int nMax) {

        //assert(S >= 0 && S <= S_MAX);

        long range = codeRangeLong(B, H, nMax);

        if (range == 0)

            return -1;  // degenerate max value for empty set of codes

        if (S == 0 || range >= (long)1<<32)

            return saturate32(range-1);

        long maxPos = range-1;

        while (isNegativeCode(maxPos, S))  --maxPos;

        if (maxPos < 0)  return -1;  // No positive codings at all.

        int smax = decodeSign32(maxPos, S);

        // check for 32-bit wraparound:

        if (smax < 0)

            return Integer.MAX_VALUE;

        return smax;

    }

    /** Smallest int representable by (B,H,S) in up to nMax bytes.

        Returns Integer.MIN_VALUE if 32-bit wraparound covers

        the entire negative range.

     */

    public static int codeMin(int B, int H, int S, int nMax) {

        //assert(S >= 0 && S <= S_MAX);

        long range = codeRangeLong(B, H, nMax);

        if (range >= (long)1<<32 && nMax == B) {

            // Can code negative values via 32-bit wraparound.

            return Integer.MIN_VALUE;

        }

        if (S == 0) {

            return 0;

        }

        int Smask = (1<<S)-1;

        long maxNeg = range-1;

        while (!isNegativeCode(maxNeg, S))  --maxNeg;

        if (maxNeg < 0)  return 0;  // No negative codings at all.

        return decodeSign32(maxNeg, S);

    }

    // Some of the arithmetic below is on unsigned 32-bit integers.

    // These must be represented in Java as longs in the range [0..2^32-1].

    // The conversion to a signed int is just the Java cast (int), but

    // the conversion to an unsigned int is the following little method:

    private static long toUnsigned32(int sx) {

        return ((long)sx << 32) >>> 32;

    }

    // Sign encoding:

    private static boolean isNegativeCode(long ux, int S) {

        assert(S > 0);

        assert(ux >= -1);  // can be out of 32-bit range; who cares

        int Smask = (1<<S)-1;

        return (((int)ux+1) & Smask) == 0;

    }

    private static boolean hasNegativeCode(int sx, int S) {

        assert(S > 0);

        // If S>=2 very low negatives are coded by 32-bit-wrapped positives.

        // The lowest negative representable by a negative coding is

        // ~(umax32 >> S), and the next lower number is coded by wrapping

        // the highest positive:

        //    CodePos(umax32-1)  ->  (umax32-1)-((umax32-1)>>S)

        // which simplifies to ~(umax32 >> S)-1.

        return (0 > sx) && (sx >= ~(-1>>>S));

    }

    private static int decodeSign32(long ux, int S) {

        assert(ux == toUnsigned32((int)ux))  // must be unsigned 32-bit number

            : (Long.toHexString(ux));

        if (S == 0) {

            return (int) ux;  // cast to signed int

        }

        int sx;

        if (isNegativeCode(ux, S)) {

            // Sgn(x)  == -(x / 2^S)-1

            sx = ~((int)ux >>> S);

        } else {

            // Sgn(x)  == (x / 2^S)*(2^S-1) + (x % 2^S)

            sx = (int)ux - ((int)ux >>> S);

        }

        // Assert special case of S==1:

        assert(!(S == 1) || sx == (((int)ux >>> 1) ^ -((int)ux & 1)));

        return sx;

    }

    private static long encodeSign32(int sx, int S) {

        if (S == 0) {

            return toUnsigned32(sx);  // unsigned 32-bit int

        }

        int Smask = (1<<S)-1;

        long ux;

        if (!hasNegativeCode(sx, S)) {

            // InvSgn(sx) = (sx / (2^S-1))*2^S + (sx % (2^S-1))

            ux = sx + (toUnsigned32(sx) / Smask);

        } else {

            // InvSgn(sx) = (-sx-1)*2^S + (2^S-1)

            ux = (-sx << S) - 1;

        }

        ux = toUnsigned32((int)ux);

        assert(sx == decodeSign32(ux, S))

            : (Long.toHexString(ux)+" -> "+

               Integer.toHexString(sx)+" != "+

               Integer.toHexString(decodeSign32(ux, S)));

        return ux;

    }

    // Top-level coding of single integers:

    public static void writeInt(byte[] out, int[] outpos, int sx, int B, int H, int S) {

        long ux = encodeSign32(sx, S);

        assert(ux == toUnsigned32((int)ux));

        assert(ux < codeRangeLong(B, H))

            : Long.toHexString(ux);

        int L = 256-H;

        long sum = ux;

        int pos = outpos[0];

        for (int i = 0; i < B-1; i++) {

            if (sum < L)

                break;

            sum -= L;

            int b_i = (int)( L + (sum % H) );

            sum /= H;

            out[pos++] = (byte)b_i;

        }

        out[pos++] = (byte)sum;

        // Report number of bytes written by updating outpos[0]:

        outpos[0] = pos;

        // Check right away for mis-coding.

        //assert(sx == readInt(out, new int[1], B, H, S));

    }

    public static int readInt(byte[] in, int[] inpos, int B, int H, int S) {

        // U(b[i]: i<n) == Sum[i<n]( b[i] * H^i )

        int L = 256-H;

        long sum = 0;

        long H_i = 1;

        int pos = inpos[0];

        for (int i = 0; i < B; i++) {

            int b_i = in[pos++] & 0xFF;

            sum += b_i*H_i;

            H_i *= H;

            if (b_i < L)  break;

        }

        //assert(sum >= 0 && sum < codeRangeLong(B, H));

        // Report number of bytes read by updating inpos[0]:

        inpos[0] = pos;

        return decodeSign32(sum, S);

    }

    // The Stream version doesn't fetch a byte unless it is needed for coding.

    public static int readIntFrom(InputStream in, int B, int H, int S) throws IOException {

        // U(b[i]: i<n) == Sum[i<n]( b[i] * H^i )

        int L = 256-H;

        long sum = 0;

        long H_i = 1;

        for (int i = 0; i < B; i++) {

            int b_i = in.read();

            if (b_i < 0)  throw new RuntimeException("unexpected EOF");

            sum += b_i*H_i;

            H_i *= H;

            if (b_i < L)  break;

        }

        assert(sum >= 0 && sum < codeRangeLong(B, H));

        return decodeSign32(sum, S);

    }

    public static final int B_MAX = 5;    /* B: [1,5] */

    public static final int H_MAX = 256;  /* H: [1,256] */

    public static final int S_MAX = 2;    /* S: [0,2] */

    // END OF STATICS.

    private final int B; /*1..5*/       // # bytes (1..5)

    private final int H; /*1..256*/     // # codes requiring a higher byte

    private final int L; /*0..255*/     // # codes requiring a higher byte

    private final int S; /*0..3*/       // # low-order bits representing sign

    private final int del; /*0..2*/     // type of delta encoding (0 == none)

    private final int min;              // smallest representable value

    private final int max;              // largest representable value

    private final int umin;             // smallest representable uns. value

    private final int umax;             // largest representable uns. value

    private final int[] byteMin;        // smallest repr. value, given # bytes

    private final int[] byteMax;        // largest repr. value, given # bytes

    private Coding(int B, int H, int S) {

        this(B, H, S, 0);

    }

    private Coding(int B, int H, int S, int del) {

        this.B = B;

        this.H = H;

        this.L = 256-H;

        this.S = S;

        this.del = del;

        this.min = codeMin(B, H, S, B);

        this.max = codeMax(B, H, S, B);

        this.umin = codeMin(B, H, 0, B);

        this.umax = codeMax(B, H, 0, B);

        this.byteMin = new int[B];

        this.byteMax = new int[B];

        for (int nMax = 1; nMax <= B; nMax++) {

            byteMin[nMax-1] = codeMin(B, H, S, nMax);

            byteMax[nMax-1] = codeMax(B, H, S, nMax);

        }

    }

    public boolean equals(Object x) {

        if (!(x instanceof Coding))  return false;

        Coding that = (Coding) x;

        if (this.B != that.B)  return false;

        if (this.H != that.H)  return false;

        if (this.S != that.S)  return false;

        if (this.del != that.del)  return false;

        return true;

    }

    public int hashCode() {

        return (del<<14)+(S<<11)+(B<<8)+(H<<0);

    }

    private static HashMap codeMap;

    private static synchronized Coding of(int B, int H, int S, int del) {

        if (codeMap == null)  codeMap = new HashMap();

        Coding x0 = new Coding(B, H, S, del);

        Coding x1 = (Coding) codeMap.get(x0);

        if (x1 == null)  codeMap.put(x0, x1 = x0);

        return x1;

    }

    public static Coding of(int B, int H) {

        return of(B, H, 0, 0);

    }

    public static Coding of(int B, int H, int S) {

        return of(B, H, S, 0);

    }

    public boolean canRepresentValue(int x) {

        if (isSubrange())

            return canRepresentUnsigned(x);

        else

            return canRepresentSigned(x);

    }

    /** Can this coding represent a single value, possibly a delta?

     *  This ignores the D property.  That is, for delta codings,

     *  this tests whether a delta value of 'x' can be coded.

     *  For signed delta codings which produce unsigned end values,

     *  use canRepresentUnsigned.

     */

    public boolean canRepresentSigned(int x) {

        return (x >= min && x <= max);

    }

    /** Can this coding, apart from its S property,

     *  represent a single value?  (Negative values

     *  can only be represented via 32-bit overflow,

     *  so this returns true for negative values

     *  if isFullRange is true.)

     */

    public boolean canRepresentUnsigned(int x) {

        return (x >= umin && x <= umax);

    }

    // object-oriented code/decode

    public int readFrom(byte[] in, int[] inpos) {

        return readInt(in, inpos, B, H, S);

    }

    public void writeTo(byte[] out, int[] outpos, int x) {

        writeInt(out, outpos, x, B, H, S);

    }

    // Stream versions

    public int readFrom(InputStream in) throws IOException {

        return readIntFrom(in, B, H, S);

    }

    public void writeTo(OutputStream out, int x) throws IOException {

        byte[] buf = new byte[B];

        int[] pos = new int[1];

        writeInt(buf, pos, x, B, H, S);

        out.write(buf, 0, pos[0]);

    }

    // Stream/array versions

    public void readArrayFrom(InputStream in, int[] a, int start, int end) throws IOException {

        // %%% use byte[] buffer

        for (int i = start; i < end; i++)

            a[i] = readFrom(in);

        for (int dstep = 0; dstep < del; dstep++) {

            long state = 0;

            for (int i = start; i < end; i++) {

                state += a[i];

                // Reduce array values to the required range.

                if (isSubrange()) {

                    state = reduceToUnsignedRange(state);

                }

                a[i] = (int) state;

            }

        }

    }

    public void writeArrayTo(OutputStream out, int[] a, int start, int end) throws IOException {

        if (end <= start)  return;

        for (int dstep = 0; dstep < del; dstep++) {

            int[] deltas;

            if (!isSubrange())

                deltas = makeDeltas(a, start, end, 0, 0);

            else

                deltas = makeDeltas(a, start, end, min, max);

            a = deltas;

            start = 0;

            end = deltas.length;

        }

        // The following code is a buffered version of this loop:

        //    for (int i = start; i < end; i++)

        //        writeTo(out, a[i]);

        byte[] buf = new byte[1<<8];

        final int bufmax = buf.length-B;

        int[] pos = { 0 };

        for (int i = start; i < end; ) {

            while (pos[0] <= bufmax) {

                writeTo(buf, pos, a[i++]);

                if (i >= end)  break;

            }

            out.write(buf, 0, pos[0]);

            pos[0] = 0;

        }

    }

    /** Tell if the range of this coding (number of distinct

     *  representable values) can be expressed in 32 bits.

     */

    boolean isSubrange() {

        return max < Integer.MAX_VALUE

            && ((long)max - (long)min + 1) <= Integer.MAX_VALUE;

    }

    /** Tell if this coding can represent all 32-bit values.

     *  Note:  Some codings, such as unsigned ones, can be neither

     *  subranges nor full-range codings.

     */

    boolean isFullRange() {

        return max == Integer.MAX_VALUE && min == Integer.MIN_VALUE;

    }

    /** Return the number of values this coding (a subrange) can represent. */

    int getRange() {

        assert(isSubrange());

        return (max - min) + 1;  // range includes both min & max

    }

    Coding setB(int B) { return Coding.of(B, H, S, del); }