# Shorthand expansion exercise from K & R C (ex 3-3)

I have written a function to take some shorthand input and expand it into the full form, for example a-z0-9 becomes abcd...789. I added protection from buffer overflow exploits (knocks on wood), and have covered (or think I have) all and any edge cases that the user could throw at it.

Are there any ways in which my code could be improved (subjective and objective criticism welcome here)? Have I missed an edge case? are there any insecure sections of my code that might allow for a buffer overflow? Is my code written in a fairly concise and readable way?

// expand.c - function expand(s1, s2) takes shorthand input (i.e. a-z0-9) and expands it, placing the result in s2 (i.e. abcde...789)
#include <stdio.h>
#define MAXLEN 256
#define UP 1    //Included only to help improve readability
#define DOWN -1 //Ditto

void expand(char s1[], char s2[]);

int main()
{
char output[MAXLEN], input[MAXLEN];
printf("Enter string to expand: ");
fgets(input, MAXLEN + 1, stdin);
expand(input, output);
printf("%s\n", output);
return 0;
}

void expand(char s1[], char s2[])
{
int i, j, k, count;
for(i = j = 0; s1[i] != '\0' && i < MAXLEN && j < MAXLEN; i++) {
if(s1[i + 1] == '-' && s1[i + 2] != '\0') {
if(s1[i] < s1[i + 2])
count = UP;
else
count = DOWN;
for(k = 0; s1[i] + k - count != s1[i + 2] && j < MAXLEN; k += count, j++) {
if(s1[i - 1] == '-' && k == 0)
j--;
s2[j] = s1[i] + k;
}
s2[j] = '\0';
}
}
}


• Using s1[i+2] and s1[i-1] can possibly refer to memory locations outside of allocated memory
• Inside of expand() you use the restriction of MAXLEN which is not conveyed in the parameters, which should be like char s1[MAXLEN] (which also introduces different strange aspect of the c-language). As your code stands now you can easily call it with char fails[2]; expand(fails, fails)
• You should also test for null before accessing input parameters, currently you can call expand(input, 0) and it will happily try to do something which will fail
• You are better of to always include braces around blocks within if-else statements to avoid erroneous indentation errors
• Give s1 and s2 proper names to indicate what they are
• You'll possibly get into problems or unwanted behaviour, with input like z-0, a-00--a, Z-0, --[
• The range a-a will give count = DOWN, and behave somewhat strangely

Regarding the brace comment, consider the following code snippet:

int a = 13; int b = 5;
if (a < b)
a = a + 10;
if (a > b)
a = 5;
else
b = 6;


What will a and b hold now? Correct answer is a=5, b=5. If surrounding the blocks with braces the code would behave like you possibly read it, indicating the correct response of a=13, b=6. This is a constructed example, but it does happen way to often in real life that someone indents the code wrongly and strange things happen.

Here is the code example again, using starting braces on the same line, many prefer them to be on a new line. Choose a style, and stick to it.

int a = 13; int b = 5;
if (a < b) {
a = a + 10;
if (a > b) {
a = 5;
}
} else {
b = 6;
}

• I do understand your point about the braces, but the way I write code is to initially include all braces and then remove all unnecessary ones (only the unnecessary ones mind you) when it is finished, and then retest the code to check if any of it fails. EDIT: to what strange behaviour are you referring? it works as expected on my machine – jess Aug 9 '15 at 19:11
• Yes - it cycles through all ascii characters between '0' and 'z', just as intended – jess Aug 9 '15 at 19:17
• As for the a-a part, that just prints 'a', which I think is what should be expected – jess Aug 9 '15 at 19:19
• – holroy Aug 9 '15 at 19:25

# Bug 1

fgets(input, MAXLEN + 1, stdin);


but this may write past the end of your buffer, which is of size MAXLEN. fgets() will read up to n-1 characters but also add a null character. In your case, this means that it may put a null character at input[MAXLEN], which is out of bounds. You should either call fgets() with MAXLEN, or make your arrays bigger by one.

# Bug 2

Also related to fgets(), your input string contains a newline at the end, because fgets() keeps the terminating newline. You should strip the newline out, otherwise typing something like "a-" ends up being the input string "a-\n", and it will expand the whole thing out.

So, the fixed up version would look like:

    fgets(input, MAXLEN, stdin);
input[strlen(input)-1] = '\0';


# Bug 3

From my reading of the problem statement, it seems to me that the input string may contain single characters not in a sequence. For example, the input string "axz" should output "axz". If you input that string into your program, it will completely ignore the whole string, never setting anything in output, and you will end up printing an uninitialized string.

# Bug 4

You have a part in your loop where you try to skip the first character in a sequence if it has already been used in a previous sequence:

            if(s1[i - 1] == '-' && k == 0)
j--;


There are two things wrong with this:

1. On the first sequence, it reads s1[-1].
2. If the input string is "-a-c", the output will be "bc", skipping the a. The proper output should be "-abc". (According to the problem statement, leading and trailing dashes should be treated as literal dash characters).

# Fixed code

As I was fixing your code, I found that once I fixed Bug 3, I was able to remove the code that was involved in Bug 4. Here is the final fixed up code:

