Initial addittion of the BMF multicast plugin
[olsrd.git] / lib / bmf / src / PacketHistory.c
1 /*
2  * OLSR Basic Multicast Forwarding (BMF) plugin.
3  * Copyright (c) 2005, 2006, Thales Communications, Huizen, The Netherlands.
4  * Written by Erik Tromp.
5  * All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without 
8  * modification, are permitted provided that the following conditions 
9  * are met:
10  *
11  * * Redistributions of source code must retain the above copyright 
12  *   notice, this list of conditions and the following disclaimer.
13  * * Redistributions in binary form must reproduce the above copyright 
14  *   notice, this list of conditions and the following disclaimer in 
15  *   the documentation and/or other materials provided with the 
16  *   distribution.
17  * * Neither the name of Thales, BMF nor the names of its 
18  *   contributors may be used to endorse or promote products derived 
19  *   from this software without specific prior written permission.
20  *
21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND 
22  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 
23  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 
24  * IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, 
25  * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 
26  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 
27  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY 
28  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE 
29  * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 
30  * OF THE POSSIBILITY OF SUCH DAMAGE.
31  */
32
33 /* $Id: PacketHistory.c,v 1.1 2006/05/03 08:59:04 kattemat Exp $ */
34
35 #include "PacketHistory.h"
36
37 /* System includes */
38 #include <assert.h> /* assert() */
39 #include <sys/types.h> /* u_int16_t, u_int32_t */
40 #include <string.h> /* memset */
41
42 /* OLSRD includes */
43 #include "olsr.h" /* olsr_printf */
44
45 /* Plugin includes */
46 #include "Packet.h"
47
48 static u_int32_t PacketHistory[HISTORY_TABLE_SIZE];
49
50 /* Calculate 16-bits CRC according to CRC-CCITT specification, modified
51  * to leave out some parts of the packet. */
52 static u_int16_t CalcCrcCcitt(unsigned char* buffer, ssize_t len)
53 {
54   /* Initial value of 0xFFFF should be 0x1D0F according to
55    * www.joegeluso.com/software/articles/ccitt.htm */
56   u_int16_t crc = 0xFFFF; 
57   int i;
58
59   assert(buffer != NULL);
60
61   for (i = 0; i < len; i++)
62   {
63     /* Skip IP header checksum; we want to avoid as much as possible
64      * calculating a checksum over data containing a checksum */
65     if (i >= 12 && i < 14) continue;
66
67     crc  = (unsigned char)(crc >> 8) | (crc << 8);
68     crc ^= buffer[i];
69     crc ^= (unsigned char)(crc & 0xff) >> 4;
70     crc ^= (crc << 8) << 4;
71     crc ^= ((crc & 0xff) << 4) << 1;
72   }
73   return crc;
74
75 #if 0
76   /* Alternative, simpler and perhaps just as good: add source IP address,
77    * destination IP address and IP identification, in 16-bit */
78   return
79     ((buffer[0x0E] << 8) + buffer[0x0F]) + ((buffer[0x10] << 8) + buffer[0x11]) +
80     ((buffer[0x12] << 8) + buffer[0x13]) + ((buffer[0x14] << 8) + buffer[0x15]) +
81     ((buffer[0x06] << 8) + buffer[0x07]);
82 #endif
83 }
84
85 void InitPacketHistory()
86 {
87   memset(PacketHistory, 0, sizeof(PacketHistory));
88 }
89
90 /* Record the fact that this packet was seen recently */
91 void MarkRecentPacket(unsigned char* buffer, ssize_t len)
92 {
93   u_int16_t crc;
94   u_int32_t index;
95   uint offset;
96
97   assert(buffer != NULL);
98
99   /* Start CRC calculation at ethertype; skip source and destination MAC 
100    * addresses */
101   crc = CalcCrcCcitt(buffer + ETH_TYPE_OFFSET, len - ETH_TYPE_OFFSET);
102
103   index = crc / NPACKETS_PER_ENTRY;
104   assert(index < HISTORY_TABLE_SIZE);
105
106   offset = (crc % NPACKETS_PER_ENTRY) * NBITS_PER_PACKET;
107   assert(offset <= NBITS_IN_UINT32 - NBITS_PER_PACKET);
108
109   /* Mark "seen recently" */
110   PacketHistory[index] = PacketHistory[index] | (0x3u << offset);
111 }
112
113 /* Check if this packet was seen recently */
114 int CheckMarkRecentPacket(unsigned char* buffer, ssize_t len)
115 {
116   u_int16_t crc;
117   u_int32_t index;
118   uint offset;
119   u_int32_t bitMask;
120   int result;
121
122   assert(buffer != NULL);
123
124   /* Start CRC calculation at ethertype; skip source and destination MAC 
125    * addresses */
126   crc = CalcCrcCcitt(buffer + ETH_TYPE_OFFSET, len - ETH_TYPE_OFFSET);
127
128   index = crc / NPACKETS_PER_ENTRY;
129   assert(index < HISTORY_TABLE_SIZE);
130
131   offset =  (crc % NPACKETS_PER_ENTRY) * NBITS_PER_PACKET;
132   assert(offset <= NBITS_IN_UINT32 - NBITS_PER_PACKET);
133
134   bitMask = 0x1u << offset;
135   result = ((PacketHistory[index] & bitMask) == bitMask);
136   
137   /* Always mark "seen recently" */
138   PacketHistory[index] = PacketHistory[index] | (0x3u << offset);
139
140   return result;
141 }
142   
143 void PrunePacketHistory(void* useless)
144 {
145   uint i;
146   for (i = 0; i < HISTORY_TABLE_SIZE; i++)
147   {
148     if (PacketHistory[i] > 0)
149     {
150       uint j;
151       for (j = 0; j < NPACKETS_PER_ENTRY; j++)
152       {
153         uint offset = j * NBITS_PER_PACKET;
154
155         u_int32_t bitMask = 0x3u << offset;
156         u_int32_t bitsSeenRecenty = 0x3u << offset;
157         u_int32_t bitsTimingOut = 0x1u << offset;
158
159         /* 10 should never occur */
160         assert ((PacketHistory[i] & bitMask) != (0x2u << offset));
161         
162         if ((PacketHistory[i] & bitMask) == bitsSeenRecenty)
163         {
164           /* 11 -> 01 */
165           PacketHistory[i] &= ~bitMask | bitsTimingOut;
166         }
167         else if ((PacketHistory[i] & bitMask) == bitsTimingOut)
168         {
169           /* 01 -> 00 */
170           PacketHistory[i] &= ~bitMask;
171         }
172       } /* for (j = ...) */
173     } /* if (PacketHistory[i] > 0) */
174   } /* for (i = ...) */
175 }