1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/modules/libbz2/src/huffman.c Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,205 @@
1.4 +
1.5 +/*-------------------------------------------------------------*/
1.6 +/*--- Huffman coding low-level stuff ---*/
1.7 +/*--- huffman.c ---*/
1.8 +/*-------------------------------------------------------------*/
1.9 +
1.10 +/* ------------------------------------------------------------------
1.11 + This file is part of bzip2/libbzip2, a program and library for
1.12 + lossless, block-sorting data compression.
1.13 +
1.14 + bzip2/libbzip2 version 1.0.4 of 20 December 2006
1.15 + Copyright (C) 1996-2006 Julian Seward <jseward@bzip.org>
1.16 +
1.17 + Please read the WARNING, DISCLAIMER and PATENTS sections in the
1.18 + README file.
1.19 +
1.20 + This program is released under the terms of the license contained
1.21 + in the file LICENSE.
1.22 + ------------------------------------------------------------------ */
1.23 +
1.24 +
1.25 +#include "bzlib_private.h"
1.26 +
1.27 +/*---------------------------------------------------*/
1.28 +#define WEIGHTOF(zz0) ((zz0) & 0xffffff00)
1.29 +#define DEPTHOF(zz1) ((zz1) & 0x000000ff)
1.30 +#define MYMAX(zz2,zz3) ((zz2) > (zz3) ? (zz2) : (zz3))
1.31 +
1.32 +#define ADDWEIGHTS(zw1,zw2) \
1.33 + (WEIGHTOF(zw1)+WEIGHTOF(zw2)) | \
1.34 + (1 + MYMAX(DEPTHOF(zw1),DEPTHOF(zw2)))
1.35 +
1.36 +#define UPHEAP(z) \
1.37 +{ \
1.38 + Int32 zz, tmp; \
1.39 + zz = z; tmp = heap[zz]; \
1.40 + while (weight[tmp] < weight[heap[zz >> 1]]) { \
1.41 + heap[zz] = heap[zz >> 1]; \
1.42 + zz >>= 1; \
1.43 + } \
1.44 + heap[zz] = tmp; \
1.45 +}
1.46 +
1.47 +#define DOWNHEAP(z) \
1.48 +{ \
1.49 + Int32 zz, yy, tmp; \
1.50 + zz = z; tmp = heap[zz]; \
1.51 + while (True) { \
1.52 + yy = zz << 1; \
1.53 + if (yy > nHeap) break; \
1.54 + if (yy < nHeap && \
1.55 + weight[heap[yy+1]] < weight[heap[yy]]) \
1.56 + yy++; \
1.57 + if (weight[tmp] < weight[heap[yy]]) break; \
1.58 + heap[zz] = heap[yy]; \
1.59 + zz = yy; \
1.60 + } \
1.61 + heap[zz] = tmp; \
1.62 +}
1.63 +
1.64 +
1.65 +/*---------------------------------------------------*/
1.66 +void BZ2_hbMakeCodeLengths ( UChar *len,
1.67 + Int32 *freq,
1.68 + Int32 alphaSize,
1.69 + Int32 maxLen )
1.70 +{
1.71 + /*--
1.72 + Nodes and heap entries run from 1. Entry 0
1.73 + for both the heap and nodes is a sentinel.
1.74 + --*/
1.75 + Int32 nNodes, nHeap, n1, n2, i, j, k;
1.76 + Bool tooLong;
1.77 +
1.78 + Int32 heap [ BZ_MAX_ALPHA_SIZE + 2 ];
1.79 + Int32 weight [ BZ_MAX_ALPHA_SIZE * 2 ];
1.80 + Int32 parent [ BZ_MAX_ALPHA_SIZE * 2 ];
1.81 +
1.82 + for (i = 0; i < alphaSize; i++)
1.83 + weight[i+1] = (freq[i] == 0 ? 1 : freq[i]) << 8;
1.84 +
1.85 + while (True) {
1.86 +
1.87 + nNodes = alphaSize;
1.88 + nHeap = 0;
1.89 +
1.90 + heap[0] = 0;
1.91 + weight[0] = 0;
1.92 + parent[0] = -2;
1.93 +
1.94 + for (i = 1; i <= alphaSize; i++) {
1.95 + parent[i] = -1;
1.96 + nHeap++;
1.97 + heap[nHeap] = i;
1.98 + UPHEAP(nHeap);
1.99 + }
1.100 +
1.101 + AssertH( nHeap < (BZ_MAX_ALPHA_SIZE+2), 2001 );
1.102 +
1.103 + while (nHeap > 1) {
1.104 + n1 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
1.105 + n2 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
1.106 + nNodes++;
1.107 + parent[n1] = parent[n2] = nNodes;
1.108 + weight[nNodes] = ADDWEIGHTS(weight[n1], weight[n2]);
1.109 + parent[nNodes] = -1;
1.110 + nHeap++;
1.111 + heap[nHeap] = nNodes;
1.112 + UPHEAP(nHeap);
1.113 + }
1.114 +
1.115 + AssertH( nNodes < (BZ_MAX_ALPHA_SIZE * 2), 2002 );
1.116 +
1.117 + tooLong = False;
1.118 + for (i = 1; i <= alphaSize; i++) {
1.119 + j = 0;
1.120 + k = i;
1.121 + while (parent[k] >= 0) { k = parent[k]; j++; }
1.122 + len[i-1] = j;
1.123 + if (j > maxLen) tooLong = True;
1.124 + }
1.125 +
1.126 + if (! tooLong) break;
1.127 +
1.128 + /* 17 Oct 04: keep-going condition for the following loop used
1.129 + to be 'i < alphaSize', which missed the last element,
1.130 + theoretically leading to the possibility of the compressor
1.131 + looping. However, this count-scaling step is only needed if
1.132 + one of the generated Huffman code words is longer than
1.133 + maxLen, which up to and including version 1.0.2 was 20 bits,
1.134 + which is extremely unlikely. In version 1.0.3 maxLen was
1.135 + changed to 17 bits, which has minimal effect on compression
1.136 + ratio, but does mean this scaling step is used from time to
1.137 + time, enough to verify that it works.
1.138 +
1.139 + This means that bzip2-1.0.3 and later will only produce
1.140 + Huffman codes with a maximum length of 17 bits. However, in
1.141 + order to preserve backwards compatibility with bitstreams
1.142 + produced by versions pre-1.0.3, the decompressor must still
1.143 + handle lengths of up to 20. */
1.144 +
1.145 + for (i = 1; i <= alphaSize; i++) {
1.146 + j = weight[i] >> 8;
1.147 + j = 1 + (j / 2);
1.148 + weight[i] = j << 8;
1.149 + }
1.150 + }
1.151 +}
1.152 +
1.153 +
1.154 +/*---------------------------------------------------*/
1.155 +void BZ2_hbAssignCodes ( Int32 *code,
1.156 + UChar *length,
1.157 + Int32 minLen,
1.158 + Int32 maxLen,
1.159 + Int32 alphaSize )
1.160 +{
1.161 + Int32 n, vec, i;
1.162 +
1.163 + vec = 0;
1.164 + for (n = minLen; n <= maxLen; n++) {
1.165 + for (i = 0; i < alphaSize; i++)
1.166 + if (length[i] == n) { code[i] = vec; vec++; };
1.167 + vec <<= 1;
1.168 + }
1.169 +}
1.170 +
1.171 +
1.172 +/*---------------------------------------------------*/
1.173 +void BZ2_hbCreateDecodeTables ( Int32 *limit,
1.174 + Int32 *base,
1.175 + Int32 *perm,
1.176 + UChar *length,
1.177 + Int32 minLen,
1.178 + Int32 maxLen,
1.179 + Int32 alphaSize )
1.180 +{
1.181 + Int32 pp, i, j, vec;
1.182 +
1.183 + pp = 0;
1.184 + for (i = minLen; i <= maxLen; i++)
1.185 + for (j = 0; j < alphaSize; j++)
1.186 + if (length[j] == i) { perm[pp] = j; pp++; };
1.187 +
1.188 + for (i = 0; i < BZ_MAX_CODE_LEN; i++) base[i] = 0;
1.189 + for (i = 0; i < alphaSize; i++) base[length[i]+1]++;
1.190 +
1.191 + for (i = 1; i < BZ_MAX_CODE_LEN; i++) base[i] += base[i-1];
1.192 +
1.193 + for (i = 0; i < BZ_MAX_CODE_LEN; i++) limit[i] = 0;
1.194 + vec = 0;
1.195 +
1.196 + for (i = minLen; i <= maxLen; i++) {
1.197 + vec += (base[i+1] - base[i]);
1.198 + limit[i] = vec-1;
1.199 + vec <<= 1;
1.200 + }
1.201 + for (i = minLen + 1; i <= maxLen; i++)
1.202 + base[i] = ((limit[i-1] + 1) << 1) - base[i];
1.203 +}
1.204 +
1.205 +
1.206 +/*-------------------------------------------------------------*/
1.207 +/*--- end huffman.c ---*/
1.208 +/*-------------------------------------------------------------*/
