bdz rev 1.0

# -*- coding: utf-8 -*-
import math
import sympy
import numpy
import itertools


def Frequency_Monobits_Test (data):
    amount=0
    count=0
    if data == 0:
        amount=count=1
    while data != 0:
        a = data & 1
        if a == 0:
            a = -1
        data = data >> 1
        count+=1
        amount += a

    static = abs(amount)/math.sqrt(count)/math.sqrt(2)

    #erfc = (2/math.sqrt(math.pi))*(sympy.integrate(sympy.exp(-sympy.Symbol('x')**2),(sympy.Symbol('x'),static,sympy.Symbol('oo'))))
    return math.erfc(static)

def Compare(value):
    p = 0.01
    if  value < p:
        print 'Ю񫥤򥫼򼠭塿㬿泱��󷠩.'
    elif value == 0xff :
        print 'ӥ񲠭塬痢򠡻򼠢󯮫.'
    else:
        print 'ñ塎ʮ'



def Frequency_Block_Test (data, data_len):
    blocks = []
    s = []
    mult = 1
    x = 0
    while data_len != 0:
        if data_len < 3:
            data <<= (3 - data_len)
            data_len = 3

        blocks.append(data >> (data_len - 3))
        data_len -= 3
        if data_len==1 and (data==0 or data==1):
            mult=1
        else:
            while x < data_len-1:
                mult = mult << 1
                mult += 1
                x += 1
            data = data & mult
            x,mult=0,1
    if blocks[len(blocks) - 1] == 0:
        del blocks[len(blocks) - 1]


    for item in blocks:
        s.append ((float(((item&0b1)+((item&0b10)>>0b1)+((item&0b100)>>0b10)))/3-0.5)**2)
    #print 12*(sum (s))
    #print math.gamma(float(len(blocks))/2)
    return sympy.uppergamma(float(len(blocks))/2,(sum (s))*6)
def Same_In_Row_Test(data, data_len):
        temp_data = data
        count_1 = 0
        arg = 0
        p = 0
        v = 0

        while (data != 0):
                if data % 2 == 1:
                        count_1 += 1
                data /= 2

        p = float(count_1) / data_len

        if abs(p - 0.5) < 2 / math.sqrt(data_len):
                while temp_data != 1:
                        if temp_data % 2 != (temp_data % 4)>>1:
                                v += 1

                        temp_data /= 2
        v += 1
        try:
            arg = abs(v - 2*data_len*p*(1 - p))/(2*math.sqrt(2*data_len)*p*(1-p))
            result = math.erfc(arg)
        except ZeroDivisionError:
            result = 0xff
        return result
def Test_For_The_Longest_Run_Of_Ones (data, data_len):
    if data_len <= 128:
        M, K, R = 8, 3, 16
        blocks_len4stat = [1, 2, 3, 4]
        p = [0.2148, 0.3672, 0.2305, 0.1875]
    elif data_len <= 6272:
        M, K, R = 128, 5, 49
        blocks_len4stat = [4, 5, 6, 7, 8, 9]
        p = [0.1174, 0.2430, 0.2493, 0.1752, 0.1027, 0.1124]
    else:
        M, K, R = 10000, 6, 75
        blocks_len4stat = [10, 11, 12, 13, 14, 15, 16]
        p = [0.0228, 0.2092, 0.2483, 0.1933, 0.1208, 0.0675, 0.0727]

    # Разбиение последовательности на блоки
    blocks = []
    count_seq_len = []
    ind = 0
    while data_len > 0:
        blocks.append(str(bin((data % ( 2 ** M)))))
        data /= 2 ** M
        data_len -= M
        if (len(blocks[ind]) != M + 2):
            temp = len(blocks[ind])
            for i in range (M + 2 - temp):
                blocks[ind] += '0'
        ind += 1

    # Вычисление максимальной последовательности единиц для каждого блока
    length = 0

    for j in range(0, len(blocks)):
        length_max = 0

        for i in range(0, M+2):
            if blocks[j][i] == '1':
                length += 1

            if blocks[j][i] == '0' or i == M+1:
                if length > length_max:
                    length_max = length
                length = 0

        # Добавление длины последовательности в list
        count_seq_len.append(length_max)

    # Вычисление статистики
    stat = [0, 0, 0, 0, 0, 0, 0]

    for i in range(len(blocks_len4stat)):
        for item in count_seq_len:
            if item < blocks_len4stat[0]:
                stat[0] += 1
            elif item == blocks_len4stat[i]:
                stat[i] += 1
            elif item > blocks_len4stat[len(blocks_len4stat) - 1]:
                stat[len(blocks_len4stat) - 1] += 1

    # Вычисление Хи-квадрата
    xi = 0
    for i in range(0, K + 1):
        xi += ((stat[i] - R * p[i]) ** 2) / (R * p[i])

    result = sympy.uppergamma(float(K)/2, float(xi)/2)
    return result / sympy.gamma(float(K)/2) #ИСПРАВЛЕНО: igamc = uppergamma(a,x)/gamma(a)

def Binary_Matrix_Rank_Test (data, data_len):
    M = Q = 3
    # Число матриц
    N = data_len / (M * Q)
    pm = [0.2888, 0.5776, 0.1284, 0.005, 0]

    matrix = []
    matrix_rank = []
    fm = []

    data = data >> (data_len % (M * Q))
    for i in range(N):
        array = []
        x = data % (2 ** (M * Q))
        data >>= (M * Q)
        data_len -= M * Q

        for j in range (M * Q):
            array.append(x % 2)
            x /= 2
        matrix.append(sympy.Matrix(M, Q, array))

        matrix_rank.append(matrix[i].rank())

    for i in range(M + 1):
        fm.append(0)

    for rank in matrix_rank:
        fm[rank] += 1

    p = 0.005
    for i in range(0, M + 1):
        if i == M:
            p = pm[0]
        elif i == M - 1:
            p = pm[1]
        elif i == M - 2:
            p = pm[2]
        elif i == M - 3:
            p = pm[3]

        fm[i] = float(((fm[i] - N * p) ** 2)) / (N * p)

    xi = 0
    xi = sum(fm)

    result = sympy.uppergamma(1, float(xi)/2)
    return result
def Spectral_Test(data, data_len):
    run =[]
    run2=[]
    four=[]
    while data != 0:
        a = data & 1
        if a == 0:
            a = -1
        data = data >> 1
        run.append(a)
    run2 = run[::-1]
    four = abs(numpy.fft.fft(run2))
    T=math.sqrt((math.log(1/0.05))*data_len)


    N0=0.95*datalen/2
    N1=math.floor(N0)
    d=float(N1-N0)/math.sqrt(float(data_len*0.95*0.05)/4)
    result = sympy.erfc(float(abs(d))/math.sqrt(2))

    for item in range(data_len/2):
        if four[item]>T:
            result=0xff
    return result


def BerkelampMassey (arr):
    N = len(arr)
    b = []
    c = []
    t = []
    b[0:N] = itertools.repeat(0, N)
    b[0]=1
    c[0:N] = b[0:N]
    t[0:N] = itertools.repeat(0, N)
    l = 0
    m = -1
    for n in range(N):
        d = 0
        for i in range(l+1):
            d ^= c[i] * arr[n-i]
        if d==1:
            c[0:N] = t[0:N]
            N_M = n - m
            for j in range(N-N_M):
                c[N_M+j] ^= b[j]
            if l <= n/2:
                l = n + 1 - l
                m = n
                t[0:N] = b[0:N]
    return l

def chi2c(v, p, nn):
    return (v - nn*p)^2/nn/p

def LinearComplexity(datanum, block_len, data_len):
    data = map((lambda x : int (x=='1')), bin(datanum)[2:])
    for z in range(len(data), datalen):
        data.insert(0,0)
    mu = block_len/2.0 + (9 + ((block_len %2)*2 - 1))/36.0 - (block_len/3.0 + 2/9.0)/2**block_len
    pii = [ 0.010417, 0.03125, 0.125, 0.5, 0.25, 0.0625, 0.020833]
    v = []
    N = 0
    v[0:7] = itertools.repeat(0, 7)
    for z in range(0, data_len, block_len):
        block = []
        block[0:block_len] = data[z:z+block_len]
        Li = BerkelampMassey(block)
        Ti = (1 - (block_len%2)*2) * (Li - mu) + 2/9.0
        ind = math.ceil(Ti+2.5)
        if (ind <= 0):
            v[0] += 1
        elif (ind >= 6):
            v[6] += 1
        else:
            v[int(ind)] += 1
        N += 1
    chi2 = sum(map (chi2c, v, pii, itertools.repeat(N, 7)))
    return sympy.uppergamma(3.0, chi2/2)/2.0 #gamma(3) = 2! = 2

