from __future__ import division

import operator
import sys, os
import math
from random import random, randint, sample

try:
    import pytest
except ImportError:
    print 'cwd', os.getcwd()
    print 'sys.path', sys.path
    raise

from rpython.rlib import rbigint as lobj
from rpython.rlib.rarithmetic import r_uint, r_longlong, r_ulonglong, intmask, LONG_BIT
from rpython.rlib.rbigint import (rbigint, SHIFT, MASK, KARATSUBA_CUTOFF,
    _store_digit, _mask_digit, InvalidEndiannessError, InvalidSignednessError,
    gcd_lehmer, lehmer_xgcd, gcd_binary, divmod_big, ONERBIGINT, MaxIntError,
    _str_to_int_big_w5pow, _str_to_int_big_base10, _str_to_int_big_inner10,
    _format_lowest_level_divmod_int_results, _format_int10_18digits)
from rpython.rlib.rbigint import HOLDER
from rpython.rlib.rfloat import NAN
from rpython.rtyper.test.test_llinterp import interpret
from rpython.translator.c.test.test_standalone import StandaloneTests
from rpython.rtyper.tool.rfficache import platform
from rpython.rlib.rstring import StringBuilder

from hypothesis import given, strategies, example, settings, assume

longs = strategies.builds(
    long, strategies.integers())
ints = strategies.integers(-sys.maxint-1, sys.maxint)

def makelong(data):
    numbits = data.draw(strategies.integers(1, 2000))
    r = data.draw(strategies.integers(0, 1 << numbits))
    if data.draw(strategies.booleans()):
        return -r
    return r

def makelong_long_sequences(data, ndigits):
    """ From CPython:
    Get quasi-random long consisting of ndigits digits (in base BASE).
    quasi == the most-significant digit will not be 0, and the number
    is constructed to contain long strings of 0 and 1 bits.  These are
    more likely than random bits to provoke digit-boundary errors.
    The sign of the number is also random.
    """
    nbits_hi = ndigits * SHIFT
    nbits_lo = nbits_hi - SHIFT + 1
    answer = 0L
    nbits = 0
    r = data.draw(strategies.integers(0, SHIFT * 2 - 1)) | 1  # force 1 bits to start
    while nbits < nbits_lo:
        bits = (r >> 1) + 1
        bits = min(bits, nbits_hi - nbits)
        assert 1 <= bits <= SHIFT
        nbits = nbits + bits
        answer = answer << bits
        if r & 1:
            answer = answer | ((1 << bits) - 1)
        r = data.draw(strategies.integers(0, SHIFT * 2 - 1))
    assert nbits_lo <= nbits <= nbits_hi
    if data.draw(strategies.booleans()):
        answer = -answer
    return answer


MAXDIGITS = 15
digitsizes = strategies.sampled_from(
    range(1, MAXDIGITS+1) +
    range(KARATSUBA_CUTOFF, KARATSUBA_CUTOFF + 14) +
    [KARATSUBA_CUTOFF * 3, KARATSUBA_CUTOFF * 1000]
)

def make_biglongs_for_division(data):
    size1 = data.draw(digitsizes)
    val1 = makelong_long_sequences(data, size1)
    size2 = data.draw(digitsizes)
    val2 = makelong_long_sequences(data, size2)
    return val1, val2

tuples_biglongs_for_division = strategies.builds(
        make_biglongs_for_division,
        strategies.data())

biglongs = strategies.builds(makelong, strategies.data())


def makerarithint(data):
    classlist = platform.numbertype_to_rclass.values()
    cls = data.draw(strategies.sampled_from(classlist))
    if cls is int:
        minimum = -sys.maxint-1
        maximum = sys.maxint
    else:
        BITS = cls.BITS
        if cls.SIGNED:
            minimum = -2 ** (BITS - 1)
            maximum = 2 ** (BITS - 1) - 1
        else:
            minimum = 0
            maximum = 2 ** BITS - 1
    value = data.draw(strategies.integers(minimum, maximum))
    return cls(value)
rarith_ints = strategies.builds(makerarithint, strategies.data())


def gen_signs(l):
    for s in l:
        if s == 0:
            yield s
        else:
            yield s
            yield -s

long_vals_not_too_big = range(17) + [
        37, 39, 50,
        127, 128, 129, 511, 512, 513, sys.maxint, sys.maxint + 1,
        12345678901234567890L,
        123456789123456789000000L,
]

long_vals = long_vals_not_too_big + [
        1 << 100, 3 ** 10000]

int_vals = range(33) + [
        1000,
        0x11111111, 0x11111112, 8888,
        9999, sys.maxint, 2 ** 19, 2 ** 18 - 1
]
signed_int_vals = list(gen_signs(int_vals)) + [-sys.maxint-1]

