LZ-СЖАТИЕ от MiCROSOFT
by DrMAD
ВВЕДЕНИЕ
1. История LZ
2. Кратко о LZ77 и LZSS
3. LZ и Microsoft
3.1. Формат, используемый утилитами COMPRESS/EXPAND и библиотеками
LZEXPAND/LZ32
3.2. Формат LZNT1
ЗАКЛЮЧЕНИЕ
ВВЕДЕНИЕ
В статье пойдет речь о некоторых нюансах методов сжатия данных,
используемых фирмой Microsoft в своих продуктах.
Прежде всего, надо отметить, что никто, кроме программистов
Microsoft, не знает и не может знать полного списка методов и
алгоритмов сжатия, встречающихся в коммерческих продуктах этой фирмы.
Если посмотреть на список функций, экспортируемых некоторыми
стандартными и "полустандартными" DLLками, то можно встретить огромное
количество идентификаторов, возможно, относящихся к упаковке/распаковке
данных... а, возможно, и не относящихся. J Например, можете ли Вы вот
так сразу сказать, что конкретно делают методы
_MsoFZCompressToStream@28 и _MsoFZUncompressFromStream@24, живущие
внутри mso97.dll? Вот лично я, как говорится "шоб да, так нет". K
Но кое-что на эту тему нарыть можно...
1. ИСТОРИЯ LZ
Различные, очень даже неплохие, способы сжатия данных без потерь
информации известны давным-давно (например, метод Хаффмана,
арифметическое кодирование, etc.).
Но вот, в 1977 году два добрячих iзраiльских хлопця - Абраша
Лемпель (Abraham Lempel) и Яша Зив (Jacob Ziv) изобрели оригинальный и
совершенно замечательный метод, который произвел целую революцию в
технологии сжатия. Метод получил название LZ77. Вскоре к изобретателям
примазались еще трое - Сторер (Storer), Шимански (Szimanski) и Белл
(Bell), которые оптимизировали алгоритм по скорости, по затратам
памяти, по способу кодирования выходной информации и т.п., но ничего
особо нового в идею метода не привнесли, а модификация получила
название LZSS.
Спустя год все те же Лемпель и Зив придумали LZ78 - еще один метод
сжатия, несколько похожий на предыдущий, но все же - другой. И снова
нашелся человек (Terry Welch), который вошел в историю благодаря тому,
что существенно вычистил, отполировал и оптимизировал эту разработку, а
заодно и запатентовал ее. Новый алгоритм получил название LZW.
В начале 90-х годов XX века все права на использование этого
алгоритма перекупила фирма Unisys и даже провела несколько
показательных судебных процессов над нарушителями авторского права.
Срок действия патента истек летом 2004 года, но до сих пор почти
никто официально не признается, что использует LZW, хотя, не исключено,
что втихаря это давным-давно делали многие упаковщики. Совершенно точно
известно, что LZW используется при сжатии изображений в GIF , но у
этого формата нет официального "хозяина", и поэтому в суд подавать было
не на кого. J
2. КРАТКО О LZ77 и LZSS
Идея этих методов сжатия очень проста. Рассмотрим строку
ABRAKADABRA
В этой строке дважды встречается подстрока 'ABRA'. Это позволяет
при упаковке оставить только одну копию этой подстроки, а все остальные
заменить на пары <адрес, длина>, например, так:
ABRAKAD<0,4>.
В общем случае строка, "нашпигованная" ссылками на саму себя, будет
короче оригинала, не правда ли?
На практике сжатие реализуется при помощи "окна" определенной длины
(обычно 8-32 бита), скользящего по сжимаемым данным слева направо,
причем часть данных, оставшаяся слева, играет роль "словаря", в котором
ищутся совпадения с фрагментами "окна".
В варианте LZSS для того, чтобы отличить "ссылку" <0,4> от
"нормальных" байтов с таким же значением, в упакованные данные
вставляются "служебные" байты, которые содержат информацию о
расположении "ссылок".
3. LZ И MICROSOFT
3.1. Формат, используемый утилитами COMPRESS/EXPAND
и библиотеками LZEXPAND/LZ32
Еще с 80-х годов Microsoft применяла для подготовки своих
дистрибутивов утилиту MS COMPRESS, при помощи ее можно было как
сжимать, так и распаковывать файлы. Разным версиям MS-DOS и Windows
соответствовали разные версии утилит, которые генерировали немножко
разные заголовки в сжатых файлах, но принцип сжатия оставался
неизменным - LZSS. Кроме того, с некоторыми дистрибутивами поставлялась
утилита MS EXPAND, которая умела только распаковывать такие файлы.
В составе Windows имеются динамические библиотеки LZEXPAND
(16-битовая) и LZ32 (32-битовая), которые содержат функции для
распаковки файлов, сжатых при помощи MS COMPRESS.
Давайте сожмем при помощи MS COMPESS вот такой текст длиной 247
байтов:
Attribute VB_Name = "ThisDocument"
Attribute VB_Base = "1Normal.ThisDocument"
Attribute VB_Creatable = False
Attribute VB_PredeclaredId = True
Attribute VB_Exposed = True
Attribute VB_TemplateDerived = True
Attribute VB_Customizable = True
Мы получим следующие данные объемом 156 байтов:
00: 53 5A 20 88-F0 27 33 D1-F7 00 00 00-FF 41 74 74 SZ ..'3......Att
10: 72 69 62 75-74 FF 65 20-56 42 5F 4E-61 6D FF 65 ribut.e VB_Nam.e
20: 20 3D 20 22-54 68 69 FF-73 44 6F 63-75 6D 65 6E = "Thi.sDocumen
30: EF 74 22 0D-0A EE FA 42-61 73 FE FE-F2 31 4E 6F яt...Bas...1No..
40: 72 6D 61 6C-F9 2E 03 0F-F1 F7 43 72-65 61 74 F7 rmal....Creat...
50: 61 62 6C FE-F1 46 61 6C-73 FD 65 10-0C 50 72 65 abl..Fal..ePre..
60: 64 65 63 DB-6C 61 6C 00-49 64 FF F0-54 72 FD 75 dec.lal.Id.ЁTr.u
70: 5B 0D 45 78-70 6F 73 65-FC 77 0F F6-F2 54 65 6D [Expose.w...em..
80: 70 6C 61 7F-74 65 44 65-72 69 76 93-0F FE 45 04 plteDeri...E....
90: 75 73 74 6F-6D 69 7A 00-50 04 BD 03 ustomiz.P.
Сначала идет заголовок длиной 12 байтов (его размер и содержимое
зависят от версии утилиты), четко видны уникальная сигнатура 'SZ',
00000000F7 - длина неупакованных данных, и т.п. Собственно сжатая
информация начинается с байта 12 со значением [FF]. Как же
интерпретировать эти данные?
0. [FF] - это служебный байт, все его биты установлены в 1, и это
означает, что следующие 8 байтов - обычные данные, которые необходимо
при распаковке просто скопировать в выходной поток.
1-8. 'Attribut'
9. [FF] - снова служебный байт аналогичного назначения.
10.-17. 'e VB_Nam'
18. [FF] - снова служебный байт аналогичного назначения
19-26. 'e = "Thi'
27. [FF] - снова служебный байт аналогичного назначения
28-35. 'sDocumen'
36. [EF] - служебный байт с битами 11101111. Обратите внимание, бит
номер 4 имеет значение 0, и это означает, что следующие 4 байта данных
- обычные, потом идет одна "ссылка" определенного формата, а потом
снова идут 3 обычных байта данных.
37. t
38. "
39. [CR]
40. [LF]
41-42. [EE][FA] - двухбайтовая ссылка назад. Она состоит из двух
битовых полей: [FEE] - это 12-битовый "адрес", а [A] - это 4-битовая
"длина минус 3" того образца в "словаре", на который выполняется
ссылка. Дело в том, что при распаковке в качестве входного и выходного
буферов используется один и тот же массив размером 4096 байтов. Первые
16 байтов упакованных данных считываются в конец буфера, начиная с
позиции 4079, т.е. FEEh - это начало данных. Потом индекс чтения
инкрементируется по модулю 4096, т.е. после 4095 идет 0, 1, 2 и так
далее.
42-44. 'Bas'...,
и так далее. Можно сделать вывод, что длина скользящего окна
составляет 16 битов, а ссылки выполняются на фрагменты длиной не менее
3 байтов.
3.2. Формат LZNT1
Этот метод недокументирован и используется для сжатия внутренних
данных, про которые Microsoft вообще не собирается никому ничего
рассказывать. По крайней мере известно, что методом LZNT1 сжимаются:
- файлы на диске (вероятно, в драйверах типа DBLDISK/DBLDRIVE, а
также в NTFS);
- фрагменты служебных потоков внутри структурированных хранилищ
(например, исходные тексты макросов внутри DOC-файлов).
Для работы с LZNT1 используются недокументированные функции
RtlCompessBuffer() и RtlDecompressBuffer() из NTDLL.DLL для Windows NT/
2000/XP, но не для 95/98/ME.
Посмотрим на кусочек сжатого макроса внутри DOC-файла,
располагающийся в конце потока ThisDocument:
2F0: 01 8A B0 00 41 74 74 .K..Att
300: 72 69 62 75-74 00 65 20-56 42 5F 4E 61 6D 00 65 ribut.e VB_Nam.e
310: 20 3D 20 22-54 68 69 00-73 44 6F 63 75 6D 65 6E = "Thi.sDocumen
320: 10 74 22 0D-0A 0A 8C 42-61 73 01 02 8C 31 4E 6F .t"...MBas..M1No
Сначала располагается заголовок, начинающийся с сигнатуры [01].
Далее идет 16-битовый заголовок вида 111XXXXXXXXXXXXX, где XXXXXXXXXXXX
- длина упакованного фрагменат данных ("чунка"). Собственно сжатые
данные начинаются с 3-го байта. Это тоже LZSS, но организованный
чуть-чуть иначе.
0. [00] - служебный байт. В LZNT1 позиции ссылок отмечают не
нулевые, а единичные биты. Таким образом, байт [00] означает, что
следующие 8 байтов - "нормальные".
1-8. 'Attribut'
9. [00] - снова служебный байт аналогичного назначения.
10.-17. 'e VB_Nam'
18. [00] - снова служебный байт аналогичного назначения
19-26. 'e = "Thi'
27. [00] - снова служебный байт аналогичного назначения
28-35. 'sDocumen'
36. [10] - служебный байт 00010000, который означает: далее 4 байта
"нормальных", потом 16-битовая ссылка, потом опять 3 байта
"нормальных".
37. t
38. "
39. [CR]
40. [LF]
41-42. [0A][8C] - ссылка. Формат ее - переменный. В начала файла 4
бита - на длину, 12 - на адрес; потом 5/11, потом 6/10, и т.п., а в
конце файла - 12/4. Слово 8C0Ah=1000110000001010 - это ссылка формата
6/10, которая означает, что: [0Ah]=0000001010 - "длина минус три";[23h]
=100011 - относительный "адрес минус 1", который отсчитывается не от
начала данных, а назад от текущей позиции, т.е. 0000001010 = 0Ah
соответствует длине 13, а 100011 соответствует позиции "36 назад от
текущей".
43-45. 'Bas'..., и так далее.
ЗАКЛЮЧЕНИЕ
Ну вот и все. Программы упаковки/распаковки пишутся тривиально.
Нужно только не забывать, что оба рассмотренных выше метода сжимают
данные блоками ("чунками") по 4096 байтов. Удачи!
|
