Integer to ascii conversion

[LarryC]

I thought I'd post this here as well, might be of use to someone.  It does conversions in 20 to 50 cycles for 1 to 10 digit integers.

I'll post the FastProc version which should convert easily to other assemblers.

itoaFastProc.inc

Code Select Expand

#Include This Once
' Usage
' Local buffer as StringZ * 12
' itoa 1234567890, ByRef buffer

AsmData itoa_cvt
  DW &h3030, &h3130, &h3230, &h3330, &h3430, &h3530, &h3630, &h3730, &h3830, &h3930
  DW &h3031, &h3131, &h3231, &h3331, &h3431, &h3531, &h3631, &h3731, &h3831, &h3931
  DW &h3032, &h3132, &h3232, &h3332, &h3432, &h3532, &h3632, &h3732, &h3832, &h3932
  DW &h3033, &h3133, &h3233, &h3333, &h3433, &h3533, &h3633, &h3733, &h3833, &h3933
  DW &h3034, &h3134, &h3234, &h3334, &h3434, &h3534, &h3634, &h3734, &h3834, &h3934
  DW &h3035, &h3135, &h3235, &h3335, &h3435, &h3535, &h3635, &h3735, &h3835, &h3935
  DW &h3036, &h3136, &h3236, &h3336, &h3436, &h3536, &h3636, &h3736, &h3836, &h3936
  DW &h3037, &h3137, &h3237, &h3337, &h3437, &h3537, &h3637, &h3737, &h3837, &h3937
  DW &h3038, &h3138, &h3238, &h3338, &h3438, &h3538, &h3638, &h3738, &h3838, &h3938
  DW &h3039, &h3139, &h3239, &h3339, &h3439, &h3539, &h3639, &h3739, &h3839, &h3939
End AsmData

FastProc itoa( ByVal value As Long, ByVal b As Long )
#Register None
  Prefix "!"
  mov ebx, esi                      ; eax = value
  mov esi, edi                      ; esi = VarPtr( b )
  lea edi, itoa_cvt                 ; edi = cvt
  xor edx, edx                      ; edx = 0 (initial 0)
  cmp ebx, edx                      ; if value
  jge itoa_init                     ;  >= 0 Then itoa_init
  mov byte ptr[esi], 45             ; @esi = '-'
  inc esi                           ; incr esi
  neg eax                           ; eax = -eax
itoa_init:
  cmp eax, 10000
  jl itoa_digit8
  cmp eax, 10000000
  jl itoa_digit5
  cmp eax, 100000000
  jl itoa_digit4
  cmp eax, 1000000000
  jl itoa_digit3

  ;===============================
  ; 10 digits
  mov byte ptr[esi+10], 0
  jmp itoa_10
itoa_digit3:

  ;===============================
  ; 9 digits
  mov   eax, 1717986919             ; 66666667H
  mov   byte ptr [esi+9], 0
  imul  ebx
  sar   edx, 2
  mov   ebx, edx
  shr   ebx, 31                     ; 0000001fH
  add   ebx, edx
  mov   al, bl
  shl   al, 2
  lea   ecx, DWORD PTR [eax+ebx]
  mov   eax, value
  add   cl, cl
  sub   al, cl
  add   al, 48                      ; 00000030H
  mov   byte ptr [esi+8], al
  jmp itoa_8
itoa_digit4:

  ;===============================
  ; 8 digits
  mov byte ptr[esi+8], 0
  jmp itoa_8
itoa_digit5:
  cmp eax, 100000
  jl itoa_digit7
  cmp eax, 1000000
  jl itoa_6

  ;===============================
  ; 7 digits
  mov   eax, 1717986919             ; 66666667H
  mov   byte ptr [esi+7], 0
  imul  ebx
  sar   edx, 2
  mov   ebx, edx
  shr   ebx, 31                     ; 0000001fH
  add   ebx, edx
  mov   al, bl
  shl   al, 2
  lea   ecx, DWORD PTR [eax+ebx]
  mov   eax, value
  add   cl, cl
  sub   al, cl
  add   al, 48                      ; 00000030H
  mov   byte ptr [esi+6], al
  jmp itoa_6
