Список форумов www.shedevr.org.ru www.shedevr.org.ru
Группа перевода приставочных игр "ШЕДЕВР"
 
 FAQFAQ   ПоискПоиск   ПользователиПользователи   ГруппыГруппы   РегистрацияРегистрация 
 ПрофильПрофиль   Войти и проверить личные сообщенияВойти и проверить личные сообщения   ВходВход 

[Документация] Архивы и алгоритмы сжатия
На страницу 1, 2, 3, 4  След.
 
Начать новую тему   Ответить на тему    Список форумов www.shedevr.org.ru -> Экстремальный ромхакинг
Предыдущая тема :: Следующая тема  
Автор Сообщение
HoRRoR
RRC2008
RRC2008


Зарегистрирован: 21.06.2006
Сообщения: 2341
Откуда: Ростов-на-Дону

СообщениеДобавлено: Вс Ноя 04, 2007 12:21 pm    Заголовок сообщения: [Документация] Архивы и алгоритмы сжатия Ответить с цитатой

Давно я хотел написать доку по алгоритмам сжатии, и просьбы в теме раздела PSX побудила меня выложить свои "труды" Smile Заодно и опишу для новичков алгоритм определения структуры архива...

--

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

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

Начнём с самого простого, как же нам найти место с графикой или текстом? Для этого существует древний, как мир (ну или почти как мир Smile ), способ - просто поганить блоками файл и смотреть на изменения, если данные исказились - значит они находятся в данном блоке. Для этих целей прекрасно подойдёт программа Vitrual_KillerПоганка, или её модифицированный римейк от BHLady. Если запакован именно текст, то можно поскать часть самой первой фразы или же самое редко встречающееся слово, например, состоящие только из больших букв (обычно в LZ77-подобных алгоритмах первые фразы не попадают под паковку, наполняя буфер, а слова из букв большого регистра встречаются редко, поэтому тоже не пакуются).
Второй способ более простой, но требует определённых навыков. Просто берём дебаггер, ждём, пока появится нужная картинка/фраза, идём в память, ищем её там и ставим бряк либо на запись в то место, либо на условие равенства того места текущему значению. Перезапускаем игру и когда брякнется либо анализируем код, ища присвоение исходного адреса, либо же просто идём и смотрим по адресам всех регистов, значения которых в пределах адресного пространства РОМа данной платформы. Описывать подробно этот способ я не буду, т.к. у тех, кто знаком с дебагом, вопросов не возникнет Smile В общем, ипровизируем Wink Ромхакинг по сути и есть импровизация...

Ну, точное расположение начала архива мы установили. Теперь открываем файл в hex-редакторе(тем, кто не знает, что это такое, просьба покинуть помещение Smile ), переходим по узнанному нами адресу. А теперь я объясню принципы сжатия на простых примерах.

----

LZ77

Основой этого алгоритма является замена повторяющихся блоков байт на один или несколько байт, в которых просто содержится информация о том, откуда и сколько байт повторить. Т.е. вместо повторяющегося блока будет просто пара байт, которые указывают на такой же блок и говорят его длину.

Рассмотрим это на примере:

{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 пар командных байт, а текст кончился, что же делать? Для этого и нужен размер файла. Мы знаем, что нужное количество байт уже распаковано и просто прекращаем процесс распаковки.

Чтобы было понятней, распишу так:
11111111 11111111 11111111 11111111 111111___0_______0____ 10000000
Этот_тек_ст_запак_ован_LZ7_7_алгори_тмом._{26}{05}{20}{09}_.
Т.е. я просто сопоставил каждому биту управляющего байта соответствующий байт или пару байт. Т.е. биту 1 сопоставлен байт, который считывается, а биту 0 пара байт с отсылкой и количеством считываемых байт.


Упрощённое объяснение алгоритма распаковки:
1. Читаем размер.
2. Читаем управляющий байт (разбирающийся по битам).
3. Читаем бит:
4. Если 1 - читаем символ. GoTo 3.
5. Если 0 - читаем командные байты (ссылка и количество читаемых байт). GoTo 3.
6. Управляющий байт кончился - читаем следующий(GoTo 2).
И во время всей этой процедуры не забываем проверять размер Smile Если он уже равен указанному - то прекращаем распаковку.
_________________
Работаю за деньги
KILL ALL HUMANS!!!!!111


Последний раз редактировалось: HoRRoR (Вт Апр 28, 2009 9:11 pm), всего редактировалось 8 раз(а)
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail Посетить сайт автора
HoRRoR
RRC2008
RRC2008


Зарегистрирован: 21.06.2006
Сообщения: 2341
Откуда: Ростов-на-Дону

СообщениеДобавлено: Вс Ноя 04, 2007 12:21 pm    Заголовок сообщения: RLE Ответить с цитатой

RLE

На этом алгоритме мы особо останавливаться не будем, т.к. он очень прост как в плане понимания, так и в плане реализации. Разновидностей его существует множество(кстати существую даже алгоритмы, где могут содержаться сразу несколько методов сжатия, например, RLE+LZ77), но я приведу самый простой пример.

В основном RLE применяют для сжатия графики, т.к. его принцип - это замена подряд идущих одинаковых байт на один такой байт и значение, в котором говорится их количество (обычно 1-2 байта). Сами понимаете, текст им ужимать бесполезно :)

Пример.

Исходный текст:
Вооооооот нееееее наааааадо тоооооормозиииииить.

Запакованный текст:
В{00}{07}от н{00}{06}е н{00}{06}адо т{00}{06}ормоз{00}{06}ить.

Сразу хочу отметить, что для большей простоты я привёл пример неструктурированного архива, т.е. в нём не наблюдается чёткой структуры, а просто есть сигнализирующий о применении сжатия байт (в нашем случае это {00}). Кстати именно байт я привёл тоже для простоты, иногда это может быть, например, старший бит в байте. Так что разновидность алгоритма может быть любой, но принцип остаётся прежним.

Теперь распакуем этот текст:
1. Считываем байт. Если он не равен {00}, то читаем дальше, а если равен, то переходим к пункту 2.
2. Читаем следующий байт, у нас первым таким байтом будет {07}. Читаем байт, идущий за ним. Это о. Повторяем о 7 раз. Переходим к пункту 1.
Вот и всё Smile
_________________
Работаю за деньги
KILL ALL HUMANS!!!!!111


