Manuel Novoa III writes:

Hello Rob,

Here's a patch to your bunzip-3.c file.  Nice work btw.

One minor bug fix... checking for error return when read()ing.
Some size/performance optimizations as well.  One instance of
memset() seems unnecssary.  You might want to take a look.

Anyway, on my machine, decompressing linux-2.6.0-test7.tar.bz2
to /dev/null gave the following times:

        bunzip-3.c    bzcat (system)   bunzip-3.c (patched)
real    0m24.420s     0m22.725s        0m20.701s
user    0m23.930s     0m22.170s        0m20.180s
sys     0m0.070s      0m0.080s         0m0.140s

Size of the patched version is comparable (slightly larger or
smaller depending on compiler flags).

Manuel

1 files changed, 43 insertions, 22 deletions

diff --git a/archival/libunarchive/decompress_bunzip2.c b/archival/libunarchive/decompress_bunzip2.c
index 474186a2a..b4bcb0b49 100644
--- a/archival/libunarchive/decompress_bunzip2.c
+++ b/archival/libunarchive/decompress_bunzip2.c
@@ -15,6 +15,7 @@
 #include <stdlib.h>
 #include <string.h>
 #include <unistd.h>
+#include <limits.h>
 
 /* Constants for huffman coding */
 #define MAX_GROUPS                      6
@@ -37,13 +38,14 @@
 /* Other housekeeping constants */
 #define IOBUF_SIZE                      4096
 
-char *bunzip_errors[]={NULL,"Bad file checksum","Not bzip data",
+static char * const bunzip_errors[]={NULL,"Bad file checksum","Not bzip data",
                 "Unexpected input EOF","Unexpected output EOF","Data error",
                  "Out of memory","Obsolete (pre 0.9.5) bzip format not supported."};
 
 /* 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];
+        /* We have an extra slot at the end of limit[] for a sentinal value. */
+        int limit[MAX_HUFCODE_BITS+1],base[MAX_HUFCODE_BITS],permute[MAX_SYMBOLS];
         char minLen, maxLen;
 };
 
@@ -82,7 +84,7 @@ static unsigned int get_bits(bunzip_data *bd, char bits_wanted)
         while (bd->inbufBitCount<bits_wanted) {
                 /* If we need to read more data from file into byte buffer, do so */
                 if(bd->inbufPos==bd->inbufCount) {
-                        if(!(bd->inbufCount = read(bd->in_fd, bd->inbuf, IOBUF_SIZE)))
+                        if((bd->inbufCount = read(bd->in_fd, bd->inbuf, IOBUF_SIZE)) <= 0)
                                 longjmp(bd->jmpbuf,RETVAL_UNEXPECTED_INPUT_EOF);
                         bd->inbufPos=0;
                 }
@@ -104,6 +106,14 @@ static unsigned int get_bits(bunzip_data *bd, char bits_wanted)
         return bits;
 }
 
+/* At certain times, it pays to have an optimized inline version of
+ * get_bits() which gets a single bit. */
+#define GET_A_BIT(bd) \
+   ((bd->inbufBitCount > 0) \
+        ? ((unsigned int)(((bd)->inbufBits >> --(bd)->inbufBitCount) & 1)) \
+        : get_bits((bd), 1))
+
+
 /* Decompress a block of text to into intermediate buffer */
 
 extern int read_bunzip_data(bunzip_data *bd)
@@ -140,7 +150,10 @@ extern int read_bunzip_data(bunzip_data *bd)
            values were present.  We make a translation table to convert the symbols
            back to the corresponding bytes. */
         t=get_bits(bd, 16);
+#if 0
+        /* I don't believe this is necessary.  Rob? */
         memset(symToByte,0,256);
