ITOA in 65 bytes

[Robert Prins]

Is it possible to fit the conversion of a 16 bit signed integer to left-aligned
ASCII without leading zeroes in just 65 bytes?
--
Robert AH Prins
robert(a)prino(d)org
The hitchhiking grandfather - https://prino.neocities.org/indez.html
Some REXX code for use on z/OS - https://prino.neocities.org/zOS/zOS-Tools.html

[Terje Mathisen]

Robert Prins wrote:
> Is it possible to fit the conversion of a 16 bit signed integer to
> left-aligned ASCII without leading zeroes in just 65 bytes?

Naively I would say yes: I assume you don't care about speed here?

;; AX has the value to be converted to ascii
;; Store the string to the buffer pointed to by DI

xor cx,cx ; Count how many digits we find
test ax,ax ; Positive?
jge next

;; Negative input value, so print a '-' sign
mov byte ptr [di],'-'
neg ax
inc di

next:
xor dx,dx
mov bx,10
div bx
push dx ; Remainder is the digit
inc cx
test ax,ax ; Is it zero yet?
jnz next

dump_digits:
pop ax
add al,'0'
stosb
loop dump_digits

That looks like 17 instructions, most of them two-byte, 5 one-byte and a
couple that are longer, so 32-35 bytes?

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

[Kerr-Mudd, John]

On Fri, 14 May 2021 21:53:32 +0200
Terje Mathisen <terje.m...@nospicedham.tmsw.no> wrote:

> Robert Prins wrote:
> > Is it possible to fit the conversion of a 16 bit signed integer to
> > left-aligned ASCII without leading zeroes in just 65 bytes?
>
> Naively I would say yes: I assume you don't care about speed here?
>
> ;; AX has the value to be converted to ascii

[code elided]
I took the liberty of moving the "mov bx,10" out of the loop!
NASM .lst file:


1 org 0x100
2 cpu 8086
3
4 ;; AX has the value to be converted to ascii
5 ;; Store the string to the buffer pointed to by DI
6 00000000 B80180 mov ax,0x8001
7 00000003 BF[3000] mov di,Ostr
8
9 putnum:
10 00000006 31C9 xor cx,cx ; Count how many digits we find
11 00000008 85C0 test ax,ax ; Positive?
12 0000000A 7D09 jge next
13
14 ;; Negative input value, so print a '-' sign
15 0000000C C6052D mov byte [di],'-'
16 0000000F F7D8 neg ax
17 00000011 47 inc di
18
19 00000012 BB0A00 mov bx,10
20
21 next:
22 00000015 31D2 xor dx,dx
23 00000017 F7F3 div bx
24 00000019 52 push dx ; Remainder is the digit
25 0000001A 41 inc cx
26 0000001B 85C0 test ax,ax ; Is it zero yet?
27 0000001D 75F6 jnz next
28
29 dump_digits:
30 0000001F 58 pop ax
31 00000020 0430 add al,'0'
32 00000022 AA stosb
33 00000023 E2FA loop dump_digits
34
35 convlth equ $-putnum
36
37 00000025 B82409 mov ax,0x100*9+'$'
38 00000028 AA stosb
39 00000029 BA[3000] mov dx,Ostr
40 0000002C CD21 int 0x21
41 0000002E C3 ret
42 0000002F 1F db convlth
43 Ostr equ $

> That looks like 17 instructions, most of them two-byte, 5 one-byte and a
> couple that are longer, so 32-35 bytes?

1F=31 bytes


--
Bah, and indeed Humbug.

[Kerr-Mudd, John]

On Sat, 15 May 2021 11:21:43 +0100
"Kerr-Mudd, John" <ad...@nospicedham.127.0.0.1> wrote:

> On Fri, 14 May 2021 21:53:32 +0200
> Terje Mathisen <terje.m...@nospicedham.tmsw.no> wrote:
>
> > Robert Prins wrote:
> > > Is it possible to fit the conversion of a 16 bit signed integer to
> > > left-aligned ASCII without leading zeroes in just 65 bytes?
> >
> > Naively I would say yes: I assume you don't care about speed here?
> >
> > ;; AX has the value to be converted to ascii
> [code elided]
> I took the liberty of moving the "mov bx,10" out of the loop!

How embarrassing; needs bx setting if +ve!

> NASM .lst file:
>
1 org 0x100
2 cpu 8086
3
4 ;; AX has the value to be converted to ascii
5 ;; Store the string to the buffer pointed to by DI

