glaurung

Fixture 32

longest common subsequence

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

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

Longest common subsequence length plus a reconstructed subsequence. The reconstruction walks the table backwards and writes into a caller-owned output buffer, so both the forward table stride and a reverse loop with a two-variable induction must survive lowering.

tests/decompiler_fixtures/src/32_longest_common_subsequence.c source 
#include <stdint.h>

/* Longest common subsequence length plus a reconstructed subsequence.  The
 * reconstruction walks the table backwards and writes into a caller-owned
 * output buffer, so both the forward table stride and a reverse loop with a
 * two-variable induction must survive lowering. */

#define LCS_MAX 8
#define LCS_STRIDE (LCS_MAX + 1)

__attribute__((noinline)) int32_t
lcs_length(const uint8_t *left, int32_t left_length, const uint8_t *right,
           int32_t right_length) {
    int32_t table[LCS_STRIDE * LCS_STRIDE];
    int32_t i;
    int32_t j;
    if (left == 0 || right == 0 || left_length < 0 || right_length < 0 ||
        left_length > LCS_MAX || right_length > LCS_MAX) {
        return -1;
    }
    for (i = 0; i <= left_length; ++i) {
        for (j = 0; j <= right_length; ++j) {
            if (i == 0 || j == 0) {
                table[i * LCS_STRIDE + j] = 0;
            } else if (left[i - 1] == right[j - 1]) {
                table[i * LCS_STRIDE + j] =
                    table[(i - 1) * LCS_STRIDE + (j - 1)] + 1;
            } else {
                int32_t up = table[(i - 1) * LCS_STRIDE + j];
                int32_t back = table[i * LCS_STRIDE + (j - 1)];
                table[i * LCS_STRIDE + j] = (up >= back) ? up : back;
            }
        }
    }
    return table[left_length * LCS_STRIDE + right_length];
}

__attribute__((noinline)) int32_t
lcs_recover(const uint8_t *left, int32_t left_length, const uint8_t *right,
            int32_t right_length, uint8_t *output) {
    int32_t table[LCS_STRIDE * LCS_STRIDE];
    int32_t i;
    int32_t j;
    int32_t produced;
    int32_t head;
    if (left == 0 || right == 0 || output == 0 || left_length < 0 ||
        right_length < 0 || left_length > LCS_MAX || right_length > LCS_MAX) {
        return -1;
    }
    for (i = 0; i <= left_length; ++i) {
        for (j = 0; j <= right_length; ++j) {
            if (i == 0 || j == 0) {
                table[i * LCS_STRIDE + j] = 0;
            } else if (left[i - 1] == right[j - 1]) {
                table[i * LCS_STRIDE + j] =
                    table[(i - 1) * LCS_STRIDE + (j - 1)] + 1;
            } else {
                int32_t up = table[(i - 1) * LCS_STRIDE + j];
                int32_t back = table[i * LCS_STRIDE + (j - 1)];
                table[i * LCS_STRIDE + j] = (up >= back) ? up : back;
            }
        }
    }
    produced = 0;
    i = left_length;
    j = right_length;
    while (i > 0 && j > 0 && produced < LCS_MAX) {
        if (left[i - 1] == right[j - 1]) {
            output[produced] = left[i - 1];
            produced += 1;
            i -= 1;
            j -= 1;
        } else if (table[(i - 1) * LCS_STRIDE + j] >=
                   table[i * LCS_STRIDE + (j - 1)]) {
            i -= 1;
        } else {
            j -= 1;
        }
    }
    for (head = 0; head < produced / 2; ++head) {
        uint8_t swap = output[head];
        output[head] = output[produced - 1 - head];
        output[produced - 1 - head] = swap;
    }
    return produced;
}

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
lcs_length pass 62 lines 
// glaurung: lcs_length @ 0x1100
__attribute__((no_stack_protector)) int32_t lcs_length(const uint8_t * arg0, int32_t arg1, const uint8_t * arg2, int32_t arg3) {
    int i;
    int j;
    int up;
    int back;
    unsigned char local_170[324];
    int local_184;
    int local_4;
    // x86-64 prologue: save rbp, frame 272 bytes
    if ((arg0 == 0)) {
        local_4 = -1;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    if ((arg2 == 0)) {
        local_4 = -1;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    if (((long)(arg1) < 0)) {
        local_4 = -1;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    if (((long)(arg3) < 0)) {
        local_4 = -1;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    if (((((unsigned long)((unsigned int)(arg1)) == 8) | ((long)(arg1) < 8)) == 0)) {
        local_4 = -1;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    if (((((unsigned long)((unsigned int)(arg3)) == 8) | ((long)(arg3) < 8)) == 0)) {
        local_4 = -1;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    i = 0;
    while (((((unsigned int)(i) == (unsigned int)(arg1)) | (i < arg1)) != 0)) {
        for (j = 0; ((((unsigned int)(j) == (unsigned int)(arg3)) | (j < arg3)) != 0); j++) {
            if ((((unsigned long)((unsigned int)(i)) == 0) || ((unsigned long)((unsigned int)(j)) == 0))) {
                *(int *)((&local_170[0] + ((long)((int)(((i * 9) + j))) * 4))) = 0;
            } else {
                if (((unsigned int)((unsigned char)(arg0[(long)((int)(((unsigned long)((unsigned int)(i)) - 1)))])) != (unsigned int)((unsigned char)(arg2[(long)((int)(((unsigned long)((unsigned int)(j)) - 1)))])))) {
                    up = *(int *)((&local_170[0] + ((long)((int)((((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(i)) - 1))) * 9) + j))) * 4)));
                    back = *(int *)((&local_170[0] + ((long)((int)(((i * 9) + (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(j)) - 1)))))) * 4)));
                    local_184 = ((up < back) ? (unsigned long)((unsigned int)(back)) : (unsigned long)((unsigned int)(up)));
                    *(int *)((&local_170[0] + ((long)((int)(((i * 9) + j))) * 4))) = local_184;
                } else {
                    *(int *)((&local_170[0] + ((long)((int)(((i * 9) + j))) * 4))) = ((unsigned long)((unsigned int)(*(int *)((&local_170[0] + ((long)((int)((((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(i)) - 1))) * 9) + (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(j)) - 1)))))) * 4))))) + 1);
                }
            }
        }
        i = ((unsigned int)(i) + 1);
    }
    local_4 = *(int *)((&local_170[0] + ((long)((int)(((arg1 * 9) + arg3))) * 4)));
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
}
lcs_recover pass 127 lines 
// glaurung: lcs_recover @ 0x1320
__attribute__((no_stack_protector)) int32_t lcs_recover(const uint8_t * arg0, int32_t arg1, const uint8_t * arg2, int32_t arg3, uint8_t * arg4) {
    int i;
    int j;
    int up;
    int back;
    int produced;
    int head;
    unsigned char swap;
    unsigned char local_180[324];
    int local_1a0;
    signed char local_1a1;
    int local_1a8;
    int local_4;
    long var66;
    if ((arg0 != 0)) {
        if ((arg2 != 0)) {
            if ((arg4 != 0)) {
                if ((0 <= (long)(arg1))) {
                    if ((0 <= (long)(arg3))) {
                        if (((((unsigned long)((unsigned int)(arg1)) == 8) | ((long)(arg1) < 8)) != 0)) {
                            if ((((unsigned long)((unsigned int)(arg3)) == 8) | ((long)(arg3) < 8))) {
                                goto L_1392;
                            }
                        }
                    }
                }
            }
        }
    }
    local_4 = -1;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
    L_1392: ;
    i = 0;
    L_139c: ;
    if (((((unsigned int)(i) == (unsigned int)(arg1)) | (i < arg1)) == 0)) {
        goto L_152f;
    }
    j = 0;
    L_13b5: ;
    if (((((unsigned int)(j) == (unsigned int)(arg3)) | (j < arg3)) == 0)) {
        goto L_1516;
    }
    if (((unsigned long)((unsigned int)(i)) != 0)) {
        if (((unsigned long)((unsigned int)(j)) != 0)) {
            goto L_13fd;
        }
    }
    *(int *)((&local_180[0] + ((long)((int)(((i * 9) + j))) * 4))) = 0;
    goto L_14fd;
    L_13fd: ;
    if (((unsigned int)((unsigned char)(arg0[(long)((int)(((unsigned long)((unsigned int)(i)) - 1)))])) == (unsigned int)((unsigned char)(arg2[(long)((int)(((unsigned long)((unsigned int)(j)) - 1)))])))) {
        *(int *)((&local_180[0] + ((long)((int)(((i * 9) + j))) * 4))) = ((unsigned long)((unsigned int)(*(int *)((&local_180[0] + ((long)((int)((((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(i)) - 1))) * 9) + (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(j)) - 1)))))) * 4))))) + 1);
        goto L_14f8;
    }
    up = *(int *)((&local_180[0] + ((long)((int)((((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(i)) - 1))) * 9) + j))) * 4)));
    back = *(int *)((&local_180[0] + ((long)((int)(((i * 9) + (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(j)) - 1)))))) * 4)));
    if ((back <= up)) {
        local_1a0 = up;
        goto L_14dc;
    }
    local_1a0 = back;
    L_14dc: ;
    *(int *)((&local_180[0] + ((long)((int)(((i * 9) + j))) * 4))) = local_1a0;
    L_14f8: ;
    goto L_14fd;
    L_14fd: ;
    goto L_1502;
    L_1502: ;
    j = ((unsigned int)(j) + 1);
    goto L_13b5;
    L_1516: ;
    goto L_151b;
    L_151b: ;
    i = ((unsigned int)(i) + 1);
    goto L_139c;
    L_152f: ;
    produced = 0;
    i = arg1;
    var66 = (unsigned long)((unsigned int)(arg3));
    j = arg3;
    L_154b: ;
    local_1a1 = 0;
    if (((((unsigned long)((unsigned int)(i)) == 0) | ((long)(i) < 0)) == 0)) {
        local_1a1 = 0;
        if (((((unsigned long)((unsigned int)(j)) == 0) | ((long)(j) < 0)) == 0)) {
            local_1a1 = ((long)(produced) < 8);
        }
    }
    if (((unsigned long)((unsigned char)((local_1a1 & 1))) == 0)) {
        goto L_1685;
    }
    if (((unsigned int)((unsigned char)(arg0[(long)((int)(((unsigned long)((unsigned int)(i)) - 1)))])) == (unsigned int)((unsigned char)(arg2[(long)((int)(((unsigned long)((unsigned int)(j)) - 1)))])))) {
        arg4[produced] = arg0[(long)((int)(((unsigned long)((unsigned int)(i)) - 1)))];
        produced = ((unsigned int)(produced) + 1);
        i = ((unsigned int)(i) - 1);
        var66 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(j)) - 1)));
        j = var66;
        goto L_1680;
    }
    if (((long)((int)(*(int *)((&local_180[0] + ((long)((int)(((i * 9) + (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(j)) - 1)))))) * 4))))) <= (long)((int)(*(int *)((&local_180[0] + ((long)((int)((((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(i)) - 1))) * 9) + j))) * 4))))))) {
        var66 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(i)) - 1)));
        i = var66;
        goto L_167b;
    }
    var66 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(j)) - 1)));
    j = var66;
    L_167b: ;
    goto L_1680;
    L_1680: ;
    goto L_154b;
    L_1685: ;
    head = 0;
    L_168f: ;
    local_1a8 = head;
    if (((long)(local_1a8) < (long)((int)(((int)((((long long)(int)((((unsigned long)((long)((int)((unsigned long)((unsigned int)(produced))))) >> 32) & 0xffffffff)) * (((long long)1) << 32)) + (unsigned int)((unsigned long)((unsigned int)(produced)))) / (int)(2))))))) {
        swap = arg4[head];
        arg4[head] = arg4[(long)((int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(produced)) - 1))) - head)))];
        arg4[(long)((int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(produced)) - 1))) - head)))] = swap;
        head = ((unsigned int)(head) + 1);
        goto L_168f;
    }
    local_4 = produced;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
}

clang -O2

2/2
lcs_length pass 77 lines 
// glaurung: lcs_length @ 0x1100
__attribute__((no_stack_protector)) int32_t lcs_length(const uint8_t * arg0, int32_t arg1, const uint8_t * arg2, int32_t arg3) {
    int up;
    int back;
    int j;
    int i;
    unsigned char local_158[344];
    long ret;
    long var10;
    long var14;
    long var17;
    long var18;
    long var3;
    long var4;
    long var5;
    long var8;
    // x86-64 prologue: save callee registers, frame 16 bytes
    ret = 0xffffffff;
    if (((((unsigned long)((unsigned int)(arg3)) == 8) | ((long)(arg3) < 8)) == 0)) {
        // x86-64 epilogue: restore callee registers
        return ret;
    }
    if (((((unsigned long)((unsigned int)(arg1)) == 8) | ((long)(arg1) < 8)) == 0)) {
        // x86-64 epilogue: restore callee registers
        return ret;
    }
    if ((arg0 == 0)) {
        // x86-64 epilogue: restore callee registers
        return ret;
    }
    if ((arg2 == 0)) {
        // x86-64 epilogue: restore callee registers
        return ret;
    }
    if (((long)((int)(((unsigned long)((unsigned int)(arg3)) | arg1))) < 0)) {
        // x86-64 epilogue: restore callee registers
        return ret;
    }
    if ((0 <= (long)(arg1))) {
        var3 = (unsigned long)((unsigned int)((arg3 + 1)));
        var4 = (unsigned long)((unsigned int)((arg1 + 1)));
        var5 = (long)(&local_158[0]);
        var8 = 0;
        do {
            var10 = ret;
            if ((0 <= (long)(arg3))) {
                var14 = 0;
                do {
                    var17 = 0;
                    var18 = 0;
                    if ((var8 != 0)) {
                        var18 = var17;
                        if ((var14 != 0)) {
                            if (((unsigned char)(((unsigned int)((unsigned char)(*(char *)(((long)arg0 + var8 - 0x1)))) & 255)) != (unsigned char)(*(char *)(((long)arg2 + var14 - 0x1))))) {
                                up = (unsigned long)((unsigned int)(*(int *)((var5 + var14 * 4 - 0x24))));
                                back = (unsigned long)((unsigned int)(*(int *)((var5 + var14 * 4 - 0x4))));
                                var18 = ((up < back) ? back : up);
                            } else {
                                var18 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(*(int *)((var5 + var14 * 4 - 0x28)))) + 1)));
                            }
                        }
                    }
                    *(int *)((var5 + var14 * 4)) = var18;
                    j = (var14 + 1);
                    var10 = (unsigned long)((unsigned int)(j));
                    var14 = (unsigned long)((unsigned int)(j));
                } while ((var3 != j));
            }
            i = (var8 + 1);
            var5 = (var5 + 36);
            var8 = (unsigned long)((unsigned int)(i));
            ret = var10;
        } while ((i != var4));
    }
    // x86-64 epilogue: restore callee registers
    return (unsigned int)(*(int *)((&local_158[0] + ((long)((int)(((unsigned long)((unsigned int)((arg1 + (arg1 * 8)))) + arg3))) * 4))));
}
lcs_recover pass 194 lines 
// glaurung: lcs_recover @ 0x11e0
__attribute__((no_stack_protector)) int32_t lcs_recover(const uint8_t * arg0, int32_t arg1, const uint8_t * arg2, int32_t arg3, uint8_t * arg4) {
    int i;
    int up;
    int back;
    int j;
    int produced;
    int head;
    unsigned char swap;
    unsigned char local_168[360];
    long ret;
    long var0;
    long var22;
    long var27;
    long var30;
    long var36;
    long var4;
    long var40;
    long var41;
    long var42;
    int var43;
    long var44;
    long var5;
    long var50;
    long var51;
    long var6;
    long var61;
    long var69;
    long var72;
    long var77;
    long var78;
    int var81;
    long var83;
    int var85;
    long var9;
    long var90;
    int var93;
    // x86-64 prologue: save callee registers, frame 24 bytes
    var0 = 0xffffffff;
    ret = 0xffffffff;
    if (((((unsigned long)((unsigned int)(arg3)) == 8) | ((long)(arg3) < 8)) == 0)) {
        goto L_134c;
    }
    ret = var0;
    if (((((unsigned long)((unsigned int)(arg1)) == 8) | ((long)(arg1) < 8)) == 0)) {
        goto L_134c;
    }
    ret = var0;
    if (((long)((int)(((unsigned long)((unsigned int)(arg3)) | arg1))) < 0)) {
        goto L_134c;
    }
    ret = var0;
    if ((arg0 == 0)) {
        goto L_134c;
    }
    ret = var0;
    if ((arg2 == 0)) {
        goto L_134c;
    }
    ret = var0;
    if ((arg4 == 0)) {
        goto L_134c;
    }
    if (((long)(arg1) < 0)) {
        goto L_134a;
    }
    var4 = (unsigned long)((unsigned int)((arg3 + 1)));
    var5 = (unsigned long)((unsigned int)((arg1 + 1)));
    var6 = (long)(&local_168[0]);
    var9 = 0;
    goto L_125d;
    L_1250: ;
    i = (var9 + 1);
    var6 = (var6 + 36);
    var9 = (unsigned long)((unsigned int)(i));
    if ((i == var5)) {
        goto L_12ae;
    }
    L_125d: ;
    if (((long)(arg3) < 0)) {
        goto L_1250;
    }
    var22 = 0;
    goto L_128c;
    L_1270: ;
    up = (unsigned long)((unsigned int)(*(int *)((var6 + var22 * 4 - 0x24))));
    back = (unsigned long)((unsigned int)(*(int *)((var6 + var22 * 4 - 0x4))));
    var27 = ((up < back) ? back : up);
    L_127f: ;
    *(int *)((var6 + var22 * 4)) = var27;
    j = (var22 + 1);
    var22 = (unsigned long)((unsigned int)(j));
    if ((var4 == j)) {
        goto L_1250;
    }
    L_128c: ;
    var30 = 0;
    var27 = 0;
    if ((var9 == 0)) {
        goto L_127f;
    }
    var27 = var30;
    if ((var22 == 0)) {
        goto L_127f;
    }
    if (((unsigned char)(((unsigned int)((unsigned char)(*(char *)(((long)arg0 + var9 - 0x1)))) & 255)) != (unsigned char)(*(char *)(((long)arg2 + var22 - 0x1))))) {
        goto L_1270;
    }
    var27 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(*(int *)((var6 + var22 * 4 - 0x28)))) + 1)));
    goto L_127f;
    L_12ae: ;
    var36 = 0;
    ret = 0;
    if ((((unsigned long)((unsigned int)(arg1)) == 0) | ((long)(arg1) < 0))) {
        goto L_134c;
    }
    ret = var36;
    if ((((unsigned long)((unsigned int)(arg3)) == 0) | ((long)(arg3) < 0))) {
        goto L_134c;
    }
    produced = 0;
    var40 = (unsigned long)((unsigned int)(arg3));
    var41 = (unsigned long)((unsigned int)(arg1));
    L_12d0: ;
    var42 = (unsigned long)((unsigned int)((var41 - 1)));
    var43 = (unsigned int)((unsigned char)(*(char *)(((long)arg0 + var42))));
    var44 = (unsigned long)((unsigned int)((var40 - 1)));
    if (((unsigned char)((var43 & 255)) == (unsigned char)(*(char *)(((long)arg2 + var44))))) {
        arg4[produced] = var43;
        produced = (unsigned long)((unsigned int)(((long)(produced) + 1)));
        var50 = (unsigned long)((unsigned int)(var44));
        var51 = (unsigned long)((unsigned int)(var42));
        goto L_1324;
    }
    var61 = var44;
    var51 = var41;
    if (((long)((int)(*(int *)((&local_168[0] + ((long)((int)(((unsigned long)((unsigned int)((var41 + (var41 * 8)))) + var44))) * 4))))) <= (long)((int)(*(int *)((&local_168[0] + ((long)((int)(((unsigned long)((unsigned int)((var42 + (var42 * 8)))) + var40))) * 4))))))) {
        var61 = (unsigned long)((unsigned int)(var40));
        var51 = (unsigned long)((unsigned int)(var42));
    }
    var50 = (unsigned long)((unsigned int)(var61));
    L_1324: ;
    if (((((unsigned long)((unsigned int)(var51)) == 0) | ((long)((int)(var51)) < 0)) == 0)) {
        if (((((unsigned long)((unsigned int)(var50)) == 0) | ((long)((int)(var50)) < 0)) == 0)) {
            var40 = var50;
            var41 = var51;
            if (((long)(produced) < 8)) {
                goto L_12d0;
            }
        }
    }
    ret = (unsigned long)((unsigned int)(produced));
    if (((long)(produced) < 2)) {
        goto L_134c;
    }
    var69 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(produced)) >> 1))) & 127)));
    if (((unsigned long)((unsigned int)(var69)) != 1)) {
        goto L_1358;
    }
    var72 = 0;
    goto L_13ab;
    L_134a: ;
    ret = 0;
    L_134c: ;
    // x86-64 epilogue: restore callee registers
    return ret;
    L_1358: ;
    var77 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var69)) & -2)));
    var78 = (unsigned long)((unsigned int)((produced - 2)));
    head = 0;
    do {
        var81 = (unsigned int)((unsigned char)(*(char *)(((long)arg4 + head))));
        var83 = (long)((int)((var78 + 1)));
        *(signed char *)(((long)arg4 + head)) = *(char *)(((long)arg4 + var83));
        *(signed char *)(((long)arg4 + var83)) = var81;
        var85 = (unsigned int)((unsigned char)(*(char *)(((long)arg4 + head + 0x1))));
        *(signed char *)(((long)arg4 + head + 0x1)) = arg4[(long)((int)(var78))];
        arg4[(long)((int)(var78))] = var85;
        head = (head + 2);
        var78 = (unsigned long)((unsigned int)(((long)((int)(var78)) - 2)));
        var72 = (unsigned long)((unsigned int)(head));
    } while ((var77 != head));
    L_13ab: ;
    ret = (unsigned long)((unsigned int)(produced));
    if (((unsigned long)((unsigned char)((var69 & 1))) == 0)) {
        goto L_134c;
    }
    var90 = (*(char *)(((long)arg4 + var72)) & 255);
    var93 = ((~(unsigned long)((unsigned int)(var72))) + produced);
    *(signed char *)(((long)arg4 + var72)) = arg4[(long)((int)(var93))];
    arg4[(long)((int)(var93))] = var90;
    ret = (unsigned long)((unsigned int)(produced));
    goto L_134c;
}

gcc -O0

2/2
lcs_length pass 44 lines 
// glaurung: lcs_length @ 0x1119
int32_t lcs_length(const uint8_t * arg0, int32_t arg1, const uint8_t * arg2, int32_t arg3) {
    extern __attribute__((noreturn)) void __stack_chk_fail(void);
    int i;
    int j;
    int up;
    int back;
    unsigned char local_150[324];
    long local_8;
    long ret;
    long var28;
    long var65;
    // x86-64 prologue: save rbp, frame 384 bytes
    local_8 = (long)(0x28);
    if (((((((arg0 == 0) || (arg2 == 0)) || ((long)(arg1) < 0)) || ((long)(arg3) < 0)) || ((((unsigned long)((unsigned int)(arg1)) == 8) | ((long)(arg1) < 8)) == 0)) || (((unsigned long)((unsigned int)(arg3)) != 8) && (8 <= (long)(arg3))))) {
        ret = 0xffffffff;
    } else {
        i = 0;
        while (((((unsigned int)(i) == (unsigned int)(arg1)) | (i < arg1)) != 0)) {
            for (j = 0; ((((unsigned int)(j) == (unsigned int)(arg3)) | (j < arg3)) != 0); j++) {
                if ((((unsigned long)((unsigned int)(i)) == 0) || ((unsigned long)((unsigned int)(j)) == 0))) {
                    *(int *)((&local_150[0] + ((long)((int)(((unsigned long)((unsigned int)(j)) + (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(i)) + (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(i)) << 3))))))))) * 4))) = 0;
                } else {
                    if (((unsigned char)(((unsigned int)((unsigned char)(arg0[((long)(i) - 1)])) & 255)) != (unsigned char)(((unsigned int)((unsigned char)(arg2[((long)(j) - 1)])) & 255)))) {
                        var28 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(i)) - 1)));
                        up = *(int *)((&local_150[0] + ((long)((int)(((unsigned long)((unsigned int)(j)) + (unsigned long)((unsigned int)((var28 + (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var28)) << 3))))))))) * 4)));
                        back = *(int *)((&local_150[0] + ((long)((int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(j)) - 1))) + (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(i)) + (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(i)) << 3))))))))) * 4)));
                        *(int *)((&local_150[0] + ((long)((int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(i)) + (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(i)) << 3)))))) + (unsigned long)((unsigned int)(j))))) * 4))) = ((up < back) ? (unsigned long)((unsigned int)(back)) : (unsigned long)((unsigned int)(up)));
                    } else {
                        var65 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(i)) - 1)));
                        *(int *)((&local_150[0] + ((long)((int)(((unsigned long)((unsigned int)(j)) + (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(i)) + (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(i)) << 3))))))))) * 4))) = ((unsigned long)((unsigned int)(*(int *)((&local_150[0] + ((long)((int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(j)) - 1))) + (unsigned long)((unsigned int)((var65 + (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var65)) << 3))))))))) * 4))))) + 1);
                    }
                }
            }
            i = (i + 1);
        }
        ret = (unsigned long)((unsigned int)(*(int *)((&local_150[0] + ((long)((int)(((unsigned long)((unsigned int)(arg3)) + (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(arg1)) + (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(arg1)) << 3))))))))) * 4)))));
    }
    if ((local_8 != 0x28)) {
        __stack_chk_fail();
    }
    // x86-64 epilogue: restore rbp
    return ret;
}
lcs_recover pass 74 lines 
// glaurung: lcs_recover @ 0x134c
int32_t lcs_recover(const uint8_t * arg0, int32_t arg1, const uint8_t * arg2, int32_t arg3, uint8_t * arg4) {
    extern __attribute__((noreturn)) void __stack_chk_fail(void);
    int i;
    int j;
    int up;
    int back;
    int produced;
    int head;
    unsigned char swap;
    unsigned char local_150[324];
    long local_8;
    long ret;
    long var104;
    long var28;
    long var65;
    // x86-64 prologue: save rbp, frame 400 bytes
    local_8 = (long)(0x28);
    if ((((((((arg0 == 0) || (arg2 == 0)) || (arg4 == 0)) || ((long)(arg1) < 0)) || ((long)(arg3) < 0)) || ((((unsigned long)((unsigned int)(arg1)) == 8) | ((long)(arg1) < 8)) == 0)) || (((unsigned long)((unsigned int)(arg3)) != 8) && (8 <= (long)(arg3))))) {
        ret = 0xffffffff;
    } else {
        i = 0;
        while (((((unsigned int)(i) == (unsigned int)(arg1)) | (i < arg1)) != 0)) {
            for (j = 0; ((((unsigned int)(j) == (unsigned int)(arg3)) | (j < arg3)) != 0); j++) {
                if ((((unsigned long)((unsigned int)(i)) == 0) || ((unsigned long)((unsigned int)(j)) == 0))) {
                    *(int *)((&local_150[0] + ((long)((int)(((unsigned long)((unsigned int)(j)) + (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(i)) + (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(i)) << 3))))))))) * 4))) = 0;
                } else {
                    if (((unsigned char)(((unsigned int)((unsigned char)(arg0[((long)(i) - 1)])) & 255)) != (unsigned char)(((unsigned int)((unsigned char)(arg2[((long)(j) - 1)])) & 255)))) {
                        var28 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(i)) - 1)));
                        up = *(int *)((&local_150[0] + ((long)((int)(((unsigned long)((unsigned int)(j)) + (unsigned long)((unsigned int)((var28 + (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var28)) << 3))))))))) * 4)));
                        back = *(int *)((&local_150[0] + ((long)((int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(j)) - 1))) + (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(i)) + (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(i)) << 3))))))))) * 4)));
                        *(int *)((&local_150[0] + ((long)((int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(i)) + (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(i)) << 3)))))) + (unsigned long)((unsigned int)(j))))) * 4))) = ((up < back) ? (unsigned long)((unsigned int)(back)) : (unsigned long)((unsigned int)(up)));
                    } else {
                        var65 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(i)) - 1)));
                        *(int *)((&local_150[0] + ((long)((int)(((unsigned long)((unsigned int)(j)) + (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(i)) + (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(i)) << 3))))))))) * 4))) = ((unsigned long)((unsigned int)(*(int *)((&local_150[0] + ((long)((int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(j)) - 1))) + (unsigned long)((unsigned int)((var65 + (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var65)) << 3))))))))) * 4))))) + 1);
                    }
                }
            }
            i = (i + 1);
        }
        produced = 0;
        i = arg1;
        j = arg3;
        while (((((unsigned long)((unsigned int)(i)) == 0) | ((long)(i) < 0)) == 0)) {
            if (((((unsigned long)((unsigned int)(j)) == 0) | ((long)(j) < 0)) || ((((unsigned long)((unsigned int)(produced)) == 7) | ((long)(produced) < 7)) == 0))) {
                break;
            }
            if (((unsigned char)(((unsigned int)((unsigned char)(arg0[((long)(i) - 1)])) & 255)) != (unsigned char)(((unsigned int)((unsigned char)(arg2[((long)(j) - 1)])) & 255)))) {
                var104 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(i)) - 1)));
                if (((long)((int)(*(int *)((&local_150[0] + ((long)((int)(((unsigned long)((unsigned int)(j)) + (unsigned long)((unsigned int)((var104 + (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var104)) << 3))))))))) * 4))))) < (long)((int)(*(int *)((&local_150[0] + ((long)((int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(j)) - 1))) + (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(i)) + (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(i)) << 3))))))))) * 4))))))) {
                    j = (j - 1);
                } else {
                    i = (i - 1);
                }
            } else {
                arg4[produced] = arg0[((long)(i) - 1)];
                produced = (produced + 1);
                i = (i - 1);
                j = (j - 1);
            }
        }
        for (head = 0; ((long)(head) < (long)((int)(((int)(((unsigned long)((unsigned int)(produced)) + (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(produced)) >> 31))))) >> 1)))); head++) {
            swap = arg4[head];
            arg4[head] = arg4[(long)((int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(produced)) - 1))) - head)))];
            arg4[(long)((int)(((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(produced)) - 1))) - head)))] = swap;
        }
        ret = (unsigned long)((unsigned int)(produced));
    }
    if ((local_8 != 0x28)) {
        __stack_chk_fail();
    }
    // x86-64 epilogue: restore rbp
    return ret;
}

gcc -O2

2/2
lcs_length pass 106 lines 
// glaurung: lcs_length @ 0x1120
int32_t lcs_length(const uint8_t * arg0, int32_t arg1, const uint8_t * arg2, int32_t arg3) {
    extern __attribute__((noreturn)) void __stack_chk_fail(void);
    int i;
    int j;
    unsigned char local_178[324];
    long local_30;
    long ret;
    long var14;
    long var15;
    long var17;
    long var18;
    long var2;
    long var28;
    long var29;
    long var3;
    long var31;
    long var4;
    int var40;
    long var5;
    long var6;
    long var7;
    long var9;
    local_30 = (long)(0x28);
    var2 = 0;
    if ((arg0 == 0)) {
        L_1240: ;
        ret = 0xffffffff;
    } else {
        var3 = (long)arg2;
        if ((arg2 == 0)) {
            goto L_1240;
        } else {
            var4 = (unsigned long)((unsigned int)(arg1));
            var5 = (unsigned long)((unsigned int)(arg3));
            if (((unsigned long)(8) < (unsigned long)((unsigned long)((unsigned int)(arg3))))) {
                goto L_1240;
            } else {
                if (((unsigned long)(8) < (unsigned long)((unsigned long)((unsigned int)(var4))))) {
                    goto L_1240;
                } else {
                    var6 = (long)(&local_178[0]);
                    var7 = (long)((arg0 - 1));
                    var9 = 0;
                    i = 0;
                    do {
                        var14 = (unsigned long)((unsigned int)((var9 - 9)));
                        var15 = (unsigned long)((unsigned int)((var9 - 1)));
                        var17 = ((unsigned long)((unsigned int)(i)) == 0);
                        var18 = (unsigned long)((unsigned int)((var9 - 10)));
                        j = 0;
                        L_11d5: ;
                        while (1) {
                            if (((unsigned long)((unsigned int)(j)) == 0)) {
                                goto L_11de;
                            }
                            goto L_11d9;
                            L_11a0: ;
                            if (((unsigned char)(*(char *)((var7))) == (unsigned char)(((unsigned int)((unsigned char)(*(char *)((var3 + j - 0x1)))) & 255)))) {
                                goto L_1230;
                            }
                            var28 = (unsigned long)((unsigned int)(*(int *)((&local_178[0] + ((long)((int)((var15 + j))) * 4)))));
                            var29 = (unsigned long)((unsigned int)(*(int *)((&local_178[0] + ((long)((int)((var14 + j))) * 4)))));
                            var31 = (((long)((int)(var28)) < (long)((int)(var29))) ? var29 : var28);
                            L_11ca: ;
                            *(int *)((var6 + j * 4)) = var31;
                            var2 = ((unsigned long)((unsigned int)(j)) + 1);
                            j = var2;
                            if (((long)((int)(var5)) < (long)((int)(var2)))) {
                                goto L_11eb;
                            }
                            goto L_11d5;
                            L_11d9: ;
                            if (((unsigned long)((unsigned char)((var17 & 255))) == 0)) {
                                goto L_11a0;
                            }
                            L_11de: ;
                            *(int *)((var6 + j * 4)) = 0;
                            var2 = ((unsigned long)((unsigned int)(j)) + 1);
                            j = var2;
                            if (((long)((int)(var2)) <= (long)((int)(var5)))) {
                                goto L_11d5;
                            }
                            goto L_11eb;
                            L_1230: ;
                            var31 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(*(int *)((&local_178[0] + ((long)((int)((var18 + j))) * 4))))) + 1)));
                            goto L_11ca;
                        }
                        L_11eb: ;
                        var40 = (i + 1);
                        i = (unsigned long)((unsigned int)(var40));
                        var6 = (var6 + 36);
                        var9 = (unsigned long)((unsigned int)((var9 + 9)));
                        var7 = (var7 + 1);
                    } while (((long)((int)(var40)) <= (long)((int)(var4))));
                    ret = (unsigned long)((unsigned int)(*(int *)((&local_178[0] + ((long)((int)(((unsigned long)((unsigned int)((var4 + (var4 * 8)))) + var5))) * 4)))));
                }
            }
        }
    }
    if ((local_30 != 0x28)) {
        __stack_chk_fail();
    }
    // x86-64 epilogue: tear down frame
    return ret;
}
lcs_recover pass 206 lines 
// glaurung: lcs_recover @ 0x1250
int32_t lcs_recover(const uint8_t * arg0, int32_t arg1, const uint8_t * arg2, int32_t arg3, uint8_t * arg4) {
    extern __attribute__((noreturn)) void __stack_chk_fail(void);
    int i;
    int j;
    int produced;
    int head;
    unsigned char swap;
    unsigned char local_188[324];
    long local_40;
    long t198;
    long var12;
    long var15;
    long var16;
    long var18;
    long var19;
    long var29;
    long var3;
    long var30;
    long var32;
    int var36;
    long var38;
    long var4;
    long var40;
    long var41;
    long var42;
    long var43;
    long var44;
    long var47;
    long var5;
    long var50;
    int var51;
    long var53;
    long var55;
    long var56;
    int var59;
    long var6;
    int var62;
    long var65;
    int var67;
    long var68;
    long var69;
    long var7;
    long var73;
    int var75;
    long var9;
    local_40 = (long)(0x28);
    if ((arg0 == 0)) {
        goto L_1455;
    }
    var3 = (long)arg2;
    if ((arg2 == 0)) {
        goto L_1455;
    }
    var4 = (long)arg4;
    if ((arg4 == 0)) {
        goto L_1455;
    }
    var5 = (unsigned long)((unsigned int)(arg1));
    if (((unsigned long)(8) < (unsigned long)((unsigned long)((unsigned int)(arg1))))) {
        goto L_1455;
    }
    if (((unsigned long)(8) < (unsigned long)((unsigned long)((unsigned int)(arg3))))) {
        goto L_1455;
    }
    var6 = (long)arg0;
    var7 = (long)(&local_188[0]);
    var9 = 0;
    var12 = (long)((arg0 - 1));
    i = 0;
    L_12d0: ;
    var15 = (unsigned long)((unsigned int)((var9 - 9)));
    var16 = (unsigned long)((unsigned int)((var9 - 1)));
    var18 = ((unsigned long)((unsigned int)(i)) == 0);
    var19 = (unsigned long)((unsigned int)((var9 - 10)));
    j = 0;
    goto L_1327;
    L_12f0: ;
    if (((unsigned char)(*(char *)((var12))) == (unsigned char)(((unsigned int)((unsigned char)(*(char *)((var3 + j - 0x1)))) & 255)))) {
        goto L_1430;
    }
    var29 = (unsigned long)((unsigned int)(*(int *)((&local_188[0] + ((long)((int)((var16 + j))) * 4)))));
    var30 = (unsigned long)((unsigned int)(*(int *)((&local_188[0] + ((long)((int)((var15 + j))) * 4)))));
    var32 = (((long)((int)(var29)) < (long)((int)(var30))) ? var30 : var29);
    L_131c: ;
    *(int *)((var7 + j * 4)) = var32;
    var6 = ((unsigned long)((unsigned int)(j)) + 1);
    j = var6;
    if (((long)(arg3) < (long)((int)(var6)))) {
        goto L_133d;
    }
    L_1327: ;
    if (((unsigned long)((unsigned int)(j)) != 0)) {
        if (((unsigned long)((unsigned char)((var18 & 255))) == 0)) {
            goto L_12f0;
        }
    }
    *(int *)((var7 + j * 4)) = 0;
    var6 = ((unsigned long)((unsigned int)(j)) + 1);
    j = var6;
    if (((long)((int)(var6)) <= (long)(arg3))) {
        goto L_1327;
    }
    L_133d: ;
    var36 = (i + 1);
    i = (unsigned long)((unsigned int)(var36));
    var7 = (var7 + 36);
    var9 = (unsigned long)((unsigned int)((var9 + 9)));
    var12 = (var12 + 1);
    if (((long)((int)(var36)) <= (long)((int)(var5)))) {
        goto L_12d0;
    }
    if ((((unsigned long)((unsigned int)(arg3)) == 0) | ((long)(arg3) < 0))) {
        goto L_1450;
    }
    var38 = (long)arg0;
    var9 = 0;
    var40 = var5;
    var41 = 0;
    var42 = (unsigned long)((unsigned int)(arg3));
    if (((((unsigned long)((unsigned int)(var5)) == 0) | ((long)((int)(var5)) < 0)) == 0)) {
        goto L_13a2;
    }
    goto L_1450;
    L_1370: ;
    var44 = (unsigned long)((unsigned int)((var43 + (var43 * 8))));
    var50 = (unsigned long)((unsigned int)(*(int *)((&local_188[0] + ((long)((int)(((var47 + var44) + 9))) * 4)))));
    t198 = *(int *)((&local_188[0] + ((long)((int)((var44 + var42))) * 4)));
    var51 = (((long)((int)(var50)) <= (long)((int)(t198))) ? var43 : var40);
    var53 = (unsigned long)((unsigned int)(var51));
    produced = var41;
    var55 = (((long)((int)(t198)) < (long)((int)(var50))) ? var47 : var42);
    var56 = var41;
    if ((((unsigned long)((unsigned int)(var51)) == 0) | ((long)((int)(var51)) < 0))) {
        goto L_13d1;
    }
    L_1394: ;
    var56 = (unsigned long)((unsigned int)(produced));
    if ((((unsigned long)((unsigned int)(var55)) == 0) | ((long)((int)(var55)) < 0))) {
        goto L_13d1;
    }
    var40 = var53;
    var41 = (unsigned long)((unsigned int)(produced));
    var42 = var55;
    if (((unsigned long)((unsigned int)(produced)) == 8)) {
        goto L_1444;
    }
    L_13a2: ;
    var47 = (unsigned long)((unsigned int)((var42 - 1)));
    var59 = (unsigned int)((unsigned char)(*(char *)(((var38 + (long)((int)(var40))) - 1))));
    var43 = (unsigned long)((unsigned int)((var40 - 1)));
    if (((unsigned char)((var59 & 255)) != (unsigned char)(*(char *)(((var3 + (long)((int)(var42))) - 1))))) {
        goto L_1370;
    }
    var62 = (var41 + 1);
    produced = (unsigned long)((unsigned int)(var62));
    *(signed char *)((var4 + (long)((int)(var41)))) = var59;
    var53 = (unsigned long)((unsigned int)(var43));
    var55 = (unsigned long)((unsigned int)(var47));
    var56 = (unsigned long)((unsigned int)(var62));
    if (((((unsigned long)((unsigned int)(var43)) == 0) | ((long)((int)(var43)) < 0)) == 0)) {
        goto L_1394;
    }
    L_13d1: ;
    var65 = (unsigned long)((unsigned int)((var56 - 1)));
    var67 = ((int)(var56) >> 1);
    var68 = (unsigned long)((unsigned int)(var67));
    var69 = var56;
    if (((unsigned long)((unsigned int)(var67)) == 0)) {
        goto L_1403;
    }
    L_13dc: ;
    var73 = ((long)((int)(var65)) + var4);
    head = 0;
    do {
        var75 = (unsigned int)((unsigned char)(*(char *)((var73))));
        swap = (unsigned int)((unsigned char)(*(char *)((var4 + head))));
        var73 = (var73 - 1);
        *(signed char *)((var4 + head)) = var75;
        head = (head + 1);
        *(signed char *)((var73 + 0x1)) = swap;
        var69 = var56;
    } while (((((unsigned int)(var68) == (unsigned int)(head)) | ((long)((int)(var68)) < (long)(head))) == 0));
    L_1403: ;
    if ((local_40 != 0x28)) {
        goto L_145d;
    }
    // x86-64 epilogue: tear down frame
    return (unsigned int)(var69);
    L_1430: ;
    var32 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(*(int *)((&local_188[0] + ((long)((int)((var19 + j))) * 4))))) + 1)));
    goto L_131c;
    L_1444: ;
    var65 = 7;
    var68 = 4;
    var56 = (unsigned long)((unsigned int)(produced));
    goto L_13dc;
    L_1450: ;
    var69 = 0;
    goto L_1403;
    L_1455: ;
    var69 = 0xffffffff;
    goto L_1403;
    L_145d: ;
    __stack_chk_fail();
}

← 213 fixtures