glaurung

Fixture 42

rpn evaluator

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

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

Reverse-Polish evaluation over an explicit operand stack. Operators arrive as bytes and dispatch through a switch; division guards zero and the INT32_MIN / -1 overflow case, which is a real correctness trap.

tests/decompiler_fixtures/src/42_rpn_evaluator.c source 
#include <stdint.h>

/* Reverse-Polish evaluation over an explicit operand stack.  Operators arrive
 * as bytes and dispatch through a switch; division guards zero and the
 * INT32_MIN / -1 overflow case, which is a real correctness trap. */

#define RPN_MAX 16

__attribute__((noinline)) int32_t
rpn_evaluate(const uint8_t *tokens, const int32_t *operands, int32_t length,
             int32_t *result) {
    int32_t stack[RPN_MAX];
    int32_t depth = 0;
    int32_t index;
    if (tokens == 0 || operands == 0 || result == 0 || length < 0 ||
        length > RPN_MAX) {
        return -1;
    }
    for (index = 0; index < length; ++index) {
        uint8_t token = tokens[index];
        if (token == (uint8_t)'#') {
            if (depth >= RPN_MAX) {
                return -2;
            }
            stack[depth] = operands[index];
            depth += 1;
            continue;
        }
        if (depth < 2) {
            return -3;
        }
        {
            int32_t right = stack[depth - 1];
            int32_t left = stack[depth - 2];
            int32_t value;
            depth -= 2;
            switch (token) {
            case '+':
                value = (int32_t)((uint32_t)left + (uint32_t)right);
                break;
            case '-':
                value = (int32_t)((uint32_t)left - (uint32_t)right);
                break;
            case '*':
                value = (int32_t)((uint32_t)left * (uint32_t)right);
                break;
            case '/':
                if (right == 0 || (left == (-2147483647 - 1) && right == -1)) {
                    return -4;
                }
                value = left / right;
                break;
            default:
                return -5;
            }
            stack[depth] = value;
            depth += 1;
        }
    }
    if (depth != 1) {
        return -6;
    }
    *result = stack[0];
    return depth;
}

Recovered C

Generated by glaurung decompile --style decbench at b47f6b43. baseline.json records the result after recompiling the C and calling it beside the original with seeded inputs.

clang -O2

0/1
rpn_evaluate fail 82 lines 
// glaurung: rpn_evaluate @ 0x1100
__attribute__((no_stack_protector)) int32_t rpn_evaluate(const uint8_t * arg0, const int32_t * arg1, int32_t arg2, int32_t * arg3) {
    int depth;
    int index;
    unsigned char token;
    int left;
    int right;
    int value;
    unsigned char local_58[88];
    long ret;
    long var0;
    long var10;
    long var17;
    long var3;
    long var7;
    // x86-64 prologue: save callee registers, frame 24 bytes
    ret = 0xffffffff;
    if (((unsigned long)(16) < (unsigned long)((unsigned long)((unsigned int)(arg2))))) {
        // x86-64 epilogue: restore callee registers
        return ret;
    }
    if ((arg0 == 0)) {
        // x86-64 epilogue: restore callee registers
        return ret;
    }
    if ((arg1 == 0)) {
        // x86-64 epilogue: restore callee registers
        return ret;
    }
    if ((arg3 == 0)) {
        // x86-64 epilogue: restore callee registers
        return ret;
    }
    ret = 0xfffffffa;
    if (((unsigned long)((unsigned int)(arg2)) == 0)) {
        // x86-64 epilogue: restore callee registers
        return ret;
    }
    var0 = (unsigned long)((unsigned int)(arg2));
    var3 = 0x2000;
    depth = 0;
    var7 = 0;
    goto L_1165;
    L_1155: ;
    index = (var7 + 1);
    depth = (unsigned long)((unsigned int)(var10));
    var7 = (unsigned long)((unsigned int)(index));
    if ((var0 == index)) {
        goto L_11f0;
    }
    L_1165: ;
    token = (unsigned int)((unsigned char)(*(char *)(((long)arg0 + var7))));
    if (((unsigned long)((unsigned char)((token & 255))) == 35)) {
        if (((((unsigned long)((unsigned int)(depth)) == 15) | ((long)(depth) < 15)) == 0)) {
            // x86-64 epilogue: restore callee registers
            return 0xfffffffe;
        }
        *(int *)((&local_58[0] + ((long)(depth) * 4))) = *(int *)(((long)arg1 + var7 * 4));
        var10 = (unsigned long)((unsigned int)((depth + 1)));
        goto L_1155;
    }
    if (((long)(depth) < 2)) {
        // x86-64 epilogue: restore callee registers
        return 0xfffffffd;
    }
    ret = 0xfffffffb;
    var17 = ((((unsigned long)(token) & 255) - 42) & 255);
    if (((unsigned long)(5) < (unsigned long)((unsigned long)((unsigned char)((var17 & 255)))))) {
        // x86-64 epilogue: restore callee registers
        return ret;
    }
    /* unrecovered indirect jump through ((long)((int)(*(int *)((var3 + ((unsigned int)((unsigned char)((var17 & 255))) * 4))))) + var3) */
    L_11f0: ;
    ret = 0xfffffffa;
    if (((unsigned long)((unsigned int)(var10)) != 1)) {
        // x86-64 epilogue: restore callee registers
        return ret;
    }
    *(int *)(((long)arg3)) = *(int *)(&local_58[0]);
    // x86-64 epilogue: restore callee registers
    return 1;
}

clang -O0

1/1
rpn_evaluate pass 131 lines 
// glaurung: rpn_evaluate @ 0x1100
__attribute__((no_stack_protector)) int32_t rpn_evaluate(const uint8_t * arg0, const int32_t * arg1, int32_t arg2, int32_t * arg3) {
    int depth;
    int index;
    unsigned char token;
    int right;
    int left;
    int value;
    int local_4;
    unsigned char local_70[64];
    long local_90;
    int var27;
    // x86-64 prologue: save rbp, frame 16 bytes
    depth = 0;
    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 ((arg3 == 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)) == 16) | ((long)(arg2) < 16)) == 0)) {
        local_4 = -1;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    index = 0;
    L_1166: ;
    while (1) {
        if ((arg2 <= index)) {
            goto L_12e7;
        }
        token = arg0[index];
        if (((unsigned long)((unsigned long)(token)) == 35)) {
            if ((16 <= (long)(depth))) {
                goto L_1197;
            }
            *(int *)((&local_70[0] + ((long)(depth) * 4))) = arg1[(long)(index)];
            depth = ((unsigned int)(depth) + 1);
            goto L_12d9;
        }
        if (((long)(depth) < 2)) {
            goto L_11ce;
        }
        right = *(int *)((&local_70[0] + ((long)((int)(((unsigned long)((unsigned int)(depth)) - 1))) * 4)));
        left = *(int *)((&local_70[0] + ((long)((int)(((unsigned long)((unsigned int)(depth)) - 2))) * 4)));
        depth = ((unsigned int)(depth) - 2);
        var27 = ((unsigned int)(token) - 42);
        local_90 = (unsigned int)(var27);
        if (((((unsigned long)((unsigned long)((unsigned int)(var27))) < (unsigned long)(5)) | ((unsigned long)((unsigned int)(((unsigned long)((unsigned int)(var27)) - 5))) == 0)) == 0)) {
            goto L_12b6;
        }
        switch (local_90) {
            case 0:
                goto L_125c;
            case 1:
                goto L_1234;
            case 3:
                goto L_1248;
            case 5:
                goto L_1271;
            default:
                goto L_12b6;
        }
        L_1234: ;
        value = ((unsigned int)(left) + right);
        goto L_12c2;
        L_1248: ;
        value = ((unsigned int)(left) - right);
        goto L_12c2;
        L_125c: ;
        value = ((unsigned int)(left) * right);
        goto L_12c2;
        L_1271: ;
        if (((unsigned long)((unsigned int)(right)) == 0)) {
            goto L_1295;
        }
        if (((unsigned long)((unsigned int)(left)) == 0x80000000)) {
            if (((unsigned long)((unsigned int)(right)) == 0xffffffff)) {
                goto L_1295;
            }
        }
        value = ((int)((((long long)(int)((((unsigned long)((long)((int)((unsigned long)((unsigned int)(left))))) >> 32) & 0xffffffff)) * (((long long)1) << 32)) + (unsigned int)((unsigned long)((unsigned int)(left)))) / (int)(right)));
        goto L_12c2;
        L_12c2: ;
        *(int *)((&local_70[0] + ((long)(depth) * 4))) = value;
        depth = ((unsigned int)(depth) + 1);
        L_12d9: ;
        index = ((unsigned int)(index) + 1);
        goto L_1166;
    }
    L_1197: ;
    local_4 = -2;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
    L_11ce: ;
    local_4 = -3;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
    L_1295: ;
    local_4 = -4;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
    L_12b6: ;
    local_4 = -5;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
    L_12e7: ;
    if (((unsigned long)((unsigned int)(depth)) != 1)) {
        local_4 = -6;
        // x86-64 epilogue: restore rbp
        return (unsigned int)(local_4);
    }
    *(int *)((long)arg3) = *(int *)(&local_70[0]);
    local_4 = depth;
    // x86-64 epilogue: restore rbp
    return (unsigned int)(local_4);
}

gcc -O0

1/1
rpn_evaluate pass 115 lines 
// glaurung: rpn_evaluate @ 0x1119
int32_t rpn_evaluate(const uint8_t * arg0, const int32_t * arg1, int32_t arg2, int32_t * arg3) {
    extern __attribute__((noreturn)) void __stack_chk_fail(void);
    int depth;
    int index;
    unsigned char token;
    int right;
    int left;
    int value;
    unsigned char local_50[64];
    long local_8;
    long ret;
    int var26;
    local_8 = (long)(0x28);
    depth = 0;
    if ((arg0 != 0)) {
        if ((arg1 != 0)) {
            if ((arg3 != 0)) {
                if ((0 <= (long)(arg2))) {
                    if ((((unsigned long)((unsigned int)(arg2)) == 16) | ((long)(arg2) < 16))) {
                        goto L_1187;
                    }
                }
            }
        }
    }
    ret = 0xffffffff;
    goto L_12ce;
    L_1187: ;
    index = 0;
    goto L_12a3;
    L_1193: ;
    token = arg0[index];
    if ((token == 35)) {
        if (((((unsigned long)((unsigned int)(depth)) == 15) | ((long)(depth) < 15)) == 0)) {
            ret = 0xfffffffe;
            goto L_12ce;
        }
        *(int *)((&local_50[0] + ((long)(depth) * 4))) = arg1[(long)(index)];
        depth = (depth + 1);
        goto L_129f;
    }
    if (((((unsigned long)((unsigned int)(depth)) == 1) | ((long)(depth) < 1)) != 0)) {
        ret = 0xfffffffd;
        goto L_12ce;
    }
    right = *(int *)((&local_50[0] + ((long)((int)(((unsigned long)((unsigned int)(depth)) - 1))) * 4)));
    left = *(int *)((&local_50[0] + ((long)((int)(((unsigned long)((unsigned int)(depth)) - 2))) * 4)));
    depth = (depth - 2);
    var26 = (unsigned int)(token);
    if (((unsigned long)((unsigned long)(token)) == 47)) {
        goto L_1260;
    }
    if (((((unsigned long)((unsigned int)(var26)) == 47) | ((long)((int)(var26)) < 47)) == 0)) {
        goto L_1288;
    }
    if (((unsigned long)((unsigned int)(var26)) != 45)) {
        if (((((unsigned long)((unsigned int)(var26)) == 45) | ((long)((int)(var26)) < 45)) == 0)) {
            goto L_1288;
        }
        if (((unsigned long)((unsigned int)(var26)) == 42)) {
            goto L_1252;
        }
        if (((unsigned long)((unsigned int)(var26)) != 43)) {
            goto L_1288;
        }
        value = ((unsigned int)(right) + (unsigned int)(left));
        goto L_128f;
    }
    value = ((unsigned int)(left) - (unsigned int)(right));
    goto L_128f;
    L_1252: ;
    value = ((unsigned int)(right) * (unsigned int)(left));
    goto L_128f;
    L_1260: ;
    if (((unsigned long)((unsigned int)(right)) != 0)) {
        if (((unsigned long)((unsigned int)(left)) != 0x80000000)) {
            goto L_127c;
        }
        if (((unsigned long)((unsigned int)(right)) != 0xffffffff)) {
            goto L_127c;
        }
    }
    ret = 0xfffffffc;
    goto L_12ce;
    L_127c: ;
    value = ((int)((((long long)(int)((((unsigned long)((long)((int)((unsigned long)((unsigned int)(left))))) >> 32) & 0xffffffff)) * (((long long)1) << 32)) + (unsigned int)((unsigned long)((unsigned int)(left)))) / (int)(right)));
    goto L_128f;
    L_1288: ;
    ret = 0xfffffffb;
    goto L_12ce;
    L_128f: ;
    *(int *)((&local_50[0] + ((long)(depth) * 4))) = value;
    depth = (depth + 1);
    L_129f: ;
    index = (index + 1);
    L_12a3: ;
    if ((index < arg2)) {
        goto L_1193;
    }
    if (((unsigned long)((unsigned int)(depth)) != 1)) {
        ret = 0xfffffffa;
        goto L_12ce;
    }
    *(int *)((long)arg3) = *(int *)(&local_50[0]);
    ret = (unsigned long)((unsigned int)(depth));
    L_12ce: ;
    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
rpn_evaluate pass 140 lines 
// glaurung: rpn_evaluate @ 0x1120
int32_t rpn_evaluate(const uint8_t * arg0, const int32_t * arg1, int32_t arg2, int32_t * arg3) {
    extern __attribute__((noreturn)) void __stack_chk_fail(void);
    int depth;
    int index;
    int right;
    int left;
    unsigned char token;
    int value;
    long cf_14;
    long local_10;
    unsigned char local_58[64];
    long ret;
    long t152;
    long var15;
    long var20;
    long var25;
    long var27;
    long var28;
    long var3;
    int * var4;
    long var8;
    long zf_14;
    local_10 = (long)(0x28);
    if ((arg0 != 0)) {
        var3 = (long)arg1;
        if ((arg1 != 0)) {
            var4 = (int *)arg3;
            if ((arg3 != 0)) {
                if (((unsigned long)((unsigned long)((unsigned int)(arg2))) <= (unsigned long)(16))) {
                    goto L_1178;
                }
            }
        }
    }
    ret = 0xffffffff;
    L_1158: ;
    if ((local_10 != 0x28)) {
        goto L_126e;
    }
    // x86-64 epilogue: tear down frame
    return ret;
    L_1178: ;
    if (((unsigned long)((unsigned int)(arg2)) == 0)) {
        goto L_1264;
    }
    var8 = (unsigned long)((unsigned int)((arg2 - 1)));
    depth = 0;
    index = 0;
    goto L_11d1;
    L_1190: ;
    if ((((unsigned long)((unsigned int)(depth)) == 1) | ((long)(depth) < 1))) {
        goto L_1250;
    }
    var15 = (unsigned long)((unsigned int)((depth - 1)));
    right = (unsigned long)((unsigned int)(*(int *)((&local_58[0] + ((long)((int)(var15)) * 4)))));
    var20 = (long)((int)((depth - 2)));
    left = (unsigned long)((unsigned int)(*(int *)((&local_58[0] + (var20 * 4)))));
    t152 = ((unsigned long)(token) & 255);
    zf_14 = ((unsigned long)((unsigned char)(t152)) == 45);
    cf_14 = ((unsigned long)((unsigned long)((unsigned char)(t152))) < (unsigned long)(45));
    if (((unsigned long)((unsigned char)(t152)) == 45)) {
        goto L_1228;
    }
    if (((cf_14 | zf_14) == 0)) {
        goto L_11f0;
    }
    if (((unsigned long)((unsigned char)((token & 255))) == 42)) {
        goto L_1220;
    }
    if (((unsigned long)((unsigned char)((token & 255))) != 43)) {
        goto L_1210;
    }
    var25 = (unsigned long)((unsigned int)((left + right)));
    L_11bf: ;
    *(int *)((&local_58[0] + (var20 * 4))) = var25;
    var27 = (unsigned long)((unsigned int)(var15));
    L_11c5: ;
    var28 = ((unsigned long)((unsigned int)(index)) + 1);
    if ((index == var8)) {
        goto L_1240;
    }
    depth = var27;
    index = var28;
    L_11d1: ;
    token = (unsigned int)((unsigned char)(*(char *)(((long)arg0 + index))));
    if (((unsigned long)((unsigned char)((token & 255))) != 35)) {
        goto L_1190;
    }
    if (((((unsigned long)((unsigned int)(depth)) == 15) | ((long)(depth) < 15)) == 0)) {
        goto L_125a;
    }
    *(int *)((&local_58[0] + ((long)(depth) * 4))) = *(int *)((var3 + index * 4));
    var27 = (unsigned long)((unsigned int)((depth + 1)));
    goto L_11c5;
    L_11f0: ;
    if (((unsigned long)((unsigned char)((token & 255))) != 47)) {
        goto L_1210;
    }
    if (((unsigned long)((unsigned int)(right)) == 0)) {
        goto L_122c;
    }
    if (((unsigned long)((unsigned int)(left)) == 0x80000000)) {
        if (((unsigned long)((unsigned int)(right)) == 0xffffffff)) {
            goto L_122c;
        }
    }
    var25 = ((int)((((long long)(int)((((unsigned long)((long)(left)) >> 32) & 0xffffffff)) * (((long long)1) << 32)) + (unsigned int)(left)) / (int)(right)));
    goto L_11bf;
    L_1210: ;
    ret = 0xfffffffb;
    goto L_1158;
    L_1220: ;
    var25 = (unsigned long)((unsigned int)((left * right)));
    goto L_11bf;
    L_1228: ;
    var25 = (unsigned long)((unsigned int)((left - right)));
    goto L_11bf;
    L_122c: ;
    ret = 0xfffffffc;
    goto L_1158;
    L_1240: ;
    if (((unsigned long)((unsigned int)(var27)) != 1)) {
        goto L_1264;
    }
    *(int *)((var4)) = *(int *)(&local_58[0]);
    ret = var27;
    goto L_1158;
    L_1250: ;
    ret = 0xfffffffd;
    goto L_1158;
    L_125a: ;
    ret = 0xfffffffe;
    goto L_1158;
    L_1264: ;
    ret = 0xfffffffa;
    goto L_1158;
    L_126e: ;
    __stack_chk_fail();
}

← 213 fixtures