Merge ehallnor@zizzer:/bk/m5 into zazzer.eecs.umich.edu:/z/ehallnor/m5

--HG--
extra : convert_revision : d950120ed0f96421bb953a96db94fb4aecf2241d

2 files changed, 29 insertions, 23 deletions

diff --git a/base/compression/lzss_compression.cc b/base/compression/lzss_compression.cc
index 8f235b808..2f6c5d338 100644
--- a/base/compression/lzss_compression.cc
+++ b/base/compression/lzss_compression.cc
@@ -36,21 +36,32 @@
 
 #include "base/misc.hh" //for fatal
 
-int
-LZSSCompression::findSubString(uint8_t *src, int front, int back, int size)
+void
+LZSSCompression::findSubString(uint8_t *src, int back, int size, uint16_t &L,
+                               uint16_t &P)
 {
-    int subSize = 0;
-    int max_length = 2048;
-    if (size - back < max_length) {
-        max_length = size - back;
-    }
-    for (int i = 0; i < max_length; ++i) {
-        if (src[front+i] != src[back+i]) {
-            return subSize;
+    int front = 0;
+    int max_length = size - back;
+    L = 0;
+    P = back - 1;
+    while (front < back) {
+        while (src[front] != src[back] && front < back) ++front;
+        if (front >= back) {
+            return;
+        }
+        int i = 1;
+        while (src[front+i] == src[back+i] && i < max_length) ++i;
+        if (i >= L) {
+            L = i;
+            P = front;
+        }
+        if (src[front+i] != src[back+i-1]) {
+            // can't find a longer substring until past this point.
+            front += i;
+        } else {
+            ++front;
         }
-        ++subSize;
     }
-    return subSize;
 }
 
 int
@@ -106,13 +117,7 @@ LZSSCompression::compress(uint8_t *dest, uint8_t *src, int size)
             ++i;
             continue;
         }
-        for (int j = 0; j < i; ++j) {
-            int sub_size = findSubString(src, j, i, size);
-            if (sub_size >= L) {
-                L = sub_size;
-                P = j;
-            }
-        }
+        findSubString(src, i, size, L, P);
         if (L > 1) {
             // Output the string reference
             emitString(&dest[dest_index], P, L);
diff --git a/base/compression/lzss_compression.hh b/base/compression/lzss_compression.hh
index 755a52c92..9707a8aca 100644
--- a/base/compression/lzss_compression.hh
+++ b/base/compression/lzss_compression.hh
@@ -41,14 +41,15 @@
 class LZSSCompression
 {
     /**
-     * Finds the longest substrings that start at the given offsets.
+     * Finds the longest substring for the given offset.
      * @param src The source block that we search for substrings.
-     * @param front The smaller offset.
      * @param back The larger offset.
      * @param size The size of the source block.
-     * @return The size of the longest substring.
+     * @param L The length of the largest substring.
+     * @param P The starting offset of the largest substring.
      */
-    int findSubString(uint8_t *src, int front, int back, int size);
+    void findSubString(uint8_t *src, int back, int size, uint16_t &L,
+                       uint16_t &P);
 
     /**
      * Emit an encoded byte to the compressed data array. If the 2 high