111#ifndef SDEFL_H_INCLUDED
112#define SDEFL_H_INCLUDED
118#define SDEFL_MAX_OFF (1 << 15)
119#define SDEFL_WIN_SIZ SDEFL_MAX_OFF
120#define SDEFL_WIN_MSK (SDEFL_WIN_SIZ-1)
122#define SDEFL_HASH_BITS 15
123#define SDEFL_HASH_SIZ (1 << SDEFL_HASH_BITS)
124#define SDEFL_HASH_MSK (SDEFL_HASH_SIZ-1)
126#define SDEFL_MIN_MATCH 4
127#define SDEFL_BLK_MAX (256*1024)
128#define SDEFL_SEQ_SIZ ((SDEFL_BLK_MAX + SDEFL_MIN_MATCH)/SDEFL_MIN_MATCH)
130#define SDEFL_SYM_MAX (288)
131#define SDEFL_OFF_MAX (32)
132#define SDEFL_PRE_MAX (19)
134#define SDEFL_LVL_MIN 0
135#define SDEFL_LVL_DEF 5
136#define SDEFL_LVL_MAX 8
168extern int sdeflate(
struct sdefl *s,
void *o,
const void *i,
int n,
int lvl);
177#ifdef SDEFL_IMPLEMENTATION
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_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)
194#define sdefl_npow2(n) (1 << (sdefl_ilog2((n)-1) + 1))
200 unsigned long msbp = 0;
201 _BitScanReverse(&msbp, (
unsigned long)n);
203#elif defined(__GNUC__) || defined(__clang__)
204 return (
int)
sizeof(
unsigned long) * CHAR_BIT - 1 - __builtin_clzl((
unsigned long)n);
206 #define lt(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n
207 static const char tbl[256] = {
208 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),
209 lt(7), lt(7), lt(7), lt(7), lt(7), lt(7), lt(7), lt(7)};
211 if ((tt = (n >> 16))) {
212 return (t = (tt >> 8)) ? 24 + tbl[t] : 16 + tbl[tt];
214 return (t = (n >> 8)) ? 8 + tbl[t] : tbl[n];
220sdefl_uload32(
const void *p) {
223 memcpy(&n, p,
sizeof(n));
227sdefl_hash32(
const void *p) {
228 unsigned n = sdefl_uload32(p);
232sdefl_put(
unsigned char **dst,
struct sdefl *s,
int code,
int bitcnt) {
236 unsigned char *tar = *dst;
237 *tar = (
unsigned char)(s->
bits & 0xFF);
244sdefl_heap_sub(
unsigned A[],
unsigned len,
unsigned sub) {
247 while ((c = p << 1) <=
len) {
248 if (c <
len && A[c + 1] > A[c]) c++;
249 if (v >= A[c])
break;
255sdefl_heap_array(
unsigned *A,
unsigned len) {
257 for (sub =
len >> 1; sub >= 1; sub--)
258 sdefl_heap_sub(A,
len, sub);
261sdefl_heap_sort(
unsigned *A,
unsigned n) {
263 sdefl_heap_array(A, n);
268 sdefl_heap_sub(A, n, 1);
272sdefl_sort_sym(
unsigned sym_cnt,
unsigned *freqs,
273 unsigned char *lens,
unsigned *sym_out) {
275 unsigned cnt_num = SDEFL_CNT_NUM(sym_cnt);
276 unsigned used_sym = 0;
278 for (sym = 0; sym < sym_cnt; sym++)
279 cnts[freqs[sym] < cnt_num-1 ? freqs[sym]: cnt_num-1]++;
280 for (i = 1; i < cnt_num; i++) {
281 unsigned cnt = cnts[i];
285 for (sym = 0; sym < sym_cnt; sym++) {
286 unsigned freq = freqs[sym];
288 unsigned idx = freq < cnt_num-1 ? freq : cnt_num-1;
289 sym_out[cnts[idx]++] = sym | (freq << SDEFL_SYM_BITS);
290 }
else lens[sym] = 0;
292 sdefl_heap_sort(sym_out + cnts[cnt_num-2], cnts[cnt_num-1] - cnts[cnt_num-2]);
296sdefl_build_tree(
unsigned *A,
unsigned sym_cnt) {
297 unsigned i = 0, b = 0, e = 0;
299 unsigned m, n, freq_shift;
300 if (i != sym_cnt && (b == e || (A[i] >> SDEFL_SYM_BITS) <= (A[b] >> SDEFL_SYM_BITS)))
303 if (i != sym_cnt && (b == e || (A[i] >> SDEFL_SYM_BITS) <= (A[b] >> SDEFL_SYM_BITS)))
307 freq_shift = (A[m] & ~SDEFL_SYM_MSK) + (A[n] & ~SDEFL_SYM_MSK);
308 A[m] = (A[m] & SDEFL_SYM_MSK) | (e << SDEFL_SYM_BITS);
309 A[n] = (A[n] & SDEFL_SYM_MSK) | (e << SDEFL_SYM_BITS);
310 A[e] = (A[e] & SDEFL_SYM_MSK) | freq_shift;
311 }
while (sym_cnt - ++e > 1);
314sdefl_gen_len_cnt(
unsigned *A,
unsigned root,
unsigned *len_cnt,
315 unsigned max_code_len) {
318 for (i = 0; i <= max_code_len; i++)
322 A[root] &= SDEFL_SYM_MSK;
323 for (n = (
int)root - 1; n >= 0; n--) {
324 unsigned p = A[n] >> SDEFL_SYM_BITS;
325 unsigned pdepth = A[p] >> SDEFL_SYM_BITS;
326 unsigned depth = pdepth + 1;
327 unsigned len = depth;
329 A[n] = (A[n] & SDEFL_SYM_MSK) | (depth << SDEFL_SYM_BITS);
330 if (
len >= max_code_len) {
332 do len--;
while (!len_cnt[
len]);
339sdefl_gen_codes(
unsigned *A,
unsigned char *lens,
const unsigned *len_cnt,
340 unsigned max_code_word_len,
unsigned sym_cnt) {
341 unsigned i, sym,
len, nxt[SDEFL_MAX_CODE_LEN + 1];
342 for (i = 0,
len = max_code_word_len;
len >= 1;
len--) {
343 unsigned cnt = len_cnt[
len];
344 while (cnt--) lens[A[i++] & SDEFL_SYM_MSK] = (
unsigned char)
len;
347 for (
len = 2;
len <= max_code_word_len;
len++)
348 nxt[
len] = (nxt[
len-1] + len_cnt[
len-1]) << 1;
349 for (sym = 0; sym < sym_cnt; sym++)
350 A[sym] = nxt[lens[sym]]++;
353sdefl_rev(
unsigned c,
unsigned char n) {
354 c = ((c & 0x5555) << 1) | ((c & 0xAAAA) >> 1);
355 c = ((c & 0x3333) << 2) | ((c & 0xCCCC) >> 2);
356 c = ((c & 0x0F0F) << 4) | ((c & 0xF0F0) >> 4);
357 c = ((c & 0x00FF) << 8) | ((c & 0xFF00) >> 8);
361sdefl_huff(
unsigned char *lens,
unsigned *codes,
unsigned *freqs,
362 unsigned num_syms,
unsigned max_code_len) {
363 unsigned c, *A = codes;
364 unsigned len_cnt[SDEFL_MAX_CODE_LEN + 1];
365 unsigned used_syms = sdefl_sort_sym(num_syms, freqs, lens, A);
366 if (!used_syms)
return;
367 if (used_syms == 1) {
368 unsigned s = A[0] & SDEFL_SYM_MSK;
369 unsigned i = s ? s : 1;
370 codes[0] = 0, lens[0] = 1;
371 codes[i] = 1, lens[i] = 1;
374 sdefl_build_tree(A, used_syms);
375 sdefl_gen_len_cnt(A, used_syms-2, len_cnt, max_code_len);
376 sdefl_gen_codes(A, lens, len_cnt, max_code_len, num_syms);
377 for (c = 0; c < num_syms; c++) {
378 codes[c] = sdefl_rev(codes[c], lens[c]);
387sdefl_precode(
struct sdefl_symcnt *cnt,
unsigned *freqs,
unsigned *items,
388 const unsigned char *litlen,
const unsigned char *offlen) {
389 unsigned *at = items;
390 unsigned run_start = 0;
395 if (litlen[cnt->lit - 1])
break;
397 if (offlen[cnt->off - 1])
break;
399 total = (unsigned)(cnt->lit + cnt->off);
400 memcpy(lens, litlen,
sizeof(
unsigned char) * (
size_t)cnt->lit);
401 memcpy(lens + cnt->lit, offlen,
sizeof(
unsigned char) * (
size_t)cnt->off);
403 unsigned len = lens[run_start];
404 unsigned run_end = run_start;
405 do run_end++;
while (run_end != total && len == lens[run_end]);
407 while ((run_end - run_start) >= 11) {
408 unsigned n = (run_end - run_start) - 11;
409 unsigned xbits = n < 0x7f ? n : 0x7f;
411 *at++ = 18u | (xbits << 5u);
412 run_start += 11 + xbits;
414 if ((run_end - run_start) >= 3) {
415 unsigned n = (run_end - run_start) - 3;
416 unsigned xbits = n < 0x7 ? n : 0x7;
418 *at++ = 17u | (xbits << 5u);
419 run_start += 3 + xbits;
421 }
else if ((run_end - run_start) >= 4) {
426 unsigned xbits = (run_end - run_start) - 3;
427 xbits = xbits < 0x03 ? xbits : 0x03;
428 *at++ = 16 | (xbits << 5);
429 run_start += 3 + xbits;
431 }
while ((run_end - run_start) >= 3);
433 while (run_start != run_end) {
438 }
while (run_start != total);
439 cnt->items = (int)(at - items);
441struct sdefl_match_codes {
446sdefl_match_codes(
struct sdefl_match_codes *cod,
int dist,
int len) {
447 static const short dxmax[] = {0,6,12,24,48,96,192,384,768,1536,3072,6144,12288,24576};
448 static const unsigned char lslot[258+1] = {
449 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 12,
450 12, 13, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15, 16, 16, 16, 16, 16,
451 16, 16, 16, 17, 17, 17, 17, 17, 17, 17, 17, 18, 18, 18, 18, 18, 18, 18,
452 18, 19, 19, 19, 19, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 20, 20, 20,
453 20, 20, 20, 20, 20, 20, 20, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
454 21, 21, 21, 21, 21, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
455 22, 22, 22, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
456 23, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
457 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 25, 25, 25,
458 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
459 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26, 26, 26, 26, 26,
460 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
461 26, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
462 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
465 cod->ls = lslot[len];
466 cod->lc = 257 + cod->ls;
467 cod->dx = sdefl_ilog2(sdefl_npow2(dist) >> 2);
468 cod->dc = cod->dx ? ((cod->dx + 1) << 1) + (dist > dxmax[cod->dx]) : dist-1;
471sdefl_match(
unsigned char **dst,
struct sdefl *s,
int dist,
int len) {
472 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};
473 static const short lmin[] = {3,4,5,6,7,8,9,10,11,13,15,17,19,23,27,31,35,43,
474 51,59,67,83,99,115,131,163,195,227,258};
475 static const short dmin[] = {1,2,3,4,5,7,9,13,17,25,33,49,65,97,129,193,257,
476 385,513,769,1025,1537,2049,3073,4097,6145,8193,12289,16385,24577};
478 struct sdefl_match_codes cod;
479 sdefl_match_codes(&cod, dist, len);
481 sdefl_put(dst, s, len - lmin[cod.ls], lxn[cod.ls]);
483 sdefl_put(dst, s, dist - dmin[cod.dc], cod.dx);
486sdefl_flush(
unsigned char **dst,
struct sdefl *s,
int is_last,
487 const unsigned char *in) {
488 int j, i = 0, item_cnt = 0;
489 struct sdefl_symcnt symcnt = {0};
494 static const unsigned char perm[
SDEFL_PRE_MAX] = {16,17,18,0,8,7,9,6,10,5,11,
495 4,12,3,13,2,14,1,15};
502 sdefl_huff(lens, codes, freqs,
SDEFL_PRE_MAX, SDEFL_PRE_CODES);
504 if (lens[perm[item_cnt - 1]])
break;
507 sdefl_put(dst, s, is_last ? 0x01 : 0x00, 1);
508 sdefl_put(dst, s, 0x02, 2);
509 sdefl_put(dst, s, symcnt.lit - 257, 5);
510 sdefl_put(dst, s, symcnt.off - 1, 5);
511 sdefl_put(dst, s, item_cnt - 4, 4);
512 for (i = 0; i < item_cnt; ++i)
513 sdefl_put(dst, s, lens[perm[i]], 3);
514 for (i = 0; i < symcnt.items; ++i) {
515 unsigned sym = items[i] & 0x1F;
516 sdefl_put(dst, s, (
int)codes[sym], lens[sym]);
517 if (sym < 16)
continue;
518 if (sym == 16) sdefl_put(dst, s, items[i] >> 5, 2);
519 else if(sym == 17) sdefl_put(dst, s, items[i] >> 5, 3);
520 else sdefl_put(dst, s, items[i] >> 5, 7);
523 for (i = 0; i < s->
seq_cnt; ++i) {
525 for (j = 0; j < s->
seq[i].
len; ++j) {
526 int c = in[s->
seq[i].
off + j];
529 else sdefl_match(dst, s, -s->
seq[i].
off, s->
seq[i].
len);
531 sdefl_put(dst, s, (
int)(s)->cod.word.lit[SDEFL_EOB], (s)->cod.len.lit[SDEFL_EOB]);
532 memset(&s->
freq, 0,
sizeof(s->
freq));
536sdefl_seq(
struct sdefl *s,
int off,
int len) {
543sdefl_reg_match(
struct sdefl *s,
int off,
int len) {
544 struct sdefl_match_codes cod;
545 sdefl_match_codes(&cod, off, len);
554sdefl_fnd(
struct sdefl_match *m,
const struct sdefl *s,
555 int chain_len,
int max_match,
const unsigned char *in,
int p) {
556 int i = s->
tbl[sdefl_hash32(&in[p])];
559 if (in[i+m->len] == in[p+m->len] &&
560 (sdefl_uload32(&in[i]) == sdefl_uload32(&in[p]))){
562 while (n < max_match && in[i+n] == in[p+n]) n++;
564 m->len = n, m->off = p - i;
565 if (n == max_match)
break;
568 if (!(--chain_len))
break;
573sdefl_compr(
struct sdefl *s,
unsigned char *out,
const unsigned char *in,
574 int in_len,
int lvl) {
575 unsigned char *q = out;
576 static const unsigned char pref[] = {8,10,14,24,30,48,65,96,130};
577 int max_chain = (lvl < 8) ? (1 << (lvl + 1)): (1 << 13);
578 int n, i = 0, litlen = 0;
580 s->
tbl[n] = SDEFL_NIL;
583 while (i < blk_end) {
584 struct sdefl_match m = {0};
585 int max_match = ((in_len-i)>SDEFL_MAX_MATCH) ? SDEFL_MAX_MATCH:(in_len-i);
586 int nice_match = pref[lvl] < max_match ? pref[lvl] : max_match;
587 int run = 1, inc = 1, run_inc;
589 sdefl_fnd(&m, s, max_chain, max_match, in, i);
592 struct sdefl_match m2 = {0};
593 sdefl_fnd(&m2, s, max_chain, m.len+1, in, i+1);
594 m.len = (m2.len > m.len) ? 0 : m.len;
598 sdefl_seq(s, i - litlen, litlen);
601 sdefl_seq(s, -m.off, m.len);
602 sdefl_reg_match(s, m.off, m.len);
603 if (lvl < 2 && m.len >= nice_match) {
615 unsigned h = sdefl_hash32(&in[i]);
617 s->
tbl[h] = i, i += inc;
624 sdefl_seq(s, i - litlen, litlen);
627 sdefl_flush(&q, s, blk_end == in_len, in);
628 }
while (i < in_len);
631 sdefl_put(&q, s, 0x00, 8 - s->
bitcnt);
632 return (
int)(q - out);
635sdeflate(
struct sdefl *s,
void *out,
const void *in,
int n,
int lvl) {
637 return sdefl_compr(s, (
unsigned char*)out, (
const unsigned char*)in, n, lvl);
640sdefl_adler32(
unsigned adler32,
const unsigned char *in,
int in_len) {
641 #define SDEFL_ADLER_INIT (1)
642 const unsigned ADLER_MOD = 65521;
643 unsigned s1 = adler32 & 0xffff;
644 unsigned s2 = adler32 >> 16;
647 blk_len = in_len % 5552;
649 for (i = 0; i + 7 < blk_len; i += 8) {
650 s1 += in[0]; s2 += s1;
651 s1 += in[1]; s2 += s1;
652 s1 += in[2]; s2 += s1;
653 s1 += in[3]; s2 += s1;
654 s1 += in[4]; s2 += s1;
655 s1 += in[5]; s2 += s1;
656 s1 += in[6]; s2 += s1;
657 s1 += in[7]; s2 += s1;
660 for (; i < blk_len; ++i) {
661 s1 += *in++, s2 += s1;
668 return (
unsigned)(s2 << 16) + (
unsigned)s1;
671zsdeflate(
struct sdefl *s,
void *out,
const void *in,
int n,
int lvl) {
674 unsigned char *q = (
unsigned char*)out;
677 sdefl_put(&q, s, 0x78, 8);
678 sdefl_put(&q, s, 0x01, 8);
679 q += sdefl_compr(s, q, (
const unsigned char*)in, n, lvl);
682 a = sdefl_adler32(SDEFL_ADLER_INIT, (
const unsigned char*)in, n);
683 for (p = 0; p < 4; ++p) {
684 sdefl_put(&q, s, (a >> 24) & 0xFF, 8);
687 return (
int)(q - (
unsigned char*)out);
691 int a = 128 + (len * 110) / 100;
692 int b = 128 + len + ((len / (31 * 1024)) + 1) * 5;
693 return (a > b) ? a : b;
int sdefl_bound(int in_len)
int sdeflate(struct sdefl *s, void *o, const void *i, int n, int lvl)
int zsdeflate(struct sdefl *s, void *o, const void *i, int n, int lvl)
unsigned off[SDEFL_OFF_MAX]
unsigned lit[SDEFL_SYM_MAX]
struct sdefl_code_words word
unsigned lit[SDEFL_SYM_MAX]
unsigned off[SDEFL_OFF_MAX]
unsigned char lit[SDEFL_SYM_MAX]
unsigned char off[SDEFL_OFF_MAX]
struct sdefl_seqt seq[SDEFL_SEQ_SIZ]