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