LordOS — a free, fast and secure GNU/Linux distribution based on Debian, with its own desktop environment: display server and Wayland compositor in C, a React UI engine on QuickJS, and private native apps.
C cdebiandesktop-environmentebpffirewalllandlocklinuxlinux-distributionopen-sourceprivacyquickjsraspberry-pi-5reactsecuritywaylandwayland-compositor
/* xz.c — decompressors for Debian's indexes: our own xz (LZMA2) and gzip (stb_image's
* inflate, which is already in lord-server for PNGs). All in memory: repository files are
* a few tens of MB.
*
* xz: container with one or more streams, blocks with a single LZMA2 filter (what Debian's
* repositories use; no BCJ or delta). Each block's check (CRC32 or CRC64) is verified, even
* though the compressed file already comes verified by the signed InRelease's SHA-256.
* The LZMA decoder follows the LZMA specification (Igor Pavlov) and the structure of xz-embedded (public domain). */
#include "xz.h"
#include "stb_image.h"
#include <stdlib.h>
#include <string.h>
typedef struct {
const uint8_t *in, *in_end;
uint32_t range, code;
int bad;
} Rc;
static inline uint8_t rc_byte(Rc *rc) {
if (rc->in >= rc->in_end) { rc->bad = 1; return 0; }
return *rc->in++;
}
static inline void rc_norm(Rc *rc) {
if (rc->range < (1u << 24)) { rc->range <<= 8; rc->code = rc->code << 8 | rc_byte(rc); }
}
static inline int rc_bit(Rc *rc, uint16_t *p) {
rc_norm(rc);
uint32_t bound = (rc->range >> 11) * *p;
if (rc->code < bound) { rc->range = bound; *p += (2048 - *p) >> 5; return 0; }
rc->range -= bound;
rc->code -= bound;
*p -= *p >> 5;
return 1;
}
static inline uint32_t rc_tree(Rc *rc, uint16_t *p, uint32_t limit) {
uint32_t s = 1;
do s = s << 1 | (uint32_t)rc_bit(rc, &p[s]); while (s < limit);
return s - limit;
}
/* Reverse tree; p[off + s] with s from 1 (off may be -1, as in dist_special). */
static inline uint32_t rc_tree_rev(Rc *rc, uint16_t *p, long off, int bits) {
uint32_t s = 1, r = 0;
for (int i = 0; i < bits; i++) {
int b = rc_bit(rc, &p[off + (long)s]);
s = s << 1 | (uint32_t)b;
r |= (uint32_t)b << i;
}
return r;
}
static inline uint32_t rc_direct(Rc *rc, int bits) {
uint32_t r = 0;
while (bits--) {
rc_norm(rc);
rc->range >>= 1;
rc->code -= rc->range;
uint32_t t = 0u - (rc->code >> 31);
rc->code += rc->range & t;
r = (r << 1) + (t + 1);
}
return r;
}
typedef struct { uint16_t choice, choice2, low[16][8], mid[16][8], high[256]; } LenDec;
typedef struct {
int lc, lp, pb, state;
uint32_t rep[4];
uint16_t is_match[12][16], is_rep[12], is_rep0[12], is_rep1[12], is_rep2[12], is_rep0_long[12][16];
uint16_t slot[4][64], special[114], align[16];
LenDec len, replen;
uint16_t lit[16][0x300]; /* lc + lp ≤ 4 in LZMA2 */
} Lzma;
static void lzma_reset(Lzma *z) {
z->state = 0;
memset(z->rep, 0, sizeof z->rep);
uint16_t *p = &z->is_match[0][0], *e = &z->lit[15][0x2ff] + 1;
while (p < e) *p++ = 1024;
}
static uint32_t len_dec(Rc *rc, LenDec *l, uint32_t ps) {
if (!rc_bit(rc, &l->choice)) return rc_tree(rc, l->low[ps], 8);
if (!rc_bit(rc, &l->choice2)) return 8 + rc_tree(rc, l->mid[ps], 8);
return 16 + rc_tree(rc, l->high, 256);
}
typedef struct { uint8_t *buf; size_t len, cap, max, dict_start; } Out;
static int out_reserve(Out *o, size_t more) {
if (o->len + more <= o->cap) return 0;
if (o->len + more > o->max) return -1;
size_t cap = o->cap ? o->cap : 1 << 20;
while (cap < o->len + more) cap *= 2;
if (cap > o->max) cap = o->max;
uint8_t *nb = realloc(o->buf, cap);
if (!nb) return -1;
o->buf = nb;
o->cap = cap;
return 0;
}
/* One LZMA chunk of LZMA2: decodes exactly `unpacked` bytes. */
static int lzma_chunk(Lzma *z, Rc *rc, Out *o, size_t unpacked) {
if (out_reserve(o, unpacked)) return -1;
size_t end = o->len + unpacked;
uint8_t *d = o->buf;
size_t pos = o->len;
uint32_t pbmask = (1u << z->pb) - 1, lpmask = (1u << z->lp) - 1;
while (pos < end && !rc->bad) {
uint32_t ps = (uint32_t)pos & pbmask;
if (!rc_bit(rc, &z->is_match[z->state][ps])) {
uint32_t prev = pos > o->dict_start ? d[pos - 1] : 0;
uint16_t *p = z->lit[(((uint32_t)pos & lpmask) << z->lc) + (prev >> (8 - z->lc))];
uint32_t sym;
if (z->state < 7) sym = rc_tree(rc, p, 0x100);
else {
if (pos - o->dict_start <= z->rep[0]) return -1;
uint32_t mb = (uint32_t)d[pos - z->rep[0] - 1] << 1, off = 0x100;
sym = 1;
do {
uint32_t mbit = mb & off;
mb <<= 1;
if (rc_bit(rc, &p[off + mbit + sym])) { sym = sym << 1 | 1; off = mbit; }
else { sym <<= 1; off ^= mbit; }
} while (sym < 0x100);
}
d[pos++] = (uint8_t)sym;
z->state = z->state < 4 ? 0 : z->state < 10 ? z->state - 3 : z->state - 6;
continue;
}
uint32_t len;
if (!rc_bit(rc, &z->is_rep[z->state])) {
z->rep[3] = z->rep[2]; z->rep[2] = z->rep[1]; z->rep[1] = z->rep[0];
len = len_dec(rc, &z->len, ps);
z->state = z->state < 7 ? 7 : 10;
uint32_t ls = len < 3 ? len : 3;
uint32_t slot = rc_tree(rc, z->slot[ls], 64);
if (slot < 4) z->rep[0] = slot;
else {
int bits = (int)(slot >> 1) - 1;
uint32_t dist = (2 | (slot & 1)) << bits;
if (slot < 14) dist += rc_tree_rev(rc, z->special, (long)dist - (long)slot - 1, bits);
else {
dist += rc_direct(rc, bits - 4) << 4;
dist += rc_tree_rev(rc, z->align, 0, 4);
}
z->rep[0] = dist;
if (dist == 0xFFFFFFFFu) return -1; /* end marker: not allowed in LZMA2 */
}
} else {
if (!rc_bit(rc, &z->is_rep0[z->state])) {
if (!rc_bit(rc, &z->is_rep0_long[z->state][ps])) {
z->state = z->state < 7 ? 9 : 11;
if (pos - o->dict_start <= z->rep[0]) return -1;
d[pos] = d[pos - z->rep[0] - 1];
pos++;
continue;
}
} else {
uint32_t dist;
if (!rc_bit(rc, &z->is_rep1[z->state])) dist = z->rep[1];
else {
if (!rc_bit(rc, &z->is_rep2[z->state])) dist = z->rep[2];
else { dist = z->rep[3]; z->rep[3] = z->rep[2]; }
z->rep[2] = z->rep[1];
}
z->rep[1] = z->rep[0];
z->rep[0] = dist;
}
len = len_dec(rc, &z->replen, ps);
z->state = z->state < 7 ? 8 : 11;
}
len += 2;
if (pos - o->dict_start <= z->rep[0] || len > end - pos) return -1;
const uint8_t *src = d + pos - z->rep[0] - 1;
for (uint32_t i = 0; i < len; i++) d[pos + i] = src[i];
pos += len;
}
o->len = pos;
return rc->bad ? -1 : 0;
}
static int lzma2(const uint8_t **pp, const uint8_t *end, Out *o, Lzma *z) {
const uint8_t *p = *pp;
int need_dict = 1, need_props = 1;
for (;;) {
if (p >= end) return -1;
uint8_t c = *p++;
if (c == 0) break;
if (c == 1 || c == 2) {
if (end - p < 2) return -1;
size_t n = ((size_t)p[0] << 8 | p[1]) + 1;
p += 2;
if (c == 1) { o->dict_start = o->len; need_dict = 0; }
else if (need_dict) return -1;
if ((size_t)(end - p) < n || out_reserve(o, n)) return -1;
memcpy(o->buf + o->len, p, n);
o->len += n;
p += n;
continue;
}
if (c < 0x80) return -1;
if (end - p < 4) return -1;
size_t unpacked = ((size_t)(c & 0x1f) << 16 | (size_t)p[0] << 8 | p[1]) + 1;
size_t packed = ((size_t)p[2] << 8 | p[3]) + 1;
p += 4;
int mode = (c >> 5) & 3;
if (mode == 3) { o->dict_start = o->len; need_dict = 0; }
else if (need_dict) return -1;
if (mode >= 2) {
if (p >= end) return -1;
int pr = *p++;
if (pr >= 225) return -1;
z->lc = pr % 9; pr /= 9;
z->lp = pr % 5;
z->pb = pr / 5;
if (z->lc + z->lp > 4) return -1;
need_props = 0;
} else if (need_props) return -1;
if (mode >= 1) lzma_reset(z);
if ((size_t)(end - p) < packed || packed < 5) return -1;
Rc rc = { p, p + packed, 0xFFFFFFFFu, 0, 0 };
if (rc_byte(&rc) != 0) return -1;
for (int i = 0; i < 4; i++) rc.code = rc.code << 8 | rc_byte(&rc);
if (lzma_chunk(z, &rc, o, unpacked)) return -1;
p += packed;
}
*pp = p;
return 0;
}
static int varint(const uint8_t **p, const uint8_t *end, uint64_t *v) {
*v = 0;
for (int i = 0; i < 9; i++) {
if (*p >= end) return -1;
uint8_t b = *(*p)++;
*v |= (uint64_t)(b & 0x7f) << (7 * i);
if (!(b & 0x80)) return 0;
}
return -1;
}
static uint32_t crc32(const uint8_t *p, size_t n) {
static uint32_t t[256];
if (!t[1]) for (uint32_t i = 0; i < 256; i++) { uint32_t c = i; for (int k = 0; k < 8; k++) c = c & 1 ? 0xEDB88320u ^ (c >> 1) : c >> 1; t[i] = c; }
uint32_t c = 0xFFFFFFFFu;
for (size_t i = 0; i < n; i++) c = t[(c ^ p[i]) & 0xff] ^ (c >> 8);
return ~c;
}
static uint64_t crc64(const uint8_t *p, size_t n) {
static uint64_t t[256];
if (!t[1]) for (uint64_t i = 0; i < 256; i++) { uint64_t c = i; for (int k = 0; k < 8; k++) c = c & 1 ? 0xC96C5795D7870F42ull ^ (c >> 1) : c >> 1; t[i] = c; }
uint64_t c = ~0ull;
for (size_t i = 0; i < n; i++) c = t[(c ^ p[i]) & 0xff] ^ (c >> 8);
return ~c;
}
int xz_decode(const uint8_t *in, size_t len, uint8_t **out, size_t *outlen, size_t max) {
static const uint8_t magic[6] = { 0xFD, '7', 'z', 'X', 'Z', 0 };
Out o = { NULL, 0, 0, max, 0 };
Lzma *z = malloc(sizeof *z);
if (!z) return -1;
const uint8_t *p = in, *end = in + len;
int streams = 0;
while (p < end) {
if (streams && !*p) { /* padding between streams */
if (end - p < 4 || p[1] || p[2] || p[3]) goto fail;
p += 4;
continue;
}
if (end - p < 12 || memcmp(p, magic, 6) || p[6] != 0) goto fail;
int check = p[7] & 0x0f;
if (crc32(p + 6, 2) != ((uint32_t)p[8] | (uint32_t)p[9] << 8 | (uint32_t)p[10] << 16 | (uint32_t)p[11] << 24)) goto fail;
size_t checklen = check == 0 ? 0 : check == 1 ? 4 : check == 4 ? 8 : check == 10 ? 32 : (size_t)4 << ((check - 1) / 3);
p += 12;
for (;;) { /* blocks */
if (p >= end) goto fail;
if (*p == 0) break; /* index */
const uint8_t *bstart = p;
size_t hsize = ((size_t)*p + 1) * 4;
if ((size_t)(end - p) < hsize) goto fail;
const uint8_t *h = p + 1, *hend = p + hsize - 4;
if (crc32(p, hsize - 4) != ((uint32_t)hend[0] | (uint32_t)hend[1] << 8 | (uint32_t)hend[2] << 16 | (uint32_t)hend[3] << 24)) goto fail;
uint8_t flags = *h++;
uint64_t v;
if (flags & 0x3c) goto fail;
if ((flags & 0x40) && varint(&h, hend, &v)) goto fail;
if ((flags & 0x80) && varint(&h, hend, &v)) goto fail;
if ((flags & 3) != 0) goto fail; /* a single filter */
uint64_t id, psize;
if (varint(&h, hend, &id) || varint(&h, hend, &psize) || id != 0x21 || psize != 1 || h >= hend) goto fail;
p += hsize;
size_t ostart = o.len;
if (lzma2(&p, end, &o, z)) goto fail;
while ((p - bstart) & 3) { if (p >= end || *p) goto fail; p++; }
if ((size_t)(end - p) < checklen) goto fail;
if (check == 1 || check == 4) { /* CRC32 or CRC64 (little-endian) */
uint64_t want = 0, got = check == 1 ? crc32(o.buf + ostart, o.len - ostart) : crc64(o.buf + ostart, o.len - ostart);
for (size_t i = 0; i < checklen; i++) want |= (uint64_t)p[i] << (8 * i);
if (want != got) goto fail;
}
p += checklen;
}
/* index: 0, count, (sizes)…, padding, CRC32; then the 12-byte footer */
p++;
const uint8_t *istart = p - 1;
uint64_t nrec, a, b;
if (varint(&p, end, &nrec)) goto fail;
for (uint64_t i = 0; i < nrec; i++) if (varint(&p, end, &a) || varint(&p, end, &b)) goto fail;
while ((p - istart) & 3) { if (p >= end) goto fail; p++; }
if (end - p < 4 + 12) goto fail;
if (crc32(istart, (size_t)(p - istart)) != ((uint32_t)p[0] | (uint32_t)p[1] << 8 | (uint32_t)p[2] << 16 | (uint32_t)p[3] << 24)) goto fail;
p += 4;
/* footer: CRC32, index size, flags (same as the header's), "YZ" */
if (p[10] != 'Y' || p[11] != 'Z' || p[8] != 0 || (p[9] & 0x0f) != check ||
crc32(p + 4, 6) != ((uint32_t)p[0] | (uint32_t)p[1] << 8 | (uint32_t)p[2] << 16 | (uint32_t)p[3] << 24)) goto fail;
p += 12;
streams++;
}
free(z);
if (!streams) { free(o.buf); return -1; }
*out = o.buf ? o.buf : malloc(1);
*outlen = o.len;
return 0;
fail:
free(z);
free(o.buf);
return -1;
}
int gz_decode(const uint8_t *in, size_t len, uint8_t **out, size_t *outlen, size_t max) {
if (len < 18 || in[0] != 0x1f || in[1] != 0x8b || in[2] != 8 || len > 0x7fffffff) return -1;
uint8_t flg = in[3];
size_t p = 10;
if (flg & 4) { if (p + 2 > len) return -1; p += 2 + (size_t)(in[p] | in[p + 1] << 8); }
if (flg & 8) { while (p < len && in[p]) p++; p++; }
if (flg & 16) { while (p < len && in[p]) p++; p++; }
if (flg & 2) p += 2;
if (p + 8 > len) return -1;
/* the original size (mod 2^32) is at the end: it serves as a first estimate */
uint32_t isize = (uint32_t)in[len - 4] | (uint32_t)in[len - 3] << 8 | (uint32_t)in[len - 2] << 16 | (uint32_t)in[len - 1] << 24;
if (isize > max) return -1;
int n = 0;
char *r = stbi_zlib_decode_noheader_malloc((const char *)in + p, (int)(len - p - 8), &n);
if (!r) return -1;
if ((size_t)n > max) { free(r); return -1; }
*out = (uint8_t *)r;
*outlen = (size_t)n;
return 0;
}