1 /* Copyright 2015 The TensorFlow Authors. All Rights Reserved. 2 3 Licensed under the Apache License, Version 2.0 (the "License"); 4 you may not use this file except in compliance with the License. 5 You may obtain a copy of the License at 6 7 http://www.apache.org/licenses/LICENSE-2.0 8 9 Unless required by applicable law or agreed to in writing, software 10 distributed under the License is distributed on an "AS IS" BASIS, 11 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 See the License for the specific language governing permissions and 13 limitations under the License. 14 ==============================================================================*/ 15 16 #ifndef TENSORFLOW_LIB_CORE_BITS_H_ 17 #define TENSORFLOW_LIB_CORE_BITS_H_ 18 19 #include "tensorflow/core/platform/logging.h" 20 #include "tensorflow/core/platform/types.h" 21 22 namespace tensorflow { 23 24 // Return floor(log2(n)) for positive integer n. Returns -1 iff n == 0. 25 int Log2Floor(uint32 n); 26 int Log2Floor64(uint64 n); 27 28 // Return ceiling(log2(n)) for positive integer n. Returns -1 iff n == 0. 29 int Log2Ceiling(uint32 n); 30 int Log2Ceiling64(uint64 n); 31 32 // ------------------------------------------------------------------------ 33 // Implementation details follow 34 // ------------------------------------------------------------------------ 35 36 #if defined(__GNUC__) 37 38 // Return floor(log2(n)) for positive integer n. Returns -1 iff n == 0. 39 inline int Log2Floor(uint32 n) { return n == 0 ? -1 : 31 ^ __builtin_clz(n); } 40 41 // Return floor(log2(n)) for positive integer n. Returns -1 iff n == 0. 42 inline int Log2Floor64(uint64 n) { 43 return n == 0 ? -1 : 63 ^ __builtin_clzll(n); 44 } 45 46 #else 47 48 // Return floor(log2(n)) for positive integer n. Returns -1 iff n == 0. 49 inline int Log2Floor(uint32 n) { 50 if (n == 0) return -1; 51 int log = 0; 52 uint32 value = n; 53 for (int i = 4; i >= 0; --i) { 54 int shift = (1 << i); 55 uint32 x = value >> shift; 56 if (x != 0) { 57 value = x; 58 log += shift; 59 } 60 } 61 assert(value == 1); 62 return log; 63 } 64 65 // Return floor(log2(n)) for positive integer n. Returns -1 iff n == 0. 66 // Log2Floor64() is defined in terms of Log2Floor32() 67 inline int Log2Floor64(uint64 n) { 68 const uint32 topbits = static_cast<uint32>(n >> 32); 69 if (topbits == 0) { 70 // Top bits are zero, so scan in bottom bits 71 return Log2Floor(static_cast<uint32>(n)); 72 } else { 73 return 32 + Log2Floor(topbits); 74 } 75 } 76 77 #endif 78 79 inline int Log2Ceiling(uint32 n) { 80 int floor = Log2Floor(n); 81 if (n == (n & ~(n - 1))) // zero or a power of two 82 return floor; 83 else 84 return floor + 1; 85 } 86 87 inline int Log2Ceiling64(uint64 n) { 88 int floor = Log2Floor64(n); 89 if (n == (n & ~(n - 1))) // zero or a power of two 90 return floor; 91 else 92 return floor + 1; 93 } 94 95 inline uint32 NextPowerOfTwo(uint32 value) { 96 int exponent = Log2Ceiling(value); 97 DCHECK_LT(exponent, std::numeric_limits<uint32>::digits); 98 return 1 << exponent; 99 } 100 101 inline uint64 NextPowerOfTwo64(uint64 value) { 102 int exponent = Log2Ceiling(value); 103 DCHECK_LT(exponent, std::numeric_limits<uint64>::digits); 104 return 1LL << exponent; 105 } 106 107 } // namespace tensorflow 108 109 #endif // TENSORFLOW_LIB_CORE_BITS_H_ 110
