include/assimp/Hash.h

0001 /*
0002 Open Asset Import Library (assimp)
0003 ----------------------------------------------------------------------
0004
0005 Copyright (c) 2006-2024, assimp team
0006
0007 All rights reserved.
0008
0009 Redistribution and use of this software in source and binary forms,
0010 with or without modification, are permitted provided that the
0011 following conditions are met:
0012
0013 * Redistributions of source code must retain the above
0014   copyright notice, this list of conditions and the
0015   following disclaimer.
0016
0017 * Redistributions in binary form must reproduce the above
0018   copyright notice, this list of conditions and the
0019   following disclaimer in the documentation and/or other
0020   materials provided with the distribution.
0021
0022 * Neither the name of the assimp team, nor the names of its
0023   contributors may be used to endorse or promote products
0024   derived from this software without specific prior
0025   written permission of the assimp team.
0026
0027 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
0028 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
0029 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
0030 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
0031 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
0032 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
0033 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
0034 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
0035 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
0036 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
0037 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
0038
0039 ----------------------------------------------------------------------
0040 */
0041 #pragma once
0042 #ifndef AI_HASH_H_INCLUDED
0043 #define AI_HASH_H_INCLUDED
0044
0045 #ifdef __GNUC__
0046 #   pragma GCC system_header
0047 #endif
0048
0049 #include <stdint.h>
0050 #include <stdlib.h>
0051 #include <string.h>
0052 #include <cmath>
0053
0054 // ------------------------------------------------------------------------------------------------
0055 // Hashing function taken from
0056 // http://www.azillionmonkeys.com/qed/hash.html
0057 // (incremental version)
0058 //
0059 // This code is Copyright 2004-2008 by Paul Hsieh. It is used here in the belief that
0060 // Assimp's license is considered compatible with Pauls's derivative license as specified
0061 // on his web page.
0062 //
0063 // (stdint.h should have been been included here)
0064 // ------------------------------------------------------------------------------------------------
0065 #undef get16bits
0066 #if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \
0067   || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__)
0068 #  define get16bits(d) (*((const uint16_t *) (d)))
0069 #endif
0070
0071 #if !defined (get16bits)
0072 #  define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\
0073                        +(uint32_t)(((const uint8_t *)(d))[0]) )
0074 #endif
0075
0076 // ------------------------------------------------------------------------------------------------
0077 inline uint32_t SuperFastHash (const char * data, uint32_t len = 0, uint32_t hash = 0) {
0078     uint32_t tmp;
0079     int rem;
0080
0081     if (data == NULL) return 0;
0082     if (len == 0)len = (uint32_t)::strlen(data);
0083
0084     rem = len & 3;
0085     len >>= 2;
0086
0087     /* Main loop */
0088     for (;len > 0; len--) {
0089         hash  += get16bits (data);
0090         tmp    = (get16bits (data+2) << 11) ^ hash;
0091         hash   = (hash << 16) ^ tmp;
0092         data  += 2*sizeof (uint16_t);
0093         hash  += hash >> 11;
0094     }
0095
0096     /* Handle end cases */
0097     switch (rem) {
0098         case 3: hash += get16bits (data);
0099                 hash ^= hash << 16;
0100                 hash ^= abs(data[sizeof(uint16_t)]) << 18;
0101                 hash += hash >> 11;
0102                 break;
0103         case 2: hash += get16bits (data);
0104                 hash ^= hash << 11;
0105                 hash += hash >> 17;
0106                 break;
0107         case 1: hash += *data;
0108                 hash ^= hash << 10;
0109                 hash += hash >> 1;
0110     }
0111
0112     /* Force "avalanching" of final 127 bits */
0113     hash ^= hash << 3;
0114     hash += hash >> 5;
0115     hash ^= hash << 4;
0116     hash += hash >> 17;
0117     hash ^= hash << 25;
0118     hash += hash >> 6;
0119
0120     return hash;
0121 }
0122
0123 #endif // !! AI_HASH_H_INCLUDED