1/* 2 * Copyright (C) Matthieu Suiche 2008 3 * 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 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. 16 * 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. 20 * 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 31 * SUCH DAMAGE. 32 * 33 */ 34 35#include "replace.h" 36#include "lzxpress.h" 37 38 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)) 42 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)) \ 47)) 48#endif 49 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)) \ 56)) 57#endif 58 59ssize_t lzxpress_compress(const uint8_t *uncompressed, 60 uint32_t uncompressed_size, 61 uint8_t *compressed, 62 uint32_t max_compressed_size) 63{ 64 uint32_t uncompressed_pos, compressed_pos, byte_left; 65 uint32_t max_offset, best_offset; 66 int32_t offset; 67 uint32_t max_len, len, best_len; 68 const uint8_t *str1, *str2; 69 uint32_t indic; 70 uint8_t *indic_pos; 71 uint32_t indic_bit, nibble_index; 72 73 uint32_t metadata_size; 74 uint16_t metadata; 75 uint16_t *dest; 76 77 if (!uncompressed_size) { 78 return 0; 79 } 80 81 uncompressed_pos = 0; 82 indic = 0; 83 compressed_pos = sizeof(uint32_t); 84 indic_pos = &compressed[0]; 85 86 byte_left = uncompressed_size; 87 indic_bit = 0; 88 nibble_index = 0; 89 90 if (uncompressed_pos > XPRESS_BLOCK_SIZE) 91 return 0; 92 93 do { 94 bool found = false; 95 96 max_offset = uncompressed_pos; 97 98 str1 = &uncompressed[uncompressed_pos]; 99 100 best_len = 2; 101 best_offset = 0; 102 103 max_offset = MIN(0x1FFF, max_offset); 104 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]; 108 109 /* maximum len we can encode into metadata */ 110 max_len = MIN((255 + 15 + 7 + 3), byte_left); 111 112 for (len = 0; (len < max_len) && (str1[len] == str2[len]); len++); 113 114 /* 115 * We check if len is better than the value found before, including the 116 * sequence of identical bytes 117 */ 118 if (len > best_len) { 119 found = true; 120 best_len = len; 121 best_offset = offset; 122 } 123 } 124 125 if (found) { 126 metadata_size = 0; 127 dest = (uint16_t *)&compressed[compressed_pos]; 128 129 if (best_len < 10) { 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); 134 } else { 135 metadata = (uint16_t)(((best_offset - 1) << 3) | 7); 136 dest[metadata_size / sizeof(uint16_t)] = metadata; 137 metadata_size = sizeof(uint16_t); 138 139 if (best_len < (15 + 7 + 3)) { 140 /* Shared byte */ 141 if (!nibble_index) { 142 compressed[compressed_pos + metadata_size] = (best_len - (3 + 7)) & 0xF; 143 metadata_size += sizeof(uint8_t); 144 } else { 145 compressed[nibble_index] &= 0xF; 146 compressed[nibble_index] |= (best_len - (3 + 7)) * 16; 147 } 148 } else if (best_len < (3 + 7 + 15 + 255)) { 149 /* Shared byte */ 150 if (!nibble_index) { 151 compressed[compressed_pos + metadata_size] = 15; 152 metadata_size += sizeof(uint8_t); 153 } else { 154 compressed[nibble_index] &= 0xF; 155 compressed[nibble_index] |= (15 * 16); 156 } 157 158 /* Additionnal best_len */ 159 compressed[compressed_pos + metadata_size] = (best_len - (3 + 7 + 15)) & 0xFF; 160 metadata_size += sizeof(uint8_t); 161 } else { 162 /* Shared byte */ 163 if (!nibble_index) { 164 compressed[compressed_pos + metadata_size] |= 15; 165 metadata_size += sizeof(uint8_t); 166 } else { 167 compressed[nibble_index] |= 15 << 4; 168 } 169 170 /* Additionnal best_len */ 171 compressed[compressed_pos + metadata_size] = 255; 172 173 metadata_size += sizeof(uint8_t); 174 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); 178 } 179 } 180 181 indic |= 1 << (32 - ((indic_bit % 32) + 1)); 182 183 if (best_len > 9) { 184 if (nibble_index == 0) { 185 nibble_index = compressed_pos + sizeof(uint16_t); 186 } else { 187 nibble_index = 0; 188 } 189 } 190 191 compressed_pos += metadata_size; 192 uncompressed_pos += best_len; 193 byte_left -= best_len; 194 } else { 195 compressed[compressed_pos++] = uncompressed[uncompressed_pos++]; 196 byte_left--; 197 } 198 indic_bit++; 199 200 if ((indic_bit - 1) % 32 > (indic_bit % 32)) { 201 *(uint32_t *)indic_pos = indic; 202 indic = 0; 203 indic_pos = &compressed[compressed_pos]; 204 compressed_pos += sizeof(uint32_t); 205 } 206 } while (byte_left > 3); 207 208 do { 209 compressed[compressed_pos] = uncompressed[uncompressed_pos]; 210 indic_bit++; 211 212 uncompressed_pos++; 213 compressed_pos++; 214 if (((indic_bit - 1) % 32) > (indic_bit % 32)){ 215 *(uint32_t *)indic_pos = indic; 216 indic = 0; 217 indic_pos = &compressed[compressed_pos]; 218 compressed_pos += sizeof(uint32_t); 219 } 220 } while (uncompressed_pos < uncompressed_size); 221 222 if ((indic_bit % 32) > 0) { 223 for (; (indic_bit % 32) != 0; indic_bit++) 224 indic |= 0 << (32 - ((indic_bit % 32) + 1)); 225 226 *(uint32_t *)indic_pos = indic; 227 compressed_pos += sizeof(uint32_t); 228 } 229 230 return compressed_pos; 231} 232 233ssize_t lzxpress_decompress(const uint8_t *input, 234 uint32_t input_size, 235 uint8_t *output, 236 uint32_t max_output_size) 237{ 238 uint32_t output_index, input_index; 239 uint32_t indicator, indicator_bit; 240 uint32_t length; 241 uint32_t offset; 242 uint32_t nibble_index; 243 244 output_index = 0; 245 input_index = 0; 246 indicator = 0; 247 indicator_bit = 0; 248 length = 0; 249 offset = 0; 250 nibble_index = 0; 251 252 do { 253 if (indicator_bit == 0) { 254 indicator = PULL_LE_UINT32(input, input_index); 255 input_index += sizeof(uint32_t); 256 indicator_bit = 32; 257 } 258 indicator_bit--; 259 260 /* 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 264 */ 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); 269 } else { 270 length = PULL_LE_UINT16(input, input_index); 271 input_index += sizeof(uint16_t); 272 offset = length / 8; 273 length = length % 8; 274 275 if (length == 7) { 276 if (nibble_index == 0) { 277 nibble_index = input_index; 278 length = input[input_index] % 16; 279 input_index += sizeof(uint8_t); 280 } else { 281 length = input[nibble_index] / 16; 282 nibble_index = 0; 283 } 284 285 if (length == 15) { 286 length = input[input_index]; 287 input_index += sizeof(uint8_t); 288 if (length == 255) { 289 length = PULL_LE_UINT16(input, input_index); 290 input_index += sizeof(uint16_t); 291 length -= (15 + 7); 292 } 293 length += 15; 294 } 295 length += 7; 296 } 297 298 length += 3; 299 300 do { 301 if ((output_index >= max_output_size) || ((offset + 1) > output_index)) break; 302 303 output[output_index] = output[output_index - offset - 1]; 304 305 output_index += sizeof(uint8_t); 306 length -= sizeof(uint8_t); 307 } while (length != 0); 308 } 309 } while ((output_index < max_output_size) && (input_index < (input_size))); 310 311 return output_index; 312} 313