2 * zfec -- fast forward error correction library with Python interface
6 #include <structmember.h>
8 #if (PY_VERSION_HEX < 0x02050000)
9 typedef int Py_ssize_t;
16 static PyObject *py_fec_error;
18 static char fec__doc__[] = "\
19 FEC - Forward Error Correction \n\
22 static char Encoder__doc__[] = "\
23 Hold static encoder state (an in-memory table for matrix multiplication), and k and m parameters, and provide {encode()} method.\n\n\
24 @param k: the number of packets required for reconstruction \n\
25 @param m: the number of packets generated \n\
40 Encoder_new(PyTypeObject *type, PyObject *args, PyObject *kwdict) {
43 self = (Encoder*)type->tp_alloc(type, 0);
47 self->fec_matrix = NULL;
50 return (PyObject *)self;
54 Encoder_init(Encoder *self, PyObject *args, PyObject *kwdict) {
55 static char *kwlist[] = {
61 if (!PyArg_ParseTupleAndKeywords(args, kwdict, "ii:Encoder.__init__", kwlist, &ink, &inm))
65 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);
69 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);
73 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);
77 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);
80 self->kk = (short)ink;
81 self->mm = (short)inm;
82 self->fec_matrix = fec_new(self->kk, self->mm);
87 static char Encoder_encode__doc__[] = "\
88 Encode data into m packets.\n\
90 @param inblocks: a sequence of k buffers of data to encode -- these are the k primary blocks, i.e. the input data split into k pieces (for best performance, make it a tuple instead of a list); All blocks are required to be the same length.\n\
91 @param desired_blocks_nums optional sequence of blocknums indicating which blocks to produce and return; If None, all m blocks will be returned (in order). (For best performance, make it a tuple instead of a list.)\n\
92 @returns: a list of buffers containing the requested blocks; Note that if any of the input blocks were 'primary blocks', i.e. their blocknum was < k, then the result sequence will contain a Python reference to the same Python object as was passed in. As long as the Python object in question is immutable (i.e. a string) then you don't have to think about this detail, but if it is mutable (i.e. an array), then you have to be aware that if you subsequently mutate the contents of that object then that will also change the contents of the sequence that was returned from this call to encode().\n\
96 Encoder_encode(Encoder *self, PyObject *args) {
98 PyObject* desired_blocks_nums = NULL; /* The blocknums of the blocks that should be returned. */
99 PyObject* result = NULL;
101 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). */
102 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). */
103 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. */
104 const gf** incblocks = (const gf**)alloca(self->kk * sizeof(const gf*));
105 unsigned num_desired_blocks;
106 PyObject* fast_desired_blocks_nums = NULL;
107 PyObject** fast_desired_blocks_nums_items;
108 unsigned* c_desired_blocks_nums = (unsigned*)alloca(self->mm * sizeof(unsigned));
109 unsigned* c_desired_checkblocks_ids = (unsigned*)alloca((self->mm - self->kk) * sizeof(unsigned));
111 PyObject* fastinblocks = NULL;
112 PyObject** fastinblocksitems;
113 Py_ssize_t sz, oldsz = 0;
114 unsigned char check_block_index = 0; /* index into the check_blocks_produced and (parallel) pystrs_produced arrays */
116 if (!PyArg_ParseTuple(args, "O|O:Encoder.encode", &inblocks, &desired_blocks_nums))
119 for (i=0; i<self->mm - self->kk; i++)
120 pystrs_produced[i] = NULL;
121 if (desired_blocks_nums) {
122 fast_desired_blocks_nums = PySequence_Fast(desired_blocks_nums, "Second argument (optional) was not a sequence.");
123 if (!fast_desired_blocks_nums)
125 num_desired_blocks = PySequence_Fast_GET_SIZE(fast_desired_blocks_nums);
126 fast_desired_blocks_nums_items = PySequence_Fast_ITEMS(fast_desired_blocks_nums);
127 for (i=0; i<num_desired_blocks; i++) {
128 if (!PyInt_Check(fast_desired_blocks_nums_items[i])) {
129 PyErr_Format(py_fec_error, "Precondition violation: second argument is required to contain int.");
132 c_desired_blocks_nums[i] = PyInt_AsLong(fast_desired_blocks_nums_items[i]);
133 if (c_desired_blocks_nums[i] >= self->kk)
134 num_check_blocks_produced++;
137 num_desired_blocks = self->mm;
138 for (i=0; i<num_desired_blocks; i++)
139 c_desired_blocks_nums[i] = i;
140 num_check_blocks_produced = self->mm - self->kk;
143 fastinblocks = PySequence_Fast(inblocks, "First argument was not a sequence.");
147 if (PySequence_Fast_GET_SIZE(fastinblocks) != self->kk) {
148 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);
152 /* Construct a C array of gf*'s of the input data. */
153 fastinblocksitems = PySequence_Fast_ITEMS(fastinblocks);
154 if (!fastinblocksitems)
157 for (i=0; i<self->kk; i++) {
158 if (!PyObject_CheckReadBuffer(fastinblocksitems[i])) {
159 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);
162 if (PyObject_AsReadBuffer(fastinblocksitems[i], (const void**)&(incblocks[i]), &sz))
164 if (oldsz != 0 && oldsz != sz) {
165 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);
171 /* Allocate space for all of the check blocks. */
173 for (i=0; i<num_desired_blocks; i++) {
174 if (c_desired_blocks_nums[i] >= self->kk) {
175 c_desired_checkblocks_ids[check_block_index] = c_desired_blocks_nums[i];
176 pystrs_produced[check_block_index] = PyString_FromStringAndSize(NULL, sz);
177 if (pystrs_produced[check_block_index] == NULL)
179 check_blocks_produced[check_block_index] = (gf*)PyString_AsString(pystrs_produced[check_block_index]);
180 if (check_blocks_produced[check_block_index] == NULL)
185 assert (check_block_index == num_check_blocks_produced);
187 /* Encode any check blocks that are needed. */
188 fec_encode(self->fec_matrix, incblocks, check_blocks_produced, c_desired_checkblocks_ids, num_check_blocks_produced, sz);
190 /* Wrap all requested blocks up into a Python list of Python strings. */
191 result = PyList_New(num_desired_blocks);
194 check_block_index = 0;
195 for (i=0; i<num_desired_blocks; i++) {
196 if (c_desired_blocks_nums[i] < self->kk) {
197 Py_INCREF(fastinblocksitems[c_desired_blocks_nums[i]]);
198 if (PyList_SetItem(result, i, fastinblocksitems[c_desired_blocks_nums[i]]) == -1) {
199 Py_DECREF(fastinblocksitems[c_desired_blocks_nums[i]]);
203 if (PyList_SetItem(result, i, pystrs_produced[check_block_index]) == -1)
205 pystrs_produced[check_block_index] = NULL;
212 for (i=0; i<num_check_blocks_produced; i++)
213 Py_XDECREF(pystrs_produced[i]);
214 Py_XDECREF(result); result = NULL;
216 Py_XDECREF(fastinblocks); fastinblocks=NULL;
217 Py_XDECREF(fast_desired_blocks_nums); fast_desired_blocks_nums=NULL;
222 Encoder_dealloc(Encoder * self) {
223 fec_free(self->fec_matrix);
224 self->ob_type->tp_free((PyObject*)self);
227 static PyMethodDef Encoder_methods[] = {
228 {"encode", (PyCFunction)Encoder_encode, METH_VARARGS, Encoder_encode__doc__},
232 static PyMemberDef Encoder_members[] = {
233 {"k", T_SHORT, offsetof(Encoder, kk), READONLY, "k"},
234 {"m", T_SHORT, offsetof(Encoder, mm), READONLY, "m"},
235 {NULL} /* Sentinel */
238 static PyTypeObject Encoder_type = {
239 PyObject_HEAD_INIT(NULL)
241 "_fec.Encoder", /*tp_name*/
242 sizeof(Encoder), /*tp_basicsize*/
244 (destructor)Encoder_dealloc, /*tp_dealloc*/
251 0, /*tp_as_sequence*/
259 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE, /*tp_flags*/
260 Encoder__doc__, /* tp_doc */
263 0, /* tp_richcompare */
264 0, /* tp_weaklistoffset */
267 Encoder_methods, /* tp_methods */
268 Encoder_members, /* tp_members */
272 0, /* tp_descr_get */
273 0, /* tp_descr_set */
274 0, /* tp_dictoffset */
275 (initproc)Encoder_init, /* tp_init */
277 Encoder_new, /* tp_new */
280 static char Decoder__doc__[] = "\
281 Hold static decoder state (an in-memory table for matrix multiplication), and k and m parameters, and provide {decode()} method.\n\n\
282 @param k: the number of packets required for reconstruction \n\
283 @param m: the number of packets generated \n\
298 Decoder_new(PyTypeObject *type, PyObject *args, PyObject *kwdict) {
301 self = (Decoder*)type->tp_alloc(type, 0);
305 self->fec_matrix = NULL;
308 return (PyObject *)self;
312 Decoder_init(Encoder *self, PyObject *args, PyObject *kwdict) {
313 static char *kwlist[] = {
320 if (!PyArg_ParseTupleAndKeywords(args, kwdict, "ii:Decoder.__init__", kwlist, &ink, &inm))
324 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);
328 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);
332 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);
336 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);
339 self->kk = (short)ink;
340 self->mm = (short)inm;
341 self->fec_matrix = fec_new(self->kk, self->mm);
346 #define SWAP(a,b,t) {t tmp; tmp=a; a=b; b=tmp;}
348 static char Decoder_decode__doc__[] = "\
349 Decode a list blocks into a list of segments.\n\
350 @param blocks a sequence of buffers containing block data (for best performance, make it a tuple instead of a list)\n\
351 @param blocknums a sequence of integers of the blocknum for each block in blocks (for best performance, make it a tuple instead of a list)\n\
353 @return a list of strings containing the segment data (i.e. ''.join(retval) yields a string containing the decoded data)\n\
357 Decoder_decode(Decoder *self, PyObject *args) {
358 PyObject*restrict blocks;
359 PyObject*restrict blocknums;
360 PyObject* result = NULL;
362 const gf**restrict cblocks = (const gf**restrict)alloca(self->kk * sizeof(const gf*));
363 unsigned* cblocknums = (unsigned*)alloca(self->kk * sizeof(unsigned));
364 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. */
365 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. */
367 PyObject*restrict fastblocknums = NULL;
368 PyObject*restrict fastblocks;
369 unsigned needtorecover=0;
370 PyObject** fastblocksitems;
371 PyObject** fastblocknumsitems;
372 Py_ssize_t sz, oldsz = 0;
374 unsigned nextrecoveredix=0;
376 if (!PyArg_ParseTuple(args, "OO:Decoder.decode", &blocks, &blocknums))
379 for (i=0; i<self->kk; i++)
380 recoveredpystrs[i] = NULL;
381 fastblocks = PySequence_Fast(blocks, "First argument was not a sequence.");
384 fastblocknums = PySequence_Fast(blocknums, "Second argument was not a sequence.");
388 if (PySequence_Fast_GET_SIZE(fastblocks) != self->kk) {
389 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);
392 if (PySequence_Fast_GET_SIZE(fastblocknums) != self->kk) {
393 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);
397 /* Construct a C array of gf*'s of the data and another of C ints of the blocknums. */
398 fastblocknumsitems = PySequence_Fast_ITEMS(fastblocknums);
399 if (!fastblocknumsitems)
401 fastblocksitems = PySequence_Fast_ITEMS(fastblocks);
402 if (!fastblocksitems)
405 for (i=0; i<self->kk; i++) {
406 if (!PyInt_Check(fastblocknumsitems[i])) {
407 PyErr_Format(py_fec_error, "Precondition violation: second argument is required to contain int.");
410 tmpl = PyInt_AsLong(fastblocknumsitems[i]);
411 if (tmpl < 0 || tmpl > 255) {
412 PyErr_Format(py_fec_error, "Precondition violation: block nums can't be less than zero or greater than 255. %ld\n", tmpl);
415 cblocknums[i] = (unsigned)tmpl;
416 if (cblocknums[i] >= self->kk)
419 if (!PyObject_CheckReadBuffer(fastblocksitems[i])) {
420 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);
423 if (PyObject_AsReadBuffer(fastblocksitems[i], (const void**)&(cblocks[i]), &sz))
425 if (oldsz != 0 && oldsz != sz) {
426 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);
432 /* Move src packets into position. At the end of this loop we want the i'th
433 element of the arrays to be the block with block number i, if that block
434 is among our inputs. */
435 for (i=0; i<self->kk;) {
436 if (cblocknums[i] >= self->kk || cblocknums[i] == i)
439 /* put pkt in the right position. */
440 unsigned c = cblocknums[i];
442 SWAP (cblocknums[i], cblocknums[c], int);
443 SWAP (cblocks[i], cblocks[c], const gf*);
444 SWAP (fastblocksitems[i], fastblocksitems[c], PyObject*);
448 /* Allocate space for all of the recovered blocks. */
449 for (i=0; i<needtorecover; i++) {
450 recoveredpystrs[i] = PyString_FromStringAndSize(NULL, sz);
451 if (recoveredpystrs[i] == NULL)
453 recoveredcstrs[i] = (gf*)PyString_AsString(recoveredpystrs[i]);
454 if (recoveredcstrs[i] == NULL)
458 /* Decode any recovered blocks that are needed. */
459 fec_decode(self->fec_matrix, cblocks, recoveredcstrs, cblocknums, sz);
461 /* Wrap up both original primary blocks and decoded blocks into a Python list of Python strings. */
462 result = PyList_New(self->kk);
465 for (i=0; i<self->kk; i++) {
466 if (cblocknums[i] == i) {
467 /* Original primary block. */
468 Py_INCREF(fastblocksitems[i]);
469 if (PyList_SetItem(result, i, fastblocksitems[i]) == -1) {
470 Py_DECREF(fastblocksitems[i]);
474 /* Recovered block. */
475 if (PyList_SetItem(result, i, recoveredpystrs[nextrecoveredix]) == -1)
477 recoveredpystrs[nextrecoveredix] = NULL;
484 for (i=0; i<self->kk; i++)
485 Py_XDECREF(recoveredpystrs[i]);
486 Py_XDECREF(result); result = NULL;
488 Py_XDECREF(fastblocks); fastblocks=NULL;
489 Py_XDECREF(fastblocknums); fastblocknums=NULL;
494 Decoder_dealloc(Decoder * self) {
495 fec_free(self->fec_matrix);
496 self->ob_type->tp_free((PyObject*)self);
499 static PyMethodDef Decoder_methods[] = {
500 {"decode", (PyCFunction)Decoder_decode, METH_VARARGS, Decoder_decode__doc__},
504 static PyMemberDef Decoder_members[] = {
505 {"k", T_SHORT, offsetof(Encoder, kk), READONLY, "k"},
506 {"m", T_SHORT, offsetof(Encoder, mm), READONLY, "m"},
507 {NULL} /* Sentinel */
510 static PyTypeObject Decoder_type = {
511 PyObject_HEAD_INIT(NULL)
513 "_fec.Decoder", /*tp_name*/
514 sizeof(Decoder), /*tp_basicsize*/
516 (destructor)Decoder_dealloc, /*tp_dealloc*/
523 0, /*tp_as_sequence*/
531 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE, /*tp_flags*/
532 Decoder__doc__, /* tp_doc */
535 0, /* tp_richcompare */
536 0, /* tp_weaklistoffset */
539 Decoder_methods, /* tp_methods */
540 Decoder_members, /* tp_members */
544 0, /* tp_descr_get */
545 0, /* tp_descr_set */
546 0, /* tp_dictoffset */
547 (initproc)Decoder_init, /* tp_init */
549 Decoder_new, /* tp_new */
553 _hexwrite(unsigned char*s, size_t l) {
554 for (size_t i = 0; i < l; i++)
555 printf("%.2x", s[i]);
559 test_from_agl(void) {
560 unsigned char b0c[8], b1c[8];
561 unsigned char b0[8], b1[8], b2[8], b3[8], b4[8];
565 const unsigned char *blocks[3] = {b0, b1, b2};
566 unsigned char *outblocks[2] = {b3, b4};
567 unsigned block_nums[] = {3, 4};
569 /*printf("_from_c before encoding:\n");
570 printf("b0: "); _hexwrite(b0, 8); printf(", ");
571 printf("b1: "); _hexwrite(b1, 8); printf(", ");
572 printf("b2: "); _hexwrite(b2, 8); printf(", ");
575 fec_t *const fec = fec_new(3, 5);
576 fec_encode(fec, blocks, outblocks, block_nums, 2, 8);
578 /*printf("after encoding:\n");
579 printf("b3: "); _hexwrite(b3, 8); printf(", ");
580 printf("b4: "); _hexwrite(b4, 8); printf(", ");
583 memcpy(b0c, b0, 8); memcpy(b1c, b1, 8);
585 const unsigned char *inpkts[] = {b3, b4, b2};
586 unsigned char *outpkts[] = {b0, b1};
587 unsigned indexes[] = {3, 4, 2};
589 fec_decode(fec, inpkts, outpkts, indexes, 8);
591 /*printf("after decoding:\n");
592 printf("b0: "); _hexwrite(b0, 8); printf(", ");
593 printf("b1: "); _hexwrite(b1, 8);
596 if ((memcmp(b0, b0c,8) == 0) && (memcmp(b1, b1c,8) == 0))
602 static PyMethodDef fec_functions[] = {
603 {"test_from_agl", test_from_agl, METH_NOARGS, NULL},
607 #ifndef PyMODINIT_FUNC /* declarations for DLL import/export */
608 #define PyMODINIT_FUNC void
613 PyObject *module_dict;
615 if (PyType_Ready(&Encoder_type) < 0)
617 if (PyType_Ready(&Decoder_type) < 0)
620 module = Py_InitModule3("_fec", fec_functions, fec__doc__);
624 Py_INCREF(&Encoder_type);
625 Py_INCREF(&Decoder_type);
627 PyModule_AddObject(module, "Encoder", (PyObject *)&Encoder_type);
628 PyModule_AddObject(module, "Decoder", (PyObject *)&Decoder_type);
630 module_dict = PyModule_GetDict(module);
631 py_fec_error = PyErr_NewException("_fec.Error", NULL, NULL);
632 PyDict_SetItemString(module_dict, "Error", py_fec_error);
636 * originally inspired by fecmodule.c by the Mnet Project, especially Myers
637 * Carpenter and Hauke Johannknecht