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