1 /* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 * 17 */ 18 19 /* 20 * This package is based on the work done by Keiron Liddle, Aftex Software 21 * <keiron@aftexsw.com> to whom the Ant project is very grateful for his 22 * great code. 23 */ 24 25 package org.apache.hadoop.io.compress.bzip2; 26 27 import java.io.OutputStream; 28 import java.io.IOException; 29 30 /** 31 * An output stream that compresses into the BZip2 format (without the file 32 * header chars) into another stream. 33 * 34 * <p> 35 * The compression requires large amounts of memory. Thus you should call the 36 * {@link #close() close()} method as soon as possible, to force 37 * <tt>CBZip2OutputStream</tt> to release the allocated memory. 38 * </p> 39 * 40 * <p> 41 * You can shrink the amount of allocated memory and maybe raise the compression 42 * speed by choosing a lower blocksize, which in turn may cause a lower 43 * compression ratio. You can avoid unnecessary memory allocation by avoiding 44 * using a blocksize which is bigger than the size of the input. 45 * </p> 46 * 47 * <p> 48 * You can compute the memory usage for compressing by the following formula: 49 * </p> 50 * 51 * <pre> 52 * <code>400k + (9 * blocksize)</code>. 53 * </pre> 54 * 55 * <p> 56 * To get the memory required for decompression by {@link CBZip2InputStream 57 * CBZip2InputStream} use 58 * </p> 59 * 60 * <pre> 61 * <code>65k + (5 * blocksize)</code>. 62 * </pre> 63 * 64 * <table width="100%" border="1"> 65 * <colgroup> <col width="33%" /> <col width="33%" /> <col width="33%" /> 66 * </colgroup> 67 * <tr> 68 * <th colspan="3">Memory usage by blocksize</th> 69 * </tr> 70 * <tr> 71 * <th align="right">Blocksize</th> <th align="right">Compression<br> 72 * memory usage</th> <th align="right">Decompression<br> 73 * memory usage</th> 74 * </tr> 75 * <tr> 76 * <td align="right">100k</td> 77 * <td align="right">1300k</td> 78 * <td align="right">565k</td> 79 * </tr> 80 * <tr> 81 * <td align="right">200k</td> 82 * <td align="right">2200k</td> 83 * <td align="right">1065k</td> 84 * </tr> 85 * <tr> 86 * <td align="right">300k</td> 87 * <td align="right">3100k</td> 88 * <td align="right">1565k</td> 89 * </tr> 90 * <tr> 91 * <td align="right">400k</td> 92 * <td align="right">4000k</td> 93 * <td align="right">2065k</td> 94 * </tr> 95 * <tr> 96 * <td align="right">500k</td> 97 * <td align="right">4900k</td> 98 * <td align="right">2565k</td> 99 * </tr> 100 * <tr> 101 * <td align="right">600k</td> 102 * <td align="right">5800k</td> 103 * <td align="right">3065k</td> 104 * </tr> 105 * <tr> 106 * <td align="right">700k</td> 107 * <td align="right">6700k</td> 108 * <td align="right">3565k</td> 109 * </tr> 110 * <tr> 111 * <td align="right">800k</td> 112 * <td align="right">7600k</td> 113 * <td align="right">4065k</td> 114 * </tr> 115 * <tr> 116 * <td align="right">900k</td> 117 * <td align="right">8500k</td> 118 * <td align="right">4565k</td> 119 * </tr> 120 * </table> 121 * 122 * <p> 123 * For decompression <tt>CBZip2InputStream</tt> allocates less memory if the 124 * bzipped input is smaller than one block. 125 * </p> 126 * 127 * <p> 128 * Instances of this class are not threadsafe. 129 * </p> 130 * 131 * <p> 132 * TODO: Update to BZip2 1.0.1 133 * </p> 134 * 135 */ 136 public class CBZip2OutputStream extends OutputStream implements BZip2Constants { 137 138 /** 139 * The minimum supported blocksize <tt> == 1</tt>. 140 */ 141 public static final int MIN_BLOCKSIZE = 1; 142 143 /** 144 * The maximum supported blocksize <tt> == 9</tt>. 145 */ 146 public static final int MAX_BLOCKSIZE = 9; 147 148 /** 149 * This constant is accessible by subclasses for historical purposes. If you 150 * don't know what it means then you don't need it. 151 */ 152 protected static final int SETMASK = (1 << 21); 153 154 /** 155 * This constant is accessible by subclasses for historical purposes. If you 156 * don't know what it means then you don't need it. 157 */ 158 protected static final int CLEARMASK = (~SETMASK); 159 160 /** 161 * This constant is accessible by subclasses for historical purposes. If you 162 * don't know what it means then you don't need it. 163 */ 164 protected static final int GREATER_ICOST = 15; 165 166 /** 167 * This constant is accessible by subclasses for historical purposes. If you 168 * don't know what it means then you don't need it. 169 */ 170 protected static final int LESSER_ICOST = 0; 171 172 /** 173 * This constant is accessible by subclasses for historical purposes. If you 174 * don't know what it means then you don't need it. 175 */ 176 protected static final int SMALL_THRESH = 20; 177 178 /** 179 * This constant is accessible by subclasses for historical purposes. If you 180 * don't know what it means then you don't need it. 181 */ 182 protected static final int DEPTH_THRESH = 10; 183 184 /** 185 * This constant is accessible by subclasses for historical purposes. If you 186 * don't know what it means then you don't need it. 187 */ 188 protected static final int WORK_FACTOR = 30; 189 190 /** 191 * This constant is accessible by subclasses for historical purposes. If you 192 * don't know what it means then you don't need it. 193 * <p> 194 * If you are ever unlucky/improbable enough to get a stack overflow whilst 195 * sorting, increase the following constant and try again. In practice I 196 * have never seen the stack go above 27 elems, so the following limit seems 197 * very generous. 198 * </p> 199 */ 200 protected static final int QSORT_STACK_SIZE = 1000; 201 202 /** 203 * Knuth's increments seem to work better than Incerpi-Sedgewick here. 204 * Possibly because the number of elems to sort is usually small, typically 205 * <= 20. 206 */ 207 private static final int[] INCS = { 1, 4, 13, 40, 121, 364, 1093, 3280, 208 9841, 29524, 88573, 265720, 797161, 2391484 }; 209 210 /** 211 * This method is accessible by subclasses for historical purposes. If you 212 * don't know what it does then you don't need it. 213 */ hbMakeCodeLengths(char[] len, int[] freq, int alphaSize, int maxLen)214 protected static void hbMakeCodeLengths(char[] len, int[] freq, 215 int alphaSize, int maxLen) { 216 /* 217 * Nodes and heap entries run from 1. Entry 0 for both the heap and 218 * nodes is a sentinel. 219 */ 220 final int[] heap = new int[MAX_ALPHA_SIZE * 2]; 221 final int[] weight = new int[MAX_ALPHA_SIZE * 2]; 222 final int[] parent = new int[MAX_ALPHA_SIZE * 2]; 223 224 for (int i = alphaSize; --i >= 0;) { 225 weight[i + 1] = (freq[i] == 0 ? 1 : freq[i]) << 8; 226 } 227 228 for (boolean tooLong = true; tooLong;) { 229 tooLong = false; 230 231 int nNodes = alphaSize; 232 int nHeap = 0; 233 heap[0] = 0; 234 weight[0] = 0; 235 parent[0] = -2; 236 237 for (int i = 1; i <= alphaSize; i++) { 238 parent[i] = -1; 239 nHeap++; 240 heap[nHeap] = i; 241 242 int zz = nHeap; 243 int tmp = heap[zz]; 244 while (weight[tmp] < weight[heap[zz >> 1]]) { 245 heap[zz] = heap[zz >> 1]; 246 zz >>= 1; 247 } 248 heap[zz] = tmp; 249 } 250 251 // assert (nHeap < (MAX_ALPHA_SIZE + 2)) : nHeap; 252 253 while (nHeap > 1) { 254 int n1 = heap[1]; 255 heap[1] = heap[nHeap]; 256 nHeap--; 257 258 int yy = 0; 259 int zz = 1; 260 int tmp = heap[1]; 261 262 while (true) { 263 yy = zz << 1; 264 265 if (yy > nHeap) { 266 break; 267 } 268 269 if ((yy < nHeap) 270 && (weight[heap[yy + 1]] < weight[heap[yy]])) { 271 yy++; 272 } 273 274 if (weight[tmp] < weight[heap[yy]]) { 275 break; 276 } 277 278 heap[zz] = heap[yy]; 279 zz = yy; 280 } 281 282 heap[zz] = tmp; 283 284 int n2 = heap[1]; 285 heap[1] = heap[nHeap]; 286 nHeap--; 287 288 yy = 0; 289 zz = 1; 290 tmp = heap[1]; 291 292 while (true) { 293 yy = zz << 1; 294 295 if (yy > nHeap) { 296 break; 297 } 298 299 if ((yy < nHeap) 300 && (weight[heap[yy + 1]] < weight[heap[yy]])) { 301 yy++; 302 } 303 304 if (weight[tmp] < weight[heap[yy]]) { 305 break; 306 } 307 308 heap[zz] = heap[yy]; 309 zz = yy; 310 } 311 312 heap[zz] = tmp; 313 nNodes++; 314 parent[n1] = parent[n2] = nNodes; 315 316 final int weight_n1 = weight[n1]; 317 final int weight_n2 = weight[n2]; 318 weight[nNodes] = (((weight_n1 & 0xffffff00) + (weight_n2 & 0xffffff00)) | (1 + (((weight_n1 & 0x000000ff) > (weight_n2 & 0x000000ff)) ? (weight_n1 & 0x000000ff) 319 : (weight_n2 & 0x000000ff)))); 320 321 parent[nNodes] = -1; 322 nHeap++; 323 heap[nHeap] = nNodes; 324 325 tmp = 0; 326 zz = nHeap; 327 tmp = heap[zz]; 328 final int weight_tmp = weight[tmp]; 329 while (weight_tmp < weight[heap[zz >> 1]]) { 330 heap[zz] = heap[zz >> 1]; 331 zz >>= 1; 332 } 333 heap[zz] = tmp; 334 335 } 336 337 // assert (nNodes < (MAX_ALPHA_SIZE * 2)) : nNodes; 338 339 for (int i = 1; i <= alphaSize; i++) { 340 int j = 0; 341 int k = i; 342 343 for (int parent_k; (parent_k = parent[k]) >= 0;) { 344 k = parent_k; 345 j++; 346 } 347 348 len[i - 1] = (char) j; 349 if (j > maxLen) { 350 tooLong = true; 351 } 352 } 353 354 if (tooLong) { 355 for (int i = 1; i < alphaSize; i++) { 356 int j = weight[i] >> 8; 357 j = 1 + (j >> 1); 358 weight[i] = j << 8; 359 } 360 } 361 } 362 } 363 hbMakeCodeLengths(final byte[] len, final int[] freq, final Data dat, final int alphaSize, final int maxLen)364 private static void hbMakeCodeLengths(final byte[] len, final int[] freq, 365 final Data dat, final int alphaSize, final int maxLen) { 366 /* 367 * Nodes and heap entries run from 1. Entry 0 for both the heap and 368 * nodes is a sentinel. 369 */ 370 final int[] heap = dat.heap; 371 final int[] weight = dat.weight; 372 final int[] parent = dat.parent; 373 374 for (int i = alphaSize; --i >= 0;) { 375 weight[i + 1] = (freq[i] == 0 ? 1 : freq[i]) << 8; 376 } 377 378 for (boolean tooLong = true; tooLong;) { 379 tooLong = false; 380 381 int nNodes = alphaSize; 382 int nHeap = 0; 383 heap[0] = 0; 384 weight[0] = 0; 385 parent[0] = -2; 386 387 for (int i = 1; i <= alphaSize; i++) { 388 parent[i] = -1; 389 nHeap++; 390 heap[nHeap] = i; 391 392 int zz = nHeap; 393 int tmp = heap[zz]; 394 while (weight[tmp] < weight[heap[zz >> 1]]) { 395 heap[zz] = heap[zz >> 1]; 396 zz >>= 1; 397 } 398 heap[zz] = tmp; 399 } 400 401 while (nHeap > 1) { 402 int n1 = heap[1]; 403 heap[1] = heap[nHeap]; 404 nHeap--; 405 406 int yy = 0; 407 int zz = 1; 408 int tmp = heap[1]; 409 410 while (true) { 411 yy = zz << 1; 412 413 if (yy > nHeap) { 414 break; 415 } 416 417 if ((yy < nHeap) 418 && (weight[heap[yy + 1]] < weight[heap[yy]])) { 419 yy++; 420 } 421 422 if (weight[tmp] < weight[heap[yy]]) { 423 break; 424 } 425 426 heap[zz] = heap[yy]; 427 zz = yy; 428 } 429 430 heap[zz] = tmp; 431 432 int n2 = heap[1]; 433 heap[1] = heap[nHeap]; 434 nHeap--; 435 436 yy = 0; 437 zz = 1; 438 tmp = heap[1]; 439 440 while (true) { 441 yy = zz << 1; 442 443 if (yy > nHeap) { 444 break; 445 } 446 447 if ((yy < nHeap) 448 && (weight[heap[yy + 1]] < weight[heap[yy]])) { 449 yy++; 450 } 451 452 if (weight[tmp] < weight[heap[yy]]) { 453 break; 454 } 455 456 heap[zz] = heap[yy]; 457 zz = yy; 458 } 459 460 heap[zz] = tmp; 461 nNodes++; 462 parent[n1] = parent[n2] = nNodes; 463 464 final int weight_n1 = weight[n1]; 465 final int weight_n2 = weight[n2]; 466 weight[nNodes] = ((weight_n1 & 0xffffff00) + (weight_n2 & 0xffffff00)) 467 | (1 + (((weight_n1 & 0x000000ff) > (weight_n2 & 0x000000ff)) ? (weight_n1 & 0x000000ff) 468 : (weight_n2 & 0x000000ff))); 469 470 parent[nNodes] = -1; 471 nHeap++; 472 heap[nHeap] = nNodes; 473 474 tmp = 0; 475 zz = nHeap; 476 tmp = heap[zz]; 477 final int weight_tmp = weight[tmp]; 478 while (weight_tmp < weight[heap[zz >> 1]]) { 479 heap[zz] = heap[zz >> 1]; 480 zz >>= 1; 481 } 482 heap[zz] = tmp; 483 484 } 485 486 for (int i = 1; i <= alphaSize; i++) { 487 int j = 0; 488 int k = i; 489 490 for (int parent_k; (parent_k = parent[k]) >= 0;) { 491 k = parent_k; 492 j++; 493 } 494 495 len[i - 1] = (byte) j; 496 if (j > maxLen) { 497 tooLong = true; 498 } 499 } 500 501 if (tooLong) { 502 for (int i = 1; i < alphaSize; i++) { 503 int j = weight[i] >> 8; 504 j = 1 + (j >> 1); 505 weight[i] = j << 8; 506 } 507 } 508 } 509 } 510 511 /** 512 * Index of the last char in the block, so the block size == last + 1. 513 */ 514 private int last; 515 516 /** 517 * Index in fmap[] of original string after sorting. 518 */ 519 private int origPtr; 520 521 /** 522 * Always: in the range 0 .. 9. The current block size is 100000 * this 523 * number. 524 */ 525 private final int blockSize100k; 526 527 private boolean blockRandomised; 528 529 private int bsBuff; 530 private int bsLive; 531 private final CRC crc = new CRC(); 532 533 private int nInUse; 534 535 private int nMTF; 536 537 /* 538 * Used when sorting. If too many long comparisons happen, we stop sorting, 539 * randomise the block slightly, and try again. 540 */ 541 private int workDone; 542 private int workLimit; 543 private boolean firstAttempt; 544 545 private int currentChar = -1; 546 private int runLength = 0; 547 548 private int blockCRC; 549 private int combinedCRC; 550 private int allowableBlockSize; 551 552 /** 553 * All memory intensive stuff. 554 */ 555 private CBZip2OutputStream.Data data; 556 557 private OutputStream out; 558 559 /** 560 * Chooses a blocksize based on the given length of the data to compress. 561 * 562 * @return The blocksize, between {@link #MIN_BLOCKSIZE} and 563 * {@link #MAX_BLOCKSIZE} both inclusive. For a negative 564 * <tt>inputLength</tt> this method returns <tt>MAX_BLOCKSIZE</tt> 565 * always. 566 * 567 * @param inputLength 568 * The length of the data which will be compressed by 569 * <tt>CBZip2OutputStream</tt>. 570 */ chooseBlockSize(long inputLength)571 public static int chooseBlockSize(long inputLength) { 572 return (inputLength > 0) ? (int) Math 573 .min((inputLength / 132000) + 1, 9) : MAX_BLOCKSIZE; 574 } 575 576 /** 577 * Constructs a new <tt>CBZip2OutputStream</tt> with a blocksize of 900k. 578 * 579 * <p> 580 * <b>Attention: </b>The caller is resonsible to write the two BZip2 magic 581 * bytes <tt>"BZ"</tt> to the specified stream prior to calling this 582 * constructor. 583 * </p> 584 * 585 * @param out * 586 * the destination stream. 587 * 588 * @throws IOException 589 * if an I/O error occurs in the specified stream. 590 * @throws NullPointerException 591 * if <code>out == null</code>. 592 */ CBZip2OutputStream(final OutputStream out)593 public CBZip2OutputStream(final OutputStream out) throws IOException { 594 this(out, MAX_BLOCKSIZE); 595 } 596 597 /** 598 * Constructs a new <tt>CBZip2OutputStream</tt> with specified blocksize. 599 * 600 * <p> 601 * <b>Attention: </b>The caller is resonsible to write the two BZip2 magic 602 * bytes <tt>"BZ"</tt> to the specified stream prior to calling this 603 * constructor. 604 * </p> 605 * 606 * 607 * @param out 608 * the destination stream. 609 * @param blockSize 610 * the blockSize as 100k units. 611 * 612 * @throws IOException 613 * if an I/O error occurs in the specified stream. 614 * @throws IllegalArgumentException 615 * if <code>(blockSize < 1) || (blockSize > 9)</code>. 616 * @throws NullPointerException 617 * if <code>out == null</code>. 618 * 619 * @see #MIN_BLOCKSIZE 620 * @see #MAX_BLOCKSIZE 621 */ CBZip2OutputStream(final OutputStream out, final int blockSize)622 public CBZip2OutputStream(final OutputStream out, final int blockSize) 623 throws IOException { 624 super(); 625 626 if (blockSize < 1) { 627 throw new IllegalArgumentException("blockSize(" + blockSize 628 + ") < 1"); 629 } 630 if (blockSize > 9) { 631 throw new IllegalArgumentException("blockSize(" + blockSize 632 + ") > 9"); 633 } 634 635 this.blockSize100k = blockSize; 636 this.out = out; 637 init(); 638 } 639 write(final int b)640 public void write(final int b) throws IOException { 641 if (this.out != null) { 642 write0(b); 643 } else { 644 throw new IOException("closed"); 645 } 646 } 647 writeRun()648 private void writeRun() throws IOException { 649 final int lastShadow = this.last; 650 651 if (lastShadow < this.allowableBlockSize) { 652 final int currentCharShadow = this.currentChar; 653 final Data dataShadow = this.data; 654 dataShadow.inUse[currentCharShadow] = true; 655 final byte ch = (byte) currentCharShadow; 656 657 int runLengthShadow = this.runLength; 658 this.crc.updateCRC(currentCharShadow, runLengthShadow); 659 660 switch (runLengthShadow) { 661 case 1: 662 dataShadow.block[lastShadow + 2] = ch; 663 this.last = lastShadow + 1; 664 break; 665 666 case 2: 667 dataShadow.block[lastShadow + 2] = ch; 668 dataShadow.block[lastShadow + 3] = ch; 669 this.last = lastShadow + 2; 670 break; 671 672 case 3: { 673 final byte[] block = dataShadow.block; 674 block[lastShadow + 2] = ch; 675 block[lastShadow + 3] = ch; 676 block[lastShadow + 4] = ch; 677 this.last = lastShadow + 3; 678 } 679 break; 680 681 default: { 682 runLengthShadow -= 4; 683 dataShadow.inUse[runLengthShadow] = true; 684 final byte[] block = dataShadow.block; 685 block[lastShadow + 2] = ch; 686 block[lastShadow + 3] = ch; 687 block[lastShadow + 4] = ch; 688 block[lastShadow + 5] = ch; 689 block[lastShadow + 6] = (byte) runLengthShadow; 690 this.last = lastShadow + 5; 691 } 692 break; 693 694 } 695 } else { 696 endBlock(); 697 initBlock(); 698 writeRun(); 699 } 700 } 701 702 /** 703 * Overriden to close the stream. 704 */ finalize()705 protected void finalize() throws Throwable { 706 finish(); 707 super.finalize(); 708 } 709 710 finish()711 public void finish() throws IOException { 712 if (out != null) { 713 try { 714 if (this.runLength > 0) { 715 writeRun(); 716 } 717 this.currentChar = -1; 718 endBlock(); 719 endCompression(); 720 } finally { 721 this.out = null; 722 this.data = null; 723 } 724 } 725 } 726 close()727 public void close() throws IOException { 728 if (out != null) { 729 OutputStream outShadow = this.out; 730 finish(); 731 outShadow.close(); 732 } 733 } 734 flush()735 public void flush() throws IOException { 736 OutputStream outShadow = this.out; 737 if (outShadow != null) { 738 outShadow.flush(); 739 } 740 } 741 init()742 private void init() throws IOException { 743 // write magic: done by caller who created this stream 744 // this.out.write('B'); 745 // this.out.write('Z'); 746 747 this.data = new Data(this.blockSize100k); 748 749 /* 750 * Write `magic' bytes h indicating file-format == huffmanised, followed 751 * by a digit indicating blockSize100k. 752 */ 753 bsPutUByte('h'); 754 bsPutUByte('0' + this.blockSize100k); 755 756 this.combinedCRC = 0; 757 initBlock(); 758 } 759 initBlock()760 private void initBlock() { 761 // blockNo++; 762 this.crc.initialiseCRC(); 763 this.last = -1; 764 // ch = 0; 765 766 boolean[] inUse = this.data.inUse; 767 for (int i = 256; --i >= 0;) { 768 inUse[i] = false; 769 } 770 771 /* 20 is just a paranoia constant */ 772 this.allowableBlockSize = (this.blockSize100k * BZip2Constants.baseBlockSize) - 20; 773 } 774 endBlock()775 private void endBlock() throws IOException { 776 this.blockCRC = this.crc.getFinalCRC(); 777 this.combinedCRC = (this.combinedCRC << 1) | (this.combinedCRC >>> 31); 778 this.combinedCRC ^= this.blockCRC; 779 780 // empty block at end of file 781 if (this.last == -1) { 782 return; 783 } 784 785 /* sort the block and establish posn of original string */ 786 blockSort(); 787 788 /* 789 * A 6-byte block header, the value chosen arbitrarily as 0x314159265359 790 * :-). A 32 bit value does not really give a strong enough guarantee 791 * that the value will not appear by chance in the compressed 792 * datastream. Worst-case probability of this event, for a 900k block, 793 * is about 2.0e-3 for 32 bits, 1.0e-5 for 40 bits and 4.0e-8 for 48 794 * bits. For a compressed file of size 100Gb -- about 100000 blocks -- 795 * only a 48-bit marker will do. NB: normal compression/ decompression 796 * donot rely on these statistical properties. They are only important 797 * when trying to recover blocks from damaged files. 798 */ 799 bsPutUByte(0x31); 800 bsPutUByte(0x41); 801 bsPutUByte(0x59); 802 bsPutUByte(0x26); 803 bsPutUByte(0x53); 804 bsPutUByte(0x59); 805 806 /* Now the block's CRC, so it is in a known place. */ 807 bsPutInt(this.blockCRC); 808 809 /* Now a single bit indicating randomisation. */ 810 if (this.blockRandomised) { 811 bsW(1, 1); 812 } else { 813 bsW(1, 0); 814 } 815 816 /* Finally, block's contents proper. */ 817 moveToFrontCodeAndSend(); 818 } 819 endCompression()820 private void endCompression() throws IOException { 821 /* 822 * Now another magic 48-bit number, 0x177245385090, to indicate the end 823 * of the last block. (sqrt(pi), if you want to know. I did want to use 824 * e, but it contains too much repetition -- 27 18 28 18 28 46 -- for me 825 * to feel statistically comfortable. Call me paranoid.) 826 */ 827 bsPutUByte(0x17); 828 bsPutUByte(0x72); 829 bsPutUByte(0x45); 830 bsPutUByte(0x38); 831 bsPutUByte(0x50); 832 bsPutUByte(0x90); 833 834 bsPutInt(this.combinedCRC); 835 bsFinishedWithStream(); 836 } 837 838 /** 839 * Returns the blocksize parameter specified at construction time. 840 */ getBlockSize()841 public final int getBlockSize() { 842 return this.blockSize100k; 843 } 844 write(final byte[] buf, int offs, final int len)845 public void write(final byte[] buf, int offs, final int len) 846 throws IOException { 847 if (offs < 0) { 848 throw new IndexOutOfBoundsException("offs(" + offs + ") < 0."); 849 } 850 if (len < 0) { 851 throw new IndexOutOfBoundsException("len(" + len + ") < 0."); 852 } 853 if (offs + len > buf.length) { 854 throw new IndexOutOfBoundsException("offs(" + offs + ") + len(" 855 + len + ") > buf.length(" + buf.length + ")."); 856 } 857 if (this.out == null) { 858 throw new IOException("stream closed"); 859 } 860 861 for (int hi = offs + len; offs < hi;) { 862 write0(buf[offs++]); 863 } 864 } 865 write0(int b)866 private void write0(int b) throws IOException { 867 if (this.currentChar != -1) { 868 b &= 0xff; 869 if (this.currentChar == b) { 870 if (++this.runLength > 254) { 871 writeRun(); 872 this.currentChar = -1; 873 this.runLength = 0; 874 } 875 // else nothing to do 876 } else { 877 writeRun(); 878 this.runLength = 1; 879 this.currentChar = b; 880 } 881 } else { 882 this.currentChar = b & 0xff; 883 this.runLength++; 884 } 885 } 886 hbAssignCodes(final int[] code, final byte[] length, final int minLen, final int maxLen, final int alphaSize)887 private static void hbAssignCodes(final int[] code, final byte[] length, 888 final int minLen, final int maxLen, final int alphaSize) { 889 int vec = 0; 890 for (int n = minLen; n <= maxLen; n++) { 891 for (int i = 0; i < alphaSize; i++) { 892 if ((length[i] & 0xff) == n) { 893 code[i] = vec; 894 vec++; 895 } 896 } 897 vec <<= 1; 898 } 899 } 900 bsFinishedWithStream()901 private void bsFinishedWithStream() throws IOException { 902 while (this.bsLive > 0) { 903 int ch = this.bsBuff >> 24; 904 this.out.write(ch); // write 8-bit 905 this.bsBuff <<= 8; 906 this.bsLive -= 8; 907 } 908 } 909 bsW(final int n, final int v)910 private void bsW(final int n, final int v) throws IOException { 911 final OutputStream outShadow = this.out; 912 int bsLiveShadow = this.bsLive; 913 int bsBuffShadow = this.bsBuff; 914 915 while (bsLiveShadow >= 8) { 916 outShadow.write(bsBuffShadow >> 24); // write 8-bit 917 bsBuffShadow <<= 8; 918 bsLiveShadow -= 8; 919 } 920 921 this.bsBuff = bsBuffShadow | (v << (32 - bsLiveShadow - n)); 922 this.bsLive = bsLiveShadow + n; 923 } 924 bsPutUByte(final int c)925 private void bsPutUByte(final int c) throws IOException { 926 bsW(8, c); 927 } 928 bsPutInt(final int u)929 private void bsPutInt(final int u) throws IOException { 930 bsW(8, (u >> 24) & 0xff); 931 bsW(8, (u >> 16) & 0xff); 932 bsW(8, (u >> 8) & 0xff); 933 bsW(8, u & 0xff); 934 } 935 sendMTFValues()936 private void sendMTFValues() throws IOException { 937 final byte[][] len = this.data.sendMTFValues_len; 938 final int alphaSize = this.nInUse + 2; 939 940 for (int t = N_GROUPS; --t >= 0;) { 941 byte[] len_t = len[t]; 942 for (int v = alphaSize; --v >= 0;) { 943 len_t[v] = GREATER_ICOST; 944 } 945 } 946 947 /* Decide how many coding tables to use */ 948 // assert (this.nMTF > 0) : this.nMTF; 949 final int nGroups = (this.nMTF < 200) ? 2 : (this.nMTF < 600) ? 3 950 : (this.nMTF < 1200) ? 4 : (this.nMTF < 2400) ? 5 : 6; 951 952 /* Generate an initial set of coding tables */ 953 sendMTFValues0(nGroups, alphaSize); 954 955 /* 956 * Iterate up to N_ITERS times to improve the tables. 957 */ 958 final int nSelectors = sendMTFValues1(nGroups, alphaSize); 959 960 /* Compute MTF values for the selectors. */ 961 sendMTFValues2(nGroups, nSelectors); 962 963 /* Assign actual codes for the tables. */ 964 sendMTFValues3(nGroups, alphaSize); 965 966 /* Transmit the mapping table. */ 967 sendMTFValues4(); 968 969 /* Now the selectors. */ 970 sendMTFValues5(nGroups, nSelectors); 971 972 /* Now the coding tables. */ 973 sendMTFValues6(nGroups, alphaSize); 974 975 /* And finally, the block data proper */ 976 sendMTFValues7(nSelectors); 977 } 978 sendMTFValues0(final int nGroups, final int alphaSize)979 private void sendMTFValues0(final int nGroups, final int alphaSize) { 980 final byte[][] len = this.data.sendMTFValues_len; 981 final int[] mtfFreq = this.data.mtfFreq; 982 983 int remF = this.nMTF; 984 int gs = 0; 985 986 for (int nPart = nGroups; nPart > 0; nPart--) { 987 final int tFreq = remF / nPart; 988 int ge = gs - 1; 989 int aFreq = 0; 990 991 for (final int a = alphaSize - 1; (aFreq < tFreq) && (ge < a);) { 992 aFreq += mtfFreq[++ge]; 993 } 994 995 if ((ge > gs) && (nPart != nGroups) && (nPart != 1) 996 && (((nGroups - nPart) & 1) != 0)) { 997 aFreq -= mtfFreq[ge--]; 998 } 999 1000 final byte[] len_np = len[nPart - 1]; 1001 for (int v = alphaSize; --v >= 0;) { 1002 if ((v >= gs) && (v <= ge)) { 1003 len_np[v] = LESSER_ICOST; 1004 } else { 1005 len_np[v] = GREATER_ICOST; 1006 } 1007 } 1008 1009 gs = ge + 1; 1010 remF -= aFreq; 1011 } 1012 } 1013 sendMTFValues1(final int nGroups, final int alphaSize)1014 private int sendMTFValues1(final int nGroups, final int alphaSize) { 1015 final Data dataShadow = this.data; 1016 final int[][] rfreq = dataShadow.sendMTFValues_rfreq; 1017 final int[] fave = dataShadow.sendMTFValues_fave; 1018 final short[] cost = dataShadow.sendMTFValues_cost; 1019 final char[] sfmap = dataShadow.sfmap; 1020 final byte[] selector = dataShadow.selector; 1021 final byte[][] len = dataShadow.sendMTFValues_len; 1022 final byte[] len_0 = len[0]; 1023 final byte[] len_1 = len[1]; 1024 final byte[] len_2 = len[2]; 1025 final byte[] len_3 = len[3]; 1026 final byte[] len_4 = len[4]; 1027 final byte[] len_5 = len[5]; 1028 final int nMTFShadow = this.nMTF; 1029 1030 int nSelectors = 0; 1031 1032 for (int iter = 0; iter < N_ITERS; iter++) { 1033 for (int t = nGroups; --t >= 0;) { 1034 fave[t] = 0; 1035 int[] rfreqt = rfreq[t]; 1036 for (int i = alphaSize; --i >= 0;) { 1037 rfreqt[i] = 0; 1038 } 1039 } 1040 1041 nSelectors = 0; 1042 1043 for (int gs = 0; gs < this.nMTF;) { 1044 /* Set group start & end marks. */ 1045 1046 /* 1047 * Calculate the cost of this group as coded by each of the 1048 * coding tables. 1049 */ 1050 1051 final int ge = Math.min(gs + G_SIZE - 1, nMTFShadow - 1); 1052 1053 if (nGroups == N_GROUPS) { 1054 // unrolled version of the else-block 1055 1056 short cost0 = 0; 1057 short cost1 = 0; 1058 short cost2 = 0; 1059 short cost3 = 0; 1060 short cost4 = 0; 1061 short cost5 = 0; 1062 1063 for (int i = gs; i <= ge; i++) { 1064 final int icv = sfmap[i]; 1065 cost0 += len_0[icv] & 0xff; 1066 cost1 += len_1[icv] & 0xff; 1067 cost2 += len_2[icv] & 0xff; 1068 cost3 += len_3[icv] & 0xff; 1069 cost4 += len_4[icv] & 0xff; 1070 cost5 += len_5[icv] & 0xff; 1071 } 1072 1073 cost[0] = cost0; 1074 cost[1] = cost1; 1075 cost[2] = cost2; 1076 cost[3] = cost3; 1077 cost[4] = cost4; 1078 cost[5] = cost5; 1079 1080 } else { 1081 for (int t = nGroups; --t >= 0;) { 1082 cost[t] = 0; 1083 } 1084 1085 for (int i = gs; i <= ge; i++) { 1086 final int icv = sfmap[i]; 1087 for (int t = nGroups; --t >= 0;) { 1088 cost[t] += len[t][icv] & 0xff; 1089 } 1090 } 1091 } 1092 1093 /* 1094 * Find the coding table which is best for this group, and 1095 * record its identity in the selector table. 1096 */ 1097 int bt = -1; 1098 for (int t = nGroups, bc = 999999999; --t >= 0;) { 1099 final int cost_t = cost[t]; 1100 if (cost_t < bc) { 1101 bc = cost_t; 1102 bt = t; 1103 } 1104 } 1105 1106 fave[bt]++; 1107 selector[nSelectors] = (byte) bt; 1108 nSelectors++; 1109 1110 /* 1111 * Increment the symbol frequencies for the selected table. 1112 */ 1113 final int[] rfreq_bt = rfreq[bt]; 1114 for (int i = gs; i <= ge; i++) { 1115 rfreq_bt[sfmap[i]]++; 1116 } 1117 1118 gs = ge + 1; 1119 } 1120 1121 /* 1122 * Recompute the tables based on the accumulated frequencies. 1123 */ 1124 for (int t = 0; t < nGroups; t++) { 1125 hbMakeCodeLengths(len[t], rfreq[t], this.data, alphaSize, 20); 1126 } 1127 } 1128 1129 return nSelectors; 1130 } 1131 sendMTFValues2(final int nGroups, final int nSelectors)1132 private void sendMTFValues2(final int nGroups, final int nSelectors) { 1133 // assert (nGroups < 8) : nGroups; 1134 1135 final Data dataShadow = this.data; 1136 byte[] pos = dataShadow.sendMTFValues2_pos; 1137 1138 for (int i = nGroups; --i >= 0;) { 1139 pos[i] = (byte) i; 1140 } 1141 1142 for (int i = 0; i < nSelectors; i++) { 1143 final byte ll_i = dataShadow.selector[i]; 1144 byte tmp = pos[0]; 1145 int j = 0; 1146 1147 while (ll_i != tmp) { 1148 j++; 1149 byte tmp2 = tmp; 1150 tmp = pos[j]; 1151 pos[j] = tmp2; 1152 } 1153 1154 pos[0] = tmp; 1155 dataShadow.selectorMtf[i] = (byte) j; 1156 } 1157 } 1158 sendMTFValues3(final int nGroups, final int alphaSize)1159 private void sendMTFValues3(final int nGroups, final int alphaSize) { 1160 int[][] code = this.data.sendMTFValues_code; 1161 byte[][] len = this.data.sendMTFValues_len; 1162 1163 for (int t = 0; t < nGroups; t++) { 1164 int minLen = 32; 1165 int maxLen = 0; 1166 final byte[] len_t = len[t]; 1167 for (int i = alphaSize; --i >= 0;) { 1168 final int l = len_t[i] & 0xff; 1169 if (l > maxLen) { 1170 maxLen = l; 1171 } 1172 if (l < minLen) { 1173 minLen = l; 1174 } 1175 } 1176 1177 // assert (maxLen <= 20) : maxLen; 1178 // assert (minLen >= 1) : minLen; 1179 1180 hbAssignCodes(code[t], len[t], minLen, maxLen, alphaSize); 1181 } 1182 } 1183 sendMTFValues4()1184 private void sendMTFValues4() throws IOException { 1185 final boolean[] inUse = this.data.inUse; 1186 final boolean[] inUse16 = this.data.sentMTFValues4_inUse16; 1187 1188 for (int i = 16; --i >= 0;) { 1189 inUse16[i] = false; 1190 final int i16 = i * 16; 1191 for (int j = 16; --j >= 0;) { 1192 if (inUse[i16 + j]) { 1193 inUse16[i] = true; 1194 } 1195 } 1196 } 1197 1198 for (int i = 0; i < 16; i++) { 1199 bsW(1, inUse16[i] ? 1 : 0); 1200 } 1201 1202 final OutputStream outShadow = this.out; 1203 int bsLiveShadow = this.bsLive; 1204 int bsBuffShadow = this.bsBuff; 1205 1206 for (int i = 0; i < 16; i++) { 1207 if (inUse16[i]) { 1208 final int i16 = i * 16; 1209 for (int j = 0; j < 16; j++) { 1210 // inlined: bsW(1, inUse[i16 + j] ? 1 : 0); 1211 while (bsLiveShadow >= 8) { 1212 outShadow.write(bsBuffShadow >> 24); // write 8-bit 1213 bsBuffShadow <<= 8; 1214 bsLiveShadow -= 8; 1215 } 1216 if (inUse[i16 + j]) { 1217 bsBuffShadow |= 1 << (32 - bsLiveShadow - 1); 1218 } 1219 bsLiveShadow++; 1220 } 1221 } 1222 } 1223 1224 this.bsBuff = bsBuffShadow; 1225 this.bsLive = bsLiveShadow; 1226 } 1227 sendMTFValues5(final int nGroups, final int nSelectors)1228 private void sendMTFValues5(final int nGroups, final int nSelectors) 1229 throws IOException { 1230 bsW(3, nGroups); 1231 bsW(15, nSelectors); 1232 1233 final OutputStream outShadow = this.out; 1234 final byte[] selectorMtf = this.data.selectorMtf; 1235 1236 int bsLiveShadow = this.bsLive; 1237 int bsBuffShadow = this.bsBuff; 1238 1239 for (int i = 0; i < nSelectors; i++) { 1240 for (int j = 0, hj = selectorMtf[i] & 0xff; j < hj; j++) { 1241 // inlined: bsW(1, 1); 1242 while (bsLiveShadow >= 8) { 1243 outShadow.write(bsBuffShadow >> 24); 1244 bsBuffShadow <<= 8; 1245 bsLiveShadow -= 8; 1246 } 1247 bsBuffShadow |= 1 << (32 - bsLiveShadow - 1); 1248 bsLiveShadow++; 1249 } 1250 1251 // inlined: bsW(1, 0); 1252 while (bsLiveShadow >= 8) { 1253 outShadow.write(bsBuffShadow >> 24); 1254 bsBuffShadow <<= 8; 1255 bsLiveShadow -= 8; 1256 } 1257 // bsBuffShadow |= 0 << (32 - bsLiveShadow - 1); 1258 bsLiveShadow++; 1259 } 1260 1261 this.bsBuff = bsBuffShadow; 1262 this.bsLive = bsLiveShadow; 1263 } 1264 sendMTFValues6(final int nGroups, final int alphaSize)1265 private void sendMTFValues6(final int nGroups, final int alphaSize) 1266 throws IOException { 1267 final byte[][] len = this.data.sendMTFValues_len; 1268 final OutputStream outShadow = this.out; 1269 1270 int bsLiveShadow = this.bsLive; 1271 int bsBuffShadow = this.bsBuff; 1272 1273 for (int t = 0; t < nGroups; t++) { 1274 byte[] len_t = len[t]; 1275 int curr = len_t[0] & 0xff; 1276 1277 // inlined: bsW(5, curr); 1278 while (bsLiveShadow >= 8) { 1279 outShadow.write(bsBuffShadow >> 24); // write 8-bit 1280 bsBuffShadow <<= 8; 1281 bsLiveShadow -= 8; 1282 } 1283 bsBuffShadow |= curr << (32 - bsLiveShadow - 5); 1284 bsLiveShadow += 5; 1285 1286 for (int i = 0; i < alphaSize; i++) { 1287 int lti = len_t[i] & 0xff; 1288 while (curr < lti) { 1289 // inlined: bsW(2, 2); 1290 while (bsLiveShadow >= 8) { 1291 outShadow.write(bsBuffShadow >> 24); // write 8-bit 1292 bsBuffShadow <<= 8; 1293 bsLiveShadow -= 8; 1294 } 1295 bsBuffShadow |= 2 << (32 - bsLiveShadow - 2); 1296 bsLiveShadow += 2; 1297 1298 curr++; /* 10 */ 1299 } 1300 1301 while (curr > lti) { 1302 // inlined: bsW(2, 3); 1303 while (bsLiveShadow >= 8) { 1304 outShadow.write(bsBuffShadow >> 24); // write 8-bit 1305 bsBuffShadow <<= 8; 1306 bsLiveShadow -= 8; 1307 } 1308 bsBuffShadow |= 3 << (32 - bsLiveShadow - 2); 1309 bsLiveShadow += 2; 1310 1311 curr--; /* 11 */ 1312 } 1313 1314 // inlined: bsW(1, 0); 1315 while (bsLiveShadow >= 8) { 1316 outShadow.write(bsBuffShadow >> 24); // write 8-bit 1317 bsBuffShadow <<= 8; 1318 bsLiveShadow -= 8; 1319 } 1320 // bsBuffShadow |= 0 << (32 - bsLiveShadow - 1); 1321 bsLiveShadow++; 1322 } 1323 } 1324 1325 this.bsBuff = bsBuffShadow; 1326 this.bsLive = bsLiveShadow; 1327 } 1328 sendMTFValues7(final int nSelectors)1329 private void sendMTFValues7(final int nSelectors) throws IOException { 1330 final Data dataShadow = this.data; 1331 final byte[][] len = dataShadow.sendMTFValues_len; 1332 final int[][] code = dataShadow.sendMTFValues_code; 1333 final OutputStream outShadow = this.out; 1334 final byte[] selector = dataShadow.selector; 1335 final char[] sfmap = dataShadow.sfmap; 1336 final int nMTFShadow = this.nMTF; 1337 1338 int selCtr = 0; 1339 1340 int bsLiveShadow = this.bsLive; 1341 int bsBuffShadow = this.bsBuff; 1342 1343 for (int gs = 0; gs < nMTFShadow;) { 1344 final int ge = Math.min(gs + G_SIZE - 1, nMTFShadow - 1); 1345 final int selector_selCtr = selector[selCtr] & 0xff; 1346 final int[] code_selCtr = code[selector_selCtr]; 1347 final byte[] len_selCtr = len[selector_selCtr]; 1348 1349 while (gs <= ge) { 1350 final int sfmap_i = sfmap[gs]; 1351 1352 // 1353 // inlined: bsW(len_selCtr[sfmap_i] & 0xff, 1354 // code_selCtr[sfmap_i]); 1355 // 1356 while (bsLiveShadow >= 8) { 1357 outShadow.write(bsBuffShadow >> 24); 1358 bsBuffShadow <<= 8; 1359 bsLiveShadow -= 8; 1360 } 1361 final int n = len_selCtr[sfmap_i] & 0xFF; 1362 bsBuffShadow |= code_selCtr[sfmap_i] << (32 - bsLiveShadow - n); 1363 bsLiveShadow += n; 1364 1365 gs++; 1366 } 1367 1368 gs = ge + 1; 1369 selCtr++; 1370 } 1371 1372 this.bsBuff = bsBuffShadow; 1373 this.bsLive = bsLiveShadow; 1374 } 1375 moveToFrontCodeAndSend()1376 private void moveToFrontCodeAndSend() throws IOException { 1377 bsW(24, this.origPtr); 1378 generateMTFValues(); 1379 sendMTFValues(); 1380 } 1381 1382 /** 1383 * This is the most hammered method of this class. 1384 * 1385 * <p> 1386 * This is the version using unrolled loops. Normally I never use such ones 1387 * in Java code. The unrolling has shown a noticable performance improvement 1388 * on JRE 1.4.2 (Linux i586 / HotSpot Client). Of course it depends on the 1389 * JIT compiler of the vm. 1390 * </p> 1391 */ mainSimpleSort(final Data dataShadow, final int lo, final int hi, final int d)1392 private boolean mainSimpleSort(final Data dataShadow, final int lo, 1393 final int hi, final int d) { 1394 final int bigN = hi - lo + 1; 1395 if (bigN < 2) { 1396 return this.firstAttempt && (this.workDone > this.workLimit); 1397 } 1398 1399 int hp = 0; 1400 while (INCS[hp] < bigN) { 1401 hp++; 1402 } 1403 1404 final int[] fmap = dataShadow.fmap; 1405 final char[] quadrant = dataShadow.quadrant; 1406 final byte[] block = dataShadow.block; 1407 final int lastShadow = this.last; 1408 final int lastPlus1 = lastShadow + 1; 1409 final boolean firstAttemptShadow = this.firstAttempt; 1410 final int workLimitShadow = this.workLimit; 1411 int workDoneShadow = this.workDone; 1412 1413 // Following block contains unrolled code which could be shortened by 1414 // coding it in additional loops. 1415 1416 HP: while (--hp >= 0) { 1417 final int h = INCS[hp]; 1418 final int mj = lo + h - 1; 1419 1420 for (int i = lo + h; i <= hi;) { 1421 // copy 1422 for (int k = 3; (i <= hi) && (--k >= 0); i++) { 1423 final int v = fmap[i]; 1424 final int vd = v + d; 1425 int j = i; 1426 1427 // for (int a; 1428 // (j > mj) && mainGtU((a = fmap[j - h]) + d, vd, 1429 // block, quadrant, lastShadow); 1430 // j -= h) { 1431 // fmap[j] = a; 1432 // } 1433 // 1434 // unrolled version: 1435 1436 // start inline mainGTU 1437 boolean onceRunned = false; 1438 int a = 0; 1439 1440 HAMMER: while (true) { 1441 if (onceRunned) { 1442 fmap[j] = a; 1443 if ((j -= h) <= mj) { 1444 break HAMMER; 1445 } 1446 } else { 1447 onceRunned = true; 1448 } 1449 1450 a = fmap[j - h]; 1451 int i1 = a + d; 1452 int i2 = vd; 1453 1454 // following could be done in a loop, but 1455 // unrolled it for performance: 1456 if (block[i1 + 1] == block[i2 + 1]) { 1457 if (block[i1 + 2] == block[i2 + 2]) { 1458 if (block[i1 + 3] == block[i2 + 3]) { 1459 if (block[i1 + 4] == block[i2 + 4]) { 1460 if (block[i1 + 5] == block[i2 + 5]) { 1461 if (block[(i1 += 6)] == block[(i2 += 6)]) { 1462 int x = lastShadow; 1463 X: while (x > 0) { 1464 x -= 4; 1465 1466 if (block[i1 + 1] == block[i2 + 1]) { 1467 if (quadrant[i1] == quadrant[i2]) { 1468 if (block[i1 + 2] == block[i2 + 2]) { 1469 if (quadrant[i1 + 1] == quadrant[i2 + 1]) { 1470 if (block[i1 + 3] == block[i2 + 3]) { 1471 if (quadrant[i1 + 2] == quadrant[i2 + 2]) { 1472 if (block[i1 + 4] == block[i2 + 4]) { 1473 if (quadrant[i1 + 3] == quadrant[i2 + 3]) { 1474 if ((i1 += 4) >= lastPlus1) { 1475 i1 -= lastPlus1; 1476 } 1477 if ((i2 += 4) >= lastPlus1) { 1478 i2 -= lastPlus1; 1479 } 1480 workDoneShadow++; 1481 continue X; 1482 } else if ((quadrant[i1 + 3] > quadrant[i2 + 3])) { 1483 continue HAMMER; 1484 } else { 1485 break HAMMER; 1486 } 1487 } else if ((block[i1 + 4] & 0xff) > (block[i2 + 4] & 0xff)) { 1488 continue HAMMER; 1489 } else { 1490 break HAMMER; 1491 } 1492 } else if ((quadrant[i1 + 2] > quadrant[i2 + 2])) { 1493 continue HAMMER; 1494 } else { 1495 break HAMMER; 1496 } 1497 } else if ((block[i1 + 3] & 0xff) > (block[i2 + 3] & 0xff)) { 1498 continue HAMMER; 1499 } else { 1500 break HAMMER; 1501 } 1502 } else if ((quadrant[i1 + 1] > quadrant[i2 + 1])) { 1503 continue HAMMER; 1504 } else { 1505 break HAMMER; 1506 } 1507 } else if ((block[i1 + 2] & 0xff) > (block[i2 + 2] & 0xff)) { 1508 continue HAMMER; 1509 } else { 1510 break HAMMER; 1511 } 1512 } else if ((quadrant[i1] > quadrant[i2])) { 1513 continue HAMMER; 1514 } else { 1515 break HAMMER; 1516 } 1517 } else if ((block[i1 + 1] & 0xff) > (block[i2 + 1] & 0xff)) { 1518 continue HAMMER; 1519 } else { 1520 break HAMMER; 1521 } 1522 1523 } 1524 break HAMMER; 1525 } // while x > 0 1526 else { 1527 if ((block[i1] & 0xff) > (block[i2] & 0xff)) { 1528 continue HAMMER; 1529 } else { 1530 break HAMMER; 1531 } 1532 } 1533 } else if ((block[i1 + 5] & 0xff) > (block[i2 + 5] & 0xff)) { 1534 continue HAMMER; 1535 } else { 1536 break HAMMER; 1537 } 1538 } else if ((block[i1 + 4] & 0xff) > (block[i2 + 4] & 0xff)) { 1539 continue HAMMER; 1540 } else { 1541 break HAMMER; 1542 } 1543 } else if ((block[i1 + 3] & 0xff) > (block[i2 + 3] & 0xff)) { 1544 continue HAMMER; 1545 } else { 1546 break HAMMER; 1547 } 1548 } else if ((block[i1 + 2] & 0xff) > (block[i2 + 2] & 0xff)) { 1549 continue HAMMER; 1550 } else { 1551 break HAMMER; 1552 } 1553 } else if ((block[i1 + 1] & 0xff) > (block[i2 + 1] & 0xff)) { 1554 continue HAMMER; 1555 } else { 1556 break HAMMER; 1557 } 1558 1559 } // HAMMER 1560 // end inline mainGTU 1561 1562 fmap[j] = v; 1563 } 1564 1565 if (firstAttemptShadow && (i <= hi) 1566 && (workDoneShadow > workLimitShadow)) { 1567 break HP; 1568 } 1569 } 1570 } 1571 1572 this.workDone = workDoneShadow; 1573 return firstAttemptShadow && (workDoneShadow > workLimitShadow); 1574 } 1575 vswap(int[] fmap, int p1, int p2, int n)1576 private static void vswap(int[] fmap, int p1, int p2, int n) { 1577 n += p1; 1578 while (p1 < n) { 1579 int t = fmap[p1]; 1580 fmap[p1++] = fmap[p2]; 1581 fmap[p2++] = t; 1582 } 1583 } 1584 med3(byte a, byte b, byte c)1585 private static byte med3(byte a, byte b, byte c) { 1586 return (a < b) ? (b < c ? b : a < c ? c : a) : (b > c ? b : a > c ? c 1587 : a); 1588 } 1589 blockSort()1590 private void blockSort() { 1591 this.workLimit = WORK_FACTOR * this.last; 1592 this.workDone = 0; 1593 this.blockRandomised = false; 1594 this.firstAttempt = true; 1595 mainSort(); 1596 1597 if (this.firstAttempt && (this.workDone > this.workLimit)) { 1598 randomiseBlock(); 1599 this.workLimit = this.workDone = 0; 1600 this.firstAttempt = false; 1601 mainSort(); 1602 } 1603 1604 int[] fmap = this.data.fmap; 1605 this.origPtr = -1; 1606 for (int i = 0, lastShadow = this.last; i <= lastShadow; i++) { 1607 if (fmap[i] == 0) { 1608 this.origPtr = i; 1609 break; 1610 } 1611 } 1612 1613 // assert (this.origPtr != -1) : this.origPtr; 1614 } 1615 1616 /** 1617 * Method "mainQSort3", file "blocksort.c", BZip2 1.0.2 1618 */ mainQSort3(final Data dataShadow, final int loSt, final int hiSt, final int dSt)1619 private void mainQSort3(final Data dataShadow, final int loSt, 1620 final int hiSt, final int dSt) { 1621 final int[] stack_ll = dataShadow.stack_ll; 1622 final int[] stack_hh = dataShadow.stack_hh; 1623 final int[] stack_dd = dataShadow.stack_dd; 1624 final int[] fmap = dataShadow.fmap; 1625 final byte[] block = dataShadow.block; 1626 1627 stack_ll[0] = loSt; 1628 stack_hh[0] = hiSt; 1629 stack_dd[0] = dSt; 1630 1631 for (int sp = 1; --sp >= 0;) { 1632 final int lo = stack_ll[sp]; 1633 final int hi = stack_hh[sp]; 1634 final int d = stack_dd[sp]; 1635 1636 if ((hi - lo < SMALL_THRESH) || (d > DEPTH_THRESH)) { 1637 if (mainSimpleSort(dataShadow, lo, hi, d)) { 1638 return; 1639 } 1640 } else { 1641 final int d1 = d + 1; 1642 final int med = med3(block[fmap[lo] + d1], 1643 block[fmap[hi] + d1], block[fmap[(lo + hi) >>> 1] + d1]) & 0xff; 1644 1645 int unLo = lo; 1646 int unHi = hi; 1647 int ltLo = lo; 1648 int gtHi = hi; 1649 1650 while (true) { 1651 while (unLo <= unHi) { 1652 final int n = ((int) block[fmap[unLo] + d1] & 0xff) 1653 - med; 1654 if (n == 0) { 1655 final int temp = fmap[unLo]; 1656 fmap[unLo++] = fmap[ltLo]; 1657 fmap[ltLo++] = temp; 1658 } else if (n < 0) { 1659 unLo++; 1660 } else { 1661 break; 1662 } 1663 } 1664 1665 while (unLo <= unHi) { 1666 final int n = ((int) block[fmap[unHi] + d1] & 0xff) 1667 - med; 1668 if (n == 0) { 1669 final int temp = fmap[unHi]; 1670 fmap[unHi--] = fmap[gtHi]; 1671 fmap[gtHi--] = temp; 1672 } else if (n > 0) { 1673 unHi--; 1674 } else { 1675 break; 1676 } 1677 } 1678 1679 if (unLo <= unHi) { 1680 final int temp = fmap[unLo]; 1681 fmap[unLo++] = fmap[unHi]; 1682 fmap[unHi--] = temp; 1683 } else { 1684 break; 1685 } 1686 } 1687 1688 if (gtHi < ltLo) { 1689 stack_ll[sp] = lo; 1690 stack_hh[sp] = hi; 1691 stack_dd[sp] = d1; 1692 sp++; 1693 } else { 1694 int n = ((ltLo - lo) < (unLo - ltLo)) ? (ltLo - lo) 1695 : (unLo - ltLo); 1696 vswap(fmap, lo, unLo - n, n); 1697 int m = ((hi - gtHi) < (gtHi - unHi)) ? (hi - gtHi) 1698 : (gtHi - unHi); 1699 vswap(fmap, unLo, hi - m + 1, m); 1700 1701 n = lo + unLo - ltLo - 1; 1702 m = hi - (gtHi - unHi) + 1; 1703 1704 stack_ll[sp] = lo; 1705 stack_hh[sp] = n; 1706 stack_dd[sp] = d; 1707 sp++; 1708 1709 stack_ll[sp] = n + 1; 1710 stack_hh[sp] = m - 1; 1711 stack_dd[sp] = d1; 1712 sp++; 1713 1714 stack_ll[sp] = m; 1715 stack_hh[sp] = hi; 1716 stack_dd[sp] = d; 1717 sp++; 1718 } 1719 } 1720 } 1721 } 1722 mainSort()1723 private void mainSort() { 1724 final Data dataShadow = this.data; 1725 final int[] runningOrder = dataShadow.mainSort_runningOrder; 1726 final int[] copy = dataShadow.mainSort_copy; 1727 final boolean[] bigDone = dataShadow.mainSort_bigDone; 1728 final int[] ftab = dataShadow.ftab; 1729 final byte[] block = dataShadow.block; 1730 final int[] fmap = dataShadow.fmap; 1731 final char[] quadrant = dataShadow.quadrant; 1732 final int lastShadow = this.last; 1733 final int workLimitShadow = this.workLimit; 1734 final boolean firstAttemptShadow = this.firstAttempt; 1735 1736 // Set up the 2-byte frequency table 1737 for (int i = 65537; --i >= 0;) { 1738 ftab[i] = 0; 1739 } 1740 1741 /* 1742 * In the various block-sized structures, live data runs from 0 to 1743 * last+NUM_OVERSHOOT_BYTES inclusive. First, set up the overshoot area 1744 * for block. 1745 */ 1746 for (int i = 0; i < NUM_OVERSHOOT_BYTES; i++) { 1747 block[lastShadow + i + 2] = block[(i % (lastShadow + 1)) + 1]; 1748 } 1749 for (int i = lastShadow + NUM_OVERSHOOT_BYTES +1; --i >= 0;) { 1750 quadrant[i] = 0; 1751 } 1752 block[0] = block[lastShadow + 1]; 1753 1754 // Complete the initial radix sort: 1755 1756 int c1 = block[0] & 0xff; 1757 for (int i = 0; i <= lastShadow; i++) { 1758 final int c2 = block[i + 1] & 0xff; 1759 ftab[(c1 << 8) + c2]++; 1760 c1 = c2; 1761 } 1762 1763 for (int i = 1; i <= 65536; i++) 1764 ftab[i] += ftab[i - 1]; 1765 1766 c1 = block[1] & 0xff; 1767 for (int i = 0; i < lastShadow; i++) { 1768 final int c2 = block[i + 2] & 0xff; 1769 fmap[--ftab[(c1 << 8) + c2]] = i; 1770 c1 = c2; 1771 } 1772 1773 fmap[--ftab[((block[lastShadow + 1] & 0xff) << 8) + (block[1] & 0xff)]] = lastShadow; 1774 1775 /* 1776 * Now ftab contains the first loc of every small bucket. Calculate the 1777 * running order, from smallest to largest big bucket. 1778 */ 1779 for (int i = 256; --i >= 0;) { 1780 bigDone[i] = false; 1781 runningOrder[i] = i; 1782 } 1783 1784 for (int h = 364; h != 1;) { 1785 h /= 3; 1786 for (int i = h; i <= 255; i++) { 1787 final int vv = runningOrder[i]; 1788 final int a = ftab[(vv + 1) << 8] - ftab[vv << 8]; 1789 final int b = h - 1; 1790 int j = i; 1791 for (int ro = runningOrder[j - h]; (ftab[(ro + 1) << 8] - ftab[ro << 8]) > a; ro = runningOrder[j 1792 - h]) { 1793 runningOrder[j] = ro; 1794 j -= h; 1795 if (j <= b) { 1796 break; 1797 } 1798 } 1799 runningOrder[j] = vv; 1800 } 1801 } 1802 1803 /* 1804 * The main sorting loop. 1805 */ 1806 for (int i = 0; i <= 255; i++) { 1807 /* 1808 * Process big buckets, starting with the least full. 1809 */ 1810 final int ss = runningOrder[i]; 1811 1812 // Step 1: 1813 /* 1814 * Complete the big bucket [ss] by quicksorting any unsorted small 1815 * buckets [ss, j]. Hopefully previous pointer-scanning phases have 1816 * already completed many of the small buckets [ss, j], so we don't 1817 * have to sort them at all. 1818 */ 1819 for (int j = 0; j <= 255; j++) { 1820 final int sb = (ss << 8) + j; 1821 final int ftab_sb = ftab[sb]; 1822 if ((ftab_sb & SETMASK) != SETMASK) { 1823 final int lo = ftab_sb & CLEARMASK; 1824 final int hi = (ftab[sb + 1] & CLEARMASK) - 1; 1825 if (hi > lo) { 1826 mainQSort3(dataShadow, lo, hi, 2); 1827 if (firstAttemptShadow 1828 && (this.workDone > workLimitShadow)) { 1829 return; 1830 } 1831 } 1832 ftab[sb] = ftab_sb | SETMASK; 1833 } 1834 } 1835 1836 // Step 2: 1837 // Now scan this big bucket so as to synthesise the 1838 // sorted order for small buckets [t, ss] for all t != ss. 1839 1840 for (int j = 0; j <= 255; j++) { 1841 copy[j] = ftab[(j << 8) + ss] & CLEARMASK; 1842 } 1843 1844 for (int j = ftab[ss << 8] & CLEARMASK, hj = (ftab[(ss + 1) << 8] & CLEARMASK); j < hj; j++) { 1845 final int fmap_j = fmap[j]; 1846 c1 = block[fmap_j] & 0xff; 1847 if (!bigDone[c1]) { 1848 fmap[copy[c1]] = (fmap_j == 0) ? lastShadow : (fmap_j - 1); 1849 copy[c1]++; 1850 } 1851 } 1852 1853 for (int j = 256; --j >= 0;) 1854 ftab[(j << 8) + ss] |= SETMASK; 1855 1856 // Step 3: 1857 /* 1858 * The ss big bucket is now done. Record this fact, and update the 1859 * quadrant descriptors. Remember to update quadrants in the 1860 * overshoot area too, if necessary. The "if (i < 255)" test merely 1861 * skips this updating for the last bucket processed, since updating 1862 * for the last bucket is pointless. 1863 */ 1864 bigDone[ss] = true; 1865 1866 if (i < 255) { 1867 final int bbStart = ftab[ss << 8] & CLEARMASK; 1868 final int bbSize = (ftab[(ss + 1) << 8] & CLEARMASK) - bbStart; 1869 int shifts = 0; 1870 1871 while ((bbSize >> shifts) > 65534) { 1872 shifts++; 1873 } 1874 1875 for (int j = 0; j < bbSize; j++) { 1876 final int a2update = fmap[bbStart + j]; 1877 final char qVal = (char) (j >> shifts); 1878 quadrant[a2update] = qVal; 1879 if (a2update < NUM_OVERSHOOT_BYTES) { 1880 quadrant[a2update + lastShadow + 1] = qVal; 1881 } 1882 } 1883 } 1884 1885 } 1886 } 1887 randomiseBlock()1888 private void randomiseBlock() { 1889 final boolean[] inUse = this.data.inUse; 1890 final byte[] block = this.data.block; 1891 final int lastShadow = this.last; 1892 1893 for (int i = 256; --i >= 0;) 1894 inUse[i] = false; 1895 1896 int rNToGo = 0; 1897 int rTPos = 0; 1898 for (int i = 0, j = 1; i <= lastShadow; i = j, j++) { 1899 if (rNToGo == 0) { 1900 rNToGo = (char) BZip2Constants.rNums[rTPos]; 1901 if (++rTPos == 512) { 1902 rTPos = 0; 1903 } 1904 } 1905 1906 rNToGo--; 1907 block[j] ^= ((rNToGo == 1) ? 1 : 0); 1908 1909 // handle 16 bit signed numbers 1910 inUse[block[j] & 0xff] = true; 1911 } 1912 1913 this.blockRandomised = true; 1914 } 1915 generateMTFValues()1916 private void generateMTFValues() { 1917 final int lastShadow = this.last; 1918 final Data dataShadow = this.data; 1919 final boolean[] inUse = dataShadow.inUse; 1920 final byte[] block = dataShadow.block; 1921 final int[] fmap = dataShadow.fmap; 1922 final char[] sfmap = dataShadow.sfmap; 1923 final int[] mtfFreq = dataShadow.mtfFreq; 1924 final byte[] unseqToSeq = dataShadow.unseqToSeq; 1925 final byte[] yy = dataShadow.generateMTFValues_yy; 1926 1927 // make maps 1928 int nInUseShadow = 0; 1929 for (int i = 0; i < 256; i++) { 1930 if (inUse[i]) { 1931 unseqToSeq[i] = (byte) nInUseShadow; 1932 nInUseShadow++; 1933 } 1934 } 1935 this.nInUse = nInUseShadow; 1936 1937 final int eob = nInUseShadow + 1; 1938 1939 for (int i = eob; i >= 0; i--) { 1940 mtfFreq[i] = 0; 1941 } 1942 1943 for (int i = nInUseShadow; --i >= 0;) { 1944 yy[i] = (byte) i; 1945 } 1946 1947 int wr = 0; 1948 int zPend = 0; 1949 1950 for (int i = 0; i <= lastShadow; i++) { 1951 final byte ll_i = unseqToSeq[block[fmap[i]] & 0xff]; 1952 byte tmp = yy[0]; 1953 int j = 0; 1954 1955 while (ll_i != tmp) { 1956 j++; 1957 byte tmp2 = tmp; 1958 tmp = yy[j]; 1959 yy[j] = tmp2; 1960 } 1961 yy[0] = tmp; 1962 1963 if (j == 0) { 1964 zPend++; 1965 } else { 1966 if (zPend > 0) { 1967 zPend--; 1968 while (true) { 1969 if ((zPend & 1) == 0) { 1970 sfmap[wr] = RUNA; 1971 wr++; 1972 mtfFreq[RUNA]++; 1973 } else { 1974 sfmap[wr] = RUNB; 1975 wr++; 1976 mtfFreq[RUNB]++; 1977 } 1978 1979 if (zPend >= 2) { 1980 zPend = (zPend - 2) >> 1; 1981 } else { 1982 break; 1983 } 1984 } 1985 zPend = 0; 1986 } 1987 sfmap[wr] = (char) (j + 1); 1988 wr++; 1989 mtfFreq[j + 1]++; 1990 } 1991 } 1992 1993 if (zPend > 0) { 1994 zPend--; 1995 while (true) { 1996 if ((zPend & 1) == 0) { 1997 sfmap[wr] = RUNA; 1998 wr++; 1999 mtfFreq[RUNA]++; 2000 } else { 2001 sfmap[wr] = RUNB; 2002 wr++; 2003 mtfFreq[RUNB]++; 2004 } 2005 2006 if (zPend >= 2) { 2007 zPend = (zPend - 2) >> 1; 2008 } else { 2009 break; 2010 } 2011 } 2012 } 2013 2014 sfmap[wr] = (char) eob; 2015 mtfFreq[eob]++; 2016 this.nMTF = wr + 1; 2017 } 2018 2019 private static final class Data extends Object { 2020 2021 // with blockSize 900k 2022 final boolean[] inUse = new boolean[256]; // 256 byte 2023 final byte[] unseqToSeq = new byte[256]; // 256 byte 2024 final int[] mtfFreq = new int[MAX_ALPHA_SIZE]; // 1032 byte 2025 final byte[] selector = new byte[MAX_SELECTORS]; // 18002 byte 2026 final byte[] selectorMtf = new byte[MAX_SELECTORS]; // 18002 byte 2027 2028 final byte[] generateMTFValues_yy = new byte[256]; // 256 byte 2029 final byte[][] sendMTFValues_len = new byte[N_GROUPS][MAX_ALPHA_SIZE]; // 1548 2030 // byte 2031 final int[][] sendMTFValues_rfreq = new int[N_GROUPS][MAX_ALPHA_SIZE]; // 6192 2032 // byte 2033 final int[] sendMTFValues_fave = new int[N_GROUPS]; // 24 byte 2034 final short[] sendMTFValues_cost = new short[N_GROUPS]; // 12 byte 2035 final int[][] sendMTFValues_code = new int[N_GROUPS][MAX_ALPHA_SIZE]; // 6192 2036 // byte 2037 final byte[] sendMTFValues2_pos = new byte[N_GROUPS]; // 6 byte 2038 final boolean[] sentMTFValues4_inUse16 = new boolean[16]; // 16 byte 2039 2040 final int[] stack_ll = new int[QSORT_STACK_SIZE]; // 4000 byte 2041 final int[] stack_hh = new int[QSORT_STACK_SIZE]; // 4000 byte 2042 final int[] stack_dd = new int[QSORT_STACK_SIZE]; // 4000 byte 2043 2044 final int[] mainSort_runningOrder = new int[256]; // 1024 byte 2045 final int[] mainSort_copy = new int[256]; // 1024 byte 2046 final boolean[] mainSort_bigDone = new boolean[256]; // 256 byte 2047 2048 final int[] heap = new int[MAX_ALPHA_SIZE + 2]; // 1040 byte 2049 final int[] weight = new int[MAX_ALPHA_SIZE * 2]; // 2064 byte 2050 final int[] parent = new int[MAX_ALPHA_SIZE * 2]; // 2064 byte 2051 2052 final int[] ftab = new int[65537]; // 262148 byte 2053 // ------------ 2054 // 333408 byte 2055 2056 final byte[] block; // 900021 byte 2057 final int[] fmap; // 3600000 byte 2058 final char[] sfmap; // 3600000 byte 2059 // ------------ 2060 // 8433529 byte 2061 // ============ 2062 2063 /** 2064 * Array instance identical to sfmap, both are used only temporarily and 2065 * indepently, so we do not need to allocate additional memory. 2066 */ 2067 final char[] quadrant; 2068 Data(int blockSize100k)2069 Data(int blockSize100k) { 2070 super(); 2071 2072 final int n = blockSize100k * BZip2Constants.baseBlockSize; 2073 this.block = new byte[(n + 1 + NUM_OVERSHOOT_BYTES)]; 2074 this.fmap = new int[n]; 2075 this.sfmap = new char[2 * n]; 2076 this.quadrant = this.sfmap; 2077 } 2078 2079 } 2080 2081 } 2082