2 * zfec -- fast forward error correction library with Python interface
6 #include <structmember.h>
9 #if (PY_VERSION_HEX < 0x02050000)
10 typedef int Py_ssize_t;
17 static PyObject *py_fec_error;
19 static char fec__doc__[] = "\
20 FEC - Forward Error Correction \n\
23 static char Encoder__doc__[] = "\
24 Hold static encoder state (an in-memory table for matrix multiplication), and k and m parameters, and provide {encode()} method.\n\n\
25 @param k: the number of packets required for reconstruction \n\
26 @param m: the number of packets generated \n\
41 Encoder_new(PyTypeObject *type, PyObject *args, PyObject *kwdict) {
44 self = (Encoder*)type->tp_alloc(type, 0);
48 self->fec_matrix = NULL;
51 return (PyObject *)self;
55 Encoder_init(Encoder *self, PyObject *args, PyObject *kwdict) {
56 static char *kwlist[] = {
62 if (!PyArg_ParseTupleAndKeywords(args, kwdict, "ii:Encoder.__init__", kwlist, &ink, &inm))
66 PyErr_Format(py_fec_error, "Precondition violation: first argument is required to be greater than or equal to 1, but it was %d", ink);
70 PyErr_Format(py_fec_error, "Precondition violation: second argument is required to be greater than or equal to 1, but it was %d", inm);
74 PyErr_Format(py_fec_error, "Precondition violation: second argument is required to be less than or equal to 256, but it was %d", inm);
78 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);
81 self->kk = (short)ink;
82 self->mm = (short)inm;
83 self->fec_matrix = fec_new(self->kk, self->mm);
88 static char Encoder_encode__doc__[] = "\
89 Encode data into m packets.\n\
91 @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\
92 @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\
93 @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\
97 Encoder_encode(Encoder *self, PyObject *args) {
99 PyObject* desired_blocks_nums = NULL; /* The blocknums of the blocks that should be returned. */
100 PyObject* result = NULL;
102 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). */
103 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). */
104 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. */
105 const gf** incblocks = (const gf**)alloca(self->kk * sizeof(const gf*));
106 unsigned num_desired_blocks;
107 PyObject* fast_desired_blocks_nums = NULL;
108 PyObject** fast_desired_blocks_nums_items;
109 unsigned* c_desired_blocks_nums = (unsigned*)alloca(self->mm * sizeof(unsigned));
110 unsigned* c_desired_checkblocks_ids = (unsigned*)alloca((self->mm - self->kk) * sizeof(unsigned));
112 PyObject* fastinblocks = NULL;
113 PyObject** fastinblocksitems;
114 Py_ssize_t sz, oldsz = 0;
115 unsigned char check_block_index = 0; /* index into the check_blocks_produced and (parallel) pystrs_produced arrays */
117 if (!PyArg_ParseTuple(args, "O|O:Encoder.encode", &inblocks, &desired_blocks_nums))
120 for (i=0; i<self->mm - self->kk; i++)
121 pystrs_produced[i] = NULL;
122 if (desired_blocks_nums) {
123 fast_desired_blocks_nums = PySequence_Fast(desired_blocks_nums, "Second argument (optional) was not a sequence.");
124 if (!fast_desired_blocks_nums)
126 num_desired_blocks = PySequence_Fast_GET_SIZE(fast_desired_blocks_nums);
127 fast_desired_blocks_nums_items = PySequence_Fast_ITEMS(fast_desired_blocks_nums);
128 for (i=0; i<num_desired_blocks; i++) {
129 if (!PyInt_Check(fast_desired_blocks_nums_items[i])) {
130 PyErr_Format(py_fec_error, "Precondition violation: second argument is required to contain int.");
133 c_desired_blocks_nums[i] = PyInt_AsLong(fast_desired_blocks_nums_items[i]);
134 if (c_desired_blocks_nums[i] >= self->kk)
135 num_check_blocks_produced++;
138 num_desired_blocks = self->mm;
139 for (i=0; i<num_desired_blocks; i++)
140 c_desired_blocks_nums[i] = i;
141 num_check_blocks_produced = self->mm - self->kk;
144 fastinblocks = PySequence_Fast(inblocks, "First argument was not a sequence.");
148 if (PySequence_Fast_GET_SIZE(fastinblocks) != self->kk) {
149 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);
153 /* Construct a C array of gf*'s of the input data. */
154 fastinblocksitems = PySequence_Fast_ITEMS(fastinblocks);
155 if (!fastinblocksitems)
158 for (i=0; i<self->kk; i++) {
159 if (!PyObject_CheckReadBuffer(fastinblocksitems[i])) {
160 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);
163 if (PyObject_AsReadBuffer(fastinblocksitems[i], (const void**)&(incblocks[i]), &sz))
165 if (oldsz != 0 && oldsz != sz) {
166 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);
172 /* Allocate space for all of the check blocks. */
174 for (i=0; i<num_desired_blocks; i++) {
175 if (c_desired_blocks_nums[i] >= self->kk) {
176 c_desired_checkblocks_ids[check_block_index] = c_desired_blocks_nums[i];
177 pystrs_produced[check_block_index] = PyString_FromStringAndSize(NULL, sz);
178 if (pystrs_produced[check_block_index] == NULL)
180 check_blocks_produced[check_block_index] = (gf*)PyString_AsString(pystrs_produced[check_block_index]);
181 if (check_blocks_produced[check_block_index] == NULL)
186 assert (check_block_index == num_check_blocks_produced);
188 /* Encode any check blocks that are needed. */
189 fec_encode(self->fec_matrix, incblocks, check_blocks_produced, c_desired_checkblocks_ids, num_check_blocks_produced, sz);
191 /* Wrap all requested blocks up into a Python list of Python strings. */
192 result = PyList_New(num_desired_blocks);
195 check_block_index = 0;
196 for (i=0; i<num_desired_blocks; i++) {
197 if (c_desired_blocks_nums[i] < self->kk) {
198 Py_INCREF(fastinblocksitems[c_desired_blocks_nums[i]]);
199 if (PyList_SetItem(result, i, fastinblocksitems[c_desired_blocks_nums[i]]) == -1) {
200 Py_DECREF(fastinblocksitems[c_desired_blocks_nums[i]]);
204 if (PyList_SetItem(result, i, pystrs_produced[check_block_index]) == -1)
206 pystrs_produced[check_block_index] = NULL;
213 for (i=0; i<num_check_blocks_produced; i++)
214 Py_XDECREF(pystrs_produced[i]);
215 Py_XDECREF(result); result = NULL;
217 Py_XDECREF(fastinblocks); fastinblocks=NULL;
218 Py_XDECREF(fast_desired_blocks_nums); fast_desired_blocks_nums=NULL;
223 Encoder_dealloc(Encoder * self) {
224 if (self->fec_matrix)
225 fec_free(self->fec_matrix);
226 self->ob_type->tp_free((PyObject*)self);
229 static PyMethodDef Encoder_methods[] = {
230 {"encode", (PyCFunction)Encoder_encode, METH_VARARGS, Encoder_encode__doc__},
234 static PyMemberDef Encoder_members[] = {
235 {"k", T_SHORT, offsetof(Encoder, kk), READONLY, "k"},
236 {"m", T_SHORT, offsetof(Encoder, mm), READONLY, "m"},
237 {NULL} /* Sentinel */
240 static PyTypeObject Encoder_type = {
241 PyObject_HEAD_INIT(NULL)
243 "_fec.Encoder", /*tp_name*/
244 sizeof(Encoder), /*tp_basicsize*/
246 (destructor)Encoder_dealloc, /*tp_dealloc*/
253 0, /*tp_as_sequence*/
261 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE, /*tp_flags*/
262 Encoder__doc__, /* tp_doc */
265 0, /* tp_richcompare */
266 0, /* tp_weaklistoffset */
269 Encoder_methods, /* tp_methods */
270 Encoder_members, /* tp_members */
274 0, /* tp_descr_get */
275 0, /* tp_descr_set */
276 0, /* tp_dictoffset */
277 (initproc)Encoder_init, /* tp_init */
279 Encoder_new, /* tp_new */
282 static char Decoder__doc__[] = "\
283 Hold static decoder state (an in-memory table for matrix multiplication), and k and m parameters, and provide {decode()} method.\n\n\
284 @param k: the number of packets required for reconstruction \n\
285 @param m: the number of packets generated \n\
300 Decoder_new(PyTypeObject *type, PyObject *args, PyObject *kwdict) {
303 self = (Decoder*)type->tp_alloc(type, 0);
307 self->fec_matrix = NULL;
310 return (PyObject *)self;
314 Decoder_init(Encoder *self, PyObject *args, PyObject *kwdict) {
315 static char *kwlist[] = {
322 if (!PyArg_ParseTupleAndKeywords(args, kwdict, "ii:Decoder.__init__", kwlist, &ink, &inm))
326 PyErr_Format(py_fec_error, "Precondition violation: first argument is required to be greater than or equal to 1, but it was %d", ink);
330 PyErr_Format(py_fec_error, "Precondition violation: second argument is required to be greater than or equal to 1, but it was %d", inm);
334 PyErr_Format(py_fec_error, "Precondition violation: second argument is required to be less than or equal to 256, but it was %d", inm);
338 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);
341 self->kk = (short)ink;
342 self->mm = (short)inm;
343 self->fec_matrix = fec_new(self->kk, self->mm);
348 #define SWAP(a,b,t) {t tmp; tmp=a; a=b; b=tmp;}
350 static char Decoder_decode__doc__[] = "\
351 Decode a list blocks into a list of segments.\n\
352 @param blocks a sequence of buffers containing block data (for best performance, make it a tuple instead of a list)\n\
353 @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\
355 @return a list of strings containing the segment data (i.e. ''.join(retval) yields a string containing the decoded data)\n\
359 Decoder_decode(Decoder *self, PyObject *args) {
360 PyObject*restrict blocks;
361 PyObject*restrict blocknums;
362 PyObject* result = NULL;
364 const gf**restrict cblocks = (const gf**restrict)alloca(self->kk * sizeof(const gf*));
365 unsigned* cblocknums = (unsigned*)alloca(self->kk * sizeof(unsigned));
366 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. */
367 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. */
369 PyObject*restrict fastblocknums = NULL;
370 PyObject*restrict fastblocks;
371 unsigned needtorecover=0;
372 PyObject** fastblocksitems;
373 PyObject** fastblocknumsitems;
374 Py_ssize_t sz, oldsz = 0;
376 unsigned nextrecoveredix=0;
378 if (!PyArg_ParseTuple(args, "OO:Decoder.decode", &blocks, &blocknums))
381 for (i=0; i<self->kk; i++)
382 recoveredpystrs[i] = NULL;
383 fastblocks = PySequence_Fast(blocks, "First argument was not a sequence.");
386 fastblocknums = PySequence_Fast(blocknums, "Second argument was not a sequence.");
390 if (PySequence_Fast_GET_SIZE(fastblocks) != self->kk) {
391 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);
394 if (PySequence_Fast_GET_SIZE(fastblocknums) != self->kk) {
395 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);
399 /* Construct a C array of gf*'s of the data and another of C ints of the blocknums. */
400 fastblocknumsitems = PySequence_Fast_ITEMS(fastblocknums);
401 if (!fastblocknumsitems)
403 fastblocksitems = PySequence_Fast_ITEMS(fastblocks);
404 if (!fastblocksitems)
407 for (i=0; i<self->kk; i++) {
408 if (!PyInt_Check(fastblocknumsitems[i])) {
409 PyErr_Format(py_fec_error, "Precondition violation: second argument is required to contain int.");
412 tmpl = PyInt_AsLong(fastblocknumsitems[i]);
413 if (tmpl < 0 || tmpl > 255) {
414 PyErr_Format(py_fec_error, "Precondition violation: block nums can't be less than zero or greater than 255. %ld\n", tmpl);
417 cblocknums[i] = (unsigned)tmpl;
418 if (cblocknums[i] >= self->kk)
421 if (!PyObject_CheckReadBuffer(fastblocksitems[i])) {
422 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);
425 if (PyObject_AsReadBuffer(fastblocksitems[i], (const void**)&(cblocks[i]), &sz))
427 if (oldsz != 0 && oldsz != sz) {
428 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);
434 /* Move src packets into position. At the end of this loop we want the i'th
435 element of the arrays to be the block with block number i, if that block
436 is among our inputs. */
437 for (i=0; i<self->kk;) {
438 if (cblocknums[i] >= self->kk || cblocknums[i] == i)
441 /* put pkt in the right position. */
442 unsigned c = cblocknums[i];
444 SWAP (cblocknums[i], cblocknums[c], int);
445 SWAP (cblocks[i], cblocks[c], const gf*);
446 SWAP (fastblocksitems[i], fastblocksitems[c], PyObject*);
450 /* Allocate space for all of the recovered blocks. */
451 for (i=0; i<needtorecover; i++) {
452 recoveredpystrs[i] = PyString_FromStringAndSize(NULL, sz);
453 if (recoveredpystrs[i] == NULL)
455 recoveredcstrs[i] = (gf*)PyString_AsString(recoveredpystrs[i]);
456 if (recoveredcstrs[i] == NULL)
460 /* Decode any recovered blocks that are needed. */
461 fec_decode(self->fec_matrix, cblocks, recoveredcstrs, cblocknums, sz);
463 /* Wrap up both original primary blocks and decoded blocks into a Python list of Python strings. */
464 result = PyList_New(self->kk);
467 for (i=0; i<self->kk; i++) {
468 if (cblocknums[i] == i) {
469 /* Original primary block. */
470 Py_INCREF(fastblocksitems[i]);
471 if (PyList_SetItem(result, i, fastblocksitems[i]) == -1) {
472 Py_DECREF(fastblocksitems[i]);
476 /* Recovered block. */
477 if (PyList_SetItem(result, i, recoveredpystrs[nextrecoveredix]) == -1)
479 recoveredpystrs[nextrecoveredix] = NULL;
486 for (i=0; i<self->kk; i++)
487 Py_XDECREF(recoveredpystrs[i]);
488 Py_XDECREF(result); result = NULL;
490 Py_XDECREF(fastblocks); fastblocks=NULL;
491 Py_XDECREF(fastblocknums); fastblocknums=NULL;
496 Decoder_dealloc(Decoder * self) {
497 if (self->fec_matrix)
498 fec_free(self->fec_matrix);
499 self->ob_type->tp_free((PyObject*)self);
502 static PyMethodDef Decoder_methods[] = {
503 {"decode", (PyCFunction)Decoder_decode, METH_VARARGS, Decoder_decode__doc__},
507 static PyMemberDef Decoder_members[] = {
508 {"k", T_SHORT, offsetof(Encoder, kk), READONLY, "k"},
509 {"m", T_SHORT, offsetof(Encoder, mm), READONLY, "m"},
510 {NULL} /* Sentinel */
513 static PyTypeObject Decoder_type = {
514 PyObject_HEAD_INIT(NULL)
516 "_fec.Decoder", /*tp_name*/
517 sizeof(Decoder), /*tp_basicsize*/
519 (destructor)Decoder_dealloc, /*tp_dealloc*/
526 0, /*tp_as_sequence*/
534 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE, /*tp_flags*/
535 Decoder__doc__, /* tp_doc */
538 0, /* tp_richcompare */
539 0, /* tp_weaklistoffset */
542 Decoder_methods, /* tp_methods */
543 Decoder_members, /* tp_members */
547 0, /* tp_descr_get */
548 0, /* tp_descr_set */
549 0, /* tp_dictoffset */
550 (initproc)Decoder_init, /* tp_init */
552 Decoder_new, /* tp_new */
556 _hexwrite(unsigned char*s, size_t l) {
557 for (size_t i = 0; i < l; i++)
558 printf("%.2x", s[i]);
563 test_from_agl(PyObject* self, PyObject* args) {
564 unsigned char b0c[8], b1c[8];
565 unsigned char b0[8], b1[8], b2[8], b3[8], b4[8];
569 const unsigned char *blocks[3] = {b0, b1, b2};
570 unsigned char *outblocks[2] = {b3, b4};
571 unsigned block_nums[] = {3, 4};
573 /*printf("_from_c before encoding:\n");
574 printf("b0: "); _hexwrite(b0, 8); printf(", ");
575 printf("b1: "); _hexwrite(b1, 8); printf(", ");
576 printf("b2: "); _hexwrite(b2, 8); printf(", ");
579 fec_t *const fec = fec_new(3, 5);
580 fec_encode(fec, blocks, outblocks, block_nums, 2, 8);
582 /*printf("after encoding:\n");
583 printf("b3: "); _hexwrite(b3, 8); printf(", ");
584 printf("b4: "); _hexwrite(b4, 8); printf(", ");
587 memcpy(b0c, b0, 8); memcpy(b1c, b1, 8);
589 const unsigned char *inpkts[] = {b3, b4, b2};
590 unsigned char *outpkts[] = {b0, b1};
591 unsigned indexes[] = {3, 4, 2};
593 fec_decode(fec, inpkts, outpkts, indexes, 8);
595 /*printf("after decoding:\n");
596 printf("b0: "); _hexwrite(b0, 8); printf(", ");
597 printf("b1: "); _hexwrite(b1, 8);
600 if ((memcmp(b0, b0c,8) == 0) && (memcmp(b1, b1c,8) == 0))
606 static PyMethodDef fec_functions[] = {
607 {"test_from_agl", test_from_agl, METH_NOARGS, NULL},
611 #ifndef PyMODINIT_FUNC /* declarations for DLL import/export */
612 #define PyMODINIT_FUNC void
617 PyObject *module_dict;
619 if (PyType_Ready(&Encoder_type) < 0)
621 if (PyType_Ready(&Decoder_type) < 0)
624 module = Py_InitModule3("_fec", fec_functions, fec__doc__);
628 Py_INCREF(&Encoder_type);
629 Py_INCREF(&Decoder_type);
631 PyModule_AddObject(module, "Encoder", (PyObject *)&Encoder_type);
632 PyModule_AddObject(module, "Decoder", (PyObject *)&Decoder_type);
634 module_dict = PyModule_GetDict(module);
635 py_fec_error = PyErr_NewException("_fec.Error", NULL, NULL);
636 PyDict_SetItemString(module_dict, "Error", py_fec_error);
640 * originally inspired by fecmodule.c by the Mnet Project, especially Myers
641 * Carpenter and Hauke Johannknecht