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