Author: Armin Rigo <ar...@tunes.org>
Branch: py3.5
Changeset: r94818:4db575509642
Date: 2018-07-06 18:25 +0200
http://bitbucket.org/pypy/pypy/changeset/4db575509642/
Log: hg merge default
diff --git a/pypy/module/__pypy__/__init__.py b/pypy/module/__pypy__/__init__.py
--- a/pypy/module/__pypy__/__init__.py
+++ b/pypy/module/__pypy__/__init__.py
@@ -48,6 +48,7 @@
'int_lshift': 'interp_intop.int_lshift',
'int_rshift': 'interp_intop.int_rshift',
'uint_rshift': 'interp_intop.uint_rshift',
+ 'int_mulmod': 'interp_intop.int_mulmod',
}
diff --git a/pypy/module/__pypy__/interp_intop.py
b/pypy/module/__pypy__/interp_intop.py
--- a/pypy/module/__pypy__/interp_intop.py
+++ b/pypy/module/__pypy__/interp_intop.py
@@ -2,7 +2,7 @@
from rpython.rtyper.lltypesystem import lltype
from rpython.rtyper.lltypesystem.lloperation import llop
from rpython.rlib.rarithmetic import r_uint, intmask
-from rpython.rlib.rarithmetic import int_c_div, int_c_mod
+from rpython.rlib.rarithmetic import int_c_div, int_c_mod, mulmod
from rpython.rlib import jit
@@ -39,3 +39,7 @@
n = r_uint(n)
x = llop.uint_rshift(lltype.Unsigned, n, m)
return space.newint(intmask(x))
+
+@unwrap_spec(a=int, b=int, c=int)
+def int_mulmod(space, a, b, c):
+ return space.newint(mulmod(a, b, c))
diff --git a/pypy/module/__pypy__/test/test_intop.py
b/pypy/module/__pypy__/test/test_intop.py
--- a/pypy/module/__pypy__/test/test_intop.py
+++ b/pypy/module/__pypy__/test/test_intop.py
@@ -102,3 +102,7 @@
assert intop.uint_rshift(-1, 1) == sys.maxsize
assert intop.uint_rshift(-1, bits-2) == 3
assert intop.uint_rshift(-1, bits-1) == 1
+
+ def test_mulmod(self):
+ from __pypy__ import intop
+ assert intop.int_mulmod(9373891, 9832739, 2**31-1) == 1025488209
diff --git a/pypy/objspace/std/intobject.py b/pypy/objspace/std/intobject.py
--- a/pypy/objspace/std/intobject.py
+++ b/pypy/objspace/std/intobject.py
@@ -371,20 +371,23 @@
return wrapint(space, a)
-@jit.look_inside_iff(lambda space, iv, iw, iz:
- jit.isconstant(iw) and jit.isconstant(iz))
def _pow(space, iv, iw, iz):
"""Helper for pow"""
- if iw < 0:
- if iz != 0:
- raise oefmt(space.w_ValueError,
- "pow() 2nd argument cannot be negative when 3rd "
- "argument specified")
+ if iz == 0:
+ return _pow_nomod(iv, iw)
+ else:
+ return _pow_mod(space, iv, iw, iz)
+
+@jit.look_inside_iff(lambda iv, iw: jit.isconstant(iw))
+def _pow_nomod(iv, iw):
+ if iw <= 0:
+ if iw == 0:
+ return 1
# bounce it, since it always returns float
raise ValueError
temp = iv
ix = 1
- while iw > 0:
+ while True:
if iw & 1:
try:
ix = ovfcheck(ix * temp)
@@ -397,12 +400,40 @@
temp = ovfcheck(temp * temp) # Square the value of temp
except OverflowError:
raise
- if iz:
- # If we did a multiplication, perform a modulo
- ix %= iz
- temp %= iz
- if iz:
- ix %= iz
+ return ix
+
+@jit.look_inside_iff(lambda space, iv, iw, iz:
+ jit.isconstant(iw) and jit.isconstant(iz))
+def _pow_mod(space, iv, iw, iz):
+ from rpython.rlib.rarithmetic import mulmod
+
+ if iw <= 0:
+ if iw == 0:
+ return 1 % iz # != 1, for iz == 1 or iz < 0
+ raise oefmt(space.w_ValueError,
+ "pow() 2nd argument cannot be negative when 3rd "
+ "argument specified")
+ if iz < 0:
+ try:
+ iz = ovfcheck(-iz)
+ except OverflowError:
+ raise
+ iz_negative = True
+ else:
+ iz_negative = False
+
+ temp = iv
+ ix = 1
+ while True:
+ if iw & 1:
+ ix = mulmod(ix, temp, iz)
+ iw >>= 1 # Shift exponent down by 1 bit
+ if iw == 0:
+ break
+ temp = mulmod(temp, temp, iz)
+
+ if iz_negative and ix > 0:
+ ix -= iz
return ix
diff --git a/pypy/objspace/std/test/test_intobject.py
b/pypy/objspace/std/test/test_intobject.py
--- a/pypy/objspace/std/test/test_intobject.py
+++ b/pypy/objspace/std/test/test_intobject.py
@@ -1,7 +1,8 @@
# encoding: utf-8
import sys
+from pypy.interpreter.error import OperationError
from pypy.objspace.std import intobject as iobj
-from rpython.rlib.rarithmetic import r_uint, is_valid_int
+from rpython.rlib.rarithmetic import r_uint, is_valid_int, intmask
from rpython.rlib.rbigint import rbigint
class TestW_IntObject:
@@ -169,6 +170,63 @@
assert space.isinstance_w(v, space.w_int)
assert space.bigint_w(v).eq(rbigint.fromlong(pow(10, 20)))
+ try:
+ from hypothesis import given, strategies, example
+ except ImportError:
+ pass
+ else:
+ @given(
+ a=strategies.integers(min_value=-sys.maxint-1,
max_value=sys.maxint),
+ b=strategies.integers(min_value=-sys.maxint-1,
max_value=sys.maxint),
+ c=strategies.integers(min_value=-sys.maxint-1,
max_value=sys.maxint))
+ @example(0, 0, -sys.maxint-1)
+ @example(0, 1, -sys.maxint-1)
+ @example(1, 0, -sys.maxint-1)
+ def test_hypot_pow(self, a, b, c):
+ if c == 0:
+ return
+ #
+ # "pow(a, b, c)": if b < 0, should get an app-level ValueError.
+ # Otherwise, should always work except if c == -maxint-1
+ if b < 0:
+ expected = "app-level ValueError"
+ elif b > 0 and c == -sys.maxint-1:
+ expected = OverflowError
+ else:
+ expected = pow(a, b, c)
+
+ try:
+ result = iobj._pow(self.space, a, b, c)
+ except OperationError as e:
+ assert ('ValueError: pow() 2nd argument cannot be negative '
+ 'when 3rd argument specified' ==
e.errorstr(self.space))
+ result = "app-level ValueError"
+ except OverflowError:
+ result = OverflowError
+ assert result == expected
+
+ @given(
+ a=strategies.integers(min_value=-sys.maxint-1,
max_value=sys.maxint),
+ b=strategies.integers(min_value=-sys.maxint-1,
max_value=sys.maxint))
+ def test_hypot_pow_nomod(self, a, b):
+ # "a ** b": detect overflows and ValueErrors
+ if b < 0:
+ expected = ValueError
+ elif b > 128 and not (-1 <= a <= 1):
+ expected = OverflowError
+ else:
+ expected = a ** b
+ if expected != intmask(expected):
+ expected = OverflowError
+
+ try:
+ result = iobj._pow(self.space, a, b, 0)
+ except ValueError:
+ result = ValueError
+ except OverflowError:
+ result = OverflowError
+ assert result == expected
+
def test_neg(self):
space = self.space
x = 42
diff --git a/rpython/rlib/rarithmetic.py b/rpython/rlib/rarithmetic.py
--- a/rpython/rlib/rarithmetic.py
+++ b/rpython/rlib/rarithmetic.py
@@ -840,6 +840,31 @@
return z
+@specialize.memo()
+def check_support_int128():
+ from rpython.rtyper.lltypesystem import rffi
+ return hasattr(rffi, '__INT128_T')
+
+def mulmod(a, b, c):
+ """Computes (a * b) % c.
+ Assumes c > 0, and returns a nonnegative result.
+ """
+ assert c > 0
+ if LONG_BIT < LONGLONG_BIT:
+ a = r_longlong(a)
+ b = r_longlong(b)
+ return intmask((a * b) % c)
+ elif check_support_int128():
+ a = r_longlonglong(a)
+ b = r_longlonglong(b)
+ return intmask((a * b) % c)
+ else:
+ from rpython.rlib.rbigint import rbigint
+ a = rbigint.fromlong(a)
+ b = rbigint.fromlong(b)
+ return a.mul(b).int_mod(c).toint()
+
+
# String parsing support
# ---------------------------
diff --git a/rpython/rlib/rbigint.py b/rpython/rlib/rbigint.py
--- a/rpython/rlib/rbigint.py
+++ b/rpython/rlib/rbigint.py
@@ -1,6 +1,7 @@
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
@@ -10,7 +11,7 @@
import math, sys
-SUPPORT_INT128 = hasattr(rffi, '__INT128_T')
+SUPPORT_INT128 = check_support_int128()
BYTEORDER = sys.byteorder
# note about digit sizes:
diff --git a/rpython/rlib/test/test_rarithmetic.py
b/rpython/rlib/test/test_rarithmetic.py
--- a/rpython/rlib/test/test_rarithmetic.py
+++ b/rpython/rlib/test/test_rarithmetic.py
@@ -1,5 +1,6 @@
from rpython.rtyper.test.tool import BaseRtypingTest
from rpython.rtyper.test.test_llinterp import interpret
+from rpython.rlib import rarithmetic
from rpython.rlib.rarithmetic import *
from rpython.rlib.rstring import ParseStringError, ParseStringOverflowError
from hypothesis import given, strategies, assume
@@ -731,3 +732,17 @@
py.test.raises(OverflowError, ovfcheck_int32_sub, 2**30, -2**30)
assert ovfcheck_int32_mul(-2**16, 2**15) == -2**31
py.test.raises(OverflowError, ovfcheck_int32_mul, -2**16, -2**15)
+
+@given(strategies.integers(min_value=-sys.maxint-1, max_value=sys.maxint),
+ strategies.integers(min_value=-sys.maxint-1, max_value=sys.maxint),
+ strategies.integers(min_value=1, max_value=sys.maxint))
+def test_mulmod(a, b, c):
+ assert mulmod(a, b, c) == (a * b) % c
+ #
+ import rpython.rlib.rbigint # import before patching check_support_int128
+ prev = rarithmetic.check_support_int128
+ try:
+ rarithmetic.check_support_int128 = lambda: False
+ assert mulmod(a, b, c) == (a * b) % c
+ finally:
+ rarithmetic.check_support_int128 = prev
diff --git a/rpython/translator/c/test/test_typed.py
b/rpython/translator/c/test/test_typed.py
--- a/rpython/translator/c/test/test_typed.py
+++ b/rpython/translator/c/test/test_typed.py
@@ -962,3 +962,12 @@
f = self.getcompiled(func, [int])
res = f(2)
assert res == 1 # and not 2
+
+ def test_mulmod(self):
+ from rpython.rlib.rarithmetic import mulmod
+
+ def func(a, b, c):
+ return mulmod(a, b, c)
+ f = self.getcompiled(func, [int, int, int])
+ res = f(1192871273, 1837632879, 2001286281)
+ assert res == 1573897320
_______________________________________________
pypy-commit mailing list
pypy-commit@python.org
https://mail.python.org/mailman/listinfo/pypy-commit
