\doxysection{hash.\+h}
\label{hash_8h_source}\index{include/osmocom/core/hash.h@{include/osmocom/core/hash.h}}
\textbf{ Go to the documentation of this file.}
\begin{DoxyCode}{0}
\DoxyCodeLine{1 \textcolor{preprocessor}{\#pragma once}}
\DoxyCodeLine{2 \textcolor{preprocessor}{\#include <osmocom/core/log2.h>}}
\DoxyCodeLine{3 \textcolor{comment}{/* Fast hashing routine for ints,  longs and pointers.}}
\DoxyCodeLine{4 \textcolor{comment}{   (C) 2002 Nadia Yvette Chambers, IBM */}}
\DoxyCodeLine{5 }
\DoxyCodeLine{6 \textcolor{preprocessor}{\#include <limits.h>}}
\DoxyCodeLine{7 \textcolor{preprocessor}{\#if ULONG\_MAX == 4294967295}}
\DoxyCodeLine{8 \textcolor{preprocessor}{\#define BITS\_PER\_LONG 32}}
\DoxyCodeLine{9 \textcolor{preprocessor}{\#else}}
\DoxyCodeLine{10 \textcolor{preprocessor}{\#define BITS\_PER\_LONG 64}}
\DoxyCodeLine{11 \textcolor{preprocessor}{\#endif}}
\DoxyCodeLine{12 }
\DoxyCodeLine{13 \textcolor{comment}{/*}}
\DoxyCodeLine{14 \textcolor{comment}{ * The "{}GOLDEN\_RATIO\_PRIME"{} is used in ifs/btrfs/brtfs\_inode.h and}}
\DoxyCodeLine{15 \textcolor{comment}{ * fs/inode.c.  It's not actually prime any more (the previous primes}}
\DoxyCodeLine{16 \textcolor{comment}{ * were actively bad for hashing), but the name remains.}}
\DoxyCodeLine{17 \textcolor{comment}{ */}}
\DoxyCodeLine{18 \textcolor{preprocessor}{\#if BITS\_PER\_LONG == 32}}
\DoxyCodeLine{19 \textcolor{preprocessor}{\#define GOLDEN\_RATIO\_PRIME GOLDEN\_RATIO\_32}}
\DoxyCodeLine{20 \textcolor{preprocessor}{\#define hash\_long(val, bits) hash\_32(val, bits)}}
\DoxyCodeLine{21 \textcolor{preprocessor}{\#elif BITS\_PER\_LONG == 64}}
\DoxyCodeLine{22 \textcolor{preprocessor}{\#define hash\_long(val, bits) hash\_64(val, bits)}}
\DoxyCodeLine{23 \textcolor{preprocessor}{\#define GOLDEN\_RATIO\_PRIME GOLDEN\_RATIO\_64}}
\DoxyCodeLine{24 \textcolor{preprocessor}{\#else}}
\DoxyCodeLine{25 \textcolor{preprocessor}{\#error Wordsize not 32 or 64}}
\DoxyCodeLine{26 \textcolor{preprocessor}{\#endif}}
\DoxyCodeLine{27 }
\DoxyCodeLine{28 \textcolor{comment}{/*}}
\DoxyCodeLine{29 \textcolor{comment}{ * This hash multiplies the input by a large odd number and takes the}}
\DoxyCodeLine{30 \textcolor{comment}{ * high bits.  Since multiplication propagates changes to the most}}
\DoxyCodeLine{31 \textcolor{comment}{ * significant end only, it is essential that the high bits of the}}
\DoxyCodeLine{32 \textcolor{comment}{ * product be used for the hash value.}}
\DoxyCodeLine{33 \textcolor{comment}{ *}}
\DoxyCodeLine{34 \textcolor{comment}{ * Chuck Lever verified the effectiveness of this technique:}}
\DoxyCodeLine{35 \textcolor{comment}{ * http://www.citi.umich.edu/techreports/reports/citi-\/tr-\/00-\/1.pdf}}
\DoxyCodeLine{36 \textcolor{comment}{ *}}
\DoxyCodeLine{37 \textcolor{comment}{ * Although a random odd number will do, it turns out that the golden}}
\DoxyCodeLine{38 \textcolor{comment}{ * ratio phi = (sqrt(5)-\/1)/2, or its negative, has particularly nice}}
\DoxyCodeLine{39 \textcolor{comment}{ * properties.  (See Knuth vol 3, section 6.4, exercise 9.)}}
\DoxyCodeLine{40 \textcolor{comment}{ *}}
\DoxyCodeLine{41 \textcolor{comment}{ * These are the negative, (1 -\/ phi) = phi**2 = (3 -\/ sqrt(5))/2,}}
\DoxyCodeLine{42 \textcolor{comment}{ * which is very slightly easier to multiply by and makes no}}
\DoxyCodeLine{43 \textcolor{comment}{ * difference to the hash distribution.}}
\DoxyCodeLine{44 \textcolor{comment}{ */}}
\DoxyCodeLine{45 \textcolor{preprocessor}{\#define GOLDEN\_RATIO\_32 0x61C88647}}
\DoxyCodeLine{46 \textcolor{preprocessor}{\#define GOLDEN\_RATIO\_64 0x61C8864680B583EBull}}
\DoxyCodeLine{47 }
\DoxyCodeLine{48 \textcolor{comment}{/*}}
\DoxyCodeLine{49 \textcolor{comment}{ * The \_generic versions exist only so lib/test\_hash.c can compare}}
\DoxyCodeLine{50 \textcolor{comment}{ * the arch-\/optimized versions with the generic.}}
\DoxyCodeLine{51 \textcolor{comment}{ *}}
\DoxyCodeLine{52 \textcolor{comment}{ * Note that if you change these, any <asm/hash.h> that aren't updated}}
\DoxyCodeLine{53 \textcolor{comment}{ * to match need to have their HAVE\_ARCH\_* define values updated so the}}
\DoxyCodeLine{54 \textcolor{comment}{ * self-\/test will not false-\/positive.}}
\DoxyCodeLine{55 \textcolor{comment}{ */}}
\DoxyCodeLine{56 \textcolor{preprocessor}{\#ifndef HAVE\_ARCH\_\_HASH\_32}}
\DoxyCodeLine{57 \textcolor{preprocessor}{\#define \_\_hash\_32 \_\_hash\_32\_generic}}
\DoxyCodeLine{58 \textcolor{preprocessor}{\#endif}}
\DoxyCodeLine{59 \textcolor{keyword}{static} \textcolor{keyword}{inline} uint32\_t \_\_hash\_32\_generic(uint32\_t val)}
\DoxyCodeLine{60 \{}
\DoxyCodeLine{61         \textcolor{keywordflow}{return} val * GOLDEN\_RATIO\_32;}
\DoxyCodeLine{62 \}}
\DoxyCodeLine{63 }
\DoxyCodeLine{64 \textcolor{preprocessor}{\#ifndef HAVE\_ARCH\_HASH\_32}}
\DoxyCodeLine{65 \textcolor{preprocessor}{\#define hash\_32 hash\_32\_generic}}
\DoxyCodeLine{66 \textcolor{preprocessor}{\#endif}}
\DoxyCodeLine{67 \textcolor{keyword}{static} \textcolor{keyword}{inline} uint32\_t hash\_32\_generic(uint32\_t val, \textcolor{keywordtype}{unsigned} \textcolor{keywordtype}{int} bits)}
\DoxyCodeLine{68 \{}
\DoxyCodeLine{69         \textcolor{comment}{/* High bits are more random, so use them. */}}
\DoxyCodeLine{70         \textcolor{keywordflow}{return} \_\_hash\_32(val) >> (32 -\/ bits);}
\DoxyCodeLine{71 \}}
\DoxyCodeLine{72 }
\DoxyCodeLine{73 \textcolor{preprocessor}{\#ifndef HAVE\_ARCH\_HASH\_64}}
\DoxyCodeLine{74 \textcolor{preprocessor}{\#define hash\_64 hash\_64\_generic}}
\DoxyCodeLine{75 \textcolor{preprocessor}{\#endif}}
\DoxyCodeLine{76 \textcolor{keyword}{static} \_\_always\_inline uint32\_t hash\_64\_generic(uint64\_t val, \textcolor{keywordtype}{unsigned} \textcolor{keywordtype}{int} bits)}
\DoxyCodeLine{77 \{}
\DoxyCodeLine{78 \textcolor{preprocessor}{\#if BITS\_PER\_LONG == 64}}
\DoxyCodeLine{79         \textcolor{comment}{/* 64x64-\/bit multiply is efficient on all 64-\/bit processors */}}
\DoxyCodeLine{80         \textcolor{keywordflow}{return} val * GOLDEN\_RATIO\_64 >> (64 -\/ bits);}
\DoxyCodeLine{81 \textcolor{preprocessor}{\#else}}
\DoxyCodeLine{82         \textcolor{comment}{/* Hash 64 bits using only 32x32-\/bit multiply. */}}
\DoxyCodeLine{83         \textcolor{keywordflow}{return} hash\_32((uint32\_t)val \string^ \_\_hash\_32(val >> 32), bits);}
\DoxyCodeLine{84 \textcolor{preprocessor}{\#endif}}
\DoxyCodeLine{85 \}}
\DoxyCodeLine{86 }
\DoxyCodeLine{87 \textcolor{keyword}{static} \textcolor{keyword}{inline} uint32\_t hash\_ptr(\textcolor{keyword}{const} \textcolor{keywordtype}{void} *ptr, \textcolor{keywordtype}{unsigned} \textcolor{keywordtype}{int} bits)}
\DoxyCodeLine{88 \{}
\DoxyCodeLine{89         \textcolor{keywordflow}{return} hash\_long((\textcolor{keywordtype}{unsigned} \textcolor{keywordtype}{long})ptr, bits);}
\DoxyCodeLine{90 \}}
\DoxyCodeLine{91 }
\DoxyCodeLine{92 \textcolor{comment}{/* This really should be called fold32\_ptr; it does no hashing to speak of. */}}
\DoxyCodeLine{93 \textcolor{keyword}{static} \textcolor{keyword}{inline} uint32\_t hash32\_ptr(\textcolor{keyword}{const} \textcolor{keywordtype}{void} *ptr)}
\DoxyCodeLine{94 \{}
\DoxyCodeLine{95         \textcolor{keywordtype}{unsigned} \textcolor{keywordtype}{long} val = (\textcolor{keywordtype}{unsigned} long)ptr;}
\DoxyCodeLine{96 }
\DoxyCodeLine{97 \textcolor{preprocessor}{\#if BITS\_PER\_LONG == 64}}
\DoxyCodeLine{98         val \string^= (val >> 32);}
\DoxyCodeLine{99 \textcolor{preprocessor}{\#endif}}
\DoxyCodeLine{100         \textcolor{keywordflow}{return} (uint32\_t)val;}
\DoxyCodeLine{101 \}}

\end{DoxyCode}
