Como ya comenté, decidí reemplazar el cargador original del Atmega32U4, llamado DFU y que se puede descargar desde la página de Atmega, por Ubaboot, un bootloader reducido que sólo ocupa 512 bytes y que es muy sencillo de utilizar. A mayores envié dos parches para simplificarlo aún más:
Para instalar Ubaboot, lo primero que hay que hacer es editar el fichero config.h y configurar los parámetros de nuestra placa. En el caso de mi teclado, hay que descomentar OSC_MHZ_16 (pues el reloj es de 16MHz), y USB_REGULATOR:
Una vez hecho esto, hay que programar los fuses del microcontrolador para un bootloader de 512bytes, además de asegurarnos de configurar bien el resto. En el caso de mi teclado, la configuración es la siguiente:
Fuse LOW: 0x5E
CKDIV8 0
CKOUT 1
SUT1/0 = 0x01
CKSEL3/0 = 0x0E
En este bloque básicamente no tocamos nada.
Fuse HIGH: 0xDE
OCDEN 1 (desactivado)
JTAGEN 1 (JTAG desactivado)
SPIEN 0 (programación por SPI activada)
WDTON 1 (watchdog desactivado)
EESAVE 1 (preservar EEPROM al borrar la memoria)
BOOTSZ1/0 0x11 (bootloader de 512 bytes)
BOOTRST 0 (vector de reset apunta al bootloader)
En este bloque básicamente desactivamos el JTAG, pues no lo necesitamos para nada, ponemos la dirección de inicio del cargador a 512 bytes antes del final de la memoria, y por último configuramos el vector de reset para que salte al cargador directamente. Esto último es muy importante, pues el propio cargador detecta si estamos arrancando «en frío» (en cuyo caso saltará a nuestro código directamente) o si hemos pulsado el botón de reset (en cuyo caso entrará en modo programación).
Fuse EXTRA: 0xFE
RESERVADO 7/4 tienen que estar todos a 1 (0xF)
HWBE 1
BODLEVEL2/0 0x1 (EDITADO)
El entorno de Arduino me había cambiado el BODLEVEL a 110 (1,8 a 2,2 voltios), en lugar del original 011 (2,4 a 2,8 voltios). Tras algunas pruebas, y en base a mi experiencia, he decidido que es más seguro ponerlo a 001 (3,3 a 3,7 voltios). Esto es algo que he cambiado en este artículo después de haberlo publicado.
El siguiente paso es conectar un programador SPI al teclado a través de los pines correspondientes. Yo uso un BusPirate que me prestaron, para lo cual tuve que editar el fichero Makefile y sustituir usbtiny -B10 por buspirate -P /dev/ttyUSB0 -b 115200, además de instalar AVRdude y el resto de utilidades de AVR. Con esto ya sólo me queda conectarlo al teclado y ya puedo leer el estado con
y hacer make y make program para grabar el Ubaboot. Con él grabado, sólo tengo que pulsar el boton de RESET del teclado y se pone automáticamente en modo programación por USB, con lo que ya no necesito más el BusPirate.
Y ya, por último, instalé Arduino y Teensyduino para disponer de las bibliotecas de USB. Sin embargo, hice un pequeño cambio para integrar la programación mejor. Los cambios concretos están descritos en el fichero README del segundo parche que envié a Ubaboot.
Y con esto escribí la primera versión del software de mi teclado, pero eso lo comentaré con calma en otra entrada.
Acabo de subir la revisión 1.7 de la placa del teclado. Uno de los cambios más importantes ha sido conectar una de las columnas del teclado desde el puerto PE2 al PB7. Para entender el motivo, primero necesitamos entender cómo es el proceso de arranque del Atmega32Ux.
El procesador Atmega32Ux permite añadir un bootloader y arrancarlo en determinadas circunstancias. Hay varias posibilidades:
Llamarlo manualmente desde el programa principal (útil para cambiar a modo programación de manera «manual»)
Llamarlo siempre que se resetee el procesador
Llamarlo tras un reset si se da cierta condición externa
Y esta última es la clave: esa condición externa es que el pin PE2 esté a nivel bajo en el momento de ocurrir el reset. Esto permite que, por defecto, se arranque el código principal, pero si se desea arrancar el bootloader, sólo haya que conectar dicho pin a masa y pulsar reset.
Pues bien, hasta ahora yo utilizaba dicho pin para una de las columnas del teclado simplemente por comodidad de diseño: al hacer el enrutado de las pistas, era más sencillo utilizar ese pin que otro.
El problema es que la placa Teensy 2.0, que es la que lleva el mismo procesador, tiene ese pin permanentemente conectado a masa a través de un pull-down y, además, no está conectado al exterior. Eso significa que en las bibliotecas de teensyduino no está disponible la opción de utilizar dicho pin.
Por simplicidad, yo quería mantener la compatibilidad con la Teensy 2.0 porque me da un entorno de programación y bibliotecas listas para utilizar, lo que simplifica mucho el trabajo, pero este problema me obligaba a rediseñar la placa, algo que no me apetecía mucho porque ya mandé fabricarlas y, aunque la versión actual es mucho más avanzada que la que tengo físicamente, los cambios hechos hasta ahora eran cosméticos y no afectaban a la lógica en sí, mientras que éste sí implicaba un cambio en la lógica de funcionamiento.
Decidí ver qué alternativas tenía, y descubrí que las placas Arduino Leonardo y Arduino Micro también utilizaban el mismo micro, así que decidí echar un vistazo a ver si podía utilizarlas. Al principio tenía buena pinta porque el bootloader estaba disponible, por lo que podía convertir mi teclado en un Arduino «con todas las de la ley». Por desgracia, la alegría no duró mucho: en el caso del Micro, el pin PE2 tampoco estaba conectado al exterior, con lo que estaba en las mismas. Aún peor: otros dos de los pines que utilizo en el teclado están asignados a LEDs, con lo que probablemente no tendría mucha libertad a la hora de utilizarlos. En el caso del Leonardo, tres cuartos de lo mismo.
Al final no me quedó otra que cortar la pista que conectaba PE2, y añadir dos puentes: uno entre PB7 y la pista original, y otra entre masa y una resistencia conectada a PE2.
Probando otros bootloaders
A pesar de todo, decidí probar el bootloader de Arduino, por si era más cómodo que el ubaboot que estaba utilizando hasta ese momento. Arranqué el editor Arduino IDE, configuré una placa Leonardo, le indiqué que tenía un programador Bus Pirate, y le di a Quemar bootloader. Varios minutos (sí, sí… tarda un muy buen rato y no muestra nada en pantalla que indique progreso) finalizó la grabación. Lo primero que descubrí es que me había cambiado los fuses del Atmega, algo que no me gustó mucho porque algunos flags eran… raros. Por ejemplo, me activaba el divisor entre ocho del cuarzo, lo que supone que la CPU va más lenta. Pero lo más raro es que pone a cero los bits 4 y 5 del byte extendido, los cuales se supone que no se deben escribir, y deben estar siempre a 1. Lo peor es que no soy capaz de devolverlos a su estado normal.
Tras varias pruebas, no me acabó de convencer el bootloader, así que volví al ubaboot de nuevo, pero esta vez quería asegurarme de corregir un par de problemas que tenía, y es que al pulsar el botón de reset para entrar en modo programación, no siempre funcionaba, sino que normalmente tenía que darle dos o tres veces antes de que el identificador USB fuese el de OpenMoko en lugar del de Teensy. Por otro lado, al darle la orden de reiniciar desde el programador ubaboot, el USB dejaba de funcionar.
Al final, tras echar un vistazo al código fuente, me di cuenta de que este bootloader espera ser llamado siempre durante el arranque, lo que significa que hay que poner a cero el bit 0 del Fuse High Byte, el flag BOOTRST. De esta manera, siempre arrancará desde el bootloader, y si éste detecta que el procesador está arrancando por haber sido conectado a la corriente, saltará directamente al código principal, y sólo entrará en modo bootloader si se pulsó el botón de reset.
Con estos cambios ya puedo programar fácilmente la placa del teclado: simplemente tengo que instalar Teensyduino para disponer de todas las bibliotecas, indicar al IDE que tengo un Teensy 2.0, y cada vez que compile, fijarme en donde ha almacenado el fichero hex con el código objeto (normalmente en /tmp/arduino_build_XXXXXX, y utilizar el comando
Hace tiempo que quiero construirme un portátil/cyberdeck alrededor de una Raspberry Pi 4, y basado en el diseño del Z88 de Sinclair/Cambridge Computers. Sin embargo, algo que tengo muy claro es que quiero un teclado completo, no uno de portátil, pues, como programador, suelo utilizar mucho las teclas SUPR, INICIO, FIN, RePAG y AvPAG, y en los portátiles algunas necesitan combinarse con Fn.
La primera opción sería utilizar un diseño TenKeyless, también conocido como «teclado 87%», como éste (pero sin lucecitas):
Sin embargo, hay mucho espacio desaprovechado. Así que sopesé utilizar un diseño «75%», como éste de Keychron:
Pero no tenía a mano la tecla de Imprimir pantalla, que uso mucho, ni tampoco la de SysReq, que utilizo de vez en cuando, así que tampoco me convencía.
Al final, después de mucho pensarlo, me decidí por hacer mi propio diseño, y ésta es la distribución final que decidí:
Como se puede ver, tiene todas las teclas de un Tenkeyless, pero es muchísimo más compacto. E incluso tiene una tecla de Fn para funciones no tan comunes, como subir y bajar el volumen. Todo ventajas.
Decidí construir uno en plan «barato», y para ello utilicé pulsadores de circuito impreso y los capuchones de un teclado que compré en el chino el bazar de al lado de casa, y lo conecté directamente a los pines de E/S de la raspberry. Este fue el resultado:
La distribución era buena, pero el tacto… en fin… hace unos treinta años había construido un teclado para mi Spectrum utilizando el mismo tipo de pulsadores, y no recordaba que fuese tan malo 🤣
Pero ya tenía el gusanillo, así que decidí coger el toro por los cuernos y diseñar un teclado en condiciones. Para ello partí de un diseño básico creado mediante el programa Klepcbgen, de Jeroen Bouwens, al que hice varios cambios para permitir, entre otras cosas, utilizar diodos normales en lugar de la versión de montaje superficial. A partir de ahí seguí puliendo el diseño hasta llegar a la versión 1.5 de mi teclado, que está disponible en mi repositorio de gitlab.
En el diseño utilicé un Atmega32U4, el mismo que se utiliza en las placas Teensy 2.0. El motivo es que son las placas que más se utilizan para diseños de teclados propios, por lo que podría reutilizar mucho software. Además, incluí, como se puede ver en la imagen de arriba, dos filas de 10 pads cada una en donde están disponibles las filas y columnas del teclado. Esto permite conectar la misma placa a un microcontrolador externo (o, en mi caso, directamente a los pines de E/S de la Raspberry PI) en lugar de utilizar el incorporado en la placa.
La primera dificultad fue donde colocar el microcontrolador. Al principio junté todas las teclas de la primera fila hacia la izquierda y coloqué el microcontrolador y el conector USB arriba a la derecha, por el lado inferior de la placa. Esto tenía la ventaja de que las pistas del par diferencial del USB eran lo más cortas posible, y además me dejaba sitio para un NeoPixel en la esquina superior derecha, pero tenía el inconveniente de que la estética de la colocación de las teclas no era muy allá, además de que, por el espacio disponible, la placa sobresalía bastante por arriba.
Ante esto, decidí intentar mover el microcontrolador a otra zona, en este caso debajo de la barra espaciadora, donde había mucho espacio libre, y así poder mover el conector USB un poco más hacia las teclas. Sin embargo, me preocupaba que las pistas del par diferencial serían muy largas… ¿daría problemas con el USB?
Decidí informarme, así que me descargué la especificación del estándar USB 1.1 y descubrí que el par diferencial tiene que tener una impedancia de 90 ohmios +/- 15%. Ante esto, utilicé la herramienta de cálculo de Kicad para líneas de transmisión, y me salió que tenía que utilizar una anchura de pista de 0,9 milímetros (sí, bastante ancha):
De todas formas, mi intención era utilizar el modo low-speed, de 1,5Mbps en lugar del full-speed de 12Mbps, por lo que lo más probable es que incluso unas pistas sin ajustar funcionasen correctamente; pero decidí no arriesgarme e intentar hacer las cosas bien. Aquí, además, conté con la inestimable ayuda de mis compañeros de A Industriosa, que me resolvieron todas mis dudas sobre diseño con Kicad. A fin de cuentas, soy programador, no electrónico.
Para hacer bien un par diferencial, lo primero es definir una malla específica para él en las clases de red. De esta manera podremos estar seguros de que los parámetros de las pistas serán correctos:
Para trazar el par, tenemos que utilizar la herramienta específica. Ella nos permite asegurarnos de que ambas pistas están siempre a la distancia correcta:
Una vez trazado el par, veremos que los ángulos son rectos (de 45 o 90 grados), cosa que no es buena. Para solucionar esto sólo tenemos que escoger dos segmentos consecutivos, darle al botón derecho, y escoger pistas de filete. Nos preguntará un valor para el radio, y una vez aceptado, añadirá una esquina curva entre las dos pistas. Aquí tenemos un ejemplo de una esquina ya con el filete, y la esquina paralela aún sin él:
Yo utilicé un radio de 3 milímetros para las curvas internas. Sin embargo, es importante recordar que las curvas deben ser concéntricas, lo que significa que las curvas externas tienen que tener un radio mayor. Dicho radio debe ser radio_interior + ancho_de_pista + separación_de_pista. En mi caso, con un radio interior de 3 milímetros, un ancho de pista de 0,9 milímetros, y una separación de pista de 0,2 milímetros, el resultado es que para los radios exteriores tengo que utilizar un radio de 4,1 milímetros. Y así queda:
Sin embargo, si seleccionamos cada una de las dos pistas del par y nos fijamos en el parámetro Longitud enrutada de cada una, veremos que la longitud no es la misma. Aunque la diferencia es pequeña (casi dos milímetros), quise hacer las cosas bien, así que utilicé la herramienta de Afinar desvío de un par diferencial para asegurarme de que la diferencia de distancias estuviese por debajo de una décima de milímetro:
Esta herramienta añade unas ondulaciones en la pista, de manera que la distancia sea correcta a la vez que se mantiene la impedancia:
Distribuciones de teclado
Durante todo el diseño inicial mantuve una distribución ISO de las teclas, pues es la que yo voy a utilizar. Sin embargo, dado que iba a publicarlo todo bajo una licencia libre, decidí intentar hacer una placa dual, que permitiese montar también una distribución ANSI de teclas. Sin embargo, me encontré con el problema de que había un par de agujeros que quedaban bastante cerca y no veía claro que los estabilizadores que iban en ellos quedasen bien anclados, por lo que ese diseño no parecía una buena idea. Pese a todo, quería poder tener ambas distribuciones, así que al final se me ocurrió una idea relativamente sencilla: en main tendría la placa dual, y luego tendría dos ramas, una para cada distribución, que mantendría actualizadas a partir de main. Al principio era bastante peñazo porque, al quitar los pulsadores que sobraban, quedaban muchas pistas mal situadas, lo que me obligaba a ajustar bastante ambos diseños antes de poder hacer el merge; pero después de afinar la placa dual conseguí solucionar esos problemas, y ahora me lleva segundos actualizar cada rama.
Distribución ISO renderizada desde KicadDistribución ANSI renderizada desde Kicad
Otros detalles que añadí fueron un conjunto de pads para un programador de Atmega (ese grupo de dos por tres que se ven junto al microcontrolador), dos pads conectados a PE2 y masa para que, al cortocircuitarlos, se pueda entrar en el modo de carga del bootloader de Atmega (que son esos dos que se ven entre el pulsador del espacio y el microcontrolador, y que está etiquetado por debajo como bootloader), y dos pads más para dos pines de E/S que me quedaban libres (PE6 y PB0), pues puede ser interesante aprovecharlos. Teniendo en cuenta que PB1, PB2 y PB3 ya están disponibles en el conector del programador, el resultado es que casi todos los pines de E/S del microcontrolador están accesibles a través de pads. La única excepción es PB7, que se quedó tan encerrado que no encontré una manera razonable de extraer una pista. Es cierto que podría hacer sitio eliminando C7, el condensador de reset, pero la verdad es que no me parece tan necesario poder acceder a ese pin. Ese condensador lo añadí únicamente por si acaso, pero realmente no es buena idea ponerlo pues, al generar un reset automático al enchufar la placa, impide aprovechar la característica de entrar en modo depuración tras un reset del bootloader.
También incluí un rectángulo en blanco en cada lado de la placa, lo que permite hacer anotaciones con un rotulador.
Protección contra sobretensiones
Al principio no tuve en cuenta la necesidad de proteger contra sobretensiones en el bus USB. A fin de cuentas, aunque en la documentación del Atmega32U4 dicen que es recomendable añadirla, no aparecía en ninguno de los diseños de referencia que incluían. Es más: la propia placa Teensy 2.0 no incluye ningún tipo de protección, sino que los dos pines del microcontrolador van a pelo al conector.
Sin embargo, un compañero de AIndustriosa me recomendó encarecidamente que la añadiese, pues parece ser que es habitual que en los conectores USB de los equipos de sobremesa (cuya alimentación va directa a la fuente) haya picos de tensión en determinadas circunstancias. Le eché un vistazo a las opciones que me daba Kicad, y me encontré con que casi todas eran diminutas: algunos chips medían aproximadamente un milímetro de largo… algo imposible de soldar a mano. Afortunadamente había otras opciones, y al final me quedé con el USB6B1, pues además de estar pensado específicamente para USB, tiene un patillaje que simplifica el diseño.
Reloj, o no reloj… he ahí la cuestión
Cuando estaba haciendo el diseño original descubrí que el Atmega32U4 incluye un oscilador RC que viene calibrado de fábrica de manera que su precisión es suficiente para que el USB funcione en modo low-speed. Dado que meter un cuarzo de 16MHz me asustaba bastante (es una frecuencia relativamente alta, y yo no soy para nada un experto en diseño electrónico), decidí que sería mejor hacer un sistema sin cuarzo externo, y utilizar sólo el oscilador RC interno. Sin embargo, a la vez, temía que hubiese algún problema, así que al final decidí que no usaría cuarzo, pero dejaría hechas las pistas para poder poner uno de ser necesario.
¡Menos mal que lo hice! Cuando monté la primera placa y quise programar el micro, descubrí que no funcionaba. Al principio pensé que podía ser un problema con el programador que estaba utilizando, un Bus Pirate, pero después de probar y probar una y otra vez, y de leerme la documentación repetidamente, descubrí que la programación mediante el puerto SPI (que es lo que estaba usando) necesita que haya un reloj activo para funcionar. Pero para que el chip utilizase el RC interno necesitaba programar los fuses de configuración, para lo cual… necesitaba un reloj activo… El huevo y la gallina. Fue aquí cuando descubrí que se vendían dos modelos: el Atmega32U4 a secas, que viene configurado de fábrica para trabajar con un cuarzo externo, y el Atmega32U4RC, idéntico en absolutamente todo excepto en que, de fábrica, viene configurado para trabajar con el oscilador RC interno. Adivinad cual había encargado yo…
Decidí no desesperarme y buscar una solución, así que intenté utilizar la interfaz JTAG para programarlo, confiando en que esa no necesitase un reloj externo. A fin de cuentas, el Bus Pirate es un dispositivo programable, y soporta todo tipo de interfaces…
O no, porque como como estaban justos de espacio de código en el microcontrolador, en las últimas revisiones eliminaron el soporte de JTAG. A fin de cuentas, «era demasiado lento para ser útil» 😡
Revisé el código y ahí estaba… y además se estaba compilando en el binario que estaba grabando, pero no aparecía en la lista de protocolos soportados. No entendía qué estaba pasando.
Encima, leyendo bien la documentación descubrí que el oscilador RC está calibrado para una tensión de trabajo de 3 voltios, cuando yo estaba alimentando el Atmega con 5. Eso me obligaba a recalibrarlo antes de poder usarlo.
Al final me cansé, me fui a la tienda de electrónica de mi ciudad y me compré un cuarzo de 16MHz por 60 míseros céntimos de euro, lo soldé, y se acabaron mis problemas: el teclado aparece como un dispositivo OpenMoko (porque, además, antes del cuarzo de 16MHz le puse, por error, uno de 12MHz pensando que era esa la frecuencia correcta, en base a los 12Mbps del bus USB; pero no…), y como no aparecía el dispositivo, probé a grabar un bootloader diferente del que trae de fábrica: UdaBoot.
Moraleja: no compensa ahorrarse unos céntimos.
¿Y ahora?
Ahora me queda la parte de programar el micro para que se comporte como un teclado, además de ver cómo puedo publicar a través de HID el NeoPixel, de manera que sea fácilmente controlable mediante software. Una vez hecho esto, montaré dos teclados más, y diseñaré la carcasa para el portátil, y una carcasa independiente para poder utilizar este teclado en mis ordenadores de casa.
Si lo comparamos con el diseño anterior, éste está mucho más pulido porque incluye las lengüetas de carga y agujeros para pasar los cables. También tiene una ranura por debajo, de manera que los cables quedan completamente ocultos.
El diseño, además, está completamente acotado, por lo que es muy sencillo ajustarlo para otros tamaños de cascos. Así, la diadema de mis cascos mide 35 milímetros de ancho, por lo que la separación entre las lengüetas está ajustada a 33 milímetros, de manera que se garantiza que siempre hará contacto al colgarlos. Pero si queremos utilizarlo con otros cascos, sólo tenemos que editar esa medida para ajustarlo al valor necesario.
Así quedó tras imprimirlo en un tono anaranjado que hace juego con la madera del mueble donde va a ir atornillado, y tras pegarle cinta adhesiva de cobre en las lengüetas para hacerlas conductoras:
El siguiente paso fue meter los cables del transformador por cada uno de los agujeros, y soldarlos al cobre. La mejor manera de hacerlo es estañar primero el punto en el que vamos a soldar el cable, cortar el cable a la longitud correcta, estañar la punta, meterlo por el agujero, y simplemente con un pequeño toque del soldador, unir ambas partes. Así evitaremos recalentar demasiado el plástico y que se derrita o deforme.
Por último, añadimos un poco de cola térmica en la guía de la base para que el cable quede firme y evitar que un tirón lo arranque de las lengüetas:
Hace tiempo me compré una tableta de dibujo de estas para «pintar con lápiz», pero por desgracia nunca la pude usar porque no funcionaba correctamente en Linux: al mover el lápiz, el cursor del ratón se movía correctamente, pero no hacía nada cuando tocaba sobre la superficie ni cuando pulsaba los botones del lápiz. Sin embargo, como estos días tenía algo de tiempo libre, decidí ponerme con ella a ver qué podía descubrir, y si conseguía resolver el problema.
La tableta de dibujo
Lo primero que hice fue echar un vistazo a la información de lsusb. Ahí puede ver el código del fabricante y el del dispositivo:
Bus 002 Device 006: ID 2179:0004 UGTABLET TABLET WP5540
Decidí entonces que podría probarla en Windows, a ver si era un problema de la tableta en sí. Para ello instalé uno en una máquina virtual y configuré un filtro USB para que redirigiese la tableta a éste tan pronto se enchufase, y evitar así interferencias desde Linux.
Y funcionó perfectamente: si movía el lápiz a unos milímetros de la superficie, el cursor se movía igual que en Linux, pero si lo apoyaba, Windows identificaba una pulsación de botón de ratón y podía seleccionar iconos, cosa que en Linux no ocurría. Los dos botones del lápiz también funcionaban como el botón derecho y central del ratón.
Por supuesto, dado que la tablet medio funcionaba en Linux, yo supuse que debía seguir el estándar USB HID, pero que habría algo que se salía de él y Linux no era capaz de identificar correctamente. O bien podría ser que hubiese que configurar primero de alguna manera la tableta, y que Windows lo estuviese haciendo bien y Linux no.
Esnifando paquetes USB
Decidí comprobar primero la segunda posibilidad. Para ello desenchufé primero la tableta y cargué el módulo usbmon con:
sudo modprobe usbmon
Luego lancé Wireshark, empecé a capturar desde el puerto 2 de USB (pues, si vemos la salida de lsusb, es en él en donde está el puerto que usé), conecté la tableta, e hice algunos movimientos con el lápiz sin apoyar y apoyado en la superficie.
Hecho esto, detuve la captura, desconecté la tableta, apagué la máquina virtual, e hice una nueva captura, para ver qué hacía Linux. Luego abrí ambas capturas, cada una en una ventana diferente, y filtré los paquetes de la tableta con:
usb.bus_id == X&& usb.device_address == YY
Siendo X el bus en el que estaba conectada la tableta, e YY el identificador que se le asignó en cada momento.
El resultado no fue nada conclusivo, pues en ambas capturas salía más o menos lo mismo: primero se piden los datos básicos del dispositivo, luego la configuración completa (donde pone que es un dispositivo HID), algunas cosas más sin importancia, y finalmente lee el HID Report, donde vienen los datos HID para configurar el dispositivo. Tanto en Windows como en Linux eran exactamente iguales, por lo que no parecían ir por ahí los tiros. Una vez hecho todo esto, el resto de datos se enviaban sólo desde la tableta hacia el ordenador en forma de interrupciones USB, y parecían bastante similares entre ambos sistemas operativos.
Llegados a este punto no podía hacer mucho más, porque no sabía nada sobre el estándar HID ni sobre el significado de cada byte que se estaba enviando sobre el cable, así que decidí hacer un alto y leerme la documentación oficial de HID (una lectura amena y tremendamente divertida, como cualquier documentación oficial 😝 ).
El estándar HID
La idea detrás de HID es crear un protocolo que permita definir absolutamente cualquier dispositivo de interfaz humana, tanto actual como futuro, y hacerlo además de una manera que permita que cada fabricante lo implemente casi de la manera que quiera. Para ello, un dispositivo HID simplemente tiene que definir un HID Report, que no es más que una tabla donde se definen qué tipos de entrada tiene, y poco más. Dicha tabla puede estar definida directamente en ROM, lo que simplifica mucho el diseño.
¿Y qué contiene dicha tabla? Pues básicamente una serie de entradas en las que se define, para cada posible sensor o actuador del dispositivo:
Tipo (por ejemplo: Eje X relativo, Tecla Y, presión…)
Número de bits que ocupa el dato (el bit inicial se deduce de la propia lista)
Rango físico y lógico
Y algunas cosas más. Además, las entradas se pueden agrupar por tipo de dispositivo, de manera que no es lo mismo un botón de ratón que un botón de teclado, y asignarle un identificador a cada grupo.
En el caso de mi tableta, la tabla HID es así:
Uso digitizer (id: 0x07)
Punta de lápiz: 1 bit
Botón de lápiz: 1 bit
Goma de borrar de lápiz: 1 bit
No usados: 2 bits
Lápiz dentro de rango: 1 bit
No usados: 2 bits
Eje X: 16 bits
rango físico: 0, 5500
rango lógico: 0, 22000
Eje Y: 16 bits
rango físico: 0, 4000
rango lógico: 0, 16000
Uso mouse (id: 0x08)
Botón 1: 1 bit
Botón 2: 1 bit
Botón 3: 1 bit
No usados: 5 bits
Eje X relativo: 8 bits
rango lógico: -127, 127
Eje Y relativo: 8 bits
rango lógico: -127, 127
Rueda de ratón: 8 bits
rango lógico: -127, 127
No usados: 8 bits
Uso mouse (id: 0x09)
Botón 1: 1 bit
Botón 2: 1 bit
Botón 3: 1 bit
No usados: 5 bits
Eje X absoluto: 16 bits
rango lógico: 0, 32767
Eje Y absoluto: 16 bits
rango lógico: 0, 32767
Presión del lápiz: 16 bits
rango lógico: 0, 1023
Con esta tabla a mano, si nos llega un bloque de interrupción con los siguientes valores:
09 00 5d 49 05 56 00 00
Podemos deducir fácilmente su significado: el primer byte es el uso, por lo que, al ser 9, tenemos que fijarnos en el último de los tres bloque de la tabla. El primer byte contiene el estado de tres botones de tipo ratón, pero como los bits correspondientes son 0, significa que no están pulsados. Los dos siguientes bytes son la posición del lápiz en el eje X, los dos siguientes la posición en el eje Y, y los dos últimos la presión. Fácil.
La cuestión es que tanto en Windows como en Linux los datos que se enviaban eran exactamente iguales: si tocaba con el lápiz en la superficie se activaba el bit 0 del primer byte y aparecía un valor en los dos últimos bytes, que aumentaba con la presión que ejercía. Si pulsaba alguno de los dos botones en el lápiz se activaban los bits 1 o 2 del primer byte… todo era correcto, salvo por el detalle de que Linux no hacía caso. Incluso escribí un pequeño programa en python para leer e interpretar los datos en tiempo real desde la interfaz usbmon, y todo era correcto: los datos se enviaban correctamente, y siempre era con bloques de tipo 9.
De hecho, no podía evitar preguntarme por qué había dos entradas de tipo ratón, y sobre todo por qué una de ellas tenía ejes relativos. La respuesta se me ocurrió de casualidad: este chip sirve para tabletas híbridas, donde se puede usar un lápiz o un ratón:
Ejemplo de tableta con lápiz y ratón
Eso explicaba los dos tipos: si se usaba el ratón, se emitirían interrupciones con el tipo 0x08, y si se usa el lápiz entonces serían de tipo 0x09. Y el tipo 0x07 supongo que sería para algún tipo de lápiz diferente.
Vamos al kernel
Llegados a este punto comprendí que el problema tenía que estar, necesariamente, en el driver HID de Linux, así que descargué las fuentes del kernel, las compilé y las instalé en mi Debian con:
make localmodconfig # copia la configuración del kernel actual make -j5 make deb-pkg -j5 # crea paquetes .deb
Y con ello, me fui al fichero hid-input.c. En él encontré el punto en el que procesa la tabla HID y descubrí un detalle interesante hacia el final de la función:
¡Si un evento estaba duplicado, parecía ignorarlo a menos que se activase HID_QUIRK_INCREMENT_USAGE_ON_DUPLICATE! Esto tenía buena pinta, porque, efectivamente, los eventos de pulsación de ratón están duplicados en el bloque 8 y en el 9. Probé a añadir el Quirk para mi tableta en el fichero hid-quirks.c, compilé, desmonté los módulos de HID y volví a montarlos, y…
¡CASI! Me había asignado al lápiz las siguientes tres acciones del ratón: siguiente página, anterior página y no-se-cual-más. Claramente iba por buen camino.
Se me ocurrió entonces modificar el código para invertir el orden en el que se procesaban las entradas de la tabla HID, de manera que primero se añadiesen las del bloque 9 y luego las del 8, y el resultado fue que… ¡¡¡FUNCIONÓ!!! Parecía que lo había resuelto, así que creé un parche para poder configurarlo como un Quirk más, añadí mi tableta a la lista de dispositivos con Quirks, y envié un parche a la gente del kernel. En respuesta, amablemente me indicaron que mi solución se veía demasiado alambicada, y que quizás debería probar con HID_QUIRK_MULTI_INPUT, que crearía un dispositivo diferente para cada tipo de bloque. Lo probé, y efectivamente, esa era la solución, así que creé un nuevo parche, mucho más sencillo, lo envié, y fue aceptado. ¡¡Hurra!!
Añadiendo un QUIRK a un dispositivo en el driver HID
Vamos a ver este detalle con más calma porque es importante, y puede serle útil a más gente. Lo primero que tenemos que hacer es bajarnos las fuentes del kernel actual desde el repositorio GIT oficial:
Una vez que lo tenemos, nos hacemos un branch para nuestro parche y abrimos el fichero drivers/hid/hid-ids.h. En él buscamos si el fabricante de nuestro dispositivo ya está añadido o no (lo más probable es que sí), mediante el identificador que obtuvimos con lsusb. En mi caso, el identificador 0x2179 ya estaba añadido a nombre de UGTizer con:
#define USB_VENDOR_ID_UGTIZER 0x2179
pero dentro de él no estaba mi tableta, por lo que añadí una línea con su definición:
Una vez hecho esto sólo tuve que abrir el fichero drivers/hid/hid-quirks.c y añadir una entrada con mi vendor, mi device y los quirks que quería añadir para él:
¿Y mientras espero a que mi distro añada el parche?
Obviamente no quería estar con el kernel de desarrollo en mi sistema, sino que quería tener el oficial. ¿Significa eso que no podré usar mi tableta hasta que Debian haga un backport del parche? Pues afortunadamente no, porque el módulo HID permite pasarle manualmente un grupo de quirks a añadir a un grupo de dispositivos. Para ello basta con editar el fichero /etc/default/grub y, en la línea donde se definen los parámetros de arranque del kernel (que, en general, será la de GRUB_CMDLINE_LINUX_DEFAULT) añadir lo siguiente:
usbhid.quirks=0x2179:0x0004:0x0040
El primer número hexadecimal es el identificador USB del fabricante, el segundo es el identificador de dispositivo, y el tercero es un mapa de bits con los quirks a activar. La lista está definida en el fichero drivers/hid/hid.h, y en el momento de escribir este artículo es:
Algunos son obvios, pero otros, la verdad, es que no se para qué pueden servir, así que si algún día me encuentro con un dispositivo HID que no va, iré probando de uno en uno a ver.
Recientemente, Alva Majo, desarrollador de videojuegos indie y youtuber, publicó un vídeo donde explicaba cómo creó Alvabot, un sintetizador de habla que utilizaba muestras de su propia voz. Como, además, hizo público el código fuente y las muestras de voz, decidí que podía ser divertido intentar llevarlo un poco más allá y hacer que cantase. ¡Y lo he conseguido!
Sí, vale… el resultado no es exactamente profesional, pero para ser algo hecho en un par de días, creo que no está mal.
El proceso fue algo alambicado, pero al final no tiene mucha ciencia. Obviamente, si hubiese querido conseguir mejores resultados tendría que haber utilizado otras técnicas, pero la idea era hacer sólo un pequeño divertimento.
En primer lugar escribí una pequeña herramienta en Python (analizador.py, disponible en el repositorio) que me permite ver la forma de onda de un fichero WAV, escoger un trozo entre dos puntos concretos, calcular la frecuencia de dicha onda, y cortar entre los máximos de dicho trozo (todo esto lo explicaré mejor a continuación). Gracias a que Python tiene módulos para todo, no necesité programar casi nada, sino que ha sido más una operación «de pegar cosas».
Así, tomé los samples de las vocales y utilicé la herramienta anterior para revisar la forma de onda de cada una (en este artículo denominaré sample a cada fichero de audio con el sonido de una vocal o una consonante; y utilizaré el término muestra para referirme a cada uno de los datos de sonido que hay dentro de cada fichero; esto es: cada «número» dentro del fichero .WAV será una muestra).
Aquí vemos una ampliación de la vocal A, tal y como se ve en la herramienta:
Si nos fijamos, vemos que parece que hay cierta «repetición». O sea: la onda no es «aleatoria», sino que parece que hay un bloque que se repite en el tiempo (como se puede apreciar por esos picos espaciados de manera regular). Es verdad que la amplitud (la altura) no es constante, pero eso es simplemente porque Alva es un ser humano, y por mucho empeño que ponga es imposible que mantenga exactamente la misma intensidad durante toda la vocal, sino que inevitablemente subirá y bajará un poco en el tiempo.
Para verlo mejor, ampliemos un trozo:
Aquí ya se ve mucho mejor cómo la vocal es, en realidad, un trocito de sonido que se repite una y otra vez. En esta imagen concreta lo vemos repetido cinco veces. Esto significa que si creamos un sample con sólo ese trozo, podremos repetirlo en bucle y conseguir que el ordenador pronuncie una vocal durante todo el tiempo que queramos, sin que se noten cortes, ligaduras ni nada por el estilo. Esto es fundamental a la hora de cantar porque cada nota puede tener una duración diferente a las demás, y son justo las vocales las que se «estiran» en el tiempo para cubrir todo el tiempo que dura una nota.
Aquí es donde mi herramienta analiza.py me pide dos puntos en la gráfica. El primero tiene que estar un poco ANTES de uno de los máximos, y el segundo un poco DESPUÉS del siguiente máximo. Entonces, la herramienta busca hacia adelante el valor máximo local desde el primer punto, y hacia atrás desde el segundo punto, para así recortar con precisión el trozo periódico. Para la vocal A utilicé 1668 y 2023, marcados en rojo en la imagen, y que como vemos caen justo cerca de dos máximos consecutivos. El propio programa busca los máximos, los cuales están en 1697 y 2001.
Lo segundo que hice fue calcular la frecuencia fundamental de cada vocal. Para los que no sepan a qué me refiero, la frecuencia fundamental determina la «nota» en la que está sonando la vocal. Cuando mayor sea la frecuencia, más alta en la escala será la nota. Al principio hice algunas pruebas con la transformada de Fourier, hasta que me di cuenta de que no necesitaba complicarlo tanto, pues simplemente con saber el número de muestras que hay en el «trozo» repetitivo y la frecuencia de muestreo, ya puedo obtener la frecuencia fundamental del sample.
Así, por ejemplo, si decidimos utilizar para la vocal A el bloque situado entre los picos de las muestras 1697 y 2001, vemos que hay un total de 304 muestras en él, lo que significa que si dividimos la frecuencia de muestreo de este fichero .WAV (que es de 44100 muestras/segundo) entre dicho valor, nos dará que la frecuencia a la que Alva pronunció la letra A es de 145 Hz.
Repitiendo este proceso para las cinco vocales, sale que cada una fue pronunciada con estas frecuencias:
vocal A: muestras 1697 a 2001, 145 Hz vocal E: muestras 555 a 855, 147 Hz vocal I: muestras 2968 a 3242, 161 Hz vocal O: muestras 2246 a 2544, 148 Hz vocal U: muestras 3027 a 3317, 152 Hz
Esto demuestra que Alva Majo NO es un robot, pues no es capaz de afinar correctamente. Por eso cada vocal tiene una frecuencia diferente.
Pero claro, para nosotros esto es un problema porque si queremos que el ordenador cante, necesitamos que las muestras estén todas en la misma frecuencia. Si no, lo único que conseguiremos es un ordenador que desafina.
Afortunadamente, una vez que tenemos ya aislado el bloque periódico de cada vocal, ajustar su frecuencia es muy sencillo: sólo necesitamos hacer que todas midan lo mismo (pues la frecuencia fundamental depende del tamaño del bloque y de la frecuencia de muestreo; como la frecuencia de muestreo tiene que ser la misma para todos los samples, tenemos que conseguir que el número de muestras sea igual). Si calculamos la media de todas esas frecuencias, nos salen 150 Hz, así que ajustaremos todas a ese valor para evitar tener que desplazarlas demasiado. Y si ahora dividimos la tasa de muestreo entre esa cifra, nos sale que cada bloque debe tener 44100/150 = 294 muestras. Por supuesto, no se trata de añadir, por ejemplo, ceros al final, porque entonces estaríamos modificando la señal. Lo que necesitamos es «inventarnos» muestras en medio para estirarla si es demasiado corta, o «tirar a la basura» muestras si es demasiado larga. Por supuesto, si añadimos muestras éstas deben «encajar» con las que las rodean; y si quitamos muestras, debemos hacerlo de manera «repartida». Esto, como no, tiene un nombre: remuestreo o cambio de tasa de muestreo, y el módulo scipy incluye una función llamada resample() que lo hace. Así que en la parte final de la herramienta hago una llamada a dicha función para ajustar cada sample justo antes de grabarlo en disco.
Para poder evaluar los resultados, podemos comparar el antes:
con el después:
Ahora llega el momento de hacer lo mismo con las consonantes, pero esto es un poco más complicado, pues éstas no tienen por qué tener un patrón (aunque algunas sí), por lo que será difícil calcular su frecuencia… o no, porque, afortunadamente, Alva grabó todas las consonantes seguidas de todas las vocales. No tenemos sólo el fonema ‘P’, sino que también tenemos los sonidos de ‘PA’, ‘PE’, ‘PI’, ‘PO’ y ‘PU’, así que podemos medir la frecuencia a la que pronunció la vocal y asumir que es la misma que la del fonema de la consonante. Luego sólo tendremos que cortar justo en el punto donde termina la consonante y empieza la vocal, y tendremos el sonido puro de la consonante. Veamos un ejemplo con la sílaba «DA»:
Para hacer esto escribí otra pequeña herramienta, cortar_consonantes.py, la cual carga un fichero .WAV, muestra su forma de onda para que podamos buscar dos muestras que delimiten un periodo de la vocal, y nos pide que tecleemos su posición. Con ellas calcula la frecuencia a la que está pronunciada y también cuanto tiene que estirar o encoger todo el fichero WAV para ajustarlo a los 150 Hz que decidimos que sería nuestra frecuencia central.
Una vez que está ajustada, nos pide el número de muestra en la que realizar el corte para separar la consonante de la vocal. Como no es fácil acertar, lo que hice es que, tras dar un punto de corte, reproduzca la consonante seguida de la vocal «I» (para lo cual, utilizo los samples que generé antes). De esta manera, si se recorta demasiado poco y se cuela parte de la vocal original, sonará AIIIIIII en lugar de IIIIIII. Así podremos ir ajustando hasta encontrar el punto óptimo de cada consonante. Cuando hayamos encontrado el punto exacto, simplemente pulsamos RETURN en lugar de meter un nuevo número y el programa grabará el nuevo sample con sólo la consonante, ya ajustada a 150 Hz.
Algunas consonantes, pese a todo, son sonoras, lo que significa que SI están formadas por una zona repetitiva. En concreto, para la B, la M y la N utilicé el mismo sistema que para las vocales, pues se entendían mucho mejor que extrayéndolas «tal cual» de los samples.
Haciendo que hable
Ahora que ya tenemos los sonidos vocales y consonantes aislados y a la misma frecuencia, podemos hacer una primera prueba que se limite a hablar. Para ello escribí hablar.py, que generará un fichero habla.wav en el que pronunciará la frase que se le pase por la propia línea de comandos.
Lo primero que hace este programa es sustituir las letras por fonemas, de manera que no hace falta pensar en sonidos sino que podemos escribir directamente una frase. Además, si alguna vocal tiene tilde la pronunciará a una frecuencia ligeramente superior, lo que permite simular la entonación de las frases. En teoría se podría hacer que fuese completamente automático, y que si una palabra no tiene tilde, compruebe si acaba en n, s o vocal y, en base a ello, determine si es aguda o llana y ponga la tilde automáticamente, pero no me apeteció ponerme con ello, así que hay que hacerlo a mano.
Ejemplo: «Hóla, sóy cantabót hablándo.»
Y haciendo que cante
Y por último, está la herramienta final, cantar.py, que genera un fichero .WAV con una canción generada con las muestras.
El programa se compone de una clase con dos métodos fundamentales: interpreta() y pausa(). Estos dos métodos se deben ir llamando para introducir la partitura y la letra de la canción. Cada llamada renderiza los sonidos correspondientes, que se van añadiendo a un buffer interno. Cuando la canción está lista, se llama al método grabar(), que lo almacenará en disco en formato WAV con el nombre canta.wav.
El método pausa es el más sencillo, y simplemente recibe como parámetro un número decimal con el número de segundos de silencio que se deben añadir al buffer. Permite añadir silencios entre notas.
El método interpreta es el más complejo, y recibe tres parámetros:
Un entero con la octava de la nota a interpretar. Este valor estará entre 0 y 12 e indica el semitono concreto. La correspondencia exacta está en el código fuente
Un valor decimal con la duración en segundos de la nota.
Un string con los fonemas a cantar en dicha nota
Para simplificar la composición, se definen seis variables (redonda, redondadot, blanca, blancadot, negra y negradot) con las duraciones en segundos. Se establece la duración de la redonda en 1,5 segundos, y el valor de la blanca y la negra queda definido automáticamente como la mitad y la cuarta parte de la redonda. A mayores, las duraciones con «dot» son un 50% más que la correspondiente sin «dot». Además, se definen también las variables nota_XX, con el valor de semitono correspondiente a cada nota (por ejemplo, nota_sol vale 5).
Por otro lado, a la hora de decidir cuanto tiempo dura cada fonema de la nota se siguen las siguientes reglas:
Las consonantes durarán lo que dure su sample, salvo las consonantes «sonoras», que durarán 0,2 segundos
Las vocales que no sean la última durarán 0,15 segundos
La última vocal durará el tiempo necesario para completar la duración de la nota
Así, la última vocal durará realmente la duración de la nota menos la duración del resto de fonemas. Este valor se calcula automáticamente, lo que simplifica mucho meter una partitura.
Dado que ya nos preocupamos antes de ajustar todos los samples para que estuviesen a 150 Hz, ahora lo único que tenemos que hacer es ajustar la frecuencia de todos los fonemas a la necesaria para la nota. Y lo interesante es que para saber cuanto tenemos que ajustar la frecuencia, sólo necesitamos elevar la raíz doceava de 2 al valor del semitono que le pasamos a la función (por supuesto, tras restar 5, pues por convenio he decidido que los samples estarán en SOL).
¿Y por qué la raíz doceava de 2? En este vídeo de Minute Physics lo explican muy bien, pero para simplificar: como la frecuencia de una nota cualquiera tiene que ser la mitad de la frecuencia de la misma nota en la siguiente octava, y cada octava son doce semitonos, la única manera de que esto encaje es que la frecuencia de cada semitono sea la frecuencia del semitono anterior multiplicado por la raíz doceava de dos. Así que si quiero hacer sonar un LA (semitono 7 como vemos en la tabla de arriba), necesito subir la frecuencia de los fonemas en dos semitonos, o sea, multiplicar dos veces por la raíz doceava de dos. En cambio, si quiero interpretar un MI, tengo que bajar la frecuencia en tres semitonos; o sea, dividir tres veces entre la raíz doceava de dos.
¿Y cómo cambiamos la frecuencia de los fonemas? Pues exactamente como vimos antes: interpolando para estirarlos o encogerlos. Si los estiramos, la frecuencia baja; y si los encojemos, la frecuencia sube. Por tanto, una vez hemos calculado el factor entre la frecuencia inicial y la final, sólo tenemos que coger el número de muestras que tiene cada fonema y multiplicarlo por dicho factor, obteniendo así el nuevo número de muestras que tiene que tener. Con ese número llamamos a interpolate() para que haga su magia, y añadimos las muestras al buffer.
Como no todo el mundo tiene un emulador de Spectrum a mano, se me ha ocurrido poner una versión de JSSpeccy en mi web con el juego dentro. Para los que no lo conozcan, se trata de un emulador de Spectrum escrito por Matt Westcott en JavaScript y, por tanto, embebible en un navegador. Ahora basta con ir a la página de Escape from M.O.N.J.A.S. y escoger «Juega a la versión en español en tu navegador» (o en inglés, si prefieres), y aparecerá el emulador en tu ventana, al máximo tamaño, y cargará automáticamente MONJAS.
Si vais al repositorio de JSSpeccy que he puesto, veréis que es el mío, y no el oficial. Esto es porque el que subí es un fork que hice para añadirle algunas características extra. Una de ellas es redimensionamiento automático, de manera que ocupe toda la pantalla. Otro cambio fue añadir la emulación del bus flotante, imprescindible para que MONJAS funcione. Había enviado el parche al autor, pero parece que el proyecto está abandonado 🙁
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í hay un detalle que no es nada trivial, y es conseguir meter mucho texto en poco espacio. En mi juego Escape from M.O.N.J.A.S. tenía unos 10 kbytes de texto, y tenía el problema de que, sencillamente, no me cabía en la memoria. Sin embargo, el texto tiene la característica de que tiene mucha redundancia, por lo que es muy compresible. Así que decidí intentar ir por esa ruta.
Alguno pensará 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é ser así: hay algoritmos en los que lo complicado es comprimir, pero la descompresión es muy sencilla y rápida.
El algoritmo que utilicé fue el LZSS (cuando hice la primera implementación no sabía que se llamaba así, pero es tan sencillo en concepto que era obvio que tenía que estar ya inventado). La idea es sustituir cada bloque que sea idéntico a otro anterior por un par (offset, tamaño) que apunte a dicho bloque anterior. El ejemplo más típico que se pone es el del poema Green Eggs and Ham, y lo podemos ver explicado en la página de la wikipedia.
En mi caso me aprovecho además 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í comienza un bloque comprimido. Cada bloque comprimido está 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ño del bloque. Tras hacer varias pruebas, encontré que para mi cantidad de texto el tamaño óptimo es de tres bits para el tamaño y 12 bits para el offset. Por supuesto, dado que no compensa comprimir bloques de tamaño cero, uno o dos, el valor almacenado será el tamaño menos tres (o sea, entre 3 y 10). Además, el offset será siempre a partir del principio del bloque completo de textos, y no «desplazamiento hacia atrás desde el punto actual». El motivo de esto es que al principio es donde hay más texto sin comprimir, y, por tanto, donde habrá más oportunidades de encontrar repetido texto de más adelante.
Esta implementación 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í necesitan). Para simplificar aún más el algoritmo, habrá una condición extra: no habrá recursividad (esto es: dentro de un bloque comprimido no habrá otros bloques comprimidos, sino que siempre apuntarán a ristras de caracteres ASCII). Esto tiene el inconveniente de que la compresión es menor, pero simplifica sobremanera el algoritmo y reduce la memoria necesaria para la pila (y dado que trabajamos con threads, interesa que este valor sea lo menor posible).
Lo más interesante de este algoritmo así descrito es que se puede utilizar al vuelo; 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álido, tiene la ventaja extra de que podemos utilizar la misma función para imprimir textos «normales», sin comprimir.
Habrá una limitación extra, y es que un bloque comprimido no puede jamás cruzar la frontera entre dos «frases» o «bloques de texto». Esto es fundamental, pues si queremos poder descomprimir al vuelo una frase, necesitamos que empiece en un byte concreto, y no en mitad de un bloque comprimido. Así, si tenemos estas tres frases:
esta es la primera frase la primera frase empieza en esta es la primera que veo
tenemos que respetar las fronteras entre frases y no comprimir el final de la segunda junto con el principio de la tercera en un único bloque, pues entonces no podríamos descomprimir la tercera de manera independiente, sino que tendríamos que descomprimir la segunda antes, almacenando el resultado, y buscar el punto de unión.
Por desgracia, si la descompresión es muy sencilla y rápida, la compresión es endiabladamente fastidiada (con jota). De hecho, por lo que he visto, ni siquiera parece existir un algoritmo óptimo, sino sólo 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á repetido anteriormente. Sin embargo, por sorprendente que parezca, el orden de las frases puede afectar (y mucho) al nivel de compresión obtenido. Veámoslo con este ejemplo:
12345678 12345 345678
Estas tres «frases» se pueden comprimir como
12345678 (0,5) (2,6)
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í:
12345 12345678 345678
tenemos que la compresión será
12345 (0,5)678 (2,3)(7,3)
que consume 14 bytes.
La solución a esto ha sido ir probando a cambiar de sitio una frase de cada vez, recomprimir, y si le nivel de compresión es mejor, guardarlo y volver a probar, mientras que si el cambio es a peor, deshacerlo y probar de nuevo. Una pequeña mejora consiste en no deshacerlo con una probabilidad pequeña (el 0,1%), de manera que sea posible «volver atrás», y que el algoritmo pueda probar otros caminos lejos de un mínimo local, pero siempre conservando en memoria la mejor combinación hallada hasta el momento. Esto tiene el inconveniente de que para conseguir altos niveles de compresión se necesita mucho tiempo (para los textos actuales dejé mi PC trabajando unas 24 horas).
Además, existe otra optimización muy importante, que consiste en intentar comprimir antes los bloques de mayor tamaño, e ir probando luego con los de menor tamaño. Así, dado que el tamaño 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 un bloque de 3, más adelante no pueda comprimir un bloque mayor. Aquí tenemos un ejemplo:
12345678 ab456dfg b456df
En este caso, si comprimo en el orden que aparece, tendré
12345678 ab(3,3)dfg b(3,3)(12,3)
que son 20 bytes, mientras que si comprimo por tamaño, tendré:
12345678 ab456dfg (9,6)
que son 18 bytes.
La diferencia entre aplicar o no estas dos optimizaciones en brutal: sin ellas, conseguía una compresión del 68% aproximadamente, mientras que aplicándolas, los textos quedan reducidos a un valor en torno al 59,7%. Una diferencia abismal, que me permitió reducir los más de diez kilobytes originales en unos seis, y que entrase por fin todo en memoria.
El compresor que escribí, además, parte de un fichero en formato assembler normal y saca el mismo fichero también en assembler pero con los datos comprimidos. Eso significa que se conservan las etiquetas, por lo que para descomprimir una frase sólo hay que pasar la etiqueta correspondiente a la rutina de descompresión/impresión, y listo.
Queda, eso sí, un detallito especial, que es qué hacemos con los caracteres específicos del español (la eñe y las aperturas de interrogación y exclamación; las tildes decidí obviarlas). La solución que se me ocurrió fue mapearlas en caracteres por debajo de 127 que no se utilicen, como el asterisco, el porcentaje, etc, reemplazándolos en el juego de caracteres del Spectrum. Por supuesto, para simplificar el trabajo, el compresor también se encarga de esta tarea, por lo que en el código fuente original los textos irán en UTF-8, y el compresor se encargará de sustituir la eñe por el asterisco, etc.
¡Pues por fin ha ocurrido! Tras tres meses de duro trabajo, por fin he terminado mi juego para Spectrum Escape from M.O.N.J.A.S. Ya podéis descargarlo desde la página oficial. Espero que lo disfrutéis.
Utilizamos cookies para garantizar que tenga la mejor experiencia en nuestro sitio web.
