Added missing files

3 files changed, 423 insertions, 113 deletions

diff --git a/include/rapidjson/internal/biginteger.h b/include/rapidjson/internal/biginteger.h
new file mode 100644
index 00000000..a0dbb849
--- /dev/null
+++ b/include/rapidjson/internal/biginteger.h
@@ -0,0 +1,283 @@
+// Copyright (C) 2011 Milo Yip
+//
+// Permission is hereby granted, free of charge, to any person obtaining a copy
+// of this software and associated documentation files (the "Software"), to deal
+// in the Software without restriction, including without limitation the rights
+// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+// copies of the Software, and to permit persons to whom the Software is
+// furnished to do so, subject to the following conditions:
+//
+// The above copyright notice and this permission notice shall be included in
+// all copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+// THE SOFTWARE.
+
+#ifndef RAPIDJSON_BIGINTEGER_H_
+#define RAPIDJSON_BIGINTEGER_H_
+
+#include "../rapidjson.h"
+
+namespace rapidjson {
+namespace internal {
+
+class BigInteger {
+public:
+    typedef uint64_t Type;
+
+    explicit BigInteger(uint64_t u) : count_(1) {
+        digits_[0] = u;
+    }
+
+    BigInteger(const char* decimals, size_t length) : count_(1) {
+        RAPIDJSON_ASSERT(length > 0);
+        digits_[0] = 0;
+        size_t i = 0;
+        const size_t kMaxDigitPerIteration = 19;  // 2^64 = 18446744073709551616 > 10^19
+        while (length >= kMaxDigitPerIteration) {
+            AppendDecimal64(decimals + i, decimals + i + kMaxDigitPerIteration);
+            length -= kMaxDigitPerIteration;
+            i += kMaxDigitPerIteration;
+        }
+
+        if (length > 0)
+            AppendDecimal64(decimals + i, decimals + i + length);
+    }
+
+    BigInteger& operator=(uint64_t u) {
+        digits_[0] = u;            
+        count_ = 1;
+        return *this;
+    }
+
+    BigInteger& operator+=(uint64_t u) {
+        Type backup = digits_[0];
+        digits_[0] += u;
+        for (size_t i = 0; i < count_ - 1; i++) {
+            if (digits_[i] >= backup)
+                return *this; // no carry
+            backup = digits_[i + 1];
+            digits_[i + 1] += 1;
+        }
+
+        // Last carry
+        if (digits_[count_ - 1] < backup)
+            PushBack(1);
+
+        return *this;
+    }
+
+    BigInteger& operator*=(uint64_t u) {
+        if (u == 0) return *this = 0;
+        if (u == 1) return *this;
+        uint64_t k = 0;
+        for (size_t i = 0; i < count_; i++) {
+            uint64_t hi;
+            digits_[i] = MulAdd64(digits_[i], u, k, &hi);
+            k = hi;
+        }
+        
+        if (k > 0)
+            PushBack(k);
+
+        return *this;
+    }
+
+    BigInteger& operator*=(uint32_t u) {
+        if (u == 0) return *this = 0;
+        if (u == 1) return *this;
+        uint32_t k = 0;
+        for (size_t i = 0; i < count_; i++) {
+            const uint64_t c = digits_[i] >> 32;
+            const uint64_t d = digits_[i] & 0xFFFFFFFF;
+            const uint64_t uc = u * c;
+            const uint64_t ud = u * d;
+            const uint64_t p0 = ud + k;
+            const uint64_t p1 = uc + (p0 >> 32);
+            digits_[i] = (p0 & 0xFFFFFFFF) | (p1 << 32);
+            k = p1 >> 32;
+        }
+        
+        if (k > 0)
+            PushBack(k);
+
+        return *this;
+    }
+
+    BigInteger& operator<<=(size_t shift) {
+        if (IsZero()) return *this;
+
+        if (shift >= kTypeBit) {
+            size_t offset = shift / kTypeBit;
+            RAPIDJSON_ASSERT(count_ + offset <= kCapacity);
+            for (size_t i = count_; i > 0; i--)
+                digits_[i - 1 + offset] = digits_[i - 1];
+            for (size_t i = 0; i < offset; i++)
+                digits_[i] = 0;
+            count_ += offset;
+            shift -= offset * kTypeBit;
+        }
+
+        if (shift > 0) {
+            // Inter-digit shifts
+            Type carry = 0;
+            for (size_t i = 0; i < count_; i++) {
+                Type newCarry = digits_[i] >> (kTypeBit - shift);
+                digits_[i] = (digits_[i] << shift) | carry;
+                carry = newCarry;
+            }
+
+            // Last carry
+            if (carry)
+                PushBack(carry);
+        }
+
+        return *this;
+    }
+
+    bool operator==(const BigInteger& rhs) const {
+        return count_ == rhs.count_ && memcmp(digits_, rhs.digits_, count_ * sizeof(Type)) == 0;
+    }
+
+    BigInteger& MultiplyPow5(unsigned exp) {
+        static const uint32_t kPow5[12] = {
+            5,
+            5 * 5,
+            5 * 5 * 5,
+            5 * 5 * 5 * 5,
+            5 * 5 * 5 * 5 * 5,
+            5 * 5 * 5 * 5 * 5 * 5,
+            5 * 5 * 5 * 5 * 5 * 5 * 5,
+            5 * 5 * 5 * 5 * 5 * 5 * 5 * 5,
+            5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5,
+            5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5,
+            5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5,
+            5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5
+        };
+        if (exp == 0) return *this;
+        unsigned e = exp;
+        for (; e >= 27; e -= 27) *this *= RAPIDJSON_UINT64_C2(0X6765C793, 0XFA10079D); // 5^27
+        for (; e >= 13; e -= 13) *this *= 1220703125u; // 5^13
+        if (e > 0)               *this *= kPow5[e - 1];
+        return *this;
+    }
+
+    // Compute absolute difference of this and rhs.
+    // Return false if this < rhs
+    bool Difference(const BigInteger& rhs, BigInteger* out) const {
+        int cmp = Compare(rhs);
+        if (cmp == 0) {
+            *out = BigInteger(0);
+            return false;
+        }
+        const BigInteger *a, *b;  // Makes a > b
+        bool ret;
+        if (cmp < 0) { a = &rhs; b = this; ret = true; }
+        else         { a = this; b = &rhs; ret = false; }
+
+        Type borrow = 0;
+        for (size_t i = 0; i < a->count_; i++) {
+            Type d = a->digits_[i] - borrow;
+            if (i < b->count_)
+                d -= b->digits_[i];
+            borrow = (d > a->digits_[i]) ? 1 : 0;
+            out->digits_[i] = d;
+            if (d != 0)
+                out->count_ = i + 1;
+        }
+
+        return ret;
+    }
+
+    int Compare(const BigInteger& rhs) const {
+        if (count_ != rhs.count_)
+            return count_ < rhs.count_ ? -1 : 1;
+
+        for (size_t i = count_; i-- > 0;)
+            if (digits_[i] != rhs.digits_[i])
+                return digits_[i] < rhs.digits_[i] ? -1 : 1;
+
+        return 0;
+    }
+
+    size_t GetCount() const { return count_; }
+    Type GetDigit(size_t index) const { RAPIDJSON_ASSERT(index < count_); return digits_[index]; }
+    bool IsZero() const { return count_ == 1 && digits_[0] == 0; }
+
+private:
+    void AppendDecimal64(const char* begin, const char* end) {
+        uint64_t u = ParseUint64(begin, end);
+        if (IsZero())
+            *this = u;
+        else {
+            unsigned exp = end - begin;
+            (MultiplyPow5(exp) <<= exp) += u;   // *this = *this * 10^exp + u
+        }
+    }
+
+    void PushBack(Type digit) {
+        RAPIDJSON_ASSERT(count_ < kCapacity);
+        digits_[count_++] = digit;
+    }
+
+    static uint64_t ParseUint64(const char* begin, const char* end) {
+        uint64_t r = 0;
+        for (const char* p = begin; p != end; ++p) {
+            RAPIDJSON_ASSERT(*p >= '0' && *p <= '9');
+            r = r * 10 + (*p - '0');
+        }
+        return r;
+    }
+
+    // Assume a * b + k < 2^128
+    static uint64_t MulAdd64(uint64_t a, uint64_t b, uint64_t k, uint64_t* outHigh) {
+#if defined(_MSC_VER) && defined(_M_AMD64)
+        uint64_t low = _umul128(a, b, outHigh) + k;
+        if (low < k)
+            (*outHigh)++;
+        return low;
+#elif (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 6)) && defined(__x86_64__)
+        unsigned __int128 p = static_cast<unsigned __int128>(a) * static_cast<unsigned __int128>(b);
+        p += k;
+        *outHigh = p >> 64;
+        return static_cast<uint64_t>(p);
+#else
+        const uint64_t a0 = a & 0xFFFFFFFF, a1 = a >> 32, b0 = b & 0xFFFFFFFF, b1 = b >> 32;
+        uint64_t x0 = a0 * b0, x1 = a0 * b1, x2 = a1 * b0, x3 = a1 * b1;
+        x1 += (x0 >> 32); // can't give carry
+        x1 += x2;
+        if (x1 < x2)
+            x3 += (static_cast<uint64_t>(1) << 32);
+        uint64_t lo = (x1 << 32) + (x0 & 0xFFFFFFFF);
+        uint64_t hi = x3 + (x1 >> 32);
+
+        lo += k;
+        if (lo < k)
+            hi++;
+        *outHigh = hi;
+        return lo;
+#endif
+    }
+
+    static Type FullAdd(Type a, Type b, bool inCarry, bool* outCarry) {
+        Type c = a + b + (inCarry ? 1 : 0);
+        *outCarry = c < a;
+        return c;
+    }
+
+    static const size_t kBitCount = 3328;  // 64bit * 54 > 10^1000
+    static const size_t kCapacity = kBitCount / sizeof(Type);
+    static const size_t kTypeBit = sizeof(Type) * 8;
+
+    Type digits_[kCapacity];
+    size_t count_;
+};
+} // namespace internal
+} // namespace rapidjson
+
+#endif // RAPIDJSON_BIGINTEGER_H_
diff --git a/test/unittest/bigintegertest.cpp b/test/unittest/bigintegertest.cpp
new file mode 100644
index 00000000..e7b3b8f9
--- /dev/null
+++ b/test/unittest/bigintegertest.cpp
@@ -0,0 +1,139 @@
+// Copyright (C) 2011 Milo Yip
+//
+// Permission is hereby granted, free of charge, to any person obtaining a copy
+// of this software and associated documentation files (the "Software"), to deal
+// in the Software without restriction, including without limitation the rights
+// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+// copies of the Software, and to permit persons to whom the Software is
+// furnished to do so, subject to the following conditions:
+//
+// The above copyright notice and this permission notice shall be included in
+// all copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+// THE SOFTWARE.
+
+#include "unittest.h"
+
+#include "rapidjson/internal/biginteger.h"
+
+using namespace rapidjson::internal;
+
+#define BIGINTEGER_LITERAL(s) BigInteger(s, sizeof(s) - 1)
+
+static const BigInteger kZero(0);
+static const BigInteger kOne(1);
+static const BigInteger kUint64Max = BIGINTEGER_LITERAL("18446744073709551615");
+static const BigInteger kTwo64 = BIGINTEGER_LITERAL("18446744073709551616");
+
+TEST(BigInteger, Constructor) {
+    EXPECT_TRUE(kZero.IsZero());
+    EXPECT_TRUE(kZero == kZero);
+    EXPECT_TRUE(kZero == BIGINTEGER_LITERAL("0"));
+    EXPECT_TRUE(kZero == BIGINTEGER_LITERAL("00"));
+
+    const BigInteger a(123);
+    EXPECT_TRUE(a == a);
+    EXPECT_TRUE(a == BIGINTEGER_LITERAL("123"));
+    EXPECT_TRUE(a == BIGINTEGER_LITERAL("0123"));
+
+    EXPECT_EQ(2u, kTwo64.GetCount());
+    EXPECT_EQ(0u, kTwo64.GetDigit(0));
+    EXPECT_EQ(1u, kTwo64.GetDigit(1));
+}
+
+TEST(BigInteger, AddUint64) {
+    BigInteger a = kZero;
+    a += 0u;
+    EXPECT_TRUE(kZero == a);
+
+    a += 1u;
+    EXPECT_TRUE(kOne == a);
+
+    a += 1u;
+    EXPECT_TRUE(BigInteger(2) == a);
+
+    EXPECT_TRUE(BigInteger(RAPIDJSON_UINT64_C2(0xFFFFFFFF, 0xFFFFFFFF)) == kUint64Max);
+    BigInteger b = kUint64Max;
+    b += 1u;
+    EXPECT_TRUE(kTwo64 == b);
+    b += RAPIDJSON_UINT64_C2(0xFFFFFFFF, 0xFFFFFFFF);
+    EXPECT_TRUE(BIGINTEGER_LITERAL("36893488147419103231") == b);
+}
+
+TEST(BigInteger, MultiplyUint64) {
+    BigInteger a = kZero;
+    a *= static_cast <uint64_t>(0);
+    EXPECT_TRUE(kZero == a);
+    a *= static_cast <uint64_t>(123);
+    EXPECT_TRUE(kZero == a);
+
+    BigInteger b = kOne;
+    b *= static_cast<uint64_t>(1);
+    EXPECT_TRUE(kOne == b);
+    b *= static_cast<uint64_t>(0);
+    EXPECT_TRUE(kZero == b);
+
+    BigInteger c(123);
+    c *= static_cast<uint64_t>(456u);
+    EXPECT_TRUE(BigInteger(123u * 456u) == c);
+    c *= RAPIDJSON_UINT64_C2(0xFFFFFFFF, 0xFFFFFFFF);
+    EXPECT_TRUE(BIGINTEGER_LITERAL("1034640981606221330982120") == c);
+    c *= RAPIDJSON_UINT64_C2(0xFFFFFFFF, 0xFFFFFFFF);
+    EXPECT_TRUE(BIGINTEGER_LITERAL("19085757395861596536664473018420572782123800") == c);
+}
+
+TEST(BigInteger, MultiplyUint32) {
+    BigInteger a = kZero;
+    a *= static_cast <uint32_t>(0);
+    EXPECT_TRUE(kZero == a);
+    a *= static_cast <uint32_t>(123);
+    EXPECT_TRUE(kZero == a);
+
+    BigInteger b = kOne;
+    b *= static_cast<uint32_t>(1);
+    EXPECT_TRUE(kOne == b);
+    b *= static_cast<uint32_t>(0);
+    EXPECT_TRUE(kZero == b);
+
+    BigInteger c(123);
+    c *= static_cast<uint32_t>(456u);
+    EXPECT_TRUE(BigInteger(123u * 456u) == c);
+    c *= 0xFFFFFFFFu;
+    EXPECT_TRUE(BIGINTEGER_LITERAL("240896125641960") == c);
+    c *= 0xFFFFFFFFu;
+    EXPECT_TRUE(BIGINTEGER_LITERAL("1034640981124429079698200") == c);
+}
+
+TEST(BigInteger, LeftShift) {
+    BigInteger a = kZero;
+    a <<= 1;
+    EXPECT_TRUE(kZero == a);
+    a <<= 64;
+    EXPECT_TRUE(kZero == a);
+
+    a = BigInteger(123);
+    a <<= 0;
+    EXPECT_TRUE(BigInteger(123) == a);
+    a <<= 1;
+    EXPECT_TRUE(BigInteger(246) == a);
+    a <<= 64;
+    EXPECT_TRUE(BIGINTEGER_LITERAL("4537899042132549697536") == a);
+    a <<= 99;
+    EXPECT_TRUE(BIGINTEGER_LITERAL("2876235222267216943024851750785644982682875244576768") == a);
+}
+
+TEST(BigInteger, Compare) {
+    EXPECT_EQ(0, kZero.Compare(kZero));
+    EXPECT_EQ(1, kOne.Compare(kZero));
+    EXPECT_EQ(-1, kZero.Compare(kOne));
+    EXPECT_EQ(0, kUint64Max.Compare(kUint64Max));
+    EXPECT_EQ(0, kTwo64.Compare(kTwo64));
+    EXPECT_EQ(-1, kUint64Max.Compare(kTwo64));
+    EXPECT_EQ(1, kTwo64.Compare(kUint64Max));
+}
diff --git a/test/unittest/strtodtest.cpp b/test/unittest/strtodtest.cpp
index ae564128..d8849be6 100644
--- a/test/unittest/strtodtest.cpp
+++ b/test/unittest/strtodtest.cpp
@@ -22,121 +22,9 @@
 
 #include "rapidjson/internal/strtod.h"
 
