//
//  main.c
//  arrtest
//
//  Created by Mattias (hz) Hansson on 9/2/12.
//  Public Domain. Credits/Bugfixes welcome.
//

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <sys/time.h>

/* Return 1 if the difference is negative, otherwise 0.  */
int timeval_subtract(struct timeval *result, struct timeval *t2, struct timeval *t1)
{
    long int diff = (t2->tv_usec + 1000000 * t2->tv_sec) - (t1->tv_usec + 1000000 * t1->tv_sec);
    result->tv_sec = diff / 1000000;
    result->tv_usec = diff % 1000000;

    return (diff<0);
}

unsigned char* buildBitcountLookup(int bits) {
    unsigned long BYTE_SIZE = powl(2, bits);
    unsigned char* arr = (void*)malloc(BYTE_SIZE);
    memset(arr, 0, BYTE_SIZE-1); //Force preallocation of mem

    unsigned long int i = 0;
    for(; i < BYTE_SIZE; i++) {
        unsigned char bitCount = 0;
        for(unsigned long bitField = i; bitField > 0; bitField = (bitField >> 1)) {
            bitCount += (bitField & 1);
        }
        arr[i] = bitCount;

    }
    return arr;
}

unsigned long int* buildRandomArr(int arrLength) {
    unsigned long ARR_SIZE = arrLength;
    unsigned long BYTE_SIZE = ARR_SIZE * sizeof(unsigned long);
    unsigned long* arr = (void*)malloc(BYTE_SIZE);
    memset(arr, 0, BYTE_SIZE-1); //Force preallocation of mem
    for(int i = 0; i < ARR_SIZE; i++) {
        //test
        //arr[i] =  0xffffffffffffffffL;
        arr[i] = ((((random() & 1) << 31) + random() << 32) | ((random() & 1) << 31) + random());
    }
    return arr;
}

unsigned int bitCountNaive(unsigned long int* testarr, int arrLength) {
    unsigned int bitCount = 0;
    for(int i = 0; i < arrLength; i++) {
        for(unsigned long bitField = testarr[i]; bitField > 0; bitField = (bitField >> 1)) {
            bitCount += (bitField & 1);
        }
    }
    return bitCount;
}

unsigned int bitCountLookup16(unsigned long int* testarr, int arrLength, unsigned char* lookupArr) {
    unsigned int bitCount = 0;
    for(int i = 0; i < arrLength; i++) {
        unsigned long int val = testarr[i];
        bitCount += lookupArr[(val & 0xffff000000000000L) >> 48] +
                    lookupArr[(val & 0xffff00000000L) >> 32]     +
                    lookupArr[(val & 0xffff0000L) >> 16]         +
                    lookupArr[(val & 0xffffL)];
    }
    return bitCount;
}

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

    const unsigned long int LOOPS = 10000;
    unsigned char* lookupArr = buildBitcountLookup(16);
    srandomdev(); //init random
    unsigned long* testarr = buildRandomArr(10000);
    struct timeval tvBegin, tvEnd, tvDiff;

    unsigned long int totalBitCount = 0;
    //-------------------------------------
    printf("Naive approach:\n");
    gettimeofday(&tvBegin, NULL);
    totalBitCount = 0;
    for (int i = 0; i < LOOPS; i++) {
        //printf("bitCountNaive = %d\n", bitCountNaive(testarr, 10000));
        totalBitCount += bitCountNaive(testarr, 10000);
    }
    printf("Total %ld bits gives %d avg. bits over %ld iterations.\n", totalBitCount, (int)(totalBitCount/LOOPS), LOOPS);
    gettimeofday(&tvEnd, NULL);
    timeval_subtract(&tvDiff, &tvEnd, &tvBegin);
    printf("%ld.%06d seconds.\n", tvDiff.tv_sec, tvDiff.tv_usec);

    //-------------------------------------
    printf("Lookup 16 bit approach:\n");
    gettimeofday(&tvBegin, NULL);
    totalBitCount = 0;
    for (int i = 0; i < LOOPS; i++) {
        //printf("bitCountNaive = %d\n", bitCountNaive(testarr, 10000));
        totalBitCount += bitCountLookup16(testarr, 10000, lookupArr);
    }
    printf("Total %ld bits gives %d avg. bits over %ld iterations.\n", totalBitCount, (int)(totalBitCount/LOOPS), LOOPS);
    gettimeofday(&tvEnd, NULL);
    timeval_subtract(&tvDiff, &tvEnd, &tvBegin);
    printf("%ld.%06d seconds.\n", tvDiff.tv_sec, tvDiff.tv_usec);

    free(testarr);
    free(lookupArr);
    printf("done.\n");
    return 0;
}