glaurung

Fixture 117

modular arithmetic

C · 5 functions · 4 lanes · 20 of 20 function-lanes behave identically

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

Unsigned arithmetic is defined modulo 2^N, which makes overflow a documented result rather than a hazard. Signed overflow is avoided throughout by doing the arithmetic in unsigned and converting back.

tests/decompiler_fixtures/src/117_modular_arithmetic.c source 
#include <stdint.h>

/* Unsigned arithmetic is defined modulo 2^N, which makes overflow a documented
 * result rather than a hazard. Signed overflow is avoided throughout by doing
 * the arithmetic in unsigned and converting back. */

__attribute__((noinline)) uint32_t wraps_to_zero(uint32_t value) {
    return value + (0u - value);
}

__attribute__((noinline)) uint32_t maximum_plus_one(void) {
    uint32_t maximum = 0xFFFFFFFFu;
    return maximum + 1u;
}

__attribute__((noinline)) int32_t
signed_overflow_avoided(int32_t left, int32_t right) {
    /* Computing in unsigned then converting is implementation-defined, not
     * undefined, and every target here wraps two's-complement. */
    return (int32_t)((uint32_t)left + (uint32_t)right);
}

__attribute__((noinline)) uint32_t
modular_exponent_of_two(int32_t exponent) {
    /* Shifting by 32 would be undefined; the identity is spelled out instead. */
    if (exponent < 0 || exponent > 31) {
        return 0u;
    }
    return 1u << (uint32_t)exponent;
}

__attribute__((noinline)) int32_t
absolute_without_branch(int32_t value) {
    uint32_t bits = (uint32_t)value;
    uint32_t mask = (uint32_t)(value >> 31);
    /* (v ^ mask) - mask, all in unsigned so INT32_MIN does not trap. */
    return (int32_t)((bits ^ mask) - mask);
}

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

5/5
absolute_without_branch pass 10 lines 
// glaurung: absolute_without_branch @ 0x11a0
int32_t absolute_without_branch(int32_t arg0) {
    unsigned int bits;
    unsigned int mask;
    // x86-64 prologue: save rbp
    bits = arg0;
    mask = ((int)(arg0) >> 31);
    // x86-64 epilogue: restore rbp
    return (unsigned int)(((unsigned long)((unsigned int)(((unsigned long)(bits) ^ mask))) - mask));
}
maximum_plus_one pass 8 lines 
// glaurung: maximum_plus_one @ 0x1120
uint32_t maximum_plus_one(void) {
    unsigned int maximum;
    // x86-64 prologue: save rbp
    maximum = -1;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(((unsigned long)(maximum) + 1));
}
modular_exponent_of_two pass 16 lines 
// glaurung: modular_exponent_of_two @ 0x1160
uint32_t modular_exponent_of_two(int32_t arg0) {
    int local_4;
    // x86-64 prologue: save rbp
    if (((long)(arg0) < 0)) {
        // x86-64 epilogue: restore rbp
        return 0;
    }
    if (((((unsigned long)((unsigned int)(arg0)) == 31) | ((long)(arg0) < 31)) == 0)) {
        // x86-64 epilogue: restore rbp
        return 0;
    }
    local_4 = (1 << ((unsigned long)((unsigned int)(arg0)) & 31));
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
}
signed_overflow_avoided pass 6 lines 
// glaurung: signed_overflow_avoided @ 0x1140
int32_t signed_overflow_avoided(int32_t arg0, int32_t arg1) {
    // x86-64 prologue: save rbp
    // x86-64 epilogue: restore rbp
    return (unsigned int)(((unsigned long)((unsigned int)(arg0)) + arg1));
}
wraps_to_zero pass 6 lines 
// glaurung: wraps_to_zero @ 0x1100
uint32_t wraps_to_zero(uint32_t arg0) {
    // x86-64 prologue: save rbp
    // x86-64 epilogue: restore rbp
    return (unsigned int)(((unsigned long)(arg0) + (unsigned long)((unsigned int)((0 - arg0)))));
}

clang -O2

