From 40e7d88fd0684beaf91d9fc24e8b5a3639b30be2 Mon Sep 17 00:00:00 2001 From: Valentin Popov Date: Thu, 5 Feb 2026 01:32:24 +0400 Subject: Add NRes format documentation and decompression algorithms - Created `huffman_decompression.md` detailing the Huffman decompression algorithm used in NRes, including context structure, block modes, and decoding methods. - Created `overview.md` for the NRes format, outlining file structure, header details, file entries, and packing algorithms. - Updated `mkdocs.yml` to include new documentation files in the navigation structure. --- docs/specs/assets/nres/huffman_decompression.md | 598 ++++++++++++++++++++++++ 1 file changed, 598 insertions(+) create mode 100644 docs/specs/assets/nres/huffman_decompression.md (limited to 'docs/specs/assets/nres/huffman_decompression.md') diff --git a/docs/specs/assets/nres/huffman_decompression.md b/docs/specs/assets/nres/huffman_decompression.md new file mode 100644 index 0000000..aafc02b --- /dev/null +++ b/docs/specs/assets/nres/huffman_decompression.md @@ -0,0 +1,598 @@ +# Huffman Декомпрессия + +## Обзор + +Это реализация **DEFLATE-подобного** алгоритма декомпрессии, используемого в [NRes](overview.md). Алгоритм поддерживает три режима блоков и использует два Huffman дерева для кодирования литералов/длин и расстояний. + +```c +int __thiscall sub_1001AF10( + unsigned int *this, // Контекст декодера (HuffmanContext) + int *a2 // Выходной параметр (результат операции) +) +``` + +## Структура контекста (HuffmanContext) + +```c +struct HuffmanContext { + uint32_t bitBuffer[0x4000]; // 0x00000-0x0FFFF: Битовый буфер (32KB) + uint32_t compressedSize; // 0x10000: Размер сжатых данных + uint32_t unknown1; // 0x10004: Не используется + uint32_t outputPosition; // 0x10008: Позиция в выходном буфере + uint32_t currentByte; // 0x1000C: Текущий байт + uint8_t* sourceData; // 0x10010: Указатель на сжатые данные + uint8_t* destData; // 0x10014: Указатель на выходной буфер + uint32_t bitPosition; // 0x10018: Позиция бита + uint32_t inputPosition; // 0x1001C: Позиция чтения (this[16389]) + uint32_t decodedBytes; // 0x10020: Декодированные байты (this[16386]) + uint32_t bitBufferValue; // 0x10024: Значение бит буфера (this[16391]) + uint32_t bitsAvailable; // 0x10028: Доступные биты (this[16392]) + // ... +}; + +// Смещения в структуре: +#define CTX_OUTPUT_POS 16385 // this[16385] +#define CTX_DECODED_BYTES 16386 // this[16386] +#define CTX_SOURCE_PTR 16387 // this[16387] +#define CTX_DEST_PTR 16388 // this[16388] +#define CTX_INPUT_POS 16389 // this[16389] +#define CTX_BIT_BUFFER 16391 // this[16391] +#define CTX_BITS_COUNT 16392 // this[16392] +#define CTX_MAX_SYMBOL 16393 // this[16393] +``` + +## Три режима блоков + +Алгоритм определяет тип блока по первым 3 битам: + +``` +Биты: [TYPE:2] [FINAL:1] + +FINAL = 1: Это последний блок +TYPE: + 00 = Несжатый блок (сырые данные) + 01 = Сжатый с фиксированными Huffman кодами + 10 = Сжатый с динамическими Huffman кодами + 11 = Зарезервировано (ошибка) +``` + +### Основной цикл декодирования + +```c +int decode_block(HuffmanContext* ctx) { + // Читаем первый бит (FINAL) + int final_bit = read_bit(ctx); + + // Читаем 2 бита (TYPE) + int type = read_bits(ctx, 2); + + switch (type) { + case 0: // 00 - Несжатый блок + return decode_uncompressed_block(ctx); + + case 1: // 01 - Фиксированные Huffman коды + return decode_fixed_huffman_block(ctx); + + case 2: // 10 - Динамические Huffman коды + return decode_dynamic_huffman_block(ctx); + + case 3: // 11 - Ошибка + return 2; // Неподдерживаемый тип + } + + return final_bit ? 0 : 1; // 0 = конец, 1 = есть еще блоки +} +``` + +## Режим 0: Несжатый блок + +Простое копирование байтов без сжатия. + +### Алгоритм + +```python +def decode_uncompressed_block(ctx): + """ + Формат несжатого блока: + [LEN:16][NLEN:16][DATA:LEN] + + Где: + LEN - длина данных (little-endian) + NLEN - инверсия LEN (~LEN) + DATA - сырые данные + """ + # Выравнивание к границе байта + bits_to_skip = ctx.bits_available & 7 + ctx.bit_buffer >>= bits_to_skip + ctx.bits_available -= bits_to_skip + + # Читаем длину (16 бит) + length = read_bits(ctx, 16) + + # Читаем инверсию длины (16 бит) + nlength = read_bits(ctx, 16) + + # Проверка целостности + if length != (~nlength & 0xFFFF): + return 1 # Ошибка + + # Копируем данные + for i in range(length): + byte = read_byte(ctx) + write_output_byte(ctx, byte) + + # Проверка переполнения выходного буфера + if ctx.output_position >= 0x8000: + flush_output_buffer(ctx) + + return 0 +``` + +### Детали + +- Данные копируются "как есть" +- Используется для несжимаемых данных +- Требует выравнивания по байтам перед чтением длины + +## Режим 1: Фиксированные Huffman коды + +Использует предопределенные Huffman таблицы. + +### Фиксированные таблицы длин кодов + +```python +# Таблица для литералов/длин (288 символов) +FIXED_LITERAL_LENGTHS = [ + 8, 8, 8, 8, ..., 8, # 0-143: коды длины 8 (144 символа) + 9, 9, 9, 9, ..., 9, # 144-255: коды длины 9 (112 символов) + 7, 7, 7, 7, ..., 7, # 256-279: коды длины 7 (24 символа) + 8, 8, 8, 8, ..., 8 # 280-287: коды длины 8 (8 символов) +] + +# Таблица для расстояний (30 символов) +FIXED_DISTANCE_LENGTHS = [ + 5, 5, 5, 5, ..., 5 # 0-29: все коды длины 5 +] +``` + +### Алгоритм декодирования + +```python +def decode_fixed_huffman_block(ctx): + """Декодирование блока с фиксированными Huffman кодами""" + + # Инициализация фиксированных таблиц + lit_tree = build_huffman_tree(FIXED_LITERAL_LENGTHS) + dist_tree = build_huffman_tree(FIXED_DISTANCE_LENGTHS) + + while True: + # Декодировать символ литерала/длины + symbol = decode_huffman_symbol(ctx, lit_tree) + + if symbol < 256: + # Литерал - просто вывести байт + write_output_byte(ctx, symbol) + + elif symbol == 256: + # Конец блока + break + + else: + # Символ длины (257-285) + length = decode_length(ctx, symbol) + + # Декодировать расстояние + dist_symbol = decode_huffman_symbol(ctx, dist_tree) + distance = decode_distance(ctx, dist_symbol) + + # Скопировать из истории + copy_from_history(ctx, distance, length) +``` + +### Таблицы экстра-бит + +```python +# Дополнительные биты для длины +LENGTH_EXTRA_BITS = { + 257: 0, 258: 0, 259: 0, 260: 0, 261: 0, 262: 0, 263: 0, 264: 0, # 3-10 + 265: 1, 266: 1, 267: 1, 268: 1, # 11-18 + 269: 2, 270: 2, 271: 2, 272: 2, # 19-34 + 273: 3, 274: 3, 275: 3, 276: 3, # 35-66 + 277: 4, 278: 4, 279: 4, 280: 4, # 67-130 + 281: 5, 282: 5, 283: 5, 284: 5, # 131-257 + 285: 0 # 258 +} + +LENGTH_BASE = { + 257: 3, 258: 4, 259: 5, ..., 285: 258 +} + +# Дополнительные биты для расстояния +DISTANCE_EXTRA_BITS = { + 0: 0, 1: 0, 2: 0, 3: 0, # 1-4 + 4: 1, 5: 1, 6: 2, 7: 2, # 5-12 + 8: 3, 9: 3, 10: 4, 11: 4, # 13-48 + 12: 5, 13: 5, 14: 6, 15: 6, # 49-192 + 16: 7, 17: 7, 18: 8, 19: 8, # 193-768 + 20: 9, 21: 9, 22: 10, 23: 10, # 769-3072 + 24: 11, 25: 11, 26: 12, 27: 12, # 3073-12288 + 28: 13, 29: 13 # 12289-24576 +} + +DISTANCE_BASE = { + 0: 1, 1: 2, 2: 3, 3: 4, ..., 29: 24577 +} +``` + +### Декодирование длины и расстояния + +```python +def decode_length(ctx, symbol): + """Декодировать длину из символа""" + base = LENGTH_BASE[symbol] + extra_bits = LENGTH_EXTRA_BITS[symbol] + + if extra_bits > 0: + extra = read_bits(ctx, extra_bits) + return base + extra + + return base + + +def decode_distance(ctx, symbol): + """Декодировать расстояние из символа""" + base = DISTANCE_BASE[symbol] + extra_bits = DISTANCE_EXTRA_BITS[symbol] + + if extra_bits > 0: + extra = read_bits(ctx, extra_bits) + return base + extra + + return base +``` + +## Режим 2: Динамические Huffman коды + +Самый сложный режим. Huffman таблицы передаются в начале блока. + +### Формат заголовка динамического блока + +``` +Биты заголовка: + [HLIT:5] - Количество литерал/длина кодов - 257 (значение: 257-286) + [HDIST:5] - Количество расстояние кодов - 1 (значение: 1-30) + [HCLEN:4] - Количество длин кодов для code length алфавита - 4 (значение: 4-19) + +Далее идут длины кодов для code length алфавита: + [CL0:3] [CL1:3] ... [CL(HCLEN-1):3] + +Порядок code length кодов: + 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 +``` + +### Алгоритм декодирования + +```python +def decode_dynamic_huffman_block(ctx): + """Декодирование блока с динамическими Huffman кодами""" + + # 1. Читаем заголовок + hlit = read_bits(ctx, 5) + 257 # Количество литерал/длина кодов + hdist = read_bits(ctx, 5) + 1 # Количество расстояние кодов + hclen = read_bits(ctx, 4) + 4 # Количество code length кодов + + if hlit > 286 or hdist > 30: + return 1 # Ошибка + + # 2. Читаем длины для code length алфавита + CODE_LENGTH_ORDER = [16, 17, 18, 0, 8, 7, 9, 6, 10, 5, + 11, 4, 12, 3, 13, 2, 14, 1, 15] + + code_length_lengths = [0] * 19 + for i in range(hclen): + code_length_lengths[CODE_LENGTH_ORDER[i]] = read_bits(ctx, 3) + + # 3. Строим дерево для code length + cl_tree = build_huffman_tree(code_length_lengths) + + # 4. Декодируем длины литерал/длина и расстояние кодов + lengths = decode_code_lengths(ctx, cl_tree, hlit + hdist) + + # 5. Разделяем на два алфавита + literal_lengths = lengths[:hlit] + distance_lengths = lengths[hlit:] + + # 6. Строим деревья для декодирования + lit_tree = build_huffman_tree(literal_lengths) + dist_tree = build_huffman_tree(distance_lengths) + + # 7. Декодируем данные (аналогично фиксированному режиму) + return decode_huffman_data(ctx, lit_tree, dist_tree) +``` + +### Декодирование длин кодов + +Используется специальный алфавит с тремя специальными символами: + +```python +def decode_code_lengths(ctx, cl_tree, total_count): + """ + Декодирование последовательности длин кодов + + Специальные символы: + 16 - Повторить предыдущую длину 3-6 раз (2 доп. бита) + 17 - Повторить 0 длину 3-10 раз (3 доп. бита) + 18 - Повторить 0 длину 11-138 раз (7 доп. бит) + """ + lengths = [] + last_length = 0 + + while len(lengths) < total_count: + symbol = decode_huffman_symbol(ctx, cl_tree) + + if symbol < 16: + # Обычная длина (0-15) + lengths.append(symbol) + last_length = symbol + + elif symbol == 16: + # Повторить предыдущую длину + repeat = read_bits(ctx, 2) + 3 + lengths.extend([last_length] * repeat) + + elif symbol == 17: + # Повторить ноль (короткий) + repeat = read_bits(ctx, 3) + 3 + lengths.extend([0] * repeat) + last_length = 0 + + elif symbol == 18: + # Повторить ноль (длинный) + repeat = read_bits(ctx, 7) + 11 + lengths.extend([0] * repeat) + last_length = 0 + + return lengths[:total_count] +``` + +## Построение Huffman дерева + +```python +def build_huffman_tree(code_lengths): + """ + Построить Huffman дерево из длин кодов + + Использует алгоритм "canonical Huffman codes" + """ + max_length = max(code_lengths) if code_lengths else 0 + + # 1. Подсчитать количество кодов каждой длины + bl_count = [0] * (max_length + 1) + for length in code_lengths: + if length > 0: + bl_count[length] += 1 + + # 2. Вычислить первый код для каждой длины + code = 0 + next_code = [0] * (max_length + 1) + + for bits in range(1, max_length + 1): + code = (code + bl_count[bits - 1]) << 1 + next_code[bits] = code + + # 3. Присвоить числовые коды символам + tree = {} + for symbol, length in enumerate(code_lengths): + if length > 0: + tree[symbol] = { + 'code': next_code[length], + 'length': length + } + next_code[length] += 1 + + # 4. Создать структуру быстрого поиска + lookup_table = create_lookup_table(tree) + + return lookup_table + + +def decode_huffman_symbol(ctx, tree): + """Декодировать один символ из Huffman дерева""" + code = 0 + length = 0 + + for length in range(1, 16): + bit = read_bit(ctx) + code = (code << 1) | bit + + # Проверить в таблице быстрого поиска + if (code, length) in tree: + return tree[(code, length)] + + return -1 # Ошибка декодирования +``` + +## Управление выходным буфером + +```python +def write_output_byte(ctx, byte): + """Записать байт в выходной буфер""" + # Записываем в bitBuffer (используется как циклический буфер) + ctx.bitBuffer[ctx.decodedBytes] = byte + ctx.decodedBytes += 1 + + # Если буфер заполнен (32KB) + if ctx.decodedBytes >= 0x8000: + flush_output_buffer(ctx) + + +def flush_output_buffer(ctx): + """Сбросить выходной буфер в финальный выход""" + # Копируем данные в финальный выходной буфер + dest_offset = ctx.outputPosition + ctx.destData + memcpy(dest_offset, ctx.bitBuffer, ctx.decodedBytes) + + # Обновляем счетчики + ctx.outputPosition += ctx.decodedBytes + ctx.decodedBytes = 0 + + +def copy_from_history(ctx, distance, length): + """Скопировать данные из истории (LZ77)""" + # Позиция источника в циклическом буфере + src_pos = (ctx.decodedBytes - distance) & 0x7FFF + + for i in range(length): + byte = ctx.bitBuffer[src_pos] + write_output_byte(ctx, byte) + src_pos = (src_pos + 1) & 0x7FFF +``` + +## Полная реализация на Python + +```python +class HuffmanDecoder: + """Полный DEFLATE-подобный декодер""" + + def __init__(self, input_data, output_size): + self.input_data = input_data + self.output_size = output_size + self.input_pos = 0 + self.bit_buffer = 0 + self.bits_available = 0 + self.output = bytearray() + self.history = bytearray(32768) # 32KB циклический буфер + self.history_pos = 0 + + def read_bit(self): + """Прочитать один бит""" + if self.bits_available == 0: + if self.input_pos >= len(self.input_data): + return 0 + self.bit_buffer = self.input_data[self.input_pos] + self.input_pos += 1 + self.bits_available = 8 + + bit = self.bit_buffer & 1 + self.bit_buffer >>= 1 + self.bits_available -= 1 + return bit + + def read_bits(self, count): + """Прочитать несколько бит (LSB first)""" + result = 0 + for i in range(count): + result |= self.read_bit() << i + return result + + def write_byte(self, byte): + """Записать байт в выход и историю""" + self.output.append(byte) + self.history[self.history_pos] = byte + self.history_pos = (self.history_pos + 1) & 0x7FFF + + def copy_from_history(self, distance, length): + """Скопировать из истории""" + src_pos = (self.history_pos - distance) & 0x7FFF + + for _ in range(length): + byte = self.history[src_pos] + self.write_byte(byte) + src_pos = (src_pos + 1) & 0x7FFF + + def decompress(self): + """Основной цикл декомпрессии""" + while len(self.output) < self.output_size: + # Читаем заголовок блока + final = self.read_bit() + block_type = self.read_bits(2) + + if block_type == 0: + # Несжатый блок + if not self.decode_uncompressed_block(): + break + elif block_type == 1: + # Фиксированные Huffman коды + if not self.decode_fixed_huffman_block(): + break + elif block_type == 2: + # Динамические Huffman коды + if not self.decode_dynamic_huffman_block(): + break + else: + # Ошибка + raise ValueError("Invalid block type") + + if final: + break + + return bytes(self.output[:self.output_size]) + + # ... реализации decode_*_block методов ... +``` + +## Оптимизации + +### 1. Таблица быстрого поиска + +```python +# Предвычисленная таблица для 9 бит (первый уровень) +FAST_LOOKUP_BITS = 9 +fast_table = [None] * (1 << FAST_LOOKUP_BITS) + +# Заполнение таблицы при построении дерева +for symbol, info in tree.items(): + if info['length'] <= FAST_LOOKUP_BITS: + # Все возможные префиксы для этого кода + code = info['code'] + for i in range(1 << (FAST_LOOKUP_BITS - info['length'])): + lookup_code = code | (i << info['length']) + fast_table[lookup_code] = symbol +``` + +### 2. Буферизация битов + +```python +# Читать по 32 бита за раз вместо побитового чтения +def refill_bits(self): + """Пополнить битовый буфер""" + while self.bits_available < 24 and self.input_pos < len(self.input_data): + byte = self.input_data[self.input_pos] + self.input_pos += 1 + self.bit_buffer |= byte << self.bits_available + self.bits_available += 8 +``` + +## Отладка и тестирование + +```python +def debug_huffman_decode(data): + """Декодирование с отладочной информацией""" + decoder = HuffmanDecoder(data, len(data) * 10) + + original_read_bits = decoder.read_bits + def debug_read_bits(count): + result = original_read_bits(count) + print(f"Read {count} bits: 0x{result:0{count//4}X} ({result})") + return result + + decoder.read_bits = debug_read_bits + return decoder.decompress() +``` + +## Заключение + +Этот Huffman декодер реализует **DEFLATE**-совместимый алгоритм с тремя режимами блоков: + +1. **Несжатый** - для несжимаемых данных +2. **Фиксированный Huffman** - быстрое декодирование с предопределенными таблицами +3. **Динамический Huffman** - максимальное сжатие с пользовательскими таблицами + +**Ключевые особенности:** + +- Поддержка LZ77 для повторяющихся последовательностей +- Канонические Huffman коды для эффективного декодирования +- Циклический буфер 32KB для истории +- Оптимизации через таблицы быстрого поиска + +**Сложность:** O(n) где n - размер выходных данных -- cgit v1.2.3