gt:         for (int i = 10; i >= 0; i = (i << 1) - (i >> 3)) {
context: /*
   * Copyright (c) 2001, 2011, 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.IOException;
  import java.io.InputStream;
  import java.io.OutputStream;
  import java.util.HashMap;
  import java.util.Map;
  import static com.sun.java.util.jar.pack.Constants.*;
  /**
   * 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 Comparable<Coding>, 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 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;
          }
          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 Map<Coding, Coding> 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 = 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); }
      Coding setH(int H) { return Coding.of(B, H, S, del); }
      Coding setS(int S) { return Coding.of(B, H, S, del); }
      Coding setL(int L) { return setH(256-L); }
      Coding setD(int del) { return Coding.of(B, H, S, del); }
      Coding getDeltaCoding() { return setD(del+1); }
  
      /** Return a coding suitable for representing summed, modulo-reduced values. */
      Coding getValueCoding() {
          if (isDelta())
              return Coding.of(B, H, 0, del-1);
          else
              return this;
      }
  
      /** Reduce the given value to be within this coding's unsigned range,
       *  by adding or subtracting a multiple of (max-min+1).
       */
      int reduceToUnsignedRange(long value) {
          if (value == (int)value && canRepresentUnsigned((int)value))
              // already in unsigned range
              return (int)value;
          int range = getRange();
          assert(range > 0);
          value %= range;
          if (value < 0)  value += range;
          assert(canRepresentUnsigned((int)value));
          return (int)value;
      }
  
      int reduceToSignedRange(int value) {
          if (canRepresentSigned(value))
              // already in signed range
              return value;
          return reduceToSignedRange(value, min, max);
      }
      static int reduceToSignedRange(int value, int min, int max) {
          int range = (max-min+1);
          assert(range > 0);
          int value0 = value;
          value -= min;
          if (value < 0 && value0 >= 0) {
              // 32-bit overflow, but the next '%=' op needs to be unsigned
              value -= range;
              assert(value >= 0);
          }
          value %= range;
          if (value < 0)  value += range;
          value += min;
          assert(min <= value && value <= max);
          return value;
      }
  
      /** Does this coding support at least one negative value?
          Includes codings that can do so via 32-bit wraparound.
       */
      boolean isSigned() {
          return min < 0;
      }
      /** Does this coding code arrays by making successive differences? */
      boolean isDelta() {
          return del != 0;
      }
  
      public int B() { return B; }
      public int H() { return H; }
      public int L() { return L; }
      public int S() { return S; }
      public int del() { return del; }
      public int min() { return min; }
      public int max() { return max; }
      public int umin() { return umin; }
      public int umax() { return umax; }
      public int byteMin(int b) { return byteMin[b-1]; }
      public int byteMax(int b) { return byteMax[b-1]; }
  
      public int compareTo(Coding that) {
          int dkey = this.del - that.del;
          if (dkey == 0)
              dkey = this.B - that.B;
          if (dkey == 0)
              dkey = this.H - that.H;
          if (dkey == 0)
              dkey = this.S - that.S;
          return dkey;
      }
  
      /** Heuristic measure of the difference between two codings. */
      public int distanceFrom(Coding that) {
          int diffdel = this.del - that.del;
          if (diffdel < 0)  diffdel = -diffdel;
          int diffS = this.S - that.S;
          if (diffS < 0)  diffS = -diffS;
          int diffB = this.B - that.B;
          if (diffB < 0)  diffB = -diffB;
          int diffHL;
          if (this.H == that.H) {
              diffHL = 0;
          } else {
              // Distance in log space of H (<=128) and L (<128).
              int thisHL = this.getHL();
              int thatHL = that.getHL();
              // Double the accuracy of the log:
              thisHL *= thisHL;
              thatHL *= thatHL;
              if (thisHL > thatHL)
                  diffHL = ceil_lg2(1+(thisHL-1)/thatHL);
              else
                  diffHL = ceil_lg2(1+(thatHL-1)/thisHL);
          }
          int norm = 5*(diffdel + diffS + diffB) + diffHL;
          assert(norm != 0 || this.compareTo(that) == 0);
          return norm;
      }
      private int getHL() {
          // Follow H in log space by the multiplicative inverse of L.
          if (H <= 128)  return H;
          if (L >= 1)    return 128*128/L;
          return 128*256;
      }
  
      /** ceiling(log[2](x)): {1->0, 2->1, 3->2, 4->2, ...} */
      static int ceil_lg2(int x) {
          assert(x-1 >= 0);  // x in range (int.MIN_VALUE -> 32)
          x -= 1;
          int lg = 0;
          while (x != 0) {
              lg++;
              x >>= 1;
          }
          return lg;
      }
  
      static private final byte[] byteBitWidths = new byte[0x100];
      static {
          for (int b = 0; b < byteBitWidths.length; b++) {
              byteBitWidths[b] = (byte) ceil_lg2(b + 1);
          }
  