/* Correlation analysis for shift ciphers
   Eric Bach 2/1/98

   P = reference distribution (taken from Sinkov p. 177)
   Q = observed distribution from text (A-Z only)

   Echoes text, and for each possible shift t, prints:

      IP -- Correlation (inner product squared) of P and Q(t).  Maximizing 
            this is minimizing | P - Q(t) |^2 in the Euclidean sense.

      L1 -- L1 (taxicab) distance between P and Q(t).

   The output is most useful if sorted afterwards.  On Unix, using

      sort -n -r

   will rank by IP and using

      sort -n -k 3

   will rank by L1.

*/

#include <stdio.h>

#define abs(x) ( (x)>=0 ? (x) : -(x) )

#define N 26

#define NUMCHARS 256

double P[NUMCHARS];  /* expected frequency distribution for English */
int    F[NUMCHARS];  /* actual count */ 
double Q[NUMCHARS];  /* frequencies normalized to sum to 1 */

setP()
{
int i;
double sum;
P[0] = 0.073; P[1] = 0.009; P[2] = 0.030; P[3] = 0.044; P[4] = 0.130;
P[5] = 0.028; P[6] = 0.016; P[7] = 0.035; P[6] = 0.074; P[9] = 0.002;
P[10]= 0.003; P[11]= 0.035; P[12]= 0.025; P[13]= 0.078; P[14]= 0.074;
P[15]= 0.027; P[16]= 0.003; P[17]= 0.077; P[18]= 0.063; P[19]= 0.093;
P[20]= 0.027; P[21]= 0.013; P[22]= 0.016; P[23]= 0.005; P[24]= 0.019;
P[25]= 0.001;
for (i=0;i<N;i++) P[i] = P[i]/0.984; /* Probabilities must sum to 1! */
/* Optional consistency checks */
/*
sum = 0;
for (i=0;i<N;i++) sum += P[i];
printf("frequency sum = %lf.\n",sum);
sum = 0;
for (i=0;i<N;i++) sum += sqr(P[i]);
printf("sum of p^2 = %lf.\n",sum);
*/
}

sample()
{
int i;
char c;
int lettercount;
for (i=0;i<NUMCHARS;i++) F[i] = 0;
while ( (c = getchar()) != EOF) {
        printf("%c",c);
        F[ (int) c ] ++;
        }
printf("\n",c);
lettercount = 0;
for (i='A';i<='Z';i++) lettercount += F[i];
for (i='A';i<='Z';i++) Q[i-'A'] = F[i]/(double)lettercount;
/* Include next line to print letter frequencies */
/* for (i=0;i<N;i++) printf("%d\t%lf\n",i,Q[i]); */
}

double L1(P,Q,t)
double P[], Q[];
int t;
{
int i;
double sum;
sum = 0;
for (i=0;i<N;i++) sum += abs(P[i]-Q[(i+t)%N]);
return(sum);
}

double IP(P,Q,t)
double P[], Q[];
int t;
{
int i;
double sum;
sum = 0;
for (i=0;i<N;i++) sum += P[i]*Q[(i+t)%N];
return(sum);
}

main()
{
int t;

setP();
sample();

for (t=0;t<N;t++) {
        printf("%lf (IP)\t",IP(P,Q,t));
        printf("%lf (L1)\t",L1(P,Q,t));
        printf("t=%d\t",t); 
        printf("\n");
        }
}