You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@trafficserver.apache.org by so...@apache.org on 2014/08/09 00:08:21 UTC
[4/6] git commit: TS-1800: Add new hash function implementation of
SipHash
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 <so...@apache.org>
Authored: Fri Aug 8 15:17:12 2014 -0600
Committer: Phil Sorber <so...@apache.org>
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"