Magic Numbers

[Grincheux]

Sometimes in our programs me must divide numbers.
Numbers which are not a power of two.
We use the DIV instruction, very slow.
I propose to change the DIV by the MUL instruction, faster.
How to proceed?
First of all you must know that we will use "Magic Numbers".
A "Magic Numbers" is computed using 2^32.
For example, the magic number for 17 is (2^32) / 17 = 4294967296 / 17 = 252645135 (0F0F0F0Fh))
When multiplying by this number we get the result.
This is the theory.

On the site http://www.hackersdelight.org/magic.htm you can compute these numbers.

For 17, we get : 4042322161, hex F0F0 F0F1
But we also have an indicator which tells the result must be right shifted by 4 bytes
and eventually we must add the "Add" indicator, 0 in this case.

Rather than compute these numbers with the help of the site, long, long... operation.
I made it for the 256 first numbers!

I created a file (http://phrio.biz/download/$Unsigned_Magic_Numbers.zip) for the 65535 numbers.
I have written a small asm program that shows hows to use these numbers.
It is http://phrio.biz/download/$MagicSrcPgm.zip.
I have translated the numbers in bytes because MASM did errors when compiling.

Code Select Expand


WinMainCRTStartup :

lea ecx,[OFFSET UnSignedMagicNumbers + (6 * 17)] ; 17 is the divisor
mov eax,25000
xor edx,edx
mul DWord Ptr [ecx]
movzx eax,Byte Ptr [ecx + 4]
mov cl,Byte Ptr [ecx + 5]
shr edx,cl
add eax,edx

comment @
00401000 8D 0D 66 20 40 00    lea         ecx,ds:[402066h] 
00401006 B8 A8 61 00 00       mov         eax,61A8h ; Number to divide : 25000 (10)
0040100B 33 D2                xor         edx,edx ;EAX = 000061A8 ECX = 00402066 EDX = 00000000
0040100D F7 21                mul         eax,dword ptr [ecx] ;EAX = 69696F28 ECX = 00402066 EDX = 00005BE9
0040100F 0F B6 41 04          movzx       eax,byte ptr [ecx+4] ;EAX = 00000000 ECX = 00402066 EDX = 00005BE9 
00401013 8A 49 05             mov         cl,byte ptr [ecx+5] ;EAX = 00000000 ECX = 00402004 EDX = 00005BE9
00401016 D3 EA                shr         edx,cl ;EAX = 00000000 ECX = 00402004 EDX = 000005BE
00401018 03 C2                add         eax,edx ;EAX = 000005BE ECX = 00402004 EDX = 000005BE
; 25000 / 17 = 1470 (05BEh)
; 26 bytes - Registers used : EAX, ECX, EDX

END WinMainCRTStartup


See also : http://www.hackersdelight.org/indexEdition1.shtml

[dedndave]

i use qWord's MagicNumber program   :t

http://www.masmforum.com/archive2012/6717_MagicNumber64.zip

[dedndave]

the original thread...

http://www.masmforum.com/board/index.php?topic=9937.0

[Grincheux]

Good work, useful.
The difference between my work and this program is that I have an exhaustive tab.

[TouEnMasm]

32 and 64 bits,not of mine

[Grincheux]

ToutEnAsm how does it work?

[TouEnMasm]

How it work ?
Put the divider in the edit (32 or 64) box and press the enter (Entrée) key.

The code to copy appear in the dialog box