Subject: bug#12350: Composites identified as primes in factor.c (when HAVE_GMP)

From: Jim Meyering <[email-masked]>
Date: Thu, 06 Sep 2012 22:23:42 +0200

Torbjorn Granlund wrote:
> I and Niels now would appreciate feedback on the new factor code.
>
> We've put the entire little project in a tar file, which is attached.
> The code is also available at <http://gmplib.org:8000/factoring/>.

Thanks a lot!  I've started looking at the code.
I was surprised to see "make check" fail.

    $ ./ourseq 0 100000 > k                                                      :
    $ ./factor < k                                                               :
    0:
    1:
    2: 2
    3: 3
    4: 2 2
    5: 5
    6: 2 3
    7: 7
    8: 2 2 2
    9: 3 3
    zsh: abort (core dumped)  ./factor < k

That was due to unexpected input.
Poking around, I see that ourseq writes from uninitialized memory:

    $ ./ourseq 9 11
    9
    102
    112
    $ ./ourseq 9 11
    9
    10>
    11>
    $ ./ourseq 9 11
    9
    10"
    11"

The fix is to change the memmove to copy one more byte each time:
to copy the required trailing NUL.
With that, it looks like "make check" will pass.
It will definitely benefit from running the individual
tests in parallel ;-)

>From 9e6db73344f43e828b8d716a0ea6a5842980d518 Mon Sep 17 00:00:00 2001
From: Jim Meyering <[email-masked]>
Date: Thu, 6 Sep 2012 22:12:41 +0200
Subject: [PATCH] incr: don't omit trailing NUL when incrementing

---
 ourseq.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/ourseq.c b/ourseq.c
index d2472aa..cb71f13 100644
--- a/ourseq.c
+++ b/ourseq.c
@@ -48,7 +48,7 @@ incr (string *st)
 	}
       s[i] = '0';
     }
-  memmove (s + 1, s, len);
+  memmove (s + 1, s, len + 1);
   s[0] = '1';
   st->len = len + 1;
 }
--
1.7.12.176.g3fc0e4c