MUX: mux/src/svdhash.cpp File Reference

#define DO1	(	buf,
		i		)	{s1 += buf[i]; s2 += s1;}

Definition at line 141 of file svdhash.cpp.

#define DO16 ( buf ) DO8(buf,0); DO8(buf,8);

Definition at line 145 of file svdhash.cpp.

Referenced by HASH_ProcessBuffer().

#define DO2	(	buf,
		i		)	DO1(buf,i); DO1(buf,i+1);

Definition at line 142 of file svdhash.cpp.

#define DO4	(	buf,
		i		)	DO2(buf,i); DO2(buf,i+2);

Definition at line 143 of file svdhash.cpp.

#define DO8	(	buf,
		i		)	DO4(buf,i); DO4(buf,i+4);

Definition at line 144 of file svdhash.cpp.

#define DO_COMMIT

Definition at line 14 of file svdhash.cpp.

#define FILE_SIZE_TRIGGER (512*1024UL)

Definition at line 2702 of file svdhash.cpp.

Referenced by CLogFile::Flush().

#define FILL_FACTOR 1

Referenced by CHashPage::GetStats().

#define NUMBER_OF_PRIMES 177

Definition at line 278 of file svdhash.cpp.

Referenced by ChoosePrimes().

static void ChoosePrimes	(	int	TableSize,
		HP_HEAPOFFSET	HashPrimes[16]
	)			`[static]`

Definition at line 295 of file svdhash.cpp.

References NUMBER_OF_PRIMES, and RandomINT32().

Referenced by CHashPage::Empty().

00296 {
00297     int LargestPrime = TableSize/2;
00298     if (LargestPrime > Primes[NUMBER_OF_PRIMES-2])
00299     {
00300         LargestPrime = Primes[NUMBER_OF_PRIMES-2];
00301     }
00302     int Spacing = LargestPrime/16;
00303 
00304     // Pick a set primes that are evenly spaced from (0 to LargestPrime)
00305     // We divide this interval into 16 equal sized zones. We want to find
00306     // one prime number that best represents that zone.
00307     //
00308     int iZone, iPrime;
00309     for (iZone = 1, iPrime = 0; iPrime < 16; iZone += Spacing)
00310     {
00311         // Search for a prime number that is less than the target zone
00312         // number given by iZone.
00313         //
00314         int Lower = Primes[0];
00315         for (int jPrime = 0; Primes[jPrime] != 0; jPrime++)
00316         {
00317             if (jPrime != 0 && TableSize % Primes[jPrime] == 0) continue;
00318             int Upper = Primes[jPrime];
00319             if (Lower <= iZone && iZone <= Upper)
00320             {
00321                 // Choose the closest lower prime number.
00322                 //
00323                 if (iZone - Lower <= Upper - iZone)
00324                 {
00325                     HashPrimes[iPrime++] = Lower;
00326                 }
00327                 else
00328                 {
00329                     HashPrimes[iPrime++] = Upper;
00330                 }
00331                 break;
00332             }
00333             Lower = Upper;
00334         }
00335     }
00336 
00337     // Alternate negative and positive numbers
00338     //
00339     for (iPrime = 0; iPrime < 16; iPrime += 2)
00340     {
00341         HashPrimes[iPrime] = TableSize-HashPrimes[iPrime];
00342     }
00343 
00344     // Shuffle the set of primes to reduce correlation with bits in
00345     // hash key.
00346     //
00347     for (iPrime = 0; iPrime < 16-1; iPrime++)
00348     {
00349         int Pick = (int)RandomINT32(0, 15-iPrime);
00350         HP_HEAPOFFSET Temp = HashPrimes[Pick];
00351         HashPrimes[Pick] = HashPrimes[15-iPrime];
00352         HashPrimes[15-iPrime] = Temp;
00353     }
00354 }

UINT32 CRC32_ProcessBuffer	(	UINT32	ulCrc,
		const void *	arg_pBuffer,
		unsigned int	nBuffer
	)

Definition at line 98 of file svdhash.cpp.

References CRC32_Table.

Referenced by FUNCTION(), and SeedRandomNumberGenerator().

00103 {
00104     UINT8 *pBuffer = (UINT8 *)arg_pBuffer;
00105 
00106     ulCrc = ~ulCrc;
00107     while (nBuffer--)
00108     {
00109         ulCrc  = CRC32_Table[((UINT8)*pBuffer++) ^ (UINT8)ulCrc] ^ (ulCrc >> 8);
00110     }
00111     return ~ulCrc;
00112 }

