It is currently Tue Aug 14, 2018 11:59 pm

 All times are UTC - 7 hours

 Page 1 of 2 [ 26 posts ] Go to page 1, 2  Next
 Print view Previous topic | Next topic
Author Message
 Post subject: Hex to DecimalPosted: Sun Jun 15, 2014 11:16 am

Joined: Tue Jun 10, 2014 8:15 pm
Posts: 35
Here is a routine I wrote to convert a 16 bit number (0-65535) to decimal, each digit separated. It only takes 150 to 162 cycles as shown below.

Edit - This is now revision 2 of the code...

Code:
;--------------------------------
;0-9999 conversion stats
;--------------------------------
;cycles          occurances
;150 - \$0860 -->  2,144
;151 - 0
;152 - 0
;153 - \$16C0 -->  5,824
;154 - 0
;155 - 0
;156 - \$07F0 -->  2,032

;average execution is 152.97 cycles

;--------------------------------
;0-65535 conversion stats
;--------------------------------
;cycles          occurances
;150 - \$1738 -->  5,944
;151 - 0
;152 - 0
;153 - \$9528 --> 38,184
;154 - 0
;155 - 0
;156 - \$2A30 --> 10,800
;157 - 0
;158 - 0
;159 - \$1F18 -->  7,960
;160 - 0
;161 - 0
;162 - \$0A58 -->  2,648

;average execution is 154.31 cycles

Here is the routine. It takes 258 bytes which is pretty good considering how fast it goes. There are other routines out there that are much shorter, but take 100's of cycles. My goal was speed while keeping the byte cost as low as possible.

If you want ASCII, then you can compile it in at a cost of just 8 more bytes, and 8 more cycles.

Code:
;----------------------------------------------------------
;Convert 16 bit Hex to Decimal (0-65535) Rev 2
;By Omegamatrix
;Further optimizations by tepples
;
; Takes 150-162 cycles to execute.
;
; Starts with 16 bit number split into hexHigh and hexLow.
; Uses A,X,Y, and three bytes of zeropage ram:
;
;    Ten Thousands digit - zp ram
;    Thousands digit - returned in A register
;    Hundreds digit - zp ram
;    Tens digit - returned in X register
;    Ones digit - zp ram
;----------------------------------------------------------

;temp register and decHundreds are doubled up to save ram...
temp = decHundreds

ASCII_OFFSET = \$30

Times256_Low:
.byte \$00,\$38,\$0C,\$44,\$18,\$50,\$24,\$5C
.byte \$30,\$04,\$3C,\$10,\$48,\$1C,\$54,\$28
Times256_Med:
.byte \$00,\$02,\$05,\$07,\$0A,\$0C,\$0F,\$11
.byte \$14,\$17,\$19,\$1C,\$1E,\$21,\$23,\$26

Times16_Low:
.byte \$00
Times4096_Low:
.byte \$00
Times4096_Med:
.byte \$00
Times4096_High:
.byte \$00 + ASCII_OFFSET

.byte \$10,\$60,\$28,\$00 + ASCII_OFFSET   ; interlaced tables, this allows less shifts to be made...
.byte \$20,\$5C,\$51,\$00 + ASCII_OFFSET
.byte \$30,\$58,\$16,\$01 + ASCII_OFFSET
.byte \$40,\$54,\$3F,\$01 + ASCII_OFFSET
.byte \$50,\$50,\$04,\$02 + ASCII_OFFSET
.byte \$60,\$4C,\$2D,\$02 + ASCII_OFFSET
.byte \$0C,\$48,\$56,\$02 + ASCII_OFFSET
.byte \$1C,\$44,\$1B,\$03 + ASCII_OFFSET
.byte \$2C,\$40,\$44,\$03 + ASCII_OFFSET
.byte \$3C,\$3C,\$09,\$04 + ASCII_OFFSET
.byte \$4C,\$38,\$32,\$04 + ASCII_OFFSET
.byte \$5C,\$34,\$5B,\$04 + ASCII_OFFSET
.byte \$08,\$30,\$20,\$05 + ASCII_OFFSET
.byte \$18,\$2C,\$49,\$05 + ASCII_OFFSET
.byte \$28,\$28,\$0E,\$06 + ASCII_OFFSET

