(Warning: some non-FP content!)
So yesterday I had a job interview for a developer position and I got the chance to put my money where my mouth is, so to speak, about my C and C++ programming skills. I was asked to write 3 functions given specifications including their prototypes, and to review a piece of C++ sample code. The interviewers left me alone with some paper for fifteen minutes or so.
There were four tasks. I scrambled around at the first one, started down a blind alley, started to get nervous, realized I was getting nervous, and decided to move on to the next questions and come back to the first question if I could. So I'll reveal that one last.
The second task was to write a "population count" -- to count the one bits in an unsigned char. This is a common operation in real-world code that operates on packed data structures such as tries. I chose a very simple lookup-table approach, with a table to look up values nybble-wise. Easy-peasy. The function itself then becomes a one-liner. "Full marks," as they say in some countries.
The third task was to write a function that tests whether the CPU it is running on is big-endian, or little-endian. If you don't know what that means, I'm not going to explain it in great detail here, but it refers to the way that the individual bytes of multi-byte values are laid out in memory. You can write quite a bit of code without running into endian problems, but it becomes an issue if you need to exchange data over a network or across a bus between processors that store their data differently. Fortunately I have written quite a few drivers, so this one was also easy.
The last task was to find errors and questionable practices. There were a lot of them -- I marked up my page with several "WTFs?" They weren't all errors that a compiler would complain about. Fortunately I've studied C++ extensively -- I used to subscribe to C++ Report -- and I was able to talk about several design issues, ranging from the lack of a virtual destructor in a base class to failure to properly implement the necessary constructor, copy constructor, and assignment operator. There was a problem with a const method. There was a pointer aliasing problem. There were a few other small issues I did not notice. I missed an issue: dynamic_cast can return NULL. I missed this because I have never had to use that sort of run-time introspection in C++, although one of my interviewers pointed out how it can be useful and necessary for adding test functionality to a framework. Overall, I think I got most of the credit for this one.
The first task, the one I botched, was to write a function to reverse a standard null-terminated C string, in place. Wow, the world loves nothing more than to humble us now and then, doesn't it?
Right off the bat, I became confused because of the prototype for the function. The question indicated that the first parameter would be a pointer to a zero-terminated string, but the second parameter was to be a size_t type -- a buffer size. I suppose this is analogous to the standard C library routines strn*, which are safer versions of the old strcpy, strlen, etc. These versions take a number indicating how far the function can travel in memory before bailing out -- giving a sort of "backup plan" in case the incoming string is not properly null-terminated. These are certainly better than the old functions that can rip through memory, or leave your code vulnerable to a variety of stack-smashing and buffer-overflow exploits. But to me there's something inherently horrible about a function with such a contradictory "contract" -- it is designed in such a way that it will hide, or at least give safe harbor, to bugs in the code that calls it. It has the information it needs to report that it has been called with an unterminated string, but there is no provision to return an error code, and the assignment did not indicate what I should do if the incoming string is not terminated. Presumably I'm not supposed to crash the computer -- although with no way to return an error, forcing a crash immediately is really the safest possible option!
The "safer" standard library function strnlen receives a value telling it how many characters it should count before it bails out, and returns a value indicating how many characters it actually counted. If you get back the same number you provided, it means that the incoming string is not properly null-terminated. You can (and hopefully will) do something with that information. But the "safer" strncpy doesn't provide any indication that it has been handed a source string that isn't null-terminated, and so can leave the destination filled with an unterminated string. That's inherently unsafe. The prototype given makes this function a little like strncpy.
So while my brain was chewing on all that in the background, I started trying to get something down on paper, writing a shell for the function, to dispose of some possible error conditions first. And I confused myself further.
In the bad old days, size_t was not guaranteed to be unsigned, so it was possible that the provided buffer size could be less than zero. That's not the case in standard C, but I coded to test for it anyway. Most compilers would tell me that I was testing for a condition that can't happen, fortunately.
Next, I tested for whether I could bail out early -- whether the provided buffer size value is less than or equal to 1. I'm not sure if this would be a performance win -- it depends a lot on the sizes of the string that the function will be given. But I wanted to show that I was at least thinking about these different possible cases.
And then it was time to write the meat of the function. I had my heart set on writing a recursive solution. Why? To show off, maybe, even though this isn't actually a very practical solution in C. But more likely, because I've gotten used to reversing lists in languages like Scheme and Haskell that use Lisp-style lists. Which... are not at all like plain old arrays of bytes. But I was determined. To show that I was at least aware that recursive functions can fail when they use too much stack space, invented a constant, MAX_STACK_SPACE_ALLOWED, and made sure my buffer size didn't exceed it. So then I had several error-checks and had filled most of the page. There was nothing else I could do but write the recursive helper function to reverse the string.
And I realized that it has been a long time since I wrote something like that in plain C I was still chewing over what to do with the buffer length parameter, and wondering if I was missing something fundamental about the problem. And so I panicked and bailed out, feeling really stupid. Stupid brain! How could you let me down like that?
I had some more time to think about it today, and play around with some code, and think about the "contract" for the function and just why I got stuck. The idea behind a recursive reverse of a list is that you recurse to the end of the list, and then build up a list of the elements in reverse order as the recursion "unwinds." In Scheme, something like this:
(define (my-reverse lat)
(if (null? lat)
'()
(append (my-reverse (cdr lat)) (list (car lat)))))
C doesn't do the data-structure bookkeeping for you. Recall that we're supposed to the reverse in place. This solution starts with an empty list and creates new cons cells to add to it. And of course a list doesn't look like a primitive string of bytes. So I've got to get my head back in the C game.
As a warmup, let's write a recursive solution that uses an auxiliary buffer for the output, because that sounds easier to me. First, I want a routine to handle some special cases, which will then call a recursive function. It is at this point that I have to figure out what I'm going to do with an unterminated string. My answer: I'm going to terminate it. You're terminated, sucker. Yes, I'm going to overwrite a character of the data you passed me. Dude, where's my data? No, DUDE! Where's my string terminator?
Is that the right answer? I don't know. Actually, I'm pretty sure that this is not what the guys that gave me the task had in mind. In retrospect I think it probably would have made more sense to just use strnlen to get a "working length," and just reverse that many characters. But I think the bigger problem is that asking for a function with that prototype is asking the wrong question. It's a guaranteed "WTF?" for someone. Anyway, here's the "preamble" error-checking code as I wrote it today, for working with a function that returns the reversed string in an auxiliary data buffer:
void ReverseString( char *str_p, size_t buffer_size )
{
if ( NULL == str_p )
{
printf( "NULL pointer!\n" );
return;
}
else
{
unsigned long len = strnlen( str_p, buffer_size );
if ( buffer_size == len )
{
str_p[buffer_size - 1] = '\0';
len--;
printf( "Terminating your string for you!\n" );
}
/* Recursive with an auxiliary array */
char *str_out_p = (char *)( malloc( buffer_size ) );
if ( NULL == str_out_p )
{
printf( "malloc failed!\n" );
return;
}
else
{
strncpy( str_out_p, str_p, buffer_size );
printf( "Before: %s\n", str_p );
ReverseStringAuxHelper ( str_out_p, str_p );
printf( "After: %s\n", str_out_p );
free( str_out_p );
}
/* This doesn't actually meet the requirements... */
}
}
So let's write ReverseStringAuxHelper now. Something like this:
void ReverseStringAuxHelper( char *str_out_p, char *str_in_p )
{
/* Do some setup, and call a recursive helper */
}
Our basic strategy for recursive calls is clear: we want to call ourselves on a shorter substring of the input string, until we hit a NUL. And then... build up the data to return. But how do we do that? As we "unwind" the call stack, we will have a series of pointers to characters in the input string, in reverse order. But we want to write them into the outgoing string in forward order. To keep track of the index into the auxiliary data structure we could use a global (a file-scope variable, maybe declared static). Gag me with a spoon. No, let's use a local. You can't nest functions in C; you don't have lexical closure. But we can do something like this (get your barf bags ready):
void ReverseStringAuxHelper( char *str_out_p, char *str_in_p )
{
char *str_out_walking_p = str_out_p;
ReverseStringAuxRecursive
( &str_out_walking_p, str_in_p );
}
We can pass the address of the local pointer variable, to allow the recursive function to modify it -- so it can use the pointer, and increment its value. The recursive function now has a prototype that looks like this:
void ReverseStringAuxRecursive( char **str_out_p_p,
char *str_in_p );
Note the double-asterisks: a pointer to a pointer. And now the whole function:
void ReverseStringAuxRecursive( char **str_out_p_p,
char *str_in_p )
{
if ( '\0' != *str_in_p )
{
ReverseStringRecursiveAuxHelper( str_out_p_p,
str_in_p + 1 );
**str_out_p_p = *str_in_p;
*str_out_p_p += 1;
}
}
Good heavens. That is.. inelegant. In C++ we could do that by reference, at least, which would clean the appearance of the pointer expressions, but that really just sweeps it under the rug. It works, but can we do better? In fact, after sleeping on it for a while, I woke up abruptly with a prettier solution in my head. The key insight was realizing that there is no good reason I can't recurse with two parameters that are each changed to bring us closer to the terminating condition. We have already calculated the length of the string, so why don't we use that to figure out the terminating condition?
void ReverseStringAux2Recursive( char *str_out_back_p,
char *str_in_fwd_p, char *str_in_term_p )
{
if ( str_in_fwd_p < str_in_term_p )
{
*str_out_back_p = *str_in_fwd_p;
ReverseStringAux2Recursive( str_out_back_p - 1,
str_in_fwd_p + 1, str_in_term_p );
}
}
The idea here is that we will recurse on the input string, walking forwards through it and ending when we reach a supplied end pointer, and copying characters into the output string walking backwards. It's tail-recursive, which is nice (I'll talk about that a little more later). We could let the function write the terminating NUL by changing the test to read
if ( str_in_fwd_p < str_in_term_p )
But if we did that, we'd wind up writing a terminating NUL before the first character in the output string. We don't want to do that, so we need a special case for this. Let's just let our helper function do it.
void ReverseStringAux2Helper( char *str_out_p,
char *str_in_p, unsigned long len )
{
/*
The caller must guarantee that the
output string can hold len + 1 chars
*/
ReverseStringAux2Recursive( &str_out_p[len - 1],
str_in_p, &str_in_p[len] );
/* Write the terminator in the output string */
str_out_p[len] = '\0';
}
That doesn't look too bad. We make use of the fact that we've already calculated the length of the string. Now, that we've figured out how to do this with two changing pointers, can we do that in place? Yes, we can:
void ReverseStringInPlaceRecursive( char *fwd_p,
char *back_p )
{
if ( fwd_p < back_p )
{
char temp = *fwd_p;
*fwd_p = *back_p;
*back_p = temp;
ReverseStringInPlaceRecursive(fwd_p + 1,
back_p - 1);
}
}
void ReverseStringInPlaceHelper( char *str_p,
unsigned long len )
{
ReverseStringInPlaceHelper( str_p,
&str_p[len - 1] );
}
That's longer, but most of the body of the recursive function is just devoted to swapping characters using a temp value, before the tail recursion. But what's going on with
if ( fwd_p < back_p )
? Well, I'm glad you asked. Note that we're swapping characters. We walk along the string, going backwards, swapping characters from the front of the string, going forwards. But then a funny thing happens. The pointers meet in the middle, and cross. In other words, you want "ABC" to become "CBA" but if you don't stop the reversing process at "B", the left and right sides of the string are swapped again, giving you "CBC." The resulting string is palindromic -- it reads the same forward as backwards -- and so reversing it again leaves it unchanged -- but that's not what you want. Run this in an interactive debugger if you can -- it's interesting to watch. Well, if you like that sort of thing. It might help if I give you a picture:
By the way, both the recursive reverse in place and the second recursive reverse to an auxiliary string have a subtle bug. Can you spot it? I'll come back to that later at the end of this post.
Anyway, pretty as that in-place solution is, we probably don't really want a recursive solution in C. The biggest reason is that although I hear some C compilers now will optimize tail recursion into simple iteration, they aren't required to do it. I've heard that GCC can do it, but I wasn't able to figure out how to get my setup (LLVM GCC 4.2 with XCode 4.6.2) to do the optimization, as far as I could tell. So I'd say you definitely can't count on it, and so a big string might blow up your stack.
So what about an iterative solution? There are a few options, but a basic pointer math approach is very idiomatic C, and it looks very similar to the recursive solution, even if walking a pointer backwards seems a little odd and hazardous:
char *fwd_p = str_p;
char *back_p = &(str_p[len - 1]);
while ( fwd_p < back_p )
{
char temp = *fwd_p;
*fwd_p = *back_p;
*back_p = temp;
fwd_p++;
back_p--;
}
That's not a complete function. Here's a complete function with a test routine. This version is written without the buffer size parameter of the original spec. You'll need to include assert.h, string.h, and stdio.h
/* in-place reverse with two pointers */
void ReverseStringWithPointers( char *str_p )
{
/*
There are several conditions that would induce us to exit
early. A null pointer is the most obvious one.
*/
if ( NULL == str_p )
{
return;
}
else
{
/*
A zero-length string is the next
*/
if ( '\0' == *str_p )
{
return;
}
else
{
/*
Assume the string is properly terminated; find the end
*/
char *back_p = str_p + 1;
while ( '\0' != *back_p)
{
back_p++;
}
/* Leave back_p pointing to the last character before the terminator */
back_p--;
while ( str_p < back_p )
{
char temp = *str_p;
*str_p = *back_p;
*back_p = temp;
str_p++;
back_p--;
}
}
}
}
char const *one_char_str = "1";
char const *two_char_str = "12";
char const *three_char_str = "123";
int main(int argc, const char * argv[]) {
/* Put these in writable storage */
char writable_one_char_str[2];
char writable_two_char_str[3];
char writable_three_char_str[4];
strcpy( writable_one_char_str, one_char_str );
strcpy( writable_two_char_str, two_char_str );
strcpy( writable_three_char_str, three_char_str );
ReverseStringWithPointers( NULL );
ReverseStringWithPointers( writable_one_char_str );
ReverseStringWithPointers( writable_two_char_str );
ReverseStringWithPointers( writable_three_char_str );
assert( 0 == strncmp( writable_one_char_str, "1", 1 ) );
assert( 0 == strncmp( writable_two_char_str, "21", 2 ) );
assert( 0 == strncmp( writable_three_char_str, "321", 3 ) );
return 0;
}
That's probably a preferred interview solution for the "standard" in-place string reverse without the buffer size parameter. It illustrates how idiomatic C pointer math is; it's idiomatic because it expressive and it works. It is probably one of the biggest reasons for C's longevity.
So, any other ideas for implementing the string reverse? Well, for the core logic you can use array indexing like so:
for ( unsigned long idx = 0; idx < ( ( len / 2 ) - 1 ); idx++ )
{
unsigned long rev_idx = len - 1 - idx;
char temp = str_p[idx];
str_p[idx] = str_p[rev_idx];
str_p[rev_idx] = temp;
}
But that is actually problematic for some string lengths. If len is less than two, dividing it by two to find the array's halfway point yields zero, and when you subtract one, you'll have an underflow, giving a very large positive number for your array index, giving undefined befhavior (if you're lucky, you'll get an immediate crash). This approach can be rehabilitated by screening the early return conditions.
Oh, there's another little trick you can do. I'll leave it to you to figure this one out, if you haven't seen it before. Instead of using a temporary variable to swap the characters, you could do this:
str_p[rev_idx] ^= str_p[idx]; str_p[idx] ^= str_p[rev_idx]; str_p[rev_idx] ^= str_p[idx];
And there, dear reader, I will leave you for today. I hope you found this interesting and maybe learned something. I did. Maybe you can see why my brain locked up -- I didn't want to write a function with that prototype; it it seems to contradict itself as far as whether it should be safe, or just efficient. Wanting to write a recursive solution was a secondary issue. Oh, and of course let's not forget that this is the wrong solution for modern strings -- for any Unicode types. It only works for old-school strings of bytes.
Don't get me wrong -- I'm not actually complaining about the interview question. It's a great interview question, because it looks easy but it should also bring up a lot of safety and design issues in the programmer's head. I've been humbled just a bit. I've been reminded that while I've spent years writing code that uses STL and reference counting and nice, modern features of C++ and more modern libraries, I've forgotten just a bit how low-level C often turns out to be. I should never do that, because of course sometimes you have to debug all that nice, modern code, and remember what is going on underneath. Had I been asked to write the solution in a simple assembly pseudo-code, I would have had to come up with an iterative solution immediately, although I'm not sure I would have been able to work out the pointer-crossing problem in the interview setting. Recursion is almost certainly the wrong way to go in C, but maybe you can see why I was drawn to the idea, especially of writing the reversed string to a second buffer. It's funny how a relatively simple problem in C can be so "interesting." May we one day no longer live in such interesting times...
FOLLOWUP: I got feedback that the interviewers were quite pleased with both my performance and attitude. I actually sent them the source code for my experiments today, too, with some comments, in case they have anything to add. I screwed that up again, though, because the first version had a crashing bug, so I sent another one, and that still didn't have the most elegant form of the recursive functions. And, a couple of the solutions have that subtle bug I mentioned earlier. What is the subtle bug?
Obviously, it is a bug to write past the end an array in memory -- whether we're talking about an array allocated dynamically on the heap, on the stack, or in static storage, like a global variable. You can't guarantee that this bug will be caught -- it could be symptomless, just silently corrupting some other variable in your program. And obviously it is a similar bug to write before the beginning of an array. But did you know it is a bug to calculate the address of an item before the first item, even if you never use it to write to the array?
The C standard guarantees that you are allowed to create the address of an extra array element past the end of your array. Reading or writing at this location is "undefined behavior" -- that is, very bad. But there is no such guarantee for creating a pointer to an array element at index -1, even if you don't read or write it. See also this CERT coding guideline.There are several places in our recursive code where that is actually a concern. If we have a zero-length string, our calculated len is zero. Every place where we use len should be inspected. For example, in ReverseStringAux2Helper, I pass the value &str_out_p[len - 1]. This gives me the address of the last writable character in the output array. But for a zero length string, this will result in calculating the address of the character before the first character of the output string.
The rationale for this, I believe, goes something like this. On an arbitrary computer running your C program, you don't actually know what your memory addresses look like, at the hardware level. C has to cover a lot of weird and arcane and now-deceased architectures: segmented pointers, odd pointer sizes, architectures where different types of addresses have different numbers of bits, architectures where only address registers can hold addresses and they aren't the same size as any other type, etc. What if you're running this on a small processor, and it just so happens that the array in question was started at hardware address zero? Calculating the address of element -1, in an unsigned pointer type, would "underflow" into a large number. I don't specifically know of an architecture where just storing that number in an address register or in memory will really crash, but there could be one, or at least could have been one. And the designers of the C standard wanted to make sure that C was as portable as possible.
The logic in ReverseStringAux2Recursive determines that there is nothing to do, and so we don't write to that address, but it is still illegal. To be strictly scrupulous about observing the standard, logic should be changed so that in the case of the zero length string, we don't get to the point where we calculate the address of that non-existent element. This also happens in the code where we calculate the length of a string and determine if it needs to be forcibly terminated -- in the case of a specified buffer length of zero, len underflows. A zero-length string can't be a valid string. I really do need to avoid this case entirely. I also need to think hard about the string size that is specified as one character, which can become a zero-length string if we forcibly terminate it. So the wrapper logic, given my chosen strategy of terminating unterminated strings, needs to look something like this:
void ReverseString( char *str_p, size_t buffer_size )
{
if ( NULL == str_p )
{
printf( "ReverseString: received NULL pointer!\n" );
return;
}
else if ( 0 == buffer_size )
{
printf( "ReverseString: received buffer_size 0!\n" );
return;
}
else
{
/*
strnlen returns the number of characters before
the NUL or the provided maximum. If we get back
the maximum, assume the string is NOT terminated.
*/
unsigned long len = strnlen( str_p, buffer_size );
if ( buffer_size == len )
{
/*
Forcibly terminate the incoming string,
consider its length to be one shorter, log a
problem, and continue
*/
str_p[buffer_size - 1] = '\0';
len--;
printf( "ReverseString: no termination found!\n" );
/*
If our adjusted string length is zero, don't
continue because some of our algorithms that
create pointers to the first character before
the terminator will generate a pointer to an
array item at index -1, an invalid operation
per the C standard
*/
if ( 0 == len )
{
printf( "After termination, len is 0!\n" );
return;
}
}
/*
There is really nothing we need to do to reverse
a string of length 1, but rather than rule that out
here, we let our algorithms handle that case to
exercise their boundary conditions.
*/
This is another case where the two parameters, the string pointer itself and the buffer_size, can contradict each other, with results that are complicated no matter what you do.
What happens if we don't forcibly terminate incoming strings that aren't terminated within buffer_size chars, but just reverse buffer_size chars? Well, the preamble code is a little different. Here's a version of the whole function that does that. The reversal algorithm in this version isn't very efficient -- it copies bytes twice, and it allocates extra storage. But efficiency wasn't mentioned in the task description, and I think it is correct, at least for this interpretation of how to deal with strings that aren't terminated within buffer_length chars. It also seems like something I might have had a better chance of getting right on paper, quickly, when put on the spot.
void ReverseStringFinal( char *str_p, size_t buffer_size )
{
/*
We take the buffer_size parameter to mean
that we shouldn't touch more that buffer_size
bytes, even if the string is longer.
There are several error conditions that really
should trigger failure, returning some kind of
error code, but the spec doesn't give us that
option.
*/
if ( NULL == str_p )
{
return;
}
else
{
/*
strnlen will return buffer_size if it
doesn't find a terminator before counting
buffer_size characters.
*/
unsigned long len = strnlen( str_p, buffer_size );
/* I'd like to use max(), but it is not standard C */
unsigned long working_len = 0;
if ( len < buffer_size )
{
working_len = len;
}
else
{
working_len = buffer_size;
}
if ( working_len < 2 )
{
/*
Reversing a string of 0 or 1 character
is a no-op
*/
return;
}
else
{
/*
An inefficient but simple solution using a
temporary buffer
*/
char *temp_buf_p = (char *)
( malloc( working_len ) );
if ( NULL == temp_buf_p )
{
return;
}
else
{
/* Copy chars backwards */
for ( unsigned long idx = 0;
idx < working_len; idx++ )
{
temp_buf_p[ working_len - 1 - idx] =
str_p[idx];
}
/* Copy forwards into original buffer */
for ( unsigned long idx = 0;
idx < working_len; idx++ )
{
str_p[idx] = temp_buf_p[idx];
}
/*
Don't write a null; only touch
the chars in the working length.
*/
free( temp_buf_p );
}
}
}
}
1 comment:
Love you, Paul. Tl;dr.
Post a Comment