Опрос

Какой архиватор наиболее эффективный?:

Новички

Виктор Васильев
Юрий Антонов
Сергей Андреевич
Генадий
Avanasy

Препроцессинг нетекстовых данных

Было замечено, что многие файлы содержат данные, записанные не в самом удобном виде для сжатия традиционными универсальными компрессорами. И если изменить форму представления этих данных, то эффективность сжатия файлов заметно увеличится. Многие компрессоры уже оснащены препроцессо­рами регулярных структур и исполнимых файлов. Среди них можно отметить 7-Zip, АСЕ, CABARC, DC, IMP, PPMN, SBC, UHARC, YBS.

Преобразование относительных адресов

Как известно, в системе команд процессоров Intel адреса меток в ряде случаев записываются в виде смещения от адреса текущей команды до ад­реса соответствующей метки. Так записываются команды CALL (код опе­рации 0хЕ8), JMP (код операции 0хЕ9). В результате, если ряд команд ссы­лаются на одну и ту же метку, каждый раз адрес этой метки записывается по-разному.

Главная идея преобразования заключается в замене относительных адре­сов на абсолютные. Обычно подпрограмма вызывается несколько раз из разных участков программы. Тогда несколько относительных адресов будут преобразованы в один абсолютный адрес, вследствие чего количество раз­личных строк в файле уменьшится, а степень сжатия возрастет. Причем не обязательно получать истинные абсолютные адреса меток. Лишь бы преоб­разование было обратимо.

Рассмотрим, например, преобразование адресов 32-разрядной команды CALL. Команда записывается в виде последовательности 5 байт:

0хЕ8 I Rp________ R, I R2_________ R3

Относительное смещение R вычисляется по формуле

R = Ro + (Ri«8) + (R?«l 6) + (R3«24).

Зная смещение команды CALL от начала файла и относительное смеще­ние R, можно вычислить абсолютный адрес. При этом следует учитывать, что не все символы с кодом 0хЕ8 являются началом команды CALL. Чтобы отличить настоящие команды, предлагается довольно простой способ, при­мененный в архиваторе CAB ARC [3].

Введем следующие обозначения:

С - величина смещения анализируемой команды от начала файла (а именно смещение байта кода операции - 0хЕ8 или 0хЕ9);

N - размер файла;

R - смещение метки, на которую указывает операнд команды, относи­тельно самой команды CALL;

А - абсолютный адрес метки.

Разделим все значения относительных смещений на 4 диапазона.

Первым делом определим диапазон значений смещений, которые имеет смысл подвергать преобразованию. Минимальное значение этого диапазона соответствует ссылке команды на начало файла, максимальное - на конец.

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

Прежде чем определять остальные два диапазона, рассмотрим процесс пре­образования относительных значений из первого диапазона в абсолютные:

A = R+C.

В результате преобразования получим величину, которая может прини­мать значения от нуля до N-l. Таким образом, в результате преобразования мы отображаем значения из отрезка [-C,N-C) на значения отрезка [0,N).

Для обеспечения возможности однозначного декодирования введем тре­тий диапазон, [N-C.N), над которым будем осуществлять компенсирующее преобразование, т. е. [N-C.N) -> [-С,0).

Оставшиеся значения смещений поместим в четвертый диапазон. Эти значения в результате преобразования будут оставаться неизменными.

Преобразование относительных адресов можно представить в виде рис. 7.4. Преобразование относительных значений [-C,N-C) в абсолютные значения [0,N) показано толстой сплошной стрелкой, компенсирующее пре­образование - толстой пунктирной.

