everything: shotgun attempt to put PROTO_WS and PROTO_WSS across core and in modules...
[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  * \file
30  * \brief SIP-router core :: 
31  * \ingroup core
32  * Module: \ref core
33  */
34
35
36
37 #ifndef _CRC_H_
38 #define _CRC_H_
39
40 extern unsigned long int crc_32_tab[];
41 extern unsigned short int ccitt_tab[];
42 extern unsigned short int crc_16_tab[];
43
44 #endif
45
46 #include <stdio.h>
47 #include <string.h>
48 #include <stdlib.h>
49 #include "hash_func.h"
50 #include "dprint.h"
51 #include "crc.h"
52 #include "ut.h"
53
54
55 unsigned int new_hash( str call_id, str cseq_nr )
56 {
57         unsigned int hash_code = 0;
58         int i,j, k, third;
59         int ci_len, cs_len;
60         char *ci, *cs;
61
62         /* trim EoLs */
63 /*
64         ci_len = call_id.len;
65         while (ci_len && ((c=call_id.s[ci_len-1])==0 || c=='\r' || c=='\n'))
66                 ci_len--;
67         cs_len = cseq_nr.len;
68         while (cs_len && ((c=cseq_nr.s[cs_len-1])==0 || c=='\r' || c=='\n'))
69                 cs_len--;
70 */
71         trim_len( ci_len, ci, call_id );
72         trim_len( cs_len, cs, cseq_nr );
73
74         /* run the cycle from the end ... we are interested in the
75            most-right digits ... and just take the %10 value of it
76         */
77         third=(ci_len-1)/3;
78         for ( i=ci_len-1, j=2*third, k=third;
79                 k>0 ; i--, j--, k-- ) {
80                 hash_code+=crc_16_tab[(unsigned char)(*(ci+i)) /*+7*/ ]+
81                         ccitt_tab[(unsigned char)*(ci+k)+63]+
82                         ccitt_tab[(unsigned char)*(ci+j)+13];
83         }
84         for( i=0 ; i<cs_len ; i++ )
85                 //hash_code+=crc_32_tab[(cseq_nr.s[i]+hash_code)%243];
86                 hash_code+=ccitt_tab[(unsigned char)*(cs+i)+123];
87
88         /* hash_code conditioning */
89 #ifdef _BUG
90         /* not flat ... % 111b has shorter period than
91        & 111b by one and results in different distribution;
92            ( 7 % 7 == 0, 7 %7 == 1 )
93            % is used as a part of the hash function too, not only
94            for rounding; & is not flat; whoever comes up with
95            a nicer flat hash function which does not take
96            costly division is welcome; feel free to verify
97            distribution using hashtest()
98     */
99         hash_code &= (TABLE_ENTRIES-1); /* TABLE_ENTRIES = 2^k */
100 #endif
101         hash_code=hash_code%(TABLE_ENTRIES-1)+1;
102         return hash_code;
103 }
104
105
106
107 #if 0
108 int new_hash2( str call_id, str cseq_nr )
109 {
110 #define h_inc h+=v^(v>>3)
111         char* p;
112         register unsigned v;
113         register unsigned h;
114         
115         h=0;
116         
117         
118         for (p=call_id.s; p<=(call_id.s+call_id.len-4); p+=4){
119                 v=(*p<<24)+(p[1]<<16)+(p[2]<<8)+p[3];
120                 h_inc;
121         }
122         v=0;
123         for (;p<(call_id.s+call_id.len); p++){ v<<=8; v+=*p;}
124         h_inc;
125         
126         for (p=cseq_nr.s; p<=(cseq_nr.s+cseq_nr.len-4); p+=4){
127                 v=(*p<<24)+(p[1]<<16)+(p[2]<<8)+p[3];
128                 h_inc;
129         }
130         v=0;
131         for (;p<(cseq_nr.s+cseq_nr.len); p++){ v<<=8; v+=*p;}
132         h_inc;
133         
134         h=((h)+(h>>11))+((h>>13)+(h>>23));
135         return (h)&(TABLE_ENTRIES-1);
136 }
137 #endif
138
139
140
141 void hashtest_cycle( int hits[TABLE_ENTRIES+5], char *ip )
142 {
143         long int i,j,k, l;
144         int  hashv;
145         static char buf1[1024];
146         static char buf2[1024];
147         str call_id; 
148         str cseq;
149
150         call_id.s=buf1;
151         cseq.s=buf2;
152
153         for (i=987654328;i<987654328+10;i++)
154                 for (j=85296341;j<85296341+10;j++)
155                         for (k=987654;k<=987654+10;k++)
156                                 for (l=101;l<201;l++) {
157                                         call_id.len=sprintf( buf1, "%d-%d-%d@%s",(int)i,(int)j,
158                                                 (int)k, ip );
159                                         cseq.len=sprintf( buf2, "%d", (int)l );
160                                         /* printf("%s\t%s\n", buf1, buf2 ); */
161                                         hashv=hash( call_id, cseq );
162                                         hits[ hashv ]++;
163                                 }
164 }
165
166 void hashtest(void)
167 {
168         int hits[TABLE_ENTRIES+5];
169         int i;
170
171         memset( hits, 0, sizeof hits );
172         hashtest_cycle( hits, "192.168.99.100" );
173         hashtest_cycle( hits, "172.168.99.100" );
174         hashtest_cycle( hits, "142.168.99.100" );
175         for (i=0; i<TABLE_ENTRIES+5; i++)
176                 printf("[%d. %d]\n", i, hits[i] );
177         exit(0);
178 }
179