bzlib/compress.c File Reference

{                                             \
   while (s->bsLive >= 8) {                   \
      s->zbits[s->numZ]                       \
         = (UChar)(s->bsBuff >> 24);          \
      s->numZ++;                              \
      s->bsBuff <<= 8;                        \
      s->bsLive -= 8;                         \
   }                                          \
}

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 }

00082 {
00083    s->bsLive = 0;
00084    s->bsBuff = 0;
00085 }

00138 {
00139    bsW( s, 8, (UInt32)c );
00140 }

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 }

00117 {
00118    bsNEEDW ( n );
00119    s->bsBuff |= (v << (32 - s->bsLive - n));
00120    s->bsLive += n;
00121 }

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 }

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 }

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 }

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 }

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)

compress.c File Reference

Defines

Functions

Define Documentation

Function Documentation