6
\$\begingroup\$

I am creating a program that will analyse encrypted text using Kasiski examination in order to find possible key length:

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>
#include <time.h>

char *file_get_contents(char *filename, char *fmode) {
    FILE *f = fopen(filename, fmode);
    fseek(f, 0L, SEEK_END);
    long fsize = ftell(f);
    rewind(f);
    char *file_contents = malloc(fsize+1);
    fread(file_contents, fsize, 1, f);
    fclose(f);
    file_contents[fsize] = 0;
    return file_contents;
}


char *str_copy(char *string, int start, int length) {
    char *s = malloc(length);
    strncpy(s, string+start, length);
    s[length+1] = '\0';    
    return s;
}

void count_factors(int *array, int number) {
    int i;
    for (i=2; i<number; i++)
        if (number % i == 0)
            array[i]++;
}

int main() {
    clock_t start, end;
    double cpu_time_used;
    start = clock();
    char *file_contents = file_get_contents("cipher.txt", "rt");
    char *test_string, *compare_string, match, is_in_array;
    unsigned seq_min = 3, seq_max = 4;
    unsigned long i, j, k, f, number, str_index = 0; 
    unsigned long iterations = 0;
    unsigned *factors_index = {0};
    unsigned text_length = strlen(file_contents);
    unsigned long *factors_value = calloc(text_length, sizeof(unsigned long));
    unsigned arr_str_count = text_length+1, arr_str_length = seq_max+1;
    char strings[arr_str_count][arr_str_length];
    unsigned count_strings = 1;

    test_string = str_copy(file_contents, 0, seq_min);
    strcpy(strings[0], test_string);
    free(test_string);

    for (i=seq_min; i<=seq_max; i++) {
        count_strings = 1;
        for (j=0; j<text_length-i*2;) {
            match = 0;
            is_in_array = 0;
            test_string = str_copy(file_contents, j, i);

            for (f=0; f<arr_str_count; f++) {
                if(strcmp(strings[i], test_string) == 0) {
                    is_in_array = 1;
                    iterations++;
                    break;
                }
            }
            //skipping couple hundreds of iterations in case we already processed current N-gram
            if (!is_in_array) {
                strcpy(strings[count_strings], test_string);
                count_strings++;
                str_index = j;
                for (k=j+i; k<text_length-i-1;) {
                    compare_string = str_copy(file_contents, k, i);
                    if (strcmp(test_string, compare_string) == 0) {
                        number = (k-str_index); //distance between current and old N-gram
                        for (f=2; f<number; f++)
                            if (number % f == 0) {
                                factors_value[f]++;
                                iterations++;
                            }
                        str_index = k;
                        match = 1;
                        k += i;
                    } else {
                        k++;
                    }
                    free(compare_string);
                    iterations++;
                }
            }
            match == 1 ? j+=i : j++;
            free(test_string);
        }

    }

    for (i=0; i<100; i++) {
        if (factors_value[i] > 1)
            printf("%d: %d \n", i, factors_value[i]);
    }

    printf("%llu iterations\n", iterations);

    free(file_contents);
    free(factors_value);

    end = clock();
    cpu_time_used = ((double) (end-start)) / CLOCKS_PER_SEC;
    printf("Process finished: %4.3f secs.\n", cpu_time_used);
    getch();
    return 0;
}

I've done all my best in order to make this process be as fast as I could make it, however, I consider this code pretty slow. Using test text with length = 25663 characters I get the following results:

  • 251,375,553 iterations
  • processing time: 17,387 seconds.

The text for this test (originally taken from dummytext-generator website) was encrypted with a key that is 5 characters long. As a final result I get the following top of possible key values (value: number of occurrences):

 2: 28227
 3: 17769
 4: 14605
 5: 50093
10: 25452
15: 15880
20: 13169

The result is pretty precise in my opinion.

So, my question is: how can I increase the performance of this code?

\$\endgroup\$
  • 1
    \$\begingroup\$ Don't edit updates or fixes based on Reviews into your question. That invalidates the answer. \$\endgroup\$ – Quill Sep 16 '15 at 7:42
6
\$\begingroup\$

Fatal: Insufficient memory allocation. Buffer is too small by 2 for s[length+1].

char *s = malloc(length);
...
s[length+1] = '\0';  

Minor: long will not necessarily will fit in size_t.

long fsize = ftell(f);
...
char *file_contents = malloc(fsize+1);

Wrong specifier. I'd expect a good compiler with properly enabled warnings would flag this.

unsigned long iterations = 0;
...
printf("%llu iterations\n", iterations);

Suggest checking code for correctness and re-submit.

\$\endgroup\$
3
\$\begingroup\$

Unnecessary string copies

Your function str_copy() makes a copy of a substring. But you use it to make a temporary copy of part of the file and then free it right away. You could just avoid making the copy and use the file buffer directly. For example:

                compare_string = str_copy(file_contents, k, i);
                if (strcmp(test_string, compare_string) == 0) {
                    // ...
                }
                free(compare_string);

could be:

                if (strncmp(test_string, file_contents+k, i) == 0) {
                    // ...
                }

Stack overflow

You declare this dynamically sized array:

char strings[arr_str_count][arr_str_length];

This array could easily overflow the stack since arr_str_count is the size of your file in bytes.

Also, as with the previous point, I really don't think you need to make copies of the substrings that you find. You could instead have an array of offsets into the file buffer. That way you don't need to make copies of all your strings.

No error checks

The first time I ran your program, it segfaulted because I didn't have a file named "cipher.txt". Your program is lacking any sort of error checks for the results of malloc(), fopen(), etc.

Unused code

count_factors() and factors_index are unused. They should be deleted.

\$\endgroup\$
3
\$\begingroup\$

Alright, I have quite a lot to say about this code. First of all, I tried compiling with GCC and it instantly threw an error as it couldn't find conio.h (I'm guessing this is some Windows only header file). I then removed the #include <conio.h> line and changed getch() to getchar() (Again, I assume this is what conio.h was for), and then it compiled successfully but gave 4 warnings.

First of all, you never actually use the variable factors_index, so you should remove it. Secondly, there are 3 sections where you used printf() incorrectly. Twice in line 99 where you used %d instead of %ul as the variable is an unsigned long and not an int, and again in line 102 where you used %ull instead of %ul. Having corrected these, it compiled with no warnings.

Now onto everything the compiler didn't spot.

It assumes nothing it does fails

There are several places in your code where you use functions that can easily fail, and if they do, will cause a SIG_SEGV (Access Violation to you Windows folk). You always need to add error handling for things like this. For example, in the function f_get_contents(), you make a call to fopen. If, for example, the file cipher.txt was not in the current directory fopen would return NULL which would cause the rest of the function to fail as fseek then tries to use the memory at address NULL which is nonsensical. You should instead do something like this:

char *file_get_contents(char *filename, char *fmode) {
    FILE *file;
    if( !(file = fopen(filename, fmode)) ) {
        fprintf(stderr, "Error opening file \"%s\"!\n", file_name);
        exit(-1);
    }
    /*Rest of function goes here...*/
}

You also do the same thing for your fseek and fread calls, as well as your malloc and calloc calls throughout your program. These can all be fixed relatively easily using a similar method as above. Your malloc and calloc calls should look something like:

char *file_contents;
if( !(file_contents = malloc(fsize + 1)) ) {
    fprintf(stderr, "Malloc error!\n");
    exit(-2);
}

Now for a function-by-function review:

f_get_contents()

As I skimmed your code, I noticed that you make quite a few references to the size of the file, calculating it each time with strlen(). I might recommend that this function returns a typedef'd struct containing both the size of the file and its contents to reduce these calls to strlen (not much of a performance boost, mostly just to tidy up the code).

Also, I'm not very familiar with the algorithm you're using but does it really need the whole file contents at the same time? This can cause major issues when trying to access big files, if possible try reading the file in blocks. If this can't be done due to algorithmic constraints, at least keep it in mind for future projects. Not much else to add apart from what I mentioned in the Access Violations section.

str_copy()

I feel like this is a really unnecessary function and you should just use the built-in strn_read instead. It also has some major issues in it. As well as what I mentioned in Access Violations section, you try to reference an address out of the range of your string with s[length + 1] = 0; (As @chux mentioned already). You need to allocate it an extra byte and then use s[length] = 0;.

count_factors()

I̶ ̶s̶u̶s̶p̶e̶c̶t̶ ̶t̶h̶i̶s̶ ̶i̶s̶ ̶p̶a̶r̶t̶ ̶o̶f̶ ̶t̶h̶e̶ ̶m̶a̶i̶n̶ ̶c̶a̶u̶s̶e̶ ̶o̶f̶ ̶y̶o̶u̶r̶ ̶p̶e̶r̶f̶o̶r̶m̶a̶n̶c̶e̶ ̶i̶s̶s̶u̶e̶ ̶h̶e̶r̶e̶. You try and find all the factors of a number up to the number itself. A number will never have an factor of greater than half itself, just change the check in the for loop to i <= number / 2. I suspect this is a choke point for the program because it's using the rather demanding modulo operator (divisions are the most demanding mathematical operation for a computer to perform), and it's doing number/2 tests that will never do anything.

Also, it's good practice to declare your loop variables as (int i = 0;...) when you can, it's cleaner and defines their scope. (Remember to enable c99 mode on your compiler though).

EDIT: I just noticed as @JS1 pointed out you don't actually use this function anywhere, remove it.

main()

Variables

I have a few issues with your variable declarations. Firstly, you have the variables seq_min and seq_max. Theses remain unchanged through the code and are constants. They should be declared before your functions with either an enum or a #define statement such as:

#define SEQ_MIN 3
#define SEQ_MAX 4

Secondly, give your variables better and more descriptive names. I have no idea what i, j, k and f are for but you use them a fair bit.

Thirdly, this is a bit of personal preference but it's also considered good practice to declare your variables before you use them.

Fourthly, is_in_array should be a bool, not a char (You will need to include stdbool.h or it's Windows equivalent though).

Fifth, there is no reason to use calloc instead of malloc when dealing with non char strings.

Finally, you should get rid of the seldom used arr_str_count and arr_string_length, and just use text_len + 1 and SEQ_MAX + 1 as it not only reduces code length but also makes it a bit clearer what's going on.

As for the algorithm itself, there isn't much I can say as I'm unfamiliar with it. I am almost sure that you don't need that many variables though. Try and find ways to remove and reuse them; it makes for much more readable and concise code.

I noticed that you used strcpy() here. You should replace that with strncpy as it requires a buffer size to be given. You also did the same thing I mentioned in count_factor with the factorisation.

Also, could you provide us with a link to your cipher.txt? This would make performance improvements easier to do.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.