Форум Эму-Россия
http://forum.emu-russia.net/

Указатели в Wai Wai World
http://forum.emu-russia.net/viewtopic.php?f=214&t=491		 Страница 1 из 1
Автор:  Griever [ 16 авг 2008, 20:58 ]
Заголовок сообщения:  Указатели в Wai Wai World
Вопрос, разумеется, в первую очередь, к CaH4e3'у, ибо
Цитата:
Довольно быстро РОМ был зверски препарирован, а алгоритм запаковки - полностью изучен.

Вот всё никак не пойму, в чем заключается непосредственно сжатие. На первый взгляд собака порыта здесь:
Код:
seg005:9007 sub_9007:                               ; CODE XREF: sub_C3D1-3548p
seg005:9007                 STA     byte_14; на входе в аккумуляторе упакованный единичный байт, соответствующий нужному указателю(?)
seg005:9009                 AND     #$F8 ; '°'
seg005:900B                 STA     byte_15
seg005:900D                 LSR     A
seg005:900E                 LSR     A
seg005:900F                 LSR     A
seg005:9010                 TAY
seg005:9011                 ADC     byte_15
seg005:9013                 STA     byte_15
; b15 := ((ptr&$F8) shr 3)+ptr&$F8 Что за странная арифметика? Очевидно, что в b15 не
;учитываются младшие три бита упакованного байта. И результат является индексом указателя в таблице указателей в РОМе
seg005:9015                 LDA     byte_14
seg005:9017                 AND     #7
seg005:9019                 BEQ     loc_9022
; Если младшие 3 бита не выставлены, это означает, что инкремент значения будущего считанного указателя больше восьми, и его
;надо читать отдельно (становится возможным увеличить значение указателя вплоть до $FF, но, очевидно, теряется вообще весь
;эффект от сжатия указателя, т.к. использованы уже два байта)
seg005:901B                 TYA                 
seg005:901C                 ADC     byte_14;  b14 := (ptr&7)+ptr shr 3 - (?! зачем это)
seg005:901E                 TAY
seg005:901F                 INY
seg005:9020                 LDA     ($A),Y          ;Загрузка инкремента младшего байта указателя   
seg005:9020                                               ; Смещение относительно 9435 - начало таблицы указателей
seg005:9022
seg005:9022 loc_9022:                               ; CODE XREF: sub_9007+12j
seg005:9022                 LDY     byte_15
seg005:9024                 ADC     ($A),Y ; Загрузка младшего байта из таблицы байтов указателей в РОМе
seg005:9026                 STA     Low_Ptr_Byte
seg005:9028                 INY
seg005:9029                 LDA     ($A),Y          ; Загрузка старшего байта из РОМа
seg005:902B                 ADC     #0
seg005:902D                 STA     Hi_Ptr_Byte
seg005:902F                 RTS

Итак, какие отсюда сдедуют выводы. Непосредственно значений байтов базовых указателей в lookup table может быть аж $FF shr 3 = $1F или аж целых 15 двухбайтовых указателей. Очевидно, что все ситуации с указателями будут решаться за счет именно трех младших битов (или, если их не хватит, дополнительного прочитанного байта). Зачем тогда эти арифметические головоломки с индексом указателя в таблице и индексом инкремента? Не легче ли было бы просто разделить на старший и младший байты и просто упаковать старшие байты указателей RLE, к примеру. Думаю, это бы значительно перекрыло по эффективности этот странный способ. Я уж не говорю вообще об идее паковать как-то указатели, в то время, как сам текст не сжат.
Не ошибся ли я где-нибудь? Может быть, дело вообще обстоит по-другому?
Автор:  CaH4e3 [ 16 авг 2008, 22:38 ]
Заголовок сообщения:  Re: Указатели в Wai Wai World
Указатели упакованы очень просто, как ави фильм с "ключевыми" кадрами. ;) Указатели идут блоками по 8 штук, первый в блоке - полный 16-битный указатель, за ним идет 7 байтов с разницей между первым и каждым из семи последующих. Чтобы получить полный указатель, надо взять первый указатель блока и прибавить к нему соответствующий байт. Итого, каждый блок из 8 указателей занимает 9 байт (вместо 16 без упаковки). А теперь простая арифметика. Индекс каждого восьмого указателя (полного) будет как раз index & 0xF8 (равносильно [(index / 8) * 8] как целое). Теперь если учесть, что байтов в блоке не 8 а 9, то к каждому индексу надо добавляеть по 1 на каждый из предыдущих блоков, а их как ни странно [index / 8] как целое или index >> 3. Таким образом (index & 0xF8) + (index >> 3) есть индекс каждого восьмого поинтера в массиве 9байтовых блоков. Соответственно, что [index % 8] + 1 или index & 7 + 1 есть уже индекс конкретного указателя в заданном блоке. Вуаля.
Код:
   0     1    2    3    4    5    6    7    8     9    A    B    C    D    E    F
0 [ABAB][+6B][+7B][+8B][+9B][+AB][+BB][+CB][ACAB][+6B][+7B][+8B][+9B][+AB][+BB][+CB]
   0 1   2    3    4    5    6    7    8    9 A   B    C    D    E    F    10   11

1 [ADAB][+6B][+7B][+8B][+9B][+AB][+BB][+CB][AEAB][+6B][+7B][+8B][+9B][+AB][+BB][+CB]
   1213  14   15   16   17   18   19   1A   1B1C  1D   1E   1F   20   21   22   23

Найти поинтер 1E

(1E / 8) * 8 = 18
1E / 8 = 3
18 + 3 = 1B
@(1B) = AEAB
1E % 8 = 6
1B + 6 + 1 = 22
@(22) = +BB
ptr = AEAB + BB = AF66
Если брать старшие байты и хранить только младшие, то все равно на N указателей надо N+1 байт. А при достаточно длинных строках не факт, что мы вообще получим N больше тех же самых восьми и таким образом выигрыш едва будет больше пары байт на полный блок поинтеров. А в плохом случае N может быть еще и меньше восьми, так что выигрыш будет спорный, это не стоит вообще такого геморроя с рле, который потом еще надо куда-то распаковывать. Так гораздо проще и эффективнее.
Автор:  Griever [ 17 авг 2008, 13:06 ]
Заголовок сообщения:  Re: Указатели в Wai Wai World
Вот ведь как! Действительно, стройная система. Наверное, стоило мне взглянуть непосредственно на массивы указателей :) Спасибо.
Страница 1 из 1 Часовой пояс: UTC + 3 часа [ Летнее время ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/