glaurung

Fixture 52

hash functions

C · 3 functions · 4 lanes · 12 of 12 function-lanes behave identically

All 4 lanes recompile and return the same results as the original.

FNV-1a, a djb2 variant, and the MurmurHash3 finalizer. These are pure multiply/xor/shift chains: with no control flow to anchor on, an incorrect constant or shift width is immediately visible in the differential.

tests/decompiler_fixtures/src/52_hash_functions.c source 
#include <stdint.h>

/* FNV-1a, a djb2 variant, and the MurmurHash3 finalizer.  These are pure
 * multiply/xor/shift chains: with no control flow to anchor on, an incorrect
 * constant or shift width is immediately visible in the differential. */

#define HASH_MAX 16

__attribute__((noinline)) uint32_t
fnv1a_32(const uint8_t *data, int32_t length) {
    uint32_t hash = 2166136261u;
    int32_t index;
    if (data == 0 || length < 0 || length > HASH_MAX) {
        return 0;
    }
    for (index = 0; index < length; ++index) {
        hash ^= (uint32_t)data[index];
        hash *= 16777619u;
    }
    return hash;
}

__attribute__((noinline)) uint32_t
djb2_xor(const uint8_t *data, int32_t length) {
    uint32_t hash = 5381u;
    int32_t index;
    if (data == 0 || length < 0 || length > HASH_MAX) {
        return 0;
    }
    for (index = 0; index < length; ++index) {
        hash = ((hash << 5) + hash) ^ (uint32_t)data[index];
    }
    return hash;
}

__attribute__((noinline)) uint32_t murmur3_finalize(uint32_t value) {
    value ^= value >> 16;
    value *= 0x85EBCA6Bu;
    value ^= value >> 13;
    value *= 0xC2B2AE35u;
    value ^= value >> 16;
    return value;
}

Recovered C

Generated by glaurung decompile --style decbench at b47f6b43. baseline.json records the result after recompiling the C and calling it beside the original with seeded inputs.

clang -O0

3/3
djb2_xor pass 26 lines 
// glaurung: djb2_xor @ 0x1190
uint32_t djb2_xor(const uint8_t * arg0, int32_t arg1) {
    unsigned int hash;
    int index;
    int local_4;
    // x86-64 prologue: save rbp
    hash = 0x1505;
    if ((arg0 == 0)) {
        // x86-64 epilogue: restore rbp
        return 0;
    }
    if (((long)(arg1) < 0)) {
        // x86-64 epilogue: restore rbp
        return 0;
    }
    if (((((unsigned long)((unsigned int)(arg1)) == 16) | ((long)(arg1) < 16)) == 0)) {
        // x86-64 epilogue: restore rbp
        return 0;
    }
    for (index = 0; (index < arg1); index++) {
        hash = ((unsigned int)(((unsigned long)((unsigned int)((hash << 5))) + hash)) ^ (unsigned int)((unsigned char)(arg0[index])));
    }
    local_4 = hash;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
}
fnv1a_32 pass 27 lines 
// glaurung: fnv1a_32 @ 0x1100
uint32_t fnv1a_32(const uint8_t * arg0, int32_t arg1) {
    unsigned int hash;
    int index;
    int local_4;
    // x86-64 prologue: save rbp
    hash = -0x7ee3623bLL;
    if ((arg0 == 0)) {
        // x86-64 epilogue: restore rbp
        return 0;
    }
    if (((long)(arg1) < 0)) {
        // x86-64 epilogue: restore rbp
        return 0;
    }
    if (((((unsigned long)((unsigned int)(arg1)) == 16) | ((long)(arg1) < 16)) == 0)) {
        // x86-64 epilogue: restore rbp
        return 0;
    }
    for (index = 0; (index < arg1); index++) {
        hash = ((unsigned int)((unsigned char)(arg0[index])) ^ hash);
        hash = (hash * 0x1000193);
    }
    local_4 = hash;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
}
murmur3_finalize pass 11 lines 
// glaurung: murmur3_finalize @ 0x1220
uint32_t murmur3_finalize(uint32_t arg0) {
    // x86-64 prologue: save rbp
    arg0 = ((unsigned int)(((unsigned int)(arg0) >> 16)) ^ arg0);
    arg0 = (arg0 * -0x7a143595LL);
    arg0 = ((unsigned int)(((unsigned int)(arg0) >> 13)) ^ arg0);
    arg0 = (arg0 * -0x3d4d51cbLL);
    arg0 = ((unsigned int)(((unsigned int)(arg0) >> 16)) ^ arg0);
    // x86-64 epilogue: restore rbp
    return arg0;
}