class TestRLong(object):
    def test_simple(self):
        for op1 in [-2, -1, 0, 1, 2, 10, 50]:
            for op2 in [-2, -1, 0, 1, 2, 10, 50]:
                rl_op1 = rbigint.fromint(op1)
                rl_op2 = rbigint.fromint(op2)
                for op in "add sub mul".split():
                    r1 = getattr(rl_op1, op)(rl_op2)
                    r2 = getattr(operator, op)(op1, op2)
                    assert r1.tolong() == r2

    def test_frombool(self):
        assert rbigint.frombool(False).tolong() == 0
        assert rbigint.frombool(True).tolong() == 1

    def test_str(self):
        n = 1
        r1 = rbigint.fromint(1)
        three = rbigint.fromint(3)
        for i in range(300):
            n *= 3
            r1 = r1.mul(three)
            assert r1.str() == str(n)
            r2 = r1.neg()
            assert r2.str() == str(-n)

    def test_floordiv(self):
        for op1 in gen_signs(long_vals):
            rl_op1 = rbigint.fromlong(op1)
            for op2 in gen_signs(long_vals):
                if not op2:
                    continue
                rl_op2 = rbigint.fromlong(op2)
                r1 = rl_op1.floordiv(rl_op2)
                r2 = op1 // op2
                assert r1.tolong() == r2

    def test_int_floordiv(self):
        x = 1000L
        r = rbigint.fromlong(x)
        r2 = r.int_floordiv(10)
        assert r2.tolong() == 100L

        for op1 in gen_signs(long_vals):
            for op2 in signed_int_vals:
                if not op2:
                    continue
                rl_op1 = rbigint.fromlong(op1)
                r1 = rl_op1.int_floordiv(op2)
                r2 = op1 // op2
                assert r1.tolong() == r2

        with pytest.raises(ZeroDivisionError):
            r.int_floordiv(0)

        # Error pointed out by Armin Rigo
        n = sys.maxint+1
        r = rbigint.fromlong(n)
        assert r.int_floordiv(int(-n)).tolong() == -1L

        for x in int_vals:
            if not x:
                continue
            r = rbigint.fromlong(x)
            rn = rbigint.fromlong(-x)
            res = r.int_floordiv(x)
            res2 = r.int_floordiv(-x)
            res3 = rn.int_floordiv(x)
            assert res.tolong() == 1L
            assert res2.tolong() == -1L
            assert res3.tolong() == -1L

    def test_floordiv2(self):
        n1 = rbigint.fromlong(sys.maxint + 1)
        n2 = rbigint.fromlong(-(sys.maxint + 1))
        assert n1.floordiv(n2).tolong() == -1L
        assert n2.floordiv(n1).tolong() == -1L

    def test_truediv(self):
        for op1 in gen_signs(long_vals_not_too_big):
            rl_op1 = rbigint.fromlong(op1)
            for op2 in gen_signs(long_vals):
                rl_op2 = rbigint.fromlong(op2)
                if not op2:
                    with pytest.raises(ZeroDivisionError):
                        rl_op1.truediv(rl_op2)
                    continue
                r1 = rl_op1.truediv(rl_op2)
                r2 = op1 / op2
                assert r1 == r2

    def test_truediv_precision(self):
        op1 = rbigint.fromlong(12345*2**30)
        op2 = rbigint.fromlong(98765*7**81)
        f = op1.truediv(op2)
        assert f == 4.7298422347492634e-61      # exactly

    def test_truediv_overflow(self):
        overflowing = 2**1024 - 2**(1024-53-1)
        op1 = rbigint.fromlong(overflowing-1)
        op2 = rbigint.fromlong(1)
        f = op1.truediv(op2)
        assert f == 1.7976931348623157e+308     # exactly

        op1 = rbigint.fromlong(overflowing-1)
        op2 = rbigint.fromlong(-1)
        f = op1.truediv(op2)
        assert f == -1.7976931348623157e+308    # exactly

        op1 = rbigint.fromlong(-overflowing+1)
        op2 = rbigint.fromlong(-1)
        f = op1.truediv(op2)
        assert f == +1.7976931348623157e+308    # exactly

        op1 = rbigint.fromlong(overflowing)
        op2 = rbigint.fromlong(1)
        with pytest.raises(OverflowError):
            op1.truediv(op2)

    def test_truediv_overflow2(self):
        overflowing = 2**1024 - 2**(1024-53-1)
        op1 = rbigint.fromlong(2*overflowing - 10)
        op2 = rbigint.fromlong(2)
        f = op1.truediv(op2)
        assert f == 1.7976931348623157e+308    # exactly
        op2 = rbigint.fromlong(-2)
        f = op1.truediv(op2)
        assert f == -1.7976931348623157e+308   # exactly

    def test_mod(self):
        for op1 in gen_signs(long_vals):
            rl_op1 = rbigint.fromlong(op1)
            for op2 in gen_signs(long_vals):
                rl_op2 = rbigint.fromlong(op2)
                if not op2:
                    with pytest.raises(ZeroDivisionError):
                        rl_op1.mod(rl_op2)
                    continue
                r1 = rl_op1.mod(rl_op2)
                r2 = op1 % op2

                assert r1.tolong() == r2

    def test_int_mod(self):
        for x in gen_signs(long_vals):
            op1 = rbigint.fromlong(x)
            for y in signed_int_vals:
                if not y:
                    with pytest.raises(ZeroDivisionError):
                        op1.int_mod(0)
                    continue
                r1 = op1.int_mod(y)
                r2 = x % y
                assert r1.tolong() == r2

    def test_int_mod_int_result(self):
        for x in gen_signs(long_vals):
            op1 = rbigint.fromlong(x)
            for y in signed_int_vals:
                if not y:
                    with pytest.raises(ZeroDivisionError):
                        op1.int_mod_int_result(0)
                    continue
                r1 = op1.int_mod_int_result(y)
                r2 = x % y
                assert r1 == r2

    def test_int_divmod_int_result(self):
        for x in gen_signs(long_vals):
            op1 = rbigint.fromlong(x)
            for y in signed_int_vals:
                if not y:
                    continue
                r1 = op1.int_mod_int_result(y)
                r2 = x % y
                assert r1 == r2


    def test_pow(self):
        for op1 in gen_signs(long_vals_not_too_big):
            rl_op1 = rbigint.fromlong(op1)
            for op2 in [0, 1, 2, 8, 9, 10, 11]:
                rl_op2 = rbigint.fromint(op2)
                r1 = rl_op1.pow(rl_op2)
                r2 = op1 ** op2
                assert r1.tolong() == r2

                for op3 in gen_signs([1, 2, 5, 1000, 12312312312312235659969696l]):
                    if not op3:
                        continue
                    r3 = rl_op1.pow(rl_op2, rbigint.fromlong(op3))
                    r4 = pow(op1, op2, op3)
                    assert r3.tolong() == r4

    def test_int_pow(self):
        for op1 in gen_signs(long_vals_not_too_big):
            rl_op1 = rbigint.fromlong(op1)
            for op2 in [0, 1, 2, 8, 9, 10, 11, 127, 128, 129]:
                r1 = rl_op1.int_pow(op2)
                r2 = op1 ** op2
                assert r1.tolong() == r2

                for op3 in gen_signs(long_vals_not_too_big):
                    if not op3:
                        continue
                    r3 = rl_op1.int_pow(op2, rbigint.fromlong(op3))
                    r4 = pow(op1, op2, op3)
                    assert r3.tolong() == r4

    def test_int_pow_big(self):
        if sys.maxint < 2**32:
            pytest.skip("64-bit only")
        for op1 in gen_signs(int_vals):
            rl_op1 = rbigint.fromint(op1)
            for op2 in [2**31, 2**32-1, 2**32]:
                r1 = rl_op1.int_pow(op2, rbigint.fromint(sys.maxint))
                r2 = pow(op1, op2, sys.maxint)
                assert r1.tolong() == r2

    def test_pow_raises(self):
        r1 = rbigint.fromint(2)
        r0 = rbigint.fromint(0)
        with pytest.raises(ValueError):
            r1.int_pow(2, r0)
        with pytest.raises(ValueError):
            r1.pow(r1, r0)

    def test_touint(self):
        result = r_uint(sys.maxint + 42)
        rl = rbigint.fromint(sys.maxint).add(rbigint.fromint(42))
        assert rl.touint() == result

    def test_eq_ne_operators(self):
        a1 = rbigint.fromint(12)
        a2 = rbigint.fromint(12)
        a3 = rbigint.fromint(123)

        assert a1 == a2
        assert a1 != a3
        assert not (a1 != a2)
        assert not (a1 == a3)

    def test_divmod_big2(self):
        def check(a, b):
            fa = rbigint.fromlong(a)
            fb = rbigint.fromlong(b)
            div, mod = divmod_big(fa, fb)
            assert div.mul(fb).add(mod).eq(fa)
        check(2, 3)
        check(3, 2)
        check((2 << 1000) - 1, (2 << (65 * 3 + 2)) - 1)
        check((2 + 5 * 2 ** SHIFT) << (100 * SHIFT), 5 << (100 * SHIFT))

    def test_divmod_big_is_used(self, monkeypatch):
        # make sure that the big divmod path is actually hit
        monkeypatch.setattr(rbigint, "_divmod_small", None)
        fa = rbigint.fromlong(3 ** (SHIFT * HOLDER.DIV_LIMIT * 2))
        fb = rbigint.fromlong(5 ** (SHIFT * HOLDER.DIV_LIMIT))
        div, mod = fa.divmod(fb)
        assert div.mul(fb).add(mod).eq(fa)

    def test_karatsuba_not_used_bug(self):
        a = rbigint.fromlong(2 ** 2000 + 1)
        b = rbigint.fromlong(2 ** 5000 + 7)
        assert a.mul(b).tolong() == a.tolong() * b.tolong()

    def test_lopsided_bug(self):
        la = 0x1b8e499a888235ea66f6497e3640bc118592a4ecb800e53e0121af9b2dede38c9323dc160ad564c10ff34095fcc89ecefde3116e7ad99bd5a5b785d811a1e930ae0b0a919623569c99d6c1e779aa5345609a14fc64a83970991d7df672d3bf2fe800766932291b2593382495d1b2a9de1a212d0e517d35764a8a30d060d4218f034807c59728a009683887c3f239f6b958216fd6e36db778bf350941be6ee987f87ea6460ba77f1db154fff175d20117107b5ebd48305b4190d082433419f3daace778d9ce9975ca33293c8b7ad7dd253321e208c22e1bf3833535dd4c76395117e6f32444254fdb9e77cd0b5f8d98c31dafaab720067ef925
        a = rbigint.fromlong(la)
        lb = 0x30fcf4a0f2ae98bd28d249c3eeabf902b492ec4f8001978aacada9f76e18b0f9e9234e6013427a3ac705c82716b9fde1c35ac9a7f6d8317bd14643473bca821da73012c9ee77b66bbc287529bbd97797c82e5e327a0e9f0110346e27e894e21c471d44493cbadaed7780410a585a118ad91e88fd02a5b4608483e500ac23c9e1ccf1d4ed7e811c8280647f953cd8d3109cad389a77df7f0f8cd01074e0c52d6380e12798f84637513b41c7029891c90c8f1436a5d5ab4ce656c80405b1f53fbda529ba66c49f0a4b059ea4862fb8a5977758ae4875a74e22b05e98a5dd43f41e6361b0407925e34d8b7fa5698d6d815adf712f7e71d2a8d75ee7749e22e558157d73c1ed1089063dd7a29c915990836b5a951aa77917847bd9807d6c89b4262871127d17ca5a84e2b23bc5eb66137cce412dcbd88622b55b05b710258affcc845a8e1b99d33c187a237eacd21e9628063948f711b2e5617b647f3fe7c28bac1989612a66d6be34d59ffee63e15e0cdf10d43c6f6301c47e7c7f3ca71dc4e312873633957a6054f25d4db49dcc401aba272ff7c23e077c143510a040f5eb80fe096384c3a4ab0604d951710956f84cdefb631a2ed806ad8f5fef5ef1223dbea4b8a7b49309e9672e77c763dbb698432c77cfff875ab5c97d24f4441b5a3704deda8835135e3e6314be281a97963b49eccf06571b634efa16605a0ec2eda8148a6537e24da5fb128cfbde3ea6c28d850eac3815dd2a0a72844a14590124a6e9062befbdf7fb14c7783ee5096481a5ef0ef9dabf4bc831213afc469a5256818e1dba97cae6f63d6cf2b9584361f36b1b8fa60286fe6bc010129b7f99ee250907ed0a134900513bd3c38555de3b085e7e86
        b = rbigint.fromlong(lb)
        x = a.mul(b)
        assert x.tolong() == la * lb

    def test_mul_bug(self):
        x = -0x1fffffffffffe00000000000007fffffffffffffffffe0000000000000fffffffffffffc0000000000000003fffffffffff1fffffffffffffffffffff8000000000000000ff80000000000000fffffff000000000000000000000fff800000000000003fffffffffffffffffffffffffffffffe000000000000000000fffffffffffffffffffffffffffffffffffffffffffffc3ffffffffffffff80000000003fffffffffffffe000000000000003fffffffffffffffffffffffffffffffffffffc000000000000000007ffc00000007fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe00000000000000000000000fffffffffe0000000000000000000000000000000007ffffffffff8000000000000000000000000007ffffffffe00000000000001ffffffff00000000007fffffffffc0000000000000000000007fffffffffffffe0000000000ffffffffffffffffffffffffffffff0000000000000000000000000000004000000000000000000007fffffffffffffffc00fffffffff80000001fffffffffffe0000000007ffffffffffffffffc000000000000000000000003f00fffffff000000001fffffffffffffffffffffffffffffffffe000000000000003ffffffffffffffc000000000000000000000000000000000000000000000000fffffffffffff8000001ffffffffffffffffffffffffe00000000000003ffffffffffffffffffffffff00000000fffffffffff000000000L
        y = -0x3fffffffffffc0000000000000000007ffffffffffff800000000000000000001ffffffffffffffc0000000000000000000000ffffffffffffffffffffffffffffc000000000000000000001ffffffffffffffffffffffffffffffffffffffffffffffffffffe00000000000000000000000000007fffffffffff000000000000000000000000fffffffffffffffffffffffffffffffffffffffff0000000003e007fffffffffffffffffff80000000000000000003fffffffffc000000000000007fffc0000000007ffffffffffffff0000000000010000000000000001fffffffffffffffffffffffffffffffffe000000000000fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe0000000000001ffff007fff0000000000000000000000001f000000000001fffffffffffffffffc00000000001fffffffffffffffffffffffffffffffffffffff0000000000000000001ffffffffffff00000000000000000000000000000000000003fffffffff00003fffffffe00000000000000000000ffffffffffffffffffffff800001ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff8000000000000001ffe000001ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff00000000000fffffffffff800000000000000000fffffffffffffffffffe00000000003ffffffffffffffffffffffffffffffffffffffffc000000000000000006000001fffffffe0000000000ffffffffffffffffffffffffff8003fffffffffffffffffffffffffffe0000007fffc0000000000000000000000001ffffffffffffffffffffffffffffffffffff0000000000001fffe00000000000000000000000000000000000000000000000000000003fffffff0000000000007ffffff8000000000000001fffffffffffffffff80001fffffffffffffffffffffffffff800000000000000000001ffffe00000000000000000003fffffffffffffffffffffffff000000000000000fffffffffffffffffffffffffffffc0000000000000003fffffe0000000000000000000000001ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe0000000003fff00001ffffffffffffffffffff0000000000001fffffffffffffc0000000000007ffffffffffffffffffffc000000000007fffffffffffffffffff80000000000003ffffffffffffc0000000000000000000000000000000000000000000000ffffe000000000000000000000000000001ffffffffffffffffffffffffffffffffffffe007ffffffffffff000000000000003fffffffffffffffffff800000000000000ff0000000000000000000000000000001ffffffffffffe00000000000007ffffffffffffff8000000000000001ffffffffffffc0000000000007ff000003fffffffffffffffffffffffffffffffffffffe00000007ffffffffffffffffffffe00000007ffffff0000000000000000ffffc00000000000000000ffffffffff8000000000000000fffffe0000000000000000000007fffffffffc000000fe0000000000000000000001ffffff800000000000000001ffffffffff00000000000000000000000000000000000000000000000ffffffffffffffffff000000000000000000000007fffffffffffffc0000fffffffffffffffffffffffffe000003ffffffffffff800000000000001fffffffffffffc000000000000000000000000001fff8000000000000000000000000000fffffffffffffffffffffffff0000000000000000003fe00000003fffffffffffffffff00000000000000ffffffffffe07fffffffffffffffc000000000000000000000003fffffff800000000000000000000003fffffffffffc0000000000000000000000003fffffffffffffffffc0000000000ffffffffffffffffffffffffffffffffffffffffffffffffffe000ffffffffffffffffc000000000000000000000000000000000000000000ffffffffffffffff8000000000000000000000000000000000000000000000000000000000fffffffffffffffc00000000000000003fffffffffffffffffffffffffffffffffffffe00003fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe0000000000003fffffff00000000007ffffffffffc0007ffffffffe00000ffffc000700000000000000fffffffffff80000000000000000000000L
        xl = rbigint.fromlong(x)
        yl = rbigint.fromlong(y)
        assert xl.mul(yl).tolong() == x * y
        assert yl.mul(xl).tolong() == x * y


