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
hugoboss
Efficient algorithm for 2x uint8 to 4-bytes BCD array?
Author
Message
hugoboss
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.
indianajones11 
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 .
hugoboss
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
hugoboss
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?
Levenkay 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;
}
}
indianajones11 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:
Besides its library , then WHY hang with Bascom ?!
...the BASCOM library does it in a whopping 4600 cycles through strings.
Last Edited: Sun. Jun 26, 2011 - 09:12 PM
hugoboss
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:Besides its library , then WHY hang with Bascom ?!...the BASCOM library does it in a whopping 4600 cycles through strings.
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.
Levenkay 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;
}
indianajones11 Hugo, check my edit .
hugoboss
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...
zbaird
Level: Raving Lunatic
Joined: Sun. Aug 13, 2006
Posts: 7438 View posts
Location: Bellingham, WA - USA
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.
hugoboss
indianajones11 What does the code for it look like and how many bytes ?
hugoboss
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.
hzrnbgy
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
larryvc
hzrnbgy, Wow, now that is what I call "service with a smile". Nice. :)
hzrnbgy
gotta exercise the brain muscles once in a while :)
theusch 
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
larryvc
Hi Lee,
That certainly was a short read. :wink: I found it quite interesting.
indianajones11 Hugo, how many clk now for the routine, was 910 clk and now... ( I mistyped before when I asked for bytes )
hugoboss
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...
sparrow2
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.
hugoboss
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!
indianajones11 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.
Last Edited: Tue. Jun 28, 2011 - 08:30 AM
sparrow2
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.
danni for small and fast code use the subtraction method:
#includeuint8_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
hugoboss
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.