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