00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073 #include "bzlib_private.h"
00074
00075
00076
00077
00078
00079
00080
00081 void bsInitWrite ( EState* s )
00082 {
00083 s->bsLive = 0;
00084 s->bsBuff = 0;
00085 }
00086
00087
00088
00089 static
00090 void bsFinishWrite ( EState* s )
00091 {
00092 while (s->bsLive > 0) {
00093 s->zbits[s->numZ] = (UChar)(s->bsBuff >> 24);
00094 s->numZ++;
00095 s->bsBuff <<= 8;
00096 s->bsLive -= 8;
00097 }
00098 }
00099
00100
00101
00102 #define bsNEEDW(nz) \
00103 { \
00104 while (s->bsLive >= 8) { \
00105 s->zbits[s->numZ] \
00106 = (UChar)(s->bsBuff >> 24); \
00107 s->numZ++; \
00108 s->bsBuff <<= 8; \
00109 s->bsLive -= 8; \
00110 } \
00111 }
00112
00113
00114
00115 static
00116 void bsW ( EState* s, Int32 n, UInt32 v )
00117 {
00118 bsNEEDW ( n );
00119 s->bsBuff |= (v << (32 - s->bsLive - n));
00120 s->bsLive += n;
00121 }
00122
00123
00124
00125 static
00126 void bsPutUInt32 ( EState* s, UInt32 u )
00127 {
00128 bsW ( s, 8, (u >> 24) & 0xffL );
00129 bsW ( s, 8, (u >> 16) & 0xffL );
00130 bsW ( s, 8, (u >> 8) & 0xffL );
00131 bsW ( s, 8, u & 0xffL );
00132 }
00133
00134
00135
00136 static
00137 void bsPutUChar ( EState* s, UChar c )
00138 {
00139 bsW( s, 8, (UInt32)c );
00140 }
00141
00142
00143
00144
00145
00146
00147
00148 static
00149 void makeMaps_e ( EState* s )
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 }
00159
00160
00161
00162 static
00163 void generateMTFValues ( EState* s )
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
00175
00176
00177
00178
00179
00180
00181
00182
00183
00184
00185
00186
00187
00188
00189
00190
00191
00192
00193
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 }
00270
00271
00272
00273 #define BZ_LESSER_ICOST 0
00274 #define BZ_GREATER_ICOST 15
00275
00276 static
00277 void sendMTFValues ( EState* s )
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
00285
00286
00287
00288
00289
00290
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
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
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
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
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
00380
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
00407
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
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
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
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
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
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
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
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++; };
00523 while (curr > s->len[t][i]) { bsW(s,2,3); curr--; };
00524 bsW ( s, 1, 0 );
00525 }
00526 }
00527
00528 if (s->verbosity >= 3)
00529 VPrintf1 ( "code lengths %d, ", s->numZ-nBytes );
00530
00531
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 }
00554
00555
00556
00557 void compressBlock ( EState* s, Bool is_last_block )
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
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
00592 bsPutUInt32 ( s, s->blockCRC );
00593
00594
00595
00596
00597
00598
00599
00600
00601
00602
00603 bsW(s,1,0);
00604
00605 bsW ( s, 24, s->origPtr );
00606 generateMTFValues ( s );
00607 sendMTFValues ( s );
00608 }
00609
00610
00611
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 }
00623
00624
00625
00626
00627