Coverage Report

Created: 2026-11-20 07:09

next uncovered line (L), next uncovered region (R), next uncovered branch (B)
/src/pdns/pdns/dnsdistdist/burtle.hh
Line
Count
Source
1
/*
2
 * This file is part of PowerDNS or dnsdist.
3
 * Copyright -- PowerDNS.COM B.V. and its contributors
4
 *
5
 * This program is free software; you can redistribute it and/or modify
6
 * it under the terms of version 2 of the GNU General Public License as
7
 * published by the Free Software Foundation.
8
 *
9
 * In addition, for the avoidance of any doubt, permission is granted to
10
 * link this program with OpenSSL and to (re)distribute the binaries
11
 * produced as the result of such linking.
12
 *
13
 * This program is distributed in the hope that it will be useful,
14
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16
 * GNU General Public License for more details.
17
 *
18
 * You should have received a copy of the GNU General Public License
19
 * along with this program; if not, write to the Free Software
20
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
21
 */
22
23
#pragma once
24
25
#include <cinttypes>
26
27
inline void burtlemix(uint32_t& a, uint32_t& b, uint32_t& c)
28
1.32M
{
29
1.32M
  a -= b;
30
1.32M
  a -= c;
31
1.32M
  a ^= (c >> 13);
32
1.32M
  b -= c;
33
1.32M
  b -= a;
34
1.32M
  b ^= (a << 8);
35
1.32M
  c -= a;
36
1.32M
  c -= b;
37
1.32M
  c ^= (b >> 13);
38
1.32M
  a -= b;
39
1.32M
  a -= c;
40
1.32M
  a ^= (c >> 12);
41
1.32M
  b -= c;
42
1.32M
  b -= a;
43
1.32M
  b ^= (a << 16);
44
1.32M
  c -= a;
45
1.32M
  c -= b;
46
1.32M
  c ^= (b >> 5);
47
1.32M
  a -= b;
48
1.32M
  a -= c;
49
1.32M
  a ^= (c >> 3);
50
1.32M
  b -= c;
51
1.32M
  b -= a;
52
1.32M
  b ^= (a << 10);
53
1.32M
  c -= a;
54
1.32M
  c -= b;
55
1.32M
  c ^= (b >> 15);
56
1.32M
}
57
58
inline uint32_t burtle(const unsigned char* k, uint32_t length, uint32_t initval)
59
39.1k
{
60
39.1k
  uint32_t a, b, c, len;
61
62
  /* Set up the internal state */
63
39.1k
  len = length;
64
39.1k
  a = b = 0x9e3779b9; /* the golden ratio; an arbitrary value */
65
39.1k
  c = initval; /* the previous hash value */
66
67
  /*---------------------------------------- handle most of the key */
68
983k
  while (len >= 12) {
69
944k
    a += (k[0] + ((uint32_t)k[1] << 8) + ((uint32_t)k[2] << 16) + ((uint32_t)k[3] << 24));
70
944k
    b += (k[4] + ((uint32_t)k[5] << 8) + ((uint32_t)k[6] << 16) + ((uint32_t)k[7] << 24));
71
944k
    c += (k[8] + ((uint32_t)k[9] << 8) + ((uint32_t)k[10] << 16) + ((uint32_t)k[11] << 24));
72
944k
    burtlemix(a, b, c);
73
944k
    k += 12;
74
944k
    len -= 12;
75
944k
  }
76
77
  /*------------------------------------- handle the last 11 bytes */
78
39.1k
  c += length;
79
39.1k
  switch (len) { /* all the case statements fall through */
80
776
  case 11:
81
776
    c += ((uint32_t)k[10] << 24);
82
    /* fall-through */
83
5.83k
  case 10:
84
5.83k
    c += ((uint32_t)k[9] << 16);
85
    /* fall-through */
86
6.98k
  case 9:
87
6.98k
    c += ((uint32_t)k[8] << 8);
88
    /* the first byte of c is reserved for the length */
89
    /* fall-through */
90
9.65k
  case 8:
91
9.65k
    b += ((uint32_t)k[7] << 24);
92
    /* fall-through */
93
10.4k
  case 7:
94
10.4k
    b += ((uint32_t)k[6] << 16);
95
    /* fall-through */
96
11.6k
  case 6:
97
11.6k
    b += ((uint32_t)k[5] << 8);
98
    /* fall-through */
99
15.8k
  case 5:
100
15.8k
    b += k[4];
101
    /* fall-through */
102
31.4k
  case 4:
103
31.4k
    a += ((uint32_t)k[3] << 24);
104
    /* fall-through */
105
33.8k
  case 3:
106
33.8k
    a += ((uint32_t)k[2] << 16);
107
    /* fall-through */
108
34.9k
  case 2:
109
34.9k
    a += ((uint32_t)k[1] << 8);
110
    /* fall-through */
111
37.7k
  case 1:
112
37.7k
    a += k[0];
113
    /* case 0: nothing left to add */
114
39.1k
  }
115
39.1k
  burtlemix(a, b, c);
116
  /*-------------------------------------------- report the result */
117
39.1k
  return c;
118
39.1k
}
119
120
inline uint32_t burtleCI(const unsigned char* k, uint32_t length, uint32_t initval)
121
3.51k
{
122
3.51k
  uint32_t a, b, c, len;
123
124
  /* Set up the internal state */
125
3.51k
  len = length;
126
3.51k
  a = b = 0x9e3779b9; /* the golden ratio; an arbitrary value */
127
3.51k
  c = initval; /* the previous hash value */
128
129
  /*---------------------------------------- handle most of the key */
130
339k
  while (len >= 12) {
131
336k
    a += (dns_tolower(k[0]) + ((uint32_t)dns_tolower(k[1]) << 8) + ((uint32_t)dns_tolower(k[2]) << 16) + ((uint32_t)dns_tolower(k[3]) << 24));
132
336k
    b += (dns_tolower(k[4]) + ((uint32_t)dns_tolower(k[5]) << 8) + ((uint32_t)dns_tolower(k[6]) << 16) + ((uint32_t)dns_tolower(k[7]) << 24));
133
336k
    c += (dns_tolower(k[8]) + ((uint32_t)dns_tolower(k[9]) << 8) + ((uint32_t)dns_tolower(k[10]) << 16) + ((uint32_t)dns_tolower(k[11]) << 24));
134
336k
    burtlemix(a, b, c);
135
336k
    k += 12;
136
336k
    len -= 12;
137
336k
  }
138
139
  /*------------------------------------- handle the last 11 bytes */
140
3.51k
  c += length;
141
3.51k
  switch (len) { /* all the case statements fall through */
142
56
  case 11:
143
56
    c += ((uint32_t)dns_tolower(k[10]) << 24);
144
    /* fall-through */
145
114
  case 10:
146
114
    c += ((uint32_t)dns_tolower(k[9]) << 16);
147
    /* fall-through */
148
134
  case 9:
149
134
    c += ((uint32_t)dns_tolower(k[8]) << 8);
150
    /* the first byte of c is reserved for the length */
151
    /* fall-through */
152
246
  case 8:
153
246
    b += ((uint32_t)dns_tolower(k[7]) << 24);
154
    /* fall-through */
155
330
  case 7:
156
330
    b += ((uint32_t)dns_tolower(k[6]) << 16);
157
    /* fall-through */
158
404
  case 6:
159
404
    b += ((uint32_t)dns_tolower(k[5]) << 8);
160
    /* fall-through */
161
472
  case 5:
162
472
    b += dns_tolower(k[4]);
163
    /* fall-through */
164
616
  case 4:
165
616
    a += ((uint32_t)dns_tolower(k[3]) << 24);
166
    /* fall-through */
167
926
  case 3:
168
926
    a += ((uint32_t)dns_tolower(k[2]) << 16);
169
    /* fall-through */
170
978
  case 2:
171
978
    a += ((uint32_t)dns_tolower(k[1]) << 8);
172
    /* fall-through */
173
3.38k
  case 1:
174
3.38k
    a += dns_tolower(k[0]);
175
    /* case 0: nothing left to add */
176
3.51k
  }
177
3.51k
  burtlemix(a, b, c);
178
  /*-------------------------------------------- report the result */
179
3.51k
  return c;
180
3.51k
}
181
182
template <typename T>
183
inline uint32_t burtleCI(const T& k, uint32_t initval)
184
0
{
185
0
  return burtleCI(reinterpret_cast<const unsigned char*>(k.data()), k.length(), initval); // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast): can't static_cast because of sign difference
186
0
}