El reto

Simplemente escriba un programa que genere su propio código fuente.

Nada más que una quine regular.

El problema

No tenemos una computadora, por lo que debemos ejecutar el programa en un dispositivo lógico programable (como un FPGA, un CPLD, una matriz de compuerta ...).

Las normas

• Cualquier dispositivo disponible en el mercado (como una impresora conectada a través del puerto Centronics, una pantalla LED, un terminal RS232 ...) conectado al dispositivo lógico se puede utilizar para emitir el programa.

• ¡Si utiliza cualquier tipo de dispositivo programable como dispositivo de salida, no podrá colocar ninguna lógica de programa allí!

  Ejemplo: si utiliza RS232 para enviar datos a una computadora, la computadora no debe hacer nada más que mostrar los datos recibidos del RS232. Sin embargo, puede activar las opciones RS232, como hacer eco de los datos al dispositivo lógico si algún programa de terminal existente tiene esta característica.

• Se puede utilizar cualquier codificación "estándar" (reciente o histórica) (ASCII, UNICODE, EBCDIC, código Morse ...).

• El programa solo necesita generar su propio código fuente. El archivo que solo contiene la asignación entre VHDL / Verilog / ... "cables" y los pines de E / S reales, el archivo que contiene la configuración del compilador y archivos similares no se consideran como "código fuente" y no necesitan ser escritos.
• Tiene un pin de entrada de reloj con la frecuencia de su elección (si lo necesita).
• Las unidades en chip (como SRAM en chip o multiplicadores en chip) no deben usarse.
• Para probar el código, puede simular el dispositivo de salida usando código adicional; por supuesto, también puede simular el dispositivo lógico (si no tiene uno real).
• Se aplican lagunas estándar.

El ganador

• Para calcular el tamaño del programa, se supone que el dispositivo de salida real (por ejemplo, la impresora) está conectado a algunos pines de E / S del dispositivo lógico.
• El código que requiere la menor cantidad de celdas "LE" en mi FPGA (Altera EP2C20F484C7) gana.
• Si mi FPGA es demasiado pequeña (= no lo suficientemente grande para la solución más pequeña) compilamos para la más grande que tiene celdas de tipo "LE" (EP4CGX150DF31I7).
• Si todavía no es suficiente, probamos el más grande compatible con el compilador gratuito (EP2AGX260FF35I5).
• Si ese dispositivo sigue siendo demasiado pequeño, el tamaño del código fuente cuenta.

Nota

Buscando "quine VHDL" en Google, ¡encontré al menos tres quines escritas en VHDL en la primera página!

Desafortunadamente, ninguno de ellos funcionará en un dispositivo lógico real, sino solo en el emulador porque se usa la salida estándar (del emulador).

¡Buena suerte!

Verilog, optimizado para área, 130 puertas LE

La quine misma (el archivo real está codificado en DEC SIXBIT ):

module q(s,d);inout s,d;wire[0:1023]v=1024'b0110111100101001011001111110110110010110100100001111011010010111010101110101010110010110111100101001011001111110110100100110100100001111011010100111010101110110111000011100111100111010011001111011100000001001000111011010100111000101100111111010100111010111010100100110101101101110111010011111010110111000011011001101111000011110011100111000000010001100001011111100111001011001001001111001010000001100110010011010011001100010001010100111100101010010011000101001011001111010011011100000001010010111011010010010110100010110111010100111011010100001100100011111100000011010010111110101110110100100010110111001011011101001000000001001011011001100111001010000001010100111011010100010110100010110111001011011101001001011011011111001001101011011001001010000000000000000101101101111100100110101101100100101000000110001001000110011001100100100001001011011101001101110101111110101110100000000110011001100100100011011110111101001110010100101111011010000011010010001010000010010010011111101110110011101010001010000010010010100000111100010;reg[9:0]i=759;reg[2:0]j=7;assign d=j<6?j==2:v[i];always@(posedge s)if(j>5)begin i=i+1;j=j&1^!i?7:1;end else j=j+1;endmodule

Versión legible con comentarios y un banco de pruebas:

module q(s,d);
   // Declare the ports. Making them both "inout" is shortest.
   inout s,d;
   // Data storage for the program.
   wire[0:1023]v=1024'b{DATA GOES HERE};
   // i is the current bit number within the program.
   // This is relative to the /end of the data storage/ (not to the start
   // of the program), so it starts at a nonzero value so that the output
   // starts at the start of the program.
   reg[9:0]i=759;
   // When expanding bits to (6-bit) bytes, j is the bit number within
   // the expansion, from 1 for the first bit up to 6 for the last.
   // When not expanding, j is always 7.
   // DEC SIXBIT encoding for 0 is (from MSB to LSB) 010 000.
   // DEC SIXBIT encoding for 1 is (from MSB to LSB) 010 001.
   // We use SSI encoding for the output, so the MSB is sent first.
   reg[2:0]j=7;
   assign d=j<6?j==2:v[i];
   // When we get a strobe:
   always@(posedge s)
     // If we just output a bit, move onto the next bit.
     // We may also need to reset j.
     if(j>5)
       begin 
          i=i+1;
          j=j&1^!i?7:1;
       end 
     else 
       // If we're inside a bit, continue to output that bit.
       j=j+1;
endmodule
// {TESTBENCH BELOW HERE}

`timescale 10ns / 1ns
module testbench();
   reg clock = 0;
   wire data, strobe;

   always
     #1 clock <= !clock;
   initial
     #14304 $finish;

   assign strobe = clock;
   q testquine(.s(strobe),.d(data));

   always @(negedge strobe)
      $display("%d", data);

endmodule // testbench

El uso de Verilog me da mucho más control sobre los detalles de bajo nivel que el que tendría con Verity. En particular, me permite controlar el reloj y restablecer las reglas yo mismo. Este programa está diseñado para una conexión en serie síncrona con entrada estroboscópica sy salida de datosd. Aunque cada uno solo se usa en una dirección, los declare a ambos como bidireccionales para guardar algunos bytes; Tuve que jugar golf a las partes que no son de datos del programa hasta 1024 bits para poder usar puertas lógicas de 10 bits internamente (los bits adicionales serían más costosos en el área), y solo se reduce a 1008, por lo que ahorros como Esto es importante. Para ahorrar una cantidad sustancial de código, confío en el circuito de reinicio de hardware del FPGA en lugar de agregar el mío, y fusiono las entradas de luz estroboscópica y reloj (que es un viejo truco que está mal visto hoy en día porque lo hace difícil) para mantener el árbol del reloj equilibrado a altas velocidades, pero es útil para jugar al golf. Espero que sea sintetizable; No sé qué tan bien los sintetizadores Verilog manejan el uso de un puerto bidireccional como reloj.

La fuente está codificada en DEC SIXBIT (supongo que aquí interpretamos su alfabeto único de letras como minúsculas; un sintetizador Verilog no tendría ninguna razón para usar una interpretación en mayúsculas). Utilicé un juego de caracteres de seis bits internamente en mi otra solución, luego desperdicié bytes convirtiéndolo; es mejor usar un conjunto de caracteres que sea "naturalmente" de seis bits de ancho para que no sea necesaria la conversión. Elegí este conjunto de caracteres de seis bits en particular porque 0y 1difieren solo en su bit menos significativo, y solo tengo otro conjunto de bits, lo que significa que el circuito para convertir un dígito binario a DEC SIXBIT (es decir, "escapar" de una cadena) puede ser muy simple. Curiosamente, al conjunto de caracteres en cuestión le falta un carácter de nueva línea; el programa original está todo en una línea, no solopara que sea más fácil generar, ¡pero para que sea posible codificar! Es bueno que a Verilog no le interesen los espacios en blanco.

El protocolo para enviar datos al host se basa en la interfaz serial sincrónica. Lo elegí porque está sincronizado (lo que me permite usar el truco del reloj / luz estroboscópica, y también me permite escribir un programa portátil que no se basa en dispositivos de temporización en chip), y porque es muy simple (por lo tanto, no tener que desperdiciar mucho código implementándolo). Este protocolo no especifica un método para especificar dónde termina el mensaje (se supone que el host debe saber); En este caso particular, rellené la salida hasta un múltiplo de 1024 bits con cero bits (un total de 16 bits de relleno), después de lo cual (según lo requerido por SSI) el mensaje se reinicia. (No implemento un temporizador de modo inactivo; su propósito es determinar si enviar un nuevo mensaje o si repetir el mensaje anterior, y como este programa siempre envía su propio código fuente como mensaje, la distinción no es visible Puedes considerar que es longitud 0,

En términos de la lógica real, lo más interesante es la forma en que divido las variables para reducir la cantidad de área necesaria en el chip. i, el registro más grande, contiene la "dirección" actual dentro de los datos del programa y solo se modifica incrementándola; Esto significa que su lógica se puede sintetizar usando la construcción de medio sumador (que, como su nombre lo indica, usa solo la mitad de los recursos que un sumador; esto en su mayoría solo importa en los FPGA más pequeños, los más grandes usarán 3 entradas o incluso LUT de 4 entradas que son lo suficientemente potentes como para tener mucha capacidad desperdiciada sintetizando un medio sumador). El registro más pequeño,j, es básicamente un estado de máquina de estado y, por lo tanto, maneja la mayor parte de la lógica compleja del programa. Es lo suficientemente pequeño como para que pueda manejarse completamente a través de una tabla de búsqueda en un FPGA más grande (haciendo que la lógica básicamente desaparezca); en caso de que el programa se sintetice para un FPGA pequeño, elegí su codificación de tal manera que pocas partes del código se preocupen por sus tres bits a la vez.

También vale la pena señalar que permuté cíclicamente el almacenamiento de datos. Podemos comenzar a iapuntar a cualquier lugar dentro de él, no necesariamente al comienzo. Con la disposición que se ve aquí, podemos imprimir desde el valor inicial ihasta el final directamente, luego imprimir todo el conjunto escapado, luego imprimir desde el principio hasta el valor inicial de i, para imprimir todas las partes de los datos en el lugares correctos sin necesidad de guardar y restaurar el valor de i. (Este truco también puede ser útil para quines en otros idiomas).

La fuente tiene 1192 bytes de 6 bits de longitud, el equivalente a 894 bytes de 8 bits. Es un poco vergonzoso que esto contenga menos bytes de origen que mi envío de Verity, a pesar de estar optimizado para algo completamente diferente; Esto se debe principalmente a que Verilog tiene cadenas y Verity no, lo que significa que aunque he codificado el programa en binario en lugar de octal (que es sustancialmente menos eficiente en términos de tamaño del código fuente), puedo codificar cada byte del programa utilizando seis caracteres de seis bits (uno para cada bit) en lugar de ocho caracteres de ocho bits (cuatro para cada dígito octal). Una presentación de Verilog que codificó el programa en octal probablemente sería más pequeña en términos de tamaño del código fuente, pero casi seguramente sería más grande en área.

No sé cuánta área usará este programa; depende mucho de cuán poderoso sea el optimizador en su sintetizador Verilog (porque el problema de minimización de convertir los datos almacenados en un conjunto de puertas lógicas es algo que se hace en el sintetizador en sí; arrojar el trabajo en el sintetizador hace que el código fuente mismo mucho más corto y, por lo tanto, reduce el área necesaria para almacenarlo). Sin embargo, debe tener una complejidad de O (n log n) y, por lo tanto, ser mucho más pequeña que la O (n²) del otro programa. Me interesaría ver que el OP intente ejecutarlo en su FPGA. (Sin embargo, puede llevar bastante tiempo sintetizar; hay varios pasos que puede seguir para optimizar un programa para el tiempo de compilación, pero no tomé ninguno aquí porque causaría un programa más grande = área más grande).

Verity 0.10, optimizado para el tamaño del código fuente (1944 bytes)

Originalmente leí mal la pregunta y la interpreté como un código de golf. Probablemente fue lo mejor, ya que es mucho más fácil escribir un quine con un código fuente corto que un código objeto corto bajo las restricciones de la pregunta; eso hizo la pregunta lo suficientemente fácil como para sentir que razonablemente podría producir una respuesta, y podría funcionar como un trampolín en el camino hacia una mejor respuesta. También me impulsó a usar un lenguaje de nivel superior para la entrada, lo que significa que necesitaría expresar menos en el programa en sí. No creé Verity como un lenguaje de golf para hardware (en realidad, me contrataron para crearlo hace un tiempo en un contexto completamente diferente), pero hay una gran reminiscencia (por ejemplo, es un nivel sustancialmente más alto que un HDL típico, y tiene mucho menos repetitivo; también es mucho más portátil que el HDL típico).

Estoy bastante seguro de que la solución correcta para el código de objeto corto implica almacenar los datos en algún tipo de estructura de árbol, dado que la pregunta no permite el uso de ROM de bloque, que es donde normalmente lo almacenarías en un programa práctico; Podría intentar escribir un programa que use este principio (no estoy seguro de qué idioma, tal vez Verity, tal vez Verilog; VHDL tiene demasiadas repeticiones para ser óptimo para este tipo de problema) en algún momento. Eso significaría que no necesitaría pasar cada bit del código fuente a cada bit de su "ROM creada manualmente". Sin embargo, el compilador Verity actualmente sintetiza la estructura de la salida en función de la precedencia y la asociatividad de la entrada, lo que significa que representa efectivamente el puntero de instrucción (por lo tanto, el índice de la tabla de búsqueda) en unario,

El programa en sí:

import <print>new x:=0$1296in(\p.\z.\a.new y:=(-a 5-a 1-a 1-a 2-a 4-a 2-a 3-a 2-a 6-a 2-a 0-a 3-a 0-a 4-a 4-a 7-a 4-a 2-a 6-a 2-a 5-a 1-a 2-a 2-a 0-a 3-a 6-a 7-a 2-a 2-a 1-a 1-a 3-a 3-a 0-a 4-a 4-a 3-a 2-a 7-a 5-a 7-a 0-a 6-a 4-a 4-a 1-a 6-a 2-a 6-a 1-a 7-a 6-a 6-a 5-a 1-a 2-a 2-a 0-a 5-a 0-a 0-a 4-a 2-a 6-a 5-a 0-a 0-a 6-a 3-a 6-a 5-a 0-a 0-a 5-a 0-a 6-a 5-a 2-a 2-a 1-a 1-a 3-a 3-a 0-a 4-a 5-a 3-a 2-a 7-a 5-a 7-a 0-a 5-a 5-a 5-a 1-a 4-a 4-a 3-a 1-a 5-a 5-a 1-a 2-a 2-a 0-a 4-a 3-a 3-a 4-a 1-a 5-a 1-a 0-a 2-a 1-a 1-a 1-a 4-a 4-a 3-a 6-a 7-a 0-a 6-a 0-a 1-a 3-a 2-a 0-a 5-a 4-a 2-a 0-a 5-a 5-a 1-a 2-a 1-a 0-a 4-a 6-a 3-a 4-a 7-a 3-a 6-a 2-a 6-a 0-a 3-a 4-a 1-a 1-a 1-a 2-a 2-a 0-a 4-a 6-a 3-a 3-a 5-a 1-a 7-a 2-a 6-a 1-a 1-a 0-a 2-a 7-a 2-a 1-a 1-a 0-a 4-a 6-a 3-a 1-a 5-a 3-a 7-a 5-a 1-a 2-a 1-a 0-a 4-a 6-a 3-a 5-a 7-a 5-a 7-a 4-a 6-a 5-a 6-a 0-a 3-a 4-a 1-a 1-a 1-a 2-a 2-a 0-a 4-a 3-a 3-a 4-a 1-a 5-a 1-a 0-a 2-a 1-a 1-a 1-a 4-a 5-a 3-a 6-a 7-a 0-a 6-a 0-a 1-a 3-a 2-a 0-a 5-a 4-a 2-a 0-a 4-a 1-a 7-a 7-a 6-a 3-a 7-a 4-a 2-a 0-a 4-a 3-a 6-a 2-a 6-a 3-a 7-a 4-a 2-a 0-a 5-a 4-a 6-a 0-a 7-a 2-a 0-a 1-a 4-a 5-a 3-a 4-a 4-a 4-a 4-a 3-a 6-a 4-a 4-a 4-a 4-a 3-a 6-a 2-a 6-a 1-a 5-a 3-a 7-a 4-a 2-a 0-a 4-a 4-a 6-a 5-a 6-a 3-a 7-a 5-a 3-a 2-a 7-a 5-a 7-a 1-a 4-a 5-a 3-a 6-a 7-a 6-a 7-a 3-a 6-a 1-a 5-a 1-a 1-a 0-a 2-a 7-a 2-a 1-a 1-a 0-a 4-a 7-a 2-a 7-a 1-a 5-a 1-a 4-a 2-a 3-a 7-a 4-a 3-a 2-a 7-a 5-a 7-a 1-a 4-a 4-a 3-a 6-a 7-a 6-a 7-a 6-a 6-a 1-a 5-a 1-a 5-a 4-a 2-a 6-a 2-a 5-a 1-a 2-a 2-a 0-a 3-a 0-a 5-a 1-a 4-a 4-a 3-a 4-a 4-a 4-a 4-a 6-a 6-a 4-a 4-a 4-a 4-a 3-a 6-a 2-a 6-a 1-a 5-a 0-a 5-a 0-a 0-a 0-a 1-a 6-a 5-a 4-a 3-a 2-a 7-a 5-a 7-a 1-a 4-a 4-a 3-a 6-a 7-a 6-a 7-a 3-a 6-a 2-a 0-a 0-a 1-a 4-a 7-a 4-a 7-a 1-a 6-a 2-a 6-a 1-a 7-a 3-a 6-a 3-a 7-a 0-a 6-a 1-a 5-!x)in while!x>0do(p(if z<32then z+92else z);if z==45then while!y>0do(p 97;p 32;p(48^!y$$3$$32);p 45;y:=!y>>3)else skip;x:=!x>>6))print(!x$$6$$32)(\d.x:=!x>>3^d<<1293;0)

Más legible:

import <print>
new x := 0$1296 in
(\p.\z.\a.
  new y := (-a 5-a 1-
            # a ton of calls to a() omitted...
            -a 1-a 5-!x) in
  while !x>0 do (
    p(if z<32 then z+92 else z);
    if z==45
    then while !y>0 do (
      p 97;
      p 32;
      p(48^!y$$3$$32);
      p 45;
      y:=!y>>3 )
    else skip;
    x:=!x>>6
  )
)(print)(!x$$6$$32)(\d.x:=!x>>3^d<<1293;0)

La idea básica es que almacenamos todos los datos en la variable x. (Como es habitual para un quine, tenemos una sección de código y una sección de datos; los datos codifican el texto del código y también se pueden usar para regenerar el texto de los datos). Desafortunadamente, Verity actualmente no permite las constantes se escribirán en el código fuente (usa enteros OCaml durante la compilación para representar enteros en la fuente, lo que claramente no es correcto en un lenguaje que admita tipos enteros arbitrariamente anchos) y, además, no permite que las constantes sean especificado en octal, por lo que generamos el valor de xen tiempo de ejecución mediante llamadas repetidas a una funcióna. Podríamos crear una función nula y llamarla repetidamente como declaraciones separadas, pero eso dificultaría identificar dónde comenzar a generar el texto de la sección de datos. Entonces, en cambio, adevolví un número entero y utilicé la aritmética para almacenar los datos (Verity garantiza que la aritmética evalúe de izquierda a derecha). La sección de datos está codificada xcon un solo -signo; cuando esto se encuentra en tiempo de ejecución, se expande al máximo -a 5-a 1-, etc., mediante el uso de y.

Inicializar ycomo una copia de xaquí es bastante sutil. Debido a que adevuelve cero específicamente, la mayor parte de la suma es solo cero menos cero menos ... y se cancela por sí solo. Terminamos con !x(es decir, "el valor de x"; en Verity, como en OCaml, el nombre de una variable funciona más como un puntero que cualquier otra cosa, y debe desreferenciarlo explícitamente para obtener el valor de la variable). Las reglas de Verity para el menos unario son un poco complejas: el menos unario vse escribe como (-v), por lo que se (-0-0-0-!x)analiza como (-(0-0-0-!x)), que es igual a !x, y terminamos inicializando ycomo una copia de x. (También vale la pena señalar que Verity no esllamada por valor, sino que permite que las funciones y los operadores elijan el orden en que evalúan las cosas; -evaluará el argumento izquierdo antes del argumento derecho y, en particular, si el argumento izquierdo tiene efectos secundarios, serán visibles cuando se evalúe el argumento derecho).

Cada carácter del código fuente se representa utilizando dos dígitos octales. Esto significa que el código fuente está limitado a 64 caracteres diferentes, por lo que tuve que crear mi propia página de códigos para uso interno. La salida está en ASCII, por lo que necesitaba convertir internamente; esto es para lo que (if z<32 then z+92 else z)sirve. Aquí está el conjunto de caracteres que usé en la representación interna, en orden numérico (es decir, \tiene el punto de código 0, ?tiene el punto de código 63):

\]^_`abcdefghijklmnopqrstuvwxyz{ !"#$%&'()*+,-./0123456789:;<=>?

Este conjunto de caracteres nos da la mayoría de los personajes importantes para Verity. Faltan caracteres notables }(lo que significa que no podemos crear un bloque usando {}, pero afortunadamente todas las declaraciones son expresiones, por lo que podemos usar ()en su lugar); y |(es por eso que tuve que usar un OR exclusivo en lugar de inclusivo al crear el valor de x, lo que significa que necesito inicializarlo a 0; sin embargo, necesitaba especificar qué tan grande era de todos modos). Algunos de los caracteres críticos que quería asegurar que estaban en el conjunto de caracteres eran <>(para importaciones, también cambios), ()(muy difícil de escribir un programa que se pueda analizar sin estos), $(para todo lo que tenga que ver con el ancho de bits) y \( para lambdas; teóricamente podríamos solucionar esto conlet…in pero sería mucho más detallado).

