http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59406
Bug ID: 59406
Summary: functions labelled FNV-1a in tr1/functional_hash.h are
not FNV-1a
Product: gcc
Version: 4.7.2
Status: UNCONFIRMED
Severity: minor
Priority: P3
Component: libstdc++
Assignee: unassigned at gcc dot gnu.org
Reporter: g1pi at libero dot it
Created attachment 31390
--> http://gcc.gnu.org/bugzilla/attachment.cgi?id=31390&action=edit
preprocessed program
As far as I know, the FNV and FNV-1a algorithms process octects, i.e. unsigned
chars. (see e.g. http://tools.ietf.org/html/draft-eastlake-fnv-03#section-2 )
The implementations in tr1/functional_hash.h work
on chars, instead, and their output is wrong (in architectures where char is
signed) when the input byte sequence includes bytes with the MSB set.
For example
std::tr1::_Fnv_hash_base<4>::hash("\x80", 1)
returns 83079839, instead of the correct value 2232128415.
The problem resides in the type cast:
template<>
struct _Fnv_hash_base<4>
{
template<typename _Tp>
static size_t
hash(const _Tp* __ptr, size_t __clength)
{
size_t __result = static_cast<size_t>(2166136261UL);
>>> const char* __cptr = reinterpret_cast<const char*>(__ptr); <<<
for (; __clength; --__clength)
{
__result ^= static_cast<size_t>(*__cptr++);
__result *= static_cast<size_t>(16777619UL);
}
return __result;
}
};
The highlighed line should read:
const unsigned char* __cptr = reinterpret_cast<const unsigned char*>(__ptr);
Since the FNV primes were carefully chosen in order to minimize
collision rates and maximize dispersion, there might be consequences in
the performance of data structures that build on tr1::hash template,
perhaps tr1::unordered_map and tr1::unordered_set.
Here is a short program exposing the bug:
#include <iostream>
#include <tr1/unordered_map>
int main()
{
std::cout << std::tr1::_Fnv_hash_base<4>::hash("\x80", 1)
<< " computed, 2232128415 expected\n";
}
and here is the output of g++ -v ...:
Using built-in specs.
COLLECT_GCC=g++
COLLECT_LTO_WRAPPER=/usr/lib/gcc/i486-linux-gnu/4.7/lto-wrapper
Target: i486-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Debian 4.7.2-5'
--with-bugurl=file:///usr/share/doc/gcc-4.7/README.Bugs
--enable-languages=c,c++,go,fortran,objc,obj-c++ --prefix=/usr
--program-suffix=-4.7 --enable-shared --enable-linker-build-id
--with-system-zlib --libexecdir=/usr/lib --without-included-gettext
--enable-threads=posix --with-gxx-include-dir=/usr/include/c++/4.7
--libdir=/usr/lib --enable-nls --with-sysroot=/ --enable-clocale=gnu
--enable-libstdcxx-debug --enable-libstdcxx-time=yes --enable-gnu-unique-object
--enable-plugin --enable-objc-gc --enable-targets=all --with-arch-32=i586
--with-tune=generic --enable-checking=release --build=i486-linux-gnu
--host=i486-linux-gnu --target=i486-linux-gnu
Thread model: posix
gcc version 4.7.2 (Debian 4.7.2-5)
COLLECT_GCC_OPTIONS='-O' '-Wextra' '-Wall' '-ansi' '-pedantic' '-v'
'-save-temps' '-fno-strict-aliasing' '-fwrapv' '-shared-libgcc'
'-mtune=generic' '-march=i586'
/usr/lib/gcc/i486-linux-gnu/4.7/cc1plus -E -quiet -v -imultiarch
i386-linux-gnu -D_GNU_SOURCE fnv-bad.cc -mtune=generic -march=i586 -ansi
-Wextra -Wall -pedantic -fno-strict-aliasing -fwrapv -O -fpch-preprocess -o
fnv-bad.ii
ignoring nonexistent directory "/usr/local/include/i386-linux-gnu"
ignoring nonexistent directory
"/usr/lib/gcc/i486-linux-gnu/4.7/../../../../i486-linux-gnu/include"
#include "..." search starts here:
#include <...> search starts here:
/usr/include/c++/4.7
/usr/include/c++/4.7/i486-linux-gnu
/usr/include/c++/4.7/backward
/usr/lib/gcc/i486-linux-gnu/4.7/include
/usr/local/include
/usr/lib/gcc/i486-linux-gnu/4.7/include-fixed
/usr/include/i386-linux-gnu
/usr/include
End of search list.
COLLECT_GCC_OPTIONS='-O' '-Wextra' '-Wall' '-ansi' '-pedantic' '-v'
'-save-temps' '-fno-strict-aliasing' '-fwrapv' '-shared-libgcc'
'-mtune=generic' '-march=i586'
/usr/lib/gcc/i486-linux-gnu/4.7/cc1plus -fpreprocessed fnv-bad.ii -quiet
-dumpbase fnv-bad.cc -mtune=generic -march=i586 -auxbase fnv-bad -O -Wextra
-Wall -pedantic -ansi -version -fno-strict-aliasing -fwrapv -o fnv-bad.s
GNU C++ (Debian 4.7.2-5) version 4.7.2 (i486-linux-gnu)
compiled by GNU C version 4.7.2, GMP version 5.0.5, MPFR version
3.1.0-p10, MPC version 0.9
GGC heuristics: --param ggc-min-expand=63 --param ggc-min-heapsize=62264
GNU C++ (Debian 4.7.2-5) version 4.7.2 (i486-linux-gnu)
compiled by GNU C version 4.7.2, GMP version 5.0.5, MPFR version
3.1.0-p10, MPC version 0.9
GGC heuristics: --param ggc-min-expand=63 --param ggc-min-heapsize=62264
Compiler executable checksum: 62bfd556e00a93e3d7f66f6876d73826
COLLECT_GCC_OPTIONS='-O' '-Wextra' '-Wall' '-ansi' '-pedantic' '-v'
'-save-temps' '-fno-strict-aliasing' '-fwrapv' '-shared-libgcc'
'-mtune=generic' '-march=i586'
as -v --32 -o fnv-bad.o fnv-bad.s
GNU assembler version 2.22 (i486-linux-gnu) using BFD version (GNU Binutils for
Debian) 2.22
COMPILER_PATH=/usr/lib/gcc/i486-linux-gnu/4.7/:/usr/lib/gcc/i486-linux-gnu/4.7/:/usr/lib/gcc/i486-linux-gnu/:/usr/lib/gcc/i486-linux-gnu/4.7/:/usr/lib/gcc/i486-linux-gnu/
LIBRARY_PATH=/usr/lib/gcc/i486-linux-gnu/4.7/:/usr/lib/gcc/i486-linux-gnu/4.7/../../../i386-linux-gnu/:/usr/lib/gcc/i486-linux-gnu/4.7/../../../../lib/:/lib/i386-linux-gnu/:/lib/../lib/:/usr/lib/i386-linux-gnu/:/usr/lib/../lib/:/usr/lib/gcc/i486-linux-gnu/4.7/../../../:/lib/:/usr/lib/
COLLECT_GCC_OPTIONS='-O' '-Wextra' '-Wall' '-ansi' '-pedantic' '-v'
'-save-temps' '-fno-strict-aliasing' '-fwrapv' '-shared-libgcc'
'-mtune=generic' '-march=i586'
/usr/lib/gcc/i486-linux-gnu/4.7/collect2 --sysroot=/ --build-id
--no-add-needed --eh-frame-hdr -m elf_i386 --hash-style=both -dynamic-linker
/lib/ld-linux.so.2
/usr/lib/gcc/i486-linux-gnu/4.7/../../../i386-linux-gnu/crt1.o
/usr/lib/gcc/i486-linux-gnu/4.7/../../../i386-linux-gnu/crti.o
/usr/lib/gcc/i486-linux-gnu/4.7/crtbegin.o -L/usr/lib/gcc/i486-linux-gnu/4.7
-L/usr/lib/gcc/i486-linux-gnu/4.7/../../../i386-linux-gnu
-L/usr/lib/gcc/i486-linux-gnu/4.7/../../../../lib -L/lib/i386-linux-gnu
-L/lib/../lib -L/usr/lib/i386-linux-gnu -L/usr/lib/../lib
-L/usr/lib/gcc/i486-linux-gnu/4.7/../../.. fnv-bad.o -lstdc++ -lm -lgcc_s -lgcc
-lc -lgcc_s -lgcc /usr/lib/gcc/i486-linux-gnu/4.7/crtend.o
/usr/lib/gcc/i486-linux-gnu/4.7/../../../i386-linux-gnu/crtn.o
In attachment, the preprocessed program (.ii). This problem was also reported
to Debian (http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=731330).
Best regards,
g
