Алгоритм сжатия "Unbuffered RLE"

Алгоритм сжатия "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 задержк