# 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 - размер выходных данных