1 /***************************************************************************** 2 3 gif_hash.c -- module to support the following operations: 4 5 1. InitHashTable - initialize hash table. 6 2. ClearHashTable - clear the hash table to an empty state. 7 2. InsertHashTable - insert one item into data structure. 8 3. ExistsHashTable - test if item exists in data structure. 9 10 This module is used to hash the GIF codes during encoding. 11 12 *****************************************************************************/ 13 14 #include <unistd.h> 15 #include <stdint.h> 16 #include <stdlib.h> 17 #include <fcntl.h> 18 #include <stdio.h> 19 #include <string.h> 20 21 #include "gif_lib.h" 22 #include "gif_hash.h" 23 #include "gif_lib_private.h" 24 25 /* #define DEBUG_HIT_RATE Debug number of misses per hash Insert/Exists. */ 26 27 #ifdef DEBUG_HIT_RATE 28 static long NumberOfTests = 0, 29 NumberOfMisses = 0; 30 #endif /* DEBUG_HIT_RATE */ 31 32 static int KeyItem(uint32_t Item); 33 34 /****************************************************************************** 35 Initialize HashTable - allocate the memory needed and clear it. * 36 ******************************************************************************/ 37 GifHashTableType *_InitHashTable(void) 38 { 39 GifHashTableType *HashTable; 40 41 if ((HashTable = (GifHashTableType *) malloc(sizeof(GifHashTableType))) 42 == NULL) 43 return NULL; 44 45 _ClearHashTable(HashTable); 46 47 return HashTable; 48 } 49 50 /****************************************************************************** 51 Routine to clear the HashTable to an empty state. * 52 This part is a little machine depended. Use the commented part otherwise. * 53 ******************************************************************************/ 54 void _ClearHashTable(GifHashTableType *HashTable) 55 { 56 memset(HashTable -> HTable, 0xFF, HT_SIZE * sizeof(uint32_t)); 57 } 58 59 /****************************************************************************** 60 Routine to insert a new Item into the HashTable. The data is assumed to be * 61 new one. * 62 ******************************************************************************/ 63 void _InsertHashTable(GifHashTableType *HashTable, uint32_t Key, int Code) 64 { 65 int HKey = KeyItem(Key); 66 uint32_t *HTable = HashTable -> HTable; 67 68 #ifdef DEBUG_HIT_RATE 69 NumberOfTests++; 70 NumberOfMisses++; 71 #endif /* DEBUG_HIT_RATE */ 72 73 while (HT_GET_KEY(HTable[HKey]) != 0xFFFFFL) { 74 #ifdef DEBUG_HIT_RATE 75 NumberOfMisses++; 76 #endif /* DEBUG_HIT_RATE */ 77 HKey = (HKey + 1) & HT_KEY_MASK; 78 } 79 HTable[HKey] = HT_PUT_KEY(Key) | HT_PUT_CODE(Code); 80 } 81 82 /****************************************************************************** 83 Routine to test if given Key exists in HashTable and if so returns its code * 84 Returns the Code if key was found, -1 if not. * 85 ******************************************************************************/ 86 int _ExistsHashTable(GifHashTableType *HashTable, uint32_t Key) 87 { 88 int HKey = KeyItem(Key); 89 uint32_t *HTable = HashTable -> HTable, HTKey; 90 91 #ifdef DEBUG_HIT_RATE 92 NumberOfTests++; 93 NumberOfMisses++; 94 #endif /* DEBUG_HIT_RATE */ 95 96 while ((HTKey = HT_GET_KEY(HTable[HKey])) != 0xFFFFFL) { 97 #ifdef DEBUG_HIT_RATE 98 NumberOfMisses++; 99 #endif /* DEBUG_HIT_RATE */ 100 if (Key == HTKey) return HT_GET_CODE(HTable[HKey]); 101 HKey = (HKey + 1) & HT_KEY_MASK; 102 } 103 104 return -1; 105 } 106 107 /****************************************************************************** 108 Routine to generate an HKey for the hashtable out of the given unique key. * 109 The given Key is assumed to be 20 bits as follows: lower 8 bits are the * 110 new postfix character, while the upper 12 bits are the prefix code. * 111 Because the average hit ratio is only 2 (2 hash references per entry), * 112 evaluating more complex keys (such as twin prime keys) does not worth it! * 113 ******************************************************************************/ 114 static int KeyItem(uint32_t Item) 115 { 116 return ((Item >> 12) ^ Item) & HT_KEY_MASK; 117 } 118 119 #ifdef DEBUG_HIT_RATE 120 /****************************************************************************** 121 Debugging routine to print the hit ratio - number of times the hash table * 122 was tested per operation. This routine was used to test the KeyItem routine * 123 ******************************************************************************/ 124 void HashTablePrintHitRatio(void) 125 { 126 printf("Hash Table Hit Ratio is %ld/%ld = %ld%%.\n", 127 NumberOfMisses, NumberOfTests, 128 NumberOfMisses * 100 / NumberOfTests); 129 } 130 #endif /* DEBUG_HIT_RATE */ 131 132 /* end */ 133