| Line |
Branch |
Exec |
Source |
| 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 */ |
| 791 |
|
|
|