#include "bzlib_private.h"
Go to the source code of this file.
Defines | |
#define | bsNEEDW(nz) |
#define | BZ_LESSER_ICOST 0 |
#define | BZ_GREATER_ICOST 15 |
Functions | |
void | bsInitWrite (EState *s) |
void | bsFinishWrite (EState *s) |
void | bsW (EState *s, Int32 n, UInt32 v) |
void | bsPutUInt32 (EState *s, UInt32 u) |
void | bsPutUChar (EState *s, UChar c) |
void | makeMaps_e (EState *s) |
void | generateMTFValues (EState *s) |
void | sendMTFValues (EState *s) |
void | compressBlock (EState *s, Bool is_last_block) |
|
Definition at line 274 of file bzlib/compress.c. |
|
Definition at line 273 of file bzlib/compress.c. |
|
Value: { \ while (s->bsLive >= 8) { \ s->zbits[s->numZ] \ = (UChar)(s->bsBuff >> 24); \ s->numZ++; \ s->bsBuff <<= 8; \ s->bsLive -= 8; \ } \ } Definition at line 102 of file bzlib/compress.c. Referenced by bsW().
|
|
Definition at line 90 of file bzlib/compress.c. Referenced by compressBlock().
|
|
Definition at line 81 of file bzlib/compress.c. Referenced by compressBlock().
|
|
Definition at line 137 of file bzlib/compress.c. Referenced by compressBlock(), and main().
00138 { 00139 bsW( s, 8, (UInt32)c ); 00140 } |
|
Definition at line 126 of file bzlib/compress.c. Referenced by compressBlock(), and main().
|
|
Definition at line 116 of file bzlib/compress.c. Referenced by bsPutUChar(), bsPutUInt32(), compressBlock(), and sendMTFValues().
|
|
Definition at line 557 of file bzlib/compress.c. Referenced by handle_compress().
00558 { 00559 if (s->nblock > 0) { 00560 00561 BZ_FINALISE_CRC ( s->blockCRC ); 00562 s->combinedCRC = (s->combinedCRC << 1) | (s->combinedCRC >> 31); 00563 s->combinedCRC ^= s->blockCRC; 00564 if (s->blockNo > 1) s->numZ = 0; 00565 00566 if (s->verbosity >= 2) 00567 VPrintf4( " block %d: crc = 0x%8x, " 00568 "combined CRC = 0x%8x, size = %d\n", 00569 s->blockNo, s->blockCRC, s->combinedCRC, s->nblock ); 00570 00571 blockSort ( s ); 00572 } 00573 00574 s->zbits = (UChar*) (&((UInt16*)s->arr2)[s->nblock]); 00575 00576 /*-- If this is the first block, create the stream header. --*/ 00577 if (s->blockNo == 1) { 00578 bsInitWrite ( s ); 00579 bsPutUChar ( s, 'B' ); 00580 bsPutUChar ( s, 'Z' ); 00581 bsPutUChar ( s, 'h' ); 00582 bsPutUChar ( s, '0' + s->blockSize100k ); 00583 } 00584 00585 if (s->nblock > 0) { 00586 00587 bsPutUChar ( s, 0x31 ); bsPutUChar ( s, 0x41 ); 00588 bsPutUChar ( s, 0x59 ); bsPutUChar ( s, 0x26 ); 00589 bsPutUChar ( s, 0x53 ); bsPutUChar ( s, 0x59 ); 00590 00591 /*-- Now the block's CRC, so it is in a known place. --*/ 00592 bsPutUInt32 ( s, s->blockCRC ); 00593 00594 /*-- 00595 Now a single bit indicating (non-)randomisation. 00596 As of version 0.9.5, we use a better sorting algorithm 00597 which makes randomisation unnecessary. So always set 00598 the randomised bit to 'no'. Of course, the decoder 00599 still needs to be able to handle randomised blocks 00600 so as to maintain backwards compatibility with 00601 older versions of bzip2. 00602 --*/ 00603 bsW(s,1,0); 00604 00605 bsW ( s, 24, s->origPtr ); 00606 generateMTFValues ( s ); 00607 sendMTFValues ( s ); 00608 } 00609 00610 00611 /*-- If this is the last block, add the stream trailer. --*/ 00612 if (is_last_block) { 00613 00614 bsPutUChar ( s, 0x17 ); bsPutUChar ( s, 0x72 ); 00615 bsPutUChar ( s, 0x45 ); bsPutUChar ( s, 0x38 ); 00616 bsPutUChar ( s, 0x50 ); bsPutUChar ( s, 0x90 ); 00617 bsPutUInt32 ( s, s->combinedCRC ); 00618 if (s->verbosity >= 2) 00619 VPrintf1( " final combined CRC = 0x%x\n ", s->combinedCRC ); 00620 bsFinishWrite ( s ); 00621 } 00622 } |
|
Definition at line 163 of file bzlib/compress.c. Referenced by compressBlock().
00164 { 00165 UChar yy[256]; 00166 Int32 i, j; 00167 UChar tmp; 00168 UChar tmp2; 00169 Int32 zPend; 00170 Int32 wr; 00171 Int32 EOB; 00172 00173 /* 00174 After sorting (eg, here), 00175 s->arr1 [ 0 .. s->nblock-1 ] holds sorted order, 00176 and 00177 ((UInt16*)s->arr2) [ 0 .. s->nblock-1 ] [15:8] 00178 holds the original block data. 00179 00180 The first thing to do is generate the MTF values, 00181 and put them in 00182 ((UInt16*)s->arr1) [ 0 .. s->nblock-1 ]. 00183 Because there are strictly fewer or equal MTF values 00184 than block values, ptr values in this area are overwritten 00185 with MTF values only when they are no longer needed. 00186 00187 The final compressed bitstream is generated into the 00188 area starting at 00189 (UChar*) (&((UInt16)s->arr2)[s->nblock]) 00190 00191 These storage aliases are set up in bzCompressInit(), 00192 except for the last one, which is arranged in 00193 compressBlock(). 00194 */ 00195 UInt32* ptr = s->ptr; 00196 UInt16* block = s->block; 00197 UInt16* mtfv = s->mtfv; 00198 00199 makeMaps_e ( s ); 00200 EOB = s->nInUse+1; 00201 00202 for (i = 0; i <= EOB; i++) s->mtfFreq[i] = 0; 00203 00204 wr = 0; 00205 zPend = 0; 00206 for (i = 0; i < s->nInUse; i++) yy[i] = (UChar) i; 00207 00208 for (i = 0; i < s->nblock; i++) { 00209 UChar ll_i; 00210 00211 AssertD ( wr <= i, "generateMTFValues(1)" ); 00212 j = ptr[i]-1; if (j < 0) j += s->nblock; 00213 ll_i = s->unseqToSeq[block[j] >> 8]; 00214 AssertD ( ll_i < s->nInUse, "generateMTFValues(2a)" ); 00215 00216 tmp = yy[0]; 00217 if (tmp == ll_i) { 00218 zPend++; 00219 } else { 00220 tmp2 = tmp; 00221 tmp = yy[1]; 00222 yy[1] = tmp2; 00223 j = 1; 00224 while ( ll_i != tmp ) { 00225 j++; 00226 tmp2 = tmp; 00227 tmp = yy[j]; 00228 yy[j] = tmp2; 00229 }; 00230 yy[0] = tmp; 00231 00232 if (zPend > 0) { 00233 zPend--; 00234 while (True) { 00235 if (zPend & 1) { 00236 mtfv[wr] = BZ_RUNB; wr++; 00237 s->mtfFreq[BZ_RUNB]++; 00238 } else { 00239 mtfv[wr] = BZ_RUNA; wr++; 00240 s->mtfFreq[BZ_RUNA]++; 00241 } 00242 if (zPend < 2) break; 00243 zPend = (zPend - 2) / 2; 00244 }; 00245 zPend = 0; 00246 } 00247 mtfv[wr] = j+1; wr++; s->mtfFreq[j+1]++; 00248 } 00249 } 00250 00251 if (zPend > 0) { 00252 zPend--; 00253 while (True) { 00254 if (zPend & 1) { 00255 mtfv[wr] = BZ_RUNB; wr++; 00256 s->mtfFreq[BZ_RUNB]++; 00257 } else { 00258 mtfv[wr] = BZ_RUNA; wr++; 00259 s->mtfFreq[BZ_RUNA]++; 00260 } 00261 if (zPend < 2) break; 00262 zPend = (zPend - 2) / 2; 00263 }; 00264 } 00265 00266 mtfv[wr] = EOB; wr++; s->mtfFreq[EOB]++; 00267 00268 s->nMTF = wr; 00269 } |
|
Definition at line 149 of file bzlib/compress.c. Referenced by generateMTFValues().
00150 { 00151 Int32 i; 00152 s->nInUse = 0; 00153 for (i = 0; i < 256; i++) 00154 if (s->inUse[i]) { 00155 s->unseqToSeq[i] = s->nInUse; 00156 s->nInUse++; 00157 } 00158 } |
|
Definition at line 277 of file bzlib/compress.c. Referenced by compressBlock().
00278 { 00279 Int32 v, t, i, j, gs, ge, totc, bt, bc, iter; 00280 Int32 nSelectors, alphaSize, minLen, maxLen, selCtr; 00281 Int32 nGroups, nBytes; 00282 00283 /*-- 00284 UChar len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; 00285 is a global since the decoder also needs it. 00286 00287 Int32 code[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; 00288 Int32 rfreq[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE]; 00289 are also globals only used in this proc. 00290 Made global to keep stack frame size small. 00291 --*/ 00292 00293 00294 UInt16 cost[BZ_N_GROUPS]; 00295 Int32 fave[BZ_N_GROUPS]; 00296 00297 UInt16* mtfv = s->mtfv; 00298 00299 if (s->verbosity >= 3) 00300 VPrintf3( " %d in block, %d after MTF & 1-2 coding, " 00301 "%d+2 syms in use\n", 00302 s->nblock, s->nMTF, s->nInUse ); 00303 00304 alphaSize = s->nInUse+2; 00305 for (t = 0; t < BZ_N_GROUPS; t++) 00306 for (v = 0; v < alphaSize; v++) 00307 s->len[t][v] = BZ_GREATER_ICOST; 00308 00309 /*--- Decide how many coding tables to use ---*/ 00310 AssertH ( s->nMTF > 0, 3001 ); 00311 if (s->nMTF < 200) nGroups = 2; else 00312 if (s->nMTF < 600) nGroups = 3; else 00313 if (s->nMTF < 1200) nGroups = 4; else 00314 if (s->nMTF < 2400) nGroups = 5; else 00315 nGroups = 6; 00316 00317 /*--- Generate an initial set of coding tables ---*/ 00318 { 00319 Int32 nPart, remF, tFreq, aFreq; 00320 00321 nPart = nGroups; 00322 remF = s->nMTF; 00323 gs = 0; 00324 while (nPart > 0) { 00325 tFreq = remF / nPart; 00326 ge = gs-1; 00327 aFreq = 0; 00328 while (aFreq < tFreq && ge < alphaSize-1) { 00329 ge++; 00330 aFreq += s->mtfFreq[ge]; 00331 } 00332 00333 if (ge > gs 00334 && nPart != nGroups && nPart != 1 00335 && ((nGroups-nPart) % 2 == 1)) { 00336 aFreq -= s->mtfFreq[ge]; 00337 ge--; 00338 } 00339 00340 if (s->verbosity >= 3) 00341 VPrintf5( " initial group %d, [%d .. %d], " 00342 "has %d syms (%4.1f%%)\n", 00343 nPart, gs, ge, aFreq, 00344 (100.0 * (float)aFreq) / (float)(s->nMTF) ); 00345 00346 for (v = 0; v < alphaSize; v++) 00347 if (v >= gs && v <= ge) 00348 s->len[nPart-1][v] = BZ_LESSER_ICOST; else 00349 s->len[nPart-1][v] = BZ_GREATER_ICOST; 00350 00351 nPart--; 00352 gs = ge+1; 00353 remF -= aFreq; 00354 } 00355 } 00356 00357 /*--- 00358 Iterate up to BZ_N_ITERS times to improve the tables. 00359 ---*/ 00360 for (iter = 0; iter < BZ_N_ITERS; iter++) { 00361 00362 for (t = 0; t < nGroups; t++) fave[t] = 0; 00363 00364 for (t = 0; t < nGroups; t++) 00365 for (v = 0; v < alphaSize; v++) 00366 s->rfreq[t][v] = 0; 00367 00368 nSelectors = 0; 00369 totc = 0; 00370 gs = 0; 00371 while (True) { 00372 00373 /*--- Set group start & end marks. --*/ 00374 if (gs >= s->nMTF) break; 00375 ge = gs + BZ_G_SIZE - 1; 00376 if (ge >= s->nMTF) ge = s->nMTF-1; 00377 00378 /*-- 00379 Calculate the cost of this group as coded 00380 by each of the coding tables. 00381 --*/ 00382 for (t = 0; t < nGroups; t++) cost[t] = 0; 00383 00384 if (nGroups == 6) { 00385 register UInt16 cost0, cost1, cost2, cost3, cost4, cost5; 00386 cost0 = cost1 = cost2 = cost3 = cost4 = cost5 = 0; 00387 for (i = gs; i <= ge; i++) { 00388 UInt16 icv = mtfv[i]; 00389 cost0 += s->len[0][icv]; 00390 cost1 += s->len[1][icv]; 00391 cost2 += s->len[2][icv]; 00392 cost3 += s->len[3][icv]; 00393 cost4 += s->len[4][icv]; 00394 cost5 += s->len[5][icv]; 00395 } 00396 cost[0] = cost0; cost[1] = cost1; cost[2] = cost2; 00397 cost[3] = cost3; cost[4] = cost4; cost[5] = cost5; 00398 } else { 00399 for (i = gs; i <= ge; i++) { 00400 UInt16 icv = mtfv[i]; 00401 for (t = 0; t < nGroups; t++) cost[t] += s->len[t][icv]; 00402 } 00403 } 00404 00405 /*-- 00406 Find the coding table which is best for this group, 00407 and record its identity in the selector table. 00408 --*/ 00409 bc = 999999999; bt = -1; 00410 for (t = 0; t < nGroups; t++) 00411 if (cost[t] < bc) { bc = cost[t]; bt = t; }; 00412 totc += bc; 00413 fave[bt]++; 00414 s->selector[nSelectors] = bt; 00415 nSelectors++; 00416 00417 /*-- 00418 Increment the symbol frequencies for the selected table. 00419 --*/ 00420 for (i = gs; i <= ge; i++) 00421 s->rfreq[bt][ mtfv[i] ]++; 00422 00423 gs = ge+1; 00424 } 00425 if (s->verbosity >= 3) { 00426 VPrintf2 ( " pass %d: size is %d, grp uses are ", 00427 iter+1, totc/8 ); 00428 for (t = 0; t < nGroups; t++) 00429 VPrintf1 ( "%d ", fave[t] ); 00430 VPrintf0 ( "\n" ); 00431 } 00432 00433 /*-- 00434 Recompute the tables based on the accumulated frequencies. 00435 --*/ 00436 for (t = 0; t < nGroups; t++) 00437 hbMakeCodeLengths ( &(s->len[t][0]), &(s->rfreq[t][0]), 00438 alphaSize, 20 ); 00439 } 00440 00441 00442 AssertH( nGroups < 8, 3002 ); 00443 AssertH( nSelectors < 32768 && 00444 nSelectors <= (2 + (900000 / BZ_G_SIZE)), 00445 3003 ); 00446 00447 00448 /*--- Compute MTF values for the selectors. ---*/ 00449 { 00450 UChar pos[BZ_N_GROUPS], ll_i, tmp2, tmp; 00451 for (i = 0; i < nGroups; i++) pos[i] = i; 00452 for (i = 0; i < nSelectors; i++) { 00453 ll_i = s->selector[i]; 00454 j = 0; 00455 tmp = pos[j]; 00456 while ( ll_i != tmp ) { 00457 j++; 00458 tmp2 = tmp; 00459 tmp = pos[j]; 00460 pos[j] = tmp2; 00461 }; 00462 pos[0] = tmp; 00463 s->selectorMtf[i] = j; 00464 } 00465 }; 00466 00467 /*--- Assign actual codes for the tables. --*/ 00468 for (t = 0; t < nGroups; t++) { 00469 minLen = 32; 00470 maxLen = 0; 00471 for (i = 0; i < alphaSize; i++) { 00472 if (s->len[t][i] > maxLen) maxLen = s->len[t][i]; 00473 if (s->len[t][i] < minLen) minLen = s->len[t][i]; 00474 } 00475 AssertH ( !(maxLen > 20), 3004 ); 00476 AssertH ( !(minLen < 1), 3005 ); 00477 hbAssignCodes ( &(s->code[t][0]), &(s->len[t][0]), 00478 minLen, maxLen, alphaSize ); 00479 } 00480 00481 /*--- Transmit the mapping table. ---*/ 00482 { 00483 Bool inUse16[16]; 00484 for (i = 0; i < 16; i++) { 00485 inUse16[i] = False; 00486 for (j = 0; j < 16; j++) 00487 if (s->inUse[i * 16 + j]) inUse16[i] = True; 00488 } 00489 00490 nBytes = s->numZ; 00491 for (i = 0; i < 16; i++) 00492 if (inUse16[i]) bsW(s,1,1); else bsW(s,1,0); 00493 00494 for (i = 0; i < 16; i++) 00495 if (inUse16[i]) 00496 for (j = 0; j < 16; j++) { 00497 if (s->inUse[i * 16 + j]) bsW(s,1,1); else bsW(s,1,0); 00498 } 00499 00500 if (s->verbosity >= 3) 00501 VPrintf1( " bytes: mapping %d, ", s->numZ-nBytes ); 00502 } 00503 00504 /*--- Now the selectors. ---*/ 00505 nBytes = s->numZ; 00506 bsW ( s, 3, nGroups ); 00507 bsW ( s, 15, nSelectors ); 00508 for (i = 0; i < nSelectors; i++) { 00509 for (j = 0; j < s->selectorMtf[i]; j++) bsW(s,1,1); 00510 bsW(s,1,0); 00511 } 00512 if (s->verbosity >= 3) 00513 VPrintf1( "selectors %d, ", s->numZ-nBytes ); 00514 00515 /*--- Now the coding tables. ---*/ 00516 nBytes = s->numZ; 00517 00518 for (t = 0; t < nGroups; t++) { 00519 Int32 curr = s->len[t][0]; 00520 bsW ( s, 5, curr ); 00521 for (i = 0; i < alphaSize; i++) { 00522 while (curr < s->len[t][i]) { bsW(s,2,2); curr++; /* 10 */ }; 00523 while (curr > s->len[t][i]) { bsW(s,2,3); curr--; /* 11 */ }; 00524 bsW ( s, 1, 0 ); 00525 } 00526 } 00527 00528 if (s->verbosity >= 3) 00529 VPrintf1 ( "code lengths %d, ", s->numZ-nBytes ); 00530 00531 /*--- And finally, the block data proper ---*/ 00532 nBytes = s->numZ; 00533 selCtr = 0; 00534 gs = 0; 00535 while (True) { 00536 if (gs >= s->nMTF) break; 00537 ge = gs + BZ_G_SIZE - 1; 00538 if (ge >= s->nMTF) ge = s->nMTF-1; 00539 for (i = gs; i <= ge; i++) { 00540 AssertH ( s->selector[selCtr] < nGroups, 3006 ); 00541 bsW ( s, 00542 s->len [s->selector[selCtr]] [mtfv[i]], 00543 s->code [s->selector[selCtr]] [mtfv[i]] ); 00544 } 00545 00546 gs = ge+1; 00547 selCtr++; 00548 } 00549 AssertH( selCtr == nSelectors, 3007 ); 00550 00551 if (s->verbosity >= 3) 00552 VPrintf1( "codes %d\n", s->numZ-nBytes ); 00553 } |