1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
|
/*****************************************************************************
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 */
|
