glaurung

Fixture 40

quickselect

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

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

Iterative quickselect for the k-th smallest element, plus a median helper. The loop narrows [low, high] from both ends, so the recovered code must keep two independent induction variables and a data-dependent exit.

tests/decompiler_fixtures/src/40_quickselect.c source 
#include <stdint.h>

/* Iterative quickselect for the k-th smallest element, plus a median helper.
 * The loop narrows [low, high] from both ends, so the recovered code must keep
 * two independent induction variables and a data-dependent exit. */

#define QSEL_MAX 16

__attribute__((noinline)) int32_t
quickselect_kth(int32_t *values, int32_t count, int32_t k) {
    int32_t low = 0;
    int32_t high;
    int32_t guard;
    if (values == 0 || count <= 0 || count > QSEL_MAX || k < 0 || k >= count) {
        return -1;
    }
    high = count - 1;
    for (guard = 0; guard < QSEL_MAX * 2 && low < high; ++guard) {
        int32_t pivot = values[high];
        int32_t boundary = low;
        int32_t scan;
        for (scan = low; scan < high; ++scan) {
            if (values[scan] <= pivot) {
                int32_t swap = values[boundary];
                values[boundary] = values[scan];
                values[scan] = swap;
                boundary += 1;
            }
        }
        values[high] = values[boundary];
        values[boundary] = pivot;
        if (boundary == k) {
            return values[boundary];
        }
        if (k < boundary) {
            high = boundary - 1;
        } else {
            low = boundary + 1;
        }
    }
    return values[low];
}

