/*
* Copyright (c) 2001, 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.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); }
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(Object x) {
Coding that = (Coding) x;
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);
}
for (int i = 10; i >= 0; i = (i << 1) - (i >> 3)) {
assert(bitWidth(i) == ceil_lg2(i + 1));
}
}
/** Number of significant bits in i, not counting sign bits.
* For positive i, it is ceil_lg2(i + 1).
*/
static int bitWidth(int i) {
if (i < 0) i = ~i; // change sign
int w = 0;
int lo = i;
if (lo < byteBitWidths.length)
return byteBitWidths[lo];
int hi;
hi = (lo >>> 16);
if (hi != 0) {
lo = hi;
w += 16;
}
hi = (lo >>> 8);
if (hi != 0) {
lo = hi;
w += 8;
}
w += byteBitWidths[lo];
//assert(w == ceil_lg2(i + 1));
return w;
}
/** Create an array of successive differences.
* If min==max, accept any and all 32-bit overflow.
* Otherwise, avoid 32-bit overflow, and reduce all differences
* to a value in the given range, by adding or subtracting
* multiples of the range cardinality (max-min+1).
* Also, the values are assumed to be in the range [0..(max-min)].
*/
static int[] makeDeltas(int[] values, int start, int end,
int min, int max) {
assert(max >= min);
int count = end-start;
int[] deltas = new int[count];
int state = 0;
if (min == max) {
for (int i = 0; i < count; i++) {
int value = values[start+i];
deltas[i] = value - state;
state = value;
}
} else {
for (int i = 0; i < count; i++) {
int value = values[start+i];
assert(value >= 0 && value+min <= max);
int delta = value - state;
assert(delta == (long)value - (long)state); // no overflow
state = value;
// Reduce delta values to the required range.
delta = reduceToSignedRange(delta, min, max);
deltas[i] = delta;
}
}
return deltas;
}
boolean canRepresent(int minValue, int maxValue) {
assert(minValue <= maxValue);
if (del > 0) {
if (isSubrange()) {
// We will force the values to reduce to the right subrange.
return canRepresentUnsigned(maxValue)
&& canRepresentUnsigned(minValue);
} else {
// Huge range; delta values must assume full 32-bit range.
return isFullRange();
}
}
else
// final values must be representable
return canRepresentSigned(maxValue)
&& canRepresentSigned(minValue);
}
boolean canRepresent(int[] values, int start, int end) {
int len = end-start;
if (len == 0) return true;
if (isFullRange()) return true;
// Calculate max, min:
int max = values[start];
int min = max;
for (int i = 1; i < len; i++) {
int value = values[start+i];
if (max < value) max = value;
if (min > value) min = value;
}
return canRepresent(min, max);
}
public double getBitLength(int value) { // implements BitMetric
return (double) getLength(value) * 8;
}
/** How many bytes are in the coding of this value?
* Returns Integer.MAX_VALUE if the value has no coding.
* The coding must not be a delta coding, since there is no
* definite size for a single value apart from its context.
*/
public int getLength(int value) {
if (isDelta() && isSubrange()) {
if (!canRepresentUnsigned(value))
return Integer.MAX_VALUE;
value = reduceToSignedRange(value);
}
if (value >= 0) {
for (int n = 0; n < B; n++) {
if (value <= byteMax[n]) return n+1;
}
} else {
for (int n = 0; n < B; n++) {
if (value >= byteMin[n]) return n+1;
}
}
return Integer.MAX_VALUE;
}
public int getLength(int[] values, int start, int end) {
int len = end-start;
if (B == 1) return len;
if (L == 0) return len * B;
if (isDelta()) {
int[] deltas;
if (!isSubrange())
deltas = makeDeltas(values, start, end, 0, 0);
else
deltas = makeDeltas(values, start, end, min, max);
//return Coding.of(B, H, S).getLength(deltas, 0, len);
values = deltas;
start = 0;
end = values.length;
}
int sum = len; // at least 1 byte per
// add extra bytes for extra-long values
for (int n = 1; n <= B; n++) {
// what is the coding interval [min..max] for n bytes?
int max = byteMax[n-1];
int min = byteMin[n-1];
int longer = 0; // count of guys longer than n bytes
for (int i = 0; i < len; i++) {
int value = values[start+i];
if (value >= 0) {
if (value > max) longer++;
} else {
if (value < min) longer++;
}
}
if (longer == 0) break; // no more passes needed
if (n == B) return Integer.MAX_VALUE; // cannot represent!
sum += longer;
}
return sum;
}
public byte[] getMetaCoding(Coding dflt) {
if (dflt == this) return new byte[]{ (byte) _meta_default };
int canonicalIndex = BandStructure.indexOf(this);
if (canonicalIndex > 0)
return new byte[]{ (byte) canonicalIndex };
return new byte[]{
(byte)_meta_arb,
(byte)(del + 2*S + 8*(B-1)),
(byte)(H-1)
};
}
public static int parseMetaCoding(byte[] bytes, int pos, Coding dflt, CodingMethod res[]) {
int op = bytes[pos++] & 0xFF;
if (_meta_canon_min <= op && op <= _meta_canon_max) {
Coding c = BandStructure.codingForIndex(op);
assert(c != null);
res[0] = c;
return pos;
}
if (op == _meta_arb) {
int dsb = bytes[pos++] & 0xFF;
int H_1 = bytes[pos++] & 0xFF;
int del = dsb % 2;
int S = (dsb / 2) % 4;
int B = (dsb / 8)+1;
int H = H_1+1;
if (!((1 <= B && B <= B_MAX) &&
(0 <= S && S <= S_MAX) &&
(1 <= H && H <= H_MAX) &&
(0 <= del && del <= 1))
|| (B == 1 && H != 256)
|| (B == 5 && H == 256)) {
throw new RuntimeException("Bad arb. coding: ("+B+","+H+","+S+","+del);
}
res[0] = Coding.of(B, H, S, del);
return pos;
}
return pos-1; // backup
}
public String keyString() {
return "("+B+","+H+","+S+","+del+")";
}
public String toString() {
String str = "Coding"+keyString();
// If -ea, print out more informative strings!
//assert((str = stringForDebug()) != null);
return str;
}
static boolean verboseStringForDebug = false;
String stringForDebug() {
String minS = (min == Integer.MIN_VALUE ? "min" : ""+min);
String maxS = (max == Integer.MAX_VALUE ? "max" : ""+max);
String str = keyString()+" L="+L+" r=["+minS+","+maxS+"]";
if (isSubrange())
str += " subrange";
else if (!isFullRange())
str += " MIDRANGE";
if (verboseStringForDebug) {
str += " {";
int prev_range = 0;
for (int n = 1; n <= B; n++) {
int range_n = saturate32((long)byteMax[n-1] - byteMin[n-1] + 1);
assert(range_n == saturate32(codeRangeLong(B, H, n)));
range_n -= prev_range;
prev_range = range_n;
String rngS = (range_n == Integer.MAX_VALUE ? "max" : ""+range_n);
str += " #"+n+"="+rngS;
}
str += " }";
}
return str;
}
}