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.

diff --git a/symm/des-base.h b/symm/des-base.h
index 7e55e04..325af53 100644 (file)
--- a/symm/des-base.h
+++ b/symm/des-base.h
@@ -122,27 +122,39 @@ extern const uint32 des_sp[8][64];
  *
  * We can implement this efficiently using our permutation machinery.
  * Writing ~k for index bit @k@ inverted, this permutation reflects the index
- * transformation given by ~0, 2, 1, ~5, ~4, ~3.  The following sequence of
- * operations is traditional.  Essentially this is an antitranspose -- a
- * reflection about the antidiagonal -- followed by a couple of fixup stages.
+ * transformation given by ~0, 2, 1, ~5, ~4, ~3.  There's a traditional
+ * swizzle sequence for this, which we used to use, namely:
+ *
+ *                                     //  5,  4,  3,  2,  1,  0
+ *     TWIZZLE_XCPL (x, y, 2);         // ~2,  4,  3, ~5,  1,  0
+ *     SWIZZLE_XCPL2(x, y, 1, 4);      // ~2, ~1,  3, ~5, ~4,  0
+ *     SWIZZLE_XCPL2(x, y, 0, 3);      // ~2, ~1, ~0, ~5, ~4, ~3
+ *     SWIZZLE_XCPL2(x, y, 3, 4);      // ~2,  0,  1, ~5, ~4, ~3
+ *     TWIZZLE_XCPL (x, y, 4);         // ~0,  2,  1, ~5, ~4, ~3
+ *
+ * Essentially this is an antitranspose -- a reflection about the
+ * antidiagonal -- followed by a couple of fixup stages.  But the non-twizzle
+ * steps require more operations, and it's easy to find a sequence which
+ * always acts on the (current) index bit 5, moving it to where it's wanted,
+ * and inverting it if necessary, so we only need twizzles.
  */
 
-#define DES_IP(x, y) do {              /*  5,  4,  3,  2,  1,  0 */    \
-  TWIZZLE_XCPL (x, y, 2);              /* ~2,  4,  3, ~5,  1,  0 */    \
-  SWIZZLE_XCPL2(x, y, 1, 4);           /* ~2, ~1,  3, ~5, ~4,  0 */    \
-  SWIZZLE_XCPL2(x, y, 0, 3);           /* ~2, ~1, ~0, ~5, ~4, ~3 */    \
-  SWIZZLE_XCPL2(x, y, 3, 4);           /* ~2,  0,  1, ~5, ~4, ~3 */    \
-  TWIZZLE_XCPL (x, y, 4);              /* ~0,  2,  1, ~5, ~4, ~3 */    \
+#define DES_IP(x, y) do {                                              \
+  TWIZZLE_XCPL(x, y, 2);               /* ~2,  4,  3, ~5,  1,  0 */    \
+  TWIZZLE_XCPL(x, y, 4);               /* ~4,  2,  3, ~5,  1,  0 */    \
+  TWIZZLE_EXCH(x, y, 1);               /*  1,  2,  3, ~5, ~4,  0 */    \
+  TWIZZLE_EXCH(x, y, 3);               /*  3,  2,  1, ~5, ~4,  0 */    \
+  TWIZZLE_XCPL(x, y, 0);               /* ~0,  2,  1, ~5, ~4, ~3 */    \
   x = ROL32(x, 1); y = ROL32(y, 1);                                    \
 } while (0)
 
 #define DES_IPINV(x, y) do {                                           \
   x = ROR32(x, 1); y = ROR32(y, 1);    /* ~0,  2,  1, ~5, ~4, ~3 */    \
-  TWIZZLE_XCPL (x, y, 4);              /* ~2,  0,  1, ~5, ~4, ~3 */    \
-  SWIZZLE_XCPL2(x, y, 3, 4);           /* ~2, ~1, ~0, ~5, ~4, ~3 */    \
-  SWIZZLE_XCPL2(x, y, 0, 3);           /* ~2, ~1,  3, ~5, ~4,  0 */    \
-  SWIZZLE_XCPL2(x, y, 1, 4);           /* ~2,  4,  3, ~5,  1,  0 */    \
-  TWIZZLE_XCPL (x, y, 2);              /*  5,  4,  3,  2,  1,  0 */    \
+  TWIZZLE_XCPL(x, y, 0);               /*  3,  2,  1, ~5, ~4,  0 */    \
+  TWIZZLE_EXCH(x, y, 3);               /*  1,  2,  3, ~5, ~4,  0 */    \
+  TWIZZLE_EXCH(x, y, 1);               /* ~4,  2,  3, ~5,  1,  0 */    \
+  TWIZZLE_XCPL(x, y, 4);               /*  3,  2,  1, ~5, ~4,  0 */    \
+  TWIZZLE_XCPL(x, y, 2);               /*  5,  4,  3,  2,  1,  0 */    \
 } while (0)
 
 /* --- @DES_EBLK@, @DES_DBLK@ --- *

diff --git a/utils/permute.lisp b/utils/permute.lisp
index 372f5cf..a8600fb 100644 (file)
--- a/utils/permute.lisp
+++ b/utils/permute.lisp
@@ -272,9 +272,20 @@
           (:exchange-invert 1 4)       ; ~2 ~1  3 ~5 ~4  0
           (:exchange-invert 0 3)       ; ~2 ~1 ~0 ~5 ~4 ~3
           (:exchange-invert 3 4)       ; ~2  0  1 ~5 ~4 ~3
-          (:exchange-invert 4 5)))))   ; ~0  2  1 ~5 ~4 ~3
+          (:exchange-invert 4 5))))    ; ~0  2  1 ~5 ~4 ~3
+       (new-network
+       (make-permutation-network
+        64                             ;  5  4  3  2  1  0
+        '((:exchange-invert 2 5)       ; ~2  4  3 ~5  1  0
+          (:exchange-invert 4 5)       ; ~4  2  3 ~5  1  0
+          (:exchange        1 5)       ;  1  2  3 ~5 ~4  0
+          (:exchange        3 5)       ;  3  2  1 ~5 ~4  0
+          (:exchange-invert 0 5)))))   ; ~0  2  1 ~5 ~4 ~3
 
   (fresh-line)
 
   (print-permutation-network trad-network)
-  (demonstrate-permutation-network 64 trad-network fixed-ip))
+  (demonstrate-permutation-network 64 trad-network fixed-ip)
+  (terpri)
+  (print-permutation-network new-network)
+  (demonstrate-permutation-network 64 new-network fixed-ip))