city-hash.cpp File Reference

#include "city-hash.hpp"
#include <algorithm>
#include <string.h>
#include <byteswap.h>

Include dependency graph for city-hash.cpp:

Go to the source code of this file.

Macros
#define	uint32_in_expected_order(x)   (x)
#define	uint64_in_expected_order(x)   (x)
#define	LIKELY(x)   (x)
#define	PERMUTE3(a, b, c)   do { std::swap(a, b); std::swap(a, c); } while (0)

Functions
static uint64	UNALIGNED_LOAD64 (const char *p)
static uint32	UNALIGNED_LOAD32 (const char *p)
static uint64	Fetch64 (const char *p)
static uint32	Fetch32 (const char *p)
static uint32	fmix (uint32 h)
static uint32	Rotate32 (uint32 val, int shift)
static uint32	Mur (uint32 a, uint32 h)
static uint32	Hash32Len13to24 (const char *s, size_t len)
static uint32	Hash32Len0to4 (const char *s, size_t len)
static uint32	Hash32Len5to12 (const char *s, size_t len)
uint32	CityHash32 (const char *s, size_t len)
static uint64	Rotate (uint64 val, int shift)
static uint64	ShiftMix (uint64 val)
static uint64	HashLen16 (uint64 u, uint64 v)
static uint64	HashLen16 (uint64 u, uint64 v, uint64 mul)
static uint64	HashLen0to16 (const char *s, size_t len)
static uint64	HashLen17to32 (const char *s, size_t len)
static pair< uint64, uint64 >	WeakHashLen32WithSeeds (uint64 w, uint64 x, uint64 y, uint64 z, uint64 a, uint64 b)
static pair< uint64, uint64 >	WeakHashLen32WithSeeds (const char *s, uint64 a, uint64 b)
static uint64	HashLen33to64 (const char *s, size_t len)
uint64	CityHash64 (const char *s, size_t len)
uint64	CityHash64WithSeed (const char *s, size_t len, uint64 seed)
uint64	CityHash64WithSeeds (const char *s, size_t len, uint64 seed0, uint64 seed1)
static uint128	CityMurmur (const char *s, size_t len, uint128 seed)
uint128	CityHash128WithSeed (const char *s, size_t len, uint128 seed)
uint128	CityHash128 (const char *s, size_t len)

Variables
static const uint64	k0 = 0xc3a5c85c97cb3127ULL
static const uint64	k1 = 0xb492b66fbe98f273ULL
static const uint64	k2 = 0x9ae16a3b2f90404fULL
static const uint32_t	c1 = 0xcc9e2d51
static const uint32_t	c2 = 0x1b873593

Macro Definition Documentation

uint32_in_expected_order

#define uint32_in_expected_order

(

x

)

(x)

Definition at line 93 of file city-hash.cpp.

uint64_in_expected_order

#define uint64_in_expected_order

(

x

)

(x)

Definition at line 94 of file city-hash.cpp.

LIKELY

#define LIKELY

(

x

)

(x)

Definition at line 101 of file city-hash.cpp.

PERMUTE3

#define PERMUTE3	(		a,
			b,
			c
	)		do { std::swap(a, b); std::swap(a, c); } while (0)

Definition at line 139 of file city-hash.cpp.

Function Documentation

UNALIGNED_LOAD64()

static uint64 UNALIGNED_LOAD64 ( const char *  p )

static

Definition at line 38 of file city-hash.cpp.

Referenced by Fetch64().

UNALIGNED_LOAD32()

static uint32 UNALIGNED_LOAD32 ( const char *  p )

static

Definition at line 44 of file city-hash.cpp.

Referenced by Fetch32().

Fetch64()

static uint64 Fetch64 ( const char *  p )

static

Definition at line 105 of file city-hash.cpp.

References uint64_in_expected_order, and UNALIGNED_LOAD64().

Referenced by CityHash128(), CityHash128WithSeed(), CityHash64(), CityMurmur(), HashLen0to16(), HashLen17to32(), HashLen33to64(), and WeakHashLen32WithSeeds().

Fetch32()

static uint32 Fetch32 ( const char *  p )

static

Definition at line 109 of file city-hash.cpp.

References uint32_in_expected_order, and UNALIGNED_LOAD32().

Referenced by CityHash32(), Hash32Len13to24(), Hash32Len5to12(), and HashLen0to16().

fmix()

static uint32 fmix ( uint32  h )

static

Definition at line 123 of file city-hash.cpp.

Referenced by Hash32Len0to4(), Hash32Len13to24(), and Hash32Len5to12().

Rotate32()

static uint32 Rotate32 ( uint32  val, int  shift  )

static

Definition at line 133 of file city-hash.cpp.

Referenced by CityHash32(), and Mur().

Mur()

static uint32 Mur ( uint32  a, uint32  h  )

static

Definition at line 141 of file city-hash.cpp.

References c1, c2, and Rotate32().

Referenced by Hash32Len0to4(), Hash32Len13to24(), and Hash32Len5to12().

Hash32Len13to24()

static uint32 Hash32Len13to24 ( const char *  s, size_t  len  )

static

Definition at line 151 of file city-hash.cpp.

References Fetch32(), fmix(), and Mur().

Referenced by CityHash32().

Hash32Len0to4()

static uint32 Hash32Len0to4 ( const char *  s, size_t  len  )

static

Definition at line 163 of file city-hash.cpp.

References c1, fmix(), and Mur().

Referenced by CityHash32().

Hash32Len5to12()

static uint32 Hash32Len5to12 ( const char *  s, size_t  len  )

static

Definition at line 174 of file city-hash.cpp.

References Fetch32(), fmix(), and Mur().

Referenced by CityHash32().

CityHash32()

uint32 CityHash32	(	const char *	s,
		size_t	len
	)

Definition at line 182 of file city-hash.cpp.

References c1, c2, Fetch32(), Hash32Len0to4(), Hash32Len13to24(), Hash32Len5to12(), PERMUTE3, and Rotate32().

Referenced by nfd::name_tree::Hash32::compute().

Here is the caller graph for this function:

Rotate()

static uint64 Rotate ( uint64  val, int  shift  )

static

Definition at line 253 of file city-hash.cpp.

Referenced by CityHash128WithSeed(), CityHash64(), HashLen0to16(), HashLen17to32(), HashLen33to64(), and WeakHashLen32WithSeeds().

ShiftMix()

static uint64 ShiftMix ( uint64  val )

static

Definition at line 258 of file city-hash.cpp.

Referenced by CityHash64(), CityMurmur(), HashLen0to16(), and HashLen33to64().

HashLen16() [1/2]

static uint64 HashLen16 ( uint64  u, uint64  v  )

static

Definition at line 262 of file city-hash.cpp.

References Hash128to64().

Referenced by CityHash128WithSeed(), CityHash64(), CityHash64WithSeeds(), CityMurmur(), HashLen0to16(), and HashLen17to32().

HashLen16() [2/2]

static uint64 HashLen16 ( uint64  u, uint64  v, uint64  mul  )

static

Definition at line 266 of file city-hash.cpp.

HashLen0to16()

static uint64 HashLen0to16 ( const char *  s, size_t  len  )

static

Definition at line 276 of file city-hash.cpp.

References Fetch32(), Fetch64(), HashLen16(), k0, k2, Rotate(), and ShiftMix().

Referenced by CityHash64(), and CityMurmur().

HashLen17to32()

static uint64 HashLen17to32 ( const char *  s, size_t  len  )

static

Definition at line 303 of file city-hash.cpp.

References Fetch64(), HashLen16(), k1, k2, and Rotate().

Referenced by CityHash64().

WeakHashLen32WithSeeds() [1/2]

static pair<uint64, uint64> WeakHashLen32WithSeeds ( uint64  w, uint64  x, uint64  y, uint64  z, uint64  a, uint64  b  )