Последний раз редактировалось: HoRRoR (Сб Мар 15, 2008 11:57 pm), всего редактировалось 4 раз(а)
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail Посетить сайт автора
HoRRoR
RRC2008
RRC2008


Зарегистрирован: 21.06.2006
Сообщения: 2341
Откуда: Ростов-на-Дону

СообщениеДобавлено: Вс Ноя 04, 2007 12:22 pm    Заголовок сообщения: Ответить с цитатой

Huffman

Этот алгоритм довольно эффективен при сжатии текста, т.к. не имеет значения, в каком порядке расположены байты в файле.
Принцип состоит в том, что составляется так называемое дерево. В нём содержатся кодируемые символы, и продвигаясь вглубь по этому дереву, будет составляться блок бит, кодирующий этот самый символ. Символы, встречающиеся чаще, расположены ближе к "верхушке" этого самого дерева, т.к. в кодированном виде они будут занимать меньшее количество бит. Но легче понять это будет на примере.

Текст:
Группа_переводов_"Шедевр".

Встречаемые символы и частота встречаемости:
Г - 1
р - 3
у - 1
п - 3
а - 1
_ - 2
е - 4
о - 2
д - 2
в - 2
" - 2
Ш - 1
. - 1

Теперь сортируем по частоте встречаемости:
е, р, п, _, о, д, в, ", Г, у, а, Ш, .

Теперь нам необходимо составить дерево. Для этого нужно грамотно расположить символы, чтобы всё получилось оптимально. Сразу предупреждаю, что тут целью оптимально составить дерево я не задавался, делал как быстрее и понятней Smile
Сперва разделим дерево на две ветви, т.к. первый бит всегда либо 1, либо 0, т.е. есть два варианта.
Слева у нас будет 0, а справа 1:
Код:

     Дерево
     /    \
    0      1


Далее разветвляем каждую ветвь на две части:
Код:

     Дерево
     /    \
    0      1
   / \    / \

На одно ответвление можно либо "повесить" байт, либо продолжить его.
Так что теперь мы можем каждое это ответвление либо продолжить, либо закончить символов. Чем выше расположен символ, тем меньше бит он занимает, поэтому может показаться, что стоит сразу вешать символы как можно выше. Но продолжив разветвление, на более низких уровнях мы сможем получить больше символов (больше веток - больше листьев), и, если сделать всё с умом, то в самом низу станет меньше символов:
Код:

     Дерево
     /    \
    0      1
   / \    / \
  0   1  0   1
 / \ / \/ \ / \

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

Вот мы и составили дерево:
Код:

     Дерево
     /    \
    0      1
   / \    / \
  0   е  р   1
 / \        / \
п   1      0   _
   / \    / \
  0   о  д   1
 / \        / \
в   1      0   "
   / \    / \
  0   Г  у   1
 /          / \
а          .   Ш


А теперь посмотрим на запакованный текст:
001011 10 110100 000 000 0010100 111 000 01 10 01 00100 0011 1100 0011 00100 111 11011 1101011 01 1100 01 00100 10 11011 1101010

Т.е. в общем текст будет выглядеть так:
00101110 11010000 00000010 10011100 00110010 01000011 11000011 00100111 11011110 10110111 00010010 01011011 11010100

Или так:
{2E}{D0}{02}{9C}{32}{43}{C3}{27}{DE}{B7}{12}{5B}{D4}

Но с учётом того, что нам нужно ещё как-то сохранить и дерево, то алоритм эффективен либо не с такими маленькимми текстами, либо же если заранее составленное дерево есть в самом архиваторе.

Теперь попробуем распаковать наш текст:

Читаем бит, смотрим на дерево. Если там следующий бит, то идём дальше, если же байт, то читаем байт и идём дальше.

Например, 00101110 - читаем 0, смотрим на дерево - с него начинается левая "ветка". У нас есть два варианта - пойти налево (0), или направо (1). Читаем следующий бит - 0, идём налево, там нет символа, значит не останавливаемся. Читаем 1 - идём направо. Там тоже нет символа. Читаем 0 - идём налево, символа. Читаем 1, направо - символа нет. Опять один, опять направо - натыкаемся на "Г". Добавляем этот символ в наш распакованный текст и идём на верхушку дерева, но следующий бит мы берём сразу же тот, который следует далее.
_________________
Работаю за деньги
KILL ALL HUMANS!!!!!111


Последний раз редактировалось: HoRRoR (Вс Мар 16, 2008 12:01 am), всего редактировалось 4 раз(а)
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail Посетить сайт автора
HoRRoR
RRC2008
RRC2008


Зарегистрирован: 21.06.2006
Сообщения: 2341
Откуда: Ростов-на-Дону

СообщениеДобавлено: Вс Ноя 04, 2007 12:24 pm    Заголовок сообщения: Ответить с цитатой

Определение структуры архивов

Для начала разберём, что такое архив.
Архив - это файл, в котором содержится некоторое количество других файлов, при этом они вовсе необязательно должны быть сжаты. Делается это либо для удобства и быстродействия (попробуйте поработать с несколькими десятками тысяч файлов в одной папке Smile), либо для экономии места (если данные ужимаются - то понятное дело для экономии, но если нет - то место тоже экономится, т.к. в кластерных файловых системах файлы с размером не кратным размеру кластера будут занимать немного больше места - ровно столько, сколько занимали бы, если бы их дополнить так, чтобы их размер всё-таки стал кратен размеру кластера).

Итак, у нас есть архив:

Код:

