Coverage Report

Created: 2023-09-25 07:13

/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
1.36M
{
42
1.36M
  assert(shift < 32);
43
1.36M
  return (x << shift) | (x >> (-shift & 31));
44
1.36M
}
45
46
1.36M
#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
164k
{
95
164k
  const uint8_t* b = (uint8_t*) buffer;
96
97
164k
  uint32_t result = seed;
98
164k
  size_t i;
99
100
164k
  if (len == 0)
101
0
    return result;
102
103
1.52M
  for (i = len - 1; i > 0; i--)
104
1.36M
  {
105
1.36M
    result ^= ROTATE_INT32(byte_to_int32[*b], i);
106
1.36M
    b++;
107
1.36M
  }
108
109
164k
  result ^= byte_to_int32[*b];
110
164k
  return result;
111
164k
}
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
105k
{
125
105k
  YR_HASH_TABLE_ENTRY* entry;
126
105k
  YR_HASH_TABLE_ENTRY* prev_entry;
127
128
105k
  void* result;
129
130
105k
  uint32_t bucket_index = yr_hash(0, key, key_length);
131
132
105k
  if (ns != NULL)
133
27.9k
    bucket_index = yr_hash(bucket_index, (uint8_t*) ns, strlen(ns));
134
135
105k
  bucket_index = bucket_index % table->size;
136
105k
  prev_entry = NULL;
137
105k
  entry = table->buckets[bucket_index];
138
139
106k
  while (entry != NULL)
140
52.7k
  {
141
52.7k
    int key_match =
142
52.7k
        ((entry->key_length == key_length) &&
143
52.7k
         (memcmp(entry->key, key, key_length) == 0));
144
145
52.7k
    int ns_match =
146
52.7k
        ((entry->ns == ns) ||
147
52.7k
         (entry->ns != NULL && ns != NULL && strcmp(entry->ns, ns) == 0));
148
149
52.7k
    if (key_match && ns_match)
150
52.2k
    {
151
52.2k
      result = entry->value;
152
153
52.2k
      if (remove)
154
0
      {
155
0
        if (prev_entry == NULL)
156
0
          table->buckets[bucket_index] = entry->next;
157
0
        else
158
0
          prev_entry->next = entry->next;
159
160
0
        if (entry->ns != NULL)
161
0
          yr_free(entry->ns);
162
163
0
        yr_free(entry->key);
164
0
        yr_free(entry);
165
0
      }
166
167
52.2k
      return result;
168
52.2k
    }
169
170
507
    prev_entry = entry;
171
507
    entry = entry->next;
172
507
  }
173
174
53.7k
  return NULL;
175
105k
}
176
177
YR_API int yr_hash_table_create(int size, YR_HASH_TABLE** table)
178
6.75k
{
179
6.75k
  YR_HASH_TABLE* new_table;
180
6.75k
  int i;
181
182
6.75k
  new_table = (YR_HASH_TABLE*) yr_malloc(
183
6.75k
      sizeof(YR_HASH_TABLE) + size * sizeof(YR_HASH_TABLE_ENTRY*));
184
185
6.75k
  if (new_table == NULL)
186
0
    return ERROR_INSUFFICIENT_MEMORY;
187
188
6.75k
  new_table->size = size;
189
190
36.4M
  for (i = 0; i < size; i++) new_table->buckets[i] = NULL;
191
192
6.75k
  *table = new_table;
193
194
6.75k
  return ERROR_SUCCESS;
195
6.75k
}
196
197
YR_API void yr_hash_table_clean(
198
    YR_HASH_TABLE* table,
199
    YR_HASH_TABLE_FREE_VALUE_FUNC free_value)
200
14.7k
{
201
14.7k
  YR_HASH_TABLE_ENTRY* entry;
202
14.7k
  YR_HASH_TABLE_ENTRY* next_entry;
203
204
14.7k
  int i;
205
206
14.7k
  if (table == NULL)
207
0
    return;
208
209
116M
  for (i = 0; i < table->size; i++)
210
116M
  {
211
116M
    entry = table->buckets[i];
212
213
116M
    while (entry != NULL)
214
22.0k
    {
215
22.0k
      next_entry = entry->next;
216
217
22.0k
      if (free_value != NULL)
218
212
        free_value(entry->value);
219
220
22.0k
      if (entry->ns != NULL)
221
8.88k
        yr_free(entry->ns);
222
223
22.0k
      yr_free(entry->key);
224
22.0k
      yr_free(entry);
225
226
22.0k
      entry = next_entry;
227
22.0k
    }
228
229
116M
    table->buckets[i] = NULL;
230
116M
  }
231
14.7k
}
232
233
YR_API void yr_hash_table_destroy(
234
    YR_HASH_TABLE* table,
235
    YR_HASH_TABLE_FREE_VALUE_FUNC free_value)
