{"id":2961,"date":"2021-04-19T22:00:06","date_gmt":"2021-04-19T22:00:06","guid":{"rendered":"https:\/\/blog.rastersoft.com\/?p=2961"},"modified":"2023-12-25T19:47:07","modified_gmt":"2023-12-25T19:47:07","slug":"pintando-en-el-spectrum-16","status":"publish","type":"post","link":"https:\/\/blog.rastersoft.com\/?p=2961","title":{"rendered":"Pintando en el Spectrum (16)"},"content":{"rendered":"\n

Vamos ahora con el tema de los textos. Pintar letras no es algo demasiado complejo una vez que hemos pintado sprites, por lo que no voy a ahondar demasiado en ello. Sin embargo, s\u00ed hay un detalle que no es nada trivial, y es conseguir meter mucho<\/em> texto en poco espacio. En mi juego Escape from M.O.N.J.A.S.<\/em> ten\u00eda unos 10 kbytes de texto, y ten\u00eda el problema de que, sencillamente, no me cab\u00eda en la memoria. Sin embargo, el texto tiene la caracter\u00edstica de que tiene mucha redundancia, por lo que es muy compresible. As\u00ed que decid\u00ed intentar ir por esa ruta.<\/p>\n\n\n\n

Alguno pensar\u00e1 que comprimir datos en un Z80 a 3,5MHz es una quimera, algo totalmente imposible, por culpa de la poca potencia; sin embargo esto no tiene por qu\u00e9 ser as\u00ed: hay algoritmos en los que lo complicado es comprimir, pero la descompresi\u00f3n es muy sencilla y r\u00e1pida.<\/p>\n\n\n\n

El algoritmo que utilic\u00e9 fue el LZSS<\/a> (cuando hice la primera implementaci\u00f3n no sab\u00eda que se llamaba as\u00ed, pero es tan sencillo en concepto que era obvio que ten\u00eda que estar ya inventado). La idea es sustituir cada bloque que sea id\u00e9ntico a otro anterior por un par (offset, tama\u00f1o) que apunte a dicho bloque anterior. El ejemplo m\u00e1s t\u00edpico que se pone es el del poema Green Eggs and Ham<\/a>, y lo podemos ver explicado en la p\u00e1gina de la wikipedia.<\/p>\n\n\n\n

En mi caso me aprovecho adem\u00e1s de que los caracteres ASCII tienen todos el bit 7 a cero, por lo que puedo utilizar un byte con el bit 7 a uno para indicar que ah\u00ed comienza un bloque comprimido. Cada bloque comprimido est\u00e1 formado por dos bytes, y como el bit 7 del primero tiene que estar a uno, eso me deja 15 bits en total para almacenar el offset y el tama\u00f1o del bloque. Tras hacer varias pruebas, encontr\u00e9 que para mi cantidad de texto el tama\u00f1o \u00f3ptimo es de tres bits para el tama\u00f1o y 12 bits para el offset. Por supuesto, dado que no compensa comprimir bloques de tama\u00f1o cero, uno o dos, el valor almacenado ser\u00e1 el tama\u00f1o menos tres (o sea, entre 3 y 10). Adem\u00e1s, el offset ser\u00e1 siempre a partir del principio del bloque completo de textos, y no \u00abdesplazamiento hacia atr\u00e1s desde el punto actual\u00bb. El motivo de esto es que al principio es donde hay m\u00e1s texto sin comprimir, y, por tanto, donde habr\u00e1 m\u00e1s oportunidades de encontrar repetido texto de m\u00e1s adelante.<\/p>\n\n\n\n

Esta implementaci\u00f3n tiene varias cosas interesantes. Para empezar, es muy sencilla de implementar, y en segundo lugar, no necesita memoria intermedia para tablas (cosa que otros algoritmos, como el LZW, s\u00ed necesitan). Para simplificar a\u00fan m\u00e1s el algoritmo, habr\u00e1 una condici\u00f3n extra: no habr\u00e1 recursividad (esto es: dentro de un bloque comprimido no habr\u00e1 otros bloques comprimidos, sino que siempre apuntar\u00e1n a ristras de caracteres ASCII). Esto tiene el inconveniente de que la compresi\u00f3n es menor, pero simplifica sobremanera el algoritmo y reduce la memoria necesaria para la pila (y dado que trabajamos con threads<\/em>, interesa que este valor sea lo menor posible).<\/p>\n\n\n\n

Lo m\u00e1s interesante de este algoritmo as\u00ed descrito es que se puede utilizar al vuelo<\/em>; esto es: podemos ir imprimiendo los caracteres a medida que los vamos descomprimiendo. Y si le sumamos que una cadena ASCII normal es un bloque comprimido v\u00e1lido, tiene la ventaja extra de que podemos utilizar la misma funci\u00f3n para imprimir textos \u00abnormales\u00bb, sin comprimir.<\/p>\n\n\n\n

Habr\u00e1 una limitaci\u00f3n extra, y es que un bloque comprimido no puede jam\u00e1s cruzar la frontera entre dos \u00abfrases\u00bb o \u00abbloques de texto\u00bb. Esto es fundamental, pues si queremos poder descomprimir al vuelo<\/em> una frase, necesitamos que empiece en un byte concreto, y no en mitad de un bloque comprimido. As\u00ed, si tenemos estas tres frases:<\/p>\n\n\n\n

esta es la primera frase
la primera frase empieza en esta
es la primera que veo<\/p>\n\n\n\n

tenemos que respetar las fronteras entre frases y no comprimir el final de la segunda junto con el principio de la tercera en un \u00fanico bloque, pues entonces no podr\u00edamos descomprimir la tercera de manera independiente, sino que tendr\u00edamos que descomprimir la segunda antes, almacenando el resultado, y buscar el punto de uni\u00f3n.<\/p>\n\n\n\n

Por desgracia, si la descompresi\u00f3n es muy sencilla y r\u00e1pida, la compresi\u00f3n es endiabladamente fastidiada<\/em> (con jota). De hecho, por lo que he visto, ni siquiera parece existir un algoritmo \u00f3ptimo, sino s\u00f3lo diferentes aproximaciones. Esto puede chocar, pues en apariencia basta con empezar por el principio e ir buscando si el bloque de caracteres que sigue ya est\u00e1 repetido anteriormente. Sin embargo, por sorprendente que parezca, el orden de las frases puede afectar (y mucho) al nivel de compresi\u00f3n obtenido. Ve\u00e1moslo con este ejemplo:<\/p>\n\n\n\n

12345678
12345
345678<\/p>\n\n\n\n

Estas tres \u00abfrases\u00bb se pueden comprimir como<\/p>\n\n\n\n

12345678
(0,5)
(2,6)<\/p>\n\n\n\n

Esto es: la segunda frase es un bloque con los 5 caracteres que hay a partir del offset 0, y la tercera frase es un bloque con los 6 caracteres a partir del offset 2. En total, 12 bytes. Sin embargo, si reordenamos estas frases as\u00ed:<\/p>\n\n\n\n

12345
12345678
345678<\/p>\n\n\n\n

tenemos que la compresi\u00f3n ser\u00e1<\/p>\n\n\n\n

12345
(0,5)678
(2,3)(7,3)<\/p>\n\n\n\n

que consume 14 bytes.<\/p>\n\n\n\n

La soluci\u00f3n a esto ha sido ir probando a cambiar de sitio una frase de cada vez, recomprimir, y si le nivel de compresi\u00f3n es mejor, guardarlo y volver a probar, mientras que si el cambio es a peor, deshacerlo y probar de nuevo. Una peque\u00f1a mejora consiste en no deshacerlo con una probabilidad peque\u00f1a (el 0,1%), de manera que sea posible \u00abvolver atr\u00e1s\u00bb, y que el algoritmo pueda probar otros caminos lejos de un m\u00ednimo local, pero siempre conservando en memoria la mejor combinaci\u00f3n hallada hasta el momento. Esto tiene el inconveniente de que para conseguir altos niveles de compresi\u00f3n se necesita mucho tiempo (para los textos actuales dej\u00e9 mi PC trabajando unas 24 horas).<\/p>\n\n\n\n

Adem\u00e1s, existe otra optimizaci\u00f3n muy importante, que consiste en intentar comprimir antes los bloques de mayor tama\u00f1o, e ir probando luego con los de menor tama\u00f1o. As\u00ed, dado que el tama\u00f1o de un bloque puede ir de 3 a 10 bytes, primero busco todos los bloques de 10 bytes que puedo comprimir; una vez hallados, procedo a buscar en las cadenas sin comprimir que quedan los bloques de 9, luego los de 8, etc. Esto es importante porque puede ocurrir que por comprimir ahora<\/em> un bloque de 3, m\u00e1s adelante no pueda comprimir un bloque mayor. Aqu\u00ed tenemos un ejemplo:<\/p>\n\n\n\n

12345678
ab456dfg
b456df<\/p>\n\n\n\n

En este caso, si comprimo en el orden que aparece, tendr\u00e9<\/p>\n\n\n\n

12345678
ab(3,3)dfg
b(3,3)(12,3)<\/p>\n\n\n\n

que son 20 bytes, mientras que si comprimo por tama\u00f1o, tendr\u00e9:<\/p>\n\n\n\n

12345678
ab456dfg
(9,6)<\/p>\n\n\n\n

que son 18 bytes.<\/p>\n\n\n\n

La diferencia entre aplicar o no estas dos optimizaciones en brutal: sin ellas, consegu\u00eda una compresi\u00f3n del 68% aproximadamente, mientras que aplic\u00e1ndolas, los textos quedan reducidos a un valor en torno al 59,7%. Una diferencia abismal, que me permiti\u00f3 reducir los m\u00e1s de diez kilobytes originales en unos seis, y que entrase por fin todo en memoria.<\/p>\n\n\n\n

El compresor que escrib\u00ed, adem\u00e1s, parte de un fichero en formato assembler normal y saca el mismo fichero tambi\u00e9n en assembler pero con los datos comprimidos. Eso significa que se conservan las etiquetas, por lo que para descomprimir una frase s\u00f3lo hay que pasar la etiqueta correspondiente a la rutina de descompresi\u00f3n\/impresi\u00f3n, y listo.<\/p>\n\n\n\n

Queda, eso s\u00ed, un detallito especial, que es qu\u00e9 hacemos con los caracteres espec\u00edficos del espa\u00f1ol (la e\u00f1e y las aperturas de interrogaci\u00f3n y exclamaci\u00f3n; las tildes decid\u00ed obviarlas). La soluci\u00f3n que se me ocurri\u00f3 fue mapearlas en caracteres por debajo de 127 que no se utilicen, como el asterisco, el porcentaje, etc, reemplaz\u00e1ndolos en el juego de caracteres del Spectrum. Por supuesto, para simplificar el trabajo, el compresor tambi\u00e9n se encarga de esta tarea, por lo que en el c\u00f3digo fuente original los textos ir\u00e1n en UTF-8, y el compresor se encargar\u00e1 de sustituir la e\u00f1e por el asterisco, etc.<\/p>\n\n\n\n

El c\u00f3digo fuente est\u00e1 en el fichero convert_sentences.py<\/em> en el repositorio de Escape from M.O.N.J.A.S.<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

Vamos ahora con el tema de los textos. Pintar letras no es algo demasiado complejo una vez que hemos pintado sprites, por lo que no voy a ahondar demasiado en ello. Sin embargo, s\u00ed hay un detalle que no es nada trivial, y es conseguir meter mucho texto en poco espacio. En mi juego Escape … Seguir leyendo Pintando en el Spectrum (16)<\/span> →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5,17,6,7],"tags":[20],"class_list":["post-2961","post","type-post","status-publish","format-standard","hentry","category-programacion","category-retrocomputacion","category-trucos","category-tutoriales","tag-pintando-en-el-spectrum"],"_links":{"self":[{"href":"https:\/\/blog.rastersoft.com\/index.php?rest_route=\/wp\/v2\/posts\/2961","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.rastersoft.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.rastersoft.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.rastersoft.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.rastersoft.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2961"}],"version-history":[{"count":7,"href":"https:\/\/blog.rastersoft.com\/index.php?rest_route=\/wp\/v2\/posts\/2961\/revisions"}],"predecessor-version":[{"id":3035,"href":"https:\/\/blog.rastersoft.com\/index.php?rest_route=\/wp\/v2\/posts\/2961\/revisions\/3035"}],"wp:attachment":[{"href":"https:\/\/blog.rastersoft.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2961"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.rastersoft.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2961"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.rastersoft.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2961"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}