GPLization banner introduced to *.[hc] files
[sip-router] / hash_func.c
1 /*
2  * $Id$
3  *
4  * Copyright (C) 2001-2003 Fhg Fokus
5  *
6  * This file is part of ser, a free SIP server.
7  *
8  * ser is free software; you can redistribute it and/or modify
9  * it under the terms of the GNU General Public License as published by
10  * the Free Software Foundation; either version 2 of the License, or
11  * (at your option) any later version
12  *
13  * For a license to use the ser software under conditions
14  * other than those described here, or to purchase support for this
15  * software, please contact iptel.org by e-mail at the following addresses:
16  *    info@iptel.org
17  *
18  * ser is distributed in the hope that it will be useful,
19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
21  * GNU General Public License for more details.
22  *
23  * You should have received a copy of the GNU General Public License 
24  * along with this program; if not, write to the Free Software 
25  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
26  */
27
28
29
30 #ifndef _CRC_H_
31 #define _CRC_H_
32
33 extern unsigned long int crc_32_tab[];
34 extern unsigned short int ccitt_tab[];
35 extern unsigned short int crc_16_tab[];
36
37 #endif
38
39 #include <stdio.h>
40 #include <string.h>
41 #include <stdlib.h>
42 #include "hash_func.h"
43 #include "dprint.h"
44 #include "crc.h"
45 #include "ut.h"
46
47 #ifdef _OBSOLETED
48 int old_hash( str  call_id, str cseq_nr )
49 {
50    int  hash_code = 0;
51    int  i;
52         
53 #if 0 /*def i386*/
54    int ci_len, cs_len;
55    char *ci, *cs;
56    
57         trim_len( ci_len, ci, call_id );
58         trim_len( cs_len, cs, cseq_nr );
59
60                 int dummy1;
61                 if (call_id.len>=4){
62                         asm(
63                                 "1: \n\r"
64                                 "addl (%1), %0 \n\r"
65                                 "add $4, %1 \n\r"
66                                 "cmp %2, %1 \n\r"
67                                 "jl 1b  \n\r"
68                                 : "=r"(hash_code), "=r"(dummy1)
69                                 :  "0" (hash_code), "1"(ci),
70                                 "r"( (ci_len & (~3)) +ci)
71                         );
72                 }
73 #else
74     if ( call_id.len>0 )
75       for( i=0 ; i<call_id.len ; hash_code+=call_id.s[i++]  );
76 #endif
77
78 #if 0 /*def i386*/
79
80                 int dummy2;
81                 if (cseq_nr.len>=4){
82                         asm(
83                                 "1: \n\r"
84                                 "addl (%1), %0 \n\r"
85                                 "add $4, %1 \n\r"
86                                 "cmp %2, %1 \n\r"
87                                 "jl 1b  \n\r"
88                                 : "=r"(hash_code), "=r"(dummy2)
89                                 :  "0" (hash_code), "1"(cs),
90                                 "r"((cs_len & (~3) )+ cs)
91                         );
92                 }
93 #else
94     if ( cseq_nr.len>0 )
95       for( i=0 ; i<cseq_nr.len ; hash_code+=cseq_nr.s[i++] );
96 #endif
97         /* this is a buggy line, see bellow hot to fix it -- as this
98            code is obsoleted I dont care anymore
99         */
100    return hash_code &= (TABLE_ENTRIES-1); /* TABLE_ENTRIES = 2^k */
101 }
102
103 #endif
104
105 int new_hash( str call_id, str cseq_nr )
106 {
107         int hash_code = 0;
108         int i,j, k, third;
109         int ci_len, cs_len;
110         char *ci, *cs;
111
112         /* trim EoLs */
113 /*
114         ci_len = call_id.len;
115         while (ci_len && ((c=call_id.s[ci_len-1])==0 || c=='\r' || c=='\n'))
116                 ci_len--;
117         cs_len = cseq_nr.len;
118         while (cs_len && ((c=cseq_nr.s[cs_len-1])==0 || c=='\r' || c=='\n'))
119                 cs_len--;
120 */
121         trim_len( ci_len, ci, call_id );
122         trim_len( cs_len, cs, cseq_nr );
123
124         /* run the cycle from the end ... we are interested in the
125            most-right digits ... and just take the %10 value of it
126         */
127         third=(ci_len-1)/3;
128         for ( i=ci_len-1, j=2*third, k=third;
129                 k>0 ; i--, j--, k-- ) {
130                 hash_code+=crc_16_tab[(unsigned char)(*(ci+i)) /*+7*/ ]+
131                         ccitt_tab[*(ci+k)+63]+
132                         ccitt_tab[*(ci+j)+13];
133         }
134         for( i=0 ; i<cs_len ; i++ )
135                 //hash_code+=crc_32_tab[(cseq_nr.s[i]+hash_code)%243];
136                 hash_code+=ccitt_tab[*(cs+i)+123];
137
138         /* hash_code conditioning */
139 #ifdef _BUG
140         /* not flat ... % 111b has shorter period than
141        & 111b by one and results in different distribution;
142            ( 7 % 7 == 0, 7 %7 == 1 )
143            % is used as a part of the hash function too, not only
144            for rounding; & is not flat; whoever comes up with
145            a nicer flat hash function which does not take
146            costly division is welcome; feel free to verify
147            distribution using hashtest()
148     */
149         hash_code &= (TABLE_ENTRIES-1); /* TABLE_ENTRIES = 2^k */
150 #endif
151         hash_code=hash_code%(TABLE_ENTRIES-1)+1;
152         return hash_code;
153 }
154
155 void hashtest_cycle( int hits[TABLE_ENTRIES+5], char *ip )
156 {
157         long int i,j,k, l;
158         int  hashv;
159         static char buf1[1024];
160         static char buf2[1024];
161         str call_id; 
162         str cseq;
163
164         call_id.s=buf1;
165         cseq.s=buf2;
166
167         for (i=987654328;i<987654328+10;i++)
168                 for (j=85296341;j<85296341+10;j++)
169                         for (k=987654;k<=987654+10;k++)
170                                 for (l=101;l<201;l++) {
171                                         call_id.len=sprintf( buf1, "%d-%d-%d@%s",(int)i,(int)j,
172                                                 (int)k, ip );
173                                         cseq.len=sprintf( buf2, "%d", (int)l );
174                                         /* printf("%s\t%s\n", buf1, buf2 ); */
175                                         hashv=hash( call_id, cseq );
176                                         hits[ hashv ]++;
177                                 }
178 }
179
180 int init_hash()
181 {
182         if (TABLE_ENTRIES != (1<<10)) {
183                 LOG(L_WARN, "WARNING: hash function optimized for %d entries\n",
184                         1<<10);
185                 LOG(L_WARN, "WARNING: use of %d entries may lead "
186                         "to unflat distribution\n", TABLE_ENTRIES );
187         } else {
188                 DBG("DEBUG: hash function initialized with optimum table size\n");
189         }
190         return 1;
191 }
192
193 void hashtest()
194 {
195         int hits[TABLE_ENTRIES+5];
196         int i;
197
198         init_hash();    
199         memset( hits, 0, sizeof hits );
200         hashtest_cycle( hits, "192.168.99.100" );
201         hashtest_cycle( hits, "172.168.99.100" );
202         hashtest_cycle( hits, "142.168.99.100" );
203         for (i=0; i<TABLE_ENTRIES+5; i++)
204                 printf("[%d. %d]\n", i, hits[i] );
205         exit(0);
206 }
207