AVR-Chat

Hi

With the recent thread on challenges, twiddles and optimisation in mind, 
I thought you might be interested in this:

I have a program that requires a 16x16 unsigned multiply. This has to be 
performed quickly inside an interrupt handler so I looked stuff up, 
checked the assembler codes for the AVR and dug in.

ATMEL app note 200 give some code for an unsigned 16x16. It says it 
needs 153 cycles plus time to get the values in and out of the 
registers. More than 10us on a 16MHz device. This is longer than I wanted.

After a bit of beavering away with AVR Studio, I decided to see what my 
C compiler (CodeVision) could do. I should have looked earlier.

unsigned long z;
unsigned int w,x,y;

z = (long)x * (long)y;	// takes 94 cycles (5.875us at 16MHz)
z = (long)x * y;        // takes 71 cycles (4.4375us at 16MHz)

In my application, I only wanted the most significant 16 bits. there are 
two easy ways to shed them:

w = ((long)x * y) / 65536;  //takes 782 cycles (toooo long at 16MHz)

This seems to trigger a full divide with the compiler missing the 
optimisation, so I gave it a clue:

w = ((long)x * y) >> 16;  // takes 79 cycles (a shade under 5us)

Now the compiler optimisation triggers and it generates code that just 
moves the two most significant bytes down and puts zeros in their place.

For what it is worth, I wrote an inline assembly function to give me a 
result by multiplying the bytes directly and disregarding the least 
significant parts. I can live with the error of a bit in the least 
significant position. This way needs only 24 cycles - 1.5us at 16MHz. 
(It is not a challenge, I am sure a few more cycles could be saved and 
the answer is not accurate but it is sufficient)

   #asm
   sub r31,r31
   lds r22,_x    ; LSB of X
   lds r23,_x+1
   lds r24,_y
   lds r25,_y+1  ; MSB of Y
   mul r22,r25
   mov r30,r1    ; only bother with the high byte
   mul r23,r24
   add r30,r1    ; only bother with the high byte
   adc r31,r31   ; remember the carry, r31 is still zero
   mul r23,r25
   add r30,r0
   adc r31,r1
   sts _w,r30
   sts _w+1,r31
   #endasm


Now the inline version is clearly fastest, as you would expect. However, 
  I can live with the 5us result in this application and I gain 
portability as the code is all in C. The only thing to watch is that, 
should I move the code to another machine that it still performs well. 
It should do as that is likely to be something with a 16x16 hardware 
multiply.


Pete Harrison