\doxysection{jhash.\+h}
\label{jhash_8h_source}\index{include/osmocom/core/jhash.h@{include/osmocom/core/jhash.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/bit32gen.h>}}
\DoxyCodeLine{3 }
\DoxyCodeLine{4 \textcolor{comment}{/* Below is a partial copy of}}
\DoxyCodeLine{5 \textcolor{comment}{ * https://raw.githubusercontent.com/torvalds/linux/3eb3c33c1d87029a3832e205eebd59cfb56ba3a4/tools/include/linux/bitops.h}}
\DoxyCodeLine{6 \textcolor{comment}{ * with an osmo\_ prefix applied to avoid any collisions.}}
\DoxyCodeLine{7 \textcolor{comment}{ */}}
\DoxyCodeLine{8 \textcolor{comment}{/* SPDX-\/License-\/Identifier: GPL-\/2.0 */}}
\DoxyCodeLine{14 \textcolor{keyword}{static} \textcolor{keyword}{inline} uint32\_t osmo\_rol32(uint32\_t word, \textcolor{keywordtype}{unsigned} \textcolor{keywordtype}{int} shift)}
\DoxyCodeLine{15 \{}
\DoxyCodeLine{16         \textcolor{keywordflow}{return} (word << shift) | (word >> ((-\/shift) \& 31));}
\DoxyCodeLine{17 \}}
\DoxyCodeLine{18 }
\DoxyCodeLine{19 \textcolor{comment}{/* Below is a partial copy of}}
\DoxyCodeLine{20 \textcolor{comment}{ * https://raw.githubusercontent.com/torvalds/linux/22c033989c3eb9731ad0c497dfab4231b8e367d6/include/linux/unaligned/packed\_struct.h}}
\DoxyCodeLine{21 \textcolor{comment}{ * with an osmo\_ prefix applied to avoid any collisions.}}
\DoxyCodeLine{22 \textcolor{comment}{ */}}
\DoxyCodeLine{23 \textcolor{keyword}{struct }osmo\_unaligned\_cpu32 \{}
\DoxyCodeLine{24         uint32\_t x;}
\DoxyCodeLine{25 \} \_\_attribute\_\_((\_\_packed\_\_));}
\DoxyCodeLine{26 }
\DoxyCodeLine{27 \textcolor{keyword}{static} \textcolor{keyword}{inline} uint32\_t osmo\_get\_unaligned\_cpu32(\textcolor{keyword}{const} \textcolor{keywordtype}{void} *p)}
\DoxyCodeLine{28 \{}
\DoxyCodeLine{29         \textcolor{keyword}{const} \textcolor{keyword}{struct }osmo\_unaligned\_cpu32 *ptr = (\textcolor{keyword}{const} \textcolor{keyword}{struct }osmo\_unaligned\_cpu32 *)p;}
\DoxyCodeLine{30         \textcolor{keywordflow}{return} ptr-\/>x;}
\DoxyCodeLine{31 \}}
\DoxyCodeLine{32 }
\DoxyCodeLine{33 \textcolor{comment}{/* Below is a partial copy of}}
\DoxyCodeLine{34 \textcolor{comment}{ * https://raw.githubusercontent.com/torvalds/linux/79e3ea5aab48c83de9410e43b52895406847eca7/tools/include/linux/jhash.h}}
\DoxyCodeLine{35 \textcolor{comment}{ * with an osmo\_ prefix applied to avoid any collisions.}}
\DoxyCodeLine{36 \textcolor{comment}{ */}}
\DoxyCodeLine{37 \textcolor{comment}{/* jhash.h: Jenkins hash support.}}
\DoxyCodeLine{38 \textcolor{comment}{ *}}
\DoxyCodeLine{39 \textcolor{comment}{ * Copyright (C) 2006. Bob Jenkins (bob\_jenkins@burtleburtle.net)}}
\DoxyCodeLine{40 \textcolor{comment}{ *}}
\DoxyCodeLine{41 \textcolor{comment}{ * https://burtleburtle.net/bob/hash/}}
\DoxyCodeLine{42 \textcolor{comment}{ *}}
\DoxyCodeLine{43 \textcolor{comment}{ * These are the credits from Bob's sources:}}
\DoxyCodeLine{44 \textcolor{comment}{ *}}
\DoxyCodeLine{45 \textcolor{comment}{ * lookup3.c, by Bob Jenkins, May 2006, Public Domain.}}
\DoxyCodeLine{46 \textcolor{comment}{ *}}
\DoxyCodeLine{47 \textcolor{comment}{ * These are functions for producing 32-\/bit hashes for hash table lookup.}}
\DoxyCodeLine{48 \textcolor{comment}{ * hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final()}}
\DoxyCodeLine{49 \textcolor{comment}{ * are externally useful functions.  Routines to test the hash are included}}
\DoxyCodeLine{50 \textcolor{comment}{ * if SELF\_TEST is defined.  You can use this free for any purpose.  It's in}}
\DoxyCodeLine{51 \textcolor{comment}{ * the public domain.  It has no warranty.}}
\DoxyCodeLine{52 \textcolor{comment}{ *}}
\DoxyCodeLine{53 \textcolor{comment}{ * Copyright (C) 2009-\/2010 Jozsef Kadlecsik (kadlec@blackhole.kfki.hu)}}
\DoxyCodeLine{54 \textcolor{comment}{ *}}
\DoxyCodeLine{55 \textcolor{comment}{ * I've modified Bob's hash to be useful in the Linux kernel, and}}
\DoxyCodeLine{56 \textcolor{comment}{ * any bugs present are my fault.}}
\DoxyCodeLine{57 \textcolor{comment}{ * Jozsef}}
\DoxyCodeLine{58 \textcolor{comment}{ */}}
\DoxyCodeLine{59 }
\DoxyCodeLine{60 \textcolor{comment}{/* OSMO\_JHASH\_MIX -\/-\/ mix 3 32-\/bit values reversibly. */}}
\DoxyCodeLine{61 \textcolor{preprocessor}{\#define OSMO\_JHASH\_MIX(a, b, c)                 \(\backslash\)}}
\DoxyCodeLine{62 \textcolor{preprocessor}{\{                                               \(\backslash\)}}
\DoxyCodeLine{63 \textcolor{preprocessor}{        a -\/= c;  a \string^= osmo\_rol32(c, 4);  c += b;        \(\backslash\)}}
\DoxyCodeLine{64 \textcolor{preprocessor}{        b -\/= a;  b \string^= osmo\_rol32(a, 6);  a += c;        \(\backslash\)}}
\DoxyCodeLine{65 \textcolor{preprocessor}{        c -\/= b;  c \string^= osmo\_rol32(b, 8);  b += a;        \(\backslash\)}}
\DoxyCodeLine{66 \textcolor{preprocessor}{        a -\/= c;  a \string^= osmo\_rol32(c, 16); c += b;        \(\backslash\)}}
\DoxyCodeLine{67 \textcolor{preprocessor}{        b -\/= a;  b \string^= osmo\_rol32(a, 19); a += c;        \(\backslash\)}}
\DoxyCodeLine{68 \textcolor{preprocessor}{        c -\/= b;  c \string^= osmo\_rol32(b, 4);  b += a;        \(\backslash\)}}
\DoxyCodeLine{69 \textcolor{preprocessor}{\}}}
\DoxyCodeLine{70 }
\DoxyCodeLine{71 \textcolor{comment}{/* OSMO\_JHASH\_FINAL -\/ final mixing of 3 32-\/bit values (a,b,c) into c */}}
\DoxyCodeLine{72 \textcolor{preprocessor}{\#define OSMO\_JHASH\_FINAL(a, b, c)                       \(\backslash\)}}
\DoxyCodeLine{73 \textcolor{preprocessor}{\{                                               \(\backslash\)}}
\DoxyCodeLine{74 \textcolor{preprocessor}{        c \string^= b; c -\/= osmo\_rol32(b, 14);         \(\backslash\)}}
\DoxyCodeLine{75 \textcolor{preprocessor}{        a \string^= c; a -\/= osmo\_rol32(c, 11);         \(\backslash\)}}
\DoxyCodeLine{76 \textcolor{preprocessor}{        b \string^= a; b -\/= osmo\_rol32(a, 25);         \(\backslash\)}}
\DoxyCodeLine{77 \textcolor{preprocessor}{        c \string^= b; c -\/= osmo\_rol32(b, 16);         \(\backslash\)}}
\DoxyCodeLine{78 \textcolor{preprocessor}{        a \string^= c; a -\/= osmo\_rol32(c, 4);          \(\backslash\)}}
\DoxyCodeLine{79 \textcolor{preprocessor}{        b \string^= a; b -\/= osmo\_rol32(a, 14);         \(\backslash\)}}
\DoxyCodeLine{80 \textcolor{preprocessor}{        c \string^= b; c -\/= osmo\_rol32(b, 24);         \(\backslash\)}}
\DoxyCodeLine{81 \textcolor{preprocessor}{\}}}
\DoxyCodeLine{82 }
\DoxyCodeLine{83 \textcolor{comment}{/* An arbitrary initial parameter */}}
\DoxyCodeLine{84 \textcolor{preprocessor}{\#define JHASH\_INITVAL           0xdeadbeef}}
\DoxyCodeLine{85 }
\DoxyCodeLine{86 \textcolor{comment}{/* osmo\_jhash -\/ hash an arbitrary key}}
\DoxyCodeLine{87 \textcolor{comment}{ * @k: sequence of bytes as key}}
\DoxyCodeLine{88 \textcolor{comment}{ * @length: the length of the key}}
\DoxyCodeLine{89 \textcolor{comment}{ * @initval: the previous hash, or an arbitray value}}
\DoxyCodeLine{90 \textcolor{comment}{ *}}
\DoxyCodeLine{91 \textcolor{comment}{ * The generic version, hashes an arbitrary sequence of bytes.}}
\DoxyCodeLine{92 \textcolor{comment}{ * No alignment or length assumptions are made about the input key.}}
\DoxyCodeLine{93 \textcolor{comment}{ *}}
\DoxyCodeLine{94 \textcolor{comment}{ * Returns the hash value of the key. The result depends on endianness.}}
\DoxyCodeLine{95 \textcolor{comment}{ */}}
\DoxyCodeLine{96 \textcolor{keyword}{static} \textcolor{keyword}{inline} uint32\_t osmo\_jhash(\textcolor{keyword}{const} \textcolor{keywordtype}{void} *key, uint32\_t length, uint32\_t initval)}
\DoxyCodeLine{97 \{}
\DoxyCodeLine{98         uint32\_t a, b, c;}
\DoxyCodeLine{99         \textcolor{keyword}{const} uint8\_t *k = key;}
\DoxyCodeLine{100 }
\DoxyCodeLine{101         \textcolor{comment}{/* Set up the internal state */}}
\DoxyCodeLine{102         a = b = c = JHASH\_INITVAL + length + initval;}
\DoxyCodeLine{103 }
\DoxyCodeLine{104         \textcolor{comment}{/* All but the last block: affect some 32 bits of (a,b,c) */}}
\DoxyCodeLine{105         \textcolor{keywordflow}{while} (length > 12) \{}
\DoxyCodeLine{106                 a += osmo\_get\_unaligned\_cpu32(k);}
\DoxyCodeLine{107                 b += osmo\_get\_unaligned\_cpu32(k + 4);}
\DoxyCodeLine{108                 c += osmo\_get\_unaligned\_cpu32(k + 8);}
\DoxyCodeLine{109                 OSMO\_JHASH\_MIX(a, b, c);}
\DoxyCodeLine{110                 length -\/= 12;}
\DoxyCodeLine{111                 k += 12;}
\DoxyCodeLine{112         \}}
\DoxyCodeLine{113         \textcolor{comment}{/* Last block: affect all 32 bits of (c) */}}
\DoxyCodeLine{114         \textcolor{comment}{/* All the case statements fall through */}}
\DoxyCodeLine{115         \textcolor{keywordflow}{switch} (length) \{}
\DoxyCodeLine{116         \textcolor{keywordflow}{case} 12: c += (uint32\_t)k[11]<<24;}
\DoxyCodeLine{117         \textcolor{keywordflow}{case} 11: c += (uint32\_t)k[10]<<16;}
\DoxyCodeLine{118         \textcolor{keywordflow}{case} 10: c += (uint32\_t)k[9]<<8;}
\DoxyCodeLine{119         \textcolor{keywordflow}{case} 9:  c += k[8];}
\DoxyCodeLine{120         \textcolor{keywordflow}{case} 8:  b += (uint32\_t)k[7]<<24;}
\DoxyCodeLine{121         \textcolor{keywordflow}{case} 7:  b += (uint32\_t)k[6]<<16;}
\DoxyCodeLine{122         \textcolor{keywordflow}{case} 6:  b += (uint32\_t)k[5]<<8;}
\DoxyCodeLine{123         \textcolor{keywordflow}{case} 5:  b += k[4];}
\DoxyCodeLine{124         \textcolor{keywordflow}{case} 4:  a += (uint32\_t)k[3]<<24;}
\DoxyCodeLine{125         \textcolor{keywordflow}{case} 3:  a += (uint32\_t)k[2]<<16;}
\DoxyCodeLine{126         \textcolor{keywordflow}{case} 2:  a += (uint32\_t)k[1]<<8;}
\DoxyCodeLine{127         \textcolor{keywordflow}{case} 1:  a += k[0];}
\DoxyCodeLine{128                  OSMO\_JHASH\_FINAL(a, b, c);}
\DoxyCodeLine{129         \textcolor{keywordflow}{case} 0: \textcolor{comment}{/* Nothing left to add */}}
\DoxyCodeLine{130                 \textcolor{keywordflow}{break};}
\DoxyCodeLine{131         \}}
\DoxyCodeLine{132 }
\DoxyCodeLine{133         \textcolor{keywordflow}{return} c;}
\DoxyCodeLine{134 \}}
\DoxyCodeLine{135 }
\DoxyCodeLine{136 \textcolor{comment}{/* osmo\_jhash2 -\/ hash an array of uint32\_t's}}
\DoxyCodeLine{137 \textcolor{comment}{ * @k: the key which must be an array of uint32\_t's}}
\DoxyCodeLine{138 \textcolor{comment}{ * @length: the number of uint32\_t's in the key}}
\DoxyCodeLine{139 \textcolor{comment}{ * @initval: the previous hash, or an arbitray value}}
\DoxyCodeLine{140 \textcolor{comment}{ *}}
\DoxyCodeLine{141 \textcolor{comment}{ * Returns the hash value of the key.}}
\DoxyCodeLine{142 \textcolor{comment}{ */}}
\DoxyCodeLine{143 \textcolor{keyword}{static} \textcolor{keyword}{inline} uint32\_t osmo\_jhash2(\textcolor{keyword}{const} uint32\_t *k, uint32\_t length, uint32\_t initval)}
\DoxyCodeLine{144 \{}
\DoxyCodeLine{145         uint32\_t a, b, c;}
\DoxyCodeLine{146 }
\DoxyCodeLine{147         \textcolor{comment}{/* Set up the internal state */}}
\DoxyCodeLine{148         a = b = c = JHASH\_INITVAL + (length<<2) + initval;}
\DoxyCodeLine{149 }
\DoxyCodeLine{150         \textcolor{comment}{/* Handle most of the key */}}
\DoxyCodeLine{151         \textcolor{keywordflow}{while} (length > 3) \{}
\DoxyCodeLine{152                 a += k[0];}
\DoxyCodeLine{153                 b += k[1];}
\DoxyCodeLine{154                 c += k[2];}
\DoxyCodeLine{155                 OSMO\_JHASH\_MIX(a, b, c);}
\DoxyCodeLine{156                 length -\/= 3;}
\DoxyCodeLine{157                 k += 3;}
\DoxyCodeLine{158         \}}
\DoxyCodeLine{159 }
\DoxyCodeLine{160         \textcolor{comment}{/* Handle the last 3 uint32\_t's: all the case statements fall through */}}
\DoxyCodeLine{161         \textcolor{keywordflow}{switch} (length) \{}
\DoxyCodeLine{162         \textcolor{keywordflow}{case} 3: c += k[2];}
\DoxyCodeLine{163         \textcolor{keywordflow}{case} 2: b += k[1];}
\DoxyCodeLine{164         \textcolor{keywordflow}{case} 1: a += k[0];}
\DoxyCodeLine{165                 OSMO\_JHASH\_FINAL(a, b, c);}
\DoxyCodeLine{166         \textcolor{keywordflow}{case} 0: \textcolor{comment}{/* Nothing left to add */}}
\DoxyCodeLine{167                 \textcolor{keywordflow}{break};}
\DoxyCodeLine{168         \}}
\DoxyCodeLine{169 }
\DoxyCodeLine{170         \textcolor{keywordflow}{return} c;}
\DoxyCodeLine{171 \}}

\end{DoxyCode}
