common/bzip2/compress.c

ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger/*-------------------------------------------------------------*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger/*--- Compression machinery (not incl block sorting)        ---*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger/*---                                            compress.c ---*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger/*-------------------------------------------------------------*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger/* ------------------------------------------------------------------
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   This file is part of bzip2/libbzip2, a program and library for
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   lossless, block-sorting data compression.
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
b9071c34cb3102be3bbda85c57015ea13193aa6bGordon Ross   bzip2/libbzip2 version 1.0.6 of 6 September 2010
b9071c34cb3102be3bbda85c57015ea13193aa6bGordon Ross   Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org>
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   Please read the WARNING, DISCLAIMER and PATENTS sections in the
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   README file.
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   This program is released under the terms of the license contained
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   in the file LICENSE.
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   ------------------------------------------------------------------ */
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger/* CHANGES
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger    0.9.0    -- original version.
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger    0.9.0a/b -- no changes in this file.
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger    0.9.0c   -- changed setting of nGroups in sendMTFValues()
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger                so as to do a bit better on small files
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
6d89ca534e2138511ecb76c02bcec1bcb83f685bIgor Kozhukhov#include <sys/ccompile.h>
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger#include "bzlib_private.h"
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger/*---------------------------------------------------*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger/*--- Bit stream I/O                              ---*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger/*---------------------------------------------------*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger/*---------------------------------------------------*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plaugervoid BZ2_bsInitWrite ( EState* s )
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger{
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   s->bsLive = 0;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   s->bsBuff = 0;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger}
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger/*---------------------------------------------------*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plaugerstatic
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plaugervoid bsFinishWrite ( EState* s )
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger{
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   while (s->bsLive > 0) {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      s->zbits[s->numZ] = (UChar)(s->bsBuff >> 24);
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      s->numZ++;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      s->bsBuff <<= 8;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      s->bsLive -= 8;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   }
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger}
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger/*---------------------------------------------------*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger#define bsNEEDW(nz)                           \
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger{                                             \
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   while (s->bsLive >= 8) {                   \
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      s->zbits[s->numZ]                       \
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         = (UChar)(s->bsBuff >> 24);          \
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      s->numZ++;                              \
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      s->bsBuff <<= 8;                        \
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      s->bsLive -= 8;                         \
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   }                                          \
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger}
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger/*---------------------------------------------------*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plaugerstatic
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger__inline__
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plaugervoid bsW ( EState* s, Int32 n, UInt32 v )
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger{
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   bsNEEDW ( n );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   s->bsBuff |= (v << (32 - s->bsLive - n));
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   s->bsLive += n;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger}
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger/*---------------------------------------------------*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plaugerstatic
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plaugervoid bsPutUInt32 ( EState* s, UInt32 u )
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger{
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   bsW ( s, 8, (u >> 24) & 0xffL );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   bsW ( s, 8, (u >> 16) & 0xffL );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   bsW ( s, 8, (u >>  8) & 0xffL );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   bsW ( s, 8,  u        & 0xffL );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger}
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger/*---------------------------------------------------*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plaugerstatic
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plaugervoid bsPutUChar ( EState* s, UChar c )
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger{
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   bsW( s, 8, (UInt32)c );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger}
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger/*---------------------------------------------------*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger/*--- The back end proper                         ---*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger/*---------------------------------------------------*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger/*---------------------------------------------------*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plaugerstatic
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plaugervoid makeMaps_e ( EState* s )
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger{
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   Int32 i;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   s->nInUse = 0;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   for (i = 0; i < 256; i++)
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      if (s->inUse[i]) {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         s->unseqToSeq[i] = s->nInUse;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         s->nInUse++;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      }
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger}
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger/*---------------------------------------------------*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plaugerstatic
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plaugervoid generateMTFValues ( EState* s )
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger{
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   UChar   yy[256];
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   Int32   i, j;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   Int32   zPend;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   Int32   wr;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   Int32   EOB;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   /*
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      After sorting (eg, here),
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         s->arr1 [ 0 .. s->nblock-1 ] holds sorted order,
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         and
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         ((UChar*)s->arr2) [ 0 .. s->nblock-1 ]
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         holds the original block data.
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      The first thing to do is generate the MTF values,
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      and put them in
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         ((UInt16*)s->arr1) [ 0 .. s->nblock-1 ].
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      Because there are strictly fewer or equal MTF values
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      than block values, ptr values in this area are overwritten
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      with MTF values only when they are no longer needed.
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      The final compressed bitstream is generated into the
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      area starting at
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         (UChar*) (&((UChar*)s->arr2)[s->nblock])
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      These storage aliases are set up in bzCompressInit(),
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      except for the last one, which is arranged in
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      compressBlock().
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   */
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   UInt32* ptr   = s->ptr;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   UChar* block  = s->block;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   UInt16* mtfv  = s->mtfv;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   makeMaps_e ( s );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   EOB = s->nInUse+1;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   for (i = 0; i <= EOB; i++) s->mtfFreq[i] = 0;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   wr = 0;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   zPend = 0;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   for (i = 0; i < s->nInUse; i++) yy[i] = (UChar) i;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   for (i = 0; i < s->nblock; i++) {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      UChar ll_i;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      AssertD ( wr <= i, "generateMTFValues(1)" );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      j = ptr[i]-1; if (j < 0) j += s->nblock;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      ll_i = s->unseqToSeq[block[j]];
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      AssertD ( ll_i < s->nInUse, "generateMTFValues(2a)" );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      if (yy[0] == ll_i) {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         zPend++;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      } else {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         if (zPend > 0) {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            zPend--;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            while (True) {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger               if (zPend & 1) {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger                  mtfv[wr] = BZ_RUNB; wr++;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger                  s->mtfFreq[BZ_RUNB]++;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger               } else {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger                  mtfv[wr] = BZ_RUNA; wr++;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger                  s->mtfFreq[BZ_RUNA]++;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger               }
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger               if (zPend < 2) break;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger               zPend = (zPend - 2) / 2;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            };
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            zPend = 0;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         }
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            register UChar  rtmp;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            register UChar* ryy_j;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            register UChar  rll_i;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            rtmp  = yy[1];
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            yy[1] = yy[0];
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            ryy_j = &(yy[1]);
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            rll_i = ll_i;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            while ( rll_i != rtmp ) {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger               register UChar rtmp2;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger               ryy_j++;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger               rtmp2  = rtmp;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger               rtmp   = *ryy_j;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger               *ryy_j = rtmp2;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            };
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            yy[0] = rtmp;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            j = ryy_j - &(yy[0]);
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            mtfv[wr] = j+1; wr++; s->mtfFreq[j+1]++;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         }
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      }
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   }
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   if (zPend > 0) {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      zPend--;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      while (True) {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         if (zPend & 1) {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            mtfv[wr] = BZ_RUNB; wr++;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            s->mtfFreq[BZ_RUNB]++;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         } else {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            mtfv[wr] = BZ_RUNA; wr++;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            s->mtfFreq[BZ_RUNA]++;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         }
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         if (zPend < 2) break;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         zPend = (zPend - 2) / 2;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      };
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      zPend = 0;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   }
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   mtfv[wr] = EOB; wr++; s->mtfFreq[EOB]++;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   s->nMTF = wr;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger}
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger/*---------------------------------------------------*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger#define BZ_LESSER_ICOST  0
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger#define BZ_GREATER_ICOST 15
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plaugerstatic
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plaugervoid sendMTFValues ( EState* s )
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger{
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   Int32 v, t, i, j, gs, ge, totc, bt, bc, iter;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   Int32 nSelectors, alphaSize, minLen, maxLen, selCtr;
6d89ca534e2138511ecb76c02bcec1bcb83f685bIgor Kozhukhov   Int32 nGroups, __GNU_UNUSED nBytes;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   /*--
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   UChar  len [BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   is a global since the decoder also needs it.
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   Int32  code[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   Int32  rfreq[BZ_N_GROUPS][BZ_MAX_ALPHA_SIZE];
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   are also globals only used in this proc.
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   Made global to keep stack frame size small.
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   --*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   UInt16 cost[BZ_N_GROUPS];
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   Int32  fave[BZ_N_GROUPS];
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   UInt16* mtfv = s->mtfv;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   if (s->verbosity >= 3)
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      VPrintf3( "      %d in block, %d after MTF & 1-2 coding, "
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger                "%d+2 syms in use\n",
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger                s->nblock, s->nMTF, s->nInUse );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   alphaSize = s->nInUse+2;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   for (t = 0; t < BZ_N_GROUPS; t++)
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      for (v = 0; v < alphaSize; v++)
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         s->len[t][v] = BZ_GREATER_ICOST;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   /*--- Decide how many coding tables to use ---*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   AssertH ( s->nMTF > 0, 3001 );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   if (s->nMTF < 200)  nGroups = 2; else
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   if (s->nMTF < 600)  nGroups = 3; else
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   if (s->nMTF < 1200) nGroups = 4; else
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   if (s->nMTF < 2400) nGroups = 5; else
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger                       nGroups = 6;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   /*--- Generate an initial set of coding tables ---*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      Int32 nPart, remF, tFreq, aFreq;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      nPart = nGroups;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      remF  = s->nMTF;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      gs = 0;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      while (nPart > 0) {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         tFreq = remF / nPart;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         ge = gs-1;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         aFreq = 0;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         while (aFreq < tFreq && ge < alphaSize-1) {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            ge++;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            aFreq += s->mtfFreq[ge];
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         }
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         if (ge > gs
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger             && nPart != nGroups && nPart != 1
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger             && ((nGroups-nPart) % 2 == 1)) {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            aFreq -= s->mtfFreq[ge];
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            ge--;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         }
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         if (s->verbosity >= 3)
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            VPrintf5( "      initial group %d, [%d .. %d], "
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger                      "has %d syms (%4.1f%%)\n",
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger                      nPart, gs, ge, aFreq,
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger                      (100.0 * (float)aFreq) / (float)(s->nMTF) );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         for (v = 0; v < alphaSize; v++)
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            if (v >= gs && v <= ge)
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger               s->len[nPart-1][v] = BZ_LESSER_ICOST; else
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger               s->len[nPart-1][v] = BZ_GREATER_ICOST;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         nPart--;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         gs = ge+1;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         remF -= aFreq;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      }
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   }
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   /*---
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      Iterate up to BZ_N_ITERS times to improve the tables.
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   ---*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   for (iter = 0; iter < BZ_N_ITERS; iter++) {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      for (t = 0; t < nGroups; t++) fave[t] = 0;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      for (t = 0; t < nGroups; t++)
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         for (v = 0; v < alphaSize; v++)
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            s->rfreq[t][v] = 0;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      /*---
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger        Set up an auxiliary length table which is used to fast-track
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger    the common case (nGroups == 6).
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      ---*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      if (nGroups == 6) {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         for (v = 0; v < alphaSize; v++) {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            s->len_pack[v][0] = (s->len[1][v] << 16) | s->len[0][v];
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            s->len_pack[v][1] = (s->len[3][v] << 16) | s->len[2][v];
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            s->len_pack[v][2] = (s->len[5][v] << 16) | s->len[4][v];
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger     }
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      }
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      nSelectors = 0;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      totc = 0;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      gs = 0;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      while (True) {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         /*--- Set group start & end marks. --*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         if (gs >= s->nMTF) break;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         ge = gs + BZ_G_SIZE - 1;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         if (ge >= s->nMTF) ge = s->nMTF-1;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         /*--
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            Calculate the cost of this group as coded
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            by each of the coding tables.
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         --*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         for (t = 0; t < nGroups; t++) cost[t] = 0;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         if (nGroups == 6 && 50 == ge-gs+1) {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            /*--- fast track the common case ---*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            register UInt32 cost01, cost23, cost45;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            register UInt16 icv;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            cost01 = cost23 = cost45 = 0;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger#           define BZ_ITER(nn)                \
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger               icv = mtfv[gs+(nn)];           \
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger               cost01 += s->len_pack[icv][0]; \
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger               cost23 += s->len_pack[icv][1]; \
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger               cost45 += s->len_pack[icv][2]; \
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            BZ_ITER(0);  BZ_ITER(1);  BZ_ITER(2);  BZ_ITER(3);  BZ_ITER(4);
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            BZ_ITER(5);  BZ_ITER(6);  BZ_ITER(7);  BZ_ITER(8);  BZ_ITER(9);
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            BZ_ITER(10); BZ_ITER(11); BZ_ITER(12); BZ_ITER(13); BZ_ITER(14);
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            BZ_ITER(15); BZ_ITER(16); BZ_ITER(17); BZ_ITER(18); BZ_ITER(19);
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            BZ_ITER(20); BZ_ITER(21); BZ_ITER(22); BZ_ITER(23); BZ_ITER(24);
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            BZ_ITER(25); BZ_ITER(26); BZ_ITER(27); BZ_ITER(28); BZ_ITER(29);
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            BZ_ITER(30); BZ_ITER(31); BZ_ITER(32); BZ_ITER(33); BZ_ITER(34);
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            BZ_ITER(35); BZ_ITER(36); BZ_ITER(37); BZ_ITER(38); BZ_ITER(39);
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            BZ_ITER(40); BZ_ITER(41); BZ_ITER(42); BZ_ITER(43); BZ_ITER(44);
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            BZ_ITER(45); BZ_ITER(46); BZ_ITER(47); BZ_ITER(48); BZ_ITER(49);
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger#           undef BZ_ITER
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            cost[0] = cost01 & 0xffff; cost[1] = cost01 >> 16;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            cost[2] = cost23 & 0xffff; cost[3] = cost23 >> 16;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            cost[4] = cost45 & 0xffff; cost[5] = cost45 >> 16;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         } else {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger        /*--- slow version which correctly handles all situations ---*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            for (i = gs; i <= ge; i++) {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger               UInt16 icv = mtfv[i];
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger               for (t = 0; t < nGroups; t++) cost[t] += s->len[t][icv];
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            }
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         }
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         /*--
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            Find the coding table which is best for this group,
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            and record its identity in the selector table.
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         --*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         bc = 999999999; bt = -1;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         for (t = 0; t < nGroups; t++)
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            if (cost[t] < bc) { bc = cost[t]; bt = t; };
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         totc += bc;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         fave[bt]++;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         s->selector[nSelectors] = bt;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         nSelectors++;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         /*--
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            Increment the symbol frequencies for the selected table.
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger          --*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         if (nGroups == 6 && 50 == ge-gs+1) {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            /*--- fast track the common case ---*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger#           define BZ_ITUR(nn) s->rfreq[bt][ mtfv[gs+(nn)] ]++
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            BZ_ITUR(0);  BZ_ITUR(1);  BZ_ITUR(2);  BZ_ITUR(3);  BZ_ITUR(4);
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            BZ_ITUR(5);  BZ_ITUR(6);  BZ_ITUR(7);  BZ_ITUR(8);  BZ_ITUR(9);
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            BZ_ITUR(10); BZ_ITUR(11); BZ_ITUR(12); BZ_ITUR(13); BZ_ITUR(14);
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            BZ_ITUR(15); BZ_ITUR(16); BZ_ITUR(17); BZ_ITUR(18); BZ_ITUR(19);
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            BZ_ITUR(20); BZ_ITUR(21); BZ_ITUR(22); BZ_ITUR(23); BZ_ITUR(24);
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            BZ_ITUR(25); BZ_ITUR(26); BZ_ITUR(27); BZ_ITUR(28); BZ_ITUR(29);
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            BZ_ITUR(30); BZ_ITUR(31); BZ_ITUR(32); BZ_ITUR(33); BZ_ITUR(34);
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            BZ_ITUR(35); BZ_ITUR(36); BZ_ITUR(37); BZ_ITUR(38); BZ_ITUR(39);
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            BZ_ITUR(40); BZ_ITUR(41); BZ_ITUR(42); BZ_ITUR(43); BZ_ITUR(44);
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            BZ_ITUR(45); BZ_ITUR(46); BZ_ITUR(47); BZ_ITUR(48); BZ_ITUR(49);
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger#           undef BZ_ITUR
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         } else {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger        /*--- slow version which correctly handles all situations ---*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            for (i = gs; i <= ge; i++)
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger               s->rfreq[bt][ mtfv[i] ]++;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         }
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         gs = ge+1;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      }
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      if (s->verbosity >= 3) {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         VPrintf2 ( "      pass %d: size is %d, grp uses are ",
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger                   iter+1, totc/8 );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         for (t = 0; t < nGroups; t++)
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            VPrintf1 ( "%d ", fave[t] );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         VPrintf0 ( "\n" );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      }
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      /*--
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger        Recompute the tables based on the accumulated frequencies.
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      --*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      /* maxLen was changed from 20 to 17 in bzip2-1.0.3.  See
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         comment in huffman.c for details. */
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      for (t = 0; t < nGroups; t++)
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         BZ2_hbMakeCodeLengths ( &(s->len[t][0]), &(s->rfreq[t][0]),
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger                                 alphaSize, 17 /*20*/ );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   }
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   AssertH( nGroups < 8, 3002 );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   AssertH( nSelectors < 32768 &&
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            nSelectors <= (2 + (900000 / BZ_G_SIZE)),
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            3003 );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   /*--- Compute MTF values for the selectors. ---*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      UChar pos[BZ_N_GROUPS], ll_i, tmp2, tmp;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      for (i = 0; i < nGroups; i++) pos[i] = i;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      for (i = 0; i < nSelectors; i++) {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         ll_i = s->selector[i];
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         j = 0;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         tmp = pos[j];
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         while ( ll_i != tmp ) {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            j++;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            tmp2 = tmp;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            tmp = pos[j];
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            pos[j] = tmp2;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         };
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         pos[0] = tmp;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         s->selectorMtf[i] = j;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      }
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   };
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   /*--- Assign actual codes for the tables. --*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   for (t = 0; t < nGroups; t++) {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      minLen = 32;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      maxLen = 0;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      for (i = 0; i < alphaSize; i++) {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         if (s->len[t][i] > maxLen) maxLen = s->len[t][i];
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         if (s->len[t][i] < minLen) minLen = s->len[t][i];
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      }
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      AssertH ( !(maxLen > 17 /*20*/ ), 3004 );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      AssertH ( !(minLen < 1),  3005 );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      BZ2_hbAssignCodes ( &(s->code[t][0]), &(s->len[t][0]),
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger                          minLen, maxLen, alphaSize );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   }
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   /*--- Transmit the mapping table. ---*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      Bool inUse16[16];
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      for (i = 0; i < 16; i++) {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger          inUse16[i] = False;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger          for (j = 0; j < 16; j++)
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger             if (s->inUse[i * 16 + j]) inUse16[i] = True;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      }
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      nBytes = s->numZ;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      for (i = 0; i < 16; i++)
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         if (inUse16[i]) bsW(s,1,1); else bsW(s,1,0);
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      for (i = 0; i < 16; i++)
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         if (inUse16[i])
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            for (j = 0; j < 16; j++) {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger               if (s->inUse[i * 16 + j]) bsW(s,1,1); else bsW(s,1,0);
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            }
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      if (s->verbosity >= 3)
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         VPrintf1( "      bytes: mapping %d, ", s->numZ-nBytes );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   }
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   /*--- Now the selectors. ---*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   nBytes = s->numZ;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   bsW ( s, 3, nGroups );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   bsW ( s, 15, nSelectors );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   for (i = 0; i < nSelectors; i++) {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      for (j = 0; j < s->selectorMtf[i]; j++) bsW(s,1,1);
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      bsW(s,1,0);
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   }
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   if (s->verbosity >= 3)
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      VPrintf1( "selectors %d, ", s->numZ-nBytes );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   /*--- Now the coding tables. ---*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   nBytes = s->numZ;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   for (t = 0; t < nGroups; t++) {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      Int32 curr = s->len[t][0];
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      bsW ( s, 5, curr );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      for (i = 0; i < alphaSize; i++) {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         while (curr < s->len[t][i]) { bsW(s,2,2); curr++; /* 10 */ };
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         while (curr > s->len[t][i]) { bsW(s,2,3); curr--; /* 11 */ };
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         bsW ( s, 1, 0 );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      }
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   }
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   if (s->verbosity >= 3)
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      VPrintf1 ( "code lengths %d, ", s->numZ-nBytes );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   /*--- And finally, the block data proper ---*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   nBytes = s->numZ;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   selCtr = 0;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   gs = 0;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   while (True) {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      if (gs >= s->nMTF) break;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      ge = gs + BZ_G_SIZE - 1;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      if (ge >= s->nMTF) ge = s->nMTF-1;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      AssertH ( s->selector[selCtr] < nGroups, 3006 );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      if (nGroups == 6 && 50 == ge-gs+1) {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            /*--- fast track the common case ---*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            UInt16 mtfv_i;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            UChar* s_len_sel_selCtr
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger               = &(s->len[s->selector[selCtr]][0]);
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            Int32* s_code_sel_selCtr
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger               = &(s->code[s->selector[selCtr]][0]);
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger#           define BZ_ITAH(nn)                      \
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger               mtfv_i = mtfv[gs+(nn)];              \
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger               bsW ( s,                             \
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger                     s_len_sel_selCtr[mtfv_i],      \
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger                     s_code_sel_selCtr[mtfv_i] )
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            BZ_ITAH(0);  BZ_ITAH(1);  BZ_ITAH(2);  BZ_ITAH(3);  BZ_ITAH(4);
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            BZ_ITAH(5);  BZ_ITAH(6);  BZ_ITAH(7);  BZ_ITAH(8);  BZ_ITAH(9);
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            BZ_ITAH(10); BZ_ITAH(11); BZ_ITAH(12); BZ_ITAH(13); BZ_ITAH(14);
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            BZ_ITAH(15); BZ_ITAH(16); BZ_ITAH(17); BZ_ITAH(18); BZ_ITAH(19);
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            BZ_ITAH(20); BZ_ITAH(21); BZ_ITAH(22); BZ_ITAH(23); BZ_ITAH(24);
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            BZ_ITAH(25); BZ_ITAH(26); BZ_ITAH(27); BZ_ITAH(28); BZ_ITAH(29);
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            BZ_ITAH(30); BZ_ITAH(31); BZ_ITAH(32); BZ_ITAH(33); BZ_ITAH(34);
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            BZ_ITAH(35); BZ_ITAH(36); BZ_ITAH(37); BZ_ITAH(38); BZ_ITAH(39);
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            BZ_ITAH(40); BZ_ITAH(41); BZ_ITAH(42); BZ_ITAH(43); BZ_ITAH(44);
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            BZ_ITAH(45); BZ_ITAH(46); BZ_ITAH(47); BZ_ITAH(48); BZ_ITAH(49);
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger#           undef BZ_ITAH
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      } else {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger     /*--- slow version which correctly handles all situations ---*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         for (i = gs; i <= ge; i++) {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger            bsW ( s,
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger                  s->len  [s->selector[selCtr]] [mtfv[i]],
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger                  s->code [s->selector[selCtr]] [mtfv[i]] );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         }
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      }
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      gs = ge+1;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      selCtr++;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   }
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   AssertH( selCtr == nSelectors, 3007 );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   if (s->verbosity >= 3)
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      VPrintf1( "codes %d\n", s->numZ-nBytes );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger}
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger/*---------------------------------------------------*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plaugervoid BZ2_compressBlock ( EState* s, Bool is_last_block )
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger{
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   if (s->nblock > 0) {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      BZ_FINALISE_CRC ( s->blockCRC );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      s->combinedCRC = (s->combinedCRC << 1) | (s->combinedCRC >> 31);
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      s->combinedCRC ^= s->blockCRC;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      if (s->blockNo > 1) s->numZ = 0;
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      if (s->verbosity >= 2)
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         VPrintf4( "    block %d: crc = 0x%08x, "
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger                   "combined CRC = 0x%08x, size = %d\n",
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger                   s->blockNo, s->blockCRC, s->combinedCRC, s->nblock );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      BZ2_blockSort ( s );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   }
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   s->zbits = (UChar*) (&((UChar*)s->arr2)[s->nblock]);
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   /*-- If this is the first block, create the stream header. --*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   if (s->blockNo == 1) {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      BZ2_bsInitWrite ( s );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      bsPutUChar ( s, BZ_HDR_B );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      bsPutUChar ( s, BZ_HDR_Z );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      bsPutUChar ( s, BZ_HDR_h );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      bsPutUChar ( s, (UChar)(BZ_HDR_0 + s->blockSize100k) );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   }
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   if (s->nblock > 0) {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      bsPutUChar ( s, 0x31 ); bsPutUChar ( s, 0x41 );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      bsPutUChar ( s, 0x59 ); bsPutUChar ( s, 0x26 );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      bsPutUChar ( s, 0x53 ); bsPutUChar ( s, 0x59 );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      /*-- Now the block's CRC, so it is in a known place. --*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      bsPutUInt32 ( s, s->blockCRC );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      /*--
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         Now a single bit indicating (non-)randomisation.
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         As of version 0.9.5, we use a better sorting algorithm
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         which makes randomisation unnecessary.  So always set
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         the randomised bit to 'no'.  Of course, the decoder
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         still needs to be able to handle randomised blocks
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         so as to maintain backwards compatibility with
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         older versions of bzip2.
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      --*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      bsW(s,1,0);
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      bsW ( s, 24, s->origPtr );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      generateMTFValues ( s );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      sendMTFValues ( s );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   }
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   /*-- If this is the last block, add the stream trailer. --*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   if (is_last_block) {
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      bsPutUChar ( s, 0x17 ); bsPutUChar ( s, 0x72 );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      bsPutUChar ( s, 0x45 ); bsPutUChar ( s, 0x38 );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      bsPutUChar ( s, 0x50 ); bsPutUChar ( s, 0x90 );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      bsPutUInt32 ( s, s->combinedCRC );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      if (s->verbosity >= 2)
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger         VPrintf1( "    final combined CRC = 0x%08x\n   ", s->combinedCRC );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger      bsFinishWrite ( s );
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger   }
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger}
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger/*-------------------------------------------------------------*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger/*--- end                                        compress.c ---*/
ca3e8d88e8c867355e441fbc914c52e7416fc537Dave Plauger/*-------------------------------------------------------------*/