Coverage Report

Created: 2023-03-26 07:37

/src/yara/libyara/hash.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
Copyright (c) 2013. The YARA Authors. All Rights Reserved.
3
4
Redistribution and use in source and binary forms, with or without modification,
5
are permitted provided that the following conditions are met:
6
7
1. Redistributions of source code must retain the above copyright notice, this
8
list of conditions and the following disclaimer.
9
10
2. Redistributions in binary form must reproduce the above copyright notice,
11
this list of conditions and the following disclaimer in the documentation and/or
12
other materials provided with the distribution.
13
14
3. Neither the name of the copyright holder nor the names of its contributors
15
may be used to endorse or promote products derived from this software without
16
specific prior written permission.
17
18
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
19
ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
20
WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
21
DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR
22
ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
23
(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
24
LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
25
ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
27
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28
*/
29
30
#include <assert.h>
31
#include <string.h>
32
#include <yara/error.h>
33
#include <yara/hash.h>
34
#include <yara/integers.h>
35
#include <yara/mem.h>
36
#include <yara/utils.h>
37
38
// Constant-time left rotate that does not invoke undefined behavior.
39
// http://blog.regehr.org/archives/1063
40
static uint32_t rotl32(uint32_t x, uint32_t shift)
41
377k
{
42
377k
  assert(shift < 32);
43
377k
  return (x << shift) | (x >> (-shift & 31));
44
377k
}
45
46
377k
#define ROTATE_INT32(x, shift) rotl32(x, shift % 32)
47
48
uint32_t byte_to_int32[] = {
49
    0xC3113E7F, 0x4C353C5F, 0x7423810B, 0x258D264E, 0xDAD39DED, 0x75D0B694,
50
    0x98CE1216, 0x93334482, 0xC5C48EA5, 0xF57E0E8B, 0x5D7F3723, 0x396B1B24,
51
    0xA8883D9F, 0xB2A74A00, 0xF8E171AE, 0x3F01FBAB, 0x5C1840CB, 0xDDD833C4,
52
    0x8D8CCA34, 0x32EF223A, 0x1A05B871, 0x9A9B6BFC, 0x50406A0C, 0xE7E1FC04,
53
    0x5E07D7F6, 0x80B83660, 0x20892A62, 0xB2C6FEA6, 0x6CEC7CAA, 0x182F764B,
54
    0x3B0353E7, 0x57FC2520, 0x4B6812D4, 0xACB654E4, 0x23C75C04, 0xB1DCD731,
55
    0xE3AF0733, 0xF2366D39, 0xC729671B, 0xFF3BE6F2, 0xABA37E34, 0x3CDAFA38,
56
    0xAAD18D03, 0xA8D35345, 0x08E9A92C, 0xF9324059, 0x42D821BE, 0x1BC152DD,
57
    0x5588811C, 0x874A1F9A, 0x6E83E9CD, 0xDA6F3AF8, 0x965D4670, 0xA7A565C0,
58
    0x68D8A9AF, 0xFC8FD8FD, 0x8FF99FF9, 0x4C9B42AE, 0x2D066A8D, 0x4D1802F7,
59
    0x557032B2, 0x12BCF371, 0xDC29D5AE, 0x72EA361F, 0xE2835B0B, 0xDFC58966,
60
    0x13B0F34D, 0x3FA02BCD, 0xBF282E3D, 0x7DC877F5, 0xF4848A32, 0x861E35F5,
61
    0x7FFA0D7F, 0x515F2E4E, 0x6B235D5C, 0x55F46E24, 0x35AD2C99, 0x072654A8,
62
    0x05163F0F, 0x9317B11A, 0xAED1FC10, 0x989444F0, 0xDB3E1814, 0x446C0CF1,
63
    0x660BF511, 0x2F227D3A, 0xFDBA0539, 0xC649E621, 0x5204D7CE, 0x5FA386D0,
64
    0xE5F22005, 0x97B6C8A1, 0x4AB69EC2, 0x5C7CA70D, 0x39A48EC6, 0x7BACF378,
65
    0x8D0ED3D1, 0xE39DE582, 0xC5FBE2AB, 0x37E3D2D0, 0x06F44724, 0x73144144,
66
    0xBA57E905, 0xB05B4307, 0xAEED8D97, 0xA68CCAC4, 0xE30DA57E, 0xED0F194B,
67
    0x8C2B9B7A, 0x814575D5, 0x79588493, 0x81D3712A, 0x3FA892F2, 0x80F0BB94,
68
    0x44EAF51A, 0x4E05F1D4, 0xFC69F858, 0x775E8D60, 0x22B20DD7, 0x170A87EA,
69
    0x1077DE52, 0x3D5EC9FB, 0x0B6EB1E5, 0xF2F9CCAF, 0xA76C7DEB, 0xD8C2D873,
70
    0xF438C592, 0x6239FEEC, 0x26D3D2A9, 0x30F6FADF, 0x4B2984CC, 0x6257F3DA,
71
    0x0E0583E2, 0x143E5E61, 0xBB2732BF, 0x9653217A, 0x027A84EA, 0x95C9AE8B,
72
    0x89B8B82B, 0x9F286485, 0x29F622FE, 0x52A3196B, 0x8392D95F, 0x33A79167,
73
    0xF5DEE92A, 0x6E397DB9, 0x11931C01, 0x8DD2CD3B, 0xF9E6003D, 0xAB955AF4,
74
    0xD38725F9, 0xDCF6F8AE, 0x7667A958, 0xE67AD995, 0xB7CF979A, 0xD88EBE5B,
75
    0x5BA889F0, 0x078BDD90, 0x447238F9, 0x3135F672, 0x187B95A8, 0x0B7D5751,
76
    0xACD59D2A, 0x9C5D1929, 0x579E5022, 0xEA90499B, 0x59901800, 0x82237DB5,
77
    0x7A375509, 0xACA9A22A, 0xEC96E649, 0x69339DB0, 0x081D0D9B, 0xD72FB8B9,
78
    0xA4184653, 0xC057321D, 0xED19CAB9, 0xB48F1E3E, 0xB9DAC51E, 0xDAED2FC7,
79
    0x7598CBBD, 0x208DF346, 0x044BE6EC, 0x1C63E6EB, 0xA15F64C1, 0xE024A061,
80
    0x68309584, 0x0758A68D, 0xF274E9AE, 0x0ABEA0CC, 0xED4FB267, 0x63D6EC46,
81
    0x9F28E026, 0xF0694A17, 0x9D6E9115, 0xC4600FAD, 0x5B121E99, 0xD6B4A13B,
82
    0xF5364B8A, 0x8514B254, 0x0182F8DD, 0xDB09F90B, 0x78C70B32, 0xD8EC3B02,
83
    0x8CD7084D, 0xA4439838, 0x72F35A3D, 0x200B48A5, 0xE2351444, 0xA5552F5F,
84
    0xD8C1E746, 0x0FE5EF3C, 0xB6A47063, 0x61F4E68B, 0x08FED99B, 0x7E461445,
85
    0x43CB8380, 0x28BA03C8, 0x21A7A2E2, 0x43437ED6, 0x2A9E6670, 0x89B4A106,
86
    0xC6C2F4EE, 0x9C4063CC, 0x2FA0DF6C, 0xB54DC409, 0xCF01538F, 0x616431D7,
87
    0x02CB0E4D, 0x44FFF425, 0xAAD5188E, 0x0742E9BC, 0xFFF41353, 0x130F0A15,
88
    0x787BDC10, 0x4A327B72, 0x702989F7, 0x5F704798, 0x8156A1BB, 0x2BCA3E74,
89
    0x1911A8C4, 0x5E1F27D3, 0x07949DC7, 0xF24C2056, 0xB4299EE6, 0x9C7045D9,
90
    0xA8BF6307, 0x7454AAD2, 0x256425E5, 0xD87DEF67, 0xCFE95452, 0xE7548DF7,
91
    0xA84956C7, 0xD8402C60, 0xCFBD0373, 0x6B6CDAFE};
92
93
uint32_t yr_hash(uint32_t seed, const void* buffer, size_t len)
94
98.1k
{
95
98.1k
  const uint8_t* b = (uint8_t*) buffer;
96
97
98.1k
  uint32_t result = seed;
98
98.1k
  size_t i;
99
100
98.1k
  if (len == 0)
101
0
    return result;
102
103
475k
  for (i = len - 1; i > 0; i--)
104
377k
  {
105
377k
    result ^= ROTATE_INT32(byte_to_int32[*b], i);
106
377k
    b++;
107
377k
  }
108
109
98.1k
  result ^= byte_to_int32[*b];
110
98.1k
  return result;
111
98.1k
}
112
113
////////////////////////////////////////////////////////////////////////////////
114
// Return the value associated to a given key and optionally remove it from
115
// the hash table. Key can be any byte sequence, namespace is a null-terminated
116
// string, and remove is a boolean.
117
//
118
static void* _yr_hash_table_lookup(
119
    YR_HASH_TABLE* table,
120
    const void* key,
121
    size_t key_length,
122
    const char* ns,
123
    int remove)
124
90.5k
{
125
90.5k
  YR_HASH_TABLE_ENTRY* entry;
126
90.5k
  YR_HASH_TABLE_ENTRY* prev_entry;
127
128
90.5k
  void* result;
129
130
90.5k
  uint32_t bucket_index = yr_hash(0, key, key_length);
131
132
90.5k
  if (ns != NULL)
133
6
    bucket_index = yr_hash(bucket_index, (uint8_t*) ns, strlen(ns));
134
135
90.5k
  bucket_index = bucket_index % table->size;
136
90.5k
  prev_entry = NULL;
137
90.5k
  entry = table->buckets[bucket_index];
138
139
90.5k
  while (entry != NULL)
140
15.0k
  {
141
15.0k
    int key_match =
142
15.0k
        ((entry->key_length == key_length) &&
143
15.0k
         (memcmp(entry->key, key, key_length) == 0));
144
145
15.0k
    int ns_match =
146
15.0k
        ((entry->ns == ns) ||
147
15.0k
         (entry->ns != NULL && ns != NULL && strcmp(entry->ns, ns) == 0));
148
149
15.0k
    if (key_match && ns_match)
150
15.0k
    {
151
15.0k
      result = entry->value;
152
153
15.0k
      if (remove)
154
7.54k
      {
155
7.54k
        if (prev_entry == NULL)
156
7.54k
          table->buckets[bucket_index] = entry->next;
157
0
        else
158
0
          prev_entry->next = entry->next;
159
160
7.54k
        if (entry->ns != NULL)
161
0
          yr_free(entry->ns);
162
163
7.54k
        yr_free(entry->key);
164
7.54k
        yr_free(entry);
165
7.54k
      }
166
167
15.0k
      return result;
168
15.0k
    }
169
170
0
    prev_entry = entry;
171
0
    entry = entry->next;
172
0
  }
173
174
75.4k
  return NULL;
175
90.5k
}
176
177
YR_API int yr_hash_table_create(int size, YR_HASH_TABLE** table)
178
7.55k
{
179
7.55k
  YR_HASH_TABLE* new_table;
180
7.55k
  int i;
181
182
7.55k
  new_table = (YR_HASH_TABLE*) yr_malloc(
183
7.55k
      sizeof(YR_HASH_TABLE) + size * sizeof(YR_HASH_TABLE_ENTRY*));
184
185
7.55k
  if (new_table == NULL)
186
0
    return ERROR_INSUFFICIENT_MEMORY;
187
188
7.55k
  new_table->size = size;
189
190
544k
  for (i = 0; i < size; i++) new_table->buckets[i] = NULL;
191
192
7.55k
  *table = new_table;
193
194
7.55k
  return ERROR_SUCCESS;
195
7.55k
}
196
197
YR_API void yr_hash_table_clean(
198
    YR_HASH_TABLE* table,
199
    YR_HASH_TABLE_FREE_VALUE_FUNC free_value)
200
7.55k
{
201
7.55k
  YR_HASH_TABLE_ENTRY* entry;
202
7.55k
  YR_HASH_TABLE_ENTRY* next_entry;
203
204
7.55k
  int i;
205
206
7.55k
  if (table == NULL)
207
0
    return;
208
209
564k
  for (i = 0; i < table->size; i++)
210
556k
  {
211
556k
    entry = table->buckets[i];
212
213
556k
    while (entry != NULL)
214
14
    {
215
14
      next_entry = entry->next;
216
217
14
      if (free_value != NULL)
218
2
        free_value(entry->value);
219
220
14
      if (entry->ns != NULL)
221
4
        yr_free(entry->ns);
222
223
14
      yr_free(entry->key);
224
14
      yr_free(entry);
225
226
14
      entry = next_entry;
227
14
    }
228
229
556k
    table->buckets[i] = NULL;
230
556k
  }
231
7.55k
}
232
233
YR_API void yr_hash_table_destroy(
234
    YR_HASH_TABLE* table,
235
    YR_HASH_TABLE_FREE_VALUE_FUNC free_value)
236
7.55k
{
237
7.55k
  yr_hash_table_clean(table, free_value);
238
7.55k
  yr_free(table);
239
7.55k
}
240
241
YR_API int yr_hash_table_iterate(
242
    YR_HASH_TABLE* table,
243
    const char* ns,
244
    YR_HASH_TABLE_ITERATE_FUNC iterate_func,
245
    void* data)
246
2
{
247
2
  int result;
248
2
  YR_HASH_TABLE_ENTRY* entry;
249
250
2
  if (table == NULL)
251
0
    return ERROR_INTERNAL_FATAL_ERROR;
252
253
2.00k
  for (int i = 0; i < table->size; i++)
254
2.00k
  {
255
2.00k
    entry = table->buckets[i];
256
2.00k
    while (entry != NULL)
257
0
    {
258
0
      if ((entry->ns == NULL && ns == NULL)
259
0
          || (entry->ns != NULL && ns != NULL && !strcmp(entry->ns, ns)))
260
0
      {
261
0
        result = iterate_func(
262
0
            entry->key, entry->key_length, entry->value, data);
263
264
0
        if (result != ERROR_SUCCESS)
265
0
          return result;
266
0
      }
267
0
      entry = entry->next;
268
0
    }
269
2.00k
  }
270
2
  return ERROR_SUCCESS;
271
2
}
272
273
YR_API void* yr_hash_table_lookup_raw_key(
274
    YR_HASH_TABLE* table,
275
    const void* key,
276
    size_t key_length,
277
    const char* ns)
278
15.1k
{
279
15.1k
  return _yr_hash_table_lookup(table, key, key_length, ns, false);
280
15.1k
}
281
282
YR_API void* yr_hash_table_remove_raw_key(
283
    YR_HASH_TABLE* table,
284
    const void* key,
285
    size_t key_length,
286
    const char* ns)
287
75.4k
{
288
75.4k
  return _yr_hash_table_lookup(table, key, key_length, ns, true);
289
75.4k
}
290
291
YR_API int yr_hash_table_add_raw_key(
292
    YR_HASH_TABLE* table,
293
    const void* key,
294
    size_t key_length,
295
    const char* ns,
296
    void* value)
297
7.55k
{
298
7.55k
  YR_HASH_TABLE_ENTRY* entry;
299
7.55k
  uint32_t bucket_index;
300
301
7.55k
  entry = (YR_HASH_TABLE_ENTRY*) yr_malloc(sizeof(YR_HASH_TABLE_ENTRY));
302
303
7.55k
  if (entry == NULL)
304
0
    return ERROR_INSUFFICIENT_MEMORY;
305
306
7.55k
  entry->key = yr_malloc(key_length);
307
308
7.55k
  if (entry->key == NULL)
309
0
  {
310
0
    yr_free(entry);
311
0
    return ERROR_INSUFFICIENT_MEMORY;
312
0
  }
313
314
7.55k
  if (ns != NULL)
315
4
  {
316
4
    entry->ns = yr_strdup(ns);
317
318
4
    if (entry->ns == NULL)
319
0
    {
320
0
      yr_free(entry->key);
321
0
      yr_free(entry);
322
323
0
      return ERROR_INSUFFICIENT_MEMORY;
324
0
    }
325
4
  }
326
7.55k
  else
327
7.55k
  {
328
7.55k
    entry->ns = NULL;
329
7.55k
  }
330
331
7.55k
  entry->key_length = key_length;
332
7.55k
  entry->value = value;
333
334
7.55k
  memcpy(entry->key, key, key_length);
335
336
7.55k
  bucket_index = yr_hash(0, key, key_length);
337
338
7.55k
  if (ns != NULL)
339
4
    bucket_index = yr_hash(bucket_index, (uint8_t*) ns, strlen(ns));
340
341
7.55k
  bucket_index = bucket_index % table->size;
342
343
7.55k
  entry->next = table->buckets[bucket_index];
344
7.55k
  table->buckets[bucket_index] = entry;
345
346
7.55k
  return ERROR_SUCCESS;
347
7.55k
}
348
349
YR_API void* yr_hash_table_lookup(
350
    YR_HASH_TABLE* table,
351
    const char* key,
352
    const char* ns)
353
15.0k
{
354
15.0k
  return yr_hash_table_lookup_raw_key(table, (void*) key, strlen(key), ns);
355
15.0k
}
356
357
YR_API void* yr_hash_table_remove(
358
    YR_HASH_TABLE* table,
359
    const char* key,
360
    const char* ns)
361
75.4k
{
362
75.4k
  return yr_hash_table_remove_raw_key(table, (void*) key, strlen(key), ns);
363
75.4k
}
364
365
YR_API int yr_hash_table_add(
366
    YR_HASH_TABLE* table,
367
    const char* key,
368
    const char* ns,
369
    void* value)
370
7.54k
{
371
7.54k
  return yr_hash_table_add_raw_key(table, (void*) key, strlen(key), ns, value);
372
7.54k
}
373
374
YR_API int yr_hash_table_add_uint32(
375
    YR_HASH_TABLE* table,
376
    const char* key,
377
    const char* ns,
378
    uint32_t value)
379
2
{
380
2
  return yr_hash_table_add_uint32_raw_key(
381
2
      table, (void*) key, strlen(key), ns, value);
382
2
}
383
384
YR_API uint32_t yr_hash_table_lookup_uint32(
385
    YR_HASH_TABLE* table,
386
    const char* key,
387
    const char* ns)
388
2
{
389
2
  return yr_hash_table_lookup_uint32_raw_key(
390
2
      table, (void*) key, strlen(key), ns);
391
2
}
392
393
YR_API int yr_hash_table_add_uint32_raw_key(
394
    YR_HASH_TABLE* table,
395
    const void* key,
396
    size_t key_length,
397
    const char* ns,
398
    uint32_t value)
399
12
{
400
  // Don't allow values equal to UINT32_MAX or UINT32_MAX - 1.
401
12
  if (value >= UINT32_MAX - 1)
402
0
    return ERROR_INVALID_ARGUMENT;
403
404
  // Add +1 to the value in order to avoid putting a NULL pointer in the
405
  // hash table once the integer is casted to a pointer. This is undone
406
  // by yr_hash_table_lookup_uint32.
407
12
  return yr_hash_table_add_raw_key(
408
12
      table, key, key_length, ns, (void*) (size_t) (value + 1));
409
12
}
410
411
YR_API uint32_t yr_hash_table_lookup_uint32_raw_key(
412
    YR_HASH_TABLE* table,
413
    const void* key,
414
    size_t key_length,
415
    const char* ns)
416
14
{
417
14
  void* ptr = yr_hash_table_lookup_raw_key(table, key, key_length, ns);
418
419
14
  if (ptr == NULL)
420
12
    return UINT32_MAX;
421
422
  // Remove one from the pointe in order to get the original value.
423
  // See comment in yr_hash_table_add_uint32_raw_key.
424
2
  return ((uint32_t) (size_t) (uint8_t*) ptr) - 1;
425
14
}