glaurung

Fixture 36

quicksort

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

2 of 4 lanes have a function that returns a different result after decompilation: clang-O2 (0/1), gcc-O2 (0/1).

Genuinely recursive Lomuto quicksort with an explicit depth bound. The rest of the corpus deliberately uses explicit stacks; this fixture exists so that real self-recursion, its base cases, and the recursive frame are covered.

tests/decompiler_fixtures/src/36_quicksort.c source 
#include <stdint.h>

/* Genuinely recursive Lomuto quicksort with an explicit depth bound.  The rest
 * of the corpus deliberately uses explicit stacks; this fixture exists so that
 * real self-recursion, its base cases, and the recursive frame are covered. */

#define QS_MAX 16

static int32_t partition_lomuto(int32_t *values, int32_t low, int32_t high) {
    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;
    return boundary;
}

static void quicksort_range(int32_t *values, int32_t low, int32_t high,
                            int32_t depth) {
    if (low >= high || depth <= 0) {
        return;
    }
    {
        int32_t split = partition_lomuto(values, low, high);
        quicksort_range(values, low, split - 1, depth - 1);
        quicksort_range(values, split + 1, high, depth - 1);
    }
}

__attribute__((noinline)) int32_t
quicksort_i32(int32_t *values, int32_t count) {
    int32_t index;
    if (values == 0 || count < 0 || count > QS_MAX) {
        return -1;
    }
    quicksort_range(values, 0, count - 1, QS_MAX * 2);
    for (index = 1; index < count; ++index) {
        if (values[index - 1] > values[index]) {
            return 0;
        }
    }
    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 -O2

0/1
quicksort_i32 fail 47 lines 
// glaurung: quicksort_i32 @ 0x1100
int32_t quicksort_i32(int32_t * arg0, int32_t arg1) {
    extern void quicksort_range(int *, int, int, int);
    int index;
    long ret;
    long var0;
    long var1;
    long var3;
    long var4;
    long var7;
    // x86-64 prologue: save callee registers, frame 24 bytes
    ret = 0xffffffff;
    if ((arg0 == 0)) {
        // x86-64 epilogue: restore callee registers
        return ret;
    }
    var0 = (unsigned long)((unsigned int)(arg1));
    if (((unsigned long)(16) < (unsigned long)((unsigned long)((unsigned int)(arg1))))) {
        // x86-64 epilogue: restore callee registers
        return ret;
    }
    var1 = (long)arg0;
    quicksort_range((int *)(arg0), 0, (unsigned long)((unsigned int)((var0 - 1))), 32);
    if (((unsigned long)((unsigned long)((unsigned int)(var0))) < (unsigned long)(2))) {
        ret = (unsigned long)((unsigned int)(var0));
        // x86-64 epilogue: restore callee registers
        return (unsigned int)(var0);
    }
    var3 = (unsigned long)((unsigned int)(var0));
    var4 = (unsigned long)((unsigned int)(*(int *)((var1))));
    index = 1;
    while (1) {
        var7 = (unsigned long)((unsigned int)(var4));
        var4 = (unsigned long)((unsigned int)(*(int *)((var1 + index * 4))));
        if (((((unsigned int)(var7) == (unsigned int)(var4)) | ((long)((int)(var7)) < (long)((int)(var4)))) == 0)) {
            break;
        }
        index = (index + 1);
        if ((var3 == index)) {
            ret = (unsigned long)((unsigned int)(var0));
            // x86-64 epilogue: restore callee registers
            return (unsigned int)(var0);
        }
    }
    // x86-64 epilogue: restore callee registers
    return 0;
}

gcc -O2

0/1
quicksort_i32 fail 37 lines 
// glaurung: quicksort_i32 @ 0x1190
int32_t quicksort_i32(int32_t * arg0, int32_t arg1) {
    extern void quicksort_range(int *, int, int, int);
    int index;
    long t10;
    long var0;
    long var2;
    long var4;
    long var5;
    long var6;
    if ((arg0 == 0)) {
        return 0xffffffff;
    }
    var0 = (unsigned long)((unsigned int)(arg1));
    if (((unsigned long)(16) < (unsigned long)((unsigned long)((unsigned int)(arg1))))) {
        return 0xffffffff;
    }
    var2 = (long)arg0;
    quicksort_range((int *)(arg0), 0, (unsigned long)((unsigned int)((arg1 - 1))), 32);
    if ((((unsigned long)((unsigned int)(var0)) == 1) | ((long)((int)(var0)) < 1))) {
        return (unsigned int)(var0);
    }
    var4 = var2;
    var5 = ((var2 + ((unsigned long)((unsigned int)((var0 - 2))) * 4)) + 4);
    while (1) {
        var6 = (unsigned long)((unsigned int)(*(int *)((var4 + 0x4))));
        t10 = *(int *)((var4));
        if (((((unsigned int)(t10) == (unsigned int)(var6)) | ((long)((int)(t10)) < (long)((int)(var6)))) == 0)) {
            break;
        }
        var4 = (var4 + 4);
        if ((var4 == var5)) {
            return (unsigned int)(var0);
        }
    }
    return 0;
}

clang -O0

1/1
quicksort_i32 pass 39 lines 
// glaurung: quicksort_i32 @ 0x1100
int32_t quicksort_i32(int32_t * arg0, int32_t arg1) {
    extern void quicksort_range(int *, int, int, int);
    int index;
    int local_4;
    long t145;
    long var9;
    if ((arg0 != 0)) {
        if ((0 <= (long)(arg1))) {
            if ((((unsigned long)((unsigned int)(arg1)) == 16) | ((long)(arg1) < 16))) {
                goto L_113a;
            }
        }
    }
    local_4 = -1;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
    L_113a: ;
    quicksort_range((int *)(arg0), 0, (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(arg1)) - 1))), 32);
    index = 1;
    L_1157: ;
    if ((arg1 <= index)) {
        goto L_11a3;
    }
    var9 = (unsigned long)((unsigned int)(arg0[(long)((int)(((unsigned long)((unsigned int)(index)) - 1)))]));
    t145 = arg0[(long)(index)];
    if (((((unsigned int)(var9) == (unsigned int)(t145)) | ((long)((int)(var9)) < (long)((int)(t145)))) == 0)) {
        // x86-64 epilogue: restore rbp
        return 0;
    }
    goto L_1195;
    L_1195: ;
    index = ((unsigned int)(index) + 1);
    goto L_1157;
    L_11a3: ;
    local_4 = arg1;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
}

gcc -O0

1/1
quicksort_i32 pass 34 lines 
// glaurung: quicksort_i32 @ 0x1287
int32_t quicksort_i32(int32_t * arg0, int32_t arg1) {
    extern void quicksort_range(int *, int, int, int);
    int index;
    long var14;
    long var8;
    if ((arg0 != 0)) {
        if ((0 <= (long)(arg1))) {
            if ((((unsigned long)((unsigned int)(arg1)) == 16) | ((long)(arg1) < 16))) {
                goto L_12b4;
            }
        }
    }
    // x86-64 epilogue: restore rbp
    return 0xffffffff;
    L_12b4: ;
    quicksort_range((int *)(arg0), 0, (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(arg1)) - 1))), 32);
    index = 1;
    goto L_1314;
    L_12d9: ;
    var8 = (unsigned long)((unsigned int)(*(int *)(((long)arg0 + (((long)(index) << 2) - 4)))));
    var14 = (unsigned long)((unsigned int)(arg0[(long)(index)]));
    if (((((unsigned int)(var8) == (unsigned int)(var14)) | ((long)((int)(var8)) < (long)((int)(var14)))) == 0)) {
        // x86-64 epilogue: restore rbp
        return 0;
    }
    index = (index + 1);
    L_1314: ;
    if ((index < arg1)) {
        goto L_12d9;
    }
    // x86-64 epilogue: restore rbp
    return (unsigned int)(arg1);
}

← 213 fixtures