Author: Carl Friedrich Bolz-Tereick <[email protected]>
Branch: py3.6
Changeset: r96958:5a7ab6765acf
Date: 2019-07-10 13:38 +0200
http://bitbucket.org/pypy/pypy/changeset/5a7ab6765acf/
Log: merge default
diff --git a/rpython/jit/backend/arm/assembler.py
b/rpython/jit/backend/arm/assembler.py
--- a/rpython/jit/backend/arm/assembler.py
+++ b/rpython/jit/backend/arm/assembler.py
@@ -532,26 +532,22 @@
def gen_shadowstack_header(self, gcrootmap):
# lr = shadow stack top addr
- # r4 = *lr
+ # ip = *lr
rst = gcrootmap.get_root_stack_top_addr()
self.mc.gen_load_int(r.lr.value, rst)
- self.load_reg(self.mc, r.r4, r.lr)
- # *r4 = 1
- # the '1' is to benefit from the shadowstack 'is_minor' optimization
- self.mc.gen_load_int(r.ip.value, 1)
- self.store_reg(self.mc, r.ip, r.r4)
- # *(r4+WORD) = r.fp
- self.store_reg(self.mc, r.fp, r.r4, WORD)
+ self.load_reg(self.mc, r.ip, r.lr)
+ # *ip = r.fp
+ self.store_reg(self.mc, r.fp, r.ip)
#
- self.mc.ADD_ri(r.r4.value, r.r4.value, 2 * WORD)
- # *lr = r4 + 2 * WORD
- self.store_reg(self.mc, r.r4, r.lr)
+ self.mc.ADD_ri(r.ip.value, r.ip.value, WORD)
+ # *lr = ip + WORD
+ self.store_reg(self.mc, r.ip, r.lr)
def gen_footer_shadowstack(self, gcrootmap, mc):
rst = gcrootmap.get_root_stack_top_addr()
mc.gen_load_int(r.ip.value, rst)
self.load_reg(mc, r.r4, r.ip)
- mc.SUB_ri(r.r4.value, r.r4.value, 2 * WORD)
+ mc.SUB_ri(r.r4.value, r.r4.value, WORD)
self.store_reg(mc, r.r4, r.ip)
def _dump(self, ops, type='loop'):
diff --git a/rpython/jit/backend/arm/regalloc.py
b/rpython/jit/backend/arm/regalloc.py
--- a/rpython/jit/backend/arm/regalloc.py
+++ b/rpython/jit/backend/arm/regalloc.py
@@ -373,6 +373,10 @@
if box.type == REF and self.rm.is_still_alive(box):
assert not noregs
assert loc.is_core_reg()
+ #val = self.cpu.all_reg_indexes[loc.value]
+ # ^^^ That is the correct way to write it down, but as a
+ # special case in the arm backend only, this is equivalent
+ # to just the line below:
val = loc.value
gcmap[val // WORD // 8] |= r_uint(1) << (val % (WORD * 8))
for box, loc in self.fm.bindings.iteritems():
diff --git a/rpython/rlib/rbigint.py b/rpython/rlib/rbigint.py
--- a/rpython/rlib/rbigint.py
+++ b/rpython/rlib/rbigint.py
@@ -1423,6 +1423,12 @@
bits = ovfcheck((i-1) * SHIFT) + msd_bits
return bits
+ def gcd(self, other):
+ """ Compute the (always positive) greatest common divisor of self and
+ other """
+ return gcd_lehmer(self.abs(), other.abs())
+
+
def __repr__(self):
return "<rbigint digits=%s, sign=%s, size=%d, len=%d, %s>" %
(self._digits,
self.sign, self.numdigits(),
len(self._digits),
@@ -2960,3 +2966,88 @@
z.setdigit(pdigit, accum)
z._normalize()
return z
+
+
+def gcd_binary(a, b):
+ if a == 0:
+ return b
+
+ if b == 0:
+ return a
+
+ a, b = abs(a), abs(b)
+
+ shift = 0
+ while (a | b) & 1 == 0:
+ a >>= 1
+ b >>= 1
+ shift += 1
+
+ while a & 1 == 0:
+ a >>= 1
+
+ while b & 1 == 0:
+ b >>= 1
+
+ while a != b:
+ a, b = abs(a - b), min(a, b)
+ while a & 1 == 0:
+ a >>= 1
+
+ return a << shift
+
+def lehmer_xgcd(a, b):
+ s_old, s_new = 1, 0
+ t_old, t_new = 0, 1
+ while b >> (SHIFT >> 1):
+ q, r = a // b, a % b
+
+ a, b = b, r
+ s_old, s_new = s_new, s_old - q * s_new
+ t_old, t_new = t_new, t_old - q * t_new
+
+ return s_old, t_old, s_new, t_new
+
+def gcd_lehmer(a, b):
+ if a.lt(b):
+ a, b = b, a
+
+ while b.size > 1:
+ a_ms = a.digit(a.size-1)
+
+ x = 0
+ while a_ms & (0xFF << SHIFT-8) == 0:
+ a_ms <<= 8
+ x += 8
+
+ while a_ms & (1 << SHIFT-1) == 0:
+ a_ms <<= 1
+ x += 1
+
+ a_ms |= a.digit(a.size-2) >> SHIFT-x
+
+ if a.size == b.size:
+ b_ms = (b.digit(b.size-1) << x) | (b.digit(b.size-2) >> SHIFT-x)
+ elif a.size == b.size+1:
+ b_ms = b.digit(b.size-1) >> SHIFT-x
+ else:
+ b_ms = 0
+
+ if b_ms >> (SHIFT+1 >> 1) == 0:
+ a, b = b, a.mod(b)
+ continue
+
+ s_old, t_old, s_new, t_new = lehmer_xgcd(a_ms, b_ms)
+
+ n_a = a.int_mul(s_new).add(b.int_mul(t_new)).abs()
+ b = a.int_mul(s_old).add(b.int_mul(t_old)).abs()
+ a = n_a
+
+ if a.lt(b):
+ a, b = b, a
+
+ if not b.tobool():
+ return a
+
+ a = a.mod(b)
+ return rbigint.fromint(gcd_binary(b.toint(), a.toint()))
diff --git a/rpython/rlib/test/test_rbigint.py
b/rpython/rlib/test/test_rbigint.py
--- a/rpython/rlib/test/test_rbigint.py
+++ b/rpython/rlib/test/test_rbigint.py
@@ -11,12 +11,13 @@
from rpython.rlib import rbigint as lobj
from rpython.rlib.rarithmetic import r_uint, r_longlong, r_ulonglong, intmask
from rpython.rlib.rbigint import (rbigint, SHIFT, MASK, KARATSUBA_CUTOFF,
- _store_digit, _mask_digit, InvalidEndiannessError, InvalidSignednessError)
+ _store_digit, _mask_digit, InvalidEndiannessError, InvalidSignednessError,
+ gcd_lehmer, lehmer_xgcd, gcd_binary)
from rpython.rlib.rfloat import NAN
from rpython.rtyper.test.test_llinterp import interpret
from rpython.translator.c.test.test_standalone import StandaloneTests
-from hypothesis import given, strategies, example
+from hypothesis import given, strategies, example, settings
longs = strategies.builds(
long, strategies.integers())
@@ -836,6 +837,27 @@
t = bigint.tobytes(len(s), byteorder=byteorder, signed=signed)
assert s == t
+ def test_gcd(self):
+ assert gcd_binary(2*3*7**2, 2**2*7) == 2*7
+ assert gcd_binary(-2*3*7**2, 2**2*7) == 2*7
+ assert gcd_binary(2*3*7**2, -2**2*7) == 2*7
+ assert gcd_binary(-2*3*7**2, -2**2*7) == 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
+
+ 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):
@@ -1255,3 +1277,52 @@
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):
+ print(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)
diff --git a/rpython/translator/goal/targetbigintbenchmark.py
b/rpython/translator/goal/targetbigintbenchmark.py
--- a/rpython/translator/goal/targetbigintbenchmark.py
+++ b/rpython/translator/goal/targetbigintbenchmark.py
@@ -251,8 +251,19 @@
sumTime += _time
print "v = v + v", _time
+ x = rbigint.fromstr("13579246801357924680135792468013579246801")
+ y =
rbigint.fromstr("112233445566778899112233445566778899112233445566778899")
+ t = time()
+ for i in range(5000):
+ x.gcd(y)
+ x = x.int_mul(2).int_add(1)
+ _time = time() - t
+ print "gcd", _time
+
+ sumTime += _time
+
print "Sum: ", sumTime
-
+
return 0
# _____ Define and setup target ___
_______________________________________________
pypy-commit mailing list
[email protected]
https://mail.python.org/mailman/listinfo/pypy-commit
