[PIC] Looking for 9-bit binary to decimal convertor

Discussion:

Dwayne Reid

2018-05-18 22:52:07 UTC

Good day to all.

I'm looking for a small, fast 9-bit binary-to-decimal conversion
routine. Somewhere between Scott Datallo's 8-bit-to-decimal and John
Payson's 16-bit-to-decimal routines.

Input range is [0..511] in binary, output in BCD or
packed-BCD. Actual input range for this project is 0..399 but I
might as well try to get the full 9-bits of range.

Short and fast if possible.

I've been looking at PICLIST.com as well as my old email archives but
haven't seen anything that is both short and fast.

Does anyone have something that they can share?

Many thanks!

dwayne
--
Dwayne Reid <***@planet.eon.net>
Trinity Electronics Systems Ltd Edmonton, AB, CANADA
780-489-3199 voice 780-487-6397 fax 888-489-3199 Toll Free
www.trinity-electronics.com
Custom Electronics Design and Manufacturing

--
http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist

Isaac M. Bavaresco

2018-05-19 16:31:22 UTC

Permalink

Dwaine,

I just changed my code to your specifications. Did not assemble or test
it, filling the gaps and debugging left as an exercise.

Cheers,

Isaac

        ; Convert an unsigned 9-bit value in v1:v0 to packed BCD in
Aux0[3:0]:Aux1[7:4]:Aux1[3:0]

        clrf    Aux0
        clrf    Aux1

        ; WARNING: Optimization for conversion of 9 bits only
        ; Shift the MSBit of the value to convert into the LSBit of the
result
        rrcf    v1,f
        rlcf    Aux1,f
        rlcf    Aux0,f

        ; WARNING: Optimization for conversion of 8 or less bits only
        ; Shift the MSBit of the value to convert into the LSBit of the
result
        ; Repeat until the result is 4 or more, or until all but the
last bit are done
        movlw    7
        movwf    Counter

LessThanEight:    rlcf    v0,f
        rlcf    Aux1,f
        rlcf    Aux0,f

        btfsc    Aux1,2
        bra    Loop

        decfsz    Counter,f
        bra    LessThanEight

LoopStart:    incf    Counter,f

Loop:        movlw    0x03
        addwf    Aux0,w
        btfsc    WREG,3,ACCESS
        movwf    Aux0
        movlw    0x30
        addwf    Aux1,w
        btfsc    WREG,7,ACCESS
        movwf    Aux1
        movlw    0x03
        addwf    Aux1,w
        btfsc    WREG,3,ACCESS
        movwf    Aux1

        rlcf    v0,f
        rlcf    v1,f
        rlcf    Aux1,f
        rlcf    Aux0,f

        decfsz    Counter,f
        bra    Loop

---
Este email foi escaneado pelo Avast antivírus.
https://www.avast.com/antivirus

--
http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/lis

David C Brown

2018-05-19 17:33:16 UTC

Permalink

Use repeated subtraction of 100 to get the top nibble then use a 100 entry
lookup table for the two lower nibbles. Fast and compact.

__________________________________________
David C Brown
43 Bings Road
Whaley Bridge
High Peak Phone: 01663 733236
Derbyshire eMail: ***@gmail.com
SK23 7ND web: www.bings-knowle.co.uk/dcb
<http://www.jb.man.ac.uk/~dcb>

*Sent from my etch-a-sketch*

Wayne,
With 9bit input and 10/11 bit output, a lookup table will be fast and
inexpensive.
Just a thought,
Jean-Paul
N1JPL

Post by Dwayne Reid
Good day to all.
I'm looking for a small, fast 9-bit binary-to-decimal conversion
routine. Somewhere between Scott Datallo's 8-bit-to-decimal and John
Payson's 16-bit-to-decimal routines.
Input range is [0..511] in binary, output in BCD or
packed-BCD. Actual input range for this project is 0..399 but I
might as well try to get the full 9-bits of range.
Short and fast if possible.
I've been looking at PICLIST.com as well as my old email archives but
haven't seen anything that is both short and fast.
Does anyone have something that they can share?
Many thanks!
dwayne
--
Trinity Electronics Systems Ltd Edmonton, AB, CANADA
780-489-3199 voice 780-487-6397 fax 888-489-3199 Toll Free
www.trinity-electronics.com
Custom Electronics Design and Manufacturing
--
http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist

--
http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist

smplx

2018-05-19 19:09:36 UTC

Permalink

Post by David C Brown
Use repeated subtraction of 100 to get the top nibble then use a 100 entry
lookup table for the two lower nibbles. Fast and compact.

