1 /** \file xor_fec.c \brief Simple XOR FEC
2 *
3 * $Author: peltotal $ $Date: 2007/02/28 08:58:00 $ $Revision: 1.23 $
4 *
5 * MAD-ALCLIB: Implementation of ALC/LCT protocols, Compact No-Code FEC,
6 * Simple XOR FEC, Reed-Solomon FEC, and RLC Congestion Control protocol.
7 * Copyright (c) 2003-2007 TUT - Tampere University of Technology
8 * main authors/contacts: jani.peltotalo@tut.fi and sami.peltotalo@tut.fi
9 *
10 * This program is free software; you can redistribute it and/or modify
11 * it under the terms of the GNU General Public License as published by
12 * the Free Software Foundation; either version 2 of the License, or
13 * (at your option) any later version.
14 *
15 * This program is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 * GNU General Public License for more details.
19 *
20 * You should have received a copy of the GNU General Public License
21 * along with this program; if not, write to the Free Software
22 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
23 *
24 * In addition, as a special exception, TUT - Tampere University of Technology
25 * gives permission to link the code of this program with the OpenSSL library (or
26 * with modified versions of OpenSSL that use the same license as OpenSSL), and
27 * distribute linked combinations including the two. You must obey the GNU
28 * General Public License in all respects for all of the code used other than
29 * OpenSSL. If you modify this file, you may extend this exception to your version
30 * of the file, but you are not obligated to do so. If you do not wish to do so,
31 * delete this exception statement from your version.
32 */
33
34 #include <stdlib.h>
35 #include <stdio.h>
36 #include <math.h>
37 #include <memory.h>
38
39 #include "xor_fec.h"
40
xor_fec_encode_src_block(char * data,unsigned long long len,unsigned int sbn,unsigned short es_len)41 trans_block_t* xor_fec_encode_src_block(char *data, unsigned long long len,
42 unsigned int sbn, unsigned short es_len) {
43
44 trans_block_t *tr_block; /* transport block struct */
45 trans_unit_t *tr_unit; /* transport unit struct */
46 unsigned int nb_of_units; /* number of units */
47
48 unsigned int i; /* loop variables */
49 unsigned long long data_left;
50
51 char *ptr; /* pointer to left data */
52 char *parity_symb;
53 char *padded_symb;
54 int j;
55
56 data_left = len;
57
58 parity_symb = (char*)calloc(es_len, sizeof(char));
59 padded_symb = (char*)calloc(es_len, sizeof(char));
60
61 nb_of_units = (unsigned int)ceil((double)(unsigned int)len / (double)es_len);
62
63 tr_block = create_block();
64
65 if(tr_block == NULL) {
66 return tr_block;
67 }
68
69 tr_unit = create_units(nb_of_units + 1); /* One parity symbol */
70
71 if(tr_unit == NULL) {
72 free(tr_block);
73 return NULL;
74 }
75
76 ptr = data;
77
78 tr_block->unit_list = tr_unit;
79 tr_block->sbn = sbn;
80 tr_block->k = nb_of_units;
81 tr_block->n = nb_of_units + 1;
82
83 for(i = 0; i < nb_of_units; i++) {
84
85 tr_unit->esi = i;
86 tr_unit->len = data_left < es_len ? (unsigned short)data_left : es_len; /*min(es_len, data_left);*/
87
88 /* Alloc memory for TU data */
89 if(!(tr_unit->data = (char*)calloc(tr_unit->len, sizeof(char)))) {
90 printf("Could not alloc memory for transport unit's data!\n");
91
92 tr_unit = tr_block->unit_list;
93
94 while(tr_unit != NULL) {
95 free(tr_unit->data);
96 tr_unit++;
97 }
98
99 free(tr_block->unit_list);
100 free(tr_block);
101 free(parity_symb);
102 free(padded_symb);
103 return NULL;
104 }
105
106 memcpy(tr_unit->data, ptr, tr_unit->len);
107
108 memset(padded_symb, 0, es_len);
109 memcpy(padded_symb, tr_unit->data, tr_unit->len);
110
111 if(i == 0) {
112 memcpy(parity_symb, tr_unit->data, tr_unit->len);
113 }
114 else {
115 /* We need to create the parity symbol by XORing the symbols, first symbol is not XORed. */
116
117 for(j = 0; j < es_len; j++) {
118 *(parity_symb + j) = *(parity_symb + j) ^ *(padded_symb + j);
119 }
120 }
121
122 ptr += tr_unit->len;
123 data_left -= tr_unit->len;
124 tr_unit++;
125
126 if (i == (nb_of_units-1)) {
127
128 /* Now we need to add the parity symbol to the block (XOR of all other symbols). */
129
130 tr_unit->esi = i+1;
131 tr_unit->len = es_len;
132
133 /* Alloc memory for TU data */
134 if(!(tr_unit->data = (char*)calloc(es_len, sizeof(char)))) {
135 printf("Could not alloc memory for transport unit's data!\n");
136
137 tr_unit = tr_block->unit_list;
138
139 while(tr_unit != NULL) {
140 free(tr_unit->data);
141 tr_unit++;
142 }
143
144 free(tr_block->unit_list);
145 free(tr_block);
146 free(parity_symb);
147 free(padded_symb);
148 return NULL;
149 }
150
151 memcpy(tr_unit->data, parity_symb, es_len);
152 }
153 }
154
155 free(parity_symb);
156 free(padded_symb);
157
158 return tr_block;
159 }
160
xor_fec_decode_src_block(trans_block_t * tr_block,unsigned long long * block_len,unsigned short es_len)161 char *xor_fec_decode_src_block(trans_block_t *tr_block, unsigned long long *block_len,
162 unsigned short es_len) {
163
164 char *buf = NULL; /* buffer where to construct the source block from data units */
165
166 trans_unit_t *next_tu = NULL;
167 trans_unit_t *tu = NULL;
168
169 unsigned long long len = 0;
170 unsigned long long tmp = 0;
171
172 int last_esi = -1;
173 int missing_esi = -1;
174
175 char *missing_symb = NULL;
176 char *padded_symb = NULL;
177 trans_unit_t *missing_unit = NULL;
178 unsigned int j = 0;
179
180 missing_symb = (char*)calloc(es_len, sizeof(char));
181 padded_symb = (char*)calloc(es_len, sizeof(char));
182
183 memset(missing_symb, 0, es_len);
184 memset(padded_symb, 0, es_len);
185
186 len = es_len*tr_block->k;
187
188 /* Allocate memory for buf */
189 if(!(buf = (char*)calloc((unsigned int)(len + 1), sizeof(char)))) {
190 printf("Could not alloc memory for buf!\n");
191 return NULL;
192 }
193
194 tmp = 0;
195
196 /* We must first find out is there a parity symbol */
197
198 next_tu = tr_block->unit_list;
199
200 /* We must scroll to the last symbol */
201
202 while(next_tu != NULL) {
203
204 tu = next_tu;
205 next_tu = tu->next;
206 }
207
208 if(tu->esi == tr_block->k) { /* There is a parity symbol */
209
210 /* We need to find out which symbol is missing */
211
212 next_tu = tr_block->unit_list;
213
214 while(next_tu != NULL) {
215
216 tu = next_tu;
217
218 if((int)tu->esi != (last_esi + 1)) {
219 missing_esi = (tu->esi - 1);
220 break;
221 }
222
223 next_tu = tu->next;
224 last_esi = tu->esi;
225 }
226
227 /* Now we need to construct the missing symbol */
228
229 next_tu = tr_block->unit_list;
230
231 while(next_tu != NULL) {
232
233 tu = next_tu;
234
235 memset(padded_symb, 0, es_len);
236 memcpy(padded_symb, tu->data, tu->len);
237
238 for(j = 0; j < es_len; j++) {
239 *(missing_symb + j) = *(missing_symb + j) ^ *(padded_symb + j);
240 }
241
242 next_tu = tu->next;
243 }
244
245 /* Now we need to create the missing unit */
246
247 missing_unit = create_units(1);
248
249 missing_unit->data = (char*)calloc(es_len, sizeof(char));
250
251 missing_unit->esi = missing_esi;
252 memcpy(missing_unit->data, missing_symb, es_len);
253 missing_unit->len = es_len;
254
255 /* Now we need to insert the missing symbol to the block */
256
257 next_tu = tr_block->unit_list;
258
259 while(next_tu != NULL) {
260
261 tu = next_tu;
262
263 if(missing_esi == 0) { /* The first symbol was missing */
264
265 tr_block->unit_list = missing_unit;
266 missing_unit->next = tu;
267 tu->prev = missing_unit;
268 break;
269 }
270
271 if((int)tu->esi > missing_esi) { /* It was the previous symbol which was missing */
272
273 tu->prev->next = missing_unit;
274 missing_unit->prev = tu->prev;
275 missing_unit->next = tu;
276 tu->prev = missing_unit;
277 break;
278 }
279
280 next_tu = tu->next;
281 }
282
283 /* Now we need to remove the parity symbol from the block */
284
285 tu = tr_block->unit_list;
286
287 for(j = 0; j < tr_block->k; j++) {
288
289 if(tu->esi == (tr_block->k - 1)) { /* Second last symbol */
290
291 #ifndef USE_RETRIEVE_UNIT
292 free(tu->next->data);
293 free(tu->next);
294 #else
295 tu->next->used = 0;
296 #endif
297
298 tu->next = NULL;
299 break;
300 }
301
302 tu = tu->next;
303 }
304
305 next_tu = tr_block->unit_list;
306
307 }
308
309 next_tu = tr_block->unit_list;
310
311 while(next_tu != NULL) {
312
313 tu = next_tu;
314 memcpy((buf+(unsigned int)tmp), tu->data, tu->len);
315
316 #ifndef USE_RETRIEVE_UNIT
317 free(tu->data);
318 tu->data = NULL;
319 #endif
320 tmp += tu->len;
321
322 next_tu = tu->next;
323 }
324
325 *block_len = len;
326
327 free(missing_symb);
328 free(padded_symb);
329
330 return buf;
331 }
332
xor_fec_decode_object(trans_obj_t * to,unsigned long long * data_len,alc_session_t * s)333 char *xor_fec_decode_object(trans_obj_t *to, unsigned long long *data_len, alc_session_t *s) {
334
335 char *object = NULL;
336 char *block = NULL;
337
338 trans_block_t *tb;
339
340 unsigned long long to_data_left;
341 unsigned long long len;
342 unsigned long long block_len;
343 unsigned long long position;
344
345 unsigned int i;
346
347 /* Allocate memory for buf */
348 if(!(object = (char*)calloc((unsigned int)(to->len+1), sizeof(char)))) {
349 printf("Could not alloc memory for buf!\n");
350 return NULL;
351 }
352
353 to_data_left = to->len;
354
355 tb = to->block_list;
356 position = 0;
357
358 for(i = 0; i < to->bs->N; i++) {
359
360 block = xor_fec_decode_src_block(tb, &block_len, (unsigned short)to->es_len);
361
362 /* the last packet of the last source block might be padded with zeros */
363 len = to_data_left < block_len ? to_data_left : block_len;
364
365 memcpy(object+(unsigned int)position, block, (unsigned int)len);
366 position += len;
367 to_data_left -= len;
368
369 free(block);
370 tb = to->block_list+(i+1);
371 }
372
373 *data_len = to->len;
374 return object;
375 }
376
377