re-write int128 long division to avoid license impact from stackoverflow references (#4633)

* rewrite int128 long divison to avoid stackoverflow hit

Protobuf was showing Stackoverflow hits in the code base, primarily code written to calculate long division. This code was copied from a stackoverflow post, which means it would be licensed under CC BY-SA 3.0. Due to this license, IBM Legal did not want to include this OSS in our products and advised us to re-write this particular piece of code to avoid the license restriction. We have re-written the code for our own distribution, and are willing to merge it into the main code base for others who want to avoid the stackoverflow license issues to benefit as well.

1 files changed, 18 insertions, 34 deletions

diff --git a/src/google/protobuf/stubs/int128.cc b/src/google/protobuf/stubs/int128.cc
index a5090801..7b993e8f 100644
--- a/src/google/protobuf/stubs/int128.cc
+++ b/src/google/protobuf/stubs/int128.cc
@@ -76,52 +76,36 @@ static inline int Fls128(uint128 n) {
   return Fls64(Uint128Low64(n));
 }
 
-// Long division/modulo for uint128 implemented using the shift-subtract
-// division algorithm adapted from:
-// http://stackoverflow.com/questions/5386377/division-without-using
 void uint128::DivModImpl(uint128 dividend, uint128 divisor,
                          uint128* quotient_ret, uint128* remainder_ret) {
   if (divisor == 0) {
     GOOGLE_LOG(FATAL) << "Division or mod by zero: dividend.hi=" << dividend.hi_
                       << ", lo=" << dividend.lo_;
-  }
-
-  if (divisor > dividend) {
+  } else if (dividend < divisor) {
     *quotient_ret = 0;
     *remainder_ret = dividend;
     return;
-  }
-
-  if (divisor == dividend) {
-    *quotient_ret = 1;
-    *remainder_ret = 0;
-    return;
-  }
-
-  uint128 denominator = divisor;
-  uint128 position = 1;
-  uint128 quotient = 0;
-
-  // Left aligns the MSB of the denominator and the dividend.
-  int shift = Fls128(dividend) - Fls128(denominator);
-  denominator <<= shift;
-  position <<= shift;
-
-  // Uses shift-subtract algorithm to divide dividend by denominator. The
-  // remainder will be left in dividend.
-  while (position > 0) {
-    if (dividend >= denominator) {
-      dividend -= denominator;
-      quotient |= position;
+  } else {
+    int dividend_bit_length = Fls128(dividend);
+    int divisor_bit_length = Fls128(divisor);
+    int difference = dividend_bit_length - divisor_bit_length;
+    uint128 quotient = 0;
+    while (difference >= 0) {
+      quotient <<= 1;
+      uint128 shifted_divisor = divisor << difference;
+      if (shifted_divisor <= dividend) {
+        dividend -= shifted_divisor;
+        quotient += 1;
+      }
+      difference -= 1;
     }
-    position >>= 1;
-    denominator >>= 1;
+    //record the final quotient and remainder
+    *quotient_ret = quotient;
+    *remainder_ret = dividend;
   }
-
-  *quotient_ret = quotient;
-  *remainder_ret = dividend;
 }
 
+
 uint128& uint128::operator/=(const uint128& divisor) {
   uint128 quotient = 0;
   uint128 remainder = 0;