    001/*
    002 *  Licensed to the Apache Software Foundation (ASF) under one or more
    003 *  contributor license agreements.  See the NOTICE file distributed with
    004 *  this work for additional information regarding copyright ownership.
    005 *  The ASF licenses this file to You under the Apache License, Version 2.0
    006 *  (the "License"); you may not use this file except in compliance with
    007 *  the License.  You may obtain a copy of the License at
    008 *
    009 *     http://www.apache.org/licenses/LICENSE-2.0
    010 *
    011 *  Unless required by applicable law or agreed to in writing, software
    012 *  distributed under the License is distributed on an "AS IS" BASIS,
    013 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    014 *  See the License for the specific language governing permissions and
    015 *  limitations under the License.
    016 */
    017package org.apache.commons.compress.harmony.pack200;
    018
    019import java.io.IOException;
    020import java.io.OutputStream;
    021import java.util.ArrayList;
    022import java.util.Arrays;
    023import java.util.HashMap;
    024import java.util.List;
    025import java.util.Map;
    026import java.util.stream.IntStream;
    027
    028/**
    029 * Abstract superclass for a set of bands
    030 */
    031public abstract class BandSet {
    032
    033    private static final byte[] EMPTY_BYTE_ARRAY = new byte[0];
    034
    035    /**
    036     * Results obtained by trying different Codecs to encode a band
    037     */
    038    public class BandAnalysisResults {
    039
    040        // The number of Codecs tried so far
    041        private int numCodecsTried;
    042
    043        // The number of bytes saved by using betterCodec instead of the default codec
    044        private int saved;
    045
    046        // Extra metadata to pass to the segment header (to be appended to the
    047        // band_headers band)
    048        private int[] extraMetadata;
    049
    050        // The results of encoding the band with betterCodec
    051        private byte[] encodedBand;
    052
    053        // The best Codec found so far, or should be null if the default is the
    054        // best so far
    055        private Codec betterCodec;
    056
    057    }
    058
    059    /**
    060     * 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
    061     * the encoded band smaller.
    062     */
    063    public class BandData {
    064
    065        private final int[] band;
    066        private int smallest = Integer.MAX_VALUE;
    067        private int largest = Integer.MIN_VALUE;
    068        private int smallestDelta;
    069        private int largestDelta;
    070
    071        private int deltaIsAscending;
    072        private int smallDeltaCount;
    073
    074        private double averageAbsoluteDelta;
    075        private double averageAbsoluteValue;
    076
    077        private Map<Integer, Integer> distinctValues;
    078
    079        /**
    080         * Constructs a new instance of BandData. The band is then analysed.
    081         *
    082         * @param band - the band of integers
    083         */
    084        public BandData(final int[] band) {
    085            this.band = band;
    086            final Integer one = Integer.valueOf(1);
    087            for (int i = 0; i < band.length; i++) {
    088                if (band[i] < smallest) {
    089                    smallest = band[i];
    090                }
    091                if (band[i] > largest) {
    092                    largest = band[i];
    093                }
    094                if (i != 0) {
    095                    final int delta = band[i] - band[i - 1];
    096                    if (delta < smallestDelta) {
    097                        smallestDelta = delta;
    098                    }
    099                    if (delta > largestDelta) {
    100                        largestDelta = delta;
    101                    }
    102                    if (delta >= 0) {
    103                        deltaIsAscending++;
    104                    }
    105                    averageAbsoluteDelta += (double) Math.abs(delta) / (double) (band.length - 1);
    106                    if (Math.abs(delta) < 256) {
    107                        smallDeltaCount++;
    108                    }
    109                } else {
    110                    smallestDelta = band[0];
    111                    largestDelta = band[0];
    112                }
    113                averageAbsoluteValue += (double) Math.abs(band[i]) / (double) band.length;
    114                if (effort > 3) { // do calculations needed to consider population codec
    115                    if (distinctValues == null) {
    116                        distinctValues = new HashMap<>();
    117                    }
    118                    final Integer value = Integer.valueOf(band[i]);
    119                    Integer count = distinctValues.get(value);
    120                    if (count == null) {
    121                        count = one;
    122                    } else {
    123                        count = Integer.valueOf(count.intValue() + 1);
    124                    }
    125                    distinctValues.put(value, count);
    126                }
    127            }
    128        }
    129
    130        /**
    131         * Returns true if any band elements are negative.
    132         *
    133         * @return true if any band elements are negative.
    134         */
    135        public boolean anyNegatives() {
    136            return smallest < 0;
    137        }
    138
    139        /**
    140         * Returns true if the band deltas are mainly positive (heuristic).
    141         *
    142         * @return true if the band deltas are mainly positive (heuristic).
    143         */
    144        public boolean mainlyPositiveDeltas() {
    145            // Note: the value below has been tuned - please test carefully if changing it
    146            return (float) deltaIsAscending / (float) band.length > 0.95F;
    147        }
    148
    149        /**
    150         * Returns true if the deltas between adjacent band elements are mainly small (heuristic).
    151         *
    152         * @return true if the deltas between adjacent band elements are mainly small (heuristic).
    153         */
    154        public boolean mainlySmallDeltas() {
    155            // Note: the value below has been tuned - please test carefully if changing it
    156            return (float) smallDeltaCount / (float) band.length > 0.7F;
    157        }
    158
    159        /**
    160         * Returns the total number of distinct values found in the band.
    161         *
    162         * @return the total number of distinct values found in the band.
    163         */
    164        public int numDistinctValues() {
    165            if (distinctValues == null) {
    166                return band.length;
    167            }
    168            return distinctValues.size();
    169        }
    170
    171        /**
    172         * Returns true if the band is well correlated (i.e. would be suitable for a delta encoding) (heuristic).
    173         *
    174         * @return true if the band is well correlated (i.e. would be suitable for a delta encoding) (heuristic).
    175         */
    176        public boolean wellCorrelated() {
    177            // Note: the value below has been tuned - please test carefully if changing it
    178            return averageAbsoluteDelta * 3.1 < averageAbsoluteValue;
    179        }
    180
    181    }
    182
    183    // Minimum size of band for each effort level where we consider alternative codecs
    184    // Note: these values have been tuned - please test carefully if changing them
    185    private static final int[] effortThresholds = { 0, 0, 1000, 500, 100, 100, 100, 100, 100, 0 };
    186
    187    protected final SegmentHeader segmentHeader;
    188    final int effort;
    189
    190    private long[] canonicalLargest;
    191
    192    private long[] canonicalSmallest;
    193
    194    /**
    195     * Constructs a new BandSet.
    196     *
    197     * @param effort - the packing effort to be used (must be 1-9)
    198     * @param header - the segment header
    199     */
    200    public BandSet(final int effort, final SegmentHeader header) {
    201        this.effort = effort;
    202        this.segmentHeader = header;
    203    }
    204
    205    private BandAnalysisResults analyseBand(final String name, final int[] band, final BHSDCodec defaultCodec) throws Pack200Exception {
    206
    207        final BandAnalysisResults results = new BandAnalysisResults();
    208
    209        if (canonicalLargest == null) {
    210            canonicalLargest = new long[116];
    211            canonicalSmallest = new long[116];
    212            for (int i = 1; i < canonicalLargest.length; i++) {
    213                canonicalLargest[i] = CodecEncoding.getCanonicalCodec(i).largest();
    214                canonicalSmallest[i] = CodecEncoding.getCanonicalCodec(i).smallest();
    215            }
    216        }
    217        final BandData bandData = new BandData(band);
    218
    219        // Check that there is a reasonable saving to be made
    220        final byte[] encoded = defaultCodec.encode(band);
    221        results.encodedBand = encoded;
    222
    223        // Note: these values have been tuned - please test carefully if changing them
    224        if (encoded.length <= band.length + 23 - 2 * effort) { // TODO: tweak
    225            return results;
    226        }
    227
    228        // Check if we can use BYTE1 as that's a 1:1 mapping if we can
    229        if (!bandData.anyNegatives() && bandData.largest <= Codec.BYTE1.largest()) {
    230            results.encodedBand = Codec.BYTE1.encode(band);
    231            results.betterCodec = Codec.BYTE1;
    232            return results;
    233        }
    234
    235        // Consider a population codec (but can't be nested)
    236        if (effort > 3 && !name.equals("POPULATION")) {
    237            final int numDistinctValues = bandData.numDistinctValues();
    238            final float distinctValuesAsProportion = (float) numDistinctValues / (float) band.length;
    239
    240            // Note: these values have been tuned - please test carefully if changing them
    241            if (numDistinctValues < 100 || distinctValuesAsProportion < 0.02 || effort > 6 && distinctValuesAsProportion < 0.04) { // TODO: tweak
    242                encodeWithPopulationCodec(name, band, defaultCodec, bandData, results);
    243                if (timeToStop(results)) {
    244                    return results;
    245                }
    246            }
    247        }
    248
    249        final List<BHSDCodec[]> codecFamiliesToTry = new ArrayList<>();
    250
    251        // See if the deltas are mainly small increments
    252        if (bandData.mainlyPositiveDeltas() && bandData.mainlySmallDeltas()) {
    253            codecFamiliesToTry.add(CanonicalCodecFamilies.deltaUnsignedCodecs2);
    254        }
    255
    256        if (bandData.wellCorrelated()) { // Try delta encodings
    257            if (bandData.mainlyPositiveDeltas()) {
    258                codecFamiliesToTry.add(CanonicalCodecFamilies.deltaUnsignedCodecs1);
    259                codecFamiliesToTry.add(CanonicalCodecFamilies.deltaUnsignedCodecs3);
    260                codecFamiliesToTry.add(CanonicalCodecFamilies.deltaUnsignedCodecs4);
    261                codecFamiliesToTry.add(CanonicalCodecFamilies.deltaUnsignedCodecs5);
    262                codecFamiliesToTry.add(CanonicalCodecFamilies.nonDeltaUnsignedCodecs1);
    263                codecFamiliesToTry.add(CanonicalCodecFamilies.nonDeltaUnsignedCodecs3);
    264                codecFamiliesToTry.add(CanonicalCodecFamilies.nonDeltaUnsignedCodecs4);
    265                codecFamiliesToTry.add(CanonicalCodecFamilies.nonDeltaUnsignedCodecs5);
    266                codecFamiliesToTry.add(CanonicalCodecFamilies.nonDeltaUnsignedCodecs2);
    267            } else {
    268                codecFamiliesToTry.add(CanonicalCodecFamilies.deltaSignedCodecs1);
    269                codecFamiliesToTry.add(CanonicalCodecFamilies.deltaSignedCodecs3);
    270                codecFamiliesToTry.add(CanonicalCodecFamilies.deltaSignedCodecs2);
    271                codecFamiliesToTry.add(CanonicalCodecFamilies.deltaSignedCodecs4);
    272                codecFamiliesToTry.add(CanonicalCodecFamilies.deltaSignedCodecs5);
    273                codecFamiliesToTry.add(CanonicalCodecFamilies.nonDeltaSignedCodecs1);
    274                codecFamiliesToTry.add(CanonicalCodecFamilies.nonDeltaSignedCodecs2);
    275            }
    276        } else if (bandData.anyNegatives()) {
    277            codecFamiliesToTry.add(CanonicalCodecFamilies.nonDeltaSignedCodecs1);
    278            codecFamiliesToTry.add(CanonicalCodecFamilies.nonDeltaSignedCodecs2);
    279            codecFamiliesToTry.add(CanonicalCodecFamilies.deltaSignedCodecs1);
    280            codecFamiliesToTry.add(CanonicalCodecFamilies.deltaSignedCodecs2);
    281            codecFamiliesToTry.add(CanonicalCodecFamilies.deltaSignedCodecs3);
    282            codecFamiliesToTry.add(CanonicalCodecFamilies.deltaSignedCodecs4);
    283            codecFamiliesToTry.add(CanonicalCodecFamilies.deltaSignedCodecs5);
    284        } else {
    285            codecFamiliesToTry.add(CanonicalCodecFamilies.nonDeltaUnsignedCodecs1);
    286            codecFamiliesToTry.add(CanonicalCodecFamilies.nonDeltaUnsignedCodecs3);
    287            codecFamiliesToTry.add(CanonicalCodecFamilies.nonDeltaUnsignedCodecs4);
    288            codecFamiliesToTry.add(CanonicalCodecFamilies.nonDeltaUnsignedCodecs5);
    289            codecFamiliesToTry.add(CanonicalCodecFamilies.nonDeltaUnsignedCodecs2);
    290            codecFamiliesToTry.add(CanonicalCodecFamilies.deltaUnsignedCodecs1);
    291            codecFamiliesToTry.add(CanonicalCodecFamilies.deltaUnsignedCodecs3);
    292            codecFamiliesToTry.add(CanonicalCodecFamilies.deltaUnsignedCodecs4);
    293            codecFamiliesToTry.add(CanonicalCodecFamilies.deltaUnsignedCodecs5);
    294        }
    295        if (name.equalsIgnoreCase("cpint")) {
    296            System.out.print("");
    297        }
    298
    299        for (final BHSDCodec[] family : codecFamiliesToTry) {
    300            tryCodecs(name, band, defaultCodec, bandData, results, encoded, family);
    301            if (timeToStop(results)) {
    302                break;
    303            }
    304        }
    305
    306        return results;
    307    }
    308
    309    /**
    310     * Converts a list of ConstantPoolEntrys to an int[] array of their indices
    311     *
    312     * @param list conversion source.
    313     * @return conversion result.
    314     */
    315    protected int[] cpEntryListToArray(final List<? extends ConstantPoolEntry> list) {
    316        final int[] array = new int[list.size()];
    317        for (int i = 0; i < array.length; i++) {
    318            array[i] = list.get(i).getIndex();
    319            if (array[i] < 0) {
    320                throw new IllegalArgumentException("Index should be > 0");
    321            }
    322        }
    323        return array;
    324    }
    325
    326    /**
    327     * Converts a list of ConstantPoolEntrys or nulls to an int[] array of their indices +1 (or 0 for nulls)
    328     *
    329     * @param list conversion source.
    330     * @return conversion result.
    331     */
    332    protected int[] cpEntryOrNullListToArray(final List<? extends ConstantPoolEntry> list) {
    333        final int[] array = new int[list.size()];
    334        for (int j = 0; j < array.length; j++) {
    335            final ConstantPoolEntry cpEntry = list.get(j);
    336            array[j] = cpEntry == null ? 0 : cpEntry.getIndex() + 1;
    337            if (cpEntry != null && cpEntry.getIndex() < 0) {
    338                throw new IllegalArgumentException("Index should be > 0");
    339            }
    340        }
    341        return array;
    342    }
    343
    344    /**
    345     * Encode a band of integers. The default codec may be used, but other Codecs are considered if effort is greater than 1.
    346     *
    347     * @param name         - name of the band (used for debugging)
    348     * @param ints         - the band
    349     * @param defaultCodec - the default Codec
    350     * @return the encoded band
    351     * @throws Pack200Exception TODO
    352     */
    353    public byte[] encodeBandInt(final String name, final int[] ints, final BHSDCodec defaultCodec) throws Pack200Exception {
    354        byte[] encodedBand = null;
    355        // Useful for debugging
    356//        if (ints.length > 0) {
    357//            System.out.println("encoding " + name + " " + ints.length);
    358//        }
    359        if (effort > 1 && ints.length >= effortThresholds[effort]) {
    360            final BandAnalysisResults results = analyseBand(name, ints, defaultCodec);
    361            final Codec betterCodec = results.betterCodec;
    362            encodedBand = results.encodedBand;
    363            if (betterCodec != null) {
    364                if (betterCodec instanceof BHSDCodec) {
    365                    final int[] specifierBand = CodecEncoding.getSpecifier(betterCodec, defaultCodec);
    366                    int specifier = specifierBand[0];
    367                    if (specifierBand.length > 1) {
    368                        for (int i = 1; i < specifierBand.length; i++) {
    369                            segmentHeader.appendBandCodingSpecifier(specifierBand[i]);
    370                        }
    371                    }
    372                    if (defaultCodec.isSigned()) {
    373                        specifier = -1 - specifier;
    374                    } else {
    375                        specifier += defaultCodec.getL();
    376                    }
    377                    final byte[] specifierEncoded = defaultCodec.encode(new int[] { specifier });
    378                    final byte[] band = new byte[specifierEncoded.length + encodedBand.length];
    379                    System.arraycopy(specifierEncoded, 0, band, 0, specifierEncoded.length);
    380                    System.arraycopy(encodedBand, 0, band, specifierEncoded.length, encodedBand.length);
    381                    return band;
    382                }
    383                if (betterCodec instanceof PopulationCodec) {
    384                    IntStream.of(results.extraMetadata).forEach(segmentHeader::appendBandCodingSpecifier);
    385                    return encodedBand;
    386                }
    387                if (betterCodec instanceof RunCodec) {
    388
    389                }
    390            }
    391        }
    392
    393        // If we get here then we've decided to use the default codec.
    394        if (ints.length > 0) {
    395            if (encodedBand == null) {
    396                encodedBand = defaultCodec.encode(ints);
    397            }
    398            final int first = ints[0];
    399            if (defaultCodec.getB() != 1) {
    400                if (defaultCodec.isSigned() && first >= -256 && first <= -1) {
    401                    final int specifier = -1 - CodecEncoding.getSpecifierForDefaultCodec(defaultCodec);
    402                    final byte[] specifierEncoded = defaultCodec.encode(new int[] { specifier });
    403                    final byte[] band = new byte[specifierEncoded.length + encodedBand.length];
    404                    System.arraycopy(specifierEncoded, 0, band, 0, specifierEncoded.length);
    405                    System.arraycopy(encodedBand, 0, band, specifierEncoded.length, encodedBand.length);
    406                    return band;
    407                }
    408                if (!defaultCodec.isSigned() && first >= defaultCodec.getL() && first <= defaultCodec.getL() + 255) {
    409                    final int specifier = CodecEncoding.getSpecifierForDefaultCodec(defaultCodec) + defaultCodec.getL();
    410                    final byte[] specifierEncoded = defaultCodec.encode(new int[] { specifier });
    411                    final byte[] band = new byte[specifierEncoded.length + encodedBand.length];
    412                    System.arraycopy(specifierEncoded, 0, band, 0, specifierEncoded.length);
    413                    System.arraycopy(encodedBand, 0, band, specifierEncoded.length, encodedBand.length);
    414                    return band;
    415                }
    416            }
    417            return encodedBand;
    418        }
    419        return EMPTY_BYTE_ARRAY;
    420    }
    421
    422    /**
    423     * Encode a band of longs (values are split into their high and low 32 bits and then encoded as two separate bands
    424     *
    425     * @param name        - name of the band (for debugging purposes)
    426     * @param flags       - the band
    427     * @param loCodec     - Codec for the low 32-bits band
    428     * @param hiCodec     - Codec for the high 32-bits band
    429     * @param haveHiFlags - ignores the high band if true as all values would be zero
    430     * @return the encoded band
    431     * @throws Pack200Exception TODO
    432     */
    433    protected byte[] encodeFlags(final String name, final long[] flags, final BHSDCodec loCodec, final BHSDCodec hiCodec, final boolean haveHiFlags)
    434            throws Pack200Exception {
    435        if (!haveHiFlags) {
    436            final int[] loBits = new int[flags.length];
    437            Arrays.setAll(loBits, i -> (int) flags[i]);
    438            return encodeBandInt(name, loBits, loCodec);
    439        }
    440        final int[] hiBits = new int[flags.length];
    441        final int[] loBits = new int[flags.length];
    442        for (int i = 0; i < flags.length; i++) {
    443            final long l = flags[i];
    444            hiBits[i] = (int) (l >> 32);
    445            loBits[i] = (int) l;
    446        }
    447        final byte[] hi = encodeBandInt(name, hiBits, hiCodec);
    448        final byte[] lo = encodeBandInt(name, loBits, loCodec);
    449        final byte[] total = new byte[hi.length + lo.length];
    450        System.arraycopy(hi, 0, total, 0, hi.length);
    451        System.arraycopy(lo, 0, total, hi.length + 1, lo.length);
    452        return total;
    453    }
    454
    455// This could be useful if further enhancements are done but is not currently used
    456//
    457//    private void encodeWithRunCodec(String name, int[] band, int index,
    458//            BHSDCodec defaultCodec, BandData bandData,
    459//            BandAnalysisResults results) throws Pack200Exception {
    460//        int[] firstBand = new int[index];
    461//        int[] secondBand = new int[band.length - index];
    462//        System.arraycopy(band, 0, firstBand, 0, index);
    463//        System.arraycopy(band, index, secondBand, 0, secondBand.length);
    464//        BandAnalysisResults firstResults = analyseBand(name + "A", firstBand, defaultCodec);
    465//        BandAnalysisResults secondResults = analyseBand(name + "B", secondBand, defaultCodec);
    466//        int specifier = 117;
    467//        byte[] specifierEncoded = defaultCodec.encode(new int[] {specifier});
    468//        int totalLength = firstResults.encodedBand.length + secondResults.encodedBand.length + specifierEncoded.length + 4; // TODO actual
    469//        if (totalLength < results.encodedBand.length) {
    470//            System.out.println("using run codec");
    471//            results.saved += results.encodedBand.length - totalLength;
    472//            byte[] encodedBand = new byte[specifierEncoded.length + firstResults.encodedBand.length + secondResults.encodedBand.length];
    473//            System.arraycopy(specifierEncoded, 0, encodedBand, 0, specifierEncoded.length);
    474//            System.arraycopy(firstResults.encodedBand, 0, encodedBand, specifierEncoded.length, firstResults.encodedBand.length);
    475//            System.arraycopy(secondResults.encodedBand, 0, encodedBand, specifierEncoded.length + firstResults.encodedBand.length,
    476//              secondResults.encodedBand.length);
    477//            results.encodedBand = encodedBand;
    478//            results.betterCodec = new RunCodec(index, firstResults.betterCodec, secondResults.betterCodec);
    479//        }
    480//    }
    481
    482    protected byte[] encodeFlags(final String name, final long[][] flags, final BHSDCodec loCodec, final BHSDCodec hiCodec, final boolean haveHiFlags)
    483            throws Pack200Exception {
    484        return encodeFlags(name, flatten(flags), loCodec, hiCodec, haveHiFlags);
    485    }
    486
    487    /**
    488     * Encode a single value with the given Codec
    489     *
    490     * @param value - the value to encode
    491     * @param codec - Codec to use
    492     * @return the encoded value
    493     * @throws Pack200Exception TODO
    494     */
    495    public byte[] encodeScalar(final int value, final BHSDCodec codec) throws Pack200Exception {
    496        return codec.encode(value);
    497    }
    498
    499    /**
    500     * Encode a band without considering other Codecs
    501     *
    502     * @param band  - the band
    503     * @param codec - the Codec to use
    504     * @return the encoded band
    505     * @throws Pack200Exception TODO
    506     */
    507    public byte[] encodeScalar(final int[] band, final BHSDCodec codec) throws Pack200Exception {
    508        return codec.encode(band);
    509    }
    510
    511    private void encodeWithPopulationCodec(final String name, final int[] band, final BHSDCodec defaultCodec, final BandData bandData,
    512            final BandAnalysisResults results) throws Pack200Exception {
    513        results.numCodecsTried += 3; // quite a bit more effort to try this codec
    514        final Map<Integer, Integer> distinctValues = bandData.distinctValues;
    515
    516        final List<Integer> favored = new ArrayList<>();
    517        distinctValues.forEach((k, v) -> {
    518            if (v.intValue() > 2 || distinctValues.size() < 256) { // TODO: tweak
    519                favored.add(k);
    520            }
    521        });
    522
    523        // Sort the favored list with the most commonly occurring first
    524        if (distinctValues.size() > 255) {
    525            favored.sort((arg0, arg1) -> distinctValues.get(arg1).compareTo(distinctValues.get(arg0)));
    526        }
    527
    528        final Map<Integer, Integer> favoredToIndex = new HashMap<>();
    529        for (int i = 0; i < favored.size(); i++) {
    530            favoredToIndex.put(favored.get(i), Integer.valueOf(i));
    531        }
    532
    533        final IntList unfavoured = new IntList();
    534        final int[] tokens = new int[band.length];
    535        for (int i = 0; i < band.length; i++) {
    536            final Integer favouredIndex = favoredToIndex.get(Integer.valueOf(band[i]));
    537            if (favouredIndex == null) {
    538                tokens[i] = 0;
    539                unfavoured.add(band[i]);
    540            } else {
    541                tokens[i] = favouredIndex.intValue() + 1;
    542            }
    543        }
    544        favored.add(favored.get(favored.size() - 1)); // repeat last value
    545        final int[] favouredBand = integerListToArray(favored);
    546        final int[] unfavouredBand = unfavoured.toArray();
    547
    548        // Analyse the three bands to get the best codec
    549        final BandAnalysisResults favouredResults = analyseBand("POPULATION", favouredBand, defaultCodec);
    550        final BandAnalysisResults unfavouredResults = analyseBand("POPULATION", unfavouredBand, defaultCodec);
    551
    552        int tdefL = 0;
    553        int l = 0;
    554        Codec tokenCodec = null;
    555        byte[] tokensEncoded;
    556        final int k = favored.size() - 1;
    557        if (k < 256) {
    558            tdefL = 1;
    559            tokensEncoded = Codec.BYTE1.encode(tokens);
    560        } else {
    561            final BandAnalysisResults tokenResults = analyseBand("POPULATION", tokens, defaultCodec);
    562            tokenCodec = tokenResults.betterCodec;
    563            tokensEncoded = tokenResults.encodedBand;
    564            if (tokenCodec == null) {
    565                tokenCodec = defaultCodec;
    566            }
    567            l = ((BHSDCodec) tokenCodec).getL();
    568            final int h = ((BHSDCodec) tokenCodec).getH();
    569            final int s = ((BHSDCodec) tokenCodec).getS();
    570            final int b = ((BHSDCodec) tokenCodec).getB();
    571            final int d = ((BHSDCodec) tokenCodec).isDelta() ? 1 : 0;
    572            if (s == 0 && d == 0) {
    573                boolean canUseTDefL = true;
    574                if (b > 1) {
    575                    final BHSDCodec oneLowerB = new BHSDCodec(b - 1, h);
    576                    if (oneLowerB.largest() >= k) {
    577                        canUseTDefL = false;
    578                    }
    579                }
    580                if (canUseTDefL) {
    581                    switch (l) {
    582                    case 4:
    583                        tdefL = 1;
    584                        break;
    585                    case 8:
    586                        tdefL = 2;
    587                        break;
    588                    case 16:
    589                        tdefL = 3;
    590                        break;
    591                    case 32:
    592                        tdefL = 4;
    593                        break;
    594                    case 64:
    595                        tdefL = 5;
    596                        break;
    597                    case 128:
    598                        tdefL = 6;
    599                        break;
    600                    case 192:
    601                        tdefL = 7;
    602                        break;
    603                    case 224:
    604                        tdefL = 8;
    605                        break;
    606                    case 240:
    607                        tdefL = 9;
    608                        break;
    609                    case 248:
    610                        tdefL = 10;
    611                        break;
    612                    case 252:
    613                        tdefL = 11;
    614                        break;
    615                    }
    616                }
    617            }
    618        }
    619
    620        final byte[] favouredEncoded = favouredResults.encodedBand;
    621        final byte[] unfavouredEncoded = unfavouredResults.encodedBand;
    622        final Codec favouredCodec = favouredResults.betterCodec;
    623        final Codec unfavouredCodec = unfavouredResults.betterCodec;
    624
    625        int specifier = 141 + (favouredCodec == null ? 1 : 0) + 4 * tdefL + (unfavouredCodec == null ? 2 : 0);
    626        final IntList extraBandMetadata = new IntList(3);
    627        if (favouredCodec != null) {
    628            IntStream.of(CodecEncoding.getSpecifier(favouredCodec, null)).forEach(extraBandMetadata::add);
    629        }
    630        if (tdefL == 0) {
    631            IntStream.of(CodecEncoding.getSpecifier(tokenCodec, null)).forEach(extraBandMetadata::add);
    632        }
    633        if (unfavouredCodec != null) {
    634            IntStream.of(CodecEncoding.getSpecifier(unfavouredCodec, null)).forEach(extraBandMetadata::add);
    635        }
    636        final int[] extraMetadata = extraBandMetadata.toArray();
    637        final byte[] extraMetadataEncoded = Codec.UNSIGNED5.encode(extraMetadata);
    638        if (defaultCodec.isSigned()) {
    639            specifier = -1 - specifier;
    640        } else {
    641            specifier += defaultCodec.getL();
    642        }
    643        final byte[] firstValueEncoded = defaultCodec.encode(new int[] { specifier });
    644        final int totalBandLength = firstValueEncoded.length + favouredEncoded.length + tokensEncoded.length + unfavouredEncoded.length;
    645
    646        if (totalBandLength + extraMetadataEncoded.length < results.encodedBand.length) {
    647            results.saved += results.encodedBand.length - (totalBandLength + extraMetadataEncoded.length);
    648            final byte[] encodedBand = new byte[totalBandLength];
    649            System.arraycopy(firstValueEncoded, 0, encodedBand, 0, firstValueEncoded.length);
    650            System.arraycopy(favouredEncoded, 0, encodedBand, firstValueEncoded.length, favouredEncoded.length);
    651            System.arraycopy(tokensEncoded, 0, encodedBand, firstValueEncoded.length + favouredEncoded.length, tokensEncoded.length);
    652            System.arraycopy(unfavouredEncoded, 0, encodedBand, firstValueEncoded.length + favouredEncoded.length + tokensEncoded.length,
    653                    unfavouredEncoded.length);
    654            results.encodedBand = encodedBand;
    655            results.extraMetadata = extraMetadata;
    656            if (l != 0) {
    657                results.betterCodec = new PopulationCodec(favouredCodec, l, unfavouredCodec);
    658            } else {
    659                results.betterCodec = new PopulationCodec(favouredCodec, tokenCodec, unfavouredCodec);
    660            }
    661        }
    662    }
    663
    664    /*
    665     * Flatten a 2-dimension array into a 1-dimension array
    666     */
    667    private long[] flatten(final long[][] flags) {
    668        int totalSize = 0;
    669        for (final long[] flag : flags) {
    670            totalSize += flag.length;
    671        }
    672        final long[] flatArray = new long[totalSize];
    673        int index = 0;
    674        for (final long[] flag : flags) {
    675            for (final long element : flag) {
    676                flatArray[index] = element;
    677                index++;
    678            }
    679        }
    680        return flatArray;
    681    }
    682
    683    /**
    684     * Converts a list of Integers to an int[] array.
    685     *
    686     * @param integerList conversion source.
    687     * @return conversion result.
    688     */
    689    protected int[] integerListToArray(final List<Integer> integerList) {
    690        return integerList.stream().mapToInt(Integer::intValue).toArray();
    691    }
    692
    693    /**
    694     * Converts a list of Longs to an long[] array.
    695     *
    696     * @param longList conversion source.
    697     * @return conversion result.
    698     */
    699    protected long[] longListToArray(final List<Long> longList) {
    700        return longList.stream().mapToLong(Long::longValue).toArray();
    701    }
    702
    703    /**
    704     * Write the packed set of bands to the given output stream
    705     *
    706     * @param out TODO
    707     * @throws IOException      If an I/O error occurs.
    708     * @throws Pack200Exception TODO
    709     */
    710    public abstract void pack(OutputStream out) throws IOException, Pack200Exception;
    711
    712    private boolean timeToStop(final BandAnalysisResults results) {
    713        // if tried more than effort number of codecs for this band then return
    714        // Note: these values have been tuned - please test carefully if changing them
    715        if (effort > 6) {
    716            return results.numCodecsTried >= effort * 2;
    717        }
    718        return results.numCodecsTried >= effort;
    719        // May want to also check how much we've saved if performance needs improving, e.g. saved more than effort*2 %
    720        // || (float) results.saved/(float) results.encodedBand.length > (float) effort * 2/100;
    721    }
    722
    723    private void tryCodecs(final String name, final int[] band, final BHSDCodec defaultCodec, final BandData bandData, final BandAnalysisResults results,
    724            final byte[] encoded, final BHSDCodec[] potentialCodecs) throws Pack200Exception {
    725        for (final BHSDCodec potential : potentialCodecs) {
    726            if (potential.equals(defaultCodec)) {
    727                return; // don't try codecs with greater cardinality in the same 'family' as the default codec as there
    728                        // won't be any savings
    729            }
    730            if (potential.isDelta()) {
    731                if (potential.largest() >= bandData.largestDelta && potential.smallest() <= bandData.smallestDelta && potential.largest() >= bandData.largest
    732                        && potential.smallest() <= bandData.smallest) {
    733                    // TODO: can represent some negative deltas with overflow
    734                    final byte[] encoded2 = potential.encode(band);
    735                    results.numCodecsTried++;
    736                    final byte[] specifierEncoded = defaultCodec.encode(CodecEncoding.getSpecifier(potential, null));
    737                    final int saved = encoded.length - encoded2.length - specifierEncoded.length;
    738                    if (saved > results.saved) {
    739                        results.betterCodec = potential;
    740                        results.encodedBand = encoded2;
    741                        results.saved = saved;
    742                    }
    743                }
    744            } else if (potential.largest() >= bandData.largest && potential.smallest() <= bandData.smallest) {
    745                final byte[] encoded2 = potential.encode(band);
    746                results.numCodecsTried++;
    747                final byte[] specifierEncoded = defaultCodec.encode(CodecEncoding.getSpecifier(potential, null));
    748                final int saved = encoded.length - encoded2.length - specifierEncoded.length;
    749                if (saved > results.saved) {
    750                    results.betterCodec = potential;
    751                    results.encodedBand = encoded2;
    752                    results.saved = saved;
    753                }
    754            }
    755            if (timeToStop(results)) {
    756                return;
    757            }
    758        }
    759    }
    760
    761}