ShiftedBcdTab
.byte \$00,\$01,\$02,\$03,\$04,\$08,\$09,\$0A,\$0B,\$0C
.byte \$10,\$11,\$12,\$13,\$14,\$18,\$19,\$1A,\$1B,\$1C
.byte \$20,\$21,\$22,\$23,\$24,\$28,\$29,\$2A,\$2B,\$2C
.byte \$30,\$31,\$32,\$33,\$34,\$38,\$39,\$3A,\$3B,\$3C
.byte \$40,\$41,\$42,\$43,\$44,\$48,\$49,\$4A,\$4B,\$4C

StartHexToDec:
lda    hexHigh               ;3  @3
and    #\$0F                  ;2  @5
tax                          ;2  @7
eor    hexHigh               ;3  @10
lsr                          ;2  @12   carry is clear, shifting just 2 times instead of 4,
lsr                          ;2  @14   since interlaced tables are used.
tay                          ;2  @16
lda    Times4096_High,Y      ;4  @20
sta    decTenThousands       ;3  @23
lda    Times4096_Low,Y       ;4  @27
sta    temp                  ;3  @34
lda    Times4096_Med,Y       ;4  @38
tay                          ;2  @44

lda    hexLow                ;3  @47
and    #\$F0                  ;2  @49
lsr                          ;2  @51
lsr                          ;2  @53
tax                          ;2  @55
tya                          ;2  @57
cpx    #13*4                 ;2  @59   times 4 due to interlaced table
cpx    #7*4                  ;2  @63
tay                          ;2  @67

lda    hexLow                ;3  @70
and    #\$0F                  ;2  @72
bcs    .sub100               ;2³ @81/82
cmp    #100                  ;2  @83
bcc    .skip1                ;2³ @85/86

.sub100:
sbc    #100                  ;2  @87
iny                          ;2  @89
.skip1:
cmp    #100                  ;2  @91
bcc    .skip2                ;2³ @93/94
sbc    #100                  ;2  @95
iny                          ;2  @97
.skip2:
lsr                          ;2  @99
tax                          ;2  @101
lda    ShiftedBcdTab,X       ;4  @105
tax                          ;2  @107
rol                          ;2  @109
and    #\$0F                  ;2  @111
IF ASCII_OFFSET
ora    #ASCII_OFFSET         ;2
ENDIF
sta    decOnes               ;3  @114

txa                          ;2  @116
lsr                          ;2  @118
lsr                          ;2  @120
lsr                          ;2  @122
IF ASCII_OFFSET
ora    #ASCII_OFFSET         ;2
ENDIF
tax                          ;2  @124   or STA decTens
tya                          ;2  @126
cmp    #100                  ;2  @128
bcc    .skip3                ;2³ @130/131
sbc    #100                  ;2  @132
inc    decTenThousands       ;5  @137
.skip3:
lsr                          ;2  @139
tay                          ;2  @141
lda    ShiftedBcdTab,Y       ;4  @145
tay                          ;2  @147
rol                          ;2  @149
and    #\$0F                  ;2  @151

IF ASCII_OFFSET
ora    #ASCII_OFFSET         ;2
ENDIF
sta    decHundreds           ;3  @154

tya                          ;2  @156
lsr                          ;2  @158
lsr                          ;2  @160
lsr                          ;2  @162
IF ASCII_OFFSET
ora    #ASCII_OFFSET         ;2
ENDIF
;   A = decThousands

Last edited by Omegamatrix on Sun Jun 15, 2014 10:00 pm, edited 2 times in total.

