from rpython.rlib.rarithmetic import LONG_BIT, intmask, longlongmask, r_uint, r_ulonglong

from rpython.rlib.rarithmetic import ovfcheck, r_longlong, widen

from rpython.rlib.rarithmetic import most_neg_value_of_same_type

from rpython.rlib.rarithmetic import check_support_int128

from rpython.rlib.rstring import StringBuilder

from rpython.rlib.debug import make_sure_not_resized, check_regular_int

from rpython.rlib.objectmodel import we_are_translated, specialize, not_rpython

from rpython.rlib import jit

from rpython.rtyper.lltypesystem import lltype, rffi

from rpython.rtyper import extregistry

import math, sys

SUPPORT_INT128 = check_support_int128()

BYTEORDER = sys.byteorder

# note about digit sizes:

# In division, the native integer type must be able to hold

# a sign bit plus two digits plus 1 overflow bit.

#SHIFT = (LONG_BIT // 2) - 1

if SUPPORT_INT128:

SHIFT = 63

UDIGIT_TYPE = r_ulonglong

if LONG_BIT >= 64:

UDIGIT_MASK = intmask

else:

UDIGIT_MASK = longlongmask

LONG_TYPE = rffi.__INT128_T

ULONG_TYPE = rffi.__UINT128_T

if LONG_BIT > SHIFT:

STORE_TYPE = lltype.Signed

UNSIGNED_TYPE = lltype.Unsigned

else:

STORE_TYPE = rffi.LONGLONG

UNSIGNED_TYPE = rffi.ULONGLONG

else:

SHIFT = 31

UDIGIT_TYPE = r_uint

UDIGIT_MASK = intmask

STORE_TYPE = lltype.Signed

UNSIGNED_TYPE = lltype.Unsigned

LONG_TYPE = rffi.LONGLONG

ULONG_TYPE = rffi.ULONGLONG

MASK = int((1 << SHIFT) - 1)

FLOAT_MULTIPLIER = float(1 << SHIFT)

# For BIGINT and INT mix.

#

# The VALID range of an int is different than a valid range of a bigint of length one.

# -1 << LONG_BIT is actually TWO digits, because they are stored without the sign.

if SHIFT == LONG_BIT - 1:

MIN_INT_VALUE = -1 << SHIFT

def int_in_valid_range(x):

if x == MIN_INT_VALUE:

return False

return True

else:

# Means we don't have INT128 on 64bit.

def int_in_valid_range(x):

if x > MASK or x < -MASK:

return False

return True

int_in_valid_range._always_inline_ = True

# Debugging digit array access.

#

# False == no checking at all

# True == check 0 <= value <= MASK

# For long multiplication, use the O(N**2) school algorithm unless

# both operands contain more than KARATSUBA_CUTOFF digits (this

# being an internal Python long digit, in base BASE).

# Karatsuba is O(N**1.585)

USE_KARATSUBA = True # set to False for comparison

if SHIFT > 31:

KARATSUBA_CUTOFF = 19

else:

KARATSUBA_CUTOFF = 38

KARATSUBA_SQUARE_CUTOFF = 2 * KARATSUBA_CUTOFF

# For exponentiation, use the binary left-to-right algorithm

# unless the exponent contains more than FIVEARY_CUTOFF digits.

# In that case, do 5 bits at a time. The potential drawback is that

# a table of 2**5 intermediate results is computed.

FIVEARY_CUTOFF = 8

@specialize.argtype(0)

def _mask_digit(x):

return UDIGIT_MASK(x & MASK)

def _widen_digit(x):

return rffi.cast(LONG_TYPE, x)

def _unsigned_widen_digit(x):

return rffi.cast(ULONG_TYPE, x)

@specialize.argtype(0)

def _store_digit(x):

return rffi.cast(STORE_TYPE, x)

def _load_unsigned_digit(x):

return rffi.cast(UNSIGNED_TYPE, x)

