Squoze sus datos

Tengo una confesión que hacer. Disfruto el desafío de presionar el software en un espacio pequeño o tratar de cortar algunos bucles más de un bucle. Es como un rompecabezas complicado. Hoy, por supuesto, no hay tanto atractivo para eso como antes. Hoy en día, incluso un microcontrolador "pequeño" tiene mucha memoria y recursos.

A pesar de esto, todavía hay algunos casos en los que necesita exprimir esos últimos bytes de la memoria. Tal vez esté tratando de maximizar la memoria disponible para algún propósito. Tal vez esté anticipando la producción en masa y esté utilizando el microcontrolador más pequeño que pueda encontrar. O tal vez hagas el desafío de 1 kB y solo quieras algunos consejos.

Una forma de encontrar técnicas para maximizar los recursos es observar lo que hacía la gente "en los viejos tiempos". Las computadoras del Equipo Digital alguna vez tuvieron un juego de caracteres especial llamado Squoze (o algunas veces DEC Radix-50). Esta técnica puede resultar útil cuando necesite insertar muchas cadenas en la memoria. La buena noticia es que puede ingresar de manera confiable 3 caracteres en 2 bytes (o, como hizo DEC, 6 caracteres en 4 bytes). La mala noticia es que debes elegir un conjunto de caracteres limitado que puedas usar. Sin embargo, esto no siempre es un gran problema.

La gran comunicación azul

La clave de Squoze es que debe seleccionar los 40 caracteres que desea codificar. Eso es suficiente para 26 letras, 10 dígitos y 4 signos de puntuación (espacio más todo lo que desee). Tenga en cuenta que 26 letras significa que debe seleccionar letras minúsculas o minúsculas, pero no ambas.

Quizás se pregunte por qué se llamó DEC Radix-50 si solo puede tener 40 caracteres. El 50 es octal (base 8) que es 40 decimal. El nombre Squoze fue utilizado tanto por DEC como por IBM. En el esquema de IBM, sin embargo, una palabra de 36 bits contenía dos banderas y 6 caracteres de un conjunto de 50 (decimal 50, esta vez). Históricamente, el uso de Squoze para tablas de símbolos es la razón por la que muchos compiladores antiguos usaban símbolos de 6 caracteres con solo unos pocos caracteres permitidos (si alguna vez se ha preguntado acerca de eso).

Cómo funciona

Una vez que tenga 40 caracteres en mente, puede tratarlos a todos como un dígito en un número básico de 40. Tenga en cuenta ese pensamiento y piense en un número decimal regular. Si tiene una cadena de dígitos del 0 al 9 ingresando, puede construir un valor decimal como este:

value=0

while not end of digits

   value=value * 10

   value = value + digit

end while

Si tiene los dígitos "643", el valor aumentará de 0 a 6 a 64 a 643.

Si generaliza a base 40, los "dígitos" son números del 0 al 39 (que representan un carácter) y el * 10 se convierte en * 40 en el pseudocódigo anterior. Si lo prefiere, puede pensar en ello matemáticamente como el primer dígito se multiplica por 40 cuadrados (1600), el segundo dígito por 40 (40 a la primera potencia) y el dígito final por 1 (40 a la potencia cero).