def bigint(lst, sign):
    for digit in lst:
        assert digit & MASK == digit    # wrongly written test!
    return rbigint(map(_store_digit, map(_mask_digit, lst)), sign)


class Test_rbigint(object):

    def test_args_from_long(self):
        BASE = 1 << SHIFT
        assert rbigint.fromlong(0).eq(bigint([0], 0))
        assert rbigint.fromlong(17).eq(bigint([17], 1))
        assert rbigint.fromlong(BASE-1).eq(bigint([intmask(BASE-1)], 1))
        assert rbigint.fromlong(BASE).eq(bigint([0, 1], 1))
        assert rbigint.fromlong(BASE**2).eq(bigint([0, 0, 1], 1))
        assert rbigint.fromlong(-17).eq(bigint([17], -1))
        assert rbigint.fromlong(-(BASE-1)).eq(bigint([intmask(BASE-1)], -1))
        assert rbigint.fromlong(-BASE).eq(bigint([0, 1], -1))
        assert rbigint.fromlong(-(BASE**2)).eq(bigint([0, 0, 1], -1))
#        assert rbigint.fromlong(-sys.maxint-1).eq(
#            rbigint.digits_for_most_neg_long(-sys.maxint-1), -1)

    def test_args_from_int(self):
        BASE = 1 << 31 # Can't can't shift here. Shift might be from longlonglong
        MAX = int(BASE-1)
        assert rbigint.fromrarith_int(0).eq(bigint([0], 0))
        assert rbigint.fromrarith_int(17).eq(bigint([17], 1))
        assert rbigint.fromrarith_int(MAX).eq(bigint([MAX], 1))
        # No longer true.
        """assert rbigint.fromrarith_int(r_longlong(BASE)).eq(bigint([0, 1], 1))
        assert rbigint.fromrarith_int(r_longlong(BASE**2)).eq(
            bigint([0, 0, 1], 1))"""
        assert rbigint.fromrarith_int(-17).eq(bigint([17], -1))
        assert rbigint.fromrarith_int(-MAX).eq(bigint([MAX], -1))
        """assert rbigint.fromrarith_int(-MAX-1).eq(bigint([0, 1], -1))
        assert rbigint.fromrarith_int(r_longlong(-(BASE**2))).eq(
            bigint([0, 0, 1], -1))"""
