Segredos em x86-64 Assembly no Exercism

Introdução

Manipulação de bits

Cada bit de um número inteiro pode ser usado para armazenar um valor binário. Como muitas situações envolvem informação binária, como verdadeiro ou falso, incluído ou excluído, ligado ou desligado, a representação binária de um número inteiro de N bits proporciona uma forma compacta de codificar o estado binário de N itens. Isto torna a capacidade de manipular bits e bytes essencial em assembly. O conjunto de instruções x86-64 oferece uma grande variedade de instruções de manipulação bit a bit.

Manipulação de bits individuais

Estas instruções trabalham com bits individuais de um operando.

Todas recebem dois operandos; o segundo indica o índice do bit sobre o qual se opera no primeiro operando. Todas elas copiam o bit selecionado para o carry flag (CF).

Nome	Descrição
`bt`	copia o bit para `CF` sem modificar nenhum operando
`bts`	copia o bit para `CF` e coloca-o a 1 no operando de destino
`btr`	copia o bit para `CF` e coloca-o a 0 no operando de destino
`btc`	copia o bit para `CF` e complementa-o (inverte-o) no operando de destino

Operações bit a bit

As operações bit a bit são efetuadas sobre todos os bits de um operando.

Todas têm uma instrução com o mesmo nome da operação bit a bit efetuada:

Nome	Descrição
`and`	1 se ambos os bits forem 1
`or`	1 se pelo menos um dos bits for 1
`xor`	1 se os bits forem diferentes
`not`	1 se o bit era 0; 0 se o bit era 1

A maioria delas recebe dois operandos, efetua uma operação bit a bit sobre ambos e guarda o resultado no operando de destino. A exceção é o not, que recebe apenas um operando de destino.

Máscaras

Quando interpretamos um e zero como inclusão e exclusão, respetivamente, um número inteiro é chamado de máscara de bits (ou simplesmente máscara).

Uma máscara de bits "mascara" itens porque um zero no bit de índice i exclui o item de índice i, enquanto um um inclui-o. Também usamos habitualmente uma máscara de bits para incluir certos bits de um número inteiro e excluir outros.

Por exemplo, seja A um número inteiro cuja representação binária é:

índice	7	6	5	4	3	2	1	0
bits	1	0	0	1	0	1	0	1

E seja M um número inteiro cuja representação binária é:

índice	7	6	5	4	3	2	1	0
bits	0	0	0	0	1	1	0	1

Ambos são números inteiros de 8 bits. Neste caso, podemos dizer que M seleciona os bits 0, 2 e 3 de A e exclui os restantes.

As instruções bit a bit discutidas anteriormente são úteis para manipular números inteiros com máscaras. Por exemplo:

Para colocar a zero os bits de A que não são selecionados por M, faz o AND bit a bit: A AND M.
Para colocar a um os bits de A selecionados por M, faz o OR bit a bit: A OR M.

Instrução TEST

A instrução test faz um AND bit a bit entre os dois operandos e define as flags de acordo com o resultado.

Se A for o primeiro operando e B o segundo:

flag	definida quando
`CF`	sempre colocada a zero
`ZF`	A AND B == 0
`SF`	o bit de sinal de A AND B está a 1
`OF`	sempre colocada a zero

Esta instrução recebe dois operandos e atualiza as flags, mas não modifica os seus operandos.

Operações de deslocamento

Estas instruções deslocam os bits do operando de destino um número de posições indicado pelo segundo operando. O segundo operando tem de ser um número constante (um immediate) ou o registo cl (os 8 bits menos significativos de rcx).

Nome	Descrição
`shl`/`sal`	Desloca os bits para a esquerda
`shr`/`sar`	Desloca os bits para a direita

Repara que a contagem no segundo operando é mascarada para 5 bits, ou 6 bits no caso de um operando de destino de 64 bits. Qualquer bit para lá disso é efetivamente ignorado. Isto significa que o deslocamento máximo é 31, ou 63 no caso de um operando de 64 bits.

Shl / Sal

Tanto shl como sal efetuam exatamente a mesma operação; um é um alias do outro.

Sempre que se faz um deslocamento para a esquerda, os bits que ficam mais perto do fim da sequência do que o comprimento do deslocamento são primeiro movidos para CF e depois descartados. Por outro lado, é acrescentado ao início um número de novos bits a zero igual ao comprimento do deslocamento.

