Binary string to dword

[MichaelW]

I coded a binary string to dword conversion thinking I was going to need it for a project. It turned out I didn't, but I thought the result was worth posting.

Code Select Expand


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

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

    include \masm32\include\windows.inc
    include \masm32\include\masm32.inc
    include \masm32\include\kernel32.inc

    includelib \masm32\lib\masm32.lib
    includelib \masm32\lib\kernel32.lib

    include \masm32\macros\macros.asm

    btodw PROTO :DWORD

    bval MACRO lpstring     ; binary string to unsigned 32 bit integer
        invoke btodw, reparg(lpstring)
        EXITM <eax>
    ENDM

; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
    .data
      buffer db "1010101010101010",0
    .code
; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
start:
; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««

    print uhex$(bval(chr$("0")))
    print chr$(13,10)

    print uhex$(bval(chr$("00000001")))
    print chr$(13,10)

    print uhex$(bval(chr$("100")))
    print chr$(13,10)

    print uhex$(bval(chr$("10000001")))
    print chr$(13,10)

    print uhex$(bval(chr$("10101010")))
    print chr$(13,10)

    print uhex$(bval(chr$("11111111")))
    print chr$(13,10)

    print uhex$(bval(chr$("1000000000000000")))
    print chr$(13,10)

    print uhex$(bval(chr$("10000000000000000000000000000000")))
    print chr$(13,10)

    print uhex$(bval(chr$("11111111111111111111111111111111")))
    print chr$(13,10)

    count equ 10000000

    call GetTickCount
    push eax
    mov ebx, count
  @@:
    invoke btodw, ADDR buffer
    dec ebx
    jnz @B
    call GetTickCount
    pop ebx
    sub eax, ebx
    print ustr$(eax)   

    print chr$(13,10,"Press enter to exit...",13,10)
    invoke StdIn, ADDR buffer, 1
    exit

btodw proc String:DWORD

  ; ----------------------------------------
  ; Convert binary string into dword value
  ; return value in eax
  ; ----------------------------------------

    mov edx, [String]
    xor eax, eax
    xor ecx, ecx
    jmp @f
  fini:
    mov eax, ecx
    ret
    ALIGN 4
  @@:
    mov al, [edx]
    sub al, 30h
    js  fini
    shl ecx, 1
    add edx, 1
    or  ecx, eax
    jmp @B

btodw endp

; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
end start


[Vortex]

Hi MichaelW,

Your work looks nice, I will give a try.

[Petroizki]

Nice. You could replace eax&ecx, so you would get rid of the final 'mov'. ;)

This would be at least little smaller:

Code Select Expand

btodw proc String:DWORD
mov edx, String
xor eax, eax

@@: movzx ecx, byte ptr [edx]
sub ecx, 30h
js fini

add eax, eax
add edx, 1
or eax, ecx
jmp @B

fini:
ret
btodw endp

Don't know how this would benchmark:

Code Select Expand

btodw proc String:DWORD
mov edx, String
xor eax, eax

@@: movzx ecx, byte ptr [edx]
add edx, 1

test ecx, ecx
je fini

lea eax, [eax*2 + ecx - 30h]
jmp @B

fini:
ret
btodw endp

[Jibz]

Unless it was very important that this function be as fast as possible, I would probably exit on any character that was not 0 or 1 -- something like:

Code Select Expand

    ...
    sub    ecx, 30h
    test   ecx, -2
    jnz    fini
    ...

[MichaelW]

Petroizki,

I tried swaping eax and ecx and eliminating the mov in my procedure, but doing so slowed it down. Using lea to combine the shift and the add into a single instruction is a good idea that didn't occur to me. Your second procedure is the fastest on my P3 and it would probably be the fastest on the earlier processors, but I wonder how it would do on a P4.

Jibz,

I can see the sense in making all conversion procedures handle invalid characters as the dominant HLLs do, but I have always felt that just ending the conversion is a less than optimum method of handling invalid characters. An invalid character in a numeric string usually indicates an error, and I feel it should be handled as such.  But, the HLL conventions are what they are... I could not think of any way to implement your suggestion in Petroizki's second procedure that did not involve adding two or more instructions to the loop.

