The following commit has been merged in the master branch: commit d2555ea376f537c7872bdae36571c24347004988 Author: Marek Lindner lindner_marek@yahoo.de Date: Wed Jan 17 18:18:22 2007 +0100
sequence structs replaced by bitarrays
diff --git a/Makefile b/Makefile index 3a6f4e3..eb98466 100644 --- a/Makefile +++ b/Makefile @@ -25,19 +25,19 @@ LDFLAGS = -lpthread UNAME=$(shell uname)
ifeq ($(UNAME),Linux) -OS_OBJ= posix-specific.o posix.o linux-specific.o linux.o allocate.o +OS_OBJ= posix-specific.o posix.o linux-specific.o linux.o allocate.o bitarray.o endif
ifeq ($(UNAME),Darwin) -OS_OBJ= posix-specific.o posix.o bsd.o allocate.o +OS_OBJ= posix-specific.o posix.o bsd.o allocate.o bitarray.o endif
ifeq ($(UNAME),FreeBSD) -OS_OBJ= posix-specific.o posix.o bsd.o allocate.o +OS_OBJ= posix-specific.o posix.o bsd.o allocate.o bitarray.o endif
ifeq ($(UNAME),OpenBSD) -OS_OBJ= posix-specific.o posix.o bsd.o allocate.o +OS_OBJ= posix-specific.o posix.o bsd.o allocate.o bitarray.o endif
all: batmand diff --git a/batman.c b/batman.c index 0de4f58..4eb263e 100644 --- a/batman.c +++ b/batman.c @@ -333,7 +333,7 @@ static void choose_gw()
-static void update_routes( struct orig_node *orig_node, struct neigh_node *neigh_node, unsigned char *hna_recv_buff, int hna_buff_len, struct batman_if *new_batman_if ) { +static void update_routes( struct orig_node *orig_node, struct neigh_node *neigh_node, unsigned char *hna_recv_buff, int hna_buff_len ) {
static char orig_str[ADDR_STR_LEN], next_str[ADDR_STR_LEN];
@@ -384,9 +384,9 @@ static void update_routes( struct orig_node *orig_node, struct neigh_node *neigh
}
- add_del_route( orig_node->orig, 32, neigh_node->addr, 0, new_batman_if->dev, new_batman_if->udp_send_sock ); + add_del_route( orig_node->orig, 32, neigh_node->addr, 0, neigh_node->if_incoming->dev, neigh_node->if_incoming->udp_send_sock );
- orig_node->batman_if = new_batman_if; + orig_node->batman_if = neigh_node->if_incoming; orig_node->router = neigh_node;
/* add new announced network(s) */ @@ -494,11 +494,10 @@ static void update_gw_list( struct orig_node *orig_node, unsigned char new_gwfla
static void debug() {
- struct list_head *forw_pos, *orig_pos, *neigh_pos, *pack_pos; + struct list_head *forw_pos, *orig_pos, *neigh_pos; struct forw_node *forw_node; struct orig_node *orig_node; struct neigh_node *neigh_node; - struct pack_node *pack_node; struct gw_node *gw_node; unsigned int batman_count = 0; static char str[ADDR_STR_LEN], str2[ADDR_STR_LEN]; @@ -554,7 +553,7 @@ static void debug() { list_for_each(orig_pos, &orig_list) { orig_node = list_entry(orig_pos, struct orig_node, list);
- if ( orig_node->router == 0 ) + if ( orig_node->router == NULL ) continue;
batman_count++; @@ -579,15 +578,6 @@ static void debug() { output( "\t\t%s (%d)\n", str, neigh_node->packet_count ); }
- if ( debug_level == 4 ) { - - list_for_each(pack_pos, &neigh_node->pack_list) { - pack_node = list_entry(pack_pos, struct pack_node, list); - output(" Sequence number: %d \n", pack_node->seqno); - } - - } - }
if ( debug_level != 4 ) @@ -614,12 +604,11 @@ static void debug() {
-int isDuplicate(unsigned int orig, unsigned short seqno) -{ - struct list_head *orig_pos, *neigh_pos, *pack_pos; +int isDuplicate( unsigned int orig, unsigned short seqno ) { + + struct list_head *orig_pos, *neigh_pos; struct orig_node *orig_node; struct neigh_node *neigh_node; - struct pack_node *pack_node;
list_for_each(orig_pos, &orig_list) { orig_node = list_entry(orig_pos, struct orig_node, list); @@ -629,14 +618,8 @@ int isDuplicate(unsigned int orig, unsigned short seqno) list_for_each(neigh_pos, &orig_node->neigh_list) { neigh_node = list_entry(neigh_pos, struct neigh_node, list);
- list_for_each(pack_pos, &neigh_node->pack_list) { - pack_node = list_entry(pack_pos, struct pack_node, list); - - if (orig_node->orig == orig && pack_node->seqno == seqno){ - return 1; - } - - } + if ( bit_status( neigh_node->seq_bits, orig_node->last_seqno, seqno ) ) + return 1;
}
@@ -647,6 +630,7 @@ int isDuplicate(unsigned int orig, unsigned short seqno) }
return 0; + }
@@ -664,14 +648,9 @@ int isBidirectionalNeigh( struct orig_node *orig_neigh_node, struct batman_if *i
void update_originator( struct orig_node *orig_node, struct packet *in, unsigned int neigh, struct batman_if *if_incoming, unsigned char *hna_recv_buff, int hna_buff_len ) {
- struct list_head *neigh_pos, *pack_pos; - struct neigh_node *neigh_node = NULL, *tmp_neigh_node; - struct pack_node *pack_node = NULL, *tmp_pack_node; - struct batman_if *max_if; - int neigh_pkts[found_ifs]; - - memset( neigh_pkts, 0, sizeof(neigh_pkts) ); - max_if = (struct batman_if *)if_list.next; /* first batman interface */ + struct list_head *neigh_pos; + struct neigh_node *neigh_node = NULL, *tmp_neigh_node, *best_neigh_node; + int max_packet_count = 0;
if ( debug_level == 4 ) @@ -684,12 +663,24 @@ void update_originator( struct orig_node *orig_node, struct packet *in, unsigned
list_for_each( neigh_pos, &orig_node->neigh_list ) { + tmp_neigh_node = list_entry(neigh_pos, struct neigh_node, list);
- if ( tmp_neigh_node->addr == neigh ) { + if ( ( tmp_neigh_node->addr == neigh ) && ( tmp_neigh_node->if_incoming == if_incoming ) ) {
neigh_node = tmp_neigh_node; - break; + + } else { + + bit_get_packet( tmp_neigh_node->seq_bits, in->seqno - orig_node->last_seqno, 0 ); + tmp_neigh_node->packet_count = bit_packet_count( tmp_neigh_node->seq_bits ); + + if ( tmp_neigh_node->packet_count > max_packet_count ) { + + max_packet_count = tmp_neigh_node->packet_count; + best_neigh_node = tmp_neigh_node; + + }
}
@@ -702,78 +693,38 @@ void update_originator( struct orig_node *orig_node, struct packet *in, unsigned
neigh_node = debugMalloc( sizeof (struct neigh_node), 6 ); INIT_LIST_HEAD(&neigh_node->list); - INIT_LIST_HEAD(&neigh_node->pack_list);
neigh_node->addr = neigh; - - neigh_node->last_ttl = debugMalloc( found_ifs * sizeof(short), 22 ); - memset( neigh_node->last_ttl, 0, found_ifs * sizeof(short) ); + neigh_node->if_incoming = if_incoming;
list_add_tail(&neigh_node->list, &orig_node->neigh_list);
- } else if ( debug_level == 4 ) - output( "Updating existing last-hop neighbour of originator\n" ); - - list_for_each(pack_pos, &neigh_node->pack_list) { - tmp_pack_node = list_entry(pack_pos, struct pack_node, list); - - if ( tmp_pack_node->seqno == in->seqno ) { - - pack_node = tmp_pack_node; - break; - - } else { - - neigh_pkts[tmp_pack_node->if_incoming->if_num]++; - - if ( neigh_pkts[tmp_pack_node->if_incoming->if_num] > neigh_pkts[max_if->if_num] ) - max_if = pack_node->if_incoming; + } else if ( debug_level == 4 ) {
- } + output( "Updating existing last-hop neighbour of originator\n" );
}
- if ( pack_node == NULL ) {
- if ( debug_level == 4 ) - output( "Creating new packet entry for last-hop neighbour of originator \n" ); - - pack_node = debugMalloc( sizeof (struct pack_node), 7 ); - INIT_LIST_HEAD(&pack_node->list); + bit_get_packet( neigh_node->seq_bits, in->seqno - orig_node->last_seqno, 1 ); + neigh_node->packet_count = bit_packet_count( neigh_node->seq_bits );
- pack_node->seqno = in->seqno; - pack_node->if_incoming = if_incoming; - list_add( &pack_node->list, &neigh_node->pack_list ); + if ( neigh_node->packet_count > max_packet_count ) {
- neigh_pkts[pack_node->if_incoming->if_num]++; - - if ( neigh_pkts[pack_node->if_incoming->if_num] > neigh_pkts[max_if->if_num] ) - max_if = pack_node->if_incoming; - - } else { - - do_log( "ERROR - duplicate packet detected while updating orginator\n", "placeholder" ); - exit(-1); + max_packet_count = neigh_node->packet_count; + best_neigh_node = neigh_node;
}
- neigh_node->last_ttl[if_incoming->if_num] = in->ttl; - neigh_node->packet_count = neigh_pkts[max_if->if_num]; - - /* update routing table */ - update_routes( orig_node, neigh_node, hna_recv_buff, hna_buff_len, max_if ); -
- /*if ( orig_node->router != neigh_node ) { + neigh_node->last_ttl = in->ttl; + neigh_node->last_aware = get_time();
- if ( ( orig_node->router == NULL ) || ( orig_node->router->packet_count < neigh_node->packet_count ) ) - update_routes( orig_node, neigh_node, hna_recv_buff, hna_buff_len, max_if ); + orig_node->last_seqno = in->seqno;
-} else {*/
- /* TODO: routing based on squence numbers -> may be other router is better now */ - - /*}*/ + /* update routing table and check for changed hna announcements */ + update_routes( orig_node, best_neigh_node, hna_recv_buff, hna_buff_len );
}
@@ -1005,11 +956,10 @@ void schedule_own_packet() {
void purge( unsigned int curr_time ) {
- struct list_head *orig_pos, *neigh_pos, *pack_pos, *orig_temp, *neigh_temp, *pack_temp; + struct list_head *orig_pos, *neigh_pos, *orig_temp, *neigh_temp; // struct list_head *gw_pos, *gw_pos_tmp; struct orig_node *orig_node; struct neigh_node *neigh_node; - struct pack_node *pack_node; // struct gw_node *gw_node; // short gw_purged = 0; static char orig_str[ADDR_STR_LEN]; @@ -1032,17 +982,7 @@ void purge( unsigned int curr_time ) { list_for_each_safe( neigh_pos, neigh_temp, &orig_node->neigh_list ) { neigh_node = list_entry(neigh_pos, struct neigh_node, list);
- /* for all packets from the orginator via this neighbours... */ - list_for_each_safe(pack_pos, pack_temp, &neigh_node->pack_list) { - pack_node = list_entry(pack_pos, struct pack_node, list); - - list_del( pack_pos ); - debugFree( pack_node, 105 ); - - } - list_del( neigh_pos ); - debugFree( neigh_node->last_ttl, 106 ); debugFree( neigh_node, 107 );
} @@ -1071,11 +1011,26 @@ void purge( unsigned int curr_time ) {
list_del( orig_pos );
- update_routes( orig_node, NULL, NULL, 0, NULL ); + update_routes( orig_node, NULL, NULL, 0 );
debugFree( orig_node->bidirect_link, 109 ); debugFree( orig_node, 110 );
+ } else { + + /* for all neighbours towards this orginator ... */ + list_for_each_safe( neigh_pos, neigh_temp, &orig_node->neigh_list ) { + neigh_node = list_entry(neigh_pos, struct neigh_node, list); + + if ( (int)( ( neigh_node->last_aware + ( 2 * TIMEOUT ) ) < curr_time ) ) { + + list_del( neigh_pos ); + debugFree( neigh_node, 108 ); + + } + + } + }
} @@ -1337,7 +1292,7 @@ int batman() if ( ((struct packet *)&in)->orig == neigh ) {
/* it is our best route towards him */ - if ( ( is_bidirectional ) && ( orig_neigh_node->router->addr == neigh ) ) { + if ( ( is_bidirectional ) && ( orig_neigh_node->router != NULL ) && ( orig_neigh_node->router->addr == neigh ) ) {
/* mark direct link on incoming interface */ schedule_forward_packet( (struct packet *)&in, 0, 1, orig_neigh_node, neigh, hna_recv_buff, hna_buff_len, if_incoming ); @@ -1347,7 +1302,7 @@ int batman()
/* if an unidirectional neighbour sends us a packet - retransmit it with unidirectional flag to tell him that we get its packets */ /* if a bidirectional neighbour sends us a packet - retransmit it with unidirectional flag if it is not our best link to it in order to prevent routing problems */ - } else if ( ( ( is_bidirectional ) && ( orig_neigh_node->router->addr != neigh ) ) || ( !is_bidirectional ) ) { + } else if ( ( ( is_bidirectional ) && ( ( orig_neigh_node->router == NULL ) || ( orig_neigh_node->router->addr != neigh ) ) ) || ( !is_bidirectional ) ) {
schedule_forward_packet( (struct packet *)&in, 1, 1, orig_neigh_node, neigh, hna_recv_buff, hna_buff_len, if_incoming );
@@ -1374,9 +1329,9 @@ int batman()
neigh_node = list_entry(neigh_pos, struct neigh_node, list);
- if ( neigh_node->addr == neigh ) { + if ( ( neigh_node->addr == neigh ) && ( neigh_node->if_incoming == if_incoming ) ) {
- if ( neigh_node->last_ttl[if_incoming->if_num] == ((struct packet *)&in)->ttl ) + if ( neigh_node->last_ttl == ((struct packet *)&in)->ttl ) forward_duplicate_packet = 1;
break; diff --git a/batman.h b/batman.h index b84ba21..32ae120 100644 --- a/batman.h +++ b/batman.h @@ -32,6 +32,7 @@ #define DIRECTLINK 0x40 #define ADDR_STR_LEN 16
+ /* * No configuration files or fancy command line switches yet * To experiment with B.A.T.M.A.N. settings change them here @@ -39,10 +40,17 @@ * Here is the stuff you may want to play with: */
-#define TTL 50 /* Time To Live of broadcast messages */ -#define TIMEOUT 60000 /* sliding window size of received orginator messages in ms */ -#define SEQ_RANGE 60 /* sliding packet range of received orginator messages in squence numbers */ #define JITTER 50 +#define TTL 50 /* Time To Live of broadcast messages */ +#define TIMEOUT 60000 /* sliding window size of received orginator messages in ms */ +#define SEQ_RANGE 64 /* sliding packet range of received orginator messages in squence numbers (should be a multiple of our word size) */ + + + +#define TYPE_OF_WORD unsigned int /* you should choose something big, if you don't want to waste cpu */ +#define NUM_WORDS ( SEQ_RANGE / ( sizeof(TYPE_OF_WORD) * 8 ) ) +#define WORD_SIZE ( sizeof(TYPE_OF_WORD) * 8 ) +
@@ -85,6 +93,7 @@ struct orig_node /* structure for orig_list maintaining nodes of unsigned char gwflags; /* flags related to gateway functions: gateway class */ unsigned char *hna_buff; int hna_buff_len; + unsigned short last_seqno; /* last known squence number */ struct list_head neigh_list; };
@@ -93,8 +102,10 @@ struct neigh_node struct list_head list; unsigned int addr; unsigned short packet_count; - unsigned short *last_ttl; /* ttl of last packet on an interface */ - struct list_head pack_list; + unsigned char last_ttl; /* ttl of last received packet */ + unsigned int last_aware; /* when last packet via this neighbour was received */ + TYPE_OF_WORD seq_bits[ NUM_WORDS ]; + struct batman_if *if_incoming; };
struct hna_node @@ -104,14 +115,6 @@ struct hna_node unsigned int netmask; };
- -struct pack_node -{ - struct list_head list; - unsigned short seqno; - struct batman_if *if_incoming; -}; - struct forw_node /* structure for forw_list maintaining packets to be send/forwarded */ { struct list_head list; @@ -169,4 +172,11 @@ void verbose_usage(void); void del_default_route(); int add_default_route();
+void bit_init( TYPE_OF_WORD *seq_bits ); +int bit_status( TYPE_OF_WORD *seq_bits, unsigned short last_seqno, unsigned short curr_seqno ); +void bit_mark( TYPE_OF_WORD *seq_bits, int n ); +void bit_shift( TYPE_OF_WORD *seq_bits, int n ); +void bit_get_packet( TYPE_OF_WORD *seq_bits, int seq_num_diff, int set_mark ); +int bit_packet_count( TYPE_OF_WORD *seq_bits ); + #endif diff --git a/bitarray.c b/bitarray.c index 9ef22a5..9ed46e1 100644 --- a/bitarray.c +++ b/bitarray.c @@ -1,108 +1,128 @@ -#include <stdio.h> /* printf() */ -#include <stdlib.h> /* malloc(), free() */ - -#define BITS_WORD unsigned int - /* you should choose something big for the BITS_WORD, - * if you don't want to waste cpu: */ - -#define BITS_USED 64 - /* should be a multiple of our word size, - * maybe 32*k, depending on our BITS_WORD */ -#define BITS_MAX_SIZE (BITS_USED/(sizeof(BITS_WORD)*8)) - /* we need an BITS_MAX_SIZE words - * to have store BITS_USED bits. */ -#define BITS_WORD_SIZE (sizeof(BITS_WORD)*8) - /* our word size */ - -/* the packet bit array. the least signifikant bit of the 0th word is the latest bit, - * the highest signifikant bit of bits[ BITS_MAX_SIZE-1 ]; is the oldest word. */ -struct bit_packet { - int last_seq; - BITS_WORD bits[ BITS_MAX_SIZE ]; -}; +/* + * Copyright (C) 2006 B.A.T.M.A.N. contributors: + * Simon Wunderlich, Axel Neumann, Marek Lindner + * This program is free software; you can redistribute it and/or + * modify it under the terms of version 2 of the GNU General Public + * License as published by the Free Software Foundation. + * + * 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 + * + */ + + + +#include <stdio.h> /* printf() */ + +#include "batman-specific.h"
-void bit_init( struct bit_packet *p); -void bit_mark( struct bit_packet *p, int n ); -void bit_shift( struct bit_packet *p, int n ); -void bit_get_packet( struct bit_packet *p, int seq_num ); -int bit_weight( struct bit_packet *p );
-/* above this is prototyping and header stuff, you might want to put this in some .h */ -/* implementation: */
/* clear the bits */ -void bit_init( struct bit_packet *p) { +void bit_init( TYPE_OF_WORD *seq_bits ) { + int i; - - p->last_seq= -1; - for (i=0; i< BITS_MAX_SIZE; i++) - p->bits[i]= 0; + + for (i=0; i< NUM_WORDS; i++) + seq_bits[i]= 0; + };
/* turn on bit on, so we can remember that we got the packet */ -void bit_mark( struct bit_packet *p, int n ) { +int bit_status( TYPE_OF_WORD *seq_bits, unsigned short last_seqno, unsigned short curr_seqno ) { + int word_offset,word_num; - - if ( n >= BITS_USED) { /* if too old, just drop it */ - printf("got old packet, dropping\n"); + + if ( curr_seqno > last_seqno || curr_seqno < last_seqno - SEQ_RANGE ) { + + return 0; + + } else { + + word_offset= ( last_seqno - curr_seqno ) % WORD_SIZE; /* which position in the selected word */ + word_num = ( last_seqno - curr_seqno ) / WORD_SIZE; /* which word */ + + if ( seq_bits[word_num] & 1<<word_offset ) /* get position status */ + return 1; + else + return 0; + + } + +} + +/* turn on bit on, so we can remember that we got the packet */ +void bit_mark( TYPE_OF_WORD *seq_bits, int n ) { + int word_offset,word_num; + + if ( n >= SEQ_RANGE ) { /* if too old, just drop it */ +// printf("got old packet, dropping\n"); return; } - printf("mark bit %d\n", n);
- word_offset= n%BITS_WORD_SIZE; /* which position in the selected word */ - word_num = n/BITS_WORD_SIZE; /* which word */ +// printf("mark bit %d\n", n); + + word_offset= n%WORD_SIZE; /* which position in the selected word */ + word_num = n/WORD_SIZE; /* which word */
- p->bits[word_num]|= 1<<word_offset; /* turn the position on */ + seq_bits[word_num]|= 1<<word_offset; /* turn the position on */ }
/* shift the packet array p by n places. */ -void bit_shift( struct bit_packet *p, int n ) { +void bit_shift( TYPE_OF_WORD *seq_bits, int n ) { int word_offset, word_num; int i;
- word_offset= n%BITS_WORD_SIZE; /* shift how much inside each word */ - word_num = n/BITS_WORD_SIZE; /* shift over how much (full) words */ + word_offset= n%WORD_SIZE; /* shift how much inside each word */ + word_num = n/WORD_SIZE; /* shift over how much (full) words */
- for ( i=BITS_MAX_SIZE-1; i>word_num; i-- ) { + for ( i=NUM_WORDS-1; i>word_num; i-- ) { /* going from old to new, so we can't overwrite the data we copy from. * - * left is high, right is low: FEDC BA98 7654 3210 - * ^^ ^^ - * vvvv - * ^^^^ = from, vvvvv =to, we'd have word_num==1 and - * word_offset==BITS_WORD_SIZE/2 in this example. + * left is high, right is low: FEDC BA98 7654 3210 + * ^^ ^^ + * vvvv + * ^^^^ = from, vvvvv =to, we'd have word_num==1 and + * word_offset==WORD_SIZE/2 in this example. * * our desired output would be: 9876 5432 1000 0000 * */ - - p->bits[i]= - (p->bits[i - word_num] << word_offset) + + + seq_bits[i]= + (seq_bits[i - word_num] << word_offset) + /* take the lower port from the left half, shift it left to its final position */ - (p->bits[i - word_num - 1] >> (BITS_WORD_SIZE-word_offset)); + (seq_bits[i - word_num - 1] >> (WORD_SIZE-word_offset)); /* and the upper part of the right half and shift it left to it's position */ /* for our example that would be: word[0] = 9800 + 0076 = 9876 */ } /* now for our last word, i==word_num, we only have the it's "left" half. that's the 1000 word in * our example.*/ - - p->bits[i]= (p->bits[i - word_num] << word_offset); - + + seq_bits[i]= (seq_bits[i - word_num] << word_offset); + /* pad the rest with 0, if there is anything */ i--;
for (; i>=0; i--) { - p->bits[i]= 0; + seq_bits[i]= 0; } }
/* print the packet array, for debugging purposes */ -void bit_print( struct bit_packet *p ) { +void bit_print( TYPE_OF_WORD *seq_bits ) { int i,j; - - printf("last sequence number: %d. of the last %d packets, we got %d:\n", p->last_seq, BITS_USED, bit_weight(p)); - for ( i=0; i<BITS_MAX_SIZE; i++ ) { - for ( j=0; j<BITS_WORD_SIZE; j++) { - printf("%d", (p->bits[i]>>j)%2 ); /* print the j position */ + +// printf("the last %d packets, we got %d:\n", SEQ_RANGE, bit_packet_count(seq_bits)); + for ( i=0; i<NUM_WORDS; i++ ) { + for ( j=0; j<WORD_SIZE; j++) { + printf("%d", (seq_bits[i]>>j)%2 ); /* print the j position */ } printf(" "); } @@ -110,94 +130,60 @@ void bit_print( struct bit_packet *p ) { }
/* receive and process one packet */ -void bit_get_packet( struct bit_packet *p, int seq_num ) { - int diff; +void bit_get_packet( TYPE_OF_WORD *seq_bits, int seq_num_diff, int set_mark ) { + int i;
- printf("processing packet %d\n", seq_num); + if (seq_num_diff < 0) { /* we already got a sequence number higher than this one, so we just mark it. this should wrap around the integer just fine */
- diff= seq_num - p->last_seq; /* get the difference between the current and the last biggest packet*/ + if ( set_mark ) + bit_mark( seq_bits, -seq_num_diff );
- if (diff < 0) { /* we already got a sequence number higher - than this one, so we just mark it. this should wrap around the integer - just fine */ - bit_mark( p, -diff); return; + }
- if (diff > BITS_USED) { /* it seems we lost a lot of bits or got manipulated, report this. */ - printf("d'oh, BIG loss (missed %d packets)!!\n", diff-1); - for (i=0; i<BITS_MAX_SIZE; i++) - p->bits[i]= 0; - p->bits[0]=1; /* we only have the latest packet */ + if (seq_num_diff > SEQ_RANGE) { /* it seems we lost a lot of bits or got manipulated, report this. */ + +// printf("d'oh, BIG loss (missed %d packets)!!\n", seq_num_diff-1); + + for (i=0; i<NUM_WORDS; i++) + seq_bits[i]= 0; + + if ( set_mark ) + seq_bits[0] = 1; /* we only have the latest packet */ + } else { - bit_shift(p, diff); - bit_mark(p, 0); - - } - p->last_seq= seq_num; /* the sequence number was bigger than the old one, so save it */ -}
-/* count the hamming weight, how many good packets did we receive? just count the 1's ... */ -int bit_weight( struct bit_packet *p ) { - int i, hamming; - BITS_WORD word; - - hamming=0; - for (i=0; i<BITS_MAX_SIZE; i++) { - word= p->bits[i]; - while (word) { - hamming+= word%2; /* get the least signifikant 1, if it's there */ - word= word>>1; /* and shift it aboard. :) */ - } - } + bit_shift(seq_bits, seq_num_diff);
- return(hamming); -} + if ( set_mark ) + bit_mark(seq_bits, 0);
-/* initializing and some testing */ -int main() { - struct bit_packet *p; - - p = (struct bit_packet *) malloc(sizeof(struct bit_packet)); /* allocate one bit array */ - bit_init(p); /* initialize it */ + }
+}
- /* this is just for testing :) */ - bit_get_packet(p, 0); - bit_print(p); - bit_get_packet(p, 1); - bit_print(p); - bit_get_packet(p, 7); - bit_print(p); - bit_get_packet(p, 5); - bit_print(p); - bit_get_packet(p, 6); - bit_print(p); - bit_get_packet(p, 35); - bit_print(p); - bit_get_packet(p, 33); - bit_print(p); - bit_get_packet(p, 2); - bit_print(p); +/* count the hamming weight, how many good packets did we receive? just count the 1's ... */ +int bit_packet_count( TYPE_OF_WORD *seq_bits ) {
- bit_get_packet(p, 127); /* we had a long, lossy time ... */ - bit_print(p); - bit_get_packet(p, 0); /* a very old packet should not bother us */ - bit_print(p); + int i, hamming = 0; + TYPE_OF_WORD word;
- /* test the wrap */ - bit_get_packet(p, (1<<(BITS_WORD_SIZE-1))-1 ); - bit_print(p); - bit_get_packet(p, (1<<(BITS_WORD_SIZE-1)) ); - bit_print(p); /* should be 110000000000.... now */ + for (i=0; i<NUM_WORDS; i++) {
+ word= seq_bits[i];
+ while (word) {
+ word &= word-1; /* see http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan */ + hamming++;
+ }
+ }
+// printf( "packets counted: %i\n", hamming ); + return(hamming);
- free(p); - return(0); }