/**
* zfec -- fast forward error correction library with Python interface
- *
- * Copyright (C) 2007 Allmydata, Inc.
- * Author: Zooko Wilcox-O'Hearn
- * mailto:zooko@zooko.com
- *
- * This file is part of zfec.
- *
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public License
- * as published by the Free Software Foundation; either version 2
- * of the License, or (at your option) any later version. This program also
- * comes with the added permission that, in the case that you are obligated to
- * release a derived work under this licence (as per section 2.b of the GPL),
- * you may delay the fulfillment of this obligation for up to 12 months.
- *
- * This program 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 General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software
- * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
- */
-
-/**
- * based on fecmodule.c by the Mnet Project, especially Myers Carpenter and
- * Hauke Johannknecht
*/
#include <Python.h>
#include "stdarg.h"
static PyObject *py_fec_error;
-static PyObject *py_raise_fec_error (const char *format, ...);
static char fec__doc__[] = "\
FEC - Forward Error Correction \n\
";
-static PyObject *
-py_raise_fec_error(const char *format, ...) {
- char exceptionMsg[1024];
- va_list ap;
-
- va_start (ap, format);
- vsnprintf (exceptionMsg, 1024, format, ap);
- va_end (ap);
- exceptionMsg[1023]='\0';
- PyErr_SetString (py_fec_error, exceptionMsg);
- return NULL;
-}
-
static char Encoder__doc__[] = "\
Hold static encoder state (an in-memory table for matrix multiplication), and k and m parameters, and provide {encode()} method.\n\n\
@param k: the number of packets required for reconstruction \n\
} Encoder;
static PyObject *
-Encoder_new(PyTypeObject *type, PyObject *args, PyObject *kwds) {
+Encoder_new(PyTypeObject *type, PyObject *args, PyObject *kwdict) {
Encoder *self;
self = (Encoder*)type->tp_alloc(type, 0);
NULL
};
int ink, inm;
- if (!PyArg_ParseTupleAndKeywords(args, kwdict, "ii", kwlist, &ink, &inm))
+ if (!PyArg_ParseTupleAndKeywords(args, kwdict, "ii:Encoder.__init__", kwlist, &ink, &inm))
return -1;
if (ink < 1) {
- py_raise_fec_error("Precondition violation: first argument is required to be greater than or equal to 1, but it was %d", self->kk);
- return -1;
+ PyErr_Format(py_fec_error, "Precondition violation: first argument is required to be greater than or equal to 1, but it was %d", self->kk);
+ return -1;
}
if (inm < 1) {
- py_raise_fec_error("Precondition violation: second argument is required to be greater than or equal to 1, but it was %d", self->mm);
- return -1;
+ PyErr_Format(py_fec_error, "Precondition violation: second argument is required to be greater than or equal to 1, but it was %d", self->mm);
+ return -1;
}
if (inm > 256) {
- py_raise_fec_error("Precondition violation: second argument is required to be less than or equal to 256, but it was %d", self->mm);
- return -1;
+ PyErr_Format(py_fec_error, "Precondition violation: second argument is required to be less than or equal to 256, but it was %d", self->mm);
+ return -1;
}
if (ink > inm) {
- py_raise_fec_error("Precondition violation: first argument is required to be less than or equal to the second argument, but they were %d and %d respectively", ink, inm);
- return -1;
+ PyErr_Format(py_fec_error, "Precondition violation: first argument is required to be less than or equal to the second argument, but they were %d and %d respectively", ink, inm);
+ return -1;
}
self->kk = (short)ink;
self->mm = (short)inm;
PyObject* desired_blocks_nums = NULL; /* The blocknums of the blocks that should be returned. */
PyObject* result = NULL;
- if (!PyArg_ParseTuple(args, "O|O", &inblocks, &desired_blocks_nums))
- return NULL;
-
- gf* check_blocks_produced[self->mm - self->kk]; /* This is an upper bound -- we will actually use only num_check_blocks_produced of these elements (see below). */
- PyObject* pystrs_produced[self->mm - self->kk]; /* This is an upper bound -- we will actually use only num_check_blocks_produced of these elements (see below). */
+ gf** check_blocks_produced = (gf**)alloca((self->mm - self->kk) * sizeof(PyObject*)); /* This is an upper bound -- we will actually use only num_check_blocks_produced of these elements (see below). */
+ PyObject** pystrs_produced = (PyObject**)alloca((self->mm - self->kk) * sizeof(PyObject*)); /* This is an upper bound -- we will actually use only num_check_blocks_produced of these elements (see below). */
unsigned num_check_blocks_produced = 0; /* The first num_check_blocks_produced elements of the check_blocks_produced array and of the pystrs_produced array will be used. */
- const gf* incblocks[self->kk];
+ const gf** incblocks = (const gf**)alloca(self->kk * sizeof(const gf*));
unsigned num_desired_blocks;
PyObject* fast_desired_blocks_nums = NULL;
PyObject** fast_desired_blocks_nums_items;
- unsigned c_desired_blocks_nums[self->mm];
- unsigned c_desired_checkblocks_ids[self->mm - self->kk];
+ unsigned* c_desired_blocks_nums = (unsigned*)alloca(self->mm * sizeof(unsigned));
+ unsigned* c_desired_checkblocks_ids = (unsigned*)alloca((self->mm - self->kk) * sizeof(unsigned));
unsigned i;
PyObject* fastinblocks = NULL;
+ PyObject** fastinblocksitems;
+ Py_ssize_t sz, oldsz = 0;
+ unsigned char check_block_index = 0; /* index into the check_blocks_produced and (parallel) pystrs_produced arrays */
+
+ if (!PyArg_ParseTuple(args, "O|O:Encoder.encode", &inblocks, &desired_blocks_nums))
+ return NULL;
for (i=0; i<self->mm - self->kk; i++)
pystrs_produced[i] = NULL;
fast_desired_blocks_nums_items = PySequence_Fast_ITEMS(fast_desired_blocks_nums);
for (i=0; i<num_desired_blocks; i++) {
if (!PyInt_Check(fast_desired_blocks_nums_items[i])) {
- py_raise_fec_error("Precondition violation: second argument is required to contain int.");
+ PyErr_Format(py_fec_error, "Precondition violation: second argument is required to contain int.");
goto err;
}
c_desired_blocks_nums[i] = PyInt_AsLong(fast_desired_blocks_nums_items[i]);
goto err;
if (PySequence_Fast_GET_SIZE(fastinblocks) != self->kk) {
- py_raise_fec_error("Precondition violation: Wrong length -- first argument is required to contain exactly k blocks. len(first): %d, k: %d", PySequence_Fast_GET_SIZE(fastinblocks), self->kk);
+ PyErr_Format(py_fec_error, "Precondition violation: Wrong length -- first argument (the sequence of input blocks) is required to contain exactly k blocks. len(first): %Zu, k: %d", PySequence_Fast_GET_SIZE(fastinblocks), self->kk);
goto err;
}
/* Construct a C array of gf*'s of the input data. */
- PyObject** fastinblocksitems = PySequence_Fast_ITEMS(fastinblocks);
+ fastinblocksitems = PySequence_Fast_ITEMS(fastinblocks);
if (!fastinblocksitems)
goto err;
- Py_ssize_t sz, oldsz = 0;
+
for (i=0; i<self->kk; i++) {
if (!PyObject_CheckReadBuffer(fastinblocksitems[i])) {
- py_raise_fec_error("Precondition violation: %u'th item is required to offer the single-segment read character buffer protocol, but it does not.\n", i);
+ PyErr_Format(py_fec_error, "Precondition violation: %u'th item is required to offer the single-segment read character buffer protocol, but it does not.", i);
goto err;
}
if (PyObject_AsReadBuffer(fastinblocksitems[i], (const void**)&(incblocks[i]), &sz))
goto err;
if (oldsz != 0 && oldsz != sz) {
- py_raise_fec_error("Precondition violation: Input blocks are required to be all the same length. oldsz: %Zu, sz: %Zu\n", oldsz, sz);
+ PyErr_Format(py_fec_error, "Precondition violation: Input blocks are required to be all the same length. length of one block was: %Zu, length of another block was: %Zu", oldsz, sz);
goto err;
}
oldsz = sz;
}
/* Allocate space for all of the check blocks. */
- unsigned char check_block_index = 0; /* index into the check_blocks_produced and (parallel) pystrs_produced arrays */
+
for (i=0; i<num_desired_blocks; i++) {
if (c_desired_blocks_nums[i] >= self->kk) {
c_desired_checkblocks_ids[check_block_index] = c_desired_blocks_nums[i];
} Decoder;
static PyObject *
-Decoder_new(PyTypeObject *type, PyObject *args, PyObject *kwds) {
+Decoder_new(PyTypeObject *type, PyObject *args, PyObject *kwdict) {
Decoder *self;
self = (Decoder*)type->tp_alloc(type, 0);
};
int ink, inm;
- if (!PyArg_ParseTupleAndKeywords(args, kwdict, "ii", kwlist, &ink, &inm))
+ if (!PyArg_ParseTupleAndKeywords(args, kwdict, "ii:Decoder.__init__", kwlist, &ink, &inm))
return -1;
if (ink < 1) {
- py_raise_fec_error("Precondition violation: first argument is required to be greater than or equal to 1, but it was %d", self->kk);
+ PyErr_Format(py_fec_error, "Precondition violation: first argument is required to be greater than or equal to 1, but it was %d", self->kk);
return -1;
}
if (inm < 1) {
- py_raise_fec_error("Precondition violation: second argument is required to be greater than or equal to 1, but it was %d", self->mm);
+ PyErr_Format(py_fec_error, "Precondition violation: second argument is required to be greater than or equal to 1, but it was %d", self->mm);
return -1;
}
if (inm > 256) {
- py_raise_fec_error("Precondition violation: second argument is required to be less than or equal to 256, but it was %d", self->mm);
+ PyErr_Format(py_fec_error, "Precondition violation: second argument is required to be less than or equal to 256, but it was %d", self->mm);
return -1;
}
if (ink > inm) {
- py_raise_fec_error("Precondition violation: first argument is required to be less than or equal to the second argument, but they were %d and %d respectively", ink, inm);
+ PyErr_Format(py_fec_error, "Precondition violation: first argument is required to be less than or equal to the second argument, but they were %d and %d respectively", ink, inm);
return -1;
}
self->kk = (short)ink;
PyObject*restrict blocknums;
PyObject* result = NULL;
- if (!PyArg_ParseTuple(args, "OO", &blocks, &blocknums))
+ const gf**restrict cblocks = (const gf**restrict)alloca(self->kk * sizeof(const gf*));
+ unsigned* cblocknums = (unsigned*)alloca(self->kk * sizeof(unsigned));
+ gf**restrict recoveredcstrs = (gf**)alloca(self->kk * sizeof(gf*)); /* self->kk is actually an upper bound -- we probably won't need all of this space. */
+ PyObject**restrict recoveredpystrs = (PyObject**restrict)alloca(self->kk * sizeof(PyObject*)); /* self->kk is actually an upper bound -- we probably won't need all of this space. */
+ unsigned i;
+ PyObject*restrict fastblocknums = NULL;
+ PyObject*restrict fastblocks;
+ unsigned needtorecover=0;
+ PyObject** fastblocksitems;
+ PyObject** fastblocknumsitems;
+ Py_ssize_t sz, oldsz = 0;
+ long tmpl;
+ unsigned nextrecoveredix=0;
+
+ if (!PyArg_ParseTuple(args, "OO:Decoder.decode", &blocks, &blocknums))
return NULL;
- const gf*restrict cblocks[self->kk];
- unsigned cblocknums[self->kk];
- gf*restrict recoveredcstrs[self->kk]; /* self->kk is actually an upper bound -- we probably won't need all of this space. */
- PyObject*restrict recoveredpystrs[self->kk]; /* self->kk is actually an upper bound -- we probably won't need all of this space. */
- unsigned i;
for (i=0; i<self->kk; i++)
recoveredpystrs[i] = NULL;
- PyObject*restrict fastblocknums = NULL;
- PyObject*restrict fastblocks = PySequence_Fast(blocks, "First argument was not a sequence.");
+ fastblocks = PySequence_Fast(blocks, "First argument was not a sequence.");
if (!fastblocks)
goto err;
fastblocknums = PySequence_Fast(blocknums, "Second argument was not a sequence.");
goto err;
if (PySequence_Fast_GET_SIZE(fastblocks) != self->kk) {
- py_raise_fec_error("Precondition violation: Wrong length -- first argument is required to contain exactly k blocks. len(first): %d, k: %d", PySequence_Fast_GET_SIZE(fastblocks), self->kk);
+ PyErr_Format(py_fec_error, "Precondition violation: Wrong length -- first argument is required to contain exactly k blocks. len(first): %Zu, k: %d", PySequence_Fast_GET_SIZE(fastblocks), self->kk);
goto err;
}
if (PySequence_Fast_GET_SIZE(fastblocknums) != self->kk) {
- py_raise_fec_error("Precondition violation: Wrong length -- blocknums is required to contain exactly k blocks. len(blocknums): %d, k: %d", PySequence_Fast_GET_SIZE(fastblocknums), self->kk);
+ PyErr_Format(py_fec_error, "Precondition violation: Wrong length -- blocknums is required to contain exactly k blocks. len(blocknums): %Zu, k: %d", PySequence_Fast_GET_SIZE(fastblocknums), self->kk);
goto err;
}
/* Construct a C array of gf*'s of the data and another of C ints of the blocknums. */
- unsigned needtorecover=0;
- PyObject** fastblocknumsitems = PySequence_Fast_ITEMS(fastblocknums);
+ fastblocknumsitems = PySequence_Fast_ITEMS(fastblocknums);
if (!fastblocknumsitems)
goto err;
- PyObject** fastblocksitems = PySequence_Fast_ITEMS(fastblocks);
+ fastblocksitems = PySequence_Fast_ITEMS(fastblocks);
if (!fastblocksitems)
goto err;
- Py_ssize_t sz, oldsz = 0;
+
for (i=0; i<self->kk; i++) {
if (!PyInt_Check(fastblocknumsitems[i])) {
- py_raise_fec_error("Precondition violation: second argument is required to contain int.");
+ PyErr_Format(py_fec_error, "Precondition violation: second argument is required to contain int.");
goto err;
}
- long tmpl = PyInt_AsLong(fastblocknumsitems[i]);
+ tmpl = PyInt_AsLong(fastblocknumsitems[i]);
if (tmpl < 0 || tmpl > 255) {
- py_raise_fec_error("Precondition violation: block nums can't be less than zero or greater than 255. %ld\n", tmpl);
+ PyErr_Format(py_fec_error, "Precondition violation: block nums can't be less than zero or greater than 255. %ld\n", tmpl);
goto err;
}
cblocknums[i] = (unsigned)tmpl;
needtorecover+=1;
if (!PyObject_CheckReadBuffer(fastblocksitems[i])) {
- py_raise_fec_error("Precondition violation: %u'th item is required to offer the single-segment read character buffer protocol, but it does not.\n", i);
+ PyErr_Format(py_fec_error, "Precondition violation: %u'th item is required to offer the single-segment read character buffer protocol, but it does not.\n", i);
goto err;
}
if (PyObject_AsReadBuffer(fastblocksitems[i], (const void**)&(cblocks[i]), &sz))
goto err;
if (oldsz != 0 && oldsz != sz) {
- py_raise_fec_error("Precondition violation: Input blocks are required to be all the same length. oldsz: %Zu, sz: %Zu\n", oldsz, sz);
+ PyErr_Format(py_fec_error, "Precondition violation: Input blocks are required to be all the same length. length of one block was: %Zu, length of another block was: %Zu\n", oldsz, sz);
goto err;
}
oldsz = sz;
}
- /* move src packets into position */
+ /* Move src packets into position. At the end of this loop we want the i'th
+ element of the arrays to be the block with block number i, if that block
+ is among our inputs. */
for (i=0; i<self->kk;) {
if (cblocknums[i] >= self->kk || cblocknums[i] == i)
i++;
fec_decode(self->fec_matrix, cblocks, recoveredcstrs, cblocknums, sz);
/* Wrap up both original primary blocks and decoded blocks into a Python list of Python strings. */
- unsigned nextrecoveredix=0;
result = PyList_New(self->kk);
if (result == NULL)
goto err;
Decoder_new, /* tp_new */
};
-static PyMethodDef fec_methods[] = {
+void
+_hexwrite(unsigned char*s, size_t l) {
+ for (size_t i = 0; i < l; i++)
+ printf("%.2x", s[i]);
+}
+
+
+PyObject*
+test_from_agl(); /* <- prototype */
+
+PyObject*
+test_from_agl() {
+ unsigned char b0c[8], b1c[8];
+ unsigned char b0[8], b1[8], b2[8], b3[8], b4[8];
+ memset(b0, 1, 8);
+ memset(b1, 2, 8);
+ memset(b2, 3, 8);
+ const unsigned char *blocks[3] = {b0, b1, b2};
+ unsigned char *outblocks[2] = {b3, b4};
+ unsigned block_nums[] = {3, 4};
+
+ /*printf("_from_c before encoding:\n");
+ printf("b0: "); _hexwrite(b0, 8); printf(", ");
+ printf("b1: "); _hexwrite(b1, 8); printf(", ");
+ printf("b2: "); _hexwrite(b2, 8); printf(", ");
+ printf("\n");*/
+
+ fec_t *const fec = fec_new(3, 5);
+ fec_encode(fec, blocks, outblocks, block_nums, 2, 8);
+
+ /*printf("after encoding:\n");
+ printf("b3: "); _hexwrite(b3, 8); printf(", ");
+ printf("b4: "); _hexwrite(b4, 8); printf(", ");
+ printf("\n");*/
+
+ memcpy(b0c, b0, 8); memcpy(b1c, b1, 8);
+
+ const unsigned char *inpkts[] = {b3, b4, b2};
+ unsigned char *outpkts[] = {b0, b1};
+ unsigned indexes[] = {3, 4, 2};
+
+ fec_decode(fec, inpkts, outpkts, indexes, 8);
+
+ /*printf("after decoding:\n");
+ printf("b0: "); _hexwrite(b0, 8); printf(", ");
+ printf("b1: "); _hexwrite(b1, 8);
+ printf("\n");*/
+
+ if ((memcmp(b0, b0c,8) == 0) && (memcmp(b1, b1c,8) == 0))
+ Py_RETURN_TRUE;
+ else
+ Py_RETURN_FALSE;
+}
+
+static PyMethodDef fec_functions[] = {
+ {"test_from_agl", test_from_agl, METH_NOARGS, NULL},
{NULL}
};
if (PyType_Ready(&Decoder_type) < 0)
return;
- module = Py_InitModule3("_fec", fec_methods, fec__doc__);
+ module = Py_InitModule3("_fec", fec_functions, fec__doc__);
if (module == NULL)
return;
PyDict_SetItemString(module_dict, "Error", py_fec_error);
}
+/**
+ * originally inspired by fecmodule.c by the Mnet Project, especially Myers
+ * Carpenter and Hauke Johannknecht
+ */