-using namespace rapidjson::internal;
-
 #define BIGINTEGER_LITERAL(s) BigInteger(s, sizeof(s) - 1)
 
-static const BigInteger kZero(0);
-static const BigInteger kOne(1);
-static const BigInteger kUint64Max = BIGINTEGER_LITERAL("18446744073709551615");
-static const BigInteger kTwo64 = BIGINTEGER_LITERAL("18446744073709551616");
-
-TEST(Strtod, BigInteger_Constructor) {
-    EXPECT_TRUE(kZero.IsZero());
-    EXPECT_TRUE(kZero == kZero);
-    EXPECT_TRUE(kZero == BIGINTEGER_LITERAL("0"));
-    EXPECT_TRUE(kZero == BIGINTEGER_LITERAL("00"));
-
-    const BigInteger a(123);
-    EXPECT_TRUE(a == a);
-    EXPECT_TRUE(a == BIGINTEGER_LITERAL("123"));
-    EXPECT_TRUE(a == BIGINTEGER_LITERAL("0123"));
-
-    EXPECT_EQ(2u, kTwo64.GetCount());
-    EXPECT_EQ(0u, kTwo64.GetDigit(0));
-    EXPECT_EQ(1u, kTwo64.GetDigit(1));
-}
-
-TEST(Strtod, BigInteger_AddUint64) {
-    BigInteger a = kZero;
-    a += 0u;
-    EXPECT_TRUE(kZero == a);
-
-    a += 1u;
-    EXPECT_TRUE(kOne == a);
-
-    a += 1u;
-    EXPECT_TRUE(BigInteger(2) == a);
-
-    EXPECT_TRUE(BigInteger(RAPIDJSON_UINT64_C2(0xFFFFFFFF, 0xFFFFFFFF)) == kUint64Max);
-    BigInteger b = kUint64Max;
-    b += 1u;
-    EXPECT_TRUE(kTwo64 == b);
-    b += RAPIDJSON_UINT64_C2(0xFFFFFFFF, 0xFFFFFFFF);
-    EXPECT_TRUE(BIGINTEGER_LITERAL("36893488147419103231") == b);
-}
-
-TEST(Strtod, BigInteger_MultiplyUint64) {
-    BigInteger a = kZero;
-    a *= static_cast <uint64_t>(0);
-    EXPECT_TRUE(kZero == a);
-    a *= static_cast <uint64_t>(123);
-    EXPECT_TRUE(kZero == a);
-
-    BigInteger b = kOne;
-    b *= static_cast<uint64_t>(1);
-    EXPECT_TRUE(kOne == b);
-    b *= static_cast<uint64_t>(0);
-    EXPECT_TRUE(kZero == b);
-
-    BigInteger c(123);
-    c *= static_cast<uint64_t>(456u);
-    EXPECT_TRUE(BigInteger(123u * 456u) == c);
-    c *= RAPIDJSON_UINT64_C2(0xFFFFFFFF, 0xFFFFFFFF);
-    EXPECT_TRUE(BIGINTEGER_LITERAL("1034640981606221330982120") == c);
-    c *= RAPIDJSON_UINT64_C2(0xFFFFFFFF, 0xFFFFFFFF);
-    EXPECT_TRUE(BIGINTEGER_LITERAL("19085757395861596536664473018420572782123800") == c);
-}
-
-TEST(Strtod, BigInteger_MultiplyUint32) {
-    BigInteger a = kZero;
-    a *= static_cast <uint32_t>(0);
-    EXPECT_TRUE(kZero == a);
-    a *= static_cast <uint32_t>(123);
-    EXPECT_TRUE(kZero == a);
-
-    BigInteger b = kOne;
-    b *= static_cast<uint32_t>(1);
-    EXPECT_TRUE(kOne == b);
-    b *= static_cast<uint32_t>(0);
-    EXPECT_TRUE(kZero == b);
-
-    BigInteger c(123);
-    c *= static_cast<uint32_t>(456u);
-    EXPECT_TRUE(BigInteger(123u * 456u) == c);
-    c *= 0xFFFFFFFFu;
-    EXPECT_TRUE(BIGINTEGER_LITERAL("240896125641960") == c);
-    c *= 0xFFFFFFFFu;
-    EXPECT_TRUE(BIGINTEGER_LITERAL("1034640981124429079698200") == c);
-}
-
-TEST(Strtod, BigInteger_LeftShift) {
-    BigInteger a = kZero;
-    a <<= 1;
-    EXPECT_TRUE(kZero == a);
-    a <<= 64;
-    EXPECT_TRUE(kZero == a);
-
-    a = BigInteger(123);
-    a <<= 0;
-    EXPECT_TRUE(BigInteger(123) == a);
-    a <<= 1;
-    EXPECT_TRUE(BigInteger(246) == a);
-    a <<= 64;
-    EXPECT_TRUE(BIGINTEGER_LITERAL("4537899042132549697536") == a);
-    a <<= 99;
-    EXPECT_TRUE(BIGINTEGER_LITERAL("2876235222267216943024851750785644982682875244576768") == a);
-}
-
-TEST(Strtod, BigInteger_Compare) {
-    EXPECT_EQ(0, kZero.Compare(kZero));
-    EXPECT_EQ(1, kOne.Compare(kZero));
-    EXPECT_EQ(-1, kZero.Compare(kOne));
-    EXPECT_EQ(0, kUint64Max.Compare(kUint64Max));
-    EXPECT_EQ(0, kTwo64.Compare(kTwo64));
-    EXPECT_EQ(-1, kUint64Max.Compare(kTwo64));
-    EXPECT_EQ(1, kTwo64.Compare(kUint64Max));
-}
+using namespace rapidjson::internal;
 
 TEST(Strtod, CheckApproximationCase) {
     static const int kSignificandSize = 52;