binary to ascii

[wwl]

Hallo,

I am new to this forum. I have registered here because I found a little routine here, coded in 6502, which does a binary to ascii conversion and I could not understand fully how it is working.

I hope someone in this forum will give me some hints.

What is the name of that algorithm?
Is there any documentation on the net?

Wolfgang

[BigDumbDinosaur]

wwl wrote:

Hallo,

I am new to this forum. I have registered here because I found a little routine here, coded in 6502, which does a binary to ascii conversion and I could not understand fully how it is working.

I hope someone in this forum will give me some hints.

What is the name of that algorithm?
Is there any documentation on the net?

Wolfgang

First, welcome to our 6502 world. When you have time, please go to the "introduce yourself" topic and tell us a bit about your background and interests.

I have to confess that I haven't a clue about what that routine is doing. It appears to be pretty obfuscated and lacking comments, not readily understood. Perhaps the original author will see your query and respond.

[nyef]

This looks like a good chance to practice reverse-engineering skills. You know what the routine is supposed to do, what its inputs are, there's a cryptic hint about how it supposedly works, and you have three different variations on the routine to work with. Just looking through it, the outer loop control is fairly obvious, and the routine is short enough to easily simulate by hand with given inputs, or you could run it in a software simulator and watch the machine state at each step.

After staring at it for a bit I can tell that it's dreadfully clever, and that the hex constants loaded into the Y register (and subsequently stored in .B) serve two purposes, at least for OUTDEC8Z. The high bit is iteration control for the inner loop which runs two or four times per digit (depending on which routine and which digit), and the lower bits form part of an ASCII character.

Once you see how the input is tested and consumed, and how the output is built, and correlate that to the values in the lookup table, the cryptic hint as to how the routine works makes a lot more sense.

OUTDEC8 and OUTDEC8S have additional logic to handle the leading digit suppression, and mask in the high bits of the ASCII code just before output, while OUTDEC8Z simply arranges for the high bits of the ASCII code to already be in the output buffer at the start of each iteration.

I'm a little rusty with my 6502 assembly, but I think that the OUTDEC8 and OUTDEC8S routines might require a 65c02. I'm not certain about this, however.

On the whole, I rather like these routines, and am glad for the opportunity to study them for a few minutes.

[barrym95838]

nyef wrote:

After staring at it for a bit I can tell that it's dreadfully clever, and that the hex constants loaded into the Y register (and subsequently stored in .B) serve two purposes, at least for OUTDEC8Z. The high bit is iteration control for the inner loop which runs two or four times per digit (depending on which routine and which digit), and the lower bits form part of an ASCII character.

I agree, and I would like to place my bet for authorship on dclxvi (Bruce).

Mike

[wwl]

nyef wrote:

After staring at it for a bit I can tell that it's dreadfully clever, and that the hex constants loaded into the Y register (and subsequently stored in .B) serve two purposes, at least for OUTDEC8Z. The high bit is iteration control for the inner loop which runs two or four times per digit (depending on which routine and which digit), and the lower bits form part of an ASCII character.

I have concentrated on the first routine. And yes, it produces ascii-codes directly after 2 (4) shifts.
I have found that
128 = 2^7 * 10^0
160 = 2^4 * 10^1
200 = 2^1 * 10^2
and it is clear to me that the high bit can not be grater then 2 (2 bits), while the two other bits need 4 bits. Thats why there are 2(4) shifts and thats why there are two different starting values $4C and $13.

BUT! I do not understand WHY this all is working!

Wolfgang

[wwl]

barrym95838 wrote:

I agree, and I would like to place my bet for authorship on dclxvi (Bruce).
Mike

Is this person a member of this list?

Wolfgang

[BigDumbDinosaur]

wwl wrote:

barrym95838 wrote:

I agree, and I would like to place my bet for authorship on dclxvi (Bruce).
Mike

Is this person a member of this list?

Wolfgang

Yes he is.

[barrym95838]

wwl wrote:

... [snip] ... BUT! I do not understand WHY this all is working!

