Fix up LZ77 compression code and prepare v1.0.3 v1.0.3
authorEric Biggers <ebiggers3@gmail.com>
Tue, 11 Sep 2012 01:01:29 +0000 (20:01 -0500)
committerEric Biggers <ebiggers3@gmail.com>
Tue, 11 Sep 2012 01:50:36 +0000 (20:50 -0500)
NEWS
README
TODO
configure.ac
src/lz.c
src/lzx-comp.c
src/lzx-decomp.c

diff --git a/NEWS b/NEWS
index d2d336c7749f12840e3de64887c92d8b6c4f7563..820cd79ecaf20bbac48536a4f85bd4d0ab584904 100644 (file)
--- a/NEWS
+++ b/NEWS
@@ -1,5 +1,11 @@
 Only the most important changes more recent than version 0.6 are noted here.
 
+Version 1.0.3:
+       LZX and XPRESS compression improvements.
+
+       Fixed calculation of Directory Count, File Count, Total Bytes, and Hard
+       Link Bytes of the WIM.
+
 Version 1.0.2:
        Fixed bug when capturing NTFS file with multiple named data streams.
 
diff --git a/README b/README
index 8e6d401a9b08e70521d984ff73e9ea80a6ec7ed3..0f15a36fe4279c2a034d4c1dda5bcbef899d1ecf 100644 (file)
--- a/README
+++ b/README
@@ -1,6 +1,6 @@
                                   WIMLIB                                    
 
-This is wimlib version 1.0.2 (September 2012).  wimlib can be used to read,
+This is wimlib version 1.0.3 (September 2012).  wimlib can be used to read,
 write, and mount files in the Windows Imaging Format (WIM files).  These
 files are normally created by using the `imagex.exe' utility on Windows,
 but this library provides a free implementation of imagex for UNIX-based
@@ -75,6 +75,33 @@ details.
 image of Windows PE that can be put on a CD or USB drive, or published on a
 server for PXE booting.  See the main page `doc/mkwinpeiso.1' for more details.
 
+                              COMPRESSION RATIO
+
+wimlib can create XPRESS or LZX compressed WIM archives.  As of wimlib v1.0.3,
+the XPRESS compression ratio is slightly better than that provided by
+Microsoft's software, while the LZX compression ratio is approaching that of
+Microsoft's software but is not quite there yet.  Running time is as good as or
+better than Microsoft's software.
+
+The following tables compare the compression ratio and performance for creating
+a compressed Windows PE image (disk usage of about 524 MB, uncompressed WIM size
+361 MB):
+
+       Table 1. WIM size
+
+                                       XPRESS Compression      LZX Compression
+       wimlib imagex (v1.0.2):         145,283,871 bytes       139,288,293 bytes
+       wimlib imagex (v1.0.3):         139,288,293 bytes       131,379,869 bytes
+       Microsoft imagex.exe:           140,406,981 bytes       127,249,176 bytes
+
+       Table 2. Time to create WIM
+
+                                       XPRESS Compression      LZX Compression
+       wimlib imagex (v1.0.2):         18 sec                  49 sec
+       wimlib imagex (v1.0.3):         19 sec                  30 sec
+       Microsoft imagex.exe:           25 sec                  89 sec
+
+
                                  DEPENDENCIES
 
 * libxml2
diff --git a/TODO b/TODO
index 16538e77b175b2fd2572bae6f6883ef083d233ff..36ab8e6258d6959b20e8280ac9bfd803704ce1d1 100644 (file)
--- a/TODO
+++ b/TODO
@@ -1,4 +1,5 @@
 - Fix bugs
 - Add more test cases
 - Implement LZX block splitting to improve compression ratio
+- Implement multi-threaded compression
 - Improve performance of large directories in mounted WIMs.
index d761ec8196f1f7e565868871c80e1279ebbc0fe5..6ccb01551fbfee8d5fd7eea6ab96b358df6e4378 100644 (file)
@@ -1,4 +1,4 @@
-AC_INIT([wimlib], [1.0.2], [ebiggers3@gmail.com])
+AC_INIT([wimlib], [1.0.3], [ebiggers3@gmail.com])
 AC_CONFIG_SRCDIR([src/wim.c])
 AC_CONFIG_MACRO_DIR([m4])
 AC_CONFIG_AUX_DIR([build-aux])
index 93d07f0d386ec2c311393f858aa4b4d37a076d1d..ddf2017aac2270a9d56db13a157d18fc7c182e86 100644 (file)
--- a/src/lz.c
+++ b/src/lz.c
 #include "comp.h"
 #include <string.h>
 
