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

[catacomb] / base / permute.h

diff --git a/base/permute.h b/base/permute.h
index ef8eb16..21726a4 100644 (file)
--- a/base/permute.h
+++ b/base/permute.h
@@ -112,6 +112,17 @@
  * bits within two different words.  This can be seen as a multiprecision
  * variant of the swizzle.
  *
+ * Finally, we consider general permutations.  These can be implemented using
+ * Beneš networks.  Pick some index bit number %$i$%.  By applying a swizzle
+ * with a shift by %$2^i$% to the inputs, and another to the outputs, we can
+ * reduce the problem to finding two independent permutations, one affecting
+ * bits whose index has bit %$i$% clear, and the other affecting bits whose
+ * index has bit %$i$% set.  This doesn't sound so helpful, except that (a)
+ * the smaller permutations can each be implemented in the same way, and (b)
+ * they can be performed in parallel.  Small Beneš networks can be
+ * constructed by hand, but computer assistance is useful for larger ones;
+ * there are some utilities in `utils/benes.lisp'.
+ *
  * The machinery here expects some parameters to have been defined:
  *
  *   * @regty@ should be an unsigned integer type, and