eXeLab
eXeL@B ВИДЕОКУРС !

ВИДЕОКУРС ВЗЛОМ
выпущен 2 августа!


УЗНАТЬ БОЛЬШЕ >>
Домой | Статьи | RAR-cтатьи | FAQ | Форум | Скачать | Видеокурс
Новичку | Ссылки | Программирование | Интервью | Архив | Связь

Русский / Russian English / Английский

Сейчас на форуме: Adler, artyavmu, AleshaA (+3 невидимых)
 · Начало · Статистика · Регистрация · Поиск · ПРАВИЛА ФОРУМА · Язык · RSS · SVN ·

 eXeL@B —› Крэки, обсуждения —› Помогите разобрать алгоритм усечённого блочного кодирования (block truncation coding, BTC)
Посл.ответ Сообщение

Ранг: 7.8 (гость)
Статус: Участник

Создано: 2 августа 2013 19:46 · Поправил: robot666 New!
Цитата · Личное сообщение · #1

Доброго всем!
Есть игра Harvester, я хочу разобраться с алгоритмом декодирования видео, вынуть видео, наложить русские титры и вставить назад.
Ссылка на описание и алгоритм - --> FutureVision_FST <--

Начал разбираться и не понял терминологию, которой описан алгоритм декодирования.

Формат видео.
Видео состоит из множества блоков видео+аудио.
Все представленные числа находятся в формате маленького индейца (Little Endian).
В заголовке FST файла идут 8*4 (32 байта, на картинке красные блоки) следующих данных (u32 - беззнаковое целое число, 32 bit, 4 байта; u16 - беззнаковое целое число, 16 бит, 2 байта):
на примере ALARM.FST

Начало заголовка файла:
u32 - Signature - сигнатура файла -- "2TSF"
u32 - Width - ширина кадра (число 320 пикс)
u32 - Height - высота кадра (число 200 пикс)
u32 - Ticks - frame rate in ticks? (под вопросом, частота кадров в тиках, во многих файлах одинаковое число 276480)
u32 - Frames - число кадров-блоков видео+аудио. (40)
u32 - Rate - частота кадров в секунду (15 к/с)
u32 - SoundRate - частота звука (22050 Гц)
u32 - SoundBits - разрядность звука (16 бит)

Следом идут блоки в количестве, указанном в Frames (40 зеленых блоков на картинке, 4+2 байта, 40*6 байт) :
u32 VideoSize -- размер блока видео
u16 AudioSize -- размер блока аудио
Конец заголовка файла.

Затем идут массивы байт количеством Frames:
u8 VideoData[VideoSize] -- блок данных видео, размером VideoSize
u8 AudioData[AudioSize] -- блок данных аудио, размером AudioSize

Каждый блок VideoData имеет следующий формат:
u16 - BitmapSize -- size of the following bitmap, in bits (размер следующего растра/изображения, в битах)
u8 Bitmap[BitmapSize/8+1] -- flag bits (битовые флаги), массив. Битовый поток?
RGB Palette[256] -- optional. 6-bits DAC values. (RGB и 256, то есть идут группы из 3х цветов R G B и групп 256, как раз палитра 768 байт)
u8 Data[] -- to the end of frame (до конца кадра 1 байтные данные)

И затем идет алгоритм декодирования:
Initialize bit reader using Bitmap. (Bitmap из заголовка выше, похоже всю цепочку надо представить битовой строкой)
Read one byte, fetch bits starting from the highest. (прочитать 1 байт, получить список бит с наивысшего?)

