Using Blizzard MPQhash in C


  • 0
    M
    unsigned long cryptTable[0x500];
    typedef struct  
    {  
        long nHashA;  
        long nHashB;  
        bool bExists;  
    } MPQHASHTABLE; 
    void prepareCryptTable()
    {
        unsigned long seed = 0x00100001, index1 = 0, index2 = 0, i;
        for( index1 = 0; index1 < 0x100; index1++ )
        {
            for( index2 = index1, i = 0; i < 5; i++, index2 += 0x100 )
            {
                unsigned long temp1, temp2;
                seed = (seed * 125 + 3) % 0x2AAAAB;
                temp1 = (seed & 0xFFFF) << 0x10;
                seed = (seed * 125 + 3) % 0x2AAAAB;
                temp2 = (seed & 0xFFFF);
                cryptTable[index2] = ( temp1 | temp2 );
            }
        }
    }
    
    unsigned long HashInt( int nNeedHash, unsigned long dwHashType )
    {
        unsigned long seed1 = 0x7FED7FED;
        unsigned long seed2 = 0xEEEEEEEE;
    	char pszTemp[10];
    	sprintf(pszTemp, "%d", nNeedHash);
    	unsigned char *key  = (unsigned char *)(pszTemp);
    	int ch;
    	while (*key != 0)
    	{
    		ch = toupper(*key++);
    		seed1 = cryptTable[(dwHashType << 8) + ch] ^ (seed1 + seed2);
    		seed2 = ch + seed1 + seed2 + (seed2 << 5) + 3;
    	}
    	return seed1;
    }
    
    
    bool containsDuplicate(int* nums, int numsSize) {
        prepareCryptTable();
        int i,j,tempHashA,tempHashB;
        int nTableSize = numsSize*2;
        MPQHASHTABLE * pHashTable = malloc(sizeof(MPQHASHTABLE)*nTableSize);
        for ( i = 0; i < nTableSize; i++){
            pHashTable[i].nHashA = -1;
            pHashTable[i].nHashB = -1;
            pHashTable[i].bExists = false;
        }
        for ( i = 0; i < numsSize; i++){
            j = HashInt(nums[i],0) % nTableSize;
            tempHashA = HashInt(nums[i],1);
            tempHashB = HashInt(nums[i],2);
            if (pHashTable[j].bExists){
                if(tempHashA == pHashTable[j].nHashA && tempHashB == pHashTable[j].nHashB){
                    return true;
                }
            }
            pHashTable[j].bExists = true;
            pHashTable[j].nHashA = tempHashA;
            pHashTable[j].nHashB = tempHashB;
        }
        return false;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.