Top

 Post subject: Re: Hex to DecimalPosted: Sun Jun 15, 2014 11:56 am

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20402
Location: NE Indiana, USA (NTSC)
Very fast. Such efficiency. Wow.

To save 2 cycles and 2 bytes, can this:
Code:
lda    hexHigh               ;3  @3
and    #\$F0                  ;2  @5
lsr                          ;2  @7
lsr                          ;2  @9    carry is clear, shifting just 2 times instead of 4,
tay                          ;2  @11   since interlaced tables are used.
lda    hexHigh               ;3  @14
and    #\$0F                  ;2  @16
tax                          ;2  @18

be replaced with this?
Code:
lda    hexHigh               ;3  @3    fedcba98
and    #\$0F                  ;2  @5    ....ba98
tax                          ;2  @7
eor    hexHigh               ;3  @10   fedc....
lsr                          ;2  @12   .fedc...
lsr                          ;2  @14   ..fedc..   carry is clear, shifting twice
tay                          ;2  @16   instead of 4, since interlaced tables are used.

To save one byte of RAM, can decThousands be the same address as temp?

Source-wise, you don't need the constant CONVERT_TO_ASCII. Instead, the ORs can be wrapped with IF ASCII_OFFSET.

Currently, the ora #ASCII_OFFSET statements require ASCII_OFFSET to be a multiple of \$10. Allowing it to be not a multiple, such as storing the digits at \$06-\$0F, would take additional bytes to ensure that the carry is clear. I'm looking into how many additional cycles those would take. The one for decOnes and decHundreds would take no additional cycles by turning rol A and #\$0F into and #\$07 rol A because the carry out of the rotation isn't used. But the ones for decTens and decThousands lack a convenient and instruction before it. Cost: 4 cycles, 2 bytes.

Top

 Post subject: Re: Hex to DecimalPosted: Sun Jun 15, 2014 12:19 pm

Joined: Mon Jan 03, 2005 10:36 am
Posts: 3110
Location: Tampere, Finland
Cool. Coincidentally only a few days ago I was looking for a 16-bit decimal conversion routine, so I'll probably give this one a shot.

_________________
Download STREEMERZ for NES from fauxgame.com! — Some other stuff I've done: fo.aspekt.fi

Top

 Post subject: Re: Hex to DecimalPosted: Sun Jun 15, 2014 12:31 pm

Joined: Tue Jun 10, 2014 8:15 pm
Posts: 35
tepples wrote:
Very fast. Such efficiency. Wow.

To save 2 cycles and 2 bytes, can this:
Code:
lda    hexHigh               ;3  @3
and    #\$F0                  ;2  @5
lsr                          ;2  @7
lsr                          ;2  @9    carry is clear, shifting just 2 times instead of 4,
tay                          ;2  @11   since interlaced tables are used.
lda    hexHigh               ;3  @14
and    #\$0F                  ;2  @16
tax                          ;2  @18

be replaced with this?
Code:
lda    hexHigh               ;3  @3    fedcba98
and    #\$0F                  ;2  @5    ....ba98
tax                          ;2  @7
eor    hexHigh               ;3  @10   fedc....
lsr                          ;2  @12   .fedc...
lsr                          ;2  @14   ..fedc..   carry is clear, shifting twice
tay                          ;2  @16   instead of 4, since interlaced tables are used.

Ha! That is a good eye. I haven't tried it yet, but looking at it I would say yes you can. The routine also executes that part of the code every time, so every execution case has been made better. Very cool, and I'll have to remember that trick (never thought of using it before).

tepples wrote:
To save one byte of RAM, can decThousands be the same address as temp?

Yep. I was going to actually going to equate it like that at the top, but I figured it was something people would do anyhow.

tepples wrote:
Source-wise, you don't need the constant CONVERT_TO_ASCII. Instead, the ORs can be wrapped with IF ASCII_OFFSET.

Currently, the ora #ASCII_OFFSET statements require ASCII_OFFSET to be a multiple of \$10. Allowing it to be not a multiple, such as storing the digits at \$06-\$0F, would take additional bytes to ensure that the carry is clear. I'm looking into how many additional cycles those would take. The one for decOnes and decHundreds would take no additional cycles by turning rol A and #\$0F into and #\$07 rol A because the carry out of the rotation isn't used. But the ones for decTens and decThousands lack a convenient and instruction before it. Cost: 4 cycles, 2 bytes.

I don't 100% follow what you are trying to do here so I'll wait and see what you come up with. Please continue to optimize the routine if you can.

Top

 Post subject: Re: Hex to DecimalPosted: Sun Jun 15, 2014 1:01 pm

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20402
Location: NE Indiana, USA (NTSC)
Omegamatrix wrote:
I don't 100% follow what you are trying to do here

Raw digits: \$00 means zero and \$09 means 9.
ASCII: \$30 means zero and \$39 means 9.
Possible layout of tiles in an actual game: \$06 means zero and \$0F means 9, or \$F6 means zero and \$FF means 9.

Top

 Post subject: Re: Hex to DecimalPosted: Sun Jun 15, 2014 2:21 pm

Joined: Tue Jun 10, 2014 8:15 pm
Posts: 35
tepples wrote:
Omegamatrix wrote:
I don't 100% follow what you are trying to do here

Raw digits: \$00 means zero and \$09 means 9.
ASCII: \$30 means zero and \$39 means 9.
Possible layout of tiles in an actual game: \$06 means zero and \$0F means 9, or \$F6 means zero and \$FF means 9.

Gotcha. This is my in-experience with the NES coming into play ha ha.

I tested your optimization and it worked as expected. I then also changed the code so that Y ends with decThousands, and X ends with decTens. I thought about this before, but thought it might be too messy. I changed my mind because X and Y get trashed anyhow, and it's easy enough for someone to change it back if they like.

Doing so saved an additional 2 cycles and 2 bytes, and with your savings the code runs quicker and shorter then ever before. I've updated the first post with the new routine, and I also put in the equate to specify the temp ram.

Top

 Post subject: Re: Hex to DecimalPosted: Sun Jun 15, 2014 5:05 pm

Joined: Tue Jun 10, 2014 8:15 pm
Posts: 35
I have some other Hex to Decimal routines. Here is one I wrote that takes converts 0-63 hex to 0-99 BCD. It doesn't split the digits apart but keeps them in the same bytes. The routine is doing a divide by 10 and then times it by 6 before adding it back to the original sum. The good thing about this routine is that it is constant cycles.
Code:
;Hex to BCD (good 0-99)
;24 bytes, 39 cycles
sta  temp
lsr
ror
lsr
lsr
ror
ror
lsr
and  #\$3C
sta  temp2
lsr

