| /***************************************************************************** |
| |
| gif_hash.c -- module to support the following operations: |
| |
| 1. InitHashTable - initialize hash table. |
| 2. ClearHashTable - clear the hash table to an empty state. |
| 2. InsertHashTable - insert one item into data structure. |
| 3. ExistsHashTable - test if item exists in data structure. |
| |
| This module is used to hash the GIF codes during encoding. |
| |
| *****************************************************************************/ |
| |
| #include <unistd.h> |
| #include <stdint.h> |
| #include <stdlib.h> |
| #include <fcntl.h> |
| #include <stdio.h> |
| #include <string.h> |
| |
| #include "gif_lib.h" |
| #include "gif_hash.h" |
| #include "gif_lib_private.h" |
| |
| /* #define DEBUG_HIT_RATE Debug number of misses per hash Insert/Exists. */ |
| |
| #ifdef DEBUG_HIT_RATE |
| static long NumberOfTests = 0, |
| NumberOfMisses = 0; |
| #endif /* DEBUG_HIT_RATE */ |
| |
| static int KeyItem(uint32_t Item); |
| |
| /****************************************************************************** |
| Initialize HashTable - allocate the memory needed and clear it. * |
| ******************************************************************************/ |
| GifHashTableType *_InitHashTable(void) |
| { |
| GifHashTableType *HashTable; |
| |
| if ((HashTable = (GifHashTableType *) malloc(sizeof(GifHashTableType))) |
| == NULL) |
| return NULL; |
| |
| _ClearHashTable(HashTable); |
| |
| return HashTable; |
| } |
| |
| /****************************************************************************** |
| Routine to clear the HashTable to an empty state. * |
| This part is a little machine depended. Use the commented part otherwise. * |
| ******************************************************************************/ |
| void _ClearHashTable(GifHashTableType *HashTable) |
| { |
| memset(HashTable -> HTable, 0xFF, HT_SIZE * sizeof(uint32_t)); |
| } |
| |
| /****************************************************************************** |
| Routine to insert a new Item into the HashTable. The data is assumed to be * |
| new one. * |
| ******************************************************************************/ |
| void _InsertHashTable(GifHashTableType *HashTable, uint32_t Key, int Code) |
| { |
| int HKey = KeyItem(Key); |
| uint32_t *HTable = HashTable -> HTable; |
| |
| #ifdef DEBUG_HIT_RATE |
| NumberOfTests++; |
| NumberOfMisses++; |
| #endif /* DEBUG_HIT_RATE */ |
| |
| while (HT_GET_KEY(HTable[HKey]) != 0xFFFFFL) { |
| #ifdef DEBUG_HIT_RATE |
| NumberOfMisses++; |
| #endif /* DEBUG_HIT_RATE */ |
| HKey = (HKey + 1) & HT_KEY_MASK; |
| } |
| HTable[HKey] = HT_PUT_KEY(Key) | HT_PUT_CODE(Code); |
| } |
| |
| /****************************************************************************** |
| Routine to test if given Key exists in HashTable and if so returns its code * |
| Returns the Code if key was found, -1 if not. * |
| ******************************************************************************/ |
| int _ExistsHashTable(GifHashTableType *HashTable, uint32_t Key) |
| { |
| int HKey = KeyItem(Key); |
| uint32_t *HTable = HashTable -> HTable, HTKey; |
| |
| #ifdef DEBUG_HIT_RATE |
| NumberOfTests++; |
| NumberOfMisses++; |
| #endif /* DEBUG_HIT_RATE */ |
| |
| while ((HTKey = HT_GET_KEY(HTable[HKey])) != 0xFFFFFL) { |
| #ifdef DEBUG_HIT_RATE |
| NumberOfMisses++; |
| #endif /* DEBUG_HIT_RATE */ |
| if (Key == HTKey) return HT_GET_CODE(HTable[HKey]); |
| HKey = (HKey + 1) & HT_KEY_MASK; |
| } |
| |
| return -1; |
| } |
| |
| /****************************************************************************** |
| Routine to generate an HKey for the hashtable out of the given unique key. * |
| The given Key is assumed to be 20 bits as follows: lower 8 bits are the * |
| new postfix character, while the upper 12 bits are the prefix code. * |
| Because the average hit ratio is only 2 (2 hash references per entry), * |
| evaluating more complex keys (such as twin prime keys) does not worth it! * |
| ******************************************************************************/ |
| static int KeyItem(uint32_t Item) |
| { |
| return ((Item >> 12) ^ Item) & HT_KEY_MASK; |
| } |
| |
| #ifdef DEBUG_HIT_RATE |
| /****************************************************************************** |
| Debugging routine to print the hit ratio - number of times the hash table * |
| was tested per operation. This routine was used to test the KeyItem routine * |
| ******************************************************************************/ |
| void HashTablePrintHitRatio(void) |
| { |
| printf("Hash Table Hit Ratio is %ld/%ld = %ld%%.\n", |
| NumberOfMisses, NumberOfTests, |
| NumberOfMisses * 100 / NumberOfTests); |
| } |
| #endif /* DEBUG_HIT_RATE */ |
| |
| /* end */ |