def ApproximateEntropy(datanum, datalen, blocklen):
    data = map((lambda x : int (x=='1')), bin(datanum)[2:])
    for z in range(len(data), datalen):
        data.insert(0,0)
    data.extend(data[0:blocklen-1])
    C = []
    C[0:2**blocklen] = itertools.repeat(0, 2**blocklen)
    for j in range(datalen):
        k = data[j:j+blocklen]
        i = sum(map((lambda x, y: x* 2**y), k, range(blocklen-1,-1,-1)))
        C[i] += 1
    phim = sum(map(lambda p: p * math.log(p) ,filter(lambda k: k!=0, map(lambda x: float(x)/datalen, C))))
    data.append(data[blocklen])
    C = []
    C[0:2*2**blocklen] = itertools.repeat(0, 2*2**blocklen)
    for j in range(datalen):
        k = data[j:j+blocklen+1]
        i = sum(map((lambda x, y: x* 2**y), k, range(blocklen,-1,-1)))
        C[i] += 1
    phimp1 = sum(map(lambda p: p * math.log(p) ,filter(lambda k: k!=0, map(lambda x: float(x)/datalen, C))))
    ApEn = phim - phimp1
    chi2 = 2*datalen*(math.log(2)-ApEn)
    return sympy.uppergamma(2**(blocklen-1), chi2/2) / sympy.gamma(2**(blocklen-1))


def cdf(x):
    return (1.0 + math.erf(x / math.sqrt(2.0))) / 2.0

def Cusum(data, datalen, mode):
    X = map((lambda x : 2*int(x=='1')-1), bin(data)[2:])
    for z in range(len(X), datalen):
        X.insert(0, -1)
    if mode:
        X.reverse()
    z = 0
    for j in range(datalen):
        si = reduce(lambda x,y: x+y, X[:j+1])
        if (abs(si)>z): z=abs(si)
    n = datalen
    s1 = reduce(lambda s, k: s + cdf((((4*k+1)*z)/math.sqrt(n))) - cdf(((4*k-1)*z)/math.sqrt(n)), range(int((-n/z+1)/4), 1+((n/z-1)/4)), 0)
    s2 = reduce(lambda s, k: s + cdf((((4*k+3)*z)/math.sqrt(n))) - cdf(((4*k+1)*z)/math.sqrt(n)), range(int((-n/z-3)/4), 1+((n/z-1)/4)), 0)
    return 1.0 - s1 + s2


def RandomWalk(data, datalen):
    X = map((lambda x : 2*int(x=='1')-1), bin(data)[2:])
    for z in range(len(X), datalen):
        X.insert(0, -1)
    S = list(range(datalen))
    P = dict()
    for j in range(datalen):
        S[j] = reduce(lambda x,y: x+y, X[:j+1])
    J = S.count(0) + 1
    for r in range(9):
        xi = S.count(-1-r)
        P[-1-r] = math.erfc(abs(xi - J)/(2*J*(4*abs(-1-r)-2))**0.5)
        xi = S.count(1+r)
        P[1+r] = math.erfc(abs(xi - J)/(2*J*(4*abs(1+r)-2))**0.5)
    return P






seq = input("Enter data:")
datalen = input("Enter len:")
temp = Frequency_Monobits_Test(seq)
#print temp
Compare(temp)
temp=Frequency_Block_Test(seq, datalen)
Compare(temp)
temp=Same_In_Row_Test(seq, datalen)
Compare(temp)
temp=Test_For_The_Longest_Run_Of_Ones (seq, datalen)
Compare(temp)
temp=Binary_Matrix_Rank_Test(seq, datalen)
Compare(temp)
temp=Spectral_Test(seq, datalen)
Compare(temp)
# проверки напрямую тут я прикручивать не стал, ибо нужен ещё размер блока
# Заметь, что RandomWalk возвращает dict с ключами -9..-1, 1..9 и значениями соответствующих P.