whiteoutlib 0.1.4

// SPDX-License-Identifier: BSD-3-Clause
// Copyright (c) 2026 Fernando Sahmkow

#include "huffman.h"

#include <array>
#include <cstring>

namespace whiteout::storages::mpq {

namespace {

// ============================================================================
// Constants
// ============================================================================

static constexpr u32 kHuffItemCount = 0x203;   // Max items in the tree pool.
static constexpr u32 kLinkItemCount = 0x80;    // Quick-link array size.
static constexpr u32 kDecompressError = 0x1FF; // Sentinel for decode failure.

// ============================================================================
// Weight tables — 9 tables of 258 bytes each, indexed by compression type 0-8.
// Last two bytes (entries 0x100, 0x101) are the termination/new-branch weights.
// ============================================================================

static constexpr std::array<u8, 258> kWeightTable0 = {{
    0x0A, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x02,
    0x00, 0x00,
}};

static constexpr std::array<u8, 258> kWeightTable1 = {{
    0x54, 0x16, 0x16, 0x0D, 0x0C, 0x08, 0x06, 0x05, 0x06, 0x05, 0x06, 0x03, 0x04, 0x04, 0x03, 0x05,
    0x0E, 0x0B, 0x14, 0x13, 0x13, 0x09, 0x0B, 0x06, 0x05, 0x04, 0x03, 0x02, 0x03, 0x02, 0x02, 0x02,
    0x0D, 0x07, 0x09, 0x06, 0x06, 0x04, 0x03, 0x02, 0x04, 0x03, 0x03, 0x03, 0x03, 0x03, 0x02, 0x02,
    0x09, 0x06, 0x04, 0x04, 0x04, 0x04, 0x03, 0x02, 0x03, 0x02, 0x02, 0x02, 0x02, 0x03, 0x02, 0x04,
    0x08, 0x03, 0x04, 0x07, 0x09, 0x05, 0x03, 0x03, 0x03, 0x03, 0x02, 0x02, 0x02, 0x03, 0x02, 0x02,
    0x03, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x01, 0x01, 0x01, 0x02, 0x01, 0x02, 0x02,
    0x06, 0x0A, 0x08, 0x08, 0x06, 0x07, 0x04, 0x03, 0x04, 0x04, 0x02, 0x02, 0x04, 0x02, 0x03, 0x03,
    0x04, 0x03, 0x07, 0x07, 0x09, 0x06, 0x04, 0x03, 0x03, 0x02, 0x01, 0x02, 0x02, 0x02, 0x02, 0x02,
    0x0A, 0x02, 0x02, 0x03, 0x02, 0x02, 0x01, 0x01, 0x02, 0x02, 0x02, 0x06, 0x03, 0x05, 0x02, 0x03,
    0x02, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x02, 0x03, 0x01, 0x01, 0x01,
    0x02, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x02, 0x04, 0x04, 0x04, 0x07, 0x09, 0x08, 0x0C, 0x02,
    0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x02, 0x01, 0x01, 0x03,
    0x04, 0x01, 0x02, 0x04, 0x05, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x02, 0x01, 0x01, 0x01,
    0x04, 0x01, 0x01, 0x01, 0x01, 0x01, 0x02, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
    0x02, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
    0x02, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x02, 0x02, 0x01, 0x01, 0x02, 0x02, 0x02, 0x06, 0x4B,
    0x00, 0x00,
}};

static constexpr std::array<u8, 258> kWeightTable2 = {{
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x03, 0x27, 0x00, 0x00, 0x23, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0xFF, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x02, 0x02, 0x01, 0x01, 0x06, 0x0E, 0x10, 0x04,
    0x06, 0x08, 0x05, 0x04, 0x04, 0x03, 0x03, 0x02, 0x02, 0x03, 0x03, 0x01, 0x01, 0x02, 0x01, 0x01,
    0x01, 0x04, 0x02, 0x04, 0x02, 0x02, 0x02, 0x01, 0x01, 0x04, 0x01, 0x01, 0x02, 0x03, 0x03, 0x02,
    0x03, 0x01, 0x03, 0x06, 0x04, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x02, 0x01, 0x02, 0x01, 0x01,
    0x01, 0x29, 0x07, 0x16, 0x12, 0x40, 0x0A, 0x0A, 0x11, 0x25, 0x01, 0x03, 0x17, 0x10, 0x26, 0x2A,
    0x10, 0x01, 0x23, 0x23, 0x2F, 0x10, 0x06, 0x07, 0x02, 0x09, 0x01, 0x01, 0x01, 0x01, 0x01, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00,
}};

static constexpr std::array<u8, 258> kWeightTable3 = {{
    0xFF, 0x0B, 0x07, 0x05, 0x0B, 0x02, 0x02, 0x02, 0x06, 0x02, 0x02, 0x01, 0x04, 0x02, 0x01, 0x03,
    0x09, 0x01, 0x01, 0x01, 0x03, 0x04, 0x01, 0x01, 0x02, 0x01, 0x01, 0x01, 0x02, 0x01, 0x01, 0x01,
    0x05, 0x01, 0x01, 0x01, 0x0D, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
    0x02, 0x01, 0x01, 0x03, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x02, 0x01, 0x01, 0x01, 0x01,
    0x0A, 0x04, 0x02, 0x01, 0x06, 0x03, 0x02, 0x01, 0x01, 0x01, 0x01, 0x01, 0x03, 0x01, 0x01, 0x01,
    0x05, 0x02, 0x03, 0x04, 0x03, 0x03, 0x03, 0x02, 0x01, 0x01, 0x01, 0x02, 0x01, 0x02, 0x03, 0x03,
    0x01, 0x03, 0x01, 0x01, 0x02, 0x05, 0x01, 0x01, 0x04, 0x03, 0x05, 0x01, 0x03, 0x01, 0x03, 0x03,
    0x02, 0x01, 0x04, 0x03, 0x0A, 0x06, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
    0x02, 0x02, 0x01, 0x0A, 0x02, 0x05, 0x01, 0x01, 0x02, 0x07, 0x02, 0x17, 0x01, 0x05, 0x01, 0x01,
    0x0E, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
    0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
    0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
    0x06, 0x02, 0x01, 0x04, 0x05, 0x01, 0x01, 0x02, 0x01, 0x01, 0x01, 0x01, 0x02, 0x01, 0x01, 0x01,
    0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
    0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x07, 0x01, 0x01, 0x02, 0x01, 0x01, 0x01, 0x01,
    0x02, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x02, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x11,
    0x00, 0x00,
}};

static constexpr std::array<u8, 258> kWeightTable4 = {{
    0xFF, 0xFB, 0x98, 0x9A, 0x84, 0x85, 0x63, 0x64, 0x3E, 0x3E, 0x22, 0x22, 0x13, 0x13, 0x18, 0x17,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00,
}};

static constexpr std::array<u8, 258> kWeightTable5 = {{
    0xFF, 0xF1, 0x9D, 0x9E, 0x9A, 0x9B, 0x9A, 0x97, 0x93, 0x93, 0x8C, 0x8E, 0x86, 0x88, 0x80, 0x82,
    0x7C, 0x7C, 0x72, 0x73, 0x69, 0x6B, 0x5F, 0x60, 0x55, 0x56, 0x4A, 0x4B, 0x40, 0x41, 0x37, 0x37,
    0x2F, 0x2F, 0x27, 0x27, 0x21, 0x21, 0x1B, 0x1C, 0x17, 0x17, 0x13, 0x13, 0x10, 0x10, 0x0D, 0x0D,
    0x0B, 0x0B, 0x09, 0x09, 0x08, 0x08, 0x07, 0x07, 0x06, 0x05, 0x05, 0x04, 0x04, 0x04, 0x19, 0x18,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00,
}};

static constexpr std::array<u8, 258> kWeightTable6 = {{
    0xC3, 0xCB, 0xF5, 0x41, 0xFF, 0x7B, 0xF7, 0x21, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0xBF, 0xCC, 0xF2, 0x40, 0xFD, 0x7C, 0xF7, 0x22, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x7A, 0x46, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00,
}};

static constexpr std::array<u8, 258> kWeightTable7 = {{
    0xC3, 0xD9, 0xEF, 0x3D, 0xF9, 0x7C, 0xE9, 0x1E, 0xFD, 0xAB, 0xF1, 0x2C, 0xFC, 0x5B, 0xFE, 0x17,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0xBD, 0xD9, 0xEC, 0x3D, 0xF5, 0x7D, 0xE8, 0x1D, 0xFB, 0xAE, 0xF0, 0x2C, 0xFB, 0x5C, 0xFF, 0x18,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x70, 0x6C, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00,
}};

static constexpr std::array<u8, 258> kWeightTable8 = {{
    0xBA, 0xC5, 0xDA, 0x33, 0xE3, 0x6D, 0xD8, 0x18, 0xE5, 0x94, 0xDA, 0x23, 0xDF, 0x4A, 0xD1, 0x10,
    0xEE, 0xAF, 0xE4, 0x2C, 0xEA, 0x5A, 0xDE, 0x15, 0xF4, 0x87, 0xE9, 0x21, 0xF6, 0x43, 0xFC, 0x12,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0xB0, 0xC7, 0xD8, 0x33, 0xE3, 0x6B, 0xD6, 0x18, 0xE7, 0x95, 0xD8, 0x23, 0xDB, 0x49, 0xD0, 0x11,
    0xE9, 0xB2, 0xE2, 0x2B, 0xE8, 0x5C, 0xDD, 0x15, 0xF1, 0x87, 0xE7, 0x20, 0xF7, 0x44, 0xFF, 0x13,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x5F, 0x9E, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00,
}};

static constexpr std::array<const u8*, 9> kWeightTables = {{
    kWeightTable0.data(),
    kWeightTable1.data(),
    kWeightTable2.data(),
    kWeightTable3.data(),
    kWeightTable4.data(),
    kWeightTable5.data(),
    kWeightTable6.data(),
    kWeightTable7.data(),
    kWeightTable8.data(),
}};

// ============================================================================
// Huffman tree structures
// ============================================================================

struct HTreeItem {
    HTreeItem* next = nullptr; // Links in the sorted-by-weight doubly-linked list.
    HTreeItem* prev = nullptr;
    u32 decompressedValue = 0; // Byte value this leaf represents (or 0 for internal nodes).
    u32 weight = 0;
    HTreeItem* parent = nullptr;
    HTreeItem* childLo = nullptr; // Lower-weight child (right child).

    void remove() {
        if (next) {
            prev->next = next;
            next->prev = prev;
            next = prev = nullptr;
        }
    }
};

struct QuickLink {
    u32 validValue = 0;
    u32 validBits = 0;
    union {
        HTreeItem* item;
        u32 decompressedValue;
    };
};

// ============================================================================
// Bit reader — LSB-first, matching StormLib's TInputStream.
// ============================================================================

struct HuffBitReader {
    const u8* data;
    const u8* end;
    u32 bitBuf = 0;
    u32 bitsAvail = 0;

    HuffBitReader(const u8* d, size_t s) : data(d), end(d + s) {}

    bool get1Bit(u32& val) {
        if (bitsAvail == 0) {
            if (data >= end)
                return false;
            bitBuf = *data++;
            bitsAvail = 8;
        }
        val = bitBuf & 1;
        bitBuf >>= 1;
        bitsAvail--;
        return true;
    }

    bool get8Bits(u32& val) {
        if (bitsAvail < 8) {
            if (data >= end)
                return false;
            bitBuf |= static_cast<u32>(*data++) << bitsAvail;
            bitsAvail += 8;
        }
        val = bitBuf & 0xFF;
        bitBuf >>= 8;
        bitsAvail -= 8;
        return true;
    }

    bool peek7Bits(u32& val) {
        if (bitsAvail < 7) {
            if (data >= end)
                return false;
            bitBuf |= static_cast<u32>(*data++) << bitsAvail;
            bitsAvail += 8;
        }
        val = bitBuf & 0x7F;
        return true;
    }