_load_unsigned_digit._always_inline_ = True

NULLDIGIT = _store_digit(0)

ONEDIGIT = _store_digit(1)

NULLDIGITS = [NULLDIGIT]

def _check_digits(l):

for x in l:

assert type(x) is type(NULLDIGIT)

assert UDIGIT_MASK(x) & MASK == UDIGIT_MASK(x)

class InvalidEndiannessError(Exception):

pass

class InvalidSignednessError(Exception):

pass

class Entry(extregistry.ExtRegistryEntry):

_about_ = _check_digits

def compute_result_annotation(self, s_list):

from rpython.annotator import model as annmodel

assert isinstance(s_list, annmodel.SomeList)

s_DIGIT = self.bookkeeper.valueoftype(type(NULLDIGIT))

assert s_DIGIT.contains(s_list.listdef.listitem.s_value)

def specialize_call(self, hop):

hop.exception_cannot_occur()

def intsign(i):

return -1 if i < 0 else 1

class rbigint(object):

"""This is a reimplementation of longs using a list of digits."""

_immutable_ = True

_immutable_fields_ = ["_digits[*]", "size", "sign"]

def __init__(self, digits=NULLDIGITS, sign=0, size=0):

if not we_are_translated():

_check_digits(digits)

make_sure_not_resized(digits)

self._digits = digits

assert size >= 0

self.size = size or len(digits)

self.sign = sign

# __eq__ and __ne__ method exist for testing only, they are not RPython!

@not_rpython

def __eq__(self, other):

if not isinstance(other, rbigint):

return NotImplemented

return self.eq(other)

@not_rpython

def __ne__(self, other):

return not (self == other)

@specialize.argtype(1)

def digit(self, x):

"""Return the x'th digit, as an int."""

return self._digits[x]

digit._always_inline_ = True

def widedigit(self, x):

"""Return the x'th digit, as a long long int if needed

to have enough room to contain two digits."""

return _widen_digit(self._digits[x])

widedigit._always_inline_ = True

def uwidedigit(self, x):

"""Return the x'th digit, as a long long int if needed

to have enough room to contain two digits."""

return _unsigned_widen_digit(self._digits[x])

uwidedigit._always_inline_ = True

def udigit(self, x):

"""Return the x'th digit, as an unsigned int."""

return _load_unsigned_digit(self._digits[x])

udigit._always_inline_ = True

@specialize.argtype(2)

def setdigit(self, x, val):

val = _mask_digit(val)

assert val >= 0

self._digits[x] = _store_digit(val)

setdigit._always_inline_ = True

def numdigits(self):

w = self.size

assert w > 0

return w

numdigits._always_inline_ = True

@staticmethod

@jit.elidable

def fromint(intval):

# This function is marked as pure, so you must not call it and

# then modify the result.

check_regular_int(intval)

if intval < 0:

sign = -1

ival = -r_uint(intval)

carry = ival >> SHIFT

elif intval > 0:

sign = 1

ival = r_uint(intval)

carry = 0

else:

return NULLRBIGINT

if carry:

return rbigint([_store_digit(ival & MASK),

_store_digit(carry)], sign, 2)

else:

return rbigint([_store_digit(ival & MASK)], sign, 1)

@staticmethod

@jit.elidable

def frombool(b):

# You must not call this function and then modify the result.

if b:

return ONERBIGINT

return NULLRBIGINT

@staticmethod

@not_rpython

def fromlong(l):

return rbigint(*args_from_long(l))

@staticmethod

@jit.elidable

def fromfloat(dval):

""" Create a new bigint object from a float """

# This function is not marked as pure because it can raise

if math.isinf(dval):

raise OverflowError("cannot convert float infinity to integer")

if math.isnan(dval):

raise ValueError("cannot convert float NaN to integer")

return rbigint._fromfloat_finite(dval)

@staticmethod

@jit.elidable

def _fromfloat_finite(dval):

