Apollon Oikonomopoulos
2018-Mar-26 12:57 UTC
murmurhash3 test failures on big-endian systems
Hi Aki, On 15:55 Mon 26 Mar , Aki Tuomi wrote:> On 26.03.2018 15:49, Apollon Oikonomopoulos wrote: > > Hi, > > > > The dovecot 2.3.0.1 Debian package currently fails to build on all > > big-endian architectures[1], due to murmurhash3 tests failing. The > > relevant output from e.g. s390x is: > > > > test-murmurhash3.c:22: Assert(#8) failed: memcmp(result, vectors[i].result, sizeof(result)) == 0 > > test-murmurhash3.c:22: Assert(#11) failed: memcmp(result, vectors[i].result, sizeof(result)) == 0 > > test-murmurhash3.c:22: Assert(#12) failed: memcmp(result, vectors[i].result, sizeof(result)) == 0 > > murmurhash3 (murmurhash3_32) ......................................... : FAILED > > test-murmurhash3.c:22: Assert(#1) failed: memcmp(result, vectors[i].result, sizeof(result)) == 0 > > test-murmurhash3.c:22: Assert(#2) failed: memcmp(result, vectors[i].result, sizeof(result)) == 0 > > test-murmurhash3.c:22: Assert(#3) failed: memcmp(result, vectors[i].result, sizeof(result)) == 0 > > test-murmurhash3.c:22: Assert(#4) failed: memcmp(result, vectors[i].result, sizeof(result)) == 0 > > test-murmurhash3.c:22: Assert(#5) failed: memcmp(result, vectors[i].result, sizeof(result)) == 0 > > test-murmurhash3.c:22: Assert(#6) failed: memcmp(result, vectors[i].result, sizeof(result)) == 0 > > test-murmurhash3.c:22: Assert(#7) failed: memcmp(result, vectors[i].result, sizeof(result)) == 0 > > test-murmurhash3.c:22: Assert(#8) failed: memcmp(result, vectors[i].result, sizeof(result)) == 0 > > test-murmurhash3.c:22: Assert(#9) failed: memcmp(result, vectors[i].result, sizeof(result)) == 0 > > test-murmurhash3.c:22: Assert(#10) failed: memcmp(result, vectors[i].result, sizeof(result)) == 0 > > test-murmurhash3.c:22: Assert(#11) failed: memcmp(result, vectors[i].result, sizeof(result)) == 0 > > test-murmurhash3.c:22: Assert(#12) failed: memcmp(result, vectors[i].result, sizeof(result)) == 0 > > test-murmurhash3.c:22: Assert(#13) failed: memcmp(result, vectors[i].result, sizeof(result)) == 0 > > murmurhash3 (murmurhash3_128) ........................................ : FAILED > > > > Looks like the murmurhash3 implementation in Dovecot is currently broken on > > big-endian systems. > > > > Regards, > > Apollon > > > > [1] https://buildd.debian.org/status/package.php?p=dovecot&suite=experimental > Hi! > > Thanks for reporting this, we'll look at it. It's not going to get fixed > on 2.3.1 though, but we can provide a patch for that.I'd be happy to test the patch, thanks! Apollon
On Mon, Mar 26, 2018 at 15:57:01 +0300, Apollon Oikonomopoulos wrote: ...> I'd be happy to test the patch, thanks!Ok, try the attached patch. (It is a first pass at the issue, so it may not be the final diff that'll end up getting committed. It'd be good to know if it actually fixes the issue for you - sadly, I don't have a big endian system to play with.) Thanks, Jeff. -- The obvious mathematical breakthrough would be development of an easy way to factor large prime numbers. - Bill Gates, The Road Ahead, pg. 265 -------------- next part -------------- diff --git a/src/lib/murmurhash3.c b/src/lib/murmurhash3.c index 45dcc22..d0336a1 100644 --- a/src/lib/murmurhash3.c +++ b/src/lib/murmurhash3.c @@ -94,6 +94,8 @@ void murmurhash3_32 (const void *key, size_t len, uint32_t seed, h1 = fmix32(h1); + h1 = cpu32_to_be(h1); + memcpy(out, &h1, sizeof(h1)); } @@ -206,6 +208,9 @@ void murmurhash3_128(const void *key, size_t len, uint32_t seed, h1 += h2; h2 += h1; + h1 = cpu64_to_be(h1); + h2 = cpu64_to_be(h2); + memcpy(out, &h1, sizeof(h1)); memcpy(out+sizeof(h1), &h2, sizeof(h2)); } @@ -323,6 +328,11 @@ void murmurhash3_128(const void *key, size_t len, uint32_t seed, h1 += h2; h1 += h3; h1 += h4; h2 += h1; h3 += h1; h4 += h1; + h1 = cpu32_to_be(h1); + h2 = cpu32_to_be(h2); + h3 = cpu32_to_be(h3); + h4 = cpu32_to_be(h4); + memcpy(out, &h1, sizeof(h1)); memcpy(out+sizeof(h1), &h2, sizeof(h2)); memcpy(out+sizeof(h1)*2, &h3, sizeof(h3)); diff --git a/src/lib/test-murmurhash3.c b/src/lib/test-murmurhash3.c index 9da3d28..4848fbd 100644 --- a/src/lib/test-murmurhash3.c +++ b/src/lib/test-murmurhash3.c @@ -7,7 +7,19 @@ struct murmur3_test_vectors { const char *input; size_t len; uint32_t seed; - uint32_t result[4]; /* fits all results */ + + /* murmurhash3_128() produces a different output on ILP32 and LP64 + systems (by design). Therefore, we must use different expected + results based on what system we're on. We define both all the + time, but use the below pre-processor magic to select which + version we'll use. */ + uint8_t result_ilp32[MURMURHASH3_128_RESULTBYTES]; /* fits all results */ + uint8_t result_lp64[MURMURHASH3_128_RESULTBYTES]; /* fits all results */ +#ifdef _LP64 +#define result result_lp64 +#else +#define result result_ilp32 +#endif }; static void test_murmurhash3_algorithm(const char *name, @@ -29,24 +41,49 @@ static void test_murmurhash3_algorithm(const char *name, static void test_murmurhash3_32(void) { + /* murmurhash3_32() produces the same output on both ILP32 and LP64 + systems, so use the same expected outputs for both */ struct murmur3_test_vectors vectors[] = { - { "", 0, 0, { 0, 0, 0, 0}}, - { "", 0, 0x1, { 0x514E28B7, 0, 0, 0 }}, - { "", 0, 0xFFFFFFFF, { 0x81F16F39, 0, 0, 0 }}, - { "\0\0\0\0", 4, 0, { 0x2362F9DE, 0, 0, 0 }}, - { "aaaa", 4, 0x9747b28c, { 0x5A97808A, 0, 0, 0 }}, - { "aaa", 3, 0x9747b28c, { 0x283E0130, 0, 0, 0 }}, - { "aa", 2, 0x9747b28c, { 0x5D211726, 0, 0, 0 }}, - { "a", 1, 0x9747b28c, { 0x7FA09EA6, 0, 0, 0 }}, - { "abcd", 4, 0x9747b28c, { 0xF0478627, 0, 0, 0 }}, - { "abc", 3, 0x9747b28c, { 0xC84A62DD, 0, 0, 0 }}, - { "ab", 2, 0x9747b28c, { 0x74875592, 0, 0, 0 }}, - { "Hello, world!", 13, 0x9747b28c, { 0x24884CBA, 0, 0, 0 }}, + { "", 0, 0, { 0, }, { 0, } }, + { "", 0, 0x1, + { 0x51, 0x4E, 0x28, 0xB7, }, + { 0x51, 0x4E, 0x28, 0xB7, } }, + { "", 0, 0xFFFFFFFF, + { 0x81, 0xF1, 0x6F, 0x39, }, + { 0x81, 0xF1, 0x6F, 0x39, } }, + { "\0\0\0\0", 4, 0, + { 0x23, 0x62, 0xF9, 0xDE, }, + { 0x23, 0x62, 0xF9, 0xDE, } }, + { "aaaa", 4, 0x9747b28c, + { 0x5A, 0x97, 0x80, 0x8A, }, + { 0x5A, 0x97, 0x80, 0x8A, } }, + { "aaa", 3, 0x9747b28c, + { 0x28, 0x3E, 0x01, 0x30, }, + { 0x28, 0x3E, 0x01, 0x30, } }, + { "aa", 2, 0x9747b28c, + { 0x5D, 0x21, 0x17, 0x26, }, + { 0x5D, 0x21, 0x17, 0x26, } }, + { "a", 1, 0x9747b28c, + { 0x7F, 0xA0, 0x9E, 0xA6, }, + { 0x7F, 0xA0, 0x9E, 0xA6, } }, + { "abcd", 4, 0x9747b28c, + { 0xF0, 0x47, 0x86, 0x27, }, + { 0xF0, 0x47, 0x86, 0x27, } }, + { "abc", 3, 0x9747b28c, + { 0xC8, 0x4A, 0x62, 0xDD, }, + { 0xC8, 0x4A, 0x62, 0xDD, } }, + { "ab", 2, 0x9747b28c, + { 0x74, 0x87, 0x55, 0x92, }, + { 0x74, 0x87, 0x55, 0x92, } }, + { "Hello, world!", 13, 0x9747b28c, + { 0x24, 0x88, 0x4C, 0xBA, }, + { 0x24, 0x88, 0x4C, 0xBA, } }, { "\xcf\x80\xcf\x80\xcf\x80\xcf\x80\xcf\x80\xcf\x80\xcf\x80\xcf\x80", 16, 0x9747b28c, - { 0xD58063C1, 0, 0, 0 } + { 0xD5, 0x80, 0x63, 0xC1, }, + { 0xD5, 0x80, 0x63, 0xC1, } }, /* 8 U+03C0 (Greek Small Letter Pi) */ { "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" @@ -56,7 +93,8 @@ static void test_murmurhash3_32(void) "aaaaaaaaaaaaaaaaaaaa", 256, 0x9747b28c, - { 0x37405BDC, 0, 0, 0 } + { 0x37, 0x40, 0x5B, 0xDC, }, + { 0x37, 0x40, 0x5B, 0xDC, } }, }; @@ -67,25 +105,73 @@ static void test_murmurhash3_32(void) static void test_murmurhash3_128(void) { + /* murmurhash3_128() produces a different output on ILP32 and LP64 + systems (by design). */ struct murmur3_test_vectors vectors[] = { -#ifdef _LP64 - { "", 0, 0x00000000, { 0x00000000, 0x00000000, 0x00000000, 0x00000000 }}, - { "", 0, 0x00000001, { 0x6eff5cb5, 0x4610abe5, 0x78f83583, 0x51622daa }}, - { "", 0, 0xffffffff, { 0x9d3bc9ec, 0x6af1df4d, 0x1ee6446b, 0x85742112 }}, - { "\0\0\0\0", 4, 0x00000000, { 0xd84c76bc, 0xcfa0f7dd, 0x1cf526f1, 0x58962316 }}, - { "aaaa", 4, 0x9747b28c, { 0x5e649bf0, 0xb4e0a5f7, 0x038c569f, 0xa5d3e8e9 }}, - { "aaa", 3, 0x9747b28c, { 0xe4c7466b, 0x8ea5e37a, 0x35dc931c, 0xf925bef0 }}, - { "aa", 2, 0x9747b28c, { 0xbee5bb1f, 0x12a698a9, 0x5e269401, 0xe93630ff }}, - { "a", 1, 0x9747b28c, { 0x2db25a1d, 0x5ce8d851, 0x9208f004, 0x9e6dab0f }}, - { "abcd", 4, 0x9747b28c, { 0xac553791, 0x49b4709e, 0xe9d3a7bb, 0x8a7e67e7 }}, - { "abc", 3, 0x9747b28c, { 0xbfc3cedc, 0x3743630d, 0x20b504bf, 0xcde0a234 }}, - { "ab", 2, 0x9747b28c, { 0x1a44280b, 0x8434eead, 0x63ce372b, 0x7eb933e7 }}, - { "Hello, world!", 13, 0x9747b28c, { 0x62a8392e, 0xedc485d6, 0x31d576ba, 0xf85e7e76 }}, + { "", 0, 0x00000000, { 0, }, { 0, }}, + { "", 0, 0x00000001, + { 0x88, 0xc4, 0xad, 0xec, 0x54, 0xd2, 0x01, 0xb9, + 0x54, 0xd2, 0x01, 0xb9, 0x54, 0xd2, 0x01, 0xb9 }, + { 0x46, 0x10, 0xab, 0xe5, 0x6e, 0xff, 0x5c, 0xb5, + 0x51, 0x62, 0x2d, 0xaa, 0x78, 0xf8, 0x35, 0x83 }}, + { "", 0, 0xffffffff, + { 0x05, 0x1e, 0x08, 0xa9, 0x98, 0x9d, 0x49, 0xf7, + 0x98, 0x9d, 0x49, 0xf7, 0x98, 0x9d, 0x49, 0xf7 }, + { 0x6a, 0xf1, 0xdf, 0x4d, 0x9d, 0x3b, 0xc9, 0xec, + 0x85, 0x74, 0x21, 0x12, 0x1e, 0xe6, 0x44, 0x6b }}, + { "\0\0\0\0", 4, 0x00000000, + { 0xcc, 0x06, 0x6f, 0x1f, 0x9e, 0x51, 0x78, 0x40, + 0x9e, 0x51, 0x78, 0x40, 0x9e, 0x51, 0x78, 0x40 }, + { 0xcf, 0xa0, 0xf7, 0xdd, 0xd8, 0x4c, 0x76, 0xbc, + 0x58, 0x96, 0x23, 0x16, 0x1c, 0xf5, 0x26, 0xf1 }}, + { "aaaa", 4, 0x9747b28c, + { 0x36, 0x80, 0x4c, 0xef, 0x2a, 0x61, 0xc2, 0x24, + 0x2a, 0x61, 0xc2, 0x24, 0x2a, 0x61, 0xc2, 0x24 }, + { 0xb4, 0xe0, 0xa5, 0xf7, 0x5e, 0x64, 0x9b, 0xf0, + 0xa5, 0xd3, 0xe8, 0xe9, 0x03, 0x8c, 0x56, 0x9f }}, + { "aaa", 3, 0x9747b28c, + { 0x83, 0x83, 0x89, 0xbe, 0x9a, 0xad, 0x7f, 0x88, + 0x9a, 0xad, 0x7f, 0x88, 0x9a, 0xad, 0x7f, 0x88 }, + { 0x8e, 0xa5, 0xe3, 0x7a, 0xe4, 0xc7, 0x46, 0x6b, + 0xf9, 0x25, 0xbe, 0xf0, 0x35, 0xdc, 0x93, 0x1c }}, + { "aa", 2, 0x9747b28c, + { 0xdf, 0xbe, 0x4a, 0x86, 0x4a, 0x9c, 0x35, 0x0b, + 0x4a, 0x9c, 0x35, 0x0b, 0x4a, 0x9c, 0x35, 0x0b }, + { 0x12, 0xa6, 0x98, 0xa9, 0xbe, 0xe5, 0xbb, 0x1f, + 0xe9, 0x36, 0x30, 0xff, 0x5e, 0x26, 0x94, 0x01 }}, + { "a", 1, 0x9747b28c, + { 0x08, 0x4e, 0xf9, 0x44, 0x21, 0xa1, 0x18, 0x6e, + 0x21, 0xa1, 0x18, 0x6e, 0x21, 0xa1, 0x18, 0x6e }, + { 0x5c, 0xe8, 0xd8, 0x51, 0x2d, 0xb2, 0x5a, 0x1d, + 0x9e, 0x6d, 0xab, 0x0f, 0x92, 0x08, 0xf0, 0x04 }}, + { "abcd", 4, 0x9747b28c, + { 0x47, 0x95, 0xc5, 0x29, 0xce, 0xc1, 0x88, 0x5e, + 0xce, 0xc1, 0x88, 0x5e, 0xce, 0xc1, 0x88, 0x5e }, + { 0x49, 0xb4, 0x70, 0x9e, 0xac, 0x55, 0x37, 0x91, + 0x8a, 0x7e, 0x67, 0xe7, 0xe9, 0xd3, 0xa7, 0xbb }}, + { "abc", 3, 0x9747b28c, + { 0xd6, 0x35, 0x9e, 0xaf, 0x48, 0xfc, 0x3a, 0xc3, + 0x48, 0xfc, 0x3a, 0xc3, 0x48, 0xfc, 0x3a, 0xc3 }, + { 0x37, 0x43, 0x63, 0x0d, 0xbf, 0xc3, 0xce, 0xdc, + 0xcd, 0xe0, 0xa2, 0x34, 0x20, 0xb5, 0x04, 0xbf }}, + { "ab", 2, 0x9747b28c, + { 0x38, 0x37, 0xd7, 0x95, 0xc7, 0xfe, 0x58, 0x96, + 0xc7, 0xfe, 0x58, 0x96, 0xc7, 0xfe, 0x58, 0x96 }, + { 0x84, 0x34, 0xee, 0xad, 0x1a, 0x44, 0x28, 0x0b, + 0x7e, 0xb9, 0x33, 0xe7, 0x63, 0xce, 0x37, 0x2b }}, + { "Hello, world!", 13, 0x9747b28c, + { 0x75, 0x6d, 0x54, 0x60, 0xbb, 0x87, 0x22, 0x16, + 0xb7, 0xd4, 0x8b, 0x7c, 0x53, 0xc8, 0xc6, 0x36 }, + { 0xed, 0xc4, 0x85, 0xd6, 0x62, 0xa8, 0x39, 0x2e, + 0xf8, 0x5e, 0x7e, 0x76, 0x31, 0xd5, 0x76, 0xba }}, { "\xcf\x80\xcf\x80\xcf\x80\xcf\x80\xcf\x80\xcf\x80\xcf\x80\xcf\x80", 16, 0x9747b28c, - { 0xc0361a1f, 0x96ea5bd8, 0x094be17b, 0xf8b72bd0 } + { 0xaf, 0x2a, 0xd3, 0x25, 0x3a, 0x74, 0xdf, 0x88, + 0x38, 0xcc, 0x75, 0x34, 0xf1, 0x97, 0xcc, 0x0d }, + { 0x96, 0xea, 0x5b, 0xd8, 0xc0, 0x36, 0x1a, 0x1f, + 0xf8, 0xb7, 0x2b, 0xd0, 0x09, 0x4b, 0xe1, 0x7b } }, { "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" @@ -95,38 +181,11 @@ static void test_murmurhash3_128(void) "aaaaaaaaaaaaaaaaaaaa", 256, 0x9747b28c, - { 0xa5dec1c4, 0x07bd957c, 0x1f6cee55, 0xc4d8bb8d } - }, -#else /* 32 bit test vectors */ - { "", 0, 0x00000000, { 0x00000000, 0x00000000, 0x00000000, 0x00000000 }}, - { "", 0, 0x00000001, { 0x88c4adec, 0x54d201b9, 0x54d201b9, 0x54d201b9 }}, - { "", 0, 0xffffffff, { 0x051e08a9, 0x989d49f7, 0x989d49f7, 0x989d49f7 }}, - { "\0\0\0\0", 4, 0x00000000, { 0xcc066f1f, 0x9e517840, 0x9e517840, 0x9e517840 }}, - { "aaaa", 4, 0x9747b28c, { 0x36804cef, 0x2a61c224, 0x2a61c224, 0x2a61c224 }}, - { "aaa", 3, 0x9747b28c, { 0x838389be, 0x9aad7f88, 0x9aad7f88, 0x9aad7f88 }}, - { "aa", 2, 0x9747b28c, { 0xdfbe4a86, 0x4a9c350b, 0x4a9c350b, 0x4a9c350b }}, - { "a", 1, 0x9747b28c, { 0x084ef944, 0x21a1186e, 0x21a1186e, 0x21a1186e }}, - { "abcd", 4, 0x9747b28c, { 0x4795c529, 0xcec1885e, 0xcec1885e, 0xcec1885e }}, - { "abc", 3, 0x9747b28c, { 0xd6359eaf, 0x48fc3ac3, 0x48fc3ac3, 0x48fc3ac3 }}, - { "ab", 2, 0x9747b28c, { 0x3837d795, 0xc7fe5896, 0xc7fe5896, 0xc7fe5896 }}, - { "Hello, world!", 13, 0x9747b28c, { 0x756d5460, 0xbb872216, 0xb7d48b7c, 0x53c8c636 }}, - { - "\xcf\x80\xcf\x80\xcf\x80\xcf\x80\xcf\x80\xcf\x80\xcf\x80\xcf\x80", - 16, - 0x9747b28c, - { 0xaf2ad325, 0x3a74df88, 0x38cc7534, 0xf197cc0d } + { 0xd3, 0xf2, 0xb7, 0xbb, 0xf6, 0x66, 0xc0, 0xcc, + 0xd4, 0xa4, 0x00, 0x60, 0x5e, 0xc8, 0xd3, 0x2a }, + { 0x07, 0xbd, 0x95, 0x7c, 0xa5, 0xde, 0xc1, 0xc4, + 0xc4, 0xd8, 0xbb, 0x8d, 0x1f, 0x6c, 0xee, 0x55 } }, - { - "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" - "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" - "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" - "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" - "aaaaaaaaaaaaaaaaaaaa", - 256, - 0x9747b28c, - { 0xd3f2b7bb, 0xf666c0cc, 0xd4a40060, 0x5ec8d32a } - }, -#endif }; test_murmurhash3_algorithm("murmurhash3_128", murmurhash3_128,
Apollon Oikonomopoulos
2018-Mar-27 08:31 UTC
murmurhash3 test failures on big-endian systems
Hi, On 12:55 Mon 26 Mar , Josef 'Jeff' Sipek wrote:> On Mon, Mar 26, 2018 at 15:57:01 +0300, Apollon Oikonomopoulos wrote: > ... > > I'd be happy to test the patch, thanks! > > Ok, try the attached patch. (It is a first pass at the issue, so it may not > be the final diff that'll end up getting committed. It'd be good to know if > it actually fixes the issue for you - sadly, I don't have a big endian > system to play with.)Thanks for the quick response! Unfortunately still fails, although with fewer assertion errors than before: test-murmurhash3.c:34: Assert(#8) failed: memcmp(result, vectors[i].result, sizeof(result)) == 0 test-murmurhash3.c:34: Assert(#11) failed: memcmp(result, vectors[i].result, sizeof(result)) == 0 test-murmurhash3.c:34: Assert(#12) failed: memcmp(result, vectors[i].result, sizeof(result)) == 0 murmurhash3 (murmurhash3_32) ......................................... : FAILED test-murmurhash3.c:34: Assert(#12) failed: memcmp(result, vectors[i].result, sizeof(result)) == 0 murmurhash3 (murmurhash3_128) ........................................ : FAILED Regards, Apollon