LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

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-2002 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@acm.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       for (t = 0; t < nGroups; t++)
00492          BZ2_hbMakeCodeLengths ( &(s->len[t][0]), &(s->rfreq[t][0]), 
00493                                  alphaSize, 20 );
00494    }
00495 
00496 
00497    AssertH( nGroups < 8, 3002 );
00498    AssertH( nSelectors < 32768 &&
00499             nSelectors <= (2 + (900000 / BZ_G_SIZE)),
00500             3003 );
00501 
00502 
00503    /*--- Compute MTF values for the selectors. ---*/
00504    {
00505       UChar pos[BZ_N_GROUPS], ll_i, tmp2, tmp;
00506       for (i = 0; i < nGroups; i++) pos[i] = i;
00507       for (i = 0; i < nSelectors; i++) {
00508          ll_i = s->selector[i];
00509          j = 0;
00510          tmp = pos[j];
00511          while ( ll_i != tmp ) {
00512             j++;
00513             tmp2 = tmp;
00514             tmp = pos[j];
00515             pos[j] = tmp2;
00516          };
00517          pos[0] = tmp;
00518          s->selectorMtf[i] = j;
00519       }
00520    };
00521 
00522    /*--- Assign actual codes for the tables. --*/
00523    for (t = 0; t < nGroups; t++) {
00524       minLen = 32;
00525       maxLen = 0;
00526       for (i = 0; i < alphaSize; i++) {
00527          if (s->len[t][i] > maxLen) maxLen = s->len[t][i];
00528          if (s->len[t][i] < minLen) minLen = s->len[t][i];
00529       }
00530       AssertH ( !(maxLen > 20), 3004 );
00531       AssertH ( !(minLen < 1),  3005 );
00532       BZ2_hbAssignCodes ( &(s->code[t][0]), &(s->len[t][0]), 
00533                           minLen, maxLen, alphaSize );
00534    }
00535 
00536    /*--- Transmit the mapping table. ---*/
00537    { 
00538       Bool inUse16[16];
00539       for (i = 0; i < 16; i++) {
00540           inUse16[i] = False;
00541           for (j = 0; j < 16; j++)
00542              if (s->inUse[i * 16 + j]) inUse16[i] = True;
00543       }
00544      
00545       nBytes = s->numZ;
00546       for (i = 0; i < 16; i++)
00547          if (inUse16[i]) bsW(s,1,1); else bsW(s,1,0);
00548 
00549       for (i = 0; i < 16; i++)
00550          if (inUse16[i])
00551             for (j = 0; j < 16; j++) {
00552                if (s->inUse[i * 16 + j]) bsW(s,1,1); else bsW(s,1,0);
00553             }
00554 
00555       if (s->verbosity >= 3) 
00556          VPrintf1( "      bytes: mapping %d, ", s->numZ-nBytes );
00557    }
00558 
00559    /*--- Now the selectors. ---*/
00560    nBytes = s->numZ;
00561    bsW ( s, 3, nGroups );
00562    bsW ( s, 15, nSelectors );
00563    for (i = 0; i < nSelectors; i++) { 
00564       for (j = 0; j < s->selectorMtf[i]; j++) bsW(s,1,1);
00565       bsW(s,1,0);
00566    }
00567    if (s->verbosity >= 3)
00568       VPrintf1( "selectors %d, ", s->numZ-nBytes );
00569 
00570    /*--- Now the coding tables. ---*/
00571    nBytes = s->numZ;
00572 
00573    for (t = 0; t < nGroups; t++) {
00574       Int32 curr = s->len[t][0];
00575       bsW ( s, 5, curr );
00576       for (i = 0; i < alphaSize; i++) {
00577          while (curr < s->len[t][i]) { bsW(s,2,2); curr++; /* 10 */ };
00578          while (curr > s->len[t][i]) { bsW(s,2,3); curr--; /* 11 */ };
00579          bsW ( s, 1, 0 );
00580       }
00581    }
00582 
00583    if (s->verbosity >= 3)
00584       VPrintf1 ( "code lengths %d, ", s->numZ-nBytes );
00585 
00586    /*--- And finally, the block data proper ---*/
00587    nBytes = s->numZ;
00588    selCtr = 0;
00589    gs = 0;
00590    while (True) {
00591       if (gs >= s->nMTF) break;
00592       ge = gs + BZ_G_SIZE - 1; 
00593       if (ge >= s->nMTF) ge = s->nMTF-1;
00594       AssertH ( s->selector[selCtr] < nGroups, 3006 );
00595 
00596       if (nGroups == 6 && 50 == ge-gs+1) {
00597             /*--- fast track the common case ---*/
00598             UInt16 mtfv_i;
00599             UChar* s_len_sel_selCtr 
00600                = &(s->len[s->selector[selCtr]][0]);
00601             Int32* s_code_sel_selCtr
00602                = &(s->code[s->selector[selCtr]][0]);
00603 
00604 #           define BZ_ITAH(nn)                      \
00605                mtfv_i = mtfv[gs+(nn)];              \
00606                bsW ( s,                             \
00607                      s_len_sel_selCtr[mtfv_i],      \
00608                      s_code_sel_selCtr[mtfv_i] )
00609 
00610             BZ_ITAH(0);  BZ_ITAH(1);  BZ_ITAH(2);  BZ_ITAH(3);  BZ_ITAH(4);
00611             BZ_ITAH(5);  BZ_ITAH(6);  BZ_ITAH(7);  BZ_ITAH(8);  BZ_ITAH(9);
00612             BZ_ITAH(10); BZ_ITAH(11); BZ_ITAH(12); BZ_ITAH(13); BZ_ITAH(14);
00613             BZ_ITAH(15); BZ_ITAH(16); BZ_ITAH(17); BZ_ITAH(18); BZ_ITAH(19);
00614             BZ_ITAH(20); BZ_ITAH(21); BZ_ITAH(22); BZ_ITAH(23); BZ_ITAH(24);
00615             BZ_ITAH(25); BZ_ITAH(26); BZ_ITAH(27); BZ_ITAH(28); BZ_ITAH(29);
00616             BZ_ITAH(30); BZ_ITAH(31); BZ_ITAH(32); BZ_ITAH(33); BZ_ITAH(34);
00617             BZ_ITAH(35); BZ_ITAH(36); BZ_ITAH(37); BZ_ITAH(38); BZ_ITAH(39);
00618             BZ_ITAH(40); BZ_ITAH(41); BZ_ITAH(42); BZ_ITAH(43); BZ_ITAH(44);
00619             BZ_ITAH(45); BZ_ITAH(46); BZ_ITAH(47); BZ_ITAH(48); BZ_ITAH(49);
00620 
00621 #           undef BZ_ITAH
00622 
00623       } else {
00624    /*--- slow version which correctly handles all situations ---*/
00625          for (i = gs; i <= ge; i++) {
00626             bsW ( s, 
00627                   s->len  [s->selector[selCtr]] [mtfv[i]],
00628                   s->code [s->selector[selCtr]] [mtfv[i]] );
00629          }
00630       }
00631 
00632 
00633       gs = ge+1;
00634       selCtr++;
00635    }
00636    AssertH( selCtr == nSelectors, 3007 );
00637 
00638    if (s->verbosity >= 3)
00639       VPrintf1( "codes %d\n", s->numZ-nBytes );
00640 }
00641 
00642 
00643 /*---------------------------------------------------*/
00644 void BZ2_compressBlock ( EState* s, Bool is_last_block )
00645 {
00646    if (s->nblock > 0) {
00647 
00648       BZ_FINALISE_CRC ( s->blockCRC );
00649       s->combinedCRC = (s->combinedCRC << 1) | (s->combinedCRC >> 31);
00650       s->combinedCRC ^= s->blockCRC;
00651       if (s->blockNo > 1) s->numZ = 0;
00652 
00653       if (s->verbosity >= 2)
00654          VPrintf4( "    block %d: crc = 0x%8x, "
00655                    "combined CRC = 0x%8x, size = %d\n",
00656                    s->blockNo, s->blockCRC, s->combinedCRC, s->nblock );
00657 
00658       BZ2_blockSort ( s );
00659    }
00660 
00661    s->zbits = (UChar*) (&((UChar*)s->arr2)[s->nblock]);
00662 
00663    /*-- If this is the first block, create the stream header. --*/
00664    if (s->blockNo == 1) {
00665       BZ2_bsInitWrite ( s );
00666       bsPutUChar ( s, BZ_HDR_B );
00667       bsPutUChar ( s, BZ_HDR_Z );
00668       bsPutUChar ( s, BZ_HDR_h );
00669       bsPutUChar ( s, (UChar)(BZ_HDR_0 + s->blockSize100k) );
00670    }
00671 
00672    if (s->nblock > 0) {
00673 
00674       bsPutUChar ( s, 0x31 ); bsPutUChar ( s, 0x41 );
00675       bsPutUChar ( s, 0x59 ); bsPutUChar ( s, 0x26 );
00676       bsPutUChar ( s, 0x53 ); bsPutUChar ( s, 0x59 );
00677 
00678       /*-- Now the block's CRC, so it is in a known place. --*/
00679       bsPutUInt32 ( s, s->blockCRC );
00680 
00681       /*-- 
00682          Now a single bit indicating (non-)randomisation. 
00683          As of version 0.9.5, we use a better sorting algorithm
00684          which makes randomisation unnecessary.  So always set
00685          the randomised bit to 'no'.  Of course, the decoder
00686          still needs to be able to handle randomised blocks
00687          so as to maintain backwards compatibility with
00688          older versions of bzip2.
00689       --*/
00690       bsW(s,1,0);
00691 
00692       bsW ( s, 24, s->origPtr );
00693       generateMTFValues ( s );
00694       sendMTFValues ( s );
00695    }
00696 
00697 
00698    /*-- If this is the last block, add the stream trailer. --*/
00699    if (is_last_block) {
00700 
00701       bsPutUChar ( s, 0x17 ); bsPutUChar ( s, 0x72 );
00702       bsPutUChar ( s, 0x45 ); bsPutUChar ( s, 0x38 );
00703       bsPutUChar ( s, 0x50 ); bsPutUChar ( s, 0x90 );
00704       bsPutUInt32 ( s, s->combinedCRC );
00705       if (s->verbosity >= 2)
00706          VPrintf1( "    final combined CRC = 0x%x\n   ", s->combinedCRC );
00707       bsFinishWrite ( s );
00708    }
00709 }
00710 
00711 
00712 /*-------------------------------------------------------------*/
00713 /*--- end                                        compress.c ---*/
00714 /*-------------------------------------------------------------*/