PiZ - Pi archiver (piz/πz/π-zip).

Число π - это особенное, по-своему магическое число. У него достаточно много интересных свойств, но сейчас нас интересует два:

• Число π - бесконечная дробь
• Число π - непериодическая дробь

Таким образом в записи числа π существует абсолютно любое другое число. А любая компьютерная информация это последовательность нулей и единиц (битов), которую можно представить в виде чисел.

И именно на этих двух фактах построен этот архиватор. При упаковке данных осуществляется поиск последовательности в числе π, описывающей бинарное представление упаковываемого файла. В итоге абсолютно любые данные можно описать с помощью двух чисел:

• Позиция первого символа в записи числа π
• Длина последовательности

На практике (с учётом современных вычислительных средств) поиск таких последовательностей займёт непозволительно много времени. Для упрощения поиска весь набор байт разбивается на "чанки", кусочки данных некоторого размера, которые будет проще найти в записи числа π, и уже они записываются в файл архива.

Если смотреть на вещи ещё более реалистично, то даже такой подход оказывается очень плох: числа получаются очень длинными, расчёты очень медленными, и результирующий файл архива запросто может оказаться больше по размеру, нежели исходные данные.

Однако, я верю в человеческий гений, и верю, что наши технологии и алгоритмы смогут развиться до такой степени, чтобы быстро и легко производить расчёты с трансцендентными и иррациональными числами. Поэтому я хочу успеть запрыгнуть в вагон этого поезда и описать свой формат архива, базирующегося на числе π, и представить некоторую реализацию утилиты для упаковки и распаковки данных этим способом, опираясь на работы выдающихся современных математиков.

О названии

Варианты написания PiZ, piz, πz, π-zip считаются эквивалентными.

Основное название PiZ строится из двух частей: названия числа π на латинице и первой буквы названия формата Zip, как одного из самых популярных форматов архивов на сегодняшний день.

Так же название piz удачно является инверсией названия формата zip.

Читаться названия PiZ, piz и πz должны как [pai zet]. Название π-zip должно читаться как [pai zip].

Про πfs (pifs)

Существует прекрасный программный проект, так же основанный на особенностях числа π - πfs!

Фактически этот проект и вдохновил меня на создание данного архиватора. Ведь использование расчётов числа π в реальном времени для файловой системы очень ресурсозатратно, и, скорее всего, не очень практично. А вот возможность сохранить свои данные для долгосрочного хранения в виде piz-архива видится мне гораздо более применимым на практике вариантом! Более того, в случае нахождения полной последовательности ваших байт в числе π, вы можете запросто распечатать файл архива на бумаге, сделать в виде татуировки или вырезать в камне, и тогда получить обратно свои файлы вы сможете даже через миллионы лет! Главное сохраните так же описание этого формата...

Тем не менее, если вы заинтересовались проектом PiZ, рекомендую так же взглянуть на πfs :)

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

Краткое описание

Формат архива разработан в первую очередь человеко-читаемым, чтобы "распаковать" исходные данные можно было имея только ручку и листок (скорее пачку листов) бумаги. При этом, предусмотрена возможность кодирования таким образом, чтобы чтение было удобно для ЭВМ, а не человека.

Достигается это с помощью возможности указания основания систем счисления, использованных для записи чисел в файле формата и при расчёте числа π.

Дополнительно в файле формата определены опциональные поля для сохранения метаданных исходного файла.

Рекомендации

1. Файлу архива рекомендуется прописать суффикс (расширение) .piz
2. PiZ предназначен для сжатия непрерывного набора данных, то есть одного файла (подобно gzip). Для сжатия набора файлов рекомендуется использовать утилиту tar, а результирующий tar-архив упаковывать с помощью PiZ.

Структура .piz-файла

<Обязательная метка архива>	[<Основание записи чисел в этом файле (по умолчанию Dec)>	[<Основание чисел для расчёта (по умолчанию, как у записи)>]]
	[ctime:	<время создания в формате yyyy-mm-dd hh:mm:ss (24 часа)>]
	[mtime:	<время последней модификации в формате yyyy-mm-dd hh:mm:ss (24 часа)>]
	[atime:	<время последнего доступа в формате yyyy-mm-dd hh:mm:ss (24 часа)>]
	[fname:	<наименование содержимого файла в кодировке utf-8>]
	[fmode:	<режим доступа к файлу в восьмеричной записи (формат линукс)>]
	[owner:	<имя владельца>[:<группа владельца>]]
