Mercurial > hg > sv-dependency-builds

annotate src/bzip2-1.0.6/huffman.c @ 169:223a55898ab9 tip default

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add null config files
author Chris Cannam <cannam@all-day-breakfast.com>
date Mon, 02 Mar 2020 14:03:47 +0000
parents 8a15ff55d9af
children
rev   line source
cannam@89 1
cannam@89 2 /*-------------------------------------------------------------*/
cannam@89 3 /*--- Huffman coding low-level stuff ---*/
cannam@89 4 /*--- huffman.c ---*/
cannam@89 5 /*-------------------------------------------------------------*/
cannam@89 6
cannam@89 7 /* ------------------------------------------------------------------
cannam@89 8 This file is part of bzip2/libbzip2, a program and library for
cannam@89 9 lossless, block-sorting data compression.
cannam@89 10
cannam@89 11 bzip2/libbzip2 version 1.0.6 of 6 September 2010
cannam@89 12 Copyright (C) 1996-2010 Julian Seward <jseward@bzip.org>
cannam@89 13
cannam@89 14 Please read the WARNING, DISCLAIMER and PATENTS sections in the
cannam@89 15 README file.
cannam@89 16
cannam@89 17 This program is released under the terms of the license contained
cannam@89 18 in the file LICENSE.
cannam@89 19 ------------------------------------------------------------------ */
cannam@89 20
cannam@89 21
cannam@89 22 #include "bzlib_private.h"
cannam@89 23
cannam@89 24 /*---------------------------------------------------*/
cannam@89 25 #define WEIGHTOF(zz0) ((zz0) & 0xffffff00)
cannam@89 26 #define DEPTHOF(zz1) ((zz1) & 0x000000ff)
cannam@89 27 #define MYMAX(zz2,zz3) ((zz2) > (zz3) ? (zz2) : (zz3))
cannam@89 28
cannam@89 29 #define ADDWEIGHTS(zw1,zw2) \
cannam@89 30 (WEIGHTOF(zw1)+WEIGHTOF(zw2)) | \
cannam@89 31 (1 + MYMAX(DEPTHOF(zw1),DEPTHOF(zw2)))
cannam@89 32
cannam@89 33 #define UPHEAP(z) \
cannam@89 34 { \
cannam@89 35 Int32 zz, tmp; \
cannam@89 36 zz = z; tmp = heap[zz]; \
cannam@89 37 while (weight[tmp] < weight[heap[zz >> 1]]) { \
cannam@89 38 heap[zz] = heap[zz >> 1]; \
cannam@89 39 zz >>= 1; \
cannam@89 40 } \
cannam@89 41 heap[zz] = tmp; \
cannam@89 42 }
cannam@89 43
cannam@89 44 #define DOWNHEAP(z) \
cannam@89 45 { \
cannam@89 46 Int32 zz, yy, tmp; \
cannam@89 47 zz = z; tmp = heap[zz]; \
cannam@89 48 while (True) { \
cannam@89 49 yy = zz << 1; \
cannam@89 50 if (yy > nHeap) break; \
cannam@89 51 if (yy < nHeap && \
cannam@89 52 weight[heap[yy+1]] < weight[heap[yy]]) \
cannam@89 53 yy++; \
cannam@89 54 if (weight[tmp] < weight[heap[yy]]) break; \
cannam@89 55 heap[zz] = heap[yy]; \
cannam@89 56 zz = yy; \
cannam@89 57 } \
cannam@89 58 heap[zz] = tmp; \
cannam@89 59 }
cannam@89 60
cannam@89 61
cannam@89 62 /*---------------------------------------------------*/
cannam@89 63 void BZ2_hbMakeCodeLengths ( UChar *len,
cannam@89 64 Int32 *freq,
cannam@89 65 Int32 alphaSize,
cannam@89 66 Int32 maxLen )
cannam@89 67 {
cannam@89 68 /*--
cannam@89 69 Nodes and heap entries run from 1. Entry 0
cannam@89 70 for both the heap and nodes is a sentinel.
cannam@89 71 --*/
cannam@89 72 Int32 nNodes, nHeap, n1, n2, i, j, k;
cannam@89 73 Bool tooLong;
cannam@89 74
cannam@89 75 Int32 heap [ BZ_MAX_ALPHA_SIZE + 2 ];
cannam@89 76 Int32 weight [ BZ_MAX_ALPHA_SIZE * 2 ];
cannam@89 77 Int32 parent [ BZ_MAX_ALPHA_SIZE * 2 ];
cannam@89 78
cannam@89 79 for (i = 0; i < alphaSize; i++)
cannam@89 80 weight[i+1] = (freq[i] == 0 ? 1 : freq[i]) << 8;
cannam@89 81
cannam@89 82 while (True) {
cannam@89 83
cannam@89 84 nNodes = alphaSize;
cannam@89 85 nHeap = 0;
cannam@89 86
cannam@89 87 heap[0] = 0;
cannam@89 88 weight[0] = 0;
cannam@89 89 parent[0] = -2;
cannam@89 90
cannam@89 91 for (i = 1; i <= alphaSize; i++) {
cannam@89 92 parent[i] = -1;
cannam@89 93 nHeap++;
cannam@89 94 heap[nHeap] = i;
cannam@89 95 UPHEAP(nHeap);
cannam@89 96 }
cannam@89 97
cannam@89 98 AssertH( nHeap < (BZ_MAX_ALPHA_SIZE+2), 2001 );
cannam@89 99
cannam@89 100 while (nHeap > 1) {
cannam@89 101 n1 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
cannam@89 102 n2 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
cannam@89 103 nNodes++;
cannam@89 104 parent[n1] = parent[n2] = nNodes;
cannam@89 105 weight[nNodes] = ADDWEIGHTS(weight[n1], weight[n2]);
cannam@89 106 parent[nNodes] = -1;
cannam@89 107 nHeap++;
cannam@89 108 heap[nHeap] = nNodes;
cannam@89 109 UPHEAP(nHeap);
cannam@89 110 }
cannam@89 111
cannam@89 112 AssertH( nNodes < (BZ_MAX_ALPHA_SIZE * 2), 2002 );
cannam@89 113
cannam@89 114 tooLong = False;
cannam@89 115 for (i = 1; i <= alphaSize; i++) {
cannam@89 116 j = 0;
cannam@89 117 k = i;
cannam@89 118 while (parent[k] >= 0) { k = parent[k]; j++; }
cannam@89 119 len[i-1] = j;
cannam@89 120 if (j > maxLen) tooLong = True;
cannam@89 121 }
cannam@89 122
cannam@89 123 if (! tooLong) break;
cannam@89 124
cannam@89 125 /* 17 Oct 04: keep-going condition for the following loop used
cannam@89 126 to be 'i < alphaSize', which missed the last element,
cannam@89 127 theoretically leading to the possibility of the compressor
cannam@89 128 looping. However, this count-scaling step is only needed if
cannam@89 129 one of the generated Huffman code words is longer than
cannam@89 130 maxLen, which up to and including version 1.0.2 was 20 bits,
cannam@89 131 which is extremely unlikely. In version 1.0.3 maxLen was
cannam@89 132 changed to 17 bits, which has minimal effect on compression
cannam@89 133 ratio, but does mean this scaling step is used from time to
cannam@89 134 time, enough to verify that it works.
cannam@89 135
cannam@89 136 This means that bzip2-1.0.3 and later will only produce
cannam@89 137 Huffman codes with a maximum length of 17 bits. However, in
cannam@89 138 order to preserve backwards compatibility with bitstreams
cannam@89 139 produced by versions pre-1.0.3, the decompressor must still
cannam@89 140 handle lengths of up to 20. */
cannam@89 141
cannam@89 142 for (i = 1; i <= alphaSize; i++) {
cannam@89 143 j = weight[i] >> 8;
cannam@89 144 j = 1 + (j / 2);
cannam@89 145 weight[i] = j << 8;
cannam@89 146 }
cannam@89 147 }
cannam@89 148 }
cannam@89 149
cannam@89 150
cannam@89 151 /*---------------------------------------------------*/
cannam@89 152 void BZ2_hbAssignCodes ( Int32 *code,
cannam@89 153 UChar *length,
cannam@89 154 Int32 minLen,
cannam@89 155 Int32 maxLen,
cannam@89 156 Int32 alphaSize )
cannam@89 157 {
cannam@89 158 Int32 n, vec, i;
cannam@89 159
cannam@89 160 vec = 0;
cannam@89 161 for (n = minLen; n <= maxLen; n++) {
cannam@89 162 for (i = 0; i < alphaSize; i++)
cannam@89 163 if (length[i] == n) { code[i] = vec; vec++; };
cannam@89 164 vec <<= 1;
cannam@89 165 }
cannam@89 166 }
cannam@89 167
cannam@89 168
cannam@89 169 /*---------------------------------------------------*/
cannam@89 170 void BZ2_hbCreateDecodeTables ( Int32 *limit,
cannam@89 171 Int32 *base,
cannam@89 172 Int32 *perm,
cannam@89 173 UChar *length,
cannam@89 174 Int32 minLen,
cannam@89 175 Int32 maxLen,
cannam@89 176 Int32 alphaSize )
cannam@89 177 {
cannam@89 178 Int32 pp, i, j, vec;
cannam@89 179
cannam@89 180 pp = 0;
cannam@89 181 for (i = minLen; i <= maxLen; i++)
cannam@89 182 for (j = 0; j < alphaSize; j++)
cannam@89 183 if (length[j] == i) { perm[pp] = j; pp++; };
cannam@89 184
cannam@89 185 for (i = 0; i < BZ_MAX_CODE_LEN; i++) base[i] = 0;
cannam@89 186 for (i = 0; i < alphaSize; i++) base[length[i]+1]++;
cannam@89 187
cannam@89 188 for (i = 1; i < BZ_MAX_CODE_LEN; i++) base[i] += base[i-1];
cannam@89 189
cannam@89 190 for (i = 0; i < BZ_MAX_CODE_LEN; i++) limit[i] = 0;
cannam@89 191 vec = 0;
cannam@89 192
cannam@89 193 for (i = minLen; i <= maxLen; i++) {
cannam@89 194 vec += (base[i+1] - base[i]);
cannam@89 195 limit[i] = vec-1;
cannam@89 196 vec <<= 1;
cannam@89 197 }
cannam@89 198 for (i = minLen + 1; i <= maxLen; i++)
cannam@89 199 base[i] = ((limit[i-1] + 1) << 1) - base[i];
cannam@89 200 }
cannam@89 201
cannam@89 202
cannam@89 203 /*-------------------------------------------------------------*/
cannam@89 204 /*--- end huffman.c ---*/
cannam@89 205 /*-------------------------------------------------------------*/