00000000: 5041434B B0000000 30000000 02000000 PACK°...0.......
00000010: 30000000 2C000000 46494C31 2E584D4C 0...,...FIL1.XML
00000020: 60000000 43000000 46494C32 2E545854 `...C...FIL2.TXT
00000030: 3C584D4C 3E206874 74703A2F 2F636F6E <XML> http://con
00000040: 736F6C67 616D6573 2E6A696E 6F2D6E65 solgames.jino-ne
00000050: 742E7275 2F203C2F 584D4C3E 00000000 t.ru/ </XML>....
00000060: 68747470 3A2F2F73 68656465 76722E6F http://shedevr.o
00000070: 72672E72 752F202D 20E3F0F3 EFEFE020 rg.ru/ - группа
00000080: EFE5F0E5 E2EEE4E0 20EFF0E8 F1F2E0E2 перевода пристав
00000090: EEF7EDFB F520E8E3 F02022D8 E5E4E5E2 очных игр "Шедев
000000A0: F0222E00 00000000 00000000 00000000 р"..............


Сначала хочу напомнить, что значения в файлах хранятся в обратном порядке, т.е. значение 002D2E2F будет выглядеть как 2F2E2D00, а два значения подряд 0102 и 0304 будут выглядеть как 02010403.
Сначала нам нужно определить заголовок, и отделить его главную часть. Мы видим, что первая строка выделяется от остальных - это и есть главная часть заголовка. Смотрим дальше - идут две строки с именами файлов, а дальше само содержимое этих файлов. Очевидно, это два подзаголовка, принадлежащих этим файлам.
Рассмотрим главную часть заголовка:
Мы видим четыре символа - PACK. Они нам не нужны, просто информация о содержимом.
Прежде всего обычно в архивах указывается размер всего файла. У нас он равен B0. Попробуем его найти. Он действительно есть и находится по адресу $04. Но для распаковки он нам не нужен, зато мы уже знаем два элемента заголовка - подпись и размер файла.
Смотрим далее - $00000030. Что же у нас может быть $30? Думает... Ага! Это размер всего заголовка! Ну или адрес первого файла, но если подумать, то это именно размер заголовка.
Следующее значение $02, ну просто 2 то бишь. Хм... Файлов у нас тоже всего два. Всё ясно! Это количество файлов. Вот и разобрали мы главную часть заголовка Smile
Теперь перейдём к подзаголовкам файлов. Ну с правыми восемью байтами всё ясно - это имена файлов. Надо разобрать левые 8 байт.
Что нам надо знать для извлечения файла из архива? Правильно, его положение и положение его конца или его размер. Смотрим на положение первого файла - $30. Ага, в подзаголовке оно идёт первым, значит первые четыре байта подзаголовка - это смещение файла.
Посчитаем его размер - тоже $30. Но оставшееся значение у нас $2C. Странно... Смещение его конца - $60, но это тоже не подходит... А что если взять первые $2C байт файла? Точно! Отсекутся ненужные нули. Значит это значение - ничто иное, как размер файла.
Распаковав архив, мы получим два файла: FIL1.XML и FIL2.TXT
Содержимое FIL1.XML:
<XML> http://consolgames.jino-net.ru/ </XML>

Содержимое FIL2.TXT:
http://shedevr.org.ru/ - группа перевода приставочных игр "Шедевр".

Всё, архив разобран, но это было самое простое, что моя фантазия могла породить Smile
Архивы могут содержать папки, там необязательно будут указаны имена файлов, смещение их конца или размер (в таких случаях они обычно высчитываются от положения следующего файла), у файлов/папок могут быть параметры, могут быть дополнительные значения, которые используются только игрой и т.д. и т.п. Всё это разбирается методом анализа, т.к. в основном каждый случай - уникальный, и в разных случаях эти данные будут храниться по-разному.
_________________
Работаю за деньги
KILL ALL HUMANS!!!!!111


Последний раз редактировалось: HoRRoR (Вс Мар 16, 2008 12:04 am), всего редактировалось 5 раз(а)
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail Посетить сайт автора
HoRRoR
RRC2008
RRC2008


Зарегистрирован: 21.06.2006
Сообщения: 2341
Откуда: Ростов-на-Дону

СообщениеДобавлено: Вс Ноя 04, 2007 12:25 pm    Заголовок сообщения: Ответить с цитатой

Примеры

Рассмотрим для примера архивы и алгоритмы сжатия в некоторых играх.
Для примера архива и LZ77 возьмём Final Fanasy [PSP], а для примера Хаффмана возьмём Silent Hill: Play Novel [GBA].

Итак, структура dpk-архива в игре Final Fantasy

Возьмём кусочек заголовка:
Код:

00000000: F1070000 401D2408 00000000 00000000 с...@.$.........
00000010: 53453030 302E4E50 4B000000 00000000 SE000.NPK.......
00000020: 00000000 00003F02 40D73E05 50C90300 ......?.@Ч>.PЙ..
00000030: 50C90300 53453030 312E4E50 4B004B00 PЙ..SE001.NPK.K.
00000040: 00000000 00000000 00004002 50A42E03 ..........@.P¤..
00000050: 90FE0000 90FE0000 53453031 302E4E50 ђю..ђю..SE010.NP
00000060: 4B004B00 00000000 00000000 00004002 K.K...........@.
00000070: 8043CF03 30A60000 30A60000 53453130 ЂCП.0¦..0¦..SE10
00000080: 302E4E50 4B000000 00000000 00000000 0.NPK...........

Как мы уже знаем, нам надо выделить главную часть заголовка (если она есть). Отчётливо выделяется первые 16 байт. Очевидно, это она и есть.
Теперь разберём её:
$000007F1 - это количество файлов в архиве.
$08241D40 - размер архива.
Оставшиеся 8 байт просто не используются или могут использоваться, но пустые. В любом случае, они нам не нужны.

Теперь разберём оставшуюся часть заголовка. Мы видим, что под заголовок каждого файла отведено 36 байт. Разберём заголовок первого файла:
Сразу видно, что сперва идёт имя файла. Оно занимает 22 байта, {00} означает окончание имени. Символы после {00} в пределах 22 байт - просто остатки от прежних имён (просто новые более короткие имена записаны поверх старых), другими словами - мусор. Не обращаем внимания, можно без угрызения совести этот мусор удалить.
Имя первого файла у нас SE000.NPK, сразу после имени идёт $23F. Это либо параметры файла, либо что-то ещё. В любом случае, это значение нам не нужно, бессовестно проигнорируем его при распаковке, а при сборке архива мы просто вернём эти значения назад.
Далее идёт значение $053ED740 - это смещение файла, ну адрес в архиве то бишь.
Затем идёт два значения $3C950. Это оба значения - размеры файлов. Но почему же их два? Ответ: т.к. в этом архиве используется сжатие файлов, то первый размер говорит нам о размере запакованного файла, а второй - о размере распакованного. Т.е. по сути нам нужен первый размер, т.к. каким бы файл не был, запакованным или распакованным, размер его в архиве от этого не изменится. У нас они одинаковые, это значит, что файл просто-напросто не запакован (в некоторых архивах в таких случаях ставят вместо размера распакованного файла 0).
Вот мы и разобрали формат dpk-архива из игры Final Fantasy.
Теперь разберём сжатие, использующееся в этой игре.



LZ77-алгоритм сжатия в игре Final Fantasy

Для примера возьмём файл FM_SHOPUS.PCK.
Данный алгоритм оперирует данными типа Word, т.е. парами байт, но управляющие биты содержатся в 4-х байтах, т.е. в данных типа DWord (Double Word).
Для начала разберём заголовок. В нашем случае его размер 8 байт, причём первые 4 байта - подпись архива "Wp16", а вторые 4 байта - размер распакованных данных. Сразу открою маленький секретик - во всех запакованных и незапакованных файлах в dpk-архиве содержатся точно такие же dpk-архивчики Smile Вот мы сейчас один такой и распакуем...

Код:

00000000: 57703136 30260000 F77BBFF7 06000000 Wp160&..ч{їч....
00000010: 30260301 4B45595F 4558502E 4D534700 0&..KEY_EXP.MSG.
00000020: 63024A03 601D0000 73054100 4A4F425F c.J.`...s.A.JOB_
00000030: 4E414D45 2E4D5347 A3047003 B01C0000 NAME.MSGЈ.p.°...
00000040: F849D500 F849D500 20010000 30303030 шIХ.шIХ. ...0000
...


{57}{70}{31}{36} {30}{26}{00}{00} - это у нас заголовок, его мы разобрали, идём дальше.
{F7}{7B}{BF}{F7} {06}{00}{00}{00} - а тут присмотримся повнимательней.
Как я уже говорил, значения в файлах хранятся в обратном порядке, поэтому и значения с управляющими битами чаще всего хранятся именно так. Тут тоже такой случай. Значит у нас получается значение $F7BF7BF7, разберём его по битам:
11110111 10111111 01111011 11110111
В этом случае 1 - просто считать Word в буфер, а 0 - повторить. Но ещё одна особенность этого случая - биты читаются справа-налево, т.е. от младшего к старшему в обратном порядке.
Итак, справа у нас подряд идёт три единицы, считываем три Word'а:
0600 0000 3026

Далее у нас 0, читаем Word с отсылкой и количеством читаемых Word'ов. У нас это $0103. Вроде бы всё просто, но... Тут разделение по значением устроено немного сложнее, чем просто по байтам. Дело в том, что за отсылку у нас отвечают старшие 11 бит, а за количество читаемых пар байт - оставшиеся 5 бит.
Разберём по битам:
00000001 00000011
Перегруппируем:
00000001000 00011 = 8 и 3.
Т.е. получается, что количество читаемых пар байт у нас 3, а отсылка назад - 8 пар байт. Но ведь это же за пределами начала файла! Вот очередная особенность этого алгоритма - если ссылка на данные перед началом буфера, то ничего не читается, а просто в буфер добавляются нулевые Word'ы. Вроде бы как их надо добавить 3, но опять особенность - т.к. не имеет смысла применять сжатие, если длина блока меньше трёх пар байт, то количество читаемых пар байт 0 у нас будет означать 2. Т.е. количество = количество + 2. Получается 5 Word'ов. И все они в аккурат перед началом буфера, значит у нас получается ровно пять нулевых Word'ов. Пишем их в буфер:
0600 0000 3026 0000 0000 0000 0000 0000

Далее у нас идёт шесть единиц, читаем 6 Word'ов в буфер:
0600 0000 3026 0000 0000 0000 0000 0000
4B45 595F 4558 502E 4D53 4700


Затем у нас опять идёт ноль. Что-ж, читаем Word компрессии. На этот раз это $0263.
$0263 = 00000010011 00011 = 19 и 3+2 = 19 и 5.
Как ни странно, этот Word по функциональности идентичен первому. "Читаем" столько же с того же "места":
0600 0000 3026 0000 0000 0000 0000 0000
4B45 595F 4558 502E 4D53 4700 0000 0000
0000 0000 0000


Четыре единицы - читаем 4 Word'а:
0600 0000 3026 0000 0000 0000 0000 0000
4B45 595F 4558 502E 4D53 4700 0000 0000
0000 0000 0000 4A03 601D 0000 7305


Читаем Word компрессии:
$0041 = 00000000010 00001 = 2 и 1+2 = 2 и 3. Т.е. отступаем назад на 2 и читаем 3 Word'а:
0600 0000 3026 0000 0000 0000 0000 0000
4B45 595F 4558 502E 4D53 4700 0000 0000
0000 0000 0000 4A03 601D 0000 7305 0000
7305 0000


В общем, продолжаем в этом духе. По исчерпыванию всех 32-х бит, читаем следующие 32 бита на той позиции, на которой остановились. Вот у нас получился распакованный файл:

Код:

00000000: 06000000 30260000 00000000 00000000 ....0&..........
00000010: 4B45595F 4558502E 4D534700 00000000 KEY_EXP.MSG.....
00000020: 00000000 00004A03 601D0000 73050000 ......J.`...s...
00000030: 73050000 4A4F425F 4E414D45 2E4D5347 s...JOB_NAME.MSG
00000040: 00000000 00000000 00007003 B01C0000 ..........p.°...
00000050: AB000000 AB000000 53484F50 5F4D5347 «...«...SHOP_MSG
00000060: 2E4D5347 00000000 00000000 00009503 .MSG..........•.
...


Вот мы и разобрали живой пример LZ77.

Huffman в игре Silent Hill: Play Novel

Дерево Хаффмана построено в этой игре, на мой взгляд, довольно оригинально. Хотя, других я не видел, если честно.
Для начала разберём общий формат хранения текста. Для примера возьмём первый блок по смещению $0053E908.

Заголовок состоит из 16 байт. Сперва идёт подпись $10 - первые четыре байта. Сл. 4 байта - относительное смещение блока поинтеров (поинтеры 3-х байтовые, но разговор сейчас не о них), далее - количество поинтеров и 4 пустых байта.
Проще говоря:
Sign: DWord; // Подпись = $10
PtrsPos: Dword; // Смещение блока поинтеров
PtrsCount: DWord; // Количество поинтеров
Null: DWord; // 0
Код:

0053E908: 10000000 A0180000 10270000 00000000 .... ....'......


А вот далее идёт самая нужная нам часть - дерево Хаффмана.
Код:

0053E918: FFFFFFFF FFFF0000 10000000 200D0000 яяяяяя...... ...
0053E928: FFFFFFFF FFFF0000 20000000 10050000 яяяяяя.. .......
0053E938: FFFFFFFF FFFF0000 30000000 E0020000 яяяяяя..0...а...
0053E948: FFFFFFFF FFFF0000 40000000 F0010000 яяяяяя..@...р...
0053E958: FFFFFFFF FFFF0000 50000000 80000000 яяяяяя..P...Ђ...
0053E968: FFFFFFFF FFFF0000 60000000 70000000 яяяяяя..`...p...

