superfasthash.c 3.1 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485
  1. // Copyright (c) 2010, Paul Hsieh
  2. // All rights reserved.
  3. //
  4. // Redistribution and use in source and binary forms, with or without
  5. // modification, are permitted provided that the following conditions are met:
  6. //
  7. // * Redistributions of source code must retain the above copyright notice, this
  8. // list of conditions and the following disclaimer.
  9. // * Redistributions in binary form must reproduce the above copyright notice,
  10. // this list of conditions and the following disclaimer in the documentation
  11. // and/or other materials provided with the distribution.
  12. // * Neither my name, Paul Hsieh, nor the names of any other contributors to the
  13. // code use may not be used to endorse or promote products derived from this
  14. // software without specific prior written permission.
  15. //
  16. // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  17. // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  18. // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  19. // ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
  20. // LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  21. // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  22. // SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  23. // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  24. // CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  25. // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  26. // POSSIBILITY OF SUCH DAMAGE.
  27. #include <stdint.h>
  28. #include <stdlib.h>
  29. #undef get16bits
  30. #if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \
  31. || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__)
  32. #define get16bits(d) (*((const uint16_t *) (d)))
  33. #endif
  34. #if !defined (get16bits)
  35. #define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\
  36. +(uint32_t)(((const uint8_t *)(d))[0]) )
  37. #endif
  38. uint32_t SuperFastHash (const char * data, int len) {
  39. uint32_t hash = (uint32_t)len, tmp;
  40. int rem;
  41. if (len <= 0 || data == NULL) return 0;
  42. rem = len & 3;
  43. len >>= 2;
  44. /* Main loop */
  45. for (;len > 0; len--) {
  46. hash += get16bits (data);
  47. tmp = (uint32_t)(get16bits (data+2) << 11) ^ hash;
  48. hash = (hash << 16) ^ tmp;
  49. data += 2*sizeof (uint16_t);
  50. hash += hash >> 11;
  51. }
  52. /* Handle end cases */
  53. switch (rem) {
  54. case 3: hash += get16bits (data);
  55. hash ^= hash << 16;
  56. hash ^=
  57. (uint32_t)(((signed char)data[sizeof (uint16_t)]) << 18);
  58. hash += hash >> 11;
  59. break;
  60. case 2: hash += get16bits (data);
  61. hash ^= hash << 11;
  62. hash += hash >> 17;
  63. break;
  64. case 1: hash += (uint32_t)((signed char)*data);
  65. hash ^= hash << 10;
  66. hash += hash >> 1;
  67. }
  68. /* Force "avalanching" of final 127 bits */
  69. hash ^= hash << 3;
  70. hash += hash >> 5;
  71. hash ^= hash << 4;
  72. hash += hash >> 17;
  73. hash ^= hash << 25;
  74. hash += hash >> 6;
  75. return hash;
  76. }