1/*****************************************************************************
2
3gif_hash.c -- module to support the following operations:
4
51. InitHashTable - initialize hash table.
62. ClearHashTable - clear the hash table to an empty state.
72. InsertHashTable - insert one item into data structure.
83. ExistsHashTable - test if item exists in data structure.
9
10This module is used to hash the GIF codes during encoding.
11
12SPDX-License-Identifier: MIT
13
14*****************************************************************************/
15
16#include <stdint.h>
17#include <stdlib.h>
18#include <fcntl.h>
19#include <stdio.h>
20#include <string.h>
21
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
29static long NumberOfTests = 0,
30 NumberOfMisses = 0;
31#endif /* DEBUG_HIT_RATE */
32
33static int KeyItem(uint32_t Item);
34
35/******************************************************************************
36 Initialize HashTable - allocate the memory needed and clear it. *
37******************************************************************************/
38GifHashTableType *_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******************************************************************************/
55void _ClearHashTable(GifHashTableType *HashTable)
56{
57 memset(HashTable -> HTable, 0xFF, HT_SIZE * sizeof(uint32_t));
58}
59
60/******************************************************************************
61 Routine to insert a new Item into the HashTable. The data is assumed to be *
62 new one. *
63******************************************************************************/
64void _InsertHashTable(GifHashTableType *HashTable, uint32_t Key, int Code)
65{
66 int HKey = KeyItem(Key);
67 uint32_t *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******************************************************************************/
87int _ExistsHashTable(GifHashTableType *HashTable, uint32_t Key)
88{
89 int HKey = KeyItem(Key);
90 uint32_t *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******************************************************************************/
115static int KeyItem(uint32_t 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******************************************************************************/
125void 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
133/* end */
134