ЗПАК

ЗПАК

Разработчик(и)	Мэтт Махони
Стабильная версия	7.15   / 22 сентября 2016 г.
Репозиторий	github .с для /z для /z
Написано в	С++
Операционная система	Microsoft Windows , Линукс
Платформа	ИА-32 , x86-64
Тип	Архив файлов
Лицензия	Массачусетский технологический институт , Общественное достояние
Веб-сайт	Мэттмахони .сеть /постоянный ток для /z .html

ZPAQ — это с открытым исходным кодом командной строки архиватор для Windows и Linux . Он использует формат ведения журнала или формат только для добавления, который можно откатить до более раннего состояния для получения более старых версий файлов и каталогов. Он поддерживает быстрое инкрементное обновление, добавляя только те файлы, дата последнего изменения которых изменилась со времени предыдущего обновления. Сжимает с помощью дедупликации и нескольких алгоритмов ( LZ77 , BWT и смешивания контекста ) в зависимости от типа данных и выбранного уровня сжатия. Чтобы сохранить прямую и обратную совместимость между версиями по мере улучшения алгоритма сжатия, алгоритм распаковки сохраняется в архиве. Исходный код ZPAQ включает общедоступный API libzpaq , который предоставляет услуги сжатия и распаковки для C++ приложений . Считается, что этот формат не обременен патентами .

Формат архива

Файлы сохраняются в формате журнала ZPAQ уровня 2. Стандарт определяет два формата — потоковую передачу и журналирование. Только формат журнала поддерживает дедупликацию, атрибуты каталога и несколько датированных версий файлов.

Формат потокового архива предназначен для извлечения за один проход. Архив разделен на последовательность блоков, которые можно независимо и параллельно распаковывать. Блоки делятся на сегменты, которые необходимо последовательно распаковывать по порядку. Каждый заголовок блока содержит описание алгоритма распаковки. Каждый сегмент имеет заголовок, содержащий необязательное имя файла и необязательный комментарий к метаданным, таким как размер, дата и атрибуты, а также необязательную конечную контрольную сумму SHA-1 исходных данных для проверки целостности. Если имя файла опущено, предполагается, что оно является продолжением файла с последним именем, который может находиться в предыдущем блоке. Таким образом, вставка, удаление или изменение порядка блоков в потоковом архиве приводит к выполнению тех же операций с данными, которые представляют блоки.

Формат журнала состоит из последовательности транзакций или обновлений. Обновление содержит 4 типа блоков: блок заголовка транзакции, последовательность блоков данных, соответствующую последовательность таблиц фрагментов и последовательность индексных блоков. Блок заголовка транзакции содержит дату транзакции и указатель, пропускающий блоки данных, что позволяет быстро прочитать индекс архива. Блоки данных содержат последовательность фрагментов файлов, сжатых вместе. В таблицах фрагментов указаны размер и хэш SHA-1 каждого фрагмента. Индексные блоки содержат список изменений глобального архивного индекса. Редактирование — это либо обновление файла, либо его удаление. Обновление включает имя файла, дату последнего изменения, атрибуты и список указателей фрагментов текущей и предыдущей транзакций. Фрагменты могут использоваться более чем одним файлом. Удаление не удаляет какие-либо данные из архива, а указывает на то, что файл не подлежит извлечению, пока архив не будет откачен до более ранней даты.

Стандарт ZPAQ не определяет алгоритм сжатия. Скорее, он определяет формат представления алгоритма распаковки в заголовках блоков. Алгоритмы декомпрессии написаны на языке ZPAQL и хранятся в виде байтового кода, который можно интерпретировать или преобразовать непосредственно в 32- или 64-битный код x86 и выполнить. Программа ZPAQL состоит из трех частей.

• COMP — дополнительная цепочка компонентов контекстного моделирования.
• HCOMP — Машинный код для вычисления контекстов для компонентов COMP.
• PCOMP — дополнительный машинный код для постобработки декодированных данных.

Модели COMP основаны на PAQ , который сжимает побитно с помощью арифметического кодирования . Существует 9 типов компонентов. Каждый компонент принимает контекст и, возможно, прогнозы предыдущих компонентов и выводит прогноз или вероятность того, что следующий бит будет равен 1. Выходные данные последнего компонента закодированы арифметически. Типы компонентов:

• CONST — фиксированный прогноз.
• CM – Контекстная модель. Контекст используется для поиска прогноза в таблице. При обновлении выбранная запись корректируется для уменьшения ошибки прогнозирования.
• ICM — Модель косвенного контекста. Контекст используется для поиска 8-битного состояния, представляющего недавнюю историю битов. История выбирает прогноз, как и в случае с CM.
• MIX — группа прогнозов объединяется путем взвешенного усреднения в логистической области или log(p/(1-p)). Веса выбираются контекстом. При обновлении веса корректируются в пользу более точных входных данных.
• MIX2 — MIX с двумя входами, веса которого ограничены суммированием до 1.
• AVG — MIX2 с фиксированным весом.
• SSE — средство оценки вторичного символа. Ищет прогноз из интерполированной таблицы с учетом контекста и квантованного прогноза из другого компонента.
• ISSE — косвенная оценка вторичного символа. Контекст выбирает битовую историю, как в случае с ICM, а затем битовая история выбирает пару весов для смешивания входных данных с константой 1.
• ПОИСКПОЗ — ищет предыдущее вхождение контекста и прогнозирует любой следующий бит, степень которого зависит от длины совпадения.

