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 | } |