Con el fin de acortar un poco el programa, construí abreviaturas para printy para !x$$6$$32(es decir, "los 6 bits inferiores de !x, emitidos para ser utilizables en la printbiblioteca) uniéndolos temporalmente a argumentos lambda.

Finalmente, está el problema de la producción. Verity proporciona una printbiblioteca destinada a la salida de depuración. En un simulador, imprime los códigos ASCII a la salida estándar, que es perfectamente utilizable para probar el programa. En una placa de circuito físico, depende de printque se haya escrito una biblioteca para el chip y la placa en particular que lo rodean; Hay una printbiblioteca en la distribución de Verity para una placa de evaluación a la que tuve acceso que imprime la salida en pantallas de siete segmentos. Dado que la biblioteca terminará ocupando espacio en la placa de circuito resultante, puede valer la pena usar un lenguaje diferente para una solución optimizada a este problema para que podamos generar los bits de la salida directamente en los cables.

Por cierto, este programa es O (n²) en hardware, lo que significa que es mucho peor en un simulador (sospecho que O (n⁴); sin embargo, no estoy seguro, pero fue lo suficientemente difícil de simular que parece poco probable que sea incluso cúbico , y en función de cómo reaccionó el tiempo a mis cambios mientras escribía el programa, la función parece crecer muy rápidamente). El compilador Verity necesitaba 436 pases de optimización (que es mucho, mucho más de lo que normalmente usaría) para optimizar el programa, e incluso después de eso, simular que era muy difícil para mi computadora portátil. La ejecución completa de compilación y simulación tomó el siguiente tiempo:

real  112m6.096s
user  105m25.136s
sys   0m14.080s

y alcanzó su punto máximo en 2740232 kibibytes de memoria. El programa toma un total de 213646 ciclos de reloj para ejecutarse. ¡Sin embargo, funciona!

De todos modos, esta respuesta realmente no cumple la pregunta ya que estaba optimizando para la cosa incorrecta, pero dado que todavía no hay otras respuestas, esta es la mejor por defecto (y es bueno ver cómo se vería una quine de golf en un lenguaje de hardware). Actualmente no estoy seguro de si trabajaré o no en un programa que tenga como objetivo producir una salida más optimizada en el chip. (Es probable que sea mucho más grande en términos de fuente, ya que una codificación de datos O (n) sería bastante más compleja que la que se ve aquí).