Home /Modules/compression/huffman_detail.cpp

huffman_detail.cpp

compression/compressors/huffman/huffman_detail.cpp · 194 line(s) · c

/*
 * Canonical static Huffman -- C++ implementation (see huffman_detail.h).
 *
 * Length-limited canonical Huffman. The encoder counts symbol frequencies,
 * builds a Huffman tree, extracts per-symbol code lengths (capped at 32),
 * assigns canonical codes from the length table, and writes an MSB-first
 * bitstream behind a self-describing header. The decoder rebuilds the identical
 * canonical codes from the stored length table alone. Every read is bounded and
 * malformed headers are rejected, matching the codecs/ security posture.
 */

#include "huffman_detail.h"

#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>

namespace {

constexpr size_t HDR = 4 + 8 + 256;   /* magic + orig_len + length table */
const uint8_t MAGIC[4] = { 'S', 'H', 'F', '1' };

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;
}

/* Derive code lengths (<=32) for each present symbol from its frequency. */
void build_lengths(const uint64_t freq[256], uint8_t lengths[256]) {
    std::memset(lengths, 0, 256);

    struct Node { uint64_t w; int sym; int left; int right; };
    std::vector<Node> nodes;
    auto cmp = [&](int a, int b) { return nodes[a].w > nodes[b].w; };
    std::priority_queue<int, std::vector<int>, decltype(cmp)> pq(cmp);

    int present = 0;
    for (int s = 0; s < 256; ++s) {
        if (freq[s]) {
            nodes.push_back({ freq[s], s, -1, -1 });
            pq.push((int)nodes.size() - 1);
            ++present;
        }
    }
    if (present == 0) return;
    if (present == 1) { lengths[nodes[pq.top()].sym] = 1; return; }  /* single symbol */

    while (pq.size() > 1) {
        int a = pq.top(); pq.pop();
        int b = pq.top(); pq.pop();
        nodes.push_back({ nodes[a].w + nodes[b].w, -1, a, b });
        pq.push((int)nodes.size() - 1);
    }

    /* Walk the tree to assign depths (code lengths). */
    std::vector<std::pair<int,int>> stack; /* (node, depth) */
    stack.push_back({ pq.top(), 0 });
    while (!stack.empty()) {
        auto [n, d] = stack.back();
        stack.pop_back();
        if (nodes[n].sym >= 0) {
            int len = d ? d : 1;
            lengths[nodes[n].sym] = (uint8_t)std::min(len, 32);
        } else {
            stack.push_back({ nodes[n].left, d + 1 });
            stack.push_back({ nodes[n].right, d + 1 });
        }
    }
}

/* Assign canonical codes from a length table. codes[s] holds the right-aligned
 * code; use lengths[s] bits of it, MSB first. */
void canonical_codes(const uint8_t lengths[256], uint32_t codes[256]) {
    uint32_t count[33] = { 0 };
    for (int s = 0; s < 256; ++s) if (lengths[s]) ++count[lengths[s]];

    uint32_t next[33] = { 0 };
    uint32_t code = 0;
    for (int bits = 1; bits <= 32; ++bits) {
        code = (code + count[bits - 1]) << 1;
        next[bits] = code;
    }
    for (int s = 0; s < 256; ++s)
        if (lengths[s]) codes[s] = next[lengths[s]]++;
}

struct BitWriter {
    uint8_t *out; size_t cap; size_t written; uint8_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 bit(int b) {
        acc = (uint8_t)((acc << 1) | (b & 1));
        if (++nbits == 8) { byte(acc); acc = 0; nbits = 0; }
    }
    void put_code(uint32_t code, int len) { for (int i = len - 1; i >= 0; --i) bit((code >> i) & 1); }
    void flush() { if (nbits) { acc = (uint8_t)(acc << (8 - nbits)); byte(acc); acc = 0; nbits = 0; } }
    void byte(uint8_t v) {
        if (out) { if (written >= cap) { overflow = true; return; } out[written] = v; }
        ++written;
    }
};

} // namespace

extern "C" sleela_compression_result sleela_huffman_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;

    uint64_t freq[256] = { 0 };
    for (size_t i = 0; i < input_len; ++i) ++freq[input[i]];

    uint8_t lengths[256];
    build_lengths(freq, lengths);
    uint32_t codes[256] = { 0 };
    canonical_codes(lengths, codes);

    /* Compute payload bit count to size the output precisely. */
    uint64_t bits = 0;
    for (size_t i = 0; i < input_len; ++i) bits += lengths[input[i]];
    size_t payload = (size_t)((bits + 7) / 8);
    size_t total = HDR + payload;

    if (!out) { *out_len = total; return SLEELA_COMPRESSION_OK; }
    if (*out_len < total) { *out_len = total; return SLEELA_COMPRESSION_ERR_BUFFER; }

    std::memcpy(out, MAGIC, 4);
    put_u64le(out + 4, (uint64_t)input_len);
    std::memcpy(out + 12, lengths, 256);

    BitWriter bw(out + HDR, payload);
    for (size_t i = 0; i < input_len; ++i) bw.put_code(codes[input[i]], lengths[input[i]]);
    bw.flush();
    if (bw.overflow) return SLEELA_COMPRESSION_ERR_BUFFER;

    *out_len = total;
    return SLEELA_COMPRESSION_OK;
}

extern "C" sleela_compression_result sleela_huffman_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);
    const uint8_t *lengths = input + 12;

    if (!out) { *out_len = (size_t)orig; return SLEELA_COMPRESSION_OK; }
    if (*out_len < (size_t)orig) { *out_len = (size_t)orig; return SLEELA_COMPRESSION_ERR_BUFFER; }

    if (orig == 0) { *out_len = 0; return SLEELA_COMPRESSION_OK; }

    /* Rebuild canonical codes and a (code,len)->symbol lookup. */
    uint32_t codes[256] = { 0 };
    canonical_codes(lengths, codes);

    const uint8_t *payload = input + HDR;
    size_t payload_len = input_len - HDR;

    size_t out_pos = 0;
    size_t byte_pos = 0;
    int bit_pos = 0;          /* 0 = MSB of current byte */
    uint32_t cur = 0;
    int cur_len = 0;

    while (out_pos < orig) {
        if (byte_pos >= payload_len) return SLEELA_COMPRESSION_ERR_FORMAT; /* truncated */
        int b = (payload[byte_pos] >> (7 - bit_pos)) & 1;
        if (++bit_pos == 8) { bit_pos = 0; ++byte_pos; }

        cur = (cur << 1) | (uint32_t)b;
        ++cur_len;
        if (cur_len > 32) return SLEELA_COMPRESSION_ERR_FORMAT;

        for (int s = 0; s < 256; ++s) {
            if (lengths[s] == cur_len && codes[s] == cur) {
                out[out_pos++] = (uint8_t)s;
                cur = 0;
                cur_len = 0;
                break;
            }
        }
    }

    *out_len = (size_t)orig;
    return SLEELA_COMPRESSION_OK;
}