/src/giflib-code/gif_hash.c
Line | Count | Source (jump to first uncovered line) |
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 <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 |
29 | | static long NumberOfTests = 0, |
30 | | NumberOfMisses = 0; |
31 | | #endif /* DEBUG_HIT_RATE */ |
32 | | |
33 | | static int KeyItem(uint32_t Item); |
34 | | |
35 | | /****************************************************************************** |
36 | | Initialize HashTable - allocate the memory needed and clear it. * |
37 | | ******************************************************************************/ |
38 | | GifHashTableType *_InitHashTable(void) |
39 | 378 | { |
40 | 378 | GifHashTableType *HashTable; |
41 | | |
42 | 378 | if ((HashTable = (GifHashTableType *) malloc(sizeof(GifHashTableType))) |
43 | 378 | == NULL) |
44 | 0 | return NULL; |
45 | | |
46 | 378 | _ClearHashTable(HashTable); |
47 | | |
48 | 378 | return HashTable; |
49 | 378 | } |
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 | | ******************************************************************************/ |
55 | | void _ClearHashTable(GifHashTableType *HashTable) |
56 | 1.65k | { |
57 | 1.65k | memset(HashTable -> HTable, 0xFF, HT_SIZE * sizeof(uint32_t)); |
58 | 1.65k | } |
59 | | |
60 | | /****************************************************************************** |
61 | | Routine to insert a new Item into the HashTable. The data is assumed to be * |
62 | | new one. * |
63 | | ******************************************************************************/ |
64 | | void _InsertHashTable(GifHashTableType *HashTable, uint32_t Key, int Code) |
65 | 3.77M | { |
66 | 3.77M | int HKey = KeyItem(Key); |
67 | 3.77M | uint32_t *HTable = HashTable -> HTable; |
68 | | |
69 | | #ifdef DEBUG_HIT_RATE |
70 | | NumberOfTests++; |
71 | | NumberOfMisses++; |
72 | | #endif /* DEBUG_HIT_RATE */ |
73 | | |
74 | 7.67M | while (HT_GET_KEY(HTable[HKey]) != 0xFFFFFL) { |
75 | | #ifdef DEBUG_HIT_RATE |
76 | | NumberOfMisses++; |
77 | | #endif /* DEBUG_HIT_RATE */ |
78 | 3.90M | HKey = (HKey + 1) & HT_KEY_MASK; |
79 | 3.90M | } |
80 | 3.77M | HTable[HKey] = HT_PUT_KEY(Key) | HT_PUT_CODE(Code); |
81 | 3.77M | } |
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 | | ******************************************************************************/ |
87 | | int _ExistsHashTable(GifHashTableType *HashTable, uint32_t Key) |
88 | 7.99M | { |
89 | 7.99M | int HKey = KeyItem(Key); |
90 | 7.99M | uint32_t *HTable = HashTable -> HTable, HTKey; |
91 | | |
92 | | #ifdef DEBUG_HIT_RATE |
93 | | NumberOfTests++; |
94 | | NumberOfMisses++; |
95 | | #endif /* DEBUG_HIT_RATE */ |
96 | | |
97 | 13.5M | while ((HTKey = HT_GET_KEY(HTable[HKey])) != 0xFFFFFL) { |
98 | | #ifdef DEBUG_HIT_RATE |
99 | | NumberOfMisses++; |
100 | | #endif /* DEBUG_HIT_RATE */ |
101 | 9.78M | if (Key == HTKey) return HT_GET_CODE(HTable[HKey]); |
102 | 5.56M | HKey = (HKey + 1) & HT_KEY_MASK; |
103 | 5.56M | } |
104 | | |
105 | 3.77M | return -1; |
106 | 7.99M | } |
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 | | ******************************************************************************/ |
115 | | static int KeyItem(uint32_t Item) |
116 | 11.7M | { |
117 | 11.7M | return ((Item >> 12) ^ Item) & HT_KEY_MASK; |
118 | 11.7M | } |
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 | | ******************************************************************************/ |
125 | | void 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 */ |