itoa_digit6:

  ;===============================
  ; 6 digits
  mov byte ptr[esi+6], 0
  jmp itoa_6
itoa_digit7:

  ;===============================
  ; 5 digits
  mov   eax, 1717986919             ; 66666667H
  mov   byte ptr [esi+5], 0
  imul  ebx
  sar   edx, 2
  mov   ebx, edx
  shr   ebx, 31                     ; 0000001fH
  add   ebx, edx
  mov   al, bl
  shl   al, 2
  lea   ecx, DWORD PTR [eax+ebx]
  mov   eax, value
  add   cl, cl
  sub   al, cl
  add   al, 48                      ; 00000030H
  mov   byte ptr [esi+4], al
  jmp itoa_4
itoa_digit8:
  cmp eax, 100
  jl itoa_digit10
  cmp eax, 1000
  jl itoa_digit9

  ;===============================
  ; 4 digits
  mov byte ptr[esi+4], 0
  jmp itoa_4
itoa_digit9:

  ;===============================
  ; 3 digits
  mov   eax, 1717986919             ; 66666667H
  mov   byte ptr [esi+3], 0
  imul  ebx
  sar   edx, 2
  mov   ebx, edx
  shr   ebx, 31                     ; 0000001fH
  add   ebx, edx
  mov   al, bl
  shl   al, 2
  lea   ecx, DWORD PTR [eax+ebx]
  mov   eax, value
  add   cl, cl
  sub   al, cl
  add   al, 48                      ; 00000030H
  mov   byte ptr [esi+2], al
  jmp itoa_2
itoa_digit10:

  ;===============================
  ; 2 digits
  cmp eax, 10
  jl itoa_digit11
  mov byte ptr[esi+2], 0
  jmp itoa_2
itoa_digit11:

  ;===============================
  ; 1 digits
  mov   eax, 1717986919             ; 66666667H
  mov   byte ptr [esi+1], 0
  imul  ebx
  sar   edx, 2
  mov   ebx, edx
  shr   ebx, 31                     ; 0000001fH
  add   ebx, edx
  mov   al, bl
  shl   al, 2
  lea   ecx, DWORD PTR [eax+ebx]
  mov   eax, value
  add   cl, cl
  sub   al, cl
  add   al, 48                      ; 00000030H
  mov   byte ptr [esi], al
  jmp itoa_0

  ; Convert 10 digits
itoa_10:
  mov   eax, 1374389535             ; 51eb851fH
  imul  ebx
  sar   edx, 5
  mov   ecx, edx
  shr   ecx, 31                     ; 0000001fH
  add   ecx, edx
  imul  eax, ecx, 100
  sub   ebx, eax                    ; ebx = value mod 100
  mov   ax, word ptr [edi+ebx*2]
  mov   ebx, ecx                    ; ebx = value \ 100
  mov   word ptr [esi+8], ax

  ; Convert 8 digits
itoa_8:
  mov   eax, 1374389535             ; 51eb851fH
  imul  ebx
  sar   edx, 5
  mov   ecx, edx
  shr   ecx, 31                     ; 0000001fH
  add   ecx, edx
  imul  eax, ecx, 100
  sub   ebx, eax                    ; ebx = value mod 100
  mov   ax, word ptr [edi+ebx*2]
  mov   ebx, ecx                    ; ebx = value \ 100
  mov   word ptr [esi+6], ax

  ; Convert 6 digits
itoa_6:
  mov   eax, 1374389535             ; 51eb851fH
  imul  ebx
  sar   edx, 5
  mov   ecx, edx
  shr   ecx, 31                     ; 0000001fH
  add   ecx, edx
  imul  eax, ecx, 100
  sub   ebx, eax                    ; ebx = value mod 100
  mov   ax, word ptr [edi+ebx*2]
  mov   ebx, ecx                    ; ebx = value \ 100
  mov   word ptr [esi+4], ax

  ; Convert 4 digits
