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