Age | Commit message (Collapse) | Author |
|
* src/factor.c: Remove unneeded #inclusion of"verify.h".
It's already included via system.h.
|
|
With this change, the maintainer builds primes.h and it is part of
the tarball. primes.h's contents are not architecture-specific.
* .gitignore: Remove /src/primes.h.
* src/factor.c: Include verify.h.
(W): New constant. Verify that uintmax_t lacks holes
and that W is no wider than the integers used to generate primes.h.
* src/local.mk (EXTRA_DIST): Add src/primes.h.
(BUILT_SOURCES, CLEANFILES): Remove src/primes.h.
($(top_srcdir)/src/primes.h): Rename from src/primes.h.
Do not depend on src/make-prime-list. Instead, use sub-make to
build, so that we build primes.h only if it does not exist.
* src/make-prime-list.c: Include <limits.h>, for ULONG_MAX.
(wide_uint): Define to uintmax_t or unsigned __int128 if not #defined.
(struct prime, binvert, process_prime): Use it instead of uintmax_t.
(print_wide_uint): New function. This generates the proper pinv
value regardless of the width of uintmax_t on the target, so long
as the width doesn't exceed that of the width of wide_uint on the
maintainer host that generated src/primes.h.
(output_primes): Use it. Output WIDE_UINT_BITS, too. Let the
target compute its own lim, since its uintmax_t may be narrower
than ours.
(SZ): Remove.
* src/primes.h: New file, generated with 128-bit integers and usable
on any host where uintmax_t's width is no greater than 128 bits.
|
|
This was not seen to be an issue in practise,
but to make the code more robust, don't assume
uintmax_t is 64 bits.
* src/factor.c (W_TYPE_SIZE): Define based on integer limits.
* src/make-prime-list.c (output_primes): Define format width
based on integer limits.
|
|
* src/factor.c (print_uintmaxes): Replace with PRIuMAX.
* src/join.c (check_order): Likewise.
* cfg.mk (sc_check-j-printf-format): Add a syntax-check rule
to flag new cases of this.
|
|
* src/factor.c (is_square): Use active voice in comment, not passive.
(factor): Add function-describing comment.
(mp_factor): Likewise.
|
|
src/factor.c (__GMP_DECLSPEC): Move back from longlong.h
to treat consistently with other stub macros.
(__GMP_GNUC_PREREQ): Reference to avoid -Wunused-macros warning.
(__GMP_DECLSPEC): Likewise.
(ASSERT): Likewise.
(__clz_tab): Likewise.
(factor_using_division): Mark a variable as unused.
(mulredc): Likewise.
(mulredc2): Likewise.
(divexact_21): Likewise.
|
|
* src/factor.c (factor_using_pollard_rho2): On some systems
(like sparc) we need to promote all addmod2() parameters
to uintmax_t to avoid warnings.
|
|
In the recent factor rewrite, the GMP code
wasn't actually used; just an error was printed
on integer overflow. While fixing that it was noticed
that correct input validation wasn't done in all cases
when falling back to the GMP code.
* src/factor.c (print_factors) Fallback to GMP on overflow.
(strto2uintmax): Scan the string for invalid characters,
so that case can be detected independently of overflow.
Return an error when an empty string is passed.
Also allow leading spaces and '+' in input numbers.
* tests/misc/factor.pl: Ensure the GMP code is exercised
when compiled in. Also add a test to verify leading
spaces and '+' are allowed.
|
|
The new factor code introduced usage of mpz_inits() and
mpz_clears(), which are only available since GMP >= 5,
and will result in a compile error when missing.
* m4/gmp.m4 (cu_GMP): Define HAVE_DECL_MPZ_INITS appropriately.
* src/factor (mpz_inits): New function, defined where missing.
(mpz_clears): Likewise.
|
|
On some systems, -Wunused-macros would warn about two macros:
src/factor.c:148:0: warning: macro "__clz_tab" is not used
src/factor.c:126:0: warning: macro "UHWtype" is not used
* src/factor.c: Add a use to placate gcc.
|
|
* src/factor.c (print_factors_single): Use fputs and umaxtostr
rather than printf with "%ju". This reduced the time required
to compute and print the factors of the first 10^7 integers from
over 8 seconds to 5.75s. Run this command:
seq $((10**7)) | env time factor > /dev/null
|
|
* src/factor.c: Renamed from factor-ng.c, with the following changes:
Adjust copyright header to be consistent with others.
Use xmalloc and xrealloc, to avoid segv upon OOM.
Switch back to using readtokens to handle input.
Diagnose invalid inputs.
s/fprintf+exit/error/
(print_factors): Add comments.
(strto2uintmax): Return strtol_error, not int.
(read_item): Remove, no longer used.
(main): Use atexit(close_stdout) so that we don't ignore failed write.
* cfg.mk: Exempt src/longlong.h from several tests.
Exempt run.sh from the test-list-consistency test.
Exempt make-prime-list.c from numerous tests, since we won't
be making it conform: it must not link with libcoreutils.a.
Exempt factor-ng.c from the no-upper-case error message test.
* AUTHORS (factor): Add Torbjörn and Niels.
* tests/local.mk (factor_tests): Encode the 37 tests.
($(factor_tests)): Rule to generate a test script for each test.
* tests/factor/run.sh: New script, marked as very expensive.
* .gitignore: Ignore new generated files.
* src/local.mk (src/primes.h): New rule.
(noinst_PROGRAMS): Add make-prime-list.
(noinst_HEADERS): Add longlong.h.
Remove all wheel-related rules and files.
* src/wheel-gen.pl: Remove file.
maint: mark set-but-not-used variables with ATTRIBUTE_UNUSED
* src/factor-ng.c (redcify, prime_p, isqrt2): Mark them, so we
don't have to disable -Wunused-but-set-variable.
maint: use __builtin_expect only if __GNUC__
* src/factor-ng.c (LIKELY, UNLIKELY) [__GNUC__]: Add #ifdef guard.
build: avoid warning about unused macro
* src/factor-ng.c (__GMP_DECLSPEC): Don't define here
* src/longlong.h (__GMP_DECLSPEC): Define if not already defined.
|
|
The multiple-precision factoring code (with HAVE_GMP) was copied from
a now-obsolete version of GMP that did not pass proper arguments to
the mpz_probab_prime_p function. It makes that code perform no more
than 3 Miller-Rabin tests only, which is not sufficient.
A Miller-Rabin test will detect composites with at least a probability
of 3/4. For a uniform random composite, the probability will actually
be much higher.
Or put another way, of the N-3 possible Miller-Rabin tests for checking
the composite N, there is no number N for which more than (N-3)/4 of the
tests will fail to detect the number as a composite. For most numbers N
the number of "false witnesses" will be much, much lower.
Problem numbers are of the form N=pq, p,q prime and (p-1)/(q-1) = s,
where s is a small integer. (There are other problem forms too,
involving 3 or more prime factors.) When s = 2, we get the 3/4 factor.
It is easy to find numbers of that form that cause coreutils' factor to
fail:
465658903
2242724851
6635692801
17709149503
17754345703
20889169003
42743470771
54890944111
72047131003
85862644003
98275842811
114654168091
117225546301
...
There are 9008992 composites of the form with s=2 below 2^64. With 3
Miller-Rabin tests, one would expect about 9008992/64 = 140766 to be
invalidly recognized as primes in that range.
* src/factor.c (MR_REPS): Define to 25.
(factor_using_pollard_rho): Use MR_REPS, not 3.
(print_factors_multi): Likewise.
* THANKS.in: Remove my name, now that it will be automatically
included in the generated THANKS file.
|
|
Run "make update-copyright".
|
|
Run this (twice):
git grep -E -l '`[^ ]+'\' src/*.c \
|xargs perl -pi -e 's/`([^ ]+'\'')/'\''$1/'
|
|
Run this command:
perl -0777 -pi -e \
's/fprintf \(stderr, _\("Try `%s --help.*\n.*;/emit_try_help ();/m'\
src/*.c
|
|
Run "make update-copyright".
|
|
* src/factor.c (factor_using_pollard_rho): Change type of "i"
to unsigned to avoid warning from gcc's -Wstrict-overflow.
* src/expr.c: Use an unsigned intermediate.
* src/dircolors.c (main): Reorder operations to avoid the risk of
pointer overflow.
* src/tr.c (squeeze_filter): Change NOT_A_CHAR from an anonymous
"enum" to an "int", to avoid this warning:
tr.c:1624:10: error: assuming signed overflow does not occur when
simplifying conditional to constant [-Werror=strict-overflow]
* src/pr.c (main): Make index "i" unsigned.
|
|
Run "make update-copyright".
|
|
Run this command:
git ls-files | grep '\.[ch]$' \
| xargs perl -pi -e 's/for \(;;\)/while (true)/g'
...except for randint.c, which does not include stdbool.h.
In that case, use "while (1)".
* gl/lib/randint.c (randint_genmax): Use "while (1)" for infloops.
* src/cat.c (simple_cat, cat): Use "while (true)" for infloops.
* gl/lib/randread.c (readsource, readisaac): Likewise.
* src/copy.c (copy_reg): Likewise.
* src/csplit.c (record_line_starts, process_regexp): Likewise.
* src/cut.c (set_fields): Likewise.
* src/dd.c (iread, parse_symbols): Likewise.
* src/df.c (find_mount_point, main): Likewise.
* src/du.c (main): Likewise.
* src/expand.c (expand): Likewise.
* src/factor.c (factor_using_division, do_stdin): Likewise.
* src/fmt.c (get_space): Likewise.
* src/ls.c (decode_switches): Likewise.
* src/od.c (main): Likewise.
* src/pr.c (main, read_line): Likewise.
* src/shred.c (dopass, genpattern): Likewise.
* src/sort.c (initbuf, fillbuf, getmonth, keycompare): Likewise.
* src/split.c (bytes_split, lines_split): Likewise.
* src/tac.c (tac_seekable): Likewise.
* src/test.c (and, or): Likewise.
* src/tr.c (squeeze_filter, main): Likewise.
* src/tsort.c (search_item): Likewise.
* src/unexpand.c (unexpand): Likewise.
* src/uniq.c (main): Likewise.
* src/yes.c (main): Likewise.
|
|
Use this command:
git ls-files | grep -v COPYING \
| xargs env UPDATE_COPYRIGHT_USE_INTERVALS=1 \
build-aux/update-copyright
|
|
* src/factor.c (debug): Add missing va_end.
|
|
* src/chroot.c (set_additional_groups): Use X2NREALLOC rather than
x2nrealloc.
* src/factor.c (emit_factor): Likewise.
* src/setuidgid.c (main): Likewise.
|
|
* src/system.h: Rename emit_bug_reporting_address() to
emit_ancillary_info() and update it to not print the translation
project address in en_* locales, and _do_ print it in the 'C'
(and other) locales so that it's included in the default man page.
Also mention how to invoke the texinfo documentation for each command.
Also move the "hard-locale.h" include to the 8 files that now use it.
* man/help2man: Strip the newly added texinfo reference from the
--help output as a more verbose version is already added by help2man.
Suggestion from C de-Avillez
|
|
* src/stty.c: Make cpp indentation reflect nesting.
* src/factor.c: Likewise.
|
|
Transformed via this shell code:
t=$'\t'
git ls-files \
| grep -vE '(^|/)((GNU)?[Mm]akefile|ChangeLog)|\.(am|mk)$' \
| grep -vE 'tests/pr/|help2man' \
| xargs grep -lE "^ *$t" \
| xargs perl -MText::Tabs -ni -le \
'$m=/^( *\t[ \t]*)(.*)/; print $m ? expand($1) . $2 : $_'
|
|
* src/sort.c (main): Use ARRAY_CARDINALITY, rather than open-coding it.
* src/factor.c (WHEEL_END): Likewise.
* src/csplit.c (main): Likewise.
* src/od.c: Likewise,
* src/ls.c (main): Likewise.
(N_ENTRIES): Remove definition. Use ARRAY_CARDINALITY instead.
* src/dircolors.c: Likewise.
(array_len): Remove definition.
|
|
* src/ls.c (ASSERT_MATCHING_DEV_INO): Comment-out unused definition,
to match commented-out use.
* src/install.c (INITIAL_HASH_MODULE, INITIAL_ENTRY_TAB_SIZE):
(READ_SIZE): Remove definitions of unused macros.
* src/mv.c (INITIAL_HASH_MODULE, INITIAL_ENTRY_TAB_SIZE): Likewise.
* src/dd.c (max): Likewise.
* src/expand.c (OUTPUT_BLOCK): Likewise.
* src/csplit.c (ALLOC_SIZE): Likewise.
* src/pr.c (NULLCOL): Likewise.
* src/ptx.c (Sword): Likewise.
* src/unexpand.c (OUTPUT_BLOCK): Likewise.
* src/factor.c (NDEBUG): Likewise.
|
|
* src/factor.c (emit_ul_factor): Call mpz_clear.
|
|
* src/factor.c (debug) [!HAVE_GMP]: Define.
Reported by Bob Proulx.
|
|
Here's a patch to remove the --bignum and --no-bignum options from
'factor'. The case for removing --bignum isn't as strong as that for
'expr', but still, it seems to me that these options are not needed and
complicate the documentation unnecessarily.
* doc/coreutils.texi (factor invocation): Remove --bignum, --no-bignum.
* src/factor.c (algorithm, ALGORITHM_CHOICE, USE_BIGNUM, NO_USE_BIGNUM):
Remove; all uses removed.
(extract_factors_multi): Remove, replacing with....
(print_factors_multi): New function, with signature similar to that
of new signature of print_factors_single.
(print_factors_single): Migrate checking code to caller.
(print_factors): Use GMP if it's available; don't bother asking user.
Improve accuracy of check for "large" numbers.
(long_options, main): Remove support for --bignum.
|
|
|
|
* src/factor.c: Credit Torbjörn Granlund as the author of the
arbitrary-precision factorization code.
|
|
* m4/gmp.m4: New file; adds cu_GMP, which detects GNU MP.
* configure.ac: Use cu_GMP.
* src/Makefile.am: Link factor against libgmp if available.
* src/factor.c: Use GNU MP if it is available.
(emit_factor, emit_ul_factor, factor_using_division,
factor_using_pollard_rho, extract_factors_multi,
sort_and_print_factors, free_factors): new functions
for the arbitrary-precision implementation, taken from an example
in GNU MP.
(factor_wheel): Renamed; was called factor.
(print_factors_single): Renamed; was called print_factors.
(print_factors): New function, chooses between the single- and
arbitrary-precision algorithms according to availability of GNU MP
and the length of the number to be factored.
(usage, main): New options --bignum and --no-bignum.
* coreutils.texi (factor invocation): Document new command-line
options for the MP implementation and update the performance
numbers to take into account the asymptotically faster algorithm.
* TODO: Remove item about factoring large primes (it's done).
* m4/gmp.m4: Add support for --without-gmp.
* NEWS: Mention the new feature.
|
|
* src/system.h: Include "inttostr.h".
(timetostr): New function, factored out of...
* src/date.c (show_date): Use timetostr.
* src/du.c (show_date): Likewise.
* src/ls.c (print_long_format): Likewise.
* src/pinky.c (time_string): Likewise.
* src/stat.c (human_time): Likewise.
* src/*.c: Don't include inttostr.h, since system.h does.
* src/c99-to-c89.diff: Adjust offsets.
|
|
* bootstrap.conf (gnulib_modules): Add progname.
* src/*.c (program_name): Remove declaration.
* (main): Call set_program_name rather than setting program_name.
* src/nice.c (main): Cast program_name to "(char *)".
* src/prog-fprintf.c: Include "system.h"
* src/system.h: Include "progname.h".
* maint.mk (sc_program_name): Adjust rule.
Suggestion from Eric Blake.
|
|
* src/base64.c: Likewise.
* src/basename.c: Likewise.
* src/cat.c: Likewise.
* src/chcon.c: Likewise.
* src/chgrp.c: Likewise.
* src/chmod.c: Likewise.
* src/chown.c: Likewise.
* src/chroot.c: Likewise.
* src/cksum.c: Likewise.
* src/comm.c: Likewise.
* src/cp.c: Likewise.
* src/csplit.c: Likewise.
* src/cut.c: Likewise.
* src/date.c: Likewise.
* src/dd.c: Likewise.
* src/df.c: Likewise.
* src/dircolors.c: Likewise.
* src/dirname.c: Likewise.
* src/du.c: Likewise.
* src/echo.c: Likewise.
* src/env.c: Likewise.
* src/expand.c: Likewise.
* src/expr.c: Likewise.
* src/factor.c: Likewise.
* src/fmt.c: Likewise.
* src/fold.c: Likewise.
* src/groups.c: Likewise.
* src/head.c: Likewise.
* src/hostid.c: Likewise.
* src/hostname.c: Likewise.
* src/id.c: Likewise.
* src/install.c: Likewise.
* src/join.c: Likewise.
* src/kill.c: Likewise.
* src/link.c: Likewise.
* src/ln.c: Likewise.
* src/logname.c: Likewise.
* src/ls.c: Likewise.
* src/md5sum.c: Likewise.
* src/mkdir.c: Likewise.
* src/mkfifo.c: Likewise.
* src/mknod.c: Likewise.
* src/mktemp.c: Likewise.
* src/mv.c: Likewise.
* src/nice.c: Likewise.
* src/nl.c: Likewise.
* src/nohup.c: Likewise.
* src/od.c: Likewise.
* src/paste.c: Likewise.
* src/pathchk.c: Likewise.
* src/pinky.c: Likewise.
* src/pr.c: Likewise.
* src/printenv.c: Likewise.
* src/printf.c: Likewise.
* src/ptx.c: Likewise.
* src/pwd.c: Likewise.
* src/readlink.c: Likewise.
* src/rm.c: Likewise.
* src/rmdir.c: Likewise.
* src/runcon.c: Likewise.
* src/seq.c: Likewise.
* src/setuidgid.c: Likewise.
* src/shuf.c: Likewise.
* src/sleep.c: Likewise.
* src/sort.c: Likewise.
* src/split.c: Likewise.
* src/stat.c: Likewise.
* src/stty.c: Likewise.
* src/su.c: Likewise.
* src/sum.c: Likewise.
* src/sync.c: Likewise.
* src/tac.c: Likewise.
* src/tail.c: Likewise.
* src/tee.c: Likewise.
* src/test.c: Likewise.
* src/timeout.c: Likewise.
* src/touch.c: Likewise.
* src/tr.c: Likewise.
* src/true.c: Likewise.
* src/tsort.c: Likewise.
* src/tty.c: Likewise.
* src/uname.c: Likewise.
* src/unexpand.c: Likewise.
* src/uniq.c: Likewise.
* src/unlink.c: Likewise.
* src/uptime.c: Likewise.
* src/users.c: Likewise.
* src/wc.c: Likewise.
* src/who.c: Likewise.
* src/whoami.c: Likewise.
* src/yes.c: Likewise.
|
|
|
|
g grep -E -l 'define AUTHORS "[^,]+"$'|xargs perl -pi -e \
's/(define AUTHORS) ("[^,]+")$/$1 proper_name ($2)/'
|
|
* src/Makefile.am (.sh, uninstall-local): Adjust all users of
hand-rolled GNU_PACKAGE to instead use autoconf-provided
PACKAGE_NAME.
* src/basename.c (main): Likewise.
* src/chroot.c (main): Likewise.
* src/dirname.c (main): Likewise.
* src/echo.c (main): Likewise.
* src/expr.c (main): Likewise.
* src/factor.c (main): Likewise.
* src/groups.sh (version): Likewise. Also, reflect change in
--version output due to GPLv3.
* src/hostid.c (main): Likewise.
* src/hostname.c (main): Likewise.
* src/link.c (main): Likewise.
* src/logname.c (main): Likewise.
* src/nice.c (main): Likewise.
* src/nohup.c (main): Likewise.
* src/printenv.c (main): Likewise.
* src/printf.c (main): Likewise.
* src/pwd.c (main): Likewise.
* src/setuidgid.c (main): Likewise.
* src/sleep.c (main): Likewise.
* src/system.h (case_GETOPT_VERSION_CHAR): Likewise.
* src/test.c (main): Likewise.
* src/true.c (main): Likewise.
* src/unlink.c (main): Likewise.
* src/uptime.c (main): Likewise.
* src/users.c (main): Likewise.
* src/whoami.c (main): Likewise.
* src/yes.c (main): Likewise.
* configure.ac (AC_CHECK_DECLS): No need to check strtoimax,
strtoumax, since gnulib does this.
|
|
|
|
|
|
* src/system.h (emit_bug_reporting_address): New function.
* src/base64.c: Use it rather than a literal printf.
* src/basename.c, src/cat.c, src/chgrp.c, src/chmod.c:
* src/chown.c, src/chroot.c, src/cksum.c, src/comm.c, src/cp.c:
* src/csplit.c, src/cut.c, src/date.c, src/dd.c, src/df.c:
* src/dircolors.c, src/dirname.c, src/du.c, src/echo.c, src/env.c:
* src/expand.c, src/expr.c, src/factor.c, src/fmt.c, src/fold.c:
* src/head.c, src/hostid.c, src/hostname.c, src/id.c, src/install.c:
* src/join.c, src/kill.c, src/link.c, src/ln.c, src/logname.c:
* src/ls.c, src/md5sum.c, src/mkdir.c, src/mkfifo.c, src/mknod.c:
* src/mv.c, src/nice.c, src/nl.c, src/nohup.c, src/od.c:
* src/paste.c, src/pathchk.c, src/pinky.c, src/pr.c, src/printenv.c:
* src/printf.c, src/ptx.c, src/pwd.c, src/readlink.c, src/rm.c:
* src/rmdir.c, src/seq.c, src/setuidgid.c, src/shred.c, src/shuf.c:
* src/sleep.c, src/sort.c, src/split.c, src/stat.c, src/stty.c:
* src/su.c, src/sum.c, src/sync.c, src/system.h, src/tac.c:
* src/tail.c, src/tee.c, src/test.c, src/touch.c, src/tr.c:
* src/true.c, src/tsort.c, src/tty.c, src/uname.c, src/unexpand.c:
* src/uniq.c, src/unlink.c, src/uptime.c, src/users.c, src/wc.c:
* src/who.c, src/whoami.c, src/yes.c: Likewise.
|
|
rather than hard-coding to 128. From Thomas M.Ott.
|
|
|
|
description, so that help2man doesn't mangle it.
|
|
Include "quote.h".
Rather than this: error (..., "...`%s'...", arg);
do this: error (..., "...%s...", quote (arg));
|
|
|
|
|
|
|