Re: [avr-gcc-list] udivmodqi optimization

[Paulo Marques]

Dmitry K. wrote:
> On Saturday 10 December 2005 01:32, Paulo Marques wrote:
>
> > Hi, all
> >
> > A while ago I noticed gcc for i386 sometimes optimized a division with a
> > constant value by doing a multiply with the inverse in fixed point.
> >
> > It goes something like:
> >
> > a / b <=> (a * (0x10000 / b)) / 0x10000  (*)
> >
> > Due to the fact that this actual truncates the result (instead of
> > rounding), the factor should be ((0x10000 / b) + 1), instead.
> >
> > I did a small program to test this out on a PC and it turns out that it
> > works just fine.
> > [...]
>
> It is very interesting idea.
> Is it really possible to use this method for 'b' which is not
> a power of 2 ?  (Case of 'b is power of 2' is not interesting:
> Gcc optimizes such division).

Yes, I know :)

Just run the code attached on the first email on a PC. It shows that 
with a 16 bit multiplier you can do *any* 8 / 8 bit division.

It probably can also be done with a 32 bit multiplier to do 16/16 bit 
divisions.

The great limitation is that the divider must be a constant known at 
compile time. But IMHO many divisions we do on regular code fall under 
this category.

Note that this is just worth it on a enhanced AVR that has MUL 
instructions. If you have to do the multiply yourself, you migth as well 
do the division instead...

--
Paulo Marques
Software Development Department - Grupo PIE, S.A.
Phone: +351 252 290600, Fax: +351 252 290601
Web: www.grupopie.com

Pointy-Haired Boss: I don't see anything that could stand in our way.
           Dilbert: Sanity? Reality? The laws of physics?