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 #include <compiler.h> 71 72 /*---------------------------------------------------*/ 73 /*--- Bit stream I/O ---*/ 74 /*---------------------------------------------------*/ 75 76 /*---------------------------------------------------*/ BZ2_bsInitWrite(EState * s)77 void BZ2_bsInitWrite ( EState* s ) 78 { 79 s->bsLive = 0; 80 s->bsBuff = 0; 81 } 82 83 84 /*---------------------------------------------------*/ 85 static bsFinishWrite(EState * s)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__ bsW(EState * s,Int32 n,UInt32 v)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 bsPutUInt32(EState * s,UInt32 u)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 bsPutUChar(EState * s,UChar c)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 makeMaps_e(EState * s)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 generateMTFValues(EState * s)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 sendMTFValues(EState * s)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; 284 Int32 nBytes __maybe_unused; 285 286 /*-- 287 UChar len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; 288 is a global since the decoder also needs it. 289 290 Int32 code[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; 291 Int32 rfreq[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; 292 are also globals only used in this proc. 293 Made global to keep stack frame size small. 294 --*/ 295 296 297 UInt16 cost[BZ_N_GROUPS]; 298 Int32 fave[BZ_N_GROUPS]; 299 300 UInt16* mtfv = s->mtfv; 301 302 if (s->verbosity >= 3) 303 VPrintf3( " %d in block, %d after MTF & 1-2 coding, " 304 "%d+2 syms in use\n", 305 s->nblock, s->nMTF, s->nInUse ); 306 307 alphaSize = s->nInUse+2; 308 for (t = 0; t < BZ_N_GROUPS; t++) 309 for (v = 0; v < alphaSize; v++) 310 s->len[t][v] = BZ_GREATER_ICOST; 311 312 /*--- Decide how many coding tables to use ---*/ 313 AssertH ( s->nMTF > 0, 3001 ); 314 if (s->nMTF < 200) nGroups = 2; else 315 if (s->nMTF < 600) nGroups = 3; else 316 if (s->nMTF < 1200) nGroups = 4; else 317 if (s->nMTF < 2400) nGroups = 5; else 318 nGroups = 6; 319 320 /*--- Generate an initial set of coding tables ---*/ 321 { 322 Int32 nPart, remF, tFreq, aFreq; 323 324 nPart = nGroups; 325 remF = s->nMTF; 326 gs = 0; 327 while (nPart > 0) { 328 tFreq = remF / nPart; 329 ge = gs-1; 330 aFreq = 0; 331 while (aFreq < tFreq && ge < alphaSize-1) { 332 ge++; 333 aFreq += s->mtfFreq[ge]; 334 } 335 336 if (ge > gs 337 && nPart != nGroups && nPart != 1 338 && ((nGroups-nPart) % 2 == 1)) { 339 aFreq -= s->mtfFreq[ge]; 340 ge--; 341 } 342 343 if (s->verbosity >= 3) 344 VPrintf5( " initial group %d, [%d .. %d], " 345 "has %d syms (%4.1f%%)\n", 346 nPart, gs, ge, aFreq, 347 (100.0 * (float)aFreq) / (float)(s->nMTF) ); 348 349 for (v = 0; v < alphaSize; v++) 350 if (v >= gs && v <= ge) 351 s->len[nPart-1][v] = BZ_LESSER_ICOST; else 352 s->len[nPart-1][v] = BZ_GREATER_ICOST; 353 354 nPart--; 355 gs = ge+1; 356 remF -= aFreq; 357 } 358 } 359 360 /*--- 361 Iterate up to BZ_N_ITERS times to improve the tables. 362 ---*/ 363 for (iter = 0; iter < BZ_N_ITERS; iter++) { 364 365 for (t = 0; t < nGroups; t++) fave[t] = 0; 366 367 for (t = 0; t < nGroups; t++) 368 for (v = 0; v < alphaSize; v++) 369 s->rfreq[t][v] = 0; 370 371 /*--- 372 Set up an auxiliary length table which is used to fast-track 373 the common case (nGroups == 6). 374 ---*/ 375 if (nGroups == 6) { 376 for (v = 0; v < alphaSize; v++) { 377 s->len_pack[v][0] = (s->len[1][v] << 16) | s->len[0][v]; 378 s->len_pack[v][1] = (s->len[3][v] << 16) | s->len[2][v]; 379 s->len_pack[v][2] = (s->len[5][v] << 16) | s->len[4][v]; 380 } 381 } 382 383 nSelectors = 0; 384 totc = 0; 385 gs = 0; 386 while (True) { 387 388 /*--- Set group start & end marks. --*/ 389 if (gs >= s->nMTF) break; 390 ge = gs + BZ_G_SIZE - 1; 391 if (ge >= s->nMTF) ge = s->nMTF-1; 392 393 /*-- 394 Calculate the cost of this group as coded 395 by each of the coding tables. 396 --*/ 397 for (t = 0; t < nGroups; t++) cost[t] = 0; 398 399 if (nGroups == 6 && 50 == ge-gs+1) { 400 /*--- fast track the common case ---*/ 401 register UInt32 cost01, cost23, cost45; 402 register UInt16 icv; 403 cost01 = cost23 = cost45 = 0; 404 405 # define BZ_ITER(nn) \ 406 icv = mtfv[gs+(nn)]; \ 407 cost01 += s->len_pack[icv][0]; \ 408 cost23 += s->len_pack[icv][1]; \ 409 cost45 += s->len_pack[icv][2]; \ 410 411 BZ_ITER(0); BZ_ITER(1); BZ_ITER(2); BZ_ITER(3); BZ_ITER(4); 412 BZ_ITER(5); BZ_ITER(6); BZ_ITER(7); BZ_ITER(8); BZ_ITER(9); 413 BZ_ITER(10); BZ_ITER(11); BZ_ITER(12); BZ_ITER(13); BZ_ITER(14); 414 BZ_ITER(15); BZ_ITER(16); BZ_ITER(17); BZ_ITER(18); BZ_ITER(19); 415 BZ_ITER(20); BZ_ITER(21); BZ_ITER(22); BZ_ITER(23); BZ_ITER(24); 416 BZ_ITER(25); BZ_ITER(26); BZ_ITER(27); BZ_ITER(28); BZ_ITER(29); 417 BZ_ITER(30); BZ_ITER(31); BZ_ITER(32); BZ_ITER(33); BZ_ITER(34); 418 BZ_ITER(35); BZ_ITER(36); BZ_ITER(37); BZ_ITER(38); BZ_ITER(39); 419 BZ_ITER(40); BZ_ITER(41); BZ_ITER(42); BZ_ITER(43); BZ_ITER(44); 420 BZ_ITER(45); BZ_ITER(46); BZ_ITER(47); BZ_ITER(48); BZ_ITER(49); 421 422 # undef BZ_ITER 423 424 cost[0] = cost01 & 0xffff; cost[1] = cost01 >> 16; 425 cost[2] = cost23 & 0xffff; cost[3] = cost23 >> 16; 426 cost[4] = cost45 & 0xffff; cost[5] = cost45 >> 16; 427 428 } else { 429 /*--- slow version which correctly handles all situations ---*/ 430 for (i = gs; i <= ge; i++) { 431 UInt16 icv = mtfv[i]; 432 for (t = 0; t < nGroups; t++) cost[t] += s->len[t][icv]; 433 } 434 } 435 436 /*-- 437 Find the coding table which is best for this group, 438 and record its identity in the selector table. 439 --*/ 440 bc = 999999999; bt = -1; 441 for (t = 0; t < nGroups; t++) 442 if (cost[t] < bc) { bc = cost[t]; bt = t; }; 443 totc += bc; 444 fave[bt]++; 445 s->selector[nSelectors] = bt; 446 nSelectors++; 447 448 /*-- 449 Increment the symbol frequencies for the selected table. 450 --*/ 451 if (nGroups == 6 && 50 == ge-gs+1) { 452 /*--- fast track the common case ---*/ 453 454 # define BZ_ITUR(nn) s->rfreq[bt][ mtfv[gs+(nn)] ]++ 455 456 BZ_ITUR(0); BZ_ITUR(1); BZ_ITUR(2); BZ_ITUR(3); BZ_ITUR(4); 457 BZ_ITUR(5); BZ_ITUR(6); BZ_ITUR(7); BZ_ITUR(8); BZ_ITUR(9); 458 BZ_ITUR(10); BZ_ITUR(11); BZ_ITUR(12); BZ_ITUR(13); BZ_ITUR(14); 459 BZ_ITUR(15); BZ_ITUR(16); BZ_ITUR(17); BZ_ITUR(18); BZ_ITUR(19); 460 BZ_ITUR(20); BZ_ITUR(21); BZ_ITUR(22); BZ_ITUR(23); BZ_ITUR(24); 461 BZ_ITUR(25); BZ_ITUR(26); BZ_ITUR(27); BZ_ITUR(28); BZ_ITUR(29); 462 BZ_ITUR(30); BZ_ITUR(31); BZ_ITUR(32); BZ_ITUR(33); BZ_ITUR(34); 463 BZ_ITUR(35); BZ_ITUR(36); BZ_ITUR(37); BZ_ITUR(38); BZ_ITUR(39); 464 BZ_ITUR(40); BZ_ITUR(41); BZ_ITUR(42); BZ_ITUR(43); BZ_ITUR(44); 465 BZ_ITUR(45); BZ_ITUR(46); BZ_ITUR(47); BZ_ITUR(48); BZ_ITUR(49); 466 467 # undef BZ_ITUR 468 469 } else { 470 /*--- slow version which correctly handles all situations ---*/ 471 for (i = gs; i <= ge; i++) 472 s->rfreq[bt][ mtfv[i] ]++; 473 } 474 475 gs = ge+1; 476 } 477 if (s->verbosity >= 3) { 478 VPrintf2 ( " pass %d: size is %d, grp uses are ", 479 iter+1, totc/8 ); 480 for (t = 0; t < nGroups; t++) 481 VPrintf1 ( "%d ", fave[t] ); 482 VPrintf0 ( "\n" ); 483 } 484 485 /*-- 486 Recompute the tables based on the accumulated frequencies. 487 --*/ 488 /* maxLen was changed from 20 to 17 in bzip2-1.0.3. See 489 comment in huffman.c for details. */ 490 for (t = 0; t < nGroups; t++) 491 BZ2_hbMakeCodeLengths ( &(s->len[t][0]), &(s->rfreq[t][0]), 492 alphaSize, 17 /*20*/ ); 493 } 494 495 496 AssertH( nGroups < 8, 3002 ); 497 AssertH( nSelectors < 32768 && 498 nSelectors <= (2 + (900000 / BZ_G_SIZE)), 499 3003 ); 500 501 502 /*--- Compute MTF values for the selectors. ---*/ 503 { 504 UChar pos[BZ_N_GROUPS], ll_i, tmp2, tmp; 505 for (i = 0; i < nGroups; i++) pos[i] = i; 506 for (i = 0; i < nSelectors; i++) { 507 ll_i = s->selector[i]; 508 j = 0; 509 tmp = pos[j]; 510 while ( ll_i != tmp ) { 511 j++; 512 tmp2 = tmp; 513 tmp = pos[j]; 514 pos[j] = tmp2; 515 }; 516 pos[0] = tmp; 517 s->selectorMtf[i] = j; 518 } 519 }; 520 521 /*--- Assign actual codes for the tables. --*/ 522 for (t = 0; t < nGroups; t++) { 523 minLen = 32; 524 maxLen = 0; 525 for (i = 0; i < alphaSize; i++) { 526 if (s->len[t][i] > maxLen) maxLen = s->len[t][i]; 527 if (s->len[t][i] < minLen) minLen = s->len[t][i]; 528 } 529 AssertH ( !(maxLen > 17 /*20*/ ), 3004 ); 530 AssertH ( !(minLen < 1), 3005 ); 531 BZ2_hbAssignCodes ( &(s->code[t][0]), &(s->len[t][0]), 532 minLen, maxLen, alphaSize ); 533 } 534 535 /*--- Transmit the mapping table. ---*/ 536 { 537 Bool inUse16[16]; 538 for (i = 0; i < 16; i++) { 539 inUse16[i] = False; 540 for (j = 0; j < 16; j++) 541 if (s->inUse[i * 16 + j]) inUse16[i] = True; 542 } 543 544 nBytes = s->numZ; 545 for (i = 0; i < 16; i++) 546 if (inUse16[i]) bsW(s,1,1); else bsW(s,1,0); 547 548 for (i = 0; i < 16; i++) 549 if (inUse16[i]) 550 for (j = 0; j < 16; j++) { 551 if (s->inUse[i * 16 + j]) bsW(s,1,1); else bsW(s,1,0); 552 } 553 554 if (s->verbosity >= 3) 555 VPrintf1( " bytes: mapping %d, ", s->numZ-nBytes ); 556 } 557 558 /*--- Now the selectors. ---*/ 559 nBytes = s->numZ; 560 bsW ( s, 3, nGroups ); 561 bsW ( s, 15, nSelectors ); 562 for (i = 0; i < nSelectors; i++) { 563 for (j = 0; j < s->selectorMtf[i]; j++) bsW(s,1,1); 564 bsW(s,1,0); 565 } 566 if (s->verbosity >= 3) 567 VPrintf1( "selectors %d, ", s->numZ-nBytes ); 568 569 /*--- Now the coding tables. ---*/ 570 nBytes = s->numZ; 571 572 for (t = 0; t < nGroups; t++) { 573 Int32 curr = s->len[t][0]; 574 bsW ( s, 5, curr ); 575 for (i = 0; i < alphaSize; i++) { 576 while (curr < s->len[t][i]) { bsW(s,2,2); curr++; /* 10 */ }; 577 while (curr > s->len[t][i]) { bsW(s,2,3); curr--; /* 11 */ }; 578 bsW ( s, 1, 0 ); 579 } 580 } 581 582 if (s->verbosity >= 3) 583 VPrintf1 ( "code lengths %d, ", s->numZ-nBytes ); 584 585 /*--- And finally, the block data proper ---*/ 586 nBytes = s->numZ; 587 selCtr = 0; 588 gs = 0; 589 while (True) { 590 if (gs >= s->nMTF) break; 591 ge = gs + BZ_G_SIZE - 1; 592 if (ge >= s->nMTF) ge = s->nMTF-1; 593 AssertH ( s->selector[selCtr] < nGroups, 3006 ); 594 595 if (nGroups == 6 && 50 == ge-gs+1) { 596 /*--- fast track the common case ---*/ 597 UInt16 mtfv_i; 598 UChar* s_len_sel_selCtr 599 = &(s->len[s->selector[selCtr]][0]); 600 Int32* s_code_sel_selCtr 601 = &(s->code[s->selector[selCtr]][0]); 602 603 # define BZ_ITAH(nn) \ 604 mtfv_i = mtfv[gs+(nn)]; \ 605 bsW ( s, \ 606 s_len_sel_selCtr[mtfv_i], \ 607 s_code_sel_selCtr[mtfv_i] ) 608 609 BZ_ITAH(0); BZ_ITAH(1); BZ_ITAH(2); BZ_ITAH(3); BZ_ITAH(4); 610 BZ_ITAH(5); BZ_ITAH(6); BZ_ITAH(7); BZ_ITAH(8); BZ_ITAH(9); 611 BZ_ITAH(10); BZ_ITAH(11); BZ_ITAH(12); BZ_ITAH(13); BZ_ITAH(14); 612 BZ_ITAH(15); BZ_ITAH(16); BZ_ITAH(17); BZ_ITAH(18); BZ_ITAH(19); 613 BZ_ITAH(20); BZ_ITAH(21); BZ_ITAH(22); BZ_ITAH(23); BZ_ITAH(24); 614 BZ_ITAH(25); BZ_ITAH(26); BZ_ITAH(27); BZ_ITAH(28); BZ_ITAH(29); 615 BZ_ITAH(30); BZ_ITAH(31); BZ_ITAH(32); BZ_ITAH(33); BZ_ITAH(34); 616 BZ_ITAH(35); BZ_ITAH(36); BZ_ITAH(37); BZ_ITAH(38); BZ_ITAH(39); 617 BZ_ITAH(40); BZ_ITAH(41); BZ_ITAH(42); BZ_ITAH(43); BZ_ITAH(44); 618 BZ_ITAH(45); BZ_ITAH(46); BZ_ITAH(47); BZ_ITAH(48); BZ_ITAH(49); 619 620 # undef BZ_ITAH 621 622 } else { 623 /*--- slow version which correctly handles all situations ---*/ 624 for (i = gs; i <= ge; i++) { 625 bsW ( s, 626 s->len [s->selector[selCtr]] [mtfv[i]], 627 s->code [s->selector[selCtr]] [mtfv[i]] ); 628 } 629 } 630 631 632 gs = ge+1; 633 selCtr++; 634 } 635 AssertH( selCtr == nSelectors, 3007 ); 636 637 if (s->verbosity >= 3) 638 VPrintf1( "codes %d\n", s->numZ-nBytes ); 639 } 640 641 642 /*---------------------------------------------------*/ BZ2_compressBlock(EState * s,Bool is_last_block)643 void BZ2_compressBlock ( EState* s, Bool is_last_block ) 644 { 645 if (s->nblock > 0) { 646 647 BZ_FINALISE_CRC ( s->blockCRC ); 648 s->combinedCRC = (s->combinedCRC << 1) | (s->combinedCRC >> 31); 649 s->combinedCRC ^= s->blockCRC; 650 if (s->blockNo > 1) s->numZ = 0; 651 652 if (s->verbosity >= 2) 653 VPrintf4( " block %d: crc = 0x%08x, " 654 "combined CRC = 0x%08x, size = %d\n", 655 s->blockNo, s->blockCRC, s->combinedCRC, s->nblock ); 656 657 BZ2_blockSort ( s ); 658 } 659 660 s->zbits = (UChar*) (&((UChar*)s->arr2)[s->nblock]); 661 662 /*-- If this is the first block, create the stream header. --*/ 663 if (s->blockNo == 1) { 664 BZ2_bsInitWrite ( s ); 665 bsPutUChar ( s, BZ_HDR_B ); 666 bsPutUChar ( s, BZ_HDR_Z ); 667 bsPutUChar ( s, BZ_HDR_h ); 668 bsPutUChar ( s, (UChar)(BZ_HDR_0 + s->blockSize100k) ); 669 } 670 671 if (s->nblock > 0) { 672 673 bsPutUChar ( s, 0x31 ); bsPutUChar ( s, 0x41 ); 674 bsPutUChar ( s, 0x59 ); bsPutUChar ( s, 0x26 ); 675 bsPutUChar ( s, 0x53 ); bsPutUChar ( s, 0x59 ); 676 677 /*-- Now the block's CRC, so it is in a known place. --*/ 678 bsPutUInt32 ( s, s->blockCRC ); 679 680 /*-- 681 Now a single bit indicating (non-)randomisation. 682 As of version 0.9.5, we use a better sorting algorithm 683 which makes randomisation unnecessary. So always set 684 the randomised bit to 'no'. Of course, the decoder 685 still needs to be able to handle randomised blocks 686 so as to maintain backwards compatibility with 687 older versions of bzip2. 688 --*/ 689 bsW(s,1,0); 690 691 bsW ( s, 24, s->origPtr ); 692 generateMTFValues ( s ); 693 sendMTFValues ( s ); 694 } 695 696 697 /*-- If this is the last block, add the stream trailer. --*/ 698 if (is_last_block) { 699 700 bsPutUChar ( s, 0x17 ); bsPutUChar ( s, 0x72 ); 701 bsPutUChar ( s, 0x45 ); bsPutUChar ( s, 0x38 ); 702 bsPutUChar ( s, 0x50 ); bsPutUChar ( s, 0x90 ); 703 bsPutUInt32 ( s, s->combinedCRC ); 704 if (s->verbosity >= 2) 705 VPrintf1( " final combined CRC = 0x%08x\n ", s->combinedCRC ); 706 bsFinishWrite ( s ); 707 } 708 } 709 710 711 /*-------------------------------------------------------------*/ 712 /*--- end compress.c ---*/ 713 /*-------------------------------------------------------------*/ 714