Coverage Report

Created: 2023-03-26 07:33

/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 */