#include "bzlib_private.h"
Go to the source code of this file.
Defines | |
#define | WEIGHTOF(zz0) ((zz0) & 0xffffff00) |
#define | DEPTHOF(zz1) ((zz1) & 0x000000ff) |
#define | MYMAX(zz2, zz3) ((zz2) > (zz3) ? (zz2) : (zz3)) |
#define | ADDWEIGHTS(zw1, zw2) |
#define | UPHEAP(z) |
#define | DOWNHEAP(z) |
Functions | |
void | hbMakeCodeLengths (UChar *len, Int32 *freq, Int32 alphaSize, Int32 maxLen) |
void | hbAssignCodes (Int32 *code, UChar *length, Int32 minLen, Int32 maxLen, Int32 alphaSize) |
void | hbCreateDecodeTables (Int32 *limit, Int32 *base, Int32 *perm, UChar *length, Int32 minLen, Int32 maxLen, Int32 alphaSize) |
|
Value: Definition at line 69 of file huffman.c. Referenced by hbMakeCodeLengths().
|
|
|
|
Value: { \ Int32 zz, yy, tmp; \ zz = z; tmp = heap[zz]; \ while (True) { \ yy = zz << 1; \ if (yy > nHeap) break; \ if (yy < nHeap && \ weight[heap[yy+1]] < weight[heap[yy]]) \ yy++; \ if (weight[tmp] < weight[heap[yy]]) break; \ heap[zz] = heap[yy]; \ zz = yy; \ } \ heap[zz] = tmp; \ } Definition at line 84 of file huffman.c. Referenced by hbMakeCodeLengths().
|
|
|
|
Value: { \ Int32 zz, tmp; \ zz = z; tmp = heap[zz]; \ while (weight[tmp] < weight[heap[zz >> 1]]) { \ heap[zz] = heap[zz >> 1]; \ zz >>= 1; \ } \ heap[zz] = tmp; \ } Definition at line 73 of file huffman.c. Referenced by hbMakeCodeLengths().
|
|
|
|
Definition at line 175 of file huffman.c. Referenced by sendMTFValues().
00180 { 00181 Int32 n, vec, i; 00182 00183 vec = 0; 00184 for (n = minLen; n <= maxLen; n++) { 00185 for (i = 0; i < alphaSize; i++) 00186 if (length[i] == n) { code[i] = vec; vec++; }; 00187 vec <<= 1; 00188 } 00189 } |
|
Definition at line 193 of file huffman.c. Referenced by decompress().
00200 { 00201 Int32 pp, i, j, vec; 00202 00203 pp = 0; 00204 for (i = minLen; i <= maxLen; i++) 00205 for (j = 0; j < alphaSize; j++) 00206 if (length[j] == i) { perm[pp] = j; pp++; }; 00207 00208 for (i = 0; i < BZ_MAX_CODE_LEN; i++) base[i] = 0; 00209 for (i = 0; i < alphaSize; i++) base[length[i]+1]++; 00210 00211 for (i = 1; i < BZ_MAX_CODE_LEN; i++) base[i] += base[i-1]; 00212 00213 for (i = 0; i < BZ_MAX_CODE_LEN; i++) limit[i] = 0; 00214 vec = 0; 00215 00216 for (i = minLen; i <= maxLen; i++) { 00217 vec += (base[i+1] - base[i]); 00218 limit[i] = vec-1; 00219 vec <<= 1; 00220 } 00221 for (i = minLen + 1; i <= maxLen; i++) 00222 base[i] = ((limit[i-1] + 1) << 1) - base[i]; 00223 } |
|
Definition at line 103 of file huffman.c. Referenced by sendMTFValues().
00107 { 00108 /*-- 00109 Nodes and heap entries run from 1. Entry 0 00110 for both the heap and nodes is a sentinel. 00111 --*/ 00112 Int32 nNodes, nHeap, n1, n2, i, j, k; 00113 Bool tooLong; 00114 00115 Int32 heap [ BZ_MAX_ALPHA_SIZE + 2 ]; 00116 Int32 weight [ BZ_MAX_ALPHA_SIZE * 2 ]; 00117 Int32 parent [ BZ_MAX_ALPHA_SIZE * 2 ]; 00118 00119 for (i = 0; i < alphaSize; i++) 00120 weight[i+1] = (freq[i] == 0 ? 1 : freq[i]) << 8; 00121 00122 while (True) { 00123 00124 nNodes = alphaSize; 00125 nHeap = 0; 00126 00127 heap[0] = 0; 00128 weight[0] = 0; 00129 parent[0] = -2; 00130 00131 for (i = 1; i <= alphaSize; i++) { 00132 parent[i] = -1; 00133 nHeap++; 00134 heap[nHeap] = i; 00135 UPHEAP(nHeap); 00136 } 00137 00138 AssertH( nHeap < (BZ_MAX_ALPHA_SIZE+2), 2001 ); 00139 00140 while (nHeap > 1) { 00141 n1 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1); 00142 n2 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1); 00143 nNodes++; 00144 parent[n1] = parent[n2] = nNodes; 00145 weight[nNodes] = ADDWEIGHTS(weight[n1], weight[n2]); 00146 parent[nNodes] = -1; 00147 nHeap++; 00148 heap[nHeap] = nNodes; 00149 UPHEAP(nHeap); 00150 } 00151 00152 AssertH( nNodes < (BZ_MAX_ALPHA_SIZE * 2), 2002 ); 00153 00154 tooLong = False; 00155 for (i = 1; i <= alphaSize; i++) { 00156 j = 0; 00157 k = i; 00158 while (parent[k] >= 0) { k = parent[k]; j++; } 00159 len[i-1] = j; 00160 if (j > maxLen) tooLong = True; 00161 } 00162 00163 if (! tooLong) break; 00164 00165 for (i = 1; i < alphaSize; i++) { 00166 j = weight[i] >> 8; 00167 j = 1 + (j / 2); 00168 weight[i] = j << 8; 00169 } 00170 } 00171 } |