Como cada bit de um número inteiro representa uma potência de 2, um deslocamento para a esquerda de n posições tem o efeito de multiplicar o número inteiro por 2ⁿ.

Shr / Sar

Há duas instruções para deslocar bits para a direita: shr e sar.

Sempre que se usa uma destas duas instruções, os bits que ficam mais perto do início da sequência do que o comprimento do deslocamento são primeiro movidos para CF e depois descartados. Por outro lado, é acrescentado ao fim um número de novos bits igual ao comprimento do deslocamento.

A diferença entre elas é que shr move bits 0 para a extremidade esquerda, enquanto sar move 1 se o mais significativo estava a 1 e 0 caso contrário. Isto significa que sar preserva o sinal no deslocamento de um número inteiro com sinal.

Como cada bit de um número inteiro representa uma potência de 2, um deslocamento para a direita de n posições com shr tem o efeito de efetuar uma divisão sem sinal por 2ⁿ.

Do mesmo modo, um deslocamento para a direita de n posições com sar tem o efeito de efetuar uma divisão com sinal por 2ⁿ.

Operações de rotação

A diferença entre uma rotação e um deslocamento é que uma rotação não descarta nem acrescenta bits. Os bits que seriam descartados por um deslocamento são, em vez disso, movidos para a extremidade oposta. Por isso, todos os bits permanecem; mudam todos de lugar.

Nome	Descrição
`rol`	Roda os bits para a esquerda
`ror`	Roda os bits para a direita

Repara que a contagem no segundo operando é mascarada para 5 bits, ou 6 bits no caso de um operando de destino de 64 bits. Qualquer bit para lá disso é efetivamente ignorado. Isto significa que a rotação máxima é 31, ou 63 no caso de um operando de 64 bits.

Outras instruções de manipulação de bits

Há outras instruções úteis de manipulação de bits:

Nome	Descrição
`popcnt`	Conta o número de bits com valor 1
`bsr`	Obtém o índice do bit mais significativo com valor 1. Se nenhum bit estiver a 1, o resultado é indefinido
`bsf`	Obtém o índice do bit menos significativo com valor 1. Se nenhum bit estiver a 1, o resultado é indefinido

Estas instruções funcionam todas com dois operandos de 16 bits, 32 bits ou 64 bits. Não podem ser usadas com operandos de 8 bits.

Instruções

O teu amigo acabou de te enviar uma mensagem com um segredo importante. Para não tornar fácil a leitura por parte de outras pessoas, a mensagem foi encriptada através de uma série de manipulações de bits. Vais ter de escrever os métodos que ajudam a desencriptar a mensagem.

Note

Estas são as instruções de bit único mencionadas neste conceito:

Name	Description
bt	copia o bit para `CF` sem modificar qualquer operando
bts	copia o bit para `CF` e define-o no operando de destino
btr	copia o bit para `CF` e limpa-o no operando de destino
btc	copia o bit para `CF` e complementa-o (inverte-o) no operando de destino

Estas são as instruções bit a bit mencionadas neste conceito:

Name	Description
and	1 se ambos os bits forem 1
or	1 se pelo menos um dos bits for 1
xor	1 se os bits forem diferentes
not	1 se o bit era 0; 0 se o bit era 1

Estas são as instruções de deslocamento mencionadas neste conceito:

Name	Description
shl/sal	Desloca os bits para a esquerda
shr/sar	Desloca os bits para a direita

Estas são as instruções de rotação mencionadas neste conceito:

Name	Description
rol	Roda os bits para a esquerda
ror	Roda os bits para a direita

Estas são as instruções diversas mencionadas neste conceito:

Name	Description
popcnt	Conta o número de bits definidos
bsr	Obtém o índice do bit definido mais significativo. Se não houver nenhum bit definido, o resultado é indefinido
bsf	Obtém o índice do bit definido menos significativo. Se não houver nenhum bit definido, o resultado é indefinido

1. Extrair a máscara

A mensagem está codificada num inteiro de 16 bits. No entanto, dos 16 bits, os 8 mais significativos não fazem parte da mensagem em si, mas sim de uma máscara que é preciso usar na desencriptação.

Implementa a função extract_higher_bits, que recebe um inteiro de 16 bits e devolve os 8 bits mais significativos.

extract_higher_bits(0b1010010011000101)
// => 0b10100100

2. Extrair a mensagem

Não basta conseguires extrair a máscara; também tens de isolar a mensagem.

Implementa a função extract_lower_bits, que recebe um inteiro de 16 bits e devolve os 8 bits menos significativos.