    void skipBits(u32 count) {
        if (bitsAvail < count) {
            if (data >= end)
                return;
            bitBuf |= static_cast<u32>(*data++) << bitsAvail;
            bitsAvail += 8;
        }
        bitBuf >>= count;
        bitsAvail -= count;
    }
};

// ============================================================================
// Huffman tree — implements the Blizzard adaptive Huffman algorithm.
// ============================================================================

struct HuffTree {
    HTreeItem itemPool[kHuffItemCount];
    u32 itemsUsed = 0;

    // List head sentinel: pFirst and pLast form a circular doubly-linked list.
    // LIST_HEAD() in StormLib is (THTreeItem*)(&pFirst).
    HTreeItem* pFirst = nullptr;
    HTreeItem* pLast = nullptr;

    HTreeItem* itemsByByte[0x102] = {};
    QuickLink quickLinks[kLinkItemCount] = {};
    u32 minValidValue = 1;
    u32 isCmp0 = 0;

    HTreeItem* listHead() {
        return reinterpret_cast<HTreeItem*>(&pFirst);
    }

    void init() {
        pFirst = listHead();
        pLast = listHead();
        itemsUsed = 0;
        minValidValue = 1;
        isCmp0 = 0;
        std::memset(itemsByByte, 0, sizeof(itemsByByte));
        // QuickLink has default member initializers, so it's non-trivial;
        // memset through void* is intentional (bit-zero is the desired reset).
        std::memset(static_cast<void*>(quickLinks), 0, sizeof(quickLinks));
    }

