glaurung

Fixture 33

knapsack

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

One lane has a function that returns a different result after decompilation: clang-O2 (1/2).

0/1 knapsack by rolling one-dimensional capacity array, iterated in reverse so each item is used at most once. The reverse inner loop with a data-dependent lower bound is a common structuring failure.

tests/decompiler_fixtures/src/33_knapsack.c source 
#include <stdint.h>

/* 0/1 knapsack by rolling one-dimensional capacity array, iterated in reverse
 * so each item is used at most once.  The reverse inner loop with a
 * data-dependent lower bound is a common structuring failure. */

#define KNAP_ITEMS 8
#define KNAP_CAPACITY 16

__attribute__((noinline)) int32_t
knapsack_best_value(const int32_t *weights, const int32_t *values,
                    int32_t item_count, int32_t capacity) {
    int32_t best[KNAP_CAPACITY + 1];
    int32_t item;
    int32_t room;
    if (weights == 0 || values == 0 || item_count < 0 ||
        item_count > KNAP_ITEMS || capacity < 0 || capacity > KNAP_CAPACITY) {
        return -1;
    }
    for (room = 0; room <= capacity; ++room) {
        best[room] = 0;
    }
    for (item = 0; item < item_count; ++item) {
        int32_t weight = weights[item];
        int32_t value = values[item];
        if (weight <= 0 || weight > capacity || value < 0) {
            continue;
        }
        for (room = capacity; room >= weight; --room) {
            int32_t candidate = best[room - weight] + value;
            if (candidate > best[room]) {
                best[room] = candidate;
            }
        }
    }
    return best[capacity];
}

__attribute__((noinline)) int32_t
unbounded_knapsack(const int32_t *weights, const int32_t *values,
                   int32_t item_count, int32_t capacity) {
    int32_t best[KNAP_CAPACITY + 1];
    int32_t item;
    int32_t room;
    if (weights == 0 || values == 0 || item_count < 0 ||
        item_count > KNAP_ITEMS || capacity < 0 || capacity > KNAP_CAPACITY) {
        return -1;
    }
    for (room = 0; room <= capacity; ++room) {
        best[room] = 0;
    }
    for (room = 1; room <= capacity; ++room) {
        for (item = 0; item < item_count; ++item) {
            int32_t weight = weights[item];
            int32_t value = values[item];
            if (weight > 0 && weight <= room && value >= 0) {
                int32_t candidate = best[room - weight] + value;
                if (candidate > best[room]) {
                    best[room] = candidate;
                }
            }
        }
    }
    return best[capacity];
}

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

1/2
knapsack_best_value fail 222 lines 
// glaurung: knapsack_best_value @ 0x1110
__attribute__((no_stack_protector)) int32_t knapsack_best_value(const int32_t * arg0, const int32_t * arg1, int32_t arg2, int32_t arg3) {
    extern void * memset(void *, int, __SIZE_TYPE__);
    int weight;
    int value;
    int item;
    int room;
    unsigned char local_7c[124];
    unsigned char local_a8[44];
    long ret;
    long rsp;
    long t60;
    long var0;
    long var1;
    int var100;
    int var107;
    int var108;
    int var109;
    int var110;
    int var123;
    int var124;
    int var125;
    int var126;
    int var133;
    int var134;
    int var135;
    int var136;
    long var15;
    long var18;
    int * var2;
    long var24;
    long var25;
    long var26;
    long var3;
    long var30;
    int var32;
    long var34;
    long var41;
    long var44;
    long var45;
    long var48;
    void * var5;
    long var50;
    long var54;
    long var62;
    int var68;
    int var69;
    long var7;
    int var70;
    int var71;
    long var73;
    long var74;
    long var76;
    int var77;
    int var78;
    int var79;
    long var8;
    int var80;
    int var85;
    int var86;
    int var87;
    int var88;
    int var89;
    int var90;
    int var91;
    int var92;
    int var97;
    int var98;
    int var99;
    // x86-64 prologue: save callee registers, frame 48 bytes
    rsp = (rsp - 120);
    ret = 0xffffffff;
    if (((unsigned long)(16) < (unsigned long)((unsigned long)((unsigned int)(arg3))))) {
        // x86-64 epilogue: restore callee registers
        return ret;
    }
    var0 = (unsigned long)((unsigned int)(arg2));
    if (((unsigned long)(8) < (unsigned long)((unsigned long)((unsigned int)(arg2))))) {
        // x86-64 epilogue: restore callee registers
        return ret;
    }
    var1 = (long)arg0;
    if ((arg0 == 0)) {
        // x86-64 epilogue: restore callee registers
        return ret;
    }
    var2 = (int *)arg1;
    if ((arg1 == 0)) {
        // x86-64 epilogue: restore callee registers
        return ret;
    }
    var3 = (unsigned long)((unsigned int)(arg3));
    *(long *)((&local_a8[0] + 16)) = (long)((long)var2);
    var5 = memset((void *)((&local_7c[0] + 4)), 0, (__SIZE_TYPE__)((((unsigned long)((unsigned int)(arg3)) * 4) + 4)));
    var7 = *(long *)((&local_a8[0] + 16));
    if (((unsigned long)((unsigned int)(var0)) != 0)) {
        var8 = (unsigned long)((unsigned int)(var0));
        *(long *)((&local_a8[0] + 32)) = (long)((long)(((&local_a8[0] + (var3 * 4)) + 48)));
        *(long *)((&local_a8[0] + 40)) = (var3 + 1);
        *(long *)((&local_a8[0] + 24)) = (long)((long)(((&local_a8[0] + (var3 * 4)) + 52)));
        var15 = (long)(((&local_a8[0] + (var3 * 4)) + 36));
        var18 = 0;
        do {
            weight = (unsigned long)((unsigned int)(*(int *)((var1 + var18 * 4))));
            if (((((unsigned long)((unsigned int)(weight)) == 0) | ((long)(weight) < 0)) == 0)) {
                if (((((unsigned int)(weight) == (unsigned int)(arg3)) | (weight < arg3)) != 0)) {
                    value = (unsigned long)((unsigned int)(*(int *)((var7 + var18 * 4))));
                    if ((0 <= (long)(value))) {
                        var24 = (*(long *)((&local_a8[0] + 40)) - ((weight < var3) ? (unsigned long)((unsigned int)(weight)) : var3));
                        var25 = var3;
                        if (((unsigned long)(var24) < (unsigned long)(8))) {
                            L_1360: ;
                            var26 = (var25 + 1);
                            var30 = (((-((unsigned long)((unsigned int)(weight)) * 4)) + rsp) + 48);
                            do {
                                var32 = ((unsigned int)(*(int *)((var30 + var26 * 4 - 0x4))) + value);
                                var34 = (unsigned long)((unsigned int)(*(int *)((&local_7c[0] + (var26 * 4)))));
                                *(int *)((&local_7c[0] + (var26 * 4))) = ((((unsigned int)(var32) == (unsigned int)(var34)) | ((long)((int)(var32)) < (long)((int)(var34)))) ? var34 : (unsigned long)((unsigned int)(var32)));
                                var26 = (var26 - 1);
                            } while ((weight < var26));
                        } else {
                            t60 = (var3 - ((weight < var3) ? (unsigned long)((unsigned int)(weight)) : var3));
                            var41 = (t60 * 4);
                            var44 = (((unsigned long)(((unsigned __int128)(unsigned long)(t60) * (unsigned __int128)(unsigned long)(4)) >> 64)) != 0);
                            var45 = *(long *)((&local_a8[0] + 32));
                            var25 = var3;
                            if (((unsigned long)(var45) < (unsigned long)((var45 - var41)))) {
                                goto L_1360;
                            } else {
                                var25 = var3;
                                if (((unsigned long)((unsigned char)((var44 & 255))) != 0)) {
                                    goto L_1360;
                                } else {
                                    var48 = ((unsigned long)((unsigned int)(weight)) * 4);
                                    var50 = (*(long *)((&local_a8[0] + 32)) - var48);
                                    var25 = var3;
                                    var7 = *(long *)((&local_a8[0] + 16));
                                    if (((unsigned long)(var50) < (unsigned long)((var50 - var41)))) {
                                        goto L_1360;
                                    } else {
                                        var25 = var3;
                                        if (((unsigned long)((unsigned char)((var44 & 255))) != 0)) {
                                            goto L_1360;
                                        } else {
                                            var54 = ((weight < var3) ? (unsigned long)((unsigned int)(weight)) : var3);
                                            if (((unsigned long)((*(long *)((&local_a8[0] + 24)) - var48)) <= (unsigned long)(((&local_a8[0] + (var54 * 4)) + 48)))) {
                                                L_12ad: ;
                                                var62 = (var24 & -8);
                                                var25 = (var3 - var62);
                                                var68 = value;
                                                var69 = value;
                                                var70 = value;
                                                var71 = value;
                                                var73 = (-var62);
                                                var74 = (var15 + ((-(unsigned long)((unsigned int)(weight))) * 4));
                                                var76 = 0;
                                                do {
                                                    var77 = *(int *)((var74 + var76 * 4 - 0x10));
                                                    var78 = *(int *)((var74 + var76 * 4 - 0xc));
                                                    var79 = *(int *)((var74 + var76 * 4 - 0x8));
                                                    var80 = *(int *)((var74 + var76 * 4 - 0x4));
                                                    var85 = *(int *)((var15 + var76 * 4 - 0x10));
                                                    var86 = *(int *)((var15 + var76 * 4 - 0xc));
                                                    var87 = *(int *)((var15 + var76 * 4 - 0x8));
                                                    var88 = *(int *)((var15 + var76 * 4 - 0x4));
                                                    var89 = *(int *)((var15 + var76 * 4));
                                                    var90 = *(int *)((var15 + var76 * 4 + 0x4));
                                                    var91 = *(int *)((var15 + var76 * 4 + 0x8));
                                                    var92 = *(int *)((var15 + var76 * 4 + 0xc));
                                                    var97 = (*(int *)((var74 + var76 * 4)) + var71);
                                                    var98 = (*(int *)((var74 + var76 * 4 + 0x4)) + var70);
                                                    var99 = (*(int *)((var74 + var76 * 4 + 0x8)) + var69);
                                                    var100 = (*(int *)((var74 + var76 * 4 + 0xc)) + var68);
                                                    var107 = (-(var89 < var97));
                                                    var108 = (-(var90 < var98));
                                                    var109 = (-(var91 < var99));
                                                    var110 = (-(var92 < var100));
                                                    *(int *)((var15 + var76 * 4)) = (((~var107) & var89) | (var97 & var107));
                                                    *(int *)((var15 + var76 * 4 + 0x4)) = (((~var108) & var90) | (var98 & var108));
                                                    *(int *)((var15 + var76 * 4 + 0x8)) = (((~var109) & var91) | (var99 & var109));
                                                    *(int *)((var15 + var76 * 4 + 0xc)) = (((~var110) & var92) | (var100 & var110));
                                                    var123 = (var77 + var71);
                                                    var124 = (var78 + var70);
                                                    var125 = (var79 + var69);
                                                    var126 = (var80 + var68);
                                                    var133 = (-(var85 < var123));
                                                    var134 = (-(var86 < var124));
                                                    var135 = (-(var87 < var125));
                                                    var136 = (-(var88 < var126));
                                                    *(int *)((var15 + var76 * 4 - 0x10)) = (((~var133) & var85) | (var123 & var133));
                                                    *(int *)((var15 + var76 * 4 - 0xc)) = (((~var134) & var86) | (var124 & var134));
                                                    *(int *)((var15 + var76 * 4 - 0x8)) = (((~var135) & var87) | (var125 & var135));
                                                    *(int *)((var15 + var76 * 4 - 0x4)) = (((~var136) & var88) | (var126 & var136));
                                                    var76 = (var76 - 8);
                                                } while ((var73 != var76));
                                                var7 = *(long *)((&local_a8[0] + 16));
                                                if ((var24 != var62)) {
                                                    goto L_1360;
                                                }
                                            } else {
                                                var25 = var3;
                                                if (((unsigned long)(((&local_a8[0] + ((var54 - weight) * 4)) + 48)) < (unsigned long)(*(long *)((&local_a8[0] + 24))))) {
                                                    goto L_1360;
                                                } else {
                                                    goto L_12ad;
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
            item = (var18 + 1);
            var18 = (unsigned long)((unsigned int)(item));
        } while ((item != var8));
    }
    // x86-64 epilogue: restore callee registers
    return (unsigned int)(*(int *)((&local_7c[0] + ((var3 * 4) + 4))));
}
unbounded_knapsack pass 74 lines 
// glaurung: unbounded_knapsack @ 0x13c0
__attribute__((no_stack_protector)) int32_t unbounded_knapsack(const int32_t * arg0, const int32_t * arg1, int32_t arg2, int32_t arg3) {
    extern void * memset(void *, int, __SIZE_TYPE__);
    int room;
    int weight;
    int value;
    int item;
    int candidate;
    unsigned char local_78[120];
    long ret;
    long var0;
    long var1;
    long var16;
    long var18;
    long var2;
    long var25;
    long var28;
    long var3;
    void * var6;
    long var8;
    long var9;
    // x86-64 prologue: save callee registers, frame 40 bytes
    ret = 0xffffffff;
    if (((unsigned long)(16) < (unsigned long)((unsigned long)((unsigned int)(arg3))))) {
        // x86-64 epilogue: restore callee registers
        return ret;
    }
    var0 = (unsigned long)((unsigned int)(arg2));
    if (((unsigned long)(8) < (unsigned long)((unsigned long)((unsigned int)(arg2))))) {
        // x86-64 epilogue: restore callee registers
        return ret;
    }
    var1 = (long)arg0;
    if ((arg0 == 0)) {
        // x86-64 epilogue: restore callee registers
        return ret;
    }
    var2 = (long)arg1;
    if ((arg1 == 0)) {
        // x86-64 epilogue: restore callee registers
        return ret;
    }
    var3 = (unsigned long)((unsigned int)(arg3));
    var6 = memset((void *)(&local_78[0]), 0, (__SIZE_TYPE__)((((unsigned long)((unsigned int)(arg3)) * 4) + 4)));
    if (((unsigned long)((unsigned int)(var3)) != 0)) {
        var8 = (unsigned long)((unsigned int)((var3 + 1)));
        var9 = (unsigned long)((unsigned int)(var0));
        room = 1;
        do {
            if (((unsigned long)((unsigned int)(var0)) != 0)) {
                var16 = 0;
                do {
                    weight = (unsigned long)((unsigned int)(*(int *)((var1 + var16 * 4))));
                    if (((((unsigned long)((unsigned int)(weight)) == 0) | ((long)(weight) < 0)) == 0)) {
                        if (((unsigned long)(weight) <= (unsigned long)(room))) {
                            var18 = (unsigned long)((unsigned int)(*(int *)((var2 + var16 * 4))));
                            if ((0 <= (long)((int)(var18)))) {
                                value = (var18 + *(int *)((&local_78[0] + ((long)((int)(((unsigned long)((unsigned int)(room)) - weight))) * 4))));
                                var25 = (unsigned long)((unsigned int)(*(int *)((&local_78[0] + (room * 4)))));
                                *(int *)((&local_78[0] + (room * 4))) = ((((unsigned int)(value) == (unsigned int)(var25)) | ((long)(value) < (long)((int)(var25)))) ? var25 : (unsigned long)((unsigned int)(value)));
                            }
                        }
                    }
                    item = (var16 + 1);
                    var16 = (unsigned long)((unsigned int)(item));
                } while ((var9 != item));
            }
            var28 = ((unsigned long)((unsigned int)(room)) + 1);
            room = var28;
        } while ((var28 != var8));
    }
    // x86-64 epilogue: restore callee registers
    return (unsigned int)(*(int *)((&local_78[0] + ((long)((int)(var3)) * 4))));
}

clang -O0

2/2
knapsack_best_value pass 75 lines 
// glaurung: knapsack_best_value @ 0x1100
__attribute__((no_stack_protector)) int32_t knapsack_best_value(const int32_t * arg0, const int32_t * arg1, int32_t arg2, int32_t arg3) {
    int room;
    int item;
    int weight;
    int value;
    int candidate;
    int local_4;
    unsigned char local_70[68];
    long t168;
    // x86-64 prologue: save rbp, frame 16 bytes
    if ((arg0 == 0)) {
        local_4 = -1;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    if ((arg1 == 0)) {
        local_4 = -1;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    if (((long)(arg2) < 0)) {
        local_4 = -1;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    if (((((unsigned long)((unsigned int)(arg2)) == 8) | ((long)(arg2) < 8)) == 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)(arg3)) == 16) | ((long)(arg3) < 16)) == 0)) {
        local_4 = -1;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    for (room = 0; ((((unsigned int)(room) == (unsigned int)(arg3)) | (room < arg3)) != 0); room++) {
        *(int *)((&local_70[0] + ((long)(room) * 4))) = 0;
    }
    item = 0;
    while ((item < arg2)) {
        weight = arg0[(long)(item)];
        value = arg1[(long)(item)];
        if ((((unsigned long)((unsigned int)(weight)) == 0) | ((long)(weight) < 0))) {
            L_11dc: ;
        } else {
            if (((((unsigned int)(weight) == (unsigned int)(arg3)) | (weight < arg3)) == 0)) {
                goto L_11dc;
            } else {
                if ((0 <= (long)(value))) {
                    room = arg3;
                    while ((weight <= room)) {
                        candidate = ((unsigned int)(*(int *)((&local_70[0] + ((long)((int)(((unsigned long)((unsigned int)(room)) - weight))) * 4)))) + value);
                        t168 = *(int *)((&local_70[0] + ((long)(room) * 4)));
                        if (((((unsigned int)(candidate) == (unsigned int)(t168)) | ((long)(candidate) < (long)((int)(t168)))) == 0)) {
                            *(int *)((&local_70[0] + ((long)(room) * 4))) = candidate;
                        }
                        room = ((unsigned int)(room) - 1);
                    }
                } else {
                    goto L_11dc;
                }
            }
        }
        item = ((unsigned int)(item) + 1);
    }
    local_4 = *(int *)((&local_70[0] + ((long)(arg3) * 4)));
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
}
unbounded_knapsack pass 67 lines 
// glaurung: unbounded_knapsack @ 0x1270
__attribute__((no_stack_protector)) int32_t unbounded_knapsack(const int32_t * arg0, const int32_t * arg1, int32_t arg2, int32_t arg3) {
    int room;
    int item;
    int weight;
    int value;
    int candidate;
    int local_4;
    unsigned char local_70[68];
    long t167;
    // x86-64 prologue: save rbp, frame 16 bytes
    if ((arg0 == 0)) {
        local_4 = -1;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    if ((arg1 == 0)) {
        local_4 = -1;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    if (((long)(arg2) < 0)) {
        local_4 = -1;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    if (((((unsigned long)((unsigned int)(arg2)) == 8) | ((long)(arg2) < 8)) == 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)(arg3)) == 16) | ((long)(arg3) < 16)) == 0)) {
        local_4 = -1;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    for (room = 0; ((((unsigned int)(room) == (unsigned int)(arg3)) | (room < arg3)) != 0); room++) {
        *(int *)((&local_70[0] + ((long)(room) * 4))) = 0;
    }
    room = 1;
    while (((((unsigned int)(room) == (unsigned int)(arg3)) | (room < arg3)) != 0)) {
        for (item = 0; (item < arg2); item++) {
            weight = arg0[(long)(item)];
            value = arg1[(long)(item)];
            if (((((unsigned long)((unsigned int)(weight)) == 0) | ((long)(weight) < 0)) == 0)) {
                if (((((unsigned int)(weight) == (unsigned int)(room)) | (weight < room)) != 0)) {
                    if ((0 <= (long)(value))) {
                        candidate = ((unsigned int)(*(int *)((&local_70[0] + ((long)((int)(((unsigned long)((unsigned int)(room)) - weight))) * 4)))) + value);
                        t167 = *(int *)((&local_70[0] + ((long)(room) * 4)));
                        if (((((unsigned int)(candidate) == (unsigned int)(t167)) | ((long)(candidate) < (long)((int)(t167)))) == 0)) {
                            *(int *)((&local_70[0] + ((long)(room) * 4))) = candidate;
                        }
                    }
                }
            }
        }
        room = ((unsigned int)(room) + 1);
    }
    local_4 = *(int *)((&local_70[0] + ((long)(arg3) * 4)));
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
}

gcc -O0

2/2
knapsack_best_value pass 46 lines 
// glaurung: knapsack_best_value @ 0x1119
int32_t knapsack_best_value(const int32_t * arg0, const int32_t * arg1, int32_t arg2, int32_t arg3) {
    extern __attribute__((noreturn)) void __stack_chk_fail(void);
    int room;
    int item;
    int weight;
    int value;
    int candidate;
    unsigned char local_50[68];
    long local_8;
    long ret;
    long var32;
    // x86-64 prologue: save rbp, frame 144 bytes
    local_8 = (long)(0x28);
    if (((((((arg0 == 0) || (arg1 == 0)) || ((long)(arg2) < 0)) || ((((unsigned long)((unsigned int)(arg2)) == 8) | ((long)(arg2) < 8)) == 0)) || ((long)(arg3) < 0)) || (((unsigned long)((unsigned int)(arg3)) != 16) && (16 <= (long)(arg3))))) {
        ret = 0xffffffff;
    } else {
        for (room = 0; ((((unsigned int)(room) == (unsigned int)(arg3)) | (room < arg3)) != 0); room++) {
            *(int *)((&local_50[0] + ((long)(room) * 4))) = 0;
        }
        item = 0;
        while ((item < arg2)) {
            weight = arg0[(long)(item)];
            value = arg1[(long)(item)];
            if ((((((unsigned long)((unsigned int)(weight)) == 0) | ((long)(weight) < 0)) || ((((unsigned int)(weight) == (unsigned int)(arg3)) | (weight < arg3)) == 0)) || ((long)(value) < 0))) {
            } else {
                room = arg3;
                while ((weight <= room)) {
                    candidate = ((unsigned int)(value) + (unsigned int)(*(int *)((&local_50[0] + ((long)((int)(((unsigned long)((unsigned int)(room)) - weight))) * 4)))));
                    var32 = (unsigned long)((unsigned int)(*(int *)((&local_50[0] + ((long)(room) * 4)))));
                    if (((((unsigned int)(candidate) == (unsigned int)(var32)) | ((long)(candidate) < (long)((int)(var32)))) == 0)) {
                        *(int *)((&local_50[0] + ((long)(room) * 4))) = candidate;
                    }
                    room = (room - 1);
                }
            }
            item = (item + 1);
        }
        ret = (unsigned long)((unsigned int)(*(int *)((&local_50[0] + ((long)(arg3) * 4)))));
    }
    if ((local_8 != 0x28)) {
        __stack_chk_fail();
    }
    // x86-64 epilogue: restore rbp
    return ret;
}
unbounded_knapsack pass 47 lines 
// glaurung: unbounded_knapsack @ 0x127e
int32_t unbounded_knapsack(const int32_t * arg0, const int32_t * arg1, int32_t arg2, int32_t arg3) {
    extern __attribute__((noreturn)) void __stack_chk_fail(void);
    int room;
    int item;
    int weight;
    int value;
    int candidate;
    unsigned char local_50[68];
    long local_8;
    long ret;
    long var31;
    // x86-64 prologue: save rbp, frame 144 bytes
    local_8 = (long)(0x28);
    if (((((((arg0 == 0) || (arg1 == 0)) || ((long)(arg2) < 0)) || ((((unsigned long)((unsigned int)(arg2)) == 8) | ((long)(arg2) < 8)) == 0)) || ((long)(arg3) < 0)) || (((unsigned long)((unsigned int)(arg3)) != 16) && (16 <= (long)(arg3))))) {
        ret = 0xffffffff;
    } else {
        for (room = 0; ((((unsigned int)(room) == (unsigned int)(arg3)) | (room < arg3)) != 0); room++) {
            *(int *)((&local_50[0] + ((long)(room) * 4))) = 0;
        }
        room = 1;
        while (((((unsigned int)(room) == (unsigned int)(arg3)) | (room < arg3)) != 0)) {
            for (item = 0; (item < arg2); item++) {
                weight = arg0[(long)(item)];
                value = arg1[(long)(item)];
                if (((((unsigned long)((unsigned int)(weight)) == 0) | ((long)(weight) < 0)) == 0)) {
                    if (((((unsigned int)(weight) == (unsigned int)(room)) | (weight < room)) != 0)) {
                        if ((0 <= (long)(value))) {
                            candidate = ((unsigned int)(value) + (unsigned int)(*(int *)((&local_50[0] + ((long)((int)(((unsigned long)((unsigned int)(room)) - weight))) * 4)))));
                            var31 = (unsigned long)((unsigned int)(*(int *)((&local_50[0] + ((long)(room) * 4)))));
                            if (((((unsigned int)(candidate) == (unsigned int)(var31)) | ((long)(candidate) < (long)((int)(var31)))) == 0)) {
                                *(int *)((&local_50[0] + ((long)(room) * 4))) = candidate;
                            }
                        }
                    }
                }
            }
            room = (room + 1);
        }
        ret = (unsigned long)((unsigned int)(*(int *)((&local_50[0] + ((long)(arg3) * 4)))));
    }
    if ((local_8 != 0x28)) {
        __stack_chk_fail();
    }
    // x86-64 epilogue: restore rbp
    return ret;
}

gcc -O2

2/2
knapsack_best_value pass 105 lines 
// glaurung: knapsack_best_value @ 0x1120
int32_t knapsack_best_value(const int32_t * arg0, const int32_t * arg1, int32_t arg2, int32_t arg3) {
    extern __attribute__((noreturn)) void __stack_chk_fail(void);
    int room;
    int item;
    int weight;
    int value;
    long df_1;
    long local_30;
    unsigned char local_78[68];
    long ret;
    long t1;
    long t139;
    long t2;
    long var10;
    long var11;
    long var15;
    long var19;
    long var2;
    long var20;
    long var23;
    long var3;
    long var35;
    long var39;
    long var4;
    long var40;
    long var41;
    long var43;
    int var44;
    long var47;
    long var8;
    df_1 = 0;
    local_30 = (long)(0x28);
    var2 = 0;
    if ((arg0 == 0)) {
        L_1243: ;
        ret = 0xffffffff;
    } else {
        var3 = (long)arg1;
        if ((arg1 == 0)) {
            goto L_1243;
        } else {
            var4 = (unsigned long)((unsigned int)(arg2));
            if (((unsigned long)(8) < (unsigned long)((unsigned long)((unsigned int)(arg2))))) {
                goto L_1243;
            } else {
                room = (unsigned long)((unsigned int)(arg3));
                if (((unsigned long)(16) < (unsigned long)((unsigned long)((unsigned int)(arg3))))) {
                    goto L_1243;
                } else {
                    var8 = (long)arg0;
                    var10 = (long)(&local_78[0]);
                    var11 = ((long)((int)((arg3 + 1))) << 2);
                    if (((unsigned long)(8) <= (unsigned long)((unsigned long)((unsigned int)(var11))))) {
                        var15 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var11)) >> 3)));
                        t139 = var10;
                        t1 = var15;
                        while ((t1 != 0)) {
                            *(long *)(t139) = var2;
                            t139 = (t139 + ((df_1 != 0) ? -8 : 8));
                            t1 = (t1 - 1);
                        }
                        t2 = (var15 * 8);
                        var10 = (var10 + (df_1 ? (-t2) : t2));
                    }
                    if (((unsigned long)((unsigned int)((var11 & 4))) != 0)) {
                        *(int *)((var10)) = 0;
                    }
                    var19 = (long)(room);
                    if (((unsigned long)((unsigned int)(var4)) != 0)) {
                        var20 = (long)((&local_78[0] + (var19 * 4)));
                        item = 0;
                        var23 = (var20 - 4);
                        do {
                            weight = (unsigned long)((unsigned int)(*(int *)((var8 + item * 4))));
                            value = (unsigned long)((unsigned int)(*(int *)((var3 + item * 4))));
                            if (((unsigned long)((unsigned char)((((((unsigned long)((unsigned int)(weight)) == 0) | ((long)(weight) < 0)) & 255) | (room < weight)))) == 0)) {
                                if ((0 <= (long)(value))) {
                                    var35 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(room)) - weight)));
                                    var39 = ((long)((int)(var35)) - var19);
                                    var40 = (var23 - ((unsigned long)((unsigned int)(var35)) << 2));
                                    var41 = var20;
                                    do {
                                        var43 = (unsigned long)((unsigned int)(*(int *)((var41))));
                                        var44 = ((unsigned int)(*(int *)((var41 + var39 * 4))) + value);
                                        var41 = (var41 - 4);
                                        *(int *)((var41 + 0x4)) = (((long)((int)(var44)) < (long)((int)(var43))) ? var43 : (unsigned long)((unsigned int)(var44)));
                                    } while ((var41 != var40));
                                }
                            }
                            var47 = ((unsigned long)((unsigned int)(item)) + 1);
                            item = var47;
                        } while (((((unsigned int)(var4) == (unsigned int)(var47)) | ((long)((int)(var4)) < (long)((int)(var47)))) == 0));
                    }
                    ret = (unsigned long)((unsigned int)(*(int *)((&local_78[0] + (var19 * 4)))));
                }
            }
        }
    }
    if ((local_30 != 0x28)) {
        __stack_chk_fail();
    }
    // x86-64 epilogue: tear down frame
    return ret;
}
unbounded_knapsack pass 127 lines 
// glaurung: unbounded_knapsack @ 0x1250
int32_t unbounded_knapsack(const int32_t * arg0, const int32_t * arg1, int32_t arg2, int32_t arg3) {
    extern __attribute__((noreturn)) void __stack_chk_fail(void);
    int room;
    int item;
    int weight;
    int value;
    int candidate;
    long df_1;
    long local_20;
    unsigned char local_68[68];
    long ret;
    long t1;
    long t139;
    long t2;
    long var10;
    long var14;
    long var18;
    long var2;
    long var24;
    long var3;
    int var35;
    long var4;
    long var5;
    long var6;
    long var7;
    long var8;
    df_1 = 0;
    local_20 = (long)(0x28);
    var2 = 0;
    if ((arg0 == 0)) {
        goto L_135c;
    }
    var3 = (long)arg1;
    if ((arg1 == 0)) {
        goto L_135c;
    }
    var4 = (unsigned long)((unsigned int)(arg2));
    if (((unsigned long)(8) < (unsigned long)((unsigned long)((unsigned int)(arg2))))) {
        goto L_135c;
    }
    var5 = (long)(arg3);
    if (((unsigned long)(16) < (unsigned long)((unsigned long)((unsigned int)(arg3))))) {
        goto L_135c;
    }
    var6 = (unsigned long)((unsigned int)((var5 + 1)));
    var7 = (long)arg0;
    var8 = (long)(&local_68[0]);
    var10 = ((long)((int)(var6)) << 2);
    if (((unsigned long)(8) <= (unsigned long)((unsigned long)((unsigned int)(var10))))) {
        var14 = (unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var10)) >> 3)));
        t139 = var8;
        t1 = var14;
        while ((t1 != 0)) {
            *(long *)(t139) = var2;
            t139 = (t139 + ((df_1 != 0) ? -8 : 8));
            t1 = (t1 - 1);
        }
        t2 = (var14 * 8);
        var8 = (var8 + (df_1 ? (-t2) : t2));
    }
    if (((unsigned long)((unsigned int)((var10 & 4))) != 0)) {
        goto L_1351;
    }
    L_12bf: ;
    if (((unsigned long)((unsigned int)(var5)) == 0)) {
        goto L_1335;
    }
    var18 = (long)((&local_68[0] + 4));
    room = 1;
    L_12d0: ;
    var2 = 0;
    item = 0;
    if (((unsigned long)((unsigned int)(var4)) != 0)) {
        goto L_12e9;
    }
    goto L_1328;
    L_12e0: ;
    var2 = ((unsigned long)((unsigned int)(item)) + 1);
    item = var2;
    if ((((unsigned int)(var4) == (unsigned int)(var2)) | ((long)((int)(var4)) < (long)((int)(var2))))) {
        goto L_1328;
    }
    L_12e9: ;
    weight = (unsigned long)((unsigned int)(*(int *)((var7 + item * 4))));
    var24 = (unsigned long)((unsigned int)(*(int *)((var3 + item * 4))));
    if (((unsigned long)((unsigned char)((((((unsigned long)((unsigned int)(weight)) == 0) | ((long)(weight) < 0)) == 0) & ((((unsigned int)(weight) == (unsigned int)(room)) | (weight < room)) & 255)))) == 0)) {
        goto L_12e0;
    }
    if (((long)((int)(var24)) < 0)) {
        goto L_12e0;
    }
    value = (var24 + *(int *)((&local_68[0] + ((long)((int)(((unsigned long)((unsigned int)(room)) - weight))) * 4))));
    candidate = (unsigned long)((unsigned int)(value));
    if (((long)(value) <= (long)((int)(*(int *)((var18)))))) {
        goto L_12e0;
    }
    item = (item + 1);
    *(int *)((var18)) = candidate;
    if (((((unsigned int)(var4) == (unsigned int)(item)) | ((long)((int)(var4)) < (long)(item))) == 0)) {
        goto L_12e9;
    }
    var2 = (unsigned long)((unsigned int)(item));
    L_1328: ;
    var35 = (room + 1);
    room = (unsigned long)((unsigned int)(var35));
    var18 = (var18 + 4);
    if (((unsigned int)(var35) != (unsigned int)(var6))) {
        goto L_12d0;
    }
    L_1335: ;
    ret = (unsigned long)((unsigned int)(*(int *)((&local_68[0] + (var5 * 4)))));
    L_1338: ;
    if ((local_20 != 0x28)) {
        goto L_1363;
    }
    // x86-64 epilogue: tear down frame
    return ret;
    L_1351: ;
    *(int *)((var8)) = 0;
    goto L_12bf;
    L_135c: ;
    ret = 0xffffffff;
    goto L_1338;
    L_1363: ;
    __stack_chk_fail();
}

← 213 fixtures