Imagine running across a block of C code that is meant to create a comma separated list of items like this:
2024/10/18,12:30:06,100,0.00,0,0,0,902.0,902.0,928.0,31.75,0,0,100 ...
2024/10/18,12:30:07,100,0.00,0,0,0,902.0,902.0,928.0,31.75,0,0,100 ...
2024/10/18,12:30:08,100,0.00,0,0,0,902.0,902.0,928.0,31.75,0,0,100 ...
2024/10/18,12:30:09,100,0.00,0,0,0,902.0,902.0,928.0,31.75,0,0,100 ...
And the code that does it was modular, so new items could be inserted anywhere, easily. This is quite flexible:
snprintf (buffer, BUFFER_LENGTH, "%u", value1);
strcat (outputLineBuffer, buffer);
strcat (outputLineBuffer, ",");
snprintf (buffer, BUFFER_LENGTH, "%u", value2);
strcat (outputLineBuffer, buffer);
strcat (outputLineBuffer, ",");
snprintf (buffer, BUFFER_LENGTH, "%.1f", value3);
strcat (outputLineBuffer, buffer);
strcat (outputLineBuffer, ",");
snprintf (buffer, BUFFER_LENGTH, "%.1f", value4);
strcat (outputLineBuffer, buffer);
strcat (outputLineBuffer, ",");
snprintf is used to format the variable into a temporary buffer, then strcat is used to append that temporary buffer to the end of the line output buffer that will be written to the file. Then strcat is used again to append a comma… and so on.
Let’s ignore the use of the “unsafe” strcat which can trash past the end of a buffer is the NIL (“\0”) zero byte is not found. We’ll just say strncat exists for a reason and can prevent buffer overruns crashing a system.
Many C programmers never think about what goes on “behind the scenes” when a function is called. It just does what it does. Only if you are on a memory constrained system may you care about how large the code is, and only on a slow system may you care about how slow the code is. As an embedded C programmer, I care about both since my systems are often slow and memory constrained.
strcat does what?
The C string functions rely on finding a zero byte at the end of the string. strlen, for example, starts at the beginning of the string then counts until if finds a 0, and returns that as the size:
size_t stringLength = strlen (someString);
And strcat would do something similar, starting at the address of the string passed in, then moving forward until a zero is found, then copying the new string bytes there up until it finds a zero byte at the end of the string to be copied. (Or, in the case of strncat, it might stop before the zero if a max length is reached.)
I have previously written about these string functions, including showing implementations of “safe” functions that are missing from the standard C libraries. See my earlier article series about these C string functions. And this one.
But what does strcat look like? I had assumed it might be implemented like this:
char *myStrcat (char *dest, const char *src)
{
// Scan forward to find the 0 at the end of the dest string.
while (*dest != 0)
{
dest++;
}
// Copy src string to the end.
do
{
*dest = *src;
dest++;
src++;
} while (*src != 0);
return dest;
}
That is a very simple way to do it.
But why re-invent the wheel? I looked to see what GCC does, and their implementation of strcat makes use of strlen and strcpy:
/* Append SRC on the end of DEST. */
char *
STRCAT (char *dest, const char *src)
{
strcpy (dest + strlen (dest), src);
return dest;
}
When you use strcat on GCC, it does the following:
- Call strlen() to count all the characters in the destination string up to the 0.
- Call strcpy() to copy the source string to the destination string address PLUS the length calculated in step 1.
- …and strcpy() is doing it’s own thing where it copies characters until it finds the 0 at the end of the source string.
Reusing code is efficient. If I were to write a strcat that worked like GCC, it would be different than my quick-and-dirty implementation above.
This is slow, isn’t it?
In the code I was looking at…
snprintf (buffer, BUFFER_LENGTH, "%u", value1);
strcat (outputLineBuffer, buffer);
strcat (outputLineBuffer, ",");
…there is alot going on. First snprint does alot of work to convert the variable in to string characters. Next, strcat is calling strlen on the outputLineBuffer, then calling strcpy. Finally, strcat calls strlen on the outputLineBuffer again, then calls strcpy to copy over the comma character.
That is alot of counting from the start of the destination string to the end, and each step along the way is more and more work since there are more characters to copy. Suppose you were going to write out ten five-digit numbers:
11111,22222,33333,44444,55555
The first number is quick because nothing is in the destinations string yet so strcat has nothing to count. “11111” is copied. Then, there is a scan of five characters to get to the end, then the comma is copied.
For the second number, strcat has to scan past SIX characters (“11111,”) and then the process continues.
The the third number has to scan past TWELVE (“11111,22222,” characters.
Each entry gets progressively slower and slower as the string gets longer and longer.
Can we make it faster?
If things were set in stone, you could do this all with one snprint like this:
snprintf ("%u,%u,%.1f,%.1f\n", value1, value2, value3, value4);
Since printf is being used to format all the values in to a buffer, then doing the whole string with one call to snprintf may be the smallest and fastest way to do this.
But if you are dealing with something with dozens of values, when you go in later to add one in the middle, there is great room for error if you get off by a comma or a variable in the parameter list somewhere.
I suspect this is why the code I am seeing was written the way it was. It makes adding something in the middle as easy as adding three new lines:
snprintf (buffer, BUFFER_LENGTH, "%u", newValue);
strcat (outputLineBuffer, buffer);
strcat (outputLineBuffer, ",");
Had fifty parameters been inside some long printf, there is a much greater chance of error when updating the code later to add new fields. The “Clean Code” philosophy says we spend more time maintaining and updating and fixing code than we do writing it, so writing it “simple and easy to understand” initially can be a huge time savings. (Spend a bit more time up front, save much time later.)
So since I want to leave it as-is, this is my suggestion which will cut the string copies in half: just put the comma in the printf:
snprintf (buffer, BUFFER_LENGTH, "%u,", value1);
strcat (outputLineBuffer, buffer);
snprintf (buffer, BUFFER_LENGTH, "%u,", value2);
strcat (outputLineBuffer, buffer);
snprintf (buffer, BUFFER_LENGTH, "%.1f,", value3);
strcat (outputLineBuffer, buffer);
snprintf (buffer, BUFFER_LENGTH, "%.1f,", value4);
strcat (outputLineBuffer, buffer);
And that is a very simple way to reduce the times the computer has to spend starting at the front of the string and counting every character forward until a 0 is found. For fifty parameters, instead of doing that scan 100 times, now we only do it 50.
And that is a nice savings of CPU time, and also saves some code space by eliminating all the extra calls to strcat.
You know better, don’t you?
But I bet some of you have an even better and/or simpler way to do this.
Comment away…
Yup, that’s what in the complexity biz they call O(n^2). Take advantage of *printf returning the number of bytes output and use sprintf() instead of strcat().
Ahh, yes. The old Schlemiel the Painter algorithm.
Also, strncat() doesn’t limit things they way you might expect. Read the documentation before using it.
Let’s see if I can guess — If I recall, strncat() makes sure it doesn’t copy more than n bytes, but if it doesn’t find a NIL at the end, it would keep copying up to that n:
strncat (buffer, 80, “add this to the end”);
If this is the first copy, and buffer is 80 bytes in size, that’s good. But if you do this:
strncat (buffer, 80, “add this to the end”);
strncat (buffer, 80, “then add this after it”);
…that is not useful, since the second one it is copying up to 80 starting at wherever it is in the buffer (NIL), so that could cause it to have a buffer overrun.
Is that what you mean? I wrote about this when I built some “safer” versions of the various calls. Like, there is no strnlen() is there? It just walks through memory until it finds a 0. Probably some other examples.
First off, I would write the following function:
void append(char **pdest,size_t *max,char *src,int len){
assert(pdest != NULL);
assert(*pdest != NULL);
assert(max != NULL);
assert(src != NULL);
assert(len >= 0);
if (len < *max)
{
memcpy(*pdest,src,len);
(*pdest) += len;
(*max) -= len;
**pdest = '\0'; /* NUL terminate string */
}
}
This is pretty much a glorified wrapper around
memcpy(), which should be faster than usingsnprintf()to copy a string. The calls toassert()is something I do to ensure it’s called correctly. Then it’s a simple matter of:char bufferp[SOMESIZE];char outputLineBuffer[SOMESIZE];
char *p = outputLineBuffer;
size_t max = sizeof(outputLineBuffer);
append(&p,&max,buffer,snprintf(buffer,BUFLEN,"%u,",value1));
append(&p,&max,buffer,snprintf(buffer,BUFLEN,"%u,",value2));
append(&p,&max,buffer,snprintf(buffer,BUFLEN,"%.1f,",value3));
append(&p,&max,buffer,snprintf(buffer,BUFLEN,"%.1f,",value4));
If you really want, you could do:
len = snprintf(buffer,BUFLEN,"%u,",value1);
append(&p,&max,buuffer,len);
But this requires a named variable.
I thought about it for a bit, and found a way to avoid the copy entirely, and making it nicer looking:
#include <stdarg.h>void append(char **pdest,size_t *max,char *fmt,...)
{
va_list ap;
int len;
assert(pdest != NULL);
assert(*pdest != NULL);
assert(max != NULL);
assert(fmt != NULL);
va_start(ap,fmt);
len = vsnprintf(*pdest,*max,fmt,ap);
va_end(ap);
(*pdest) += len;
(*max) -= len;
}
char outputLineBuffer[SOMESIZE];
char *p = outputLineBuffer;
size_t max = sizeof(outputLineBuffer);
append(&p,&max,"%u,",value1);
append(&p,&max,"%u,",value2);
append(&p,&max,"%.1f,",value3);
append(&p,&max,"%.1f,",value4);
For some reason, I get the feeling that many people shy away from functions with variable arguments.
That looks really cool. The closets thing I’ve done like that is some stuff to get/put variables of different sizes in to a buffer, and I would pass in the address like that so it could be incremented after each call.
Now, assert() is something I have never used. Most of my work is with “C like” embedded compilers. Subsets of printf, missing lots of library calls, etc.
Ah, so assert() aborts the program?
a.out: main.c:63: append: Assertion `pdest != NULL’ failed.
There is an errchk() macro used in LabWindows/CVI C code that does that, so I think I understand. I suppose error checking parameters would still be needed to ensure a program can keep running if something bad is passed in.
Reading up on this, I’ve never seen/used raise(SIGABRT) and such, either. I learned C during the K&R days, and keep finding stuff introduced over the years I have never seen.
For anyone who wants to check it out — this append() routine online:
https://onlinegdb.com/ubLMu2wI0
I really like it. Nicely done.
assert()is a macro where if the given expression is false, it prints a diagnostic message and callsabort(). If you defineNDEBUGthough,assert()will not generate any code. Useful in debugging—add anassert()for conditions that must be true at that point in the program. I do them at the start of each function to check that I’m passing in valid data, and sometimes (if I’m doing some tricky pointer manipulations) in the middle of functions as well.It’s sad that so many embedded C compilers are so bad.
The printf code from the full ANSI C compiler that OS-9/68000 had was larger than the OS kernel (which was in assembly, so no surprise). I can see why Arduino, etc. have to get rid of so much to make things fit.
Sorry if I missed something in the previous comments, but:
Have a global variable keep track of where the end of the output buffer currently sits. Use that to point where snprintf prints to, and use the return value from snprintf to add to this pointer. That way you don’t have to find the end of the current buffer and also don’t have to do any extra copying.
How is this data outputted? If it’s sent over for example a serial line, another option would be to create the data on the fly as the output buffer empties out. Might not be a benefit in reality as you have to switch to the context of outputting these strings whenever the buffer runs low, so would mostly be useful for the simplest outputs like predefined strings with say two/four digit hex values and whatnot. If you for example have a 16550 UART with 16 bytes of buffer, you could vary the amount of data you fill the buffer, so you fill it to the brim as long as you only have to copy predefined strings, while when you need to convert a number to text (especially decimal rather than hex) you run the conversion when the buffer has enough room for the result of the conversation (and if there is more room left add any additional simple predefined string data). This might run a bit slower in some cases as creating the output data might be slower than the rate the UART can send data, but this surely must be the way to preserve as much memory as possible.
If you send data over Ethernet then use (at least) two buffers that contain an ethernet packet each, and have the TCP/IP stack (or whichever protocol you use) fill in it’s things around the data block when the data block is full. This way the network stack doesn’t need to copy data from your buffer to the ethernet interface buffer. A downside though might be that the ethernet interface buffer might be slower to access (and in some cases it might even be I/O mapped). If it’s memory mapped and has a reasonable bus speed this seems like a viable option.
To some extent I agree with the philosophy to write code that’s easy to read, but if you produce millions of devices and use fewer/cheaper chips, it might be worth the cost to write “harder to read” code.
Also in both the UART and Ethernet specific examples you would have some sort of table or list that tells which data you should send, I.E. a table or list with pointers to the values you want to output, and what data type the values are.
I would also consider doing conversions on the receiving end. I.E. output epoch time as hex rather than human readable date/time.
Side track: Why slash for dates? ISO 8601 specifies the minus/dash sign :)
This is a Windows program, so the mindset seems to be “unlimited processing power, unlimited storage, unlimited memory” when I see code like this.
Yeah tracking buffer position and just using snprintf() is the route I think I would take. Dozens of strcats in a row seems unnecessary.
US connection is typically mm/dd/yyyy and hh:mm:ss, but I got used to yyyy/mm/dd when I learned OS-9. I thought that was weird and backwards but later learned you cannot sort by date name unless you put the year first and I’ve used that ever since.
Excel defaults “short date” to be mm/dd/yyyy and these files get opened in Excel so maybe that is why?
Actually now I wonder… does Excel defaults to other formats based on the region it is in???
I’m not a fan of global variables as it makes it harder to reason about the code due to “spooky action at a distance” (any function can change any global, thus changing the behavior of the program at any time). Also, what if you forget to update the pointer to the buffer? Then you get weird output bugs.
The 6809 assembly I used to use was nothing but global variables, and thus, it was not easy to change. I ended up writing my 6809 assembler without any global variables. Yes, there is a “god object” that gets passed around, but it’s explicit (the only places it can change are those function that have it as a parameter, which is easy to check), but at the same time, on an N-core system, I can assemble N files at the same time in the program without issue—I don’t even need to think about this.
I have maintained an awful lot (or a lot of awful) globals in several of my day jobs :( As I touch code, I’ve been trying to rename them to start with “g_” (old coding standard from a previous job) so they can at least be visually identified as globals when looking at a routine. Found one issue where there was a global “index” variable, and local “index” variables, and … yeah.
The “god object” sounds like the “context” structures I run in to. In a previous job, we have lots of thing that used a “context” which was an anonymous pointer to “something”. Those would be passed around to functions, I guess similar to what a “FILE *” is in C stdio. In later stuff, I’ve seen a large global structure full of runtime variables, and functions just go an access them globally.
Perhaps a simple first step would be to make that structure local to the main(), and pass it around, so no one could touch it without being called with that structure.