src/thirdparty/VirtualDub/system/source/hash.cpp

   1 //      VirtualDub - Video processing and capture application
   2 //      System library component
   3 //      Copyright (C) 1998-2007 Avery Lee, All Rights Reserved.
   4 //
   5 //      Beginning with 1.6.0, the VirtualDub system library is licensed
   6 //      differently than the remainder of VirtualDub.  This particular file is
   7 //      thus licensed as follows (the "zlib" license):
   8 //
   9 //      This software is provided 'as-is', without any express or implied
  10 //      warranty.  In no event will the authors be held liable for any
  11 //      damages arising from the use of this software.
  12 //
  13 //      Permission is granted to anyone to use this software for any purpose,
  14 //      including commercial applications, and to alter it and redistribute it
  15 //      freely, subject to the following restrictions:
  16 //
  17 //      1.      The origin of this software must not be misrepresented; you must
  18 //              not claim that you wrote the original software. If you use this
  19 //              software in a product, an acknowledgment in the product
  20 //              documentation would be appreciated but is not required.
  21 //      2.      Altered source versions must be plainly marked as such, and must
  22 //              not be misrepresented as being the original software.
  23 //      3.      This notice may not be removed or altered from any source
  24 //              distribution.
  25
  26 #include "stdafx.h"
  27 #include <vd2/system/hash.h>
  28 #include <vd2/system/binary.h>
  29
  30 // Based on: SuperFastHash by Paul Hsieh
  31 //                   http://www.azillionmonkeys.com/qed/hash.html
  32
  33 uint32 VDHashString32(const char *s) {
  34         uint32 len = (uint32)strlen(s);
  35
  36         return VDHashString32(s, len);
  37 }
  38
  39 uint32 VDHashString32(const char *s, uint32 len) {
  40         uint32 hash = len;
  41
  42         uint32 rem = len & 3;
  43         len >>= 2;
  44
  45         uint32 tmp;
  46         for(uint32 i=0; i<len; ++i) {
  47                 hash += VDReadUnalignedU16(s);
  48                 tmp = (VDReadUnalignedU16(s + 2) << 11) ^ hash;
  49                 hash = (hash << 16) ^ tmp;
  50                 s += 4;
  51                 hash += hash >> 11;
  52         }
  53
  54         switch(rem) {
  55                 case 3:
  56                         hash += VDReadUnalignedU16(s);
  57                         hash ^= hash << 16;
  58                         hash ^= (uint32)(uint8)s[2] << 18;
  59                         hash += hash >> 11;
  60                         break;
  61                 case 2:
  62                         hash += VDReadUnalignedU16(s);
  63                         hash ^= hash << 11;
  64                         hash += hash >> 17;
  65                         break;
  66                 case 1:
  67                         hash += (uint8)s[0];
  68                         hash ^= hash << 10;
  69                         hash += hash >> 1;
  70                         break;
  71         }
  72
  73         hash ^= hash << 3;
  74         hash += hash >> 5;
  75         hash ^= hash << 4;
  76         hash += hash >> 17;
  77         hash ^= hash << 25;
  78         hash += hash >> 6;
  79
  80         return hash;
  81 }
  82
  83 uint32 VDHashString32(const wchar_t *s) {
  84         return VDHashString32((const char *)s, wcslen(s) * sizeof(wchar_t));
  85 }
  86
  87 uint32 VDHashString32(const wchar_t *s, uint32 len) {
  88         return VDHashString32((const char *)s, len * sizeof(wchar_t));
  89 }
  90
  91 uint32 VDHashString32I(const char *s) {
  92         uint32 len = (uint32)strlen(s);
  93
  94         return VDHashString32I(s, len);
  95 }
  96
  97 uint32 VDHashString32I(const char *s, uint32 len) {
  98         uint32 hash = 2166136261U;
  99
 100         for(uint32 i=0; i<len; ++i) {
 101                 hash *= 16777619;
 102                 hash ^= (uint32)tolower((unsigned char)*s++);
 103         }
 104
 105         return hash;
 106 }
 107
 108 uint32 VDHashString32I(const wchar_t *s) {
 109         uint32 len = (uint32)wcslen(s);
 110
 111         return VDHashString32I(s, len);
 112 }
 113
 114 uint32 VDHashString32I(const wchar_t *s, uint32 len) {
 115         uint32 hash = 2166136261U;
 116
 117         for(uint32 i=0; i<len; ++i) {
 118                 hash *= 16777619;
 119                 hash ^= (uint32)towlower(*s++);
 120         }
 121
 122         return hash;
 123 }