glaurung

Fixture 48

gray code

C · 4 functions · 4 lanes · 16 of 16 function-lanes behave identically

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

Gray-code conversion and a bit-reversal permutation. The decode is an xor-shift reduction whose loop cannot be strength-reduced away, and the reversal is a masked swap ladder.

tests/decompiler_fixtures/src/48_gray_code.c source 
#include <stdint.h>

/* Gray-code conversion and a bit-reversal permutation.  The decode is an
 * xor-shift reduction whose loop cannot be strength-reduced away, and the
 * reversal is a masked swap ladder. */

#define GRAY_MAX 16

__attribute__((noinline)) uint32_t binary_to_gray(uint32_t value) {
    return value ^ (value >> 1);
}

__attribute__((noinline)) uint32_t gray_to_binary(uint32_t gray) {
    uint32_t value = gray;
    value ^= value >> 16;
    value ^= value >> 8;
    value ^= value >> 4;
    value ^= value >> 2;
    value ^= value >> 1;
    return value;
}

__attribute__((noinline)) uint32_t reverse_bits32(uint32_t value) {
    value = ((value & 0x55555555u) << 1) | ((value >> 1) & 0x55555555u);
    value = ((value & 0x33333333u) << 2) | ((value >> 2) & 0x33333333u);
    value = ((value & 0x0F0F0F0Fu) << 4) | ((value >> 4) & 0x0F0F0F0Fu);
    value = ((value & 0x00FF00FFu) << 8) | ((value >> 8) & 0x00FF00FFu);
    return (value << 16) | (value >> 16);
}

__attribute__((noinline)) int32_t
gray_sequence(uint32_t *output, int32_t count) {
    int32_t index;
    if (output == 0 || count < 0 || count > GRAY_MAX) {
        return -1;
    }
    for (index = 0; index < count; ++index) {
        output[index] = binary_to_gray((uint32_t)index);
    }
    return count;
}

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

