akr	2013-07-07 10:22:55 +0900 (Sun, 07 Jul 2013)

  New Revision: 41813

  http://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=rev&revision=41813

  Log:
    * 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.

  Modified files:
    trunk/ChangeLog
    trunk/bignum.c

Index: ChangeLog
===================================================================
--- ChangeLog	(revision 41812)
+++ ChangeLog	(revision 41813)
@@ -1,3 +1,9 @@ https://github.com/ruby/ruby/blob/trunk/ChangeLog#L1
+Sun Jul  7 10:07:22 2013  Tanaka Akira  <akr@f...>
+
+	* 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.
+
 Sat Jul  6 07:37:43 2013  Martin Bosslet  <Martin.Bosslet@g...>
 
 	* ext/openssl/ossl_pkey_ec.c: Ensure compatibility to builds of
Index: bignum.c
===================================================================
--- bignum.c	(revision 41812)
+++ bignum.c	(revision 41813)
@@ -4388,23 +4388,23 @@ bigmul1_toom3(VALUE x, VALUE y) https://github.com/ruby/ruby/blob/trunk/bignum.c#L4388
  * 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) https://github.com/ruby/ruby/blob/trunk/bignum.c#L4412
 	    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;
 }
 

--
ML: ruby-changes@q...
Info: http://www.atdot.net/~ko1/quickml/