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}