Алгоритм сжатия "Unbuffered RLE"
    Дмитрий Сахань
    Контакт с автором: www.aimatrix.nm.ru
    Хочешь совершенства - создай его своими руками. (AIMatrix)
    Возникла у меня задача использовать сжатие по методу RLE. Одним из важных условий было жесткое ограничение в исполняемом механизме, что проще можно сформулировать как отсутствие лишних ячеек памяти плюс выделение кодировщику недопустимо малого количества регистров процессора. Грубо говоря, все выглядело так, как если бы в окончательном варианте кодировщик работал внутри примитивного аппаратного устройства, собранного на базе не менее примитивного микропроцессора. Причем желательно было сразу найти такое решение, в котором устройство не содержало бы вообще памяти (как пример, на плате остается только один микропроцессор), а сам процессор чтобы был ну чуть ли не I8008 (один из первых микропроцессоров фирмы Intel, разработанный в 70-х годах прошлого века). На вход устройство побайтно принимает байты входного незакодированного потока, а на выход сбрасывает байты уже RLE-закодированного потока.
    Несмотря на давнишнее рождение RLE как алгоритма сжатия несложных изображений и его нынешнюю неэффективность в свете сложности (обилие мелких деталей, высокие битовые глубины) современных изображений, все-таки и сегодня существует класс приложений, где использование RLE более оправдано, нежели применение других алгоритмов. Оправданием служит простота алгоритма RLE, а значит уменьшаются финансовые (впрочем, как и аппаратные) затраты на исполняющие блоки некоторой контролирующей системы. Ну, допустим, такой пример. В одном помещении находится светодиодно-фотодиодный приемник, сканирующий движущуюся перед ним бумажную ленту с нанесенными на нее вертикальными черными полосами разной ширины (что-то в духе непрерывного штрих-кода). По кабелю вся последовательность отсканированных сигналов направляется в другое помещение, на следящую систему. Можно отправлять сигналы как не сжатый поток, но можно ведь, сжимая предварительно поток, уменьшить нагрузку на транспортную магистраль. Вот здесь и появляется дилемма: то ли увеличивать стоимость и сложность приемника (ибо как раз на его стороне должно выполняться сжатие), то ли отказаться от сжатия в принципе. И если сжатие будет достигнуто ценой дешевого усовершенствования считывающего приемника, то дилемма решаема в положительную сторону.
    Однако в чистом виде RLE не обеспечивает полного удешевления конструкции приемного устройства. Давайте вспомним, как работает RLE. Из входного потока извлекается байт. Если он был равен предыдущему извлеченному байту (соседние байты одинаковы), тогда просто увеличивается на 1 внутренний счетчик повторов для данного байта, а в выходной поток пока ничего не сбрасывается. Как только новый извлеченный из входного потока байт отличается от предыдущего байта, в выходной поток выбрасывается СЧЕТЧИК повторов, а затем ПОВТОРЯВШИЙСЯ байт. Теперь уже начинает увеличиваться на 1 внутренний счетчик неодинаковых байт (разнобоя). Когда же во входном потоке снова будет встречен фрагмент из одинаковых байт, тогда в выходной поток будет сброшен СЧЕТЧИК разнобоя, а за ним целиком вся ПОСЛЕДОВАТЕЛЬНОСТЬ неодинаковых байт. На следующем рисунке для наглядности изображено некоторое условное содержимое входного и выходного потоков (разнобои выделены красным цветом, повторы - зеленым, синим цветом в выходном потоке обозначены поля счетчиков). ............