1 /* 2 * Copyright (c) 2010 The WebM project authors. All Rights Reserved. 3 * 4 * Use of this source code is governed by a BSD-style license 5 * that can be found in the LICENSE file in the root of the source 6 * tree. An additional intellectual property rights grant can be found 7 * in the file PATENTS. All contributing project authors may 8 * be found in the AUTHORS file in the root of the source tree. 9 */ 10 11 #ifndef VPX_VPX_PORTS_BITOPS_H_ 12 #define VPX_VPX_PORTS_BITOPS_H_ 13 14 #include <assert.h> 15 16 #include "vpx_ports/msvc.h" 17 18 #ifdef _MSC_VER 19 #if defined(_M_X64) || defined(_M_IX86) 20 #include <intrin.h> 21 #define USE_MSC_INTRINSICS 22 #endif 23 #endif 24 25 #ifdef __cplusplus 26 extern "C" { 27 #endif 28 29 // These versions of get_lsb() and get_msb() are only valid when n != 0 30 // because all of the optimized versions are undefined when n == 0: 31 // https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html 32 33 // use GNU builtins where available. 34 #if defined(__GNUC__) && \ 35 ((__GNUC__ == 3 && __GNUC_MINOR__ >= 4) || __GNUC__ >= 4) get_lsb(unsigned int n)36static INLINE int get_lsb(unsigned int n) { 37 assert(n != 0); 38 return __builtin_ctz(n); 39 } 40 get_msb(unsigned int n)41static INLINE int get_msb(unsigned int n) { 42 assert(n != 0); 43 return 31 ^ __builtin_clz(n); 44 } 45 #elif defined(USE_MSC_INTRINSICS) 46 #pragma intrinsic(_BitScanForward) 47 #pragma intrinsic(_BitScanReverse) 48 49 static INLINE int get_lsb(unsigned int n) { 50 unsigned long first_set_bit; // NOLINT(runtime/int) 51 _BitScanForward(&first_set_bit, n); 52 return first_set_bit; 53 } 54 55 static INLINE int get_msb(unsigned int n) { 56 unsigned long first_set_bit; 57 assert(n != 0); 58 _BitScanReverse(&first_set_bit, n); 59 return first_set_bit; 60 } 61 #undef USE_MSC_INTRINSICS 62 #else 63 static INLINE int get_lsb(unsigned int n) { 64 int i; 65 assert(n != 0); 66 for (i = 0; i < 32 && !(n & 1); ++i) n >>= 1; 67 return i; 68 } 69 70 // Returns (int)floor(log2(n)). n must be > 0. 71 static INLINE int get_msb(unsigned int n) { 72 int log = 0; 73 unsigned int value = n; 74 int i; 75 76 assert(n != 0); 77 78 for (i = 4; i >= 0; --i) { 79 const int shift = (1 << i); 80 const unsigned int x = value >> shift; 81 if (x != 0) { 82 value = x; 83 log += shift; 84 } 85 } 86 return log; 87 } 88 #endif 89 90 #ifdef __cplusplus 91 } // extern "C" 92 #endif 93 94 #endif // VPX_VPX_PORTS_BITOPS_H_ 95