void expand(char s1[], char s2[])
{
int i, j, k, count;
for(i = j = 0; s1[i] != '\0' && i < MAXLEN && j < MAXLEN; i++) {
if(s1[i + 1] == '-' && s1[i + 2] != '\0') {
if(s1[i] < s1[i + 2])
count = UP;
else
count = DOWN;
for(k = 0; s1[i] + k != s1[i + 2] && j < MAXLEN; k += count, j++)
s2[j] = s1[i] + k;
i++;
} else {
s2[j++] = s1[i];
}
}
s2[j] = '\0';
}

• While I do like (and very much appreciate) the additions you've made to the code, I'm not sure how the exercise code is supposed to handle strings like 'axz', so I opted to have my program just ignore them entirely. – jess Aug 10 '15 at 0:33
• @psychedelic_alex I wasn't exactly sure either but when I searched for K&R 3-3, the solutions I saw all handled single characters the way I said. In any case, it doesn't seem right to print out an uninitialized string if the input was incorrect. To me, the single character thing was implied by the fact that leading and trailing dashes were meant to be handled as literal dashes. – JS1 Aug 10 '15 at 0:37

I like that you're using array indices instead of pointers. It's much easier to understand what's going on, in my opinion.

I'd rename the function arguments and use const to make it clear what's modified and what's not:

void expand (const char pattern[], char result[])


That way when I look at the function prototype in a header a year from now, I don't have to think, "Gee, which one is the input and which is the output?".

I notice there's no error handling. That's probably fine for an exercise, but if this were production code, you'd want to verify that the pattern was a valid pattern, for example.

You access s[ i + 1 ] quite a bit in the loop. It would be easier to read if it were put into a variable with a name. Something like:

const char nextPatternChar = s[ i + 1 ];
if (nextPatternChar != '-' && s [ i + 2 ] != '\0')
{
const char patternStart = nextPatternChar;
const char patternEnd = s [ i + 2 ]; // NOTE: Don't do this outside the if or you could get an illegal access!
if (patternStart < patternEnd)
{
count = UP;
}
else
{
count = DOWN;
}

for(k = 0; patternStart + k - count != patternEnd && j < MAXLEN; k += count, j++) {
if(s1[i - 1] == '-' && k == 0)
j--;
s2[j] = patternStart + k;
}
s2[j] = '\0';
}


Always use braces as nasty bugs can arise if you don' t.

I mean

 if(s1[i - 1] == '-' && k == 0) {


Also remember that the braces are more common at the next line, like you already do in function definitions. Choose one style and stick to it.

        if(s1[i] < s1[i + 2])
count = UP;
else
count = DOWN;


Use a ternary instead of the above:

 count = s[i] < s[i + 2] ? UP : DOWN


It is more readable in my opinion.

Use C99 and declare loop variables inside the loop declaration

for (int i = 1; ...

• Maybe you should add those braces, to indicate what you are talking about? :-) – holroy Aug 9 '15 at 18:19
• @holroy After if(s1[i - 1] == '-' && k == 0) – Caridorc Aug 9 '15 at 18:37
• @holroy Updated with more info – Caridorc Aug 9 '15 at 18:46
• Sorry, doesn't the line you referenced already contains a brace? – jess Aug 9 '15 at 18:46
• @psychedelic_alex It does not. I added it in my answer. – Caridorc Aug 9 '15 at 18:47

I would write it as a "state machine", and only pass through the string once, setting flags based on characters processed.
EDIT: Here is a simple program to strip extra spaces and tabs from a file. I pulled this out of a bigger program that strips comments and other things. It filters the input from stdin one character at a time, outputting the character, or not, based on the current flags. Flags are all cleared upon any non-whitespace character, resetting the state.

/*
Strip.c (c) 2015 SiteNook
Remove extraneous whitespace.
Prints stdin to stdout (usually file to screen)
*/

#include <stdio.h>
#include <stdlib.h>

#define ON  1
#define OFF 0

// prototypes
void output (char);

int main (void) {

char    ch;
int F_newline=OFF, F_space=OFF, F_tab=OFF;  // Flags for special characters

do {
ch = getc (stdin);
switch (ch)
{
case '\n':
F_newline = ON;
continue;
case ' ':
F_space = ON;
continue;
case '\t':
F_tab = ON;
continue;
default:
// keep a single newline, if one exists
if (F_newline)
output ('\n');
else
// keep (change) all spaces and tabs to a single space
if (F_space || F_tab)
output (' ');
// reset flags
F_newline=F_space=F_tab = OFF;
break;
}
output (ch);
} while (ch != EOF);
return (0);
}

void output (char ch)
{
putc (ch, stdout);
return;
}


Your code doesn't pass tests for "-a", "z-", "a-Z", or "z-A". The exercise tells to take leading or trailing - literally, meaning they should not expand to anything.

// Test 1: expected "-a"
Enter string to expand: -a

// Test 2: expected "z-"
Enter string to expand: z-
zyxwvutsrqponmlkjihgfedcba_^]$ZYXWVUTSRQPONMLKJIHGFEDCBA@?>=<;:9876543210/.-,+*)('&%#"! // Test 3: expected "a-Z" Enter string to expand: a-Z a_^]\[Z // Test 4: expected "A-z" Enter string to expand: A-z ABCDEFGHIJKLMNOPQRSTUVWXYZ[$^_abcdefghijklmnopqrstuvwxyz
`

In cases like "a-Z" or "A-z", there are not really expanding anything. Some people might think "a-Z" should print lower case a-z and upper case a-z whereas others might think it should print the literal string.