Introdução
Manipulação de bits
Cada bit de um inteiro pode ser usado para armazenar um valor binário.
Como muitas situações envolvem informação binária, como verdadeiro ou falso, inclusão ou exclusão, ligado ou desligado, a representação binária de um inteiro de N bits oferece uma forma compacta de codificar o estado binário de N itens.
Isso 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 de bits.
Manipulação de bits individuais
Essas instruções trabalham com bits individuais de um operando.
Todas elas recebem dois operandos, e o segundo indica o índice do bit que será manipulado no primeiro operando.
Todas copiam o bit selecionado para a flag de carry (CF).
| Nome |
Descrição |
bt |
copia o bit para CF sem modificar nenhum operando |
bts |
copia o bit para CF e o define no operando de destino |
btr |
copia o bit para CF e o limpa no operando de destino |
btc |
copia o bit para CF e o complementa (inverte) no operando de destino |
Operações bit a bit
As operações bit a bit são realizadas em todos os bits de um operando.
Todas têm uma instrução com o mesmo nome da operação bit a bit realizada:
| Nome |
Descrição |
and |
1 se ambos os bits forem 1 |
or |
1 se ao 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, realiza uma operação bit a bit nos dois e armazena o resultado no operando de destino.
A exceção é not, que recebe apenas um operando de destino.
Máscaras
Quando interpretamos um e zero como inclusão e exclusão, respectivamente, o inteiro é chamado de máscara de bits (ou simplesmente máscara).
Uma máscara de bits "mascara" itens porque um zero no i-ésimo bit exclui o i-ésimo item, enquanto um 1 o inclui.
Também costumamos usar uma máscara de bits para incluir certos bits de um inteiro e excluir outros.
Por exemplo, seja A um 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 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 inteiros de 8 bits.
Neste caso, podemos dizer que M seleciona os bits 0, 2 e 3 de A, e exclui o restante.
As instruções bit a bit discutidas anteriormente são úteis para manipular inteiros com máscaras.
Por exemplo:
- Para limpar os bits de
A que não são selecionados por M, faça o AND bit a bit: A AND M.
- Para definir os bits de
A selecionados por M, faça 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 é o primeiro operando e B, o segundo:
| flag |
definida quando |
CF |
sempre limpa |
ZF |
A AND B == 0 |
SF |
o bit de sinal de A AND B está definido |
OF |
sempre limpa |
Essa instrução recebe dois operandos e atualiza as flags, mas não modifica seus operandos.
Operações de deslocamento
Essas instruções movem os bits do operando de destino em um número de posições especificado pelo segundo operando.
O segundo operando deve ser um número constante (um immediate) ou o registrador cl (os 8 bits mais baixos de rcx).
| Nome |
Descrição |
shl/sal
|
Desloca os bits para a esquerda |
shr/sar
|
Desloca os bits para a direita |
Observe que a contagem no segundo operando é mascarada para 5 bits, ou 6 bits com um operando de destino de 64 bits.
Qualquer bit além disso é efetivamente ignorado.
Isso significa que o deslocamento máximo é 31, ou 63 com um operando de 64 bits.
Shl / Sal
Tanto shl quanto sal realizam exatamente a mesma operação, uma é um alias da outra.
Sempre que é feito um deslocamento para a esquerda, os bits mais próximos do fim da sequência do que o comprimento do deslocamento são primeiro movidos para CF e depois descartados.
Por outro lado, um número de novos bits zerados igual ao comprimento do deslocamento é adicionado ao início.
Como cada bit de um inteiro representa uma potência de 2, um deslocamento de n posições para a esquerda tem o efeito de multiplicar o inteiro por 2ⁿ.
Shr / Sar
Há duas instruções para mover bits para a direita: shr e sar.
Sempre que qualquer uma das duas instruções é usada, os bits mais próximos do início da sequência do que o comprimento do deslocamento são primeiro movidos para CF e depois descartados.
Por outro lado, um número de novos bits igual ao comprimento do deslocamento é adicionado ao fim.
A diferença entre elas é que shr move bits 0 para a extremidade esquerda, enquanto sar move 1 se o bit mais significativo estava definido e 0 caso contrário.
Isso significa que sar preserva o sinal no deslocamento de um inteiro com sinal.
Como cada bit de um inteiro representa uma potência de 2, um deslocamento de n posições para a direita usando shr tem o efeito de fazer uma divisão sem sinal por 2ⁿ.
Da mesma forma, um deslocamento de n posições para a direita usando sar tem o efeito de fazer uma divisão com sinal por 2ⁿ.
Operações de rotação
Essas instruções movem os bits do operando de destino em um número de posições especificado pelo segundo operando.
O segundo operando deve ser um número constante (um immediate) ou o registrador cl (os 8 bits mais baixos de rcx).
A diferença entre uma rotação e um deslocamento é que uma rotação não descarta nem adiciona bits.
Os bits que seriam descartados por um deslocamento são movidos para a extremidade oposta.
Assim, todos os bits permanecem, todos eles mudam de lugar.
| Nome |
Descrição |
rol |
Rotaciona os bits para a esquerda |
ror |
Rotaciona os bits para a direita |
Observe que a contagem no segundo operando é mascarada para 5 bits, ou 6 bits com um operando de destino de 64 bits.
Qualquer bit além disso é efetivamente ignorado.
Isso significa que a rotação máxima é 31, ou 63 com um operando de 64 bits.
Outras instruções de manipulação de bits
Existem outras instruções úteis de manipulação de bits:
| Nome |
Descrição |
popcnt |
Conta o número de bits definidos |
bsr |
Obtém o índice do bit definido mais significativo. Se nenhum bit estiver definido, o resultado é indefinido |
bsf |
Obtém o índice do bit definido menos significativo. Se nenhum bit estiver definido, o resultado é indefinido |
Essas instruções trabalham todas com dois operandos de 16 bits, 32 bits ou 64 bits.
Elas não podem ser usadas com operandos de 8 bits.
Instruções
Seu amigo acabou de lhe enviar uma mensagem com um segredo importante.
Como ele não queria facilitar a vida de quem tentasse lê-la, a mensagem foi criptografada por meio de uma série de manipulações de bits.
Você vai precisar escrever os métodos que ajudam a descriptografar a mensagem.
Estas são as instruções de bit único mencionadas neste conceito:
| Name |
Description |
| bt |
copia o bit para CF sem modificar nenhum operando |
| bts |
copia o bit para CF e o define no operando de destino |
| btr |
copia o bit para CF e o limpa no operando de destino |
| btc |
copia o bit para CF e o complementa (inverte) 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 |
Rotaciona os bits para a esquerda |
| ror |
Rotaciona 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 nenhum bit estiver definido, o resultado é indefinido |
| bsf |
Obtém o índice do bit definido menos significativo. Se nenhum bit estiver definido, o resultado é indefinido |
A mensagem está codificada em um número inteiro de 16 bits.
No entanto, dos 16 bits, os 8 mais altos não fazem parte da mensagem de fato: eles formam uma máscara que precisa ser usada na descriptografia.
Implemente a função extract_higher_bits, que recebe um número inteiro de 16 bits e retorna os 8 bits mais altos dele.
extract_higher_bits(0b1010010011000101)
// => 0b10100100
Saber extrair a máscara não é suficiente: você também precisa isolar a mensagem.
Implemente a função extract_lower_bits, que recebe um número inteiro de 16 bits e retorna os 8 bits mais baixos dele.
extract_lower_bits(0b1010010011000101);
// => 0b11000101
Alguns bits estão definidos tanto na mensagem quanto na máscara.
Essa é uma informação muito importante, que será usada mais adiante.
Implemente a função extract_redundant_bits, que recebe um número inteiro de 16 bits, codificando tanto a mensagem quanto uma máscara, e retorna um número inteiro de 8 bits com apenas os bits redundantes definidos.
Um bit no número retornado deve ser definido como 1 quando também for 1 tanto na mensagem quanto na máscara.
Todos os outros bits devem ser limpos.
extract_redundant_bits(0b1010010011000101);
// => 0b10000100
4. Defina todos os bits da mensagem
Em seguida, há alguns bits que precisam ser definidos como 1 na mensagem, de acordo com a máscara.
Implemente a função set_message_bits, que recebe um número inteiro de 16 bits, codificando tanto a mensagem quanto uma máscara, e retorna o resultado de definir como 1 os bits da mensagem.
Um bit da mensagem deve ser definido como 1 quando o bit na máscara for 1.
Todos os outros bits devem ser mantidos inalterados, de modo que continuem definidos se já estavam definidos, e limpos se já estavam limpos.
set_message_bits(0b1010010011000101);
// => 0b11100101
5. Rotacione a chave privada
Há uma peça do quebra-cabeça que não está explícita na mensagem: o número de 16 bits 0b1011001100111100.
Esse número é a sua chave privada compartilhada, e você deve usá-la para ajudar a descriptografar a mensagem.
Para isso, primeiro você precisa rotacionar os bits da sua chave privada para a esquerda em um certo número de posições.
O número de posições é igual ao número de bits redundantes definidos tanto na mensagem quanto na máscara.
Implemente a função rotate_private_key, que recebe um número inteiro de 16 bits, codificando tanto a mensagem quanto uma máscara, e retorna o resultado de rotacionar a sua chave privada.
Esse resultado é um número inteiro de 16 bits.
rotate_private_key(0b1010010011000101);
// => 0b1100110011110010
O NASM (The Netwide Assembler, o montador usado por esta trilha) tem suporte a constantes em formato binário com o prefixo 0b.
Ele também aceita o uso de um sublinhado (_) como separador em uma constante, para facilitar a leitura:
PRIVATE_KEY equ 0b1011_0011_0011_1100
Para ser usada na descriptografia, a sua chave privada precisa ser formatada de modo a isolar os bits relevantes.
Para formatar completamente uma chave privada, você deve:
- Rotacioná-la.
- Isolar a porção de 8 bits mais baixa da chave privada rotacionada, que é o valor base.
- Isolar a porção de 8 bits mais alta da chave privada rotacionada, que é uma máscara a ser aplicada 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.
Implemente a função format_private_key, que recebe um número inteiro de 16 bits, codificando tanto a mensagem quanto uma máscara, e retorna uma chave privada de 8 bits totalmente formatada.
format_private_key(0b1010010011000101);
// => 0b11000001
7. Conclua a descriptografia
Quando você tiver a mensagem com todos os bits relevantes definidos e a chave privada formatada, é hora de juntá-las para obter a mensagem resultante.
A mensagem resultante é um número inteiro de 16 bits, no qual:
- Os 8 bits mais altos são preenchidos com a chave privada formatada.
- Os 8 bits mais baixos são preenchidos com a mensagem, depois de definir todos os bits relevantes.
Implemente a função decrypt_message, que recebe um número inteiro de 16 bits codificando tanto a mensagem quanto uma máscara, e retorna um número inteiro de 16 bits com a mensagem totalmente descriptografada.
Essa função deve usar a chave privada formatada que você gera com format_private_key e também a mensagem com todos os bits relevantes definidos com set_message_bits.
decrypt_message(0b1010010011000101);
// => 0b1100000111100101
Exercício de aprendizagem
