English Amiga Board


Go Back   English Amiga Board > Coders > Coders. General

 
 
Thread Tools
Old 17 August 2010, 23:00   #1
Herpes
... aka Amix73

Herpes's Avatar
 
Join Date: Jan 2009
Location: Austria
Posts: 76
Stick out tongue BCD Arithmetic - howto^

Hi coding gurus - please help!

Just wanted to test how to work with BCD (binary coded decimal) arithmetics in assembler - and I got confused. I never used it but always thought it would be crystal clear and easy

My assumption was that 4 bit represent one BCD-Digit and hence if I add 1 to 09 I get 10. This works somehow:
Code:
    move.w  #4,CCR
    moveq   #1,d0
    moveq   #9,d1
    abcd    d0,d1
    rts
The result is literally '10' in d1 - as I expected. But - an now I start to get confused - this works well until 19 - when I add for instance 5 in d0 to 15 in d1 I get as a result 1A in d1

Well, well, in the 68K instruction set sheet there is a nice example how to use BCD-arithmetics with multiple bcd-digits which is done using bcd digits in memory which is similar to this code:

Code:
start
    lea    num1,a0
    lea    num2,a1
    move   #4,CCR
    moveq  #3,d0
.lp
    abcd    -(a0),-(a1)
    dbra    d0,.lp
    rts

    dcb.b   100,$ff      ; just dummy - for hexdump
    dc.b    12,34,98,01  ; should be 12349801
num1
    dc.b    0,0,0,99     ; should be 00000099 and result in 12349900
num2
    dcb.b   100,$ff
I get strange results. Normally I would expect to get 12,34,99,00 as a result. But when I hexdump the memory I get 12 (18 dec),22 (34 dec), 62 (98 dec) and 64 (100). Actually I don't care how they are displayed but this is a complete mix-up! I mean I have no Idea how to define a BCD Number else then using dc.b 12 which will be shown as $0C in hexdump. But when it is added the $C value must be interpreted as a 12 and the result should be correct.

I thought that the digits in memory would be treated as BCD and stored as such. But this is not the case. This is also not the case when I use the registers to compute.

Please enlighten me - I am completely confused and and on the brink of madness - this must be easy and I have overseen something - or I am really - I think I need a nap

Thanks in advance.
Herpes is offline  
Old 18 August 2010, 00:09   #2
StingRay
move.l #$c0ff33,throat

StingRay's Avatar
 
Join Date: Dec 2005
Location: Berlin/Joymoney
Posts: 6,146
Quote:
Originally Posted by Herpes View Post
when I add for instance 5 in d0 to 15 in d1 I get as a result 1A in d1
15 is not the same as $15 (which would be the valid BCD number).


Quote:
Originally Posted by Herpes View Post
I get strange results. Normally I would expect to get 12,34,99,00 as a result.
Not very surprising since when using BCD arithmetic you should actually use BCD numbers. Same problem as above.

12 != $12; 34 != $34 etc.

