src/rohc/c_util.c

/*
    ROHC Project 2003 at Lulea University of Technology, Sweden.
    Authors: Andreas Vernersson <andver-8@student.luth.se>
             Daniel Pettersson <danpet-7@student.luth.se>
             Erik Soderstrom <soderstrom@yahoo.com>
             Fredrik Lindstrom <frelin-9@student.luth.se>
             Johan Stenmark <johste-8@student.luth.se>
             Martin Juhlin <juhlin@users.sourceforge.net>
             Mikael Larsson <larmik-9@student.luth.se>
             Robert Maxe <robmax-1@student.luth.se>
             
    Copyright (C) 2003 Andreas Vernersson, Daniel Pettersson, 
    Erik Soderström, Fredrik Lindström, Johan Stenmark, 
    Martin Juhlin, Mikael Larsson, Robert Maxe.  

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
*/    
/***************************************************************************
 * File:        util.c                                                     *
 * Description: utility functions for the compressor                       *
 *                                                                         *
 ***************************************************************************/

#include "rohc.h"
#include "comp.h"
#include "c_util.h"

void c_ack_remove(struct sc_wlsb * s, int index, int time);

 /////////////////////////////////////////////////////////////////////
// W-LSB: Window base - Least Significant Bits  encoding

/* Removes (deallocates) a struct of window based LSB encoding
 * Param s : the struct
 */
void c_destroy_wlsb(struct sc_wlsb *s)
{
        if (s) {
                if (s->window)
                        kfree(s->window);
                kfree(s);
        }
}


/* Create a new WLSB instance (and allocate memory for it)
 * Param bits : number of maximum bits for representing a value
 * Param windowWidth : number of entrys in the window
 * Param p : bit calculation algorithm modifying parameter, specific for the
 * profile.
 * Returns : the allocated struct, NULL if failure
 */

struct sc_wlsb *c_create_wlsb(int bits, int windowWidth, int p)
{
        int i;
        struct sc_wlsb * s = kmalloc(sizeof(struct sc_wlsb),GFP_ATOMIC);

        if(!s) {
          rohc_debugf(0, "c_create_wlsb(): no mem for wlsb\n");
          return NULL;
        }

        s->oldest = 0;
        s->next = 0;
        s->windowWidth = windowWidth;

        s->window = (struct sc_window *)kmalloc(sizeof(struct sc_window)*windowWidth, GFP_ATOMIC);
        if (!s->window) {
                kfree(s);
                rohc_debugf(0, "c_create_wlsb(): no mem for window\n");
                return NULL;
        }

        s->bits = bits;
        s->p = p;
        for(i = 0; i < windowWidth; i++){
                s->window[i].time = -1;
                s->window[i].used = ROHC_FALSE;
        }

        return s;
}

// debug function
void print_wlsb_stats(struct sc_wlsb * s)
{
        int i;
        if (!s)
          return;

        for(i = 0; i < s->windowWidth; i++) {
                if (s->window[i].used) {
                        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);
                }
        }

        rohc_debugf(0, "oldest entry has number %d\n", s->oldest);
        rohc_debugf(0, " and is (sn) %d\n", s->window[s->oldest].sn);
        rohc_debugf(0, "Next entry has number %d, oldest entry has number %d\n", s->next, s->oldest);
}

/* Adds a value (inserts an entry) to a window
 * Param s : the window
 * Param sn : the sequence number for the package (entry)
 * Param time : the time stamp for the package
 * Param value : the value to base the LSB coding on (i.e. sn)
 */
void c_add_wlsb(struct sc_wlsb * s, int sn, int time, int value)
{
        if (!s)
                return;
        if(s->window[s->next].used) s->oldest++;                // if window is full and an entry is overwritten
        s->window[s->next].sn = sn;
        s->window[s->next].time = time;
        s->window[s->next].value = value;
        s->window[s->next].used = ROHC_TRUE;
        s->next++;
        if(s->next >= s->windowWidth) s->next = 0;
        if(s->oldest >= s->windowWidth) s->oldest = 0;
}


