1 /*
2 * dict.c: dictionary of reusable strings, just used to avoid allocation
3 * and freeing operations.
4 *
5 * Copyright (C) 2003-2012 Daniel Veillard.
6 *
7 * Permission to use, copy, modify, and distribute this software for any
8 * purpose with or without fee is hereby granted, provided that the above
9 * copyright notice and this permission notice appear in all copies.
10 *
11 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
12 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
13 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE AUTHORS AND
14 * CONTRIBUTORS ACCEPT NO RESPONSIBILITY IN ANY CONCEIVABLE MANNER.
15 *
16 * Author: [email protected]
17 */
18
19 #define IN_LIBXML
20 #include "libxml.h"
21
22 #include <errno.h>
23 #include <limits.h>
24 #include <stdlib.h>
25 #include <string.h>
26
27 #include "private/dict.h"
28 #include "private/error.h"
29 #include "private/globals.h"
30 #include "private/threads.h"
31
32 #include <libxml/parser.h>
33 #include <libxml/dict.h>
34 #include <libxml/xmlmemory.h>
35 #include <libxml/xmlstring.h>
36
37 #ifndef SIZE_MAX
38 #define SIZE_MAX ((size_t) -1)
39 #endif
40
41 #define MAX_FILL_NUM 7
42 #define MAX_FILL_DENOM 8
43 #define MIN_HASH_SIZE 8
44 #define MAX_HASH_SIZE (1u << 31)
45
46 typedef struct _xmlDictStrings xmlDictStrings;
47 typedef xmlDictStrings *xmlDictStringsPtr;
48 struct _xmlDictStrings {
49 xmlDictStringsPtr next;
50 xmlChar *free;
51 xmlChar *end;
52 size_t size;
53 size_t nbStrings;
54 xmlChar array[1];
55 };
56
57 typedef xmlHashedString xmlDictEntry;
58
59 /*
60 * The entire dictionary
61 */
62 struct _xmlDict {
63 int ref_counter;
64
65 xmlDictEntry *table;
66 size_t size;
67 unsigned int nbElems;
68 xmlDictStringsPtr strings;
69
70 struct _xmlDict *subdict;
71 /* used for randomization */
72 unsigned seed;
73 /* used to impose a limit on size */
74 size_t limit;
75 };
76
77 /*
78 * A mutex for modifying the reference counter for shared
79 * dictionaries.
80 */
81 static xmlMutex xmlDictMutex;
82
83 /**
84 * xmlInitializeDict:
85 *
86 * DEPRECATED: Alias for xmlInitParser.
87 *
88 * Returns 0.
89 */
90 int
xmlInitializeDict(void)91 xmlInitializeDict(void) {
92 xmlInitParser();
93 return(0);
94 }
95
96 /**
97 * xmlInitDictInternal:
98 *
99 * Initialize mutex.
100 */
101 void
xmlInitDictInternal(void)102 xmlInitDictInternal(void) {
103 xmlInitMutex(&xmlDictMutex);
104 }
105
106 /**
107 * xmlDictCleanup:
108 *
109 * DEPRECATED: This function is a no-op. Call xmlCleanupParser
110 * to free global state but see the warnings there. xmlCleanupParser
111 * should be only called once at program exit. In most cases, you don't
112 * have call cleanup functions at all.
113 */
114 void
xmlDictCleanup(void)115 xmlDictCleanup(void) {
116 }
117
118 /**
119 * xmlCleanupDictInternal:
120 *
121 * Free the dictionary mutex.
122 */
123 void
xmlCleanupDictInternal(void)124 xmlCleanupDictInternal(void) {
125 xmlCleanupMutex(&xmlDictMutex);
126 }
127
128 /*
129 * xmlDictAddString:
130 * @dict: the dictionary
131 * @name: the name of the userdata
132 * @len: the length of the name
133 *
134 * Add the string to the array[s]
135 *
136 * Returns the pointer of the local string, or NULL in case of error.
137 */
138 static const xmlChar *
xmlDictAddString(xmlDictPtr dict,const xmlChar * name,unsigned int namelen)139 xmlDictAddString(xmlDictPtr dict, const xmlChar *name, unsigned int namelen) {
140 xmlDictStringsPtr pool;
141 const xmlChar *ret;
142 size_t size = 0; /* + sizeof(_xmlDictStrings) == 1024 */
143 size_t limit = 0;
144
145 pool = dict->strings;
146 while (pool != NULL) {
147 if ((size_t)(pool->end - pool->free) > namelen)
148 goto found_pool;
149 if (pool->size > size) size = pool->size;
150 limit += pool->size;
151 pool = pool->next;
152 }
153 /*
154 * Not found, need to allocate
155 */
156 if (pool == NULL) {
157 if ((dict->limit > 0) && (limit > dict->limit)) {
158 return(NULL);
159 }
160
161 if (size == 0) {
162 size = 1000;
163 } else {
164 if (size < (SIZE_MAX - sizeof(xmlDictStrings)) / 4)
165 size *= 4; /* exponential growth */
166 else
167 size = SIZE_MAX - sizeof(xmlDictStrings);
168 }
169 if (size / 4 < namelen) {
170 if ((size_t) namelen + 0 < (SIZE_MAX - sizeof(xmlDictStrings)) / 4)
171 size = 4 * (size_t) namelen; /* just in case ! */
172 else
173 return(NULL);
174 }
175 pool = (xmlDictStringsPtr) xmlMalloc(sizeof(xmlDictStrings) + size);
176 if (pool == NULL)
177 return(NULL);
178 pool->size = size;
179 pool->nbStrings = 0;
180 pool->free = &pool->array[0];
181 pool->end = &pool->array[size];
182 pool->next = dict->strings;
183 dict->strings = pool;
184 }
185 found_pool:
186 ret = pool->free;
187 memcpy(pool->free, name, namelen);
188 pool->free += namelen;
189 *(pool->free++) = 0;
190 pool->nbStrings++;
191 return(ret);
192 }
193
194 /*
195 * xmlDictAddQString:
196 * @dict: the dictionary
197 * @prefix: the prefix of the userdata
198 * @plen: the prefix length
199 * @name: the name of the userdata
200 * @len: the length of the name
201 *
202 * Add the QName to the array[s]
203 *
204 * Returns the pointer of the local string, or NULL in case of error.
205 */
206 static const xmlChar *
xmlDictAddQString(xmlDictPtr dict,const xmlChar * prefix,unsigned int plen,const xmlChar * name,unsigned int namelen)207 xmlDictAddQString(xmlDictPtr dict, const xmlChar *prefix, unsigned int plen,
208 const xmlChar *name, unsigned int namelen)
209 {
210 xmlDictStringsPtr pool;
211 const xmlChar *ret;
212 size_t size = 0; /* + sizeof(_xmlDictStrings) == 1024 */
213 size_t limit = 0;
214
215 pool = dict->strings;
216 while (pool != NULL) {
217 if ((size_t)(pool->end - pool->free) > namelen + plen + 1)
218 goto found_pool;
219 if (pool->size > size) size = pool->size;
220 limit += pool->size;
221 pool = pool->next;
222 }
223 /*
224 * Not found, need to allocate
225 */
226 if (pool == NULL) {
227 if ((dict->limit > 0) && (limit > dict->limit)) {
228 return(NULL);
229 }
230
231 if (size == 0) size = 1000;
232 else size *= 4; /* exponential growth */
233 if (size < 4 * (namelen + plen + 1))
234 size = 4 * (namelen + plen + 1); /* just in case ! */
235 pool = (xmlDictStringsPtr) xmlMalloc(sizeof(xmlDictStrings) + size);
236 if (pool == NULL)
237 return(NULL);
238 pool->size = size;
239 pool->nbStrings = 0;
240 pool->free = &pool->array[0];
241 pool->end = &pool->array[size];
242 pool->next = dict->strings;
243 dict->strings = pool;
244 }
245 found_pool:
246 ret = pool->free;
247 memcpy(pool->free, prefix, plen);
248 pool->free += plen;
249 *(pool->free++) = ':';
250 memcpy(pool->free, name, namelen);
251 pool->free += namelen;
252 *(pool->free++) = 0;
253 pool->nbStrings++;
254 return(ret);
255 }
256
257 /**
258 * xmlDictCreate:
259 *
260 * Create a new dictionary
261 *
262 * Returns the newly created dictionary, or NULL if an error occurred.
263 */
264 xmlDictPtr
xmlDictCreate(void)265 xmlDictCreate(void) {
266 xmlDictPtr dict;
267
268 xmlInitParser();
269
270 dict = xmlMalloc(sizeof(xmlDict));
271 if (dict == NULL)
272 return(NULL);
273 dict->ref_counter = 1;
274 dict->limit = 0;
275
276 dict->size = 0;
277 dict->nbElems = 0;
278 dict->table = NULL;
279 dict->strings = NULL;
280 dict->subdict = NULL;
281 dict->seed = xmlRandom();
282 #ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION
283 dict->seed = 0;
284 #endif
285 return(dict);
286 }
287
288 /**
289 * xmlDictCreateSub:
290 * @sub: an existing dictionary
291 *
292 * Create a new dictionary, inheriting strings from the read-only
293 * dictionary @sub. On lookup, strings are first searched in the
294 * new dictionary, then in @sub, and if not found are created in the
295 * new dictionary.
296 *
297 * Returns the newly created dictionary, or NULL if an error occurred.
298 */
299 xmlDictPtr
xmlDictCreateSub(xmlDictPtr sub)300 xmlDictCreateSub(xmlDictPtr sub) {
301 xmlDictPtr dict = xmlDictCreate();
302
303 if ((dict != NULL) && (sub != NULL)) {
304 dict->seed = sub->seed;
305 dict->subdict = sub;
306 xmlDictReference(dict->subdict);
307 }
308 return(dict);
309 }
310
311 /**
312 * xmlDictReference:
313 * @dict: the dictionary
314 *
315 * Increment the reference counter of a dictionary
316 *
317 * Returns 0 in case of success and -1 in case of error
318 */
319 int
xmlDictReference(xmlDictPtr dict)320 xmlDictReference(xmlDictPtr dict) {
321 if (dict == NULL) return -1;
322 xmlMutexLock(&xmlDictMutex);
323 dict->ref_counter++;
324 xmlMutexUnlock(&xmlDictMutex);
325 return(0);
326 }
327
328 /**
329 * xmlDictFree:
330 * @dict: the dictionary
331 *
332 * Free the hash @dict and its contents. The userdata is
333 * deallocated with @f if provided.
334 */
335 void
xmlDictFree(xmlDictPtr dict)336 xmlDictFree(xmlDictPtr dict) {
337 xmlDictStringsPtr pool, nextp;
338
339 if (dict == NULL)
340 return;
341
342 /* decrement the counter, it may be shared by a parser and docs */
343 xmlMutexLock(&xmlDictMutex);
344 dict->ref_counter--;
345 if (dict->ref_counter > 0) {
346 xmlMutexUnlock(&xmlDictMutex);
347 return;
348 }
349
350 xmlMutexUnlock(&xmlDictMutex);
351
352 if (dict->subdict != NULL) {
353 xmlDictFree(dict->subdict);
354 }
355
356 if (dict->table) {
357 xmlFree(dict->table);
358 }
359 pool = dict->strings;
360 while (pool != NULL) {
361 nextp = pool->next;
362 xmlFree(pool);
363 pool = nextp;
364 }
365 xmlFree(dict);
366 }
367
368 /**
369 * xmlDictOwns:
370 * @dict: the dictionary
371 * @str: the string
372 *
373 * check if a string is owned by the dictionary
374 *
375 * Returns 1 if true, 0 if false and -1 in case of error
376 * -1 in case of error
377 */
378 int
xmlDictOwns(xmlDictPtr dict,const xmlChar * str)379 xmlDictOwns(xmlDictPtr dict, const xmlChar *str) {
380 xmlDictStringsPtr pool;
381
382 if ((dict == NULL) || (str == NULL))
383 return(-1);
384 pool = dict->strings;
385 while (pool != NULL) {
386 if ((str >= &pool->array[0]) && (str <= pool->free))
387 return(1);
388 pool = pool->next;
389 }
390 if (dict->subdict)
391 return(xmlDictOwns(dict->subdict, str));
392 return(0);
393 }
394
395 /**
396 * xmlDictSize:
397 * @dict: the dictionary
398 *
399 * Query the number of elements installed in the hash @dict.
400 *
401 * Returns the number of elements in the dictionary or
402 * -1 in case of error
403 */
404 int
xmlDictSize(xmlDictPtr dict)405 xmlDictSize(xmlDictPtr dict) {
406 if (dict == NULL)
407 return(-1);
408 if (dict->subdict)
409 return(dict->nbElems + dict->subdict->nbElems);
410 return(dict->nbElems);
411 }
412
413 /**
414 * xmlDictSetLimit:
415 * @dict: the dictionary
416 * @limit: the limit in bytes
417 *
418 * Set a size limit for the dictionary
419 * Added in 2.9.0
420 *
421 * Returns the previous limit of the dictionary or 0
422 */
423 size_t
xmlDictSetLimit(xmlDictPtr dict,size_t limit)424 xmlDictSetLimit(xmlDictPtr dict, size_t limit) {
425 size_t ret;
426
427 if (dict == NULL)
428 return(0);
429 ret = dict->limit;
430 dict->limit = limit;
431 return(ret);
432 }
433
434 /**
435 * xmlDictGetUsage:
436 * @dict: the dictionary
437 *
438 * Get how much memory is used by a dictionary for strings
439 * Added in 2.9.0
440 *
441 * Returns the amount of strings allocated
442 */
443 size_t
xmlDictGetUsage(xmlDictPtr dict)444 xmlDictGetUsage(xmlDictPtr dict) {
445 xmlDictStringsPtr pool;
446 size_t limit = 0;
447
448 if (dict == NULL)
449 return(0);
450 pool = dict->strings;
451 while (pool != NULL) {
452 limit += pool->size;
453 pool = pool->next;
454 }
455 return(limit);
456 }
457
458 /*****************************************************************
459 *
460 * The code below was rewritten and is additionally licensed under
461 * the main license in file 'Copyright'.
462 *
463 *****************************************************************/
464
465 ATTRIBUTE_NO_SANITIZE_INTEGER
466 static unsigned
xmlDictHashName(unsigned seed,const xmlChar * data,size_t maxLen,size_t * plen)467 xmlDictHashName(unsigned seed, const xmlChar* data, size_t maxLen,
468 size_t *plen) {
469 unsigned h1, h2;
470 size_t i;
471
472 HASH_INIT(h1, h2, seed);
473
474 for (i = 0; i < maxLen && data[i]; i++) {
475 HASH_UPDATE(h1, h2, data[i]);
476 }
477
478 HASH_FINISH(h1, h2);
479
480 *plen = i;
481 return(h2 | MAX_HASH_SIZE);
482 }
483
484 ATTRIBUTE_NO_SANITIZE_INTEGER
485 static unsigned
xmlDictHashQName(unsigned seed,const xmlChar * prefix,const xmlChar * name,size_t * pplen,size_t * plen)486 xmlDictHashQName(unsigned seed, const xmlChar *prefix, const xmlChar *name,
487 size_t *pplen, size_t *plen) {
488 unsigned h1, h2;
489 size_t i;
490
491 HASH_INIT(h1, h2, seed);
492
493 for (i = 0; prefix[i] != 0; i++) {
494 HASH_UPDATE(h1, h2, prefix[i]);
495 }
496 *pplen = i;
497
498 HASH_UPDATE(h1, h2, ':');
499
500 for (i = 0; name[i] != 0; i++) {
501 HASH_UPDATE(h1, h2, name[i]);
502 }
503 *plen = i;
504
505 HASH_FINISH(h1, h2);
506
507 /*
508 * Always set the upper bit of hash values since 0 means an unoccupied
509 * bucket.
510 */
511 return(h2 | MAX_HASH_SIZE);
512 }
513
514 /**
515 * xmlDictComputeHash:
516 * @dict: dictionary
517 * @string: C string
518 *
519 * Compute the hash value of a C string.
520 *
521 * Returns the hash value.
522 */
523 unsigned
xmlDictComputeHash(const xmlDict * dict,const xmlChar * string)524 xmlDictComputeHash(const xmlDict *dict, const xmlChar *string) {
525 size_t len;
526 return(xmlDictHashName(dict->seed, string, SIZE_MAX, &len));
527 }
528
529 #define HASH_ROL31(x,n) ((x) << (n) | ((x) & 0x7FFFFFFF) >> (31 - (n)))
530
531 /**
532 * xmlDictCombineHash:
533 * @v1: first hash value
534 * @v2: second hash value
535 *
536 * Combine two hash values.
537 *
538 * Returns the combined hash value.
539 */
540 ATTRIBUTE_NO_SANITIZE_INTEGER
541 unsigned
xmlDictCombineHash(unsigned v1,unsigned v2)542 xmlDictCombineHash(unsigned v1, unsigned v2) {
543 /*
544 * The upper bit of hash values is always set, so we have to operate on
545 * 31-bit hashes here.
546 */
547 v1 ^= v2;
548 v1 += HASH_ROL31(v2, 5);
549
550 return((v1 & 0xFFFFFFFF) | 0x80000000);
551 }
552
553 /**
554 * xmlDictFindEntry:
555 * @dict: dict
556 * @prefix: optional QName prefix
557 * @name: string
558 * @len: length of string
559 * @hashValue: valid hash value of string
560 * @pfound: result of search
561 *
562 * Try to find a matching hash table entry. If an entry was found, set
563 * @found to 1 and return the entry. Otherwise, set @found to 0 and return
564 * the location where a new entry should be inserted.
565 */
566 ATTRIBUTE_NO_SANITIZE_INTEGER
567 static xmlDictEntry *
xmlDictFindEntry(const xmlDict * dict,const xmlChar * prefix,const xmlChar * name,int len,unsigned hashValue,int * pfound)568 xmlDictFindEntry(const xmlDict *dict, const xmlChar *prefix,
569 const xmlChar *name, int len, unsigned hashValue,
570 int *pfound) {
571 xmlDictEntry *entry;
572 unsigned mask, pos, displ;
573 int found = 0;
574
575 mask = dict->size - 1;
576 pos = hashValue & mask;
577 entry = &dict->table[pos];
578
579 if (entry->hashValue != 0) {
580 /*
581 * Robin hood hashing: abort if the displacement of the entry
582 * is smaller than the displacement of the key we look for.
583 * This also stops at the correct position when inserting.
584 */
585 displ = 0;
586
587 do {
588 if (entry->hashValue == hashValue) {
589 if (prefix == NULL) {
590 /*
591 * name is not necessarily null-terminated.
592 */
593 if ((strncmp((const char *) entry->name,
594 (const char *) name, len) == 0) &&
595 (entry->name[len] == 0)) {
596 found = 1;
597 break;
598 }
599 } else {
600 if (xmlStrQEqual(prefix, name, entry->name)) {
601 found = 1;
602 break;
603 }
604 }
605 }
606
607 displ++;
608 pos++;
609 entry++;
610 if ((pos & mask) == 0)
611 entry = dict->table;
612 } while ((entry->hashValue != 0) &&
613 (((pos - entry->hashValue) & mask) >= displ));
614 }
615
616 *pfound = found;
617 return(entry);
618 }
619
620 /**
621 * xmlDictGrow:
622 * @dict: dictionary
623 * @size: new size of the dictionary
624 *
625 * Resize the dictionary hash table.
626 *
627 * Returns 0 in case of success, -1 if a memory allocation failed.
628 */
629 static int
xmlDictGrow(xmlDictPtr dict,unsigned size)630 xmlDictGrow(xmlDictPtr dict, unsigned size) {
631 const xmlDictEntry *oldentry, *oldend, *end;
632 xmlDictEntry *table;
633 unsigned oldsize, i;
634
635 /* Add 0 to avoid spurious -Wtype-limits warning on 64-bit GCC */
636 if ((size_t) size + 0 > SIZE_MAX / sizeof(table[0]))
637 return(-1);
638 table = xmlMalloc(size * sizeof(table[0]));
639 if (table == NULL)
640 return(-1);
641 memset(table, 0, size * sizeof(table[0]));
642
643 oldsize = dict->size;
644 if (oldsize == 0)
645 goto done;
646
647 oldend = &dict->table[oldsize];
648 end = &table[size];
649
650 /*
651 * Robin Hood sorting order is maintained if we
652 *
653 * - compute dict indices with modulo
654 * - resize by an integer factor
655 * - start to copy from the beginning of a probe sequence
656 */
657 oldentry = dict->table;
658 while (oldentry->hashValue != 0) {
659 if (++oldentry >= oldend)
660 oldentry = dict->table;
661 }
662
663 for (i = 0; i < oldsize; i++) {
664 if (oldentry->hashValue != 0) {
665 xmlDictEntry *entry = &table[oldentry->hashValue & (size - 1)];
666
667 while (entry->hashValue != 0) {
668 if (++entry >= end)
669 entry = table;
670 }
671 *entry = *oldentry;
672 }
673
674 if (++oldentry >= oldend)
675 oldentry = dict->table;
676 }
677
678 xmlFree(dict->table);
679
680 done:
681 dict->table = table;
682 dict->size = size;
683
684 return(0);
685 }
686
687 /**
688 * xmlDictLookupInternal:
689 * @dict: dict
690 * @prefix: optional QName prefix
691 * @name: string
692 * @maybeLen: length of string or -1 if unknown
693 * @update: whether the string should be added
694 *
695 * Internal lookup and update function.
696 */
697 ATTRIBUTE_NO_SANITIZE_INTEGER
698 static const xmlDictEntry *
xmlDictLookupInternal(xmlDictPtr dict,const xmlChar * prefix,const xmlChar * name,int maybeLen,int update)699 xmlDictLookupInternal(xmlDictPtr dict, const xmlChar *prefix,
700 const xmlChar *name, int maybeLen, int update) {
701 xmlDictEntry *entry = NULL;
702 const xmlChar *ret;
703 unsigned hashValue;
704 size_t maxLen, len, plen, klen;
705 int found = 0;
706
707 if ((dict == NULL) || (name == NULL))
708 return(NULL);
709
710 maxLen = (maybeLen < 0) ? SIZE_MAX : (size_t) maybeLen;
711
712 if (prefix == NULL) {
713 hashValue = xmlDictHashName(dict->seed, name, maxLen, &len);
714 if (len > INT_MAX / 2)
715 return(NULL);
716 klen = len;
717 } else {
718 hashValue = xmlDictHashQName(dict->seed, prefix, name, &plen, &len);
719 if ((len > INT_MAX / 2) || (plen >= INT_MAX / 2 - len))
720 return(NULL);
721 klen = plen + 1 + len;
722 }
723
724 if ((dict->limit > 0) && (klen >= dict->limit))
725 return(NULL);
726
727 /*
728 * Check for an existing entry
729 */
730 if (dict->size > 0)
731 entry = xmlDictFindEntry(dict, prefix, name, klen, hashValue, &found);
732 if (found)
733 return(entry);
734
735 if ((dict->subdict != NULL) && (dict->subdict->size > 0)) {
736 xmlDictEntry *subEntry;
737 unsigned subHashValue;
738
739 if (prefix == NULL)
740 subHashValue = xmlDictHashName(dict->subdict->seed, name, len,
741 &len);
742 else
743 subHashValue = xmlDictHashQName(dict->subdict->seed, prefix, name,
744 &plen, &len);
745 subEntry = xmlDictFindEntry(dict->subdict, prefix, name, klen,
746 subHashValue, &found);
747 if (found)
748 return(subEntry);
749 }
750
751 if (!update)
752 return(NULL);
753
754 /*
755 * Grow the hash table if needed
756 */
757 if (dict->nbElems + 1 > dict->size / MAX_FILL_DENOM * MAX_FILL_NUM) {
758 unsigned newSize, mask, displ, pos;
759
760 if (dict->size == 0) {
761 newSize = MIN_HASH_SIZE;
762 } else {
763 if (dict->size >= MAX_HASH_SIZE)
764 return(NULL);
765 newSize = dict->size * 2;
766 }
767 if (xmlDictGrow(dict, newSize) != 0)
768 return(NULL);
769
770 /*
771 * Find new entry
772 */
773 mask = dict->size - 1;
774 displ = 0;
775 pos = hashValue & mask;
776 entry = &dict->table[pos];
777
778 while ((entry->hashValue != 0) &&
779 ((pos - entry->hashValue) & mask) >= displ) {
780 displ++;
781 pos++;
782 entry++;
783 if ((pos & mask) == 0)
784 entry = dict->table;
785 }
786 }
787
788 if (prefix == NULL)
789 ret = xmlDictAddString(dict, name, len);
790 else
791 ret = xmlDictAddQString(dict, prefix, plen, name, len);
792 if (ret == NULL)
793 return(NULL);
794
795 /*
796 * Shift the remainder of the probe sequence to the right
797 */
798 if (entry->hashValue != 0) {
799 const xmlDictEntry *end = &dict->table[dict->size];
800 const xmlDictEntry *cur = entry;
801
802 do {
803 cur++;
804 if (cur >= end)
805 cur = dict->table;
806 } while (cur->hashValue != 0);
807
808 if (cur < entry) {
809 /*
810 * If we traversed the end of the buffer, handle the part
811 * at the start of the buffer.
812 */
813 memmove(&dict->table[1], dict->table,
814 (char *) cur - (char *) dict->table);
815 cur = end - 1;
816 dict->table[0] = *cur;
817 }
818
819 memmove(&entry[1], entry, (char *) cur - (char *) entry);
820 }
821
822 /*
823 * Populate entry
824 */
825 entry->hashValue = hashValue;
826 entry->name = ret;
827
828 dict->nbElems++;
829
830 return(entry);
831 }
832
833 /**
834 * xmlDictLookup:
835 * @dict: dictionary
836 * @name: string key
837 * @len: length of the key, if -1 it is recomputed
838 *
839 * Lookup a string and add it to the dictionary if it wasn't found.
840 *
841 * Returns the interned copy of the string or NULL if a memory allocation
842 * failed.
843 */
844 const xmlChar *
xmlDictLookup(xmlDictPtr dict,const xmlChar * name,int len)845 xmlDictLookup(xmlDictPtr dict, const xmlChar *name, int len) {
846 const xmlDictEntry *entry;
847
848 entry = xmlDictLookupInternal(dict, NULL, name, len, 1);
849 if (entry == NULL)
850 return(NULL);
851 return(entry->name);
852 }
853
854 /**
855 * xmlDictLookupHashed:
856 * @dict: dictionary
857 * @name: string key
858 * @len: length of the key, if -1 it is recomputed
859 *
860 * Lookup a dictionary entry and add the string to the dictionary if
861 * it wasn't found.
862 *
863 * Returns the dictionary entry.
864 */
865 xmlHashedString
xmlDictLookupHashed(xmlDictPtr dict,const xmlChar * name,int len)866 xmlDictLookupHashed(xmlDictPtr dict, const xmlChar *name, int len) {
867 const xmlDictEntry *entry;
868 xmlHashedString ret;
869
870 entry = xmlDictLookupInternal(dict, NULL, name, len, 1);
871
872 if (entry == NULL) {
873 ret.name = NULL;
874 ret.hashValue = 0;
875 } else {
876 ret = *entry;
877 }
878
879 return(ret);
880 }
881
882 /**
883 * xmlDictExists:
884 * @dict: the dictionary
885 * @name: the name of the userdata
886 * @len: the length of the name, if -1 it is recomputed
887 *
888 * Check if a string exists in the dictionary.
889 *
890 * Returns the internal copy of the name or NULL if not found.
891 */
892 const xmlChar *
xmlDictExists(xmlDictPtr dict,const xmlChar * name,int len)893 xmlDictExists(xmlDictPtr dict, const xmlChar *name, int len) {
894 const xmlDictEntry *entry;
895
896 entry = xmlDictLookupInternal(dict, NULL, name, len, 0);
897 if (entry == NULL)
898 return(NULL);
899 return(entry->name);
900 }
901
902 /**
903 * xmlDictQLookup:
904 * @dict: the dictionary
905 * @prefix: the prefix
906 * @name: the name
907 *
908 * Lookup the QName @prefix:@name and add it to the dictionary if
909 * it wasn't found.
910 *
911 * Returns the interned copy of the string or NULL if a memory allocation
912 * failed.
913 */
914 const xmlChar *
xmlDictQLookup(xmlDictPtr dict,const xmlChar * prefix,const xmlChar * name)915 xmlDictQLookup(xmlDictPtr dict, const xmlChar *prefix, const xmlChar *name) {
916 const xmlDictEntry *entry;
917
918 entry = xmlDictLookupInternal(dict, prefix, name, -1, 1);
919 if (entry == NULL)
920 return(NULL);
921 return(entry->name);
922 }
923
924 /*
925 * Pseudo-random generator
926 */
927
928 #ifdef _WIN32
929 #define WIN32_LEAN_AND_MEAN
930 #include <windows.h>
931 #include <bcrypt.h>
932 #elif HAVE_DECL_GETENTROPY
933 #include <unistd.h>
934 #include <sys/random.h>
935 #else
936 #include <time.h>
937 #endif
938
939 static xmlMutex xmlRngMutex;
940
941 static unsigned globalRngState[2];
942
943 /*
944 * xmlInitRandom:
945 *
946 * Initialize the PRNG.
947 */
948 ATTRIBUTE_NO_SANITIZE_INTEGER
949 void
xmlInitRandom(void)950 xmlInitRandom(void) {
951 xmlInitMutex(&xmlRngMutex);
952
953 {
954 #ifdef _WIN32
955 NTSTATUS status;
956
957 status = BCryptGenRandom(NULL, (unsigned char *) globalRngState,
958 sizeof(globalRngState),
959 BCRYPT_USE_SYSTEM_PREFERRED_RNG);
960 if (!BCRYPT_SUCCESS(status))
961 xmlAbort("libxml2: BCryptGenRandom failed with error code %lu\n",
962 GetLastError());
963 #elif HAVE_DECL_GETENTROPY
964 while (1) {
965 if (getentropy(globalRngState, sizeof(globalRngState)) == 0)
966 break;
967
968 if (errno != EINTR)
969 xmlAbort("libxml2: getentropy failed with error code %d\n",
970 errno);
971 }
972 #else
973 int var;
974
975 globalRngState[0] =
976 (unsigned) time(NULL) ^
977 HASH_ROL((unsigned) ((size_t) &xmlInitRandom & 0xFFFFFFFF), 8);
978 globalRngState[1] =
979 HASH_ROL((unsigned) ((size_t) &xmlRngMutex & 0xFFFFFFFF), 16) ^
980 HASH_ROL((unsigned) ((size_t) &var & 0xFFFFFFFF), 24);
981 #endif
982 }
983 }
984
985 /*
986 * xmlCleanupRandom:
987 *
988 * Clean up PRNG globals.
989 */
990 void
xmlCleanupRandom(void)991 xmlCleanupRandom(void) {
992 xmlCleanupMutex(&xmlRngMutex);
993 }
994
995 ATTRIBUTE_NO_SANITIZE_INTEGER
996 static unsigned
xoroshiro64ss(unsigned * s)997 xoroshiro64ss(unsigned *s) {
998 unsigned s0 = s[0];
999 unsigned s1 = s[1];
1000 unsigned result = HASH_ROL(s0 * 0x9E3779BB, 5) * 5;
1001
1002 s1 ^= s0;
1003 s[0] = HASH_ROL(s0, 26) ^ s1 ^ (s1 << 9);
1004 s[1] = HASH_ROL(s1, 13);
1005
1006 return(result & 0xFFFFFFFF);
1007 }
1008
1009 /*
1010 * xmlGlobalRandom:
1011 *
1012 * Generate a pseudo-random value using the global PRNG.
1013 *
1014 * Returns a random value.
1015 */
1016 unsigned
xmlGlobalRandom(void)1017 xmlGlobalRandom(void) {
1018 unsigned ret;
1019
1020 xmlMutexLock(&xmlRngMutex);
1021 ret = xoroshiro64ss(globalRngState);
1022 xmlMutexUnlock(&xmlRngMutex);
1023
1024 return(ret);
1025 }
1026
1027 /*
1028 * xmlRandom:
1029 *
1030 * Generate a pseudo-random value using the thread-local PRNG.
1031 *
1032 * Returns a random value.
1033 */
1034 unsigned
xmlRandom(void)1035 xmlRandom(void) {
1036 #ifdef LIBXML_THREAD_ENABLED
1037 return(xoroshiro64ss(xmlGetLocalRngState()));
1038 #else
1039 return(xmlGlobalRandom());
1040 #endif
1041 }
1042
1043