__attribute__((noinline)) int32_t
median_of_three(int32_t a, int32_t b, int32_t c) {
    if ((a >= b && a <= c) || (a <= b && a >= c)) {
        return a;
    }
    if ((b >= a && b <= c) || (b <= a && b >= c)) {
        return b;
    }
    return c;
}

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
median_of_three pass 39 lines 
// glaurung: median_of_three @ 0x12b0
int32_t median_of_three(int32_t arg0, int32_t arg1, int32_t arg2) {
    int local_4;
    if ((arg1 <= arg0)) {
        if ((((unsigned int)(arg0) == (unsigned int)(arg2)) | (arg0 < arg2))) {
            goto L_12ed;
        }
    }
    if (((((unsigned int)(arg0) == (unsigned int)(arg1)) | (arg0 < arg1)) == 0)) {
        goto L_12f8;
    }
    if ((arg0 < arg2)) {
        goto L_12f8;
    }
    L_12ed: ;
    local_4 = arg0;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
    L_12f8: ;
    if ((arg0 <= arg1)) {
        if ((((unsigned int)(arg1) == (unsigned int)(arg2)) | (arg1 < arg2))) {
            goto L_1328;
        }
    }
    if (((((unsigned int)(arg1) == (unsigned int)(arg0)) | (arg1 < arg0)) == 0)) {
        goto L_1333;
    }
    if ((arg1 < arg2)) {
        goto L_1333;
    }
    L_1328: ;
    local_4 = arg1;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
    L_1333: ;
    local_4 = arg2;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
}
quickselect_kth pass 79 lines 
// glaurung: quickselect_kth @ 0x1100
int32_t quickselect_kth(int32_t * arg0, int32_t arg1, int32_t arg2) {
    int low;
    int high;
    int guard;
    int pivot;
    int boundary;
    int scan;
    int swap;
    signed char local_35;
    int local_4;
    long var19;
    low = 0;
    if ((arg0 != 0)) {
        if (((((unsigned long)((unsigned int)(arg1)) == 0) | ((long)(arg1) < 0)) == 0)) {
            if (((((unsigned long)((unsigned int)(arg1)) == 16) | ((long)(arg1) < 16)) != 0)) {
                if ((0 <= (long)(arg2))) {
                    if ((arg2 < arg1)) {
                        goto L_1156;
                    }
                }
            }
        }
    }
    local_4 = -1;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
    L_1156: ;
    high = ((unsigned int)(arg1) - 1);
    guard = 0;
    L_1166: ;
    local_35 = 0;
    if (((long)(guard) < 32)) {
        local_35 = (low < high);
    }
    if (((unsigned long)((unsigned char)((local_35 & 1))) == 0)) {
        goto L_1292;
    }
    pivot = arg0[(long)(high)];
    boundary = low;
    scan = low;
    L_11ab: ;
    if ((high <= scan)) {
        goto L_1219;
    }
    var19 = (unsigned long)((unsigned int)(arg0[(long)(scan)]));
    if (((((unsigned int)(var19) == (unsigned int)(pivot)) | ((long)((int)(var19)) < (long)(pivot))) != 0)) {
        swap = arg0[(long)(boundary)];
        arg0[(long)(boundary)] = arg0[(long)(scan)];
        arg0[(long)(scan)] = swap;
        boundary = ((unsigned int)(boundary) + 1);
    }
    goto L_120b;
    L_120b: ;
    scan = ((unsigned int)(scan) + 1);
    goto L_11ab;
    L_1219: ;
    arg0[(long)(high)] = arg0[(long)(boundary)];
    arg0[(long)(boundary)] = pivot;
    if (((unsigned int)(boundary) == (unsigned int)(arg2))) {
        local_4 = arg0[(long)(boundary)];
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    if ((arg2 < boundary)) {
        high = ((unsigned int)(boundary) - 1);
        goto L_127f;
    }
    low = ((unsigned int)(boundary) + 1);
    L_127f: ;
    goto L_1284;
    L_1284: ;
    guard = ((unsigned int)(guard) + 1);
    goto L_1166;
    L_1292: ;
    local_4 = arg0[(long)(low)];
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
}

clang -O2

2/2
median_of_three pass 24 lines 
// glaurung: median_of_three @ 0x1210
int32_t median_of_three(int32_t arg0, int32_t arg1, int32_t arg2) {
    long ret;
    int var2;
    ret = (unsigned long)((unsigned int)(arg0));
    if ((arg0 < arg1)) {
        goto L_121b;
    }
    if (((((unsigned int)(ret) == (unsigned int)(arg2)) | ((long)((int)(ret)) < (long)(arg2))) == 0)) {
        goto L_121b;
    }
    L_121a: ;
    return ret;
    L_121b: ;
    if (((((unsigned int)(ret) == (unsigned int)(arg1)) | ((long)((int)(ret)) < (long)(arg1))) == 0)) {
        var2 = (((long)((int)(ret)) < (long)(arg1)) ? arg2 : ((arg1 < arg2) ? arg2 : (unsigned long)((unsigned int)(arg1))));
        return (unsigned int)(((((unsigned int)(ret) == (unsigned int)(arg1)) | ((long)((int)(ret)) < (long)(arg1))) == 0) ? var2 : (((((unsigned int)(arg1) == (unsigned int)(arg2)) | (arg1 < arg2)) == 0) ? var2 : (unsigned long)((unsigned int)(arg1))));
    }
    if (((long)(arg2) <= (long)((int)(ret)))) {
        goto L_121a;
    }
    var2 = (((long)((int)(ret)) < (long)(arg1)) ? arg2 : ((arg1 < arg2) ? arg2 : (unsigned long)((unsigned int)(arg1))));
    return (unsigned int)(((((unsigned int)(ret) == (unsigned int)(arg1)) | ((long)((int)(ret)) < (long)(arg1))) == 0) ? var2 : (((((unsigned int)(arg1) == (unsigned int)(arg2)) | (arg1 < arg2)) == 0) ? var2 : (unsigned long)((unsigned int)(arg1))));
}
quickselect_kth pass 133 lines 
// glaurung: quickselect_kth @ 0x1100
int32_t quickselect_kth(int32_t * arg0, int32_t arg1, int32_t arg2) {
    int pivot;
    int boundary;
    int high;
    int guard;
    int swap;
    long var0;
    long var11;
    long var12;
    long var14;
    long var15;
    long var19;
    long var21;
    long var23;
    long var24;
    long var28;
    long var29;
    long var3;
    int var35;
    long var37;
    long var38;
    long var4;
    long var40;
    long var43;
    long var45;
    long var9;
    var0 = 0xffffffff;
    pivot = 0xffffffff;
    if ((arg1 <= arg2)) {
        // x86-64 epilogue: tear down frame
        return pivot;
    }
    pivot = var0;
    if (((long)(arg2) < 0)) {
        // x86-64 epilogue: tear down frame
        return pivot;
    }
    pivot = var0;
    if ((arg0 == 0)) {
        // x86-64 epilogue: tear down frame
        return pivot;
    }
    pivot = var0;
    if (((unsigned long)((unsigned long)((unsigned int)((arg1 - 17)))) < (unsigned long)(0xfffffff0))) {
        // x86-64 epilogue: tear down frame
        return pivot;
    }
    var3 = 0;
    var4 = 0;
    if (((unsigned long)((unsigned long)((unsigned int)(arg1))) < (unsigned long)(2))) {
        // x86-64 epilogue: tear down frame
        return (unsigned int)(*(int *)(((long)arg0 + var4 * 4)));
    }
    var9 = 0;
    boundary = var3;
    var11 = (unsigned long)((unsigned int)((arg1 - 1)));
    L_1140: ;
    var12 = (long)((int)(var11));
    pivot = (unsigned long)((unsigned int)(arg0[(long)((int)(var11))]));
    var14 = (unsigned long)((unsigned int)(boundary));
    if (((long)((int)(var11)) <= (long)(boundary))) {
        goto L_1189;
    }
    var15 = (long)(boundary);
    var19 = (long)(boundary);
    var14 = (unsigned long)((unsigned int)(boundary));
    if (((unsigned long)((unsigned char)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var11)) - boundary))) & 1))) != 0)) {
        var21 = (unsigned long)((unsigned int)(*(int *)(((long)arg0 + var15 * 4))));
        var23 = (unsigned long)((unsigned int)(boundary));
        if (((((unsigned int)(var21) == (unsigned int)(pivot)) | ((long)((int)(var21)) < (long)(pivot))) != 0)) {
            var24 = (unsigned long)((unsigned int)(*(int *)(((long)arg0 + var15 * 4))));
            *(int *)(((long)arg0 + var15 * 4)) = var21;
            *(int *)(((long)arg0 + var15 * 4)) = var24;
            var23 = (unsigned long)((unsigned int)((boundary + 1)));
        }
        var19 = (var15 + 1);
        var14 = var23;
    }
    var28 = var14;
    var29 = var19;
    if ((((~var15) + var12) != 0)) {
        goto L_11c9;
    }
    L_1189: ;
    *(int *)(((long)arg0 + var12 * 4)) = arg0[(long)((int)(var14))];
    arg0[(long)((int)(var14))] = pivot;
    if (((unsigned int)(var14) == (unsigned int)(arg2))) {
        // x86-64 epilogue: tear down frame
        return pivot;
    }
    high = (((((unsigned int)(var14) == (unsigned int)(arg2)) | ((long)((int)(var14)) < (long)(arg2))) == 0) ? (unsigned long)((unsigned int)((var14 - 1))) : var11);
    var35 = ((((unsigned int)(var14) == (unsigned int)(arg2)) | ((long)((int)(var14)) < (long)(arg2))) ? (unsigned long)((unsigned int)((var14 + 1))) : boundary);
    if (((unsigned long)(30) < (unsigned long)((unsigned long)((unsigned int)(var9))))) {
        var4 = (long)((int)(var35));
        // x86-64 epilogue: tear down frame
        return (unsigned int)(arg0[(long)((int)(var35))]);
    }
    var9 = (unsigned long)((unsigned int)((var9 + 1)));
    boundary = var35;
    var11 = (unsigned long)((unsigned int)(high));
    if ((var35 < high)) {
        goto L_1140;
    }
    var4 = (long)((int)(var35));
    // x86-64 epilogue: tear down frame
    return (unsigned int)(arg0[(long)((int)(var35))]);
    L_11c0: ;
    var29 = (var29 + 2);
    var14 = var28;
    if ((var12 == var29)) {
        goto L_1189;
    }
    L_11c9: ;
    var37 = (unsigned long)((unsigned int)(*(int *)(((long)arg0 + var29 * 4))));
    var38 = var28;
    if (((((unsigned int)(var37) == (unsigned int)(pivot)) | ((long)((int)(var37)) < (long)(pivot))) != 0)) {
        var40 = (unsigned long)((unsigned int)(arg0[(long)((int)(var28))]));
        arg0[(long)((int)(var28))] = var37;
        *(int *)(((long)arg0 + var29 * 4)) = var40;
        var38 = (unsigned long)((unsigned int)(((long)((int)(var28)) + 1)));
    }
    var43 = (unsigned long)((unsigned int)(*(int *)(((long)arg0 + var29 * 4 + 0x4))));
    var28 = var38;
    if (((((unsigned int)(var43) == (unsigned int)(pivot)) | ((long)((int)(var43)) < (long)(pivot))) == 0)) {
        goto L_11c0;
    }
    var45 = (unsigned long)((unsigned int)(arg0[(long)((int)(var38))]));
    arg0[(long)((int)(var38))] = var43;
    *(int *)(((long)arg0 + var29 * 4 + 0x4)) = var45;
    var28 = (unsigned long)((unsigned int)(((long)((int)(var38)) + 1)));
    goto L_11c0;
}

