Conjunto de Problemas

1. Mapa de Karnaugh

O mapa de Karnaugh é uma técnica visual para montar uma função lógica que gere um bit de saída dado um conjunto de diversos bits de entrada. A partir de cada possível entrada e da saída correspondente desejada para cada uma dessas entradas, o mapa de Karnaugh permite encontrar um conjunto de operações lógicas bastante otimizado para obter o resultado desejado.

Estude o mapa de Karnaugh e implemente um código em Assembly do 8051 que obedeça à tabela-verdade do exemplo da página da Wikipedia sobre o mapa de Karnaugh:

ABCDSaída
00000
00010
00100
00110
01000
01010
01101
01110
10001
10011
10101
10111
11001
11011
11101
11110

Seu código deve receber como entradas os registradores R0, R1, R2 e R3, e retornar a saída em A. Utilize as instruções lógicas do 8051 normalmente, de forma que as operações sejam feitas bit-a-bit, ou seja, com o primeiro bit da saída dado pela operação descrita pela tabela acima sobre o primeiro bit de cada um dos registradores de entrada, idem para todos os outros bits.

Exemplo

Entradas:

R0 = #00111111b
R1 = #11000011b
R2 = #11001100b
R3 = #01010101b

Saída:

A  = #10111111b

2. Operações sobre bits isolados

Implemente a mesma função lógica do exercício anterior, mas desta vez opere sobre um conjunto de apenas 4 bits de entrada, gerando um único bit de saída.

Sua entrada será dada pelos 4 bits menos significativos do registrador R0, da direita para a esquerda. Ou seja, a entrada 1,1,1,0 é dada por R0=#0111b (acredite, isso é para facilitar o seu código). Dê a saída no flag de carry (C).

Dica: Copie a entrada do registrador R0 para algum byte de memória que seja endereçável bit-a-bit no microprocessador 8051, por exemplo o byte 20h. Utilize instruções do tipo ANL C, bit, ANL C, /bit, ORL C, bit, ORL C, /bit, CPL C, etc. para implementar a lógica.

Exemplo

Entrada:

R0 = #0111b

Saída:

C = 1

3. CRC32

Implemente o algoritmo CRC32 em Assembly do 8051. O CRC32 é um algoritmo que calcula um número de 32 bits a partir de uma entrada de qualquer número de bytes. O número calculado com CRC32 é incluído ao final de frames de rede Ethernet, dentro de arquivos zip, e em várias outras tecnologias do dia-a-dia, como um meio de conferir se os dados transmitidos ou contidos em um arquivo estão corrompidos. O CRC32 foi projetado de forma que dados acidentalmente corrompidos tivessem uma grande chance de apresentar um CRC32 diferente dos dados originais.

Esse problema deve ser resolvido em dois passos. Primeiro, gere uma tabela auxiliar para o cálculo do CRC32. Grave essa tabela na memória externa, a partir da posição 7000h. A tabela possui 256 entradas de 32 bits cada, ou seja, a tabela vai ocupar ao todo 1024 bytes.

Em C, é utilizado o código abaixo para gerar essa tabela. Adapte esse algoritmo para o Assembly do 8051.

unsigned int tabela[256];
unsigned int poly = 0xedb88320;
for(int n = 0; n < 256; n++) {
    unsigned int c = n;
    for(int k = 0; k < 8; k++) {
        if((c & 1) == 1) {
            c = poly ^ (c >> 1);
        }
        else {
            c = c >> 1;
        }
    }
    tabela[n] = c;
}

Verifique se os primeiros números da tabela conferem com os gerados pelo seu código: 00000000, 77073096, ee0e612c, 990951ba, 076dc419, ...

Após calcular essa tabela auxiliar, faça um código que calcule o CRC32 de um número qualquer de bytes contidos a partir da posição 7400h da memória externa. A quantidade de bytes de entrada será dada pelo registrador R0. Retorne o valor do CRC32 em R1,R2,R3,R4 (ordenados do byte mais significativo ao menos significativo).

Em C, é utilizado o código abaixo para calcular o CRC32. Adapte esse código para o Assembly do 8051.

unsigned int crc = 0xffffffff;
for(int i = 0; i < tamanho_entrada; i++) {
    crc = tabela[(crc ^ entrada[i]) & 0xff] ^ (crc >> 8);
}
crc = ~crc;

Exemplo

Entradas:

R0 = 4
Bytes (em hexa) a partir de 7400h: 74 65 73 74.
Obs.: esses bytes correspondem ao código ASCII dos caracteres da palavra "test".

Saída

R1 = D8
R2 = 7F
R3 = 7E
R4 = 0C

4. Desafio: CRC32 inverso

Existe uma forma de, dado o CRC32 de um conjunto de dados, encontrar um conjunto de 4 bytes que pode ser adicionado ao final desse conjunto de dados para que ele passe a ter qualquer valor de CRC32 desejado.

Você consegue encontrar uma forma de fazer isso? Tentar todos os conjuntos de 4 bytes possíveis não é uma solução válida. Implemente sua solução no Assembly do 8051.