Binary coded decimal: Difference between revisions
Line 318: | Line 318: | ||
=== using daa and das === |
=== using daa and das === |
||
This time we'll supply the arguments in hex/BCD. |
This time we'll supply the arguments in hex/BCD. |
||
Note the result is limited to 16 bits plus one carry bit here. |
Note the result is limited to 16 bits plus one carry bit here.<br> |
||
The aaa, |
The aaa, aas, aam, and aad instructions are also available. |
||
Same output as above, of course |
Same output as above, of course |
||
<!--<lang Phix>--> |
<!--<lang Phix>--> |
||
Line 350: | Line 350: | ||
<span style="color: #000000;">test2</span><span style="color: #0000FF;">(</span><span style="color: #000000;">#99</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'+'</span><span style="color: #0000FF;">)</span> |
<span style="color: #000000;">test2</span><span style="color: #0000FF;">(</span><span style="color: #000000;">#99</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'+'</span><span style="color: #0000FF;">)</span> |
||
<!--</lang>--> |
<!--</lang>--> |
||
=== hll bit fiddling === |
=== hll bit fiddling === |
||
With routines to convert between decimal and bcd, same output as above, of course. |
With routines to convert between decimal and bcd, same output as above, of course. |
Revision as of 20:25, 15 July 2022
Binary-Coded Decimal (or BCD for short) is a method of representing decimal numbers by storing what appears to be a decimal number but is actually stored as hexadecimal. Many CISC CPUs (e.g. X86 Assembly have special hardware routines for displaying these kinds of numbers.) On low-level hardware, such as 7-segment displays, binary-coded decimal is very important for outputting data in a format the end user can understand.
- Task
Use your language's built-in BCD functions, OR create your own conversion function, that converts an addition of hexadecimal numbers to binary-coded decimal. You should get the following results with these test cases:
- 0x19 + 1 = 0x20
- 0x30 - 1 = 0x29
- 0x99 + 1 = 0x100
- Bonus Points
Demonstrate the above test cases in both "packed BCD" (two digits per byte) and "unpacked BCD" (one digit per byte).
6502 Assembly
Doesn't work with: Ricoh 2A03
The 6502 is a bit different in that it has a special operating mode where all addition and subtraction is handled as binary-coded decimal. Like the 68000, this must be invoked ahead of time, rather than using the Intel method of doing the math normally and then correcting it after the fact. (This special operating mode won't work on the aforementioned Ricoh 2A03, which performs math in "normal" mode even if the decimal flag is set.)
<lang 6502asm>sed ;set decimal flag; now all math is BCD lda #$19 clc adc #1 cld ;chances are, PrintHex won't work properly when in decimal mode. JSR PrintHex ;unimplemented print routine JSR NewLine
sed lda #$30 sec sbc #1 cld jsr PrintHex JSR NewLine
sed lda #$99 clc adc #1 pha lda #0 adc #0 ;adds the carry cld jsr PrintHex pla jsr PrintHex jsr NewLine rts ;return to basic</lang>
- Output:
20 29 0100
68000 Assembly
The 68000 has special mathematics commands for binary-coded decimal. However, they only work at byte length, and cannot use immediate operands. Even adding by 1 this way requires you to load 1 into a register first. <lang 68000devpac> MOVEQ #$19,D0 MOVEQ #1,D1 MOVEQ #0,D2
ABCD D1,D0 JSR PrintHex JSR NewLine
MOVEQ #$30,D0 SBCD D1,D0 JSR PrintHex JSR NewLine
MOVE.B #$99,D0 ABCD D1,D0 ;D0 has rolled over to 00 and set both the extend and carry flags. ADDX D2,D2 ;add the extend flag which was set by the above operation ;this can't use immediate operands either so we're using D2 which we set to zero at the start.
MOVE.L D0,D3 ;back up the output since PrintHex takes D0 as its argument. MOVE.L D2,D0 ;print the 01 JSR PrintHex MOVE.L D3,D0 ;then the 00 JSR PrintHex
jmp *</lang>
- Output:
20 29 0100
J
Here, we represent hexadecimal numbers using J's constant notation, and to demonstrate bcd we generate results in that representation:
<lang J> bcd=: &.((10 #. 16 #.inv ". ::]) :. ('16b',16 hfd@#. 10 #.inv ]))
16b19 +bcd 1
16b20
16b30 -bcd 1
16b29
16b99 +bcd 1
16b100
(16b99 +bcd 1) -bcd 1
16b99</lang>
Note that we're actually using a hex representation as an intermediate result here. Technically, though, sticking with built in arithmetic and formatting as decimal, but gluing the '16b' prefix onto the formatted result would have been more efficient. And that says a lot about bcd representation. (The value of bcd is not efficiency, but how it handles edge cases. Consider the decimal IEEE 754 format as an example where this might be considered significant. There are other ways to achieve those edge cases -- bcd happens to be relevant when building the mechanisms into hardware.)
For reference, here are decimal and binary representations of the above numbers:
<lang J> (":,_16{.' '-.~'2b',":@#:) 16b19 25 2b11001
(":,_16{.' '-.~'2b',":@#:) 16b20
32 2b100000
(":,_16{.' '-.~'2b',":@#:) 16b29
41 2b101001
(":,_16{.' '-.~'2b',":@#:) 16b30
48 2b110000
(":,_16{.' '-.~'2b',":@#:) 16b99
153 2b10011001
(":,_16{.' '-.~'2b',":@#:) 16b100
256 2b100000000
2b11001
25
NB. ...</lang>
Julia
Handles negative and floating point numbers (but avoid BigFloats due to very long decimal places from binary to decimal conversion). <lang ruby>const nibs = [0b0, 0b1, 0b10, 0b11, 0b100, 0b101, 0b110, 0b111, 0b1000, 0b1001]
"""
function bcd_decode(data::Vector{codeunit}, sgn, decimalplaces; table = nibs)
Decode BCD number
bcd: packed BCD data as vector of bytes sgn: sign(positive 1, negative -1, zero 0) decimalplaces: decimal places from end for placing decimal point (-1 if none) table: translation table, defaults to same as nibble (nibs table)
""" function bcd_decode(bcd::Vector{UInt8}, sgn, decimalplaces = 0; table = nibs)
decoded = 0 for (i, byt) in enumerate(bcd) decoded = decoded * 10 + table[byt >> 4 + 1] decoded = decoded * 10 + table[byt & 0b1111 + 1] end return decimalplaces == 0 ? sgn * decoded : sgn * decoded / 10^decimalplaces
end
"""
function bcd_encode(number::Real; table::Vector{UInt8} = nibs)
Encode real number as BCD.
`number`` is in native binary formats `table`` is the table used for encoding the nibbles of the decimal digits, default `nibs` Returns: BCD encoding vector of UInt8, number's sign (1, 0 -1), and position of decimal point
""" function bcd_encode(number::Real; table::Vector{UInt8} = nibs)
if (sgn = sign(number)) < 0 number = -number end s = string(number) if (exponentfound = findlast(ch -> ch in ['e', 'E'], s)) != nothing expplace = parse(Int, s[exponentfound+1:end]) s = s[begin:exponentfound-1] else expplace = 0 end if (decimalplaces = findfirst(==('.'), s)) != nothing s = s[begin:decimalplaces-1] * s[decimalplaces+1:end] decimalplaces = length(s) - decimalplaces + 1 decimalplaces -= expplace else decimalplaces = -expplace end len = length(s) if isodd(len) s = "0" * s len += 1 end return [table[s[i+1]-'0'+1] | (table[s[i]-'0'+1] << 4) for i in 1:2:len-1], sgn, decimalplaces
end
"""
function bcd_encode(number::Integer; table::Vector{UInt8} = nibs)
Encode integer as BCD.
`number`` is in native binary formats `table`` is the table used for encoding the nibbles of the decimal digits, default `nibs` Returns: Tuple containg two values: a BCD encoded vector of UInt8 and the number's sign (1, 0 -1)
""" function bcd_encode(number::Integer; table::Vector{UInt8} = nibs)
if (sgn = sign(number)) < 0 number = -number end s = string(number) len = length(s) if isodd(len) s = "0" * s len += 1 end return [table[s[i+1]-'0'+1] | (table[s[i]-'0'+1] << 4) for i in 1:2:len-1], sgn
end
for test in [1, 2, 3, -9876, 10, 12342436]
enc = bcd_encode(test, table = nibs) dec = bcd_decode(enc..., table = nibs) println("$test encoded is $enc, decoded is $dec")
end
for test in [-987654.321, -10.0, 9.9999, 123424367.0089]
enc = bcd_encode(test, table = nibs) dec = bcd_decode(enc..., table = nibs) println("$test encoded is $enc, decoded is $dec")
end
</lang>
- Output:
1 encoded is (UInt8[0x01], 1), decoded is 1 2 encoded is (UInt8[0x02], 1), decoded is 2 3 encoded is (UInt8[0x03], 1), decoded is 3 -9876 encoded is (UInt8[0x98, 0x76], -1), decoded is -9876 10 encoded is (UInt8[0x10], 1), decoded is 10 12342436 encoded is (UInt8[0x12, 0x34, 0x24, 0x36], 1), decoded is 12342436 -987654.321 encoded is (UInt8[0x09, 0x87, 0x65, 0x43, 0x21], -1.0, 3), decoded is -987654.321 -10.0 encoded is (UInt8[0x01, 0x00], -1.0, 1), decoded is -10.0 9.9999 encoded is (UInt8[0x09, 0x99, 0x99], 1.0, 4), decoded is 9.9999 1.234243670089e8 encoded is (UInt8[0x01, 0x23, 0x42, 0x43, 0x67, 0x00, 0x89], 1.0, 4), decoded is 1.234243670089e8
Pascal
Free Pascal
There exist a special unit for BCD, even with fractions.Obvious for Delphi compatibility. <lang pascal>program CheckBCD; // See https://wiki.freepascal.org/BcdUnit {$IFDEF FPC} {$MODE objFPC}{$ELSE} {$APPTYPE CONSOLE} {$ENDIF} uses
sysutils,fmtBCD {$IFDEF WINDOWS},Windows{$ENDIF} ;
{type
TBcd = packed record Precision: Byte; SignSpecialPlaces: Byte; Fraction: packed array [0..31] of Byte; end;}
var
Bcd0,Bcd1,BcdOut : tBCD;
Begin
Bcd1 := IntegerToBcd(1);
// 0x19 + 1 = 0x20
Bcd0 := IntegerToBcd(19); BcdAdd(Bcd0,Bcd1,BcdOut); writeln(BcdToStr(Bcd0),'+',BcdToStr(Bcd1),' =',BcdToStr(BcdOut));
// 0x30 - 1 = 0x29
Bcd0 := IntegerToBcd(29); BcdAdd(Bcd0,Bcd1,BcdOut); writeln(BcdToStr(Bcd0),'+',BcdToStr(Bcd1),' =',BcdToStr(BcdOut));
// 0x99 + 1 = 0x100
Bcd0 := IntegerToBcd(99); BcdAdd(Bcd0,Bcd1,BcdOut); writeln(BcdToStr(Bcd0),'+',BcdToStr(Bcd1),' =',BcdToStr(BcdOut)); BcdMultiply(Bcd0,Bcd0,BcdOut); writeln(BcdToStr(Bcd0),'*',BcdToStr(Bcd0),' =',BcdToStr(BcdOut));
end.</lang>
- Output:
19+1 =20 29+1 =30 99+1 =100 99*99 =9801
Phix
using fbld and fbstp
The FPU maths is all as normal (decimal), it is only the load and store that convert from/to BCD.
While I supply everything in decimal, you could easily return and pass around the likes of acc and res.
without javascript_semantics -- (not a chance!) requires("1.0.2") -- #ilASM{fbld, fbstp} added function h(string s) -- convert the 10 bytes BCD, as held in -- a binary string, to a decimal string. for i=length(s) to 1 by -1 do if s[i]!='\0' or i=1 then string res = sprintf("%x",s[i]) for j=i-1 to 1 by -1 do res &= sprintf("%02x",s[j]) end for return res end if end for end function procedure test(integer a, b) -- Some (binary) strings to hold 10 byte BCDs: string acc = repeat('\0',10), res = repeat('\0',10) #ilASM{ mov eax,[a] mov edx,[b] mov esi,[acc] mov edi,[res] push eax fild dword[esp] fbstp tbyte[ebx+esi*4] -- save as 10 byte BCD fbld tbyte[ebx+esi*4] -- reload proves we can mov [esp],edx fild dword[esp] faddp fbstp tbyte[ebx+edi*4] pop eax -- (discard temp workspace) } integer pm = iff(b>=0?'+':'-') printf(1,"%s %c %d = %s\n",{h(acc),pm,abs(b),h(res)}) end procedure test(19,+1) test(30,-1) test(99,+1)
- Output:
19 + 1 = 20 30 - 1 = 29 99 + 1 = 100
using daa and das
This time we'll supply the arguments in hex/BCD.
Note the result is limited to 16 bits plus one carry bit here.
The aaa, aas, aam, and aad instructions are also available.
Same output as above, of course
without javascript_semantics -- (not a chance!) requires("1.0.2") -- #ilASM{aaa, etc} added requires(32) -- aaa etc not valid on 64 bit procedure test2(integer bcd, op) integer res #ilASM{ mov eax,[bcd] mov ecx, 1 mov edx,[op] cmp [op],'+' jne :sub1 add al,cl daa adc ah,0 jmp @f ::sub1 sub al,cl das @@: mov[res],eax } printf(1,"%x %c 1 = %x\n",{bcd,op,res}) end procedure test2(#19,'+') test2(#30,'-') test2(#99,'+')
hll bit fiddling
With routines to convert between decimal and bcd, same output as above, of course. No attempt has been made to support fractions or negative numbers...
with javascript_semantics -- (no requires() needed here) function bcd_decode(integer bcd) assert(bcd>=0) integer res = 0, dec = 1 while bcd do res += and_bits(bcd,#F)*dec bcd = bcd >> 4 dec *= 10 end while return res end function function bcd_encode(integer dec) assert(dec>=0) integer res = 0, shift = 0 while dec do res += remainder(dec,10) << shift dec = trunc(dec/10) shift += 4 end while return res end function procedure test3(integer dec, op) integer bcd = bcd_encode(dec), work = bcd, res = 0, shift = 0, carry = 1 while work or carry do integer digit = (work && #F) if op='+' then digit += carry if digit>9 then digit -= 10 carry = 1 else carry = 0 end if else digit -= carry if digit<0 then digit += 10 carry = 1 else carry = 0 end if end if res += digit<<shift work = work>>4 shift += 4 end while printf(1,"%d %c 1 = %d\n",{bcd_decode(bcd),op,bcd_decode(res)}) end procedure test3(19,'+') test3(30,'-') test3(99,'+')
Wren
In Wren all numbers are represented by 64 bit floats and the language has no real concept of bytes, nibbles or even integers.
The following is therefore a simulation of BCD arithmetic using packed binary strings to represent decimal digits. It only works for non-negative integral numbers.
We can change to 'unpacked' notation simply by prepending '0000' to each 'digit' of the 'packed' notation.
In what follows, the hex prefix '0x' is simply a way of representing BCD literals and has nothing to do with hexadecimal as such. <lang ecmascript>import "./check" for Check import "./math" for Int import "./str" for Str import "./fmt" for Fmt
class BCD {
static init_() { __bcd = [ "0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001" ] __dec = { "0000": "0", "0001": "1", "0010": "2", "0011": "3", "0100": "4", "0101": "5", "0110": "6", "0111": "7", "1000": "8", "1001": "9" } }
construct new(n) { if (n is String) { if (n.startsWith("0x")) n = n[2..-1] n = Num.fromString(n) } Check.nonNegInt("n", n) if (!__bcd) BCD.init_() _b = "" for (digit in Int.digits(n)) _b = _b + __bcd[digit] }
toInt { var ns = "" for (nibble in Str.chunks(_b, 4)) ns = ns + __dec[nibble] return Num.fromString(ns) }
+(other) { if (!(other is BCD)) other = BCD.new(other) return BCD.new(this.toInt + other.toInt) }
-(other) { if (!(other is BCD)) other = BCD.new(other) return BCD.new(this.toInt - other.toInt) }
toString { var ret = _b.trimStart("0") if (ret == "") ret = "0" return ret }
toUnpacked { var ret = "" for (nibble in Str.chunks(_b, 4)) ret = ret + "0000" + nibble ret = ret.trimStart("0") if (ret == "") ret = "0" return ret }
toHex { "0x" + this.toInt.toString }
}
var hexs = ["0x19", "0x30", "0x99"] var ops = ["+", "-", "+"] for (packed in [true, false]) {
for (i in 0...hexs.count) { var op = ops[i] var bcd = BCD.new(hexs[i]) var bcd2 = (op == "+") ? bcd + 1 : bcd - 1 var str = packed ? bcd.toString : bcd.toUnpacked var str2 = packed ? bcd2.toString : bcd2.toUnpacked var hex = bcd.toHex var hex2 = bcd2.toHex var un = packed ? "" : "un" var w = packed ? 8 : 12 var args = [hex, op, hex2, un, w, str, op, str2] Fmt.lprint("$s $s 1 = $-5s or, in $0spacked BCD, $*s $s 1 = $s", args) } if (packed) System.print()
}</lang>
- Output:
0x19 + 1 = 0x20 or, in packed BCD, 11001 + 1 = 100000 0x30 - 1 = 0x29 or, in packed BCD, 110000 - 1 = 101001 0x99 + 1 = 0x100 or, in packed BCD, 10011001 + 1 = 100000000 0x19 + 1 = 0x20 or, in unpacked BCD, 100001001 + 1 = 1000000000 0x30 - 1 = 0x29 or, in unpacked BCD, 1100000000 - 1 = 1000001001 0x99 + 1 = 0x100 or, in unpacked BCD, 100100001001 + 1 = 10000000000000000
Z80 Assembly
The DAA
function will convert an 8-bit hexadecimal value to BCD after an addition or subtraction is performed. The algorithm used is actually quite complex, but the Z80's dedicated hardware for it makes it all happen in 4 clock cycles, tied with the fastest instructions the CPU can perform.
<lang z80> PrintChar equ &BB5A ;Amstrad CPC kernel's print routine org &1000
ld a,&19 add 1 daa call ShowHex call NewLine
ld a,&30 sub 1 daa call ShowHex call NewLine
ld a,&99 add 1 daa
- this rolls over to 00 since DAA only works with the accumulator.
- But the carry is set by this operation, so we can work accordingly.
jr nc,continue ;this branch is never taken, it exists to demonstrate the concept of how DAA affects the carry flag. push af ld a,1 call ShowHex pop af continue: call ShowHex call NewLine ret ;return to basic
ShowHex: push af and %11110000 rrca rrca rrca rrca call PrintHexChar pop af and %00001111 ;call PrintHexChar ;execution flows into it naturally. PrintHexChar: ;this little trick converts hexadecimal or BCD to ASCII. or a ;Clear Carry Flag daa add a,&F0 adc a,&40 jp PrintChar</lang>
- Output:
20 29 0100