Алгоритм сжатия "Unbuffered RLE" (стр. 1 из 2)
Алгоритм сжатия "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 // и вывести его в выходной поток