[-0x80000000, -Q

[-C.N-Q

[N-QN)

[HOxVFFFFFFF)

[-0x80000000, -Q

[-QP)

рдо

[НОхУШ-Ш*')

Рис. 7.4. Схема преобразования относительных значений в абсолютные

После преобразования заменим запись команды CALL такой последова­тельностью:

0хЕ8 Ао А, А2 А3

где

Ао = А & OxFF; А, = (А»8) & OxFF; A2 = (A»16)&0xFF; А3 = (А»24) & OxFF.

Функция преобразования выглядит следующим образом:

//in - указатель на найденную команду // ор - адрес в буфере, где записан операнд // cur_pos - номер позиции команды в файле // file_size - размер файла

op = (long *)&in[l]; if( *ор >= -cur_pos &&

*ор < file_size - cur_pos ) { *op += cur_pos; ) else if( *op > 0 &&

*op < file_size ) { *op -= file size;

Аналогичное преобразование выполняется и для команды безусловного перехода, JMP. Правда, замена относительных значений адресов для этой команды не так эффективна. В частности, из-за того, что, как правило, чис­ло команд относительного перехода на один и тот же абсолютный адрес в среднем меньше, чем количество вызовов одной и той же подпрограммы. А также из-за того, что относительные адреса обычно принимают меньшие значения, чем в случае с командой CALL, т. е. могут быть эффективно сжа­ты и без какого-либо преобразования. Поэтому преобразование может даже ухудшить сжатие. Решение о применении данного преобразования можно принимать на основе оценки статистики его выполнения. Критерием целе­сообразности выполнения преобразования может выступать следующее ус­ловие: доля компенсирующих преобразований адресов незначительна и в результате преобразования получается большое число совпадающих значе­ний абсолютных адресов.

Сравним влияние описываемого преобразования команд CALL и JMP на сжатие данных компрессорами, представляющими различные методы. В ка­честве тестового файла был использован исполнимый модуль wcc386.exe из дистрибутива Watcom С 10.0 (табл. 7.11).

Таблица 7.11

Архиватор

Тип метода сжатия

Размер

архива,

байт

Замена операндов команды CALL

Замена операндов ■ команд CALL и JMP

Размер

архива,

байт

Улучше­ние сжа­тия, %

Размер

архива,

байт

Улучше­ние сжа­тия, %

Bzip2, вер 1.00

BWT

308624

291492

5.55

292051

5.37

WinRAR, вер 2.70

LZ77

298959

281584

5.81

280995

6.01

НАа2, вер. 0.999с

РРМ

296769

280316

5.54

279959

5.66

Следует отметить, что данное преобразование, хотя и является достаточ­но простым и эффективным, может быть усовершенствовано для достиже­ния более сильного сжатия. Например, можно заметить, что код операции 0хЕ8 соседствует с младшим байтом значения абсолютного адреса Ао, в то время как более логичным было бы расположить рядом более связанные друг с другом 0хЕ8 и А3. То есть, можно записывать значение абсолютного адреса старшими байтами вперед. Другой способ повышения эффективно­сти заключается в предварительном составлении списка всех процедур, на которые делаются ссылки в программе, и указании номеров процедур в спи­ске вместо адресов.

Упражнение. Напишите процедуру обратного преобразования абсолютного значения адреса в относительное.

Преобразование табличных структур

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

Например, рассмотрим преобразование таблиц, представляющих собой упорядоченный по возрастанию список 32-разрядных значений. Чем нам могут помешать эти структуры в первоначальном виде? Статистические ха­рактеристики таких табличных последовательностей обычно сильно отли­чаются от характеристик файла в целом. Например, в таблицах рядом нахо­дятся байты, имеющие разный вес в составе 32-разрядных значений и ста­тистически слабо связанные между собой. Таким образом, эти таблицы не только сами хранятся в неудобном для сжатия виде, но и ухудшают сжатие окружающих их данных за счет искажения вероятностных характеристик.

Первая задача, которая встает перед нами, - распознать такие таблицы среди остальных данных. Учтем, что таблицы могут быть произвольного размера и располагаться в любом месте файла. Будем рассматривать какую-то область данных как таблицу при выполнении следующих условий:

■ Если нам в файле встретились подряд три 32-разрядных числа, идущие в
неубывающем порядке, будем считать это началом таблицы. Например
(1-й байт самый младший):

0x05 0x00 0x80 0x3f 0x05 0x00 0x80 0x3f 0x35 0x00 0x80 0x3f

■ Если эти -числа могут быть закодированы при помощи RLE, отказываем­ся от применения преобразования таблиц.

■ Концом таблицы будем считать число, которое превышает предыдущее более чем на 2* - 2 или меньше предыдущего.

Выполним преобразование таких таблиц следующим образом:

■ Первые 3 числа таблицы записываем в неизменном виде.

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

■ В качестве признака конца таблицы записываем дополнительно символ с кодом 28 - 1 = OxFF.

В качестве тестового файла возьмем тот же исполнимый модуль wcc386.exe из дистрибутива Watcom С Ю.О.

Таблица 7.12

Архиватор

Тип метода сжатия

Размер

архива,

байт

Преобразование 32-разрядных таблиц

Размер

архива,

байт

Улучшение

сжатия,

%

Bzip2, вер 1.00

BWT

308624

306791

0.59

WinRAR, вер 2.70

LZ77

298959

298342

0.21

НА а2, вер. 0.999с

РРМ

296769

295240

0.52

Можно заметить, что для архиватора, использующего LZ77, выигрыш в сжатии оказался существенно меньше, чем для других методов. Это объяс­няется особенностью алгоритма кодирования указателей, используемого в WinRAR, позволяющего эффективно обрабатывать такого рода структуры.

Описанный алгоритм не является самым эффективным с точки зрения сжатия, но позволяет оценить полезные свойства такого рода преобразова­ний. Способов улучшения довольно много. Например, большие таблицы следует кодировать отдельно от всего файла. Кроме того, помимо 32-разрядных таблиц, в файле могут присутствовать и, например, 16-разрядные; в таблицах могут находиться как возрастающие, так и убываю­щие последовательности чисел и т. п. И надо сказать, зачастую суммарный эффект от применения такого рода преобразований оказывается довольно ощутимым.

Упражнение. Придумайте способ преобразования для 16-разрядных таблиц.