upstream: import some hacked systemd headers

This brings journal-file data structures and byte swapping
helpers I may as well just reuse.

I've had to do some minor messing about to make things workable in
isolation out of the systemd tree without pulling in too much.

I've also added a new HashedObjectHeader type to encompass the
slightly larger common header components of FieldObject and
DataObject to facilitate a generic hash table iterator that can
operate on just loading HashedObjectHeader when nothing more
than the object size is needed for accounting.  Basically the
HashedObjectHeader is ObjectHeader+hash+next_hash_offset.

9 files changed, 1953 insertions, 0 deletions

diff --git a/src/upstream/_sd-common.h b/src/upstream/_sd-common.h
new file mode 100644
index 0000000..1055b00
--- /dev/null
+++ b/src/upstream/_sd-common.h
@@ -0,0 +1,102 @@
+/* SPDX-License-Identifier: LGPL-2.1+ */
+#ifndef foosdcommonhfoo
+#define foosdcommonhfoo
+
+/***
+  systemd is free software; you can redistribute it and/or modify it
+  under the terms of the GNU Lesser General Public License as published by
+  the Free Software Foundation; either version 2.1 of the License, or
+  (at your option) any later version.
+
+  systemd is distributed in the hope that it will be useful, but
+  WITHOUT ANY WARRANTY; without even the implied warranty of
+  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+  Lesser General Public License for more details.
+
+  You should have received a copy of the GNU Lesser General Public License
+  along with systemd; If not, see <http://www.gnu.org/licenses/>.
+***/
+
+/* This is a private header; never even think of including this directly! */
+
+#if defined(__INCLUDE_LEVEL__) && __INCLUDE_LEVEL__ <= 1 && !defined(__COVERITY__)
+#  error "Do not include _sd-common.h directly; it is a private header."
+#endif
+
+typedef void (*_sd_destroy_t)(void *userdata);
+
+#ifndef _sd_printf_
+#  if __GNUC__ >= 4
+#    define _sd_printf_(a,b) __attribute__((__format__(printf, a, b)))
+#  else
+#    define _sd_printf_(a,b)
+#  endif
+#endif
+
+#ifndef _sd_sentinel_
+#  define _sd_sentinel_ __attribute__((__sentinel__))
+#endif
+
+#ifndef _sd_packed_
+#  define _sd_packed_ __attribute__((__packed__))
+#endif
+
+#ifndef _sd_pure_
+#  define _sd_pure_ __attribute__((__pure__))
+#endif
+
+/* Note that strictly speaking __deprecated__ has been available before GCC 6. However, starting with GCC 6
+ * it also works on enum values, which we are interested in. Since this is a developer-facing feature anyway
+ * (as opposed to build engineer-facing), let's hence conditionalize this to gcc 6, given that the developers
+ * are probably going to use something newer anyway. */
+#ifndef _sd_deprecated_
+#  if __GNUC__ >= 6
+#    define _sd_deprecated_ __attribute__((__deprecated__))
+#  else
+#    define _sd_deprecated_
+#  endif
+#endif
+
+#ifndef _SD_STRINGIFY
+#  define _SD_XSTRINGIFY(x) #x
+#  define _SD_STRINGIFY(x) _SD_XSTRINGIFY(x)
+#endif
+
+#ifndef _SD_BEGIN_DECLARATIONS
+#  ifdef __cplusplus
+#    define _SD_BEGIN_DECLARATIONS                              \
+        extern "C" {                                            \
+        struct _sd_useless_struct_to_allow_trailing_semicolon_
+#  else
+#    define _SD_BEGIN_DECLARATIONS                              \
+        struct _sd_useless_struct_to_allow_trailing_semicolon_
+#  endif
+#endif
+
+#ifndef _SD_END_DECLARATIONS
+#  ifdef __cplusplus
+#    define _SD_END_DECLARATIONS                                \
+        }                                                       \
+        struct _sd_useless_cpp_struct_to_allow_trailing_semicolon_
+#  else
+#    define _SD_END_DECLARATIONS                                \
+        struct _sd_useless_struct_to_allow_trailing_semicolon_
+#  endif
+#endif
+
+#ifndef _SD_ARRAY_STATIC
+#  if __STDC_VERSION__ >= 199901L
+#    define _SD_ARRAY_STATIC static
+#  else
+#    define _SD_ARRAY_STATIC
+#  endif
+#endif
+
+#define _SD_DEFINE_POINTER_CLEANUP_FUNC(type, func)             \
+        static __inline__ void func##p(type **p) {              \
+                if (*p)                                         \
+                        func(*p);                               \
+        }                                                       \
+        struct _sd_useless_struct_to_allow_trailing_semicolon_
+
+#endif
diff --git a/src/upstream/journal-def.h b/src/upstream/journal-def.h
new file mode 100644
index 0000000..29c19d5
--- /dev/null
+++ b/src/upstream/journal-def.h
@@ -0,0 +1,272 @@
+/* SPDX-License-Identifier: LGPL-2.1+ */
+#pragma once
+
+#include "sd-id128.h"
+
+#include "sparse-endian.h"
+
+/* lifted from macro.h */
+#define XCONCATENATE(x, y) x ## y
+#define CONCATENATE(x, y) XCONCATENATE(x, y)
+#define ALIGN64(x) (((x) + 7ULL) & ~7ULL)
+
+#if defined(static_assert)
+#define assert_cc(expr)                                                 \
+        static_assert(expr, #expr)
+#else
+#define assert_cc(expr)                                                 \
+        struct CONCATENATE(_assert_struct_, __COUNTER__) {              \
+                char x[(expr) ? 0 : -1];                                \
+        }
+#endif
+
+#define _packed_ __attribute__((__packed__))
+/* end lift from macro.h */
+
+/*
+ * If you change this file you probably should also change its documentation:
+ *
+ * https://systemd.io/JOURNAL_FILE_FORMAT
+ */
+
+typedef struct Header Header;
+
+typedef struct HashedObjectHeader HashedObjectHeader;
+typedef struct ObjectHeader ObjectHeader;
+typedef union Object Object;
+
+typedef struct DataObject DataObject;
+typedef struct FieldObject FieldObject;
+typedef struct EntryObject EntryObject;
+typedef struct HashTableObject HashTableObject;
+typedef struct EntryArrayObject EntryArrayObject;
+typedef struct TagObject TagObject;
+
+typedef struct EntryItem EntryItem;
+typedef struct HashItem HashItem;
+
+typedef struct FSSHeader FSSHeader;
+
+/* Object types */
+typedef enum ObjectType {
+        OBJECT_UNUSED, /* also serves as "any type" or "additional context" */
+        OBJECT_DATA,
+        OBJECT_FIELD,
+        OBJECT_ENTRY,
+        OBJECT_DATA_HASH_TABLE,
+        OBJECT_FIELD_HASH_TABLE,
+        OBJECT_ENTRY_ARRAY,
+        OBJECT_TAG,
+        _OBJECT_TYPE_MAX
+} ObjectType;
+
+/* Object flags */
+enum {
+        OBJECT_COMPRESSED_XZ   = 1 << 0,
+        OBJECT_COMPRESSED_LZ4  = 1 << 1,
+        OBJECT_COMPRESSED_ZSTD = 1 << 2,
+        OBJECT_COMPRESSION_MASK = (OBJECT_COMPRESSED_XZ | OBJECT_COMPRESSED_LZ4 | OBJECT_COMPRESSED_ZSTD),
+        _OBJECT_COMPRESSED_MAX = OBJECT_COMPRESSION_MASK,
+};
+
+struct ObjectHeader {
+        uint8_t type;
+        uint8_t flags;
+        uint8_t reserved[6];
+        le64_t size;
+        uint8_t payload[];
+} _packed_;
+
+struct HashedObjectHeader {
+        ObjectHeader object;
+        le64_t hash;
+        le64_t next_hash_offset;
+} _packed_;
+
+#define DataObject__contents {                                          \
+        HashedObjectHeader hashed;                                      \
+        le64_t next_field_offset;                                       \
+        le64_t entry_offset; /* the first array entry we store inline */ \
+        le64_t entry_array_offset;                                      \
+        le64_t n_entries;                                               \
+        uint8_t payload[];                                              \
+        }
+
+struct DataObject DataObject__contents;
+struct DataObject__packed DataObject__contents _packed_;
+assert_cc(sizeof(struct DataObject) == sizeof(struct DataObject__packed));
+
+#define FieldObject__contents {                 \
+        HashedObjectHeader hashed;              \
+        le64_t head_data_offset;                \
+        uint8_t payload[];                      \
+}
+
+struct FieldObject FieldObject__contents;
+struct FieldObject__packed FieldObject__contents _packed_;
+assert_cc(sizeof(struct FieldObject) == sizeof(struct FieldObject__packed));
+
+struct EntryItem {
+        le64_t object_offset;
+        le64_t hash;
+} _packed_;
+
+#define EntryObject__contents { \
+        ObjectHeader object;    \
+        le64_t seqnum;          \
+        le64_t realtime;        \
+        le64_t monotonic;       \
+        sd_id128_t boot_id;     \
+        le64_t xor_hash;        \
+        EntryItem items[];      \
+        }
+
+struct EntryObject EntryObject__contents;
+struct EntryObject__packed EntryObject__contents _packed_;
+assert_cc(sizeof(struct EntryObject) == sizeof(struct EntryObject__packed));
+
+struct HashItem {
+        le64_t head_hash_offset;
+        le64_t tail_hash_offset;
+} _packed_;
+
+struct HashTableObject {
+        ObjectHeader object;
+        HashItem items[];
+} _packed_;
+
+struct EntryArrayObject {
+        ObjectHeader object;
+        le64_t next_entry_array_offset;
+        le64_t items[];
+} _packed_;
+
+#define TAG_LENGTH (256/8)
+
+struct TagObject {
+        ObjectHeader object;
+        le64_t seqnum;
+        le64_t epoch;
+        uint8_t tag[TAG_LENGTH]; /* SHA-256 HMAC */
+} _packed_;
+
+union Object {
+        ObjectHeader object;
+        DataObject data;
+        FieldObject field;
+        EntryObject entry;
+        HashTableObject hash_table;
+        EntryArrayObject entry_array;
+        TagObject tag;
+};
+
+typedef enum JournalState {
+        STATE_OFFLINE = 0,
+        STATE_ONLINE = 1,
+        STATE_ARCHIVED = 2,
+        _STATE_MAX
+} JournalState;
+
+/* Header flags */
+enum {
+        HEADER_INCOMPATIBLE_COMPRESSED_XZ   = 1 << 0,
+        HEADER_INCOMPATIBLE_COMPRESSED_LZ4  = 1 << 1,
+        HEADER_INCOMPATIBLE_KEYED_HASH      = 1 << 2,
+        HEADER_INCOMPATIBLE_COMPRESSED_ZSTD = 1 << 3,
+};
+
+#define HEADER_INCOMPATIBLE_ANY               \
+        (HEADER_INCOMPATIBLE_COMPRESSED_XZ |  \
+         HEADER_INCOMPATIBLE_COMPRESSED_LZ4 | \
+         HEADER_INCOMPATIBLE_KEYED_HASH |     \
+         HEADER_INCOMPATIBLE_COMPRESSED_ZSTD)
+
+#if HAVE_XZ && HAVE_LZ4 && HAVE_ZSTD
+#  define HEADER_INCOMPATIBLE_SUPPORTED HEADER_INCOMPATIBLE_ANY
+#elif HAVE_XZ && HAVE_LZ4
+#  define HEADER_INCOMPATIBLE_SUPPORTED (HEADER_INCOMPATIBLE_COMPRESSED_XZ|HEADER_INCOMPATIBLE_COMPRESSED_LZ4|HEADER_INCOMPATIBLE_KEYED_HASH)
+#elif HAVE_XZ && HAVE_ZSTD
+#  define HEADER_INCOMPATIBLE_SUPPORTED (HEADER_INCOMPATIBLE_COMPRESSED_XZ|HEADER_INCOMPATIBLE_COMPRESSED_ZSTD|HEADER_INCOMPATIBLE_KEYED_HASH)
+#elif HAVE_LZ4 && HAVE_ZSTD
+#  define HEADER_INCOMPATIBLE_SUPPORTED (HEADER_INCOMPATIBLE_COMPRESSED_LZ4|HEADER_INCOMPATIBLE_COMPRESSED_ZSTD|HEADER_INCOMPATIBLE_KEYED_HASH)
+#elif HAVE_XZ
+#  define HEADER_INCOMPATIBLE_SUPPORTED (HEADER_INCOMPATIBLE_COMPRESSED_XZ|HEADER_INCOMPATIBLE_KEYED_HASH)
+#elif HAVE_LZ4
+#  define HEADER_INCOMPATIBLE_SUPPORTED (HEADER_INCOMPATIBLE_COMPRESSED_LZ4|HEADER_INCOMPATIBLE_KEYED_HASH)
+#elif HAVE_ZSTD
+#  define HEADER_INCOMPATIBLE_SUPPORTED (HEADER_INCOMPATIBLE_COMPRESSED_ZSTD|HEADER_INCOMPATIBLE_KEYED_HASH)
+#else
+#  define HEADER_INCOMPATIBLE_SUPPORTED HEADER_INCOMPATIBLE_KEYED_HASH
+#endif
+
+enum {
+        HEADER_COMPATIBLE_SEALED = 1 << 0,
+};
+
+#define HEADER_COMPATIBLE_ANY HEADER_COMPATIBLE_SEALED
+#if HAVE_GCRYPT
+#  define HEADER_COMPATIBLE_SUPPORTED HEADER_COMPATIBLE_SEALED
+#else
+#  define HEADER_COMPATIBLE_SUPPORTED 0
+#endif
+
+#define HEADER_SIGNATURE                                                \
+        ((const char[]) { 'L', 'P', 'K', 'S', 'H', 'H', 'R', 'H' })
+
+#define struct_Header__contents {                       \
+        uint8_t signature[8]; /* "LPKSHHRH" */          \
+        le32_t compatible_flags;                        \
+        le32_t incompatible_flags;                      \
+        uint8_t state;                                  \
+        uint8_t reserved[7];                            \
+        sd_id128_t file_id;                             \
+        sd_id128_t machine_id;                          \
+        sd_id128_t boot_id;    /* last writer */        \
+        sd_id128_t seqnum_id;                           \
+        le64_t header_size;                             \
+        le64_t arena_size;                              \
+        le64_t data_hash_table_offset;                  \
+        le64_t data_hash_table_size;                    \
+        le64_t field_hash_table_offset;                 \
+        le64_t field_hash_table_size;                   \
+        le64_t tail_object_offset;                      \
+        le64_t n_objects;                               \
+        le64_t n_entries;                               \
+        le64_t tail_entry_seqnum;                       \
+        le64_t head_entry_seqnum;                       \
+        le64_t entry_array_offset;                      \
+        le64_t head_entry_realtime;                     \
+        le64_t tail_entry_realtime;                     \
+        le64_t tail_entry_monotonic;                    \
+        /* Added in 187 */                              \
+        le64_t n_data;                                  \
+        le64_t n_fields;                                \
+        /* Added in 189 */                              \
+        le64_t n_tags;                                  \
+        le64_t n_entry_arrays;                          \
+        /* Added in 246 */                              \
+        le64_t data_hash_chain_depth;                   \
+        le64_t field_hash_chain_depth;                  \
+        }
+
+struct Header struct_Header__contents;
+struct Header__packed struct_Header__contents _packed_;
+assert_cc(sizeof(struct Header) == sizeof(struct Header__packed));
+assert_cc(sizeof(struct Header) == 256);
+
+#define FSS_HEADER_SIGNATURE                                            \
+        ((const char[]) { 'K', 'S', 'H', 'H', 'R', 'H', 'L', 'P' })
+
+struct FSSHeader {
+        uint8_t signature[8]; /* "KSHHRHLP" */
+        le32_t compatible_flags;
+        le32_t incompatible_flags;
+        sd_id128_t machine_id;
+        sd_id128_t boot_id;    /* last writer */
+        le64_t header_size;
+        le64_t start_usec;
+        le64_t interval_usec;
+        le16_t fsprg_secpar;
+        le16_t reserved[3];
+        le64_t fsprg_state_size;
+} _packed_;
diff --git a/src/upstream/lookup3.c b/src/upstream/lookup3.c
new file mode 100644
index 0000000..74c80b7
--- /dev/null
+++ b/src/upstream/lookup3.c
@@ -0,0 +1,1005 @@
+/* Slightly modified by Lennart Poettering, to avoid name clashes, and
+ * unexport a few functions. */
+
+#include "lookup3.h"
+
+/*
+-------------------------------------------------------------------------------
+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 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.
+-------------------------------------------------------------------------------
+*/
+/* #define SELF_TEST 1 */
+
+#include <stdint.h>     /* defines uint32_t etc */
+#include <stdio.h>      /* defines printf for tests */
+#include <sys/param.h>  /* attempt to define endianness */
+#include <time.h>       /* defines time_t for timings in the test */
+#ifdef linux
+# include <endian.h>    /* attempt to define endianness */
+#endif
+
+#if __GNUC__ >= 7
+_Pragma("GCC diagnostic ignored \"-Wimplicit-fallthrough\"")
+#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); \
+}
+
+/*
+--------------------------------------------------------------------
+ This works on all machines.  To be useful, it requires
+ -- that the key be an array of uint32_t's, and
+ -- that the length be the number of uint32_t's in the key
+
+ The function hashword() is identical to hashlittle() on little-endian
+ machines, and identical to hashbig() on big-endian machines,
+ except that the length has to be measured in uint32_ts rather than in
+ bytes.  hashlittle() is more complicated than hashword() only because
+ hashlittle() has to dance around fitting the key bytes into registers.
+--------------------------------------------------------------------
+*/
+uint32_t jenkins_hashword(
+const uint32_t *k,                   /* the key, an array of uint32_t values */
+size_t          length,               /* the length of the key, in uint32_ts */
+uint32_t        initval)         /* the previous hash, or an arbitrary value */
+{
+  uint32_t a,b,c;
+
+  /* Set up the internal state */
+  a = b = c = 0xdeadbeef + (((uint32_t)length)<<2) + initval;
+
+  /*------------------------------------------------- handle most of the key */
+  while (length > 3)
+  {
+    a += k[0];
+    b += k[1];
+    c += k[2];
+    mix(a,b,c);
+    length -= 3;
+    k += 3;
+  }
+
+  /*------------------------------------------- handle the last 3 uint32_t's */
+  switch(length)                     /* all the case statements fall through */
+  {
+  case 3 : c+=k[2];
+  case 2 : b+=k[1];
+  case 1 : a+=k[0];
+    final(a,b,c);
+  case 0:     /* case 0: nothing left to add */
+    break;
+  }
+  /*------------------------------------------------------ report the result */
+  return c;
+}
+
+/*
+--------------------------------------------------------------------
+hashword2() -- same as hashword(), but take two seeds and return two
+32-bit values.  pc and pb must both be nonnull, and *pc and *pb must
+both be initialized with seeds.  If you pass in (*pb)==0, the output
+(*pc) will be the same as the return value from hashword().
+--------------------------------------------------------------------
+*/
+void jenkins_hashword2 (
+const uint32_t *k,                   /* the key, an array of uint32_t values */
+size_t          length,               /* the length of the key, in uint32_ts */
+uint32_t       *pc,                      /* IN: seed OUT: primary hash value */
+uint32_t       *pb)               /* IN: more seed OUT: secondary hash value */
+{
+  uint32_t a,b,c;
+
+  /* Set up the internal state */
+  a = b = c = 0xdeadbeef + ((uint32_t)(length<<2)) + *pc;
+  c += *pb;
+
+  /*------------------------------------------------- handle most of the key */
+  while (length > 3)
+  {
+    a += k[0];
+    b += k[1];
+    c += k[2];
+    mix(a,b,c);
+    length -= 3;
+    k += 3;
+  }
+
+  /*------------------------------------------- handle the last 3 uint32_t's */
+  switch(length)                     /* all the case statements fall through */
+  {
+  case 3 : c+=k[2];
+  case 2 : b+=k[1];
+  case 1 : a+=k[0];
+    final(a,b,c);
+  case 0:     /* case 0: nothing left to add */
+    break;
+  }
+  /*------------------------------------------------------ report the result */
+  *pc=c; *pb=b;
+}
+
+/*
+-------------------------------------------------------------------------------
+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.
+-------------------------------------------------------------------------------
+*/
+
+uint32_t jenkins_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 */
+
+    /*------ 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
+     * noticeably faster for short strings (like English words).
+     */
+#if !VALGRIND && !HAS_FEATURE_ADDRESS_SANITIZER && !HAS_FEATURE_MEMORY_SANITIZER
+
+    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 */
+    {
+      const uint8_t *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;
+}
+
+/*
+ * hashlittle2: return 2 32-bit hash values
+ *
+ * This is identical to hashlittle(), except it returns two 32-bit hash
+ * values instead of just one.  This is good enough for hash table
+ * lookup with 2^^64 buckets, or if you want a second hash if you're not
+ * happy with the first, or if you want a probably-unique 64-bit ID for
+ * the key.  *pc is better mixed than *pb, so use *pc first.  If you want
+ * a 64-bit value do something like "*pc + (((uint64_t)*pb)<<32)".
+ */
+void jenkins_hashlittle2(
+  const void *key,       /* the key to hash */
+  size_t      length,    /* length of the key */
+  uint32_t   *pc,        /* IN: primary initval, OUT: primary hash */
+  uint32_t   *pb)        /* IN: secondary initval, OUT: secondary hash */
+{
+  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) + *pc;
+  c += *pb;
+
+  u.ptr = key;
+  if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {
+    const uint32_t *k = (const uint32_t *)key;         /* read 32-bit chunks */
+
+    /*------ 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
+     * noticeably faster for short strings (like English words).
+     */
+#if !VALGRIND && !HAS_FEATURE_ADDRESS_SANITIZER && !HAS_FEATURE_MEMORY_SANITIZER
+
+    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 : *pc=c; *pb=b; return;  /* zero length strings require no mixing */
+    }
+
+#else /* make valgrind happy */
+
+    {
+      const uint8_t *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 : *pc=c; *pb=b; return;  /* zero length strings require no mixing */
+      }
+    }
+
+#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 : *pc=c; *pb=b; return;  /* zero length strings require 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 : *pc=c; *pb=b; return;  /* zero length strings require no mixing */
+    }
+  }
+
+  final(a,b,c);
+  *pc=c; *pb=b;
+}
+
+/*
+ * hashbig():
+ * This is the same as hashword() on big-endian machines.  It is different
+ * from hashlittle() on all machines.  hashbig() takes advantage of
+ * big-endian byte ordering.
+ */
+uint32_t jenkins_hashbig( const void *key, size_t length, uint32_t initval)
+{
+  uint32_t a,b,c;
+  union { const void *ptr; size_t i; } u; /* to cast key to (size_t) happily */
+
+  /* Set up the internal state */
+  a = b = c = 0xdeadbeef + ((uint32_t)length) + initval;
+
+  u.ptr = key;
+  if (HASH_BIG_ENDIAN && ((u.i & 0x3) == 0)) {
+    const uint32_t *k = (const uint32_t *)key;         /* read 32-bit chunks */
+
+    /*------ 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]<<8" actually reads beyond the end of the string, but
+     * then shifts out the part it's not allowed to read.  Because the
+     * string is aligned, the illegal read 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
+     * noticeably faster for short strings (like English words).
+     */
+#if !VALGRIND && !HAS_FEATURE_ADDRESS_SANITIZER && !HAS_FEATURE_MEMORY_SANITIZER
+
+    switch(length)
+    {
+    case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
+    case 11: c+=k[2]&0xffffff00; b+=k[1]; a+=k[0]; break;
+    case 10: c+=k[2]&0xffff0000; b+=k[1]; a+=k[0]; break;
+    case 9 : c+=k[2]&0xff000000; b+=k[1]; a+=k[0]; break;
+    case 8 : b+=k[1]; a+=k[0]; break;
+    case 7 : b+=k[1]&0xffffff00; a+=k[0]; break;
+    case 6 : b+=k[1]&0xffff0000; a+=k[0]; break;
+    case 5 : b+=k[1]&0xff000000; a+=k[0]; break;
+    case 4 : a+=k[0]; break;
+    case 3 : a+=k[0]&0xffffff00; break;
+    case 2 : a+=k[0]&0xffff0000; break;
+    case 1 : a+=k[0]&0xff000000; break;
+    case 0 : return c;              /* zero length strings require no mixing */
+    }
+
+#else  /* make valgrind happy */
+
+    {
+      const uint8_t *k8 = (const uint8_t *)k;
+      switch(length)                   /* all the case statements fall through */
+      {
+      case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
+      case 11: c+=((uint32_t)k8[10])<<8;  /* fall through */
+      case 10: c+=((uint32_t)k8[9])<<16;  /* fall through */
+      case 9 : c+=((uint32_t)k8[8])<<24;  /* fall through */
+      case 8 : b+=k[1]; a+=k[0]; break;
+      case 7 : b+=((uint32_t)k8[6])<<8;   /* fall through */
+      case 6 : b+=((uint32_t)k8[5])<<16;  /* fall through */
+      case 5 : b+=((uint32_t)k8[4])<<24;  /* fall through */
+      case 4 : a+=k[0]; break;
+      case 3 : a+=((uint32_t)k8[2])<<8;   /* fall through */
+      case 2 : a+=((uint32_t)k8[1])<<16;  /* fall through */
+      case 1 : a+=((uint32_t)k8[0])<<24; break;
+      case 0 : return c;
+      }
+    }
+
+#endif /* !VALGRIND */
+
+  } 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 += ((uint32_t)k[0])<<24;
+      a += ((uint32_t)k[1])<<16;
+      a += ((uint32_t)k[2])<<8;
+      a += ((uint32_t)k[3]);
+      b += ((uint32_t)k[4])<<24;
+      b += ((uint32_t)k[5])<<16;
+      b += ((uint32_t)k[6])<<8;
+      b += ((uint32_t)k[7]);
+      c += ((uint32_t)k[8])<<24;
+      c += ((uint32_t)k[9])<<16;
+      c += ((uint32_t)k[10])<<8;
+      c += ((uint32_t)k[11]);
+      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+=k[11];
+    case 11: c+=((uint32_t)k[10])<<8;
+    case 10: c+=((uint32_t)k[9])<<16;
+    case 9 : c+=((uint32_t)k[8])<<24;
+    case 8 : b+=k[7];
+    case 7 : b+=((uint32_t)k[6])<<8;
+    case 6 : b+=((uint32_t)k[5])<<16;
+    case 5 : b+=((uint32_t)k[4])<<24;
+    case 4 : a+=k[3];
+    case 3 : a+=((uint32_t)k[2])<<8;
+    case 2 : a+=((uint32_t)k[1])<<16;
+    case 1 : a+=((uint32_t)k[0])<<24;
+             break;
+    case 0 : return c;
+    }
+  }
+
+  final(a,b,c);
+  return c;
+}
+
+#ifdef SELF_TEST
+
+/* used for timings */
+void driver1()
+{
+  uint8_t buf[256];
+  uint32_t i;
+  uint32_t h=0;
+  time_t a,z;
+
+  time(&a);
+  for (i=0; i<256; ++i) buf[i] = 'x';
+  for (i=0; i<1; ++i)
+  {
+    h = hashlittle(&buf[0],1,h);
+  }
+  time(&z);
+  if (z-a > 0) printf("time %d %.8x\n", z-a, h);
+}
+
+/* check that every input bit changes every output bit half the time */
+#define HASHSTATE 1
+#define HASHLEN   1
+#define MAXPAIR 60
+#define MAXLEN  70
+void driver2()
+{
+  uint8_t qa[MAXLEN+1], qb[MAXLEN+2], *a = &qa[0], *b = &qb[1];
+  uint32_t c[HASHSTATE], d[HASHSTATE], i=0, j=0, k, l, m=0, z;
+  uint32_t e[HASHSTATE],f[HASHSTATE],g[HASHSTATE],h[HASHSTATE];
+  uint32_t x[HASHSTATE],y[HASHSTATE];
+  uint32_t hlen;
+
+  printf("No more than %d trials should ever be needed \n",MAXPAIR/2);
+  for (hlen=0; hlen < MAXLEN; ++hlen)
+  {
+    z=0;
+    for (i=0; i<hlen; ++i)  /*----------------------- for each input byte, */
+    {
+      for (j=0; j<8; ++j)   /*------------------------ for each input bit, */
+      {
+        for (m=1; m<8; ++m) /*------------- for several possible initvals, */
+        {
+          for (l=0; l<HASHSTATE; ++l)
+            e[l]=f[l]=g[l]=h[l]=x[l]=y[l]=~((uint32_t)0);
+
+          /*---- check that every output bit is affected by that input bit */
+          for (k=0; k<MAXPAIR; k+=2)
+          {
+            uint32_t finished=1;
+            /* keys have one bit different */
+            for (l=0; l<hlen+1; ++l) {a[l] = b[l] = (uint8_t)0;}
+            /* have a and b be two keys differing in only one bit */
+            a[i] ^= (k<<j);
+            a[i] ^= (k>>(8-j));
+             c[0] = hashlittle(a, hlen, m);
+            b[i] ^= ((k+1)<<j);
+            b[i] ^= ((k+1)>>(8-j));
+             d[0] = hashlittle(b, hlen, m);
+            /* check every bit is 1, 0, set, and not set at least once */
+            for (l=0; l<HASHSTATE; ++l)
+            {
+              e[l] &= (c[l]^d[l]);
+              f[l] &= ~(c[l]^d[l]);
+              g[l] &= c[l];
+              h[l] &= ~c[l];
+              x[l] &= d[l];
+              y[l] &= ~d[l];
+              if (e[l]|f[l]|g[l]|h[l]|x[l]|y[l]) finished=0;
+            }
+            if (finished) break;
+          }
+          if (k>z) z=k;
+          if (k==MAXPAIR)
+          {
+             printf("Some bit didn't change: ");
+             printf("%.8x %.8x %.8x %.8x %.8x %.8x  ",
+                    e[0],f[0],g[0],h[0],x[0],y[0]);
+             printf("i %d j %d m %d len %d\n", i, j, m, hlen);
+          }
+          if (z==MAXPAIR) goto done;
+        }
+      }
+    }
+   done:
+    if (z < MAXPAIR)
+    {
+      printf("Mix success  %2d bytes  %2d initvals  ",i,m);
+      printf("required  %d  trials\n", z/2);
+    }
+  }
+  printf("\n");
+}
+
+/* Check for reading beyond the end of the buffer and alignment problems */
+void driver3()
+{
+  uint8_t buf[MAXLEN+20], *b;
+  uint32_t len;
+  uint8_t q[] = "This is the time for all good men to come to the aid of their country...";
+  uint32_t h;
+  uint8_t qq[] = "xThis is the time for all good men to come to the aid of their country...";
+  uint32_t i;
+  uint8_t qqq[] = "xxThis is the time for all good men to come to the aid of their country...";
+  uint32_t j;
+  uint8_t qqqq[] = "xxxThis is the time for all good men to come to the aid of their country...";
+  uint32_t ref,x,y;
+  uint8_t *p;
+
+  printf("Endianness.  These lines should all be the same (for values filled in):\n");
+  printf("%.8x                            %.8x                            %.8x\n",
+         hashword((const uint32_t *)q, (sizeof(q)-1)/4, 13),
+         hashword((const uint32_t *)q, (sizeof(q)-5)/4, 13),
+         hashword((const uint32_t *)q, (sizeof(q)-9)/4, 13));
+  p = q;
+  printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
+         hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
+         hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
+         hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
+         hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
+         hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
+         hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
+  p = &qq[1];
+  printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
+         hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
+         hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
+         hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
+         hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
+         hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
+         hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
+  p = &qqq[2];
+  printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
+         hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
+         hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
+         hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
+         hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
+         hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
+         hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
+  p = &qqqq[3];
+  printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
+         hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
+         hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
+         hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
+         hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
+         hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
+         hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
+  printf("\n");
+
+  /* check that hashlittle2 and hashlittle produce the same results */
+  i=47; j=0;
+  hashlittle2(q, sizeof(q), &i, &j);
+  if (hashlittle(q, sizeof(q), 47) != i)
+    printf("hashlittle2 and hashlittle mismatch\n");
+
+  /* check that hashword2 and hashword produce the same results */
+  len = 0xdeadbeef;
+  i=47, j=0;
+  hashword2(&len, 1, &i, &j);
+  if (hashword(&len, 1, 47) != i)
+    printf("hashword2 and hashword mismatch %x %x\n",
+           i, hashword(&len, 1, 47));
+
+  /* check hashlittle doesn't read before or after the ends of the string */
+  for (h=0, b=buf+1; h<8; ++h, ++b)
+  {
+    for (i=0; i<MAXLEN; ++i)
+    {
+      len = i;
+      for (j=0; j<i; ++j) *(b+j)=0;
+
+      /* these should all be equal */
+      ref = hashlittle(b, len, (uint32_t)1);
+      *(b+i)=(uint8_t)~0;
+      *(b-1)=(uint8_t)~0;
+      x = hashlittle(b, len, (uint32_t)1);
+      y = hashlittle(b, len, (uint32_t)1);
+      if ((ref != x) || (ref != y))
+      {
+        printf("alignment error: %.8x %.8x %.8x %d %d\n",ref,x,y,
+               h, i);
+      }
+    }
+  }
+}
+
+/* check for problems with nulls */
+ void driver4()
+{
+  uint8_t buf[1];
+  uint32_t h,i,state[HASHSTATE];
+
+  buf[0] = ~0;
+  for (i=0; i<HASHSTATE; ++i) state[i] = 1;
+  printf("These should all be different\n");
+  for (i=0, h=0; i<8; ++i)
+  {
+    h = hashlittle(buf, 0, h);
+    printf("%2ld  0-byte strings, hash is  %.8x\n", i, h);
+  }
+}
+
+void driver5()
+{
+  uint32_t b,c;
+  b=0, c=0, hashlittle2("", 0, &c, &b);
+  printf("hash is %.8lx %.8lx\n", c, b);   /* deadbeef deadbeef */
+  b=0xdeadbeef, c=0, hashlittle2("", 0, &c, &b);
+  printf("hash is %.8lx %.8lx\n", c, b);   /* bd5b7dde deadbeef */
+  b=0xdeadbeef, c=0xdeadbeef, hashlittle2("", 0, &c, &b);
+  printf("hash is %.8lx %.8lx\n", c, b);   /* 9c093ccd bd5b7dde */
+  b=0, c=0, hashlittle2("Four score and seven years ago", 30, &c, &b);
+  printf("hash is %.8lx %.8lx\n", c, b);   /* 17770551 ce7226e6 */
+  b=1, c=0, hashlittle2("Four score and seven years ago", 30, &c, &b);
+  printf("hash is %.8lx %.8lx\n", c, b);   /* e3607cae bd371de4 */
+  b=0, c=1, hashlittle2("Four score and seven years ago", 30, &c, &b);
+  printf("hash is %.8lx %.8lx\n", c, b);   /* cd628161 6cbea4b3 */
+  c = hashlittle("Four score and seven years ago", 30, 0);
+  printf("hash is %.8lx\n", c);   /* 17770551 */
+  c = hashlittle("Four score and seven years ago", 30, 1);
+  printf("hash is %.8lx\n", c);   /* cd628161 */
+}
+
+int main()
+{
+  driver1();   /* test that the key is hashed: used for timings */
+  driver2();   /* test that whole key is hashed thoroughly */
+  driver3();   /* test that nothing but the key is hashed */
+  driver4();   /* test hashing multiple buffers (all buffers are null) */
+  driver5();   /* test the hash against known vectors */
+  return 1;
+}
+
+#endif  /* SELF_TEST */
diff --git a/src/upstream/lookup3.h b/src/upstream/lookup3.h
new file mode 100644
index 0000000..ce8a468
--- /dev/null
+++ b/src/upstream/lookup3.h
@@ -0,0 +1,20 @@
+#pragma once
+
+#include <inttypes.h>
+#include <sys/types.h>
+
+uint32_t jenkins_hashword(const uint32_t *k, size_t length, uint32_t initval);
+void jenkins_hashword2(const uint32_t *k, size_t length, uint32_t *pc, uint32_t *pb);
+
+uint32_t jenkins_hashlittle(const void *key, size_t length, uint32_t initval);
+void jenkins_hashlittle2(const void *key, size_t length, uint32_t *pc, uint32_t *pb);
+
+uint32_t jenkins_hashbig(const void *key, size_t length, uint32_t initval);
+
+static inline uint64_t jenkins_hash64(const void *data, size_t length) {
+        uint32_t a = 0, b = 0;
+
+        jenkins_hashlittle2(data, length, &a, &b);
+
+        return ((uint64_t) a << 32ULL) | (uint64_t) b;
+}
diff --git a/src/upstream/sd-id128.h b/src/upstream/sd-id128.h
new file mode 100644
index 0000000..9b00b76
--- /dev/null
+++ b/src/upstream/sd-id128.h
@@ -0,0 +1,124 @@
+/* SPDX-License-Identifier: LGPL-2.1+ */
+#ifndef foosdid128hfoo
+#define foosdid128hfoo
+
+/***
+  systemd is free software; you can redistribute it and/or modify it
+  under the terms of the GNU Lesser General Public License as published by
+  the Free Software Foundation; either version 2.1 of the License, or
+  (at your option) any later version.
+
+  systemd is distributed in the hope that it will be useful, but
+  WITHOUT ANY WARRANTY; without even the implied warranty of
+  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+  Lesser General Public License for more details.
+
+  You should have received a copy of the GNU Lesser General Public License
+  along with systemd; If not, see <http://www.gnu.org/licenses/>.
+***/
+
+#include <inttypes.h>
+#include <string.h>
+
+#include "_sd-common.h"
+
+_SD_BEGIN_DECLARATIONS;
+
+/* 128-bit ID APIs. See sd-id128(3) for more information. */
+
+typedef union sd_id128 sd_id128_t;
+
+union sd_id128 {
+        uint8_t bytes[16];
+        uint64_t qwords[2];
+};
+
+#define SD_ID128_STRING_MAX 33
+
+char *sd_id128_to_string(sd_id128_t id, char s[_SD_ARRAY_STATIC SD_ID128_STRING_MAX]);
+int sd_id128_from_string(const char *s, sd_id128_t *ret);
+
+int sd_id128_randomize(sd_id128_t *ret);
+
+int sd_id128_get_machine(sd_id128_t *ret);
+int sd_id128_get_boot(sd_id128_t *ret);
+int sd_id128_get_invocation(sd_id128_t *ret);
+
+int sd_id128_get_machine_app_specific(sd_id128_t app_id, sd_id128_t *ret);
+int sd_id128_get_boot_app_specific(sd_id128_t app_id, sd_id128_t *ret);
+
+#define SD_ID128_ARRAY(v0, v1, v2, v3, v4, v5, v6, v7, v8, v9, v10, v11, v12, v13, v14, v15) \
+        { .bytes = { 0x##v0, 0x##v1, 0x##v2, 0x##v3, 0x##v4, 0x##v5, 0x##v6, 0x##v7, \
+                     0x##v8, 0x##v9, 0x##v10, 0x##v11, 0x##v12, 0x##v13, 0x##v14, 0x##v15 }}
+
+#define SD_ID128_MAKE(v0, v1, v2, v3, v4, v5, v6, v7, v8, v9, v10, v11, v12, v13, v14, v15) \
+        ((const sd_id128_t) SD_ID128_ARRAY(v0, v1, v2, v3, v4, v5, v6, v7, v8, v9, v10, v11, v12, v13, v14, v15))
+
+/* Note that SD_ID128_FORMAT_VAL will evaluate the passed argument 16
+ * times. It is hence not a good idea to call this macro with an
+ * expensive function as parameter or an expression with side
+ * effects */
+
+#define SD_ID128_FORMAT_STR "%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x"
+#define SD_ID128_FORMAT_VAL(x) (x).bytes[0], (x).bytes[1], (x).bytes[2], (x).bytes[3], (x).bytes[4], (x).bytes[5], (x).bytes[6], (x).bytes[7], (x).bytes[8], (x).bytes[9], (x).bytes[10], (x).bytes[11], (x).bytes[12], (x).bytes[13], (x).bytes[14], (x).bytes[15]
+
+/* Like SD_ID128_FORMAT_STR, but formats as UUID, not in plain format */
+#define SD_ID128_UUID_FORMAT_STR "%02x%02x%02x%02x-%02x%02x-%02x%02x-%02x%02x-%02x%02x%02x%02x%02x%02x"
+
+#define SD_ID128_CONST_STR(x)                                           \
+        ((const char[SD_ID128_STRING_MAX]) {                            \
+                ((x).bytes[0] >> 4) >= 10 ? 'a' + ((x).bytes[0] >> 4) - 10 : '0' + ((x).bytes[0] >> 4), \
+                ((x).bytes[0] & 15) >= 10 ? 'a' + ((x).bytes[0] & 15) - 10 : '0' + ((x).bytes[0] & 15), \
+                ((x).bytes[1] >> 4) >= 10 ? 'a' + ((x).bytes[1] >> 4) - 10 : '0' + ((x).bytes[1] >> 4), \
+                ((x).bytes[1] & 15) >= 10 ? 'a' + ((x).bytes[1] & 15) - 10 : '0' + ((x).bytes[1] & 15), \
+                ((x).bytes[2] >> 4) >= 10 ? 'a' + ((x).bytes[2] >> 4) - 10 : '0' + ((x).bytes[2] >> 4), \
+                ((x).bytes[2] & 15) >= 10 ? 'a' + ((x).bytes[2] & 15) - 10 : '0' + ((x).bytes[2] & 15), \
+                ((x).bytes[3] >> 4) >= 10 ? 'a' + ((x).bytes[3] >> 4) - 10 : '0' + ((x).bytes[3] >> 4), \
+                ((x).bytes[3] & 15) >= 10 ? 'a' + ((x).bytes[3] & 15) - 10 : '0' + ((x).bytes[3] & 15), \
+                ((x).bytes[4] >> 4) >= 10 ? 'a' + ((x).bytes[4] >> 4) - 10 : '0' + ((x).bytes[4] >> 4), \
+                ((x).bytes[4] & 15) >= 10 ? 'a' + ((x).bytes[4] & 15) - 10 : '0' + ((x).bytes[4] & 15), \
+                ((x).bytes[5] >> 4) >= 10 ? 'a' + ((x).bytes[5] >> 4) - 10 : '0' + ((x).bytes[5] >> 4), \
+                ((x).bytes[5] & 15) >= 10 ? 'a' + ((x).bytes[5] & 15) - 10 : '0' + ((x).bytes[5] & 15), \
+                ((x).bytes[6] >> 4) >= 10 ? 'a' + ((x).bytes[6] >> 4) - 10 : '0' + ((x).bytes[6] >> 4), \
+                ((x).bytes[6] & 15) >= 10 ? 'a' + ((x).bytes[6] & 15) - 10 : '0' + ((x).bytes[6] & 15), \
+                ((x).bytes[7] >> 4) >= 10 ? 'a' + ((x).bytes[7] >> 4) - 10 : '0' + ((x).bytes[7] >> 4), \
+                ((x).bytes[7] & 15) >= 10 ? 'a' + ((x).bytes[7] & 15) - 10 : '0' + ((x).bytes[7] & 15), \
+                ((x).bytes[8] >> 4) >= 10 ? 'a' + ((x).bytes[8] >> 4) - 10 : '0' + ((x).bytes[8] >> 4), \
+                ((x).bytes[8] & 15) >= 10 ? 'a' + ((x).bytes[8] & 15) - 10 : '0' + ((x).bytes[8] & 15), \
+                ((x).bytes[9] >> 4) >= 10 ? 'a' + ((x).bytes[9] >> 4) - 10 : '0' + ((x).bytes[9] >> 4), \
+                ((x).bytes[9] & 15) >= 10 ? 'a' + ((x).bytes[9] & 15) - 10 : '0' + ((x).bytes[9] & 15), \
+                ((x).bytes[10] >> 4) >= 10 ? 'a' + ((x).bytes[10] >> 4) - 10 : '0' + ((x).bytes[10] >> 4), \
+                ((x).bytes[10] & 15) >= 10 ? 'a' + ((x).bytes[10] & 15) - 10 : '0' + ((x).bytes[10] & 15), \
+                ((x).bytes[11] >> 4) >= 10 ? 'a' + ((x).bytes[11] >> 4) - 10 : '0' + ((x).bytes[11] >> 4), \
+                ((x).bytes[11] & 15) >= 10 ? 'a' + ((x).bytes[11] & 15) - 10 : '0' + ((x).bytes[11] & 15), \
+                ((x).bytes[12] >> 4) >= 10 ? 'a' + ((x).bytes[12] >> 4) - 10 : '0' + ((x).bytes[12] >> 4), \
+                ((x).bytes[12] & 15) >= 10 ? 'a' + ((x).bytes[12] & 15) - 10 : '0' + ((x).bytes[12] & 15), \
+                ((x).bytes[13] >> 4) >= 10 ? 'a' + ((x).bytes[13] >> 4) - 10 : '0' + ((x).bytes[13] >> 4), \
+                ((x).bytes[13] & 15) >= 10 ? 'a' + ((x).bytes[13] & 15) - 10 : '0' + ((x).bytes[13] & 15), \
+                ((x).bytes[14] >> 4) >= 10 ? 'a' + ((x).bytes[14] >> 4) - 10 : '0' + ((x).bytes[14] >> 4), \
+                ((x).bytes[14] & 15) >= 10 ? 'a' + ((x).bytes[14] & 15) - 10 : '0' + ((x).bytes[14] & 15), \
+                ((x).bytes[15] >> 4) >= 10 ? 'a' + ((x).bytes[15] >> 4) - 10 : '0' + ((x).bytes[15] >> 4), \
+                ((x).bytes[15] & 15) >= 10 ? 'a' + ((x).bytes[15] & 15) - 10 : '0' + ((x).bytes[15] & 15), \
+                0 })
+
+#define SD_ID128_MAKE_STR(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p) \
+        #a #b #c #d #e #f #g #h #i #j #k #l #m #n #o #p
+
+_sd_pure_ static __inline__ int sd_id128_equal(sd_id128_t a, sd_id128_t b) {
+        return memcmp(&a, &b, 16) == 0;
+}
+
+_sd_pure_ static __inline__ int sd_id128_is_null(sd_id128_t a) {
+        return a.qwords[0] == 0 && a.qwords[1] == 0;
+}
+
+_sd_pure_ static __inline__ int sd_id128_is_allf(sd_id128_t a) {
+        return a.qwords[0] == UINT64_C(0xFFFFFFFFFFFFFFFF) && a.qwords[1] == UINT64_C(0xFFFFFFFFFFFFFFFF);
+}
+
+#define SD_ID128_NULL ((const sd_id128_t) { .qwords = { 0, 0 }})
+#define SD_ID128_ALLF ((const sd_id128_t) { .qwords = { UINT64_C(0xFFFFFFFFFFFFFFFF), UINT64_C(0xFFFFFFFFFFFFFFFF) }})
+
+_SD_END_DECLARATIONS;
+
+#endif
diff --git a/src/upstream/siphash24.c b/src/upstream/siphash24.c
new file mode 100644
index 0000000..1fb9393
--- /dev/null
+++ b/src/upstream/siphash24.c
@@ -0,0 +1,200 @@
+/*
+   SipHash reference C implementation
+
+   Written in 2012 by
+   Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com>
+   Daniel J. Bernstein <djb@cr.yp.to>
+
+   To the extent possible under law, the author(s) have dedicated all copyright
+   and related and neighboring rights to this software to the public domain
+   worldwide. This software is distributed without any warranty.
+
+   You should have received a copy of the CC0 Public Domain Dedication along with
+   this software. If not, see <http://creativecommons.org/publicdomain/zero/1.0/>.
+
+   (Minimal changes made by Lennart Poettering, to make clean for inclusion in systemd)
+   (Refactored by Tom Gundersen to split up in several functions and follow systemd
+    coding style)
+*/
+
+#include <assert.h>
+#include <stdio.h>
+
+#include "siphash24.h"
+#include "unaligned.h"
+
+static uint64_t rotate_left(uint64_t x, uint8_t b) {
+        assert(b < 64);
+
+        return (x << b) | (x >> (64 - b));
+}
+
+static void sipround(struct siphash *state) {
+        assert(state);
+
+        state->v0 += state->v1;
+        state->v1 = rotate_left(state->v1, 13);
+        state->v1 ^= state->v0;
+        state->v0 = rotate_left(state->v0, 32);
+        state->v2 += state->v3;
+        state->v3 = rotate_left(state->v3, 16);
+        state->v3 ^= state->v2;
+        state->v0 += state->v3;
+        state->v3 = rotate_left(state->v3, 21);
+        state->v3 ^= state->v0;
+        state->v2 += state->v1;
+        state->v1 = rotate_left(state->v1, 17);
+        state->v1 ^= state->v2;
+        state->v2 = rotate_left(state->v2, 32);
+}
+
+void siphash24_init(struct siphash *state, const uint8_t k[static 16]) {
+        uint64_t k0, k1;
+
+        assert(state);
+        assert(k);
+
+        k0 = unaligned_read_le64(k);
+        k1 = unaligned_read_le64(k + 8);
+
+        *state = (struct siphash) {
+                /* "somepseudorandomlygeneratedbytes" */
+                .v0 = 0x736f6d6570736575ULL ^ k0,
+                .v1 = 0x646f72616e646f6dULL ^ k1,
+                .v2 = 0x6c7967656e657261ULL ^ k0,
+                .v3 = 0x7465646279746573ULL ^ k1,
+                .padding = 0,
+                .inlen = 0,
+        };
+}
+
+void siphash24_compress(const void *_in, size_t inlen, struct siphash *state) {
+
+        const uint8_t *in = _in;
+        const uint8_t *end = in + inlen;
+        size_t left = state->inlen & 7;
+        uint64_t m;
+
+        assert(in);
+        assert(state);
+
+        /* Update total length */
+        state->inlen += inlen;
+
+        /* If padding exists, fill it out */
+        if (left > 0) {
+                for ( ; in < end && left < 8; in ++, left ++)
+                        state->padding |= ((uint64_t) *in) << (left * 8);
+
+                if (in == end && left < 8)
+                        /* We did not have enough input to fill out the padding completely */
+                        return;
+
+#if ENABLE_DEBUG_SIPHASH
+                printf("(%3zu) v0 %08x %08x\n", state->inlen, (uint32_t) (state->v0 >> 32), (uint32_t) state->v0);
+                printf("(%3zu) v1 %08x %08x\n", state->inlen, (uint32_t) (state->v1 >> 32), (uint32_t) state->v1);
+                printf("(%3zu) v2 %08x %08x\n", state->inlen, (uint32_t) (state->v2 >> 32), (uint32_t) state->v2);
+                printf("(%3zu) v3 %08x %08x\n", state->inlen, (uint32_t) (state->v3 >> 32), (uint32_t) state->v3);
+                printf("(%3zu) compress padding %08x %08x\n", state->inlen, (uint32_t) (state->padding >> 32), (uint32_t)state->padding);
+#endif
+
+                state->v3 ^= state->padding;
+                sipround(state);
+                sipround(state);
+                state->v0 ^= state->padding;
+
+                state->padding = 0;
+        }
+
+        end -= (state->inlen % sizeof(uint64_t));
+
+        for ( ; in < end; in += 8) {
+                m = unaligned_read_le64(in);
+#if ENABLE_DEBUG_SIPHASH
+                printf("(%3zu) v0 %08x %08x\n", state->inlen, (uint32_t) (state->v0 >> 32), (uint32_t) state->v0);
+                printf("(%3zu) v1 %08x %08x\n", state->inlen, (uint32_t) (state->v1 >> 32), (uint32_t) state->v1);
+                printf("(%3zu) v2 %08x %08x\n", state->inlen, (uint32_t) (state->v2 >> 32), (uint32_t) state->v2);
+                printf("(%3zu) v3 %08x %08x\n", state->inlen, (uint32_t) (state->v3 >> 32), (uint32_t) state->v3);
+                printf("(%3zu) compress %08x %08x\n", state->inlen, (uint32_t) (m >> 32), (uint32_t) m);
+#endif
+                state->v3 ^= m;
+                sipround(state);
+                sipround(state);
+                state->v0 ^= m;
+        }
+
+        left = state->inlen & 7;
+        switch (left) {
+                case 7:
+                        state->padding |= ((uint64_t) in[6]) << 48;
+                        _fallthrough_;
+                case 6:
+                        state->padding |= ((uint64_t) in[5]) << 40;
+                        _fallthrough_;
+                case 5:
+                        state->padding |= ((uint64_t) in[4]) << 32;
+                        _fallthrough_;
+                case 4:
+                        state->padding |= ((uint64_t) in[3]) << 24;
+                        _fallthrough_;
+                case 3:
+                        state->padding |= ((uint64_t) in[2]) << 16;
+                        _fallthrough_;
+                case 2:
+                        state->padding |= ((uint64_t) in[1]) <<  8;
+                        _fallthrough_;
+                case 1:
+                        state->padding |= ((uint64_t) in[0]);
+                        _fallthrough_;
+                case 0:
+                        break;
+        }
+}
+
+uint64_t siphash24_finalize(struct siphash *state) {
+        uint64_t b;
+
+        assert(state);
+
+        b = state->padding | (((uint64_t) state->inlen) << 56);
+
+#if ENABLE_DEBUG_SIPHASH
+        printf("(%3zu) v0 %08x %08x\n", state->inlen, (uint32_t) (state->v0 >> 32), (uint32_t) state->v0);
+        printf("(%3zu) v1 %08x %08x\n", state->inlen, (uint32_t) (state->v1 >> 32), (uint32_t) state->v1);
+        printf("(%3zu) v2 %08x %08x\n", state->inlen, (uint32_t) (state->v2 >> 32), (uint32_t) state->v2);
+        printf("(%3zu) v3 %08x %08x\n", state->inlen, (uint32_t) (state->v3 >> 32), (uint32_t) state->v3);
+        printf("(%3zu) padding   %08x %08x\n", state->inlen, (uint32_t) (state->padding >> 32), (uint32_t) state->padding);
+#endif
+
+        state->v3 ^= b;
+        sipround(state);
+        sipround(state);
+        state->v0 ^= b;
+
+#if ENABLE_DEBUG_SIPHASH
+        printf("(%3zu) v0 %08x %08x\n", state->inlen, (uint32_t) (state->v0 >> 32), (uint32_t) state->v0);
+        printf("(%3zu) v1 %08x %08x\n", state->inlen, (uint32_t) (state->v1 >> 32), (uint32_t) state->v1);
+        printf("(%3zu) v2 %08x %08x\n", state->inlen, (uint32_t) (state->v2 >> 32), (uint32_t) state->v2);
+        printf("(%3zu) v3 %08x %08x\n", state->inlen, (uint32_t) (state->v3 >> 32), (uint32_t) state->v3);
+#endif
+        state->v2 ^= 0xff;
+
+        sipround(state);
+        sipround(state);
+        sipround(state);
+        sipround(state);
+
+        return state->v0 ^ state->v1 ^ state->v2  ^ state->v3;
+}
+
+uint64_t siphash24(const void *in, size_t inlen, const uint8_t k[static 16]) {
+        struct siphash state;
+
+        assert(in);
+        assert(k);
+
+        siphash24_init(&state, k);
+        siphash24_compress(in, inlen, &state);
+
+        return siphash24_finalize(&state);
+}
diff --git a/src/upstream/siphash24.h b/src/upstream/siphash24.h
new file mode 100644
index 0000000..7f799ed
--- /dev/null
+++ b/src/upstream/siphash24.h
@@ -0,0 +1,41 @@
+#pragma once
+
+#include <inttypes.h>
+#include <stddef.h>
+#include <stdint.h>
+#include <string.h>
+#include <sys/types.h>
+
+struct siphash {
+        uint64_t v0;
+        uint64_t v1;
+        uint64_t v2;
+        uint64_t v3;
+        uint64_t padding;
+        size_t inlen;
+};
+
+void siphash24_init(struct siphash *state, const uint8_t k[static 16]);
+void siphash24_compress(const void *in, size_t inlen, struct siphash *state);
+#define siphash24_compress_byte(byte, state) siphash24_compress((const uint8_t[]) { (byte) }, 1, (state))
+
+static inline void siphash24_compress_boolean(bool in, struct siphash *state) {
+        uint8_t i = in;
+
+        siphash24_compress(&i, sizeof i, state);
+}
+
+static inline void siphash24_compress_string(const char *in, struct siphash *state) {
+        if (!in)
+                return;
+
+        siphash24_compress(in, strlen(in), state);
+}
+
+uint64_t siphash24_finalize(struct siphash *state);
+
+uint64_t siphash24(const void *in, size_t inlen, const uint8_t k[static 16]);
+
+static inline uint64_t siphash24_string(const char *s, const uint8_t k[static 16]) {
+        return siphash24(s, strlen(s) + 1, k);
+}
diff --git a/src/upstream/sparse-endian.h b/src/upstream/sparse-endian.h
new file mode 100644
index 0000000..9583dda
--- /dev/null
+++ b/src/upstream/sparse-endian.h
@@ -0,0 +1,90 @@
+/* SPDX-License-Identifier: MIT
+ *
+ * Copyright (c) 2012 Josh Triplett <josh@joshtriplett.org>
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to
+ * deal in the Software without restriction, including without limitation the
+ * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
+ * sell copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
+ * IN THE SOFTWARE.
+ */
+#pragma once
+
+#include <byteswap.h>
+#include <endian.h>
+#include <stdint.h>
+
+#ifdef __CHECKER__
+#define __sd_bitwise __attribute__((__bitwise__))
+#define __sd_force __attribute__((__force__))
+#else
+#define __sd_bitwise
+#define __sd_force
+#endif
+
+typedef uint16_t __sd_bitwise le16_t;
+typedef uint16_t __sd_bitwise be16_t;
+typedef uint32_t __sd_bitwise le32_t;
+typedef uint32_t __sd_bitwise be32_t;
+typedef uint64_t __sd_bitwise le64_t;
+typedef uint64_t __sd_bitwise be64_t;
+
+#undef htobe16
+#undef htole16
+#undef be16toh
+#undef le16toh
+#undef htobe32
+#undef htole32
+#undef be32toh
+#undef le32toh
+#undef htobe64
+#undef htole64
+#undef be64toh
+#undef le64toh
+
+#if __BYTE_ORDER == __LITTLE_ENDIAN
+#define bswap_16_on_le(x) __bswap_16(x)
+#define bswap_32_on_le(x) __bswap_32(x)
+#define bswap_64_on_le(x) __bswap_64(x)
+#define bswap_16_on_be(x) (x)
+#define bswap_32_on_be(x) (x)
+#define bswap_64_on_be(x) (x)
+#elif __BYTE_ORDER == __BIG_ENDIAN
+#define bswap_16_on_le(x) (x)
+#define bswap_32_on_le(x) (x)
+#define bswap_64_on_le(x) (x)
+#define bswap_16_on_be(x) __bswap_16(x)
+#define bswap_32_on_be(x) __bswap_32(x)
+#define bswap_64_on_be(x) __bswap_64(x)
+#endif
+
+static inline le16_t htole16(uint16_t value) { return (le16_t __sd_force) bswap_16_on_be(value); }
+static inline le32_t htole32(uint32_t value) { return (le32_t __sd_force) bswap_32_on_be(value); }
+static inline le64_t htole64(uint64_t value) { return (le64_t __sd_force) bswap_64_on_be(value); }
+
+static inline be16_t htobe16(uint16_t value) { return (be16_t __sd_force) bswap_16_on_le(value); }
+static inline be32_t htobe32(uint32_t value) { return (be32_t __sd_force) bswap_32_on_le(value); }
+static inline be64_t htobe64(uint64_t value) { return (be64_t __sd_force) bswap_64_on_le(value); }
+
+static inline uint16_t le16toh(le16_t value) { return bswap_16_on_be((uint16_t __sd_force)value); }
+static inline uint32_t le32toh(le32_t value) { return bswap_32_on_be((uint32_t __sd_force)value); }
+static inline uint64_t le64toh(le64_t value) { return bswap_64_on_be((uint64_t __sd_force)value); }
+
+static inline uint16_t be16toh(be16_t value) { return bswap_16_on_le((uint16_t __sd_force)value); }
+static inline uint32_t be32toh(be32_t value) { return bswap_32_on_le((uint32_t __sd_force)value); }
+static inline uint64_t be64toh(be64_t value) { return bswap_64_on_le((uint64_t __sd_force)value); }
+
+#undef __sd_bitwise
+#undef __sd_force
diff --git a/src/upstream/unaligned.h b/src/upstream/unaligned.h
new file mode 100644
index 0000000..00c17f8
--- /dev/null
+++ b/src/upstream/unaligned.h
@@ -0,0 +1,99 @@
+/* SPDX-License-Identifier: LGPL-2.1+ */
+#pragma once
+
+#include <endian.h>
+#include <stdint.h>
+
+/* BE */
+
+static inline uint16_t unaligned_read_be16(const void *_u) {
+        const struct __attribute__((__packed__, __may_alias__)) { uint16_t x; } *u = _u;
+
+        return be16toh(u->x);
+}
+
+static inline uint32_t unaligned_read_be32(const void *_u) {
+        const struct __attribute__((__packed__, __may_alias__)) { uint32_t x; } *u = _u;
+
+        return be32toh(u->x);
+}
+
+static inline uint64_t unaligned_read_be64(const void *_u) {
+        const struct __attribute__((__packed__, __may_alias__)) { uint64_t x; } *u = _u;
+
+        return be64toh(u->x);
+}
+
+static inline void unaligned_write_be16(void *_u, uint16_t a) {
+        struct __attribute__((__packed__, __may_alias__)) { uint16_t x; } *u = _u;
+
+        u->x = be16toh(a);
+}
+
+static inline void unaligned_write_be32(void *_u, uint32_t a) {
+        struct __attribute__((__packed__, __may_alias__)) { uint32_t x; } *u = _u;
+
+        u->x = be32toh(a);
+}
+
+static inline void unaligned_write_be64(void *_u, uint64_t a) {
+        struct __attribute__((__packed__, __may_alias__)) { uint64_t x; } *u = _u;
+
+        u->x = be64toh(a);
+}
+
+/* LE */
+
+static inline uint16_t unaligned_read_le16(const void *_u) {
+        const struct __attribute__((__packed__, __may_alias__)) { uint16_t x; } *u = _u;
+
+        return le16toh(u->x);
+}
+
+static inline uint32_t unaligned_read_le32(const void *_u) {
+        const struct __attribute__((__packed__, __may_alias__)) { uint32_t x; } *u = _u;
+
+        return le32toh(u->x);
+}
+
+static inline uint64_t unaligned_read_le64(const void *_u) {
+        const struct __attribute__((__packed__, __may_alias__)) { uint64_t x; } *u = _u;
+
+        return le64toh(u->x);
+}
+
+static inline void unaligned_write_le16(void *_u, uint16_t a) {
+        struct __attribute__((__packed__, __may_alias__)) { uint16_t x; } *u = _u;
+
+        u->x = le16toh(a);
+}
+
+static inline void unaligned_write_le32(void *_u, uint32_t a) {
+        struct __attribute__((__packed__, __may_alias__)) { uint32_t x; } *u = _u;
+
+        u->x = le32toh(a);
+}
+
+static inline void unaligned_write_le64(void *_u, uint64_t a) {
+        struct __attribute__((__packed__, __may_alias__)) { uint64_t x; } *u = _u;
+
+        u->x = le64toh(a);
+}
+
+#if __BYTE_ORDER == __BIG_ENDIAN
+#define unaligned_read_ne16 unaligned_read_be16
+#define unaligned_read_ne32 unaligned_read_be32
+#define unaligned_read_ne64 unaligned_read_be64
+
+#define unaligned_write_ne16 unaligned_write_be16
+#define unaligned_write_ne32 unaligned_write_be32
+#define unaligned_write_ne64 unaligned_write_be64
+#else
+#define unaligned_read_ne16 unaligned_read_le16
+#define unaligned_read_ne32 unaligned_read_le32
+#define unaligned_read_ne64 unaligned_read_le64
+
+#define unaligned_write_ne16 unaligned_write_le16
+#define unaligned_write_ne32 unaligned_write_le32
+#define unaligned_write_ne64 unaligned_write_le64
+#endif