## [sdcc-devel] Multiplication question

 [sdcc-devel] Multiplication question From: Michael Hope - 2001-10-16 05:14:26 ```I've begun adding code so that a port can have some multiplications pass through to genMult and some go to the support function calls. This is useful on the z80 where one of the operands is a constant and the result is 8 or 16 bit, as you can use the add hl,hl instruction to multiply reasonably quickly. Say result = left * n where n is a positive constant with two set bits, then hl can do the top most bit and de can be used as a tap to do the middle bit. Eg: n = 5 (4+1) ld hl,left ld de,hl ; Tap at 1. ld de,hl is sumbolic - doesnt really exist. add hl,hl ; Multiply by 4 add hl,h add hl,de ld result,hl n = 12 (8+4) ld hl,left add hl,hl add hl,hl ld de,hl ; Tap at *4 add hl,hl add hl,de ld result,hl which are both a hell of alot cheaper than the equivalent function call and are especially good for indexing to arrays of structures. Like in the dhrystone test :) So here's my question. Can you do the same for where n is a power of 2 minus a power of 2? - The above is a power of 2 plus a power of 2. For example, n = 7 (8-1, 2^3 - 2^0) ld hl,left ld de,hl ; Tap at *1 add hl,hl add hl,hl add hl,hl sub hl,de ld result,hl It works for small values, but does it still work when it starts truncating? I can probably proove it by doing a long multiplication on paper and comparing it to the result of above, but I'm lazy :) Any better ways to proove it? -- Michael ```

 [sdcc-devel] Multiplication question From: Michael Hope - 2001-10-16 05:14:26 ```I've begun adding code so that a port can have some multiplications pass through to genMult and some go to the support function calls. This is useful on the z80 where one of the operands is a constant and the result is 8 or 16 bit, as you can use the add hl,hl instruction to multiply reasonably quickly. Say result = left * n where n is a positive constant with two set bits, then hl can do the top most bit and de can be used as a tap to do the middle bit. Eg: n = 5 (4+1) ld hl,left ld de,hl ; Tap at 1. ld de,hl is sumbolic - doesnt really exist. add hl,hl ; Multiply by 4 add hl,h add hl,de ld result,hl n = 12 (8+4) ld hl,left add hl,hl add hl,hl ld de,hl ; Tap at *4 add hl,hl add hl,de ld result,hl which are both a hell of alot cheaper than the equivalent function call and are especially good for indexing to arrays of structures. Like in the dhrystone test :) So here's my question. Can you do the same for where n is a power of 2 minus a power of 2? - The above is a power of 2 plus a power of 2. For example, n = 7 (8-1, 2^3 - 2^0) ld hl,left ld de,hl ; Tap at *1 add hl,hl add hl,hl add hl,hl sub hl,de ld result,hl It works for small values, but does it still work when it starts truncating? I can probably proove it by doing a long multiplication on paper and comparing it to the result of above, but I'm lazy :) Any better ways to proove it? -- Michael ```
 Re: [sdcc-devel] Multiplication question From: Scott Dattalo - 2001-10-16 05:39:06 ```On Tue, 16 Oct 2001, Michael Hope wrote: > I've begun adding code so that a port can have some multiplications pass > through to genMult and some go to the support function calls. This is > useful on the z80 where one of the operands is a constant and the result > is 8 or 16 bit, as you can use the add hl,hl instruction to multiply > reasonably quickly. Michael, I happen to work with the guy that wrote the PIC automatic code generator for efficiently multiplying and dividing constants. It's damn good. I'll approach him and see if he would release it under GPL and allow us to incorporate it into SDCC. > > Say result = left * n where n is a positive constant with two set bits, > then hl can do the top most bit and de can be used as a tap to do the > middle bit. > > Eg: > > n = 5 (4+1) > > ld hl,left > ld de,hl ; Tap at 1. ld de,hl is sumbolic - doesnt really exist. > add hl,hl ; Multiply by 4 > add hl,h hl? ---------^ > add hl,de > > ld result,hl > > n = 12 (8+4) > > ld hl,left > add hl,hl > add hl,hl > ld de,hl ; Tap at *4 > add hl,hl > add hl,de > > ld result,hl > > which are both a hell of alot cheaper than the equivalent function call > and are especially good for indexing to arrays of structures. Like in the > dhrystone test :) > > So here's my question. Can you do the same for where n is a power of 2 > minus a power of 2? - The above is a power of 2 plus a power of 2. > > For example, > > n = 7 (8-1, 2^3 - 2^0) > > ld hl,left > ld de,hl ; Tap at *1 > add hl,hl > add hl,hl > add hl,hl > sub hl,de > > ld result,hl > > It works for small values, but does it still work when it starts > truncating? I can probably proove it by doing a long multiplication on > paper and comparing it to the result of above, but I'm lazy :) Any better > ways to proove it? What do you mean by "starts truncating"? I think you can easily abstract your algorithm for arbitrary N. For example, for n=7: ld hl,left ld de,hl add hl,hl add hl,de add hl,hl add hl,de ld result,hl for n=10 ld hl,left ld de,hl add hl,hl add hl,hl add hl,de add hl,hl ld result,hl in general: ld hl,left ld de,hl b = MSB of N ; eg. b = 2, for N=7 mask = 2^(b-1) while(mask) { add hl,hl if(N & mask) add hl,de mask >>=1; } Scott ```