Алгоритм сжатия "Unbuffered RLE"
Дмитрий Сахань
Контакт с автором: www.aimatrix.nm.ru
Хочешь совершенства – создай его своими руками. (AIMatrix)
Возникла у меня задача использовать сжатие по методу RLE. Одним из важных условий было жесткое ограничение в исполняемом механизме, что проще можно сформулировать как отсутствие лишних ячеек памяти плюс выделение кодировщику недопустимо малого количества регистров процессора. Грубо говоря, все выглядело так, как если бы в окончательном варианте кодировщик работал внутри примитивного аппаратного устройства, собранного на базе не менее примитивного микропроцессора. Причем желательно было сразу найти такое решение, в котором устройство не содержало бы вообще памяти (как пример, на плате остается только один микропроцессор), а сам процессор чтобы был ну чуть ли не I8008 (один из первых микропроцессоров фирмы Intel, разработанный в 70-х годах прошлого века). На вход устройство побайтно принимает байты входного незакодированного потока, а на выход сбрасывает байты уже RLE-закодированного потока.
Несмотря на давнишнее рождение RLE как алгоритма сжатия несложных изображений и его нынешнюю неэффективность в свете сложности (обилие мелких деталей, высокие битовые глубины) современных изображений, все-таки и сегодня существует класс приложений, где использование RLE более оправдано, нежели применение других алгоритмов. Оправданием служит простота алгоритма RLE, а значит уменьшаются финансовые (впрочем, как и аппаратные) затраты на исполняющие блоки некоторой контролирующей системы. Ну, допустим, такой пример. В одном помещении находится светодиодно-фотодиодный приемник, сканирующий движущуюся перед ним бумажную ленту с нанесенными на нее вертикальными черными полосами разной ширины (что-то в духе непрерывного штрих-кода). По кабелю вся последовательность отсканированных сигналов направляется в другое помещение, на следящую систему. Можно отправлять сигналы как не сжатый поток, но можно ведь, сжимая предварительно поток, уменьшить нагрузку на транспортную магистраль. Вот здесь и появляется дилемма: то ли увеличивать стоимость и сложность приемника (ибо как раз на его стороне должно выполняться сжатие), то ли отказаться от сжатия в принципе. И если сжатие будет достигнуто ценой дешевого усовершенствования считывающего приемника, то дилемма решаема в положительную сторону.
Однако в чистом виде RLE не обеспечивает полного удешевления конструкции приемного устройства. Давайте вспомним, как работает RLE. Из входного потока извлекается байт. Если он был равен предыдущему извлеченному байту (соседние байты одинаковы), тогда просто увеличивается на 1 внутренний счетчик повторов для данного байта, а в выходной поток пока ничего не сбрасывается. Как только новый извлеченный из входного потока байт отличается от предыдущего байта, в выходной поток выбрасывается СЧЕТЧИК повторов, а затем ПОВТОРЯВШИЙСЯ байт. Теперь уже начинает увеличиваться на 1 внутренний счетчик неодинаковых байт (разнобоя). Когда же во входном потоке снова будет встречен фрагмент из одинаковых байт, тогда в выходной поток будет сброшен СЧЕТЧИК разнобоя, а за ним целиком вся ПОСЛЕДОВАТЕЛЬНОСТЬ неодинаковых байт. На следующем рисунке для наглядности изображено некоторое условное содержимое входного и выходного потоков (разнобои выделены красным цветом, повторы – зеленым, синим цветом в выходном потоке обозначены поля счетчиков).
Итак, очевидно, что выходной поток состоит из "записей", причем каждая начинается с поля счетчика. Поскольку "записи" могут быть только двух типов – для разнобоев и для повторов, - а эти типы "записей" могут встречаться в выходном потоке в самом непредсказуемом сочетании, то для их точной идентификации в алгоритм RLE пришлось ввести однобитный признак, определяющий, что именно описывает (разнобой или повтор) встреченная "запись". Этот признак помещен в старший бит поля счетчика, что при размере поля в 1 байт позволяет кодировать одной "записью" не более чем 128 одинаковых или неодинаковых байт.
Но самый неприятный для удешевления конструкции приемника момент кроется в необходимости применения дополнительной памяти – буфера, ведь в выходной поток мы должны сначала вытолкнуть счетчик разнобоя, и только потом всю последовательность неодинаковых байт. А это значит, что такую последовательность байт придется где-то временно накапливать, пока не встретится фрагмент одинаковых байт.
Из затруднительного положения выход есть. Я попробовал модернизировать по своим соображениям алгоритм RLE, из чего уродился его собрат, который по определенным параметрам оказывается предпочтительнее. К числу таких параметров относится, во-первых, удивительная простота алгоритма (для исполнения хватает трех регистров микропроцессора), во-вторых, исключается за ненадобностью однобитный признак типа "записи" (счетчик теперь описывает до 255 повторов, а не до 128), а в-третьих, полностью отказываемся от счетчика разнобоев. То есть используем только один счетчик, и считать он будет только повторы одинаковых байт. Весь разнобой отправляется без задержек в выходной поток, благодаря чему имеем еще один дополнительный плюс, и заключается он в следующем. В обычном RLE пополнение выходного потока идет неравномерно, то есть с задержками во времени, что обусловлено периодом ожидания конца фрагмента одинаковых или неодинаковых байт. В алгоритме Unbuffered RLE задержки случаются только при ожидании конца фрагмента одинаковых байт.
В двух словах описать механику работу алгоритма можно так. Извлекая из входного потока байт, мы сравниваем его с предыдущим извлеченным байтом. Если новый байт отличается от предыдущего байта, просто выталкиваем его в выходной поток. Если же он одинаков с предыдущим байтом, начинаем увеличивать счетчик повторов на каждый следующий такой же байт и ждем окончания фрагмента одинаковых байт. Как только фрагмент закончился, сбрасываем в выходной поток ПОВТОРЯВШИЙСЯ байт, а затем сбрасываем в поток СЧЕТЧИК минус 1, то есть сколько этот байт повторялся после только что выброшенного в поток байта. Сразу уточню, что первый байт из фрагмента одинаковых байт уже итак попал в выходной поток (он был воспринят как неодинаковый с предыдущим), однако за ним мы вынуждены снова затолкнуть в поток этот же байт вместе со счетчиком повторов минус 1, иначе декодер впоследствии не сможет декодировать правильно сжатый поток. Чтобы стало понятнее, обратимся к примеру, в нем квадратными скобками обозначены "записи" для повторов, круглыми скобками - "записи" для разнобоев.
Пусть входной поток будет таким:
6 2 17 9 9 9 9 9 9 9 9 4 10 10 10 10 10 10 10 10 7 11 6 4 3
Тогда выходной поток станет таким:
6 2 17 [9 9 6] 4 [10 10 6] 7 11 6 4 3
В то же время обычный RLE создаст такой выходной поток:
(3 6 2 17) [8 9] (1 4) [8 10] (5 7 11 6 4 3)
Разница в том, что Unbuffered RLE делает "записи" только для фрагментов из одинаковых байт, причем счетчик повторов всегда находится в конце "записи" и трактуется как "еще столько раз повторить байт, находящийся перед счетчиком". Помимо этого, отпадает необходимость введения в выходной поток признака типа "записи", потому что существует только один тип "записи" – для повторов. А разнобойные фрагменты попадают в выходной поток без указания размера фрагмента (счетчик для них не нужен), так как конец такого фрагмента всегда обозначается встречей двух одинаковых байт либо вообще достижением конца выходного потока.
Дальше привожу полный ассемблерный код алгоритма, даже с учетом чтения из входного потока первого байта, для которого вообще не существует предыдущего байта. И даже с учетом невозможности использования памяти, а вместе с этим и команд CALL (вызов подпрограммы), так как во многих микропроцессорах стек по определению нельзя использовать при отсутствующей памяти. И даже с учетом контроля переполнения счетчика повторов. Приведенный код использует всего три регистра микропроцессора, а совокупный размер кода – 27 однотактных команд. В общем, дешево и сердито, к тому же вдобавок получаем минимум временных затрат во время выполнения алгоритма (на каждый разнобойный байт уходит 8 тактов времени, а на каждый одинаковый байт – или 8 тактов, или 9 тактов, или 13 тактов в зависимости от местоположен
Unbuffred_RLE: // -----------------------
//
mov bl, 0 // BL = очистить счетчик повторов
in al, Number_of_InputPort // AL = первый байт из входного потока
jmp Put_to_OutputStream // сразу же вывести его в выходной поток
//
Get_from_InputStream: // -----------------------
//
//-----------------------------//
//
// здесь вставить контроль
// выхода из бесконечного цикла,
// если алгоритм должен работать
// не внутри аппаратного устройства
//
//-----------------------------//
//
in al, Number_of_InputPort // AL = следующий байт из входного потока
cmp al, ah // равен ли он предыдущему байту?
jnz Put_to_OutputStream // если нет, вывести его в выходной поток
//
cmp bl, 0 // повторы байта уже начались (BL <> 0)?
jnz Increment_Counter // если да, увеличить счетчик повторов на 1
out Number_of_OutputPort, al // записать байт в выходной поток
//
Increment_Counter: //------------------------
//
inc bl // BL = +1 одинаковый байт поступил
cmp bl, 255 // превышен лимит счетчика в 255 повторов?
jnz Get_from_InputStream // если нет, взять следующий байт
//
Put_Counter: //------------------------
//
dec bl // BL = сколько раз декодеру копировать байт
mov al, bl // передать счетчик в AL
out Number_of_OutputPort, al // и вывести его в выходной поток
mov bl, 0 // BL = очистить счетчик повторов
jmp Get_from_InputStream // взять из входного потока следующий байт
//
Put_to_OutputStream: //------------------------
//
mov ah, al // этот байт теперь становится предыдущим
cmp bl, 0 // были ли повторы байта (BL <> 0)?
jz Put_Byte // если нет, вывести в выходной поток байт
//
dec bl // BL = сколько раз декодеру копировать байт
mov al, bl // передать счетчик в AL
out Number_of_OutputPort, al // и вывести его в выходной поток
mov bl, 0 // BL = очистить счетчик повторов
mov al, ah // восстановить в AL текущий байт
//
Put_Byte: //------------------------
//
out Number_of_OutputPort, al // записать байт в выходной поток
jmp Get_from_InputStream // взять из входного потока следующий байт
Итак, регистр BL играет роль счетчика, увеличивающегося в тот момент, когда из входного потока приходят одинаковые байты. Разумеется, каждый следующий одинаковый байт увеличивает счетчик (регистр BL) на 1. Регистр AL принимает в себя тот байт, который только что поступил из входного потока. В регистре AH хранится предыдущий байт входного потока. Поскольку код ориентирован под конструкцию считывающего приемника, то есть входной порт микропроцессора подключен к свето-фотодиодной матрице, а его выходной порт подключен прямо к транспортной магистрали, поэтому и извлечение байт из входного потока и выталкивание байт в выходной поток выполнено при помощи команд чтения/записи портов ввода-вывода (номера требуемых портов заданы константами Number_of_InputPort и Number_of_OutputPort). Кроме того, работа по сжатию входного потока сделана в форме бесконечного цикла, подразумевая тот случай, когда аппаратный приемник без перерыва сканирует некую внешнюю информацию, соответственно, также постоянно эта информация (уже сжатая) поступает в транспортную магистраль.
И ниже то же самое, но уже для программистов в языках высокого уровня. Ну, на всякий случай, вдруг нет желания разбираться в ассемблерном коде.
Счетчик = 0
Предыдущий_байт = Взять_байт_из_входного_потока
Выходной_поток = Предыдущий_байт
Бесконечный цикл
Текущий_байт = Взять_байт_из_входного_потока
Если Текущий_байт = Предыдущий_байт тогда
Если Счетчик = 0 тогда Выходной_поток = Текущий_байт
Счетчик = Счетчик + 1
Если Счетчик = 255 тогда
Выходной_поток = Счетчик – 1
Счетчик = 0
Конец если
Иначе
Если Счетчик > 0 тогда Выходной_поток = Счетчик – 1
Выходной_поток = Текущий_байт
Предыдущий_байт = Текущий_байт
Счетчик = 0
Конец если
Конец цикла
Как работает декодер
Здесь алгоритм еще проще. При декодировании бывший выходной поток является уже входным потоком, а получающийся выходной поток – это декодированная информация. Так вот, извлекая из входного потока байт, сразу же выбрасываем его в выходной поток. Далее сравниваем текущий байт с предыдущим байтом. Как только они одинаковы, извлекаем из входного потока байт, который является счетчиком повторов. Именно столько раз в выходной поток копируем текущий байт (что был перед счетчиком).
Предыдущий_байт = Взять_байт_из_входного_потока
Выходной_поток = Предыдущий_байт
Бесконечный цикл
Текущий_байт = Взять_байт_из_входного_потока
Выходной_поток = Текущий_байт
Если Текущий_байт = Предыдущий_байт тогда
Счетчик = Взять_байт_из_входного_потока
Цикл Счетчик раз Выходной_поток = Текущий_байт
Конец если
Предыдущий_байт = Текущий_байт
Конец цикла
И на всякий случай привожу ассемблерный код алгоритма декодирования. Код, естественно, рассчитан опять под аппаратное устройство, то есть дешевую плату с микропроцессором (нет памяти, используются три регистра, работа через порты ввода-вывода), которое находится на противоположной стороне транспортной магистрали и занимается банальным декодированием приходящего из транспортной магистрали потока. Тут входной порт микропроцессора подключен к транспортной магистрали, а выходной порт - к чему-нибудь еще, куда затем направляется раскодированный поток.
Decode_Unbuffred_RLE: // -----------------------
//
in al, Number_of_InputPort // AL = первый байт из входного потока
out Number_of_OutputPort, al // записать байт в выходной поток
mov ah, al // этот байт теперь становится предыдущим
//
Get_from_InputStream: // -----------------------
//
in al, Number_of_InputPort // AL = следующий байт из входного потока
out Number_of_OutputPort, al // записать байт в выходной поток
cmp al, ah // равен ли он предыдущему байту?
mov ah, al // этот байт теперь становится предыдущим
jnz Get_from_InputStream // если байты не одинаковы, взять следующий байт
//
in al, Number_of_InputPort // AL = следующий байт из входного потока
mov bl, al // BL = счетчик повторов
mov al, ah // восстановить в AL текущий байт
//
Copy_Byte: //------------------------
//
cmp bl, 0 // есть ли еще повторы байта?
jz Get_from_InputStream // если нет, взять следующий байт
out Number_of_OutputPort, al // записать байт в выходной поток
dec bl // BL = еще один байт скопировали
jmp Copy_Byte // копировать байт дальше
Все, рассказ закончен. Будем полагать, вы осведомлены теперь, а значит подготовлены. Возникни у вас похожая задача, решение готово. Напомню только, что алгоритм эффективен с позиций строгих ограничений, накладываемых на исполняющие аппаратные устройства. Никаких привилегий в степени сжатия он не дает, ибо это всего лишь собрат RLE, который используют ту же самую методику сжатия. Если в RLE за счет принудительного введения поля счетчика оказывается по одному лишнему байту на каждую "запись" для разнобоев, то в Unbuffered RLE этот байт не затрачивается ввиду отсутствия "записей" для разнобоев, но зато каждая "запись" для повторов теперь занимает по 3 байта, и вот здесь затрачивается один лишний байт.