TS-1800: Add new hash function implementation of SipHash
Project: http://git-wip-us.apache.org/repos/asf/trafficserver/repo Commit: http://git-wip-us.apache.org/repos/asf/trafficserver/commit/5d0d6d8b Tree: http://git-wip-us.apache.org/repos/asf/trafficserver/tree/5d0d6d8b Diff: http://git-wip-us.apache.org/repos/asf/trafficserver/diff/5d0d6d8b Branch: refs/heads/master Commit: 5d0d6d8ba9490df9ce3da5064722f64ef373fedb Parents: 524f8d7 Author: Phil Sorber <[email protected]> Authored: Fri Aug 8 15:17:12 2014 -0600 Committer: Phil Sorber <[email protected]> Committed: Fri Aug 8 16:06:16 2014 -0600 ---------------------------------------------------------------------- NOTICE | 7 +++ ci/rat-regex.txt | 1 + lib/ts/HashSip.cc | 138 ++++++++++++++++++++++++++++++++++++++++++++++++ lib/ts/HashSip.h | 52 ++++++++++++++++++ lib/ts/Makefile.am | 2 + lib/ts/libts.h | 1 + 6 files changed, 201 insertions(+) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/trafficserver/blob/5d0d6d8b/NOTICE ---------------------------------------------------------------------- diff --git a/NOTICE b/NOTICE index 69bea65..6132ce6 100644 --- a/NOTICE +++ b/NOTICE @@ -84,3 +84,10 @@ Copyright (C) 2012 Go Daddy Operating Company, LLC lib/ts/HashFNV.cc contains code derived from code at http://www.isthe.com/chongo/tech/comp/fnv/ It is public domain and has no copyright. + +~~ + +lib/ts/HashSip.cc contains code derived from code at https://github.com/floodyberry/siphash +The code is public domain. + +The algorithm info can be found at: https://131002.net/siphash/ http://git-wip-us.apache.org/repos/asf/trafficserver/blob/5d0d6d8b/ci/rat-regex.txt ---------------------------------------------------------------------- diff --git a/ci/rat-regex.txt b/ci/rat-regex.txt index ffab470..d993267 100644 --- a/ci/rat-regex.txt +++ b/ci/rat-regex.txt @@ -51,3 +51,4 @@ MurmurHash3.cc MurmurHash3.h ^ck$ HashFNV.cc +HashSip.cc http://git-wip-us.apache.org/repos/asf/trafficserver/blob/5d0d6d8b/lib/ts/HashSip.cc ---------------------------------------------------------------------- diff --git a/lib/ts/HashSip.cc b/lib/ts/HashSip.cc new file mode 100644 index 0000000..ac1632f --- /dev/null +++ b/lib/ts/HashSip.cc @@ -0,0 +1,138 @@ +/** + +Algorithm Info: +https://131002.net/siphash/ + +Based off of implementation: +https://github.com/floodyberry/siphash + + */ + +#include "HashSip.h" +#include <cstring> + +#define SIP_BLOCK_SIZE 8 + +#define ROTL64(a,b) (((a)<<(b))|((a)>>(64-b))) + +#define U8TO64_LE(p) *(const uint64_t *)(p) + +#define SIPCOMPRESS(x0,x1,x2,x3) \ + x0 += x1; \ + x2 += x3; \ + x1 = ROTL64(x1,13); \ + x3 = ROTL64(x3,16); \ + x1 ^= x0; \ + x3 ^= x2; \ + x0 = ROTL64(x0,32); \ + x2 += x1; \ + x0 += x3; \ + x1 = ROTL64(x1,17); \ + x3 = ROTL64(x3,21); \ + x1 ^= x2; \ + x3 ^= x0; \ + x2 = ROTL64(x2,32); + +ATSHash64Sip24::ATSHash64Sip24(void) { + k0 = 0; + k1 = 0; + this->clear(); +} + +ATSHash64Sip24::ATSHash64Sip24(const unsigned char key[16]) { + k0 = U8TO64_LE(key); + k1 = U8TO64_LE(key + sizeof(k0)); + this->clear(); +} + +ATSHash64Sip24::ATSHash64Sip24(uint64_t key0, uint64_t key1) { + k0 = key0; + k1 = key1; + this->clear(); +} + +void +ATSHash64Sip24::update(const void *data, size_t len) { + size_t i, blocks; + unsigned char *m; + uint64_t mi; + uint8_t block_off = 0; + + if (!finalized) { + m = (unsigned char *) data; + total_len += len; + + if (len + block_buffer_len < SIP_BLOCK_SIZE) { + memcpy(block_buffer + block_buffer_len, m, len); + block_buffer_len += len; + } else { + if (block_buffer_len > 0) { + block_off = SIP_BLOCK_SIZE - block_buffer_len; + memcpy(block_buffer + block_buffer_len, m, block_off); + + mi = U8TO64_LE(block_buffer); + v3 ^= mi; + SIPCOMPRESS(v0, v1, v2, v3); + SIPCOMPRESS(v0, v1, v2, v3); + v0 ^= mi; + } + + for (i = block_off, blocks = ((len - block_off) & ~(SIP_BLOCK_SIZE - 1)); i < blocks; i += SIP_BLOCK_SIZE) { + mi = U8TO64_LE(m + i); + v3 ^= mi; + SIPCOMPRESS(v0, v1, v2, v3); + SIPCOMPRESS(v0, v1, v2, v3); + v0 ^= mi; + } + + block_buffer_len = (len - block_off) & (SIP_BLOCK_SIZE - 1); + memcpy(block_buffer, m + block_off + blocks, block_buffer_len); + } + } +} + +void +ATSHash64Sip24::final(void) { + uint64_t last7; + int i; + + if (!finalized) { + last7 = (uint64_t) (total_len & 0xff) << 56; + + for (i = block_buffer_len - 1; i >= 0; i--) { + last7 |= (uint64_t) block_buffer[i] << (i * 8); + } + + v3 ^= last7; + SIPCOMPRESS(v0, v1, v2, v3); + SIPCOMPRESS(v0, v1, v2, v3); + v0 ^= last7; + v2 ^= 0xff; + SIPCOMPRESS(v0, v1, v2, v3); + SIPCOMPRESS(v0, v1, v2, v3); + SIPCOMPRESS(v0, v1, v2, v3); + SIPCOMPRESS(v0, v1, v2, v3); + hfinal = v0 ^ v1 ^ v2 ^ v3; + finalized = true; + } +} + +uint64_t +ATSHash64Sip24::get(void) const { + if (finalized) { + return hfinal; + } else { + return 0; + } +} + +void +ATSHash64Sip24::clear(void) { + v0 = k0 ^ 0x736f6d6570736575ull; + v1 = k1 ^ 0x646f72616e646f6dull; + v2 = k0 ^ 0x6c7967656e657261ull; + v3 = k1 ^ 0x7465646279746573ull; + finalized = false; + total_len = 0; + block_buffer_len = 0; +} http://git-wip-us.apache.org/repos/asf/trafficserver/blob/5d0d6d8b/lib/ts/HashSip.h ---------------------------------------------------------------------- diff --git a/lib/ts/HashSip.h b/lib/ts/HashSip.h new file mode 100644 index 0000000..80fe733 --- /dev/null +++ b/lib/ts/HashSip.h @@ -0,0 +1,52 @@ +/** @file + + @section license License + + Licensed to the Apache Software Foundation (ASF) under one + or more contributor license agreements. See the NOTICE file + distributed with this work for additional information + regarding copyright ownership. The ASF licenses this file + to you under the Apache License, Version 2.0 (the + "License"); you may not use this file except in compliance + with the License. You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. + */ + +#ifndef __HASH_SIP_H__ +#define __HASH_SIP_H__ + +#include "Hash.h" +#include <stdint.h> + +/* + Siphash is a Hash Message Authentication Code and can take a key. + + If you don't care about MAC use the void constructor and it will use + a zero key for you. + */ + +struct ATSHash64Sip24 : ATSHash64 { + ATSHash64Sip24(void); + ATSHash64Sip24(const unsigned char key[16]); + ATSHash64Sip24(uint64_t key0, uint64_t key1); + void update(const void *data, size_t len); + void final(void); + uint64_t get(void) const; + void clear(void); + +private: + unsigned char block_buffer[8]; + uint8_t block_buffer_len; + uint64_t k0, k1, v0, v1, v2, v3, hfinal; + size_t total_len; + bool finalized; +}; + +#endif http://git-wip-us.apache.org/repos/asf/trafficserver/blob/5d0d6d8b/lib/ts/Makefile.am ---------------------------------------------------------------------- diff --git a/lib/ts/Makefile.am b/lib/ts/Makefile.am index acc55d7..6d207eb 100644 --- a/lib/ts/Makefile.am +++ b/lib/ts/Makefile.am @@ -58,6 +58,8 @@ libtsutil_la_SOURCES = \ HashFNV.h \ HashMD5.cc \ HashMD5.h \ + HashSip.cc \ + HashSip.h \ HostLookup.cc \ HostLookup.h \ INK_MD5.h \ http://git-wip-us.apache.org/repos/asf/trafficserver/blob/5d0d6d8b/lib/ts/libts.h ---------------------------------------------------------------------- diff --git a/lib/ts/libts.h b/lib/ts/libts.h index 164780a..245ef77 100644 --- a/lib/ts/libts.h +++ b/lib/ts/libts.h @@ -84,6 +84,7 @@ #include "Hash.h" #include "HashFNV.h" #include "HashMD5.h" +#include "HashSip.h" #include "I_Version.h" #include "InkPool.h" #include "List.h"