/* Finds the interval [vref-p, v_ref+(2^k-1)-p] for given k
 * Part of the LSB calculation algorithm
 */
static void f(int v_ref, int k, int p, int * min, int * max)
{
        *min = v_ref - p;
        *max = v_ref + ((1 << k) - 1) - p;      // (1 << k) = 2 to the power of k
}

/* Find minimum k so that v falls into the interval f(v_ref, k)
 * Part of the LSB calculation algorithm
 */
static int g(int v_ref, int v, int p, int bits)
{
        int k, min, max;
        for(k = 0; k < bits; k++){
                f(v_ref, k, p, &min, &max);
                if( (v <= max) && (v >= min) ) break;
        }
        return k;
}

/* This is the function that is called when calculation of the LSB is desired.
 * Calculates the minimum number bits of the value that is required to uniquely
 * be able to create it given the window.
 * Param s : the window
 * Param value : the value to encode
 * Returns : the number of bits required to recreate the value uniquely
 */
int c_get_k_wlsb(struct sc_wlsb * s, int value)
{
        int i, k, min, max, tmp, valid;
        if (!s)
          return 0;
        min = 0x7fffffff;
        max = 0x80000000;
        valid = 0;
        for(i = 0; i < s->windowWidth; i++){
                if(!s->window[i].used) continue;
                valid = 1;
                tmp = s->window[i].value;
                if( tmp < min ) min = tmp;
                if( tmp > max ) max = tmp;
        }
        if(valid){
                k = g(min, value, s->p, s->bits);
                tmp = g(max, value, s->p, s->bits);
                if( tmp > k ) k = tmp;
        } else return -1; // return -1 if no k match
        return k;
}

/* Acknowledge based on the sequence number. Removes all entries older than the given sn.
 * Param s : the window
 * Param sn : the sequence number
 */
void c_ack_sn_wlsb(struct sc_wlsb * s, int sn)
{
        int i, found;
        found = 0;
        if (!s)
          return;
/*      if(s->next == 0){
                i = s->windowWidth - 1;
        } else i = s->next - 1;*/
        for(i = s->oldest; i < s->windowWidth; i++){
                if((s->window[i].used == ROHC_TRUE) && (s->window[i].sn == sn)){
                        found = 1;
                        break;
                }
        }
        if(!found){
                for(i = 0; (i < s->oldest); i++){
                        if((s->window[i].used == ROHC_TRUE) && (s->window[i].sn == sn)){
                                found = 1;
                                break;
                        }
                }
        }
        if(s->oldest == i) return;
        if(!found) return;
        c_ack_remove(s, i, 0);
}

/* Acknowledge based on the time stamp. Removes all entries older than the given time stamp.
 * Param s : the window
 * Param time : the time stamp
 */
void c_ack_time_wlsb(struct sc_wlsb * s, int time)
{
        int i, found;
        if (!s)
          return;
        found = 0;
/*      if(s->next == 0){
                i = s->windowWidth - 1;
        } else i = s->next - 1;*/
        for(i = s->oldest; i < s->windowWidth; i++){
                if((s->window[i].used == ROHC_TRUE) && (s->window[i].time <= time)){
                        if(s->window[i].time < time) i++;
                        if(i >= s->windowWidth) i = 0;
                        found = 1;
                        break;
                }
        }
        if(!found){
                for(i = 0; i < s->oldest; i++){
                        if((s->window[i].used == ROHC_TRUE) && (s->window[i].time <= time)){
                                found = 1;
                                break;
                        }
                }
        }
        if(!found) return;
        c_ack_remove(s, i, 1);
}

/* Removes elements from the window. Removes all entries prior to index.
 * Param s : the window
 * Param index : the position to set as oldest
 * Param time : flag to see if called by sn or time ack
 */