5/5
absolute_without_branch pass 6 lines 
// glaurung: absolute_without_branch @ 0x1150
int32_t absolute_without_branch(int32_t arg0) {
    long t0;
    t0 = (-(unsigned long)((unsigned int)(arg0)));
    return (((long)((int)(t0)) < 0) ? arg0 : t0);
}
maximum_plus_one pass 4 lines 
// glaurung: maximum_plus_one @ 0x1110
uint32_t maximum_plus_one(void) {
    return 0;
}
modular_exponent_of_two pass 4 lines 
// glaurung: modular_exponent_of_two @ 0x1130
uint32_t modular_exponent_of_two(int32_t arg0) {
    return (((unsigned long)((unsigned long)((unsigned int)(arg0))) < (unsigned long)(32)) ? (unsigned long)((unsigned int)((1 << ((unsigned long)((unsigned int)(arg0)) & 31)))) : 0);
}
signed_overflow_avoided pass 4 lines 
// glaurung: signed_overflow_avoided @ 0x1120
int32_t signed_overflow_avoided(int32_t arg0, int32_t arg1) {
    return (unsigned int)((arg0 + arg1));
}
wraps_to_zero pass 4 lines 
// glaurung: wraps_to_zero @ 0x1100
uint32_t wraps_to_zero(uint32_t arg0) {
    return 0;
}

gcc -O0

5/5
absolute_without_branch pass 10 lines 
// glaurung: absolute_without_branch @ 0x1168
int32_t absolute_without_branch(int32_t arg0) {
    unsigned int bits;
    unsigned int mask;
    // x86-64 prologue: save rbp
    bits = arg0;
    mask = ((int)(arg0) >> 31);
    // x86-64 epilogue: restore rbp
    return (unsigned int)(((unsigned long)((unsigned int)(((unsigned long)(bits) ^ mask))) - mask));
}
maximum_plus_one pass 8 lines 
// glaurung: maximum_plus_one @ 0x110b
uint32_t maximum_plus_one(void) {
    unsigned int maximum;
    // x86-64 prologue: save rbp
    maximum = -1;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(((unsigned long)(maximum) + 1));
}
modular_exponent_of_two pass 14 lines 
// glaurung: modular_exponent_of_two @ 0x113a
uint32_t modular_exponent_of_two(int32_t arg0) {
    // x86-64 prologue: save rbp
    if (((long)(arg0) < 0)) {
        // x86-64 epilogue: restore rbp
        return 0;
    }
    if (((((unsigned long)((unsigned int)(arg0)) == 31) | ((long)(arg0) < 31)) == 0)) {
        // x86-64 epilogue: restore rbp
        return 0;
    }
    // x86-64 epilogue: restore rbp
    return (unsigned int)((1 << ((unsigned long)((unsigned int)(arg0)) & 31)));
}
signed_overflow_avoided pass 6 lines 
// glaurung: signed_overflow_avoided @ 0x1122
int32_t signed_overflow_avoided(int32_t arg0, int32_t arg1) {
    // x86-64 prologue: save rbp
    // x86-64 epilogue: restore rbp
    return (unsigned int)(((unsigned long)((unsigned int)(arg1)) + (unsigned long)((unsigned int)(arg0))));
}
wraps_to_zero pass 6 lines 
// glaurung: wraps_to_zero @ 0x10f9
uint32_t wraps_to_zero(uint32_t arg0) {
    // x86-64 prologue: save rbp
    // x86-64 epilogue: restore rbp
    return 0;
}

gcc -O2

5/5
absolute_without_branch pass 7 lines 
// glaurung: absolute_without_branch @ 0x1150
int32_t absolute_without_branch(int32_t arg0) {
    unsigned int mask;
    unsigned int bits;
    mask = (unsigned long)((unsigned int)(((int)(arg0) >> 31)));
    return (unsigned int)(((unsigned long)((unsigned int)((arg0 ^ mask))) - mask));
}
maximum_plus_one pass 4 lines 
// glaurung: maximum_plus_one @ 0x1110
uint32_t maximum_plus_one(void) {
    return 0;
}
modular_exponent_of_two pass 4 lines 
// glaurung: modular_exponent_of_two @ 0x1130
uint32_t modular_exponent_of_two(int32_t arg0) {
    return (((unsigned long)(32) <= (unsigned long)((unsigned long)((unsigned int)(arg0)))) ? 0 : (unsigned long)((unsigned int)((1 << ((unsigned long)((unsigned int)(arg0)) & 31)))));
}
signed_overflow_avoided pass 4 lines 
// glaurung: signed_overflow_avoided @ 0x1120
int32_t signed_overflow_avoided(int32_t arg0, int32_t arg1) {
    return (unsigned int)((arg0 + arg1));
}
wraps_to_zero pass 4 lines 
// glaurung: wraps_to_zero @ 0x1100
uint32_t wraps_to_zero(uint32_t arg0) {
    return 0;
}

← 213 fixtures