changeset 1463:fd134edef387

cfield: Added C implementation of GF256.
author Marcel Keller <mkeller@cs.au.dk>
date Mon, 02 Aug 2010 17:17:34 +0200
parents 47386d89e4fc
children 47f4c80e1acd
files setup.py viff/boost.py viff/cfield.c
diffstat 3 files changed, 453 insertions(+), 1 deletions(-) [+]
line wrap: on
line diff
--- a/setup.py	Mon Aug 02 17:17:13 2010 +0200
+++ b/setup.py	Mon Aug 02 17:17:34 2010 +0200
@@ -52,6 +52,8 @@
 
 cdefer = Extension('viff.cdefer',
                    sources = ['viff/cdefer.c'])
+cfield = Extension('viff.cfield',
+                   sources = ['viff/cfield.c'])
 
 setup(name='viff',
       version=viff.__version__,
@@ -105,7 +107,7 @@
         'Topic :: Software Development :: Libraries :: Python Modules'
         ],
       cmdclass={'sdist': hg_sdist},
-      ext_modules = [cdefer]
+      ext_modules = [cdefer, cfield]
       )
 
 # When releasing VIFF, notify these sites:
--- a/viff/boost.py	Mon Aug 02 17:17:13 2010 +0200
+++ b/viff/boost.py	Mon Aug 02 17:17:34 2010 +0200
@@ -23,6 +23,8 @@
 import viff.cdefer
 from viff.cdefer import Deferred, Share, ShareList
 
+import viff.cfield
+
 
 # DeferredList copied here to base it on cdefer
 
@@ -110,6 +112,11 @@
     twisted.internet.defer.Deferred = viff.cdefer.Deferred
     twisted.internet.defer.DeferredList = DeferredList
 