    void linkTwo(HTreeItem* item1, HTreeItem* item2) {
        item2->next = item1->next;
        item2->prev = item1->next->prev;
        item1->next->prev = item2;
        item1->next = item2;
    }

    void insertItem(HTreeItem* newItem, bool before, HTreeItem* insertPoint) {
        newItem->remove();
        if (!insertPoint)
            insertPoint = listHead();

        if (!before) {
            // InsertAfter
            linkTwo(insertPoint, newItem);
        } else {
            // InsertBefore
            newItem->next = insertPoint;
            newItem->prev = insertPoint->prev;
            insertPoint->prev->next = newItem;
            insertPoint->prev = newItem;
        }
    }

    HTreeItem* findHigherOrEqual(HTreeItem* item, u32 weight) {
        if (item) {
            while (item != listHead()) {
                if (item->weight >= weight)
                    return item;
                item = item->prev;
            }
        }
        return listHead();
    }

    HTreeItem* createItem(u32 value, u32 weight, bool before) {
        if (itemsUsed >= kHuffItemCount)
            return nullptr;
        HTreeItem* item = &itemPool[itemsUsed++];
        item->next = item->prev = nullptr;
        item->decompressedValue = value;
        item->weight = weight;
        item->parent = nullptr;
        item->childLo = nullptr;
        insertItem(item, before, nullptr);
        return item;
    }

    u32 fixupPosition(HTreeItem* item, u32 maxWeight) {
        if (item->weight < maxWeight) {
            HTreeItem* higher = findHigherOrEqual(pLast, item->weight);
            item->remove();
            linkTwo(higher, item);
        } else {
            maxWeight = item->weight;
        }
        return maxWeight;
    }

    bool buildTree(u32 compType) {
        std::memset(itemsByByte, 0, sizeof(itemsByByte));
        u32 maxWeight = 0;

        if ((compType & 0x0F) > 0x08)
            return false;
        const u8* weights = kWeightTables[compType & 0x0F];

        for (u32 i = 0; i < 0x100; i++) {
            if (weights[i] != 0) {
                itemsByByte[i] = createItem(i, weights[i], false);
                maxWeight = fixupPosition(itemsByByte[i], maxWeight);
            }
        }

        // Terminal and new-branch entries.
        itemsByByte[0x100] = createItem(0x100, 1, true);
        itemsByByte[0x101] = createItem(0x101, 1, true);

        // Build the binary tree bottom-up from the sorted list.
        HTreeItem* childLo = pLast;
        while (childLo != listHead()) {
            HTreeItem* childHi = childLo->prev;
            if (childHi == listHead())
                break;

            HTreeItem* parent = createItem(0, childHi->weight + childLo->weight, false);
            if (!parent)
                return false;

            childLo->parent = parent;
            childHi->parent = parent;
            parent->childLo = childLo;

            maxWeight = fixupPosition(parent, maxWeight);
            childLo = childHi->prev;
        }

        minValidValue = 1;
        return true;
    }

