RFC 1950

RFC 1950 — это документ из серии Request for Comments (RFC) Интернет-инженерного совета (IETF), описывающий спецификацию формата данных и алгоритмов сжатия, известную как zlib. Опубликованный в мае 1996 года, RFC 1950 определяет структуру потока данных, который может быть сжат с использованием алгоритмов, описанных в смежных документах: RFC 1951 (Deflate) и RFC 1952 (gzip). Zlib является широко распространённым стандартом сжатия данных без потерь, используемым в сетевых протоколах, файловых форматах и программном обеспечении.

История

Разработка zlib была инициирована в середине 1990-х годов в ответ на потребность в свободном, эффективном и переносимом алгоритме сжатия данных для интернет-приложений. До этого доминирующим форматом сжатия был LZW (используемый в GIF и Unix-утилите compress), однако он был обременён патентными ограничениями (патент на LZW принадлежал компании Unisys). Это создавало юридические риски для разработчиков свободного программного обеспечения, включая создателей операционной системы GNU.

Авторами RFC 1950 и связанных с ним спецификаций стали Питер Дойч (Peter Deutsch, из компании Aladdin Enterprises) и Жан-Лу Гайи (Jean-Loup Gailly). Гайи был одним из авторов утилиты gzip (GNU zip), которая стала свободной альтернативой compress. Дойч и Гайи поставили цель создать универсальный, свободный от патентных ограничений и хорошо документированный формат сжатия. Результатом стала триада RFC: 1950 (zlib), 1951 (Deflate) и 1952 (gzip).

RFC 1950 был принят в качестве стандарта IETF и получил статус «Draft Standard». Он стал основой для реализации библиотеки zlib, написанной на языке C, которая была выпущена под лицензией, позволяющей свободное использование как в свободном, так и в проприетарном программном обеспечении.

Структура формата zlib

Формат zlib, описываемый в RFC 1950, представляет собой контейнер для сжатых данных. Он состоит из двух основных частей: заголовка (header) и блока сжатых данных, за которыми может следовать контрольная сумма (checksum).

Заголовок (2 байта)

Заголовок zlib имеет фиксированную длину в 2 байта и содержит информацию о методе сжатия, уровне сжатия и проверочную информацию.

• CMF (Compression Method and Flags) — первый байт:
• CM (Compression Method, биты 0-3): Определяет метод сжатия. Единственным определённым методом является CM = 8, что соответствует алгоритму Deflate, описанному в RFC 1951.
• CINFO (Compression Info, биты 4-7): Указывает размер окна (window size) для алгоритма LZ77, используемого в Deflate. Значение CINFO = 7 соответствует размеру окна 32 КБ (2^(7+8) = 32768 байт). Это наиболее распространённое значение.

• FLG (Flags) — второй байт:
• FCHECK (биты 0-4): Контрольная сумма заголовка. Она вычисляется таким образом, чтобы общее 16-битное значение заголовка (CMF и FLG) было кратно 31. Это позволяет быстро обнаруживать ошибки в заголовке.
• FDICT (бит 5): Флаг словаря. Если установлен в 1, то после заголовка следует 4-байтовый идентификатор словаря (DICTID). Использование предопределённого словаря позволяет повысить степень сжатия для данных определённого типа. В большинстве реализаций FDICT = 0.
• FLEVEL (биты 6-7): Указывает уровень сжатия, использованный при кодировании. Возможные значения: 0 (быстрое/минимальное сжатие), 1 (среднее), 2 (максимальное), 3 (зарезервировано, обычно не используется).

Сжатые данные

Сразу после заголовка (и, опционально, идентификатора словаря) следуют сжатые данные, закодированные в соответствии с алгоритмом Deflate (RFC 1951). Данные могут быть представлены в виде одного или нескольких блоков Deflate, которые могут быть сжаты или храниться в несжатом виде.

Контрольная сумма (Adler-32)

После сжатых данных следует 4-байтовая контрольная сумма, вычисленная по алгоритму Adler-32. Adler-32 — это более быстрая, но несколько менее надёжная альтернатива CRC-32. Она вычисляется на основе исходных (несжатых) данных. Наличие контрольной суммы позволяет получателю проверить целостность распакованных данных.

Алгоритм сжатия Deflate (RFC 1951)

Хотя RFC 1950 описывает контейнер, основным алгоритмом сжатия, используемым в zlib, является Deflate, описанный в RFC 1951. Deflate представляет собой комбинацию двух методов:

