Ну здесь не ГБА, а сега.

Ты мне льстишь. =)

Всякими разными алгоритмам сжатия. =)

Djinn, он наверное имел ввиду саму распаковку У меня была дока на одном форуме, но его база безвозвратно утеряна Там я всё чётко расписывал...

Она?

FFF sql base
user: horror
post: 18

Ломаем LZ77 без экстрим хакинга.

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

  Как известно, все стремяться что-то экономить, будь то деньги, материалы или же свободное место в РОМе. Ведь экономя место, разработчики экономят те самые денежки, порой так извращаясь, что Лемпель-Зив бы в гробу перевернулся . А нам, горе-ромхакерам, приходиться всю эту кашу разгребать. Конечно, хорошо знать такую штутку, как ассемблер, тогда всё нипочём - посмотрел процедуру распаковки, написал прогу и усё. Но что же делать, если мы ентого самого ассемблера не знаем? Ведь на его изучение надо убить не мало времени, да и не каждому дано познать его тайны. Я сам асма не знаю, поэтому каждый раз выкручивался без него. Один раз мне помогли разобраться со сжатием (спасибо Ghost'у ), и я понял, что в этом нет ничего сложного. Алгоритм применяется один, главное разобраться в особенностях каждого случая.

  Начнём с самого простого, как же нам найти место с графикой? Для этого существует древний, как мир, способ - просто поганить блоками РОМ и смотреть на изменения, если изображение изменилось - значит графика находиться в данном блоке. Для этого идеально подойдёт прога Virtual_Killer'а - Поганка. Елси запакован текст, то можно поскать часть самой первой фразы или же самое редко встречающееся слово, например, состоящие только из больших букв.
  Ну, точное расположение начала архива мы установили. Теперь открываем РОМ в hex-редакторе(тем, кто не знает, что это такое, просьба покинуть помещение ), переходим по узнанному нами адресу. А теперь я объясню принцип сжатия на простом примере.

----

Дальше пока не написал.
Но приведу самый простой пример.
{xx} - байт в hex-счислении.

Незапакованный текст:
Этот текст запакован LZ77 алгоритмом. Этот запакован.

Запакованный текст:
{35}{00}{FF}Этот тек{FF}ст запак{FF}ован LZ7{FF}7 алгори{3F}тмом. {26}{05}{20}{09}{01}.

Теперь распакуем этот текст:
1. Читаем первые два байта. {35}{00} - это размер запакованного файла. Он нужен для того, чтобы не распаковать лишнего и вовремя остановиться. В большинестве случаев байты читаем задом наперёд - это особенности процесора.
2. Читаем "управляющий" байт. В нашем случае он равен {FF}.
3. Разбираем его по битам: 11111111. В нашем случае 1 значит просто считать в буфер распаковки один байт, а 0 - считать командный байт(о нём чуть позже).
1 - читаем "Э"
1 - читаем "т"
...
1 - читаем "к"
Командный байт кончился, читаем следующий(GoTo 2)
---
Так доходим до 3F. Разберём его по битам: 00111111.
Что делать с еденицами мы знаем. Что же делать с нулями? Вот тут-то вот и проявляется сжатие. Если мы наталкиваемся на 0, то нам надо прочитать не символ, а командные байт. В нашем случае их два - один отвечает за отсылку назад, а другой - за количество считываемых файлов. У нас это {26} и {05}. 26(hex)=38(dec). Наш буфер: "Этот текст запакован LZ77 алгоритмом. ". Возвращаемся от текущей позиции на 38 символов назад: "Этот текст запакован LZ77 алгоритмом. ". И читаем 5 байт(05 hex=5 dec) подряд:
"[Этот ]текст запакован LZ77 алгоритмом. ". Теперь наш буфер выглядит так: "Этот текст запакован LZ77 алгоритмом. Этот ". Берём следующий бит командного байта, он равен 0. Опять читаем два командный байта и делаем то же самое.
Наш командный байт кончился, берём следующий. Он равен {01}, т.е. 00000001. Соответственно читаем один символ в буфер. Но дальше идёт 7 нулей, то есть они говорят, что надо считать 7 пар командных байт, а текст кончился, что же делать? Для этого и нужен размер файла. Мы знаем, что нужное количество байт уже распаковано и просто прекращаем процесс распаковки.
Надеюсь, объяснил понятно .

Упрощённое объяснение алгоритма распаковки:
1. Читаем размер.
2. Читаем управляющий байт.
3. Читаем бит:
4. Если 1 - читаем символ. GoTo 3.
5. Если 0 - читаем управляющие байты. GoTo 3.
4. Ком. байт кончился - читаем следующий(GoTo 2).