topic Re: Signed multiplication using MUL in 8-bit Microcontrollers

Signed multiplication using MUL

JohanF — Fri, 15 Jun 2007 03:13:28 GMT

Hello out there,

I need a fast executing assembly code for signed multiplication (8bitx8bit) using the MUL instruction

/Johan

Re: Signed multiplication using MUL

CompilerGuru — Fri, 15 Jun 2007 04:20:37 GMT

Do you need a 8 or a 16 bit result?
Especially the 8x8=8 bit signed multiplication in simple, its the same as the unsigned one :smileyhappy:
For the 8x8=16 bit signed multiplication, the CW _BMULS runtime routine in lib\hc08c\src\rtshc08.c does just that, it first multiplies unsigned and then adapts the result if the operands have been negative.
And are both of your operands eventually negative, or is one known to be positive?
What do you need it for?

Daniel

Message Edited by CompilerGuru on 2007-06-14 11:21 PM

Re: Signed multiplication using MUL

bigmac — Fri, 15 Jun 2007 12:52:53 GMT

Hello Johan, and welcome to the forum.

As mentioned by Daniel, an approach to 8-bit signed multiply, with 16-bit result, is to convert any negative input value to positive, multiply, then process the signs separately, and convert the result to a negative value, if required.

The following assembly routine appears to work - and assumes ACC and X contain the 8-bit signed values. On exit, X:A should contain the signed result.

SMUL8:    AIS    #-1
          CLR    1,SP           ; Sign calculation on stack
          TSTA
          BPL    SM1            ; Branch if ACC is positive
          NEGA
          COM    1,SP
SM1:      TSTX
          BPL    SM2
          NEGX
          COM    1,SP
SM2:      MUL
          TST    1,SP           ; Test sign of result
          BPL    SM3            ; Exit if positive
          COMA
          COMX
          ADD    #1
          BCC    SM3
          INCX
SM3:      AIS    #1             ; Adjust stack pointer
          RTS

As shown, the routine will take between 43 and 65 cycles for a HCS08 device. Using a temporary, zero page RAM register, in lieu of the stack, will save a few cycles.

Regards,

Mac

Re: Signed multiplication using MUL

tonyp — Fri, 15 Jun 2007 16:26:59 GMT

And here's yet another version.

Re: Signed multiplication using MUL

JohanF — Fri, 15 Jun 2007 19:46:34 GMT

Thanks,

I need 8X8bit into a 16bit result. I already know that one of the factors is positive. The other factor could be either positive or negative.

Re: Signed multiplication using MUL

CompilerGuru — Fri, 15 Jun 2007 19:55:51 GMT

The CW _BMULS does take advantage of that the unsigned 8x8=16 and the signed 8x8=16 result are closely related. So it does the unsigned multiplication first and then patches the resulting high byte to match the signed multiplication behavior. It's 23 bytes, I did not count the cycles.

Daniel

Re: Signed multiplication using MUL

JohanF — Fri, 15 Jun 2007 21:10:53 GMT

Thanks again,

Where do I find this lib\hc08c\src\rtshc08.c? Is it somwhere in the freescale webpage?

/Johan

Re: Signed multiplication using MUL

bigmac — Fri, 15 Jun 2007 22:20:32 GMT

Hello,

The rtshc08.c file can be found within the CW installation. Once you find the file, you will need to search for the function _BMULS. This is an inline assembler routine within a C function wrapper.

For those interested, I have done a performance comparison between the three methods outlined -

Daniel:

Size: 26 bytes

Both values positive: 46 cycles

One value negative: 50 cycles

Both values negative: 54 cycles

TonyP:

Size: 30 bytes

Both values positive: 47 cycles

One value negative: 54 or 55 cycles

Both values negative: 49 cycles

Bigmac:

Size: 35 bytes

Both values positive: 43 cycles

One value negative: 57 or 58 cycles

Both values negative: 57 cycles

All results are based on the HCS08, and assume the routine is called with a JSR instruction (6 cycles). Not surprisingly, the performance differences are small, with the method outlined by Daniel having the best overall efficiency (as might be expected).

Regards,

Mac

Re: Signed multiplication using MUL

CompilerGuru — Sat, 16 Jun 2007 02:19:36 GMT

When manually counting the bytes in _BMULS I do get to 26 bytes too, however when the compiler compiles it does
perform some frame optimizations (replace SP accesses with H:X relative ones), so the compiler does really emit 23 bytes, I did count correctly :smileyhappy:.
I think the frame optimization is the only optimization done for HLI by default, it can be disabled with -onx.

