/*
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* 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.
*/
/**
* Heuristic chooser of basic encodings.
* Runs "zip" to measure the apparent information content after coding.
* @author John Rose
*/
class CodingChooser {
int verbose;
int effort;
boolean optUseHistogram = true;
boolean optUsePopulationCoding = true;
boolean optUseAdaptiveCoding = true;
boolean disablePopCoding;
boolean disableRunCoding;
boolean topLevel = true;
// Derived from effort; >1 (<1) means try more (less) experiments
// when looking to beat a best score.
double fuzz;
// Element in sorted set of coding choices:
static
class Choice {
}
// These variables are reset and reused:
void reset() {
}
boolean isExtra() {
return index < 0;
}
return stringForDebug();
}
String s = "";
s += " so: "+searchOrder;
s += " md: "+minDistance;
if (zipSize > 0)
s += " zs: "+zipSize;
if (byteSize > 0)
s += " bs: "+byteSize;
if (histSize > 0)
s += " hs: "+histSize;
}
}
this.verbose
this.optUseHistogram
this.optUseAdaptiveCoding
int lstress
if (lstress != 0)
}
// The following line "makes sense" but is too much
// work for a simple heuristic.
//if (effort > 5) zipDef.setLevel(effort);
this.allCodingChoices = allCodingChoices;
// If effort = 9, look carefully at any solution
// whose initial metrics are within 1% of the best
// so far. If effort = 1, look carefully only at
// solutions whose initial metrics promise a 1% win.
int nc = 0;
if (allCodingChoices[i] == null) continue;
nc++;
}
nc = 0;
if (allCodingChoices[i] == null) continue;
}
for (int j = 0; j < i; j++) {
assert(dij > 0);
}
}
}
assert(dij > 0);
}
c.reset();
return c;
}
return context;
}
// These variables are reset and reused:
private int[] values;
private int[] deltas;
private int searchOrder;
private int bestByteSize;
private int bestZipSize;
this.searchOrder = 0;
this.regularChoice = null;
this.bestChoice = null;
this.bestMethod = null;
}
// Save the value array
}
return regular;
}
if (optUseHistogram) {
}
}
// Find all the preset choices that might be worth looking at:
// Make a random choice.
break;
}
}
} else {
// Pick a totally random coding 6% of the time.
}
}
if (!disablePopCoding
&& effort >= POP_EFFORT) {
}
if (!disableRunCoding
&& effort >= RUN_EFFORT) {
}
return coding;
}
double searchScale = 1.0;
for (int x = effort; x < MAX_EFFORT; x++) {
}
// Start by evaluating the "regular" choice.
// save these first-cut numbers for later
int zipSize1 = bestZipSize;
int byteSize1 = bestByteSize;
// Give credit for being the default; no band header is needed.
// Rather than increasing every other size value by the band
// header amount, we decrement this one metric, to give it an edge.
// Decreasing zipSize by a byte length is conservatively correct,
// especially considering that the escape byte is not likely to
// zip well with other bytes in the band.
if (regular.canRepresentSigned(X)) {
//regularChoice.histSize -= Xlen; // keep exact byteSize
//regularChoice.byteSize -= Xlen; // keep exact byteSize
}
}
int dscale = 1;
// Continually select a new choice to evaluate.
while (searchOrder < searchOrderLimit) {
if (nextChoice == null) continue;
if (nextChoice == bestChoice) {
}
}
// Record best "plain coding" choice.
assert(plainBest == bestMethod);
if (verbose > 2) {
Utils.log.info("chooser: plain result="+bestChoice+" after "+bestChoice.searchOrder+" rounds, "+(regularChoice.zipSize-bestZipSize)+" fewer bytes than regular "+regular);
}
bestChoice = null;
if (!disablePopCoding
&& effort >= POP_EFFORT
&& bestMethod instanceof Coding) {
}
if (!disableRunCoding
&& effort >= RUN_EFFORT
&& bestMethod instanceof Coding) {
}
// Pass back the requested information:
}
if (verbose > 1) {
" fewer bytes than regular "+regular+
}
return lbestMethod;
}
}
}
}
int numChoices = 0;
c.reset();
// Mark as already visited:
c.searchOrder = -1;
}
continue;
}
regularChoice = c;
numChoices++;
}
if (verbose > 1) {
}
}
if (regularChoice == null) {
if (c.searchOrder != -1) {
regularChoice = c; // arbitrary pick
break;
}
}
if (verbose > 1) {
}
}
if (verbose > 2) {
if (verbose > 4) {
if (c.searchOrder >= 0)
}
}
}
return numChoices;
}
// Find an arbitrary choice at least dlo away from a previously
// evaluated choices, and at most dhi. Try also to regulate its
// min distance to all previously evaluated choices, in this range.
if (verbose > 5)
if (c.searchOrder < searchOrder)
continue; // already searched
// Distance from "near" guy must be in bounds:
// Try also to keep min-distance from other guys in bounds:
if (verbose > 5)
return c;
}
found = c;
}
}
if (verbose > 5)
return found;
}
c.searchOrder = searchOrder++;
boolean mustComputeSize;
if (c == bestChoice || c.isExtra()) {
mustComputeSize = true;
} else if (optUseHistogram) {
} else {
mustComputeSize = true;
}
if (mustComputeSize) {
bestChoice = c;
}
if (c.histSize >= 0) {
}
if (verbose > 4) {
}
}
if (verbose > 3)
(" better by "+
if (better) {
bestMethod = c;
return true;
} else {
return false;
}
}
// update all minDistance values in still unevaluated choices
continue;
int d = distance[i];
if (verbose > 5)
if (mind > d)
if (maxd < d)
maxd = d;
}
// Now maxd has the distance of the farthest outlier
// from all evaluated choices.
if (verbose > 5)
return maxd;
}
// Compute the coded size of a sequence of values.
// The first int is the size in uncompressed bytes.
// The second is an estimate of the compressed size of these bytes.
return;
}
try {
resetData();
} catch (IOException ee) {
}
}
}
return sizes;
}
}
// This version uses the implicit local arguments
return sizes;
}
if (len < 0) {
return 0;
}
int size2;
return size;
}
}
try {
return byteOnlySizer.getSize();
} catch (IOException ee) {
}
}
}
return deltas;
}
if (verbose > 3) {
} else if (verbose > 1) {
}
}
return vHist;
}
if (verbose > 3) {
} else if (verbose > 1) {
}
}
return dHist;
}
}
// assert(plainCoding.canRepresent(min, max));
// Start with "reasonable" default codings.
final int approxL = 64;
// There's going to be a band header. Estimate conservatively large.
final int BAND_HEADER = 4;
// Keep a running model of the predicted sizes of the F/T/U sequences.
int currentFSize;
int currentTSize;
int currentUSize;
// Start by assuming a degenerate favored-value length of 0,
// which looks like a bunch of zero tokens followed by the
// original sequence.
// The {F} list ends with a repeated F value; find worst case:
// The {T} list starts out a bunch of zeros, each of length 1.
// The {U} list starts out a copy of the plainCoding:
int bestPopFVC = 0;
// Record all the values, in decreasing order of favor.
//int[] allPopSizes = new int[1+hist.getTotalLength()];
// What sizes are "interesting"?
int targetLowFVC = -1;
int targetHighFVC = -1;
// For each length, adjust the currentXSize model, and look for a win.
int mrow = -1;
int mcol = 1;
int mrowFreq = 0;
// The {F} list gets an additional member.
// Take it from the end of the current matrix row.
// (It's the end, so that we get larger favored values first.)
if (mcol == 1) {
mrow += 1;
}
currentFSize += thisVLen;
// The token list replaces occurrences of zero with a new token:
int thisVCount = mrowFreq;
- ZERO_LEN) * thisVCount;
// The unfavored list loses occurrences of the newly favored value.
// (This is the whole point of the exercise!)
//allPopSizes[fvcount] = currentSize;
if (bestPopSize > currentSize) {
if (currentSize <= targetSize) {
if (targetLowFVC < 0)
if (verbose > 4)
bestPopSize));
}
}
}
if (targetLowFVC < 0) {
if (verbose > 1) {
// Complete loss.
if (verbose > 1)
" worse by "+
bestByteSize));
}
return;
}
if (verbose > 1)
bestByteSize));
int oldZipSize = bestZipSize;
// Now close onto a specific coding, testing more rigorously
// with the zipSize metric.
// Questions to decide:
// 1. How many favored values?
// 2. What token coding (TC)?
// 3. Sort favored values by value within length brackets?
// 4. What favored coding?
// 5. What unfavored coding?
// Steps 1/2/3 are interdependent, and may be iterated.
// Steps 4 and 5 may be decided independently afterward.
final int PACK_TO_MAX_S = 1;
if (bestPopFVC <= 255) {
} else {
if (doFullAlso)
int L = LValuesCoded[i];
}
if (doFullAlso) {
if (B == c1.B()) continue;
if (B == 1) continue;
}
}
}
// interleave all B greater than bestB with best and full fits
if (c.B() > bestB) {
i.remove();
}
}
}
}
if (effort == POP_EFFORT)
maxFits = 2;
else if (maxFits > 4) {
maxFits -= 4;
) / (MAX_EFFORT-POP_EFFORT);
maxFits += 4;
}
if (verbose > 4)
}
if (verbose > 3)
boolean packToMax = false;
if (tc.S() == PACK_TO_MAX_S) {
// Kludge: setS(PACK_TO_MAX_S) means packToMax here.
packToMax = true;
}
int fVlen;
if (!packToMax) {
fVlen = bestPopFVC;
} else {
if (fVlen < targetLowFVC)
continue;
if (fVlen == bestPopFVC)
continue; // redundant test
}
int[] tcsizes =
}
if (verbose > 3) {
"/zs="+bestZipSize+
" better by "+
if (bestZipSize < oldZipSize) {
(oldZipSize - bestZipSize));
}
}
}
private
popHelper.disablePopCoding = true;
if (effort < MID_EFFORT)
// No nested run codings.
popHelper.disableRunCoding = true;
}
if (verbose > 2) {
}
// Find good coding choices for the token and unfavored sequences.
if (verbose > 2)
if (verbose > 2)
if (verbose > 2)
}
}
else {
if (verbose > 2)
}
if (verbose > 3) {
//pop.hist.print("pop-hist", null, System.out);
for (int i = 1; i <= fVlen; i++) {
if ((i % 10) == 0)
}
}
if (verbose > 2) {
}
return null; // do not bother with size computation
}
int[] sizes;
try {
resetData();
// Write the array of favored values.
} catch (IOException ee) {
}
int[] checkSizes = null;
return sizes;
}
int oldZipSize = bestZipSize;
// Scan the value sequence, determining whether an interesting
// run occupies too much space. ("Too much" means, say 5% more
// than the average integer size of the band as a whole.)
// Try to find a better coding for those segments.
if (plainCoding.isDelta()) {
lstart = 0;
}
int fillp = 0;
int totalSize = 0;
//System.out.println("len "+val+" = "+size);
}
double sizeFuzz;
double sizeFuzz2;
double sizeFuzz3;
if (effort >= MID_EFFORT) {
sizeFuzz = 1.001;
else
sizeFuzz = 1.003;
} else {
if (effort > RUN_EFFORT)
sizeFuzz = 1.01;
else
sizeFuzz = 1.03;
}
// for now:
// Find some mesh scales we like.
}
int mfillp = 0;
if (m <= 0 || m >= len) continue;
}
// There's going to be a band header. Estimate conservatively large.
// Threshold values for a "too big" mesh.
double lfuzz;
if (mesh < 10)
else if (mesh < 100)
else
}
if (verbose > 1) {
" meshes: {");
}
}
runHelper.disableRunCoding = true;
if (effort < MID_EFFORT)
// No nested pop codings.
runHelper.disablePopCoding = true;
}
for (int i = 0; i < len; i++) {
// Found a size bulge.
break;
}
}
if (verbose > 2) {
}
this.start+i,
if (midcm == plainCoding) {
// No use working further.
begcm = plainCoding;
endcm = plainCoding;
} else {
this.start,
this.start+i,
}
if (verbose > 2)
i = 0;
}
}
if (begcm != plainCoding ||
midcm != plainCoding ||
endcm != plainCoding) {
int hlen = 0;
} else {
hlen += BAND_HEADER;
}
if (i > 0) {
hlen += BAND_HEADER;
}
}
i = nexti;
break;
}
}
}
if (verbose > 3) {
if (bestZipSize < oldZipSize) {
(oldZipSize - bestZipSize));
}
}
}
static private
}
static
}
Sizer() {
this(null);
}
private int count;
count++;
}
}
public void reset() {
count = 0;
}
// If -ea, print out more informative strings!
return str;
}
}
}
private void resetData() {
flushData();
// Prepend given salt to the test output.
try {
} catch (IOException ee) {
}
}
}
private void flushData() {
try {
} catch (IOException ee) {
}
}
private int getByteSize() {
}
private int getZipSize() {
flushData();
}
/// Stress-test helpers.
void addStressSeed(int x) {
}
// Pick a random pop-coding.
// Don't turn it into a pop coding if it's already something special.
if (stress.nextBoolean()) {
// Build the population from the value list.
}
} else {
}
}
}
// Lose the order.
} else {
// Keep the order, mostly.
}
// Cut the list down.
// Cut at end.
} else {
// Cut at start.
}
}
for (int i = 0; i < fVlen; i++) {
}
if (popl < 0) continue;
break;
}
}
for (int i = 2; i <= fVlen; i++) {
}
}
return pop;
}
// Pick a random adaptive coding.
// Don't turn it into a run coding if it's already something special.
// Decide how many spans we'll create.
try {
assert(!disableRunCoding);
disableRunCoding = true; // temporary, while I decide spans
int thisspan;
} else {
for (;;) {
// Try smaller and smaller codings:
else
KX -= 1;
}
//System.out.println("KX="+KX+" KB="+KB+" K="+thisspan);
}
--thisspan;
}
// Choose a coding for the span [split..scan).
} else {
}
}
return result;
} finally {
disableRunCoding = false; // return to normal value
}
}
// Return a random value in [0..len], gently biased toward extremes.
for (int i = 0; i < 100; i++) {
if (stress.nextBoolean()) {
}
}
return BandStructure.UNSIGNED5;
}
// Return a random value in [0..len], gently biased toward extremes.
assert(len >= 0);
if (rand < 20)
else if (rand < 40)
return len;
else
}
// For debug only.
/*
public static
int[] readValuesFrom(InputStream instr) {
return readValuesFrom(new InputStreamReader(instr));
}
public static
int[] readValuesFrom(Reader inrdr) {
inrdr = new BufferedReader(inrdr);
final StreamTokenizer in = new StreamTokenizer(inrdr);
final int TT_NOTHING = -99;
in.commentChar('#');
return readValuesFrom(new Iterator() {
int token = TT_NOTHING;
private int getToken() {
if (token == TT_NOTHING) {
try {
token = in.nextToken();
assert(token != TT_NOTHING);
} catch (IOException ee) {
throw new RuntimeException(ee);
}
}
return token;
}
public boolean hasNext() {
return getToken() != StreamTokenizer.TT_EOF;
}
public Object next() {
int ntok = getToken();
token = TT_NOTHING;
switch (ntok) {
case StreamTokenizer.TT_EOF:
throw new NoSuchElementException();
case StreamTokenizer.TT_NUMBER:
return Integer.valueOf((int) in.nval);
default:
assert(false);
return null;
}
}
public void remove() {
throw new UnsupportedOperationException();
}
});
}
public static
int[] readValuesFrom(Iterator iter) {
return readValuesFrom(iter, 0);
}
public static
int[] readValuesFrom(Iterator iter, int initSize) {
int[] na = new int[Math.max(10, initSize)];
int np = 0;
while (iter.hasNext()) {
Integer val = (Integer) iter.next();
if (np == na.length) {
na = BandStructure.realloc(na);
}
na[np++] = val.intValue();
}
if (np != na.length) {
na = BandStructure.realloc(na, np);
}
return na;
}
public static
void main(String[] av) throws IOException {
int effort = MID_EFFORT;
int ap = 0;
if (ap < av.length && av[ap].equals("-e")) {
ap++;
effort = Integer.parseInt(av[ap++]);
}
int verbose = 1;
if (ap < av.length && av[ap].equals("-v")) {
ap++;
verbose = Integer.parseInt(av[ap++]);
}
Coding[] bcs = BandStructure.getBasicCodings();
CodingChooser cc = new CodingChooser(effort, bcs);
if (ap < av.length && av[ap].equals("-p")) {
ap++;
cc.optUsePopulationCoding = false;
}
if (ap < av.length && av[ap].equals("-a")) {
ap++;
cc.optUseAdaptiveCoding = false;
}
cc.verbose = verbose;
int[] values = readValuesFrom(System.in);
int[] sizes = {0,0};
CodingMethod cm = cc.choose(values, BandStructure.UNSIGNED5, sizes);
System.out.println("size: "+sizes[BYTE_SIZE]+"/zs="+sizes[ZIP_SIZE]);
System.out.println(cm);
}
//*/
}