#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# UPMC - c.durr - 2016
# Conception et Pratique de l'Algorithmique
# experiences avec plusieurs familles de fct de hashage

from heapq     import *
from random    import *
from sys       import *
from math      import *
from ipaddress import *


BITS = 32

def mult(a,b):
    ''' multiplication dans le corps GF[2^{32}]
        http://web.eecs.utk.edu/~plank/plank/papers/CS-07-593/primitive-polynomial-table.txt
    '''
    assert BITS==32
    v = 0
    for _ in range(BITS):
        if b&1:
            v ^= a
        carry = a & (1<<(BITS-1))
        a <<= 1
        if carry:
            a ^= 0o40020000007
        b >>= 1
    return v

class HashfunctionRijndael:
    ''' Carter Wegman appliqué au corps de Galois GF[2^32]
        aussi appelé corps de Rijndael
    '''
    def __init__(self):
        self.a = getrandbits(BITS)
        self.b = getrandbits(BITS)

    def __call__(self, val):
        return mult(self.a, val) ^ self.b

class HashfunctionCarterWegman:
    ''' Carter and Wegman
        p = next prime after 2**32 = 2**32 + 15
        http://www.wolframalpha.com/input/?i=next+prime+after+2**32
        rapide en pratique, mais en temps non limité en pire des cas
    '''
    p = 4294967311

    def __init__(self):
        self.a = []
        self.b = []

    def __call__(self, val):
        # assert type(val) == int and 0 <= val and val < 1<<BITS
        i = 0
        while True:
            if i >= len(self.a):
                self.a.append(randint(0,Hashfunction.p-1))
                self.b.append(randint(0,Hashfunction.p-1))
            h = ((self.a[i]*val + self.b[i]) % Hashfunction.p )
            if h < 1<<BITS:
                return h
            i += 1

class HashfunctionMatrice:
    ''' Matrice binaire
        http://www.cs.cmu.edu/~avrim/Randalgs97/lect0127
    '''

    def __init__(self):
        self.H = [getrandbits(BITS) for _ in range(BITS + 1)]

    def __call__(self, val):
        # assert type(val) == int and 0 <= val and val < 1<<BITS
        v = self.H[-1]    # si v=0, alors la fct est constante 0 sur val=0 !
        for hi in self.H:
            if val & 1 == 1:
                v ^= hi
            val >>= 1
        return v