Back to index

avfs  1.0.1
Classes | Defines | Typedefs | Functions | Variables
bzlib_private.h File Reference
#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include "bzlib.h"
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes

struct  EState
struct  DState

Defines

#define BZ_VERSION   "1.0.6, 6-Sept-2010"
#define True   ((Bool)1)
#define False   ((Bool)0)
#define __inline__   /* */
#define AssertH(cond, errcode)   { if (!(cond)) BZ2_bz__AssertH__fail ( errcode ); }
#define AssertD(cond, msg)   /* */
#define VPrintf0(zf)   fprintf(stderr,zf)
#define VPrintf1(zf, za1)   fprintf(stderr,zf,za1)
#define VPrintf2(zf, za1, za2)   fprintf(stderr,zf,za1,za2)
#define VPrintf3(zf, za1, za2, za3)   fprintf(stderr,zf,za1,za2,za3)
#define VPrintf4(zf, za1, za2, za3, za4)   fprintf(stderr,zf,za1,za2,za3,za4)
#define VPrintf5(zf, za1, za2, za3, za4, za5)   fprintf(stderr,zf,za1,za2,za3,za4,za5)
#define BZALLOC(nnn)   (strm->bzalloc)(strm->opaque,(nnn),1)
#define BZFREE(ppp)   (strm->bzfree)(strm->opaque,(ppp))
#define BZ_HDR_B   0x42 /* 'B' */
#define BZ_HDR_Z   0x5a /* 'Z' */
#define BZ_HDR_h   0x68 /* 'h' */
#define BZ_HDR_0   0x30 /* '0' */
#define BZ_MAX_ALPHA_SIZE   258
#define BZ_MAX_CODE_LEN   23
#define BZ_RUNA   0
#define BZ_RUNB   1
#define BZ_N_GROUPS   6
#define BZ_G_SIZE   50
#define BZ_N_ITERS   4
#define BZ_MAX_SELECTORS   (2 + (900000 / BZ_G_SIZE))
#define BZ_RAND_DECLS
#define BZ_RAND_INIT_MASK
#define BZ_RAND_MASK   ((s->rNToGo == 1) ? 1 : 0)
#define BZ_RAND_UPD_MASK
#define BZ_INITIALISE_CRC(crcVar)
#define BZ_FINALISE_CRC(crcVar)
#define BZ_UPDATE_CRC(crcVar, cha)
#define BZ_M_IDLE   1
#define BZ_M_RUNNING   2
#define BZ_M_FLUSHING   3
#define BZ_M_FINISHING   4
#define BZ_S_OUTPUT   1
#define BZ_S_INPUT   2
#define BZ_N_RADIX   2
#define BZ_N_QSORT   12
#define BZ_N_SHELL   18
#define BZ_N_OVERSHOOT   (BZ_N_RADIX + BZ_N_QSORT + BZ_N_SHELL + 2)
#define BZ_X_IDLE   1
#define BZ_X_OUTPUT   2
#define BZ_X_MAGIC_1   10
#define BZ_X_MAGIC_2   11
#define BZ_X_MAGIC_3   12
#define BZ_X_MAGIC_4   13
#define BZ_X_BLKHDR_1   14
#define BZ_X_BLKHDR_2   15
#define BZ_X_BLKHDR_3   16
#define BZ_X_BLKHDR_4   17
#define BZ_X_BLKHDR_5   18
#define BZ_X_BLKHDR_6   19
#define BZ_X_BCRC_1   20
#define BZ_X_BCRC_2   21
#define BZ_X_BCRC_3   22
#define BZ_X_BCRC_4   23
#define BZ_X_RANDBIT   24
#define BZ_X_ORIGPTR_1   25
#define BZ_X_ORIGPTR_2   26
#define BZ_X_ORIGPTR_3   27
#define BZ_X_MAPPING_1   28
#define BZ_X_MAPPING_2   29
#define BZ_X_SELECTOR_1   30
#define BZ_X_SELECTOR_2   31
#define BZ_X_SELECTOR_3   32
#define BZ_X_CODING_1   33
#define BZ_X_CODING_2   34
#define BZ_X_CODING_3   35
#define BZ_X_MTF_1   36
#define BZ_X_MTF_2   37
#define BZ_X_MTF_3   38
#define BZ_X_MTF_4   39
#define BZ_X_MTF_5   40
#define BZ_X_MTF_6   41
#define BZ_X_ENDHDR_2   42
#define BZ_X_ENDHDR_3   43
#define BZ_X_ENDHDR_4   44
#define BZ_X_ENDHDR_5   45
#define BZ_X_ENDHDR_6   46
#define BZ_X_CCRC_1   47
#define BZ_X_CCRC_2   48
#define BZ_X_CCRC_3   49
#define BZ_X_CCRC_4   50
#define MTFA_SIZE   4096
#define MTFL_SIZE   16
#define BZ_GET_FAST(cccc)
#define BZ_GET_FAST_C(cccc)
#define SET_LL4(i, n)
#define GET_LL4(i)   ((((UInt32)(s->ll4[(i) >> 1])) >> (((i) << 2) & 0x4)) & 0xF)
#define SET_LL(i, n)
#define GET_LL(i)   (((UInt32)s->ll16[i]) | (GET_LL4(i) << 16))
#define BZ_GET_SMALL(cccc)

Typedefs

typedef char Char
typedef unsigned char Bool
typedef unsigned char UChar
typedef int Int32
typedef unsigned int UInt32
typedef short Int16
typedef unsigned short UInt16

Functions

void BZ2_bz__AssertH__fail (int errcode)
void BZ2_blockSort (EState *)
void BZ2_compressBlock (EState *, Bool)
void BZ2_bsInitWrite (EState *)
void BZ2_hbAssignCodes (Int32 *, UChar *, Int32, Int32, Int32)
void BZ2_hbMakeCodeLengths (UChar *, Int32 *, Int32, Int32)
Int32 BZ2_indexIntoF (Int32, Int32 *)
Int32 BZ2_decompress (DState *)
void BZ2_hbCreateDecodeTables (Int32 *, Int32 *, Int32 *, UChar *, Int32, Int32, Int32)

Variables

Int32 BZ2_rNums [512]
UInt32 BZ2_crc32Table [256]

Class Documentation

struct EState

Definition at line 204 of file bzlib_private.h.

