Faster matrices

1 files changed, 100 insertions, 103 deletions

diff --git a/pypride.py b/pypride.py
index 82788d4..4fa09c9 100644
--- a/pypride.py
+++ b/pypride.py
@@ -128,118 +128,115 @@ PBox_inv = [PBox.index(x) for x in xrange(64)]
 
 # Matrices for permutation in the L layer
 L0_inv = L0 = [
-      [0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0],
-      [0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0],
-      [0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0],
-      [0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1],
-      [1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0],
-      [0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0],
-      [0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0],
-      [0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1],
-      [1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0],
-      [0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0],
-      [0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0],
-      [0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1],
-      [1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0],
-      [0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0],
-      [0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0],
-      [0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0]]
-L1 = [[1,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0],
-      [0,1,1,0,0,0,0,0,0,0,0,0,1,0,0,0],
-      [0,0,1,1,0,0,0,0,0,0,0,0,0,1,0,0],
-      [0,0,0,1,1,0,0,0,0,0,0,0,0,0,1,0],
-      [0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,1],
-      [0,0,0,0,0,1,1,0,1,0,0,0,0,0,0,0],
-      [0,0,0,0,0,0,1,1,0,1,0,0,0,0,0,0],
-      [1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0],
-      [1,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0],
-      [0,1,0,0,0,0,0,0,0,0,0,0,1,1,0,0],
-      [0,0,1,0,0,0,0,0,0,0,0,0,0,1,1,0],
-      [0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,1],
-      [0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,1],
-      [0,0,0,0,0,1,0,0,1,1,0,0,0,0,0,0],
-      [0,0,0,0,0,0,1,0,0,1,1,0,0,0,0,0],
-      [0,0,0,0,0,0,0,1,0,0,1,1,0,0,0,0]]
+    0b0000100010001000,
+    0b0000010001000100,
+    0b0000001000100010,
+    0b0000000100010001,
+    0b1000000010001000,
+    0b0100000001000100,
+    0b0010000000100010,
+    0b0001000000010001,
+    0b1000100000001000,
+    0b0100010000000100,
+    0b0010001000000010,
+    0b0001000100000001,
+    0b1000100010000000,
+    0b0100010001000000,
+    0b0010001000100000,
+    0b0001000100010000]
+L1 = [
+    0b1100000000010000,
+    0b0110000000001000,
+    0b0011000000000100,
+    0b0001100000000010,
+    0b0000110000000001,
+    0b0000011010000000,
+    0b0000001101000000,
+    0b1000000100100000,
+    0b1000000000011000,
+    0b0100000000001100,
+    0b0010000000000110,
+    0b0001000000000011,
+    0b0000100010000001,
+    0b0000010011000000,
+    0b0000001001100000,
+    0b0000000100110000]
 L1_inv = [
-      [0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0],
-      [1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1],
-      [1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0],
-      [0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0],
-      [0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0],
-      [0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0],
-      [0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0],
-      [0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0],
-      [0,0,0,1,0,0,0,0,0,0,0,1,1,0,0,0],
-      [0,0,0,0,1,0,0,0,0,0,0,0,1,1,0,0],
-      [0,0,0,0,0,1,0,0,0,0,0,0,0,1,1,0],
-      [0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,1],
-      [0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1],
-      [1,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0],
-      [0,1,0,0,0,0,0,0,0,1,1,0,0,0,0,0],
-      [0,0,1,0,0,0,0,0,0,0,1,1,0,0,0,0]]
-L2 = [[0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,1],
-      [0,0,0,0,0,1,1,0,1,0,0,0,0,0,0,0],
-      [0,0,0,0,0,0,1,1,0,1,0,0,0,0,0,0],
-      [1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0],
-      [1,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0],
-      [0,1,1,0,0,0,0,0,0,0,0,0,1,0,0,0],
-      [0,0,1,1,0,0,0,0,0,0,0,0,0,1,0,0],
-      [0,0,0,1,1,0,0,0,0,0,0,0,0,0,1,0],
-      [0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,1],
-      [0,0,0,0,0,1,0,0,1,1,0,0,0,0,0,0],
-      [0,0,0,0,0,0,1,0,0,1,1,0,0,0,0,0],
-      [0,0,0,0,0,0,0,1,0,0,1,1,0,0,0,0],
-      [1,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0],
-      [0,1,0,0,0,0,0,0,0,0,0,0,1,1,0,0],
-      [0,0,1,0,0,0,0,0,0,0,0,0,0,1,1,0],
-      [0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,1]]
+    0b0000001100000010,
+    0b1000000100000001,
+    0b1100000010000000,
+    0b0110000001000000,
+    0b0011000000100000,
+    0b0001100000010000,
+    0b0000110000001000,
+    0b0000011000000100,
+    0b0001000000011000,
+    0b0000100000001100,
+    0b0000010000000110,
+    0b0000001000000011,
+    0b0000000110000001,
+    0b1000000011000000,
+    0b0100000001100000,
+    0b0010000000110000]
+L2 = [
+    0b0000110000000001,
+    0b0000011010000000,
+    0b0000001101000000,
+    0b1000000100100000,
+    0b1100000000010000,
+    0b0110000000001000,
+    0b0011000000000100,
+    0b0001100000000010,
+    0b0000100010000001,
+    0b0000010011000000,
+    0b0000001001100000,
+    0b0000000100110000,
+    0b1000000000011000,
+    0b0100000000001100,
+    0b0010000000000110,
+    0b0001000000000011]
 L2_inv = [
-      [0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0],
-      [0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0],
-      [0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0],
-      [0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0],
-      [0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0],
-      [1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1],
-      [1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0],
-      [0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0],
-      [0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1],
-      [1,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0],
-      [0,1,0,0,0,0,0,0,0,1,1,0,0,0,0,0],
-      [0,0,1,0,0,0,0,0,0,0,1,1,0,0,0,0],
-      [0,0,0,1,0,0,0,0,0,0,0,1,1,0,0,0],
-      [0,0,0,0,1,0,0,0,0,0,0,0,1,1,0,0],
-      [0,0,0,0,0,1,0,0,0,0,0,0,0,1,1,0],
-      [0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,1]]
+    0b0011000000100000,
+    0b0001100000010000,
+    0b0000110000001000,
+    0b0000011000000100,
+    0b0000001100000010,
+    0b1000000100000001,
+    0b1100000010000000,
+    0b0110000001000000,
+    0b0000000110000001,
+    0b1000000011000000,
+    0b0100000001100000,
+    0b0010000000110000,
+    0b0001000000011000,
+    0b0000100000001100,
+    0b0000010000000110,
+    0b0000001000000011]
 L3_inv = L3 = [
-      [1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0],
-      [0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0],
-      [0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0],
-      [0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1],
-      [1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0],
-      [0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0],
-      [0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0],
-      [0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0],
-      [0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0],
-      [0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0],
-      [0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0],
-      [0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1],
-      [1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0],
-      [0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0],
-      [0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0],
-      [0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1]]
-
-def mapXor(xs):
-    """Xor elements of a list together"""
-    return reduce(lambda a, b: a^b, xs, 0)
+    0b1000100000001000,
+    0b0100010000000100,
+    0b0010001000000010,
+    0b0001000100000001,
+    0b1000100010000000,
+    0b0100010001000000,
+    0b0010001000100000,
+    0b0001000100010000,
+    0b0000100010001000,
+    0b0000010001000100,
+    0b0000001000100010,
+    0b0000000100010001,
+    0b1000000010001000,
+    0b0100000001000100,
+    0b0010000000100010,
+    0b0001000000010001]
 
 def matrixMultiply(matrix, input):
     """Multiply a vector with a binary matrix
 
-    Input:  matrix as [[Int]];
+    Input:  matrix as [Int], where the rows are integers;
             input as Int
     Output: Int"""
-
-    mult = [mapXor([1 for i,c in enumerate(r) if c == 1 and input & (1 << (15 - i))]) for r in matrix]
+    mult = [bin(r & input).count("1") % 2 for r in matrix]
     return sum([(1 << (15 - i)) * v for i,v in enumerate(mult)])
 
 def roundKey(key, i):