Skip to content

Instantly share code, notes, and snippets.

@bit-hack

bit-hack/x86_branch.c

Created October 24, 2017 15:11
Show Gist options
  • Save bit-hack/181c25143ab46a210542972149e8b62c to your computer and use it in GitHub Desktop.
Save bit-hack/181c25143ab46a210542972149e8b62c to your computer and use it in GitHub Desktop.
Download ZIP
x86 branch emulation and fuzz test code
Raw
x86_branch.c
// ______ ________ __________,_ ___________
// ___ ___/ __ \/ _____/ \_ _____/ | _____ ____ ______\_ _____/_____ __ __
// \ \/ /> / __ \ | __)| | \__ \ / ___\/ ___/ | __)_/ \| | \
// > </ -- \ |__\ \ | | | |__/ __ \_/ /_/ >___ \ | \ Y Y \ | /
// / /\ \_______/\_______/ \____/ |____(______/\___ /_____/ /_________/_|_|__/____/
// \_/ \_/ ..:: x86 flags emulator ::.. /_____/
// '' Aidan Dodds 2017 ''
#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <intrin.h>
// eflags bit extraction macros
#define bit(NUM, IN) (((IN) >> (NUM)) & 1)
#define CF(IN) (bit(0x0, IN))
#define PF(IN) (bit(0x2, IN))
#define AF(IN) (bit(0x4, IN))
#define ZF(IN) (bit(0x6, IN))
#define SF(IN) (bit(0x7, IN))
#define DF(IN) (bit(0xa, IN))
#define OF(IN) (bit(0xb, IN))
// eflags bit masks
enum eflags_t {
e_CF = 1 << 0x00,
e_PF = 1 << 0x02,
e_AF = 1 << 0x04,
e_ZF = 1 << 0x06,
e_SF = 1 << 0x07,
e_DF = 1 << 0x10,
e_OF = 1 << 0x11,
};
// mask for only the bits needed for branch emulation
static const uint32_t EFLAG_MASK = e_CF | e_PF | e_AF | e_ZF | e_SF | e_DF | e_OF;
// branch type enumeration
enum branch_type_t {
eJA, eJNBE, // Jump Above / Jump Not Below or Equal
eJAE, eJNB, // Jump Above or Equal / Jump on Not Below
eJB, eJNAE, // Jump Below / Jump Not Above or Equal
eJBE, eJNA, // Jump Below or Equal / Jump Not Above
eJC, // Jump on Carry
eJE, eJZ, // Jump Equal / Jump Zero
eJG, eJNLE, // Jump Greater / Jump Not Less or Equal
eJGE, eJNL, // Jump Greater or Equal / Jump Not Less
eJL, eJNGE, // Jump Less / Jump Not Greater or Equal
eJLE, eJNG, // Jump Less or Equal / Jump Not Greater
eJMP, // Unconditional Jump
eJNC, // Jump Not Carry
eJNE, eJNZ, // Jump Not Equal / Jump Not Zero
eJNO, // Jump Not Overflow
eJNS, // Jump Not Signed
eJNP, eJPO, // Jump Not Parity / Jump Parity Odd
eJO, // Jump on Overflow
eJP, eJPE, // Jump on Parity / Jump on Parity Even
eJS, // Jump Signed
};
// 64 bit random number generator
static uint64_t rand64(uint64_t *x) {
*x ^= *x >> 12;
*x ^= *x << 25;
*x ^= *x >> 27;
return *x * 0x2545F4914F6CDD1D;
}
// x86 jump instruction conditional emulation
static int branch_emu(const enum branch_type_t type, const uint32_t flags) {
switch (type) {
case eJA:
case eJNBE: return !(CF(flags) || ZF(flags));
case eJAE:
case eJNB: return !CF(flags);
case eJB:
case eJNAE: return CF(flags);
case eJBE:
case eJNA: return CF(flags) || ZF(flags);
case eJG: return !SF(flags) && !OF(flags) && !ZF(flags);
case eJNLE: return !SF(flags) && !ZF(flags);
case eJGE: return !SF(flags) && !OF(flags);
case eJNL: return !SF(flags);
case eJL: return SF(flags);
case eJNGE: return SF(flags) || OF(flags);
case eJLE: return SF(flags) || ZF(flags);
case eJNG: return SF(flags) || OF(flags) || ZF(flags);
case eJC: return CF(flags);
case eJE:
case eJZ: return ZF(flags);
case eJMP: return 1;
case eJNC: return !CF(flags);
case eJNE:
case eJNZ: return !ZF(flags);
case eJNO: return !OF(flags);
case eJNS: return !SF(flags);
case eJNP:
case eJPO: return !PF(flags);
case eJO: return OF(flags);
case eJP:
case eJPE: return PF(flags);
case eJS: return SF(flags);
default:
assert(!"unknown branch type");
return 0;
}
}
typedef struct test_t {
const char *name;
enum branch_type_t type;
uint32_t (*test)(uint32_t);
} test_t;
// hardware reference for x86 JMP conditional
#define TEST_FUNC(INST) \
__declspec(naked) static \
uint32_t __cdecl test_##INST(uint32_t flags) { \
__asm { \
__asm pushfd \
__asm push [esp+8] \
__asm xor eax, eax \
__asm inc eax \
__asm popfd \
__asm INST done \
__asm xor eax, eax \
__asm done: \
__asm popfd \
__asm ret \
} \
}
// reference branch test functions
TEST_FUNC(JA)
TEST_FUNC(JNBE)
TEST_FUNC(JAE)
TEST_FUNC(JNB)
TEST_FUNC(JB)
TEST_FUNC(JNAE)
TEST_FUNC(JBE)
TEST_FUNC(JNA)
TEST_FUNC(JC)
TEST_FUNC(JE)
TEST_FUNC(JZ)
TEST_FUNC(JG)
TEST_FUNC(JNLE)
TEST_FUNC(JGE)
TEST_FUNC(JNL)
TEST_FUNC(JL)
TEST_FUNC(JNGE)
TEST_FUNC(JLE)
TEST_FUNC(JNG)
TEST_FUNC(JMP)
TEST_FUNC(JNC)
TEST_FUNC(JNE)
TEST_FUNC(JNZ)
TEST_FUNC(JNO)
TEST_FUNC(JNS)
TEST_FUNC(JNP)
TEST_FUNC(JPO)
TEST_FUNC(JO)
TEST_FUNC(JP)
TEST_FUNC(JPE)
TEST_FUNC(JS)
// branch test cases
#define TEST_CASE(INST) {#INST, e##INST, test_##INST}
static test_t tests[] = {
TEST_CASE(JA),
TEST_CASE(JNBE),
TEST_CASE(JAE),
TEST_CASE(JNB),
TEST_CASE(JB),
TEST_CASE(JNAE),
TEST_CASE(JBE),
TEST_CASE(JNA),
TEST_CASE(JC),
TEST_CASE(JE),
TEST_CASE(JZ),
TEST_CASE(JG),
TEST_CASE(JNLE),
TEST_CASE(JGE),
TEST_CASE(JNL),
TEST_CASE(JL),
TEST_CASE(JNGE),
TEST_CASE(JLE),
TEST_CASE(JNG),
TEST_CASE(JMP),
TEST_CASE(JNC),
TEST_CASE(JNE),
TEST_CASE(JNZ),
TEST_CASE(JNO),
TEST_CASE(JNS),
TEST_CASE(JNP),
TEST_CASE(JPO),
TEST_CASE(JO),
TEST_CASE(JP),
TEST_CASE(JPE),
TEST_CASE(JS),
{NULL, eJMP, NULL}
};
// hardware reference CMP routine
static uint32_t ref_cmp(uint32_t a, uint32_t b) {
uint32_t flags = 0;
__asm {
__asm pushad
__asm pushfd
__asm mov eax, a
__asm mov ebx, b
__asm cmp eax, ebx
__asm pushfd
__asm pop flags
__asm popfd
__asm popad
};
return flags;
}
// emulated CMP instruction
static uint32_t emu_cmp(uint32_t a, uint32_t b) {
uint32_t out = 0, res = a - b;
// set sign flag
out |= (res & 0x80000000) ? e_SF : 0;
// set zero flag
out |= (res == 0) ? e_ZF : 0;
// set parity flag
out ^= (res & 0x01) ? 0 : e_PF;
out ^= (res & 0x02) ? e_PF : 0;
out ^= (res & 0x04) ? e_PF : 0;
out ^= (res & 0x08) ? e_PF : 0;
out ^= (res & 0x10) ? e_PF : 0;
out ^= (res & 0x20) ? e_PF : 0;
out ^= (res & 0x40) ? e_PF : 0;
out ^= (res & 0x80) ? e_PF : 0;
// set carry flag
out |= (a < b) ? e_CF : 0;
// set adjust flag
out |= ((a & 0xf) < (b & 0xf)) ? e_AF : 0;
// return flags
return out;
}
// reference hardware TEST instruction
static uint32_t ref_test(uint32_t a, uint32_t b) {
uint32_t flags = 0;
__asm {
__asm pushad
__asm pushfd
__asm mov eax, a
__asm mov ebx, b
__asm test eax, ebx
__asm pushfd
__asm pop flags
__asm popfd
__asm popad
};
return flags;
}
// emulated TEST instruction
static uint32_t emu_test(uint32_t a, uint32_t b) {
uint32_t out = 0, res = a & b;
// set sign flag
out |= (res & 0x80000000) ? e_SF : 0;
// set zero flag
out |= (res == 0) ? e_ZF : 0;
// set parity flag
out ^= (res & 0x01) ? 0 : e_PF;
out ^= (res & 0x02) ? e_PF : 0;
out ^= (res & 0x04) ? e_PF : 0;
out ^= (res & 0x08) ? e_PF : 0;
out ^= (res & 0x10) ? e_PF : 0;
out ^= (res & 0x20) ? e_PF : 0;
out ^= (res & 0x40) ? e_PF : 0;
out ^= (res & 0x80) ? e_PF : 0;
// return flags
return out;
}
// evaluate JMP instruction emulations vs hardware reference
static void check_jmp() {
static const size_t num_itters = 10000;
uint64_t rng = 1;
// for each of out jump instruction conditions
for (int t = 0; tests[t].name; ++t) {
test_t *test = &tests[t];
uint32_t fails = 0;
// test for a number of itteration
for (uint32_t i = 0; i < num_itters; ++i) {
// generate random permutation of eflags
const uint32_t flags = EFLAG_MASK & (uint32_t)rand64(&rng);
// emulate branch instruction
const uint32_t r1 = branch_emu(test->type, flags);
// execute reference on hardware
const uint32_t r2 = test->test(flags);
fails += (r1 != r2);
}
printf(" %5s | (%u%%)\n", test->name, 100 - (fails*100)/num_itters);
}
}
// evaluate CMP instruction emulation vs hardware reference
static void check_cmp() {
static const size_t num_itters = 10000;
uint64_t rng = 1;
uint32_t tested = 0, failed = 0;
// flags affected:
// OF, SF, ZF, AF, PF, and CF as described in Appendix C
static const MASK = e_SF | e_ZF | e_PF | e_OF | e_CF | e_AF;
for (uint32_t i = 0; i < num_itters; ++i) {
// generate two random operands
const uint32_t opa = (uint32_t)rand64(&rng);
const uint32_t opb = (uint32_t)rand64(&rng);
// reference computed via native execution
const uint32_t ref = MASK & ref_cmp(opa, opb);
// emulation computed via emulation
const uint32_t gen = MASK & emu_cmp(opa, opb);
// count number of incorrect flags
const uint32_t dif = ref ^ gen;
failed += __popcnt(dif);
tested += __popcnt(MASK);
}
printf(" CMP | (%u%%)\n", 100 - (failed*100)/tested);
}
// evaluate TEST instruction emulation vs hardware reference
static void check_test() {
static const size_t num_itters = 10000;
uint64_t rng = 1;
uint32_t tested = 0, failed = 0;
// flags affected:
// OF = 0, CF = 0; SF, ZF, and PF as described in Appendix C
static const MASK = e_SF | e_ZF | e_PF | e_OF | e_CF;
for (uint32_t i = 0; i < num_itters; ++i) {
// generate two random operands
const uint32_t opa = (uint32_t)rand64(&rng);
const uint32_t opb = (uint32_t)rand64(&rng);
// reference computed via native execution
const uint32_t ref = MASK & ref_test(opa, opb);
// emulation computed via emulation
const uint32_t gen = MASK & emu_test(opa, opb);
// count number of incorrect flags
const uint32_t dif = ref ^ gen;
failed += __popcnt(dif);
tested += __popcnt(MASK);
}
printf(" TEST | (%u%%)\n", 100 - (failed*100)/tested);
}
int main(int argc, char **args) {
printf(" NAME | PASSED\n");
printf("--------+---------\n");
// run out test routines
check_jmp();
check_cmp();
check_test();
// hold on the static report
printf("press enter to exit...");
fgetc(stdin);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment