viff

changeset 1323:2fb6e3f39e69

Optimized GF256 operations.
author Marcel Keller <mkeller@cs.au.dk>
date Tue, 06 Oct 2009 18:37:52 +0200
parents 5a2e6564c40a
children 382f0eb42dca
files viff/field.py
diffstat 1 files changed, 17 insertions(+), 9 deletions(-) [+]
line diff
     1.1 --- a/viff/field.py	Tue Oct 06 17:52:14 2009 +0200
     1.2 +++ b/viff/field.py	Tue Oct 06 18:37:52 2009 +0200
     1.3 @@ -117,13 +117,17 @@
     1.4  #: Inversion table.
     1.5  #:
     1.6  #: Maps a value *x* to *x^-1*. See `_generate_tables`.
     1.7 -_inv_table = {}
     1.8 +_inv_table = [None] * 256
     1.9  
    1.10  #: Multiplication table.
    1.11  #:
    1.12  #: Maps *(x,y)* to *xy*. See `_generate_tables`.
    1.13 -_mul_table = {}
    1.14 +_mul_table = [[None] * 256 for i in range(256)]
    1.15  
    1.16 +#: Addition table.
    1.17 +#:
    1.18 +#: Maps *(x,y)* to *x + y*. See `_generate_tables`.
    1.19 +_add_table = [[None] * 256 for i in range(256)]
    1.20  
    1.21  # The class name is slightly wrong since the class instances cannot be
    1.22  # said to be represent a field. Instead they represent instances of
    1.23 @@ -166,7 +170,7 @@
    1.24              return NotImplemented
    1.25          if isinstance(other, GF256):
    1.26              other = other.value
    1.27 -        return GF256(self.value ^ other)
    1.28 +        return _add_table[self.value][other]
    1.29  
    1.30      def __radd__(self, other):
    1.31          """Add this and another number (reflected argument version).
    1.32 @@ -174,8 +178,8 @@
    1.33          other is not Share, otherwise Share.__add__() would have been
    1.34          called, and other is not a GF256, otherwise GF256.__add__()
    1.35          would have been called."""
    1.36 -        return GF256(self.value ^ other)
    1.37 -    
    1.38 +        return _add_table[self.value][other]
    1.39 +
    1.40      #: Subtract this and another GF256 element.
    1.41      #:
    1.42      #: Addition is its own inverse in GF(2^8) and so this is the same
    1.43 @@ -206,7 +210,7 @@
    1.44              return NotImplemented
    1.45          if isinstance(other, GF256):
    1.46              other = other.value
    1.47 -        return _mul_table[(self.value, other)]
    1.48 +        return _mul_table[self.value][other]
    1.49  
    1.50  
    1.51      def __rmul__(self, other):
    1.52 @@ -216,7 +220,7 @@
    1.53          other is not Share, otherwise Share.__mul__() would have been
    1.54          called, and other is not a GF256, otherwise GF256.__mul__()
    1.55          would have been called."""
    1.56 -        return _mul_table[(self.value, other)]
    1.57 +        return _mul_table[self.value][other]
    1.58  
    1.59      def __pow__(self, exponent):
    1.60          """Exponentiation."""
    1.61 @@ -325,6 +329,9 @@
    1.62          log_table[exp_table[c]] = c
    1.63      exp_table[255] = exp_table[0]
    1.64  
    1.65 +    # Don't waste memory for several instances with the same value.
    1.66 +    inst_table = [GF256(i) for i in range(256)]
    1.67 +
    1.68      for x in range(256):
    1.69          for y in range(256):
    1.70              if x == 0 or y == 0:
    1.71 @@ -332,10 +339,11 @@
    1.72              else:
    1.73                  log_product = (log_table[x] + log_table[y]) % 255
    1.74                  z = exp_table[log_product]
    1.75 -            _mul_table[(x,y)] = GF256(z)
    1.76 +            _mul_table[x][y] = inst_table[z % 256]
    1.77 +            _add_table[x][y] = inst_table[x ^ y]
    1.78  
    1.79      for c in range(1, 256):
    1.80 -        _inv_table[c] = GF256(exp_table[255 - log_table[c]])
    1.81 +        _inv_table[c] = inst_table[exp_table[255 - log_table[c]]]
    1.82  
    1.83  _generate_tables()
    1.84