Speed and memory usage improvements from Laurence Adnerson

2 files changed, 190 insertions, 164 deletions

diff --git a/archival/libunarchive/decompress_unzip.c b/archival/libunarchive/decompress_unzip.c
index 7ebbd0ee7..d8d5b77b1 100644
--- a/archival/libunarchive/decompress_unzip.c
+++ b/archival/libunarchive/decompress_unzip.c
@@ -14,6 +14,8 @@
  * General cleanup to better adhere to the style guide and make use of standard
  * busybox functions by Glenn McGrath <bug1@optushome.com.au>
  * 
+ * read_gz interface + associated hacking by Laurence Anderson
+ *
  * This program is free software; you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
  * the Free Software Foundation; either version 2 of the License, or
@@ -92,20 +94,15 @@ unsigned char *gunzip_in_buffer;
 /* gunzip_window size--must be a power of two, and
  *  at least 32K for zip's deflate method */
 static const int gunzip_wsize = 0x8000;
-static int output_buffer_size = 0x8000; // gunzip_wsize initially
 
 static unsigned char *gunzip_window;
 static unsigned int *gunzip_crc_table;
 unsigned int gunzip_crc;
 
-static unsigned char *output_buffer;
-static unsigned int output_buffer_len;
-
 /* If BMAX needs to be larger than 16, then h and x[] should be ulg. */
 #define BMAX 16 /* maximum bit length of any code (16 for explode) */
 #define N_MAX 288       /* maximum number of codes in any set */
 
-static unsigned int gunzip_hufts;       /* track memory usage */
 static unsigned int gunzip_bb;  /* bit buffer */
 static unsigned char gunzip_bk; /* bits in bit buffer */
 
@@ -343,7 +340,6 @@ static int huft_build(unsigned int *b, const unsigned int n,
                                 /* allocate and link in new table */
                                 q = (huft_t *) xmalloc((z + 1) * sizeof(huft_t));
 
-                                gunzip_hufts += z + 1;  /* track memory usage */
                                 *t = q + 1;     /* link to list for huft_free() */
                                 *(t = &(q->v.t)) = NULL;
                                 u[h] = ++q;     /* table starts after link */
@@ -395,36 +391,6 @@ static int huft_build(unsigned int *b, const unsigned int n,
         return y != 0 && g != 1;
 }
 
-/* ===========================================================================
- * Write the output gunzip_window gunzip_window[0..gunzip_outbuf_count-1] and update crc and gunzip_bytes_out.
- * (Used for the decompressed data only.)
- */
-static void flush_gunzip_window(void)
-{
-        int n;
-
-        for (n = 0; n < gunzip_outbuf_count; n++) {
-                gunzip_crc = gunzip_crc_table[((int) gunzip_crc ^ (gunzip_window[n])) & 0xff] ^ (gunzip_crc >> 8);
-        }
-
-        if (output_buffer_len == 0) { // Our buffer is empty -> straight memcpy
-                memcpy(output_buffer, gunzip_window, gunzip_outbuf_count);
-                output_buffer_len = gunzip_outbuf_count;
-        } else { // Bit more complicated, append to end of output_buffer, realloc as necessary
-                int newlen = output_buffer_len + gunzip_outbuf_count;
-                if (newlen > output_buffer_size) {
-                        output_buffer = xrealloc(output_buffer, newlen); // Could free later, but as we now have the memory...
-                        //printf("Using %d byte output buffer\n", newlen);
-                        output_buffer_size = newlen;
-                }
-                memcpy(output_buffer + output_buffer_len, gunzip_window, gunzip_outbuf_count);
-                output_buffer_len += gunzip_outbuf_count;
-        }
-        
-        gunzip_bytes_out += gunzip_outbuf_count;
-        gunzip_outbuf_count = 0;
-}
-
 /*
  * inflate (decompress) the codes in a deflated (compressed) block.
  * Return an error code or zero if it all goes ok.
@@ -468,7 +434,7 @@ static int inflate_codes(huft_t * my_tl, huft_t * my_td, const unsigned int my_b
                 if ((e = (t = tl + ((unsigned) b & ml))->e) > 16)
                         do {
                                 if (e == 99) {
-                                        return 1;
+                                        error_msg_and_die("inflate_codes error 1");;
                                 }
                                 b >>= t->b;
                                 k -= t->b;
@@ -484,7 +450,7 @@ static int inflate_codes(huft_t * my_tl, huft_t * my_td, const unsigned int my_b
                                 gunzip_outbuf_count = (w);
                                 //flush_gunzip_window();
                                 w = 0;
-                                return -1;
+                                return 1; // We have a block to read
                         }
                 } else {                /* it's an EOB or a length */
 
@@ -504,7 +470,7 @@ static int inflate_codes(huft_t * my_tl, huft_t * my_td, const unsigned int my_b
                         if ((e = (t = td + ((unsigned) b & md))->e) > 16)
                                 do {
                                         if (e == 99)
-                                                return 1;
+                                                error_msg_and_die("inflate_codes error 2");;
                                         b >>= t->b;
                                         k -= t->b;
                                         e -= 16;
@@ -542,7 +508,7 @@ do_copy:		do {
                                         else resumeCopy = 0;
                                         //flush_gunzip_window();
                                         w = 0;
-                                        return -1;
+                                        return 1;
                                 }
                         } while (n);
                         resumeCopy = 0;
@@ -563,7 +529,7 @@ do_copy:		do {
         return 0;
 }
 
-int inflate_stored(int my_n, int my_b_stored, int my_k_stored, int setup)
+static int inflate_stored(int my_n, int my_b_stored, int my_k_stored, int setup)
 {
         static int n, b_stored, k_stored, w;
         if (setup) {
@@ -584,7 +550,7 @@ int inflate_stored(int my_n, int my_b_stored, int my_k_stored, int setup)
                         w = 0;
                         b_stored >>= 8;
                         k_stored -= 8;
-                        return -1; // Means more stuff 2do
+                        return 1; // We have a block
                 }
                 b_stored >>= 8;
                 k_stored -= 8;
@@ -866,51 +832,85 @@ static int inflate_block(int *e)
         }
         default:
                 /* bad block type */
-                error_msg("bad block type %d\n", t);
-                return 2;
+                error_msg_and_die("bad block type %d\n", t);
+        }
+}
+
+static void calculate_gunzip_crc(void)
+{
+        int n;
+        for (n = 0; n < gunzip_outbuf_count; n++) {
+                gunzip_crc = gunzip_crc_table[((int) gunzip_crc ^ (gunzip_window[n])) & 0xff] ^ (gunzip_crc >> 8);
+        }
+        gunzip_bytes_out += gunzip_outbuf_count;
+}
+
+static int inflate_get_next_window(void)
+{
+        static int needAnotherBlock = 1;
+        static int method = -1; // Method == -1 for stored, -2 for codes
+        static int e = 0;
+        
+        gunzip_outbuf_count = 0;
+
+        while(1) {
+                int ret;
+        
+                if (needAnotherBlock) {
+                        if(e) { calculate_gunzip_crc(); return 0; } // Last block
+                        method = inflate_block(&e);
+                        needAnotherBlock = 0;
+                }
+        
+                switch (method) {
+                        case -1:        ret = inflate_stored(0,0,0,0);
+                                        break;
+                        case -2:        ret = inflate_codes(0,0,0,0,0);
+                                        break;
+                        default:        error_msg_and_die("inflate error %d", method);
+                }
+
+                if (ret == 1) {
+                        calculate_gunzip_crc();
+                        return 1; // More data left
+                } else needAnotherBlock = 1; // End of that block
         }
 }
 
 /*
- * decompress an inflated entry
+ * User functions
  *
- * GLOBAL VARIABLES: gunzip_outbuf_count, bk, gunzip_bb, hufts, inptr
+ * read_gz, GZ_gzReadOpen, GZ_gzReadClose, inflate
  */
 
 extern ssize_t read_gz(int fd, void *buf, size_t count)
 {
-        static int e = 0;                               /* last block flag */
-        int r;                          /* result code */
-        unsigned h = 0;         /* maximum struct huft's malloc'ed */
-        ssize_t written = count;
-        static char *output_buffer_ptr = 0;
-
-        while (output_buffer_len == 0) { // We need more data
-                if (e) return 0; // No more data here!
-                gunzip_hufts = 0;
-                r = inflate_block(&e);
-                if (r == -1) { // Call inflate_stored while returning -1
-                        while(inflate_stored(0,0,0,0) == -1) flush_gunzip_window();
-                } else if (r == -2) { // Call inflate_codes while returning -1
-                        while(inflate_codes(0,0,0,0,0) == -1) flush_gunzip_window();
-                } else {
-                        error_msg_and_die("inflate error %d", r);
-                        return -1;
-                }
-                if (gunzip_hufts > h) {
-                        h = gunzip_hufts;
-                }
-                if (e) { // Ok finished uncompressing, get any buffered uncompressed data
-                        flush_gunzip_window();
-                }
-                output_buffer_ptr = output_buffer;
+        static int morebytes = 0, finished = 0;
+        
+        if (morebytes) {
+                int bytesRead = morebytes > count ? count : morebytes;
+                memcpy(buf, gunzip_window + (gunzip_outbuf_count - morebytes), bytesRead);
+                morebytes -= bytesRead;
+                return bytesRead;
+        } else if (finished) {
+                return 0;
+        } else if (count >= 0x8000) { // We can decompress direcly to the buffer, 32k at a time
+                // Could decompress to larger buffer, but it must be a power of 2, and calculating that is probably more expensive than the benefit
+                unsigned char *old_gunzip_window = gunzip_window; // Save old window
+                gunzip_window = buf;
+                if (inflate_get_next_window() == 0) finished = 1;
+                gunzip_window = old_gunzip_window; // Restore old window
+                return gunzip_outbuf_count;
+        } else { // Oh well, need to split up the gunzip_window
+                int bytesRead;
+                if (inflate_get_next_window() == 0) finished = 1;
+                morebytes = gunzip_outbuf_count;
+                bytesRead = morebytes > count ? count : morebytes;
+                memcpy(buf, gunzip_window, bytesRead);
+                morebytes -= bytesRead;
+                return bytesRead;
         }
-        if (count > output_buffer_len) written = output_buffer_len; // We're only giving them as much as we have!
-        memcpy(buf, output_buffer_ptr, written);
-        output_buffer_ptr += written;
-        output_buffer_len -= written;
-
-        return written;
+        
 }
 
 extern void GZ_gzReadOpen(int fd, void *unused, int nUnused)
@@ -919,7 +919,6 @@ extern void GZ_gzReadOpen(int fd, void *unused, int nUnused)
 
         /* Allocate all global buffers (for DYN_ALLOC option) */
         gunzip_window = xmalloc(gunzip_wsize);
-        output_buffer = xmalloc(gunzip_wsize);
         gunzip_outbuf_count = 0;
         gunzip_bytes_out = 0;
         gunzip_src_fd = fd;
@@ -938,7 +937,6 @@ extern void GZ_gzReadClose(void)
 {
         /* Cleanup */
         free(gunzip_window);
-        free(output_buffer);
         free(gunzip_crc_table);
 
         /* Store unused bytes in a global buffer so calling applets can access it */
@@ -953,11 +951,10 @@ extern void GZ_gzReadClose(void)
         }
 }
 