4/4
binary_to_gray pass 6 lines 
// glaurung: binary_to_gray @ 0x1110
uint32_t binary_to_gray(uint32_t arg0) {
    // x86-64 prologue: save rbp
    // x86-64 epilogue: restore rbp
    return (unsigned int)(((unsigned long)(arg0) ^ (unsigned long)((unsigned int)(((unsigned long)(arg0) >> 1)))));
}
gray_sequence pass 30 lines 
// glaurung: gray_sequence @ 0x1210
int32_t gray_sequence(uint32_t * arg0, int32_t arg1) {
    extern unsigned int binary_to_gray(unsigned int);
    int index;
    int local_4;
    unsigned int var5;
    // x86-64 prologue: save rbp, frame 32 bytes
    if ((arg0 == 0)) {
        local_4 = -1;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    if (((long)(arg1) < 0)) {
        local_4 = -1;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    if (((((unsigned long)((unsigned int)(arg1)) == 16) | ((long)(arg1) < 16)) == 0)) {
        local_4 = -1;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    for (index = 0; (index < arg1); index++) {
        var5 = binary_to_gray((unsigned long)((unsigned int)(index)));
        arg0[(long)(index)] = var5;
    }
    local_4 = arg1;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
}
gray_to_binary pass 13 lines 
// glaurung: gray_to_binary @ 0x1130
uint32_t gray_to_binary(uint32_t arg0) {
    unsigned int value;
    // x86-64 prologue: save rbp
    value = arg0;
    value = ((unsigned int)(((unsigned int)(value) >> 16)) ^ value);
    value = ((unsigned int)(((unsigned int)(value) >> 8)) ^ value);
    value = ((unsigned int)(((unsigned int)(value) >> 4)) ^ value);
    value = ((unsigned int)(((unsigned int)(value) >> 2)) ^ value);
    value = ((unsigned int)(((unsigned int)(value) >> 1)) ^ value);
    // x86-64 epilogue: restore rbp
    return value;
}
reverse_bits32 pass 10 lines 
// glaurung: reverse_bits32 @ 0x1180
uint32_t reverse_bits32(uint32_t arg0) {
    // x86-64 prologue: save rbp
    arg0 = ((unsigned int)(((unsigned long)((unsigned int)((arg0 & 0x55555555))) << 1)) | (unsigned int)(((unsigned long)((unsigned int)(((unsigned int)(arg0) >> 1))) & 0x55555555)));
    arg0 = ((unsigned int)(((unsigned long)((unsigned int)((arg0 & 0x33333333))) << 2)) | (unsigned int)(((unsigned long)((unsigned int)(((unsigned int)(arg0) >> 2))) & 0x33333333)));
    arg0 = ((unsigned int)(((unsigned long)((unsigned int)((arg0 & 0xf0f0f0f))) << 4)) | (unsigned int)(((unsigned long)((unsigned int)(((unsigned int)(arg0) >> 4))) & 0xf0f0f0f)));
    arg0 = ((unsigned int)(((unsigned long)((unsigned int)((arg0 & 0xff00ff))) << 8)) | (unsigned int)(((unsigned long)((unsigned int)(((unsigned int)(arg0) >> 8))) & 0xff00ff)));
    // x86-64 epilogue: restore rbp
    return (unsigned int)(((unsigned long)((unsigned int)(((unsigned long)(arg0) << 16))) | (unsigned long)((unsigned int)(((unsigned long)(arg0) >> 16)))));
}

clang -O2

4/4
binary_to_gray pass 4 lines 
// glaurung: binary_to_gray @ 0x1110
uint32_t binary_to_gray(uint32_t arg0) {
    return (unsigned int)(((unsigned long)((unsigned int)(((unsigned long)(arg0) >> 1))) ^ arg0));
}
gray_sequence pass 39 lines 
// glaurung: gray_sequence @ 0x1190
int32_t gray_sequence(uint32_t * arg0, int32_t arg1) {
    extern unsigned int binary_to_gray(unsigned int);
    int index;
    long local_10;
    long local_18;
    long local_8;
    long var0;
    long var1;
    unsigned int var12;
    long var2;
    long var3;
    long var8;
    local_8 = var0;
    local_10 = var1;
    local_18 = var2;
    var3 = 0xffffffff;
    if ((arg0 == 0)) {
        // x86-64 epilogue: tear down frame
        return (unsigned int)(var3);
    }
    if (((unsigned long)(16) < (unsigned long)((unsigned long)((unsigned int)(arg1))))) {
        // x86-64 epilogue: tear down frame
        return (unsigned int)(var3);
    }
    if (((unsigned long)((unsigned int)(arg1)) == 0)) {
        return 0;
    }
    var8 = (long)arg0;
    var3 = (unsigned long)((unsigned int)(arg1));
    index = 0;
    do {
        var12 = binary_to_gray((unsigned long)((unsigned int)(index)));
        *(int *)((var8 + index * 4)) = var12;
        index = (index + 1);
    } while ((var3 != index));
    // x86-64 epilogue: tear down frame
    return (unsigned int)(var3);
}
gray_to_binary pass 13 lines 
// glaurung: gray_to_binary @ 0x1120
uint32_t gray_to_binary(uint32_t arg0) {
    unsigned int value;
    long var11;
    long var17;
    long var23;
    long var5;
    var5 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(((unsigned int)(arg0) >> 16))) ^ arg0)));
    var11 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var5)) >> 8))) ^ var5)));
    var17 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var11)) >> 4))) ^ var11)));
    var23 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var17)) >> 2))) ^ var17)));
    return (unsigned int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var23)) >> 1))) ^ var23));
}
reverse_bits32 pass 10 lines 
// glaurung: reverse_bits32 @ 0x1150
uint32_t reverse_bits32(uint32_t arg0) {
    int var0;
    long var12;
    long var21;
    var0 = (unsigned int)((((((arg0 & 255) << 24) | (((arg0 >> 8) & 255) << 16)) | (((arg0 >> 16) & 255) << 8)) | ((arg0 >> 24) & 255)));
    var12 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var0)) >> 4))) & 0xf0f0f0f))) | (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var0)) & 0xf0f0f0f))) << 4))))));
    var21 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var12)) >> 2))) & 0x33333333))) + ((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var12)) & 0x33333333))) * 4))));
    return (unsigned int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var21)) >> 1))) & 0x55555555))) + ((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var21)) & 0x55555555))) * 2)));
}

gcc -O0