Collaboration diagram for EState:
Class Members
UInt32 * arr1
UInt32 * arr2
UInt32 avail_in_expect
UChar * block
UInt32 blockCRC
Int32 blockNo
Int32 blockSize100k
UInt32 bsBuff
Int32 bsLive
BZ_RAND_DECLS
Int32 code
UInt32 combinedCRC
UInt32 * ftab
Bool inUse
UChar len
UInt32 len_pack
Int32 mode
Int32 mtfFreq
UInt16 * mtfv
Int32 nblock
Int32 nblockMAX
Int32 nInUse
Int32 nMTF
Int32 numZ
Int32 origPtr
UInt32 * ptr
Int32 rfreq
UChar selector
UChar selectorMtf
Int32 state
UInt32 state_in_ch
Int32 state_in_len
Int32 state_out_pos
bz_stream * strm
UChar unseqToSeq
Int32 verbosity
Int32 workFactor
UChar * zbits

Define Documentation

#define __inline__   /* */

Definition at line 61 of file bzlib_private.h.

#define AssertD (   cond,
  msg 
)    /* */

Definition at line 78 of file bzlib_private.h.

#define AssertH (   cond,
  errcode 
)    { if (!(cond)) BZ2_bz__AssertH__fail ( errcode ); }

Definition at line 67 of file bzlib_private.h.

#define BZ_FINALISE_CRC (   crcVar)
Value:
{                                              \
   crcVar = ~(crcVar);                         \
}

Definition at line 170 of file bzlib_private.h.

#define BZ_G_SIZE   50

Definition at line 130 of file bzlib_private.h.

#define BZ_GET_FAST (   cccc)
Value:
/* c_tPos is unsigned, hence test < 0 is pointless. */ \
    if (s->tPos >= (UInt32)100000 * (UInt32)s->blockSize100k) return True; \
    s->tPos = s->tt[s->tPos];                 \
    cccc = (UChar)(s->tPos & 0xff);           \
    s->tPos >>= 8;

Definition at line 457 of file bzlib_private.h.

#define BZ_GET_FAST_C (   cccc)
Value:
/* c_tPos is unsigned, hence test < 0 is pointless. */ \
    if (c_tPos >= (UInt32)100000 * (UInt32)ro_blockSize100k) return True; \
    c_tPos = c_tt[c_tPos];                    \
    cccc = (UChar)(c_tPos & 0xff);            \
    c_tPos >>= 8;

Definition at line 464 of file bzlib_private.h.

#define BZ_GET_SMALL (   cccc)
Value:
/* c_tPos is unsigned, hence test < 0 is pointless. */ \
    if (s->tPos >= (UInt32)100000 * (UInt32)s->blockSize100k) return True; \
    cccc = BZ2_indexIntoF ( s->tPos, s->cftab );    \
    s->tPos = GET_LL(s->tPos);

Definition at line 488 of file bzlib_private.h.

#define BZ_HDR_0   0x30 /* '0' */

Definition at line 119 of file bzlib_private.h.

#define BZ_HDR_B   0x42 /* 'B' */

Definition at line 116 of file bzlib_private.h.

#define BZ_HDR_h   0x68 /* 'h' */

Definition at line 118 of file bzlib_private.h.

#define BZ_HDR_Z   0x5a /* 'Z' */

Definition at line 117 of file bzlib_private.h.

#define BZ_INITIALISE_CRC (   crcVar)
Value:
{                                              \
   crcVar = 0xffffffffL;                       \
}

Definition at line 165 of file bzlib_private.h.

#define BZ_M_FINISHING   4

Definition at line 189 of file bzlib_private.h.

#define BZ_M_FLUSHING   3

Definition at line 188 of file bzlib_private.h.

#define BZ_M_IDLE   1

Definition at line 186 of file bzlib_private.h.

#define BZ_M_RUNNING   2

Definition at line 187 of file bzlib_private.h.

#define BZ_MAX_ALPHA_SIZE   258

Definition at line 123 of file bzlib_private.h.

#define BZ_MAX_CODE_LEN   23

Definition at line 124 of file bzlib_private.h.

#define BZ_MAX_SELECTORS   (2 + (900000 / BZ_G_SIZE))

Definition at line 133 of file bzlib_private.h.

#define BZ_N_GROUPS   6

Definition at line 129 of file bzlib_private.h.

#define BZ_N_ITERS   4

Definition at line 131 of file bzlib_private.h.

Definition at line 197 of file bzlib_private.h.

#define BZ_N_QSORT   12

Definition at line 195 of file bzlib_private.h.

#define BZ_N_RADIX   2

Definition at line 194 of file bzlib_private.h.

#define BZ_N_SHELL   18

Definition at line 196 of file bzlib_private.h.

#define BZ_RAND_DECLS
Value:
Int32 rNToGo;                               \
   Int32 rTPos                                 \

Definition at line 141 of file bzlib_private.h.

Value:
s->rNToGo = 0;                              \
   s->rTPos  = 0                               \

Definition at line 145 of file bzlib_private.h.

#define BZ_RAND_MASK   ((s->rNToGo == 1) ? 1 : 0)

Definition at line 149 of file bzlib_private.h.

Value:
if (s->rNToGo == 0) {                       \
      s->rNToGo = BZ2_rNums[s->rTPos];         \
      s->rTPos++;                              \
      if (s->rTPos == 512) s->rTPos = 0;       \
   }                                           \
   s->rNToGo--;

Definition at line 151 of file bzlib_private.h.

#define BZ_RUNA   0

Definition at line 126 of file bzlib_private.h.

#define BZ_RUNB   1

Definition at line 127 of file bzlib_private.h.

#define BZ_S_INPUT   2

Definition at line 192 of file bzlib_private.h.

#define BZ_S_OUTPUT   1

Definition at line 191 of file bzlib_private.h.

#define BZ_UPDATE_CRC (   crcVar,
  cha 
)
Value:
{                                              \
   crcVar = (crcVar << 8) ^                    \
            BZ2_crc32Table[(crcVar >> 24) ^    \
                           ((UChar)cha)];      \
}

Definition at line 175 of file bzlib_private.h.

#define BZ_VERSION   "1.0.6, 6-Sept-2010"

Definition at line 47 of file bzlib_private.h.

#define BZ_X_BCRC_1   20

Definition at line 312 of file bzlib_private.h.

#define BZ_X_BCRC_2   21

Definition at line 313 of file bzlib_private.h.

#define BZ_X_BCRC_3   22

Definition at line 314 of file bzlib_private.h.

#define BZ_X_BCRC_4   23

Definition at line 315 of file bzlib_private.h.

#define BZ_X_BLKHDR_1   14

