С хаффманом сжимает на 22 байта лучше. Хотя это возможно потому, что я максимально использовал все коды. В оригинале, если мне не изменяет память. Несколько последних кодов не использовалось. Я же это учёл. Т.е. в таблице у меня всё место занято за исключением кодов FC, FD, FE, FF.

Ещё немного подшаманил. Теперь ещё лучше сжимает. До 4347 байт с учётом заголовка.
Плюс написал распаковщик.

Посмотрю на досуге, чтобы залить на сайт.
Возможно понадобится немного "прилохматить".

А это не кодекс, это сжатый файл для сравнения.

Давай уж кодеК)

Решил я сегодня до ума довести codec и приключилась со мной одна неприятная ситуация.
Я уже заканчивал доработку и решил проверить напоследок, что кодек работает правильно.
Начал делать распаковку и тут ошибка вылезла. Нарущение доступа и т.п.



Ну, думаю, что за фигня? Я же не менял код, а только обратил внимание на warning'и и устранил их. Более получаса, наверно, потратил, чтоб найти ошибку.
Оказалось ошибка здесь. Вот он мне писал:



И тогда я добавил такую строчку, чтобы проинициализировать переменную.



И после этого началась вся эта свистопляска. Вот уж не подумал бы, что из-за могло что-то нарушиться.

Вот.

Императивопроблемы.
Ни разу не дебажил программу на Хаскелле. При этом из самого сложного могу вспомнить МТЕ/LZ под Megal Gear на GBC и упаковщик по Kirby, который жмет даже эффективнее exhal'а .
До твоего хаффмана в Jewel Master у меня тоже руки дойдут

Что с первого раза у тебя упаковщик начинает работать?
Я сколько бы ни писал компрессоров, всегда что-нибудь упущу. Соответственно приходиться трассировать код, как без этого.

Программа на функциональном языке - не последовательность команд. А ленивость делает трассирование вообще бессмысленным.
Сам процесс написания отличается - в Хаскелле ты открываешь REPL и пишешь однострочные функции, которые возвращают тебе то, что надо, а потом компонуешь уже заведомо работающие.
Из-за строгой типизации Хаскелля ты не сможешь скомпилировать код, в котором что-то забыл. Если код успешно скомпилировался, и при этом делает не то, что ты задумал, значит ты сказал ему конкретно делать так. Это устраняется прочтением своих функций (благо, код высокоуровневый и его получается немного), а в крайнем случае, просто вызываешь функции из REPL'а и находишь, какая из них возвращает не то, что надо.

Интересно. Я когда-то скачивал книги о Хаскелл, но руки не дошли. Так что перефразирую тебя: до твоего хаскелла у меня тоже руки дойдут.

Ты ещё, кстати, не начал писать пакет к Star trek'у? Там довольно интересный алгоритм, как раз как ты любишь.
Я когда-то разбирал, но все мои потуги остались на не рабочем диске.

Уже написал Схема сжатия интересная, но алгоритм оптимальной упаковки довольно тривиален. Конечно, не Кирби.

Там, если не ошибаюсь, нужно много вариантов выбирать, каким способом лучше сжать.

Да, но каждый кандидат либо исключает других кандидатов, либо заведомо имеет меньшую стоимость, поэтому на каждом шаге ты сразу точно можешь сказать, какой из кандидатов оптимален и выбрать его.
Нет головной боли с оптимальным LZ парсингом.

Спасибо, Marat. По всей видимости, ты прав. Это алгоритм с префиксными кодами, который может быть улучшен Хаффманом.
Обновил readme для своего инструмента со ссылкой на эту ветку форума.

Оказывается это сжатие используется также в игре Phantasy Star 2: Anne's adventure, ну и скорее всего в остальных частях.
Предыстория:
Где-то примерно год назад ко мне обратился товарищ Lin1985, и попросил помочь с переводом данной игры. Ему требовалась помощь в перерисовки шрифта. Я написал ему утилитку, и он ушёл переводить.)

И вот спустя год ему снова потребовалась помощь в нахождении шрифта и перерисовки надписи Phantasy Star в меню.
Я начал изучать код и мне показалось, что где-то это я уже видел, что-то знакомое. Но никак не мог вспомнить где. Тогда я решил прошерстить все свои исходники декомпрессоров, но искал я только в исходниках, с RLE кодом. А так как я помнил, что в Jewel Master используется Хаффман, то не заглядывал в его исходник. Просмотрев несколько раз свои исходники, я пришёл к выводу, что, скорее всего, это было давно и код распаковщика, если когда-то я что-то писал похожее, утерян. С это мыслью я взялся за подробное изучение кода распаковки. Всё это осложнялось тем, что часть кода разработчики запихали в область RAM( причём там тупо идут прыжки на код в роме. Я так и понял суть таких манипуляции. Что интересно 8 кб данных и кода копируются в память RAM перед началом игры и читаются и исполняются из RAM). А ни IDA, ни дебаггер Шеллоский не показывают выполнение команд в RAM. Из-за этого IDA не может построить дерево кода распаковки. Так или иначе я разобрался с процедурой распаковки и пришло время писать компрессор. Начал прикидывать, как я буду это делать. Сразу подумал о том, что надо перед началом сжатия, произвести подсчёт кол-ва появлений RLE-nibble'a. Как я буду распределять длину кода для каждого ниббла и как оно будет распределяться в таблице вероятности. И ровно в этот момент, у меня всплыла в голове это тема на форуме, и ток, как Гривер описывал сжатие, и про его LookUpTable в 256 байт, и то как я доказывал Гриверу, что это здесь используется дерево Хаффмана. Сразу полез в код распаковщика Jewel Master'a и убедился, что это и есть тот самый код распаковки из игры. Так что теперь мне даже не надо писать код компрессора). Жаль только, что я его сразу не нашёл. Вот такая вот история.

Ну там и разработчик один и годы релизов рядом, небось, и код распаковщиков совпадает, если не учитывать оффсеты

Возможно, но я не помню чтобы мне попадалось, чтобы код программы выполнялся в ОЗУ, кроме пересылки DMA.