mirror of
https://github.com/mariadb-corporation/mariadb-columnstore-engine.git
synced 2025-06-07 19:22:02 +03:00
487 lines
9.2 KiB
C++
487 lines
9.2 KiB
C++
/* Copyright (C) 2014 InfiniDB, Inc.
|
|
|
|
This program is free software; you can redistribute it and/or
|
|
modify it under the terms of the GNU General Public License
|
|
as published by the Free Software Foundation; version 2 of
|
|
the License.
|
|
|
|
This program is distributed in the hope that it will be useful,
|
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
GNU General Public License for more details.
|
|
|
|
You should have received a copy of the GNU General Public License
|
|
along with this program; if not, write to the Free Software
|
|
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
|
|
MA 02110-1301, USA. */
|
|
|
|
/******************************************************************************
|
|
* $Id: hasher.h 3843 2013-05-31 13:46:24Z pleblanc $
|
|
*
|
|
*****************************************************************************/
|
|
|
|
/** @file
|
|
* class Hasher interface
|
|
*/
|
|
|
|
#pragma once
|
|
|
|
#include <cstddef>
|
|
#include <stdint.h>
|
|
#include <string.h>
|
|
#include <string>
|
|
#include "mcs_basic_types.h"
|
|
|
|
namespace utils
|
|
{
|
|
/** @brief class Hasher
|
|
* As of 10/16/12, this implements the Murmur3 hash algorithm.
|
|
*/
|
|
|
|
inline uint32_t rotl32(uint32_t x, int8_t r)
|
|
{
|
|
return (x << r) | (x >> (32 - r));
|
|
}
|
|
|
|
inline uint32_t fmix(uint32_t h)
|
|
{
|
|
h ^= h >> 16;
|
|
h *= 0x85ebca6b;
|
|
h ^= h >> 13;
|
|
h *= 0xc2b2ae35;
|
|
h ^= h >> 16;
|
|
|
|
return h;
|
|
}
|
|
|
|
inline uint64_t fmix(uint64_t k)
|
|
{
|
|
k ^= k >> 33;
|
|
k *= 0xff51afd7ed558ccdULL;
|
|
k ^= k >> 33;
|
|
k *= 0xc4ceb9fe1a85ec53ULL;
|
|
k ^= k >> 33;
|
|
|
|
return k;
|
|
}
|
|
|
|
inline uint64_t rotl64(uint64_t x, int8_t r)
|
|
{
|
|
return (x << r) | (x >> (64 - r));
|
|
}
|
|
|
|
class Hasher
|
|
{
|
|
public:
|
|
inline uint32_t operator()(const std::string& s) const
|
|
{
|
|
return operator()(s.data(), s.length());
|
|
}
|
|
|
|
inline uint32_t operator()(const char* data, uint64_t len) const
|
|
{
|
|
const int nblocks = len / 4;
|
|
|
|
uint32_t h1 = 0;
|
|
|
|
const uint32_t c1 = 0xcc9e2d51;
|
|
const uint32_t c2 = 0x1b873593;
|
|
|
|
//----------
|
|
// body
|
|
|
|
const uint32_t* blocks = (const uint32_t*)(data + nblocks * 4);
|
|
|
|
for (int i = -nblocks; i; i++)
|
|
{
|
|
uint32_t k1 = blocks[i];
|
|
|
|
k1 *= c1;
|
|
k1 = rotl32(k1, 15);
|
|
k1 *= c2;
|
|
|
|
h1 ^= k1;
|
|
h1 = rotl32(h1, 13);
|
|
h1 = h1 * 5 + 0xe6546b64;
|
|
}
|
|
|
|
//----------
|
|
// tail
|
|
|
|
const uint8_t* tail = (const uint8_t*)(data + nblocks * 4);
|
|
|
|
uint32_t k1 = 0;
|
|
|
|
switch (len & 3)
|
|
{
|
|
case 3:
|
|
k1 ^= tail[2] << 16;
|
|
/* fall through */
|
|
case 2:
|
|
k1 ^= tail[1] << 8;
|
|
/* fall through */
|
|
case 1:
|
|
k1 ^= tail[0];
|
|
k1 *= c1;
|
|
k1 = rotl32(k1, 15);
|
|
k1 *= c2;
|
|
h1 ^= k1;
|
|
};
|
|
|
|
//----------
|
|
// finalization
|
|
|
|
h1 ^= len;
|
|
|
|
h1 = fmix(h1);
|
|
|
|
return h1;
|
|
}
|
|
};
|
|
|
|
class Hasher_r
|
|
{
|
|
public:
|
|
inline uint32_t operator()(const char* data, uint64_t len, uint32_t seed) const
|
|
{
|
|
const int nblocks = len / 4;
|
|
|
|
uint32_t h1 = seed;
|
|
|
|
const uint32_t c1 = 0xcc9e2d51;
|
|
const uint32_t c2 = 0x1b873593;
|
|
|
|
//----------
|
|
// body
|
|
|
|
const uint32_t* blocks = (const uint32_t*)(data + nblocks * 4);
|
|
|
|
for (int i = -nblocks; i; i++)
|
|
{
|
|
uint32_t k1 = blocks[i];
|
|
|
|
k1 *= c1;
|
|
k1 = rotl32(k1, 15);
|
|
k1 *= c2;
|
|
|
|
h1 ^= k1;
|
|
h1 = rotl32(h1, 13);
|
|
h1 = h1 * 5 + 0xe6546b64;
|
|
}
|
|
|
|
//----------
|
|
// tail
|
|
|
|
const uint8_t* tail = (const uint8_t*)(data + nblocks * 4);
|
|
|
|
uint32_t k1 = 0;
|
|
|
|
switch (len & 3)
|
|
{
|
|
case 3:
|
|
k1 ^= tail[2] << 16;
|
|
/* FALLTHRU */
|
|
|
|
case 2:
|
|
k1 ^= tail[1] << 8;
|
|
/* FALLTHRU */
|
|
|
|
case 1:
|
|
k1 ^= tail[0];
|
|
k1 *= c1;
|
|
k1 = rotl32(k1, 15);
|
|
k1 *= c2;
|
|
h1 ^= k1;
|
|
};
|
|
|
|
return h1;
|
|
}
|
|
|
|
inline uint32_t finalize(uint32_t seed, uint32_t len) const
|
|
{
|
|
seed ^= len;
|
|
seed = fmix(seed);
|
|
return seed;
|
|
}
|
|
};
|
|
|
|
// This stream hasher was borrowed from RobinHood
|
|
class Hasher64_r
|
|
{
|
|
public:
|
|
inline uint64_t operator()(const void* ptr, uint32_t len, uint64_t x = 0ULL)
|
|
{
|
|
auto const* const data64 = static_cast<uint64_t const*>(ptr);
|
|
uint64_t h = seed ^ (len * m);
|
|
|
|
std::size_t const n_blocks = len / 8;
|
|
if (x)
|
|
{
|
|
x *= m;
|
|
x ^= x >> r;
|
|
x *= m;
|
|
h ^= x;
|
|
h *= m;
|
|
}
|
|
for (std::size_t i = 0; i < n_blocks; ++i)
|
|
{
|
|
uint64_t k;
|
|
memcpy(&k, data64 + i, sizeof(k));
|
|
|
|
k *= m;
|
|
k ^= k >> r;
|
|
k *= m;
|
|
|
|
h ^= k;
|
|
h *= m;
|
|
}
|
|
|
|
auto const* const data8 = reinterpret_cast<uint8_t const*>(data64 + n_blocks);
|
|
switch (len & 7U)
|
|
{
|
|
case 7:
|
|
h ^= static_cast<uint64_t>(data8[6]) << 48U;
|
|
// FALLTHROUGH
|
|
case 6:
|
|
h ^= static_cast<uint64_t>(data8[5]) << 40U;
|
|
// FALLTHROUGH
|
|
case 5:
|
|
h ^= static_cast<uint64_t>(data8[4]) << 32U;
|
|
// FALLTHROUGH
|
|
case 4:
|
|
h ^= static_cast<uint64_t>(data8[3]) << 24U;
|
|
// FALLTHROUGH
|
|
case 3:
|
|
h ^= static_cast<uint64_t>(data8[2]) << 16U;
|
|
// FALLTHROUGH
|
|
case 2:
|
|
h ^= static_cast<uint64_t>(data8[1]) << 8U;
|
|
// FALLTHROUGH
|
|
case 1:
|
|
h ^= static_cast<uint64_t>(data8[0]);
|
|
h *= m;
|
|
// FALLTHROUGH
|
|
default: break;
|
|
}
|
|
return h;
|
|
}
|
|
|
|
inline uint64_t finalize(uint64_t h, uint64_t /*len*/) const
|
|
{
|
|
h ^= h >> r;
|
|
h *= m;
|
|
h ^= h >> r;
|
|
return h;
|
|
}
|
|
|
|
private:
|
|
static constexpr uint64_t m = 0xc6a4a7935bd1e995ULL;
|
|
static constexpr uint64_t seed = 0xe17a1465ULL;
|
|
static constexpr unsigned int r = 47;
|
|
};
|
|
|
|
class Hasher128
|
|
{
|
|
public:
|
|
inline uint64_t operator()(const char* data, uint64_t len) const
|
|
{
|
|
const int nblocks = len / 16;
|
|
|
|
uint64_t h1 = 0;
|
|
uint64_t h2 = 0;
|
|
|
|
const uint64_t c1 = 0x87c37b91114253d5ULL;
|
|
const uint64_t c2 = 0x4cf5ad432745937fULL;
|
|
|
|
//----------
|
|
// body
|
|
|
|
const uint64_t* blocks = (const uint64_t*)(data);
|
|
|
|
for (int i = 0; i < nblocks; i++)
|
|
{
|
|
uint64_t k1 = blocks[i * 2 + 0];
|
|
uint64_t k2 = blocks[i * 2 + 1];
|
|
|
|
k1 *= c1;
|
|
k1 = rotl64(k1, 31);
|
|
k1 *= c2;
|
|
h1 ^= k1;
|
|
|
|
h1 = rotl64(h1, 27);
|
|
h1 += h2;
|
|
h1 = h1 * 5 + 0x52dce729;
|
|
|
|
k2 *= c2;
|
|
k2 = rotl64(k2, 33);
|
|
k2 *= c1;
|
|
h2 ^= k2;
|
|
|
|
h2 = rotl64(h2, 31);
|
|
h2 += h1;
|
|
h2 = h2 * 5 + 0x38495ab5;
|
|
}
|
|
|
|
//----------
|
|
// tail
|
|
|
|
const uint8_t* tail = (const uint8_t*)(data + nblocks * 16);
|
|
|
|
uint64_t k1 = 0;
|
|
uint64_t k2 = 0;
|
|
|
|
switch (len & 15)
|
|
{
|
|
case 15:
|
|
k2 ^= uint64_t(tail[14]) << 48;
|
|
/* FALLTHRU */
|
|
|
|
case 14:
|
|
k2 ^= uint64_t(tail[13]) << 40;
|
|
/* FALLTHRU */
|
|
|
|
case 13:
|
|
k2 ^= uint64_t(tail[12]) << 32;
|
|
/* FALLTHRU */
|
|
|
|
case 12:
|
|
k2 ^= uint64_t(tail[11]) << 24;
|
|
/* FALLTHRU */
|
|
|
|
case 11:
|
|
k2 ^= uint64_t(tail[10]) << 16;
|
|
/* FALLTHRU */
|
|
|
|
case 10:
|
|
k2 ^= uint64_t(tail[9]) << 8;
|
|
/* FALLTHRU */
|
|
|
|
case 9:
|
|
k2 ^= uint64_t(tail[8]) << 0;
|
|
k2 *= c2;
|
|
k2 = rotl64(k2, 33);
|
|
k2 *= c1;
|
|
h2 ^= k2;
|
|
/* FALLTHRU */
|
|
|
|
case 8:
|
|
k1 ^= uint64_t(tail[7]) << 56;
|
|
/* FALLTHRU */
|
|
|
|
case 7:
|
|
k1 ^= uint64_t(tail[6]) << 48;
|
|
/* FALLTHRU */
|
|
|
|
case 6:
|
|
k1 ^= uint64_t(tail[5]) << 40;
|
|
/* FALLTHRU */
|
|
|
|
case 5:
|
|
k1 ^= uint64_t(tail[4]) << 32;
|
|
/* FALLTHRU */
|
|
|
|
case 4:
|
|
k1 ^= uint64_t(tail[3]) << 24;
|
|
/* FALLTHRU */
|
|
|
|
case 3:
|
|
k1 ^= uint64_t(tail[2]) << 16;
|
|
/* FALLTHRU */
|
|
|
|
case 2:
|
|
k1 ^= uint64_t(tail[1]) << 8;
|
|
/* FALLTHRU */
|
|
|
|
case 1:
|
|
k1 ^= uint64_t(tail[0]) << 0;
|
|
k1 *= c1;
|
|
k1 = rotl64(k1, 31);
|
|
k1 *= c2;
|
|
h1 ^= k1;
|
|
};
|
|
|
|
//----------
|
|
// finalization
|
|
|
|
h1 ^= len;
|
|
|
|
h2 ^= len;
|
|
|
|
h1 += h2;
|
|
|
|
h2 += h1;
|
|
|
|
h1 = fmix(h1);
|
|
|
|
h2 = fmix(h2);
|
|
|
|
h1 += h2;
|
|
|
|
h2 += h1;
|
|
|
|
return h1;
|
|
}
|
|
};
|
|
|
|
// TODO a copy of these classes also exists in primitiveprocessor.h; consolidate
|
|
class Hash128
|
|
{
|
|
public:
|
|
inline size_t operator()(const int128_t i) const
|
|
{
|
|
return (uint64_t)((int64_t)i);
|
|
}
|
|
};
|
|
|
|
class Equal128
|
|
{
|
|
public:
|
|
inline bool operator()(const int128_t f1, const int128_t f2) const
|
|
{
|
|
return f1 == f2;
|
|
}
|
|
};
|
|
|
|
//------------------------------------------------------------------------------
|
|
/** @brief class TupleHasher
|
|
*
|
|
*/
|
|
//------------------------------------------------------------------------------
|
|
class TupleHasher
|
|
{
|
|
public:
|
|
TupleHasher(uint32_t len) : fHashLen(len)
|
|
{
|
|
}
|
|
inline uint64_t operator()(const uint8_t* hashKey) const
|
|
{
|
|
return fHasher(reinterpret_cast<const char*>(hashKey), fHashLen);
|
|
}
|
|
|
|
private:
|
|
Hasher fHasher;
|
|
uint32_t fHashLen;
|
|
};
|
|
|
|
//------------------------------------------------------------------------------
|
|
/** @brief class TupleComparator
|
|
*
|
|
*/
|
|
//------------------------------------------------------------------------------
|
|
class TupleComparator
|
|
{
|
|
public:
|
|
TupleComparator(uint32_t len) : fCmpLen(len)
|
|
{
|
|
}
|
|
inline bool operator()(const uint8_t* hashKey1, const uint8_t* hashKey2) const
|
|
{
|
|
return (memcmp(hashKey1, hashKey2, fCmpLen) == 0);
|
|
}
|
|
|
|
private:
|
|
uint32_t fCmpLen;
|
|
};
|
|
|
|
} // namespace utils
|