[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[avr-gcc-list] udivmodqi optimization

From: Paulo Marques
Subject: [avr-gcc-list] udivmodqi optimization
Date: Fri, 09 Dec 2005 15:32:28 +0000
User-agent: Mozilla Thunderbird 1.0.6 (X11/20050716)

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;

reply via email to

[Prev in Thread] Current Thread [Next in Thread]