I am still confused....by dwtoa

[asmman]

Hi Everyone,

I am trying to understand the dwtoa proc in the m32lib to see how it converts numbers into equivalent character strings.  After reading the forums I went and downloaded Ollydbg 1.10 (Thx for the idea).  I now see what is happening but I don't understand why....  Hopefully someone can explain the following snippet to me....

     eax = 20h (the number I want to convert)

     mov ecx,3435973837   
     mul  ecx                                          ;????????
     shr   edx,3                                       ;divide by 8
     mov eax,edx                                    ;save results
     lea  edx,[edx*4+edx]                       ;?????????
     ....
I see that after the mul that eax = x'999999A0' and that edx = x'00000019' what I don't understand is why?   I know that eax = low half of double word and edx=high half of double word but what causes this?  I guess it has something to do with unsigned multiplication but I am fuzzy about the unsigned part of this.  I tried using calc.exe to 'see' the result but I only get the value in eax,  probably an issue with my using calc.exe?

The rest of the function I think I pretty much understand, it's basically playing some tricks with math in order to convert the x'20' to the number 32 though if someone could elaborate I would appreciate it....

Thanks!

[Ossa]

I'm not sure that I understand exactly which bit it is that you're having trouble with, so I'll explain the whole thing:

I'll show you the complete bit from dwtoa so that it makes sense:

Code Select Expand

pos:
    mov ecx, 3435973837    ; Magic number for  division
    mov esi, edi           ; Save pointer to first number (needed later)

    .while (eax > 0)       ; For this loop, A is the value of eax at
                           ;   the start of the loop (which starts at
                           ;   the value to be converted)
      mov ebx,eax          ; ebx = eax = A
      mul ecx              ; edx = floor(8 * A / 10)
      shr edx, 3           ; edx = floor(A / 10)
      mov eax,edx          ; eax = floor(A / 10)
      lea edx,[edx*4+edx]  ; edx = 5 * floor(A / 10)
      add edx,edx          ; edx = 10 * floor(A / 10)
      sub ebx,edx          ; ebx = A - 10 * floor(A / 10) = A % 10
     
      add bl,'0'           ; bl = ASCII(A % 10)
      mov [edi],bl         ; save to string
      add edi, 1           ; increment buffer pointer
    .endw

    mov byte ptr [edi], 0       ; terminate the string

The aim of this is to find - IN REVERSE ORDER - the digits of the number and to store them in ASCII in the buffer. (% is C notation for modulus (remainder from integer division) if you aren't familiar with C)

The trick is that the magic number in ecx happens to do: edx = floor(8 * eax / 10)

This is called division by multiplication and is a sneaky technique used in fixed point arithmatic (check it out: 10 * 3435973837 = 34359738370 = 800000002h, clever eh?)

The whole loop could be replaced by:

Code Select Expand

pos:
    mov ecx, 10
    mov esi, edi

    .while (eax > 0)
      xor edx, edx
      div ecx
      add dl,'0'
      mov [edi],dl
      add edi, 1
    .endw

    mov byte ptr [edi], 0       ; terminate the string

which is much simpler. So why not? Because div is slow (~42 cylces on old CPUs IIRC) and mul is relatively fast (~10 cylces). Welcome to the wonderful world of optimisation, where the simple becomes complex in the blink of an eye.

Hope that helps,
Ossa

[raymond]

One word of caution about that particular conversion algo from dword to ASCII. It will yield WRONG results with some of the binary numbers.

That algo was developed as an "optimized" procedure to save a few nanoseconds compared to other algos. However, this "optimization" has resulted in some erroneous results which have been well publicized. I really don't know why it is still included in the library.

[hutch--]

Ray,

I thought the fix done by Jibz in 2004 had solved the problem He built a test that directly compared it with a C runtime function and it was identical from 0 to maximum limit. This is the version I have of it.

Code Select Expand


; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««

  ; ---------------------------------------------------------------
  ; This procedure was written by Tim Roberts
  ; Minor fix by Jibz, December 2004
  ; ---------------------------------------------------------------

    .486
    .model flat, stdcall  ; 32 bit memory model
    option casemap :none  ; case sensitive

    .code

; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««

align 4

dwtoa proc dwValue:DWORD, lpBuffer:DWORD

    ; -------------------------------------------------------------
    ; convert DWORD to ascii string
    ; dwValue is value to be converted
    ; lpBuffer is the address of the receiving buffer
    ; EXAMPLE:
    ; invoke dwtoa,edx,ADDR buffer
    ;
    ; Uses: eax, ecx, edx.
    ; -------------------------------------------------------------

    push ebx
    push esi
    push edi

    mov eax, dwValue
    mov edi, [lpBuffer]

    test eax,eax
    jnz sign

  zero:
    mov word ptr [edi],30h
    jmp dtaexit

  sign:
    jns pos
    mov byte ptr [edi],'-'
    neg eax
    add edi, 1

  pos:
    mov ecx, 3435973837
    mov esi, edi

    .while (eax > 0)
      mov ebx,eax
      mul ecx
      shr edx, 3
      mov eax,edx
      lea edx,[edx*4+edx]
      add edx,edx
      sub ebx,edx
      add bl,'0'
      mov [edi],bl
      add edi, 1
    .endw

    mov byte ptr [edi], 0       ; terminate the string

    ; We now have all the digits, but in reverse order.

    .while (esi < edi)
      sub edi, 1
      mov al, [esi]
      mov ah, [edi]
      mov [edi], al
      mov [esi], ah
      add esi, 1
    .endw

  dtaexit:

    pop edi
    pop esi
    pop ebx

    ret

dwtoa endp

; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««

end


[asmman]

Ossa,

Thank You, your explanation makes much more sense.  I had a feeling the mul was something to do with optimization but I understand it better now.

:U