glaurung

Fixture 64

root finding

C · 2 functions · 4 lanes · 8 of 8 function-lanes behave identically

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

Bisection and Newton-Raphson on the same Q16.16 objective. Bisection is a sign-test loop with a shrinking bracket; Newton is a self-correcting recurrence with a derivative guard. Both terminate on a tolerance.

tests/decompiler_fixtures/src/64_root_finding.c source 
#include <stdint.h>

/* Bisection and Newton-Raphson on the same Q16.16 objective.  Bisection is a
 * sign-test loop with a shrinking bracket; Newton is a self-correcting
 * recurrence with a derivative guard.  Both terminate on a tolerance. */

#define ROOT_ITERATIONS 40

static int32_t root_mul_q16(int32_t left, int32_t right) {
    return (int32_t)(((int64_t)left * (int64_t)right) >> 16);
}

static int32_t root_div_q16(int32_t numerator, int32_t denominator) {
    if (denominator == 0) {
        return 0;
    }
    return (int32_t)(((int64_t)numerator << 16) / (int64_t)denominator);
}

static int32_t root_objective(int32_t x, int32_t target) {
    return root_mul_q16(x, x) - target;
}

__attribute__((noinline)) int32_t
bisection_sqrt(int32_t target, int32_t tolerance) {
    int32_t low = 0;
    int32_t high = 256 * 65536;
    int32_t iteration;
    if (target < 0 || tolerance <= 0) {
        return -1;
    }
    for (iteration = 0; iteration < ROOT_ITERATIONS; ++iteration) {
        int32_t middle = low + (high - low) / 2;
        int32_t value = root_objective(middle, target);
        int32_t magnitude = (value < 0) ? -value : value;
        if (magnitude <= tolerance) {
            return middle;
        }
        if (value > 0) {
            high = middle;
        } else {
            low = middle;
        }
    }
    return low + (high - low) / 2;
}

__attribute__((noinline)) int32_t
newton_sqrt(int32_t target, int32_t tolerance) {
    int32_t estimate = 65536;
    int32_t iteration;
    if (target <= 0 || tolerance <= 0) {
        return -1;
    }
    for (iteration = 0; iteration < ROOT_ITERATIONS; ++iteration) {
        int32_t value = root_objective(estimate, target);
        int32_t derivative = 2 * estimate;
        int32_t magnitude = (value < 0) ? -value : value;
        if (magnitude <= tolerance) {
            return estimate;
        }
        if (derivative == 0) {
            return -2;
        }
        estimate -= root_div_q16(value, derivative);
        if (estimate <= 0) {
            estimate = 65536;
        }
    }
    return estimate;
}

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