Оно состоит из множества элементов. По сути, структура каждого элемента такова:
Teg1: Индикатор/Распакованный байт - 4 байта
Teg2: Неиспользуемая часть - 4 байта
Bit0: Смещение при бите, равном 0 - 4 байта
Bit1: Смещение при бите, равном 1 - 4 байта

А теперь поподробнее. Индикатор говорит нам - стоит ли дальше продвигаться по дереву к нашему заветному байту. Стоит, если он равен -1 ($FFFFFFFF). Если же нет - то он и есть наш байт. Bit0 - если Teg1=-1 и наш бит=0, то нам следует перейти к элементу по смещению Bit0 от начала дерева. Bit1 - аналогично Bit0, только при бите=1.
А теперь распакуем первый байт первой строки. Напомню, что у сжатого потока Хаффмана нет отдельных байт - идёт один общий поток бит.
Итак, наш первый байт - 66. Разобьём его на биты - 01100110.
Наш первый бит=0, идём к первому элементу словаря: $FFFFFFFF $0000FFFF $00000010 $00000D20. По сути его можно интерпретировать так:
Teg1 = -1;
Teg2 = $FFFF;
Bit0 = $10;
Bit1 = $D20;

В нашем случае бит=0 и Teg1 равен минус единице, значит мы должны перейти по смещению $10 от начала дерева. Получается $0053E918(абсолютное смещение дерева)+$10=$0053E928. Читаем следующий бит (1) и читаем элемент по этому адресу: $FFFFFFFF $0000FFFF $00000020 $00000510. Teg1 у нас опять равен -1, но теперь бит=1, так что переходим мы не по смещению Bit0, а по смещению Bit1. Это у нас $0053E918+$510=$0053EE28. И сл. бит у нас 1.
Читаем: $FFFFFFFF $FFFF0000 $00000520 $00000930. Мы уже знаем, что надо делать. Идём на $0053E918+$930=$0053F248.
Читаем: $FFFFFFFF $FFFF0000 $00000940 $00000AD0. Бит=0. Идём на $0053E918+$940=$0053F258.
Читаем: $FFFFFFFF $FFFF0000 $00000950 $00000960. Бит=0. Идём на $0053E918+$950=$0053F268.
Читаем: $000C0083 $00000005 $FFFFFFFF $FFFFFFFF. Вот это и есть то, что нам надо. Teg1 не равен -1, он равен другому значению. А из этого значения нам нужен только один байт. Это $83. Именно это и есть первый запакованный байт. Проще говоря, если Teg<>-1, то байт=Teg1 AND $FF (т.е. мы берём только последний байт значения).
Теперь возвращаемся к первому элементу, читаем следующий бит и продолжаем в таком же духу. Распаковка продолжается до тех пор, пока нам не распакуется байт $00.

В общем алгоритм выглядит так:
Считать первый бит.
Пока Распакованный байт<>0
. Пока Teg1<>-1
. . Если бит=0, то перейти по первому смещению от начала словаря (третий Integer, то бишь Bit0)
. . Если бит=1, то перейти по второму смещению от начала словаря (четвёртый Integer, то бишь Bit1)
. . Считать следующий бит.
. повторить
. Распакованный байт=Byte(Teg1)
повторить.
_________________
Работаю за деньги
KILL ALL HUMANS!!!!!111


Последний раз редактировалось: HoRRoR (Вс Мар 16, 2008 12:07 am), всего редактировалось 6 раз(а)
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail Посетить сайт автора
АнС
RRC2008
RRC2008


Зарегистрирован: 08.11.2003
Сообщения: 2796

СообщениеДобавлено: Вс Ноя 04, 2007 3:11 pm    Заголовок сообщения: Ответить с цитатой

Ух, я хотел создать подобную тему ещё с 2003 года.
Вован, выкладывай уже свою доку по тому продвинутому RLE, а то тут всё уже забито! Shocked Very Happy
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail
Гость






СообщениеДобавлено: Вс Ноя 04, 2007 4:07 pm    Заголовок сообщения: Ответить с цитатой

HoRRoR если будет еще возможность то напиши в каждом примере по 1 названию игры PSP в котором используеться тот или иной алгоритм.
Конечно можно и без этого. Но так проще будет догнать что и как.
Но если даж не напишешь то тож ничего страшного будем разбираться сами.
Вернуться к началу
Shiru



Зарегистрирован: 25.10.2006
Сообщения: 295
Откуда: Russia, Moscow

СообщениеДобавлено: Вс Ноя 04, 2007 6:46 pm    Заголовок сообщения: Ответить с цитатой

Столько текста и цифр про LZ77, а принцип сжатия так и не объяснил (объяснил только один из возможных способов кодирования)...

Есть большой русскоязычный сайт, посвящённый теме сжатия данных - http://www.compression.ru/
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Посетить сайт автора
Гость






СообщениеДобавлено: Вс Ноя 04, 2007 7:26 pm    Заголовок сообщения: Ответить с цитатой

Shiru писал(а):
Столько текста и цифр про LZ77, а принцип сжатия так и не объяснил (объяснил только один из возможных способов кодирования)...

Есть большой русскоязычный сайт, посвящённый теме сжатия данных -


