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