Next (and this won't work on the NES, but hey maybe some other programmers might be reading this) I wrote one that used BCD mode to help the conversion:
Code:
;Hex to BCD (good 0-99)
;24 bytes, 28 cycles
tay              ;2  @2
lsr              ;2  @4
lsr              ;2  @6
lsr              ;2  @8
lsr              ;2  @10
tax              ;2  @12
tya              ;2  @14
and  #\$0F        ;2  @16
sed              ;2  @18
clc              ;2  @20
cld              ;2  @28

BcdTab:
.byte \$00,\$16,\$32,\$48,\$64,\$80,\$96

It was at this point where I became interested in the NES, and splitting the individual digits apart. I have some more routines that I wrote which I will post at another time that does this. There is also a nice compact routine that Bregalad wrote and Movax12 helped improved. At the end of the thread I reduced it a few more bytes as well.

Top

 Post subject: Re: Hex to DecimalPosted: Sun Jun 15, 2014 5:37 pm

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20402
Location: NE Indiana, USA (NTSC)
Thanks.

Got anything to do 0-255 to three digits? My current routine is 53 bytes and takes 80 cycles including the RTS.
Code:
.macro bcd8bit_iter value
.local skip
cmp value
bcc skip
sbc value
skip:
rol highDigits
.endmacro

;;
; Converts a decimal number to two or three BCD digits
; in no more than 80 cycles.
; @param a the number to change
; @return a: low digit; 0: upper digits as nibbles
; No other memory or register is touched.
.proc bcd8bit
highDigits = 0

; First clear out two bits of highDigits.  (The conversion will
; fill in the other six.)
asl highDigits
asl highDigits

; Each iteration takes 11 if subtraction occurs or 10 if not.
; But if 80 is subtracted, 40 and 20 aren't, and if 200 is
; subtracted, 80 is not, and at least one of 40 and 20 is not.
; So this part takes up to 6*11-2 cycles.
bcd8bit_iter #200
bcd8bit_iter #100
bcd8bit_iter #80
bcd8bit_iter #40
bcd8bit_iter #20
bcd8bit_iter #10
rts
.endproc

Top

 Post subject: Re: Hex to DecimalPosted: Sun Jun 15, 2014 6:10 pm

Joined: Tue Jun 10, 2014 8:15 pm
Posts: 35
tepples wrote:
Thanks.

Got anything to do 0-255 to three digits? My current routine is 53 bytes and takes 80 cycles including the RTS.

Yes I do have some three digits. I am just preparing supper so I'll take a look in a bit. I also just realized I'm using a TAY at the end of the 16 bit routine for no reason. I could just return the value in A, and save 2 cycles and a byte. I'll update that later.

Top

 Post subject: Re: Hex to DecimalPosted: Sun Jun 15, 2014 9:31 pm

Joined: Tue Jun 10, 2014 8:15 pm
Posts: 35
Okay here is one that I just tweaked to handle both (0-99) and (0-255) separately. It takes 43 bytes and cycles are listed below including the 12 cycles for jumping and returning from the subroutines.

Edit - This is now rev 3... uses less bytes, slightly faster average execution time, and the BIT instruction has changed. ASCII support is now optional for 2 more cycles and 2 more bytes.

Code:
;--------------------------------
;0-99 conversion stats
;--------------------------------
;cycles  occurances
;28  -  10
;31  -  10
;34  -  10
;37  -  10
;39  -  10
;42  -  10
;45  -  10
;48  -  10
;50  -  10
;56  -  10

;average execution is 41 cycles

;--------------------------------
;0-255 conversion stats
;--------------------------------
;cycles  occurances
;35  -  10
;38  -  10
;41  -  10
;43  -  10
;44  -  10
;46  -  30
;49  -  30
;52  -  26
;54  -  10
;55  -  10
;57  -  30
;60  -  20
;63  -  20
;65  -  10
;68  -  10
;71  -  10

;average execution is 52.78 cycles

Here are the routines. You start with the value in A, and at the end of the routine A = Ones digit, X = Tens digit, and Y = Hundreds digit (when using 0-255) conversion. Y is not used for the HexToDec99 subroutine.
Code:
;---------------------------------------
;  0-255 Hex to Decimal conversion
;  By Omegamatrix (rev 3)
;  35-71 cycles, average 52.78 cycles
;---------------------------------------

;change to \$30 for ASCII support. Adds 2 cycles and 2 bytes.
ASCII_OFFSET = \$00

HexToDec255; SUBROUTINE
ldy    #0 + ASCII_OFFSET
cmp    #100                  ; A = 0-255
bcc    .done100
iny
sbc    #200
bcc    .use100
iny                          ; If a mapper conflicts with SBC #-101 (becomes BIT \$9BE9), then you can try:
.byte \$2C                    ; - 'BNE .done100' instead of .byte \$2C, as Y=2 or Y=\$32 at this point...
.use100
sbc    #-101                 ; - substitute with SBC #-101 with ADC #100 (which would become BIT \$6469)
.done100:
; Y = decimal hundreds

;---------------------------------------
;  0-99 Hex to Decimal conversion
;  By Omegamatrix (rev 3)
;  28-56 cycles, average 41 cycles
;---------------------------------------

HexToDec99; SUBROUTINE
ldx    #0 + ASCII_OFFSET
cmp    #50                   ; A = 0-99
bcc    .try20
sbc    #50
ldx    #5 + ASCII_OFFSET
bne    .try20                ; always branch

.div20:
inx
inx
sbc    #20
.try20:
cmp    #20
bcs    .div20
.try10:
cmp    #10
bcc    .finished
sbc    #10
inx
.finished:
IF ASCII_OFFSET
ora    #ASCII_OFFSET
ENDIF
; X = decimal tens
; A = decimal ones
rts

Last edited by Omegamatrix on Wed Jun 18, 2014 7:17 am, edited 3 times in total.

Top

 Post subject: Re: Hex to DecimalPosted: Mon Jun 16, 2014 11:04 pm

Joined: Tue Jun 10, 2014 8:15 pm
Posts: 35
I updated the Hex to Decimal routine (0-255) to rev 2 in the above post. I've chopped 3 bytes out of the old routine and slightly speed it up.

I'm doing BIT \$6469 to skip over the ADC #100. From what I've seen of the NES memory map \$6469 is just SRAM so reading there should be no problem...

Top

 Post subject: Re: Hex to DecimalPosted: Tue Jun 17, 2014 2:25 am

Joined: Mon Jan 03, 2005 10:36 am
Posts: 3110
Location: Tampere, Finland
Omegamatrix wrote:
I'm doing BIT \$6469 to skip over the ADC #100. From what I've seen of the NES memory map \$6469 is just SRAM so reading there should be no problem...

The cartridge is free to map whatever it wants at \$6469. In fact, all of \$4020..\$FFFF. It could be RAM, ROM, mapper registers or nothing (= open bus). Most of the time it's (S)RAM or nothing, though.

_________________
Download STREEMERZ for NES from fauxgame.com! — Some other stuff I've done: fo.aspekt.fi

Top

 Post subject: Re: Hex to DecimalPosted: Tue Jun 17, 2014 6:53 am

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20402
Location: NE Indiana, USA (NTSC)
But so long as the cart doesn't put something with read side effects into \$6xxx, BIT \$6469 should work. (The addresses with read side effects on the NES are \$2002, \$2007, \$4015-\$4017, and \$4020-\$5FFF for the Vs. System's credit acknowledge.) The only mapper that I can think of that has read side effects there is Bandai boards with an I²C EEPROM.

Top

 Post subject: Re: Hex to DecimalPosted: Tue Jun 17, 2014 5:24 pm

Joined: Sun Jan 02, 2011 11:50 am
Posts: 522
Omegamatrix, nice code, but what I am more interested in at the moment is how you determine the following:

Code:
;--------------------------------
;0-99 conversion stats
;--------------------------------
;cycles  occurances
;28  -  10
;31  -  10
;34  -  10
;37  -  10
;39  -  10
;42  -  10
;45  -  10
;48  -  10
;50  -  10
;56  -  10

;average execution is 41 cycles

What method/tools do you use to create that information?

Top

 Post subject: Re: Hex to DecimalPosted: Tue Jun 17, 2014 5:46 pm

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20402
Location: NE Indiana, USA (NTSC)
I can't speak for the OP's methodology, but I wrote a 6502 simulator in Python so that I could run automated unit tests on 6502 code. With peek(), poke(), and jsr() functions, I can determine whether a subroutine returns a correct result and how long it takes. Combining such a simulator with collections.Counter makes it easy to test all combinations of parameters and produce a cycle count histogram.

Want to see my simulator?

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 2 [ 26 posts ] Go to page 1, 2  Next

 All times are UTC - 7 hours