Ascii to DWORD replacement

[MichaelW]

It seems to me that "decimal string" specifies a string of decimal digits, and “signed decimal string” specifies a string of decimal digits with a sign.

Michael,

Show me one example on the World Wide Web where the absence of the word "signed" implies that the conversion is unsigned.

Actually I had intended to put an appropriate smiley after that sentence, but forgot :icon_confused:

[dedndave]

well - i am with Hutch on one thing
we can attempt to improve the algo without regard to the added bells and whistles
for example, my routine could easily be modified to not handle signed values or unicode
conversely, support for unicode or signed strings can easily be added to any of the others   :P

what is left is the inner loop that converts ASCII chars into binary via Horner's Rule
the atou algo provided by Iczelion simply unrolls the loop once to achieve a little gain

one way we try to speed things up is by using an LUT
that approach doesn't seem to apply, in this case

another way to speed it up is by handling a series of items en mass, in parallel
it may be practical to grab 2 chars and multiply the first by
100 and the second by 10, or something along that line

[jj2007]

I consider the "added bells and whistles" pretty important. Few programmers, including those who read manuals, would expect "-123" to be translated to 253123 - imagine that "horrible coding error" happens in a real life paid for application. Imagine (quoting "it is a DWORD algo and that means unsigned") that the Microsoft Macro Assembler aka Masm would assign 253123 to
.data
MyVar   DWORD -1
... without even issuing a warning ::)

It is a pity that Iczelion is not here to comment on this debate. Unless he has become the director of a museum, I believe he would be in favour of improving his algo.

P.S.: In the previous version of the algo posted above, I had forgotten the range "2147483648" ... "4294967295". These strings are now correctly interpreted (one byte more, one cycle less )

[dedndave]

well - i tend to write my own code for apps, anyways   :P
each case is a little different and i can optimize in the direction according to need
i can also add or remove features that each specific case dictates
i use the masm32 library for trivials and mostly for test/debug - very handy

back to the basic algo....
here is a little teaser to inspire thought   

Code: [Select]

        add     ecx,eax               ;ECX = ECX + EAX
        lea     eax,[32*eax+eax]      ;EAX = 33 * EAX
        add     ecx,eax               ;ECX = ECX + (34 * EAX)
        lea     eax,[2*eax+ecx]       ;EAX = (66 * EAX) + ECX + (34 * EAX) = (100 * EAX) + ECX
well - it looked good, on paper - lol

[dedndave]

another idea is to approach it as a set of cases
we might select the "major" case set based on which dword the first null is found

Code: [Select]

case0_0 db 0        ;invalid case, but we should probably return 0
case0_1 db '1',0
case0_2 db '12',0
case0_3 db '123',0

case1_4 db '1234',0
case1_5 db '12345',0
case1_6 db '123456',0
case1_7 db '1234567',0

case2_8 db '12345678',0
case2_9 db '123456789',0
case2_0 db '1234567890',0
case2_x db '12345678901'     ;illegal case
then, we can use the "fast null finder" algo....

Code: [Select]

        mov     ecx,[edx]
        and     ecx,7F7F7F7Fh
        sub     ecx,01010101h
        and     ecx,80808080h
        jnz     test_one_of_the_bytes_is_null_or_80hthat algo is fast because it assumes that 80h is rare in the string
that particularly applies in this application, because valid string characters are never 80h

now, we want to process 0 to 4 decimal chars at a time
i.e., 5 "sub-cases" - one of which is "we are done"

[dedndave]

i devised a little test to make comparison somewhat "real world"
i use 6 test strings, then divide the result by 6.....

Code: [Select]

        ALIGN 4
szTest01 db '123',0
        ALIGN 4
szTest02 db '1234567',0
        ALIGN 4
szTest03 db '1234567890',0

        ALIGN 4
         db 0                ;mis-align
szTest04 db '123',0
        ALIGN 4
         db 0                ;mis-align
szTest05 db '1234567',0
        ALIGN 4
         db 0                ;mis-align
szTest06 db '1234567890',0
the atou function runs about 52 cycles average on the 6 test strings
that's a little under 8 cycles per char
hard to beat that, really   :P

[hutch--]

 

I consider the "added bells and whistles" pretty important. Few programmers, including those who read manuals, would expect "-123" to be translated to 253123 - imagine that "horrible coding error" happens in a real life paid for application. Imagine (quoting "it is a DWORD algo and that means unsigned") that the Microsoft Macro Assembler aka Masm would assign 253123 to
.data
MyVar   DWORD -1
... without even issuing a warning

Assembler programmers are supposed to know the difference between signed and unsigned, in various higher level languages the distinction between DWORD and LONG, if they don't they find out REAL SOON.  :P Way better for it to go BANG when you get it wrong than hide behind pseudo objects that hide the blunders.

The debate is not about improving Iczelion's old algo, everything and its dog has done that, it is what will be used as a drop in replacement and here changing the functionality of the algo is a big NO NO as it risks breaking someone's code. Writing a "different" algo is uncontentious, get it going, make sure its reliable and document it properly.

What I refuse to do is get involved in function creep, add this, add that, more bells and whistles and you eventually end up with crap like most higher level languages, a function that is both slow and does everything badly but HAY, its got all sorts of bells and whistles. (Yeah yeah, but you can always get a faster box to make crap look like its fast) 

I do have a couple of faster versions, the "_ex" version outperforms it over a wide range of test conditions but at the cost of it being larger and Lingo's version is also faster but has a scruffy exit that messes up the call / ret pairing, I was foolish enough to expect that a few of the folks here may have had a faster one than atou, I don't need a slower different version.

[dedndave]

well....
the ability to support signed values, in this case, does not violate the ability to support unsigned values
this is one of the rare cases where that statement can be made