<Размер чанка данных первой группы данных (количество цифр числа Пи, которые надо искать далее)>
	<Стартовая позиция первого чанка данных (место, начиная с которого надо искать цифры числа Пи)>
	[<Стартовая позиция следующего чанка данных>...]
[<Размер чанка данных второй группы данных>
	<Стартовая позиция первого чанка данных (место, начиная с которого надо искать цифры числа Пи)>
	[<Стартовая позиция следующего чанка данных>...]...]

Обратите внимание, что в файле формата используются обязательные знаки табуляции (\t) и переноса строки (\n). Последняя пустая строка в файле так же обязательна.

Примеры .piz-файлов

Самый минималистичный пример

PiZ
0
	0

В данном примере опущены все опциональные поля, а полный размер файла составляет 9 байт. Для наглядности представлю ту же запись в "линейном" виде: PiZ\n0\n\t0\n.

Здесь:

• PiZ - обязательная метка формата архива;
• \n - обязательный перенос строки, как признак окончания заголовка формата;
• 0 - количество цифр числа π, которое необходимо найти (в данном случае десятичное число);
• \n - обязательный перенос строки, как признак окончания числа;
• \t - обязательный символ табуляции, как признак, что на этой строке записана позиция искомых данных в числе π;
• 0 - стартовая позиция, с которой начинаются данные (в данном случае десятичное число);
• \n - обязательный перенос строки, как признак окончания числа.

Данный минималистичный архив будет "распакован" в 0 байт информации.

Полный пример

PiZ	Dec	Hex
	ctime:	2022-10-17 14:45:27
	mtime:	2022-10-17 14:45:27
	atime:	2022-10-17 14:45:27
	fname:	trash-data.bin
	fmode:	0777
	owner:	user:users
50
	50
	150
	250
100
	1000
	10000
	100000
1000
	100
	200
	300
	400
	500

В данном примере заполнены все опциональные поля и представлено три группы данных, с указанием размера каждой из них. В заголовке формата указано, что запись в файл архива произведена десятичными числами, а при расчётах цифр числа π следует использовать шестнадцатеричную систему счисления.

Данный пример является полноценным архивом и может быть распакован в файл с именем "trash-data.bin" размером 2725 байт (при размере архива в 223 байта). Стоит отметить, что в данный пример составлялся вручную, а не путём упаковки каких-то данных, поэтому в результате обработки данного примера получится "мусорный" набор байт.

Спецификация

Конкретная специфика будет готова позднее.

Описание утилиты piz

Общая информация

Это консольная утилита, написанная на языке программирования Rust.

В данный момент она в глубокой альфа-версии, поэтому не поддерживает упаковку чанками (как в примерах формата). То есть, в процессе упаковки, считывается весь файл и идёт попытка найти в числе π последовательность, полностью описывающая данный файл. Осуществить такую упаковку возможно только для специально подготовленных данных, поэтому не стоит на данном этапе экспериментировать с упаковкой.

При этом распаковка возможно для любого архива, соответствующего спецификации формата.

Основные этапы (Milestones)

• 0.0.1 - Составление начальной спецификации
• 0.1.0 - Возможность распаковки архива в формате Dec Hex <-- Вы здесь
• 0.1.1 - Решить проблему с переполнением чисел (перейти на f64 или взять длинную арифметику)
• 0.1.2 - Простое распараллеливание расчётов цифр числа π
• 0.1.3 - "Причёсывание" CLI
• 0.1.4 - Возможность использования кэша посчитанных ранее цифр числа π
• 0.1.5 - Сохранение кэша между запусками
• 0.2.0 - Возможность распаковки архива в формате Dec Bin
• 0.3.0 - Возможность распаковки любого валидного архива
• 0.4.0 - Правильная обработка метаданных
• 0.5.0 - Возможность упаковки одним чанком в формате Dec Bin
• 0.6.0 - Возможность упаковки одним чанком в формате Dec Hex
• 0.7.0 - Возможность упаковки одним чанком в формате Dec 256
• 0.8.0 - Возможность упаковки одним чанком в любом формате
• 0.9.0 - Возможность работы через pipes (для использования tar | piz и piz | tar)
• 0.10.0 - Возможность упаковки с делением на чанки заданной длины
• 0.11.0 - Возможность упаковки с делением на заданное количество чанков
• 0.11.1 - Сложное распараллеливание расчётов цифр числа π
• 1.0.0 - Окончательная стабилизация спецификации формата архива. Написание конкретных специализаций для различных оснований чисел при расчётах, с упором на скорость работы алгоритма
• 2.0.0 - Коллаборация с лучшими математиками и программистами нашего времени для поиска лучших вариантов алгоритмов
• 3.0.0 - Успешная упаковка и последующая распаковка реальных данных размером более 3,14 Gb за разумное время
• 3.14.0 - Успешное повсеместное внедрение архиватора для выполнения бытовых и производственных нужд

