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

Сжимаем? Сжимаем!

Нет сомнения в том, что, однажды изобретя сжатие данных, человечество уже больше не расстанется с этой технологией (или правильнее, пожалуй, было бы говорить о целом спектре технологий, потому что сжатие сжатию рознь). Несмотря на то, что в сжатии без потерь, которое применяется при хранении большинства типов данных, сделать что-то новое очень сложно, периодически на горизонте появляются программные продукты и алгоритмы сжатия, которые пытаются предложить пользователям еще большую степень компрессии. Но получается это, надо сказать, далеко не у всех. Алгоритм сжатия LZMA, который лежит в основе ставшего весьма популярным в последние годы архивного формата 7z, является счастливым исключением из этого правила. Сжимает он действительно очень хорошо и при этом является совершенно открытым, как, впрочем, и сам формат, и даже использующий его популярный архиватор 7Zip.

Бесплатного сыра, конечно, не бывает: хотя LZMA действительно сжимает эффективнее того же ZIP'а (не верите - можете попробовать сами), и для сжатия, и для распаковки требуются достаточно большие объемы оперативной памяти. Давно тому назад это составляло проблему - помнится, когда я впервые столкнулся с необходимостью распаковать ооооочень крепко сжатый 7z-архив на стареньком Pentium-200 с 64 Мб RAM, то немало "добрых" слов было высказано в адрес создателя этого архива, не воспользовавшегося ZIP'ом или RAR'ом. Сегодня, когда 64 Мб - это несолидно уже даже для телефона, проблема с памятью не стоит так остро. А вот сжимать данные по-прежнему надо - беспроводной, особенно мобильный, трафик по-прежнему дорог, и поэтому высокая степень компрессии, достигаемая с использованием алгоритма LZMA, остается безоговорочным плюсом.

Немного об LZMA

Думаю, что подавляющее большинство наших читателей более-менее знакомы с тем, как работают современные алгоритмы сжатия данных. Самыми распространенными и при этом эффективными (и LZMA тому яркое подтверждение) остаются алгоритмы сжатия по словарю. Что это означает? Это алгоритмы, которые заменяют длинную последовательность байт, встречающуюся в файле или в потоке данных, на более короткую. Сама длинная при этом добавляется в "словарь", а при распаковке уже производится замена короткого варианта на оригинальный. За примерами, в общем-то, далеко ходить не нужно, потому что даже сжатие текста, содержащего, например, часто встречающуюся в нем фразу "персональный компьютер" с помощью её замены на более короткую аббревиатуру "ПК", способно дать какой-либо результат.

LZMA относится к словарным алгоритмам, базирующимся на старом и проверенном временем алгоритме Лемпеля-Зива. Вообще название LZMA расшифровывается как Lempel-Ziv-Markov chain-Algorithm. Этот алгоритм использует не только словари, но и теорию вероятности. Главной инновацией в LZMA стало использование вместо общепринятой модели, основанной на байтах, модели контекстов, специфических для битовых полей в каждой словарной фразе. Более высокая степень компрессии обеспечивается отсутствием смешивания несвязанных друг с другом битов в одном контексте, но при этом, в целом, простота алгоритма сохраняется примерно на том же уровне, что и для обычных, ориентированных на байты, словарных алгоритмов. Также LZMA позволяет работать со словарем очень большого размера (до 4 Гб), что, собственно говоря, и даёт нагрузку на "оперативку".

Если вас заинтересовали подробности работы LZMA, то имеет смысл обратиться к английской "Википедии" (en.wikipedia.org/wiki/LZMA). Не нужно пугаться того, что читать придется по-английски - там всё написано достаточно просто и понятно.

Преимущества этого алгоритма оценили авторы многих программных продуктов, и его применение можно встретить не только в архиваторе 7Zip, где он был реализован изначально. LZMA сегодня применяется, например, в продуктах для создания установочных дистрибутивов различных приложений, в частности, в любимом многими разработчиками средстве создания дистрибутивов для Windows-приложений InnoSetup. На нем, конечно, список не заканчивается - если вам интересно, список приложений, использующих LZMA, можно найти на всё той же странице англоязычной "Вики". Вы тоже можете добавить поддержку алгоритма сжатия LZMA в своё приложение благодаря существованию такой замечательной вещи, как LZMA SDK. Именно о ней и пойдёт наш разговор далее.

Собственно, LZMA SDK

Этот SDK можно взять по адресу 7-zip.org.ua/ru/sdk.html. "Вес" дистрибутива LZMA SDK совсем невелик, по теперешним меркам, - всего каких-то полмегабайта.

На официальной странице сайта видим, что в настоящее время этот SDK содержит в себе следующие вещи:

• Исходный код C++ для декодирования и кодирования LZMA
• Совместимый с ANSI-C исходный код для декодера LZMA
• Исходный код C# для декодирования и кодирования LZMA
• Исходный код Java для декодирования и кодирования LZMA
• Скомпилированная программа file->file LZMA для компрессии / декомпресии в Windows