+#define LZ_MIN_MATCH 3
+
 #define HASH_BITS      15
 #define HASH_SIZE      (1 << HASH_BITS)
 #define HASH_MASK      (HASH_SIZE - 1)
-#define HASH_SHIFT     ((HASH_BITS + 2) /  3)
+
+#if LZ_MIN_MATCH == 2
+#      define HASH_SHIFT       8
+#elif LZ_MIN_MATCH == 3
+#      define HASH_SHIFT       5
+#else
+#error "Invalid LZ_MIN_MATCH"
+#endif
 
 /* Hash function, based on code from zlib.  This function will update and return
  * the hash value @hash for the string ending on the additional input character
@@ -64,7 +73,7 @@ static inline uint update_hash(uint hash, u8 c)
 static inline uint insert_string(u16 hash_tab[], u16 prev_tab[], 
                                 const u8 window[], uint str_pos, uint hash)
 {
-       hash = update_hash(hash, window[str_pos + 2]);
+       hash = update_hash(hash, window[str_pos + LZ_MIN_MATCH - 1]);
        prev_tab[str_pos] = hash_tab[hash];
        hash_tab[hash] = str_pos;
        return hash;
@@ -108,7 +117,7 @@ static uint longest_match(const u8 window[], uint bytes_remaining,
 
        uint nice_match = min(params->nice_match, bytes_remaining);
 
-       const u8 *strend = scan + params->max_match;
+       const u8 *strend = scan + min(params->max_match, bytes_remaining);
 
        u8 scan_end1 = scan[best_len - 1];
        u8 scan_end = scan[best_len];
@@ -121,42 +130,39 @@ static uint longest_match(const u8 window[], uint bytes_remaining,
        do {
                match = &window[cur_match];
 
-
-               /* Skip to next match if the match length cannot increase
-                * or if the match length is less than 2.  Note that the checks below
-                * for insufficient lookahead only occur occasionally for performance
-                * reasons.  Therefore uninitialized memory will be accessed, and
-                * conditional jumps will be made that depend on those values.
-                * However the length of the match is limited to the lookahead, so
-                * the output of deflate is not affected by the uninitialized values.
+               /* Skip to next match if the match length cannot increase or if
+                * the match length is less than 2.  Note that the checks below
+                * for insufficient lookahead only occur occasionally for
+                * performance reasons.  Therefore uninitialized memory will be
+                * accessed, and conditional jumps will be made that depend on
+                * those values.  However the length of the match is limited to
+                * the lookahead, so the output of deflate is not affected by
+                * the uninitialized values.
                 */
 
-               if (match[best_len]   != scan_end  ||
-                       match[best_len-1] != scan_end1 ||
-                       *match                  != *scan         ||
-                       *++match                  != scan[1])     continue;
+               if (match[best_len] != scan_end
+                   || match[best_len - 1] != scan_end1
+                   || *match != *scan
+                   || *++match != scan[1])
+                       continue;
+               scan++;
 
-               /* The check at best_len-1 can be removed because it will be made
-                * again later. (This heuristic is not always a win.)
-                * It is not necessary to compare scan[2] and match[2] since they
-                * are always equal when the other bytes match, given that
-                * the hash keys are equal and that HASH_BITS >= 8.
-                */
-               scan += 2, match++;
-
-               wimlib_assert(*scan == *match);
+       #if 0
+               do {
+               } while (scan < strend && *++match == *++scan);
+       #else
 
-               /* We check for insufficient lookahead only every 8th comparison;
-                * the 256th check will be made at strstart+258.  */
                do {
-               } while (*++scan == *++match && *++scan == *++match &&
-                                *++scan == *++match && *++scan == *++match &&
-                                *++scan == *++match && *++scan == *++match &&
-                                *++scan == *++match && *++scan == *++match &&
-                                scan < strend);
+               } while (
+                        *++match == *++scan && *++match == *++scan &&
+                        *++match == *++scan && *++match == *++scan &&
+                        *++match == *++scan && *++match == *++scan &&
+                        *++match == *++scan && *++match == *++scan &&
+                        scan < strend);
+       #endif
+               len = match - &window[cur_match];
 
-               len = params->max_match - (int)(strend - scan);
-               scan = strend - params->max_match;
+               scan = &window[strstart];
 
                if (len > best_len) {
                        match_start = cur_match;
@@ -166,8 +172,7 @@ static uint longest_match(const u8 window[], uint bytes_remaining,
                        scan_end1  = scan[best_len - 1];
                        scan_end   = scan[best_len];
                }
-               cur_match = prev_tab[cur_match];
-       } while (--chain_len != 0 && cur_match != 0);
+       } while (--chain_len != 0 && (cur_match = prev_tab[cur_match]) != 0);
        *match_start_ret = match_start;
        return min(min(best_len, bytes_remaining), params->max_match);
 }
