Архиватор Хаффмана (HaffmanArch)

Консольное приложение для сжатия и распаковки файлов и папок с использованием алгоритма Хаффмана.

Обзор проекта

HaffmanArch — это утилита командной строки, написанная на языке C, предназначенная для эффективного сжатия данных. Она поддерживает работу с отдельными файлами и целыми директориями, а также позволяет выбирать ширину символа для кодирования (1 или 2 байта).

Возможности

• Сжатие: Уменьшение размера файлов и папок.
• Распаковка: Восстановление оригинальных данных из архива.
• Поддержка переменной ширины символа: Автоматическое определение или ручное указание (1 или 2 байта) для оптимального сжатия различных типов данных.
• Рекурсивная обработка папок: Сжатие и распаковка содержимого папок, включая вложенные структуры.
• Отображение прогресса: Индикация выполнения длительных операций.
• Справочная информация: Встроенная помощь по командам и опциям.

Структура проекта

HaffmanArch/
├── src/                  # Исходные коды проекта
│   ├── main.c            # Главный файл, обработка аргументов, запуск операций
│   ├── huffman.c         # Реализация алгоритма Хаффмана
│   ├── huffman.h         # Заголовочный файл для huffman.c
│   ├── archive.c         # Функции архивации и разархивации
│   ├── archive.h         # Заголовочный файл для archive.c
│   ├── bitio.c           # Функции побитового ввода/вывода
│   ├── bitio.h           # Заголовочный файл для bitio.c
│   ├── fsUtils.c         # Утилиты для работы с файловой системой
│   ├── fsUtils.h         # Заголовочный файл для fsUtils.c
│   ├── Heap.c            # Реализация минимальной кучи
│   ├── Heap.h            # Заголовочный файл для Heap.c
│   ├── progress.c        # Функции отображения прогресса
│   ├── progress.h        # Заголовочный файл для progress.c
│   ├── help.c            # Функции вывода справки
│   └── help.h            # Заголовочный файл для help.c
├── obj/                  # Объектные файлы (генерируются при сборке)
├── Makefile              # Файл для сборки проекта
├── README.md             # Этот файл
└── huffmatic             # Исполняемый файл архиватора (после сборки)

Инструкции по сборке

Требования

• Компилятор GCC
• Утилита Make

Сборка

Для сборки проекта выполните команду в корневой директории HaffmanArch:

make

Эта команда скомпилирует исходные файлы и создаст исполняемый файл huffmatic в корневой директории проекта.

Использование

Общий формат команды

./huffmatic <режим> [опции] [файлы ...] <архив>

• -h или --help: Показать справочную информацию.

Режимы

• -c Режим сжатия (упаковки). Укажите один или несколько входных файлов или директорий, а затем имя создаваемого архива.

• -d Режим распаковки (извлечения). Укажите имя архива для распаковки. Можно также указать имена конкретных файлов или директорий из архива для извлечения только их. Если имена не указаны, распаковывается всё содержимое архива.

Опции (-c):

• -s <ширина> Задает ширину символа для кодирования Хаффмана. Если опция не указана, используется ширина символа 1 байт. <ширина> может быть: 1 - для 1-байтных символов. Это значение по умолчанию. 2 - для 2-байтных символов. Пример: ./huffmatic -c -s 2 мой_файл.txt мой_архив.huf

Примеры:

1. Упаковать один файл с настройками по умолчанию: ./huffmatic -c документ.txt архив.huf

2. Упаковать несколько файлов и директорию: ./huffmatic -c файл1.txt папка1 файл2.jpg архив.huf

3. Упаковать файл, используя 2-байтную ширину символа: ./huffmatic -c -s 2 текст.txt архив.huf

4. Распаковать все содержимое архива: ./huffmatic -d архив.huf

5. Распаковать только указанные файлы из архива: ./huffmatic -d архив.huf файл1.txt папка/файл2.doc

Дополнительная информация:

Название архива не обязательно должно заканчиваться на .huf ! Оно может быть любым. При сжатии программа выводит статистику, включая общий размер входных файлов, размер полученного архива и коэффициент сжатия. При распаковке программа автоматически определяет ширину символа, использованную при сжатии, из заголовка архива.

Как это работает

Сжатие