2/2
bisection_sqrt pass 66 lines 
// glaurung: bisection_sqrt @ 0x1100
int32_t bisection_sqrt(int32_t arg0, int32_t arg1) {
    extern int root_objective(int, int);
    int low;
    int high;
    int iteration;
    int middle;
    int value;
    int magnitude;
    int local_28;
    int local_2c;
    int local_30;
    int local_4;
    int var12;
    long var3;
    long var30;
    low = 0;
    high = 0x1000000;
    if ((0 <= (long)(arg0))) {
        if (((((unsigned long)((unsigned int)(arg1)) == 0) | ((long)(arg1) < 0)) == 0)) {
            goto L_113c;
        }
    }
    local_4 = -1;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
    L_113c: ;
    iteration = 0;
    L_1143: ;
    if ((40 <= (long)(iteration))) {
        goto L_11e1;
    }
    local_28 = low;
    var3 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(high)) - low)));
    middle = ((unsigned int)(local_28) + (unsigned int)(((int)((((long long)(int)((((unsigned long)((long)((int)(var3))) >> 32) & 0xffffffff)) * (((long long)1) << 32)) + (unsigned int)(var3)) / (int)(2)))));
    var12 = root_objective((unsigned long)((unsigned int)(middle)), (unsigned long)((unsigned int)(arg0)));
    value = var12;
    if (((long)(value) < 0)) {
        local_2c = (0 - value);
        goto L_1196;
    }
    local_2c = value;
    L_1196: ;
    magnitude = local_2c;
    if (((((unsigned int)(magnitude) == (unsigned int)(arg1)) | (magnitude < arg1)) != 0)) {
        local_4 = middle;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    if (((((unsigned long)((unsigned int)(value)) == 0) | ((long)(value) < 0)) == 0)) {
        high = middle;
        goto L_11ce;
    }
    low = middle;
    L_11ce: ;
    goto L_11d3;
    L_11d3: ;
    iteration = ((unsigned int)(iteration) + 1);
    goto L_1143;
    L_11e1: ;
    local_30 = low;
    var30 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(high)) - low)));
    local_4 = ((unsigned int)(local_30) + (unsigned int)(((int)((((long long)(int)((((unsigned long)((long)((int)(var30))) >> 32) & 0xffffffff)) * (((long long)1) << 32)) + (unsigned int)(var30)) / (int)(2)))));
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
}
newton_sqrt pass 62 lines 
// glaurung: newton_sqrt @ 0x1240
int32_t newton_sqrt(int32_t arg0, int32_t arg1) {
    extern int root_div_q16(int, int);
    extern int root_objective(int, int);
    int estimate;
    int iteration;
    int value;
    int derivative;
    int magnitude;
    int local_24;
    int local_4;
    int var15;
    int var2;
    estimate = 0x10000;
    if (((((unsigned long)((unsigned int)(arg0)) == 0) | ((long)(arg0) < 0)) == 0)) {
        if (((((unsigned long)((unsigned int)(arg1)) == 0) | ((long)(arg1) < 0)) == 0)) {
            goto L_1275;
        }
    }
    local_4 = -1;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
    L_1275: ;
    iteration = 0;
    L_127c: ;
    if ((40 <= (long)(iteration))) {
        goto L_1326;
    }
    var2 = root_objective((unsigned long)((unsigned int)(estimate)), (unsigned long)((unsigned int)(arg0)));
    value = var2;
    derivative = ((unsigned long)((unsigned int)(estimate)) << 1);
    if (((long)(value) < 0)) {
        local_24 = (0 - value);
        goto L_12ba;
    }
    local_24 = value;
    L_12ba: ;
    magnitude = local_24;
    if (((((unsigned int)(magnitude) == (unsigned int)(arg1)) | (magnitude < arg1)) != 0)) {
        local_4 = estimate;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    if (((unsigned long)((unsigned int)(derivative)) == 0)) {
        local_4 = -2;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    var15 = root_div_q16((unsigned long)((unsigned int)(value)), (unsigned long)((unsigned int)(derivative)));
    estimate = ((unsigned int)(estimate) - (unsigned int)(var15));
    if (((((unsigned long)((unsigned int)(estimate)) == 0) | ((long)(estimate) < 0)) != 0)) {
        estimate = 0x10000;
    }
    goto L_1318;
    L_1318: ;
    iteration = ((unsigned int)(iteration) + 1);
    goto L_127c;
    L_1326: ;
    local_4 = estimate;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
}

clang -O2

2/2
bisection_sqrt pass 62 lines 
// glaurung: bisection_sqrt @ 0x1100
int32_t bisection_sqrt(int32_t arg0, int32_t arg1) {
    int middle;
    int high;
    int low;
    int value;
    int magnitude;
    long t137;
    long var12;
    int var22;
    int var31;
    long var33;
    long var4;
    long var7;
    int var8;
    long var9;
    middle = 0xffffffff;
    if (((long)(arg0) < 0)) {
        return middle;
    }
    middle = 0xffffffff;
    if ((((unsigned long)((unsigned int)(arg1)) == 0) | ((long)(arg1) < 0))) {
        return middle;
    }
    var4 = 40;
    high = 0x1000000;
    low = 0;
    goto L_1129;
    L_1120: ;
    var7 = (unsigned long)((unsigned int)(middle));
    var8 = (var4 - 1);
    var4 = (unsigned long)((unsigned int)(var8));
    low = (unsigned long)((unsigned int)(middle));
    var9 = (unsigned long)((unsigned int)(high));
    if (((unsigned long)((unsigned int)(var8)) == 0)) {
        var33 = (unsigned long)((unsigned int)((var9 - var7)));
        return (unsigned int)(((unsigned long)((unsigned int)(((int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var33)) >> 31))) + var33)) >> 1))) + var7));
    }
    L_1129: ;
    var12 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(high)) - low)));
    var22 = ((unsigned int)(((int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var12)) >> 31))) + var12)) >> 1)) + low);
    middle = (unsigned long)((unsigned int)(var22));
    value = (unsigned long)((unsigned int)((((unsigned long)(((long)((int)(var22)) * (long)((int)(var22)))) >> 16) - arg0)));
    t137 = (-(unsigned long)((unsigned int)(value)));
    magnitude = (((long)((int)(t137)) < 0) ? value : t137);
    if ((((unsigned int)(magnitude) == (unsigned int)(arg1)) | (magnitude < arg1))) {
        return middle;
    }
    if ((((unsigned long)((unsigned int)(value)) == 0) | ((long)(value) < 0))) {
        goto L_1120;
    }
    var9 = (unsigned long)((unsigned int)(middle));
    var31 = (var4 - 1);
    var4 = (unsigned long)((unsigned int)(var31));
    high = (unsigned long)((unsigned int)(middle));
    var7 = (unsigned long)((unsigned int)(low));
    if (((unsigned long)((unsigned int)(var31)) != 0)) {
        goto L_1129;
    }
    var33 = (unsigned long)((unsigned int)((var9 - var7)));
    return (unsigned int)(((unsigned long)((unsigned int)(((int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var33)) >> 31))) + var33)) >> 1))) + var7));
}
newton_sqrt pass 46 lines 
// glaurung: newton_sqrt @ 0x1180
int32_t newton_sqrt(int32_t arg0, int32_t arg1) {
    int estimate;
    int value;
    int magnitude;
    int derivative;
    long t137;
    int var1;
    long var16;
    long var3;
    long var30;
    long var31;
    int var32;
    long var4;
    var1 = 0xffffffff;
    if ((((unsigned long)((unsigned int)(arg0)) != 0) && (0 <= (long)(arg0)))) {
        var1 = 0xffffffff;
        if ((((unsigned long)((unsigned int)(arg1)) == 0) | ((long)(arg1) < 0))) {
            return (unsigned int)(var1);
        }
        var3 = 40;
        var4 = 0x10000;
        estimate = 0x10000;
        while (1) {
            value = (unsigned long)((unsigned int)((((unsigned long)(((unsigned long)((unsigned int)(estimate)) * (unsigned long)((unsigned int)(estimate)))) >> 16) - arg0)));
            t137 = (-(unsigned long)((unsigned int)(value)));
            magnitude = (((long)((int)(t137)) < 0) ? value : t137);
            var1 = estimate;
            if (((((unsigned int)(magnitude) == (unsigned int)(arg1)) | (magnitude < arg1)) != 0)) {
                break;
            }
            derivative = (unsigned long)((unsigned int)((estimate + estimate)));
            var16 = ((long)(value) << 16);
            var30 = (unsigned long)((unsigned int)((estimate - ((((unsigned long)((var16 | (long)(derivative))) >> 32) == 0) ? ((unsigned int)(((((unsigned long long)(unsigned int)((unsigned long)((unsigned int)(0))) << 32) | (unsigned int)(var16)) / (unsigned int)(derivative)))) : ((long)((((__int128)(long)(((long)(var16) >> 63)) * (((__int128)1) << 64)) + (unsigned long)(var16)) / (long)((long)(derivative))))))));
            var31 = ((((unsigned long)((unsigned int)(var30)) == 0) | ((long)((int)(var30)) < 0)) ? var4 : var30);
            var32 = (var3 - 1);
            var3 = (unsigned long)((unsigned int)(var32));
            estimate = var31;
            var1 = var31;
            if (((unsigned long)((unsigned int)(var32)) == 0)) {
                break;
            }
        }
    }
    return (unsigned int)(var1);
}