sign = 1

if dval < 0.0:

sign = -1

dval = -dval

frac, expo = math.frexp(dval) # dval = frac*2**expo; 0.0 <= frac < 1.0

if expo <= 0:

return NULLRBIGINT

ndig = (expo-1) // SHIFT + 1 # Number of 'digits' in result

v = rbigint([NULLDIGIT] * ndig, sign, ndig)

frac = math.ldexp(frac, (expo-1) % SHIFT + 1)

for i in range(ndig-1, -1, -1):

# use int(int(frac)) as a workaround for a CPython bug:

# with frac == 2147483647.0, int(frac) == 2147483647L

bits = int(int(frac))

v.setdigit(i, bits)

frac -= float(bits)

frac = math.ldexp(frac, SHIFT)

return v

@staticmethod

@jit.elidable

@specialize.argtype(0)

def fromrarith_int(i):

# This function is marked as pure, so you must not call it and

# then modify the result.

return rbigint(*args_from_rarith_int(i))

@staticmethod

@jit.elidable

def fromdecimalstr(s):

# This function is marked as elidable, so you must not call it and

# then modify the result.

return _decimalstr_to_bigint(s)

@staticmethod

@jit.elidable

def fromstr(s, base=0, allow_underscores=False):

"""As string_to_int(), but ignores an optional 'l' or 'L' suffix

and returns an rbigint."""

from rpython.rlib.rstring import NumberStringParser, \

strip_spaces

s = literal = strip_spaces(s)

if (s.endswith('l') or s.endswith('L')) and base < 22:

# in base 22 and above, 'L' is a valid digit! try: long('L',22)

s = s[:-1]

parser = NumberStringParser(s, literal, base, 'long',

allow_underscores=allow_underscores)

return rbigint._from_numberstring_parser(parser)

@staticmethod

def _from_numberstring_parser(parser):

return parse_digit_string(parser)

@staticmethod

@jit.elidable

def frombytes(s, byteorder, signed):

if byteorder not in ('big', 'little'):

raise InvalidEndiannessError()

if not s:

return NULLRBIGINT

if byteorder == 'big':

msb = ord(s[0])

itr = range(len(s)-1, -1, -1)

else:

msb = ord(s[-1])

itr = range(0, len(s))

sign = -1 if msb >= 0x80 and signed else 1

accum = _widen_digit(0)

accumbits = 0

digits = []

carry = 1

for i in itr:

c = _widen_digit(ord(s[i]))

if sign == -1:

c = (0xFF ^ c) + carry

carry = c >> 8

c &= 0xFF

accum |= c << accumbits

accumbits += 8

if accumbits >= SHIFT:

digits.append(_store_digit(intmask(accum & MASK)))

accum >>= SHIFT

accumbits -= SHIFT

if accumbits:

digits.append(_store_digit(intmask(accum)))

result = rbigint(digits[:], sign)

result._normalize()

return result

@jit.elidable

def tobytes(self, nbytes, byteorder, signed):

if byteorder not in ('big', 'little'):

raise InvalidEndiannessError()

if not signed and self.sign == -1:

raise InvalidSignednessError()

bswap = byteorder == 'big'

d = _widen_digit(0)

j = 0

imax = self.numdigits()

accum = _widen_digit(0)

accumbits = 0

result = StringBuilder(nbytes)

carry = 1

for i in range(0, imax):

d = self.widedigit(i)

if self.sign == -1:

d = (d ^ MASK) + carry

carry = d >> SHIFT

d &= MASK

accum |= d << accumbits

if i == imax - 1:

# Avoid bogus 0's

s = d ^ MASK if self.sign == -1 else d

while s:

s >>= 1

accumbits += 1

else:

accumbits += SHIFT

while accumbits >= 8:

if j >= nbytes:

raise OverflowError()

j += 1

result.append(chr(accum & 0xFF))

accum >>= 8

accumbits -= 8

if accumbits:

if j >= nbytes:

raise OverflowError()

j += 1

if self.sign == -1:

# Add a sign bit

accum |= (~_widen_digit(0)) << accumbits

result.append(chr(accum & 0xFF))

if j < nbytes:

signbyte = 0xFF if self.sign == -1 else 0

result.append_multiple_char(chr(signbyte), nbytes - j)

digits = result.build()

if j == nbytes and nbytes > 0 and signed:

# If not already set, we cannot contain the sign bit

msb = digits[-1]

if (self.sign == -1) != (ord(msb) >= 0x80):

raise OverflowError()

if bswap:

# Bah, this is very inefficient. At least it's not

# quadratic.

length = len(digits)

if length >= 0:

digits = ''.join([digits[i] for i in range(length-1, -1, -1)])

return digits

def toint(self):

"""

Get an integer from a bigint object.

Raises OverflowError if overflow occurs.

"""

if self.numdigits() > MAX_DIGITS_THAT_CAN_FIT_IN_INT:

raise OverflowError

return self._toint_helper()

@jit.elidable

def _toint_helper(self):

x = self._touint_helper()

# Haven't lost any bits so far

if self.sign >= 0:

res = intmask(x)

if res < 0:

raise OverflowError

else:

# Use "-" on the unsigned number, not on the signed number.

# This is needed to produce valid C code.

res = intmask(-x)

if res >= 0:

raise OverflowError

return res

@jit.elidable

def tolonglong(self):

return _AsLongLong(self)

def tobool(self):

return self.sign != 0

@jit.elidable

def touint(self):

if self.sign == -1:

raise ValueError("cannot convert negative integer to unsigned int")

return self._touint_helper()

@jit.elidable

def _touint_helper(self):

x = r_uint(0)

i = self.numdigits() - 1

while i >= 0:

prev = x

x = (x << SHIFT) + self.udigit(i)

if (x >> SHIFT) != prev:

raise OverflowError("long int too large to convert to unsigned int")

i -= 1

return x

@jit.elidable

def toulonglong(self):

if self.sign == -1:

raise ValueError("cannot convert negative integer to unsigned int")

return _AsULonglong_ignore_sign(self)

@jit.elidable

def uintmask(self):

return _AsUInt_mask(self)

@jit.elidable

def ulonglongmask(self):

"""Return r_ulonglong(self), truncating."""

return _AsULonglong_mask(self)

@jit.elidable

def tofloat(self):

return _AsDouble(self)

@jit.elidable

def format(self, digits, prefix='', suffix=''):

# 'digits' is a string whose length is the base to use,

# and where each character is the corresponding digit.

return _format(self, digits, prefix, suffix)

@jit.elidable

def repr(self):

try:

x = self.toint()

except OverflowError:

return self.format(BASE10, suffix="L")

return str(x) + "L"

@jit.elidable

def str(self):

try:

x = self.toint()

except OverflowError:

return self.format(BASE10)

return str(x)

@jit.elidable

def eq(self, other):

if (self.sign != other.sign or

self.numdigits() != other.numdigits()):

return False

i = 0

ld = self.numdigits()

while i < ld:

if self.digit(i) != other.digit(i):

return False

i += 1

return True

@jit.elidable

def int_eq(self, iother):

""" eq with int """

if not int_in_valid_range(iother):

# Fallback to Long.

return self.eq(rbigint.fromint(iother))

if self.numdigits() > 1:

return False

return (self.sign * self.digit(0)) == iother

def ne(self, other):

return not self.eq(other)

def int_ne(self, iother):

return not self.int_eq(iother)

@jit.elidable

def lt(self, other):

if self.sign > other.sign:

return False

if self.sign < other.sign:

return True

ld1 = self.numdigits()

ld2 = other.numdigits()

if ld1 > ld2:

if other.sign > 0:

return False

else:

return True

elif ld1 < ld2:

if other.sign > 0:

return True

else:

return False

i = ld1 - 1

while i >= 0:

d1 = self.digit(i)

d2 = other.digit(i)

if d1 < d2:

if other.sign > 0:

return True

else:

return False

elif d1 > d2:

if other.sign > 0:

return False

else:

return True

i -= 1

return False

@jit.elidable

def int_lt(self, iother):

""" lt where other is an int """

if not int_in_valid_range(iother):

# Fallback to Long.

return self.lt(rbigint.fromint(iother))

return _x_int_lt(self, iother, False)

def le(self, other):

return not other.lt(self)

def int_le(self, iother):

""" le where iother is an int """

if not int_in_valid_range(iother):

# Fallback to Long.

return self.le(rbigint.fromint(iother))

return _x_int_lt(self, iother, True)

def gt(self, other):

return other.lt(self)

def int_gt(self, iother):

return not self.int_le(iother)

def ge(self, other):

return not self.lt(other)

def int_ge(self, iother):

return not self.int_lt(iother)

@jit.elidable

def hash(self):

return _hash(self)

@jit.elidable

def add(self, other):

if self.sign == 0:

return other

if other.sign == 0:

return self

if self.sign == other.sign:

result = _x_add(self, other)

else:

result = _x_sub(other, self)

result.sign *= other.sign

return result

@jit.elidable

def int_add(self, iother):

if not int_in_valid_range(iother):

# Fallback to long.

return self.add(rbigint.fromint(iother))

elif self.sign == 0:

return rbigint.fromint(iother)

elif iother == 0:

return self

sign = intsign(iother)

if self.sign == sign:

result = _x_int_add(self, iother)

else:

result = _x_int_sub(self, iother)

result.sign *= -1

result.sign *= sign

return result

@jit.elidable

def sub(self, other):

if other.sign == 0:

return self

elif self.sign == 0:

return rbigint(other._digits[:other.numdigits()], -other.sign, other.numdigits())

elif self.sign == other.sign:

result = _x_sub(self, other)

else:

result = _x_add(self, other)

result.sign *= self.sign

return result

@jit.elidable

def int_sub(self, iother):

if not int_in_valid_range(iother):

# Fallback to long.

return self.sub(rbigint.fromint(iother))

elif iother == 0:

return self

elif self.sign == 0:

return rbigint.fromint(-iother)

elif self.sign == intsign(iother):

result = _x_int_sub(self, iother)

else:

result = _x_int_add(self, iother)

result.sign *= self.sign

return result

@jit.elidable

def mul(self, other):

selfsize = self.numdigits()

othersize = other.numdigits()

if selfsize > othersize:

self, other, selfsize, othersize = other, self, othersize, selfsize

if self.sign == 0 or other.sign == 0:

return NULLRBIGINT

if selfsize == 1:

if self._digits[0] == ONEDIGIT:

return rbigint(other._digits[:othersize], self.sign * other.sign, othersize)

elif othersize == 1:

res = other.uwidedigit(0) * self.udigit(0)

carry = res >> SHIFT

if carry:

return rbigint([_store_digit(res & MASK), _store_digit(carry)], self.sign * other.sign, 2)

else:

return rbigint([_store_digit(res & MASK)], self.sign * other.sign, 1)

result = _x_mul(self, other, self.digit(0))

elif USE_KARATSUBA:

if self is other:

i = KARATSUBA_SQUARE_CUTOFF

else:

i = KARATSUBA_CUTOFF

if selfsize <= i:

result = _x_mul(self, other)

"""elif 2 * selfsize <= othersize:

result = _k_lopsided_mul(self, other)"""

else:

result = _k_mul(self, other)

else:

result = _x_mul(self, other)

result.sign = self.sign * other.sign

return result

@jit.elidable

def int_mul(self, iother):

if not int_in_valid_range(iother):

# Fallback to long.

return self.mul(rbigint.fromint(iother))