    void incWeightsAndRebalance(HTreeItem* item) {
        for (; item != nullptr; item = item->parent) {
            item->weight++;

            HTreeItem* higher = findHigherOrEqual(item->prev, item->weight);
            HTreeItem* childHi = higher->next;

            if (childHi != item) {
                childHi->remove();
                linkTwo(item, childHi);

                item->remove();
                linkTwo(higher, item);

                HTreeItem const* childLo2 = childHi->parent->childLo;
                HTreeItem* par = item->parent;
                if (par->childLo == item)
                    par->childLo = childHi;
                if (childLo2 == childHi)
                    childHi->parent->childLo = item;
                par = item->parent;
                item->parent = childHi->parent;
                childHi->parent = par;

                minValidValue++;
            }
        }
    }

    bool insertNewBranch(u32 value1, u32 value2) {
        HTreeItem* lastItem = pLast;

        HTreeItem* childHi = createItem(value1, lastItem->weight, true);
        if (!childHi)
            return false;
        childHi->parent = lastItem;
        itemsByByte[value1] = childHi;

        HTreeItem* childLo = createItem(value2, 0, true);
        if (!childLo)
            return false;
        childLo->parent = lastItem;
        lastItem->childLo = childLo;
        itemsByByte[value2] = childLo;

        incWeightsAndRebalance(childLo);
        return true;
    }

    u32 decodeOneByte(HuffBitReader& is) {
        HTreeItem* itemLink = nullptr;
        u32 linkIndex = 0;
        u32 bitCount = 0;

        bool const hasLink = is.peek7Bits(linkIndex);

        HTreeItem* item;
        if (hasLink && quickLinks[linkIndex].validValue > minValidValue) {
            if (quickLinks[linkIndex].validBits <= 7) {
                is.skipBits(quickLinks[linkIndex].validBits);
                return quickLinks[linkIndex].decompressedValue;
            }
            item = quickLinks[linkIndex].item;
            is.skipBits(7);
        } else {
            if (pFirst == listHead())
                return kDecompressError;
            item = pFirst;
        }

        while (item->childLo != nullptr) {
            u32 bitVal = 0;
            if (!is.get1Bit(bitVal))
                return kDecompressError;
            item = bitVal ? item->childLo->prev : item->childLo;
            bitCount++;
            if (bitCount == 7)
                itemLink = item;
        }

        if (hasLink && quickLinks[linkIndex].validValue < minValidValue) {
            if (bitCount > 7) {
                quickLinks[linkIndex].validValue = minValidValue;
                quickLinks[linkIndex].validBits = bitCount;
                quickLinks[linkIndex].item = itemLink;
            } else {
                u32 idx = (bitCount != 0) ? linkIndex & (0xFFFFFFFF >> (32 - bitCount)) : 0;
                while (idx < kLinkItemCount) {
                    quickLinks[idx].validValue = minValidValue;
                    quickLinks[idx].validBits = bitCount;
                    quickLinks[idx].decompressedValue = item->decompressedValue;
                    idx += (1u << bitCount);
                }
            }
        }

        return item->decompressedValue;
    }
};

} // anonymous namespace

// ============================================================================
// Public API
// ============================================================================

std::vector<u8> huffmanDecompress(std::span<const u8> src, size_t expectedSize) {
    if (src.empty() || expectedSize == 0)
        return {};

    HuffBitReader is(src.data(), src.size());
    HuffTree tree;
    tree.init();

    // Read compression type (first 8 bits).
    u32 compType = 0;
    if (!is.get8Bits(compType))
        return {};
    tree.isCmp0 = (compType == 0) ? 1 : 0;

    if (!tree.buildTree(compType))
        return {};

    std::vector<u8> out;
    out.reserve(expectedSize);

    for (;;) {
        u32 value = tree.decodeOneByte(is);
        if (value == 0x100)
            break; // End of stream.
        if (value == kDecompressError)
            return {};

        if (value == 0x101) {
            // New symbol — read the 8-bit value.
            if (!is.get8Bits(value))
                return {};
            if (!tree.insertNewBranch(tree.pLast->decompressedValue, value))
                return {};
            if (tree.isCmp0 == 0)
                tree.incWeightsAndRebalance(tree.itemsByByte[value]);
        }

        if (out.size() >= expectedSize)
            break;
        out.push_back(static_cast<u8>(value));

        if (tree.isCmp0) {
            tree.incWeightsAndRebalance(tree.itemsByByte[value]);
        }
    }

    return out;
}

// ============================================================================
// Huffman Compressor
// ============================================================================

namespace {

struct HuffBitWriter {
    std::vector<u8>& out;
    u32 bitBuf = 0;
    u32 bitsUsed = 0;

