| OLD | NEW |
| (Empty) |
| 1 #!/usr/bin/python | |
| 2 # Copyright (C) 2013 Google, Inc. | |
| 3 # | |
| 4 # This library is free software; you can redistribute it and/or | |
| 5 # modify it under the terms of the GNU Library General Public | |
| 6 # License as published by the Free Software Foundation; either | |
| 7 # version 2 of the License, or (at your option) any later version. | |
| 8 # | |
| 9 # This library is distributed in the hope that it will be useful, | |
| 10 # but WITHOUT ANY WARRANTY; without even the implied warranty of | |
| 11 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
| 12 # Library General Public License for more details. | |
| 13 # | |
| 14 # You should have received a copy of the GNU Library General Public License | |
| 15 # along with this library; see the file COPYING.LIB. If not, write to | |
| 16 # the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, | |
| 17 # Boston, MA 02110-1301, USA. | |
| 18 | |
| 19 # This implementaiton of SuperFastHash is based on the Python implementation | |
| 20 # by Victor Perron at <https://github.com/vperron/python-superfasthash>. | |
| 21 # We've modified Victor's version to output hash values that match WTFString, | |
| 22 # which involves using a specific seed and some different constants. | |
| 23 | |
| 24 class uint32_t(long): | |
| 25 def __rshift__(self, other): | |
| 26 return uint32_t(long.__rshift__(self, other) & ((1L << 32) - 1)) | |
| 27 | |
| 28 def __lshift__(self, other): | |
| 29 return uint32_t(long.__lshift__(self, other) & ((1L << 32) - 1)) | |
| 30 | |
| 31 def __add__(self, other): | |
| 32 return uint32_t(long.__add__(self, other) & ((1L << 32) - 1)) | |
| 33 | |
| 34 def __xor__(self, other): | |
| 35 return uint32_t(long.__xor__(self, other) & ((1L << 32) - 1)) | |
| 36 | |
| 37 | |
| 38 def hash(string): | |
| 39 """ | |
| 40 Stream-adapted SuperFastHash algorithm from Paul Hsieh, | |
| 41 http://www.azillionmonkeys.com/qed/hash.html | |
| 42 LGPLv2.1 | |
| 43 Python version with no dependencies. | |
| 44 Victor Perron <victor@iso3103.net> | |
| 45 """ | |
| 46 | |
| 47 if not string: | |
| 48 return 0 | |
| 49 | |
| 50 result = uint32_t(0x9E3779B9L) | |
| 51 length = len(string) | |
| 52 remainder = length & 1 | |
| 53 length >>= 1 | |
| 54 | |
| 55 i = 0 | |
| 56 while length > 0: | |
| 57 length -= 1 | |
| 58 result += ord(string[i]) | |
| 59 temp = (ord(string[i + 1]) << 11) ^ result | |
| 60 result = (result << 16) ^ temp | |
| 61 i += 2 | |
| 62 result += (result >> 11) | |
| 63 | |
| 64 if remainder == 1: | |
| 65 result += ord(string[i]) | |
| 66 result ^= (result << 11) | |
| 67 result += (result >> 17) | |
| 68 | |
| 69 # Force "avalanching" of final 127 bits | |
| 70 result ^= (result << 3) | |
| 71 result += (result >> 5) | |
| 72 result ^= (result << 2) | |
| 73 result += (result >> 15) | |
| 74 result ^= (result << 10) | |
| 75 | |
| 76 # Save 8 bits for StringImpl to use as flags. | |
| 77 result &= 0xffffff | |
| 78 | |
| 79 # This avoids ever returning a hash code of 0, since that is used to | |
| 80 # signal "hash not computed yet". | |
| 81 assert result != 0 | |
| 82 | |
| 83 return result | |
| OLD | NEW |