+/* Count leading zeros (for nonzero inputs) */
+
+/*
+ * On i386 and x86_64, we know clang and GCC will generate BSR for
+ * __builtin_clzl. This instruction IS NOT constant time on all micro-
+ * architectures, but it *is* constant time on all micro-architectures that
+ * have been used by Apple, and we expect that to continue to be the case.
+ *
+ * When building for x86_64h with clang, this produces LZCNT, which is exactly
+ * what we want.
+ *
+ * On arm and arm64, we know that clang and GCC generate the constant-time CLZ
+ * instruction from __builtin_clzl( ).
+ */
+
+#if defined(_WIN32)
+/* We use the Windows implementations below. */
+#elif defined(__x86_64__) || defined(__i386__) || defined(__arm64__) || defined(__arm__)
+/* We use a thought-to-be-good version of __builtin_clz. */
+#elif defined __GNUC__
+#warning Using __builtin_clz() on an unknown architecture; it may not be constant-time.
+/* If you find yourself seeing this warning, file a radar for someone to
+ * check whether or not __builtin_clz() generates a constant-time
+ * implementation on the architecture you are targeting. If it does, append
+ * the name of that architecture to the list of "safe" architectures above. */ */
+#endif
+
+
+#if defined(_WIN32)
+
+#include <windows.h>
+#include <intrin.h>
+
+CC_INLINE CC_CONST unsigned clz64_win(uint64_t value)
+{
+ DWORD leading_zero;
+ _BitScanReverse64(&leading_zero, value);
+ return 63 - leading_zero;
+}
+
+
+CC_INLINE CC_CONST unsigned clz32_win(uint32_t value)
+{
+ DWORD leading_zero;
+ _BitScanReverse(&leading_zero, value);
+ return 31 - leading_zero;
+}
+
+#endif
+
+CC_INLINE CC_CONST unsigned cc_clz32_fallback(uint32_t data)
+{
+ unsigned int b = 0;
+ unsigned int bit = 0;
+ // Work from LSB to MSB
+ for (int i = 0; i < 32; i++) {
+ bit = (data >> i) & 1;
+ // If the bit is 0, update the "leading bits are zero" counter "b".
+ b += (1 - bit);
+ /* If the bit is 0, (bit - 1) is 0xffff... therefore b is retained.
+ * If the bit is 1, (bit - 1) is 0 therefore b is set to 0.
+ */
+ b &= (bit - 1);
+ }
+ return b;
+}
+
+CC_INLINE CC_CONST unsigned cc_clz64_fallback(uint64_t data)
+{
+ unsigned int b = 0;
+ unsigned int bit = 0;
+ // Work from LSB to MSB
+ for (int i = 0; i < 64; i++) {
+ bit = (data >> i) & 1;
+ // If the bit is 0, update the "leading bits are zero" counter.
+ b += (1 - bit);
+ /* If the bit is 0, (bit - 1) is 0xffff... therefore b is retained.
+ * If the bit is 1, (bit - 1) is 0 therefore b is set to 0.
+ */
+ b &= (bit - 1);
+ }
+ return b;
+}
+
+/*!
+ @function cc_clz32
+ @abstract Count leading zeros of a nonzero 32-bit value
+
+ @param data A nonzero 32-bit value
+
+ @result Count of leading zeros of @p data
+
+ @discussion @p data is assumed to be nonzero.
+*/
+CC_INLINE CC_CONST unsigned cc_clz32(uint32_t data) {
+#if defined(_WIN32)
+ return clz32_win(data);
+#elif defined(__x86_64__) || defined(__i386__) || defined(__arm64__) || defined(__arm__) || defined(__GNUC__)
+ cc_static_assert(sizeof(unsigned) == 4, "clz relies on an unsigned int being 4 bytes");
+ return (unsigned)__builtin_clz(data);
+#else
+ return cc_clz32_fallback(data);
+#endif
+}
+
+/*!
+ @function cc_clz64
+ @abstract Count leading zeros of a nonzero 64-bit value
+
+ @param data A nonzero 64-bit value
+
+ @result Count of leading zeros of @p data
+
+ @discussion @p data is assumed to be nonzero.
+*/
+CC_INLINE CC_CONST unsigned cc_clz64(uint64_t data) {
+#if defined(_WIN32)
+ return clz64_win(data);
+#elif defined(__x86_64__) || defined(__i386__) || defined(__arm64__) || defined(__arm__) || defined(__GNUC__)
+ return (unsigned)__builtin_clzll(data);
+#else
+ return cc_clz64_fallback(data);
+#endif
+}
+
projects / apple / xnu.git / blobdiff