Whether or not the true author is dclxvi, you are treading water in the deep
end of the pool here. 6502 gurus like him have the ability to assemble obscure
bit patterns, instruction side-effects and sequences that work in their favor,
almost 'magically'. I do not count myself among that group, of which there
may be only a few hundred survivors ... I can only watch and admire from a
safe distance!

If you want to learn how to read and write English, do you start with Dr.
Seuss or William Shakespeare? Both methods are possible ... whether or not
both are feasible depends on the desire and aptitude of the 'student', as
well as the approachability of the 'teacher'. The terse explanation and lack
of comments in those examples puts you at a disadvantage, but if you can
figure it out on your own, you could be on your way to becoming a guru as
well. If not, you can still hang out with the rest of us 'regular guys'.

Happy coding!

Mike

[BigEd]

Agreed, both that this is Bruce's work and that it's advanced code! Picking apart the algorithm is the first challenge and the second is figuring out how to be quite so adept at using the very few registers we have.

Note that that routine converts a single byte from binary to decimal, and that it uses a lookup table. Extending to 2 or 4 byte conversion would be quite a bit of work and the code would look quite different. It's a compact solution to a very specific problem.

Bruce has quite a few interesting and substantial contributions both on this forum and as articles elsewhere on the site: see https://duckduckgo.com/?q=site%3A6502.org+bruce

Cheers
Ed

[BitWise]

I like the way the value loaded into .B controls the number of interations of the main loop. The first digit can only be 0,1 or 2 so the top nybble $4 (in $4C) allows two iterations (before the 1 bit is shifted out) while the low nybble $C becomes the top nybble of the character code $30-$32. In subsequent iterations the $13 code allows four iterations to produce $30-$39.

The loop shifts the remaining value one bit. If this sets the carry you have a $100-$1ff value that is bigger than any of the constants so it will aways subtract the next constant and shift a 1 bit into the decimal value. If there is no carry the a comparison is needed to see if the remaining value is greater than or equal to the constant (shifts in a 1 after subtracting the constant) or not (shifts in a 0).

Instead of leaving the value under conversion unscaled and subtracting 100s and 10s the algorithm scales the remaining value and subtracts a constant value from it. So this algorithm will do two iterations for the first digit and four for each of the two remaining digits.

I agree with Ed, I don't think this extends to 16-bits or more very easily. I suspect the constants would have to be extended so the value in A would have to be saved and restored during the comparison and subtraction.

Still very clever.

[GARTHWILSON]

I re-wrote the OUTDEC8 routine with the structure macros (which would give the same machine code but make the source code much more clear) and was trying to add the comments, and put it aside as it was taking so long to figure it out like I see now BitWise already did. Actually, the routines at http://6502.org/source/integers/hex2dec.htm are a little shorter.

If you have a division routine already in place for other uses though, you can convert to any base, with the same routines. The following is from my article, "Large Look-up Tables for Hyperfast, Accurate, 16-Bit Fixed-Point/Scaled-Integer Math" which also includes some general scaled-integer tutorial:

Quote:

You may be wondering about base conversions for when you want decimal input and output even though the computer internally uses hexadecimal. After all, we're also talking about handling things like decimal points and signs for input and output. It's not particularly difficult; and you can use the same routines to convert to and from any base, changing only the number in variable BASE. It does require multiplication and division, but you only do it when it's time for human I/O, and otherwise let the computer do its business efficiently in hex. The processor does not even need any decimal-mode arithmetic instructions like the 6502 & '816 have.

Here's an explanation of how, simplified not quite to the point of lying. It should give the basic understanding so you can write suitable routines. For inputting numbers from a text string (e.g. typed in from a keyboard), initialize a number as 0 to build on, then take the first digit in the string and add its value to the hex number you're building. Continue until you're out of digits, each time multiplying the build by the number in variable BASE and then adding the new digit's value to the build. If you encounter a decimal point, keep track of how many digits were after it. In Forth, the decimal point automatically makes the result double-precision; but you can convert back to single if you want to. If there was a minus sign, record that too.

For converting hex numbers to other bases for output (which will normally be a string), initialize a blank string. You will build it from right to left. Divide your number by what's in variable BASE, and use the remainder to add a text digit to the build, even if it's a 0. Keep doing that until there's 0 in the number. You can add a decimal point or other characters between digits, e.g. 12.345 or 12:36:40 (actually you might want to change BASE from 10 to 6 and back for the time readout, if you started with a number of seconds!)

