Network Working Group P. Deutsch
Request for Comments: 1950 Aladdin Enterprises
Category: Informational J-L. Gailly
Info-ZIP
May 1996
ZLIB Compressed Data Format Specification version 3.3
Спецификация формата сжатых данных ZLIB, версия 3.3
Статус документа
Документ является информационным, не содержит стандартов Internet и может распространяться без ограничений.
Примечание IESG
IESG не занимает какой-либо позиции в отношении заявлений о правах интеллектуальной собственности, содержащихся в документе.
Уведомления
Copyright (c) 1996 L. Peter Deutsch and Jean-Loup Gailly.
Разрешается копировать и распространять этот документ в любых целях и бесплатно, в том числе переводить на другие языки и включать в сборники, при условии сохранения уведомления об авторских правах и данного уведомления, а также чёткого указания на любые существенные изменения оригинала и удаление части содержимого.
Указатель на последнюю версию этого документа и связанных с ним документов в формате HTML можно получить по ссылке URL <ftp://ftp.uu.net/graphics/png/documents/zlib/zdoc-index.html>.
Аннотация
Эта спецификация задаёт формат сжатия данных без потерь. Данные можно создавать и потреблять даже как последовательность произвольной длины в форме входного потока, используя лишь априори ограниченное по размеру промежуточное хранилище. В настоящее время формат использует метод компрессии DEFLATE, но его легко расширить для других методов сжатия. Метод легко реализуется свободным от патентов способом. Спецификация также определяет контрольную сумму ADLER-32 (расширение и усовершенствование контрольной суммы Флетчера), используемую для обнаружения повреждений данных, и приводит алгоритм расчёта суммы.
1. Введение
1.1. Цель
Целью данной спецификации является определение формата сжатия данных без потерь, который:
-
не зависит от типа CPU, файловой системы, набора символов и пригоден для обмена данными;
-
может создаваться и потребляться для сколь угодно длинной последовательности входных данных, используя лишь априори ограниченный объём промежуточного хранилища и пригоден для обмена данными и структур, похожих на фильтры Unix;
-
может применять множество разных методов сжатия;
-
может быть легко реализован без использования патентов и поэтому может применяться свободно.
Заданный здесь формат не предусматривает произвольный доступ к сжатым данным.
1.2. Целевая аудитория
Эта спецификация предназначена для разработчиков программ сжатия данных в формат zlib и/или распаковки сжатых данных zlib.
Текст спецификации предполагает базовые знания в сфере программирования на уровне битов и других примитивов представления данных.
1.3. Область действия
Спецификация задаёт формат данных, который подходит для сжатия в памяти произвольной последовательности байтов.
1.4. Соответствие
Если ниже явно не указано иное, соответствующий спецификации декомпрессор должен быть способен принимать и распаковывать любые данные, соответствующие этой спецификации. Компрессор должен давать на выходе набор данных, соответствующий этой спецификации.
1.5. Используемые термины и соглашения
byte — байт
8 битов, сохраняемых или передаваемых как единое целое (то же, что и октет). В этой спецификации байт всегда состоит из 8 битов, даже на машинах, где один символ представляется иным число битов. Нумерация битов в байте описана ниже.
1.6. Отличия от предыдущих версий
Первым публичным выпуском этой спецификации была версия 3.1. В версии 3.2 изменена терминология и переписан для чёткости пример кода Adler-32. В версии 3.3 добавлена поддержка заранее установленного словаря и спецификация приведена к стилю RFC.
2. Подробная спецификация
2.1. Базовые соглашения
На рисунках ниже прямоугольники вида
+---+
| | <-- вертикальная черта может отсутствовать
+---+
представляют 1 байт, а прямоугольники вида
+==============+
| |
+==============+
— переменное число байтов.
Байты в компьютере не имеют номеров битов, поскольку рассматриваются как единое целое. Однако в байте, рассматриваемом как целое число от 0 до 255, имеется старший и младший бит. Поскольку обычно при записи чисел старшая часть указывается слева, байты здесь представляются таким же способом — старший бит слева. На последующих рисунках бит 0 в байте размещается справа и биты нумеруются как
+--------+
|76543210|
+--------+
В компьютере число может представляться несколькими байтами. Для всех многобайтовых чисел в документе старший байт указывается первым (с меньшим адресом в памяти). Например, десятичное число 520 представляется в виде
0 1
+--------+--------+
|00000010|00001000|
+--------+--------+
^ ^
| |
| + младший байт = 8
+ старший байт = 2 x 256
2.2. Формат данных
Поток zlib имеет структуру, показанную на рисунке.
0 1
+---+---+
|CMF|FLG| (продолжение-->)
+---+---+
(при установленном FLG.FDICT)
0 1 2 3
+---+---+---+---+
| DICTID | (продолжение-->)
+---+---+---+---+
+=====================+---+---+---+---+
|....сжатые данные....| ADLER32 |
+=====================+---+---+---+---+
Какие-либо данные после ADLER32 не являются частью потока zlib.
CMF (Compression Method and flags) — метод сжатия и флаги
Байт содержит 4-битовое поле метода сжатия и 4-битовое информационное поле, зависящее от метода сжатия
биты 0 - 3 CM метод сжатия
биты 4 - 7 CINFO информация о сжатии
CM (Compression method) — метод сжатия
Указывает метод используемый сжатия. CM = 8 указывает метод deflate с размером окна до 32K, применяемый в gzip и PNG (см. [1] и [2] в разделе 3). Значение CM = 15 зарезервировано и может использоваться в будущем для указания наличия дополнительного поля перед сжатыми данными.
CINFO (Compression info) — информация о сжатии
Для CM = 8, поле CINFO содержит двоичный логарифм размера окна LZ77 минус 8 (CINFO=7 указывает окно размером 32K). Значения CINFO больше 7 не допускаются этой версией спецификации. Для CM отличных от 8 эта спецификация не задаёт значений CINFO.
FLG (FlaGs) — флаги
Байт флагов поделён на три части:
биты 0 - 4 FCHECK (проверочные биты для CMF и FLG)
бит 5 FDICT (установленный заранее словарь)
биты 6 - 7 FLEVEL (степень сжатия)
Значение FCHECK должно быть таким, чтобы значение полей CMF и FLG, представленное как 16-битовое целое число без знака в порядке MSB (CMF*256 + FLG), было кратно 31.
FDICT (Preset dictionary) — заранее установленный словарь
При установленном флаге FDICT сразу после байта FLG следует идентификатор словаря DICT, являющегося последовательностью байтов, подаваемой на вход компрессора без выдачи каких-либо данных на выходе. DICT — это контрольная сумма Adler-32 для такой последовательности байтов (см. определение ADLER32 ниже). Декомпрессор может использовать этот идентификатор для определения использованного при сжатии словаря.
FLEVEL (Compression level) — степень сжатия
Флаги, доступные при использовании некоторых методов сжатия. Для метода deflate (CM = 8) значения флагов указаны ниже.
0 - самый быстрый алгоритм
1 - быстрый алгоритм
2 - принятый по умолчанию алгоритм
3 - максимальное сжатие (самый медленный алгоритм)
Флаги FLEVEL не требуются для распаковки, они лишь указывают, возможно ли последующее сжатие.
compressed data — сжатые данные
Для метода 8 сжатые данные сохраняются в формате deflate, описанном L. Peter Deutsch в документе «DEFLATE Compressed Data Format Specification» (см. ссылку [3] в разделе 3)
Данная версия спецификации zlib не задаёт других форматов сжатых данных.
ADLER32 (Adler-32 checksum) — контрольная сумма Adler-32
Контрольная сумма несжатых данных (без учёта словаря), рассчитанная по алгоритму Adler-32, который является 32-битовым расширением и усовершенствованием алгоритма Флетчера, применяемого в стандартах ITU-T X.224 / ISO 8073 (см. ссылки [4] и [5] в разделе 3).
Значение Adler-32 состоит из двух сумм, накапливаемых по байтам: s1 содержит сумму всех байтов, а s2 — сумму всех значений s1. Суммирование выполняется по модулю 65521, s1 инициализируется значением 1, s2 — 0. Контрольная сумма Adler-32 сохраняется как s2*65536 + s1 в сетевом порядке байтов (сначала старший).
2.3. Соответствие
Соответствующий спецификации компрессор должен создавать потоки с корректными полями CMF, FLG и ADLER32, но поддержка установленного заранее словаря не требуется. При использовании zlib как части другого стандартного формата данных компрессор может использовать только словари, заданные этим форматом. Если такой формат не предусматривает заранее установленных словарей, компрессору недопустимо устанавливать флаг FDICT.
Соответствующий спецификации декомпрессор должен проверять поля CMF, FLG, ADLER32 и указывать ошибку при обнаружении некорректного значения. Декомпрессор должен указывать ошибку, если значение CM не соответствует данной спецификации (сейчас определено только значение 8), поскольку иное значение может указывать наличие новых функций, из-за которых последующие данные могут интерпретироваться некорректно. Декомпрессор должен указывать ошибку, если в FDICT указано значение DICTID, не соответствующее известному словарю. Декомпрессор может игнорировать FLEVEL, не теряя соответствия спецификации. При использовании zlib как части другого стандартного формата декомпрессор должен поддерживать все заранее установленные словари этого формата. Если формат не поддерживает заранее установленный словарь, декомпрессор должен отвергать любые потоки с установленным флагом FDICT.
3. Литература
[1] Deutsch, L.P.,»GZIP Compressed Data Format Specification», available in ftp://ftp.uu.net/pub/archiving/zip/doc/1
[2] Thomas Boutell, «PNG (Portable Network Graphics) specification», available in ftp://ftp.uu.net/graphics/png/documents/2
[3] Deutsch, L.P.,»DEFLATE Compressed Data Format Specification», available in ftp://ftp.uu.net/pub/archiving/zip/doc/3
[4] Fletcher, J. G., «An Arithmetic Checksum for Serial Transmissions,» IEEE Transactions on Communications, Vol. COM-30, No. 1, January 1982, pp. 247-252.
[5] ITU-T Recommendation X.224, Annex D, «Checksum Algorithms,» November, 1993, pp. 144, 145. (Available from gopher://info.itu.ch4). ITU-T X.244 is also the same as ISO 8073.
4. Исходный код
Исходный код реализации совместимой с zlib библиотеки на языке C доступен по ссылке ftp://ftp.uu.net/pub/archiving/zip/zlib/.
5. Вопросы безопасности
Декодер, не проверяющий контрольную сумму ADLER32, может не заметить повреждения данных.
6. Благодарности
Упомянутые в документе торговые знаки принадлежат соответствующим владельцам.
Жан-Лу Гайи (Jean-Loup Gailly) и Марк Адлер (Mark Adler) разработали формат zlib и написали программы, указанные в этой спецификации. Глен Рандерс-Персон (Glenn Randers-Pehrson) преобразовал документ в формат RFC и HTML.
7. Адреса авторов
L. Peter Deutsch
Aladdin Enterprises
203 Santa Margarita Ave.
Menlo Park, CA 94025
Phone: (415) 322-0103 (AM only)
FAX: (415) 322-1734
EMail: <ghost@aladdin.com>
Jean-Loup Gailly
EMail: <gzip@prep.ai.mit.edu>
Технические вопросы по данной спецификации можно направлять по электронной почте Jean-Loup Gailly <gzip@prep.ai.mit.edu> и Mark Adler <madler@alumni.caltech.edu>, редакционные замечания — L. Peter Deutsch <ghost@aladdin.com> и Glenn Randers-Pehrson <randeg@alumni.rpi.edu>
8. Приложение. Обоснование
8.1. Заранее установленные словари
Заранее установленный словарь особенно полезен при сжатии коротких последовательностей данных Компрессор может использовать контекст словаря для более компактного кодирования входных данных. Декомпрессор можно инициализировать с соответствующим контекстом, виртуально распаковав сжатую версию словаря без передачи результата на выход. Однако некоторые алгоритмы сжатия, такие как deflate, позволяют выполнить инициализацию без декомпрессии.
Компрессор и декомпрессор должны использовать один словарь, который может быть постоянным или выбираться из нескольких в соответствии с типом входных данных. Декомпрессор может определить выбранный компрессором словарь по его идентификатору. Этот документ не задаёт содержимого заранее устанавливаемых словарей, поскольку оптимальный словарь зависит от приложения. Стандартные форматы данных, использующие это свойство спецификации zlib, должны чётко определять допустимые словари.
8.2. Алгоритм Adler-32
Алгоритм Adler-32 намного быстрее, чем CRC32, и обеспечивает очень низкую вероятность пропуска ошибок.
Деление по модулю для накопителей unsigned long можно отложить на 5552 байта, поэтому время операции деления по модулю пренебрежимо мало. Если входные байты имеют значения a, b, c, второй суммой (s2) будет значение 3a + 2b + c + 3, чувствительное к позиции и порядку, тогда как первая сумма (s1) является просто контрольной суммой. Важно, что число 65521 является простым, чтобы избежать возможно большого класса двухбайтовых ошибок, которые не меняют результат проверки (в контрольной сумме Флетчера применяется значение 255, не являющееся простым, что делает такую проверку нечувствительной к смене в одном байте 0 на 255 или наоборот).
Сумма s1 инициализируется значением 1 вместо 0, чтобы длина последовательности была частью s2 и для длины не требовалась отдельная проверка (любая последовательность нулей даёт нулевую контрольную сумму Флетчера).
9. Приложение. Пример кода
Ниже приведён код C расчёта контрольных сумм Adler-32 для буфера данных, созданный для демонстрации без оптимизации скорости работы. В примере используется язык программирования ANSI C. Незнакомым с C читателям могут быть полезны приведённые ниже подсказки.
& побитовый оператор AND (И).
>> оператор побитового сдвига вправо; при использовании для
чисел без знака освободившиеся позиции слева заполняются 0.
<< оператор побитового сдвига влево; при использовании для
чисел без знака освободившиеся позиции спрва заполняются 0.
++ n++ инкрементирует переменную n.
% деление по модулю; a % b - это остаток от деления a на b.
#define BASE 65521 /* наибольшее простое число меньше 65536 */
/*
Обновление текущей контрольной суммы Adler-32 байтами buf[0..len-1]
и возврат обновлённого значения. Сумма Adler-32 инициализируется
значением 1.
Пример использования:
unsigned long adler = 1L;
while (read_buffer(buffer, length) != EOF) {
adler = update_adler32(adler, buffer, length);
}
if (adler != original_adler) error();
*/
unsigned long update_adler32(unsigned long adler,
unsigned char *buf, int len)
{
unsigned long s1 = adler & 0xffff;
unsigned long s2 = (adler >> 16) & 0xffff;
int n;
for (n = 0; n < len; n++) {
s1 = (s1 + buf[n]) % BASE;
s2 = (s2 + s1) % BASE;
}
return (s2 << 16) + s1;
}
/* Возврат значения adler32 для байтов buf[0..len-1] */
unsigned long adler32(unsigned char *buf, int len)
{
return update_adler32(1L, buf, len);
}
Перевод на русский язык
Николай Малых