É um modelo matemático de um computador que funciona de forma simples, mas tem o poder computacional total que é possível de ser alcançado. A máquina de Turing é uma das ferramentas mais importantes da ciência da computação teórica, pois apresenta um modelo básico de computação, um sistema matemático capaz de executar cálculos matemáticos gerais, para estudar computadores e algoritmos, ela estava no início da ciência da computação teórica quando Alan Turing a inventou em 1936 e a usou para provar matematicamente coisas essenciais sobre computadores, que seu poder computacional é inevitavelmente limitado, ele mostrou que, embora a máquina de Turing tenha o poder computacional total que podemos esperar, existem problemas que ela é incapaz de resolver, e assim será qualquer outro computador equivalente à máquina de Turing, até o cérebro humano.
Muitos outros chamados sistemas completos de Turing, sistemas com exatamente o mesmo poder computacional de uma máquina de Turing, foram inventados e descobertos, como cálculo lambda ou redes de Petri, a máquina de Turing ainda permanece não apenas relevante, mas provavelmente de maior importância, não historicamente, mas também porque é semelhante a computadores físicos na forma como funciona.
A vantagem de uma máquina de Turing é que ela é, em primeiro lugar, simples, é basicamente um autômato de estado finito operando em uma fita de memória, então pode ser compreendido matematicamente muito facilmente e, em segundo lugar, ao contrário de muitos outros sistemas de computação, semelhante a computadores reais em princípio, principalmente por sua execução sequencial de instruções e posse de uma fita de memória explícita na qual opera, equivalente à RAM em computadores tradicionais.
Observe que uma máquina de Turing pura não pode existir na realidade porque nunca pode existir um computador com quantidade infinita de memória que a máquina de Turing possui; computadores que podem existir fisicamente são realmente equivalentes a autômatos de estado finito, o tipo mais fraco de sistemas de computação.
Podemos ver nossos computadores físicos como aproximações de uma máquina de Turing que, na maioria dos casos relevantes, se comportam da mesma forma, então tendemos a ver os computadores teoricamente como máquinas de Turing com memória limitada.
Embora puramente hipoteticamente, poderíamos entreter uma ideia de um computador que é capaz de fabricar uma nova célula de fita sempre que uma for necessária, que poderia então ter algo como uma fita de memória ilimitada, mas ainda assim seria limitado pelo menos pela quantidade de matéria no universo observável.
Na máquina, os dados e o programa são separados, os dados são armazenados na fita, o programa é representado pela unidade de controle, está mais próximo da arquitetura Harvard do que da arquitetura von Neumann.
Existe algo computacionalmente mais poderoso do que uma máquina de Turing? Sim, mas é apenas uma espécie de fantasia matemática. Veja a máquina oráculo que adiciona um dispositivo especial oráculo a uma máquina de Turing para fazê-la resolver magicamente problemas indecidíveis.
A máquina de Turing possui algumas versões diferentes, como uma com várias fitas de memória, fita de memória ilimitada em ambas descreverá apenas uma das variantes mais comuns.
Uma máquina de Turing é composta de:
A máquina é interrompida quando atinge o estado final, quando tenta deixar a fita, vai para a esquerda da célula de memória 0, ou quando encontra uma situação para a qual ela não possui regra definida.
O cálculo funciona com os dados de entrada que queremos processar, como uma string que queremos reverter, são armazenados na memória antes de executar a máquina. Depois executamos a máquina e aguardamos até que ela termine, então pegamos o que está presente na memória como a saída da máquina, a string invertida. Essa é uma máquina de Turing que não possui uma I/O tradicional, como uma função printf, ela funciona inteiramente em dados na memória.
Programaremos uma máquina de Turing que leva um número binário em sua saída e adiciona 1 a ele, por simplicidade, supomos um número fixo de bits para que um transbordamento possa acontecer. Suponhamos os símbolos 0 e 1 como o alfabeto da fita. A unidade de controle terá as seguintes regras:
| stateFrom | inputSymbol | stateTo | outputSymbol | headShift | goRight | non-blank | goRight | inputSymbol | right goRight | blank | add1 | blank | left add1 | 0 | add0 | 1 | left | add1 | 1 | add1 | 0 | left | add0 | 0 | add0 | 0 | left | add0 | 1 | add0 | 1 | left | end
Nosso state de partida será goRright e o fim será o sstate final, embora não precisaremos, pois nossa máquina sempre parava deixando a fita. Os states são feitos para que primeiro faça a máquina passo à direita até encontrar o símbolo em branco, depois ele pisará uma etapa para a esquerda e mudará para o modo de adição. Adicionando trabalhos como estamos acostumados, com potencialmente carregando 1s para os pedidos mais altos.
Vamos tentar inserir o número binário 0101, 5 em decimal, na máquina isso significa que escreveremos o número na fita e executaremos a máquina como assim:
goRight
_V_ ___ ___ ___ ___ ___ ___ ___
| 0 | 1 | 0 | 1 | | | | ...
'---'---'---'---'---'---'---'---
goRight
___ _V_ ___ ___ ___ ___ ___ ___
| 0 | 1 | 0 | 1 | | | | ...
'---'---'---'---'---'---'---'---
goRight
___ ___ _V_ ___ ___ ___ ___ ___
| 0 | 1 | 0 | 1 | | | | ...
'---'---'---'---'---'---'---'---
goRight
___ ___ ___ _V_ ___ ___ ___ ___
| 0 | 1 | 0 | 1 | | | | ...
'---'---'---'---'---'---'---'---
goRight
___ ___ ___ ___ _V_ ___ ___ ___
| 0 | 1 | 0 | 1 | | | | ...
'---'---'---'---'---'---'---'---
add1
___ ___ ___ _V_ ___ ___ ___ ___
| 0 | 1 | 0 | 1 | | | | ...
'---'---'---'---'---'---'---'---
add1
___ ___ _V_ ___ ___ ___ ___ ___
| 0 | 1 | 0 | 0 | | | | ...
'---'---'---'---'---'---'---'---
add0
___ _V_ ___ ___ ___ ___ ___ ___
| 0 | 1 | 1 | 0 | | | | ...
'---'---'---'---'---'---'---'---
add0
_V_ ___ ___ ___ ___ ___ ___ ___
| 0 | 1 | 1 | 0 | | | | ...
'---'---'---'---'---'---'---'---
END
A máquina de Turing universal é um tipo extremamente importante de máquina de Turing, uma que é capaz de simular outra máquina de Turing, podemos vê-la como um intérprete de máquina de Turing de uma máquina de Turing. A máquina de Turing que deve ser simulada é codificada em uma string, que pode então ser vista como uma linguagem de programação, o formato da string pode variar, mas de alguma forma ela tem que codificar as regras da unidade de controle, e essa string, junto com uma entrada para a máquina simulada, é passada para a máquina universal que a executa.
Isso é importante porque agora podemos ver as próprias máquinas de Turing como programas e podemos usar máquinas de Turing para analisar outras máquinas de Turing, para nos tornarmos auto-hospedados. Isso abre um enorme mundo de possibilidades.
A máquina de Turing não determinística é uma modificação da máquina de Turing que remove a limitação do determinismo, permitindo ter regras conflitantes diferentes definidas para a mesma combinação de estado e entrada. Durante a execução, essa máquina pode escolher convenientemente qual dessas regras seguir ou, imaginando de forma diferente, podemos ver a máquina executando todos os cálculos possíveis em paralelo e, então, retroativamente, deixando no lugar apenas o caminho mais conveniente, o mais rápido ou o que terminou sem ficar preso em um loop infinito.
Uma máquina de Turing não determinística é computacionalmente equivalente a uma máquina de Turing determinística, embora uma máquina não determinística possa ser mais rápida, veja P vs NP.
Máquinas de Turing podem ser usadas para definir linguagens formais computáveis. Digamos que queremos definir a linguagem L, que pode ser uma linguagem de programação, podemos fazer isso programando uma máquina de Turing que recebe como entrada uma string e emite sim se essa string pertence à linguagem, ou não se não pertence. Isso é novamente útil para a teoria da decidibilidade e computabilidade.
#include <stdio.h>
#define CELLS 2048
#define BLANK 0xff
#define STATE_END 0xff
#define SHIFT_NONE 0
#define SHIFT_LEFT 1
#define SHIFT_RIGHT 2
unsigned int state;
unsigned int headPosition
unsigned char tape[CELLS];
unsigned char input[] =
{ 0, 1, 0, 1 };
unsigned char rules[] =
{
0, 0, 0, 0, SHIFT_RIGHT,
0, 1, 0, 1, SHIFT_RIGHT,
0, BLANK, 1, BLANK, SHIFT_LEFT,
1, 0, 2, 1, SHIFT_LEFT,
1, 1, 1, 0, SHIFT_LEFT,
2, 0, 2, 0, SHIFT_LEFT,
2, 1, 2, 1, SHIFT_LEFT
};
void init(void)
{
state = 0;
headPosition = 0;
for (unsigned int i = 0; i < CELLS; ++i)
tape[i] = i < sizeof(input) ? input[i] : BLANK;
}
void print(void)
{
printf("state %d, tape: ", state);
for (unsigned int i = 0; i < 32; ++i)
printf("%c%c", tape[i] != BLANK ? '0' + tape[i] : '.', i == headPosition ? '<' : ' ');
putchar('\n');
}
unsigned char step(void)
{
const unsigned char *rule = rules;
for (unsigned int i = 0; i < sizeof(rules) / 5; ++i)
{
if (rule[0] == state && rule[1] == tape[headPosition])
{
state = rule[2];
tape[headPosition] = rule[3];
if (rule[4] == SHIFT_LEFT)
{
if (headPosition == 0)
return 0;
else
headPosition--;
}
else if (rule[4] == SHIFT_RIGHT)
headPosition++;
return state != STATE_END;
}
rule += 5;
}
return 0;
}
int main(void)
{
init();
print();
while (step())
print();
puts("halted");
return 0;
}
Bom, depois de um certo ser (hermian) me implorar de joelhos para programar uma Turing Machine, eu aceitei, e fui fazer essa porra, foi muito bom escrever essa desgraça, o único problema real era vencer a minha preguiça a nível de escrever código (já que metade do tempo foi gasta pensando em soluções, e a metade da outra metade foi gasta procastinando, e a metade da metade da outra metade foi gasta dormindo, e outra metade da metade da outra metade foi gasta verdadeiramente programando.
Antes de começar a putaria computada, é importante considerar algumas coisas:
Bom, depois de fazer pesquisas ultra aprofundadas, em bibliotecas antigas com mais de 10⁴ anos de existência (Wikipedia + Artigo da UFSC + Artigo do Unixtopia), eu defini a Máquina de Turing como uma impressora linear (ou uma que esteja com algum defeito), capaz de escrever e apagar, o que significa que para simular uma Maquina de Turing, precisamso ao menos das seguintes instruções:
Entretando, fica claro que é muito difícil ir longe com essa porra, logo, precisaremos usar mais 2 outras instruções para indexar onde os processos de escrita serão feitos, sendo elas:
Entendido tais operações, podemos iniciar o planejamento de nosso software, o que significa responder a algumas perguntas simples
Alguns diriam para usar alguma chamada da stdio.h, tais como scanf, gets, fgets, e assim por diante, entretando, é importante lembrar que uma chamada dessas ocuparia tempo de execução, e como mr chamam de Lady C, e não de Lady Python, eu vou fazer o que puder para preservar um baixo tempo de execução, sendo assim, eu escolhi utilizar os argumentos de linha de comando (command line arguments) que a função main recebe ao ser executada. Tendo isso em mente, fica claro que teremos a obrigação de converter, de algum modo, a entrada recebida para um número decimal, o que nós dá a possibilidade de seguir por duas vertentes: Decimal X Binário
Nesta vertente de código, usaremos potências de 10, que podem ser representadas facilmente com a seguinte função (C):
for (int i = 0; i < n; i++)
{
r *= 10;
}
A lógica é simples, multiplicar um número por 10, N vezes
Nesta vertente de código, usaremos potências de 2, tais números podem ser representados de forma mais simples (se comparados a vertente anterior, as únicas coisas que precisamos verdadeiramente fazer são algumas operações de shift left (bitwise) N vezes, exemplo:
00000001 = 1 --> 2⁰ 00000010 = 2 --> 2¹ 00000100 = 4 --> 2² 00001000 = 8 --> 2³
Bom, para fazer tal escolha é necessário colocar algumas condições de teste para ambas as vertentes, como o enfoque é escrever um software rápido independente do consumo de memória, usaremos aquela que tem maior potencial para poupar clock cycles, sendo assim, vamos usar um ambiente hipotético de 1 byte (8 bits) de entrada, e 2 pseudo-algorítimos para calcular os respectivos valores decimais de tais entradas.
Entrada: 25obs.: Neste contexto, cycle não é o mesmo que clock cycle, mas sim uma medida de tempo próxima a "um step" do programa, assim como estaremos desconsiderando o tempo ocupado por cada uma das operações (por enquanto)
Para converter a string "25" para seu correspondente inteiro, serão necessários 2 cycles para percorrer todos os bytes importantes da string b[0] = '2' e b[1] = '5', após isso, 1 cycle será necessário para calcular a potência 10¹
Teremos então, algo próximo ao seguinte pseudo-código:
int a = 1, b = 0;
for (int i = 0; i < 2; i++)
{
for (int n = 0; n < i; n++)
{
a *= 10;
}
b += ("25"[1-i] - '0') * a;
}
Um total de 3 cycles
Já na conversão binária, usaremos de algumas "vantagens" de tal sistema para calcular seus números inteiros correspondentes, ou seja, ao invés de subtrair o byte analisado por '0'/48, usaremos apenas uma operação AND de tal byte com o número 1, e multiplicaremos o resultado dessa operação por 2^N, e somaremos tudo ao final. Como todos os resultados possíveis da operação AND se resumem a 1 e 0, tal multiplicação é desnecessária, assim como a soma, podemos substituir ambas por um SHL por tamnho_da_string - N. Em pseudo-código teremos:
for (int i = 0; i < 5; i++)
{
byte |= (1 & "11001"[i]) << (5 - i - 1)
}
Temos apenas um for relativo ao tamanho da string, tendo um total de 5 cycles, já que 25 = 0b00011001.
Entrada: 100A string analisada terá um total de 3 bytes: '1', '0', '0', logo, 3 cycles, com as exponenciações 10¹ e 10² a serem calculadas, consumindo 3 cycles
Um total de 6 cycles
A string analisada terá um total de 7 bytes '1' '1' '0' '0' '1' '0' '0', logo, 7 cycles
Um total de 7 cycles
Entrada: 900String: 3 bytes --> 3 cycles
Potências: 10¹, 10² --> 3 cycles
Total: 6 cycles
String: 9 bytes ('1' '1' '1' '1' '1' '0' '1' '0' '0') --> 9 cycles
Total: 9 cyclesBom, os resultados já eram esperados, afinal, se comparados aos números decimais, binários precisam de mais números para representar uma mesma quantidade de combinações, seguindo a função:
Log2 (10^N) = X
Onde N representa a quantidade de números decimais usados, e X a quantidade de números binários usados. Tendo em vista apenas tais informações, é muito difícil bater o martelo e definir qual a melhor versão, sendo assim, é a melhor coisa a se fazer é analisar ambos lado a lado.
A primeira dica que podemos usar para decidir qual delas é a melhor, seria, em tese, as operações usadas em ambos os casos, já que a vertente decimal faz uso de 2 multiplicações (que podem ser reduzidas a apenas uma), e duas somas (uma adição, e uma subtração). Enquanto a contraparte binária se usa de um shift left, um and e duas somas (duas subtrações), a princípio, as operações realizadas na conversão binária são muito mais simples se comparadas a versão decimal (o que é uma verdade), o problema está na quantidade de vezes que a versão binária realiza para computar números iguais. Mesmo aplicando tudo o que fora dito, ainda é importante analisar uma característca, os acessos a memória de ambas as versões, já que ambas as versões irão acessar memória fora do escopo do processador (estamos usando um processador de 32 bits, e ela acessa um char, de 8 bits), tais acessos a memória são lentos, ou seja, se considerarmos o volume dessas acessos (N), fica evidente que quanto maior o número binário, muito mais processamento será perdido. Em resumo, a única vantagem do uso binário se concentra em números muito pequenos.
Bom, seguindo a mesma lógica da conversão decimal X binária, é mais apropriado escolher uma padronização decimal para o código que será recebido por nossa Máquina. Partindo disso, usaremos números de 0 a 3 para padronizar nossas funções, seguindo a seguinte tabela:
0 - Write 1 - Erase 2 - Right 3 - Left
Logo, o código: "330" será equivalente a execução das instruções "Left, Left, Write"
Bom, com o I/O do programa decidido, podemos finalmente nós aprofundar no desenvolvimento lógico da maquina de turing, para isso, vamos entender como a mesma deve funcionar com as 4 instruções anteriormente definidas.
Suponha a seguinte composição de bits:
----------------- | 0 | 0 | 0 | 0 | -----------------
Nosso primeiro passo será definir onde estão os bits mais e menos significativos, e por uma questão de padronização, os mesmos serão definidos da seguinte forma:
----------------- | 0 | 0 | 0 | 0 | ----------------- ↑ ↑ H L
Logo, caso queiramos editar o 3° bit da sequência, será necessário mover o "bit focal" para esquerda 2 vezes, e então, escrever 1 ao bit, em passos lógicos, teremos a seguinte representação:
↓
-----------------
| 0 | 0 | 0 | 0 |
-----------------
↓
-----------------
| 0 | 0 | 0 | 0 |
-----------------
↓
-----------------
| 0 | 0 | 0 | 0 |
-----------------
↓
-----------------
| 0 | 1 | 0 | 0 |
-----------------
Em termos práticos, teriamos um algorítimo próximo a isso: Left, Left, Write
Sintetizando todas as informações dadas, temos então o seguinte esqueleto para um programa
Com isso em mãos, podemos finalmente escrever nosso programa. Logo, dividiremos nosso programa em partes:
Primeiro precisamos calcular o tamanho das strings de entrada, e para isso, vamos usar um for loop até atingir o fim de ambas as strings (já que não podemos usar `sizeof()` com ponteiros)
#include <stdio.h>
int main(int argc, char** argv)
{
int i = 0, n = 0;
char sizes[2];
for (; i < 2; i++)
{
for (n = 0; argv[i+1][n] != 0; n++
{
sizes[i]++;
}
}
}
Agora devemos escrever as funções, que serão feitas a partir do uso de um pouco de lógica boolena
void write()
{
b |= 1 << index;
}
void erase()
{
b &= ~(1 << index);
}
void right()
{
index--;
}
void left()
{
index++;
}
Com este script em mãos, só precisamos converter os valores entrada para inteiros, e executar os comandos do segundo input
#include <stdio.h>
int main(int argc, char** argv)
{
int i = 0, n = 0, a = 1, b = 0, index = 0;
char sizes[2];
for (; i < 2; i++)
{
for (n = 0; argv[i+1][n] != 0; n++
{
sizes[i]++;
}
}
for (int i = 0; i < sizes[1]; i++)
{
for (int n = 0; n < i; n++)
{
a *= 10;
}
b += (argv[1][sizes[1]-i] - '0') * a;
}
for (int i = 0; i < sizes[2]; i++)
{
switch (argv[2][i])
{
case 0:
write();
break;
case 1:
erase();
break;
case 2:
right();
break;
case 3:
left();
break;
}
}
printf("%d", b);
}
Parabéns, sua Máquina está terminada :)
Tá, agora vamos conversar de forma seria, se seu código se parece minimamente com isso, vá urgentemente ao médico, você tem problemas mentais sérios, ou seu cérebro está derretido, já que se algo neste nível aconteceu, puta merda, você está MUITO FUDIDO, seu imbecil do caralho.
Vamos começar com o fato de que tal código usa uma caralhada de for loops desnecessários, não tem um gerenciamento eficiente de memória, e ainda consegue falhar na própria lógica, já que o mesmo não funciona direito, como você pode concordar com algo assim? K
Bom, com um código desses, eu diria que é impossível haver uma restauração completa de seu código, ele será permane..... espere um segundo, está ouvindo essa música? Acho que eu conheço ela de algum lugar...
Luz no fim do tunel.mp3 ♫
Beleza, acabou a palhaçada, vamos otimizar essa merda. Em primeiro lugar, vamos reestruturar completamente essa porcaria de código, as mudanças vão começar na padronização do I/O, colocaremos o valor inicial como primeira entrada string, e o código a ser executado como segunda entrada string, o objetivo é simples, conseguir a diferença entre os endereços, e calcular a sequência de nossas iterações. Também é importante lembrar que strings terminam com caracteres nulos, o que torna necessário diminuir um do tamanho calculado, e claro, usaremos essa característica para integrar nosso for loop da "fita de código", que, inclusive, precisam ser retrabalhados URGENTEMENTE, PUTA QUE PARIU SEU IDIOTA DO CARALHO, COMO VOCÊ NÃO PERCEBEU A DESGRAÇA DA BURRICE QUE ERA COLOCAR TUDO EM UM SWITCH CASE SEU ANIMAL DO CARALHO, VAI APRENDER C SEU FILHO DE UMA PUTA QUE O ANALMENTE PARIU. O que eu quero dizer é, se um pouco mais de atenção fosse dada a situação, ficaria evidente que a um array de ponteiros com uma subtração de 48/'0' seria muito mais eficiente que A PORRA DE UM STATEMENT INTEIRO SEU FILHO DA PUTA, lembrando que usar um array de ponteiros inclui padronizar as variáveis envolvidas, o que deixa evidente como o uso parametros seria outra forma de processamento desperdiçado, logo, variáveis globais serão necessárias. E claro, aos idiotas que não perceberam a falha explícita no código de calculo de potência, eu digo, VOCÊ É BURRO, peço de forma caridosa que execute aquele algoritimo por si mesmo, com um número que tenha ao menos 3 casas decimais, e você vai perceber a cagada que você estava concordando.
Com as mudanças aplicadas temos o seguinte código:
#include <stdio.h>
int byte = 0, index = 0;
void write()
{
byte |= 1 << index;
}
void erase()
{
byte &= ~(1 << index);
}
void right()
{
index--;
}
void left()
{
index++;
}
int main(int argc, char** argv)
{
void (*inst[4])() = {write, erase, right, left};
for (argc = 0; argc < argv[2]-argv[1]-1; argc++)
{
byte *= 10;
byte += argv[1][argc] - '0';
}
for (argc = 0; argv[2][argc] != 0; argc++)
{
inst[argv[2][argc]-'0']();
}
printf("%d\n", byte);
}
Alguns idiotas poderiam pensar "Agora assim, finalmente temos um bom código", e eu te respondo, PUTA QUE PARIU SEU ANIMAL DO CARALHO, PORRAAAAAAAAAA. Vamos a uma aula básica de C Calling Convention. Ao chamar uma função C, você faz a execução de duas principais instruções: `call` e `push`, mas espere, como eu posso fazer uso de duas instruções em apenas uma operação de chamada simples? Bom, é agora que eu te respondo, vamos desmontar um programa C simples, esste programa aqui:
int a = 1;
void function()
{
a <<= 1;
}
void _start()
{
function();
}
int a = 1;
void function()
{
a <<= 1;
}
void _start()
{
function();
}
Ao ser desmontado, teremos como resultado o seguinte código:
804810c: 55 push %ebp 804810d: 89 e5 mov %esp,%ebp 804810f: 81 ec 00 00 00 00 sub $0x0,%esp 8048115: 8b 05 38 91 04 08 mov 0x8049138,%eax 804811b: c1 e0 01 shl $0x1,%eax 804811e: 89 05 38 91 04 08 mov %eax,0x8049138 8048124: c9 leave 8048125: c3 ret 8048126: 55 push %ebp 8048127: 89 e5 mov %esp,%ebp 8048129: 81 ec 00 00 00 00 sub $0x0,%esp 804812f: e8 d8 ff ff ff call 0x804810c 8048134: c9 leave 8048135: c3 ret
Seguindo um pouco de lógica, podemos ver que o código possui duas `ret`s, as instruções de retorno, e seguindo a estrutura do código C, fica claro que o primeiro setor de código (`804810c --> 8048125`) se trata da primeira função (`function`) e o segundo setor de código (`8048126 --> 8048135`) se trata da segunda função (`_start`). Dito isso, perceba que ambos os setores executam duas instruções antes de começar a executar código: `push %ebp` e `mov %esp, %ebp`, estas intruções fazem parte da C Calling Convention, assim como a instrução `call 0x804810c`, que além de realizar um `jmp` até o endereço indicado, também salva o atual `%eip` (instruction pointer) que será usado no retorno da função para voltar a `_start`
Dito isso, vamos entender a lógica de nosso programa. A primeira coisa a considerar são as calls feitas durante sua execução, que se resumem apenas ao array de function pointers do segundo for loop:
for (argc = 0; argv[2][argc] != 0; argc++)
{
inst[argv[2][argc]-'0']();
}
Isso significa que temos um endereço de retorno constante, já que as calls são feitas apenas dentro deste for loop, nesta linha de raciocínio, seguir usando a instrução `call` seria perder processamento, já que a mesma moveria o valor do registrador `%eip` à stack toda vez que fosse chamada, logo, podemos substituir a instrução `call` por um simples `jmp`, e adicionar um `jmp` de retorno no fim de todas as funções usadas (já que o endereço de retorno é constante). Outro detalhe que devemos prestar atenção é o início de nossas funções, já que as mesmas realizam `push`s e `mov`s, o que é desnecessário, já que elas não se utilizam de nenhum parâmetro, assim como não declaram nenhuma variável dentro de seu escopo, o que torna desnecessário realizar tais instruções. Por fim, as últimas mudanças verdadeiramente necessárias são aquelas que dizem respeito a redução máxima do número de variáveis, o que significa eliminar as variáveis `byte` e `index`, que serão substituidas pelos registradores `%ebx` e `%edx` respectivamente, e claro, para calcular nossas iterações em for's, usaremos uma variável respectiva ao registrador `%esi`, e para que obtenhamos o desempenho máximo com nossas funções, devemos escrevê-las em assembly, evitando que o compilador realize as instruções `push` e `mov` ao início das funções. Aplicando todas as mudanças ao código, teremos por fim, o seguinte código:
#include <stdio.h>
void write();
__asm__(
"write:"
"movl %edx, %ecx;"
"movl $1, %eax;"
"shll %cl, %eax;"
"orl %eax, %ebx;"
"jmp retn;"
);
void erase();
__asm__(
"erase:"
"movl %edx, %ecx;"
"movl $1, %eax;"
"shll %cl, %eax;"
"notl %eax;"
"andl %eax, %ebx;"
"jmp retn;"
);
void right();
__asm__(
"right:;"
"decl %edx;"
"jmp retn;"
);
void left();
__asm__(
"left:;"
"incl %edx;"
"jmp retn;"
);
int main(int, char** argv)
{
register int bx asm("%ebx") = 0;
register int si asm("%esi") = 0;
__asm__ ("movl $0, %edx");
void (*inst[4])() = {write, erase, right, left};
for (; si < argv[2]-argv[1]-1; si++)
{
bx *= 10;
bx += argv[1][si] - '0';
}
for (si = 0; argv[2][si] != 0; si++)
{
__asm__ volatile(
"jmp *%0;"
"retn:;"
:: "m" (inst[argv[2][si]-'0'])
);
}
__asm__ volatile("movl %ebx, %esi");
printf("%d\n");
}
A primeira coisa a se notar, é realização das funções, as quais são declaradas como protótipos, mas são escritas em assembly, perceba que as mesmas não possuem nenhum tipo de instrução relacionada a memória primária, RAM, assim como todas as funções possuem um jmp constante, essa parte do código diz respeito as otimizações quanto as chamadas de funções, onde, se comparadas as funções anteriormente desmontadas, não possuem nenhuma interação com a memória.
Todas as variáveis são associadas a um registrador específico, para que não haja conflitos no código, é necessário bloquear o uso destes registradores durante a compilação, com a flag -ffixed-reg, e claro, há também um array de ponteiros de funções, que aponta para todas as funções usadas no programa (sendo estas as funções escritas em assembly.
Estes seguem o mesmo padrão do código anterior, a diferença é que não fazem a porra de um código enorme que resulta em algo infuncional. É importante destacar a presença de uma label de retorno no segundo for loop, a label retn, que é usada em nossas funções para retornar à `main` function.
O fim do programa move o valor do registrador %ebx para o registrador %esi, e o motivo é simples, este é o registrador usado como um dos parâmetros da função printf, e isso é feito para evitar mov's desnecessários para o registrador %eax, que seriam devidamente feitos se tratassemos o parametro %ebx com sua variável respectiva bx.
Impulsionado por nada. Todo conteúdo é disponível sob CC0 1.0 domínio público. Envie comentários e correções para Mr. Unix em victor_hermian@disroot.org.