CVE-2013-6401 (C, published 2014-03-21T01:04Z)
Description: value: Jansson, possibly 2.4 and earlier, does not restrict the ability to trigger hash collisions predictably, which allows context-dependent attackers to cause a denial of service (CPU consumption) via a crafted JSON document.
Severity: MEDIUM (CVSS v3 base score: )
Weakness: CWE-310 \u2014 Cryptographic Issues
Weaknesses in this category are related to the design and implementation of data confidentiality and integrity. Frequently these deal with the use of encoding techniques, encryption libraries, and hashing algorithms. The weaknesses in this category could lead to a degradation of the quality data if they are not addressed.
Repository: https://github.com/akheron/jansson
Files changed:
CMakeLists.txt
cmake/config.h.cmake
configure.ac
src/Makefile.am
src/hashtable.c
src/hashtable.h
src/hashtable_seed.c
src/jansson.def
src/jansson.h
src/lookup3.h
src/utf.h
src/value.c
test/bin/json_process.c
test/suites/api/test_memory_funcs.c
test/suites/api/test_object.c
test/suites/encoding-flags/compact-object/env
test/suites/encoding-flags/indent-compact-object/env
test/suites/encoding-flags/indent-object/env
test/suites/encoding-flags/object/env
Commit message: CVE-2013-6401: Change hash function, randomize hashes

Thanks to Florian Weimer and Eric Sesterhenn for reporting, reviewing
and testing.


Vulnerable code:

   
check_include_files (sys/types.h HAVE_SYS_TYPES_H)
check_include_files (inttypes.h HAVE_INTTYPES_H)


elseif (HAVE_LONG AND (${LONG_INT} EQUAL 4))
   message (FATAL_ERROR "Could not detect a valid 32 bit integer type")


/* Reduced down to the defines that are actually used in the code */

/* Define to 1 if you have the <inttypes.h> (and friends) header file. */
#cmakedefine HAVE_INTTYPES_H 1
#cmakedefine HAVE_STDINT_H 1
/* We must include this here, as in (eg) utf.h it will want to use
   the integer type, which in MSVC2010 will be in stdint.h
   (there is no inttypes.h in MSVC2010) */
#if defined(HAVE_STDINT_H)
#  include <stdint.h>
#elif defined(HAVE_INTTYPES_H)
#  include <inttypes.h>
#elif defined(HAVE_SYS_TYPES_H)
#  include <sys/types.h>
#endif
/* Define to 1 if you have the <locale.h> header file. */
#cmakedefine HAVE_LOCALE_H 1
/* Define to 1 if you have the 'setlocale' function. */
/* Define to the type of a signed integer type of width exactly 32 bits if
   such a type exists and the standard includes do not define it. */

AC_CHECK_HEADERS([locale.h])
AC_CHECK_FUNCS([strtoll localeconv])
#define list_to_pair(list_)  container_of(list_, pair_t, list)

/* From http://www.cse.yorku.ca/~oz/hash.html */
static size_t hash_str(const void *ptr)
{
    const char *str = (const char *)ptr;

    size_t hash = 5381;
    size_t c;
    while((c = (size_t)*str))
    {
        hash = ((hash << 5) + hash) + c;
        str++;
    }
    return hash;
}
static const size_t primes[] = {
    5, 13, 23, 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
    49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469,
    12582917, 25165843, 50331653, 100663319, 201326611, 402653189,
    805306457, 1610612741
};

static JSON_INLINE size_t num_buckets(hashtable_t *hashtable)
{
    return primes[hashtable->num_buckets];
}


    index = hash % num_buckets(hashtable);
    hashtable->num_buckets++;
    new_size = num_buckets(hashtable);
    for(i = 0; i < num_buckets(hashtable); i++)
    hashtable->num_buckets = 0;  /* index to primes[] */
    hashtable->buckets = jsonp_malloc(num_buckets(hashtable) * sizeof(bucket_t));
    for(i = 0; i < num_buckets(hashtable); i++)
    if(hashtable->size >= num_buckets(hashtable))
    index = hash % num_buckets(hashtable);
    bucket = &hashtable->buckets[hash % num_buckets(hashtable)];
    for(i = 0; i < num_buckets(hashtable); i++)
    bucket = &hashtable->buckets[hash % num_buckets(hashtable)];
    size_t num_buckets;  /* index to primes[] */
#ifdef HAVE_INTTYPES_H
/* inttypes.h includes stdint.h in a standard environment, so there's
no need to include stdint.h separately. If inttypes.h doesn't define
int32_t, it's defined in config.h. */
#include <inttypes.h>
#endif /* HAVE_INTTYPES_H */

#else /* !HAVE_CONFIG_H */
#ifdef _WIN32
typedef int int32_t;
#else /* !_WIN32 */
/* Assume a standard environment */
#include <inttypes.h>
#endif /* _WIN32 */