Очень полезная ссылочка. Но там чтоб разобраться на туеву кучу времени убить которого слава богу полно.
Но... но все же надеюсь что HoRRoR у тебя будут не только теоритические примеры но будет хотяб 1 практический какой нибудь это конечно максимум.

P/S ввожу юзер нейм принимает а все равно как гость.
Вернуться к началу
HoRRoR
RRC2008
RRC2008


Зарегистрирован: 21.06.2006
Сообщения: 2341
Откуда: Ростов-на-Дону

СообщениеДобавлено: Вс Ноя 04, 2007 8:11 pm    Заголовок сообщения: Ответить с цитатой

АнС писал(а):
Вован, выкладывай уже свою доку по тому продвинутому RLE, а то тут всё уже забито!

Забил, чтобы посты по порядку шли, а не чтобы никто не размещал :)

Кто-то писал(а):
HoRRoR если будет еще возможность то напиши в каждом примере по 1 названию игры PSP в котором используеться тот или иной алгоритм.

Ну да, прям все они юзались именно на PSP.

Shiru писал(а):
Столько текста и цифр про LZ77, а принцип сжатия так и не объяснил

А разве не ясно по мною написанному, что принципом сжатия является замена повторяющихся блоков?
На другом сайте мне наоборот сказали, что всё понятно.
Но в любом случае, скажи подробней - что не нравится, попытаюсь исправить...

Shiru писал(а):
Есть большой русскоязычный сайт, посвящённый теме сжатия данных - http://www.compression.ru/

Мне этот сайт ничего не дал, т.к. описанные там методики сжатия мне пока ни в одной игре не встречались (zlib не всчёт, это стандарт, легко обходится).

Кто-то писал(а):
Но... но все же надеюсь что HoRRoR у тебя будут не только теоритические примеры но будет хотяб 1 практический какой нибудь это конечно максимум.

Всему своё время. Как пример приведу dpk из Final Fantasy. За пример хаффмана возьму Silent Hill: Play Novel на GBA, т.к. больше мне этот алгоритм нигде не попадался Smile Если и буду писать пример RLE, то возьму Tombs & Treasure...

Кто-то писал(а):
P/S ввожу юзер нейм принимает а все равно как гость.

Ну так скажи нам своё имя, незнакомец Smile
Попробуй куки почистить - должно помочь...
_________________
Работаю за деньги
KILL ALL HUMANS!!!!!111
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail Посетить сайт автора
Shiru



Зарегистрирован: 25.10.2006
Сообщения: 295
Откуда: Russia, Moscow

СообщениеДобавлено: Вс Ноя 04, 2007 8:21 pm    Заголовок сообщения: Ответить с цитатой

HoRRoR писал(а):
А разве не ясно по мною написанному, что принципом сжатия является замена повторяющихся блоков?
На другом сайте мне наоборот сказали, что всё понятно.

Когда знаешь, о чём речь - конечно-же всё понятно. Но ты вроде как для новичков пишешь. Они по умолчанию не знают, как и почему вообще возможно сжимать данные. Поэтому обязательно нужны общие объяснения.

HoRRoR писал(а):
Мне этот сайт ничего не дал, т.к. описанные там методики сжатия мне пока ни в одной игре не встречались (zlib не всчёт, это стандарт, легко обходится).

Методик сжатия существует ограниченное количество. На указанном сайте находится библиотека материалов по теме, включая, например, подробные описания LZ77 и всех прочих 'забитых' тобой в этой теме методов.
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Посетить сайт автора
HoRRoR
RRC2008
RRC2008


Зарегистрирован: 21.06.2006
Сообщения: 2341
Откуда: Ростов-на-Дону

СообщениеДобавлено: Вс Ноя 04, 2007 8:37 pm    Заголовок сообщения: Ответить с цитатой

Shiru писал(а):

Когда знаешь, о чём речь - конечно-же всё понятно. Но ты вроде как для новичков пишешь. Они по умолчанию не знают, как и почему вообще возможно сжимать данные. Поэтому обязательно нужны общие объяснения.

Ну не знаю, если б я пример рассмотрел, я б всё понял Smile Ведь из примеров всё в основном и понимается...

HoRRoR писал(а):
Методик сжатия существует ограниченное количество. На указанном сайте находится библиотека материалов по теме, включая, например, подробные описания LZ77 и всех прочих 'забитых' тобой в этой теме методов.

Там какой-то не такой LZ77 Smile Там не такое примитивное сжатие, какое встречается на консолях, да и написано каким-то языком терминов Smile
_________________
Работаю за деньги
KILL ALL HUMANS!!!!!111
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail Посетить сайт автора
Макс
Гость





СообщениеДобавлено: Вс Ноя 04, 2007 11:10 pm    Заголовок сообщения: Ответить с цитатой

Horror, респект тебе. Very Happy Не забрасывай.
Вернуться к началу
HoRRoR
RRC2008
RRC2008


Зарегистрирован: 21.06.2006
Сообщения: 2341
Откуда: Ростов-на-Дону

СообщениеДобавлено: Вс Ноя 04, 2007 11:21 pm    Заголовок сообщения: Ответить с цитатой

Макс писал(а):
Horror, респект тебе. Very Happy Не забрасывай.

Спасибо, стараимси Very Happy
Да и забрасывать то нечего, осталось только реальные примеры привести :)

З.Ы. Исправил пару ляпов и неточностей. Просьба информировать, если будете замечать ошибки Smile
_________________
Работаю за деньги
KILL ALL HUMANS!!!!!111
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail Посетить сайт автора
LG.BALUKATION



Зарегистрирован: 05.08.2006
Сообщения: 141
Откуда: Saint-Patersburg

СообщениеДобавлено: Пн Ноя 05, 2007 12:45 am    Заголовок сообщения: Ответить с цитатой

Может лучше такую статью в виде доки повесить где иль для скачивания выложить... Хех, вот на такие случаи и было бы уместно wiki-двигло =)

ЗЫ: текст вроде понятный, но вот в Хоффмане про построение дерева наверно стоилоб упомянуть подробней, а не показывать готовое.
_________________
Zwei Drachen betrachten einander
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail Посетить сайт автора
HoRRoR
RRC2008
RRC2008


Зарегистрирован: 21.06.2006
Сообщения: 2341
Откуда: Ростов-на-Дону