Для тех, кто пишет на Си, возможно, для каких-либо встраиваемых систем, наверняка будет приятно узнать о том, что реализованный в LZMA SDK декодер LZMA использует только целочисленные инструкции и может применяться любым современным 32-битным процессором (или, при определенных условиях, 16-битным CPU).

Что ж, давайте посмотрим на то, что мы получим, когда скачаем этот SDK. Поскольку все языки сразу мы не рассмотрим, то остановимся на Java как на самом популярном из предложенных.

Фактически, в самой папке Java внутри главной папки, которую мы получаем, распаковав архив с SDK, находятся примеры реализации консольного архиватора на основе LZMA, - классы LzmaAlone, LzmaBench и CRC. Первый из них - это и есть, собственно говоря, консольный архиватор, второй реализует тестирование упакованных данных (что тоже, надо сказать, совсем не лишнее при их распаковке, поскольку, как говорится, случаи бывают разные), а третий является вспомогательным для подсчета контрольной суммы упакованных данных, что нужно при проверке их целостности. Код этих файлов достаточно простой, и, несмотря на нагромождение разных проверок аргументов командной строки, разобраться, как работать с входящими в SDK классами, совсем несложно.

Думаю, что не помешает небольшая иллюстрация работы с данными в LZMA SDK. Она, опять-таки, для Java, дана в листинге, сопровождающем этот обзор. Я взял этот программный код из класса LzmaAlone и сократил для лучшей читаемости. Фрагмент просто иллюстрирует общие принципы работы с SDK, поэтому я в нем ничего особенно пояснять не буду, поскольку пояснения грозят съесть изрядную газетную площадь - уверен, что тот, кто хотя бы поверхностно знаком с Java, сумеет разобраться в предложенном коде.

java.io.File inFile = new java.io.File(params.InFile);
java.io.File outFile = new java.io.File(params.OutFile);
java.io.BufferedInputStream inStream =
 new java.io.BufferedInputStream(new java.io.FileInputStream(inFile));
java.io.BufferedOutputStream outStream =
 new java.io.BufferedOutputStream(new java.io.FileOutputStream(outFile));
if (params.Command == CommandLine.kEncode)
{
 SevenZip.Compression.LZMA.Encoder encoder
  = new SevenZip.Compression.LZMA.Encoder();
 if (!encoder.SetAlgorithm(params.Algorithm))
  throw new Exception("Incorrect compression mode");
 encoder.SetEndMarkerMode(eos);
 encoder.WriteCoderProperties(outStream);
 long fileSize;
 if (eos)
  fileSize = -1;
 else
  fileSize = inFile.length();
 for (int i = 0; i < 8; i++)
 outStream.write((int)(fileSize >>> (8 * i)) & 0xFF);
 encoder.Code(inStream, outStream, -1, -1, null);
}
else
{
 int propertiesSize = 5;
 byte[] properties = new byte[propertiesSize];
 if (inStream.read(properties, 0, propertiesSize) != propertiesSize)
  throw new Exception("input .lzma file is too short");
 SevenZip.Compression.LZMA.Decoder decoder =
  new SevenZip.Compression.LZMA.Decoder();
 if (!decoder.SetDecoderProperties(properties))
  throw new Exception("Incorrect stream properties");
 long outSize = 0;
 for (int i = 0; i < 8; i++)
 {
  int v = inStream.read();
  if (v < 0)
   throw new Exception("Can't read stream size");
  outSize |= ((long)v) << (8 * i);
 }
 if (!decoder.Code(inStream, outStream, outSize))
  throw new Exception("Error in data stream");
}
outStream.flush();
outStream.close();
inStream.close();

В завершение статьи стоит рассказать о реализации LZMA для других языков программирования, разработчики на которых наверняка также будут рады возможности использовать этот мощный алгоритм сжатия данных. Для Delphi-программистов есть специальный компонент TSevenZipVCL (www.rg-software.de), для "питонщиков" есть специальный проект PyLZMA (www.joachim-bauch.de/projects/pylzma), представляющий собой "обертку" вокруг оригинального SDK. Для Java-программистов будет полезной небольшая библиотека LZMA Streams in Java (contrapunctus.net/league/haques), реализующая прозрачную поддержку сжатия стандартных для Java-потоков данных. Им же будет полезен 7Zip'овый "таск" для ANT'а, расположенный по адресу www.pharmasoft.be/7z. А "шарписты" наверняка "заценят" пример компрессии в памяти с использованием LZMA, он расположен по адресу www.eggheadcafe.com/tutorials/aspnet/064b41e4-60bc-4d35-9136-368603bcc27a/7zip-lzma-inmemory-com.aspx.

Что ж, теперь остается только пожелать вам успехов в работе с LZMA SDK. Думаю, что если работа будет упорной, то и успехи не заставят себя ждать.

Вадим СТАНКЕВИЧ,
[email protected]