Войти
| Разработчик (и) | |
|---|---|
| Стабильный выпуск | 7.15 / 17 августа 2016 г.; 4 года назад (17.08.2016) |
| Репозиторий |  |
| Написано на | C ++ |
| Операционная система | Microsoft Windows, Linux |
| Платформа | IA-32, x86-64 |
| Тип | Файловый архиватор |
| Лицензия | MIT, Общественное достояние |
| Веб-сайт | mattmahoney.net / dc / zpaq.html |
ZPAQ - это открытый исходный код командная строка архиватор для Windows и Linux. Он использует формат ведения журнала или только для добавления, который можно откатить до более раннего состояния для получения более старых версий файлов и каталогов. Он поддерживает быстрое инкрементное обновление, добавляя только файлы, дата последнего изменения которых изменилась с момента предыдущего обновления. Он сжимает с использованием дедупликации и нескольких алгоритмов (LZ77, BWT и смешение контекста ) в зависимости от типа данных и выбранного уровня сжатия.. Чтобы сохранить прямую и обратную совместимость между версиями по мере улучшения алгоритма сжатия, он сохраняет алгоритм распаковки в архиве. Исходный код ZPAQ включает общедоступный API, libzpaq, который предоставляет услуги сжатия и распаковки для приложений C ++. Считается, что формат не обременен патентами.
Файлы сохраняются в формате журналирования уровня 2 ZPAQ. Стандарт определяет два формата - потоковую передачу и ведение журнала. Только формат ведения журнала поддерживает дедупликацию, атрибуты каталогов и несколько датированных версий файлов.
Формат потокового архива предназначен для извлечения за один проход. Архив делится на последовательность блоков, которые могут быть распакованы независимо параллельно. Блоки делятся на сегменты, которые необходимо распаковать последовательно по порядку. Заголовок каждого блока содержит описание алгоритма распаковки. Каждый сегмент имеет заголовок, содержащий необязательное имя файла и необязательный комментарий для метаданных, таких как размер, дата и атрибуты, а также необязательную завершающую контрольную сумму SHA-1 исходных данных для проверки целостности. Если имя файла опущено, предполагается, что он является продолжением последнего указанного файла, который может находиться в предыдущем блоке. Таким образом, вставка, удаление или переупорядочивание блоков в потоковом архиве приводит к выполнению тех же операций с данными, которые представляют блоки.
Формат ведения журнала состоит из последовательности транзакций или обновлений. Обновление содержит 4 типа блоков: блок заголовка транзакции, последовательность блоков данных, соответствующую последовательность таблиц фрагментов и последовательность блоков индекса. Блок заголовка транзакции содержит дату транзакции и указатель, пропускающий блоки данных, чтобы можно было быстро прочитать индекс архива. Блоки данных содержат последовательность сжатых вместе фрагментов файлов. В таблицах фрагментов указан размер и хэш SHA-1 каждого фрагмента. Блоки индекса содержат список изменений индекса глобального архива. Редактирование - это либо обновление файла, либо удаление файла. Обновление включает имя файла, дату последнего изменения, атрибуты и список указателей фрагментов в текущей и предыдущей транзакциях. Фрагменты могут использоваться более чем одним файлом. Удаление не удаляет какие-либо данные из архива, а скорее указывает на то, что файл не должен быть извлечен, если архив не откат к более ранней дате.
Стандарт ZPAQ не определяет алгоритм сжатия. Скорее, он определяет формат для представления алгоритма распаковки в заголовках блоков. Алгоритмы декомпрессии написаны на языке ZPAQL и хранятся в виде байтового кода, который можно интерпретировать или преобразовать напрямую в 32- или 64-разрядный код x86 и выполнить. Программа ZPAQL состоит из 3 частей.
Модели COMP основаны на PAQ, который сжимает один бит за раз с использованием арифметического кодирования. Всего существует 9 типов компонентов. Каждый компонент принимает контекст и, возможно, предсказания более ранних компонентов, и выводит предсказание или вероятность того, что следующим битом будет 1. Выход последнего компонента арифметически закодирован. Типы компонентов:
Раздел HCOMP вычисляет контексты для компонентов в разделе COMP. Это виртуальная машина, состояние которой состоит из 4 32-битных регистров (A, B, C, D), 16-битного счетчика программ, бит флага условия и двух массивов памяти, один из байтов (M) и один из 32 битов. слова (H). Начало H образует массив контекстов. Программа, подобная на языке ассемблера, вызывается один раз для каждого закодированного или декодированного байта с этим байтом в качестве входных в A. Последний контекст, видимый секцией COMP, - это вычисленный контекст, объединенный с ранее увиденными битами текущего байт.
Дополнительная секция PCOMP используется для пост-обработки декодированных данных. Он работает на отдельной виртуальной машине, такой как HCOMP. Однако, в отличие от разделов COMP и HCOMP, которые используются как для сжатия, так и для распаковки, раздел PCOMP запускается только во время распаковки. Компрессор отвечает за выполнение обратной операции над входными данными перед кодированием.
В исходном коде ZPAQL используется текстовый синтаксис, в котором каждое слово, разделенное пробелами, в большинстве случаев объединяется в один байт, а комментарии в скобках. Следующий пример представляет собой среднюю конфигурацию, аналогичную сжатию уровня 5. Он описывает цепочку компонентов ICM-ISSE, принимающих хешированные контексты порядков от 0 до 5, MATCH, принимающий контекст порядка 7, и в качестве заключительного шага усреднение этих битовых предсказаний с использованием MIX. Постобработки нет.
comp 3 3 0 0 8 (hh hm ph pm n) 0 icm 5 (последовательность порядка 0... 5) 1 isse 13 0 2 isse 17 1 3 isse 18 2 4 isse 18 3 5 isse 19 4 6 соответствие 22 24 (порядок 7) 7 mix 16 0 7 24 255 (порядок 1) hcomp c ++ * c = ab = ca = 0 (сохранить во вращающемся буфере M) d = 1 hash * d = a (порядки 1... 5 для 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 (порядок совпадения 7) d ++ a = * ca <<= 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 указывает на массив из 8 слов H. M используется для хранения последних 8 байтов ввода из Регистр А. C указывает на заголовок этого буфера. Инструкция HASH вычисляет:
a = (a + * b + 512) * 773;
Таким образом, код хранит хеши контекста различного порядка в H [0]... H [7].
При обновлении ZPAQ делит входные файлы на фрагменты, вычисляет их хэши SHA-1 и сравнивает их с хешами, хранящимися в архиве. Если есть совпадение, то предполагается, что фрагменты идентичны, и сохраняется только указатель на ранее сжатый фрагмент. В противном случае фрагмент упаковывается в блок для сжатия. Размер блока может составлять от 16 до 64 МБ в зависимости от уровня сжатия.
Файлы разделены на фрагменты по границам, зависящим от содержимого. Вместо отпечатка Рабина, ZPAQ использует скользящий хэш, который зависит от последних 32 байтов, которые не предсказываются контекстом порядка 1, плюс любые предсказанные байты между ними. Если все ведущие 16 бит 32-битного хэша равны 0, то отмечается граница фрагмента. Это дает средний размер фрагмента 64 КБ.
Скользящий хэш использует 256-байтовую таблицу, содержащую байт, который последний раз встречался в каждом возможном контексте порядка 1. Хэш обновляется путем добавления следующего байта и последующего умножения либо на нечетную константу, если байт был предсказан, либо на четное число, не кратное 4, если байт не был предсказан.
ZPAQ имеет 5 уровней сжатия, от самого быстрого до наилучшего. На любом уровне, кроме наилучшего, он использует статистику таблицы прогнозирования порядка 1, используемой для дедупликации, чтобы проверить, является ли ввод случайным. Если это так, он сохраняется без сжатия для оптимизации скорости. В противном случае он выбирает алгоритм сжатия следующим образом:
Кроме того, ZPAQ будет использовать преобразование E8E9 для улучшения сжатия кода x86, который обычно встречается в файлах.exe и.dll. Преобразование E8E9 сканирует инструкции CALL и JMP (коды операций E8 и E9 в шестнадцатеричном формате) и заменяет их относительные адреса абсолютными. Затем он вставляет код в раздел PCOMP для выполнения обратного преобразования.
В ZPAQ отсутствует коррекция ошибок, но есть несколько функций, которые ограничивают повреждение при повреждении архива. При распаковке проверяются все хэши SHA-1. Если хэш не совпадает или возникает другая ошибка, выводится предупреждение и блок игнорируется. Блоки начинаются с 13-байтового «тега локатора», содержащего случайно выбранную, но фиксированную строку, позволяющую обнаружить начало следующего блока путем сканирования. Если фрагмент данных потерян, то все файлы, ссылающиеся на этот фрагмент и оставшиеся фрагменты в блоке, также теряются. Если таблица фрагментов потеряна, ее можно восстановить из избыточного списка размеров фрагментов, хранящегося в соответствующем блоке данных, и путем пересчета хэшей. В этом случае проверяется второй хеш всего блока данных. Если индексный блок потерян, соответствующие файлы теряются. Индексные блоки небольшие (16 КиБ), чтобы ограничить урон.
Обновления выполняются путем добавления временного заголовка транзакции и последующего обновления заголовка на последнем этапе. Если обновление прерывается, временный заголовок сигнализирует ZPAQ о том, что после него не найдено никаких полезных данных. Следующее обновление перезапишет эти лишние данные.