Yes I was just putting together some code to show this and you beat me to
it. Also take into account that the last two bits don't change with
repeated subtraction of 100 and you can speed the whole thing up by using
8 bit arithmetic instead of 16bit.

e.g.
// y = 0;
//
// while (x >= 100)
// {
// y++;
//
// x -= 100;
// }
//
// res = (arr[y] << 8) | arr[x];
//

// // 100 base 10 = 64 base 16 = 01100100 base 2
//
// uint8 x8, pl, ph;
// int16 res;
//
// convert 10 bit number to 8 bit number
// x8 = x >> 2;
//
// ph = 0;
//
// while (x8 >= (100 >> 2))
// {
// ph++;
// x8 -= (100 >> 2);
// }
//
// will always be 8 bits
// pl = (x & 3) | (x8 << 2);
//
// 2 x 8 bit BCD packed into 16 bit variable
// res = (arr[ph] << 8) | arr[pl];
//

where arr =
0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x08, 0x09
0x10, ... 0x19,
0x20, ... 0x29,
...
0x90, ... 0x99

Regards
Sergio Masci

Post by David C Brown
__________________________________________
David C Brown
43 Bings Road
Whaley Bridge
High Peak Phone: 01663 733236
SK23 7ND web: www.bings-knowle.co.uk/dcb
<http://www.jb.man.ac.uk/~dcb>
*Sent from my etch-a-sketch*

Wayne,
With 9bit input and 10/11 bit output, a lookup table will be fast and
inexpensive.
Just a thought,
Jean-Paul
N1JPL

--
http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist

Isaac M. Bavaresco

2018-05-19 18:44:24 UTC

Permalink

A comparison is a subtraction. You could optimize by doing the
subtraction and storing the result in a different variable, then writing
the result back and repeating the loop only if it didn't overflow. This
optimization is only worthy for very low-end CPUs, but for the PIC16
(that takes six instructions to do a 16-bit subtraction) it can be very
efficient.

The table lookup is indeed very fast, but a 100 entry table is not
exactly small. Why not use the same approach for tens and units? Just
two more loops, but faster because they need to do only 8-bit subtractions.

Cheers,

Isaac

Post by smplx

Post by David C Brown
Use repeated subtraction of 100 to get the top nibble then use a 100 entry
lookup table for the two lower nibbles. Fast and compact.

Yes I was just putting together some code to show this and you beat me to
it. Also take into account that the last two bits don't change with
repeated subtraction of 100 and you can speed the whole thing up by using
8 bit arithmetic instead of 16bit.
e.g.
// y = 0;
//
// while (x >= 100)
// {
// y++;
//
// x -= 100;
// }
//
// res = (arr[y] << 8) | arr[x];
//
// // 100 base 10 = 64 base 16 = 01100100 base 2
//
// uint8 x8, pl, ph;
// int16 res;
//
// convert 10 bit number to 8 bit number
// x8 = x >> 2;
//
// ph = 0;
//
// while (x8 >= (100 >> 2))
// {
// ph++;
// x8 -= (100 >> 2);
// }
//
// will always be 8 bits
// pl = (x & 3) | (x8 << 2);
//
// 2 x 8 bit BCD packed into 16 bit variable
// res = (arr[ph] << 8) | arr[pl];
//
where arr =
0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x08, 0x09
0x10, ... 0x19,
0x20, ... 0x29,
...
0x90, ... 0x99
Regards
Sergio Masci

Wayne,
With 9bit input and 10/11 bit output, a lookup table will be fast and
inexpensive.
Just a thought,
Jean-Paul
N1JPL

--
http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist

---
Este email foi escaneado pelo Avast antivírus.
https://www.avast.com/antivirus

--
http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.ed

smplx

2018-05-19 20:49:59 UTC

Permalink

Post by Isaac M. Bavaresco
A comparison is a subtraction. You could optimize by doing the
subtraction and storing the result in a different variable, then writing
the result back and repeating the loop only if it didn't overflow. This
optimization is only worthy for very low-end CPUs, but for the PIC16
(that takes six instructions to do a 16-bit subtraction) it can be very
efficient.

Hi Isaac,

The example I gave was in two parts. The first was designed to be as
simple as possible to describe the algorithm used. The second part went on
to optimise the first by converting the 16 bit arithmetic into 8 bit
arithmetic. Yes I understand that a compare of '>=' is implmented as a
subtraction and how this can be optimised BUT the greatest benefit I was
trying to emphasize was in converting the 10 bit number to an 8 bit number
which was possible because of the range involved and the fact that the two
least significant bits could be omitted from the loop computation.

