[avr-gcc-list] udivmodqi optimization

[Paulo Marques]

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

--
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?

(*) this was 32 bits on a i386, i.e., 0x100000000, but I'm simplifying 
here for avr and 8 bit values
#include <stdio.h>

int drop_lower_byte_mul(int a, int b)
{
        return ((a * (b & 0xFF)) >> 8) + (a * ((b >> 8) & 0xFF));
}

int test_number(int a, int b)
{
        int i;

        for (i = 0; i < 256; i++) {
                if ((i / a) != (drop_lower_byte_mul(i, b) >> 8))
                        return 0;
        }
        return 1;
}

int main(void)
{
        int i, mul;

        for (i = 1; i < 256; i++) {
                mul = (65536 / i) + 1;
                if (!test_number(i, mul)) {
                        printf("no factor for %d\n", i);
                } else {
                        printf("factor for %d = %d\n", i, mul);
                }
        }
        return 0;
}