260 lines
8.7 KiB
C
260 lines
8.7 KiB
C
/*-*- mode:c;indent-tabs-mode:nil;c-basic-offset:2;tab-width:8;coding:utf-8 -*-│
|
|
│vi: set net ft=c ts=2 sts=2 sw=2 fenc=utf-8 :vi│
|
|
╞══════════════════════════════════════════════════════════════════════════════╡
|
|
│ Copyright 2020 Justine Alexandra Roberts Tunney │
|
|
│ │
|
|
│ Permission to use, copy, modify, and/or distribute this software for │
|
|
│ any purpose with or without fee is hereby granted, provided that the │
|
|
│ above copyright notice and this permission notice appear in all copies. │
|
|
│ │
|
|
│ THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL │
|
|
│ WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED │
|
|
│ WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE │
|
|
│ AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL │
|
|
│ DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR │
|
|
│ PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER │
|
|
│ TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR │
|
|
│ PERFORMANCE OF THIS SOFTWARE. │
|
|
╚─────────────────────────────────────────────────────────────────────────────*/
|
|
#include "libc/assert.h"
|
|
#include "libc/bits/bits.h"
|
|
#include "libc/intrin/repmovsb.h"
|
|
#include "libc/macros.h"
|
|
#include "libc/nexgen32e/kompressor.h"
|
|
#include "libc/str/str.h"
|
|
#include "libc/str/undeflate.h"
|
|
|
|
#define kDeflateCompressionTypeNone 0b00
|
|
#define kDeflateCompressionTypeFixedHuffman 0b01
|
|
#define kDeflateCompressionTypeDynamicHuffman 0b10
|
|
|
|
#define kDeflateCodeLengthCopyPrevious3To6Times 16
|
|
#define kDeflateCodeLengthRepeatZero3To10Times 17
|
|
#define kDeflateCodeLengthRepeatZero11To138Times 18
|
|
|
|
#define CONSUME(BITS) \
|
|
hold.word >>= BITS; \
|
|
hold.bits -= BITS
|
|
|
|
#define MOAR(BITS) \
|
|
while (hold.bits < BITS) { \
|
|
al = *ip++; \
|
|
hold.word |= (size_t)al << hold.bits; \
|
|
hold.bits += 8; \
|
|
}
|
|
|
|
struct DeflateHold {
|
|
size_t word;
|
|
size_t bits;
|
|
};
|
|
|
|
static const struct DeflateConsts {
|
|
uint16_t lenbase[32];
|
|
uint16_t distbase[32];
|
|
uint8_t lenbits[32];
|
|
uint8_t distbits[32];
|
|
uint8_t orders[19];
|
|
struct RlDecode lensrl[6];
|
|
} kDeflate = {
|
|
{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},
|
|
{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},
|
|
{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, 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},
|
|
{16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15},
|
|
{{144, 8}, {112, 9}, {24, 7}, {8, 8}, {32, 5}, {0, 0}},
|
|
};
|
|
|
|
static uint32_t undeflatetree(struct DeflateState *ds, uint32_t *tree,
|
|
const uint8_t *lens, size_t symcount) {
|
|
size_t i, len;
|
|
uint32_t code, slot;
|
|
uint16_t codes[16], first[16], counts[16];
|
|
memset(counts, 0, sizeof(counts));
|
|
for (i = 0; i < symcount; i++) {
|
|
counts[lens[i]]++;
|
|
}
|
|
codes[0] = 0;
|
|
first[0] = 0;
|
|
counts[0] = 0;
|
|
for (i = 1; i < ARRAYLEN(codes); i++) {
|
|
codes[i] = (codes[i - 1] + counts[i - 1]) << 1;
|
|
first[i] = first[i - 1] + counts[i - 1];
|
|
}
|
|
assert(first[15] + counts[15] <= symcount);
|
|
for (i = 0; i < symcount; i++) {
|
|
if ((len = lens[i])) {
|
|
code = codes[len]++;
|
|
slot = first[len]++;
|
|
tree[slot] = code << (32 - len) | i << 4 | len;
|
|
}
|
|
}
|
|
return first[15];
|
|
}
|
|
|
|
static struct DeflateHold undeflatesymbol(struct DeflateHold hold,
|
|
const uint32_t *tree,
|
|
size_t treecount,
|
|
uint32_t *out_symbol) {
|
|
size_t left, right, m;
|
|
uint32_t search, key;
|
|
left = 0;
|
|
right = treecount;
|
|
search = bitreverse16(hold.word);
|
|
search <<= 16;
|
|
search |= 0xffff;
|
|
while (left < right) { /* TODO(jart): Make this O(1) like Zlib. */
|
|
m = (left + right) >> 1;
|
|
if (search < tree[m]) {
|
|
right = m;
|
|
} else {
|
|
left = m + 1;
|
|
}
|
|
}
|
|
key = tree[left - 1];
|
|
assert(!((search ^ key) >> (32 - (key & 0xf))));
|
|
*out_symbol = (key >> 4) & 0xfff;
|
|
CONSUME(key & 0xf);
|
|
return hold;
|
|
}
|
|
|
|
/**
|
|
* Decompresses raw DEFLATE data.
|
|
*
|
|
* This is 10x smaller and 10x slower than chromium zlib.
|
|
*
|
|
* @param output should be followed by a single guard page, and have
|
|
* 36kb of guard pages preceding it too
|
|
* @note h/t Phil Katz, David Huffman, Claude Shannon
|
|
*/
|
|
ssize_t undeflate(void *output, size_t outputsize, void *input,
|
|
size_t inputsize, struct DeflateState *ds) {
|
|
struct DeflateHold hold;
|
|
bool isfinalblock;
|
|
size_t i, nlit, ndist;
|
|
uint8_t *ip, *op, *si, b, al, last, compressiontype;
|
|
uint32_t j, l, len, sym, tlit, tdist, tlen, nlen;
|
|
|
|
op = output;
|
|
ip = input;
|
|
hold.word = 0;
|
|
hold.bits = 0;
|
|
isfinalblock = 0;
|
|
|
|
while (!isfinalblock) {
|
|
MOAR(3);
|
|
isfinalblock = hold.word & 0b1;
|
|
CONSUME(1);
|
|
compressiontype = hold.word & 0b11;
|
|
CONSUME(2);
|
|
|
|
switch (compressiontype) {
|
|
case kDeflateCompressionTypeNone:
|
|
CONSUME(hold.bits & 7);
|
|
MOAR(32);
|
|
len = hold.word & 0xffff;
|
|
nlen = (hold.word >> 16) & 0xffff;
|
|
assert(len == ~nlen);
|
|
CONSUME(32);
|
|
while (len--) {
|
|
if (hold.bits) {
|
|
*op++ = hold.word;
|
|
CONSUME(8);
|
|
} else {
|
|
*op++ = *ip++;
|
|
}
|
|
}
|
|
continue;
|
|
|
|
case kDeflateCompressionTypeFixedHuffman:
|
|
nlit = 288;
|
|
ndist = 32;
|
|
rldecode(ds->lens, kDeflate.lensrl);
|
|
break;
|
|
|
|
case kDeflateCompressionTypeDynamicHuffman:
|
|
MOAR(5 + 5 + 4);
|
|
nlit = (hold.word & 0b11111) + 257;
|
|
CONSUME(5);
|
|
ndist = (hold.word & 0b11111) + 1;
|
|
CONSUME(5);
|
|
nlen = (hold.word & 0b1111) + 4;
|
|
CONSUME(4);
|
|
for (i = 0; i < nlen; i++) {
|
|
MOAR(3);
|
|
ds->lenlens[kDeflate.orders[i]] = hold.word & 0b111;
|
|
CONSUME(3);
|
|
}
|
|
for (; i < ARRAYLEN(ds->lenlens); i++) {
|
|
ds->lenlens[kDeflate.orders[i]] = 0;
|
|
}
|
|
tlen =
|
|
undeflatetree(ds, ds->lencodes, ds->lenlens, ARRAYLEN(ds->lenlens));
|
|
i = 0;
|
|
last = 0;
|
|
while (i < nlit + ndist) {
|
|
MOAR(16);
|
|
hold = undeflatesymbol(hold, ds->lencodes, tlen, &sym);
|
|
b = 2;
|
|
j = 1;
|
|
switch (sym) {
|
|
case kDeflateCodeLengthRepeatZero11To138Times:
|
|
b += 4;
|
|
j += 8;
|
|
/* fallthrough */
|
|
case kDeflateCodeLengthRepeatZero3To10Times:
|
|
b += 1;
|
|
last = 0;
|
|
/* fallthrough */
|
|
case kDeflateCodeLengthCopyPrevious3To6Times:
|
|
MOAR(b);
|
|
j += (hold.word & ((1u << b) - 1u)) + 2u;
|
|
CONSUME(b);
|
|
break;
|
|
default:
|
|
last = sym;
|
|
break;
|
|
}
|
|
while (j--) {
|
|
ds->lens[i++] = last;
|
|
}
|
|
}
|
|
break;
|
|
default:
|
|
return -1;
|
|
}
|
|
|
|
tlit = undeflatetree(ds, ds->litcodes, ds->lens, nlit);
|
|
tdist = undeflatetree(ds, ds->distcodes, &ds->lens[nlit], ndist);
|
|
|
|
do {
|
|
MOAR(16);
|
|
hold = undeflatesymbol(hold, ds->litcodes, tlit, &sym);
|
|
if (sym < 256) {
|
|
*op++ = sym;
|
|
} else if (sym > 256) {
|
|
sym -= 257;
|
|
b = kDeflate.lenbits[sym];
|
|
MOAR(b);
|
|
l = kDeflate.lenbase[sym] + (hold.word & ((1u << b) - 1));
|
|
CONSUME(b);
|
|
MOAR(16);
|
|
hold = undeflatesymbol(hold, ds->distcodes, tdist, &sym);
|
|
b = kDeflate.distbits[sym];
|
|
MOAR(b);
|
|
/* max readback: 24577 + 2**13-1 = 32768 */
|
|
si = op - ((uint32_t)kDeflate.distbase[sym] +
|
|
(uint32_t)(hold.word & ((1u << b) - 1)));
|
|
CONSUME(b);
|
|
repmovsb(&op, &si, l);
|
|
}
|
|
} while (sym != 256);
|
|
}
|
|
|
|
return 0;
|
|
}
|