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