google / farmhash Goto Github PK

Automatically exported from code.google.com/p/farmhash

License: MIT License

Shell 43.03% C++ 48.45% Makefile 8.13% M4 0.39%

farmhash's Introduction

FarmHash, a family of hash functions.
Version 1.1

Introduction
============

A general overview of hash functions and their use is available in the file
Understanding_Hash_Functions in this directory.  It may be helpful to read it
before using FarmHash.

FarmHash provides hash functions for strings and other data.  The functions
mix the input bits thoroughly but are not suitable for cryptography.  See
"Hash Quality," below, for details on how FarmHash was tested and so on.

We provide reference implementations in C++, with a friendly MIT license.

All members of the FarmHash family were designed with heavy reliance on
previous work by Jyrki Alakuijala, Austin Appleby, Bob Jenkins, and others.


Recommended Usage
=================

Our belief is that the typical hash function is mostly used for in-memory hash
tables and similar.  That use case allows hash functions that differ on
different platforms, and that change from time to time.  For this, I recommend
using wrapper functions in a .h file with comments such as, "may change from
time to time, may differ on different platforms, and may change depending on
NDEBUG."

Some projects may also require a forever-fixed, portable hash function.  Again
we recommend using wrapper functions in a .h, but in this case the comments on
them would be very different.

We have provided a sample of these wrapper functions in src/farmhash.h.  Our
hope is that most people will need nothing more than src/farmhash.h and
src/farmhash.cc.  Those two files are a usable and relatively portable library.
(One portability snag: if your compiler doesn't have __builtin_expect then
you may need to define FARMHASH_NO_BUILTIN_EXPECT.)  For those that prefer
using a configure script (perhaps because they want to "make install" later),
FarmHash has one, but for many people it's best to ignore it.

Note that the wrapper functions such as Hash() in src/farmhash.h can select
one of several hash functions.  The selection is done at compile time, based
on your machine architecture (e.g., sizeof(size_t)) and the availability of
vector instructions (e.g., SSE4.1).

To get the best performance from FarmHash, one will need to think a bit about
when to use compiler flags that allow vector instructions and such: -maes,
-msse4.2, -mavx, etc., or their equivalents for other compilers.  Those are
the g++ flags that make g++ emit more types of machine instructions than it
otherwise would.  For example, if you are confident that you will only be
using FarmHash on systems with SSE4.2 and/or AES, you may communicate that to
the compiler as explained in src/farmhash.cc.  If not, use -maes, -mavx, etc.,
when you can, and the appropriate choices will be made by via conditional
compilation in src/farmhash.cc.

It may be beneficial to try -O3 or other compiler flags as well.  I also have
found feedback-directed optimization (FDO) to improve the speed of FarmHash.

The "configure" script: creating config.h
=========================================

We provide reference implementations of several FarmHash functions, written in
C++.  The build system is based on autoconf.  It defaults the C++ compiler
flags to "-g -O2", which may or may not be best.

If you are planning to use the configure script, I generally recommend
trying this first, unless you know that your system lacks AVX and/or AESNI:

  ./configure CXXFLAGS="-g -mavx -maes -O3"
  make all check

If that fails, you can retry with -mavx and/or -maes removed, or with -mavx replaced by
-msse4.1 or -msse4.2.

Please see below for thoughts on cross-platform testing, if that is a concern.
Finally, if you want to install a library, you may use

  make install

Some useful flags for configure include:

  --enable-optional-builtin-expect: This causes __builtin_expect to be optional.
    If you don't use this flag, the assumption is that FarmHash will be compiled
    with compilers that provide __builtin_expect.  In practice, some FarmHash
    variants may be slightly faster if __builtin_expect is available, but it
    isn't very important and affects speed only.

Further Details
===============

The above instructions will produce a single source-level library that
includes multiple hash functions.  It will use conditional compilation, and
perhaps GCC's multiversioning, to select among the functions.  In addition,
"make all check" will create an object file using your chosen compiler, and
test it.  The object file won't necessarily contain all the code that would be
used if you were to compile the code on other platforms.  The downside of this
is obvious: the paths not tested may not actually work if and when you try
them.  The FarmHash developers try hard to prevent such problems; please let
us know if you find bugs.

