3828f841 |
/*
* $Id$
*/
#ifndef _CRC_H_
#define _CRC_H_
extern unsigned long int crc_32_tab[];
extern unsigned short int ccitt_tab[];
extern unsigned short int crc_16_tab[];
#endif
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "hash_func.h"
#include "dprint.h"
#include "crc.h"
#include "ut.h"
|
9df1213c |
#ifdef _OBSOLETED
|
3828f841 |
int old_hash( str call_id, str cseq_nr )
{
int hash_code = 0;
int i;
#if 0 /*def i386*/
int ci_len, cs_len;
char *ci, *cs;
trim_len( ci_len, ci, call_id );
trim_len( cs_len, cs, cseq_nr );
int dummy1;
if (call_id.len>=4){
asm(
"1: \n\r"
"addl (%1), %0 \n\r"
"add $4, %1 \n\r"
"cmp %2, %1 \n\r"
"jl 1b \n\r"
: "=r"(hash_code), "=r"(dummy1)
: "0" (hash_code), "1"(ci),
"r"( (ci_len & (~3)) +ci)
);
}
#else
if ( call_id.len>0 )
for( i=0 ; i<call_id.len ; hash_code+=call_id.s[i++] );
#endif
#if 0 /*def i386*/
int dummy2;
if (cseq_nr.len>=4){
asm(
"1: \n\r"
"addl (%1), %0 \n\r"
"add $4, %1 \n\r"
"cmp %2, %1 \n\r"
"jl 1b \n\r"
: "=r"(hash_code), "=r"(dummy2)
: "0" (hash_code), "1"(cs),
"r"((cs_len & (~3) )+ cs)
);
}
#else
if ( cseq_nr.len>0 )
for( i=0 ; i<cseq_nr.len ; hash_code+=cseq_nr.s[i++] );
#endif
|
9df1213c |
/* this is a buggy line, see bellow hot to fix it -- as this
code is obsoleted I dont care anymore
*/
|
3828f841 |
return hash_code &= (TABLE_ENTRIES-1); /* TABLE_ENTRIES = 2^k */
}
|
9df1213c |
#endif
|
3828f841 |
int new_hash( str call_id, str cseq_nr )
{
int hash_code = 0;
int i,j, k, third;
int ci_len, cs_len;
char *ci, *cs;
/* trim EoLs */
/*
ci_len = call_id.len;
while (ci_len && ((c=call_id.s[ci_len-1])==0 || c=='\r' || c=='\n'))
ci_len--;
cs_len = cseq_nr.len;
while (cs_len && ((c=cseq_nr.s[cs_len-1])==0 || c=='\r' || c=='\n'))
cs_len--;
*/
trim_len( ci_len, ci, call_id );
trim_len( cs_len, cs, cseq_nr );
/* run the cycle from the end ... we are interested in the
most-right digits ... and just take the %10 value of it
*/
third=(ci_len-1)/3;
for ( i=ci_len-1, j=2*third, k=third;
k>0 ; i--, j--, k-- ) {
hash_code+=crc_16_tab[(unsigned char)(*(ci+i)) /*+7*/ ]+
ccitt_tab[*(ci+k)+63]+
ccitt_tab[*(ci+j)+13];
}
for( i=0 ; i<cs_len ; i++ )
//hash_code+=crc_32_tab[(cseq_nr.s[i]+hash_code)%243];
hash_code+=ccitt_tab[*(cs+i)+123];
|
73c6728d |
/* hash_code conditioning */
|
9df1213c |
#ifdef _BUG
|
73c6728d |
/* not flat ... % 111b has shorter period than
& 111b by one and results in different distribution;
( 7 % 7 == 0, 7 %7 == 1 )
% is used as a part of the hash function too, not only
for rounding; & is not flat; whoever comes up with
a nicer flat hash function which does not take
costly division is welcome; feel free to verify
distribution using hashtest()
*/
|
3828f841 |
hash_code &= (TABLE_ENTRIES-1); /* TABLE_ENTRIES = 2^k */
|
9df1213c |
#endif
hash_code=hash_code%(TABLE_ENTRIES-1)+1;
|
3828f841 |
return hash_code;
}
|
73c6728d |
void hashtest_cycle( int hits[TABLE_ENTRIES+5], char *ip )
|
3828f841 |
{
long int i,j,k, l;
int hashv;
static char buf1[1024];
static char buf2[1024];
str call_id;
str cseq;
call_id.s=buf1;
cseq.s=buf2;
for (i=987654328;i<987654328+10;i++)
for (j=85296341;j<85296341+10;j++)
for (k=987654;k<=987654+10;k++)
for (l=101;l<201;l++) {
call_id.len=sprintf( buf1, "%d-%d-%d@%s",(int)i,(int)j,
(int)k, ip );
cseq.len=sprintf( buf2, "%d", (int)l );
|
9df1213c |
/* printf("%s\t%s\n", buf1, buf2 ); */
|
3828f841 |
hashv=hash( call_id, cseq );
hits[ hashv ]++;
}
}
|
9df1213c |
int init_hash()
{
if (TABLE_ENTRIES != (1<<10)) {
LOG(L_WARN, "WARNING: hash function optimized for %d entries\n",
1<<10);
LOG(L_WARN, "WARNING: use of %d entries may lead "
"to unflat distribution\n", TABLE_ENTRIES );
|
73c6728d |
} else {
DBG("DEBUG: hash function initialized with optimum table size\n");
|
9df1213c |
}
return 1;
}
|
3828f841 |
void hashtest()
{
|
73c6728d |
int hits[TABLE_ENTRIES+5];
|
3828f841 |
int i;
|
73c6728d |
init_hash();
|
3828f841 |
memset( hits, 0, sizeof hits );
hashtest_cycle( hits, "192.168.99.100" );
hashtest_cycle( hits, "172.168.99.100" );
hashtest_cycle( hits, "142.168.99.100" );
|
73c6728d |
for (i=0; i<TABLE_ENTRIES+5; i++)
|
3828f841 |
printf("[%d. %d]\n", i, hits[i] );
exit(0);
}
|