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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  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.1
Committed:	Sun Feb 8 06:02:44 2004 UTC (20 years, 4 months ago) by pcg
Content type:	text/plain
Branch:	MAIN
CVS Tags:	rel-1_9, rel-1_8, ROHC-IMPORT-2004-02-08, VPE_1_6, rel-1_7, VPE-1_6_1
Log Message:	* empty log message *
#	User	Rev	Content
1	pcg	1.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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 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