6 00000000 B8FF7F mov ax,0x7FFF
7 00000003 BF[2F00] mov di,Ostr

8
9 putnum:
10 00000006 31C9 xor cx,cx ; Count how many digits we find
11 00000008 85C0 test ax,ax ; Positive?

12 0000000A 7D06 jge notneg

13
14 ;; Negative input value, so print a '-' sign
15 0000000C C6052D mov byte [di],'-'
16 0000000F F7D8 neg ax
17 00000011 47 inc di

18 notneg:

19 00000012 BB0A00 mov bx,10
20
21 next:

22 ; xor dx,dx
23 00000015 99 cwd ; ok as hibit has been removed
24 00000016 F7F3 div bx
25 00000018 52 push dx ; Remainder is the digit
26 00000019 41 inc cx
27 0000001A 85C0 test ax,ax ; Is it zero yet?
28 0000001C 75F7 jnz next
29
30 dump_digits:
31 0000001E 58 pop ax
32 0000001F 0430 add al,'0'
33 00000021 AA stosb
34 00000022 E2FA loop dump_digits
35
36 convlth equ $-putnum
37
38 00000024 B82409 mov ax,0x100*9+'$'
39 00000027 AA stosb
40 00000028 BA[2F00] mov dx,Ostr
41 0000002B CD21 int 0x21
42 0000002D C3 ret
43 0000002E 1E db convlth
44 Ostr equ $

>
> > That looks like 17 instructions, most of them two-byte, 5 one-byte and a
> > couple that are longer, so 32-35 bytes?
>

> 1E=30 bytes

[Terje Mathisen]

The CWD was a valid improvement, moving BX=10 out of the loop probably
doesn't matter that much since the DIV BX takes forever. :-(

The key idea here is of course that I abuse the stack as temporary
storage to reverse the digits to be printed, since the challenge was to
get below 65 bytes I think my code was pretty good for a simple
"programming while responding to clax post" exercise. :-)

I did consider printing each digit directly to the console, it probably
would not have added much to the code size for an unsigned value, but
getting the sign logic correct was much easier when using the STOSB buffer.

xor cx,cx
test ax,ax
jge not_negative

xchg ax,bx
mov dl,'-' - '0'
call print_char
xchg ax,bx
neg ax

not_negative:
mov bx,10
next:
...
test ax,ax
jnz next

print_digits:
pop dx
call print_char
loop print_digits
ret

print_char:
add dl,'0'
mov ah,2
int 21h
ret

[R.Wieser]

> Is it possible to fit the conversion of a 16 bit signed integer to
> left-aligned
> ASCII without leading zeroes in just 65 bytes?

As no specifications have been posted, I do have some code that outputs a
signed number using just 25 bytes.

The trick ? Filling the buffer backwards (putting the sign at the end).

Regards,
Rudy Wieser

[Robert Prins]

The code is replacement code for the itoa routine in the Borland TP3 compiler,
so it has to give the same result.

Robert

[Kerr-Mudd, John]

On Sat, 15 May 2021 19:46:21 +0200

Terje Mathisen <terje.m...@nospicedham.tmsw.no> wrote:

> Kerr-Mudd, John wrote:
> > On Sat, 15 May 2021 11:21:43 +0100
> > "Kerr-Mudd, John" <ad...@nospicedham.127.0.0.1> wrote:
> >
> >> On Fri, 14 May 2021 21:53:32 +0200
> >> Terje Mathisen <terje.m...@nospicedham.tmsw.no> wrote:
> >>
> >>> Robert Prins wrote:
> >>>> Is it possible to fit the conversion of a 16 bit signed integer to
> >>>> left-aligned ASCII without leading zeroes in just 65 bytes?
> >>>
> >>> Naively I would say yes: I assume you don't care about speed here?
> >>>
> >>> ;; AX has the value to be converted to ascii
> >> [code elided]
>

>

Dirty trick, saves a call/ret:

xor cx,cx
test ax,ax
jge not_negative

xchg ax,bx
mov dl,'-'

inc cx ; print once!

call print_char
xchg ax,bx
neg ax

not_negative:
mov bx,10
next:
...
test ax,ax
jnz next

print_digits:
pop dx

; print_*num*:
add dl,'0'
print_char:
mov ah,2
int 21h
loop print_digits
ret

[R.Wieser]

Robert,

> The code is replacement code for the itoa routine in the Borland TP3
> compiler, so it has to give the same result.

