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

Было замечено, что многие файлы содержат данные, записанные не в самом удобном виде для сжатия традиционными универсальными компрессорами. И если изменить форму представления этих данных, то эффективность сжатия файлов заметно увеличится. Многие компрессоры уже оснащены препроцессо­рами регулярных структур и исполнимых файлов. Среди них можно отметить 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 R₂_________ R3

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

R = Ro + (Ri«8) + (R_?«l 6) + (R₃«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) показано толстой сплошной стрелкой, компенсирующее пре­образование - толстой пунктирной.

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

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

0хЕ8 Ао А, А₂ А₃

где

Ао = А & OxFF; А, = (А»8) & OxFF; A₂ = (A»16)&0xFF; А₃ = (А»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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 7.12

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

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

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