BTW. The TonyP version can save a byte by combining the inca and the coma to a nega :smileyhappy:

Daniel

Re: Signed multiplication using MUL

JohanF — Sat, 16 Jun 2007 04:18:06 GMT

Interesting...

My application is that I want to calculate a DFT to detect a few discret fequencies, from a set of sampled signals.

The signalsamples are 8 bits, always positive.

The phasekoefficients are 8 bits either positive or negative.

So the algoritm is to multiply each sample by its pasekoefficient (into 16 bits result) and add them all together (into 24bits sum).

Based on the number of clockcycles the signed multiplication algoritm takes, I believe I will get away with less clockcycles by:

1. Check sign of phasecoefficient. If negative, negate it to make it positive

2. Calculate unsigned multiplication of phasecoefficient and sample.

3. If the phasecoefficient was positive from the beginning, add 16bit result to the sum.

4. If the phasecoefficient was negative from the beginning, subtract 16bit result from the sum.

As my application is very timecritical, I really need to minimize processing time. In this algoritm, what takes the most time is the adding or subtracting of 16bits to the 24bits sum, but I have to do that weather or not I use a signed multiply or if I do according to above.

Re: Signed multiplication using MUL

CompilerGuru — Sat, 16 Jun 2007 15:35:00 GMT

I think a "24bit += signed16bit" is also slower than a "24bit += unsigned16bit" or "24bit -= unsigned16bit" operation, so using a unsigned 16 bit multiplication helps even more than "just" for the multiplication.

Daniel

Re: Signed multiplication using MUL

bigmac — Sat, 16 Jun 2007 22:57:21 GMT

Hello Johan,

If my understanding of your proposal is correct, there appears to be some advantage in arranging so that the sign of the coefficient be placed in a separate register prior to DFT processing. This should increase the (unsigned) resolution of the coefficient from 7-bits to 8-bits.

The following code would seem to achieve what you describe -

;**************************************************************
; ACCUMULATE SCALED SAMPLE VALUE TO 24-BIT SUM
; On entry,
; ACC = sample value (8-bit unsigned),
; X = Phase coefficient (positive 8-bit value),
; PH_SIGN register (MSB) contains the sign of the coefficient.

; On exit, 24-bit value of SUM is updated.
; RAM registers PH_SIGN and SUM must reside in page zero.

PROCSAMP: MUL
BRCLR 7,PH_SIGN,PS1 ; Branch if positive sign

          ; Subtract scaled result from 24-bit sum
          PSHA
          PSHX
          LDA    SUM+2
          SUB    2,SP
          STA    SUM+2
          LDA    SUM+1
          SBC    1,SP
          STA    SUM+1
          BCC    *+4            ; Skip next if no carry
          DEC    SUM
          AIS    #2             ; Adjust stack pointer
          RTS

PS1:      ; Add scaled result to 24-bit sum
          ADD    SUM+2
          STA    SUM+2
          TXA
          ADC    SUM+1
          STA    SUM+1
          BCC    *+4            ; Skip next if no carry
          INC    SUM
          RTS

The processing of the routine should take 43 cycles for a positive coefficient, and 56 cycles for a negative coefficient. The question is can you live with this sort of sample processing period?

I also looked at the possibility, in the case of a negative coefficient, of negating the result of the multiplication, and then adding to SUM - this would appear to save only two cycles (assuming my coding is correct), and also quite a few bytes of code.

Regards,
Mac

Message Edited by bigmac on 2007-06-17 02:02 AM

Re: Signed multiplication using MUL

JohanF — Mon, 18 Jun 2007 04:34:18 GMT

You have understood correctly. Your code is almost identical to what I came up with (but you won by a couple of cycles...).

I have pasted your code below and calculated cycles, I get 7 cycles less than you have calculated in both cases. Am I wrong?

Are you willing to share your code for taking the negative of a 16-bit number? I think I would benefit by gaining even just a few clockcycles for the negative coefficient.

PROCSAMP: MUL       ; 5 cycles
          BRCLR 7,PH_SIGN,PS1 ; Branch if positive sign ; 5 cycles

          ; Subtract scaled result from 24-bit sum
          PSHA       ; 2 cycles
          PSHX       ; 2 cycles
          LDA    SUM+2      ; 3 cycles
          SUB    2,SP      ; 4 cycles
          STA    SUM+2      ; 4 cycles
          LDA    SUM+1      ; 3 cycles
          SBC    1,SP      ; 4 cycles
          STA    SUM+1      ; 4 cycles
          BCC    *+4            ; Skip next if no carry  ; 3 cycles
          DEC    SUM      ; 4 cycles
          AIS    #2             ; Adjust stack pointer  ; 2 cycles
          RTS       ; 4 cycles

