[FIXED] Decimal 16 bit variables and CPU time/ROM space...

[Vectrex2809]

Up until now, I never used a 16 bit variable in my games as a variable that is buffered to the screen (at least not to its full potential, since the coins in Brony Blaster are a 16 bit variable but it can only go up to 9999 in the game). The first thing that came to my mind when buffering such variables is to take 5 variables in the RAM, load the high byte to X and then add decimal 256 to those variables, while having a loop where X decrements. When all this is done, I convert the lower byte to decimal and put it in the designated variables (Which works as it should). Here's some pseudocode to show you what I mean

Code: Select all

LDX highbyte
.loop
CPX #$00
BEQ .done
;Fairly enough code that adds the decimal values to the designated RAM spot
DEX
JMP .loop
.done
;Rest of code

The problem is that converting the high byte to decimal takes more CPU time each time the high byte is incremented, up to a certain point where the game slows down and becomes unplayable. I had another solution in mind but that would take a lot of ROM space which I don't want to waste either.
Does there exist any solution to buffer 16-bit variables conveniently? I know a few commercial games managed to do so (For example, the money in Uncharted Waters is a 16 bit variable, but then that game is rather slow paced so it can get away with CPU time use)

tl;dr Is there any convenient way to buffer decimal 16 bit variables to sprites or to the background?

[Sik]

Doesn't SMB1 store coins as two separate digits without ever storing the value as-is? (i.e. works off the split digits directly)

But yeah, it may be more convenient to update each digit directly instead of recalculating them off the 16-bit value each time

[Vectrex2809]

Doesn't SMB1 store coins as two separate digits without ever storing the value as-is? (i.e. works off the split digits directly)

But yeah, it may be more convenient to update each digit directly instead of recalculating them off the 16-bit value each time

