1 /*- 2 * SPDX-License-Identifier: BSD-2-Clause 3 * 4 * Copyright (c) 2000-2008 Marc Alexander Lehmann <schmorp@schmorp.de> 5 * 6 * Redistribution and use in source and binary forms, with or without modifica- 7 * tion, are permitted provided that the following conditions are met: 8 * 9 * 1. Redistributions of source code must retain the above copyright notice, 10 * this list of conditions and the following disclaimer. 11 * 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED 17 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MER- 18 * CHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO 19 * EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPE- 20 * CIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 21 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; 22 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 23 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTH- 24 * ERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 25 * OF THE POSSIBILITY OF SUCH DAMAGE. 26 * 27 * Alternatively, the contents of this file may be used under the terms of 28 * the GNU General Public License ("GPL") version 2 or any later version, 29 * in which case the provisions of the GPL are applicable instead of 30 * the above. If you wish to allow the use of your version of this file 31 * only under the terms of the GPL and not to allow others to use your 32 * version of this file under the BSD license, indicate your decision 33 * by deleting the provisions above and replace them with the notice 34 * and other provisions required by the GPL. If you do not delete the 35 * provisions above, a recipient may use your version of this file under 36 * either the BSD or the GPL. 37 */ 38 39 #include "lzf.h" 40 41 #define HSIZE (1 << (HLOG)) 42 43 /* 44 * don't play with this unless you benchmark! 45 * decompression is not dependent on the hash function 46 * the hashing function might seem strange, just believe me 47 * it works ;) 48 */ 49 #ifndef FRST 50 # define FRST(p) (((p[0]) << 8) | p[1]) 51 # define NEXT(v,p) (((v) << 8) | p[2]) 52 # if ULTRA_FAST 53 # define IDX(h) ((( h >> (3*8 - HLOG)) - h ) & (HSIZE - 1)) 54 # elif VERY_FAST 55 # define IDX(h) ((( h >> (3*8 - HLOG)) - h*5) & (HSIZE - 1)) 56 # else 57 # define IDX(h) ((((h ^ (h << 5)) >> (3*8 - HLOG)) - h*5) & (HSIZE - 1)) 58 # endif 59 #endif 60 /* 61 * IDX works because it is very similar to a multiplicative hash, e.g. 62 * ((h * 57321 >> (3*8 - HLOG)) & (HSIZE - 1)) 63 * the latter is also quite fast on newer CPUs, and compresses similarly. 64 * 65 * the next one is also quite good, albeit slow ;) 66 * (int)(cos(h & 0xffffff) * 1e6) 67 */ 68 69 #if 0 70 /* original lzv-like hash function, much worse and thus slower */ 71 # define FRST(p) (p[0] << 5) ^ p[1] 72 # define NEXT(v,p) ((v) << 5) ^ p[2] 73 # define IDX(h) ((h) & (HSIZE - 1)) 74 #endif 75 76 #define MAX_LIT (1 << 5) 77 #define MAX_OFF (1 << 13) 78 #define MAX_REF ((1 << 8) + (1 << 3)) 79 80 #if __GNUC__ >= 3 81 # define expect(expr,value) __builtin_expect ((expr),(value)) 82 # define inline inline 83 #else 84 # define expect(expr,value) (expr) 85 # define inline static 86 #endif 87 88 #define expect_false(expr) expect ((expr) != 0, 0) 89 #define expect_true(expr) expect ((expr) != 0, 1) 90 91 /* 92 * compressed format 93 * 94 * 000LLLLL <L+1> ; literal 95 * LLLooooo oooooooo ; backref L 96 * 111ooooo LLLLLLLL oooooooo ; backref L+7 97 * 98 */ 99 100 unsigned int 101 lzf_compress (const void *const in_data, unsigned int in_len, 102 void *out_data, unsigned int out_len 103 #if LZF_STATE_ARG 104 , LZF_STATE htab 105 #endif 106 ) 107 { 108 #if !LZF_STATE_ARG 109 LZF_STATE htab; 110 #endif 111 const u8 **hslot; 112 const u8 *ip = (const u8 *)in_data; 113 u8 *op = (u8 *)out_data; 114 const u8 *in_end = ip + in_len; 115 u8 *out_end = op + out_len; 116 const u8 *ref; 117 118 /* off requires a type wide enough to hold a general pointer difference. 119 * ISO C doesn't have that (size_t might not be enough and ptrdiff_t only 120 * works for differences within a single object). We also assume that no 121 * no bit pattern traps. Since the only platform that is both non-POSIX 122 * and fails to support both assumptions is windows 64 bit, we make a 123 * special workaround for it. 124 */ 125 #if defined (WIN32) && defined (_M_X64) 126 unsigned _int64 off; /* workaround for missing POSIX compliance */ 127 #else 128 unsigned long off; 129 #endif 130 unsigned int hval; 131 int lit; 132 133 if (!in_len || !out_len) 134 return 0; 135 136 #if INIT_HTAB 137 memset (htab, 0, sizeof (htab)); 138 # if 0 139 for (hslot = htab; hslot < htab + HSIZE; hslot++) 140 *hslot++ = ip; 141 # endif 142 #endif 143 144 lit = 0; op++; /* start run */ 145 146 hval = FRST (ip); 147 while (ip < in_end - 2) 148 { 149 hval = NEXT (hval, ip); 150 hslot = htab + IDX (hval); 151 ref = *hslot; *hslot = ip; 152 153 if (1 154 #if INIT_HTAB 155 && ref < ip /* the next test will actually take care of this, but this is faster */ 156 #endif 157 && (off = ip - ref - 1) < MAX_OFF 158 && ip + 4 < in_end 159 && ref > (const u8 *)in_data 160 #if STRICT_ALIGN 161 && ref[0] == ip[0] 162 && ref[1] == ip[1] 163 && ref[2] == ip[2] 164 #else 165 && *(const u16 *)ref == *(const u16 *)ip 166 && ref[2] == ip[2] 167 #endif 168 ) 169 { 170 /* match found at *ref++ */ 171 unsigned int len = 2; 172 unsigned int maxlen = in_end - ip - len; 173 maxlen = maxlen > MAX_REF ? MAX_REF : maxlen; 174 175 if (expect_false (op + 3 + 1 >= out_end)) /* first a faster conservative test */ 176 if (op - !lit + 3 + 1 >= out_end) /* second the exact but rare test */ 177 return 0; 178 179 op [- lit - 1] = lit - 1; /* stop run */ 180 op -= !lit; /* undo run if length is zero */ 181 182 for (;;) 183 { 184 if (expect_true (maxlen > 16)) 185 { 186 len++; if (ref [len] != ip [len]) break; 187 len++; if (ref [len] != ip [len]) break; 188 len++; if (ref [len] != ip [len]) break; 189 len++; if (ref [len] != ip [len]) break; 190 191 len++; if (ref [len] != ip [len]) break; 192 len++; if (ref [len] != ip [len]) break; 193 len++; if (ref [len] != ip [len]) break; 194 len++; if (ref [len] != ip [len]) break; 195 196 len++; if (ref [len] != ip [len]) break; 197 len++; if (ref [len] != ip [len]) break; 198 len++; if (ref [len] != ip [len]) break; 199 len++; if (ref [len] != ip [len]) break; 200 201 len++; if (ref [len] != ip [len]) break; 202 len++; if (ref [len] != ip [len]) break; 203 len++; if (ref [len] != ip [len]) break; 204 len++; if (ref [len] != ip [len]) break; 205 } 206 207 do 208 len++; 209 while (len < maxlen && ref[len] == ip[len]); 210 211 break; 212 } 213 214 len -= 2; /* len is now #octets - 1 */ 215 ip++; 216 217 if (len < 7) 218 { 219 *op++ = (off >> 8) + (len << 5); 220 } 221 else 222 { 223 *op++ = (off >> 8) + ( 7 << 5); 224 *op++ = len - 7; 225 } 226 227 *op++ = off; 228 lit = 0; op++; /* start run */ 229 230 ip += len + 1; 231 232 if (expect_false (ip >= in_end - 2)) 233 break; 234 235 #if ULTRA_FAST || VERY_FAST 236 --ip; 237 # if VERY_FAST && !ULTRA_FAST 238 --ip; 239 # endif 240 hval = FRST (ip); 241 242 hval = NEXT (hval, ip); 243 htab[IDX (hval)] = ip; 244 ip++; 245 246 # if VERY_FAST && !ULTRA_FAST 247 hval = NEXT (hval, ip); 248 htab[IDX (hval)] = ip; 249 ip++; 250 # endif 251 #else 252 ip -= len + 1; 253 254 do 255 { 256 hval = NEXT (hval, ip); 257 htab[IDX (hval)] = ip; 258 ip++; 259 } 260 while (len--); 261 #endif 262 } 263 else 264 { 265 /* one more literal byte we must copy */ 266 if (expect_false (op >= out_end)) 267 return 0; 268 269 lit++; *op++ = *ip++; 270 271 if (expect_false (lit == MAX_LIT)) 272 { 273 op [- lit - 1] = lit - 1; /* stop run */ 274 lit = 0; op++; /* start run */ 275 } 276 } 277 } 278 279 if (op + 3 > out_end) /* at most 3 bytes can be missing here */ 280 return 0; 281 282 while (ip < in_end) 283 { 284 lit++; *op++ = *ip++; 285 286 if (expect_false (lit == MAX_LIT)) 287 { 288 op [- lit - 1] = lit - 1; /* stop run */ 289 lit = 0; op++; /* start run */ 290 } 291 } 292 293 op [- lit - 1] = lit - 1; /* end run */ 294 op -= !lit; /* undo run if length is zero */ 295 296 return op - (u8 *)out_data; 297 } 298 299 #if AVOID_ERRNO 300 # define SET_ERRNO(n) 301 #else 302 # include <errno.h> 303 # define SET_ERRNO(n) errno = (n) 304 #endif 305 306 #if (__i386 || __amd64) && __GNUC__ >= 3 307 # define lzf_movsb(dst, src, len) \ 308 asm ("rep movsb" \ 309 : "=D" (dst), "=S" (src), "=c" (len) \ 310 : "0" (dst), "1" (src), "2" (len)); 311 #endif 312 313 unsigned int 314 lzf_decompress (const void *const in_data, unsigned int in_len, 315 void *out_data, unsigned int out_len) 316 { 317 u8 const *ip = (const u8 *)in_data; 318 u8 *op = (u8 *)out_data; 319 u8 const *const in_end = ip + in_len; 320 u8 *const out_end = op + out_len; 321 322 do 323 { 324 unsigned int ctrl = *ip++; 325 326 if (ctrl < (1 << 5)) /* literal run */ 327 { 328 ctrl++; 329 330 if (op + ctrl > out_end) 331 { 332 SET_ERRNO (E2BIG); 333 return 0; 334 } 335 336 #if CHECK_INPUT 337 if (ip + ctrl > in_end) 338 { 339 SET_ERRNO (EINVAL); 340 return 0; 341 } 342 #endif 343 344 #ifdef lzf_movsb 345 lzf_movsb (op, ip, ctrl); 346 #else 347 do 348 *op++ = *ip++; 349 while (--ctrl); 350 #endif 351 } 352 else /* back reference */ 353 { 354 unsigned int len = ctrl >> 5; 355 356 u8 *ref = op - ((ctrl & 0x1f) << 8) - 1; 357 358 #if CHECK_INPUT 359 if (ip >= in_end) 360 { 361 SET_ERRNO (EINVAL); 362 return 0; 363 } 364 #endif 365 if (len == 7) 366 { 367 len += *ip++; 368 #if CHECK_INPUT 369 if (ip >= in_end) 370 { 371 SET_ERRNO (EINVAL); 372 return 0; 373 } 374 #endif 375 } 376 377 ref -= *ip++; 378 379 if (op + len + 2 > out_end) 380 { 381 SET_ERRNO (E2BIG); 382 return 0; 383 } 384 385 if (ref < (u8 *)out_data) 386 { 387 SET_ERRNO (EINVAL); 388 return 0; 389 } 390 391 #ifdef lzf_movsb 392 len += 2; 393 lzf_movsb (op, ref, len); 394 #else 395 *op++ = *ref++; 396 *op++ = *ref++; 397 398 do 399 *op++ = *ref++; 400 while (--len); 401 #endif 402 } 403 } 404 while (ip < in_end); 405 406 return op - (u8 *)out_data; 407 } 408 409