    HuffBitWriter(std::vector<u8>& o) : out(o) {}

    void put1Bit(u32 val) {
        bitBuf |= (val & 1) << bitsUsed;
        bitsUsed++;
        if (bitsUsed >= 8) {
            out.push_back(static_cast<u8>(bitBuf & 0xFF));
            bitBuf >>= 8;
            bitsUsed -= 8;
        }
    }

    void put8Bits(u32 val) {
        bitBuf |= (val & 0xFF) << bitsUsed;
        bitsUsed += 8;
        while (bitsUsed >= 8) {
            out.push_back(static_cast<u8>(bitBuf & 0xFF));
            bitBuf >>= 8;
            bitsUsed -= 8;
        }
    }

    void flush() {
        if (bitsUsed > 0) {
            out.push_back(static_cast<u8>(bitBuf & 0xFF));
            bitBuf = 0;
            bitsUsed = 0;
        }
    }
};

// Encode a value by walking from the leaf to root and emitting bits.
// childLo child = bit 0, childHi (childLo->prev) = bit 1
void encodeValue(HuffTree& tree, HuffBitWriter& bw, u32 value) {
    HTreeItem const* leaf = tree.itemsByByte[value];
    if (!leaf)
        return;

    // Collect bits from leaf to root.
    std::array<u32, 64> bits;
    u32 bitCount = 0;

    HTreeItem const* item = leaf;
    while (item->parent != nullptr) {
        HTreeItem const* par = item->parent;
        // childLo = 0, childHi (childLo->prev) = 1
        bits[bitCount++] = (item == par->childLo) ? 0 : 1;
        item = par;
        if (bitCount >= 64)
            break;
    }

    // Emit bits in reverse order (root-first becomes LSB-first).
    for (u32 i = bitCount; i > 0; i--) {
        bw.put1Bit(bits[i - 1]);
    }
}

} // anonymous namespace

std::vector<u8> huffmanCompress(std::span<const u8> src, u32 compType) {
    if (src.empty())
        return {};

    std::vector<u8> out;
    out.reserve(src.size() + 16);

    HuffBitWriter bw(out);

    // Write compression type byte.
    bw.put8Bits(compType);

    // Build tree with same logic as decompressor.
    HuffTree tree;
    tree.init();
    tree.isCmp0 = (compType == 0) ? 1 : 0;
    if (!tree.buildTree(compType))
        return {};

    for (size_t i = 0; i < src.size(); i++) {
        u8 const byte = src[i];

        if (tree.itemsByByte[byte] != nullptr) {
            // Symbol already in tree — encode it.
            encodeValue(tree, bw, byte);
        } else {
            // New symbol — encode 0x101 (new-branch marker), then the raw 8-bit value.
            encodeValue(tree, bw, 0x101);
            bw.put8Bits(byte);

            tree.insertNewBranch(tree.pLast->decompressedValue, byte);
            if (tree.isCmp0 == 0) {
                tree.incWeightsAndRebalance(tree.itemsByByte[byte]);
            }
        }

        if (tree.isCmp0) {
            tree.incWeightsAndRebalance(tree.itemsByByte[byte]);
        }
    }

    // Encode end-of-stream (0x100).
    encodeValue(tree, bw, 0x100);
    bw.flush();

    return out;
}

} // namespace whiteout::storages::mpq