clang -O2

3/3
djb2_xor pass 58 lines 
// glaurung: djb2_xor @ 0x11c0
uint32_t djb2_xor(const uint8_t * arg0, int32_t arg1) {
    int index;
    unsigned int hash;
    long ret;
    long var12;
    long var2;
    long var20;
    long var28;
    long var36;
    long var44;
    long var48;
    long var50;
    long var51;
    long var6;
    long var8;
    ret = 0;
    if ((arg0 != 0)) {
        ret = 0;
        if (((unsigned long)(16) < (unsigned long)((unsigned long)((unsigned int)(arg1))))) {
            return ret;
        }
        if (((unsigned long)((unsigned int)(arg1)) == 0)) {
            return 0x1505;
        }
        var2 = (unsigned long)((unsigned int)(arg1));
        var6 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(arg1)) & 3)));
        if (((unsigned long)(3) <= (unsigned long)(((unsigned long)((unsigned int)(arg1)) - 1)))) {
            var8 = (unsigned long)((unsigned int)((var2 & -4)));
            index = 0;
            var12 = 0x1505;
            do {
                var20 = (unsigned long)((unsigned int)(((unsigned int)((unsigned char)(*(char *)(((long)arg0 + index)))) ^ (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var12)) << 5))) + var12))))));
                var28 = (unsigned long)((unsigned int)(((unsigned int)((unsigned char)(*(char *)(((long)arg0 + index + 0x1)))) ^ (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var20)) << 5))) + var20))))));
                var36 = (unsigned long)((unsigned int)(((unsigned int)((unsigned char)(*(char *)(((long)arg0 + index + 0x2)))) ^ (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var28)) << 5))) + var28))))));
                ret = (unsigned long)((unsigned int)(((unsigned int)((unsigned char)(*(char *)(((long)arg0 + index + 0x3)))) ^ (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var36)) << 5))) + var36))))));
                index = (index + 4);
                var12 = ret;
                var44 = (unsigned long)((unsigned int)(index));
            } while ((var8 != index));
        } else {
            ret = 0x1505;
            var44 = 0;
        }
        if ((var6 == 0)) {
            return ret;
        }
        var48 = (long)(((long)arg0 + var44));
        var50 = 0;
        var51 = ret;
        do {
            ret = (unsigned long)((unsigned int)(((unsigned int)((unsigned char)(*(char *)((var48 + var50)))) ^ (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var51)) << 5))) + var51))))));
            var50 = (var50 + 1);
            var51 = ret;
        } while ((var6 != var50));
    }
    return ret;
}
fnv1a_32 pass 56 lines 
// glaurung: fnv1a_32 @ 0x1100
uint32_t fnv1a_32(const uint8_t * arg0, int32_t arg1) {
    int index;
    unsigned int hash;
    long ret;
    long var12;
    long var2;
    long var28;
    long var29;
    long var33;
    long var35;
    long var36;
    long var40;
    long var6;
    long var8;
    ret = 0;
    if ((arg0 != 0)) {
        ret = 0;
        if (((unsigned long)(16) < (unsigned long)((unsigned long)((unsigned int)(arg1))))) {
            return ret;
        }
        if (((unsigned long)((unsigned int)(arg1)) == 0)) {
            return 0x811c9dc5;
        }
        var2 = (unsigned long)((unsigned int)(arg1));
        var6 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(arg1)) & 3)));
        if (((unsigned long)(3) <= (unsigned long)(((unsigned long)((unsigned int)(arg1)) - 1)))) {
            var8 = (unsigned long)((unsigned int)((var2 & -4)));
            index = 0;
            var12 = 0x811c9dc5;
            do {
                var28 = ((unsigned long)((unsigned int)(((unsigned int)((unsigned char)(*(char *)(((long)arg0 + index + 0x3)))) ^ ((unsigned long)((unsigned int)(((unsigned int)((unsigned char)(*(char *)(((long)arg0 + index + 0x2)))) ^ ((unsigned long)((unsigned int)(((unsigned int)((unsigned char)(*(char *)(((long)arg0 + index + 0x1)))) ^ ((unsigned long)((unsigned int)(((unsigned int)((unsigned char)(*(char *)(((long)arg0 + index)))) ^ var12))) * 0x1000193)))) * 0x1000193)))) * 0x1000193)))) * 0x1000193);
                index = (index + 4);
                var12 = var28;
                var29 = (unsigned long)((unsigned int)(index));
            } while ((var8 != index));
        } else {
            var28 = 0x811c9dc5;
            var29 = 0;
        }
        ret = var28;
        if ((var6 == 0)) {
            return ret;
        }
        var33 = (long)(((long)arg0 + var29));
        var35 = 0;
        var36 = var28;
        do {
            var40 = ((unsigned long)((unsigned int)(((unsigned int)((unsigned char)(*(char *)((var33 + var35)))) ^ var36))) * 0x1000193);
            var35 = (var35 + 1);
            var36 = var40;
            ret = var40;
        } while ((var6 != var35));
    }
    return ret;
}
murmur3_finalize pass 8 lines 
// glaurung: murmur3_finalize @ 0x1280
uint32_t murmur3_finalize(uint32_t arg0) {
    int var13;
    int var6;
    var6 = ((unsigned int)(((unsigned long)((unsigned int)(((unsigned int)(arg0) >> 16))) ^ arg0)) * -0x7a143595LL);
    var13 = ((unsigned int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var6)) >> 13))) ^ var6)) * -0x3d4d51cbLL);
    return (unsigned int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var13)) >> 16))) ^ var13));
}

