progs/perftest.c: Use from Glibc syscall numbers.

symm/gcm-arm64-pmull.S (mul192): Fix commentary.

configure.ac: Lightly modernize.

  * Use `@%:@' for hashes.
  * Delete unnecessary toothpicks in `AC_DEFINE'.
  * Replace `AC_TRY_...' with `AC_..._IFELSE'.
  * Use `LT_INIT' instead of `AM_PROG_LIBTOOL'.

base/dispatch-x86ish.S: Lift register allocation definitions.

... and use the logical names during setup.  This seems to be the
convention I've followed elsewhere and it makes some sense as
(a) establishing a target for the following setup code to aim for,
and (b) giving a visual indication of how well we're getting there.

base/dispatch-x86ish.S (dispatch_x86ish_cpuid): Add missing `#undef'.

Leaked from the local register allocation switch.

base/dispatch-x86ish.S (dispatch_x86ish_cpuid): Skip `EFLAGS_ID' dance on AMD64.

The 64-bit instruction set postdates the `cpuid' instruction.

base/dispatch-x86ish.S (dispatch_x86ish_xgetbv): Preserve `edi' on i386.

Oh, dear!  This broke the world on 32-bit x86 and I didn't notice.
Definite brown-paper-bag time.

symm/{chacha,salsa20}-{arm64,arm-neon}.S: Improve rotation code.

Apparently I was asleep when I read the architecture reference because I
missed the `sri' instruction and how it can be used to synthesize
rotations with only two instructions rather than three.

Also replace rotation by 16 with the obvious `rev32'.

symm/salsa20-arm-neon.S: Indent some reordered instructions.

To emphasize that they're not part of the nearby logic but moved to
improve pipelining.

symm/salsa20-*.S: Fix vector diagrams to be little-endian.

Missed these in the previous pass.

base/reggump.h, base/regdump-*.S: Commentary and formatting improvements.

No code change at all.

base/dispatch.c, base/dispatch.h: Add proper detection for AVX2.

No plans to use this for anything yet.

base/asm-common.h, *.S: Use consistent little-endian notation for SIMD regs.

This makes operations which involve changing one's perspective about the
SIMD processing elements make significantly more sense.  In particular,
I hope that this removes a layer of brain-twisting from the GCM code.

  * Adjust all of the register-contents diagrams so that less
    significant elements are on the right, rather than on the left.

  * Change the x86 `SHUF' macro so that the desired pieces are listed in
    decreasing significance order, so `SHUF(3, 2, 1, 0)' would be a
    no-op.

I would, of course, continue to use big-endian notation on a target
which actually used a big-endian ordering natively, but we don't
currently support any of them.

utils/permute.lisp (demonstrate-permutation-network): Optionally show offsets.

Add an option to print a table showing how far each bit has still to
move.  This can be helpful for understanding some permutations.  Others,
not so much.

utils/permute.lisp (demonstrate-permutation-network): : Print nice diagrams.

Delete the ones in the commentary again.

utils/permute.lisp (demonstrate-permutation-network): Use keyword args.

utils/permute.lisp: Add supporting diagrams for IP permutations.

I decided I didn't want to lose these, and putting them in the main code
seemed too cluttery.

symm/des.c: Replace PC1 and PC2 permutation tables with Beneš networks.

math/gfx-sqr.c: Use bithacking rather than a table for squaring.

This gives a modest performance improvement to binary-curve scalar
multiplication.

symm/des-base.h: Improve the IP permutation network.

The new network is the same number of steps as the old one, but by
exchanging bits between the two halves, we reduce the number of CPU
operations needed to perform the permutation.

This is the same network used by PuTTY, but I derived it independently.

base/permute.h, utils/permute.lisp, symm/...: Formalize bit permutations.

Add a bunch of Lisp code for messing with permutations.  Add a C header
file with macros for implementing interesting primitive permutations.
Apply these to DES and Keccak-1600 as a demonstration.

symm/gcm.c, symm/gcm-*.S, utils/gcm-ref: Replace one-bit shift with algebra.

The ARM32 and x86 instruction sets lack an instruction to reverse the
order of bits in each byte of a vector register.  Therefore, they
resolve the GCM bit-ordering nightmare by reordering the bytes and
working with reversed polynomials.  But when you multiply reversed
polynomials, the result ends up being shifted by one bit relative to the
answer you actually wanted -- and SIMD instruction sets are bad at
multiprecision bit shifts, so this involves a lot of work.

Instead, use algebra.  If the result is shifted by one bit position,
then it's been multiplied by the generator t.  We can therefore fix this
by dividing through by t.  Of course, this might not even be possible
working in general the ring of polynomials over GF(2), but we're
actually working in the GCM quotient field, and t definitely has an
inverse there.  Also, dividing by t will take time and effort -- but in
fact one of the operands is something we know ahead of time and get to
prepare in whatever way we like.  So, in particular, we could divide it
by t before we even start.

The result is that we get to delete a bunch of rather fiddly assembler
code, in favour of some fairly simple C setup (and extra compensation
work in `recover_k').

I stole this trick from PuTTY.

symm/gcm-*.S (mul256): Label the partial-product terms correctly.

Two problems in three letters:

  * the middle term was written as `d', rather than `b' as introduced in
    the previous paragraph; and

  * the three are listed in the wrong order.

symm/gcm-arm-crypto.S (mul96): Fill in the clobbered-registers list.

utils/gcm-ref: Pull `poly64_mul' and `poly64_redc' out of `poly64_common'.

Basically a refactoring, but there's some foreshadowing too -- most
notably the UWHAT and VWHAT arguments.

utils/gcm-ref (present_gf_vmullp64): Add `v' prefix to match front end.

The inconsistency annoyed me.

utils/gcm-ref (poly64_mul_simple): Strip padding off the product.

Rather than leaving this job to the caller.  I'm going to decree that
it's the presentation-function's job to show padding in the right place,
rather than the multiplier's job to retain it.  This means that we need
to keep track of the padding properly, but it's pretty easy.

The most important effect is that there's no longer a rather strange
bodge in `poly64_common' to strip the padding in one particular case
because `poly64_mul_simple' has done it properly in every case.

utils/gcm-ref: Fix embarrassing mistakes in comments.

Imagine my head hanging in shame.

utils/gcm-ref (present_gf_pmull): Round width up to a multiple of 64 bits.

Otherwise the later loop, which pulls off 64-bit chunks, gets badly
confused.

Now `gcm-ref' can actually calculate all of the things properly.

for p in pclmul vmullp64 pmull; do
  while read u v; do utils/gcm-ref $p $u $v || break 2; done <<EOF
cde4bef260d7bcda 163547d348b75511
cde4bef260d7bcda163547d3 48b7551195e77022907dd1df
cde4bef260d7bcda163547d348b75511 95e77022907dd1dff7dac5c9941d26d0
cde4bef260d7bcda163547d348b7551195e77022907dd1df f7dac5c9941d26d0c6eb14ad568f86edd1dc9268eeee5332
cde4bef260d7bcda163547d348b7551195e77022907dd1dff7dac5c9941d26d0 c6eb14ad568f86edd1dc9268eeee533285a6ed810c9b689daaa9060d2d4b6003
EOF
done

I wonder what this means about the changes coming up...

utils/gcm-ref (poly64_mul_simple): Pad v based on the length of v.

Not the already-padded length of u, which doesn't make any sense.  Now
we actually calculate 96-bit products correctly using the `poly64'
multiplication machinery.

utils/gcm-ref (demo_table_l): Use an end-swap function that exists.

Now `table-l' actually runs at all.

symm/gcm-*.S: Fix the `ṽ' encodings.

For some reason, Emacs got confused about how it wanted to display
that.  I think I did something crazy involving entering combining
characters by hand; this time, I just typed the thing on the keyboard
using the compose key and it worked.

rand/rand.c: Fix multiplication and division formatting.

rand/rand.c: Rearrange some comparisons to avoid arithmetic overflow.

math/f25519.h: Fix argument name in commentary.

Merge branch '2.5.x' into HEAD

* 2.5.x:
  rand/rand.c (rand_gate): Evolve r->ibits in a more sensible manner.
  rand/rand.c (rand_getgood): Stretch the output buffer if necessary.

Merge branch '2.4.x' into 2.5.x

* 2.4.x:
  rand/rand.c (rand_gate): Evolve r->ibits in a more sensible manner.
  rand/rand.c (rand_getgood): Stretch the output buffer if necessary.

rand/rand.c (rand_gate): Evolve r->ibits in a more sensible manner.

It's not really clear what this code was trying to do.  Write i and o
for the initial values of r->ibits and r->obits, respectively, i' and 'o
for their respective final values, and O for RAND_OBITS.  In the case
that i + o <= O, we update i' = 0 and o' = i + o, maintaining the
invariant that i' + o' = i + o.  But if i + o > O, then we set o' = O and
i' = (i + o) - i = o, which seems nonsensical.  In particular, in the
case that i = 1 and o = O, it apparently magics O - 1 bits of entropy
from nowhere.

Modify the code so that it at least maintains the sum of the entropy
counters in either branch.  I'm not sure this is actually correct, but
it seems like a defensible position.

rand/rand.c (rand_getgood): Stretch the output buffer if necessary.

It's possible to have `r->o == RAND_BUFSZ' in the main loop, while
`r->obits' is larger than the requested size.  The following program
contrives this situation, though it can (and does) happen organically.

#include <stdio.h>
#include <stdlib.h>

#include "noise.h"
#include "rand.h"

int main(void)
{
  rand_pool pool;
  unsigned char buf[64];
  size_t n;

  rand_init(&pool);
  rand_noisesrc(&pool, &noise_source);
  rand_seed(&pool, 64);

  while (pool.obits < RAND_OBITS) rand_seed(&pool, RAND_IBITS);
  while (pool.o < RAND_BUFSZ) {
    n = RAND_BUFSZ - pool.o; if (n > sizeof(buf)) n = sizeof(buf);
    rand_getgood(&pool, buf, n);
  }
  rand_getgood(&pool, buf, 4);
  return (0);
}

When this happens, `rand_getgood' gets stuck in an infinite loop,
trimming the chunk size to zero because the output buffer is exhausted,
but not refilling it because there's still notional entropy remaining.
Detect this situation and stretch the output buffer when there's nothing
left, as in `rand_get'.

base/dispatch.c: Check atomic copy of the probes flags, not the original.

Rather defeats the point otherwise.

base/asm-common.h: Hoist executable-stack stuff into the ELF block.

base/asm-common.h: Move ELF section-type business into the main ELF block.

base/asm-common.h: Sink the `PIC' stuff a little.

base/asm-common.h: Farm out the section selection macros.

Leave them to the end because nobody's relying on them earlier.

base/asm-common.h: Add a macro for setting the types of data symbols.

base/asm-common.c: Add a paragraph comments and squash some blank lines.

base/asm-common.h (FORCE_EXECUTABLE_STACK): Rename from `WANT...'.

Makes it sound less like a sensible thing to want.

pub/x25519.h, pub/x448.h: Add descriptions of the curves.

math/f25519.c (f25519_load): Improve the tabular layout.

math/f25519.c: Add missing space in commant.

symm/poly1305.c: Remove spaces around `&'.

symm/chacha-x86ish-sse2.S: Fix mathematical errors in commentary.

The commentary proving the correctness for the general solution of
`gfreduce_quadsolve' was wrong in a number of details that somehow
managed to cancel out.  The claim is correct, and now the proof has been
fixed, with somewhat expanded calculations making the tricks easier to
notice.

math/mpx-mul4-arm64-simd.S: Fix case of argument `I' in commentary.

math/mpx-mul4-arm64-simd.S: Fix unfortunate line-breaks in commentary.

math/group-dstr.c: Delete some spurious blank lines.

symm/* (aead): Implement the `szok' methods.

I think this was intended to be part of the initial AEAD work, but got
forgotten.  Oh, well.

symm/ccm.c: Fix the title of the comment for `ccm_check'.

symm/*.S: Delete stray dots in some banner comments.

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.

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.