Primeiro
Infelizmente, não parece que o MathJax está ativado nesta troca de pilha, então as partes matemáticas abaixo estão horrivelmente formatadas. Também estou longe de ser um matemático, então a notação pode estar errada em alguns lugares.
Compreendendo o número mágico e o código
O objetivo do código acima é reescrever uma divisão em uma multiplicação porque a divisão leva mais ciclos de clock do que uma multiplicação. Está na área de cerca de duas vezes mais ciclos, dependendo muito da CPU. Portanto, precisamos encontrar uma boa maneira sem ramificações de fazer isso. Se ramificarmos, provavelmente perderemos para simplesmente fazer a divisão.
Uma maneira é simplesmente perceber que a divisão é o mesmo que a multiplicação com o inverso do número, ou seja, 
. O problema é que 
é um número muito pobre para armazenar como um inteiro. Portanto, precisamos multiplicar o divisor e o dividendo por algum número. Como operamos com números de 32 bits e obtemos resultados de multiplicação em números de 64 bits, obtemos a melhor precisão com 
e também evitamos problemas de estouro. Então basicamente obtemos 
. Essa parte fracionária é o que nos causa problemas, porque causará erros de arredondamento.
Então, vamos tentar formalizar isso:
Onde 
é nosso multiplicando, por exemplo, 
, ou realmente qualquer número 
, mas 
funciona muito bem com nossos tamanhos de registro, pois podemos simplesmente descartar o registro inferior de 32 bits. 
é o número que você deve adicionar para tornar igualmente divisível por 
. 
é o número que desejamos dividir.
Podemos reescrever a equação acima, como
O que ilustra o que temos nosso dividendo 
dividido por nosso divisor 
e então um fator de erro de 
.
Estudando nossa equação original de 
, fica claro que podemos afetar muito pouco. 
precisa ser uma potência de 2, não pode ser muito grande ou corremos o risco de transbordar e não pode ser muito pequeno, pois tem um efeito negativo direto em nosso fator de erro 
. 
depende diretamente de 
e 
.
Então, vamos tentar 
que fornece uma fração máxima de erro de com o valor máximo de 
sendo 
, então 
, infelizmente isso não é menor que 
para que possamos obter erros de arredondamento.
Vamos aumentar o expoente de 
para 
, o que dá 
, fração máxima de erro 
que é menor que 
. Isso significa que nosso multiplicando é 
, que não é menor ou igual ao valor máximo com sinal que podemos armazenar em um registrador de 32 bits (
). Então, em vez disso, fazemos o multiplicando 
. Como uma observação lateral, graças à magia do complemento de dois quando subtraímos 
, o número 
é 
que é 
quando interpretado como um número sem sinal. Mas estamos fazendo aritmética assinada aqui. Portanto, precisamos corrigir a expressão final adicionando 
. Isso também só resolve o problema de 
, para números negativos teremos um erro de 1, então precisamos adicionar 1 se tivermos um número negativo.
Essa é a explicação para a constante na multiplicação e como chegar a ele. Agora, vamos examinar o código:
; Carregar -1840700269mov ecx, 0x92492493; Carregar nmov eax, edi; n * -1840700269imul ecx; adicione n para compensar 2 ^ 32 subtraçãoadd edx, edi; verifique o bit de sinal de nosso resultmov ecx, edxshr ecx, 0x1f; divida por 2 ^ 2 para nos compensar usando y = 2 ^ 34 em vez de 2 ^ 32sar edx, 0x2mov eax, edx; adicione o valor do bit de sinal ao resultado finaladd eax, ecx
Calculando o divisor do número mágico e do código
Eu não provei isso matematicamente, no entanto, se você quiser para recuperar o divisor de um dump de montagem como o que você mostrou, podemos fazer alguns exercícios mentais simples. Primeiro, precisamos perceber que o seguinte é válido
Onde 
é o ajuste que fizemos para colocar o valor na faixa de um valor de 32 bits. A partir do código, podemos conceber o seguinte, o deslocamento à direita por dois significa que temos 
, 
, 
, 
é desconhecido. Isso significa que estamos perdendo uma variável para realizar uma solução perfeita. No entanto, o efeito de é desprezível, pois seu propósito é trazer o divisor o mais próximo possível de seu valor inteiro. Isso significa que a solução pode ser encontrada resolvendo
Outro exemplo com o divisor 31337 que tem o multiplicando número mágico 140346763 e desloca para a direita 10 bits.
Finalmente
Para uma análise matemática completa de como isso funciona, incluindo todas as provas e algoritmos apropriados para calcular o números mágicos, deslocamentos e acréscimos, consulte Hacker's Delight, capítulo 10-3.