Definition at line 306 of file bzlib_private.h.

#define BZ_X_BLKHDR_2   15

Definition at line 307 of file bzlib_private.h.

#define BZ_X_BLKHDR_3   16

Definition at line 308 of file bzlib_private.h.

#define BZ_X_BLKHDR_4   17

Definition at line 309 of file bzlib_private.h.

#define BZ_X_BLKHDR_5   18

Definition at line 310 of file bzlib_private.h.

#define BZ_X_BLKHDR_6   19

Definition at line 311 of file bzlib_private.h.

#define BZ_X_CCRC_1   47

Definition at line 339 of file bzlib_private.h.

#define BZ_X_CCRC_2   48

Definition at line 340 of file bzlib_private.h.

#define BZ_X_CCRC_3   49

Definition at line 341 of file bzlib_private.h.

#define BZ_X_CCRC_4   50

Definition at line 342 of file bzlib_private.h.

#define BZ_X_CODING_1   33

Definition at line 325 of file bzlib_private.h.

#define BZ_X_CODING_2   34

Definition at line 326 of file bzlib_private.h.

#define BZ_X_CODING_3   35

Definition at line 327 of file bzlib_private.h.

#define BZ_X_ENDHDR_2   42

Definition at line 334 of file bzlib_private.h.

#define BZ_X_ENDHDR_3   43

Definition at line 335 of file bzlib_private.h.

#define BZ_X_ENDHDR_4   44

Definition at line 336 of file bzlib_private.h.

#define BZ_X_ENDHDR_5   45

Definition at line 337 of file bzlib_private.h.

#define BZ_X_ENDHDR_6   46

Definition at line 338 of file bzlib_private.h.

#define BZ_X_IDLE   1

Definition at line 299 of file bzlib_private.h.

#define BZ_X_MAGIC_1   10

Definition at line 302 of file bzlib_private.h.

#define BZ_X_MAGIC_2   11

Definition at line 303 of file bzlib_private.h.

#define BZ_X_MAGIC_3   12

Definition at line 304 of file bzlib_private.h.

#define BZ_X_MAGIC_4   13

Definition at line 305 of file bzlib_private.h.

#define BZ_X_MAPPING_1   28

Definition at line 320 of file bzlib_private.h.

#define BZ_X_MAPPING_2   29

Definition at line 321 of file bzlib_private.h.

#define BZ_X_MTF_1   36

Definition at line 328 of file bzlib_private.h.

#define BZ_X_MTF_2   37

Definition at line 329 of file bzlib_private.h.

#define BZ_X_MTF_3   38

Definition at line 330 of file bzlib_private.h.

#define BZ_X_MTF_4   39

Definition at line 331 of file bzlib_private.h.

#define BZ_X_MTF_5   40

Definition at line 332 of file bzlib_private.h.

#define BZ_X_MTF_6   41

Definition at line 333 of file bzlib_private.h.

#define BZ_X_ORIGPTR_1   25

Definition at line 317 of file bzlib_private.h.

#define BZ_X_ORIGPTR_2   26

Definition at line 318 of file bzlib_private.h.

#define BZ_X_ORIGPTR_3   27

Definition at line 319 of file bzlib_private.h.

#define BZ_X_OUTPUT   2

Definition at line 300 of file bzlib_private.h.

#define BZ_X_RANDBIT   24

Definition at line 316 of file bzlib_private.h.

#define BZ_X_SELECTOR_1   30

Definition at line 322 of file bzlib_private.h.

#define BZ_X_SELECTOR_2   31

Definition at line 323 of file bzlib_private.h.

#define BZ_X_SELECTOR_3   32

Definition at line 324 of file bzlib_private.h.

#define BZALLOC (   nnn)    (strm->bzalloc)(strm->opaque,(nnn),1)

Definition at line 110 of file bzlib_private.h.

#define BZFREE (   ppp)    (strm->bzfree)(strm->opaque,(ppp))

Definition at line 111 of file bzlib_private.h.

#define False   ((Bool)0)

Definition at line 58 of file bzlib_private.h.

#define GET_LL (   i)    (((UInt32)s->ll16[i]) | (GET_LL4(i) << 16))

Definition at line 485 of file bzlib_private.h.

#define GET_LL4 (   i)    ((((UInt32)(s->ll4[(i) >> 1])) >> (((i) << 2) & 0x4)) & 0xF)

Definition at line 477 of file bzlib_private.h.

#define MTFA_SIZE   4096

Definition at line 348 of file bzlib_private.h.

#define MTFL_SIZE   16

Definition at line 349 of file bzlib_private.h.

#define SET_LL (   i,
 
)
Value:
{ s->ll16[i] = (UInt16)(n & 0x0000ffff);  \
     SET_LL4(i, n >> 16);                    \
   }

Definition at line 480 of file bzlib_private.h.

#define SET_LL4 (   i,
 
)
Value:
{ if (((i) & 0x1) == 0)                                    \
        s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0xf0) | (n); else    \
        s->ll4[(i) >> 1] = (s->ll4[(i) >> 1] & 0x0f) | ((n) << 4);  \
   }

Definition at line 471 of file bzlib_private.h.

#define True   ((Bool)1)

Definition at line 57 of file bzlib_private.h.

#define VPrintf0 (   zf)    fprintf(stderr,zf)

Definition at line 81 of file bzlib_private.h.

#define VPrintf1 (   zf,
  za1 
)    fprintf(stderr,zf,za1)

Definition at line 83 of file bzlib_private.h.

#define VPrintf2 (   zf,
  za1,
  za2 
)    fprintf(stderr,zf,za1,za2)

Definition at line 85 of file bzlib_private.h.

#define VPrintf3 (   zf,
  za1,
  za2,
  za3 
)    fprintf(stderr,zf,za1,za2,za3)

Definition at line 87 of file bzlib_private.h.

#define VPrintf4 (   zf,
  za1,
  za2,
  za3,
  za4 
)    fprintf(stderr,zf,za1,za2,za3,za4)

Definition at line 89 of file bzlib_private.h.

#define VPrintf5 (   zf,
  za1,
  za2,
  za3,
  za4,
  za5 
)    fprintf(stderr,zf,za1,za2,za3,za4,za5)

Definition at line 91 of file bzlib_private.h.


Typedef Documentation

typedef unsigned char Bool

Definition at line 50 of file bzlib_private.h.

typedef char Char

Definition at line 49 of file bzlib_private.h.

typedef short Int16

Definition at line 54 of file bzlib_private.h.

typedef int Int32

