1 /* MIT License
2 *
3 * Copyright (c) 2023 Brad House
4 *
5 * Permission is hereby granted, free of charge, to any person obtaining a copy
6 * of this software and associated documentation files (the "Software"), to deal
7 * in the Software without restriction, including without limitation the rights
8 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
9 * copies of the Software, and to permit persons to whom the Software is
10 * furnished to do so, subject to the following conditions:
11 *
12 * The above copyright notice and this permission notice (including the next
13 * paragraph) shall be included in all copies or substantial portions of the
14 * Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22 * SOFTWARE.
23 *
24 * SPDX-License-Identifier: MIT
25 */
26 #include "ares_setup.h"
27 #include "ares.h"
28 #include "ares_private.h"
29
30 /* Uses public domain code snippets from
31 * http://graphics.stanford.edu/~seander/bithacks.html */
32
ares__round_up_pow2_u32(unsigned int n)33 static unsigned int ares__round_up_pow2_u32(unsigned int n)
34 {
35 /* NOTE: if already a power of 2, will return itself, not the next */
36 n--;
37 n |= n >> 1;
38 n |= n >> 2;
39 n |= n >> 4;
40 n |= n >> 8;
41 n |= n >> 16;
42 n++;
43 return n;
44 }
45
ares__round_up_pow2_u64(ares_int64_t n)46 static ares_int64_t ares__round_up_pow2_u64(ares_int64_t n)
47 {
48 /* NOTE: if already a power of 2, will return itself, not the next */
49 n--;
50 n |= n >> 1;
51 n |= n >> 2;
52 n |= n >> 4;
53 n |= n >> 8;
54 n |= n >> 16;
55 n |= n >> 32;
56 n++;
57 return n;
58 }
59
ares__round_up_pow2(size_t n)60 size_t ares__round_up_pow2(size_t n)
61 {
62 if (sizeof(size_t) > 4) {
63 return (size_t)ares__round_up_pow2_u64((ares_int64_t)n);
64 }
65
66 return (size_t)ares__round_up_pow2_u32((unsigned int)n);
67 }
68
ares__log2(size_t n)69 size_t ares__log2(size_t n)
70 {
71 static const unsigned char tab32[32] = { 0, 1, 28, 2, 29, 14, 24, 3,
72 30, 22, 20, 15, 25, 17, 4, 8,
73 31, 27, 13, 23, 21, 19, 16, 7,
74 26, 12, 18, 6, 11, 5, 10, 9 };
75 static const unsigned char tab64[64] = {
76 63, 0, 58, 1, 59, 47, 53, 2, 60, 39, 48, 27, 54, 33, 42, 3,
77 61, 51, 37, 40, 49, 18, 28, 20, 55, 30, 34, 11, 43, 14, 22, 4,
78 62, 57, 46, 52, 38, 26, 32, 41, 50, 36, 17, 19, 29, 10, 13, 21,
79 56, 45, 25, 31, 35, 16, 9, 12, 44, 24, 15, 8, 23, 7, 6, 5
80 };
81
82 if (sizeof(size_t) == 4) {
83 return tab32[(n * 0x077CB531) >> 27];
84 }
85
86 return tab64[(n * 0x07EDD5E59A4E28C2) >> 58];
87 }
88
89 /* x^y */
ares__pow(size_t x,size_t y)90 size_t ares__pow(size_t x, size_t y)
91 {
92 size_t res = 1;
93
94 while (y > 0) {
95 /* If y is odd, multiply x with result */
96 if (y & 1) {
97 res = res * x;
98 }
99
100 /* y must be even now */
101 y = y >> 1; /* y /= 2; */
102 x = x * x; /* x^2 */
103 }
104
105 return res;
106 }
107
ares__count_digits(size_t n)108 size_t ares__count_digits(size_t n)
109 {
110 size_t digits;
111
112 for (digits = 0; n > 0; digits++) {
113 n /= 10;
114 }
115 if (digits == 0) {
116 digits = 1;
117 }
118
119 return digits;
120 }
121
ares__count_hexdigits(size_t n)122 size_t ares__count_hexdigits(size_t n)
123 {
124 size_t digits;
125
126 for (digits = 0; n > 0; digits++) {
127 n /= 16;
128 }
129 if (digits == 0) {
130 digits = 1;
131 }
132
133 return digits;
134 }
135
ares__count_bits_u8(unsigned char x)136 unsigned char ares__count_bits_u8(unsigned char x)
137 {
138 /* Implementation obtained from:
139 * http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetTable */
140 #define B2(n) n, n + 1, n + 1, n + 2
141 #define B4(n) B2(n), B2(n + 1), B2(n + 1), B2(n + 2)
142 #define B6(n) B4(n), B4(n + 1), B4(n + 1), B4(n + 2)
143 static const unsigned char lookup[256] = { B6(0), B6(1), B6(1), B6(2) };
144 return lookup[x];
145 }
146