gcc -O0

3/3
djb2_xor pass 24 lines 
// glaurung: djb2_xor @ 0x1165
uint32_t djb2_xor(const uint8_t * arg0, int32_t arg1) {
    unsigned int hash;
    int index;
    // x86-64 prologue: save rbp
    hash = 0x1505;
    if ((arg0 == 0)) {
        // x86-64 epilogue: restore rbp
        return 0;
    }
    if (((long)(arg1) < 0)) {
        // x86-64 epilogue: restore rbp
        return 0;
    }
    if (((((unsigned long)((unsigned int)(arg1)) == 16) | ((long)(arg1) < 16)) == 0)) {
        // x86-64 epilogue: restore rbp
        return 0;
    }
    for (index = 0; (index < arg1); index++) {
        hash = ((unsigned int)((unsigned char)(((unsigned int)((unsigned char)(arg0[index])) & 255))) ^ (unsigned int)(((unsigned long)((unsigned int)((hash << 5))) + hash)));
    }
    // x86-64 epilogue: restore rbp
    return hash;
}
fnv1a_32 pass 25 lines 
// glaurung: fnv1a_32 @ 0x10f9
uint32_t fnv1a_32(const uint8_t * arg0, int32_t arg1) {
    unsigned int hash;
    int index;
    // x86-64 prologue: save rbp
    hash = -0x7ee3623bLL;
    if ((arg0 == 0)) {
        // x86-64 epilogue: restore rbp
        return 0;
    }
    if (((long)(arg1) < 0)) {
        // x86-64 epilogue: restore rbp
        return 0;
    }
    if (((((unsigned long)((unsigned int)(arg1)) == 16) | ((long)(arg1) < 16)) == 0)) {
        // x86-64 epilogue: restore rbp
        return 0;
    }
    for (index = 0; (index < arg1); index++) {
        hash = (hash ^ (unsigned int)((unsigned char)(((unsigned int)((unsigned char)(arg0[index])) & 255))));
        hash = (hash * 0x1000193);
    }
    // x86-64 epilogue: restore rbp
    return hash;
}
murmur3_finalize pass 11 lines 
// glaurung: murmur3_finalize @ 0x11d5
uint32_t murmur3_finalize(uint32_t arg0) {
    // x86-64 prologue: save rbp
    arg0 = (arg0 ^ (unsigned int)(((unsigned int)(arg0) >> 16)));
    arg0 = (arg0 * -0x7a143595LL);
    arg0 = (arg0 ^ (unsigned int)(((unsigned int)(arg0) >> 13)));
    arg0 = (arg0 * -0x3d4d51cbLL);
    arg0 = (arg0 ^ (unsigned int)(((unsigned int)(arg0) >> 16)));
    // x86-64 epilogue: restore rbp
    return arg0;
}

