2 * Copyright (c) 2003-2005 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.
28 * Authors: Erik Hallnor
32 * LZSSCompression definitions.
37 #include "base/compression/lzss_compression.hh"
39 #include "base/misc.hh" //for fatal
42 LZSSCompression::findSubString(uint8_t *src
, int back
, int size
, uint16_t &L
,
46 int max_length
= size
- back
;
49 while (front
< back
) {
50 while (src
[front
] != src
[back
] && front
< back
) ++front
;
55 while (src
[front
+i
] == src
[back
+i
] && i
< max_length
) ++i
;
60 if (src
[front
+i
] != src
[back
+i
-1]) {
61 // can't find a longer substring until past this point.
70 LZSSCompression::emitByte(uint8_t *dest
, uint8_t byte
)
72 if ((byte
>> 5 & 0x7) == 0 || (byte
>> 5 & 0x7) == 7) {
73 // If the top 3 bits are the same, emit 00<6bits>
74 dest
[0] = byte
& 0x3f;
77 // emit 01XXXXXX <8 bits>
85 LZSSCompression::emitString(uint8_t *dest
, uint16_t P
, uint16_t L
)
87 // Emit 1<7P> <5P><3L> <8L>
88 dest
[0] = 1<<7 | (P
>> 5 & 0x7f);
89 dest
[1] = ((P
& 0x1f) << 3) | (L
>>8 & 0x3);
94 LZSSCompression::compress(uint8_t *dest
, uint8_t *src
, int size
)
97 fatal("Compression can only handle block sizes of 4096 bytes or less");
100 // Encode the first byte.
101 int dest_index
= emitByte(dest
, src
[0]);
108 while (i
< size
&& dest_index
< size
) {
111 if (dest_index
+3 >= size
) {
117 // Output the character
118 dest_index
+= emitByte(&dest
[dest_index
], src
[i
]);
122 findSubString(src
, i
, size
, L
, P
);
124 // Output the string reference
125 emitString(&dest
[dest_index
], P
, L
);
129 // Output the character
130 dest_index
+= emitByte(&dest
[dest_index
], src
[i
]);
135 if (dest_index
>= size
) {
136 // Have expansion instead of compression, just copy.
137 memcpy(dest
,src
,size
);
144 LZSSCompression::uncompress(uint8_t *dest
, uint8_t *src
, int size
)
149 if (src
[i
] & 1<<7 ) {
152 int start
= (src
[i
] & 0x3f)<<5 | ((src
[i
+1] >> 3) & 0x1f);
154 int len
= (src
[i
+1] & 0x07)<<8 | src
[i
+2];
156 for (int j
= start
; j
< start
+len
; ++j
) {
157 dest
[index
++] = dest
[j
];
160 // We have a character
162 // Value is in the next byte
163 dest
[index
++] = src
[i
+1];
166 // just extend the lower 6 bits
167 dest
[index
++] = (src
[i
] & 0x3f) | ((src
[i
] & 1<<5) ? 0xC0 : 0);