From 9438ef5f79fdac11080c3fa10c518e335fd7d8d6 Mon Sep 17 00:00:00 2001 From: Henri Beauchamp Date: Tue, 31 Jan 2023 17:42:51 +0100 Subject: SL-19110 Fast hashing classes for use in place of the slow LLMD5, where speed matters. (#64) This commit adds the HBXX64 and HBXX128 classes for use as a drop-in replacement for the slow LLMD5 hashing class, where speed matters and backward compatibility (with standard hashing algorithms) and/or cryptographic hashing qualities are not required. It also replaces LLMD5 with HBXX* in a few existing hot (well, ok, just "warm" for some) paths meeting the above requirements, while paving the way for future use cases, such as in the DRTVWR-559 and sibling branches where the slow LLMD5 is used (e.g. to hash materials and vertex buffer cache entries), and could be use such a (way) faster algorithm with very significant benefits and no negative impact. Here is the comment I added in indra/llcommon/hbxx.h: // HBXXH* classes are to be used where speed matters and cryptographic quality // is not required (no "one-way" guarantee, though they are likely not worst in // this respect than MD5 which got busted and is now considered too weak). The // xxHash code they are built upon is vectorized and about 50 times faster than // MD5. A 64 bits hash class is also provided for when 128 bits of entropy are // not needed. The hashes collision rate is similar to MD5's. // See https://github.com/Cyan4973/xxHash#readme for details. --- indra/llcommon/lluuid.cpp | 28 ++++++++-------------------- 1 file changed, 8 insertions(+), 20 deletions(-) (limited to 'indra/llcommon/lluuid.cpp') diff --git a/indra/llcommon/lluuid.cpp b/indra/llcommon/lluuid.cpp index acce8366ea..8ff6c45760 100644 --- a/indra/llcommon/lluuid.cpp +++ b/indra/llcommon/lluuid.cpp @@ -40,11 +40,11 @@ #include "lluuid.h" #include "llerror.h" #include "llrand.h" -#include "llmd5.h" #include "llstring.h" #include "lltimer.h" #include "llthread.h" #include "llmutex.h" +#include "hbxxh.h" const LLUUID LLUUID::null; const LLTransactionID LLTransactionID::tnull; @@ -402,11 +402,9 @@ LLUUID LLUUID::operator^(const LLUUID& rhs) const void LLUUID::combine(const LLUUID& other, LLUUID& result) const { - LLMD5 md5_uuid; - md5_uuid.update((unsigned char*)mData, 16); - md5_uuid.update((unsigned char*)other.mData, 16); - md5_uuid.finalize(); - md5_uuid.raw_digest(result.mData); + HBXXH128 hash((const void*)mData, 16, false); // false = do not finalize + hash.update((const void*)other.mData, 16); + hash.digest(result); } LLUUID LLUUID::combine(const LLUUID &other) const @@ -857,17 +855,12 @@ void LLUUID::generate() tmp >>= 8; mData[8] = (unsigned char) tmp; - LLMD5 md5_uuid; - - md5_uuid.update(mData,16); - md5_uuid.finalize(); - md5_uuid.raw_digest(mData); + HBXXH128::digest(*this, (const void*)mData, 16); } void LLUUID::generate(const std::string& hash_string) { - LLMD5 md5_uuid((U8*)hash_string.c_str()); - md5_uuid.raw_digest(mData); + HBXXH128::digest(*this, hash_string); } U32 LLUUID::getRandomSeed() @@ -885,13 +878,8 @@ U32 LLUUID::getRandomSeed() seed[7]=(unsigned char)(pid); getSystemTime((uuid_time_t *)(&seed[8])); - LLMD5 md5_seed; - - md5_seed.update(seed,16); - md5_seed.finalize(); - md5_seed.raw_digest(seed); - - return(*(U32 *)seed); + U64 seed64 = HBXXH64((const void*)seed, 16).digest(); + return U32(seed64) ^ U32(seed64 >> 32); } BOOL LLUUID::parseUUID(const std::string& buf, LLUUID* value) -- cgit v1.2.3 From 1eb2b23f4b254052924b198d446c052df9ca3124 Mon Sep 17 00:00:00 2001 From: Henri Beauchamp Date: Tue, 7 Feb 2023 13:51:53 +0100 Subject: SL-19159 Faster LLUUID and LLMaterialID hashing for std and boost containers keys (#70) LLUUID and LLMaterialID already have an excellent entropy and value dispersion; there is therefore strictly no need to further (slowly) hash their value for use with std and boost libraries containers. This commit adds a trivial getDigest64() method to both LLUUID and LLMaterialID (which simply returns the XOR of the two 64 bits long words their value is made of), and uses it in std::hash and hash_value() specializations for use with containers. --- indra/llcommon/lluuid.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'indra/llcommon/lluuid.cpp') diff --git a/indra/llcommon/lluuid.cpp b/indra/llcommon/lluuid.cpp index 8ff6c45760..aa8045e6ab 100644 --- a/indra/llcommon/lluuid.cpp +++ b/indra/llcommon/lluuid.cpp @@ -878,7 +878,7 @@ U32 LLUUID::getRandomSeed() seed[7]=(unsigned char)(pid); getSystemTime((uuid_time_t *)(&seed[8])); - U64 seed64 = HBXXH64((const void*)seed, 16).digest(); + U64 seed64 = HBXXH64::digest((const void*)seed, 16); return U32(seed64) ^ U32(seed64 >> 32); } -- cgit v1.2.3 From e2836313a8d2b5e2acd4fd20bde50521613ed0ef Mon Sep 17 00:00:00 2001 From: Henri Beauchamp Date: Mon, 13 Feb 2023 18:34:00 +0100 Subject: SL-19110 revert LLUUID::combine() to old algorithm to match server code. (#75) As it happens, the change in the LLUUID::combine() algorithm introduced by one of my previous commits is causing invalid assets creation (seen with some clothing items, such as Shape and Universal types); obviously, the server is using the old algorithm for UUID validation purpose of these assets. This commit reverts LLUUID::combine() code to use LLMD5. --- indra/llcommon/lluuid.cpp | 12 +++++++++--- 1 file changed, 9 insertions(+), 3 deletions(-) (limited to 'indra/llcommon/lluuid.cpp') diff --git a/indra/llcommon/lluuid.cpp b/indra/llcommon/lluuid.cpp index aa8045e6ab..adf31b2d28 100644 --- a/indra/llcommon/lluuid.cpp +++ b/indra/llcommon/lluuid.cpp @@ -44,6 +44,7 @@ #include "lltimer.h" #include "llthread.h" #include "llmutex.h" +#include "llmd5.h" #include "hbxxh.h" const LLUUID LLUUID::null; @@ -400,11 +401,16 @@ LLUUID LLUUID::operator^(const LLUUID& rhs) const return id; } +// WARNING: this algorithm SHALL NOT be changed. It is also used by the server +// and plays a role in some assets validation (e.g. clothing items). Changing +// it would cause invalid assets. void LLUUID::combine(const LLUUID& other, LLUUID& result) const { - HBXXH128 hash((const void*)mData, 16, false); // false = do not finalize - hash.update((const void*)other.mData, 16); - hash.digest(result); + LLMD5 md5_uuid; + md5_uuid.update((unsigned char*)mData, 16); + md5_uuid.update((unsigned char*)other.mData, 16); + md5_uuid.finalize(); + md5_uuid.raw_digest(result.mData); } LLUUID LLUUID::combine(const LLUUID &other) const -- cgit v1.2.3