1 /* 2 * Copyright 2011-2015 Samy Al Bahra. 3 * Copyright 2011 David Joseph. 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 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 * Several of these are from: http://graphics.stanford.edu/~seander/bithacks.html 30 */ 31 32 #define CK_INTERNAL_LOG_0 (0xAAAAAAAA) 33 #define CK_INTERNAL_LOG_1 (0xCCCCCCCC) 34 #define CK_INTERNAL_LOG_2 (0xF0F0F0F0) 35 #define CK_INTERNAL_LOG_3 (0xFF00FF00) 36 #define CK_INTERNAL_LOG_4 (0xFFFF0000) 37 38 CK_CC_INLINE static uint32_t 39 ck_internal_log(uint32_t v) 40 { 41 uint32_t r = (v & CK_INTERNAL_LOG_0) != 0; 42 43 r |= ((v & CK_INTERNAL_LOG_4) != 0) << 4; 44 r |= ((v & CK_INTERNAL_LOG_3) != 0) << 3; 45 r |= ((v & CK_INTERNAL_LOG_2) != 0) << 2; 46 r |= ((v & CK_INTERNAL_LOG_1) != 0) << 1; 47 return (r); 48 } 49 50 CK_CC_INLINE static uint32_t 51 ck_internal_power_2(uint32_t v) 52 { 53 54 --v; 55 v |= v >> 1; 56 v |= v >> 2; 57 v |= v >> 4; 58 v |= v >> 8; 59 v |= v >> 16; 60 return (++v); 61 } 62 63 CK_CC_INLINE static unsigned long 64 ck_internal_max(unsigned long x, unsigned long y) 65 { 66 67 return x ^ ((x ^ y) & -(x < y)); 68 } 69 70 CK_CC_INLINE static uint64_t 71 ck_internal_max_64(uint64_t x, uint64_t y) 72 { 73 74 return x ^ ((x ^ y) & -(x < y)); 75 } 76 77 CK_CC_INLINE static uint32_t 78 ck_internal_max_32(uint32_t x, uint32_t y) 79 { 80 81 return x ^ ((x ^ y) & -(x < y)); 82 } 83 84 CK_CC_INLINE static unsigned long 85 ck_internal_bsf(unsigned long v) 86 { 87 #if defined(__GNUC__) 88 return __builtin_ffs(v); 89 #else 90 unsigned int i; 91 const unsigned int s = sizeof(unsigned long) * 8 - 1; 92 93 for (i = 0; i < s; i++) { 94 if (v & (1UL << (s - i))) 95 return sizeof(unsigned long) * 8 - i; 96 } 97 98 return 1; 99 #endif /* !__GNUC__ */ 100 } 101 102 CK_CC_INLINE static uint64_t 103 ck_internal_bsf_64(uint64_t v) 104 { 105 #if defined(__GNUC__) 106 return __builtin_ffs(v); 107 #else 108 unsigned int i; 109 const unsigned int s = sizeof(unsigned long) * 8 - 1; 110 111 for (i = 0; i < s; i++) { 112 if (v & (1ULL << (63U - i))) 113 return i; 114 } 115 #endif /* !__GNUC__ */ 116 117 return 1; 118 } 119 120