prime generation: Deploy the new Baillie--PSW testers.

math/pgen.c, math/pgen-simul.c: Add Baillie--PSW testers.

Add plain and simultaneous Baillie--PSW testers.

math/pgen.c: Have `steps' and `tests' count down as documented.

This was how they worked originally, but they were changed a long time
ago to count up from zero instead.  This makes it impossible for a
stepper or tester function to know in advance how many times it will be
invoked, which turns out to be important for a forthcoming change.

The reason it was changed wasn't explained in the commit
(283b9af095a5b24ae71b49a6d2dcbdcdaae47c40) that made it, but I deduce
that it was so that `pgen_test' could identify the first test round and
use the somewhat faster approach of using (the residue whose Montgomery
REDC representative is) 2, rather than a random witness.  That change
has now been undone, so we can restore the documented behaviour.

math/pgen.c (pgen_test): Use random witnesses only.

This means that we no longer need to distinguish the first round of a
Rabin--Miller test loop, which in turn will allow a more useful change
in the future.

pub/keycheck-mp.c (keycheck_prime): Use `pgen_primep' to do the legwork.

This will now use Baillie--PSW rather than Rabin--Miller, giving more
useful, faster results.

symm/t/chacha: Add tests for crossing the 2^32 blocks boundary.

symm/*-arm*.S: Fix some section titles.

I'm sure I've fixed this one before.

math/mp-sqrt.c, math/pgen-granfrob.c: Publish `squarep' function.

It's not super-useful, but it fits thematically with
`mp_perfect_power_p', and publishing it is better than not.

base/asm-common.h: Add register-name conversions for ARM64 registers.

Not using these yet, but maybe some time.

symm/des.c: Introduce a function to fix or check key parity.

I found myself wanting this (though Python) today, and realised that not
only was it missing from the Python bindings, it wasn't in the library
at all.  So here it is.  The Python bindings will come later.

base/ct.[ch]: Set the return type of `ct_pick' correctly.

This is, technically speaking, an API break.  But I don't think anything
actually cares, this is an improvement, and the ABI is unchanged on
every platform I can think of.

build: Switch to using the new subtree version of CFD.

Add '.ext/cfd/' from commit '09d274abdda494424271ffff4f83ee5a58cb262e'

git-subtree-dir: .ext/cfd
git-subtree-mainline: 01386fc8db473eac03c5aaaa53f3790cde319a76
git-subtree-split: 09d274abdda494424271ffff4f83ee5a58cb262e

.gitignores: Organize and clean up.

Divide into sections and add headings; add leading `/' to patterns which
are only expected to match in the same directory as the `.gitignore'
file; and add trailing `/' to patterns which should match directories.

Merge branch '2.6.x'

* 2.6.x:
  progs/key.c, progs/key.1: Fix option discrepancies.

progs/key.c, progs/key.1: Fix option discrepancies.

The `-E' option wasn't mentioned in the built-in help or the manpage
synopsis; the `--retag' long option wasn't actually recognized.

.gitignore: Delete now that we don't need this thing any more.

symm/*-def.h: Fix repeated garbled commentary by adding the missing word.

This is a bit embarrassing.  I should have read this text more carefully
before copying it everywhere.

symm/eax-def.h: Fix bungled `\' alignment.

math/mp-nthrt.c: Add commentary for `mp_perfect_power_p'.

This is quite simple, really, but it doesn't hurt to explain what's
going on.

math/mp-nthrt.c: Fix garbled commentary.

math/mp-nthrt.c: Delete redundant check for termination.

This case is already handled above.

base/asm-common.h, ...: Add missing `cmov' instruction (and `.CC' variants).

This instruction conditionally moves a value from one register to
another, otherwise leaving the destination unchanged:

cmov RD, RN, CC == csel RD, RN, RD, CC

Also define `cmov.CC' for all condition codes CC.

Use this to slightly improve `rijndael_setup_arm64_crypto'.

base/asm-common.h: Improve conditional instruction notation.

ARM64 conditional instructions -- `ccmp', `csel', etc. -- are
inexplicably notated differently from conditional branches.  The latter
are rather pleasantly written as `b.CC TARGET', while the former are,
disappointingly, `csel RD, RN, RM, CC' and similar, with the condition
tacked on the end.

Fix this by introducing aliases `csel.CC' and suchlike for all of the
conditional instructions.

base/regdump.c: Print matching condition codes along with CPU flags.

base/regdump-arm64.S, base/regdump.h: Save NZCV and x8--x15 early.

Alas, the processor flags /and/ at least x14 and x15 are clobbered by
the PLT on-demand linkage machinery, so we must save them in the macro
before calling out to the library.  To be safe, preserve all of the
non-argument call-clobbered registers.

base/regdump-arm.S, base/regdump.h: Save CPSR before `regdump_gpsave'.

Alas, the processor flags are clobbered by the PLT on-demand linkage
machinery, so we must save them in the macro before calling out to the
library.

m4/mdw-uint-bits.m4: Delete stray `dnl' from the comment header.

debian/catacomb2: Add missing symbol version entries.

debian/changelog: Prepare for next minor version.

build/autotest.am: Fix formatting of list initialization assignments.

m4/: Reformat to match current m4/shell style.

m4/mdw-dir-texmf.m4: Nest and indent `mdw_DEFINE_PATHS' properly.

Not sure why this enclosed the `AC_MSG_RESULT' before.  Oh, well.

m4/mdw-dir-texmf.m4: Pull `texmf' path guesswork out of `AC_ARG_WITH'.

Unfortunate tangling of responsibilities.  Instead, leave a flag so that
top-level code can decide to do the guesswork.

m4/mdw-manext.m4: Don't hardcode the manpage extension to `mLib'.

Obviously this isn't used as widely as it ought to be!

m4/mdw-dir-texmf.m4, m4/mdw-manext.m4: Use `AS_HELP_STRING'.

I think this didn't exist when I wrote these macros.

m4/mdw-define-paths.m4: Replace `$(eval echo ...)' nonsense.

No idea why I didn't do it this way before.

m4/mdw-define-paths.m4: Use `$(...)' for command substitution.

It nests better than the old-fashioned ``...`' syntax.  Which is good,
because it's nested here.

m4/mdw-auto-version.m4: Don't try appending suffixes any more.

The old `auto-version.in' has gone for good.

m4/mdw-auto-version.m4: Delete the bizarre pre-definition.

Not really sure what this was for, but this hack has always been there
in some form since the macro was introduced.  It doesn't seem necessary
now, certainly.

m4/: Reformat the Autoconf macros in `aclocal' style.

Add a `LICENSE' section, and `# serial' markers.

aclocal.glob, m4/: Split the monster into separate `aclocal'-ish files.

Now these can be linked into a project's `m4/' directory in the usual
way.  Much better!

This has just redistributed the existing content: none of the code is
changed.

build/ scripts: Remove the version-number machinery.

Since these things are no longer installed anywhere outside of a
revision-controlled working tree, they don't need to know their version
numbers any more.

Scatter the useful files into subdirectories by theme.

This is maybe a little random, but better ideas seem thin on the ground.

  * `build/' is for build tools: scripts and build-tool fragments which
    are handy for building projects.

  * `doc/' is for documentation, and things which help with producing
    documentation, such as styles.

  * `licence/' contains licence documents.

  * `m4/' will be for Autoconf machinery, but it's not there yet:
    splitting up `aclocal.glob' will be a job for another commit.

  * `src/' contains source code which is shared among many projects.

This commit just moves the files about.  Some of the scripts have had
their `.in' suffix stripped because they should no longer be hacked by
Autoconf or anything similar, but none of the content is modified.

Delete everything only needed for standalone building.

This is the start of an effort to change the way CFD is used by
projects.  Rather than being installed on developer systems as a thing
in its own right, it should be tucked away in a project, using `git
subtree' or similar.

Please don't use `git submodule' for this!

auto-version.in: Fix typo in commentary.

math/mp-nthrt.c: Implement nth-root, and perfect-power detection.

symm/square-mktab.c, etc.: Provide enough round constants for short keys.

It turns out that one needs 35 round constants to correctly schedule a
32-bit key, not just 32.  It further turns out that Clang orders the
various constant tables differently from GCC, which leads to the two
implementations producing different, but both incorrect, answers.

This is all very embarrassing.  Fortunately, nobody will use a 32-bit
key and expect anything useful to come of it, and no larger key size is
affected.  I think the main effect is that a bunch of the mode test
vectors needed changing.

math/mpx-mul4-*.S: Use more portable type syntax for ambiguous instructions.

Specifically, replace `adcd MEM, 0' by `adc dword ptr MEM, 0'.  This
removes one reason why Clang's defective assembler won't work, but there
are others.

This is not part of a concerted effort to improve Clang support.
Honestly, as far as I'm concerned, `CCASFLAGS=-fno-integrated-as
-Wno-unicode' is sufficient support for building Catacomb using
Clang.  (That said, I don't actively object to supporting Clang: it's
just not something I want to put much effort into.  I'm happy to accept
tasteful patches which improve Clang support.)  But in retrospect, using
`adcd' here was kind of bletcherous in its own right, and it should be
fixed.

Release 2.6.2.

base/dispatch.c: Fix feature probe for AESNI.

Oh, this is embarrassing.  2.6.0 and 2.6.1 are broken on pre-AESNI
hardware.

progs/mkphrase.c: Fix trailing spaces in usage message.

Release 2.6.1.

rand/rand-x86ish.S: Establish GOT pointer before making an i386 PLT call.

Otherwise you just get a segfault.

Release 2.6.0.

base/dispatch.c, rand/rand.c, and asm: Support `rdseed' for quick noise.

Prefer the `rdseed' instruction over `rdrand' for quick randomness, if
it's available.

rand/rand-x86ish.S: Hoist argument register allocation outside.

This will soon be shared with another entry point for `rdseed'.

rand/rand-x86ish.S: Add missing `undef' of the `COUNT' register.

base/dispatch.c, base/dispatch-x86ish.S: Add opcode to `rdrand_works_p'.

I want to add support foer the `rdseed' instruction, but this might be
broken on AMD64 like `rdrand'.  Rather than duplicate this logic, add an
opcode argument to the checking functions.

base/dispatch.c: Make `cpuid_feature_p' more easily extensible.

It turns out that Intel scatter feature flags throughout the various
CPUID leaves.  Change the interface for checking these flags so that we
can cover more ground without too much extra work.

  * Firstly, rename the function to `cpuid_feature_p' because it's only
    really useful for checking one feature at a time.

  * Secondly, make the first argument be a code indicating which
    particular `cpuid' output we're interested in; the second is still a
    mask used to check for the bit we're interested in.

Obviously this involves changing all of the callers too.

rand/dsarand.c: Return the old number of passes from `DSARAND_PASSES'.

Also, don't update if the input operand is zero.

*.c: Check for ARM64 SIMD before using the accelerated code.

I don't expect ARM64 processors to omit the SIMD instructions, but it's
convenient to have a way to inhibit the accelerated code (e.g., for
performance measurement).

base/dispatch.c: Reformat an ugly line-break.

math/mpx-mul4-{arm-neon,arm64-simd}.S, etc.: Add ARM versions of `mul4'.

With this, I think we (finally) have parity across the various premier
target platforms.

base/regdump.[ch]: Add a feature for printing plain messages.

Introduce a `REGSRC_NONE' which just prints the message, and add a `msg'
macro which invokes this.

math/mpmont.c: Fix comment title for `mulcore'.

math/mpx-mul4-*.S: Output expanded Montgomery factor in a sensible order.

The current order is (y'_0, y'_1; y''_0, y''_1), (y'_2, y'_3; y''_2,
y''_3), but while this makes sense in the context of SSE2, it's not
really very satisfactory as a common currency.  (In particular, if we
want to resolve the expanded factor into a value then we'll have to do
it by steam because the limb placements are irregular.)

Instead, fix the ordering in the test stubs so that the pieces come out
as (y'_0, y''_0; y'_1, y''_1), (y'_2, y''_2; y'_3, y''_3), which is
generally much better to work with outside of SSE2.

Of course, this only affects testing, not the actual code, so
performance is unchanged.

math/mpx-mul4-amd64-sse2.S: Improve the end-of-loop condition testing.

Previously, I waited until `rdi' was set up for the next iteration
before comparing it against the limit.  But in fact, `DV' already has
the right value, so we can compare earlier.

math/mpx-mul4-amd64-sse2.S: Save a spill by better register allocation.

The Windows code doesn't need to spill r12, because we don't need the
`mi' register after we've loaded and expanded the Montgomery factor.
This doesn't save any stack space because we need 16-byte alignment, but
it does avoid saving and restoring the register.

math/mpx-mul4-*-sse2.S (mpxmont_redc4): Fix end-of-outer-loop commentary.

  * The carry loop is wrong if the destination is an exact multiple of
    four limbs.  Fortunately, it isn't.

  * The initial pass feeds into the main loop unconditionally, unlike
    `mpxmont_mul4_...' (from which I think the commentary was
    uncritically copied), so being at the end of it doesn't tell you
    anything about whether to start another.  And, indeed, we do indeed
    check the loop-end condition.

math/mpx-mul4-*-sse2.S: Remove an unhelpful comment.

It's not actually wrong, but it's misleading because we don't actually
care that the flags are preserved at this point, because the next
instruction clobbers them anyway.  I think this was cut-and-paste
lossage from the earlier code which relies on `mov' preserving the carry
flag.

math/mpx-mul4-*.S: Fix up some of the commentary.

  * Fix bogus formatting.

  * Fill in the `...' in the AMD64 version.

  * Explain the common notation and register allocation conventions.

base/asm-common.h: Decorate pseudoregister `nil' as `nil'.

This allows `nil' to be passed through macros which want to apply
decoration transforms to their register arguments through to other
macros which treat `nil' as a special marker that a register is absent
or otherwise not to be used.

math/t/mpx-mul4: Fix comment markers.

math/: Delete some unnecessary blank lines.

Initialize the register dumping machinery while testing assembler code.

symm/blkc.h: Add a hook for cipher-specific initialization.

You'll see what this is for soon.

math/mpx-mul4-test.c: Compare and print test outputs by value.

Different implementations may find it useful to calculate redundant-
representation outputs in different ways.  Compare these by value rather
than by raw representation.

x86ish *.S: Use `stalloc' consistently to allocate space on the stack.

Also, prefer aligning afterwards, except where that won't work.

base/dispatch-x86ish.S: Capture the `xmm0' address in a register.

This saves 16 bytes overall, and makes for slightly more readable code.

base/asm-common.h (x86), and knock-on: Add macros for full-size regs.

These registers get used a lot as pointers, so it's useful to be able to
refer to them as full-width registers more conveniently than `R_sp(r)'.
Introduce (C preprocessor) macros `AX', ..., for this purpose, and use
them extensively.

(Delete the existing `SI' and `DI' macros from `rijndael-x86ish-aesni.S'
which had the same purpose.)

base/regdump.h: Pass cooked register index to `REGDEF_GPX86_COMMON'.

I want to define `BP' and `SP' as macros, but they'll expand in the
calls to `REGDEF_GPX86_COMMON', which will break things.  They don't
expand directly in the body of `REGDEF_GPX86_XP' because `##' inhibits
this.  Alas, this means we have to do this token-gluing in the interface
macros rather than the common core.

symm/poly1305.c, etc.: Convert the Monte-Carlo tests to incremental form.

Similarly to the way 1e4c26653e52aa4c4b06e345617135a6ff271ab5 modified
the X25519 and X448 tests, arrange that each Monte-Carlo test vector
continues from where the previous one left off.  This is considerably
trickier to pull off because there's so much more state to maintain in
these tests, and changes to the processing code was necessary to make it
work.

Again, as in 1e4c2665..., move the very slow high-iteration-count tests
into a separate file, and arrange for it to be distributed.

Note that the outputs are unchanged by all of this.

symm/poly1305.c: Keep the working buffers in `dstr' buffers.

This way, they can be printed easily using the testrig type machinery.

symm/poly1305.c: Use explicit sizes in the Monte-Carlo test.

The indirect `sizeof' expressions weren't always of the right variable,
and I'm going to replace the vectors with pointers soon.

progs/key.c: Don't print secret parts of keys at verbosity 3.

Print them at level 4.  Push printing of locked portions to level 5.

progs/key.c: Use `HASH' rather than `HASHALG' to denote a hash-function name.

I noticed that the synopses were inconsistent between `fingerprint' and
`verify'.  Resolve this in favour of the shorter `HASH', despite the
1--3 minority.  (Note that the manual already uses `hash' consistently.)

key/key-misc.c (key_bytag): Accept `tag:', `id:' and `type:' prefixes.

Further to the fix 079836cc4d21b355c8b58a4624ef85df0ac6c21a, allow the
user to attach a disambiguating prefix to the label.  Using the colon is
safe here, since it's obviously not acceptable in a hex id, and
`key_chkident' rejects colons in tag and type strings.

Deploy the new <ctype.h> and `foocmp' macros from mLib.

symm/t/poly1305: Spell Dan Bernstein's name correctly.

Sorry, Dan.

pub/dh-kcdsa.c: Retry or fail if we don't get the target sizes.

Following the usual convention, we retry unless the caller gave us a
bounded number of steps, and otherwise fail.

I think failure is fairly unlikely now.  To find an N-bit prime, we
expect to take about 4 N steps (see analysis in `math/strongprime.c').
But we're trying to find two primes simultaneously, one of N bits, and
one of M bits, so this will take about 16 M N steps in total.  We start
with v < 2^{N-M-1}, and choose 2^{M-1} <= q_0 < 2^M such that 2^{N-1} <
p_0 = 2 q_0 v + 1 < 2^N (nearly true).  We'll fail if 2^M - q_0 < 16 M N,
which seems unlikely, or if 2^N - p_0 < 32 M N v, i.e., 2^M - p_0/(2 v) <
16 M N, which is basically the same condition.

pub/dh-kcdsa.c: Choose the starting point for the right result size.

And try again until it's actually likely to work.

pub/dh-kcdsa.c: Choose the cofactor size correctly.

Considering that we're going to have to multiply in a factor of 2 at
some point.

pub/dh-kcdsa.c: Make the cleanup flow less crazy.

I'm pretty sure I've fixed bugs in here.

pub/dh-kcdsa.c: Fix commentary blunder.

utils/advmodes, utils/gcm-ref: Make conversions from `int' to `GF' explicit.

This anticipates a Catacomb/Python change which breaks implicit
conversions to `GF'.

symm/hmac-def.h: Base key sizes on the hash size, not state size.

Back in c850c0da81ad9f72315f8e6e26bdfbd98daf9d89 (`Support HMAC mode for
hash functions which need to store more state than the hash output
size'), there was only a single key-size specification shared between
HMAC and NMAC.  This nearly makes sense, because an NMAC key is a /pair/
of hash states, for the outer and inner hash applications, but the key
size at this time was only the size of /single/ state.  At this time,
only HMAC had a `gcmac' definition, so the key size had to be right for
HMAC, which may explain this, but it seems rather unconvincing.

Later, 2a62e96dc602cf6ec0e5a489b18262ae6abb29be (`Provide correct key
sizes for NMAC, HMAC and SSLMAC') splits this single key-size
specification into three, and adds a `gcmac' definition for the NMAC
variant.  The new key-size specification for NMAC correctly reports
double the state size, and uses `KSZ_SET' rather than `KSZ_ANY'.  I
think the other two should have been based on the hash size at this
point, but weren't: I suspect that I just propagated the previous
mistake without thinking about it very hard.

Even later, c148759dc94794db3faa3ed556583b65d40ae799 (`symm/hmac-def.h:
Report key sizes as 16-bit quantities') changes the key-size
specifications to use the new 16-bit format, but shies away from fixing
the HMAC and SSLMAC key sizes.

I'm now going to bite this bullet and declare that the HMAC and SSLMAC
key sizes should be based on the hash size.  This changes the default
key sizes for: MD2, SHA224, SHA384, SHA512/224, SHA512/256, SHA3 (all
variants), and Whirlpool256.  I think it's probably a mistake to have
used any of these hash functions with HMAC: MD2 is slow and weak; the
SHA2 variants are all worse than truncating SHA256 or SHA512; similarly,
using Whirlpool256 rather than truncating plain Whirlpool is
bizarre (and Whirlpool is slow and rarely used anyway); and SHA3 is just
a terrible fit for HMAC, and you should be using KMAC instead.

This will break interoperability in `catcrypt' if HMAC based on any of
the above hash functions is used as the `mac'.  TrIPE (sensibly) doesn't
use the default key size, so isn't affected by this change.

math/mpgen, symm/multigen: Fix the various build scripts for Python 3.

  * Put parentheses around `print' arguments.

  * Write `raise EXC(VALUE)' rather than `raise EXC, VALUE' to raise
    exceptions.

  * Cope with `xrange' being renamed to `range' in Python 3.

  * Cope with `long' not being a type name in Python 3.

  * Cope with `execfile' not being available in Python 3.

  * Cope with function-object attribute names being renamed in Python 3.

  * Cope with `StringIO' being in `io' rather than `cStringIO' in Python
    3, and with `StringIO.reset' not being available any more.

  * Cope with `itertools.izip' not being available in Python 3.

  * Cope with `OBJ.next' not being available in Python 3.

  * Use an unpleasant hack to inject metaclasses, because the official
    syntax is so different between the two versions.

symm/multigen (SequenceTemplate): Don't try to pass `seq' initarg.

I have no idea how this ever worked.  Certainly Python 3 complains, but
Python 2 should have done too.

key/key-io.c: Add low-level `key_mergeline' and `key_extractline' functions.

Python 3 doesn't use C `stdio' streams.  In order to integrate properly,
we need to provide some other way to do I/O of key material.  Introduce
new functions which work in terms of lines in the keyring, which a
Python wrapper can transfer between us and a Python file.