static

Definition at line 315 of file city-hash.cpp.

References Rotate().

Referenced by CityHash128WithSeed(), CityHash64(), and WeakHashLen32WithSeeds().

WeakHashLen32WithSeeds() [2/2]

static pair<uint64, uint64> WeakHashLen32WithSeeds ( const char *  s, uint64  a, uint64  b  )

static

Definition at line 327 of file city-hash.cpp.

References Fetch64(), and WeakHashLen32WithSeeds().

HashLen33to64()

static uint64 HashLen33to64 ( const char *  s, size_t  len  )

static

Definition at line 338 of file city-hash.cpp.

References Fetch64(), k2, Rotate(), and ShiftMix().

Referenced by CityHash64().

CityHash64()

uint64 CityHash64	(	const char *	s,
		size_t	len
	)

Definition at line 359 of file city-hash.cpp.

References Fetch64(), HashLen0to16(), HashLen16(), HashLen17to32(), HashLen33to64(), k1, Rotate(), ShiftMix(), nonstd::any_lite::swap(), and WeakHashLen32WithSeeds().

Referenced by CityHash64WithSeeds(), and nfd::name_tree::Hash64::compute().

Here is the caller graph for this function:

CityHash64WithSeed()

uint64 CityHash64WithSeed	(	const char *	s,
		size_t	len,
		uint64	seed
	)

Definition at line 397 of file city-hash.cpp.

References CityHash64WithSeeds(), and k2.

CityHash64WithSeeds()

uint64 CityHash64WithSeeds	(	const char *	s,
		size_t	len,
		uint64	seed0,
		uint64	seed1
	)

Definition at line 401 of file city-hash.cpp.

References CityHash64(), and HashLen16().

Referenced by CityHash64WithSeed().

Here is the caller graph for this function:

CityMurmur()

static uint128 CityMurmur ( const char *  s, size_t  len, uint128  seed  )

static

Definition at line 408 of file city-hash.cpp.

References Fetch64(), HashLen0to16(), HashLen16(), k1, ShiftMix(), Uint128High64(), and Uint128Low64().

Referenced by CityHash128WithSeed().

CityHash128WithSeed()

uint128 CityHash128WithSeed	(	const char *	s,
		size_t	len,
		uint128	seed
	)

Definition at line 438 of file city-hash.cpp.

References CityMurmur(), Fetch64(), HashLen16(), k0, k1, LIKELY, Rotate(), nonstd::any_lite::swap(), Uint128High64(), Uint128Low64(), and WeakHashLen32WithSeeds().

Referenced by CityHash128().

Here is the caller graph for this function:

CityHash128()

uint128 CityHash128	(	const char *	s,
		size_t	len
	)

Definition at line 501 of file city-hash.cpp.

References CityHash128WithSeed(), Fetch64(), k0, and k1.

Variable Documentation

k0

const uint64 k0 = 0xc3a5c85c97cb3127ULL

static

Definition at line 114 of file city-hash.cpp.

Referenced by CityHash128(), CityHash128WithSeed(), and HashLen0to16().

k1

const uint64 k1 = 0xb492b66fbe98f273ULL

static

Definition at line 115 of file city-hash.cpp.

Referenced by CityHash128(), CityHash128WithSeed(), CityHash64(), CityMurmur(), and HashLen17to32().

k2

const uint64 k2 = 0x9ae16a3b2f90404fULL

static

Definition at line 116 of file city-hash.cpp.

Referenced by CityHash64WithSeed(), HashLen0to16(), HashLen17to32(), and HashLen33to64().

c1

const uint32_t c1 = 0xcc9e2d51

static

Definition at line 119 of file city-hash.cpp.

Referenced by CityHash32(), Hash32Len0to4(), and Mur().

c2

const uint32_t c2 = 0x1b873593

static

Definition at line 120 of file city-hash.cpp.

Referenced by CityHash32(), and Mur().