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