SE250:lab-5:dcho040

Understanding the codes

buzhash.c

Satic Values

hash_t(unsigned long) BUZINIT
hash_t(unsigned long) buztbl[256]

void random_perm( int *C)

input : 256 int array
work : Random changing between values in the array
output : No
used in ressed_buztable

void ressed_buztable

input : No
work : Change the values(BUZINIT, buztbl[256]) to random
output : No

• test

=====How it works=====
e.g. changing of the value BUZINIT

C[0] = 1
Before
BUZINIT = D4A96F89
11010100 10101001 01101111 10001001 

BUZINIT = NUZINIT << 1 | C[0]

After
BUZINIT = A952DF13
10101001 01010010 11011111 00010011 

-------------------------------------------------------------------------

C[0] = 0

Before
BUZINIT = A952DF13
10101001 01010010 11011111 00010011 

BUZINIT = NUZINIT << 1 | C[0]

After
BUZINIT = 52A5BE26
01010010 10100101 10111110 00100110 

--------------------------------------------------------------------------
... 256 times with random C[0] = (0 or 1)

to get binary information

//Use this function
void bits(unsigned long a) {
	unsigned long displayMask = 1 << 31;
	int c;
	for (c = 1; c <= 32; c++) {
		putchar( a & displayMask ? '1' : '0' );
		a = a << 1;
		if ( c%8 == 0) {
			putchar(' ');
		}
	}
	putchar('\n');
}

How to use &, |, <<, >>

• e.g. How it works? a = a<<2 | 3;

1) the initial value of 'a'
6A54B7C4 (01101010 01010100 10110111 11000100)

2) a << 2 is run
6A54B7C4 (01101010 01010100 10110111 11000100) to
A952DF10 (10101001 01010010 11011111 00010000) 

3) a | 3 is run
a      = A952DF10 (10101001 01010010 11011111 00010000) 
3      =                    3 (00000000 00000000 00000000 00000011)
a | 3 = A952DF13 (10101001 01010010 11011111 00010011)

void dump_buztbl

input : No
work : print BUZINIT and buztbl[]
output : No

hash_t buzhash( char * key )

input : char *key => char array (e.g. "bbbbbbb0")
work : No
output : hash h (explain below)

How to return value(hash h)

e.g. char *key => "abcdef0"
         BUZINIT = 1783936964L
         buztbl[97] = 11100011 10011101 11100101 10000010(base2)
 
hast_t h = BUZINIT // h = 1783936964
while ( *key )             // a -> b -> c -> d -> e
 
   h = ((h << 1) | (h >> (sizeof(hash_t)*8-1))) ^ buztbl[ (unsigned)*key++ ]; //*key = a
	   // h = 01101010 01010100 10110111 11000100
	   // ((h << 1) | (h >> (sizeof(hash_t)*8-1)))
		// '0'1101010 01010100 10110111 11000100 move first value '0'
		//     11010100 10101001 01101111 1000100'0'     to the end
	   //buztbl[ (unsigned)*key++ ] //buztbl[97]     ( 97='a' )
		//11100011 10011101 11100101 10000010
	   //       11010100 10101001 01101111 10001000 ^ (xor)
	   //       11100011 10011101 11100101 10000010
	   // h = 00110111 00110100 10001010 00001010(base2)
   h = ((h << 1) | (h >> (sizeof(hash_t)*8-1))) ^ buztbl[ (unsigned)*key++ ]; //*key = b
   h = ((h << 1) | (h >> (sizeof(hash_t)*8-1))) ^ buztbl[ (unsigned)*key++ ]; //*key = c
   h = ((h << 1) | (h >> (sizeof(hash_t)*8-1))) ^ buztbl[ (unsigned)*key++ ]; //*key = d
   h = ((h << 1) | (h >> (sizeof(hash_t)*8-1))) ^ buztbl[ (unsigned)*key++ ]; //*key = e
   
return h;

hash_t buzhashn( char * key, int n )

input : char *key => char array (e.g. "bbbbbbb0")
             int n                                      (e.g. 3)
work : No
output : hash h (same as buzhash but use only use n values from *key)