Prev: OctaOS
Next: DIV overflow
From: Guga on 1 Apr 2007 19:54 On Apr 1, 4:17 pm, "r...(a)cs.ucr.edu" <r...(a)cs.ucr.edu> wrote: > On Mar 31, 3:18 pm, "Guga" <Guga...(a)gmail.com> wrote: > > > On Mar 31, 8:19 am, "r...(a)cs.ucr.edu" <r...(a)cs.ucr.edu> wrote: > > > For that huge number i provided, the test were made on the 1st 128 > > Bits only . But.. the results for those 1st 128 bits should work on > > yours too, no matter if the string is bigger or not. I mean, the 1st 4 > > dword of your code should be those ones. > > No guarantees. Overflow is not guaranteed to be the same across > different algorithms. > > > > > > > > > On smaller numbers the error is more easilly seen. > > > For example, take the number: 7458784146511699504104824251512520706 > > > This is a 128 Bit number. The results are: > > > Mine: > > [Value: > > Value.Conv32Bit: D$ 0E000002 > > Value.Conv64Bit: D$ 0F549DDB > > Value.Conv96Bit: D$ 06B2C5BFC > > Value.Conv128Bit: D$ 059C8273] > > > Yours: > > [Value: > > Value.Conv32Bit: D$ 0FFFFFFD0 > > Value.Conv64Bit: D$ 0F549DDB > > Value.Conv96Bit: D$ 06B2C5BFC > > Value.Conv128Bit: D$ 059C8273] > > Now the problem is apparent. You've apparently translated my algorithm > incorrectly. Here's the unit test I use for my conversion code with > both a test for the value you've provided as well as a dump, in hex, > of the four dwords: > > try > > conv.strToi128( "64", 0, inputL ); > if( cmp128( inputL, 64 ) ) then > > raise($1_1280); > > endif; > > conv.strToi128( "-64", 0, inputL ); > if( cmp128( inputL, -64 ) ) then > > raise($1_1281); > > endif; > > conv.strToi128( "0", 0, inputL ); > if( cmp128( inputL, 0 ) ) then > > raise($1_1282); > > endif; > > conv.strToi128( "170141183460469231731687303715884105727", 0, > inputL ); > if( cmp128( inputL, > 170141183460469231731687303715884105727 ) ) then > > raise($1_1283); > > endif; > > conv.strToi128( "-170141183460469231731687303715884105728", 0, > inputL ); > if( cmp128( inputL, > -170141183460469231731687303715884105728 ) ) then > > raise($1_1284); > > endif; > > conv.strToi128( "7458784146511699504104824251512520706", 0, > inputL ); > > stdout.put( "dwords = ", (type dword inputL), ", ", (type dword > inputL[4]), > ", ", (type dword inputL[8]), ", ", (type dword inputL[12]), nl ); > if( cmp128( inputL, 7458784146511699504104824251512520706 )) > then > > raise($1_1287); > > endif; > > try > > conv.strToi128( "170141183460469231731687303715884105728", > 0, inputL ); > > unprotected > > // We we got to this point, we failed to raise an overflow > error. > > Raise( $1_1285 ); > > exception( ex.ValueOutOfRange ) > > // Okay, we succeeded if we got this exception. > > anyexception > > // Anything else? Pass it on. > > Raise( eax ); > > endtry; > > try > > conv.strToi128( IllegalCharStr, 0, inputL ); > > unprotected > > // We we got to this point, we failed to raise an illegal > // character exception. > > Raise( $1_1286 ); > > exception( ex.IllegalChar ) > > // Okay, we succeeded if we got this exception. > > anyexception > > // Anything else? Pass it on. > > Raise( eax ); > > endtry; > > try > > conv.strToi128( "", 10, inputL ); > > unprotected > > // We we got to this point, we failed to raise an illegal > // index exception. > > Raise( $1_1287 ); > > exception( ex.StringIndexError ) > > // Okay, we succeeded if we got this exception. > > anyexception > > // Anything else? Pass it on. > > Raise( eax ); > > endtry; > > stderr.put( "conv.strToi128 succeeded!" nl ); > > anyexception > > stderr.put > ( > nl nl > "***************************************************" nl > "conv.strToi128 failed! eax=", eax, nl > "***************************************************" nl > nl > ); > os.exitProcess(1); > > endtry; > > Here is the output from the section of code above: > > dwords = 0E000002, 0F549DDB, 6B2C5BFC, 059C8273 > conv.strToi128 succeeded! > > > > > Try analysing the results for 128 bit, i´m sure you will find the > > error. > > I think you'll have to do that on your end. I get the values you claim > to be the correct ones. > > > > > Do what Herbert said.. increment or decrement the number to you see. > > Again, that would need to be done on your side. I seem to be getting > correct values. > > > > > Make tests for > > 7458784146511699504104824251512520704 > > 7458784146511699504104824251512520705 > > Better than that, here's the maximum (signed) 128-bit value you can > allow: > 170141183460469231731687303715884105727 > > Obviously, double it and add one for the maximum unsigned 128-bit > value. > > Other than checking for overflow detection (which you'll notice my > routines are doing), I'd be *very* careful about testing values larger > than this. Such tests are meaningless unless your specifications > require you to return some modulo or other value when overflow occurs. > Cheers, > Randy Hyde- Hide quoted text - > > - Show quoted text - Hi Randall what is this piece of code ? Apparently this functino you provided are now generating the correct numbers, the result i got and you got are the same. But, this was not the one i translated. I translated the functino you provided earlier. The function called "_atou128" This is the code you provided procedure _atou128; @nodisplay; @noframe; procedure _accX10; @nodisplay; @noframe; begin _accX10; // Compute EDX:ECX:EBX:EDI * 10 push( eax ); shl( 1, edi ); rcl( 1, ebx ); rcl( 1, ecx ); rcl( 1, edx ); jc Overflow; push( edx ); push( ecx ); push( ebx ); push( edi ); shl( 1, edi ); rcl( 1, ebx ); rcl( 1, ecx ); rcl( 1, edx ); jc Overflow; shl( 1, edi ); rcl( 1, ebx ); rcl( 1, ecx ); rcl( 1, edx ); jc Overflow; pop( eax ); add( eax, edi ); pop( eax ); adc( eax, ebx ); pop( eax ); adc( eax, ecx ); pop( eax ); adc( eax, edx ); jc Overflow; pop( eax ); ret(); Overflow: raise( ex.ValueOutOfRange ); end _accX10; begin _atou128; push( edi ); xor( eax, eax ); // Init H.O. three bytes of EAX to zero. mov( eax, edx ); // Initialize EDX:ECX:EBX:EDI with zero. mov( eax, ecx ); mov( eax, ebx ); mov( eax, edi ); // For each legal character that ESI points at, repeat // the following until we encounter a delimiter or // illegal character. mov( [esi], al ); // Get the first character (which must be a digit). whileDigits: cmp( al, '0' ); jb convError; cmp( al, '9' ); ja convError; // Okay, we've got a digit, so add it into EDX:ECX. _accX10(); // EDX:ECX:EBX:EDI * 10. and( $f, al ); add( eax, edi ); adc( 0, ebx ); adc( 0, ecx ); adc( 0, edx ); jc Overflow; // Move on to the next character: NextChar; // Repeat until we hit a delimiter character cmp( eax, $80 ); jae IllegalChar; bt( eax, (type dword Delimiters )); jnc whileDigits; // Return 128-bit result in EDX:ECX:EBX:EAX mov( edi, eax ); pop( edi ); ret(); convError: raise( ex.ConversionError ); Overflow: raise( ex.ValueOutOfRange ); IllegalChar: raise( ex.IllegalChar ); end _atou128; So.. which function is correct ? The above one or this new one ? The one above i translated as: Proc atoi128: Arguments @String mov esi D(a)String xor eax eax xor edx edx xor ecx ecx xor ebx ebx xor edi edi movsx eax B$esi sub eax '0' While B$esi <> 0 ; when we reach the end of the string we ends the loop call alldecmul2 eax, edx, ecx, ebx, edi and al 0F add edi eax adc ebx 0 adc ecx 0 adc edx 0 jc @Overflow inc esi movsx eax B$esi sub eax '0' End_While ExitP @Overflow: call 'USER32.MessageBoxA', &NULL, {"Overflow Error", 0}, {"Error", 0}, 0A EndP Proc alldecmul2: Arguments @Digit, @Val1, @Val2, @Val3, @Val4 push eax shl edi 1 rcl ebx 1 rcl ecx 1 rcl edx 1 | jc @Overflow push edx push ecx push ebx push edi shl edi 1 rcl ebx 1 rcl ecx 1 rcl edx 1 | jc @Overflow shl edi 1 rcl ebx 1 rcl ecx 1 rcl edx 1 | jc @Overflow pop eax add edi eax pop eax adc ebx eax pop eax adc ecx eax pop eax adc edx eax | jc @Overflow pop eax ExitP @Overflow: call 'USER32.MessageBoxA', &NULL, {"Overflow Error", 0}, {"Error", 0}, 0A EndP If this translation is correct, then it is on this one that is resulting an incorrect result. The one in "_atou128" i mean. Is "_atou128" different from strToi128 ??? What "raise" means ? Best Regards, Guga
From: rhyde on 2 Apr 2007 01:11 On Apr 1, 4:54 pm, "Guga" <Guga...(a)gmail.com> wrote: > > Hi Randall > > what is this piece of code ? This comes from the regression test that I wrote for the HLA stdlib v2.0, from which the _atou128 code that I posted is a member. This code actually tests the strtoi128 function which directly calls _atou128. I'm pretty sure you can find all the regressions tests for the CONV module that I've written here: http://webster.cs.ucr.edu/AsmTools/HLA/stdlib2/index.html BTW, this set of regression tests is *exactly* what I was talking about when I said that RosAsm users could benefit from a command-line version of the assembler. Being able to put together a set of tests like this that you can run whenever someone questions the validity of a code sequence is a heck of a lot better than having to manually run the test sequences. Particuarly when you have hundreds of test programs you could run. > > Apparently this functino you provided are now generating the correct > numbers, the result i got and you got are the same. I haven't changed the code since I posted it. And the regression tests ran fine the last time I ran them (before this discussion). What can I say? I seriously doubt it was magic. Perhaps you forgot to switch an operand or two when doing the conversion? In any case, feel free to download the code directly from Webster -- the page hasn't been updated in a couple of months, and try out the original code. I'd act fast, though, because I *do* plan on updating the stdlib v2.0 code immediately after HLA v1.90 appears (which should be sometime this week). Not that I'm touching any of the CONV code, mind you, but if you grab a copy now you can be assured that you've got something that is a couple months old. > > But, this was not the one i translated. > > I translated the functino you provided earlier. The function called > "_atou128" Here is strtou128, notice that all it really does it check parameter validity and turn around and call _atou128: procedure conv.strTou128( s:string; index:dword; var dest:lword ); @nodisplay; @noframe; @noalignstack; begin strTou128; push( ebp ); mov( esp, ebp ); push( eax ); push( ebx ); push( ecx ); push( edx ); push( esi ); push( edi ); // Get the string pointer and make sure it's valid. mov( s, esi ); test( esi, esi ); jz refNULL; cmp( dest, NULL ); jz refNULL; // Get the starting index and make sure it does not // exceed the string length. mov( index, eax ); cmp( eax, (type str.strRec [esi]).length ); ja strIndexErr; add( eax, esi ); // Point at start of integer string. dec( esi ); whileDelimLoop: NextChar; cmp( eax, $80 ); jae IllegalChar; bt( eax, (type dword Delimiters )); jc whileDelimLoop; _atou128(); // Store result into the dest parameter: mov( dest, edi ); mov( eax, [edi] ); mov( ebx, [edi+4] ); mov( ecx, [edi+8] ); mov( edx, [edi+12] ); pop( edi ); pop( esi ); pop( edx ); pop( ecx ); pop( ebx ); pop( eax ); pop( ebp ); ret( _parms_ ); refNULL: raise( ex.AttemptToDerefNULL ); strIndexErr: raise( ex.StringIndexError ); IllegalChar: raise( ex.IllegalChar ); end strTou128; Here is strtoi128. Notice that it checks parameter validity, deals with the sign, and calls _atou128: procedure conv.strToi128( s:string; index:dword; var dest:int128 ); @nodisplay; @noframe; @noalignstack; begin strToi128; push( ebp ); mov( esp, ebp ); push( eax ); push( ebx ); push( ecx ); push( edx ); push( esi ); push( edi ); // Get the string pointer and make sure it's valid. mov( s, esi ); test( esi, esi ); jz refNULL; // Get the starting index and make sure it does not // exceed the string length. mov( index, eax ); cmp( eax, (type str.strRec [esi]).length ); ja badIndex; add( eax, esi ); // Point at start of integer string. dec( esi ); whileDelimLoop: NextChar; cmp( eax, $80 ); jae IllegalChar; bt( eax, (type dword Delimiters )); jc whileDelimLoop; cmp( al, '-' ); jne notNegative; // If this number has a leading minus sign, then skip over it, // convert the number to an unsigned integer, check for overflow, // and then negate the result. inc( esi ); _atou128(); // $8000_0000_0000_0000_0000_0000_0000_0000 is okay, but // any other value with the sign bit set is a value that // is out of range. test( edx, edx ); jns validi128; cmp( edx, $8000_0000 ); ja voor; test( eax, eax ); jnz voor; test( ebx, ebx ); jnz voor; test( ecx, ecx ); jnz voor; validi128: xor( edi, edi ); sub( eax, edi ); mov( 0, eax ); sbb( ebx, eax ); mov( 0, ebx ); sbb( ecx, ebx ); mov( 0, ecx ); sbb( edx, ecx ); mov( dest, edx ); mov( edi, [edx] ); mov( eax, [edx+4] ); mov( ebx, [edx+8] ); mov( ecx, [edx+12] ); jmp si128Done; notNegative: // If the number does not have a leading "-" character, then // treat it like an unsigned integer. Note, however, that // the H.O. bit of the result must be clear or we have an // overflow. _atou128(); test( edx, edx ); js voor; // Store the result away in the i128 variable pointed at by dest: mov( dest, edi ); mov( eax, [edi] ); mov( ebx, [edi+4] ); mov( ecx, [edi+8] ); mov( edx, [edi+12] ); si128Done: pop( edi ); pop( esi ); pop( edx ); pop( ecx ); pop( ebx ); pop( eax ); pop( ebp ); ret( _parms_ ); refNULL: raise( ex.AttemptToDerefNULL ); badIndex: raise( ex.StringIndexError ); voor: raise( ex.ValueOutOfRange ); IllegalChar: raise( ex.IllegalChar ); end strToi128; The code I posted checked strToi128. Rest assured there is nearly an identical routine that tests strTou128. Both call _atou128. If _atou128 fails in the manner you suggest, these routines would detect this. Note that I also have a test routine that tests _atou128 directly, here's the pertinent section of code: stderr.put( "Testing _atou128()" nl ); try #macro raiseif128( expectedValue, raiseValue ); mov( @text( "_" + @string( expectedValue )), esi ); _atou128(); if ( eax <> (expectedValue & $FFFF_FFFF) && ebx <> ((expectedValue >> 32 ) & $FFFF_FFFF) && ecx <> ((expectedValue >> 64 ) & $FFFF_FFFF) && edx <> (expectedValue >> 96 ) ) then raise( raiseValue ); endif; #endmacro raiseif128( 0, $1040 ); raiseif128( 1, $1041 ); raiseif128( 127, $1042 ); raiseif128( 128, $1043 ); raiseif128( 255, $1044 ); raiseif128( 256, $1045 ); raiseif128( 32767, $1046 ); raiseif128( 32768, $1047 ); raiseif128( 65535, $1048 ); raiseif128( 65536, $1049 ); raiseif128( 2147483647, $1050 ); raiseif128( 2147483648, $1051 ); raiseif128( 4294967295, $1052 ); raiseif128( 4294967296, $1053 ); raiseif128( 9223372036854775807, $1054 ); raiseif128( 9223372036854775808, $1055 ); raiseif128( 18446744073709551615, $1056 ); raiseif128( 18446744073709551616, $1057 ); raiseif128( 170141183460469231731687303715884105727, $1058 ); raiseif128( 170141183460469231731687303715884105728, $1059 ); raiseif128( 340282366920938463463374607431768211455, $1060 ); try mov( _340282366920938463463374607431768211456, esi ); _atou128(); raise( $1061 ); // Better not get here. exception( ex.ValueOutOfRange ) // This is the expected case endtry; stdout.put( "_atou128 tests succeeded!" nl nl ); anyexception (sorry for not posting the macros, if you're really interested, download the code from the URL I gave earlier) This code runs and succeeds. Again, if _atou128 was exhibiting the behavior you're describing, this test code would have caught it. > > So.. which function is correct ? > > The above one or this new one ? What new one? > > The one above i translated as: > > Proc atoi128: > Arguments @String > > mov esi D(a)String > > xor eax eax > xor edx edx > xor ecx ecx > xor ebx ebx > xor edi edi > > movsx eax B$esi > sub eax '0' > > While B$esi <> 0 ; when we reach the end of the string we ends the > loop > We haven't gotten far into the code at all, and already you've changed the code quite a bit. If you're going to accuse my code of operating incorrectly, I would expect an instruction-for-instruction translation. Forgive me for not taking a *careful* look at *your* code, but I can easily imagine that this "translation" is incorrect. .... > If this translation is correct, And that "If" is a mighty big "If" indeed. You've made some very fundamental changes to the code. Is it not suprising that it produces different results? Again, forgive me for not analyzing your code instruction by instruction. But I've already spent the time doing that with my own code, as well as writing a fair set of regression test routines to shake it down. That's a lot of work (as you're seeing with your *one* routine). Now I could spend a lot of time finding out what's wrong with *your* code, or I could use that same time to test another major routine in the HLA standard library. As I've already got numeric conversion fairly well tested, I'm not sure there's much benefit to testing yet another version, so you'll forgive me if I pass on this one. You really *ought* to take a look at the regression tests I've posted in the URL I gave earlier. They might help you discover some ways to better test your code in the future. Cheers, Randy Hyde
From: �a/b on 2 Apr 2007 02:21 On Sun, 01 Apr 2007 18:15:46 +0200, "�a\\/b" <al(a)f.g> wrote: >On 26 Mar 2007 12:39:48 -0700, "Guga" wrote: >>Hi guys >>someone knows how to convert an null terminated ascii string to >>tword ? (80 bits) >> >>I suceeded to convert an ascii to qword, making an similar function as >>atoi64, but i can�t extend the convertion to 80 bits. >> >>Some one knows how to convert? Also for 128 bit would be good too :) >> >>Btw: If someone have a C source of those routines and not an assembly >>one.. no problem...i can try translate to assembly; >> >> >>Best Regards, >> >>Guga > this should be for 80 bits numbers #include <stdio.h> #include <stdlib.h> /* for 80 bits numbers */ extern "C" {int StrToNum(char* res, char* string, char** pos, int base);} /* Assembly function */ class num{ public: friend void prx(num& a); friend int StrToNum(num* res, char* string, char** pos, int base); num& operator=(num& a); num& operator=(unsigned a); num(); ~num(); /*----------------------------------------------*/ unsigned len; /* how many unsigned is the number long */ unsigned *pu; /* number */ unsigned lung; /* memory reserved for that number */ }; num::num() {pu=(unsigned*)malloc(4*3); if(pu==0){len=0; lung=0; exit(0); } else {lung=3; len=1; *pu=0;} } num::~num() {free(pu); len=0; lung=0; pu=0;} void prx(num& a) {unsigned i, len=a.len; printf("0x"); for(i=0;i<len-1;++i) if(i==0) printf("%x ", a.pu[len-1-i]); else printf("%08x ",a.pu[len-1-i]); printf("%08x; ", a.pu[0]); } num& num::operator=(num& a) {unsigned i; if(&a == this) return *this; if(a.len>lung||a.len>0xFFFFFF) exit(0); len=a.len; for(i=0; i<len; ++i) pu[i]=a.pu[i]; return *this; } num& num::operator=(unsigned a) {if( (int)lung<1) exit(0); len=1; pu[0]=a; return *this; } int StrToNum(num* res, char* string, char** pos, int base) {int a=StrToNum( (char*) res, string, pos, base); if(res->len!=3) return a; if( res->pu[2] & 0xFFFF0000 ) {*res=0u; return 0;} return a; } int main(void) {char s[1000], *pc; int rr, h; num n; printf("Inserisci un numero decimale > "); pc=fgets(s, 1000, stdin); if(pc==0) return 0; rr=StrToNum(&n, s, &pc, 10); for(h=0; s[h] ; ++h ); if(s[--h]=='\n') s[h]=0; if(rr==0) {printf("errore\n"); } printf("rr=%i, pc=%s\nHai inserito = ", rr, pc); prx(n); printf("\n"); return 0; }
From: Wolfgang Kern on 2 Apr 2007 11:20 Hello Guga, [...] > btw: I don't use the slow FPU with its constant FLDL2T. > My norm for this int(log(2)) is: > > MOVZX eax B$MSbitNr ;or from a byte reg > IMUL eax 04d10 ;*19728 > SHR eax 010 ;/65536 > > even it results to 0.301025391 > instead of 0.301029996 > it's close enough up to 300 decimal digits > I just tested it with MSbitNr: B$ 320, and the result is 19. ??? Shouldnt it be 96 ? (log(2)*320) Yes it is: 04d10 * 0140 = 0605400 SHR 010 060 = 96 dec But I told it's precision limit is about 300 decimal digits, as above there may be an 'off by one' error. > Also.. how to multiply a value by 10 (with overflow) without mul ? > For speed purposes the fast is: > lea eax D$eax+eax*4 > add eax eax Yes but this works only on smaller than 0_2000_0000 values So in a chained MUL (for larger figures) the overhead may wipe out the speed advantage. > But, how to do it using lea ? not recommendable for larger figures.... > I tried: > xor edx edx > mov eax 745878414 > lea eax D$eax+eax*4 *** the overflow may start here already !!! > add eax eax > jnc L1> THIS WONT WORK! even an "ADC EDX,0" or "SETC DL" may show what you expect in this example ... :) > ; what insert here in case of overflown that > makes edx be equal to 1 ? > L1: > I was looking if Paul Hsieh could have the solutino for the > overflown.. but on his site i found nothing. > www.azillionmonkeys.com/qed/amultl2.html I Paul doesn't have a solution, then there may be none ... :) Other ideas for MUL by TEN ________ (NOT TESTED): MOV ecx eax XOR edx edx ADD eax eax ;*2 ADC edx 5 ADD eax eax ;*2 (*4) ADC edx 2 ADD eax ecx ;+1 (*5) ADC edx 1 ADD eax eax ;*2 (*10) ADC edx 0 24 bytes ~10 cycles aren't really faster than MUL edx:eax=eax*ecx) _________ or: XOR edx edx MOV ecx eax SHLD edx eax 03 ;*8 SHL eax 03 ADD eax ecx ;+1 ADC edx 0 ADD eax ecx ;+1 ADC edx 0 A bit shorter than the above and about same speed (on AMD). I think on newer CPUs the usage of "MUL ecx" isn't too bad at all (5..12 cycles depending on CPU and value). __ wolfgang
From: Wolfgang Kern on 2 Apr 2007 11:26
Hello Guga, > [...] > > > btw: I don't use the slow FPU with its constant FLDL2T. > > My norm for this int(log(2)) is: > > > > MOVZX eax B$MSbitNr ;or from a byte reg > > IMUL eax 04d10 ;*19728 > > SHR eax 010 ;/65536 > > > > even it results to 0.301025391 > > instead of 0.301029996 > > it's close enough up to 300 decimal digits > > > I just tested it with MSbitNr: B$ 320, and the result is 19. > > ??? I also stumbled first over it.... B$ cannot hold more than 255 !!!! :) __ wolfgang |