tag:blogger.com,1999:blog-5246987755651065286.post5678304466697946823..comments2024-02-22T16:15:42.388-08:00Comments on cbloom rants: 12-05-08 - lrotlcbloomhttp://www.blogger.com/profile/10714564834899413045noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-5246987755651065286.post-40397531344618438832008-12-07T11:09:00.000-08:002008-12-07T11:09:00.000-08:00OK I think I figured out a good way to do the last...OK I think I figured out a good way to do the last, NUL-containing word. The trick is to overlap the multiply with the search for the NUL. What seems to work pretty well is to first check if the first byte is NUL, then kick off the multiply, then find the NUL byte to compute a mask you use on the eventual product. The mask should include the valid and NUL bytes, but zero-out the following garbage bytes.<BR/><BR/>Also, it is probably a good idea to incorporate the length of the string in the hash somehow, although less important for NUL-terminated strings.won3dhttps://www.blogger.com/profile/09787472194187459747noreply@blogger.comtag:blogger.com,1999:blog-5246987755651065286.post-54910880161469580842008-12-06T21:24:00.000-08:002008-12-06T21:24:00.000-08:00So, GCC manages to do some nice things. "(x&l...So, GCC manages to do some nice things. "(x<25) + (x>>7)" automatically turns into rotl, and accessing the high 32-bits of the 64-bit multiplication result doesn't have any ridiculousness. Maybe some extra MOVs.<BR/><BR/>Anyway, combining chocolate/peanut butter, using all 64 bits of the MUL seems like it makes a pretty good/fast hash. I'm still trying to figure out a good way to handle the final mix with MUL, which seems expensive there.won3dhttps://www.blogger.com/profile/09787472194187459747noreply@blogger.com