From 785dd995feb46487804ff8ceb67a5f3371ceeb7d Mon Sep 17 00:00:00 2001
From: Davide Bolcioni <dbolcioni@fb.com>
Date: Tue, 20 Nov 2012 19:27:14 -0800
Subject: [PATCH] Fix output of 128 bit integer to string conversion.

Summary:
Added specializations of folly::to<String> for __int128_t
and __uint128_t.

Test Plan: Added tests of the above to the integral to string tests.

Reviewed By: andrei.alexandrescu@fb.com

FB internal diff: D636992
---
 folly/Conv.h            | 84 +++++++++++++++++++++++++++++++++++++++--
 folly/configure.ac      |  3 ++
 folly/test/ConvTest.cpp | 49 ++++++++++++++++++++++++
 3 files changed, 132 insertions(+), 4 deletions(-)

diff --git a/folly/Conv.h b/folly/Conv.h
index de369c0a..1bf2a39f 100644
--- a/folly/Conv.h
+++ b/folly/Conv.h
@@ -37,6 +37,8 @@
 #include <stdexcept>
 #include <typeinfo>
 
+#include <limits.h>
+
 #include "double-conversion.h"   // V8 JavaScript implementation
 
 #define FOLLY_RANGE_CHECK(condition, message)                           \
@@ -122,6 +124,46 @@ typename std::tuple_element<
  * Conversions from integral types to string types.
  ******************************************************************************/
 
+#if FOLLY_HAVE_INT128_T
+namespace detail {
+
+template <typename IntegerType>
+constexpr unsigned int
+digitsEnough() {
+  return ceil((double(sizeof(IntegerType) * CHAR_BIT) * M_LN2) / M_LN10);
+}
+
+inline unsigned int
+unsafeTelescope128(char * buffer, unsigned int room, unsigned __int128 x) {
+  typedef unsigned __int128 Usrc;
+  unsigned int p = room - 1;
+
+  while (x >= (Usrc(1) << 64)) { // Using 128-bit division while needed
+    const auto y = x / 10;
+    const auto digit = x % 10;
+
+    buffer[p--] = '0' + digit;
+    x = y;
+  }
+
+  uint64_t xx = x; // Moving to faster 64-bit division thereafter
+
+  while (xx >= 10) {
+    const auto y = xx / 10ULL;
+    const auto digit = xx % 10ULL;
+
+    buffer[p--] = '0' + digit;
+    xx = y;
+  }
+
+  buffer[p] = '0' + xx;
+
+  return p;
+}
+
+}
+#endif
+
 /**
  * Returns the number of digits in the base 10 representation of an
  * uint64_t. Useful for preallocating buffers and such. It's also used
@@ -229,19 +271,53 @@ toAppend(const fbstring& value, Tgt * result) {
   result->append(value.data(), value.size());
 }
 
+#if FOLLY_HAVE_INT128_T
+/**
+ * Special handling for 128 bit integers.
+ */
+
+template <class Tgt>
+void
+toAppend(__int128 value, Tgt * result) {
+  typedef unsigned __int128 Usrc;
+  char buffer[detail::digitsEnough<unsigned __int128>() + 1];
+  unsigned int p;
+
+  if (value < 0) {
+    p = detail::unsafeTelescope128(buffer, sizeof(buffer), Usrc(-value));
+    buffer[--p] = '-';
+  } else {
+    p = detail::unsafeTelescope128(buffer, sizeof(buffer), value);
+  }
+
+  result->append(buffer + p, buffer + sizeof(buffer));
+}
+
+template <class Tgt>
+void
+toAppend(unsigned __int128 value, Tgt * result) {
+  char buffer[detail::digitsEnough<unsigned __int128>()];
+  unsigned int p;
+
+  p = detail::unsafeTelescope128(buffer, sizeof(buffer), value);
+
+  result->append(buffer + p, buffer + sizeof(buffer));
+}
+
+#endif
+
 /**
  * int32_t and int64_t to string (by appending) go through here. The
  * result is APPENDED to a preexisting string passed as the second
- * parameter. For convenience, the function also returns a reference
- * to *result. This should be efficient with fbstring because fbstring
+ * parameter. This should be efficient with fbstring because fbstring
  * incurs no dynamic allocation below 23 bytes and no number has more
  * than 22 bytes in its textual representation (20 for digits, one for
  * sign, one for the terminating 0).
  */
 template <class Tgt, class Src>
 typename std::enable_if<