СообщениеДобавлено: Пн Ноя 05, 2007 1:02 am    Заголовок сообщения: Ответить с цитатой

LG.BALUKATION писал(а):
Может лучше такую статью в виде доки повесить где иль для скачивания выложить...

Ну не знаю, я под форум делал Smile Да и редачить ещё не раз это придётся... Поэтому сначала лучше всё до ума довести...

LG.BALUKATION писал(а):
Хех, вот на такие случаи и было бы уместно wiki-двигло =)

:D

LG.BALUKATION писал(а):
ЗЫ: текст вроде понятный, но вот в Хоффмане про построение дерева наверно стоилоб упомянуть подробней, а не показывать готовое.

Исправил. Попытался объяснить...
_________________
Работаю за деньги
KILL ALL HUMANS!!!!!111
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail Посетить сайт автора
Гость






СообщениеДобавлено: Пн Ноя 05, 2007 1:13 am    Заголовок сообщения: Ответить с цитатой

Кода была выложена 1ая часть были одни вопросы
когда прочитал вторую часть стали совершенно другие
В коде стал замечать то что не замечал раньше.
спс. жду примеров. в топ заглядываю по 20 раз надень))
Вернуться к началу
HoRRoR
RRC2008
RRC2008


Зарегистрирован: 21.06.2006
Сообщения: 2341
Откуда: Ростов-на-Дону

СообщениеДобавлено: Пн Ноя 05, 2007 12:42 pm    Заголовок сообщения: Ответить с цитатой

Anonymous писал(а):
Кода была выложена 1ая часть были одни вопросы
когда прочитал вторую часть стали совершенно другие
В коде стал замечать то что не замечал раньше.
спс. жду примеров. в топ заглядываю по 20 раз надень))

Всё поймёшь - ужаснёшься простоте Smile
_________________
Работаю за деньги
KILL ALL HUMANS!!!!!111
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail Посетить сайт автора
BlueHairLady
RRC2008
RRC2008


Зарегистрирован: 12.05.2007
Сообщения: 158
Откуда: Гонолулу

СообщениеДобавлено: Вт Ноя 06, 2007 8:14 am    Заголовок сообщения: Ответить с цитатой

Shiru писал(а):
Когда знаешь, о чём речь - конечно-же всё понятно. Но ты вроде как для новичков пишешь. Они по умолчанию не знают, как и почему вообще возможно сжимать данные. Поэтому обязательно нужны общие объяснения.
Говорю как новичок, не имеющий никакого компьютерного образования и умеющий работать только с не сжатыми данными, - мне понятно.
Вернее, почти понятно. Сейчас вышлю подробный отчёт. HoRRoR, если не хочешь его получить, то лучше заплати.


Shiru писал(а):
Есть большой русскоязычный сайт, посвящённый теме сжатия данных
Быть может, там и есть всё, но требуемую информацию необходимо ещё найти среди сотен полок, отделить от ненужной и как-то вникнуть в техническу терминологию. А здесь сразу всё на блюдечке с золотой каёмочкой. И самое главное, на доступном языке.


Жду более подробного разбора Huffman-а. Принцип сжатия понятен, но много вопросов по его дереву.

С теорией сжатия более-менее понятно, но плохо представляю, как данные вещи на практику переносятся. С моими основами Бейсика в подобных вещах особо не развернёшься. Пытаюсь найти С++ (и чтоб без .NET), может, с ним понятнее будет? Если разберусь в нём, конечно.
На всякий случай информирую, что Си мне нужен для других вещей, так что предложение сменить Си на Delphi в данном случае не уместно.


HoRRoR писал(а):
Всё поймёшь - ужаснёшься простоте
Похоже на буддисткое изречение. Вот только до состояния нирваны способны дойти лишь избранные.
_________________
Надеюсь на возвращение, но сейчас меня нет.
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail Посетить сайт автора
Shiru



Зарегистрирован: 25.10.2006
Сообщения: 295
Откуда: Russia, Moscow

СообщениеДобавлено: Вт Ноя 06, 2007 8:48 am    Заголовок сообщения: Ответить с цитатой

BHLady писал(а):
Говорю как новичок, не имеющий никакого компьютерного образования и умеющий работать только с не сжатыми данными, - мне понятно.

На тот момент HoRRoR написал только про LZ77, и первый абзац описания ('основой этого алгоритма...') отсутствовал.
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Посетить сайт автора
АнС
RRC2008
RRC2008


Зарегистрирован: 08.11.2003
Сообщения: 2796

СообщениеДобавлено: Вт Ноя 06, 2007 9:54 am    Заголовок сообщения: Ответить с цитатой

Здорово пишешь! Я бы, наверное, так просто и понятно не смог описать.


HoRRoR писал(а):
Определение структуры архивов

Для начала разберём, что такое архив.
Архив - это файл, в котором содержится некоторое количество других файлов, при этом они вовсе необязательно должны быть сжаты.

Делается это либо для удобства и быстродействия (попробуйте поработать с несколькими десятками тысяч файлов в одной папке Smile), либо для экономии места (если данные ужимаются - то понятное дело для экономии, но если нет - то место тоже экономится, т.к. в кластерных файловых системах файлы с размером не кратным размеру кластера будут занимать немного больше места - ровно столько, сколько занимали бы, если бы их дополнить так, чтобы их размер всё-таки стал кратен размеру кластера).


Всё-таки там дело не столько в экономии места, сколько в скорости доступа. До считывания данных приводы компакт-дисков ОЧЕНЬ долго разгоняются, поэтому оптимальнее считывать данные, пока диск не замедлился.
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail
HoRRoR
RRC2008
RRC2008


Зарегистрирован: 21.06.2006
Сообщения: 2341
Откуда: Ростов-на-Дону

СообщениеДобавлено: Вт Ноя 06, 2007 4:19 pm    Заголовок сообщения: Ответить с цитатой

BHLady писал(а):
Сейчас вышлю подробный отчёт. HoRRoR, если не хочешь его получить, то лучше заплати.

Мммм... Торги уместны? :D

BHLady писал(а):
Жду более подробного разбора Huffman-а. Принцип сжатия понятен, но много вопросов по его дереву.

Ну что с деревом то непонятно?) Разве что если вопросы по части его реализации Smile Но в примере всё опишу ;)