Code Select Expand


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

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

    include \masm32\include\windows.inc
    include \masm32\include\masm32.inc
    include \masm32\include\kernel32.inc

    includelib \masm32\lib\masm32.lib
    includelib \masm32\lib\kernel32.lib

    include \masm32\macros\macros.asm

    btodw PROTO :DWORD
    btodw0 PROTO :DWORD
    btodw1 PROTO :DWORD
    btodw2 PROTO :DWORD
    btodw3 PROTO :DWORD


    bval MACRO lpstring     ; binary string to unsigned 32 bit integer
        invoke btodw, reparg(lpstring)
        EXITM <eax>
    ENDM

; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
    .data
      buffer db "1010101010101010",0
    .code
; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
start:
; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««

    print uhex$(bval(chr$("0")))
    print chr$(13,10)

    print uhex$(bval(chr$("00000001")))
    print chr$(13,10)

    print uhex$(bval(chr$("100")))
    print chr$(13,10)

    print uhex$(bval(chr$("10000000")))
    print chr$(13,10)

    print uhex$(bval(chr$("10101010")))
    print chr$(13,10)

    print uhex$(bval(chr$("11111111")))
    print chr$(13,10)

    print uhex$(bval(chr$("1000000000000000")))
    print chr$(13,10)

    print uhex$(bval(chr$("10000000000000000000000000000000")))
    print chr$(13,10)

    print uhex$(bval(chr$("11111111111111111111111111111111")))
    print chr$(13,10)

    count equ 10000000

    call GetTickCount
    push eax
    mov ebx, count
  @@:
    invoke btodw, ADDR buffer
    dec ebx
    jnz @B
    call GetTickCount
    pop ebx
    sub eax, ebx
    print ustr$(eax)
   
    print chr$(13,10,13,10)
    print uhex$(hval(chr$("12x34")))

    print chr$(13,10)
    print ustr$(val(chr$("12x34")))

    print chr$(13,10,13,10,"Press enter to exit...",13,10)
    invoke StdIn, ADDR buffer, 1
    exit

btodw proc String:DWORD
    mov edx, String
    xor eax, eax
  @@:
    movzx ecx, byte ptr [edx]
    add edx, 1

    test ecx, 0FFFFFFCEh
    jnz fini

    test ecx, ecx
    je fini

    lea eax, [eax*2 + ecx - 30h]

    jmp @B

  fini:
    ret
btodw endp

btodw0 proc String:DWORD

  ; ----------------------------------------
  ; Convert binary string into dword value
  ; return value in eax
  ; ----------------------------------------

    mov edx, [String]
    xor eax, eax
    xor ecx, ecx
    jmp @f
  fini:
    mov eax, ecx
    ret
    ALIGN 4
  @@:
    mov al, [edx]
    sub al, 30h

    js  fini

    shl ecx, 1
    add edx, 1
    or  ecx, eax
    jmp @B

btodw0 endp

btodw1 proc String:DWORD
    mov edx, String
    xor eax, eax

@@: movzx ecx, byte ptr [edx]
    sub ecx, 30h
    js fini

    add eax, eax
    add edx, 1
    or eax, ecx
    jmp @B

  fini:
    ret
btodw1 endp

btodw2 proc String:DWORD
    mov edx, String
    xor eax, eax

@@: movzx ecx, byte ptr [edx]
    add edx, 1

    test ecx, ecx
    je fini

    lea eax, [eax*2 + ecx - 30h]
    jmp @B

  fini:
    ret
btodw2 endp

btodw3 proc String:DWORD
    mov edx, String
    xor ecx, ecx

@@: movzx eax, byte ptr [edx]
    add edx, 1

    test eax, eax
    je fini

    lea ecx, [ecx*2 + eax - 30h]
    jmp @B 

  fini:
    mov eax, ecx
ret
btodw3 endp

; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
end start

As posted (btodw0):
00000000
00000001
00000004
00000081
000000AA
000000FF
00008000
80000000
FFFFFFFF
1512

Petroizki 1 (btodw1):
00000000
00000001
00000004
00000081
000000AA
000000FF
00008000
80000000
FFFFFFFF
1783

Petroizki 2 (btodw2):
00000000
00000001
00000004
00000081
000000AA
000000FF
00008000
80000000
FFFFFFFF
1432

Petroizki 2, eax & ecx swapped, mov added (btodw3):
00000000
00000001
00000004
00000081
000000AA
000000FF
00008000
80000000
FFFFFFFF
1452