BCD: Only numbers 0-9 are used (that's why they are called binary coded DECIMALS), so 9 becomes $9, 10 = $10, 11 = $11 etc.
StingRay is offline  
Old 18 August 2010, 00:54   #3
Herpes
... aka Amix73

Herpes's Avatar
 
Join Date: Jan 2009
Location: Austria
Posts: 76
Quote:
Originally Posted by StingRay View Post
15 is not the same as $15 (which would be the valid BCD number).

Not very surprising since when using BCD arithmetic you should actually use BCD numbers. Same problem as above.

12 != $12; 34 != $34 etc.
Thanks for the quick reply.
I know that $12 != 12 - at least I though I would

Just to explain my idiotic blackout and to reconstruct how my confusion became virulent - I got strange results after trying a bit and forgetting to clear the X and set Z (move #4,CCR) (that I know now). Second I was not sure anymore whether the value in the register is only interpreted through the abcd-instruction as a bcd value. What confused me int this regard even more was the example in Peter Wollschl├Ągers Assembler-book where he wrote that he has 2 BCD - numbers (3 digits 123456 and 654321) in memory starting @ address 1001:12 1002:34 1003:56 and @ address 2001:65 2002:43 2003:21 - I think this was the main reason.

This shows what a stupid idiot I am this is embarrassing!

At least you helped to clear my confusion and get my code working
Thank you very much.

Last edited by Herpes; 18 August 2010 at 00:56. Reason: Typo
Herpes is offline  
Old 22 August 2010, 13:11   #4
Photon
Moderator
Photon's Avatar
 
Join Date: Nov 2004
Location: Hult / Sweden
Posts: 4,589
BCD is silly and useless, inefficient and a typical 'bad idea'. It has always baffled me why they wasted instruction bits putting them in the CPUs. Even after 1971 they continued with that crap Even after the 68000 they continued.

It's perfectly safe for every coder to rip out the pages concerning BCD instructions from their programming manuals and forget about them completely.

Perhaps its flaws can be used for some contrived demo effect.
Photon is offline  
Old 26 August 2010, 00:36   #5
Herpes
... aka Amix73

Herpes's Avatar
 
Join Date: Jan 2009
Location: Austria
Posts: 76
Hehe, yes that's my opinion too after my confusion was settled and my code worked. I have no practical application for it ... (yet)
Herpes is offline  
Old 26 August 2010, 05:24   #6
Thorham
Computer Nerd

Thorham's Avatar
 
Join Date: Sep 2007
Location: Rotterdam/Netherlands
Age: 42
Posts: 3,085
Quote:
Originally Posted by Photon View Post
BCD is silly and useless, inefficient and a typical 'bad idea'. It has always baffled me why they wasted instruction bits putting them in the CPUs. Even after 1971 they continued with that crap Even after the 68000 they continued.

It's perfectly safe for every coder to rip out the pages concerning BCD instructions from their programming manuals and forget about them completely.

Perhaps its flaws can be used for some contrived demo effect.
BCD is not at all useless and silly, it has it's uses, see here on Wikipedia: advantages.
Thorham is offline  
Old 26 August 2010, 23:50   #7
Photon
Moderator
Photon's Avatar
 
Join Date: Nov 2004
Location: Hult / Sweden
Posts: 4,589
What, they really mean base 10 is good for base 10 arithmetic!?

...except the normal instructions do it faster and isn't limited to the few example calculations they list. The 7-segment display crap is silly, BCD is much older, they should have used nixies for the example instead. Converting to text is hard now??

And oh I see, printing a 7 million decimal math constant shows the flaws of binary arithmetic and the superiority of BCD. I wonder how the math lab programmers at Uni have coped all these decades!!!

That big a number is always generated. By computers. Wozniak showed how to compute e to a couple hundred thousand places (216000 or something? IIRC) in 1978 already. He did it right, ie. instead of converting like a nincompoop he delivered the digits in base 10 already. Interesting read, that was.

OK, I will now start a BCD is shit club! Hehe.
Photon is offline  
Old 06 September 2010, 00:39   #8
Lonewolf10
AMOS Extensions Developer
Lonewolf10's Avatar
 
Join Date: Jun 2007
Location: near Cambridge, UK
Age: 39
Posts: 1,919
Quote:
Originally Posted by Photon View Post
BCD is silly and useless, inefficient and a typical 'bad idea'. It has always baffled me why they wasted instruction bits putting them in the CPUs. Even after 1971 they continued with that crap Even after the 68000 they continued.

Hardly useless.

How would you store a 100 digit number efficiently? BCD is the only efficient option I can think of (forgetting about compressing it, of course), with storing it as a string being the next option, but using twice as much memory.

Personally I find BCD to be pretty cool, just as Hexadecimal, Roman Numerals and Binary are


Regards,
Lonewolf10
Lonewolf10 is offline  
Old 06 September 2010, 01:20   #9
Leffmann
 
Join Date: Jul 2008
Location: Sweden
Posts: 2,187
I can also see how it's very useful if you need to very quickly access individual digits of base 10 in a number, or quickly do operations like divisions or multiplications with 10^n. Question is, when do you need to?

If you were just to store the number as efficiently as possible (as little space as possible) then encoding it in base 256 and store as a number of bytes would be the most efficient+practical solution.
Leffmann is offline  
Old 07 September 2010, 01:11   #10
Photon
Moderator
Photon's Avatar
 
Join Date: Nov 2004
Location: Hult / Sweden
Posts: 4,589
Well, by the clues I left in my previous post you can find out what they were put in CPUs for, and why their use after the appearance of >256 bytes RAM in computers and non-serial output devices (not to mention FPUs and CPUs with larger words than 8 bits) made them quite obsolete. A computer's base is 2, and it has always been that way, all input data is in base 2, all units are made to calculate it. The reasons for its brief appearance on the scene are temporary practical ones.

I agree the limited uses on large numbers only using certain operations in base 10 is a bit silly. First of all, nobody who needs to operate on really large numbers in base 10 buys a $30 7 MHz CPU to do it, much less an 80 MHz one 10 years later, and certainly not droves of them to compensate for the puny speed. They tacked it on unnecessarily.

Secondly, the instructions are rudimentary for even the simplest math someone would want to do, and they'd do it inefficiently.

Anyway.

I've left some clues for those who want to find out their use way back and don't want the nostalgia spoiled. Would be cool if someone could contribute some code snippet where they're (ab)used to do something useful on Amiga, but...
Photon is offline  
Old 20 June 2012, 20:02   #11
phx
Natteravn

phx's Avatar
 
Join Date: Nov 2009
Location: Herford / Germany
Posts: 1,203
Quote:
Originally Posted by Photon View Post
Would be cool if someone could contribute some code snippet where they're (ab)used to do something useful on Amiga, but...
I found BCD to be useful while trying to display the scores for the game Sqrxz.
http://eab.abime.net/showthread.php?...ighlight=sqrxz

Having to spend 140 cycles for each "divu #10" in a timing-critical program like a scrolling platform game is certainly to be avoided. So I keep all the scores in BCD and only have to do some masking and shifting to convert it into ASCII, ready to display.
phx is offline  
Old 20 June 2012, 22:35   #12
Photon
Moderator
Photon's Avatar
 
Join Date: Nov 2004
Location: Hult / Sweden
Posts: 4,589
I'm sorry if I was being polite and vague. BCD is useless and was only wasting instruction space in 680x0 to provide easy recoding of horrible old CP/M and mainframe programs. My point was using them for something other than their intended horrible purpose that would be of use in loops in games and demos, some way of making them .01% special-case useful, at least. (pant pant)

Sorry, I really hate BCD with a vengeance. Once stored the wrong way (in BCD) you couldn't do arithmetic other than + and - to it. A 10x bonus multiplier would mean you'd have to loop/repeat-add 10 times, or a bunch of if-statements to add different constants.

What you want out is each digit in a byte or possibly word. Preferably also keeping the score as a normal number, so you could go add #bonus,score rather than having a multiline macro or subroutine to cascade-update the score. Rather than storing them in nibbles, second best would be to store them in bytes or words all the time, and cascade-add to that.

While cascading add adds 48 cycles per two digits (compared to cascading abcd) but saves the 34-cycle (per two digits), nibble-masking and shifting you mention it's ugly. My favorite is

Code:
;d0=4710
divu #100,d0
add.w d0,d0
move.w Tbl99(PC,d0.w),d1    ;or -(a1)...
swap d0
swap d1
add.w d0,d0
move.w Tbl99(PC,d0.w),d1
;d1="4710"
because you can keep the score as a number and only do this once per score-update. Another div for 4 more digits. Even with BCD-stored numbers, getting 8 digits out as ASCII will have a hard time competing with this. You can easily modify the table to get two byte- or word-offsets to graphics out instead of ASCII.

There should be some successive approximation inverse-multiply or daisy-chained magic constant-subtract algorithms out there but they're bound to be crap so I didn't bother looking.
Photon is offline  
Old 21 June 2012, 00:38   #13
Codetapper
2 contact me: email only!

Codetapper's Avatar
 
Join Date: May 2001
Location: Auckland / New Zealand
Posts: 3,147
I disagree about BCD being useless too. If you have an 8 digit decimal score and your scoring system is relatively simple (ie. adding the odd value to the score once in a while), then BCD is definitely the way to go.

Say you wanted to add 1000 points to the score:

Code:
        lea     value(pc),a1
        move.l  #$1000,(a1)+  ;a1 now points to the end of the value to add

        lea     score+4(pc),a0
        sub     d0,d0         ;to clear the carry
        abcd    -(a1),-(a0)
        abcd    -(a1),-(a0)
        abcd    -(a1),-(a0)
        abcd    -(a1),-(a0)
        ...
score   dc.l    0
value   dc.l    0
Obviously adding to the score is slower than an add.l #1000,score instruction. But you make huge gains when it comes to displaying the score:

Code:
        lea     digits(pc),a0     ;8 bytes
        move.l  score,d0
        move.l  d0,d1
        and.l   #$F0F0F0F0,d0
        eor.l   d0,d1
        lsr.l   #4,d0
        ;if your character set is ASCII, add the 2 following lines:
        ;add.l  #$30303030,d0
        ;add.l  #$30303030,d1
        movep.l d0,0(a0)
        movep.l d1,1(a0)
Not a single division operation is used, and you have all 8 bytes of the score now converted to decimal ready for printing each character. One div operation is conceivably more cycles than the entire conversion code above takes.

You might need to replace the movep instructions if you're running on an 060 but BCD has some unique/awesome features!

Last edited by Codetapper; 21 June 2012 at 07:09.
Codetapper is offline  
Old 21 June 2012, 02:59   #14
Photon
Moderator
Photon's Avatar
 
Join Date: Nov 2004
Location: Hult / Sweden
Posts: 4,589
For 8 digits, your BCD comes in at 348 cycles, div comes in at 448, and a stupid ascii adder without checking if add-value is < 10000 comes in at 436c (else it would be 280c).

So that's how much adding instructions on a whim saves, 11 cycles per digit (less if 68060 compatibility is desired...). BCD was added as a lazy convenience, never to save cycles or code size. It's never used where performance is of importance, as this max-once-per-frame score example shows.

Modify your code for 4 digits as is the case with Sqrzx and I'll make a comparison with div.

Last edited by Photon; 21 June 2012 at 03:09. Reason: added of
Photon is offline  
Old 21 June 2012, 06:50   #15
Codetapper
2 contact me: email only!

Codetapper's Avatar
 
Join Date: May 2001
Location: Auckland / New Zealand
Posts: 3,147
If you're not concerned about memory on a 100 word table, you could go one step further, divide by 10,000 and store 10,000 longwords of every combination to handle an 8 digit score with 1 div!

I remember seeing huge ASCII strings 00010203040506070809101112 etc in games and wondering what on earth they had done that for. I guess they're using Photon's score lookup method.

In my case I also go through the ASCII string and change the first digit from "0" to a space as I like right aligned scores without leading 0's.

I guess you could adjust Photon's table lookup to have a second table of 100 words with the leading 0's replaced and use that table when relevant.

For 4 digits, the only real change is a few longwords change to words:

Code:
Add4    lea     value(pc),a1
        move.l  a1,a0         ;a0 now points to the end of the score
        move.w  #$1000,(a1)+  ;a1 now points to the end of the value to add

        sub     d0,d0         ;to clear the carry
        abcd    -(a1),-(a0)
        abcd    -(a1),-(a0)

Show4   lea     digits(pc),a0     ;4 bytes
        move.w  score(pc),d0
        move.w  d0,d1
        and.w   #$F0F0,d0
        eor.w   d0,d1
        lsr.w   #4,d0
        ;if your character set is ASCII, add the 2 following lines:
        ;add.w  #'00',d0
        ;add.w  #'00',d1
        movep.w d0,0(a0)
        movep.w d1,1(a0)
        ...
score   dc.w    0
value   dc.w    0
digits  ds.b    4
It might be quicker to move '00' into a register, add that to d0 and d1, or maybe skip that and at the very end do add.l #'0000',(a0) instead if you're dealing with ASCII digits.

Last edited by Codetapper; 21 June 2012 at 21:37. Reason: Removed the 2 extraneous abcd instructions!
Codetapper is offline  
Old 21 June 2012, 09:06   #16
phx
Natteravn

phx's Avatar
 
Join Date: Nov 2009
Location: Herford / Germany
Posts: 1,203
Quote:
Originally Posted by Photon View Post
Modify your code for 4 digits as is the case with Sqrzx and I'll make a comparison with div.
This is the code I'm currently using:
Code:
8       subq.l  #8,sp
4       move.l  sp,a0
12      move.b  Score(a4),d0
4       moveq   #15,d1
4       and.b   d0,d1
8       move.b  d1,(a0)+
14      lsr.b   #4,d0
8       move.b  d0,(a0)+
12      move.b  Score+1(a4),d0
4       moveq   #15,d1
4       and.b   d0,d1
8       move.b  d1,(a0)+
14      lsr.b   #4,d0
8       move.b  d0,(a0)
28      add.l   #'0000',(sp)
---
140
Comparing that with your divu+table approach:
Code:
8       subq.l  #8,sp
4       moveq   #0,d0
12      move.w  Score(a4),d0
140     divu    #100,d0
4       add.w   d0,d0
14      move.w  Tbl99(pc,d0.w),d1
4       swap    d0
4       swap    d1
4       add.w   d0,d0
14      move.w  Tbl99(pc,d0.w),d1
12      move.l  d1,(sp)
---
220
This shows a gain of 80 cycles (provided I looked up the cycles correctly) and nearly 400 bytes of memory, where I happily accept some BCD arithmetics for.

EDIT: And Codetappers solution with eor and movep even gains another 30 cycles (110)! Very nice. Although I'm not sure if I want to use movep.

Last edited by phx; 21 June 2012 at 09:34.
phx is offline  
Old 21 June 2012, 17:37   #17
Photon
Moderator
Photon's Avatar
 
Join Date: Nov 2004
Location: Hult / Sweden
Posts: 4,589
I removed the extraneous abcd but added the ASCII as that's what comes out of phx's too.

Quote:
Originally Posted by Codetapper View Post
Code:
8	lea     value(pc),a1
4	move.l  a1,a0	 ;a0 now points to the end of the score
12      move.w  #$1000,(a1)+  ;a1 now points to the end of the value to add

4	sub     d0,d0	 ;to clear the carry
32	abcd    -(a1),-(a0)
32	abcd    -(a1),-(a0)
	;abcd    -(a1),-(a0)
	;abcd    -(a1),-(a0)

8	lea     digits(pc),a0     ;4 bytes
12	move.w  score(pc),d0
4	move.w  d0,d1
8	and.w   #$F0F0,d0
4	eor.w   d0,d1
14	lsr.w   #4,d0
	;if your character set is ASCII, add the 2 following lines:
8	add.w  #'00',d0
8	add.w  #'00',d1
24	movep.w d0,0(a0)
24	movep.w d1,1(a0)
=206
Code:
16	add.w #1000,score
	
4	moveq #0,d0
8	lea score+4(PC),a1
8       move.w (a1),d0
140	divu #100,d0
4	add.w d0,d0 
26	move.w Tbl99(PC,d0.w),-(a1) 
4	swap d0 
4	add.w d0,d0 
26	move.w Tbl99(PC,d0.w),-(a1) 
=240
If you need to replace the movep you've saved 1 cycle per digit, if you add to the score maximum once per frame. If the player should kill 2 baddies in one frame, the BCD method takes longer.

The table takes 200 bytes, but has the advantage that it can directly point to digit graphics, digit-pair graphics, or digit-pair blits. It's silly to do that for scores, on the other hand it saves many more cycles than using BCD

Here's a non-div, non-table, non-BCD alternative:

Code:
maxdigit="0"+"0"+10
mindigit="0"+10
8	lea score(pc),a1 
28	add.l #"1000",score(a4)

4	moveq #maxdigit,d0
4	moveq #mindigit,d1
4	moveq #10,d2
8	move.w #1<<8,d3

16	move.l score(a4),d4
	REPT 4
4	sub.b d0,d4
18/2	bpl.s .ok
4/2	add.b d2,d4
4/2	add.w d3,d4	;carry
.ok:4	add.b d1,d4
24	ror.l #8,d4
45x4	ENDR
16	move.l d4,score(a4)
=268
...
score:  dc.b "0000"
Photon is offline  
Old 21 June 2012, 21:43   #18
Codetapper
2 contact me: email only!

Codetapper's Avatar
 
Join Date: May 2001
Location: Auckland / New Zealand
Posts: 3,147
Whoops, thanks for spotting the excess abcd instructions when I modified it. I also dislike using movep. I am loving this thread though!
Codetapper is offline  
Old 22 June 2012, 00:14   #19
Asman
68k

Asman's Avatar
 
Join Date: Sep 2005
Location: Somewhere
Posts: 646
As I know abcd works with extended bit ( x bit ) so sub.w d0,d0 clear x bit in this case.

My first attempt (based on Codetapper version with BCD):
Code:
;add aabb (in this case 100 points ) to the score

	lea	score(pc),a0	;8c
	sub.w	d0,d0		;4c clear X bit 
	moveq	#1,d0		;4c BCD aa
	moveq	#0,d1		;4c BCD bb (can be removed in this case:) )

	move.l	(a0),d2		;12c

	abcd	d1,d2		;6c
	swap	d2		;4c
	abcd	d0,d2		;6c
	swap	d2		;4c

	move.l	d2,(a0)+	;12c	now a0 points to digits
				;=64c

	move.l	d2,d1		;4c
	and.l	#$00f000f0,d2	;14c
	eor.l	d2,d1		;8c
	lsl.l	#4,d2		;16c
	or.l	d1,d2		;6c
	add.l	#'0000',d2	;16c
	move.l	d2,(a0)		;12c
				;=76c
				;total 140c
score:	dc.w	$09,$99
digits:	dc.l	0
If there is something wrong please correct me.
Asman is offline  
Old 22 June 2012, 00:43   #20
Photon
Moderator
Photon's Avatar
 
Join Date: Nov 2004
Location: Hult / Sweden
Posts: 4,589
That seems to add 100 to a strangely stored score, using moveq to save cycles for one case when it really should work for adding any number

We excluded the bsr/rts etc for easier comparison, but you need to isolate the adding from the conversion (to compare with previous examples, and how these things would work in a real game.)

You can store the score as bytes with BCD numbers only in the lower nibble, you can store them as byte numbers between -1 and -10 or 0 and -9, or as bytes multiplied by 26 or 13... but it would just get uglier and uglier I think

I was really only interested in showing BCD gives no real gain, but you can optimize away if you want of course
Photon is offline  
 


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
Prefs/DefIcons howto ? amiga support.Apps 1 04 October 2008 19:34
Got a Catweasel MK2... howto? Photon support.Hardware 3 27 July 2008 17:22
MKick Howto? maxlock support.Other 2 12 June 2008 20:01
My CD32-compilation HOWTO... frostwork Amiga scene 1 05 January 2005 16:53

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT +2. The time now is 06:04.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2018, vBulletin Solutions Inc.
Page generated in 0.10285 seconds with 13 queries