diff options
author | Lisa Hsu <hsul@eecs.umich.edu> | 2004-05-11 01:15:18 -0400 |
---|---|---|
committer | Lisa Hsu <hsul@eecs.umich.edu> | 2004-05-11 01:15:18 -0400 |
commit | a5f90eba3bd2d96c6733a6ac9e8d03a9297fae6a (patch) | |
tree | 06662aecdd919aa0bafb0562fc646465dda5a901 /base/compression/lzss_compression.cc | |
parent | 3c7071a6be21fc0c87753758fc09ff28890edc99 (diff) | |
parent | 2cc4fd87eb643c81d37954cbf4a226e78ebd34bc (diff) | |
download | gem5-a5f90eba3bd2d96c6733a6ac9e8d03a9297fae6a.tar.xz |
first pass at merging m5 with linux
--HG--
extra : convert_revision : dfe23349b80ae3b34d3cb95c5734e01ef62f700e
Diffstat (limited to 'base/compression/lzss_compression.cc')
-rw-r--r-- | base/compression/lzss_compression.cc | 43 |
1 files changed, 24 insertions, 19 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); |