itoa_4:
  mov   eax, 1374389535             ; 51eb851fH
  imul  ebx
  sar   edx, 5
  mov   ecx, edx
  shr   ecx, 31                     ; 0000001fH
  add   ecx, edx
  imul  eax, ecx, 100
  sub   ebx, eax                    ; ebx = value mod 100
  mov   ax, word ptr [edi+ebx*2]
  mov   ebx, ecx                    ; ebx = value \ 100
  mov   word ptr [esi+2], ax

  ; Convert 2 digits
itoa_2:
  mov   eax, 1374389535             ; 51eb851fH
  imul  ebx
  sar   edx, 5
  mov   ecx, edx
  shr   ecx, 31                     ; 0000001fH
  add   ecx, edx
  imul  eax, ecx, 100
  sub   ebx, eax                    ; ebx = value mod 100
  mov   ax, word ptr [edi+ebx*2]
  mov   ebx, ecx                    ; ebx = value \ 100
  mov   word ptr [esi], ax
itoa_0:
  End Prefix
End FastProc

MakeCvt.bas

Code Select Expand

#Compile Exe
#Dim All

Function PBMain () As Long
  MakeCvt
End Function

Sub MakeCvt()
  Local i As Long
  Local msg As String

  msg = "AsmData cvt"
  For i=0 To 99
    If i Mod 10 = 0 Then msg += $CrLf + "  DW " Else msg += ", "
    msg += "&h" + Right$("0000" + Hex$( (i\10 + 48)  + ((i Mod 10)+48 )*256 ), 4)
  Next
  msg += $CrLf + "End AsmData" + $CrLf

  Clipboard Reset
  Clipboard Set Text msg
End Sub

test_itoaFastProc.bas

Code Select Expand

#Compile Exe
#Dim All
#Optimize Speed

#Include "itoaFastProc.inc"

%COUNT = 100000000
Function PBMain () As Long
  Local i As Long
  Local v As StringZ * 12
  Local q As Quad
  Local s, e As Single

  s = Timer
  Tix q
  For i=1 To %COUNT
   itoa 1234567890, ByRef v
  Next
  Tix End q
  e = Timer
  ? "FastProc atoi: " + Format$( q/%COUNT, "#,##0.0" ) + " tix : " + Format$( %COUNT/(e-s), "#,##0" )+ "/sec : " + v
End Function

[hutch--]

Thanks Larry, it looks good.

[guga]

Just an small update on Larry´s algo. Fixed negative values to show the correct values, preserved the registers, eax now returns the lenght of the string
He was right, the function takes about 40 clock cycles on my I7 (including the modifications). On his original version (with the negative  errors and no preservation of registers) it varies from 7 to 25 clock cycles.

Code Select Expand



[itoa_cvt:  W$ 03030, 03130, 03230, 03330, 03430, 03530, 03630, 03730, 03830, 03930
            W$ 03031, 03131, 03231, 03331, 03431, 03531, 03631, 03731, 03831, 03931
            W$ 03032, 03132, 03232, 03332, 03432, 03532, 03632, 03732, 03832, 03932
            W$ 03033, 03133, 03233, 03333, 03433, 03533, 03633, 03733, 03833, 03933
            W$ 03034, 03134, 03234, 03334, 03434, 03534, 03634, 03734, 03834, 03934
            W$ 03035, 03135, 03235, 03335, 03435, 03535, 03635, 03735, 03835, 03935
            W$ 03036, 03136, 03236, 03336, 03436, 03536, 03636, 03736, 03836, 03936
            W$ 03037, 03137, 03237, 03337, 03437, 03537, 03637, 03737, 03837, 03937
            W$ 03038, 03138, 03238, 03338, 03438, 03538, 03638, 03738, 03838, 03938
            W$ 03039, 03139, 03239, 03339, 03439, 03539, 03639, 03739, 03839, 03939]