Yeah, I was thinking about this instead of using 16-bit variables. I actually use this method for scoring since scores usually have 5 or 6 "active" digits (I don't use the last zero in most of my games) that need to go over 65536. 16-bit variables would be more interesting to use for coin counts and similar purposes though IMO

[Sik]

You could always just keep the value stored both ways =P (that's 7 bytes already, though...)

Is it that bad to do four loops? (dividing by 10000, 1000, 100 and 10, in that order) Sounds wasteful, but shouldn't explode like that in terms of CPU usage (36 iterations at worst), and the last loop would only need 8-bit calculations even.

[tepples]

A 16-bit conversion takes 670 cycles at most. (Source) It works by subtracting 40000, 20000, 10000, 8000, 4000, 2000, 1000, 800, ..., 10. And only when the status bar updates do you need to repeat the conversion. This is the approach I used for money in RHDE and kill count in Haunted.

A trick I've used in Thwaite is "base 100", which stores a 4-digit value as two bytes from 0 to 99 ($00 to $63) and subtracts 100 ($64) when it compares higher. Then I can use another unrolled 8-bit binary to decimal routine, which takes 80 cycles per byte.

[Vectrex2809]

Actually I found a rather simple way to do it! Here's a snippet of code from Brony Blaster that makes calculating 16 bit variables way easier.
This only works for 4 number values, and there is another part in my code that stops the counter at #$270F (dec 9999)
Thanks for the replies

Code: Select all

;;Doing an 8-bit conversion to coins+1 first

;;If bit 0 of the coins variable=1, add 256
;;Then if bit 1 of the variable=1, add 512
;;If bit 2=1, add 1024
;;And so on

  LDA coins
  STA maintemp
  LDX #$05
.sixteenbitloop
  CLC
  ROR maintemp
  BCC .nextbin
  TXA
  PHA
  ASL A
  ASL A
  TAX
  LDY #$00
.add16bitloop
  LDA Buffer+72,y   ;Buffer position doesn't matter, using Buffer+72 to Buffer+76 (!)
  CLC
  ADC calc16bit,x
  STA Buffer+72,y
  INX
  INY
  CPY #$04
  BNE .add16bitloop
  PLA
  TAX
.nextbin
  DEX
  BPL .sixteenbitloop

;;Arrange decimal

;;More code

calc16bit:
  .db $08,$01,$09,$02,$04,$00,$09,$06,$02,$00,$04,$08,$01,$00,$02,$04
  .db $00,$05,$01,$02,$00,$02,$05,$06

Here's a version for 5 digits (using this one for another game with sprites)

Code: Select all

  LDX #$07
  LDA position+1
  STA maintemp
.sixteenbitloop
  CLC
  ROR maintemp
  BCC .nextbin
  TXA
  PHA
  ASL A
  ASL A
  STA maintemp+1
  PLA
  PHA
  CLC
  ADC maintemp+1
  TAX
  LDY #$00
.add16bitloop
  LDA $023D,y   ;Sprite position doesn't matter either, using $023D,$0241,$0245,$0249 and $024D
  CLC
  ADC calc16bit,x
  STA $023D,y
  INX
  TYA
  CLC
  ADC #$04
  TAY
  CPY #$14
  BNE .add16bitloop
  PLA
  TAX
.nextbin
  DEX
  BPL .sixteenbitloop

;;;;;;;;;;;;;;;;;;;;

calc16bit:
  .db $03,$02,$07,$06,$08,$01,$06,$03,$08,$04,$00,$08,$01,$09,$02,$00
  .db $04,$00,$09,$06,$00,$02,$00,$04,$08,$00,$01,$00,$02,$04,$00,$00
  .db $05,$01,$02,$00,$00,$02,$05,$06

[zzo38]

Here is another way (approx. 150 cycles, but not really tested yet) to convert 16-bit numbers into decimal form, although it requires more ROM space for the tables, requires the pattern tables to be arranged in a particular way (the digits 0-9 need to be duplicated within the first 32 cells, the program this code comes from duplicates them even twice more in other parts of the pattern table), and uses some unofficial opcodes.

Code: Select all

	; *** PRINTN
	def_inst_ext 230
	lda <$30
	beq zcrlf2 ; ensure there is room in the buffer
	ldy <$11
	lax <$21
	anc #$FF
	bcc znum01
	eor #$FF
	sta <4
	ldx <$30
	inc <$30
	lda #'-'
	sta <0,x
	tya
	eor #$FF
	tay
	ldx <4
znum01	lda digit0l,y
	adc digit0h,x
	pha
	cmp #10
	lda digit1l,y
	adc digit1h,x
	pha
	cmp #10
	lda digit2l,y
	adc digit2h,x
	pha
	cmp #10
	lda #0
	adc digit3h,x
	pha
	cmp #10
	lda #0
	adc digit4h,x
	ldx <$30
	tay ; make the flag according to accumulator
	beq znum02
	; Five digits
	sta <0,x
	pla
	sta 1,x
	pla
	sta 2,x
	pla
	sta 3,x
	pla
	sta 4,x
	txa
	axs #-5
	stx <$30
	jmp nxtinst
znum02	pla
	beq znum03
	; Four digits
	sta <0,x
	pla
	sta 1,x
	pla
	sta 2,x
	pla
	sta 3,x
	txa
	axs #-4
	stx <$30
	jmp nxtinst
znum03	pla
	beq znum04
	; Three digits
	sta <0,x
	pla
	sta 1,x
	pla
	sta 2,x
	txa
	axs #-3
	stx <$30
	jmp nxtinst
znum04	pla
	beq znum05
	; Two digits
	sta <0,x
	inx
	pla
	sta <0,x
	inx
	stx <$30
	jmp nxtinst
znum05	pla
	; One digit
	sta <0,x
	inc <$30
	jmp nxtinst

[Myask]

It's funny: the number of frames the decimal score-conversion in Super Mario World consumes is one of the things that TASers have to optimize for.

[Sik]

Are you serious? I doubt something like that would slow down the game regularly. You aren't mixing up with the score tally, right?

[Drag]

I took a stab at it for funsies:

Code: Select all

hexLo           ;Input number
hexHi
numDigits       ;Number of digits to output, minus 1
decE            ;Most significant output digit
decD
decC
decB
decA            ;Least significant output digit

; Tables for digit addition
digE
 .db 3,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0
digD
 .db 2,6,8,4,2,1,0,0,0,0,0,0,0,0,0,0
digC
 .db 7,3,1,0,0,0,5,2,1,0,0,0,0,0,0,0
digB
 .db 6,8,9,9,4,2,1,5,2,6,3,1,0,0,0,0
digA
 .db 7,3,1,5,7,3,1,5,7,3,1,5,7,3,1,0

 lda #$00       ;Initialize output digits
 sta decA
 sta decB
 sta decC
 sta decD
 sta decE
 ldy #$10       ;Current bit
nextBit
 dey            ;Advance to next bit value in table
 bmi exit       ;Exit if we're out of bits to check
 lsr hexHi      ;Shift input right once
 ror hexLo
 bcc nextBit    ;Don't add if bit is 0
 lda decA       ;Ones place
 adc digA,y     ;Carry is always set here, table compensates for it
 cmp #$0A       ;Did the digit overflow?
 bcc skipA      ;Don't subtract if it didn't, carry stays cleared
 sbc #$0A       ;Carry is already set, and remains set
skipA
 sta decA
 ldx numDigits  ;Number of digits remaining
 beq nextBit
 lda decB       ;Tens place
 adc digB,y
 cmp #$0A       ;Did the digit overflow?
 bcc skipB      ;Don't subtract if it didn't, carry stays cleared
 sbc #$0A       ;Carry is already set, and remains set
skipB
 sta decB
 dex            ;Number of digits remaining
 beq nextBit
 lda decC       ;Hundreds place
 adc digC,y
 cmp #$0A       ;Did the digit overflow?
 bcc skipC      ;Don't subtract if it didn't, carry stays cleared
 sbc #$0A       ;Carry is already set, and remains set
skipC
 sta decC
 dex            ;Number of digits remaining
 beq nextBit
 lda decD       ;Thousands place
 adc digD,y
 cmp #$0A       ;Did the digit overflow?
 bcc skipD      ;Don't subtract if it didn't, carry stays cleared
 sbc #$0A       ;Carry is already set, and remains set
skipD
 sta decD
 dex            ;Number of digits remaining
 beq nextBit
 lda decE       ;Ten thousands place
 adc digE,y     ;This fifth digit will never overflow
 sta decE       ;so carry will always be clear
 bcc nextBit    ;Branch always
exit

If you know you'll never use this to output more than 4 digits, you can insert a check to see if the input value is >= $270F and skip to a routine which outputs "9999". If you do this, you can remove the first row and the leftmost two columns of the table (change ldy #$10 to ldy #$0e), and you can remove the decE part of the unrolled loop, applying the carry skip and branch always tricks to the decD part instead.

[Myask]

Are you serious? I doubt something like that would slow down the game regularly. You aren't mixing up with the score tally, right?

Completely serious. That the sum of the decimal digits of the score and the tens but not ones digits of lives/coins impact fadeout time is what leads to belief in it being a decimal conversion.

[tokumaru]

A 16-bit conversion takes 670 cycles at most. (Source) It works by subtracting 40000, 20000, 10000, 8000, 4000, 2000, 1000, 800, ..., 10.

Turns out you can make this conversion much faster (over twice as fast) if you use the exact same technique (which took me nearly 10 years to understand! ), but with unrolled loops and a few optimizations:

Code: Select all

binary = 0
decimal = 0
value = 65535

	.org $8000

	lda #<value
	sta binary+0
	lda #>value
	sta binary+1

	lda #$00
	sta decimal+2
	sta decimal+3
	sta decimal+4
	clc

	;5th digit, bit 2
	lda binary+0
	sbc #<39999
	tax
	lda binary+1
	sbc #>39999
	bcc Skip52
	stx binary+0
	sta binary+1
Skip52:
	rol decimal+4
	;5th digit, bit 1
	lda binary+0
	sbc #<19999
	tax
	lda binary+1
	sbc #>19999
	bcc Skip51
	stx binary+0
	sta binary+1 
Skip51:
	rol decimal+4
	;5th digit, bit 0
	lda binary+0
	sbc #<9999
	tax
	lda binary+1
	sbc #>9999
	bcc Skip50
	stx binary+0
	sta binary+1 
Skip50:
	rol decimal+4

	;4th digit, bit 3
	lda binary+0
	sbc #<7999
	tax
	lda binary+1
	sbc #>7999
	bcc Skip43
	stx binary+0
	sta binary+1
Skip43:
	rol decimal+3
	;4th digit, bit 2
	lda binary+0
	sbc #<3999
	tax
	lda binary+1
	sbc #>3999
	bcc Skip42
	stx binary+0
	sta binary+1
Skip42:
	rol decimal+3
	;4th digit, bit 1
	lda binary+0
	sbc #<1999
	tax
	lda binary+1
	sbc #>1999
	bcc Skip41
	stx binary+0
	sta binary+1
Skip41:
	rol decimal+3
	;4th digit, bit 0
	lda binary+0
	sbc #<999
	tax
	lda binary+1
	sbc #>999
	bcc Skip40
	stx binary+0
	sta binary+1
Skip40:
	rol decimal+3

	;3rd digit, bit 3
	lda binary+0
	sbc #<799
	tax
	lda binary+1
	sbc #>799
	bcc Skip33
	stx binary+0
	sta binary+1
Skip33:
	rol decimal+2
	;3rd digit, bit 2
	lda binary+0
	sbc #<399
	tax
	lda binary+1
	sbc #>399
	bcc Skip32
	stx binary+0
	sta binary+1
Skip32:
	rol decimal+2
	;3rd digit, bit 1
	lda binary+0
	sbc #<199
	tax
	lda binary+1
	sbc #>199
	bcc Skip31
	stx binary+0
	sta binary+1
Skip31:
	rol decimal+2
	;3rd digit, bit 0
	lda binary+0
	sbc #99
	bcc Skip30
	sta binary+0
Skip30:
	rol decimal+2

	;2nd digit, bit 3
	lda binary+0
	sbc #79
	bcc Skip23
	sta binary+0
Skip23:
	rol decimal+1
	;2nd digit, bit 2
	lda binary+0
	sbc #39
	bcc Skip22
	sta binary+0
Skip22:
	rol decimal+1
	;2nd digit, bit 1
	lda binary+0
	sbc #19
	bcc Skip21
	sta binary+0
Skip21:
	rol decimal+1
	;2nd digit, bit 0
	lda binary+0
	sbc #9
	bcc Skip20
	sta binary+0
Skip20:
	rol decimal+1

Please excuse the "SkipXX" labels, but this code is for the 6502 simulator, which doesn't have anonymous labels.

Anyway, if converting binary numbers to decimal is something you do frequently, it might pay off to dedicate some extra ROM space to this unrolled version of the code.

[Omegamatrix]

Here is a link to some of the routines I wrote for very fast hex to decimal:

viewtopic.php?p=130363#p130363

These routines are all tested and confirmed working. They are in subroutine form and can be used for smaller conversions. A summary is below:

Code: Select all

;slow routine - 174 bytes, 183 bytes with HexToDec255 and HexToDec999
;HexToDec99     ; 37 cycles
;HexToDec255    ; 52-57 cycles
;HexToDec999    ; 72-77 cycles
;HexToDec65535  ; 178-186 cycles


;Fast routine - 234 bytes, 243 bytes with HexToDec255 and HexToDec999
;HexToDec99     ; 37 cycles
;HexToDec255    ; 52-57 cycles
;HexToDec999    ; 72-77 cycles
;HexToDec65535  ; 157-162 cycles

[tokumaru]

Those are some impressive times! Damn, it will probably take me another 10 years to understand THAT method!

[zzo38]

The code I posted is doing several things that you might not need, such as dealing with negative numbers, appending to the end of a text buffer, stripping leading zeroes, etc. It could probably be simplified to remove the stuff that you do not need. However, it uses more space in the program ROM space and in the pattern table than other methods do. You can compare all of the methods (including but not limited to mine) in a table in order to compare its working.