compress.c (22149B)
1 2 /*-------------------------------------------------------------*/ 3 /*--- Compression machinery (not incl block sorting) ---*/ 4 /*--- compress.c ---*/ 5 /*-------------------------------------------------------------*/ 6 7 /*-- 8 This file is a part of bzip2 and/or libbzip2, a program and 9 library for lossless, block-sorting data compression. 10 11 Copyright (C) 1996-2005 Julian R Seward. All rights reserved. 12 13 Redistribution and use in source and binary forms, with or without 14 modification, are permitted provided that the following conditions 15 are met: 16 17 1. Redistributions of source code must retain the above copyright 18 notice, this list of conditions and the following disclaimer. 19 20 2. The origin of this software must not be misrepresented; you must 21 not claim that you wrote the original software. If you use this 22 software in a product, an acknowledgment in the product 23 documentation would be appreciated but is not required. 24 25 3. Altered source versions must be plainly marked as such, and must 26 not be misrepresented as being the original software. 27 28 4. The name of the author may not be used to endorse or promote 29 products derived from this software without specific prior written 30 permission. 31 32 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS 33 OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 34 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 35 ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY 36 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 37 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE 38 GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 39 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 40 WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 41 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 42 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 43 44 Julian Seward, Cambridge, UK. 45 jseward@bzip.org 46 bzip2/libbzip2 version 1.0 of 21 March 2000 47 48 This program is based on (at least) the work of: 49 Mike Burrows 50 David Wheeler 51 Peter Fenwick 52 Alistair Moffat 53 Radford Neal 54 Ian H. Witten 55 Robert Sedgewick 56 Jon L. Bentley 57 58 For more information on these sources, see the manual. 59 --*/ 60 61 /*-- 62 CHANGES 63 ~~~~~~~ 64 0.9.0 -- original version. 65 66 0.9.0a/b -- no changes in this file. 67 68 0.9.0c 69 * changed setting of nGroups in sendMTFValues() so as to 70 do a bit better on small files 71 --*/ 72 73 #include "bzlib_private.h" 74 75 76 /*---------------------------------------------------*/ 77 /*--- Bit stream I/O ---*/ 78 /*---------------------------------------------------*/ 79 80 /*---------------------------------------------------*/ 81 void BZ2_bsInitWrite ( EState* s ) 82 { 83 s->bsLive = 0; 84 s->bsBuff = 0; 85 } 86 87 88 /*---------------------------------------------------*/ 89 static 90 void bsFinishWrite ( EState* s ) 91 { 92 while (s->bsLive > 0) { 93 s->zbits[s->numZ] = (UChar)(s->bsBuff >> 24); 94 s->numZ++; 95 s->bsBuff <<= 8; 96 s->bsLive -= 8; 97 } 98 } 99 100 101 /*---------------------------------------------------*/ 102 #define bsNEEDW(nz) \ 103 { \ 104 while (s->bsLive >= 8) { \ 105 s->zbits[s->numZ] \ 106 = (UChar)(s->bsBuff >> 24); \ 107 s->numZ++; \ 108 s->bsBuff <<= 8; \ 109 s->bsLive -= 8; \ 110 } \ 111 } 112 113 114 /*---------------------------------------------------*/ 115 static 116 __inline__ 117 void bsW ( EState* s, Int32 n, UInt32 v ) 118 { 119 bsNEEDW ( n ); 120 s->bsBuff |= (v << (32 - s->bsLive - n)); 121 s->bsLive += n; 122 } 123 124 125 /*---------------------------------------------------*/ 126 static 127 void bsPutUInt32 ( EState* s, UInt32 u ) 128 { 129 bsW ( s, 8, (u >> 24) & 0xffL ); 130 bsW ( s, 8, (u >> 16) & 0xffL ); 131 bsW ( s, 8, (u >> 8) & 0xffL ); 132 bsW ( s, 8, u & 0xffL ); 133 } 134 135 136 /*---------------------------------------------------*/ 137 static 138 void bsPutUChar ( EState* s, UChar c ) 139 { 140 bsW( s, 8, (UInt32)c ); 141 } 142 143 144 /*---------------------------------------------------*/ 145 /*--- The back end proper ---*/ 146 /*---------------------------------------------------*/ 147 148 /*---------------------------------------------------*/ 149 static 150 void makeMaps_e ( EState* s ) 151 { 152 Int32 i; 153 s->nInUse = 0; 154 for (i = 0; i < 256; i++) 155 if (s->inUse[i]) { 156 s->unseqToSeq[i] = s->nInUse; 157 s->nInUse++; 158 } 159 } 160 161 162 /*---------------------------------------------------*/ 163 static 164 void generateMTFValues ( EState* s ) 165 { 166 UChar yy[256]; 167 Int32 i, j; 168 Int32 zPend; 169 Int32 wr; 170 Int32 EOB; 171 172 /* 173 After sorting (eg, here), 174 s->arr1 [ 0 .. s->nblock-1 ] holds sorted order, 175 and 176 ((UChar*)s->arr2) [ 0 .. s->nblock-1 ] 177 holds the original block data. 178 179 The first thing to do is generate the MTF values, 180 and put them in 181 ((UInt16*)s->arr1) [ 0 .. s->nblock-1 ]. 182 Because there are strictly fewer or equal MTF values 183 than block values, ptr values in this area are overwritten 184 with MTF values only when they are no longer needed. 185 186 The final compressed bitstream is generated into the 187 area starting at 188 (UChar*) (&((UChar*)s->arr2)[s->nblock]) 189 190 These storage aliases are set up in bzCompressInit(), 191 except for the last one, which is arranged in 192 compressBlock(). 193 */ 194 UInt32* ptr = s->ptr; 195 UChar* block = s->block; 196 UInt16* mtfv = s->mtfv; 197 198 makeMaps_e ( s ); 199 EOB = s->nInUse+1; 200 201 for (i = 0; i <= EOB; i++) s->mtfFreq[i] = 0; 202 203 wr = 0; 204 zPend = 0; 205 for (i = 0; i < s->nInUse; i++) yy[i] = (UChar) i; 206 207 for (i = 0; i < s->nblock; i++) { 208 UChar ll_i; 209 AssertD ( wr <= i, "generateMTFValues(1)" ); 210 j = ptr[i]-1; if (j < 0) j += s->nblock; 211 ll_i = s->unseqToSeq[block[j]]; 212 AssertD ( ll_i < s->nInUse, "generateMTFValues(2a)" ); 213 214 if (yy[0] == ll_i) { 215 zPend++; 216 } else { 217 218 if (zPend > 0) { 219 zPend--; 220 while (True) { 221 if (zPend & 1) { 222 mtfv[wr] = BZ_RUNB; wr++; 223 s->mtfFreq[BZ_RUNB]++; 224 } else { 225 mtfv[wr] = BZ_RUNA; wr++; 226 s->mtfFreq[BZ_RUNA]++; 227 } 228 if (zPend < 2) break; 229 zPend = (zPend - 2) / 2; 230 }; 231 zPend = 0; 232 } 233 { 234 register UChar rtmp; 235 register UChar* ryy_j; 236 register UChar rll_i; 237 rtmp = yy[1]; 238 yy[1] = yy[0]; 239 ryy_j = &(yy[1]); 240 rll_i = ll_i; 241 while ( rll_i != rtmp ) { 242 register UChar rtmp2; 243 ryy_j++; 244 rtmp2 = rtmp; 245 rtmp = *ryy_j; 246 *ryy_j = rtmp2; 247 }; 248 yy[0] = rtmp; 249 j = ryy_j - &(yy[0]); 250 mtfv[wr] = j+1; wr++; s->mtfFreq[j+1]++; 251 } 252 253 } 254 } 255 256 if (zPend > 0) { 257 zPend--; 258 while (True) { 259 if (zPend & 1) { 260 mtfv[wr] = BZ_RUNB; wr++; 261 s->mtfFreq[BZ_RUNB]++; 262 } else { 263 mtfv[wr] = BZ_RUNA; wr++; 264 s->mtfFreq[BZ_RUNA]++; 265 } 266 if (zPend < 2) break; 267 zPend = (zPend - 2) / 2; 268 }; 269 zPend = 0; 270 } 271 272 mtfv[wr] = EOB; wr++; s->mtfFreq[EOB]++; 273 274 s->nMTF = wr; 275 } 276 277 278 /*---------------------------------------------------*/ 279 #define BZ_LESSER_ICOST 0 280 #define BZ_GREATER_ICOST 15 281 282 static 283 void sendMTFValues ( EState* s ) 284 { 285 Int32 v, t, i, j, gs, ge, totc, bt, bc, iter; 286 Int32 nSelectors, alphaSize, minLen, maxLen, selCtr; 287 Int32 nGroups, nBytes; 288 289 /*-- 290 UChar len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; 291 is a global since the decoder also needs it. 292 293 Int32 code[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; 294 Int32 rfreq[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; 295 are also globals only used in this proc. 296 Made global to keep stack frame size small. 297 --*/ 298 299 300 UInt16 cost[BZ_N_GROUPS]; 301 Int32 fave[BZ_N_GROUPS]; 302 303 UInt16* mtfv = s->mtfv; 304 305 if (s->verbosity >= 3) 306 VPrintf3( " %d in block, %d after MTF & 1-2 coding, " 307 "%d+2 syms in use\n", 308 s->nblock, s->nMTF, s->nInUse ); 309 310 alphaSize = s->nInUse+2; 311 for (t = 0; t < BZ_N_GROUPS; t++) 312 for (v = 0; v < alphaSize; v++) 313 s->len[t][v] = BZ_GREATER_ICOST; 314 315 /*--- Decide how many coding tables to use ---*/ 316 AssertH ( s->nMTF > 0, 3001 ); 317 if (s->nMTF < 200) nGroups = 2; else 318 if (s->nMTF < 600) nGroups = 3; else 319 if (s->nMTF < 1200) nGroups = 4; else 320 if (s->nMTF < 2400) nGroups = 5; else 321 nGroups = 6; 322 323 /*--- Generate an initial set of coding tables ---*/ 324 { 325 Int32 nPart, remF, tFreq, aFreq; 326 327 nPart = nGroups; 328 remF = s->nMTF; 329 gs = 0; 330 while (nPart > 0) { 331 tFreq = remF / nPart; 332 ge = gs-1; 333 aFreq = 0; 334 while (aFreq < tFreq && ge < alphaSize-1) { 335 ge++; 336 aFreq += s->mtfFreq[ge]; 337 } 338 339 if (ge > gs 340 && nPart != nGroups && nPart != 1 341 && ((nGroups-nPart) % 2 == 1)) { 342 aFreq -= s->mtfFreq[ge]; 343 ge--; 344 } 345 346 if (s->verbosity >= 3) 347 VPrintf5( " initial group %d, [%d .. %d], " 348 "has %d syms (%4.1f%%)\n", 349 nPart, gs, ge, aFreq, 350 (100.0 * (float)aFreq) / (float)(s->nMTF) ); 351 352 for (v = 0; v < alphaSize; v++) 353 if (v >= gs && v <= ge) 354 s->len[nPart-1][v] = BZ_LESSER_ICOST; else 355 s->len[nPart-1][v] = BZ_GREATER_ICOST; 356 357 nPart--; 358 gs = ge+1; 359 remF -= aFreq; 360 } 361 } 362 363 /*--- 364 Iterate up to BZ_N_ITERS times to improve the tables. 365 ---*/ 366 for (iter = 0; iter < BZ_N_ITERS; iter++) { 367 368 for (t = 0; t < nGroups; t++) fave[t] = 0; 369 370 for (t = 0; t < nGroups; t++) 371 for (v = 0; v < alphaSize; v++) 372 s->rfreq[t][v] = 0; 373 374 /*--- 375 Set up an auxiliary length table which is used to fast-track 376 the common case (nGroups == 6). 377 ---*/ 378 if (nGroups == 6) { 379 for (v = 0; v < alphaSize; v++) { 380 s->len_pack[v][0] = (s->len[1][v] << 16) | s->len[0][v]; 381 s->len_pack[v][1] = (s->len[3][v] << 16) | s->len[2][v]; 382 s->len_pack[v][2] = (s->len[5][v] << 16) | s->len[4][v]; 383 } 384 } 385 386 nSelectors = 0; 387 totc = 0; 388 gs = 0; 389 while (True) { 390 391 /*--- Set group start & end marks. --*/ 392 if (gs >= s->nMTF) break; 393 ge = gs + BZ_G_SIZE - 1; 394 if (ge >= s->nMTF) ge = s->nMTF-1; 395 396 /*-- 397 Calculate the cost of this group as coded 398 by each of the coding tables. 399 --*/ 400 for (t = 0; t < nGroups; t++) cost[t] = 0; 401 402 if (nGroups == 6 && 50 == ge-gs+1) { 403 /*--- fast track the common case ---*/ 404 register UInt32 cost01, cost23, cost45; 405 register UInt16 icv; 406 cost01 = cost23 = cost45 = 0; 407 408 # define BZ_ITER(nn) \ 409 icv = mtfv[gs+(nn)]; \ 410 cost01 += s->len_pack[icv][0]; \ 411 cost23 += s->len_pack[icv][1]; \ 412 cost45 += s->len_pack[icv][2]; \ 413 414 BZ_ITER(0); BZ_ITER(1); BZ_ITER(2); BZ_ITER(3); BZ_ITER(4); 415 BZ_ITER(5); BZ_ITER(6); BZ_ITER(7); BZ_ITER(8); BZ_ITER(9); 416 BZ_ITER(10); BZ_ITER(11); BZ_ITER(12); BZ_ITER(13); BZ_ITER(14); 417 BZ_ITER(15); BZ_ITER(16); BZ_ITER(17); BZ_ITER(18); BZ_ITER(19); 418 BZ_ITER(20); BZ_ITER(21); BZ_ITER(22); BZ_ITER(23); BZ_ITER(24); 419 BZ_ITER(25); BZ_ITER(26); BZ_ITER(27); BZ_ITER(28); BZ_ITER(29); 420 BZ_ITER(30); BZ_ITER(31); BZ_ITER(32); BZ_ITER(33); BZ_ITER(34); 421 BZ_ITER(35); BZ_ITER(36); BZ_ITER(37); BZ_ITER(38); BZ_ITER(39); 422 BZ_ITER(40); BZ_ITER(41); BZ_ITER(42); BZ_ITER(43); BZ_ITER(44); 423 BZ_ITER(45); BZ_ITER(46); BZ_ITER(47); BZ_ITER(48); BZ_ITER(49); 424 425 # undef BZ_ITER 426 427 cost[0] = cost01 & 0xffff; cost[1] = cost01 >> 16; 428 cost[2] = cost23 & 0xffff; cost[3] = cost23 >> 16; 429 cost[4] = cost45 & 0xffff; cost[5] = cost45 >> 16; 430 431 } else { 432 /*--- slow version which correctly handles all situations ---*/ 433 for (i = gs; i <= ge; i++) { 434 UInt16 icv = mtfv[i]; 435 for (t = 0; t < nGroups; t++) cost[t] += s->len[t][icv]; 436 } 437 } 438 439 /*-- 440 Find the coding table which is best for this group, 441 and record its identity in the selector table. 442 --*/ 443 bc = 999999999; bt = -1; 444 for (t = 0; t < nGroups; t++) 445 if (cost[t] < bc) { bc = cost[t]; bt = t; }; 446 totc += bc; 447 fave[bt]++; 448 s->selector[nSelectors] = bt; 449 nSelectors++; 450 451 /*-- 452 Increment the symbol frequencies for the selected table. 453 --*/ 454 if (nGroups == 6 && 50 == ge-gs+1) { 455 /*--- fast track the common case ---*/ 456 457 # define BZ_ITUR(nn) s->rfreq[bt][ mtfv[gs+(nn)] ]++ 458 459 BZ_ITUR(0); BZ_ITUR(1); BZ_ITUR(2); BZ_ITUR(3); BZ_ITUR(4); 460 BZ_ITUR(5); BZ_ITUR(6); BZ_ITUR(7); BZ_ITUR(8); BZ_ITUR(9); 461 BZ_ITUR(10); BZ_ITUR(11); BZ_ITUR(12); BZ_ITUR(13); BZ_ITUR(14); 462 BZ_ITUR(15); BZ_ITUR(16); BZ_ITUR(17); BZ_ITUR(18); BZ_ITUR(19); 463 BZ_ITUR(20); BZ_ITUR(21); BZ_ITUR(22); BZ_ITUR(23); BZ_ITUR(24); 464 BZ_ITUR(25); BZ_ITUR(26); BZ_ITUR(27); BZ_ITUR(28); BZ_ITUR(29); 465 BZ_ITUR(30); BZ_ITUR(31); BZ_ITUR(32); BZ_ITUR(33); BZ_ITUR(34); 466 BZ_ITUR(35); BZ_ITUR(36); BZ_ITUR(37); BZ_ITUR(38); BZ_ITUR(39); 467 BZ_ITUR(40); BZ_ITUR(41); BZ_ITUR(42); BZ_ITUR(43); BZ_ITUR(44); 468 BZ_ITUR(45); BZ_ITUR(46); BZ_ITUR(47); BZ_ITUR(48); BZ_ITUR(49); 469 470 # undef BZ_ITUR 471 472 } else { 473 /*--- slow version which correctly handles all situations ---*/ 474 for (i = gs; i <= ge; i++) 475 s->rfreq[bt][ mtfv[i] ]++; 476 } 477 478 gs = ge+1; 479 } 480 if (s->verbosity >= 3) { 481 VPrintf2 ( " pass %d: size is %d, grp uses are ", 482 iter+1, totc/8 ); 483 for (t = 0; t < nGroups; t++) 484 VPrintf1 ( "%d ", fave[t] ); 485 VPrintf0 ( "\n" ); 486 } 487 488 /*-- 489 Recompute the tables based on the accumulated frequencies. 490 --*/ 491 /* maxLen was changed from 20 to 17 in bzip2-1.0.3. See 492 comment in huffman.c for details. */ 493 for (t = 0; t < nGroups; t++) 494 BZ2_hbMakeCodeLengths ( &(s->len[t][0]), &(s->rfreq[t][0]), 495 alphaSize, 17 /*20*/ ); 496 } 497 498 499 AssertH( nGroups < 8, 3002 ); 500 AssertH( nSelectors < 32768 && 501 nSelectors <= (2 + (900000 / BZ_G_SIZE)), 502 3003 ); 503 504 505 /*--- Compute MTF values for the selectors. ---*/ 506 { 507 UChar pos[BZ_N_GROUPS], ll_i, tmp2, tmp; 508 for (i = 0; i < nGroups; i++) pos[i] = i; 509 for (i = 0; i < nSelectors; i++) { 510 ll_i = s->selector[i]; 511 j = 0; 512 tmp = pos[j]; 513 while ( ll_i != tmp ) { 514 j++; 515 tmp2 = tmp; 516 tmp = pos[j]; 517 pos[j] = tmp2; 518 }; 519 pos[0] = tmp; 520 s->selectorMtf[i] = j; 521 } 522 }; 523 524 /*--- Assign actual codes for the tables. --*/ 525 for (t = 0; t < nGroups; t++) { 526 minLen = 32; 527 maxLen = 0; 528 for (i = 0; i < alphaSize; i++) { 529 if (s->len[t][i] > maxLen) maxLen = s->len[t][i]; 530 if (s->len[t][i] < minLen) minLen = s->len[t][i]; 531 } 532 AssertH ( !(maxLen > 17 /*20*/ ), 3004 ); 533 AssertH ( !(minLen < 1), 3005 ); 534 BZ2_hbAssignCodes ( &(s->code[t][0]), &(s->len[t][0]), 535 minLen, maxLen, alphaSize ); 536 } 537 538 /*--- Transmit the mapping table. ---*/ 539 { 540 Bool inUse16[16]; 541 for (i = 0; i < 16; i++) { 542 inUse16[i] = False; 543 for (j = 0; j < 16; j++) 544 if (s->inUse[i * 16 + j]) inUse16[i] = True; 545 } 546 547 nBytes = s->numZ; 548 for (i = 0; i < 16; i++) 549 if (inUse16[i]) bsW(s,1,1); else bsW(s,1,0); 550 551 for (i = 0; i < 16; i++) 552 if (inUse16[i]) 553 for (j = 0; j < 16; j++) { 554 if (s->inUse[i * 16 + j]) bsW(s,1,1); else bsW(s,1,0); 555 } 556 557 if (s->verbosity >= 3) 558 VPrintf1( " bytes: mapping %d, ", s->numZ-nBytes ); 559 } 560 561 /*--- Now the selectors. ---*/ 562 nBytes = s->numZ; 563 bsW ( s, 3, nGroups ); 564 bsW ( s, 15, nSelectors ); 565 for (i = 0; i < nSelectors; i++) { 566 for (j = 0; j < s->selectorMtf[i]; j++) bsW(s,1,1); 567 bsW(s,1,0); 568 } 569 if (s->verbosity >= 3) 570 VPrintf1( "selectors %d, ", s->numZ-nBytes ); 571 572 /*--- Now the coding tables. ---*/ 573 nBytes = s->numZ; 574 575 for (t = 0; t < nGroups; t++) { 576 Int32 curr = s->len[t][0]; 577 bsW ( s, 5, curr ); 578 for (i = 0; i < alphaSize; i++) { 579 while (curr < s->len[t][i]) { bsW(s,2,2); curr++; /* 10 */ }; 580 while (curr > s->len[t][i]) { bsW(s,2,3); curr--; /* 11 */ }; 581 bsW ( s, 1, 0 ); 582 } 583 } 584 585 if (s->verbosity >= 3) 586 VPrintf1 ( "code lengths %d, ", s->numZ-nBytes ); 587 588 /*--- And finally, the block data proper ---*/ 589 nBytes = s->numZ; 590 selCtr = 0; 591 gs = 0; 592 while (True) { 593 if (gs >= s->nMTF) break; 594 ge = gs + BZ_G_SIZE - 1; 595 if (ge >= s->nMTF) ge = s->nMTF-1; 596 AssertH ( s->selector[selCtr] < nGroups, 3006 ); 597 598 if (nGroups == 6 && 50 == ge-gs+1) { 599 /*--- fast track the common case ---*/ 600 UInt16 mtfv_i; 601 UChar* s_len_sel_selCtr 602 = &(s->len[s->selector[selCtr]][0]); 603 Int32* s_code_sel_selCtr 604 = &(s->code[s->selector[selCtr]][0]); 605 606 # define BZ_ITAH(nn) \ 607 mtfv_i = mtfv[gs+(nn)]; \ 608 bsW ( s, \ 609 s_len_sel_selCtr[mtfv_i], \ 610 s_code_sel_selCtr[mtfv_i] ) 611 612 BZ_ITAH(0); BZ_ITAH(1); BZ_ITAH(2); BZ_ITAH(3); BZ_ITAH(4); 613 BZ_ITAH(5); BZ_ITAH(6); BZ_ITAH(7); BZ_ITAH(8); BZ_ITAH(9); 614 BZ_ITAH(10); BZ_ITAH(11); BZ_ITAH(12); BZ_ITAH(13); BZ_ITAH(14); 615 BZ_ITAH(15); BZ_ITAH(16); BZ_ITAH(17); BZ_ITAH(18); BZ_ITAH(19); 616 BZ_ITAH(20); BZ_ITAH(21); BZ_ITAH(22); BZ_ITAH(23); BZ_ITAH(24); 617 BZ_ITAH(25); BZ_ITAH(26); BZ_ITAH(27); BZ_ITAH(28); BZ_ITAH(29); 618 BZ_ITAH(30); BZ_ITAH(31); BZ_ITAH(32); BZ_ITAH(33); BZ_ITAH(34); 619 BZ_ITAH(35); BZ_ITAH(36); BZ_ITAH(37); BZ_ITAH(38); BZ_ITAH(39); 620 BZ_ITAH(40); BZ_ITAH(41); BZ_ITAH(42); BZ_ITAH(43); BZ_ITAH(44); 621 BZ_ITAH(45); BZ_ITAH(46); BZ_ITAH(47); BZ_ITAH(48); BZ_ITAH(49); 622 623 # undef BZ_ITAH 624 625 } else { 626 /*--- slow version which correctly handles all situations ---*/ 627 for (i = gs; i <= ge; i++) { 628 bsW ( s, 629 s->len [s->selector[selCtr]] [mtfv[i]], 630 s->code [s->selector[selCtr]] [mtfv[i]] ); 631 } 632 } 633 634 635 gs = ge+1; 636 selCtr++; 637 } 638 AssertH( selCtr == nSelectors, 3007 ); 639 640 if (s->verbosity >= 3) 641 VPrintf1( "codes %d\n", s->numZ-nBytes ); 642 } 643 644 645 /*---------------------------------------------------*/ 646 void BZ2_compressBlock ( EState* s, Bool is_last_block ) 647 { 648 if (s->nblock > 0) { 649 650 BZ_FINALISE_CRC ( s->blockCRC ); 651 s->combinedCRC = (s->combinedCRC << 1) | (s->combinedCRC >> 31); 652 s->combinedCRC ^= s->blockCRC; 653 if (s->blockNo > 1) s->numZ = 0; 654 655 if (s->verbosity >= 2) 656 VPrintf4( " block %d: crc = 0x%08x, " 657 "combined CRC = 0x%08x, size = %d\n", 658 s->blockNo, s->blockCRC, s->combinedCRC, s->nblock ); 659 660 BZ2_blockSort ( s ); 661 } 662 663 s->zbits = (UChar*) (&((UChar*)s->arr2)[s->nblock]); 664 665 /*-- If this is the first block, create the stream header. --*/ 666 if (s->blockNo == 1) { 667 BZ2_bsInitWrite ( s ); 668 bsPutUChar ( s, BZ_HDR_B ); 669 bsPutUChar ( s, BZ_HDR_Z ); 670 bsPutUChar ( s, BZ_HDR_h ); 671 bsPutUChar ( s, (UChar)(BZ_HDR_0 + s->blockSize100k) ); 672 } 673 674 if (s->nblock > 0) { 675 676 bsPutUChar ( s, 0x31 ); bsPutUChar ( s, 0x41 ); 677 bsPutUChar ( s, 0x59 ); bsPutUChar ( s, 0x26 ); 678 bsPutUChar ( s, 0x53 ); bsPutUChar ( s, 0x59 ); 679 680 /*-- Now the block's CRC, so it is in a known place. --*/ 681 bsPutUInt32 ( s, s->blockCRC ); 682 683 /*-- 684 Now a single bit indicating (non-)randomisation. 685 As of version 0.9.5, we use a better sorting algorithm 686 which makes randomisation unnecessary. So always set 687 the randomised bit to 'no'. Of course, the decoder 688 still needs to be able to handle randomised blocks 689 so as to maintain backwards compatibility with 690 older versions of bzip2. 691 --*/ 692 bsW(s,1,0); 693 694 bsW ( s, 24, s->origPtr ); 695 generateMTFValues ( s ); 696 sendMTFValues ( s ); 697 } 698 699 700 /*-- If this is the last block, add the stream trailer. --*/ 701 if (is_last_block) { 702 703 bsPutUChar ( s, 0x17 ); bsPutUChar ( s, 0x72 ); 704 bsPutUChar ( s, 0x45 ); bsPutUChar ( s, 0x38 ); 705 bsPutUChar ( s, 0x50 ); bsPutUChar ( s, 0x90 ); 706 bsPutUInt32 ( s, s->combinedCRC ); 707 if (s->verbosity >= 2) 708 VPrintf1( " final combined CRC = 0x%08x\n ", s->combinedCRC ); 709 bsFinishWrite ( s ); 710 } 711 } 712 713 714 /*-------------------------------------------------------------*/ 715 /*--- end compress.c ---*/ 716 /*-------------------------------------------------------------*/