Prev: OctaOS
Next: DIV overflow
From: Guga on 31 Mar 2007 18:25 On Mar 31, 8:50 am, "Wolfgang Kern" <nowh...(a)never.at> wrote: > Hello Guga, > > < For example, if i have a decimal string as: > < Decimal: > < 48148617815154186478618618618258218 .... > < 687878489746514564564897848745174861831717821729 > > < The correct values i found are: > < [Value: > < Value.Conv32Bit: D$ 0A9549D21 > < Value.Conv64Bit: D$ 056372845 > < Value.Conv96Bit: D$ 0334CD7E6 > < Value.Conv128Bit: D$ 0F2D05D75] > > ??? > > an 128 bit binary value is limited to: > > integer(log(2)*MSbitNr) > > 0,301029 * 128 = 38 decimal digits > > 2^128 = 3,4028236692093846346337460743177... e+38 > > So you should limit the input to 38 digits and to be <2^128. > > I didn't count how many digits you posted here, > but for this ascii-number you might need a 'very large' result buffer. > > ie: you need a 1024-bit result for 308 decimal digits. > > __ > wolfgang Hi wolfgang.. Many, many tks for this formula, i was looking for it. :) For that huge number, i know the decimal string was larger then 128 bits, but, the 1st dwords (128 bits) should be truncated on the proper values. I just posted an small example, and tested some numbers as Herbert proposed, and the results seems accurated. I made a set of those convertions asciito128, asciito80, asciito4096, asciitoany and so on. When i posted the 1st numbers, i was testing several different numbers while i was building the 1st routine for the asciito128 and asciito80. I wanted mainly to follow the logic of those sort of convertions. i´m finishing inserting the comments on them, and after that can i send to you see if they needs improves on speed ? So far, it seems fast, but maybe teher is another way to optimize it. Best Regards, Guga
From: Wolfgang Kern on 1 Apr 2007 07:21 Hello Guga, [..] > an 128 bit binary value is limited to: > > integer(log(2)*MSbitNr) > > 0,301029 * 128 = 38 decimal digits > > 2^128 = 3,4028236692093846346337460743177... e+38 > > So you should limit the input to 38 digits and to be <2^128. > > I didn't count how many digits you posted here, > but for this ascii-number you might need a 'very large' result buffer. > > ie: you need a 1024-bit result for 308 decimal digits. > Many, many tks for this formula, i was looking for it. :) Always welcome :) 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 Also the opposite works that way [determine binary size for MSD decimal digits power] GetPower2 from MSdigit: n = integer(lg(10)(base 2)*power10 of MSD) lg(10)2 = 1/lg(2)10 = 3.321928095 Again, no FLDLG2 is used here: MOVZX eax B$MSDdigitPower ;or from a byte reg IMUL eax 03526A ;*217706 SHR eax 010 ;/65536 results in MUL 3.321929932 instead of 3.321928095 > For that huge number, i know the decimal string was larger then 128 > bits, but, the 1st dwords (128 bits) should be truncated on the proper > values. > I just posted an small example, and tested some numbers as Herbert > proposed, and the results seems accurated. > I made a set of those convertions asciito128, asciito80, asciito4096, > asciitoany and so on. I got only one routine which covers all of them .. > When i posted the 1st numbers, i was testing several different numbers > while i was building the 1st routine for the asciito128 and asciito80. > I wanted mainly to follow the logic of those sort of convertions. > i�m finishing inserting the comments on them, and after that can i > send to you see if they needs improves on speed ? So far, it seems > fast, but maybe teher is another way to optimize it. Oh yes I will, as this a main part of the fun :) __ wolfgang
From: �a/b on 1 Apr 2007 12:15 On 26 Mar 2007 12:39:48 -0700, "Guga" <GugaGTG(a)gmail.com> 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 c++ + assembly below should convert a number show with base 2<=b<=32 in its binary form the number is a class that contain like main members unsigned len; /* how many unsigned is the number long */ unsigned *pu; /* number */ unsigned lung; /* memory reserved for that number */ but it is not secure because i have done almost no test so could be very bugged....... --------------------------- #include <stdio.h> #include <stdlib.h> extern "C" {int StrToNum(char* res, char* string, char** pos, int base);} class num{ public: friend void prx(num* a); friend int StrToNum(num* res, char* string, char** pos, int base); 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*1000); if(pu==0){len=0; lung=0;} else {lung=999; 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]); } int StrToNum(num* res, char* string, char** pos, int base) { return StrToNum( (char*) res, string, pos, base); } int main(void) {char s[1000], *pc; int rr, h; num n; printf("Inserisci un numero in hex > "); pc=fgets(s, 1000, stdin); if(pc<=0) return 0; rr=StrToNum(&n, s, &pc, 16); for(h=0; s[h] ; ++h ); --h; if(s[h]=='\n') s[h]=0; if(rr==0) {printf("errore\n"); return 0;} printf("rr=%i, pc=%s\nHai inserito = ", rr, pc); prx(n); printf("\n"); return 0; } section _DATA public align=4 class=DATA use32 global _StrToNum ; 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 tab dd 0xff , 0xff , 0xff , 0xff , 0xff , 0xff , 0xff , 0xff , 0xff , 0x36ff ; 0 dd 0xff , 0xff , 0xff , 0xff , 0xff , 0xff , 0xff , 0xff , 0xff , 0xff ; 10 dd 0xff , 0xff , 0xff , 0xff , 0xff , 0xff , 0xff , 0xff , 0xff , 0xff ; 20 dd 0xff , 0xff , 0x37ff , 0x1ff , 0xff , 0xff , 0x33ff , 0x35ff , 0xff , 0x34ff ; 30 dd 0x31ff , 0xff , 0xff , 0xff , 0xff , 0x3ff , 0xff , 0xff , 0x0 , 0x1 ; 40 dd 0x2 , 0x3 , 0x4 , 0x5 , 0x6 , 0x7 , 0x8 , 0x9 , 0xff , 0xff ; 50 dd 0xff , 0xff , 0xff , 0xff , 0xff , 0xa , 0xb , 0xc , 0xd , 0xe ; 60 dd 0xf , 0x10 , 0x11 , 0x12 , 0x13 , 0x14 , 0x15 , 0x16 , 0x17 , 0x18 ; 70 dd 0x19 , 0x1a , 0x1b , 0x1c , 0x1d , 0x1e , 0x1f , 0x20 , 0x21 , 0x22 ; 80 dd 0x23 , 0xff , 0xff , 0xff , 0xff , 0xff , 0xff , 0xa , 0xb , 0xc ; 90 dd 0xd , 0xe , 0xf , 0x10 , 0x11 , 0x12 , 0x13 , 0x14 , 0x15 , 0x16 ; 100 dd 0x17 , 0x18 , 0x19 , 0x1a , 0x1b , 0x1c , 0x1d , 0x1e , 0x1f , 0x20 ; 110 dd 0x21 , 0x22 , 0x23 , 0xff , 0xff , 0xff , 0x2ff ; 120 times 132 dd 0xff section _TEXT public align=1 class=CODE use32 ; int ; StrToNum(num[*|&] res, char* string, char** pos, int base) ; eg. char buf[256]={0}, *pc; int val=StrToUns( res, buf, &pc, 10); ; CF==carry flag ; format==<spaces><+><digits> where spaces={' ', '\t'} ; convert the number in format above in the 0 terminated ; string "string" in the base format in a unsigned integer ; 2<=base<=36 possible digits "0123456789[A-Z][a-z]" ; if there is not a number in the above format then ; after the call => (string==pos and CF==1) ; if overflow [mem number not enought] return 0 CF==1 ; if there is (or not) overflow it read all the number ; and save in "pos" the first not digit position ; if all is ok CF==0 and return 1, if error CF==1 and ; return 0 ; 0k, 4j, 8i, 12r, 16c, 20b, 24ra, 28res, 32string, 36pos, 40base _StrToNum: push ebx push ecx push edx push esi push edi push ebp %define @res [esp+28] %define @string [esp+32] %define @pos [esp+36] %define @base [esp+40] mov esi, @string mov edi, @res cmp edi, 0 je .ce cmp dword[edi+4], 0 je .ce cmp dword[edi+8], 1 jb .ce cmp esi, 0 je .ce xor ebx, ebx mov ebp, @base cmp ebp, 36 ja .ce cmp ebp, 1 jbe .ce jmp short .c1 ..c0: inc esi ..c1: cmp byte[esi], ' ' je .c0 cmp byte[esi], 9 je .c0 cmp byte[esi], '+' jne .c2 inc esi ..c2: mov bl, [esi] cmp [tab+4*ebx], ebp jae .ce jmp short .c5 ..ce: mov eax, @pos mov edx, @string mov [eax], edx mov eax, 0 jmp .ca ..c4: inc esi ..c5: cmp byte[esi], '0' je .c4 mov eax, 0 mov dword[edi], 1 mov ebp, [edi+4] mov dword[ebp], 0 mov ecx, 1 ..c6: xor ebx, ebx mov bl, [esi] mov ebx, [tab+4*ebx] cmp ebx, dword @base jae .c8 ..a0: ; moltiplicazione *10 mov eax, [ebp] mul dword @base add eax, ebx adc edx, 0 jc .c7 mov ebx, edx mov [ebp], eax add ebp, 4 dec ecx jnz .a0 cmp edx, 0 je .a1 mov eax, [edi] cmp dword[edi+8], eax jbe .c7 inc dword[edi] mov [ebp], edx ..a1: mov ecx, [edi] mov ebp, [edi+4] inc esi jmp short .c6 ..c7: mov dword[edi], 1 mov ebp, [edi+4] mov dword[ebp], 0 xor ebx, ebx ..a2: inc esi mov bl, [esi] mov edx, [tab+4*ebx] cmp edx, dword @base jb .a2 mov edx, 1 jmp short .c9 ..c8: mov edx, 0 ..c9: mov ebx, @pos mov [ebx], esi cmp edx, 0 jne .ca mov eax, 1 clc jmp short .cf ..ca: mov eax, 0 stc ..cf: %undef @res %undef @string %undef @pos %undef @base pop ebp pop edi pop esi pop edx pop ecx pop ebx ret ---------------------- Inserisci un numero in hex > fffffffffffffffffffffffffffffffffffffffffffffffffff ffffffffffffffffffffffffffffffaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaafffffffffffffffffffffffffffffffffffffffffffffffffffff ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff ffffffffffff aaaaaaaaaaaaaaaaaaaaaaaaaaa rr=1, pc= aaaaaaaaaaaaaaaaaaaaaaaaaaa Hai inserito = 0xfffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa aaaaaaaf ffffffff ffffffff ffffffff ffffffff fffffff f ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffff ff ffffffff ffffffff ffffffff ffffffff;
From: Guga on 1 Apr 2007 14:01 On Apr 1, 4:21 am, "Wolfgang Kern" <nowh...(a)never.at> wrote: > Hello Guga, > > [..] > > > an 128 bit binary value is limited to: > > > integer(log(2)*MSbitNr) > > > 0,301029 * 128 = 38 decimal digits > > > 2^128 = 3,4028236692093846346337460743177... e+38 > > > So you should limit the input to 38 digits and to be <2^128. > > > I didn't count how many digits you posted here, > > but for this ascii-number you might need a 'very large' result buffer. > > > ie: you need a 1024-bit result for 308 decimal digits. > > Many, many tks for this formula, i was looking for it. :) > > Always welcome :) > > 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 > > Also the opposite works that way > [determine binary size for MSD decimal digits power] > > GetPower2 from MSdigit: > > n = integer(lg(10)(base 2)*power10 of MSD) > > lg(10)2 = 1/lg(2)10 = 3.321928095 > > Again, no FLDLG2 is used here: > > MOVZX eax B$MSDdigitPower ;or from a byte reg > IMUL eax 03526A ;*217706 > SHR eax 010 ;/65536 > > results in MUL 3.321929932 > instead of 3.321928095 > > > For that huge number, i know the decimal string was larger then 128 > > bits, but, the 1st dwords (128 bits) should be truncated on the proper > > values. > > I just posted an small example, and tested some numbers as Herbert > > proposed, and the results seems accurated. > > I made a set of those convertions asciito128, asciito80, asciito4096, > > asciitoany and so on. > > I got only one routine which covers all of them .. > > > When i posted the 1st numbers, i was testing several different numbers > > while i was building the 1st routine for the asciito128 and asciito80. > > I wanted mainly to follow the logic of those sort of convertions. > > i´m finishing inserting the comments on them, and after that can i > > send to you see if they needs improves on speed ? So far, it seems > > fast, but maybe teher is another way to optimize it. > > Oh yes I will, as this a main part of the fun :) > > __ > wolfgang Hi wolfgang, tks. But.. are u sure that this MOVZX eax B$MSbitNr ;or from a byte reg IMUL eax 04d10 ;*19728 SHR eax 010 ;/65536 is accurated for number above 300 ? I just tested it with MSbitNr: B$ 320, and the result is 19. Shouldnt it be 96 ? (log(2)*320) 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 but, i wanted the remainder too.to simulatye exactly the mul mnemonic. Example: mov eax 745878414 mov ecx 10 mul ecx Eax = 0BC94038C edx = 01 both forms the correct value: 01BC94038C But, how to do it using lea ? I tried: xor edx edx mov eax 745878414 lea eax D$eax+eax*4 add eax eax jnc L1> ; 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 Best Regards, Guga
From: rhyde on 1 Apr 2007 19:17
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 |