2 * Copyright (c) 2003-2004 The Regents of The University of Michigan
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are
7 * met: redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer;
9 * redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution;
12 * neither the name of the copyright holders nor the names of its
13 * contributors may be used to endorse or promote products derived from
14 * this software without specific prior written permission.
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 * LZSSCompression definitions.
35 #include "base/compression/lzss_compression.hh"
37 #include "base/misc.hh" //for fatal
40 LZSSCompression::findSubString(uint8_t *src
, int back
, int size
, uint16_t &L
,
44 int max_length
= size
- back
;
47 while (front
< back
) {
48 while (src
[front
] != src
[back
] && front
< back
) ++front
;
53 while (src
[front
+i
] == src
[back
+i
] && i
< max_length
) ++i
;
58 if (src
[front
+i
] != src
[back
+i
-1]) {
59 // can't find a longer substring until past this point.
68 LZSSCompression::emitByte(uint8_t *dest
, uint8_t byte
)
70 if ((byte
>> 5 & 0x7) == 0 || (byte
>> 5 & 0x7) == 7) {
71 // If the top 3 bits are the same, emit 00<6bits>
72 dest
[0] = byte
& 0x3f;
75 // emit 01XXXXXX <8 bits>
83 LZSSCompression::emitString(uint8_t *dest
, uint16_t P
, uint16_t L
)
85 // Emit 1<7P> <5P><3L> <8L>
86 dest
[0] = 1<<7 | (P
>> 5 & 0x7f);
87 dest
[1] = ((P
& 0x1f) << 3) | (L
>>8 & 0x3);
92 LZSSCompression::compress(uint8_t *dest
, uint8_t *src
, int size
)
95 fatal("Compression can only handle block sizes of 4096 bytes or less");
98 // Encode the first byte.
99 int dest_index
= emitByte(dest
, src
[0]);
106 while (i
< size
&& dest_index
< size
) {
109 if (dest_index
+3 >= size
) {
115 // Output the character
116 dest_index
+= emitByte(&dest
[dest_index
], src
[i
]);
120 findSubString(src
, i
, size
, L
, P
);
122 // Output the string reference
123 emitString(&dest
[dest_index
], P
, L
);
127 // Output the character
128 dest_index
+= emitByte(&dest
[dest_index
], src
[i
]);
133 if (dest_index
>= size
) {
134 // Have expansion instead of compression, just copy.
135 memcpy(dest
,src
,size
);
142 LZSSCompression::uncompress(uint8_t *dest
, uint8_t *src
, int size
)
147 if (src
[i
] & 1<<7 ) {
150 int start
= (src
[i
] & 0x3f)<<5 | ((src
[i
+1] >> 3) & 0x1f);
152 int len
= (src
[i
+1] & 0x07)<<8 | src
[i
+2];
154 for (int j
= start
; j
< start
+len
; ++j
) {
155 dest
[index
++] = dest
[j
];
158 // We have a character
160 // Value is in the next byte
161 dest
[index
++] = src
[i
+1];
164 // just extend the lower 6 bits
165 dest
[index
++] = (src
[i
] & 0x3f) | ((src
[i
] & 1<<5) ? 0xC0 : 0);