gcc -O0

2/2
bisection_sqrt pass 51 lines 
// glaurung: bisection_sqrt @ 0x1173
int32_t bisection_sqrt(int32_t arg0, int32_t arg1) {
    extern int root_objective(int, int);
    int low;
    int high;
    int iteration;
    int middle;
    int value;
    int magnitude;
    long t140;
    int var18;
    long var2;
    long var29;
    low = 0;
    high = 0x1000000;
    if ((0 <= (long)(arg0))) {
        if (((((unsigned long)((unsigned int)(arg1)) == 0) | ((long)(arg1) < 0)) == 0)) {
            goto L_11a9;
        }
    }
    // x86-64 epilogue: restore rbp
    return 0xffffffff;
    L_11a9: ;
    iteration = 0;
    goto L_120f;
    L_11b2: ;
    var2 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(high)) - low)));
    middle = ((unsigned int)(low) + (unsigned int)(((int)((var2 + (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var2)) >> 31))))) >> 1)));
    var18 = root_objective((unsigned long)((unsigned int)(middle)), (unsigned long)((unsigned int)(arg0)));
    value = var18;
    t140 = (-(unsigned long)((unsigned int)(value)));
    magnitude = ((0 <= (long)((int)(t140))) ? t140 : (unsigned long)((unsigned int)(value)));
    if (((((unsigned int)(magnitude) == (unsigned int)(arg1)) | (magnitude < arg1)) != 0)) {
        // x86-64 epilogue: restore rbp
        return (unsigned int)(middle);
    }
    if (((((unsigned long)((unsigned int)(value)) == 0) | ((long)(value) < 0)) == 0)) {
        high = middle;
        goto L_120b;
    }
    low = middle;
    L_120b: ;
    iteration = (iteration + 1);
    L_120f: ;
    if ((((unsigned long)((unsigned int)(iteration)) == 39) | ((long)(iteration) < 39))) {
        goto L_11b2;
    }
    var29 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(high)) - low)));
    // x86-64 epilogue: restore rbp
    return (unsigned int)(((unsigned long)((unsigned int)(low)) + (unsigned long)((unsigned int)(((int)((var29 + (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var29)) >> 31))))) >> 1)))));
}
newton_sqrt pass 50 lines 
// glaurung: newton_sqrt @ 0x122d
int32_t newton_sqrt(int32_t arg0, int32_t arg1) {
    extern int root_div_q16(int, int);
    extern int root_objective(int, int);
    int estimate;
    int iteration;
    int value;
    int derivative;
    int magnitude;
    long t139;
    int var14;
    int var2;
    estimate = 0x10000;
    if (((((unsigned long)((unsigned int)(arg0)) == 0) | ((long)(arg0) < 0)) == 0)) {
        if (((((unsigned long)((unsigned int)(arg1)) == 0) | ((long)(arg1) < 0)) == 0)) {
            goto L_1259;
        }
    }
    // x86-64 epilogue: restore rbp
    return 0xffffffff;
    L_1259: ;
    iteration = 0;
    goto L_12c6;
    L_1262: ;
    var2 = root_objective((unsigned long)((unsigned int)(estimate)), (unsigned long)((unsigned int)(arg0)));
    value = var2;
    derivative = ((unsigned int)(estimate) + (unsigned int)(estimate));
    t139 = (-(unsigned long)((unsigned int)(value)));
    magnitude = ((0 <= (long)((int)(t139))) ? t139 : (unsigned long)((unsigned int)(value)));
    if (((((unsigned int)(magnitude) == (unsigned int)(arg1)) | (magnitude < arg1)) != 0)) {
        // x86-64 epilogue: restore rbp
        return (unsigned int)(estimate);
    }
    if (((unsigned long)((unsigned int)(derivative)) == 0)) {
        // x86-64 epilogue: restore rbp
        return 0xfffffffe;
    }
    var14 = root_div_q16((unsigned long)((unsigned int)(value)), (unsigned long)((unsigned int)(derivative)));
    estimate = (estimate - var14);
    if (((((unsigned long)((unsigned int)(estimate)) == 0) | ((long)(estimate) < 0)) != 0)) {
        estimate = 0x10000;
    }
    iteration = (iteration + 1);
    L_12c6: ;
    if ((((unsigned long)((unsigned int)(iteration)) == 39) | ((long)(iteration) < 39))) {
        goto L_1262;
    }
    // x86-64 epilogue: restore rbp
    return (unsigned int)(estimate);
}

