lzw_detail.cpp
compression/compressors/lzw/lzw_detail.cpp · 185 line(s) · c
/*
* Lempel-Ziv-Welch -- C++ implementation (see lzw_detail.h).
*
* Variable-width LZW, 9..12 bits, with an explicit CLEAR code (256) and a
* dictionary cap of 4096 entries; the dictionary resets when full, keeping
* memory and code width bounded. A self-describing header carries the original
* length so decode can size its output exactly. Reads are bounded and the
* header is validated, matching the codecs/ security posture.
*/
#include "lzw_detail.h"
#include <cstring>
#include <string>
#include <unordered_map>
#include <vector>
namespace {
constexpr size_t HDR = 4 + 8;
const uint8_t MAGIC[4] = { 'S', 'L', 'Z', 'W' };
constexpr int MIN_BITS = 9;
constexpr int MAX_BITS = 12;
constexpr int CLEAR_CODE = 256;
constexpr int FIRST_CODE = 257; /* first dictionary entry after CLEAR */
constexpr size_t MAX_ENTRIES = 1u << MAX_BITS;
void put_u64le(uint8_t *p, uint64_t v) { for (int i = 0; i < 8; ++i) p[i] = (uint8_t)((v >> (8 * i)) & 0xFF); }
uint64_t get_u64le(const uint8_t *p) { uint64_t v = 0; for (int i = 0; i < 8; ++i) v |= (uint64_t)p[i] << (8 * i); return v; }
int width_for(size_t next_code) {
int bits = MIN_BITS;
while (((size_t)1 << bits) < next_code + 1 && bits < MAX_BITS) ++bits;
return bits;
}
struct BitWriter {
uint8_t *out; size_t cap; size_t written; uint32_t acc; int nbits; bool overflow;
BitWriter(uint8_t *o, size_t c) : out(o), cap(c), written(0), acc(0), nbits(0), overflow(false) {}
void put(uint32_t code, int w) {
acc = (acc << w) | (code & ((1u << w) - 1));
nbits += w;
while (nbits >= 8) {
nbits -= 8;
byte((uint8_t)((acc >> nbits) & 0xFF));
}
}
void flush() { if (nbits) { byte((uint8_t)((acc << (8 - nbits)) & 0xFF)); nbits = 0; } }
void byte(uint8_t v) { if (out) { if (written >= cap) { overflow = true; return; } out[written] = v; } ++written; }
};
struct BitReader {
const uint8_t *in; size_t len; size_t pos; uint32_t acc; int nbits;
BitReader(const uint8_t *i, size_t l) : in(i), len(l), pos(0), acc(0), nbits(0) {}
bool get(int w, uint32_t &out_code) {
while (nbits < w) {
if (pos >= len) return false;
acc = (acc << 8) | in[pos++];
nbits += 8;
}
nbits -= w;
out_code = (acc >> nbits) & ((1u << w) - 1);
return true;
}
};
} // namespace
extern "C" sleela_compression_result sleela_lzw_encode(const uint8_t *input, size_t input_len,
uint8_t *out, size_t *out_len) {
if (!out_len) return SLEELA_COMPRESSION_ERR_INVALID;
if (input_len && !input) return SLEELA_COMPRESSION_ERR_INVALID;
/* Two passes: measure by encoding to a scratch vector, then (if out) copy. */
std::vector<uint8_t> scratch;
scratch.reserve(input_len / 2 + HDR + 8);
scratch.resize(HDR);
std::memcpy(scratch.data(), MAGIC, 4);
put_u64le(scratch.data() + 4, (uint64_t)input_len);
BitWriter bw(nullptr, 0);
/* Redirect BitWriter to the vector via a local lambda sink. */
std::vector<uint8_t> body;
{
std::unordered_map<std::string, int> dict;
auto reset = [&]() { dict.clear(); for (int i = 0; i < 256; ++i) dict[std::string(1, (char)i)] = i; };
reset();
size_t next = FIRST_CODE;
/* Local bit sink over `body`. */
uint32_t acc = 0; int nb = 0;
auto emit = [&](uint32_t code, int w) {
acc = (acc << w) | (code & ((1u << w) - 1));
nb += w;
while (nb >= 8) { nb -= 8; body.push_back((uint8_t)((acc >> nb) & 0xFF)); }
};
emit(CLEAR_CODE, width_for(next));
std::string cur;
for (size_t i = 0; i < input_len; ++i) {
std::string nxt = cur + (char)input[i];
if (dict.count(nxt)) {
cur = nxt;
} else {
emit(dict[cur], width_for(next));
if (next < MAX_ENTRIES) {
dict[nxt] = (int)next++;
} else {
emit(CLEAR_CODE, width_for(next));
reset();
next = FIRST_CODE;
}
cur = std::string(1, (char)input[i]);
}
}
if (!cur.empty()) emit(dict[cur], width_for(next));
if (nb) body.push_back((uint8_t)((acc << (8 - nb)) & 0xFF));
}
(void)bw;
size_t total = HDR + body.size();
if (!out) { *out_len = total; return SLEELA_COMPRESSION_OK; }
if (*out_len < total) { *out_len = total; return SLEELA_COMPRESSION_ERR_BUFFER; }
std::memcpy(out, scratch.data(), HDR);
if (!body.empty()) std::memcpy(out + HDR, body.data(), body.size());
*out_len = total;
return SLEELA_COMPRESSION_OK;
}
extern "C" sleela_compression_result sleela_lzw_decode(const uint8_t *input, size_t input_len,
uint8_t *out, size_t *out_len) {
if (!out_len) return SLEELA_COMPRESSION_ERR_INVALID;
if (input_len && !input) return SLEELA_COMPRESSION_ERR_INVALID;
if (input_len < HDR || std::memcmp(input, MAGIC, 4) != 0)
return SLEELA_COMPRESSION_ERR_FORMAT;
uint64_t orig = get_u64le(input + 4);
/* Decode to a scratch vector first so we can honour the sizing contract and
* validate the whole stream before touching the caller's buffer. */
std::vector<uint8_t> result;
result.reserve((size_t)orig);
BitReader br(input + HDR, input_len - HDR);
std::vector<std::string> dict;
auto reset = [&]() { dict.clear(); dict.resize(FIRST_CODE); for (int i = 0; i < 256; ++i) dict[i] = std::string(1, (char)i); };
reset();
size_t next = FIRST_CODE;
std::string prev;
bool have_prev = false;
while (result.size() < orig) {
int w = width_for(next);
uint32_t code;
if (!br.get(w, code)) return SLEELA_COMPRESSION_ERR_FORMAT; /* truncated */
if ((int)code == CLEAR_CODE) { reset(); next = FIRST_CODE; have_prev = false; continue; }
std::string entry;
if (code < dict.size() && !dict[code].empty()) {
entry = dict[code];
} else if (code == next && have_prev) {
entry = prev + prev[0]; /* KwKwK special case */
} else {
return SLEELA_COMPRESSION_ERR_FORMAT; /* invalid code */
}
result.insert(result.end(), entry.begin(), entry.end());
if (have_prev && next < MAX_ENTRIES) {
if (dict.size() <= next) dict.resize(next + 1);
dict[next++] = prev + entry[0];
}
prev = entry;
have_prev = true;
}
if (!out) { *out_len = result.size(); return SLEELA_COMPRESSION_OK; }
if (*out_len < result.size()) { *out_len = result.size(); return SLEELA_COMPRESSION_ERR_BUFFER; }
if (!result.empty()) std::memcpy(out, result.data(), result.size());
*out_len = result.size();
return SLEELA_COMPRESSION_OK;
}