Definition at line 52 of file bzlib_private.h.

typedef unsigned char UChar

Definition at line 51 of file bzlib_private.h.

typedef unsigned short UInt16

Definition at line 55 of file bzlib_private.h.

typedef unsigned int UInt32

Definition at line 53 of file bzlib_private.h.


Function Documentation

void BZ2_blockSort ( EState )

Definition at line 1031 of file blocksort.c.

{
   UInt32* ptr    = s->ptr; 
   UChar*  block  = s->block;
   UInt32* ftab   = s->ftab;
   Int32   nblock = s->nblock;
   Int32   verb   = s->verbosity;
   Int32   wfact  = s->workFactor;
   UInt16* quadrant;
   Int32   budget;
   Int32   budgetInit;
   Int32   i;

   if (nblock < 10000) {
      fallbackSort ( s->arr1, s->arr2, ftab, nblock, verb );
   } else {
      /* Calculate the location for quadrant, remembering to get
         the alignment right.  Assumes that &(block[0]) is at least
         2-byte aligned -- this should be ok since block is really
         the first section of arr2.
      */
      i = nblock+BZ_N_OVERSHOOT;
      if (i & 1) i++;
      quadrant = (UInt16*)(&(block[i]));

      /* (wfact-1) / 3 puts the default-factor-30
         transition point at very roughly the same place as 
         with v0.1 and v0.9.0.  
         Not that it particularly matters any more, since the
         resulting compressed stream is now the same regardless
         of whether or not we use the main sort or fallback sort.
      */
      if (wfact < 1  ) wfact = 1;
      if (wfact > 100) wfact = 100;
      budgetInit = nblock * ((wfact-1) / 3);
      budget = budgetInit;

      mainSort ( ptr, block, quadrant, ftab, nblock, verb, &budget );
      if (verb >= 3) 
         VPrintf3 ( "      %d work, %d block, ratio %5.2f\n",
                    budgetInit - budget,
                    nblock, 
                    (float)(budgetInit - budget) /
                    (float)(nblock==0 ? 1 : nblock) ); 
      if (budget < 0) {
         if (verb >= 2) 
            VPrintf0 ( "    too repetitive; using fallback"
                       " sorting algorithm\n" );
         fallbackSort ( s->arr1, s->arr2, ftab, nblock, verb );
      }
   }

   s->origPtr = -1;
   for (i = 0; i < s->nblock; i++)
      if (ptr[i] == 0)
         { s->origPtr = i; break; };

   AssertH( s->origPtr != -1, 1003 );
}

Here is the call graph for this function:

void BZ2_bsInitWrite ( EState )

Definition at line 37 of file compress.c.

{
   s->bsLive = 0;
   s->bsBuff = 0;
}
void BZ2_bz__AssertH__fail ( int  errcode)

Definition at line 49 of file bzlib.c.

{
   fprintf(stderr, 
      "\n\nbzip2/libbzip2: internal error number %d.\n"
      "This is a bug in bzip2/libbzip2, %s.\n"
      "Please report it to me at: jseward@bzip.org.  If this happened\n"
      "when you were using some program which uses libbzip2 as a\n"
      "component, you should also report this bug to the author(s)\n"
      "of that program.  Please make an effort to report this bug;\n"
      "timely and accurate bug reports eventually lead to higher\n"
      "quality software.  Thanks.  Julian Seward, 10 December 2007.\n\n",
      errcode,
      BZ2_bzlibVersion()
   );

   if (errcode == 1007) {
   fprintf(stderr,
      "\n*** A special note about internal error number 1007 ***\n"
      "\n"
      "Experience suggests that a common cause of i.e. 1007\n"
      "is unreliable memory or other hardware.  The 1007 assertion\n"
      "just happens to cross-check the results of huge numbers of\n"
      "memory reads/writes, and so acts (unintendedly) as a stress\n"
      "test of your memory system.\n"
      "\n"
      "I suggest the following: try compressing the file again,\n"
      "possibly monitoring progress in detail with the -vv flag.\n"
      "\n"
      "* If the error cannot be reproduced, and/or happens at different\n"
      "  points in compression, you may have a flaky memory system.\n"
      "  Try a memory-test program.  I have used Memtest86\n"
      "  (www.memtest86.com).  At the time of writing it is free (GPLd).\n"
      "  Memtest86 tests memory much more thorougly than your BIOSs\n"
      "  power-on test, and may find failures that the BIOS doesn't.\n"
      "\n"
      "* If the error can be repeatably reproduced, this is a bug in\n"
      "  bzip2, and I would very much like to hear about it.  Please\n"
      "  let me know, and, ideally, save a copy of the file causing the\n"
      "  problem -- without which I will be unable to investigate it.\n"
      "\n"
   );
   }

   exit(3);
}
void BZ2_compressBlock ( EState ,
Bool   
)

Definition at line 602 of file compress.c.

{
   if (s->nblock > 0) {

      BZ_FINALISE_CRC ( s->blockCRC );
      s->combinedCRC = (s->combinedCRC << 1) | (s->combinedCRC >> 31);
      s->combinedCRC ^= s->blockCRC;
      if (s->blockNo > 1) s->numZ = 0;

      if (s->verbosity >= 2)
         VPrintf4( "    block %d: crc = 0x%08x, "
                   "combined CRC = 0x%08x, size = %d\n",
                   s->blockNo, s->blockCRC, s->combinedCRC, s->nblock );

      BZ2_blockSort ( s );
   }

   s->zbits = (UChar*) (&((UChar*)s->arr2)[s->nblock]);

   /*-- If this is the first block, create the stream header. --*/
   if (s->blockNo == 1) {
      BZ2_bsInitWrite ( s );
      bsPutUChar ( s, BZ_HDR_B );
      bsPutUChar ( s, BZ_HDR_Z );
      bsPutUChar ( s, BZ_HDR_h );
      bsPutUChar ( s, (UChar)(BZ_HDR_0 + s->blockSize100k) );
   }

   if (s->nblock > 0) {

      bsPutUChar ( s, 0x31 ); bsPutUChar ( s, 0x41 );
      bsPutUChar ( s, 0x59 ); bsPutUChar ( s, 0x26 );
      bsPutUChar ( s, 0x53 ); bsPutUChar ( s, 0x59 );

      /*-- Now the block's CRC, so it is in a known place. --*/
      bsPutUInt32 ( s, s->blockCRC );

      /*-- 
         Now a single bit indicating (non-)randomisation. 
         As of version 0.9.5, we use a better sorting algorithm
         which makes randomisation unnecessary.  So always set
         the randomised bit to 'no'.  Of course, the decoder
         still needs to be able to handle randomised blocks
         so as to maintain backwards compatibility with
         older versions of bzip2.
      --*/
      bsW(s,1,0);

      bsW ( s, 24, s->origPtr );
      generateMTFValues ( s );
      sendMTFValues ( s );
   }


   /*-- If this is the last block, add the stream trailer. --*/
   if (is_last_block) {

      bsPutUChar ( s, 0x17 ); bsPutUChar ( s, 0x72 );
      bsPutUChar ( s, 0x45 ); bsPutUChar ( s, 0x38 );
      bsPutUChar ( s, 0x50 ); bsPutUChar ( s, 0x90 );
      bsPutUInt32 ( s, s->combinedCRC );
      if (s->verbosity >= 2)
         VPrintf1( "    final combined CRC = 0x%08x\n   ", s->combinedCRC );
      bsFinishWrite ( s );
   }
}

