1/* ----------------------------------------------------------------------- *
2 *
3 * Copyright 1996-2017 The NASM Authors - All Rights Reserved
4 * See the file AUTHORS included with the NASM distribution for
5 * the specific copyright holders.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following
9 * conditions are met:
10 *
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above
14 * copyright notice, this list of conditions and the following
15 * disclaimer in the documentation and/or other materials provided
16 * with the distribution.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
19 * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
20 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
21 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
23 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
25 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
26 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
28 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
29 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
30 * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 *
32 * ----------------------------------------------------------------------- */
33
34#ifndef ILOG2_H
35#define ILOG2_H
36
37#include "compiler.h"
38#include <limits.h>
39
40#ifdef ILOG2_C /* For generating the out-of-line functions */
41# undef extern_inline
42# define extern_inline
43# define inline_prototypes
44#endif
45
46#ifdef inline_prototypes
47extern int const_func ilog2_32(uint32_t v);
48extern int const_func ilog2_64(uint64_t v);
49extern int const_func ilog2_64(uint64_t vv);
50extern int const_func alignlog2_32(uint32_t v);
51extern int const_func alignlog2_64(uint64_t v);
52#endif
53
54#ifdef extern_inline
55
56#define ROUND(v, a, w) \
57 do { \
58 if (v & (((UINT32_C(1) << w) - 1) << w)) { \
59 a += w; \
60 v >>= w; \
61 } \
62 } while (0)
63
64
65#if defined(__GNUC__) && defined(__x86_64__)
66
67extern_inline int const_func ilog2_32(uint32_t v)
68{
69 int n;
70
71 __asm__("bsrl %1,%0"
72 : "=r" (n)
73 : "rm" (v), "0" (0));
74 return n;
75}
76
77#elif defined(__GNUC__) && defined(__i386__)
78
79extern_inline int const_func ilog2_32(uint32_t v)
80{
81 int n;
82
83#ifdef __i686__
84 __asm__("bsrl %1,%0 ; cmovz %2,%0\n"
85 : "=&r" (n)
86 : "rm" (v), "r" (0));
87#else
88 __asm__("bsrl %1,%0 ; jnz 1f ; xorl %0,%0\n"
89 "1:"
90 : "=&r" (n)
91 : "rm" (v));
92#endif
93 return n;
94}
95
96#elif defined(HAVE___BUILTIN_CLZ) && INT_MAX == 2147483647
97
98extern_inline int const_func ilog2_32(uint32_t v)
99{
100 if (!v)
101 return 0;
102
103 return __builtin_clz(v) ^ 31;
104}
105
106#elif defined(HAVE__BITSCANREVERSE)
107
108extern_inline int const_func ilog2_32(uint32_t v)
109{
110 unsigned long ix;
111 return _BitScanReverse(&ix, v) ? v : 0;
112}
113
114#else
115
116extern_inline int const_func ilog2_32(uint32_t v)
117{
118 int p = 0;
119
120 ROUND(v, p, 16);
121 ROUND(v, p, 8);
122 ROUND(v, p, 4);
123 ROUND(v, p, 2);
124 ROUND(v, p, 1);
125
126 return p;
127}
128
129#endif
130
131#if defined(__GNUC__) && defined(__x86_64__)
132
133extern_inline int const_func ilog2_64(uint64_t v)
134{
135 uint64_t n;
136
137 __asm__("bsrq %1,%0"
138 : "=r" (n)
139 : "rm" (v), "0" (UINT64_C(0)));
140 return n;
141}
142
143#elif defined(HAVE__BUILTIN_CLZLL) && LLONG_MAX == 9223372036854775807LL
144
145extern_inline int const_func ilog2_64(uint64_t v)
146{
147 if (!v)
148 return 0;
149
150 return __builtin_clzll(v) ^ 63;
151}
152
153#elif defined(HAVE__BITSCANREVERSE64)
154
155extern_inline int const_func ilog2_64(uint64_t v)
156{
157 unsigned long ix;
158 return _BitScanReverse64(&ix, v) ? ix : 0;
159}
160
161#else
162
163extern_inline int const_func ilog2_64(uint64_t vv)
164{
165 int p = 0;
166 uint32_t v;
167
168 v = vv >> 32;
169 if (v)
170 p += 32;
171 else
172 v = vv;
173
174 ROUND(v, p, 16);
175 ROUND(v, p, 8);
176 ROUND(v, p, 4);
177 ROUND(v, p, 2);
178 ROUND(v, p, 1);
179
180 return p;
181}
182
183#endif
184
185/*
186 * v == 0 ? 0 : is_power2(x) ? ilog2_X(v) : -1
187 */
188extern_inline int const_func alignlog2_32(uint32_t v)
189{
190 if (unlikely(v & (v-1)))
191 return -1; /* invalid alignment */
192
193 return ilog2_32(v);
194}
195
196extern_inline int const_func alignlog2_64(uint64_t v)
197{
198 if (unlikely(v & (v-1)))
199 return -1; /* invalid alignment */
200
201 return ilog2_64(v);
202}
203
204#undef ROUND
205
206#endif /* extern_inline */
207
208#endif /* ILOG2_H */
209