+#endif
         symTotal=0;
         for (i=0;i<16;i++) {
                 if(t&(1<<(15-i))) {
@@ -162,7 +175,13 @@ extern int read_bunzip_data(bunzip_data *bd)
                 for(j=0;get_bits(bd,1);j++) if (j>=groupCount) return RETVAL_DATA_ERROR;
                 /* Decode MTF to get the next selector */
                 uc = mtfSymbol[j];
-                memmove(mtfSymbol+1,mtfSymbol,j);
+                /* A very small amount of data to move, so memmove is overkill
+                 * and bigger at least in my tests. */
+                k = j;
+                while (k) {
+                        mtfSymbol[k] = mtfSymbol[k-1];
+                        --k;
+                }
                 mtfSymbol[0]=selectors[i]=uc;
         }
         /* Read the huffman coding tables for each group, which code for symTotal
@@ -172,15 +191,15 @@ extern int read_bunzip_data(bunzip_data *bd)
                 unsigned char length[MAX_SYMBOLS],temp[MAX_HUFCODE_BITS+1];
                 int     minLen, maxLen, pp;
                 /* Read lengths */
-                t=get_bits(bd, 5);
+                t=get_bits(bd, 5) - 1;  /* This lets us avoid a test in the loop. */
                 for (i = 0; i < symCount; i++) {
                         for(;;) {
-                                if (t < 1 || t > MAX_HUFCODE_BITS) return RETVAL_DATA_ERROR;
+                                if (((unsigned)t) > (MAX_HUFCODE_BITS-1)) return RETVAL_DATA_ERROR;
                                         if(!get_bits(bd, 1)) break;
-                                        if(!get_bits(bd, 1)) t++;
-                                        else t--;
+                                        /* We can avoid an if/else with a little arithmetic. */
+                                        t += (1 - 2*get_bits(bd, 1)); /* 0 -> t++ ; 1 -> t-- */
                         }
-                        length[i] = t;
+                        length[i] = t + 1;      /* Correct for the initial -1 adjustment. */
                 }
                 /* Find largest and smallest lengths in this group */
                 minLen=maxLen=length[0];
@@ -228,6 +247,7 @@ extern int read_bunzip_data(bunzip_data *bd)
                         pp<<=1;
                         base[i+1]=pp-(t+=temp[i]);
                 }
+                limit[maxLen+1] = INT_MAX; /* Sentinal value for reading next sym. */
                 limit[maxLen]=pp+temp[maxLen]-1;
                 base[minLen]=0;
         }
@@ -252,19 +272,15 @@ extern int read_bunzip_data(bunzip_data *bd)
                 /* 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;
-                        i++;
-
-                        j = (j << 1) | get_bits(bd,1);
+                while (j > limit[i]) { /* The sentinal allows us to avoid testing i. */
+                        j = (j << 1) | GET_A_BIT(bd);
+                        ++i;
                 }
                 /* 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-=base[i])) >= MAX_SYMBOLS)) return RETVAL_DATA_ERROR;
                 nextSym = hufGroup->permute[j];
                 /* If this is a repeated run, loop collecting data */
-                if (nextSym == SYMBOL_RUNA || nextSym == SYMBOL_RUNB) {
+                if (((unsigned)nextSym) <= SYMBOL_RUNB) { /* RUNA or RUNB */
                         /* If this is the start of a new run, zero out counter */
                         if(!runPos) {
                                 runPos = 1;
@@ -277,8 +293,7 @@ extern int read_bunzip_data(bunzip_data *bd)
                            the basic or 0/1 method (except all bits 0, which would use no
                            symbols, but a run of length 0 doesn't mean anything in this
                            context).  Thus space is saved. */
-                        if (nextSym == SYMBOL_RUNA) t += runPos;
-                        else t += 2*runPos;
+                        t += (runPos << nextSym); /* +runPos if RUNA; +2*runPos if RUNB */
                         runPos <<= 1;
                         continue;
                 }
@@ -305,7 +320,13 @@ extern int read_bunzip_data(bunzip_data *bd)
                 if(dbufCount>=dbufSize) return RETVAL_DATA_ERROR;
                 i = nextSym - 1;
                 uc = mtfSymbol[i];
-                memmove(mtfSymbol+1,mtfSymbol,i);
+                /* Since we typically expect to move only a small number of symbols,
+                 * and are bound by 256 in any case, using memmove here would
+                 * typically be slower due to function call overhead and other
+                 * assorted setup costs. */
+                do {
+                        mtfSymbol[i] = mtfSymbol[i-1];
+                } while (--i);
                 mtfSymbol[0] = uc;
                 uc=symToByte[uc];
                 /* We have our literal byte.  Save it into dbuf. */
@@ -319,7 +340,7 @@ extern int read_bunzip_data(bunzip_data *bd)
          */
 
         /* Now we know what dbufCount is, do a better sanity check on origPtr.  */
-        if (origPtr<0 || origPtr>=dbufCount) return RETVAL_DATA_ERROR;
+        if (((unsigned)origPtr)>=dbufCount) return RETVAL_DATA_ERROR;
         /* Turn byteCount into cumulative occurrence counts of 0 to n-1. */
         j=0;
         for(i=0;i<256;i++) {