← Back to branch summary

~ubuntu-branches/ubuntu/trusty/batmand/trusty

« back to all changes in this revision

Viewing changes to bitarray.c

  • Committer: Bazaar Package Importer
  • Author(s): Holger Levsen
  • Date: 2007-11-26 09:10:49 UTC
  • Revision ID: james.westby@ubuntu.com-20071126091049-9fqg546f2c4ct759
Tags: upstream-0.2
Import upstream version 0.2

Show diffs side-by-side

added added

removed removed

Lines of Context:
bitarray.c
 
1
/*
 
2
 * Copyright (C) 2006 B.A.T.M.A.N. contributors:
 
3
 * Simon Wunderlich, Axel Neumann, Marek Lindner
 
4
 * This program is free software; you can redistribute it and/or
 
5
 * modify it under the terms of version 2 of the GNU General Public
 
6
 * License as published by the Free Software Foundation.
 
7
 *
 
8
 * This program is distributed in the hope that it will be useful, but
 
9
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 
10
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 
11
 * General Public License for more details.
 
12
 *
 
13
 * You should have received a copy of the GNU General Public License
 
14
 * along with this program; if not, write to the Free Software
 
15
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
 
16
 * 02110-1301, USA
 
17
 *
 
18
 */
 
19
 
 
20
 
 
21
 
 
22
#include <stdio.h>              /* printf() */
 
23
 
 
24
#include "bitarray.h"
 
25
#include "os.h"
 
26
 
 
27
 
 
28
 
 
29
/* clear the bits */
 
30
void bit_init( TYPE_OF_WORD *seq_bits ) {
 
31
 
 
32
        int i;
 
33
 
 
34
        for (i=0; i< NUM_WORDS; i++)
 
35
                seq_bits[i]= 0;
 
36
 
 
37
};
 
38
 
 
39
/* returns true if corresponding bit in given seq_bits indicates so and curr_seqno is within range of last_seqno */
 
40
uint8_t get_bit_status( TYPE_OF_WORD *seq_bits, uint16_t last_seqno, uint16_t curr_seqno ) {
 
41
 
 
42
        int16_t diff, word_offset, word_num;
 
43
 
 
44
        diff= last_seqno- curr_seqno;
 
45
        if ( diff < 0 || diff >= SEQ_RANGE ) {
 
46
                return 0;
 
47
 
 
48
        } else {
 
49
 
 
50
                word_offset= ( last_seqno - curr_seqno ) % WORD_BIT_SIZE;       /* which position in the selected word */
 
51
                word_num   = ( last_seqno - curr_seqno ) / WORD_BIT_SIZE;       /* which word */
 
52
 
 
53
                if ( seq_bits[word_num] & (1<<word_offset) )   /* get position status */
 
54
                        return 1;
 
55
                else
 
56
                        return 0;
 
57
 
 
58
        }
 
59
 
 
60
}
 
61
 
 
62
/* print the packet array, for debugging purposes */
 
63
static char bit_string[130];
 
64
char* bit_print( TYPE_OF_WORD *seq_bits ) {
 
65
        int i,j,k=0,b=0;
 
66
 
 
67
//      printf("the last %d packets, we got %d:\n", SEQ_RANGE, bit_packet_count(seq_bits));
 
68
        for ( i=0; i<NUM_WORDS; i++ ) {
 
69
                for ( j=0; j<WORD_BIT_SIZE; j++) {
 
70
                        bit_string[k++] = ((seq_bits[i]>>j)%2 ? '1':'0'); /* print the j position */
 
71
                        if( ++b == SEQ_RANGE ) {
 
72
                                bit_string[k++]='|';
 
73
                        }
 
74
                }
 
75
                bit_string[k++]=' ';
 
76
        }
 
77
        bit_string[k++]='\0';
 
78
//      debug_output( 4, "%s\n", bit_string);
 
79
//      printf("\n\n");
 
80
        return bit_string;
 
81
}
 
82
 
 
83
/* turn corresponding bit on, so we can remember that we got the packet */
 
84
void bit_mark( TYPE_OF_WORD *seq_bits, int32_t n ) {
 
85
        int32_t word_offset,word_num;
 
86
 
 
87
        if ( n<0 || n >= SEQ_RANGE ) {                  /* if too old, just drop it */
 
88
//              printf("got old packet, dropping\n");
 
89
                return;
 
90
        }
 
91
 
 
92
//      printf("mark bit %d\n", n);
 
93
 
 
94
        word_offset= n%WORD_BIT_SIZE;   /* which position in the selected word */
 
95
        word_num   = n/WORD_BIT_SIZE;   /* which word */
 
96
 
 
97
        seq_bits[word_num]|= 1<<word_offset;    /* turn the position on */
 
98
}
 
