Mercurial > hg > toybox
changeset 62:f41f997c1e73
More optimizations originally suggested by Manuel Nova: Use a sentinel value
for limit[] to move a test out of a loop. Unroll a single-bit get_bits()
to avoid a function call in the common case on a hot path. And one more
application of the old "two tests in one via typecasting and/or math" trick.
author | Rob Landley <rob@landley.net> |
---|---|
date | Thu, 18 Jan 2007 18:16:11 -0500 |
parents | d6ece20e13ce |
children | 69efffcacd70 |
files | lib/bunzip.c |
diffstat | 1 files changed, 12 insertions(+), 6 deletions(-) [+] |
line wrap: on
line diff
--- a/lib/bunzip.c Wed Jan 17 18:24:17 2007 -0500 +++ b/lib/bunzip.c Thu Jan 18 18:16:11 2007 -0500 @@ -46,7 +46,7 @@ // This is what we know about each huffman coding group struct group_data { - int limit[MAX_HUFCODE_BITS], base[MAX_HUFCODE_BITS], permute[MAX_SYMBOLS]; + int limit[MAX_HUFCODE_BITS+1], base[MAX_HUFCODE_BITS], permute[MAX_SYMBOLS]; char minLen, maxLen; }; @@ -259,6 +259,7 @@ base[i+1] = pp-(t+=temp[i]); } limit[maxLen] = pp+temp[maxLen]-1; + limit[maxLen+1] = INT_MAX; base[minLen] = 0; } @@ -288,17 +289,22 @@ // Read next huffman-coded symbol i = hufGroup->minLen; j = get_bits(bd, i); - for (;;) { - if (i > hufGroup->maxLen) return RETVAL_DATA_ERROR; - if (j <= limit[i]) break; + while (j > limit[i]) { + // if (i > hufGroup->maxLen) return RETVAL_DATA_ERROR; i++; - j = (j << 1) | get_bits(bd,1); + // Unroll get_bits() to avoid a function call when the data's in + // the buffer already. + k = bd->inbufBitCount + ? (bd->inbufBits >> --(bd->inbufBitCount)) & 1 + : get_bits(bd, 1); + j = (j << 1) | k; } // Huffman decode nextSym (with bounds checking) j-=base[i]; - if (j < 0 || j >= MAX_SYMBOLS) return RETVAL_DATA_ERROR; + if (i > hufGroup->maxLen || (unsigned)j >= MAX_SYMBOLS) + return RETVAL_DATA_ERROR; nextSym = hufGroup->permute[j]; // If this is a repeated run, loop collecting data