Trying to write itoa

[AnujSuper9]

Hello everyone, I'm working on a small assignment where I am supposed to write the code for the itoa function char* itoa(int Value, int Base); without using any built-in functions, and where the returned value is allocated on behalf of the caller. Value being the integer to convert, and base being octal, decimal, or hex.

I found this rather simple implementation and I was hoping we could discuss it here to see if the changes I'm making are appropriate/accurate and etc.

char* itoa(int val, int base){
  static char buf[32] = {0};
  int i = 30;
  for(; val && i ; --i, val /= base)
    buf[i] = "0123456789abcdef"[val % base];
  return &buf[i+1];
}

Here's my current, pseudo-codey implementation:

char* itoa(int val, int base){

  static char buf[36] = {0};
  buf = (char *) malloc(//...);

  if (val == 0)
    return &buf=0;

  //since base can only be octal, decimal or hex
  if (base != 8 || base != 10 || base != 16)
    printf("Not a valid base.");

  for(int i=30; val && i; --i)
  {
    val /= base;
    buf[i] = "0123456789abcdef"[val % base];
  }

  if(value < 0 && base == 10)
    //make the output negative

  return &buf[i+1];
}

Thanks in advance! :)

[mvmalderen]

I wrote something equal using strings, look at this snippet :) so you can see how it' done ...

Hope this helps !

[WaltP]

Hello everyone, I'm working on a small assignment where I am supposed to write the code for the itoa function char* itoa(int Value, int Base); without using any built-in functions, and where the returned value is allocated on behalf of the caller. Value being the integer to convert, and base being octal, decimal, or hex.

I found this rather simple implementation and I was hoping we could discuss it here to see if the changes I'm making are appropriate/accurate and etc.

OK, have a seat...
1) malloc() -- this will cause memory leaks on each call. Once the function returns, the memory address allocated is lost and can not be returned to the heap. Stick with the static char from the original code.

2)

for(int i=30; val && i; --i)
  {
    val /= base;
    buf[i] = "0123456789abcdef"[val % base];
  }

The first thing you do in the loop is remove the low order digit so if you pass in 2765 you would get back 276.

3)

buf[i] = "0123456789abcdef"[val % base];

This is a trick that I personally would avoid -- but that's just me. Create a char* with the character values.
Also, what happens if the base passed in is > 16? This line will cause a lot of trouble. You need to test for proper base range to protect the program this function is used it.

[vmanes]

Lines 3 & 4 - you create the array buf, then again allocate memory to it? Why using malloc() when you can use the C++ new? You're on the right track, as to return the string you need to allocate with new so the memory exists outside the function's stack allocation. Declare buf as a char*.

Lines 6 & 7 - you probably don't need to worry about special case of 0, just let the code set a 0 in the output string, as it would any other value. Otherwise, if you want to do this, you'll need to put the char '0' into the string, not in the way your line 7 does.

Line 10 - check the logic of the boolean operator you're using. Will that really reject anything other than 8, 10, 16?

Line 16 - clever. I'd never seen that done or considered it.

Watch your index usage. You start out with array of 36 elements, your processing loop starts at index 30. Pick a size! Remember that last valid index is size-1, and that position better contain a NULL terminator for the string.

I do find it a bit problematic that you will return the address of a point inside the block of memory allocated, thus orphaning the memory at the beginning of that block.

[AnujSuper9]

Hmmm, ok. Let me make some adjustments.

char* itoa(int val, int base)
{
  new static char* buf[32] = {0}; //1

  //since base can only be octal, decimal or hex
  if (base != 8 && base != 10 && base != 16) //2
    printf("Not a valid base.");

  for(int i=30; val && i; --i)
  {
    val /= base;
    buf[i] = "0123456789abcdef"[val % base]; //3
  }

  if(value == 0)
    //return char 0 //4

  if(value < 0 && base == 10)
    //make the output negative //5

  return &buf[i+1];
}

1. So 'new' here will work? This will allocate the return value on behalf of the caller?
I was worried that if two consecutive itoa() calls were made, and then they were both output, that the first one would be overridden.

2. LOL, duh, stupid mistake. Thanks vmanes. :P

3. And actually, could someone please explain buf[i] = "0123456789abcdef"[val % base]; to me. I found the trick somewhere else, and kind of understand how it works, but I don't exactly understand HOW it works, if you know what I mean.
WaltP, why would you avoid this trick?