@@ -235,8 +240,8 @@ uint lz_analyze_block(const u8 uncompressed_data[], uint uncompressed_len,
                 * hash bucket, or 0 if there is no such string */
                if (uncompressed_len - cur_input_pos >= params->min_match) {
                        hash = insert_string(hash_tab, prev_tab, 
-                                               uncompressed_data, 
-                                               cur_input_pos, hash);
+                                            uncompressed_data, 
+                                            cur_input_pos, hash);
                        hash_head = prev_tab[cur_input_pos];
                } else {
                        hash_head = 0;
@@ -254,16 +259,14 @@ uint lz_analyze_block(const u8 uncompressed_data[], uint uncompressed_len,
                         * avoid a match of the string with itself at the start
                         * of the input file).  */
                        match_len = longest_match(uncompressed_data, 
-                                               uncompressed_len - cur_input_pos,
-                                               cur_input_pos, prev_tab, 
-                                               hash_head, prev_len,
-                                               &match_start, params);
+                                                 uncompressed_len - cur_input_pos,
+                                                 cur_input_pos, prev_tab, 
+                                                 hash_head, prev_len,
+                                                 &match_start, params);
 
-                       if (match_len == params->min_match && 
-                               cur_input_pos - match_start > params->too_far) 
-                       {
+                       if (match_len == params->min_match &&
+                            cur_input_pos - match_start > params->too_far)
                                match_len = params->min_match - 1;
-                       }
                }
 
                /* If there was a match at the previous step and the current
@@ -280,9 +283,9 @@ uint lz_analyze_block(const u8 uncompressed_data[], uint uncompressed_len,
                                        /*prev_len);*/
 
                        match = (*record_match)(cur_input_pos - 1 - prev_start, 
-                                                       prev_len, 
-                                                       record_match_arg1,
-                                                       record_match_arg2);
+                                               prev_len, 
+                                               record_match_arg1,
+                                               record_match_arg2);
 
                        match_tab[cur_match_pos++] = match;
 
@@ -291,17 +294,21 @@ uint lz_analyze_block(const u8 uncompressed_data[], uint uncompressed_len,
                         * enough lookahead, the last two strings are not inserted in
                         * the hash table.
                         */
-                       prev_len -= 2;
-
-                       do {
-                               if (++cur_input_pos <= max_insert) {
-                                       hash = insert_string(hash_tab, prev_tab,
-                                                               uncompressed_data,
-                                                               cur_input_pos,
-                                                               hash);
-                               }
-                       } while (--prev_len != 0);
-
+#if LZ_MIN_MATCH == 2
+                       if (prev_len >= 3)
+#endif
+                       {
+                               prev_len -= 2;
+
+                               do {
+                                       if (++cur_input_pos <= max_insert) {
+                                               hash = insert_string(hash_tab, prev_tab,
+                                                                    uncompressed_data,
+                                                                    cur_input_pos,
+                                                                    hash);
+                                       }
+                               } while (--prev_len != 0);
+                       }
                        match_available = false;
                        match_len = params->min_match - 1;
                } else if (match_available) {
index bf120f58730e5de7798d8fdbbb4b710f5ece439a..8267a2eaece40d28187adee2c114a953f2ebe825 100644 (file)
@@ -599,7 +599,11 @@ static void do_call_insn_preprocessing(u8 uncompressed_data[],
 
 
 static const struct lz_params lzx_lz_params = {
+
+        /* LZX_MIN_MATCH == 2, but 2-character matches are rarely useful; the
+         * minimum match for compression is set to 3 instead. */
        .min_match      = 3,
+
        .max_match      = LZX_MAX_MATCH,
        .good_match     = LZX_MAX_MATCH,
        .nice_match     = LZX_MAX_MATCH,
index 8aa0b755cb2083fc8d97311733e3c60848cb8428..d598d941c1d49bb0c2fef2c6c4b44ba26de4636f 100644 (file)
@@ -626,8 +626,21 @@ static int lzx_decode_match(int main_element, int block_type,
                return -1;
        }
 
+#if 0
+       printf("Match: src %u, dst %u, len %u\n", match_src - window,
+                                               match_dest - window,
+                                               match_len);
+       putchar('|');
+       for (i = 0; i < match_len; i++) {
+               match_dest[i] = match_src[i];
+               putchar(match_src[i]);
+       }
+       putchar('|');
+       putchar('\n');
+#else
        for (i = 0; i < match_len; i++)
                match_dest[i] = match_src[i];
+#endif
 
        return match_len;
 }