gcc -O2

3/3
djb2_xor pass 27 lines 
// glaurung: djb2_xor @ 0x1150
uint32_t djb2_xor(const uint8_t * arg0, int32_t arg1) {
    unsigned int hash;
    int index;
    long ret;
    long var2;
    long var4;
    long var5;
    if ((arg0 == 0)) {
        return 0;
    }
    if (((unsigned long)(16) < (unsigned long)((unsigned long)((unsigned int)(arg1))))) {
        return 0;
    }
    if (((unsigned long)((unsigned int)(arg1)) == 0)) {
        return 0x1505;
    }
    var2 = (long)((((long)arg0 + (unsigned long)((unsigned int)((arg1 - 1)))) + 1));
    var4 = 0x1505;
    var5 = (long)arg0;
    do {
        var5 = (var5 + 1);
        ret = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)((var4 + (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var4)) << 5)))))) ^ (unsigned int)((unsigned char)(*(char *)((var5 - 0x1)))))));
        var4 = ret;
    } while ((var5 != var2));
    return ret;
}
fnv1a_32 pass 27 lines 
// glaurung: fnv1a_32 @ 0x1100
uint32_t fnv1a_32(const uint8_t * arg0, int32_t arg1) {
    unsigned int hash;
    int index;
    long ret;
    long var2;
    long var4;
    int var5;
    if ((arg0 == 0)) {
        return 0;
    }
    if (((unsigned long)(16) < (unsigned long)((unsigned long)((unsigned int)(arg1))))) {
        return 0;
    }
    if (((unsigned long)((unsigned int)(arg1)) == 0)) {
        return 0x811c9dc5;
    }
    var2 = (long)((((long)arg0 + (unsigned long)((unsigned int)((arg1 - 1)))) + 1));
    ret = 0x811c9dc5;
    var4 = (long)arg0;
    do {
        var5 = (unsigned int)((unsigned char)(*(char *)((var4))));
        var4 = (var4 + 1);
        ret = ((unsigned long)((unsigned int)((ret ^ var5))) * 0x1000193);
    } while ((var4 != var2));
    return ret;
}
murmur3_finalize pass 8 lines 
// glaurung: murmur3_finalize @ 0x11a0
uint32_t murmur3_finalize(uint32_t arg0) {
    int var13;
    int var6;
    var6 = ((unsigned int)(((unsigned long)((unsigned int)(((unsigned int)(arg0) >> 16))) ^ arg0)) * -0x7a143595LL);
    var13 = ((unsigned int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var6)) >> 13))) ^ var6)) * -0x3d4d51cbLL);
    return (unsigned int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var13)) >> 16))) ^ var13));
}

← 213 fixtures