5920be05953055536599222858b46a7d7b88fd6f
[sip-router] / hash_func.c
1 /*
2  * $Id$
3  */
4
5
6 #ifndef _CRC_H_
7 #define _CRC_H_
8
9 extern unsigned long int crc_32_tab[];
10 extern unsigned short int ccitt_tab[];
11 extern unsigned short int crc_16_tab[];
12
13 #endif
14
15 #include <stdio.h>
16 #include <string.h>
17 #include <stdlib.h>
18 #include "hash_func.h"
19 #include "dprint.h"
20 #include "crc.h"
21 #include "ut.h"
22
23 #ifdef _OBSOLETED
24 int old_hash( str  call_id, str cseq_nr )
25 {
26    int  hash_code = 0;
27    int  i;
28         
29 #if 0 /*def i386*/
30    int ci_len, cs_len;
31    char *ci, *cs;
32    
33         trim_len( ci_len, ci, call_id );
34         trim_len( cs_len, cs, cseq_nr );
35
36                 int dummy1;
37                 if (call_id.len>=4){
38                         asm(
39                                 "1: \n\r"
40                                 "addl (%1), %0 \n\r"
41                                 "add $4, %1 \n\r"
42                                 "cmp %2, %1 \n\r"
43                                 "jl 1b  \n\r"
44                                 : "=r"(hash_code), "=r"(dummy1)
45                                 :  "0" (hash_code), "1"(ci),
46                                 "r"( (ci_len & (~3)) +ci)
47                         );
48                 }
49 #else
50     if ( call_id.len>0 )
51       for( i=0 ; i<call_id.len ; hash_code+=call_id.s[i++]  );
52 #endif
53
54 #if 0 /*def i386*/
55
56                 int dummy2;
57                 if (cseq_nr.len>=4){
58                         asm(
59                                 "1: \n\r"
60                                 "addl (%1), %0 \n\r"
61                                 "add $4, %1 \n\r"
62                                 "cmp %2, %1 \n\r"
63                                 "jl 1b  \n\r"
64                                 : "=r"(hash_code), "=r"(dummy2)
65                                 :  "0" (hash_code), "1"(cs),
66                                 "r"((cs_len & (~3) )+ cs)
67                         );
68                 }
69 #else
70     if ( cseq_nr.len>0 )
71       for( i=0 ; i<cseq_nr.len ; hash_code+=cseq_nr.s[i++] );
72 #endif
73         /* this is a buggy line, see bellow hot to fix it -- as this
74            code is obsoleted I dont care anymore
75         */
76    return hash_code &= (TABLE_ENTRIES-1); /* TABLE_ENTRIES = 2^k */
77 }
78
79 #endif
80
81 int new_hash( str call_id, str cseq_nr )
82 {
83         int hash_code = 0;
84         int i,j, k, third;
85         int ci_len, cs_len;
86         char *ci, *cs;
87
88         /* trim EoLs */
89 /*
90         ci_len = call_id.len;
91         while (ci_len && ((c=call_id.s[ci_len-1])==0 || c=='\r' || c=='\n'))
92                 ci_len--;
93         cs_len = cseq_nr.len;
94         while (cs_len && ((c=cseq_nr.s[cs_len-1])==0 || c=='\r' || c=='\n'))
95                 cs_len--;
96 */
97         trim_len( ci_len, ci, call_id );
98         trim_len( cs_len, cs, cseq_nr );
99
100         /* run the cycle from the end ... we are interested in the
101            most-right digits ... and just take the %10 value of it
102         */
103         third=(ci_len-1)/3;
104         for ( i=ci_len-1, j=2*third, k=third;
105                 k>0 ; i--, j--, k-- ) {
106                 hash_code+=crc_16_tab[(unsigned char)(*(ci+i)) /*+7*/ ]+
107                         ccitt_tab[*(ci+k)+63]+
108                         ccitt_tab[*(ci+j)+13];
109         }
110         for( i=0 ; i<cs_len ; i++ )
111                 //hash_code+=crc_32_tab[(cseq_nr.s[i]+hash_code)%243];
112                 hash_code+=ccitt_tab[*(cs+i)+123];
113
114         /* hash_code conditioning */
115 #ifdef _BUG
116         /* not flat ... % 111b has shorter period than
117        & 111b by one and results in different distribution;
118            ( 7 % 7 == 0, 7 %7 == 1 )
119            % is used as a part of the hash function too, not only
120            for rounding; & is not flat; whoever comes up with
121            a nicer flat hash function which does not take
122            costly division is welcome; feel free to verify
123            distribution using hashtest()
124     */
125         hash_code &= (TABLE_ENTRIES-1); /* TABLE_ENTRIES = 2^k */
126 #endif
127         hash_code=hash_code%(TABLE_ENTRIES-1)+1;
128         return hash_code;
129 }
130
131 void hashtest_cycle( int hits[TABLE_ENTRIES+5], char *ip )
132 {
133         long int i,j,k, l;
134         int  hashv;
135         static char buf1[1024];
136         static char buf2[1024];
137         str call_id; 
138         str cseq;
139
140         call_id.s=buf1;
141         cseq.s=buf2;
142
143         for (i=987654328;i<987654328+10;i++)
144                 for (j=85296341;j<85296341+10;j++)
145                         for (k=987654;k<=987654+10;k++)
146                                 for (l=101;l<201;l++) {
147                                         call_id.len=sprintf( buf1, "%d-%d-%d@%s",(int)i,(int)j,
148                                                 (int)k, ip );
149                                         cseq.len=sprintf( buf2, "%d", (int)l );
150                                         /* printf("%s\t%s\n", buf1, buf2 ); */
151                                         hashv=hash( call_id, cseq );
152                                         hits[ hashv ]++;
153                                 }
154 }
155
156 int init_hash()
157 {
158         if (TABLE_ENTRIES != (1<<10)) {
159                 LOG(L_WARN, "WARNING: hash function optimized for %d entries\n",
160                         1<<10);
161                 LOG(L_WARN, "WARNING: use of %d entries may lead "
162                         "to unflat distribution\n", TABLE_ENTRIES );
163         } else {
164                 DBG("DEBUG: hash function initialized with optimum table size\n");
165         }
166         return 1;
167 }
168
169 void hashtest()
170 {
171         int hits[TABLE_ENTRIES+5];
172         int i;
173
174         init_hash();    
175         memset( hits, 0, sizeof hits );
176         hashtest_cycle( hits, "192.168.99.100" );
177         hashtest_cycle( hits, "172.168.99.100" );
178         hashtest_cycle( hits, "142.168.99.100" );
179         for (i=0; i<TABLE_ENTRIES+5; i++)
180                 printf("[%d. %d]\n", i, hits[i] );
181         exit(0);
182 }
183