TS-1800: Add new hash function implementation of FNV
Project: http://git-wip-us.apache.org/repos/asf/trafficserver/repo Commit: http://git-wip-us.apache.org/repos/asf/trafficserver/commit/709650ee Tree: http://git-wip-us.apache.org/repos/asf/trafficserver/tree/709650ee Diff: http://git-wip-us.apache.org/repos/asf/trafficserver/diff/709650ee Branch: refs/heads/master Commit: 709650eec623ebf842ddc9825b232c1f8cc6fe94 Parents: 9e7cedd Author: Phil Sorber <[email protected]> Authored: Fri Aug 8 12:46:37 2014 -0600 Committer: Phil Sorber <[email protected]> Committed: Fri Aug 8 16:05:18 2014 -0600 ---------------------------------------------------------------------- NOTICE | 4 +++ ci/rat-regex.txt | 1 + lib/ts/HashFNV.cc | 73 +++++++++++++++++++++++++++++++++++++++++++++++++ lib/ts/HashFNV.h | 56 +++++++++++++++++++++++++++++++++++++ lib/ts/Makefile.am | 2 ++ lib/ts/libts.h | 1 + 6 files changed, 137 insertions(+) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/trafficserver/blob/709650ee/NOTICE ---------------------------------------------------------------------- diff --git a/NOTICE b/NOTICE index 83d5a1c..69bea65 100644 --- a/NOTICE +++ b/NOTICE @@ -80,3 +80,7 @@ Copyright (C) 2014 Yahoo! Inc. All rights reserved. healthchecks: Plugin for ATS healthchecks. 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. http://git-wip-us.apache.org/repos/asf/trafficserver/blob/709650ee/ci/rat-regex.txt ---------------------------------------------------------------------- diff --git a/ci/rat-regex.txt b/ci/rat-regex.txt index 01a3dfa..ffab470 100644 --- a/ci/rat-regex.txt +++ b/ci/rat-regex.txt @@ -50,3 +50,4 @@ pm_to_blib MurmurHash3.cc MurmurHash3.h ^ck$ +HashFNV.cc http://git-wip-us.apache.org/repos/asf/trafficserver/blob/709650ee/lib/ts/HashFNV.cc ---------------------------------------------------------------------- diff --git a/lib/ts/HashFNV.cc b/lib/ts/HashFNV.cc new file mode 100644 index 0000000..4931cd5 --- /dev/null +++ b/lib/ts/HashFNV.cc @@ -0,0 +1,73 @@ +/* + This algorithm is in the public domain. This code was + derived from code in the public domain. + + http://www.isthe.com/chongo/tech/comp/fnv/ + + Currently implemented FNV-1a 32bit and FNV-1a 64bit + */ + +#include "HashFNV.h" + +#define FNV_INIT_32 ((uint32_t)0x811c9dc5) +#define FNV_INIT_64 ((uint64_t)0xcbf29ce484222325ULL) + +// FNV-1a 64bit +ATSHash32FNV1a::ATSHash32FNV1a(void) { + this->clear(); +} + +void +ATSHash32FNV1a::update(const void *data, size_t len) { + uint8_t *bp = (uint8_t *) data; + uint8_t *be = bp + len; + + while (bp < be) { + hval ^= (uint32_t) *bp++; + hval += (hval << 1) + (hval << 4) + (hval << 7) + (hval << 8) + (hval << 24); + } +} + +void +ATSHash32FNV1a::final(void) { +} + +uint32_t +ATSHash32FNV1a::get(void) const { + return hval; +} + +void +ATSHash32FNV1a::clear(void) { + hval = FNV_INIT_32; +} + +// FNV-1a 64bit +ATSHash64FNV1a::ATSHash64FNV1a(void) { + this->clear(); +} + +void +ATSHash64FNV1a::update(const void *data, size_t len) { + uint8_t *bp = (uint8_t *) data; + uint8_t *be = bp + len; + + while (bp < be) { + hval ^= (uint64_t) *bp++; + hval += (hval << 1) + (hval << 4) + (hval << 5) + (hval << 7) + (hval << 8) + (hval << 40); + } +} + +void +ATSHash64FNV1a::final(void) { +} + +uint64_t +ATSHash64FNV1a::get(void) const { + return hval; +} + +void +ATSHash64FNV1a::clear(void) { + hval = FNV_INIT_64; +} http://git-wip-us.apache.org/repos/asf/trafficserver/blob/709650ee/lib/ts/HashFNV.h ---------------------------------------------------------------------- diff --git a/lib/ts/HashFNV.h b/lib/ts/HashFNV.h new file mode 100644 index 0000000..3be6038 --- /dev/null +++ b/lib/ts/HashFNV.h @@ -0,0 +1,56 @@ +/** @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. + */ + +/* + http://www.isthe.com/chongo/tech/comp/fnv/ + + Currently implemented FNV-1a 32bit and FNV-1a 64bit + */ + +#ifndef __HASH_FNV_H__ +#define __HASH_FNV_H__ + +#include "Hash.h" +#include <stdint.h> + +struct ATSHash32FNV1a : ATSHash32 { + ATSHash32FNV1a(void); + void update(const void *data, size_t len); + void final(void); + uint32_t get(void) const; + void clear(void); + +private: + uint32_t hval; +}; + +struct ATSHash64FNV1a : ATSHash64 { + ATSHash64FNV1a(void); + void update(const void *data, size_t len); + void final(void); + uint64_t get(void) const; + void clear(void); + +private: + uint64_t hval; +}; + +#endif http://git-wip-us.apache.org/repos/asf/trafficserver/blob/709650ee/lib/ts/Makefile.am ---------------------------------------------------------------------- diff --git a/lib/ts/Makefile.am b/lib/ts/Makefile.am index d745dba..25e357b 100644 --- a/lib/ts/Makefile.am +++ b/lib/ts/Makefile.am @@ -54,6 +54,8 @@ libtsutil_la_SOURCES = \ EventNotify.h \ Hash.cc \ Hash.h \ + HashFNV.cc \ + HashFNV.h \ HostLookup.cc \ HostLookup.h \ INK_MD5.h \ http://git-wip-us.apache.org/repos/asf/trafficserver/blob/709650ee/lib/ts/libts.h ---------------------------------------------------------------------- diff --git a/lib/ts/libts.h b/lib/ts/libts.h index 7a6097c..1e05251 100644 --- a/lib/ts/libts.h +++ b/lib/ts/libts.h @@ -82,6 +82,7 @@ #include "DynArray.h" #include "EventNotify.h" #include "Hash.h" +#include "HashFNV.h" #include "I_Version.h" #include "InkPool.h" #include "List.h"
