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

[Bob Paddock]

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
>  ADD r0, r0
>  ADC r1, r2
>  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;