Efficient algorithm for 2x uint8 to 4-bytes BCD array?

Go To Last Post
28 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Suppose you have 2 unsigned 8-bits integers that you want to convert into a 4-bytes BCD array, how would you go about it in the most CPU-efficient way?

Example:
Turn:
uint8_A = 45
uint8_B = 15
Into:
BCDarray(4) = 4, 5, 1, 5

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I was thinking something along the lines of:

BCDarray(1) = uint8_a AND &H0F
BCDarray(2) = uint8_a AND &HF0
BCDarray(3) = uint8_b AND &H0F
BCDarray(4) = uint8_b AND &HF0

But it does not work as expected, and I haven't put much time on it yet.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I'd think you have to think in hex, not decimal. What if the number is 3 digits ( 255 ) ? Then BCDA[0] = 0x0F and BCDA[1] = 0x0F .

1) Studio 4.18 build 716 (SP3)
2) WinAvr 20100110
3) PN, all on Doze XP... For Now
A) Avr Dragon ver. 1
B) Avr MKII ISP, 2009 model
C) MKII JTAGICE ver. 1

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I forgot to mention but A and B will never be above 99 and 59 respectively. It's time. I convert the ticks count from a timer at 1Hz interrupts into minutes and seconds with A=(ticks \ 60) and B=(ticks mod 60). I just need to extract the digits in a quick way, the BASCOM library does it in a whopping 4600 cycles through strings.

Last Edited: Sun. Jun 26, 2011 - 07:53 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

And yes I see the problem with my previous approach... Do you have another suggestion? Maybe I should rotate the variable right by 4 and always mask the lower nibble?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Do the two integers represent two separate numbers from 0 to 255, or one composite number from 0 to 65535? Either way, it seems like their base-ten representations would need six decimal digits, rather than four.

But judging from what you're trying to do, the "unsigned 8-bit integers" are ALREADY in BCD format; they're just what's called "packed BCD", and you just want to un-pack them. This is written more for (hopefully) readability than efficiency, but I think it's more like what you seem to want:

void unpacker (uint8_t unpacked[4], uint8_t packed[2])
{
    uint8_t *inhale = packed;
    uint8_t *exhale = unpacked;

    for (int8_t loop = 2; 0 <= --loop; ) {
        uint8_t temp = *(inhale++);
        *(exhale++) = temp & 0xf;
        *(exhale++) = temp >> 4;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Then it has to be a decimal think . Shifting 99 won't give you two 9s. BCDA[0] = a/10; , etc. , is all I see, in asm ( for most efficient ). Can Bascom link to a asm file ?

Maybe a struct ( pointing to a GPIOR, so would use IN/OUT ) with 2 bytes and each nibble bit field would store digit. Then you could do your increments on each nibble and display by just referencing. You could use four if statements and masking to handle the digits... Overall it might be less code than ( what you do now to keep time + what it takes to isolate digits ( /, % )).

Quote:
...the BASCOM library does it in a whopping 4600 cycles through strings.
Besides its library , then WHY hang with Bascom ?!

1) Studio 4.18 build 716 (SP3)
2) WinAvr 20100110
3) PN, all on Doze XP... For Now
A) Avr Dragon ver. 1
B) Avr MKII ISP, 2009 model
C) MKII JTAGICE ver. 1

Last Edited: Sun. Jun 26, 2011 - 09:12 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

indianajones11 wrote:
Then it has to be a decimal think . Shifting 99 won't give you two 9s. BCDA[0] = a/10; , etc. , is all I see, in asm ( for most efficient ). Can Bascom link to a asm file ?

Quote:
...the BASCOM library does it in a whopping 4600 cycles through strings.
Besides its library , then WHY hang with Bascom ?!

BASCOM can mix and match basic and ASM at will, and well the BASCOM way involves STR() which turns a number into it's string representation, just a bit of a walk around...

Think what you will man, BASCOM is great for rapid app development. I just started this firmware yesterday and about 75% of it is done.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Oh, OK, so your numbers aren't already BCD; they're just guaranteed to be less than 100. Well, then if it's just a matter of converting a 0..59 value into "tens" and "units", then:

void decomposeBaseSixty(uint8_t *destinatation, uint8_t zeroToFiftynine)
{
    *(destination++) = zeroToFiftynine % 10;
    *(destination++) = zeroToFiftynine / 10;
}
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Hugo, check my edit .