I took my clues from the code Terje posted, which seemed to indicate that
anything goes (not actually outputting anything, non-terminated string,
inline). :-)

And alas, as I'm using an assembler that doesn't tell me anything ...

Should the sign be on the left
Should only the negative sign be displayed or both.
Should the positive sign be replaced by a space
Should the string be put into a buffer
Should it than be either zero or "$' terminated
Should the string-end position be returned and if so in which register
Should it be send to STDOUT
Should it be a function or in-line
... any other relevant specs I've not mentioned

Regards,
Rudy Wieser

[Terje Mathisen]

Robert Prins wrote:
> On 2021-05-16 08:25, R.Wieser wrote:
>>> Is it possible to fit the conversion of a 16 bit signed integer to
>>> left-aligned
>>> ASCII without leading zeroes in just 65 bytes?
>>
>> As no specifications have been posted, I do have some code that outputs a
>> signed number using just 25 bytes.
>>
>> The trick ?    Filling the buffer backwards (putting the sign at the
>> end).
>
> The code is replacement code for the itoa routine in the Borland TP3
> compiler, so it has to give the same result.

Why didn't you state so?

The key here is that this function returns a TP string, right?

This means that the space for it has to be allocated, but I don't
remember anymore if that is done by the caller or callee in that
environment?

[Robert Prins]

On 2021-05-16 13:09, Terje Mathisen wrote:
> Robert Prins wrote:
>> On 2021-05-16 08:25, R.Wieser wrote:
>>>> Is it possible to fit the conversion of a 16 bit signed integer to
>>>> left-aligned
>>>> ASCII without leading zeroes in just 65 bytes?
>>>
>>> As no specifications have been posted, I do have some code that outputs a
>>> signed number using just 25 bytes.
>>>
>>> The trick ?    Filling the buffer backwards (putting the sign at the end).
>>
>> The code is replacement code for the itoa routine in the Borland TP3 compiler,
>> so it has to give the same result.
>
> Why didn't you state so?

I should have done earlier, rather than in that follow-up, apologies.

> The key here is that this function returns a TP string, right?

No, see the code of the current routine I also posted. It puts the result into a
22-byte fixed buffer @ DS:00B6 and from there it's processed further.

> This means that the space for it has to be allocated, but I don't remember
> anymore if that is done by the caller or callee in that environment?

The TP3 manual is silent about this for strings, but looking at the only
procedure that actually returns a string, it looks like the caller sets up the
space for the string to be returned.

For what it's worth, -32768 is problematic for all routines posted, it doesn't
change sign when negated! TP3 also doesn't accept it as valid integer, unless
coded as $8000.

[Kerr-Mudd, John]

On Sun, 16 May 2021 20:11:15 +0000
Robert Prins <rob...@nospicedham.prino.org> wrote:

> On 2021-05-16 13:09, Terje Mathisen wrote:
> > Robert Prins wrote:
> >> On 2021-05-16 08:25, R.Wieser wrote:
> >>>> Is it possible to fit the conversion of a 16 bit signed integer to
> >>>> left-aligned
> >>>> ASCII without leading zeroes in just 65 bytes?
> >>>
> >>> As no specifications have been posted, I do have some code that outputs a
> >>> signed number using just 25 bytes.
> >>>
> >>> The trick ?    Filling the buffer backwards (putting the sign at the end).
> >>
> >> The code is replacement code for the itoa routine in the Borland TP3 compiler,
> >> so it has to give the same result.
> >
> > Why didn't you state so?
>
> I should have done earlier, rather than in that follow-up, apologies.
>
> > The key here is that this function returns a TP string, right?
>
> No, see the code of the current routine I also posted.

Not that I've seen on this NG.

> For what it's worth, -32768 is problematic for all routines posted, it doesn't
> change sign when negated! TP3 also doesn't accept it as valid integer, unless
> coded as $8000.
>
> Robert
> --
> Robert AH Prins
> robert(a)prino(d)org
> The hitchhiking grandfather - https://prino.neocities.org/indez.html
> Some REXX code for use on z/OS - https://prino.neocities.org/zOS/zOS-Tools.html
>

[R.Wieser]

Robert,

> No, see the code of the current routine I also posted.

Missing : the current routine.

> For what it's worth, -32768 is problematic for all routines posted, it
> doesn't change sign when negated!

:-) You forgot that after the sign change part you have an unsigned value.
And in that mode 0x8000 is decimally represented as 32768. The initial code
Terje posted, with its "xor dx,dx" (instead of the later, shorter "cwd"),
does the job as expected.

