diff options
author | zxu <zxu@google.com> | 2018-01-27 17:53:27 -0500 |
---|---|---|
committer | Gil <mcg@google.com> | 2018-01-27 14:53:27 -0800 |
commit | af6976a907b0d2a9fadbb14d7258bab44f075364 (patch) | |
tree | 62918ca2d8da0696967e3003e495ba11cd56bf33 /Firestore/core/src/firebase/firestore/util/bits.h | |
parent | 7226b4adf38e4732dfb9a840d25f86d3e5533bdb (diff) |
normalize and port the rest of Firebase/Port code (#713)
* normalize bits
* normalize ordered_code
Diffstat (limited to 'Firestore/core/src/firebase/firestore/util/bits.h')
-rw-r--r-- | Firestore/core/src/firebase/firestore/util/bits.h | 166 |
1 files changed, 166 insertions, 0 deletions
diff --git a/Firestore/core/src/firebase/firestore/util/bits.h b/Firestore/core/src/firebase/firestore/util/bits.h new file mode 100644 index 0000000..185273f --- /dev/null +++ b/Firestore/core/src/firebase/firestore/util/bits.h @@ -0,0 +1,166 @@ +/* + * Copyright 2017 Google + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_BITS_H_ +#define FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_BITS_H_ + +// Various bit-twiddling functions, all of which are static members of the Bits +// class (making it effectively a namespace). Operands are unsigned integers. +// Munging bits in _signed_ integers is fraught with peril! For example, +// -5 << n has undefined behavior (for some values of n). + +#include <stdint.h> + +class Bits_Port32_Test; +class Bits_Port64_Test; + +namespace firebase { +namespace firestore { +namespace util { + +class Bits { + public: + /** Return floor(log2(n)) for positive integer n. Returns -1 iff n == 0. */ + static int Log2Floor(uint32_t n); + static int Log2Floor64(uint64_t n); + + /** + * Potentially faster version of Log2Floor() that returns an + * undefined value if n == 0. + */ + static int Log2FloorNonZero(uint32_t n); + static int Log2FloorNonZero64(uint64_t n); + + private: + // Portable implementations. + static int Log2Floor_Portable(uint32_t n); + static int Log2Floor64_Portable(uint64_t n); + static int Log2FloorNonZero_Portable(uint32_t n); + static int Log2FloorNonZero64_Portable(uint64_t n); + + Bits(Bits const&) = delete; + void operator=(Bits const&) = delete; + + // Allow tests to call _Portable variants directly. + friend class Bits_Port32_Test; + friend class Bits_Port64_Test; +}; + +// ------------------------------------------------------------------------ +// Implementation details follow +// ------------------------------------------------------------------------ + +#if defined(__GNUC__) + +inline int Bits::Log2Floor(uint32_t n) { + return n == 0 ? -1 : 31 ^ __builtin_clz(n); +} + +inline int Bits::Log2FloorNonZero(uint32_t n) { + return 31 ^ __builtin_clz(n); +} + +inline int Bits::Log2Floor64(uint64_t n) { + return n == 0 ? -1 : 63 ^ __builtin_clzll(n); +} + +inline int Bits::Log2FloorNonZero64(uint64_t n) { + return 63 ^ __builtin_clzll(n); +} + +#elif defined(COMPILER_MSVC) + +inline int Bits::Log2FloorNonZero(uint32 n) { +#ifdef _M_IX86 + _asm { + bsr ebx, n + mov n, ebx + } + return n; +#else + return Bits::Log2FloorNonZero_Portable(n); +#endif +} + +inline int Bits::Log2Floor(uint32 n) { +#ifdef _M_IX86 + _asm { + xor ebx, ebx + mov eax, n + and eax, eax + jz return_ebx + bsr ebx, eax + return_ebx: + mov n, ebx + } + return n; +#else + return Bits::Log2Floor_Portable(n); +#endif +} + +inline int Bits::Log2Floor64(uint64_t n) { + return Bits::Log2Floor64_Portable(n); +} + +inline int Bits::Log2FloorNonZero64(uint64_t n) { + return Bits::Log2FloorNonZero64_Portable(n); +} + +#else // !__GNUC__ && !COMPILER_MSVC + +inline int Bits::Log2Floor64(uint64_t n) { + return Bits::Log2Floor64_Portable(n); +} + +inline int Bits::Log2FloorNonZero64(uint64_t n) { + return Bits::Log2FloorNonZero64_Portable(n); +} + +#endif + +inline int Bits::Log2FloorNonZero_Portable(uint32_t n) { + // Just use the common routine + return Log2Floor(n); +} + +// Log2Floor64() is defined in terms of Log2Floor32(), Log2FloorNonZero32() +inline int Bits::Log2Floor64_Portable(uint64_t n) { + const uint32_t topbits = static_cast<uint32_t>(n >> 32); + if (topbits == 0) { + // Top bits are zero, so scan in bottom bits + return Log2Floor(static_cast<uint32_t>(n)); + } else { + return 32 + Log2FloorNonZero(topbits); + } +} + +// Log2FloorNonZero64() is defined in terms of Log2FloorNonZero32() +inline int Bits::Log2FloorNonZero64_Portable(uint64_t n) { + const uint32_t topbits = static_cast<uint32_t>(n >> 32); + if (topbits == 0) { + // Top bits are zero, so scan in bottom bits + return Log2FloorNonZero(static_cast<uint32_t>(n)); + } else { + return 32 + Log2FloorNonZero(topbits); + } +} + +} // namespace util +} // namespace firestore +} // namespace firebase + +#endif // FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_BITS_H_ |