mirror of
https://github.com/brazilofmux/tinymux
synced 2026-08-13 00:23:11 -04:00
9bd2e02c1f
Closes #1454. Six UBSan reports from a sanitizer smoke run (#1440): svdhash.cpp:183: load of misaligned address 0x602000000553 for type 'const uint32_t', which requires 4 byte alignment svdhash.cpp:188: ... 0x602000000557 ... svdhash.cpp:202: ... 0x602000000372 ... The three reads are the fast path of CRC32_ProcessBuffer, guarded by UNALIGNED32 && WORDS_LITTLEENDIAN. That guard is not wrong about the hardware -- it records that the TARGET tolerates an unaligned 32-bit load -- but it does not make *reinterpret_cast<const uint32_t *>(p) defined in C++, and the compiler is entitled to assume the alignment it was promised. memcpy is the portable spelling of the same operation and folds to the same single load, so this keeps the fast path rather than falling back to the byte-at-a-time branch. VALUE STABILITY IS THE POINT HERE. This is the attribute-lookup hash; a changed value would invalidate every existing database, so "should be the same" is not good enough. Old and new linked against the same probe over every offset 0..7 within an over-aligned block and every length 0..40 -- 329 hashes, covering both the <=16 switch and the bulk loop: diff old new -> IDENTICAL, including the accumulator over all 329. Verified the reports are gone against the run that produced them, since a synthetic probe does not reproduce the misalignment -- the pBuffer -= 16 - nBuffer adjustment lands my chosen offsets back on a boundary. Full sanitizer smoke: before svdhash 6 reports after svdhash 0 reports smoke 1497 passed, 0 failed, 315/315 The remaining reports on master are #1455 (fix in #1459) and #1456. Co-Authored-By: Claude Opus 5 <noreply@anthropic.com>
324 lines
14 KiB
C++
324 lines
14 KiB
C++
/*! \file svdhash.cpp
|
|
* \brief CRC32 and hash utilities.
|
|
*
|
|
*/
|
|
|
|
#include "copyright.h"
|
|
#include "autoconf.h"
|
|
#include "config.h"
|
|
#include "core.h"
|
|
|
|
static const uint32_t CRC32_Table[256] =
|
|
{
|
|
0x00000000, 0x77073096, 0xee0e612c, 0x990951ba,
|
|
0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3,
|
|
0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
|
|
0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91,
|
|
0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de,
|
|
0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
|
|
0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec,
|
|
0x14015c4f, 0x63066cd9, 0xfa0f3d63, 0x8d080df5,
|
|
0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
|
|
0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b,
|
|
0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940,
|
|
0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
|
|
0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116,
|
|
0x21b4f4b5, 0x56b3c423, 0xcfba9599, 0xb8bda50f,
|
|
0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
|
|
0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d,
|
|
0x76dc4190, 0x01db7106, 0x98d220bc, 0xefd5102a,
|
|
0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
|
|
0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818,
|
|
0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01,
|
|
0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
|
|
0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457,
|
|
0x65b0d9c6, 0x12b7e950, 0x8bbeb8ea, 0xfcb9887c,
|
|
0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
|
|
0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2,
|
|
0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb,
|
|
0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
|
|
0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9,
|
|
0x5005713c, 0x270241aa, 0xbe0b1010, 0xc90c2086,
|
|
0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
|
|
0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4,
|
|
0x59b33d17, 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad,
|
|
0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
|
|
0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683,
|
|
0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8,
|
|
0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
|
|
0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe,
|
|
0xf762575d, 0x806567cb, 0x196c3671, 0x6e6b06e7,
|
|
0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
|
|
0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5,
|
|
0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252,
|
|
0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
|
|
0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60,
|
|
0xdf60efc3, 0xa867df55, 0x316e8eef, 0x4669be79,
|
|
0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
|
|
0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f,
|
|
0xc5ba3bbe, 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04,
|
|
0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
|
|
0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a,
|
|
0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713,
|
|
0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
|
|
0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21,
|
|
0x86d3d2d4, 0xf1d4e242, 0x68ddb3f8, 0x1fda836e,
|
|
0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
|
|
0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c,
|
|
0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45,
|
|
0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
|
|
0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db,
|
|
0xaed16a4a, 0xd9d65adc, 0x40df0b66, 0x37d83bf0,
|
|
0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
|
|
0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6,
|
|
0xbad03605, 0xcdd70693, 0x54de5729, 0x23d967bf,
|
|
0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
|
|
0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
|
|
};
|
|
|
|
// Portable CRC-32 routine. These slower routines are less compiler and
|
|
// platform dependent and still get the job done.
|
|
//
|
|
// A 32-bit load from a possibly-unaligned address.
|
|
//
|
|
// UNALIGNED32 records that the TARGET tolerates such a load; it does not make
|
|
// *reinterpret_cast<const uint32_t *>(p) defined in C++, and UndefinedBehavior-
|
|
// Sanitizer reports each one (#1454). memcpy is the portable spelling of the
|
|
// same operation and every compiler this builds with folds it to the single
|
|
// load the cast produced -- so the hash values are bit-identical, which is the
|
|
// property that matters here: this is the attribute-lookup hash, and a changed
|
|
// value would invalidate every existing database.
|
|
//
|
|
static inline uint32_t mux_read_u32(const uint8_t *p)
|
|
{
|
|
uint32_t v;
|
|
memcpy(&v, p, sizeof(v));
|
|
return v;
|
|
}
|
|
|
|
uint32_t CRC32_ProcessBuffer
|
|
(
|
|
uint32_t ulCrc,
|
|
const void *arg_pBuffer,
|
|
size_t nBuffer
|
|
)
|
|
{
|
|
const uint8_t *pBuffer = reinterpret_cast<const uint8_t *>(arg_pBuffer);
|
|
|
|
ulCrc = ~ulCrc;
|
|
while (nBuffer--)
|
|
{
|
|
ulCrc = CRC32_Table[(*pBuffer++) ^ static_cast<uint8_t>(ulCrc)] ^ (ulCrc >> 8);
|
|
}
|
|
return ~ulCrc;
|
|
}
|
|
|
|
uint32_t CRC32_ProcessInteger(uint32_t nInteger)
|
|
{
|
|
uint32_t ulCrc;
|
|
ulCrc = ~nInteger;
|
|
ulCrc = CRC32_Table[static_cast<uint8_t>(ulCrc)] ^ (ulCrc >> 8);
|
|
ulCrc = CRC32_Table[static_cast<uint8_t>(ulCrc)] ^ (ulCrc >> 8);
|
|
ulCrc = CRC32_Table[static_cast<uint8_t>(ulCrc)] ^ (ulCrc >> 8);
|
|
ulCrc = CRC32_Table[static_cast<uint8_t>(ulCrc)] ^ (ulCrc >> 8);
|
|
return ~ulCrc;
|
|
}
|
|
|
|
uint32_t CRC32_ProcessInteger2(uint32_t nInteger1, uint32_t nInteger2)
|
|
{
|
|
uint32_t ulCrc;
|
|
ulCrc = ~nInteger1;
|
|
ulCrc = CRC32_Table[static_cast<uint8_t>(ulCrc)] ^ (ulCrc >> 8);
|
|
ulCrc = CRC32_Table[static_cast<uint8_t>(ulCrc)] ^ (ulCrc >> 8);
|
|
ulCrc = CRC32_Table[static_cast<uint8_t>(ulCrc)] ^ (ulCrc >> 8);
|
|
ulCrc = CRC32_Table[static_cast<uint8_t>(ulCrc)] ^ (ulCrc >> 8);
|
|
ulCrc ^= nInteger2;
|
|
ulCrc = CRC32_Table[static_cast<uint8_t>(ulCrc)] ^ (ulCrc >> 8);
|
|
ulCrc = CRC32_Table[static_cast<uint8_t>(ulCrc)] ^ (ulCrc >> 8);
|
|
ulCrc = CRC32_Table[static_cast<uint8_t>(ulCrc)] ^ (ulCrc >> 8);
|
|
ulCrc = CRC32_Table[static_cast<uint8_t>(ulCrc)] ^ (ulCrc >> 8);
|
|
return ~ulCrc;
|
|
}
|
|
|
|
#define DO1(buf,i) {s1 += buf[i]; s2 += s1;}
|
|
#define DO2(buf,i) DO1(buf,i); DO1(buf,i+1);
|
|
#define DO4(buf,i) DO2(buf,i); DO2(buf,i+2);
|
|
#define DO8(buf,i) DO4(buf,i); DO4(buf,i+4);
|
|
#define DO16(buf) DO8(buf,0); DO8(buf,8);
|
|
|
|
/*! \brief Calculate hash from string of given length.
|
|
*
|
|
* HASH_ProcesBuffer() uses a combination of CRC-32 and Adler-32. For strings
|
|
* up to 16 bytes long, it uses CRC-32 to preserve most of the string's
|
|
* information. For medium-sized strings, it switches to Adler-32 which is
|
|
* much faster than CRC-32 for strings that size but does not preserve as
|
|
* much information as CRC-32. Medium-sized strings have more information
|
|
* than small strings anyway, so losing a little is not an issue. Adler-32
|
|
* will eventually overflow, so CRC-32 is again used to squeeze the sums down
|
|
* without performing the very costly division/modulus normally part of
|
|
* Adler-32.
|
|
*
|
|
* This outperforms Adler-32 for small, medium, and long strings. It also
|
|
* outperforms all other tested hashes for medium and long strings. For short
|
|
* strings, it is still fast, but not as fast as some quick-and-dirty hashes.
|
|
* The tradeoff is that the time spent gleaning information from small strings
|
|
* pays for itself with fewer probes into any hash table.
|
|
*
|
|
* The cost for shorter strings is somewhat compensated by using
|
|
* CRC32_ProcessInteger() and CRC32_ProcessInteger2() instead.
|
|
*
|
|
* \param ulHash Hash previously returned or zero (0) if first call.
|
|
* \param arg_pBuffer String to be hashed.
|
|
* \param nBuffer Size (in bytes) of the above buffer.
|
|
* \return Resulting hash value.
|
|
*/
|
|
|
|
uint32_t HASH_ProcessBuffer
|
|
(
|
|
uint32_t ulHash,
|
|
const void *arg_pBuffer,
|
|
size_t nBuffer
|
|
)
|
|
{
|
|
const uint8_t *pBuffer = reinterpret_cast<const uint8_t *>(arg_pBuffer);
|
|
ulHash = ~ulHash;
|
|
|
|
if (nBuffer <= 16)
|
|
{
|
|
pBuffer -= 16 - nBuffer;
|
|
switch (nBuffer)
|
|
{
|
|
case 16: ulHash = CRC32_Table[pBuffer[0] ^ static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
case 15: ulHash = CRC32_Table[pBuffer[1] ^ static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
case 14: ulHash = CRC32_Table[pBuffer[2] ^ static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
case 13: ulHash = CRC32_Table[pBuffer[3] ^ static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
case 12: ulHash = CRC32_Table[pBuffer[4] ^ static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
case 11: ulHash = CRC32_Table[pBuffer[5] ^ static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
case 10: ulHash = CRC32_Table[pBuffer[6] ^ static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
case 9: ulHash = CRC32_Table[pBuffer[7] ^ static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
#if defined(UNALIGNED32) && defined(WORDS_LITTLEENDIAN)
|
|
case 8: // Read via memcpy rather than a cast. UNALIGNED32 says the TARGET
|
|
// tolerates an unaligned 32-bit load; it does not make the cast
|
|
// defined in C++, and UBSan reports every one of these (#1454).
|
|
// memcpy is the portable spelling and compiles to the same single
|
|
// load here, so the hash values are unchanged -- which matters,
|
|
// because this is the attribute-lookup hash and a changed value
|
|
// would invalidate every existing database.
|
|
//
|
|
ulHash ^= mux_read_u32(pBuffer + 8);
|
|
ulHash = CRC32_Table[static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
ulHash = CRC32_Table[static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
ulHash = CRC32_Table[static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
ulHash = CRC32_Table[static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
ulHash ^= mux_read_u32(pBuffer + 12);
|
|
ulHash = CRC32_Table[static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
ulHash = CRC32_Table[static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
ulHash = CRC32_Table[static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
ulHash = CRC32_Table[static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
return ~ulHash;
|
|
#else
|
|
case 8: ulHash = CRC32_Table[pBuffer[8] ^ static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
#endif
|
|
|
|
case 7: ulHash = CRC32_Table[pBuffer[9] ^ static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
case 6: ulHash = CRC32_Table[pBuffer[10] ^ static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
case 5: ulHash = CRC32_Table[pBuffer[11] ^ static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
#if defined(UNALIGNED32) && defined(WORDS_LITTLEENDIAN)
|
|
case 4: ulHash ^= mux_read_u32(pBuffer + 12);
|
|
ulHash = CRC32_Table[static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
ulHash = CRC32_Table[static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
ulHash = CRC32_Table[static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
ulHash = CRC32_Table[static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
return ~ulHash;
|
|
#else
|
|
case 4: ulHash = CRC32_Table[pBuffer[12] ^ static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
#endif
|
|
|
|
case 3: ulHash = CRC32_Table[pBuffer[13] ^ static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
case 2: ulHash = CRC32_Table[pBuffer[14] ^ static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
case 1: ulHash = CRC32_Table[pBuffer[15] ^ static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
case 0: return ~ulHash;
|
|
}
|
|
}
|
|
|
|
size_t nSmall = nBuffer & 15;
|
|
size_t nMedium = (nBuffer >> 4) & 255;
|
|
size_t nLarge = nBuffer >> 12;
|
|
|
|
uint32_t s1 = ulHash & 0xFFFF;
|
|
uint32_t s2 = (ulHash >> 16) & 0xFFFF;
|
|
|
|
while (nLarge--)
|
|
{
|
|
int k = 256;
|
|
while (k)
|
|
{
|
|
DO16(pBuffer);
|
|
pBuffer += 16;
|
|
k--;
|
|
}
|
|
ulHash = ~s1;
|
|
ulHash = CRC32_Table[static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
ulHash = CRC32_Table[static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
ulHash = CRC32_Table[static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
ulHash = CRC32_Table[static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
ulHash ^= s2;
|
|
ulHash = CRC32_Table[static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
ulHash = CRC32_Table[static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
ulHash = CRC32_Table[static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
ulHash = CRC32_Table[static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
ulHash = ~ulHash;
|
|
s1 = ulHash & 0xFFFF;
|
|
s2 = (ulHash >> 16) & 0xFFFF;
|
|
}
|
|
|
|
while (nMedium--)
|
|
{
|
|
DO16(pBuffer);
|
|
pBuffer += 16;
|
|
}
|
|
|
|
pBuffer -= 15 - nSmall;
|
|
switch (nSmall)
|
|
{
|
|
case 15: s1 += pBuffer[0]; s2 += s1;
|
|
case 14: s1 += pBuffer[1]; s2 += s1;
|
|
case 13: s1 += pBuffer[2]; s2 += s1;
|
|
case 12: s1 += pBuffer[3]; s2 += s1;
|
|
case 11: s1 += pBuffer[4]; s2 += s1;
|
|
case 10: s1 += pBuffer[5]; s2 += s1;
|
|
case 9: s1 += pBuffer[6]; s2 += s1;
|
|
case 8: s1 += pBuffer[7]; s2 += s1;
|
|
case 7: s1 += pBuffer[8]; s2 += s1;
|
|
case 6: s1 += pBuffer[9]; s2 += s1;
|
|
case 5: s1 += pBuffer[10]; s2 += s1;
|
|
case 4: s1 += pBuffer[11]; s2 += s1;
|
|
case 3: s1 += pBuffer[12]; s2 += s1;
|
|
case 2: s1 += pBuffer[13]; s2 += s1;
|
|
case 1: s1 += pBuffer[14]; s2 += s1;
|
|
case 0: break;
|
|
}
|
|
|
|
ulHash = ~s1;
|
|
ulHash = CRC32_Table[static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
ulHash = CRC32_Table[static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
ulHash = CRC32_Table[static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
ulHash = CRC32_Table[static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
ulHash ^= s2;
|
|
ulHash = CRC32_Table[static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
ulHash = CRC32_Table[static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
ulHash = CRC32_Table[static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
ulHash = CRC32_Table[static_cast<uint8_t>(ulHash)] ^ (ulHash >> 8);
|
|
return ~ulHash;
|
|
}
|
|
|
|
uint32_t munge_hash(const UTF8 *pBuffer)
|
|
{
|
|
uint32_t h = 0;
|
|
while (*pBuffer)
|
|
{
|
|
h ^= (h << 5) + (h >> 2) + CRC32_Table[static_cast<unsigned char>(*pBuffer++)];
|
|
}
|
|
return h;
|
|
}
|
|
|