#include <stdio.h>
#include <string.h>
#include <math.h>

#define BUFSIZE 5120
#define MAX_KEYLEN ( BUFSIZE / 100 )
#define LANGUAGE_ENTROPY 4.08
#define ENTROPY_TOL 0.1
#define MOST_FREQ_CHAR 'E'

const unsigned int num_letters = 'Z' - 'A' + 1;

void decrypt(char* text, const char* key) {
    const char* c = key;
    while(*text) {
        // encrpypt
        int shift = (*text - 'A') - (*c - 'A');
        if (shift < 0) shift += num_letters;
        *text = 'A' + shift ;
        
        // increase pointers
        ++c;
        if (*c == '\0') {
            c = key; // reset c at end of keyword
        }
        ++text;
    }
}

void freq_analysis(double p[], const char* t, int strlen_t, int shift, int offset) {
    // p is array with num_letters elements
    // initialize p
    for (int i = 0; i < num_letters; ++i) {
        p[i] = 0;
    }
    // compute absolute frequency
    t += offset;
    for (int i = offset; i <= strlen_t; i += shift, t += shift) {
        ++(p[*t - 'A']); 
    }
    // compute relative frequency from absolute
    for (int i = 0; i < num_letters; ++i) {
        p[i] /= strlen_t / shift;
    }
}

double shannon_entropy(double p[]) {
    double ret = 0;
    for (int i = 0; i < num_letters; ++i) {
        if (p[i]) {
            ret -= p[i] * log(p[i]) / log(2);
        }
    }
    return ret;
}

unsigned int most_frequent_idx(double p[]) {
    int ret = 0; 
    for (int i = 1; i < num_letters; ++i) {
        if (p[i] > p[ret]) ret = i;
    }
    return ret;
}

int main() {
    char text[BUFSIZE + 1];
    unsigned int len = 0;
    char c;
    // fill text-buffer
    while (len < BUFSIZE && (c = getchar()) != EOF) {
        if (c >= 'A' && c <= 'Z') {
            text[len++] = c; 
        }
    }
    // terminate string with nullbyte
    text[len] = '\0'; 
    
    // determin key length
    char key[MAX_KEYLEN + 1];
    double p[num_letters];
    int keylen = 1;
    double entropy = 0;
    for (; keylen <= MAX_KEYLEN; ++keylen) {
        // perform frequency analysis
        freq_analysis(p, text, len, keylen, 0);
        // If Shannon entropy is near to natural text entropy,
        entropy = shannon_entropy(p);
        printf("Entropy for key length %d is %f.\n", keylen, entropy);
        if (entropy < LANGUAGE_ENTROPY + ENTROPY_TOL) {
            // we have found a matching key length.
            break;
        }
    }
    
    printf("Key lenth is %d\n",keylen);
    
    key[keylen] = '\0'; //terminate string

    for (int i = 0; i < keylen; ++i) {
        freq_analysis(p, text, len, keylen, i);
        int shift = most_frequent_idx(p) - (MOST_FREQ_CHAR -'A');
        if (shift < 0) shift += num_letters;
        key[i] = 'A' + shift;
    }
    
    printf("Key: %s\n",key);
    decrypt(text, key);
    printf("Entschluesselt: %s\n", text);
}