Generación de caracteres en 144 bytes

[Jaromir Sukuba] tiene un proyecto asombroso del intérprete BrainF * ck. Maneja todo el lenguaje en menos de 1 kB de código. Parece una gran entrada al desafío de 1 kB. El único problema es la interfaz de usuario. El diseño original utilizaba una pantalla LCD basada en caracteres de 4 líneas. El controlador HD44780 de estos LCD tiene su propia tabla de señales ROM, que ocupa más de 1 kB de espacio por sí sola.

[Jaromir] Podría enviar el reproductor BrainF * ck sin la pantalla LCD, y probablemente estaría bien en el concurso. Sin embargo, eso no fue suficiente para él. Sabía que podía obtener una salida de personaje en las reglas del concurso. La solución fue un poco de compresión creativa.

En lugar de la representación píxel por píxel de los caracteres, [Jaromir] creó una paleta de 16 vectores de una octava de patrones de uso común. Los personajes se crean combinando estos vectores. Cada carácter tiene 4 x 8 píxeles, por lo que se utilizan 4 vectores para cada carácter. La parte difícil fue elegir patrones de piezas de uso frecuente para los vectores.

La primera iteración fue bastante prometedora: el texto era generalmente legible, pero algunas señales eran bastante malas. [Jaromir] lo sostuvo, reduciendo y optimizando su paleta de vectores al doble. El diseño final es bastante malo. Cada carácter utiliza 16 bits de almacenamiento (cuatro valores de búsqueda de vectores de 4 bits). La paleta de vectores en sí usa 16 bytes. Eso significa que 64 caracteres comen solo 144 bytes de rayos.
Exactamente ese truco que esperábamos ver en el desafío de 1 kB. Algunos pensamientos creativos encuentran la manera de sortear una barrera aparentemente imposible. La mejor parte de todo es que [Jaromir] documentó su trabajo, por lo que ahora cualquiera puede usarlo en el desafío de 1 kB y más.