236
6.75k
{
237
6.75k
  yr_hash_table_clean(table, free_value);
238
6.75k
  yr_free(table);
239
6.75k
}
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
8.31k
{
247
8.31k
  int result;
248
8.31k
  YR_HASH_TABLE_ENTRY* entry;
249
250
8.31k
  if (table == NULL)
251
0
    return ERROR_INTERNAL_FATAL_ERROR;
252
253
8.26M
  for (int i = 0; i < table->size; i++)
254
8.25M
  {
255
8.25M
    entry = table->buckets[i];
256
8.26M
    while (entry != NULL)
257
1.19k
    {
258
1.19k
      if ((entry->ns == NULL && ns == NULL)
259
1.19k
          || (entry->ns != NULL && ns != NULL && !strcmp(entry->ns, ns)))
260
1.19k
      {
261
1.19k
        result = iterate_func(
262
1.19k
            entry->key, entry->key_length, entry->value, data);
263
264
1.19k
        if (result != ERROR_SUCCESS)
265
276
          return result;
266
1.19k
      }
267
914
      entry = entry->next;
268
914
    }
269
8.25M
  }
270
8.04k
  return ERROR_SUCCESS;
271
8.31k
}
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
105k
{
279
105k
  return _yr_hash_table_lookup(table, key, key_length, ns, false);
280
105k
}
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
0
{
288
0
  return _yr_hash_table_lookup(table, key, key_length, ns, true);
289
0
}
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
22.0k
{
298
22.0k
  YR_HASH_TABLE_ENTRY* entry;
299
22.0k
  uint32_t bucket_index;
300
301
22.0k
  entry = (YR_HASH_TABLE_ENTRY*) yr_malloc(sizeof(YR_HASH_TABLE_ENTRY));
302
303
22.0k
  if (entry == NULL)
304
0
    return ERROR_INSUFFICIENT_MEMORY;
305
306
22.0k
  entry->key = yr_malloc(key_length);
307
308
22.0k
  if (entry->key == NULL)
309
0
  {
310
0
    yr_free(entry);
311
0
    return ERROR_INSUFFICIENT_MEMORY;
312
0
  }
313
314
22.0k
  if (ns != NULL)
315
8.88k
  {
316
8.88k
    entry->ns = yr_strdup(ns);
317
318
8.88k
    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
8.88k
  }
326
13.1k
  else
327
13.1k
  {
328
13.1k
    entry->ns = NULL;
329
13.1k
  }
330
331
22.0k
  entry->key_length = key_length;
332
22.0k
  entry->value = value;
333
334
22.0k
  memcpy(entry->key, key, key_length);
335
336
22.0k
  bucket_index = yr_hash(0, key, key_length);
337
338
22.0k
  if (ns != NULL)
339
8.88k
    bucket_index = yr_hash(bucket_index, (uint8_t*) ns, strlen(ns));
340
341
22.0k
  bucket_index = bucket_index % table->size;
342
343
22.0k
  entry->next = table->buckets[bucket_index];
344
22.0k
  table->buckets[bucket_index] = entry;
345
346
22.0k
  return ERROR_SUCCESS;
347
22.0k
}
348
349
YR_API void* yr_hash_table_lookup(
350
    YR_HASH_TABLE* table,
351
    const char* key,
352
    const char* ns)
353
17.5k
{
354
17.5k
  return yr_hash_table_lookup_raw_key(table, (void*) key, strlen(key), ns);
355
17.5k
}
356
357
YR_API void* yr_hash_table_remove(
358
    YR_HASH_TABLE* table,
359
    const char* key,
360
    const char* ns)
361
0
{
362
0
  return yr_hash_table_remove_raw_key(table, (void*) key, strlen(key), ns);
363
0
}
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
212
{
371
212
  return yr_hash_table_add_raw_key(table, (void*) key, strlen(key), ns, value);
372
212
}
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
9.13k
{
380
9.13k
  return yr_hash_table_add_uint32_raw_key(
381
9.13k
      table, (void*) key, strlen(key), ns, value);
382
9.13k
}
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
39.6k
{
389
39.6k
  return yr_hash_table_lookup_uint32_raw_key(
390
39.6k
      table, (void*) key, strlen(key), ns);
391
39.6k
}
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
21.8k
{
400
  // Don't allow values equal to UINT32_MAX or UINT32_MAX - 1.
401
21.8k
  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
21.8k
  return yr_hash_table_add_raw_key(
408
21.8k
      table, key, key_length, ns, (void*) (size_t) (value + 1));
409
21.8k
}
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
88.4k
{
417
88.4k
  void* ptr = yr_hash_table_lookup_raw_key(table, key, key_length, ns);
418
419
88.4k
  if (ptr == NULL)
420
38.0k
    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
50.4k
  return ((uint32_t) (size_t) (uint8_t*) ptr) - 1;
425
88.4k
}