Proc itoa:
    Arguments @value, @bValue
    Local @Return, @Sign
    Uses ebx, ecx, edx, edi, esi

    mov eax D@Value
    mov edi D@bValue
    mov D@Sign 0

  mov ebx, eax;esi                      ; eax = value
  mov esi, edi                      ; esi = VarPtr( b )
  mov edi itoa_cvt                 ; edi = cvt
  xor edx, edx                      ; edx = 0 (initial 0)
  cmp ebx, edx                      ; if value
  jge @itoa_init                     ;  >= 0 Then itoa_init
  mov D@Sign 1
  mov B$esi '-';45             ; @esi = '-'
  inc esi                           ; incr esi
  neg eax                           ; eax = -eax
  neg ebx
  mov D@Value eax
@itoa_init:
  cmp eax, 10000
  jl @itoa_digit8
  cmp eax, 10000000
  jl @itoa_digit5
  cmp eax, 100000000
  jl @itoa_digit4
  cmp eax, 1000000000
  jl @itoa_digit3

  mov D@Return 10
  ;===============================
  ; 10 digits
  mov B$esi+10, 0
  jmp @itoa_10
@itoa_digit3:

  mov D@Return 9
  ;===============================
  ; 9 digits
  mov   eax, 1717986919             ; 66666667H
  mov   B$esi+9, 0
  imul  ebx
  sar   edx, 2
  mov   ebx, edx
  shr   ebx, 31                     ; 0000001fH
  add   ebx, edx
  mov   al, bl
  shl   al, 2
  lea   ecx, D$eax+ebx
  mov   eax D@value
  add   cl, cl
  sub   al, cl
  add   al, 48                      ; 00000030H
  mov   B$esi+8, al
  jmp @itoa_8
@itoa_digit4:

    mov D@Return 8
  ;===============================
  ; 8 digits
  mov B$esi+8, 0
  jmp @itoa_8
@itoa_digit5:
  cmp eax, 100000
  jl @itoa_digit7

mov D@Return 6

  cmp eax, 1000000
  jl @itoa_6

    mov D@Return 7
  ;===============================
  ; 7 digits
  mov   eax, 1717986919             ; 66666667H
  mov   B$esi+7, 0
  imul  ebx
  sar   edx, 2
  mov   ebx, edx
  shr   ebx, 31                     ; 0000001fH
  add   ebx, edx
  mov   al, bl
  shl   al, 2
  lea   ecx, D$eax+ebx
  mov   eax, D@value
  add   cl, cl
  sub   al, cl
  add   al, 48                      ; 00000030H
  mov   B$esi+6, al
  jmp @itoa_6
@itoa_digit6:

  ;===============================
  ; 6 digits
  mov B$esi+6, 0
  jmp @itoa_6
@itoa_digit7:

  ;===============================
  ; 5 digits

  mov D@Return 5

  mov   eax, 1717986919             ; 66666667H
  mov   B$esi+5, 0
  imul  ebx
  sar   edx, 2
  mov   ebx, edx
  shr   ebx, 31                     ; 0000001fH
  add   ebx, edx
  mov   al, bl
  shl   al, 2
  lea   ecx, D$eax+ebx
  mov   eax, D@value
  add   cl, cl
  sub   al, cl
  add   al, 48                      ; 00000030H
  mov   B$esi+4, al
  jmp @itoa_4
@itoa_digit8:
  cmp eax, 100
  jl @itoa_digit10
  cmp eax, 1000
  jl @itoa_digit9

    mov D@Return 4
  ;===============================
  ; 4 digits
  mov B$esi+4, 0
  jmp @itoa_4
