Verilog, otimizado para área, portões 130 LE
O próprio quine (o arquivo real é codificado em 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
Versão legível com comentários e um banco de testes:
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
O uso do Verilog me dá um controle consideravelmente maior sobre os detalhes de baixo nível do que eu teria com o Verity. Em particular, ele permite controlar o relógio e redefinir as regras. Este programa destina-se a uma conexão serial síncrona com entrada estroboscópica se saída de dadosd. Embora cada um seja usado apenas em uma direção, declarei os dois como bidirecionais para economizar alguns bytes; Eu tive que jogar golfe em partes que não são de dados do programa em até 1024 bits para poder usar portas lógicas de 10 bits internamente (bits extras seriam mais caros em área), e ele apenas reduz em 1008, para economias como isso é importante. Para economizar uma quantidade substancial de código, confio nos circuitos de redefinição de hardware do FPGA, em vez de adicionar os meus, e mesclo as entradas estroboscópicas e de clock (que é um truque antigo que meio que é desaprovado hoje em dia porque dificulta para manter a árvore do relógio equilibrada em altas velocidades, mas é útil para jogar golfe.) Espero que seja sintetizável; Não sei como os sintetizadores Verilog lidam com o uso de uma porta bidirecional como relógio.
A fonte é codificada em DEC SIXBIT (estou assumindo aqui que interpretamos seu único alfabeto de letras como minúsculas; um sintetizador Verilog não teria motivos para usar uma interpretação em maiúsculas). Usei um conjunto de caracteres de seis bits internamente em minha outra solução e perdi bytes convertendo-o; é melhor usar um conjunto de caracteres "naturalmente" com seis bits de largura, para que nenhuma conversão seja necessária. Eu escolhi este conjunto de caracteres de seis bits particular, porque 0e 1diferem apenas em seu bit menos significativo, e só tem um outro conjunto de bits, o que significa que o circuito para converter um dígito binário de dezembro SIXBIT (ou seja, "escapar" uma string) pode ser muito simples. Curiosamente, o conjunto de caracteres em questão está faltando um caractere de nova linha; o programa original é tudo em uma linha e não apenaspara facilitar a geração, mas para possibilitar a codificação! É bom que a Verilog não se importe com espaços em branco.
O protocolo para enviar dados ao host é baseado na Interface Serial Síncrona. Eu o escolhi porque é com clock (permitindo que eu use o truque de relógio / estroboscópio, e também permitindo que eu escreva um programa portátil que não depende de dispositivos de temporização no chip) e porque é muito simples (portanto, não tem que desperdiçar muito código implementando-o). Este protocolo não especifica um método para especificar onde a mensagem termina (o host deve saber); nesse caso em particular, preenchi a saída em um múltiplo de 1024 bits com zero bits (um total de 16 bits de preenchimento), após o qual (conforme exigido pelo SSI) a mensagem é reiniciada. (Não implemento um timer no modo inativo; seu objetivo é determinar se uma nova mensagem deve ser enviada ou se deve repetir a mensagem anterior. Como esse programa sempre envia seu próprio código-fonte como mensagem, a distinção não é visível. Você pode considerar o comprimento 0,
Em termos da lógica real, o mais interessante é a maneira como eu divido as variáveis para reduzir a quantidade de área necessária no chip. i, o registro maior, mantém o "endereço" atual nos dados do programa e só é alterado através do incremento; isso significa que sua lógica pode ser sintetizada usando a construção de meio adicionador (que, como o nome sugere, usa apenas metade dos recursos que um adicionador faz; isso importa principalmente nos menores FPGAs, os maiores usarão 3 entradas ou mesmo LUTs de 4 entradas que são poderosas o suficiente para ter muita capacidade desperdiçada sintetizando um meio adicionador). O registro menor,j, é basicamente um estado de máquina de estado e, portanto, lida com a maior parte da lógica complexa do programa. É pequeno o suficiente para ser manuseado inteiramente via tabela de pesquisa em um FPGA maior (fazendo a lógica basicamente desaparecer); caso o programa seja sintetizado para um pequeno FPGA, escolhi sua codificação de forma que poucas partes do código se importem com os três bits de uma só vez.
Também vale a pena notar que permutei ciclicamente o armazenamento de dados. Podemos começar a iapontar para qualquer lugar dentro dele, não necessariamente no início. Com o arranjo visto aqui, podemos imprimir idiretamente do valor inicial de até o fim, depois imprimir toda a matriz escapada, depois imprimir do início ao valor inicial de i, para imprimir todas as partes dos dados no lugares certos sem a necessidade de salvar e restaurar o valor de i. (Esse truque também pode ser útil para quines em outros idiomas.)
A origem tem 1192 bytes de 6 bits, o equivalente a 894 bytes de 8 bits. É meio embaraçoso que isso contenha menos bytes de origem do que meu envio do Verity, apesar de otimizado para algo totalmente diferente; isso ocorre principalmente porque o Verilog possui seqüências de caracteres e o Verity não, o que significa que, embora eu tenha codificado o programa em binário e não em octal (que é substancialmente menos eficiente em termos de tamanho do código-fonte), posso codificar cada byte do programa usando seis caracteres de seis bits (um para cada bit) em vez de oito caracteres de oito bits (quatro para cada dígito octal). Uma submissão da Verilog que codificasse o programa em octal provavelmente seria menor em termos de tamanho do código-fonte, mas certamente seria maior em área.
Não sei quanta área esse programa vai acabar usando; depende muito de quão poderoso o otimizador é no seu sintetizador Verilog (porque o problema de minimização de converter os dados armazenados em um conjunto de portas lógicas é algo que é feito no próprio sintetizador; jogar o trabalho no sintetizador torna o próprio código-fonte muito mais curto e, portanto, reduz a área necessária para armazená-lo). Porém, ele deve ter uma complexidade de O (n log n) e, portanto, ser muito menor que o O (n²) do outro programa. Eu ficaria interessado em ver o OP tentar executá-lo em seu FPGA. (Porém, pode levar algum tempo para sintetizar; existem várias etapas que você pode executar para otimizar um programa durante o tempo de compilação, mas eu não tomei nenhuma aqui, pois causaria um programa maior = área maior.)
Verity 0.10, otimizado para o tamanho do código-fonte (1944 bytes)
Eu originalmente interpretei mal a questão e a interpretei como um código-golfe. Provavelmente foi o melhor, pois é muito mais fácil escrever um quine com código-fonte curto do que com código de objeto curto, de acordo com as restrições da pergunta; isso tornou a pergunta fácil o suficiente para que eu pudesse produzir uma resposta razoável e pudesse funcionar como um trampolim no caminho para uma resposta melhor. Também me levou a usar uma linguagem de nível superior para a entrada, o que significa que eu precisaria expressar menos no próprio programa. Não criei o Verity como uma linguagem de golfe para hardware (na verdade, fui contratado para criá-lo há algum tempo em um contexto completamente diferente), mas há uma reminiscência lá (por exemplo, é um nível substancialmente mais alto do que um HDL típico, e tem muito menos clichê; também é muito mais portátil que o HDL típico).
Tenho certeza de que a solução correta para o código de objeto curto envolve armazenar os dados em algum tipo de estrutura em árvore, já que a pergunta não permite o uso do bloco ROM, que é onde você normalmente os armazena em um programa prático; Talvez eu escreva um programa que use esse princípio (não sei qual idioma, talvez Verity, talvez Verilog; o VHDL tem muitos clichês para provavelmente ser o ideal para esse tipo de problema) em algum momento. Isso significaria que você não precisaria passar todos os bits do código fonte para todos os bits da sua "ROM criada manualmente". No entanto, o compilador Verity atualmente sintetiza a estrutura da saída com base na precedência e associatividade da entrada, o que significa que está efetivamente representando o ponteiro da instrução (portanto, o índice da tabela de pesquisa) em unário,
O próprio programa:
Mais legível:
A ideia básica é que armazenemos todos os dados na variável
x. (Como é habitual em um quine, temos uma seção de código e uma seção de dados; os dados codificam o texto do código e também podem ser usados para regenerar o texto dos dados.) Infelizmente, atualmente, o Verity atualmente não permite muito grande constantes a serem escritas no código-fonte (ele usa inteiros OCaml durante a compilação para representar números inteiros na fonte, o que claramente não está correto em uma linguagem que suporta tipos inteiros arbitrariamente amplos) - além disso, não permite que constantes sejam especificado em octal - geramos o valorxem tempo de execução por meio de chamadas repetidas para uma funçãoa. Poderíamos criar uma função nula e chamá-la repetidamente como instruções separadas, mas isso tornaria difícil identificar por onde começar a produzir o texto da seção de dados. Então, em vez disso,aretornei um número inteiro e utilizei a aritmética para armazenar os dados (o Verity garante que a aritmética é avaliada da esquerda para a direita). A seção de dados é codificadaxusando um único-sinal; quando isso é encontrado no tempo de execução, é expandido ao máximo-a 5-a 1-etc., por meio do uso dey.Inicializar
ycomo uma cópia dexé bastante sutil aqui. Comoaretorna zero especificamente, a maior parte da soma é apenas zero menos zero menos ... e se cancela. Terminamos com!x(ou seja, "o valor dex"; no Verity, como no OCaml, o nome de uma variável funciona mais como um ponteiro do que qualquer outra coisa, e você deve desreferenciá-lo explicitamente para obter o valor da variável). As regras da Verity para menos unário são um pouco complexas - o menos unário devé escrito como(-v)- assim(-0-0-0-!x)analisa como(-(0-0-0-!x)), que é igual a!x, e acabamos inicializandoycomo uma cópia dex. (Também vale a pena notar que o Verity não échamar por valor, mas permite que funções e operadores escolham a ordem em que avaliam as coisas;-avaliará o argumento esquerdo antes do argumento direito e, em particular, se o argumento esquerdo tiver efeitos colaterais, eles serão visíveis quando o argumento direito for avaliado.)Cada caractere do código fonte é representado usando dois dígitos octais. Isso significa que o código-fonte é limitado a 64 caracteres diferentes, então tive que criar minha própria página de código para uso interno. A saída é em ASCII, então eu precisei converter internamente; é para isso que
(if z<32 then z+92 else z)serve. Aqui está o conjunto de caracteres que usei na representação interna, em ordem numérica (ou seja,\tem o ponto de código 0, o?ponto de código 63):Esse conjunto de caracteres fornece a maioria dos caracteres importantes para o Verity. Caracteres notáveis ausentes são
}(o que significa que não podemos criar um bloco usando{}, mas felizmente todas as instruções são expressões para que possamos usá-lo()); e|(é por isso que eu tive que usar um OR exclusivo e não inclusivo ao criar o valor dex, o que significa que eu preciso inicializá-lo para 0; no entanto, eu preciso especificar o tamanho dele). Alguns dos caracteres críticos que eu queria garantir estavam no conjunto de caracteres<>(para importação e também para turnos),()(muito difícil escrever um programa que possa ser analisado sem eles),$(para tudo relacionado à largura de bit) e\( para lambdas; teoricamente, poderíamos contornar isso comlet…inmas seria muito mais detalhado).Para tornar o programa um pouco mais curto, construí abreviações para
printe para!x$$6$$32(ou seja, "os 6 bits inferiores!x, convertidos para serem utilizados naprintbiblioteca), ligando-os temporariamente aos argumentos lambda.Finalmente, há a questão da saída. O Verity fornece uma
printbiblioteca destinada à saída de depuração. Em um simulador, ele imprime os códigos ASCII na saída padrão, o que é perfeitamente utilizável para testar o programa. Em uma placa de circuito físico, depende de umaprintbiblioteca ter sido escrita para o chip e a placa em torno dele; há umaprintbiblioteca na distribuição Verity para um painel de avaliação ao qual tive acesso que imprime a saída em displays de sete segmentos. Dado que a biblioteca acabará ocupando espaço na placa de circuito resultante, pode valer a pena usar um idioma diferente para uma solução otimizada para esse problema, para que possamos enviar os bits da saída diretamente nos fios.A propósito, este programa é O (n²) no hardware, o que significa que é muito pior em um simulador (suspeito de O (n⁴); porém, não tenho certeza, mas era difícil o suficiente para simular que parece improvável que seja cúbico e com base em como o tempo reagiu às minhas alterações enquanto eu escrevia o programa, a função parece crescer muito rapidamente). O compilador Verity precisava de 436 passes de otimização (o que é muito, muito mais do que normalmente usaria) para otimizar o programa e, mesmo depois disso, simulá-lo era muito difícil para o meu laptop. A execução completa de compilação e simulação levou o seguinte tempo:
e atingiu o máximo de 2740232 kibibytes de memória. O programa leva um total de 213646 ciclos de relógio para executar. Mas funciona!
Enfim, essa resposta realmente não atende à pergunta, pois eu estava otimizando a coisa errada, mas, como ainda não há outras respostas, essa é a melhor por padrão (e é bom ver como seria uma coluna de golfe em uma linguagem de hardware). No momento, não tenho certeza se trabalharei ou não em um programa que visa produzir uma saída mais otimizada no chip. (Provavelmente seria muito maior em termos de origem, pois uma codificação de dados O (n) seria bastante mais complexa do que a vista aqui.)
fonte
veritygos.orgpara verificação ...