Back to index...

	/*
	* 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 + b1H + b2H^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;
	}
	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);
	}
	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 lmax = values[start];
	int lmin = lmax;
	for (int i = 1; i < len; i++) {
	int value = values[start+i];
	if (lmax < value) lmax = value;
	if (lmin > value) lmin = value;
	}
	return canRepresent(lmin, lmax);
	}

	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;
	}
	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 lmax = byteMax[n-1];
	int lmin = 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 > lmax) longer++;
	} else {
	if (value < lmin) 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 + 2S + 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;
	}
	}

Back to index...