Раздел HCOMP вычисляет контексты для компонентов в разделе COMP. Это виртуальная машина, состояние которой представляет собой 4 32-битных регистра (A, B, C, D), 16-битный счетчик программ, бит флага состояния и два массива памяти, один из байтов (M) и один из 32-бит. слова (Н). Начало H образует массив контекстов. Программа , подобная ассемблеру, вызывается один раз для каждого закодированного или декодированного байта, используя этот байт в качестве входных данных в A. Конечный контекст, видимый в разделе COMP, представляет собой вычисленный контекст, объединенный с ранее просмотренными битами текущего байта.

Дополнительный раздел PCOMP используется для постобработки декодированных данных. Он работает на отдельной виртуальной машине, такой как HCOMP. Однако в отличие от разделов COMP и HCOMP, которые используются как для сжатия, так и для распаковки, раздел PCOMP запускается только во время распаковки. Компрессор отвечает за выполнение обратной операции над входными данными перед кодированием.

Пример ZPAQL

Исходный код ZPAQL использует текстовый синтаксис, при этом каждое слово, разделенное пробелами, в большинстве случаев собирается в один байт, а комментарии заключаются в круглые скобки. Следующий пример представляет собой среднюю конфигурацию, аналогичную сжатию уровня 5. Он описывает цепочку компонентов ICM-ISSE, принимающую хешированные контексты порядков от 0 до 5, MATCH, принимающую контекст порядка 7, и, в качестве последнего шага, усреднение этих битовых предсказаний с использованием MIX. Постобработка отсутствует.

comp 3 3 0 0 8 (hh hm ph pm n)
   0 icm 5      (order 0...5 chain)
   1 isse 13 0
   2 isse 17 1
   3 isse 18 2
   4 isse 18 3
   5 isse 19 4
   6 match 22 24  (order 7)
   7 mix 16 0 7 24 255  (order 1)
 hcomp
   c++ *c=a b=c a=0 (save in rotating buffer M)
   d= 1 hash *d=a   (orders 1...5 for isse)
   b-- d++ hash *d=a
   b-- d++ hash *d=a
   b-- d++ hash *d=a
   b-- d++ hash *d=a
   b-- d++ hash b-- hash *d=a (order 7 for match)
   d++ a=*c a<<= 8 *d=a       (order 1 for mix)
   halt
 end

Параметры COMP описывают размеры массивов слов и байтов по базе 2 журнала (hh, hm), по 8 байтов каждый в разделе HCOMP и не используемые в разделе PCOMP. Имеется n = 8 пронумерованных компонентов. Компоненты принимают параметры, описывающие размеры их таблиц и входные данные. В частности, каждый ISSE получает входные данные от предыдущего компонента, а MIX принимает входные данные от 7 компонентов, начиная с 0. Строка «5 isse 19 4» говорит, что ISSE имеет размер таблицы 2. ¹⁹⁺⁶ битовые истории и получает входные данные от компонента 4.

В разделе HCOMP регистры B и C указывают на 8-байтовый вращающийся массив M, а D указывает на массив H из 8 слов. M используется для хранения последних 8 байтов ввода из регистра A. C указывает на заголовок этого буфера. Инструкция HASH вычисляет:

 a = (a + *b + 512) * 773;

Таким образом, код хранит хеши контекстов разного порядка в H[0]...H[7].

Дедупликация

При обновлении ZPAQ делит входные файлы на фрагменты, вычисляет их хэши SHA-1 и сравнивает их с хэшами, хранящимися в архиве. Если совпадение имеется, то фрагменты считаются идентичными и сохраняется только указатель на ранее сжатый фрагмент. В противном случае фрагмент упаковывается в блок для сжатия. Размеры блоков могут составлять от 16 до 64 МБ в зависимости от уровня сжатия.

Файлы делятся на фрагменты по границам, зависящим от содержимого. Вместо отпечатка пальца Рабина ZPAQ использует скользящий хеш , который зависит от последних 32 байтов, которые не предсказаны контекстом первого порядка, плюс любые предсказанные байты между ними. Если все ведущие 16 бит 32-битного хеша равны 0, то граница фрагмента отмечена. Это дает средний размер фрагмента 64 КиБ.

В скользящем хэше используется таблица размером 256 байт, содержащая последний увиденный байт в каждом возможном контексте порядка 1. Хэш обновляется путем добавления следующего байта и последующего умножения либо на нечетную константу, если байт был предсказан, либо на четное число, не кратное 4, если байт не был предсказан.

Сжатие

ZPAQ имеет 5 уровней сжатия, от самого быстрого до лучшего. На всех уровнях, кроме лучшего, он использует статистику таблицы прогнозирования порядка 1, используемой для дедупликации, чтобы проверить, является ли ввод случайным. Если да, то он сохраняется без сжатия в целях оптимизации скорости.

