/*

 * dict.c: dictionary of reusable strings, just used to avoid allocation

 *         and freeing operations.

 *

 * Copyright (C) 2003-2012 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

 * MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE AUTHORS AND

 * CONTRIBUTORS ACCEPT NO RESPONSIBILITY IN ANY CONCEIVABLE MANNER.

 *

 * Author: daniel@veillard.com

 */

#define IN_LIBXML

#include "libxml.h"

#include <limits.h>

#ifdef HAVE_STDLIB_H

#include <stdlib.h>

#endif

#ifdef HAVE_TIME_H

#include <time.h>

#endif

/*

 * 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(HAVE_RAND) && defined(HAVE_SRAND) && defined(HAVE_TIME)

#define DICT_RANDOMIZATION

#endif

#include <string.h>

#ifdef HAVE_STDINT_H

#include <stdint.h>

#else

#ifdef HAVE_INTTYPES_H

#include <inttypes.h>

#elif defined(_WIN32)

typedef unsigned __int32 uint32_t;

#endif

#endif

#include <libxml/tree.h>

#include <libxml/dict.h>

#include <libxml/xmlmemory.h>

#include <libxml/xmlerror.h>

#include <libxml/globals.h>

/* #define DEBUG_GROW */

/* #define DICT_DEBUG_PATTERNS */

#define MAX_HASH_LEN 3

#define MIN_DICT_SIZE 128

#define MAX_DICT_HASH 8 * 2048

#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 long okey;

};

typedef struct _xmlDictStrings xmlDictStrings;

typedef xmlDictStrings *xmlDictStringsPtr;

struct _xmlDictStrings {

    xmlDictStringsPtr next;

    xmlChar *free;

    xmlChar *end;

    size_t size;

    size_t nbStrings;

    xmlChar array[1];

};

/*

 * The entire dictionary

 */

struct _xmlDict {

    int ref_counter;

    struct _xmlDictEntry *dict;

    size_t size;

    unsigned int nbElems;

    xmlDictStringsPtr strings;

    struct _xmlDict *subdict;

    /* used for randomization */

    int seed;

    /* used to impose a limit on size */

    size_t limit;

};

/*

 * A mutex for modifying the reference counter for shared

 * dictionaries.

 */

static xmlRMutexPtr xmlDictMutex = NULL;

/*

 * Whether the dictionary mutex was initialized.

 */

static int xmlDictInitialized = 0;

#ifdef DICT_RANDOMIZATION

#ifdef HAVE_RAND_R

/*

 * Internal data for random function, protected by xmlDictMutex

 */

static unsigned int rand_seed = 0;

#endif

#endif

/**

 * xmlInitializeDict:

 *

 * Do the dictionary mutex initialization.

 * this function is deprecated

 *

 * Returns 0 if initialization was already done, and 1 if that

 * call led to the initialization

 */

int xmlInitializeDict(void) {

    return(0);

}

/**

 * __xmlInitializeDict:

 *

 * This function is not public

 * Do the dictionary mutex initialization.

 * this function is not thread safe, initialization should

 * normally be done once at setup when called from xmlOnceInit()

 * we may also land in this code if thread support is not compiled in

 *

 * Returns 0 if initialization was already done, and 1 if that

 * call led to the initialization

 */

int __xmlInitializeDict(void) {

    if (xmlDictInitialized)

        return(1);

    if ((xmlDictMutex = xmlNewRMutex()) == NULL)

        return(0);

    xmlRMutexLock(xmlDictMutex);

#ifdef DICT_RANDOMIZATION

#ifdef HAVE_RAND_R

    rand_seed = time(NULL);

    rand_r(& rand_seed);

#else

    srand(time(NULL));

#endif

#endif

    xmlDictInitialized = 1;

    xmlRMutexUnlock(xmlDictMutex);

    return(1);

}

#ifdef DICT_RANDOMIZATION

int __xmlRandom(void) {

    int ret;

    if (xmlDictInitialized == 0)

        __xmlInitializeDict();

    xmlRMutexLock(xmlDictMutex);

#ifdef HAVE_RAND_R

    ret = rand_r(& rand_seed);

#else

    ret = rand();

#endif

    xmlRMutexUnlock(xmlDictMutex);

    return(ret);

}

#endif

/**

 * xmlDictCleanup:

 *

 * Free the dictionary mutex. Do not call unless sure the library

 * is not in use anymore !

 */

void

xmlDictCleanup(void) {

    if (!xmlDictInitialized)

        return;

    xmlFreeRMutex(xmlDictMutex);

    xmlDictInitialized = 0;

}

/*

 * xmlDictAddString:

 * @dict: the dictionary

 * @name: the name of the userdata

 * @len: the length of the name

 *

 * Add the string to the array[s]

 *

 * Returns the pointer of the local string, or NULL in case of error.

 */

static const xmlChar *

xmlDictAddString(xmlDictPtr dict, const xmlChar *name, unsigned int namelen) {

    xmlDictStringsPtr pool;

    const xmlChar *ret;

    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)

	    goto found_pool;

	if (pool->size > size) size = pool->size;

        limit += pool->size;

	pool = pool->next;

    }

    /*

     * Not found, need to allocate

     */

    if (pool == NULL) {

        if ((dict->limit > 0) && (limit > dict->limit)) {

            return(NULL);

        }

        if (size == 0) size = 1000;

	else size *= 4; /* exponential growth */

        if (size < 4 * namelen)

	    size = 4 * namelen; /* just in case ! */

	pool = (xmlDictStringsPtr) xmlMalloc(sizeof(xmlDictStrings) + size);

	if (pool == NULL)

	    return(NULL);

	pool->size = size;

	pool->nbStrings = 0;

	pool->free = &pool->array[0];

	pool->end = &pool->array[size];

	pool->next = dict->strings;

	dict->strings = pool;

#ifdef DICT_DEBUG_PATTERNS

        fprintf(stderr, "+");

#endif

    }

found_pool:

    ret = pool->free;

    memcpy(pool->free, name, namelen);

    pool->free += namelen;

    *(pool->free++) = 0;

    pool->nbStrings++;

    return(ret);

}

/*

 * xmlDictAddQString:

 * @dict: the dictionary

 * @prefix: the prefix of the userdata

 * @plen: the prefix length

 * @name: the name of the userdata

 * @len: the length of the name

 *

 * Add the QName to the array[s]

 *

 * Returns the pointer of the local string, or NULL in case of error.

 */

static const xmlChar *

xmlDictAddQString(xmlDictPtr dict, const xmlChar *prefix, unsigned int plen,

                 const xmlChar *name, unsigned int namelen)

{

    xmlDictStringsPtr pool;

    const xmlChar *ret;

    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)

	    goto found_pool;

	if (pool->size > size) size = pool->size;

        limit += pool->size;

	pool = pool->next;

    }

    /*

     * Not found, need to allocate

     */

    if (pool == NULL) {

        if ((dict->limit > 0) && (limit > dict->limit)) {

            return(NULL);

        }

        if (size == 0) size = 1000;

	else size *= 4; /* exponential growth */

        if (size < 4 * (namelen + plen + 1))

	    size = 4 * (namelen + plen + 1); /* just in case ! */

	pool = (xmlDictStringsPtr) xmlMalloc(sizeof(xmlDictStrings) + size);

	if (pool == NULL)

	    return(NULL);

	pool->size = size;

	pool->nbStrings = 0;

	pool->free = &pool->array[0];

	pool->end = &pool->array[size];

	pool->next = dict->strings;

	dict->strings = pool;

#ifdef DICT_DEBUG_PATTERNS

        fprintf(stderr, "+");

#endif

    }

found_pool:

    ret = pool->free;

    memcpy(pool->free, prefix, plen);

    pool->free += plen;

    *(pool->free++) = ':';

    memcpy(pool->free, name, namelen);

    pool->free += namelen;

    *(pool->free++) = 0;

    pool->nbStrings++;

    return(ret);

}

#ifdef WITH_BIG_KEY

/*

 * xmlDictComputeBigKey:

 *

 * Calculate a hash key 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

 */

static uint32_t

xmlDictComputeBigKey(const xmlChar* data, int namelen, int seed) {

    uint32_t hash;

    int i;

    if (namelen <= 0 || data == NULL) return(0);

    hash = seed;

    for (i = 0;i < namelen; i++) {

        hash += data[i];

	hash += (hash << 10);

	hash ^= (hash >> 6);

    }

    hash += (hash << 3);

    hash ^= (hash >> 11);

    hash += (hash << 15);

    return hash;

}

/*

 * 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.

 */

static unsigned long

xmlDictComputeBigQKey(const xmlChar *prefix, int plen,

                      const xmlChar *name, int len, int seed)

