Mercurial > hg > toybox

comparison lib/bunzip.c @ 61:d6ece20e13ce

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Minor cleanups.
author Rob Landley <rob@landley.net>
date Wed, 17 Jan 2007 18:24:17 -0500
parents 23aac9d42234
children f41f997c1e73
comparison
equal deleted inserted replaced
60:23aac9d42234 61:d6ece20e13ce
119 119
120 // Decompress a block of text to 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 unsigned origPtr;
125 int dbufCount, nextSym, dbufSize, groupCount, *base, *limit,
125 selector, i, j, k, t, runPos, symCount, symTotal, nSelectors, 126 selector, i, j, k, t, runPos, symCount, symTotal, nSelectors,
126 byteCount[256]; 127 byteCount[256];
127 char uc, mtfSymbol[256], symToByte[256], *selectors; 128 char uc, mtfSymbol[256], symToByte[256], *selectors;
128 unsigned int *dbuf; 129 unsigned int *dbuf;
129 130
146 dbufSize = bd->dbufSize; 147 dbufSize = bd->dbufSize;
147 selectors = bd->selectors; 148 selectors = bd->selectors;
148 149
149 // We can add support for blockRandomised if anybody complains. 150 // We can add support for blockRandomised if anybody complains.
150 if (get_bits(bd,1)) return RETVAL_OBSOLETE_INPUT; 151 if (get_bits(bd,1)) return RETVAL_OBSOLETE_INPUT;
151 if ((origPtr=get_bits(bd,24)) > dbufSize) return RETVAL_DATA_ERROR; 152 if ((origPtr = get_bits(bd,24)) > dbufSize) return RETVAL_DATA_ERROR;
152 153
153 // mapping table: if some byte values are never used (encoding things 154 // mapping table: if some byte values are never used (encoding things
154 // like ascii text), the compression code removes the gaps to have fewer 155 // like ascii text), the compression code removes the gaps to have fewer
155 // symbols to deal with, and writes a sparse bitfield indicating which 156 // symbols to deal with, and writes a sparse bitfield indicating which
156 // values were present. We make a translation table to convert the symbols 157 // values were present. We make a translation table to convert the symbols
344 Another instance of the first symbol in the mtf array, position 0, 345 Another instance of the first symbol in the mtf array, position 0,
345 would have been handled as part of a run.) */ 346 would have been handled as part of a run.) */
346 if (dbufCount>=dbufSize) return RETVAL_DATA_ERROR; 347 if (dbufCount>=dbufSize) return RETVAL_DATA_ERROR;
347 i = nextSym - 1; 348 i = nextSym - 1;
348 uc = mtfSymbol[i]; 349 uc = mtfSymbol[i];
349 // On my laptop, unrolling this memmove() into a loop costs 11 bytes 350 // On my laptop, unrolling this memmove() into a loop shaves 3.5% off
350 // but shaves 3.5% off the total running time. 351 // the total running time.
351 while(i--) mtfSymbol[i+1] = mtfSymbol[i]; 352 while(i--) mtfSymbol[i+1] = mtfSymbol[i];
352 mtfSymbol[0] = uc; 353 mtfSymbol[0] = uc;
353 uc = symToByte[uc]; 354 uc = symToByte[uc];
354 355
355 // We have our literal byte. Save it into dbuf. 356 // We have our literal byte. Save it into dbuf.
362 them in dbuf[]. Now undo the Burrows-Wheeler transform on dbuf. 363 them in dbuf[]. Now undo the Burrows-Wheeler transform on dbuf.
363 See http://marknelson.us/1996/09/01/bwt/ 364 See http://marknelson.us/1996/09/01/bwt/
364 */ 365 */
365 366
366 // Now we know what dbufCount is, do a better sanity check on origPtr. 367 // Now we know what dbufCount is, do a better sanity check on origPtr.
367 if (origPtr<0 || origPtr>=dbufCount) return RETVAL_DATA_ERROR; 368 if (origPtr>=dbufCount) return RETVAL_DATA_ERROR;
368 369
369 // Turn byteCount into cumulative occurrence counts of 0 to n-1. 370 // Turn byteCount into cumulative occurrence counts of 0 to n-1.
370 j = 0; 371 j = 0;
371 for (i=0;i<256;i++) { 372 for (i=0;i<256;i++) {
372 k = j+byteCount[i]; 373 k = j+byteCount[i];