// Arup Guha
// 11/12/2014
// Hash Function for CIS 3362 Homework #5D:
// Find two different strings that map to the same hash value.

// Edited on 11/17/2014 to add hashmap like capability - specific to the assignment.

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

#define MAX 20
#define TABLESIZE  1000003

// Structs for hash function.
typedef struct node {
    char word[MAX];
    int realHash;
    struct node* next;
} Node;

typedef struct hashmap {
    Node** table;
} HashMap;

// Functions to support the hash function.
int hashFunction(char input[]);
int f(int value);
int reverse(int value);
int box(int value);
int box2(int value);
int f2(int value);

// Functions to support the special hash map.
void initHashMap(HashMap* ptrMap);
char* insert(HashMap* ptrMap, char newword[]);
void freeHashMap(HashMap* ptrMap);
void freeList(Node* front);

int main() {
    return 0;
}

// Pre-condition: input must be null terminated.
int hashFunction(char input[]) {

    int i = 0, n = strlen(input);
    int buffer = 832671294;
    while (i < n) {
        int temp = 0, j;
        for (j=0; j<4 && i+j<n; j++)
            temp +=  ( (f((int)input[i+j])) << (24-8*j));
        i += 4;

        buffer = f2(buffer ^ temp);
    }
    return buffer;
}

// value must be 8 bits. Swaps the left and the right halves and runs
// each through an s-box.
int f(int value) {
    value = reverse(value);
    int left = (value & (0xf0)) >> 4;
    int right = value & (0xf);
    return (box(left) << 4) + box(right);
}

// value must be 8 bits. It's reverse (in binary) is returned.
int reverse(int value) {
    int ans = 0, i;
    for (i=0; i<8; i++) {
        ans = (ans << 1) + (value & 1);
        value = value >> 1;
    }
    return ans;
}

// Random s-box of values.
int box(int value) {
    int ans[] = {9, 4, 15, 0, 6, 7, 2, 11, 13, 12, 3, 8, 14, 1, 10 ,5};
    return ans[value];
}

// A second random s-box of values.
int box2(int value) {
    int ans[] = {13, 6, 2, 14, 7, 10, 4, 5, 0, 9, 12, 3, 15, 8, 11, 1};
    return ans[value];
}

// A second function based on the sbox. Value is once again reversed, with
// another substitution into a different sbox.
int f2(int value) {
    int i, ans = 0;
    for (i=0; i<8; i++) {
        int index = value & 0xf;
        if (index < 0) index += 16;
        ans = (ans << 4)  + box2(index);
        value = value >> 4;
    }
    return ans;
}

/********************* HASH MAP CODE HERE **************************/

void initHashMap(HashMap* ptrMap) {
    ptrMap->table = malloc(TABLESIZE*sizeof(Node*));
    int i;

    // All linked lists start at null.
    for (i=0; i<TABLESIZE; i++)
        ptrMap->table[i] = NULL;
}

char* insert(HashMap* ptrMap, char newword[]) {

    // Make node for new word.
    Node* tmp = malloc(sizeof(Node));
    strcpy(tmp->word, newword);
    tmp->realHash = hashFunction(newword);

    // Insert this new node into the list.
    int mappedHash = abs(tmp->realHash)%TABLESIZE;
    tmp->next = ptrMap->table[mappedHash];
    ptrMap->table[mappedHash] = tmp;

    // Look for another word in this list with the same real hash value.
    // This is why we start with the second node in the list...
    Node* nPtr;
    for (nPtr=ptrMap->table[mappedHash]->next; nPtr != NULL; nPtr = nPtr->next) {
        if (nPtr->realHash == tmp->realHash) {
            char* ans = malloc(sizeof(char)*MAX);
            strcpy(ans, nPtr->word);
            return ans;
        }
    }

    // No match found.
    return NULL;
}

// Frees the memory for the hash map.
void freeHashMap(HashMap* ptrMap) {

    // Free all linked lists.
    int i;
    for (i=0; i<TABLESIZE; i++)
        freeList(ptrMap->table[i]);

    // Free the array.
    free(ptrMap->table);
}

// Frees the linked list pointed to by front.
void freeList(Node* front) {
    if (front == NULL) return;
    Node* second = front->next;
    free(front);
    freeList(second);
}