gcc -O0

2/2
median_of_three pass 34 lines 
// glaurung: median_of_three @ 0x12ba
int32_t median_of_three(int32_t arg0, int32_t arg1, int32_t arg2) {
    if ((arg1 <= arg0)) {
        if ((((unsigned int)(arg0) == (unsigned int)(arg2)) | (arg0 < arg2))) {
            goto L_12eb;
        }
    }
    if (((((unsigned int)(arg0) == (unsigned int)(arg1)) | (arg0 < arg1)) == 0)) {
        goto L_12f0;
    }
    if ((arg0 < arg2)) {
        goto L_12f0;
    }
    L_12eb: ;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(arg0);
    L_12f0: ;
    if ((arg0 <= arg1)) {
        if ((((unsigned int)(arg1) == (unsigned int)(arg2)) | (arg1 < arg2))) {
            // x86-64 epilogue: restore rbp
            return (unsigned int)(arg1);
        }
    }
    if (((((unsigned int)(arg1) == (unsigned int)(arg0)) | (arg1 < arg0)) == 0)) {
        // x86-64 epilogue: restore rbp
        return (unsigned int)(arg2);
    }
    if ((arg1 < arg2)) {
        // x86-64 epilogue: restore rbp
        return (unsigned int)(arg2);
    }
    // x86-64 epilogue: restore rbp
    return (unsigned int)(arg1);
}
quickselect_kth pass 68 lines 
// glaurung: quickselect_kth @ 0x10f9
int32_t quickselect_kth(int32_t * arg0, int32_t arg1, int32_t arg2) {
    int low;
    int high;
    int guard;
    int pivot;
    int boundary;
    int scan;
    int swap;
    low = 0;
    if ((arg0 != 0)) {
        if (((((unsigned long)((unsigned int)(arg1)) == 0) | ((long)(arg1) < 0)) == 0)) {
            if (((((unsigned long)((unsigned int)(arg1)) == 16) | ((long)(arg1) < 16)) != 0)) {
                if ((0 <= (long)(arg2))) {
                    if ((arg2 < arg1)) {
                        goto L_113d;
                    }
                }
            }
        }
    }
    // x86-64 epilogue: restore rbp
    return 0xffffffff;
    L_113d: ;
    high = ((unsigned int)(arg1) - 1);
    guard = 0;
    goto L_1290;
    L_1152: ;
    pivot = arg0[(long)(high)];
    boundary = low;
    scan = low;
    goto L_11fe;
    L_117c: ;
    if (((long)((int)(arg0[(long)(scan)])) <= (long)(pivot))) {
        swap = arg0[(long)(boundary)];
        arg0[(long)(boundary)] = arg0[(long)(scan)];
        arg0[(long)(scan)] = swap;
        boundary = (boundary + 1);
    }
    scan = (scan + 1);
    L_11fe: ;
    if ((scan < high)) {
        goto L_117c;
    }
    arg0[(long)(high)] = arg0[(long)(boundary)];
    arg0[(long)(boundary)] = pivot;
    if (((unsigned int)(boundary) == (unsigned int)(arg2))) {
        // x86-64 epilogue: restore rbp
        return (unsigned int)(arg0[(long)(boundary)]);
    }
    if ((arg2 < boundary)) {
        high = ((unsigned int)(boundary) - 1);
        goto L_128c;
    }
    low = ((unsigned int)(boundary) + 1);
    L_128c: ;
    guard = (guard + 1);
    L_1290: ;
    if (((((unsigned long)((unsigned int)(guard)) == 31) | ((long)(guard) < 31)) == 0)) {
        // x86-64 epilogue: restore rbp
        return (unsigned int)(arg0[(long)(low)]);
    }
    if ((low < high)) {
        goto L_1152;
    }
    // x86-64 epilogue: restore rbp
    return (unsigned int)(arg0[(long)(low)]);
}

