(Wangle) Possibly undefined behavior in collect

[folly.git] / folly / Conv.h

diff --git a/folly/Conv.h b/folly/Conv.h
index 31902c73d8008ed4dced18c224aee4c2e45f7e20..ccb394b9bcb9114c8a66ee78dcba31e0fa533beb 100644 (file)
--- a/folly/Conv.h
+++ b/folly/Conv.h
@@ -1,5 +1,5 @@
 /*
- * Copyright 2014 Facebook, Inc.
+ * Copyright 2015 Facebook, Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -46,6 +46,13 @@
 #define FOLLY_RANGE_CHECK_STRINGIZE(x) #x
 #define FOLLY_RANGE_CHECK_STRINGIZE2(x) FOLLY_RANGE_CHECK_STRINGIZE(x)
 
+// Android doesn't support std::to_string so just use a placeholder there.
+#ifdef __ANDROID__
+#define FOLLY_RANGE_CHECK_TO_STRING(x) std::string("N/A")
+#else
+#define FOLLY_RANGE_CHECK_TO_STRING(x) std::to_string(x)
+#endif
+
 #define FOLLY_RANGE_CHECK(condition, message, src)                          \
   ((condition) ? (void)0 : throw std::range_error(                          \
     (std::string(__FILE__ "(" FOLLY_RANGE_CHECK_STRINGIZE2(__LINE__) "): ") \
@@ -95,15 +102,15 @@ to(const Src & value) {
                    < std::numeric_limits<Src>::max()) {
     FOLLY_RANGE_CHECK(
       (!greater_than<Tgt, std::numeric_limits<Tgt>::max()>(value)),
-      "Overflow", std::to_string(value)
-    );
+      "Overflow",
+      FOLLY_RANGE_CHECK_TO_STRING(value));
   }
   /* static */ if (std::is_signed<Src>::value &&
                    (!std::is_signed<Tgt>::value || sizeof(Src) > sizeof(Tgt))) {
     FOLLY_RANGE_CHECK(
       (!less_than<Tgt, std::numeric_limits<Tgt>::min()>(value)),
-      "Negative overflow", std::to_string(value)
-    );
+      "Negative overflow",
+      FOLLY_RANGE_CHECK_TO_STRING(value));
   }
   return static_cast<Tgt>(value);
 }
@@ -122,9 +129,11 @@ to(const Src & value) {
   /* static */ if (std::numeric_limits<Tgt>::max() <
                    std::numeric_limits<Src>::max()) {
     FOLLY_RANGE_CHECK(value <= std::numeric_limits<Tgt>::max(),
-                      "Overflow", std::to_string(value));
+                      "Overflow",
+                      FOLLY_RANGE_CHECK_TO_STRING(value));
     FOLLY_RANGE_CHECK(value >= -std::numeric_limits<Tgt>::max(),
-                      "Negative overflow", std::to_string(value));
+                      "Negative overflow",
+                      FOLLY_RANGE_CHECK_TO_STRING(value));
   }
   return boost::implicit_cast<Tgt>(value);
 }
@@ -219,6 +228,42 @@ unsafeTelescope128(char * buffer, size_t room, unsigned __int128 x) {
  */
 
 inline uint32_t digits10(uint64_t v) {
+#ifdef __x86_64__
+
+  // For this arch we can get a little help from specialized CPU instructions
+  // which can count leading zeroes; 64 minus that is appx. log (base 2).
+  // Use that to approximate base-10 digits (log_10) and then adjust if needed.
+
+  // 10^i, defined for i 0 through 19.
+  // This is 20 * 8 == 160 bytes, which fits neatly into 5 cache lines
+  // (assuming a cache line size of 64).
+  static const uint64_t powersOf10[20] __attribute__((__aligned__(64))) = {
+    1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000,
+    10000000000, 100000000000, 1000000000000, 10000000000000, 100000000000000,
+    1000000000000000, 10000000000000000, 100000000000000000,
+    1000000000000000000, 10000000000000000000UL
+  };
+
+  // "count leading zeroes" operation not valid; for 0; special case this.
+  if UNLIKELY (! v) {
+    return 1;
+  }
+
+  // bits is in the ballpark of log_2(v).
+  const uint8_t leadingZeroes = __builtin_clzll(v);
+  const auto bits = 63 - leadingZeroes;
+
+  // approximate log_10(v) == log_10(2) * bits.
+  // Integer magic below: 77/256 is appx. 0.3010 (log_10(2)).
+  // The +1 is to make this the ceiling of the log_10 estimate.
+  const uint32_t minLength = 1 + ((bits * 77) >> 8);
+
+  // return that log_10 lower bound, plus adjust if input >= 10^(that bound)
+  // in case there's a small error and we misjudged length.
+  return minLength + (uint32_t) (UNLIKELY (v >= powersOf10[minLength]));
+
+#else
+
   uint32_t result = 1;
   for (;;) {
     if (LIKELY(v < 10)) return result;
@@ -229,6 +274,8 @@ inline uint32_t digits10(uint64_t v) {
     v /= 10000U;
     result += 4;
   }
+
+#endif
 }
 
 /**
@@ -1416,7 +1463,12 @@ to(const Src & value) {
   if (value != witness) {
     throw std::range_error(
       to<std::string>("to<>: loss of precision when converting ", value,
-                      " to type ", typeid(Tgt).name()).c_str());
+#ifdef FOLLY_HAS_RTTI
+                      " to type ", typeid(Tgt).name()
+#else
+                      " to other type"
+#endif
+                      ).c_str());
   }
   return result;
 }