#        assert rbigint.fromrarith_int(-sys.maxint-1).eq((
#            rbigint.digits_for_most_neg_long(-sys.maxint-1), -1)

    def test_args_from_uint(self):
        BASE = 1 << SHIFT
        assert rbigint.fromrarith_int(r_uint(0)).eq(bigint([0], 0))
        assert rbigint.fromrarith_int(r_uint(17)).eq(bigint([17], 1))
        assert rbigint.fromrarith_int(r_uint(BASE-1)).eq(bigint([intmask(BASE-1)], 1))
        assert rbigint.fromrarith_int(r_uint(BASE)).eq(bigint([0, 1], 1))
        #assert rbigint.fromrarith_int(r_uint(BASE**2)).eq(bigint([0], 0))
        assert rbigint.fromrarith_int(r_uint(sys.maxint)).eq(
            rbigint.fromint(sys.maxint))
        assert rbigint.fromrarith_int(r_uint(sys.maxint+1)).eq(
            rbigint.fromlong(sys.maxint+1))
        assert rbigint.fromrarith_int(r_uint(2*sys.maxint+1)).eq(
            rbigint.fromlong(2*sys.maxint+1))

    def test_fromdecimalstr(self):
        x = rbigint.fromdecimalstr("12345678901234567890523897987")
        assert x.tolong() == 12345678901234567890523897987L
        assert x.tobool() is True
        x = rbigint.fromdecimalstr("+12345678901234567890523897987")
        assert x.tolong() == 12345678901234567890523897987L
        assert x.tobool() is True
        x = rbigint.fromdecimalstr("-12345678901234567890523897987")
        assert x.tolong() == -12345678901234567890523897987L
        assert x.tobool() is True
        x = rbigint.fromdecimalstr("+0")
        assert x.tolong() == 0
        assert x.tobool() is False
        x = rbigint.fromdecimalstr("-0")
        assert x.tolong() == 0
        assert x.tobool() is False

    def test_fromstr(self):
        from rpython.rlib.rstring import ParseStringError
        assert rbigint.fromstr('123L').tolong() == 123
        assert rbigint.fromstr('123L  ').tolong() == 123
        with pytest.raises(ParseStringError):
            rbigint.fromstr('L')
        with pytest.raises(ParseStringError):
            rbigint.fromstr('L  ')
        assert rbigint.fromstr('123L', 4).tolong() == 27
        assert rbigint.fromstr('123L', 30).tolong() == 27000 + 1800 + 90 + 21
        assert rbigint.fromstr('123L', 22).tolong() == 10648 + 968 + 66 + 21
        assert rbigint.fromstr('123L', 21).tolong() == 441 + 42 + 3
        assert rbigint.fromstr('1891234174197319').tolong() == 1891234174197319
        assert rbigint.fromstr('1891_234_17_4_19731_9', allow_underscores=True).tolong() == 1891234174197319
        assert rbigint.fromstr('1_1' * 6000, allow_underscores=True).tolong() == int('11' * 6000)

    def test__from_numberstring_parser_rewind_bug(self):
        from rpython.rlib.rstring import NumberStringParser
        s = "-99"
        p = NumberStringParser(s, s, 10, 'int')
        assert p.sign == -1
        res = p.next_digit()
        assert res == 9
        res = p.next_digit()
        assert res == 9
        res = p.next_digit()
        assert res == -1
        p.rewind()
        res = p.next_digit()
        assert res == 9
        res = p.next_digit()
        assert res == 9
        res = p.next_digit()
        assert res == -1

    def test_fromstr_huge(self):
        assert _str_to_int_big_base10("1" * 1000, 0, 1000).tolong() == int("1" * 1000)
        mem = {}

        result = _str_to_int_big_inner10('123952' * 1000, 0, 6000, mem, 20)
        assert len(mem) == 13
        assert result

    def test_from_numberstring_parser(self):
        from rpython.rlib.rstring import NumberStringParser
        parser = NumberStringParser("1231231241", "1231231241", 10, "long")
        assert rbigint._from_numberstring_parser(parser).tolong() == 1231231241

    def test_from_numberstring_parser_no_implicit_octal(self):
        from rpython.rlib.rstring import NumberStringParser, ParseStringError
        s = "077777777777777777777777777777"
        parser = NumberStringParser(s, s, 0, "long",
                                    no_implicit_octal=True)
        with pytest.raises(ParseStringError):
            rbigint._from_numberstring_parser(parser)
        parser = NumberStringParser("000", "000", 0, "long",
                                    no_implicit_octal=True)
        assert rbigint._from_numberstring_parser(parser).tolong() == 0

    def test_limit(self):
        from rpython.rlib.rstring import NumberStringParser, MaxDigitsError
        max_str_digits = 999
        s = '0' * (max_str_digits)
        s0 = '1' + s
        s1 = '1' + s[1:]
        s2 = '  - 1' + s[1:]
        with pytest.raises(MaxDigitsError):
            parser = NumberStringParser(s0, s0, 0, "long",
                                        max_str_digits=max_str_digits)
        # these succeed
        parser = NumberStringParser(s2, s2, 0, "long",
                                    max_str_digits=max_str_digits)
        parser = NumberStringParser(s1, s1, 0, "long",
                                    max_str_digits=max_str_digits)
        x = rbigint._from_numberstring_parser(parser)

        assert s1 == x.str(max_str_digits)
        with pytest.raises(MaxIntError):
            x.str(max_str_digits - 1)

    def test_add(self):
        for x in gen_signs(long_vals):
            f1 = rbigint.fromlong(x)
            for y in gen_signs(long_vals):
                f2 = rbigint.fromlong(y)
                result = f1.add(f2)
                assert result.tolong() == x + y
            
        

    def test_add(self):
        for x in gen_signs(long_vals):
            f1 = rbigint.fromlong(x)
            for y in gen_signs(long_vals):
                f2 = rbigint.fromlong(y)
                result = f1.add(f2)
                assert result.tolong() == x + y

    def test_int_add(self):
        for x in gen_signs(long_vals):
            f1 = rbigint.fromlong(x)
            for y in signed_int_vals:
                result = f1.int_add(y)
                assert result.tolong() == x + y

    def test_sub(self):
        for x in gen_signs(long_vals):
            f1 = rbigint.fromlong(x)
            for y in gen_signs(long_vals):
                f2 = rbigint.fromlong(y)
                result = f1.sub(f2)
                assert result.tolong() == x - y

    def test_int_sub(self):
        for x in gen_signs(long_vals):
            f1 = rbigint.fromlong(x)
            for y in signed_int_vals:
                result = f1.int_sub(y)
                assert result.tolong() == x - y

    def test_subzz(self):
        w_l0 = rbigint.fromint(0)
        assert w_l0.sub(w_l0).tolong() == 0

    def test_mul(self):
        for x in gen_signs(long_vals):
            f1 = rbigint.fromlong(x)
            for y in gen_signs(long_vals_not_too_big):
                f2 = rbigint.fromlong(y)
                result = f1.mul(f2)
                assert result.tolong() == x * y
            # there's a special case for a is b
            result = f1.mul(f1)
            assert result.tolong() == x * x

    def test_int_mul(self):
        for x in gen_signs(long_vals):
            f1 = rbigint.fromlong(x)
            for y in signed_int_vals:
                result = f1.int_mul(y)
                assert result.tolong() == x * y

    def test_mul_int_int_rbigint_result(self):
        for x in signed_int_vals:
            for y in signed_int_vals:
                result = rbigint.mul_int_int_bigint_result(x, y)
                assert result.tolong() == x * y

    def test_tofloat(self):
        x = 12345678901234567890L ** 10
        f1 = rbigint.fromlong(x)
        d = f1.tofloat()
        assert d == float(x)
        x = x ** 100
        f1 = rbigint.fromlong(x)
        with pytest.raises(OverflowError):
            f1.tofloat()
        f2 = rbigint.fromlong(2097152 << SHIFT)
        d = f2.tofloat()
        assert d == float(2097152 << SHIFT)

    def test_tofloat_precision(self):
        assert rbigint.fromlong(0).tofloat() == 0.0
        for sign in [1, -1]:
            for p in xrange(100):
                x = long(2**p * (2**53 + 1) + 1) * sign
                y = long(2**p * (2**53+ 2)) * sign
                rx = rbigint.fromlong(x)
                rxf = rx.tofloat()
                assert rxf == float(y)
                assert rbigint.fromfloat(rxf).tolong() == y
                #
                x = long(2**p * (2**53 + 1)) * sign
                y = long(2**p * 2**53) * sign
                rx = rbigint.fromlong(x)
                rxf = rx.tofloat()
                assert rxf == float(y)
                assert rbigint.fromfloat(rxf).tolong() == y

    def test_fromfloat(self):
        x = 1234567890.1234567890
        f1 = rbigint.fromfloat(x)
        y = f1.tofloat()
        assert f1.tolong() == long(x)
        # check overflow
        #x = 12345.6789e10000000000000000000000000000
        # XXX don't use such consts. marshal doesn't handle them right.
        x = 12345.6789e200
        x *= x
        with pytest.raises(OverflowError):
            rbigint.fromfloat(x)
        with pytest.raises(ValueError):
            rbigint.fromfloat(NAN)
        #
        f1 = rbigint.fromfloat(9007199254740991.0)
        assert f1.tolong() == 9007199254740991

        null = rbigint.fromfloat(-0.0)
        assert null.int_eq(0)

    def test_eq_ne(self):
        x = 5858393919192332223L
        y = 585839391919233111223311112332L
        f1 = rbigint.fromlong(x)
        f2 = rbigint.fromlong(-x)
        f3 = rbigint.fromlong(y)
        assert f1.eq(f1)
        assert f2.eq(f2)
        assert f3.eq(f3)
        assert not f1.eq(f2)
        assert not f1.eq(f3)

        assert not f1.ne(f1)
        assert not f2.ne(f2)
        assert not f3.ne(f3)
        assert f1.ne(f2)
        assert f1.ne(f3)

    def test_eq_fastpath(self):
        x = 1234
        y = 1234
        f1 = rbigint.fromint(x)
        f2 = rbigint.fromint(y)
        assert f1.eq(f2)

    def test_lt(self):
        val = [0, 0x111111111111, 0x111111111112, 0x111111111112FFFF]
        for x in gen_signs(val):
            for y in gen_signs(val):
                f1 = rbigint.fromlong(x)
                f2 = rbigint.fromlong(y)
                assert (x < y) ==  f1.lt(f2)

    def test_int_comparison(self):
        for x in gen_signs(long_vals):
            for y in signed_int_vals:
                f1 = rbigint.fromlong(x)
                assert (x < y) == f1.int_lt(y)
                assert (x <= y) == f1.int_le(y)
                assert (x > y) == f1.int_gt(y)
                assert (x >= y) == f1.int_ge(y)
                assert (x == y) == f1.int_eq(y)
                assert (x != y) == f1.int_ne(y)

    def test_order(self):
        f6 = rbigint.fromint(6)
        f7 = rbigint.fromint(7)
        assert (f6.lt(f6), f6.lt(f7), f7.lt(f6)) == (0,1,0)
        assert (f6.le(f6), f6.le(f7), f7.le(f6)) == (1,1,0)
        assert (f6.gt(f6), f6.gt(f7), f7.gt(f6)) == (0,0,1)
        assert (f6.ge(f6), f6.ge(f7), f7.ge(f6)) == (1,0,1)

    def test_int_order(self):
        f6 = rbigint.fromint(6)
        f7 = rbigint.fromint(7)
        assert (f6.int_lt(6), f6.int_lt(7), f7.int_lt(6)) == (0,1,0)
        assert (f6.int_le(6), f6.int_le(7), f7.int_le(6)) == (1,1,0)
        assert (f6.int_gt(6), f6.int_gt(7), f7.int_gt(6)) == (0,0,1)
        assert (f6.int_ge(6), f6.int_ge(7), f7.int_ge(6)) == (1,0,1)

    def test_int_conversion(self):
        f1 = rbigint.fromlong(12332)
        f2 = rbigint.fromint(12332)
        assert f2.tolong() == f1.tolong()
        assert f2.toint()
        assert rbigint.fromlong(42).tolong() == 42
        assert rbigint.fromlong(-42).tolong() == -42

        u = f2.touint()
        assert u == 12332
        assert type(u) is r_uint

    def test_conversions(self):
        for v in (0, 1, -1, sys.maxint, -sys.maxint-1):
            assert rbigint.fromlong(long(v)).tolong() == long(v)
            l = rbigint.fromint(v)
            assert l.toint() == v
            if v >= 0:
                u = l.touint()
                assert u == v
                assert type(u) is r_uint
            else:
                with pytest.raises(ValueError):
                    l.touint()

        toobig_lv1 = rbigint.fromlong(sys.maxint+1)
        assert toobig_lv1.tolong() == sys.maxint+1
        toobig_lv2 = rbigint.fromlong(sys.maxint+2)
        assert toobig_lv2.tolong() == sys.maxint+2
        toobig_lv3 = rbigint.fromlong(-sys.maxint-2)
        assert toobig_lv3.tolong() == -sys.maxint-2

        for lv in (toobig_lv1, toobig_lv2, toobig_lv3):
            with pytest.raises(OverflowError):
                lv.toint()

        lmaxuint = rbigint.fromlong(2*sys.maxint+1)
        toobig_lv4 = rbigint.fromlong(2*sys.maxint+2)

        u = lmaxuint.touint()
        assert u == 2*sys.maxint+1

        with pytest.raises(ValueError):
            toobig_lv3.touint()
        with pytest.raises(OverflowError):
            toobig_lv4.touint()


    def test_pow_lll(self):
        x = 10L
        y = 2L
        z = 13L
        f1 = rbigint.fromlong(x)
        f2 = rbigint.fromlong(y)
        f3 = rbigint.fromlong(z)
        v = f1.pow(f2, f3)
        assert v.tolong() == pow(x, y, z)
        f3n = f3.neg()
        v = f1.pow(f2, f3n)
        assert v.tolong() == pow(x, y, -z)
        #
        f1, f2, f3 = [rbigint.fromlong(i)
                      for i in (10L, -1L, 42L)]
        with pytest.raises(TypeError):
            f1.pow(f2, f3)
        f1, f2, f3 = [rbigint.fromlong(i)
                      for i in (10L, 5L, 0L)]
        with pytest.raises(ValueError):
            f1.pow(f2, f3)

    def test_pow_lll_bug(self):
        two = rbigint.fromint(2)
        t = rbigint.fromlong(2655689964083835493447941032762343136647965588635159615997220691002017799304)
        for n, expected in [(37, 9), (1291, 931), (67889, 39464)]:
            v = two.pow(t, rbigint.fromint(n))
            assert v.toint() == expected
        #
        # more tests, comparing against CPython's answer
        enabled = sample(range(5*32), 10)
        for i in range(5*32):
            t = t.mul(two)      # add one random bit
            if random() >= 0.5:
                t = t.add(rbigint.fromint(1))
            if i not in enabled:
                continue    # don't take forever
            n = randint(1, sys.maxint)
            v = two.pow(t, rbigint.fromint(n))
            assert v.toint() == pow(2, t.tolong(), n)

    def test_pow_lll_bug2(self):
        x = rbigint.fromlong(2)
        y = rbigint.fromlong(5100894665148900058249470019412564146962964987365857466751243988156579407594163282788332839328303748028644825680244165072186950517295679131100799612871613064597)
        z = rbigint.fromlong(538564)
        expected = rbigint.fromlong(163464)
        got = x.pow(y, z)
        assert got.eq(expected)

    def test_pow_lln(self):
        x = 10L
        y = 2L
        f1 = rbigint.fromlong(x)
        f2 = rbigint.fromlong(y)
        v = f1.pow(f2)
        assert v.tolong() == x ** y

    def test_normalize(self):
        f1 = bigint([1, 0], 1)
        f1._normalize()
        assert f1.numdigits() == 1
        f0 = bigint([0], 0)
        f0._normalize()
        assert f0.numdigits() == 1
        assert f0._size == 0
        assert f1.sub(f1).eq(f0)

    def test_invert(self):
        x = 3 ** 40
        f1 = rbigint.fromlong(x)
        f2 = rbigint.fromlong(-x)
        r1 = f1.invert()
        r2 = f2.invert()
        assert r1.tolong() == -(x + 1)
        assert r2.tolong() == -(-x + 1)

    def test_shift(self):
        negative = -23
        masks_list = [int((1 << i) - 1) for i in range(1, r_uint.BITS-1)]
        for x in gen_signs([3L ** 30L, 5L ** 20L, 7 ** 300, 0L, 1L]):
            f1 = rbigint.fromlong(x)
            with pytest.raises(ValueError):
                f1.lshift(negative)
            with pytest.raises(ValueError):
                f1.rshift(negative)
            for y in [0L, 1L, 32L, 2304L, 11233L, 3 ** 9]:
                res1 = f1.lshift(int(y)).tolong()
                res2 = f1.rshift(int(y)).tolong()
                assert res1 == x << y
                assert res2 == x >> y
                for mask in masks_list:
                    res3 = f1.abs_rshift_and_mask(r_ulonglong(y), mask)
                    assert res3 == (abs(x) >> y) & mask

        # test special optimization case in rshift:
        assert rbigint.fromlong(-(1 << 100)).rshift(5).tolong() == -(1 << 100) >> 5

        # Chek value accuracy.
        assert rbigint.fromlong(18446744073709551615L).rshift(1).tolong() == 18446744073709551615L >> 1

    def test_shift_optimization(self):
        # does not crash with memory error
        assert rbigint.fromint(0).lshift(sys.maxint).tolong() == 0

    def test_qshift(self):
        for x in range(10):
            for y in range(1, 161, 16):
                num = (x << y) + x
                f1 = rbigint.fromlong(num)
                nf1 = rbigint.fromlong(-num)

                for z in range(1, 31):
                    res1 = f1.lqshift(z).tolong()
                    res2 = f1.rqshift(z).tolong()
                    res3 = nf1.lqshift(z).tolong()

                    assert res1 == num << z
                    assert res2 == num >> z
                    assert res3 == -num << z

        # Large digit
        for x in range((1 << SHIFT) - 10, (1 << SHIFT) + 10):
            f1 = rbigint.fromlong(x)
            assert f1.rqshift(SHIFT).tolong() == x >> SHIFT
            assert f1.rqshift(SHIFT+1).tolong() == x >> (SHIFT+1)

    def test_from_list_n_bits(self):
        for x in ([3L ** 30L, 5L ** 20L, 7 ** 300] +
                  [1L << i for i in range(130)] +
                  [(1L << i) - 1L for i in range(130)]):
            for nbits in range(1, SHIFT+1):
                mask = (1 << nbits) - 1
                lst = []
                got = x
                while got > 0:
                    lst.append(int(got & mask))
                    got >>= nbits
                f1 = rbigint.from_list_n_bits(lst, nbits)
                assert f1.tolong() == x

    def test_bitwise(self):
        for x in gen_signs(long_vals):
            lx = rbigint.fromlong(x)
            for y in gen_signs(long_vals):
                ly = rbigint.fromlong(y)
                for mod in "xor and_ or_".split():
                    res1 = getattr(lx, mod)(ly).tolong()
                    res2 = getattr(operator, mod)(x, y)
                    assert res1 == res2

    def test_int_bitwise(self):
        for x in gen_signs(long_vals):
            lx = rbigint.fromlong(x)
            for y in signed_int_vals:
                for mod in "xor and_ or_".split():
                    res1 = getattr(lx, 'int_' + mod)(y).tolong()
                    res2 = getattr(operator, mod)(x, y)
                    assert res1 == res2

    def test_mul_eq_shift(self):
        p2 = rbigint.fromlong(1).lshift(63)
        f1 = rbigint.fromlong(0).lshift(63)
        f2 = rbigint.fromlong(0).mul(p2)
        assert f1.eq(f2)

    def test_tostring(self):
        z = rbigint.fromlong(0)
        assert z.str() == '0'
        assert z.repr() == '0L'
        assert z.hex() == '0x0L'
        assert z.oct() == '0L'
        x = rbigint.fromlong(-18471379832321)
        assert x.str() == '-18471379832321'
        assert x.repr() == '-18471379832321L'
        assert x.hex() == '-0x10ccb4088e01L'
        assert x.oct() == '-0414626402107001L'
        assert x.format('.!') == (
            '-!....!!..!!..!.!!.!......!...!...!!!........!')
        assert x.format('abcdefghijkl', '<<', '>>') == '-<<cakdkgdijffjf>>'
        x = rbigint.fromlong(-18471379832321000000000000000000000000000000000000000000)
        assert x.str() == '-18471379832321000000000000000000000000000000000000000000'
        assert x.repr() == '-18471379832321000000000000000000000000000000000000000000L'
        assert x.hex() == '-0xc0d9a6f41fbcf1718b618443d45516a051e40000000000L'
        assert x.oct() == '-014033151572037571705614266060420752125055201217100000000000000L'

    def test_format_caching(self):
        big = rbigint.fromlong(2 ** 1000)
        res1 = big.str()
        oldpow = rbigint.__dict__['pow']
        rbigint.pow = None
        # make sure pow is not used the second time
        try:
            res2 = big.str()
            assert res2 == res1
        finally:
            rbigint.pow = oldpow

    def test_overzealous_assertion(self):
        a = rbigint.fromlong(-1<<10000)
        b = rbigint.fromlong(-1<<3000)
        assert a.mul(b).tolong() == (-1<<10000)*(-1<<3000)

    def test_bit_length(self):
        assert rbigint.fromlong(0).bit_length() == 0
        assert rbigint.fromlong(1).bit_length() == 1
        assert rbigint.fromlong(2).bit_length() == 2
        assert rbigint.fromlong(3).bit_length() == 2
        assert rbigint.fromlong(4).bit_length() == 3
        assert rbigint.fromlong(-3).bit_length() == 2
        assert rbigint.fromlong(-4).bit_length() == 3
        assert rbigint.fromlong(1<<40).bit_length() == 41

    def test_hash(self):
        for i in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
                  sys.maxint-3, sys.maxint-2, sys.maxint-1, sys.maxint,
                  ]:
            # hash of machine-sized integers
            assert rbigint.fromint(i).hash() == i
            # hash of negative machine-sized integers
            assert rbigint.fromint(-i-1).hash() == -i-1
        #

    def test_log(self):
        from rpython.rlib.rfloat import ulps_check
        for op in long_vals:
            for base in [0, 2, 4, 8, 16, 10, math.e]:
                if not op:
                    with pytest.raises(ValueError):
                        rbigint.fromlong(op).log(base)
                    continue
                l = rbigint.fromlong(op).log(base)
                if base:
                    assert ulps_check(l, math.log(op, base)) is None
                else:
                    assert ulps_check(l, math.log(op)) is None

    def test_log2(self):
        assert rbigint.fromlong(1).log(2.0) == 0.0
        assert rbigint.fromlong(2).log(2.0) == 1.0
        assert rbigint.fromlong(2**1023).log(2.0) == 1023.0

    def test_frombytes(self):
        bigint = rbigint.frombytes('', byteorder='big', signed=True)
        assert bigint.tolong() == 0
        s = "\xFF\x12\x34\x56"
        bigint = rbigint.frombytes(s, byteorder="big", signed=False)
        assert bigint.tolong() == 0xFF123456
        bigint = rbigint.frombytes(s, byteorder="little", signed=False)
        assert bigint.tolong() == 0x563412FF
        s = "\xFF\x02\x03\x04\x05\x06\x07\x08\x09\x10\x11\x12\x13\x14\x15\xFF"
        bigint = rbigint.frombytes(s, byteorder="big", signed=False)
        assert s == bigint.tobytes(16, byteorder="big", signed=False)
        with pytest.raises(InvalidEndiannessError):
            bigint.frombytes('\xFF', 'foo', signed=True)
        bigint = rbigint.frombytes('\x82', byteorder='big', signed=True)
        assert bigint.tolong() == -126

    def test_tobytes(self):
        assert rbigint.fromint(0).tobytes(1, 'big', signed=True) == '\x00'
        assert rbigint.fromint(1).tobytes(2, 'big', signed=True) == '\x00\x01'
        with pytest.raises(OverflowError):
            rbigint.fromint(255).tobytes(1, 'big', signed=True)
        assert rbigint.fromint(-129).tobytes(2, 'big', signed=True) == '\xff\x7f'
        assert rbigint.fromint(-129).tobytes(2, 'little', signed=True) == '\x7f\xff'
        assert rbigint.fromint(65535).tobytes(3, 'big', signed=True) == '\x00\xff\xff'
        assert rbigint.fromint(-65536).tobytes(3, 'little', signed=True) == '\x00\x00\xff'
        assert rbigint.fromint(65535).tobytes(2, 'big', signed=False) == '\xff\xff'
        assert rbigint.fromint(-8388608).tobytes(3, 'little', signed=True) == '\x00\x00\x80'
        i = rbigint.fromint(-8388608)
        with pytest.raises(InvalidEndiannessError):
            i.tobytes(3, 'foo', signed=True)
        with pytest.raises(InvalidSignednessError):
            i.tobytes(3, 'little', signed=False)
        with pytest.raises(OverflowError):
            i.tobytes(2, 'little', signed=True)

    def test_gcd(self):
        assert gcd_binary(2*3*7**2, 2**2*7) == 2*7
        pytest.raises(ValueError, gcd_binary, 2*3*7**2, -2**2*7)
        assert gcd_binary(1234, 5678) == 2
        assert gcd_binary(13, 13**6) == 13
        assert gcd_binary(12, 0) == 12
        assert gcd_binary(0, 0) == 0
        with pytest.raises(ValueError):
            gcd_binary(-10, 0)
        with pytest.raises(ValueError):
            gcd_binary(10, -10)

        x = rbigint.fromlong(9969216677189303386214405760200)
        y = rbigint.fromlong(16130531424904581415797907386349)
        g = x.gcd(y)
        assert g == rbigint.fromlong(1)

        for x in gen_signs([12843440367927679363613699686751681643652809878241019930204617606850071260822269719878805]):
            x = rbigint.fromlong(x)
            for y in gen_signs([12372280584571061381380725743231391746505148712246738812788540537514927882776203827701778968535]):
                y = rbigint.fromlong(y)
                g = x.gcd(y)
                assert g.tolong() == 18218089570126697993340888567155155527541105


