gif_hash.c revision 9b8f8602a74a943ddc356bb11c55b4998b2b386d
19b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot/***************************************************************************** 29b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 39b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfootgif_hash.c -- module to support the following operations: 49b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 59b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot1. InitHashTable - initialize hash table. 69b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot2. ClearHashTable - clear the hash table to an empty state. 79b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot2. InsertHashTable - insert one item into data structure. 89b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot3. ExistsHashTable - test if item exists in data structure. 99b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 109b8f8602a74a943ddc356bb11c55b4998b2b386dKeith PlatfootThis module is used to hash the GIF codes during encoding. 119b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 129b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot*****************************************************************************/ 139b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 149b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot#include <unistd.h> 159b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot#include <stdint.h> 169b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot#include <stdlib.h> 179b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot#include <fcntl.h> 189b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot#include <stdio.h> 199b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot#include <string.h> 209b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 219b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot#include "gif_lib.h" 229b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot#include "gif_hash.h" 239b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot#include "gif_lib_private.h" 249b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 259b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot/* #define DEBUG_HIT_RATE Debug number of misses per hash Insert/Exists. */ 269b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 279b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot#ifdef DEBUG_HIT_RATE 289b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfootstatic long NumberOfTests = 0, 299b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot NumberOfMisses = 0; 309b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot#endif /* DEBUG_HIT_RATE */ 319b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 329b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfootstatic int KeyItem(uint32_t Item); 339b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 349b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot/****************************************************************************** 359b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot Initialize HashTable - allocate the memory needed and clear it. * 369b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot******************************************************************************/ 379b8f8602a74a943ddc356bb11c55b4998b2b386dKeith PlatfootGifHashTableType *_InitHashTable(void) 389b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot{ 399b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot GifHashTableType *HashTable; 409b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 419b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot if ((HashTable = (GifHashTableType *) malloc(sizeof(GifHashTableType))) 429b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot == NULL) 439b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot return NULL; 449b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 459b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot _ClearHashTable(HashTable); 469b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 479b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot return HashTable; 489b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot} 499b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 509b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot/****************************************************************************** 519b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot Routine to clear the HashTable to an empty state. * 529b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot This part is a little machine depended. Use the commented part otherwise. * 539b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot******************************************************************************/ 549b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfootvoid _ClearHashTable(GifHashTableType *HashTable) 559b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot{ 569b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot memset(HashTable -> HTable, 0xFF, HT_SIZE * sizeof(uint32_t)); 579b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot} 589b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 599b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot/****************************************************************************** 609b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot Routine to insert a new Item into the HashTable. The data is assumed to be * 619b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot new one. * 629b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot******************************************************************************/ 639b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfootvoid _InsertHashTable(GifHashTableType *HashTable, uint32_t Key, int Code) 649b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot{ 659b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot int HKey = KeyItem(Key); 669b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot uint32_t *HTable = HashTable -> HTable; 679b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 689b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot#ifdef DEBUG_HIT_RATE 699b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot NumberOfTests++; 709b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot NumberOfMisses++; 719b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot#endif /* DEBUG_HIT_RATE */ 729b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 739b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot while (HT_GET_KEY(HTable[HKey]) != 0xFFFFFL) { 749b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot#ifdef DEBUG_HIT_RATE 759b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot NumberOfMisses++; 769b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot#endif /* DEBUG_HIT_RATE */ 779b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot HKey = (HKey + 1) & HT_KEY_MASK; 789b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot } 799b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot HTable[HKey] = HT_PUT_KEY(Key) | HT_PUT_CODE(Code); 809b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot} 819b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 829b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot/****************************************************************************** 839b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot Routine to test if given Key exists in HashTable and if so returns its code * 849b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot Returns the Code if key was found, -1 if not. * 859b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot******************************************************************************/ 869b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfootint _ExistsHashTable(GifHashTableType *HashTable, uint32_t Key) 879b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot{ 889b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot int HKey = KeyItem(Key); 899b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot uint32_t *HTable = HashTable -> HTable, HTKey; 909b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 919b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot#ifdef DEBUG_HIT_RATE 929b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot NumberOfTests++; 939b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot NumberOfMisses++; 949b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot#endif /* DEBUG_HIT_RATE */ 959b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 969b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot while ((HTKey = HT_GET_KEY(HTable[HKey])) != 0xFFFFFL) { 979b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot#ifdef DEBUG_HIT_RATE 989b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot NumberOfMisses++; 999b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot#endif /* DEBUG_HIT_RATE */ 1009b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot if (Key == HTKey) return HT_GET_CODE(HTable[HKey]); 1019b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot HKey = (HKey + 1) & HT_KEY_MASK; 1029b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot } 1039b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 1049b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot return -1; 1059b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot} 1069b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 1079b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot/****************************************************************************** 1089b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot Routine to generate an HKey for the hashtable out of the given unique key. * 1099b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot The given Key is assumed to be 20 bits as follows: lower 8 bits are the * 1109b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot new postfix character, while the upper 12 bits are the prefix code. * 1119b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot Because the average hit ratio is only 2 (2 hash references per entry), * 1129b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot evaluating more complex keys (such as twin prime keys) does not worth it! * 1139b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot******************************************************************************/ 1149b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfootstatic int KeyItem(uint32_t Item) 1159b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot{ 1169b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot return ((Item >> 12) ^ Item) & HT_KEY_MASK; 1179b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot} 1189b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 1199b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot#ifdef DEBUG_HIT_RATE 1209b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot/****************************************************************************** 1219b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot Debugging routine to print the hit ratio - number of times the hash table * 1229b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot was tested per operation. This routine was used to test the KeyItem routine * 1239b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot******************************************************************************/ 1249b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfootvoid HashTablePrintHitRatio(void) 1259b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot{ 1269b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot printf("Hash Table Hit Ratio is %ld/%ld = %ld%%.\n", 1279b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot NumberOfMisses, NumberOfTests, 1289b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot NumberOfMisses * 100 / NumberOfTests); 1299b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot} 1309b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot#endif /* DEBUG_HIT_RATE */ 1319b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot 1329b8f8602a74a943ddc356bb11c55b4998b2b386dKeith Platfoot/* end */ 133