PS1:      ; Add scaled result to 24-bit sum
          ADD    SUM+2      ; 3 cycles
          STA    SUM+2      ; 4 cycles
          TXA       ; 1 cycle
          ADC    SUM+1      ; 3 cycles
          STA    SUM+1      ; 4 cycles
          BCC    *+4            ; Skip next if no carry  ; 3 cycles
          INC    SUM      ; 4 cycles
          RTS       ; 4 cycles

I get the result 36 cycles for a positive coefficient and 49 cycles for a negative coefficient.

Re: Signed multiplication using MUL

rocco — Mon, 18 Jun 2007 06:23:55 GMT

Hi, Johan:

You did not mention which processor you were using, but Mac mentioned that his cycle count was based on the S08. Could your cycle counts be based on the HC08? There is a small difference in cycles between the two versions for some instructions. I did not count cycles myself, as I bet you and Mac are both correct.

As for negating a sixteen-bit number, here is the code I have been using since the early eighties:

** Negate the 16 bit signed integer in the psuedo-accumulator.*NEG16 MACRO        COM    ACCUM1     ; 4        LDA    ACCUM0     ; 3        COMA              ; 1        ADD    #1         ; 2        STA    ACCUM0     ; 3        LDA    ACCUM1     ; 3        ADC    #0         ; 2        STA    ACCUM1     ; 3      ENDM     ;          =21*

This is a macro that negates the low sixteen bits of my 32-bit pseudo-accumulator, but it should be easy to adapt. It takes 21 cycles on an HC08 (I don't use any S08s yet).

If you find a method that is faster, please post it, as everything I do is math-intensive.

Re: Signed multiplication using MUL

rocco — Mon, 18 Jun 2007 06:39:03 GMT

Oh, and here is a routine that negates the 16-bit value, using H:X

        com     value16        ; 4  - compliment the high byte        ldhx    value16        ; 4  - load all 16 bits into H:X        comx                   ; 1  - compliment the low byte        ais     #1             ; 2  - increment all 16 bits
        sthx    value16        ; 4  - save it in place (optional)
;                              =15

On the HC08, it takes only 15 cycles. It's a first draft, so it might be able to be improved upon.

Re: Signed multiplication using MUL

peg — Mon, 18 Jun 2007 06:59:42 GMT

Hi rocco,

That would be aix (not ais)

Still time to edit?

Re: Signed multiplication using MUL

rocco — Mon, 18 Jun 2007 07:31:44 GMT

OOps. Thanks Peg.

Unfortunately, it is too late to edit, although it has only been 45 minutes. What is the timeout, anyway?

So here is the corrected version:

        com     value16        ; 4  - compliment the high byte        ldhx    value16        ; 4  - load all 16 bits into H:X        comx                   ; 1  - compliment the low byte        aix     #1             ; 2  - increment all 16 bits        sthx    value16        ; 4  - save it in place (optional);                              =15

AIX and AIS both take 2 cycles.

Re: Signed multiplication using MUL

bigmac — Mon, 18 Jun 2007 10:16:53 GMT

Hello all,

Since the negated 16-bit value must then be added to the 24 bit accumulator SUM, I would suspect that the negation process should also include the instruction COM SUM, an additional 5 cycles, to prepare for the addition.

Because the 16-bit value resides in X:A after the MUL instruction, the following represents my thoughts on the negation process -

COMX ; 1 cycle

NEGA ; 1 cycle

BNE *+3 ; 3 cycles

INCX ; 1 cycle

COM SUM ; 5 cycles

If my reckoning is correct, in the case of a negative coefficient, this should give a total cycle count of 53/54 for the routine.

Another possible reason for the cycle count discrepancy - when I estimate the cycle count of a sub-routine, I always allow for a JSR instruction (6 cycles) to call the routine.

Regards,

Mac

Message Edited by bigmac on 2007-06-18 01:45 PM

Re: Signed multiplication using MUL

peg — Mon, 18 Jun 2007 10:40:45 GMT

Hi,

I believe the edit time depends on the relative alignment of the planets. Whether or not pluto is included in the calculation seems to vary. The short answer - Try it!

Re: Signed multiplication using MUL

JohanF — Mon, 18 Jun 2007 13:53:15 GMT

Hi,

I have to ask the question, with the risk of looking stupid. Why to you need "COM SUM". To subtract a value from SUM, I would just take the 2-complement of the value and add to SUM, without manipulating SUM first.

What is your opinion?

/Johan