UINT32 CRC32_ProcessInteger ( UINT32 nInteger )

Definition at line 114 of file svdhash.cpp.

References CRC32_Table.

00115 {
00116     UINT32 ulCrc;
00117     ulCrc  = ~nInteger;
00118     ulCrc  = CRC32_Table[(UINT8)ulCrc] ^ (ulCrc >> 8);
00119     ulCrc  = CRC32_Table[(UINT8)ulCrc] ^ (ulCrc >> 8);
00120     ulCrc  = CRC32_Table[(UINT8)ulCrc] ^ (ulCrc >> 8);
00121     ulCrc  = CRC32_Table[(UINT8)ulCrc] ^ (ulCrc >> 8);
00122     return ~ulCrc;
00123 }

UINT32 CRC32_ProcessInteger2	(	UINT32	nInteger1,
		UINT32	nInteger2
	)

Definition at line 125 of file svdhash.cpp.

References CRC32_Table.

Referenced by cache_del(), cache_get(), cache_put(), and pool_init().

00126 {
00127     UINT32 ulCrc;
00128     ulCrc  = ~nInteger1;
00129     ulCrc  = CRC32_Table[(UINT8)ulCrc] ^ (ulCrc >> 8);
00130     ulCrc  = CRC32_Table[(UINT8)ulCrc] ^ (ulCrc >> 8);
00131     ulCrc  = CRC32_Table[(UINT8)ulCrc] ^ (ulCrc >> 8);
00132     ulCrc  = CRC32_Table[(UINT8)ulCrc] ^ (ulCrc >> 8);
00133     ulCrc ^= nInteger2;
00134     ulCrc  = CRC32_Table[(UINT8)ulCrc] ^ (ulCrc >> 8);
00135     ulCrc  = CRC32_Table[(UINT8)ulCrc] ^ (ulCrc >> 8);
00136     ulCrc  = CRC32_Table[(UINT8)ulCrc] ^ (ulCrc >> 8);
00137     ulCrc  = CRC32_Table[(UINT8)ulCrc] ^ (ulCrc >> 8);
00138     return ~ulCrc;
00139 }

UINT32 HASH_ProcessBuffer	(	UINT32	ulHash,
		const void *	arg_pBuffer,
		size_t	nBuffer
	)

Definition at line 148 of file svdhash.cpp.

References CRC32_Table, DO16, and Bigint::k.

Referenced by dbclean_RemoveStaleAttributeNames(), dbclean_RenumberAttributes(), hashaddLEN(), hashdeleteLEN(), hashfindLEN(), hashreplLEN(), vattr_define_LEN(), vattr_delete_LEN(), vattr_find_LEN(), and vattr_rename_LEN().

00153 {
00154     UINT8 *pBuffer = (UINT8 *)arg_pBuffer;
00155     ulHash = ~ulHash;
00156 
00157     if (nBuffer <= 16)
00158     {
00159         pBuffer -= 16 - nBuffer;
00160         switch (nBuffer)
00161         {
00162         case 16: ulHash  = CRC32_Table[pBuffer[0] ^ (UINT8)ulHash] ^ (ulHash >> 8);
00163         case 15: ulHash  = CRC32_Table[pBuffer[1] ^ (UINT8)ulHash] ^ (ulHash >> 8);
00164         case 14: ulHash  = CRC32_Table[pBuffer[2] ^ (UINT8)ulHash] ^ (ulHash >> 8);
00165         case 13: ulHash  = CRC32_Table[pBuffer[3] ^ (UINT8)ulHash] ^ (ulHash >> 8);
00166         case 12: ulHash  = CRC32_Table[pBuffer[4] ^ (UINT8)ulHash] ^ (ulHash >> 8);
00167         case 11: ulHash  = CRC32_Table[pBuffer[5] ^ (UINT8)ulHash] ^ (ulHash >> 8);
00168         case 10: ulHash  = CRC32_Table[pBuffer[6] ^ (UINT8)ulHash] ^ (ulHash >> 8);
00169         case 9:  ulHash  = CRC32_Table[pBuffer[7] ^ (UINT8)ulHash] ^ (ulHash >> 8);
00170 #if defined(UNALIGNED32) && defined(WORDS_LITTLEENDIAN)
00171         case 8:  ulHash ^= *(UINT32 *)(pBuffer + 8);
00172                  ulHash  = CRC32_Table[(UINT8)ulHash] ^ (ulHash >> 8);
00173                  ulHash  = CRC32_Table[(UINT8)ulHash] ^ (ulHash >> 8);
00174                  ulHash  = CRC32_Table[(UINT8)ulHash] ^ (ulHash >> 8);
00175                  ulHash  = CRC32_Table[(UINT8)ulHash] ^ (ulHash >> 8);
00176                  ulHash ^= *(UINT32 *)(pBuffer + 12);
00177                  ulHash  = CRC32_Table[(UINT8)ulHash] ^ (ulHash >> 8);
00178                  ulHash  = CRC32_Table[(UINT8)ulHash] ^ (ulHash >> 8);
00179                  ulHash  = CRC32_Table[(UINT8)ulHash] ^ (ulHash >> 8);
00180                  ulHash  = CRC32_Table[(UINT8)ulHash] ^ (ulHash >> 8);
00181                  return ~ulHash;
00182 #else
00183         case 8:  ulHash  = CRC32_Table[pBuffer[8] ^ (UINT8)ulHash] ^ (ulHash >> 8);
00184 #endif
00185 
00186         case 7:  ulHash  = CRC32_Table[pBuffer[9] ^ (UINT8)ulHash] ^ (ulHash >> 8);
00187         case 6:  ulHash  = CRC32_Table[pBuffer[10] ^ (UINT8)ulHash] ^ (ulHash >> 8);
00188         case 5:  ulHash  = CRC32_Table[pBuffer[11] ^ (UINT8)ulHash] ^ (ulHash >> 8);
00189 #if defined(UNALIGNED32) && defined(WORDS_LITTLEENDIAN)
00190         case 4:  ulHash ^= *(UINT32 *)(pBuffer + 12);
00191                  ulHash  = CRC32_Table[(UINT8)ulHash] ^ (ulHash >> 8);
00192                  ulHash  = CRC32_Table[(UINT8)ulHash] ^ (ulHash >> 8);
00193                  ulHash  = CRC32_Table[(UINT8)ulHash] ^ (ulHash >> 8);
00194                  ulHash  = CRC32_Table[(UINT8)ulHash] ^ (ulHash >> 8);
00195                  return ~ulHash;
00196 #else
00197         case 4:  ulHash  = CRC32_Table[pBuffer[12] ^ (UINT8)ulHash] ^ (ulHash >> 8);
00198 #endif
00199 
00200         case 3:  ulHash  = CRC32_Table[pBuffer[13] ^ (UINT8)ulHash] ^ (ulHash >> 8);
00201         case 2:  ulHash  = CRC32_Table[pBuffer[14] ^ (UINT8)ulHash] ^ (ulHash >> 8);
00202         case 1:  ulHash  = CRC32_Table[pBuffer[15] ^ (UINT8)ulHash] ^ (ulHash >> 8);
00203         case 0:  return ~ulHash;
00204         }
00205     }
00206 
00207     size_t nSmall  = nBuffer & 15;
00208     size_t nMedium = (nBuffer >> 4) & 255;
00209     size_t nLarge  = nBuffer >> 12;
00210 
00211     UINT32 s1 = ulHash & 0xFFFF;
00212     UINT32 s2 = (ulHash >> 16) & 0xFFFF;
00213 
00214     while (nLarge--)
00215     {
00216         int k = 256;
00217         while (k)
00218         {
00219             DO16(pBuffer);
00220             pBuffer += 16;
00221             k--;
00222         }
00223         ulHash  = ~s1;
00224         ulHash  = CRC32_Table[(UINT8)ulHash] ^ (ulHash >> 8);
00225         ulHash  = CRC32_Table[(UINT8)ulHash] ^ (ulHash >> 8);
00226         ulHash  = CRC32_Table[(UINT8)ulHash] ^ (ulHash >> 8);
00227         ulHash  = CRC32_Table[(UINT8)ulHash] ^ (ulHash >> 8);
00228         ulHash ^= s2;
00229         ulHash  = CRC32_Table[(UINT8)ulHash] ^ (ulHash >> 8);
00230         ulHash  = CRC32_Table[(UINT8)ulHash] ^ (ulHash >> 8);
00231         ulHash  = CRC32_Table[(UINT8)ulHash] ^ (ulHash >> 8);
00232         ulHash  = CRC32_Table[(UINT8)ulHash] ^ (ulHash >> 8);
00233         ulHash = ~ulHash;
00234         s1 = ulHash & 0xFFFF;
00235         s2 = (ulHash >> 16) & 0xFFFF;
00236     }
00237 
00238     while (nMedium--)
00239     {
00240         DO16(pBuffer);
00241         pBuffer += 16;
00242     }
00243 
00244     pBuffer -= 15 - nSmall;
00245     switch (nSmall)
00246     {
00247     case 15: s1 += pBuffer[0];  s2 += s1;
00248     case 14: s1 += pBuffer[1];  s2 += s1;
00249     case 13: s1 += pBuffer[2];  s2 += s1;
00250     case 12: s1 += pBuffer[3];  s2 += s1;
00251     case 11: s1 += pBuffer[4];  s2 += s1;
00252     case 10: s1 += pBuffer[5];  s2 += s1;
00253     case 9:  s1 += pBuffer[6];  s2 += s1;
00254     case 8:  s1 += pBuffer[7];  s2 += s1;
00255     case 7:  s1 += pBuffer[8];  s2 += s1;
00256     case 6:  s1 += pBuffer[9];  s2 += s1;
00257     case 5:  s1 += pBuffer[10]; s2 += s1;
00258     case 4:  s1 += pBuffer[11]; s2 += s1;
00259     case 3:  s1 += pBuffer[12]; s2 += s1;
00260     case 2:  s1 += pBuffer[13]; s2 += s1;
00261     case 1:  s1 += pBuffer[14]; s2 += s1;
00262     case 0:  break;
00263     }
00264 
00265     ulHash  = ~s1;
00266     ulHash  = CRC32_Table[(UINT8)ulHash] ^ (ulHash >> 8);
00267     ulHash  = CRC32_Table[(UINT8)ulHash] ^ (ulHash >> 8);
00268     ulHash  = CRC32_Table[(UINT8)ulHash] ^ (ulHash >> 8);
00269     ulHash  = CRC32_Table[(UINT8)ulHash] ^ (ulHash >> 8);
00270     ulHash ^= s2;
00271     ulHash  = CRC32_Table[(UINT8)ulHash] ^ (ulHash >> 8);
00272     ulHash  = CRC32_Table[(UINT8)ulHash] ^ (ulHash >> 8);
00273     ulHash  = CRC32_Table[(UINT8)ulHash] ^ (ulHash >> 8);
00274     ulHash  = CRC32_Table[(UINT8)ulHash] ^ (ulHash >> 8);
00275     return ~ulHash;
00276 }

static void MakeLogName	(	const char *	pBasename,
		const char *	szPrefix,
		CLinearTimeAbsolute	lta,
		char *	szLogName
	)			`[static]`

Definition at line 2628 of file svdhash.cpp.

References CLinearTimeAbsolute::ReturnUniqueString().

Referenced by CLogFile::Flush(), CLogFile::SetPrefix(), and CLogFile::StartLogging().

02634 {
02635     char szTimeStamp[18];
02636     lta.ReturnUniqueString(szTimeStamp);
02637     if (  pBasename
02638        && pBasename[0] != '\0')
02639     {
02640         sprintf(szLogName, "%s/%s-%s.log",
02641             pBasename,
02642             szPrefix,
02643             szTimeStamp);
02644     }
02645     else
02646     {
02647         sprintf(szLogName, "%s-%s.log",
02648             szPrefix,
02649             szTimeStamp);
02650     }
02651 }

const UINT32 anGroupMask[33] [static]

Initial value:

{
    0x00000000U,
    0x80000000U, 0xC0000000U, 0xE0000000U, 0xF0000000U,
    0xF8000000U, 0xFC000000U, 0xFE000000U, 0xFF000000U,
    0xFF800000U, 0xFFC00000U, 0xFFE00000U, 0xFFF00000U,
    0xFFF80000U, 0xFFFC0000U, 0xFFFE0000U, 0xFFFF0000U,
    0xFFFF8000U, 0xFFFFC000U, 0xFFFFE000U, 0xFFFFF000U,
    0xFFFFF800U, 0xFFFFFC00U, 0xFFFFFE00U, 0xFFFFFF00U,
    0xFFFFFF80U, 0xFFFFFFC0U, 0xFFFFFFE0U, 0xFFFFFFF0U,
    0xFFFFFFF8U, 0xFFFFFFFCU, 0xFFFFFFFEU, 0xFFFFFFFFU
}

Definition at line 356 of file svdhash.cpp.

const UINT32 CRC32_Table[256] [static]

Definition at line 26 of file svdhash.cpp.

Referenced by CRC32_ProcessBuffer(), CRC32_ProcessInteger(), CRC32_ProcessInteger2(), and HASH_ProcessBuffer().

int cs_dbreads = 0

Definition at line 21 of file svdhash.cpp.

Referenced by list_db_stats(), and CHashPage::ReadPage().

int cs_dbwrites = 0