Still also missing : a description of what the TP6 output should look like.

Regards,
Rudy Wieser

[Robert Prins]

On 2021-05-16 16:58, Kerr-Mudd, John wrote:
> On Sun, 16 May 2021 20:11:15 +0000
> Robert Prins <rob...@nospicedham.prino.org> wrote:
>
>> On 2021-05-16 13:09, Terje Mathisen wrote:
>>> Robert Prins wrote:
>>>> On 2021-05-16 08:25, R.Wieser wrote:
>>>>>> Is it possible to fit the conversion of a 16 bit signed integer to
>>>>>> left-aligned
>>>>>> ASCII without leading zeroes in just 65 bytes?
>>>>>
>>>>> As no specifications have been posted, I do have some code that outputs a
>>>>> signed number using just 25 bytes.
>>>>>
>>>>> The trick ?    Filling the buffer backwards (putting the sign at the end).
>>>>
>>>> The code is replacement code for the itoa routine in the Borland TP3 compiler,
>>>> so it has to give the same result.
>>>
>>> Why didn't you state so?
>>
>> I should have done earlier, rather than in that follow-up, apologies.
>>
>>> The key here is that this function returns a TP string, right?
>>
>> No, see the code of the current routine I also posted.
>
> Not that I've seen on this NG.

Then once again it has not gone through. I'll repost it to the direct moderator
address.

[Robert Prins]

-------- Forwarded Message --------
Subject: Re: ITOA in 65 bytes
Date: Sat, 15 May 2021 19:01:58 +0000
From: Robert Prins <rob...@prino.org>
Newsgroups: comp.lang.asm.x86
References: <s7m8nd$f4p$1...@dont-email.me> <s7mkfs$196d$1...@gioia.aioe.org>

On 2021-05-14 19:53, Terje Mathisen wrote:
> Robert Prins wrote:
>> Is it possible to fit the conversion of a 16 bit signed integer to
>> left-aligned ASCII without leading zeroes in just 65 bytes?
>

> Naively I would say yes: I assume you don't care about speed here?

You're getting soft... ;)

Anyway, this is the original TP3 RTL code, which uses repeated subtractions, as
disassembled by Hex-Rays' IDA Pro

111B intasc proc near
111B 0B C0 or ax, ax
111D 79 06 jns short iapos
111F F7 D8 neg ax
1121 C6 07 2D mov byte ptr [bx], '-'
1124 43 inc bx
1125
1125 iapos:
1125 32 ED xor ch, ch
1127 BA 10 27 mov dx, 10000
112A E8 15 00 call iadigit
112D BA E8 03 mov dx, 1000
1130 E8 0F 00 call iadigit
1133 BA 64 00 mov dx, 100
1136 E8 09 00 call iadigit
1139 B2 0A mov dl, 10
113B E8 04 00 call iadigit
113E 8A C8 mov cl, al
1140 EB 14 jmp short iadput
1140 intasc endp
1140
1142
1142 iadigit proc near
1142
1142 32 C9 xor cl, cl
1144
1144 iadsub:
1144 FE C1 inc cl
1146 2B C2 sub ax, dx
1148 73 FA jnb short iadsub
114A 03 C2 add ax, dx
114C FE C5 inc ch
114E FE C9 dec cl
1150 75 04 jnz short iadput
1152 FE CD dec ch
1154 74 06 jz short iadnoput
1156
1156 iadput:
1156 80 C1 30 add cl, '0'
1159 88 0F mov [bx], cl
115B 43 inc bx
115C
115C iadnoput:
115C C3 retn
115C iadigit endp

>
> ;; AX has the value to be converted to ascii

> ;; Store the string to the buffer pointed to by DI
>

>   xor cx,cx    ; Count how many digits we find

>   test ax,ax    ; Positive?
>    jge next
>

> ;; Negative input value, so print a '-' sign

>   mov byte ptr [di],'-'
>   neg ax
>   inc di
>
> next:
>   xor dx,dx
>   mov bx,10
>   div bx

>   push dx    ; Remainder is the digit

>   inc cx

>   test ax,ax    ; Is it zero yet?

>    jnz next
>
> dump_digits:
>   pop ax
>   add al,'0'
>   stosb
>    loop dump_digits
>

> That looks like 17 instructions, most of them two-byte, 5 one-byte and a couple
> that are longer, so 32-35 bytes?

