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