avr-gcc-list
[Top][All Lists]

## Re: [avr-gcc-list] Small super-optimizer results

 From: Bob Paddock Subject: Re: [avr-gcc-list] Small super-optimizer results Date: Mon, 11 Jul 2011 15:40:04 -0400

```On Mon, Jul 11, 2011 at 2:02 PM, Paulo Marques <address@hidden> wrote:

> Some time ago I toyed with trying to build a super-optimizer for the
> avr. The project didn't went very far, but it produced a few small bits
> of code that I think are worth sharing.
>
> Basically I was trying to produce functions to multiply an 8 bit value
> by 8 bit constants with a 16 bit result in avr families without a mul
> instruction.

Your results looked similar to what I've seen out of the
"star-chain" multiplication routine from Doctor Dobb's Journal #125, March 1987.
[The old multiplication one is not on line, but the newer division one
is, with broken formatting:
http://drdobbs.com/high-performance-computing/184408499 ]

Curious if you were doing the some thing similar?

> multiply x129:
>  MOV r2, r0
>  ROR r1
>  ROR r0

[Output from the 'starchain.exe' I hacked together long ago:]
/* The factors of 129 are: 3 43 */

Star-Chain Multiply of 129:

/*  Multiplier = 129 */

Rw =   R1 = /* Your Multiplicand */
Rw <<= 7;
Rw +=  R1;

Star-Chain Division by 129:

R1 = /* Your divisor */
Rw = R1;
Rw <<= 7;
Rw -= R1;
Rw <<= 2;
Rw += 511;
Rw >>= 16;

> multiply x254
>  NEG r0
>  SBC r1, r0
>  SBC r0, r1
>  SBC r1, r2

/* The factors of 254 are: 2 127 */

Star-Chain Multiply of 254:

/*  Multiplier = 254 */

Rw =   R1 = /* Your Multiplicand */
Rw <<= 7;
Rw -=  R1;
Rw <<= 1;

Star-Chain Division by 254:

R1 = /* Your divisor */
R1 >>= 1;
Rw = R1;
Rw <<= 7;
Rw += R1;
Rw <<= 2;
Rw += 519;
Rw >>= 16;

> multiply x255
>  NEG r0
>  SBC r1, r0

/* The factors of 255 are: 3 5 17 */

Star-Chain Multiply of 255:

/*  Multiplier = 255 */

Rw =   R1 = /* Your Multiplicand */
Rw <<= 8;
Rw -=  R1;

Star-Chain Division by 255:

R1 = /* Your divisor */
Rw = R1;
Rw <<= 8;
Rw += R1;
Rw += 257;
Rw >>= 16;

```