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 public void write(final int b) throws IOException { 435 if (this.out != null) { 436 write0(b); 437 } else { 438 throw new IOException("closed"); 439 } 440 } 441 442 private void writeRun() throws IOException { 443 final int lastShadow = this.last; 444 445 if (lastShadow < this.allowableBlockSize) { 446 final int currentCharShadow = this.currentChar; 447 final Data dataShadow = this.data; 448 dataShadow.inUse[currentCharShadow] = true; 449 final byte ch = (byte) currentCharShadow; 450 451 int runLengthShadow = this.runLength; 452 this.crc.updateCRC(currentCharShadow, runLengthShadow); 453 454 switch (runLengthShadow) { 455 case 1: 456 dataShadow.block[lastShadow + 2] = ch; 457 this.last = lastShadow + 1; 458 break; 459 460 case 2: 461 dataShadow.block[lastShadow + 2] = ch; 462 dataShadow.block[lastShadow + 3] = ch; 463 this.last = lastShadow + 2; 464 break; 465 466 case 3: { 467 final byte[] block = dataShadow.block; 468 block[lastShadow + 2] = ch; 469 block[lastShadow + 3] = ch; 470 block[lastShadow + 4] = ch; 471 this.last = lastShadow + 3; 472 } 473 break; 474 475 default: { 476 runLengthShadow -= 4; 477 dataShadow.inUse[runLengthShadow] = true; 478 final byte[] block = dataShadow.block; 479 block[lastShadow + 2] = ch; 480 block[lastShadow + 3] = ch; 481 block[lastShadow + 4] = ch; 482 block[lastShadow + 5] = ch; 483 block[lastShadow + 6] = (byte) runLengthShadow; 484 this.last = lastShadow + 5; 485 } 486 break; 487 488 } 489 } else { 490 endBlock(); 491 initBlock(); 492 writeRun(); 493 } 494 } 495 496 /** 497 * Overriden to close the stream. 498 */ 499 protected void finalize() throws Throwable { 500 finish(); 501 super.finalize(); 502 } 503 504 505 public void finish() throws IOException { 506 if (out != null) { 507 try { 508 if (this.runLength > 0) { 509 writeRun(); 510 } 511 this.currentChar = -1; 512 endBlock(); 513 endCompression(); 514 } finally { 515 this.out = null; 516 this.data = null; 517 } 518 } 519 } 520 521 public void close() throws IOException { 522 if (out != null) { 523 OutputStream outShadow = this.out; 524 finish(); 525 outShadow.close(); 526 } 527 } 528 529 public void flush() throws IOException { 530 OutputStream outShadow = this.out; 531 if (outShadow != null) { 532 outShadow.flush(); 533 } 534 } 535 536 /** 537 * Writes magic bytes like BZ on the first position of the stream 538 * and bytes indiciating the file-format, which is 539 * huffmanised, followed by a digit indicating blockSize100k. 540 * @throws IOException if the magic bytes could not been written 541 */ 542 private void init() throws IOException { 543 bsPutUByte('B'); 544 bsPutUByte('Z'); 545 546 this.data = new Data(this.blockSize100k); 547 548 // huffmanised magic bytes 549 bsPutUByte('h'); 550 bsPutUByte('0' + this.blockSize100k); 551 552 this.combinedCRC = 0; 553 initBlock(); 554 } 555 556 private void initBlock() { 557 // blockNo++; 558 this.crc.initialiseCRC(); 559 this.last = -1; 560 // ch = 0; 561 562 boolean[] inUse = this.data.inUse; 563 for (int i = 256; --i >= 0;) { 564 inUse[i] = false; 565 } 566 567 /* 20 is just a paranoia constant */ 568 this.allowableBlockSize = (this.blockSize100k * BZip2Constants.BASEBLOCKSIZE) - 20; 569 } 570 571 private void endBlock() throws IOException { 572 this.blockCRC = this.crc.getFinalCRC(); 573 this.combinedCRC = (this.combinedCRC << 1) | (this.combinedCRC >>> 31); 574 this.combinedCRC ^= this.blockCRC; 575 576 // empty block at end of file 577 if (this.last == -1) { 578 return; 579 } 580 581 /* sort the block and establish posn of original string */ 582 blockSort(); 583 584 /* 585 * A 6-byte block header, the value chosen arbitrarily as 0x314159265359 586 * :-). A 32 bit value does not really give a strong enough guarantee 587 * that the value will not appear by chance in the compressed 588 * datastream. Worst-case probability of this event, for a 900k block, 589 * is about 2.0e-3 for 32 bits, 1.0e-5 for 40 bits and 4.0e-8 for 48 590 * bits. For a compressed file of size 100Gb -- about 100000 blocks -- 591 * only a 48-bit marker will do. NB: normal compression/ decompression 592 * donot rely on these statistical properties. They are only important 593 * when trying to recover blocks from damaged files. 594 */ 595 bsPutUByte(0x31); 596 bsPutUByte(0x41); 597 bsPutUByte(0x59); 598 bsPutUByte(0x26); 599 bsPutUByte(0x53); 600 bsPutUByte(0x59); 601 602 /* Now the block's CRC, so it is in a known place. */ 603 bsPutInt(this.blockCRC); 604 605 /* Now a single bit indicating randomisation. */ 606 if (this.blockRandomised) { 607 bsW(1, 1); 608 } else { 609 bsW(1, 0); 610 } 611 612 /* Finally, block's contents proper. */ 613 moveToFrontCodeAndSend(); 614 } 615 616 private void endCompression() throws IOException { 617 /* 618 * Now another magic 48-bit number, 0x177245385090, to indicate the end 619 * of the last block. (sqrt(pi), if you want to know. I did want to use 620 * e, but it contains too much repetition -- 27 18 28 18 28 46 -- for me 621 * to feel statistically comfortable. Call me paranoid.) 622 */ 623 bsPutUByte(0x17); 624 bsPutUByte(0x72); 625 bsPutUByte(0x45); 626 bsPutUByte(0x38); 627 bsPutUByte(0x50); 628 bsPutUByte(0x90); 629 630 bsPutInt(this.combinedCRC); 631 bsFinishedWithStream(); 632 } 633 634 /** 635 * Returns the blocksize parameter specified at construction time. 636 */ 637 public final int getBlockSize() { 638 return this.blockSize100k; 639 } 640 641 public void write(final byte[] buf, int offs, final int len) 642 throws IOException { 643 if (offs < 0) { 644 throw new IndexOutOfBoundsException("offs(" + offs + ") < 0."); 645 } 646 if (len < 0) { 647 throw new IndexOutOfBoundsException("len(" + len + ") < 0."); 648 } 649 if (offs + len > buf.length) { 650 throw new IndexOutOfBoundsException("offs(" + offs + ") + len(" 651 + len + ") > buf.length(" 652 + buf.length + ")."); 653 } 654 if (this.out == null) { 655 throw new IOException("stream closed"); 656 } 657 658 for (int hi = offs + len; offs < hi;) { 659 write0(buf[offs++]); 660 } 661 } 662 663 private void write0(int b) throws IOException { 664 if (this.currentChar != -1) { 665 b &= 0xff; 666 if (this.currentChar == b) { 667 if (++this.runLength > 254) { 668 writeRun(); 669 this.currentChar = -1; 670 this.runLength = 0; 671 } 672 // else nothing to do 673 } else { 674 writeRun(); 675 this.runLength = 1; 676 this.currentChar = b; 677 } 678 } else { 679 this.currentChar = b & 0xff; 680 this.runLength++; 681 } 682 } 683 684 private static void hbAssignCodes(final int[] code, final byte[] length, 685 final int minLen, final int maxLen, 686 final int alphaSize) { 687 int vec = 0; 688 for (int n = minLen; n <= maxLen; n++) { 689 for (int i = 0; i < alphaSize; i++) { 690 if ((length[i] & 0xff) == n) { 691 code[i] = vec; 692 vec++; 693 } 694 } 695 vec <<= 1; 696 } 697 } 698 699 private void bsFinishedWithStream() throws IOException { 700 while (this.bsLive > 0) { 701 int ch = this.bsBuff >> 24; 702 this.out.write(ch); // write 8-bit 703 this.bsBuff <<= 8; 704 this.bsLive -= 8; 705 } 706 } 707 708 private void bsW(final int n, final int v) throws IOException { 709 final OutputStream outShadow = this.out; 710 int bsLiveShadow = this.bsLive; 711 int bsBuffShadow = this.bsBuff; 712 713 while (bsLiveShadow >= 8) { 714 outShadow.write(bsBuffShadow >> 24); // write 8-bit 715 bsBuffShadow <<= 8; 716 bsLiveShadow -= 8; 717 } 718 719 this.bsBuff = bsBuffShadow | (v << (32 - bsLiveShadow - n)); 720 this.bsLive = bsLiveShadow + n; 721 } 722 723 private void bsPutUByte(final int c) throws IOException { 724 bsW(8, c); 725 } 726 727 private void bsPutInt(final int u) throws IOException { 728 bsW(8, (u >> 24) & 0xff); 729 bsW(8, (u >> 16) & 0xff); 730 bsW(8, (u >> 8) & 0xff); 731 bsW(8, u & 0xff); 732 } 733 734 private void sendMTFValues() throws IOException { 735 final byte[][] len = this.data.sendMTFValues_len; 736 final int alphaSize = this.nInUse + 2; 737 738 for (int t = N_GROUPS; --t >= 0;) { 739 byte[] len_t = len[t]; 740 for (int v = alphaSize; --v >= 0;) { 741 len_t[v] = GREATER_ICOST; 742 } 743 } 744 745 /* Decide how many coding tables to use */ 746 // assert (this.nMTF > 0) : this.nMTF; 747 final int nGroups = (this.nMTF < 200) ? 2 : (this.nMTF < 600) ? 3 748 : (this.nMTF < 1200) ? 4 : (this.nMTF < 2400) ? 5 : 6; 749 750 /* Generate an initial set of coding tables */ 751 sendMTFValues0(nGroups, alphaSize); 752 753 /* 754 * Iterate up to N_ITERS times to improve the tables. 755 */ 756 final int nSelectors = sendMTFValues1(nGroups, alphaSize); 757 758 /* Compute MTF values for the selectors. */ 759 sendMTFValues2(nGroups, nSelectors); 760 761 /* Assign actual codes for the tables. */ 762 sendMTFValues3(nGroups, alphaSize); 763 764 /* Transmit the mapping table. */ 765 sendMTFValues4(); 766 767 /* Now the selectors. */ 768 sendMTFValues5(nGroups, nSelectors); 769 770 /* Now the coding tables. */ 771 sendMTFValues6(nGroups, alphaSize); 772 773 /* And finally, the block data proper */ 774 sendMTFValues7(nSelectors); 775 } 776 777 private void sendMTFValues0(final int nGroups, final int alphaSize) { 778 final byte[][] len = this.data.sendMTFValues_len; 779 final int[] mtfFreq = this.data.mtfFreq; 780 781 int remF = this.nMTF; 782 int gs = 0; 783 784 for (int nPart = nGroups; nPart > 0; nPart--) { 785 final int tFreq = remF / nPart; 786 int ge = gs - 1; 787 int aFreq = 0; 788 789 for (final int a = alphaSize - 1; (aFreq < tFreq) && (ge < a);) { 790 aFreq += mtfFreq[++ge]; 791 } 792 793 if ((ge > gs) && (nPart != nGroups) && (nPart != 1) 794 && (((nGroups - nPart) & 1) != 0)) { 795 aFreq -= mtfFreq[ge--]; 796 } 797 798 final byte[] len_np = len[nPart - 1]; 799 for (int v = alphaSize; --v >= 0;) { 800 if ((v >= gs) && (v <= ge)) { 801 len_np[v] = LESSER_ICOST; 802 } else { 803 len_np[v] = GREATER_ICOST; 804 } 805 } 806 807 gs = ge + 1; 808 remF -= aFreq; 809 } 810 } 811 812 private int sendMTFValues1(final int nGroups, final int alphaSize) { 813 final Data dataShadow = this.data; 814 final int[][] rfreq = dataShadow.sendMTFValues_rfreq; 815 final int[] fave = dataShadow.sendMTFValues_fave; 816 final short[] cost = dataShadow.sendMTFValues_cost; 817 final char[] sfmap = dataShadow.sfmap; 818 final byte[] selector = dataShadow.selector; 819 final byte[][] len = dataShadow.sendMTFValues_len; 820 final byte[] len_0 = len[0]; 821 final byte[] len_1 = len[1]; 822 final byte[] len_2 = len[2]; 823 final byte[] len_3 = len[3]; 824 final byte[] len_4 = len[4]; 825 final byte[] len_5 = len[5]; 826 final int nMTFShadow = this.nMTF; 827 828 int nSelectors = 0; 829 830 for (int iter = 0; iter < N_ITERS; iter++) { 831 for (int t = nGroups; --t >= 0;) { 832 fave[t] = 0; 833 int[] rfreqt = rfreq[t]; 834 for (int i = alphaSize; --i >= 0;) { 835 rfreqt[i] = 0; 836 } 837 } 838 839 nSelectors = 0; 840 841 for (int gs = 0; gs < this.nMTF;) { 842 /* Set group start & end marks. */ 843 844 /* 845 * Calculate the cost of this group as coded by each of the 846 * coding tables. 847 */ 848 849 final int ge = Math.min(gs + G_SIZE - 1, nMTFShadow - 1); 850 851 if (nGroups == N_GROUPS) { 852 // unrolled version of the else-block 853 854 short cost0 = 0; 855 short cost1 = 0; 856 short cost2 = 0; 857 short cost3 = 0; 858 short cost4 = 0; 859 short cost5 = 0; 860 861 for (int i = gs; i <= ge; i++) { 862 final int icv = sfmap[i]; 863 cost0 += len_0[icv] & 0xff; 864 cost1 += len_1[icv] & 0xff; 865 cost2 += len_2[icv] & 0xff; 866 cost3 += len_3[icv] & 0xff; 867 cost4 += len_4[icv] & 0xff; 868 cost5 += len_5[icv] & 0xff; 869 } 870 871 cost[0] = cost0; 872 cost[1] = cost1; 873 cost[2] = cost2; 874 cost[3] = cost3; 875 cost[4] = cost4; 876 cost[5] = cost5; 877 878 } else { 879 for (int t = nGroups; --t >= 0;) { 880 cost[t] = 0; 881 } 882 883 for (int i = gs; i <= ge; i++) { 884 final int icv = sfmap[i]; 885 for (int t = nGroups; --t >= 0;) { 886 cost[t] += len[t][icv] & 0xff; 887 } 888 } 889 } 890 891 /* 892 * Find the coding table which is best for this group, and 893 * record its identity in the selector table. 894 */ 895 int bt = -1; 896 for (int t = nGroups, bc = 999999999; --t >= 0;) { 897 final int cost_t = cost[t]; 898 if (cost_t < bc) { 899 bc = cost_t; 900 bt = t; 901 } 902 } 903 904 fave[bt]++; 905 selector[nSelectors] = (byte) bt; 906 nSelectors++; 907 908 /* 909 * Increment the symbol frequencies for the selected table. 910 */ 911 final int[] rfreq_bt = rfreq[bt]; 912 for (int i = gs; i <= ge; i++) { 913 rfreq_bt[sfmap[i]]++; 914 } 915 916 gs = ge + 1; 917 } 918 919 /* 920 * Recompute the tables based on the accumulated frequencies. 921 */ 922 for (int t = 0; t < nGroups; t++) { 923 hbMakeCodeLengths(len[t], rfreq[t], this.data, alphaSize, 20); 924 } 925 } 926 927 return nSelectors; 928 } 929 930 private void sendMTFValues2(final int nGroups, final int nSelectors) { 931 // assert (nGroups < 8) : nGroups; 932 933 final Data dataShadow = this.data; 934 byte[] pos = dataShadow.sendMTFValues2_pos; 935 936 for (int i = nGroups; --i >= 0;) { 937 pos[i] = (byte) i; 938 } 939 940 for (int i = 0; i < nSelectors; i++) { 941 final byte ll_i = dataShadow.selector[i]; 942 byte tmp = pos[0]; 943 int j = 0; 944 945 while (ll_i != tmp) { 946 j++; 947 byte tmp2 = tmp; 948 tmp = pos[j]; 949 pos[j] = tmp2; 950 } 951 952 pos[0] = tmp; 953 dataShadow.selectorMtf[i] = (byte) j; 954 } 955 } 956 957 private void sendMTFValues3(final int nGroups, final int alphaSize) { 958 int[][] code = this.data.sendMTFValues_code; 959 byte[][] len = this.data.sendMTFValues_len; 960 961 for (int t = 0; t < nGroups; t++) { 962 int minLen = 32; 963 int maxLen = 0; 964 final byte[] len_t = len[t]; 965 for (int i = alphaSize; --i >= 0;) { 966 final int l = len_t[i] & 0xff; 967 if (l > maxLen) { 968 maxLen = l; 969 } 970 if (l < minLen) { 971 minLen = l; 972 } 973 } 974 975 // assert (maxLen <= 20) : maxLen; 976 // assert (minLen >= 1) : minLen; 977 978 hbAssignCodes(code[t], len[t], minLen, maxLen, alphaSize); 979 } 980 } 981 982 private void sendMTFValues4() throws IOException { 983 final boolean[] inUse = this.data.inUse; 984 final boolean[] inUse16 = this.data.sentMTFValues4_inUse16; 985 986 for (int i = 16; --i >= 0;) { 987 inUse16[i] = false; 988 final int i16 = i * 16; 989 for (int j = 16; --j >= 0;) { 990 if (inUse[i16 + j]) { 991 inUse16[i] = true; 992 } 993 } 994 } 995 996 for (int i = 0; i < 16; i++) { 997 bsW(1, inUse16[i] ? 1 : 0); 998 } 999 1000 final OutputStream outShadow = this.out; 1001 int bsLiveShadow = this.bsLive; 1002 int bsBuffShadow = this.bsBuff; 1003 1004 for (int i = 0; i < 16; i++) { 1005 if (inUse16[i]) { 1006 final int i16 = i * 16; 1007 for (int j = 0; j < 16; j++) { 1008 // inlined: bsW(1, inUse[i16 + j] ? 1 : 0); 1009 while (bsLiveShadow >= 8) { 1010 outShadow.write(bsBuffShadow >> 24); // write 8-bit 1011 bsBuffShadow <<= 8; 1012 bsLiveShadow -= 8; 1013 } 1014 if (inUse[i16 + j]) { 1015 bsBuffShadow |= 1 << (32 - bsLiveShadow - 1); 1016 } 1017 bsLiveShadow++; 1018 } 1019 } 1020 } 1021 1022 this.bsBuff = bsBuffShadow; 1023 this.bsLive = bsLiveShadow; 1024 } 1025 1026 private void sendMTFValues5(final int nGroups, final int nSelectors) 1027 throws IOException { 1028 bsW(3, nGroups); 1029 bsW(15, nSelectors); 1030 1031 final OutputStream outShadow = this.out; 1032 final byte[] selectorMtf = this.data.selectorMtf; 1033 1034 int bsLiveShadow = this.bsLive; 1035 int bsBuffShadow = this.bsBuff; 1036 1037 for (int i = 0; i < nSelectors; i++) { 1038 for (int j = 0, hj = selectorMtf[i] & 0xff; j < hj; j++) { 1039 // inlined: bsW(1, 1); 1040 while (bsLiveShadow >= 8) { 1041 outShadow.write(bsBuffShadow >> 24); 1042 bsBuffShadow <<= 8; 1043 bsLiveShadow -= 8; 1044 } 1045 bsBuffShadow |= 1 << (32 - bsLiveShadow - 1); 1046 bsLiveShadow++; 1047 } 1048 1049 // inlined: bsW(1, 0); 1050 while (bsLiveShadow >= 8) { 1051 outShadow.write(bsBuffShadow >> 24); 1052 bsBuffShadow <<= 8; 1053 bsLiveShadow -= 8; 1054 } 1055 // bsBuffShadow |= 0 << (32 - bsLiveShadow - 1); 1056 bsLiveShadow++; 1057 } 1058 1059 this.bsBuff = bsBuffShadow; 1060 this.bsLive = bsLiveShadow; 1061 } 1062 1063 private void sendMTFValues6(final int nGroups, final int alphaSize) 1064 throws IOException { 1065 final byte[][] len = this.data.sendMTFValues_len; 1066 final OutputStream outShadow = this.out; 1067 1068 int bsLiveShadow = this.bsLive; 1069 int bsBuffShadow = this.bsBuff; 1070 1071 for (int t = 0; t < nGroups; t++) { 1072 byte[] len_t = len[t]; 1073 int curr = len_t[0] & 0xff; 1074 1075 // inlined: bsW(5, curr); 1076 while (bsLiveShadow >= 8) { 1077 outShadow.write(bsBuffShadow >> 24); // write 8-bit 1078 bsBuffShadow <<= 8; 1079 bsLiveShadow -= 8; 1080 } 1081 bsBuffShadow |= curr << (32 - bsLiveShadow - 5); 1082 bsLiveShadow += 5; 1083 1084 for (int i = 0; i < alphaSize; i++) { 1085 int lti = len_t[i] & 0xff; 1086 while (curr < lti) { 1087 // inlined: bsW(2, 2); 1088 while (bsLiveShadow >= 8) { 1089 outShadow.write(bsBuffShadow >> 24); // write 8-bit 1090 bsBuffShadow <<= 8; 1091 bsLiveShadow -= 8; 1092 } 1093 bsBuffShadow |= 2 << (32 - bsLiveShadow - 2); 1094 bsLiveShadow += 2; 1095 1096 curr++; /* 10 */ 1097 } 1098 1099 while (curr > lti) { 1100 // inlined: bsW(2, 3); 1101 while (bsLiveShadow >= 8) { 1102 outShadow.write(bsBuffShadow >> 24); // write 8-bit 1103 bsBuffShadow <<= 8; 1104 bsLiveShadow -= 8; 1105 } 1106 bsBuffShadow |= 3 << (32 - bsLiveShadow - 2); 1107 bsLiveShadow += 2; 1108 1109 curr--; /* 11 */ 1110 } 1111 1112 // inlined: bsW(1, 0); 1113 while (bsLiveShadow >= 8) { 1114 outShadow.write(bsBuffShadow >> 24); // write 8-bit 1115 bsBuffShadow <<= 8; 1116 bsLiveShadow -= 8; 1117 } 1118 // bsBuffShadow |= 0 << (32 - bsLiveShadow - 1); 1119 bsLiveShadow++; 1120 } 1121 } 1122 1123 this.bsBuff = bsBuffShadow; 1124 this.bsLive = bsLiveShadow; 1125 } 1126 1127 private void sendMTFValues7(final int nSelectors) throws IOException { 1128 final Data dataShadow = this.data; 1129 final byte[][] len = dataShadow.sendMTFValues_len; 1130 final int[][] code = dataShadow.sendMTFValues_code; 1131 final OutputStream outShadow = this.out; 1132 final byte[] selector = dataShadow.selector; 1133 final char[] sfmap = dataShadow.sfmap; 1134 final int nMTFShadow = this.nMTF; 1135 1136 int selCtr = 0; 1137 1138 int bsLiveShadow = this.bsLive; 1139 int bsBuffShadow = this.bsBuff; 1140 1141 for (int gs = 0; gs < nMTFShadow;) { 1142 final int ge = Math.min(gs + G_SIZE - 1, nMTFShadow - 1); 1143 final int selector_selCtr = selector[selCtr] & 0xff; 1144 final int[] code_selCtr = code[selector_selCtr]; 1145 final byte[] len_selCtr = len[selector_selCtr]; 1146 1147 while (gs <= ge) { 1148 final int sfmap_i = sfmap[gs]; 1149 1150 // 1151 // inlined: bsW(len_selCtr[sfmap_i] & 0xff, 1152 // code_selCtr[sfmap_i]); 1153 // 1154 while (bsLiveShadow >= 8) { 1155 outShadow.write(bsBuffShadow >> 24); 1156 bsBuffShadow <<= 8; 1157 bsLiveShadow -= 8; 1158 } 1159 final int n = len_selCtr[sfmap_i] & 0xFF; 1160 bsBuffShadow |= code_selCtr[sfmap_i] << (32 - bsLiveShadow - n); 1161 bsLiveShadow += n; 1162 1163 gs++; 1164 } 1165 1166 gs = ge + 1; 1167 selCtr++; 1168 } 1169 1170 this.bsBuff = bsBuffShadow; 1171 this.bsLive = bsLiveShadow; 1172 } 1173 1174 private void moveToFrontCodeAndSend() throws IOException { 1175 bsW(24, this.origPtr); 1176 generateMTFValues(); 1177 sendMTFValues(); 1178 } 1179 1180 /** 1181 * This is the most hammered method of this class. 1182 * 1183 * <p> 1184 * This is the version using unrolled loops. Normally I never use such ones 1185 * in Java code. The unrolling has shown a noticable performance improvement 1186 * on JRE 1.4.2 (Linux i586 / HotSpot Client). Of course it depends on the 1187 * JIT compiler of the vm. 1188 * </p> 1189 */ 1190 private boolean mainSimpleSort(final Data dataShadow, final int lo, 1191 final int hi, final int d) { 1192 final int bigN = hi - lo + 1; 1193 if (bigN < 2) { 1194 return this.firstAttempt && (this.workDone > this.workLimit); 1195 } 1196 1197 int hp = 0; 1198 while (INCS[hp] < bigN) { 1199 hp++; 1200 } 1201 1202 final int[] fmap = dataShadow.fmap; 1203 final char[] quadrant = dataShadow.quadrant; 1204 final byte[] block = dataShadow.block; 1205 final int lastShadow = this.last; 1206 final int lastPlus1 = lastShadow + 1; 1207 final boolean firstAttemptShadow = this.firstAttempt; 1208 final int workLimitShadow = this.workLimit; 1209 int workDoneShadow = this.workDone; 1210 1211 // Following block contains unrolled code which could be shortened by 1212 // coding it in additional loops. 1213 1214 HP: while (--hp >= 0) { 1215 final int h = INCS[hp]; 1216 final int mj = lo + h - 1; 1217 1218 for (int i = lo + h; i <= hi;) { 1219 // copy 1220 for (int k = 3; (i <= hi) && (--k >= 0); i++) { 1221 final int v = fmap[i]; 1222 final int vd = v + d; 1223 int j = i; 1224 1225 // for (int a; 1226 // (j > mj) && mainGtU((a = fmap[j - h]) + d, vd, 1227 // block, quadrant, lastShadow); 1228 // j -= h) { 1229 // fmap[j] = a; 1230 // } 1231 // 1232 // unrolled version: 1233 1234 // start inline mainGTU 1235 boolean onceRunned = false; 1236 int a = 0; 1237 1238 HAMMER: while (true) { 1239 if (onceRunned) { 1240 fmap[j] = a; 1241 if ((j -= h) <= mj) { 1242 break HAMMER; 1243 } 1244 } else { 1245 onceRunned = true; 1246 } 1247 1248 a = fmap[j - h]; 1249 int i1 = a + d; 1250 int i2 = vd; 1251 1252 // following could be done in a loop, but 1253 // unrolled it for performance: 1254 if (block[i1 + 1] == block[i2 + 1]) { 1255 if (block[i1 + 2] == block[i2 + 2]) { 1256 if (block[i1 + 3] == block[i2 + 3]) { 1257 if (block[i1 + 4] == block[i2 + 4]) { 1258 if (block[i1 + 5] == block[i2 + 5]) { 1259 if (block[(i1 += 6)] == block[(i2 += 6)]) { 1260 int x = lastShadow; 1261 X: while (x > 0) { 1262 x -= 4; 1263 1264 if (block[i1 + 1] == block[i2 + 1]) { 1265 if (quadrant[i1] == quadrant[i2]) { 1266 if (block[i1 + 2] == block[i2 + 2]) { 1267 if (quadrant[i1 + 1] == quadrant[i2 + 1]) { 1268 if (block[i1 + 3] == block[i2 + 3]) { 1269 if (quadrant[i1 + 2] == quadrant[i2 + 2]) { 1270 if (block[i1 + 4] == block[i2 + 4]) { 1271 if (quadrant[i1 + 3] == quadrant[i2 + 3]) { 1272 if ((i1 += 4) >= lastPlus1) { 1273 i1 -= lastPlus1; 1274 } 1275 if ((i2 += 4) >= lastPlus1) { 1276 i2 -= lastPlus1; 1277 } 1278 workDoneShadow++; 1279 continue X; 1280 } else if ((quadrant[i1 + 3] > quadrant[i2 + 3])) { 1281 continue HAMMER; 1282 } else { 1283 break HAMMER; 1284 } 1285 } else if ((block[i1 + 4] & 0xff) > (block[i2 + 4] & 0xff)) { 1286 continue HAMMER; 1287 } else { 1288 break HAMMER; 1289 } 1290 } else if ((quadrant[i1 + 2] > quadrant[i2 + 2])) { 1291 continue HAMMER; 1292 } else { 1293 break HAMMER; 1294 } 1295 } else if ((block[i1 + 3] & 0xff) > (block[i2 + 3] & 0xff)) { 1296 continue HAMMER; 1297 } else { 1298 break HAMMER; 1299 } 1300 } else if ((quadrant[i1 + 1] > quadrant[i2 + 1])) { 1301 continue HAMMER; 1302 } else { 1303 break HAMMER; 1304 } 1305 } else if ((block[i1 + 2] & 0xff) > (block[i2 + 2] & 0xff)) { 1306 continue HAMMER; 1307 } else { 1308 break HAMMER; 1309 } 1310 } else if ((quadrant[i1] > quadrant[i2])) { 1311 continue HAMMER; 1312 } else { 1313 break HAMMER; 1314 } 1315 } else if ((block[i1 + 1] & 0xff) > (block[i2 + 1] & 0xff)) { 1316 continue HAMMER; 1317 } else { 1318 break HAMMER; 1319 } 1320 1321 } 1322 break HAMMER; 1323 } // while x > 0 1324 else { 1325 if ((block[i1] & 0xff) > (block[i2] & 0xff)) { 1326 continue HAMMER; 1327 } else { 1328 break HAMMER; 1329 } 1330 } 1331 } else if ((block[i1 + 5] & 0xff) > (block[i2 + 5] & 0xff)) { 1332 continue HAMMER; 1333 } else { 1334 break HAMMER; 1335 } 1336 } else if ((block[i1 + 4] & 0xff) > (block[i2 + 4] & 0xff)) { 1337 continue HAMMER; 1338 } else { 1339 break HAMMER; 1340 } 1341 } else if ((block[i1 + 3] & 0xff) > (block[i2 + 3] & 0xff)) { 1342 continue HAMMER; 1343 } else { 1344 break HAMMER; 1345 } 1346 } else if ((block[i1 + 2] & 0xff) > (block[i2 + 2] & 0xff)) { 1347 continue HAMMER; 1348 } else { 1349 break HAMMER; 1350 } 1351 } else if ((block[i1 + 1] & 0xff) > (block[i2 + 1] & 0xff)) { 1352 continue HAMMER; 1353 } else { 1354 break HAMMER; 1355 } 1356 1357 } // HAMMER 1358 // end inline mainGTU 1359 1360 fmap[j] = v; 1361 } 1362 1363 if (firstAttemptShadow && (i <= hi) 1364 && (workDoneShadow > workLimitShadow)) { 1365 break HP; 1366 } 1367 } 1368 } 1369 1370 this.workDone = workDoneShadow; 1371 return firstAttemptShadow && (workDoneShadow > workLimitShadow); 1372 } 1373 1374 private static void vswap(int[] fmap, int p1, int p2, int n) { 1375 n += p1; 1376 while (p1 < n) { 1377 int t = fmap[p1]; 1378 fmap[p1++] = fmap[p2]; 1379 fmap[p2++] = t; 1380 } 1381 } 1382 1383 private static byte med3(byte a, byte b, byte c) { 1384 return (a < b) ? (b < c ? b : a < c ? c : a) : (b > c ? b : a > c ? c 1385 : a); 1386 } 1387 1388 private void blockSort() { 1389 this.workLimit = WORK_FACTOR * this.last; 1390 this.workDone = 0; 1391 this.blockRandomised = false; 1392 this.firstAttempt = true; 1393 mainSort(); 1394 1395 if (this.firstAttempt && (this.workDone > this.workLimit)) { 1396 randomiseBlock(); 1397 this.workLimit = this.workDone = 0; 1398 this.firstAttempt = false; 1399 mainSort(); 1400 } 1401 1402 int[] fmap = this.data.fmap; 1403 this.origPtr = -1; 1404 for (int i = 0, lastShadow = this.last; i <= lastShadow; i++) { 1405 if (fmap[i] == 0) { 1406 this.origPtr = i; 1407 break; 1408 } 1409 } 1410 1411 // assert (this.origPtr != -1) : this.origPtr; 1412 } 1413 1414 /** 1415 * Method "mainQSort3", file "blocksort.c", BZip2 1.0.2 1416 */ 1417 private void mainQSort3(final Data dataShadow, final int loSt, 1418 final int hiSt, final int dSt) { 1419 final int[] stack_ll = dataShadow.stack_ll; 1420 final int[] stack_hh = dataShadow.stack_hh; 1421 final int[] stack_dd = dataShadow.stack_dd; 1422 final int[] fmap = dataShadow.fmap; 1423 final byte[] block = dataShadow.block; 1424 1425 stack_ll[0] = loSt; 1426 stack_hh[0] = hiSt; 1427 stack_dd[0] = dSt; 1428 1429 for (int sp = 1; --sp >= 0;) { 1430 final int lo = stack_ll[sp]; 1431 final int hi = stack_hh[sp]; 1432 final int d = stack_dd[sp]; 1433 1434 if ((hi - lo < SMALL_THRESH) || (d > DEPTH_THRESH)) { 1435 if (mainSimpleSort(dataShadow, lo, hi, d)) { 1436 return; 1437 } 1438 } else { 1439 final int d1 = d + 1; 1440 final int med = med3(block[fmap[lo] + d1], 1441 block[fmap[hi] + d1], block[fmap[(lo + hi) >>> 1] + d1]) & 0xff; 1442 1443 int unLo = lo; 1444 int unHi = hi; 1445 int ltLo = lo; 1446 int gtHi = hi; 1447 1448 while (true) { 1449 while (unLo <= unHi) { 1450 final int n = (block[fmap[unLo] + d1] & 0xff) 1451 - med; 1452 if (n == 0) { 1453 final int temp = fmap[unLo]; 1454 fmap[unLo++] = fmap[ltLo]; 1455 fmap[ltLo++] = temp; 1456 } else if (n < 0) { 1457 unLo++; 1458 } else { 1459 break; 1460 } 1461 } 1462 1463 while (unLo <= unHi) { 1464 final int n = (block[fmap[unHi] + d1] & 0xff) 1465 - med; 1466 if (n == 0) { 1467 final int temp = fmap[unHi]; 1468 fmap[unHi--] = fmap[gtHi]; 1469 fmap[gtHi--] = temp; 1470 } else if (n > 0) { 1471 unHi--; 1472 } else { 1473 break; 1474 } 1475 } 1476 1477 if (unLo <= unHi) { 1478 final int temp = fmap[unLo]; 1479 fmap[unLo++] = fmap[unHi]; 1480 fmap[unHi--] = temp; 1481 } else { 1482 break; 1483 } 1484 } 1485 1486 if (gtHi < ltLo) { 1487 stack_ll[sp] = lo; 1488 stack_hh[sp] = hi; 1489 stack_dd[sp] = d1; 1490 sp++; 1491 } else { 1492 int n = ((ltLo - lo) < (unLo - ltLo)) ? (ltLo - lo) 1493 : (unLo - ltLo); 1494 vswap(fmap, lo, unLo - n, n); 1495 int m = ((hi - gtHi) < (gtHi - unHi)) ? (hi - gtHi) 1496 : (gtHi - unHi); 1497 vswap(fmap, unLo, hi - m + 1, m); 1498 1499 n = lo + unLo - ltLo - 1; 1500 m = hi - (gtHi - unHi) + 1; 1501 1502 stack_ll[sp] = lo; 1503 stack_hh[sp] = n; 1504 stack_dd[sp] = d; 1505 sp++; 1506 1507 stack_ll[sp] = n + 1; 1508 stack_hh[sp] = m - 1; 1509 stack_dd[sp] = d1; 1510 sp++; 1511 1512 stack_ll[sp] = m; 1513 stack_hh[sp] = hi; 1514 stack_dd[sp] = d; 1515 sp++; 1516 } 1517 } 1518 } 1519 } 1520 1521 private void mainSort() { 1522 final Data dataShadow = this.data; 1523 final int[] runningOrder = dataShadow.mainSort_runningOrder; 1524 final int[] copy = dataShadow.mainSort_copy; 1525 final boolean[] bigDone = dataShadow.mainSort_bigDone; 1526 final int[] ftab = dataShadow.ftab; 1527 final byte[] block = dataShadow.block; 1528 final int[] fmap = dataShadow.fmap; 1529 final char[] quadrant = dataShadow.quadrant; 1530 final int lastShadow = this.last; 1531 final int workLimitShadow = this.workLimit; 1532 final boolean firstAttemptShadow = this.firstAttempt; 1533 1534 // Set up the 2-byte frequency table 1535 for (int i = 65537; --i >= 0;) { 1536 ftab[i] = 0; 1537 } 1538 1539 /* 1540 * In the various block-sized structures, live data runs from 0 to 1541 * last+NUM_OVERSHOOT_BYTES inclusive. First, set up the overshoot area 1542 * for block. 1543 */ 1544 for (int i = 0; i < NUM_OVERSHOOT_BYTES; i++) { 1545 block[lastShadow + i + 2] = block[(i % (lastShadow + 1)) + 1]; 1546 } 1547 for (int i = lastShadow + NUM_OVERSHOOT_BYTES +1; --i >= 0;) { 1548 quadrant[i] = 0; 1549 } 1550 block[0] = block[lastShadow + 1]; 1551 1552 // Complete the initial radix sort: 1553 1554 int c1 = block[0] & 0xff; 1555 for (int i = 0; i <= lastShadow; i++) { 1556 final int c2 = block[i + 1] & 0xff; 1557 ftab[(c1 << 8) + c2]++; 1558 c1 = c2; 1559 } 1560 1561 for (int i = 1; i <= 65536; i++) 1562 ftab[i] += ftab[i - 1]; 1563 1564 c1 = block[1] & 0xff; 1565 for (int i = 0; i < lastShadow; i++) { 1566 final int c2 = block[i + 2] & 0xff; 1567 fmap[--ftab[(c1 << 8) + c2]] = i; 1568 c1 = c2; 1569 } 1570 1571 fmap[--ftab[((block[lastShadow + 1] & 0xff) << 8) + (block[1] & 0xff)]] = lastShadow; 1572 1573 /* 1574 * Now ftab contains the first loc of every small bucket. Calculate the 1575 * running order, from smallest to largest big bucket. 1576 */ 1577 for (int i = 256; --i >= 0;) { 1578 bigDone[i] = false; 1579 runningOrder[i] = i; 1580 } 1581 1582 for (int h = 364; h != 1;) { 1583 h /= 3; 1584 for (int i = h; i <= 255; i++) { 1585 final int vv = runningOrder[i]; 1586 final int a = ftab[(vv + 1) << 8] - ftab[vv << 8]; 1587 final int b = h - 1; 1588 int j = i; 1589 for (int ro = runningOrder[j - h]; (ftab[(ro + 1) << 8] - ftab[ro << 8]) > a; ro = runningOrder[j 1590 - h]) { 1591 runningOrder[j] = ro; 1592 j -= h; 1593 if (j <= b) { 1594 break; 1595 } 1596 } 1597 runningOrder[j] = vv; 1598 } 1599 } 1600 1601 /* 1602 * The main sorting loop. 1603 */ 1604 for (int i = 0; i <= 255; i++) { 1605 /* 1606 * Process big buckets, starting with the least full. 1607 */ 1608 final int ss = runningOrder[i]; 1609 1610 // Step 1: 1611 /* 1612 * Complete the big bucket [ss] by quicksorting any unsorted small 1613 * buckets [ss, j]. Hopefully previous pointer-scanning phases have 1614 * already completed many of the small buckets [ss, j], so we don't 1615 * have to sort them at all. 1616 */ 1617 for (int j = 0; j <= 255; j++) { 1618 final int sb = (ss << 8) + j; 1619 final int ftab_sb = ftab[sb]; 1620 if ((ftab_sb & SETMASK) != SETMASK) { 1621 final int lo = ftab_sb & CLEARMASK; 1622 final int hi = (ftab[sb + 1] & CLEARMASK) - 1; 1623 if (hi > lo) { 1624 mainQSort3(dataShadow, lo, hi, 2); 1625 if (firstAttemptShadow 1626 && (this.workDone > workLimitShadow)) { 1627 return; 1628 } 1629 } 1630 ftab[sb] = ftab_sb | SETMASK; 1631 } 1632 } 1633 1634 // Step 2: 1635 // Now scan this big bucket so as to synthesise the 1636 // sorted order for small buckets [t, ss] for all t != ss. 1637 1638 for (int j = 0; j <= 255; j++) { 1639 copy[j] = ftab[(j << 8) + ss] & CLEARMASK; 1640 } 1641 1642 for (int j = ftab[ss << 8] & CLEARMASK, hj = (ftab[(ss + 1) << 8] & CLEARMASK); j < hj; j++) { 1643 final int fmap_j = fmap[j]; 1644 c1 = block[fmap_j] & 0xff; 1645 if (!bigDone[c1]) { 1646 fmap[copy[c1]] = (fmap_j == 0) ? lastShadow : (fmap_j - 1); 1647 copy[c1]++; 1648 } 1649 } 1650 1651 for (int j = 256; --j >= 0;) 1652 ftab[(j << 8) + ss] |= SETMASK; 1653 1654 // Step 3: 1655 /* 1656 * The ss big bucket is now done. Record this fact, and update the 1657 * quadrant descriptors. Remember to update quadrants in the 1658 * overshoot area too, if necessary. The "if (i < 255)" test merely 1659 * skips this updating for the last bucket processed, since updating 1660 * for the last bucket is pointless. 1661 */ 1662 bigDone[ss] = true; 1663 1664 if (i < 255) { 1665 final int bbStart = ftab[ss << 8] & CLEARMASK; 1666 final int bbSize = (ftab[(ss + 1) << 8] & CLEARMASK) - bbStart; 1667 int shifts = 0; 1668 1669 while ((bbSize >> shifts) > 65534) { 1670 shifts++; 1671 } 1672 1673 for (int j = 0; j < bbSize; j++) { 1674 final int a2update = fmap[bbStart + j]; 1675 final char qVal = (char) (j >> shifts); 1676 quadrant[a2update] = qVal; 1677 if (a2update < NUM_OVERSHOOT_BYTES) { 1678 quadrant[a2update + lastShadow + 1] = qVal; 1679 } 1680 } 1681 } 1682 1683 } 1684 } 1685 1686 private void randomiseBlock() { 1687 final boolean[] inUse = this.data.inUse; 1688 final byte[] block = this.data.block; 1689 final int lastShadow = this.last; 1690 1691 for (int i = 256; --i >= 0;) 1692 inUse[i] = false; 1693 1694 int rNToGo = 0; 1695 int rTPos = 0; 1696 for (int i = 0, j = 1; i <= lastShadow; i = j, j++) { 1697 if (rNToGo == 0) { 1698 rNToGo = (char) Rand.rNums(rTPos); 1699 if (++rTPos == 512) { 1700 rTPos = 0; 1701 } 1702 } 1703 1704 rNToGo--; 1705 block[j] ^= ((rNToGo == 1) ? 1 : 0); 1706 1707 // handle 16 bit signed numbers 1708 inUse[block[j] & 0xff] = true; 1709 } 1710 1711 this.blockRandomised = true; 1712 } 1713 1714 private void generateMTFValues() { 1715 final int lastShadow = this.last; 1716 final Data dataShadow = this.data; 1717 final boolean[] inUse = dataShadow.inUse; 1718 final byte[] block = dataShadow.block; 1719 final int[] fmap = dataShadow.fmap; 1720 final char[] sfmap = dataShadow.sfmap; 1721 final int[] mtfFreq = dataShadow.mtfFreq; 1722 final byte[] unseqToSeq = dataShadow.unseqToSeq; 1723 final byte[] yy = dataShadow.generateMTFValues_yy; 1724 1725 // make maps 1726 int nInUseShadow = 0; 1727 for (int i = 0; i < 256; i++) { 1728 if (inUse[i]) { 1729 unseqToSeq[i] = (byte) nInUseShadow; 1730 nInUseShadow++; 1731 } 1732 } 1733 this.nInUse = nInUseShadow; 1734 1735 final int eob = nInUseShadow + 1; 1736 1737 for (int i = eob; i >= 0; i--) { 1738 mtfFreq[i] = 0; 1739 } 1740 1741 for (int i = nInUseShadow; --i >= 0;) { 1742 yy[i] = (byte) i; 1743 } 1744 1745 int wr = 0; 1746 int zPend = 0; 1747 1748 for (int i = 0; i <= lastShadow; i++) { 1749 final byte ll_i = unseqToSeq[block[fmap[i]] & 0xff]; 1750 byte tmp = yy[0]; 1751 int j = 0; 1752 1753 while (ll_i != tmp) { 1754 j++; 1755 byte tmp2 = tmp; 1756 tmp = yy[j]; 1757 yy[j] = tmp2; 1758 } 1759 yy[0] = tmp; 1760 1761 if (j == 0) { 1762 zPend++; 1763 } else { 1764 if (zPend > 0) { 1765 zPend--; 1766 while (true) { 1767 if ((zPend & 1) == 0) { 1768 sfmap[wr] = RUNA; 1769 wr++; 1770 mtfFreq[RUNA]++; 1771 } else { 1772 sfmap[wr] = RUNB; 1773 wr++; 1774 mtfFreq[RUNB]++; 1775 } 1776 1777 if (zPend >= 2) { 1778 zPend = (zPend - 2) >> 1; 1779 } else { 1780 break; 1781 } 1782 } 1783 zPend = 0; 1784 } 1785 sfmap[wr] = (char) (j + 1); 1786 wr++; 1787 mtfFreq[j + 1]++; 1788 } 1789 } 1790 1791 if (zPend > 0) { 1792 zPend--; 1793 while (true) { 1794 if ((zPend & 1) == 0) { 1795 sfmap[wr] = RUNA; 1796 wr++; 1797 mtfFreq[RUNA]++; 1798 } else { 1799 sfmap[wr] = RUNB; 1800 wr++; 1801 mtfFreq[RUNB]++; 1802 } 1803 1804 if (zPend >= 2) { 1805 zPend = (zPend - 2) >> 1; 1806 } else { 1807 break; 1808 } 1809 } 1810 } 1811 1812 sfmap[wr] = (char) eob; 1813 mtfFreq[eob]++; 1814 this.nMTF = wr + 1; 1815 } 1816 1817 private static final class Data extends Object { 1818 1819 // with blockSize 900k 1820 final boolean[] inUse = new boolean[256]; // 256 byte 1821 final byte[] unseqToSeq = new byte[256]; // 256 byte 1822 final int[] mtfFreq = new int[MAX_ALPHA_SIZE]; // 1032 byte 1823 final byte[] selector = new byte[MAX_SELECTORS]; // 18002 byte 1824 final byte[] selectorMtf = new byte[MAX_SELECTORS]; // 18002 byte 1825 1826 final byte[] generateMTFValues_yy = new byte[256]; // 256 byte 1827 final byte[][] sendMTFValues_len = new byte[N_GROUPS][MAX_ALPHA_SIZE]; // 1548 1828 // byte 1829 final int[][] sendMTFValues_rfreq = new int[N_GROUPS][MAX_ALPHA_SIZE]; // 6192 1830 // byte 1831 final int[] sendMTFValues_fave = new int[N_GROUPS]; // 24 byte 1832 final short[] sendMTFValues_cost = new short[N_GROUPS]; // 12 byte 1833 final int[][] sendMTFValues_code = new int[N_GROUPS][MAX_ALPHA_SIZE]; // 6192 1834 // byte 1835 final byte[] sendMTFValues2_pos = new byte[N_GROUPS]; // 6 byte 1836 final boolean[] sentMTFValues4_inUse16 = new boolean[16]; // 16 byte 1837 1838 final int[] stack_ll = new int[QSORT_STACK_SIZE]; // 4000 byte 1839 final int[] stack_hh = new int[QSORT_STACK_SIZE]; // 4000 byte 1840 final int[] stack_dd = new int[QSORT_STACK_SIZE]; // 4000 byte 1841 1842 final int[] mainSort_runningOrder = new int[256]; // 1024 byte 1843 final int[] mainSort_copy = new int[256]; // 1024 byte 1844 final boolean[] mainSort_bigDone = new boolean[256]; // 256 byte 1845 1846 final int[] heap = new int[MAX_ALPHA_SIZE + 2]; // 1040 byte 1847 final int[] weight = new int[MAX_ALPHA_SIZE * 2]; // 2064 byte 1848 final int[] parent = new int[MAX_ALPHA_SIZE * 2]; // 2064 byte 1849 1850 final int[] ftab = new int[65537]; // 262148 byte 1851 // ------------ 1852 // 333408 byte 1853 1854 final byte[] block; // 900021 byte 1855 final int[] fmap; // 3600000 byte 1856 final char[] sfmap; // 3600000 byte 1857 // ------------ 1858 // 8433529 byte 1859 // ============ 1860 1861 /** 1862 * Array instance identical to sfmap, both are used only 1863 * temporarily and indepently, so we do not need to allocate 1864 * additional memory. 1865 */ 1866 final char[] quadrant; 1867 1868 Data(int blockSize100k) { 1869 super(); 1870 1871 final int n = blockSize100k * BZip2Constants.BASEBLOCKSIZE; 1872 this.block = new byte[(n + 1 + NUM_OVERSHOOT_BYTES)]; 1873 this.fmap = new int[n]; 1874 this.sfmap = new char[2 * n]; 1875 this.quadrant = this.sfmap; 1876 } 1877 1878 } 1879 1880 }