Get bit. If bit is set - read the palette data (взять бит, если он установлен в 1, то читать данные палитры)
For each 4x4 block of the image (left to right, top to bottom) (для каждого блока 4х4 (пикселей) изображения (слева-направо, сверху-вниз, ноль значит в левом-верхнем углу)
Get Bit. If bit is set: (взять бит, если он в 1, то)
Get Bit. If bit is set: (взять бит, если он в 1, то)
Read Color0, Color1 8-bits values from Data (читать Цвет0, Цвет1 8-битные значения из DATA)
Read BTCMap 16-bits value from Data (читать BTCMap 16 битное значение из DATA, битовая матрица 4х4)
For each pixel of 4x4 block (left to right, top to bottom) (для каждого пикселя блока 4х4, каждый пиксель это бит)
pixel = (BTCMap & 0x8000) ? Color1 : Color0 (сделать битовую операцию BTCMap (2байта) & 8000h, 8000h = 10000000 00000000, старший бит 16 бит числа в 1, результат сей битовой операции будет или 0, или 1. В зависимости от этого возвращается Цвет1 или Цвет0, понял. )
BTCMap <<= 1 (делается битовый сдвиг влево BTCMap на 1, то есть BTCMap=BTCMap*2)
Else
Draw block using next 4x4 bytes of Data (рисовать блок, используя следующие 4х4 байта данных, видимо используя палитру. На выходе получается RAW картинка наверное)

--> Иллюстрация <--

ЗЫ1:
Метод усечённого блочного кодирования (block truncation coding, BTC), первоначально разработанный для кодирования двухуровневых чёрно-белых изображений, может быть с успехом применён и для сжатия полутоновых изображений (как чёрно-белых полутоновых, так и цветных).
Классический метод BTC чрезвычайно прост: изображение разбивается на непересекающиеся прямоугольные блоки, для каждого блока вычисляются среднее значение яркостей пикселов и дисперсия, затем пикселы блока делятся на две группы – надпороговые, яркость которых превышает вычисленное среднее, и подпороговые. Для того, чтобы можно было установить, к какой группе принадлежит кодируемый пиксел, передаётся (кодируется) бинарная матрица, кроме того, передаются вычисленные среднее и дисперсия, используемые для восстановления блока при декодировании.

ЗЫ2:
Судя по вики (--> Block_Truncation_Coding <--), битовые 0 и 1 - это как раз Цвет0 и Цвет1.
BTCMap - битовая карта 4х4, 16 бит закодированы в 2х байтах, представляют собой в итоге 4х4 байта матрицу.


Ранг: 1011.0 (!!!!)
Статус: Участник

Создано: 2 августа 2013 20:28 New!
Цитата · Личное сообщение · #2

ну так вы все прекрасно рассписали, теперь берите и делайте
а еще лучше гугл в руки или гитхаб и ищите уже готовые реализации

Ранг: 7.8 (гость)
Статус: Участник

Создано: 2 августа 2013 20:44 · Поправил: robot666 New!
Цитата · Личное сообщение · #3

reversecode
Мне абсолютно непонятны следующие строки
1. Initialize bit reader using Bitmap. ( что за бит ридер, используя Битмап?)
2. For each 4x4 block of the image (left to right, top to bottom) (Что за цикл такой 4х4 блок изображения, для бит, для пикселей?)
3. Get Bit (Какой бит? Из Битмап 2 старших бита?)
4. For each pixel of 4x4 block (left to right, top to bottom) (То же самое что в п.2, опять какой-то блок, толи битовый, толи байтовый)
5. Draw block using next 4x4 bytes of Data (А тут уже 4х4 байта из Дата, причем нарисовать, то есть получается из 320х200 если разбить на блоки 4х4 получается 80х50 блоков, в которых 4х4 блоки, ох)

У меня в голове схема из-за этого странного псевдоязыка не строится. Как формируется цикл декодирования?
Куча вопросов, которые не складываются в единую картину мира (((((


Ранг: 1011.0 (!!!!)
Статус: Участник

Создано: 2 августа 2013 20:48 · Поправил: reversecode New!
Цитата · Личное сообщение · #4

так я не получил ответа на свой "наводящий" вопрос - вас в гугле забанили ??
--> Link <--

| Сообщение посчитали полезным: Abraham


Ранг: 7.8 (гость)
Статус: Участник

Создано: 2 августа 2013 20:55 New!
Цитата · Личное сообщение · #5

reversecode
Там мне пока что никто не помог, поэтому я пришел сюда. В гугле тоже за 2 дня ничего толкового не нашел.
Я не пойму как формируется цикл на их чУдном псевдоязыке.


Ранг: 1011.0 (!!!!)
Статус: Участник

Создано: 2 августа 2013 20:57 · Поправил: reversecode New!
Цитата · Личное сообщение · #6

а вы программист что ли? ну так берете декомпилер для этой игры и изучаете

а там все чудно рассписали, биты карты итд
видимо вы не программер

Ранг: 7.8 (гость)
Статус: Участник

Создано: 2 августа 2013 21:02 · Поправил: robot666 New!
Цитата · Личное сообщение · #7

reversecode
Я оочень далек от классического программирования как по образованию, так и по работе, для меня это god damned hobby, но тут я закопался и завис ( IDA с поиском константы 8000 пока ни к чему не привела.
Недельное изучение в dosbox debugger ни к чему пока не привели.

Предложите пожалуйста продолжение или иной вариант:
1. Ловлю чтение файла, int 21h, ah=3fh
2. Нахожу байт-поиском в IDA куда же я попал
3. Курю годы до просветления..

ЗЫ: походу сюда я старую версию запулил текста, ща гляну ( не, последняя правка, застрял на циклах.
Пролистал книгу Методы сжатия данных. - М: Диалог-МИФИ, - 2003, 384 с., про BTC там нет ничего (


Ранг: 1011.0 (!!!!)
Статус: Участник

Создано: 2 августа 2013 21:15 · Поправил: reversecode New!
Цитата · Личное сообщение · #8

вы не то ловите,
графика выводтся через vesa vbe а не через dos
программа собрана на watcom, стаб там впереди кажется прицеплен,
и зза этого прога как мне кажется вообще неправильно в ида грузится
так что отцепляйте цепляйте .. играйтесь что бы правильно загрузилась
вконце exe, вроде даже какая то мнини дебаг инфа, которую может даже поймет ИДА,
но я знаю как минимум один отладчик что ее понимает, это wd(watcom debugger)

в комплекте ваткома кажется была утилита которая отцепляет стаб

отрезать надо до
0000041533: 4D 5A
очень похоже на реальное начало файла
а до этого это расширитель памяти итд
он не нужен, и изза этого ида не так дизассемблирует, а вы ищите не те данные, точнее не в том месте

Ранг: 7.8 (гость)
Статус: Участник

Создано: 2 августа 2013 21:40 · Поправил: robot666 New!
Цитата · Личное сообщение · #9

reversecode
стаб я отцепил, мне помогли
(sb.exe /U somegame.exe
Теперь файл somegame.le можно открывать в IDA,
утилита dos extender 32 забыл как точнее они зовутся, замена dos4gw)

, открыл 32 битный код идой, в коде байт-поиском находил места, куда я попадал в досбокс дебагере. Смотрел байты текущих инструкций в дебагере, вбивал поиск в Иде и находил блоки.
Оказалось несложно.
Отладчик всё никак не решусь начать копать через softice dos под vmware, мне айс нравился, но последний раз я его трогал 10 лет назад и я ничего не помню (

То есть плясать от чтения файла видео - плохой вариант?
Тогда подскажи как выводилась графика в vesa режиме? Там вроде плавающее окно в 64кб было и нужно было поток данных для вывода графики писать по какому-то адресу, а палитру совать в порт, афаир, 3f8h.

Или у меня уже каша в голове от дос-ада.


Ранг: 1011.0 (!!!!)
Статус: Участник

Создано: 2 августа 2013 21:45 New!
Цитата · Личное сообщение · #10

ооо ну так я ж не знал что вы догадались отцепить)) думал по стабу лазите...

дайте отцепленый файл глянуть, а то лень резать в винхексе

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

Ранг: 7.8 (гость)
Статус: Участник

Создано: 2 августа 2013 21:49 · Поправил: robot666 New!
Цитата · Личное сообщение · #11

http://rghost.ru/47853829

вот его я колупаю в иде в 32 битном режиме. В нем пытался искать константу 8000 из алгоритма, с которой делается битовая операция.

Я использую dosbox svn daum, там есть откомпилированная версия с дебагером.


Ранг: 1011.0 (!!!!)
Статус: Участник

Создано: 2 августа 2013 21:57 · Поправил: reversecode New!
Цитата · Личное сообщение · #12

я не дождался отцепил в winhex
http://rghost.ru/47854037
ида сразу все распознала и показала
вот к примеру функция чтения ваших FST

FST_sub_72160((int)"graphic\fst\kinggrow.fst", 0, 2, v8, a1);

ps вы то отцепили, а прицеплять обычный стаб кто будет?)

Ранг: 7.8 (гость)
Статус: Участник

Создано: 2 августа 2013 22:05 New!
Цитата · Личное сообщение · #13

reversecode
Черт побери, в вашем варианте всё намного лучше ИДА признала файл как LE, просто магия, ушел изучать.
Куча функций автоматом ида разобрала.
Спасибо огромное.


Ранг: 1011.0 (!!!!)
Статус: Участник

Создано: 2 августа 2013 22:06 · Поправил: reversecode New!
Цитата · Личное сообщение · #14

потому что нужно было обрезать фул стаб и оставить prestub который и формирует нормальный заголовок перед LE
и да, этот exe является рабочим, только dos4gw.exe надо рядом положить ))

Ранг: 7.8 (гость)
Статус: Участник

Создано: 2 августа 2013 22:10 · Поправил: robot666 New!
Цитата · Личное сообщение · #15

reversecode
Я про стабы то узнал месяц назад, а мне тут фулл стаб, престаб. Проще было на китайском написать))
Короче не хватило предметных знаний.

В игре есть 2 плохих момента:
1. В текстовых файлах есть субтитры для видео, но в видео титров нет.
2. Некоторые видеоролики начинают проигрываться, показывает пару кадров и пропуск. Причем если уменьшить количество циклов досбокс до 5000-8000, то ролики проигрываются нормально, но игра становится медленной до неиграбельности. Вот ломаем голову что же делать.


Ранг: 1011.0 (!!!!)
Статус: Участник

Создано: 3 августа 2013 00:25 · Поправил: reversecode New!
Цитата · Личное сообщение · #16

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

как вариант можете попробовать поганять ваткомоским дизасмом может он дебаг инфу увидет и ее можно будет выдрать

Ранг: 56.9 (постоянный)
Статус: Участник

Создано: 3 августа 2013 03:51 New!
Цитата · Личное сообщение · #17

Вывод ваткомовского wdump: http://pastebin.com/XAg19MLQ


Ранг: 1011.0 (!!!!)
Статус: Участник

Создано: 3 августа 2013 04:31 · Поправил: reversecode New!
Цитата · Личное сообщение · #18

wdump не знал... но парсер на пять строк написал... сгодится на будущее

harvest.idc --> Link <--
в иде применить и всего то

Ранг: 7.8 (гость)
Статус: Участник

Создано: 3 августа 2013 09:28 · Поправил: robot666 New!
Цитата · Личное сообщение · #19

reversecode проставил соответствие адресам функции имена из ватком лога? класс.
Применил, стало еще красивее.

Есть какие-нибудь идеи, почему воспроизведение видео зависит от циклов-тактов в досбокс и почему при больших значениях некоторые видео показывают всего пару кадров?
В режиме LOG пошагово всё видео воспроизводит нормально, а в режиме авто с циклами ~40000 начинает чудить. Если циклы уменьшить до 5000, то видео показывает нормально, но играть становится невозможно. На vogons'е гениально посоветовали постоянно переключать циклы.

Буду в отладчике смотреть функцию decompress_fst, на нее все ссылаются.
Сперва идет play_fvi с указанием файла fst, а внутри

Code:
  1. if ( v6 )
  2.  viewport::resize((int)&the_viewport, 320, 200, 8, 1); // переключили видеорежим в 320х200 для видео
  3.  decompress_fst(v5, a5, 480); // разжали fst, видимо и показали где-то тут же внутри функции
  4.  v8 = viewport::resize((int)&the_viewport, 640, 480, v11, 1); // Переключили назад в 640х480
  5.  v9 = (unsigned __int8)setvgapalette(v8, 256); // установили палитру


Я тут подумал. Вот можно разобрать видео, но когда собирать его назад придется, то произойдет снова понижение качества, в оригинале итак грустно, а будет еще грустнее. (


Ранг: 755.0 (! !)
Статус: Участник
Student

Создано: 5 августа 2013 04:31 New!
Цитата · Личное сообщение · #20

robot666 пишет:
то произойдет снова понижение качества

на то оно и сжатие с потерей качества... и если нигде коэффициент сжатия не задаётся в функции компрессии, то robot666 пишет:
будет еще грустнее.

Ранг: 7.8 (гость)
Статус: Участник

Создано: 5 августа 2013 09:47 · Поправил: robot666 New!
Цитата · Личное сообщение · #21

Три дня смотрел функцию Decompress_fst, не вижу места почему некоторые видео пропускает игра.

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

Есть одно непонятное мне место:
Code:
  1. cseg01:00013039                 movsx   eax, W?raw_key$nys ; short volatile raw_key
  2. cseg01:00013040                 cmp     eax, 1
  3. cseg01:00013043                 jz      VIDEO_EXIT
  4. cseg01:00013049                 cmp     W?left_button$nyuc, 0 ; char volatile left_button
  5. cseg01:00013050                 jnz     VIDEO_EXIT
  6. cseg01:00013056                 cmp     W?right_button$nyuc, 0 ; char volatile right_button
  7. cseg01:0001305D                 jnz     VIDEO_EXIT

По идее тут сравнивается нажата ли левая/правая кнопка мыши или клавиша и переход на VIDEO_EXIT.
НО, в IDA навожу на movsx eax, W?raw_key$nys, смотрю в HEX, последовательность 0F BF 05 60 59 0D 00, иду в WinHex на это же место и вижу уже 0F BF 05 60 59 02 00.

Вопрос, почему предпоследний байт кода отличается?
02 и 0D.
wtf?
Убирал переходы, игра вообще валится с ошибками, возможно это и не то, что я думаю?

Интересное наблюдение:
Взял на тестирование момент повторного разговора с Хэнком, показывает 1 или пара кадров видео ковбоя, стреляющего в индейца и пропуск. Это видео RANGSHOT.FST, подменил его другим видео, то же самое, пара кадров из другого видео. Никак не пойму, почему игра одни видео играет, а другие нет. Например, начальные 3 видео проигрываются всегда нормально.
Подменил RANGSHOT.FST на VIRGLOGO.FST, играющий в начале, воспроизвелось нормально.
Если VIRGLOGO.FST подменить на RANGSHOT.FST, то при старте игры видео показывает нормально.
Загадка.


Ранг: 1011.0 (!!!!)
Статус: Участник

Создано: 5 августа 2013 10:07 New!
Цитата · Личное сообщение · #22

буфер сканкодов живой

потому что формат видео скорее всего разный

Ранг: 7.8 (гость)
Статус: Участник

Создано: 5 августа 2013 10:18 · Поправил: robot666 New!
Цитата · Личное сообщение · #23

reversecode
У меня было такое предположение, что когда кликаешь мышкой и начинается видео, то да, в буфере что-то как-то остается. Но непонятно куда копать.

А как бы буфер сбросить? В порт 61h подать коротко сигнал. Это для клавиатуры, ищу для мышки, так как клаву в момент начала видео я не трогаю.


Ранг: 1011.0 (!!!!)
Статус: Участник

Создано: 5 августа 2013 10:37 New!
Цитата · Личное сообщение · #24

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

манияки которые захотят в нее поиграть, поставят дос или поставят какойто вирутал ПК,
и поиграют

зачем ломать логику задуманую автором и чего то там перекодировать ...

Ранг: 7.8 (гость)
Статус: Участник

Создано: 5 августа 2013 10:48 · Поправил: robot666 New!
Цитата · Личное сообщение · #25

Игра прекрасно играется под dosbox, весь текст уже переведен и вставлен.
Под vmware и virtualpc2007 не работает.

Единственный момент который всё портит - это пропуски видео.

У меня чето руки кривые чтоли, HEX VIEW-A в IDA и Winhex не могу состыковать, не то вижу. Делаю NOP на условных переходах, а IDA мне пишет, что там int3 и retf, игра естественно валится.

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

Ранг: 7.8 (гость)
Статус: Участник

Создано: 6 августа 2013 21:38 · Поправил: robot666 New!
Цитата · Личное сообщение · #26

reverser будь добр, напиши, пожалуйста, где взять wdump и как им пользоваться. Я так же хочу получить красивый LE исполняемый файл игры "противостояние - военная хроника".

Это из состава OpenWatcom C++ ?
Ага из состава.
http://www.openwatcom.org/index.php/Downloads

wdump.exe -Dx h.exe выдает красоту.


Ранг: 1011.0 (!!!!)
Статус: Участник

Создано: 6 августа 2013 21:44 New!
Цитата · Личное сообщение · #27

в комплекте ваткома
а вы уверены что вообще там осталась дебаг инфа?
и такой красивый как я вам дал? wdump не генерит
могу сгенерить, давайте файл
 eXeL@B —› Крэки, обсуждения —› Помогите разобрать алгоритм усечённого блочного кодирования (block truncation coding, BTC)

Оригинальный DVD-ROM: eXeL@B DVD !

Вы находитесь на форуме сайта EXELAB.RU
Проект ReactOS