class TestInternalFunctions(object):
    def test__inplace_divrem1(self):
        # signs are not handled in the helpers!
        for x, y in [(1238585838347L, 3), (1234123412311231L, 1231231), (99, 100)]:
            if y > MASK:
                continue
            f1 = rbigint.fromlong(x)
            f2 = y
            remainder = lobj._inplace_divrem1(f1, f1, f2)
            f1._normalize()
            assert (f1.tolong(), remainder) == divmod(x, y)
        out = bigint([99, 99], 1)
        remainder = lobj._inplace_divrem1(out, out, 100)

    def test__divrem1(self):
        # signs are not handled in the helpers!
        x = 1238585838347L
        y = 3
        f1 = rbigint.fromlong(x)
        f2 = y
        div, rem = lobj._divrem1(f1, f2)
        assert (div.tolong(), rem) == divmod(x, y)

    def test__muladd1(self):
        x = 1238585838347L
        y = 3
        z = 42
        f1 = rbigint.fromlong(x)
        f2 = y
        f3 = z
        prod = lobj._muladd1(f1, f2, f3)
        assert prod.tolong() == x * y + z

    def test__x_divrem(self):
        x = 12345678901234567890L
        for i in range(100):
            y = long(randint(1, 1 << 60))
            y <<= 60
            y += randint(1, 1 << 60)
            if y > x:
                x <<= 100

            f1 = rbigint.fromlong(x)
            f2 = rbigint.fromlong(y)
            div, rem = lobj._x_divrem(f1, f2)
            _div, _rem = divmod(x, y)
            assert div.tolong() == _div
            assert rem.tolong() == _rem

    def test__x_divrem2(self):
        Rx = 1 << 130
        Rx2 = 1 << 150
        Ry = 1 << 127
        Ry2 = 1 << 150
        for i in range(10):
            x = long(randint(Rx, Rx2))
            y = long(randint(Ry, Ry2))
            f1 = rbigint.fromlong(x)
            f2 = rbigint.fromlong(y)
            div, rem = lobj._x_divrem(f1, f2)
            _div, _rem = divmod(x, y)
            assert div.tolong() == _div
            assert rem.tolong() == _rem

    def test_divmod(self):
        x = 12345678901234567890L
        for i in range(100):
            y = long(randint(0, 1 << 60))
            y <<= 60
            y += randint(0, 1 << 60)
            for sx, sy in (1, 1), (1, -1), (-1, -1), (-1, 1):
                sx *= x
                sy *= y
                f1 = rbigint.fromlong(sx)
                f2 = rbigint.fromlong(sy)
                div, rem = f1.divmod(f2)
                _div, _rem = divmod(sx, sy)
                assert div.tolong() == _div
                assert rem.tolong() == _rem
        with pytest.raises(ZeroDivisionError):
            rbigint.fromlong(x).divmod(rbigint.fromlong(0))

        # an explicit example for a very rare case in _x_divrem:
        # "add w back if q was too large (this branch taken rarely)"
        x = 2401064762424988628303678384283622960038813848808995811101817752058392725584695633
        y = 510439143470502793407446782273075179624699774495710665331026
        f1 = rbigint.fromlong(x)
        f2 = rbigint.fromlong(y)
        div, rem = f1.divmod(f2)
        _div, _rem = divmod(x, y)
        assert div.tolong() == _div
        assert rem.tolong() == _rem

    def test_divmod_big_bug(self):
        a = -0x13131313131313131313cfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfd0
        b = -0x131313131313131313d0
        ra = rbigint.fromlong(a)
        rb = rbigint.fromlong(b)
        oldval = HOLDER.DIV_LIMIT
        try:
            HOLDER.DIV_LIMIT = 2 # set limit low to test divmod_big more
            rdiv, rmod = divmod_big(ra, rb)
            div, mod = divmod(a, b)
            assert rdiv.tolong() == div
            assert rmod.tolong() == mod
        finally:
            HOLDER.DIV_LIMIT = oldval

    def test_int_divmod(self):
        for x in long_vals:
            for y in int_vals + [-sys.maxint-1]:
                if not y:
                    continue
                for sx, sy in (1, 1), (1, -1), (-1, -1), (-1, 1):
                    sx *= x
                    sy *= y
                    if sy == sys.maxint + 1:
                        continue
                    f1 = rbigint.fromlong(sx)
                    div, rem = f1.int_divmod(sy)
                    div1, rem1 = f1.divmod(rbigint.fromlong(sy))
                    _div, _rem = divmod(sx, sy)
                    assert div1.tolong() == _div
                    assert rem1.tolong() == _rem
                    assert div.tolong() == _div
                    assert rem.tolong() == _rem
        with pytest.raises(ZeroDivisionError):
            rbigint.fromlong(x).int_divmod(0)

    # testing Karatsuba stuff
    def test__v_iadd(self):
        f1 = bigint([lobj.MASK] * 10, 1)
        f2 = bigint([1], 1)
        carry = lobj._v_iadd(f1, 1, len(f1._digits)-1, f2, 1)
        assert carry == 1
        assert f1.tolong() == lobj.MASK

    def test__v_isub(self):
        f1 = bigint([lobj.MASK] + [0] * 9 + [1], 1)
        f2 = bigint([1], 1)
        borrow = lobj._v_isub(f1, 1, len(f1._digits)-1, f2, 1)
        assert borrow == 0
        assert f1.tolong() == (1 << lobj.SHIFT) ** 10 - 1

    def test__kmul_split(self):
        split = 5
        diglo = [0] * split
        dighi = [lobj.MASK] * split
        f1 = bigint(diglo + dighi, 1)
        hi, lo = lobj._kmul_split(f1, split)
        assert lo._digits == [_store_digit(0)]
        assert hi._digits == map(_store_digit, dighi)

    def test__k_mul(self):
        digs = KARATSUBA_CUTOFF * 5
        f1 = bigint([lobj.MASK] * digs, 1)
        f2 = lobj._x_add(f1, bigint([1], 1))
        ret = lobj._k_mul(f1, f2)
        assert ret.tolong() == f1.tolong() * f2.tolong()

    def test_longlong(self):
        max = 1L << (r_longlong.BITS-1)
        f1 = rbigint.fromlong(max-1)    # fits in r_longlong
        f2 = rbigint.fromlong(-max)     # fits in r_longlong
        f3 = rbigint.fromlong(max)      # overflows
        f4 = rbigint.fromlong(-max-1)   # overflows
        assert f1.tolonglong() == max-1
        assert f2.tolonglong() == -max
        with pytest.raises(OverflowError):
            f3.tolonglong()
        with pytest.raises(OverflowError):
            f4.tolonglong()

    def test_uintmask(self):
        assert rbigint.fromint(-1).uintmask() == r_uint(-1)
        assert rbigint.fromint(0).uintmask() == r_uint(0)
        assert (rbigint.fromint(sys.maxint).uintmask() ==
                r_uint(sys.maxint))
        assert (rbigint.fromlong(sys.maxint+1).uintmask() ==
                r_uint(-sys.maxint-1))

    def test_ulonglongmask(self):
        assert rbigint.fromlong(-1).ulonglongmask() == r_ulonglong(-1)
        assert rbigint.fromlong(0).ulonglongmask() == r_ulonglong(0)
        assert (rbigint.fromlong(sys.maxint).ulonglongmask() ==
                r_ulonglong(sys.maxint))
        assert (rbigint.fromlong(9**50).ulonglongmask() ==
                r_ulonglong(9**50))
        assert (rbigint.fromlong(-9**50).ulonglongmask() ==
                r_ulonglong(-9**50))

    def test_toulonglong(self):
        with pytest.raises(ValueError):
            rbigint.fromlong(-1).toulonglong()

    def test_fits_int(self):
        assert rbigint.fromlong(0).fits_int()
        assert rbigint.fromlong(42).fits_int()
        assert rbigint.fromlong(-42).fits_int()
        assert rbigint.fromlong(sys.maxint).fits_int()
        assert not rbigint.fromlong(sys.maxint + 1).fits_int()
        assert rbigint.fromlong(-sys.maxint - 1).fits_int()
        assert not rbigint.fromlong(-sys.maxint - 2).fits_int()
        assert not rbigint.fromlong(-73786976294838206459).fits_int()
        assert not rbigint.fromlong(1 << 1000).fits_int()

    def test_parse_digit_string(self):
        from rpython.rlib.rbigint import parse_digit_string
        class Parser:
            def __init__(self, base, sign, digits):
                self.base = base
                self.sign = sign
                self.i = 0
                self._digits = digits
                self.start = 0
                self.end = len(digits)
            def next_digit(self):
                i = self.i
                if i == len(self._digits):
                    return -1
                self.i = i + 1
                return self._digits[i]
            def prev_digit(self):
                i = self.i - 1
                assert i >= 0
                self.i = i
                return self._digits[i]
        x = parse_digit_string(Parser(10, 1, [6]))
        assert x.eq(rbigint.fromint(6))
        x = parse_digit_string(Parser(10, 1, [6, 2, 3]))
        assert x.eq(rbigint.fromint(623))
        x = parse_digit_string(Parser(10, -1, [6, 2, 3]))
        assert x.eq(rbigint.fromint(-623))
        x = parse_digit_string(Parser(16, 1, [0xA, 0x4, 0xF]))
        assert x.eq(rbigint.fromint(0xA4F))
        num = 0
        for i in range(36):
            x = parse_digit_string(Parser(36, 1, range(i)))
            assert x.eq(rbigint.fromlong(num))
            num = num * 36 + i
        x = parse_digit_string(Parser(16, -1, range(15,-1,-1)*99))
        assert x.eq(rbigint.fromlong(long('-0x' + 'FEDCBA9876543210'*99, 16)))
        assert x.tobool() is True
        x = parse_digit_string(Parser(7, 1, [0, 0, 0]))
        assert x.tobool() is False
        x = parse_digit_string(Parser(7, -1, [0, 0, 0]))
        assert x.tobool() is False

        for base in [2, 4, 8, 16, 32]:
            for inp in [[0], [1], [1, 0], [0, 1], [1, 0, 1], [1, 0, 0, 1],
                        [1, 0, 0, base-1, 0, 1], [base-1, 1, 0, 0, 0, 1, 0],
                        [base-1]]:
                inp = inp * 97
                x = parse_digit_string(Parser(base, -1, inp))
                num = sum(inp[i] * (base ** (len(inp)-1-i))
                          for i in range(len(inp)))
                assert x.eq(rbigint.fromlong(-num))


