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.6 of 6 September 2010
  12    Copyright (C) 1996-2010 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                                 Int16 *hufcode,
 174                                 UChar *length,
 175                                 Int32 minLen,
 176                                 Int32 maxLen,
 177                                 Int32 alphaSize )
 178 {
 179    Int32 pp, i, j, vec, k, vec2;
 180
 181    for (i = 0; i < (1 << HUFCODE_SIZE); i++)
 182       hufcode[i] = 0;
 183    pp = 0;
 184    for (i = minLen; i <= maxLen; i++)
 185       for (j = 0; j < alphaSize; j++)
 186          if (length[j] == i) { perm[pp] = j; pp++; };
 187
 188    for (i = 0; i < BZ_MAX_CODE_LEN; i++) base[i] = 0;
 189    for (i = 0; i < alphaSize; i++) base[length[i]+1]++;
 190
 191    for (i = 1; i < BZ_MAX_CODE_LEN; i++) base[i] += base[i-1];
 192
 193    for (i = 0; i < BZ_MAX_CODE_LEN; i++) limit[i] = -1;
 194    vec = 0;
 195
 196    for (i = minLen; i <= maxLen; i++) {
 197       if (i <= HUFCODE_SIZE) {
 198          for (j = base[i]; j < base[i + 1]; j++) {
 199             vec2 = (vec + j - base[i]) << (HUFCODE_SIZE - i);
 200             k = (1 << (HUFCODE_SIZE - i));
 201             if (vec2 + k > (1 << HUFCODE_SIZE))
 202                 k = (1 << HUFCODE_SIZE) - vec2;
 203             for (; --k >= 0; vec2++)
 204                hufcode[vec2] = perm[j] | 512 | (HUFCODE_SIZE - i) << 10;
 205          }
 206       }
 207       vec += (base[i+1] - base[i]);
 208       limit[i] = vec-1;
 209       vec <<= 1;
 210    }
 211    for (i = minLen + 1; i <= maxLen; i++)
 212       base[i] = ((limit[i-1] + 1) << 1) - base[i];
 213    limit[maxLen + 1] = 0x7fffffff;      /* make it terminate */
 214    base[maxLen + 1] = 0;
 215 }
 216
 217
 218 /*-------------------------------------------------------------*/
 219 /*--- end                                         huffman.c ---*/
 220 /*-------------------------------------------------------------*/