4. With the code the way it is, wouldn't I need a special case to account for a value of 0? Otherwise it won't even run the for loop. Additionally, how should a return a char 0?

5. I'm not sure how to make the output negative here exactly.

--

Watch your index usage. You start out with array of 36 elements, your processing loop starts at index 30. Pick a size! Remember that last valid index is size-1, and that position better contain a NULL terminator for the string.

I changed the array of elements to be 32. This should solve both issues, right?

I do find it a bit problematic that you will return the address of a point inside the block of memory allocated, thus orphaning the memory at the beginning of that block.

How would I go about correcting these issues? I'd really like this implementation to be functional as well as optimally efficient.

---
I was getting frustrated with this implementation I was trying above, so I started working on something much much more basic, and therefore probably a lot less efficient, and no doubt soon to be full of problems as well, but seeing your guys' posts here makes me want to make sure this implementation works moreso than the new one I was going to get at. So please bare with me as I try to get the final function for my code. :)

[AnujSuper9]

So I updated my current implementation in the last post. Does anyone else have any suggestions for me?

[vmanes]

Compile and see where the several mistakes still exist.

Line 3 - declaring buf that way doesn't work. You'll need to declare a pointer, then allocate memory to it. I'd also set the last element as the string terminator.

You use the variable i which is declared in the loop at line 9 in your return statement - at that point, i is out of scope. Declare your variable outside the loop (at the beginning of the function?)

Swap lines 11 and 12. As they are, input of 234 at base 10 gives output of 023. You want to strip off and store the lower values, then discard them.

Line 15 - how can val (value - watch that you use the same names!) be anything but 0 at this point? Unless you sent in a really large number.

Line 19 - really, what do you have to do to make the string represent a negative number? Oh, you've destroyed the initial input, so you don't know what it was. Perhaps you need a variable to modify, but keep the input parameter untouched.

[skatamatic]

Your function makes little to no sense to me. Just think about injecting test values into it. Say you pass it 5, base 10:

5 / 10 = 0.5 = 0 (int)
"0123456789abcdef"[0 % 10] = '0'
Well damn. It's already broken and didn't even give me my single digit!

Now try 15
15 / 10 = 1.5 = 1(int)
"0123456789abcdef"[1 % 10] = '1' --->promising start...?
1 / 10 = 0
"0123456789abcdef"[0 % 10] = '0' ----> aww crap!

I think you're going to have to find an alternate method.
And to explain "0123456789abcdef"[val % base]
Basically this takes the base, divides it by the value, spits out the remainder and that servers as the index of the output char in the string previous to the index operator - [].
This works great for single digits by itself:
"0123456789abcdef"[5 % 10] = '5'

But then it can be argued...so does just using the single digit:
"0123456789abcdef"[5] = '5'

I understand what the original author is trying to do by dividing by the base each time to shrink the number (ie access each digit) but it just doesn't seem to work! Unless, perhaps, I'm missing something...

As for the negative:

char * itoa(int iNum, int iBase)
{
        char* buf = new char[32]; 
        int i = 0;
        if (iNum < 0)
            buf[i++] = '-';
        //...Code...
}

I wouldn't start the for loop at 30 though, i would start it at whatever i is. (either 0 or 1)

[AnujSuper9]

Ok, here is my current implementation:

#include <stdio.h>

char* itoa(int value, int base)
{
  static char* buf = new (char [32]); //1
  buf[31] = '\0';

  if (base != 8 && base != 10 && base != 16)
    printf("Not a valid base.");

  int valuecopy;
  valuecopy = value;

  if(value == 0)
    return buf = '0'; //2, return char 0

  int i = 30;
  for(; valuecopy && i; --i)
  {
    buf[i] = "0123456789abcdef"[valuecopy % base];
    valuecopy /= base;
  }

  if(value < 0 && base == 10)
  {
    --i;
    buf[i] = '-'; //3, make the output negative
  }

  return &buf[i+1];
}

1. Is this right? For the memory allocation of the output.

2. Will this return a char 0? I'm not sure how to write this line.

3. As with 2, will this make the output appear negative? Again, not sure how to write this line.