Here is the call graph for this function:

Definition at line 106 of file decompress.c.

{
   UChar      uc;
   Int32      retVal;
   Int32      minLen, maxLen;
   bz_stream* strm = s->strm;

   /* stuff that needs to be saved/restored */
   Int32  i;
   Int32  j;
   Int32  t;
   Int32  alphaSize;
   Int32  nGroups;
   Int32  nSelectors;
   Int32  EOB;
   Int32  groupNo;
   Int32  groupPos;
   Int32  nextSym;
   Int32  nblockMAX;
   Int32  nblock;
   Int32  es;
   Int32  N;
   Int32  curr;
   Int32  zt;
   Int32  zn; 
   Int32  zvec;
   Int32  zj;
   Int32  gSel;
   Int32  gMinlen;
   Int32* gLimit;
   Int32* gBase;
   Int32* gPerm;

   if (s->state == BZ_X_MAGIC_1) {
      /*initialise the save area*/
      s->save_i           = 0;
      s->save_j           = 0;
      s->save_t           = 0;
      s->save_alphaSize   = 0;
      s->save_nGroups     = 0;
      s->save_nSelectors  = 0;
      s->save_EOB         = 0;
      s->save_groupNo     = 0;
      s->save_groupPos    = 0;
      s->save_nextSym     = 0;
      s->save_nblockMAX   = 0;
      s->save_nblock      = 0;
      s->save_es          = 0;
      s->save_N           = 0;
      s->save_curr        = 0;
      s->save_zt          = 0;
      s->save_zn          = 0;
      s->save_zvec        = 0;
      s->save_zj          = 0;
      s->save_gSel        = 0;
      s->save_gMinlen     = 0;
      s->save_gLimit      = NULL;
      s->save_gBase       = NULL;
      s->save_gPerm       = NULL;
   }

   /*restore from the save area*/
   i           = s->save_i;
   j           = s->save_j;
   t           = s->save_t;
   alphaSize   = s->save_alphaSize;
   nGroups     = s->save_nGroups;
   nSelectors  = s->save_nSelectors;
   EOB         = s->save_EOB;
   groupNo     = s->save_groupNo;
   groupPos    = s->save_groupPos;
   nextSym     = s->save_nextSym;
   nblockMAX   = s->save_nblockMAX;
   nblock      = s->save_nblock;
   es          = s->save_es;
   N           = s->save_N;
   curr        = s->save_curr;
   zt          = s->save_zt;
   zn          = s->save_zn; 
   zvec        = s->save_zvec;
   zj          = s->save_zj;
   gSel        = s->save_gSel;
   gMinlen     = s->save_gMinlen;
   gLimit      = s->save_gLimit;
   gBase       = s->save_gBase;
   gPerm       = s->save_gPerm;

   retVal = BZ_OK;

   switch (s->state) {

      GET_UCHAR(BZ_X_MAGIC_1, uc);
      if (uc != BZ_HDR_B) RETURN(BZ_DATA_ERROR_MAGIC);

      GET_UCHAR(BZ_X_MAGIC_2, uc);
      if (uc != BZ_HDR_Z) RETURN(BZ_DATA_ERROR_MAGIC);

      GET_UCHAR(BZ_X_MAGIC_3, uc)
      if (uc != BZ_HDR_h) RETURN(BZ_DATA_ERROR_MAGIC);

      GET_BITS(BZ_X_MAGIC_4, s->blockSize100k, 8)
      if (s->blockSize100k < (BZ_HDR_0 + 1) || 
          s->blockSize100k > (BZ_HDR_0 + 9)) RETURN(BZ_DATA_ERROR_MAGIC);
      s->blockSize100k -= BZ_HDR_0;

      if (s->smallDecompress) {
         s->ll16 = BZALLOC( s->blockSize100k * 100000 * sizeof(UInt16) );
         s->ll4  = BZALLOC( 
                      ((1 + s->blockSize100k * 100000) >> 1) * sizeof(UChar) 
                   );
         if (s->ll16 == NULL || s->ll4 == NULL) RETURN(BZ_MEM_ERROR);
      } else {
         s->tt  = BZALLOC( s->blockSize100k * 100000 * sizeof(Int32) );
         if (s->tt == NULL) RETURN(BZ_MEM_ERROR);
      }

      GET_UCHAR(BZ_X_BLKHDR_1, uc);

      if (uc == 0x17) goto endhdr_2;
      if (uc != 0x31) RETURN(BZ_DATA_ERROR);
      GET_UCHAR(BZ_X_BLKHDR_2, uc);
      if (uc != 0x41) RETURN(BZ_DATA_ERROR);
      GET_UCHAR(BZ_X_BLKHDR_3, uc);
      if (uc != 0x59) RETURN(BZ_DATA_ERROR);
      GET_UCHAR(BZ_X_BLKHDR_4, uc);
      if (uc != 0x26) RETURN(BZ_DATA_ERROR);
      GET_UCHAR(BZ_X_BLKHDR_5, uc);
      if (uc != 0x53) RETURN(BZ_DATA_ERROR);
      GET_UCHAR(BZ_X_BLKHDR_6, uc);
      if (uc != 0x59) RETURN(BZ_DATA_ERROR);

      s->currBlockNo++;
      if (s->verbosity >= 2)
         VPrintf1 ( "\n    [%d: huff+mtf ", s->currBlockNo );
 
      s->storedBlockCRC = 0;
      GET_UCHAR(BZ_X_BCRC_1, uc);
      s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
      GET_UCHAR(BZ_X_BCRC_2, uc);
      s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
      GET_UCHAR(BZ_X_BCRC_3, uc);
      s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
      GET_UCHAR(BZ_X_BCRC_4, uc);
      s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);

      GET_BITS(BZ_X_RANDBIT, s->blockRandomised, 1);

      s->origPtr = 0;
      GET_UCHAR(BZ_X_ORIGPTR_1, uc);
      s->origPtr = (s->origPtr << 8) | ((Int32)uc);
      GET_UCHAR(BZ_X_ORIGPTR_2, uc);
      s->origPtr = (s->origPtr << 8) | ((Int32)uc);
      GET_UCHAR(BZ_X_ORIGPTR_3, uc);
      s->origPtr = (s->origPtr << 8) | ((Int32)uc);

      if (s->origPtr < 0)
         RETURN(BZ_DATA_ERROR);
      if (s->origPtr > 10 + 100000*s->blockSize100k) 
         RETURN(BZ_DATA_ERROR);

      /*--- Receive the mapping table ---*/
      for (i = 0; i < 16; i++) {
         GET_BIT(BZ_X_MAPPING_1, uc);
         if (uc == 1) 
            s->inUse16[i] = True; else 
            s->inUse16[i] = False;
      }

      for (i = 0; i < 256; i++) s->inUse[i] = False;

      for (i = 0; i < 16; i++)
         if (s->inUse16[i])
            for (j = 0; j < 16; j++) {
               GET_BIT(BZ_X_MAPPING_2, uc);
               if (uc == 1) s->inUse[i * 16 + j] = True;
            }
      makeMaps_d ( s );
      if (s->nInUse == 0) RETURN(BZ_DATA_ERROR);
      alphaSize = s->nInUse+2;

      /*--- Now the selectors ---*/
      GET_BITS(BZ_X_SELECTOR_1, nGroups, 3);
      if (nGroups < 2 || nGroups > 6) RETURN(BZ_DATA_ERROR);
      GET_BITS(BZ_X_SELECTOR_2, nSelectors, 15);
      if (nSelectors < 1) RETURN(BZ_DATA_ERROR);
      for (i = 0; i < nSelectors; i++) {
         j = 0;
         while (True) {
            GET_BIT(BZ_X_SELECTOR_3, uc);
            if (uc == 0) break;
            j++;
            if (j >= nGroups) RETURN(BZ_DATA_ERROR);
         }
         s->selectorMtf[i] = j;
      }

      /*--- Undo the MTF values for the selectors. ---*/
      {
         UChar pos[BZ_N_GROUPS], tmp, v;
         for (v = 0; v < nGroups; v++) pos[v] = v;
   
         for (i = 0; i < nSelectors; i++) {
            v = s->selectorMtf[i];
            tmp = pos[v];
            while (v > 0) { pos[v] = pos[v-1]; v--; }
            pos[0] = tmp;
            s->selector[i] = tmp;
         }
      }

      /*--- Now the coding tables ---*/
      for (t = 0; t < nGroups; t++) {
         GET_BITS(BZ_X_CODING_1, curr, 5);
         for (i = 0; i < alphaSize; i++) {
            while (True) {
               if (curr < 1 || curr > 20) RETURN(BZ_DATA_ERROR);
               GET_BIT(BZ_X_CODING_2, uc);
               if (uc == 0) break;
               GET_BIT(BZ_X_CODING_3, uc);
               if (uc == 0) curr++; else curr--;
            }
            s->len[t][i] = curr;
         }
      }

      /*--- Create the Huffman decoding tables ---*/
      for (t = 0; t < nGroups; t++) {
         minLen = 32;
         maxLen = 0;
         for (i = 0; i < alphaSize; i++) {
            if (s->len[t][i] > maxLen) maxLen = s->len[t][i];
            if (s->len[t][i] < minLen) minLen = s->len[t][i];
         }
         BZ2_hbCreateDecodeTables ( 
            &(s->limit[t][0]), 
            &(s->base[t][0]), 
            &(s->perm[t][0]), 
            &(s->len[t][0]),
            minLen, maxLen, alphaSize
         );
         s->minLens[t] = minLen;
      }

      /*--- Now the MTF values ---*/

      EOB      = s->nInUse+1;
      nblockMAX = 100000 * s->blockSize100k;
      groupNo  = -1;
      groupPos = 0;

      for (i = 0; i <= 255; i++) s->unzftab[i] = 0;

      /*-- MTF init --*/
      {
         Int32 ii, jj, kk;
         kk = MTFA_SIZE-1;
         for (ii = 256 / MTFL_SIZE - 1; ii >= 0; ii--) {
            for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
               s->mtfa[kk] = (UChar)(ii * MTFL_SIZE + jj);
               kk--;
            }
            s->mtfbase[ii] = kk + 1;
         }
      }
      /*-- end MTF init --*/

      nblock = 0;
      GET_MTF_VAL(BZ_X_MTF_1, BZ_X_MTF_2, nextSym);

      while (True) {

         if (nextSym == EOB) break;

         if (nextSym == BZ_RUNA || nextSym == BZ_RUNB) {

            es = -1;
            N = 1;
            do {
               /* Check that N doesn't get too big, so that es doesn't
                  go negative.  The maximum value that can be
                  RUNA/RUNB encoded is equal to the block size (post
                  the initial RLE), viz, 900k, so bounding N at 2
                  million should guard against overflow without
                  rejecting any legitimate inputs. */
               if (N >= 2*1024*1024) RETURN(BZ_DATA_ERROR);
               if (nextSym == BZ_RUNA) es = es + (0+1) * N; else
               if (nextSym == BZ_RUNB) es = es + (1+1) * N;
               N = N * 2;
               GET_MTF_VAL(BZ_X_MTF_3, BZ_X_MTF_4, nextSym);
            }
               while (nextSym == BZ_RUNA || nextSym == BZ_RUNB);

            es++;
            uc = s->seqToUnseq[ s->mtfa[s->mtfbase[0]] ];
            s->unzftab[uc] += es;

            if (s->smallDecompress)
               while (es > 0) {
                  if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
                  s->ll16[nblock] = (UInt16)uc;
                  nblock++;
                  es--;
               }
            else
               while (es > 0) {
                  if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
                  s->tt[nblock] = (UInt32)uc;
                  nblock++;
                  es--;
               };

            continue;

         } else {

            if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);

            /*-- uc = MTF ( nextSym-1 ) --*/
            {
               Int32 ii, jj, kk, pp, lno, off;
               UInt32 nn;
               nn = (UInt32)(nextSym - 1);

               if (nn < MTFL_SIZE) {
                  /* avoid general-case expense */
                  pp = s->mtfbase[0];
                  uc = s->mtfa[pp+nn];
                  while (nn > 3) {
                     Int32 z = pp+nn;
                     s->mtfa[(z)  ] = s->mtfa[(z)-1];
                     s->mtfa[(z)-1] = s->mtfa[(z)-2];
                     s->mtfa[(z)-2] = s->mtfa[(z)-3];
                     s->mtfa[(z)-3] = s->mtfa[(z)-4];
                     nn -= 4;
                  }
                  while (nn > 0) { 
                     s->mtfa[(pp+nn)] = s->mtfa[(pp+nn)-1]; nn--; 
                  };
                  s->mtfa[pp] = uc;
               } else { 
                  /* general case */
                  lno = nn / MTFL_SIZE;
                  off = nn % MTFL_SIZE;
                  pp = s->mtfbase[lno] + off;
                  uc = s->mtfa[pp];
                  while (pp > s->mtfbase[lno]) { 
                     s->mtfa[pp] = s->mtfa[pp-1]; pp--; 
                  };
                  s->mtfbase[lno]++;
                  while (lno > 0) {
                     s->mtfbase[lno]--;
                     s->mtfa[s->mtfbase[lno]] 
                        = s->mtfa[s->mtfbase[lno-1] + MTFL_SIZE - 1];
                     lno--;
                  }
                  s->mtfbase[0]--;
                  s->mtfa[s->mtfbase[0]] = uc;
                  if (s->mtfbase[0] == 0) {
                     kk = MTFA_SIZE-1;
                     for (ii = 256 / MTFL_SIZE-1; ii >= 0; ii--) {
                        for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
                           s->mtfa[kk] = s->mtfa[s->mtfbase[ii] + jj];
                           kk--;
                        }
                        s->mtfbase[ii] = kk + 1;
                     }
                  }
               }
            }
            /*-- end uc = MTF ( nextSym-1 ) --*/

            s->unzftab[s->seqToUnseq[uc]]++;
            if (s->smallDecompress)
               s->ll16[nblock] = (UInt16)(s->seqToUnseq[uc]); else
               s->tt[nblock]   = (UInt32)(s->seqToUnseq[uc]);
            nblock++;

            GET_MTF_VAL(BZ_X_MTF_5, BZ_X_MTF_6, nextSym);
            continue;
         }
      }

      /* Now we know what nblock is, we can do a better sanity
         check on s->origPtr.
      */
      if (s->origPtr < 0 || s->origPtr >= nblock)
         RETURN(BZ_DATA_ERROR);

      /*-- Set up cftab to facilitate generation of T^(-1) --*/
      /* Check: unzftab entries in range. */
      for (i = 0; i <= 255; i++) {
         if (s->unzftab[i] < 0 || s->unzftab[i] > nblock)
            RETURN(BZ_DATA_ERROR);
      }
      /* Actually generate cftab. */
      s->cftab[0] = 0;
      for (i = 1; i <= 256; i++) s->cftab[i] = s->unzftab[i-1];
      for (i = 1; i <= 256; i++) s->cftab[i] += s->cftab[i-1];
      /* Check: cftab entries in range. */
      for (i = 0; i <= 256; i++) {
         if (s->cftab[i] < 0 || s->cftab[i] > nblock) {
            /* s->cftab[i] can legitimately be == nblock */
            RETURN(BZ_DATA_ERROR);
         }
      }
      /* Check: cftab entries non-descending. */
      for (i = 1; i <= 256; i++) {
         if (s->cftab[i-1] > s->cftab[i]) {
            RETURN(BZ_DATA_ERROR);
         }
      }

      s->state_out_len = 0;
      s->state_out_ch  = 0;
      BZ_INITIALISE_CRC ( s->calculatedBlockCRC );
      s->state = BZ_X_OUTPUT;
      if (s->verbosity >= 2) VPrintf0 ( "rt+rld" );

      if (s->smallDecompress) {

         /*-- Make a copy of cftab, used in generation of T --*/
         for (i = 0; i <= 256; i++) s->cftabCopy[i] = s->cftab[i];

         /*-- compute the T vector --*/
         for (i = 0; i < nblock; i++) {
            uc = (UChar)(s->ll16[i]);
            SET_LL(i, s->cftabCopy[uc]);
            s->cftabCopy[uc]++;
         }

         /*-- Compute T^(-1) by pointer reversal on T --*/
         i = s->origPtr;
         j = GET_LL(i);
         do {
            Int32 tmp = GET_LL(j);
            SET_LL(j, i);
            i = j;
            j = tmp;
         }
            while (i != s->origPtr);

         s->tPos = s->origPtr;
         s->nblock_used = 0;
         if (s->blockRandomised) {
            BZ_RAND_INIT_MASK;
            BZ_GET_SMALL(s->k0); s->nblock_used++;
            BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK; 
         } else {
            BZ_GET_SMALL(s->k0); s->nblock_used++;
         }

      } else {

         /*-- compute the T^(-1) vector --*/
         for (i = 0; i < nblock; i++) {
            uc = (UChar)(s->tt[i] & 0xff);
            s->tt[s->cftab[uc]] |= (i << 8);
            s->cftab[uc]++;
         }

         s->tPos = s->tt[s->origPtr] >> 8;
         s->nblock_used = 0;
         if (s->blockRandomised) {
            BZ_RAND_INIT_MASK;
            BZ_GET_FAST(s->k0); s->nblock_used++;
            BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK; 
         } else {
            BZ_GET_FAST(s->k0); s->nblock_used++;
         }

      }

      RETURN(BZ_OK);



    endhdr_2:

      GET_UCHAR(BZ_X_ENDHDR_2, uc);
      if (uc != 0x72) RETURN(BZ_DATA_ERROR);
      GET_UCHAR(BZ_X_ENDHDR_3, uc);
      if (uc != 0x45) RETURN(BZ_DATA_ERROR);
      GET_UCHAR(BZ_X_ENDHDR_4, uc);
      if (uc != 0x38) RETURN(BZ_DATA_ERROR);
      GET_UCHAR(BZ_X_ENDHDR_5, uc);
      if (uc != 0x50) RETURN(BZ_DATA_ERROR);
      GET_UCHAR(BZ_X_ENDHDR_6, uc);
      if (uc != 0x90) RETURN(BZ_DATA_ERROR);

      s->storedCombinedCRC = 0;
      GET_UCHAR(BZ_X_CCRC_1, uc);
      s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
      GET_UCHAR(BZ_X_CCRC_2, uc);
      s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
      GET_UCHAR(BZ_X_CCRC_3, uc);
      s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
      GET_UCHAR(BZ_X_CCRC_4, uc);
      s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);

      s->state = BZ_X_IDLE;
      RETURN(BZ_STREAM_END);

      default: AssertH ( False, 4001 );
   }

   AssertH ( False, 4002 );

   save_state_and_return:

   s->save_i           = i;
   s->save_j           = j;
   s->save_t           = t;
   s->save_alphaSize   = alphaSize;
   s->save_nGroups     = nGroups;
   s->save_nSelectors  = nSelectors;
   s->save_EOB         = EOB;
   s->save_groupNo     = groupNo;
   s->save_groupPos    = groupPos;
   s->save_nextSym     = nextSym;
   s->save_nblockMAX   = nblockMAX;
   s->save_nblock      = nblock;
   s->save_es          = es;
   s->save_N           = N;
   s->save_curr        = curr;
   s->save_zt          = zt;
   s->save_zn          = zn;
   s->save_zvec        = zvec;
   s->save_zj          = zj;
   s->save_gSel        = gSel;
   s->save_gMinlen     = gMinlen;
   s->save_gLimit      = gLimit;
   s->save_gBase       = gBase;
   s->save_gPerm       = gPerm;

   return retVal;   
}

Here is the call graph for this function:

void BZ2_hbAssignCodes ( Int32 ,
UChar ,
Int32  ,
Int32  ,
Int32   
)

Definition at line 152 of file huffman.c.

{
   Int32 n, vec, i;

   vec = 0;
   for (n = minLen; n <= maxLen; n++) {
      for (i = 0; i < alphaSize; i++)
         if (length[i] == n) { code[i] = vec; vec++; };
      vec <<= 1;
   }
}
void BZ2_hbCreateDecodeTables ( Int32 ,
Int32 ,
Int32 ,
UChar ,
Int32  ,
Int32  ,
Int32   
)

Definition at line 170 of file huffman.c.

{
   Int32 pp, i, j, vec;

   pp = 0;
   for (i = minLen; i <= maxLen; i++)
      for (j = 0; j < alphaSize; j++)
         if (length[j] == i) { perm[pp] = j; pp++; };

   for (i = 0; i < BZ_MAX_CODE_LEN; i++) base[i] = 0;
   for (i = 0; i < alphaSize; i++) base[length[i]+1]++;

   for (i = 1; i < BZ_MAX_CODE_LEN; i++) base[i] += base[i-1];

   for (i = 0; i < BZ_MAX_CODE_LEN; i++) limit[i] = 0;
   vec = 0;

   for (i = minLen; i <= maxLen; i++) {
      vec += (base[i+1] - base[i]);
      limit[i] = vec-1;
      vec <<= 1;
   }
   for (i = minLen + 1; i <= maxLen; i++)
      base[i] = ((limit[i-1] + 1) << 1) - base[i];
}
void BZ2_hbMakeCodeLengths ( UChar ,
Int32 ,
Int32  ,
Int32   
)

