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