void c_ack_remove(struct sc_wlsb * s, int index, int time)
{

        int j;
        if (!s)
          return;
        rohc_debugf(2, "c_ack_remove(): Index is %d\n", index);
        if(s->oldest == index){
                s->window[s->oldest].time = -1;
                s->window[s->oldest].used = ROHC_FALSE;
        }else   if(s->oldest < index){  // remove all entries from oldest to (not including) index
                for(j = s->oldest; j < index; j++){
                        s->window[j].time = -1;
                        s->window[j].used = ROHC_FALSE;
                }
        } else {        // remove all entries from oldest to wrap-around, and all from start to (excluding) index
                for(j = s->oldest; j < s->windowWidth; j++){
                        s->window[j].time = -1;
                        s->window[j].used = ROHC_FALSE;
                }
                for(j = 0; j < index; j++){
                        s->window[j].time = -1;
                        s->window[j].used = ROHC_FALSE;
                }
        }
        if(index >= (s->windowWidth - 1)){
                s->oldest = index;
                /*if(time)*/ s->oldest = 0;
        } else {
                s->oldest = index;
                if(s->oldest >= s->windowWidth) s->oldest = 0;
        }
        s->next = s->oldest;
        for(j = s->oldest; j < s->windowWidth; j++){
                if(s->window[j].used == ROHC_TRUE){
                        s->next = ( s->next+1 ) % s->windowWidth;
                } else {
                        break;
                }
        }
        for(j = 0; j < s->oldest; j++){
                if(s->window[j].used == ROHC_TRUE){
                        s->next = ( s->next+1 ) % s->windowWidth;
                } else {
                        break;
                }
        }
        if(s->oldest >= s->windowWidth) s->oldest = 0;
}

/* Calculates the sum of the value for all the entries in the window.
 * Used for statistics
 */
int c_sum_wlsb(struct sc_wlsb *s) {
        int i;
        int sum=0;

        for (i=0; i<s->windowWidth; i++) {
                if (s->window[i].used) {
                        sum += s->window[i].value;
                }
        }

        return sum;
}

/* Calculates the mean of the value for all the entries in the window.
 * Used for statistics
 */
int c_mean_wlsb(struct sc_wlsb *s) {
        int i;
        int sum=0;
        int num=0;

        for (i=0; i<s->windowWidth; i++) {
                if (s->window[i].used) {
                        sum += s->window[i].value;
                        num++;
                }
        }

        if (num > 0)
                return sum/num;

        return sum;
}


/////////////////////////////////////////////////////////////////////
// SDVL: Self Described Variable Length  encoding

/* Calculates how many bytes that are needed to represent the value with sdvl :
 * self-described variable length.
 * Param value : the value
 * Returns : number of bytes needed to represent the given value with sdvl.
 */
int c_bytesSdvl(int value)
{
        if(value <= 127) return 1;
        if(value <= 16383) return 2;
        if(value <= 2097151) return 3;
        if(value <= 536870911) return 4;
        return 5;
}

/* Encode a value using sdvl (self-described variable length).
 * Param *dest : the destination to write the result to.
 * Param value : the value to encode.
 * Returns : true if success, false if failure (due to value
 * greater than 2^29).
 */
boolean c_encodeSdvl(unsigned char *dest, int value)
{
        int tmp;
        if (!dest)
          return ROHC_FALSE;
        tmp = c_bytesSdvl(value);
        if( tmp > 4 ) return ROHC_FALSE;
        if( tmp == 4 ){
                *dest++ = ((7 << 5) ^ ((value >> 24) & 31)) & 255;      // 7 = bit pattern 111
                *dest++ = (value >> 16) & 255;
                *dest++ = (value >> 8) & 255;
                *dest = value & 255;
        } else if( tmp == 3 ){
                *dest++ = ((6 << 5) ^ ((value >> 16) & 31)) & 255;      // 6 = bit pattern 110
                *dest++ = (value >> 8) & 255;
                *dest = value & 255;
        } else if( tmp == 2 ){
                *dest++ = ((2 << 6) ^ ((value >> 8)& 63)) & 255;        // 2 = bit pattern 10
                *dest = value & 255;
        } else if( tmp == 1 ){
                *dest = value & 255;
        }
        return ROHC_TRUE;
}


/////////////////////////////////////////////////////////////////////
// CRC

