Re: [avr-gcc-list] udivmodqi optimization

[Dmitry K.]

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.
>
> I simplified a bit more, by dropping the lower byte of the 24 bit result
> of doing the 8 bit x 16 bit multiply, and verifyng that the result was
> not affected by this.
>
> The advantage of this method is that when doing constant divisions, like
>   "a / 10", we do a couple of multiplies (cheap on enhanced avr's) and
> additions instead of calling a function that loops 8 times doing
> compares and subtracts.
>
> Even if we need the module (we often do), it is just one more multiply /
> subtract away.
>
> I can write the assembly code for doing this, if it seems like a good
> idea, but if someone more experienced can write the md rules, that would
> be great :)

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).

Dmitry.