glaurung

Fixture 25

kmp search

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

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

tests/decompiler_fixtures/src/25_kmp_search.c source 
#include <stdint.h>

__attribute__((noinline)) int32_t kmp_search(const uint8_t *text, int32_t n,
                                              const uint8_t *pattern,
                                              int32_t m) {
    int32_t prefix[16];
    int32_t i;
    int32_t matched = 0;
    if (text == 0 || pattern == 0 || n < 0 || n > 16 || m < 0 || m > 16) {
        return -1;
    }
    if (m == 0) {
        return 0;
    }
    prefix[0] = 0;
    for (i = 1; i < m; ++i) {
        while (matched > 0 && pattern[i] != pattern[matched]) {
            matched = prefix[matched - 1];
        }
        if (pattern[i] == pattern[matched]) {
            ++matched;
        }
        prefix[i] = matched;
    }
    matched = 0;
    for (i = 0; i < n; ++i) {
        while (matched > 0 && text[i] != pattern[matched]) {
            matched = prefix[matched - 1];
        }
        if (text[i] == pattern[matched]) {
            ++matched;
        }
        if (matched == m) {
            return i - m + 1;
        }
    }
    return -1;
}

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

1/1
kmp_search pass 86 lines 
// glaurung: kmp_search @ 0x1100
__attribute__((no_stack_protector)) int32_t kmp_search(const uint8_t * arg0, int32_t arg1, const uint8_t * arg2, int32_t arg3) {
    int matched;
    int i;
    int local_4;
    unsigned char local_70[64];
    signed char local_79;
    signed char local_7a;
    matched = 0;
    if ((arg0 != 0)) {
        if ((arg2 != 0)) {
            if ((0 <= (long)(arg1))) {
                if (((((unsigned long)((unsigned int)(arg1)) == 16) | ((long)(arg1) < 16)) != 0)) {
                    if ((0 <= (long)(arg3))) {
                        if ((((unsigned long)((unsigned int)(arg3)) == 16) | ((long)(arg3) < 16))) {
                            goto L_1163;
                        }
                    }
                }
            }
        }
    }
    local_4 = -1;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
    L_1163: ;
    if (((unsigned long)((unsigned int)(arg3)) == 0)) {
        // x86-64 epilogue: restore rbp
        return 0;
    }
    *(int *)(&local_70[0]) = 0;
    i = 1;
    L_1187: ;
    if ((arg3 <= i)) {
        goto L_122d;
    }
    goto L_1198;
    L_1198: ;
    local_79 = 0;
    if (((((unsigned long)((unsigned int)(matched)) == 0) | ((long)(matched) < 0)) == 0)) {
        local_79 = ((unsigned int)((unsigned char)(arg2[i])) != (unsigned int)((unsigned char)(arg2[matched])));
    }
    if (((unsigned long)((unsigned char)((local_79 & 1))) != 0)) {
        matched = *(int *)((&local_70[0] + ((long)((int)(((unsigned long)((unsigned int)(matched)) - 1))) * 4)));
        goto L_1198;
    }
    if (((unsigned int)((unsigned char)(arg2[i])) == (unsigned int)((unsigned char)(arg2[matched])))) {
        matched = ((unsigned int)(matched) + 1);
    }
    *(int *)((&local_70[0] + ((long)(i) * 4))) = matched;
    i = ((unsigned int)(i) + 1);
    goto L_1187;
    L_122d: ;
    matched = 0;
    i = 0;
    L_123b: ;
    if ((arg1 <= i)) {
        goto L_12f8;
    }
    goto L_124c;
    L_124c: ;
    local_7a = 0;
    if (((((unsigned long)((unsigned int)(matched)) == 0) | ((long)(matched) < 0)) == 0)) {
        local_7a = ((unsigned int)((unsigned char)(arg0[i])) != (unsigned int)((unsigned char)(arg2[matched])));
    }
    if (((unsigned long)((unsigned char)((local_7a & 1))) != 0)) {
        matched = *(int *)((&local_70[0] + ((long)((int)(((unsigned long)((unsigned int)(matched)) - 1))) * 4)));
        goto L_124c;
    }
    if (((unsigned int)((unsigned char)(arg0[i])) == (unsigned int)((unsigned char)(arg2[matched])))) {
        matched = ((unsigned int)(matched) + 1);
    }
    if (((unsigned int)(matched) == (unsigned int)(arg3))) {
        local_4 = ((unsigned int)(((unsigned long)((unsigned int)(i)) - arg3)) + 1);
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    goto L_12ea;
    L_12ea: ;
    i = ((unsigned int)(i) + 1);
    goto L_123b;
    L_12f8: ;
    local_4 = -1;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
}

clang -O2

1/1
kmp_search pass 113 lines 
// glaurung: kmp_search @ 0x1100
__attribute__((no_stack_protector)) int32_t kmp_search(const uint8_t * arg0, int32_t arg1, const uint8_t * arg2, int32_t arg3) {
    int i;
    int matched;
    unsigned char local_48[72];
    long ret;
    long var10;
    long var12;
    long var13;
    long var2;
    int var20;
    long var21;
    long var23;
    long var27;
    long var3;
    long var31;
    long var34;
    int var36;
    long var37;
    long var4;
    int var43;
    // x86-64 prologue: save callee registers, frame 8 bytes
    ret = 0xffffffff;
    if (((unsigned long)(16) < (unsigned long)((unsigned long)((unsigned int)(arg3))))) {
        goto L_117e;
    }
    if (((unsigned long)(16) < (unsigned long)((unsigned long)((unsigned int)(arg1))))) {
        goto L_117e;
    }
    if ((arg0 == 0)) {
        goto L_117e;
    }
    if ((arg2 == 0)) {
        goto L_117e;
    }
    if (((unsigned long)((unsigned int)(arg3)) == 0)) {
        goto L_1180;
    }
    *(int *)(&local_48[0]) = 0;
    var2 = var3;
    if (((unsigned long)((unsigned int)(arg3)) != 1)) {
        goto L_1184;
    }
    L_112b: ;
    if ((((unsigned long)((unsigned int)(arg1)) == 0) | ((long)(arg1) < 0))) {
        goto L_117e;
    }
    var4 = (unsigned long)((unsigned int)(arg1));
    i = 0;
    var10 = 0;
    do {
        var12 = (*(char *)(((long)arg0 + i)) & 255);
        if (((((unsigned long)((unsigned int)(var10)) == 0) | ((long)((int)(var10)) < 0)) == 0)) {
            var13 = var10;
            do {
                var2 = (unsigned long)((unsigned int)(var13));
                var10 = var13;
                if (((unsigned char)((var12 & 255)) == (unsigned char)(arg2[(unsigned long)((unsigned int)(var13))]))) {
                    break;
                }
                var13 = (unsigned long)((unsigned int)(*(int *)((&local_48[0] + ((unsigned long)((unsigned int)((var13 - 1))) * 4)))));
                var10 = var13;
            } while (((((unsigned long)((unsigned int)(var13)) == 0) | ((long)((int)(var13)) < 0)) == 0));
        }
        var2 = ((unsigned char)((var12 & 255)) == (unsigned char)(arg2[(long)((int)(var10))]));
        var20 = ((long)((int)(var10)) + var2);
        var21 = (unsigned long)((unsigned int)(var20));
        if (((unsigned int)(var20) == (unsigned int)(arg3))) {
            var43 = ((unsigned int)((i - arg3)) + 1);
            ret = (unsigned long)((unsigned int)(var43));
            // x86-64 epilogue: restore callee registers
            return (unsigned int)(var43);
        }
        i = (i + 1);
        var10 = var21;
    } while ((i != var4));
    L_117e: ;
    // x86-64 epilogue: restore callee registers
    return ret;
    L_1180: ;
    // x86-64 epilogue: restore callee registers
    return 0;
    L_1184: ;
    var23 = (unsigned long)((unsigned int)(arg3));
    var27 = 1;
    matched = 0;
    goto L_11c1;
    L_11a0: ;
    var2 = ((unsigned char)((var34 & 255)) == (unsigned char)(arg2[(long)((int)(var31))]));
    var36 = ((long)((int)(var31)) + var2);
    *(int *)((&local_48[0] + (var27 * 4))) = var36;
    var37 = (var27 + 1);
    var27 = var37;
    matched = (unsigned long)((unsigned int)(var36));
    if ((var37 == var23)) {
        goto L_112b;
    }
    L_11c1: ;
    var34 = (*(char *)(((long)arg2 + var27)) & 255);
    var31 = (unsigned long)((unsigned int)(matched));
    if ((((unsigned long)((unsigned int)(matched)) == 0) | ((long)(matched) < 0))) {
        goto L_11a0;
    }
    do {
        var31 = (unsigned long)((unsigned int)(matched));
        if (((unsigned char)((var34 & 255)) == (unsigned char)(arg2[(unsigned long)((unsigned int)(matched))]))) {
            goto L_11a0;
        }
        matched = (unsigned long)((unsigned int)(*(int *)((&local_48[0] + ((unsigned long)((unsigned int)((matched - 1))) * 4)))));
    } while (((((unsigned long)((unsigned int)(matched)) == 0) | ((long)(matched) < 0)) == 0));
    var31 = (unsigned long)((unsigned int)(matched));
    goto L_11a0;
}

gcc -O0

1/1
kmp_search pass 83 lines 
// glaurung: kmp_search @ 0x1119
int32_t kmp_search(const uint8_t * arg0, int32_t arg1, const uint8_t * arg2, int32_t arg3) {
    extern __attribute__((noreturn)) void __stack_chk_fail(void);
    int matched;
    int i;
    unsigned char local_50[64];
    long local_8;
    long ret;
    local_8 = (long)(0x28);
    matched = 0;
    if ((arg0 != 0)) {
        if ((arg2 != 0)) {
            if ((0 <= (long)(arg1))) {
                if (((((unsigned long)((unsigned int)(arg1)) == 16) | ((long)(arg1) < 16)) != 0)) {
                    if ((0 <= (long)(arg3))) {
                        if ((((unsigned long)((unsigned int)(arg3)) == 16) | ((long)(arg3) < 16))) {
                            goto L_1179;
                        }
                    }
                }
            }
        }
    }
    ret = 0xffffffff;
    goto L_12a7;
    L_1179: ;
    if (((unsigned long)((unsigned int)(arg3)) == 0)) {
        ret = 0;
        goto L_12a7;
    }
    *(int *)(&local_50[0]) = 0;
    i = 1;
    goto L_120a;
    L_1199: ;
    matched = *(int *)((&local_50[0] + ((long)((int)(((unsigned long)((unsigned int)(matched)) - 1))) * 4)));
    L_11a8: ;
    if (((((unsigned long)((unsigned int)(matched)) == 0) | ((long)(matched) < 0)) == 0)) {
        if (((unsigned char)(((unsigned int)((unsigned char)(arg2[i])) & 255)) != (unsigned char)(((unsigned int)((unsigned char)(arg2[matched])) & 255)))) {
            goto L_1199;
        }
    }
    if (((unsigned char)(((unsigned int)((unsigned char)(arg2[i])) & 255)) == (unsigned char)(((unsigned int)((unsigned char)(arg2[matched])) & 255)))) {
        matched = (matched + 1);
    }
    *(int *)((&local_50[0] + ((long)(i) * 4))) = matched;
    i = (i + 1);
    L_120a: ;
    if ((i < arg3)) {
        goto L_11a8;
    }
    matched = 0;
    i = 0;
    goto L_129a;
    L_1222: ;
    matched = *(int *)((&local_50[0] + ((long)((int)(((unsigned long)((unsigned int)(matched)) - 1))) * 4)));
    L_1231: ;
    if (((((unsigned long)((unsigned int)(matched)) == 0) | ((long)(matched) < 0)) == 0)) {
        if (((unsigned char)(((unsigned int)((unsigned char)(arg0[i])) & 255)) != (unsigned char)(((unsigned int)((unsigned char)(arg2[matched])) & 255)))) {
            goto L_1222;
        }
    }
    if (((unsigned char)(((unsigned int)((unsigned char)(arg0[i])) & 255)) == (unsigned char)(((unsigned int)((unsigned char)(arg2[matched])) & 255)))) {
        matched = (matched + 1);
    }
    if (((unsigned int)(matched) == (unsigned int)(arg3))) {
        ret = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(i)) - arg3))) + 1)));
        goto L_12a7;
    }
    i = (i + 1);
    L_129a: ;
    if ((i < arg1)) {
        goto L_1231;
    }
    ret = 0xffffffff;
    L_12a7: ;
    if ((local_8 == 0x28)) {
        // x86-64 epilogue: restore rbp
        return ret;
    }
    __stack_chk_fail();
    // x86-64 epilogue: restore rbp
    return ret;
}

gcc -O2

1/1
kmp_search pass 159 lines 
// glaurung: kmp_search @ 0x1120
int32_t kmp_search(const uint8_t * arg0, int32_t arg1, const uint8_t * arg2, int32_t arg3) {
    extern __attribute__((noreturn)) void __stack_chk_fail(void);
    int matched;
    int i;
    long local_10;
    unsigned char local_58[64];
    long ret;
    long var10;
    int var11;
    long var19;
    long var2;
    long var23;
    int var24;
    long var25;
    long var26;
    long var27;
    long var3;
    int var32;
    long var34;
    long var35;
    long var36;
    long var4;
    long var5;
    long var7;
    long var9;
    local_10 = (long)(0x28);
    ret = 0;
    if ((arg0 == 0)) {
        goto L_1270;
    }
    if ((arg2 == 0)) {
        goto L_1270;
    }
    var2 = (unsigned long)((unsigned int)(arg1));
    if (((unsigned long)(16) < (unsigned long)((unsigned long)((unsigned int)(arg1))))) {
        goto L_1270;
    }
    var3 = (unsigned long)((unsigned int)(arg3));
    if (((unsigned long)(16) < (unsigned long)((unsigned long)((unsigned int)(arg3))))) {
        goto L_1270;
    }
    if (((unsigned long)((unsigned int)(arg3)) == 0)) {
        goto L_123d;
    }
    *(int *)(&local_58[0]) = 0;
    var4 = var5;
    if (((unsigned long)((unsigned int)(arg3)) == 1)) {
        goto L_11c9;
    }
    var7 = 1;
    var9 = ((unsigned long)((unsigned int)((arg3 - 2))) + 2);
    var10 = ret;
    L_1190: ;
    var11 = (unsigned int)((unsigned char)(*(char *)(((long)arg2 + var7))));
    if (((((unsigned long)((unsigned int)(var10)) == 0) | ((long)((int)(var10)) < 0)) == 0)) {
        goto L_11b0;
    }
    ret = var10;
    goto L_1258;
    L_11a0: ;
    ret = (unsigned long)((unsigned int)(*(int *)((&local_58[0] + ((long)((int)((var10 - 1))) * 4)))));
    var10 = ret;
    if ((((unsigned long)((unsigned int)(ret)) == 0) | ((long)((int)(ret)) < 0))) {
        goto L_1258;
    }
    L_11b0: ;
    ret = var10;
    if (((unsigned char)((var11 & 255)) != (unsigned char)(arg2[(long)((int)(var10))]))) {
        goto L_11a0;
    }
    L_11b9: ;
    ret = (unsigned long)((unsigned int)((ret + 1)));
    L_11bc: ;
    *(int *)((&local_58[0] + (var7 * 4))) = ret;
    var4 = (var7 + 1);
    var7 = var4;
    var10 = ret;
    if ((var9 != var4)) {
        goto L_1190;
    }
    L_11c9: ;
    if (((unsigned long)((unsigned int)(var2)) == 0)) {
        goto L_1270;
    }
    var19 = 0;
    matched = 0;
    var23 = (unsigned long)((unsigned int)((var2 - 1)));
    var24 = (unsigned int)((unsigned char)(*(char *)((long)arg0)));
    var25 = 0;
    var26 = 0;
    var27 = 0;
    if (0) {
        goto L_11fc;
    }
    goto L_1228;
    L_11f0: ;
    matched = (unsigned long)((unsigned int)(*(int *)((&local_58[0] + ((long)((int)((var27 - 1))) * 4)))));
    var27 = (unsigned long)((unsigned int)(matched));
    var19 = var26;
    if ((((unsigned long)((unsigned int)(matched)) == 0) | ((long)(matched) < 0))) {
        goto L_1228;
    }
    L_11fc: ;
    var19 = var26;
    matched = var27;
    if (((unsigned char)(arg2[(long)((int)(var27))]) != (unsigned char)((var24 & 255)))) {
        goto L_11f0;
    }
    L_1205: ;
    var32 = (matched + 1);
    var34 = var19;
    var27 = (unsigned long)((unsigned int)(var32));
    var35 = (unsigned long)((unsigned int)(var32));
    if (((unsigned int)(var32) == (unsigned int)(var3))) {
        goto L_1236;
    }
    L_120d: ;
    var36 = (var34 + 1);
    if ((var23 == var34)) {
        goto L_1270;
    }
    var19 = var36;
    var24 = (unsigned int)((unsigned char)(*(char *)(((long)arg0 + var36))));
    var25 = (unsigned long)((unsigned int)(var36));
    var26 = var36;
    if (((((unsigned long)((unsigned int)(var27)) == 0) | ((long)((int)(var27)) < 0)) == 0)) {
        goto L_11fc;
    }
    matched = var27;
    L_1228: ;
    if (((unsigned char)(arg2[matched]) == (unsigned char)((var24 & 255)))) {
        goto L_1205;
    }
    var34 = var19;
    var27 = (unsigned long)((unsigned int)(matched));
    var35 = (unsigned long)((unsigned int)(matched));
    if (((unsigned int)(matched) != (unsigned int)(var3))) {
        goto L_120d;
    }
    L_1236: ;
    ret = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)((var25 - var35))) + 1)));
    L_123d: ;
    if ((local_10 != 0x28)) {
        goto L_1277;
    }
    // x86-64 epilogue: tear down frame
    return ret;
    L_1258: ;
    if (((unsigned char)((var11 & 255)) != (unsigned char)(arg2[(long)((int)(ret))]))) {
        goto L_11bc;
    }
    goto L_11b9;
    L_1270: ;
    ret = 0xffffffff;
    goto L_123d;
    L_1277: ;
    __stack_chk_fail();
}

← 213 fixtures