1 /* 2 * Copyright (c) 2008-2016 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 BITS_H 30 #define BITS_H 31 32 33 #include "mpdecimal.h" 34 #include <stdio.h> 35 36 37 /* Check if n is a power of 2. */ 38 static inline int 39 ispower2(mpd_size_t n) 40 { 41 return n != 0 && (n & (n-1)) == 0; 42 } 43 44 #if defined(ANSI) 45 /* 46 * Return the most significant bit position of n from 0 to 31 (63). 47 * Assumptions: n != 0. 48 */ 49 static inline int 50 mpd_bsr(mpd_size_t n) 51 { 52 int pos = 0; 53 mpd_size_t tmp; 54 55 #ifdef CONFIG_64 56 tmp = n >> 32; 57 if (tmp != 0) { n = tmp; pos += 32; } 58 #endif 59 tmp = n >> 16; 60 if (tmp != 0) { n = tmp; pos += 16; } 61 tmp = n >> 8; 62 if (tmp != 0) { n = tmp; pos += 8; } 63 tmp = n >> 4; 64 if (tmp != 0) { n = tmp; pos += 4; } 65 tmp = n >> 2; 66 if (tmp != 0) { n = tmp; pos += 2; } 67 tmp = n >> 1; 68 if (tmp != 0) { n = tmp; pos += 1; } 69 70 return pos + (int)n - 1; 71 } 72 73 /* 74 * Return the least significant bit position of n from 0 to 31 (63). 75 * Assumptions: n != 0. 76 */ 77 static inline int 78 mpd_bsf(mpd_size_t n) 79 { 80 int pos; 81 82 #ifdef CONFIG_64 83 pos = 63; 84 if (n & 0x00000000FFFFFFFFULL) { pos -= 32; } else { n >>= 32; } 85 if (n & 0x000000000000FFFFULL) { pos -= 16; } else { n >>= 16; } 86 if (n & 0x00000000000000FFULL) { pos -= 8; } else { n >>= 8; } 87 if (n & 0x000000000000000FULL) { pos -= 4; } else { n >>= 4; } 88 if (n & 0x0000000000000003ULL) { pos -= 2; } else { n >>= 2; } 89 if (n & 0x0000000000000001ULL) { pos -= 1; } 90 #else 91 pos = 31; 92 if (n & 0x000000000000FFFFUL) { pos -= 16; } else { n >>= 16; } 93 if (n & 0x00000000000000FFUL) { pos -= 8; } else { n >>= 8; } 94 if (n & 0x000000000000000FUL) { pos -= 4; } else { n >>= 4; } 95 if (n & 0x0000000000000003UL) { pos -= 2; } else { n >>= 2; } 96 if (n & 0x0000000000000001UL) { pos -= 1; } 97 #endif 98 return pos; 99 } 100 /* END ANSI */ 101 102 #elif defined(ASM) 103 /* 104 * Bit scan reverse. Assumptions: a != 0. 105 */ 106 static inline int 107 mpd_bsr(mpd_size_t a) 108 { 109 mpd_size_t retval; 110 111 __asm__ ( 112 #ifdef CONFIG_64 113 "bsrq %1, %0\n\t" 114 #else 115 "bsr %1, %0\n\t" 116 #endif 117 :"=r" (retval) 118 :"r" (a) 119 :"cc" 120 ); 121 122 return (int)retval; 123 } 124 125 /* 126 * Bit scan forward. Assumptions: a != 0. 127 */ 128 static inline int 129 mpd_bsf(mpd_size_t a) 130 { 131 mpd_size_t retval; 132 133 __asm__ ( 134 #ifdef CONFIG_64 135 "bsfq %1, %0\n\t" 136 #else 137 "bsf %1, %0\n\t" 138 #endif 139 :"=r" (retval) 140 :"r" (a) 141 :"cc" 142 ); 143 144 return (int)retval; 145 } 146 /* END ASM */ 147 148 #elif defined(MASM) 149 #include <intrin.h> 150 /* 151 * Bit scan reverse. Assumptions: a != 0. 152 */ 153 static inline int __cdecl 154 mpd_bsr(mpd_size_t a) 155 { 156 unsigned long retval; 157 158 #ifdef CONFIG_64 159 _BitScanReverse64(&retval, a); 160 #else 161 _BitScanReverse(&retval, a); 162 #endif 163 164 return (int)retval; 165 } 166 167 /* 168 * Bit scan forward. Assumptions: a != 0. 169 */ 170 static inline int __cdecl 171 mpd_bsf(mpd_size_t a) 172 { 173 unsigned long retval; 174 175 #ifdef CONFIG_64 176 _BitScanForward64(&retval, a); 177 #else 178 _BitScanForward(&retval, a); 179 #endif 180 181 return (int)retval; 182 } 183 /* END MASM (_MSC_VER) */ 184 #else 185 #error "missing preprocessor definitions" 186 #endif /* BSR/BSF */ 187 188 189 #endif /* BITS_H */ 190 191 192 193