1) Studio 4.18 build 716 (SP3)
2) WinAvr 20100110
3) PN, all on Doze XP... For Now
A) Avr Dragon ver. 1
B) Avr MKII ISP, 2009 model
C) MKII JTAGICE ver. 1

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Ah yes you got it! This works fine:

      Isr_1hz_minutes = Isr_1hz_ticks \ 60
      Isr_1hz_seconds = Isr_1hz_ticks Mod 60
      Isr_1hz_bcdtime(1) = Isr_1hz_minutes \ 10
      Isr_1hz_bcdtime(2) = Isr_1hz_minutes Mod 10
      Isr_1hz_bcdtime(3) = Isr_1hz_seconds \ 10
      Isr_1hz_bcdtime(4) = Isr_1hz_seconds Mod 10

910 cycles! Now can we do better?

EDIT: Your idea is interesting indiana, to replace the divisions by additions. I will give this a try...

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

One thing to consider in problems like this is backing up a step. Converting a "finished" time value to something else is one way to do it, and is what has been done above.

Provided your program builds that time value in the first place, another approach is to do the conversion as you accumulate the time. So, let's say you're getting an interrupt every second. Rather than increment a seconds counter to 59, then zero and increment a minutes count (to a max of 59), etc., try the following:

Increment the sec1 count to 9, then zero and increment the sec2 count. When sec1 == 9 and sec2 == 5 on increment, zero both and increment min1. And so on. In other words, build the BCD rather than binary in the first place.

If you need the actual binary values for something else this won't help, but if display is all you need it may be an easier approach.

Chuck Baird

"I wish I were dumber so I could be more certain about my opinions. It looks fun." -- Scott Adams

http://www.cbaird.org

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Yay my display update routine works! :)

Attachment(s): 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

What does the code for it look like and how many bytes ?

1) Studio 4.18 build 716 (SP3)
2) WinAvr 20100110
3) PN, all on Doze XP... For Now
A) Avr Dragon ver. 1
B) Avr MKII ISP, 2009 model
C) MKII JTAGICE ver. 1

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Well the whole project is 325 lines of BASIC including comments if that is what you are asking, maybe 1/3 of it is for the AT25 dataflash routines, rest is hardware setup, declarations, utility routines, and ISRs.

The actual display update is this:

Sub Display_update()                                             ' Update the displays and cycle through the five anode phases.
                                                                 ' ------------------------------------------------------------
   ' Increment (and reset) the display phase counter as needed.
   Incr Display_phase
   If Display_phase = 6 Then Display_phase = 1

   ' Update the anodes (PORTF) for the current phase.
   Display_anodes = Display_phasebyte(display_phase)

   ' Update the cathodes on the two displays to display their current digit as set by their respective clocks.
   ' If this is phase 5, light up only the two dots for the semicolon.
   If Display_phase = 5 Then
      If Active_team_toggle = 1 Then
         Display_red_cathodes = &B11111000
         Display_yellow_cathodes = &B11111100
      Else
         Display_red_cathodes = &B11111100
         Display_yellow_cathodes = &B11111000
      End If
   Else
      Temp_bcd = Isr_1hz_bcdtime_red(display_phase)
      If Temp_bcd = 0 Then Temp_bcd = 10
      Display_red_cathodes = Display_number(temp_bcd)

      Temp_bcd = Isr_1hz_bcdtime_yellow(display_phase)
      If Temp_bcd = 0 Then Temp_bcd = 10
      Display_yellow_cathodes = Display_number(temp_bcd)
   End If

End Sub

Which is run at 14.4KHz from a timer. Probably going to move it to react to a flag in the main loop at approximately the same speed to keep the ISR short, and give priority to the sound playback interrupt.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

for your very specific case, this assembly code should yield you around 12 to 40 cycles max, depending on which number you are converting (12 for anything less than 10, 40 for anything more than 90)

LDI R16, any number between 0 and 99
RCALL convert
R17 -> ones digit
R18 -> tens digit

;R16 for the original number
;R17 'ones' digit
;R18 'tens' digit

convert:
CPI R16, 10   ;0 to 9
BRSH comp_20
LDI R18, 0
MOV R17, R16
SUBI R17, 0
RET

comp_20:			;10 to 19
CPI R16, 20
BRSH comp_30
LDI R18, 1
MOV R17, R16
SUBI R17, 10
RET

comp_30:			;20 to 29
CPI R16, 30
BRSH comp_40
LDI R18, 2
MOV R17, R16
SUBI R17, 20
RET

comp_40:			;30 to 39
CPI R16, 40
BRSH comp_50
LDI R18, 3
MOV R17, R16
SUBI R17, 30
RET

comp_50:			;40 to 49
CPI R16, 50
BRSH comp_60
LDI R18, 4
MOV R17, R16
SUBI R17, 40
RET