{

    uint32_t hash;

    int i;

    hash = seed;

    for (i = 0;i < plen; i++) {

        hash += prefix[i];

	hash += (hash << 10);

	hash ^= (hash >> 6);

    }

    hash += ':';

    hash += (hash << 10);

    hash ^= (hash >> 6);

    for (i = 0;i < len; i++) {

        hash += name[i];

	hash += (hash << 10);

	hash ^= (hash >> 6);

    }

    hash += (hash << 3);

    hash ^= (hash >> 11);

    hash += (hash << 15);

    return hash;

}

#endif /* WITH_BIG_KEY */

/*

 * xmlDictComputeFastKey:

 *

 * Calculate a hash key using a fast hash function that works well

 * for low hash table fill.

 */

static unsigned long

xmlDictComputeFastKey(const xmlChar *name, int namelen, int seed) {

    unsigned long value = seed;

    if (name == NULL) return(0);

    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.

 */

static unsigned long

xmlDictComputeFastQKey(const xmlChar *prefix, int plen,

                       const xmlChar *name, int len, int seed)

{

    unsigned long value = (unsigned long) seed;

    if (plen == 0)

	value += 30 * (unsigned long) ':';

    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 += (unsigned long) ':';

	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:

 *

 * Create a new dictionary

 *

 * Returns the newly created dictionary, or NULL if an error occurred.

 */

xmlDictPtr

xmlDictCreate(void) {

    xmlDictPtr dict;

    if (!xmlDictInitialized)

        if (!__xmlInitializeDict())

            return(NULL);

#ifdef DICT_DEBUG_PATTERNS

    fprintf(stderr, "C");

#endif

    dict = xmlMalloc(sizeof(xmlDict));

    if (dict) {

        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;

#endif

	    return(dict);

        }

        xmlFree(dict);

    }

    return(NULL);

}

/**

 * xmlDictCreateSub:

 * @sub: an existing dictionary

 *

 * Create a new dictionary, inheriting strings from the read-only

 * dictionary @sub. On lookup, strings are first searched in the

 * new dictionary, then in @sub, and if not found are created in the

 * new dictionary.

 *

 * Returns the newly created dictionary, or NULL if an error occurred.

 */

xmlDictPtr

xmlDictCreateSub(xmlDictPtr sub) {

    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);

    }

    return(dict);

}

/**

 * xmlDictReference:

 * @dict: the dictionary

 *

 * Increment the reference counter of a dictionary

 *

 * Returns 0 in case of success and -1 in case of error

 */

int

xmlDictReference(xmlDictPtr dict) {

    if (!xmlDictInitialized)

        if (!__xmlInitializeDict())

            return(-1);

    if (dict == NULL) return -1;

    xmlRMutexLock(xmlDictMutex);

    dict->ref_counter++;

    xmlRMutexUnlock(xmlDictMutex);

    return(0);

}

/**

 * 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 long key, okey;

    size_t oldsize, i;

    xmlDictEntryPtr iter, next;

    struct _xmlDictEntry *olddict;

#ifdef DEBUG_GROW

    unsigned long nbElem = 0;

#endif

    int ret = 0;

    int keep_keys = 1;

    if (dict == NULL)

	return(-1);

    if (size < 8)

        return(-1);

    if (size > 8 * 2048)

	return(-1);

#ifdef DICT_DEBUG_PATTERNS

    fprintf(stderr, "*");

#endif

    oldsize = dict->size;

    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 herei

		 * 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

 *

 * Free the hash @dict and its contents. The userdata is

 * deallocated with @f if provided.

 */

void

xmlDictFree(xmlDictPtr dict) {

    size_t i;

    xmlDictEntryPtr iter;

    xmlDictEntryPtr next;

    int inside_dict = 0;

    xmlDictStringsPtr pool, nextp;

    if (dict == NULL)

	return;

    if (!xmlDictInitialized)

        if (!__xmlInitializeDict())

            return;

    /* decrement the counter, it may be shared by a parser and docs */

    xmlRMutexLock(xmlDictMutex);

    dict->ref_counter--;

    if (dict->ref_counter > 0) {

        xmlRMutexUnlock(xmlDictMutex);

        return;

    }

    xmlRMutexUnlock(xmlDictMutex);

    if (dict->subdict != NULL) {

        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);

    }

    pool = dict->strings;

    while (pool != NULL) {

        nextp = pool->next;

	xmlFree(pool);

	pool = nextp;

    }

    xmlFree(dict);

}

/**

 * 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 long key, okey, nbi = 0;

    xmlDictEntryPtr entry;

    xmlDictEntryPtr insert;

    const xmlChar *ret;

    unsigned int 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);