""" ciphertools.py
    c odenthal
    2005/05/30

    This module contains some cryptanalysis functions.
"""

from __future__ import division

import counts, stringtools, datatools

def kappa(T1,T2):
    """ Computes the 'Incidence of Coincidence' for the two
        strings 'T1' and 'T2'. That is, we count the number
        of positions where 'T1' and 'T2' have the same character,
        and then we divide by the length of the shortest string.
    """
    zLst = zip(T1,T2)
    M = len(zLst)
    match = lambda (x,y) : x==y
    mLst = filter(match,zLst)
    return len(mLst)/M

def phi(T):
    """ Computes phi(T) for the string 'T'. This is defined as
            phi(T) = sum_{1:26} (m_i)(m_i - 1)/(M(M-1))
        where M is the number of letters in T, and m_i is the
        number of occurences of the ith letter in T.
    """
    # Get a dictionary containing the letter freqencies in 'T'.
    # Non alphabetic characters are ignored.
    freqDct = stringtools.letterFreq(T)

    # Get to total number of letters in 'T'.
    M  = sum(freqDct.values())

    # Compute the summands in the numerator.
    fL = [ m*(m-1) for m in freqDct.values() ]

    # Get the sum and compute 'phi'.
    return sum(fL)/(M*(M-1))

def chi(T1,T2):
    """ Computes chi(T1,T2) for the two strings 'T1' and 'T2'.
        This is defined as
            chi(T,T') = sum_{1:26} p_i p_i'
        where p_i is the probability of the occurence of the
        ith letter in T. Similarly for T' and p_i'.
    """
    # Get the dictionaries with keys the uppercase letters and
    # values the probabilities p_i.
    pD1 = stringtools.letterProb(T1)
    pD2 = stringtools.letterProb(T2)

    # Form the list of probability products p_i p_i'
    ppL = [ p*pD2.get(k,0) for (k,p) in pD1.items() ]

    # Form the sum
    return sum(ppL)

def psi(T):
    """ Computes psi(T)=chi(T,T).
    """
    return chi(T,T)

def chiStandard(T):
    """ Computes chi(T,S) for the string 'T' and the standard
        English alphabet 'S'. This is defined as
            chi(T,T') = sum_{1:26} p_i p_i'
        where p_i is the probability of the occurence of the
        ith letter in T. Similarly for S and p_i'.
    """
    # Get the dictionaries with keys the uppercase letters and
    # values the probabilities p_i.
    pD1 = stringtools.letterProb(T)
    pD2 = counts.englishLetterProb

    # Form the list of probability products p_i p_i'
    ppL = [ p*pD2.get(k,0) for (k,p) in pD1.items() ]

    # Form the sum
    return sum(ppL)

def kappaTest(T,k):
    """ Computes kappa(T,T') where T' is T shifted left k spaces.
    """
    return kappa(T,T[k:]+T[:k])

def chiTest(T,k):
    """ Computes chi(T,T') where T' is obtained from T by shifting
        the alphabet of T left k spaces.
    """
    pD  = stringtools.letterProb(T)
    for c in stringtools.UPPERCASE:
        pD.setdefault(c,0)
    pL1 = datatools.sortByValue(pD)
    pL2 = pL1[k:] + pL1[:k]

    pL1 = [p for (k,p) in pL1]
    pL2 = [p for (k,p) in pL2]

    ppL = [p*q for (p,q) in zip(pL1,pL2)]

    return sum(ppL)

def phiTest(T1,T2):
    """ Computes phi(T) where T is the sum of T1 and T2.
    """
    return phi(T1+T2)

def phiAvg(TLst):
    """ Computes the average of phi(T) for T in TLst
    """
    phiLst = map(phi,TLst)
    return sum(phiLst)/len(phiLst)

def testKasiski(T,k):
    """ Finds repeated patterns in T.
    """
    M=len(T)
    for i in range(M-k):
        s = T[i:i+k]
        if T.count(s)>1:
            print i,s