The way Forth does this output number formatting is somewhat explained starting at about the middle of the page of chapter 5 of Leo Brodie's "Starting Forth" (with ANS updates here, and they're mostly calling single-precision 32-bit, like I want for the 65Org32 with all 32-bit registers).

(emphasis added)

[wwl]

I have tried to expand it to 16 bits.

The .B constants would be for

1 shift : 10011000=$98
2 shifts: 01001100=$4C
3 shifts: 00100110=$26
4 shifts: 00010011=$13

all this constants fit in 1 byte. Unfortunately the second loop (4. decimal digit) needs 5 shifts. Can anybody confirm this?

Wolfgang

[Klaus2m5]

wwl wrote:

I have tried to expand it to 16 bits.

The .B constants would be for

1 shift : 10011000=$98
2 shifts: 01001100=$4C
3 shifts: 00100110=$26
4 shifts: 00010011=$13

all this constants fit in 1 byte. Unfortunately the second loop (4. decimal digit) needs 5 shifts. Can anybody confirm this?

Wolfgang

You are mixing the compare and subtract constant table .A with the preset for .B which is only determining the number of shifts and the ASCII number offset. One decimal digit in the output is made of four bit values (1,2,4,8). So you always need four shifts to decode one digit, except the topmost digit for 16-bit is 3 shifts as it can only represent 0-6.

All operations must now be 16-bit wide including all shifts, compares and subtracts. The table for the compare and subtract operation needs 16-bit words and would represent:

2^14 * 10^0
2^11 * 10^1
2^8 * 10^2
2^5 * 10^3
2^2 * 10^4

As other people said before: it will not be easy to convert the routine to 16-bit on an 8-bit machine and it will not be that slim anymore.

[RichTW]

There wouldn't be any need for 5 shifts in the B constant, as the maximum digit is '9' which only requires a maximum of 4 shifts to build. However, in the 16 bit case, it'd be necessary to change the constant to $26 the first time round, so as to be able to build the maximum allowed first digit (6).

As for the algorithm, it is undeniably cunning, and I still haven't quite figured it out. It's doing something very similar to the standard division algorithm, but the factor of 2^n in the constants eludes me a little, as does the way it's able to start the next iteration using the value of A that results from the last one.

That said, to get it working in the 16-bit case is reasonably simple. The constants required in this case are:

$4000 = 16384 = 2^14 * 10^0
$5000 = 20480 = 2^11 * 10^1
$6400 = 25600 = 2^8 * 10^2
$7D00 = 32000 = 2^5 * 10^3
$9C40 = 40000 = 2^2 * 10^4

and "it just works". Such a shame that last one has a non-zero LSB...

Edit: Erm, yeah, what Klaus said.

[RichTW]

I don't think it'd be so ugly on an 8-bit CPU:

Code: Select all

OUTDEC16Z
    LDX #4
    LDY #$26
.1  LDA VALUELO
    CMP TABLO,X
    LDA VALUEHI
    SBC TABHI,X
    BCC .3
.2  LDA VALUELO
    SBC TABLO,X
    STA VALUELO
    LDA VALUEHI
    SBC TABHI,X
    STA VALUEHI
    SEC
.3  TYA
    ROL A
    BCS .4
    TAY
    ASL VALUELO
    ROL VALUEHI
    BCS .2
    BCC .1
.4  JSR OUTPUT
    LDY #$13
    DEX
    BPL .1
    RTS

.VALUELO DB 0
.VALUEHI DB 0
.TABLO   DB $00,$00,$00,$00,$40
.TABHI   DB $40,$50,$64,$7D,$9C

I juggled things around a bit to avoid a 16-bit right shift followed immediately by a 16-bit left shift, and I think it should work ok (disclaimer: it's completely untested). To optimise for speed (but probably not size), you could take the first iteration completely out of the loop, as it has a different magic constant and a non-zero table LSB, and then only perform comparisons and subtracts on VALUEHI in the loop.

Edit to add: just tried it now on a 6502 machine, and it works fine