Mercurial > hg > toybox

comparison lib/bunzip.c @ 56:7794562e2e64

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Comment and whitespace changes.
author Rob Landley <rob@landley.net>
date Wed, 17 Jan 2007 13:58:08 -0500
parents 0bb7c679499a
children 034de958ee65
comparison
equal deleted inserted replaced
55:0bb7c679499a 56:7794562e2e64
115 bits |= (bd->inbufBits>>bd->inbufBitCount) & ((1<<bits_wanted)-1); 115 bits |= (bd->inbufBits>>bd->inbufBitCount) & ((1<<bits_wanted)-1);
116 116
117 return bits; 117 return bits;
118 } 118 }
119 119
120 // Decompress a block of text to into intermediate buffer 120 // Decompress a block of text to intermediate buffer
121 int read_bunzip_data(bunzip_data *bd) 121 int read_bunzip_data(bunzip_data *bd)
122 { 122 {
123 struct group_data *hufGroup; 123 struct group_data *hufGroup;
124 int dbufCount, nextSym, dbufSize, origPtr, groupCount, *base, *limit, 124 int dbufCount, nextSym, dbufSize, origPtr, groupCount, *base, *limit,
125 selector, i, j, k, t, runPos, symCount, symTotal, nSelectors, 125 selector, i, j, k, t, runPos, symCount, symTotal, nSelectors,
169 groupCount = get_bits(bd,3); 169 groupCount = get_bits(bd,3);
170 if (groupCount<2 || groupCount>MAX_GROUPS) return RETVAL_DATA_ERROR; 170 if (groupCount<2 || groupCount>MAX_GROUPS) return RETVAL_DATA_ERROR;
171 171
172 // nSelectors: Every GROUP_SIZE many symbols we select a new huffman coding 172 // nSelectors: Every GROUP_SIZE many symbols we select a new huffman coding
173 // group. Read in the group selector list, which is stored as MTF encoded 173 // group. Read in the group selector list, which is stored as MTF encoded
174 // bit runs. 174 // bit runs. (MTF = Move To Front. Every time a symbol occurs it's moved
175 // to the front of the table, so it has a shorter encoding next time.)
175 if (!(nSelectors = get_bits(bd, 15))) return RETVAL_DATA_ERROR; 176 if (!(nSelectors = get_bits(bd, 15))) return RETVAL_DATA_ERROR;
176 for (i=0; i<groupCount; i++) mtfSymbol[i] = i; 177 for (i=0; i<groupCount; i++) mtfSymbol[i] = i;
177 for (i=0; i<nSelectors; i++) { 178 for (i=0; i<nSelectors; i++) {
178 179
179 // Get next value 180 // Get next value
180 for(j=0;get_bits(bd,1);j++) 181 for(j=0;get_bits(bd,1);j++)
181 if (j>=groupCount) return RETVAL_DATA_ERROR; 182 if (j>=groupCount) return RETVAL_DATA_ERROR;
182 183
183 // Decode MTF to get the next selector 184 // Decode MTF to get the next selector, and move it to the front.
184 uc = mtfSymbol[j]; 185 uc = mtfSymbol[j];
185 memmove(mtfSymbol+1, mtfSymbol, j); 186 memmove(mtfSymbol+1, mtfSymbol, j);
186 mtfSymbol[0] = selectors[i] = uc; 187 mtfSymbol[0] = selectors[i] = uc;
187 } 188 }
188 // Read the huffman coding tables for each group, which code for symTotal 189 // Read the huffman coding tables for each group, which code for symTotal
219 * limit[] indicates the largest numerical value a symbol with a given 220 * limit[] indicates the largest numerical value a symbol with a given
220 * number of bits can have. It lets us know when to stop reading. 221 * number of bits can have. It lets us know when to stop reading.
221 * 222 *
222 * To use these, keep reading bits until value <= limit[bitcount] or 223 * To use these, keep reading bits until value <= limit[bitcount] or
223 * you've read over 20 bits (error). Then the decoded symbol 224 * you've read over 20 bits (error). Then the decoded symbol
224 * equals permute[hufcode_value-base[hufcode_bitcount]]. 225 * equals permute[hufcode_value - base[hufcode_bitcount]].
225 */ 226 */
226 hufGroup = bd->groups+j; 227 hufGroup = bd->groups+j;
227 hufGroup->minLen = minLen; 228 hufGroup->minLen = minLen;
228 hufGroup->maxLen = maxLen; 229 hufGroup->maxLen = maxLen;
229 230
230 // Note that minLen can't be smaller than 1, so we adjust the base 231 // Note that minLen can't be smaller than 1, so we adjust the base
231 // and limit array pointers so we're not always wasting the first 232 // and limit array pointers so we're not always wasting the first
232 // entry. We do this again when using them (during symbol decoding). 233 // entry. We do this again when using them (during symbol decoding).
233 base=hufGroup->base-1; 234 base = hufGroup->base-1;
234 limit=hufGroup->limit-1; 235 limit = hufGroup->limit-1;
235 236
236 // Calculate permute[] 237 // Calculate permute[]
237 pp = 0; 238 pp = 0;
238 for (i=minLen; i<=maxLen; i++) 239 for (i = minLen; i <= maxLen; i++)
239 for (t=0;t<symCount;t++) 240 for (t = 0; t < symCount; t++)
240 if (length[t]==i) hufGroup->permute[pp++] = t; 241 if (length[t] == i) hufGroup->permute[pp++] = t;
241 242
242 // Count cumulative symbols coded for at each bit length 243 // Count cumulative symbols coded for at each bit length
243 for (i=minLen; i<=maxLen; i++) temp[i] = limit[i] = 0; 244 for (i = minLen; i <= maxLen; i++) temp[i] = limit[i] = 0;
244 for (i=0; i<symCount; i++) temp[length[i]]++; 245 for (i = 0; i < symCount; i++) temp[length[i]]++;
245 246
246 /* Calculate limit[] (the largest symbol-coding value at each bit 247 /* Calculate limit[] (the largest symbol-coding value at each bit
247 * length, which is (previous limit<<1)+symbols at this level), and 248 * length, which is (previous limit<<1)+symbols at this level), and
248 * base[] (number of symbols to ignore at each bit length, which is 249 * base[] (number of symbols to ignore at each bit length, which is
249 * limit-cumulative count of symbols coded for already). */ 250 * limit-cumulative count of symbols coded for already). */
250 pp = t = 0; 251 pp = t = 0;
251 for (i=minLen; i<maxLen; i++) { 252 for (i = minLen; i < maxLen; i++) {
252 pp += temp[i]; 253 pp += temp[i];
253 limit[i] = pp-1; 254 limit[i] = pp-1;
254 pp <<= 1; 255 pp <<= 1;
255 base[i+1] = pp-(t+=temp[i]); 256 base[i+1] = pp-(t+=temp[i]);
256 } 257 }
264 265
265 // Initialize symbol occurrence counters and symbol mtf table 266 // Initialize symbol occurrence counters and symbol mtf table
266 memset(byteCount, 0, 256*sizeof(int)); 267 memset(byteCount, 0, 256*sizeof(int));
267 for(i=0; i<256; i++) mtfSymbol[i] = (unsigned char)i; 268 for(i=0; i<256; i++) mtfSymbol[i] = (unsigned char)i;
268 269
269 // Loop through compressed symbols 270 // Loop through compressed symbols. This is the first "tight inner loop"
271 // that needs to be micro-optimized for speed. (This one fills out dbuf[]
272 // linearly, staying in cache more, so isn't as limited by DRAM access.)
270 runPos = dbufCount = symCount = selector = 0; 273 runPos = dbufCount = symCount = selector = 0;
271 for (;;) { 274 for (;;) {
272 275
273 // Determine which huffman coding group to use. 276 // Determine which huffman coding group to use.
274 if (!(symCount--)) { 277 if (!(symCount--)) {