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 #include "bzlib_private.h"
00030
00031
00032
00033
00034
00035
00036
00037 void BZ2_bsInitWrite ( EState* s )
00038 {
00039 s->bsLive = 0;
00040 s->bsBuff = 0;
00041 }
00042
00043
00044
00045 static
00046 void bsFinishWrite ( EState* s )
00047 {
00048 while (s->bsLive > 0) {
00049 s->zbits[s->numZ] = (UChar)(s->bsBuff >> 24);
00050 s->numZ++;
00051 s->bsBuff <<= 8;
00052 s->bsLive -= 8;
00053 }
00054 }
00055
00056
00057
00058 #define bsNEEDW(nz) \
00059 { \
00060 while (s->bsLive >= 8) { \
00061 s->zbits[s->numZ] \
00062 = (UChar)(s->bsBuff >> 24); \
00063 s->numZ++; \
00064 s->bsBuff <<= 8; \
00065 s->bsLive -= 8; \
00066 } \
00067 }
00068
00069
00070
00071 static
00072 __inline__
00073 void bsW ( EState* s, Int32 n, UInt32 v )
00074 {
00075 bsNEEDW ( n );
00076 s->bsBuff |= (v << (32 - s->bsLive - n));
00077 s->bsLive += n;
00078 }
00079
00080
00081
00082 static
00083 void bsPutUInt32 ( EState* s, UInt32 u )
00084 {
00085 bsW ( s, 8, (u >> 24) & 0xffL );
00086 bsW ( s, 8, (u >> 16) & 0xffL );
00087 bsW ( s, 8, (u >> 8) & 0xffL );
00088 bsW ( s, 8, u & 0xffL );
00089 }
00090
00091
00092
00093 static
00094 void bsPutUChar ( EState* s, UChar c )
00095 {
00096 bsW( s, 8, (UInt32)c );
00097 }
00098
00099
00100
00101
00102
00103
00104
00105 static
00106 void makeMaps_e ( EState* s )
00107 {
00108 Int32 i;
00109 s->nInUse = 0;
00110 for (i = 0; i < 256; i++)
00111 if (s->inUse[i]) {
00112 s->unseqToSeq[i] = s->nInUse;
00113 s->nInUse++;
00114 }
00115 }
00116
00117
00118
00119 static
00120 void generateMTFValues ( EState* s )
00121 {
00122 UChar yy[256];
00123 Int32 i, j;
00124 Int32 zPend;
00125 Int32 wr;
00126 Int32 EOB;
00127
00128
00129
00130
00131
00132
00133
00134
00135
00136
00137
00138
00139
00140
00141
00142
00143
00144
00145
00146
00147
00148
00149
00150 UInt32* ptr = s->ptr;
00151 UChar* block = s->block;
00152 UInt16* mtfv = s->mtfv;
00153
00154 makeMaps_e ( s );
00155 EOB = s->nInUse+1;
00156
00157 for (i = 0; i <= EOB; i++) s->mtfFreq[i] = 0;
00158
00159 wr = 0;
00160 zPend = 0;
00161 for (i = 0; i < s->nInUse; i++) yy[i] = (UChar) i;
00162
00163 for (i = 0; i < s->nblock; i++) {
00164 UChar ll_i;
00165 AssertD ( wr <= i, "generateMTFValues(1)" );
00166 j = ptr[i]-1; if (j < 0) j += s->nblock;
00167 ll_i = s->unseqToSeq[block[j]];
00168 AssertD ( ll_i < s->nInUse, "generateMTFValues(2a)" );
00169
00170 if (yy[0] == ll_i) {
00171 zPend++;
00172 } else {
00173
00174 if (zPend > 0) {
00175 zPend--;
00176 while (True) {
00177 if (zPend & 1) {
00178 mtfv[wr] = BZ_RUNB; wr++;
00179 s->mtfFreq[BZ_RUNB]++;
00180 } else {
00181 mtfv[wr] = BZ_RUNA; wr++;
00182 s->mtfFreq[BZ_RUNA]++;
00183 }
00184 if (zPend < 2) break;
00185 zPend = (zPend - 2) / 2;
00186 };
00187 zPend = 0;
00188 }
00189 {
00190 register UChar rtmp;
00191 register UChar* ryy_j;
00192 register UChar rll_i;
00193 rtmp = yy[1];
00194 yy[1] = yy[0];
00195 ryy_j = &(yy[1]);
00196 rll_i = ll_i;
00197 while ( rll_i != rtmp ) {
00198 register UChar rtmp2;
00199 ryy_j++;
00200 rtmp2 = rtmp;
00201 rtmp = *ryy_j;
00202 *ryy_j = rtmp2;
00203 };
00204 yy[0] = rtmp;
00205 j = ryy_j - &(yy[0]);
00206 mtfv[wr] = j+1; wr++; s->mtfFreq[j+1]++;
00207 }
00208
00209 }
00210 }
00211
00212 if (zPend > 0) {
00213 zPend--;
00214 while (True) {
00215 if (zPend & 1) {
00216 mtfv[wr] = BZ_RUNB; wr++;
00217 s->mtfFreq[BZ_RUNB]++;
00218 } else {
00219 mtfv[wr] = BZ_RUNA; wr++;
00220 s->mtfFreq[BZ_RUNA]++;
00221 }
00222 if (zPend < 2) break;
00223 zPend = (zPend - 2) / 2;
00224 };
00225 zPend = 0;
00226 }
00227
00228 mtfv[wr] = EOB; wr++; s->mtfFreq[EOB]++;
00229
00230 s->nMTF = wr;
00231 }
00232
00233
00234
00235 #define BZ_LESSER_ICOST 0
00236 #define BZ_GREATER_ICOST 15
00237
00238 static
00239 void sendMTFValues ( EState* s )
00240 {
00241 Int32 v, t, i, j, gs, ge, totc, bt, bc, iter;
00242 Int32 nSelectors, alphaSize, minLen, maxLen, selCtr;
00243 Int32 nGroups, nBytes;
00244
00245
00246
00247
00248
00249
00250
00251
00252
00253
00254
00255
00256 UInt16 cost[BZ_N_GROUPS];
00257 Int32 fave[BZ_N_GROUPS];
00258
00259 UInt16* mtfv = s->mtfv;
00260
00261 if (s->verbosity >= 3)
00262 VPrintf3( " %d in block, %d after MTF & 1-2 coding, "
00263 "%d+2 syms in use\n",
00264 s->nblock, s->nMTF, s->nInUse );
00265
00266 alphaSize = s->nInUse+2;
00267 for (t = 0; t < BZ_N_GROUPS; t++)
00268 for (v = 0; v < alphaSize; v++)
00269 s->len[t][v] = BZ_GREATER_ICOST;
00270
00271
00272 AssertH ( s->nMTF > 0, 3001 );
00273 if (s->nMTF < 200) nGroups = 2; else
00274 if (s->nMTF < 600) nGroups = 3; else
00275 if (s->nMTF < 1200) nGroups = 4; else
00276 if (s->nMTF < 2400) nGroups = 5; else
00277 nGroups = 6;
00278
00279
00280 {
00281 Int32 nPart, remF, tFreq, aFreq;
00282
00283 nPart = nGroups;
00284 remF = s->nMTF;
00285 gs = 0;
00286 while (nPart > 0) {
00287 tFreq = remF / nPart;
00288 ge = gs-1;
00289 aFreq = 0;
00290 while (aFreq < tFreq && ge < alphaSize-1) {
00291 ge++;
00292 aFreq += s->mtfFreq[ge];
00293 }
00294
00295 if (ge > gs
00296 && nPart != nGroups && nPart != 1
00297 && ((nGroups-nPart) % 2 == 1)) {
00298 aFreq -= s->mtfFreq[ge];
00299 ge--;
00300 }
00301
00302 if (s->verbosity >= 3)
00303 VPrintf5( " initial group %d, [%d .. %d], "
00304 "has %d syms (%4.1f%%)\n",
00305 nPart, gs, ge, aFreq,
00306 (100.0 * (float)aFreq) / (float)(s->nMTF) );
00307
00308 for (v = 0; v < alphaSize; v++)
00309 if (v >= gs && v <= ge)
00310 s->len[nPart-1][v] = BZ_LESSER_ICOST; else
00311 s->len[nPart-1][v] = BZ_GREATER_ICOST;
00312
00313 nPart--;
00314 gs = ge+1;
00315 remF -= aFreq;
00316 }
00317 }
00318
00319
00320
00321
00322 for (iter = 0; iter < BZ_N_ITERS; iter++) {
00323
00324 for (t = 0; t < nGroups; t++) fave[t] = 0;
00325
00326 for (t = 0; t < nGroups; t++)
00327 for (v = 0; v < alphaSize; v++)
00328 s->rfreq[t][v] = 0;
00329
00330
00331
00332
00333
00334 if (nGroups == 6) {
00335 for (v = 0; v < alphaSize; v++) {
00336 s->len_pack[v][0] = (s->len[1][v] << 16) | s->len[0][v];
00337 s->len_pack[v][1] = (s->len[3][v] << 16) | s->len[2][v];
00338 s->len_pack[v][2] = (s->len[5][v] << 16) | s->len[4][v];
00339 }
00340 }
00341
00342 nSelectors = 0;
00343 totc = 0;
00344 gs = 0;
00345 while (True) {
00346
00347
00348 if (gs >= s->nMTF) break;
00349 ge = gs + BZ_G_SIZE - 1;
00350 if (ge >= s->nMTF) ge = s->nMTF-1;
00351
00352
00353
00354
00355
00356 for (t = 0; t < nGroups; t++) cost[t] = 0;
00357
00358 if (nGroups == 6 && 50 == ge-gs+1) {
00359
00360 register UInt32 cost01, cost23, cost45;
00361 register UInt16 icv;
00362 cost01 = cost23 = cost45 = 0;
00363
00364 # define BZ_ITER(nn) \
00365 icv = mtfv[gs+(nn)]; \
00366 cost01 += s->len_pack[icv][0]; \
00367 cost23 += s->len_pack[icv][1]; \
00368 cost45 += s->len_pack[icv][2]; \
00369
00370 BZ_ITER(0); BZ_ITER(1); BZ_ITER(2); BZ_ITER(3); BZ_ITER(4);
00371 BZ_ITER(5); BZ_ITER(6); BZ_ITER(7); BZ_ITER(8); BZ_ITER(9);
00372 BZ_ITER(10); BZ_ITER(11); BZ_ITER(12); BZ_ITER(13); BZ_ITER(14);
00373 BZ_ITER(15); BZ_ITER(16); BZ_ITER(17); BZ_ITER(18); BZ_ITER(19);
00374 BZ_ITER(20); BZ_ITER(21); BZ_ITER(22); BZ_ITER(23); BZ_ITER(24);
00375 BZ_ITER(25); BZ_ITER(26); BZ_ITER(27); BZ_ITER(28); BZ_ITER(29);
00376 BZ_ITER(30); BZ_ITER(31); BZ_ITER(32); BZ_ITER(33); BZ_ITER(34);
00377 BZ_ITER(35); BZ_ITER(36); BZ_ITER(37); BZ_ITER(38); BZ_ITER(39);
00378 BZ_ITER(40); BZ_ITER(41); BZ_ITER(42); BZ_ITER(43); BZ_ITER(44);
00379 BZ_ITER(45); BZ_ITER(46); BZ_ITER(47); BZ_ITER(48); BZ_ITER(49);
00380
00381 # undef BZ_ITER
00382
00383 cost[0] = cost01 & 0xffff; cost[1] = cost01 >> 16;
00384 cost[2] = cost23 & 0xffff; cost[3] = cost23 >> 16;
00385 cost[4] = cost45 & 0xffff; cost[5] = cost45 >> 16;
00386
00387 } else {
00388
00389 for (i = gs; i <= ge; i++) {
00390 UInt16 icv = mtfv[i];
00391 for (t = 0; t < nGroups; t++) cost[t] += s->len[t][icv];
00392 }
00393 }
00394
00395
00396
00397
00398
00399 bc = 999999999; bt = -1;
00400 for (t = 0; t < nGroups; t++)
00401 if (cost[t] < bc) { bc = cost[t]; bt = t; };
00402 totc += bc;
00403 fave[bt]++;
00404 s->selector[nSelectors] = bt;
00405 nSelectors++;
00406
00407
00408
00409
00410 if (nGroups == 6 && 50 == ge-gs+1) {
00411
00412
00413 # define BZ_ITUR(nn) s->rfreq[bt][ mtfv[gs+(nn)] ]++
00414
00415 BZ_ITUR(0); BZ_ITUR(1); BZ_ITUR(2); BZ_ITUR(3); BZ_ITUR(4);
00416 BZ_ITUR(5); BZ_ITUR(6); BZ_ITUR(7); BZ_ITUR(8); BZ_ITUR(9);
00417 BZ_ITUR(10); BZ_ITUR(11); BZ_ITUR(12); BZ_ITUR(13); BZ_ITUR(14);
00418 BZ_ITUR(15); BZ_ITUR(16); BZ_ITUR(17); BZ_ITUR(18); BZ_ITUR(19);
00419 BZ_ITUR(20); BZ_ITUR(21); BZ_ITUR(22); BZ_ITUR(23); BZ_ITUR(24);
00420 BZ_ITUR(25); BZ_ITUR(26); BZ_ITUR(27); BZ_ITUR(28); BZ_ITUR(29);
00421 BZ_ITUR(30); BZ_ITUR(31); BZ_ITUR(32); BZ_ITUR(33); BZ_ITUR(34);
00422 BZ_ITUR(35); BZ_ITUR(36); BZ_ITUR(37); BZ_ITUR(38); BZ_ITUR(39);
00423 BZ_ITUR(40); BZ_ITUR(41); BZ_ITUR(42); BZ_ITUR(43); BZ_ITUR(44);
00424 BZ_ITUR(45); BZ_ITUR(46); BZ_ITUR(47); BZ_ITUR(48); BZ_ITUR(49);
00425
00426 # undef BZ_ITUR
00427
00428 } else {
00429
00430 for (i = gs; i <= ge; i++)
00431 s->rfreq[bt][ mtfv[i] ]++;
00432 }
00433
00434 gs = ge+1;
00435 }
00436 if (s->verbosity >= 3) {
00437 VPrintf2 ( " pass %d: size is %d, grp uses are ",
00438 iter+1, totc/8 );
00439 for (t = 0; t < nGroups; t++)
00440 VPrintf1 ( "%d ", fave[t] );
00441 VPrintf0 ( "\n" );
00442 }
00443
00444
00445
00446
00447
00448
00449 for (t = 0; t < nGroups; t++)
00450 BZ2_hbMakeCodeLengths ( &(s->len[t][0]), &(s->rfreq[t][0]),
00451 alphaSize, 17 );
00452 }
00453
00454
00455 AssertH( nGroups < 8, 3002 );
00456 AssertH( nSelectors < 32768 &&
00457 nSelectors <= (2 + (900000 / BZ_G_SIZE)),
00458 3003 );
00459
00460
00461
00462 {
00463 UChar pos[BZ_N_GROUPS], ll_i, tmp2, tmp;
00464 for (i = 0; i < nGroups; i++) pos[i] = i;
00465 for (i = 0; i < nSelectors; i++) {
00466 ll_i = s->selector[i];
00467 j = 0;
00468 tmp = pos[j];
00469 while ( ll_i != tmp ) {
00470 j++;
00471 tmp2 = tmp;
00472 tmp = pos[j];
00473 pos[j] = tmp2;
00474 };
00475 pos[0] = tmp;
00476 s->selectorMtf[i] = j;
00477 }
00478 };
00479
00480
00481 for (t = 0; t < nGroups; t++) {
00482 minLen = 32;
00483 maxLen = 0;
00484 for (i = 0; i < alphaSize; i++) {
00485 if (s->len[t][i] > maxLen) maxLen = s->len[t][i];
00486 if (s->len[t][i] < minLen) minLen = s->len[t][i];
00487 }
00488 AssertH ( !(maxLen > 17 ), 3004 );
00489 AssertH ( !(minLen < 1), 3005 );
00490 BZ2_hbAssignCodes ( &(s->code[t][0]), &(s->len[t][0]),
00491 minLen, maxLen, alphaSize );
00492 }
00493
00494
00495 {
00496 Bool inUse16[16];
00497 for (i = 0; i < 16; i++) {
00498 inUse16[i] = False;
00499 for (j = 0; j < 16; j++)
00500 if (s->inUse[i * 16 + j]) inUse16[i] = True;
00501 }
00502
00503 nBytes = s->numZ;
00504 for (i = 0; i < 16; i++)
00505 if (inUse16[i]) bsW(s,1,1); else bsW(s,1,0);
00506
00507 for (i = 0; i < 16; i++)
00508 if (inUse16[i])
00509 for (j = 0; j < 16; j++) {
00510 if (s->inUse[i * 16 + j]) bsW(s,1,1); else bsW(s,1,0);
00511 }
00512
00513 if (s->verbosity >= 3)
00514 VPrintf1( " bytes: mapping %d, ", s->numZ-nBytes );
00515 }
00516
00517
00518 nBytes = s->numZ;
00519 bsW ( s, 3, nGroups );
00520 bsW ( s, 15, nSelectors );
00521 for (i = 0; i < nSelectors; i++) {
00522 for (j = 0; j < s->selectorMtf[i]; j++) bsW(s,1,1);
00523 bsW(s,1,0);
00524 }
00525 if (s->verbosity >= 3)
00526 VPrintf1( "selectors %d, ", s->numZ-nBytes );
00527
00528
00529 nBytes = s->numZ;
00530
00531 for (t = 0; t < nGroups; t++) {
00532 Int32 curr = s->len[t][0];
00533 bsW ( s, 5, curr );
00534 for (i = 0; i < alphaSize; i++) {
00535 while (curr < s->len[t][i]) { bsW(s,2,2); curr++; };
00536 while (curr > s->len[t][i]) { bsW(s,2,3); curr--; };
00537 bsW ( s, 1, 0 );
00538 }
00539 }
00540
00541 if (s->verbosity >= 3)
00542 VPrintf1 ( "code lengths %d, ", s->numZ-nBytes );
00543
00544
00545 nBytes = s->numZ;
00546 selCtr = 0;
00547 gs = 0;
00548 while (True) {
00549 if (gs >= s->nMTF) break;
00550 ge = gs + BZ_G_SIZE - 1;
00551 if (ge >= s->nMTF) ge = s->nMTF-1;
00552 AssertH ( s->selector[selCtr] < nGroups, 3006 );
00553
00554 if (nGroups == 6 && 50 == ge-gs+1) {
00555
00556 UInt16 mtfv_i;
00557 UChar* s_len_sel_selCtr
00558 = &(s->len[s->selector[selCtr]][0]);
00559 Int32* s_code_sel_selCtr
00560 = &(s->code[s->selector[selCtr]][0]);
00561
00562 # define BZ_ITAH(nn) \
00563 mtfv_i = mtfv[gs+(nn)]; \
00564 bsW ( s, \
00565 s_len_sel_selCtr[mtfv_i], \
00566 s_code_sel_selCtr[mtfv_i] )
00567
00568 BZ_ITAH(0); BZ_ITAH(1); BZ_ITAH(2); BZ_ITAH(3); BZ_ITAH(4);
00569 BZ_ITAH(5); BZ_ITAH(6); BZ_ITAH(7); BZ_ITAH(8); BZ_ITAH(9);
00570 BZ_ITAH(10); BZ_ITAH(11); BZ_ITAH(12); BZ_ITAH(13); BZ_ITAH(14);
00571 BZ_ITAH(15); BZ_ITAH(16); BZ_ITAH(17); BZ_ITAH(18); BZ_ITAH(19);
00572 BZ_ITAH(20); BZ_ITAH(21); BZ_ITAH(22); BZ_ITAH(23); BZ_ITAH(24);
00573 BZ_ITAH(25); BZ_ITAH(26); BZ_ITAH(27); BZ_ITAH(28); BZ_ITAH(29);
00574 BZ_ITAH(30); BZ_ITAH(31); BZ_ITAH(32); BZ_ITAH(33); BZ_ITAH(34);
00575 BZ_ITAH(35); BZ_ITAH(36); BZ_ITAH(37); BZ_ITAH(38); BZ_ITAH(39);
00576 BZ_ITAH(40); BZ_ITAH(41); BZ_ITAH(42); BZ_ITAH(43); BZ_ITAH(44);
00577 BZ_ITAH(45); BZ_ITAH(46); BZ_ITAH(47); BZ_ITAH(48); BZ_ITAH(49);
00578
00579 # undef BZ_ITAH
00580
00581 } else {
00582
00583 for (i = gs; i <= ge; i++) {
00584 bsW ( s,
00585 s->len [s->selector[selCtr]] [mtfv[i]],
00586 s->code [s->selector[selCtr]] [mtfv[i]] );
00587 }
00588 }
00589
00590
00591 gs = ge+1;
00592 selCtr++;
00593 }
00594 AssertH( selCtr == nSelectors, 3007 );
00595
00596 if (s->verbosity >= 3)
00597 VPrintf1( "codes %d\n", s->numZ-nBytes );
00598 }
00599
00600
00601
00602 void BZ2_compressBlock ( EState* s, Bool is_last_block )
00603 {
00604 if (s->nblock > 0) {
00605
00606 BZ_FINALISE_CRC ( s->blockCRC );
00607 s->combinedCRC = (s->combinedCRC << 1) | (s->combinedCRC >> 31);
00608 s->combinedCRC ^= s->blockCRC;
00609 if (s->blockNo > 1) s->numZ = 0;
00610
00611 if (s->verbosity >= 2)
00612 VPrintf4( " block %d: crc = 0x%08x, "
00613 "combined CRC = 0x%08x, size = %d\n",
00614 s->blockNo, s->blockCRC, s->combinedCRC, s->nblock );
00615
00616 BZ2_blockSort ( s );
00617 }
00618
00619 s->zbits = (UChar*) (&((UChar*)s->arr2)[s->nblock]);
00620
00621
00622 if (s->blockNo == 1) {
00623 BZ2_bsInitWrite ( s );
00624 bsPutUChar ( s, BZ_HDR_B );
00625 bsPutUChar ( s, BZ_HDR_Z );
00626 bsPutUChar ( s, BZ_HDR_h );
00627 bsPutUChar ( s, (UChar)(BZ_HDR_0 + s->blockSize100k) );
00628 }
00629
00630 if (s->nblock > 0) {
00631
00632 bsPutUChar ( s, 0x31 ); bsPutUChar ( s, 0x41 );
00633 bsPutUChar ( s, 0x59 ); bsPutUChar ( s, 0x26 );
00634 bsPutUChar ( s, 0x53 ); bsPutUChar ( s, 0x59 );
00635
00636
00637 bsPutUInt32 ( s, s->blockCRC );
00638
00639
00640
00641
00642
00643
00644
00645
00646
00647
00648 bsW(s,1,0);
00649
00650 bsW ( s, 24, s->origPtr );
00651 generateMTFValues ( s );
00652 sendMTFValues ( s );
00653 }
00654
00655
00656
00657 if (is_last_block) {
00658
00659 bsPutUChar ( s, 0x17 ); bsPutUChar ( s, 0x72 );
00660 bsPutUChar ( s, 0x45 ); bsPutUChar ( s, 0x38 );
00661 bsPutUChar ( s, 0x50 ); bsPutUChar ( s, 0x90 );
00662 bsPutUInt32 ( s, s->combinedCRC );
00663 if (s->verbosity >= 2)
00664 VPrintf1( " final combined CRC = 0x%08x\n ", s->combinedCRC );
00665 bsFinishWrite ( s );
00666 }
00667 }
00668
00669
00670
00671
00672