comp_60:			;50 to 59
CPI R16, 60
BRSH comp_70
LDI R18, 5
MOV R17, R16
SUBI R17, 50
RET

comp_70:			;60 to 69
CPI R16, 70
BRSH comp_80
LDI R18, 6
MOV R17, R16
SUBI R17, 60
RET

comp_80:			;70 to 79
CPI R16, 80
BRSH comp_90
LDI R18, 7
MOV R17, R16
SUBI R17, 70
RET

comp_90:			;80 to 89
CPI R16, 90
BRSH comp_100
LDI R18, 8
MOV R17, R16
SUBI R17, 80
RET

comp_100:			;90 to 99
CPI R16, 100
BRSH comp_invalid
LDI R18, 9
MOV R17, R16
SUBI R17, 90
RET

comp_invalid:
LDI R18, invalid_identifier
LDI R17, invalid_identifier
RET
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

hzrnbgy, Wow, now that is what I call "service with a smile". Nice. :)

"I may make you feel but I can't make you think" - Jethro Tull - Thick As A Brick

"void transmigratus(void) {transmigratus();} // recursio infinitus" - larryvc

"It's much more practical to rely on the processing powers of the real debugger, i.e. the one between the keyboard and chair." - JW wek3

"When you arise in the morning think of what a privilege it is to be alive: to breathe, to think, to enjoy, to love." -  Marcus Aurelius

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

gotta exercise the brain muscles once in a while :)

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:

910 cycles! Now can we do better?


Wow--doncha y'all know that at AVRfreaks every possible AVR-related question has been raised, discussed, and consensus reached?

https://www.avrfreaks.net/index.p...

And, over the years, many other threads. Search them out.

Lee

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Hi Lee,

That certainly was a short read. :wink: I found it quite interesting.

"I may make you feel but I can't make you think" - Jethro Tull - Thick As A Brick

"void transmigratus(void) {transmigratus();} // recursio infinitus" - larryvc

"It's much more practical to rely on the processing powers of the real debugger, i.e. the one between the keyboard and chair." - JW wek3

"When you arise in the morning think of what a privilege it is to be alive: to breathe, to think, to enjoy, to love." -  Marcus Aurelius

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Hugo, how many clk now for the routine, was 910 clk and now... ( I mistyped before when I asked for bytes )

1) Studio 4.18 build 716 (SP3)
2) WinAvr 20100110
3) PN, all on Doze XP... For Now
A) Avr Dragon ver. 1
B) Avr MKII ISP, 2009 model
C) MKII JTAGICE ver. 1

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Well I am still trying some things out, I have changed things up a bit, and now the display updates asynchronously. I am still using the divide by 10 method, but I see now that I can skip the second divide by reading the remainder directly after the division. Will report later...

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

On an mega AVR (with HW mul) it can be done in 14 clk by using mul with 1/x (the last code in Lee's link, last part). but I think it will take about 30-35 clk in one without, but it's still fast.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0
   Isr_1hz_minutes = Isr_1hz_ticks_red \ 60
   Isr_1hz_seconds = Peek(16)
   Isr_1hz_bcdtime_red(1) = Isr_1hz_minutes \ 10
   Isr_1hz_bcdtime_red(2) = Peek(24)
   Isr_1hz_bcdtime_red(3) = Isr_1hz_seconds \ 10
   Isr_1hz_bcdtime_red(4) = Peek(24)

277 cycles :) Skipping the second division and fetching the remainder directly goes a long way!

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Way to get it down ! But your code is NOT according to what your stated goal in your OP . Additions and IF statements will be.

1) Studio 4.18 build 716 (SP3)
2) WinAvr 20100110
3) PN, all on Doze XP... For Now
A) Avr Dragon ver. 1
B) Avr MKII ISP, 2009 model
C) MKII JTAGICE ver. 1

Last Edited: Tue. Jun 28, 2011 - 08:30 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

If you need to display it fast then have a byte for each digit and make a digit counter with level check for
sec ==10,
10sec==6,
min ==10,
10min==6,
hour ==10
10hour==3 (just more than 2)
and then make a 24 check.
then 9 out of 10 times it will only be ?? 10-20 clk.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

for small and fast code use the subtraction method:

#include


uint8_t tens, ones;


void split_number( int8_t num )  // num = 0 .. 99
{
  uint8_t i = -1;

  do{
    i++;
    num -= 10;
  }while( num >= 0 );

  tens = i;
  ones = num + 10;
}

Peter

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

It's fine at the moment really I run it once a second, I moved it out of the display routine, and the display matrix is average 116 cycles per phase, refreshing every 69.4uS.