From 04a3ce66be2ffb141b96006966d1245789134121 Mon Sep 17 00:00:00 2001
From: Sage Weil <sage@redhat.com>
Date: Mon, 6 Jun 2016 17:38:33 -0400
Subject: [PATCH] include/intarith: add ctz/clz/cbits helpers

"Count trailing zero" and "count leading zero".

Signed-off-by: Sage Weil <sage@redhat.com>
---
 src/include/intarith.h      | 53 +++++++++++++++++++++++++++++++
 src/test/Makefile-client.am |  5 +++
 src/test/test_intarith.cc   | 63 +++++++++++++++++++++++++++++++++++++
 3 files changed, 121 insertions(+)
 create mode 100644 src/test/test_intarith.cc

diff --git a/src/include/intarith.h b/src/include/intarith.h
index 2c27cecd16dcb..5602b9c632b5c 100644
--- a/src/include/intarith.h
+++ b/src/include/intarith.h
@@ -35,4 +35,57 @@
 # define SHIFT_ROUND_UP(x,y) (((x)+(1<<(y))-1) >> (y))
 #endif
 
+// count trailing zeros.
+// NOTE: the builtin is nondeterministic on 0 input
+static inline unsigned ctz(unsigned v) {
+  if (v == 0)
+    return sizeof(v) * 8;
+  return __builtin_ctz(v);
+}
+static inline unsigned ctzl(unsigned long v) {
+  if (v == 0)
+    return sizeof(v) * 8;
+  return __builtin_ctzl(v);
+}
+static inline unsigned ctzll(unsigned long long v) {
+  if (v == 0)
+    return sizeof(v) * 8;
+  return __builtin_ctzll(v);
+}
+
+// count leading zeros
+// NOTE: the builtin is nondeterministic on 0 input
+static inline unsigned clz(unsigned v) {
+  if (v == 0)
+    return sizeof(v) * 8;
+  return __builtin_clz(v);
+}
+static inline unsigned clzl(unsigned long v) {
+  if (v == 0)
+    return sizeof(v) * 8;
+  return __builtin_clzl(v);
+}
+static inline unsigned clzll(unsigned long long v) {
+  if (v == 0)
+    return sizeof(v) * 8;
+  return __builtin_clzll(v);
+}
+
+// count bits (set + any 0's that follow)
+static inline unsigned cbits(unsigned v) {
+  if (v == 0)
+    return 0;
+  return (sizeof(v) * 8) - __builtin_clz(v);
+}
+static inline unsigned cbitsl(unsigned long v) {
+  if (v == 0)
+    return 0;
+  return (sizeof(v) * 8) - __builtin_clzl(v);
+}
+static inline unsigned cbitsll(unsigned long long v) {
+  if (v == 0)
+    return 0;
+  return (sizeof(v) * 8) - __builtin_clzll(v);
+}
+
 #endif
diff --git a/src/test/Makefile-client.am b/src/test/Makefile-client.am
index 686f2fc89ffa4..f934345584fbd 100644
--- a/src/test/Makefile-client.am
+++ b/src/test/Makefile-client.am
@@ -126,6 +126,11 @@ ceph_test_rados_watch_notify_LDADD = $(LIBRADOS) libsystest.la $(PTHREAD_LIBS)
 bin_DEBUGPROGRAMS += ceph_test_rados_watch_notify
 endif # LINUX
 
+unittest_intarith_SOURCES = test/test_intarith.cc
+unittest_intarith_LDADD = $(UNITTEST_LDADD)
+unittest_intarith_CXXFLAGS = $(UNITTEST_CXXFLAGS)
+check_TESTPROGRAMS += unittest_intarith
+
 unittest_librados_SOURCES = test/librados/librados.cc
 unittest_librados_LDADD = $(LIBRADOS) $(CEPH_GLOBAL) $(UNITTEST_LDADD)
 unittest_librados_CXXFLAGS = $(UNITTEST_CXXFLAGS)
diff --git a/src/test/test_intarith.cc b/src/test/test_intarith.cc
new file mode 100644
index 0000000000000..0843469bdb92b
--- /dev/null
+++ b/src/test/test_intarith.cc
@@ -0,0 +1,63 @@
+// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
+// vim: ts=8 sw=2 smarttab
+
+#include <iostream>
+#include <gtest/gtest.h>
+
+#include "include/intarith.h"
+
+TEST(intarith, cbits) {
+  ASSERT_EQ(0u, cbits(0));
+  ASSERT_EQ(1u, cbits(1));
+  ASSERT_EQ(2u, cbits(2));
+  ASSERT_EQ(2u, cbits(3));
+  ASSERT_EQ(3u, cbits(4));
+  ASSERT_EQ(0u, cbitsl(0));
+  ASSERT_EQ(1u, cbitsl(1));
+  ASSERT_EQ(2u, cbitsl(2));
+  ASSERT_EQ(2u, cbitsl(3));
+  ASSERT_EQ(3u, cbitsl(4));
+  ASSERT_EQ(9u, cbits(0x100));
+  ASSERT_EQ(32u, cbits(0xffffffff));
+  ASSERT_EQ(32u, cbitsl(0xffffffff));
+  ASSERT_EQ(32u, cbitsll(0xffffffff));
+  ASSERT_EQ(64u, cbitsll(0xffffffffffffffff));
+}
+
+TEST(intarith, clz) {
+  ASSERT_EQ(32u, clz(0));
+  ASSERT_EQ(31u, clz(1));
+  ASSERT_EQ(30u, clz(2));
+  ASSERT_EQ(30u, clz(3));
+  ASSERT_EQ(29u, clz(4));
+  ASSERT_EQ(64u, clzll(0));
+  ASSERT_EQ(63u, clzll(1));
+  ASSERT_EQ(62u, clzll(2));
+  ASSERT_EQ(62u, clzll(3));
+  ASSERT_EQ(61u, clzll(4));
+  ASSERT_EQ(23u, clz(0x100));
+  ASSERT_EQ(55u, clzll(0x100));
+  ASSERT_EQ(0u, clz(0xffffffff));
+  ASSERT_EQ(32u, clzll(0xffffffff));
+  ASSERT_EQ(0u, clzll(0xffffffffffffffff));
+}
+
+TEST(intarith, ctz) {
+  ASSERT_EQ(32u, ctz(0));
+  ASSERT_EQ(0u, ctz(1));
+  ASSERT_EQ(1u, ctz(2));
+  ASSERT_EQ(0u, ctz(3));
+  ASSERT_EQ(2u, ctz(4));
+  ASSERT_EQ(64u, ctzll(0));
+  ASSERT_EQ(0u, ctzll(1));
+  ASSERT_EQ(1u, ctzll(2));
+  ASSERT_EQ(0u, ctzll(3));
+  ASSERT_EQ(2u, ctzll(4));
+  ASSERT_EQ(8u, ctz(0x100));
+  ASSERT_EQ(8u, ctzll(0x100));
+  ASSERT_EQ(0u, ctz(0xffffffff));
+  ASSERT_EQ(0u, ctzl(0xffffffff));
+  ASSERT_EQ(0u, ctzll(0xffffffff));
+  ASSERT_EQ(20u, ctzll(0xffffffff00000));
+  ASSERT_EQ(48u, ctzll(0xff000000000000ull));
+}
-- 
2.39.5