Re: [fpc-devel] The "magic div" algorithm

[Marģers . via fpc-devel]

if you have not bout book you can always try search in internet.

I did some research in magic div constants. As already known, there are good case where you can replace division by

mov magic
mul
shr

and bad case

mov magic
mul
add
rcr
shr


Bad cases are approximately  1/3 of all cases.
For unsigned byte, word and dword divisions by constant on 64 bit cpu can be converted as good cases.

Here is possibility for improvements.
 

----- Reply to message -----
Subject: Re: [fpc-devel] The "magic div" algorithm
From: J. Gareth Moreton via fpc-devel <fpc-devel@lists.freepascal.org>
To: <fpc-devel@lists.freepascal.org>

Something tells me I should purchase that book - I sense it could reveal some interesting insights.

Note that while I understand the concept of turning integer division into multiplication (indeed, I implemented the first version into x86 before it was improved with the "calc_divconst_magic_unsigned" routine, and then implemented it for AArch64), the algorithm that is used in "calc_divconst_magic_unsigned" I don't quite get if just for the lack of comments and references, although I am studying it more closely.

Still, I figure I'll put down Hacker's Delight as a future purchase so I have a reputable source rather than just an online one (I know there's one somewhere that isn't behind a paywall).

Gareth aka. Kit

On 20/08/2021 18:46, Marģers . via fpc-devel wrote:

 

 is there a reference to the algorithm that's used to calculate the
reciprocal constants used in the integer division optimisations for x86 and AArch64?

Hacker’s Delight
Second Edition
Henry S. Warren, Jr.

 

 

_______________________________________________
fpc-devel maillist  -  fpc-devel@lists.freepascal.org
https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel

 

	

		

			

			
Virus-free. www.avast.com
		
	

_______________________________________________
fpc-devel maillist  -  fpc-devel@lists.freepascal.org
https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel