Unsigned int to ascii in C

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Prelates, Moderators General

Unsigned int to ascii in C

Postby Little Richie » Tue Nov 22, 2011 8:02 am UTC

I was presented with a problem that I need some help on.

The Problem:
A routine that will convert an unsigned integer from Binary to an ASCII string suitable for output. That means you must handle unsigned signed numbers ranging from 0 to 4294967295. For extra credit you can make it work for signed values as well, ranging from -2147483648 to 2147483647. For Extra-Extra Credit, make it work for 64-bit values.

Remember, the key points are:

1) It must work...
2) It should be as general as possible
3) It should be small and fast
4) It should be easy to read and modify
5) It should be commented.

So,

If the input is 0x7B (1111011 binary), the answer would be a string of four (4) bytes containing:

0x31 0x32 0x33 0x00

which is the hex equivalent of the C zero terminated string "123".

The man I am learning from wants me to do all of his problems using the most basic operations, bitwise preferred.
Some of the solutions I have seen online are far to simple, and rely on outside or more than the "basic" functions.

Please start with the "bad" way to do this, and walk me up, so I can have a better understanding.

I think I logically know what to do, but I'm not sure...
From what I grasp, I want to take the input, look at each decimal place, and somehow (maybe a lookup table) convert that to ascii.

There is no time limit for this, nor is this for school.
Thanks!
With man gone, will there be hope for gorilla?
Check out my blog, my mission to save the world.
User avatar
Little Richie
 
Posts: 127
Joined: Tue Feb 05, 2008 3:02 am UTC
Location: Orlando, Florida

Re: Unsigned int to ascii in C

Postby Jplus » Tue Nov 22, 2011 3:30 pm UTC

You'll learn most from this if you try it on your own first, then tell us where you get stuck. On the way we can also point out some ways to improve the code that already works.

If you think you know what to do, but you're not sure, just try it out. Hint: you don't need a full-blown lookup table in order to convert decimal values to their corresponding ascii-coded digits.
Feel free to call me Julian. J+ is just an abbreviation.
Image coding and xkcd combined
User avatar
Jplus
 
Posts: 1538
Joined: Wed Apr 21, 2010 12:29 pm UTC
Location: classified

Re: Unsigned int to ascii in C

Postby headprogrammingczar » Tue Nov 22, 2011 4:11 pm UTC

sprintf should be enough to get you started.
<quintopia> You're not crazy. you're the goddamn headprogrammingspock!
<Weeks> You're the goddamn headprogrammingspock!
<Cheese> I love you
User avatar
headprogrammingczar
 
Posts: 3023
Joined: Mon Oct 22, 2007 5:28 pm UTC
Location: Beaming you up

Re: Unsigned int to ascii in C

Postby SWGlassPit » Tue Nov 22, 2011 5:34 pm UTC

headprogrammingczar wrote:sprintf should be enough to get you started.

I'm pretty sure he's supposed to be a little more bare-metal than that. Basic (if not even bitwise) operations.
Up in space is a laboratory the size of a football field zipping along at 7 km/s. It's my job to keep it safe.
Image
Erdös number: 5
User avatar
SWGlassPit
 
Posts: 312
Joined: Mon Feb 18, 2008 9:34 pm UTC
Location: Houston, TX

Re: Unsigned int to ascii in C

Postby Little Richie » Tue Nov 22, 2011 10:49 pm UTC

SWGlassPit wrote:
headprogrammingczar wrote:sprintf should be enough to get you started.

I'm pretty sure he's supposed to be a little more bare-metal than that. Basic (if not even bitwise) operations.


Yeah, you are right, that would be cheating.
He told me today that I shouldn't even need to use casting.

Am I on the right track going to decimal and then looking at every digit through a modulus or devision? Or is counting the on bits making this harder than it needs to be?

I think my biggest problem is not knowing the last step before printf.
With man gone, will there be hope for gorilla?
Check out my blog, my mission to save the world.
User avatar
Little Richie
 
Posts: 127
Joined: Tue Feb 05, 2008 3:02 am UTC
Location: Orlando, Florida

Re: Unsigned int to ascii in C

Postby PM 2Ring » Wed Nov 23, 2011 6:24 pm UTC

Little Richie wrote:Am I on the right track going to decimal and then looking at every digit through a modulus or devision?

That sounds good. You should give it a try & see what happens. Hint: you will need to use both modulus and division.

Little Richie wrote:Or is counting the on bits making this harder than it needs to be?

This program doesn't need to examine individual bits.

Little Richie wrote:I think my biggest problem is not knowing the last step before printf.

What?

Do you understand how to assemble the ASCII characters representing the digits of the number into a printable string?
User avatar
PM 2Ring
 
Posts: 3233
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

Re: Unsigned int to ascii in C

Postby You, sir, name? » Thu Nov 24, 2011 6:51 am UTC

PM 2Ring wrote:
Little Richie wrote:Or is counting the on bits making this harder than it needs to be?

This program doesn't need to examine individual bits.


It's fairly easy to implement with bitwise operators though, which is what I assume Richie means.
I now occasionally update my rarely-updated blog.

I edit my posts a lot and sometimes the words wrong order words appear in sentences get messed up.
User avatar
You, sir, name?
 
Posts: 6493
Joined: Sun Apr 22, 2007 10:07 am UTC
Location: Chako Paul City

Re: Unsigned int to ascii in C

Postby PM 2Ring » Thu Nov 24, 2011 7:39 am UTC

PM 2Ring wrote:Hint: you will need to use both modulus and division.

Although you can do the modulus operation indirectly, via division and subtraction.

You, sir, name? wrote:It's fairly easy to implement with bitwise operators though

I'd agree if we were converting to a binary power base, but I don't see a simple way to convert to decimal using bitwise operators.
User avatar
PM 2Ring
 
Posts: 3233
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

Re: Unsigned int to ascii in C

Postby You, sir, name? » Thu Nov 24, 2011 4:39 pm UTC

PM 2Ring wrote:
You, sir, name? wrote:It's fairly easy to implement with bitwise operators though

I'd agree if we were converting to a binary power base, but I don't see a simple way to convert to decimal using bitwise operators.


Huh, I read the problem as printing it as hexadecimal. But no matter, you can still express division by numbers-near-powers-of-2 with repeated bit-shifting and addition and/or subtraction.

You can demonstrate this fairly simply (I'll do 1/5, as you can go from that to 1/10 by simple bit shifting), it's slightly more complex with straight division by 10.

We're looking for the difference between dividing by 5 and dividing by 4
1/5 - 1/4 = (4 - 5)/20
Move this around a bit
1/5 = 1/4 - (1/4)(1/5)
Hey, 1/5 occurs on both sides. This means we get a recursive definition
1/5 = 1/4 - (1/4)(1/4 - (1/4)(1/5)) = 1/4 - 1/16 + (1/16)*(1/5)
Rinse & repeat.

Here's how it looks in code:
Code: Select all
nt divideby5(unsigned char i) {
  int r = i - (i >> 2) + (i >> 4) - (i >> 6) + (i >> 8);
  return r >> 2;
}


(you divide by 3 by adding all numbers, rather than doing alternating subtraction)

The exact formulation with a delayed divide-by-4 is crucial for not getting rounding errors.
I now occasionally update my rarely-updated blog.

I edit my posts a lot and sometimes the words wrong order words appear in sentences get messed up.
User avatar
You, sir, name?
 
Posts: 6493
Joined: Sun Apr 22, 2007 10:07 am UTC
Location: Chako Paul City

Re: Unsigned int to ascii in C

Postby PM 2Ring » Thu Nov 24, 2011 7:37 pm UTC

You, sir, name? wrote:Huh, I read the problem as printing it as hexadecimal.

That's what I suspected. :)

You, sir, name? wrote:But no matter, you can still express division by numbers-near-powers-of-2 with repeated bit-shifting and addition and/or subtraction.
[stuff about expressing fractions in balanced binary]

Certainly. I wouldn't call that technique simple, though. And while it's nice to know that stuff, it's probably not a good way to approach this assignment. Code that uses clever arcane tricks may be impressive, but it's also evil, especially when a straight-forward method supported directly by operators in the language can be utilised.
User avatar
PM 2Ring
 
Posts: 3233
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

Re: Unsigned int to ascii in C

Postby You, sir, name? » Thu Nov 24, 2011 7:50 pm UTC

PM 2Ring wrote:
You, sir, name? wrote:But no matter, you can still express division by numbers-near-powers-of-2 with repeated bit-shifting and addition and/or subtraction.
[stuff about expressing fractions in balanced binary]

Certainly. I wouldn't call that technique simple, though. And while it's nice to know that stuff, it's probably not a good way to approach this assignment. Code that uses clever arcane tricks may be impressive, but it's also evil, especially when a straight-forward method supported directly by operators in the language can be utilised.


Well, the OP said he preferred bitwise operators. There's generally few cases you can answer such a request without resorting to this sort of voodoo.
I now occasionally update my rarely-updated blog.

I edit my posts a lot and sometimes the words wrong order words appear in sentences get messed up.
User avatar
You, sir, name?
 
Posts: 6493
Joined: Sun Apr 22, 2007 10:07 am UTC
Location: Chako Paul City

Re: Unsigned int to ascii in C

Postby Yakk » Thu Nov 24, 2011 8:04 pm UTC

Yep. But easy to read and modify that is not. :)
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
User avatar
Yakk
Poster with most posts but no title.
 
Posts: 10377
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Unsigned int to ascii in C

Postby You, sir, name? » Thu Nov 24, 2011 9:15 pm UTC

Yakk wrote:Yep. But easy to read and modify that is not. :)


Bit twiddling seldom is.
I now occasionally update my rarely-updated blog.

I edit my posts a lot and sometimes the words wrong order words appear in sentences get messed up.
User avatar
You, sir, name?
 
Posts: 6493
Joined: Sun Apr 22, 2007 10:07 am UTC
Location: Chako Paul City

Re: Unsigned int to ascii in C

Postby Yakk » Thu Nov 24, 2011 9:28 pm UTC

1) It must work...
2) It should be as general as possible
3) It should be small and fast
4) It should be easy to read and modify
5) It should be commented.

And that is why you fail. :)

...

So, the data you have isn't arranged with decimal places. It is packed binary data in what is known as 2s completement. Now, you don't care about this, unless you are bit twiddling.

Instead, your goal should be "how would I define a mathematical function that, given a number, returns the last digit?"

Converting to ascii is actually easy, and a distraction from the main problem. (In C, char is actually an integer type. So char constants, like '0', are actually char's and hence integers. As it happens, '1' - '0' = 1, and '5' - '0' = 5.)

Alternatively, you can just do a big switch statement on the digit you have to generate the char. Or, you can build an array of size 10, where the nth entry is the decimal digit.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
User avatar
Yakk
Poster with most posts but no title.
 
Posts: 10377
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Unsigned int to ascii in C

Postby Little Richie » Wed Nov 30, 2011 10:23 am UTC

I think I am getting held up on the easy part of this problem.
My problem, as I'm seeing, is not the code before the printf, but the use of printf.

I can get each digit down to it's ASCI equivalent binary/hex, but I don't know how to use printf to let it know to treat it as asci.

Any help would be great.

Edit:
PM 2Ring wrote:Do you understand how to assemble the ASCII characters representing the digits of the number into a printable string?

No, I didn't.
I was playing around with it a bit more, and I figured it out. At first I was trying to use %d, because I didn't know about printf, then I thought that %s would work, because I wanted it to be a string, finally, %c did the job. I'm still unclear as to why %s didn't work, probably because of my formatting. Could I have an example of %s with a many-character output.

Edit2:
Let me be more clear

int foo = 0x32;
printf("%s",foo);

gives me an error.

int foo = 0x32;
printf("%c",foo);

prints a "2"
With man gone, will there be hope for gorilla?
Check out my blog, my mission to save the world.
User avatar
Little Richie
 
Posts: 127
Joined: Tue Feb 05, 2008 3:02 am UTC
Location: Orlando, Florida

Re: Unsigned int to ascii in C

Postby PM 2Ring » Wed Nov 30, 2011 1:14 pm UTC

Little Richie wrote: At first I was trying to use %d, because I didn't know about printf, then I thought that %s would work, because I wanted it to be a string, finally, %c did the job. I'm still unclear as to why %s didn't work, probably because of my formatting. Could I have an example of %s with a many-character output.

Edit2:
Let me be more clear

int foo = 0x32;
printf("%s",foo);

gives me an error.

int foo = 0x32;
printf("%c",foo);

prints a "2"


printf() is a special kind of function that takes a variable number of arguments. The first argument, the format string, lets printf know how many other arguments there will be, and what their types are. Each formatting sequence, like %d, %s or %c, must be matched up with a corresponding argument of the correct type.

Your example above using %s doesn't work because %s tells printf to print chars from a nul-terminated string of chars. The argument corresponding to %s must be the address of the first char in the string. But the argument you supplied is a plain int. The most straightforward way to give printf a proper argument for a %s format specifier is to use a char array, or a pointer to char.

Here's a silly example that assembles a string of digits into a char array and then prints it. Notice that after we've put the chars we want to print into the array we need to terminate the string with a nul byte (0x00) - this is a C convention used by the standard string handling functions to indicate where a string ends.

Code: Select all
#include <stdio.h>

int main(int argc, char *argv[])
{
    char s[11];
    int i;

    for (i=0; i<10; i++)
    {
        s[i] = i + '0';
    }
    s[i] = '\0';

    printf("%s\n", s);

    return 0;
}
User avatar
PM 2Ring
 
Posts: 3233
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

Re: Unsigned int to ascii in C

Postby Yakk » Wed Nov 30, 2011 1:39 pm UTC

Little Richie wrote:I think I am getting held up on the easy part of this problem.
My problem, as I'm seeing, is not the code before the printf, but the use of printf.

I can get each digit down to it's ASCI equivalent binary/hex, but I don't know how to use printf to let it know to treat it as asci.

Demonstrate turning a digit into it's ASCII (not ASCI) equivalent integer.

There are ways you could think you are doing the right thing without actually doing the right thing. Saying you know how to do X doesn't mean you actually know how to do it, you could easily be mistaken.
int foo = 0x32;
printf("%c",foo);

prints a "2"

Do you know why it prints 2? And what printf("%c", 0x31) would do -- without trying it? (Once you try it, of course it is easy to know what it would do!)

How about printf("%c", 0x41)?

(I'm actually looking for a particular kind of error in your thinking here, which is why I'm asking for what you think it will do before trying it. Saying "I do not know" is acceptable, unless you think you do)
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
User avatar
Yakk
Poster with most posts but no title.
 
Posts: 10377
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Unsigned int to ascii in C

Postby EvanED » Wed Nov 30, 2011 4:33 pm UTC

The other suggestion is figure out what your compiler flag is that will give you warnings about incorrect printf format strings. You still have to figure out why it's wrong and fix it, but at least your compiler would tell you that it is wrong.
EvanED
 
Posts: 4113
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI

Re: Unsigned int to ascii in C

Postby Little Richie » Wed Nov 30, 2011 10:29 pm UTC

Yakk wrote:int foo = 0x32;
printf("%c",foo);

prints a "2"

Do you know why it prints 2? And what printf("%c", 0x31) would do -- without trying it? (Once you try it, of course it is easy to know what it would do!)

How about printf("%c", 0x41)?

(I'm actually looking for a particular kind of error in your thinking here, which is why I'm asking for what you think it will do before trying it. Saying "I do not know" is acceptable, unless you think you do)


printf("%c", 0x31) : "1"
printf("%c", 0x41) : I believe this is an "A"

I'm not sure what you're getting at, but I think I do understand this part of it.

PM 2Ring wrote:Your example above using %s doesn't work because %s tells printf to print chars from a nul-terminated string of chars. The argument corresponding to %s must be the address of the first char in the string. But the argument you supplied is a plain int. The most straightforward way to give printf a proper argument for a %s format specifier is to use a char array, or a pointer to char.

Here's a silly example that assembles a string of digits into a char array and then prints it. Notice that after we've put the chars we want to print into the array we need to terminate the string with a nul byte (0x00) - this is a C convention used by the standard string handling functions to indicate where a string ends.


That makes a lot more sense now, but is there any way to do this without knowing beforehand how many characters I will be needing? We don't want to waste memory!
With man gone, will there be hope for gorilla?
Check out my blog, my mission to save the world.
User avatar
Little Richie
 
Posts: 127
Joined: Tue Feb 05, 2008 3:02 am UTC
Location: Orlando, Florida

Re: Unsigned int to ascii in C

Postby Yakk » Thu Dec 01, 2011 5:34 am UTC

Heh, just making sure you didn't think printf("%c", 0x77) would print 7, as it is the last "character" of 0x77... :)

So your next problem is to either use a static or stack buffer of characters, or malloc one off the heap.

Assuming that int has a known finite size is one approach. Then create a buffer big enough to fit it.

Fancier methods might involve using malloc and realloc to grow the buffer.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
User avatar
Yakk
Poster with most posts but no title.
 
Posts: 10377
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Unsigned int to ascii in C

Postby PM 2Ring » Thu Dec 01, 2011 10:49 am UTC

Little Richie wrote:That makes a lot more sense now, but is there any way to do this without knowing beforehand how many characters I will be needing? We don't want to waste memory!

Yes, there is. You could use a modern C compiler that permits a variable size in the array declaration. That's the simplest way, although some may consider that's cheating, and your teacher may want you to learn the traditional techniques first.

As Yakk said, you can dynamically allocate the buffer using malloc(). But in this situation I'd go for the fixed length buffer, since we're only talking about a measly 11 bytes. The extra code required to dynamically allocate (and free) a buffer would probably end up wasting more memory than it would save. Also, when memory is allocated there's some additional "invisible" memory consumed.

Firstly, there's a header added to your memory block to store its size and to link it into a list. free() needs to know how big a memory block is to deallocate it properly, and any memory that you allocate but don't explicitly free gets freed automatically at program termination. The linked list makes it possible for the "system" to find all of your un-freed blocks.

Secondly, for reasons of efficiency (and because of those hidden memory requirements) the memory allocator never hands out single bytes: requests are usually rounded up to some sensible quantity, like a round multiple of 4 or 8 bytes. This has the added benefit that an allocated block will be properly aligned on machine word boundaries. CPUs like to access multi-byte entities at aligned locations, eg the address of a 16 bit short int should be divisible by 2, the address of a 32 bit int should be divisible by 4, etc. This is mandatory on some architectures, and desirable on most others.

Fortunately, C handles all of that stuff for you, so you don't need to worry about it; if you ever decide to get into assembler programming you'll have to look after such things yourself.


tl;dr: For a buffer of 11 bytes, use a fixed length array. The alternative wastes more than it saves.
User avatar
PM 2Ring
 
Posts: 3233
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

Re: Unsigned int to ascii in C

Postby EvanED » Thu Dec 01, 2011 2:12 pm UTC

PM 2Ring wrote:Firstly, there's a header added to your memory block to store its size and to link it into a list. free() needs to know how big a memory block is to deallocate it properly, and any memory that you allocate but don't explicitly free gets freed automatically at program termination. The linked list makes it possible for the "system" to find all of your un-freed blocks.

free() needs to have that extra size, but the OS doesn't. It only tracks process memory use at the level of pages (4K chunks). When your process exits, it knows it can give the whole page to a different one. It doesn't look into the memory that your process was using.

This is why you can corrupt your heap and it will cause no end of problems for your own program, but the rest of the system will continue operating fine. Or why your program can substitute in other alternative malloc implementations, garbage collection, etc.
EvanED
 
Posts: 4113
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI

Re: Unsigned int to ascii in C

Postby Yakk » Thu Dec 01, 2011 2:39 pm UTC

That is a non-portable assumption!
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
User avatar
Yakk
Poster with most posts but no title.
 
Posts: 10377
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Unsigned int to ascii in C

Postby PM 2Ring » Fri Dec 02, 2011 7:06 am UTC

Notice that I put the word "system" in quotes. I wasn't (necessarily) talking about the OS, I was talking about the invisible stuff supplied by the compiler / linker (generally in a _main() function) that handles such things as opening stdin/stdout/stderr, and the automatic freeing of allocated memory and closing of open files upon normal program termination. I was being intentionally ambiguous, since I didn't want to go into the murky details of where & how all that stuff happens. The OPer is a new C programmer and I didn't want to make things too confusing for him, and I was already a bit uncomfortable about the low-level memory related stuff that I'd mentioned in that post.

Of course, it would be possible to create an OS that automatically provides such services for all processes, rather than having them supplied by the compiler / linker, just as it's possible to create an OS that provides the standard C library as DLLs. And of course, at the other end of the spectrum it's quite possible to have a C environment that only provides very restricted I/O support, eg an embedded system with rudimentary memory mapped I/O and no support for things like printf() or scanf().
User avatar
PM 2Ring
 
Posts: 3233
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

Re: Unsigned int to ascii in C

Postby jareds » Fri Dec 02, 2011 10:31 am UTC

PM 2Ring wrote:Notice that I put the word "system" in quotes. I wasn't (necessarily) talking about the OS, I was talking about the invisible stuff supplied by the compiler / linker (generally in a _main() function) that handles such things as opening stdin/stdout/stderr, and the automatic freeing of allocated memory and closing of open files upon normal program termination.

EvanED is still right. Neither the OS nor the C run-time library use a malloc block list to free allocated memory at program termination, and the C run-time does not in fact free memory at program termination1. With any modern OS, the heap is freed in pages by the OS as he described. With a pre-modern desktop OS that only let you run one program at a time, I very strongly assume that the OS simply assumed that all non-OS memory was free once the program exited. Even with embedded systems, you typically either have virtual memory management, in which case it behaves like a desktop OS in this respect, or a single main function that never returns, on pain of hanging the device, and the C run-time does not free memory at termination in any event. There are however systems where you can have multiple heaps even though you only have one address space, but in such cases freeing an entire heap does not depend on the malloc block list within that heap.

1. I am not categorically saying that the system you describe never existed in the history of the world.
jareds
 
Posts: 405
Joined: Wed Jan 03, 2007 3:56 pm UTC

Re: Unsigned int to ascii in C

Postby EvanED » Fri Dec 02, 2011 3:27 pm UTC

TLDR version: Your program is not going to walk the heap and free blocks when it exits. There is one primary exception to this rule: a leak detector, which walks the heap to list any blocks that are still allocated. (Even then I doubt they actually free them.)

It's better to say "don't worry about memory your program allocates wasting space after it exits, the OS cleans it up" then to talk about your program walking the list of allocated blocks when it exits and freeing each of them. The former is both a simpler explanation and actually correct (at least to the extent you can say anything regarding such behavior in a C program).

PM 2Ring wrote:Notice that I put the word "system" in quotes. I wasn't (necessarily) talking about the OS, I was talking about the invisible stuff supplied by the compiler / linker (generally in a _main() function) that handles such things as opening stdin/stdout/stderr, and the automatic freeing of allocated memory and closing of open files upon normal program termination.

Again, these things are not generally handled by your program. (Also, ) Why? Because the OS will take care of it. Especially in the case of memory, why have your program do a bunch of extra work for no reason? How your program runs your heap is up to your program (do you even have a heap?) and the OS is going to do exactly the same thing no matter whether your program walks over all malloc()'d blocks and frees them or not -- because it doesn't care what the contents of your process's pages are. So why would your program do a bunch of extra work it doesn't need to?

You can see this effect in action.

Code: Select all
#include <stdlib.h>

#define NUM_BLOCKS 10000000
int * blocks[NUM_BLOCKS];

int main()
{
    int i;
    for(i=0; i<NUM_BLOCKS; ++i) {
        blocks[i] = malloc(10);
    }
    for(i=0; i<NUM_BLOCKS; ++i) {
        free(blocks[i]);
    }
    return 0;
}


If I run this on my system (amd64 Linux, compiled with GCC 4.3.2 with gcc -O2 leak.c), it takes about .63 seconds to execute:
Code: Select all
~/delete : time ./a.out 
./a.out  0.48s user 0.15s system 100% cpu 0.631 total
~/delete : time ./a.out
./a.out  0.49s user 0.14s system 99% cpu 0.630 total
~/delete : time ./a.out
./a.out  0.49s user 0.14s system 99% cpu 0.628 total


If I comment out just the call to free, it takes more like .46 seconds to execute:
Code: Select all
~/delete : time ./a.out 
./a.out  0.29s user 0.17s system 99% cpu 0.459 total
~/delete : time ./a.out
./a.out  0.33s user 0.13s system 99% cpu 0.458 total
~/delete : time ./a.out
./a.out  0.31s user 0.18s system 100% cpu 0.491 total


What can we conclude from this? If the runtime is walking the heap, it is doing it in a far more efficient way then what you have access to as a programmer (i.e. free). It's not completely impossible (e.g. they could provide a different version of free that doesn't do coalescing), but when you put all this information together, Occam's Razor says that the better explanation is that it's not doing it at all.

Edit:

Actually we can make this more precise even. Add code to measure timing of malloc and free. I put a call to gettimeofday before and after each loop, then printed out the times for those loops. (As a side note, every time I read the manpage for gettimeofday I feel like the next manpage I read is going to just be the lyrics of Never Gonna Give You Up. There are two parameters, but you are required to pass NULL for the second? It returns a value which is guaranteed to be 0? Whose idea of "good API design" is this?)

Now we get this (just one run of each since the times are consistent among 3; this is the median):

With free:
Code: Select all
malloc took 0 seconds and 428884 microseconds
free took 0 seconds and 170775 microseconds
./a.out  0.47s user 0.15s system 99% cpu 0.622 total

In other words, more than 0.600 sec took place within main() proper, which means about 0.022 seconds outside of it.

Code: Select all
malloc took 0 seconds and 431134 microseconds
free took 0 seconds and 0 microseconds
./a.out  0.31s user 0.14s system 100% cpu 0.454 total

This leaves 0.023 seconds outside of my main(). That's 0.001 seconds more than the run with free().

In other words, if the runtime is walking over the heap explicitly freeing all still-allocated blocks, it's doing it two orders of magnitude faster than my free loop. Yeah right.

(BTW, I also tried counting down from NUM_BLOCKS-1 to 0, freeing in that order. Came out exactly the same.)
EvanED
 
Posts: 4113
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI

Re: Unsigned int to ascii in C

Postby PM 2Ring » Sat Dec 03, 2011 1:01 am UTC

Thanks for the correction, guys.

In my defense, the malloc()/free() mechanism I described above is basically what happened on the Amiga, where I did most of my early C programming, and it's also very similar to how it's handled in P.J. Plauger's The Standard C Library.

FWIW, I've never done any programming in DOS or Windows (apart from a little JavaScript). These days I mostly use Mepis Linux; my C compiler is gcc version 4.4.5, but I must admit I haven't studied its man page intensively.
User avatar
PM 2Ring
 
Posts: 3233
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

Re: Unsigned int to ascii in C

Postby Little Richie » Thu Feb 09, 2012 12:18 am UTC

Thank you guys for all of your help so far!
Learning to code has been a really low duty-cycle task for me, but I had some time this week and worked through my problems.

Here is my revised code that now works:
Code: Select all
int main(void)
{

    unsigned int input =0xFFFFFFFF;    // used for testing inputs
    int lastDigit = 0;
    int i =0;
    int swap = 0;
    int pos =  0;
    char temp;
    char c[10];                                    // I need a way to not know how large the array needs to be

    do
    {
        lastDigit = input % 10;                     //extract the last digit of the input
        c[i++] = lastDigit + '0';                   // Store in ascii equivalent to char array
        input /= 10;                                // remove the last digit from original input


    }while(input);

    c[i] = 0;                                        //write null to end string

    swap = (i-1) - pos;                              //set swap to the last place that isn't the null

    while(swap > pos)
    {
        swap = (i-1) - pos;
        temp =c[swap];                               //move last to temp
        c[swap] = c[pos];                            // set first to last
        c[pos++] = temp;                               // set last(temp) to first, advance pos

    }

        printf("Output: %s\n", c);
}


My mentor told me there was a way to do this without the reversing loop. I know I will need to use a pointer variable to do it, I'm just not sure exactly how. Could someone point me in the right direction?
Thanks!
With man gone, will there be hope for gorilla?
Check out my blog, my mission to save the world.
User avatar
Little Richie
 
Posts: 127
Joined: Tue Feb 05, 2008 3:02 am UTC
Location: Orlando, Florida

Re: Unsigned int to ascii in C

Postby PM 2Ring » Thu Feb 09, 2012 4:07 am UTC

Little Richie wrote:My mentor told me there was a way to do this without the reversing loop. I know I will need to use a pointer variable to do it, I'm just not sure exactly how. Could someone point me in the right direction?
Thanks!


Well, it can be done without a pointer, but here's one way to do it with a pointer. This program gets the data to process from the DATA macro. A proper program would get it from the command line, or stdin, etc. Your C compiler will allow you to supply macro values on its command line; with gcc you can do this:

gcc -o intstrdemo1 -D DATA=0x1234 intstrdemo1.c

Code: Select all
#include <stdio.h>

#ifndef DATA
#define DATA 0x7B
#endif

int main(void)
{
    char s[11], *p = s + 10;
    unsigned int i = DATA;
   
    *p-- = '\0';
   
    do
    {
        *p-- = i % 10 + '0';
        i /= 10;
    } while (i);

    printf("%s\n", ++p);

    return 0;
}


I have a couple of suggestions.

It's a Good Idea to include headers for any library functions that your program uses. You're using printf(), so you should include <stdio.h>, otherwise the compiler will have to guess what the argument types of printf() are. Luckily, automatic promotion makes everything work properly in this instance, but you shouldn't rely on that.

You've declared main() to return an int, but you haven't provided an explicit return statement. This can do weird things in some environments, although your compiler may automagically add a return 0; for you.
User avatar
PM 2Ring
 
Posts: 3233
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

Re: Unsigned int to ascii in C

Postby Carnildo » Thu Feb 09, 2012 5:44 am UTC

EvanED wrote:(As a side note, every time I read the manpage for gettimeofday I feel like the next manpage I read is going to just be the lyrics of Never Gonna Give You Up. There are two parameters, but you are required to pass NULL for the second? It returns a value which is guaranteed to be 0? Whose idea of "good API design" is this?)

Sounds like you need a better man page. Mine explains why you should pass NULL (it's obsolete functionality that has never been supported on LInux), and that it returns -1 on failure; looking at the error codes it can return, the implementation on your system may not have any failure modes.
Carnildo
 
Posts: 2022
Joined: Fri Jul 18, 2008 8:43 am UTC

Re: Unsigned int to ascii in C

Postby Little Richie » Thu Feb 09, 2012 6:32 am UTC

That code makes a lot of sense, we are doing the same math, just writing it to memory in the reverse order.

My only question is why the printf statement needs to be "++p" and not just p.
That question stems from my limited knowledge of pointers.
I have read a few articles on pointers and none have helped.

Does printf("p:%s\n", p); print everything in front of and including position p in memory (to the end of the array)
Is the problem in just printing p, that we are also seeing whatever is in the place before the information we care about?

Is there a way to initialize the memory so we do not have this problem?
With man gone, will there be hope for gorilla?
Check out my blog, my mission to save the world.
User avatar
Little Richie
 
Posts: 127
Joined: Tue Feb 05, 2008 3:02 am UTC
Location: Orlando, Florida

Re: Unsigned int to ascii in C

Postby darkone238 » Thu Feb 09, 2012 6:38 am UTC

Carnildo wrote:
EvanED wrote:(As a side note, every time I read the manpage for gettimeofday I feel like the next manpage I read is going to just be the lyrics of Never Gonna Give You Up. There are two parameters, but you are required to pass NULL for the second? It returns a value which is guaranteed to be 0? Whose idea of "good API design" is this?)

Sounds like you need a better man page. Mine explains why you should pass NULL (it's obsolete functionality that has never been supported on LInux), and that it returns -1 on failure; looking at the error codes it can return, the implementation on your system may not have any failure modes.


http://pubs.opengroup.org/onlinepubs/009604599/functions/gettimeofday.html

Maybe the Evan was looking at this :)
User avatar
darkone238
 
Posts: 110
Joined: Thu Feb 09, 2012 6:37 am UTC

Re: Unsigned int to ascii in C

Postby PM 2Ring » Thu Feb 09, 2012 7:48 am UTC

Little Richie wrote:That code makes a lot of sense, we are doing the same math, just writing it to memory in the reverse order.


Exactly.

My only question is why the printf statement needs to be "++p" and not just p.

The logic I used writes a byte to s and decrements the pointer so it points to the byte in front of (ie with a lower memory address) the byte just written. So at the end of the loop, p is pointing to the byte before the start of the string of digits we've written, so we need to increment it by one to make it actually point to the start of the string.

This process may look a bit dodgy. What happens if we're converting a large number that totally fills s? At the end of the loop, p points to a memory address that's outside of s. Fortunately, that's ok - to permit algorithms like this one, the C standard says that pointer arithmetic is allowed to reference the location just before or just after an array. But it's definitely not wise to dereference a pointer when it points to a location that you don't legitimately own.

That question stems from my limited knowledge of pointers.
I have read a few articles on pointers and none have helped.
FWIW, I only used a pointer in this example because you mentioned it. Don't worry, pointers can be confusing at first, but you'll eventually get used to them with practice & experimentation. And these days, you can safely experiment with pointers without too much worry - back in the bad old days, a pointer blunder could easily crash your machine.

Does printf("p:%s\n", p); print everything in front of and including position p in memory (to the end of the array)
Is the problem in just printing p, that we are also seeing whatever is in the place before the information we care about?

It prints all the bytes from position p upto but not including the first \0 byte it encounters, as that's the C convention for delimiting a string. If instead we used printf("%s\n", s); then we'd get garbage bytes because we didn't initialize s, and in C local variables are uninitialized. If the garbage bytes happened to include a \0 byte, then the output would be terminated before we got to our actual digits.

You can easily test this for yourself - modify the source of the program, and when you run it pipe the output into a hex dumper. On *nix systems you can use hd or od; I don't know what the Windows options are.

Is there a way to initialize the memory so we do not have this problem?
Well we could do that, but that's not really a great solution here. We could initialize s to contain spaces, and then if we used printf("%s\n", s); the output string would be right justified with leading spaces, but it's generally better to do that sort of thing with the proper printf() format string.

Some people like to initialize arrays before use; I prefer to make sure that my pointer arithmetic is correct. :)
User avatar
PM 2Ring
 
Posts: 3233
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

Re: Unsigned int to ascii in C

Postby Little Richie » Thu Feb 09, 2012 8:46 am UTC

Thank you so much, that clears up a lot of my problems about pointers.
My one remaining is the distinction between p, *p and s[] and how they fit together
From what I understand:

p is an int representing the char array starting location in memory through to the end of the array

*p is an int that passes to a char at the specific memory address represented by the int

s[] is the char array, [x] bytes long
Is this correct?

What exactly is happening here in this line relative to pointer land? : char s[11], *p = s + 10;
I'm sure this could be split up into two lines:
char s[11];
char *p = c + 10;
With man gone, will there be hope for gorilla?
Check out my blog, my mission to save the world.
User avatar
Little Richie
 
Posts: 127
Joined: Tue Feb 05, 2008 3:02 am UTC
Location: Orlando, Florida

Re: Unsigned int to ascii in C

Postby PM 2Ring » Thu Feb 09, 2012 11:14 am UTC

Little Richie wrote:Thank you so much, that clears up a lot of my problems about pointers.

No worries.

My one remaining is the distinction between p, *p and s[] and how they fit together
From what I understand:

p is an int representing the char array starting location in memory through to the end of the array

*p is an int that passes to a char at the specific memory address represented by the int

s[] is the char array, [x] bytes long
Is this correct?

Pretty much. As far as the CPU is concerned, a pointer is an integer, but as far as C is concerned they are separate types, although various forms of arithmetic involving both pointers and integers are permitted.
p is a pointer containing a memory address, the asterisk operator dereferences the pointer, so *p effectively contains whatever is at the memory address pointed to by p. I like to think of *p as the target of p.

What exactly is happening here in this line relative to pointer land? : char s[11], *p = s + 10;
I'm sure this could be split up into two lines:
char s[11];
char *p = s + 10;

Correct. I admit that this kind of initialization can be slightly confusing, but it's so common that it's a good idea to get used to this idiom. It can also be written as
char s[11];
char *p;
p = s + 10;
User avatar
PM 2Ring
 
Posts: 3233
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

Re: Unsigned int to ascii in C

Postby Yakk » Thu Feb 09, 2012 2:16 pm UTC

By the way, don't use ++p type constructions in the middle of expressions. And don't advise new people to start using them.

First, because they make expressions more complicated without making them perform any better.

Second, because there are quirks to pre/post increment that you don't understand as a new to C programmer that kick in when you use them in the middle of expressions. Learning those quirks while learning how to program is exceedingly dumb. If you personally know all of the quirks to them, then why in the hell are you sabotaging someone's learning of the language with traps? And if you don't think there are traps, you don't know enough, so don't teach new programmers to use them in the middle of expressions.

tl;dr: don't use pre/post increment (++p, and p++) in the middle of other expressions. It just isn't worth it.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
User avatar
Yakk
Poster with most posts but no title.
 
Posts: 10377
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Unsigned int to ascii in C

Postby EvanED » Thu Feb 09, 2012 7:14 pm UTC

darkone238 wrote:
Carnildo wrote:
EvanED wrote:(As a side note, every time I read the manpage for gettimeofday I feel like the next manpage I read is going to just be the lyrics of Never Gonna Give You Up. There are two parameters, but you are required to pass NULL for the second? It returns a value which is guaranteed to be 0? Whose idea of "good API design" is this?)

Sounds like you need a better man page. Mine explains why you should pass NULL (it's obsolete functionality that has never been supported on LInux), and that it returns -1 on failure; looking at the error codes it can return, the implementation on your system may not have any failure modes.


http://pubs.opengroup.org/onlinepubs/00 ... ofday.html

Maybe the Evan was looking at this :)

Yep. More discussion here to not hijack the thread more.

Yakk wrote:By the way, don't use ++p type constructions in the middle of expressions. And don't advise new people to start using them.

First, because they make expressions more complicated without making them perform any better.

Second, because there are quirks to pre/post increment that you don't understand as a new to C programmer that kick in when you use them in the middle of expressions. Learning those quirks while learning how to program is exceedingly dumb. If you personally know all of the quirks to them, then why in the hell are you sabotaging someone's learning of the language with traps? And if you don't think there are traps, you don't know enough, so don't teach new programmers to use them in the middle of expressions.

tl;dr: don't use pre/post increment (++p, and p++) in the middle of other expressions. It just isn't worth it.

I agree with basically everything Yakk says. The one place where I actually like seeing p++ when it is not by itself is in something like:
Code: Select all
static int next_count = 1;
int this_count = next_count++;

In most other contexts it just makes me mad.
EvanED
 
Posts: 4113
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI

Re: Unsigned int to ascii in C

Postby PM 2Ring » Thu Feb 09, 2012 11:18 pm UTC

Yakk wrote:By the way, don't use ++p type constructions in the middle of expressions. And don't advise new people to start using them.

Rightio.

First, because they make expressions more complicated without making them perform any better.

True.

Second, because there are quirks to pre/post increment that you don't understand as a new to C programmer that kick in when you use them in the middle of expressions. Learning those quirks while learning how to program is exceedingly dumb.

Good point.

If you personally know all of the quirks to them, then why in the hell are you sabotaging someone's learning of the language with traps? And if you don't think there are traps, you don't know enough, so don't teach new programmers to use them in the middle of expressions.

I wasn't trying to sabotage his learning; this was a just a 5 minute example. I agree I should've used simpler code; OTOH, it is homework & I didn't want to make it too easy. :twisted:

I admit that using pre/post increment in the middle of expressions or in the middle of an argument list can do unexpected things, although all my uses in this example are benign. But I'll try to use more straight-forward constructions in future examples.

Ok?
User avatar
PM 2Ring
 
Posts: 3233
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

Re: Unsigned int to ascii in C

Postby Little Richie » Fri Feb 10, 2012 1:25 am UTC

PM 2Ring wrote:
What exactly is happening here in this line relative to pointer land? : char s[11], *p = s + 10;
I'm sure this could be split up into two lines:
char s[11];
char *p = s + 10;

Correct. I admit that this kind of initialization can be slightly confusing, but it's so common that it's a good idea to get used to this idiom. It can also be written as
char s[11];
char *p;
p = s + 10;

If this is also the same, then I understand:
char s[11];
char *p;
p = s;
p = 10;

Yakk wrote:tl;dr: don't use pre/post increment (++p, and p++) in the middle of other expressions. It just isn't worth it.

Actually, my mentor encourages making the code more efficient. I learned about " pre/post increment" in my first assignment, a bit counter. Personally, I'd also rather see it on one line than written in two.

PM 2Ring wrote:Well, it can be done without a pointer [. . .]

Would you just use an indexed array and write to s[x], instead of the pointer?
What are the advantages / disadvantages of pointers over indexes?
With man gone, will there be hope for gorilla?
Check out my blog, my mission to save the world.
User avatar
Little Richie
 
Posts: 127
Joined: Tue Feb 05, 2008 3:02 am UTC
Location: Orlando, Florida

Re: Unsigned int to ascii in C

Postby Yakk » Fri Feb 10, 2012 1:36 am UTC

Lines of code are not a useful measure of efficiency.

Doing something in fewer lines of code doesn't really do much. If clean, it can reduce the cognitive load required to figure out what is going on in a line of code. However, the design of pre and post increment in the context of C is iffy. There are serious quirks (sequence points etc) you do not need to learn.

In general, debugging code is harder than writing it. If you write code that is as clever as you can, you won't he smart enough to debug it.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
User avatar
Yakk
Poster with most posts but no title.
 
Posts: 10377
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Next

Return to Coding

Who is online

Users browsing this forum: WarDaft and 2 guests