From b2cf5f36b904c86352665aa8f789ea56d2391290 Mon Sep 17 00:00:00 2001 From: akr Date: Sun, 7 Jul 2013 01:22:55 +0000 Subject: * bignum.c (bary_sq_fast): Extracted from bigsqr_fast and ensure not to access zds[2*xn]. (bigsqr_fast): Allocate the result bignum with 2*xn words. git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@41813 b2dd03c8-39d4-4d8f-98ff-823fe69b080e --- bignum.c | 34 +++++++++++++++++++++++----------- 1 file changed, 23 insertions(+), 11 deletions(-) (limited to 'bignum.c') diff --git a/bignum.c b/bignum.c index 4176d0f9b4..ae2778f6a5 100644 --- a/bignum.c +++ b/bignum.c @@ -4388,23 +4388,23 @@ bigmul1_toom3(VALUE x, VALUE y) * ref: Handbook of Applied Cryptography, Algorithm 14.16 * http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf */ -static VALUE -bigsqr_fast(VALUE x) +static void +bary_sq_fast(BDIGIT *zds, size_t zn, BDIGIT *xds, size_t xn) { - long len = RBIGNUM_LEN(x), i, j; - VALUE z = bignew(2 * len + 1, 1); - BDIGIT *xds = BDIGITS(x), *zds = BDIGITS(z); + size_t i, j; BDIGIT_DBL c, v, w; - for (i = 2 * len + 1; i--; ) zds[i] = 0; - for (i = 0; i < len; i++) { + assert(xn * 2 <= zn); + + MEMZERO(zds, BDIGIT, zn); + for (i = 0; i < xn; i++) { v = (BDIGIT_DBL)xds[i]; if (!v) continue; c = (BDIGIT_DBL)zds[i + i] + v * v; zds[i + i] = BIGLO(c); c = BIGDN(c); v *= 2; - for (j = i + 1; j < len; j++) { + for (j = i + 1; j < xn; j++) { w = (BDIGIT_DBL)xds[j]; c += (BDIGIT_DBL)zds[i + j] + BIGLO(v) * w; zds[i + j] = BIGLO(c); @@ -4412,12 +4412,24 @@ bigsqr_fast(VALUE x) if (BIGDN(v)) c += w; } if (c) { - c += (BDIGIT_DBL)zds[i + len]; - zds[i + len] = BIGLO(c); + c += (BDIGIT_DBL)zds[i + xn]; + zds[i + xn] = BIGLO(c); c = BIGDN(c); + assert(c == 0 || i != xn-1); + if (c && i != xn-1) zds[i + xn + 1] += (BDIGIT)c; } - if (c) zds[i + len + 1] += (BDIGIT)c; } +} + +static VALUE +bigsqr_fast(VALUE x) +{ + long xn = RBIGNUM_LEN(x); + VALUE z = bignew(2 * xn, 1); + BDIGIT *xds = BDIGITS(x), *zds = BDIGITS(z); + + bary_sq_fast(zds, RBIGNUM_LEN(z), xds, xn); + return z; } -- cgit v1.2.3