99
 
 
100
/* shift the packet array p by n places. */
 
101
void bit_shift( TYPE_OF_WORD *seq_bits, int32_t n ) {
 
102
        int32_t word_offset, word_num;
 
103
        int32_t i;
 
104
 
 
105
//      bit_print( seq_bits );
 
106
        if( n<=0 ) return;
 
107
 
 
108
        word_offset= n%WORD_BIT_SIZE;   /* shift how much inside each word */
 
109
        word_num   = n/WORD_BIT_SIZE;   /* shift over how much (full) words */
 
110
 
 
111
        for ( i=NUM_WORDS-1; i>word_num; i-- ) {
 
112
                /* going from old to new, so we can't overwrite the data we copy from. *
 
113
                 * left is high, right is low: FEDC BA98 7654 3210
 
114
                 *                                        ^^ ^^
 
115
                 *                             vvvv
 
116
                 * ^^^^ = from, vvvvv =to, we'd have word_num==1 and
 
117
                 * word_offset==WORD_BIT_SIZE/2 ????? in this example. (=24 bits)
 
118
                 *
 
119
                 * our desired output would be: 9876 5432 1000 0000
 
120
                 * */
 
121
 
 
122
                seq_bits[i]=
 
123
                        (seq_bits[i - word_num] << word_offset) +
 
124
                                        /* take the lower port from the left half, shift it left to its final position */
 
125
                        (seq_bits[i - word_num - 1] >>  (WORD_BIT_SIZE-word_offset));
 
126
                                        /* and the upper part of the right half and shift it left to it's position */
 
127
                /* for our example that would be: word[0] = 9800 + 0076 = 9876 */
 
128
        }
 
129
        /* now for our last word, i==word_num, we only have the it's "left" half. that's the 1000 word in
 
130
         * our example.*/
 
131
 
 
132
        seq_bits[i]= (seq_bits[i - word_num] << word_offset);
 
133
 
 
134
        /* pad the rest with 0, if there is anything */
 
135
        i--;
 
136
 
 
137
        for (; i>=0; i--) {
 
138
                seq_bits[i]= 0;
 
139
        }
 
140
//      bit_print( seq_bits );
 
141
}
 
142
 
 
143
 
 
144
/* receive and process one packet, returns 1 if received seq_num is considered new, 0 if old  */
 
145
char bit_get_packet( TYPE_OF_WORD *seq_bits, int16_t seq_num_diff, int8_t set_mark ) {
 
146
 
 
147
        int i;
 
148
 
 
149
        if ( ( seq_num_diff < 0 ) && ( seq_num_diff >= -SEQ_RANGE ) ) {  /* we already got a sequence number higher than this one, so we just mark it. this should wrap around the integer just fine */
 
150
 
 
151
                if ( set_mark )
 
152
                        bit_mark( seq_bits, -seq_num_diff );
 
153
 
 
154
                return 0;
 
155
 
 
156
        }
 
157
 
 
158
        if ( ( seq_num_diff > SEQ_RANGE ) || ( seq_num_diff < -SEQ_RANGE ) ) {        /* it seems we missed a lot of packets or the other host restarted */
 
159
 
 
160
                 if ( seq_num_diff > SEQ_RANGE )
 
161
                        debug_output( 4, "It seems we missed a lot of packets (%i) !\n",  seq_num_diff-1 );
 
162
 
 
163
                if ( -seq_num_diff > SEQ_RANGE )
 
164
                        debug_output( 4, "Other host probably restarted !\n" );
 
165
 
 
166
                for (i=0; i<NUM_WORDS; i++)
 
167
                        seq_bits[i]= 0;
 
168
 
 
169
                if ( set_mark )
 
170
                        seq_bits[0] = 1;  /* we only have the latest packet */
 
171
 
 
172
        } else {
 
173
 
 
174
                bit_shift(seq_bits, seq_num_diff);
 
175
 
 
176
                if ( set_mark )
 
177
                        bit_mark(seq_bits, 0);
 
178
 
 
179
        }
 
180
 
 
181
        return 1;
 
182
 
 
183
}
 
184
 
 
185
/* count the hamming weight, how many good packets did we receive? just count the 1's ... */
 
186
int bit_packet_count( TYPE_OF_WORD *seq_bits ) {
 
187
 
 
188
        int i, hamming = 0;
 
189
        TYPE_OF_WORD word;
 
190
 
 
191
        for (i=0; i<NUM_WORDS; i++) {
 
192
 
 
193
                word = seq_bits[i];
 
194
 
 
195
                while (word) {
 
196
 
 
197
                        word &= word-1;   /* see http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan */
 
198
                        hamming++;
 
199
 
 
200
                }
 
201
 
 
202
        }
 
203
 
 
204
        return(hamming);
 
205
 
 
206
}