Definition at line 22 of file svdhash.cpp.

Referenced by list_db_stats(), and CHashPage::WritePage().

int cs_dels = 0

Definition at line 18 of file svdhash.cpp.

Referenced by list_db_stats(), and CHashFile::Remove().

int cs_fails = 0

Definition at line 19 of file svdhash.cpp.

Referenced by CHashFile::FindFirstKey(), and CHashFile::FindNextKey().

int cs_reads = 0

Definition at line 17 of file svdhash.cpp.

Referenced by CHashFile::FindFirstKey(), CHashFile::FindNextKey(), and list_db_stats().

int cs_rhits = 0

Definition at line 24 of file svdhash.cpp.

Referenced by CHashFile::FindFirstKey(), and list_db_stats().

int cs_syncs = 0

Definition at line 20 of file svdhash.cpp.

Referenced by list_db_stats(), and CHashFile::Sync().

int cs_whits = 0

Definition at line 23 of file svdhash.cpp.

Referenced by CHashFile::Insert(), and list_db_stats().

int cs_writes = 0

Definition at line 16 of file svdhash.cpp.

Referenced by CHashFile::Insert(), and list_db_stats().

CLogFile Log

Definition at line 2563 of file svdhash.cpp.

Referenced by add_comsys(), AssertionFailed(), cache_del(), cache_put(), CF_HAND(), cf_log_notfound(), db_read(), db_write(), dbconvert(), del_comsys(), do_restart(), dup_bool(), end_log(), eval_boolexp(), CHashTable::FindFirstKey(), CHashFile::FindFirstKey(), get_list(), HelpIndex_Read(), info(), init_dbfile(), CHashTable::Insert(), CHashFile::Insert(), CHashPage::Insert(), load_channels(), load_comsys(), load_comsystem(), load_game(), load_malias(), log_name(), log_number(), log_perror(), log_printf(), log_text(), LogStatBuf(), main(), make_socket(), OutOfMemory(), pool_alloc(), pool_alloc_lbuf(), pool_err(), pool_free(), pool_free_lbuf(), putbool_subexp(), CHashFile::ReadCache(), CHashPage::ReadPage(), CHashFile::RebuildDirectory(), ReplaceFile(), report_timecheck(), save_comsys(), sighandler(), CHashPage::Split(), start_log(), CHashFile::Sync(), unparse_boolexp1(), write_pidfile(), and CHashPage::WritePage().

const int Primes[NUMBER_OF_PRIMES]

Initial value:

{

    1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67,
    71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151,
    157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239,
    241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337,
    347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433,
    439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541,
    547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641,
    643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743,
    751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857,
    859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971,
    977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 0
}

Definition at line 279 of file svdhash.cpp.

mux/src/svdhash.cpp File Reference

Defines

Functions

Variables

Define Documentation

Function Documentation

Variable Documentation


Defines
#define	DO_COMMIT
#define	DO1(buf, i) {s1 += buf[i]; s2 += s1;}
#define	DO2(buf, i) DO1(buf,i); DO1(buf,i+1);
#define	DO4(buf, i) DO2(buf,i); DO2(buf,i+2);
#define	DO8(buf, i) DO4(buf,i); DO4(buf,i+4);
#define	DO16(buf) DO8(buf,0); DO8(buf,8);
#define	NUMBER_OF_PRIMES 177
#define	FILL_FACTOR 1
#define	FILE_SIZE_TRIGGER (512*1024UL)
Functions
UINT32	CRC32_ProcessBuffer (UINT32 ulCrc, const void *arg_pBuffer, unsigned int nBuffer)
UINT32	CRC32_ProcessInteger (UINT32 nInteger)
UINT32	CRC32_ProcessInteger2 (UINT32 nInteger1, UINT32 nInteger2)
UINT32	HASH_ProcessBuffer (UINT32 ulHash, const void *arg_pBuffer, size_t nBuffer)
static void	ChoosePrimes (int TableSize, HP_HEAPOFFSET HashPrimes[16])
static void	MakeLogName (const char pBasename, const char szPrefix, CLinearTimeAbsolute lta, char *szLogName)
Variables
int	cs_writes = 0
int	cs_reads = 0
int	cs_dels = 0
int	cs_fails = 0
int	cs_syncs = 0
int	cs_dbreads = 0
int	cs_dbwrites = 0
int	cs_whits = 0
int	cs_rhits = 0
static const UINT32	CRC32_Table [256]
const int	Primes [NUMBER_OF_PRIMES]
static const UINT32	anGroupMask [33]
CLogFile	Log