@itoa_digit9:

  mov D@Return 3
  ;===============================
  ; 3 digits
  mov   eax, 1717986919             ; 66666667H
  mov   B$esi+3, 0
  imul  ebx
  sar   edx, 2
  mov   ebx, edx
  shr   ebx, 31                     ; 0000001fH
  add   ebx, edx
  mov   al, bl
  shl   al, 2
  lea   ecx, D$eax+ebx
  mov   eax, D@value
  add   cl, cl
  sub   al, cl
  add   al, 48                      ; 00000030H
  mov   B$esi+2, al
  jmp @itoa_2
@itoa_digit10:

mov D@Return 2
  ;===============================
  ; 2 digits
  cmp eax, 10
  jl @itoa_digit11
  mov B$esi+2, 0
  jmp @itoa_2
@itoa_digit11:

mov D@Return 1
  ;===============================
  ; 1 digits
  mov   eax, 1717986919             ; 66666667H
  mov   B$esi+1, 0
  imul  ebx
  sar   edx, 2
  mov   ebx, edx
  shr   ebx, 31                     ; 0000001fH
  add   ebx, edx
  mov   al, bl
  shl   al, 2
  lea   ecx, D$eax+ebx
  mov   eax, D@value
  add   cl, cl
  sub   al, cl
  add   al, 48                      ; 00000030H
  mov   B$esi, al
  jmp @itoa_0

  ; Convert 10 digits
@itoa_10:
  mov   eax, 1374389535             ; 51eb851fH
  imul  ebx; 1374389535
  sar   edx, 5
  mov   ecx, edx
  shr   ecx, 31                     ; 0000001fH
  add   ecx, edx
  imul  eax, ecx, 100
  sub   ebx, eax                    ; ebx = value mod 100
  mov   ax, W$edi+ebx*2
  mov   ebx, ecx                    ; ebx = value \ 100
  mov   W$esi+8, ax

  ; Convert 8 digits
@itoa_8:
  mov   eax, 1374389535             ; 51eb851fH
  imul  ebx
  sar   edx, 5
  mov   ecx, edx
  shr   ecx, 31                     ; 0000001fH
  add   ecx, edx
  imul  eax, ecx, 100
  sub   ebx, eax                    ; ebx = value mod 100
  mov   ax, W$edi+ebx*2
  mov   ebx, ecx                    ; ebx = value \ 100
  mov   W$esi+6, ax

  ; Convert 6 digits
@itoa_6:
  mov   eax, 1374389535             ; 51eb851fH
  imul  ebx
  sar   edx, 5
  mov   ecx, edx
  shr   ecx, 31                     ; 0000001fH
  add   ecx, edx
  imul  eax, ecx, 100
  sub   ebx, eax                    ; ebx = value mod 100
  mov   ax, W$edi+ebx*2
  mov   ebx, ecx                    ; ebx = value \ 100
  mov   W$esi+4, ax

  ; Convert 4 digits
@itoa_4:
  mov   eax, 1374389535             ; 51eb851fH
  imul  ebx
  sar   edx, 5
  mov   ecx, edx
  shr   ecx, 31                     ; 0000001fH
  add   ecx, edx
  imul  eax, ecx, 100
  sub   ebx, eax                    ; ebx = value mod 100
  mov   ax, W$edi+ebx*2
  mov   ebx, ecx                    ; ebx = value \ 100
  mov   W$esi+2, ax

  ; Convert 2 digits
@itoa_2:
  mov   eax, 1374389535             ; 51eb851fH
  imul  ebx
  sar   edx, 5
  mov   ecx, edx
  shr   ecx, 31                     ; 0000001fH
  add   ecx, edx
  imul  eax, ecx, 100
  sub   ebx, eax                    ; ebx = value mod 100
  mov   ax, W$edi+ebx*2
  mov   ebx, ecx                    ; ebx = value \ 100
  mov   W$esi, ax
@itoa_0:

mov eax D@Return
add eax D@Sign

EndP


Steve, i believe this can be optimized a bit more. Perhaps, using less registers instead of all of them. Or changing those cmp to test instructions.