+    import viff.field
+    viff.field.FieldElement = viff.cfield.FieldElement
+    viff.field.GF256 = viff.cfield.GF256
+    viff.field._field_cache[256] = viff.cfield.GF256
+
     if with_viff_reactor:
         import viff.reactor
         viff.reactor.install()
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/viff/cfield.c	Mon Aug 02 17:17:34 2010 +0200
@@ -0,0 +1,443 @@
+/*
+ * Copyright 2010 VIFF Development Team.
+ *
+ * This file is part of VIFF, the Virtual Ideal Functionality Framework.
+ *
+ * VIFF is free software: you can redistribute it and/or modify it
+ * under the terms of the GNU Lesser General Public License (LGPL) as
+ * published by the Free Software Foundation, either version 3 of the
+ * License, or (at your option) any later version.
+ *
+ * VIFF is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+ * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
+ * Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
+ *
+ */
+
+#include <Python.h>
+#include <structmember.h>
+
+// dummy type FieldElement
+static PyTypeObject cfield_FieldElementType = {
+    PyObject_HEAD_INIT(NULL)
+    0,                          /*ob_size*/
+    "cfield.FieldElement",      /*tp_name*/
+    sizeof(PyObject),           /*tp_basicsize*/
+    0,                          /*tp_itemsize*/
+    0,                          /*tp_dealloc*/
+    0,                          /*tp_print*/
+    0,                          /*tp_getattr*/
+    0,                          /*tp_setattr*/
+    0,                          /*tp_compare*/
+    0,                          /*tp_repr*/
+    0,                          /*tp_as_number*/
+    0,                          /*tp_as_sequence*/
+    0,                          /*tp_as_mapping*/
+    0,                          /*tp_hash */
+    0,                          /*tp_call*/
+    0,                          /*tp_str*/
+    0,                          /*tp_getattro*/
+    0,                          /*tp_setattro*/
+    0,                          /*tp_as_buffer*/
+    Py_TPFLAGS_DEFAULT|Py_TPFLAGS_BASETYPE, /*tp_flags*/
+    0,                          /*tp_doc*/
+    0,                          /*tp_traverse*/
+    0,                          /*tp_clear*/
+    0,                          /*tp_richcompare*/
+    0,                          /*tp_weaklistoffset*/
+    0,                          /*tp_iter*/
+    0,                          /*tp_iternext*/
+    0,                          /*tp_methods*/
+    0,                          /*tp_members*/
+    0,                          /*tp_getset*/
+    0,                          /*tp_base*/
+    0,                          /*tp_dict*/
+    0,                          /*tp_descr_get*/
+    0,                          /*tp_descr_set*/
+    0,                          /*tp_dictoffset*/
+    0,                          /*tp_init*/
+    0,                          /*tp_alloc*/
+    0,                          /*tp_new*/
+    0,                          /*tp_free*/
+    0,                          /*tp_is_gc*/
+    0,                          /*tp_bases*/
+    0,                          /*tp_mro*/
+    0,                          /*tp_cache*/
+    0,                          /*tp_subclasses*/
+    0,                          /*tp_weaklist*/
+};
+
+typedef struct {
+    PyObject_HEAD
+    int value;
+} cfield_GF256;
+
+static struct PyMemberDef cfield_GF256_members[] = {
+  {"value", T_INT, offsetof(cfield_GF256, value), READONLY, 0},
+  {0, 0, 0, 0, 0}
+};
+
+static cfield_GF256 cfield_GF256_inst[256];
+static PyObject* cfield_GF256_mult_table[256][256];
+static PyObject* cfield_GF256_inv_table[256];
+
+static void cfield_GF256_generate_tables(void) {
+    int log_table[256];
+    int exp_table[256];
+    unsigned char c;
+    unsigned char a = 1;
+    unsigned char d;
+    int x, y;
+    unsigned char z;
+
+    // Code from http://www.samiam.org/galois.html
+    for (c = 0; c < 255; c++) {
+	exp_table[c] = a;
+	/* Multiply by three */
+	d = a & 0x80;
+	a <<= 1;
+
+	if (d == 0x80)
+	    a ^= 0x1b;
+
+	a ^= exp_table[c];
+	/* Set the log table value */
+	log_table[exp_table[c]] = c;
+    }
+
+    exp_table[255] = exp_table[0];
+    log_table[0] = 0;
+
+    for (x = 0; x < 256; x++) {
+	for (y = 0; y < 256; y++) {
+	    if (x == 0 || y == 0)
+		z = 0;
+	    else
+		z = exp_table[(log_table[x] + log_table[y]) % 255];
+	    cfield_GF256_mult_table[x][y] =
+		(PyObject*)&cfield_GF256_inst[z];
+	}
+
+	cfield_GF256_inv_table[x] = (PyObject*)
+	    &cfield_GF256_inst[exp_table[255 - log_table[x]]];
+    }
+}
+
+static PyObject* cfield_GF256__new(unsigned char value) {
+    Py_INCREF(&cfield_GF256_inst[value]);
+    return (PyObject*)&cfield_GF256_inst[value];
+}
+
+static PyObject* cfield_GF256_new(PyTypeObject* type, PyObject* args,
+				  PyObject* kwargs)
+{
+    unsigned char value;
+
+    if (!PyArg_ParseTuple(args, "B", &value))
+	return NULL;
+
+    return cfield_GF256__new(value);
+}
+
+#define GET_VALUES(IN1, IN2, OUT1, OUT2, OP)			    \
+    if (Py_TYPE(IN1)->tp_as_number != NULL &&			    \
+	Py_TYPE(IN1)->tp_as_number->nb_##OP == cfield_GF256_##OP) { \
+	OUT1 = (unsigned char) ((cfield_GF256*)IN1)->value;	    \
+    } else {							    \
+	if (PyInt_Check(IN1))					    \
+	    OUT1 = (unsigned char) PyInt_AS_LONG(IN1);		    \
+	else if (PyLong_Check(IN1))				    \
+	    OUT1 = (unsigned char) PyLong_AsLong(IN1);		    \
+	else {							    \
+	    Py_INCREF(Py_NotImplemented);			    \
+	    return Py_NotImplemented;				    \
+	}							    \
+	OUT2 = (unsigned char) ((cfield_GF256*)IN2)->value;	    \
+    }								    \
+    if (Py_TYPE(IN2)->tp_as_number != NULL &&			    \
+	Py_TYPE(IN2)->tp_as_number->nb_##OP == cfield_GF256_##OP) { \
+	OUT2 = (unsigned char) ((cfield_GF256*)IN2)->value;	    \
+    } else if (PyInt_Check(IN2))				    \
+	OUT2 = (unsigned char) PyInt_AS_LONG(IN2);		    \
+    else if (PyLong_Check(IN2))					    \
+	OUT2 = (unsigned char) PyLong_AsLong(IN2);		    \
+    else {							    \
+	Py_INCREF(Py_NotImplemented);				    \
+	return Py_NotImplemented;				    \
+    }
+
+static PyObject* cfield_GF256_add(PyObject* self, PyObject* other) {
+    unsigned char a, b;
+    GET_VALUES(self, other, a, b, add);
+    return cfield_GF256__new(a ^ b);
+}
+
+static PyObject* cfield_GF256_multiply(PyObject* self, PyObject* other) {
+    unsigned char a, b;
+    PyObject* result;
+    GET_VALUES(self, other, a, b, multiply);
+    result = cfield_GF256_mult_table[a][b];
+    Py_INCREF(result);
+    return result;
+}
+
+static PyObject* cfield_GF256_divide(PyObject* self, PyObject* other) {
+    unsigned char a, b;
+    PyObject* result;
+    GET_VALUES(self, other, a, b, divide);
+
+    if (b == 0) {
+	PyErr_SetString(PyExc_ZeroDivisionError, "Cannot divide by zero.");
+	return NULL;
+    }
+
+    result = cfield_GF256_mult_table[a]
+	[((cfield_GF256*)cfield_GF256_inv_table[b])->value];
+    Py_INCREF(result);
+    return result;
+}
+
+static PyObject* cfield_GF256_inv(cfield_GF256* self) {
+    PyObject* result;
+
+    if (self->value == 0) {
+	PyErr_SetString(PyExc_ZeroDivisionError, "Cannot invert zero.");
+	return NULL;
+    }
+
+    result = cfield_GF256_inv_table[self->value];
+    Py_INCREF(result);
+    return result;
+}
+
+static cfield_GF256* cfield_GF256_square_multiply(cfield_GF256* base,
+						  unsigned char exponent)
+{
+    cfield_GF256* tmp;
+
+    if (exponent == 0)
+	return &cfield_GF256_inst[1];
+    else if (exponent % 2 == 0) {
+	base = cfield_GF256_square_multiply(base, exponent / 2);
+	return (cfield_GF256*)cfield_GF256_mult_table[base->value][base->value];
+    } else {
+	tmp = cfield_GF256_square_multiply(base, exponent - 1);
+	return (cfield_GF256*)cfield_GF256_mult_table[base->value][tmp->value];
+    }
+}
+
+static PyObject* cfield_GF256_pow(PyObject* self, PyObject* other,
+				  PyObject* modulus)
+{
+    unsigned char exponent;
+    cfield_GF256* result;
+
+    if (!PyInt_Check(other)) {
+	PyErr_SetString(PyExc_TypeError, "Exponent must be integer.");
+	return NULL;
+    }
+
+    if (modulus != Py_None) {
+	PyErr_SetString(PyExc_TypeError,
+			"Exponentiation with modulus not possible.");
+	return NULL;
+    }
+
+    exponent = (unsigned char)PyInt_AS_LONG(other);
+    result = cfield_GF256_square_multiply((cfield_GF256*)self, exponent);
+    Py_INCREF(result);
+    return (PyObject*)result;
+}
+
+static PyObject* cfield_GF256_richcompare(PyObject* self, PyObject* other,
+					  int op)
+{
+    unsigned char a, b;
+
+    switch (op) {
+    case Py_EQ:
+    case Py_NE:
+	if (Py_TYPE(self)->tp_richcompare == cfield_GF256_richcompare) {
+	    a = (unsigned char) ((cfield_GF256*)self)->value;
+	} else {
+	    if (PyInt_Check(self))
+		a = (unsigned char) PyInt_AS_LONG(self);
+	    else if (PyLong_Check(self))
+		a = (unsigned char) PyLong_AsLong(self);
+	    else {
+		Py_INCREF(Py_NotImplemented);
+		return Py_NotImplemented;
+	    }
+
+	    b = (unsigned char) ((cfield_GF256*)other)->value;
+	}
+
+	if (Py_TYPE(other)->tp_richcompare == cfield_GF256_richcompare) {
+	    b = (unsigned char) ((cfield_GF256*)other)->value;
+	} else if (PyInt_Check(other))
+	    b = (unsigned char) PyInt_AS_LONG(other);
+	else if (PyLong_Check(other))
+	    b = (unsigned char) PyLong_AsLong(other);
+ 	else {
+	    Py_INCREF(Py_NotImplemented);
+	    return Py_NotImplemented;
+	}
+
+	if ((a == b) ^ (op == Py_EQ)) {
+	    Py_INCREF(Py_False);
+	    return Py_False;
+	} else {
+	    Py_INCREF(Py_True);
+	    return Py_True;
+	}
+
+	break;
+    default:
+	PyErr_SetString(PyExc_TypeError, "GF256 elements are not ordered.");
+	return NULL;
+    }
+}
+
+static long cfield_GF256_hash(PyObject* self) {
+    return (long)self;
+}
+
+static PyObject* cfield_GF256_repr(PyObject* self) {
+    return PyString_FromFormat("[%d]", ((cfield_GF256*)self)->value);
+}
+
+static int cfield_GF256_nonzero(cfield_GF256* self) {
+    if (self->value == 0)
+	return 0;
+    else
+	return 1;
+}
+
+static PyObject* cfield_GF256_int(cfield_GF256* self) {
+    return PyInt_FromLong(self->value);
+}
+
+static PyNumberMethods cfield_GF256_as_number = {
+        cfield_GF256_add,               /*nb_add*/
+        cfield_GF256_add,               /*nb_subtract*/
+        cfield_GF256_multiply,          /*nb_multiply*/
+        cfield_GF256_divide,            /*nb_divide*/
+        0,                              /*nb_remainder*/
+        0,                              /*nb_divmod*/
+        cfield_GF256_pow,               /*nb_power*/
+        0,                              /*nb_negative*/
+        0,                              /*tp_positive*/
+        0,                              /*tp_absolute*/
+        (inquiry)cfield_GF256_nonzero,  /*tp_nonzero*/
+        (unaryfunc)cfield_GF256_inv,    /*nb_invert*/
+        0,                              /*nb_lshift*/
+        0,                              /*nb_rshift*/
+        0,                              /*nb_and*/
+	cfield_GF256_add,               /*nb_xor*/
+        0,                              /*nb_or*/
+        0,                              /*nb_coerce*/
+        (unaryfunc)cfield_GF256_int,    /*nb_int*/
+        0,                              /*nb_long*/
+        0,                              /*nb_float*/
+        0,                              /*nb_oct*/
+        0,                              /*nb_hex*/
+        0,                              /* nb_inplace_add */
+        0,                              /* nb_inplace_subtract */
+        0,                              /* nb_inplace_multiply */
+        0,                              /* nb_inplace_divide */
+        0,                              /* nb_inplace_remainder */
+        0,                              /* nb_inplace_power */
+        0,                              /* nb_inplace_lshift */
+        0,                              /* nb_inplace_rshift */
+        0,                              /* nb_inplace_and */
+        0,                              /* nb_inplace_xor */
+        0,                              /* nb_inplace_or */
+        0,                              /* nb_floor_divide */
+        0,                              /* nb_true_divide */
+        0,                              /* nb_inplace_floor_divide */
+        0                               /* nb_inplace_true_divide */
+};
+
+static PyTypeObject cfield_GF256Type = {
+    PyObject_HEAD_INIT(NULL)
+    0,                          /*ob_size*/
+    "cfield.GF256",             /*tp_name*/
+    sizeof(cfield_GF256),       /*tp_basicsize*/
+    0,                          /*tp_itemsize*/
+    0,                          /*tp_dealloc*/
+    0,                          /*tp_print*/
+    0,                          /*tp_getattr*/
+    0,                          /*tp_setattr*/
+    0,                          /*tp_compare*/
+    cfield_GF256_repr,          /*tp_repr*/
+    &cfield_GF256_as_number,    /*tp_as_number*/
+    0,                          /*tp_as_sequence*/
+    0,                          /*tp_as_mapping*/
+    cfield_GF256_hash,          /*tp_hash */
+    0,                          /*tp_call*/
+    cfield_GF256_repr,          /*tp_str*/
+    0,                          /*tp_getattro*/
+    0,                          /*tp_setattro*/
+    0,                          /*tp_as_buffer*/
+    Py_TPFLAGS_DEFAULT|Py_TPFLAGS_BASETYPE|Py_TPFLAGS_CHECKTYPES, /*tp_flags*/
+    0,                          /*tp_doc*/
+    0,                          /*tp_traverse*/
+    0,                          /*tp_clear*/
+    cfield_GF256_richcompare,   /*tp_richcompare*/
+    0,                          /*tp_weaklistoffset*/
+    0,                          /*tp_iter*/
+    0,                          /*tp_iternext*/
+    0,                          /*tp_methods*/
+    cfield_GF256_members,       /*tp_members*/
+    0,                          /*tp_getset*/
+    &cfield_FieldElementType,   /*tp_base*/
+    0,                          /*tp_dict*/
+    0,                          /*tp_descr_get*/
+    0,                          /*tp_descr_set*/
+    0,                          /*tp_dictoffset*/
+    0,                          /*tp_init*/
+    0,                          /*tp_alloc*/
+    cfield_GF256_new,           /*tp_new*/
+    0,                          /*tp_free*/
+    0,                          /*tp_is_gc*/
+    0,                          /*tp_bases*/
+    0,                          /*tp_mro*/
+    0,                          /*tp_cache*/
+    0,                          /*tp_subclasses*/
+    0,                          /*tp_weaklist*/
+};
+
+PyMODINIT_FUNC initcfield(void) {
+    PyObject* m;
+    int i;
+
+    if (PyType_Ready(&cfield_GF256Type) < 0)
+	return;
+
+    m = Py_InitModule3("cfield", 0, "C implemementation of viff.field");
+
+    if (!m)
+	return;
+
+    Py_INCREF(&cfield_FieldElementType);
+    PyModule_AddObject(m, "FieldElement", (PyObject*)&cfield_FieldElementType);
+    Py_INCREF(&cfield_GF256Type);
+    PyModule_AddObject(m, "GF256", (PyObject*)&cfield_GF256Type);
+
+    PyDict_SetItemString(cfield_GF256Type.tp_dict, "modulus",
+			 PyInt_FromLong(256));
+    PyDict_SetItemString(cfield_GF256Type.tp_dict, "field",
+			 (PyObject*)&cfield_GF256Type);
+
+    for (i = 0; i < 256; i++) {
+	PyObject_Init((PyObject*)(&cfield_GF256_inst[i]),
+		      (PyTypeObject*)&cfield_GF256Type);
+	cfield_GF256_inst[i].value = i;
+    }
+
+    cfield_GF256_generate_tables();
+}