BHLady писал(а):
С теорией сжатия более-менее понятно, но плохо представляю, как данные вещи на практику переносятся. С моими основами Бейсика в подобных вещах особо не развернёшься. Пытаюсь найти С++ (и чтоб без .NET), может, с ним понятнее будет?

Мб приведу ещё примеры реализации распаковки (мб и паковки) на Делбьфи/Ассемблере.

BHLady писал(а):
На всякий случай информирую, что Си мне нужен для других вещей, так что предложение сменить Си на Delphi в данном случае не уместно.

А менять Си на Дельфи никто и не заставляет о_О Просто нет смысла учить C, если не собираешься организовывать крупные проекты Smile
Мне бы вот самому C++ знать, давно бы уже пару дебаггеров в эмули встроил, да дебаггер PSP написал:(

АнС писал(а):
Здорово пишешь! Я бы, наверное, так просто и понятно не смог описать.

Спасибо, рад слышать, что хоть кому-то нравится :)

АнС писал(а):
Всё-таки там дело не столько в экономии места, сколько в скорости доступа. До считывания данных приводы компакт-дисков ОЧЕНЬ долго разгоняются, поэтому оптимальнее считывать данные, пока диск не замедлился.

Вообще, например, для PSX без разницы, т.к. чтение производится по секторам, а "кластеризация" там (ну секторизация то бишь) тоже присутствует :)

P.S. Большое спасибо BHLady за её багрепорт. Исправил множество ляпов, ошибок и опечаток Smile
_________________
Работаю за деньги
KILL ALL HUMANS!!!!!111
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail Посетить сайт автора
УхоЖёр



Зарегистрирован: 31.10.2007
Сообщения: 14

СообщениеДобавлено: Ср Ноя 07, 2007 12:43 am    Заголовок сообщения: Ответить с цитатой

Мне нравиться идея перевода игр
Но переводить на уже забытие платформы скучно
фиг знает Может быть мне хочеться славы??)) чеславие с ума сойти...

Я реально 4 дня как начал вникать в тему гдет по 5 часов в день примерн...

Благодаря одному англоизычному сайту и форуму шедевр я примерн разабравшись в самых что ни на есть основах осилил марио на денди))

далее прочел СУПЕР ПУПЕР фак HoRRoR'а я все что написанно усвоил но не все догнав... остались вопросы конечн.

Главное конечный результат ... распаковать то что надо и запаковать назад .... пока это не очень из фака понятно как ... но фак не дописан и я думаю что еще прочту то что даст пищи для размышления...

Пока не написанно как это делаеться в факе я начал включать мозг гы)) или то что там есть...

ну вобщем решил зделать так
взял текстовый файл назвал Super.txt написал там слово FUCK больше умного ничего в бошку не пришло). Далее заархифировал его раром по умолчанию. Открыл ХЕКСОМ и чтож я там увидел??

Почему то что подчеркнуто подчеркнуто будет ясно после сравнения рис 1 и рис 2
Первое подчеркнутое так и осталось для меня загадкой. Вопрос первый что это? второе и третье это 04 как я понял это 4 байта которые весил файл со словом в 4 буквы)) Далее опять 2 непонятных для меня вещи которые подчеркнуты и вопрос номер 2 что это? далее черным подчеркнуто название моего файла тхт. далее опять подчеркнутое чтото синим после двух нулей и опять не понять что эт есть такое)) вопрос три что это? во далее черным идет мои 4 буквы и после них опять какой то старческий маразм)))

поглядел на это все я... почесал макушку и решил изменить архив добавив еще 1 букву)) опять раскрыл хексом и вуаля

Сделав скрины которые вы видете я начал их сравнивать. Все что как то отличалось я подчеркнул. Потом был еще опыт с архивом на 2 файла в 1ом было 3 буквы во 2ом 4 буквы. Из всего я вынес одно я знал где увидеть количество 1ое байт (тоесть я знал длинну слова в файле) 2. знал имя + расширение файла 3. Я понял что после названия файла идут два нуля потом еще 4 байта и после них мои слова длинну которую я знал.
Далее я открыл прост файл тхт в хексе и увидел там ток байты своих букв. Ни каких других. Открыв архив хексом опять я скопировал в блок в заранее пустой хекс и выбрав сохранив как сохранил как тхт файл. После открыв тхт файлик я увидел свой текс)))...
Далее я начал эксперементировать с рисунками. Создал масенький белый квадрат в Паинте ... результат тот же ... я извлек его без проблем.
Далее я начал уже эксперементировать с одним из архивов ПСП и опять результат тот же) Единственное что еще не попробывал разархивировав изменить буквы (не их количество) или разукрасить белый квадратик не меняя размера вернуть биты назад вставив их назад на ихнее место.


Последний раз редактировалось: УхоЖёр (Ср Ноя 07, 2007 1:21 am), всего редактировалось 1 раз
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
HoRRoR
RRC2008
RRC2008


Зарегистрирован: 21.06.2006
Сообщения: 2341
Откуда: Ростов-на-Дону

СообщениеДобавлено: Ср Ноя 07, 2007 1:01 am    Заголовок сообщения: Ответить с цитатой

RAR под данную документацию не подходит, т.к. там используется более сложный алгоритм сжатия.
_________________
Работаю за деньги
KILL ALL HUMANS!!!!!111
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail Посетить сайт автора
LG.BALUKATION



Зарегистрирован: 05.08.2006
Сообщения: 141
Откуда: Saint-Patersburg

СообщениеДобавлено: Ср Ноя 07, 2007 3:27 am    Заголовок сообщения: Ответить с цитатой

Кстати, с RAR'ом идёт описание формата файла и распаковщик доступен в сырцах.
_________________
Zwei Drachen betrachten einander
Вернуться к началу
Посмотреть профиль Отправить личное сообщение Отправить e-mail Посетить сайт автора
Показать сообщения:   
Начать новую тему   Ответить на тему    Список форумов www.shedevr.org.ru -> Экстремальный ромхакинг Часовой пояс: GMT + 3
На страницу 1, 2, 3, 4  След.
Страница 1 из 4

 
Перейти:  
Вы не можете начинать темы
Вы можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах


Powered by phpBB © 2001, 2005 phpBB Group