1 /*
2 * Copyright (c) 2008-2024 Stefan Krah. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 *
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
24 * SUCH DAMAGE.
25 */
26
27
28 #ifndef LIBMPDEC_BITS_H_
29 #define LIBMPDEC_BITS_H_
30
31
32 #include "mpdecimal.h"
33
34
35 /* Check if n is a power of 2. */
36 static inline int
ispower2(mpd_size_t n)37 ispower2(mpd_size_t n)
38 {
39 return n != 0 && (n & (n-1)) == 0;
40 }
41
42 #if defined(ANSI)
43 /*
44 * Return the most significant bit position of n from 0 to 31 (63).
45 * Assumptions: n != 0.
46 */
47 static inline int
mpd_bsr(mpd_size_t n)48 mpd_bsr(mpd_size_t n)
49 {
50 int pos = 0;
51 mpd_size_t tmp;
52
53 #ifdef CONFIG_64
54 tmp = n >> 32;
55 if (tmp != 0) { n = tmp; pos += 32; }
56 #endif
57 tmp = n >> 16;
58 if (tmp != 0) { n = tmp; pos += 16; }
59 tmp = n >> 8;
60 if (tmp != 0) { n = tmp; pos += 8; }
61 tmp = n >> 4;
62 if (tmp != 0) { n = tmp; pos += 4; }
63 tmp = n >> 2;
64 if (tmp != 0) { n = tmp; pos += 2; }
65 tmp = n >> 1;
66 if (tmp != 0) { n = tmp; pos += 1; }
67
68 return pos + (int)n - 1;
69 }
70
71 /*
72 * Return the least significant bit position of n from 0 to 31 (63).
73 * Assumptions: n != 0.
74 */
75 static inline int
mpd_bsf(mpd_size_t n)76 mpd_bsf(mpd_size_t n)
77 {
78 int pos;
79
80 #ifdef CONFIG_64
81 pos = 63;
82 if (n & 0x00000000FFFFFFFFULL) { pos -= 32; } else { n >>= 32; }
83 if (n & 0x000000000000FFFFULL) { pos -= 16; } else { n >>= 16; }
84 if (n & 0x00000000000000FFULL) { pos -= 8; } else { n >>= 8; }
85 if (n & 0x000000000000000FULL) { pos -= 4; } else { n >>= 4; }
86 if (n & 0x0000000000000003ULL) { pos -= 2; } else { n >>= 2; }
87 if (n & 0x0000000000000001ULL) { pos -= 1; }
88 #else
89 pos = 31;
90 if (n & 0x000000000000FFFFUL) { pos -= 16; } else { n >>= 16; }
91 if (n & 0x00000000000000FFUL) { pos -= 8; } else { n >>= 8; }
92 if (n & 0x000000000000000FUL) { pos -= 4; } else { n >>= 4; }
93 if (n & 0x0000000000000003UL) { pos -= 2; } else { n >>= 2; }
94 if (n & 0x0000000000000001UL) { pos -= 1; }
95 #endif
96 return pos;
97 }
98 /* END ANSI */
99
100 #elif defined(ASM)
101 /*
102 * Bit scan reverse. Assumptions: a != 0.
103 */
104 static inline int
mpd_bsr(mpd_size_t a)105 mpd_bsr(mpd_size_t a)
106 {
107 mpd_size_t retval;
108
109 __asm__ (
110 #ifdef CONFIG_64
111 "bsrq %1, %0\n\t"
112 #else
113 "bsr %1, %0\n\t"
114 #endif
115 :"=r" (retval)
116 :"r" (a)
117 :"cc"
118 );
119
120 return (int)retval;
121 }
122
123 /*
124 * Bit scan forward. Assumptions: a != 0.
125 */
126 static inline int
mpd_bsf(mpd_size_t a)127 mpd_bsf(mpd_size_t a)
128 {
129 mpd_size_t retval;
130
131 __asm__ (
132 #ifdef CONFIG_64
133 "bsfq %1, %0\n\t"
134 #else
135 "bsf %1, %0\n\t"
136 #endif
137 :"=r" (retval)
138 :"r" (a)
139 :"cc"
140 );
141
142 return (int)retval;
143 }
144 /* END ASM */
145
146 #elif defined(MASM)
147 #include <intrin.h>
148 /*
149 * Bit scan reverse. Assumptions: a != 0.
150 */
151 static inline int __cdecl
mpd_bsr(mpd_size_t a)152 mpd_bsr(mpd_size_t a)
153 {
154 unsigned long retval;
155
156 #ifdef CONFIG_64
157 _BitScanReverse64(&retval, a);
158 #else
159 _BitScanReverse(&retval, a);
160 #endif
161
162 return (int)retval;
163 }
164
165 /*
166 * Bit scan forward. Assumptions: a != 0.
167 */
168 static inline int __cdecl
mpd_bsf(mpd_size_t a)169 mpd_bsf(mpd_size_t a)
170 {
171 unsigned long retval;
172
173 #ifdef CONFIG_64
174 _BitScanForward64(&retval, a);
175 #else
176 _BitScanForward(&retval, a);
177 #endif
178
179 return (int)retval;
180 }
181 /* END MASM (_MSC_VER) */
182
183 #else
184 #error "missing preprocessor definitions"
185 #endif /* BSR/BSF */
186
187
188 #endif /* LIBMPDEC_BITS_H_ */
189