Алгоритм стиснення "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 байти, і
ось тут витрачається один зайвий байт.
Список літератури
Для
підготовки даної роботи були використані матеріали з сайту http://www.sciteclibrary.ru
