Upgrade to libxml 2.9.2 and libxslt 1.1.28

third_party/libxml/src/hash.c

 /*
  * hash.c: chained hash tables
  *
  * Reference: Your favorite introductory book on algorithms
  *
- * Copyright (C) 2000 Bjorn Reese and Daniel Veillard.
+ * 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
  * MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE AUTHORS AND
  * CONTRIBUTORS ACCEPT NO RESPONSIBILITY IN ANY CONCEIVABLE MANNER.
  *
  * Author: breese@users.sourceforge.net
  */
 
 #define IN_LIBXML
 #include "libxml.h"
 
 #include <string.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
+ */
+#if defined(HAVE_RAND) && defined(HAVE_SRAND) && defined(HAVE_TIME)
+#define HASH_RANDOMIZATION
+#endif
+
 #include <libxml/parser.h>
 #include <libxml/hash.h>
 #include <libxml/xmlmemory.h>
 #include <libxml/xmlerror.h>
 #include <libxml/globals.h>
 
 #define MAX_HASH_LEN 8
 
 /* #define DEBUG_GROW */
 
@@ skipping 12 matching lines @@
 };
 
 /*
  * The entire hash table
  */
 struct _xmlHashTable {
     struct _xmlHashEntry *table;
     int size;
     int nbElems;
     xmlDictPtr dict;
+#ifdef HASH_RANDOMIZATION
+    int random_seed;
+#endif
 };
 
 /*
  * xmlHashComputeKey:
  * Calculate the hash key
  */
 static unsigned long
 xmlHashComputeKey(xmlHashTablePtr table, const xmlChar *name,
                   const xmlChar *name2, const xmlChar *name3) {
     unsigned long value = 0L;
     char ch;
-    
+
+#ifdef HASH_RANDOMIZATION
+    value = table->random_seed;
+#endif
     if (name != NULL) {
         value += 30 * (*name);
         while ((ch = *name++) != 0) {
             value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
         }
     }
+    value = value ^ ((value << 5) + (value >> 3));
     if (name2 != NULL) {
         while ((ch = *name2++) != 0) {
             value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
         }
     }
+    value = value ^ ((value << 5) + (value >> 3));
     if (name3 != NULL) {
         while ((ch = *name3++) != 0) {
             value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
         }
     }
     return (value % table->size);
 }
 
 static unsigned long
 xmlHashComputeQKey(xmlHashTablePtr table,
                    const xmlChar *prefix, const xmlChar *name,
                    const xmlChar *prefix2, const xmlChar *name2,
                    const xmlChar *prefix3, const xmlChar *name3) {
     unsigned long value = 0L;
     char ch;
-    
+
+#ifdef HASH_RANDOMIZATION
+    value = table->random_seed;
+#endif
     if (prefix != NULL)
         value += 30 * (*prefix);
     else
         value += 30 * (*name);
 
     if (prefix != NULL) {
         while ((ch = *prefix++) != 0) {
             value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
         }
         value = value ^ ((value << 5) + (value >> 3) + (unsigned long)':');
     }
     if (name != NULL) {
         while ((ch = *name++) != 0) {
             value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
         }
     }
+    value = value ^ ((value << 5) + (value >> 3));
     if (prefix2 != NULL) {
         while ((ch = *prefix2++) != 0) {
             value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
         }
         value = value ^ ((value << 5) + (value >> 3) + (unsigned long)':');
     }
     if (name2 != NULL) {
         while ((ch = *name2++) != 0) {
             value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
         }
     }
+    value = value ^ ((value << 5) + (value >> 3));
     if (prefix3 != NULL) {
         while ((ch = *prefix3++) != 0) {
             value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
         }
         value = value ^ ((value << 5) + (value >> 3) + (unsigned long)':');
     }
     if (name3 != NULL) {
         while ((ch = *name3++) != 0) {
             value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
         }
     }
     return (value % table->size);
 }
 
 /**
  * xmlHashCreate:
  * @size: the size of the hash table
  *
  * Create a new xmlHashTablePtr.
  *
  * Returns the newly created object, or NULL if an error occured.
  */
 xmlHashTablePtr
 xmlHashCreate(int size) {
     xmlHashTablePtr table;
-  
+
     if (size <= 0)
         size = 256;
-  
+
     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));
-            return(table);
+            memset(table->table, 0, size * sizeof(xmlHashEntry));
+#ifdef HASH_RANDOMIZATION
+            table->random_seed = __xmlRandom();
+#endif
+            return(table);
         }
         xmlFree(table);
     }
     return(NULL);
 }
 
 /**
  * xmlHashCreateDict:
  * @size: the size of the hash table
  * @dict: a dictionary to use for the hash
@@ skipping 25 matching lines @@
  */
 static int
 xmlHashGrow(xmlHashTablePtr table, int size) {
     unsigned long key;
     int oldsize, i;
     xmlHashEntryPtr iter, next;
     struct _xmlHashEntry *oldtable;
 #ifdef DEBUG_GROW
     unsigned long nbElem = 0;
 #endif
-  
+
     if (table == NULL)
         return(-1);
     if (size < 8)
         return(-1);
     if (size > 8 * 2048)
         return(-1);
 
     oldsize = table->size;
     oldtable = table->table;
     if (oldtable == NULL)
         return(-1);
-  
+
     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;
 
     /*  If the two loops are merged, there would be situations where
-        a new entry needs to allocated and data copied into it from 
+        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) 
+        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;
     }
 
     for (i = 0; i < oldsize; i++) {
         iter = oldtable[i].next;
         while (iter) {
             next = iter->next;
 
             /*
              * put back the entry in the new table
              */
 
             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;
+                iter->next = table->table[key].next;
+                table->table[key].next = iter;
             }
 
 #ifdef DEBUG_GROW
             nbElem++;
 #endif
 
             iter = next;
         }
     }
 
