C language > Expert questions

How can I test a numeric string overflow?

<< < (3/4) > >>

PaoloC13:

--- Quote from: frankie on May 04, 2020, 04:02:00 PM ---Maybe also the use of larger storage should be avoided?

--- End quote ---
I'd say, no, I would just like to practice in speed performances without ready-made things that I can't see how they are coded inside.

frankie:

--- Quote from: PaoloC13 on May 04, 2020, 08:44:40 PM ---
--- Quote from: frankie on May 04, 2020, 04:02:00 PM ---Maybe also the use of larger storage should be avoided?

--- End quote ---
I'd say, no, I would just like to practice in speed performances without ready-made things that I can't see how they are coded inside.

--- End quote ---
The problem again is to trace eventual overflow at each stage, the check for the last bit wasn't enough.
Last fix could be:

--- Code: ---bool UIntOverflow(const char *p)
{
uint32_t v = 0;
while(*p && (*p>='0' && *p<='9'))
{
if (v & 0xe0000000) //if last 3 bits are set multiply
return false; //by 8 or by 2 will overflow
uint32_t tmp = v;
v <<= 3;
if ((v & 0x80000000) && (tmp & 0xc0000000))
return false; //sum with doubled value will overflow
v += tmp << 1; //v*10 done as v*8 + v*2
v += (uint32_t)(*p++ -'0'); //now add next digit
if (tmp > v)
return false; //Overflow
}
return true;
}

--- End code ---

Anyway if the size of storage isn't relevant a more simple form is the following:

--- Code: ---bool UIntOverflow(const char *p)
{
uint64_t v = 0;
while(*p && (*p>='0' && *p<='9'))
{
v = (v * 10) + (uint64_t)(*p++ -'0');
if (v > 4294967295)
return false; //Overflow
}
return true;
}

--- End code ---
Last, for our friends who likes more the assembler, this is a very simple routine in assembler having access to the carry bit.

PaoloC13:
Ok frankie, great work!  ;)
The last one is the most immediate but also the most performing (if we consider 64 bit processors).

The previous one is a masterpiece of bitwise understanding. I will take the time to go deeper into it. I found it is 1.37 (averagely) slower than the last one.

My fix called UIntSafeStr() I found it is 1.12 (averagely) slower than the last one.

Thanks

John Z:
In addition, if you have verified the length of the string before calling this procedure you can speed this up more. There is no need to check the value of v after every digit.  Check it once after all digits have been added.

frankie:
Thanks Paolo.
Just for fun I made it in assember 32bits:

--- Code: ---bool UIntOverflowAsm(const char *p)
{
__asm
{
xor ebx,ebx;
mov edx, p;
repeat:
movsx eax,byte ptr [edx];
cmp eax,0x30; //'0'
jb  success;
cmp eax,0x39; //'9'
ja  success;
sub eax,0x30; //*p-'0'
shl ebx,1; //ebx = val*2
jc  ovflow; //jump if overflow
add eax, ebx; //eax=val*2+actual digit
jc  ovflow; //jump if overflow
shl ebx,1; //ebx=val*4
jc  ovflow; //jump if overflow
shl ebx,1; //ebx=val*8
jc  ovflow; //jump if overflow
add ebx,eax; //ebx=val*8+val*2+actual digit=val*10+actual digit
jc  ovflow; //jump if overflow
inc edx; //p++
jmp repeat;
}
ovflow:
return 0;

success:
return 1;
}

--- End code ---
For 64 bits the C short version is already optimized.
As suggested computing the length of the string can shorter the test, but, apart the time to compute length, the string must not include non numeric characters. I.e. testing for "0 foo bar foo" will fail.

Navigation

[0] Message Index

[#] Next page

[*] Previous page