# A somewhat efficient collision table implementation

Here is a bit of code implementing the generalized birthday attack, that maybe some might find useful. I am not an incredibly proficient C-programmer and I have not checked for memory leaks in this code, since my computer does not have Valgrind (but at least #frees = #mallocs!). Nonetheless, it seems pretty fast on even larger instances.

It can be use as basis when implementing various algorithm such as Stern’s algorithm or the BKW algorithm.

If you find errors or improvements, feel free to post it in the comments.

```////////////////////////////////////////////////////////////////////////////////
//      Carl Löndahl, 2013
//        www.grocid.net
////////////////////////////////////////////////////////////////////////////////

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <inttypes.h>

#define BITS_IN_WORD				5
#define TOTAL_ELEMENT_LENGTH 		10
#define NUMBER_OF_ELEMENTS_IN_BLOCK 32
#define NUMBER_OF_BLOCKS			(1<<BITS_IN_WORD)
#define ITERATIONS					4

////////////////////////////////////////////////////////////////////////////////////////////

typedef struct element {

uint64_t	content[TOTAL_ELEMENT_LENGTH];

} element_t;

inline void print_binary(uint64_t word) {

uint32_t	s;

for (s = 0; s < BITS_IN_WORD; ++s)
printf("%d", (uint8_t)((word>>(BITS_IN_WORD-1-s)) & 1));
printf(" ");

}

inline void random_fill(element_t *target) {

uint32_t	s;

for (s = 0; s < TOTAL_ELEMENT_LENGTH; ++s) {
}
}

////////////////////////////////////////////////////////////////////////////////////////////

int main (int argc, char const *argv[])
{
// counting variables
uint32_t	s, t, q, p;

// indexing_block gives which element block should index the element
uint32_t	indexing_block = 0, to_table, from_table, block_size;
uint64_t	index;
element_t 	*block[2], *target_block, *from_block;

// to keep track of the number of elements in each block
uint32_t  	occupied[2][NUMBER_OF_BLOCKS];
uint32_t  	block_index[NUMBER_OF_BLOCKS];
uint32_t	target_occupied;

// allocate the blocks from which we iterate back-and-forth ))<>((
block[0] = malloc(NUMBER_OF_BLOCKS*NUMBER_OF_ELEMENTS_IN_BLOCK*sizeof(element_t));
block[1] = malloc(NUMBER_OF_BLOCKS*NUMBER_OF_ELEMENTS_IN_BLOCK*sizeof(element_t));

// cache offsets and init+reset sizes
for(s = 0; s < NUMBER_OF_BLOCKS; ++s) {
block_index[s] = NUMBER_OF_ELEMENTS_IN_BLOCK*s;
occupied[0][s] = NUMBER_OF_ELEMENTS_IN_BLOCK;
occupied[1][s] = 0;
}

// fill storage with (truly) random junk
for(s = 0; s < NUMBER_OF_BLOCKS*NUMBER_OF_ELEMENTS_IN_BLOCK; ++s) {
random_fill(block[0]+s);
}

////////////////////////////////////////////////////////////////////////////////////////////

// perform this [ITERATIONS] many times.
for (indexing_block = 0; indexing_block < ITERATIONS; ++indexing_block) {

// determine which block to be the target block
to_table = (indexing_block & 1) ^ 1;
from_table = (indexing_block & 1);

// for each block in the table
for (p = 0; p < NUMBER_OF_BLOCKS; ++p) {

from_block = block[from_table] + block_index[p];
block_size = occupied[from_table][p];

// add all pairs in block
for (s = 0; s < block_size; ++s) {
for (t = s + 1; t < block_size; ++t) {

// determine the target block
index = from_block[s].content[indexing_block] ^ from_block[t].content[indexing_block];

// if there is free place in the target
if (occupied[to_table][index] < NUMBER_OF_ELEMENTS_IN_BLOCK) {

target_occupied = occupied[to_table][index];
target_block = block[to_table] + block_index[index];

// put the result of the pair in the target variable
for (q = 0; q < TOTAL_ELEMENT_LENGTH; ++q) {
target_block[target_occupied].content[q] = from_block[s].content[q] ^ from_block[t].content[q];
}

// note the increase of elements
occupied[to_table][index]++;
}
}
}
}

// reset the from-block sizes
for(s = 0; s < NUMBER_OF_BLOCKS; ++s) {
occupied[from_table][s] = 0;
}

}

////////////////////////////////////////////////////////////////////////////////////////////

free(block[0]);
free(block[1]);

return 0;
}

```