Загадочный ZIP-файл. Что это и как его получить?
Создание zip-архивов позволяет экономить память, перемещать и передавать файлы между пользователями, а также удобно организовывать хранение документов. Сегодня мы расскажем что из себя представляет zip-формат и как с ним работать.
Что это такое?
Zip – универсальный формат сжатия и архивации файлов. Файл любого типа после архивации с помощью специализированных программ или встроенных функций Windows приобретает именно это разрешение.
Как открыть файл?
Рассмотрим как открыть zip-файл с помощью встроенных возможностей Windows:
- Выделите zip-файл (иконка папки с замком). Кликните на него правой кнопкой мыши, выберете позицию «Извлечь все».
- Далее откроется окно распаковки архива. В нем можно выбрать папку, в которую произойдет извлечение архива (написать путь самостоятельно или выбрать папку с помощью кнопки Обзор).
- Нажмите кнопку Извлечь в нижнем углу окна.
Теперь все файлы архива извлечены в указанную папку.
Как его получить?
Существует два способа добавить несколько файлов в архив. Для первого способа:
- Выделите файл или группу файлов, которые вы хотели бы архивировать.
- Кликните по ним правой кнопкой мыши, в выпавшем списке выберете позицию «Отправить», затем «Сжатая папка-ZIP».
Для второго способа:
- На пустом месте экрана кликните правой кнопкой мыши.
- В открывшемся списке выберете «Создать», далее «Сжатая папка ZIP».
- Далее выделите нужные файлы и перетащите их мышью на иконку созданной сжатой папки.
Архиваторы
На сегодняшний момент кроме стандартного архиватора Windows существует множество специализированных программ, с расширенным арсеналом функций. Мы расскажем о самых популярных программах:
- WinRAR. Одна из самых популярных бесплатных программ для работы с архивами. Может создавать архивы типа .rar и .zip, распаковывать может значительно больше форматов. В рамках работы с WinRAR возможно создавать комментарии к созданным архивам.
- 7-Zip. По сравнению с WinRAR имеет значительно больше возможностей архивации файлов. Формат zip поддерживает как для создания архива, так и для распаковки. Имеет усовершенствованные алгоритмы, что позволяет сжимать файлы до меньшего размера в ускоренном режиме.
- IZArc. Усовершенствованная бесплатная утилита для работы с архивами. Работает с теми же форматами архивов, что и 7-Zip. Отличает IZArc возможность работы с образами дисков (ISO,CDI) и работа с самораспаковывающимися архивами. Также с ее помощью можно восстанавливать поврежденные архивы без дополнительных программ.
- PeaZip. Программа представляет собой кроссплатформенный портативный бесплатный архиватор. Дает возможность создания, открытия и распаковки архивов формата zip. Дает возможность использования уникального формата архивирования pea с особой системой шифрования.
Использование архивов типа zip экономит время и дарит множество новых возможностей пользователю. Не стоит пугаться неизвестных форматов и программ, работа с ними практически интуитивная и значительно облегчит вашу жизнь.
Zip-файлы: история, объяснение и реализация
Мне давно было интересно, как сжимаются данные, в том числе в Zip-файлах. Однажды я решил удовлетворить своё любопытство: узнать, как работает сжатие, и написать собственную Zip-программу. Реализация превратилась в захватывающее упражнение в программировании. Получаешь огромное удовольствие от создания отлаженной машины, которая берёт данные, перекладывает их биты в более эффективное представление, а затем собирает обратно. Надеюсь, вам тоже будет интересно об этом читать.
В статье очень подробно объясняется, как работают Zip-файлы и схема сжатия: LZ77-сжатие, алгоритм Хаффмана, алгоритм Deflate и прочее. Вы узнаете историю развития технологии и посмотрите довольно эффективные примеры реализации, написанные с нуля на С. Исходный код лежит тут: hwzip-1.0.zip.
Я очень благодарен Ange Albertini, Gynvael Coldwind, Fabian Giesen, Jonas Skeppstedt (web), Primiano Tucci и Nico Weber, которые дали ценные отзывы на черновики этой статьи.
Содержание
История
PKZip
В восьмидесятых и начале девяностых, до широкого распространения интернета, энтузиасты-компьютерщики использовали dial-up-модемы для подключения через телефонную сеть к сети Bulletin Board Systems (BBS). BBS представляла собой интерактивную компьютерную систему, которая позволяла пользователям отправлять сообщения, играть в игры и делиться файлам. Для выхода в онлайн достаточно было компьютера, модема и телефонного номера хорошей BBS. Номера публиковались в компьютерных журналах и на других BBS.
Важным инструментом, облегчающим распространение файлов, был архиватор. Он позволяет сохранять один или несколько файлов в едином файле-архиве, чтобы удобнее хранить или передавать информацию. А в идеале архив ещё и сжимал файлы для экономии места и времени на передачу по сети. Во времена BBS был популярен архиватор Arc, написанный Томом Хендерсоном из System Enhancement Associates (SEA), маленькой компании, которую он основал со своим шурином.
В конце 1980-х программист Фил Катц выпустил собственную версию Arc — PKArc. Она была совместима с SEA Arc, но работала быстрее благодаря подпрограммам, написанным на ассемблере, и использовала новый метод сжатия. Программа стала популярной, Катц ушёл с работы и создал компанию PKWare, чтобы сосредоточиться на дальнейшей разработке. Согласно легенде, большая часть работы проходила на кухне его матери в Глендейле, штат Висконсин.
Фотография Фила Катца из статьи в Milwaukee Sentinel, 19 сентября 1994.
Однако SEA не устраивала инициатива Катца. Компания обвинила его в нарушении товарного знака и авторских прав. Разбирательства и споры в сети BBS и мире ПК стали известны как Arc-войны. В конце концов, спор был урегулирован в пользу SEA.
Отказавшись от Arc, Катц в 1989 создал новый формат архивирования, который он назвал Zip и передал в общественное пользование:
Программа Катца для создания таких файлов получила название PKZip и скоро распространилась в мире BBS и ПК.
Одним из аспектов, который с наибольшей вероятностью поспособствовал успеху Zip-формата, является то, что с PKZip шла документация, Application Note, в которой подробно объяснялось, как работает формат. Это позволило другим изучить формат и создать программы, которые генерируют, извлекают или как-то иначе взаимодействуют с Zip-файлами.
Zip — это формат сжатия без потерь: после распаковки данные будут такими же, как перед сжатием. Алгоритм ищет избыточности в исходных данных и эффективнее представляет информацию. Этот подход отличается от сжатия с потерями, который используется в таких форматах, как JPEG и MP3: при сжатии выбрасывается часть информации, которая менее заметна для человеческого глаза или уха.
PKZip распространялась как Shareware: её можно было свободно использовать и копировать, но автор предлагал пользователям «зарегистрировать» программу. За $47 можно было получить распечатанную инструкцию, премиальную поддержку и расширенную версию приложения.
Одной из ключевых версий PKZip стала 2.04c, вышедшая 28 декабря 1992 (вскоре после неё вышла версия 2.04g). В ней по умолчанию использовался алгоритм сжатия Deflate. Версия определила дальнейший путь развития сжатия в Zip-файлах (статья, посвящённая релизу).
С тех пор Zip-формат используется во многих других форматах файлов. Например, Java-архивы (.jar), Android Application Packages (.apk) и .docx-файлы Microsoft Office используют Zip-формат. Во многих форматах и протоколах применяется тот же алгоритм сжатия, Deflate. Скажем, веб-страницы наверняка передаются в ваш браузер в виде gzip-файла, формат которого использует Deflate-сжатие.
Фил Катц умер в 2000-м. PKWare всё ещё существует и поддерживает Zip-формат, хотя компания сосредоточена в основном на ПО для защиты данных.
Info-ZIP и zlib
Вскоре после выхода PKZip в 1989-м начали появляться другие программы для распаковки Zip-файлов. Например, программа unzip, которая могла распаковывать на Unix-системах. В марте 1990-го был создан список рассылки под названием Info-ZIP.
Группа Info-ZIP выпустила бесплатные программы с открытым исходным кодом unzip и zip, которые использовались для распаковки и создания Zip-файлов. Код портировали во многие системы, и он до сих пор является стандартом для Zip-программ под Unix-системы. Позднее это помогло росту популярности Zip-файлов.
Однажды код Info-ZIP, который выполнял Deflate-сжатие и распаковку, был вынесен в отдельную библиотеку zlib, которую написали Jean-loup Gailly (сжатие) и Mark Adler (распаковка).
Jean-loup Gailly (слева) и Mark Adler (справа) на вручении им премии USENIX STUG Award в 2009-м.
Одна из причин создания библиотеки заключалась в том, что это обеспечивало удобство использования Deflate-сжатия в других приложениях и форматах, например, в новых gzip и PNG. Эти новые форматы были призваны заменить Compress и GIF, в которых применялся защищённый патентом алгоритм LZW.
В рамках создания этих форматов Питер Дойч написал спецификацию Deflate и опубликовал под названием Internet RFC 1951 в мае 1996-го. Это оказалось более доступное описание по сравнению с исходным PKZip Application Note.
Сегодня zlib используется повсеместно. Возможно, он сейчас отвечает за сжатие этой страницы на веб-сервере и её распаковки в вашем браузере. Сегодня сжатие и распаковка большинства Zip-файлов выполняется с помощью zlib.
WinZip
Многие из тех, кто не застал PKZip, пользовались WinZip. Пользователи ПК перешли как с DOS на Windows, так и с PKZip на WinZip.
Всё началось с проекта программиста Нико Мака, который создавал ПО для OS/2 в компании Mansfield Software Group в городе Сторрс-Мансфилд, штат Коннектикут. Нико использовал Presentation Manager, это графический пользовательский интерфейс в OS/2, и его расстраивало, что приходится переходить от файлового менеджера к DOS-командам каждый раз, когда он хотел создать Zip-файлы.
Мак написал простую программу с графическим интерфейсом, которая работала с Zip-файлами прямо в Presentation Manager, назвал её PMZip и выпустил в качестве shareware в 1990-м.
OS/2 так и не добилась успеха, а мир ПК захватывала Microsoft Windows. В 1991-м Мак решил научиться писать Windows-программы, и его первым проектом стало портирование своего Zip-приложения под новую ОС. В апреле 1991-го вышла WinZip 1.00. Она распространялась в качестве shareware с 21-дневным пробным периодом и стоимостью регистрации $29. Выглядела она так:
В первых версиях WinZip под капотом использовалась PKZip. Но с версии 5.0 в 1993-м для прямой обработки Zip-файлов стал использоваться код из Info-ZIP. Пользовательский интерфейс тоже постепенно эволюционировал.
WinZip 6.3 под Windows 3.11 for Workgroups.
WinZip была одной из самых популярных shareware-программ в 1990-е. Но в конце концов она потеряла актуальность из-за встраивания поддержки Zip-файлов в операционные системы. Windows работает с ними как со «сжатыми папками» начиная с 2001-го (Windows XP), для этого используется библиотека DynaZip.
Изначально компания Мака называлась Nico Mak Computing. В 2000-м её переименовали в WinZip Computing, и примерно в те годы Мак её покинул. В 2005-м компанию продали Vector Capital, и в конце концов ею стала владеть Corel, которая до сих пор выпускает WinZip в качестве продукта.
Сжатие Lempel-Ziv (LZ77)
Zip-сжатие состоит из двух основных ингредиентов: сжатия Lempel-Ziv и кода Хаффмана.
Один из способов сжатия текста заключается в создании списка частых слов или фраз с заменой разновидностей этих слов в рамках текста ссылками на словарь. Например, длинное слово «compression» в исходном тексте можно представить как #1234, где 1234 ссылается на позицию слова в списке. Это называется сжатием с использованием словаря.
Но с точки зрения сжатия универсального назначения у такого метода есть несколько недостатков. Во-первых, что именно должно попасть в словарь? Исходные данные могут быть на разных языках, это может быть даже не человеко читаемый текст. И если заранее не согласовать словарь между сжатием и распаковкой, то его придётся хранить и передавать вместе со сжатыми данными, что снижает выгоду от сжатия.
Элегантным решением этой проблемы является использование в качестве словаря самих исходных данных. В работе «A Universal Algorithm for Sequential Data Compression» 1977 года Якоб Зив и Абрахам Лемпел (работавшие в компании Technion), предложили схему сжатия, при которой исходные данные представляются в виде последовательности триплетов:
где указатель и длина формируют обратную ссылку на последовательность символов, которую нужно скопировать из предыдущей позиции в оригинальном тексте, а следующий — это следующий символ в генерируемых данных.
Абрахам Лемпел и Якоб Зив.
Рассмотрим такие строки:
Во второй строке последовательность «t was the w» можно представить как (26, 10, w), поскольку она воссоздаётся копированием 10 символов с позиции в 26 символов назад и до буквы «w». Для символов, которые до этого ещё не появлялись, используются обратные ссылки нулевой длины. Например, начальная «I» может быть представлена как (0, 0, I).
Эта схема получила название сжатие Lempel-Ziv, или сжатие LZ77. Однако в практических реализациях алгоритма обычно не используется часть триплета следующий . Вместо этого символы генерируются по-одиночке, а для обратных ссылок используются пары ( расстояние , длина ) (этот вариант называется сжатием LZSS). Как кодируются литералы и обратные ссылки — это отдельный вопрос, мы рассмотрим его ниже, когда будем разбирать алгоритм Deflate.
Можно сжать в такой:
Одним из важных свойств обратных ссылок является то, что они могут перекрывать друг друга. Такое случается тогда, когда длина больше расстояния. Например:
Вам это может показаться странным, но метод работает: после того, как скопированы байты первых трёх «-la», копирование продолжается уже с использованием недавно сгенерированных байтов.
По сути, это разновидность кодирования длин серий, при котором часть данных многократно копируется для получения нужной длины.
Интерактивный пример использования сжатия Lempel-Ziv для текстов песен показан в статье Колина Морриса Are Pop Lyrics Getting More Repetitive?.
Ниже приведён пример копирования обратных ссылок на языке С. Обратите внимание, что из-за возможного перекрытия мы не можем использовать memcpy или memmove .
Генерировать литералы легко, но для полноты воспользуемся вспомогательной функцией:
Обратите внимание, что вызывающий эту функцию должен удостовериться, что в dst достаточно места для генерируемых данных и что обратная ссылка не обращается к позиции до начала буфера.
Сложно не генерировать данные с помощью обратных ссылок в ходе распаковки, а создавать их первым делом при сжатии исходных данных. Это можно сделать по-разному, но мы воспользуемся методикой на основе хэш-таблиц из zlib, который предлагается в RFC 1951.
Будем применять хэш-таблицу с позициями трёхсимвольных префиксов, которые ранее встречались в строке (более короткие обратные ссылки пользы не приносят). В Deflate допускаются обратные ссылки в рамках предыдущих 32 768 символов — это называется окном. Это обеспечивает потоковое сжатие: входные данные подвергаются небольшой обработке за раз, при условии, что окно с последними байтами хранится в памяти. Однако наша реализация предполагает, что нам доступны все входные данные и мы можем обработать их целиком за раз. Это позволяет сосредоточиться на сжатии, а не на учёте, который необходим для потоковой обработки.
Воспользуемся двумя массивами: в head содержится хэш-значение трёхсимвольного префикса для позиции во входных данных, а в prev содержится позиция предыдущей позиции с этим хэш-значением. По сути, head[h] — это заголовок связного списка позиций префиксов с хэшем h , а prev[x] получает элемент, предшествующий x в списке.
Для вставки в хэш-таблицу новой строковой позиции prev обновляется, чтобы указывать на предыдущую head , а затем обновляется сама head :
Обратите внимание на операцию по модулю при индексировании в prev : нас интересуют только те позиции, которые попадают в текущее окно.
Вместо того, чтобы с нуля вычислять хэш-значение для каждого трёхсимвольного префикса, мы воспользуемся кольцевым хэшем и будем постоянно обновлять его, чтобы в его значении отражались только три последних символа:
Хэш-карту потом можно использовать для эффективного поиска предыдущих совпадений с последовательностью, как показано ниже. Поиск совпадений — самая ресурсозатратная операция сжатия, поэтому мы ограничим глубину поиска по списку.
Изменение различных параметров, вроде глубины поиска по списку префиксов и выполнения ленивого сравнения, как будет описано ниже, — это способ повышения скорости за счёт снижения степени сжатия. Настройки в нашем коде выбраны так, чтобы соответствовать максимальному уровню сжатия в zlib.
Можно завершить функцию lz77_compress этим кодом для поиска предыдущих совпадений:
Этот код ищет самую длинную обратную ссылку, которая может быть сгенерирована на текущей позиции. Но прежде чем её выдать, программа решает, можно ли на следующей позиции найти ещё более длинное совпадение. В zlib это называется оценкой с помощью ленивого сравнения. Это всё ещё жадный алгоритм: он выбирает самое длинное совпадение, даже если текущее более короткое позволяет позднее получить совпадение ещё длиннее и достичь более сильного сжатия.
Сжатие Lempel-Ziv может работать как быстро, так и медленно. Zopfli потратил много времени на поиски оптимальных обратных ссылок, чтобы выжать дополнительные проценты сжатия. Это полезно для данных, которые сжимаются один раз и потом многократно используются, например, для статичной информации на веб-сервере. На другой стороне шкалы находятся такие компрессоры, как Snappy и LZ4, которые сравнивают только с последним 4-байтным префиксом и работают очень быстро. Такой тип сжатия полезен в базах данных и RPC-системах, в которых время, потраченное на сжатие, окупается экономией времени при отправке данных по сети или на диск.
Идея использовать исходные данные в качестве словаря очень элегантна, но и от статичного словаря можно получить пользу. Brotli — алгоритм на основе LZ77, но он также использует большой статичный словарь из строковых, которые часто встречаются в сети.
Код LZ77 можно посмотреть в lz77.h и lz77.c.
Код Хаффмана
Вторым алгоритмом Zip-сжатия является код Хаффмана.
Термин код в данном контексте является отсылкой к системе представления данных в какой-то другой форме. В данном случае нас интересует код, с помощью которого можно эффективно представлять литералы и обратные ссылки, сгенерированные алгоритмом Lempel-Ziv.
Традиционно англоязычный текст представляют с помощью American Standard Code for Information Interchange (ASCII). Эта система присваивает каждому символу число, которые обычно хранятся в 8-битном представлении. Вот ASCII-коды для прописных букв английского алфавита:
| A | 01000001 | N | 01001110 |
| B | 01000010 | O | 01001111 |
| C | 01000011 | P | 01010000 |
| D | 01000100 | Q | 01010001 |
| E | 01000101 | R | 01010010 |
| F | 01000110 | S | 01010011 |
| G | 01000111 | T | 01010100 |
| H | 01001000 | U | 01010101 |
| I | 01001001 | V | 01010110 |
| J | 01001010 | W | 01010111 |
| K | 01001011 | X | 01011000 |
| L | 01001100 | Y | 01011001 |
| M | 01001101 | Z | 01011010 |
Один байт на символ — это удобный способ хранения текста. Он позволяет легко обращаться к частям текста или изменять их, и всегда понятно, сколько байтов требуется для хранения N символов, или сколько символов хранится в N байтов. Однако это не самый эффективный способ с точки зрения занимаемого объёма. Например, в английском языке буква E используется чаще всего, а Z — реже всего. Поэтому с точки зрения объёма эффективнее использовать более короткое битовое представление для E и более длинное для Z, а не присваивать каждому символу одинаковое количество битов.
Код, который разным исходным символам задаёт кодировки разной длины, называется кодом переменной длины. Самый известный пример — азбука Морзе, в которой каждый символ кодируется точками и тире, изначально передававшимися по телеграфу короткими и длинными импульсами:
| A | • − | N | − • |
| B | − • • • | O | − − − |
| C | − • − • | P | • − − • |
| D | − • • | Q | − − • − |
| E | • | R | • − • |
| F | • • − • | S | • • • |
| G | − − • | T | − |
| H | • • • • | U | • • − |
| I | • • | V | • • • − |
| J | • − − − | W | • − − |
| K | − • − | X | − • • − |
| L | • − • • | Y | − • − − |
| M | − − | Z | − − • • |
Одним из недостатков азбуки Морзе является то, что одно кодовое слово может быть префиксом другого. Например, • • − • не имеет уникального декодирования: это может быть F или ER. Это решается с помощью пауз (длиной в три точки) между буквами в ходе передачи. Однако было бы лучше, если бы кодовые слова не могли являться префиксами других слов. Такой код называется беспрефиксным. ASCII-код фиксированной длины является беспрефиксным, потому что кодовые слова всегда одной длины. Но коды переменной длины тоже могут быть беспрефиксными. Телефонные номера чаще всего беспрефиксные. Прежде чем в Швеции ввели телефон экстренной помощи 112, пришлось поменять все номера, начинавшиеся со 112. А в США нет ни одного телефонного номера, начинающегося с 911.
Для минимизации размера закодированного сообщения лучше использовать беспрефиксный код, в котором часто встречающиеся символы имеют более короткие кодовые слова. Оптимальным кодом будет такой, который генерирует самый короткий возможный результат — сумма длин кодовых слов, умноженная на их частоту появления, будет минимально возможной. Это называется беспрефиксным кодом с минимальной избыточностью, или кодом Хаффмана, в честь изобретателя эффективного алгоритма для генерирования таких кодов.
Алгоритм Хаффмана
Изучая материалы для написания своей докторской диссертации по электронной инженерии в MIT, Дэвид Хаффман прослушал курс по теории информации, который читал Роберт Фано. Согласно легенде, Фано позволил своим слушателям выбирать: писать финальный экзамен или курсовую. Хаффман выбрал последнее, и ему дали тему поиска беcпрефиксных кодов с минимальной избыточностью. Предполагается, что он не знал о том, что над этой задачей в то время работал сам Фано (самым известный методом в те годы был алгоритм Шеннона-Фано). Работа Хаффмана была опубликована в 1952-м под названием A Method for the Construction of Minimum-Redundancy Codes in 1952. И с тех пор его алгоритм получил широкое распространение.
Дэвид Хаффман пресс-релиз UC Santa Cruz.
Алгоритм Хаффмана создаёт беспрефиксный код с минимальной избыточностью для набора символов и их частоты использования. Алгоритм многократно выбирает два символа, которые реже всего встречаются в исходных данных, — допустим, Х и Y — и заменяет их на составной символ, означающий «X или Y». Частотой появления составного символа является сумма частот двух исходных символов. Кодовые слова для X и Y могут быть любыми кодовыми словами, которые присвоены составному символу «X или Y», за которым идёт 0 или 1, чтобы отличать друг от друга исходные символы. Когда входные данные уменьшаются до одного символа, алгоритм прекращает работу (видеообъяснение).
Вот пример работы алгоритма на маленьком наборе символов:
| Символ | Частота |
| A | 6 |
| B | 4 |
| C | 2 |
| D | 3 |
Первая итерация обработки:
Два самых редких символа, C и D, убираются из набора и заменяются составным символом, частота которого является суммой частот C и D:
Теперь самыми редкими символами стали B и составной символ с частотой 5. Они убираются из набора и заменяются составным символом с частотой 9:
Наконец, A и составной символ с частотой 9 объединяются в новый символ с частотой 15:
Весь набор свёлся к одному символу, обработка завершена.
Алгоритм создал структуру, которая называется деревом Хаффмана. Входные символы — это листья, а чем больше частота у символа, тем выше он расположен. Начиная от корня дерева можно сгенерировать кодовые слова для символов, добавляя 0 или 1, когда переходим влево или вправо соответственно. Получится так:
| Символ | Кодовое слово |
| A | 0 |
| B | 10 |
| C | 110 |
| D | 111 |
Ни одно кодовое слово не является префиксом для какого-то другого. Чем чаще встречается символ, тем короче его кодовое слово.
Дерево можно использовать и для декодирования: начинаем с корня и идём направо или налево для значение с 0 или 1 перед символом. Например, строка 010100 декодируется в ABBA.
Обратите внимание, что длина каждого кодового слова эквивалентна глубине соответствующего узла дерева. Как мы увидим в следующей части, нам не нужно настоящее дерево для присвоения кодовых слов. Достаточно знать длину самих слов. Таким образом, результатом работы нашей реализации алгоритма Хаффмана будут длины кодовых слов.
Для хранения набора символов и эффективного нахождения наименьших частот мы воспользуемся структурой данных двоичная куча. В частности, нас интересует min-куча, поскольку минимальное значение должно быть наверху.
Чтобы отслеживать частоту n символов, будем использовать кучу из n элементов. Также при каждом создании составного символа мы хотим «связывать» с ним оба исходных символа. Поэтому каждый символ будет иметь «элемент связи».
Для хранения n -элементной кучи и n элементов связи будем использовать массив из n * 2 + 1 элементов. Когда два символа в куче заменяются одним, мы будем использовать второй элемент для сохранения ссылки на новый символ. Этот подход основан на реализации Managing Gigabytes Уиттена, Моффата и Белла.
В каждом узле куче мы будем использовать 16 старших битов для хранения частоты символа, а 16 младших — для хранения индекса элемента связи символа. За счёт использования старших битов разница частот будет определяться результатом 32-битного сравнения между двумя элементами кучи.
Из-за такого представления нам нужно удостовериться, что частота символов всегда укладывается в 16 битов. После завершения работы алгоритма финальный составной символ будет иметь частоту всех объединённых символов, то есть эта сумма должна помещаться в 16 битов. Наша реализация Deflate будет проверять это с помощью одновременной обработки до 64 535 символов.
Символы с нулевой частотой будут получать кодовые слова нулевой длины и не станут участвовать в составлении кодировки.
Если кодовое слово достигнет заданной максимальной глубины, мы «сгладим» распределение частот, наложив частотное ограничение, и попробуем опять (да, с помощью goto ). Есть и более сложные способы выполнения ограниченного по глубине кодирования Хаффмана, но этот прост и эффективен.
Элегантной альтернативой варианту с двоичной кучей является сохранение символов в двух очередях. Первая содержит исходные символы, отсортированные по частоте. Когда создаётся составной символ, он добавляется во вторую очередь. Таким образом символ с наименьшей частотой всегда будет на первой позиции одной из очередей. Этот подход описан Jan van Leeuwen в On the Construction of Huffman Trees (1976).
Кодирование Хаффмана оптимально для беспрефиксных кодов, но в других случаях есть более эффективные способы: арифметическое кодирование и асимметричные системы счисления.
Канонические коды Хаффмана
В примере выше мы построили дерево Хаффмана:
Если идти от корня и использовать 0 для левой ветки и 1 для правой, то мы получим такие коды:
| Символ | Кодовое слово |
| A | 0 |
| B | 10 |
| C | 110 |
| D | 111 |
Решение об использовании 0 для левой ветки и 1 для правой выглядит произвольным. Если сделать наоборот, то получим:
| Символ | Кодовое слово |
| A | 1 |
| B | 01 |
| C | 001 |
| D | 000 |
Мы можем произвольно помечать две ветки, исходящие из ноды, нулём и единицей (главное, чтобы метки были разными), и всё равно получим эквивалентный код:
| Символ | Кодовое слово |
| A | 0 |
| B | 11 |
| C | 100 |
| D | 101 |
Хотя алгоритм Хаффмана дает требуемые длины кодовых слов для беспрефиксного кода с минимальной избыточностью, есть множество способов присвоения отдельных кодовых слов.
Учитывая длину кодового слова, вычисляемую по алгоритму Хаффмана, канонический код Хаффмана присваивает символам кодовые слова определённым образом. Это полезно, поскольку позволяет хранить и передавать длины кодовых слов со сжатыми данными: декодер сможет восстановить кодовые слова на основе их длин. Конечно, можно хранить и передавать частоты символов и запускать в декодере алгоритм Хаффмана, но это потребует от декодера больше работы и больше места для хранения. Другим очень важным свойством является то, что структура канонических кодов использует эффективное декодирование.
Идея заключается в том, чтобы присваивать символам кодовые слова последовательно, под одному за раз. Первым кодовым словом является 0. Следующим будет слово длиной предыдущее слово + 1. Первое слово длиной N составляется из последнего слова длиной N-1, добавления единицы (чтобы получилось новое кодовое слово) и смещения на один шаг влево (для увеличения длины).
В терминологии дерева Хоффмана кодовые слова последовательно присваиваются листьям в порядке слева-направо, по одному уровню за раз, смещаясь влево при переходе на следующий уровень.
В нашем примере A-B-C-D алгоритм Хаффмана присвоил кодовые слова с длинами 1, 2, 3 и 3. Первым словом является 0. Это также последнее слово длиной 1. Для длины 2 мы берём 0 и добавляем 1 для получения следующего кода, который станет префиксом двухбитных кодов, смещаемся влево и получаем 10. Это теперь последнее слово длиной 2. Для получения длины 3 мы добавляем 1 и смещаемся: 110. Для получения следующего слова длиной 3 мы добавляем 1: 111.
| Символ | Кодовое слово |
| A | 0 |
| B | 10 |
| C | 110 |
| D | 111 |
Ниже показана реализация генератора канонических кодов. Обратите внимание, что алгоритм Deflate ожидает, что кодовые слова будут генерироваться по принципу LSB-first (сначала младшим значащим битом). То есть первый бит кодового слова должен храниться в наименьшем значащем бите. Это означает, что нам нужно поменять порядок битов, например, с помощью поисковой таблицы.
Теперь соберём всё вместе и напишем код инициализации кодировщика:
Также сделаем функцию для настройки кодировщика с помощью уже вычисленных длин кодов:
Эффективное декодирование Хаффмана
Самый простой способ декодирования Хаффмана заключается в обходе дерева начиная с корня, считывая по одному биту входных данных за раз и решая, какую ветку брать следующей, левую или правую. Когда достигается листовой узел, это декодированный символ.
Этому методу часто учат в университетах и книгах. Он прост и элегантен, но обрабатывать по одному биту за раз слишком медленно. Гораздо быстрее декодировать с помощью поисковой таблицы. Для вышеприведённого примера, в котором максимальная длина кодового слова равна трём битам, можно использовать такую таблицу:
| Биты | Символ | Длина кодового слова |
| 000 | A | 1 |
| 001 | A | 1 |
| 010 | A | 1 |
| 011 | A | 1 |
| 100 | B | 2 |
| 101 | B | 2 |
| 110 | C | 3 |
| 111 | D | 3 |
Хотя символов всего четыре, нам нужна таблица с восемью записями, чтобы охватить все возможные трёхбитные комбинации. Символы с кодовыми словами короче трёх битов имеют в таблице по несколько записей. Например, слово 10 было «дополнено» 100 и 101, чтобы охватить все трёхбитные комбинации, начинающиеся с 10.
Чтобы декодировать таким образом, нужно проиндексировать в таблице с помощью следующих трёх входных битов и немедленно найти соответствующий символ и длину его кодового слова. Длина важна, потому что несмотря на то, что мы смотрели на следующие три бита, нам нужно получить такое же количество входных битов, какова длина кодового слова.
Метод на основе поисковой таблицы работает очень быстро, но у него есть недостаток: размер таблицы удваивается при каждом дополнительном бите в длине кодового слова. То есть построение таблицы замедляется экспоненциально, и если она перестаёт помещаться в кэш процессора, то метод начинает работать медленно.
Из-за этого таблицу поиска обычно используют только для кодовых слов не больше определённой длины. А для более длинных слов применяют другой подход. Как при кодировании Хаффмана более частым символами присваиваются более короткие кодовые слова, так и использование поисковой таблицы для коротких кодовых слов является во многих случаях прекрасной оптимизацией.
В zlib используется несколько уровней поисковых таблиц. Если кодовое слово слишком длинное для первой таблицы, то поиск перейдёт во вторичную таблицу, чтобы проиндексировать оставшиеся биты.
Но есть и другой, очень элегантный метод, основанный на свойствах канонических кодов Хаффмана. Он описывается в статье On the Implementation of Minimum Redundancy Prefix Codes (Моффат и Турпин, 1997-й), а также объясняется в статье The Lost Huffman Paper Чарльза Блума.
Возьмём кодовые слова из канонической версии: 0, 10, 110, 111. Будем отслеживать первые кодовые слова каждой из длин, а также номер каждого кодового слова в общей последовательности — «символьный индекс».
| Длина кодового слова | Первое кодовое слово | Первый символьный индекс |
| 1 | 0 | 1 (A) |
| 2 | 10 | 2 (B) |
| 3 | 110 | 3 (С) |
Поскольку кодовые слова присваиваются последовательно, то если нам известно количество битов, мы можем в вышеприведённой таблице найти символ, который представляют эти биты. Например, для трёхбитного 111 мы видим, что это смещение на единицу от первого кодового слова этой длины (110). Первым символьным индексом такой длины является 3, а смещение на единицу даёт нам индекс 4. Другая таблица сопоставляет символьный индекс с символом:
Маленька оптимизация: вместо раздельного хранения первого символьного индекса и первого кодового слова мы можем хранить в таблице первый индекс минус первое кодовое слово:
Чтобы понять, сколько битов нужно оценить, мы снова воспользуемся свойством последовательности кода. В нашем примере все валидные однобитные кодовые слова строго меньше 1, двухбитные — строго меньше 11, трёхбитные — меньше 1000 (по сути, верно для всех трёхбитных значений). Иными словами, валидное N-битное кодовое слово должно быть строго меньше первого N-битного кодового слова плюс количество N-битных кодовых слов. Более того, мы можем смещать влево эти границы, чтобы все они были трёхбитной ширины. Давайте назовём это ограничительными битами для каждой из длин кодовых слов:
| Длина кодового слова | Ограничительные биты |
| 1 | 100 |
| 2 | 110 |
| 3 | 1000 |
Ограничитель для длины 3 переполнился до 4 битов, но это лишь означает, что подойдёт любое трёхбитное слово.
Мы можем искать среди трёхбитных входных данных и сравнивать с ограничительными битами, чтобы понять, какой длины наше кодовое слово. После завершения мы смещаем входные биты, только чтобы вычислить их правильное количество, а затем находим символьный индекс:
Временная сложность процесса линейная относительно количества битов в кодовых словах, но зато место расходуется эффективно, на каждом шаге требуется только загрузка и сравнение, а поскольку более короткие кодовые слова встречаются чаще, метод позволяет оптимизировать сжатие во многих ситуациях.
Полный код декодера:
Для настройки декодера мы заранее вычислим канонические коды, как для huffman_encoder_init, и заполним разные таблицы:
Deflate
Алгоритм Deflate, представленный в PKZip 2.04c в 1993-м, это стандартный метод сжатия в современных Zip-файлах. Он также применяется в gzip, PNG и многих других форматах. В нём используется сочетание сжатия LZ77 и кодирования Хаффмана, которое мы рассмотрим и реализуем в этом разделе.
До Deflate в PKZip использовались методы сжатия Shrink, Reduce и Implode. Сегодня они встречаются редко, хотя после появления Deflate ещё какое-то время были в ходу, потому что потребляли меньше памяти. Но мы их рассматривать не будем.
Битовые потоки
Deflate сохраняет кодовые слова Хаффмана в битовом потоке по принципу LSB-first. Это означает, что первый бит потока сохраняется в наименее младшем значащем бите первого байта.
Рассмотрим битовый поток (читается слева направо) 1-0-0-1-1. Когда он сохраняется по принципу LSB-first, то значение байта становится 0b00011001 (двоичное) или 0x19 (шестнадцатеричное). Может показаться, что поток просто представлен задом наперёд (в некотором смысле так и есть), но преимущество заключается в том, что так нам проще получить первые N битов из компьютерного слова: просто скрываем N младших битов.
Эти процедуры взяты из bitstream.h:
Нашему декодеру Хаффмана нужно смотреть на следующие биты в потоке (достаточно битов для самого длинного возможного кодового слова), а затем продолжать поток на количество битов, использованных декодированным символом:
Суть в том, что на 64-битных машинах istream_bits обычно можно исполнять как инструкцию одиночной загрузки и каких-то арифметических действий, учитывая, что элементы структуры istream_t находятся в регистрах. read64le реализован в bits.h (современные компиляторы преобразуют его в одиночную 64-битную загрузку по принципу little-endian):
Также нам нужна функция для продолжения битового потока к границе следующего байта:
Для исходящего битового потока мы пишем биты с помощью последовательности операций чтение-модификация-запись. В быстром случае записать бит можно с помощью 64-битного чтения, какой-то битовой операции и 64-битной записи.
Также нам нужно эффективно записывать в поток байты. Конечно, можно многократно выполнять 8-битные записи, но гораздо быстрее будет использовать memcpy :
Распаковка (Inflation)
Поскольку алгоритм сжатия называется Deflate — сдувание, извлечение воздуха из чего-либо, — то процесс распаковки иногда называют Inflation (накачивание). Если первым делом изучить этот процесс, то мы поймём, как работает формат. Код можно посмотреть в первой части deflate.h и deflate.c, bits.h, tables.h и tables.c (сгенерирован с помощью generate_tables.c).
Данные, сжатые с помощью Deflate, хранятся в виде серии блоков. Каждый блок начинается с 3-битного заголовка, в котором первый (младший значимый) бит задаётся в том случае, если это финальный блок серии, а остальные два бита обозначают его тип.
Есть три типа блоков: несжатый (0), сжатый с помощью фиксированных кодов Хаффмана (1) и сжатый с помощью «динамических» кодов Хаффмана (2).
Этот код выполняет распаковку с использованием вспомогательных функций для разных типов блоков, которые мы реализуем позднее:
Несжатые Deflate-блоки
Это «хранимые» блоки, простейший тип. Он начинается со следующей 8-битной границы битового потока с 16 битного слова (len), обозначающего длину блока. За ним идёт другое 16-битное слово (nlen), которое дополняет (порядок битов инвертирован) слов len. Предполагается, что nlen действует как простая контрольная сумма len: если файл повреждён, то, вероятно, значения уже не будут взаимодополняющими и программа сможет обнаружить ошибку.
После len и nlen идут несжатые данные. Поскольку длина блока представляет собой 16-битное значение, размер данных ограничен 65 535 байтами.
Deflate-блоки с применением фиксированных кодов Хаффмана
Сжатые Deflate-блоки используют код Хаффмана для представления последовательности LZ77-литералов. Обратные ссылки прерываются с помощью маркеров конца блока. Для литералов, длин обратных ссылок и маркеров используется код Хаффмана litlen. А для расстояний обратных ссылок используется код dist.
С помощью litlen кодируются значения в диапазоне 0-285. Значения 0-255 используются для байтов литералов, 256 — маркер конца блока, а 257-285 используются для длин обратных ссылок.
Обратные ссылки бывают длиной 3-258 байтов. Litlen-значение определяет базовую длину, к которой из потока добавляется ноль или больше дополнительных битов, чтобы получилась полная длина согласно нижеприведённой таблице. Например, litlen-значение 269 означает базовую длину 19 и два дополнительных бита. Прибавка двух битов из потока даёт финальную длину от 19 до 22.
| Litlen | Дополнительные биты | Длины |
| 257 | 0 | 3 |
| 258 | 0 | 4 |
| 259 | 0 | 5 |
| 260 | 0 | 6 |
| 261 | 0 | 7 |
| 262 | 0 | 8 |
| 263 | 0 | 9 |
| 264 | 0 | 10 |
| 265 | 1 | 11–12 |
| 266 | 1 | 13–14 |
| 267 | 1 | 15–16 |
| 268 | 1 | 17–18 |
| 269 | 2 | 19–22 |
| 270 | 2 | 23–26 |
| 271 | 2 | 27–30 |
| 272 | 2 | 31–34 |
| 273 | 3 | 35–42 |
| 274 | 3 | 43–50 |
| 275 | 3 | 51–58 |
| 276 | 3 | 59–66 |
| 277 | 4 | 67–82 |
| 278 | 4 | 83–98 |
| 279 | 4 | 99–114 |
| 280 | 4 | 115–130 |
| 281 | 5 | 131–162 |
| 282 | 5 | 163–194 |
| 283 | 5 | 195–226 |
| 284 | 5 | 227–257 |
| 285 | 0 | 258 |
Обратите внимание, что litlen-значение 284 плюс 5 дополнительных битов может представлять длины от 227 до 258, однако в спецификации указано, что длина 258 — максимальная длина обратной ссылки — должна быть представлена с помощью отдельного litlen-значения. Предполагается, что это позволяет сократить кодирование в ситуациях, когда часто встречается максимальная длина.
Декомпрессор использует использует таблицу для получения из litlen-значения (минус 257) базовой длины и дополнительных битов:
Фиксированный litlen-код Хаффмана является каноническим и использует следующие длины кодовых слов (286–287 не являются корректными litlen-значениями, но они участвуют в генерировании кодов):
| Litlen-значения | Длина кодового слова |
| 0–143 | 8 |
| 144–255 | 9 |
| 256–279 | 7 |
| 280–287 | 8 |
Декомпрессор сохраняет эти длины в таблицу, удобную для передачи в huffman_decoder_init :
Расстояния обратных ссылок меняются от 1 до 32 768. Они кодируются с помощью схемы, которая аналогична схеме кодирования длин. Код Хаффмана dist кодирует значения от 0 до 29, каждое из которых соответствует базовой длине, к которой добавляются дополнительные биты для получения финального расстояния:
| Dist | Дополнительные биты | Расстояния |
| 0 | 0 | 1 |
| 1 | 0 | 2 |
| 2 | 0 | 3 |
| 3 | 0 | 4 |
| 4 | 1 | 5–6 |
| 5 | 1 | 7–8 |
| 6 | 2 | 9–12 |
| 7 | 2 | 13–16 |
| 8 | 3 | 17–24 |
| 9 | 3 | 25–32 |
| 10 | 4 | 33–48 |
| 11 | 4 | 49–64 |
| 12 | 5 | 65–96 |
| 13 | 5 | 97–128 |
| 14 | 6 | 129–192 |
| 15 | 6 | 193–256 |
| 16 | 7 | 257–384 |
| 17 | 7 | 385–512 |
| 18 | 8 | 513–768 |
| 19 | 8 | 769–1024 |
| 20 | 9 | 1025–1536 |
| 21 | 9 | 1537–2048 |
| 22 | 10 | 2049–3072 |
| 23 | 10 | 3073–4096 |
| 24 | 11 | 4097–6144 |
| 25 | 11 | 6145–8192 |
| 26 | 12 | 8193–12288 |
| 27 | 12 | 12289–16384 |
| 28 | 13 | 16385–24576 |
| 29 | 13 | 24577–32768 |
Фиксированный код Хаффмана dist является каноническим. Все кодовые слова длиной 5 битов. Он прост, декомпрессор хранит коды в таблице, которую можно использовать с huffman_decoder_init (dist-значения 30–31 не являются корректными. Указано, что они участвуют в генерировании кодов Хаффмана, но на самом деле не оказывают никакого эффекта):
Код декомпрессии, или распаковки — Deflate-блок с использованием фиксированных кодов Хаффмана:
Обратите внимание на такую оптимизацию: когда в исходящем буфере недостаточно места, мы выдаём обратные ссылки с помощью нижеприведённой функции, которая копирует по 64 бита за раз. Это «неаккуратно» в том смысле, что при этом часто копируется несколько дополнительных байтов (до следующего значения, кратного 8). Но работает гораздо быстрее lz77_output_backref , потому что требует меньше циклических итераций и обращений к памяти. По сути, короткие обратные ссылки теперь будут обрабатываться за одну итерацию, что очень хорошо для прогнозирования ветвления.
Deflate-блоки с применением динамических кодов Хаффмана
Deflate-блоки, использующие динамические коды Хаффмана, работают так же, как описано выше. Но вместо заранее определённых кодов для litlen и dist они используют коды, хранящиеся в самом Deflate-потоке, в начале блока. Название, пожалуй, неудачное, поскольку динамическими кодами Хаффмана также называют коды, которые меняются в ходе кодирования — это адаптивное кодирование Хаффмана. Описанные здесь коды не имеют к той процедуре никакого отношения. Они динамические лишь в том смысле, что разные блоки могут использовать разные коды.
Генерирование динамических litlen- и dist-кодов является самой сложной частью Deflate-формата. Но как только коды сгенерированы, декомпрессия выполняется так же, как описано в предыдущей части, с использованием inf_block :
Litlen- и dist-коды для динамических Deflate-блоков хранятся в виде серий длин кодовых слов. Сами длины закодированы с помощью третьего кода Хаффмана — codelen. Этот код определяется длиной кодовых слов ( codelen_lens ), которые хранятся в блоке (я уже говорил, что это сложно?).
В начале динамического блока находятся 14 битов, которые определяют количество litlen-, dist- и codelen-длин кодовых слов, которые нужно прочитать из блока:
Затем идут длины кодовых слов для codelen-кода. Эти длины представляют собой обычные трёхбитные значения, но записанные в особом порядке, который задан в codelen_lengths_order . Поскольку нужно определить 19 длин, из потока будет прочитан только num_codelen_lens ; всё остальное является неявно нулевым. Длины перечисляются в определённом порядке, чтобы нулевые длины с большей вероятностью попадали в конец списка и не сохранялись в блоке.
С помощью настройки codelen-декодера мы можем считывать из потока длины кодовых слов litlen и dist.
16, 17 и 18 не являются настоящими длинами, это индикаторы того, что предыдущую длину нужно повторить какое-то количество раз, или что нужно повторить нулевую длину:
Обратите внимание, что litlen- и dist-длины считываются одна за другой в массив code_lengths . Они не могут считываться отдельно, потому что прогоны длин кода могут переноситься с последних litlen-длин на первые dist-длины.
Подготовив длины кодовых слов, мы можем настроить декодеры Хаффмана и вернуться к задаче декодирования литералов и обратных ссылок:
Сжатие (Deflation)
В предыдущих частях мы создали все инструменты, необходимые для Deflate-сжатия: Lempel-Ziv, кодирование Хаффмана, битовые потоки и описание трёх типов Deflate-блоков. А в этой части мы соберём всё вместе, чтобы получилось Deflate-сжатие.
Сжатие Lempel-Ziv парсит исходные данные в последовательность обратных ссылок и литералов. Эту последовательность нужно разделить и закодировать в Deflate-блоки, как описано в предыдущей части. Выбор способа разделения часто называют разбиением на блоки. С одной стороны, каждый новый блок означает какие-то накладные расходы, объём которых зависит от типа блока и его содержимого. Меньше блоков — меньше накладных расходов. С другой стороны, эти расходы на создание нового блока могут окупаться. Например, если характеристики данных позволяют эффективнее выполнять кодирование Хаффмана и уменьшать общий объём генерируемых данных.
Разбиение на блоки — сложная задача по оптимизации. Некоторые компрессоры (например, Zopfli) стараются лучше других, но большинство просто используют жадный подход: выдают блоки, как только те достигают определённого размера.
У разных типов блоков свои ограничения размеров:
- Несжатые блоки могут содержать не больше 65 535 байтов.
- Фиксированные коды Хаффмана не имеют максимального размера.
- Динамические коды Хаффмана в целом не имеют максимального размера, но поскольку наша реализация алгоритма Хаффмана используется 16-битные последовательности символов, мы ограничены 65 535 символами.
Для отслеживания исходящего битового потока и содержимого текущего блока в ходе сжатия будем использовать структуру:
Чтобы добавлять в блок результаты работы lz77_compress будем использовать функции обратного вызова, и по достижении максимального размера запишем блок в битовый поток:
Самое интересное — запись блоков. Если блок не сжат, то всё просто:
Для записи статичного блока Хаффмана мы сначала сгенерируем канонические коды на основе фиксированных длин кодовых слов для litlen- и dist-кодов. Затем итерируем блок, записывая символы, которые используют эти коды:
Конечно, записывать динамические блоки Хаффмана сложнее, потому что они содержат хитрое кодирование litlen- и dist-кодов. Для представления этого кодирования воспользуемся такой структурой:
Сначала мы отбрасываем хвост их нулевых длин кодовых слов litlen и dist, а потом копируем их в обычный массив для последующего кодирования. Мы не можем отбросить все нули: невозможно закодировать Deflate-блок, если в нём ни одного dist-кода. Также невозможно иметь меньше 257 litlen-кодов, но поскольку у нас всегда есть маркер окончания байта, то всегда будут ненулевая длина кода для символа 256.
Сложив длины кодов в один массив, мы выполняем кодирование, применяя специальные символы для прогона одинаковых длин кодов.
Использованные для кодирования символы будут записаны с помощью кода Хаффмана — codelen. Длины кодовых слов из кода codelen записываются в блок в определённом порядке, чтобы нулевые длины с большей вероятностью оказывались в конце. Вот функция, подсчитывающая, сколько длин нужно записать:
Допустим, мы уже задали litlen- и dist-коды, настроили кодирование длин их кодовых слов и код для этих длин. Теперь можем записать динамический блок Хаффмана:
Для каждого блока мы хотим использовать тот тип, которому требуется наименьшее количество битов. Длину несжатого блока можно вычислить быстро:
Для блоков, закодированных по Хаффману, можно вычислить длину тела с помощью litlen- и dist-частот символов и длин кодовых слов:
Общая длина статичного блока равна 3 битам заголовка плюс длина тела. Вычисление размера заголовка динамического блока требует гораздо больше работы:
Теперь соберём всё воедино и создадим главную функцию записи блоков:
Наконец, инициатор всего процесса сжатия должен задать начальное состояние, запустить сжатие Lempel-Ziv и записать получившийся блок:
Формат Zip-файлов
Выше мы рассмотрели, как работает Deflate-сжатие, используемое в Zip-файлах. А что насчёт самого формата файлов? В этой части мы подробно рассмотрим его устройство и реализацию. Код доступен в zip.h и zip.c.
Обзор
Формат файлов описан в PKZip Application Note:
- Каждый файл, или элемента архива, в Zip-файле имеет локальный заголовок файла с метаданными об элементе.
- Центральный каталог служит индексом архива. Он содержит центральный заголовок файла для каждого элемента архива, копию метаданных из локального заголовка файла, а также дополнительную информацию, такую как смещение элемента в Zip-файле.
- В конце файла, сразу после центрального каталога конец записи центрального каталога. Она содержит размер и позицию центрального каталога, а также может содержать комментарии обо всём архиве. Это начальная точка чтения Zip-файла.
Каждый элемент архива сжимается и хранится индивидуально. Это означает, что даже если между файлами в архиве есть совпадения, они не будут учитываться для улучшения сжатия.
Расположение центрального каталога в конце позволяет постепенно достраивать архив. По мере сжатия файлов элементов они дописываются в архив. Индекс записывается после всех сжатых размеров, что позволяет узнать смещения всех файлов. Добавлять файлы в существующий архив довольно легко, он помещается после последнего элемента, а центральный каталог перезаписывается.
Возможность постепенно создавать архивы была особенно важна для распространения информации на многочисленных дискетах или томах. По мере сжатия PKZip предлагал пользователям вставлять новые дискеты, а на последнюю (последние) записывал центральный каталог. Для распаковки многотомного архива PKZip сначала спрашивал последнюю дискету, чтобы записать прочитать центральный каталог, а затем остальные дискеты, необходимые для извлечения запрошенных файлов.
Вас это может удивить, но не существовало правила, запрещающего иметь в архиве несколько файлов с одинаковыми именами. Это могло приводить к большой путанице при распаковке: если есть несколько файлов с одинаковыми именами, то какой из них нужно распаковать? В свою очередь это могло приводить к проблемам в безопасности. Из-за бага «Master Key» в Android (CVE-2013-4787, слайды и видео с доклада на Black Hat) злоумышленник мог при установке программ обходить проверки операционной системой криптоподписей. Android-программы распространяются в APK-файлах, которые представляют собой Zip-файлы. Как выяснилось, если APK содержал несколько файлов с одинаковыми именами, код проверки подписи выбирал последний файл с таким именем, а инсталлятор выбирал первый файл, то есть проверка не выполнялась. Иными словами, это небольшое различие между двумя Zip-библиотеками позволяло обойти всю модель безопасности операционной системы.
В отличие от большинства форматов, Zip-файлы не должны начинаться с сигнатуры или магического числа. Вообще не указано, что Zip-файл должен начинаться каким-то конкретным образом, что легко позволяет создавать файлы, одновременно валидные и как Zip, и как другой формат — файлы-полиглоты. Например, самораспаковывающиеся Zip-архивы (например, pkz204g.exe) обычно одновременно и исполняемые, и Zip-файлы: первая часть является исполняемой, а за ней идёт Zip-файл (который распаковывается исполняемой частью). ОС может выполнять его как исполняемый, но Zip-программа откроет его как Zip-файл. Такая особенность могла стать причиной не требовать сигнатуру в начале файла.
Хотя такие файлы-полиглоты и умны, но они могут приводить к проблемам в безопасности, поскольку способны обмануть программы, старающиеся определить содержимое файла, а также позволяют доставлять зловредный код в месте с файлами разных типов. Например, в эксплойтах использовались GIFAR-файлы, которые одновременно являются корректными GIF-изображениями и Java-архивами (JAR, разновидность Zip-файлов). Подробнее об этой проблеме рассказывается в статье Abusing file formats (начиная со страницы 18).
Как мы увидим ниже, Zip-файлы используют для смещений и размеров 32-битные поля, чтобы ограничивать размер архива и его элементов четырьмя гигабайтами. В Application Note 4.5 PKWare добавила расширения формата, позволяющие использовать 64-битные смещения и размеры. Файлы, использующие эти расширения, относят к формату Zip64, но мы не будем их рассматривать.
Структуры данных
Конец записи центрального каталога
Конец записи центрального каталога (EOCDR) обычно используется в качестве начальной точки для чтения Zip-файла. В ней содержится расположение и размер центрального каталога, а также опциональные комментарии обо всём архиве.
В Zip-файлах, которые занимали несколько дискет — или томов, — EOCDR также содержала информацию о том, какой диск мы сейчас используем, на каком диске начинается центральный каталог и т.д. Сегодня эта функциональность используется редко, и код из этой статьи такие файлы не обрабатывает.
EOCDR определяется по сигнатуре ‘P’ ‘K’, за которой идут байты 5 и 6. За ней следует нижеприведённая структура, числа хранятся по принципу little-endian:
EOCDR должна располагаться в конце файла. Но поскольку в её хвосте может быть комментарий произвольной 16-битной длины, может потребоваться находиться конкретную позицию:
Записывать EOCDR несложно. Эта функция записывает и возвращает количество записанных байтов:
Центральный заголовок файла
Центральный каталог состоит из центральных заголовков файлов, записанных друг за другом, по одному для каждого элемента архива. Каждый заголовок начинается с сигнатуры ‘P’, ‘K’, 1, 2, а потом идёт такая структура:
made_by_ver и extract_ver кодируют информацию об ОС и версии программы, использованной для добавления этого элемента, а также о том, какая версия нужна для его извлечения. Самые важные восемь битов кодируют операционную систему (например, 0 означает DOS, 3 — Unix, 10 — Windows NTFS), а младшие восемь битов кодируют версию ПО. Зададим десятичное значение 20, что означает совместимость с PKZip 2.0.
gp_flag содержит разные флаги. Нас интересуют:
- Бит 0, обозначающий факт зашифровки элемента (мы это не будем рассматривать);
- И биты 1 и 2, кодирующие уровень Deflate-сжатия (0 — нормальное, 1 — максимальное, 2 — быстрое, 3 — очень быстрое).
mod_time и mod_date содержат дату и время изменения файла, закодированные в MS-DOS-формате. С помощью этого кода мы преобразуем обычные временные метки С time_t в MS-DOS-формат и из него:
Поле crc32 содержит значение циклического избыточного кода несжатых данных. Он используется для проверки целостности данных после извлечения. Реализация здесь: crc32.c.
comp_size и uncomp_size содержат сжатый и несжатый размер данных файла элемента. Следующие три поля содержат длины имени, комментарий и дополнительные данные, которые идут сразу после заголовка. disk_nbr_start предназначено для архивов, использующих несколько дискет.
int_attrs и ext_attrs описывают внутренние и внешние атрибуты файла. Внутренние относятся к содержимому файла, например, младший бит обозначает, содержит ли файл только текст. Внешние атрибуты показывают, является ли файл скрытым, только для чтения и т.д. Содержимое этих полей зависит от ОС, в частности, от made_by_ver . В DOS младшие 8 битов содержат байт атрибутов файла, который можно получить из системного вызова Int 21/AX=4300h. К примеру, бит 4 означает, что это директория, а бит 5 — что установлен атрибут «архив» (верно для большинства файлов в DOS). Насколько я понял, ради совместимости эти биты аналогично задаются и в других ОС. В Unix старшие 16 битов этого поля содержат биты режима файла, которые возвращаются stat(2) в st_mode .
lfh_offset говорит нам, где искать локальный заголовок файла. name — имя файла (C-строка), а comment — опциональный комментарий для этого элемента архива (С-строка). extra может содержать опциональные дополнительные данные вроде информации о владельце Unix-файла, более точные дату и время изменения или Zip64-поля.
Эта функция используется для чтения центральных заголовков файлов:
Локальный заголовок файла
Данные каждого элемента архива предваряются локальным заголовком файла, который повторяет большую часть информации из центрального заголовка.
Вероятно, дублирование данных в центральном и локальном заголовках было введено для того, чтобы PKZip при распаковке не держал в памяти весь центральный каталог. Вместо этого по мере извлечения каждого файла его имя и прочая информация может быть считана из локального заголовка. Кроме того, локальные заголовки полезны для восстановления файлов из Zip-архивов, в которых центральный каталог отсутствует или повреждён.
Однако эта избыточность является и главным источником неопределённости. Например, что будет, если имена файлов в центральном и локальном заголовках не совпадают? Это часто приводит к багам и проблемам в безопасности.
Дублируется не вся информация из центрального заголовка. Например, поля с атрибутами файлов. Кроме того, если задан третий младший значимый бит gp_flags (CRC-32), то поля сжатого и несжатого размера будут обнулены, а эту информацию можно будет найти в блоке Data Descriptor после данных самого файла (рассматривать не будем). Это позволяет записывать локальный заголовок до того, как станет известен размер файла элемента или до какого размера он будет сжат.
Локальный заголовок начинается с сигнатуры ‘P’, ‘K’, 3, 4, а потом идёт такая структура:
Эти функции считывают и записывают локальные заголовки, как и другие структуры данных:
Реализация Zip-считывания
С помощью вышеописанных функций мы реализуем чтение Zip-файла в память и получаем итератор для доступа к элементам архива:
Как я упоминал выше, итераторы элементов — это просто смещения центрального заголовка файла, через которые можно обращаться к данным элементов:
Реализация Zip-записи
Чтобы записать Zip-файл в буфер памяти, сначала нужно узнать, сколько памяти под него выделить. А раз мы не знаем, сколько данных сожмём, прежде чем попытаемся записать, то вычислим верхнюю границу на основе размеров несжатых элементов:
Этот код записывает Zip-файл с помощью Deflate-сжатия каждого элемента, уменьшая их размер:
HWZip
Теперь мы знаем, как читать и записывать Zip-файлы, как сжимать и распаковывать хранящиеся в них данные. Теперь напишем простую Zip-программу, содержащую все эти инструменты. Код доступен в hwzip.c.
Воспользуемся макросом для простой обработки ошибок и несколькими вспомогательными функциями для проверенного выделения памяти:
Другие две функции используются для чтения и записи файлов:
Наша Zip-программ может выполнять три функции: составлять список содержимого Zip-файлов и извлекать его, а также создавать Zip-файлы. Составление списка проще некуда:
Извлечение чуть сложнее. Мы будем использовать вспомогательные функции для нуль-терминирования имени файла (чтобы передавать его в fopen ) и распаковки:
Наша программа будет пропускать любые элементы архива, которые есть директории. Это делается для того, чтобы избежать так называемых path traversal-атак: зловредный архив используется для записи файла извне директории, указанной пользователем. Подробности читайте в Info-ZIP FAQ.
Чтобы создать Zip-архив, мы прочитаем входные файлы и скормим их zip_write . Поскольку стандартная библиотека C не позволяет получить время изменения файла, мы воспользуемся текущим временем (исправление этой особенности оставляю вам в качестве домашнего задания).
Наконец, main проверяет аргументы командной строки и решает, что делать:
Инструкции по сборке
Полный набор исходных файлов доступен в hwzip-1.0.zip. Как скомпилировать HWZip под Linux или Mac:
Под Windows, в командной строке разработчика в Visual Studio (если у вас нет Visual Studio, скачайте инструменты для сборки):
Заключение
Удивительно, как одновременно быстро и медленно развивается технология. Формат Zip был создан 30 лет назад на основе технологий пятидесятых и семидесятых годов. И хотя с тех пор многое изменилось, Zip-файлы, по сути, остались теми же и сегодня более распространены, чем когда-либо. Думаю, будет полезно хорошо разбираться в том, как они работают.
ZIP — где скачать, как установить, распаковать и запаковать архив
ZIP — это формат сжатия данных. Является одним из самых популярных в мире, повсеместно используется в Windows, так как встроенный в него архиватор создаёт архивы именно в формате .zip.
Как установить архиватор ZIP в Windows
Скачайте и устанавливайте: бесплатный архиватор 7-ZIP. Он подойдёт, если вас не устраивает встроенный в Windows архиватор.
Скачать 7-zip архиватор
Как создать архив ZIP в Windows
Чтобы создать архив, кликните правой кнопкой мыши на папке и в контекстном меню выберите Сжать или Создать архив.
Как распаковать архив ZIP в Windows
Чтобы распаковать архив, кликните правой кнопкой мыши по архиву, затем Разархивировать или Распаковать архив. Там же можно указать путь, в какую папку распаковать архив.
Как установить архиватор ZIP в Ubuntu, Debian, CentOS, FreeBSD
В Ubuntu, Debian установка ZIP происходит командой:
Если вы авторизованы не под root , предваряйте установку префиксом sudo, например
Установка ZIP в CentOS:
Установка ZIP во FreeBSD
Как запаковать архив ZIP в Ubuntu, Debian, CentOS
- zip — команда архиватора, не меняется
- -9r — ключи. Они определяют правила, по которым будет работать архиватор. Ключи указываются с дефисом в начале. Можно указывать ключи группой, можно каждый по отдельности, например -9 -r . Ключи могут быть следующие:
- 9 — степень сжатия. Может варьироваться от 1 до 9, от меньшего к большему, соответственно. Если указать 0, сжатия не произойдёт
- r — сжатие сделать рекурсивным. Это означает, что если в каталоге, который сжимаем, есть поддиректории, то их включаем в архив тоже
- x — исключить некоторые файлы или каталоги. Указывается отдельно в самом конце команды, например:
Путь может быть как относительным, так и абсолютным. Пример абсолютного пути:
Теперь, на архив установлен пароль pass . Чтобы увидеть содержимое архива или его распаковать, Вас будут просить ввести пароль к архиву.
Помните, что стандарт шифрования .zip очень слабый и относительно легко взламывается, поэтому старайтесь не шифровать зипом важную информацию.
Как распаковать архив zip в Ubuntu, Debian, CentOS
Чтобы распаковать архив .zip в текущий каталог, воспользуйтесь командой:
Если архив запаролен, то так:
где password — пароль к архиву.
Также, можно чётко указать путь для распаковки:
- Пример с относительным путём:
- Пример с абсолютным путём:
Чтобы распаковать только часть архива, можно воспользоваться командой:
Эта команда распакует файл index.php в текущий каталог.
Как увидеть содержимое архива ZIP в Linux
Чтобы увидеть содержимое архива .zip без распаковки, можно воспользоваться ключом -l
Методы архивации папки с файлами
Чтобы заархивировать папку с файлами, можно воспользоваться встроенными средствами системы Windows или установить дополнительные специализированные программы, которые предназначены для сжатия.
Способ 1: Встроенный инструмент системы
Самый простой и быстрый способ добавить папку в архив – это применение встроенного инструмента, сжимающего данные в формат ZIP. Он предназначен для простой компрессии файлов и не предполагает дополнительных возможностей. Заархивировать папку можно через контекстное меню ОС:
- Щелкните по папке, которую желаете заархивировать, правой кнопкой мыши. В контекстном меню найдите пункт «Отправить» и наведите на него курсор. Появится дополнительный список, из которого выберите «Сжатая ZIP-папка».
- На экране отобразится процесс сжатия. Дождитесь окончания процедуры.
По умолчанию ZIP-архиву присваивается то же имя, что и папке, которая была заархивирована. При этом с помощью штатных средств можно создать только ZIP, для других вариантов потребуется использовать сторонний софт.
Способ 2: WinRAR
Один из наиболее распространенных архиваторов для компьютеров – условно-бесплатная программа WinRAR. Она работает с несколькими типами форматов, позволяет создавать или распаковывать сжатые данные.
- Скачайте и установите WinRAR. Найдите программу в списке установленного софта и запустите ее. Ее иконка может располагаться также на рабочем столе.
- Через встроенный проводник отыщите папку, которую следует заархивировать. Ориентироваться между каталогами можно через верхнюю строку и кнопки навигации. Выделите каталог одним нажатием левой кнопкой мыши, затем кликните по кнопке «Добавить», которая находится на верхней рабочей панели.
- В новом окне останется задать архиву имя, выбрать формат и степень сжатия. Если содержимое много весит, то его можно разбить на несколько архивов, но при этом они будут взаимосвязаны между собой: при распаковке первого извлекутся и остальные. Если надо, установите пароль, а для запуска компрессии нажмите на «ОК».
Также доступно создание архива из папки через ее контекстное меню. Щелкните правой кнопкой мыши по файлу/папке и выберите один из пунктов, связанных с программой WinRAR. Затем потребуется в дополнительном окне настроить будущий архив.
Читайте также: Как пользоваться WinRAR
Способ 3: 7-Zip
Бесплатная программа 7-Zip позволяет работать с различными типами сжатых данных: извлекать содержимое или создавать новые архивы. При этом, вопреки названию, поддерживается не только формат ZIP, но и различные другие, включая популярнейший RAR.
- Установите и откройте приложение 7-Zip File Manager. Через встроенный файловый менеджер найдите папку, которую нужно архивировать. Выделите и нажмите на кнопку «Добавить», расположенную вверху.
- Появится новое окно с настройками будущего архива. Задайте для него имя и выберите формат. Всего доступно несколько вариантов, включая ZIP и 7z. Также можно определить уровень и метод компрессии, зашифровать данные, разбить содержимое на тома и использовать другие параметры. Когда все будет готово, нажмите на «ОК».
По умолчанию, если путь сохранения не изменен, архив сохранится в том же месте, где и сама папка-оригинал.
После установки программы ее функции автоматически добавятся и в контекстное меню. Алгоритм действий при этом похож на описанный в предыдущем способе: щелкните по папке правой кнопкой мыши, наведите курсор на пункт «7-Zip» и из списка выберите интересующий вариант.
Способ 4: WinZip
Еще один функциональный архиватор для Windows – это WinZip, который позволяет тонко настраивать создание архива, включая уровень сжатия и другие параметры. Приложение работает практически со всеми распространенными форматами сжатых данных. Оно платное, но предоставляется пробный период, в течение которого можно ознакомиться со всеми его преимуществами и возможностями.
- Установите программу. После первого запуска можно изучить информацию о приложении и его использовании. В главном окне интерфейса на панели слева через встроенный каталог найдите папку, которая будет архивироваться.
- Поставьте отметку в чекбоксе справа от названия нужной папки. Ниже найдите и нажмите на «Добавить в архив».
- В центральной части отобразится, что папка добавлена в архив. Чтобы его сохранить, кликните по соответствующей кнопке справа.
- В системном окне укажите, куда ZIP-архив будет помещен, при необходимости впишите имя и выберите тип. Щелкните по «Сохранить».
Так же, как и в предыдущих вариантах, функции архиватора добавляются в контекстное меню системы. В нем наведите курсор на пункт «WinZip», затем выберите подходящий вариант.
Читайте также: Программы для сжатия файлов
Вариант 2: На смартфоне
Для смартфонов тоже разработаны приложения, работающие с архивами, но устанавливать их надо отдельно, поскольку мобильные системы не предусматривают встроенных средств.
Читайте также: Как открыть на Айфоне файл ZIP / RAR
Способ 1: WinRAR
Архивировать папку с файлами на телефоне можно с помощью приложения WinRAR, доступного для бесплатного скачивания и использования. Делается это двумя способами: через интерфейс архиватора или любой файловый менеджер.
-
Запустите архиватор и с помощью файлового менеджера отыщите папку, которую хотите сжать. Отметьте ее, кликнув по чекбоксу справа. На верхней рабочей панели выберите иконку в виде архива с плюсиком. В новом окне потребуется переименовать будущий архив, если это нужно, а также выбрать формат, применить дополнительные опции, задать пароль. Тонкая настройка осуществляется при помощи вкладок в верхней части окна. Нажмите на кнопку «ОК», чтобы начать процедуру архивации папки.
Настроенные параметры можно сохранить в профиль (то есть как шаблон), чтобы в будущем выбрать его и не тратить время на те же самые действия.
Способ 2: ZArchiver
Приложение ZArchiver – еще один архиватор, работающий с самыми популярными форматами сжатых файлов. Здесь также предусмотрен файловый менеджер, через который просто отыскать папки и любые данные.
- Найдите через интерфейс запущенного ZArchiver папку (по умолчанию открывается внутреннее хранилище). В меню вверху можно выбрать часто используемые каталоги. Выделите нужную папку продолжительным тапом.
- Появится всплывающее меню, в котором коснитесь пункта «Сжать…». В новом окне задайте имя архиву, выберите формат и уровень сжатия. Если необходимо, здесь также можно поставить пароль или разделить большой архив на тома. По завершении настройки нажмите «ОК».
В отличие от многих аналогичных продуктов, ZArchiver позволяет создать архив в любом из самых распространенных форматов, включая RAR, TAR, ZIP.
Как и в предыдущем варианте, добавить папку в архив можно через файловый менеджер и функцию «Поделиться» или «Отправить», в зависимости от интерфейса проводника.
Способ 3: WinZip
Простой архиватор, который позволяет быстро сжимать файлы в формат ZIP – это приложение WinZip. Оно предусматривает платные функции, но для создания архива из папки достаточно базовых возможностей.
- Установите и запустите приложение на телефоне. В главном окне доступен переход во внутреннее или съемное хранилище, а также сортировка по типам файлов. Коснитесь «Internal storage», если каталог находится в памяти мобильного устройства.
- Нажмите на три точки и во всплывающем меню выберите «Zip to…».
- После этого потребуется указать место, куда будет сохранен архив, причем сделать это можно и на облачное хранилище. После выбора нажмите на кнопку «ZIP HERE».
На этом создание ZIP-архива завершено. Такой формат можно открыть практически через любое приложение, работающее со сжатыми папками.