[ruby-cvs:64300] nobu:r57134 (trunk): st.c: fix st_hash* functions [Bug #13019]

nobu at ruby-lang.org nobu at ruby-lang.org
Wed Dec 21 15:22:17 JST 2016


nobu	2016-12-21 15:22:16 +0900 (Wed, 21 Dec 2016)

  New Revision: 57134

  https://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=revision&revision=57134

  Log:
    st.c: fix st_hash* functions [Bug #13019]
    
    Previous implementation had an issues:
    - macros murmur1 assumes murmur_step takes rotation value
      as a second argument
    - but murmur_step second argument is "next block"
    - this makes st_hash_uint and st_hash_end to not mix high bits of
      hash value into lower bits
    - this leads to pure hash behavior on doubles and mixing hashes using
      st_hash_uint.
      It didn't matter when bins amount were prime numbers, but it hurts
      when bins are powers of two.
    
    Mistake were created cause of attempt to co-exist Murmur1 and Murmur2
    in a same code.
    
    Change it to single hash-function implementation.
    - block function is in a spirit of Murmur functions,
      but handles inter-block dependency a bit better (imho).
    - final block is read in bit more optimal way on CPU with unaligned word access,
    - final block is mixed in simple way,
    - finalizer is taken from MurmurHash3 (it makes most of magic :) )
      (64bit finalizer is taken from
      http://zimbry.blogspot.ru/2011/09/better-bit-mixing-improving-on.html)
    
    Also remove ST_USE_FNV1: it lacks implementation of many functions,
    and looks to be abandoned
    
    Author: Sokolov Yura aka funny_falcon <funny.falcon at gmail.com>

  Modified files:
    trunk/include/ruby/st.h
    trunk/st.c


More information about the ruby-cvs mailing list