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 #ifdef _WIN32
20 #include "../win32/config.h"
21 #else
22 #include "../config.h"
23 #endif
24
25 /* Find a thirty-two bit int type */
26 #ifdef HAVE_SYS_TYPES_H
27 #include <sys/types.h>
28 #endif
29
30 #ifdef __MSDOS__
31 #include <io.h>
32 #include <alloc.h>
33 #include <sys\stat.h>
34 #else
35 #include <sys/types.h>
36 #include <sys/stat.h>
37 #endif /* __MSDOS__ */
38
39 #ifdef HAVE_FCNTL_H
40 #include <fcntl.h>
41 #endif /* HAVE_FCNTL_H */
42 #include <stdio.h>
43 #include <string.h>
44 #include "gif_lib.h"
45 #include "gif_hash.h"
46 #include "gif_lib_private.h"
47
48 /* #define DEBUG_HIT_RATE Debug number of misses per hash Insert/Exists. */
49
50 #ifdef DEBUG_HIT_RATE
51 static long NumberOfTests = 0,
52 NumberOfMisses = 0;
53 #endif /* DEBUG_HIT_RATE */
54
55 static int KeyItem(UINT32 Item);
56
57 /******************************************************************************
58 * Initialize HashTable - allocate the memory needed and clear it. *
59 ******************************************************************************/
_InitHashTable(void)60 GifHashTableType *_InitHashTable(void)
61 {
62 GifHashTableType *HashTable;
63
64 if ((HashTable = (GifHashTableType *) malloc(sizeof(GifHashTableType)))
65 == NULL)
66 return NULL;
67
68 _ClearHashTable(HashTable);
69
70 return HashTable;
71 }
72
73 /******************************************************************************
74 * Routine to clear the HashTable to an empty state. *
75 * This part is a little machine depended. Use the commented part otherwise. *
76 ******************************************************************************/
_ClearHashTable(GifHashTableType * HashTable)77 void _ClearHashTable(GifHashTableType *HashTable)
78 {
79 memset(HashTable -> HTable, 0xFF, HT_SIZE * sizeof(UINT32));
80 }
81
82 /******************************************************************************
83 * Routine to insert a new Item into the HashTable. The data is assumed to be *
84 * new one. *
85 ******************************************************************************/
_InsertHashTable(GifHashTableType * HashTable,UINT32 Key,int Code)86 void _InsertHashTable(GifHashTableType *HashTable, UINT32 Key, int Code)
87 {
88 int HKey = KeyItem(Key);
89 UINT32 *HTable = HashTable -> HTable;
90
91 #ifdef DEBUG_HIT_RATE
92 NumberOfTests++;
93 NumberOfMisses++;
94 #endif /* DEBUG_HIT_RATE */
95
96 while (HT_GET_KEY(HTable[HKey]) != 0xFFFFFL) {
97 #ifdef DEBUG_HIT_RATE
98 NumberOfMisses++;
99 #endif /* DEBUG_HIT_RATE */
100 HKey = (HKey + 1) & HT_KEY_MASK;
101 }
102 HTable[HKey] = HT_PUT_KEY(Key) | HT_PUT_CODE(Code);
103 }
104
105 /******************************************************************************
106 * Routine to test if given Key exists in HashTable and if so returns its code *
107 * Returns the Code if key was found, -1 if not. *
108 ******************************************************************************/
_ExistsHashTable(GifHashTableType * HashTable,UINT32 Key)109 int _ExistsHashTable(GifHashTableType *HashTable, UINT32 Key)
110 {
111 int HKey = KeyItem(Key);
112 UINT32 *HTable = HashTable -> HTable, HTKey;
113
114 #ifdef DEBUG_HIT_RATE
115 NumberOfTests++;
116 NumberOfMisses++;
117 #endif /* DEBUG_HIT_RATE */
118
119 while ((HTKey = HT_GET_KEY(HTable[HKey])) != 0xFFFFFL) {
120 #ifdef DEBUG_HIT_RATE
121 NumberOfMisses++;
122 #endif /* DEBUG_HIT_RATE */
123 if (Key == HTKey) return HT_GET_CODE(HTable[HKey]);
124 HKey = (HKey + 1) & HT_KEY_MASK;
125 }
126
127 return -1;
128 }
129
130 /******************************************************************************
131 * Routine to generate an HKey for the hashtable out of the given unique key. *
132 * The given Key is assumed to be 20 bits as follows: lower 8 bits are the *
133 * new postfix character, while the upper 12 bits are the prefix code. *
134 * Because the average hit ratio is only 2 (2 hash references per entry), *
135 * evaluating more complex keys (such as twin prime keys) does not worth it! *
136 ******************************************************************************/
KeyItem(UINT32 Item)137 static int KeyItem(UINT32 Item)
138 {
139 return ((Item >> 12) ^ Item) & HT_KEY_MASK;
140 }
141
142 #ifdef DEBUG_HIT_RATE
143 /******************************************************************************
144 * Debugging routine to print the hit ratio - number of times the hash table *
145 * was tested per operation. This routine was used to test the KeyItem routine *
146 ******************************************************************************/
HashTablePrintHitRatio(void)147 void HashTablePrintHitRatio(void)
148 {
149 printf("Hash Table Hit Ratio is %ld/%ld = %ld%%.\n",
150 NumberOfMisses, NumberOfTests,
151 NumberOfMisses * 100 / NumberOfTests);
152 }
153 #endif /* DEBUG_HIT_RATE */
154