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