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 "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 for (t = 0; t < nGroups; t++) 492 BZ2_hbMakeCodeLengths ( &(s->len[t][0]), &(s->rfreq[t][0]), 493 alphaSize, 20 ); 494 } 495 496 497 AssertH( nGroups < 8, 3002 ); 498 AssertH( nSelectors < 32768 && 499 nSelectors <= (2 + (900000 / BZ_G_SIZE)), 500 3003 ); 501 502 503 /*--- Compute MTF values for the selectors. ---*/ 504 { 505 UChar pos[BZ_N_GROUPS], ll_i, tmp2, tmp; 506 for (i = 0; i < nGroups; i++) pos[i] = i; 507 for (i = 0; i < nSelectors; i++) { 508 ll_i = s->selector[i]; 509 j = 0; 510 tmp = pos[j]; 511 while ( ll_i != tmp ) { 512 j++; 513 tmp2 = tmp; 514 tmp = pos[j]; 515 pos[j] = tmp2; 516 }; 517 pos[0] = tmp; 518 s->selectorMtf[i] = j; 519 } 520 }; 521 522 /*--- Assign actual codes for the tables. --*/ 523 for (t = 0; t < nGroups; t++) { 524 minLen = 32; 525 maxLen = 0; 526 for (i = 0; i < alphaSize; i++) { 527 if (s->len[t][i] > maxLen) maxLen = s->len[t][i]; 528 if (s->len[t][i] < minLen) minLen = s->len[t][i]; 529 } 530 AssertH ( !(maxLen > 20), 3004 ); 531 AssertH ( !(minLen < 1), 3005 ); 532 BZ2_hbAssignCodes ( &(s->code[t][0]), &(s->len[t][0]), 533 minLen, maxLen, alphaSize ); 534 } 535 536 /*--- Transmit the mapping table. ---*/ 537 { 538 Bool inUse16[16]; 539 for (i = 0; i < 16; i++) { 540 inUse16[i] = False; 541 for (j = 0; j < 16; j++) 542 if (s->inUse[i * 16 + j]) inUse16[i] = True; 543 } 544 545 nBytes = s->numZ; 546 for (i = 0; i < 16; i++) 547 if (inUse16[i]) bsW(s,1,1); else bsW(s,1,0); 548 549 for (i = 0; i < 16; i++) 550 if (inUse16[i]) 551 for (j = 0; j < 16; j++) { 552 if (s->inUse[i * 16 + j]) bsW(s,1,1); else bsW(s,1,0); 553 } 554 555 if (s->verbosity >= 3) 556 VPrintf1( " bytes: mapping %d, ", s->numZ-nBytes ); 557 } 558 559 /*--- Now the selectors. ---*/ 560 nBytes = s->numZ; 561 bsW ( s, 3, nGroups ); 562 bsW ( s, 15, nSelectors ); 563 for (i = 0; i < nSelectors; i++) { 564 for (j = 0; j < s->selectorMtf[i]; j++) bsW(s,1,1); 565 bsW(s,1,0); 566 } 567 if (s->verbosity >= 3) 568 VPrintf1( "selectors %d, ", s->numZ-nBytes ); 569 570 /*--- Now the coding tables. ---*/ 571 nBytes = s->numZ; 572 573 for (t = 0; t < nGroups; t++) { 574 Int32 curr = s->len[t][0]; 575 bsW ( s, 5, curr ); 576 for (i = 0; i < alphaSize; i++) { 577 while (curr < s->len[t][i]) { bsW(s,2,2); curr++; /* 10 */ }; 578 while (curr > s->len[t][i]) { bsW(s,2,3); curr--; /* 11 */ }; 579 bsW ( s, 1, 0 ); 580 } 581 } 582 583 if (s->verbosity >= 3) 584 VPrintf1 ( "code lengths %d, ", s->numZ-nBytes ); 585 586 /*--- And finally, the block data proper ---*/ 587 nBytes = s->numZ; 588 selCtr = 0; 589 gs = 0; 590 while (True) { 591 if (gs >= s->nMTF) break; 592 ge = gs + BZ_G_SIZE - 1; 593 if (ge >= s->nMTF) ge = s->nMTF-1; 594 AssertH ( s->selector[selCtr] < nGroups, 3006 ); 595 596 if (nGroups == 6 && 50 == ge-gs+1) { 597 /*--- fast track the common case ---*/ 598 UInt16 mtfv_i; 599 UChar* s_len_sel_selCtr 600 = &(s->len[s->selector[selCtr]][0]); 601 Int32* s_code_sel_selCtr 602 = &(s->code[s->selector[selCtr]][0]); 603 604 # define BZ_ITAH(nn) \ 605 mtfv_i = mtfv[gs+(nn)]; \ 606 bsW ( s, \ 607 s_len_sel_selCtr[mtfv_i], \ 608 s_code_sel_selCtr[mtfv_i] ) 609 610 BZ_ITAH(0); BZ_ITAH(1); BZ_ITAH(2); BZ_ITAH(3); BZ_ITAH(4); 611 BZ_ITAH(5); BZ_ITAH(6); BZ_ITAH(7); BZ_ITAH(8); BZ_ITAH(9); 612 BZ_ITAH(10); BZ_ITAH(11); BZ_ITAH(12); BZ_ITAH(13); BZ_ITAH(14); 613 BZ_ITAH(15); BZ_ITAH(16); BZ_ITAH(17); BZ_ITAH(18); BZ_ITAH(19); 614 BZ_ITAH(20); BZ_ITAH(21); BZ_ITAH(22); BZ_ITAH(23); BZ_ITAH(24); 615 BZ_ITAH(25); BZ_ITAH(26); BZ_ITAH(27); BZ_ITAH(28); BZ_ITAH(29); 616 BZ_ITAH(30); BZ_ITAH(31); BZ_ITAH(32); BZ_ITAH(33); BZ_ITAH(34); 617 BZ_ITAH(35); BZ_ITAH(36); BZ_ITAH(37); BZ_ITAH(38); BZ_ITAH(39); 618 BZ_ITAH(40); BZ_ITAH(41); BZ_ITAH(42); BZ_ITAH(43); BZ_ITAH(44); 619 BZ_ITAH(45); BZ_ITAH(46); BZ_ITAH(47); BZ_ITAH(48); BZ_ITAH(49); 620 621 # undef BZ_ITAH 622 623 } else { 624 /*--- slow version which correctly handles all situations ---*/ 625 for (i = gs; i <= ge; i++) { 626 bsW ( s, 627 s->len [s->selector[selCtr]] [mtfv[i]], 628 s->code [s->selector[selCtr]] [mtfv[i]] ); 629 } 630 } 631 632 633 gs = ge+1; 634 selCtr++; 635 } 636 AssertH( selCtr == nSelectors, 3007 ); 637 638 if (s->verbosity >= 3) 639 VPrintf1( "codes %d\n", s->numZ-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%8x, " 655 "combined CRC = 0x%8x, 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, 'B' ); 667 bsPutUChar ( s, 'Z' ); 668 bsPutUChar ( s, 'h' ); 669 bsPutUChar ( s, (UChar)('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%x\n ", s->combinedCRC ); 707 bsFinishWrite ( s ); 708 } 709 } 710 711 712 /*-------------------------------------------------------------*/ 713 /*--- end compress.c ---*/ 714 /*-------------------------------------------------------------*/ 715