Created attachment 31390 [details]
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