The Tor Browser / file comparison
comparison: modules/libbz2/src/huffman.c
modules/libbz2/src/huffman.c
- changeset 0
- 6474c204b198
equal
deleted
inserted
replaced
| -1:000000000000 | 0:8e8c0035a374 |
|---|---|
| 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.4 of 20 December 2006 | |
| 12 Copyright (C) 1996-2006 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 /*-------------------------------------------------------------*/ |