if self.sign == 0 or iother == 0:

return NULLRBIGINT

asize = self.numdigits()

digit = abs(iother)

othersign = intsign(iother)

if digit == 1:

if othersign == 1:

return self

return rbigint(self._digits[:asize], self.sign * othersign, asize)

elif asize == 1:

udigit = r_uint(digit)

res = self.uwidedigit(0) * udigit

carry = res >> SHIFT

if carry:

return rbigint([_store_digit(res & MASK), _store_digit(carry)], self.sign * othersign, 2)

else:

return rbigint([_store_digit(res & MASK)], self.sign * othersign, 1)

elif digit & (digit - 1) == 0:

result = self.lqshift(ptwotable[digit])

else:

result = _muladd1(self, digit)

result.sign = self.sign * othersign

return result

@jit.elidable

def truediv(self, other):

div = _bigint_true_divide(self, other)

return div

@jit.elidable

def floordiv(self, other):

if other.numdigits() == 1:

otherint = other.digit(0) * other.sign

assert int_in_valid_range(otherint)

return self.int_floordiv(otherint)

div, mod = _divrem(self, other)

if mod.sign * other.sign == -1:

if div.sign == 0:

return ONENEGATIVERBIGINT

div = div.int_sub(1)

return div

def div(self, other):

return self.floordiv(other)

@jit.elidable

def int_floordiv(self, iother):

if not int_in_valid_range(iother):

# Fallback to long.

return self.floordiv(rbigint.fromint(iother))

if iother == 0:

raise ZeroDivisionError("long division by zero")

digit = abs(iother)

assert digit > 0

if self.sign == 1 and iother > 0:

if digit == 1:

return self

elif digit & (digit - 1) == 0:

return self.rqshift(ptwotable[digit])

div, mod = _divrem1(self, digit)

if mod != 0 and self.sign * intsign(iother) == -1:

if div.sign == 0:

return ONENEGATIVERBIGINT

div = div.int_add(1)

div.sign = self.sign * intsign(iother)

div._normalize()

return div

def int_div(self, iother):

return self.int_floordiv(iother)

@jit.elidable

def mod(self, other):

if other.sign == 0:

raise ZeroDivisionError("long division or modulo by zero")

if self.sign == 0:

return NULLRBIGINT

if other.numdigits() == 1:

otherint = other.digit(0) * other.sign

assert int_in_valid_range(otherint)

return self.int_mod(otherint)

else:

div, mod = _divrem(self, other)

if mod.sign * other.sign == -1:

mod = mod.add(other)

return mod

@jit.elidable

def int_mod(self, iother):

if iother == 0:

raise ZeroDivisionError("long division or modulo by zero")

if self.sign == 0:

return NULLRBIGINT

elif not int_in_valid_range(iother):

# Fallback to long.

return self.mod(rbigint.fromint(iother))

if 1: # preserve indentation to preserve history

digit = abs(iother)

if digit == 1:

return NULLRBIGINT

elif digit == 2:

modm = self.digit(0) & 1

if modm:

return ONENEGATIVERBIGINT if iother < 0 else ONERBIGINT

return NULLRBIGINT

elif digit & (digit - 1) == 0:

mod = self.int_and_(digit - 1)

else:

# Perform

size = UDIGIT_TYPE(self.numdigits() - 1)

if size > 0:

wrem = self.widedigit(size)

while size > 0:

size -= 1

wrem = ((wrem << SHIFT) | self.digit(size)) % digit

rem = _store_digit(wrem)

else:

rem = _store_digit(self.digit(0) % digit)

if rem == 0:

return NULLRBIGINT

mod = rbigint([rem], -1 if self.sign < 0 else 1, 1)

if mod.sign * intsign(iother) == -1:

mod = mod.int_add(iother)

return mod

@jit.elidable

def divmod(self, other):

