git ptrace.dev


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