Roll libxml from b8961a75 to 7a2d412f 2023-10-31 wellnhofer@aevum.de parser: Copy default namespace in xmlParseBalancedChunkMemory 2023-10-31 wellnhofer@aevum.de parser: Copy namespaces in xmlParseBalancedChunkMemory 2023-10-28 wellnhofer@aevum.de encoding: Fix decoding of large chunks 2023-10-24 wellnhofer@aevum.de Update NEWS 2023-10-24 wellnhofer@aevum.de error: Make more xmlError structs constant 2023-10-23 daniel.garcia@suse.com python: Make it compatible with python3.12 2023-10-22 wellnhofer@aevum.de tests: Also test xmlNextChar in testchar.c 2023-10-22 wellnhofer@aevum.de parser: Remove redundant IS_CHAR check in xmlCurrentChar 2023-08-09 wellnhofer@aevum.de parser: Stop switching to ISO-8859-1 on encoding errors 2023-10-22 wellnhofer@aevum.de tests: Start with testparser.c for extra tests 2023-10-22 wellnhofer@aevum.de parser: Fix buffer shrinking when push parsing 2023-10-18 wellnhofer@aevum.de threads: Fix --with-thread-alloc 2023-10-14 wellnhofer@aevum.de fuzz: Raise rss_limit_mb 2023-10-14 wellnhofer@aevum.de fuzz: Test xmlTextReaderRead after EOF or failure 2023-10-14 wellnhofer@aevum.de fuzz: Test XML_PARSE_XINCLUDE | XML_PARSE_VALID 2023-10-14 wellnhofer@aevum.de parser: Fix stack handling in xmlParseTryOrFinish 2023-10-11 wellnhofer@aevum.de dict: Fix integer overflow in xmlDictAddString 2023-10-11 wellnhofer@aevum.de buf: Also reset input in error case 2023-10-11 wellnhofer@aevum.de parser: Don't overwrite error state in xmlParseTextDecl 2023-10-09 wellnhofer@aevum.de parser: Fix memory leak in xmlLoadEntityContent 2023-10-08 wellnhofer@aevum.de parser: Also grow comment buffer if SAX is disabled 2023-10-08 wellnhofer@aevum.de parser: Fix error handling in xmlLoadEntityContent 2023-10-06 wellnhofer@aevum.de parser: Fix regression when push parsing parameter entities 2023-10-06 wellnhofer@aevum.de parser: Protect against quadratic default attribute expansion 2023-10-05 wellnhofer@aevum.de parser: Make XML_PARSE_NSCLEAN option work again 2023-10-05 wellnhofer@aevum.de parser: Support encoded external PEs in entity values 2023-10-05 wellnhofer@aevum.de parser: Missing checks for disableSAX 2023-10-06 wellnhofer@aevum.de tests: Handle entities in SAX tests 2023-10-06 wellnhofer@aevum.de entities: Make xmlFreeEntity public 2023-10-05 wellnhofer@aevum.de parser: Acknowledge that entities with namespaces are broken 2023-10-02 wellnhofer@aevum.de examples: Don't use sprintf 2023-10-02 wellnhofer@aevum.de encoding: Suppress -Wcast-align warnings 2023-10-02 wellnhofer@aevum.de dict: Compare strings with strncmp 2023-10-02 wellnhofer@aevum.de parser: Fix initialization of namespace data 2023-10-02 wellnhofer@aevum.de parser: Fix error handling in xmlParseQNameHashed 2023-09-30 wellnhofer@aevum.de malloc-fail: Fix memory leak in xmlParseBalancedChunkMemoryInternal 2023-09-30 wellnhofer@aevum.de dict: Fix null-deref with empty subdict 2023-09-30 wellnhofer@aevum.de malloc-fail: Grow hash tables before making allocations 2023-09-30 wellnhofer@aevum.de xinclude: Expand comment about fuzz timeouts 2023-09-30 wellnhofer@aevum.de fuzz: Disable XML_PARSE_SAX1 option in xml fuzzer 2023-09-29 wellnhofer@aevum.de doc: Add notes about runtest to MAINTAINERS.md 2023-09-29 wellnhofer@aevum.de legacy: Add private declarations for stubs 2023-09-29 wellnhofer@aevum.de encoding: Fix infinite loop in xmlCharEncInput 2023-09-29 wellnhofer@aevum.de parser: Use hash tables to avoid quadratic behavior 2023-09-27 wellnhofer@aevum.de tests: Add more tests for redefined attributes 2023-09-25 wellnhofer@aevum.de parser: Introduce xmlParseQNameHashed 2023-09-25 wellnhofer@aevum.de parser: Don't skip CR in xmlCurrentChar 2023-09-25 wellnhofer@aevum.de dict: Internal API to look up hash values 2023-09-11 wellnhofer@aevum.de dict: Rewrite dictionary hash table code 2023-09-16 wellnhofer@aevum.de hash: Rewrite hash table code 2023-09-12 wellnhofer@aevum.de hash: Add hash table tests 2023-09-16 wellnhofer@aevum.de dict: Separate RNG code 2023-09-16 wellnhofer@aevum.de tests: Add ATTRIBUTE_NO_SANITIZE_INTEGER macro 2023-09-25 wellnhofer@aevum.de string: Fix UTF-8 validation in xmlGetUTF8Char 2023-09-23 wellnhofer@aevum.de malloc-fail: Report malloc failure in xmlFARegExec 2023-09-28 wellnhofer@aevum.de include: Add more missing stdio.h includes Bug: 934413 Change-Id: I6fb176d76dba9a9adf411395fa5f6b950b52920a Reviewed-on: https://chromium-review.googlesource.com/c/chromium/src/+/4985186 Reviewed-by: David Baron <dbaron@chromium.org> Commit-Queue: Joey Arhar <jarhar@chromium.org> Cr-Commit-Position: refs/heads/main@{#1219084} NOKEYCHECK=True GitOrigin-RevId: 871f8ae9b65ce2679b0bc0be36902d65edf0c1e4
diff --git a/README.chromium b/README.chromium index 33cfec9..9fea49f 100644 --- a/README.chromium +++ b/README.chromium
@@ -1,6 +1,6 @@ Name: libxml URL: http://xmlsoft.org -Version: b8961a75e96c302713326e94782d2dcc2e08624c +Version: 7a2d412f681fa4847c5351d7944a1de6959685da CPEPrefix: cpe:/a:xmlsoft:libxml2:2.11.0 License: MIT License File: src/Copyright
diff --git a/src/Copyright b/src/Copyright index d613185..c058f02 100644 --- a/src/Copyright +++ b/src/Copyright
@@ -1,4 +1,4 @@ -Except where otherwise noted in the source code (e.g. the files hash.c, +Except where otherwise noted in the source code (e.g. the files dict.c, list.c and the trio files, which are covered by a similar licence but with different Copyright notices) all the files are:
diff --git a/src/Makefile.am b/src/Makefile.am index 1c08480..0a49d37 100644 --- a/src/Makefile.am +++ b/src/Makefile.am
@@ -24,6 +24,7 @@ testchar \ testdict \ testlimits \ + testparser \ testrecurse bin_PROGRAMS = xmllint xmlcatalog @@ -140,6 +141,10 @@ testdict_DEPENDENCIES = $(DEPS) testdict_LDADD= $(LDADDS) +testparser_SOURCES=testparser.c +testparser_DEPENDENCIES = $(DEPS) +testparser_LDADD= $(LDADDS) + runsuite_SOURCES=runsuite.c runsuite_DEPENDENCIES = $(DEPS) runsuite_LDADD= $(LDADDS) @@ -193,6 +198,7 @@ $(CHECKER) ./testapi$(EXEEXT) $(CHECKER) ./testchar$(EXEEXT) $(CHECKER) ./testdict$(EXEEXT) + $(CHECKER) ./testparser$(EXEEXT) $(CHECKER) ./testModule$(EXEEXT) $(CHECKER) ./testThreads$(EXEEXT) $(CHECKER) ./runxmlconf$(EXEEXT)
diff --git a/src/NEWS b/src/NEWS index 53a8419..1111a6a 100644 --- a/src/NEWS +++ b/src/NEWS
@@ -4,6 +4,10 @@ ### Major changes +Most of the known issues leading to quadratic behavior in the XML parser +were fixed. Internal hash tables were rewritten to reduce memory +consumption. + Starting with this release, it should be enough to add the --with-legacy configuration option to provide maximum ABI compatibility. For example, if a code module was removed from the default configuration, the option @@ -12,7 +16,9 @@ libxml2 will now store global variables in thread-local storage if supported by the compiler. This avoids allocating the data lazily which can result in a fatal error condition. A new API function xmlCheckThreadLocalStorage -was added so the allocation can be checked earlier. +was added so the allocation can be checked earlier if compiler TLS is not +supported. To prepare for future improvements, some API functions now expect +or return a const xmlError struct. Several cyclic dependencies in public header files were fixed. As a result, certain headers won't include other headers as before. @@ -32,6 +38,224 @@ Schemas which previous versions erroneously accepted will now be rejected. +### Regressions + +- threads: Fix --with-thread-alloc +- xinclude: Fix 'last' pointer in xmlXIncludeCopyNode + +### Deprecations + +- globals: Deprecate xmlLastError +- parser: Deprecate global parser options +- win32: Deprecate old Windows build system + +### Bug fixes + +- parser: Stop switching to ISO-8859-1 on encoding errors +- parser: Support encoded external PEs in entity values +- string: Fix UTF-8 validation in xmlGetUTF8Char +- SAX2: Allow multiple top-level elements +- parser: Update line number after coalescing text nodes +- parser: Check for truncated multi-byte sequences + +### Improvements + +- error: Make more xmlError structs constant +- parser: Remove redundant IS_CHAR check in xmlCurrentChar +- parser: Fix stack handling in xmlParseTryOrFinish +- parser: Protect against quadratic default attribute expansion +- parser: Missing checks for disableSAX +- entities: Make xmlFreeEntity public +- examples: Don't use sprintf +- encoding: Suppress -Wcast-align warnings +- parser: Use hash tables to avoid quadratic behavior +- parser: Don't skip CR in xmlCurrentChar +- dict: Rewrite dictionary hash table code +- hash: Rewrite hash table code +- malloc-fail: Report malloc failure in xmlFARegExec +- malloc-fail: Report malloc failure in xmlRegEpxFromParse +- parser: Simplify xmlStringCurrentChar +- regexp: Fix status codes and handle invalid UTF-8 +- error: Make xmlGetLastError return a const error +- html: Fix logic in htmlAutoClose +- globals: Move globals back to correct header files +- globals: Use thread-local storage if available +- globals: Rework global state destruction on Windows +- globals: Define globals using macros +- globals: Introduce xmlCheckThreadLocalStorage +- globals: Make xmlGlobalState private +- threads: Move library initialization code to threads.c +- debug: Remove debugging code +- globals: Move code from threads.c to globals.c +- parser: Avoid undefined behavior in xmlParseStartTag2 +- schemas: Fix memory leak of annotations in notations +- dict: Update hash function +- dict: Use thread-local storage for PRNG state +- dict: Use xoroshiro64** as PRNG +- xmllint: Fix error messages +- parser: Fix detection of null bytes +- parser: Improve error handling in push parser +- parser: Don't check inputNr in xmlParseTryOrFinish +- parser: Remove push parser debugging code +- tree: Fix copying of DTDs +- legacy: Add stubs for disabled modules +- parser: Allow to set maximum amplification factor +- entities: Don't change doc when encoding entities +- parser: Never use UTF-8 encoding handler +- encoding: Remove debugging code +- malloc-fail: Fix unsigned integer overflow in xmlTextReaderPushData +- html: Remove encoding hack in htmlCreateFileParserCtxt +- parser: Decode all data in xmlCharEncInput +- parser: Stream data when reading from memory +- parser: Optimize xmlLoadEntityContent +- parser: Don't overwrite EOF parser state +- parser: Simplify input pointer updates +- parser: Don't reinitialize parser input members +- encoding: Move rawconsumed accounting to xmlCharEncInput +- parser: Rework encoding detection +- parser: Always create UTF-8 in xmlParseReference +- html: Remove some debugging code in htmlParseTryOrFinish +- malloc-fail: Fix memory leak in xmlCompileAttributeTest +- parser: Fix potential use-after-free in xmlParseCharDataInternal +- parser: Recover more input from encoding errors +- malloc-fail: Handle malloc failures in xmlAddEncodingAlias +- malloc-fail: Fix null-deref with xmllint --copy +- xpath: Ignore entity ref nodes when computing node hash +- malloc-fail: Fix null deref after xmlXIncludeNewRef +- SAX: Always validate xml:ids +- Stop using sprintf +- Fix compiler warning on GCC < 8 +- regexp: Fix determinism checks +- regexp: Fix checks for eliminated transitions +- regexp: Simplify xmlFAReduceEpsilonTransitions +- regexp: Fix cycle check in xmlFAReduceEpsilonTransitions +- schemas: Fix filename in xmlSchemaValidateFile +- schemas: Fix line numbers in streaming validation +- writer: Add error check in xmlTextWriterEndDocument +- encoding: Stop calling xmlEncodingErr +- xmlIO: Remove some calls to xmlIOErr +- parser: Improve handling of encoding and IO errors +- parser: Move xmlFatalErr to parserInternals.c +- encoding: Rework error codes +- .gitignore: Split up and rearrange .gitignore files +- .gitignore: Add runsuite.log +- Stop calling xmlMemoryDump +- examples: Don't call xmlCleanupParser and xmlMemoryDump +- xpath: Remove remaining references to valueFrame + +### Portability + +- python: Make it compatible with python3.12 (Daniel Garcia Moreno) + +### Build systems + +- cmake: Check whether static linking dependencies found in config files + (James Le Cuirot) +- autotools: Make --with-minimum disable lzma support +- build: Remove some GCC warnings +- Handle NOCONFIG case when setting locations from CMake target properties + (Markus Rickert) +- cmake: Generate better pkg-config file for SYSROOT builds under CMake + (James Le Cuirot) +- autoconf: Include non-pkg-config dependency flags in the pkg-config file + (James Le Cuirot) +- autoconf: Don't bake build time CFLAGS into pkg-config file (James Le Cuirot) +- build: Generate better pkg-config files for static-only builds (James + Le Cuirot) +- build: Generate better pkg-config file for SYSROOT builds (James Le Cuirot) +- autoconf: Allow custom --with-icu configure option + +### Tests + +- tests: Also test xmlNextChar in testchar.c +- tests: Start with testparser.c for extra tests +- fuzz: Raise rss_limit_mb +- fuzz: Test xmlTextReaderRead after EOF or failure +- fuzz: Test XML_PARSE_XINCLUDE | XML_PARSE_VALID +- tests: Handle entities in SAX tests +- fuzz: Disable XML_PARSE_SAX1 option in xml fuzzer +- tests: Add more tests for redefined attributes +- hash: Add hash table tests +- tests: Add ATTRIBUTE_NO_SANITIZE_INTEGER macro +- fuzz: Allow to fuzz without push, reader or output modules +- gitlab-ci: Add a "medium" config build +- python: Fix tests on MinGW +- test: Add push parser test with overridden encoding +- testapi: test_xmlSAXDefaultVersion() leaves xmlSAX2DefaultVersionValue set + to 1 with LIBXML_SAX1_ENABLED (David Kilzer) +- gitlab-ci: Lower _XOPEN_SOURCE value +- testapi: Don't set http_proxy environment variable +- test: Add push parser tests for split UTF-8 sequences +- xinclude: Lower initial table size when fuzzing +- tests: Test streaming schema validation +- runtest: Skip element name in schema error messages + +### Documentation + +- doc: Add notes about runtest to MAINTAINERS.md +- doc: Don't document internal macros in xmlversion.h +- doc: Allow 'unsigned' without 'int' +- doc: Improve documentation of configuration options + + +v2.11.5: Aug 9 2023 + +### Regressions + +- parser: Make xmlSwitchEncoding always skip the BOM +- autotools: Improve iconv check + +### Bug fixes + +- valid: Fix c1->parent pointer in xmlCopyDocElementContent +- encoding: Always call ucnv_convertEx with flush set to false + +### Portability + +- autotools: fix Python module file ext for cygwin/msys2 (Christoph Reiter) + +### Tests + +- runtest: Fix compilation without LIBXML_HTML_ENABLED + + +v2.11.4: May 18 2023 + +Fixes a serious regression. + +- parser: Fix regression when push parsing UTF-8 sequences + + +v2.11.3: May 11 2023 + +Fixes more regressions. + +- xinclude: Fix false positives in inclusion loop detection +- autotools: Fix ICU detection +- parser: Fix "huge input lookup" error with push parser +- xpath: Fix build without LIBXML_XPATH_ENABLED +- hash: Fix possible startup crash with old libxslt versions +- autoconf: fix iconv library paths (Mike Dalessio) + + +v2.11.2: May 5 2023 + +Fix regressions. + +- threads: Fix startup crash with weak symbol hack +- win32: Don't depend on removed .def file +- schemas: Fix memory leak in xmlSchemaValidateStream + + +v2.11.1: Apr 30 2023 + +Fixes build and ABI issues. + +- cmake: Fix va_copy detection (Luca Niccoli) +- libxml.m4: Fix quoting +- Link with --undefined-version +- libxml2.syms: Revert removal of version information + v2.11.0: Apr 28 2023
diff --git a/src/SAX2.c b/src/SAX2.c index e9cd21b..e20ec88 100644 --- a/src/SAX2.c +++ b/src/SAX2.c
@@ -1870,8 +1870,12 @@ /* * Note: if prefix == NULL, the attribute is not in the default namespace */ - if (prefix != NULL) - namespace = xmlSearchNs(ctxt->myDoc, ctxt->node, prefix); + if (prefix != NULL) { + namespace = xmlParserNsLookupSax(ctxt, prefix); + if ((namespace == NULL) && (xmlStrEqual(prefix, BAD_CAST "xml"))) { + namespace = xmlSearchNs(ctxt->myDoc, ctxt->node, prefix); + } + } /* * allocate the node @@ -2201,6 +2205,9 @@ */ continue; } + + xmlParserNsUpdateSax(ctxt, pref, ns); + #ifdef LIBXML_VALID_ENABLED if ((!ctxt->html) && ctxt->validate && ctxt->wellFormed && ctxt->myDoc && ctxt->myDoc->intSubset) { @@ -2242,7 +2249,7 @@ * Note that, if prefix is NULL, this searches for the default Ns */ if ((URI != NULL) && (ret->ns == NULL)) { - ret->ns = xmlSearchNs(ctxt->myDoc, parent, prefix); + ret->ns = xmlParserNsLookupSax(ctxt, prefix); if ((ret->ns == NULL) && (xmlStrEqual(prefix, BAD_CAST "xml"))) { ret->ns = xmlSearchNs(ctxt->myDoc, ret, prefix); }
diff --git a/src/buf.c b/src/buf.c index e0afd79..266395f 100644 --- a/src/buf.c +++ b/src/buf.c
@@ -1017,8 +1017,12 @@ */ int xmlBufResetInput(xmlBufPtr buf, xmlParserInputPtr input) { - if ((input == NULL) || (buf == NULL) || (buf->error)) + if (input == NULL) return(-1); + if ((buf == NULL) || (buf->error)) { + input->base = input->cur = input->end = BAD_CAST ""; + return(-1); + } CHECK_COMPAT(buf) input->base = input->cur = buf->content; input->end = &buf->content[buf->use];
diff --git a/src/configure.ac b/src/configure.ac index c3071b7..4fac7b2 100644 --- a/src/configure.ac +++ b/src/configure.ac
@@ -519,7 +519,7 @@ fi # warnings we'd like to see - AM_CFLAGS="${AM_CFLAGS} -pedantic -Wall -Wextra -Wshadow -Wpointer-arith -Wcast-align -Wwrite-strings -Waggregate-return -Wstrict-prototypes -Wmissing-prototypes" + AM_CFLAGS="${AM_CFLAGS} -pedantic -Wall -Wextra -Wshadow -Wpointer-arith -Wcast-align -Wwrite-strings -Wstrict-prototypes -Wmissing-prototypes" # warnings we'd like to suppress AM_CFLAGS="${AM_CFLAGS} -Wno-long-long -Wno-format-extra-args" case "${host}" in
diff --git a/src/dict.c b/src/dict.c index c804939..d4ce383 100644 --- a/src/dict.c +++ b/src/dict.c
@@ -29,64 +29,16 @@ #include <libxml/parser.h> #include <libxml/dict.h> #include <libxml/xmlmemory.h> -#include <libxml/xmlerror.h> +#include <libxml/xmlstring.h> -/* - * Following http://www.ocert.org/advisories/ocert-2011-003.html - * it seems that having hash randomization might be a good idea - * when using XML with untrusted data - * Note1: that it works correctly only if compiled with WITH_BIG_KEY - * which is the default. - * Note2: the fast function used for a small dict won't protect very - * well but since the attack is based on growing a very big hash - * list we will use the BigKey algo as soon as the hash size grows - * over MIN_DICT_SIZE so this actually works - */ -#if !defined(FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION) -#define DICT_RANDOMIZATION +#ifndef SIZE_MAX + #define SIZE_MAX ((size_t) -1) #endif -/* #define DEBUG_GROW */ -/* #define DICT_DEBUG_PATTERNS */ - -#define MAX_HASH_LEN 16 -#define MAX_FILL 2 -#define GROWTH_FACTOR 4 -#define MIN_DICT_SIZE 128 -#define WITH_BIG_KEY - -#ifdef WITH_BIG_KEY -#define xmlDictComputeKey(dict, name, len) \ - (((dict)->size == MIN_DICT_SIZE) ? \ - xmlDictComputeFastKey(name, len, (dict)->seed) : \ - xmlDictComputeBigKey(name, len, (dict)->seed)) - -#define xmlDictComputeQKey(dict, prefix, plen, name, len) \ - (((prefix) == NULL) ? \ - (xmlDictComputeKey(dict, name, len)) : \ - (((dict)->size == MIN_DICT_SIZE) ? \ - xmlDictComputeFastQKey(prefix, plen, name, len, (dict)->seed) : \ - xmlDictComputeBigQKey(prefix, plen, name, len, (dict)->seed))) - -#else /* !WITH_BIG_KEY */ -#define xmlDictComputeKey(dict, name, len) \ - xmlDictComputeFastKey(name, len, (dict)->seed) -#define xmlDictComputeQKey(dict, prefix, plen, name, len) \ - xmlDictComputeFastQKey(prefix, plen, name, len, (dict)->seed) -#endif /* WITH_BIG_KEY */ - -/* - * An entry in the dictionary - */ -typedef struct _xmlDictEntry xmlDictEntry; -typedef xmlDictEntry *xmlDictEntryPtr; -struct _xmlDictEntry { - struct _xmlDictEntry *next; - const xmlChar *name; - unsigned int len; - int valid; - unsigned okey; -}; +#define MAX_FILL_NUM 7 +#define MAX_FILL_DENOM 8 +#define MIN_HASH_SIZE 8 +#define MAX_HASH_SIZE (1u << 31) typedef struct _xmlDictStrings xmlDictStrings; typedef xmlDictStrings *xmlDictStringsPtr; @@ -98,13 +50,16 @@ size_t nbStrings; xmlChar array[1]; }; + +typedef xmlHashedString xmlDictEntry; + /* * The entire dictionary */ struct _xmlDict { int ref_counter; - struct _xmlDictEntry *dict; + xmlDictEntry *table; size_t size; unsigned int nbElems; xmlDictStringsPtr strings; @@ -122,16 +77,6 @@ */ static xmlMutex xmlDictMutex; -/* - * Internal data for random function, protected by xmlDictMutex - */ -static unsigned globalRngState[2]; - -#ifdef XML_THREAD_LOCAL -XML_THREAD_LOCAL static int localRngInitialized = 0; -XML_THREAD_LOCAL static unsigned localRngState[2]; -#endif - /** * xmlInitializeDict: * @@ -146,64 +91,11 @@ /** * xmlInitializeDict: * - * Initialize mutex and global PRNG seed. + * Initialize mutex. */ -#ifdef __clang__ -ATTRIBUTE_NO_SANITIZE("unsigned-integer-overflow") -ATTRIBUTE_NO_SANITIZE("unsigned-shift-base") -#endif void xmlInitDictInternal(void) { - int var; - xmlInitMutex(&xmlDictMutex); - - /* TODO: Get seed values from system PRNG */ - - globalRngState[0] = (unsigned) time(NULL) ^ - HASH_ROL((unsigned) (size_t) &xmlInitializeDict, 8); - globalRngState[1] = HASH_ROL((unsigned) (size_t) &xmlDictMutex, 16) ^ - HASH_ROL((unsigned) (size_t) &var, 24); -} - -#ifdef __clang__ -ATTRIBUTE_NO_SANITIZE("unsigned-integer-overflow") -ATTRIBUTE_NO_SANITIZE("unsigned-shift-base") -#endif -static unsigned -xoroshiro64ss(unsigned *s) { - unsigned s0 = s[0]; - unsigned s1 = s[1]; - unsigned result = HASH_ROL(s0 * 0x9E3779BB, 5) * 5; - - s1 ^= s0; - s[0] = HASH_ROL(s0, 26) ^ s1 ^ (s1 << 9); - s[1] = HASH_ROL(s1, 13); - - return(result & 0xFFFFFFFF); -} - -unsigned -xmlRandom(void) { -#ifdef XML_THREAD_LOCAL - if (!localRngInitialized) { - xmlMutexLock(&xmlDictMutex); - localRngState[0] = xoroshiro64ss(globalRngState); - localRngState[1] = xoroshiro64ss(globalRngState); - localRngInitialized = 1; - xmlMutexUnlock(&xmlDictMutex); - } - - return(xoroshiro64ss(localRngState)); -#else - unsigned ret; - - xmlMutexLock(&xmlDictMutex); - ret = xoroshiro64ss(globalRngState); - xmlMutexUnlock(&xmlDictMutex); - - return(ret); -#endif } /** @@ -245,9 +137,6 @@ size_t size = 0; /* + sizeof(_xmlDictStrings) == 1024 */ size_t limit = 0; -#ifdef DICT_DEBUG_PATTERNS - fprintf(stderr, "-"); -#endif pool = dict->strings; while (pool != NULL) { if ((size_t)(pool->end - pool->free) > namelen) @@ -264,10 +153,20 @@ return(NULL); } - if (size == 0) size = 1000; - else size *= 4; /* exponential growth */ - if (size < 4 * namelen) - size = 4 * namelen; /* just in case ! */ + if (size == 0) { + size = 1000; + } else { + if (size < (SIZE_MAX - sizeof(xmlDictStrings)) / 4) + size *= 4; /* exponential growth */ + else + size = SIZE_MAX - sizeof(xmlDictStrings); + } + if (size / 4 < namelen) { + if ((size_t) namelen + 0 < (SIZE_MAX - sizeof(xmlDictStrings)) / 4) + size = 4 * (size_t) namelen; /* just in case ! */ + else + return(NULL); + } pool = (xmlDictStringsPtr) xmlMalloc(sizeof(xmlDictStrings) + size); if (pool == NULL) return(NULL); @@ -277,9 +176,6 @@ pool->end = &pool->array[size]; pool->next = dict->strings; dict->strings = pool; -#ifdef DICT_DEBUG_PATTERNS - fprintf(stderr, "+"); -#endif } found_pool: ret = pool->free; @@ -311,11 +207,6 @@ size_t size = 0; /* + sizeof(_xmlDictStrings) == 1024 */ size_t limit = 0; - if (prefix == NULL) return(xmlDictAddString(dict, name, namelen)); - -#ifdef DICT_DEBUG_PATTERNS - fprintf(stderr, "="); -#endif pool = dict->strings; while (pool != NULL) { if ((size_t)(pool->end - pool->free) > namelen + plen + 1) @@ -345,9 +236,6 @@ pool->end = &pool->array[size]; pool->next = dict->strings; dict->strings = pool; -#ifdef DICT_DEBUG_PATTERNS - fprintf(stderr, "+"); -#endif } found_pool: ret = pool->free; @@ -361,207 +249,6 @@ return(ret); } -#ifdef WITH_BIG_KEY -/* - * xmlDictComputeBigKey: - * - * Calculate a hash key using a good hash function that works well for - * larger hash table sizes. - */ - -#ifdef __clang__ -ATTRIBUTE_NO_SANITIZE("unsigned-integer-overflow") -ATTRIBUTE_NO_SANITIZE("unsigned-shift-base") -#endif -static unsigned -xmlDictComputeBigKey(const xmlChar* data, int namelen, unsigned seed) { - unsigned h1, h2; - int i; - - if (namelen <= 0 || data == NULL) return(0); - - HASH_INIT(h1, h2, seed); - - for (i = 0; i < namelen; i++) { - HASH_UPDATE(h1, h2, data[i]); - } - - HASH_FINISH(h1, h2); - - return h2; -} - -/* - * xmlDictComputeBigQKey: - * - * Calculate a hash key for two strings using a good hash function - * that works well for larger hash table sizes. - * - * Hash function by "One-at-a-Time Hash" see - * http://burtleburtle.net/bob/hash/doobs.html - * - * Neither of the two strings must be NULL. - */ -#ifdef __clang__ -ATTRIBUTE_NO_SANITIZE("unsigned-integer-overflow") -ATTRIBUTE_NO_SANITIZE("unsigned-shift-base") -#endif -static unsigned -xmlDictComputeBigQKey(const xmlChar *prefix, int plen, - const xmlChar *name, int len, unsigned seed) -{ - unsigned h1, h2; - int i; - - HASH_INIT(h1, h2, seed); - - for (i = 0; i < plen; i++) { - HASH_UPDATE(h1, h2, prefix[i]); - } - HASH_UPDATE(h1, h2, ':'); - - for (i = 0; i < len; i++) { - HASH_UPDATE(h1, h2, name[i]); - } - - HASH_FINISH(h1, h2); - - return h2; -} -#endif /* WITH_BIG_KEY */ - -/* - * xmlDictComputeFastKey: - * - * Calculate a hash key using a fast hash function that works well - * for low hash table fill. - */ -#ifdef __clang__ -ATTRIBUTE_NO_SANITIZE("unsigned-integer-overflow") -ATTRIBUTE_NO_SANITIZE("unsigned-shift-base") -#endif -static unsigned -xmlDictComputeFastKey(const xmlChar *name, int namelen, unsigned seed) { - unsigned value = seed; - - if ((name == NULL) || (namelen <= 0)) - return(value); - value += *name; - value <<= 5; - if (namelen > 10) { - value += name[namelen - 1]; - namelen = 10; - } - switch (namelen) { - case 10: value += name[9]; - /* Falls through. */ - case 9: value += name[8]; - /* Falls through. */ - case 8: value += name[7]; - /* Falls through. */ - case 7: value += name[6]; - /* Falls through. */ - case 6: value += name[5]; - /* Falls through. */ - case 5: value += name[4]; - /* Falls through. */ - case 4: value += name[3]; - /* Falls through. */ - case 3: value += name[2]; - /* Falls through. */ - case 2: value += name[1]; - /* Falls through. */ - default: break; - } - return(value); -} - -/* - * xmlDictComputeFastQKey: - * - * Calculate a hash key for two strings using a fast hash function - * that works well for low hash table fill. - * - * Neither of the two strings must be NULL. - */ -#ifdef __clang__ -ATTRIBUTE_NO_SANITIZE("unsigned-integer-overflow") -ATTRIBUTE_NO_SANITIZE("unsigned-shift-base") -#endif -static unsigned -xmlDictComputeFastQKey(const xmlChar *prefix, int plen, - const xmlChar *name, int len, unsigned seed) -{ - unsigned value = seed; - - if (plen == 0) - value += 30 * ':'; - else - value += 30 * (*prefix); - - if (len > 10) { - int offset = len - (plen + 1 + 1); - if (offset < 0) - offset = len - (10 + 1); - value += name[offset]; - len = 10; - if (plen > 10) - plen = 10; - } - switch (plen) { - case 10: value += prefix[9]; - /* Falls through. */ - case 9: value += prefix[8]; - /* Falls through. */ - case 8: value += prefix[7]; - /* Falls through. */ - case 7: value += prefix[6]; - /* Falls through. */ - case 6: value += prefix[5]; - /* Falls through. */ - case 5: value += prefix[4]; - /* Falls through. */ - case 4: value += prefix[3]; - /* Falls through. */ - case 3: value += prefix[2]; - /* Falls through. */ - case 2: value += prefix[1]; - /* Falls through. */ - case 1: value += prefix[0]; - /* Falls through. */ - default: break; - } - len -= plen; - if (len > 0) { - value += ':'; - len--; - } - switch (len) { - case 10: value += name[9]; - /* Falls through. */ - case 9: value += name[8]; - /* Falls through. */ - case 8: value += name[7]; - /* Falls through. */ - case 7: value += name[6]; - /* Falls through. */ - case 6: value += name[5]; - /* Falls through. */ - case 5: value += name[4]; - /* Falls through. */ - case 4: value += name[3]; - /* Falls through. */ - case 3: value += name[2]; - /* Falls through. */ - case 2: value += name[1]; - /* Falls through. */ - case 1: value += name[0]; - /* Falls through. */ - default: break; - } - return(value); -} - /** * xmlDictCreate: * @@ -575,32 +262,22 @@ xmlInitParser(); -#ifdef DICT_DEBUG_PATTERNS - fprintf(stderr, "C"); -#endif - dict = xmlMalloc(sizeof(xmlDict)); - if (dict) { - dict->ref_counter = 1; - dict->limit = 0; + if (dict == NULL) + return(NULL); + dict->ref_counter = 1; + dict->limit = 0; - dict->size = MIN_DICT_SIZE; - dict->nbElems = 0; - dict->dict = xmlMalloc(MIN_DICT_SIZE * sizeof(xmlDictEntry)); - dict->strings = NULL; - dict->subdict = NULL; - if (dict->dict) { - memset(dict->dict, 0, MIN_DICT_SIZE * sizeof(xmlDictEntry)); -#ifdef DICT_RANDOMIZATION - dict->seed = xmlRandom(); -#else - dict->seed = 0; + dict->size = 0; + dict->nbElems = 0; + dict->table = NULL; + dict->strings = NULL; + dict->subdict = NULL; + dict->seed = xmlRandom(); +#ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION + dict->seed = 0; #endif - return(dict); - } - xmlFree(dict); - } - return(NULL); + return(dict); } /** @@ -619,9 +296,6 @@ xmlDictPtr dict = xmlDictCreate(); if ((dict != NULL) && (sub != NULL)) { -#ifdef DICT_DEBUG_PATTERNS - fprintf(stderr, "R"); -#endif dict->seed = sub->seed; dict->subdict = sub; xmlDictReference(dict->subdict); @@ -647,139 +321,6 @@ } /** - * xmlDictGrow: - * @dict: the dictionary - * @size: the new size of the dictionary - * - * resize the dictionary - * - * Returns 0 in case of success, -1 in case of failure - */ -static int -xmlDictGrow(xmlDictPtr dict, size_t size) { - unsigned key, okey; - size_t oldsize, i; - xmlDictEntryPtr iter, next; - struct _xmlDictEntry *olddict; -#ifdef DEBUG_GROW - unsigned nbElem = 0; -#endif - int ret = 0; - int keep_keys = 1; - - if (dict == NULL) - return(-1); - oldsize = dict->size; - if (size <= oldsize) - return(0); - -#ifdef DICT_DEBUG_PATTERNS - fprintf(stderr, "*"); -#endif - - olddict = dict->dict; - if (olddict == NULL) - return(-1); - if (oldsize == MIN_DICT_SIZE) - keep_keys = 0; - - dict->dict = xmlMalloc(size * sizeof(xmlDictEntry)); - if (dict->dict == NULL) { - dict->dict = olddict; - return(-1); - } - memset(dict->dict, 0, size * sizeof(xmlDictEntry)); - dict->size = size; - - /* If the two loops are merged, there would be situations where - a new entry needs to allocated and data copied into it from - the main dict. It is nicer to run through the array twice, first - copying all the elements in the main array (less probability of - allocate) and then the rest, so we only free in the second loop. - */ - for (i = 0; i < oldsize; i++) { - if (olddict[i].valid == 0) - continue; - - if (keep_keys) - okey = olddict[i].okey; - else - okey = xmlDictComputeKey(dict, olddict[i].name, olddict[i].len); - key = okey % dict->size; - - if (dict->dict[key].valid == 0) { - memcpy(&(dict->dict[key]), &(olddict[i]), sizeof(xmlDictEntry)); - dict->dict[key].next = NULL; - dict->dict[key].okey = okey; - } else { - xmlDictEntryPtr entry; - - entry = xmlMalloc(sizeof(xmlDictEntry)); - if (entry != NULL) { - entry->name = olddict[i].name; - entry->len = olddict[i].len; - entry->okey = okey; - entry->next = dict->dict[key].next; - entry->valid = 1; - dict->dict[key].next = entry; - } else { - /* - * we don't have much ways to alert from here - * result is losing an entry and unicity guarantee - */ - ret = -1; - } - } -#ifdef DEBUG_GROW - nbElem++; -#endif - } - - for (i = 0; i < oldsize; i++) { - iter = olddict[i].next; - while (iter) { - next = iter->next; - - /* - * put back the entry in the new dict - */ - - if (keep_keys) - okey = iter->okey; - else - okey = xmlDictComputeKey(dict, iter->name, iter->len); - key = okey % dict->size; - if (dict->dict[key].valid == 0) { - memcpy(&(dict->dict[key]), iter, sizeof(xmlDictEntry)); - dict->dict[key].next = NULL; - dict->dict[key].valid = 1; - dict->dict[key].okey = okey; - xmlFree(iter); - } else { - iter->next = dict->dict[key].next; - iter->okey = okey; - dict->dict[key].next = iter; - } - -#ifdef DEBUG_GROW - nbElem++; -#endif - - iter = next; - } - } - - xmlFree(olddict); - -#ifdef DEBUG_GROW - xmlGenericError(xmlGenericErrorContext, - "xmlDictGrow : from %lu to %lu, %u elems\n", oldsize, size, nbElem); -#endif - - return(ret); -} - -/** * xmlDictFree: * @dict: the dictionary * @@ -788,10 +329,6 @@ */ void xmlDictFree(xmlDictPtr dict) { - size_t i; - xmlDictEntryPtr iter; - xmlDictEntryPtr next; - int inside_dict = 0; xmlDictStringsPtr pool, nextp; if (dict == NULL) @@ -811,22 +348,8 @@ xmlDictFree(dict->subdict); } - if (dict->dict) { - for(i = 0; ((i < dict->size) && (dict->nbElems > 0)); i++) { - iter = &(dict->dict[i]); - if (iter->valid == 0) - continue; - inside_dict = 1; - while (iter) { - next = iter->next; - if (!inside_dict) - xmlFree(iter); - dict->nbElems--; - inside_dict = 0; - iter = next; - } - } - xmlFree(dict->dict); + if (dict->table) { + xmlFree(dict->table); } pool = dict->strings; while (pool != NULL) { @@ -838,367 +361,6 @@ } /** - * xmlDictLookup: - * @dict: the dictionary - * @name: the name of the userdata - * @len: the length of the name, if -1 it is recomputed - * - * Add the @name to the dictionary @dict if not present. - * - * Returns the internal copy of the name or NULL in case of internal error - */ -const xmlChar * -xmlDictLookup(xmlDictPtr dict, const xmlChar *name, int len) { - unsigned key, okey, nbi = 0; - xmlDictEntryPtr entry; - xmlDictEntryPtr insert; - const xmlChar *ret; - size_t l; - - if ((dict == NULL) || (name == NULL)) - return(NULL); - - if (len < 0) - l = strlen((const char *) name); - else - l = len; - - if (((dict->limit > 0) && (l >= dict->limit)) || - (l > INT_MAX / 2)) - return(NULL); - - /* - * Check for duplicate and insertion location. - */ - okey = xmlDictComputeKey(dict, name, l); - key = okey % dict->size; - if (dict->dict[key].valid == 0) { - insert = NULL; - } else { - for (insert = &(dict->dict[key]); insert->next != NULL; - insert = insert->next) { -#ifdef __GNUC__ - if ((insert->okey == okey) && (insert->len == l)) { - if (!memcmp(insert->name, name, l)) - return(insert->name); - } -#else - if ((insert->okey == okey) && (insert->len == l) && - (!xmlStrncmp(insert->name, name, l))) - return(insert->name); -#endif - nbi++; - } -#ifdef __GNUC__ - if ((insert->okey == okey) && (insert->len == l)) { - if (!memcmp(insert->name, name, l)) - return(insert->name); - } -#else - if ((insert->okey == okey) && (insert->len == l) && - (!xmlStrncmp(insert->name, name, l))) - return(insert->name); -#endif - } - - if (dict->subdict) { - unsigned skey; - - /* we cannot always reuse the same okey for the subdict */ - if (((dict->size == MIN_DICT_SIZE) && - (dict->subdict->size != MIN_DICT_SIZE)) || - ((dict->size != MIN_DICT_SIZE) && - (dict->subdict->size == MIN_DICT_SIZE))) - skey = xmlDictComputeKey(dict->subdict, name, l); - else - skey = okey; - - key = skey % dict->subdict->size; - if (dict->subdict->dict[key].valid != 0) { - xmlDictEntryPtr tmp; - - for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL; - tmp = tmp->next) { -#ifdef __GNUC__ - if ((tmp->okey == skey) && (tmp->len == l)) { - if (!memcmp(tmp->name, name, l)) - return(tmp->name); - } -#else - if ((tmp->okey == skey) && (tmp->len == l) && - (!xmlStrncmp(tmp->name, name, l))) - return(tmp->name); -#endif - nbi++; - } -#ifdef __GNUC__ - if ((tmp->okey == skey) && (tmp->len == l)) { - if (!memcmp(tmp->name, name, l)) - return(tmp->name); - } -#else - if ((tmp->okey == skey) && (tmp->len == l) && - (!xmlStrncmp(tmp->name, name, l))) - return(tmp->name); -#endif - } - key = okey % dict->size; - } - - ret = xmlDictAddString(dict, name, l); - if (ret == NULL) - return(NULL); - if (insert == NULL) { - entry = &(dict->dict[key]); - } else { - entry = xmlMalloc(sizeof(xmlDictEntry)); - if (entry == NULL) - return(NULL); - } - entry->name = ret; - entry->len = l; - entry->next = NULL; - entry->valid = 1; - entry->okey = okey; - - - if (insert != NULL) - insert->next = entry; - - dict->nbElems++; - - if ((dict->nbElems > dict->size / MAX_FILL) || - (nbi > MAX_HASH_LEN)) { - int newSize = dict->size > INT_MAX / GROWTH_FACTOR ? - INT_MAX : - GROWTH_FACTOR * dict->size; - if (xmlDictGrow(dict, newSize) != 0) - return(NULL); - } - /* Note that entry may have been freed at this point by xmlDictGrow */ - - return(ret); -} - -/** - * xmlDictExists: - * @dict: the dictionary - * @name: the name of the userdata - * @len: the length of the name, if -1 it is recomputed - * - * Check if the @name exists in the dictionary @dict. - * - * Returns the internal copy of the name or NULL if not found. - */ -const xmlChar * -xmlDictExists(xmlDictPtr dict, const xmlChar *name, int len) { - unsigned key, okey; - xmlDictEntryPtr insert; - size_t l; - - if ((dict == NULL) || (name == NULL)) - return(NULL); - - if (len < 0) - l = strlen((const char *) name); - else - l = len; - if (((dict->limit > 0) && (l >= dict->limit)) || - (l > INT_MAX / 2)) - return(NULL); - - /* - * Check for duplicate and insertion location. - */ - okey = xmlDictComputeKey(dict, name, l); - key = okey % dict->size; - if (dict->dict[key].valid == 0) { - insert = NULL; - } else { - for (insert = &(dict->dict[key]); insert->next != NULL; - insert = insert->next) { -#ifdef __GNUC__ - if ((insert->okey == okey) && (insert->len == l)) { - if (!memcmp(insert->name, name, l)) - return(insert->name); - } -#else - if ((insert->okey == okey) && (insert->len == l) && - (!xmlStrncmp(insert->name, name, l))) - return(insert->name); -#endif - } -#ifdef __GNUC__ - if ((insert->okey == okey) && (insert->len == l)) { - if (!memcmp(insert->name, name, l)) - return(insert->name); - } -#else - if ((insert->okey == okey) && (insert->len == l) && - (!xmlStrncmp(insert->name, name, l))) - return(insert->name); -#endif - } - - if (dict->subdict) { - unsigned skey; - - /* we cannot always reuse the same okey for the subdict */ - if (((dict->size == MIN_DICT_SIZE) && - (dict->subdict->size != MIN_DICT_SIZE)) || - ((dict->size != MIN_DICT_SIZE) && - (dict->subdict->size == MIN_DICT_SIZE))) - skey = xmlDictComputeKey(dict->subdict, name, l); - else - skey = okey; - - key = skey % dict->subdict->size; - if (dict->subdict->dict[key].valid != 0) { - xmlDictEntryPtr tmp; - - for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL; - tmp = tmp->next) { -#ifdef __GNUC__ - if ((tmp->okey == skey) && (tmp->len == l)) { - if (!memcmp(tmp->name, name, l)) - return(tmp->name); - } -#else - if ((tmp->okey == skey) && (tmp->len == l) && - (!xmlStrncmp(tmp->name, name, l))) - return(tmp->name); -#endif - } -#ifdef __GNUC__ - if ((tmp->okey == skey) && (tmp->len == l)) { - if (!memcmp(tmp->name, name, l)) - return(tmp->name); - } -#else - if ((tmp->okey == skey) && (tmp->len == l) && - (!xmlStrncmp(tmp->name, name, l))) - return(tmp->name); -#endif - } - } - - /* not found */ - return(NULL); -} - -/** - * xmlDictQLookup: - * @dict: the dictionary - * @prefix: the prefix - * @name: the name - * - * Add the QName @prefix:@name to the hash @dict if not present. - * - * Returns the internal copy of the QName or NULL in case of internal error - */ -const xmlChar * -xmlDictQLookup(xmlDictPtr dict, const xmlChar *prefix, const xmlChar *name) { - unsigned okey, key, nbi = 0; - xmlDictEntryPtr entry; - xmlDictEntryPtr insert; - const xmlChar *ret; - size_t len, plen, l; - - if ((dict == NULL) || (name == NULL)) - return(NULL); - if (prefix == NULL) - return(xmlDictLookup(dict, name, -1)); - - l = len = strlen((const char *) name); - plen = strlen((const char *) prefix); - if ((len > INT_MAX / 2) || (plen > INT_MAX / 2)) - return(NULL); - len += 1 + plen; - - /* - * Check for duplicate and insertion location. - */ - okey = xmlDictComputeQKey(dict, prefix, plen, name, l); - key = okey % dict->size; - if (dict->dict[key].valid == 0) { - insert = NULL; - } else { - for (insert = &(dict->dict[key]); insert->next != NULL; - insert = insert->next) { - if ((insert->okey == okey) && (insert->len == len) && - (xmlStrQEqual(prefix, name, insert->name))) - return(insert->name); - nbi++; - } - if ((insert->okey == okey) && (insert->len == len) && - (xmlStrQEqual(prefix, name, insert->name))) - return(insert->name); - } - - if (dict->subdict) { - unsigned skey; - - /* we cannot always reuse the same okey for the subdict */ - if (((dict->size == MIN_DICT_SIZE) && - (dict->subdict->size != MIN_DICT_SIZE)) || - ((dict->size != MIN_DICT_SIZE) && - (dict->subdict->size == MIN_DICT_SIZE))) - skey = xmlDictComputeQKey(dict->subdict, prefix, plen, name, l); - else - skey = okey; - - key = skey % dict->subdict->size; - if (dict->subdict->dict[key].valid != 0) { - xmlDictEntryPtr tmp; - for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL; - tmp = tmp->next) { - if ((tmp->okey == skey) && (tmp->len == len) && - (xmlStrQEqual(prefix, name, tmp->name))) - return(tmp->name); - nbi++; - } - if ((tmp->okey == skey) && (tmp->len == len) && - (xmlStrQEqual(prefix, name, tmp->name))) - return(tmp->name); - } - key = okey % dict->size; - } - - ret = xmlDictAddQString(dict, prefix, plen, name, l); - if (ret == NULL) - return(NULL); - if (insert == NULL) { - entry = &(dict->dict[key]); - } else { - entry = xmlMalloc(sizeof(xmlDictEntry)); - if (entry == NULL) - return(NULL); - } - entry->name = ret; - entry->len = len; - entry->next = NULL; - entry->valid = 1; - entry->okey = okey; - - if (insert != NULL) - insert->next = entry; - - dict->nbElems++; - - if ((dict->nbElems > dict->size / MAX_FILL) || - (nbi > MAX_HASH_LEN)) { - int newSize = dict->size > INT_MAX / GROWTH_FACTOR ? - INT_MAX : - GROWTH_FACTOR * dict->size; - if (xmlDictGrow(dict, newSize) != 0) - return(NULL); - } - /* Note that entry may have been freed at this point by xmlDictGrow */ - - return(ret); -} - -/** * xmlDictOwns: * @dict: the dictionary * @str: the string @@ -1288,3 +450,502 @@ return(limit); } +/***************************************************************** + * + * The code below was rewritten and is additionally licensed under + * the main license in file 'Copyright'. + * + *****************************************************************/ + +ATTRIBUTE_NO_SANITIZE_INTEGER +static unsigned +xmlDictHashName(unsigned seed, const xmlChar* data, size_t maxLen, + size_t *plen) { + unsigned h1, h2; + size_t i; + + HASH_INIT(h1, h2, seed); + + for (i = 0; i < maxLen && data[i]; i++) { + HASH_UPDATE(h1, h2, data[i]); + } + + HASH_FINISH(h1, h2); + + *plen = i; + return(h2 | MAX_HASH_SIZE); +} + +ATTRIBUTE_NO_SANITIZE_INTEGER +static unsigned +xmlDictHashQName(unsigned seed, const xmlChar *prefix, const xmlChar *name, + size_t *pplen, size_t *plen) { + unsigned h1, h2; + size_t i; + + HASH_INIT(h1, h2, seed); + + for (i = 0; prefix[i] != 0; i++) { + HASH_UPDATE(h1, h2, prefix[i]); + } + *pplen = i; + + HASH_UPDATE(h1, h2, ':'); + + for (i = 0; name[i] != 0; i++) { + HASH_UPDATE(h1, h2, name[i]); + } + *plen = i; + + HASH_FINISH(h1, h2); + + return(h2 | MAX_HASH_SIZE); +} + +unsigned +xmlDictComputeHash(const xmlDict *dict, const xmlChar *string) { + size_t len; + return(xmlDictHashName(dict->seed, string, SIZE_MAX, &len)); +} + +/** + * xmlDictFindEntry: + * @dict: dict + * @prefix: optional QName prefix + * @name: string + * @len: length of string + * @hashValue: valid hash value of string + * @pfound: result of search + * + * Try to find a matching hash table entry. If an entry was found, set + * @found to 1 and return the entry. Otherwise, set @found to 0 and return + * the location where a new entry should be inserted. + */ +ATTRIBUTE_NO_SANITIZE_INTEGER +static xmlDictEntry * +xmlDictFindEntry(const xmlDict *dict, const xmlChar *prefix, + const xmlChar *name, int len, unsigned hashValue, + int *pfound) { + xmlDictEntry *entry; + unsigned mask, pos, displ; + int found = 0; + + mask = dict->size - 1; + pos = hashValue & mask; + entry = &dict->table[pos]; + + if (entry->hashValue != 0) { + /* + * Robin hood hashing: abort if the displacement of the entry + * is smaller than the displacement of the key we look for. + * This also stops at the correct position when inserting. + */ + displ = 0; + + do { + if (entry->hashValue == hashValue) { + if (prefix == NULL) { + /* + * name is not necessarily null-terminated. + */ + if ((strncmp((const char *) entry->name, + (const char *) name, len) == 0) && + (entry->name[len] == 0)) { + found = 1; + break; + } + } else { + if (xmlStrQEqual(prefix, name, entry->name)) { + found = 1; + break; + } + } + } + + displ++; + pos++; + entry++; + if ((pos & mask) == 0) + entry = dict->table; + } while ((entry->hashValue != 0) && + (((pos - entry->hashValue) & mask) >= displ)); + } + + *pfound = found; + return(entry); +} + +/** + * xmlDictGrow: + * @dict: dictionary + * @size: new size of the dictionary + * + * Resize the dictionary hash table. + * + * Returns 0 in case of success, -1 if a memory allocation failed. + */ +static int +xmlDictGrow(xmlDictPtr dict, unsigned size) { + const xmlDictEntry *oldentry, *oldend, *end; + xmlDictEntry *table; + unsigned oldsize, i; + + /* Add 0 to avoid spurious -Wtype-limits warning on 64-bit GCC */ + if ((size_t) size + 0 > SIZE_MAX / sizeof(table[0])) + return(-1); + table = xmlMalloc(size * sizeof(table[0])); + if (table == NULL) + return(-1); + memset(table, 0, size * sizeof(table[0])); + + oldsize = dict->size; + if (oldsize == 0) + goto done; + + oldend = &dict->table[oldsize]; + end = &table[size]; + + /* + * Robin Hood sorting order is maintained if we + * + * - compute dict indices with modulo + * - resize by an integer factor + * - start to copy from the beginning of a probe sequence + */ + oldentry = dict->table; + while (oldentry->hashValue != 0) { + if (++oldentry >= oldend) + oldentry = dict->table; + } + + for (i = 0; i < oldsize; i++) { + if (oldentry->hashValue != 0) { + xmlDictEntry *entry = &table[oldentry->hashValue & (size - 1)]; + + while (entry->hashValue != 0) { + if (++entry >= end) + entry = table; + } + *entry = *oldentry; + } + + if (++oldentry >= oldend) + oldentry = dict->table; + } + + xmlFree(dict->table); + +done: + dict->table = table; + dict->size = size; + + return(0); +} + +/** + * xmlDictLookupInternal: + * @dict: dict + * @prefix: optional QName prefix + * @name: string + * @maybeLen: length of string or -1 if unknown + * @update: whether the string should be added + * + * Internal lookup and update function. + */ +ATTRIBUTE_NO_SANITIZE_INTEGER +static const xmlDictEntry * +xmlDictLookupInternal(xmlDictPtr dict, const xmlChar *prefix, + const xmlChar *name, int maybeLen, int update) { + xmlDictEntry *entry = NULL; + const xmlChar *ret; + unsigned hashValue; + size_t maxLen, len, plen, klen; + int found = 0; + + if ((dict == NULL) || (name == NULL)) + return(NULL); + + maxLen = (maybeLen < 0) ? SIZE_MAX : (size_t) maybeLen; + + if (prefix == NULL) { + hashValue = xmlDictHashName(dict->seed, name, maxLen, &len); + if (len > INT_MAX / 2) + return(NULL); + klen = len; + } else { + hashValue = xmlDictHashQName(dict->seed, prefix, name, &plen, &len); + if ((len > INT_MAX / 2) || (plen >= INT_MAX / 2 - len)) + return(NULL); + klen = plen + 1 + len; + } + + if ((dict->limit > 0) && (klen >= dict->limit)) + return(NULL); + + /* + * Check for an existing entry + */ + if (dict->size > 0) + entry = xmlDictFindEntry(dict, prefix, name, klen, hashValue, &found); + if (found) + return(entry); + + if ((dict->subdict != NULL) && (dict->subdict->size > 0)) { + xmlDictEntry *subEntry; + unsigned subHashValue; + + if (prefix == NULL) + subHashValue = xmlDictHashName(dict->subdict->seed, name, len, + &len); + else + subHashValue = xmlDictHashQName(dict->subdict->seed, prefix, name, + &plen, &len); + subEntry = xmlDictFindEntry(dict->subdict, prefix, name, klen, + subHashValue, &found); + if (found) + return(subEntry); + } + + if (!update) + return(NULL); + + /* + * Grow the hash table if needed + */ + if (dict->nbElems + 1 > dict->size / MAX_FILL_DENOM * MAX_FILL_NUM) { + unsigned newSize, mask, displ, pos; + + if (dict->size == 0) { + newSize = MIN_HASH_SIZE; + } else { + if (dict->size >= MAX_HASH_SIZE) + return(NULL); + newSize = dict->size * 2; + } + if (xmlDictGrow(dict, newSize) != 0) + return(NULL); + + /* + * Find new entry + */ + mask = dict->size - 1; + displ = 0; + pos = hashValue & mask; + entry = &dict->table[pos]; + + while ((entry->hashValue != 0) && + ((pos - entry->hashValue) & mask) >= displ) { + displ++; + pos++; + entry++; + if ((pos & mask) == 0) + entry = dict->table; + } + } + + if (prefix == NULL) + ret = xmlDictAddString(dict, name, len); + else + ret = xmlDictAddQString(dict, prefix, plen, name, len); + if (ret == NULL) + return(NULL); + + /* + * Shift the remainder of the probe sequence to the right + */ + if (entry->hashValue != 0) { + const xmlDictEntry *end = &dict->table[dict->size]; + const xmlDictEntry *cur = entry; + + do { + cur++; + if (cur >= end) + cur = dict->table; + } while (cur->hashValue != 0); + + if (cur < entry) { + /* + * If we traversed the end of the buffer, handle the part + * at the start of the buffer. + */ + memmove(&dict->table[1], dict->table, + (char *) cur - (char *) dict->table); + cur = end - 1; + dict->table[0] = *cur; + } + + memmove(&entry[1], entry, (char *) cur - (char *) entry); + } + + /* + * Populate entry + */ + entry->hashValue = hashValue; + entry->name = ret; + + dict->nbElems++; + + return(entry); +} + +/** + * xmlDictLookup: + * @dict: dictionary + * @name: string key + * @len: length of the key, if -1 it is recomputed + * + * Lookup a string and add it to the dictionary if it wasn't found. + * + * Returns the interned copy of the string or NULL if a memory allocation + * failed. + */ +const xmlChar * +xmlDictLookup(xmlDictPtr dict, const xmlChar *name, int len) { + const xmlDictEntry *entry; + + entry = xmlDictLookupInternal(dict, NULL, name, len, 1); + if (entry == NULL) + return(NULL); + return(entry->name); +} + +/** + * xmlDictLookupHashed: + * @dict: dictionary + * @name: string key + * @len: length of the key, if -1 it is recomputed + * + * Lookup a dictionary entry and add the string to the dictionary if + * it wasn't found. + * + * Returns the dictionary entry. + */ +xmlHashedString +xmlDictLookupHashed(xmlDictPtr dict, const xmlChar *name, int len) { + const xmlDictEntry *entry; + xmlHashedString ret; + + entry = xmlDictLookupInternal(dict, NULL, name, len, 1); + + if (entry == NULL) { + ret.name = NULL; + ret.hashValue = 0; + } else { + ret = *entry; + } + + return(ret); +} + +/** + * xmlDictExists: + * @dict: the dictionary + * @name: the name of the userdata + * @len: the length of the name, if -1 it is recomputed + * + * Check if a string exists in the dictionary. + * + * Returns the internal copy of the name or NULL if not found. + */ +const xmlChar * +xmlDictExists(xmlDictPtr dict, const xmlChar *name, int len) { + const xmlDictEntry *entry; + + entry = xmlDictLookupInternal(dict, NULL, name, len, 0); + if (entry == NULL) + return(NULL); + return(entry->name); +} + +/** + * xmlDictQLookup: + * @dict: the dictionary + * @prefix: the prefix + * @name: the name + * + * Lookup the QName @prefix:@name and add it to the dictionary if + * it wasn't found. + * + * Returns the interned copy of the string or NULL if a memory allocation + * failed. + */ +const xmlChar * +xmlDictQLookup(xmlDictPtr dict, const xmlChar *prefix, const xmlChar *name) { + const xmlDictEntry *entry; + + entry = xmlDictLookupInternal(dict, prefix, name, -1, 1); + if (entry == NULL) + return(NULL); + return(entry->name); +} + +/* + * Pseudo-random generator + */ + +static xmlMutex xmlRngMutex; + +static unsigned globalRngState[2]; + +#ifdef XML_THREAD_LOCAL +XML_THREAD_LOCAL static int localRngInitialized = 0; +XML_THREAD_LOCAL static unsigned localRngState[2]; +#endif + +ATTRIBUTE_NO_SANITIZE_INTEGER +void +xmlInitRandom(void) { + int var; + + xmlInitMutex(&xmlRngMutex); + + /* TODO: Get seed values from system PRNG */ + + globalRngState[0] = (unsigned) time(NULL) ^ + HASH_ROL((unsigned) (size_t) &xmlInitRandom, 8); + globalRngState[1] = HASH_ROL((unsigned) (size_t) &xmlRngMutex, 16) ^ + HASH_ROL((unsigned) (size_t) &var, 24); +} + +void +xmlCleanupRandom(void) { + xmlCleanupMutex(&xmlRngMutex); +} + +ATTRIBUTE_NO_SANITIZE_INTEGER +static unsigned +xoroshiro64ss(unsigned *s) { + unsigned s0 = s[0]; + unsigned s1 = s[1]; + unsigned result = HASH_ROL(s0 * 0x9E3779BB, 5) * 5; + + s1 ^= s0; + s[0] = HASH_ROL(s0, 26) ^ s1 ^ (s1 << 9); + s[1] = HASH_ROL(s1, 13); + + return(result & 0xFFFFFFFF); +} + +unsigned +xmlRandom(void) { +#ifdef XML_THREAD_LOCAL + if (!localRngInitialized) { + xmlMutexLock(&xmlRngMutex); + localRngState[0] = xoroshiro64ss(globalRngState); + localRngState[1] = xoroshiro64ss(globalRngState); + localRngInitialized = 1; + xmlMutexUnlock(&xmlRngMutex); + } + + return(xoroshiro64ss(localRngState)); +#else + unsigned ret; + + xmlMutexLock(&xmlRngMutex); + ret = xoroshiro64ss(globalRngState); + xmlMutexUnlock(&xmlRngMutex); + + return(ret); +#endif +} +
diff --git a/src/encoding.c b/src/encoding.c index bac65ac..bc2772d 100644 --- a/src/encoding.c +++ b/src/encoding.c
@@ -480,7 +480,7 @@ unsigned char* outstart = out; const unsigned char* processed = inb; unsigned char* outend; - unsigned short* in = (unsigned short*) inb; + unsigned short* in = (unsigned short *) (void *) inb; unsigned short* inend; unsigned int c, d, inlen; unsigned char *tmp; @@ -566,7 +566,7 @@ UTF8ToUTF16LE(unsigned char* outb, int *outlen, const unsigned char* in, int *inlen) { - unsigned short* out = (unsigned short*) outb; + unsigned short* out = (unsigned short *) (void *) outb; const unsigned char* processed = in; const unsigned char *const instart = in; unsigned short* outstart= out; @@ -718,7 +718,7 @@ unsigned char* outstart = out; const unsigned char* processed = inb; unsigned char* outend; - unsigned short* in = (unsigned short*) inb; + unsigned short* in = (unsigned short *) (void *) inb; unsigned short* inend; unsigned int c, d, inlen; unsigned char *tmp; @@ -804,7 +804,7 @@ UTF8ToUTF16BE(unsigned char* outb, int *outlen, const unsigned char* in, int *inlen) { - unsigned short* out = (unsigned short*) outb; + unsigned short* out = (unsigned short *) (void *) outb; const unsigned char* processed = in; const unsigned char *const instart = in; unsigned short* outstart= out; @@ -1989,9 +1989,22 @@ int ret; if (handler->input != NULL) { + int oldinlen = *inlen; + ret = handler->input(out, outlen, in, inlen); - if (ret > 0) - ret = XML_ENC_ERR_SUCCESS; + if (ret >= 0) { + /* + * The built-in converters don't signal XML_ENC_ERR_SPACE. + */ + if (*inlen < oldinlen) { + if (*outlen > 0) + ret = XML_ENC_ERR_SPACE; + else + ret = XML_ENC_ERR_PARTIAL; + } else { + ret = XML_ENC_ERR_SUCCESS; + } + } } #ifdef LIBXML_ICONV_ENABLED else if (handler->iconv_in != NULL) { @@ -2036,9 +2049,22 @@ int ret; if (handler->output != NULL) { + int oldinlen = *inlen; + ret = handler->output(out, outlen, in, inlen); - if (ret > 0) - ret = XML_ENC_ERR_SUCCESS; + if (ret >= 0) { + /* + * The built-in converters don't signal XML_ENC_ERR_SPACE. + */ + if (*inlen < oldinlen) { + if (*outlen > 0) + ret = XML_ENC_ERR_SPACE; + else + ret = XML_ENC_ERR_PARTIAL; + } else { + ret = XML_ENC_ERR_SUCCESS; + } + } } #ifdef LIBXML_ICONV_ENABLED else if (handler->iconv_out != NULL) { @@ -2118,8 +2144,8 @@ avail = xmlBufAvail(out); if (avail > INT_MAX) avail = INT_MAX; - if (avail < toconv * 2) { - if (xmlBufGrow(out, toconv * 2) < 0) { + if (avail < 4096) { + if (xmlBufGrow(out, 4096) < 0) { input->error = XML_ERR_NO_MEMORY; return(XML_ENC_ERR_MEMORY); }
diff --git a/src/entities.c b/src/entities.c index 09d47d7..aec5144 100644 --- a/src/entities.c +++ b/src/entities.c
@@ -113,7 +113,7 @@ /* * xmlFreeEntity : clean-up an entity record. */ -static void +void xmlFreeEntity(xmlEntityPtr entity) { xmlDictPtr dict = NULL;
diff --git a/src/error.c b/src/error.c index 1b4fe76..c87cf2a 100644 --- a/src/error.c +++ b/src/error.c
@@ -939,7 +939,7 @@ * * Returns NULL if no error occurred or a pointer to the error */ -xmlErrorPtr +const xmlError * xmlCtxtGetLastError(void *ctx) { xmlParserCtxtPtr ctxt = (xmlParserCtxtPtr) ctx;
diff --git a/src/globals.c b/src/globals.c index 157f7f0..a786a4b 100644 --- a/src/globals.c +++ b/src/globals.c
@@ -754,12 +754,20 @@ gs->gs_xmlDefaultSAXLocator.getColumnNumber = xmlSAX2GetColumnNumber; gs->gs_xmlDoValidityCheckingDefaultValue = xmlDoValidityCheckingDefaultValueThrDef; -#if defined(DEBUG_MEMORY_LOCATION) - gs->gs_xmlFree = (xmlFreeFunc) xmlMemFree; - gs->gs_xmlMalloc = (xmlMallocFunc) xmlMemMalloc; - gs->gs_xmlMallocAtomic = (xmlMallocFunc) xmlMemMalloc; - gs->gs_xmlRealloc = (xmlReallocFunc) xmlMemRealloc; - gs->gs_xmlMemStrdup = (xmlStrdupFunc) xmlMemoryStrdup; +#ifdef LIBXML_THREAD_ALLOC_ENABLED +#ifdef DEBUG_MEMORY_LOCATION + gs->gs_xmlFree = xmlMemFree; + gs->gs_xmlMalloc = xmlMemMalloc; + gs->gs_xmlMallocAtomic = xmlMemMalloc; + gs->gs_xmlRealloc = xmlMemRealloc; + gs->gs_xmlMemStrdup = xmlMemoryStrdup; +#else + gs->gs_xmlFree = free; + gs->gs_xmlMalloc = malloc; + gs->gs_xmlMallocAtomic = malloc; + gs->gs_xmlRealloc = realloc; + gs->gs_xmlMemStrdup = xmlPosixStrdup; +#endif #endif gs->gs_xmlGetWarningsDefaultValue = xmlGetWarningsDefaultValueThrDef; #ifdef LIBXML_OUTPUT_ENABLED
diff --git a/src/hash.c b/src/hash.c index 34825f3..dcda199 100644 --- a/src/hash.c +++ b/src/hash.c
@@ -1,204 +1,197 @@ /* - * hash.c: chained hash tables + * hash.c: hash tables * - * Reference: Your favorite introductory book on algorithms + * Hash table with open addressing, linear probing and + * Robin Hood reordering. * - * Copyright (C) 2000,2012 Bjorn Reese and Daniel Veillard. - * - * Permission to use, copy, modify, and distribute this software for any - * purpose with or without fee is hereby granted, provided that the above - * copyright notice and this permission notice appear in all copies. - * - * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED - * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF - * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE AUTHORS AND - * CONTRIBUTORS ACCEPT NO RESPONSIBILITY IN ANY CONCEIVABLE MANNER. - * - * Author: breese@users.sourceforge.net + * See Copyright for the status of this software. */ #define IN_LIBXML #include "libxml.h" #include <string.h> -#include <stdlib.h> -#include <time.h> - -/* - * Following http://www.ocert.org/advisories/ocert-2011-003.html - * it seems that having hash randomization might be a good idea - * when using XML with untrusted data - */ -#if !defined(FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION) -#define HASH_RANDOMIZATION -#endif +#include <limits.h> #include <libxml/parser.h> #include <libxml/hash.h> +#include <libxml/dict.h> #include <libxml/xmlmemory.h> -#include <libxml/xmlerror.h> +#include <libxml/xmlstring.h> #include "private/dict.h" -#define MAX_HASH_LEN 16 -#define MAX_FILL 2 -#define GROWTH_FACTOR 4 -#define MIN_HASH_SIZE 16 +#ifndef SIZE_MAX + #define SIZE_MAX ((size_t) -1) +#endif -/* #define DEBUG_GROW */ +#define MAX_FILL_NUM 7 +#define MAX_FILL_DENOM 8 +#define MIN_HASH_SIZE 8 +#define MAX_HASH_SIZE (1u << 31) /* * A single entry in the hash table */ -typedef struct _xmlHashEntry xmlHashEntry; -typedef xmlHashEntry *xmlHashEntryPtr; -struct _xmlHashEntry { - struct _xmlHashEntry *next; - xmlChar *name; - xmlChar *name2; - xmlChar *name3; +typedef struct { + unsigned hashValue; /* 0 means unoccupied, occupied entries have the + * MAX_HASH_SIZE bit set to 1 */ + xmlChar *key; + xmlChar *key2; /* TODO: Don't allocate possibly empty keys */ + xmlChar *key3; void *payload; - int valid; -}; +} xmlHashEntry; /* * The entire hash table */ struct _xmlHashTable { - struct _xmlHashEntry *table; - int size; - int nbElems; + xmlHashEntry *table; + unsigned size; /* power of two */ + unsigned nbElems; xmlDictPtr dict; - unsigned random_seed; + unsigned randomSeed; }; -/* - * xmlHashComputeKey: - * Calculate the hash key - */ -#ifdef __clang__ -ATTRIBUTE_NO_SANITIZE("unsigned-integer-overflow") -ATTRIBUTE_NO_SANITIZE("unsigned-shift-base") -#endif +static int +xmlHashGrow(xmlHashTablePtr hash, unsigned size); + +ATTRIBUTE_NO_SANITIZE_INTEGER static unsigned -xmlHashComputeKey(xmlHashTablePtr table, const xmlChar *name, - const xmlChar *name2, const xmlChar *name3) { - unsigned h1, h2, ch; +xmlHashValue(unsigned seed, const xmlChar *key, const xmlChar *key2, + const xmlChar *key3, size_t *lengths) { + unsigned h1, h2; + size_t i; - HASH_INIT(h1, h2, table->random_seed); + HASH_INIT(h1, h2, seed); - if (name != NULL) { - while ((ch = *name++) != 0) { - HASH_UPDATE(h1, h2, ch); - } + for (i = 0; key[i] != 0; i++) { + HASH_UPDATE(h1, h2, key[i]); } + if (lengths) + lengths[0] = i; + HASH_UPDATE(h1, h2, 0); - if (name2 != NULL) { - while ((ch = *name2++) != 0) { - HASH_UPDATE(h1, h2, ch); - } + + if (key2 != NULL) { + for (i = 0; key2[i] != 0; i++) { + HASH_UPDATE(h1, h2, key2[i]); + } + if (lengths) + lengths[1] = i; } + HASH_UPDATE(h1, h2, 0); - if (name3 != NULL) { - while ((ch = *name3++) != 0) { - HASH_UPDATE(h1, h2, ch); - } + + if (key3 != NULL) { + for (i = 0; key3[i] != 0; i++) { + HASH_UPDATE(h1, h2, key3[i]); + } + if (lengths) + lengths[2] = i; } HASH_FINISH(h1, h2); - return (h2 % table->size); + return(h2); } -#ifdef __clang__ -ATTRIBUTE_NO_SANITIZE("unsigned-integer-overflow") -ATTRIBUTE_NO_SANITIZE("unsigned-shift-base") -#endif +ATTRIBUTE_NO_SANITIZE_INTEGER static unsigned -xmlHashComputeQKey(xmlHashTablePtr table, - const xmlChar *prefix, const xmlChar *name, - const xmlChar *prefix2, const xmlChar *name2, - const xmlChar *prefix3, const xmlChar *name3) { +xmlHashQNameValue(unsigned seed, + const xmlChar *prefix, const xmlChar *name, + const xmlChar *prefix2, const xmlChar *name2, + const xmlChar *prefix3, const xmlChar *name3) { unsigned h1, h2, ch; - HASH_INIT(h1, h2, table->random_seed); + HASH_INIT(h1, h2, seed); if (prefix != NULL) { - while ((ch = *prefix++) != 0) { + while ((ch = *prefix++) != 0) { HASH_UPDATE(h1, h2, ch); - } + } HASH_UPDATE(h1, h2, ':'); } if (name != NULL) { - while ((ch = *name++) != 0) { + while ((ch = *name++) != 0) { HASH_UPDATE(h1, h2, ch); - } + } } HASH_UPDATE(h1, h2, 0); if (prefix2 != NULL) { - while ((ch = *prefix2++) != 0) { + while ((ch = *prefix2++) != 0) { HASH_UPDATE(h1, h2, ch); - } + } HASH_UPDATE(h1, h2, ':'); } if (name2 != NULL) { - while ((ch = *name2++) != 0) { + while ((ch = *name2++) != 0) { HASH_UPDATE(h1, h2, ch); - } + } } HASH_UPDATE(h1, h2, 0); if (prefix3 != NULL) { - while ((ch = *prefix3++) != 0) { + while ((ch = *prefix3++) != 0) { HASH_UPDATE(h1, h2, ch); - } + } HASH_UPDATE(h1, h2, ':'); } if (name3 != NULL) { - while ((ch = *name3++) != 0) { + while ((ch = *name3++) != 0) { HASH_UPDATE(h1, h2, ch); - } + } } HASH_FINISH(h1, h2); - return (h2 % table->size); + return(h2); } /** * xmlHashCreate: - * @size: the size of the hash table + * @size: initial size of the hash table * - * Create a new xmlHashTablePtr. + * Create a new hash table. Set size to zero if the number of entries + * can't be estimated. * - * Returns the newly created object, or NULL if an error occurred. + * Returns the newly created object, or NULL if a memory allocation failed. */ xmlHashTablePtr xmlHashCreate(int size) { - xmlHashTablePtr table; + xmlHashTablePtr hash; xmlInitParser(); - if (size <= MIN_HASH_SIZE) - size = MIN_HASH_SIZE; - - table = xmlMalloc(sizeof(xmlHashTable)); - if (table) { - table->dict = NULL; - table->size = size; - table->nbElems = 0; - table->table = xmlMalloc(size * sizeof(xmlHashEntry)); - if (table->table) { - memset(table->table, 0, size * sizeof(xmlHashEntry)); -#ifdef HASH_RANDOMIZATION - table->random_seed = xmlRandom(); -#else - table->random_seed = 0; + hash = xmlMalloc(sizeof(*hash)); + if (hash == NULL) + return(NULL); + hash->dict = NULL; + hash->size = 0; + hash->table = NULL; + hash->nbElems = 0; + hash->randomSeed = xmlRandom(); +#ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION + hash->randomSeed = 0; #endif - return(table); + + /* + * Unless a larger size is passed, the backing table is created + * lazily with MIN_HASH_SIZE capacity. In practice, there are many + * hash tables which are never filled. + */ + if (size > MIN_HASH_SIZE) { + unsigned newSize = MIN_HASH_SIZE * 2; + + while ((newSize < (unsigned) size) && (newSize < MAX_HASH_SIZE)) + newSize *= 2; + + if (xmlHashGrow(hash, newSize) != 0) { + xmlFree(hash); + return(NULL); } - xmlFree(table); } - return(NULL); + + return(hash); } /** @@ -206,987 +199,953 @@ * @size: the size of the hash table * @dict: a dictionary to use for the hash * - * Create a new xmlHashTablePtr which will use @dict as the internal dictionary + * Create a new hash table backed by a dictionary. This can reduce + * resource usage considerably if most keys passed to API functions + * originate from this dictionary. * - * Returns the newly created object, or NULL if an error occurred. + * Returns the newly created object, or NULL if a memory allocation failed. */ xmlHashTablePtr xmlHashCreateDict(int size, xmlDictPtr dict) { - xmlHashTablePtr table; + xmlHashTablePtr hash; - table = xmlHashCreate(size); - if (table != NULL) { - table->dict = dict; - xmlDictReference(dict); + hash = xmlHashCreate(size); + if (hash != NULL) { + hash->dict = dict; + xmlDictReference(dict); } - return(table); + return(hash); +} + +/** + * xmlHashFree: + * @hash: hash table + * @dealloc: deallocator function or NULL + * + * Free the hash and its contents. The payload is deallocated with + * @dealloc if provided. + */ +void +xmlHashFree(xmlHashTablePtr hash, xmlHashDeallocator dealloc) { + if (hash == NULL) + return; + + if (hash->table) { + const xmlHashEntry *end = &hash->table[hash->size]; + const xmlHashEntry *entry; + + for (entry = hash->table; entry < end; entry++) { + if (entry->hashValue == 0) + continue; + if ((dealloc != NULL) && (entry->payload != NULL)) + dealloc(entry->payload, entry->key); + if (hash->dict == NULL) { + if (entry->key) + xmlFree(entry->key); + if (entry->key2) + xmlFree(entry->key2); + if (entry->key3) + xmlFree(entry->key3); + } + } + + xmlFree(hash->table); + } + + if (hash->dict) + xmlDictFree(hash->dict); + + xmlFree(hash); +} + +/** + * xmlFastStrEqual: + * @s1: string + * @s2: string + * + * Compare two strings for equality, allowing NULL values. + */ +static int +xmlFastStrEqual(const xmlChar *s1, const xmlChar *s2) { + if (s1 == NULL) + return(s2 == NULL); + else + return((s2 != NULL) && + (strcmp((const char *) s1, (const char *) s2) == 0)); +} + +/** + * xmlHashFindEntry: + * @hash: hash table, non-NULL, size > 0 + * @key: first string key, non-NULL + * @key2: second string key + * @key3: third string key + * @hashValue: valid hash value of keys + * @pfound: result of search + * + * Try to find a matching hash table entry. If an entry was found, set + * @found to 1 and return the entry. Otherwise, set @found to 0 and return + * the location where a new entry should be inserted. + */ +ATTRIBUTE_NO_SANITIZE_INTEGER +static xmlHashEntry * +xmlHashFindEntry(const xmlHashTable *hash, const xmlChar *key, + const xmlChar *key2, const xmlChar *key3, + unsigned hashValue, int *pfound) { + xmlHashEntry *entry; + unsigned mask, pos, displ; + int found = 0; + + mask = hash->size - 1; + pos = hashValue & mask; + entry = &hash->table[pos]; + + if (entry->hashValue != 0) { + /* + * Robin hood hashing: abort if the displacement of the entry + * is smaller than the displacement of the key we look for. + * This also stops at the correct position when inserting. + */ + displ = 0; + hashValue |= MAX_HASH_SIZE; + + do { + if (entry->hashValue == hashValue) { + if (hash->dict) { + if ((entry->key == key) && + (entry->key2 == key2) && + (entry->key3 == key3)) { + found = 1; + break; + } + } + if ((strcmp((const char *) entry->key, + (const char *) key) == 0) && + (xmlFastStrEqual(entry->key2, key2)) && + (xmlFastStrEqual(entry->key3, key3))) { + found = 1; + break; + } + } + + displ++; + pos++; + entry++; + if ((pos & mask) == 0) + entry = hash->table; + } while ((entry->hashValue != 0) && + (((pos - entry->hashValue) & mask) >= displ)); + } + + *pfound = found; + return(entry); } /** * xmlHashGrow: - * @table: the hash table - * @size: the new size of the hash table + * @hash: hash table + * @size: new size of the hash table * - * resize the hash table + * Resize the hash table. * - * Returns 0 in case of success, -1 in case of failure + * Returns 0 in case of success, -1 if a memory allocation failed. */ static int -xmlHashGrow(xmlHashTablePtr table, int size) { - unsigned key; - int oldsize, i; - xmlHashEntryPtr iter, next; - struct _xmlHashEntry *oldtable; -#ifdef DEBUG_GROW - unsigned nbElem = 0; -#endif +xmlHashGrow(xmlHashTablePtr hash, unsigned size) { + const xmlHashEntry *oldentry, *oldend, *end; + xmlHashEntry *table; + unsigned oldsize, i; - if (table == NULL) - return(-1); - oldsize = table->size; - if (size <= oldsize) - return(0); - - oldtable = table->table; - if (oldtable == NULL) + /* Add 0 to avoid spurious -Wtype-limits warning on 64-bit GCC */ + if ((size_t) size + 0 > SIZE_MAX / sizeof(table[0])) return(-1); + table = xmlMalloc(size * sizeof(table[0])); + if (table == NULL) + return(-1); + memset(table, 0, size * sizeof(table[0])); - table->table = xmlMalloc(size * sizeof(xmlHashEntry)); - if (table->table == NULL) { - table->table = oldtable; - return(-1); - } - memset(table->table, 0, size * sizeof(xmlHashEntry)); - table->size = size; + oldsize = hash->size; + if (oldsize == 0) + goto done; - /* If the two loops are merged, there would be situations where - a new entry needs to allocated and data copied into it from - the main table. So instead, we run through the array twice, first - copying all the elements in the main array (where we can't get - conflicts) and then the rest, so we only free (and don't allocate) - */ - for (i = 0; i < oldsize; i++) { - if (oldtable[i].valid == 0) - continue; - key = xmlHashComputeKey(table, oldtable[i].name, oldtable[i].name2, - oldtable[i].name3); - memcpy(&(table->table[key]), &(oldtable[i]), sizeof(xmlHashEntry)); - table->table[key].next = NULL; + oldend = &hash->table[oldsize]; + end = &table[size]; + + /* + * Robin Hood sorting order is maintained if we + * + * - compute hash indices with modulo + * - resize by an integer factor + * - start to copy from the beginning of a probe sequence + */ + oldentry = hash->table; + while (oldentry->hashValue != 0) { + if (++oldentry >= oldend) + oldentry = hash->table; } for (i = 0; i < oldsize; i++) { - iter = oldtable[i].next; - while (iter) { - next = iter->next; + if (oldentry->hashValue != 0) { + xmlHashEntry *entry = &table[oldentry->hashValue & (size - 1)]; - /* - * put back the entry in the new table - */ + while (entry->hashValue != 0) { + if (++entry >= end) + entry = table; + } + *entry = *oldentry; + } - key = xmlHashComputeKey(table, iter->name, iter->name2, - iter->name3); - if (table->table[key].valid == 0) { - memcpy(&(table->table[key]), iter, sizeof(xmlHashEntry)); - table->table[key].next = NULL; - xmlFree(iter); - } else { - iter->next = table->table[key].next; - table->table[key].next = iter; - } - -#ifdef DEBUG_GROW - nbElem++; -#endif - - iter = next; - } + if (++oldentry >= oldend) + oldentry = hash->table; } - xmlFree(oldtable); + xmlFree(hash->table); -#ifdef DEBUG_GROW - xmlGenericError(xmlGenericErrorContext, - "xmlHashGrow : from %d to %d, %d elems\n", oldsize, size, nbElem); -#endif +done: + hash->table = table; + hash->size = size; return(0); } /** - * xmlHashFree: - * @table: the hash table - * @f: the deallocator function for items in the hash + * xmlHashUpdateInternal: + * @hash: hash table + * @key: first string key + * @key2: second string key + * @key3: third string key + * @payload: pointer to the payload + * @dealloc: deallocator function for replaced item or NULL + * @update: whether existing entries should be updated * - * Free the hash @table and its contents. The userdata is - * deallocated with @f if provided. + * Internal function to add or update hash entries. */ -void -xmlHashFree(xmlHashTablePtr table, xmlHashDeallocator f) { - int i; - xmlHashEntryPtr iter; - xmlHashEntryPtr next; - int inside_table = 0; - int nbElems; +ATTRIBUTE_NO_SANITIZE_INTEGER +static int +xmlHashUpdateInternal(xmlHashTablePtr hash, const xmlChar *key, + const xmlChar *key2, const xmlChar *key3, + void *payload, xmlHashDeallocator dealloc, int update) { + xmlChar *copy, *copy2, *copy3; + xmlHashEntry *entry = NULL; + size_t lengths[3]; + unsigned hashValue; + int found = 0; - if (table == NULL) - return; - if (table->table) { - nbElems = table->nbElems; - for(i = 0; (i < table->size) && (nbElems > 0); i++) { - iter = &(table->table[i]); - if (iter->valid == 0) - continue; - inside_table = 1; - while (iter) { - next = iter->next; - if ((f != NULL) && (iter->payload != NULL)) - f(iter->payload, iter->name); - if (table->dict == NULL) { - if (iter->name) - xmlFree(iter->name); - if (iter->name2) - xmlFree(iter->name2); - if (iter->name3) - xmlFree(iter->name3); - } - iter->payload = NULL; - if (!inside_table) - xmlFree(iter); - nbElems--; - inside_table = 0; - iter = next; - } - } - xmlFree(table->table); + if ((hash == NULL) || (key == NULL)) + return(-1); + + /* + * Check for an existing entry + */ + hashValue = xmlHashValue(hash->randomSeed, key, key2, key3, lengths); + if (hash->size > 0) + entry = xmlHashFindEntry(hash, key, key2, key3, hashValue, &found); + if (found) { + if (update) { + if (dealloc) + dealloc(entry->payload, entry->key); + entry->payload = payload; + return(0); + } else { + /* + * xmlHashAddEntry found an existing entry. + * + * TODO: We should return a different error code here to + * distinguish from malloc failures. + */ + return(-1); + } } - if (table->dict) - xmlDictFree(table->dict); - xmlFree(table); + + /* + * Grow the hash table if needed + */ + if (hash->nbElems + 1 > hash->size / MAX_FILL_DENOM * MAX_FILL_NUM) { + unsigned newSize, mask, displ, pos; + + if (hash->size == 0) { + newSize = MIN_HASH_SIZE; + } else { + /* This guarantees that nbElems < INT_MAX */ + if (hash->size >= MAX_HASH_SIZE) + return(-1); + newSize = hash->size * 2; + } + if (xmlHashGrow(hash, newSize) != 0) + return(-1); + + /* + * Find new entry + */ + mask = hash->size - 1; + displ = 0; + pos = hashValue & mask; + entry = &hash->table[pos]; + + if (entry->hashValue != 0) { + do { + displ++; + pos++; + entry++; + if ((pos & mask) == 0) + entry = hash->table; + } while ((entry->hashValue != 0) && + ((pos - entry->hashValue) & mask) >= displ); + } + } + + /* + * Copy keys + */ + if (hash->dict != NULL) { + if (xmlDictOwns(hash->dict, key)) { + copy = (xmlChar *) key; + } else { + copy = (xmlChar *) xmlDictLookup(hash->dict, key, -1); + if (copy == NULL) + return(-1); + } + + if ((key2 == NULL) || (xmlDictOwns(hash->dict, key2))) { + copy2 = (xmlChar *) key2; + } else { + copy2 = (xmlChar *) xmlDictLookup(hash->dict, key2, -1); + if (copy2 == NULL) + return(-1); + } + if ((key3 == NULL) || (xmlDictOwns(hash->dict, key3))) { + copy3 = (xmlChar *) key3; + } else { + copy3 = (xmlChar *) xmlDictLookup(hash->dict, key3, -1); + if (copy3 == NULL) + return(-1); + } + } else { + copy = xmlMalloc(lengths[0] + 1); + if (copy == NULL) + return(-1); + memcpy(copy, key, lengths[0] + 1); + + if (key2 != NULL) { + copy2 = xmlMalloc(lengths[1] + 1); + if (copy2 == NULL) { + xmlFree(copy); + return(-1); + } + memcpy(copy2, key2, lengths[1] + 1); + } else { + copy2 = NULL; + } + + if (key3 != NULL) { + copy3 = xmlMalloc(lengths[2] + 1); + if (copy3 == NULL) { + xmlFree(copy); + xmlFree(copy2); + return(-1); + } + memcpy(copy3, key3, lengths[2] + 1); + } else { + copy3 = NULL; + } + } + + /* + * Shift the remainder of the probe sequence to the right + */ + if (entry->hashValue != 0) { + const xmlHashEntry *end = &hash->table[hash->size]; + const xmlHashEntry *cur = entry; + + do { + cur++; + if (cur >= end) + cur = hash->table; + } while (cur->hashValue != 0); + + if (cur < entry) { + /* + * If we traversed the end of the buffer, handle the part + * at the start of the buffer. + */ + memmove(&hash->table[1], hash->table, + (char *) cur - (char *) hash->table); + cur = end - 1; + hash->table[0] = *cur; + } + + memmove(&entry[1], entry, (char *) cur - (char *) entry); + } + + /* + * Populate entry + */ + entry->key = copy; + entry->key2 = copy2; + entry->key3 = copy3; + entry->payload = payload; + /* OR with MAX_HASH_SIZE to make sure that the value is non-zero */ + entry->hashValue = hashValue | MAX_HASH_SIZE; + + hash->nbElems++; + + return(0); } /** * xmlHashDefaultDeallocator: - * @entry: the hash table entry - * @name: the entry's name + * @entry: hash table entry + * @key: the entry's string key * * Free a hash table entry with xmlFree. */ void -xmlHashDefaultDeallocator(void *entry, const xmlChar *name ATTRIBUTE_UNUSED) { +xmlHashDefaultDeallocator(void *entry, const xmlChar *key ATTRIBUTE_UNUSED) { xmlFree(entry); } /** * xmlHashAddEntry: - * @table: the hash table - * @name: the name of the userdata - * @userdata: a pointer to the userdata + * @hash: hash table + * @key: string key + * @payload: pointer to the payload * - * Add the @userdata to the hash @table. This can later be retrieved - * by using the @name. Duplicate names generate errors. + * Add a hash table entry. If an entry with this key already exists, + * payload will not be updated and -1 is returned. This return value + * can't be distinguished from out-of-memory errors, so this function + * should be used with care. * - * Returns 0 the addition succeeded and -1 in case of error. + * Returns 0 on success and -1 in case of error. */ int -xmlHashAddEntry(xmlHashTablePtr table, const xmlChar *name, void *userdata) { - return(xmlHashAddEntry3(table, name, NULL, NULL, userdata)); +xmlHashAddEntry(xmlHashTablePtr hash, const xmlChar *key, void *payload) { + return(xmlHashUpdateInternal(hash, key, NULL, NULL, payload, NULL, 0)); } /** * xmlHashAddEntry2: - * @table: the hash table - * @name: the name of the userdata - * @name2: a second name of the userdata - * @userdata: a pointer to the userdata + * @hash: hash table + * @key: first string key + * @key2: second string key + * @payload: pointer to the payload * - * Add the @userdata to the hash @table. This can later be retrieved - * by using the (@name, @name2) tuple. Duplicate tuples generate errors. + * Add a hash table entry with two strings as key. * - * Returns 0 the addition succeeded and -1 in case of error. + * See xmlHashAddEntry. */ int -xmlHashAddEntry2(xmlHashTablePtr table, const xmlChar *name, - const xmlChar *name2, void *userdata) { - return(xmlHashAddEntry3(table, name, name2, NULL, userdata)); -} - -/** - * xmlHashUpdateEntry: - * @table: the hash table - * @name: the name of the userdata - * @userdata: a pointer to the userdata - * @f: the deallocator function for replaced item (if any) - * - * Add the @userdata to the hash @table. This can later be retrieved - * by using the @name. Existing entry for this @name will be removed - * and freed with @f if found. - * - * Returns 0 the addition succeeded and -1 in case of error. - */ -int -xmlHashUpdateEntry(xmlHashTablePtr table, const xmlChar *name, - void *userdata, xmlHashDeallocator f) { - return(xmlHashUpdateEntry3(table, name, NULL, NULL, userdata, f)); -} - -/** - * xmlHashUpdateEntry2: - * @table: the hash table - * @name: the name of the userdata - * @name2: a second name of the userdata - * @userdata: a pointer to the userdata - * @f: the deallocator function for replaced item (if any) - * - * Add the @userdata to the hash @table. This can later be retrieved - * by using the (@name, @name2) tuple. Existing entry for this tuple will - * be removed and freed with @f if found. - * - * Returns 0 the addition succeeded and -1 in case of error. - */ -int -xmlHashUpdateEntry2(xmlHashTablePtr table, const xmlChar *name, - const xmlChar *name2, void *userdata, - xmlHashDeallocator f) { - return(xmlHashUpdateEntry3(table, name, name2, NULL, userdata, f)); -} - -/** - * xmlHashLookup: - * @table: the hash table - * @name: the name of the userdata - * - * Find the userdata specified by the @name. - * - * Returns the pointer to the userdata - */ -void * -xmlHashLookup(xmlHashTablePtr table, const xmlChar *name) { - return(xmlHashLookup3(table, name, NULL, NULL)); -} - -/** - * xmlHashLookup2: - * @table: the hash table - * @name: the name of the userdata - * @name2: a second name of the userdata - * - * Find the userdata specified by the (@name, @name2) tuple. - * - * Returns the pointer to the userdata - */ -void * -xmlHashLookup2(xmlHashTablePtr table, const xmlChar *name, - const xmlChar *name2) { - return(xmlHashLookup3(table, name, name2, NULL)); -} - -/** - * xmlHashQLookup: - * @table: the hash table - * @prefix: the prefix of the userdata - * @name: the name of the userdata - * - * Find the userdata specified by the QName @prefix:@name/@name. - * - * Returns the pointer to the userdata - */ -void * -xmlHashQLookup(xmlHashTablePtr table, const xmlChar *prefix, - const xmlChar *name) { - return(xmlHashQLookup3(table, prefix, name, NULL, NULL, NULL, NULL)); -} - -/** - * xmlHashQLookup2: - * @table: the hash table - * @prefix: the prefix of the userdata - * @name: the name of the userdata - * @prefix2: the second prefix of the userdata - * @name2: a second name of the userdata - * - * Find the userdata specified by the QNames tuple - * - * Returns the pointer to the userdata - */ -void * -xmlHashQLookup2(xmlHashTablePtr table, const xmlChar *prefix, - const xmlChar *name, const xmlChar *prefix2, - const xmlChar *name2) { - return(xmlHashQLookup3(table, prefix, name, prefix2, name2, NULL, NULL)); +xmlHashAddEntry2(xmlHashTablePtr hash, const xmlChar *key, + const xmlChar *key2, void *payload) { + return(xmlHashUpdateInternal(hash, key, key2, NULL, payload, NULL, 0)); } /** * xmlHashAddEntry3: - * @table: the hash table - * @name: the name of the userdata - * @name2: a second name of the userdata - * @name3: a third name of the userdata - * @userdata: a pointer to the userdata + * @hash: hash table + * @key: first string key + * @key2: second string key + * @key3: third string key + * @payload: pointer to the payload * - * Add the @userdata to the hash @table. This can later be retrieved - * by using the tuple (@name, @name2, @name3). Duplicate entries generate - * errors. + * Add a hash table entry with three strings as key. * - * Returns 0 the addition succeeded and -1 in case of error. + * See xmlHashAddEntry. */ int -xmlHashAddEntry3(xmlHashTablePtr table, const xmlChar *name, - const xmlChar *name2, const xmlChar *name3, - void *userdata) { - unsigned key, len = 0; - xmlHashEntryPtr entry; - xmlHashEntryPtr insert; +xmlHashAddEntry3(xmlHashTablePtr hash, const xmlChar *key, + const xmlChar *key2, const xmlChar *key3, + void *payload) { + return(xmlHashUpdateInternal(hash, key, key2, key3, payload, NULL, 0)); +} - if ((table == NULL) || (name == NULL) || (table->nbElems == INT_MAX)) - return(-1); +/** + * xmlHashUpdateEntry: + * @hash: hash table + * @key: string key + * @payload: pointer to the payload + * @dealloc: deallocator function for replaced item or NULL + * + * Add a hash table entry. If an entry with this key already exists, + * the old payload will be freed and updated with the new value. + * + * Returns 0 in case of success, -1 if a memory allocation failed. + */ +int +xmlHashUpdateEntry(xmlHashTablePtr hash, const xmlChar *key, + void *payload, xmlHashDeallocator dealloc) { + return(xmlHashUpdateInternal(hash, key, NULL, NULL, payload, + dealloc, 1)); +} - /* - * If using a dict internalize if needed - */ - if (table->dict) { - if (!xmlDictOwns(table->dict, name)) { - name = xmlDictLookup(table->dict, name, -1); - if (name == NULL) - return(-1); - } - if ((name2 != NULL) && (!xmlDictOwns(table->dict, name2))) { - name2 = xmlDictLookup(table->dict, name2, -1); - if (name2 == NULL) - return(-1); - } - if ((name3 != NULL) && (!xmlDictOwns(table->dict, name3))) { - name3 = xmlDictLookup(table->dict, name3, -1); - if (name3 == NULL) - return(-1); - } - } - - /* - * Check for duplicate and insertion location. - */ - key = xmlHashComputeKey(table, name, name2, name3); - if (table->table[key].valid == 0) { - insert = NULL; - } else { - if (table->dict) { - for (insert = &(table->table[key]); insert->next != NULL; - insert = insert->next) { - if ((insert->name == name) && - (insert->name2 == name2) && - (insert->name3 == name3)) - return(-1); - len++; - } - if ((insert->name == name) && - (insert->name2 == name2) && - (insert->name3 == name3)) - return(-1); - } else { - for (insert = &(table->table[key]); insert->next != NULL; - insert = insert->next) { - if ((xmlStrEqual(insert->name, name)) && - (xmlStrEqual(insert->name2, name2)) && - (xmlStrEqual(insert->name3, name3))) - return(-1); - len++; - } - if ((xmlStrEqual(insert->name, name)) && - (xmlStrEqual(insert->name2, name2)) && - (xmlStrEqual(insert->name3, name3))) - return(-1); - } - } - - if (insert == NULL) { - entry = &(table->table[key]); - } else { - entry = xmlMalloc(sizeof(xmlHashEntry)); - if (entry == NULL) - return(-1); - } - - if (table->dict != NULL) { - entry->name = (xmlChar *) name; - entry->name2 = (xmlChar *) name2; - entry->name3 = (xmlChar *) name3; - } else { - entry->name = xmlStrdup(name); - if (entry->name == NULL) { - entry->name2 = NULL; - goto error; - } - if (name2 == NULL) { - entry->name2 = NULL; - } else { - entry->name2 = xmlStrdup(name2); - if (entry->name2 == NULL) - goto error; - } - if (name3 == NULL) { - entry->name3 = NULL; - } else { - entry->name3 = xmlStrdup(name3); - if (entry->name3 == NULL) - goto error; - } - } - entry->payload = userdata; - entry->next = NULL; - entry->valid = 1; - - - if (insert != NULL) - insert->next = entry; - - table->nbElems++; - - if ((table->nbElems > table->size / MAX_FILL) || - (len > MAX_HASH_LEN)) { - int newSize = table->size > INT_MAX / GROWTH_FACTOR ? - INT_MAX : - GROWTH_FACTOR * table->size; - xmlHashGrow(table, newSize); - } - - return(0); - -error: - xmlFree(entry->name2); - xmlFree(entry->name); - if (insert != NULL) - xmlFree(entry); - return(-1); +/** + * xmlHashUpdateEntry2: + * @hash: hash table + * @key: first string key + * @key2: second string key + * @payload: pointer to the payload + * @dealloc: deallocator function for replaced item or NULL + * + * Add a hash table entry with two strings as key. + * + * See xmlHashUpdateEntry. + */ +int +xmlHashUpdateEntry2(xmlHashTablePtr hash, const xmlChar *key, + const xmlChar *key2, void *payload, + xmlHashDeallocator dealloc) { + return(xmlHashUpdateInternal(hash, key, key2, NULL, payload, + dealloc, 1)); } /** * xmlHashUpdateEntry3: - * @table: the hash table - * @name: the name of the userdata - * @name2: a second name of the userdata - * @name3: a third name of the userdata - * @userdata: a pointer to the userdata - * @f: the deallocator function for replaced item (if any) + * @hash: hash table + * @key: first string key + * @key2: second string key + * @key3: third string key + * @payload: pointer to the payload + * @dealloc: deallocator function for replaced item or NULL * - * Add the @userdata to the hash @table. This can later be retrieved - * by using the tuple (@name, @name2, @name3). Existing entry for this tuple - * will be removed and freed with @f if found. + * Add a hash table entry with three strings as key. * - * Returns 0 the addition succeeded and -1 in case of error. + * See xmlHashUpdateEntry. */ int -xmlHashUpdateEntry3(xmlHashTablePtr table, const xmlChar *name, - const xmlChar *name2, const xmlChar *name3, - void *userdata, xmlHashDeallocator f) { - unsigned key; - xmlHashEntryPtr entry; - xmlHashEntryPtr insert; +xmlHashUpdateEntry3(xmlHashTablePtr hash, const xmlChar *key, + const xmlChar *key2, const xmlChar *key3, + void *payload, xmlHashDeallocator dealloc) { + return(xmlHashUpdateInternal(hash, key, key2, key3, payload, + dealloc, 1)); +} - if ((table == NULL) || (name == NULL) || (table->nbElems == INT_MAX)) - return(-1); +/** + * xmlHashLookup: + * @hash: hash table + * @key: string key + * + * Find the entry specified by @key. + * + * Returns a pointer to the payload or NULL if no entry was found. + */ +void * +xmlHashLookup(xmlHashTablePtr hash, const xmlChar *key) { + return(xmlHashLookup3(hash, key, NULL, NULL)); +} - /* - * If using a dict internalize if needed - */ - if (table->dict) { - if (!xmlDictOwns(table->dict, name)) { - name = xmlDictLookup(table->dict, name, -1); - if (name == NULL) - return(-1); - } - if ((name2 != NULL) && (!xmlDictOwns(table->dict, name2))) { - name2 = xmlDictLookup(table->dict, name2, -1); - if (name2 == NULL) - return(-1); - } - if ((name3 != NULL) && (!xmlDictOwns(table->dict, name3))) { - name3 = xmlDictLookup(table->dict, name3, -1); - if (name3 == NULL) - return(-1); - } - } +/** + * xmlHashLookup2: + * @hash: hash table + * @key: first string key + * @key2: second string key + * + * Find the payload specified by the (@key, @key2) tuple. + * + * Returns a pointer to the payload or NULL if no entry was found. + */ +void * +xmlHashLookup2(xmlHashTablePtr hash, const xmlChar *key, + const xmlChar *key2) { + return(xmlHashLookup3(hash, key, key2, NULL)); +} - /* - * Check for duplicate and insertion location. - */ - key = xmlHashComputeKey(table, name, name2, name3); - if (table->table[key].valid == 0) { - insert = NULL; - } else { - if (table ->dict) { - for (insert = &(table->table[key]); insert->next != NULL; - insert = insert->next) { - if ((insert->name == name) && - (insert->name2 == name2) && - (insert->name3 == name3)) { - if (f) - f(insert->payload, insert->name); - insert->payload = userdata; - return(0); - } - } - if ((insert->name == name) && - (insert->name2 == name2) && - (insert->name3 == name3)) { - if (f) - f(insert->payload, insert->name); - insert->payload = userdata; - return(0); - } - } else { - for (insert = &(table->table[key]); insert->next != NULL; - insert = insert->next) { - if ((xmlStrEqual(insert->name, name)) && - (xmlStrEqual(insert->name2, name2)) && - (xmlStrEqual(insert->name3, name3))) { - if (f) - f(insert->payload, insert->name); - insert->payload = userdata; - return(0); - } - } - if ((xmlStrEqual(insert->name, name)) && - (xmlStrEqual(insert->name2, name2)) && - (xmlStrEqual(insert->name3, name3))) { - if (f) - f(insert->payload, insert->name); - insert->payload = userdata; - return(0); - } - } - } +/** + * xmlHashQLookup: + * @hash: hash table + * @prefix: prefix of the string key + * @name: local name of the string key + * + * Find the payload specified by the QName @prefix:@name or @name. + * + * Returns a pointer to the payload or NULL if no entry was found. + */ +void * +xmlHashQLookup(xmlHashTablePtr hash, const xmlChar *prefix, + const xmlChar *name) { + return(xmlHashQLookup3(hash, prefix, name, NULL, NULL, NULL, NULL)); +} - if (insert == NULL) { - entry = &(table->table[key]); - } else { - entry = xmlMalloc(sizeof(xmlHashEntry)); - if (entry == NULL) - return(-1); - } - - if (table->dict != NULL) { - entry->name = (xmlChar *) name; - entry->name2 = (xmlChar *) name2; - entry->name3 = (xmlChar *) name3; - } else { - entry->name = xmlStrdup(name); - if (entry->name == NULL) { - entry->name2 = NULL; - goto error; - } - if (name2 == NULL) { - entry->name2 = NULL; - } else { - entry->name2 = xmlStrdup(name2); - if (entry->name2 == NULL) - goto error; - } - if (name3 == NULL) { - entry->name3 = NULL; - } else { - entry->name3 = xmlStrdup(name3); - if (entry->name3 == NULL) - goto error; - } - } - entry->payload = userdata; - entry->next = NULL; - entry->valid = 1; - table->nbElems++; - - - if (insert != NULL) { - insert->next = entry; - } - return(0); - -error: - xmlFree(entry->name2); - xmlFree(entry->name); - if (insert != NULL) - xmlFree(entry); - return(-1); +/** + * xmlHashQLookup2: + * @hash: hash table + * @prefix: first prefix + * @name: first local name + * @prefix2: second prefix + * @name2: second local name + * + * Find the payload specified by the QNames tuple. + * + * Returns a pointer to the payload or NULL if no entry was found. + */ +void * +xmlHashQLookup2(xmlHashTablePtr hash, const xmlChar *prefix, + const xmlChar *name, const xmlChar *prefix2, + const xmlChar *name2) { + return(xmlHashQLookup3(hash, prefix, name, prefix2, name2, NULL, NULL)); } /** * xmlHashLookup3: - * @table: the hash table - * @name: the name of the userdata - * @name2: a second name of the userdata - * @name3: a third name of the userdata + * @hash: hash table + * @key: first string key + * @key2: second string key + * @key3: third string key * - * Find the userdata specified by the (@name, @name2, @name3) tuple. + * Find the payload specified by the (@key, @key2, @key3) tuple. * - * Returns the a pointer to the userdata + * Returns a pointer to the payload or NULL if no entry was found. */ void * -xmlHashLookup3(xmlHashTablePtr table, const xmlChar *name, - const xmlChar *name2, const xmlChar *name3) { - unsigned key; - xmlHashEntryPtr entry; +xmlHashLookup3(xmlHashTablePtr hash, const xmlChar *key, + const xmlChar *key2, const xmlChar *key3) { + const xmlHashEntry *entry; + unsigned hashValue; + int found; - if (table == NULL) - return(NULL); - if (name == NULL) - return(NULL); - key = xmlHashComputeKey(table, name, name2, name3); - if (table->table[key].valid == 0) - return(NULL); - if (table->dict) { - for (entry = &(table->table[key]); entry != NULL; entry = entry->next) { - if ((entry->name == name) && - (entry->name2 == name2) && - (entry->name3 == name3)) - return(entry->payload); - } - } - for (entry = &(table->table[key]); entry != NULL; entry = entry->next) { - if ((xmlStrEqual(entry->name, name)) && - (xmlStrEqual(entry->name2, name2)) && - (xmlStrEqual(entry->name3, name3))) - return(entry->payload); - } + if ((hash == NULL) || (hash->size == 0) || (key == NULL)) + return(NULL); + hashValue = xmlHashValue(hash->randomSeed, key, key2, key3, NULL); + entry = xmlHashFindEntry(hash, key, key2, key3, hashValue, &found); + if (found) + return(entry->payload); return(NULL); } /** * xmlHashQLookup3: - * @table: the hash table - * @prefix: the prefix of the userdata - * @name: the name of the userdata - * @prefix2: the second prefix of the userdata - * @name2: a second name of the userdata - * @prefix3: the third prefix of the userdata - * @name3: a third name of the userdata + * @hash: hash table + * @prefix: first prefix + * @name: first local name + * @prefix2: second prefix + * @name2: second local name + * @prefix3: third prefix + * @name3: third local name * - * Find the userdata specified by the (@name, @name2, @name3) tuple. + * Find the payload specified by the QNames tuple. * - * Returns the a pointer to the userdata + * Returns a pointer to the payload or NULL if no entry was found. */ +ATTRIBUTE_NO_SANITIZE_INTEGER void * -xmlHashQLookup3(xmlHashTablePtr table, +xmlHashQLookup3(xmlHashTablePtr hash, const xmlChar *prefix, const xmlChar *name, - const xmlChar *prefix2, const xmlChar *name2, - const xmlChar *prefix3, const xmlChar *name3) { - unsigned key; - xmlHashEntryPtr entry; + const xmlChar *prefix2, const xmlChar *name2, + const xmlChar *prefix3, const xmlChar *name3) { + const xmlHashEntry *entry; + unsigned hashValue, mask, pos, displ; - if (table == NULL) - return(NULL); - if (name == NULL) - return(NULL); - key = xmlHashComputeQKey(table, prefix, name, prefix2, - name2, prefix3, name3); - if (table->table[key].valid == 0) - return(NULL); - for (entry = &(table->table[key]); entry != NULL; entry = entry->next) { - if ((xmlStrQEqual(prefix, name, entry->name)) && - (xmlStrQEqual(prefix2, name2, entry->name2)) && - (xmlStrQEqual(prefix3, name3, entry->name3))) - return(entry->payload); + if ((hash == NULL) || (hash->size == 0) || (name == NULL)) + return(NULL); + + hashValue = xmlHashQNameValue(hash->randomSeed, prefix, name, prefix2, + name2, prefix3, name3); + mask = hash->size - 1; + pos = hashValue & mask; + entry = &hash->table[pos]; + + if (entry->hashValue != 0) { + displ = 0; + hashValue |= MAX_HASH_SIZE; + + do { + if ((hashValue == entry->hashValue) && + (xmlStrQEqual(prefix, name, entry->key)) && + (xmlStrQEqual(prefix2, name2, entry->key2)) && + (xmlStrQEqual(prefix3, name3, entry->key3))) + return(entry->payload); + + displ++; + pos++; + entry++; + if ((pos & mask) == 0) + entry = hash->table; + } while ((entry->hashValue != 0) && + (((pos - entry->hashValue) & mask) >= displ)); } + return(NULL); } typedef struct { - xmlHashScanner hashscanner; + xmlHashScanner scan; void *data; } stubData; static void -stubHashScannerFull (void *payload, void *data, const xmlChar *name, - const xmlChar *name2 ATTRIBUTE_UNUSED, - const xmlChar *name3 ATTRIBUTE_UNUSED) { - stubData *stubdata = (stubData *) data; - stubdata->hashscanner (payload, stubdata->data, (xmlChar *) name); +stubHashScannerFull(void *payload, void *data, const xmlChar *key, + const xmlChar *key2 ATTRIBUTE_UNUSED, + const xmlChar *key3 ATTRIBUTE_UNUSED) { + stubData *sdata = (stubData *) data; + sdata->scan(payload, sdata->data, key); } /** * xmlHashScan: - * @table: the hash table - * @f: the scanner function for items in the hash - * @data: extra data passed to f + * @hash: hash table + * @scan: scanner function for items in the hash + * @data: extra data passed to @scan * - * Scan the hash @table and applied @f to each value. + * Scan the hash @table and apply @scan to each value. */ void -xmlHashScan(xmlHashTablePtr table, xmlHashScanner f, void *data) { - stubData stubdata; - stubdata.data = data; - stubdata.hashscanner = f; - xmlHashScanFull (table, stubHashScannerFull, &stubdata); +xmlHashScan(xmlHashTablePtr hash, xmlHashScanner scan, void *data) { + stubData sdata; + sdata.data = data; + sdata.scan = scan; + xmlHashScanFull(hash, stubHashScannerFull, &sdata); } /** * xmlHashScanFull: - * @table: the hash table - * @f: the scanner function for items in the hash - * @data: extra data passed to f + * @hash: hash table + * @scan: scanner function for items in the hash + * @data: extra data passed to @scan * - * Scan the hash @table and applied @f to each value. + * Scan the hash @table and apply @scan to each value. */ void -xmlHashScanFull(xmlHashTablePtr table, xmlHashScannerFull f, void *data) { - int i, nb; - xmlHashEntryPtr iter; - xmlHashEntryPtr next; +xmlHashScanFull(xmlHashTablePtr hash, xmlHashScannerFull scan, void *data) { + const xmlHashEntry *entry, *end; - if (table == NULL) - return; - if (f == NULL) - return; + if ((hash == NULL) || (hash->size == 0) || (scan == NULL)) + return; - if (table->table) { - for(i = 0; i < table->size; i++) { - if (table->table[i].valid == 0) - continue; - iter = &(table->table[i]); - while (iter) { - next = iter->next; - nb = table->nbElems; - if ((f != NULL) && (iter->payload != NULL)) - f(iter->payload, data, iter->name, - iter->name2, iter->name3); - if (nb != table->nbElems) { - /* table was modified by the callback, be careful */ - if (iter == &(table->table[i])) { - if (table->table[i].valid == 0) - iter = NULL; - if (table->table[i].next != next) - iter = &(table->table[i]); - } else - iter = next; - } else - iter = next; - } - } + end = &hash->table[hash->size]; + + for (entry = hash->table; entry < end; entry++) { + if ((entry->hashValue != 0) && (entry->payload != NULL)) + scan(entry->payload, data, entry->key, entry->key2, entry->key3); } } /** * xmlHashScan3: - * @table: the hash table - * @name: the name of the userdata or NULL - * @name2: a second name of the userdata or NULL - * @name3: a third name of the userdata or NULL - * @f: the scanner function for items in the hash - * @data: extra data passed to f + * @hash: hash table + * @key: first string key or NULL + * @key2: second string key or NULL + * @key3: third string key or NULL + * @scan: scanner function for items in the hash + * @data: extra data passed to @scan * - * Scan the hash @table and applied @f to each value matching - * (@name, @name2, @name3) tuple. If one of the names is null, + * Scan the hash @table and apply @scan to each value matching + * (@key, @key2, @key3) tuple. If one of the keys is null, * the comparison is considered to match. */ void -xmlHashScan3(xmlHashTablePtr table, const xmlChar *name, - const xmlChar *name2, const xmlChar *name3, - xmlHashScanner f, void *data) { - stubData stubdata; - stubdata.data = data; - stubdata.hashscanner = f; - xmlHashScanFull3(table, name, name2, name3, stubHashScannerFull, - &stubdata); +xmlHashScan3(xmlHashTablePtr hash, const xmlChar *key, + const xmlChar *key2, const xmlChar *key3, + xmlHashScanner scan, void *data) { + stubData sdata; + sdata.data = data; + sdata.scan = scan; + xmlHashScanFull3(hash, key, key2, key3, stubHashScannerFull, &sdata); } /** * xmlHashScanFull3: - * @table: the hash table - * @name: the name of the userdata or NULL - * @name2: a second name of the userdata or NULL - * @name3: a third name of the userdata or NULL - * @f: the scanner function for items in the hash - * @data: extra data passed to f + * @hash: hash table + * @key: first string key or NULL + * @key2: second string key or NULL + * @key3: third string key or NULL + * @scan: scanner function for items in the hash + * @data: extra data passed to @scan * - * Scan the hash @table and applied @f to each value matching - * (@name, @name2, @name3) tuple. If one of the names is null, + * Scan the hash @table and apply @scan to each value matching + * (@key, @key2, @key3) tuple. If one of the keys is null, * the comparison is considered to match. */ void -xmlHashScanFull3(xmlHashTablePtr table, const xmlChar *name, - const xmlChar *name2, const xmlChar *name3, - xmlHashScannerFull f, void *data) { - int i; - xmlHashEntryPtr iter; - xmlHashEntryPtr next; +xmlHashScanFull3(xmlHashTablePtr hash, const xmlChar *key, + const xmlChar *key2, const xmlChar *key3, + xmlHashScannerFull scan, void *data) { + const xmlHashEntry *entry, *end; - if (table == NULL) - return; - if (f == NULL) - return; + if ((hash == NULL) || (hash->size == 0) || (scan == NULL)) + return; - if (table->table) { - for(i = 0; i < table->size; i++) { - if (table->table[i].valid == 0) - continue; - iter = &(table->table[i]); - while (iter) { - next = iter->next; - if (((name == NULL) || (xmlStrEqual(name, iter->name))) && - ((name2 == NULL) || (xmlStrEqual(name2, iter->name2))) && - ((name3 == NULL) || (xmlStrEqual(name3, iter->name3))) && - (iter->payload != NULL)) { - f(iter->payload, data, iter->name, - iter->name2, iter->name3); - } - iter = next; - } - } + end = &hash->table[hash->size]; + + for (entry = hash->table; entry < end; entry++) { + if (entry->hashValue == 0) + continue; + if (((key == NULL) || + (strcmp((const char *) key, (const char *) entry->key) == 0)) && + ((key2 == NULL) || (xmlFastStrEqual(key2, entry->key2))) && + ((key3 == NULL) || (xmlFastStrEqual(key3, entry->key3))) && + (entry->payload != NULL)) { + scan(entry->payload, data, entry->key, entry->key2, entry->key3); + } } } /** * xmlHashCopy: - * @table: the hash table - * @f: the copier function for items in the hash + * @hash: hash table + * @copy: copier function for items in the hash * - * Scan the hash @table and applied @f to each value. + * Copy the hash @table using @copy to copy payloads. * - * Returns the new table or NULL in case of error. + * Returns the new table or NULL if a memory allocation failed. */ xmlHashTablePtr -xmlHashCopy(xmlHashTablePtr table, xmlHashCopier f) { - int i; - xmlHashEntryPtr iter; - xmlHashEntryPtr next; +xmlHashCopy(xmlHashTablePtr hash, xmlHashCopier copy) { + const xmlHashEntry *entry, *end; xmlHashTablePtr ret; - if (table == NULL) - return(NULL); - if (f == NULL) - return(NULL); + if ((hash == NULL) || (copy == NULL)) + return(NULL); - ret = xmlHashCreate(table->size); + ret = xmlHashCreate(hash->size); if (ret == NULL) return(NULL); - if (table->table) { - for(i = 0; i < table->size; i++) { - if (table->table[i].valid == 0) - continue; - iter = &(table->table[i]); - while (iter) { - next = iter->next; - xmlHashAddEntry3(ret, iter->name, iter->name2, - iter->name3, f(iter->payload, iter->name)); - iter = next; - } - } + if (hash->size == 0) + return(ret); + + end = &hash->table[hash->size]; + + for (entry = hash->table; entry < end; entry++) { + if (entry->hashValue != 0) + xmlHashAddEntry3(ret, entry->key, entry->key2, entry->key3, + copy(entry->payload, entry->key)); } - ret->nbElems = table->nbElems; + return(ret); } /** * xmlHashSize: - * @table: the hash table + * @hash: hash table * - * Query the number of elements installed in the hash @table. + * Query the number of elements in the hash table. * * Returns the number of elements in the hash table or - * -1 in case of error + * -1 in case of error. */ int -xmlHashSize(xmlHashTablePtr table) { - if (table == NULL) - return(-1); - return(table->nbElems); +xmlHashSize(xmlHashTablePtr hash) { + if (hash == NULL) + return(-1); + return(hash->nbElems); } /** * xmlHashRemoveEntry: - * @table: the hash table - * @name: the name of the userdata - * @f: the deallocator function for removed item (if any) + * @hash: hash table + * @key: string key + * @dealloc: deallocator function for removed item or NULL * - * Find the userdata specified by the @name and remove - * it from the hash @table. Existing userdata for this tuple will be removed - * and freed with @f. + * Find the entry specified by the @key and remove it from the hash table. + * Payload will be freed with @dealloc. * - * Returns 0 if the removal succeeded and -1 in case of error or not found. + * Returns 0 on success and -1 if no entry was found. */ -int xmlHashRemoveEntry(xmlHashTablePtr table, const xmlChar *name, - xmlHashDeallocator f) { - return(xmlHashRemoveEntry3(table, name, NULL, NULL, f)); +int xmlHashRemoveEntry(xmlHashTablePtr hash, const xmlChar *key, + xmlHashDeallocator dealloc) { + return(xmlHashRemoveEntry3(hash, key, NULL, NULL, dealloc)); } /** * xmlHashRemoveEntry2: - * @table: the hash table - * @name: the name of the userdata - * @name2: a second name of the userdata - * @f: the deallocator function for removed item (if any) + * @hash: hash table + * @key: first string key + * @key2: second string key + * @dealloc: deallocator function for removed item or NULL * - * Find the userdata specified by the (@name, @name2) tuple and remove - * it from the hash @table. Existing userdata for this tuple will be removed - * and freed with @f. + * Remove an entry with two strings as key. * - * Returns 0 if the removal succeeded and -1 in case of error or not found. + * See xmlHashRemoveEntry. */ int -xmlHashRemoveEntry2(xmlHashTablePtr table, const xmlChar *name, - const xmlChar *name2, xmlHashDeallocator f) { - return(xmlHashRemoveEntry3(table, name, name2, NULL, f)); +xmlHashRemoveEntry2(xmlHashTablePtr hash, const xmlChar *key, + const xmlChar *key2, xmlHashDeallocator dealloc) { + return(xmlHashRemoveEntry3(hash, key, key2, NULL, dealloc)); } /** * xmlHashRemoveEntry3: - * @table: the hash table - * @name: the name of the userdata - * @name2: a second name of the userdata - * @name3: a third name of the userdata - * @f: the deallocator function for removed item (if any) + * @hash: hash table + * @key: first string key + * @key2: second string key + * @key3: third string key + * @dealloc: deallocator function for removed item or NULL * - * Find the userdata specified by the (@name, @name2, @name3) tuple and remove - * it from the hash @table. Existing userdata for this tuple will be removed - * and freed with @f. + * Remove an entry with three strings as key. * - * Returns 0 if the removal succeeded and -1 in case of error or not found. + * See xmlHashRemoveEntry. */ +ATTRIBUTE_NO_SANITIZE_INTEGER int -xmlHashRemoveEntry3(xmlHashTablePtr table, const xmlChar *name, - const xmlChar *name2, const xmlChar *name3, xmlHashDeallocator f) { - unsigned key; - xmlHashEntryPtr entry; - xmlHashEntryPtr prev = NULL; +xmlHashRemoveEntry3(xmlHashTablePtr hash, const xmlChar *key, + const xmlChar *key2, const xmlChar *key3, + xmlHashDeallocator dealloc) { + xmlHashEntry *entry, *cur, *next; + unsigned hashValue, mask, pos, nextpos; + int found; - if (table == NULL || name == NULL) + if ((hash == NULL) || (hash->size == 0) || (key == NULL)) return(-1); - key = xmlHashComputeKey(table, name, name2, name3); - if (table->table[key].valid == 0) { + hashValue = xmlHashValue(hash->randomSeed, key, key2, key3, NULL); + entry = xmlHashFindEntry(hash, key, key2, key3, hashValue, &found); + if (!found) return(-1); - } else { - for (entry = &(table->table[key]); entry != NULL; entry = entry->next) { - if (xmlStrEqual(entry->name, name) && - xmlStrEqual(entry->name2, name2) && - xmlStrEqual(entry->name3, name3)) { - if ((f != NULL) && (entry->payload != NULL)) - f(entry->payload, entry->name); - entry->payload = NULL; - if (table->dict == NULL) { - if(entry->name) - xmlFree(entry->name); - if(entry->name2) - xmlFree(entry->name2); - if(entry->name3) - xmlFree(entry->name3); - } - if(prev) { - prev->next = entry->next; - xmlFree(entry); - } else { - if (entry->next == NULL) { - entry->valid = 0; - } else { - entry = entry->next; - memcpy(&(table->table[key]), entry, sizeof(xmlHashEntry)); - xmlFree(entry); - } - } - table->nbElems--; - return(0); - } - prev = entry; - } - return(-1); + + if ((dealloc != NULL) && (entry->payload != NULL)) + dealloc(entry->payload, entry->key); + if (hash->dict == NULL) { + if (entry->key) + xmlFree(entry->key); + if (entry->key2) + xmlFree(entry->key2); + if (entry->key3) + xmlFree(entry->key3); } + + /* + * Find end of probe sequence. Entries at their initial probe + * position start a new sequence. + */ + mask = hash->size - 1; + pos = entry - hash->table; + cur = entry; + + while (1) { + nextpos = pos + 1; + next = cur + 1; + if ((nextpos & mask) == 0) + next = hash->table; + + if ((next->hashValue == 0) || + (((next->hashValue - nextpos) & mask) == 0)) + break; + + cur = next; + pos = nextpos; + } + + /* + * Backward shift + */ + next = entry + 1; + + if (cur < entry) { + xmlHashEntry *end = &hash->table[hash->size]; + + memmove(entry, next, (char *) end - (char *) next); + entry = hash->table; + end[-1] = *entry; + next = entry + 1; + } + + memmove(entry, next, (char *) cur - (char *) entry); + + /* + * Update entry + */ + cur->hashValue = 0; + + hash->nbElems--; + + return(0); }
diff --git a/src/include/libxml/entities.h b/src/include/libxml/entities.h index 2c69514..615ead4 100644 --- a/src/include/libxml/entities.h +++ b/src/include/libxml/entities.h
@@ -85,6 +85,8 @@ const xmlChar *ExternalID, const xmlChar *SystemID, const xmlChar *content); +XMLPUBFUN void + xmlFreeEntity (xmlEntityPtr entity); XMLPUBFUN xmlEntityPtr xmlAddDocEntity (xmlDocPtr doc, const xmlChar *name,
diff --git a/src/include/libxml/parser.h b/src/include/libxml/parser.h index 046c0d0..5c3f02f 100644 --- a/src/include/libxml/parser.h +++ b/src/include/libxml/parser.h
@@ -172,6 +172,8 @@ } xmlParserMode; typedef struct _xmlStartTag xmlStartTag; +typedef struct _xmlParserNsData xmlParserNsData; +typedef struct _xmlAttrHashBucket xmlAttrHashBucket; /** * xmlParserCtxt: @@ -282,7 +284,7 @@ int nsNr; /* the number of inherited namespaces */ int nsMax; /* the size of the arrays */ const xmlChar * *nsTab; /* the array of prefix/namespace name */ - int *attallocs; /* which attribute were allocated */ + unsigned *attallocs; /* which attribute were allocated */ xmlStartTag *pushTab; /* array of data for push */ xmlHashTablePtr attsDefault; /* defaulted attributes if any */ xmlHashTablePtr attsSpecial; /* non-CDATA attributes if any */ @@ -319,6 +321,10 @@ unsigned short nbErrors; /* number of errors */ unsigned short nbWarnings; /* number of warnings */ unsigned maxAmpl; /* maximum amplification factor */ + + xmlParserNsData *nsdb; /* namespace database */ + unsigned attrHashMax; /* allocated size */ + xmlAttrHashBucket *attrHash; /* atttribute hash table */ }; /**
diff --git a/src/include/libxml/uri.h b/src/include/libxml/uri.h index 2717f69..eb8631c 100644 --- a/src/include/libxml/uri.h +++ b/src/include/libxml/uri.h
@@ -11,6 +11,7 @@ #ifndef __XML_URI_H__ #define __XML_URI_H__ +#include <stdio.h> #include <libxml/xmlversion.h> #include <libxml/xmlstring.h>
diff --git a/src/include/libxml/xmlerror.h b/src/include/libxml/xmlerror.h index 2d3651e..2dd792a 100644 --- a/src/include/libxml/xmlerror.h +++ b/src/include/libxml/xmlerror.h
@@ -856,7 +856,7 @@ * Signature of the function to use when there is an error and * the module handles the new error reporting mechanism. */ -typedef void (*xmlStructuredErrorFunc) (void *userData, xmlErrorPtr error); +typedef void (*xmlStructuredErrorFunc) (void *userData, const xmlError *error); /** DOC_DISABLE */ #define XML_GLOBALS_ERROR \ @@ -932,7 +932,7 @@ xmlGetLastError (void); XMLPUBFUN void xmlResetLastError (void); -XMLPUBFUN xmlErrorPtr +XMLPUBFUN const xmlError * xmlCtxtGetLastError (void *ctx); XMLPUBFUN void xmlCtxtResetLastError (void *ctx);
diff --git a/src/include/libxml/xmlmemory.h b/src/include/libxml/xmlmemory.h index 1a43882..a3e26dd 100644 --- a/src/include/libxml/xmlmemory.h +++ b/src/include/libxml/xmlmemory.h
@@ -80,7 +80,7 @@ #define XML_OP XML_DECLARE_GLOBAL XML_GLOBALS_ALLOC #undef XML_OP - #ifdef LIBXML_THREAD_ENABLED + #if defined(LIBXML_THREAD_ENABLED) && !defined(XML_GLOBALS_NO_REDEFINITION) #define xmlMalloc XML_GLOBAL_MACRO(xmlMalloc) #define xmlMallocAtomic XML_GLOBAL_MACRO(xmlMallocAtomic) #define xmlRealloc XML_GLOBAL_MACRO(xmlRealloc)
diff --git a/src/include/libxml/xmlschemas.h b/src/include/libxml/xmlschemas.h index 1ad5be9..c2af3d7 100644 --- a/src/include/libxml/xmlschemas.h +++ b/src/include/libxml/xmlschemas.h
@@ -16,6 +16,7 @@ #ifdef LIBXML_SCHEMAS_ENABLED +#include <stdio.h> #include <libxml/encoding.h> #include <libxml/tree.h> #include <libxml/xmlerror.h>
diff --git a/src/include/libxml/xpathInternals.h b/src/include/libxml/xpathInternals.h index 870055f..d1c90df 100644 --- a/src/include/libxml/xpathInternals.h +++ b/src/include/libxml/xpathInternals.h
@@ -12,6 +12,7 @@ #ifndef __XML_XPATH_INTERNALS_H__ #define __XML_XPATH_INTERNALS_H__ +#include <stdio.h> #include <libxml/xmlversion.h> #include <libxml/xpath.h>
diff --git a/src/include/private/dict.h b/src/include/private/dict.h index 9dcbc1d..21084a7 100644 --- a/src/include/private/dict.h +++ b/src/include/private/dict.h
@@ -1,6 +1,8 @@ #ifndef XML_DICT_H_PRIVATE__ #define XML_DICT_H_PRIVATE__ +#include <libxml/dict.h> + /* * Values are ANDed with 0xFFFFFFFF to support platforms where * unsigned is larger than 32 bits. With 32-bit unsigned values, @@ -43,10 +45,25 @@ h2 &= 0xFFFFFFFF; \ } while (0) +typedef struct { + unsigned hashValue; + const xmlChar *name; +} xmlHashedString; + XML_HIDDEN void xmlInitDictInternal(void); XML_HIDDEN void xmlCleanupDictInternal(void); + +unsigned +xmlDictComputeHash(const xmlDict *dict, const xmlChar *string); +xmlHashedString +xmlDictLookupHashed(xmlDictPtr dict, const xmlChar *name, int len); + +XML_HIDDEN void +xmlInitRandom(void); +XML_HIDDEN void +xmlCleanupRandom(void); XML_HIDDEN unsigned xmlRandom(void);
diff --git a/src/include/private/parser.h b/src/include/private/parser.h index 50cf218..40d179f 100644 --- a/src/include/private/parser.h +++ b/src/include/private/parser.h
@@ -24,7 +24,7 @@ #define XML_INPUT_AUTO_UTF16BE (3u << 1) #define XML_INPUT_AUTO_OTHER (4u << 1) #define XML_INPUT_USES_ENC_DECL (1u << 4) -#define XML_INPUT_8_BIT (1u << 5) +#define XML_INPUT_ENCODING_ERROR (1u << 5) XML_HIDDEN void xmlErrMemory(xmlParserCtxtPtr ctxt, const char *extra); @@ -49,4 +49,18 @@ XML_HIDDEN void xmlSetDeclaredEncoding(xmlParserCtxtPtr ctxt, xmlChar *encoding); +XML_HIDDEN xmlParserNsData * +xmlParserNsCreate(void); +XML_HIDDEN void +xmlParserNsFree(xmlParserNsData *nsdb); +/* + * These functions allow SAX handlers to attach extra data to namespaces + * efficiently and should be made public. + */ +XML_HIDDEN int +xmlParserNsUpdateSax(xmlParserCtxtPtr ctxt, const xmlChar *prefix, + void *saxData); +XML_HIDDEN void * +xmlParserNsLookupSax(xmlParserCtxtPtr ctxt, const xmlChar *prefix); + #endif /* XML_PARSER_H_PRIVATE__ */
diff --git a/src/libxml.h b/src/libxml.h index c3d04bc..2f72e0a 100644 --- a/src/libxml.h +++ b/src/libxml.h
@@ -59,4 +59,12 @@ #define ATTRIBUTE_NO_SANITIZE(arg) #endif +#ifdef __clang__ + #define ATTRIBUTE_NO_SANITIZE_INTEGER \ + ATTRIBUTE_NO_SANITIZE("unsigned-integer-overflow") \ + ATTRIBUTE_NO_SANITIZE("unsigned-shift-base") +#else + #define ATTRIBUTE_NO_SANITIZE_INTEGER +#endif + #endif /* ! __XML_LIBXML_H__ */
diff --git a/src/parser.c b/src/parser.c index e3e93ea..9fbd546 100644 --- a/src/parser.c +++ b/src/parser.c
@@ -67,12 +67,18 @@ #endif #include "private/buf.h" +#include "private/dict.h" #include "private/entities.h" #include "private/error.h" #include "private/html.h" #include "private/io.h" #include "private/parser.h" +#define NS_INDEX_EMPTY INT_MAX +#define NS_INDEX_XML (INT_MAX - 1) +#define URI_HASH_EMPTY 0xD943A04E +#define URI_HASH_XML 0xF0451F02 + struct _xmlStartTag { const xmlChar *prefix; const xmlChar *URI; @@ -80,6 +86,35 @@ int nsNr; }; +typedef struct { + void *saxData; + unsigned prefixHashValue; + unsigned uriHashValue; + unsigned elementId; + int oldIndex; +} xmlParserNsExtra; + +typedef struct { + unsigned hashValue; + int index; +} xmlParserNsBucket; + +struct _xmlParserNsData { + xmlParserNsExtra *extra; + + unsigned hashSize; + unsigned hashElems; + xmlParserNsBucket *hash; + + unsigned elementId; + int defaultNsIndex; +}; + +struct _xmlAttrHashBucket { + unsigned hashValue; + int index; +}; + static xmlParserCtxtPtr xmlCreateEntityParserCtxtInternal(xmlSAXHandlerPtr sax, void *userData, const xmlChar *URL, const xmlChar *ID, const xmlChar *base, @@ -129,7 +164,6 @@ -#define SAX2 1 #define XML_PARSER_BIG_BUFFER_SIZE 300 #define XML_PARSER_BUFFER_SIZE 100 #define SAX_COMPAT_MODE BAD_CAST "SAX compatibility mode document" @@ -845,6 +879,15 @@ } } +typedef struct { + xmlHashedString prefix; + xmlHashedString name; + xmlHashedString value; + const xmlChar *valueEnd; + int external; + int expandedSize; +} xmlDefAttr; + typedef struct _xmlDefAttrs xmlDefAttrs; typedef xmlDefAttrs *xmlDefAttrsPtr; struct _xmlDefAttrs { @@ -852,9 +895,9 @@ int maxAttrs; /* the size of the array */ #if __STDC_VERSION__ >= 199901L /* Using a C99 flexible array member avoids UBSan errors. */ - const xmlChar *values[]; /* array of localname/prefix/values/external */ + xmlDefAttr attrs[]; /* array of localname/prefix/values/external */ #else - const xmlChar *values[5]; + xmlDefAttr attrs[1]; #endif }; @@ -971,9 +1014,12 @@ const xmlChar *fullattr, const xmlChar *value) { xmlDefAttrsPtr defaults; - int len; - const xmlChar *name; - const xmlChar *prefix; + xmlDefAttr *attr; + int len, expandedSize; + xmlHashedString name; + xmlHashedString prefix; + xmlHashedString hvalue; + const xmlChar *localname; /* * Allows to detect attribute redefinitions @@ -993,41 +1039,38 @@ * split the element name into prefix:localname , the string found * are within the DTD and then not associated to namespace names. */ - name = xmlSplitQName3(fullname, &len); - if (name == NULL) { - name = xmlDictLookup(ctxt->dict, fullname, -1); - prefix = NULL; + localname = xmlSplitQName3(fullname, &len); + if (localname == NULL) { + name = xmlDictLookupHashed(ctxt->dict, fullname, -1); + prefix.name = NULL; } else { - name = xmlDictLookup(ctxt->dict, name, -1); - prefix = xmlDictLookup(ctxt->dict, fullname, len); + name = xmlDictLookupHashed(ctxt->dict, localname, -1); + prefix = xmlDictLookupHashed(ctxt->dict, fullname, len); + if (prefix.name == NULL) + goto mem_error; } + if (name.name == NULL) + goto mem_error; /* * make sure there is some storage */ - defaults = xmlHashLookup2(ctxt->attsDefault, name, prefix); - if (defaults == NULL) { - defaults = (xmlDefAttrsPtr) xmlMalloc(sizeof(xmlDefAttrs) + - (4 * 5) * sizeof(const xmlChar *)); - if (defaults == NULL) - goto mem_error; - defaults->nbAttrs = 0; - defaults->maxAttrs = 4; - if (xmlHashUpdateEntry2(ctxt->attsDefault, name, prefix, - defaults, NULL) < 0) { - xmlFree(defaults); - goto mem_error; - } - } else if (defaults->nbAttrs >= defaults->maxAttrs) { + defaults = xmlHashLookup2(ctxt->attsDefault, name.name, prefix.name); + if ((defaults == NULL) || + (defaults->nbAttrs >= defaults->maxAttrs)) { xmlDefAttrsPtr temp; + int newSize; - temp = (xmlDefAttrsPtr) xmlRealloc(defaults, sizeof(xmlDefAttrs) + - (2 * defaults->maxAttrs * 5) * sizeof(const xmlChar *)); + newSize = (defaults != NULL) ? 2 * defaults->maxAttrs : 4; + temp = xmlRealloc(defaults, + sizeof(*defaults) + newSize * sizeof(xmlDefAttr)); if (temp == NULL) goto mem_error; - defaults = temp; - defaults->maxAttrs *= 2; - if (xmlHashUpdateEntry2(ctxt->attsDefault, name, prefix, + if (defaults == NULL) + temp->nbAttrs = 0; + temp->maxAttrs = newSize; + defaults = temp; + if (xmlHashUpdateEntry2(ctxt->attsDefault, name.name, prefix.name, defaults, NULL) < 0) { xmlFree(defaults); goto mem_error; @@ -1035,32 +1078,40 @@ } /* - * Split the element name into prefix:localname , the string found + * Split the attribute name into prefix:localname , the string found * are within the DTD and hen not associated to namespace names. */ - name = xmlSplitQName3(fullattr, &len); - if (name == NULL) { - name = xmlDictLookup(ctxt->dict, fullattr, -1); - prefix = NULL; + localname = xmlSplitQName3(fullattr, &len); + if (localname == NULL) { + name = xmlDictLookupHashed(ctxt->dict, fullattr, -1); + prefix.name = NULL; } else { - name = xmlDictLookup(ctxt->dict, name, -1); - prefix = xmlDictLookup(ctxt->dict, fullattr, len); + name = xmlDictLookupHashed(ctxt->dict, localname, -1); + prefix = xmlDictLookupHashed(ctxt->dict, fullattr, len); + if (prefix.name == NULL) + goto mem_error; } - - defaults->values[5 * defaults->nbAttrs] = name; - defaults->values[5 * defaults->nbAttrs + 1] = prefix; - /* intern the string and precompute the end */ - len = xmlStrlen(value); - value = xmlDictLookup(ctxt->dict, value, len); - if (value == NULL) + if (name.name == NULL) goto mem_error; - defaults->values[5 * defaults->nbAttrs + 2] = value; - defaults->values[5 * defaults->nbAttrs + 3] = value + len; - if (ctxt->external) - defaults->values[5 * defaults->nbAttrs + 4] = BAD_CAST "external"; - else - defaults->values[5 * defaults->nbAttrs + 4] = NULL; - defaults->nbAttrs++; + + /* intern the string and precompute the end */ + len = strlen((const char *) value); + hvalue = xmlDictLookupHashed(ctxt->dict, value, len); + if (hvalue.name == NULL) + goto mem_error; + + expandedSize = strlen((const char *) name.name); + if (prefix.name != NULL) + expandedSize += strlen((const char *) prefix.name); + expandedSize += len; + + attr = &defaults->attrs[defaults->nbAttrs++]; + attr->name = name; + attr->prefix = prefix; + attr->value = hvalue; + attr->valueEnd = hvalue.name + len; + attr->external = ctxt->external; + attr->expandedSize = expandedSize; return; @@ -1346,93 +1397,463 @@ static xmlEntityPtr xmlParseStringEntityRef(xmlParserCtxtPtr ctxt, const xmlChar ** str); -#ifdef SAX2 /** - * nsPush: - * @ctxt: an XML parser context - * @prefix: the namespace prefix or NULL - * @URL: the namespace name + * xmlParserNsCreate: * - * Pushes a new parser namespace on top of the ns stack + * Create a new namespace database. * - * Returns -1 in case of error, -2 if the namespace should be discarded - * and the index in the stack otherwise. + * Returns the new obejct. + */ +xmlParserNsData * +xmlParserNsCreate(void) { + xmlParserNsData *nsdb = xmlMalloc(sizeof(*nsdb)); + + if (nsdb == NULL) + return(NULL); + memset(nsdb, 0, sizeof(*nsdb)); + nsdb->defaultNsIndex = INT_MAX; + + return(nsdb); +} + +/** + * xmlParserNsFree: + * @nsdb: namespace database + * + * Free a namespace database. + */ +void +xmlParserNsFree(xmlParserNsData *nsdb) { + if (nsdb == NULL) + return; + + xmlFree(nsdb->extra); + xmlFree(nsdb->hash); + xmlFree(nsdb); +} + +/** + * xmlParserNsReset: + * @nsdb: namespace database + * + * Reset a namespace database. + */ +static void +xmlParserNsReset(xmlParserNsData *nsdb) { + if (nsdb == NULL) + return; + + nsdb->hashElems = 0; + nsdb->elementId = 0; + nsdb->defaultNsIndex = INT_MAX; + + if (nsdb->hash) + memset(nsdb->hash, 0, nsdb->hashSize * sizeof(nsdb->hash[0])); +} + +/** + * xmlParserStartElement: + * @nsdb: namespace database + * + * Signal that a new element has started. + * + * Returns 0 on success, -1 if the element counter overflowed. */ static int -nsPush(xmlParserCtxtPtr ctxt, const xmlChar *prefix, const xmlChar *URL) -{ - if (ctxt->options & XML_PARSE_NSCLEAN) { - int i; - for (i = ctxt->nsNr - 2;i >= 0;i -= 2) { - if (ctxt->nsTab[i] == prefix) { - /* in scope */ - if (ctxt->nsTab[i + 1] == URL) - return(-2); - /* out of scope keep it */ - break; - } - } - } - if ((ctxt->nsMax == 0) || (ctxt->nsTab == NULL)) { - ctxt->nsMax = 10; - ctxt->nsNr = 0; - ctxt->nsTab = (const xmlChar **) - xmlMalloc(ctxt->nsMax * sizeof(xmlChar *)); - if (ctxt->nsTab == NULL) { - xmlErrMemory(ctxt, NULL); - ctxt->nsMax = 0; - return (-1); - } - } else if (ctxt->nsNr >= ctxt->nsMax) { - const xmlChar ** tmp; - ctxt->nsMax *= 2; - tmp = (const xmlChar **) xmlRealloc((char *) ctxt->nsTab, - ctxt->nsMax * sizeof(ctxt->nsTab[0])); - if (tmp == NULL) { - xmlErrMemory(ctxt, NULL); - ctxt->nsMax /= 2; - return (-1); - } - ctxt->nsTab = tmp; - } - ctxt->nsTab[ctxt->nsNr++] = prefix; - ctxt->nsTab[ctxt->nsNr++] = URL; - return (ctxt->nsNr); +xmlParserNsStartElement(xmlParserNsData *nsdb) { + if (nsdb->elementId == UINT_MAX) + return(-1); + nsdb->elementId++; + + return(0); } + /** - * nsPop: + * xmlParserNsLookup: + * @ctxt: parser context + * @prefix: namespace prefix + * @bucketPtr: optional bucket (return value) + * + * Lookup namespace with given prefix. If @bucketPtr is non-NULL, it will + * be set to the matching bucket, or the first empty bucket if no match + * was found. + * + * Returns the namespace index on success, INT_MAX if no namespace was + * found. + */ +static int +xmlParserNsLookup(xmlParserCtxtPtr ctxt, const xmlHashedString *prefix, + xmlParserNsBucket **bucketPtr) { + xmlParserNsBucket *bucket; + unsigned index, hashValue; + + if (prefix->name == NULL) + return(ctxt->nsdb->defaultNsIndex); + + if (ctxt->nsdb->hashSize == 0) + return(INT_MAX); + + hashValue = prefix->hashValue; + index = hashValue & (ctxt->nsdb->hashSize - 1); + bucket = &ctxt->nsdb->hash[index]; + + while (bucket->hashValue) { + if ((bucket->hashValue == hashValue) && + (bucket->index != INT_MAX)) { + if (ctxt->nsTab[bucket->index * 2] == prefix->name) { + if (bucketPtr != NULL) + *bucketPtr = bucket; + return(bucket->index); + } + } + + index++; + bucket++; + if (index == ctxt->nsdb->hashSize) { + index = 0; + bucket = ctxt->nsdb->hash; + } + } + + if (bucketPtr != NULL) + *bucketPtr = bucket; + return(INT_MAX); +} + +/** + * xmlParserNsLookupUri: + * @ctxt: parser context + * @prefix: namespace prefix + * + * Lookup namespace URI with given prefix. + * + * Returns the namespace URI on success, NULL if no namespace was found. + */ +static const xmlChar * +xmlParserNsLookupUri(xmlParserCtxtPtr ctxt, const xmlHashedString *prefix) { + const xmlChar *ret; + int nsIndex; + + if (prefix->name == ctxt->str_xml) + return(ctxt->str_xml_ns); + + nsIndex = xmlParserNsLookup(ctxt, prefix, NULL); + if (nsIndex == INT_MAX) + return(NULL); + + ret = ctxt->nsTab[nsIndex * 2 + 1]; + if (ret[0] == 0) + ret = NULL; + return(ret); +} + +/** + * xmlParserNsLookupSax: + * @ctxt: parser context + * @prefix: namespace prefix + * + * Lookup extra data for the given prefix. This returns data stored + * with xmlParserNsUdpateSax. + * + * Returns the data on success, NULL if no namespace was found. + */ +void * +xmlParserNsLookupSax(xmlParserCtxtPtr ctxt, const xmlChar *prefix) { + xmlHashedString hprefix; + int nsIndex; + + if (prefix == ctxt->str_xml) + return(NULL); + + hprefix.name = prefix; + if (prefix != NULL) + hprefix.hashValue = xmlDictComputeHash(ctxt->dict, prefix); + else + hprefix.hashValue = 0; + nsIndex = xmlParserNsLookup(ctxt, &hprefix, NULL); + if (nsIndex == INT_MAX) + return(NULL); + + return(ctxt->nsdb->extra[nsIndex].saxData); +} + +/** + * xmlParserNsUpdateSax: + * @ctxt: parser context + * @prefix: namespace prefix + * @saxData: extra data for SAX handler + * + * Sets or updates extra data for the given prefix. This value will be + * returned by xmlParserNsLookupSax as long as the namespace with the + * given prefix is in scope. + * + * Returns the data on success, NULL if no namespace was found. + */ +int +xmlParserNsUpdateSax(xmlParserCtxtPtr ctxt, const xmlChar *prefix, + void *saxData) { + xmlHashedString hprefix; + int nsIndex; + + if (prefix == ctxt->str_xml) + return(-1); + + hprefix.name = prefix; + if (prefix != NULL) + hprefix.hashValue = xmlDictComputeHash(ctxt->dict, prefix); + else + hprefix.hashValue = 0; + nsIndex = xmlParserNsLookup(ctxt, &hprefix, NULL); + if (nsIndex == INT_MAX) + return(-1); + + ctxt->nsdb->extra[nsIndex].saxData = saxData; + return(0); +} + +/** + * xmlParserNsGrow: + * @ctxt: parser context + * + * Grows the namespace tables. + * + * Returns 0 on success, -1 if a memory allocation failed. + */ +static int +xmlParserNsGrow(xmlParserCtxtPtr ctxt) { + const xmlChar **table; + xmlParserNsExtra *extra; + int newSize; + + if (ctxt->nsMax > INT_MAX / 2) + goto error; + newSize = ctxt->nsMax ? ctxt->nsMax * 2 : 16; + + table = xmlRealloc(ctxt->nsTab, 2 * newSize * sizeof(table[0])); + if (table == NULL) + goto error; + ctxt->nsTab = table; + + extra = xmlRealloc(ctxt->nsdb->extra, newSize * sizeof(extra[0])); + if (extra == NULL) + goto error; + ctxt->nsdb->extra = extra; + + ctxt->nsMax = newSize; + return(0); + +error: + xmlErrMemory(ctxt, NULL); + return(-1); +} + +/** + * xmlParserNsPush: + * @ctxt: parser context + * @prefix: prefix with hash value + * @uri: uri with hash value + * @saxData: extra data for SAX handler + * @defAttr: whether the namespace comes from a default attribute + * + * Push a new namespace on the table. + * + * Returns 1 if the namespace was pushed, 0 if the namespace was ignored, + * -1 if a memory allocation failed. + */ +static int +xmlParserNsPush(xmlParserCtxtPtr ctxt, const xmlHashedString *prefix, + const xmlHashedString *uri, void *saxData, int defAttr) { + xmlParserNsBucket *bucket = NULL; + xmlParserNsExtra *extra; + const xmlChar **ns; + unsigned hashValue, nsIndex, oldIndex; + + if ((prefix != NULL) && (prefix->name == ctxt->str_xml)) + return(0); + + if ((ctxt->nsNr >= ctxt->nsMax) && (xmlParserNsGrow(ctxt) < 0)) { + xmlErrMemory(ctxt, NULL); + return(-1); + } + + /* + * Default namespace and 'xml' namespace + */ + if ((prefix == NULL) || (prefix->name == NULL)) { + oldIndex = ctxt->nsdb->defaultNsIndex; + + if (oldIndex != INT_MAX) { + if (defAttr != 0) + return(0); + + extra = &ctxt->nsdb->extra[oldIndex]; + + if (extra->elementId == ctxt->nsdb->elementId) { + xmlErrAttributeDup(ctxt, NULL, BAD_CAST "xmlns"); + return(0); + } + + if ((ctxt->options & XML_PARSE_NSCLEAN) && + (uri->name == ctxt->nsTab[oldIndex * 2 + 1])) + return(0); + } + + ctxt->nsdb->defaultNsIndex = ctxt->nsNr; + goto populate_entry; + } + + /* + * Hash table lookup + */ + oldIndex = xmlParserNsLookup(ctxt, prefix, &bucket); + if (oldIndex != INT_MAX) { + extra = &ctxt->nsdb->extra[oldIndex]; + + if (defAttr != 0) + return(0); + + /* + * Check for duplicate definitions on the same element. + */ + if (extra->elementId == ctxt->nsdb->elementId) { + xmlErrAttributeDup(ctxt, BAD_CAST "xmlns", prefix->name); + return(0); + } + + if ((ctxt->options & XML_PARSE_NSCLEAN) && + (uri->name == ctxt->nsTab[bucket->index * 2 + 1])) + return(0); + + bucket->index = ctxt->nsNr; + goto populate_entry; + } + + /* + * Insert new bucket + */ + + hashValue = prefix->hashValue; + + /* + * Grow hash table, 50% fill factor + */ + if (ctxt->nsdb->hashElems + 1 > ctxt->nsdb->hashSize / 2) { + xmlParserNsBucket *newHash; + unsigned newSize, i, index; + + if (ctxt->nsdb->hashSize > UINT_MAX / 2) { + xmlErrMemory(ctxt, NULL); + return(-1); + } + newSize = ctxt->nsdb->hashSize ? ctxt->nsdb->hashSize * 2 : 16; + newHash = xmlMalloc(newSize * sizeof(newHash[0])); + if (newHash == NULL) { + xmlErrMemory(ctxt, NULL); + return(-1); + } + memset(newHash, 0, newSize * sizeof(newHash[0])); + + for (i = 0; i < ctxt->nsdb->hashSize; i++) { + unsigned hv = ctxt->nsdb->hash[i].hashValue; + unsigned newIndex; + + if (hv == 0) + continue; + newIndex = hv & (newSize - 1); + + while (newHash[newIndex].hashValue != 0) { + newIndex++; + if (newIndex == newSize) + newIndex = 0; + } + + newHash[newIndex] = ctxt->nsdb->hash[i]; + } + + xmlFree(ctxt->nsdb->hash); + ctxt->nsdb->hash = newHash; + ctxt->nsdb->hashSize = newSize; + + /* + * Relookup + */ + index = hashValue & (newSize - 1); + + while (newHash[index].hashValue != 0) { + index++; + if (index == newSize) + index = 0; + } + + bucket = &newHash[index]; + } + + bucket->hashValue = hashValue; + bucket->index = ctxt->nsNr; + ctxt->nsdb->hashElems++; + oldIndex = INT_MAX; + +populate_entry: + nsIndex = ctxt->nsNr; + + ns = &ctxt->nsTab[nsIndex * 2]; + ns[0] = prefix ? prefix->name : NULL; + ns[1] = uri->name; + + extra = &ctxt->nsdb->extra[nsIndex]; + extra->saxData = saxData; + extra->prefixHashValue = prefix ? prefix->hashValue : 0; + extra->uriHashValue = uri->hashValue; + extra->elementId = ctxt->nsdb->elementId; + extra->oldIndex = oldIndex; + + ctxt->nsNr++; + + return(1); +} + +/** + * xmlParserNsPop: * @ctxt: an XML parser context * @nr: the number to pop * - * Pops the top @nr parser prefix/namespace from the ns stack + * Pops the top @nr namespaces and restores the hash table. * - * Returns the number of namespaces removed + * Returns the number of namespaces popped. */ static int -nsPop(xmlParserCtxtPtr ctxt, int nr) +xmlParserNsPop(xmlParserCtxtPtr ctxt, int nr) { int i; - if (ctxt->nsTab == NULL) return(0); - if (ctxt->nsNr < nr) { - xmlGenericError(xmlGenericErrorContext, "Pbm popping %d NS\n", nr); - nr = ctxt->nsNr; - } - if (ctxt->nsNr <= 0) - return (0); + /* assert(nr <= ctxt->nsNr); */ - for (i = 0;i < nr;i++) { - ctxt->nsNr--; - ctxt->nsTab[ctxt->nsNr] = NULL; + for (i = ctxt->nsNr - 1; i >= ctxt->nsNr - nr; i--) { + const xmlChar *prefix = ctxt->nsTab[i * 2]; + xmlParserNsExtra *extra = &ctxt->nsdb->extra[i]; + + if (prefix == NULL) { + ctxt->nsdb->defaultNsIndex = extra->oldIndex; + } else { + xmlHashedString hprefix; + xmlParserNsBucket *bucket = NULL; + + hprefix.name = prefix; + hprefix.hashValue = extra->prefixHashValue; + xmlParserNsLookup(ctxt, &hprefix, &bucket); + /* assert(bucket && bucket->hashValue); */ + bucket->index = extra->oldIndex; + } } + + ctxt->nsNr -= nr; return(nr); } -#endif static int xmlCtxtGrowAttrs(xmlParserCtxtPtr ctxt, int nr) { const xmlChar **atts; - int *attallocs; + unsigned *attallocs; int maxatts; if (nr + 5 > ctxt->maxatts) { @@ -1440,8 +1861,8 @@ atts = (const xmlChar **) xmlMalloc( maxatts * sizeof(const xmlChar *)); if (atts == NULL) goto mem_error; - attallocs = (int *) xmlRealloc((void *) ctxt->attallocs, - (maxatts / 5) * sizeof(int)); + attallocs = xmlRealloc(ctxt->attallocs, + (maxatts / 5) * sizeof(attallocs[0])); if (attallocs == NULL) { xmlFree(atts); goto mem_error; @@ -1840,13 +2261,14 @@ xmlParserGrow(ctxt); \ } while (0) -#define SHRINK if ((ctxt->progressive == 0) && \ - (ctxt->input->cur - ctxt->input->base > 2 * INPUT_CHUNK) && \ - (ctxt->input->end - ctxt->input->cur < 2 * INPUT_CHUNK)) \ +/* Don't shrink push parser buffer. */ +#define SHRINK \ + if (((ctxt->progressive == 0) || (ctxt->inputNr > 1)) && \ + (ctxt->input->cur - ctxt->input->base > 2 * INPUT_CHUNK) && \ + (ctxt->input->end - ctxt->input->cur < 2 * INPUT_CHUNK)) \ xmlParserShrink(ctxt); -#define GROW if ((ctxt->progressive == 0) && \ - (ctxt->input->end - ctxt->input->cur < INPUT_CHUNK)) \ +#define GROW if (ctxt->input->end - ctxt->input->cur < INPUT_CHUNK) \ xmlParserGrow(ctxt); #define SKIP_BLANKS xmlSkipBlankChars(ctxt) @@ -1870,8 +2292,8 @@ #define CUR_CHAR(l) xmlCurrentChar(ctxt, &l) #define CUR_SCHAR(s, l) xmlStringCurrentChar(ctxt, s, &l) -#define COPY_BUF(l,b,i,v) \ - if (l == 1) b[i++] = v; \ +#define COPY_BUF(b, i, v) \ + if (v < 0x80) b[i++] = v; \ else i += xmlCopyCharMultiByte(&b[i],v) /** @@ -2421,7 +2843,7 @@ int val = xmlParseStringCharRef(ctxt, &str); if (val == 0) goto int_error; - COPY_BUF(0,buffer,nbchars,val); + COPY_BUF(buffer, nbchars, val); if (nbchars + XML_PARSER_BUFFER_SIZE > buffer_size) { growBuffer(buffer, XML_PARSER_BUFFER_SIZE); } @@ -2434,7 +2856,7 @@ if ((ent != NULL) && (ent->etype == XML_INTERNAL_PREDEFINED_ENTITY)) { if (ent->content != NULL) { - COPY_BUF(0,buffer,nbchars,ent->content[0]); + COPY_BUF(buffer, nbchars, ent->content[0]); if (nbchars + XML_PARSER_BUFFER_SIZE > buffer_size) { growBuffer(buffer, XML_PARSER_BUFFER_SIZE); } @@ -2545,7 +2967,7 @@ rep = NULL; } } else { - COPY_BUF(l,buffer,nbchars,c); + COPY_BUF(buffer, nbchars, c); str += l; if (nbchars + XML_PARSER_BUFFER_SIZE > buffer_size) { growBuffer(buffer, XML_PARSER_BUFFER_SIZE); @@ -3144,8 +3566,9 @@ return(xmlParseNameComplex(ctxt)); } -static const xmlChar * +static xmlHashedString xmlParseNCNameComplex(xmlParserCtxtPtr ctxt) { + xmlHashedString ret; int len = 0, l; int c; int maxLength = (ctxt->options & XML_PARSE_HUGE) ? @@ -3153,6 +3576,9 @@ XML_MAX_NAME_LENGTH; size_t startPosition = 0; + ret.name = NULL; + ret.hashValue = 0; + /* * Handler for more complex cases */ @@ -3160,7 +3586,7 @@ c = CUR_CHAR(l); if ((c == ' ') || (c == '>') || (c == '/') || /* accelerators */ (!xmlIsNameStartChar(ctxt, c) || (c == ':'))) { - return(NULL); + return(ret); } while ((c != ' ') && (c != '>') && (c != '/') && /* test bigname.xml */ @@ -3171,12 +3597,13 @@ c = CUR_CHAR(l); } if (ctxt->instate == XML_PARSER_EOF) - return(NULL); + return(ret); if (len > maxLength) { xmlFatalErr(ctxt, XML_ERR_NAME_TOO_LONG, "NCName"); - return(NULL); + return(ret); } - return(xmlDictLookup(ctxt->dict, (BASE_PTR + startPosition), len)); + ret = xmlDictLookupHashed(ctxt->dict, (BASE_PTR + startPosition), len); + return(ret); } /** @@ -3194,15 +3621,17 @@ * Returns the Name parsed or NULL */ -static const xmlChar * +static xmlHashedString xmlParseNCName(xmlParserCtxtPtr ctxt) { const xmlChar *in, *e; - const xmlChar *ret; + xmlHashedString ret; size_t count = 0; size_t maxLength = (ctxt->options & XML_PARSE_HUGE) ? XML_MAX_TEXT_LENGTH : XML_MAX_NAME_LENGTH; + ret.name = NULL; + /* * Accelerator for simple ASCII names */ @@ -3224,12 +3653,12 @@ count = in - ctxt->input->cur; if (count > maxLength) { xmlFatalErr(ctxt, XML_ERR_NAME_TOO_LONG, "NCName"); - return(NULL); + return(ret); } - ret = xmlDictLookup(ctxt->dict, ctxt->input->cur, count); + ret = xmlDictLookupHashed(ctxt->dict, ctxt->input->cur, count); ctxt->input->cur = in; ctxt->input->col += count; - if (ret == NULL) { + if (ret.name == NULL) { xmlErrMemory(ctxt, NULL); } return(ret); @@ -3313,11 +3742,11 @@ return(NULL); } - COPY_BUF(l,buf,len,c); + COPY_BUF(buf, len, c); cur += l; c = CUR_SCHAR(cur, l); while (xmlIsNameChar(ctxt, c)) { - COPY_BUF(l,buf,len,c); + COPY_BUF(buf, len, c); cur += l; c = CUR_SCHAR(cur, l); if (len >= XML_MAX_NAMELEN) { /* test bigentname.xml */ @@ -3347,7 +3776,7 @@ } buffer = tmp; } - COPY_BUF(l,buffer,len,c); + COPY_BUF(buffer, len, c); cur += l; c = CUR_SCHAR(cur, l); if (len > maxLength) { @@ -3396,7 +3825,7 @@ c = CUR_CHAR(l); while (xmlIsNameChar(ctxt, c)) { - COPY_BUF(l,buf,len,c); + COPY_BUF(buf, len, c); NEXTL(l); c = CUR_CHAR(l); if (len >= XML_MAX_NAMELEN) { @@ -3426,7 +3855,7 @@ } buffer = tmp; } - COPY_BUF(l,buffer,len,c); + COPY_BUF(buffer, len, c); if (len > maxLength) { xmlFatalErr(ctxt, XML_ERR_NAME_TOO_LONG, "NmToken"); xmlFree(buffer); @@ -3528,7 +3957,7 @@ } buf = tmp; } - COPY_BUF(l,buf,len,c); + COPY_BUF(buf, len, c); NEXTL(l); GROW; @@ -3812,7 +4241,7 @@ if ((c == 0x20) || (c == 0xD) || (c == 0xA) || (c == 0x9)) { if ((len != 0) || (!normalize)) { if ((!normalize) || (!in_space)) { - COPY_BUF(l,buf,len,0x20); + COPY_BUF(buf, len, 0x20); while (len + 10 > buf_size) { growBuffer(buf, 10); } @@ -3821,7 +4250,7 @@ } } else { in_space = 0; - COPY_BUF(l,buf,len,c); + COPY_BUF(buf, len, c); if (len + 10 > buf_size) { growBuffer(buf, 10); } @@ -3968,7 +4397,7 @@ } buf = tmp; } - COPY_BUF(l,buf,len,cur); + COPY_BUF(buf, len, cur); if (len > maxLength) { xmlFatalErr(ctxt, XML_ERR_NAME_TOO_LONG, "SystemLiteral"); xmlFree(buf); @@ -4156,6 +4585,7 @@ ctxt->input->cur = in; if ((ctxt->sax != NULL) && + (ctxt->disableSAX == 0) && (ctxt->sax->ignorableWhitespace != ctxt->sax->characters)) { if (areBlanks(ctxt, tmp, nbchar, 1)) { @@ -4170,6 +4600,7 @@ *ctxt->space = -2; } } else if ((ctxt->sax != NULL) && + (ctxt->disableSAX == 0) && (ctxt->sax->characters != NULL)) { ctxt->sax->characters(ctxt->userData, tmp, nbchar); @@ -4206,6 +4637,7 @@ nbchar = in - ctxt->input->cur; if (nbchar > 0) { if ((ctxt->sax != NULL) && + (ctxt->disableSAX == 0) && (ctxt->sax->ignorableWhitespace != ctxt->sax->characters) && (IS_BLANK_CH(*ctxt->input->cur))) { @@ -4225,7 +4657,8 @@ } line = ctxt->input->line; col = ctxt->input->col; - } else if (ctxt->sax != NULL) { + } else if ((ctxt->sax != NULL) && + (ctxt->disableSAX == 0)) { if (ctxt->sax->characters != NULL) ctxt->sax->characters(ctxt->userData, ctxt->input->cur, nbchar); @@ -4284,11 +4717,11 @@ cur = CUR_CHAR(l); while ((cur != '<') && /* checked */ (cur != '&') && - (IS_CHAR(cur))) /* test also done in xmlCurrentChar() */ { + (IS_CHAR(cur))) { if ((cur == ']') && (NXT(1) == ']') && (NXT(2) == '>')) { xmlFatalErr(ctxt, XML_ERR_MISPLACED_CDATA_END, NULL); } - COPY_BUF(l,buf,nbchar,cur); + COPY_BUF(buf, nbchar, cur); /* move current position before possible calling of ctxt->sax->characters */ NEXTL(l); if (nbchar >= XML_PARSER_BIG_BUFFER_SIZE) { @@ -4531,7 +4964,7 @@ buf = new_buf; size = new_size; } - COPY_BUF(ql,buf,len,q); + COPY_BUF(buf, len, q); if (len > maxLength) { xmlFatalErrMsgStr(ctxt, XML_ERR_COMMENT_NOT_FINISHED, "Comment too big found", NULL); @@ -4654,36 +5087,33 @@ * save current set of data */ if (nbchar > 0) { - if ((ctxt->sax != NULL) && - (ctxt->sax->comment != NULL)) { - if (buf == NULL) { - if ((*in == '-') && (in[1] == '-')) - size = nbchar + 1; - else - size = XML_PARSER_BUFFER_SIZE + nbchar; - buf = (xmlChar *) xmlMallocAtomic(size); - if (buf == NULL) { - xmlErrMemory(ctxt, NULL); - ctxt->instate = state; - return; - } - len = 0; - } else if (len + nbchar + 1 >= size) { - xmlChar *new_buf; - size += len + nbchar + XML_PARSER_BUFFER_SIZE; - new_buf = (xmlChar *) xmlRealloc(buf, size); - if (new_buf == NULL) { - xmlFree (buf); - xmlErrMemory(ctxt, NULL); - ctxt->instate = state; - return; - } - buf = new_buf; - } - memcpy(&buf[len], ctxt->input->cur, nbchar); - len += nbchar; - buf[len] = 0; - } + if (buf == NULL) { + if ((*in == '-') && (in[1] == '-')) + size = nbchar + 1; + else + size = XML_PARSER_BUFFER_SIZE + nbchar; + buf = (xmlChar *) xmlMallocAtomic(size); + if (buf == NULL) { + xmlErrMemory(ctxt, NULL); + ctxt->instate = state; + return; + } + len = 0; + } else if (len + nbchar + 1 >= size) { + xmlChar *new_buf; + size += len + nbchar + XML_PARSER_BUFFER_SIZE; + new_buf = (xmlChar *) xmlRealloc(buf, size); + if (new_buf == NULL) { + xmlFree (buf); + xmlErrMemory(ctxt, NULL); + ctxt->instate = state; + return; + } + buf = new_buf; + } + memcpy(&buf[len], ctxt->input->cur, nbchar); + len += nbchar; + buf[len] = 0; } if (len > maxLength) { xmlFatalErrMsgStr(ctxt, XML_ERR_COMMENT_NOT_FINISHED, @@ -4956,7 +5386,7 @@ buf = tmp; size = new_size; } - COPY_BUF(l,buf,len,cur); + COPY_BUF(buf, len, cur); if (len > maxLength) { xmlFatalErrMsgStr(ctxt, XML_ERR_PI_NOT_FINISHED, "PI %s too big found", target); @@ -6704,6 +7134,8 @@ if (c == '>') break; } + if (ctxt->instate == XML_PARSER_EOF) + return; } ctxt->instate = oldstate; @@ -6814,7 +7246,7 @@ /* * Just encode the value in UTF-8 */ - COPY_BUF(0, out, i, value); + COPY_BUF(out, i, value); out[i] = 0; if ((ctxt->sax != NULL) && (ctxt->sax->characters != NULL) && (!ctxt->disableSAX)) @@ -6854,6 +7286,39 @@ * of validating, or substituting entities were given. Doing so is * far more secure as the parser will only process data coming from * the document entity by default. + * + * FIXME: This doesn't work correctly since entities can be + * expanded with different namespace declarations in scope. + * For example: + * + * <!DOCTYPE doc [ + * <!ENTITY ent "<ns:elem/>"> + * ]> + * <doc> + * <decl1 xmlns:ns="urn:ns1"> + * &ent; + * </decl1> + * <decl2 xmlns:ns="urn:ns2"> + * &ent; + * </decl2> + * </doc> + * + * Proposed fix: + * + * - Remove the ent->owner optimization which tries to avoid the + * initial copy of the entity. Always make entities own the + * subtree. + * - Ignore current namespace declarations when parsing the + * entity. If a prefix can't be resolved, don't report an error + * but mark it as unresolved. + * - Try to resolve these prefixes when expanding the entity. + * This will require a specialized version of xmlStaticCopyNode + * which can also make use of the namespace hash table to avoid + * quadratic behavior. + * + * Alternatively, we could simply reparse the entity on each + * expansion like we already do with custom SAX callbacks. + * External entity content should be cached in this case. */ if (((ent->flags & XML_ENT_PARSED) == 0) && ((ent->etype != XML_EXTERNAL_GENERAL_PARSED_ENTITY) || @@ -7293,6 +7758,7 @@ "Entity '%s' not defined\n", name); if ((ctxt->inSubset == 0) && (ctxt->sax != NULL) && + (ctxt->disableSAX == 0) && (ctxt->sax->reference != NULL)) { ctxt->sax->reference(ctxt->userData, name); } @@ -7731,9 +8197,12 @@ */ static int xmlLoadEntityContent(xmlParserCtxtPtr ctxt, xmlEntityPtr entity) { - xmlParserInputPtr input = NULL; + xmlParserInputPtr oldinput, input = NULL; + xmlParserInputPtr *oldinputTab; + const xmlChar *oldencoding; xmlChar *content = NULL; size_t length, i; + int oldinputNr, oldinputMax, oldprogressive; int ret = -1; int res; @@ -7758,9 +8227,58 @@ return(-1); } - while ((res = xmlParserInputBufferGrow(input->buf, 16384)) > 0) + oldinput = ctxt->input; + oldinputNr = ctxt->inputNr; + oldinputMax = ctxt->inputMax; + oldinputTab = ctxt->inputTab; + oldencoding = ctxt->encoding; + oldprogressive = ctxt->progressive; + + ctxt->input = NULL; + ctxt->inputNr = 0; + ctxt->inputMax = 1; + ctxt->encoding = NULL; + ctxt->progressive = 0; + ctxt->inputTab = xmlMalloc(sizeof(xmlParserInputPtr)); + if (ctxt->inputTab == NULL) { + xmlErrMemory(ctxt, NULL); + xmlFreeInputStream(input); + goto error; + } + + xmlBufResetInput(input->buf->buffer, input); + + inputPush(ctxt, input); + + xmlDetectEncoding(ctxt); + + /* + * Parse a possible text declaration first + */ + if ((CMP5(CUR_PTR, '<', '?', 'x', 'm', 'l')) && (IS_BLANK_CH(NXT(5)))) { + xmlParseTextDecl(ctxt); + /* + * An XML-1.0 document can't reference an entity not XML-1.0 + */ + if ((xmlStrEqual(ctxt->version, BAD_CAST "1.0")) && + (!xmlStrEqual(ctxt->input->version, BAD_CAST "1.0"))) { + xmlFatalErrMsg(ctxt, XML_ERR_VERSION_MISMATCH, + "Version mismatch between document and entity\n"); + } + } + + if (ctxt->instate == XML_PARSER_EOF) + goto error; + + length = input->cur - input->base; + xmlBufShrink(input->buf->buffer, length); + xmlSaturatedAdd(&ctxt->sizeentities, length); + + while ((res = xmlParserInputBufferGrow(input->buf, 4096)) > 0) ; + xmlBufResetInput(input->buf->buffer, input); + if (res < 0) { xmlFatalErr(ctxt, input->buf->error, NULL); goto error; @@ -7794,8 +8312,19 @@ ret = 0; error: + while (ctxt->inputNr > 0) + xmlFreeInputStream(inputPop(ctxt)); + xmlFree(ctxt->inputTab); + xmlFree((xmlChar *) ctxt->encoding); + + ctxt->input = oldinput; + ctxt->inputNr = oldinputNr; + ctxt->inputMax = oldinputMax; + ctxt->inputTab = oldinputTab; + ctxt->encoding = oldencoding; + ctxt->progressive = oldprogressive; + xmlFree(content); - xmlFreeInputStream(input); return(ret); } @@ -8398,28 +8927,61 @@ * * ************************************************************************/ -/* - * xmlGetNamespace: +/** + * xmlParseQNameHashed: * @ctxt: an XML parser context - * @prefix: the prefix to lookup + * @prefix: pointer to store the prefix part * - * Lookup the namespace name for the @prefix (which ca be NULL) - * The prefix must come from the @ctxt->dict dictionary + * parse an XML Namespace QName * - * Returns the namespace name or NULL if not bound + * [6] QName ::= (Prefix ':')? LocalPart + * [7] Prefix ::= NCName + * [8] LocalPart ::= NCName + * + * Returns the Name parsed or NULL */ -static const xmlChar * -xmlGetNamespace(xmlParserCtxtPtr ctxt, const xmlChar *prefix) { - int i; - if (prefix == ctxt->str_xml) return(ctxt->str_xml_ns); - for (i = ctxt->nsNr - 2;i >= 0;i-=2) - if (ctxt->nsTab[i] == prefix) { - if ((prefix == NULL) && (*ctxt->nsTab[i + 1] == 0)) - return(NULL); - return(ctxt->nsTab[i + 1]); - } - return(NULL); +static xmlHashedString +xmlParseQNameHashed(xmlParserCtxtPtr ctxt, xmlHashedString *prefix) { + xmlHashedString l, p; + int start; + + l.name = NULL; + p.name = NULL; + + GROW; + if (ctxt->instate == XML_PARSER_EOF) + return(l); + start = CUR_PTR - BASE_PTR; + + l = xmlParseNCName(ctxt); + if ((l.name != NULL) && (CUR == ':')) { + NEXT; + p = l; + l = xmlParseNCName(ctxt); + } + if ((l.name == NULL) || (CUR == ':')) { + xmlChar *tmp; + + l.name = NULL; + p.name = NULL; + if (ctxt->instate == XML_PARSER_EOF) + return(l); + if ((CUR != ':') && (CUR_PTR <= BASE_PTR + start)) + return(l); + tmp = xmlParseNmtoken(ctxt); + if (tmp != NULL) + xmlFree(tmp); + if (ctxt->instate == XML_PARSER_EOF) + return(l); + l = xmlDictLookupHashed(ctxt->dict, BASE_PTR + start, + CUR_PTR - (BASE_PTR + start)); + xmlNsErr(ctxt, XML_NS_ERR_QNAME, + "Failed to parse QName '%s'\n", l.name, NULL, NULL); + } + + *prefix = p; + return(l); } /** @@ -8438,76 +9000,13 @@ static const xmlChar * xmlParseQName(xmlParserCtxtPtr ctxt, const xmlChar **prefix) { - const xmlChar *l, *p; + xmlHashedString n, p; - GROW; - if (ctxt->instate == XML_PARSER_EOF) + n = xmlParseQNameHashed(ctxt, &p); + if (n.name == NULL) return(NULL); - - l = xmlParseNCName(ctxt); - if (l == NULL) { - if (CUR == ':') { - l = xmlParseName(ctxt); - if (l != NULL) { - xmlNsErr(ctxt, XML_NS_ERR_QNAME, - "Failed to parse QName '%s'\n", l, NULL, NULL); - *prefix = NULL; - return(l); - } - } - return(NULL); - } - if (CUR == ':') { - NEXT; - p = l; - l = xmlParseNCName(ctxt); - if (l == NULL) { - xmlChar *tmp; - - if (ctxt->instate == XML_PARSER_EOF) - return(NULL); - xmlNsErr(ctxt, XML_NS_ERR_QNAME, - "Failed to parse QName '%s:'\n", p, NULL, NULL); - l = xmlParseNmtoken(ctxt); - if (l == NULL) { - if (ctxt->instate == XML_PARSER_EOF) - return(NULL); - tmp = xmlBuildQName(BAD_CAST "", p, NULL, 0); - } else { - tmp = xmlBuildQName(l, p, NULL, 0); - xmlFree((char *)l); - } - p = xmlDictLookup(ctxt->dict, tmp, -1); - if (tmp != NULL) xmlFree(tmp); - *prefix = NULL; - return(p); - } - if (CUR == ':') { - xmlChar *tmp; - - xmlNsErr(ctxt, XML_NS_ERR_QNAME, - "Failed to parse QName '%s:%s:'\n", p, l, NULL); - NEXT; - tmp = (xmlChar *) xmlParseName(ctxt); - if (tmp != NULL) { - tmp = xmlBuildQName(tmp, l, NULL, 0); - l = xmlDictLookup(ctxt->dict, tmp, -1); - if (tmp != NULL) xmlFree(tmp); - *prefix = p; - return(l); - } - if (ctxt->instate == XML_PARSER_EOF) - return(NULL); - tmp = xmlBuildQName(BAD_CAST "", l, NULL, 0); - l = xmlDictLookup(ctxt->dict, tmp, -1); - if (tmp != NULL) xmlFree(tmp); - *prefix = p; - return(l); - } - *prefix = p; - } else - *prefix = NULL; - return(l); + *prefix = p.name; + return(n.name); } /** @@ -8559,6 +9058,8 @@ * all strings coms from the dictionary, equality can be done directly */ ret = xmlParseQName (ctxt, &prefix2); + if (ret == NULL) + return(NULL); if ((ret == name) && (prefix == prefix2)) return((const xmlChar*) 1); return ret; @@ -8775,24 +9276,30 @@ * Returns the attribute name, and the value in *value, . */ -static const xmlChar * +static xmlHashedString xmlParseAttribute2(xmlParserCtxtPtr ctxt, const xmlChar * pref, const xmlChar * elem, - const xmlChar ** prefix, xmlChar ** value, + xmlHashedString * hprefix, xmlChar ** value, int *len, int *alloc) { - const xmlChar *name; + xmlHashedString hname; + const xmlChar *prefix, *name; xmlChar *val, *internal_val = NULL; int normalize = 0; *value = NULL; GROW; - name = xmlParseQName(ctxt, prefix); - if (name == NULL) { + hname = xmlParseQNameHashed(ctxt, hprefix); + if (hname.name == NULL) { xmlFatalErrMsg(ctxt, XML_ERR_NAME_REQUIRED, "error parsing attribute name\n"); - return (NULL); + return(hname); } + name = hname.name; + if (hprefix->name != NULL) + prefix = hprefix->name; + else + prefix = NULL; /* * get the type if needed @@ -8801,7 +9308,8 @@ int type; type = (int) (ptrdiff_t) xmlHashQLookup2(ctxt->attsSpecial, - pref, elem, *prefix, name); + pref, elem, + prefix, name); if (type != 0) normalize = 1; } @@ -8814,8 +9322,10 @@ NEXT; SKIP_BLANKS; val = xmlParseAttValueInternal(ctxt, len, alloc, normalize); - if (val == NULL) - return (NULL); + if (val == NULL) { + hname.name = NULL; + return(hname); + } if (normalize) { /* * Sometimes a second normalisation pass for spaces is needed @@ -8838,10 +9348,10 @@ xmlFatalErrMsgStr(ctxt, XML_ERR_ATTRIBUTE_WITHOUT_VALUE, "Specification mandates value for attribute %s\n", name); - return (name); + return(hname); } - if (*prefix == ctxt->str_xml) { + if (prefix == ctxt->str_xml) { /* * Check that xml:lang conforms to the specification * No more registered as an error, just generate a warning now @@ -8877,8 +9387,149 @@ } *value = val; - return (name); + return (hname); } + +ATTRIBUTE_NO_SANITIZE_INTEGER +static unsigned +xmlCombineHash(unsigned v1, unsigned v2) { + return(HASH_ROL(v1, 15) ^ v2); +} + +/** + * xmlAttrHashInsert: + * @ctxt: parser context + * @aindex: attribute index (this is a multiple of 5) + * @sizePtr: size of the hash table (input/output value) + * @name: attribute name + * @uri: namespace uri + * @hashValue: combined hash value of name and uri + * + * Inserts a new attribute into the hash table. + * + * Returns INT_MAX if no existing attribute was found, the attribute + * index if an attribute was found, -1 if a memory allocation failed. + */ +static int +xmlAttrHashInsert(xmlParserCtxtPtr ctxt, int aindex, unsigned *sizePtr, + const xmlChar *name, const xmlChar *uri, + unsigned hashValue) { + xmlAttrHashBucket *table = ctxt->attrHash; + xmlAttrHashBucket *bucket; + unsigned hindex; + unsigned size = *sizePtr; + + if (size > 0) { + hindex = hashValue & (size - 1); + bucket = &table[hindex]; + + while (bucket->hashValue != 0) { + const xmlChar **atts = &ctxt->atts[bucket->index]; + + if (name == atts[0]) { + int nsIndex = (int) (ptrdiff_t) atts[2]; + + if ((nsIndex == NS_INDEX_EMPTY) ? (uri == NULL) : + (nsIndex == NS_INDEX_XML) ? (uri == ctxt->str_xml) : + (uri == ctxt->nsTab[nsIndex * 2 + 1])) + return(bucket->index); + } + + hindex++; + bucket++; + if (hindex >= size) { + hindex = 0; + bucket = table; + } + } + } + + /* + * Grow hash table + */ + if ((unsigned) aindex / 5 >= size / 2) { + xmlAttrHashBucket *newTable; + unsigned newSize, i, nindex; + + newSize = size ? size * 2 : 8; + + if (newSize > ctxt->attrHashMax) { + newTable = xmlRealloc(table, newSize * sizeof(newTable[0])); + if (newTable == NULL) { + xmlErrMemory(ctxt, NULL); + return(-1); + } + + table = newTable; + ctxt->attrHash = newTable; + ctxt->attrHashMax = newSize; + } + + memset(&table[size], 0, (newSize - size) * sizeof(table[0])); + + if (size > 0) { + /* + * We must search for the start of a probe sequence to make + * in-place operation work. + */ + hindex = 0; + bucket = table; + while (bucket->hashValue != 0) { + hindex++; + bucket++; + } + + for (i = 0; i < size; i++) { + if (bucket->hashValue != 0) { + nindex = bucket->hashValue & (newSize - 1); + + while (nindex != hindex) { + if (table[nindex].hashValue == 0) { + table[nindex] = *bucket; + bucket->hashValue = 0; + break; + } + + nindex++; + if (nindex >= newSize) + nindex = 0; + } + } + + hindex++; + bucket++; + if (hindex >= size) { + hindex = 0; + bucket = table; + } + } + } + + size = newSize; + *sizePtr = newSize; + + /* + * Relookup + */ + hindex = hashValue & (size - 1); + bucket = &table[hindex]; + + while (bucket->hashValue != 0) { + hindex++; + bucket++; + if (hindex >= size) { + hindex = 0; + bucket = table; + } + } + } + + bucket->hashValue = hashValue; + bucket->index = aindex; + + return(INT_MAX); +} + /** * xmlParseStartTag2: * @ctxt: an XML parser context @@ -8910,40 +9561,47 @@ static const xmlChar * xmlParseStartTag2(xmlParserCtxtPtr ctxt, const xmlChar **pref, - const xmlChar **URI, int *tlen) { + const xmlChar **URI, int *nbNsPtr) { + xmlHashedString hlocalname; + xmlHashedString hprefix; + xmlHashedString hattname; + xmlHashedString haprefix; const xmlChar *localname; const xmlChar *prefix; const xmlChar *attname; const xmlChar *aprefix; - const xmlChar *nsname; - xmlChar *attvalue; + const xmlChar *uri; + xmlChar *attvalue = NULL; const xmlChar **atts = ctxt->atts; + unsigned attrHashSize = 0; int maxatts = ctxt->maxatts; int nratts, nbatts, nbdef, inputid; - int i, j, nbNs, attval; - size_t cur; - int nsNr = ctxt->nsNr; + int i, j, nbNs, attval, nsIndex; + int alloc = 0; if (RAW != '<') return(NULL); NEXT1; - cur = ctxt->input->cur - ctxt->input->base; inputid = ctxt->input->id; nbatts = 0; nratts = 0; nbdef = 0; nbNs = 0; attval = 0; - /* Forget any namespaces added during an earlier parse of this element. */ - ctxt->nsNr = nsNr; - localname = xmlParseQName(ctxt, &prefix); - if (localname == NULL) { + if (xmlParserNsStartElement(ctxt->nsdb) < 0) { + xmlErrMemory(ctxt, NULL); + return(NULL); + } + + hlocalname = xmlParseQNameHashed(ctxt, &hprefix); + if (hlocalname.name == NULL) { xmlFatalErrMsg(ctxt, XML_ERR_NAME_REQUIRED, "StartTag: invalid element name\n"); return(NULL); } - *tlen = ctxt->input->cur - ctxt->input->base - cur; + localname = hlocalname.name; + prefix = hprefix.name; /* * Now parse the attributes, it ends up with the ending @@ -8953,48 +9611,74 @@ SKIP_BLANKS; GROW; + /* + * The ctxt->atts array will be ultimately passed to the SAX callback + * containing five xmlChar pointers for each attribute: + * + * [0] attribute name + * [1] attribute prefix + * [2] namespace URI + * [3] attribute value + * [4] end of attribute value + * + * To save memory, we reuse this array temporarily and store integers + * in these pointer variables. + * + * [0] attribute name + * [1] attribute prefix + * [2] hash value of attribute prefix, and later namespace index + * [3] for non-allocated values: ptrdiff_t offset into input buffer + * [4] for non-allocated values: ptrdiff_t offset into input buffer + * + * The ctxt->attallocs array contains an additional unsigned int for + * each attribute, containing the hash value of the attribute name + * and the alloc flag in bit 31. + */ + while (((RAW != '>') && ((RAW != '/') || (NXT(1) != '>')) && (IS_BYTE_CHAR(RAW))) && (ctxt->instate != XML_PARSER_EOF)) { - int len = -1, alloc = 0; + int len = -1; - attname = xmlParseAttribute2(ctxt, prefix, localname, - &aprefix, &attvalue, &len, &alloc); - if (attname == NULL) { + hattname = xmlParseAttribute2(ctxt, prefix, localname, + &haprefix, &attvalue, &len, + &alloc); + if (hattname.name == NULL) { xmlFatalErr(ctxt, XML_ERR_INTERNAL_ERROR, "xmlParseStartTag: problem parsing attributes\n"); break; } if (attvalue == NULL) goto next_attr; + attname = hattname.name; + aprefix = haprefix.name; if (len < 0) len = xmlStrlen(attvalue); if ((attname == ctxt->str_xmlns) && (aprefix == NULL)) { - const xmlChar *URL = xmlDictLookup(ctxt->dict, attvalue, len); - xmlURIPtr uri; + xmlHashedString huri; + xmlURIPtr parsedUri; - if (URL == NULL) { - xmlErrMemory(ctxt, "dictionary allocation failure"); - if ((attvalue != NULL) && (alloc != 0)) - xmlFree(attvalue); - localname = NULL; - goto done; + huri = xmlDictLookupHashed(ctxt->dict, attvalue, len); + uri = huri.name; + if (uri == NULL) { + xmlErrMemory(ctxt, NULL); + goto next_attr; } - if (*URL != 0) { - uri = xmlParseURI((const char *) URL); - if (uri == NULL) { + if (*uri != 0) { + parsedUri = xmlParseURI((const char *) uri); + if (parsedUri == NULL) { xmlNsErr(ctxt, XML_WAR_NS_URI, "xmlns: '%s' is not a valid URI\n", - URL, NULL, NULL); + uri, NULL, NULL); } else { - if (uri->scheme == NULL) { + if (parsedUri->scheme == NULL) { xmlNsWarn(ctxt, XML_WAR_NS_URI_RELATIVE, "xmlns: URI %s is not absolute\n", - URL, NULL, NULL); + uri, NULL, NULL); } - xmlFreeURI(uri); + xmlFreeURI(parsedUri); } - if (URL == ctxt->str_xml_ns) { + if (uri == ctxt->str_xml_ns) { if (attname != ctxt->str_xml) { xmlNsErr(ctxt, XML_NS_ERR_XML_NAMESPACE, "xml namespace URI cannot be the default namespace\n", @@ -9003,7 +9687,7 @@ goto next_attr; } if ((len == 29) && - (xmlStrEqual(URL, + (xmlStrEqual(uri, BAD_CAST "http://www.w3.org/2000/xmlns/"))) { xmlNsErr(ctxt, XML_NS_ERR_XML_NAMESPACE, "reuse of the xmlns namespace name is forbidden\n", @@ -9011,23 +9695,22 @@ goto next_attr; } } - /* - * check that it's not a defined namespace - */ - for (j = 1;j <= nbNs;j++) - if (ctxt->nsTab[ctxt->nsNr - 2 * j] == NULL) - break; - if (j <= nbNs) - xmlErrAttributeDup(ctxt, NULL, attname); - else - if (nsPush(ctxt, NULL, URL) > 0) nbNs++; + if (xmlParserNsPush(ctxt, NULL, &huri, NULL, 0) > 0) + nbNs++; } else if (aprefix == ctxt->str_xmlns) { - const xmlChar *URL = xmlDictLookup(ctxt->dict, attvalue, len); - xmlURIPtr uri; + xmlHashedString huri; + xmlURIPtr parsedUri; + + huri = xmlDictLookupHashed(ctxt->dict, attvalue, len); + uri = huri.name; + if (uri == NULL) { + xmlErrMemory(ctxt, NULL); + goto next_attr; + } if (attname == ctxt->str_xml) { - if (URL != ctxt->str_xml_ns) { + if (uri != ctxt->str_xml_ns) { xmlNsErr(ctxt, XML_NS_ERR_XML_NAMESPACE, "xml namespace prefix mapped to wrong URI\n", NULL, NULL, NULL); @@ -9037,7 +9720,7 @@ */ goto next_attr; } - if (URL == ctxt->str_xml_ns) { + if (uri == ctxt->str_xml_ns) { if (attname != ctxt->str_xml) { xmlNsErr(ctxt, XML_NS_ERR_XML_NAMESPACE, "xml namespace URI mapped to wrong prefix\n", @@ -9052,48 +9735,40 @@ goto next_attr; } if ((len == 29) && - (xmlStrEqual(URL, + (xmlStrEqual(uri, BAD_CAST "http://www.w3.org/2000/xmlns/"))) { xmlNsErr(ctxt, XML_NS_ERR_XML_NAMESPACE, "reuse of the xmlns namespace name is forbidden\n", NULL, NULL, NULL); goto next_attr; } - if ((URL == NULL) || (URL[0] == 0)) { + if ((uri == NULL) || (uri[0] == 0)) { xmlNsErr(ctxt, XML_NS_ERR_XML_NAMESPACE, "xmlns:%s: Empty XML namespace is not allowed\n", attname, NULL, NULL); goto next_attr; } else { - uri = xmlParseURI((const char *) URL); - if (uri == NULL) { + parsedUri = xmlParseURI((const char *) uri); + if (parsedUri == NULL) { xmlNsErr(ctxt, XML_WAR_NS_URI, "xmlns:%s: '%s' is not a valid URI\n", - attname, URL, NULL); + attname, uri, NULL); } else { - if ((ctxt->pedantic) && (uri->scheme == NULL)) { + if ((ctxt->pedantic) && (parsedUri->scheme == NULL)) { xmlNsWarn(ctxt, XML_WAR_NS_URI_RELATIVE, "xmlns:%s: URI %s is not absolute\n", - attname, URL, NULL); + attname, uri, NULL); } - xmlFreeURI(uri); + xmlFreeURI(parsedUri); } } - /* - * check that it's not a defined namespace - */ - for (j = 1;j <= nbNs;j++) - if (ctxt->nsTab[ctxt->nsNr - 2 * j] == attname) - break; - if (j <= nbNs) - xmlErrAttributeDup(ctxt, aprefix, attname); - else - if (nsPush(ctxt, attname, URL) > 0) nbNs++; - + if (xmlParserNsPush(ctxt, &hattname, &huri, NULL, 0) > 0) + nbNs++; } else { /* - * Add the pair to atts + * Populate attributes array, see above for repurposing + * of xmlChar pointers. */ if ((atts == NULL) || (nbatts + 5 > maxatts)) { if (xmlCtxtGrowAttrs(ctxt, nbatts + 5) < 0) { @@ -9102,10 +9777,11 @@ maxatts = ctxt->maxatts; atts = ctxt->atts; } - ctxt->attallocs[nratts++] = alloc; + ctxt->attallocs[nratts++] = (hattname.hashValue & 0x7FFFFFFF) | + ((unsigned) alloc << 31); atts[nbatts++] = attname; atts[nbatts++] = aprefix; - atts[nbatts++] = NULL; + atts[nbatts++] = (const xmlChar *) (size_t) haprefix.hashValue; if (alloc) { atts[nbatts++] = attvalue; attvalue += len; @@ -9153,169 +9829,255 @@ goto done; } - /* Reconstruct attribute value pointers. */ - for (i = 0, j = 0; j < nratts; i += 5, j++) { - if (ctxt->attallocs[j] == 0) { - atts[i+3] = BASE_PTR + (ptrdiff_t) atts[i+3]; /* value */ - atts[i+4] = BASE_PTR + (ptrdiff_t) atts[i+4]; /* valuend */ - } - } - /* - * The attributes defaulting + * Namespaces from default attributes */ if (ctxt->attsDefault != NULL) { xmlDefAttrsPtr defaults; defaults = xmlHashLookup2(ctxt->attsDefault, localname, prefix); if (defaults != NULL) { - for (i = 0;i < defaults->nbAttrs;i++) { - attname = defaults->values[5 * i]; - aprefix = defaults->values[5 * i + 1]; + for (i = 0; i < defaults->nbAttrs; i++) { + xmlDefAttr *attr = &defaults->attrs[i]; - /* - * special work for namespaces defaulted defs - */ + attname = attr->name.name; + aprefix = attr->prefix.name; + if ((attname == ctxt->str_xmlns) && (aprefix == NULL)) { - /* - * check that it's not a defined namespace - */ - for (j = 1;j <= nbNs;j++) - if (ctxt->nsTab[ctxt->nsNr - 2 * j] == NULL) - break; - if (j <= nbNs) continue; + xmlParserEntityCheck(ctxt, attr->expandedSize); - nsname = xmlGetNamespace(ctxt, NULL); - if (nsname != defaults->values[5 * i + 2]) { - if (nsPush(ctxt, NULL, - defaults->values[5 * i + 2]) > 0) - nbNs++; - } + if (xmlParserNsPush(ctxt, NULL, &attr->value, NULL, 1) > 0) + nbNs++; } else if (aprefix == ctxt->str_xmlns) { - /* - * check that it's not a defined namespace - */ - for (j = 1;j <= nbNs;j++) - if (ctxt->nsTab[ctxt->nsNr - 2 * j] == attname) - break; - if (j <= nbNs) continue; + xmlParserEntityCheck(ctxt, attr->expandedSize); - nsname = xmlGetNamespace(ctxt, attname); - if (nsname != defaults->values[5 * i + 2]) { - if (nsPush(ctxt, attname, - defaults->values[5 * i + 2]) > 0) - nbNs++; - } - } else { - /* - * check that it's not a defined attribute - */ - for (j = 0;j < nbatts;j+=5) { - if ((attname == atts[j]) && (aprefix == atts[j+1])) - break; - } - if (j < nbatts) continue; - - if ((atts == NULL) || (nbatts + 5 > maxatts)) { - if (xmlCtxtGrowAttrs(ctxt, nbatts + 5) < 0) { - localname = NULL; - goto done; - } - maxatts = ctxt->maxatts; - atts = ctxt->atts; - } - atts[nbatts++] = attname; - atts[nbatts++] = aprefix; - if (aprefix == NULL) - atts[nbatts++] = NULL; - else - atts[nbatts++] = xmlGetNamespace(ctxt, aprefix); - atts[nbatts++] = defaults->values[5 * i + 2]; - atts[nbatts++] = defaults->values[5 * i + 3]; - if ((ctxt->standalone == 1) && - (defaults->values[5 * i + 4] != NULL)) { - xmlValidityError(ctxt, XML_DTD_STANDALONE_DEFAULTED, - "standalone: attribute %s on %s defaulted from external subset\n", - attname, localname); - } - nbdef++; + if (xmlParserNsPush(ctxt, &attr->name, &attr->value, + NULL, 1) > 0) + nbNs++; } } } } /* - * The attributes checkings + * Resolve attribute namespaces */ - for (i = 0; i < nbatts;i += 5) { + for (i = 0; i < nbatts; i += 5) { + attname = atts[i]; + aprefix = atts[i+1]; + /* * The default namespace does not apply to attribute names. */ - if (atts[i + 1] != NULL) { - nsname = xmlGetNamespace(ctxt, atts[i + 1]); - if (nsname == NULL) { - xmlNsErr(ctxt, XML_NS_ERR_UNDEFINED_NAMESPACE, + if (aprefix == NULL) { + nsIndex = NS_INDEX_EMPTY; + } else if (aprefix == ctxt->str_xml) { + nsIndex = NS_INDEX_XML; + } else { + haprefix.name = aprefix; + haprefix.hashValue = (size_t) atts[i+2]; + nsIndex = xmlParserNsLookup(ctxt, &haprefix, NULL); + if (nsIndex == INT_MAX) { + xmlNsErr(ctxt, XML_NS_ERR_UNDEFINED_NAMESPACE, "Namespace prefix %s for %s on %s is not defined\n", - atts[i + 1], atts[i], localname); - } - atts[i + 2] = nsname; - } else - nsname = NULL; + aprefix, attname, localname); + nsIndex = NS_INDEX_EMPTY; + } + } + + atts[i+2] = (const xmlChar *) (ptrdiff_t) nsIndex; + } + + /* + * Verify that attribute names are unique. + */ + for (i = 0, j = 0; j < nratts; i += 5, j++) { + const xmlChar *nsuri; + unsigned hashValue, nameHashValue, uriHashValue; + int res; + + attname = atts[i]; + aprefix = atts[i+1]; + nsIndex = (ptrdiff_t) atts[i+2]; + /* Hash values always have bit 31 set, see dict.c */ + nameHashValue = ctxt->attallocs[j] | 0x80000000; + + if (nsIndex == NS_INDEX_EMPTY) { + nsuri = NULL; + uriHashValue = URI_HASH_EMPTY; + } else if (nsIndex == NS_INDEX_XML) { + nsuri = ctxt->str_xml_ns; + uriHashValue = URI_HASH_XML; + } else { + nsuri = ctxt->nsTab[nsIndex * 2 + 1]; + uriHashValue = ctxt->nsdb->extra[nsIndex].uriHashValue; + } + + hashValue = xmlCombineHash(nameHashValue, uriHashValue); + res = xmlAttrHashInsert(ctxt, i, &attrHashSize, attname, nsuri, + hashValue); + if (res < 0) + continue; + /* * [ WFC: Unique Att Spec ] * No attribute name may appear more than once in the same * start-tag or empty-element tag. * As extended by the Namespace in XML REC. */ - for (j = 0; j < i;j += 5) { - if (atts[i] == atts[j]) { - if (atts[i+1] == atts[j+1]) { - xmlErrAttributeDup(ctxt, atts[i+1], atts[i]); - break; - } - if ((nsname != NULL) && (atts[j + 2] == nsname)) { - xmlNsErr(ctxt, XML_NS_ERR_ATTRIBUTE_REDEFINED, - "Namespaced Attribute %s in '%s' redefined\n", - atts[i], nsname, NULL); - break; - } + if (res < INT_MAX) { + if (aprefix == atts[res+1]) { + xmlErrAttributeDup(ctxt, aprefix, attname); + } else { + xmlNsErr(ctxt, XML_NS_ERR_ATTRIBUTE_REDEFINED, + "Namespaced Attribute %s in '%s' redefined\n", + attname, nsuri, NULL); + } + } + } + + /* + * Default attributes + */ + if (ctxt->attsDefault != NULL) { + xmlDefAttrsPtr defaults; + + defaults = xmlHashLookup2(ctxt->attsDefault, localname, prefix); + if (defaults != NULL) { + for (i = 0; i < defaults->nbAttrs; i++) { + xmlDefAttr *attr = &defaults->attrs[i]; + const xmlChar *nsuri; + unsigned hashValue, uriHashValue; + int res; + + attname = attr->name.name; + aprefix = attr->prefix.name; + + if ((attname == ctxt->str_xmlns) && (aprefix == NULL)) + continue; + if (aprefix == ctxt->str_xmlns) + continue; + + if (aprefix == NULL) { + nsIndex = NS_INDEX_EMPTY; + nsuri = NULL; + uriHashValue = URI_HASH_EMPTY; + } if (aprefix == ctxt->str_xml) { + nsIndex = NS_INDEX_XML; + nsuri = ctxt->str_xml_ns; + uriHashValue = URI_HASH_XML; + } else if (aprefix != NULL) { + nsIndex = xmlParserNsLookup(ctxt, &attr->prefix, NULL); + if (nsIndex == INT_MAX) { + xmlNsErr(ctxt, XML_NS_ERR_UNDEFINED_NAMESPACE, + "Namespace prefix %s for %s on %s is not " + "defined\n", + aprefix, attname, localname); + nsIndex = NS_INDEX_EMPTY; + nsuri = NULL; + uriHashValue = URI_HASH_EMPTY; + } else { + nsuri = ctxt->nsTab[nsIndex * 2 + 1]; + uriHashValue = ctxt->nsdb->extra[nsIndex].uriHashValue; + } + } + + /* + * Check whether the attribute exists + */ + hashValue = xmlCombineHash(attr->name.hashValue, uriHashValue); + res = xmlAttrHashInsert(ctxt, nbatts, &attrHashSize, attname, + nsuri, hashValue); + if (res < 0) + continue; + if (res < INT_MAX) { + if (aprefix == atts[res+1]) + continue; + xmlNsErr(ctxt, XML_NS_ERR_ATTRIBUTE_REDEFINED, + "Namespaced Attribute %s in '%s' redefined\n", + attname, nsuri, NULL); + } + + xmlParserEntityCheck(ctxt, attr->expandedSize); + + if ((atts == NULL) || (nbatts + 5 > maxatts)) { + if (xmlCtxtGrowAttrs(ctxt, nbatts + 5) < 0) { + localname = NULL; + goto done; + } + maxatts = ctxt->maxatts; + atts = ctxt->atts; + } + + atts[nbatts++] = attname; + atts[nbatts++] = aprefix; + atts[nbatts++] = (const xmlChar *) (ptrdiff_t) nsIndex; + atts[nbatts++] = attr->value.name; + atts[nbatts++] = attr->valueEnd; + if ((ctxt->standalone == 1) && (attr->external != 0)) { + xmlValidityError(ctxt, XML_DTD_STANDALONE_DEFAULTED, + "standalone: attribute %s on %s defaulted " + "from external subset\n", + attname, localname); + } + nbdef++; } } } - nsname = xmlGetNamespace(ctxt, prefix); - if ((prefix != NULL) && (nsname == NULL)) { + /* + * Reconstruct attribute pointers + */ + for (i = 0, j = 0; i < nbatts; i += 5, j++) { + /* namespace URI */ + nsIndex = (ptrdiff_t) atts[i+2]; + if (nsIndex == INT_MAX) + atts[i+2] = NULL; + else if (nsIndex == INT_MAX - 1) + atts[i+2] = ctxt->str_xml_ns; + else + atts[i+2] = ctxt->nsTab[nsIndex * 2 + 1]; + + if ((j < nratts) && (ctxt->attallocs[j] & 0x80000000) == 0) { + atts[i+3] = BASE_PTR + (ptrdiff_t) atts[i+3]; /* value */ + atts[i+4] = BASE_PTR + (ptrdiff_t) atts[i+4]; /* valuend */ + } + } + + uri = xmlParserNsLookupUri(ctxt, &hprefix); + if ((prefix != NULL) && (uri == NULL)) { xmlNsErr(ctxt, XML_NS_ERR_UNDEFINED_NAMESPACE, "Namespace prefix %s on %s is not defined\n", prefix, localname, NULL); } *pref = prefix; - *URI = nsname; + *URI = uri; /* - * SAX: Start of Element ! + * SAX callback */ if ((ctxt->sax != NULL) && (ctxt->sax->startElementNs != NULL) && (!ctxt->disableSAX)) { if (nbNs > 0) - ctxt->sax->startElementNs(ctxt->userData, localname, prefix, - nsname, nbNs, &ctxt->nsTab[ctxt->nsNr - 2 * nbNs], + ctxt->sax->startElementNs(ctxt->userData, localname, prefix, uri, + nbNs, ctxt->nsTab + 2 * (ctxt->nsNr - nbNs), nbatts / 5, nbdef, atts); else - ctxt->sax->startElementNs(ctxt->userData, localname, prefix, - nsname, 0, NULL, nbatts / 5, nbdef, atts); + ctxt->sax->startElementNs(ctxt->userData, localname, prefix, uri, + 0, NULL, nbatts / 5, nbdef, atts); } done: /* - * Free up attribute allocated strings if needed + * Free allocated attribute values */ if (attval != 0) { - for (i = 3,j = 0; j < nratts;i += 5,j++) - if ((ctxt->attallocs[j] != 0) && (atts[i] != NULL)) - xmlFree((xmlChar *) atts[i]); + for (i = 0, j = 0; j < nratts; i += 5, j++) + if (ctxt->attallocs[j] & 0x80000000) + xmlFree((xmlChar *) atts[i+3]); } + *nbNsPtr = nbNs; return(localname); } @@ -9385,7 +10147,7 @@ spacePop(ctxt); if (tag->nsNr != 0) - nsPop(ctxt, tag->nsNr); + xmlParserNsPop(ctxt, tag->nsNr); } /** @@ -9456,7 +10218,7 @@ buf = tmp; size *= 2; } - COPY_BUF(rl,buf,len,r); + COPY_BUF(buf, len, r); if (len > maxLength) { xmlFatalErrMsg(ctxt, XML_ERR_CDATA_NOT_FINISHED, "CData section too big found\n"); @@ -9652,9 +10414,9 @@ const xmlChar *prefix = NULL; const xmlChar *URI = NULL; xmlParserNodeInfo node_info; - int line, tlen = 0; + int line; xmlNodePtr cur; - int nsNr = ctxt->nsNr; + int nbNs = 0; if (((unsigned int) ctxt->nameNr > xmlParserMaxDepth) && ((ctxt->options & XML_PARSE_HUGE) == 0)) { @@ -9683,7 +10445,7 @@ #ifdef LIBXML_SAX1_ENABLED if (ctxt->sax2) #endif /* LIBXML_SAX1_ENABLED */ - name = xmlParseStartTag2(ctxt, &prefix, &URI, &tlen); + name = xmlParseStartTag2(ctxt, &prefix, &URI, &nbNs); #ifdef LIBXML_SAX1_ENABLED else name = xmlParseStartTag(ctxt); @@ -9694,7 +10456,7 @@ spacePop(ctxt); return(-1); } - nameNsPush(ctxt, name, prefix, URI, line, ctxt->nsNr - nsNr); + nameNsPush(ctxt, name, prefix, URI, line, nbNs); cur = ctxt->node; #ifdef LIBXML_VALID_ENABLED @@ -9726,8 +10488,8 @@ } namePop(ctxt); spacePop(ctxt); - if (nsNr != ctxt->nsNr) - nsPop(ctxt, ctxt->nsNr - nsNr); + if (nbNs > 0) + xmlParserNsPop(ctxt, nbNs); if (cur != NULL && ctxt->record_info) { node_info.node = cur; node_info.end_pos = ctxt->input->consumed + @@ -9756,8 +10518,8 @@ nodePop(ctxt); namePop(ctxt); spacePop(ctxt); - if (nsNr != ctxt->nsNr) - nsPop(ctxt, ctxt->nsNr - nsNr); + if (nbNs > 0) + xmlParserNsPop(ctxt, nbNs); return(-1); } @@ -10883,7 +11645,6 @@ static int xmlParseTryOrFinish(xmlParserCtxtPtr ctxt, int terminate) { int ret = 0; - int tlen; size_t avail; xmlChar cur, next; @@ -10978,7 +11739,7 @@ const xmlChar *prefix = NULL; const xmlChar *URI = NULL; int line = ctxt->input->line; - int nsNr = ctxt->nsNr; + int nbNs = 0; if ((!terminate) && (avail < 2)) goto done; @@ -11002,7 +11763,7 @@ #ifdef LIBXML_SAX1_ENABLED if (ctxt->sax2) #endif /* LIBXML_SAX1_ENABLED */ - name = xmlParseStartTag2(ctxt, &prefix, &URI, &tlen); + name = xmlParseStartTag2(ctxt, &prefix, &URI, &nbNs); #ifdef LIBXML_SAX1_ENABLED else name = xmlParseStartTag(ctxt); @@ -11039,8 +11800,8 @@ (!ctxt->disableSAX)) ctxt->sax->endElementNs(ctxt->userData, name, prefix, URI); - if (ctxt->nsNr - nsNr > 0) - nsPop(ctxt, ctxt->nsNr - nsNr); + if (nbNs > 0) + xmlParserNsPop(ctxt, nbNs); #ifdef LIBXML_SAX1_ENABLED } else { if ((ctxt->sax != NULL) && @@ -11049,30 +11810,26 @@ ctxt->sax->endElement(ctxt->userData, name); #endif /* LIBXML_SAX1_ENABLED */ } - if (ctxt->instate == XML_PARSER_EOF) - goto done; spacePop(ctxt); - if (ctxt->nameNr == 0) { - ctxt->instate = XML_PARSER_EPILOG; - } else { - ctxt->instate = XML_PARSER_CONTENT; - } - break; - } - if (RAW == '>') { + } else if (RAW == '>') { NEXT; + nameNsPush(ctxt, name, prefix, URI, line, nbNs); } else { xmlFatalErrMsgStr(ctxt, XML_ERR_GT_REQUIRED, "Couldn't find end of Start Tag %s\n", name); nodePop(ctxt); spacePop(ctxt); + if (nbNs > 0) + xmlParserNsPop(ctxt, nbNs); } - nameNsPush(ctxt, name, prefix, URI, line, ctxt->nsNr - nsNr); if (ctxt->instate == XML_PARSER_EOF) goto done; - ctxt->instate = XML_PARSER_CONTENT; + if (ctxt->nameNr == 0) + ctxt->instate = XML_PARSER_EPILOG; + else + ctxt->instate = XML_PARSER_CONTENT; break; } case XML_PARSER_CONTENT: { @@ -12237,9 +12994,8 @@ xmlNodePtr content = NULL; xmlNodePtr last = NULL; xmlParserErrors ret = XML_ERR_OK; -#ifdef SAX2 - int i; -#endif + xmlHashedString hprefix, huri; + unsigned i; if (((oldctxt->depth > 40) && ((oldctxt->options & XML_PARSE_HUGE) == 0)) || (oldctxt->depth > 100)) { @@ -12269,12 +13025,44 @@ ctxt->str_xmlns = xmlDictLookup(ctxt->dict, BAD_CAST "xmlns", 5); ctxt->str_xml_ns = xmlDictLookup(ctxt->dict, XML_XML_NAMESPACE, 36); -#ifdef SAX2 - /* propagate namespaces down the entity */ - for (i = 0;i < oldctxt->nsNr;i += 2) { - nsPush(ctxt, oldctxt->nsTab[i], oldctxt->nsTab[i+1]); + /* + * Propagate namespaces down the entity + * + * Making entities and namespaces work correctly requires additional + * changes, see xmlParseReference. + */ + + /* Default namespace */ + hprefix.name = NULL; + hprefix.hashValue = 0; + huri.name = xmlParserNsLookupUri(oldctxt, &hprefix); + huri.hashValue = 0; + if (huri.name != NULL) + xmlParserNsPush(ctxt, NULL, &huri, NULL, 0); + + for (i = 0; i < oldctxt->nsdb->hashSize; i++) { + xmlParserNsBucket *bucket = &oldctxt->nsdb->hash[i]; + const xmlChar **ns; + xmlParserNsExtra *extra; + unsigned nsIndex; + + if ((bucket->hashValue != 0) && + (bucket->index != INT_MAX)) { + nsIndex = bucket->index; + ns = &oldctxt->nsTab[nsIndex * 2]; + extra = &oldctxt->nsdb->extra[nsIndex]; + + hprefix.name = ns[0]; + hprefix.hashValue = bucket->hashValue; + huri.name = ns[1]; + huri.hashValue = extra->uriHashValue; + /* + * Don't copy SAX data to avoid a use-after-free with XML reader. + * This matches the pre-2.12 behavior. + */ + xmlParserNsPush(ctxt, &hprefix, &huri, NULL, 0); + } } -#endif oldsax = ctxt->sax; ctxt->sax = oldctxt->sax; @@ -12286,10 +13074,8 @@ if (oldctxt->myDoc == NULL) { newDoc = xmlNewDoc(BAD_CAST "1.0"); if (newDoc == NULL) { - ctxt->sax = oldsax; - ctxt->dict = NULL; - xmlFreeParserCtxt(ctxt); - return(XML_ERR_INTERNAL_ERROR); + ret = XML_ERR_INTERNAL_ERROR; + goto error; } newDoc->properties = XML_DOC_INTERNAL; newDoc->dict = ctxt->dict; @@ -12302,13 +13088,8 @@ } newRoot = xmlNewDocNode(ctxt->myDoc, NULL, BAD_CAST "pseudoroot", NULL); if (newRoot == NULL) { - ctxt->sax = oldsax; - ctxt->dict = NULL; - xmlFreeParserCtxt(ctxt); - if (newDoc != NULL) { - xmlFreeDoc(newDoc); - } - return(XML_ERR_INTERNAL_ERROR); + ret = XML_ERR_INTERNAL_ERROR; + goto error; } ctxt->myDoc->children = NULL; ctxt->myDoc->last = NULL; @@ -12391,6 +13172,8 @@ oldctxt->nbErrors = ctxt->nbErrors; oldctxt->nbWarnings = ctxt->nbWarnings; + +error: ctxt->sax = oldsax; ctxt->dict = NULL; ctxt->attsDefault = NULL; @@ -12425,7 +13208,6 @@ xmlParserErrors xmlParseInNodeContext(xmlNodePtr node, const char *data, int datalen, int options, xmlNodePtr *lst) { -#ifdef SAX2 xmlParserCtxtPtr ctxt; xmlDocPtr doc = NULL; xmlNodePtr fake, cur; @@ -12533,21 +13315,13 @@ cur = node; while ((cur != NULL) && (cur->type == XML_ELEMENT_NODE)) { xmlNsPtr ns = cur->nsDef; - const xmlChar *iprefix, *ihref; + xmlHashedString hprefix, huri; while (ns != NULL) { - if (ctxt->dict) { - iprefix = xmlDictLookup(ctxt->dict, ns->prefix, -1); - ihref = xmlDictLookup(ctxt->dict, ns->href, -1); - } else { - iprefix = ns->prefix; - ihref = ns->href; - } - - if (xmlGetNamespace(ctxt, iprefix) == NULL) { - nsPush(ctxt, iprefix, ihref); - nsnr++; - } + hprefix = xmlDictLookupHashed(ctxt->dict, ns->prefix, -1); + huri = xmlDictLookupHashed(ctxt->dict, ns->href, -1); + if (xmlParserNsPush(ctxt, &hprefix, &huri, ns, 1) > 0) + nsnr++; ns = ns->next; } cur = cur->parent; @@ -12568,7 +13342,7 @@ #endif xmlParseContent(ctxt); - nsPop(ctxt, nsnr); + xmlParserNsPop(ctxt, nsnr); if ((RAW == '<') && (NXT(1) == '/')) { xmlFatalErr(ctxt, XML_ERR_NOT_WELL_BALANCED, NULL); } else if (RAW != 0) { @@ -12622,9 +13396,6 @@ xmlFreeParserCtxt(ctxt); return(ret); -#else /* !SAX2 */ - return(XML_ERR_INTERNAL_ERROR); -#endif } #ifdef LIBXML_SAX1_ENABLED @@ -13680,6 +14451,7 @@ ctxt->name = NULL; ctxt->nsNr = 0; + xmlParserNsReset(ctxt->nsdb); DICT_FREE(ctxt->version); ctxt->version = NULL;
diff --git a/src/parserInternals.c b/src/parserInternals.c index 6c3fb78..77b5a00 100644 --- a/src/parserInternals.c +++ b/src/parserInternals.c
@@ -38,7 +38,6 @@ #define CUR(ctxt) ctxt->input->cur #define END(ctxt) ctxt->input->end -#define VALID_CTXT(ctxt) (CUR(ctxt) <= END(ctxt)) #include "private/buf.h" #include "private/enc.h" @@ -519,7 +518,7 @@ if (buf == NULL) return(0); /* Don't grow push parser buffer. */ - if (ctxt->progressive) + if ((ctxt->progressive) && (ctxt->inputNr <= 1)) return(0); if (buf->error != 0) return(-1); @@ -603,10 +602,7 @@ xmlParserInputBufferPtr buf = in->buf; size_t used; - /* Don't shrink pull parser memory buffers. */ - if ((buf == NULL) || - ((ctxt->progressive == 0) && - (buf->encoder == NULL) && (buf->readcallback == NULL))) + if (buf == NULL) return; used = in->cur - in->base; @@ -700,138 +696,102 @@ void xmlNextChar(xmlParserCtxtPtr ctxt) { + const unsigned char *cur; + size_t avail; + int c; + if ((ctxt == NULL) || (ctxt->instate == XML_PARSER_EOF) || (ctxt->input == NULL)) return; - if (!(VALID_CTXT(ctxt))) { - xmlErrInternal(ctxt, "Parser input data memory error\n", NULL); - ctxt->errNo = XML_ERR_INTERNAL_ERROR; - xmlStopParser(ctxt); - return; - } + avail = ctxt->input->end - ctxt->input->cur; - if (ctxt->input->end - ctxt->input->cur < INPUT_CHUNK) { + if (avail < INPUT_CHUNK) { xmlParserGrow(ctxt); if ((ctxt->instate == XML_PARSER_EOF) || (ctxt->input->cur >= ctxt->input->end)) return; + avail = ctxt->input->end - ctxt->input->cur; } - if ((ctxt->input->flags & XML_INPUT_8_BIT) == 0) { - const unsigned char *cur; - unsigned char c; + cur = ctxt->input->cur; + c = *cur; - /* - * 2.11 End-of-Line Handling - * the literal two-character sequence "#xD#xA" or a standalone - * literal #xD, an XML processor must pass to the application - * the single character #xA. - */ - if (*(ctxt->input->cur) == '\n') { - ctxt->input->line++; ctxt->input->col = 1; - } else - ctxt->input->col++; - - /* - * We are supposed to handle UTF8, check it's valid - * From rfc2044: encoding of the Unicode values on UTF-8: - * - * UCS-4 range (hex.) UTF-8 octet sequence (binary) - * 0000 0000-0000 007F 0xxxxxxx - * 0000 0080-0000 07FF 110xxxxx 10xxxxxx - * 0000 0800-0000 FFFF 1110xxxx 10xxxxxx 10xxxxxx - * - * Check for the 0x110000 limit too - */ - cur = ctxt->input->cur; - - c = *cur; - if (c & 0x80) { - size_t avail; - - if (c == 0xC0) - goto encoding_error; - - avail = ctxt->input->end - ctxt->input->cur; - - if ((avail < 2) || (cur[1] & 0xc0) != 0x80) - goto encoding_error; - if ((c & 0xe0) == 0xe0) { - unsigned int val; - - if ((avail < 3) || (cur[2] & 0xc0) != 0x80) - goto encoding_error; - if ((c & 0xf0) == 0xf0) { - if (((c & 0xf8) != 0xf0) || - (avail < 4) || ((cur[3] & 0xc0) != 0x80)) - goto encoding_error; - /* 4-byte code */ - ctxt->input->cur += 4; - val = (cur[0] & 0x7) << 18; - val |= (cur[1] & 0x3f) << 12; - val |= (cur[2] & 0x3f) << 6; - val |= cur[3] & 0x3f; - } else { - /* 3-byte code */ - ctxt->input->cur += 3; - val = (cur[0] & 0xf) << 12; - val |= (cur[1] & 0x3f) << 6; - val |= cur[2] & 0x3f; - } - if (((val > 0xd7ff) && (val < 0xe000)) || - ((val > 0xfffd) && (val < 0x10000)) || - (val >= 0x110000)) { - xmlErrEncodingInt(ctxt, XML_ERR_INVALID_CHAR, - "Char 0x%X out of allowed range\n", - val); - } - } else - /* 2-byte code */ - ctxt->input->cur += 2; - } else - /* 1-byte code */ + if (c < 0x80) { + if (c == '\n') { ctxt->input->cur++; - } else { - /* - * Assume it's a fixed length encoding (1) with - * a compatible encoding for the ASCII set, since - * XML constructs only use < 128 chars - */ - - if (*(ctxt->input->cur) == '\n') { - ctxt->input->line++; ctxt->input->col = 1; - } else + ctxt->input->line++; + ctxt->input->col = 1; + } else if (c == '\r') { + /* + * 2.11 End-of-Line Handling + * the literal two-character sequence "#xD#xA" or a standalone + * literal #xD, an XML processor must pass to the application + * the single character #xA. + */ + ctxt->input->cur += ((cur[1] == '\n') ? 2 : 1); + ctxt->input->line++; + ctxt->input->col = 1; + return; + } else { + ctxt->input->cur++; ctxt->input->col++; - ctxt->input->cur++; - } - return; -encoding_error: - /* - * If we detect an UTF8 error that probably mean that the - * input encoding didn't get properly advertised in the - * declaration header. Report the error and switch the encoding - * to ISO-Latin-1 (if you don't like this policy, just declare the - * encoding !) - */ - if ((ctxt == NULL) || (ctxt->input == NULL) || - (ctxt->input->end - ctxt->input->cur < 4)) { - __xmlErrEncoding(ctxt, XML_ERR_INVALID_CHAR, - "Input is not proper UTF-8, indicate encoding !\n", - NULL, NULL); + } } else { - char buffer[150]; + ctxt->input->col++; - snprintf(buffer, 149, "Bytes: 0x%02X 0x%02X 0x%02X 0x%02X\n", - ctxt->input->cur[0], ctxt->input->cur[1], - ctxt->input->cur[2], ctxt->input->cur[3]); - __xmlErrEncoding(ctxt, XML_ERR_INVALID_CHAR, - "Input is not proper UTF-8, indicate encoding !\n%s", - BAD_CAST buffer, NULL); + if ((avail < 2) || (cur[1] & 0xc0) != 0x80) + goto encoding_error; + + if (c < 0xe0) { + /* 2-byte code */ + if (c < 0xc2) + goto encoding_error; + ctxt->input->cur += 2; + } else { + unsigned int val = (c << 8) | cur[1]; + + if ((avail < 3) || (cur[2] & 0xc0) != 0x80) + goto encoding_error; + + if (c < 0xf0) { + /* 3-byte code */ + if ((val < 0xe0a0) || ((val >= 0xeda0) && (val < 0xee00))) + goto encoding_error; + ctxt->input->cur += 3; + } else { + if ((avail < 4) || ((cur[3] & 0xc0) != 0x80)) + goto encoding_error; + + /* 4-byte code */ + if ((val < 0xf090) || (val >= 0xf490)) + goto encoding_error; + ctxt->input->cur += 4; + } + } } - if ((ctxt->input->flags & XML_INPUT_HAS_ENCODING) == 0) { - ctxt->input->flags |= XML_INPUT_HAS_ENCODING; - ctxt->input->flags |= XML_INPUT_8_BIT; + + return; + +encoding_error: + /* Only report the first error */ + if ((ctxt->input->flags & XML_INPUT_ENCODING_ERROR) == 0) { + if ((ctxt == NULL) || (ctxt->input == NULL) || + (ctxt->input->end - ctxt->input->cur < 4)) { + __xmlErrEncoding(ctxt, XML_ERR_INVALID_CHAR, + "Input is not proper UTF-8, indicate encoding !\n", + NULL, NULL); + } else { + char buffer[150]; + + snprintf(buffer, 149, "Bytes: 0x%02X 0x%02X 0x%02X 0x%02X\n", + ctxt->input->cur[0], ctxt->input->cur[1], + ctxt->input->cur[2], ctxt->input->cur[3]); + __xmlErrEncoding(ctxt, XML_ERR_INVALID_CHAR, + "Input is not proper UTF-8, indicate encoding !\n%s", + BAD_CAST buffer, NULL); + } + ctxt->input->flags |= XML_INPUT_ENCODING_ERROR; } ctxt->input->cur++; return; @@ -859,149 +819,128 @@ int xmlCurrentChar(xmlParserCtxtPtr ctxt, int *len) { + const unsigned char *cur; + size_t avail; + int c; + if ((ctxt == NULL) || (len == NULL) || (ctxt->input == NULL)) return(0); if (ctxt->instate == XML_PARSER_EOF) return(0); - if (ctxt->input->end - ctxt->input->cur < INPUT_CHUNK) { + avail = ctxt->input->end - ctxt->input->cur; + + if (avail < INPUT_CHUNK) { xmlParserGrow(ctxt); if (ctxt->instate == XML_PARSER_EOF) return(0); + avail = ctxt->input->end - ctxt->input->cur; } - if ((*ctxt->input->cur >= 0x20) && (*ctxt->input->cur <= 0x7F)) { - *len = 1; - return(*ctxt->input->cur); - } - if ((ctxt->input->flags & XML_INPUT_8_BIT) == 0) { - /* - * We are supposed to handle UTF8, check it's valid - * From rfc2044: encoding of the Unicode values on UTF-8: - * - * UCS-4 range (hex.) UTF-8 octet sequence (binary) - * 0000 0000-0000 007F 0xxxxxxx - * 0000 0080-0000 07FF 110xxxxx 10xxxxxx - * 0000 0800-0000 FFFF 1110xxxx 10xxxxxx 10xxxxxx - * - * Check for the 0x110000 limit too - */ - const unsigned char *cur = ctxt->input->cur; - unsigned char c; - unsigned int val; + cur = ctxt->input->cur; + c = *cur; - c = *cur; - if (c & 0x80) { - size_t avail; + if (c < 0x80) { + /* 1-byte code */ + if (c < 0x20) { + /* + * 2.11 End-of-Line Handling + * the literal two-character sequence "#xD#xA" or a standalone + * literal #xD, an XML processor must pass to the application + * the single character #xA. + */ + if (c == '\r') { + *len = ((cur[1] == '\n') ? 2 : 1); + c = '\n'; + } else if (c == 0) { + if (ctxt->input->cur >= ctxt->input->end) { + *len = 0; + } else { + *len = 1; + /* + * TODO: Null bytes should be handled by callers, + * but this can be tricky. + */ + xmlErrEncodingInt(ctxt, XML_ERR_INVALID_CHAR, + "Char 0x0 out of allowed range\n", c); + } + } else { + *len = 1; + } + } else { + *len = 1; + } - if (((c & 0x40) == 0) || (c == 0xC0)) - goto encoding_error; + return(c); + } else { + int val; - avail = ctxt->input->end - ctxt->input->cur; + if (avail < 2) + goto incomplete_sequence; + if ((cur[1] & 0xc0) != 0x80) + goto encoding_error; - if (avail < 2) + if (c < 0xe0) { + /* 2-byte code */ + if (c < 0xc2) + goto encoding_error; + val = (c & 0x1f) << 6; + val |= cur[1] & 0x3f; + *len = 2; + } else { + if (avail < 3) goto incomplete_sequence; - if ((cur[1] & 0xc0) != 0x80) - goto encoding_error; - if ((c & 0xe0) == 0xe0) { - if (avail < 3) + if ((cur[2] & 0xc0) != 0x80) + goto encoding_error; + + if (c < 0xf0) { + /* 3-byte code */ + val = (c & 0xf) << 12; + val |= (cur[1] & 0x3f) << 6; + val |= cur[2] & 0x3f; + if ((val < 0x800) || ((val >= 0xd800) && (val < 0xe000))) + goto encoding_error; + *len = 3; + } else { + if (avail < 4) goto incomplete_sequence; - if ((cur[2] & 0xc0) != 0x80) - goto encoding_error; - if ((c & 0xf0) == 0xf0) { - if (avail < 4) - goto incomplete_sequence; - if (((c & 0xf8) != 0xf0) || - ((cur[3] & 0xc0) != 0x80)) - goto encoding_error; - /* 4-byte code */ - *len = 4; - val = (cur[0] & 0x7) << 18; - val |= (cur[1] & 0x3f) << 12; - val |= (cur[2] & 0x3f) << 6; - val |= cur[3] & 0x3f; - if (val < 0x10000) - goto encoding_error; - } else { - /* 3-byte code */ - *len = 3; - val = (cur[0] & 0xf) << 12; - val |= (cur[1] & 0x3f) << 6; - val |= cur[2] & 0x3f; - if (val < 0x800) - goto encoding_error; - } - } else { - /* 2-byte code */ - *len = 2; - val = (cur[0] & 0x1f) << 6; - val |= cur[1] & 0x3f; - if (val < 0x80) - goto encoding_error; - } - if (!IS_CHAR(val)) { - xmlErrEncodingInt(ctxt, XML_ERR_INVALID_CHAR, - "Char 0x%X out of allowed range\n", val); - } - return(val); - } else { - /* 1-byte code */ - *len = 1; - if ((*ctxt->input->cur == 0) && - (ctxt->input->end > ctxt->input->cur)) { - xmlErrEncodingInt(ctxt, XML_ERR_INVALID_CHAR, - "Char 0x0 out of allowed range\n", 0); - } - if (*ctxt->input->cur == 0xD) { - if (ctxt->input->cur[1] == 0xA) { - ctxt->input->cur++; - } - return(0xA); - } - return(*ctxt->input->cur); - } + if ((cur[3] & 0xc0) != 0x80) + goto encoding_error; + + /* 4-byte code */ + val = (c & 0x0f) << 18; + val |= (cur[1] & 0x3f) << 12; + val |= (cur[2] & 0x3f) << 6; + val |= cur[3] & 0x3f; + if ((val < 0x10000) || (val >= 0x110000)) + goto encoding_error; + *len = 4; + } + } + + return(val); } - /* - * Assume it's a fixed length encoding (1) with - * a compatible encoding for the ASCII set, since - * XML constructs only use < 128 chars - */ - *len = 1; - if (*ctxt->input->cur == 0xD) { - if (ctxt->input->cur[1] == 0xA) { - ctxt->input->cur++; - } - return(0xA); - } - return(*ctxt->input->cur); encoding_error: - /* - * If we detect an UTF8 error that probably mean that the - * input encoding didn't get properly advertised in the - * declaration header. Report the error and switch the encoding - * to ISO-Latin-1 (if you don't like this policy, just declare the - * encoding !) - */ - if (ctxt->input->end - ctxt->input->cur < 4) { - __xmlErrEncoding(ctxt, XML_ERR_INVALID_CHAR, - "Input is not proper UTF-8, indicate encoding !\n", - NULL, NULL); - } else { - char buffer[150]; + /* Only report the first error */ + if ((ctxt->input->flags & XML_INPUT_ENCODING_ERROR) == 0) { + if (ctxt->input->end - ctxt->input->cur < 4) { + __xmlErrEncoding(ctxt, XML_ERR_INVALID_CHAR, + "Input is not proper UTF-8, indicate encoding !\n", + NULL, NULL); + } else { + char buffer[150]; - snprintf(&buffer[0], 149, "Bytes: 0x%02X 0x%02X 0x%02X 0x%02X\n", - ctxt->input->cur[0], ctxt->input->cur[1], - ctxt->input->cur[2], ctxt->input->cur[3]); - __xmlErrEncoding(ctxt, XML_ERR_INVALID_CHAR, - "Input is not proper UTF-8, indicate encoding !\n%s", - BAD_CAST buffer, NULL); - } - if ((ctxt->input->flags & XML_INPUT_HAS_ENCODING) == 0) { - ctxt->input->flags |= XML_INPUT_HAS_ENCODING; - ctxt->input->flags |= XML_INPUT_8_BIT; + snprintf(&buffer[0], 149, "Bytes: 0x%02X 0x%02X 0x%02X 0x%02X\n", + ctxt->input->cur[0], ctxt->input->cur[1], + ctxt->input->cur[2], ctxt->input->cur[3]); + __xmlErrEncoding(ctxt, XML_ERR_INVALID_CHAR, + "Input is not proper UTF-8, indicate encoding !\n%s", + BAD_CAST buffer, NULL); + } + ctxt->input->flags |= XML_INPUT_ENCODING_ERROR; } *len = 1; - return(*ctxt->input->cur); + return(0xFFFD); /* U+FFFD Replacement Character */ incomplete_sequence: /* @@ -1258,7 +1197,6 @@ in = input->buf; input->flags |= XML_INPUT_HAS_ENCODING; - input->flags &= ~XML_INPUT_8_BIT; /* * UTF-8 requires no encoding handler. @@ -1986,6 +1924,15 @@ ctxt->input_id = 1; ctxt->maxAmpl = XML_MAX_AMPLIFICATION_DEFAULT; xmlInitNodeInfoSeq(&ctxt->node_seq); + + if (ctxt->nsdb == NULL) { + ctxt->nsdb = xmlParserNsCreate(); + if (ctxt->nsdb == NULL) { + xmlErrMemory(ctxt, NULL); + return(-1); + } + } + return(0); } @@ -2045,7 +1992,9 @@ if (ctxt->vctxt.nodeTab != NULL) xmlFree(ctxt->vctxt.nodeTab); if (ctxt->atts != NULL) xmlFree((xmlChar * *)ctxt->atts); if (ctxt->dict != NULL) xmlDictFree(ctxt->dict); - if (ctxt->nsTab != NULL) xmlFree((char *) ctxt->nsTab); + if (ctxt->nsTab != NULL) xmlFree(ctxt->nsTab); + if (ctxt->nsdb != NULL) xmlParserNsFree(ctxt->nsdb); + if (ctxt->attrHash != NULL) xmlFree(ctxt->attrHash); if (ctxt->pushTab != NULL) xmlFree(ctxt->pushTab); if (ctxt->attallocs != NULL) xmlFree(ctxt->attallocs); if (ctxt->attsDefault != NULL)
diff --git a/src/runtest.c b/src/runtest.c index ed1dfab..fe896b7 100644 --- a/src/runtest.c +++ b/src/runtest.c
@@ -359,7 +359,7 @@ } static void -testStructuredErrorHandler(void *ctx ATTRIBUTE_UNUSED, xmlErrorPtr err) { +testStructuredErrorHandler(void *ctx ATTRIBUTE_UNUSED, const xmlError *err) { char *file = NULL; int line = 0; int code = -1; @@ -839,6 +839,12 @@ NULL /* xmlStructuredErrorFunc */ }; +typedef struct { + const char *filename; + xmlHashTablePtr generalEntities; + xmlHashTablePtr parameterEntities; +} debugContext; + static xmlSAXHandlerPtr emptySAXHandler = &emptySAXHandlerStruct; static int callbacks = 0; static int quiet = 0; @@ -997,13 +1003,16 @@ * Returns the xmlParserInputPtr if inlined or NULL for DOM behaviour. */ static xmlEntityPtr -getEntityDebug(void *ctx ATTRIBUTE_UNUSED, const xmlChar *name) +getEntityDebug(void *ctx, const xmlChar *name) { + debugContext *ctxt = ctx; + callbacks++; if (quiet) return(NULL); fprintf(SAXdebug, "SAX.getEntity(%s)\n", name); - return(NULL); + + return(xmlHashLookup(ctxt->generalEntities, name)); } /** @@ -1016,13 +1025,16 @@ * Returns the xmlParserInputPtr */ static xmlEntityPtr -getParameterEntityDebug(void *ctx ATTRIBUTE_UNUSED, const xmlChar *name) +getParameterEntityDebug(void *ctx, const xmlChar *name) { + debugContext *ctxt = ctx; + callbacks++; if (quiet) return(NULL); fprintf(SAXdebug, "SAX.getParameterEntity(%s)\n", name); - return(NULL); + + return(xmlHashLookup(ctxt->parameterEntities, name)); } @@ -1038,10 +1050,13 @@ * An entity definition has been parsed */ static void -entityDeclDebug(void *ctx ATTRIBUTE_UNUSED, const xmlChar *name, int type, +entityDeclDebug(void *ctx, const xmlChar *name, int type, const xmlChar *publicId, const xmlChar *systemId, xmlChar *content) { -const xmlChar *nullstr = BAD_CAST "(null)"; + debugContext *ctxt = ctx; + xmlEntityPtr ent; + const xmlChar *nullstr = BAD_CAST "(null)"; + /* not all libraries handle printing null pointers nicely */ if (publicId == NULL) publicId = nullstr; @@ -1054,6 +1069,16 @@ return; fprintf(SAXdebug, "SAX.entityDecl(%s, %d, %s, %s, %s)\n", name, type, publicId, systemId, content); + + ent = xmlNewEntity(NULL, name, type, publicId, systemId, content); + if (systemId != NULL) + ent->URI = xmlBuildURI(systemId, (const xmlChar *) ctxt->filename); + + if ((type == XML_INTERNAL_PARAMETER_ENTITY) || + (type == XML_EXTERNAL_PARAMETER_ENTITY)) + xmlHashAddEntry(ctxt->parameterEntities, name, ent); + else + xmlHashAddEntry(ctxt->generalEntities, name, ent); } /** @@ -1711,6 +1736,13 @@ static xmlSAXHandlerPtr debugHTMLSAXHandler = &debugHTMLSAXHandlerStruct; #endif /* LIBXML_HTML_ENABLED */ +static void +hashFreeEntity(void *payload, const xmlChar *name ATTRIBUTE_UNUSED) { + xmlEntityPtr ent = payload; + + xmlFreeEntity(ent); +} + /** * saxParseTest: * @filename: the file to parse @@ -1784,16 +1816,24 @@ } else #endif { + debugContext userData; xmlParserCtxtPtr ctxt = xmlCreateFileParserCtxt(filename); + if (options & XML_PARSE_SAX1) { memcpy(ctxt->sax, debugSAXHandler, sizeof(xmlSAXHandler)); options -= XML_PARSE_SAX1; } else { memcpy(ctxt->sax, debugSAX2Handler, sizeof(xmlSAXHandler)); } + userData.filename = filename; + userData.generalEntities = xmlHashCreate(0); + userData.parameterEntities = xmlHashCreate(0); + ctxt->userData = &userData; xmlCtxtUseOptions(ctxt, options); xmlParseDocument(ctxt); ret = ctxt->wellFormed ? 0 : ctxt->errNo; + xmlHashFree(userData.generalEntities, hashFreeEntity); + xmlHashFree(userData.parameterEntities, hashFreeEntity); xmlFreeDoc(ctxt->myDoc); xmlFreeParserCtxt(ctxt); } @@ -4391,6 +4431,10 @@ const char *filename = params->filename; int okay = 1; +#ifdef LIBXML_THREAD_ALLOC_ENABLED + xmlMemSetup(xmlMemFree, xmlMemMalloc, xmlMemRealloc, xmlMemoryStrdup); +#endif + myDoc = xmlReadFile(filename, NULL, XML_PARSE_NOENT | XML_PARSE_DTDLOAD); if (myDoc) { xmlFreeDoc(myDoc);
diff --git a/src/runxmlconf.c b/src/runxmlconf.c index b871b69..3053f6a 100644 --- a/src/runxmlconf.c +++ b/src/runxmlconf.c
@@ -121,7 +121,7 @@ } static void -testErrorHandler(void *userData ATTRIBUTE_UNUSED, xmlErrorPtr error) { +testErrorHandler(void *userData ATTRIBUTE_UNUSED, const xmlError *error) { int res; if (testErrorsSize >= 32768)
diff --git a/src/testapi.c b/src/testapi.c index 7337b34..b780e23 100644 --- a/src/testapi.c +++ b/src/testapi.c
@@ -39,7 +39,7 @@ static void structured_errors(void *userData ATTRIBUTE_UNUSED, - xmlErrorPtr error ATTRIBUTE_UNUSED) { + const xmlError *error ATTRIBUTE_UNUSED) { generic_errors++; }
diff --git a/src/testchar.c b/src/testchar.c index 0dc7ccd..8895d8d 100644 --- a/src/testchar.c +++ b/src/testchar.c
@@ -15,7 +15,7 @@ int lastError; -static void errorHandler(void *unused, xmlErrorPtr err) { +static void errorHandler(void *unused, const xmlError *err) { if ((unused == NULL) && (err != NULL) && (lastError == 0)) { lastError = err->code; } @@ -261,6 +261,40 @@ return(test_ret); } +static int +testCurrentChar(xmlParserCtxtPtr ctxt, int *len) { + const xmlChar *oldcur; + int c, err, len2; + + lastError = 0; + c = xmlCurrentChar(ctxt, len); + ctxt->input->flags = 0; + err = lastError; + + oldcur = ctxt->input->cur; + lastError = 0; + xmlNextChar(ctxt); + ctxt->input->flags = 0; + len2 = ctxt->input->cur - oldcur; + ctxt->input->cur = oldcur; + + if ((*ctxt->input->cur != 0) && (err != lastError)) { + fprintf(stderr, "xmlCurrentChar and xmlNextChar report different " + "errors: %d %d\n", err, lastError); + return(-1); + } + + if ((err == 0) && (*len != len2)) { + fprintf(stderr, "xmlCurrentChar and xmlNextChar report different " + "lengths: %d %d\n", *len, len2); + return(-1); + } + + lastError = err; + + return(c); +} + static int testCharRangeByte1(xmlParserCtxtPtr ctxt) { int i = 0; int len, c; @@ -273,9 +307,9 @@ data[0] = (char) i; ctxt->nbErrors = 0; - lastError = 0; - c = xmlCurrentChar(ctxt, &len); - ctxt->input->flags = 0; + c = testCurrentChar(ctxt, &len); + if (c < 0) + continue; if ((i == 0) || (i >= 0x80)) { /* we must see an error there */ if (lastError != XML_ERR_INVALID_CHAR) { @@ -309,9 +343,9 @@ data[1] = (char) j; ctxt->nbErrors = 0; - lastError = 0; - c = xmlCurrentChar(ctxt, &len); - ctxt->input->flags = 0; + c = testCurrentChar(ctxt, &len); + if (c < 0) + continue; /* if first bit of first char is set, then second bit must too */ if ((i & 0x80) && ((i & 0x40) == 0)) { @@ -403,9 +437,9 @@ value = (K & 0x3F) + ((j & 0x3F) << 6) + ((i & 0xF) << 12); ctxt->nbErrors = 0; - lastError = 0; - c = xmlCurrentChar(ctxt, &len); - ctxt->input->flags = 0; + c = testCurrentChar(ctxt, &len); + if (c < 0) + continue; /* * if fourth bit of first char is set, then the sequence would need @@ -447,10 +481,9 @@ } /* - * There are values in that range that are not allowed in XML-1.0 + * There are values that are not allowed in UTF-8 */ - else if (((value > 0xD7FF) && (value <0xE000)) || - ((value > 0xFFFD) && (value <0x10000))) { + else if ((value > 0xD7FF) && (value <0xE000)) { if (lastError != XML_ERR_INVALID_CHAR) { fprintf(stderr, "Failed to detect invalid char 0x%04X for Bytes 0x%02X 0x%02X 0x%02X\n", @@ -506,9 +539,9 @@ ((i & 0x7) << 18); ctxt->nbErrors = 0; - lastError = 0; - c = xmlCurrentChar(ctxt, &len); - ctxt->input->flags = 0; + c = testCurrentChar(ctxt, &len); + if (c < 0) + continue; /* * if fifth bit of first char is set, then the sequence would need @@ -551,10 +584,9 @@ } /* - * There are values in that range that are not allowed in XML-1.0 + * There are values in that are not allowed in UTF-8 */ - else if (((value > 0xD7FF) && (value <0xE000)) || - ((value > 0xFFFD) && (value <0x10000)) || + else if (((value > 0xD7FF) && (value < 0xE000)) || (value > 0x10FFFF)) { if (lastError != XML_ERR_INVALID_CHAR) { fprintf(stderr,
diff --git a/src/testdict.c b/src/testdict.c index 97157b1..9066424 100644 --- a/src/testdict.c +++ b/src/testdict.c
@@ -3,6 +3,9 @@ #include <libxml/parser.h> #include <libxml/dict.h> + +/**** dictionary tests ****/ + /* #define WITH_PRINT */ static const char *seeds1[] = { @@ -119,7 +122,8 @@ /* * This tests the sub-dictionary support */ -static int run_test2(xmlDictPtr parent) { +static int +test_subdict(xmlDictPtr parent) { int i, j; xmlDictPtr dict; int ret = 0; @@ -283,19 +287,14 @@ /* * Test a single dictionary */ -static int run_test1(void) { +static int +test_dict(xmlDict *dict) { int i, j; - xmlDictPtr dict; int ret = 0; xmlChar prefix[40]; xmlChar *cur, *pref; const xmlChar *tmp; - dict = xmlDictCreate(); - if (dict == NULL) { - fprintf(stderr, "Out of memory while creating dictionary\n"); - exit(1); - } /* Cast to avoid buggy warning on MSVC. */ memset((void *) test1, 0, sizeof(test1)); @@ -391,17 +390,13 @@ } } - run_test2(dict); - - xmlDictFree(dict); return(ret); } -int main(void) -{ - int ret; - - LIBXML_TEST_VERSION +static int +testall_dict(void) { + xmlDictPtr dict; + int ret = 0; strings1 = xmlMalloc(NB_STRINGS_MAX * sizeof(strings1[0])); memset(strings1, 0, NB_STRINGS_MAX * sizeof(strings1[0])); @@ -417,17 +412,407 @@ #ifdef WITH_PRINT print_strings(); #endif - ret = run_test1(); - if (ret == 0) { - printf("dictionary tests succeeded %d strings\n", 2 * NB_STRINGS_MAX); - } else { - printf("dictionary tests failed with %d errors\n", nbErrors); + + dict = xmlDictCreate(); + if (dict == NULL) { + fprintf(stderr, "Out of memory while creating dictionary\n"); + exit(1); } + if (test_dict(dict) != 0) { + ret = 1; + } + if (test_subdict(dict) != 0) { + ret = 1; + } + xmlDictFree(dict); + clean_strings(); xmlFree(strings1); xmlFree(strings2); xmlFree(test1); xmlFree(test2); + + return ret; +} + + +/**** Hash table tests ****/ + +static unsigned +rng_state[2] = { 123, 456 }; + +#define HASH_ROL(x,n) ((x) << (n) | ((x) & 0xFFFFFFFF) >> (32 - (n))) + +#ifdef __clang__ +__attribute__ ((no_sanitize("unsigned-integer-overflow"))) +__attribute__ ((no_sanitize("unsigned-shift-base"))) +#endif +static unsigned +my_rand(unsigned max) { + unsigned s0 = rng_state[0]; + unsigned s1 = rng_state[1]; + unsigned result = HASH_ROL(s0 * 0x9E3779BB, 5) * 5; + + s1 ^= s0; + rng_state[0] = HASH_ROL(s0, 26) ^ s1 ^ (s1 << 9); + rng_state[1] = HASH_ROL(s1, 13); + + return((result & 0xFFFFFFFF) % max); +} + +static xmlChar * +gen_random_string(xmlChar id) { + unsigned size = my_rand(64) + 1; + unsigned id_pos = my_rand(size); + size_t j; + + xmlChar *str = xmlMalloc(size + 1); + for (j = 0; j < size; j++) { + str[j] = 'a' + my_rand(26); + } + str[id_pos] = id; + str[size] = 0; + + /* Generate QName in 75% of cases */ + if (size > 3 && my_rand(4) > 0) { + unsigned colon_pos = my_rand(size - 3) + 1; + + if (colon_pos >= id_pos) + colon_pos++; + str[colon_pos] = ':'; + } + + return str; +} + +typedef struct { + xmlChar **strings; + size_t num_entries; + size_t num_keys; + size_t num_strings; + size_t index; + xmlChar id; +} StringPool; + +static StringPool * +pool_new(size_t num_entries, size_t num_keys, xmlChar id) { + StringPool *ret; + size_t num_strings; + + ret = xmlMalloc(sizeof(*ret)); + ret->num_entries = num_entries; + ret->num_keys = num_keys; + num_strings = num_entries * num_keys; + ret->strings = xmlMalloc(num_strings * sizeof(ret->strings[0])); + memset(ret->strings, 0, num_strings * sizeof(ret->strings[0])); + ret->num_strings = num_strings; + ret->index = 0; + ret->id = id; + + return ret; +} + +static void +pool_free(StringPool *pool) { + size_t i; + + for (i = 0; i < pool->num_strings; i++) { + xmlFree(pool->strings[i]); + } + xmlFree(pool->strings); + xmlFree(pool); +} + +static int +pool_done(StringPool *pool) { + return pool->index >= pool->num_strings; +} + +static void +pool_reset(StringPool *pool) { + pool->index = 0; +} + +static int +pool_bulk_insert(StringPool *pool, xmlHashTablePtr hash, size_t num) { + size_t i, j; + int ret = 0; + + for (i = pool->index, j = 0; i < pool->num_strings && j < num; j++) { + xmlChar *str[3]; + size_t k; + + while (1) { + xmlChar tmp_key[1]; + int res; + + for (k = 0; k < pool->num_keys; k++) + str[k] = gen_random_string(pool->id); + + switch (pool->num_keys) { + case 1: + res = xmlHashAddEntry(hash, str[0], tmp_key); + if (res == 0 && + xmlHashUpdateEntry(hash, str[0], str[0], NULL) != 0) + ret = -1; + break; + case 2: + res = xmlHashAddEntry2(hash, str[0], str[1], tmp_key); + if (res == 0 && + xmlHashUpdateEntry2(hash, str[0], str[1], str[0], + NULL) != 0) + ret = -1; + break; + case 3: + res = xmlHashAddEntry3(hash, str[0], str[1], str[2], + tmp_key); + if (res == 0 && + xmlHashUpdateEntry3(hash, str[0], str[1], str[2], + str[0], NULL) != 0) + ret = -1; + break; + } + + if (res == 0) + break; + for (k = 0; k < pool->num_keys; k++) + xmlFree(str[k]); + } + + for (k = 0; k < pool->num_keys; k++) + pool->strings[i++] = str[k]; + } + + pool->index = i; + return ret; +} + +static xmlChar * +hash_qlookup(xmlHashTable *hash, xmlChar **names, size_t num_keys) { + xmlChar *prefix[3]; + const xmlChar *local[3]; + xmlChar *res; + size_t i; + + for (i = 0; i < 3; ++i) { + if (i >= num_keys) { + prefix[i] = NULL; + local[i] = NULL; + } else { + const xmlChar *name = names[i]; + const xmlChar *colon = BAD_CAST strchr((const char *) name, ':'); + + if (colon == NULL) { + prefix[i] = NULL; + local[i] = name; + } else { + prefix[i] = xmlStrndup(name, colon - name); + local[i] = &colon[1]; + } + } + } + + res = xmlHashQLookup3(hash, prefix[0], local[0], prefix[1], local[1], + prefix[2], local[2]); + + for (i = 0; i < 3; ++i) + xmlFree(prefix[i]); + + return res; +} + +static int +pool_bulk_lookup(StringPool *pool, xmlHashTablePtr hash, size_t num, + int existing) { + size_t i, j; + int ret = 0; + + for (i = pool->index, j = 0; i < pool->num_strings && j < num; j++) { + xmlChar **str = &pool->strings[i]; + int q; + + for (q = 0; q < 2; q++) { + xmlChar *res = NULL; + + if (q) { + res = hash_qlookup(hash, str, pool->num_keys); + } else { + switch (pool->num_keys) { + case 1: + res = xmlHashLookup(hash, str[0]); + break; + case 2: + res = xmlHashLookup2(hash, str[0], str[1]); + break; + case 3: + res = xmlHashLookup3(hash, str[0], str[1], str[2]); + break; + } + } + + if (existing) { + if (res != str[0]) + ret = -1; + } else { + if (res != NULL) + ret = -1; + } + } + + i += pool->num_keys; + } + + pool->index = i; + return ret; +} + +static int +pool_bulk_remove(StringPool *pool, xmlHashTablePtr hash, size_t num) { + size_t i, j; + int ret = 0; + + for (i = pool->index, j = 0; i < pool->num_strings && j < num; j++) { + xmlChar **str = &pool->strings[i]; + int res = -1; + + switch (pool->num_keys) { + case 1: + res = xmlHashRemoveEntry(hash, str[0], NULL); + break; + case 2: + res = xmlHashRemoveEntry2(hash, str[0], str[1], NULL); + break; + case 3: + res = xmlHashRemoveEntry3(hash, str[0], str[1], str[2], NULL); + break; + } + + if (res != 0) + ret = -1; + + i += pool->num_keys; + } + + pool->index = i; + return ret; +} + +static int +test_hash(size_t num_entries, size_t num_keys, int use_dict) { + xmlDict *dict = NULL; + xmlHashTable *hash; + StringPool *pool1, *pool2; + int ret = 0; + + if (use_dict) { + dict = xmlDictCreate(); + hash = xmlHashCreateDict(0, dict); + } else { + hash = xmlHashCreate(0); + } + pool1 = pool_new(num_entries, num_keys, '1'); + pool2 = pool_new(num_entries, num_keys, '2'); + + /* Insert all strings from pool2 and about half of pool1. */ + while (!pool_done(pool2)) { + if (pool_bulk_insert(pool1, hash, my_rand(50)) != 0) { + fprintf(stderr, "pool1: hash insert failed\n"); + ret = 1; + } + if (pool_bulk_insert(pool2, hash, my_rand(100)) != 0) { + fprintf(stderr, "pool1: hash insert failed\n"); + ret = 1; + } + } + + /* Check existing entries */ + pool_reset(pool2); + if (pool_bulk_lookup(pool2, hash, pool2->num_entries, 1) != 0) { + fprintf(stderr, "pool2: hash lookup failed\n"); + ret = 1; + } + + /* Remove all strings from pool2 and insert the rest of pool1. */ + pool_reset(pool2); + while (!pool_done(pool1) || !pool_done(pool2)) { + if (pool_bulk_insert(pool1, hash, my_rand(50)) != 0) { + fprintf(stderr, "pool1: hash insert failed\n"); + ret = 1; + } + if (pool_bulk_remove(pool2, hash, my_rand(100)) != 0) { + fprintf(stderr, "pool2: hash remove failed\n"); + ret = 1; + } + } + + /* Check existing entries */ + pool_reset(pool1); + if (pool_bulk_lookup(pool1, hash, pool1->num_entries, 1) != 0) { + fprintf(stderr, "pool1: hash lookup failed\n"); + ret = 1; + } + + /* Check removed entries */ + pool_reset(pool2); + if (pool_bulk_lookup(pool2, hash, pool2->num_entries, 0) != 0) { + fprintf(stderr, "pool2: hash lookup succeeded unexpectedly\n"); + ret = 1; + } + + pool_free(pool1); + pool_free(pool2); + xmlHashFree(hash, NULL); + xmlDictFree(dict); + + return ret; +} + +static int +testall_hash(void) { + size_t num_keys; + + for (num_keys = 1; num_keys <= 3; num_keys++) { + size_t num_strings; + size_t max_strings = num_keys == 1 ? 100000 : 1000; + + for (num_strings = 10; num_strings <= max_strings; num_strings *= 10) { + size_t reps, i; + + reps = 1000 / num_strings; + if (reps == 0) + reps = 1; + + for (i = 0; i < reps; i++) { + if (test_hash(num_strings, num_keys, /* use_dict */ 0) != 0) + return(1); + } + + if (test_hash(num_strings, num_keys, /* use_dict */ 1) != 0) + return(1); + } + } + + return(0); +} + + +/**** main ****/ + +int +main(void) { + int ret = 0; + + LIBXML_TEST_VERSION + + if (testall_dict() != 0) { + fprintf(stderr, "dictionary tests failed\n"); + ret = 1; + } + if (testall_hash() != 0) { + fprintf(stderr, "hash tests failed\n"); + ret = 1; + } + xmlCleanupParser(); return(ret); }
diff --git a/src/testlimits.c b/src/testlimits.c index de0da9d..78d62fb 100644 --- a/src/testlimits.c +++ b/src/testlimits.c
@@ -475,7 +475,7 @@ } static void -testStructuredErrorHandler(void *ctx ATTRIBUTE_UNUSED, xmlErrorPtr err) { +testStructuredErrorHandler(void *ctx ATTRIBUTE_UNUSED, const xmlError *err) { char *file = NULL; int line = 0; int code = -1;
diff --git a/src/testparser.c b/src/testparser.c new file mode 100644 index 0000000..625ba10 --- /dev/null +++ b/src/testparser.c
@@ -0,0 +1,80 @@ +/* + * testparser.c: Additional parser tests + * + * See Copyright for the status of this software. + */ + +#include <libxml/parser.h> + +#ifdef LIBXML_PUSH_ENABLED +static int +testHugePush(void) { + xmlParserCtxtPtr ctxt; + int err, i; + + ctxt = xmlCreatePushParserCtxt(NULL, NULL, NULL, 0, NULL); + + /* + * Push parse a document larger than XML_MAX_LOOKUP_LIMIT + * (10,000,000 bytes). This mainly tests whether shrinking the + * buffer works when push parsing. + */ + xmlParseChunk(ctxt, "<doc>", 5, 0); + for (i = 0; i < 1000000; i++) + xmlParseChunk(ctxt, "<elem>text</elem>", 17, 0); + xmlParseChunk(ctxt, "</doc>", 6, 1); + + err = ctxt->wellFormed ? 0 : 1; + xmlFreeDoc(ctxt->myDoc); + xmlFreeParserCtxt(ctxt); + + return err; +} + +static int +testHugeEncodedChunk(void) { + xmlBufferPtr buf; + xmlChar *chunk; + xmlParserCtxtPtr ctxt; + int err, i; + + /* + * Test the push parser with a built-in encoding handler like ISO-8859-1 + * and a chunk larger than the initial decoded buffer (currently 4 KB). + */ + buf = xmlBufferCreate(); + xmlBufferCat(buf, + BAD_CAST "<?xml version='1.0' encoding='ISO-8859-1'?>\n"); + xmlBufferCat(buf, BAD_CAST "<doc><!-- "); + for (i = 0; i < 2000; i++) + xmlBufferCat(buf, BAD_CAST "0123456789"); + xmlBufferCat(buf, BAD_CAST " --></doc>"); + chunk = xmlBufferDetach(buf); + xmlBufferFree(buf); + + ctxt = xmlCreatePushParserCtxt(NULL, NULL, NULL, 0, NULL); + + xmlParseChunk(ctxt, (char *) chunk, xmlStrlen(chunk), 0); + xmlParseChunk(ctxt, NULL, 0, 1); + + err = ctxt->wellFormed ? 0 : 1; + xmlFreeDoc(ctxt->myDoc); + xmlFreeParserCtxt(ctxt); + xmlFree(chunk); + + return err; +} +#endif + +int +main(void) { + int err = 0; + +#ifdef LIBXML_PUSH_ENABLED + err |= testHugePush(); + err |= testHugeEncodedChunk(); +#endif + + return err; +} +
diff --git a/src/testrecurse.c b/src/testrecurse.c index 01e15b2..c583290 100644 --- a/src/testrecurse.c +++ b/src/testrecurse.c
@@ -444,7 +444,7 @@ } static void -testStructuredErrorHandler(void *ctx ATTRIBUTE_UNUSED, xmlErrorPtr err) { +testStructuredErrorHandler(void *ctx ATTRIBUTE_UNUSED, const xmlError *err) { char *file = NULL; int line = 0; int code = -1;
diff --git a/src/threads.c b/src/threads.c index 5b68b61..3e8ef2f 100644 --- a/src/threads.c +++ b/src/threads.c
@@ -579,6 +579,7 @@ if (xmlParserInnerInitialized == 0) { #if defined(_WIN32) && \ + !defined(LIBXML_THREAD_ALLOC_ENABLED) && \ (!defined(LIBXML_STATIC) || defined(LIBXML_STATIC_FOR_DLL)) if (xmlFree == free) atexit(xmlCleanupParser); @@ -586,6 +587,7 @@ xmlInitMemoryInternal(); /* Should come second */ xmlInitGlobalsInternal(); + xmlInitRandom(); xmlInitDictInternal(); xmlInitEncodingInternal(); #if defined(LIBXML_XPATH_ENABLED) || defined(LIBXML_SCHEMAS_ENABLED) @@ -650,6 +652,7 @@ #endif xmlCleanupDictInternal(); + xmlCleanupRandom(); xmlCleanupGlobalsInternal(); /* * Must come last. On Windows, xmlCleanupGlobalsInternal can call @@ -663,7 +666,9 @@ xmlParserInnerInitialized = 0; } -#if defined(HAVE_ATTRIBUTE_DESTRUCTOR) && !defined(LIBXML_STATIC) && \ +#if defined(HAVE_ATTRIBUTE_DESTRUCTOR) && \ + !defined(LIBXML_THREAD_ALLOC_ENABLED) && \ + !defined(LIBXML_STATIC) && \ !defined(_WIN32) static void ATTRIBUTE_DESTRUCTOR
diff --git a/src/tree.c b/src/tree.c index fe02b41..a6264e8 100644 --- a/src/tree.c +++ b/src/tree.c
@@ -4206,7 +4206,10 @@ /* * Humm, we are copying an element whose namespace is defined * out of the new tree scope. Search it in the original tree - * and add it at the top of the new tree + * and add it at the top of the new tree. + * + * TODO: Searching the original tree seems unnecessary. We + * already have a namespace URI. */ ns = xmlSearchNs(node->doc, node, node->ns->prefix); if (ns != NULL) { @@ -4214,8 +4217,8 @@ while (root->parent != NULL) root = root->parent; ret->ns = xmlNewNs(root, ns->href, ns->prefix); - } else { - ret->ns = xmlNewReconciledNs(doc, ret, node->ns); + } else { + ret->ns = xmlNewReconciledNs(doc, ret, node->ns); } } else { /*
diff --git a/src/xmlreader.c b/src/xmlreader.c index c04cb11..5c37738 100644 --- a/src/xmlreader.c +++ b/src/xmlreader.c
@@ -3973,10 +3973,10 @@ } static void - xmlTextReaderStructuredError(void *ctxt, xmlErrorPtr error); +xmlTextReaderStructuredError(void *ctxt, const xmlError *error); static void -xmlTextReaderValidityStructuredRelay(void *userData, xmlErrorPtr error) +xmlTextReaderValidityStructuredRelay(void *userData, const xmlError *error) { xmlTextReaderPtr reader = (xmlTextReaderPtr) userData; @@ -4707,7 +4707,7 @@ } static void -xmlTextReaderStructuredError(void *ctxt, xmlErrorPtr error) +xmlTextReaderStructuredError(void *ctxt, const xmlError *error) { xmlParserCtxtPtr ctx = (xmlParserCtxtPtr) ctxt;
diff --git a/src/xmlstring.c b/src/xmlstring.c index 5473472..d9e16d7 100644 --- a/src/xmlstring.c +++ b/src/xmlstring.c
@@ -712,47 +712,47 @@ goto error; if (len == NULL) goto error; - if (*len < 1) - goto error; c = utf[0]; - if (c & 0x80) { - if (*len < 2) + if (c < 0x80) { + if (*len < 1) goto error; - if ((utf[1] & 0xc0) != 0x80) + /* 1-byte code */ + *len = 1; + } else { + if ((*len < 2) || ((utf[1] & 0xc0) != 0x80)) goto error; - if ((c & 0xe0) == 0xe0) { - if (*len < 3) + if (c < 0xe0) { + if (c < 0xc2) goto error; - if ((utf[2] & 0xc0) != 0x80) + /* 2-byte code */ + *len = 2; + c = (c & 0x1f) << 6; + c |= utf[1] & 0x3f; + } else { + if ((*len < 3) || ((utf[2] & 0xc0) != 0x80)) goto error; - if ((c & 0xf0) == 0xf0) { - if (*len < 4) + if (c < 0xf0) { + /* 3-byte code */ + *len = 3; + c = (c & 0xf) << 12; + c |= (utf[1] & 0x3f) << 6; + c |= utf[2] & 0x3f; + if ((c < 0x800) || ((c >= 0xd800) && (c < 0xe000))) goto error; - if ((c & 0xf8) != 0xf0 || (utf[3] & 0xc0) != 0x80) + } else { + if ((*len < 4) || ((utf[3] & 0xc0) != 0x80)) goto error; *len = 4; /* 4-byte code */ - c = (utf[0] & 0x7) << 18; + c = (c & 0x7) << 18; c |= (utf[1] & 0x3f) << 12; c |= (utf[2] & 0x3f) << 6; c |= utf[3] & 0x3f; - } else { - /* 3-byte code */ - *len = 3; - c = (utf[0] & 0xf) << 12; - c |= (utf[1] & 0x3f) << 6; - c |= utf[2] & 0x3f; + if ((c < 0x10000) || (c >= 0x110000)) + goto error; } - } else { - /* 2-byte code */ - *len = 2; - c = (utf[0] & 0x1f) << 6; - c |= utf[1] & 0x3f; } - } else { - /* 1-byte code */ - *len = 1; } return(c);