Nicron #21 21 февраля 1997

Программирование - курс изучения ассемблера от Wlodek Black, продолжение. Методы сжатия данных.

╔──────────────────────────────────────────────────────────────╗
│ ▒▒▒▒░  ▒▒▒▒░  ▒▒▒▒░ ▒▒▒▒▒▒░▒▒░ ▒▒░▒▒▒▒▒▒░  ▒▒▒▒░▒▒▒▒▒▒░▒▒▒▒▒░│
│▒▒░ ▒▒░▒▒░ ▒▒░▒▒░ ▒▒░▒▒░    ▒▒▒▒▒▒░▒▒░     ▒▒░▒▒░▒▒░    ▒▒░ ▒▒│
│▒▒░ ▒▒░▒▒░    ▒▒░    ▒▒▒▒▒░ ▒▒░ ▒▒░▒▒▒▒▒▒░ ▒▒░▒▒░▒▒▒▒▒░ ▒▒░ ▒▒│
│▒▒▒▒▒▒░▒▒░ ▒▒░▒▒░ ▒▒░▒▒░    ▒▒░ ▒▒░▒▒░ ▒▒░▒▒░ ▒▒░▒▒░    ▒▒▒▒▒░│
│▒▒░ ▒▒░ ▒▒▒▒░  ▒▒▒▒░ ▒▒▒▒▒▒░▒▒░ ▒▒░▒▒▒▒▒▒░▒▒░ ▒▒░▒▒▒▒▒▒░▒▒░z80│
╚──────────────────────────────────────────────────────────────╝

[ Продолжение ]

(C) WLODEK BLACK

...Снова всем здравствуйте, и возвращаемся к теме беседы. У вас
есть дема DIGITAL TUNE 1? Есть? Тогда прошу: сосчитайте,  сколь-
ко секторов она занимает и из скольких файлов состоит.  Сосчита-
ли? Правильно, 7 файлов на общую сумму 173 сектора. Пройдет сов-
сем немного времени (у меня это и получаса не отняло),  и  дема
эта съежится в один-единственный файл размером 95 секторов. Как
же сжимают данные?
   Самый простой алгоритм - отслеживание потоков одинаковых бай-
тов и замена их на конструкцию вида "маркер-префикс"+"байт  дан-
ных"+"сколько раз повторить". Такой алгоритм был использован  в
древнем и бестолковом компрессоре "RAMPACK D.J.S." Дмитрия  Сте-
паненко, опубликованном в журнале "ZX+еще" в 1991 году (помните?
Не помните? И никто уже не помнит...). Естественный  и логичный,
такой подход к проблеме сжатия данных далеко  не всегда  оптима-
лен. Экранное изображение, например, может и не содержать  длин-
ных последовательностей одинаковых байтов в памяти, но зато  ви-
зуально может состоять из множества одинаковых фрагментов, текс-
товых символов, например. Или может  содержать  крупные  "пятна"
с равномерной структурой или вообще пустые места.  Если  "прохо-
дить" экранную область не последовательно по нарастанию адресов,
а, например, сверху вниз или по знакоместам, можно будет  порой
обнаружить повторяющиеся участки, и  заменить  их  на  знакомые
"маркер"+"что повторить"+"сколько повторить", причем "что повто-
рить" может быть и не одним байтом, а, например,набором из 8-ми
байт шаблона текстового символа.  Один  из наиболее  популярных
компрессоров экрана - "Кельн", как его обычно называют, - выпол-
няет 4 прохода по экрану и сам выбирает наиболее оптимальный ал-
горитм. Методы сжатия текстовой информации не менее  разнообраз-
ны. Например, наиболее употребимые символы  можно  закодировать
не байтом, а меньшим количеством бит - допустим, 5-ю. 5-битовых
комбинаций - 32, чего достаточно для символов алфавита.  К тому
же в латинских символах всегда сброшен 7-й бит, а  в  русских -
он всегда установлен, и его тоже можно без особых ухищрений  вы-
бросить. При подобном методе сжатия маркер обозначает начало  и
длину сжатого участка, а дальше следуют, скажем, 5-битовые  ком-
бинации, плотно прижатые друг к другу с помощью операций сдвига;
например, первый байт содержит 5 бит первого символа и  3  бита
второго, второй байт - 2 бита второго символа,  5 бит  третьего
символа и 1 бит четвертого, и так далее. Один из наиболее эффек-
тивных компрессоров текстовой информации - ASC LZPAC. Даже весь-
ма хаотичные тексты, явно не содержащие последовательностей оди-
наковых символов, он сжимает процентов на 20-30, что  на первый
(непосвященный) взгляд может показаться невероятным.  Блоки  ко-
дов, не являющиеся текстами, он тоже  неплохо  упаковывает  (во
всяком случае, уж получше, нежели "RAMPACK DJS"). Существуют  и
еще более эффективные компрессоры, например MSPACK.  Не буду на-
стаивать, но, на мой взгляд, для экранного компрессора одной из
важнейших характеристик является возможность  запуска  распаков-
щика (программы, восстанавливающей исходные данные) с любого ад-
реса, а для текстового упаковщика - эффективность сжатия данных
и... безглючность (да, да, ибо опыт использования  всевозможных
"читалок" для газетных и других текстов вынуждает упоминать и о
такой, с позволения сказать, "характеристике").  Опять-таки  не
буду настаивать, но на первых порах советую обзавестись  упаков-
щиками "А.С.Кельн" для экрана и "ASC LZPAC" для текстов и кодов.
   Если от сжатия текста компрессором мы только выигрываем,  то
от сжатия мыслей, наверно,  ничего хорошего  не получится...  Я
это к тому, что "NICRON", увы, не резиновый... Здесь мне придет-
ся закругляться до следующего выпуска, но, чтобы тема  не повис-
ла, как завешенный сервер, прошу вас, друзья, те, кто  интересу-
ется и присылал в "NICRON" вопросы, выполните за предстоящую не-
делю такое "домашнее задание":  возьмите  файлы      "M      3",
"M      4", "M      6" от демы "DIGITAL TUNE 1" и  упакуйте  их
LZPAC-ом. На все вопросы компрессора,  кроме  "Code keep place",
отвечайте предельно кратко - Enter, а на этот вопрос введите ад-
рес "49152". Результаты, конечно, выгрузите на диск  под  любым
именем. Далее нажмите Reset, чтобы очистить ОЗУ, и  в  "чистую"
машину загрузите последовательно подряд файлы "M", "M      0" и
"M      7". Данные из этих файлов присутствуют в памяти  и испо-
льзуются совместно, и нет никакой надобности грузить их порознь.
Выгрузите их одним файлом с адреса 31232  и длиной  21196  байт
(49152+3276-31232). Упакуйте и этот файл, указав "Code keep pla-
ce"=31232. И, наконец, выдерите из демы картинку.  Это делается
так: загрузите Бейсиковый загрузчик  "D.TUNE#1"  через  "merge",
чтобы он не стартовал, и выполните такую строку:  RANDOMIZE USR
23872:RANDOMIZE USR 15619: REM : SAVE "dt1$" CODE 16384,6912. И
картинку эту запакуйте "Кельн"-ом (если вы еще  не освоили  его
управление, то спешу порадовать: все сообщения в нем сделаны на
русском языке; жмите цифры с номерами ответов, и все дела).  На
следующем "занятии" мы соберем все упакованные файлы  в один ме-
шок... Тьфу! Мы сделаем к ним монозагрузчик, вот!
   До встречи через неделю!

P.S. Пользуясь случаем,  хочу  поблагодарить  Германа  и  Глеба
(CHIP) за помощь в приобретении программ под CP/M!