On Thu, Sep 01, 2016 at 06:36:15AM +0100, Theo Buehler wrote:
> In factor(6), there is the line
>
> 216 stop = usqrt(val) + 1;
>
> where the u_int64_t stop is the upper bound for the sieve of
> Eratosthenes (I cautiously added 1 to be sure to be on the safe side).
> Unfortunately, the right hand side may now overflow for large enough
> val because my brilliant former self chose usqrt() to be of type
> u_int32_t usqrt(u_sqrt64_t); ...
>
> Example from http://cvsweb.netbsd.org/bsdweb.cgi/src/games/primes/pattern.c
>
> $ printf "%u\n" $((139646831 * 132095686967))
> 18446744073709551577
> $ factor 18446744073709551577
> 18446744073709551577
>
> With the patch below:
>
> $ obj/factor
> 18446744073709551577: 139646831 132095686967
>
> as it should be.
ok,
-Otto
>
> Index: factor.c
> ===================================================================
> RCS file: /var/cvs/src/games/factor/factor.c,v
> retrieving revision 1.29
> diff -u -p -r1.29 factor.c
> --- factor.c 14 Aug 2016 18:34:48 -0000 1.29
> +++ factor.c 1 Sep 2016 04:56:00 -0000
> @@ -75,7 +75,7 @@ extern const int pattern_size;
>
> static void pr_fact(u_int64_t); /* print factors of a value */
> static void pr_bigfact(u_int64_t);
> -static u_int32_t usqrt(u_int64_t);
> +static u_int64_t usqrt(u_int64_t);
> static void __dead usage(void);
>
> int
> @@ -284,7 +284,7 @@ pr_bigfact(u_int64_t val) /* Factor this
> }
>
> /* Code taken from ping.c */
> -static u_int32_t
> +static u_int64_t
> usqrt(u_int64_t n)
> {
> u_int64_t y, x = 1;
> @@ -299,7 +299,7 @@ usqrt(u_int64_t n)
> x /= 2;
> } while (((y < x) && (x - y) > 1) || (y - x) > 1);
>
> - return (u_int32_t)x;
> + return x;
> }
>
> static void __dead
