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
27 #include "ares_private.h"
28
29 /* Uses public domain code snippets from
30 * http://graphics.stanford.edu/~seander/bithacks.html */
31
ares_round_up_pow2_u32(unsigned int n)32 static unsigned int ares_round_up_pow2_u32(unsigned int n)
33 {
34 /* NOTE: if already a power of 2, will return itself, not the next */
35 n--;
36 n |= n >> 1;
37 n |= n >> 2;
38 n |= n >> 4;
39 n |= n >> 8;
40 n |= n >> 16;
41 n++;
42 return n;
43 }
44
ares_round_up_pow2_u64(ares_int64_t n)45 static ares_int64_t ares_round_up_pow2_u64(ares_int64_t n)
46 {
47 /* NOTE: if already a power of 2, will return itself, not the next */
48 n--;
49 n |= n >> 1;
50 n |= n >> 2;
51 n |= n >> 4;
52 n |= n >> 8;
53 n |= n >> 16;
54 n |= n >> 32;
55 n++;
56 return n;
57 }
58
ares_is_64bit(void)59 ares_bool_t ares_is_64bit(void)
60 {
61 #ifdef _MSC_VER
62 # pragma warning(push)
63 # pragma warning(disable : 4127)
64 #endif
65
66 return (sizeof(size_t) == 4) ? ARES_FALSE : ARES_TRUE;
67
68 #ifdef _MSC_VER
69 # pragma warning(pop)
70 #endif
71 }
72
ares_round_up_pow2(size_t n)73 size_t ares_round_up_pow2(size_t n)
74 {
75 if (ares_is_64bit()) {
76 return (size_t)ares_round_up_pow2_u64((ares_int64_t)n);
77 }
78
79 return (size_t)ares_round_up_pow2_u32((unsigned int)n);
80 }
81
ares_log2(size_t n)82 size_t ares_log2(size_t n)
83 {
84 static const unsigned char tab32[32] = { 0, 1, 28, 2, 29, 14, 24, 3,
85 30, 22, 20, 15, 25, 17, 4, 8,
86 31, 27, 13, 23, 21, 19, 16, 7,
87 26, 12, 18, 6, 11, 5, 10, 9 };
88 static const unsigned char tab64[64] = {
89 63, 0, 58, 1, 59, 47, 53, 2, 60, 39, 48, 27, 54, 33, 42, 3,
90 61, 51, 37, 40, 49, 18, 28, 20, 55, 30, 34, 11, 43, 14, 22, 4,
91 62, 57, 46, 52, 38, 26, 32, 41, 50, 36, 17, 19, 29, 10, 13, 21,
92 56, 45, 25, 31, 35, 16, 9, 12, 44, 24, 15, 8, 23, 7, 6, 5
93 };
94
95 if (!ares_is_64bit()) {
96 return tab32[(n * 0x077CB531) >> 27];
97 }
98
99 return tab64[(n * 0x07EDD5E59A4E28C2) >> 58];
100 }
101
102 /* x^y */
ares_pow(size_t x,size_t y)103 size_t ares_pow(size_t x, size_t y)
104 {
105 size_t res = 1;
106
107 while (y > 0) {
108 /* If y is odd, multiply x with result */
109 if (y & 1) {
110 res = res * x;
111 }
112
113 /* y must be even now */
114 y = y >> 1; /* y /= 2; */
115 x = x * x; /* x^2 */
116 }
117
118 return res;
119 }
120
ares_count_digits(size_t n)121 size_t ares_count_digits(size_t n)
122 {
123 size_t digits;
124
125 for (digits = 0; n > 0; digits++) {
126 n /= 10;
127 }
128 if (digits == 0) {
129 digits = 1;
130 }
131
132 return digits;
133 }
134
ares_count_hexdigits(size_t n)135 size_t ares_count_hexdigits(size_t n)
136 {
137 size_t digits;
138
139 for (digits = 0; n > 0; digits++) {
140 n /= 16;
141 }
142 if (digits == 0) {
143 digits = 1;
144 }
145
146 return digits;
147 }
148
ares_count_bits_u8(unsigned char x)149 unsigned char ares_count_bits_u8(unsigned char x)
150 {
151 /* Implementation obtained from:
152 * http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetTable */
153 #define B2(n) n, n + 1, n + 1, n + 2
154 #define B4(n) B2(n), B2(n + 1), B2(n + 1), B2(n + 2)
155 #define B6(n) B4(n), B4(n + 1), B4(n + 1), B4(n + 2)
156 static const unsigned char lookup[256] = { B6(0), B6(1), B6(1), B6(2) };
157 return lookup[x];
158 }
159