2
* Copyright (C) Matthieu Suiche 2008
6
* Redistribution and use in source and binary forms, with or without
7
* modification, are permitted provided that the following conditions
10
* 1. Redistributions of source code must retain the above copyright
11
* notice, this list of conditions and the following disclaimer.
13
* 2. Redistributions in binary form must reproduce the above copyright
14
* notice, this list of conditions and the following disclaimer in the
15
* documentation and/or other materials provided with the distribution.
17
* 3. Neither the name of the author nor the names of its contributors
18
* may be used to endorse or promote products derived from this software
19
* without specific prior written permission.
21
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
22
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24
* ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
25
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
27
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
30
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
39
#define __BUF_POS_CONST(buf,ofs)(((const uint8_t *)buf)+(ofs))
40
#define __PULL_BYTE(buf,ofs) \
41
((uint8_t)((*__BUF_POS_CONST(buf,ofs)) & 0xFF))
43
#ifndef PULL_LE_UINT16
44
#define PULL_LE_UINT16(buf,ofs) ((uint16_t)( \
45
((uint16_t)(((uint16_t)(__PULL_BYTE(buf,(ofs)+0))) << 0)) | \
46
((uint16_t)(((uint16_t)(__PULL_BYTE(buf,(ofs)+1))) << 8)) \
50
#ifndef PULL_LE_UINT32
51
#define PULL_LE_UINT32(buf,ofs) ((uint32_t)( \
52
((uint32_t)(((uint32_t)(__PULL_BYTE(buf,(ofs)+0))) << 0)) | \
53
((uint32_t)(((uint32_t)(__PULL_BYTE(buf,(ofs)+1))) << 8)) | \
54
((uint32_t)(((uint32_t)(__PULL_BYTE(buf,(ofs)+2))) << 16)) | \
55
((uint32_t)(((uint32_t)(__PULL_BYTE(buf,(ofs)+3))) << 24)) \
59
ssize_t lzxpress_compress(const uint8_t *uncompressed,
60
uint32_t uncompressed_size,
62
uint32_t max_compressed_size)
64
uint32_t uncompressed_pos, compressed_pos, byte_left;
65
uint32_t max_offset, best_offset;
67
uint32_t max_len, len, best_len;
68
const uint8_t *str1, *str2;
71
uint32_t indic_bit, nibble_index;
73
uint32_t metadata_size;
77
if (!uncompressed_size) {
83
compressed_pos = sizeof(uint32_t);
84
indic_pos = &compressed[0];
86
byte_left = uncompressed_size;
90
if (uncompressed_pos > XPRESS_BLOCK_SIZE)
96
max_offset = uncompressed_pos;
98
str1 = &uncompressed[uncompressed_pos];
103
max_offset = MIN(0x1FFF, max_offset);
105
/* search for the longest match in the window for the lookahead buffer */
106
for (offset = 1; (uint32_t)offset <= max_offset; offset++) {
107
str2 = &str1[-offset];
109
/* maximum len we can encode into metadata */
110
max_len = MIN((255 + 15 + 7 + 3), byte_left);
112
for (len = 0; (len < max_len) && (str1[len] == str2[len]); len++);
115
* We check if len is better than the value found before, including the
116
* sequence of identical bytes
118
if (len > best_len) {
121
best_offset = offset;
127
dest = (uint16_t *)&compressed[compressed_pos];
130
/* Classical meta-data */
131
metadata = (uint16_t)(((best_offset - 1) << 3) | (best_len - 3));
132
dest[metadata_size / sizeof(uint16_t)] = metadata;
133
metadata_size += sizeof(uint16_t);
135
metadata = (uint16_t)(((best_offset - 1) << 3) | 7);
136
dest[metadata_size / sizeof(uint16_t)] = metadata;
137
metadata_size = sizeof(uint16_t);
139
if (best_len < (15 + 7 + 3)) {
142
compressed[compressed_pos + metadata_size] = (best_len - (3 + 7)) & 0xF;
143
metadata_size += sizeof(uint8_t);
145
compressed[nibble_index] &= 0xF;
146
compressed[nibble_index] |= (best_len - (3 + 7)) * 16;
148
} else if (best_len < (3 + 7 + 15 + 255)) {
151
compressed[compressed_pos + metadata_size] = 15;
152
metadata_size += sizeof(uint8_t);
154
compressed[nibble_index] &= 0xF;
155
compressed[nibble_index] |= (15 * 16);
158
/* Additionnal best_len */
159
compressed[compressed_pos + metadata_size] = (best_len - (3 + 7 + 15)) & 0xFF;
160
metadata_size += sizeof(uint8_t);
164
compressed[compressed_pos + metadata_size] |= 15;
165
metadata_size += sizeof(uint8_t);
167
compressed[nibble_index] |= 15 << 4;
170
/* Additionnal best_len */
171
compressed[compressed_pos + metadata_size] = 255;
173
metadata_size += sizeof(uint8_t);
175
compressed[compressed_pos + metadata_size] = (best_len - 3) & 0xFF;
176
compressed[compressed_pos + metadata_size + 1] = ((best_len - 3) >> 8) & 0xFF;
177
metadata_size += sizeof(uint16_t);
181
indic |= 1 << (32 - ((indic_bit % 32) + 1));
184
if (nibble_index == 0) {
185
nibble_index = compressed_pos + sizeof(uint16_t);
191
compressed_pos += metadata_size;
192
uncompressed_pos += best_len;
193
byte_left -= best_len;
195
compressed[compressed_pos++] = uncompressed[uncompressed_pos++];
200
if ((indic_bit - 1) % 32 > (indic_bit % 32)) {
201
*(uint32_t *)indic_pos = indic;
203
indic_pos = &compressed[compressed_pos];
204
compressed_pos += sizeof(uint32_t);
206
} while (byte_left > 3);
209
compressed[compressed_pos] = uncompressed[uncompressed_pos];
214
if (((indic_bit - 1) % 32) > (indic_bit % 32)){
215
*(uint32_t *)indic_pos = indic;
217
indic_pos = &compressed[compressed_pos];
218
compressed_pos += sizeof(uint32_t);
220
} while (uncompressed_pos < uncompressed_size);
222
if ((indic_bit % 32) > 0) {
223
for (; (indic_bit % 32) != 0; indic_bit++)
224
indic |= 0 << (32 - ((indic_bit % 32) + 1));
226
*(uint32_t *)indic_pos = indic;
227
compressed_pos += sizeof(uint32_t);
230
return compressed_pos;
233
ssize_t lzxpress_decompress(const uint8_t *input,
236
uint32_t max_output_size)
238
uint32_t output_index, input_index;
239
uint32_t indicator, indicator_bit;
242
uint32_t nibble_index;
253
if (indicator_bit == 0) {
254
indicator = PULL_LE_UINT32(input, input_index);
255
input_index += sizeof(uint32_t);
261
* check whether the bit specified by indicator_bit is set or not
262
* set in indicator. For example, if indicator_bit has value 4
263
* check whether the 4th bit of the value in indicator is set
265
if (((indicator >> indicator_bit) & 1) == 0) {
266
output[output_index] = input[input_index];
267
input_index += sizeof(uint8_t);
268
output_index += sizeof(uint8_t);
270
length = PULL_LE_UINT16(input, input_index);
271
input_index += sizeof(uint16_t);
276
if (nibble_index == 0) {
277
nibble_index = input_index;
278
length = input[input_index] % 16;
279
input_index += sizeof(uint8_t);
281
length = input[nibble_index] / 16;
286
length = input[input_index];
287
input_index += sizeof(uint8_t);
289
length = PULL_LE_UINT16(input, input_index);
290
input_index += sizeof(uint16_t);
301
if ((output_index >= max_output_size) || ((offset + 1) > output_index)) break;
303
output[output_index] = output[output_index - offset - 1];
305
output_index += sizeof(uint8_t);
306
length -= sizeof(uint8_t);
307
} while (length != 0);
309
} while ((output_index < max_output_size) && (input_index < (input_size)));