4/4
binary_to_gray pass 6 lines 
// glaurung: binary_to_gray @ 0x1119
uint32_t binary_to_gray(uint32_t arg0) {
    // x86-64 prologue: save rbp
    // x86-64 epilogue: restore rbp
    return (unsigned int)(((unsigned long)((unsigned int)(((unsigned long)(arg0) >> 1))) ^ arg0));
}
gray_sequence pass 27 lines 
// glaurung: gray_sequence @ 0x11f5
int32_t gray_sequence(uint32_t * arg0, int32_t arg1) {
    extern unsigned int binary_to_gray(unsigned int);
    int index;
    long var7;
    unsigned int var8;
    // x86-64 prologue: save rbp, frame 8 bytes
    if ((arg0 == 0)) {
        // x86-64 epilogue: restore rbp
        return 0xffffffff;
    }
    if (((long)(arg1) < 0)) {
        // x86-64 epilogue: restore rbp
        return 0xffffffff;
    }
    if (((((unsigned long)((unsigned int)(arg1)) == 16) | ((long)(arg1) < 16)) == 0)) {
        // x86-64 epilogue: restore rbp
        return 0xffffffff;
    }
    for (index = 0; (index < arg1); index++) {
        var7 = (long)((((long)(index) * 4) + (long)arg0));
        var8 = binary_to_gray((unsigned long)((unsigned int)(index)));
        *(int *)((var7)) = var8;
    }
    // x86-64 epilogue: restore rbp
    return (unsigned int)(arg1);
}
gray_to_binary pass 13 lines 
// glaurung: gray_to_binary @ 0x112e
uint32_t gray_to_binary(uint32_t arg0) {
    unsigned int value;
    // x86-64 prologue: save rbp
    value = arg0;
    value = (value ^ (unsigned int)(((unsigned int)(value) >> 16)));
    value = (value ^ (unsigned int)(((unsigned int)(value) >> 8)));
    value = (value ^ (unsigned int)(((unsigned int)(value) >> 4)));
    value = (value ^ (unsigned int)(((unsigned int)(value) >> 2)));
    value = (value ^ (unsigned int)(((unsigned int)(value) >> 1)));
    // x86-64 epilogue: restore rbp
    return value;
}
reverse_bits32 pass 10 lines 
// glaurung: reverse_bits32 @ 0x1170
uint32_t reverse_bits32(uint32_t arg0) {
    // x86-64 prologue: save rbp
    arg0 = ((unsigned int)(((unsigned long)((unsigned int)(((unsigned int)(arg0) >> 1))) & 0x55555555)) | (unsigned int)(((unsigned long)((unsigned int)((arg0 + arg0))) & -0x55555556LL)));
    arg0 = ((unsigned int)(((unsigned long)((unsigned int)(((unsigned int)(arg0) >> 2))) & 0x33333333)) | (unsigned int)(((unsigned long)((unsigned int)((arg0 << 2))) & -0x33333334LL)));
    arg0 = ((unsigned int)(((unsigned long)((unsigned int)(((unsigned int)(arg0) >> 4))) & 0xf0f0f0f)) | (unsigned int)(((unsigned long)((unsigned int)((arg0 << 4))) & -0xf0f0f10LL)));
    arg0 = ((unsigned int)(((unsigned long)((unsigned int)(((unsigned int)(arg0) >> 8))) & 0xff00ff)) | (unsigned int)(((unsigned long)((unsigned int)((arg0 << 8))) & -0xff0100LL)));
    // x86-64 epilogue: restore rbp
    return (((unsigned long)(arg0) << 16) | ((unsigned long)(arg0) >> 16));
}

gcc -O2

4/4
binary_to_gray pass 4 lines 
// glaurung: binary_to_gray @ 0x1120
uint32_t binary_to_gray(uint32_t arg0) {
    return (unsigned int)(((unsigned long)((unsigned int)(((unsigned long)(arg0) >> 1))) ^ arg0));
}
gray_sequence pass 30 lines 
// glaurung: gray_sequence @ 0x11b0
int32_t gray_sequence(uint32_t * arg0, int32_t arg1) {
    extern unsigned int binary_to_gray(unsigned int);
    int index;
    long var1;
    long var2;
    long var3;
    unsigned int var6;
    long zf_8;
    if ((arg0 == 0)) {
        return (unsigned int)(-1);
    }
    var1 = (unsigned long)((unsigned int)(arg1));
    if (((unsigned long)(16) < (unsigned long)((unsigned long)((unsigned int)(arg1))))) {
        return 0xffffffff;
    } else {
        var2 = (long)arg0;
        var3 = (unsigned long)((unsigned int)((arg1 - 1)));
        index = 0;
        if (((unsigned long)((unsigned int)(arg1)) != 0)) {
            do {
                var6 = binary_to_gray((unsigned long)((unsigned int)(index)));
                *(int *)((var2 + index * 4)) = var6;
                zf_8 = (index == var3);
                index = (index + 1);
            } while ((zf_8 == 0));
        }
        return (unsigned int)(var1);
    }
}
gray_to_binary pass 13 lines 
// glaurung: gray_to_binary @ 0x1130
uint32_t gray_to_binary(uint32_t arg0) {
    unsigned int value;
    long var11;
    long var17;
    long var23;
    long var5;
    var5 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(((unsigned int)(arg0) >> 16))) ^ arg0)));
    var11 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var5)) >> 8))) ^ var5)));
    var17 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var11)) >> 4))) ^ var11)));
    var23 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var17)) >> 2))) ^ var17)));
    return (unsigned int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var23)) >> 1))) ^ var23));
}
reverse_bits32 pass 10 lines 
// glaurung: reverse_bits32 @ 0x1160
uint32_t reverse_bits32(uint32_t arg0) {
    long var10;
    long var20;
    long var32;
    var10 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)((arg0 + arg0))) & -0x55555556LL))) | (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(((unsigned int)(arg0) >> 1))) & 0x55555555))))));
    var20 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)((var10 * 4))) & -0x33333334LL))) | (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var10)) >> 2))) & 0x33333333))))));
    var32 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var20)) << 4))) & -0xf0f0f10LL))) | (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var20)) >> 4))) & 0xf0f0f0f))))));
    return (unsigned int)(((((((unsigned int)(var32) & 255) << 24) | ((((unsigned int)(var32) >> 8) & 255) << 16)) | ((((unsigned int)(var32) >> 16) & 255) << 8)) | (((unsigned int)(var32) >> 24) & 255)));
}

← 213 fixtures