huffman.c

   1
   2 /*-------------------------------------------------------------*/
   3 /*--- Huffman coding low-level stuff                        ---*/
   4 /*---                                             huffman.c ---*/
   5 /*-------------------------------------------------------------*/
   6
   7 /* ------------------------------------------------------------------
   8    This file is part of bzip2/libbzip2, a program and library for
   9    lossless, block-sorting data compression.
  10
  11    bzip2/libbzip2 version 1.0.5 of 10 December 2007
  12    Copyright (C) 1996-2007 Julian Seward <jseward@bzip.org>
  13
  14    Please read the WARNING, DISCLAIMER and PATENTS sections in the
  15    README file.
  16
  17    This program is released under the terms of the license contained
  18    in the file LICENSE.
  19    ------------------------------------------------------------------ */
  20
  21
  22 #include "bzlib_private.h"
  23
  24 /*---------------------------------------------------*/
  25 #define WEIGHTOF(zz0)  ((zz0) & 0xffffff00)
  26 #define DEPTHOF(zz1)   ((zz1) & 0x000000ff)
  27 #define MYMAX(zz2,zz3) ((zz2) > (zz3) ? (zz2) : (zz3))
  28
  29 #define ADDWEIGHTS(zw1,zw2)                           \
  30    (WEIGHTOF(zw1)+WEIGHTOF(zw2)) |                    \
  31    (1 + MYMAX(DEPTHOF(zw1),DEPTHOF(zw2)))
  32
  33 #define UPHEAP(z)                                     \
  34 {                                                     \
  35    Int32 zz, tmp;                                     \
  36    zz = z; tmp = heap[zz];                            \
  37    while (weight[tmp] < weight[heap[zz >> 1]]) {      \
  38       heap[zz] = heap[zz >> 1];                       \
  39       zz >>= 1;                                       \
  40    }                                                  \
  41    heap[zz] = tmp;                                    \
  42 }
  43
  44 #define DOWNHEAP(z)                                   \
  45 {                                                     \
  46    Int32 zz, yy, tmp;                                 \
  47    zz = z; tmp = heap[zz];                            \
  48    while (True) {                                     \
  49       yy = zz << 1;                                   \
  50       if (yy > nHeap) break;                          \
  51       if (yy < nHeap &&                               \
  52           weight[heap[yy+1]] < weight[heap[yy]])      \
  53          yy++;                                        \
  54       if (weight[tmp] < weight[heap[yy]]) break;      \
  55       heap[zz] = heap[yy];                            \
  56       zz = yy;                                        \
  57    }                                                  \
  58    heap[zz] = tmp;                                    \
  59 }
  60
  61
  62 /*---------------------------------------------------*/
  63 void BZ2_hbMakeCodeLengths ( UChar *len,
  64                              Int32 *freq,
  65                              Int32 alphaSize,
  66                              Int32 maxLen )
  67 {
  68    /*--
  69       Nodes and heap entries run from 1.  Entry 0
  70       for both the heap and nodes is a sentinel.
  71    --*/
  72    Int32 nNodes, nHeap, n1, n2, i, j, k;
  73    Bool  tooLong;
  74
  75    Int32 heap   [ BZ_MAX_ALPHA_SIZE + 2 ];
  76    Int32 weight [ BZ_MAX_ALPHA_SIZE * 2 ];
  77    Int32 parent [ BZ_MAX_ALPHA_SIZE * 2 ];
  78
  79    for (i = 0; i < alphaSize; i++)
  80       weight[i+1] = (freq[i] == 0 ? 1 : freq[i]) << 8;
  81
  82    while (True) {
  83
  84       nNodes = alphaSize;
  85       nHeap = 0;
  86
  87       heap[0] = 0;
  88       weight[0] = 0;
  89       parent[0] = -2;
  90
  91       for (i = 1; i <= alphaSize; i++) {
  92          parent[i] = -1;
  93          nHeap++;
  94          heap[nHeap] = i;
  95          UPHEAP(nHeap);
  96       }
  97
  98       AssertH( nHeap < (BZ_MAX_ALPHA_SIZE+2), 2001 );
  99
 100       while (nHeap > 1) {
 101          n1 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
 102          n2 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
 103          nNodes++;
 104          parent[n1] = parent[n2] = nNodes;
 105          weight[nNodes] = ADDWEIGHTS(weight[n1], weight[n2]);
 106          parent[nNodes] = -1;
 107          nHeap++;
 108          heap[nHeap] = nNodes;
 109          UPHEAP(nHeap);
 110       }
 111
 112       AssertH( nNodes < (BZ_MAX_ALPHA_SIZE * 2), 2002 );
 113
 114       tooLong = False;
 115       for (i = 1; i <= alphaSize; i++) {
 116          j = 0;
 117          k = i;
 118          while (parent[k] >= 0) { k = parent[k]; j++; }
 119          len[i-1] = j;
 120          if (j > maxLen) tooLong = True;
 121       }
 122
 123       if (! tooLong) break;
 124
 125       /* 17 Oct 04: keep-going condition for the following loop used
 126          to be 'i < alphaSize', which missed the last element,
 127          theoretically leading to the possibility of the compressor
 128          looping.  However, this count-scaling step is only needed if
 129          one of the generated Huffman code words is longer than
 130          maxLen, which up to and including version 1.0.2 was 20 bits,
 131          which is extremely unlikely.  In version 1.0.3 maxLen was
 132          changed to 17 bits, which has minimal effect on compression
 133          ratio, but does mean this scaling step is used from time to
 134          time, enough to verify that it works.
 135
 136          This means that bzip2-1.0.3 and later will only produce
 137          Huffman codes with a maximum length of 17 bits.  However, in
 138          order to preserve backwards compatibility with bitstreams
 139          produced by versions pre-1.0.3, the decompressor must still
 140          handle lengths of up to 20. */
 141
 142       for (i = 1; i <= alphaSize; i++) {
 143          j = weight[i] >> 8;
 144          j = 1 + (j / 2);
 145          weight[i] = j << 8;
 146       }
 147    }
 148 }
 149
 150
 151 /*---------------------------------------------------*/
 152 void BZ2_hbAssignCodes ( Int32 *code,
 153                          UChar *length,
 154                          Int32 minLen,
 155                          Int32 maxLen,
 156                          Int32 alphaSize )
 157 {
 158    Int32 n, vec, i;
 159
 160    vec = 0;
 161    for (n = minLen; n <= maxLen; n++) {
 162       for (i = 0; i < alphaSize; i++)
 163          if (length[i] == n) { code[i] = vec; vec++; };
 164       vec <<= 1;
 165    }
 166 }
 167
 168
 169 /*---------------------------------------------------*/
 170 void BZ2_hbCreateDecodeTables ( Int32 *limit,
 171                                 Int32 *base,
 172                                 Int32 *perm,
 173                                 UChar *length,
 174                                 Int32 minLen,
 175                                 Int32 maxLen,
 176                                 Int32 alphaSize )
 177 {
 178    Int32 pp, i, j, vec;
 179
 180    pp = 0;
 181    for (i = minLen; i <= maxLen; i++)
 182       for (j = 0; j < alphaSize; j++)
 183          if (length[j] == i) { perm[pp] = j; pp++; };
 184
 185    for (i = 0; i < BZ_MAX_CODE_LEN; i++) base[i] = 0;
 186    for (i = 0; i < alphaSize; i++) base[length[i]+1]++;
 187
 188    for (i = 1; i < BZ_MAX_CODE_LEN; i++) base[i] += base[i-1];
 189
 190    for (i = 0; i < BZ_MAX_CODE_LEN; i++) limit[i] = 0;
 191    vec = 0;
 192
 193    for (i = minLen; i <= maxLen; i++) {
 194       vec += (base[i+1] - base[i]);
 195       limit[i] = vec-1;
 196       vec <<= 1;
 197    }
 198    for (i = minLen + 1; i <= maxLen; i++)
 199       base[i] = ((limit[i-1] + 1) << 1) - base[i];
 200 }
 201
 202
 203 /*-------------------------------------------------------------*/
 204 /*--- end                                         huffman.c ---*/
 205 /*-------------------------------------------------------------*/