ZPAQ будет использовать преобразование E8E9 (см.: BCJ ) для улучшения сжатия кода x86, обычно встречающегося в файлах .exe и .dll. Преобразование E8E9 сканирует инструкции CALL и JMP (шестнадцатеричные коды операций E8 и E9) и заменяет их относительные адреса абсолютными адресами. Затем он вставляет код в раздел PCOMP для выполнения обратного преобразования.

Восстановление ошибок

В ZPAQ отсутствует коррекция ошибок, но есть несколько функций, которые ограничивают ущерб в случае повреждения архива. При распаковке проверяются все хэши SHA-1. Если хэш не совпадает или возникает какая-либо другая ошибка, то выводится предупреждение и блок игнорируется. Блоки начинаются с 13-байтового «тега локатора», содержащего случайно выбранную, но фиксированную строку, позволяющую найти начало следующего блока путем сканирования. Если фрагмент данных потерян, то все файлы, ссылающиеся на этот фрагмент, и остальные фрагменты в блоке также теряются. Если таблица фрагментов утеряна, то ее можно восстановить из избыточного списка размеров фрагментов, хранящегося в соответствующем блоке данных, и путем пересчета хэшей. В этом случае проверяется второй хеш всего блока данных. Если индексный блок потерян, соответствующие файлы теряются. Индексные блоки небольшие (16 КиБ), чтобы ограничить ущерб.

Обновления выполняются путем добавления временного заголовка транзакции и последующего обновления заголовка на последнем этапе. Если обновление прерывается, то временный заголовок сигнализирует ZPAQ о том, что после него не найдено никаких полезных данных. Следующее обновление перезапишет эти лишние данные.

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

Создание архива и обновление архива

zpaq add directory/archive.zpaq directory/source_directory -mX -key password

Варианты -mX (где X — уровень сжатия от 0 до 5) и -key (который выполняет шифрование AES-256 ) можно опустить. Уровень сжатия 0 не сжимает данные, но по-прежнему выполняет дедупликацию данных. Уровни сжатия 4 и 5 могут занять очень много времени. По умолчанию (1) используется простое сжатие LZ77.

Листинг содержимого архива

zpaq list archive.zpaq перечисляет файлы и каталоги самой последней версии. Добавление -all выведет список всех версий всех файлов и каталогов в формате version_number/directory/file_name. Вывод может быть дополнительно обработан с помощью grep и других инструментов.

Извлечение файлов

zpaq extract archive.zpaq распакует последнюю версию всего архива в активный каталог. zpaq extract backup.zpaq path извлечет только указанный каталог (или файл). Добавление -until N Опция выбирает версию, в которой разрешены отрицательные числа. -2 извлечет третью самую последнюю версию архива. Необязательный -to сообщает ZPAQ, где сохранить извлеченные файлы.

zpaq extract backup.zpaq -all -only "*muppet*" извлечет все версии всех файлов и каталогов, имя которых содержит «muppet». Различные версии файлов будут размещены в разных каталогах ( 0001/ 0002/ 0003/ и так далее). -only является необязательным.

История

• 15 февраля 2009 г. — экспериментальный выпуск zpaq 0.01.
• 12 марта 2009 г. — завершена разработка спецификации zpaq 1.00, гарантирующей обратную совместимость.
• 29 сентября 2009 г. — zpaq 1.06, спецификация обновлена ​​до версии 1.01, добавлены теги локатора для поддержки самораспаковывающихся архивов.
• 14 октября 2009 г. — в zpaq 1.09 добавлен ZPAQL в транслятор C++ для оптимизации скорости.
• 27 сентября 2010 г. — отдельный API libzpaq 0.01.
• 21 января 2011 г. — pzpaq 0.01, первая многопоточная версия, позже снова включенная в zpaq.
• 13 ноября 2011 г. — в zpaq 4.00 добавлен JIT-компилятор (от ZPAQL до x86), устраняющий необходимость во внешнем компиляторе C++ для оптимизации.
• 1 февраля 2012 г. — zpaq 5.00, спецификация обновлена ​​до версии 2.00, чтобы разрешить пустой раздел COMP (только постобработка).
• 28 сентября 2012 г. — zpaq 6.00, спецификация обновлена ​​до версии 2.01, добавлен формат журналирования.
• 23 января 2013 г. — в zpaq 6.19 функции разработки вынесены в отдельную программу zpaqd.

Связанные проекты

• Squash — уровень абстракции сжатия, поддерживающий множество кодеков .
• PeaZip — архиватор, поддерживающий более 150 форматов, включая извлечение потокового формата ZPAQ.
• fastqz — компрессор FASTQ, созданный с использованием libzpaq.
• zpaqfranz — швейцарский армейский нож для серьезного менеджера по резервному копированию и аварийному восстановлению.
• wcx_zpaq — плагин упаковщика (wcx) для Total Commander.

Внешние ссылки

• Официальный сайт
• zpaq на GitHub
• Введение в zpaql с изображениями в оттенках серого