1 /** \file rs_fec.c \brief Reed-Solomon FEC
2 *
3 * $Author: peltotal $ $Date: 2007/02/28 08:58:00 $ $Revision: 1.37 $
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 <memory.h>
37 #include <assert.h>
38
39 #include "rs_fec.h"
40 #include "fec.h"
41
rs_fec_encode_src_block(char * data,unsigned long long len,unsigned int sbn,unsigned short es_len,int rs,unsigned int max_sb_len)42 trans_block_t* rs_fec_encode_src_block(char *data, unsigned long long len, unsigned int sbn,
43 unsigned short es_len, int rs, unsigned int max_sb_len) {
44
45 trans_block_t *tr_block; /* transport block struct */
46 trans_unit_t *tr_unit; /* transport unit struct */
47 unsigned int i; /* loop variables */
48 char *ptr; /* pointer to left data */
49 void *code;
50 char *src[GF_SIZE];
51 unsigned int k; /* number of source symbols */
52 unsigned int n; /* number of encoding symbols */
53 unsigned int max_k;
54 unsigned int max_n;
55 unsigned long long data_left;
56 div_t div_k;
57 div_t div_max_n;
58 div_t div_n;
59
60 data_left = len;
61 max_k = max_sb_len;
62
63 div_k = div((unsigned int)len, es_len);
64
65 if(div_k.rem == 0) {
66 k = (unsigned int)div_k.quot;
67 }
68 else {
69 k = (unsigned int)div_k.quot + 1;
70 }
71
72 div_max_n = div((max_k * (100 + rs)), 100);
73 max_n = (unsigned int)div_max_n.quot;
74
75 div_n = div((k * max_n), (max_k));
76 n = (unsigned int)div_n.quot;
77
78 code = fec_new(k, n);
79 tr_block = create_block();
80
81 if(tr_block == NULL) {
82 return tr_block;
83 }
84
85 tr_unit = create_units(n);
86
87 if(tr_unit == NULL) {
88 free(tr_block);
89 return NULL;
90 }
91
92 ptr = data;
93
94 tr_block->unit_list = tr_unit;
95 tr_block->sbn = sbn;
96 tr_block->n = n;
97
98 tr_block->k = k;
99 tr_block->max_k = max_k;
100 tr_block->max_n = max_n;
101
102 for(i = 0; i < k; i++) {
103 tr_unit->esi = i;
104 tr_unit->len = data_left < es_len ? (unsigned short)data_left : es_len;
105
106 /* Alloc memory for TU data */
107 if(!(tr_unit->data = (char*)calloc(es_len, sizeof(char)))) {
108 printf("Could not alloc memory for transport unit's data!\n");
109
110 tr_unit = tr_block->unit_list;
111
112 while(tr_unit != NULL) {
113 free(tr_unit->data);
114 tr_unit++;
115 }
116
117 free(tr_block->unit_list);
118 free(tr_block);
119 return NULL;
120 }
121
122 memcpy(tr_unit->data, ptr, tr_unit->len);
123
124 src[i] = tr_unit->data;
125
126 ptr += tr_unit->len;
127 data_left -= tr_unit->len;
128 tr_unit++;
129 }
130 /* let's create FEC units */
131
132 for (i = 0; i < (n - k); i++) {
133
134 tr_unit->esi = k+i;
135 tr_unit->len = es_len;
136
137 /* Alloc memory for TU data */
138 if(!(tr_unit->data = (char*)calloc(es_len, sizeof(char)))) {
139 printf("Could not alloc memory for transport unit's data!\n");
140
141 tr_unit = tr_block->unit_list;
142
143 while(tr_unit != NULL) {
144 free(tr_unit->data);
145 tr_unit++;
146 }
147
148 free(tr_block->unit_list);
149 free(tr_block);
150 return NULL;
151 }
152
153 fec_encode(code, (void**)src, tr_unit->data, k+i, es_len);
154
155 tr_unit++;
156 }
157 fec_free(code);
158
159 return tr_block;
160 }
161
rs_fec_decode_src_block(trans_block_t * tr_block,unsigned long long * block_len,unsigned short es_len)162 char *rs_fec_decode_src_block(trans_block_t *tr_block, unsigned long long *block_len,
163 unsigned short es_len) {
164
165 char *buf = NULL; /* buffer where to construct the source block from data units */
166 trans_unit_t *next_tu;
167 trans_unit_t *tu;
168
169 unsigned long long len;
170 void *code;
171 char *dst[GF_SIZE];
172 int index[GF_SIZE];
173 unsigned int i = 0;
174 unsigned int k;
175 unsigned int n;
176 div_t div_n;
177
178 k = tr_block->k;
179
180 div_n = div((k * tr_block->max_n), tr_block->max_k);
181 n = (unsigned int)div_n.quot;
182
183 len = es_len*tr_block->k;
184
185 code = fec_new(k, n);
186
187 /* Allocate memory for buf */
188 if(!(buf = (char*)calloc((unsigned int)(len + 1), sizeof(char)))) {
189 printf("Could not alloc memory for buf!\n");
190 *block_len = 0;
191 return NULL;
192 }
193
194 next_tu = tr_block->unit_list;
195
196 while(next_tu != NULL) {
197
198 tu = next_tu;
199 dst[i] = tu->data;
200 index[i] = tu->esi;
201
202 next_tu = tu->next;
203 i++;
204 }
205
206 /* Let's decode source block using Reed-Solomon FEC */
207
208 fec_decode(code, (void**)dst, index, es_len);
209
210 fec_free(code);
211
212 /* Copy decoded encoding symbols to buffer */
213
214 for(i = 0; i < k; i++) {
215 memcpy(buf + i*es_len, dst[i], es_len);
216 }
217
218 next_tu = tr_block->unit_list;
219
220 #ifndef USE_RETRIEVE_UNIT
221 while(next_tu != NULL) {
222 tu = next_tu;
223 free(tu->data);
224 tu->data = NULL;
225 next_tu = tu->next;
226 }
227 #endif
228
229 *block_len = len;
230
231 return buf;
232 }
233
234
235
rs_fec_decode_object(trans_obj_t * to,unsigned long long * data_len,alc_session_t * s)236 char *rs_fec_decode_object(trans_obj_t *to, unsigned long long *data_len, alc_session_t *s) {
237
238 char *object = NULL; /* buffer where to construct the object */
239 char *block = NULL; /* buffer where to contruct the object */
240
241 trans_block_t *tb;
242
243 unsigned long long len;
244 unsigned long long position;
245 unsigned long long to_data_left;
246 unsigned long long block_len;
247 unsigned int i;
248
249 /* Allocate memory for object */
250 if(!(object = (char*)calloc((unsigned int)(to->len + 1), sizeof(char)))) {
251 printf("Could not alloc memory for object!\n");
252 *data_len = 0;
253 return NULL;
254 }
255
256 position = 0;
257 to_data_left = to->len;
258
259 tb = to->block_list;
260
261 /*while(tb != NULL) {*/
262 for(i = 0; i < to->bs->N; i++) {
263 block = rs_fec_decode_src_block(tb, &block_len, (unsigned short)to->es_len);
264
265 /* the last packet of the last source block might be padded with zeros */
266 len = to_data_left < block_len ? to_data_left : block_len;
267
268 assert(0 <= position);
269 assert(position < to->len+1);
270 assert(len <= (to->len-position));
271
272 memcpy(object+(unsigned int)position, block, (unsigned int)len);
273 position += len;
274 to_data_left -= len;
275
276 free(block);
277 block = NULL;
278
279 /*tb = tb->next;*/
280 tb = to->block_list+(i+1);
281 }
282
283 *data_len = to->len;
284 return object;
285 }
286