/* Tables to enable fast CRC computations */
static unsigned char crc_table_8[256];
static unsigned char crc_table_7[256];
static unsigned char crc_table_3[256];

/* Get the polynom for the crc type
 * Param type : the CRC type
 * Returns : the polynom for the requested type
 */
int crc_get_polynom(int type)
{
        if(type == CRC_TYPE_3) return 0x6;
        if(type == CRC_TYPE_7) return 0x79;
        if(type == CRC_TYPE_8) return 0xe0;
        return 0;
}

/* Initialize a table given a 256 bytes table and the polynom to use */
void crc_init_table(unsigned char *table, unsigned char poly) {
  unsigned char crc;
  int i,j;

  for (i=0; i<256; i++) {
    crc = i;
    for (j=0; j<8; j++) {
      if (crc & 1)
        crc = (crc>>1) ^ poly;
      else
        crc = (crc>>1);
    }
    table[i] = crc;
  }
}

/* Optimized CRC-8 calculation using the table */
inline unsigned char crc_calc_8(unsigned char *buf, int size) {
  int i;
  unsigned char crc = 0xff;
  for (i=0; i<size; i++) {
    crc = crc_table_8[buf[i]^crc];
  }
  return crc;
}

/* Optimized CRC-7 calculation using the table */
inline unsigned char crc_calc_7(unsigned char *buf, int size) {
  int i;
  unsigned char crc = 0x7f;
  for (i=0; i<size; i++) {
    crc = crc_table_7[buf[i]^(crc&127)];
  }
  return crc;
}

/* Optimized CRC-3 calculation using the table */
inline unsigned char crc_calc_3(unsigned char *buf, int size) {
  int i;
  unsigned char crc = 0x7;
  for (i=0; i<size; i++) {
    crc = crc_table_3[buf[i]^(crc&7)];
  }
  return crc;
}

/* Calculates the checksym for the given data.
 * Param type : the CRC type (CRC_TYPE_3, CRC_TYPE_7 or CRC_TYPE_8)
 * Param data : the data to calculate the checksum on
 * Param length : the length of the data
 * Returns : the checksum
 */

unsigned int crc_calculate(int type, unsigned char *data, int length) {
  switch (type) {
  case CRC_TYPE_8: return crc_calc_8(data, length);
  case CRC_TYPE_7: return crc_calc_7(data, length);
  case CRC_TYPE_3: return crc_calc_3(data, length);
  }
  return 0;
}

/**********************************************************/

/*Function for setting a addcid value when using small cids*/
unsigned char c_add_cid(int cid){
        unsigned char ret_value = 0xe0;
        ret_value |= (cid & 0x0f);
        return ret_value;
}

/* Function that sets the cid_values it will set the cids proper in the
pointer dest, the function takes a pointer called first_position where you get the position
to place your first byte, the second byte can be placed in the value that this function returns.
*/
int code_cid_values(struct sc_context *context,unsigned char *dest,int max_size,int *first_position)
{
        int counter = 0;
        //small cid
        if(!(context->compressor->large_cid)){
                if(context->cid > 0){
                        dest[counter] = c_add_cid(context->cid);
                        *first_position = 1;
                        counter = 2;

                }
                else{
                        *first_position = 0;
                        counter = 1;
                }

                return counter; //return 0 if cid ==0 and small_cid
        }
        //large cid
        else{
                *first_position = 0;
                counter++;
                c_encodeSdvl(&dest[counter],context->cid);
                counter += c_bytesSdvl(context->cid);
                return counter;
        }
}


/////////////////////////////////////////////////////////////////////

Revision:	1.2
Committed:	Tue Apr 26 00:55:56 2005 UTC (19 years, 1 month ago) by pcg
Content type:	text/plain
Branch:	MAIN
CVS Tags:	rel-2_01, rel-3_0, rel-2_2, rel-2_0, rel-2_21, rel-2_22, rel-2_25, HEAD
Changes since 1.1:	+1 -1 lines
Log Message:	* empty log message *
#	Content
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