I was in the process of converting this into PIC16 assembler but then I
figured what's the point the HL code is simple enough to convert.

Regards
Sergio Masci

Post by Isaac M. Bavaresco
The table lookup is indeed very fast, but a 100 entry table is not
exactly small. Why not use the same approach for tens and units? Just
two more loops, but faster because they need to do only 8-bit subtractions.
Cheers,
Isaac

Post by smplx

Post by David C Brown
Use repeated subtraction of 100 to get the top nibble then use a 100 entry
lookup table for the two lower nibbles. Fast and compact.

Yes I was just putting together some code to show this and you beat me to
it. Also take into account that the last two bits don't change with
repeated subtraction of 100 and you can speed the whole thing up by using
8 bit arithmetic instead of 16bit.
e.g.
// y = 0;
//
// while (x >= 100)
// {
// y++;
//
// x -= 100;
// }
//
// res = (arr[y] << 8) | arr[x];
//
// // 100 base 10 = 64 base 16 = 01100100 base 2
//
// uint8 x8, pl, ph;
// int16 res;
//
// convert 10 bit number to 8 bit number
// x8 = x >> 2;
//
// ph = 0;
//
// while (x8 >= (100 >> 2))
// {
// ph++;
// x8 -= (100 >> 2);
// }
//
// will always be 8 bits
// pl = (x & 3) | (x8 << 2);
//
// 2 x 8 bit BCD packed into 16 bit variable
// res = (arr[ph] << 8) | arr[pl];
//
where arr =
0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x08, 0x09
0x10, ... 0x19,
0x20, ... 0x29,
...
0x90, ... 0x99
Regards
Sergio Masci

Wayne,
With 9bit input and 10/11 bit output, a lookup table will be fast and
inexpensive.
Just a thought,
Jean-Paul
N1JPL

--
http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist

---
Este email foi escaneado pelo Avast antivÃrus.
https://www.avast.com/antivirus
--
http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist

Forrest Christian (List Account)

2018-05-19 14:24:29 UTC

Permalink

Which processor?

If it has a 8x8 hardware multiplier there might be some options using it.
I'd have to spend some time figuring out how to leverage it since it only
multiplies. Often you can get around this by a multiply by a constant and
a shift. The constant is chosen such that the result is an even power of
two too high, which results in your division result being in the most
significant bits, and a fractional remainder being in the least
significant bits.

--
http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist

Forrest Christian (List Account)

2018-05-19 14:59:35 UTC

Permalink

A quick follow up.

Spent a few minutes looking for an appropriate multiplication constant and
didn't find one.

A Google search for a div10 algorithm returned this page:
https://electronics.stackexchange.com/questions/12618/fastest-way-to-get-integer-mod-10-and-integer-divide-10

It contains several bcd conversion routines. The most interesting one to
me is the double dabble algorithm.

On Sat, May 19, 2018, 7:24 AM Forrest Christian (List Account) <

Post by Forrest Christian (List Account)
Which processor?
If it has a 8x8 hardware multiplier there might be some options using it.
I'd have to spend some time figuring out how to leverage it since it only
multiplies. Often you can get around this by a multiply by a constant and
a shift. The constant is chosen such that the result is an even power of
two too high, which results in your division result being in the most
significant bits, and a fractional remainder being in the least
significant bits.

--
http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist

Isaac M. Bavaresco

2018-05-19 15:14:45 UTC

Permalink

Hi,

The routine below for PIC18F in extended mode implements the 'utoa' and
'itoa' functions. It may seem complicated but is indeed very simple.
Most of the complexity is due to the fact that it is reentrant and uses
indexed memory accesses.

The algorithm adds 3 to each nibble of the result only if the resulting
nibble is 8 or higher, then shifts the MSBit of the value to be
converted into the LSBit of the result, until all the bits are done.

<pre>
<code>
;===============================================================================
; Copyright (c) 2008, Isaac Marino Bavaresco
; All rights reserved
; ***@yahoo.com.br
;===============================================================================
#include "P18CXXX.INC"
;===============================================================================
        radix    decimal
;===============================================================================
STDLIB        code
;===============================================================================
s        equ    0
v        equ    2
Aux        equ    6

#define    NotZero    0
;===============================================================================
; char *utoa( auto unsigned short v, auto char RAM *s );

        global    utoa

utoa:        bsf    STATUS,C,ACCESS        ; Unsigned = 1;
        bra    Common
;===============================================================================
; char *itoa( auto signed short v, auto char RAM *s );

        global    itoa

