1 /*
2 * Copyright (C) 2001-2003 FhG Fokus
3 *
4 * This file is part of Kamailio, a free SIP server.
5 *
6 * Kamailio is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version
10 *
11 * Kamailio is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
19 */
20
21 /*!
22 * \file
23 * \brief Kamailio core :: Hash functions
24 * \ingroup core
25 * Module: \ref core
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
new_hash(str call_id,str cseq_nr)48 unsigned int new_hash( str call_id, str cseq_nr )
49 {
50 unsigned int hash_code = 0;
51 int i,j, k, third;
52 int ci_len, cs_len;
53 char *ci, *cs;
54
55 /* trim EoLs */
56 /*
57 ci_len = call_id.len;
58 while (ci_len && ((c=call_id.s[ci_len-1])==0 || c=='\r' || c=='\n'))
59 ci_len--;
60 cs_len = cseq_nr.len;
61 while (cs_len && ((c=cseq_nr.s[cs_len-1])==0 || c=='\r' || c=='\n'))
62 cs_len--;
63 */
64 trim_len( ci_len, ci, call_id );
65 trim_len( cs_len, cs, cseq_nr );
66
67 /* run the cycle from the end ... we are interested in the
68 most-right digits ... and just take the %10 value of it
69 */
70 third=(ci_len-1)/3;
71 for ( i=ci_len-1, j=2*third, k=third;
72 k>0 ; i--, j--, k-- ) {
73 hash_code+=crc_16_tab[(unsigned char)(*(ci+i)) /*+7*/ ]+
74 ccitt_tab[(unsigned char)*(ci+k)+63]+
75 ccitt_tab[(unsigned char)*(ci+j)+13];
76 }
77 for( i=0 ; i<cs_len ; i++ )
78 //hash_code+=crc_32_tab[(cseq_nr.s[i]+hash_code)%243];
79 hash_code+=ccitt_tab[(unsigned char)*(cs+i)+123];
80
81 /* hash_code conditioning */
82 hash_code=hash_code%(TABLE_ENTRIES-1)+1;
83 return hash_code;
84 }
85
86
87
88 #if 0
89 int new_hash2( str call_id, str cseq_nr )
90 {
91 #define h_inc h+=v^(v>>3)
92 char* p;
93 register unsigned v;
94 register unsigned h;
95
96 h=0;
97
98
99 for (p=call_id.s; p<=(call_id.s+call_id.len-4); p+=4){
100 v=(*p<<24)+(p[1]<<16)+(p[2]<<8)+p[3];
101 h_inc;
102 }
103 v=0;
104 for (;p<(call_id.s+call_id.len); p++){ v<<=8; v+=*p;}
105 h_inc;
106
107 for (p=cseq_nr.s; p<=(cseq_nr.s+cseq_nr.len-4); p+=4){
108 v=(*p<<24)+(p[1]<<16)+(p[2]<<8)+p[3];
109 h_inc;
110 }
111 v=0;
112 for (;p<(cseq_nr.s+cseq_nr.len); p++){ v<<=8; v+=*p;}
113 h_inc;
114
115 h=((h)+(h>>11))+((h>>13)+(h>>23));
116 return (h)&(TABLE_ENTRIES-1);
117 }
118 #endif
119
120
121
hashtest_cycle(int hits[TABLE_ENTRIES+5],char * ip)122 void hashtest_cycle( int hits[TABLE_ENTRIES+5], char *ip )
123 {
124 long int i,j,k, l;
125 int hashv;
126 static char buf1[1024];
127 static char buf2[1024];
128 str call_id;
129 str cseq;
130
131 call_id.s=buf1;
132 cseq.s=buf2;
133
134 for (i=987654328;i<987654328+10;i++)
135 for (j=85296341;j<85296341+10;j++)
136 for (k=987654;k<=987654+10;k++)
137 for (l=101;l<201;l++) {
138 call_id.len=snprintf(buf1, 1024, "%d-%d-%d@%s",(int)i,(int)j,
139 (int)k, ip);
140 cseq.len=snprintf(buf2, 1024, "%d", (int)l );
141 /* printf("%s\t%s\n", buf1, buf2 ); */
142 hashv=hash(call_id, cseq);
143 hits[ hashv ]++;
144 }
145 }
146
hashtest(void)147 void hashtest(void)
148 {
149 int hits[TABLE_ENTRIES+5];
150 int i;
151
152 memset( hits, 0, sizeof hits );
153 hashtest_cycle( hits, "192.168.99.100" );
154 hashtest_cycle( hits, "172.168.99.100" );
155 hashtest_cycle( hits, "142.168.99.100" );
156 for (i=0; i<TABLE_ENTRIES+5; i++)
157 printf("[%d. %d]\n", i, hits[i] );
158 exit(0);
159 }
160
161