From: Mark Wooding <mdw@distorted.org.uk>
Date: Thu, 1 Feb 2024 14:29:06 +0000 (+0000)
Subject: symm/des-base.h: Improve the IP permutation network.
X-Git-Url: https://git.distorted.org.uk/~mdw/catacomb/commitdiff_plain/48af823d9b5218ce32d7590b786d3b1cd089b68c

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 7e55e044..325af534 100644
--- 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 372f5cfc..a8600fbe 100644
--- 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))