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 7e55e0448149c1427caf770765fd7d20cff2cb31..325af534fe8f3832d4ef302a2eab9bcebe9c5a52 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 372f5cfce092de6ed8ea775e0c60842bfcd5242b..a8600fbe43beaa1f61ca297f2fbf7b42a493a9eb 100644 (file)
--- a/utils/permute.lisp
+++ b/utils/permute.lisp
@@ -272,9 +272,20 @@ (let* ((ip #(58 50 42 34 26 18 10  2
           (: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))