<commit_before>
/////////////////////////////////////
// This C code is a companion to the paper 
//
// Reference: <NAME> and <NAME>, Strongly universal string hashing is fast, Computer Journal 
// http://arxiv.org/abs/1202.4961
//
// It shows that we can compute strongly universal hash functions very quickly.
/////////////////////////////////////

//
// this code will hash strings of 32-bit characters. To use on 
// strings of 8-bit characters, you may need some adequate padding.
// 
 #include <stdint.h>
 #include <stdlib.h>
 #include <stdio.h>
 #include <sys/time.h>
 #include <smmintrin.h>

//
// this is strongly universal. Condition: randomsource must be at least as long as 
// the string length  + 3.
//  
// Reference: <NAME> and <NAME>, Strongly universal string hashing is fast, Computer Journal 
// http://arxiv.org/abs/1202.4961
//__attribute__ ((__target__ ("no-sse2"))) // GCC has buggy SSE2 code generation in some cases
uint32_t hashMultilinear(const uint64_t *  randomsource, const uint32_t *  string, const size_t length) {
    const uint32_t * const endstring = string + length;
    uint64_t sum = *(randomsource++);
    for(; string!= endstring; ++randomsource,++string ) {
        sum+= (*randomsource *  (uint64_t)(*string)) ;
    }
    sum += *randomsource;
    return (int) (sum>>32);
}



uint32_t hashMultilinearSSE41(const uint64_t *  randomsource, const uint32_t *  string, const size_t length) {
    uint64_t sum = *(randomsource++);
    randomsource++;// skipp
    __m128i counter =  _mm_setzero_si128 ();
    for(size_t i = 0; i < length;i+=4) {
    	__m128i randvec1 = _mm_load_si128 ((__m128i*) randomsource);
    	randomsource += 2;
    	__m128i randvec2 = _mm_load_si128 ((__m128i*) randomsource);
    	randomsource += 2;
    	__m128i datavec = _mm_load_si128 ((__m128i*) string);
    	string += 4;
    	
    	__m128i iterm1 =  _mm_slli_epi64 ( _mm_mul_epu32 (randvec1, datavec), 32);
    	counter = _mm_add_epi64 (counter, iterm1);
    	__m128i iterm2 =    _mm_mul_epu32 ( _mm_slli_si128(randvec1,4), datavec);
    	counter = _mm_add_epi64 (counter, iterm2);
    	datavec = _mm_slli_si128(datavec,4);
    	__m128i iterm3 =  _mm_slli_epi64 ( _mm_mul_epu32 (randvec2, datavec), 32);
    	counter = _mm_add_epi64 (counter, iterm3);
    	__m128i iterm4 =    _mm_mul_epu32 ( _mm_slli_si128(randvec2,4), datavec);
    	counter = _mm_add_epi64 (counter, iterm4);
    }

    sum +=  _mm_extract_epi64 (counter,0);
    sum +=  _mm_extract_epi64 (counter,1);

    sum += *randomsource;

    return (int) (sum>>32);
}


// Rabin-Karp Hashing
uint32_t hashRabinKarp(const uint64_t * , const uint32_t *  string, const size_t length) {
    int sum = 0;
    const int someprime = 31;
    for(size_t i = 0; i < length; ++i) {
        sum = someprime * sum +  string[i] ;
    }
    return sum;
}

// This is similar to Rabin-Karp, but we avoid the multiplication
//<NAME>, CDB–Constant Database, http://cr.yp.to/cdb.html
uint32_t hashBernstein(const uint64_t * ,const uint32_t *  string, const size_t length) {
    int sum = 0;
    const int L = 3;
    for(size_t i = 0; i < length; ++i) {
        sum= (( sum<< L) + sum) ^ string[i] ;
    }
    return sum;
}

// Fowler-Noll-Vo hashing
// <NAME>, Fowler/Noll/Vo Hash, http://www.isthe.com/chongo/tech/comp/fnv/
uint32_t hashFNV1(const uint64_t * ,const uint32_t *  string, const size_t length) {
    int sum = 0;
    const uint32_t someprime = 31;
    for(size_t i = 0; i < length; ++i) {
        sum = ( someprime * sum) ^ string[i] ;
    }
    return sum;
}

// Fowler-Noll-Vo hashing
// <NAME>, Fowler/Noll/Vo Hash, http://www.isthe.com/chongo/tech/comp/fnv/
uint32_t hashFNV1a(const uint64_t *  ,const uint32_t *  string, const size_t length) {
    int sum = 0;
    const uint32_t someprime = 31;
    for(size_t i = 0; i < length; ++i) {
        sum = ( (string[i]) ^ sum) * someprime ;
    }
    return sum;
}