1. Анализ частот: Программа подсчитывает частоту каждого символа (1-байтового или 2-байтового, в зависимости от режима) во входных данных.
2. Построение дерева Хаффмана: На основе таблицы частот строится бинарное дерево Хаффмана, где символы с меньшей частотой располагаются дальше от корня.
3. Генерация кодов: Для каждого символа генерируется уникальный префиксный код Хаффмана (последовательность битов). Часто встречающиеся символы получают короткие коды, редкие — длинные.
4. Запись метаданных: В начало архива записывается служебная информация:
   • Сигнатура архива.
   • Информация о ширине символа (1 или 2 байта).
   • Таблица частот, необходимая для декодирования.
   • Информация о структуре файлов и папок (для архивации директорий).
5. Кодирование и запись данных: Исходные данные заменяются их кодами Хаффмана и записываются в архив в виде плотного потока битов.

Распаковка

1. Чтение метаданных: Из архива считывается служебная информация, включая данные для восстановления дерева Хаффмана и структуру оригинальных файлов/папок.
2. Декодирование данных: Архив читается побитово. Каждая последовательность битов, соответствующая коду Хаффмана, заменяется на исходный символ.
3. Восстановление файлов: Декодированные данные записываются в файлы, восстанавливая оригинальную структуру, если была сжата папка.

Краткое описание каждого исходного файла

Ниже более подробное описание того, что делает каждый файл вашего архиватора (расширив ваш черновик и добавив недостающие детали).

---

1. main.c

• Задачи:

  • Точка входа int main(int argc, char *argv[]).
  • Разбор и валидация аргументов (режим -c/-d, флаг ширины символа -s, список входных путей и имя архива).
  • В случае некорректных аргументов или флага -h/--help вызывает print_usage() из main.c или print_full_help() из help.c.
  • В режиме сжатия вызывает archive_compress(...) из archive.c, в режиме распаковки — archive_decompress(...).
  • Обрабатывает коды возврата и выводит понятные сообщения об ошибках («не корректный архив», «ошибка распаковки» и т. п.).

• Функции:

  • static void print_usage(const char *prog) — краткая подсказка по синтаксису.
  • int main(…) — как описано выше.

---

2. help.c

• Задачи: При запросе подробной справки (обычно через -h/--help) выводит на stdout описание всех режимов, ключей и примеры использования.

• Функции:

  • void print_full_help(const char *prog_name) — выводит детальное руководство по работе с утилитой.

---

3. fsUtils.c

• Задачи: Работа с файловой системой при сборе списка файлов для архивации и освобождении ресурсов.

• Основные возможности:

  • Рекурсивный обход входных путей (файлов и директорий), чтобы собрать все файлы для последующего сжатия.

  • Формирование структуры FileEntry для каждого файла:

    typedef struct FileEntry {
        char *path;    // полный путь на диске
        char *name;    // путь внутри архива (относительный)
        uint64_t size; // размер файла
    } FileEntry;

  • Поддержка автоматического расширения массива FileEntry * при добавлении новых элементов.

  • Освобождение памяти при помощи free_entries().

• Функции:

  • FileEntry *scan_paths_recursive(int path_count, const char *paths[], const char *base_path_for_name, int *out_count) Рекурсивно сканирует переданные paths[], заполняет массив FileEntry, возвращает его и количество.
  • uint64_t get_file_size(const char *path) — обёртка над stat() для получения st_size.
  • void free_entries(FileEntry *entries, int count) — освобождает все строки path, name и сам массив.

---

4. bitio.c

• Задачи: Битовый ввод/вывод — запись и чтение не целых байт, а отдельных битов, как того требует кодирование Хаффмана.

• Структура:

  typedef struct {
      FILE *file;
      uint8_t buffer;   // «собираем» или «срезаем» биты здесь
      int position;     // сколько бит уже записано/прочитано в buffer
      char mode;        // 'r' или 'w'
  } BitIO;

• Функции:

  • BitIO *bitio_open(const char *filename, const char *mode) — открыть файл в режиме чтения/записи битов, инициализировать буфер.
  • int bitio_read(BitIO *bitio) — прочитать следующий бит (0 или 1), возвращает EOF при окончании.
  • int bitio_write(BitIO *bitio, int bit) — дописать бит (0/1) в буфер, и при заполнении байта — записать его в файл.
  • int bitio_close(BitIO *bitio) — при записи дозаполняет последний байт нулями, закрывает файл и освобождает BitIO.

---

5. Heap.c

• Задачи: Стандартный минимальный (min-)куча для узлов дерева Хаффмана; нужен для построения дерева по частотам.

• Структура:

  typedef struct {
      int size;
      int capacity;
      HuffmanNode **array; // массив указателей на узлы
  } MinHeap;

