jdmhash.c

jdmhash.c

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/stat.h>

void printC(unsigned char* c, int size)
{
    for(int i = 0; i < size; i++)
    {
        printf("%02x", c[i]);
    }
    printf("\n");
}


typedef uint64_t ui64;
typedef uint32_t ui32;
typedef uint16_t ui16;

#define grab32(x) *((ui32*)x)
#define grab16(x) *((ui16*)x)

ui32 wrap32Left (ui32 value, unsigned int count) {
    const unsigned int mask = (CHAR_BIT*sizeof(value)-1);
    count &= mask;
    return (value<<count) | (value>>((-count) & mask));
}

ui32 wrap32Right (ui32 value, unsigned int count) {
    const unsigned int mask = (CHAR_BIT*sizeof(value)-1);
    count &= mask;
    return (value>>count) | (value<<((-count) & mask));
}

// My own custom hashing scheme. I think it works rather well.
ui64 jdmhash(char* data, int len, ui64 c)
{
    ui64 hash = 0;
    
    char *overflow = (char*)calloc(7, 1);
    ui32 *a = (ui32*)overflow, *b = (ui32*)(overflow+3); 
    *b = c;

    int left = len & 3; 
    int g = 0; 
    len >>= 2;

    if(left && !len)
    {
        memcpy(overflow, data, left);
        data = overflow;
        left = 0;
        len = 1;
    }

    while(len--)
    {
         g += grab32(data) ^ hash;
        *a ^= wrap32Right(~g, hash & 31);
        *b += wrap32Left(g, (*a) & 31);
        *a += wrap32Right(~(*b), 17);

        hash ^= hash << 8;
        hash *= *a;
        hash = (hash << 16) ^ wrap32Left(g,19);
        hash += *b;
        hash += hash >> 14;
        
        data += 4;
        if(!len && left)
        {       
            memcpy(overflow, data, left);
            data = overflow;
            left = 0;
            len = 1; 
       
        } 
    }

    free(overflow);
    return hash;
}


// Dynamic Hashing Scheme
unsigned char* jdmhash_dynamic(int rlen, char* data, int len, ui64 c)
{
    if(rlen < 8) rlen = 8;
    rlen -= 8;

    unsigned char *hash = (unsigned char*)calloc(rlen + 8, 1);
    ui64 hash2 = 0, cnt = 0;

    char *overflow = (char*)calloc(7, 1);
    ui32 *a = (ui32*)overflow, *b = (ui32*)(overflow+3); 
    *b = c;

    int left = len & 3; 
    int g = 0; 
    len >>= 2;

    rlen++;

    if(left && !len)
    {
        memcpy(overflow, data, left);
        data = overflow;
        left = 0;
        len = 1;
    }

    while(len--)
    {
         g += grab32(data) ^ hash2;
        *a ^= wrap32Right(~g, hash2 & 31);
        *b += wrap32Left(g, (*a) & 31);
        *a += wrap32Right(~(*b), 17);

        hash2 ^= hash2 << 8;
        hash2 *= *a;
        hash2 = (hash2 << 16) ^ wrap32Left(g,19);
        *((ui64*)(hash + ((hash2+cnt++) % rlen))) += hash2;         
        hash2 += *b;
        hash2 += hash2 >> 14;
        
        data += 4;
        if(!len && left)
        {
            memcpy(overflow, data, left);
            data = overflow;
            left = 0;
            len = 1; 
        } 
       
    }

    // For an avalanche-like effect.
    for(int i = 0; i < rlen; i++)
    {
        *((ui64*)(hash + (i))) += hash2;
    }

    free(overflow);
    return hash;
}




// Incremental (Static) Code 
struct jdmhash_incremental_helper
{
    char* data; 
    int   len, g;
    char* overflow;
    ui64  hash;
};
typedef struct jdmhash_incremental_helper* jdmhash_i; 

jdmhash_i jdmhash_make_helper(ui64 c)
{
    jdmhash_i result = calloc(1, sizeof(struct jdmhash_incremental_helper));
    result->overflow = (char*)calloc(7, 1);
    
    ui32 *b = (ui32*)(result->overflow+3);
    *b = c;

    return result;  
} 

void jdmhash_destroy_helper(jdmhash_i h)
{
    free(h->overflow);
    free(h);
}


void jdmhash_incremental(jdmhash_i h)
{
    ui64 hash = h->hash;

    char *overflow = h->overflow;
    ui32 *a = (ui32*)overflow, *b = (ui32*)(overflow+3); 

    int len = h->len;
    char* data = h->data;

    int left = len & 3; 
    int g = h->g; 
    len >>= 2;

    if(left && !len)
    {
        memcpy(overflow, data, left);
        data = overflow;
        left = 0;
        len = 1;
    }

    while(len--)
    {
         g += grab32(data) ^ hash;
        *a ^= wrap32Right(~g, hash & 31);
        *b += wrap32Left(g, (*a) & 31);
        *a += wrap32Right(~(*b), 17);

        hash ^= hash << 8;
        hash *= *a;
        hash = (hash << 16) ^ wrap32Left(g,19);
        hash += *b;
        hash += hash >> 14;
        
        data += 4;
        if(!len && left)
        {
            memcpy(overflow, data, left);
            data = overflow;
            left = 0;
            len = 1;    
        } 
    }

    h->g = g;
    h->hash = hash;
}

// Incremental (Dynamic) Code
struct jdmhash_dynamic_incremental_helper
{
    char* data; 
    int   len, rlen, g;
    char* overflow;
    char* hash;
    ui64  hash2, cnt; 
};
typedef struct jdmhash_dynamic_incremental_helper* jdmhash_dynamic_i; 

jdmhash_dynamic_i jdmhash_dynamic_make_helper(int rlen, ui64 c)
{
    if(rlen < 8) rlen = 8;
    rlen -= 8;

    jdmhash_dynamic_i result = calloc(1, sizeof(struct jdmhash_dynamic_incremental_helper));
    
    result->overflow = (char*)calloc(7, 1);
    result->rlen = rlen+1;
    result->hash = (char*)calloc(rlen+8, 1);
    
    ui32 *b = (ui32*)(result->overflow+3);
    *b = c;

    return result;  
} 

void jdmhash_dynamic_destroy_helper(jdmhash_dynamic_i h)
{
    free(h->hash);
    free(h->overflow);
    free(h);
}


void jdmhash_dynamic_incremental_finalize(jdmhash_dynamic_i h)
{
    // For an avalanche-like effect.
    for(int i = 0; i < h->rlen; i++)
    {
        *((ui64*)(h->hash + (i))) += h->hash2;
    }
}


// Dynamic Hashing Scheme
void jdmhash_dynamic_incremental(jdmhash_dynamic_i h)
{
    unsigned char *hash = h->hash;
    ui64 hash2 = h->hash2, cnt = h->cnt;

    char *overflow = h->overflow;
    ui32 *a = (ui32*)overflow, *b = (ui32*)(overflow+3); 

    
    int len = h->len, rlen = h->rlen;
    char* data = h->data; 


    int left = len & 3; 
    int g = h->g; 
    len >>= 2;

    if(left && !len)
    {
        memcpy(overflow, data, left);
        data = overflow;
        left = 0;
        len = 1;
    }

    while(len--)
    {
         g += grab32(data) ^ hash2;
        *a ^= wrap32Right(~g, hash2 & 31);
        *b += wrap32Left(g, (*a) & 31);
        *a += wrap32Right(~(*b), 17);

        hash2 ^= hash2 << 8;
        hash2 *= *a;
        hash2 = (hash2 << 16) ^ wrap32Left(g,19);
        *((ui64*)(hash + ((hash2+cnt++) % rlen))) += hash2;         
        hash2 += *b;
        hash2 += hash2 >> 14;
        
        data += 4;
        if(!len && left)
        {
            memcpy(overflow, data, left);
            data = overflow;
            left = 0;
            len = 1; 
        } 
    }

    h->g = g;
    h->hash2 = hash2;
    h->cnt = cnt;
}


#define BLOCK_SIZE 65536

int main(int argc, char **args)
{
    if(argc == 1) return -1;
    //Open File.
    FILE *f = fopen(args[1], "rb");
    
    // Get File Size and go back to beginning
    struct stat st;
    stat(args[1], &st);
    int size = st.st_size;

    if(argc == 2)
    {
        jdmhash_i x = jdmhash_make_helper(0); 
        char *buf = calloc(BLOCK_SIZE, 1);
        
        x->len = BLOCK_SIZE;
        x->data = buf; 
        
        while(size >= BLOCK_SIZE)
        {
            fread(buf, BLOCK_SIZE, 1, f);
            jdmhash_incremental(x); 
            size -= BLOCK_SIZE; 
        }
    
        x->len = size;
        fread(buf, size, 1, f);
        jdmhash_incremental(x);
        
        printf("%llx\n", x->hash);

        jdmhash_destroy_helper(x);
        free(buf); 
    }
    else
    {
        int hsize = atoi(args[2]);
        jdmhash_dynamic_i x = jdmhash_dynamic_make_helper(hsize, 0);
        char *buf = calloc(BLOCK_SIZE, 1);
    
        x->len = BLOCK_SIZE;
        x->data = buf; 
        
        while(size >= BLOCK_SIZE)
        {
            fread(buf, BLOCK_SIZE, 1, f);
            jdmhash_dynamic_incremental(x); 
            size -= BLOCK_SIZE; 
        }

        x->len = size;
        fread(buf, size, 1, f);
        jdmhash_dynamic_incremental(x);
        jdmhash_dynamic_incremental_finalize(x);
        
        printC(x->hash, hsize);
        
        jdmhash_dynamic_destroy_helper(x);
        free(buf);
    }
    
    // Close the file.
    fclose(f);
    return 0;
}