From 3a1d97f556bc4c5384799ac121640984b590c05c Mon Sep 17 00:00:00 2001 From: Thomas Date: Sun, 15 Aug 2021 10:03:09 +0200 Subject: Updated to raylib 3.7 --- libs/raylib/src/external/sinfl.h | 464 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 464 insertions(+) create mode 100644 libs/raylib/src/external/sinfl.h (limited to 'libs/raylib/src/external/sinfl.h') diff --git a/libs/raylib/src/external/sinfl.h b/libs/raylib/src/external/sinfl.h new file mode 100644 index 0000000..37c1aae --- /dev/null +++ b/libs/raylib/src/external/sinfl.h @@ -0,0 +1,464 @@ +/* +# Small Deflate +`sdefl` is a small bare bone lossless compression library in ANSI C (ISO C90) +which implements the Deflate (RFC 1951) compressed data format specification standard. +It is mainly tuned to get as much speed and compression ratio from as little code +as needed to keep the implementation as concise as possible. + +## Features +- Portable single header and source file duo written in ANSI C (ISO C90) +- Dual license with either MIT or public domain +- Small implementation + - Deflate: 525 LoC + - Inflate: 320 LoC +- Webassembly: + - Deflate ~3.7 KB (~2.2KB compressed) + - Inflate ~3.6 KB (~2.2KB compressed) + +## Usage: +This file behaves differently depending on what symbols you define +before including it. + +Header-File mode: +If you do not define `SINFL_IMPLEMENTATION` before including this file, it +will operate in header only mode. In this mode it declares all used structs +and the API of the library without including the implementation of the library. + +Implementation mode: +If you define `SINFL_IMPLEMENTATION` before including this file, it will +compile the implementation. Make sure that you only include +this file implementation in *one* C or C++ file to prevent collisions. + +### Benchmark + +| Compressor name | Compression| Decompress.| Compr. size | Ratio | +| ------------------------| -----------| -----------| ----------- | ----- | +| sdefl 1.0 -0 | 127 MB/s | 233 MB/s | 40004116 | 39.88 | +| sdefl 1.0 -1 | 111 MB/s | 259 MB/s | 38940674 | 38.82 | +| sdefl 1.0 -5 | 45 MB/s | 275 MB/s | 36577183 | 36.46 | +| sdefl 1.0 -7 | 38 MB/s | 276 MB/s | 36523781 | 36.41 | +| zlib 1.2.11 -1 | 72 MB/s | 307 MB/s | 42298774 | 42.30 | +| zlib 1.2.11 -6 | 24 MB/s | 313 MB/s | 36548921 | 36.55 | +| zlib 1.2.11 -9 | 20 MB/s | 314 MB/s | 36475792 | 36.48 | +| miniz 1.0 -1 | 122 MB/s | 208 MB/s | 48510028 | 48.51 | +| miniz 1.0 -6 | 27 MB/s | 260 MB/s | 36513697 | 36.51 | +| miniz 1.0 -9 | 23 MB/s | 261 MB/s | 36460101 | 36.46 | +| libdeflate 1.3 -1 | 147 MB/s | 667 MB/s | 39597378 | 39.60 | +| libdeflate 1.3 -6 | 69 MB/s | 689 MB/s | 36648318 | 36.65 | +| libdeflate 1.3 -9 | 13 MB/s | 672 MB/s | 35197141 | 35.20 | +| libdeflate 1.3 -12 | 8.13 MB/s | 670 MB/s | 35100568 | 35.10 | + +### Compression +Results on the [Silesia compression corpus](http://sun.aei.polsl.pl/~sdeor/index.php?page=silesia): + +| File | Original | `sdefl 0` | `sdefl 5` | `sdefl 7` | +| :------ | ---------: | -----------------: | ---------: | ----------: | +| dickens | 10.192.446 | 4,260,187| 3,845,261| 3,833,657 | +| mozilla | 51.220.480 | 20,774,706 | 19,607,009 | 19,565,867 | +| mr | 9.970.564 | 3,860,531 | 3,673,460 | 3,665,627 | +| nci | 33.553.445 | 4,030,283 | 3,094,526 | 3,006,075 | +| ooffice | 6.152.192 | 3,320,063 | 3,186,373 | 3,183,815 | +| osdb | 10.085.684 | 3,919,646 | 3,649,510 | 3,649,477 | +| reymont | 6.627.202 | 2,263,378 | 1,857,588 | 1,827,237 | +| samba | 21.606.400 | 6,121,797 | 5,462,670 | 5,450,762 | +| sao | 7.251.944 | 5,612,421 | 5,485,380 | 5,481,765 | +| webster | 41.458.703 | 13,972,648 | 12,059,432 | 11,991,421 | +| xml | 5.345.280 | 886,620| 674,009 | 662,141 | +| x-ray | 8.474.240 | 6,304,655 | 6,244,779 | 6,244,779 | + +## License +``` +------------------------------------------------------------------------------ +This software is available under 2 licenses -- choose whichever you prefer. +------------------------------------------------------------------------------ +ALTERNATIVE A - MIT License +Copyright (c) 2020 Micha Mettke +Permission is hereby granted, free of charge, to any person obtaining a copy of +this software and associated documentation files (the "Software"), to deal in +the Software without restriction, including without limitation the rights to +use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies +of the Software, and to permit persons to whom the Software is furnished to do +so, subject to the following conditions: +The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software. +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +SOFTWARE. +------------------------------------------------------------------------------ +ALTERNATIVE B - Public Domain (www.unlicense.org) +This is free and unencumbered software released into the public domain. +Anyone is free to copy, modify, publish, use, compile, sell, or distribute this +software, either in source code form or as a compiled binary, for any purpose, +commercial or non-commercial, and by any means. +In jurisdictions that recognize copyright laws, the author or authors of this +software dedicate any and all copyright interest in the software to the public +domain. We make this dedication for the benefit of the public at large and to +the detriment of our heirs and successors. We intend this dedication to be an +overt act of relinquishment in perpetuity of all present and future rights to +this software under copyright law. +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN +ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION +WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. +------------------------------------------------------------------------------ +``` +*/ +#ifndef SINFL_H_INCLUDED +#define SINFL_H_INCLUDED + +#ifdef __cplusplus +extern "C" { +#endif + +#define SINFL_PRE_TBL_SIZE 128 +#define SINFL_LIT_TBL_SIZE 1334 +#define SINFL_OFF_TBL_SIZE 402 + +struct sinfl { + int bits, bitcnt; + unsigned lits[SINFL_LIT_TBL_SIZE]; + unsigned dsts[SINFL_OFF_TBL_SIZE]; +}; +extern int sinflate(void *out, const void *in, int size); +extern int zsinflate(void *out, const void *in, int size); + +#ifdef __cplusplus +} +#endif + +#endif /* SINFL_H_INCLUDED */ + +#ifdef SINFL_IMPLEMENTATION + +#include /* memcpy, memset */ + +static int +sinfl_bsr(unsigned n) { +#ifdef _MSC_VER + _BitScanReverse(&n, n); + return n; +#elif defined(__GNUC__) || defined(__clang__) + return 31 - __builtin_clz(n); +#endif +} +static int +sinfl_get(const unsigned char **src, const unsigned char *end, struct sinfl *s, + int n) { + const unsigned char *in = *src; + int v = s->bits & ((1 << n)-1); + s->bits >>= n; + s->bitcnt = s->bitcnt - n; + s->bitcnt = s->bitcnt < 0 ? 0 : s->bitcnt; + while (s->bitcnt < 16 && in < end) { + s->bits |= (*in++) << s->bitcnt; + s->bitcnt += 8; + } + *src = in; + return v; +} +struct sinfl_gen { + int len; + int cnt; + int word; + short* sorted; +}; +static int +sinfl_build_tbl(struct sinfl_gen *gen, unsigned *tbl, int tbl_bits, + const int *cnt) { + int tbl_end = 0; + while (!(gen->cnt = cnt[gen->len])) { + ++gen->len; + } + tbl_end = 1 << gen->len; + while (gen->len <= tbl_bits) { + do {unsigned bit = 0; + tbl[gen->word] = (*gen->sorted++ << 16) | gen->len; + if (gen->word == tbl_end - 1) { + for (; gen->len < tbl_bits; gen->len++) { + memcpy(&tbl[tbl_end], tbl, (size_t)tbl_end * sizeof(tbl[0])); + tbl_end <<= 1; + } + return 1; + } + bit = 1 << sinfl_bsr((unsigned)(gen->word ^ (tbl_end - 1))); + gen->word &= bit - 1; + gen->word |= bit; + } while (--gen->cnt); + do { + if (++gen->len <= tbl_bits) { + memcpy(&tbl[tbl_end], tbl, (size_t)tbl_end * sizeof(tbl[0])); + tbl_end <<= 1; + } + } while (!(gen->cnt = cnt[gen->len])); + } + return 0; +} +static void +sinfl_build_subtbl(struct sinfl_gen *gen, unsigned *tbl, int tbl_bits, + const int *cnt) { + int sub_bits = 0; + int sub_start = 0; + int sub_prefix = -1; + int tbl_end = 1 << tbl_bits; + while (1) { + unsigned entry; + int bit, stride, i; + /* start new subtable */ + if ((gen->word & ((1 << tbl_bits)-1)) != sub_prefix) { + int used = 0; + sub_prefix = gen->word & ((1 << tbl_bits)-1); + sub_start = tbl_end; + sub_bits = gen->len - tbl_bits; + used = gen->cnt; + while (used < (1 << sub_bits)) { + sub_bits++; + used = (used << 1) + cnt[tbl_bits + sub_bits]; + } + tbl_end = sub_start + (1 << sub_bits); + tbl[sub_prefix] = (sub_start << 16) | 0x10 | (sub_bits & 0xf); + } + /* fill subtable */ + entry = (*gen->sorted << 16) | ((gen->len - tbl_bits) & 0xf); + gen->sorted++; + i = sub_start + (gen->word >> tbl_bits); + stride = 1 << (gen->len - tbl_bits); + do { + tbl[i] = entry; + i += stride; + } while (i < tbl_end); + if (gen->word == (1 << gen->len)-1) { + return; + } + bit = 1 << sinfl_bsr(gen->word ^ ((1 << gen->len) - 1)); + gen->word &= bit - 1; + gen->word |= bit; + gen->cnt--; + while (!gen->cnt) { + gen->cnt = cnt[++gen->len]; + } + } +} +static void +sinfl_build(unsigned *tbl, unsigned char *lens, int tbl_bits, int maxlen, + int symcnt) { + int i, used = 0; + short sort[288]; + int cnt[16] = {0}, off[16]= {0}; + struct sinfl_gen gen = {0}; + gen.sorted = sort; + gen.len = 1; + + for (i = 0; i < symcnt; ++i) + cnt[lens[i]]++; + off[1] = cnt[0]; + for (i = 1; i < maxlen; ++i) { + off[i + 1] = off[i] + cnt[i]; + used = (used << 1) + cnt[i]; + } + used = (used << 1) + cnt[i]; + for (i = 0; i < symcnt; ++i) + gen.sorted[off[lens[i]]++] = (short)i; + gen.sorted += off[0]; + + if (used < (1 << maxlen)){ + for (i = 0; i < 1 << tbl_bits; ++i) + tbl[i] = (0 << 16u) | 1; + return; + } + if (!sinfl_build_tbl(&gen, tbl, tbl_bits, cnt)){ + sinfl_build_subtbl(&gen, tbl, tbl_bits, cnt); + } +} +static int +sinfl_decode(const unsigned char **in, const unsigned char *end, + struct sinfl *s, const unsigned *tbl, int bit_len) { + int idx = s->bits & ((1 << bit_len) - 1); + unsigned key = tbl[idx]; + if (key & 0x10) { + /* sub-table lookup */ + int len = key & 0x0f; + sinfl_get(in, end, s, bit_len); + idx = s->bits & ((1 << len)-1); + key = tbl[((key >> 16) & 0xffff) + (unsigned)idx]; + } + sinfl_get(in, end, s, key & 0x0f); + return (key >> 16) & 0x0fff; +} +static int +sinfl_decompress(unsigned char *out, const unsigned char *in, int size) { + static const unsigned char order[] = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15}; + static const short dbase[30+2] = {1,2,3,4,5,7,9,13,17,25,33,49,65,97,129,193, + 257,385,513,769,1025,1537,2049,3073,4097,6145,8193,12289,16385,24577}; + static const unsigned char dbits[30+2] = {0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9, + 10,10,11,11,12,12,13,13,0,0}; + static const short lbase[29+2] = {3,4,5,6,7,8,9,10,11,13,15,17,19,23,27,31,35, + 43,51,59,67,83,99,115,131,163,195,227,258,0,0}; + static const unsigned char lbits[29+2] = {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,0,0}; + + const unsigned char *e = in + size, *o = out; + enum sinfl_states {hdr,stored,fixed,dyn,blk}; + enum sinfl_states state = hdr; + struct sinfl s = {0}; + int last = 0; + + sinfl_get(&in,e,&s,0); /* buffer input */ + while (in < e || s.bitcnt) { + switch (state) { + case hdr: { + int type = 0; /* block header */ + last = sinfl_get(&in,e,&s,1); + type = sinfl_get(&in,e,&s,2); + + switch (type) {default: return (int)(out-o); + case 0x00: state = stored; break; + case 0x01: state = fixed; break; + case 0x02: state = dyn; break;} + } break; + case stored: { + int len; /* uncompressed block */ + sinfl_get(&in,e,&s,s.bitcnt & 7); + len = sinfl_get(&in,e,&s,16); + //int nlen = sinfl_get(&in,e,&s,16); + in -= 2; s.bitcnt = 0; + + if (len > (e-in) || !len) + return (int)(out-o); + memcpy(out, in, (size_t)len); + in += len, out += len; + state = hdr; + } break; + case fixed: { + /* fixed huffman codes */ + int n; unsigned char lens[288+32]; + for (n = 0; n <= 143; n++) lens[n] = 8; + for (n = 144; n <= 255; n++) lens[n] = 9; + for (n = 256; n <= 279; n++) lens[n] = 7; + for (n = 280; n <= 287; n++) lens[n] = 8; + for (n = 0; n < 32; n++) lens[288+n] = 5; + + /* build lit/dist tables */ + sinfl_build(s.lits, lens, 10, 15, 288); + sinfl_build(s.dsts, lens + 288, 8, 15, 32); + state = blk; + } break; + case dyn: { + /* dynamic huffman codes */ + int n, i; + unsigned hlens[SINFL_PRE_TBL_SIZE]; + unsigned char nlens[19] = {0}, lens[288+32]; + int nlit = 257 + sinfl_get(&in,e,&s,5); + int ndist = 1 + sinfl_get(&in,e,&s,5); + int nlen = 4 + sinfl_get(&in,e,&s,4); + for (n = 0; n < nlen; n++) + nlens[order[n]] = (unsigned char)sinfl_get(&in,e,&s,3); + sinfl_build(hlens, nlens, 7, 7, 19); + + /* decode code lengths */ + for (n = 0; n < nlit + ndist;) { + int sym = sinfl_decode(&in, e, &s, hlens, 7); + switch (sym) {default: lens[n++] = (unsigned char)sym; break; + case 16: for (i=3+sinfl_get(&in,e,&s,2);i;i--,n++) lens[n]=lens[n-1]; break; + case 17: for (i=3+sinfl_get(&in,e,&s,3);i;i--,n++) lens[n]=0; break; + case 18: for (i=11+sinfl_get(&in,e,&s,7);i;i--,n++) lens[n]=0; break;} + } + /* build lit/dist tables */ + sinfl_build(s.lits, lens, 10, 15, nlit); + sinfl_build(s.dsts, lens + nlit, 8, 15, ndist); + state = blk; + } break; + case blk: { + /* decompress block */ + int i, sym = sinfl_decode(&in, e, &s, s.lits, 10); + if (sym > 256) {sym -= 257; /* match symbol */ + {int len = sinfl_get(&in, e, &s, lbits[sym]) + lbase[sym]; + int dsym = sinfl_decode(&in, e, &s, s.dsts, 8); + int offs = sinfl_get(&in, e, &s, dbits[dsym]) + dbase[dsym]; + if (offs > (int)(out-o)) { + return (int)(out-o); + } else if (offs == 1) { + /* rle match copying */ + unsigned char c = *(out - offs); + unsigned long w = (c << 24) | (c << 16) | (c << 8) | c; + for (i = 0; i < len >> 2; ++i) { + memcpy(out, &w, 4); + out += 4; + } + len = len & 3; + } else if (offs >= 4) { + /* copy match */ + int wcnt = len >> 2; + for (i = 0; i < wcnt; ++i) { + unsigned long w = 0; + memcpy(&w, out - offs, 4); + memcpy(out, &w, 4); + out += 4; + } + len = len & 3; + } + for (i = 0; i < len; ++i) + {*out = *(out-offs), out++;} + } + } else if (sym == 256) { + /* end of block */ + if (last) return (int)(out-o); + state = hdr; + break; + /* literal */ + } else *out++ = (unsigned char)sym; + } break;} + } + return (int)(out-o); +} +extern int +sinflate(void *out, const void *in, int size) { + return sinfl_decompress((unsigned char*)out, (const unsigned char*)in, size); +} +static unsigned +sinfl_adler32(unsigned adler32, const unsigned char *in, int in_len) { + const unsigned ADLER_MOD = 65521; + unsigned s1 = adler32 & 0xffff; + unsigned s2 = adler32 >> 16; + unsigned blk_len, i; + + blk_len = in_len % 5552; + while (in_len) { + for (i=0; i + 7 < blk_len; i += 8) { + s1 += in[0]; s2 += s1; + s1 += in[1]; s2 += s1; + s1 += in[2]; s2 += s1; + s1 += in[3]; s2 += s1; + s1 += in[4]; s2 += s1; + s1 += in[5]; s2 += s1; + s1 += in[6]; s2 += s1; + s1 += in[7]; s2 += s1; + in += 8; + } + for (; i < blk_len; ++i) + s1 += *in++, s2 += s1; + s1 %= ADLER_MOD; s2 %= ADLER_MOD; + in_len -= blk_len; + blk_len = 5552; + } return (unsigned)(s2 << 16) + (unsigned)s1; +} +extern int +zsinflate(void *out, const void *mem, int size) { + const unsigned char *in = (const unsigned char*)mem; + if (size >= 6) { + const unsigned char *eob = in + size - 4; + int n = sinfl_decompress((unsigned char*)out, in + 2u, size); + unsigned a = sinfl_adler32(1u, (unsigned char*)out, n); + unsigned h = eob[0] << 24 | eob[1] << 16 | eob[2] << 8 | eob[3] << 0; + return a == h ? n : -1; + } else { + return -1; + } +} +#endif + -- cgit v1.2.3