still, i can see the case, in terms of backward compatibility, as well
if someone writes code with this version of the library, we shouldn't cause it to not work on the previous one
while that isn't always true, we don't have to got out of our way to cause it to happen - lol

at any rate....
let's see the algo that lingo had
it shouldn't be too hard to fix the call/ret code and see how it performs
either way, it would be interesting to see the algo, from a design point of view

[dedndave]

I was foolish enough to expect that a few of the folks here may have
had a faster one than atou, I don't need a slower different version.

that's pretty crappy
really, if you don't want our help, don't ask for it - we'll all be happier

[hutch--]

Tolerate me here, when I posted the original question I was not looking for "help", I have only been writing assembler for the last 20 years and 32 bit for over 15 years, what I asked if any of our members had a fast algo that I could use as a drop in for the old one. It was an entirely reasonable peer request to what used to be a range of members who wrote fast code. pseudo philosophical debate, re-interpretations and function redesign just make the task really hard to keep track of and its why I rarely post much code these days as the signal to noise ratio exceeds the value of what you get back from it.

I did not write the old algo and I loath to touch an heirloom like that so I went looking for a drop in replacement given that once we had members who did write fast code and had a range of algos floating around that were useful with such requests.

[dedndave]

the original post doesn't come off that way

i was willing to set the bells and whistles and philosophical discussion aside and try a few twists on algo design
that is the part that i find interesting, to be honest

at the end of the day, you are going to use the Iczelion replacement code, anyways
it was a waste of my time

and, tolerate me, here, but this isn't a very kind statement to aim at people who are trying to be helpful

I was foolish enough to expect that a few of the folks here may have had a faster one than atou

i don't really care which routine you use - lol
as i mentioned, i usually like to write my own stuff, anyways

the way it is, i wouldn't use this routine in a real-world app
because it eats up erroneous strings and spits out a smiley face
if the string has a non-numeric, is too long, is null, you won't know about it

[dedndave]

this shaves a few clock cycles off, overall about 5% faster on a variety of strings

Code: [Select]

    mov     edx, [esp+4]
    movzx   eax, byte ptr [edx]
    add     edx, 1
    test    eax, eax
    jnz     entry

    jmp short quit

lpst:
    lea     eax, [eax+eax*4]            ; mul eax * 5
    add     edx, 1
    lea     eax, [ecx+eax*2-48]

entry:
    movzx   ecx, byte ptr [edx]
    test    ecx, ecx
    jz      quit

    lea     eax, [eax+eax*4]            ; mul eax * 5
    add     edx, 1
    lea     eax, [ecx+eax*2-48]
    movzx   ecx, byte ptr [edx]
    test    ecx, ecx
    jnz     lpst

quit:
    ret     4

[dedndave]

a while back, i needed a function like this to process user input (console)
in this case, i wanted to allow unsigned values, only
the routine that did the conversion was actually a helper routine
but - it would return error status for the top-level function

Code: [Select]

;******************************************************************

Str2Uint PROC    lpString:LPSTR

;Convert an ASCII Decimal String to a 32-Bit Unsigned Integer
;
;Call With: lpString = address of zero-terminated ASCII numeric string
;
;  Returns: EAX = status:
;                 0 = no error, EDX is valid
;                 1 = "value too large" error
;                 2 = "non-numeric character in string" error
;           EDX = 32-bit unsigned integer if EAX = 0
;                 undefined if EAX is not 0
;
;Also Uses: ECX, all other registers are preserved

;------------------------------------------------------------------
the top-level function could then display error strings and re-prompt the user for input

Code: [Select]

;******************************************************************

ReadUnsigned PROC

;Read an Unsigned Integer from Console Keyboard
;
;  If the user enters a value that is too large or any non-numeric
;characters, a re-try prompt is displayed.
;
;Call With: Nothing
;
;  Returns: EAX = EDX = 32-bit unsigned integer value
;
;Also Uses: ECX, all other registers are preserved

;------------------------------------------------------------------
speed isn't a big deal - how fast can the guy enter numbers, anyways - lol
but, handling the cases was important

because i only wanted to allow unsigned integers, i could have filtered out non-numerics at the keyboard
but - you still have to know if the value is too large
4294967296 should not return a 0

[jj2007]

I was foolish enough to expect that a few of the folks here may have had a faster one than atou, I don't need a slower different version.

Hutch,

I understand your concerns about breaking existing code. You asked for an atodw replacement, we tried to offer a version that does exactly the same but faster.

What I posted returns exactly the same in eax when fed valid positive strings, so it should not break any existing code. It's also a factor five faster.

What you chose in the end returns exactly the same in eax when fed valid positive strings, is even faster than mine, but if the user has any doubt about the validity of the strings (leading whitespace, + and -, dots in 123.456), then the error checking will eat up the advantage.

But OK, there are cases where you have a huge text file to read in and no doubts about the format, so it will be convenient to have a really fast algo like atou. Nonetheless, it would enhance the usability of Masm32 if you could add a line to the documentation saying "no signs, no whitespace allowed". The mere assumption that assembler programmers see DWORD and understand unsigned is risky, given that ML.EXE interprets DWORD -1 as ffffffffh.

 :icon14:

[dedndave]

i can see where handling signed values is a problem
on previous versions, these input values were not supported
if you now allow it, then 4294967295 = -1
well - that would be a problem if previous versions denied the minus sign

But OK, there are cases where you have a huge text file to read in and no doubts about the format

i can't think of any practical cases where that is true
if it's a text file, then the user may have edited it
unless - your application just wrote that file - then you know the format
but - oops - if i just wrote a file with a large number of dword values, i should have stored them as binary dwords