I've done a check, and found that a multiply of eax by 0x1999_999a works over
the full 16 bit range to divide by 10 without requiring additional shifts. Of
course it needs a back-multiply and subtraction to actually get the digit.
However, even the above code using a divide will quite likely be (significantly)
faster than the multiple subtraction loops in the original RTL. (And having
mentioned multiplying eax, it should be clear that I don't really care about
keeping the RTL compatible with the 8086/286, and given that replacing
Int21h/AX=2C with "RDTSC" is also an option...)

The really [b|s]ad parts of the RTL are the compares of REALs, there are six
procedures like

1A0E realeq proc near
1A0E 8F 06 86 01 pop errpos
1A12 59 pop cx
1A13 5E pop si
1A14 5F pop di
1A15 58 pop ax
1A16 5B pop bx
1A17 5A pop dx
1A18 E8 99 FE call recmp
1A1B FF 36 86 01 push errpos
1A1F B8 01 00 mov ax, 1 ; setz al
1A22 74 01 jz short realeq1 ; and ax, 1
1A24 48 dec ax
1A25
1A25 realeq1:
1A25 0B C0 or ax, ax
1A27 C3 retn
1A27 realeq endp

The last part of all of them can be replaced with a "SETcc al/and ax, 1", and
using 32 bit registers it's likely that the first nine instructions can also be
commonned out (a bit). Similar code (6x) is used for comparing strings (>, <, =,
<>, >=, <=) and pointers (2x, =, <>)

Of course all of this is strangely silly, fiddling with the RTL of a 35 year old
compiler, but it keeps me off the street, Lithuania is officially still locked
down until 31 May and it's just as much fun as hitchhiking to Nordkapp, which I
did in 1982, for more or less similar reasons, because it's there.

[Kerr-Mudd, John]

On Sun, 16 May 2021 19:56:56 +0200
"R.Wieser" <add...@nospicedham.not.available> wrote:

> Robert,
>
> > No, see the code of the current routine I also posted.
>
> Missing : the current routine.
>
> > For what it's worth, -32768 is problematic for all routines posted, it
> > doesn't change sign when negated!
>
> :-) You forgot that after the sign change part you have an unsigned value.
> And in that mode 0x8000 is decimally represented as 32768. The initial code
> Terje posted, with its "xor dx,dx" (instead of the later, shorter "cwd"),
> does the job as expected.

Sorry. I blame the tester (me).

[Kerr-Mudd, John]

On Sun, 16 May 2021 21:43:10 +0000
Robert Prins <robert....@nospicedham.gmail.com> wrote:

[]

>
> Anyway, this is the original TP3 RTL code, which uses repeated subtractions, as
> disassembled by Hex-Rays' IDA Pro

I guess on the original PCs 8088 the subtractions *were* faster?

> I've done a check, and found that a multiply of eax by 0x1999_999a works over
> the full 16 bit range to divide by 10 without requiring additional shifts. Of
> course it needs a back-multiply and subtraction to actually get the digit.
> However, even the above code using a divide will quite likely be (significantly)
> faster than the multiple subtraction loops in the original RTL. (And having
> mentioned multiplying eax, it should be clear that I don't really care about
> keeping the RTL compatible with the 8086/286, and given that replacing
> Int21h/AX=2C with "RDTSC" is also an option...)
>

[]

[Bonita Montero]

> As no specifications have been posted, I do have some code that outputs a
> signed number using just 25 bytes.
> The trick ? Filling the buffer backwards (putting the sign at the end).

Show the code !

[R.Wieser]

Bonita,

Alas, when it was made clear it had to work "just as in TP3" I threw the
code away. :-|

There was nothing special to it though. Pretty-much the same as the first
code Terje posted, just without the pushing and popping (instead directly
storing it into the buffer).

Regards,
Rudy Wieser

[Kerr-Mudd, John]

Simple enough to re-invent I'd have thought.
Something like this? (untested)


;; 16bit num in ax (max +/-32k), di is output area. uses bx,dx

add di,6 ; end of display area (possibly 5 digits & sign)
test ax,ax ; Is it positive?
jge NotNeg
mov byte [di],'-' ; put minus sign
neg ax ; show as positive
NotNeg:
mov bx,10 ; decimal
NextDigit:
xor dx,dx ; clear for div
div bx ; get digit in dl
add dl,'0'
dec di ; backward
mov [di],dl ; putc
test ax,ax ; finished?
jnz NextDigit

;;di now points to output string with '-' at the end if negative