#endif /* HAVE_CONFIG_H */
         flags |= JSON_SORT_KEYS;
    malloc_called += 1;
    free_called += 1;
    if(malloc_called != 20 || free_called != 20)
    if(strcmp(json_object_iter_key(iter), "a"))
        fail("iterating failed: wrong key");
    if(json_object_iter_value(iter) != foo)
        fail("iterating failed: wrong value");
    if(strcmp(json_object_iter_key(iter), "b"))
        fail("iterating failed: wrong key");
    if(json_object_iter_value(iter) != bar)
        fail("iterating failed: wrong value");
    if(strcmp(json_object_iter_key(iter), "c"))
        fail("iterating failed: wrong key");
    if(json_object_iter_value(iter) != baz)
        fail("iterating failed: wrong value");
    iter = json_object_iter_next(object, iter);
    if(!iter)
        fail("unable to increment iterator");
    if(strcmp(json_object_iter_key(iter), "c"))
        fail("iterating failed: wrong key");
    if(json_object_iter_value(iter) != baz)
        fail("iterating failed: wrong value");

    if(json_object_iter_set(object, iter, bar))
    if(strcmp(json_object_iter_key(iter), "c"))
    if(json_object_iter_value(iter) != bar)
    if(json_object_get(object, "c") != bar)
export JSON_COMPACT
export JSON_INDENT JSON_COMPACT
export JSON_INDENT

Fixed code:
OPTION (USE_URANDOM "Use /dev/urandom to seed the hash function." ON)
OPTION (USE_WINDOWS_CRYPTOAPI "Use CryptGenRandom to seed the hash function." ON)
INCLUDE (CheckCSourceCompiles)
check_include_files (endian.h HAVE_ENDIAN_H)
check_include_files (fcntl.h HAVE_FCNTL_H)
check_include_files (sched.h HAVE_SCHED_H)
check_include_files (unistd.h HAVE_UNISTD_H)
check_include_files (sys/param.h HAVE_SYS_PARAM_H)
check_include_files (sys/stat.h HAVE_SYS_STAT_H)
check_include_files (sys/time.h HAVE_SYS_TIME_H)
check_include_files (sys/time.h HAVE_SYS_TYPES_H)

check_function_exists (close HAVE_CLOSE)
check_function_exists (getpid HAVE_GETPID)
check_function_exists (gettimeofday HAVE_GETTIMEOFDAY)
check_function_exists (open HAVE_OPEN)
check_function_exists (read HAVE_READ)
check_function_exists (sched_yield HAVE_SCHED_YIELD)
elseif (HAVE_LONG_INT AND (${LONG_INT} EQUAL 4))
   message (FATAL_ERROR "Could not detect a valid 32-bit integer type")
endif ()

check_type_size (uint32_t UINT32_T)
check_type_size (__uint32 __UINT32)
check_type_size ("unsigned long" UNSIGNED_LONG_INT)
check_type_size ("unsigned int" UNSIGNED_INT)
if (HAVE_UINT32_T)
   set (JSON_UINT32 uint32_t)
elseif (HAVE___UINT32)
   set (JSON_UINT32 __uint32)
elseif (HAVE_UNSIGNED_LONG_INT AND (${UNSIGNED_LONG_INT} EQUAL 4))
   set (JSON_UINT32 "unsigned long")
elseif (HAVE_UNSIGNED_INT AND (${UNSIGNED_INT} EQUAL 4))
   set (JSON_UINT32 "unsigned int")
else ()
   message (FATAL_ERROR "Could not detect a valid unsigned 32-bit integer type")
check_c_source_compiles ("int main() { unsigned long val; __sync_bool_compare_and_swap(&val, 0, 1); return 0; } " HAVE_SYNC_BUILTINS)
check_c_source_compiles ("int main() { char l; unsigned long v; __atomic_test_and_set(&l, __ATOMIC_RELAXED); __atomic_store_n(&v, 1, __ATOMIC_ACQ_REL); __atomic_load_n(&v, __ATOMIC_ACQUIRE); return 0; }" HAVE_ATOMIC_BUILTINS)

#cmakedefine HAVE_ENDIAN_H 1
#cmakedefine HAVE_FCNTL_H 1
#cmakedefine HAVE_SCHED_H 1
#cmakedefine HAVE_UNISTD_H 1
#cmakedefine HAVE_SYS_PARAM_H 1
#cmakedefine HAVE_SYS_STAT_H 1
#cmakedefine HAVE_SYS_TIME_H 1
#cmakedefine HAVE_STDINT_H 1
#cmakedefine HAVE_CLOSE 1
#cmakedefine HAVE_GETPID 1
#cmakedefine HAVE_GETTIMEOFDAY 1
#cmakedefine HAVE_OPEN 1
#cmakedefine HAVE_READ 1
#cmakedefine HAVE_SCHED_YIELD 1
#cmakedefine HAVE_SYNC_BUILTINS 1
#cmakedefine HAVE_ATOMIC_BUILTINS 1
#cmakedefine HAVE_LOCALE_H 1
#cmakedefine HAVE_UINT32_T 1
#ifndef HAVE_UINT32_T
#  define uint32_t @JSON_UINT32@
#endif


