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
|
/*****************************************************************************
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.
*****************************************************************************/
// SPDX-License-Identifier: MIT
// SPDX-File-Copyright-Txt: (C) Copyright 1989 Gershon Elber
#include <fcntl.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "gif_hash.h"
#include "gif_lib.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 */
|