• LZ77 (Lempel-Ziv 1977): Алгоритм, который заменяет повторяющиеся последовательности байтов ссылками на предыдущие вхождения. Он использует скользящее окно (обычно 32 КБ) для поиска совпадений.
• Кодирование Хаффмана: После этапа LZ77 полученные литералы (неповторяющиеся байты) и ссылки (длина и расстояние) кодируются с использованием алгоритма Хаффмана, который присваивает более короткие коды более часто встречающимся символам.

Deflate обеспечивает хорошее сжатие без потерь и является основой для многих форматов, включая gzip, PNG и ZIP.

Применение

Формат zlib и его реализация в виде библиотеки нашли широчайшее применение в самых разных областях вычислительной техники.

• Сетевые протоколы: Многие протоколы прикладного уровня используют сжатие zlib для уменьшения объёма передаваемых данных. Например, протокол HTTP (через заголовок Content-Encoding: deflate или Content-Encoding: gzip), протокол SSH, протокол TLS (для сжатия записей), а также протоколы электронной почты (POP3, IMAP).
• Файловые форматы:
• PNG (Portable Network Graphics): Формат растровой графики использует сжатие Deflate в качестве основного метода сжатия данных изображения. Заголовок и структура данных PNG не являются чистым zlib, но используют его алгоритм.
• ZIP: Архивный формат ZIP использует Deflate как один из основных методов сжатия. Внутренняя структура ZIP-файла отличается от zlib, но алгоритм сжатия данных идентичен.
• PDF (Portable Document Format): Формат PDF использует сжатие zlib для сжатия текстовых и графических объектов.
• Библиотеки и программное обеспечение:
• zlib: Эталонная библиотека на языке C, реализующая RFC 1950 и RFC 1951. Она включена в состав большинства операционных систем (Linux, macOS, Windows) и используется тысячами приложений.
• zlib-ng: Современная, оптимизированная версия библиотеки zlib, совместимая с оригинальным API.
• Python: Модуль zlib в стандартной библиотеке Python предоставляет функции для сжатия и распаковки данных в формате zlib.
• Java: Классы java.util.zip.Deflater и java.util.zip.Inflater реализуют сжатие и распаковку в формате zlib.

Критика и альтернативы

Несмотря на широкое распространение, формат zlib и алгоритм Deflate имеют некоторые недостатки.

• Скорость: Алгоритм Deflate, особенно на высоких уровнях сжатия, может быть относительно медленным по сравнению с более современными алгоритмами, такими как LZ4 (ориентирован на скорость) или Brotli (ориентирован на степень сжатия).
• Степень сжатия: Современные алгоритмы, такие как Zstandard (zstd) и LZMA, могут достигать значительно более высокой степени сжатия, чем Deflate, хотя и за счёт большего потребления памяти и процессорного времени.
• Безопасность: В некоторых реализациях zlib были обнаружены уязвимости, связанные с переполнением буфера и целочисленными переполнениями. Однако эти проблемы были исправлены в последующих версиях библиотеки.

В ответ на эти ограничения были разработаны альтернативные форматы и алгоритмы, такие как Brotli (используется в HTTP/2 и HTTP/3), Zstandard (от Facebook/Meta — организация признана экстремистской и запрещена в РФ) и LZMA (используется в архиваторах 7-Zip). Тем не менее, zlib остаётся одним из самых распространённых и универсальных стандартов сжатия данных, особенно в областях, где требуется совместимость с большим количеством устаревшего и современного программного обеспечения.

Интересные факты

• Название «zlib» не является акронимом. Оно было выбрано авторами как короткое и запоминающееся имя для библиотеки.
• Контрольная сумма Adler-32, используемая в zlib, была разработана Марком Адлером (Mark Adler), одним из соавторов библиотеки zlib.
• Формат gzip (RFC 1952) использует тот же алгоритм сжатия Deflate, что и zlib, но имеет другой формат заголовка и использует контрольную сумму CRC-32 вместо Adler-32.

Источники

• RFC 1950: ZLIB Compressed Data Format Specification version 3.3 (P. Deutsch, J-L. Gailly, May 1996)
• RFC 1951: DEFLATE Compressed Data Format Specification version 1.3 (P. Deutsch, May 1996)
• RFC 1952: GZIP file format specification version 4.3 (P. Deutsch, May 1996)
• Deutsch, P. (1996). "ZLIB Compressed Data Format Specification". IETF.