#cmakedefine USE_URANDOM 1
#cmakedefine USE_WINDOWS_CRYPTOAPI 1
AC_CHECK_HEADERS([endian.h fcntl.h locale.h sched.h unistd.h sys/param.h sys/stat.h sys/time.h sys/types.h])
AC_TYPE_UINT32_T
AC_CHECK_FUNCS([close getpid gettimeofday localeconv open read sched_yield strtoll])

AC_MSG_CHECKING([for gcc __sync builtins])
have_sync_builtins=no
AC_TRY_LINK(
  [], [unsigned long val; __sync_bool_compare_and_swap(&val, 0, 1);],
  [have_sync_builtins=yes],
)
if test "x$have_sync_builtins" = "xyes"; then
  AC_DEFINE([HAVE_SYNC_BUILTINS], [1],
    [Define to 1 if gcc's __sync builtins are available])
fi
AC_MSG_RESULT([$have_sync_builtins])

AC_MSG_CHECKING([for gcc __atomic builtins])
have_atomic_builtins=no
AC_TRY_LINK(
  [], [char l; unsigned long v; __atomic_test_and_set(&l, __ATOMIC_RELAXED); __atomic_store_n(&v, 1, __ATOMIC_ACQ_REL); __atomic_load_n(&v, __ATOMIC_ACQUIRE);],
  [have_atomic_builtins=yes],
)
if test "x$have_atomic_builtins" = "xyes"; then
  AC_DEFINE([HAVE_ATOMIC_BUILTINS], [1],
    [Define to 1 if gcc's __atomic builtins are available])
fi
AC_MSG_RESULT([$have_atomic_builtins])
# Features
AC_ARG_ENABLE([urandom],
  [AS_HELP_STRING([--disable-urandom],
    [Don't use /dev/urandom to seed the hash function])],
  [use_urandom=$enableval], [use_urandom=yes])

if test "x$use_urandom" = xyes; then
AC_DEFINE([USE_URANDOM], [1],
  [Define to 1 if /dev/urandom should be used for seeding the hash function])
fi

AC_ARG_ENABLE([windows-cryptoapi],
  [AS_HELP_STRING([--disable-windows-cryptoapi],
    [Don't use CryptGenRandom to seed the hash function])],
  [use_windows_cryptoapi=$enableval], [use_windows_cryptoapi=yes])

if test "x$use_windows_cryptoapi" = xyes; then
AC_DEFINE([USE_WINDOWS_CRYPTOAPI], [1],
  [Define to 1 if CryptGenRandom should be used for seeding the hash function])
fi

	hashtable_seed.c \
#if HAVE_CONFIG_H
#include <config.h>
#endif


#if HAVE_STDINT_H
#include <stdint.h>
#endif

extern volatile uint32_t hashtable_seed;
/* Implementation of the hash function */
#include "lookup3.h"
#define list_to_pair(list_)  container_of(list_, pair_t, list)
#define hash_str(key)        ((size_t)hashlittle((key), strlen(key), hashtable_seed))
    index = hash & hashmask(hashtable->order);
    hashtable->order++;
    new_size = hashsize(hashtable->order);
    for(i = 0; i < hashsize(hashtable->order); i++)
    hashtable->order = 3;
    hashtable->buckets = jsonp_malloc(hashsize(hashtable->order) * sizeof(bucket_t));
    for(i = 0; i < hashsize(hashtable->order); i++)
    if(hashtable->size >= hashsize(hashtable->order))
    index = hash & hashmask(hashtable->order);
    bucket = &hashtable->buckets[hash & hashmask(hashtable->order)];
    for(i = 0; i < hashsize(hashtable->order); i++)
    bucket = &hashtable->buckets[hash & hashmask(hashtable->order)];
    size_t order;  /* hashtable has pow(2, order) buckets */

/* Generate sizeof(uint32_t) bytes of as random data as possible to seed
   the hash function.
*/

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <stdio.h>
#include <time.h>

#ifdef HAVE_STDINT_H
#include <stdint.h>
#endif

#ifdef HAVE_FCNTL_H
#include <fcntl.h>
#endif

#ifdef HAVE_SCHED_H
#include <sched.h>
#endif

#ifdef HAVE_UNISTD_H
#include <unistd.h>
#endif

#ifdef HAVE_SYS_STAT_H
#include <sys/stat.h>
#endif

#ifdef HAVE_SYS_TIME_H
#include <sys/time.h>
#endif

#ifdef HAVE_SYS_TYPES_H
#include <sys/types.h>
#endif

#if defined(_WIN32)
/* For _getpid() */
#include <process.h>
#endif

#include "jansson.h"


static uint32_t buf_to_uint32(char *data) {
    size_t i;
    uint32_t result = 0;

    for (i = 0; i < sizeof(uint32_t); i++)
        result = (result << 8) | (unsigned char)data[i];

    return result;
}



/* /dev/urandom */
#if !defined(_WIN32) && defined(USE_URANDOM)
static int seed_from_urandom(uint32_t *seed) {
    /* Use unbuffered I/O if we have open(), close() and read(). Otherwise
       fall back to fopen() */

    char data[sizeof(uint32_t)];
    int ok;

#if defined(HAVE_OPEN) && defined(HAVE_CLOSE) && defined(HAVE_READ)
    int urandom;
    urandom = open("/dev/urandom", O_RDONLY);
    if (urandom == -1)
        return 1;

    ok = read(urandom, data, sizeof(uint32_t)) == sizeof(uint32_t);
    close(urandom);
#else
    FILE *urandom;

    urandom = fopen("/dev/urandom", "rb");
    if (!urandom)
        return 1;

    ok = fread(data, 1, sizeof(uint32_t), urandom) == sizeof(uint32_t);
    fclose(urandom);
#endif

    if (!ok)
        return 1;

    *seed = buf_to_uint32(data);
    return 0;
}
#endif

/* Windows Crypto API */
#if defined(_WIN32) && defined(USE_WINDOWS_CRYPTOAPI)
#include <windows.h>
#include <wincrypt.h>

typedef BOOL (WINAPI *CRYPTACQUIRECONTEXTA)(HCRYPTPROV *phProv, LPCSTR pszContainer, LPCSTR pszProvider, DWORD dwProvType, DWORD dwFlags);
typedef BOOL (WINAPI *CRYPTGENRANDOM)(HCRYPTPROV hProv, DWORD dwLen, BYTE *pbBuffer);
typedef BOOL (WINAPI *CRYPTRELEASECONTEXT)(HCRYPTPROV hProv, DWORD dwFlags);

static int seed_from_windows_cryptoapi(uint32_t *seed)
{
    HINSTANCE hAdvAPI32 = NULL;
    CRYPTACQUIRECONTEXTA pCryptAcquireContext = NULL;
    CRYPTGENRANDOM pCryptGenRandom = NULL;
    CRYPTRELEASECONTEXT pCryptReleaseContext = NULL;
    HCRYPTPROV hCryptProv = 0;
    BYTE data[sizeof(uint32_t)];
    int ok;

    hAdvAPI32 = GetModuleHandle("advapi32.dll");
    if(hAdvAPI32 == NULL)
        return 1;

    pCryptAcquireContext = (CRYPTACQUIRECONTEXTA)GetProcAddress(hAdvAPI32, "CryptAcquireContextA");
    if (!pCryptAcquireContext)
        return 1;

    pCryptGenRandom = (CRYPTGENRANDOM)GetProcAddress(hAdvAPI32, "CryptGenRandom");
    if (!pCryptGenRandom)
        return 1;

    pCryptReleaseContext = (CRYPTRELEASECONTEXT)GetProcAddress(hAdvAPI32, "CryptReleaseContext");
    if (!pCryptReleaseContext)
        return 1;

    if (!pCryptAcquireContext(&hCryptProv, NULL, NULL, PROV_RSA_FULL, CRYPT_VERIFYCONTEXT))
        return 1;

    ok = CryptGenRandom(hCryptProv, sizeof(uint32_t), data);
    pCryptReleaseContext(hCryptProv, 0);

    if (!ok)
        return 1;

    *seed = buf_to_uint32((char *)data);
    return 0;
}
#endif

/* gettimeofday() and getpid() */
static int seed_from_timestamp_and_pid(uint32_t *seed) {
#ifdef HAVE_GETTIMEOFDAY
    /* XOR of seconds and microseconds */
    struct timeval tv;
    gettimeofday(&tv, NULL);
    *seed = (uint32_t)tv.tv_sec ^ (uint32_t)tv.tv_usec;
#else
    /* Seconds only */
    *seed = (uint32_t)time(NULL);
#endif

    /* XOR with PID for more randomness */
#if defined(_WIN32)
    *seed ^= (uint32_t)_getpid();
#elif defined(HAVE_GETPID)
    *seed ^= (uint32_t)getpid();
#endif

    return 0;
}

static uint32_t generate_seed() {
    uint32_t seed;
    int done = 0;

#if !defined(_WIN32) && defined(USE_URANDOM)
    if (!done && seed_from_urandom(&seed) == 0)
        done = 1;
#endif

#if defined(_WIN32) && defined(USE_WINDOWS_CRYPTOAPI)
    if (!done && seed_from_windows_cryptoapi(&seed) == 0)
        done = 1;
#endif

    if (!done) {
        /* Fall back to timestamp and PID if no better randomness is
           available */
        seed_from_timestamp_and_pid(&seed);
    }

    /* Make sure the seed is never zero */
    if (seed == 0)
        seed = 1;

    return seed;
}


volatile uint32_t hashtable_seed = 0;

#if defined(HAVE_ATOMIC_BUILTINS) && (defined(HAVE_SCHED_YIELD) || !defined(_WIN32))
static volatile char seed_initialized = 0;

void json_object_seed(size_t seed) {
    uint32_t new_seed = (uint32_t)seed;

    if (hashtable_seed == 0) {
        if (__atomic_test_and_set(&seed_initialized, __ATOMIC_RELAXED) == 0) {
            /* Do the seeding ourselves */
            if (new_seed == 0)
                new_seed = generate_seed();

            __atomic_store_n(&hashtable_seed, new_seed, __ATOMIC_ACQ_REL);
        } else {
            /* Wait for another thread to do the seeding */
            do {
#ifdef HAVE_SCHED_YIELD
                sched_yield();
#endif
            } while(__atomic_load_n(&hashtable_seed, __ATOMIC_ACQUIRE) == 0);
        }
    }
}
#elif defined(HAVE_SYNC_BUILTINS) && (defined(HAVE_SCHED_YIELD) || !defined(_WIN32))
void json_object_seed(size_t seed) {
    uint32_t new_seed = (uint32_t)seed;

    if (hashtable_seed == 0) {
        if (new_seed == 0) {
            /* Explicit synchronization fences are not supported by the
               __sync builtins, so every thread getting here has to
               generate the seed value.
            */
            new_seed = generate_seed();
        }

        do {
            if (__sync_bool_compare_and_swap(&hashtable_seed, 0, new_seed)) {
                /* We were the first to seed */
                break;
            } else {
                /* Wait for another thread to do the seeding */
#ifdef HAVE_SCHED_YIELD
                sched_yield();
#endif
            }
        } while(hashtable_seed == 0);
    }
}
#elif defined(_WIN32)
static long seed_initialized = 0;
void json_object_seed(size_t seed) {
    uint32_t new_seed = (uint32_t)seed;

    if (hashtable_seed == 0) {
        if (InterlockedIncrement(&seed_initialized) == 1) {
            /* Do the seeding ourselves */
            if (new_seed == 0)
                new_seed = generate_seed();

            hashtable_seed = new_seed;
        } else {
            /* Wait for another thread to do the seeding */
            do {
                SwitchToThread();
            } while (hashtable_seed == 0);
        }
    }
}
#else
/* Fall back to a thread-unsafe version */
void json_object_seed(size_t seed) {
    uint32_t new_seed = (uint32_t)seed;

    if (hashtable_seed == 0) {
        if (new_seed == 0)
            new_seed = generate_seed();

        hashtable_seed = new_seed;
    }
}
#endif
    json_object_seed
void json_object_seed(size_t seed);
/*
-------------------------------------------------------------------------------
lookup3.c, by Bob Jenkins, May 2006, Public Domain.

These are functions for producing 32-bit hashes for hash table lookup.
hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final() 
are externally useful functions.  Routines to test the hash are included 
if SELF_TEST is defined.  You can use this free for any purpose.  It's in
the public domain.  It has no warranty.

You probably want to use hashlittle().  hashlittle() and hashbig()
hash byte arrays.  hashlittle() is is faster than hashbig() on
little-endian machines.  Intel and AMD are little-endian machines.
On second thought, you probably want hashlittle2(), which is identical to
hashlittle() except it returns two 32-bit hashes for the price of one.  
You could implement hashbig2() if you wanted but I haven't bothered here.

If you want to find a hash of, say, exactly 7 integers, do
  a = i1;  b = i2;  c = i3;
  mix(a,b,c);
  a += i4; b += i5; c += i6;
  mix(a,b,c);
  a += i7;
  final(a,b,c);
then use c as the hash value.  If you have a variable length array of
4-byte integers to hash, use hashword().  If you have a byte array (like
a character string), use hashlittle().  If you have several byte arrays, or
a mix of things, see the comments above hashlittle().  

Why is this so big?  I read 12 bytes at a time into 3 4-byte integers, 
then mix those integers.  This is fast (you can do a lot more thorough
mixing with 12*3 instructions on 3 integers than you can with 3 instructions
on 1 byte), but shoehorning those bytes into integers efficiently is messy.
-------------------------------------------------------------------------------
*/

#include <stdlib.h>

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#ifdef HAVE_STDINT_H
#include <stdint.h>     /* defines uint32_t etc */
#endif

#ifdef HAVE_SYS_PARAM_H
#include <sys/param.h>  /* attempt to define endianness */
#endif

#ifdef HAVE_ENDIAN_H
# include <endian.h>    /* attempt to define endianness */
#endif

/*
 * My best guess at if you are big-endian or little-endian.  This may
 * need adjustment.
 */
#if (defined(__BYTE_ORDER) && defined(__LITTLE_ENDIAN) && \
     __BYTE_ORDER == __LITTLE_ENDIAN) || \
    (defined(i386) || defined(__i386__) || defined(__i486__) || \
     defined(__i586__) || defined(__i686__) || defined(vax) || defined(MIPSEL))
# define HASH_LITTLE_ENDIAN 1
# define HASH_BIG_ENDIAN 0
#elif (defined(__BYTE_ORDER) && defined(__BIG_ENDIAN) && \
       __BYTE_ORDER == __BIG_ENDIAN) || \
      (defined(sparc) || defined(POWERPC) || defined(mc68000) || defined(sel))
# define HASH_LITTLE_ENDIAN 0
# define HASH_BIG_ENDIAN 1
#else
# define HASH_LITTLE_ENDIAN 0
# define HASH_BIG_ENDIAN 0
#endif

#define hashsize(n) ((uint32_t)1<<(n))
#define hashmask(n) (hashsize(n)-1)
#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))

/*
-------------------------------------------------------------------------------
mix -- mix 3 32-bit values reversibly.

This is reversible, so any information in (a,b,c) before mix() is
still in (a,b,c) after mix().

If four pairs of (a,b,c) inputs are run through mix(), or through
mix() in reverse, there are at least 32 bits of the output that
are sometimes the same for one pair and different for another pair.
This was tested for:
* pairs that differed by one bit, by two bits, in any combination
  of top bits of (a,b,c), or in any combination of bottom bits of
  (a,b,c).
* "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
  the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
  is commonly produced by subtraction) look like a single 1-bit
  difference.
* the base values were pseudorandom, all zero but one bit set, or 
  all zero plus a counter that starts at zero.

Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that
satisfy this are
    4  6  8 16 19  4
    9 15  3 18 27 15
   14  9  3  7 17  3
Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing
for "differ" defined as + with a one-bit base and a two-bit delta.  I
used http://burtleburtle.net/bob/hash/avalanche.html to choose 
the operations, constants, and arrangements of the variables.

This does not achieve avalanche.  There are input bits of (a,b,c)
that fail to affect some output bits of (a,b,c), especially of a.  The
most thoroughly mixed value is c, but it doesn't really even achieve
avalanche in c.

This allows some parallelism.  Read-after-writes are good at doubling
the number of bits affected, so the goal of mixing pulls in the opposite
direction as the goal of parallelism.  I did what I could.  Rotates
seem to cost as much as shifts on every machine I could lay my hands
on, and rotates are much kinder to the top and bottom bits, so I used
rotates.
-------------------------------------------------------------------------------
*/
#define mix(a,b,c) \
{ \
  a -= c;  a ^= rot(c, 4);  c += b; \
  b -= a;  b ^= rot(a, 6);  a += c; \
  c -= b;  c ^= rot(b, 8);  b += a; \
  a -= c;  a ^= rot(c,16);  c += b; \
  b -= a;  b ^= rot(a,19);  a += c; \
  c -= b;  c ^= rot(b, 4);  b += a; \
}

/*
-------------------------------------------------------------------------------
final -- final mixing of 3 32-bit values (a,b,c) into c

Pairs of (a,b,c) values differing in only a few bits will usually
produce values of c that look totally different.  This was tested for
* pairs that differed by one bit, by two bits, in any combination
  of top bits of (a,b,c), or in any combination of bottom bits of
  (a,b,c).
* "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
  the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
  is commonly produced by subtraction) look like a single 1-bit
  difference.
* the base values were pseudorandom, all zero but one bit set, or 
  all zero plus a counter that starts at zero.

These constants passed:
 14 11 25 16 4 14 24
 12 14 25 16 4 14 24
and these came close:
  4  8 15 26 3 22 24
 10  8 15 26 3 22 24
 11  8 15 26 3 22 24
-------------------------------------------------------------------------------
*/
#define final(a,b,c) \
{ \
  c ^= b; c -= rot(b,14); \
  a ^= c; a -= rot(c,11); \
  b ^= a; b -= rot(a,25); \
  c ^= b; c -= rot(b,16); \
  a ^= c; a -= rot(c,4);  \
  b ^= a; b -= rot(a,14); \
  c ^= b; c -= rot(b,24); \
}

/*
-------------------------------------------------------------------------------
hashlittle() -- hash a variable-length key into a 32-bit value
  k       : the key (the unaligned variable-length array of bytes)
  length  : the length of the key, counting by bytes
  initval : can be any 4-byte value
Returns a 32-bit value.  Every bit of the key affects every bit of
the return value.  Two keys differing by one or two bits will have
totally different hash values.

The best hash table sizes are powers of 2.  There is no need to do
mod a prime (mod is sooo slow!).  If you need less than 32 bits,
use a bitmask.  For example, if you need only 10 bits, do
  h = (h & hashmask(10));
In which case, the hash table should have hashsize(10) elements.

If you are hashing n strings (uint8_t **)k, do it like this:
  for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h);

By Bob Jenkins, 2006.  bob_jenkins@burtleburtle.net.  You may use this
code any way you wish, private, educational, or commercial.  It's free.

Use for hash table lookup, or anything where one collision in 2^^32 is
acceptable.  Do NOT use for cryptographic purposes.
-------------------------------------------------------------------------------
*/

static uint32_t hashlittle(const void *key, size_t length, uint32_t initval)
{
  uint32_t a,b,c;                                          /* internal state */
  union { const void *ptr; size_t i; } u;     /* needed for Mac Powerbook G4 */

  /* Set up the internal state */
  a = b = c = 0xdeadbeef + ((uint32_t)length) + initval;

  u.ptr = key;
  if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {
    const uint32_t *k = (const uint32_t *)key;         /* read 32-bit chunks */

#ifdef VALGRIND
    const uint8_t  *k8;
#endif

    /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
    while (length > 12)
    {
      a += k[0];
      b += k[1];
      c += k[2];
      mix(a,b,c);
      length -= 12;
      k += 3;
    }

    /*----------------------------- handle the last (probably partial) block */
    /* 
     * "k[2]&0xffffff" actually reads beyond the end of the string, but
     * then masks off the part it's not allowed to read.  Because the
     * string is aligned, the masked-off tail is in the same word as the
     * rest of the string.  Every machine with memory protection I've seen
     * does it on word boundaries, so is OK with this.  But VALGRIND will
     * still catch it and complain.  The masking trick does make the hash
     * noticably faster for short strings (like English words).
     */
#ifndef VALGRIND

    switch(length)
    {
    case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
    case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break;
    case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break;
    case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break;
    case 8 : b+=k[1]; a+=k[0]; break;
    case 7 : b+=k[1]&0xffffff; a+=k[0]; break;
    case 6 : b+=k[1]&0xffff; a+=k[0]; break;
    case 5 : b+=k[1]&0xff; a+=k[0]; break;
    case 4 : a+=k[0]; break;
    case 3 : a+=k[0]&0xffffff; break;
    case 2 : a+=k[0]&0xffff; break;
    case 1 : a+=k[0]&0xff; break;
    case 0 : return c;              /* zero length strings require no mixing */
    }

#else /* make valgrind happy */

    k8 = (const uint8_t *)k;
    switch(length)
    {
    case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
    case 11: c+=((uint32_t)k8[10])<<16;  /* fall through */
    case 10: c+=((uint32_t)k8[9])<<8;    /* fall through */
    case 9 : c+=k8[8];                   /* fall through */
    case 8 : b+=k[1]; a+=k[0]; break;
    case 7 : b+=((uint32_t)k8[6])<<16;   /* fall through */
    case 6 : b+=((uint32_t)k8[5])<<8;    /* fall through */
    case 5 : b+=k8[4];                   /* fall through */
    case 4 : a+=k[0]; break;
    case 3 : a+=((uint32_t)k8[2])<<16;   /* fall through */
    case 2 : a+=((uint32_t)k8[1])<<8;    /* fall through */
    case 1 : a+=k8[0]; break;
    case 0 : return c;
    }

#endif /* !valgrind */

  } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) {
    const uint16_t *k = (const uint16_t *)key;         /* read 16-bit chunks */
    const uint8_t  *k8;

    /*--------------- all but last block: aligned reads and different mixing */
    while (length > 12)
    {
      a += k[0] + (((uint32_t)k[1])<<16);
      b += k[2] + (((uint32_t)k[3])<<16);
      c += k[4] + (((uint32_t)k[5])<<16);
      mix(a,b,c);
      length -= 12;
      k += 6;
    }

    /*----------------------------- handle the last (probably partial) block */
    k8 = (const uint8_t *)k;
    switch(length)
    {
    case 12: c+=k[4]+(((uint32_t)k[5])<<16);
             b+=k[2]+(((uint32_t)k[3])<<16);
             a+=k[0]+(((uint32_t)k[1])<<16);
             break;
    case 11: c+=((uint32_t)k8[10])<<16;     /* fall through */
    case 10: c+=k[4];
             b+=k[2]+(((uint32_t)k[3])<<16);
             a+=k[0]+(((uint32_t)k[1])<<16);
             break;
    case 9 : c+=k8[8];                      /* fall through */
    case 8 : b+=k[2]+(((uint32_t)k[3])<<16);
             a+=k[0]+(((uint32_t)k[1])<<16);
             break;
    case 7 : b+=((uint32_t)k8[6])<<16;      /* fall through */
    case 6 : b+=k[2];
             a+=k[0]+(((uint32_t)k[1])<<16);
             break;
    case 5 : b+=k8[4];                      /* fall through */
    case 4 : a+=k[0]+(((uint32_t)k[1])<<16);
             break;
    case 3 : a+=((uint32_t)k8[2])<<16;      /* fall through */
    case 2 : a+=k[0];
             break;
    case 1 : a+=k8[0];
             break;
    case 0 : return c;                     /* zero length requires no mixing */
    }

  } else {                        /* need to read the key one byte at a time */
    const uint8_t *k = (const uint8_t *)key;

    /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
    while (length > 12)
    {
      a += k[0];
      a += ((uint32_t)k[1])<<8;
      a += ((uint32_t)k[2])<<16;
      a += ((uint32_t)k[3])<<24;
      b += k[4];
      b += ((uint32_t)k[5])<<8;
      b += ((uint32_t)k[6])<<16;
      b += ((uint32_t)k[7])<<24;
      c += k[8];
      c += ((uint32_t)k[9])<<8;
      c += ((uint32_t)k[10])<<16;
      c += ((uint32_t)k[11])<<24;
      mix(a,b,c);
      length -= 12;
      k += 12;
    }

    /*-------------------------------- last block: affect all 32 bits of (c) */
    switch(length)                   /* all the case statements fall through */
    {
    case 12: c+=((uint32_t)k[11])<<24;
    case 11: c+=((uint32_t)k[10])<<16;
    case 10: c+=((uint32_t)k[9])<<8;
    case 9 : c+=k[8];
    case 8 : b+=((uint32_t)k[7])<<24;
    case 7 : b+=((uint32_t)k[6])<<16;
    case 6 : b+=((uint32_t)k[5])<<8;
    case 5 : b+=k[4];
    case 4 : a+=((uint32_t)k[3])<<24;
    case 3 : a+=((uint32_t)k[2])<<16;
    case 2 : a+=((uint32_t)k[1])<<8;
    case 1 : a+=k[0];
             break;
    case 0 : return c;
    }
  }

  final(a,b,c);
  return c;
}
#endif
#ifdef HAVE_STDINT_H
#include <stdint.h>
#endif
#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#ifdef HAVE_STDINT_H
#include <stdint.h>
#endif

extern volatile uint32_t hashtable_seed;


    if (!hashtable_seed) {
        /* Autoseed */
        json_object_seed(0);
    }

    int have_hashseed;
    int hashseed;
        if (!strcmp(line, "HASHSEED")) {
            conf.have_hashseed = 1;
            conf.hashseed = atoi(val);
        } else {
            conf.have_hashseed = 0;
        }
    if (conf.have_hashseed)
        json_object_seed(conf.hashseed);

        flags |= JSON_SORT_KEYS;

    if(getenv("HASHSEED"))
        json_object_seed(getenv_int("HASHSEED"));
    malloc_called = 1;
    free_called = 1;
    if(malloc_called != 1 || free_called != 1)
    int i;
    const char *iter_keys[3];
    int have_key[3] = { 0, 0, 0 };
    json_t *iter_values[3];
    iter_keys[0] = json_object_iter_key(iter);
    iter_values[0] = json_object_iter_value(iter);
    iter_keys[1] = json_object_iter_key(iter);
    iter_values[1] = json_object_iter_value(iter);
    iter_keys[2] = json_object_iter_key(iter);
    iter_values[2] = json_object_iter_value(iter);
    /* Check that keys have correct values */
    for (i = 0; i < 3; i++) {
        if (strcmp(iter_keys[i], "a") == 0) {
            if (iter_values[i] != foo)
                fail("wrong value for iter key a");
            else
                have_key[0] = 1;
        } else if (strcmp(iter_keys[i], "b") == 0) {
            if (iter_values[i] != bar)
                fail("wrong value for iter key b");
            else
                have_key[1] = 1;
        } else if (strcmp(iter_keys[i], "c") == 0) {
            if (iter_values[i] != baz)
                fail("wrong value for iter key c");
            else
                have_key[2] = 1;
        }
    }

    /* Check that we got all keys */
    for(i = 0; i < 3; i++) {
        if(!have_key[i])
            fail("a key wasn't iterated over");
    }

    if(json_object_iter_set(object, iter, baz))
    if(strcmp(json_object_iter_key(iter), "b"))
    if(json_object_iter_value(iter) != baz)
    if(json_object_get(object, "b") != baz)
HASHSEED=1
export JSON_COMPACT HASHSEED
HASHSEED=1
export JSON_INDENT JSON_COMPACT HASHSEED
HASHSEED=1
export JSON_INDENT HASHSEED
HASHSEED=1
export HASHSEED