src/share/classes/com/sun/java/util/jar/pack/PopulationCoding.java - platform/external/jetbrains/jdk8u_jdk - Git at Google

 /*
  * Copyright (c) 2003, 2010, Oracle and/or its affiliates. All rights reserved.
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  *
  * This code is free software; you can redistribute it and/or modify it
  * under the terms of the GNU General Public License version 2 only, as
  * published by the Free Software Foundation.  Oracle designates this
  * particular file as subject to the "Classpath" exception as provided
  * by Oracle in the LICENSE file that accompanied this code.
  *
  * This code is distributed in the hope that it will be useful, but WITHOUT
  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  * version 2 for more details (a copy is included in the LICENSE file that
  * accompanied this code).
  *
  * You should have received a copy of the GNU General Public License version
  * 2 along with this work; if not, write to the Free Software Foundation,
  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  *
  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  * or visit www.oracle.com if you need additional information or have any
  * questions.
  */

 package com.sun.java.util.jar.pack;

 import java.io.ByteArrayOutputStream;
 import java.io.IOException;
 import java.io.InputStream;
 import java.io.OutputStream;
 import java.util.Arrays;
 import java.util.HashSet;
 import java.util.Set;
 import static com.sun.java.util.jar.pack.Constants.*;

 /**
  * Population-based coding.
  * See the section "Encodings of Uncorrelated Values" in the Pack200 spec.
  * @author John Rose
  */
 // This tactic alone reduces the final zipped rt.jar by about a percent.
 class PopulationCoding implements CodingMethod {
     Histogram vHist;   // histogram of all values
     int[]     fValues; // list of favored values
     int       fVlen;   // inclusive max index
     long[]    symtab;  // int map of favored value -> token [1..#fValues]

     CodingMethod favoredCoding;
     CodingMethod tokenCoding;
     CodingMethod unfavoredCoding;

     int L = -1;  //preferred L value for tokenCoding

     public void setFavoredValues(int[] fValues, int fVlen) {
         // Note:  {f} is allFavoredValues[1..fvlen], not [0..fvlen-1].
         // This is because zero is an exceptional favored value index.
         assert(fValues[0] == 0);  // must be empty
         assert(this.fValues == null);  // do not do this twice
         this.fValues = fValues;
         this.fVlen   = fVlen;
         if (L >= 0) {
             setL(L);  // reassert
         }
     }
     public void setFavoredValues(int[] fValues) {
         int lfVlen = fValues.length-1;
         setFavoredValues(fValues, lfVlen);
     }
     public void setHistogram(Histogram vHist) {
         this.vHist = vHist;
     }
     public void setL(int L) {
         this.L = L;
         if (L >= 0 && fValues != null && tokenCoding == null) {
             tokenCoding = fitTokenCoding(fVlen, L);
             assert(tokenCoding != null);
         }
     }

     public static Coding fitTokenCoding(int fVlen, int L) {
         // Find the smallest B s.t. (B,H,0) covers fVlen.
         if (fVlen < 256)
             // H/L do not matter when B==1
             return BandStructure.BYTE1;
         Coding longest = BandStructure.UNSIGNED5.setL(L);
         if (!longest.canRepresentUnsigned(fVlen))
             return null;  // failure; L is too sharp and fVlen too large
         Coding tc = longest;
         for (Coding shorter = longest; ; ) {
             shorter = shorter.setB(shorter.B()-1);
             if (shorter.umax() < fVlen)
                 break;
             tc = shorter;  // shorten it by reducing B
         }
         return tc;
     }

     public void setFavoredCoding(CodingMethod favoredCoding) {
         this.favoredCoding = favoredCoding;
     }
     public void setTokenCoding(CodingMethod tokenCoding) {
         this.tokenCoding = tokenCoding;
         this.L = -1;
         if (tokenCoding instanceof Coding && fValues != null) {
             Coding tc = (Coding) tokenCoding;
             if (tc == fitTokenCoding(fVlen, tc.L()))
                 this.L = tc.L();
             // Otherwise, it's a non-default coding.
         }
     }
     public void setUnfavoredCoding(CodingMethod unfavoredCoding) {
         this.unfavoredCoding = unfavoredCoding;
     }

     public int favoredValueMaxLength() {
         if (L == 0)
             return Integer.MAX_VALUE;
         else
             return BandStructure.UNSIGNED5.setL(L).umax();
     }

     public void resortFavoredValues() {
         Coding tc = (Coding) tokenCoding;
         // Make a local copy before reordering.
         fValues = BandStructure.realloc(fValues, 1+fVlen);
         // Resort favoredValues within each byte-size cadre.
         int fillp = 1;  // skip initial zero
         for (int n = 1; n <= tc.B(); n++) {
             int nmax = tc.byteMax(n);
             if (nmax > fVlen)
                 nmax = fVlen;
             if (nmax < tc.byteMin(n))
                 break;
             int low = fillp;
             int high = nmax+1;
             if (high == low)  continue;
             assert(high > low)
                 : high+"!>"+low;
             assert(tc.getLength(low) == n)
                 : n+" != len("+(low)+") == "+
                   tc.getLength(low);
             assert(tc.getLength(high-1) == n)
                 : n+" != len("+(high-1)+") == "+
                   tc.getLength(high-1);
             int midTarget = low + (high-low)/2;
             int mid = low;
             // Divide the values into cadres, and sort within each.
             int prevCount = -1;
             int prevLimit = low;
             for (int i = low; i < high; i++) {
                 int val = fValues[i];
                 int count = vHist.getFrequency(val);
                 if (prevCount != count) {
                     if (n == 1) {
                         // For the single-byte encoding, keep strict order
                         // among frequency groups.
                         Arrays.sort(fValues, prevLimit, i);
                     } else if (Math.abs(mid - midTarget) >
                                Math.abs(i   - midTarget)) {
                         // Find a single inflection point
                         // close to the middle of the byte-size cadre.
                         mid = i;
                     }
                     prevCount = count;
                     prevLimit = i;
                 }
             }
             if (n == 1) {
                 Arrays.sort(fValues, prevLimit, high);
             } else {
                 // Sort up to the midpoint, if any.
                 Arrays.sort(fValues, low, mid);
                 Arrays.sort(fValues, mid, high);
             }
             assert(tc.getLength(low) == tc.getLength(mid));
             assert(tc.getLength(low) == tc.getLength(high-1));
             fillp = nmax+1;
         }
         assert(fillp == fValues.length);

         // Reset symtab.
         symtab = null;
     }

     public int getToken(int value) {
         if (symtab == null)
             symtab = makeSymtab();
         int pos = Arrays.binarySearch(symtab, (long)value << 32);
         if (pos < 0)  pos = -pos-1;
         if (pos < symtab.length && value == (int)(symtab[pos] >>> 32))
             return (int)symtab[pos];
         else
             return 0;
     }

     public int[][] encodeValues(int[] values, int start, int end) {
         // Compute token sequence.
         int[] tokens = new int[end-start];
         int nuv = 0;
         for (int i = 0; i < tokens.length; i++) {
             int val = values[start+i];
             int tok = getToken(val);
             if (tok != 0)
                 tokens[i] = tok;
             else
                 nuv += 1;
         }
         // Compute unfavored value sequence.
         int[] unfavoredValues = new int[nuv];
         nuv = 0;  // reset
         for (int i = 0; i < tokens.length; i++) {
             if (tokens[i] != 0)  continue;  // already covered
             int val = values[start+i];
             unfavoredValues[nuv++] = val;
         }
         assert(nuv == unfavoredValues.length);
         return new int[][]{ tokens, unfavoredValues };
     }

     private long[] makeSymtab() {
         long[] lsymtab = new long[fVlen];
         for (int token = 1; token <= fVlen; token++) {
             lsymtab[token-1] = ((long)fValues[token] << 32) | token;
         }
         // Index by value:
         Arrays.sort(lsymtab);
         return lsymtab;
     }

     private Coding getTailCoding(CodingMethod c) {
         while (c instanceof AdaptiveCoding)
             c = ((AdaptiveCoding)c).tailCoding;
         return (Coding) c;
     }

     // CodingMethod methods.
     public void writeArrayTo(OutputStream out, int[] a, int start, int end) throws IOException {
         int[][] vals = encodeValues(a, start, end);
         writeSequencesTo(out, vals[0], vals[1]);
     }
     void writeSequencesTo(OutputStream out, int[] tokens, int[] uValues) throws IOException {
         favoredCoding.writeArrayTo(out, fValues, 1, 1+fVlen);
         getTailCoding(favoredCoding).writeTo(out, computeSentinelValue());
         tokenCoding.writeArrayTo(out, tokens, 0, tokens.length);
         if (uValues.length > 0)
             unfavoredCoding.writeArrayTo(out, uValues, 0, uValues.length);
     }

    int computeSentinelValue() {
         Coding fc = getTailCoding(favoredCoding);
         if (fc.isDelta()) {
             // repeat the last favored value, using delta=0
             return 0;
         } else {
             // else repeat the shorter of the min or last value
             int min = fValues[1];
             int last = min;
             // (remember that fVlen is an inclusive limit in fValues)
             for (int i = 2; i <= fVlen; i++) {
                 last = fValues[i];
                 min = moreCentral(min, last);
             }
             int endVal;
             if (fc.getLength(min) <= fc.getLength(last))
                 return min;
             else
                 return last;
         }
    }

     public void readArrayFrom(InputStream in, int[] a, int start, int end) throws IOException {
         // Parameters are fCode, L, uCode.
         setFavoredValues(readFavoredValuesFrom(in, end-start));
         // Read the tokens.  Read them into the final array, for the moment.
         tokenCoding.readArrayFrom(in, a, start, end);
         // Decode the favored tokens.
         int headp = 0, tailp = -1;
         int uVlen = 0;
         for (int i = start; i < end; i++) {
             int tok = a[i];
             if (tok == 0) {
                 // Make a linked list, and decode in a second pass.
                 if (tailp < 0) {
                     headp = i;
                 } else {
                     a[tailp] = i;
                 }
                 tailp = i;
                 uVlen += 1;
             } else {
                 a[i] = fValues[tok];
             }
         }
         // Walk the linked list of "zero" locations, decoding unfavored vals.
         int[] uValues = new int[uVlen];
         if (uVlen > 0)
             unfavoredCoding.readArrayFrom(in, uValues, 0, uVlen);
         for (int i = 0; i < uVlen; i++) {
             int nextp = a[headp];
             a[headp] = uValues[i];
             headp = nextp;
         }
     }

     int[] readFavoredValuesFrom(InputStream in, int maxForDebug) throws IOException {
         int[] lfValues = new int[1000];  // realloc as needed
         // The set uniqueValuesForDebug records all favored values.
         // As each new value is added, we assert that the value
         // was not already in the set.
         Set<Integer> uniqueValuesForDebug = null;
         assert((uniqueValuesForDebug = new HashSet<>()) != null);
         int fillp = 1;
         maxForDebug += fillp;
         int min = Integer.MIN_VALUE;  // farthest from the center
         //int min2 = Integer.MIN_VALUE;  // emulate buggy 150.7 spec.
         int last = 0;
         CodingMethod fcm = favoredCoding;
         while (fcm instanceof AdaptiveCoding) {
             AdaptiveCoding ac = (AdaptiveCoding) fcm;
             int len = ac.headLength;
             while (fillp + len > lfValues.length) {
                 lfValues = BandStructure.realloc(lfValues);
             }
             int newFillp = fillp + len;
             ac.headCoding.readArrayFrom(in, lfValues, fillp, newFillp);
             while (fillp < newFillp) {
                 int val = lfValues[fillp++];
                 assert(uniqueValuesForDebug.add(val));
                 assert(fillp <= maxForDebug);
                 last = val;
                 min = moreCentral(min, val);
                 //min2 = moreCentral2(min2, val, min);
             }
             fcm = ac.tailCoding;
         }
         Coding fc = (Coding) fcm;
         if (fc.isDelta()) {
             for (long state = 0;;) {
                 // Read a new value:
                 state += fc.readFrom(in);
                 int val;
                 if (fc.isSubrange())
                     val = fc.reduceToUnsignedRange(state);
                 else
                     val = (int)state;
                 state = val;
                 if (fillp > 1 && (val == last || val == min)) //|| val == min2
                     break;
                 if (fillp == lfValues.length)
                     lfValues = BandStructure.realloc(lfValues);
                 lfValues[fillp++] = val;
                 assert(uniqueValuesForDebug.add(val));
                 assert(fillp <= maxForDebug);
                 last = val;
                 min = moreCentral(min, val);
                 //min2 = moreCentral(min2, val);
             }
         } else {
             for (;;) {
                 int val = fc.readFrom(in);
                 if (fillp > 1 && (val == last || val == min)) //|| val == min2
                     break;
                 if (fillp == lfValues.length)
                     lfValues = BandStructure.realloc(lfValues);
                 lfValues[fillp++] = val;
                 assert(uniqueValuesForDebug.add(val));
                 assert(fillp <= maxForDebug);
                 last = val;
                 min = moreCentral(min, val);
                 //min2 = moreCentral2(min2, val, min);
             }
         }
         return BandStructure.realloc(lfValues, fillp);
     }

     private static int moreCentral(int x, int y) {
         int kx = (x >> 31) ^ (x << 1);
         int ky = (y >> 31) ^ (y << 1);
         // bias kx/ky to get an unsigned comparison:
         kx -= Integer.MIN_VALUE;
         ky -= Integer.MIN_VALUE;
         int xy = (kx < ky? x: y);
         // assert that this ALU-ish version is the same:
         assert(xy == moreCentralSlow(x, y));
         return xy;
     }
 //  private static int moreCentral2(int x, int y, int min) {
 //      // Strict implementation of buggy 150.7 specification.
 //      // The bug is that the spec. says absolute-value ties are broken
 //      // in favor of positive numbers, but the suggested implementation
 //      // (also mentioned in the spec.) breaks ties in favor of negatives.
 //      if (x + y == 0)  return (x > y? x : y);
 //      return min;
 //  }
     private static int moreCentralSlow(int x, int y) {
         int ax = x;
         if (ax < 0)  ax = -ax;
         if (ax < 0)  return y;  //x is MIN_VALUE
         int ay = y;
         if (ay < 0)  ay = -ay;
         if (ay < 0)  return x;  //y is MIN_VALUE
         if (ax < ay)  return x;
         if (ax > ay)  return y;
         // At this point the absolute values agree, and the negative wins.
         return x < y ? x : y;
     }

     static final int[] LValuesCoded
         = { -1, 4, 8, 16, 32, 64, 128, 192, 224, 240, 248, 252 };

     public byte[] getMetaCoding(Coding dflt) {
         int K = fVlen;
         int LCoded = 0;
         if (tokenCoding instanceof Coding) {
             Coding tc = (Coding) tokenCoding;
             if (tc.B() == 1) {
                 LCoded = 1;
             } else if (L >= 0) {
                 assert(L == tc.L());
                 for (int i = 1; i < LValuesCoded.length; i++) {
                     if (LValuesCoded[i] == L) { LCoded = i; break; }
                 }
             }
         }
         CodingMethod tokenDflt = null;
         if (LCoded != 0 && tokenCoding == fitTokenCoding(fVlen, L)) {
             // A simple L value is enough to recover the tokenCoding.
             tokenDflt = tokenCoding;
         }
         int FDef = (favoredCoding == dflt)?1:0;
         int UDef = (unfavoredCoding == dflt || unfavoredCoding == null)?1:0;
         int TDef = (tokenCoding == tokenDflt)?1:0;
         int TDefL = (TDef == 1) ? LCoded : 0;
         assert(TDef == ((TDefL>0)?1:0));
         ByteArrayOutputStream bytes = new ByteArrayOutputStream(10);
         bytes.write(_meta_pop + FDef + 2*UDef + 4*TDefL);
         try {
             if (FDef == 0)  bytes.write(favoredCoding.getMetaCoding(dflt));
             if (TDef == 0)  bytes.write(tokenCoding.getMetaCoding(dflt));
             if (UDef == 0)  bytes.write(unfavoredCoding.getMetaCoding(dflt));
         } catch (IOException ee) {
             throw new RuntimeException(ee);
         }
         return bytes.toByteArray();
     }
     public static int parseMetaCoding(byte[] bytes, int pos, Coding dflt, CodingMethod res[]) {
         int op = bytes[pos++] & 0xFF;
         if (op < _meta_pop || op >= _meta_limit)  return pos-1; // backup
         op -= _meta_pop;
         int FDef = op % 2;
         int UDef = (op / 2) % 2;
         int TDefL = (op / 4);
         int TDef = (TDefL > 0)?1:0;
         int L = LValuesCoded[TDefL];
         CodingMethod[] FCode = {dflt}, TCode = {null}, UCode = {dflt};
         if (FDef == 0)
             pos = BandStructure.parseMetaCoding(bytes, pos, dflt, FCode);
         if (TDef == 0)
             pos = BandStructure.parseMetaCoding(bytes, pos, dflt, TCode);
         if (UDef == 0)
             pos = BandStructure.parseMetaCoding(bytes, pos, dflt, UCode);
         PopulationCoding pop = new PopulationCoding();
         pop.L = L;  // might be -1
         pop.favoredCoding   = FCode[0];
         pop.tokenCoding     = TCode[0];  // might be null!
         pop.unfavoredCoding = UCode[0];
         res[0] = pop;
         return pos;
     }

     private String keyString(CodingMethod m) {
         if (m instanceof Coding)
             return ((Coding)m).keyString();
         if (m == null)
             return "none";
         return m.toString();
     }
     public String toString() {
         PropMap p200 = Utils.currentPropMap();
         boolean verbose
             = (p200 != null &&
                p200.getBoolean(Utils.COM_PREFIX+"verbose.pop"));
         StringBuilder res = new StringBuilder(100);
         res.append("pop(").append("fVlen=").append(fVlen);
         if (verbose && fValues != null) {
             res.append(" fV=[");
             for (int i = 1; i <= fVlen; i++) {
                 res.append(i==1?"":",").append(fValues[i]);
             }
             res.append(";").append(computeSentinelValue());
             res.append("]");
         }
         res.append(" fc=").append(keyString(favoredCoding));
         res.append(" tc=").append(keyString(tokenCoding));
         res.append(" uc=").append(keyString(unfavoredCoding));
         res.append(")");
         return res.toString();
     }
 }
	/*
	* Copyright (c) 2003, 2010, Oracle and/or its affiliates. All rights reserved.
	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
	*
	* This code is free software; you can redistribute it and/or modify it
	* under the terms of the GNU General Public License version 2 only, as
	* published by the Free Software Foundation. Oracle designates this
	* particular file as subject to the "Classpath" exception as provided
	* by Oracle in the LICENSE file that accompanied this code.
	*
	* This code is distributed in the hope that it will be useful, but WITHOUT
	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
	* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
	* version 2 for more details (a copy is included in the LICENSE file that
	* accompanied this code).
	*
	* You should have received a copy of the GNU General Public License version
	* 2 along with this work; if not, write to the Free Software Foundation,
	* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
	*
	* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
	* or visit www.oracle.com if you need additional information or have any
	* questions.
	*/

	package com.sun.java.util.jar.pack;

	import java.io.ByteArrayOutputStream;
	import java.io.IOException;
	import java.io.InputStream;
	import java.io.OutputStream;
	import java.util.Arrays;
	import java.util.HashSet;
	import java.util.Set;
	import static com.sun.java.util.jar.pack.Constants.*;

	/**
	* Population-based coding.
	* See the section "Encodings of Uncorrelated Values" in the Pack200 spec.
	* @author John Rose
	*/
	// This tactic alone reduces the final zipped rt.jar by about a percent.
	class PopulationCoding implements CodingMethod {
	Histogram vHist; // histogram of all values
	int[] fValues; // list of favored values
	int fVlen; // inclusive max index
	long[] symtab; // int map of favored value -> token [1..#fValues]

	CodingMethod favoredCoding;
	CodingMethod tokenCoding;
	CodingMethod unfavoredCoding;

	int L = -1; //preferred L value for tokenCoding

	public void setFavoredValues(int[] fValues, int fVlen) {
	// Note: {f} is allFavoredValues[1..fvlen], not [0..fvlen-1].
	// This is because zero is an exceptional favored value index.
	assert(fValues[0] == 0); // must be empty
	assert(this.fValues == null); // do not do this twice
	this.fValues = fValues;
	this.fVlen = fVlen;
	if (L >= 0) {
	setL(L); // reassert
	}
	}
	public void setFavoredValues(int[] fValues) {
	int lfVlen = fValues.length-1;
	setFavoredValues(fValues, lfVlen);
	}
	public void setHistogram(Histogram vHist) {
	this.vHist = vHist;
	}
	public void setL(int L) {
	this.L = L;
	if (L >= 0 && fValues != null && tokenCoding == null) {
	tokenCoding = fitTokenCoding(fVlen, L);
	assert(tokenCoding != null);
	}
	}

	public static Coding fitTokenCoding(int fVlen, int L) {
	// Find the smallest B s.t. (B,H,0) covers fVlen.
	if (fVlen < 256)
	// H/L do not matter when B==1
	return BandStructure.BYTE1;
	Coding longest = BandStructure.UNSIGNED5.setL(L);
	if (!longest.canRepresentUnsigned(fVlen))
	return null; // failure; L is too sharp and fVlen too large
	Coding tc = longest;
	for (Coding shorter = longest; ; ) {
	shorter = shorter.setB(shorter.B()-1);
	if (shorter.umax() < fVlen)
	break;
	tc = shorter; // shorten it by reducing B
	}
	return tc;
	}

	public void setFavoredCoding(CodingMethod favoredCoding) {
	this.favoredCoding = favoredCoding;
	}
	public void setTokenCoding(CodingMethod tokenCoding) {
	this.tokenCoding = tokenCoding;
	this.L = -1;
	if (tokenCoding instanceof Coding && fValues != null) {
	Coding tc = (Coding) tokenCoding;
	if (tc == fitTokenCoding(fVlen, tc.L()))
	this.L = tc.L();
	// Otherwise, it's a non-default coding.
	}
	}
	public void setUnfavoredCoding(CodingMethod unfavoredCoding) {
	this.unfavoredCoding = unfavoredCoding;
	}

	public int favoredValueMaxLength() {
	if (L == 0)
	return Integer.MAX_VALUE;
	else
	return BandStructure.UNSIGNED5.setL(L).umax();
	}

	public void resortFavoredValues() {
	Coding tc = (Coding) tokenCoding;
	// Make a local copy before reordering.
	fValues = BandStructure.realloc(fValues, 1+fVlen);
	// Resort favoredValues within each byte-size cadre.
	int fillp = 1; // skip initial zero
	for (int n = 1; n <= tc.B(); n++) {
	int nmax = tc.byteMax(n);
	if (nmax > fVlen)
	nmax = fVlen;
	if (nmax < tc.byteMin(n))
	break;
	int low = fillp;
	int high = nmax+1;
	if (high == low) continue;
	assert(high > low)
	: high+"!>"+low;
	assert(tc.getLength(low) == n)
	: n+" != len("+(low)+") == "+
	tc.getLength(low);
	assert(tc.getLength(high-1) == n)
	: n+" != len("+(high-1)+") == "+
	tc.getLength(high-1);
	int midTarget = low + (high-low)/2;
	int mid = low;
	// Divide the values into cadres, and sort within each.
	int prevCount = -1;
	int prevLimit = low;
	for (int i = low; i < high; i++) {
	int val = fValues[i];
	int count = vHist.getFrequency(val);
	if (prevCount != count) {
	if (n == 1) {
	// For the single-byte encoding, keep strict order
	// among frequency groups.
	Arrays.sort(fValues, prevLimit, i);
	} else if (Math.abs(mid - midTarget) >
	Math.abs(i - midTarget)) {
	// Find a single inflection point
	// close to the middle of the byte-size cadre.
	mid = i;
	}
	prevCount = count;
	prevLimit = i;
	}
	}
	if (n == 1) {
	Arrays.sort(fValues, prevLimit, high);
	} else {
	// Sort up to the midpoint, if any.
	Arrays.sort(fValues, low, mid);
	Arrays.sort(fValues, mid, high);
	}
	assert(tc.getLength(low) == tc.getLength(mid));
	assert(tc.getLength(low) == tc.getLength(high-1));
	fillp = nmax+1;
	}
	assert(fillp == fValues.length);

	// Reset symtab.
	symtab = null;
	}

	public int getToken(int value) {
	if (symtab == null)
	symtab = makeSymtab();
	int pos = Arrays.binarySearch(symtab, (long)value << 32);
	if (pos < 0) pos = -pos-1;
	if (pos < symtab.length && value == (int)(symtab[pos] >>> 32))
	return (int)symtab[pos];
	else
	return 0;
	}

	public int[][] encodeValues(int[] values, int start, int end) {
	// Compute token sequence.
	int[] tokens = new int[end-start];
	int nuv = 0;
	for (int i = 0; i < tokens.length; i++) {
	int val = values[start+i];
	int tok = getToken(val);
	if (tok != 0)
	tokens[i] = tok;
	else
	nuv += 1;
	}
	// Compute unfavored value sequence.
	int[] unfavoredValues = new int[nuv];
	nuv = 0; // reset
	for (int i = 0; i < tokens.length; i++) {
	if (tokens[i] != 0) continue; // already covered
	int val = values[start+i];
	unfavoredValues[nuv++] = val;
	}
	assert(nuv == unfavoredValues.length);
	return new int[][]{ tokens, unfavoredValues };
	}

	private long[] makeSymtab() {
	long[] lsymtab = new long[fVlen];
	for (int token = 1; token <= fVlen; token++) {
	lsymtab[token-1] = ((long)fValues[token] << 32) \| token;
	}
	// Index by value:
	Arrays.sort(lsymtab);
	return lsymtab;
	}

	private Coding getTailCoding(CodingMethod c) {
	while (c instanceof AdaptiveCoding)
	c = ((AdaptiveCoding)c).tailCoding;
	return (Coding) c;
	}

	// CodingMethod methods.
	public void writeArrayTo(OutputStream out, int[] a, int start, int end) throws IOException {
	int[][] vals = encodeValues(a, start, end);
	writeSequencesTo(out, vals[0], vals[1]);
	}
	void writeSequencesTo(OutputStream out, int[] tokens, int[] uValues) throws IOException {
	favoredCoding.writeArrayTo(out, fValues, 1, 1+fVlen);
	getTailCoding(favoredCoding).writeTo(out, computeSentinelValue());
	tokenCoding.writeArrayTo(out, tokens, 0, tokens.length);
	if (uValues.length > 0)
	unfavoredCoding.writeArrayTo(out, uValues, 0, uValues.length);
	}

	int computeSentinelValue() {
	Coding fc = getTailCoding(favoredCoding);
	if (fc.isDelta()) {
	// repeat the last favored value, using delta=0
	return 0;
	} else {
	// else repeat the shorter of the min or last value
	int min = fValues[1];
	int last = min;
	// (remember that fVlen is an inclusive limit in fValues)
	for (int i = 2; i <= fVlen; i++) {
	last = fValues[i];
	min = moreCentral(min, last);
	}
	int endVal;
	if (fc.getLength(min) <= fc.getLength(last))
	return min;
	else
	return last;
	}
	}

	public void readArrayFrom(InputStream in, int[] a, int start, int end) throws IOException {
	// Parameters are fCode, L, uCode.
	setFavoredValues(readFavoredValuesFrom(in, end-start));
	// Read the tokens. Read them into the final array, for the moment.
	tokenCoding.readArrayFrom(in, a, start, end);
	// Decode the favored tokens.
	int headp = 0, tailp = -1;
	int uVlen = 0;
	for (int i = start; i < end; i++) {
	int tok = a[i];
	if (tok == 0) {
	// Make a linked list, and decode in a second pass.
	if (tailp < 0) {
	headp = i;
	} else {
	a[tailp] = i;
	}
	tailp = i;
	uVlen += 1;
	} else {
	a[i] = fValues[tok];
	}
	}
	// Walk the linked list of "zero" locations, decoding unfavored vals.
	int[] uValues = new int[uVlen];
	if (uVlen > 0)
	unfavoredCoding.readArrayFrom(in, uValues, 0, uVlen);
	for (int i = 0; i < uVlen; i++) {
	int nextp = a[headp];
	a[headp] = uValues[i];
	headp = nextp;
	}
	}

	int[] readFavoredValuesFrom(InputStream in, int maxForDebug) throws IOException {
	int[] lfValues = new int[1000]; // realloc as needed
	// The set uniqueValuesForDebug records all favored values.
	// As each new value is added, we assert that the value
	// was not already in the set.
	Set<Integer> uniqueValuesForDebug = null;
	assert((uniqueValuesForDebug = new HashSet<>()) != null);
	int fillp = 1;
	maxForDebug += fillp;
	int min = Integer.MIN_VALUE; // farthest from the center
	//int min2 = Integer.MIN_VALUE; // emulate buggy 150.7 spec.
	int last = 0;
	CodingMethod fcm = favoredCoding;
	while (fcm instanceof AdaptiveCoding) {
	AdaptiveCoding ac = (AdaptiveCoding) fcm;
	int len = ac.headLength;
	while (fillp + len > lfValues.length) {
	lfValues = BandStructure.realloc(lfValues);
	}
	int newFillp = fillp + len;
	ac.headCoding.readArrayFrom(in, lfValues, fillp, newFillp);
	while (fillp < newFillp) {
	int val = lfValues[fillp++];
	assert(uniqueValuesForDebug.add(val));
	assert(fillp <= maxForDebug);
	last = val;
	min = moreCentral(min, val);
	//min2 = moreCentral2(min2, val, min);
	}
	fcm = ac.tailCoding;
	}
	Coding fc = (Coding) fcm;
	if (fc.isDelta()) {
	for (long state = 0;;) {
	// Read a new value:
	state += fc.readFrom(in);
	int val;
	if (fc.isSubrange())
	val = fc.reduceToUnsignedRange(state);
	else
	val = (int)state;
	state = val;
	if (fillp > 1 && (val == last \|\| val == min)) //\|\| val == min2
	break;
	if (fillp == lfValues.length)
	lfValues = BandStructure.realloc(lfValues);
	lfValues[fillp++] = val;
	assert(uniqueValuesForDebug.add(val));
	assert(fillp <= maxForDebug);
	last = val;
	min = moreCentral(min, val);
	//min2 = moreCentral(min2, val);
	}
	} else {
	for (;;) {
	int val = fc.readFrom(in);
	if (fillp > 1 && (val == last \|\| val == min)) //\|\| val == min2
	break;
	if (fillp == lfValues.length)
	lfValues = BandStructure.realloc(lfValues);
	lfValues[fillp++] = val;
	assert(uniqueValuesForDebug.add(val));
	assert(fillp <= maxForDebug);
	last = val;
	min = moreCentral(min, val);
	//min2 = moreCentral2(min2, val, min);
	}
	}
	return BandStructure.realloc(lfValues, fillp);
	}

	private static int moreCentral(int x, int y) {
	int kx = (x >> 31) ^ (x << 1);
	int ky = (y >> 31) ^ (y << 1);
	// bias kx/ky to get an unsigned comparison:
	kx -= Integer.MIN_VALUE;
	ky -= Integer.MIN_VALUE;
	int xy = (kx < ky? x: y);
	// assert that this ALU-ish version is the same:
	assert(xy == moreCentralSlow(x, y));
	return xy;
	}
	// private static int moreCentral2(int x, int y, int min) {
	// // Strict implementation of buggy 150.7 specification.
	// // The bug is that the spec. says absolute-value ties are broken
	// // in favor of positive numbers, but the suggested implementation
	// // (also mentioned in the spec.) breaks ties in favor of negatives.
	// if (x + y == 0) return (x > y? x : y);
	// return min;
	// }
	private static int moreCentralSlow(int x, int y) {
	int ax = x;
	if (ax < 0) ax = -ax;
	if (ax < 0) return y; //x is MIN_VALUE
	int ay = y;
	if (ay < 0) ay = -ay;
	if (ay < 0) return x; //y is MIN_VALUE
	if (ax < ay) return x;
	if (ax > ay) return y;
	// At this point the absolute values agree, and the negative wins.
	return x < y ? x : y;
	}

	static final int[] LValuesCoded
	= { -1, 4, 8, 16, 32, 64, 128, 192, 224, 240, 248, 252 };

	public byte[] getMetaCoding(Coding dflt) {
	int K = fVlen;
	int LCoded = 0;
	if (tokenCoding instanceof Coding) {
	Coding tc = (Coding) tokenCoding;
	if (tc.B() == 1) {
	LCoded = 1;
	} else if (L >= 0) {
	assert(L == tc.L());
	for (int i = 1; i < LValuesCoded.length; i++) {
	if (LValuesCoded[i] == L) { LCoded = i; break; }
	}
	}
	}
	CodingMethod tokenDflt = null;
	if (LCoded != 0 && tokenCoding == fitTokenCoding(fVlen, L)) {
	// A simple L value is enough to recover the tokenCoding.
	tokenDflt = tokenCoding;
	}
	int FDef = (favoredCoding == dflt)?1:0;
	int UDef = (unfavoredCoding == dflt \|\| unfavoredCoding == null)?1:0;
	int TDef = (tokenCoding == tokenDflt)?1:0;
	int TDefL = (TDef == 1) ? LCoded : 0;
	assert(TDef == ((TDefL>0)?1:0));
	ByteArrayOutputStream bytes = new ByteArrayOutputStream(10);
	bytes.write(_meta_pop + FDef + 2UDef + 4TDefL);
	try {
	if (FDef == 0) bytes.write(favoredCoding.getMetaCoding(dflt));
	if (TDef == 0) bytes.write(tokenCoding.getMetaCoding(dflt));
	if (UDef == 0) bytes.write(unfavoredCoding.getMetaCoding(dflt));
	} catch (IOException ee) {
	throw new RuntimeException(ee);
	}
	return bytes.toByteArray();
	}
	public static int parseMetaCoding(byte[] bytes, int pos, Coding dflt, CodingMethod res[]) {
	int op = bytes[pos++] & 0xFF;
	if (op < _meta_pop \|\| op >= _meta_limit) return pos-1; // backup
	op -= _meta_pop;
	int FDef = op % 2;
	int UDef = (op / 2) % 2;
	int TDefL = (op / 4);
	int TDef = (TDefL > 0)?1:0;
	int L = LValuesCoded[TDefL];
	CodingMethod[] FCode = {dflt}, TCode = {null}, UCode = {dflt};
	if (FDef == 0)
	pos = BandStructure.parseMetaCoding(bytes, pos, dflt, FCode);
	if (TDef == 0)
	pos = BandStructure.parseMetaCoding(bytes, pos, dflt, TCode);
	if (UDef == 0)
	pos = BandStructure.parseMetaCoding(bytes, pos, dflt, UCode);
	PopulationCoding pop = new PopulationCoding();
	pop.L = L; // might be -1
	pop.favoredCoding = FCode[0];
	pop.tokenCoding = TCode[0]; // might be null!
	pop.unfavoredCoding = UCode[0];
	res[0] = pop;
	return pos;
	}

	private String keyString(CodingMethod m) {
	if (m instanceof Coding)
	return ((Coding)m).keyString();
	if (m == null)
	return "none";
	return m.toString();
	}
	public String toString() {
	PropMap p200 = Utils.currentPropMap();
	boolean verbose
	= (p200 != null &&
	p200.getBoolean(Utils.COM_PREFIX+"verbose.pop"));
	StringBuilder res = new StringBuilder(100);
	res.append("pop(").append("fVlen=").append(fVlen);
	if (verbose && fValues != null) {
	res.append(" fV=[");
	for (int i = 1; i <= fVlen; i++) {
	res.append(i==1?"":",").append(fValues[i]);
	}
	res.append(";").append(computeSentinelValue());
	res.append("]");
	}
	res.append(" fc=").append(keyString(favoredCoding));
	res.append(" tc=").append(keyString(tokenCoding));
	res.append(" uc=").append(keyString(unfavoredCoding));
	res.append(")");
	return res.toString();
	}
	}