gcc -O2

2/2
bisection_sqrt pass 65 lines 
// glaurung: bisection_sqrt @ 0x1100
int32_t bisection_sqrt(int32_t arg0, int32_t arg1) {
    int high;
    int low;
    int middle;
    int value;
    long t139;
    long var0;
    long var1;
    int var10;
    long var11;
    long var14;
    long var2;
    long var23;
    long var32;
    int var36;
    var0 = (unsigned long)((unsigned int)(arg0));
    var1 = (unsigned long)((unsigned int)(arg1));
    if (((long)(arg0) < 0)) {
        goto L_1182;
    }
    if ((((unsigned long)((unsigned int)(arg1)) == 0) | ((long)(arg1) < 0))) {
        goto L_1182;
    }
    var2 = 40;
    high = 0x1000000;
    low = 0;
    goto L_1130;
    L_1128: ;
    var10 = (var2 - 1);
    var2 = (unsigned long)((unsigned int)(var10));
    high = (unsigned long)((unsigned int)(middle));
    var11 = (unsigned long)((unsigned int)(low));
    if (((unsigned long)((unsigned int)(var10)) == 0)) {
        goto L_116e;
    }
    L_1130: ;
    var14 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(high)) - low)));
    var23 = (unsigned long)((unsigned int)(((int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var14)) >> 31))) + var14)) >> 1)));
    middle = (unsigned long)((unsigned int)((var23 + low)));
    value = (unsigned long)((unsigned int)((((long)(((long)(middle) * (long)(middle))) >> 16) - var0)));
    t139 = (-(unsigned long)((unsigned int)(value)));
    var32 = (unsigned long)((unsigned int)(middle));
    if (((long)((int)((((long)((int)(t139)) < 0) ? value : t139))) <= (long)((int)(var1)))) {
        goto L_117e;
    }
    if (((((unsigned long)((unsigned int)(value)) == 0) | ((long)(value) < 0)) == 0)) {
        goto L_1128;
    }
    var23 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(high)) - middle)));
    var36 = (var2 - 1);
    var2 = (unsigned long)((unsigned int)(var36));
    low = (unsigned long)((unsigned int)(middle));
    var11 = (unsigned long)((unsigned int)(middle));
    if (((unsigned long)((unsigned int)(var36)) != 0)) {
        goto L_1130;
    }
    L_116e: ;
    var32 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(((int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var23)) >> 31))) + var23)) >> 1))) + var11)));
    L_117e: ;
    return (unsigned int)(var32);
    L_1182: ;
    var32 = 0xffffffff;
    goto L_117e;
}
newton_sqrt pass 48 lines 
// glaurung: newton_sqrt @ 0x1190
int32_t newton_sqrt(int32_t arg0, int32_t arg1) {
    int estimate;
    int value;
    int derivative;
    long t138;
    long var0;
    long var18;
    int var2;
    long var23;
    long var24;
    int var25;
    long var3;
    long var5;
    long var8;
    var0 = (unsigned long)((unsigned int)(arg1));
    if ((((unsigned long)((unsigned int)(arg0)) == 0) | ((long)(arg0) < 0))) {
        var2 = 0xffffffff;
        return 0xffffffff;
    }
    if ((((unsigned long)((unsigned int)(arg1)) == 0) | ((long)(arg1) < 0))) {
        var2 = 0xffffffff;
        return 0xffffffff;
    }
    var3 = 40;
    var5 = 0x10000;
    estimate = 0x10000;
    while (1) {
        var8 = (unsigned long)((unsigned int)((estimate + estimate)));
        value = (unsigned long)((unsigned int)((((long)(((long)(estimate) * (long)(estimate))) >> 16) - arg0)));
        t138 = (-(unsigned long)((unsigned int)(value)));
        var2 = estimate;
        if (((long)((int)((((long)((int)(t138)) < 0) ? value : t138))) <= (long)((int)(var0)))) {
            break;
        }
        var18 = ((long)(value) << 16);
        var23 = (unsigned long)((unsigned int)((estimate - ((long)((((__int128)(long)(((long)(var18) >> 63)) * (((__int128)1) << 64)) + (unsigned long)(var18)) / (long)((long)((int)(var8))))))));
        var24 = ((((unsigned long)((unsigned int)(var23)) == 0) | ((long)((int)(var23)) < 0)) ? var5 : var23);
        var25 = (var3 - 1);
        var3 = (unsigned long)((unsigned int)(var25));
        estimate = var24;
        var2 = var24;
        if (((unsigned long)((unsigned int)(var25)) == 0)) {
            break;
        }
    }
    return (unsigned int)(var2);
}

← 213 fixtures