Вначале инициализируется таблица словаря, путём заполнения полей кода значением «–1», что является признаком незаполненности данной позиции словаря. Вслед за этим устройство начинает читать друг за другом байты из входного буфера, постоянно наращивая счётчик прочитанных байтов. Значение первого прочитанного символа присваивается переменной «СТРОКА», а второго – «СИМВОЛ». Производится поиск в словаре последовательности «СТРОКА+СИМВОЛ». Если в словаре такой последовательности не существует, то она (по возможности) заносится в словарь, а в выходной буфер выводится соответствующий ей код. (Последовательности продолжают заносится в словарь до тех пор, пока он не окажется окончательно заполненным. После заполнения словаря коды продолжают выводиться в неупакованном состоянии. Это оказывается более эффективным, чем сброс словаря при таком небольшом объёме данных, так как для удовлетворительного сжатия необходимо наполнение словаря кодами хотя бы на 25%). Далее переменной «СТРОКА» присваивается значение «СИМВОЛ». В случае, если в словаре уже существует последовательность идентичная текущей паре «СТРОКА»+«СИМВОЛ», то в выходной буфер выводится код данной последовательности, а переменной «СТРОКА», как уже говорилось выше, присваивается значение «СИМВОЛ». Далее снова считывается из входного буфера данных значение переменной «СИМВОЛ» и цикл сжатия повторяется до тех пор, пока входной буфер данных не опустеет. После этого в выходной буфер выводится специальный код сигнализирующий об окончании потока данных.
Алгоритм, заложенный в основу программы микроконтроллера, позволяет экономно расходовать ресурсы памяти благодаря особой организации устройства словаря и процедуре хеширования, о которых говорилось выше.
В целях максимально возможного увеличения степени сжатия, в программе сжатия применена процедура вывода кодов переменной длины. Программа постоянно отслеживает количество записей в словаре и выводит только то количество бит кода, которое необходимо для записи данного кода без потери информации. Например: После начала работы программы, длина выводимого кода равна 9 бит. По достижении числа записей 512, программа вставляет в выходной поток специальный код, указывающий на переход к более длинным кодам, и в дальнейшем выводит коды длиной по 10 бит и т. д. до достижения предельно возможной длины кодов в 13 бит.
Так, как и для микроконтроллера, и для компьютера основной единицей информации является байт, в программе применена процедура, организующая сложную систему сдвигов для обеспечения «склеивания» кодов переменной длины в байты.
Если во время сжатия объём выходных данных выходит за пределы 16382 байта, сжатие прекращается, так как вместе со служебной информацией размер данных превысит 16 килобайт, то есть эффект от сжатия будет отрицательным. В этом случае устройство, при организации вывода результатов сжатия, в поле длины пакета (которое занимает первые два байта выходного буфера) поместит 0, что проинформирует программу-клиент о том, что попытка уменьшить объём данных не удалась, и производить дальнейшее чтение данных из регистра данных не нужно. В случае же успешного окончания процесса сжатия, поле длины пакета будет иметь ненулевое значение, что проинформирует компьютер о готовности устройства «отдать» удачно сжатые данные. После этого клиентское ПО производит последовательное чтение байтов данных из выходного буфера данных устройства.
При выполнении программы распаковки сначала считывается первый код из входного буфера данных, а его значение присваивается переменной «СТАРЫЙ КОД». Затем переменной «СИМВОЛ» присваивается значение «СТАРЫЙ КОД», а сам «СТАРЫЙ КОД» выводится в выходной буфер данных. (Согласно алгоритма сжатия первый символ выводится без перекодирования). Вслед за этим начинается основной цикл распаковки, который продолжается до тех пор, пока не будет встречен специальный символ, указывающий на окончание потока сжатых данных.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.