-  std::is_integral<Src>::value && std::is_signed<Src>::value
-  && detail::IsSomeString<Tgt>::value && sizeof(Src) >= 4>::type
+  std::is_integral<Src>::value && std::is_signed<Src>::value &&
+  detail::IsSomeString<Tgt>::value && sizeof(Src) >= 4>::type
 toAppend(Src value, Tgt * result) {
   typedef typename std::make_unsigned<Src>::type Usrc;
   char buffer[20];
diff --git a/folly/configure.ac b/folly/configure.ac
index ed487786..6d564f9f 100644
--- a/folly/configure.ac
+++ b/folly/configure.ac
@@ -51,6 +51,9 @@ AC_C_INLINE
 AC_TYPE_SIZE_T
 AC_HEADER_TIME
 AC_C_VOLATILE
+AC_CHECK_TYPE([__int128],
+  [AC_DEFINE([HAVE_INT128_T], [1])],
+  [AC_DEFINE([HAVE_INT128_T], [0])])
 AC_CHECK_TYPES([ptrdiff_t])
 
 # Checks for library functions.
diff --git a/folly/test/ConvTest.cpp b/folly/test/ConvTest.cpp
index 1cde6198..bb31bd53 100644
--- a/folly/test/ConvTest.cpp
+++ b/folly/test/ConvTest.cpp
@@ -97,9 +97,58 @@ void testIntegral2String() {
   testIntegral2String<String, Ints...>();
 }
 
+#if FOLLY_HAVE_INT128_T
+template <class String>
+void test128Bit2String() {
+  typedef unsigned __int128 Uint;
+  typedef __int128 Sint;
+
+  EXPECT_EQ(detail::digitsEnough<unsigned __int128>(), 39);
+
+  Uint value = 123;
+  EXPECT_EQ(to<String>(value), "123");
+  Sint svalue = 123;
+  EXPECT_EQ(to<String>(svalue), "123");
+  svalue = -123;
+  EXPECT_EQ(to<String>(svalue), "-123");
+
+  value = __int128(1) << 64;
+  EXPECT_EQ(to<String>(value), "18446744073709551616");
+
+  svalue =  -(__int128(1) << 64);
+  EXPECT_EQ(to<String>(svalue), "-18446744073709551616");
+
+  value = 0;
+  EXPECT_EQ(to<String>(value), "0");
+
+  svalue = 0;
+  EXPECT_EQ(to<String>(svalue), "0");
+
+  // TODO: the following do not compile to<__int128> ...
+
+#if 0
+  value = numeric_limits<Uint>::min();
+  EXPECT_EQ(to<Uint>(to<String>(value)), value);
+  value = numeric_limits<Uint>::max();
+  EXPECT_EQ(to<Uint>(to<String>(value)), value);
+
+  svalue = numeric_limits<Sint>::min();
+  EXPECT_EQ(to<Sint>(to<String>(svalue)), svalue);
+  value = numeric_limits<Sint>::max();
+  EXPECT_EQ(to<Sint>(to<String>(svalue)), svalue);
+#endif
+}
+
+#endif
+
 TEST(Conv, Integral2String) {
   testIntegral2String<std::string, char, short, int, long>();
   testIntegral2String<fbstring, char, short, int, long>();
+
+#if FOLLY_HAVE_INT128_T
+  test128Bit2String<std::string>();
+  test128Bit2String<fbstring>();
+#endif
 }
 
 template <class String>
-- 
2.34.1