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