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}