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", ink);
69 PyErr_Format(py_fec_error, "Precondition violation: second argument is required to be greater than or equal to 1, but it was %d", inm);
73 PyErr_Format(py_fec_error, "Precondition violation: second argument is required to be less than or equal to 256, but it was %d", inm);
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 if (self->fec_matrix)
224 fec_free(self->fec_matrix);
225 self->ob_type->tp_free((PyObject*)self);
228 static PyMethodDef Encoder_methods[] = {
229 {"encode", (PyCFunction)Encoder_encode, METH_VARARGS, Encoder_encode__doc__},
233 static PyMemberDef Encoder_members[] = {
234 {"k", T_SHORT, offsetof(Encoder, kk), READONLY, "k"},
235 {"m", T_SHORT, offsetof(Encoder, mm), READONLY, "m"},
236 {NULL} /* Sentinel */
239 static PyTypeObject Encoder_type = {
240 PyObject_HEAD_INIT(NULL)
242 "_fec.Encoder", /*tp_name*/
243 sizeof(Encoder), /*tp_basicsize*/
245 (destructor)Encoder_dealloc, /*tp_dealloc*/
252 0, /*tp_as_sequence*/
260 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE, /*tp_flags*/
261 Encoder__doc__, /* tp_doc */
264 0, /* tp_richcompare */
265 0, /* tp_weaklistoffset */
268 Encoder_methods, /* tp_methods */
269 Encoder_members, /* tp_members */
273 0, /* tp_descr_get */
274 0, /* tp_descr_set */
275 0, /* tp_dictoffset */
276 (initproc)Encoder_init, /* tp_init */
278 Encoder_new, /* tp_new */
281 static char Decoder__doc__[] = "\
282 Hold static decoder state (an in-memory table for matrix multiplication), and k and m parameters, and provide {decode()} method.\n\n\
283 @param k: the number of packets required for reconstruction \n\
284 @param m: the number of packets generated \n\
299 Decoder_new(PyTypeObject *type, PyObject *args, PyObject *kwdict) {
302 self = (Decoder*)type->tp_alloc(type, 0);
306 self->fec_matrix = NULL;
309 return (PyObject *)self;
313 Decoder_init(Encoder *self, PyObject *args, PyObject *kwdict) {
314 static char *kwlist[] = {
321 if (!PyArg_ParseTupleAndKeywords(args, kwdict, "ii:Decoder.__init__", kwlist, &ink, &inm))
325 PyErr_Format(py_fec_error, "Precondition violation: first argument is required to be greater than or equal to 1, but it was %d", ink);
329 PyErr_Format(py_fec_error, "Precondition violation: second argument is required to be greater than or equal to 1, but it was %d", inm);
333 PyErr_Format(py_fec_error, "Precondition violation: second argument is required to be less than or equal to 256, but it was %d", inm);
337 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);
340 self->kk = (short)ink;
341 self->mm = (short)inm;
342 self->fec_matrix = fec_new(self->kk, self->mm);
347 #define SWAP(a,b,t) {t tmp; tmp=a; a=b; b=tmp;}
349 static char Decoder_decode__doc__[] = "\
350 Decode a list blocks into a list of segments.\n\
351 @param blocks a sequence of buffers containing block data (for best performance, make it a tuple instead of a list)\n\
352 @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\
354 @return a list of strings containing the segment data (i.e. ''.join(retval) yields a string containing the decoded data)\n\
358 Decoder_decode(Decoder *self, PyObject *args) {
359 PyObject*restrict blocks;
360 PyObject*restrict blocknums;
361 PyObject* result = NULL;
363 const gf**restrict cblocks = (const gf**restrict)alloca(self->kk * sizeof(const gf*));
364 unsigned* cblocknums = (unsigned*)alloca(self->kk * sizeof(unsigned));
365 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. */
366 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. */
368 PyObject*restrict fastblocknums = NULL;
369 PyObject*restrict fastblocks;
370 unsigned needtorecover=0;
371 PyObject** fastblocksitems;
372 PyObject** fastblocknumsitems;
373 Py_ssize_t sz, oldsz = 0;
375 unsigned nextrecoveredix=0;
377 if (!PyArg_ParseTuple(args, "OO:Decoder.decode", &blocks, &blocknums))
380 for (i=0; i<self->kk; i++)
381 recoveredpystrs[i] = NULL;
382 fastblocks = PySequence_Fast(blocks, "First argument was not a sequence.");
385 fastblocknums = PySequence_Fast(blocknums, "Second argument was not a sequence.");
389 if (PySequence_Fast_GET_SIZE(fastblocks) != self->kk) {
390 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);
393 if (PySequence_Fast_GET_SIZE(fastblocknums) != self->kk) {
394 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);
398 /* Construct a C array of gf*'s of the data and another of C ints of the blocknums. */
399 fastblocknumsitems = PySequence_Fast_ITEMS(fastblocknums);
400 if (!fastblocknumsitems)
402 fastblocksitems = PySequence_Fast_ITEMS(fastblocks);
403 if (!fastblocksitems)
406 for (i=0; i<self->kk; i++) {
407 if (!PyInt_Check(fastblocknumsitems[i])) {
408 PyErr_Format(py_fec_error, "Precondition violation: second argument is required to contain int.");
411 tmpl = PyInt_AsLong(fastblocknumsitems[i]);
412 if (tmpl < 0 || tmpl > 255) {
413 PyErr_Format(py_fec_error, "Precondition violation: block nums can't be less than zero or greater than 255. %ld\n", tmpl);
416 cblocknums[i] = (unsigned)tmpl;
417 if (cblocknums[i] >= self->kk)
420 if (!PyObject_CheckReadBuffer(fastblocksitems[i])) {
421 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);
424 if (PyObject_AsReadBuffer(fastblocksitems[i], (const void**)&(cblocks[i]), &sz))
426 if (oldsz != 0 && oldsz != sz) {
427 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);
433 /* Move src packets into position. At the end of this loop we want the i'th
434 element of the arrays to be the block with block number i, if that block
435 is among our inputs. */
436 for (i=0; i<self->kk;) {
437 if (cblocknums[i] >= self->kk || cblocknums[i] == i)
440 /* put pkt in the right position. */
441 unsigned c = cblocknums[i];
443 SWAP (cblocknums[i], cblocknums[c], int);
444 SWAP (cblocks[i], cblocks[c], const gf*);
445 SWAP (fastblocksitems[i], fastblocksitems[c], PyObject*);
449 /* Allocate space for all of the recovered blocks. */
450 for (i=0; i<needtorecover; i++) {
451 recoveredpystrs[i] = PyString_FromStringAndSize(NULL, sz);
452 if (recoveredpystrs[i] == NULL)
454 recoveredcstrs[i] = (gf*)PyString_AsString(recoveredpystrs[i]);
455 if (recoveredcstrs[i] == NULL)
459 /* Decode any recovered blocks that are needed. */
460 fec_decode(self->fec_matrix, cblocks, recoveredcstrs, cblocknums, sz);
462 /* Wrap up both original primary blocks and decoded blocks into a Python list of Python strings. */
463 result = PyList_New(self->kk);
466 for (i=0; i<self->kk; i++) {
467 if (cblocknums[i] == i) {
468 /* Original primary block. */
469 Py_INCREF(fastblocksitems[i]);
470 if (PyList_SetItem(result, i, fastblocksitems[i]) == -1) {
471 Py_DECREF(fastblocksitems[i]);
475 /* Recovered block. */
476 if (PyList_SetItem(result, i, recoveredpystrs[nextrecoveredix]) == -1)
478 recoveredpystrs[nextrecoveredix] = NULL;
485 for (i=0; i<self->kk; i++)
486 Py_XDECREF(recoveredpystrs[i]);
487 Py_XDECREF(result); result = NULL;
489 Py_XDECREF(fastblocks); fastblocks=NULL;
490 Py_XDECREF(fastblocknums); fastblocknums=NULL;
495 Decoder_dealloc(Decoder * self) {
496 if (self->fec_matrix)
497 fec_free(self->fec_matrix);
498 self->ob_type->tp_free((PyObject*)self);
501 static PyMethodDef Decoder_methods[] = {
502 {"decode", (PyCFunction)Decoder_decode, METH_VARARGS, Decoder_decode__doc__},
506 static PyMemberDef Decoder_members[] = {
507 {"k", T_SHORT, offsetof(Encoder, kk), READONLY, "k"},
508 {"m", T_SHORT, offsetof(Encoder, mm), READONLY, "m"},
509 {NULL} /* Sentinel */
512 static PyTypeObject Decoder_type = {
513 PyObject_HEAD_INIT(NULL)
515 "_fec.Decoder", /*tp_name*/
516 sizeof(Decoder), /*tp_basicsize*/
518 (destructor)Decoder_dealloc, /*tp_dealloc*/
525 0, /*tp_as_sequence*/
533 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE, /*tp_flags*/
534 Decoder__doc__, /* tp_doc */
537 0, /* tp_richcompare */
538 0, /* tp_weaklistoffset */
541 Decoder_methods, /* tp_methods */
542 Decoder_members, /* tp_members */
546 0, /* tp_descr_get */
547 0, /* tp_descr_set */
548 0, /* tp_dictoffset */
549 (initproc)Decoder_init, /* tp_init */
551 Decoder_new, /* tp_new */
555 _hexwrite(unsigned char*s, size_t l) {
556 for (size_t i = 0; i < l; i++)
557 printf("%.2x", s[i]);
562 test_from_agl(PyObject* self, PyObject* args) {
563 unsigned char b0c[8], b1c[8];
564 unsigned char b0[8], b1[8], b2[8], b3[8], b4[8];
568 const unsigned char *blocks[3] = {b0, b1, b2};
569 unsigned char *outblocks[2] = {b3, b4};
570 unsigned block_nums[] = {3, 4};
572 /*printf("_from_c before encoding:\n");
573 printf("b0: "); _hexwrite(b0, 8); printf(", ");
574 printf("b1: "); _hexwrite(b1, 8); printf(", ");
575 printf("b2: "); _hexwrite(b2, 8); printf(", ");
578 fec_t *const fec = fec_new(3, 5);
579 fec_encode(fec, blocks, outblocks, block_nums, 2, 8);
581 /*printf("after encoding:\n");
582 printf("b3: "); _hexwrite(b3, 8); printf(", ");
583 printf("b4: "); _hexwrite(b4, 8); printf(", ");
586 memcpy(b0c, b0, 8); memcpy(b1c, b1, 8);
588 const unsigned char *inpkts[] = {b3, b4, b2};
589 unsigned char *outpkts[] = {b0, b1};
590 unsigned indexes[] = {3, 4, 2};
592 fec_decode(fec, inpkts, outpkts, indexes, 8);
594 /*printf("after decoding:\n");
595 printf("b0: "); _hexwrite(b0, 8); printf(", ");
596 printf("b1: "); _hexwrite(b1, 8);
599 if ((memcmp(b0, b0c,8) == 0) && (memcmp(b1, b1c,8) == 0))
605 static PyMethodDef fec_functions[] = {
606 {"test_from_agl", test_from_agl, METH_NOARGS, NULL},
610 #ifndef PyMODINIT_FUNC /* declarations for DLL import/export */
611 #define PyMODINIT_FUNC void
616 PyObject *module_dict;
618 if (PyType_Ready(&Encoder_type) < 0)
620 if (PyType_Ready(&Decoder_type) < 0)
623 module = Py_InitModule3("_fec", fec_functions, fec__doc__);
627 Py_INCREF(&Encoder_type);
628 Py_INCREF(&Decoder_type);
630 PyModule_AddObject(module, "Encoder", (PyObject *)&Encoder_type);
631 PyModule_AddObject(module, "Decoder", (PyObject *)&Decoder_type);
633 module_dict = PyModule_GetDict(module);
634 py_fec_error = PyErr_NewException("_fec.Error", NULL, NULL);
635 PyDict_SetItemString(module_dict, "Error", py_fec_error);
639 * originally inspired by fecmodule.c by the Mnet Project, especially Myers
640 * Carpenter and Hauke Johannknecht