summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorErik Hallnor <ehallnor@umich.edu>2004-03-24 04:41:27 -0500
committerErik Hallnor <ehallnor@umich.edu>2004-03-24 04:41:27 -0500
commit6cb02394c07b432b700762bc6c5c43968fbf8920 (patch)
tree617326c75b2aebad8d00362f604cc65cb565451b
parent5e3b1f09c89ac962fd8781d4c582fc709deee57b (diff)
parent81882c0d10ee7a29181eea89ab56953049c86e00 (diff)
downloadgem5-6cb02394c07b432b700762bc6c5c43968fbf8920.tar.xz
Merge ehallnor@zizzer:/bk/m5 into zazzer.eecs.umich.edu:/z/ehallnor/m5
--HG-- extra : convert_revision : d950120ed0f96421bb953a96db94fb4aecf2241d
-rw-r--r--base/compression/lzss_compression.cc43
-rw-r--r--base/compression/lzss_compression.hh9
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