Ремарка:

В процессе разработки промежуточные этапы могут добавляться или выполняться раньше намеченного плана.

Устранение каких-либо этапов с мотивацией "это не нужно" или "это не возможно" - не допустимы и строго запрещены!

Использование утилиты

Для удобства использования интерфейс утилиты старается быть максимально похожим на прочие популярные инструменты командной строки.

piz [ПАРАМЕТР]... [ФАЙЛ]...
Упаковывает или распаковывает ФАЙЛы (по-умолчанию действие определяется по структуре файла).
Если ФАЙЛ не указан, или указан -, чтение происходит из стандартного потока ввода.

ПАРАМЕТРы:
    -c, --stdout                    Запись в стандартный поток вывода
    -d, --decompress                Принудительно попытаться распаковать файл
    -D, --compress                  Принудительно запаковать файл
    -f, --force                     Принудительная перезапись существующих файлов
    -h, --help                      Вывод справочной информации
    -L, --license                   Вывод лицензии
    -m, --no-meta                   Не сохранять/не извлекать метаинформацию о файле
    -M, --meta                      Сохранять/извлекать метаинформацию о файле (по-умолчанию)
    -q, --quiet                     Не выводить предупреждения
    -s, --no-suffix                 Не использовать стандартный суффикс архива .piz
    -S, --suffix=<SUF>              Использовать суффикс <SUF> вместо стандартного суффикса .piz
    -v, --verbose                   Подробный вывод
    -V, --version                   Вывод версии приложения
    -w, --no-cache                  Не использовать кэш
    -W, --cache[=</path/to/cache>]  Использовать кэш расположенный в </path/to/cache>
                                    Если путь не указан, используется стандартный кэш
                                    Если параметр не указан, используется стандартный кэш
    -n, --chunks=<N>                Разбить исходный файл на <N> чанков равного размера
    -b, --size=<N>                  Разбить исходный файл на чанки размером <N> байт
                                    Допустимо использовать суффиксы K, M, G, T, P, E, Z, Y для значений степеней десятки
                                    Допустимо использовать суффиксы k, m, g, t, p, e, z, y для значений степеней двойки
    -F, --full                      Упаковать файл одним чанком
                                    Параметр включен по-умолчанию
    -j, --threads[=<N>]             Упаковка в <N> потоков
                                    Если <N> не указан используется количество ядер процессора
                                    Если параметр не указан, то используется 1 поток.

Несовместимые между собой параметры:
    -d/--decompress и -D/--compress
    -m/--no-meta    и -M/--meta
    -s/--no-suffix  и -S/--suffix
    -w/--no-cache   и -W/--cache
    -n/--chunks,      -b/--size     и -F/--full
Если указан параметр -q/--quiet, то применяется последний указанный из несовместимых параметров.
В противном случае работа приложения прекращается с ошибкой.

При указании в любом сочетании ключей -V/--version, -L/--license, -h/--help будет выведена вся запрошенная информация
и приложение завершит работу.

Примеры использования утилиты

Упаковка:

$ tar -cf- file1 file2 file3 | piz -mc > archive.tar.piz

$ tar -cf archive.tar file1 file2 file3
$ piz archive.tar

Распаковка:

$ piz -mc archive.tar.piz | tar -xf-

$ piz archive.tar.piz
$ tar -xf archive.tar

Математика

На данный момент использованы алгоритм BBP, за авторством David H. Bailey, для расчётов в шестнадцатеричной системе счисления, и алгоритм Fabrice Bellard для расчётов в любой другой системе счисления.

Я далеко не великий математик, поэтому выбор данных алгоритмов может быть не совсем корректным, но если вы посмотрите на запланированные этапы разработки, там есть "камни" для улучшения именно математики ;)

Лицензия

На данный момент проект не лицензирован полноценно. Можете считать, что он распространяется под WTFPL. Позже этот вопрос будет решён с применением полноценного юридически верного лицензионного соглашения (вероятнее всего это будет MIT/Apache 2.0).