valentineus/fparkan
1
Fork 0
Code Issues Pull Requests Actions Releases Wiki Activity
Files
devel
fparkan/docs/specs/assets/nres/huffman_decompression.md

599 lines
21 KiB
Markdown
Raw Permalink Normal View History

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.
2026-02-05 01:32:24 +04:00
# 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 - размер выходных данных
Copy Permalink