BASE = 2 ** SHIFT

class TestTranslatable(object):
    def test_square(self):
        def test():
            xlo = rbigint.fromint(1410065408)
            xhi = rbigint.fromint(4)
            x = xlo.or_(xhi.lshift(31))
            y = x.mul(x)
            return y.str()
        res = interpret(test, [])
        assert "".join(res.chars) == test()

    def test_add(self):
        x = rbigint.fromint(-2147483647)
        y = rbigint.fromint(-1)
        z = rbigint.fromint(-2147483648)
        def test():
            return x.add(y).eq(z)
        assert test()
        res = interpret(test, [])
        assert res

    def test_args_from_rarith_int(self):
        from rpython.rlib.rarithmetic import r_int
        from rpython.rlib.unroll import unrolling_iterable
        from rpython.rtyper.lltypesystem.rffi import r_int_real, r_uint_real
        classlist = platform.numbertype_to_rclass.values()
        cases = [] # tuples of (values, strvalues, typename)
        for r in classlist:
            if r in (r_int, r_int_real, r_uint_real):  # and also r_longlong on 64-bit
                continue
            if r is int:
                mask = sys.maxint*2+1
                signed = True
            else:
                mask = r.MASK
                signed = r.SIGNED
            values = [0, -1, mask>>1, -(mask>>1)-1]
            if not signed:
                values = [x & mask for x in values]
            values = [r(x) for x in values]
            results = [str(long(x)) for x in values]
            cases.append((values, results, str(r)))
        cases = unrolling_iterable(cases)
        def fn():
            for values, results, typname in cases:
                for i in range(len(values)):
                    n = rbigint.fromrarith_int(values[i])
                    n = rbigint.fromrarith_int(values[i])
                    if n.str() != results[i]:
                        return typname + str(i)
            return None
        res = interpret(fn, [])
        assert not res

    def test_truediv_overflow(self):
        overflowing = 2**1024 - 2**(1024-53-1)
        op1 = rbigint.fromlong(overflowing)

        def fn():
            try:
                return op1.truediv(rbigint.fromint(1))
            except OverflowError:
                return -42.0

        res = interpret(fn, [])
        assert res == -42.0

    def test_isqrt(self):
        def fn(x):
            num = rbigint.fromint(3).int_pow(x)
            return num.mul(num).isqrt().eq(num)


        res = interpret(fn, [100])
        assert res == True

    def test_mul_int_int_rbigint_result(self):
        def fn(x, y):
            res = rbigint.mul_int_int_bigint_result(x, y)
            return len(res.str())
        res = interpret(fn, [sys.maxint, sys.maxint])


