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