-extern int inflate(int in, int out)
+/*extern int inflate(int in, int out) // Useful for testing read_gz
 {
         char buf[8192];
         ssize_t nread, nwrote;
-        ssize_t total = 0;
 
         GZ_gzReadOpen(in, 0, 0);
         while(1) { // Robbed from copyfd.c
@@ -972,7 +969,23 @@ extern int inflate(int in, int out)
                         perror_msg("write");
                         return -1;
                 }
-                total += nwrote;
+        }
+        GZ_gzReadClose();
+        return 0;
+}*/
+
+extern int inflate(int in, int out)
+{
+        ssize_t nwrote;
+        GZ_gzReadOpen(in, 0, 0);
+        while(1) {
+                int ret = inflate_get_next_window();
+                nwrote = full_write(out, gunzip_window, gunzip_outbuf_count);
+                if (nwrote == -1) {
+                        perror_msg("write");
+                        return -1;
+                }
+                if (ret == 0) break;
         }
         GZ_gzReadClose();
         return 0;
diff --git a/archival/libunarchive/unzip.c b/archival/libunarchive/unzip.c
index 7ebbd0ee7..d8d5b77b1 100644
--- a/archival/libunarchive/unzip.c
+++ b/archival/libunarchive/unzip.c
@@ -14,6 +14,8 @@
  * General cleanup to better adhere to the style guide and make use of standard
  * busybox functions by Glenn McGrath <bug1@optushome.com.au>
  * 
+ * read_gz interface + associated hacking by Laurence Anderson
+ *
  * This program is free software; you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
  * the Free Software Foundation; either version 2 of the License, or
@@ -92,20 +94,15 @@ unsigned char *gunzip_in_buffer;
 /* gunzip_window size--must be a power of two, and
  *  at least 32K for zip's deflate method */
 static const int gunzip_wsize = 0x8000;
-static int output_buffer_size = 0x8000; // gunzip_wsize initially
 
 static unsigned char *gunzip_window;
 static unsigned int *gunzip_crc_table;
 unsigned int gunzip_crc;
 
-static unsigned char *output_buffer;
-static unsigned int output_buffer_len;
-
 /* If BMAX needs to be larger than 16, then h and x[] should be ulg. */
 #define BMAX 16 /* maximum bit length of any code (16 for explode) */
 #define N_MAX 288       /* maximum number of codes in any set */
 
-static unsigned int gunzip_hufts;       /* track memory usage */
 static unsigned int gunzip_bb;  /* bit buffer */
 static unsigned char gunzip_bk; /* bits in bit buffer */
 
@@ -343,7 +340,6 @@ static int huft_build(unsigned int *b, const unsigned int n,
                                 /* allocate and link in new table */
                                 q = (huft_t *) xmalloc((z + 1) * sizeof(huft_t));
 
-                                gunzip_hufts += z + 1;  /* track memory usage */
                                 *t = q + 1;     /* link to list for huft_free() */
                                 *(t = &(q->v.t)) = NULL;
                                 u[h] = ++q;     /* table starts after link */
@@ -395,36 +391,6 @@ static int huft_build(unsigned int *b, const unsigned int n,
         return y != 0 && g != 1;
 }
 
-/* ===========================================================================
- * Write the output gunzip_window gunzip_window[0..gunzip_outbuf_count-1] and update crc and gunzip_bytes_out.
- * (Used for the decompressed data only.)
- */
-static void flush_gunzip_window(void)
-{
-        int n;
-
-        for (n = 0; n < gunzip_outbuf_count; n++) {
-                gunzip_crc = gunzip_crc_table[((int) gunzip_crc ^ (gunzip_window[n])) & 0xff] ^ (gunzip_crc >> 8);
-        }
-
-        if (output_buffer_len == 0) { // Our buffer is empty -> straight memcpy
-                memcpy(output_buffer, gunzip_window, gunzip_outbuf_count);
-                output_buffer_len = gunzip_outbuf_count;
-        } else { // Bit more complicated, append to end of output_buffer, realloc as necessary
-                int newlen = output_buffer_len + gunzip_outbuf_count;
-                if (newlen > output_buffer_size) {
-                        output_buffer = xrealloc(output_buffer, newlen); // Could free later, but as we now have the memory...
-                        //printf("Using %d byte output buffer\n", newlen);
-                        output_buffer_size = newlen;
-                }
-                memcpy(output_buffer + output_buffer_len, gunzip_window, gunzip_outbuf_count);
-                output_buffer_len += gunzip_outbuf_count;
-        }
-        
-        gunzip_bytes_out += gunzip_outbuf_count;
-        gunzip_outbuf_count = 0;
-}
-
 /*
  * inflate (decompress) the codes in a deflated (compressed) block.
  * Return an error code or zero if it all goes ok.
@@ -468,7 +434,7 @@ static int inflate_codes(huft_t * my_tl, huft_t * my_td, const unsigned int my_b
                 if ((e = (t = tl + ((unsigned) b & ml))->e) > 16)
                         do {
                                 if (e == 99) {
-                                        return 1;
+                                        error_msg_and_die("inflate_codes error 1");;
                                 }
                                 b >>= t->b;
                                 k -= t->b;
@@ -484,7 +450,7 @@ static int inflate_codes(huft_t * my_tl, huft_t * my_td, const unsigned int my_b
                                 gunzip_outbuf_count = (w);
                                 //flush_gunzip_window();
                                 w = 0;
-                                return -1;
+                                return 1; // We have a block to read
                         }
                 } else {                /* it's an EOB or a length */
 
@@ -504,7 +470,7 @@ static int inflate_codes(huft_t * my_tl, huft_t * my_td, const unsigned int my_b
                         if ((e = (t = td + ((unsigned) b & md))->e) > 16)
                                 do {
                                         if (e == 99)
-                                                return 1;
+                                                error_msg_and_die("inflate_codes error 2");;
                                         b >>= t->b;
                                         k -= t->b;
                                         e -= 16;
@@ -542,7 +508,7 @@ do_copy:		do {
                                         else resumeCopy = 0;
                                         //flush_gunzip_window();
                                         w = 0;
-                                        return -1;
+                                        return 1;
                                 }
                         } while (n);
                         resumeCopy = 0;
@@ -563,7 +529,7 @@ do_copy:		do {
         return 0;
 }
 
-int inflate_stored(int my_n, int my_b_stored, int my_k_stored, int setup)
+static int inflate_stored(int my_n, int my_b_stored, int my_k_stored, int setup)
 {
         static int n, b_stored, k_stored, w;
         if (setup) {
@@ -584,7 +550,7 @@ int inflate_stored(int my_n, int my_b_stored, int my_k_stored, int setup)
                         w = 0;
                         b_stored >>= 8;
                         k_stored -= 8;
-                        return -1; // Means more stuff 2do
+                        return 1; // We have a block
                 }
                 b_stored >>= 8;
                 k_stored -= 8;
@@ -866,51 +832,85 @@ static int inflate_block(int *e)
         }
         default:
                 /* bad block type */
-                error_msg("bad block type %d\n", t);
-                return 2;
+                error_msg_and_die("bad block type %d\n", t);
+        }
+}
+
+static void calculate_gunzip_crc(void)
+{
+        int n;
+        for (n = 0; n < gunzip_outbuf_count; n++) {
+                gunzip_crc = gunzip_crc_table[((int) gunzip_crc ^ (gunzip_window[n])) & 0xff] ^ (gunzip_crc >> 8);
+        }
+        gunzip_bytes_out += gunzip_outbuf_count;
+}
+
+static int inflate_get_next_window(void)
+{
+        static int needAnotherBlock = 1;
+        static int method = -1; // Method == -1 for stored, -2 for codes
+        static int e = 0;
+        
+        gunzip_outbuf_count = 0;
+
+        while(1) {
+                int ret;
+        
+                if (needAnotherBlock) {
+                        if(e) { calculate_gunzip_crc(); return 0; } // Last block
+                        method = inflate_block(&e);
+                        needAnotherBlock = 0;
+                }
+        
+                switch (method) {
+                        case -1:        ret = inflate_stored(0,0,0,0);
+                                        break;
+                        case -2:        ret = inflate_codes(0,0,0,0,0);
+                                        break;
+                        default:        error_msg_and_die("inflate error %d", method);
+                }
+
+                if (ret == 1) {
+                        calculate_gunzip_crc();
+                        return 1; // More data left
+                } else needAnotherBlock = 1; // End of that block
         }
 }
 
 /*
- * decompress an inflated entry
+ * User functions
  *
- * GLOBAL VARIABLES: gunzip_outbuf_count, bk, gunzip_bb, hufts, inptr
+ * read_gz, GZ_gzReadOpen, GZ_gzReadClose, inflate
  */
 
 extern ssize_t read_gz(int fd, void *buf, size_t count)
 {
-        static int e = 0;                               /* last block flag */
-        int r;                          /* result code */
-        unsigned h = 0;         /* maximum struct huft's malloc'ed */
-        ssize_t written = count;
-        static char *output_buffer_ptr = 0;
-
-        while (output_buffer_len == 0) { // We need more data
-                if (e) return 0; // No more data here!
-                gunzip_hufts = 0;
-                r = inflate_block(&e);
-                if (r == -1) { // Call inflate_stored while returning -1
-                        while(inflate_stored(0,0,0,0) == -1) flush_gunzip_window();
-                } else if (r == -2) { // Call inflate_codes while returning -1
-                        while(inflate_codes(0,0,0,0,0) == -1) flush_gunzip_window();
-                } else {
-                        error_msg_and_die("inflate error %d", r);
-                        return -1;
-                }
-                if (gunzip_hufts > h) {
-                        h = gunzip_hufts;
-                }
-                if (e) { // Ok finished uncompressing, get any buffered uncompressed data
-                        flush_gunzip_window();
-                }
-                output_buffer_ptr = output_buffer;
+        static int morebytes = 0, finished = 0;
+        
+        if (morebytes) {
+                int bytesRead = morebytes > count ? count : morebytes;
+                memcpy(buf, gunzip_window + (gunzip_outbuf_count - morebytes), bytesRead);
+                morebytes -= bytesRead;
+                return bytesRead;
+        } else if (finished) {
+                return 0;
+        } else if (count >= 0x8000) { // We can decompress direcly to the buffer, 32k at a time
+                // Could decompress to larger buffer, but it must be a power of 2, and calculating that is probably more expensive than the benefit
+                unsigned char *old_gunzip_window = gunzip_window; // Save old window
+                gunzip_window = buf;
+                if (inflate_get_next_window() == 0) finished = 1;
+                gunzip_window = old_gunzip_window; // Restore old window
+                return gunzip_outbuf_count;
+        } else { // Oh well, need to split up the gunzip_window
+                int bytesRead;
+                if (inflate_get_next_window() == 0) finished = 1;
+                morebytes = gunzip_outbuf_count;
+                bytesRead = morebytes > count ? count : morebytes;
+                memcpy(buf, gunzip_window, bytesRead);
+                morebytes -= bytesRead;
+                return bytesRead;
         }
-        if (count > output_buffer_len) written = output_buffer_len; // We're only giving them as much as we have!
-        memcpy(buf, output_buffer_ptr, written);
-        output_buffer_ptr += written;
-        output_buffer_len -= written;
-
-        return written;
+        
 }
 
 extern void GZ_gzReadOpen(int fd, void *unused, int nUnused)
@@ -919,7 +919,6 @@ extern void GZ_gzReadOpen(int fd, void *unused, int nUnused)
 
         /* Allocate all global buffers (for DYN_ALLOC option) */
         gunzip_window = xmalloc(gunzip_wsize);
-        output_buffer = xmalloc(gunzip_wsize);
         gunzip_outbuf_count = 0;
         gunzip_bytes_out = 0;
         gunzip_src_fd = fd;
@@ -938,7 +937,6 @@ extern void GZ_gzReadClose(void)
 {
         /* Cleanup */
         free(gunzip_window);
-        free(output_buffer);
         free(gunzip_crc_table);
 
         /* Store unused bytes in a global buffer so calling applets can access it */
@@ -953,11 +951,10 @@ extern void GZ_gzReadClose(void)
         }
 }
 
-extern int inflate(int in, int out)
+/*extern int inflate(int in, int out) // Useful for testing read_gz
 {
         char buf[8192];
         ssize_t nread, nwrote;
-        ssize_t total = 0;
 
         GZ_gzReadOpen(in, 0, 0);
         while(1) { // Robbed from copyfd.c
@@ -972,7 +969,23 @@ extern int inflate(int in, int out)
                         perror_msg("write");
                         return -1;
                 }
-                total += nwrote;
+        }
+        GZ_gzReadClose();
+        return 0;
+}*/
+
+extern int inflate(int in, int out)
+{
+        ssize_t nwrote;
+        GZ_gzReadOpen(in, 0, 0);
+        while(1) {
+                int ret = inflate_get_next_window();
+                nwrote = full_write(out, gunzip_window, gunzip_outbuf_count);
+                if (nwrote == -1) {
+                        perror_msg("write");
+                        return -1;
+                }
+                if (ret == 0) break;
         }
         GZ_gzReadClose();
         return 0;