Add a 32-bit version of CountDigits.

vitaut · vitaut · commit e9b219168955 · 2014-02-19T12:43:55.000-08:00
diff --git a/format-test.cc b/format-test.cc
@@ -170,6 +170,24 @@ TEST(UtilTest, Increment) {
   EXPECT_STREQ("200", s);
 }
 
+// Tests fmt::internal::CountDigits for integer type Int.
+template <typename Int>
+void TestCountDigits(Int) {
+  for (Int i = 0; i < 10; ++i)
+    EXPECT_EQ(1, fmt::internal::CountDigits(i));
+  for (Int i = 1, n = 1,
+       end = std::numeric_limits<Int>::max() / 10; n <= end; ++i) {
+    n *= 10;
+    EXPECT_EQ(i, fmt::internal::CountDigits(n - 1));
+    EXPECT_EQ(i + 1, fmt::internal::CountDigits(n));
+  }
+}
+
+TEST(UtilTest, CountDigits) {
+  TestCountDigits(uint32_t());
+  TestCountDigits(uint64_t());
+}
+
 class TestString {
  private:
   std::string value_;
@@ -1427,18 +1445,21 @@ TEST(FormatIntTest, FormatInt) {
   EXPECT_EQ(os.str(), fmt::FormatInt(std::numeric_limits<int64_t>::max()).str());
 }
 
-TEST(FormatIntTest, FormatDec) {
+template <typename T>
+std::string FormatDec(T value) {
   char buffer[10];
   char *ptr = buffer;
-  fmt::FormatDec(ptr, 42);
-  EXPECT_EQ(buffer + 2, ptr);
-  *ptr = '\0';
-  EXPECT_STREQ("42", buffer);
-  ptr = buffer;
-  fmt::FormatDec(ptr, -42);
-  *ptr = '\0';
-  EXPECT_EQ(buffer + 3, ptr);
-  EXPECT_STREQ("-42", buffer);
+  fmt::FormatDec(ptr, value);
+  return std::string(buffer, ptr);
+}
+
+TEST(FormatIntTest, FormatDec) {
+  EXPECT_EQ("42", FormatDec(42));
+  EXPECT_EQ("-42", FormatDec(-42));
+  EXPECT_EQ("42", FormatDec(42l));
+  EXPECT_EQ("42", FormatDec(42ul));
+  EXPECT_EQ("42", FormatDec(42ll));
+  EXPECT_EQ("42", FormatDec(42ull));
 }
 
 template <typename T>
diff --git a/format.cc b/format.cc
@@ -118,27 +118,23 @@ const char fmt::internal::DIGITS[] =
     "4041424344454647484950515253545556575859"
     "6061626364656667686970717273747576777879"
     "8081828384858687888990919293949596979899";
-    
-const uint64_t fmt::internal::POWERS_OF_10[] = {
+
+#define FMT_POWERS_OF_10(prefix) \
+  prefix 10, \
+  prefix 100, \
+  prefix 1000, \
+  prefix 10000, \
+  prefix 100000, \
+  prefix 1000000, \
+  prefix 10000000, \
+  prefix 100000000, \
+  prefix 1000000000
+
+const uint32_t fmt::internal::POWERS_OF_10_32[] = {0, FMT_POWERS_OF_10()};
+const uint64_t fmt::internal::POWERS_OF_10_64[] = {
   0,
-  10,
-  100,
-  1000,
-  10000,
-  100000,
-  1000000,
-  10000000,
-  100000000,
-  1000000000,
-  ULongLong(1000000000) * 10,
-  ULongLong(1000000000) * 100,
-  ULongLong(1000000000) * 1000,
-  ULongLong(1000000000) * 10000,
-  ULongLong(1000000000) * 100000,
-  ULongLong(1000000000) * 1000000,
-  ULongLong(1000000000) * 10000000,
-  ULongLong(1000000000) * 100000000,
-  ULongLong(1000000000) * 1000000000,
+  FMT_POWERS_OF_10(),
+  FMT_POWERS_OF_10(ULongLong(1000000000) *),
   ULongLong(1000000000) * ULongLong(1000000000) * 10
 };
 
diff --git a/format.h b/format.h
@@ -213,17 +213,32 @@ class CharTraits<wchar_t> : public BasicCharTraits<wchar_t> {
       const wchar_t *format, unsigned width, int precision, T value);
 };
 
+// Selects uint32_t if FitsIn32Bits is true, uint64_t otherwise.
+template <bool FitsIn32Bits>
+struct TypeSelector { typedef uint32_t Type; };
+
+template <>
+struct TypeSelector<false> { typedef uint64_t Type; };
+
+template <typename T>
+struct IntTraitsBase {
+  // Smallest of uint32_t and uint64_t that is large enough to represent
+  // all values of T.
+  typedef typename
+    TypeSelector<std::numeric_limits<T>::digits <= 32>::Type MainType;
+};
+
 // Information about an integer type.
 // IntTraits is not specialized for integer types smaller than int,
 // since these are promoted to int.
 template <typename T>
-struct IntTraits {
+struct IntTraits : IntTraitsBase<T> {
   typedef T UnsignedType;
   static bool IsNegative(T) { return false; }
 };
 
 template <typename T, typename UnsignedT>
-struct SignedIntTraits {
+struct SignedIntTraits : IntTraitsBase<T> {
   typedef UnsignedT UnsignedType;
   static bool IsNegative(T value) { return value < 0; }
 };
@@ -245,17 +260,28 @@ struct IsLongDouble<long double> { enum {VALUE = 1}; };
 
 void ReportUnknownType(char code, const char *type);
 
-extern const uint64_t POWERS_OF_10[];
+extern const uint32_t POWERS_OF_10_32[];
+extern const uint64_t POWERS_OF_10_64[];
 
+#if FMT_GCC_VERSION >= 400 || __has_builtin(__builtin_clzll)
 // Returns the number of decimal digits in n. Leading zeros are not counted
 // except for n == 0 in which case CountDigits returns 1.
 inline unsigned CountDigits(uint64_t n) {
-#if FMT_GCC_VERSION >= 400 || __has_builtin(__builtin_clzll)
   // Based on http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog10
   // and the benchmark https://github.com/localvoid/cxx-benchmark-count-digits.
   uint64_t t = (64 - __builtin_clzll(n | 1)) * 1233 >> 12;
-  return t - (n < POWERS_OF_10[t]) + 1;
+  return t - (n < POWERS_OF_10_64[t]) + 1;
+}
+# if FMT_GCC_VERSION >= 400 || __has_builtin(__builtin_clz)
+// Optional version of CountDigits for better performance on 32-bit platforms.
+inline unsigned CountDigits(uint32_t n) {
+  uint32_t t = (32 - __builtin_clz(n | 1)) * 1233 >> 12;
+  return t - (n < POWERS_OF_10_32[t]) + 1;
+}
+# endif
 #else
+// Slower version of CountDigits used when __builtin_clz is not available.
+inline unsigned CountDigits(uint64_t n) {
   unsigned count = 1;
   for (;;) {
     // Integer division is slow so do it for a group of four digits instead
@@ -268,8 +294,8 @@ inline unsigned CountDigits(uint64_t n) {
     n /= 10000u;
     count += 4;
   }
-#endif
 }
+#endif
 
 extern const char DIGITS[];
 
@@ -838,7 +864,7 @@ template <typename T, typename Spec>
 void BasicWriter<Char>::FormatInt(T value, const Spec &spec) {
   unsigned size = 0;
   char sign = 0;
-  typedef typename internal::IntTraits<T>::UnsignedType UnsignedType;
+  typedef typename internal::IntTraits<T>::MainType UnsignedType;
   UnsignedType abs_value = value;
   if (internal::IntTraits<T>::IsNegative(value)) {
     sign = '-';
@@ -850,7 +876,8 @@ void BasicWriter<Char>::FormatInt(T value, const Spec &spec) {
   }
   switch (spec.type()) {
   case 0: case 'd': {
-    unsigned num_digits = internal::CountDigits(abs_value);
+    typename internal::IntTraits<T>::MainType normalized_value = abs_value;
+    unsigned num_digits = internal::CountDigits(normalized_value);
     CharPtr p =
         PrepareFilledBuffer(size + num_digits, spec, sign) + 1 - num_digits;
     internal::FormatDecimal(GetBase(p), abs_value, num_digits);
@@ -1380,7 +1407,7 @@ class FormatInt {
 // write a terminating null character.
 template <typename T>
 inline void FormatDec(char *&buffer, T value) {
-  typedef typename internal::IntTraits<T>::UnsignedType UnsignedType;
+  typedef typename internal::IntTraits<T>::MainType UnsignedType;
   UnsignedType abs_value = value;
   if (internal::IntTraits<T>::IsNegative(value)) {
     *buffer++ = '-';