----
@skatamatic: With the lines switched as per vmanes observation, it should make much more sense. And as for starting at 0 or 1 instead of 30, if I did this, than the resulting string would be reversed, no?

[vmanes]

Does it work? Seems to, except for the line 14/15 part. You cannot assign a single character to the array. You want to put a character '0' into the array and then return the address of where that 0 is, similar to your normal return at the end.

Or just put a '0' in the lowest digit position, and let your processing loop overwrite it, if that 's what happens. If input value was 0, be sure to account for the index i.

Experiment!

[AnujSuper9]

If input value was 0, be sure to account for the index i.

What do you mean by this? In my for loop, one of the conditions is valuecopy && i, so if value is 0, valuecopy will be 0, and then it won't enter the for loop at all and continue like normal.

Anyway, your idea for putting 0 in the buffer is great! Why didn't I think of that.

So if I put on line 7 buf[30]='0'; and then just get rid of lines 14 and 15, that would work! Right?

[vmanes]

What do you mean by this? In my for loop, one of the conditions is valuecopy && i, so if value is 0, valuecopy will be 0, and then it won't enter the for loop at all and continue like normal.

Anyway, your idea for putting 0 in the buffer is great! Why didn't I think of that.

So if I put on line 7 buf[30]='0'; and then just get rid of lines 14 and 15, that would work! Right?

Almost right. If input value is 0, what is the value of i when you get to the return statement? Will the address you return correctly point to the character '0' you put at index 30?

[AnujSuper9]

Whoops, I meant for it to say buf[31]='0'; instead of 30.

In which case the return statement should still be ok.

[AnujSuper9]

Ok, I made some more additions and changes, and I think this is perfect. Pending any of your stamp of approval, of course. :)

So, instead of the buffer size of 32, I added a bit to calculate the length of the result string and instead base it on that.

Here it is:

char* itoa(int value, int base)
{
  int valuecopy;
  valuecopy = value;

  int bufsize=1;
  while(valuecopy > 0)
  {
    valuecopy /= base;
    bufsize++;
  }

  valuecopy = value;

  static char* buf = new (char [bufsize+2]); //1
  buf[bufsize+1] = '\0';
  buf[bufsize] = '0';

  if (base != 8 && base != 10 && base != 16)
    printf("Not a valid base.");

  int i = bufsize;
  for(; valuecopy && i; --i)
  {
    buf[i] = "0123456789abcdef"[valuecopy % base];
    valuecopy /= base;
  }

  if(value < 0 && base == 10)
  {
    --i;
    buf[i] = '-';
  }

  return &buf[i+1];
}

[vmanes]

Test, test, then test some more.

It doesn't appear to correctly handle input value 0 or negatives.

Step through the code (by hand or in a debugger) Follow the values.

[AnujSuper9]

Alas, that's actually one of my problems, is that I don't have visual studio on my current machine, which makes it a lot harder to debug this. :(

Though, aha! I think I see the problem.

When I return &buf[i+1] , in the case of negative numbers, it's stripping off the '-' which should be in , and in the case of zero, the zero is also in , so [i+1] for both of those is wrong.

Also, the original valuecopy check could be negative and mess the whole thing up, so now valuecopy will be the absolute value of value.

So if i change the for loop to a while loop, and put the i-- at the end, it should end with i = i+1. Which would solve the problems I think.

So...

char* itoa(int value, int base)
{
  int valuecopy1, valuecopy2;
  valuecopy1 = value;
  if (valuecopy1 < 0)
    valuecopy1 *= -1;
  valuecopy2 = valuecopy1;

  int bufsize=1;
  while(valuecopy1 > 0)
  {
    valuecopy1 /= base;
    bufsize++;
  }

  static char* buf = new (char [bufsize+2]);
  buf[bufsize+1] = '\0';
  buf[bufsize] = '0';

  if (base != 8 && base != 10 && base != 16)
    printf("Not a valid base.");

  int i = bufsize;
  while(valuecopy2 > 0)
  {
    buf[i] = "0123456789abcdef"[valuecopy2 % base];
    valuecopy2 /= base;
    i--;
  }

  if(value < 0 && base == 10)
  {
    i--;
    buf[i] = '-';
  }

  return &buf[i];
}

[mvmalderen]

Alas, that's actually one of my problems, is that I don't have visual studio on my current machine, which makes it a lot harder to debug this. :(

You can get a free express edition of Visual Studio here :) ...

[AnujSuper9]

Oh sweet, thanks Tux4Life! :)

Ok cool, I'll try that and see what I can get.

[ArkM]

~0.5 years ago, not so far, far away (on DaniWeb forum):
http://www.daniweb.com/forums/thread148080.html
;)

[AnujSuper9]

That's pretty great ArkM, thanks a bunch!

What do you think of my implementation though? It's a little different, because I'm allocating the space on behalf of the caller instead of passing in the return char string.

But otherwise they seem very similar.

[ArkM]

>What do you think of my implementation though?
I don't like both implementations (your and mine).

I'm considering allocating the space on behalf of the caller as a bad practice (except malloc in C, but no need in malloc in C++ ):
1. It's annoying and error-prone to deallocate returned memory on behalf of the callee. It's a narrow pedantry to count this tiny buffer size in relatively expensive (operator divide) loop. As usually, there is some minimal size of an allocated heap chunk in C++ implementations (16 bytes or ever more) so you can't save actual memory expenses.
Another defects:
2. The RTL itoa allows bases in the range 2..36 however you provide 8, 10 and 16 only. Why?
3. It's a bad practice to print messages in low level utility functions (see line #21). For example, it's impossible to use your function in GDI applications (no stdout in this environment).
4. Why buf variable has a static duration? Now your function is not reenterable, we can't use it in multi-threaded environments.
5. No proper argument check out: what happens if base == 0? Why the only arg check inserted in line #20 but we are trying to calculate anything for unacceptable base value in lines 4..18?
6. Why bufsize == 1 for value == 0 but it's equal to 2 for values from 1 to 9?
7. The last but not the least: your implementation returns wrong pointer to the allocated block so impossible to free this memory (see you function epilogue)...
8....

My implementation has the same defect as RTL itoa: possible buffer overflow.

[WaltP]

I'm considering allocating the space on behalf of the caller as a bad practice (except malloc in C, but no need in malloc in C++ ):
1. It's annoying and error-prone to deallocate returned memory on behalf of the callee. It's a narrow pedantry to count this tiny buffer size in relatively expensive (operator divide) loop. As usually, there is some minimal size of an allocated heap chunk in C++ implementations (16 bytes or ever more) so you can't save actual memory expenses.

Exactly! What I said about malloc() in my first post goes for new too. STOP USING IT! Reread what I said.

[AnujSuper9]

Thank you very much for your assessment ArkM. I have some comments and questions.

1. The big reason I'm allocating on behalf of the caller is because it is part of the assignment. Otherwise, believe me, I would much prefer not to.
2. Same. The assignment specifies that the base will only be octal, decimal, or hex.
3. I just needed something to happen to indicate that no other base except for those 3 is allowed. I'm not attached to printing out that message at all. Would you suggest something else?
4. This implementation is meant to be standalone, since it is for the assignment. That's why I did this.
5. Yes, I can't believe I didn't notice this. I moved line 20 up to 8, so hopefully this problem should be avoided.
6. I assume you're referring to base 10 when you say values 1 through 9, but in this case, won't bufsize still be 1? It'll exit the loop when value /= base is 0. Right?
7. I'm sorry, could you please explain this more. I'm not sure I understand what you mean.
8. I assume there is more, but you didn't feel like going into it. i would definitely appreciate any improvements I could make. Most of my limitations come from the specifications of the assignment unfortunately. :-S

Again, some more information on your point #7 would be much appreciated.

My current implementation:

char* itoa(int Value, int Base)
{
//making copies of the absolute value of the input value so as not to destroy it
int valuecopy1, valuecopy2;
valuecopy1 = Value;
if (valuecopy1 < 0)
  valuecopy1 *= -1;
valuecopy2 = valuecopy1;

//check to see if anything other than octal, decimal or hex base is passed
if (Base != 8 && Base != 10 && Base != 16)
{
  printf("Not a valid Base.");
  break;
}

//determine the size of the output buffer string
int bufsize=1;
while (valuecopy1 > 0)
{
  valuecopy1 /= Base;
  bufsize++;
}

//allocate the memory for the output buffer
//bufsize plus the added space for null terminator character and negative sign if appropriate
static char* buf = new (char [bufsize+2]);
buf[bufsize+1] = '\0';  //null terminator
buf[bufsize] = '0';  //initialize with 0 default to be overridden if appropriate

//conversion from int to string happens here
int i = bufsize;
while (valuecopy2 > 0)
{
  //pull last int and convert it to a character and enter it into the end (i) of the buffer
  buf[i] = "0123456789abcdef"[valuecopy2 % Base];
  valuecopy2 /= Base;
  i--;
}

//insert a negative symbol if the value is negative and the base is decimal
if(Value < 0 && Base == 10)
{
  i--;
  buf[i] = '-';
}

//return the output buffer
return &buf[i];
}

Exactly! What I said about malloc() in my first post goes for new too. STOP USING IT! Reread what I said.

What should I do? If I am to allocate on behalf of the caller, I have to do this, no?

[ArkM]

#3: Yes, I can: for example, return "?" or "*" or an empty string or what else (clearly documented) to indicate error conditions.

#4: Well, where is the requirement: we need at least one static variable in the code? ;)

#6: Reread my post again, it's about values, not bases: value == 0 => bufsize == 1; value 1..9 => bufsize == 2 (see while statement in the line #19).

#7: You must return exactly the same pointer value which you got from the operator new (line #27) otherwise it's impossible to free the memory obtained "on behalf of the caller". It's exactly your case: your itoa(0,10) returns buf+1 address. It seems you didn't test your function at all. It's a severe error but I can't see the correspondent requirement: the program must return the pointer value which is unacceptable for dynamically allocated buffer deletion ;)

#8: OK, look at the line 7. The simplest way to change sign: v = -v; The worst one (the most expensive): v *= -1; ;)

[AnujSuper9]

Ok, I fixed everything per your suggestions (thank you very much btw). I'm returning return "?"; , buf is no longer static, I reorganized my while loop to be more appropriate

int bufsize=0;
while (valuecopy1 > 0)
{
	bufsize++;
	valuecopy1 /= Base;
}

and I made it valuecopy1 = -valuecopy1 .

But as for #7, I'm still not sure how to correct this. Are you saying that the returned string will be wrong? Or just that the deletion of the buffer will no be possible? So, in my return statement at the end, this should be return &buf[i+2] ?
If you have some suggestions on what to do to correct this, that would be very helpful.

[AnujSuper9]

Well, I made some other changes, and now I'm confident that it is working. As for the issue of memory leaks, I suppose that will be inevitable though, because I can't return a reference to a std::string object (due to the limitations of the problem), and I can't exactly delete my output buffer, which is the problem that I think you are/were talking about.

If this is the problem you refer to, then I don't know at all how to fix it. If you know of a way, please do let me know.

Otherwise, I think here is a complete and functional version of this problem:

char* itoa(int Value, int Base)
{
	//making copies of the absolute value of the input value so as not to destroy it
	int valuecopy1, valuecopy2;
	valuecopy1 = Value;
	if (valuecopy1 < 0)
		valuecopy1 = -valuecopy1;
	valuecopy2 = valuecopy1;

	//check to see if anything other than octal, decimal or hex base is passed
	if (Base != 8 && Base != 10 && Base != 16)
		return "?";
	
	//determine the size of the output buffer string
	int bufsize=0;
	while (valuecopy1 > 0)
	{
		bufsize++;
		valuecopy1 /= Base;
	}

	//allocate the memory for the output buffer
	//bufsize plus the added space for null terminator character and negative sign if appropriate
	char* buf = new (char [bufsize+2]);
	buf[bufsize+1] = '\0';  //null terminator
	buf[bufsize] = '0';  //initialize with 0 default to be overridden if appropriate

	//conversion from int to string happens here
	int i = bufsize;
	while (valuecopy2 > 0)
	{
		//pull last int and convert it to a character and enter it into the end (i) of the buffer
		buf[i] = "0123456789abcdef"[valuecopy2 % Base];
		valuecopy2 /= Base;
		i--;
	}

	//return at i if zero
	if (Value == 0)
		return &buf[i];

	//insert a negative symbol if the value is negative and the base is decimal
	//and return at i if negative
	if (Value < 0 && Base == 10)
	{
		buf[i] = '-';
		return &buf[i];
	}

	//return the output buffer at i+1
	return &buf[i+1];
}