BCD Mulitplication 8Bit BCD * 20Bit BCD

[zenta]

Hello,

I have to create a subroutine, which multiply 8Bit packed BCD(2 Digits)  with 20Bit packed BCD. (5 Digits). I don't know, which is the best possibility for code optimisation and speed optimisation. (...let say the best of all possibilities...)
Ok, on the one hand you could make a multiplication table of 81 - 100 Bytes. But this will take a lot of space in ROM.
Is there a fast and short algorithm for the HCS08?

Thank you for your help,

best regards
zenta



Message Edited by zenta on 2009-02-13 11:06 AM

[bigmac]

Hello Zenta,

Since you are referring to a sub-routine, I assume that you are using assembly code.  Is this correct?  In general, lookup table methods are usually speedier than algorithmic methods.  You do not say whether the multiplication result needs to be in packed BCD format, or whether a binary value would suffice.  You also do not indicate the minimum speed required by your application.

One possible method is to convert the two packed BCD quantities to binary, do the multiplication (using hardware multiply), and then to optionally convert the binary result back to packed BCD.  Using this method, the assembly sub-routines that I tried required the following resources -

Binary result:  150 bytes and 302 cycles
Packed BCD result:  Add 74 bytes and 235 cycles to the above figures.

If these figures are adequate for your application, I can post the code that I tested.

Regards,
Mac

[PeterHouse]

Hey Mac,

Stop teasing the rest of us and post the code.

I would sure like to see what you have come up with for my own curiosity!

Thanks,

Peter House

[bigmac]

Hello,

The following assembly sub-routines seem to give the correct result when tested under full chip simulation.  The first sub-routine requires that the 5-digit packed BCD multiplicand be loaded to the first three bytes of BUF, right justified.  ACC should contain the 2-digit multiplier.  The result of the multiplication is then presented as a 24-bit binary value within BUF.

;**************************************************************
; BCD MULTIPLY
;**************************************************************
; On entry, First 3-bytes of BUF contains 5-digit packed BCD
; value, right aligned.
; ACC = packed BCD (2-digit) multiplier value.
; On exit, first 3-bytes of BUF contain 24-bit result of the
; multiplication.

BCDMULT:  JSR    BCDCONV        ; Convert packed BCD byte to binary
          PSHA                  ; Multiplier (binary) value 0-99
          AIS    #-3            ; Create additional space on stack

          ; Packed BCD (5-digit) to binary
          LDA    BUF            ; MS byte ($00- $09)
          AND    #$0F           ; Ensure high nybble is zero
          LDX    #100
          MUL
          STA    3,SP
          LDA    BUF+1          ; Second byte ($00-$99)
          JSR    BCDCONV        ; Convert packed BCD byte to binary
          ADD    3,SP
          STA    3,SP
          BCC    *+3            ; Skip next if no carry
          INCX
          STX    2,SP

          LDX    #100
          MUL
          STA    3,SP
          LDA    BUF+2          ; LS byte ($00-$99)
          JSR    BCDCONV        ; Convert packed BCD byte to binary
          ADD    3,SP
          STA    3,SP
          BCC    *+3            ; Skip next if no carry
          INCX
          STX    BUF            ; Temporary storage
          LDA    2,SP
          LDX    #100
          MUL
          ADD    BUF
          STA    2,SP
          BCC    *+3            ; Skip next if no carry
          INCX
          STX    1,SP

          ; Multiplication process
          LDX    4,SP           ; Multiplier (binary)
          LDA    3,SP
          MUL
          STA    BUF+2
          STX    3,SP
          LDA    2,SP
          LDX    4,SP           ; Multiplier (binary)
          MUL
          ADD    3,SP
          STA    BUF+1
          BCC    *+4            ; Skip next if no carry
          AIX    #1
          STX    3,SP
          LDA    1,SP
          LDX    4,SP           ; Multiplier (binary)
          MUL
          ADD    3,SP
          STA    BUF
          AIS    #4             ; Adjust stack pointer
          RTS

; CONVERT PACKED BCD BYTE TO BINARY
; On entry, ACC = Packed BCD byte
; On exit, ACC = Binary value

BCDCONV:  PSHX                  ; Save current value
          PSHA
          NSA
          AND    #$0F           ; High nybble
          LDX    #10
          MUL
          PSHA
          LDA    2,SP
          AND    #$0F           ; Low nybble
          ADD    1,SP
          AIS    #2             ; Adjust stack pointer
          PULX                  ; Restore previous value
          RTS

The following sub-routine takes the 24-bit value within BUF, and converts it back to packed BCD, this time within the first four byes of BUF.

;**************************************************************
; 24-BIT BINARY TO 8-DIGIT BCD CONVERSION
;**************************************************************
; On entry, first three bytes of BUF contain binary number.
; On exit, the four bytes of BUF contain packed BCD data.

CONVERT:  ; Convert to four byte values within range 0 - 100
          LDHX   #100           ; Set up divisor & clear H-reg
          LDA    BUF
          DIV
          STA    BUF
          LDA    BUF+1
          DIV
          STA    BUF+1
          LDA    BUF+2
          DIV
          STA    BUF+2
          PSHH                  ; Store remainder to stack

          LDA    BUF
          PSHA
          PULH
          LDA    BUF+1
          DIV
          STA    BUF+1
          LDA    BUF+2
          DIV
          STA    BUF+2
          PSHH                  ; Store remainder to stack

          LDA    BUF+1
          PSHA
          PULH
          LDA    BUF+2
          DIV
          PSHH                  ; Store remainder to stack

          LDX    #10
          BSR    BCDPACK        ; Convert to packed BCD
          STA    BUF
          PULA
          BSR    BCDPACK        ; Convert to packed BCD
          STA    BUF+1
          PULA
          BSR    BCDPACK        ; Convert to packed BCD
          STA    BUF+2
          PULA
          BSR    BCDPACK        ; Convert to packed BCD
          STA    BUF+3
          RTS

* Convert byte value to packed BCD
; On entry, ACC = byte value and X = 10
; On exit, ACC = packed BCD

BCDPACK:  CLRH
          DIV
          NSA
          PSHH
          ORA    1,SP
          AIS    #1             ; Adjust stack pointer
          RTS

Regards,
Mac

[zenta]

Hello mac,

thank you for your fast response.

I needed to multiply one 5-digit packed BCD with one 2-digit packed BCD. The result has to be max. 5-digit packed BCD, too. My subroutine should be in assembler.

A minimal speed for my application does not exist. The main point is to save current consumption. And RUN-Mode should be short.

But all in all, I think the code you have post, works very well and is short enough.

Really thank you for your help,

best regards
zenta