Supongamos, entonces, que elegimos 0 para representar el espacio, 1 para representar A, 2 para B, y así sucesivamente. La cadena "AB" (es decir, un espacio en el centro "sería 1, 0, 2. A través del algoritmo, el resultado sería 1602.

La decodificación es todo lo contrario. Comenzando con 1602, por ejemplo, haces una división entera entre 1600 para obtener 1 (A). Quite eso dejando 2. Dividir por 40 le da espacio (0). Luego hay 2 - B - por lo que la cadena es "AB" como era de esperar.

¿Por qué cuarenta?

¿Por qué pasar por todos estos problemas? ¿Por qué usar 40 y no, por ejemplo, 41 o 50? Piense en el número más grande que puede representar con tres 40 caracteres básicos. 39 * 1600 + 39 * 40 + 39 = 63999. Esto coincide con una palabra de 16 bits. Si eligió la base 41, el número más grande posible es 68920. Eso es demasiado grande para un número de 16 bits.

El caso es que con este esquema puedes empaquetar 3 caracteres (de tu conjunto de 40) en dos bytes. En comparación con los caracteres ASCII normales, esto supone un ahorro del 33%. No mucho, pero en comparación con otros esquemas de compresión, es simplemente factible y siempre ahorra un 33%. Bueno, al menos aproximadamente. Si la longitud de su texto no es igualmente divisible por 3, es posible que tenga uno o dos caracteres acolchados, lo que reduce un poco el rendimiento según la longitud total del texto.

Imagine un conjunto de entradas de menú LCD almacenadas en EPROM. Ahorrar un 33% podría dejarle espacio para más cadenas o más funciones no relacionadas. Por supuesto, también debe tener en cuenta el tamaño del código y la matriz de caracteres. A menudo, no es necesario codificar y decodificar durante la ejecución, pero todavía hay que tener en cuenta un poco de lo anterior. Debe evaluar sus necesidades y tomar una decisión adecuada.

Mejoras

Si traspasa el límite de 40 caracteres, puede correr algunos riesgos para obtener más a expensas de una posible pérdida efectiva. Por ejemplo, para algunas aplicaciones, puede suponer que la primera letra de una cadena está en mayúsculas y el resto en minúsculas. O elija sus 39 caracteres más comunes, use uno más como carácter de escape y luego elija 40 más para un total de 79 caracteres. También puede usar la señal de escape como una señal de "cambio" si eso funciona mejor para usted.

Implementación

Puede encontrar una implementación de lenguaje C simple en GitHub. El archivo make genera dos ejecutables, uno para codificar y otro para decodificar. Puede definir un símbolo para evitar la creación de ejecutables si desea experimentar con el código como una biblioteca.

El codificador y el descodificador utilizarán un juego de caracteres predeterminado si lo desea. También puede proporcionar uno usted mismo. El código está apenas optimizado, por lo que si su aplicación comparte código y espacio de datos, probablemente querrá pasar algún tiempo analizando el tamaño del código. Sin embargo, para una demostración o si su espacio de código es particular y abundante, probablemente sea bastante bueno como está.

El código está configurado para que pueda ejecutar el código y proporcionar su salida al decodificador:

$ ./encode | ./decode
Hello La-Tecnologia. A man, a plan, a canal, Panama.
Characters in=48
(13012) HEL
(19800) LO 
(12843) HAC
(17644) KAD
(2637) AY.
(40) A 
(20854) MAN
(60801) , A
(652) PL
(2198) AN,
(40) A 
(4854) CAN
(2118) AL,
(641) PA
(22453) NAM
(3080) A. 
Bytes out=32
Full String (length=48):
HELLO la-tecnologia.com. A MAN, A PLAN, A CANAL, PANAMA. 
$

Tenga en cuenta que los caracteres se cambian a mayúsculas con el codificador.

¿Vale la pena?

Este es solo un truco más para poner en su caja de herramientas. No es adecuado para todos los proyectos. Tienes que poder vivir con los límites. También debería poder aceptar el código adicional y la sobrecarga del tiempo de ejecución. Dependiendo de los datos que tenga, puede haber mejores opciones. Por ejemplo, un registrador de datos puede almacenar números de punto flotante o algún otro esquema.

La codificación Huffman, la codificación a largo plazo y otros métodos podrían funcionar mejor, depende de su aplicación. Sin embargo, creo que es interesante minimizar algunas de las técnicas antiguas y aplicarlas a nuevas soluciones.

Si te estabas divirtiendo con esto, deberías lanzar tu sombrero al ring con el Desafío de 1 kB que mencioné anteriormente. La-Tecnologia quiere ver qué puede hacer con un límite binario compilado de 1 kB para un proyecto de microcontrolador. Pruébelo y aprenda las técnicas de ahorro de espacio de los viejos tiempos.

  • gudenau dice:

    Me pregunto qué tan difícil sería limitarse a menos signos para obtener una mayor compresión. Si solo desea texto, podría ganar 28 o menos si no usa los 26 caracteres.

    • Piotrsko dice:

      Necesitas un poco de 38 caracteres. ¿Olvidaste los números?

      • Raf Cellucci dice:

        Siempre puedes deletrear números ...

      • gudenau dice:

        No es necesario utilizar números.

      • un pensamiento dice:

        Excepto por los números ly O (recordando la máquina de escribir de mis padres)

    • METRO dice:

      oye, ¿olvidaste zero end h7 468trh 4tr86h 4t358

      • Al Williams dice:

        Divertida. Por lo general, con estos tenías un número fijo de caracteres. Es por eso que muchos compiladores tenían 6 símbolos de caracteres sin espacios.

      • Tony Stark dice:

        Puedes simplemente tirar de tus cuerdas con espacios.

      • Senji dice:

        No necesitas un final cero. Simplemente prefija todas sus cadenas con su longitud. Usted predice las cosas por la longitud de su cadena.

  • Joel Finkle dice:

    Otro almacenamiento: finales de los 70 y principios de los 80 Las computadoras de uso general tenían una palabra de 60 bits en la que se podían almacenar 10 caracteres de un conjunto de caracteres similar como una cadena corta.

    Sin mencionar la tendencia a sobrecargar las variables, especialmente las booleanas, como los conjuntos de bits en un byte o un número entero del tamaño de una palabra, los buenos viejos tiempos requerían mucha creatividad para adaptarse a los modelos de memoria mínima. Recuerde que las computadoras domésticas de primera generación (Apple II, TRS-80) tenían 4K RAM. La Mac original tenía 128K (y el sistema operativo, MacWrite y MacPaint podían coincidir con un disquete). Todavía me sorprende que las aplicaciones simples en mi teléfono ocupen varios megabytes. Oh, y deja mi pasto.

    • Ostraco dice:

      "Sal de mi césped" ocupa demasiado espacio. Tendré que cortar eso. 🙂

    • Galane dice:

      Macintosh solucionó el pequeño tamaño de la RAM al empaquetar una gran cantidad de sistema operativo en la ROM, especialmente las partes gráficas de la GUI.

    • yo estuve ahí dice:

      No Daya General, sino Datos de control.

  • joshuacoppersmith dice:

    Tengo buenos recuerdos del desarrollo de un sistema de base de datos para la computadora IBM original. Incluso después de generalizar los sistemas de menú y usar la segmentación de datos, el tamaño del programa comenzó a restar valor al tamaño de los datos que podíamos manejar. Así que escribí un programa "cruncher" que tomaba un archivo .BAS y juntaba líneas no ramificadas, eliminaba comentarios, etc. Compró otro año más o menos usado de los mismos ordenadores. No bajó al nivel de bytes, pero fue interesante analizar previamente el lenguaje interpretativo.

  • METRO dice:

    Es posible que en muchos sistemas no se necesite una tabla de búsqueda. Si está leyendo o escribiendo en un dispositivo que entiende ASCII, entonces la legibilidad humana de ASCII puede ser útil. Notará que muchas de las cosas alfanuméricas son secuenciales, por lo que todo lo que realmente tiene que hacer para obtener el valor de cada carácter es cortar la representación ASCII y cambiar a través del espacio sumando o restando un desplazamiento. Este también es un proceso reversible y es algo que puede hacer cada vez que lee o escribe un carácter en un dispositivo ASCII. En última instancia, la tabla solo es necesaria para traducir dentro y fuera de su conjunto de caracteres internos, lo que probablemente solo hará cuando hable con un dispositivo ASCII.

    Otra opción, por cierto, es hacer todo en baudot. Es un poco más compacto, 5 bits por carácter (5 * 3 = 15

    • METRO dice:

      Maldita revisión ortográfica. reemplace 'sexista' por 'existe'.

      He leído muchas noticias electorales, pero hagamos una pausa.

      • METRO dice:

        Reemplaza "ser" por "yo".

        No tengo excusa esta vez.

        • Ostraco dice:

          Sería bueno si este foro tuviera una función de "edición".

          • Mike Szczys dice:

            Característica solicitada a menudo. Por ahora soy el botón de editar

            @M: Arreglé su problema de autocorrección "sexista" 😉

        • notarealemail dice:

          No, en realidad se recomienda la corrección ortográfica del error inicial.

          Gracias por la mención de baudot; ¡Empecé a perderme en los enlaces de Wikipedia!

        • KDM dice:

          "Cortar es una pausa" es aceptable, como un corte es una pausa ... ¿y tal vez tuviste un "sapo" (frío) y lo escribiste como lo dirías?

      • METRO dice:

        Es asombroso cómo el impacto duradero de esta publicación hace que la gente se pregunte acerca de mi terrible ortografía.
        _ಠ

  • emjay dice:

    Joel, quizás esté pensando en el control de datos (CDC); no hay una máquina de 60 bits en las ofertas comerciales de datos generales.

    • Lucas dice:

      La serie Univac 1100 también tenía símbolos de 6 bits, 6 para palabras de 36 bits. Aah, recuerdos ... ¿o son esas pesadillas?

      • Al Williams dice:

        Pasé mucho tiempo en 1108. Eso fue Fieldata: http://nssdc.gsfc.nasa.gov/nssdc/formats/UnisysFieldata.htm

      • BrilaBluJim dice:

        PDP-10 lo llamó "SIXBIT" cuando empaquetaron seis caracteres en una palabra de 36 bits. Esto se usó, por ejemplo, para nombres de archivos.

  • Dave dice:

    ¡Ah! Buenos recuerdos de los nombres de archivo RAD-50 en RSTS / E.

    • Comedias dice:

      ¡No existe tal memoria RSTS / E favorita!

  • karulo dice:

    Si sigue esta ruta, también debe ser responsable del tamaño de un decodificador (puede que al final no valga la pena el problema). También debe leer sobre el esquema de codificación aritmética porque se trata de algún tipo de codificación aritmética (muy ineficiente) ...

  • comensal dice:

    También puede usar la compresión LZSS, que usé en 6502 al escribir código para concursos de tamaño limitado (aunque en ese caso era 4k): http://www.deater.net/weave/vmwprod/tb1/ tb_6502.html

    Tengo implementaciones LZSS de tamaño optimizado en 26 tipos de lenguaje ensamblador si alguien las quiere: http://www.deater.net/weave/vmwprod/asm/ll/

    • Westfw dice:

      ¡LZSS en conjunto para 26 arquitecturas! Fresco. (Oh, dijiste eso. Lo leí mal como "26 bytes de ..." :-))
      Es fascinante que Thumb y Thumb2 tengan un tamaño tan parecido.

      • eater78 dice:

        Thumb2 solo es una ganancia si el código en cuestión no se asigna bien a un Thumb normal. Con algo relativamente simple como la decodificación LZSS (que no usa muchos registros o constantes grandes) no ayudó mucho.

        Mi objetivo era extraer arquitecturas adicionales, especialmente risc-v. Simplemente no tuve tiempo 🙁

  • McPeppr dice:

    ¡Muy buena idea!
    También puede utilizar los 1536 caracteres entre 63999 y 65536 de una manera especial para codificar la suma de comprobación EOF (final de archivo), CR (retorno de carro), LF (flujo lineal) o CRC (verificación de redundancia cíclica). Esto puede ser realmente interesante cuando se piensa en arduino y con. Su "cifrado" es una especie de cadena de bloques con las mismas distancias de 16 bits, por lo que el código se puede ejecutar de forma simple.
    Pero creo que un algoritmo de diccionario logrará fácilmente velocidades de compresión mucho más altas debido a la ley de Zipf, que también sería más difícil de implementar de manera eficiente y, por lo tanto, más flexible.

    • Al Williams dice:

      Puede hacer eso, pero tiene un impacto en la eficiencia. Si tiene un carácter perdido, debe jugarlo con un valor de espacios y luego soplar otros dos bytes para su código especial. Dependiendo de eso, sin embargo, puede ser apropiado para su aplicación. Solo algo para pensar.

  • Galane dice:

    Squoze inmediatamente me recordó esto https://www.pinterest.com/pin/562668547164443686/

  • Galane dice:

    ¿Alguien ha usado alguna vez código Morse en un programa de computadora?

    • svofski dice:

      No.

    • Al Williams dice:

      Los datos parpadean repetidamente

      • Galane dice:

        Podría reducir ligeramente un poco con Morse usando 0 para un punto y 1 para un guión. Esto hace que todos los números sean de solo 5 bits y las letras sean de 1 a 4 bits, y que las letras menos utilizadas usen 4 bits.

        Pero, ¿cómo encapsula el código Morse en una arquitectura de 8 bits, sabiendo aún dónde están las rupturas entre caracteres, especialmente si no lo llena hasta 5 bits por carácter?

        • BrilaBluJim dice:

          El código Morse realmente no es adecuado para comprimir texto, PORQUE necesitas piezas adicionales para codificar la longitud del carácter, y solo se vuelve complicado si también tienes que considerar códigos muy largos (al menos incluso siete elementos, por encima de mi cabeza) que son raramente usado. Es mucho más fácil de hacer en ternario porque puede usar 0 para dit, 1 para dah y -1 para stop. Pero, por supuesto, debe convertir de ternario a binario si lo mantiene. Si desea hacer esto con bytes de 8 bits, tiene 256 códigos disponibles. En ternario, 5 dígitos tienen 243 códigos posibles que coinciden muy bien con 8 bits. Por lo tanto, puede codificar cinco dígitos ternarios en cada byte, lo que significa que todas las letras coinciden con un byte o menos, pero los números y la puntuación no.

          Si desea algo más simple, puede usar dos bits para codificar cada elemento. Esto parece un desperdicio, pero recuerde que con cuatro códigos disponibles, puede tener 00 = dit, 01 = dah, 10 = dit final y 11 = dah final, por lo que no necesita un código separado para indicar el final de un carácter , y todas las letras aún pueden ingresar un byte. Pero creo que los números y la puntuación acaban tomando más piezas.

          Para usar bits individuales para dit y dah como sugiere, puede prefijar cada carácter con un campo fijo de tres bits para almacenar el número simbólico, luego letras y números, todo en 8 bits (cuenta de 3 bits + 5 o menos bits de datos), pero luego es diabólico pagar si tiene algunos caracteres con más de 8 símbolos.

          Todos estos esquemas requieren el uso de campos de bits de longitud variable para tener alguna posibilidad de guardar bits, lo que a nadie le gusta hacer. El enfoque que utilizó Emile Baudot en la telegrafía meizinganic fue utilizar un número fijo de símbolos (5) por signo y códigos especiales de "cambio" para alternar entre los códigos alfabéticos y no alfabéticos.

          Es precisamente ese pensamiento el que conduce a un código que se rompe de una manera que nadie puede entender. En la mayoría de los casos, es más fácil utilizar códigos de longitud fija, junto con un algoritmo de compresión generalizado. De esa manera, solo tiene UN algoritmo "listo" para admitir.

  • Steve dice:

    Entonces ... ¿esta es básicamente una tabla de búsqueda con algunos bits de datos en mayúscula izquierda / mayúscula derecha? Tal vez sea demasiado mayor, pero esto me parece básico.

  • Dithermaster dice:

    Eso es una maravilla del pasado: utilicé Rad50 en un proyecto hace mucho tiempo para ahorrar espacio (cuando importaba). Por lo tanto, mantuvimos los números de pieza y les dije que podían tener AZ, 0-9 y solo 4 signos de puntuación que discutimos durante una semana.

  • Comedias dice:

    Esa es una forma bastante complicada de decir que DEC usó octals y mordidas de 3 bits (0 a 7) en lugar de 4 bits y hexadecimales. Teniendo en cuenta la velocidad de las máquinas y el conjunto de instrucciones, una tabla de búsqueda es mucho más rápida que ese algoritmo. Nunca he visto nada usado que no sean LUT a menos que la RAM sea increíblemente ajustada. De hecho, LUT es más rápido para determinar cosas como mayúsculas frente a minúsculas, o conversión de mayúsculas, o multiplicar dos bits, y no es muy grande.

    • BrilaBluJim dice:

      Sí, a DEC le gustó su octal y lo usó incluso en máquinas de 16 bits, donde era realmente un poco incómodo. La única arquitectura de AR que he visto que es adecuada para octal fue 8080 / Z-80, donde se podía aprender a ensamblar programas manualmente con bastante rapidez, ya que casi todas las instrucciones usaban un campo de dos bits más dos campos de tres bits. No, DEC eligió 36 bits para la palabra de máquina por ... razones, y luego insertar seis caracteres en cada palabra fue una solución más elegante (?) Que insertar cinco caracteres ASCII de 7 bits y descartar el bit adicional. ¿Cuál es otra forma en que se hicieron las cadenas en el PDP-10 IIRC? El 10 también tenía algunas instrucciones de bytes, pero no por bytes como las conocemos. Estos se utilizaron para descomprimir "bytes" de cualquier longitud. Especificó la longitud del byte, la dirección de su cadena y el número del byte que deseaba, y realizaría todo el esfuerzo y devolvería ese byte. Porque los desarrolladores siempre han creado paquetes raros para ahorrar un poco aquí y un poco allá. Lo que creo que tiene sentido, porque en una máquina de 36 bits, podrías tirar MUCHAS piezas si no empacas todo lo que puedas pensar, en cada palabra.

Isabella Ortiz
Isabella Ortiz

Deja una respuesta

Tu dirección de correo electrónico no será publicada.