class TestTranslated(StandaloneTests):

    def test_gcc_4_9(self):
        MIN = -sys.maxint-1

        def entry_point(argv):
            print rbigint.fromint(MIN+1)._digits
            print rbigint.fromint(MIN)._digits
            return 0

        t, cbuilder = self.compile(entry_point)
        data = cbuilder.cmdexec('hi there')
        if SHIFT == LONG_BIT-1:
            assert data == '[%d]\n[0, 1]\n' % sys.maxint
        else:
            # assume 64-bit without native 128-bit type
            assert data == '[%d, %d, 1]\n[0, 0, 2]\n' % (2**31-1, 2**31-1)

class TestHypothesis(object):
    @given(longs, longs, longs)
    def test_pow(self, x, y, z):
        f1 = rbigint.fromlong(x)
        f2 = rbigint.fromlong(y)
        f3 = rbigint.fromlong(z)
        try:
            res = pow(x, y, z)
        except Exception as e:
            with pytest.raises(type(e)):
                f1.pow(f2, f3)
        else:
            v1 = f1.pow(f2, f3)
            try:
                v2 = f1.int_pow(f2.toint(), f3)
            except OverflowError:
                pass
            else:
                assert v2.tolong() == res
            assert v1.tolong() == res

    @given(biglongs, biglongs)
    @example(510439143470502793407446782273075179618477362188870662225920,
             108089693021945158982483698831267549521)
    def test_divmod(self, x, y):
        if x < y:
            x, y = y, x

        f1 = rbigint.fromlong(x)
        f2 = rbigint.fromlong(y)
        try:
            res = divmod(x, y)
        except Exception as e:
            with pytest.raises(type(e)):
                f1.divmod(f2)
        else:
            a, b = f1.divmod(f2)
            assert (a.tolong(), b.tolong()) == res

    @given(biglongs, biglongs)
    @example(510439143470502793407446782273075179618477362188870662225920,
             108089693021945158982483698831267549521)
    def test_divmod_small(self, x, y):
        if x < y:
            x, y = y, x

        f1 = rbigint.fromlong(x)
        f2 = rbigint.fromlong(y)
        try:
            res = divmod(x, y)
        except Exception as e:
            with pytest.raises(type(e)):
                f1._divmod_small(f2)
        else:
            a, b = f1._divmod_small(f2)
            assert (a.tolong(), b.tolong()) == res


    @given(biglongs, biglongs)
    @example(510439143470502793407446782273075179618477362188870662225920,
             108089693021945158982483698831267549521)
    @example(51043991434705027934074467822730751796184773621888706622259209143470502793407446782273075179618477362188870662225920143470502793407446782273075179618477362188870662225920,
             10808)
    @example(17, 257)
    @example(510439143470502793407446782273075179618477362188870662225920L, 108089693021945158982483698831267549521L)
    def test_divmod_big(self, x, y):
        oldval = HOLDER.DIV_LIMIT
        try:
            HOLDER.DIV_LIMIT = 2 # set limit low to test divmod_big more
            if x < y:
                x, y = y, x

            # boost size
            x *= 3 ** (HOLDER.DIV_LIMIT * SHIFT * 5) - 1
            y *= 2 ** (HOLDER.DIV_LIMIT * SHIFT * 5) - 1

            f1 = rbigint.fromlong(x)
            f2 = rbigint.fromlong(y)
            try:
                res = divmod(x, y)
            except Exception as e:
                with pytest.raises(type(e)):
                    divmod_big(f1, f2)
            else:
                a, b = divmod_big(f1, f2)
                assert (a.tolong(), b.tolong()) == res
        finally:
            HOLDER.DIV_LIMIT = oldval

    @given(tuples_biglongs_for_division)
    def test_divmod_consistency(self, tup):
        lx, ly = tup
        ly = ly or 1
        x = rbigint.fromlong(lx)
        y = rbigint.fromlong(ly)
        q, r = x.divmod(y)
        q2, r2 = x.floordiv(y), x.mod(y)
        pab, pba = x.mul(y), y.mul(x)
        assert pab.eq(pba)
        assert q.eq(q2)
        assert r.eq(r2)
        assert x.eq(q.mul(y).add(r))
        if y.int_gt(0):
            assert r.lt(y)
            assert r.int_ge(0)
        else:
            assert y.lt(r)
            assert y.int_le(0)

    @given(biglongs, ints)
    def test_int_divmod(self, x, iy):
        f1 = rbigint.fromlong(x)
        try:
            res = divmod(x, iy)
        except Exception as e:
            with pytest.raises(type(e)):
                f1.int_divmod(iy)
        else:
            a, b = f1.int_divmod(iy)
            assert (a.tolong(), b.tolong()) == res

    @given(longs)
    def test_hash(self, x):
        # hash of large integers: should be equal to the hash of the
        # integer reduced modulo 2**64-1, to make decimal.py happy
        x = abs(x)
        y = x % (2**64-1)
        assert rbigint.fromlong(x).hash() == rbigint.fromlong(y).hash()
        assert rbigint.fromlong(-x).hash() == rbigint.fromlong(-y).hash()

    @given(ints)
    def test_hash_int(self, x):
        # hash of machine-sized integers
        assert rbigint.fromint(x).hash() == x
        # hash of negative machine-sized integers
        assert rbigint.fromint(-x-1).hash() == -x-1

    @given(longs)
    def test_abs(self, x):
        assert rbigint.fromlong(x).abs().tolong() == abs(x)

    @given(longs, longs)
    def test_truediv(self, a, b):
        ra = rbigint.fromlong(a)
        rb = rbigint.fromlong(b)
        if not b:
            with pytest.raises(ZeroDivisionError):
                ra.truediv(rb)
        else:
            assert repr(ra.truediv(rb)) == repr(a / b)

    @given(longs, longs)
    def test_bitwise_and_mul(self, x, y):
        lx = rbigint.fromlong(x)
        ly = rbigint.fromlong(y)
        for mod in "xor and_ or_ mul".split():
            res1a = getattr(lx, mod)(ly).tolong()
            res1b = getattr(ly, mod)(lx).tolong()
            res2 = getattr(operator, mod)(x, y)
            assert res1a == res2

    @given(longs, ints)
    def test_int_bitwise_and_mul(self, x, y):
        lx = rbigint.fromlong(x)
        for mod in "xor and_ or_ mul".split():
            res1 = getattr(lx, 'int_' + mod)(y).tolong()
            res2 = getattr(operator, mod)(x, y)
            assert res1 == res2

    @given(longs, ints)
    def test_int_comparison(self, x, y):
        lx = rbigint.fromlong(x)
        assert lx.int_lt(y) == (x < y)
        assert lx.int_eq(y) == (x == y)
        assert lx.int_le(y) == (x <= y)

    @given(longs, longs)
    def test_int_comparison2(self, x, y):
        lx = rbigint.fromlong(x)
        ly = rbigint.fromlong(y)
        assert lx.lt(ly) == (x < y)
        assert lx.eq(ly) == (x == y)
        assert lx.le(ly) == (x <= y)

    @given(ints, ints, ints)
    def test_gcd_binary(self, x, y, z):
        x, y, z = abs(x), abs(y), abs(z)

        def test(a, b, res):
            g = gcd_binary(a, b)

            assert g == res

        a, b = x, y
        while b:
            a, b = b, a % b

        gcd_x_y = a

        test(x, y, gcd_x_y)
        test(x, 0, x)
        test(0, x, x)
        test(x * z, y * z, gcd_x_y * z)
        test(x * z, z, z)
        test(z, y * z, z)

    @given(biglongs, biglongs, biglongs)
    @example(112233445566778899112233445566778899112233445566778899,
             13579246801357924680135792468013579246801,
             99887766554433221113)
    @settings(max_examples=10)
    def test_gcd(self, x, y, z):
        x, y, z = abs(x), abs(y), abs(z)

        def test(a, b, res):
            g = rbigint.fromlong(a).gcd(rbigint.fromlong(b)).tolong()

            assert g == res

        a, b = x, y
        while b:
            a, b = b, a % b

        gcd_x_y = a

        test(x, y, gcd_x_y)
        test(x * z, y * z, gcd_x_y * z)
        test(x * z, z, z)
        test(z, y * z, z)
        test(x, 0, x)
        test(0, x, x)

    @given(ints)
    def test_longlong_roundtrip(self, x):
        try:
            rx = r_longlong(x)
        except OverflowError:
            pass
        else:
            assert rbigint.fromrarith_int(rx).tolonglong() == rx

    @given(longs)
    def test_unsigned_roundtrip(self, x):
        x = abs(x)
        rx = r_uint(x) # will wrap on overflow
        assert rbigint.fromrarith_int(rx).touint() == rx
        rx = r_ulonglong(x) # will wrap on overflow
        assert rbigint.fromrarith_int(rx).toulonglong() == rx

    @given(biglongs, biglongs)
    def test_mod(self, x, y):
        rx = rbigint.fromlong(x)
        ry = rbigint.fromlong(y)
        if not y:
            with pytest.raises(ZeroDivisionError):
                rx.mod(ry)
            return
        r1 = rx.mod(ry)
        r2 = x % y

        assert r1.tolong() == r2

    @given(biglongs, ints)
    def test_int_mod(self, x, y):
        rx = rbigint.fromlong(x)
        if not y:
            with pytest.raises(ZeroDivisionError):
                rx.int_mod(0)
            return
        r1 = rx.int_mod(y)
        r2 = x % y
        assert r1.tolong() == r2

    @given(biglongs, ints)
    def test_int_mod_int_result(self, x, y):
        rx = rbigint.fromlong(x)
        if not y:
            with pytest.raises(ZeroDivisionError):
                rx.int_mod_int_result(0)
            return
        r1 = rx.int_mod_int_result(y)
        r2 = x % y
        assert r1 == r2

    @given(longs, strategies.integers(0, 2000))
    def test_shift(self, x, shift):
        rx = rbigint.fromlong(x)
        r1 = rx.lshift(shift)
        assert r1.tolong() == x << shift

        r1 = rx.rshift(shift)
        assert r1.tolong() == x >> shift

    @given(longs, strategies.integers(0, 2000), strategies.data())
    def test_abs_rshift_and_mask(self, x, shift, data):
        mask = data.draw(
            strategies.sampled_from(
                [int((1 << i) - 1) for i in range(1, min(SHIFT, r_uint.BITS - 1))]))
        rx = rbigint.fromlong(x)
        r1 = rx.abs_rshift_and_mask(r_ulonglong(shift), mask)
        assert r1 == (abs(x) >> shift) & mask

    @given(biglongs, strategies.integers(min_value=1, max_value=10000))
    def test_str_to_int_big_base10(self, l, limit):
        l = abs(l)
        s = str(l)
        assert _str_to_int_big_base10(str(l), 0, len(s), limit).tolong() == l

    @given(biglongs)
    def test_fromstr(self, l):
        assert rbigint.fromstr(str(l)).tolong() == l

    @given(biglongs)
    def test_fromstr_str_consistency(self, l):
        assert rbigint.fromstr(rbigint.fromlong(l).str()).tolong() == l

    @given(biglongs)
    def test_fromstr_small_limit(self, l):
        # set limits to 2 to stress the recursive algorithm some more
        oldval = HOLDER.STR2INT_LIMIT
        oldval2 = HOLDER.MINSIZE_STR2INT
        try:
            HOLDER.STR2INT_LIMIT = 2
            HOLDER.MINSIZE_STR2INT = 1
            assert rbigint.fromstr(str(l)).tolong() == l
            assert rbigint.fromstr(str(l) + "_1", allow_underscores=True).tolong() == int(str(l) + '1')
        finally:
            HOLDER.STR2INT_LIMIT = oldval
            HOLDER.MINSIZE_STR2INT = 1

    @given(strategies.integers(min_value=1, max_value=10000), strategies.integers(min_value=1, max_value=10000))
    @settings(max_examples=10)
    def test_str_to_int_big_w5pow(self, exp, limit):
        mem = {}
        assert (_str_to_int_big_w5pow(exp, mem, limit).tolong() == 5 ** exp ==
                rbigint.fromint(5).int_pow(exp).tolong())

    @given(biglongs)
    def test_bit_count(self, val):
        assert rbigint.fromlong(val).bit_count() == bin(abs(val)).count("1")

    @given(strategies.binary(), strategies.booleans(), strategies.booleans())
    def test_frombytes_tobytes_hypothesis(self, s, big, signed):
        # check the roundtrip from binary strings to bigints and back
        byteorder = 'big' if big else 'little'
        bigint = rbigint.frombytes(s, byteorder=byteorder, signed=signed)
        t = bigint.tobytes(len(s), byteorder=byteorder, signed=signed)
        assert s == t

    @given(biglongs, biglongs, biglongs)
    def test_distributive(self, a, b, c):
        la = rbigint.fromlong(a)
        lb = rbigint.fromlong(b)
        lc = rbigint.fromlong(c)
        # a * (b + c) == a * b + a * c
        assert la.mul(lb.add(lc)).eq(la.mul(lb).add(la.mul(lc)))

    @given(biglongs, biglongs, biglongs)
    def test_associative(self, a, b, c):
        la = rbigint.fromlong(a)
        lb = rbigint.fromlong(b)
        lc = rbigint.fromlong(c)
        # a * (b * c) == (a * b) * c
        assert la.mul(lb.mul(lc)).eq(la.mul(lb).mul(lc))
        # a + (b + c) == (a + b) + c
        assert la.add(lb.add(lc)).eq(la.add(lb).add(lc))

    @given(biglongs, biglongs)
    def test_commutative(self, a, b):
        la = rbigint.fromlong(a)
        lb = rbigint.fromlong(b)
        # a * b == b * a
        assert la.mul(lb).eq(lb.mul(la))
        # a + b == b + a
        assert la.add(lb).eq(lb.add(la))

    @given(longs, strategies.integers(0, 100), strategies.integers(0, 100))
    @settings(max_examples=10)
    def test_pow_mul(self, a, b, c):
        la = rbigint.fromlong(a)
        lb = rbigint.fromlong(b)
        lc = rbigint.fromlong(c)
        # a ** (b + c) == a ** b * a ** c
        assert la.pow(lb.add(lc)).eq(la.pow(lb).mul(la.pow(lc)))

    @given(rarith_ints)
    def test_args_from_rarith_int(self, i):
        li = rbigint.fromrarith_int(i)
        assert li.tolong() == int(i)

    @given(biglongs)
    @example(3**100)
    def test_isqrt(self, a):
        a = abs(a)
        la = rbigint.fromlong(a)
        lsq = la.isqrt()
        sq = lsq.tolong()
        assert sq * sq <= a
        assert (sq + 1) ** 2 > a

        x = a * a
        lx = rbigint.fromlong(x)
        assert lx.isqrt().tolong() == a

    @given(ints, ints)
    def test_mul_int_int_rbigint_result(self, a, b):
        res = rbigint.mul_int_int_bigint_result(a, b)
        assert res.tolong() == a * b

    @given(strategies.data())
    def test_format_lowest_level_divmod_int_results(self, data):
        b = data.draw(strategies.integers(1, MASK))
        a = data.draw(strategies.integers(0, b-1))
        c = data.draw(strategies.integers(0, b-1))
        assume(bool(b))
        atimesbplusb = rbigint.mul_int_int_bigint_result(a, b).int_add(c)
        div, mod = _format_lowest_level_divmod_int_results(atimesbplusb, b)
        print a, b, c, atimesbplusb, div, mod
        assert (div, mod) == divmod(atimesbplusb.tolong(), b)

    @given(strategies.integers(0, 10**18-1))
    def test_format_int10_18digits(self, val):
        builder = StringBuilder()
        _format_int10_18digits(val, builder)
        s = builder.build()
        assert len(s) == 18
        assert s.lstrip('0') == str(val).lstrip('0')