@@ skipping 295 matching lines @@
     } else {
         entry->name = xmlStrdup(name);
         entry->name2 = xmlStrdup(name2);
         entry->name3 = xmlStrdup(name3);
     }
     entry->payload = userdata;
     entry->next = NULL;
     entry->valid = 1;
 
 
-    if (insert != NULL) 
+    if (insert != NULL)
         insert->next = entry;
 
     table->nbElems++;
 
     if (len > MAX_HASH_LEN)
         xmlHashGrow(table, MAX_HASH_LEN * table->size);
 
     return(0);
 }
 
@@ skipping 128 matching lines @@
  * @table: the hash table
  * @name: the name of the userdata
  * @name2: a second name of the userdata
  * @name3: a third name of the userdata
  *
  * Find the userdata specified by the (@name, @name2, @name3) tuple.
  *
  * Returns the a pointer to the userdata
  */
 void *
-xmlHashLookup3(xmlHashTablePtr table, const xmlChar *name, 
+xmlHashLookup3(xmlHashTablePtr table, const xmlChar *name,
                const xmlChar *name2, const xmlChar *name3) {
     unsigned long key;
     xmlHashEntryPtr entry;
 
     if (table == NULL)
         return(NULL);
     if (name == NULL)
         return(NULL);
     key = xmlHashComputeKey(table, name, name2, name3);
     if (table->table[key].valid == 0)
@@ skipping 52 matching lines @@
             return(entry->payload);
     }
     return(NULL);
 }
 
 typedef struct {
     xmlHashScanner hashscanner;
     void *data;
 } stubData;
 
-static void 
-stubHashScannerFull (void *payload, void *data, const xmlChar *name, 
+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);
-}                                  
- 
+}
+
 /**
  * xmlHashScan:
  * @table: the hash table
  * @f:  the scanner function for items in the hash
  * @data:  extra data passed to f
  *
  * Scan the hash @table and applied @f to each value.
  */
 void
 xmlHashScan(xmlHashTablePtr table, xmlHashScanner f, void *data) {
     stubData stubdata;
     stubdata.data = data;
-    stubdata.hashscanner = f; 
+    stubdata.hashscanner = f;
     xmlHashScanFull (table, stubHashScannerFull, &stubdata);
 }
 
 /**
  * xmlHashScanFull:
  * @table: the hash table
  * @f:  the scanner function for items in the hash
  * @data:  extra data passed to f
  *
  * Scan the hash @table and applied @f to each value.
  */
 void
 xmlHashScanFull(xmlHashTablePtr table, xmlHashScannerFull f, void *data) {
     int i, nb;
     xmlHashEntryPtr iter;
     xmlHashEntryPtr next;
 
     if (table == NULL)
         return;
     if (f == NULL)
         return;
 
     if (table->table) {
         for(i = 0; i < table->size; i++) {
-            if (table->table[i].valid == 0) 
+            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 */
@@ skipping 18 matching lines @@
  * @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
  *
  * Scan the hash @table and applied @f to each value matching
  * (@name, @name2, @name3) tuple. If one of the names is null,
  * the comparison is considered to match.
  */
 void
-xmlHashScan3(xmlHashTablePtr table, const xmlChar *name, 
+xmlHashScan3(xmlHashTablePtr table, const xmlChar *name,
              const xmlChar *name2, const xmlChar *name3,
              xmlHashScanner f, void *data) {
     xmlHashScanFull3 (table, name, name2, name3,
                       (xmlHashScannerFull) f, data);
 }
 
 /**
  * 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
  *
  * Scan the hash @table and applied @f to each value matching
  * (@name, @name2, @name3) tuple. If one of the names is null,
  * the comparison is considered to match.
  */
 void
-xmlHashScanFull3(xmlHashTablePtr table, const xmlChar *name, 
+xmlHashScanFull3(xmlHashTablePtr table, const xmlChar *name,
                  const xmlChar *name2, const xmlChar *name3,
                  xmlHashScannerFull f, void *data) {
     int i;
     xmlHashEntryPtr iter;
     xmlHashEntryPtr next;
 
     if (table == NULL)
         return;
     if (f == NULL)
         return;
@@ skipping 33 matching lines @@
     xmlHashEntryPtr iter;
     xmlHashEntryPtr next;
     xmlHashTablePtr ret;
 
     if (table == NULL)
         return(NULL);
     if (f == NULL)
         return(NULL);
 
     ret = xmlHashCreate(table->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;
@@ skipping 115 matching lines @@
                 return(0);
             }
             prev = entry;
         }
         return(-1);
     }
 }
 
 #define bottom_hash
 #include "elfgcchack.h"