Branch data     Line data    Source code

       1                 :            : // This file is a part of Julia. License is MIT: https://julialang.org/license
       2                 :            : 
       3                 :            : /*
       4                 :            :   Hashing
       5                 :            : */
       6                 :            : #include <stdlib.h>
       7                 :            : #include "dtypes.h"
       8                 :            : #include "utils.h"
       9                 :            : #include "hashing.h"
      10                 :            : #include "timefuncs.h"
      11                 :            : #include "ios.h"
      12                 :            : 
      13                 :            : #ifdef __cplusplus
      14                 :            : extern "C" {
      15                 :            : #endif
      16                 :            : 
      17                 :      24010 : uint32_t int32hash(uint32_t a)
      18                 :            : {
      19                 :      24010 :     a = (a+0x7ed55d16) + (a<<12);
      20                 :      24010 :     a = (a^0xc761c23c) ^ (a>>19);
      21                 :      24010 :     a = (a+0x165667b1) + (a<<5);
      22                 :      24010 :     a = (a+0xd3a2646c) ^ (a<<9);
      23                 :      24010 :     a = (a+0xfd7046c5) + (a<<3);
      24                 :      24010 :     a = (a^0xb55a4f09) ^ (a>>16);
      25                 :      24010 :     return a;
      26                 :            : }
      27                 :            : 
      28                 : 3003780000 : uint64_t int64hash(uint64_t key)
      29                 :            : {
      30                 : 3003780000 :     key = (~key) + (key << 21);            // key = (key << 21) - key - 1;
      31                 : 3003780000 :     key =   key  ^ (key >> 24);
      32                 : 3003780000 :     key = (key + (key << 3)) + (key << 8); // key * 265
      33                 : 3003780000 :     key =  key ^ (key >> 14);
      34                 : 3003780000 :     key = (key + (key << 2)) + (key << 4); // key * 21
      35                 : 3003780000 :     key =  key ^ (key >> 28);
      36                 : 3003780000 :     key =  key + (key << 31);
      37                 : 3003780000 :     return key;
      38                 :            : }
      39                 :            : 
      40                 :          0 : uint32_t int64to32hash(uint64_t key)
      41                 :            : {
      42                 :          0 :     key = (~key) + (key << 18); // key = (key << 18) - key - 1;
      43                 :          0 :     key =   key  ^ (key >> 31);
      44                 :          0 :     key = key * 21;             // key = (key + (key << 2)) + (key << 4);
      45                 :          0 :     key = key ^ (key >> 11);
      46                 :          0 :     key = key + (key << 6);
      47                 :          0 :     key = key ^ (key >> 22);
      48                 :          0 :     return (uint32_t)key;
      49                 :            : }
      50                 :            : 
      51                 :            : #include "MurmurHash3.c"
      52                 :            : 
      53                 :            : #define _MHASH_SEED_ 0xcafe8881
      54                 :            : 
      55                 :   39575000 : uint64_t memhash(const char *buf, size_t n)
      56                 :            : {
      57                 :            :     uint64_t out[2];
      58                 :            : 
      59                 :            :     // TODO: expose 128-bit hash
      60                 :            : #ifdef _P64
      61                 :   39575000 :     MurmurHash3_x64_128(buf, n, _MHASH_SEED_, out);
      62                 :            : #else
      63                 :            :     MurmurHash3_x86_128(buf, n, _MHASH_SEED_, out);
      64                 :            : #endif
      65                 :   39575000 :     return out[1];
      66                 :            : }
      67                 :            : 
      68                 :     165512 : uint64_t memhash_seed(const char *buf, size_t n, uint32_t seed)
      69                 :            : {
      70                 :            :     uint64_t out[2];
      71                 :            : 
      72                 :            :     // TODO: expose 128-bit hash
      73                 :            : #ifdef _P64
      74                 :     165512 :     MurmurHash3_x64_128(buf, n, seed, out);
      75                 :            : #else
      76                 :            :     MurmurHash3_x86_128(buf, n, seed, out);
      77                 :            : #endif
      78                 :     165512 :     return out[1];
      79                 :            : }
      80                 :            : 
      81                 :     237564 : uint32_t memhash32(const char *buf, size_t n)
      82                 :            : {
      83                 :            :     uint32_t out;
      84                 :            : 
      85                 :     237564 :     MurmurHash3_x86_32(buf, n, _MHASH_SEED_, &out);
      86                 :     237564 :     return out;
      87                 :            : }
      88                 :            : 
      89                 :          0 : uint32_t memhash32_seed(const char *buf, size_t n, uint32_t seed)
      90                 :            : {
      91                 :            :     uint32_t out;
      92                 :            : 
      93                 :          0 :     MurmurHash3_x86_32(buf, n, seed, &out);
      94                 :          0 :     return out;
      95                 :            : }
      96                 :            : 
      97                 :            : #ifdef __cplusplus
      98                 :            : }
      99                 :            : #endif