@pytest.mark.parametrize(['methname'], [(methodname, ) for methodname in dir(TestHypothesis) if methodname.startswith("test_")])
def test_hypothesis_small_shift(methname):
    # run the TestHypothesis in a subprocess with a smaller SHIFT value
    # the idea is that this finds hopefully finds edge cases more easily
    import subprocess, os
    # The cwd on the buildbot is actually in rpython
    # Add the pypy basedir so we get the local pytest
    env = os.environ.copy()
    parent = os.path.dirname
    env['PYTHONPATH'] = parent(parent(parent(parent(__file__))))
    p = subprocess.Popen(" ".join([sys.executable, os.path.abspath(__file__), methname]),
                         stdout=subprocess.PIPE, stderr=subprocess.PIPE,
                         shell=True, env=env)
    stdout, stderr = p.communicate()
    if p.returncode:
        print stdout
        print stderr
    assert not p.returncode

def _get_hacked_rbigint(shift):
    testpath = os.path.dirname(os.path.abspath(__file__))
    with open(os.path.join(os.path.dirname(testpath), "rbigint.py")) as f:
        s = f.read()
    s = s.replace("SHIFT = 63", "SHIFT = %s" % (shift, ))
    s = s.replace("SHIFT = 31", "SHIFT = %s" % (shift, ))
    with open(os.path.join(testpath, "_hacked_rbigint.py"), "w") as f:
        f.write(s)

    from rpython.rlib.test import _hacked_rbigint
    assert _hacked_rbigint.SHIFT == shift
    return _hacked_rbigint

def run():
    shift = 9
    print "USING SHIFT", shift, sys.argv[1]
    _hacked_rbigint = _get_hacked_rbigint(shift)
    globals().update(_hacked_rbigint.__dict__) # emulate import *
    assert SHIFT == shift
    t = TestHypothesis()
    try:
        getattr(t, sys.argv[1])()
    except:
        if "--pdb" in sys.argv:
            import traceback, pdb
            info = sys.exc_info()
            print(traceback.format_exc())
            pdb.post_mortem(info[2], pdb.Pdb)
        raise


if __name__ == '__main__':
    run()