1 |
/* |
2 |
ROHC Project 2003 at Lulea University of Technology, Sweden. |
3 |
Authors: Andreas Vernersson <andver-8@student.luth.se> |
4 |
Daniel Pettersson <danpet-7@student.luth.se> |
5 |
Erik Soderstrom <soderstrom@yahoo.com> |
6 |
Fredrik Lindstrom <frelin-9@student.luth.se> |
7 |
Johan Stenmark <johste-8@student.luth.se> |
8 |
Martin Juhlin <juhlin@users.sourceforge.net> |
9 |
Mikael Larsson <larmik-9@student.luth.se> |
10 |
Robert Maxe <robmax-1@student.luth.se> |
11 |
|
12 |
Copyright (C) 2003 Andreas Vernersson, Daniel Pettersson, |
13 |
Erik Soderström, Fredrik Lindström, Johan Stenmark, |
14 |
Martin Juhlin, Mikael Larsson, Robert Maxe. |
15 |
|
16 |
This program is free software; you can redistribute it and/or modify |
17 |
it under the terms of the GNU General Public License as published by |
18 |
the Free Software Foundation; either version 2 of the License, or |
19 |
(at your option) any later version. |
20 |
|
21 |
This program is distributed in the hope that it will be useful, |
22 |
but WITHOUT ANY WARRANTY; without even the implied warranty of |
23 |
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
24 |
GNU General Public License for more details. |
25 |
|
26 |
You should have received a copy of the GNU General Public License |
27 |
along with this program; if not, write to the Free Software |
28 |
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA |
29 |
*/ |
30 |
/*************************************************************************** |
31 |
* File: util.c * |
32 |
* Description: utility functions for the compressor * |
33 |
* * |
34 |
***************************************************************************/ |
35 |
|
36 |
#include "rohc.h" |
37 |
#include "comp.h" |
38 |
#include "c_util.h" |
39 |
|
40 |
void c_ack_remove(struct sc_wlsb * s, int index, int time); |
41 |
|
42 |
///////////////////////////////////////////////////////////////////// |
43 |
// W-LSB: Window base - Least Significant Bits encoding |
44 |
|
45 |
/* Removes (deallocates) a struct of window based LSB encoding |
46 |
* Param s : the struct |
47 |
*/ |
48 |
void c_destroy_wlsb(struct sc_wlsb *s) |
49 |
{ |
50 |
if (s) { |
51 |
if (s->window) |
52 |
kfree(s->window); |
53 |
kfree(s); |
54 |
} |
55 |
} |
56 |
|
57 |
|
58 |
/* Create a new WLSB instance (and allocate memory for it) |
59 |
* Param bits : number of maximum bits for representing a value |
60 |
* Param windowWidth : number of entrys in the window |
61 |
* Param p : bit calculation algorithm modifying parameter, specific for the |
62 |
* profile. |
63 |
* Returns : the allocated struct, NULL if failure |
64 |
*/ |
65 |
|
66 |
struct sc_wlsb *c_create_wlsb(int bits, int windowWidth, int p) |
67 |
{ |
68 |
int i; |
69 |
struct sc_wlsb * s = kmalloc(sizeof(struct sc_wlsb),GFP_ATOMIC); |
70 |
|
71 |
if(!s) { |
72 |
rohc_debugf(0, "c_create_wlsb(): no mem for wlsb\n"); |
73 |
return NULL; |
74 |
} |
75 |
|
76 |
s->oldest = 0; |
77 |
s->next = 0; |
78 |
s->windowWidth = windowWidth; |
79 |
|
80 |
s->window = (struct sc_window *)kmalloc(sizeof(struct sc_window)*windowWidth, GFP_ATOMIC); |
81 |
if (!s->window) { |
82 |
kfree(s); |
83 |
rohc_debugf(0, "c_create_wlsb(): no mem for window\n"); |
84 |
return NULL; |
85 |
} |
86 |
|
87 |
s->bits = bits; |
88 |
s->p = p; |
89 |
for(i = 0; i < windowWidth; i++){ |
90 |
s->window[i].time = -1; |
91 |
s->window[i].used = ROHC_FALSE; |
92 |
} |
93 |
|
94 |
return s; |
95 |
} |
96 |
|
97 |
// debug function |
98 |
void print_wlsb_stats(struct sc_wlsb * s) |
99 |
{ |
100 |
int i; |
101 |
if (!s) |
102 |
return; |
103 |
|
104 |
for(i = 0; i < s->windowWidth; i++) { |
105 |
if (s->window[i].used) { |
106 |
rohc_debugf(2, "window[%d].sn = %d, .time = %d, .value = %d\n", i, s->window[i].sn, s->window[i].time, s->window[i].value); |
107 |
} |
108 |
} |
109 |
|
110 |
rohc_debugf(0, "oldest entry has number %d\n", s->oldest); |
111 |
rohc_debugf(0, " and is (sn) %d\n", s->window[s->oldest].sn); |
112 |
rohc_debugf(0, "Next entry has number %d, oldest entry has number %d\n", s->next, s->oldest); |
113 |
} |
114 |
|
115 |
/* Adds a value (inserts an entry) to a window |
116 |
* Param s : the window |
117 |
* Param sn : the sequence number for the package (entry) |
118 |
* Param time : the time stamp for the package |
119 |
* Param value : the value to base the LSB coding on (i.e. sn) |
120 |
*/ |
121 |
void c_add_wlsb(struct sc_wlsb * s, int sn, int time, int value) |
122 |
{ |
123 |
if (!s) |
124 |
return; |
125 |
if(s->window[s->next].used) s->oldest++; // if window is full and an entry is overwritten |
126 |
s->window[s->next].sn = sn; |
127 |
s->window[s->next].time = time; |
128 |
s->window[s->next].value = value; |
129 |
s->window[s->next].used = ROHC_TRUE; |
130 |
s->next++; |
131 |
if(s->next >= s->windowWidth) s->next = 0; |
132 |
if(s->oldest >= s->windowWidth) s->oldest = 0; |
133 |
} |
134 |
|
135 |
|
136 |
/* Finds the interval [vref-p, v_ref+(2^k-1)-p] for given k |
137 |
* Part of the LSB calculation algorithm |
138 |
*/ |
139 |
static void f(int v_ref, int k, int p, int * min, int * max) |
140 |
{ |
141 |
*min = v_ref - p; |
142 |
*max = v_ref + ((1 << k) - 1) - p; // (1 << k) = 2 to the power of k |
143 |
} |
144 |
|
145 |
/* Find minimum k so that v falls into the interval f(v_ref, k) |
146 |
* Part of the LSB calculation algorithm |
147 |
*/ |
148 |
static int g(int v_ref, int v, int p, int bits) |
149 |
{ |
150 |
int k, min, max; |
151 |
for(k = 0; k < bits; k++){ |
152 |
f(v_ref, k, p, &min, &max); |
153 |
if( (v <= max) && (v >= min) ) break; |
154 |
} |
155 |
return k; |
156 |
} |
157 |
|
158 |
/* This is the function that is called when calculation of the LSB is desired. |
159 |
* Calculates the minimum number bits of the value that is required to uniquely |
160 |
* be able to create it given the window. |
161 |
* Param s : the window |
162 |
* Param value : the value to encode |
163 |
* Returns : the number of bits required to recreate the value uniquely |
164 |
*/ |
165 |
int c_get_k_wlsb(struct sc_wlsb * s, int value) |
166 |
{ |
167 |
int i, k, min, max, tmp, valid; |
168 |
if (!s) |
169 |
return 0; |
170 |
min = 0x7fffffff; |
171 |
max = 0x80000000; |
172 |
valid = 0; |
173 |
for(i = 0; i < s->windowWidth; i++){ |
174 |
if(!s->window[i].used) continue; |
175 |
valid = 1; |
176 |
tmp = s->window[i].value; |
177 |
if( tmp < min ) min = tmp; |
178 |
if( tmp > max ) max = tmp; |
179 |
} |
180 |
if(valid){ |
181 |
k = g(min, value, s->p, s->bits); |
182 |
tmp = g(max, value, s->p, s->bits); |
183 |
if( tmp > k ) k = tmp; |
184 |
} else return -1; // return -1 if no k match |
185 |
return k; |
186 |
} |
187 |
|
188 |
/* Acknowledge based on the sequence number. Removes all entries older than the given sn. |
189 |
* Param s : the window |
190 |
* Param sn : the sequence number |
191 |
*/ |
192 |
void c_ack_sn_wlsb(struct sc_wlsb * s, int sn) |
193 |
{ |
194 |
int i, found; |
195 |
found = 0; |
196 |
if (!s) |
197 |
return; |
198 |
/* if(s->next == 0){ |
199 |
i = s->windowWidth - 1; |
200 |
} else i = s->next - 1;*/ |
201 |
for(i = s->oldest; i < s->windowWidth; i++){ |
202 |
if((s->window[i].used == ROHC_TRUE) && (s->window[i].sn == sn)){ |
203 |
found = 1; |
204 |
break; |
205 |
} |
206 |
} |
207 |
if(!found){ |
208 |
for(i = 0; (i < s->oldest); i++){ |
209 |
if((s->window[i].used == ROHC_TRUE) && (s->window[i].sn == sn)){ |
210 |
found = 1; |
211 |
break; |
212 |
} |
213 |
} |
214 |
} |
215 |
if(s->oldest == i) return; |
216 |
if(!found) return; |
217 |
c_ack_remove(s, i, 0); |
218 |
} |
219 |
|
220 |
/* Acknowledge based on the time stamp. Removes all entries older than the given time stamp. |
221 |
* Param s : the window |
222 |
* Param time : the time stamp |
223 |
*/ |
224 |
void c_ack_time_wlsb(struct sc_wlsb * s, int time) |
225 |
{ |
226 |
int i, found; |
227 |
if (!s) |
228 |
return; |
229 |
found = 0; |
230 |
/* if(s->next == 0){ |
231 |
i = s->windowWidth - 1; |
232 |
} else i = s->next - 1;*/ |
233 |
for(i = s->oldest; i < s->windowWidth; i++){ |
234 |
if((s->window[i].used == ROHC_TRUE) && (s->window[i].time <= time)){ |
235 |
if(s->window[i].time < time) i++; |
236 |
if(i >= s->windowWidth) i = 0; |
237 |
found = 1; |
238 |
break; |
239 |
} |
240 |
} |
241 |
if(!found){ |
242 |
for(i = 0; i < s->oldest; i++){ |
243 |
if((s->window[i].used == ROHC_TRUE) && (s->window[i].time <= time)){ |
244 |
found = 1; |
245 |
break; |
246 |
} |
247 |
} |
248 |
} |
249 |
if(!found) return; |
250 |
c_ack_remove(s, i, 1); |
251 |
} |
252 |
|
253 |
/* Removes elements from the window. Removes all entries prior to index. |
254 |
* Param s : the window |
255 |
* Param index : the position to set as oldest |
256 |
* Param time : flag to see if called by sn or time ack |
257 |
*/ |
258 |
void c_ack_remove(struct sc_wlsb * s, int index, int time) |
259 |
{ |
260 |
|
261 |
int j; |
262 |
if (!s) |
263 |
return; |
264 |
rohc_debugf(2, "c_ack_remove(): Index is %d\n", index); |
265 |
if(s->oldest == index){ |
266 |
s->window[s->oldest].time = -1; |
267 |
s->window[s->oldest].used = ROHC_FALSE; |
268 |
}else if(s->oldest < index){ // remove all entries from oldest to (not including) index |
269 |
for(j = s->oldest; j < index; j++){ |
270 |
s->window[j].time = -1; |
271 |
s->window[j].used = ROHC_FALSE; |
272 |
} |
273 |
} else { // remove all entries from oldest to wrap-around, and all from start to (excluding) index |
274 |
for(j = s->oldest; j < s->windowWidth; j++){ |
275 |
s->window[j].time = -1; |
276 |
s->window[j].used = ROHC_FALSE; |
277 |
} |
278 |
for(j = 0; j < index; j++){ |
279 |
s->window[j].time = -1; |
280 |
s->window[j].used = ROHC_FALSE; |
281 |
} |
282 |
} |
283 |
if(index >= (s->windowWidth - 1)){ |
284 |
s->oldest = index; |
285 |
/*if(time)*/ s->oldest = 0; |
286 |
} else { |
287 |
s->oldest = index; |
288 |
if(s->oldest >= s->windowWidth) s->oldest = 0; |
289 |
} |
290 |
s->next = s->oldest; |
291 |
for(j = s->oldest; j < s->windowWidth; j++){ |
292 |
if(s->window[j].used == ROHC_TRUE){ |
293 |
s->next = ( s->next+1 ) % s->windowWidth; |
294 |
} else { |
295 |
break; |
296 |
} |
297 |
} |
298 |
for(j = 0; j < s->oldest; j++){ |
299 |
if(s->window[j].used == ROHC_TRUE){ |
300 |
s->next = ( s->next+1 ) % s->windowWidth; |
301 |
} else { |
302 |
break; |
303 |
} |
304 |
} |
305 |
if(s->oldest >= s->windowWidth) s->oldest = 0; |
306 |
} |
307 |
|
308 |
/* Calculates the sum of the value for all the entries in the window. |
309 |
* Used for statistics |
310 |
*/ |
311 |
int c_sum_wlsb(struct sc_wlsb *s) { |
312 |
int i; |
313 |
int sum=0; |
314 |
|
315 |
for (i=0; i<s->windowWidth; i++) { |
316 |
if (s->window[i].used) { |
317 |
sum += s->window[i].value; |
318 |
} |
319 |
} |
320 |
|
321 |
return sum; |
322 |
} |
323 |
|
324 |
/* Calculates the mean of the value for all the entries in the window. |
325 |
* Used for statistics |
326 |
*/ |
327 |
int c_mean_wlsb(struct sc_wlsb *s) { |
328 |
int i; |
329 |
int sum=0; |
330 |
int num=0; |
331 |
|
332 |
for (i=0; i<s->windowWidth; i++) { |
333 |
if (s->window[i].used) { |
334 |
sum += s->window[i].value; |
335 |
num++; |
336 |
} |
337 |
} |
338 |
|
339 |
if (num > 0) |
340 |
return sum/num; |
341 |
|
342 |
return sum; |
343 |
} |
344 |
|
345 |
|
346 |
///////////////////////////////////////////////////////////////////// |
347 |
// SDVL: Self Described Variable Length encoding |
348 |
|
349 |
/* Calculates how many bytes that are needed to represent the value with sdvl : |
350 |
* self-described variable length. |
351 |
* Param value : the value |
352 |
* Returns : number of bytes needed to represent the given value with sdvl. |
353 |
*/ |
354 |
int c_bytesSdvl(int value) |
355 |
{ |
356 |
if(value <= 127) return 1; |
357 |
if(value <= 16383) return 2; |
358 |
if(value <= 2097151) return 3; |
359 |
if(value <= 536870911) return 4; |
360 |
return 5; |
361 |
} |
362 |
|
363 |
/* Encode a value using sdvl (self-described variable length). |
364 |
* Param *dest : the destination to write the result to. |
365 |
* Param value : the value to encode. |
366 |
* Returns : true if success, false if failure (due to value |
367 |
* greater than 2^29). |
368 |
*/ |
369 |
boolean c_encodeSdvl(unsigned char *dest, int value) |
370 |
{ |
371 |
int tmp; |
372 |
if (!dest) |
373 |
return ROHC_FALSE; |
374 |
tmp = c_bytesSdvl(value); |
375 |
if( tmp > 4 ) return ROHC_FALSE; |
376 |
if( tmp == 4 ){ |
377 |
*dest++ = ((7 << 5) ^ ((value >> 24) & 31)) & 255; // 7 = bit pattern 111 |
378 |
*dest++ = (value >> 16) & 255; |
379 |
*dest++ = (value >> 8) & 255; |
380 |
*dest = value & 255; |
381 |
} else if( tmp == 3 ){ |
382 |
*dest++ = ((6 << 5) ^ ((value >> 16) & 31)) & 255; // 6 = bit pattern 110 |
383 |
*dest++ = (value >> 8) & 255; |
384 |
*dest = value & 255; |
385 |
} else if( tmp == 2 ){ |
386 |
*dest++ = ((2 << 6) ^ ((value >> 8)& 63)) & 255; // 2 = bit pattern 10 |
387 |
*dest = value & 255; |
388 |
} else if( tmp == 1 ){ |
389 |
*dest = value & 255; |
390 |
} |
391 |
return ROHC_TRUE; |
392 |
} |
393 |
|
394 |
|
395 |
///////////////////////////////////////////////////////////////////// |
396 |
// CRC |
397 |
|
398 |
/* Tables to enable fast CRC computations */ |
399 |
static unsigned char crc_table_8[256]; |
400 |
static unsigned char crc_table_7[256]; |
401 |
static unsigned char crc_table_3[256]; |
402 |
|
403 |
/* Get the polynom for the crc type |
404 |
* Param type : the CRC type |
405 |
* Returns : the polynom for the requested type |
406 |
*/ |
407 |
int crc_get_polynom(int type) |
408 |
{ |
409 |
if(type == CRC_TYPE_3) return 0x6; |
410 |
if(type == CRC_TYPE_7) return 0x79; |
411 |
if(type == CRC_TYPE_8) return 0xe0; |
412 |
return 0; |
413 |
} |
414 |
|
415 |
/* Initialize a table given a 256 bytes table and the polynom to use */ |
416 |
void crc_init_table(unsigned char *table, unsigned char poly) { |
417 |
unsigned char crc; |
418 |
int i,j; |
419 |
|
420 |
for (i=0; i<256; i++) { |
421 |
crc = i; |
422 |
for (j=0; j<8; j++) { |
423 |
if (crc & 1) |
424 |
crc = (crc>>1) ^ poly; |
425 |
else |
426 |
crc = (crc>>1); |
427 |
} |
428 |
table[i] = crc; |
429 |
} |
430 |
} |
431 |
|
432 |
/* Optimized CRC-8 calculation using the table */ |
433 |
inline unsigned char crc_calc_8(unsigned char *buf, int size) { |
434 |
int i; |
435 |
unsigned char crc = 0xff; |
436 |
for (i=0; i<size; i++) { |
437 |
crc = crc_table_8[buf[i]^crc]; |
438 |
} |
439 |
return crc; |
440 |
} |
441 |
|
442 |
/* Optimized CRC-7 calculation using the table */ |
443 |
inline unsigned char crc_calc_7(unsigned char *buf, int size) { |
444 |
int i; |
445 |
unsigned char crc = 0x7f; |
446 |
for (i=0; i<size; i++) { |
447 |
crc = crc_table_7[buf[i]^(crc&127)]; |
448 |
} |
449 |
return crc; |
450 |
} |
451 |
|
452 |
/* Optimized CRC-3 calculation using the table */ |
453 |
inline unsigned char crc_calc_3(unsigned char *buf, int size) { |
454 |
int i; |
455 |
unsigned char crc = 0x7; |
456 |
for (i=0; i<size; i++) { |
457 |
crc = crc_table_3[buf[i]^(crc&7)]; |
458 |
} |
459 |
return crc; |
460 |
} |
461 |
|
462 |
/* Calculates the checksym for the given data. |
463 |
* Param type : the CRC type (CRC_TYPE_3, CRC_TYPE_7 or CRC_TYPE_8) |
464 |
* Param data : the data to calculate the checksum on |
465 |
* Param length : the length of the data |
466 |
* Returns : the checksum |
467 |
*/ |
468 |
|
469 |
unsigned int crc_calculate(int type, unsigned char *data, int length) { |
470 |
switch (type) { |
471 |
case CRC_TYPE_8: return crc_calc_8(data, length); |
472 |
case CRC_TYPE_7: return crc_calc_7(data, length); |
473 |
case CRC_TYPE_3: return crc_calc_3(data, length); |
474 |
} |
475 |
return 0; |
476 |
} |
477 |
|
478 |
/**********************************************************/ |
479 |
|
480 |
/*Function for setting a addcid value when using small cids*/ |
481 |
unsigned char c_add_cid(int cid){ |
482 |
unsigned char ret_value = 0xe0; |
483 |
ret_value |= (cid & 0x0f); |
484 |
return ret_value; |
485 |
} |
486 |
|
487 |
/* Function that sets the cid_values it will set the cids proper in the |
488 |
pointer dest, the function takes a pointer called first_position where you get the position |
489 |
to place your first byte, the second byte can be placed in the value that this function returns. |
490 |
*/ |
491 |
int code_cid_values(struct sc_context *context,unsigned char *dest,int max_size,int *first_position) |
492 |
{ |
493 |
int counter = 0; |
494 |
//small cid |
495 |
if(!(context->compressor->large_cid)){ |
496 |
if(context->cid > 0){ |
497 |
dest[counter] = c_add_cid(context->cid); |
498 |
*first_position = 1; |
499 |
counter = 2; |
500 |
|
501 |
} |
502 |
else{ |
503 |
*first_position = 0; |
504 |
counter = 1; |
505 |
} |
506 |
|
507 |
return counter; //return 0 if cid ==0 and small_cid |
508 |
} |
509 |
//large cid |
510 |
else{ |
511 |
*first_position = 0; |
512 |
counter++; |
513 |
c_encodeSdvl(&dest[counter],context->cid); |
514 |
counter += c_bytesSdvl(context->cid); |
515 |
return counter; |
516 |
} |
517 |
} |
518 |
|
519 |
|
520 |
///////////////////////////////////////////////////////////////////// |
521 |
|