// <NAME>, <NAME>, Performance in practice of string hashing functions,
//in: Proc. Int. Conf. on Database Systems for Advanced Applications, 1997.
uint32_t hashSAX(const uint64_t * ,  const uint32_t *  string, const size_t length) {
    int sum = 0;
    const int L = 3;
    const int R = 5;
    for(size_t i = 0; i < length; ++i) {
        sum = sum ^((sum<<L)+(sum>>R) + string[i]) ;
    }
    return sum;
}


typedef unsigned long long ticks;

// Taken from stackoverflow (see http://stackoverflow.com/questions/3830883/cpu-cycle-count-based-profiling-in-c-c-linux-x86-64)
// Can give nonsensical results on multi-core AMD processors.
ticks rdtsc() {
    unsigned int lo, hi;
    asm volatile (
        "cpuid \n" /* serializing */
        "rdtsc"
        : "=a"(lo), "=d"(hi) /* outputs */
        : "a"(0)           /* inputs */
        : "%ebx", "%ecx");     /* clobbers*/
    return ((unsigned long long)lo) | (((unsigned long long)hi) << 32);
}
ticks startRDTSC (void) {
    return rdtsc();
}

ticks stopRDTSCP (void) {
    return rdtsc();
}
// start and stop are as recommended by 
// <NAME>, How to Benchmark Code Execution Times on Intel® IA-32 and IA-64 Instruction Set Architectures
// September 2010
// http://edc.intel.com/Link.aspx?id=3954

static __inline__ ticks fancystartRDTSC (void) {
  unsigned cycles_low, cycles_high;
  asm volatile ("CPUID\n\t"
                "RDTSC\n\t"
                "mov %%edx, %0\n\t"
                "mov %%eax, %1\n\t": "=r" (cycles_high), "=r" (cycles_low)::
                "%rax", "%rbx", "%rcx", "%rdx");
  return ((ticks)cycles_high << 32) | cycles_low;
}

static __inline__ ticks fancystopRDTSCP (void) {
  unsigned cycles_low, cycles_high;
/// This should work fine on most machines, if the RDTSCP thing
/// fails for you, use the  rdtsc() call instead.
  asm volatile("RDTSCP\n\t"
               "mov %%edx, %0\n\t"
               "mov %%eax, %1\n\t"
               "CPUID\n\t": "=r" (cycles_high), "=r" (cycles_low):: "%rax",
               "%rbx", "%rcx", "%rdx");
  return ((ticks)cycles_high << 32) | cycles_low;
}


typedef uint32_t (*hashFunction)(const uint64_t *  ,const  uint32_t * , const size_t );

#define HowManyFunctions 6

hashFunction funcArr[HowManyFunctions] = {&hashMultilinear, &hashMultilinearSSE41, &hashRabinKarp, &hashFNV1, &hashFNV1a, &hashSAX};

 const char* functionnames[HowManyFunctions] = {"Multilinear   (strongly universal)",
 												"MultilinearSSE(strongly universal)", 
                                                 "RabinKarp                        ",
                                                 "FNV1                             ",
                                                 "FNV1a                            ",
                                                 "SAX                              "};

int main(int , char **) {
    const int N = 1024; // should be divisible by two!<commit_msg>Reverting<commit_after>
/////////////////////////////////////
// This C code is a companion to the paper 
//
// Reference: <NAME> and <NAME>, Strongly universal string hashing is fast, Computer Journal 
// http://arxiv.org/abs/1202.4961
//
// It shows that we can compute strongly universal hash functions very quickly.
/////////////////////////////////////

//
// this code will hash strings of 32-bit characters. To use on 
// strings of 8-bit characters, you may need some adequate padding.
// 
 #include <stdint.h>
 #include <stdlib.h>
 #include <stdio.h>
 #include <sys/time.h>
 #include <smmintrin.h>
 #include <assert.h>
//
// this is strongly universal. Condition: randomsource must be at least as long as 
// the string length  + 3.
//  
// Reference: <NAME> and <NAME>, Strongly universal string hashing is fast, Computer Journal 
// http://arxiv.org/abs/1202.4961
//__attribute__ ((__target__ ("no-sse2"))) // GCC has buggy SSE2 code generation in some cases
uint32_t hashMultilinear(const uint64_t *  randomsource, const uint32_t *  string, const size_t length) {
    const uint32_t * const endstring = string + length;
    uint64_t sum = *(randomsource++);
    for(; string!= endstring; ++randomsource,++string ) {
        sum+= (*randomsource *  (uint64_t)(*string)) ;
    }
    sum += *randomsource;
    return (int) (sum>>32);
}


// Rabin-Karp Hashing
uint32_t hashRabinKarp(const uint64_t * , const uint32_t *  string, const size_t length) {
    int sum = 0;
    const int someprime = 31;
    for(size_t i = 0; i < length; ++i) {
        sum = someprime * sum +  string[i] ;
    }
    return sum;
}

// This is similar to Rabin-Karp, but we avoid the multiplication
//<NAME>, CDB–Constant Database, http://cr.yp.to/cdb.html
uint32_t hashBernstein(const uint64_t * ,const uint32_t *  string, const size_t length) {
    int sum = 0;
    const int L = 3;
    for(size_t i = 0; i < length; ++i) {
        sum= (( sum<< L) + sum) ^ string[i] ;
    }
    return sum;
}

// Fowler-Noll-Vo hashing
// <NAME>, Fowler/Noll/Vo Hash, http://www.isthe.com/chongo/tech/comp/fnv/
uint32_t hashFNV1(const uint64_t * ,const uint32_t *  string, const size_t length) {
    int sum = 0;
    const uint32_t someprime = 31;
    for(size_t i = 0; i < length; ++i) {
        sum = ( someprime * sum) ^ string[i] ;
    }
    return sum;
}

// Fowler-Noll-Vo hashing
// <NAME>, Fowler/Noll/Vo Hash, http://www.isthe.com/chongo/tech/comp/fnv/
uint32_t hashFNV1a(const uint64_t *  ,const uint32_t *  string, const size_t length) {
    int sum = 0;
    const uint32_t someprime = 31;
    for(size_t i = 0; i < length; ++i) {
        sum = ( (string[i]) ^ sum) * someprime ;
    }
    return sum;
}

// <NAME>, <NAME>, Performance in practice of string hashing functions,
//in: Proc. Int. Conf. on Database Systems for Advanced Applications, 1997.
uint32_t hashSAX(const uint64_t * ,  const uint32_t *  string, const size_t length) {
    int sum = 0;
    const int L = 3;
    const int R = 5;
    for(size_t i = 0; i < length; ++i) {
        sum = sum ^((sum<<L)+(sum>>R) + string[i]) ;
    }
    return sum;
}


typedef unsigned long long ticks;

// Taken from stackoverflow (see http://stackoverflow.com/questions/3830883/cpu-cycle-count-based-profiling-in-c-c-linux-x86-64)
// Can give nonsensical results on multi-core AMD processors.
ticks rdtsc() {
    unsigned int lo, hi;
    asm volatile (
        "cpuid \n" /* serializing */
        "rdtsc"
        : "=a"(lo), "=d"(hi) /* outputs */
        : "a"(0)           /* inputs */
        : "%ebx", "%ecx");     /* clobbers*/
    return ((unsigned long long)lo) | (((unsigned long long)hi) << 32);
}
ticks startRDTSC (void) {
    return rdtsc();
}

ticks stopRDTSCP (void) {
    return rdtsc();
}
// start and stop are as recommended by 
// <NAME>, How to Benchmark Code Execution Times on Intel® IA-32 and IA-64 Instruction Set Architectures
// September 2010
// http://edc.intel.com/Link.aspx?id=3954

static __inline__ ticks fancystartRDTSC (void) {
  unsigned cycles_low, cycles_high;
  asm volatile ("CPUID\n\t"
                "RDTSC\n\t"
                "mov %%edx, %0\n\t"
                "mov %%eax, %1\n\t": "=r" (cycles_high), "=r" (cycles_low)::
                "%rax", "%rbx", "%rcx", "%rdx");
  return ((ticks)cycles_high << 32) | cycles_low;
}

static __inline__ ticks fancystopRDTSCP (void) {
  unsigned cycles_low, cycles_high;
/// This should work fine on most machines, if the RDTSCP thing
/// fails for you, use the  rdtsc() call instead.
  asm volatile("RDTSCP\n\t"
               "mov %%edx, %0\n\t"
               "mov %%eax, %1\n\t"
               "CPUID\n\t": "=r" (cycles_high), "=r" (cycles_low):: "%rax",
               "%rbx", "%rcx", "%rdx");
  return ((ticks)cycles_high << 32) | cycles_low;
}


typedef uint32_t (*hashFunction)(const uint64_t *  ,const  uint32_t * , const size_t );

#define HowManyFunctions 5

hashFunction funcArr[HowManyFunctions] = {&hashMultilinear, &hashRabinKarp, &hashFNV1, &hashFNV1a, &hashSAX};

 const char* functionnames[HowManyFunctions] = {"Multilinear   (strongly universal)",
                                                 "RabinKarp                        ",
                                                 "FNV1                             ",
                                                 "FNV1a                            ",
                                                 "SAX                              "};

int main(int , char **) {
    const int N = 1024; // should be divisible by two!
{'fraction_non_alphanumeric': 0.14761556584612884, 'fraction_numerical': 0.03314647818669266, 'mean_word_length': 2.3297268055179874, 'pattern_counts': {'":': 4, '<': 65, '<?xml version=': 0, '>': 44, 'https://': 0, 'lorem ipsum': 0, 'www.': 4, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 16, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5962831', 'n_tokens_mistral': 4591, 'n_tokens_neox': 4160, 'n_words': 1163}