itoa:        bcf    STATUS,C,ACCESS        ; Unsigned = 0;
;===============================================================================
Common:        movff    FSR2L,POSTINC1        ; *(WORD*)FSR1++ = FSR2;
        movff    FSR2H,POSTINC1

        movff    FSR1L,FSR2L        ; FSR2        = FSR1
        movff    FSR1H,FSR2H

        subfsr    2,6            ; FSR2        -= 4;
        addfsr    1,3
        ;---------------------------------------------------------------
        movf    [s+0],w            ; PROD = FSR0    = s;
        movwf    FSR0L,ACCESS
        movwf    PRODL,ACCESS
        movf    [s+1],w
        movwf    FSR0H,ACCESS
        movwf    PRODH,ACCESS
        ;---------------------------------------------------------------
        btfss    STATUS,C,ACCESS        ; if( !Unsigned && v < 0 )
        btfss    [v+1],7            ;     {
        bra    Positive

Negative:    movlw    '-'            ;     *s++ = '-'
        movwf    POSTINC0,ACCESS

        subwf    WREG,f,ACCESS        ;     v = -v; }
        subfwb    [v+0],f
        subfwb    [v+1],f
        ;
        ;
        ;---------------------------------------------------------------
Positive:    clrf    [Aux+0]
        clrf    [Aux+1]
        clrf    [Aux+2]
        ;
        ;

        movlw    15
        movwf    TBLPTRL,ACCESS

        ;----------------------

LessThanEight:    rlcf    [v+0],f                ; 3
        rlcf    [v+1],f                ; 4
        ;
        ;
        ;
        ;
        rlcf    [Aux+2],f            ; 9
        rlcf    [Aux+1],f            ; 10
        rlcf    [Aux+0],f            ; 11

        btfsc    [Aux+2],2
        bra    Loop

        decfsz    TBLPTRL,f,ACCESS        ; 12
        bra    LessThanEight            ; 13/14

        ;----------------------

LoopStart:    incf    TBLPTRL,f,ACCESS

Loop:        movlw    3                ; 1
        movwf    TBLPTRH,ACCESS        ; 0

DigitLoop:    movlw    0x03            ; 1
        addwf    [Aux+0],w        ; 2
        btfsc    WREG,3,ACCESS        ; 3
        movwf    [Aux+0]            ; 4
        movlw    0x30            ; 5
        addwf    [Aux+0],w        ; 6
        btfsc    WREG,7,ACCESS        ; 7
        movwf    [Aux+0]            ; 8

        addfsr    2,1            ; 9
        decfsz    TBLPTRH,f,ACCESS    ; 10
        bra    DigitLoop        ; 11/12
        subfsr    2,3                ; 2

        rlcf    [v+0],f                ; 3
        rlcf    [v+1],f                ; 4
        ;
        ;
        ;
        ;
        rlcf    [Aux+2],f            ; 9
        rlcf    [Aux+1],f            ; 10
        rlcf    [Aux+0],f            ; 11

        decfsz    TBLPTRL,f,ACCESS        ; 12
        bra    Loop                ; 13/14
        ;---------------------------------------------------------------
        bcf    TBLPTRH,NotZero,ACCESS
        movlw    3
        movwf    TBLPTRL            ; 0

Tens:        swapf    [Aux+0],w        ; 1
        andlw    0x0f            ; 2
        btfss    TBLPTRH,NotZero,ACCESS    ; 3
        bz    Units            ; 4
        bsf    TBLPTRH,NotZero,ACCESS    ; 5
        addlw    '0'            ; 6
        movwf    POSTINC0,ACCESS        ; 7

Units:        movf    [Aux+0],w        ; 8
        andlw    0x0f            ; 9
        btfss    TBLPTRH,NotZero,ACCESS    ; 10
        bz    Next            ; 11
        bsf    TBLPTRH,NotZero,ACCESS    ; 12
        addlw    '0'            ; 13
        movwf    POSTINC0,ACCESS        ; 14

Next:        addfsr    2,1            ; 15
        decfsz    TBLPTRL,f,ACCESS    ; 16
        bra    Tens            ; 17/18

        movlw    '0'
        btfss    TBLPTRH,NotZero,ACCESS
        movwf    POSTINC0,ACCESS

        clrf    INDF0,ACCESS
        ;---------------------------------------------------------------
Epilog:        subfsr    1,4
        movff    POSTDEC1,FSR2H
        movff    INDF1,FSR2L
        return    0
;===============================================================================
        end
;===============================================================================
</code>
</pre>

---
Este email foi escaneado pelo Avast antivírus.
https://www.avast.com/antivirus

--
http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailma