6502 облегченных алгоритма сжатия

Я реализую виртуальную память на двухкассетных магнитофонах на Commodore PET (ради развлечения) для Форта, который я пишу. То, что у меня есть на данный момент, находится на http://github.com/chitselb/pettil, если вам интересно.

Я планирую использовать собственный 192-байтовый формат файла данных кассеты PET. Ах да, только 32 КБ ОЗУ для всего. Я встроил в язык отличный интерпретатор Sweet-16 от Woz, который очень эффективно использует память.

Блок Forth (обычно) составляет 1024 байта. Добавление двух байтов для идентификатора блока ограничивает доступное виртуальное адресное пространство до 64 мегабайт, что намного больше, чем может поместиться на ленте. Будет колода «воспроизведение» (устройство 1) и колода «запись» (устройство 2), а FLUSH будет включать копирование всей виртуальной памяти с одного диска на другой. Зачем бросаться на ветряные мельницы? Потому что когда-то кассетная лента была тем, что было у большинства владельцев ПЭТ, включая их самих.

Большая часть данных будет экранами кода Forth, который в этой реализации будет состоять из 1000 байтов текста и 24-байтовой таблицы переноса строк, поскольку я также использую экранный редактор PET ROM. То, что я ищу, - это предложения для всего, что (вероятно) превзойдет простое кодирование длины цикла для этой цели, но без накладных расходов ЦП и памяти на что-то столь же сложное, как Lempel-Ziv. Все предложения, кроме «просто забудьте об этом», приветствуются.


person chitselb    schedule 13.09.2013    source источник
comment
Вы можете взглянуть на Кодирование Хаффмана .   -  person Aadit M Shah    schedule 13.09.2013
comment
Я использовал code.google.com/p/lzfx только для распаковки и думаю, вы все равно израсходуете большую часть / все эти 32 КБ, поэтому, вероятно, он недостаточно легкий. но если вы посмотрите на концепцию, а не на реализацию, это длина прогона с некоторой оптимизацией. Если эта строка была обнаружена недавно, а не является набором из одного байта a, одного байта b, одного байта c, то это одна инструкция для копирования N байтов с адреса current-X.   -  person old_timer    schedule 13.09.2013
comment
Где-то здесь, в stackoverflow, есть вопрос и ответы для легкого встроенного сжатия. у которого были другие красивые предложения.   -  person old_timer    schedule 13.09.2013
comment
@dwelch: вы имели в виду этот?   -  person Seki    schedule 13.09.2013
comment
Вы можете использовать закодированное слово с поиском по словарю, если у вас много строк повторяющихся последовательностей. Он прост в реализации, быстр и прекрасно работает с различными типами текста, если он состоит из различных общих последовательностей строк. Идея состоит в том, чтобы посмотреть на данные и понять, где есть избыточность, и воспользоваться этим. Lempel-Ziv тяжелый, потому что он предназначен для хорошей работы в общем случае с различными типами данных. В этом случае у вас есть очень специфический тип данных, которыми вы можете воспользоваться.   -  person lurker    schedule 13.09.2013
comment
Как лечится Форт? Мне кажется, что вы можете хранить словарь Forth и определять текст без комментариев, просто ссылаясь на него — точно так же, как большинство микрокомпьютеров хранят свой Бейсик на кассете в токенизированной форме.   -  person Tommy    schedule 14.09.2013


Ответы (1)


Если вас больше всего беспокоит исходный код Forth, вы можете ограничить набор символов 48, выбранным Чаком Муром для colorForth, и использовать его схема кодирования Шеннона, которая дает в среднем 5,2 бита на символ. Он также утверждает, что исходный код colorForth примерно в два раза превышает размер объектного кода. Кстати, похоже, что набор символов в arrayForth немного отличается (см. стр. 47 Руководства пользователя - другой порядок цифр, апостроф вместо двоеточия и т.д.).

Использование кодирования Шеннона, конечно, не обязательно имеет отношение к цветным словам. Если вы хотите пройти весь путь и сохранить предварительно проанализированные слова, как в colorForth, вы можете использовать его схема здесь.

Он не сообщает подробностей, но для etherForth он отказался от кодировки Шеннона и использовал простую 6-битную кодировку. для того же набора символов с 11xxxx, дополнительно указывающим на 16-битный тег, который он использует для цветов и токенов, включая инструкции F18 и несколько примитивов ассемблера (начало, конец, затем, для). Это действительно очень крутая схема (особенно на 18-битном F18 с местом для 3 на слово). Предельно простой и достаточно компактный.

Во всяком случае, есть некоторые идеи. Не совсем прямой ответ на ваш вопрос о сжатии, но некоторые способы хранения исходного кода Forth в хорошо сжатом виде. Радоваться, веселиться!

person AshleyF    schedule 13.09.2013
comment
Целью является создание стандартного Форта, который был разработан специально для оборудования Commodore PET, используя набор символов PETSCII и любые подпрограммы встроенного ПЗУ везде, где это возможно. Он будет работать на ПЭТ с ПЗУ 1.0, обновления или 4.0 BASIC и, при желании, может быть целевым образом скомпилирован в (неиспользуемое в заводском ПЭТ) адресное пространство от $9000 до $AFFF. - person chitselb; 17.09.2013