- LZSS Decompress -
_____________________________________________________________________
Descompresión del Intro del Secret of Mana
PARTE 1
- SNES -
V 1.0
Por Dark-N ( naldo_go@hotmail.com )
http://www.nekein.com/tyh
____________________________________________________________________
Nota: Debes tener la versión en Ingles del juego, ya que con esta versión hice la guía.
Introducción
Antes de Empezar
La Intro
Punteros LZSS.
Regla de los 4 pasos
Analizando la
compresión de la ROM
Una vez descomprimida,
¿Qué sigue?
Fin de primera
parte
_________________________________________________________________________________________________
Esta guía la hice con intenciones de explicar como descomprimir la Intro del Secreto of Mana, que está comprimida con el algoritmo LZSS, muy parecido a LZ77. Magno me ha orientado y explicado muchas cosas que aquí detallo (¡muchas gracias!), ya que el lo tradujo al 100% ;)
Primero hay que decir que trabajaremos con la intro que se muestra antes de
jugar, es decir, en la que sale si no tocas ningún botón del control
pad y habla de cuando el maná estaba desapareciendo.
La intro está en ASCII pero comprimida, es decir que
debes verla sin usar Búsqueda relativa. La compresión LZSS es
progresiva, es decir, que si bien los primeros caracteres los puedes ver bien,
conforme empiecen a haber letras repetidas, éstas serán sustituidas
por punteros LZSS a donde ya aparecieron anteriormente, con lo que dejarás
de verlas.
En la versión en español de Magno, al ver el intro en un editor
(en la versión en español y en la US, el offset es de la intro
es 0x7BC78) se verá:
Si te fijas bien dice:"...oscuridadXXXcierne..." en donde están
las tres 'X' debería decir " se ", para que el trozo completo
quede "...oscuridad se cierne...", pero como " se " ha aparecido
ya anteriormente donde dice "mientras se debilita" justo al principio,
pues sustituimos esas 4 letras por un puntero de 3 bytes a esa zona; esta es
la base del LZSS.
Como verás, es poco efectiva para trozos pequeños de texto, pero efectiva para datos repetitivos. Además, si cambias alguna letra de las que no están comprimidas (es decir, las que ves como texto ASCII), puedes que estropees toda la estructura de la compresión, puesto que de los tres bytes que forman el puntero LZSS, uno de ellos dice cuántos bytes vienen a continuación en texto sin comprimir, por lo que si añades o quitas uno a los comprimidos, puedes desalinear el algoritmo o la partida de la rom.
También hay problemas si sustituyes al azar alguno de los 3 bytes del
puntero por algún carácter especial que quiera ponerle, ya que
uno de esos bytes guarda información si lo que sigue a continuación,
si lo que sigue es un puntero o solo texto. Esto pasaría si por ejemplo
pusieras en una tabla la letra ñ como hex 80 ya que el hex 80 es muy
usado en este puntero, al menos en esta rom.
En cuanto al texto del juego, no tiene ninguna compresión, ni la fuente
tampoco; lo más difícil que tiene el juego es, sin duda alguna,
tanto la intro comprimida en LZSS.
La Intro original en ingles, el texto que sale es este:
darkness sweeps the
troubled land, as mana's
power fades...
people await a hero who
will wield the sword...
excalibur, herald, gigas...
the blade had many
names, for it has been
celebrated in myths and
leyends throughout time.
but all of these speak to
just one weapon:
the sword of mana.
Ahora si vamos al editor, vamos al offset 0x7BC78 (como se dijo en los antecedentes)
veremos esta intro en completo ASCII, como se ve abajo:
Esta será la intro que trabajaremos en esta guía.
Ahora si le aplicamos le aplicamos la siguiente tabla:
61=a
62=b
63=c
64=d
65=e
66=f
67=g
68=h
69=i
6A=j
6B=k
6C=l
6D=m
6E=n
6F=o
70=p
71=q
72=r
73=s
74=t
75=u
76=v
77=w
78=x
79=y
7A=z
20=
5E='
7B=.
7C=,
5F=:
(A0E0Eh)intro_texto
(92B19h)texto_inicio
(92A25h)texto_jugando
(7BC78h)intro principio
Es
decir, nos queda esto:
troubled land,`as mana's<80><1b><0e><09>
power fades...<82><2D><16>
people await a hero who<82><1a><09>
will wield<82><5A><80><65><02>ord<86><35><0b><02>
excalibur,`<80><31><01>al<80>g<03>giga<88>T<00><05>
<82>.<01>bl<80>e<01> h<80>~<02>had<82><82><00>y<82><19><0A>
names,`for <80>o<82><1d><03>been<82>m<07>
celebrat<80><b8><08>in myths
<80><c0><82><1a><05>
legend<82><e0><80><da><09>ghout
time<82>j<01><03>
b<80><0c><00>a<80><a7><01>of<82><a4><00>s<80><a6><05>peak
t<82><c1><10><08>
just one weapon:<80><13><00><07>
<8c><ca><82>2<83><19><82>F<8a><01><18><04>
P[\\]|[~<7f>`QRSTUV`co{|`ltd<82>$<00><06><82>g<07>rights
¿Por qué esta de color azul algunas partes? Estos son los punteros LZSS que debemos analizar antes de continuar.
Punteros LZSS. Regla de los 4 pasos
Un puntero LZSS es un grupo de 3 bytes seguidos (es decir de 24 Bits que enumeraremos del 0 al 23, 0 es el bit de mas a la izquierda y 23 el de mas a la derecha) que hacen referencia a otra parte de la ROM, puede ser un texto, un código (bajar una línea, línea en blanco, etc.), u otro puntero que a su vez nos puede llevar a otro lugar.
Hay excepciones, donde un puntero puede ser de 2 bytes, cuando hay 2 punteros seguidos, uno tras otro. El primero es solo de 2 bytes y el segundo de 3. Debido a que el 3er byte de un puntero indica la distancia al próximo puntero, y como es 0, entonces se omite. Ya lo verán con más detalle en esta sección.
15 = 00010101 b
1C = 00011100 b
1)- El bit más significativo (MSB) o primer bit está activo (a "1") cuando lo que viene a continuación son 23 bits de puntero, no de texto.
Aquí surge de inmediato un problema ya que si una letra de TEXTO es por ejemplo,
el hexadecimal 70, que convertido a binario sería 11100000, el primer bit es 1 lo que LZSS tomaría como un puntero y
no como texto.
Entonces necesitamos otro mecanismo para detectar dónde empieza un puntero y así distinguirlo del texto no referenciado (es decir, aquél que se obtendrá repetido de alguna parte anterior del texto).
2)- Este mecanismo lo aporta el tercer byte del puntero (desde el bit 16 al 23), que nos dice cuántos bytes vienen a continuación, de TEXTO en que NO aparecerá ningún puntero.
Esto tiene la limitación de que sólo puedes almacenar aquí 255 bytes de texto no referenciado (sin punteros). Esto es ya que si del 16 al 23 hay 1 byte de información, y un byte puede ir desde 00 a FF.
Por ejemplo si esta parte del puntero seria 00 quiere decir que después del puntero hay 0 bytes de texto puro.
Si seria FF, quiere decir que hay 255 bytes de texto puro. Es decir que después de 255 bytes limpios, debe seguir obligatoriamente un nuevo puntero.
3)- Nos falta por saber qué son los bits de en medio, es decir, los bits 1 al 15. Lo Dividimos en 2 grupos: del bit 1 al 6 y del 7 al 15 ya que nos distinta información.
Los 4 primeros bits de estos 15 indicaban (bit 1 al bit 6) cuántas letras tienes que copiar a partir de donde diga el puntero. Si tenemos 4 bits entonces podemos tener 26 = 64 valores máximos posibles, es decir, copiar 64 letras consecutivas de un texto que esta atrás del puntero. Pero como mínimo debes tener estos 6 bits con un 03 ya que eso nos dice que se copiaran 3 letras que equivalen a 24 bits. En total puedes copiar hasta 64+3 letras.
4)-El resto de bits (bit 7 al bit 15) indicaban los bytes antes del puntero que nos tenemos que desplazar para encontrar las letras repetidas.
Se puede desplazar desde 0 hasta 512
posiciones hacia atrás para encontrar una letra repetida.
Y: ‘Y’ bytes repetidos a leer. El Mínimo que se guarda en estos 6 bit es el valor 03h.
Z: ‘Z’ posiciones hacia atrás hemos de ir a leer los ‘Y’ bytes.
W: 'w' bytes siguientes en los que no aparecerá ningún puntero.
Tomamos de nuevo el texto que se ve en el editor, enumeramos las líneas para ir una a una analizando:
1. darkness sweeps the<80><27><18><04>
2. troubled land,`as mana's<80><1b><0e><09>
3. power fades...<82><2D><16>
4. people await a hero who<82><1a><09>
5. will wield<82><5A><80><65><02>ord<86><35><0b><02>
6. excalibur,`<80><31><01>al<80>g<03>giga<88>T<00><05>
7. <82>.<01>bl<80>e<01> h<80>~<02>had<82><82><00>y<82><19><0A>
8. names,`for <80>o<82><1d><03>been<82>m<07>
9. celebrat<80><b8><08>in myths <80><c0><82><1a><05>
10. legend<82><e0><80><da><09>ghout time<82>j<01><03>
11. b<80><0c><00>a<80><a7><01>of<82><a4><00>s<80><a6><05>peak
t<82><c1><10><08>
12. just one weapon:<80><13><00><07>
13. <8c><ca><82>2<83><19><82>F<8a><01><18><04>P[\\]|[~<7f>`QRSTUV`co{|`ltd<82>$<00><06><82>g<07>rights
Empecemos a analizar CADA línea:
80 27 18
Si estás usando la versión USA de la ROM, verás que si echas hacia atrás 39 posiciones desde la posición donde aparece el $80 (el puntero LZ) los tres bytes a leer son $00 03 02. Luego descifraremos que significan, ya que no es texto.
Ahora, sólo queda el $18 (18 hex
= 24 decimal) ese que es el tercer byte del puntero LZ; éste indica que los
próximos 24 bytes +1 (siempre se la suma 1) son de texto normal. Si lo miras
en el editor hexadecimal verás como 25 bytes después del puntero (parándote
en el 04 que esta justo después del puntero y cuéntalo desde allí como 0, 1…25)
más allá aparece un nuevo puntero LZ que es el <80><1B><0E>
(siguiente línea a analizar).
Como
verás en la INTRO, entre las líneas "darkness sweeps the" y "troubled
land, as mana's", hay una línea sin texto del tamaño de un tile 8x8; esa
línea en blanco se consigue con los tres bytes estos misteriosos que has copiado
con el puntero más el $04 ese que no sabemos qué significa; por tanto, cuando
encuentras $00 $03 $02 $04 quiere decir que hay una línea nueva, una línea en
blanco y algo más que no recuerdo muy bien.
2. troubled land,`as mana's<80><1b><0e><09>
80 1B 0E
Los 6 bits siguientes están en 0, pero le sumamos 3, quedando finalmente en 3.
Los siguientes bits son 000 00011011 = 1B hex = 27 decimal. Es decir que hay que ir 27 posiciones hacia atrás a copiar 3 bytes.
Los siguientes bits son 00001110 = 0E hex = 14 decimal. Es decir que después del puntero, 14+1 posiciones mas adelante estará el siguiente puntero. Párate en el 09 contando 0, luego sigue con 1, 2…y en la posición 15 estarás en el $82 del siguiente puntero que es <82><2D><16>.
Ahora
hay que descifrar que hay que copiar, si vamos hacia atrás 27 posiciones, contando
desde 1, nos encontramos con el puntero anterior <80><27><18>, pero alli no esta el puntero, allí esta el código descomprimido, sol oque
en el editor se ve el puro puntero.
Un puntero LZ nunca apunta a otro, solo a
código o letras.
Bueno,
alli se copia lo que esta descomprimido en 1. que es el código para bajar de línea y el llenado de la línea siguiente
de pantalla con una línea de tiles negros (sin texto).
Respuesta: pronto lo sabré, no lo tengo muy claro aun.
3. power fades...<82><2D><16>
Binario:
82 2D 16
Los 6 bits siguientes están en 0, pero le sumamos 3, entonces copiaremos 3 bytes.
Los siguientes bits son 0 00101101 = 45 decimal. Es decir que hay que ir 45 posiciones hacia atrás a copiar 3 bytes.
Los siguientes bits son 00010110 = 22 decimal. Es decir que después del puntero, 22+1 posiciones mas adelante estará el siguiente puntero.
Ahora hay que descifrar que hay que copiar, si vamos hacia atrás 45 posiciones constando desde 0, nos encontraremos con. 802718. al igual que el anterior (línea 2.), nos encontramos con el código descomprimo que reverenciaba el puntero mostrado en 1. Ya sabemos lo que hace, entonces sigamos.
Binario:
82 1A 9
Los 6 bits siguientes están en 0, pero le sumamos 3, entonces copiaremos 3 bytes.
Los siguientes bits son 0 00011010 = 26 decimal. Es decir que hay que ir 26 posiciones hacia atrás a copiar esos 3 bytes.
Los siguientes bits son 00001001 = 9 decimal. Es decir que después del puntero, 9+1 posiciones mas adelante estará el siguiente puntero.
Ahora hay que descifrar que hay que copiar, si vamos hacia atrás 26 posiciones nos encontraremos con 822D16, es decir, el puntero anterior. Ya sabemos lo que hace el puntero anterior, por lo que este hace exactamente lo mismo.
5. will wield<82><5A><80><65><02>ord<86><35><0b><02>
Tenemos aquí 5 bytes, y el puntero es SOLO de 3 bytes ¿qué pasa? Lo que pasa es estamos en un caso de Excepción ya que hay 2 punteros, uno seguido de otro. Según lo explicado en “Puntero LZSS” el primero puntero puede ser de 2 bytes y el segundo de 3 bytes, esto sucede aquí.
Puntero2: <80><65><02>
82 5A
Los 6 bits siguientes están en 00000001=1 decimal, pero le sumamos 3, entonces copiaremos 4 bytes.
Los siguientes bits son 0 01011010 = 90 decimal. Es decir que hay que ir 90 posiciones hacia atrás a copiar esos 4 bytes.
Los siguientes bits NO EXISTEN ya que este puntero esta atrás del segundo, y la distancia con el segundo puntero es 0.
Ahora hay que descifrar que hay que copiar, si vamos hacia atrás 90 posiciones, nos encontraremos con s de “sweeps the” de la linea 1.
Pero deberíamos copiar <espacio>the para que esto funcione (no se porque sucede esto).
Luego si copiamos los 4 bytes a partir del espacio tendríamos el texto “ the”.
80 65 02
Los 6 bits siguientes están en 0, pero le sumamos 3, entonces copiaremos 3 bytes.
Los siguientes bits son 0 01100101 = 101 decimal. Es decir que hay que ir 101 posiciones hacia atrás a copiar esos 3 bytes.
Los siguientes bits son 00000010 = 2 decimal, hay que ir 2+1 posición mas adelante para encontrar el siguiente puntero.
Ahora hay que descifrar que hay que copiar, si vamos hacia atrás 101 posiciones, nos encontraremos con TEXTO (en la e de darkness), por lo que se restan 3 bytes, entonces llegamos el espacio que esta justo después de “darkness<aqui>sweeps”.
Luego si copiamos los siguientes 3 bytes tendríamos el texto “ sw”.
SIIII, lo hicimos!!! (aplausos)
86 35 0B
Los 6 bits siguientes están en 000011 = 3 y le sumamos 3, entonces copiaremos 6 bytes.
Los siguientes bits son 0 00110101 = 53 decimal. Es decir que hay que ir 53 posiciones hacia atrás a copiar esos 6 bytes.
Los siguientes bits son 00001011 = 11 decimal, hay que ir 11+1 posición mas adelante para encontrar el siguiente puntero.
Ahora
hay que descifrar que hay que copiar, si vamos hacia atrás 53 posiciones, nos
encontraremos con des de “power fades…<82><2D><16>”, si
copiamos 6 letras estas son: des…
Aquí hay un error (que aun no entiendo cuando o porque sucede) ya que deberíamos copiar estos 6 bytes …<82><2D><16>, en vez de des… ya que después de “wield the sword” siguen 3 puntos (…) y luego el código para que baje, que seria <82><2D><16>. Por lo tanto, se copiaron 6 bytes que no corresponden, esto es debido a los bit 00110101 = 35 hex = 53 decimal, si hubiera sido 110010 = 50 decimal, seria perfecto ya que se copiarían: …<82><2D><16>, quedando la frase completa:
will wield the sword…
Los 6 bits siguientes están en 0 y le sumamos 3, entonces copiaremos 3 bytes.
Los siguientes bits son 0 00110001 = 49 decimal. Es decir que hay que ir 49 posiciones hacia atrás a copiar esos 3 bytes.
Los siguientes bits son 00000001 = 1 decimal, hay que ir 1+1=2 posiciones más adelante para encontrar el siguiente puntero.
Ahora
hay que descifrar que hay que copiar, si vamos hacia atrás 49 (debería ser 44
y no 49) posiciones, nos encontraremos
con her de “a hero who”. El texto a copiar es
her.
Tenemos entonces:
excalibur,`heral<80>g<03>giga<88>T<00><05>
Puntero 2: <80>g<03> pasa a ser <80><67><03> ya que g en el editor tiene el código 67.
En
binario: 10000000 01100111 00000011
Esta vez, vamos mas rápido ya que debes haber captado la idea:
6 bits siguientes en 0, entonces 0+3 bytes se copian.
Luego 01100111 binario = 103 decimal, volver 103 posiciones atrás a copiar 3 bytes, que a la vez son “ed “ de “troubled land”
Luego 00000011 binario = 3 decimal, entonces 3 posiciones mas adelante esta el próximo puntero.
Tenemos entonces:
excalibur,`heraled giga<88>T<00><05>
En
binario: 10001000 01010100 00000000
6 bits siguientes son 000100 = 4 decimal, entonces 4+3 = 7 bytes se copian.
Luego 01010100 binario = 84 decimal, volver 84 posiciones atrás a copiar 7 bytes, que a la vez son “r fades“ de “power fades”.
Otro error (no se porqué) ya que deberíamos copiar s…<82><2D><16> que están después de “fades…”
excalibur,`heraled gigas…<82><2D><16>
7. <82>.<01>bl<80>e<01>h<80>~<02>had<82><82><00>y<82><19><0A>
La línea y en rojo lo que los punteros copiaban desde atrás.
Puntero2: <80>E<01> pasa a ser <80><65><01>
Puntero3: <80>~<02> pasa a ser <80<7E><02>
Puntero4: <82><82><00>
Puntero5: <82><19><0A> ->puntero de fin de línea
the blade had many
8. names,`for <80>o<82><1d><03>been<82>m<07>
Puntero2: <82><1D><03>
Puntero3: <82>m<07> pasa a ser <82<6D><07> ->salto de línea
names, for it has
been
Puntero2: <80><C0> ->
puntero especial
Puntero3: <82><1A><05> ->puntero de fin de línea
celebrated in myths and
10. legend<82><e0><80><da><09>ghout
time<82>j<01><03>
Puntero2: <80><DA><09>
Puntero3:
<82>j<01> pasa a ser <82><6A><01> ->puntero de fin de línea
leyends throughout
time.
11. b<80><0c><00>a<80><a7><01>of<82><a4><00>s<80><a6><05>peak
t<82><c1><10><08>
Puntero1: <80><A7><01>
Puntero1: <82><A4><00>
Puntero1: <80><A6><05>
Puntero1: <82><C1><10> ->puntero de fin de línea
but all of these speak to
12. just one weapon:<80><13><00><07>
just one weapon: (queda igual ya que esta línea no tiene
letras comprimidas)
13. <8c><ca><82>2<83><19><82>F<8a><01><18><04>
-> linea de “the sword of mana”
P[\\]|[~<7f>`QRSTUV`co{|`ltd<82>$<00><06><82>g<07>rights
->esta es otra línea
Creo que aquí se acaba el intro, ya que sigue un <04> que debe ser fin de línea.
P[\\]|[~<7f>`QRSTUV`co{|`ltd<82>$<00><06><82>g<07>rights
es eso lo que se muestra después del intro “©1993, 1994 Square.”
the sword of mana. (toda la linea estaba comprimida)
Hay que saber varias cosas…pero quizás mas adelante pondré en la segunda parte de esta guía, creo que es mucho por hoy, ¿o no?
Ah, y ojalá que ustedes mismos hagan una descompresión de al menos 2 punteros. ¡no sean vagos!
V 1.0
by Dark-N. naldo_go@hotmail.com
volver
a Inicio