• Функции:

  • MinHeap *createMinHeap(int capacity) — выделяет и возвращает пустую кучу заданной вместимости.
  • void destroyMinHeap(MinHeap *heap) — освобождает память.
  • void insertNode(MinHeap *heap, HuffmanNode *node) — вставка узла с сохранением свойства min-кучи.
  • HuffmanNode *extractMin(MinHeap *heap) — извлечение узла с наименьшей частотой.
  • Внутренние (static): swapNodes(), minHeapify() — поддерживают упорядоченность кучи.

---

6. huffman.c

• Задачи: Собственно алгоритм Хаффмана: подсчёт частот символов, построение дерева, генерация кодов, сжатие и распаковка отдельных файлов.

• Ключевые типы:

  typedef struct HuffmanNode {
      uint64_t freq;
      uint16_t symbol;          
      struct HuffmanNode *left, *right;
  } HuffmanNode;
  
  typedef struct {
      uint16_t length;   
      uint32_t bits;           
  } Code;

• Функции:

  • static HuffmanNode **make_node_list(const size_t *freq, size_t alphabet_size, int *out_n) Создаёт список узлов для всех символов с ненулевой частотой.
  • HuffmanNode *build_huffman_tree(const size_t *freq, size_t alphabet_size) Строит дерево: заводит все узлы в MinHeap, затем последовательно извлекает два наименьших, объединяет их в новый узел и вставляет обратно.
  • void generate_codes(const HuffmanNode *root, Code *codes, char *buffer, size_t depth, size_t alphabet_size) Обход дерева в глубину, заполняет массив codes[symbol] = {длина, биты}.
  • void free_huffman_tree(HuffmanNode *root) — освобождает память всего дерева.
  • int huffman_compress(const char *input_filename, const char *output_filename, progress_callback_t callback, int symbol_width) — подсчитывает частоты (читая symbol_width байт за раз), строит дерево, генерирует коды, записывает в начало выходного файла заголовок кодовой таблицы, затем побитово пишет закодированные данные. Вызывает callback для отображения прогресса.
  • int decode_symbol(BitIO *input, const HuffmanNode *root) — читает биты до встречи листа дерева, возвращает decoded symbol.
  • int huffman_decompress(const char *input_filename, const char *output_filename, progress_callback_t callback, int symbol_width) — читает заголовок (частотные данные или дерево), собирает дерево, побитово читает код и восстанавливает исходные символы в выходной файл.

---

7. archive.c

• Задачи: Высокоуровневая логика «многопоточности» архива: работа не с одним файлом, а с набором файлов/директорий, организация единого архива, формат заголовка и метаданных, пакетная упаковка и распаковка.

• Основные шаги компрессии (archive_compress):

  1. Сканирование всех входных путей через scan_paths_recursive() → массив FileEntry.

  2. Открытие архива на запись и запись:

     • байта symbol_width (1 или 2),
     • 4-байтового file_count,
     • для каждого файла: 2-байтовой длины имени, саму строку имени, зарезервированные 8 байт под offset и 8 байт под compressed_size.

  3. Цикл по FileEntry:

     • для обычного файла — вызов huffman_compress(...),
     • для директории — просто записывает нулевые длины (размер = 0).
     • после компрессии заполняет зарезервированные в заголовке поля offset и compressed_size через fseek/fwrite.

  4. Возвращает суммарный оригинальный размер (для статистики).

• Основные шаги декомпрессии (archive_decompress):

  1. Открытие архива на чтение, чтение symbol_width и file_count.

  2. Чтение метаданных всех записей (имена, оффсеты, размеры).

  3. По селект-списку sel_files[] или «все, если пусто» — выбор нужных записей.

  4. Для каждой записи:

     • создание вложенных директорий через mkdir по пути name,
     • если compressed_size > 0 — вызов huffman_decompress(...) с указанием смещения и длины,
     • иначе — просто создаётся пустой файл или каталог.

• Вспомогательные функции:

  • static void make_tmp_name(...) — генерирует временное имя для промежуточной записи.
  • void huffman_progress_callback(uint64_t inc) — аккумулирует байты и передаёт их в progress_update().

---

8. progress.c

• Задачи: Красивый вывод прогресса (в процентах) в консоль при долгих операциях.

• Локальные переменные:

  static uint64_t total_size = 0;
  static int last_percentage = -1;

• Функции:

  • void progress_start(uint64_t total_bytes) — инициализирует общий объём.
  • void progress_update(uint64_t processed_bytes) — пересчитывает процент и печатает «\rПрогресс: XX%».
  • void progress_end() — доводит индикатор до 100% и переводит строку.

---