"""

The / and % operators are now defined in terms of divmod().

The expression a mod b has the value a - b*floor(a/b).

The _divrem function gives the remainder after division of

|a| by |b|, with the sign of a. This is also expressed

as a - b*trunc(a/b), if trunc truncates towards zero.

Some examples:

a b a rem b a mod b

13 10 3 3

-13 10 -3 7

13 -10 3 -7

-13 -10 -3 -3

So, to get from rem to mod, we have to add b if a and b

have different signs. We then subtract one from the 'div'

part of the outcome to keep the invariant intact.

"""

div, mod = _divrem(self, other)

if mod.sign * other.sign == -1:

mod = mod.add(other)

if div.sign == 0:

return ONENEGATIVERBIGINT, mod

div = div.int_sub(1)

return div, mod

@jit.elidable

def int_divmod(self, iother):

""" Divmod with int """

if iother == 0:

raise ZeroDivisionError("long division or modulo by zero")

wsign = intsign(iother)

if not int_in_valid_range(iother) or (wsign == -1 and self.sign != wsign):

# Just fallback.

return self.divmod(rbigint.fromint(iother))

digit = abs(iother)

assert digit > 0

div, mod = _divrem1(self, digit)

# _divrem1 doesn't fix the sign

if div.size == 1 and div._digits[0] == NULLDIGIT:

div.sign = 0

else:

div.sign = self.sign * wsign

if self.sign < 0:

mod = -mod

if mod and self.sign * wsign == -1:

mod += iother

if div.sign == 0:

div = ONENEGATIVERBIGINT

else:

div = div.int_sub(1)

mod = rbigint.fromint(mod)

return div, mod

@jit.elidable

def pow(self, other, modulus=None):

negativeOutput = False # if x<0 return negative output

# 5-ary values. If the exponent is large enough, table is

# precomputed so that table[i] == self**i % modulus for i in range(32).

# python translation: the table is computed when needed.

if other.sign < 0: # if exponent is negative

if modulus is not None:

raise TypeError(

"pow() 2nd argument "

"cannot be negative when 3rd argument specified")

# XXX failed to implement

raise ValueError("bigint pow() too negative")

size_b = UDIGIT_TYPE(other.numdigits())

if modulus is not None:

if modulus.sign == 0:

raise ValueError("pow() 3rd argument cannot be 0")

# if modulus < 0:

# negativeOutput = True

# modulus = -modulus

if modulus.sign < 0:

negativeOutput = True

modulus = modulus.neg()

# if modulus == 1:

# return 0

if modulus.numdigits() == 1 and modulus._digits[0] == ONEDIGIT:

return NULLRBIGINT

# Reduce base by modulus in some cases:

# 1. If base < 0. Forcing the base non-neg makes things easier.

# 2. If base is obviously larger than the modulus. The "small

# exponent" case later can multiply directly by base repeatedly,

# while the "large exponent" case multiplies directly by base 31

# times. It can be unboundedly faster to multiply by

# base % modulus instead.

# We could _always_ do this reduction, but mod() isn't cheap,

# so we only do it when it buys something.

if self.sign < 0 or self.numdigits() > modulus.numdigits():

self = self.mod(modulus)

elif other.sign == 0:

return ONERBIGINT

elif self.sign == 0:

return NULLRBIGINT

elif size_b == 1:

if other._digits[0] == ONEDIGIT:

return self

elif self.numdigits() == 1 and modulus is None:

adigit = self.digit(0)

digit = other.digit(0)

if adigit == 1:

if self.sign == -1 and digit % 2:

return ONENEGATIVERBIGINT

return ONERBIGINT

elif adigit & (adigit - 1) == 0:

ret = self.lshift(((digit-1)*(ptwotable[adigit]-1)) + digit-1)

if self.sign == -1 and not digit % 2:

ret.sign = 1

return ret

# At this point self, other, and modulus are guaranteed non-negative UNLESS

# modulus is NULL, in which case self may be negative. */

z = ONERBIGINT