Back to index

avfs  1.0.1
compress.c
Go to the documentation of this file.
00001 
00002 /*-------------------------------------------------------------*/
00003 /*--- Compression machinery (not incl block sorting)        ---*/
00004 /*---                                            compress.c ---*/
00005 /*-------------------------------------------------------------*/
00006 
00007 /* ------------------------------------------------------------------
00008    This file is part of bzip2/libbzip2, a program and library for
00009    lossless, block-sorting data compression.
00010 
00011    bzip2/libbzip2 version 1.0.6 of 6 September 2010
00012    Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org>
00013 
00014    Please read the WARNING, DISCLAIMER and PATENTS sections in the 
00015    README file.
00016 
00017    This program is released under the terms of the license contained
00018    in the file LICENSE.
00019    ------------------------------------------------------------------ */
00020 
00021 
00022 /* CHANGES
00023     0.9.0    -- original version.
00024     0.9.0a/b -- no changes in this file.
00025     0.9.0c   -- changed setting of nGroups in sendMTFValues() 
00026                 so as to do a bit better on small files
00027 */
00028 
00029 #include "bzlib_private.h"
00030 
00031 
00032 /*---------------------------------------------------*/
00033 /*--- Bit stream I/O                              ---*/
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 /*--- The back end proper                         ---*/
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       After sorting (eg, here),
00130          s->arr1 [ 0 .. s->nblock-1 ] holds sorted order,
00131          and
00132          ((UChar*)s->arr2) [ 0 .. s->nblock-1 ] 
00133          holds the original block data.
00134 
00135       The first thing to do is generate the MTF values,
00136       and put them in
00137          ((UInt16*)s->arr1) [ 0 .. s->nblock-1 ].
00138       Because there are strictly fewer or equal MTF values
00139       than block values, ptr values in this area are overwritten
00140       with MTF values only when they are no longer needed.
00141 
00142       The final compressed bitstream is generated into the
00143       area starting at
00144          (UChar*) (&((UChar*)s->arr2)[s->nblock])
00145 
00146       These storage aliases are set up in bzCompressInit(),
00147       except for the last one, which is arranged in 
00148       compressBlock().
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    UChar  len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
00247    is a global since the decoder also needs it.
00248 
00249    Int32  code[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
00250    Int32  rfreq[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
00251    are also globals only used in this proc.
00252    Made global to keep stack frame size small.
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    /*--- Decide how many coding tables to use ---*/
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    /*--- Generate an initial set of coding tables ---*/
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       Iterate up to BZ_N_ITERS times to improve the tables.
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         Set up an auxiliary length table which is used to fast-track
00332        the common case (nGroups == 6). 
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          /*--- Set group start & end marks. --*/
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             Calculate the cost of this group as coded
00354             by each of the coding tables.
00355          --*/
00356          for (t = 0; t < nGroups; t++) cost[t] = 0;
00357 
00358          if (nGroups == 6 && 50 == ge-gs+1) {
00359             /*--- fast track the common case ---*/
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            /*--- slow version which correctly handles all situations ---*/
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             Find the coding table which is best for this group,
00397             and record its identity in the selector table.
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             Increment the symbol frequencies for the selected table.
00409           --*/
00410          if (nGroups == 6 && 50 == ge-gs+1) {
00411             /*--- fast track the common case ---*/
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            /*--- slow version which correctly handles all situations ---*/
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         Recompute the tables based on the accumulated frequencies.
00446       --*/
00447       /* maxLen was changed from 20 to 17 in bzip2-1.0.3.  See 
00448          comment in huffman.c for details. */
00449       for (t = 0; t < nGroups; t++)
00450          BZ2_hbMakeCodeLengths ( &(s->len[t][0]), &(s->rfreq[t][0]), 
00451                                  alphaSize, 17 /*20*/ );
00452    }
00453 
00454 
00455    AssertH( nGroups < 8, 3002 );
00456    AssertH( nSelectors < 32768 &&
00457             nSelectors <= (2 + (900000 / BZ_G_SIZE)),
00458             3003 );
00459 
00460 
00461    /*--- Compute MTF values for the selectors. ---*/
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    /*--- Assign actual codes for the tables. --*/
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 /*20*/ ), 3004 );
00489       AssertH ( !(minLen < 1),  3005 );
00490       BZ2_hbAssignCodes ( &(s->code[t][0]), &(s->len[t][0]), 
00491                           minLen, maxLen, alphaSize );
00492    }
00493 
00494    /*--- Transmit the mapping table. ---*/
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    /*--- Now the selectors. ---*/
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    /*--- Now the coding tables. ---*/
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++; /* 10 */ };
00536          while (curr > s->len[t][i]) { bsW(s,2,3); curr--; /* 11 */ };
00537          bsW ( s, 1, 0 );
00538       }
00539    }
00540 
00541    if (s->verbosity >= 3)
00542       VPrintf1 ( "code lengths %d, ", s->numZ-nBytes );
00543 
00544    /*--- And finally, the block data proper ---*/
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             /*--- fast track the common case ---*/
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         /*--- slow version which correctly handles all situations ---*/
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    /*-- If this is the first block, create the stream header. --*/
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       /*-- Now the block's CRC, so it is in a known place. --*/
00637       bsPutUInt32 ( s, s->blockCRC );
00638 
00639       /*-- 
00640          Now a single bit indicating (non-)randomisation. 
00641          As of version 0.9.5, we use a better sorting algorithm
00642          which makes randomisation unnecessary.  So always set
00643          the randomised bit to 'no'.  Of course, the decoder
00644          still needs to be able to handle randomised blocks
00645          so as to maintain backwards compatibility with
00646          older versions of bzip2.
00647       --*/
00648       bsW(s,1,0);
00649 
00650       bsW ( s, 24, s->origPtr );
00651       generateMTFValues ( s );
00652       sendMTFValues ( s );
00653    }
00654 
00655 
00656    /*-- If this is the last block, add the stream trailer. --*/
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 /*--- end                                        compress.c ---*/
00672 /*-------------------------------------------------------------*/