atoi

atoi

So as some of you may know I am writing my own runtime ( WIP ) and I started the atox / xtoa routine set today.. here's atoi
C&C would be appreciated.

713 lines of code...

Code:

INT RunTime::atoi( LPCSTR lpBuffer )
{
	if( lpBuffer == nullptr )
		return 0;

	INT iReturnValue = 0;

	bool bNegetive = false;

	UINT uiBufferLen = RunTime::strlen( lpBuffer );

	if( uiBufferLen == 0 )
		return 0;

	if( lpBuffer[ 0 ] == '-' )
		bNegetive = true;

	if( ( bNegetive == false && uiBufferLen > 1 ) || ( bNegetive == true && uiBufferLen > 2 ) ){
		UINT uiIter = ( bNegetive == false ) ? 0 : 1;
		for( ; uiIter < uiBufferLen; uiIter++ )
			switch( lpBuffer[ uiIter ] ){
				
				case '0':
					continue;

				case '1':
					switch( uiBufferLen - uiIter ){

						case 1:
							if( bNegetive == false )
								iReturnValue += 1;
							else
								iReturnValue -= 1;
							continue;

						case 2:
							if( bNegetive == false )
								iReturnValue += 10;
							else
								iReturnValue -= 10;
							continue;

						case 3:
							if( bNegetive == false )
								iReturnValue += 100;
							else
								iReturnValue -= 100;
							continue;

						case 4:
							if( bNegetive == false )
								iReturnValue += 1000;
							else
								iReturnValue -= 1000;
							continue;

						case 5:
							if( bNegetive == false )
								iReturnValue += 10000;
							else
								iReturnValue -= 10000;
							continue;

						case 6:
							if( bNegetive == false )
								iReturnValue += 100000;
							else
								iReturnValue -= 100000;
							continue;

						case 7:
							if( bNegetive == false )
								iReturnValue += 1000000;
							else
								iReturnValue -= 1000000;
							continue;

						case 8:
							if( bNegetive == false )
								iReturnValue += 10000000;
							else
								iReturnValue -= 10000000;
							continue;

						case 9:
							if( bNegetive == false )
								iReturnValue += 100000000;
							else
								iReturnValue -= 100000000;
							continue;

						case 10:
							if( bNegetive == false )
								iReturnValue += 1000000000;
							else
								iReturnValue -= 1000000000;
							continue;

						default:
							return 0;
				}
				break;

				case '2':
					switch( uiBufferLen - uiIter ){

						case 1:
							if( bNegetive == false )
								iReturnValue += 2;
							else
								iReturnValue -= 2;
							continue;

						case 2:
							if( bNegetive == false )
								iReturnValue += 20;
							else
								iReturnValue -= 20;
							continue;

						case 3:
							if( bNegetive == false )
								iReturnValue += 200;
							else
								iReturnValue -= 200;
							continue;

						case 4:
							if( bNegetive == false )
								iReturnValue += 2000;
							else
								iReturnValue -= 2000;
							continue;

						case 5:
							if( bNegetive == false )
								iReturnValue += 20000;
							else
								iReturnValue -= 20000;
							continue;

						case 6:
							if( bNegetive == false )
								iReturnValue += 200000;
							else
								iReturnValue -= 200000;
							continue;

						case 7:
							if( bNegetive == false )
								iReturnValue += 2000000;
							else
								iReturnValue -= 2000000;
							continue;

						case 8:
							if( bNegetive == false )
								iReturnValue += 20000000;
							else
								iReturnValue -= 20000000;
							continue;

						case 9:
							if( bNegetive == false )
								iReturnValue += 200000000;
							else
								iReturnValue -= 200000000;
							continue;

						case 10:
							if( bNegetive == false )
								iReturnValue += 2000000000;
							else
								iReturnValue -= 2000000000;
							continue;

						default:
							return 0;
				}
				break;

				case '3':
					switch( uiBufferLen - uiIter ){

						case 1:
							if( bNegetive == false )
								iReturnValue += 3;
							else
								iReturnValue -= 3;
							continue;

						case 2:
							if( bNegetive == false )
								iReturnValue += 30;
							else
								iReturnValue -= 30;
							continue;

						case 3:
							if( bNegetive == false )
								iReturnValue += 300;
							else
								iReturnValue -= 300;
							continue;

						case 4:
							if( bNegetive == false )
								iReturnValue += 3000;
							else
								iReturnValue -= 3000;
							continue;

						case 5:
							if( bNegetive == false )
								iReturnValue += 30000;
							else
								iReturnValue -= 30000;
							continue;

						case 6:
							if( bNegetive == false )
								iReturnValue += 300000;
							else
								iReturnValue -= 300000;
							continue;

						case 7:
							if( bNegetive == false )
								iReturnValue += 3000000;
							else
								iReturnValue -= 3000000;
							continue;

						case 8:
							if( bNegetive == false )
								iReturnValue += 30000000;
							else
								iReturnValue -= 30000000;
							continue;

						case 9:
							if( bNegetive == false )
								iReturnValue += 300000000;
							else
								iReturnValue -= 300000000;
							continue;

						case 10:
							continue;

						default:
							return 0;
				}
				break;

				case '4':
					switch( uiBufferLen - uiIter ){

						case 1:
							if( bNegetive == false )
								iReturnValue += 4;
							else
								iReturnValue -= 4;
							continue;

						case 2:
							if( bNegetive == false )
								iReturnValue += 40;
							else
								iReturnValue -= 40;
							continue;

						case 3:
							if( bNegetive == false )
								iReturnValue += 400;
							else
								iReturnValue -= 400;
							continue;

						case 4:
							if( bNegetive == false )
								iReturnValue += 4000;
							else
								iReturnValue -= 4000;
							continue;

						case 5:
							if( bNegetive == false )
								iReturnValue += 40000;
							else
								iReturnValue -= 40000;
							continue;

						case 6:
							if( bNegetive == false )
								iReturnValue += 400000;
							else
								iReturnValue -= 400000;
							continue;

						case 7:
							if( bNegetive == false )
								iReturnValue += 4000000;
							else
								iReturnValue -= 4000000;
							continue;

						case 8:
							if( bNegetive == false )
								iReturnValue += 40000000;
							else
								iReturnValue -= 40000000;
							continue;

						case 9:
							if( bNegetive == false )
								iReturnValue += 400000000;
							else
								iReturnValue -= 400000000;
							continue;

						case 10:
							continue;

						default:
							return 0;
				}
				break;

				case '5':
					switch( uiBufferLen - uiIter ){
	
						case 1:
							if( bNegetive == false )
								iReturnValue += 5;
							else
								iReturnValue -= 5;
							continue;

						case 2:
							if( bNegetive == false )
								iReturnValue += 50;
							else
								iReturnValue -= 50;
							continue;

						case 3:
							if( bNegetive == false )
								iReturnValue += 500;
							else
								iReturnValue -= 500;
							continue;

						case 4:
							if( bNegetive == false )
								iReturnValue += 5000;
							else
								iReturnValue -= 5000;
							continue;

						case 5:
							if( bNegetive == false )
								iReturnValue += 50000;
							else
								iReturnValue -= 50000;
							continue;

						case 6:
							if( bNegetive == false )
								iReturnValue += 500000;
							else
								iReturnValue -= 500000;
							continue;

						case 7:
							if( bNegetive == false )
								iReturnValue += 5000000;
							else
								iReturnValue -= 5000000;
							continue;

						case 8:
							if( bNegetive == false )
								iReturnValue += 50000000;
							else
								iReturnValue -= 50000000;
							continue;

						case 9:
							if( bNegetive == false )
								iReturnValue += 500000000;
							else
								iReturnValue -= 500000000;
							continue;

						case 10:
							continue;

						default:
							return 0;
				}
				break;

				case '6':
					switch( uiBufferLen - uiIter ){

						case 1:
							if( bNegetive == false )
								iReturnValue += 6;
							else
								iReturnValue -= 6;
							continue;

						case 2:
							if( bNegetive == false )
								iReturnValue += 60;
							else
								iReturnValue -= 60;
							continue;

						case 3:
							if( bNegetive == false )
								iReturnValue += 600;
							else
								iReturnValue -= 600;
							continue;

						case 4:
							if( bNegetive == false )
								iReturnValue += 6000;
							else
								iReturnValue -= 6000;
							continue;

						case 5:
							if( bNegetive == false )
								iReturnValue += 60000;
							else
								iReturnValue -= 60000;
							continue;

						case 6:
							if( bNegetive == false )
								iReturnValue += 600000;
							else
								iReturnValue -= 600000;
							continue;

						case 7:
							if( bNegetive == false )
								iReturnValue += 6000000;
							else
								iReturnValue -= 6000000;
							continue;

						case 8:
							if( bNegetive == false )
								iReturnValue += 60000000;
							else
								iReturnValue -= 60000000;
							continue;

						case 9:
							if( bNegetive == false )
								iReturnValue += 600000000;
							else
								iReturnValue -= 600000000;
							continue;

						case 10:
							continue;

						default:
							return 0;
				}
				break;

				case '7':
					switch( uiBufferLen - uiIter ){

						case 1:
							if( bNegetive == false )
								iReturnValue += 7;
							else
								iReturnValue -= 7;
							continue;

						case 2:
							if( bNegetive == false )
								iReturnValue += 70;
							else
								iReturnValue -= 70;
							continue;

						case 3:
							if( bNegetive == false )
								iReturnValue += 700;
							else
								iReturnValue -= 700;
							continue;

						case 4:
							if( bNegetive == false )
								iReturnValue += 7000;
							else
								iReturnValue -= 7000;
							continue;

						case 5:
							if( bNegetive == false )
								iReturnValue += 70000;
							else
								iReturnValue -= 70000;
							continue;

						case 6:
							if( bNegetive == false )
								iReturnValue += 700000;
							else
								iReturnValue -= 700000;
							continue;

						case 7:
							if( bNegetive == false )
								iReturnValue += 7000000;
							else
								iReturnValue -= 7000000;
							continue;

						case 8:
							if( bNegetive == false )
								iReturnValue += 70000000;
							else
								iReturnValue -= 70000000;
							continue;

						case 9:
							if( bNegetive == false )
								iReturnValue += 700000000;
							else
								iReturnValue -= 700000000;
							continue;

						case 10:
							continue;

						default:
							return 0;
				}
				break;

				case '8':
					switch( uiBufferLen - uiIter ){

						case 1:
							if( bNegetive == false )
								iReturnValue += 8;
							else
								iReturnValue -= 8;
							continue;

						case 2:
							if( bNegetive == false )
								iReturnValue += 80;
							else
								iReturnValue -= 80;
							continue;

						case 3:
							if( bNegetive == false )
								iReturnValue += 800;
							else
								iReturnValue -= 800;
							continue;

						case 4:
							if( bNegetive == false )
								iReturnValue += 8000;
							else
								iReturnValue -= 8000;
							continue;

						case 5:
							if( bNegetive == false )
								iReturnValue += 80000;
							else
								iReturnValue -= 80000;
							continue;

						case 6:
							if( bNegetive == false )
								iReturnValue += 800000;
							else
								iReturnValue -= 800000;
							continue;

						case 7:
							if( bNegetive == false )
								iReturnValue += 8000000;
							else
								iReturnValue -= 8000000;
							continue;

						case 8:
							if( bNegetive == false )
								iReturnValue += 80000000;
							else
								iReturnValue -= 80000000;
							continue;

						case 9:
							if( bNegetive == false )
								iReturnValue += 800000000;
							else
								iReturnValue -= 800000000;
							continue;

						case 10:
							continue;

						default:
							return 0;
				}
				break;

				case '9':
					switch( uiBufferLen - uiIter ){

						case 1:
							if( bNegetive == false )
								iReturnValue += 9;
							else
								iReturnValue -= 9;
							continue;

						case 2:
							if( bNegetive == false )
								iReturnValue += 90;
							else
								iReturnValue -= 90;
							continue;

						case 3:
							if( bNegetive == false )
								iReturnValue += 900;
							else
								iReturnValue -= 900;
							continue;

						case 4:
							if( bNegetive == false )
								iReturnValue += 9000;
							else
								iReturnValue -= 9000;
							continue;

						case 5:
							if( bNegetive == false )
								iReturnValue += 90000;
							else
								iReturnValue -= 90000;
							continue;

						case 6:
							if( bNegetive == false )
								iReturnValue += 900000;
							else
								iReturnValue -= 900000;
							continue;

						case 7:
							if( bNegetive == false )
								iReturnValue += 9000000;
							else
								iReturnValue -= 9000000;
							continue;

						case 8:
							if( bNegetive == false )
								iReturnValue += 90000000;
							else
								iReturnValue -= 90000000;
							continue;

						case 9:
							if( bNegetive == false )
								iReturnValue += 900000000;
							else
								iReturnValue -= 900000000;
							continue;

						case 10:
							continue;

						default:
							return 0;
				}
				break;

				default:
					return 0;
		}
	}
	else{

		if( ( bNegetive == false && lpBuffer[ 0 ] > 48 && lpBuffer[ 0 ] < 58 ) || ( bNegetive == true && lpBuffer[ 1 ] > 48 && lpBuffer[ 1 ] < 58 ) )
			iReturnValue = ( bNegetive == false ) ? ( lpBuffer[ 0 ] - 48 ) : -( lpBuffer[ 1 ] - 48 );
		else
			return 0;
	}

	return iReturnValue;
}

