How does division by constant work in avr-gcc?

Question

In avr assembly, I wanted to divide a number by a constant. I checked how to see how avr-gcc does it. So in a c file I have :

#include <stdint.h>

uint8_t divide_by_6(uint8_t x) {
    return x / 6;
}

and when I run avr-gcc -O3 -mmcu=atmega16 -D__AVR_ATmega16__ -S main.c it gives me:

divide_by_6:
    ldi r25,lo8(-85)
    mul r24,r25
    mov r24,r1
    clr r1
    lsr r24
    lsr r24
    ret

But I do not understand what this assembly is doing. How does this assembly code perform division?

and what is your question exactly? – Dilip Kumar Dec 07 '15 at 14:52 — Dilip Kumar, Dec 07 '15 at 14:52

score 4 · Accepted Answer · answered Dec 07 '15 at 15:15

-85 is 0xFFFFFFFFFFFFFFAB, so lo8(-85) is 0xAB, which is 171.

The code is multiplying the argument by 171, and then returning the most significant byte of the product, shifted right by 2 (i.e. divided by 4).

So it's effectively returning x * 171 / (256 * 4) == x * 171 / 1024, which is approximately == x * 1 / 6 == x / 6.

score 3 · Answer 2 · answered Dec 07 '15 at 18:23

Google: Jones on reciprocal multiplication

We all know or should know from elementary school that dividing by n is the same as multiplying by 1/n. We also learned how to use decimal places. And other manipulations, so multiplying by 1.234 is the same as multiplying by 1234 then dividing by 1000 later or not and just knowing that your result is 1000 to big. Like thinking in pennies instead of dollars 12.34 dollars is 1234 pennies. 6 hours is 360 minutes, etc.

Long division in binary is trivial compared to grade school. For each digit as you move along there can either be exactly zero or exactly one time the divisor fits into the pulled down numerator. Basically for 1/6th you end up with 0.001010101010...in binary.

So if I want 1234/6 I could do 1234*0x2AAA = 0xCDA774. the integer/fixed point answer is 205 which is 0xCD so that makes sense 0x2AAA is (1/6)65536 so (X((1/6)*65536))/65536 = X/6 or (X*0x2AAA)>>16 is approx X/6.

Now what about rounding? 1234/6 is actually 205 and 2/3rds so what if you wanted to round up. Well rounding means you take the number after the cutoff and if that is at or above half you round right? well 10101010 the digit after the cutoff is a 1, 1/2 is at or above half so why not use 0x2AAB?

Also we know that 6 = 2*3. The two comes out of the number easy with a shift so you could do (N/3)/2 or (N/2)/3. And a 1/3 is 0.01010101... binary where 1/6 was 0.001010101...

So this should all lead to a rough idea how you can multiply to divide and a rough idea where the 0xAB they multiplied against may have come from. but other elementary math identities are likely in there as well.

Note you dont have to do the hand binary division, 0x10000/6 = 0x2AAA on your calculator. X/6 = (X*0X10000)/(6*0X10000) = (X/0X10000)(0X10000/6) = (X(0X10000/6))/0X10000. And then you just have to account for accuracy/rounding when trying to use this fixed point. Sometimes 16 bits isnt enough you need 24 or 32 or who knows...depends on the divisor.

How does division by constant work in avr-gcc?

2 Answers2