To aid your cross-platform testing, for each relevant platform you may
compile your program that uses farmhash.cc with the preprocessor flag
FARMHASHSELFTEST equal to 1.  This causes a FarmHash self test to run
at program startup; the self test writes output to stdout and then
calls std::exit().  You can see this in action by running "make check":
see src/farm-test.cc for details.

There's also a trivial workaround to force particular functions to be used:
modify the wrapper functions in hash.h.  You can prevent choices being made via
conditional compilation or multiversioning by choosing FarmHash variants with
names like farmhashaa::Hash32, farmhashab::Hash64, etc.: those compute the same
hash function regardless of conditional compilation, multiversioning, or
endianness.  Consult their comments and ifdefs to learn their requirements: for
example, they are not all guaranteed to work on all platforms.

Known Issues
============

1) FarmHash was developed with little-endian architectures in mind.  It should
work on big-endian too, but less work has gone into optimizing for those
platforms.  To make FarmHash work properly on big-endian platforms you may
need to modify the wrapper .h file and/or your compiler flags to arrange for
FARMHASH_BIG_ENDIAN to be defined, though there is logic that tries to figure
it out automatically.

2) FarmHash's implementation is fairly complex.

3) The techniques described in dev/INSTRUCTIONS to let hash function
developers regenerate src/*.cc from dev/* are hacky and not so portable.

Hash Quality
============

We like to test hash functions with SMHasher, among other things.
SMHasher isn't perfect, but it seems to find almost any significant flaw.
SMHasher is available at http://code.google.com/p/smhasher/

SMHasher is designed to pass a 32-bit seed to the hash functions it tests.
For our functions that accept a seed, we use the given seed directly (padded
with zeroes as needed); for our functions that don't accept a seed, we hash
the concatenation of the given seed and the input string.

Some minor flaws in 32-bit and 64-bit functions are harmless, as we
expect the primary use of these functions will be in hash tables.  We
may have gone slightly overboard in trying to please SMHasher and other
similar tests, but we don't want anyone to choose a different hash function
because of some minor issue reported by a quality test.

If your setup is similar enough to mine, it's easy to use SMHasher and other
tools yourself via the "builder" in the dev directory.  See dev/INSTRUCTIONS.
(Improvements to that directory are a relatively low priority, and code
there is never going to be as portable as the other parts of FarmHash.)

For more information
====================

http://code.google.com/p/farmhash/

[email protected]

Please feel free to send us comments, questions, bug reports, or patches.

farmhash's People

Contributors

Stargazers

Watchers

Forkers

adfernandes zhengkejun xubingyue allenwangxiao jygan caomw liehuochen fengshao0907 mdisanto samanalysis cybernetics mldbai 3rduncle alephman ibmsoe grimderp jamesxia4 jackbro firephil eokeeffe lingya anpark fritzo-google headupinclouds pombredanne hunter-packages koolhazz solertis extrowerk praveenmunagapati duoertai jakirkham dailyncepu luciham stoma-siarhei nanonid walsonyang ericyao2013 yasushi-saito zengjieyu carlowood allancodes b-xiang xinshu the-mad-pirate giordi91 yazici arritmic mattn sharklee1031 max19931 saonam irfanhabib one909 kevin1958 denise-amiga thomasahle mishugana beebreeze neotim pllawliet mazhongzhong muskanmahajan37 kamranash fxmeiller zhaohb meghabedi13 bonniema anrongwn wzb1005 edge-side-story codeswolves isabella232 kingins planetmarshall clintonkildepstein telematixsw cjmcgraw clyde-zhao tawiesn hexagon-geo-surv qm-quant nktelnet trixirt hichemelb fangnanwei central-intelligence-tf-185 yahonanjing ghas-results gerhobbelt digitaldawggco

farmhash's Issues

expose self test as ordinary function

so that it can be called on demand as part of testsuite

gcc-4.3 and older

does not have <immintrin.h>

see my fixes at rurban/smhasher@0d0a40e

Big endian platform not detected by farmhash

We are building TensorFlow on big endian system and farmhash is being downloaded as external dependency.

Few tests are failing on our system ( s390x platform) as it's not getting detected as big endian by farmhash. We tried setting the macro FARMHASH_BIG_ENDIAN for s390x in farmhash.cc file and with this change the tests are passing .

The farmhash/README mentions a known issue for big endian that
to make FarmHash work properly on big-endian platforms you may need to modify the wrapper .h file.

Is farmhash.cc right place to add a macro for our platform?
(We have seen macros used in config.h for big endian but doesn't seem to work for s390x )

/bin/bash: aclocal-1.14: command not found

The configure script generates an incorrect Makefile, which tries to run aclocal-1.14 (which I don't have, my system has aclocal-1.15). Fixed it by running autoreconf.

Build system not working for automake-1.15

Debian Sid now ships automake-1.15.

./configure works for me, however the subsequent make all failed.

$ make
 cd . && automake-1.14 --foreign
/bin/bash: line 4: automake-1.14: command not found
Makefile:378: recipe for target 'Makefile.in' failed
make: *** [Makefile.in] Error 1

$ apt list automake\* -a
Listing... Done
automake/unstable,now 1:1.15-5 all [installed,automatic]

automake1.11/unstable,now 1:1.11.6-4 all [installed]

s390x support in farmhash

We had raised an issue in google/farmhash master earlier for big endian. However due to restructuring in the code via latest commits, the support for s390x needs to be explicitly added.
filename: farmhash/src/farmhash.h

#endif
- #elif defined(__OpenBSD__) || defined(__NetBSD__) || defined(__FreeBSD__) || defined(__DragonFly__) 
+ #elif defined(__OpenBSD__) || defined(__NetBSD__) || defined(__FreeBSD__) || defined(__DragonFly__) || defined(__s390x__)
 #include <sys/endian.h>

Installation error

Please see this question on StackOverflow.

I'm getting the following error on installation.

./node_modules/farmhash/index.js

Module not found: Can't resolve './build/Release/farmhash' in '/path/to/my_project/node_modules/farmhash'

Steps to recreate.

At the command line, I did

yarn add farmhash

Then imported using

import farmhash from 'farmhash';

Then tried to use with

  const hash = farmhash.hash32('test');

I checked my node_modules directory to verify it installed to the correct location: node_node_modules/farmhash/index.js

What am I doing wrong and how can I correct this error?

The initial Debian package of farmhash FTBFS on several architectures

All buildlogs can be found here:
https://buildd.debian.org/status/package.php?p=farmhash&suite=experimental

Farmhash failed to build on s390x and mips etc.

make -j4 all check" fails

It looks like farm-test rule runs twice, concurrently. "make all check", "make -j4 all", "make -j4 check" all succeed. Only "make -j4 all check" fails.

Below is a log:

make all-recursive
Making check in src
make[1]: Entering directory /home/saito/src_master/__build__/third_party/farmha sh-1.1.0/__tmp__/farmhash-1.1.0' Making all in src make[1]: Entering directory/home/saito/src_master/build/third_party/farmha
sh-1.1.0/tmp/farmhash-1.1.0/src'
/bin/bash ../libtool --tag=CXX --mode=compile g++ -DHAVE_CONFIG_H -I. -I..
-g -msse4.2 -maes -O3 -MT farmhash.lo -MD -MP -MF .deps/farmhash.Tpo -c -o far
mhash.lo farmhash.cc
g++ -DHAVE_CONFIG_H -I. -I.. -g -msse4.2 -maes -O3 -MT farm-test.o -MD -MP -
MF .deps/farm-test.Tpo -c -o farm-test.o farm-test.cc
make[2]: Entering directory /home/saito/src_master/__build__/third_party/farmha sh-1.1.0/__tmp__/farmhash-1.1.0/src' /bin/bash ../libtool --tag=CXX --mode=compile g++ -DHAVE_CONFIG_H -I. -I.. -g -msse4.2 -maes -O3 -MT farmhash.lo -MD -MP -MF .deps/farmhash.Tpo -c -o far mhash.lo farmhash.cc g++ -DHAVE_CONFIG_H -I. -I.. -g -msse4.2 -maes -O3 -MT farm-test.o -MD -MP - MF .deps/farm-test.Tpo -c -o farm-test.o farm-test.cc libtool: compile: g++ -DHAVE_CONFIG_H -I. -I.. -g -msse4.2 -maes -O3 -MT farmha sh.lo -MD -MP -MF .deps/farmhash.Tpo -c farmhash.cc -fPIC -DPIC -o .libs/farmha sh.o libtool: compile: g++ -DHAVE_CONFIG_H -I. -I.. -g -msse4.2 -maes -O3 -MT farmha sh.lo -MD -MP -MF .deps/farmhash.Tpo -c farmhash.cc -fPIC -DPIC -o .libs/farmha sh.o libtool: compile: g++ -DHAVE_CONFIG_H -I. -I.. -g -msse4.2 -maes -O3 -MT farmha sh.lo -MD -MP -MF .deps/farmhash.Tpo -c farmhash.cc -o farmhash.o >/dev/null 2>& 1 libtool: compile: g++ -DHAVE_CONFIG_H -I. -I.. -g -msse4.2 -maes -O3 -MT farmha sh.lo -MD -MP -MF .deps/farmhash.Tpo -c farmhash.cc -o farmhash.o >/dev/null 2>& 1 mv -f .deps/farm-test.Tpo .deps/farm-test.Po mv -f .deps/farm-test.Tpo .deps/farm-test.Po mv: cannot stat ‘.deps/farm-test.Tpo’: No such file or directory make[2]: *** [farm-test.o] Error 1 make[2]: *** Waiting for unfinished jobs.... mv -f .deps/farmhash.Tpo .deps/farmhash.Plo /bin/bash ../libtool --tag=CXX --mode=link g++ -g -msse4.2 -maes -O3 -o li bfarmhash.la -rpath /home/saito/src_master/__build__/third_party/farmhash-1.1.0/ lib farmhash.lo mv -f .deps/farmhash.Tpo .deps/farmhash.Plo mv: cannot stat ‘.deps/farmhash.Tpo’: No such file or directory make[2]: *** [farmhash.lo] Error 1 make[2]: Leaving directory/home/saito/src_master/build/third_party/farmhash-1.1.0/tmp/farmhash-1.1.0/src'
make[1]: *** [all-recursive] Error 1
make[1]: Leaving directory `/home/saito/src_master/build/third_party/farmhash-1.1.0/tmp/farmhash-1.1.0'
make: *** [all] Error 2
make: *** Waiting for unfinished jobs....

FreeBSD produces wrong hashes

In my smhasher I just added a FreeBSD 12.1 smoker, and noticed that FarmHash (64 and 128 bit) fails the hash verification tests. I.e. FarmHash is not really portable on FreeBSD.

See https://cirrus-ci.com/task/6233793094746112

Crash in farmhash used by ml vision

Hello,

I have a crash which seems to be related to farmhash here: flutter/flutter#35201

Do you have any information how this could be addressed?

Please tag the version

The comments say that the version is "1.1", but it isn't tagged.

Milk did bud utter fax

Charlaix limozeen

make -j4 all check" fails

It looks like farm-test rule runs twice, concurrently. "make all check", "make -j4 all", "make -j4 check" all succeeds. Only "make -j4 all check" fails.

Below is a log:

Compiler warnings when 64-bit size_t is squashed to 32-bits

What steps will reproduce the problem?
1. Try compiling farmhash on a 64-bit Mac using Xcode 6.x

What is the expected output? What do you see instead?
I expect it to compile clean. Instead I get a ton of warnings:
farmhash.cc:995:26: Implicit conversion loses integer precision: 'size_t' (aka 
'unsigned long') to 'uint32_t' (aka 'unsigned int')

What version of the product are you using? On what operating system?
farmhash-1.1.0

Please provide any additional information below.

Not that anybody would try to hash 4+ gigabytes of data, but if they do, will 
it still work?

If you feel that losing precision is intentional, then a bunch of 
static_cast<uint32_t>(len) would do the trick.

Original issue reported on code.google.com by [email protected] on 30 Jun 2015 at 5:56

farmhash via vcpkg

FYI, farmhash was submitted to vcpkg port. You are welcome to review and comment here

256-bit variant of farmhash

Since both Highway hash and Cityhash have 256-bit variants, would Farmhash ever get its own 256-bit hash?

npm install compile error

MacOS Mojave 10.14.2
XCODE Version 10.1 (10B61)

run npm i got the follwing error

$ npm i
> [email protected] install /xxx/> [email protected] install /Users/zhangliao/Dev_Code/jingGangShan/node_modules/farmhash
> node-gyp rebuild

  CXX(target) Release/obj.target/farmhash-legacy/src/upstream/farmhash-legacy.o
In file included from ../src/upstream/farmhash-legacy.cc:23:
../src/upstream/farmhash.h:49:10: warning: non-portable path to file '<String.h>'; specified path differs in case from file name on disk
      [-Wnonportable-include-path]
#include <string.h>   // for memcpy and memset
         ^~~~~~~~~~
         <String.h>
In file included from ../src/upstream/farmhash-legacy.cc:23:
In file included from ../src/upstream/farmhash.h:49:
In file included from /usr/local/include/string.h:26:
In file included from /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/string:477:
In file included from /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/string_view:176:
In file included from /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/__string:56:
In file included from /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/algorithm:641:
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/cstring:70:9: error: no member named 'memcpy' in the global
      namespace
using ::memcpy;
      ~~^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/cstring:71:9: error: no member named 'memmove' in the global
      namespace
using ::memmove;
      ~~^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/cstring:72:9: error: no member named 'strcpy' in the global
      namespace
using ::strcpy;rm node_modules/farmhash
> node-gyp rebuild

  CXX(target) Release/obj.target/farmhash-legacy/src/upstream/farmhash-legacy.o
In file included from ../src/upstream/farmhash-legacy.cc:23:
../src/upstream/farmhash.h:49:10: warning: non-portable path to file '<String.h>'; specified path differs in case from file name on disk
      [-Wnonportable-include-path]
#include <string.h>   // for memcpy and memset
         ^~~~~~~~~~
         <String.h>
In file included from ../src/upstream/farmhash-legacy.cc:23:
In file included from ../src/upstream/farmhash.h:49:
In file included from /usr/local/include/string.h:26:
In file included from /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/string:477:
In file included from /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/string_view:176:
In file included from /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/__string:56:
In file included from /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/algorithm:641:
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/cstring:70:9: error: no member named 'memcpy' in the global
      namespace
using ::memcpy;
      ~~^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/cstring:71:9: error: no member named 'memmove' in the global
      namespace
using ::memmove;
      ~~^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/cstring:72:9: error: no member named 'strcpy' in the global
      namespace
using ::strcpy;

broken config.sub with a ton unresolved merge conflicts

https://github.com/google/farmhash/blob/master/config.sub

e.g.

#! /bin/sh
# Configuration validation subroutine script.
<<<<<<< HEAD
#   Copyright 1992-2016 Free Software Foundation, Inc.

timestamp='2016-06-20'
=======
#   Copyright 1992-2015 Free Software Foundation, Inc.

timestamp='2015-08-20'
>>>>>>> 96e46782298bdf50ac214ab1920e4eb49f7a0cda

clang + libc++ + c++17 errors

"using namespace std;" in farmhash.cc causes the following error:
you should remove the "using namespace std" from the source code.

lib/hash/farmhash.cc:2006:14: error: reference to 'data' is ambiguous
memcpy(data + i, &u, 1); // uint8_t -> char
^
lib/hash/farmhash.cc:1990:13: note: candidate found by name lookup is 'data'
static char data[kDataSize];
^
/scratch-nvme/saito/bazel/_bazel_ysaito/e1a7c710473372ee150f48ad758734b2/external/grail_toolchain/include/c++/v1/iterator:1876:22: note: candidate found by name lookup is 'std::__1::data'
constexpr const _Ep* data(initializer_list<_Ep> __il) noexcept { return __il.begin(); }

Add documentation on the hash algorithm

As far as I can see, there's no documentation on how the thing actually works. 
The source code is rather complex. Are there any Google-internal docs? If so, 
is there any chance of releasing them? Implementations in different languages 
would be so much easier to write...

Original issue reported on code.google.com by [email protected] on 26 Jan 2015 at 1:14

Error compilation using MinGW 64 on Windows 10

Hi,
Compiling the library for MinGW 64, it comes to this like and it fails:

farmhash/src/farmhash.h

Line 308 in 2f0e005

    
           #elif defined(__linux__) || defined(__CYGWIN__) || defined( __GNUC__ ) || defined( __GNU_LIBRARY__ )

Error: "endian.h: No such file or directory"

I am using just the last MinGW 7.3.0 64