| /* |
| * Licensed to the Apache Software Foundation (ASF) under one or more |
| * contributor license agreements. See the NOTICE file distributed with |
| * this work for additional information regarding copyright ownership. |
| * The ASF licenses this file to You under the Apache License, Version 2.0 |
| * (the "License"); you may not use this file except in compliance with |
| * the License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| package org.apache.harmony.pack200; |
| |
| import java.io.IOException; |
| import java.io.OutputStream; |
| import java.util.ArrayList; |
| import java.util.Collections; |
| import java.util.Comparator; |
| import java.util.HashMap; |
| import java.util.Iterator; |
| import java.util.List; |
| import java.util.Map; |
| |
| /** |
| * Abstract superclass for a set of bands |
| */ |
| public abstract class BandSet { |
| |
| protected final SegmentHeader segmentHeader; |
| final int effort; |
| |
| // Minimum size of band for each effort level where we consider alternative codecs |
| // Note: these values have been tuned - please test carefully if changing them |
| private static final int[] effortThresholds = new int[] {0, 0, 1000, 500, 100, 100, 100, 100, 100, 0}; |
| |
| private long[] canonicalLargest; |
| private long[] canonicalSmallest; |
| |
| /** |
| * Create a new BandSet |
| * @param effort - the packing effort to be used (must be 1-9) |
| * @param header - the segment header |
| */ |
| public BandSet(int effort, SegmentHeader header) { |
| this.effort = effort; |
| this.segmentHeader = header; |
| } |
| |
| /** |
| * Write the packed set of bands to the given output stream |
| * @param out |
| * @throws IOException |
| * @throws Pack200Exception |
| */ |
| public abstract void pack(OutputStream out) throws IOException, Pack200Exception; |
| |
| /** |
| * Encode a band without considering other Codecs |
| * @param band - the band |
| * @param codec - the Codec to use |
| * @return the encoded band |
| * @throws Pack200Exception |
| */ |
| public byte[] encodeScalar(int[] band, BHSDCodec codec) throws Pack200Exception { |
| return codec.encode(band); |
| } |
| |
| /** |
| * Encode a single value with the given Codec |
| * @param value - the value to encode |
| * @param codec - Codec to use |
| * @return the encoded value |
| * @throws Pack200Exception |
| */ |
| public byte[] encodeScalar(int value, BHSDCodec codec) throws Pack200Exception { |
| return codec.encode(value); |
| } |
| |
| /** |
| * Encode a band of integers. The default codec may be used, but other |
| * Codecs are considered if effort is greater than 1. |
| * |
| * @param name |
| * - name of the band (used for debugging) |
| * @param ints |
| * - the band |
| * @param defaultCodec |
| * - the default Codec |
| * @return the encoded band |
| * @throws Pack200Exception |
| */ |
| public byte[] encodeBandInt(String name, int[] ints, BHSDCodec defaultCodec) throws Pack200Exception { |
| byte[] encodedBand = null; |
| // Useful for debugging |
| // if(ints.length > 0) { |
| // System.out.println("encoding " + name + " " + ints.length); |
| // } |
| if(effort > 1 && (ints.length >= effortThresholds[effort])) { |
| BandAnalysisResults results = analyseBand(name, ints, defaultCodec); |
| Codec betterCodec = results.betterCodec; |
| encodedBand = results.encodedBand; |
| if(betterCodec != null) { |
| if(betterCodec instanceof BHSDCodec) { |
| int[] specifierBand = CodecEncoding.getSpecifier(betterCodec, defaultCodec); |
| int specifier = specifierBand[0]; |
| if(specifierBand.length > 1) { |
| for (int i = 1; i < specifierBand.length; i++) { |
| segmentHeader.appendBandCodingSpecifier(specifierBand[i]); |
| } |
| } |
| if(defaultCodec.isSigned()) { |
| specifier = -1 -specifier; |
| } else { |
| specifier = specifier + defaultCodec.getL(); |
| } |
| byte[] specifierEncoded = defaultCodec.encode(new int[] {specifier}); |
| byte[] band = new byte[specifierEncoded.length + encodedBand.length]; |
| System.arraycopy(specifierEncoded, 0, band, 0, specifierEncoded.length); |
| System.arraycopy(encodedBand, 0, band, specifierEncoded.length, encodedBand.length); |
| return band; |
| } else if (betterCodec instanceof PopulationCodec) { |
| int[] extraSpecifierInfo = results.extraMetadata; |
| for (int i = 0; i < extraSpecifierInfo.length; i++) { |
| segmentHeader.appendBandCodingSpecifier(extraSpecifierInfo[i]); |
| } |
| return encodedBand; |
| } else if (betterCodec instanceof RunCodec) { |
| |
| } |
| } |
| } |
| |
| // If we get here then we've decided to use the default codec. |
| if(ints.length > 0) { |
| if(encodedBand == null) { |
| encodedBand = defaultCodec.encode(ints); |
| } |
| int first = ints[0]; |
| if(defaultCodec.getB() != 1) { |
| if (defaultCodec.isSigned() && first >= -256 && first <= -1) { |
| int specifier = -1 - CodecEncoding.getSpecifierForDefaultCodec(defaultCodec); |
| byte[] specifierEncoded = defaultCodec.encode(new int[] {specifier}); |
| byte[] band = new byte[specifierEncoded.length + encodedBand.length]; |
| System.arraycopy(specifierEncoded, 0, band, 0, specifierEncoded.length); |
| System.arraycopy(encodedBand, 0, band, specifierEncoded.length, encodedBand.length); |
| return band; |
| } else if (!defaultCodec.isSigned() && first >= defaultCodec.getL() |
| && first <= defaultCodec.getL() + 255) { |
| int specifier = CodecEncoding.getSpecifierForDefaultCodec(defaultCodec) + defaultCodec.getL(); |
| byte[] specifierEncoded = defaultCodec.encode(new int[] {specifier}); |
| byte[] band = new byte[specifierEncoded.length + encodedBand.length]; |
| System.arraycopy(specifierEncoded, 0, band, 0, specifierEncoded.length); |
| System.arraycopy(encodedBand, 0, band, specifierEncoded.length, encodedBand.length); |
| return band; |
| } |
| } |
| return encodedBand; |
| } |
| return new byte[0]; |
| } |
| |
| private BandAnalysisResults analyseBand(String name, int[] band, |
| BHSDCodec defaultCodec) throws Pack200Exception { |
| |
| BandAnalysisResults results = new BandAnalysisResults(); |
| |
| if(canonicalLargest == null) { |
| canonicalLargest = new long[116]; |
| canonicalSmallest = new long[116]; |
| for (int i = 1; i < canonicalLargest.length; i++) { |
| canonicalLargest[i] = CodecEncoding.getCanonicalCodec(i).largest(); |
| canonicalSmallest[i] = CodecEncoding.getCanonicalCodec(i).smallest(); |
| } |
| } |
| BandData bandData = new BandData(band); |
| |
| // Check that there is a reasonable saving to be made |
| byte[] encoded = defaultCodec.encode(band); |
| results.encodedBand = encoded; |
| |
| // Note: these values have been tuned - please test carefully if changing them |
| if(encoded.length <= band.length + 23 - 2*effort) { // TODO: tweak |
| return results; |
| } |
| |
| // Check if we can use BYTE1 as that's a 1:1 mapping if we can |
| if(!bandData.anyNegatives() && bandData.largest <= Codec.BYTE1.largest()) { |
| results.encodedBand = Codec.BYTE1.encode(band) ; |
| results.betterCodec = Codec.BYTE1; |
| return results; |
| } |
| |
| // Consider a population codec (but can't be nested) |
| if(effort > 3 && !name.equals("POPULATION")) { |
| int numDistinctValues = bandData.numDistinctValues(); |
| float distinctValuesAsProportion = (float)numDistinctValues / (float)band.length; |
| |
| // Note: these values have been tuned - please test carefully if changing them |
| if(numDistinctValues < 100 || distinctValuesAsProportion < 0.02 || (effort > 6 && distinctValuesAsProportion < 0.04)) { // TODO: tweak |
| encodeWithPopulationCodec(name, band, defaultCodec, bandData, results); |
| if(timeToStop(results)) { |
| return results; |
| } |
| } |
| } |
| |
| List codecFamiliesToTry = new ArrayList(); |
| |
| // See if the deltas are mainly small increments |
| if(bandData.mainlyPositiveDeltas() && bandData.mainlySmallDeltas()) { |
| codecFamiliesToTry.add(CanonicalCodecFamilies.deltaUnsignedCodecs2); |
| } |
| |
| if (bandData.wellCorrelated()) { // Try delta encodings |
| if (bandData.mainlyPositiveDeltas()) { |
| codecFamiliesToTry.add(CanonicalCodecFamilies.deltaUnsignedCodecs1); |
| codecFamiliesToTry.add(CanonicalCodecFamilies.deltaUnsignedCodecs3); |
| codecFamiliesToTry.add(CanonicalCodecFamilies.deltaUnsignedCodecs4); |
| codecFamiliesToTry.add(CanonicalCodecFamilies.deltaUnsignedCodecs5); |
| codecFamiliesToTry.add(CanonicalCodecFamilies.nonDeltaUnsignedCodecs1); |
| codecFamiliesToTry.add(CanonicalCodecFamilies.nonDeltaUnsignedCodecs3); |
| codecFamiliesToTry.add(CanonicalCodecFamilies.nonDeltaUnsignedCodecs4); |
| codecFamiliesToTry.add(CanonicalCodecFamilies.nonDeltaUnsignedCodecs5); |
| codecFamiliesToTry.add(CanonicalCodecFamilies.nonDeltaUnsignedCodecs2); |
| } else { |
| codecFamiliesToTry.add(CanonicalCodecFamilies.deltaSignedCodecs1); |
| codecFamiliesToTry.add(CanonicalCodecFamilies.deltaSignedCodecs3); |
| codecFamiliesToTry.add(CanonicalCodecFamilies.deltaSignedCodecs2); |
| codecFamiliesToTry.add(CanonicalCodecFamilies.deltaSignedCodecs4); |
| codecFamiliesToTry.add(CanonicalCodecFamilies.deltaSignedCodecs5); |
| codecFamiliesToTry.add(CanonicalCodecFamilies.nonDeltaSignedCodecs1); |
| codecFamiliesToTry.add(CanonicalCodecFamilies.nonDeltaSignedCodecs2); |
| } |
| } else { |
| if (bandData.anyNegatives()) { |
| codecFamiliesToTry.add(CanonicalCodecFamilies.nonDeltaSignedCodecs1); |
| codecFamiliesToTry.add(CanonicalCodecFamilies.nonDeltaSignedCodecs2); |
| codecFamiliesToTry.add(CanonicalCodecFamilies.deltaSignedCodecs1); |
| codecFamiliesToTry.add(CanonicalCodecFamilies.deltaSignedCodecs2); |
| codecFamiliesToTry.add(CanonicalCodecFamilies.deltaSignedCodecs3); |
| codecFamiliesToTry.add(CanonicalCodecFamilies.deltaSignedCodecs4); |
| codecFamiliesToTry.add(CanonicalCodecFamilies.deltaSignedCodecs5); |
| } else { |
| codecFamiliesToTry.add(CanonicalCodecFamilies.nonDeltaUnsignedCodecs1); |
| codecFamiliesToTry.add(CanonicalCodecFamilies.nonDeltaUnsignedCodecs3); |
| codecFamiliesToTry.add(CanonicalCodecFamilies.nonDeltaUnsignedCodecs4); |
| codecFamiliesToTry.add(CanonicalCodecFamilies.nonDeltaUnsignedCodecs5); |
| codecFamiliesToTry.add(CanonicalCodecFamilies.nonDeltaUnsignedCodecs2); |
| codecFamiliesToTry.add(CanonicalCodecFamilies.deltaUnsignedCodecs1); |
| codecFamiliesToTry.add(CanonicalCodecFamilies.deltaUnsignedCodecs3); |
| codecFamiliesToTry.add(CanonicalCodecFamilies.deltaUnsignedCodecs4); |
| codecFamiliesToTry.add(CanonicalCodecFamilies.deltaUnsignedCodecs5); |
| } |
| } |
| if(name.equalsIgnoreCase("cpint")) { |
| System.out.print(""); |
| } |
| |
| for (Iterator iterator = codecFamiliesToTry.iterator(); iterator |
| .hasNext();) { |
| BHSDCodec[] family = (BHSDCodec[]) iterator.next(); |
| tryCodecs(name, band, defaultCodec, bandData, results, encoded, |
| family); |
| if (timeToStop(results)) { |
| break; |
| } |
| } |
| |
| return results; |
| } |
| |
| private boolean timeToStop(BandAnalysisResults results) { |
| // if tried more than effort number of codecs for this band then return |
| // Note: these values have been tuned - please test carefully if changing them |
| if(effort > 6) { |
| return results.numCodecsTried >= effort * 2; |
| } |
| return results.numCodecsTried >= effort; |
| // May want to also check how much we've saved if performance needs improving, e.g. saved more than effort*2 % |
| // || (float)results.saved/(float)results.encodedBand.length > (float)effort * 2/100; |
| } |
| |
| private void tryCodecs(String name, int[] band, BHSDCodec defaultCodec, BandData bandData, |
| BandAnalysisResults results, byte[] encoded, |
| BHSDCodec[] potentialCodecs) throws Pack200Exception { |
| for (int i = 0; i < potentialCodecs.length; i++) { |
| BHSDCodec potential = potentialCodecs[i]; |
| if(potential.equals(defaultCodec)) { |
| return; // don't try codecs with greater cardinality in the same 'family' as the default codec as there won't be any savings |
| } |
| if (potential.isDelta()) { |
| if (potential.largest() >= bandData.largestDelta |
| && potential.smallest() <= bandData.smallestDelta |
| && potential.largest() >= bandData.largest |
| && potential.smallest() <= bandData.smallest) { |
| // TODO: can represent some negative deltas with overflow |
| byte[] encoded2 = potential.encode(band); |
| results.numCodecsTried++; |
| byte[] specifierEncoded = defaultCodec.encode(CodecEncoding |
| .getSpecifier(potential, null)); |
| int saved = encoded.length - encoded2.length |
| - specifierEncoded.length; |
| if (saved > results.saved) { |
| results.betterCodec = potential; |
| results.encodedBand = encoded2; |
| results.saved = saved; |
| } |
| } |
| } else if (potential.largest() >= bandData.largest |
| && potential.smallest() <= bandData.smallest) { |
| byte[] encoded2 = potential.encode(band); |
| results.numCodecsTried++; |
| byte[] specifierEncoded = defaultCodec.encode(CodecEncoding |
| .getSpecifier(potential, null)); |
| int saved = encoded.length - encoded2.length |
| - specifierEncoded.length; |
| if (saved > results.saved) { |
| results.betterCodec = potential; |
| results.encodedBand = encoded2; |
| results.saved = saved; |
| } |
| } |
| if(timeToStop(results)) { |
| return; |
| } |
| } |
| } |
| |
| // This could be useful if further enhancements are done but is not currently used |
| // |
| // private void encodeWithRunCodec(String name, int[] band, int index, |
| // BHSDCodec defaultCodec, BandData bandData, |
| // BandAnalysisResults results) throws Pack200Exception { |
| // int[] firstBand = new int[index]; |
| // int[] secondBand = new int[band.length - index]; |
| // System.arraycopy(band, 0, firstBand, 0, index); |
| // System.arraycopy(band, index, secondBand, 0, secondBand.length); |
| // BandAnalysisResults firstResults = analyseBand(name + "A", firstBand, defaultCodec); |
| // BandAnalysisResults secondResults = analyseBand(name + "B", secondBand, defaultCodec); |
| // int specifier = 117; |
| // byte[] specifierEncoded = defaultCodec.encode(new int[] {specifier}); |
| // int totalLength = firstResults.encodedBand.length + secondResults.encodedBand.length + specifierEncoded.length + 4; // TODO actual |
| // if(totalLength < results.encodedBand.length) { |
| // System.out.println("using run codec"); |
| // results.saved += results.encodedBand.length - totalLength; |
| // byte[] encodedBand = new byte[specifierEncoded.length + firstResults.encodedBand.length + secondResults.encodedBand.length]; |
| // System.arraycopy(specifierEncoded, 0, encodedBand, 0, specifierEncoded.length); |
| // System.arraycopy(firstResults.encodedBand, 0, encodedBand, specifierEncoded.length, firstResults.encodedBand.length); |
| // System.arraycopy(secondResults.encodedBand, 0, encodedBand, specifierEncoded.length + firstResults.encodedBand.length, secondResults.encodedBand.length); |
| // results.encodedBand = encodedBand; |
| // results.betterCodec = new RunCodec(index, firstResults.betterCodec, secondResults.betterCodec); |
| // } |
| // } |
| |
| private void encodeWithPopulationCodec(String name, int[] band, |
| BHSDCodec defaultCodec, BandData bandData, BandAnalysisResults results) throws Pack200Exception { |
| results.numCodecsTried += 3; // quite a bit more effort to try this codec |
| final Map distinctValues = bandData.distinctValues; |
| |
| List favoured = new ArrayList(); |
| for (Iterator iterator = distinctValues.keySet().iterator(); iterator |
| .hasNext();) { |
| Integer value = (Integer) iterator.next(); |
| Integer count = (Integer) distinctValues.get(value); |
| if(count.intValue() > 2 || distinctValues.size() < 256) { // TODO: tweak |
| favoured.add(value); |
| } |
| } |
| |
| // Sort the favoured list with the most commonly occurring first |
| if(distinctValues.size() > 255) { |
| Collections.sort(favoured, new Comparator() { |
| public int compare(Object arg0, Object arg1) { |
| return ((Integer)distinctValues.get(arg1)).compareTo((Integer)distinctValues.get(arg0)); |
| } |
| }); |
| } |
| |
| IntList unfavoured = new IntList(); |
| Map favouredToIndex = new HashMap(); |
| for (int i = 0; i < favoured.size(); i++) { |
| Integer value = (Integer) favoured.get(i); |
| favouredToIndex.put(value, new Integer(i)); |
| } |
| |
| int[] tokens = new int[band.length]; |
| for (int i = 0; i < band.length; i++) { |
| Integer favouredIndex = (Integer)favouredToIndex.get(new Integer(band[i])); |
| if(favouredIndex == null) { |
| tokens[i] = 0; |
| unfavoured.add(band[i]); |
| } else { |
| tokens[i] = favouredIndex.intValue() + 1; |
| } |
| } |
| favoured.add(favoured.get(favoured.size() - 1)); // repeat last value |
| int[] favouredBand = integerListToArray(favoured); |
| int[] unfavouredBand = unfavoured.toArray(); |
| |
| // Analyse the three bands to get the best codec |
| BandAnalysisResults favouredResults = analyseBand("POPULATION", favouredBand, defaultCodec); |
| BandAnalysisResults unfavouredResults = analyseBand("POPULATION", unfavouredBand, defaultCodec); |
| |
| int tdefL = 0; |
| int l = 0; |
| Codec tokenCodec = null; |
| byte[] tokensEncoded; |
| int k = favoured.size() - 1; |
| if(k < 256) { |
| tdefL = 1; |
| tokensEncoded = Codec.BYTE1.encode(tokens); |
| } else { |
| BandAnalysisResults tokenResults = analyseBand("POPULATION", tokens, defaultCodec); |
| tokenCodec = tokenResults.betterCodec; |
| tokensEncoded = tokenResults.encodedBand; |
| if(tokenCodec == null) { |
| tokenCodec = defaultCodec; |
| } |
| l = ((BHSDCodec) tokenCodec).getL(); |
| int h = ((BHSDCodec) tokenCodec).getH(); |
| int s = ((BHSDCodec) tokenCodec).getS(); |
| int b = ((BHSDCodec) tokenCodec).getB(); |
| int d = ((BHSDCodec) tokenCodec).isDelta() ? 1 : 0; |
| if(s == 0 && d == 0) { |
| boolean canUseTDefL = true; |
| if(b > 1) { |
| BHSDCodec oneLowerB = new BHSDCodec(b-1, h); |
| if(oneLowerB.largest() >= k) { |
| canUseTDefL = false; |
| } |
| } |
| if(canUseTDefL) { |
| switch (l) { |
| case 4: |
| tdefL = 1; |
| break; |
| case 8: |
| tdefL = 2; |
| break; |
| case 16: |
| tdefL = 3; |
| break; |
| case 32: |
| tdefL = 4; |
| break; |
| case 64: |
| tdefL = 5; |
| break; |
| case 128: |
| tdefL = 6; |
| break; |
| case 192: |
| tdefL = 7; |
| break; |
| case 224: |
| tdefL = 8; |
| break; |
| case 240: |
| tdefL = 9; |
| break; |
| case 248: |
| tdefL = 10; |
| break; |
| case 252: |
| tdefL = 11; |
| break; |
| } |
| } |
| } |
| } |
| |
| byte[] favouredEncoded = favouredResults.encodedBand; |
| byte[] unfavouredEncoded = unfavouredResults.encodedBand; |
| Codec favouredCodec = favouredResults.betterCodec; |
| Codec unfavouredCodec = unfavouredResults.betterCodec; |
| |
| int specifier = 141 + (favouredCodec == null ? 1 : 0) + (4 * tdefL) + (unfavouredCodec == null ? 2 : 0); |
| IntList extraBandMetadata = new IntList(3); |
| if(favouredCodec != null) { |
| int[] specifiers = CodecEncoding.getSpecifier(favouredCodec, null); |
| for (int i = 0; i < specifiers.length; i++) { |
| extraBandMetadata.add(specifiers[i]); |
| } |
| } |
| if(tdefL == 0) { |
| int[] specifiers = CodecEncoding.getSpecifier(tokenCodec, null); |
| for (int i = 0; i < specifiers.length; i++) { |
| extraBandMetadata.add(specifiers[i]); |
| } |
| } |
| if(unfavouredCodec != null) { |
| int[] specifiers = CodecEncoding.getSpecifier(unfavouredCodec, null); |
| for (int i = 0; i < specifiers.length; i++) { |
| extraBandMetadata.add(specifiers[i]); |
| } |
| } |
| int[] extraMetadata = extraBandMetadata.toArray(); |
| byte[] extraMetadataEncoded = Codec.UNSIGNED5.encode(extraMetadata); |
| if(defaultCodec.isSigned()) { |
| specifier = -1 -specifier; |
| } else { |
| specifier = specifier + defaultCodec.getL(); |
| } |
| byte[] firstValueEncoded = defaultCodec.encode(new int[] {specifier}); |
| int totalBandLength = firstValueEncoded.length + favouredEncoded.length + tokensEncoded.length + unfavouredEncoded.length; |
| |
| if(totalBandLength + extraMetadataEncoded.length < results.encodedBand.length) { |
| results.saved += results.encodedBand.length - (totalBandLength + extraMetadataEncoded.length); |
| byte[] encodedBand = new byte[totalBandLength]; |
| System.arraycopy(firstValueEncoded, 0, encodedBand, 0, firstValueEncoded.length); |
| System.arraycopy(favouredEncoded, 0, encodedBand, firstValueEncoded.length, favouredEncoded.length); |
| System.arraycopy(tokensEncoded, 0, encodedBand, firstValueEncoded.length + favouredEncoded.length, tokensEncoded.length); |
| System.arraycopy(unfavouredEncoded, 0, encodedBand, firstValueEncoded.length + favouredEncoded.length + tokensEncoded.length, unfavouredEncoded.length); |
| results.encodedBand = encodedBand; |
| results.extraMetadata = extraMetadata; |
| if(l != 0) { |
| results.betterCodec = new PopulationCodec(favouredCodec, l, unfavouredCodec); |
| } else { |
| results.betterCodec = new PopulationCodec(favouredCodec, tokenCodec, unfavouredCodec); |
| } |
| } |
| } |
| |
| /** |
| * Encode a band of longs (values are split into their high and low 32 bits |
| * and then encoded as two separate bands |
| * |
| * @param name |
| * - name of the band (for debugging purposes) |
| * @param flags |
| * - the band |
| * @param loCodec |
| * - Codec for the low 32-bits band |
| * @param hiCodec |
| * - Codec for the high 32-bits band |
| * @param haveHiFlags |
| * - ignores the high band if true as all values would be zero |
| * @return the encoded band |
| * @throws Pack200Exception |
| */ |
| protected byte[] encodeFlags(String name, long[] flags, BHSDCodec loCodec, BHSDCodec hiCodec, |
| boolean haveHiFlags) throws Pack200Exception { |
| if(!haveHiFlags) { |
| int[] loBits = new int[flags.length]; |
| for (int i = 0; i < flags.length; i++) { |
| loBits[i] = (int) flags[i]; |
| } |
| return encodeBandInt(name, loBits, loCodec); |
| } else { |
| |
| int[] hiBits = new int[flags.length]; |
| int[] loBits = new int[flags.length]; |
| for (int i = 0; i < flags.length; i++) { |
| long l = flags[i]; |
| hiBits[i] = (int) (l >> 32); |
| loBits[i] = (int) l; |
| } |
| byte[] hi = encodeBandInt(name, hiBits, hiCodec); |
| byte[] lo = encodeBandInt(name, loBits, loCodec); |
| byte[] total = new byte[hi.length + lo.length]; |
| System.arraycopy(hi, 0, total, 0, hi.length); |
| System.arraycopy(lo, 0, total, hi.length + 1, lo.length); |
| return total; |
| } |
| } |
| |
| /** |
| * Converts a list of Integers to an int[] array |
| */ |
| protected int[] integerListToArray(List integerList) { |
| int[] array = new int[integerList.size()]; |
| for (int i = 0; i < array.length; i++) { |
| array[i] = ((Integer)integerList.get(i)).intValue(); |
| } |
| return array; |
| } |
| |
| /** |
| * Converts a list of Longs to an long[] array |
| */ |
| protected long[] longListToArray(List longList) { |
| long[] array = new long[longList.size()]; |
| for (int i = 0; i < array.length; i++) { |
| array[i] = ((Long)longList.get(i)).longValue(); |
| } |
| return array; |
| } |
| |
| /** |
| * Converts a list of ConstantPoolEntrys to an int[] array of their indices |
| */ |
| protected int[] cpEntryListToArray(List list) { |
| int[] array = new int[list.size()]; |
| for (int i = 0; i < array.length; i++) { |
| array[i] = ((ConstantPoolEntry)list.get(i)).getIndex(); |
| if(array[i] < 0) { |
| throw new RuntimeException("Index should be > 0"); |
| } |
| } |
| return array; |
| } |
| |
| /** |
| * Converts a list of ConstantPoolEntrys or nulls to an int[] array of their |
| * indices +1 (or 0 for nulls) |
| */ |
| protected int[] cpEntryOrNullListToArray(List theList) { |
| int[] array = new int[theList.size()]; |
| for (int j = 0; j < array.length; j++) { |
| ConstantPoolEntry cpEntry = (ConstantPoolEntry) theList.get(j); |
| array[j] = cpEntry == null ? 0 : cpEntry.getIndex() + 1; |
| if(cpEntry != null && cpEntry.getIndex() < 0) { |
| throw new RuntimeException("Index should be > 0"); |
| } |
| } |
| return array; |
| } |
| |
| protected byte[] encodeFlags(String name, long[][] flags, BHSDCodec loCodec, BHSDCodec hiCodec, |
| boolean haveHiFlags) throws Pack200Exception { |
| return encodeFlags(name, flatten(flags), loCodec, hiCodec, haveHiFlags); |
| } |
| |
| /* |
| * Flatten a 2-dimension array into a 1-dimension array |
| */ |
| private long[] flatten(long[][] flags) { |
| int totalSize = 0; |
| for (int i = 0; i < flags.length; i++) { |
| totalSize += flags[i].length; |
| } |
| long[] flatArray = new long[totalSize]; |
| int index = 0; |
| for (int i = 0; i < flags.length; i++) { |
| for (int j = 0; j < flags[i].length; j++) { |
| flatArray[index] = flags[i][j]; |
| index++; |
| } |
| } |
| return flatArray; |
| } |
| |
| /** |
| * BandData represents information about a band, e.g. largest value etc |
| * and is used in the heuristics that calculate whether an alternative |
| * Codec could make the encoded band smaller. |
| */ |
| public class BandData { |
| |
| private final int[] band; |
| private int smallest = Integer.MAX_VALUE; |
| private int largest = Integer.MIN_VALUE; |
| private int smallestDelta; |
| private int largestDelta; |
| |
| private int deltaIsAscending = 0; |
| private int smallDeltaCount = 0; |
| |
| private double averageAbsoluteDelta = 0; |
| private double averageAbsoluteValue = 0; |
| |
| private Map distinctValues; |
| |
| /** |
| * Create a new instance of BandData. The band is then analysed. |
| * @param band - the band of integers |
| */ |
| public BandData(int[] band) { |
| this.band = band; |
| Integer one = new Integer(1); |
| for (int i = 0; i < band.length; i++) { |
| if(band[i] < smallest) { |
| smallest = band[i]; |
| } |
| if(band[i] > largest) { |
| largest = band[i]; |
| } |
| if(i != 0) { |
| int delta = band[i] - band[i - 1]; |
| if(delta < smallestDelta) { |
| smallestDelta = delta; |
| } |
| if(delta > largestDelta) { |
| largestDelta = delta; |
| } |
| if(delta >= 0) { |
| deltaIsAscending++; |
| } |
| averageAbsoluteDelta += (double)Math.abs(delta)/(double)(band.length - 1); |
| if(Math.abs(delta) < 256) { |
| smallDeltaCount++; |
| } |
| } else { |
| smallestDelta = band[0]; |
| largestDelta = band[0]; |
| } |
| averageAbsoluteValue += (double)Math.abs(band[i])/(double)band.length; |
| if(effort > 3) { // do calculations needed to consider population codec |
| if(distinctValues == null) { |
| distinctValues = new HashMap(); |
| } |
| Integer value = new Integer(band[i]); |
| Integer count = (Integer) distinctValues.get(value); |
| if(count == null) { |
| count = one; |
| } else { |
| count = new Integer(count.intValue() + 1); |
| } |
| distinctValues.put(value, count); |
| } |
| } |
| } |
| |
| /** |
| * Returns true if the deltas between adjacent band elements are mainly |
| * small (heuristic) |
| */ |
| public boolean mainlySmallDeltas() { |
| // Note: the value below has been tuned - please test carefully if changing it |
| return (float)smallDeltaCount/(float)band.length > 0.7F; |
| } |
| |
| /** |
| * Returns true if the band is well correlated (i.e. would be suitable |
| * for a delta encoding) (heuristic) |
| */ |
| public boolean wellCorrelated() { |
| // Note: the value below has been tuned - please test carefully if changing it |
| return averageAbsoluteDelta * 3.1 < averageAbsoluteValue; |
| } |
| |
| /** |
| * Returns true if the band deltas are mainly positive (heuristic) |
| */ |
| public boolean mainlyPositiveDeltas() { |
| // Note: the value below has been tuned - please test carefully if changing it |
| return (float)deltaIsAscending/(float)band.length > 0.95F; |
| } |
| |
| /** |
| * Returns true if any band elements are negative |
| */ |
| public boolean anyNegatives() { |
| return smallest < 0; |
| } |
| |
| /** |
| * Returns the total number of distinct values found in the band |
| */ |
| public int numDistinctValues() { |
| if(distinctValues == null) { |
| return band.length; |
| } |
| return distinctValues.size(); |
| } |
| |
| } |
| |
| /** |
| * Results obtained by trying different Codecs to encode a band |
| */ |
| public class BandAnalysisResults { |
| |
| // The number of Codecs tried so far |
| private int numCodecsTried = 0; |
| |
| // The number of bytes saved by using betterCodec instead of the default codec |
| private int saved = 0; |
| |
| // Extra metadata to pass to the segment header (to be appended to the |
| // band_headers band) |
| private int[] extraMetadata; |
| |
| // The results of encoding the band with betterCodec |
| private byte[] encodedBand; |
| |
| // The best Codec found so far, or should be null if the default is the |
| // best so far |
| private Codec betterCodec; |
| |
| } |
| |
| } |
