Nesta seção faremos alguns cálculos com números binários, considerando cada um de seus dígitos, também chamados de bits. Além de operações aritiméticas clássicas como adição, subtração, multiplicação e divisão, estudaremos também conjunção, disjunção, negação e disjunção exclusiva. Também incluiremos outras operações bit-a-bit que fogem da álgebra tradicional, como deslocamento e rotação de bits. Todas são importantes pois existem no contexto do Assembly, que estudaremos no futuro.
Você pode encontrar mais sobre este assunto pesquisando por álgebra booleana e operações bit-a-bit (bitwise).
Dados dois bits x e y, a conjunção entre eles resulta em 1 se ambos forem iguais a 1. Na programação, o seu símbolo na programação é normalmente o "e comercial" (&). Sendo assim, a chamada tabela verdade desta operação é:
Então suponha que queiramos calcular a conjunção do número 0xa com 12. Sim, estamos misturando dois sistemas de numeração (hexadecimal e decimal) na mesma operação. E por que não? O segredo é converter para binário e fazer o cálculo para cada bit, respeitando a tabela verdade da conjunção. Mãos à obra:
O resultado é 0b1000, ou 8 em decimal. Sendo assim, as linhas abaixo farão o mesmo cálculo, ainda que utilizem sistemas de numeração (bases) diferentes:
Por que utilizei tantas bases diferentes? Quero com isso por na sua cabeça que um número é só um número, independente da base na qual ele está sendo representado.
O resultado da disjunção entre dois bits x e y é 1 se pelo menos um deles for 1. Sendo assim, segue a tabela verdade:
Na programação, o símbolo normalmente é a barra em pé (|). Por exemplo, vamos calcular a disjunção entre 8 e 5:
O resultado é 0b1101, que é 13 em decimal.
Aí você pode questionar:
Opa, então a disjunção é tipo a soma?
Te respondo:
Não.
Veja que o resultado da disjunção entre 9 e 5, também é 13:
Isso porque numa soma entre 1 e 1 o resultado seria 10 (2 em decimal), já na operação OU o resultado é 1.
A disjunção exclusiva entre x e y resulta em 1 se somente um deles for 1. Sendo assim:
Assim como a disjunção é normalmente chamada de "OU", a disjunção exclusiva é chamada de "OU exclusivo", ou simplesmente XOR. O símbolo que representa a disjunção exclusiva em programação é o circunflexo (^).
Algumas propriedades importantes desta operação são:
Você pode aplicá-la em qualquer ordem. Então, x ^ (y ^ z) = (x ^ y) ^ z por exemplo.
O XOR de um número com ele mesmo é sempre zero.
O XOR de um número com zero é sempre ele mesmo.
A operação XOR tem vários usos em computação. Alguns exemplos:
É possível saber se um número é diferente de outro com XOR. Se os números forem diferentes, o resultado é diferente de zero. Por exemplo, tomemos um XOR entre 8 e 5 e outro entre 5 e 5:
Fica claro que é possível zerar variáveis bastando fazer uma operação XOR do valor dela com ele mesmo, independentemente de que valor é este:
O algoritmo conhecido por XOR swap consiste em trocar os valores de duas variáveis somente com operações XOR, sem usar uma terceira variável temporária. Basta fazer, nesta ordem:
XOR entre x e y e armazenar o resultado em x.
XOR entre x e y e armazenar o resultado em y.
XOR entre x e y e armazenar o resultado em x.
Veja:
Analisando em binário:
Dado um número x, é possível calcular o resultado de uma operação XOR com um valor qualquer que chamaremos de chave. Se usarmos a mesma chave num XOR com este resultado, obtemos o número original:
Portanto, para uma cifrabem básica, se você quiser esconder o valor original de um número antes de enviá-lo numa mensagem, basta fazer um XOR dele com uma chave que só você e o receptor da mensagem conheça (0x42 no exemplo). Assim você usa a chave para fazer a operação XOR com ele e instrui o receptor da mensagem (por outro canal) a usar a mesma chave numa operação XOR afim de obter o número original. Claro que esta cifragem é muito simples, e consequentemente muito fraca e fácil de quebrar, mas está aqui em caráter de exemplo.
Em textos matemáticos sobre lógica, o circunflexo ^ representa conjunção ao invés de disjunção exclusiva. Já em softwares matemáticos, pode significar potência, por exemplo: 2^32 é dois elevado à trigésima segunda potência.
Na língua Portuguesa utilizamos a palavra "OU" no sentido de "OU exclusivo". Por exemplo, quando você pede "Pizza de presunto ou pepperoni ou lombo", quer dizer que só quer um dos sabores (exclusividade). Se fosse uma disjunção tradicional "OU", o garçom poderia trazer presunto com pepperoni, ou mesmo todos os três ingredientes e você não poderia reclamar. :)
O deslocamento para a esquerda (shift left) consiste em deslocar todos os bits de um número para a esquerda e completar a posição criada mais à direita com zero. Tomemos por exemplo o número 7 e uma operação SHL com 1 (deslocar uma vez para a esquerda):
Assim podemos perceber que deslocar à esquerda dá no mesmo que multiplicar por 2. Veja:
No exemplo acima deslocamos 1 bit do número 7 (0b111) para a esquerda três vezes, que resultou em 56. Seria o mesmo que deslocar 3 bits de uma só vez:
De forma análoga, o deslocamento para a direita (shift right), ou simplesmente SHR, consiste em deslocar todos os _bits_de um número para a direita e completar a posição criada à esquerda com zero. Tomando o mesmo 7 (0b111):
O resultado é uma divisão inteira (sem considerar o resto) por 2. Assim, 7/2 = 3 (e sobra 1, que é desconsiderado neste cálculo). Esta é de fato uma maneira rápida de dobrar ou calcular a metade de um número.
Assim como no deslocamento, a rotação envolve deslocar os bits de um número para a esquerda (rotate left) ou direita (rotate right) mas o bit mais significativo (mais à esquerda) é posto no final (mais à direita), no lugar de zero. Por isso é necessário considerar o tamanho. Tomemos o número 5 como exemplo:
O bit zero, que está mais à esquerda, "deu a volta" e veio parar ao lado direito do bit 1, mais à direita do número 0b00000101.
Analise com o número 133 agora:
Desta vez o bit 1, que estava mais à esquerda, veio parar ao lado direito do bit mais à direita, e todos os outros bits foram "empurrados" para a esquerda.
Não estamos limitados a fazer operações ROL e ROR somente com 1. O byte 133 ROL 3 por exemplo resulta em 0x2c. Você é capaz de conferir se acertei?
Para negar um bit, basta invertê-lo:
No entanto, para inverter o número maior, como por exemplo 0b100, é preciso saber seu tamanho. Analise os exemplos abaixo para tamanhos variados:
Fazer essa inversão é o mesmo que calcular o complemento (também chamado de "complemento de um") de um número. Para obter seu simétrico, é preciso ainda somar uma unidade, como vimos anteriormente. Por isso, um NOT bit-a-bit no número 4, por exemplo, resulta em -5. Veja:
Os processadores Intel x86 trabalham com muitas outras operações bitwise, mas detalhá-las foge do escopo deste livro. Conforme você avançar no estudo de engenharia reversa, vai se deparar com elas.
x | y | x & y |
---|---|---|
x | y | x | y |
---|---|---|
x | y | x ^ y |
---|---|---|
x | ~x |
---|---|
Tamanho | 0b100 | ~0b100 |
---|---|---|
0
0
0
0
1
0
1
0
0
1
1
1
0
0
0
0
1
1
1
0
1
1
1
1
0
0
0
0
1
1
1
0
1
1
1
0
0
1
1
0
1 byte
0b00000100
0b11111011
2 bytes (WORD)
0b0000000000000100
0b1111111111111011
4 bytes (DWORD)
0b00000000000000000000000000000100
0b11111111111111111111111111111011
Tudo é número (Pitágoras)
Costumo dizer para meus alunos que um computador é basicamente uma calculadora gigante. Claro que esta é uma afirmação muito simplista, mas a verdade é que a ideia pitagórica de que "tudo é número" cabe muito bem aqui. Não é à toa que em textos sobre a origem da computação você encontra a foto de um ábaco, a primeira máquina de calcular, datando-se aproximadamente de mais de 2000 anos antes de Cristo e que é feita de pedras. De fato, calculus em Latim significa pedrinha (agora você entende a expressão "cálculo renal"!), porque era a maneira que o povo tinha para contar na antiguidade.
Um fato interessante é que a patente número US4812124 do Google descreve um ábaco hexadecimal e é datada de 1988.
Neste capítulo vamos focar nos números. Em breve veremos como o processador trabalha com eles também.
Pois então, o que é um número? De acordo com definição na Wikipédia, um número é um objeto matemático utilizado para contar, medir ou descrever uma quantidade. Na prática também utilizamos números para outros fins, como um número de telefone ou número de série de um equipamento.
O processador de um computador moderno consegue realizar muitos cálculos num intervalo de tempo muito curto. Mas, considerando o computador como dispositivo eletrônico que ele é, já parou para pensar como é que um número "entra" no processador? Para entender isso com precisão, seria necessário falar de eletricidade, física, química e talvez quântica, mas vou resumir: os elétrons que caminham pelos circuitos de um computador e chegam até o processador são interpretados de modo que uma baixa tensão elétrica é interpretada como o número 0 e uma mais alta, como 1. É através de um componente eltrônico chamado transístor que se consegue representar 0 e 1 dentro do processador. Você pode aprender mais sobre isso no apêndice Referências deste livro. Parece pouco, mas nas próximas seções você verá como que, a partir de somente dois números é possível obter-se todos os outros.
Agora que já temos um olhar mais abstraído sobre os números, é necessário entender como o computador trabalha com eles. Acontece que é preciso armazenar estes números em algum lugar antes de usá-los em qualquer operação. Para isso foi criado o byte, a unidade de medida da computação. Consiste em um espaço para armazenar bits (8 na arquitetura Intel, também chamado de octeto). Então, neste livro, sempre que falarmos em em 1 byte, leia-se, "um espaço onde cabem 8 bits". Sendo assim, o primeiro número possível num byte é 0b00000000, ou simplesmente 0 (já que zero à esquerda não vale nada). E o maior número possível é 0b11111111 que é igual a 0xff ou 255, em decimal.
Uma maneira rápida de calcular o maior número positivo que pode ser representado num espaço de x bits é usando a fórmula 2^x - 1. Por exemplo, para os 8 bits que mencionamos, basta elevar 2 à oitava potência (que resulta em 256) e diminuir uma unidade: 2^8 - 1 = 255. E por que diminuir um? Porque que o zero precisa ser representado também. Se podemos representar 256 números diferentes e o zero é um deles, ficamos com a faixa de 0 a 255.
Agora que você já sabe o que é um byte, podemos apresentar seus primos nibble (metade dele), word, double word e quad word. Veja a tabela:
Fica claro que o maior valor que cabe, por exemplo, numa variável, depende de seu tamanho (quantidade de espaço para armazenar algum dado). Normalmente um tipo inteiro tem 32 bits, portanto, podemos calcular 2 elevado a 32 menos 1, que dá 4294967295. O inteiro de 32 bits ou 4 bytes é muito comum na arquitetura Intel x86.
Já vimos que um byte pode armazenar números de 0 a 255 por conta de seus 8 bits. Mas como fazemos quando um número é negativo? Não temos sinal de menos (-), só bits. E agora? Não é possível ter números negativos então? Claro que sim, do contrário você não poderia fazer contas com números negativos e o código em Python abaixo falharia:
Mas não falhou! Isso acontece porque na computação dividimos as possibilidades quase que "ao meio". Por exemplo, sabendo que 1 byte pode representar 256 possibilidades (sendo o 0 e mais 255 de números positivos), podemos dividir tais possibilidades, de modo a representar de -128 até +127. Continuamos com 256 possibilidades diferentes (incluindo o zero), reduzimos o máximo e aumentamos o mínimo. :-)
O bit mais significativo (mais à esquerda) é utilizado para representar o sinal. Se for 0, é um número positivo. Se for 1, é um número negativo.
Há ainda a técnica chamada de complemento de dois, necessária para calcular um valor negativo. Para explicá-la, vamos ao exemplo de obter o valor negativo -10 a partir do valor positivo 10, considerando o espaço de 1 byte. Os passos são:
Converter 10 para binário, que resulta em 0b1010.
Acrescentar à esquerda do valor binário os zeros para formar o byte completo (8 bits): 0b00001010.
Inverter todos os bits: 0b11110101 (essa operação é chamada de complementação ou complemento de um).
Somar 1 ao resultado final, quando finalmente chegamos ao complemento de dois: 0b11110110.
Sendo assim, vamos checar em Python:
O que aconteceu? Bem, realmente 0b11110110 é 246 (em decimal), se interpretado como número sem sinal. Acontece que temos que dizer explicitamente que vamos interpretar um número como número com sinal (que pode ser positivo ou negativo). Em Python, um jeito é usando o pacote ctypes:
Já em C, é preciso especificar se uma variável é signed ou unsigned. O jeito como o processador reconhece isso foge do escopo deste livro, mas por hora entenda que não há mágica: 0b11110110 (ou 0xf6) pode ser tanto 246 quanto -10. Depende de como é interpretado, com ou sem sinal.
Por fim, é importante notar que a mesma regra se aplica para números de outros tamanhos (4 bytes por exemplo). Analise a tabela abaixo, que considera números de 32 bits:
Perceba que o número 0x7fffffff tem seu primeiro bit zerado, portanto nunca será negativo, independente de como seja interpretado. Para ser um número negativo, é necessário que o primeiro bit do número esteja setado, ou seja, igual a 1.
Conhecemos bem os dez símbolos latinos 0, 1, 2, 3, 4, 5, 6, 7, 8 e 9 utilizados no sistema de numeração decimal. Neste sistema, o símbolo 0 (zero) é utilizado para descrever uma quantidade nula, enquanto o símbolo 1 (um) descreve uma quantidade, o 2 (dois) duas quantidades e assim sucessivamente, até que atinjamos a quantidade máxima com apenas um dígito, que é 9 (nove). Para representar uma quantidade a mais que essa, a regra é: pegamos o símbolo que representa uma quantidade e colocamos à sua direita o que representa uma quantidade nula formando, assim, 10 (dez). O mesmo processo ocorre com este zero à direita, até que os dígitos "acabem" novamente e aí incrementamos o 1 da esquerda em uma unidade, até que chegamos ao 20. Estudos futuros definiram este conjunto como números naturais e adicionaram outros: números inteiros (que contemplam os negativos), fracionários, complexos, etc.
Mas este não é o único - nem é o primeiro - sistema para representação de quantidades. Ou seja, não é o único sistema de numeração possível. Os computadores, diferente dos humanos, são máquinas elétricas. Sendo assim, a maneira mais fácil de números fluírem por eles seria com um sistema que pudesse ser interpretado a partir de dois estados: ligado e desligado.
O sistema binário surgiu há muito tempo e não vou arriscar precisar quando ou onde, mas em 1703 o alemão Leibniz publicou um trabalho refinado, com tradução para o inglês disponível em http://www.leibniz-translations.com/binary.htm, baseado na dualidade taoísta chinesa do yin e yan a qual descrevia o sistema binário moderno com dois símbolos: 0 (nulo) e 1 (uma unidade). Por ter somente dois símbolos, ficou conhecido como sistema binário, ou de base 2. A contagem segue a regra: depois de 0 e 1, pega-se o símbolo que representa uma unidade e se insere, à sua direita, o que representa nulo, formando o número que representa duas unidades neste sistema: 10.
Daí vem a piada nerd que diz haver apenas 10 tipos de pessoas no mundo: as que entendem linguagem binária e as que não entendem.
Assim sendo, se formos contar até dez unidades, teremos: 0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001 e 1010.
Perceba que a lógica de organização dos símbolos no sistema binário é a mesma do sistema de numeração decimal. No entanto, em binário, como o próprio nome sugere, só temos dois símbolos disponíveis para representar todas as quantidades.
Por utilizar dois símbolos que são idênticos aos do sistema decimal, num contexto genérico, números binários são normalmente precedidos com 0b para não haver confusão. Então para expressar dez quantidades faríamos 0b1010. Por exemplo, a seguinte linha na console do Python imprime o valor 10:
Ou em linguagem C:
Como o próprio nome sugere, o sistema octal possui oito símbolos: 0, 1, 2, 3, 4, 5, 6 e 7. À esta altura já dá pra sacar que para representar oito quantidades em octal o número é 10. Nove é 11, dez é 12 e assim sucessivamente.
O sistema octal é utilizado para as permissões de arquivo pelo comando chmod nos sistemas baseados em Linux e BSD. Os números 1, 2 e 4 representam permissão de execução, escrita e leitura, respectivamente. Para combiná-las, basta somar seus números correspondentes. Sendo assim, uma permissão 7 significa que se pode-se tudo (rwx) enquanto uma permissão 6 somente escrita e leitura (rw-). Tais números foram escolhidos para não haver confusão. Se fossem os números 1, 2 e 3 a permissão 3 poderia significar tanto ela mesma quanto 1+2 (execução + escrita). Usando 1, 2 e 4 não há brechas para dúvida. ;)
Na programação, normalmente um número octal é precedido de um algarismo 0 para diferenciar-se do decimal. Por exemplo, 12 é doze em decimal, mas 012 é octal, que vale dez em decimal. Logo, preste atenção antes de ignorar um zero à esquerda.
Veja um exemplo em Python (lembre-se: abra o Python e estude junto agora):
Finalmente o queridinho hexa; o sistema de numeração que mais vamos utilizar durante todo o livro.
O hexadecimal apresenta várias vantagens sobre seus colegas, a começar pelo número de símbolos: 16. São eles: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E e F. Os números que eles formam são normalmente prefixados com 0x, embora alguns programas utilizem um sufixo h. Por exemplo: 0x1234 ou 1234h.
Perceba que todos os sistemas apresentados até agora utilizam os mesmos símbolos latinos. Isso é só para facilitar mesmo.
Aqui cabe uma tabela comparativa, só para exercitar:
Existem algumas propriedades interessantes quando relacionamos os diferentes sistemas de numeração vistos aqui. São elas:
Quanto mais símbolos existem no sistema, menos dígitos utilizamos para representar mais quantidades.
0xF é igual a 0b1111, assim como 0xFF equivale a 0b11111111 e 0xFE é o mesmo que 0b11111110.
0x10 é 16. Então, 0x20 é 32 e 0x40 é 64.
Em hexadecimal, 9 + 1 é A, então 19 + 1 é 1A.
Na arquitetura x86, os endereços são de 32-bits. Ao analisar a pilha de memória, é bom se acostumar com decrementos de 4 bytes. Por exemplo, 12FF90, 12FF8C, 12FF88, 12FF84, 12FF80, 12FF7C e assim sucessivamente.
Na conversão de hexadecimal para binário, cada dígito hexa pode ser compreendido como quatro dígitos binários. Para exemplificar, tomemos o número 0xB0B0CA. Separando cada dígito hexa e convertendo-o para binário, temos:
Por isso podemos dizer que 0xB0B0CA é 0b101100001011000011001010.
Em hexadecimal, zeros à esquerda e letras maiúsculas ou minúsculas não importam. Veja no Python:
Falaremos bastante em endereços de memória no conteúdo de engenharia reversa e todos estão em hexadecimal, por isso é importante "pensar em hexa" daqui para frente. Mas não se preocupe, se precisar calcular algo, sempre poderá recorrer à calculadora ou ao Python.
Um bom exercício para fixar este conteúdo é criar o seu sistema de numeração com símbolos à sua escolha. Por exemplo, inventarei agora um sistema ternário chamado Lulip's que possui os seguintes símbolos para representar zero, uma e duas quantidades respectivamente: @, # e $. Olha só como ficaria a comparação dele com o sistema decimal:
É importante que você perceba a lógica utilizada para contar no sistema Lulip's. Apesar de não ser um sistema que exista por aí, ele serve de base para você entender como qualquer valor, em qualquer sistema, pode ser convertido para outro.
Binário | Hexadecimal | Com sinal | Sem sinal |
---|---|---|---|
Hexadecimal | Decimal | Octal | Binário |
---|---|---|---|
Decimal | Lulip's |
---|---|
Medida
Tamanho (Intel)
Nomenclatura Intel
nibble
4 bits
byte
8 bits
BYTE
word
16 bits
WORD
double word
32 bits
DWORD
quad word
64 bits
QWORD
10000000000000000000000000000000
80000000
-2147483648
2147483648
11111111111111111111111111111111
FFFFFFFF
-1
4294967295
00000000000000000000000000000000
00000000
0
0
01111111111111111111111111111111
7FFFFFFF
2147483647
2147483647
0
0
0
0
1
1
1
1
2
2
2
10
3
3
3
11
4
4
4
100
5
5
5
101
6
6
6
110
7
7
7
111
8
8
10
1000
9
9
11
1001
A
10
12
1010
B
11
13
1011
C
12
14
1100
D
13
15
1101
E
14
16
1110
F
15
17
1111
0
@
1
#
2
$
3
#@
4
##
5
#$
6
$@
7
$#
8
$$
9
#@@
10
#@#
11
#@$