gcc -O2

2/2
median_of_three pass 41 lines 
// glaurung: median_of_three @ 0x11e0
int32_t median_of_three(int32_t arg0, int32_t arg1, int32_t arg2) {
    long ret;
    long var1;
    long var3;
    ret = (unsigned long)((unsigned int)(arg0));
    var1 = (arg1 <= arg0);
    if (((((unsigned int)(arg0) == (unsigned int)(arg2)) | (arg0 < arg2)) == 0)) {
        goto L_11f8;
    }
    if (((unsigned long)((unsigned char)((var1 & 255))) == 0)) {
        goto L_11f8;
    }
    L_11f3: ;
    return ret;
    L_11f8: ;
    var3 = ((((unsigned int)(ret) == (unsigned int)(arg1)) | ((long)((int)(ret)) < (long)(arg1))) & 255);
    if (((long)(arg2) <= (long)((int)(ret)))) {
        if (((unsigned long)((unsigned char)((var3 & 255))) != 0)) {
            goto L_11f3;
        }
    }
    if (((((unsigned int)(arg1) == (unsigned int)(arg2)) | (arg1 < arg2)) == 0)) {
        goto L_1220;
    }
    ret = (unsigned long)((unsigned int)(arg1));
    if (((unsigned long)((unsigned char)((var3 & 255))) != 0)) {
        goto L_11f3;
    }
    if ((arg2 <= arg1)) {
        goto L_1220;
    }
    L_1216: ;
    return (unsigned int)(arg2);
    L_1220: ;
    ret = (unsigned long)((unsigned int)(arg1));
    if (((unsigned long)((unsigned char)((var1 & 255))) == 0)) {
        goto L_1216;
    }
    return ret;
}
quickselect_kth pass 101 lines 
// glaurung: quickselect_kth @ 0x1100
int32_t quickselect_kth(int32_t * arg0, int32_t arg1, int32_t arg2) {
    int high;
    int guard;
    int low;
    int scan;
    int pivot;
    int boundary;
    long of_16;
    long sf_16;
    long t204;
    long var0;
    long var1;
    long var14;
    long var17;
    long var18;
    long var2;
    long var22;
    long var23;
    long var24;
    long var26;
    int var28;
    long var8;
    long zf_16;
    var0 = (unsigned long)((unsigned int)((arg1 - 1)));
    if (((unsigned long)(15) < (unsigned long)((unsigned long)((unsigned int)(var0))))) {
        return 0xffffffff;
    }
    var1 = (long)arg0;
    if ((arg0 == 0)) {
        return 0xffffffff;
    }
    var2 = (unsigned long)((unsigned int)(arg2));
    if (((long)(arg2) < 0)) {
        goto L_11c8;
    }
    if ((((unsigned int)(arg1) == (unsigned int)(arg2)) | (arg1 < arg2))) {
        goto L_11c8;
    }
    if (((unsigned long)((unsigned int)(var0)) == 0)) {
        goto L_11af;
    }
    var8 = 0;
    high = var0;
    guard = 0;
    low = 0;
    L_1148: ;
    var14 = (var1 + ((long)(high) * 4));
    scan = var8;
    pivot = (unsigned long)((unsigned int)(*(int *)((var14))));
    var17 = (unsigned long)((unsigned int)(low));
    do {
        var18 = (unsigned long)((unsigned int)(*(int *)((var1 + scan * 4))));
        boundary = var17;
        if (((((unsigned int)(var18) == (unsigned int)(pivot)) | ((long)((int)(var18)) < (long)(pivot))) != 0)) {
            boundary = (unsigned long)((unsigned int)((var17 + 1)));
            var22 = (var1 + ((long)((int)(var17)) * 4));
            var23 = (unsigned long)((unsigned int)(*(int *)((var22))));
            *(int *)((var22)) = var18;
            *(int *)((var1 + scan * 4)) = var23;
        }
        var24 = ((unsigned long)((unsigned int)(scan)) + 1);
        scan = var24;
        var17 = (unsigned long)((unsigned int)(boundary));
    } while (((((unsigned int)(high) == (unsigned int)(var24)) | ((long)(high) < (long)((int)(var24)))) == 0));
    var26 = (var1 + ((long)(boundary) * 4));
    *(int *)((var14)) = *(int *)((var26));
    *(int *)((var26)) = pivot;
    t204 = ((unsigned long)((unsigned int)(boundary)) - var2);
    zf_16 = ((unsigned int)(boundary) == (unsigned int)(var2));
    sf_16 = ((long)((int)(t204)) < 0);
    of_16 = (((long)(boundary) < (long)((int)(var2))) ^ ((long)((int)(t204)) < 0));
    if (((unsigned int)(boundary) == (unsigned int)(var2))) {
        goto L_11b2;
    }
    if ((zf_16 | (sf_16 ^ of_16))) {
        goto L_11c0;
    }
    high = (unsigned long)((unsigned int)((boundary - 1)));
    L_119e: ;
    var28 = (guard + 1);
    guard = (unsigned long)((unsigned int)(var28));
    if (((((unsigned long)((unsigned int)(var28)) == 31) | ((long)((int)(var28)) < 31)) != 0)) {
        if ((low < high)) {
            goto L_1148;
        }
    }
    var1 = (var1 + (var8 * 4));
    L_11af: ;
    pivot = (unsigned long)((unsigned int)(*(int *)((var1))));
    L_11b2: ;
    // x86-64 epilogue: tear down frame
    return (unsigned int)(pivot);
    L_11c0: ;
    low = (unsigned long)((unsigned int)((boundary + 1)));
    var8 = (long)(low);
    goto L_119e;
    L_11c8: ;
    pivot = 0xffffffff;
    goto L_11b2;
}

← 213 fixtures