Petroizki 2 with my version of Jibz mod (btodw):
00000000
00000001
00000004
00000080
000000AA
000000FF
00008000
80000000
FFFFFFFF
2073


[Ratch]

     My contribution to this function is below.  Notice that I read 4 bytes at a time.  The loops are unrolled, but it would be easy to roll them up.  By the way, how do you differentiate between '0', ' 00', '000', etc in the EAX value?  Ratch

Code Select Expand


;*******************************************************************************
; ABS_ABDW:  Converts a ASCII binary string into an arithmetic binary DWORD.   *
;                                                                              *
; Called by: PUSH <address of string>                                          *
;            CALL ABS_ABDW                                                     *
;                                                                              *
; Returns:   EAX=arithmetic binary value                                       *
;                                                                              *
; Notes:     This subroutine conforms with WIN32 conventions regarding         *
;            register preservation and stack balancing. EBX,EBP,ESI,EDI are    *
;            not used.                                                         *
;                                                                              *
;            This subroutine makes the assumption that the string length will  *
;            not exceed 32 bytes, and will be terminated by a zero byte.       *
;            Furthermore, since it is a ASCII binary string, it is assumed     *
;            that the string will contain only ASCII zeros and ones.           *
;                                                                              *
; Coder:     Ratch                                                             *
;*******************************************************************************
ABS_ABDW:                   ;it all begins here
MOV ECX,[ESP+DWORD]        ;ECX=address of string
XOR EAX,EAX                ;fresh beginning

@@:
MOV EDX,[ECX]              ;EDX=4 bytes of string

TEST DL,DL                 ;is zero byte terminator?
JZ  @F
  SHL EAX,1                 ;make room for next bit
  SHR EDX,1                 ;send 1 or 0 into the CF
  ADC EAX,0                 ;tack on CF to LSB of EAX
  SHR EDX,7                 ;move to the next byte

TEST DL,DL                 ;is zero byte terminator?
JZ  @F
  SHL EAX,1                 ;make room for next bit
  SHR EDX,1                 ;send 1 or 0 into the CF
  ADC EAX,0                 ;tack on CF to LSB of EAX
  SHR EDX,7                 ;move to the next byte

TEST DL,DL                 ;is zero byte terminator?
JZ  @F
  SHL EAX,1                 ;make room for next bit
  SHR EDX,1                 ;send 1 or 0 into the CF
  ADC EAX,0                 ;tack on CF to LSB of EAX
  SHR EDX,7                 ;move to the next byte

TEST DL,DL                 ;is zero byte terminator?
JZ  @F
  SHL EAX,1                 ;make room for next bit
  SHR EDX,1                 ;send 1 or 0 into the CF
  ADC EAX,0                 ;tack on CF to LSB of EAX
  SHR EDX,7                 ;move to the next byte

  ADD ECX,DWORD             ;pointer to next word
  JMP @B
@@:
RET DWORD                  ;return to sender



[Mark_Larson]

these are my timings on my P3 at work.  I used RDTSC, and divided by the total number of loops.  Other than that I just cut and pasted Michael's code.

Code Select Expand


btodw   : 118
btodw0 : 83
btodw1 : 80
btodw2 : 68
btodw3 : 69


[Mark_Larson]

  I am still trying other things.  But I got it down to 57 cycles on my P3.  The previous fastest way on my P3 was 68 cycles.  Usually I wait to post my final code until I have the fastest possible version.  But I figured I'd post this now in case it helps anyone see the light, and come up with another way that is a variation on my way.  I just basically broke the inner loop up into handling two bytes at a time.

Code Select Expand


btodw4 proc String:DWORD
    mov edx, String
    xor eax, eax
align 4
@@:
    movzx ecx, byte ptr [edx]
movzx esi, byte ptr [edx+1]
;    add edx, 1
add edx,2

    test ecx, ecx
    je fini
   
    lea eax, [eax*2 + ecx - 30h]

test esi, esi
je fini

lea eax, [eax*2 + esi - 30h]

    jmp @B

  fini:
    ret
btodw4 endp


[Mark_Larson]

  Here is something else I am trying.  It still has a bug in it.  I haven't figured out how to fixup it up properly at the end.  But hopefully either someone will spot the fixup ( or I'll have time to do it), or someone will post a faster version using mine as a basis.  I read a whole dword, and deal with 4 binary characters at a time.  It runs in 29 cycles on my P3 at work.

Code Select Expand


btodw5 proc String:DWORD
    mov edx, String
    xor eax, eax

align 4
@@:
    mov ecx, [edx]
    add edx,4

    sub ecx, 30303030h
   
    shl eax,4           ;we deal with 4 bytes at a time, so we multiply by 16
    or eax,ecx

;adjust for negative number from a 0 at the end
    test ecx,80000000h
    jnz fini

    jmp @B

  fini:
  ;need to do a fixup for EAX here
    ret
btodw5 endp


[Ratch]

Mark Larson,

I read a whole dword, and deal with 4 binary characters at a time.

     Isn't that what the program I previously posted does?  Ratch

[Petroizki]

mark,

Please note that your btodw4 uses esi, without restoring it. :eek

[Mirno]

Mark, you don't compact the bits. So after your subtract you end up with (01010101h), not (0Fh)...
Easiest way to compact is to multiply by 01020408h, then shift right by 24, but this uses eax & edx :eek

Then you need to mask the unused bits, and shift eax accordingly (i.e. not always 4 if there are only 3 bits left you'll need to shift 3 :tdown ).

Mirno

[Mirno]

As an aside, when I first saw the problem I mis-read it, and came up with an interesting version for strings that were always 32 characters long (i.e. don't deal with null terminators)...

Code Select Expand


  mov edx, String          ; EDX is our string pointer
  mov eax, 1               ; Use 1, so we know when we're done

@@:
  cmp BYTE PTR [edx], '1'  ; CARRY flag is set for '0' and not for '1'
  lea edx, [edx + 1]       ; Increment EDX without touching the flags
  rcl eax, 1               ; Add this bit to the result.
  jnc @B                   ; If our marker hasn't fallen off, carry on

  not eax                  ; Our result is inverted, so NOT to correct
  ret                      ; ... And relax!


Mirno

[Mark_Larson]

Mark Larson,

I read a whole dword, and deal with 4 binary characters at a time.

     Isn't that what the program I previously posted does?  Ratch

  What you did was read a whole dword at a time, but then handle it one byte at a time.  I read a dword at a time, and then handle a dword at a time.  See the difference?  Also your code runs in 79 cycles on my P3.  There were a few earlier posts that were faster than that.

Here's a repost of those previous timings:

Code Select Expand


btodw   : 118
btodw0 : 83
btodw1 : 80
btodw2 : 68
btodw3 : 69


mark,

Please note that your btodw4 uses esi, without restoring it. :eek

Thanks.  I was just trying to get something up quick, without worrying about robustiness.  You can add that later.  That's the same reason I don't generally add comments to code while I am optimizing it.

 

Mark, you don't compact the bits. So after your subtract you end up with (01010101h), not (0Fh)...
Easiest way to compact is to multiply by 01020408h, then shift right by 24, but this uses eax & edx :eek

Then you need to mask the unused bits, and shift eax accordingly (i.e. not always 4 if there are only 3 bits left you'll need to shift 3 :tdown ).

Mirno

Thanks.  I am actually trying something different at the moment.  I had a bit of a brainstorm on the way home from work.  I am hoping it is faster than the read and handle a dword at a time version. 

[Mark_Larson]

Mirno, I didn't compact until the end.  I didn't have time to take a close look at it to see if that introduced any bugs.  I also didn't do any AND's at the end. The test value came out right.  For the string that Michael provides it prints out a correct value.  I really should do more testing to verify it works with different values.  It runs in 30 cyclces on my P3 with doing the compaction only at the end.  Modifying the compaction to doing it every loop would add a lot of overhead.

Code Select Expand


btodw5 proc String:DWORD
    mov edx, String
    xor eax, eax

align 4
@@:
    mov ecx, [edx]
    add edx,4

    sub ecx, 30303030h
   
    shl eax,4           ;we deal with 4 bytes at a time, so we multiply by 16
    or eax,ecx

;adjust for negative number from a 0 at the end
    test ecx,80000000h
    jnz fini

    jmp @B

  fini:
  ;need to do a fixup for EAX here
    mov esi,01020408h
    mul esi        ; result in EDX:EAX
    shrd eax,edx,24
    shr eax,24
    ret
btodw5 endp


EDIT:  It doesn't return the correct result.  I made a boo-boo.  I ran the wrong version when printing the result.