My number one piece of advice: More functions! One of your goals when writing a program should be to minimize the number of comments that are necessary by organizing the code in such a way as to make the functionality obvious.
Let's take a top-down approach to begin: I'll rewrite main with this principle in mind.
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Number of characters in our input alphabet (A-Z).
#define ALEN 26
// Characters in decreasing order of frequency in English.
const char charsByFrequency[] = "ETAONRISHDLFCMUGYPWBVKJXQZ";
enum OperationMode {
DECODE,
I, // I'm not sure what -i does
};
struct ProgramOptions {
enum OperationMode operation_mode;
};
// Prints usage statement to stderr and returns non-zero on error.
int read_options(int argc, const char** argv, struct ProgramOptions* options);
// Allocates space for text and reads text from in. Returns the number of
// characters in *text, or 0 on a read error. *text must be deallocated with free().
size_t read_text(FILE* in, char** text);
struct CharacterFrequency {
char c;
int count;
};
// counts must have dimension ALEN.
void count_character_frequencies(const char* text, size_t num_chars, struct CharacterFrequency counts[]);
void print_character_frequencies(FILE* out, const struct CharacterFrequency counts[]);
// Use the frequency counts of characters (as given by counts)
// to decode encoded into decoded.
//
// decoded must have space for at least num_chars + 1 characters.
// counts must have dimension ALEN and will be modified.
void decode_text(const char* encoded, char* decoded, size_t num_chars,
struct CharacterFrequency counts[]);
int main(int argc, char** argv) {
struct CharacterFrequency counts[ALEN];
struct ProgramOptions program_options;
char* text;
size_t text_length;
if (read_options(argc, argv, &program_options)) {
exit(1);
}
if (!(text_length = read_text(stdin, &text)) {
free(text);
exit(1);
}
count_character_frequencies(text, text_length, counts);
print_character_frequencies(stderr, counts);
if (program_options.operation_mode == DECODE) {
char* decoded = (char *) malloc(sizeof(char) * (text_length + 1));
decode_text(text, decoded, text_length, counts);
printf("%s\n", decoded);
free(decoded);
} else {
fprintf(stderr, "-i is unimplemented");
free(text);
exit(1);
}
free(text);
return 0;
}
Now the full functionality of the program can be understood by reading a couple of dozen lines instead of the whole program! Now let's implement our helper functions.
int read_options(int argc, const char** argv, struct ProgramOptions* options) {
static const char usage_format_str[] =
"Usage:\n"
" %s [-d|-i]\n"
" Options:\n"
" -d: Print a best-guess decryption of the input.\n"
" -i: ????\n";
if (argc != 2 || argv[1][0] != '-') {
fprintf(stderr, usage_format_str, argv[0]);
return 1;
}
switch (argv[1][1]) {
case 'i':
options->operation_mode = I;
break;
case 'd':
options->operation_mode = DECODE;
break;
default:
fprintf(stderr, usage_format_str, argv[0]);
return 1;
}
return 0;
}
Not much has changed here. I've given the options names so that I can localize the knowledge that "-d" means decode and "-i" means whatever to this single function.
// Increasing this size increases the minimum memory requirements
// but decreases time spent re-allocating memory for large inputs.
// I've chosen 1MB as a reasonable buffer size.
#define INITIAL_BUFSIZE 1048576
// If there's not at least this much free space in the buffer between
// reads, the buffer will be reallocated.
#define MIN_BUF_OVERHEAD 1024
size_t read_text(FILE* in, char** text) {
size_t total_read = 0, alloc_size = INITIAL_BUFSIZE;
assert(text);
*text = (char *) malloc(INITIAL_BUFSIZE);
while (*text) {
// Loop invariant: *text points to a buffer that is of length at least
// total_read + MIN_BUF_OVERHEAD
assert(alloc_size >= total_read + MIN_BUF_OVERHEAD);
total_read += fread(*text + total_read, 1, alloc_size - total_read - 1, in);
if (feof(in)) {
(*text)[total_read] = '\0';
return total_read;
} else if (ferror(in)) {
fprintf(stderr, "Error reading in text.\n");
return 0;
}
if (alloc_size - total_read < MIN_BUF_OVERHEAD) {
// Doubling the allocation size makes this total read take O(N) time.
size_t new_alloc_size = 2 * alloc_size;
void* newptr;
if (new_alloc_size < alloc_size) {
fprintf(stderr, "Goodness, we've run out of virtual memory!\n");
return 0;
}
newptr = realloc(*text, new_alloc_size);
if (!newptr) {
fprintf(stderr, "Error allocating %zu bytes.\n", new_alloc_size);
return 0;
}
*text = (char *) newptr;
alloc_size = new_alloc_size;
}
}
// We're only here if the initial allocation failed.
fprintf(stderr, "Couldn't allocate any memory for text.\n");
return 0;
}
A couple things here. First, using fread instead of fgetc should make your reads considerably faster. This is for two main reasons: fewer function calls means less overhead, and fgetc copies one byte at a time while fread uses memcpy, which generally copies multiple bytes per instruction. Second, this allocates enough memory to read in whatever file is passed on stdin; it's not limited to 10000 bytes. There is a tradeoff: The code is, as a result, more complicated and less obviously correct.
int is_decodable_character(c) {
// NOTE: isalpha returns true for more than just A-Z in some locales.
// However, our code assumes that A-Z (26 letters) is our entire alphabet,
// so isalpha is not appropriate here.
return 'A' <= c && c <= 'Z';
}
void count_character_frequencies(const char* text, size_t num_chars, struct CharacterFrequency counts[]) {
for (size_t i = 0; i < ALEN; ++i) {
counts[i].c = 'A' + i;
counts[i].count = 0;
}
for (size_t i = 0; i < num_chars; ++i) {
char c = toupper(text[i]);
if (is_decodable_character(c)) {
++counts[c - 'A'].count;
}
}
}
OK, some big differences here. I've built in the assumption that the alphabet is the 26 Roman letters A-Z. This should make the code considerably faster (not a big deal on small inputs, but should be noticeable on large inputs). If you want to allow arbitrary character sets, consider using a map data structure of some type instead of an array so that you can have efficient lookup.
void print_character_frequencies(FILE* out, const struct CharacterFrequency counts[]) {
fprintf(out, "Character Frequencies:\n");
for (size_t i = 0; i < ALEN; ++i) {
fprintf(out, "%c: %d\n", counts[i].c, counts[i].count);
}
}
Your code appeared to print out the ASCII character corresponding to the count for each letter (e.g. if a letter appeared 33 times, '!' would be printed). You also printed the translated character frequencies; that is, 'E' would always have the highest count because you swapped out characters before printing the frequencies.
That seems like it would be less useful to the user than printing the frequencies of the encoded characters, so I've done the latter.
Here's an alternative implementation:
void print_character_frequencies(FILE* out, const struct CharacterFrequency counts[]) {
fprintf(out, "Character Frequencies:\n");
for (size_t i = 0; i < ALEN; ++i) {
fprintf(out, "%3c", counts[i].c);
}
fprintf(out, "\n");
for (size_t i = 0; i < ALEN; ++i) {
fprintf(out, "%3d", counts[i].count);
}
fprintf(out, "\n");
}
This version will be more compact, but you'll run into trouble if any character appears more than 999 times (and the numbers will run together if any character appears more than 99 times).
int count_greater(const void* l, const void* r) {
const struct CharacterFrequency *lc = (const struct CharacterFrequency *) l,
*rc = (const struct CharacterFrequency *) r;
return rc->count - lc->count;
}
void decode_text(const char* encoded, char* decoded, size_t num_chars,
struct CharacterFrequency counts[]) {
char translationMap[ALEN];
qsort(counts, ALEN, sizeof(counts[0]), &count_greater);
for (size_t i = 0; i < ALEN; ++i) {
translationMap[counts[i].c - 'A'] = charsByFrequency[i];
}
for (size_t i = 0; i < num_chars; ++i) {
char c = toupper(encoded[i]);
if (is_decodable_character(c)) {
decoded[i] = translationMap[c];
} else {
decoded[i] = c;
}
}
decoded[num_chars] = '\0';
}
This is the biggest departure from your code. First, I've used a library function to sort the frequency counts in descending order. qsort is defined in stdlib.h and uses a much better algorithm than bubble sort. One of the advantages to extracting functions from your code is that it makes it easier to see when you're doing a common operation. In this case, extracting your sorting loop into a function, and calling it "sort_frequencies" (or whatever), makes it easy to see that you're sorting a list. This is such a common operation that even C's standard library provides a sorting function.
Second, I've computed a forward mapping (encoded character -> decoded character) rather than a reverse mapping (decoded character -> encoded character) as you have. This again allows me to do a direct lookup rather than a search through the mapping on each character. Design your data structures so that your most common operations are natural and efficient.
Here's some general-approach advice.
Use the type system appropriately. For example, textfreq isn't really a 2-dimensional array of characters, it's a mapping from characters to counts. Make it an array of an appropriate struct instead of a 2-d array of char.
Encapsulate knowledge. For example, ou store opt as a character -- now all readers of this code need to remember that when opt is 'd', it means that a decryption of the text should be printed at the end of the program. Instead, limit that knowledge to the smallest piece of code possible (in this case, part of a single function) and use well-named variables and the type system to pass this knowledge elsewhere.
Design your data structures so that you don't have to fight against them. textfreq and map were both written so that you needed to write a loop just to do a simple lookup. Now, I chose to rewrite them so that I could just index them by c - 'A', but even if you wanted to keep your approach, you should write accessors with signatures like increment_frequency(char[][2] counts, char c) or char get_frequency(char[][2] counts, char c) or translate_char(char[][2] map, char c).
Use library functions when you can (e.g. toupper instead of your upcase, qsort instead of your bubble sort). They're generally at least as fast as anything you can write -- standard library writers have a lot of experience writing efficient code. They're also well-tested and widely used, and thus less likely to have a bug than ad hoc code.
Use size_t when indexing into arrays or (especially) when referring to buffer sizes.
When you know the length of a string, you should probably pass it along rather than counting on strlen. Besides arguments about efficiency, you should also consider: what if my string is binary data that may contain NULs? Alternatively, what if I forgot to NUL-terminate my string? It's good general practice to pass a string's length around with the string.
One last note: I haven't tried to compile my code, much less tested it. Drop a comment if you have any questions, and good luck!