extract_lower_bits(0b1010010011000101);
// => 0b11000101

3. Extrair os bits redundantes

Há bits que estão definidos tanto na mensagem como na máscara. Esta informação é muito importante e será usada mais à frente.

Implementa a função extract_redundant_bits, que recebe um inteiro de 16 bits que codifica tanto a mensagem como uma máscara, e devolve um inteiro de 8 bits com apenas os bits redundantes definidos. Um bit do número devolvido deve ser definido como 1 quando também for 1 tanto na mensagem como na máscara. Todos os outros bits devem ser limpos.

extract_redundant_bits(0b1010010011000101);
// => 0b10000100

4. Definir todos os bits da mensagem

A seguir, há alguns bits que têm de ser definidos como 1 na mensagem, de acordo com a máscara.

Implementa a função set_message_bits, que recebe um inteiro de 16 bits que codifica tanto a mensagem como uma máscara, e devolve o resultado de definir como 1 os bits da mensagem. Um bit da mensagem deve ser definido como 1 quando o bit correspondente na máscara for 1. Todos os outros bits devem ficar inalterados, ou seja, continuam definidos se já estavam definidos, e limpos se já estavam limpos.

set_message_bits(0b1010010011000101);
// => 0b11100101

5. Rodar a chave privada

Há uma peça do puzzle que não está explícita na mensagem: o número de 16 bits 0b1011001100111100. Este número é a tua chave privada partilhada e deves usá-lo para ajudar a desencriptar a mensagem.

Para isso, primeiro tens de rodar os bits da tua chave privada para a esquerda um certo número de posições. O número de posições é igual ao número de bits redundantes definidos tanto na mensagem como na máscara.

Implementa a função rotate_private_key, que recebe um inteiro de 16 bits que codifica tanto a mensagem como uma máscara, e devolve o resultado de rodar a tua chave privada. Esse resultado é um inteiro de 16 bits.

rotate_private_key(0b1010010011000101);
// => 0b1100110011110010

Note

O NASM (The Netwide Assembler, o assembler usado neste percurso) suporta constantes em formato binário com o prefixo 0b. Também suporta a utilização de um underscore (_) como separador numa constante, para facilitar a leitura:

PRIVATE_KEY equ 0b1011_0011_0011_1100

6. Formatar a chave privada

Para poder ser usada na desencriptação, a tua chave privada tem de ser formatada de modo a isolar os bits relevantes.

Para formatar completamente uma chave privada, tens de:

Rodá-la.
Isolar a parte correspondente aos 8 bits menos significativos da chave privada rodada, que é o valor base.
Isolar a parte correspondente aos 8 bits mais significativos da chave privada rodada, que é uma máscara a aplicar ao valor base.
Inverter os bits do valor base que também estão definidos na máscara.
Inverter todos os bits do resultado.

Um bit invertido é 1 se era 0 e 0 se era 1.

Implementa a função format_private_key, que recebe um inteiro de 16 bits que codifica tanto a mensagem como uma máscara, e devolve uma chave privada de 8 bits totalmente formatada.

format_private_key(0b1010010011000101);
// => 0b11000001

7. Terminar a desencriptação

Depois de teres a mensagem com todos os bits relevantes definidos e a chave privada formatada, está na altura de as juntar para obter a mensagem resultante.

A mensagem resultante é um inteiro de 16 bits, do qual:

Os 8 bits mais significativos são preenchidos com a chave privada formatada.
Os 8 bits menos significativos são preenchidos com a mensagem, depois de definidos todos os bits relevantes.

Implementa a função decrypt_message, que recebe um inteiro de 16 bits que codifica tanto a mensagem como uma máscara, e devolve um inteiro de 16 bits com a mensagem totalmente desencriptada.

Esta função deve usar a chave privada formatada que geras com format_private_key e também a mensagem com todos os bits relevantes definidos com set_message_bits.

decrypt_message(0b1010010011000101);
// => 0b1100000111100101

Editar via GitHub

Percursos de linguagens

Aprende a programar com o Jiki

A tua jornada

Os teus favoritosNovo

Vantagens do Exercism

Vídeos da comunidade

Série de introduções breves

Entrevistas e histórias

Discord

Fórum

Primeiros passos

Mentoria

Documentação

Contribuidores

TradutoresNovo

Doar

Sobre o Exercism

O nosso impacto

Sincronizador do GitHubNovo

Insiders