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


typedef struct {
    char* contents;
    int length;
} Buffer;

Buffer* readFile(const char* filename) {
    FILE *fileptr;
    char *buffer;
    long filelen;

    fileptr = fopen(filename, "rb");        // Open the file in binary mode
    fseek(fileptr, 0, SEEK_END);            // Jump to the end of the file
    filelen = ftell(fileptr);               // Get the current byte offset in the file
    rewind(fileptr);                        // Jump back to the beginning of the file

    buffer = (char *)malloc((filelen)*sizeof(char)); // Enough memory for file
    fread(buffer, filelen, 1, fileptr);     // Read in the entire file
    fclose(fileptr);                        // Close the file

    Buffer *ret = malloc(sizeof(Buffer));
    ret->length = filelen;
    ret->contents = buffer;
    return ret;
}

const int DESC_BITS = 512;
const int DESC_BYTES = DESC_BITS / 8;
static int DESC_INTS = DESC_BYTES / sizeof(unsigned);  // 512 bits: as integers, so we can use popcnt
const int THRESH = 50;

int descriptorDistance(unsigned* a, unsigned* b) {
    int sumBits = 0;
    unsigned compare = 0;
    int i;
    for (i=0; i<DESC_INTS; i++) {
        compare = a[i]^b[i];
        sumBits += __builtin_popcount(compare);
    }

    return sumBits;
}

int main (int argc, char * argv[]) {

    Buffer *haystack = readFile("haystack");
    Buffer *needleImage = readFile("needle_image_descriptors");

    uint64_t position = 0;
    uint16_t *pNumImages = (uint16_t*)&haystack->contents[position];
    uint16_t numImages = *pNumImages;
    printf("images in haystack: %i\n\n", numImages);

    Buffer **allHaystack = (Buffer**)malloc(haystack->length*sizeof(Buffer*));

    position += 2;
    int i;
    for(i=0; i<numImages; i++)  {
        uint16_t *pNumDescriptors = (uint16_t*)&haystack->contents[position];
        uint16_t numDescriptors = *pNumDescriptors;
        position += 2;

        Buffer *descriptors = (Buffer*)malloc(numDescriptors * sizeof(Buffer));
        descriptors->length = numDescriptors * DESC_BYTES;
        descriptors->contents = (char *)malloc((descriptors->length)*sizeof(char));
        memcpy(descriptors->contents, &haystack->contents[position], descriptors->length);

        allHaystack[i] = descriptors;

        position += numDescriptors * DESC_BYTES;
    }

    printf("Starting comparison\n");

    int k,j;
    unsigned distance = 0;
    int matches = 0;
    int step = DESC_INTS * sizeof(int);
    Buffer *haystackImage;
    unsigned* haystackDescriptor;

    for(k=0; k<numImages; k++) {

        haystackImage = allHaystack[k];
        //printf("Comparing to image %i (%i descriptors)\n", k, haystackImage->length / DESC_BYTES);
        matches = 0;

        for(i=0; i<haystackImage->length; i+=step)  {

            haystackDescriptor = (unsigned *)&haystackImage->contents[i];

            for(j=0; j<needleImage->length; j+=step) {
                distance = descriptorDistance(haystackDescriptor, (unsigned *)&needleImage->contents[j]);
                if (distance < THRESH) {
                    matches++;
                }
            }
        }

        if (matches > 3) {
            printf("Image match found: %i (%i matches)\n", k, matches);
        }
    }

    return 0;
}