sdefl.h (28019B)
1 /*# Small Deflate 2 `sdefl` is a small bare bone lossless compression library in ANSI C (ISO C90) 3 which implements the Deflate (RFC 1951) compressed data format specification standard. 4 It is mainly tuned to get as much speed and compression ratio from as little code 5 as needed to keep the implementation as concise as possible. 6 7 ## Features 8 - Portable single header and source file duo written in ANSI C (ISO C90) 9 - Dual license with either MIT or public domain 10 - Small implementation 11 - Deflate: 525 LoC 12 - Inflate: 320 LoC 13 - Webassembly: 14 - Deflate ~3.7 KB (~2.2KB compressed) 15 - Inflate ~3.6 KB (~2.2KB compressed) 16 17 ## Usage: 18 This file behaves differently depending on what symbols you define 19 before including it. 20 21 Header-File mode: 22 If you do not define `SDEFL_IMPLEMENTATION` before including this file, it 23 will operate in header only mode. In this mode it declares all used structs 24 and the API of the library without including the implementation of the library. 25 26 Implementation mode: 27 If you define `SDEFL_IMPLEMENTATION` before including this file, it will 28 compile the implementation . Make sure that you only include 29 this file implementation in *one* C or C++ file to prevent collisions. 30 31 ### Benchmark 32 33 | Compressor name | Compression| Decompress.| Compr. size | Ratio | 34 | ------------------------| -----------| -----------| ----------- | ----- | 35 | miniz 1.0 -1 | 122 MB/s | 208 MB/s | 48510028 | 48.51 | 36 | miniz 1.0 -6 | 27 MB/s | 260 MB/s | 36513697 | 36.51 | 37 | miniz 1.0 -9 | 23 MB/s | 261 MB/s | 36460101 | 36.46 | 38 | zlib 1.2.11 -1 | 72 MB/s | 307 MB/s | 42298774 | 42.30 | 39 | zlib 1.2.11 -6 | 24 MB/s | 313 MB/s | 36548921 | 36.55 | 40 | zlib 1.2.11 -9 | 20 MB/s | 314 MB/s | 36475792 | 36.48 | 41 | sdefl 1.0 -0 | 127 MB/s | 355 MB/s | 40004116 | 39.88 | 42 | sdefl 1.0 -1 | 111 MB/s | 413 MB/s | 38940674 | 38.82 | 43 | sdefl 1.0 -5 | 45 MB/s | 436 MB/s | 36577183 | 36.46 | 44 | sdefl 1.0 -7 | 38 MB/s | 432 MB/s | 36523781 | 36.41 | 45 | libdeflate 1.3 -1 | 147 MB/s | 667 MB/s | 39597378 | 39.60 | 46 | libdeflate 1.3 -6 | 69 MB/s | 689 MB/s | 36648318 | 36.65 | 47 | libdeflate 1.3 -9 | 13 MB/s | 672 MB/s | 35197141 | 35.20 | 48 | libdeflate 1.3 -12 | 8.13 MB/s | 670 MB/s | 35100568 | 35.10 | 49 50 ### Compression 51 Results on the [Silesia compression corpus](http://sun.aei.polsl.pl/~sdeor/index.php?page=silesia): 52 53 | File | Original | `sdefl 0` | `sdefl 5` | `sdefl 7` | 54 | --------| -----------| -------------| ---------- | ------------| 55 | dickens | 10.192.446 | 4,260,187 | 3,845,261 | 3,833,657 | 56 | mozilla | 51.220.480 | 20,774,706 | 19,607,009 | 19,565,867 | 57 | mr | 9.970.564 | 3,860,531 | 3,673,460 | 3,665,627 | 58 | nci | 33.553.445 | 4,030,283 | 3,094,526 | 3,006,075 | 59 | ooffice | 6.152.192 | 3,320,063 | 3,186,373 | 3,183,815 | 60 | osdb | 10.085.684 | 3,919,646 | 3,649,510 | 3,649,477 | 61 | reymont | 6.627.202 | 2,263,378 | 1,857,588 | 1,827,237 | 62 | samba | 21.606.400 | 6,121,797 | 5,462,670 | 5,450,762 | 63 | sao | 7.251.944 | 5,612,421 | 5,485,380 | 5,481,765 | 64 | webster | 41.458.703 | 13,972,648 | 12,059,432 | 11,991,421 | 65 | xml | 5.345.280 | 886,620 | 674,009 | 662,141 | 66 | x-ray | 8.474.240 | 6,304,655 | 6,244,779 | 6,244,779 | 67 68 ## License 69 ``` 70 ------------------------------------------------------------------------------ 71 This software is available under 2 licenses -- choose whichever you prefer. 72 ------------------------------------------------------------------------------ 73 ALTERNATIVE A - MIT License 74 Copyright (c) 2020-2023 Micha Mettke 75 Permission is hereby granted, free of charge, to any person obtaining a copy of 76 this software and associated documentation files (the "Software"), to deal in 77 the Software without restriction, including without limitation the rights to 78 use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies 79 of the Software, and to permit persons to whom the Software is furnished to do 80 so, subject to the following conditions: 81 The above copyright notice and this permission notice shall be included in all 82 copies or substantial portions of the Software. 83 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 84 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 85 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 86 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 87 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 88 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 89 SOFTWARE. 90 ------------------------------------------------------------------------------ 91 ALTERNATIVE B - Public Domain (www.unlicense.org) 92 This is free and unencumbered software released into the public domain. 93 Anyone is free to copy, modify, publish, use, compile, sell, or distribute this 94 software, either in source code form or as a compiled binary, for any purpose, 95 commercial or non-commercial, and by any means. 96 In jurisdictions that recognize copyright laws, the author or authors of this 97 software dedicate any and all copyright interest in the software to the public 98 domain. We make this dedication for the benefit of the public at large and to 99 the detriment of our heirs and successors. We intend this dedication to be an 100 overt act of relinquishment in perpetuity of all present and future rights to 101 this software under copyright law. 102 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 103 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 104 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 105 AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN 106 ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 107 WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 108 ------------------------------------------------------------------------------ 109 ``` 110 */ 111 #ifndef SDEFL_H_INCLUDED 112 #define SDEFL_H_INCLUDED 113 114 #ifdef __cplusplus 115 extern "C" { 116 #endif 117 118 #define SDEFL_MAX_OFF (1 << 15) 119 #define SDEFL_WIN_SIZ SDEFL_MAX_OFF 120 #define SDEFL_WIN_MSK (SDEFL_WIN_SIZ-1) 121 122 #define SDEFL_HASH_BITS 15 123 #define SDEFL_HASH_SIZ (1 << SDEFL_HASH_BITS) 124 #define SDEFL_HASH_MSK (SDEFL_HASH_SIZ-1) 125 126 #define SDEFL_MIN_MATCH 4 127 #define SDEFL_BLK_MAX (256*1024) 128 #define SDEFL_SEQ_SIZ ((SDEFL_BLK_MAX+2)/3) 129 130 #define SDEFL_SYM_MAX (288) 131 #define SDEFL_OFF_MAX (32) 132 #define SDEFL_PRE_MAX (19) 133 134 #define SDEFL_LVL_MIN 0 135 #define SDEFL_LVL_DEF 5 136 #define SDEFL_LVL_MAX 8 137 138 struct sdefl_freq { 139 unsigned lit[SDEFL_SYM_MAX]; 140 unsigned off[SDEFL_OFF_MAX]; 141 }; 142 struct sdefl_code_words { 143 unsigned lit[SDEFL_SYM_MAX]; 144 unsigned off[SDEFL_OFF_MAX]; 145 }; 146 struct sdefl_lens { 147 unsigned char lit[SDEFL_SYM_MAX]; 148 unsigned char off[SDEFL_OFF_MAX]; 149 }; 150 struct sdefl_codes { 151 struct sdefl_code_words word; 152 struct sdefl_lens len; 153 }; 154 struct sdefl_seqt { 155 int off, len; 156 }; 157 struct sdefl { 158 int bits, bitcnt; 159 int tbl[SDEFL_HASH_SIZ]; 160 int prv[SDEFL_WIN_SIZ]; 161 162 int seq_cnt; 163 struct sdefl_seqt seq[SDEFL_SEQ_SIZ]; 164 struct sdefl_freq freq; 165 struct sdefl_codes cod; 166 }; 167 extern int sdefl_bound(int in_len); 168 extern int sdeflate(struct sdefl *s, void *o, const void *i, int n, int lvl); 169 extern int zsdeflate(struct sdefl *s, void *o, const void *i, int n, int lvl); 170 171 #ifdef __cplusplus 172 } 173 #endif 174 175 #endif /* SDEFL_H_INCLUDED */ 176 177 #ifdef SDEFL_IMPLEMENTATION 178 179 #include <assert.h> /* assert */ 180 #include <string.h> /* memcpy */ 181 #include <limits.h> /* CHAR_BIT */ 182 183 #define SDEFL_NIL (-1) 184 #define SDEFL_MAX_MATCH 258 185 #define SDEFL_MAX_CODE_LEN (15) 186 #define SDEFL_SYM_BITS (10u) 187 #define SDEFL_SYM_MSK ((1u << SDEFL_SYM_BITS)-1u) 188 #define SDEFL_RAW_BLK_SIZE (65535) 189 #define SDEFL_LIT_LEN_CODES (14) 190 #define SDEFL_OFF_CODES (15) 191 #define SDEFL_PRE_CODES (7) 192 #define SDEFL_CNT_NUM(n) ((((n)+3u/4u)+3u)&~3u) 193 #define SDEFL_EOB (256) 194 195 #define sdefl_npow2(n) (1 << (sdefl_ilog2((n)-1) + 1)) 196 #define sdefl_div_round_up(n,d) (((n)+((d)-1))/(d)) 197 198 static int 199 sdefl_ilog2(int n) { 200 if (!n) return 0; 201 #ifdef _MSC_VER 202 unsigned long msbp = 0; 203 _BitScanReverse(&msbp, (unsigned long)n); 204 return (int)msbp; 205 #elif defined(__GNUC__) || defined(__clang__) 206 return (int)sizeof(unsigned long) * CHAR_BIT - 1 - __builtin_clzl((unsigned long)n); 207 #else 208 #define lt(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n 209 static const char tbl[256] = { 210 0,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,lt(4), lt(5), lt(5), lt(6), lt(6), lt(6), lt(6), 211 lt(7), lt(7), lt(7), lt(7), lt(7), lt(7), lt(7), lt(7)}; 212 int tt, t; 213 if ((tt = (n >> 16))) { 214 return (t = (tt >> 8)) ? 24 + tbl[t] : 16 + tbl[tt]; 215 } else { 216 return (t = (n >> 8)) ? 8 + tbl[t] : tbl[n]; 217 } 218 #undef lt 219 #endif 220 } 221 static unsigned 222 sdefl_uload32(const void *p) { 223 /* hopefully will be optimized to an unaligned read */ 224 unsigned n = 0; 225 memcpy(&n, p, sizeof(n)); 226 return n; 227 } 228 static unsigned 229 sdefl_hash32(const void *p) { 230 unsigned n = sdefl_uload32(p); 231 return (n * 0x9E377989) >> (32 - SDEFL_HASH_BITS); 232 } 233 static void 234 sdefl_put(unsigned char **dst, struct sdefl *s, int code, int bitcnt) { 235 s->bits |= (code << s->bitcnt); 236 s->bitcnt += bitcnt; 237 while (s->bitcnt >= 8) { 238 unsigned char *tar = *dst; 239 *tar = (unsigned char)(s->bits & 0xFF); 240 s->bits >>= 8; 241 s->bitcnt -= 8; 242 *dst = *dst + 1; 243 } 244 } 245 static void 246 sdefl_heap_sub(unsigned A[], unsigned len, unsigned sub) { 247 unsigned c, p = sub; 248 unsigned v = A[sub]; 249 while ((c = p << 1) <= len) { 250 if (c < len && A[c + 1] > A[c]) c++; 251 if (v >= A[c]) break; 252 A[p] = A[c], p = c; 253 } 254 A[p] = v; 255 } 256 static void 257 sdefl_heap_array(unsigned *A, unsigned len) { 258 unsigned sub; 259 for (sub = len >> 1; sub >= 1; sub--) 260 sdefl_heap_sub(A, len, sub); 261 } 262 static void 263 sdefl_heap_sort(unsigned *A, unsigned n) { 264 A--; 265 sdefl_heap_array(A, n); 266 while (n >= 2) { 267 unsigned tmp = A[n]; 268 A[n--] = A[1]; 269 A[1] = tmp; 270 sdefl_heap_sub(A, n, 1); 271 } 272 } 273 static unsigned 274 sdefl_sort_sym(unsigned sym_cnt, unsigned *freqs, 275 unsigned char *lens, unsigned *sym_out) { 276 unsigned cnts[SDEFL_CNT_NUM(SDEFL_SYM_MAX)] = {0}; 277 unsigned cnt_num = SDEFL_CNT_NUM(sym_cnt); 278 unsigned used_sym = 0; 279 unsigned sym, i; 280 for (sym = 0; sym < sym_cnt; sym++) 281 cnts[freqs[sym] < cnt_num-1 ? freqs[sym]: cnt_num-1]++; 282 for (i = 1; i < cnt_num; i++) { 283 unsigned cnt = cnts[i]; 284 cnts[i] = used_sym; 285 used_sym += cnt; 286 } 287 for (sym = 0; sym < sym_cnt; sym++) { 288 unsigned freq = freqs[sym]; 289 if (freq) { 290 unsigned idx = freq < cnt_num-1 ? freq : cnt_num-1; 291 sym_out[cnts[idx]++] = sym | (freq << SDEFL_SYM_BITS); 292 } else lens[sym] = 0; 293 } 294 sdefl_heap_sort(sym_out + cnts[cnt_num-2], cnts[cnt_num-1] - cnts[cnt_num-2]); 295 return used_sym; 296 } 297 static void 298 sdefl_build_tree(unsigned *A, unsigned sym_cnt) { 299 unsigned i = 0, b = 0, e = 0; 300 do { 301 unsigned m, n, freq_shift; 302 if (i != sym_cnt && (b == e || (A[i] >> SDEFL_SYM_BITS) <= (A[b] >> SDEFL_SYM_BITS))) 303 m = i++; 304 else m = b++; 305 if (i != sym_cnt && (b == e || (A[i] >> SDEFL_SYM_BITS) <= (A[b] >> SDEFL_SYM_BITS))) 306 n = i++; 307 else n = b++; 308 309 freq_shift = (A[m] & ~SDEFL_SYM_MSK) + (A[n] & ~SDEFL_SYM_MSK); 310 A[m] = (A[m] & SDEFL_SYM_MSK) | (e << SDEFL_SYM_BITS); 311 A[n] = (A[n] & SDEFL_SYM_MSK) | (e << SDEFL_SYM_BITS); 312 A[e] = (A[e] & SDEFL_SYM_MSK) | freq_shift; 313 } while (sym_cnt - ++e > 1); 314 } 315 static void 316 sdefl_gen_len_cnt(unsigned *A, unsigned root, unsigned *len_cnt, 317 unsigned max_code_len) { 318 int n; 319 unsigned i; 320 for (i = 0; i <= max_code_len; i++) 321 len_cnt[i] = 0; 322 len_cnt[1] = 2; 323 324 A[root] &= SDEFL_SYM_MSK; 325 for (n = (int)root - 1; n >= 0; n--) { 326 unsigned p = A[n] >> SDEFL_SYM_BITS; 327 unsigned pdepth = A[p] >> SDEFL_SYM_BITS; 328 unsigned depth = pdepth + 1; 329 unsigned len = depth; 330 331 A[n] = (A[n] & SDEFL_SYM_MSK) | (depth << SDEFL_SYM_BITS); 332 if (len >= max_code_len) { 333 len = max_code_len; 334 do len--; while (!len_cnt[len]); 335 } 336 len_cnt[len]--; 337 len_cnt[len+1] += 2; 338 } 339 } 340 static void 341 sdefl_gen_codes(unsigned *A, unsigned char *lens, const unsigned *len_cnt, 342 unsigned max_code_word_len, unsigned sym_cnt) { 343 unsigned i, sym, len, nxt[SDEFL_MAX_CODE_LEN + 1]; 344 for (i = 0, len = max_code_word_len; len >= 1; len--) { 345 unsigned cnt = len_cnt[len]; 346 while (cnt--) lens[A[i++] & SDEFL_SYM_MSK] = (unsigned char)len; 347 } 348 nxt[0] = nxt[1] = 0; 349 for (len = 2; len <= max_code_word_len; len++) 350 nxt[len] = (nxt[len-1] + len_cnt[len-1]) << 1; 351 for (sym = 0; sym < sym_cnt; sym++) 352 A[sym] = nxt[lens[sym]]++; 353 } 354 static unsigned 355 sdefl_rev(unsigned c, unsigned char n) { 356 c = ((c & 0x5555) << 1) | ((c & 0xAAAA) >> 1); 357 c = ((c & 0x3333) << 2) | ((c & 0xCCCC) >> 2); 358 c = ((c & 0x0F0F) << 4) | ((c & 0xF0F0) >> 4); 359 c = ((c & 0x00FF) << 8) | ((c & 0xFF00) >> 8); 360 return c >> (16-n); 361 } 362 static void 363 sdefl_huff(unsigned char *lens, unsigned *codes, unsigned *freqs, 364 unsigned num_syms, unsigned max_code_len) { 365 unsigned c, *A = codes; 366 unsigned len_cnt[SDEFL_MAX_CODE_LEN + 1]; 367 unsigned used_syms = sdefl_sort_sym(num_syms, freqs, lens, A); 368 if (!used_syms) return; 369 if (used_syms == 1) { 370 unsigned s = A[0] & SDEFL_SYM_MSK; 371 unsigned i = s ? s : 1; 372 codes[0] = 0, lens[0] = 1; 373 codes[i] = 1, lens[i] = 1; 374 return; 375 } 376 sdefl_build_tree(A, used_syms); 377 sdefl_gen_len_cnt(A, used_syms-2, len_cnt, max_code_len); 378 sdefl_gen_codes(A, lens, len_cnt, max_code_len, num_syms); 379 for (c = 0; c < num_syms; c++) { 380 codes[c] = sdefl_rev(codes[c], lens[c]); 381 } 382 } 383 struct sdefl_symcnt { 384 int items; 385 int lit; 386 int off; 387 }; 388 static void 389 sdefl_precode(struct sdefl_symcnt *cnt, unsigned *freqs, unsigned *items, 390 const unsigned char *litlen, const unsigned char *offlen) { 391 unsigned *at = items; 392 unsigned run_start = 0; 393 394 unsigned total = 0; 395 unsigned char lens[SDEFL_SYM_MAX + SDEFL_OFF_MAX]; 396 for (cnt->lit = SDEFL_SYM_MAX; cnt->lit > 257; cnt->lit--) 397 if (litlen[cnt->lit - 1]) break; 398 for (cnt->off = SDEFL_OFF_MAX; cnt->off > 1; cnt->off--) 399 if (offlen[cnt->off - 1]) break; 400 401 total = (unsigned)(cnt->lit + cnt->off); 402 memcpy(lens, litlen, sizeof(unsigned char) * (size_t)cnt->lit); 403 memcpy(lens + cnt->lit, offlen, sizeof(unsigned char) * (size_t)cnt->off); 404 do { 405 unsigned len = lens[run_start]; 406 unsigned run_end = run_start; 407 do run_end++; while (run_end != total && len == lens[run_end]); 408 if (!len) { 409 while ((run_end - run_start) >= 11) { 410 unsigned n = (run_end - run_start) - 11; 411 unsigned xbits = n < 0x7f ? n : 0x7f; 412 freqs[18]++; 413 *at++ = 18u | (xbits << 5u); 414 run_start += 11 + xbits; 415 } 416 if ((run_end - run_start) >= 3) { 417 unsigned n = (run_end - run_start) - 3; 418 unsigned xbits = n < 0x7 ? n : 0x7; 419 freqs[17]++; 420 *at++ = 17u | (xbits << 5u); 421 run_start += 3 + xbits; 422 } 423 } else if ((run_end - run_start) >= 4) { 424 freqs[len]++; 425 *at++ = len; 426 run_start++; 427 do { 428 unsigned xbits = (run_end - run_start) - 3; 429 xbits = xbits < 0x03 ? xbits : 0x03; 430 *at++ = 16 | (xbits << 5); 431 run_start += 3 + xbits; 432 freqs[16]++; 433 } while ((run_end - run_start) >= 3); 434 } 435 while (run_start != run_end) { 436 freqs[len]++; 437 *at++ = len; 438 run_start++; 439 } 440 } while (run_start != total); 441 cnt->items = (int)(at - items); 442 } 443 struct sdefl_match_codest { 444 int ls, lc; 445 int dc, dx; 446 }; 447 static void 448 sdefl_match_codes(struct sdefl_match_codest *cod, int dist, int len) { 449 static const short dxmax[] = {0,6,12,24,48,96,192,384,768,1536,3072,6144,12288,24576}; 450 static const unsigned char lslot[258+1] = { 451 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 12, 452 12, 13, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15, 16, 16, 16, 16, 16, 453 16, 16, 16, 17, 17, 17, 17, 17, 17, 17, 17, 18, 18, 18, 18, 18, 18, 18, 454 18, 19, 19, 19, 19, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 20, 20, 20, 455 20, 20, 20, 20, 20, 20, 20, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 456 21, 21, 21, 21, 21, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 457 22, 22, 22, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 458 23, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 459 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 25, 25, 25, 460 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 461 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26, 26, 26, 26, 26, 462 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 463 26, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 464 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 465 27, 27, 28 466 }; 467 assert(len <= 258); 468 assert(dist <= 32768); 469 cod->ls = lslot[len]; 470 cod->lc = 257 + cod->ls; 471 assert(cod->lc <= 285); 472 473 cod->dx = sdefl_ilog2(sdefl_npow2(dist) >> 2); 474 cod->dc = cod->dx ? ((cod->dx + 1) << 1) + (dist > dxmax[cod->dx]) : dist-1; 475 } 476 enum sdefl_blk_type { 477 SDEFL_BLK_UCOMPR, 478 SDEFL_BLK_DYN 479 }; 480 static enum sdefl_blk_type 481 sdefl_blk_type(const struct sdefl *s, int blk_len, int pre_item_len, 482 const unsigned *pre_freq, const unsigned char *pre_len) { 483 static const unsigned char x_pre_bits[] = { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7}; 484 static const unsigned char x_len_bits[] = {0,0,0,0,0,0,0,0, 1,1,1,1,2,2,2,2, 485 3,3,3,3,4,4,4,4, 5,5,5,5,0}; 486 static const unsigned char x_off_bits[] = {0,0,0,0,1,1,2,2, 3,3,4,4,5,5,6,6, 487 7,7,8,8,9,9,10,10, 11,11,12,12,13,13}; 488 489 int dyn_cost = 0; 490 int fix_cost = 0; 491 int sym = 0; 492 493 dyn_cost += 5 + 5 + 4 + (3 * pre_item_len); 494 for (sym = 0; sym < SDEFL_PRE_MAX; sym++) 495 dyn_cost += pre_freq[sym] * (x_pre_bits[sym] + pre_len[sym]); 496 for (sym = 0; sym < 256; sym++) 497 dyn_cost += s->freq.lit[sym] * s->cod.len.lit[sym]; 498 dyn_cost += s->cod.len.lit[SDEFL_EOB]; 499 for (sym = 257; sym < 286; sym++) 500 dyn_cost += s->freq.lit[sym] * (x_len_bits[sym - 257] + s->cod.len.lit[sym]); 501 for (sym = 0; sym < 30; sym++) 502 dyn_cost += s->freq.off[sym] * (x_off_bits[sym] + s->cod.len.off[sym]); 503 504 fix_cost += 8*(5 * sdefl_div_round_up(blk_len, SDEFL_RAW_BLK_SIZE) + blk_len + 1 + 2); 505 return (dyn_cost < fix_cost) ? SDEFL_BLK_DYN : SDEFL_BLK_UCOMPR; 506 } 507 static void 508 sdefl_put16(unsigned char **dst, unsigned short x) { 509 unsigned char *val = *dst; 510 val[0] = (unsigned char)(x & 0xff); 511 val[1] = (unsigned char)(x >> 8); 512 *dst = val + 2; 513 } 514 static void 515 sdefl_match(unsigned char **dst, struct sdefl *s, int dist, int len) { 516 static const char lxn[] = {0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0}; 517 static const short lmin[] = {3,4,5,6,7,8,9,10,11,13,15,17,19,23,27,31,35,43, 518 51,59,67,83,99,115,131,163,195,227,258}; 519 static const short dmin[] = {1,2,3,4,5,7,9,13,17,25,33,49,65,97,129,193,257, 520 385,513,769,1025,1537,2049,3073,4097,6145,8193,12289,16385,24577}; 521 522 struct sdefl_match_codest cod; 523 sdefl_match_codes(&cod, dist, len); 524 sdefl_put(dst, s, (int)s->cod.word.lit[cod.lc], s->cod.len.lit[cod.lc]); 525 sdefl_put(dst, s, len - lmin[cod.ls], lxn[cod.ls]); 526 sdefl_put(dst, s, (int)s->cod.word.off[cod.dc], s->cod.len.off[cod.dc]); 527 sdefl_put(dst, s, dist - dmin[cod.dc], cod.dx); 528 } 529 static void 530 sdefl_flush(unsigned char **dst, struct sdefl *s, int is_last, 531 const unsigned char *in, int blk_begin, int blk_end) { 532 int blk_len = blk_end - blk_begin; 533 int j, i = 0, item_cnt = 0; 534 struct sdefl_symcnt symcnt = {0}; 535 unsigned codes[SDEFL_PRE_MAX]; 536 unsigned char lens[SDEFL_PRE_MAX]; 537 unsigned freqs[SDEFL_PRE_MAX] = {0}; 538 unsigned items[SDEFL_SYM_MAX + SDEFL_OFF_MAX]; 539 static const unsigned char perm[SDEFL_PRE_MAX] = {16,17,18,0,8,7,9,6,10,5,11, 540 4,12,3,13,2,14,1,15}; 541 542 /* calculate huffman codes */ 543 s->freq.lit[SDEFL_EOB]++; 544 sdefl_huff(s->cod.len.lit, s->cod.word.lit, s->freq.lit, SDEFL_SYM_MAX, SDEFL_LIT_LEN_CODES); 545 sdefl_huff(s->cod.len.off, s->cod.word.off, s->freq.off, SDEFL_OFF_MAX, SDEFL_OFF_CODES); 546 sdefl_precode(&symcnt, freqs, items, s->cod.len.lit, s->cod.len.off); 547 sdefl_huff(lens, codes, freqs, SDEFL_PRE_MAX, SDEFL_PRE_CODES); 548 for (item_cnt = SDEFL_PRE_MAX; item_cnt > 4; item_cnt--) { 549 if (lens[perm[item_cnt - 1]]){ 550 break; 551 } 552 } 553 /* write block */ 554 switch (sdefl_blk_type(s, blk_len, item_cnt, freqs, lens)) { 555 case SDEFL_BLK_UCOMPR: { 556 /* uncompressed blocks */ 557 int n = sdefl_div_round_up(blk_len, SDEFL_RAW_BLK_SIZE); 558 for (i = 0; i < n; ++i) { 559 int fin = is_last && (i + 1 == n); 560 int amount = blk_len < SDEFL_RAW_BLK_SIZE ? blk_len : SDEFL_RAW_BLK_SIZE; 561 sdefl_put(dst, s, !!fin, 1); /* block */ 562 sdefl_put(dst, s, 0x00, 2); /* stored block */ 563 if (s->bitcnt) { 564 sdefl_put(dst, s, 0x00, 8 - s->bitcnt); 565 } 566 assert(s->bitcnt == 0); 567 sdefl_put16(dst, (unsigned short)amount); 568 sdefl_put16(dst, ~(unsigned short)amount); 569 memcpy(*dst, in + blk_begin + i * SDEFL_RAW_BLK_SIZE, amount); 570 *dst = *dst + amount; 571 blk_len -= amount; 572 } 573 } break; 574 case SDEFL_BLK_DYN: { 575 /* dynamic huffman block */ 576 sdefl_put(dst, s, !!is_last, 1); /* block */ 577 sdefl_put(dst, s, 0x02, 2); /* dynamic huffman */ 578 sdefl_put(dst, s, symcnt.lit - 257, 5); 579 sdefl_put(dst, s, symcnt.off - 1, 5); 580 sdefl_put(dst, s, item_cnt - 4, 4); 581 for (i = 0; i < item_cnt; ++i) { 582 sdefl_put(dst, s, lens[perm[i]], 3); 583 } 584 for (i = 0; i < symcnt.items; ++i) { 585 unsigned sym = items[i] & 0x1F; 586 sdefl_put(dst, s, (int)codes[sym], lens[sym]); 587 if (sym < 16) continue; 588 if (sym == 16) sdefl_put(dst, s, items[i] >> 5, 2); 589 else if(sym == 17) sdefl_put(dst, s, items[i] >> 5, 3); 590 else sdefl_put(dst, s, items[i] >> 5, 7); 591 } 592 /* block sequences */ 593 for (i = 0; i < s->seq_cnt; ++i) { 594 if (s->seq[i].off >= 0) { 595 for (j = 0; j < s->seq[i].len; ++j) { 596 int c = in[s->seq[i].off + j]; 597 sdefl_put(dst, s, (int)s->cod.word.lit[c], s->cod.len.lit[c]); 598 } 599 } else { 600 sdefl_match(dst, s, -s->seq[i].off, s->seq[i].len); 601 } 602 } 603 sdefl_put(dst, s, (int)(s)->cod.word.lit[SDEFL_EOB], (s)->cod.len.lit[SDEFL_EOB]); 604 } break;} 605 memset(&s->freq, 0, sizeof(s->freq)); 606 s->seq_cnt = 0; 607 } 608 static void 609 sdefl_seq(struct sdefl *s, int off, int len) { 610 assert(s->seq_cnt + 2 < SDEFL_SEQ_SIZ); 611 s->seq[s->seq_cnt].off = off; 612 s->seq[s->seq_cnt].len = len; 613 s->seq_cnt++; 614 } 615 static void 616 sdefl_reg_match(struct sdefl *s, int off, int len) { 617 struct sdefl_match_codest cod; 618 sdefl_match_codes(&cod, off, len); 619 620 assert(cod.lc < SDEFL_SYM_MAX); 621 assert(cod.dc < SDEFL_OFF_MAX); 622 623 s->freq.lit[cod.lc]++; 624 s->freq.off[cod.dc]++; 625 } 626 struct sdefl_match { 627 int off; 628 int len; 629 }; 630 static void 631 sdefl_fnd(struct sdefl_match *m, const struct sdefl *s, int chain_len, 632 int max_match, const unsigned char *in, int p, int e) { 633 int i = s->tbl[sdefl_hash32(in + p)]; 634 int limit = ((p - SDEFL_WIN_SIZ) < SDEFL_NIL) ? SDEFL_NIL : (p-SDEFL_WIN_SIZ); 635 636 assert(p < e); 637 assert(p + max_match <= e); 638 while (i > limit) { 639 assert(i + m->len < e); 640 assert(p + m->len < e); 641 assert(i + SDEFL_MIN_MATCH < e); 642 assert(p + SDEFL_MIN_MATCH < e); 643 644 if (in[i + m->len] == in[p + m->len] && 645 (sdefl_uload32(&in[i]) == sdefl_uload32(&in[p]))) { 646 int n = SDEFL_MIN_MATCH; 647 while (n < max_match && in[i + n] == in[p + n]) { 648 assert(i + n < e); 649 assert(p + n < e); 650 n++; 651 } 652 if (n > m->len) { 653 m->len = n, m->off = p - i; 654 if (n == max_match) 655 break; 656 } 657 } 658 if (!(--chain_len)) break; 659 i = s->prv[i & SDEFL_WIN_MSK]; 660 } 661 } 662 static int 663 sdefl_compr(struct sdefl *s, unsigned char *out, const unsigned char *in, 664 int in_len, int lvl) { 665 unsigned char *q = out; 666 static const unsigned char pref[] = {8,10,14,24,30,48,65,96,130}; 667 int max_chain = (lvl < 8) ? (1 << (lvl + 1)): (1 << 13); 668 int n, i = 0, litlen = 0; 669 for (n = 0; n < SDEFL_HASH_SIZ; ++n) { 670 s->tbl[n] = SDEFL_NIL; 671 } 672 do {int blk_begin = i; 673 int blk_end = ((i + SDEFL_BLK_MAX) < in_len) ? (i + SDEFL_BLK_MAX) : in_len; 674 while (i < blk_end) { 675 struct sdefl_match m = {0}; 676 int left = blk_end - i; 677 int max_match = (left > SDEFL_MAX_MATCH) ? SDEFL_MAX_MATCH : left; 678 int nice_match = pref[lvl] < max_match ? pref[lvl] : max_match; 679 int run = 1, inc = 1, run_inc = 0; 680 if (max_match > SDEFL_MIN_MATCH) { 681 sdefl_fnd(&m, s, max_chain, max_match, in, i, in_len); 682 } 683 if (lvl >= 5 && m.len >= SDEFL_MIN_MATCH && m.len + 1 < nice_match){ 684 struct sdefl_match m2 = {0}; 685 sdefl_fnd(&m2, s, max_chain, m.len + 1, in, i + 1, in_len); 686 m.len = (m2.len > m.len) ? 0 : m.len; 687 } 688 if (m.len >= SDEFL_MIN_MATCH) { 689 if (litlen) { 690 sdefl_seq(s, i - litlen, litlen); 691 litlen = 0; 692 } 693 sdefl_seq(s, -m.off, m.len); 694 sdefl_reg_match(s, m.off, m.len); 695 if (lvl < 2 && m.len >= nice_match) { 696 inc = m.len; 697 } else { 698 run = m.len; 699 } 700 } else { 701 s->freq.lit[in[i]]++; 702 litlen++; 703 } 704 run_inc = run * inc; 705 if (in_len - (i + run_inc) > SDEFL_MIN_MATCH) { 706 while (run-- > 0) { 707 unsigned h = sdefl_hash32(&in[i]); 708 s->prv[i&SDEFL_WIN_MSK] = s->tbl[h]; 709 s->tbl[h] = i, i += inc; 710 assert(i <= blk_end); 711 } 712 } else { 713 i += run_inc; 714 assert(i <= blk_end); 715 } 716 } 717 if (litlen) { 718 sdefl_seq(s, i - litlen, litlen); 719 litlen = 0; 720 } 721 sdefl_flush(&q, s, blk_end == in_len, in, blk_begin, blk_end); 722 } while (i < in_len); 723 if (s->bitcnt) { 724 sdefl_put(&q, s, 0x00, 8 - s->bitcnt); 725 } 726 assert(s->bitcnt == 0); 727 return (int)(q - out); 728 } 729 extern int 730 sdeflate(struct sdefl *s, void *out, const void *in, int n, int lvl) { 731 s->bits = s->bitcnt = 0; 732 return sdefl_compr(s, (unsigned char*)out, (const unsigned char*)in, n, lvl); 733 } 734 static unsigned 735 sdefl_adler32(unsigned adler32, const unsigned char *in, int in_len) { 736 #define SDEFL_ADLER_INIT (1) 737 const unsigned ADLER_MOD = 65521; 738 unsigned s1 = adler32 & 0xffff; 739 unsigned s2 = adler32 >> 16; 740 unsigned blk_len, i; 741 742 blk_len = in_len % 5552; 743 while (in_len) { 744 for (i = 0; i + 7 < blk_len; i += 8) { 745 s1 += in[0]; s2 += s1; 746 s1 += in[1]; s2 += s1; 747 s1 += in[2]; s2 += s1; 748 s1 += in[3]; s2 += s1; 749 s1 += in[4]; s2 += s1; 750 s1 += in[5]; s2 += s1; 751 s1 += in[6]; s2 += s1; 752 s1 += in[7]; s2 += s1; 753 in += 8; 754 } 755 for (; i < blk_len; ++i) { 756 s1 += *in++, s2 += s1; 757 } 758 s1 %= ADLER_MOD; 759 s2 %= ADLER_MOD; 760 in_len -= blk_len; 761 blk_len = 5552; 762 } 763 return (unsigned)(s2 << 16) + (unsigned)s1; 764 } 765 extern int 766 zsdeflate(struct sdefl *s, void *out, const void *in, int n, int lvl) { 767 int p = 0; 768 unsigned a = 0; 769 unsigned char *q = (unsigned char*)out; 770 771 s->bits = s->bitcnt = 0; 772 sdefl_put(&q, s, 0x78, 8); /* deflate, 32k window */ 773 sdefl_put(&q, s, 0x01, 8); /* fast compression */ 774 q += sdefl_compr(s, q, (const unsigned char*)in, n, lvl); 775 776 /* append adler checksum */ 777 a = sdefl_adler32(SDEFL_ADLER_INIT, (const unsigned char*)in, n); 778 for (p = 0; p < 4; ++p) { 779 sdefl_put(&q, s, (a >> 24) & 0xFF, 8); 780 a <<= 8; 781 } 782 return (int)(q - (unsigned char*)out); 783 } 784 extern int 785 sdefl_bound(int len) { 786 int max_blocks = 1 + sdefl_div_round_up(len, SDEFL_RAW_BLK_SIZE); 787 int bound = 5 * max_blocks + len + 1 + 4 + 8; 788 return bound; 789 } 790 #endif /* SDEFL_IMPLEMENTATION */