Back to index

avfs  1.0.1
huffman.c
Go to the documentation of this file.
00001 
00002 /*-------------------------------------------------------------*/
00003 /*--- Huffman coding low-level stuff                        ---*/
00004 /*---                                             huffman.c ---*/
00005 /*-------------------------------------------------------------*/
00006 
00007 /* ------------------------------------------------------------------
00008    This file is part of bzip2/libbzip2, a program and library for
00009    lossless, block-sorting data compression.
00010 
00011    bzip2/libbzip2 version 1.0.6 of 6 September 2010
00012    Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org>
00013 
00014    Please read the WARNING, DISCLAIMER and PATENTS sections in the 
00015    README file.
00016 
00017    This program is released under the terms of the license contained
00018    in the file LICENSE.
00019    ------------------------------------------------------------------ */
00020 
00021 
00022 #include "bzlib_private.h"
00023 
00024 /*---------------------------------------------------*/
00025 #define WEIGHTOF(zz0)  ((zz0) & 0xffffff00)
00026 #define DEPTHOF(zz1)   ((zz1) & 0x000000ff)
00027 #define MYMAX(zz2,zz3) ((zz2) > (zz3) ? (zz2) : (zz3))
00028 
00029 #define ADDWEIGHTS(zw1,zw2)                           \
00030    (WEIGHTOF(zw1)+WEIGHTOF(zw2)) |                    \
00031    (1 + MYMAX(DEPTHOF(zw1),DEPTHOF(zw2)))
00032 
00033 #define UPHEAP(z)                                     \
00034 {                                                     \
00035    Int32 zz, tmp;                                     \
00036    zz = z; tmp = heap[zz];                            \
00037    while (weight[tmp] < weight[heap[zz >> 1]]) {      \
00038       heap[zz] = heap[zz >> 1];                       \
00039       zz >>= 1;                                       \
00040    }                                                  \
00041    heap[zz] = tmp;                                    \
00042 }
00043 
00044 #define DOWNHEAP(z)                                   \
00045 {                                                     \
00046    Int32 zz, yy, tmp;                                 \
00047    zz = z; tmp = heap[zz];                            \
00048    while (True) {                                     \
00049       yy = zz << 1;                                   \
00050       if (yy > nHeap) break;                          \
00051       if (yy < nHeap &&                               \
00052           weight[heap[yy+1]] < weight[heap[yy]])      \
00053          yy++;                                        \
00054       if (weight[tmp] < weight[heap[yy]]) break;      \
00055       heap[zz] = heap[yy];                            \
00056       zz = yy;                                        \
00057    }                                                  \
00058    heap[zz] = tmp;                                    \
00059 }
00060 
00061 
00062 /*---------------------------------------------------*/
00063 void BZ2_hbMakeCodeLengths ( UChar *len, 
00064                              Int32 *freq,
00065                              Int32 alphaSize,
00066                              Int32 maxLen )
00067 {
00068    /*--
00069       Nodes and heap entries run from 1.  Entry 0
00070       for both the heap and nodes is a sentinel.
00071    --*/
00072    Int32 nNodes, nHeap, n1, n2, i, j, k;
00073    Bool  tooLong;
00074 
00075    Int32 heap   [ BZ_MAX_ALPHA_SIZE + 2 ];
00076    Int32 weight [ BZ_MAX_ALPHA_SIZE * 2 ];
00077    Int32 parent [ BZ_MAX_ALPHA_SIZE * 2 ]; 
00078 
00079    for (i = 0; i < alphaSize; i++)
00080       weight[i+1] = (freq[i] == 0 ? 1 : freq[i]) << 8;
00081 
00082    while (True) {
00083 
00084       nNodes = alphaSize;
00085       nHeap = 0;
00086 
00087       heap[0] = 0;
00088       weight[0] = 0;
00089       parent[0] = -2;
00090 
00091       for (i = 1; i <= alphaSize; i++) {
00092          parent[i] = -1;
00093          nHeap++;
00094          heap[nHeap] = i;
00095          UPHEAP(nHeap);
00096       }
00097 
00098       AssertH( nHeap < (BZ_MAX_ALPHA_SIZE+2), 2001 );
00099    
00100       while (nHeap > 1) {
00101          n1 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
00102          n2 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
00103          nNodes++;
00104          parent[n1] = parent[n2] = nNodes;
00105          weight[nNodes] = ADDWEIGHTS(weight[n1], weight[n2]);
00106          parent[nNodes] = -1;
00107          nHeap++;
00108          heap[nHeap] = nNodes;
00109          UPHEAP(nHeap);
00110       }
00111 
00112       AssertH( nNodes < (BZ_MAX_ALPHA_SIZE * 2), 2002 );
00113 
00114       tooLong = False;
00115       for (i = 1; i <= alphaSize; i++) {
00116          j = 0;
00117          k = i;
00118          while (parent[k] >= 0) { k = parent[k]; j++; }
00119          len[i-1] = j;
00120          if (j > maxLen) tooLong = True;
00121       }
00122       
00123       if (! tooLong) break;
00124 
00125       /* 17 Oct 04: keep-going condition for the following loop used
00126          to be 'i < alphaSize', which missed the last element,
00127          theoretically leading to the possibility of the compressor
00128          looping.  However, this count-scaling step is only needed if
00129          one of the generated Huffman code words is longer than
00130          maxLen, which up to and including version 1.0.2 was 20 bits,
00131          which is extremely unlikely.  In version 1.0.3 maxLen was
00132          changed to 17 bits, which has minimal effect on compression
00133          ratio, but does mean this scaling step is used from time to
00134          time, enough to verify that it works.
00135 
00136          This means that bzip2-1.0.3 and later will only produce
00137          Huffman codes with a maximum length of 17 bits.  However, in
00138          order to preserve backwards compatibility with bitstreams
00139          produced by versions pre-1.0.3, the decompressor must still
00140          handle lengths of up to 20. */
00141 
00142       for (i = 1; i <= alphaSize; i++) {
00143          j = weight[i] >> 8;
00144          j = 1 + (j / 2);
00145          weight[i] = j << 8;
00146       }
00147    }
00148 }
00149 
00150 
00151 /*---------------------------------------------------*/
00152 void BZ2_hbAssignCodes ( Int32 *code,
00153                          UChar *length,
00154                          Int32 minLen,
00155                          Int32 maxLen,
00156                          Int32 alphaSize )
00157 {
00158    Int32 n, vec, i;
00159 
00160    vec = 0;
00161    for (n = minLen; n <= maxLen; n++) {
00162       for (i = 0; i < alphaSize; i++)
00163          if (length[i] == n) { code[i] = vec; vec++; };
00164       vec <<= 1;
00165    }
00166 }
00167 
00168 
00169 /*---------------------------------------------------*/
00170 void BZ2_hbCreateDecodeTables ( Int32 *limit,
00171                                 Int32 *base,
00172                                 Int32 *perm,
00173                                 UChar *length,
00174                                 Int32 minLen,
00175                                 Int32 maxLen,
00176                                 Int32 alphaSize )
00177 {
00178    Int32 pp, i, j, vec;
00179 
00180    pp = 0;
00181    for (i = minLen; i <= maxLen; i++)
00182       for (j = 0; j < alphaSize; j++)
00183          if (length[j] == i) { perm[pp] = j; pp++; };
00184 
00185    for (i = 0; i < BZ_MAX_CODE_LEN; i++) base[i] = 0;
00186    for (i = 0; i < alphaSize; i++) base[length[i]+1]++;
00187 
00188    for (i = 1; i < BZ_MAX_CODE_LEN; i++) base[i] += base[i-1];
00189 
00190    for (i = 0; i < BZ_MAX_CODE_LEN; i++) limit[i] = 0;
00191    vec = 0;
00192 
00193    for (i = minLen; i <= maxLen; i++) {
00194       vec += (base[i+1] - base[i]);
00195       limit[i] = vec-1;
00196       vec <<= 1;
00197    }
00198    for (i = minLen + 1; i <= maxLen; i++)
00199       base[i] = ((limit[i-1] + 1) << 1) - base[i];
00200 }
00201 
00202 
00203 /*-------------------------------------------------------------*/
00204 /*--- end                                         huffman.c ---*/
00205 /*-------------------------------------------------------------*/