Back to index

lightning-sunbird  0.9+nobinonly
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 a part of bzip2 and/or libbzip2, a program and
00009   library for lossless, block-sorting data compression.
00010 
00011   Copyright (C) 1996-2005 Julian R Seward.  All rights reserved.
00012 
00013   Redistribution and use in source and binary forms, with or without
00014   modification, are permitted provided that the following conditions
00015   are met:
00016 
00017   1. Redistributions of source code must retain the above copyright
00018      notice, this list of conditions and the following disclaimer.
00019 
00020   2. The origin of this software must not be misrepresented; you must 
00021      not claim that you wrote the original software.  If you use this 
00022      software in a product, an acknowledgment in the product 
00023      documentation would be appreciated but is not required.
00024 
00025   3. Altered source versions must be plainly marked as such, and must
00026      not be misrepresented as being the original software.
00027 
00028   4. The name of the author may not be used to endorse or promote 
00029      products derived from this software without specific prior written 
00030      permission.
00031 
00032   THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
00033   OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
00034   WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
00035   ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
00036   DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
00037   DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
00038   GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
00039   INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
00040   WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00041   NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00042   SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00043 
00044   Julian Seward, Cambridge, UK.
00045   jseward@bzip.org
00046   bzip2/libbzip2 version 1.0 of 21 March 2000
00047 
00048   This program is based on (at least) the work of:
00049      Mike Burrows
00050      David Wheeler
00051      Peter Fenwick
00052      Alistair Moffat
00053      Radford Neal
00054      Ian H. Witten
00055      Robert Sedgewick
00056      Jon L. Bentley
00057 
00058   For more information on these sources, see the manual.
00059 --*/
00060 
00061 /*--
00062    CHANGES
00063    ~~~~~~~
00064    0.9.0 -- original version.
00065 
00066    0.9.0a/b -- no changes in this file.
00067 
00068    0.9.0c
00069       * changed setting of nGroups in sendMTFValues() so as to 
00070         do a bit better on small files
00071 --*/
00072 
00073 #include "bzlib_private.h"
00074 
00075 
00076 /*---------------------------------------------------*/
00077 /*--- Bit stream I/O                              ---*/
00078 /*---------------------------------------------------*/
00079 
00080 /*---------------------------------------------------*/
00081 void BZ2_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 __inline__
00117 void bsW ( EState* s, Int32 n, UInt32 v )
00118 {
00119    bsNEEDW ( n );
00120    s->bsBuff |= (v << (32 - s->bsLive - n));
00121    s->bsLive += n;
00122 }
00123 
00124 
00125 /*---------------------------------------------------*/
00126 static
00127 void bsPutUInt32 ( EState* s, UInt32 u )
00128 {
00129    bsW ( s, 8, (u >> 24) & 0xffL );
00130    bsW ( s, 8, (u >> 16) & 0xffL );
00131    bsW ( s, 8, (u >>  8) & 0xffL );
00132    bsW ( s, 8,  u        & 0xffL );
00133 }
00134 
00135 
00136 /*---------------------------------------------------*/
00137 static
00138 void bsPutUChar ( EState* s, UChar c )
00139 {
00140    bsW( s, 8, (UInt32)c );
00141 }
00142 
00143 
00144 /*---------------------------------------------------*/
00145 /*--- The back end proper                         ---*/
00146 /*---------------------------------------------------*/
00147 
00148 /*---------------------------------------------------*/
00149 static
00150 void makeMaps_e ( EState* s )
00151 {
00152    Int32 i;
00153    s->nInUse = 0;
00154    for (i = 0; i < 256; i++)
00155       if (s->inUse[i]) {
00156          s->unseqToSeq[i] = s->nInUse;
00157          s->nInUse++;
00158       }
00159 }
00160 
00161 
00162 /*---------------------------------------------------*/
00163 static
00164 void generateMTFValues ( EState* s )
00165 {
00166    UChar   yy[256];
00167    Int32   i, j;
00168    Int32   zPend;
00169    Int32   wr;
00170    Int32   EOB;
00171 
00172    /* 
00173       After sorting (eg, here),
00174          s->arr1 [ 0 .. s->nblock-1 ] holds sorted order,
00175          and
00176          ((UChar*)s->arr2) [ 0 .. s->nblock-1 ] 
00177          holds the original block data.
00178 
00179       The first thing to do is generate the MTF values,
00180       and put them in
00181          ((UInt16*)s->arr1) [ 0 .. s->nblock-1 ].
00182       Because there are strictly fewer or equal MTF values
00183       than block values, ptr values in this area are overwritten
00184       with MTF values only when they are no longer needed.
00185 
00186       The final compressed bitstream is generated into the
00187       area starting at
00188          (UChar*) (&((UChar*)s->arr2)[s->nblock])
00189 
00190       These storage aliases are set up in bzCompressInit(),
00191       except for the last one, which is arranged in 
00192       compressBlock().
00193    */
00194    UInt32* ptr   = s->ptr;
00195    UChar* block  = s->block;
00196    UInt16* mtfv  = s->mtfv;
00197 
00198    makeMaps_e ( s );
00199    EOB = s->nInUse+1;
00200 
00201    for (i = 0; i <= EOB; i++) s->mtfFreq[i] = 0;
00202 
00203    wr = 0;
00204    zPend = 0;
00205    for (i = 0; i < s->nInUse; i++) yy[i] = (UChar) i;
00206 
00207    for (i = 0; i < s->nblock; i++) {
00208       UChar ll_i;
00209       AssertD ( wr <= i, "generateMTFValues(1)" );
00210       j = ptr[i]-1; if (j < 0) j += s->nblock;
00211       ll_i = s->unseqToSeq[block[j]];
00212       AssertD ( ll_i < s->nInUse, "generateMTFValues(2a)" );
00213 
00214       if (yy[0] == ll_i) { 
00215          zPend++;
00216       } else {
00217 
00218          if (zPend > 0) {
00219             zPend--;
00220             while (True) {
00221                if (zPend & 1) {
00222                   mtfv[wr] = BZ_RUNB; wr++; 
00223                   s->mtfFreq[BZ_RUNB]++; 
00224                } else {
00225                   mtfv[wr] = BZ_RUNA; wr++; 
00226                   s->mtfFreq[BZ_RUNA]++; 
00227                }
00228                if (zPend < 2) break;
00229                zPend = (zPend - 2) / 2;
00230             };
00231             zPend = 0;
00232          }
00233          {
00234             register UChar  rtmp;
00235             register UChar* ryy_j;
00236             register UChar  rll_i;
00237             rtmp  = yy[1];
00238             yy[1] = yy[0];
00239             ryy_j = &(yy[1]);
00240             rll_i = ll_i;
00241             while ( rll_i != rtmp ) {
00242                register UChar rtmp2;
00243                ryy_j++;
00244                rtmp2  = rtmp;
00245                rtmp   = *ryy_j;
00246                *ryy_j = rtmp2;
00247             };
00248             yy[0] = rtmp;
00249             j = ryy_j - &(yy[0]);
00250             mtfv[wr] = j+1; wr++; s->mtfFreq[j+1]++;
00251          }
00252 
00253       }
00254    }
00255 
00256    if (zPend > 0) {
00257       zPend--;
00258       while (True) {
00259          if (zPend & 1) {
00260             mtfv[wr] = BZ_RUNB; wr++; 
00261             s->mtfFreq[BZ_RUNB]++; 
00262          } else {
00263             mtfv[wr] = BZ_RUNA; wr++; 
00264             s->mtfFreq[BZ_RUNA]++; 
00265          }
00266          if (zPend < 2) break;
00267          zPend = (zPend - 2) / 2;
00268       };
00269       zPend = 0;
00270    }
00271 
00272    mtfv[wr] = EOB; wr++; s->mtfFreq[EOB]++;
00273 
00274    s->nMTF = wr;
00275 }
00276 
00277 
00278 /*---------------------------------------------------*/
00279 #define BZ_LESSER_ICOST  0
00280 #define BZ_GREATER_ICOST 15
00281 
00282 static
00283 void sendMTFValues ( EState* s )
00284 {
00285    Int32 v, t, i, j, gs, ge, totc, bt, bc, iter;
00286    Int32 nSelectors, alphaSize, minLen, maxLen, selCtr;
00287    Int32 nGroups, nBytes;
00288 
00289    /*--
00290    UChar  len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
00291    is a global since the decoder also needs it.
00292 
00293    Int32  code[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
00294    Int32  rfreq[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
00295    are also globals only used in this proc.
00296    Made global to keep stack frame size small.
00297    --*/
00298 
00299 
00300    UInt16 cost[BZ_N_GROUPS];
00301    Int32  fave[BZ_N_GROUPS];
00302 
00303    UInt16* mtfv = s->mtfv;
00304 
00305    if (s->verbosity >= 3)
00306       VPrintf3( "      %d in block, %d after MTF & 1-2 coding, "
00307                 "%d+2 syms in use\n", 
00308                 s->nblock, s->nMTF, s->nInUse );
00309 
00310    alphaSize = s->nInUse+2;
00311    for (t = 0; t < BZ_N_GROUPS; t++)
00312       for (v = 0; v < alphaSize; v++)
00313          s->len[t][v] = BZ_GREATER_ICOST;
00314 
00315    /*--- Decide how many coding tables to use ---*/
00316    AssertH ( s->nMTF > 0, 3001 );
00317    if (s->nMTF < 200)  nGroups = 2; else
00318    if (s->nMTF < 600)  nGroups = 3; else
00319    if (s->nMTF < 1200) nGroups = 4; else
00320    if (s->nMTF < 2400) nGroups = 5; else
00321                        nGroups = 6;
00322 
00323    /*--- Generate an initial set of coding tables ---*/
00324    { 
00325       Int32 nPart, remF, tFreq, aFreq;
00326 
00327       nPart = nGroups;
00328       remF  = s->nMTF;
00329       gs = 0;
00330       while (nPart > 0) {
00331          tFreq = remF / nPart;
00332          ge = gs-1;
00333          aFreq = 0;
00334          while (aFreq < tFreq && ge < alphaSize-1) {
00335             ge++;
00336             aFreq += s->mtfFreq[ge];
00337          }
00338 
00339          if (ge > gs 
00340              && nPart != nGroups && nPart != 1 
00341              && ((nGroups-nPart) % 2 == 1)) {
00342             aFreq -= s->mtfFreq[ge];
00343             ge--;
00344          }
00345 
00346          if (s->verbosity >= 3)
00347             VPrintf5( "      initial group %d, [%d .. %d], "
00348                       "has %d syms (%4.1f%%)\n",
00349                       nPart, gs, ge, aFreq, 
00350                       (100.0 * (float)aFreq) / (float)(s->nMTF) );
00351  
00352          for (v = 0; v < alphaSize; v++)
00353             if (v >= gs && v <= ge) 
00354                s->len[nPart-1][v] = BZ_LESSER_ICOST; else
00355                s->len[nPart-1][v] = BZ_GREATER_ICOST;
00356  
00357          nPart--;
00358          gs = ge+1;
00359          remF -= aFreq;
00360       }
00361    }
00362 
00363    /*--- 
00364       Iterate up to BZ_N_ITERS times to improve the tables.
00365    ---*/
00366    for (iter = 0; iter < BZ_N_ITERS; iter++) {
00367 
00368       for (t = 0; t < nGroups; t++) fave[t] = 0;
00369 
00370       for (t = 0; t < nGroups; t++)
00371          for (v = 0; v < alphaSize; v++)
00372             s->rfreq[t][v] = 0;
00373 
00374       /*---
00375         Set up an auxiliary length table which is used to fast-track
00376        the common case (nGroups == 6). 
00377       ---*/
00378       if (nGroups == 6) {
00379          for (v = 0; v < alphaSize; v++) {
00380             s->len_pack[v][0] = (s->len[1][v] << 16) | s->len[0][v];
00381             s->len_pack[v][1] = (s->len[3][v] << 16) | s->len[2][v];
00382             s->len_pack[v][2] = (s->len[5][v] << 16) | s->len[4][v];
00383         }
00384       }
00385 
00386       nSelectors = 0;
00387       totc = 0;
00388       gs = 0;
00389       while (True) {
00390 
00391          /*--- Set group start & end marks. --*/
00392          if (gs >= s->nMTF) break;
00393          ge = gs + BZ_G_SIZE - 1; 
00394          if (ge >= s->nMTF) ge = s->nMTF-1;
00395 
00396          /*-- 
00397             Calculate the cost of this group as coded
00398             by each of the coding tables.
00399          --*/
00400          for (t = 0; t < nGroups; t++) cost[t] = 0;
00401 
00402          if (nGroups == 6 && 50 == ge-gs+1) {
00403             /*--- fast track the common case ---*/
00404             register UInt32 cost01, cost23, cost45;
00405             register UInt16 icv;
00406             cost01 = cost23 = cost45 = 0;
00407 
00408 #           define BZ_ITER(nn)                \
00409                icv = mtfv[gs+(nn)];           \
00410                cost01 += s->len_pack[icv][0]; \
00411                cost23 += s->len_pack[icv][1]; \
00412                cost45 += s->len_pack[icv][2]; \
00413 
00414             BZ_ITER(0);  BZ_ITER(1);  BZ_ITER(2);  BZ_ITER(3);  BZ_ITER(4);
00415             BZ_ITER(5);  BZ_ITER(6);  BZ_ITER(7);  BZ_ITER(8);  BZ_ITER(9);
00416             BZ_ITER(10); BZ_ITER(11); BZ_ITER(12); BZ_ITER(13); BZ_ITER(14);
00417             BZ_ITER(15); BZ_ITER(16); BZ_ITER(17); BZ_ITER(18); BZ_ITER(19);
00418             BZ_ITER(20); BZ_ITER(21); BZ_ITER(22); BZ_ITER(23); BZ_ITER(24);
00419             BZ_ITER(25); BZ_ITER(26); BZ_ITER(27); BZ_ITER(28); BZ_ITER(29);
00420             BZ_ITER(30); BZ_ITER(31); BZ_ITER(32); BZ_ITER(33); BZ_ITER(34);
00421             BZ_ITER(35); BZ_ITER(36); BZ_ITER(37); BZ_ITER(38); BZ_ITER(39);
00422             BZ_ITER(40); BZ_ITER(41); BZ_ITER(42); BZ_ITER(43); BZ_ITER(44);
00423             BZ_ITER(45); BZ_ITER(46); BZ_ITER(47); BZ_ITER(48); BZ_ITER(49);
00424 
00425 #           undef BZ_ITER
00426 
00427             cost[0] = cost01 & 0xffff; cost[1] = cost01 >> 16;
00428             cost[2] = cost23 & 0xffff; cost[3] = cost23 >> 16;
00429             cost[4] = cost45 & 0xffff; cost[5] = cost45 >> 16;
00430 
00431          } else {
00432            /*--- slow version which correctly handles all situations ---*/
00433             for (i = gs; i <= ge; i++) { 
00434                UInt16 icv = mtfv[i];
00435                for (t = 0; t < nGroups; t++) cost[t] += s->len[t][icv];
00436             }
00437          }
00438  
00439          /*-- 
00440             Find the coding table which is best for this group,
00441             and record its identity in the selector table.
00442          --*/
00443          bc = 999999999; bt = -1;
00444          for (t = 0; t < nGroups; t++)
00445             if (cost[t] < bc) { bc = cost[t]; bt = t; };
00446          totc += bc;
00447          fave[bt]++;
00448          s->selector[nSelectors] = bt;
00449          nSelectors++;
00450 
00451          /*-- 
00452             Increment the symbol frequencies for the selected table.
00453           --*/
00454          if (nGroups == 6 && 50 == ge-gs+1) {
00455             /*--- fast track the common case ---*/
00456 
00457 #           define BZ_ITUR(nn) s->rfreq[bt][ mtfv[gs+(nn)] ]++
00458 
00459             BZ_ITUR(0);  BZ_ITUR(1);  BZ_ITUR(2);  BZ_ITUR(3);  BZ_ITUR(4);
00460             BZ_ITUR(5);  BZ_ITUR(6);  BZ_ITUR(7);  BZ_ITUR(8);  BZ_ITUR(9);
00461             BZ_ITUR(10); BZ_ITUR(11); BZ_ITUR(12); BZ_ITUR(13); BZ_ITUR(14);
00462             BZ_ITUR(15); BZ_ITUR(16); BZ_ITUR(17); BZ_ITUR(18); BZ_ITUR(19);
00463             BZ_ITUR(20); BZ_ITUR(21); BZ_ITUR(22); BZ_ITUR(23); BZ_ITUR(24);
00464             BZ_ITUR(25); BZ_ITUR(26); BZ_ITUR(27); BZ_ITUR(28); BZ_ITUR(29);
00465             BZ_ITUR(30); BZ_ITUR(31); BZ_ITUR(32); BZ_ITUR(33); BZ_ITUR(34);
00466             BZ_ITUR(35); BZ_ITUR(36); BZ_ITUR(37); BZ_ITUR(38); BZ_ITUR(39);
00467             BZ_ITUR(40); BZ_ITUR(41); BZ_ITUR(42); BZ_ITUR(43); BZ_ITUR(44);
00468             BZ_ITUR(45); BZ_ITUR(46); BZ_ITUR(47); BZ_ITUR(48); BZ_ITUR(49);
00469 
00470 #           undef BZ_ITUR
00471 
00472          } else {
00473            /*--- slow version which correctly handles all situations ---*/
00474             for (i = gs; i <= ge; i++)
00475                s->rfreq[bt][ mtfv[i] ]++;
00476          }
00477 
00478          gs = ge+1;
00479       }
00480       if (s->verbosity >= 3) {
00481          VPrintf2 ( "      pass %d: size is %d, grp uses are ", 
00482                    iter+1, totc/8 );
00483          for (t = 0; t < nGroups; t++)
00484             VPrintf1 ( "%d ", fave[t] );
00485          VPrintf0 ( "\n" );
00486       }
00487 
00488       /*--
00489         Recompute the tables based on the accumulated frequencies.
00490       --*/
00491       /* maxLen was changed from 20 to 17 in bzip2-1.0.3.  See 
00492          comment in huffman.c for details. */
00493       for (t = 0; t < nGroups; t++)
00494          BZ2_hbMakeCodeLengths ( &(s->len[t][0]), &(s->rfreq[t][0]), 
00495                                  alphaSize, 17 /*20*/ );
00496    }
00497 
00498 
00499    AssertH( nGroups < 8, 3002 );
00500    AssertH( nSelectors < 32768 &&
00501             nSelectors <= (2 + (900000 / BZ_G_SIZE)),
00502             3003 );
00503 
00504 
00505    /*--- Compute MTF values for the selectors. ---*/
00506    {
00507       UChar pos[BZ_N_GROUPS], ll_i, tmp2, tmp;
00508       for (i = 0; i < nGroups; i++) pos[i] = i;
00509       for (i = 0; i < nSelectors; i++) {
00510          ll_i = s->selector[i];
00511          j = 0;
00512          tmp = pos[j];
00513          while ( ll_i != tmp ) {
00514             j++;
00515             tmp2 = tmp;
00516             tmp = pos[j];
00517             pos[j] = tmp2;
00518          };
00519          pos[0] = tmp;
00520          s->selectorMtf[i] = j;
00521       }
00522    };
00523 
00524    /*--- Assign actual codes for the tables. --*/
00525    for (t = 0; t < nGroups; t++) {
00526       minLen = 32;
00527       maxLen = 0;
00528       for (i = 0; i < alphaSize; i++) {
00529          if (s->len[t][i] > maxLen) maxLen = s->len[t][i];
00530          if (s->len[t][i] < minLen) minLen = s->len[t][i];
00531       }
00532       AssertH ( !(maxLen > 17 /*20*/ ), 3004 );
00533       AssertH ( !(minLen < 1),  3005 );
00534       BZ2_hbAssignCodes ( &(s->code[t][0]), &(s->len[t][0]), 
00535                           minLen, maxLen, alphaSize );
00536    }
00537 
00538    /*--- Transmit the mapping table. ---*/
00539    { 
00540       Bool inUse16[16];
00541       for (i = 0; i < 16; i++) {
00542           inUse16[i] = False;
00543           for (j = 0; j < 16; j++)
00544              if (s->inUse[i * 16 + j]) inUse16[i] = True;
00545       }
00546      
00547       nBytes = s->numZ;
00548       for (i = 0; i < 16; i++)
00549          if (inUse16[i]) bsW(s,1,1); else bsW(s,1,0);
00550 
00551       for (i = 0; i < 16; i++)
00552          if (inUse16[i])
00553             for (j = 0; j < 16; j++) {
00554                if (s->inUse[i * 16 + j]) bsW(s,1,1); else bsW(s,1,0);
00555             }
00556 
00557       if (s->verbosity >= 3) 
00558          VPrintf1( "      bytes: mapping %d, ", s->numZ-nBytes );
00559    }
00560 
00561    /*--- Now the selectors. ---*/
00562    nBytes = s->numZ;
00563    bsW ( s, 3, nGroups );
00564    bsW ( s, 15, nSelectors );
00565    for (i = 0; i < nSelectors; i++) { 
00566       for (j = 0; j < s->selectorMtf[i]; j++) bsW(s,1,1);
00567       bsW(s,1,0);
00568    }
00569    if (s->verbosity >= 3)
00570       VPrintf1( "selectors %d, ", s->numZ-nBytes );
00571 
00572    /*--- Now the coding tables. ---*/
00573    nBytes = s->numZ;
00574 
00575    for (t = 0; t < nGroups; t++) {
00576       Int32 curr = s->len[t][0];
00577       bsW ( s, 5, curr );
00578       for (i = 0; i < alphaSize; i++) {
00579          while (curr < s->len[t][i]) { bsW(s,2,2); curr++; /* 10 */ };
00580          while (curr > s->len[t][i]) { bsW(s,2,3); curr--; /* 11 */ };
00581          bsW ( s, 1, 0 );
00582       }
00583    }
00584 
00585    if (s->verbosity >= 3)
00586       VPrintf1 ( "code lengths %d, ", s->numZ-nBytes );
00587 
00588    /*--- And finally, the block data proper ---*/
00589    nBytes = s->numZ;
00590    selCtr = 0;
00591    gs = 0;
00592    while (True) {
00593       if (gs >= s->nMTF) break;
00594       ge = gs + BZ_G_SIZE - 1; 
00595       if (ge >= s->nMTF) ge = s->nMTF-1;
00596       AssertH ( s->selector[selCtr] < nGroups, 3006 );
00597 
00598       if (nGroups == 6 && 50 == ge-gs+1) {
00599             /*--- fast track the common case ---*/
00600             UInt16 mtfv_i;
00601             UChar* s_len_sel_selCtr 
00602                = &(s->len[s->selector[selCtr]][0]);
00603             Int32* s_code_sel_selCtr
00604                = &(s->code[s->selector[selCtr]][0]);
00605 
00606 #           define BZ_ITAH(nn)                      \
00607                mtfv_i = mtfv[gs+(nn)];              \
00608                bsW ( s,                             \
00609                      s_len_sel_selCtr[mtfv_i],      \
00610                      s_code_sel_selCtr[mtfv_i] )
00611 
00612             BZ_ITAH(0);  BZ_ITAH(1);  BZ_ITAH(2);  BZ_ITAH(3);  BZ_ITAH(4);
00613             BZ_ITAH(5);  BZ_ITAH(6);  BZ_ITAH(7);  BZ_ITAH(8);  BZ_ITAH(9);
00614             BZ_ITAH(10); BZ_ITAH(11); BZ_ITAH(12); BZ_ITAH(13); BZ_ITAH(14);
00615             BZ_ITAH(15); BZ_ITAH(16); BZ_ITAH(17); BZ_ITAH(18); BZ_ITAH(19);
00616             BZ_ITAH(20); BZ_ITAH(21); BZ_ITAH(22); BZ_ITAH(23); BZ_ITAH(24);
00617             BZ_ITAH(25); BZ_ITAH(26); BZ_ITAH(27); BZ_ITAH(28); BZ_ITAH(29);
00618             BZ_ITAH(30); BZ_ITAH(31); BZ_ITAH(32); BZ_ITAH(33); BZ_ITAH(34);
00619             BZ_ITAH(35); BZ_ITAH(36); BZ_ITAH(37); BZ_ITAH(38); BZ_ITAH(39);
00620             BZ_ITAH(40); BZ_ITAH(41); BZ_ITAH(42); BZ_ITAH(43); BZ_ITAH(44);
00621             BZ_ITAH(45); BZ_ITAH(46); BZ_ITAH(47); BZ_ITAH(48); BZ_ITAH(49);
00622 
00623 #           undef BZ_ITAH
00624 
00625       } else {
00626         /*--- slow version which correctly handles all situations ---*/
00627          for (i = gs; i <= ge; i++) {
00628             bsW ( s, 
00629                   s->len  [s->selector[selCtr]] [mtfv[i]],
00630                   s->code [s->selector[selCtr]] [mtfv[i]] );
00631          }
00632       }
00633 
00634 
00635       gs = ge+1;
00636       selCtr++;
00637    }
00638    AssertH( selCtr == nSelectors, 3007 );
00639 
00640    if (s->verbosity >= 3)
00641       VPrintf1( "codes %d\n", s->numZ-nBytes );
00642 }
00643 
00644 
00645 /*---------------------------------------------------*/
00646 void BZ2_compressBlock ( EState* s, Bool is_last_block )
00647 {
00648    if (s->nblock > 0) {
00649 
00650       BZ_FINALISE_CRC ( s->blockCRC );
00651       s->combinedCRC = (s->combinedCRC << 1) | (s->combinedCRC >> 31);
00652       s->combinedCRC ^= s->blockCRC;
00653       if (s->blockNo > 1) s->numZ = 0;
00654 
00655       if (s->verbosity >= 2)
00656          VPrintf4( "    block %d: crc = 0x%08x, "
00657                    "combined CRC = 0x%08x, size = %d\n",
00658                    s->blockNo, s->blockCRC, s->combinedCRC, s->nblock );
00659 
00660       BZ2_blockSort ( s );
00661    }
00662 
00663    s->zbits = (UChar*) (&((UChar*)s->arr2)[s->nblock]);
00664 
00665    /*-- If this is the first block, create the stream header. --*/
00666    if (s->blockNo == 1) {
00667       BZ2_bsInitWrite ( s );
00668       bsPutUChar ( s, BZ_HDR_B );
00669       bsPutUChar ( s, BZ_HDR_Z );
00670       bsPutUChar ( s, BZ_HDR_h );
00671       bsPutUChar ( s, (UChar)(BZ_HDR_0 + s->blockSize100k) );
00672    }
00673 
00674    if (s->nblock > 0) {
00675 
00676       bsPutUChar ( s, 0x31 ); bsPutUChar ( s, 0x41 );
00677       bsPutUChar ( s, 0x59 ); bsPutUChar ( s, 0x26 );
00678       bsPutUChar ( s, 0x53 ); bsPutUChar ( s, 0x59 );
00679 
00680       /*-- Now the block's CRC, so it is in a known place. --*/
00681       bsPutUInt32 ( s, s->blockCRC );
00682 
00683       /*-- 
00684          Now a single bit indicating (non-)randomisation. 
00685          As of version 0.9.5, we use a better sorting algorithm
00686          which makes randomisation unnecessary.  So always set
00687          the randomised bit to 'no'.  Of course, the decoder
00688          still needs to be able to handle randomised blocks
00689          so as to maintain backwards compatibility with
00690          older versions of bzip2.
00691       --*/
00692       bsW(s,1,0);
00693 
00694       bsW ( s, 24, s->origPtr );
00695       generateMTFValues ( s );
00696       sendMTFValues ( s );
00697    }
00698 
00699 
00700    /*-- If this is the last block, add the stream trailer. --*/
00701    if (is_last_block) {
00702 
00703       bsPutUChar ( s, 0x17 ); bsPutUChar ( s, 0x72 );
00704       bsPutUChar ( s, 0x45 ); bsPutUChar ( s, 0x38 );
00705       bsPutUChar ( s, 0x50 ); bsPutUChar ( s, 0x90 );
00706       bsPutUInt32 ( s, s->combinedCRC );
00707       if (s->verbosity >= 2)
00708          VPrintf1( "    final combined CRC = 0x%08x\n   ", s->combinedCRC );
00709       bsFinishWrite ( s );
00710    }
00711 }
00712 
00713 
00714 /*-------------------------------------------------------------*/
00715 /*--- end                                        compress.c ---*/
00716 /*-------------------------------------------------------------*/