Definition at line 63 of file huffman.c.

{
   /*--
      Nodes and heap entries run from 1.  Entry 0
      for both the heap and nodes is a sentinel.
   --*/
   Int32 nNodes, nHeap, n1, n2, i, j, k;
   Bool  tooLong;

   Int32 heap   [ BZ_MAX_ALPHA_SIZE + 2 ];
   Int32 weight [ BZ_MAX_ALPHA_SIZE * 2 ];
   Int32 parent [ BZ_MAX_ALPHA_SIZE * 2 ]; 

   for (i = 0; i < alphaSize; i++)
      weight[i+1] = (freq[i] == 0 ? 1 : freq[i]) << 8;

   while (True) {

      nNodes = alphaSize;
      nHeap = 0;

      heap[0] = 0;
      weight[0] = 0;
      parent[0] = -2;

      for (i = 1; i <= alphaSize; i++) {
         parent[i] = -1;
         nHeap++;
         heap[nHeap] = i;
         UPHEAP(nHeap);
      }

      AssertH( nHeap < (BZ_MAX_ALPHA_SIZE+2), 2001 );
   
      while (nHeap > 1) {
         n1 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
         n2 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
         nNodes++;
         parent[n1] = parent[n2] = nNodes;
         weight[nNodes] = ADDWEIGHTS(weight[n1], weight[n2]);
         parent[nNodes] = -1;
         nHeap++;
         heap[nHeap] = nNodes;
         UPHEAP(nHeap);
      }

      AssertH( nNodes < (BZ_MAX_ALPHA_SIZE * 2), 2002 );

      tooLong = False;
      for (i = 1; i <= alphaSize; i++) {
         j = 0;
         k = i;
         while (parent[k] >= 0) { k = parent[k]; j++; }
         len[i-1] = j;
         if (j > maxLen) tooLong = True;
      }
      
      if (! tooLong) break;

      /* 17 Oct 04: keep-going condition for the following loop used
         to be 'i < alphaSize', which missed the last element,
         theoretically leading to the possibility of the compressor
         looping.  However, this count-scaling step is only needed if
         one of the generated Huffman code words is longer than
         maxLen, which up to and including version 1.0.2 was 20 bits,
         which is extremely unlikely.  In version 1.0.3 maxLen was
         changed to 17 bits, which has minimal effect on compression
         ratio, but does mean this scaling step is used from time to
         time, enough to verify that it works.

         This means that bzip2-1.0.3 and later will only produce
         Huffman codes with a maximum length of 17 bits.  However, in
         order to preserve backwards compatibility with bitstreams
         produced by versions pre-1.0.3, the decompressor must still
         handle lengths of up to 20. */

      for (i = 1; i <= alphaSize; i++) {
         j = weight[i] >> 8;
         j = 1 + (j / 2);
         weight[i] = j << 8;
      }
   }
}
Int32 BZ2_indexIntoF ( Int32  ,
Int32  
)

Definition at line 729 of file bzlib.c.

{
   Int32 nb, na, mid;
   nb = 0;
   na = 256;
   do {
      mid = (nb + na) >> 1;
      if (indx >= cftab[mid]) nb = mid; else na = mid;
   }
   while (na - nb != 1);
   return nb;
}

Variable Documentation

Definition at line 31 of file crctable.c.

Definition at line 26 of file randtable.c.