The solution can be a lot easier than that (and I don't claim that mine is the most optimal) just that its much simpler. YOu can exploit that fact that the ascii values '1' through '9' are in a linear sequence, one after the other. Then the rest is just figuring out to which power you want to put the number.

Code:

#include "stdafx.h"

#include <math.h>
#include <string.h>

#include <cassert>
#include <climits>

#define CHARTOINT(x) (x - ('1' - 1)) 

int myAtoi(const char* sNumber)
{
    const char *sScale = (sNumber[0] == '-' ? &sNumber[1] : sNumber);

    int iNumber = 0;

    for(unsigned char i = strlen(sScale); i > 0; i--)
        iNumber += CHARTOINT(sScale[i - 1]) * (int)pow(10, (double)strlen(sScale) - i);

    assert(iNumber <= INT_MAX);

    return iNumber *= (sNumber[0] == '-' ? -1 : 1);
}

Your method is essentially using a look-up table, which could cost a lot of memory. Typically though, look up tabes are able to perform more quickly due to their simplistic nature (i.e, implemented with simple addition and subtraction). However, using a look-up table for something like atoi is a waste of space even on a microcontroller, since the cost of space doesn't justify the micro-optimization introduced.

Look up tables are a good idea with, i.e, sin\cos computations, if their taylor series (or whatever model they use to compute it) is too slow.

Here's my version because I'm supposed to be studying and procrastination is fun!

Code:

int _atoi(const char *str) {
	while(*str && isspace(*str)) { ++str; }
	if ((*str != '-') && (*str != '+') && !isdigit(*str)) { return 0; }

	int value = 0;
	bool negative = *str == '-';
	if (negative || *str == '+') { ++str; }
	
	while(isdigit(*str)) {
		value = (value * 10) + (*str++ - '0');
	}

	return negative ? -value : value;
}

At the moment this doesn't fit the spec if the "str" parameter has a ridiculously large number. I.e

Code:

_atoi("123473258364587364856387456"); 
// won't return the same as
atoi("123473258364587364856387456");

But I'll leave that up to you to implement

@Jetamay Will your assert ever fire? Given that you're using an INT datatype to store the number, and the wraparound nature of integer addition, I don't think it can ever hold anything > INT_MAX, can it?

this is very rudimentary and basic code that I just made on the spot. Doesn't have error checking either, but gets the job done in the end. Just don't feed it anything invalid

Just wrote it on notepad, pretty sure it works but not 100% positive.

Code:

int atoi(const char* sNum)
{
	int number = 0;
	for(; *sNum != 0; sNum++)
	{
		number = number * 10 + (*sNum -'0');
	}
	if(sNum[0] == '-')
	{
		number *= -1;
	}	
	return number;
}

wow, being CS even capitalizes code

@Jetamay I plan on benchmarking a few different implementations - this isn't a final version. The thing that concerns me about your implementation is the backwards loop float/double to int and vice versa conversions ( as those in general are expensive operations ) and I'm not -positive- on the implementation of pow but I believe that uses a loop too. Thank you for your input though, I appreciate it! @Jason I thought of something similar to yours when I woke up today and I face palmed.. Like I said above I plan on writing multiple implementations and benchmarking them and then picking a final candidate.

Originally Posted by Jason

Here's my version because I'm supposed to be studying and procrastination is fun!

Code:

int _atoi(const char *str) {
    while(*str && isspace(*str)) { ++str; }
    if ((*str != '-') && (*str != '+') && !isdigit(*str)) { return 0; }

    int value = 0;
    bool negative = *str == '-';
    if (negative || *str == '+') { ++str; }
    
    while(isdigit(*str)) {
        value = (value * 10) + (*str++ - '0');
    }

    return negative ? -value : value;
}

At the moment this doesn't fit the spec if the "str" parameter has a ridiculously large number. I.e

Code:

_atoi("123473258364587364856387456"); 
// won't return the same as
atoi("123473258364587364856387456");

But I'll leave that up to you to implement

Originally Posted by ~FALLEN~

The thing that concerns me about your implementation is the backwards loop float/double to int and vice versa conversions ( as those in general are expensive operations )

It'd be completely pointless to optmize out the typecasts unless you are programming a _VERY_ _VERY_ slow microcontroller. Even then it might be considered a micro-optimization and you shouldn't be programming in C anyways.

and I'm not -positive- on the implementation of pow but I believe that uses a loop too.

It is, and that is why Jason's solution is much more optimal. I didn't explore optimizations to my solution in all honesty, it is just something I wrote up quickly to illustrate recursion to significantly simplify the solution.

713 lines for ATOI? WTF m8

Originally Posted by Dave84311

713 lines for ATOI? WTF m8

Yup LOL
On the brightside the other atox and xtoa functions won't be too different.

Originally Posted by Jetamay

Lol... didn't think about that. Good point...

Better approach might be to check for negative sign at the end, but even then, that doesn't guarantee anything if it is overflown more than once. You could also assert inside the for loop to assure the significance of each digit doesn't exceed the max integer value - which should work fine to avoid a double overflow.

It'd be completely pointless to optmize out the typecasts unless you are programming a _VERY_ _VERY_ slow microcontroller. Even then it might be considered a micro-optimization and you shouldn't be programming in C anyways.

It is, and that is why Jason's solution is much more optimal. I didn't explore optimizations to my solution in all honesty, it is just something I wrote up quickly to illustrate recursion to significantly simplify the solution.

I think the best way would be to implement it like so:

Code:

int __atoi(const char *str) {
	// runtime assertion
	assert(str != NULL);
	// ignore initial whitespace characters
    for(;isspace(*str); ++str);
	// validate the first character to make sure there is actually a number
    if ((*str != '-') && (*str != '+') && !isdigit(*str)) { 
		return 0; 
	}

    bool negative = *str == '-';
	long long value = 0;

    if (negative || *str == '+') { 
		++str; 
	}

    while(isdigit(*str)) {
        value = (value * 10) + (*str++ - '0');
        if (value > INT_MAX || value < INT_MIN) { 
            return value > INT_MAX ? INT_MAX : INT_MIN;
        }
    }

    return (int)(negative ? -value : value);
}

i.e use a bigger storage type than int to hold the value during calculation (allowing the number to overflow INT_MAX or INT_MIN, then check for this situation and return early if that's the case. I was originally going to do the check a single time during the final return, then realized you'd have the same problem if the number was bigger than a long long's max value (wraparound)

Post a Reply

Tags for this Thread