Si tiene un proyecto nuevo en mente, ¡todavía hay tiempo suficiente para participar en el desafío de 1 kB! La fecha límite es el 5 de enero, ¡así que échale un vistazo y dispara tus monturas!

  • Scott_Tx dice:

    ese es el tipo de TOC que podría llevarnos a Windows 10 en un disquete. 🙂

    • Ostraco dice:

      FORTH OS en el espacio integrado.

    • Dave Davidson dice:

      La NSA funciona mucho en Windows 11

    • Thomas R. Koll (@ananasblau) dice:

      Dudo que los controladores win10 para disquetes sean adecuados para el tiempo de CD-ROM.

      • Genki dice:

        Desafío publicado: haga un controlador W10 para un disquete tan pequeño como 1k.

        • Steve dice:

          Barney Stinson, ¿verdad?

      • MikeRJ45 dice:

        https://github.com/Microsoft/Windows-driver-samples/blob/master/storage/sfloppy/src/floppy.c

        Fuente de 93k del controlador súper débil solo. Sin incluir los conductores de bus inferiores y los marcos de los que depende.

        Tenga en cuenta que este es el controlador de ventana oficial “apropiado”. La antítesis del desafío 1k.

    • Martín dice:

      En el momento en que se hizo esto, es aún más difícil encontrar un disquete y un disco que funcionen. 🙂

      • pícaro dice:

        Me tomó 3 meses buscar y preguntar en Facebook y Craigslist antes de que un amigo encontrara Dimension 3000 en su ático, que todavía tenía un disquete en funcionamiento. Después de todo, el disco que quería leer estaba dañado.

        • Steve dice:

          Predigo una buena carrera en política para ese récord.

        • Ostraco dice:

          Más difícil de encontrar MB con IDE y conexión suelta.

  • Graham Briggs dice:

    ¡Buena solución!

    Utiliza el bit 0 de cada patrón de bytes como una máscara inversa, lo que le da 32 patrones posibles de 7 bits en lugar de 16 patrones de 8 bits, donde el bit 0 siempre está limpio. Pero eso podría ampliar el código de texto.

    • Graham Briggs dice:

      Er, eso no tiene ningún sentido considerándolo … Tenía la intención de que el bit inverso estuviera en los caracteres de definición, pero eso sería un poco menos flexible incluso porque eso es completamente de 4, lo que reduciría los patrones a 8 .

  • protomaker3dprinter dice:

    Pruebe ASCII para 127 bytes Juego de caracteres
    https://eo.wikipedia.org/wiki/ASCII

    • Graham Briggs dice:

      Un conjunto de caracteres de 127 píxeles de 4 × 8 utiliza 508 bytes para definir los patrones.

      • Steven Clark dice:

        Solo 94 son imprimibles sin espacio. Eso es 376 bytes. Algunos de estos probablemente podrían adaptarse aún más como ilegibles para ese tamaño. Si solo tiene 64, diremos 30 y luego 256 bytes.

    • richfiles dice:

      ASCII solo representa caracteres en un conjunto … ASCII no es un mapa de bits. Se trata del mapa de bits real.
      Existe una gran diferencia

    • Dissy dice:

      La imagen de la página a la que está enlazando, que contiene la representación visual de esos caracteres ascii, tiene 2,5 millones de bytes.
      Tiene más de 27 mil bytes por compresión PNG.

      Usted, señor, ha superado con creces el límite de almacenamiento de datos de 1024 bytes en su solución.

  • fontanero espíritu dice:

    Esto es pura poesía.

    • Biomed dice:

      Acordado.

  • DainBramage dice:

    Muy impresionante algo de codificación allí.

  • Dan dice:

    ¿Puede organizar estos picos de patrones de píxeles de acuerdo con el tamaño y luego asumir que la longitud de bits disminuye a una velocidad definida? es decir, ¿puede entremezclar los datos de modo que los 1 estén principalmente en la esquina inferior izquierda de la tabla? ¿Ves lo que quiero decir? Quizás puedas, pero el código para manejarlo sería más grande que los datos almacenados. No sé.

    • jaromirs dice:

      Gracias por una sugerencia.
      Sí, la frecuencia de los vectores es muy diferente, como 50 para los más utilizados y 3 para los menos utilizados. La longitud de bit variable tendría sentido aquí, teóricamente. Sin embargo, considerando el hecho de que tengo una codificación de 180B libre, el decodificador probablemente ocupará más espacio del que la codificación puede ahorrar. En mi caso, un decodificador es solo un puntero de datos y un mordisco que cambia de patrones fijos a largos.
      Este es un conjunto de datos muy pequeño y cada byte / instrucción cuenta, si fuera un pedido grande, definitivamente iría aquí, aunque podría ser un experimento interesante de todos modos.

      • SarahC dice:

        ¿Tienes una demostración en alguna parte? ¿JavaScript tal vez?

  • cnlohr dice:

    Me recuerda que necesito escribir un algoritmo para crear las llamadas de dibujo para el VNC FPS en el ESP. Tener que escribir un programa que descubrió cómo usar cuadrados para representar texto. algunos de ellos se comprimieron muy bien, otros eran más grandes que si solo representara las piezas en bruto 🙁

    • cnlohr dice:

      Aunque esto es simplemente bueno.

  • ROBÓ dice:

    Eso es exactamente lo que me gustaría ver en el desafío de 1kB (1KiB en SI).

  • alexcat3 dice:

    ¿Por qué no usó esta fuente?
    http://fontstruct.com/fontstructions/show/716744/3_by_5_pixel_font
    Sería aproximadamente del mismo tamaño, y no necesitaría pensar en esa loca compresión.

    • Gryd3 dice:

      ¿Puede decirnos cuánto espacio usaría esto?
      Si puede decirnos eso, entonces por qué.

      • Lennart dice:

        Necesitará 15 bits. Eso es dos bytes por carácter, sin matriz de vectores y probablemente un decodificador más pequeño.

        • Ben Hencke dice:

          Eso es lo que usé para OKOS, incluso el soporte de enlace descendente relleno en el bit 16 (si puede guardar los 10 bytes para admitirlo). Usé 40 caracteres imprimibles en 80 bytes. Otros 50 bytes para decodificar y enviar i2c. 3 × 5 es legible, pero no tan agradable como 4 × 8.
          https://la-tecnologia.io/project/18774-one-kilobyte-operating-system-okos

  • Steve dice:

    Gran idea, gran ejecución.

  • Lennart dice:

    La fuente de 3 × 5 anterior no es muy legible, por lo que otra solución es reducir la fuente a 4 × 6 o 4 × 5, esto reduce la combinación requerida en la tabla de vectores y puede ser más fácil crear los caracteres más legibles.

  • algún chico dice:

    Hoy en día hay un bloatware terrible en todas partes, es realmente agradable ver a alguien hablar sobre 180B (¡bytes!) Quedan e intentar optimizar su código realmente bien.

Ricardo Prieto
Ricardo Prieto

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *