title: Emulate a MOS 6502 CPU

text:
# Question
Title: Emulate a MOS 6502 CPU
This is kind of inspired by the Intel 8086 challenge that's also on here, but I thought a 6502 challenge would be interesting too.

## The challenge

I thought this would be a fun one to see the results for. This one is obviously towards the more advanced side of the spectrum. The challenge is to write your own 6502 CPU emulator. This involves, of course, understanding its instruction set and its encoding format. Resources are linked at the bottom of this. The 6502 is one of the easiest real-world processors to emulate. For the purposes of this challenge, you won't need to worry about cycle timing if you don't want to — but that's always a plus to include!

DON'T COPY ANYBODY ELSE'S CODE!! Of course, you can certainly peek at other emulators to help you understand, but no copy and pasting! :)

Once your code works, you can always go the extra mile if you like and turn it into an Apple II emulator, or NES, C64, VIC-20 or any of the other billions of old 6502-based systems from back in the day.

### Testing your emulator

I have compiled a 6502 test suite which I found the source code to here: AllSuiteA.asm from hcm-6502

My compiled version can be downloaded here.

Load the 48 KB binary into your emulator's memory space at $4000, which leaves 16 KB of read-write RAM below it. When the test has finished executing, the value in address $0210 should be $FF, if your CPU passed. You will know that the test is finished when the program counter (PC) has reached address $45C0.

Other tests are available here as well: 6502 Test programs (for emulators and re-implementations)

### Doing something more interactive with it

Once your CPU works, you probably will want to do something more fun than staring at test output! I compiled a ROM image of Enhanced BASIC for the 6502. It is 16 KB, so you should load it into $C000 of your emulated memory space, reset your virtual 6502, and begin execution.

Download this ZIP, which contains ehbasic.bin.

The way that EhBASIC handles input/output is very simple. When it wants to write a character to the console, it writes the byte to memory location $F001. So, when your emulator sees the 6502 try to write to that location, simply print that character value to the console with a `printf("%c", value);` or however else you'd like. (This challenge isn't limited to C of course.)

When it polls for a character being inputted from the console, it's pretty similar. It keeps reading from memory location $F004, where you should have the next ASCII character value from the keyboard waiting to be read. If there is no more input to read, it should return a value of zero.

EhBASIC polls the value at that location until it's non-zero, which lets it know the byte is valid keyboard input. That's why if there's no more input to read, the emulator should return zero there. EhBASIC will spin on it until the next valid key when it's looking for input.

If you don't clear that value to zero after it reads the last key value, it will cause it to repeat as if you were holding the key down, so be careful to do that correctly!

If your emulator works correctly, this is what you will see printed out on your console when it executes the ROM image:

```
6502 EhBASIC [C]old/[W]arm ?

```

Press C, then press enter and you should see:

```
Memory size ?

31999 Bytes free

Enhanced BASIC 2.22

Ready

```

The bytes free may be different for you, but in my emulator I limited the writable memory area to a cap of 32 KB. You could really go all the way up to where the ROM begins, which is the 48 KB mark.

### 6502 CPU resource links

Here are some resources that should give you enough information to work with:

If you have questions or need more technical information, feel free to ask me. There is also a massive wealth of other 6502 info on the web. Google is your friend!

# Answer
> 23 votes
Thought I would go ahead and post my own implementation. It's COMPLETELY ungolfed, but it's a full implementation.

* 668 lines of C. (not counting blank lines or lines with only comments)
* Supports (I think) all undocumented instructions.
* Supports BCD.
* CPU clock cycle timing. (including adjustments on certain page-boundary wraps)
* Can execute instructions by either single-step or by specifying number of ticks.
* Supports hooking an external function to be called after every instruction is exectued. This was because it was originally for a NES emulator and I used this for audio timing.

```
/* Fake6502 CPU emulator core v1.1 *******************
 * (c)2011-2013 Mike Chambers                        *
 *****************************************************/

#include <stdio.h>
#include <stdint.h>

//externally supplied functions
extern uint8_t read6502(uint16_t address);
extern void write6502(uint16_t address, uint8_t value);

//6502 defines
#define UNDOCUMENTED //when this is defined, undocumented opcodes are handled.
                     //otherwise, they're simply treated as NOPs.

//#define NES_CPU      //when this is defined, the binary-coded decimal (BCD)
                     //status flag is not honored by ADC and SBC. the 2A03
                     //CPU in the Nintendo Entertainment System does not
                     //support BCD operation.

#define FLAG_CARRY     0x01
#define FLAG_ZERO      0x02
#define FLAG_INTERRUPT 0x04
#define FLAG_DECIMAL   0x08
#define FLAG_BREAK     0x10
#define FLAG_CONSTANT  0x20
#define FLAG_OVERFLOW  0x40
#define FLAG_SIGN      0x80

#define BASE_STACK     0x100

#define saveaccum(n) a = (uint8_t)((n) & 0x00FF)

//flag modifier macros
#define setcarry() status |= FLAG_CARRY
#define clearcarry() status &= (~FLAG_CARRY)
#define setzero() status |= FLAG_ZERO
#define clearzero() status &= (~FLAG_ZERO)
#define setinterrupt() status |= FLAG_INTERRUPT
#define clearinterrupt() status &= (~FLAG_INTERRUPT)
#define setdecimal() status |= FLAG_DECIMAL
#define cleardecimal() status &= (~FLAG_DECIMAL)
#define setoverflow() status |= FLAG_OVERFLOW
#define clearoverflow() status &= (~FLAG_OVERFLOW)
#define setsign() status |= FLAG_SIGN
#define clearsign() status &= (~FLAG_SIGN)

//flag calculation macros
#define zerocalc(n) {\
    if ((n) & 0x00FF) clearzero();\
        else setzero();\
}

#define signcalc(n) {\
    if ((n) & 0x0080) setsign();\
        else clearsign();\
}

#define carrycalc(n) {\
    if ((n) & 0xFF00) setcarry();\
        else clearcarry();\
}

#define overflowcalc(n, m, o) { /* n = result, m = accumulator, o = memory */ \
    if (((n) ^ (uint16_t)(m)) & ((n) ^ (o)) & 0x0080) setoverflow();\
        else clearoverflow();\
}

//6502 CPU registers
uint16_t pc;
uint8_t sp, a, x, y, status = FLAG_CONSTANT;

//helper variables
uint64_t instructions = 0; //keep track of total instructions executed
uint32_t clockticks6502 = 0, clockgoal6502 = 0;
uint16_t oldpc, ea, reladdr, value, result;
uint8_t opcode, oldstatus;

//a few general functions used by various other functions
void push16(uint16_t pushval) {
    write6502(BASE_STACK + sp, (pushval >> 8) & 0xFF);
    write6502(BASE_STACK + ((sp - 1) & 0xFF), pushval & 0xFF);
    sp -= 2;
}

void push8(uint8_t pushval) {
    write6502(BASE_STACK + sp--, pushval);
}

uint16_t pull16() {
    uint16_t temp16;
    temp16 = read6502(BASE_STACK + ((sp + 1) & 0xFF)) | ((uint16_t)read6502(BASE_STACK + ((sp + 2) & 0xFF)) << 8);
    sp += 2;
    return(temp16);
}

uint8_t pull8() {
    return (read6502(BASE_STACK + ++sp));
}

void reset6502() {
    pc = (uint16_t)read6502(0xFFFC) | ((uint16_t)read6502(0xFFFD) << 8);
    a = 0;
    x = 0;
    y = 0;
    sp = 0xFD;
    status |= FLAG_CONSTANT;
}

static void (*addrtable[256])();
static void (*optable[256])();
uint8_t penaltyop, penaltyaddr;

//addressing mode functions, calculates effective addresses
static void imp() { //implied
}

static void acc() { //accumulator
}

static void imm() { //immediate
    ea = pc++;
}

static void zp() { //zero-page
    ea = (uint16_t)read6502((uint16_t)pc++);
}

static void zpx() { //zero-page,X
    ea = ((uint16_t)read6502((uint16_t)pc++) + (uint16_t)x) & 0xFF; //zero-page wraparound
}

static void zpy() { //zero-page,Y
    ea = ((uint16_t)read6502((uint16_t)pc++) + (uint16_t)y) & 0xFF; //zero-page wraparound
}

static void rel() { //relative for branch ops (8-bit immediate value, sign-extended)
    reladdr = (uint16_t)read6502(pc++);
    if (reladdr & 0x80) reladdr |= 0xFF00;
}

static void abso() { //absolute
    ea = (uint16_t)read6502(pc) | ((uint16_t)read6502(pc+1) << 8);
    pc += 2;
}

static void absx() { //absolute,X
    uint16_t startpage;
    ea = ((uint16_t)read6502(pc) | ((uint16_t)read6502(pc+1) << 8));
    startpage = ea & 0xFF00;
    ea += (uint16_t)x;

    if (startpage != (ea & 0xFF00)) { //one cycle penlty for page-crossing on some opcodes
        penaltyaddr = 1;
    }

    pc += 2;
}

static void absy() { //absolute,Y
    uint16_t startpage;
    ea = ((uint16_t)read6502(pc) | ((uint16_t)read6502(pc+1) << 8));
    startpage = ea & 0xFF00;
    ea += (uint16_t)y;

    if (startpage != (ea & 0xFF00)) { //one cycle penlty for page-crossing on some opcodes
        penaltyaddr = 1;
    }

    pc += 2;
}

static void ind() { //indirect
    uint16_t eahelp, eahelp2;
    eahelp = (uint16_t)read6502(pc) | (uint16_t)((uint16_t)read6502(pc+1) << 8);
    eahelp2 = (eahelp & 0xFF00) | ((eahelp + 1) & 0x00FF); //replicate 6502 page-boundary wraparound bug
    ea = (uint16_t)read6502(eahelp) | ((uint16_t)read6502(eahelp2) << 8);
    pc += 2;
}

static void indx() { // (indirect,X)
    uint16_t eahelp;
    eahelp = (uint16_t)(((uint16_t)read6502(pc++) + (uint16_t)x) & 0xFF); //zero-page wraparound for table pointer
    ea = (uint16_t)read6502(eahelp & 0x00FF) | ((uint16_t)read6502((eahelp+1) & 0x00FF) << 8);
}

static void indy() { // (indirect),Y
    uint16_t eahelp, eahelp2, startpage;
    eahelp = (uint16_t)read6502(pc++);
    eahelp2 = (eahelp & 0xFF00) | ((eahelp + 1) & 0x00FF); //zero-page wraparound
    ea = (uint16_t)read6502(eahelp) | ((uint16_t)read6502(eahelp2) << 8);
    startpage = ea & 0xFF00;
    ea += (uint16_t)y;

    if (startpage != (ea & 0xFF00)) { //one cycle penlty for page-crossing on some opcodes
        penaltyaddr = 1;
    }
}

static uint16_t getvalue() {
    if (addrtable[opcode] == acc) return((uint16_t)a);
        else return((uint16_t)read6502(ea));
}

static void putvalue(uint16_t saveval) {
    if (addrtable[opcode] == acc) a = (uint8_t)(saveval & 0x00FF);
        else write6502(ea, (saveval & 0x00FF));
}

//instruction handler functions
static void adc() {
    penaltyop = 1;
    value = getvalue();
    result = (uint16_t)a + value + (uint16_t)(status & FLAG_CARRY);

    carrycalc(result);
    zerocalc(result);
    overflowcalc(result, a, value);
    signcalc(result);

    #ifndef NES_CPU
    if (status & FLAG_DECIMAL) {
        clearcarry();

        if ((a & 0x0F) > 0x09) {
            a += 0x06;
        }
        if ((a & 0xF0) > 0x90) {
            a += 0x60;
            setcarry();
        }

        clockticks6502++;
    }
    #endif

    saveaccum(result);
}

static void and() {
    penaltyop = 1;
    value = getvalue();
    result = (uint16_t)a & value;

    zerocalc(result);
    signcalc(result);

    saveaccum(result);
}

static void asl() {
    value = getvalue();
    result = value << 1;

    carrycalc(result);
    zerocalc(result);
    signcalc(result);

    putvalue(result);
}

static void bcc() {
    if ((status & FLAG_CARRY) == 0) {
        oldpc = pc;
        pc += reladdr;
        if ((oldpc & 0xFF00) != (pc & 0xFF00)) clockticks6502 += 2; //check if jump crossed a page boundary
            else clockticks6502++;
    }
}

static void bcs() {
    if ((status & FLAG_CARRY) == FLAG_CARRY) {
        oldpc = pc;
        pc += reladdr;
        if ((oldpc & 0xFF00) != (pc & 0xFF00)) clockticks6502 += 2; //check if jump crossed a page boundary
            else clockticks6502++;
    }
}

static void beq() {
    if ((status & FLAG_ZERO) == FLAG_ZERO) {
        oldpc = pc;
        pc += reladdr;
        if ((oldpc & 0xFF00) != (pc & 0xFF00)) clockticks6502 += 2; //check if jump crossed a page boundary
            else clockticks6502++;
    }
}

static void bit() {
    value = getvalue();
    result = (uint16_t)a & value;

    zerocalc(result);
    status = (status & 0x3F) | (uint8_t)(value & 0xC0);
}

static void bmi() {
    if ((status & FLAG_SIGN) == FLAG_SIGN) {
        oldpc = pc;
        pc += reladdr;
        if ((oldpc & 0xFF00) != (pc & 0xFF00)) clockticks6502 += 2; //check if jump crossed a page boundary
            else clockticks6502++;
    }
}

static void bne() {
    if ((status & FLAG_ZERO) == 0) {
        oldpc = pc;
        pc += reladdr;
        if ((oldpc & 0xFF00) != (pc & 0xFF00)) clockticks6502 += 2; //check if jump crossed a page boundary
            else clockticks6502++;
    }
}

static void bpl() {
    if ((status & FLAG_SIGN) == 0) {
        oldpc = pc;
        pc += reladdr;
        if ((oldpc & 0xFF00) != (pc & 0xFF00)) clockticks6502 += 2; //check if jump crossed a page boundary
            else clockticks6502++;
    }
}

static void brk() {
    pc++;
    push16(pc); //push next instruction address onto stack
    push8(status | FLAG_BREAK); //push CPU status to stack
    setinterrupt(); //set interrupt flag
    pc = (uint16_t)read6502(0xFFFE) | ((uint16_t)read6502(0xFFFF) << 8);
}

static void bvc() {
    if ((status & FLAG_OVERFLOW) == 0) {
        oldpc = pc;
        pc += reladdr;
        if ((oldpc & 0xFF00) != (pc & 0xFF00)) clockticks6502 += 2; //check if jump crossed a page boundary
            else clockticks6502++;
    }
}

static void bvs() {
    if ((status & FLAG_OVERFLOW) == FLAG_OVERFLOW) {
        oldpc = pc;
        pc += reladdr;
        if ((oldpc & 0xFF00) != (pc & 0xFF00)) clockticks6502 += 2; //check if jump crossed a page boundary
            else clockticks6502++;
    }
}

static void clc() {
    clearcarry();
}

static void cld() {
    cleardecimal();
}

static void cli() {
    clearinterrupt();
}

static void clv() {
    clearoverflow();
}

static void cmp() {
    penaltyop = 1;
    value = getvalue();
    result = (uint16_t)a - value;

    if (a >= (uint8_t)(value & 0x00FF)) setcarry();
        else clearcarry();
    if (a == (uint8_t)(value & 0x00FF)) setzero();
        else clearzero();
    signcalc(result);
}

static void cpx() {
    value = getvalue();
    result = (uint16_t)x - value;

    if (x >= (uint8_t)(value & 0x00FF)) setcarry();
        else clearcarry();
    if (x == (uint8_t)(value & 0x00FF)) setzero();
        else clearzero();
    signcalc(result);
}

static void cpy() {
    value = getvalue();
    result = (uint16_t)y - value;

    if (y >= (uint8_t)(value & 0x00FF)) setcarry();
        else clearcarry();
    if (y == (uint8_t)(value & 0x00FF)) setzero();
        else clearzero();
    signcalc(result);
}

static void dec() {
    value = getvalue();
    result = value - 1;

    zerocalc(result);
    signcalc(result);

    putvalue(result);
}

static void dex() {
    x--;

    zerocalc(x);
    signcalc(x);
}

static void dey() {
    y--;

    zerocalc(y);
    signcalc(y);
}

static void eor() {
    penaltyop = 1;
    value = getvalue();
    result = (uint16_t)a ^ value;

    zerocalc(result);
    signcalc(result);

    saveaccum(result);
}

static void inc() {
    value = getvalue();
    result = value + 1;

    zerocalc(result);
    signcalc(result);

    putvalue(result);
}

static void inx() {
    x++;

    zerocalc(x);
    signcalc(x);
}

static void iny() {
    y++;

    zerocalc(y);
    signcalc(y);
}

static void jmp() {
    pc = ea;
}

static void jsr() {
    push16(pc - 1);
    pc = ea;
}

static void lda() {
    penaltyop = 1;
    value = getvalue();
    a = (uint8_t)(value & 0x00FF);

    zerocalc(a);
    signcalc(a);
}

static void ldx() {
    penaltyop = 1;
    value = getvalue();
    x = (uint8_t)(value & 0x00FF);

    zerocalc(x);
    signcalc(x);
}

static void ldy() {
    penaltyop = 1;
    value = getvalue();
    y = (uint8_t)(value & 0x00FF);

    zerocalc(y);
    signcalc(y);
}

static void lsr() {
    value = getvalue();
    result = value >> 1;

    if (value & 1) setcarry();
        else clearcarry();
    zerocalc(result);
    signcalc(result);

    putvalue(result);
}

static void nop() {
    switch (opcode) {
        case 0x1C:
        case 0x3C:
        case 0x5C:
        case 0x7C:
        case 0xDC:
        case 0xFC:
            penaltyop = 1;
            break;
    }
}

static void ora() {
    penaltyop = 1;
    value = getvalue();
    result = (uint16_t)a | value;

    zerocalc(result);
    signcalc(result);

    saveaccum(result);
}

static void pha() {
    push8(a);
}

static void php() {
    push8(status | FLAG_BREAK);
}

static void pla() {
    a = pull8();

    zerocalc(a);
    signcalc(a);
}

static void plp() {
    status = pull8() | FLAG_CONSTANT;
}

static void rol() {
    value = getvalue();
    result = (value << 1) | (status & FLAG_CARRY);

    carrycalc(result);
    zerocalc(result);
    signcalc(result);

    putvalue(result);
}

static void ror() {
    value = getvalue();
    result = (value >> 1) | ((status & FLAG_CARRY) << 7);

    if (value & 1) setcarry();
        else clearcarry();
    zerocalc(result);
    signcalc(result);

    putvalue(result);
}

static void rti() {
    status = pull8();
    value = pull16();
    pc = value;
}

static void rts() {
    value = pull16();
    pc = value + 1;
}

static void sbc() {
    penaltyop = 1;
    value = getvalue() ^ 0x00FF;
    result = (uint16_t)a + value + (uint16_t)(status & FLAG_CARRY);

    carrycalc(result);
    zerocalc(result);
    overflowcalc(result, a, value);
    signcalc(result);

    #ifndef NES_CPU
    if (status & FLAG_DECIMAL) {
        clearcarry();

        a -= 0x66;
        if ((a & 0x0F) > 0x09) {
            a += 0x06;
        }
        if ((a & 0xF0) > 0x90) {
            a += 0x60;
            setcarry();
        }

        clockticks6502++;
    }
    #endif

    saveaccum(result);
}

static void sec() {
    setcarry();
}

static void sed() {
    setdecimal();
}

static void sei() {
    setinterrupt();
}

static void sta() {
    putvalue(a);
}

static void stx() {
    putvalue(x);
}

static void sty() {
    putvalue(y);
}

static void tax() {
    x = a;

    zerocalc(x);
    signcalc(x);
}

static void tay() {
    y = a;

    zerocalc(y);
    signcalc(y);
}

static void tsx() {
    x = sp;

    zerocalc(x);
    signcalc(x);
}

static void txa() {
    a = x;

    zerocalc(a);
    signcalc(a);
}

static void txs() {
    sp = x;
}

static void tya() {
    a = y;

    zerocalc(a);
    signcalc(a);
}

//undocumented instructions
#ifdef UNDOCUMENTED
    static void lax() {
        lda();
        ldx();
    }

    static void sax() {
        sta();
        stx();
        putvalue(a & x);
        if (penaltyop && penaltyaddr) clockticks6502--;
    }

    static void dcp() {
        dec();
        cmp();
        if (penaltyop && penaltyaddr) clockticks6502--;
    }

    static void isb() {
        inc();
        sbc();
        if (penaltyop && penaltyaddr) clockticks6502--;
    }

    static void slo() {
        asl();
        ora();
        if (penaltyop && penaltyaddr) clockticks6502--;
    }

    static void rla() {
        rol();
        and();
        if (penaltyop && penaltyaddr) clockticks6502--;
    }

    static void sre() {
        lsr();
        eor();
        if (penaltyop && penaltyaddr) clockticks6502--;
    }

    static void rra() {
        ror();
        adc();
        if (penaltyop && penaltyaddr) clockticks6502--;
    }
#else
    #define lax nop
    #define sax nop
    #define dcp nop
    #define isb nop
    #define slo nop
    #define rla nop
    #define sre nop
    #define rra nop
#endif

static void (*addrtable[256])() = {
/*        |  0  |  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9  |  A  |  B  |  C  |  D  |  E  |  F  |     */
/* 0 */     imp, indx,  imp, indx,   zp,   zp,   zp,   zp,  imp,  imm,  acc,  imm, abso, abso, abso, abso, /* 0 */
/* 1 */     rel, indy,  imp, indy,  zpx,  zpx,  zpx,  zpx,  imp, absy,  imp, absy, absx, absx, absx, absx, /* 1 */
/* 2 */    abso, indx,  imp, indx,   zp,   zp,   zp,   zp,  imp,  imm,  acc,  imm, abso, abso, abso, abso, /* 2 */
/* 3 */     rel, indy,  imp, indy,  zpx,  zpx,  zpx,  zpx,  imp, absy,  imp, absy, absx, absx, absx, absx, /* 3 */
/* 4 */     imp, indx,  imp, indx,   zp,   zp,   zp,   zp,  imp,  imm,  acc,  imm, abso, abso, abso, abso, /* 4 */
/* 5 */     rel, indy,  imp, indy,  zpx,  zpx,  zpx,  zpx,  imp, absy,  imp, absy, absx, absx, absx, absx, /* 5 */
/* 6 */     imp, indx,  imp, indx,   zp,   zp,   zp,   zp,  imp,  imm,  acc,  imm,  ind, abso, abso, abso, /* 6 */
/* 7 */     rel, indy,  imp, indy,  zpx,  zpx,  zpx,  zpx,  imp, absy,  imp, absy, absx, absx, absx, absx, /* 7 */
/* 8 */     imm, indx,  imm, indx,   zp,   zp,   zp,   zp,  imp,  imm,  imp,  imm, abso, abso, abso, abso, /* 8 */
/* 9 */     rel, indy,  imp, indy,  zpx,  zpx,  zpy,  zpy,  imp, absy,  imp, absy, absx, absx, absy, absy, /* 9 */
/* A */     imm, indx,  imm, indx,   zp,   zp,   zp,   zp,  imp,  imm,  imp,  imm, abso, abso, abso, abso, /* A */
/* B */     rel, indy,  imp, indy,  zpx,  zpx,  zpy,  zpy,  imp, absy,  imp, absy, absx, absx, absy, absy, /* B */
/* C */     imm, indx,  imm, indx,   zp,   zp,   zp,   zp,  imp,  imm,  imp,  imm, abso, abso, abso, abso, /* C */
/* D */     rel, indy,  imp, indy,  zpx,  zpx,  zpx,  zpx,  imp, absy,  imp, absy, absx, absx, absx, absx, /* D */
/* E */     imm, indx,  imm, indx,   zp,   zp,   zp,   zp,  imp,  imm,  imp,  imm, abso, abso, abso, abso, /* E */
/* F */     rel, indy,  imp, indy,  zpx,  zpx,  zpx,  zpx,  imp, absy,  imp, absy, absx, absx, absx, absx  /* F */
};

static void (*optable[256])() = {
/*        |  0  |  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9  |  A  |  B  |  C  |  D  |  E  |  F  |      */
/* 0 */      brk,  ora,  nop,  slo,  nop,  ora,  asl,  slo,  php,  ora,  asl,  nop,  nop,  ora,  asl,  slo, /* 0 */
/* 1 */      bpl,  ora,  nop,  slo,  nop,  ora,  asl,  slo,  clc,  ora,  nop,  slo,  nop,  ora,  asl,  slo, /* 1 */
/* 2 */      jsr,  and,  nop,  rla,  bit,  and,  rol,  rla,  plp,  and,  rol,  nop,  bit,  and,  rol,  rla, /* 2 */
/* 3 */      bmi,  and,  nop,  rla,  nop,  and,  rol,  rla,  sec,  and,  nop,  rla,  nop,  and,  rol,  rla, /* 3 */
/* 4 */      rti,  eor,  nop,  sre,  nop,  eor,  lsr,  sre,  pha,  eor,  lsr,  nop,  jmp,  eor,  lsr,  sre, /* 4 */
/* 5 */      bvc,  eor,  nop,  sre,  nop,  eor,  lsr,  sre,  cli,  eor,  nop,  sre,  nop,  eor,  lsr,  sre, /* 5 */
/* 6 */      rts,  adc,  nop,  rra,  nop,  adc,  ror,  rra,  pla,  adc,  ror,  nop,  jmp,  adc,  ror,  rra, /* 6 */
/* 7 */      bvs,  adc,  nop,  rra,  nop,  adc,  ror,  rra,  sei,  adc,  nop,  rra,  nop,  adc,  ror,  rra, /* 7 */
/* 8 */      nop,  sta,  nop,  sax,  sty,  sta,  stx,  sax,  dey,  nop,  txa,  nop,  sty,  sta,  stx,  sax, /* 8 */
/* 9 */      bcc,  sta,  nop,  nop,  sty,  sta,  stx,  sax,  tya,  sta,  txs,  nop,  nop,  sta,  nop,  nop, /* 9 */
/* A */      ldy,  lda,  ldx,  lax,  ldy,  lda,  ldx,  lax,  tay,  lda,  tax,  nop,  ldy,  lda,  ldx,  lax, /* A */
/* B */      bcs,  lda,  nop,  lax,  ldy,  lda,  ldx,  lax,  clv,  lda,  tsx,  lax,  ldy,  lda,  ldx,  lax, /* B */
/* C */      cpy,  cmp,  nop,  dcp,  cpy,  cmp,  dec,  dcp,  iny,  cmp,  dex,  nop,  cpy,  cmp,  dec,  dcp, /* C */
/* D */      bne,  cmp,  nop,  dcp,  nop,  cmp,  dec,  dcp,  cld,  cmp,  nop,  dcp,  nop,  cmp,  dec,  dcp, /* D */
/* E */      cpx,  sbc,  nop,  isb,  cpx,  sbc,  inc,  isb,  inx,  sbc,  nop,  sbc,  cpx,  sbc,  inc,  isb, /* E */
/* F */      beq,  sbc,  nop,  isb,  nop,  sbc,  inc,  isb,  sed,  sbc,  nop,  isb,  nop,  sbc,  inc,  isb  /* F */
};

static const uint32_t ticktable[256] = {
/*        |  0  |  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9  |  A  |  B  |  C  |  D  |  E  |  F  |     */
/* 0 */      7,    6,    2,    8,    3,    3,    5,    5,    3,    2,    2,    2,    4,    4,    6,    6,  /* 0 */
/* 1 */      2,    5,    2,    8,    4,    4,    6,    6,    2,    4,    2,    7,    4,    4,    7,    7,  /* 1 */
/* 2 */      6,    6,    2,    8,    3,    3,    5,    5,    4,    2,    2,    2,    4,    4,    6,    6,  /* 2 */
/* 3 */      2,    5,    2,    8,    4,    4,    6,    6,    2,    4,    2,    7,    4,    4,    7,    7,  /* 3 */
/* 4 */      6,    6,    2,    8,    3,    3,    5,    5,    3,    2,    2,    2,    3,    4,    6,    6,  /* 4 */
/* 5 */      2,    5,    2,    8,    4,    4,    6,    6,    2,    4,    2,    7,    4,    4,    7,    7,  /* 5 */
/* 6 */      6,    6,    2,    8,    3,    3,    5,    5,    4,    2,    2,    2,    5,    4,    6,    6,  /* 6 */
/* 7 */      2,    5,    2,    8,    4,    4,    6,    6,    2,    4,    2,    7,    4,    4,    7,    7,  /* 7 */
/* 8 */      2,    6,    2,    6,    3,    3,    3,    3,    2,    2,    2,    2,    4,    4,    4,    4,  /* 8 */
/* 9 */      2,    6,    2,    6,    4,    4,    4,    4,    2,    5,    2,    5,    5,    5,    5,    5,  /* 9 */
/* A */      2,    6,    2,    6,    3,    3,    3,    3,    2,    2,    2,    2,    4,    4,    4,    4,  /* A */
/* B */      2,    5,    2,    5,    4,    4,    4,    4,    2,    4,    2,    4,    4,    4,    4,    4,  /* B */
/* C */      2,    6,    2,    8,    3,    3,    5,    5,    2,    2,    2,    2,    4,    4,    6,    6,  /* C */
/* D */      2,    5,    2,    8,    4,    4,    6,    6,    2,    4,    2,    7,    4,    4,    7,    7,  /* D */
/* E */      2,    6,    2,    8,    3,    3,    5,    5,    2,    2,    2,    2,    4,    4,    6,    6,  /* E */
/* F */      2,    5,    2,    8,    4,    4,    6,    6,    2,    4,    2,    7,    4,    4,    7,    7   /* F */
};

void nmi6502() {
    push16(pc);
    push8(status);
    status |= FLAG_INTERRUPT;
    pc = (uint16_t)read6502(0xFFFA) | ((uint16_t)read6502(0xFFFB) << 8);
}

void irq6502() {
    push16(pc);
    push8(status);
    status |= FLAG_INTERRUPT;
    pc = (uint16_t)read6502(0xFFFE) | ((uint16_t)read6502(0xFFFF) << 8);
}

uint8_t callexternal = 0;
void (*loopexternal)();

void exec6502(uint32_t tickcount) {
    clockgoal6502 += tickcount;

    while (clockticks6502 < clockgoal6502) {
        opcode = read6502(pc++);

        penaltyop = 0;
        penaltyaddr = 0;

        (*addrtable[opcode])();
        (*optable[opcode])();
        clockticks6502 += ticktable[opcode];
        if (penaltyop && penaltyaddr) clockticks6502++;

        instructions++;

        if (callexternal) (*loopexternal)();
    }

}

void step6502() {
    opcode = read6502(pc++);

    penaltyop = 0;
    penaltyaddr = 0;

    (*addrtable[opcode])();
    (*optable[opcode])();
    clockticks6502 += ticktable[opcode];
    if (penaltyop && penaltyaddr) clockticks6502++;
    clockgoal6502 = clockticks6502;

    instructions++;

    if (callexternal) (*loopexternal)();
}

void hookexternal(void *funcptr) {
    if (funcptr != (void *)NULL) {
        loopexternal = funcptr;
        callexternal = 1;
    } else callexternal = 0;
}

```

# Answer
> 21 votes
A MOS 6502 emulator in Haskell. Features include:

* bit accurate implementation including subtle P register handling and page wrapping during indexing and indirection
* memory mapped IO, with spin loop detection (so host CPU doesn't peg while waiting for input)
* halt detection (jumps/branches to self)
* CPU implemented in exactly 200 lines & 6502 characters of code
* CPU implementation is pure state monad

This is a somewhat golf'd version of a full implementation (with more features) I did for this challenge that I'll post later. Despite the golf, the code is still straight forward. Only known missing feature is BCD mode (coming...)

Runs the ehBASIC code:

```
& ghc -O2 -o z6502min -Wall -fwarn-tabs -fno-warn-missing-signatures Z6502.hs
[1 of 1] Compiling Main             ( Z6502.hs, Z6502.o )

Z6502.hs:173:1: Warning: Defined but not used: `nmi'

Z6502.hs:174:1: Warning: Defined but not used: `irq'
Linking z6502min ...

& ./z6502min ehbasic.bin
6502 EhBASIC [C]old/[W]arm ?

Memory size ?

48383 Bytes free

Enhanced BASIC 2.22

Ready
PRINT "Hello World"
Hello World

Ready
10 FOR I = 1 TO 10
20 FOR J = 1 TO I
30 PRINT J;
40 NEXT J
50 PRINT
60 NEXT I
RUN
 1
 1 2
 1 2 3
 1 2 3 4
 1 2 3 4 5
 1 2 3 4 5 6
 1 2 3 4 5 6 7
 1 2 3 4 5 6 7 8
 1 2 3 4 5 6 7 8 9
 1 2 3 4 5 6 7 8 9 10

Ready

```

And the code, at under 300 lines total:

```
-- Z6502: a 6502 emulator
-- by Mark Lentczner

module Main (main) where

import Control.Applicative
import Control.Monad
import Control.Monad.State.Strict
import Data.Bits
import qualified Data.ByteString as B
import Data.List
import qualified Data.Vector as V
import qualified Data.Vector.Unboxed as VU
import Data.Word
import System.Environment
import System.IO

{- === CPU: 200 lines, 6502 characters === -}
type Addr = Word16
toAd = fromIntegral :: Int -> Addr
addr :: Word8 -> Word8 -> Addr
addr lo hi = fromIntegral hi `shiftL` 8 .|. fromIntegral lo
lohi ad = (fromIntegral ad, fromIntegral $ ad `shiftR` 8)
zeroPage v = addr v 0
index ad idx = ad + fromIntegral (idx :: Word8)
relativeAddr ad off = index ad off - if off > 0x7f then 256 else 0

data Page = Missing | ROM !B.ByteString | RAM !(VU.Vector Word8)
type Memory = V.Vector Page
emptyMemory = V.replicate 256 Missing

fetchByte ad mv = case mv V.! hi of
    ROM bs -> B.index bs lo
    RAM vs -> vs VU.! lo
    _ -> 0
  where (hi,lo) = fromIntegral ad `divMod` 256
storeByte ad v mv = case mv V.! hi of
    RAM vs -> mv V.// [(hi, RAM $ vs VU.// [(lo, v)])]
    _ -> mv
  where (hi,lo) = fromIntegral ad `divMod` 256

data S = S { rA, rX, rY, rP, rS :: !Word8, rPC :: !Addr
           , mem :: !Memory, busR,busW :: Maybe Addr }
powerOnState = S 0 0 0 0 0 0 emptyMemory Nothing Nothing

[bitN, bitV, bitX, bitB, bitD, bitI, bitZ, bitC] = [7,6..0]
toBit b t v = (if t then setBit else clearBit) v b
toZ v = toBit bitZ (v == 0)
toZN v = toBit bitZ (v == 0) . toBit bitN (testBit v 7)
to67 v = toBit bitV (testBit v 6) . toBit bitN (testBit v 7)

setZN v = modify $ \s -> s { rP = toZN v $ rP s }
setAZN v = modify $ \s -> s { rA = v, rP=toZN v $ rP s }
setXZN v = modify $ \s -> s { rX = v, rP=toZN v $ rP s }
setYZN v = modify $ \s -> s { rY = v, rP=toZN v $ rP s }
setZVNbit (a,v) = modify $ \s -> s { rP = toZ (a .&. v) $ to67 v $ rP s }
setACZVN (c,v,a) = modify $ \s ->
    s { rA = a, rP = toBit bitC c $ toBit bitV v $ toZN a $ rP s }
setCZN (c,v) = modify $ \s -> s { rP = toBit bitC c $ toZN v $ rP s }

fetch a = state $ \s -> (fetchByte a $ mem s, s { busR = Just a })
fetchIndirectAddr a0 = do
    m <- gets mem
    let (lo,hi) = lohi a0
        a1 = addr (lo+1) hi
        bLo = fetchByte a0 m
        bHi = fetchByte a1 m
    return $ addr bLo bHi
store a v = modify $ \s -> s { mem = storeByte a v $ mem s, busW = Just a }

clearBus = modify $ \s -> s { busR = Nothing, busW = Nothing }
nextPC = state $ \s -> (rPC s, s { rPC = rPC s + 1 })
fetchPC = nextPC >>= \a -> gets mem >>= return . fetchByte a

adjSP n m = state $ \s -> (addr (rS s + m) 1, s { rS = rS s + n })
push v = adjSP (-1) 0 >>= flip store v
pull = adjSP 1 1 >>= fetch
pushAddr a = let (lo, hi) = lohi a in push hi >> push lo
pullAddr = addr <$> pull <*> pull
pushP fromSW = gets rP >>= push . toBit bitX True . toBit bitB fromSW
pullP = pull >>= \v -> modify $ \s -> s { rP = v .&. 0xCF }

indexX a = gets rX >>= return . index a
indexY a = gets rY >>= return . index a
aImm=nextPC
aZero=zeroPage<$>fetchPC
aZeroX=zeroPage<$>((+)<$>fetchPC<*>gets rX)
aZeroY=zeroPage<$>((+)<$>fetchPC<*>gets rY)
aRel=flip relativeAddr<$>fetchPC<*>gets rPC
aAbs=addr<$>fetchPC<*>fetchPC
aAbsX=aAbs>>=indexX
aAbsY=aAbs>>=indexY
aInd=aAbs>>=fetchIndirectAddr
aIndIdx=aZeroX>>=fetchIndirectAddr
aIdxInd=aZero>>=fetchIndirectAddr>>=indexY

decode = V.fromList $ concat $ transpose
 [[iBRK,iBPL,iJSR&aAbs,iBMI,iRTI,iBVC,iRTS,iBVS
  ,iErr,iBCC,iLDY&aImm,iBCS,iCPY&aImm,iBNE,iCPX&aImm,iBEQ]
 ,cAlu aIndIdx aIdxInd
 ,cErr//(10,iLDX&aImm)
 ,cErr
 ,[iErr,iErr,iBIT&aZero,iErr,iErr,iErr,iErr,iErr
  ,iSTY&aZero,iSTY&aZeroX,iLDY&aZero,iLDY&aZeroX,iCPY&aZero,iErr,iCPX&aZero,iErr]
 ,cAlu aZero aZeroX
 ,cBit aZero aZeroX//(9,iSTX&aZeroY)//(11,iLDX&aZeroY)
 ,cErr
 ,[iPHP,iCLC,iPLP,iSEC,iPHA,iCLI,iPLA,iSEI,iDEY,iTYA,iTAY,iCLV,iINY,iCLD,iINX,iSED]
 ,cAlu aImm aAbsY//(8,iErr)
 ,[iASLa,iErr,iROLa,iErr,iLSRa,iErr,iRORa,iErr
  ,iTXA,iTXS,iTAX,iTSX,iDEX,iErr,iNOP,iErr ]
 ,cErr
 ,[iErr,iErr,iBIT&aAbs,iErr,iJMP&aAbs,iErr,iJMP&aInd,iErr
  ,iSTY&aAbs,iErr,iLDY&aAbs,iLDY&aAbsX,iCPY&aAbs,iErr,iCPX&aAbs,iErr]
 ,cAlu aAbs aAbsX
 ,cBit aAbs aAbsX//(9,iErr)//(11,iLDX&aAbsY)
 ,cErr
 ]
cAlt is e o = is >>= (\i->[i&e,i&o])
cAlu = cAlt [iORA,iAND,iEOR,iADC,iSTA,iLDA,iCMP,iSBC]
cBit = cAlt [iASL,iROL,iLSR,iROR,iSTX,iLDX,iDEC,iINC]
cErr = replicate 16 iErr
is//(n,j) = let (f,_:h) = splitAt n is in f++j:h
i&a=a>>=i

loadIns l a = fetch a >>= l
storeIns f a = f >>= store a

aluIns set op ad = do
    v <- fetch ad
    a <- gets rA
    set $ op a v

modIns op a = fetch a >>= op >>= store a
modAccIns op = gets rA >>= op >>= \v -> modify $ \s -> s { rA = v }

stIns b op = modify $ \s -> s { rP = op (rP s) b }

jump a = modify $ \s -> s { rPC = a }
brIns b t = do
    a <- aRel
    p <- gets rP
    when (testBit p b == t) $ jump a

adcOp a b cIn = (cOut, v, s)
  where
    h = b + (if cIn then 1 else 0)
    s = a + h
    cOut = h < b || s < a
    v = testBit (a `xor` s .&. b `xor` s) 7
sbcOp a b cIn = adcOp a (complement b) cIn
carryOp f = gets rP >>= setACZVN . f . flip testBit bitC

cmpOp a b = (a >= b, a - b)

shiftOp shifter isRot inBit outBit v = do
    s <- get
    let newC = testBit v outBit
        bitIn = toBit inBit $ isRot && testBit (rP s) bitC
        v' = bitIn $ shifter v 1
    put s { rP = toBit bitC newC $ toZN v' $ rP s }
    return v'

vector a = fetchIndirectAddr a >>= jump

interrupt isBrk pcOffset a = do
    gets rPC >>= pushAddr . flip index pcOffset
    pushP isBrk
    iSEI
    vector a

reset = vector $ toAd 0xFFFC
nmi = interrupt False 0 $ toAd 0xFFFA
irq = interrupt False 0 $ toAd 0xFFFE

[iORA,iAND,iEOR]=aluIns setAZN<$>[(.|.),(.&.),xor]
[iADC,iSBC]=aluIns carryOp<$>[adcOp,sbcOp]
iSTA=storeIns$gets rA
iLDA=loadIns setAZN
iCMP=aluIns setCZN cmpOp

[iSTX,iSTY]=storeIns.gets<$>[rX,rY]
[iLDX,iLDY]=loadIns<$>[setXZN,setYZN]
[iCPX,iCPY]=(\r a->gets r>>= \v->fetch a>>=setCZN.cmpOp v)<$>[rX,rY]
[iDEC,iINC]=modIns.(\i v->setZN(v+i)>>return(v+i))<$>[-1,1]
[iDEX,iINX]=(gets rX>>=).(setXZN.).(+)<$>[-1,1]
[iDEY,iINY]=(gets rY>>=).(setYZN.).(+)<$>[-1,1]

shOps=[shiftOp d r b(7-b)|(d,b)<-[(shiftL,0),(shiftR,7)],r<-[False,True]]
[iASL,iROL,iLSR,iROR]=modIns<$>shOps
[iASLa,iROLa,iLSRa,iRORa]=modAccIns<$>shOps

iBIT=aluIns setZVNbit(,)
iJMP=jump

[iBPL,iBMI,iBVC,iBVS,iBCC,iBCS,iBNE,iBEQ]=brIns<$>[bitN,bitV,bitC,bitZ]<*>[False,True]
[iCLC,iSEC,iCLI,iSEI,iCLV,_,iCLD,iSED]=stIns<$>[bitC,bitI,bitV,bitD]<*>[clearBit,setBit]

iBRK=interrupt True 1 $ toAd 0xFFFE
iJSR a=gets rPC>>=pushAddr.(-1+)>>jump a
iRTI=iPLP>>pullAddr>>=jump
iRTS=pullAddr>>=jump.(1+)

iPHP=pushP True
iPLP=pullP
iPHA=gets rA>>=push
iPLA=pull>>=setAZN

iNOP=return ()

[iTAX,iTAY]=(gets rA>>=)<$>[setXZN,setYZN]
[iTXA,iTYA]=(>>=setAZN).gets<$>[rX,rY]
iTXS=modify $ \s -> s { rS=rX s }
iTSX=gets rS>>=setXZN

iErr=gets rPC>>=jump.(-1+)

executeOne = clearBus >> fetchPC >>= (decode V.!) . fromIntegral
{- === END OF CPU === -}

{- === MOTHERBOARD === -}
buildMemory rom =
    loadRAM 0xF0 1 $ loadRAM 0x00 ramSize $ loadROM romStart rom $ emptyMemory
  where
    ramSize = 256 - (B.length rom `div` 256)
    romStart = fromIntegral ramSize

    loadRAM p0 n = (V.// zip [p0..] (map RAM $ replicate n ramPage))
    ramPage = VU.replicate 256 0

    loadROM p0 bs = (V.// zip [p0..] (map ROM $ romPages bs))
    romPages b = case B.length b of
        l | l == 0    -> []
          | l < 256   -> [b `B.append` B.replicate (256 - l) 0]
          | l == 256  -> [b]
          | otherwise -> let (b0,bn) = B.splitAt 256 b in b0 : romPages bn

main = getArgs >>= go
  where
    go [romFile] = B.readFile romFile >>= exec . buildState . buildMemory
    go _ = putStrLn "agument should be a single ROM file"

    buildState m = execState reset (powerOnState { mem = m })

    exec s0 = do
        stopIO <- startIO
        loop (0 :: Int) s0
        stopIO

    loop n s = do
        let pcsp = (rPC s, rS s)
        (n',s') <- processIO n (execState executeOne s)
        let pcsp' = (rPC s', rS s')
        if pcsp /= pcsp'
            then (loop $! n') $! s'
            else do
                putStrLn $ "Execution snagged at " ++ show (fst pcsp')

    startIO = do
        ibuf <- hGetBuffering stdin
        obuf <- hGetBuffering stdout
        iecho <- hGetEcho stdin
        hSetBuffering stdin NoBuffering
        hSetBuffering stdout NoBuffering
        hSetEcho stdin False
        return $ do
            hSetEcho stdin iecho
            hSetBuffering stdin ibuf
            hSetBuffering stdout obuf
            putStr "\n\n"

    processIO n s = do
        when (busW s == Just outPortAddr) $ do
            let c = fetchByte outPortAddr $ mem s
            when (c /= 0) $ hPutChar stdout $ toEnum $ fromIntegral c
        if (busR s == Just inPortAddr)
            then do
                r <- if n < 16
                        then hWaitForInput stdin 50
                        else hReady stdin
                c <- if r then (fromIntegral . fromEnum) <$> hGetChar stdin else return 0
                let c' = if c == 0xA then 0xD else c
                let s' = s { mem = storeByte inPortAddr c' $ mem s }
                return (0,s')
            else return (n+1,s)

    inPortAddr = toAd 0xF004
    outPortAddr = toAd 0xF001

```

# Answer
> 8 votes
For anyone interested I thought I would share my implementation of the 6502 in C#. As with other posts here it is completely ungolfed but is a feature complete implementation.

* Supports NMOS and CMOS
* Includes several test programs including the AllSuite test above as Unit Tests.
* Supports BCD

I started this project by creating a spreadsheet of instructions when I was first learning about the CPU. I realized I could use this spreadsheet to save myself some typing. I turned this into a text file table that the emulator loads to help count cycles and for easy disassembly output.

Entire project is available on Github https://github.com/amensch/e6502

```
/*
 * e6502: A complete 6502 CPU emulator.
 * Copyright 2016 Adam Mensch
 */

using System;

namespace e6502CPU
{
    public enum e6502Type
    {
        CMOS,
        NMOS
    };

    public class e6502
    {
        // Main Register
        public byte A;

        // Index Registers
        public byte X;
        public byte Y;

        // Program Counter
        public ushort PC;

        // Stack Pointer
        // Memory location is hard coded to 0x01xx
        // Stack is descending (decrement on push, increment on pop)
        // 6502 is an empty stack so SP points to where next value is stored
        public byte SP;

        // Status Registers (in order bit 7 to 0)
        public bool NF;    // negative flag (N)
        public bool VF;    // overflow flag (V)
                           // bit 5 is unused
                           // bit 4 is the break flag however it is not a physical flag in the CPU
        public bool DF;    // binary coded decimal flag (D)
        public bool IF;    // interrupt flag (I)
        public bool ZF;    // zero flag (Z)
        public bool CF;    // carry flag (C)

        // RAM - 16 bit address bus means 64KB of addressable memory
        public byte[] memory;

        // List of op codes and their attributes
        private OpCodeTable _opCodeTable;

        // The current opcode
        private OpCodeRecord _currentOP;

        // Clock cycles to adjust due to page boundaries being crossed, branches taken, or NMOS/CMOS differences
        private int _extraCycles;

        // Flag for hardware interrupt (IRQ)
        public bool IRQWaiting { get; set; }

        // Flag for non maskable interrupt (NMI)
        public bool NMIWaiting { get; set; }

        public e6502Type _cpuType { get; set; }

        public e6502(e6502Type type)
        {
            memory = new byte[0x10000];
            _opCodeTable = new OpCodeTable();

            // Set these on instantiation so they are known values when using this object in testing.
            // Real programs should explicitly load these values before using them.
            A = 0;
            X = 0;
            Y = 0;
            SP = 0;
            PC = 0;
            NF = false;
            VF = false;
            DF = false;
            IF = true;
            ZF = false;
            CF = false;
            NMIWaiting = false;
            IRQWaiting = false;
            _cpuType = type;
        }

        public void Boot()
        {
            // On reset the addresses 0xfffc and 0xfffd are read and PC is loaded with this value.
            // It is expected that the initial program loaded will have these values set to something.
            // Most 6502 systems contain ROM in the upper region (around 0xe000-0xffff)
            PC = GetWordFromMemory(0xfffc);

            // interrupt disabled is set on powerup
            IF = true;

            NMIWaiting = false;
            IRQWaiting = false;
        }

        public void LoadProgram(ushort startingAddress, byte[] program)
        {
            program.CopyTo(memory, startingAddress);
            PC = startingAddress;
        }

        public string DasmNextInstruction()
        {
            OpCodeRecord oprec = _opCodeTable.OpCodes[ memory[PC] ];
            if (oprec.Bytes == 3)
                return oprec.Dasm( GetImmWord() );
            else
                return oprec.Dasm( GetImmByte() );
        }

        // returns # of clock cycles needed to execute the instruction
        public int ExecuteNext()
        {
            _extraCycles = 0;

            // Check for non maskable interrupt (has higher priority over IRQ)
            if (NMIWaiting)
            {
                DoIRQ(0xfffa);
                NMIWaiting = false;
                _extraCycles += 6;
            }
            // Check for hardware interrupt, if enabled
            else if (!IF)
            {
                if(IRQWaiting)
                {
                    DoIRQ(0xfffe);
                    IRQWaiting = false;
                    _extraCycles += 6;
                }
            }

            _currentOP = _opCodeTable.OpCodes[memory[PC]];

            ExecuteInstruction();

            return _currentOP.Cycles + _extraCycles;
        }

        private void ExecuteInstruction()
        {
            int result;
            int oper = GetOperand(_currentOP.AddressMode);

            switch (_currentOP.OpCode)
            {
                // ADC - add memory to accumulator with carry
                // A+M+C -> A,C (NZCV)
                case 0x61:
                case 0x65:
                case 0x69:
                case 0x6d:
                case 0x71:
                case 0x72:
                case 0x75:
                case 0x79:
                case 0x7d:

                    if (DF)
                    {
                        result = HexToBCD(A) + HexToBCD((byte)oper);
                        if (CF) result++;

                        CF = (result > 99);

                        if (result > 99 )
                        {
                            result -= 100;
                        }
                        ZF = (result == 0);

                        // convert decimal result to hex BCD result
                        A = BCDToHex(result);

                        // Unlike ZF and CF, the NF flag represents the MSB after conversion
                        // to BCD.
                        NF = (A > 0x7f);

                        // extra clock cycle on CMOS in decimal mode
                        if (_cpuType == e6502Type.CMOS)
                            _extraCycles++;
                    }
                    else
                    {
                        ADC((byte)oper);
                    }
                    PC += _currentOP.Bytes;
                    break;

                // AND - and memory with accumulator
                // A AND M -> A (NZ)
                case 0x21:
                case 0x25:
                case 0x29:
                case 0x2d:
                case 0x31:
                case 0x32:
                case 0x35:
                case 0x39:
                case 0x3d:
                    result = A & oper;

                    NF = ((result & 0x80) == 0x80);
                    ZF = ((result & 0xff) == 0x00);

                    A = (byte)result;
                    PC += _currentOP.Bytes;
                    break;

                // ASL - shift left one bit (NZC)
                // C <- (76543210) <- 0

                case 0x06:
                case 0x16:
                case 0x0a:
                case 0x0e:
                case 0x1e:

                    // On 65C02 (abs,X) takes one less clock cycle (but still add back 1 if page boundary crossed)
                    if (_currentOP.OpCode == 0x1e && _cpuType == e6502Type.CMOS)
                        _extraCycles--;

                    // shift bit 7 into carry
                    CF = (oper >= 0x80);

                    // shift operand
                    result = oper << 1;

                    NF = ((result & 0x80) == 0x80);
                    ZF = ((result & 0xff) == 0x00);

                    SaveOperand(_currentOP.AddressMode, result);
                    PC += _currentOP.Bytes;

                    break;

                // BBRx - test bit in memory (no flags)
                // Test the zero page location and branch of the specified bit is clear
                // These instructions are only available on Rockwell and WDC 65C02 chips.
                // Number of clock cycles is the same regardless if the branch is taken.
                case 0x0f:
                case 0x1f:
                case 0x2f:
                case 0x3f:
                case 0x4f:
                case 0x5f:
                case 0x6f:
                case 0x7f:

                    // upper nibble specifies the bit to check
                    byte check_bit = (byte)(_currentOP.OpCode >> 4);
                    byte check_value = 0x01;
                    for( int ii=0; ii < check_bit; ii++)
                    {
                        check_value = (byte)(check_value << 1);
                    }

                    // if the specified bit is 0 then branch
                    byte offset = memory[PC + 2];
                    PC += _currentOP.Bytes;

                    if ((oper & check_value) == 0x00)
                        PC += offset;

                    break;

                // BBSx - test bit in memory (no flags)
                // Test the zero page location and branch of the specified bit is set
                // These instructions are only available on Rockwell and WDC 65C02 chips.
                // Number of clock cycles is the same regardless if the branch is taken.
                case 0x8f:
                case 0x9f:
                case 0xaf:
                case 0xbf:
                case 0xcf:
                case 0xdf:
                case 0xef:
                case 0xff:

                    // upper nibble specifies the bit to check (but ignore bit 7)
                    check_bit = (byte)((_currentOP.OpCode & 0x70) >> 4);
                    check_value = 0x01;
                    for (int ii = 0; ii < check_bit; ii++)
                    {
                        check_value = (byte)(check_value << 1);
                    }

                    // if the specified bit is 1 then branch
                    offset = memory[PC + 2];
                    PC += _currentOP.Bytes;

                    if ((oper & check_value) == check_value)
                        PC += offset;

                    break;

                // BCC - branch on carry clear
                case 0x90:
                    PC += _currentOP.Bytes;
                    CheckBranch(!CF, oper);
                    break;

                // BCS - branch on carry set
                case 0xb0:
                    PC += _currentOP.Bytes;
                    CheckBranch(CF, oper);
                    break;

                // BEQ - branch on zero
                case 0xf0:
                    PC += _currentOP.Bytes;
                    CheckBranch(ZF, oper);
                    break;

                // BIT - test bits in memory with accumulator (NZV)
                // bits 7 and 6 of oper are transferred to bits 7 and 6 of conditional register (N and V)
                // the zero flag is set to the result of oper AND accumulator
                case 0x24:
                case 0x2c:
                // added by 65C02
                case 0x34:
                case 0x3c:
                case 0x89:
                    result = A & oper;

                    // The WDC programming manual for 65C02 indicates NV are unaffected in immediate mode.
                    // The extended op code test program reflects this.
                    if (_currentOP.AddressMode != AddressModes.Immediate)
                    {
                        NF = ((oper & 0x80) == 0x80);
                        VF = ((oper & 0x40) == 0x40);
                    }

                    ZF = ((result & 0xff) == 0x00);

                    PC += _currentOP.Bytes;
                    break;

                // BMI - branch on negative
                case 0x30:
                    PC += _currentOP.Bytes;
                    CheckBranch(NF, oper);
                    break;

                // BNE - branch on non zero
                case 0xd0:
                    PC += _currentOP.Bytes;
                    CheckBranch(!ZF, oper);
                    break;

                // BPL - branch on non negative
                case 0x10:
                    PC += _currentOP.Bytes;
                    CheckBranch(!NF, oper);
                    break;

                // BRA - unconditional branch to immediate address
                // NOTE: In OpcodeList.txt the number of clock cycles is one less than the documentation.
                // This is because CheckBranch() adds one when a branch is taken, which in this case is always.
                case 0x80:
                    PC += _currentOP.Bytes;
                    CheckBranch(true, oper);
                    break;

                // BRK - force break (I)
                case 0x00:

                    // This is a software interrupt (IRQ).  These events happen in a specific order.

                    // Processor adds two to the current PC
                    PC += 2;

                    // Call IRQ routine
                    DoIRQ(0xfffe, true);

                    // Whether or not the decimal flag is cleared depends on the type of 6502 CPU.
                    // The CMOS 65C02 clears this flag but the NMOS 6502 does not.
                    if( _cpuType == e6502Type.CMOS )
                        DF = false;

                    break;
                // BVC - branch on overflow clear
                case 0x50:
                    PC += _currentOP.Bytes;
                    CheckBranch(!VF, oper);
                    break;

                // BVS - branch on overflow set
                case 0x70:
                    PC += _currentOP.Bytes;
                    CheckBranch(VF, oper);
                    break;

                // CLC - clear carry flag
                case 0x18:
                    CF = false;
                    PC += _currentOP.Bytes;
                    break;

                // CLD - clear decimal mode
                case 0xd8:
                    DF = false;
                    PC += _currentOP.Bytes;
                    break;

                // CLI - clear interrupt disable bit
                case 0x58:
                    IF = false;
                    PC += _currentOP.Bytes;
                    break;

                // CLV - clear overflow flag
                case 0xb8:
                    VF = false;
                    PC += _currentOP.Bytes;
                    break;

                // CMP - compare memory with accumulator (NZC)
                // CMP, CPX and CPY are unsigned comparisions
                case 0xc5:
                case 0xc9:
                case 0xc1:
                case 0xcd:
                case 0xd1:
                case 0xd2:
                case 0xd5:
                case 0xd9:
                case 0xdd:

                    byte temp = (byte)(A - oper);

                    CF = A >= (byte)oper;
                    ZF = A == (byte)oper;
                    NF = ((temp & 0x80) == 0x80);

                    PC += _currentOP.Bytes;
                    break;

                // CPX - compare memory and X (NZC)
                case 0xe0:
                case 0xe4:
                case 0xec:
                    temp = (byte)(X - oper);

                    CF = X >= (byte)oper;
                    ZF = X == (byte)oper;
                    NF = ((temp & 0x80) == 0x80);

                    PC += _currentOP.Bytes;
                    break;

                // CPY - compare memory and Y (NZC)
                case 0xc0:
                case 0xc4:
                case 0xcc:
                    temp = (byte)(Y - oper);

                    CF = Y >= (byte)oper;
                    ZF = Y == (byte)oper;
                    NF = ((temp & 0x80) == 0x80);

                    PC += _currentOP.Bytes;
                    break;

                // DEC - decrement memory by 1 (NZ)
                case 0xc6:
                case 0xce:
                case 0xd6:
                case 0xde:
                // added by 65C02
                case 0x3a:
                    result = oper - 1;

                    ZF = ((result & 0xff) == 0x00);
                    NF = ((result & 0x80) == 0x80);

                    SaveOperand(_currentOP.AddressMode, result);

                    PC += _currentOP.Bytes;
                    break;

                // DEX - decrement X by one (NZ)
                case 0xca:
                    result = X - 1;

                    ZF = ((result & 0xff) == 0x00);
                    NF = ((result & 0x80) == 0x80);

                    X = (byte)result;
                    PC += _currentOP.Bytes;
                    break;

                // DEY - decrement Y by one (NZ)
                case 0x88:
                    result = Y - 1;

                    ZF = ((result & 0xff) == 0x00);
                    NF = ((result & 0x80) == 0x80);

                    Y = (byte)result;
                    PC += _currentOP.Bytes;
                    break;

                // EOR - XOR memory with accumulator (NZ)
                case 0x41:
                case 0x45:
                case 0x49:
                case 0x4d:
                case 0x51:
                case 0x52:
                case 0x55:
                case 0x59:
                case 0x5d:
                    result = A ^ (byte)oper;

                    ZF = ((result & 0xff) == 0x00);
                    NF = ((result & 0x80) == 0x80);

                    A = (byte)result;

                    PC += _currentOP.Bytes;
                    break;

                // INC - increment memory by 1 (NZ)
                case 0xe6:
                case 0xee:
                case 0xf6:
                case 0xfe:
                // added by 65C02
                case 0x1a:
                    result = oper + 1;

                    ZF = ((result & 0xff) == 0x00);
                    NF = ((result & 0x80) == 0x80);

                    SaveOperand(_currentOP.AddressMode, result);

                    PC += _currentOP.Bytes;
                    break;

                // INX - increment X by one (NZ)
                case 0xe8:
                    result = X + 1;

                    ZF = ((result & 0xff) == 0x00);
                    NF = ((result & 0x80) == 0x80);

                    X = (byte)result;
                    PC += _currentOP.Bytes;
                    break;

                // INY - increment Y by one (NZ)
                case 0xc8:
                    result = Y + 1;

                    ZF = ((result & 0xff) == 0x00);
                    NF = ((result & 0x80) == 0x80);

                    Y = (byte)result;
                    PC += _currentOP.Bytes;
                    break;

                // JMP - jump to new location (two byte immediate)
                case 0x4c:
                case 0x6c:
                // added for 65C02
                case 0x7c:

                    if (_currentOP.AddressMode == AddressModes.Absolute)
                    {
                        PC = GetImmWord();
                    }
                    else if (_currentOP.AddressMode == AddressModes.Indirect)
                    {
                        PC = (ushort)(GetWordFromMemory(GetImmWord()));
                    }
                    else if( _currentOP.AddressMode == AddressModes.AbsoluteX)
                    {
                        PC = GetWordFromMemory((GetImmWord() + X));
                    }
                    else
                    {
                        throw new InvalidOperationException("This address mode is invalid with the JMP instruction");
                    }

                    // CMOS fixes a bug in this op code which results in an extra clock cycle
                    if (_currentOP.OpCode == 0x6c && _cpuType == e6502Type.CMOS)
                        _extraCycles++;
                    break;

                // JSR - jump to new location and save return address
                case 0x20:
                    // documentation says push PC+2 even though this is a 3 byte instruction
                    // When pulled via RTS 1 is added to the result
                    Push((ushort)(PC+2));
                    PC = GetImmWord();
                    break;

                // LDA - load accumulator with memory (NZ)
                case 0xa1:
                case 0xa5:
                case 0xa9:
                case 0xad:
                case 0xb1:
                case 0xb2:
                case 0xb5:
                case 0xb9:
                case 0xbd:
                    A = (byte)oper;

                    ZF = ((A & 0xff) == 0x00);
                    NF = ((A & 0x80) == 0x80);

                    PC += _currentOP.Bytes;
                    break;

                // LDX - load index X with memory (NZ)
                case 0xa2:
                case 0xa6:
                case 0xae:
                case 0xb6:
                case 0xbe:
                    X = (byte)oper;

                    ZF = ((X & 0xff) == 0x00);
                    NF = ((X & 0x80) == 0x80);

                    PC += _currentOP.Bytes;
                    break;

                // LDY - load index Y with memory (NZ)
                case 0xa0:
                case 0xa4:
                case 0xac:
                case 0xb4:
                case 0xbc:
                    Y = (byte)oper;

                    ZF = ((Y & 0xff) == 0x00);
                    NF = ((Y & 0x80) == 0x80);

                    PC += _currentOP.Bytes;
                    break;

                // LSR - shift right one bit (NZC)
                // 0 -> (76543210) -> C
                case 0x46:
                case 0x4a:
                case 0x4e:
                case 0x56:
                case 0x5e:

                    // On 65C02 (abs,X) takes one less clock cycle (but still add back 1 if page boundary crossed)
                    if (_currentOP.OpCode == 0x5e && _cpuType == e6502Type.CMOS)
                        _extraCycles--;

                    // shift bit 0 into carry
                    CF = ((oper & 0x01) == 0x01);

                    // shift operand
                    result = oper >> 1;

                    ZF = ((result & 0xff) == 0x00);
                    NF = ((result & 0x80) == 0x80);

                    SaveOperand(_currentOP.AddressMode, result);

                    PC += _currentOP.Bytes;
                    break;

                // NOP - no operation
                case 0xea:
                    PC += _currentOP.Bytes;
                    break;

                // ORA - OR memory with accumulator (NZ)
                case 0x01:
                case 0x05:
                case 0x09:
                case 0x0d:
                case 0x11:
                case 0x12:
                case 0x15:
                case 0x19:
                case 0x1d:
                    result = A | (byte)oper;

                    ZF = ((result & 0xff) == 0x00);
                    NF = ((result & 0x80) == 0x80);

                    A = (byte)result;

                    PC += _currentOP.Bytes;
                    break;

                // PHA - push accumulator on stack
                case 0x48:
                    Push(A);
                    PC += _currentOP.Bytes;
                    break;

                // PHP - push processor status on stack
                case 0x08:
                    int sr = 0x00;

                    if (NF) sr = sr | 0x80;
                    if (VF) sr = sr | 0x40;
                    sr = sr | 0x20; // bit 5 is always 1
                    sr = sr | 0x10; // bit 4 is always 1 for PHP
                    if (DF) sr = sr | 0x08;
                    if (IF) sr = sr | 0x04;
                    if (ZF) sr = sr | 0x02;
                    if (CF) sr = sr | 0x01;

                    Push((byte)sr);
                    PC += _currentOP.Bytes;
                    break;

                // PHX - push X on stack
                case 0xda:
                    Push(X);
                    PC += _currentOP.Bytes;
                    break;

                // PHY - push Y on stack
                case 0x5a:
                    Push(Y);
                    PC += _currentOP.Bytes;
                    break;

                // PLA - pull accumulator from stack (NZ)
                case 0x68:
                    A = PopByte();
                    NF = (A & 0x80) == 0x80;
                    ZF = (A & 0xff) == 0x00;
                    PC += _currentOP.Bytes;
                    break;

                // PLP - pull status from stack
                case 0x28:
                    sr = PopByte();

                    NF = (sr & 0x80) == 0x80;
                    VF = (sr & 0x40) == 0x40;
                    DF = (sr & 0x08) == 0x08;
                    IF = (sr & 0x04) == 0x04;
                    ZF = (sr & 0x02) == 0x02;
                    CF = (sr & 0x01) == 0x01;
                    PC += _currentOP.Bytes;
                    break;

                // PLX - pull X from stack (NZ)
                case 0xfa:
                    X = PopByte();
                    NF = (X & 0x80) == 0x80;
                    ZF = (X & 0xff) == 0x00;
                    PC += _currentOP.Bytes;
                    break;

                // PLY - pull Y from stack (NZ)
                case 0x7a:
                    Y = PopByte();
                    NF = (Y & 0x80) == 0x80;
                    ZF = (Y & 0xff) == 0x00;
                    PC += _currentOP.Bytes;
                    break;

                // RMBx - clear bit in memory (no flags)
                // Clear the zero page location of the specified bit
                // These instructions are only available on Rockwell and WDC 65C02 chips.
                case 0x07:
                case 0x17:
                case 0x27:
                case 0x37:
                case 0x47:
                case 0x57:
                case 0x67:
                case 0x77:

                    // upper nibble specifies the bit to check
                     check_bit = (byte)(_currentOP.OpCode >> 4);
                     check_value = 0x01;
                    for (int ii = 0; ii < check_bit; ii++)
                    {
                        check_value = (byte)(check_value << 1);
                    }
                    check_value = (byte)~check_value;
                    SaveOperand(_currentOP.AddressMode, oper & check_value);
                    PC += _currentOP.Bytes;
                    break;

                // SMBx - set bit in memory (no flags)
                // Set the zero page location of the specified bit
                // These instructions are only available on Rockwell and WDC 65C02 chips.
                case 0x87:
                case 0x97:
                case 0xa7:
                case 0xb7:
                case 0xc7:
                case 0xd7:
                case 0xe7:
                case 0xf7:

                    // upper nibble specifies the bit to check (but ignore bit 7)
                    check_bit = (byte)((_currentOP.OpCode & 0x70) >> 4);
                    check_value = 0x01;
                    for (int ii = 0; ii < check_bit; ii++)
                    {
                        check_value = (byte)(check_value << 1);
                    }
                    SaveOperand(_currentOP.AddressMode, oper | check_value);
                    PC += _currentOP.Bytes;
                    break;

                // ROL - rotate left one bit (NZC)
                // C <- 76543210 <- C
                case 0x26:
                case 0x2a:
                case 0x2e:
                case 0x36:
                case 0x3e:

                    // On 65C02 (abs,X) takes one less clock cycle (but still add back 1 if page boundary crossed)
                    if (_currentOP.OpCode == 0x3e && _cpuType == e6502Type.CMOS)
                        _extraCycles--;

                    // perserve existing cf value
                    bool old_cf = CF;

                    // shift bit 7 into carry flag
                    CF = (oper >= 0x80);

                    // shift operand
                    result = oper << 1;

                    // old carry flag goes to bit zero
                    if (old_cf) result = result | 0x01;

                    ZF = ((result & 0xff) == 0x00);
                    NF = ((result & 0x80) == 0x80);
                    SaveOperand(_currentOP.AddressMode, result);

                    PC += _currentOP.Bytes;
                    break;

                // ROR - rotate right one bit (NZC)
                // C -> 76543210 -> C
                case 0x66:
                case 0x6a:
                case 0x6e:
                case 0x76:
                case 0x7e:

                    // On 65C02 (abs,X) takes one less clock cycle (but still add back 1 if page boundary crossed)
                    if (_currentOP.OpCode == 0x7e && _cpuType == e6502Type.CMOS)
                        _extraCycles--;

                    // perserve existing cf value
                    old_cf = CF;

                    // shift bit 0 into carry flag
                    CF = (oper & 0x01) == 0x01;

                    // shift operand
                    result = oper >> 1;

                    // old carry flag goes to bit 7
                    if (old_cf) result = result | 0x80;

                    ZF = ((result & 0xff) == 0x00);
                    NF = ((result & 0x80) == 0x80);
                    SaveOperand(_currentOP.AddressMode, result);

                    PC += _currentOP.Bytes;
                    break;

                // RTI - return from interrupt
                case 0x40:
                    // pull SR
                    sr = PopByte();

                    NF = (sr & 0x80) == 0x80;
                    VF = (sr & 0x40) == 0x40;
                    DF = (sr & 0x08) == 0x08;
                    IF = (sr & 0x04) == 0x04;
                    ZF = (sr & 0x02) == 0x02;
                    CF = (sr & 0x01) == 0x01;

                    // pull PC
                    PC = PopWord();

                    break;

                // RTS - return from subroutine
                case 0x60:
                    PC = (ushort)(PopWord() + 1);
                    break;

                // SBC - subtract memory from accumulator with borrow (NZCV)
                // A-M-C -> A (NZCV)
                case 0xe1:
                case 0xe5:
                case 0xe9:
                case 0xed:
                case 0xf1:
                case 0xf2:
                case 0xf5:
                case 0xf9:
                case 0xfd:

                    if (DF)
                    {
                        result = HexToBCD(A) - HexToBCD((byte)oper);
                        if (!CF) result--;

                        CF = (result >= 0);

                        // BCD numbers wrap around when subtraction is negative
                        if (result < 0)
                            result += 100;
                        ZF = (result == 0);

                        A = BCDToHex(result);

                        // Unlike ZF and CF, the NF flag represents the MSB after conversion
                        // to BCD.
                        NF = (A > 0x7f);

                        // extra clock cycle on CMOS in decimal mode
                        if (_cpuType == e6502Type.CMOS)
                            _extraCycles++;
                    }
                    else
                    {
                        ADC((byte)~oper);
                    }
                    PC += _currentOP.Bytes;

                    break;

                // SEC - set carry flag
                case 0x38:
                    CF = true;
                    PC += _currentOP.Bytes;
                    break;

                // SED - set decimal mode
                case 0xf8:
                    DF = true;
                    PC += _currentOP.Bytes;
                    break;

                // SEI - set interrupt disable bit
                case 0x78:
                    IF = true;
                    PC += _currentOP.Bytes;
                    break;

                // STA - store accumulator in memory
                case 0x81:
                case 0x85:
                case 0x8d:
                case 0x91:
                case 0x92:
                case 0x95:
                case 0x99:
                case 0x9d:
                    SaveOperand(_currentOP.AddressMode, A);
                    PC += _currentOP.Bytes;
                    break;

                // STX - store X in memory
                case 0x86:
                case 0x8e:
                case 0x96:
                    SaveOperand(_currentOP.AddressMode, X);
                    PC += _currentOP.Bytes;
                    break;

                // STY - store Y in memory
                case 0x84:
                case 0x8c:
                case 0x94:
                    SaveOperand(_currentOP.AddressMode, Y);
                    PC += _currentOP.Bytes;
                    break;

                // STZ - Store zero
                case 0x64:
                case 0x74:
                case 0x9c:
                case 0x9e:
                    SaveOperand(_currentOP.AddressMode, 0);
                    PC += _currentOP.Bytes;
                    break;

                // TAX - transfer accumulator to X (NZ)
                case 0xaa:
                    X = A;
                    ZF = ((X & 0xff) == 0x00);
                    NF = ((X & 0x80) == 0x80);
                    PC += _currentOP.Bytes;
                    break;

                // TAY - transfer accumulator to Y (NZ)
                case 0xa8:
                    Y = A;
                    ZF = ((Y & 0xff) == 0x00);
                    NF = ((Y & 0x80) == 0x80);
                    PC += _currentOP.Bytes;
                    break;

                // TRB - test and reset bits (Z)
                // Perform bitwise AND between accumulator and contents of memory
                case 0x14:
                case 0x1c:
                    SaveOperand(_currentOP.AddressMode, ~A & oper);
                    ZF = (A & oper) == 0x00;
                    PC += _currentOP.Bytes;
                    break;

                // TSB - test and set bits (Z)
                // Perform bitwise AND between accumulator and contents of memory
                case 0x04:
                case 0x0c:
                    SaveOperand(_currentOP.AddressMode, A | oper);
                    ZF = (A & oper) == 0x00;
                    PC += _currentOP.Bytes;
                    break;

                // TSX - transfer SP to X (NZ)
                case 0xba:
                    X = SP;
                    ZF = ((X & 0xff) == 0x00);
                    NF = ((X & 0x80) == 0x80);
                    PC += _currentOP.Bytes;
                    break;

                // TXA - transfer X to A (NZ)
                case 0x8a:
                    A = X;
                    ZF = ((A & 0xff) == 0x00);
                    NF = ((A & 0x80) == 0x80);
                    PC += _currentOP.Bytes;
                    break;

                // TXS - transfer X to SP (no flags -- some online docs are incorrect)
                case 0x9a:
                    SP = X;
                    PC += _currentOP.Bytes;
                    break;

                // TYA - transfer Y to A (NZ)
                case 0x98:
                    A = Y;
                    ZF = ((A & 0xff) == 0x00);
                    NF = ((A & 0x80) == 0x80);
                    PC += _currentOP.Bytes;
                    break;

                // The original 6502 has undocumented and erratic behavior if
                // undocumented op codes are invoked.  The 65C02 on the other hand
                // are guaranteed to be NOPs although they vary in number of bytes
                // and cycle counts.  These NOPs are listed in the OpcodeList.txt file
                // so the proper number of clock cycles are used.
                //
                // Instructions STP (0xdb) and WAI (0xcb) will reach this case.
                // For now these are treated as a NOP.
                default:
                    PC += _currentOP.Bytes;
                    break;
            }
        }

        private int GetOperand(AddressModes mode)
        {
            int oper = 0;
            switch (mode)
            {
                // Accumulator mode uses the value in the accumulator
                case AddressModes.Accumulator:
                    oper = A;
                    break;

                // Retrieves the byte at the specified memory location
                case AddressModes.Absolute:
                    oper = memory[ GetImmWord() ];
                    break;

                // Indexed absolute retrieves the byte at the specified memory location
                case AddressModes.AbsoluteX:

                    ushort imm = GetImmWord();
                    ushort result = (ushort)(imm + X);

                    if (_currentOP.CheckPageBoundary)
                    {
                        if ((imm & 0xff00) != (result & 0xff00)) _extraCycles += 1;
                    }
                    oper = memory[ result ];
                    break;
                case AddressModes.AbsoluteY:
                    imm = GetImmWord();
                    result = (ushort)(imm + Y);

                    if (_currentOP.CheckPageBoundary)
                    {
                        if ((imm & 0xff00) != (result & 0xff00)) _extraCycles += 1;
                    }
                    oper = memory[result]; break;

                // Immediate mode uses the next byte in the instruction directly.
                case AddressModes.Immediate:
                    oper = GetImmByte();
                    break;

                // Implied or Implicit are single byte instructions that do not use
                // the next bytes for the operand.
                case AddressModes.Implied:
                    break;

                // Indirect mode uses the absolute address to get another address.
                // The immediate word is a memory location from which to retrieve
                // the 16 bit operand.
                case AddressModes.Indirect:
                    oper = GetWordFromMemory(GetImmWord());
                    break;

                // The indexed indirect modes uses the immediate byte rather than the
                // immediate word to get the memory location from which to retrieve
                // the 16 bit operand.  This is a combination of ZeroPage indexed and Indirect.
                case AddressModes.XIndirect:

                    /*
                     * 1) fetch immediate byte
                     * 2) add X to the byte
                     * 3) obtain word from this zero page address
                     * 4) return the byte located at the address specified by the word
                     */

                    oper = memory[GetWordFromMemory( (byte)(GetImmByte() + X))];
                    break;

                // The Indirect Indexed works a bit differently than above.
                // The Y register is added *after* the deferencing instead of before.
                case AddressModes.IndirectY:

                    /*
                        1) Fetch the address (word) at the immediate zero page location
                        2) Add Y to obtain the final target address
                        3)Load the byte at this address
                    */

                    ushort addr = GetWordFromMemory(GetImmByte());
                    oper = memory[addr + Y];

                    if (_currentOP.CheckPageBoundary)
                    {
                        if ((oper & 0xff00) != (addr & 0xff00)) _extraCycles++;
                    }
                    break;

                // Relative is used for branching, the immediate value is a
                // signed 8 bit value and used to offset the current PC.
                case AddressModes.Relative:
                    oper = SignExtend(GetImmByte());
                    break;

                // Zero Page mode is a fast way of accessing the first 256 bytes of memory.
                // Best programming practice is to place your variables in 0x00-0xff.
                // Retrieve the byte at the indicated memory location.
                case AddressModes.ZeroPage:
                    oper = memory[GetImmByte()];
                    break;
                case AddressModes.ZeroPageX:
                    oper = memory[(GetImmByte() + X) & 0xff];
                    break;
                case AddressModes.ZeroPageY:
                    oper = memory[(GetImmByte() + Y) & 0xff];
                    break;

                // this mode is from the 65C02 extended set
                // works like ZeroPageY when Y=0
                case AddressModes.ZeroPage0:
                    oper = memory[GetWordFromMemory((GetImmByte()) & 0xff)];
                    break;

                // for this mode do the same thing as ZeroPage
                case AddressModes.BranchExt:
                    oper = memory[GetImmByte()];
                    break;
                default:
                    break;
            }
            return oper;
        }

        private void SaveOperand(AddressModes mode, int data)
        {
            switch (mode)
            {
                // Accumulator mode uses the value in the accumulator
                case AddressModes.Accumulator:
                    A = (byte)data;
                    break;

                // Absolute mode retrieves the byte at the indicated memory location
                case AddressModes.Absolute:
                    memory[GetImmWord()] = (byte)data;
                    break;
                case AddressModes.AbsoluteX:
                    memory[GetImmWord() + X] = (byte)data;
                    break;
                case AddressModes.AbsoluteY:
                    memory[GetImmWord() + Y] = (byte)data;
                    break;

                // Immediate mode uses the next byte in the instruction directly.
                case AddressModes.Immediate:
                    throw new InvalidOperationException("Address mode " + mode.ToString() + " is not valid for this operation");

                // Implied or Implicit are single byte instructions that do not use
                // the next bytes for the operand.
                case AddressModes.Implied:
                    throw new InvalidOperationException("Address mode " + mode.ToString() + " is not valid for this operation");

                // Indirect mode uses the absolute address to get another address.
                // The immediate word is a memory location from which to retrieve
                // the 16 bit operand.
                case AddressModes.Indirect:
                    throw new InvalidOperationException("Address mode " + mode.ToString() + " is not valid for this operation");

                // The indexed indirect modes uses the immediate byte rather than the
                // immediate word to get the memory location from which to retrieve
                // the 16 bit operand.  This is a combination of ZeroPage indexed and Indirect.
                case AddressModes.XIndirect:
                    memory[GetWordFromMemory((byte)(GetImmByte() + X))] = (byte)data;
                    break;

                // The Indirect Indexed works a bit differently than above.
                // The Y register is added *after* the deferencing instead of before.
                case AddressModes.IndirectY:
                    memory[GetWordFromMemory(GetImmByte()) + Y] = (byte)data;
                    break;

                // Relative is used for branching, the immediate value is a
                // signed 8 bit value and used to offset the current PC.
                case AddressModes.Relative:
                    throw new InvalidOperationException("Address mode " + mode.ToString() + " is not valid for this operation");

                // Zero Page mode is a fast way of accessing the first 256 bytes of memory.
                // Best programming practice is to place your variables in 0x00-0xff.
                // Retrieve the byte at the indicated memory location.
                case AddressModes.ZeroPage:
                    memory[GetImmByte()] = (byte)data;
                    break;
                case AddressModes.ZeroPageX:
                    memory[(GetImmByte() + X) & 0xff] = (byte)data;
                    break;
                case AddressModes.ZeroPageY:
                    memory[(GetImmByte() + Y) & 0xff] = (byte)data;
                    break;
                case AddressModes.ZeroPage0:
                    memory[GetWordFromMemory((GetImmByte()) & 0xff)] = (byte)data;
                    break;

                // for this mode do the same thing as ZeroPage
                case AddressModes.BranchExt:
                    memory[GetImmByte()] = (byte)data;
                    break;

                default:
                    break;
            }
        }

        private ushort GetWordFromMemory(int address)
        {
            return (ushort)((memory[address + 1] << 8 | memory[address]) & 0xffff);
        }

        private ushort GetImmWord()
        {
            return (ushort)((memory[PC + 2] << 8 | memory[PC + 1]) & 0xffff);
        }

        private byte GetImmByte()
        {
            return memory[PC + 1];
        }

        private int SignExtend(int num)
        {
            if (num < 0x80)
                return num;
            else
                return (0xff << 8 | num) & 0xffff;
        }

        private void Push(byte data)
        {
            memory[(0x0100 | SP)] = data;
            SP--;
        }

        private void Push(ushort data)
        {
            // HI byte is in a higher address, LO byte is in the lower address
            memory[(0x0100 | SP)] = (byte)(data >> 8);
            memory[(0x0100 | (SP-1))] = (byte)(data & 0xff);
            SP -= 2;
        }

        private byte PopByte()
        {
            SP++;
            return memory[(0x0100 | SP)];
        }

        private ushort PopWord()
        {
            // HI byte is in a higher address, LO byte is in the lower address
            SP += 2;
            ushort idx = (ushort)(0x0100 | SP);
            return (ushort)((memory[idx] << 8 | memory[idx-1]) & 0xffff);
        }

        private void ADC(byte oper)
        {
            ushort answer = (ushort)(A + oper);
            if (CF) answer++;

            CF = (answer > 0xff);
            ZF = ((answer & 0xff) == 0x00);
            NF = (answer & 0x80) == 0x80;

            //ushort temp = (ushort)(~(A ^ oper) & (A ^ answer) & 0x80);
            VF = (~(A ^ oper) & (A ^ answer) & 0x80) != 0x00;

            A = (byte)answer;
        }

        private int HexToBCD(byte oper)
        {
            // validate input is valid packed BCD
            if (oper > 0x99)
                throw new InvalidOperationException("Invalid BCD number: " + oper.ToString("X2"));
            if ((oper & 0x0f) > 0x09)
                throw new InvalidOperationException("Invalid BCD number: " + oper.ToString("X2"));

            return ((oper >> 4) * 10) + (oper & 0x0f);
        }

        private byte BCDToHex(int result)
        {
            if (result > 0xff)
                throw new InvalidOperationException("Invalid BCD to hex number: " + result.ToString());

            if (result <= 9)
                return (byte)result;
            else
                return (byte)(((result / 10) << 4) + (result % 10));

        }

        private void DoIRQ(ushort vector)
        {
            DoIRQ(vector, false);
        }

        private void DoIRQ(ushort vector, bool isBRK)
        {
            // Push the MSB of the PC
            Push((byte)(PC >> 8));

            // Push the LSB of the PC
            Push((byte)(PC & 0xff));

            // Push the status register
            int sr = 0x00;
            if (NF) sr = sr | 0x80;
            if (VF) sr = sr | 0x40;

            sr = sr | 0x20;             // bit 5 is unused and always 1

            if(isBRK)
                sr = sr | 0x10;         // software interrupt (BRK) pushes B flag as 1
                                        // hardware interrupt pushes B flag as 0
            if (DF) sr = sr | 0x08;
            if (IF) sr = sr | 0x04;
            if (ZF) sr = sr | 0x02;
            if (CF) sr = sr | 0x01;

            Push((byte)sr);

            // set interrupt disable flag
            IF = true;

            // On 65C02, IRQ, NMI, and RESET also clear the D flag (but not on BRK) after pushing the status register.
            if (_cpuType == e6502Type.CMOS && !isBRK)
                DF = false;

            // load program counter with the interrupt vector
            PC = GetWordFromMemory(vector);
        }

        private void CheckBranch(bool flag, int oper)
        {
            if (flag)
            {
                // extra cycle on branch taken
                _extraCycles++;

                // extra cycle if branch destination is a different page than
                // the next instruction
                if ((PC & 0xff00) != ((PC + oper) & 0xff00))
                    _extraCycles++;

                PC += (ushort)oper;
            }

        }
    }
}

```

---
Tags: popularity-contest
---


title: Date within range?

text:
# Question
Title: Date within range?
Given a `MM/DD` date (`12/24`) and a start/end date range (`11/01 - 06/24`), figure out if the date is within the listed date span.

Date ranges can be sequential (`05/01 - 11/01`) or wrap around to the next year (`11/01 - 05/01`).

Examples:

* `12/24` is in `11/01 - 06/24` = True
* `06/24` is in `11/01 - 06/24` = True
* `06/24` is in `06/24 - 06/24` = True
* `06/24` is in `11/01 - 06/23` = False
* `07/24` is in `11/01 - 06/24` = False
* `07/24` is in `05/01 - 11/01` = True
* `07/24` is in `07/23 - 07/20` = True

Years do not mater. The date and/or date range is assumed to apply for any year past or future.

The end date will always be after the start date. If the end date is numerically less than the start date, we assume we are wrapping around to the next year.

The three input variables can be via any method (args, HTTP, stdin, etc..) and in any format (string, JSON, array, etc..)

Response can be `boolean` or any form of a yes/no/correct/etc.. string. Shortest code wins.

You cannot simply pass args to a built-in function.

# Answer
# Python, 31 bytes

```
lambda a,d,e:(e<d)>=(a<d)+(e<a)

```

Try it online!

Takes inputs as `MM/DD` in order `target, start, end`.
> 8 votes

# Answer
# Haskell, 28 bytes

```
(a%d)e=((e<a)/=(a<d))==(e<d)

```

Try it online!

Thanks to Leo for the trick of xor'ing the Booleans with `/=`.

---

# Haskell, 33 bytes

```
(a%d)e=show[e>=d,d>a,a>e]!!16>'a'

```

Try it online!
> 4 votes

# Answer
## JavaScript (ES6), ~~26~~ 20 bytes

```
(a,b,c)=>b>c^b>a^a>c

```

Output is `0` if `a` lies within the range `b`...`c`, `1` if not. Edit: Saved 6 bytes thanks to @nwellnhof.
> 4 votes

# Answer
# JavaScript (ES6), 31 bytes

Takes input as 3 strings in `MM/DD` format: *date*, *range\_from*, *range\_to*. Returns a boolean.

```
(a,b,c)=>!(b<c?a<b|a>c:a<b&a>c)

```

### Test cases

```
let f =

(a,b,c)=>!(b<c?a<b|a>c:a<b&a>c)

console.log(f('12/24','11/01','06/24')) // True
console.log(f('06/24','11/01','06/24')) // True
console.log(f('06/24','06/24','06/24')) // True
console.log(f('06/24','11/01','06/23')) // False
console.log(f('07/24','11/01','06/24')) // False
console.log(f('07/24','05/01','11/01')) // True
console.log(f('07/24','07/23','07/20')) // True
```
> 2 votes

# Answer
# Haskell, ~~38~~ 37 bytes

```
(b#e)d=(last$and:[or|b>e])[d>=b,d<=e]

```

Try it online!

*Saved 1 byte thanks to Laikoni*
> 2 votes

# Answer
# Perl 6, ~~33~~ ~~31~~ 29 bytes

```
{.[0]>.[2]??![>] $_!![<=] $_}

```

Try it online!

Takes a list containing start, date, and end.

-2 bytes thanks to Ramillies.
> 1 votes

# Answer
# Perl 5, 60 bytes

59 bytes of code + 1 `-a`

```
$F[1]=~s/./2/if$F[1]le$F[0];say($F[2]le$F[1]&&$F[2]ge$F[0])

```

Try it online!

Input: *`start_date end_date target_date`*
> 1 votes

---
Tags: code-golf, decision-problem, date
---


title: Implement QuickSort in BrainF***

text:
# Question
Title: Implement QuickSort in BrainF***
As discussed in the Lounge room on Stack Overflow:

> if you can't implement the Quicksort algorithm given en.wikipedia.org/wiki/Quicksort in any language you have minimal knowledge of, you might want to consider a different profession. @sbi

but SBI also noted that maybe BrainF\*** was an exception.

So, here's the puzzle/challenge: implement QuickSort in BrainF\***. The implementation must

* be interpreted by this and/or by the interpreter(s) here (for large scripts)
* implement the algorithm as described on Wikipedia - if possible as an in-place sort
* sort the following list of integers: \[0,4,6,4,2,3,9,2,3,6,5,3\] and print the result

# Answer
**BrainF\*** *(697 bytes)*

```
>>>>>>>>,[>,]<[[>>>+<<<-]>[<+>-]<+<]>[<<<<<<<<+>>>>>>>>-]<<<<<<<<[[>>+
>+>>+<<<<<-]>>[<<+>>-]<[>+>>+>>+<<<<<-]>[<+>-]>>>>[-<->]+<[>->+<<-[>>-
<<[-]]]>[<+>-]>[<<+>>-]<+<[->-<<[-]<[-]<<[-]<[[>+<-]<]>>[>]<+>>>>]>[-<
<+[-[>+<-]<-[>+<-]>>>>>>>>[<<<<<<<<+>>>>>>>>-]<<<<<<]<<[>>+<<-]>[>[>+>
>+<<<-]>[<+>-]>>>>>>[<+<+>>-]<[>+<-]<<<[>+>[<-]<[<]>>[<<+>[-]+>-]>-<<-
]>>[-]+<<<[->>+<<]>>[->-<<<<<[>+<-]<[>+<-]>>>>>>>>[<<<<<<<<+>>>>>>>>-]
<<]>[[-]<<<<<<[>>+>>>>>+<<<<<<<-]>>[<<+>>-]>>>>>[-[>>[<<<+>>>-]<[>+<-]
<-[>+<-]>]<<[[>>+<<-]<]]>]<<<<<<-]>[>>>>>>+<<<<<<-]<<[[>>>>>>>+<<<<<<<
-]>[<+>-]<+<]<[[>>>>>>>>+<<<<<<<<-]>>[<+>-]<+<<]>+>[<-<<[>+<-]<[<]>[[<
+>-]>]>>>[<<<<+>>>>-]<<[<+>-]>>]<[-<<+>>]>>>]<<<<<<]>>>>>>>>>>>[.>]

```

Below is an annotated version. In order to keep track of what was supposed to be happening while developing it, I used a comment notation that looks like this: `|a|b=0|c=A0|@d|A0|A1|```|`

<pre><code>|a| represents a named cell
|b=X| means we know the cell has value X, where X can be a constant or a variable name
|@d|  means the data pointer is in this cell
|A0|A1|```| is variable length array. (using ``` for ... because . is a command)
</code></pre>

The memory is laid out with a left-growing stack of partitions to process on the left, a scratch space in the center, and the array being sorted to the right. Array indexing is handled by moving a "data bus" containing the index and working space through the array. So for instance a 3-wide bus of `|i|data|0|A0|A1|A2`, will become `|A0|i-1|data|0|A1|A2` after shifting by one. The partitioning is performed by keeping the bus between the high and low elements.
Here's the full version:

<pre><code>Get input
>>>>>>>> ,[>,]                      |A0|A1|```|An|@0|
Count items
<[ [>>>+<<<-]>[<+>-]<+ <]  |@0|n|0|0|A0|A1|```
Make 8wide data bus w/ stack on left
>[<<<<<<<<+>>>>>>>>-]  ```|K1=n|K0=0|Z=0|a|b|c|d|e|@f|g|X=0|A0|A1|```
K1 and K0 represent the first index to process (I) and one past the last (J)
Check if still partitions to process
<<<<<<<<[
  Copy K1 to a&c via Z
  [>>+>+>>+<<<<<-]>>[<<+>>-] ```|K1=J|K0=I|@Z=0|a=J|b|c=J|d|e|f|g|X=0|A0|A1|```
  Copy K0 to b&d via Z
  <[>+>>+>>+<<<<<-]>[<+>-] ```|K1|K0|@Z=0|a=J|b=I|c=J|d=I|e|f|g|X=0|A0|A1|```
  Check if J minus I LE 1 : Subtract d from c
  >>>>[-<->]                    |a=J|b=I|c=JminusI|@d=0|e|f|g|
  d= c==0; e = c==1
  +<[>- >+<<-[>>-<<[-]]]        |a=J|b=I|@c=0|d=c==0|e=c==1|f|g|
  if d or e is 1 then J minus I LE 1: partition empty
  >[<+>-]>[<<+>>-]<+<      |a=J|b=I|@c=isEmpty|d=1|e=0|f|g|
  If Partition Empty;
  [->-                      |a=J|b=I|@c=0|d=0|c=0|f|g|
    pop K0: Zero it and copy the remaining stack right one; inc new K0
    <<[-]<[-]<<[-]<[[>+<-]<]>>[>]<+    ``|K1|@Z=0|a=J|b=I|c=0|d=0|e|f|g|
  Else:
  >>>>]>[-                   Z|a=J|b=I|c=isEmpty=0|@d=0|e|f|g|X|A0|A1
    Move Bus right I plus 1 frames; leaving first element to left
    <<+[ -[>+<-]<-[>+<-]>>>>>>>>      (dec J as we move)
      [<<<<<<<<+>>>>>>>>-]<<<<<< ]      Z|Ai|a=J|@b=0|c=0|d|e|f|g|X|Aq
    first element becomes pivot Ap; store in b
    <<[>>+<<-]            Z|@0|a=J|b=Ap|c=0|d|e|f|g|X|Aq
    While there are more elements (J GT 0);
    >[                    Z|0|@a=J|b=Ap|c=0|d|e|f|g|X|Aq
      copy Ap to e via c
      >[>+>>+<<<-]>[<+>-]  Z|0|a=J|b=Ap|@c=0|d=0|e=Ap|f|g|X=0|Aq
       copy Aq to g via X
      >>>>>>[<+<+>>-]<[>+<-] |c|d=0|e=Ap|f|g=Aq|@X=0|Aq
      Test Aq LT Ap:  while e; mark f; clear it if g
      <<<[ >+>[<-]<[<]           |@d=0|e|f=gLTe|g|
        if f: set d and e to 1; dec e and g
        >>[<<+>[-]+>-]>-<<-]
      set g to 1; if d: set f
      >>[-]+<<< [->>+<<]
      If Aq LT Ap move Aq across Bus
      >>[->- <<<<<[>+<-] <[>+<-] >>>>>>>>
        [<<<<<<<<+>>>>>>>>-] <<]  Z|0|Aq|a=J|b=Ap|c|d|e|@f=0|g=0|X=0|Ar
      Else Swap AQ w/ Aj: Build a 3wide shuttle holding J and Aq
      >[[-] <<<<<<[>>+>>>>>+<<<<<<<-]>>[<<+>>-] |@c=0|d|e|f=0|g=0|X=J|Aq|Ar|```
      If J then dec J
      >>>>>[-
        & While J shuttle right
        [>>[<<<+>>>-]<[>+<-]<-[>+<-]>] |a=J|b=Ap|c|d|e|f|Ar|```|Aj|g=0|@X=0|Aq|
        Leave Aq out there and bring Aj back
        <<[ [>>+<<-] < ]              |a=J|b=Ap|c|d|e|@f=0|g|X=0|Ar|```|Aj|Aq|
      ]>]
    Either bus moved or last element swapped; reduce J in either case
    <<<<<<-]                 |Aq|@a=0|b=Ap|c|d|e|f|g|X|Ar|```|
    Insert Ap To right of bus
    >[>>>>>>+<<<<<<-]        |Aq|a=0|@b=0|c|d|e|f|g|Ap|Ar|```|
    Move the bus back to original location tracking pivot location
    <<[ [>>>>>>>+<<<<<<<-]>[<+>-]<+ <]
    <[ [>>>>>>>>+<<<<<<<<-]>>[<+>-]<+ <<] |K1|K0|@Z=0|a=0|b=p|c|d|e|f|g|X|Ar|```
    if p is not 0:  put new partition on stack between K0 and K1:
    >+>[<-                                 |K1|K0|Z=0|@a=pEQ0|b=p|
      move K0 to Z; search for last K
      <<[>+<-] <[<]                           |@0|Kn|```|K1|0|Z=K0|a=0|b=p|
      shift left until return to 0 at K0;
      >[ [<+>-] >]                            |Kn|```|K1|0|@0|Z=K0|a=0|b=p|
      put p one left of there making it K1; restore K0 from Z;
      >>>[<<<<+>>>>-]<<[<+>-]                 |Kn|```|K2|K1=p|K0|@Z=0|a=0|b=0|
    else increment K0 (special case when first partition empty)
    >>]<[- <<+>>]
  >>>]  End if !empty
<<<<<<] End If Partitions remaining   @K1=0|K0=0|Z=0|a|b|c|d|e|f|g|X=0|A0|A1|```
Print the Results
>>>>>>>>>>>[.>]
</code></pre>
> 55 votes

# Answer
**brainfuck** *(178 bytes)*

Even if brainfuck is cumbersome, it helps to work with the grain of the language. Ask yourself "Do I have to store this value explicitly in a cell?" You can often gain speed and concision by doing something more subtle. And when the value is an array index (or an arbitrary natural number), it may not *fit* in a cell. Of course, you could just accept that as a limit of your program. But designing your program to handle large values will often make it better in other ways.

As usual, my first working version was twice as long as it needed to be—392 bytes. Numerous modifications and two or three major rewrites produced this comparatively graceful 178-byte version. (Though amusingly a linear-time sort is only 40 bytes.)

```
>+>>>>>,[>+>>,]>+[--[+<<<-]<[[<+>-]<[<[->[<<<+>>>>+<-]<<[>>+>[->]<<[<]
<-]>]>>>+<[[-]<[>+<-]<]>[[>>>]+<<<-<[<<[<<<]>>+>[>>>]<-]<<[<<<]>[>>[>>
>]<+<<[<<<]>-]]+<<<]]+[->>>]>>]>[brainfuck.org>>>]

```

The input values are spaced every three cells: for every (V)alue cell, there is a (L)abel cell (used for navigation) and one more cell for (S)cratch space. The overall layout of the array is

0 1 0 0 0 S V L S V L ... S V L 0 0 0 0 0 0 ...

Initially all the L cells are set to 1, to mark portions of the array that still need sorting. When we're done partitioning a subarray, we divide it into smaller subarrays by setting its pivot's L cell to 0, then locate the rightmost L cell that's still 1 and partition that subarray next. Oddly, this is all the bookkeeping we need to properly handle the recursive processing of subarrays. When all L cells have been zeroed, the whole array is sorted.

To partition a subarray, we pull its rightmost value into an S cell to act as pivot, and bring it (and the corresponding empty V cell) left, comparing it to each other value in the subarray and swapping as needed. At the end the pivot gets swapped back in, using the same swap code (which saves 50 bytes or so). During partitioning, two extra L cells are kept set to 0, to mark the two cells that may need to be swapped with each other; at the end of partitioning, the left 0 will fuse with the 0 to the left of the subarray, and the right 0 will end up marking its pivot. This process also leaves an extra 1 in the L cell to the right of the subarray; the main loop begins and ends at this cell.

```
>+>>>>>,[>+>>,]>+[                      set up; for each subarray:
    --[+<<<-]<[                         find the subarray; if it exists:
        [<+>-]<[                        S=pivot; while pivot is in S:
            <[                          if not at end of subarray
                ->[<<<+>>>>+<-]         move pivot left (and copy it)
                <<[>>+>[->]<<[<]<-]>    move value to S and compare with pivot
            ]>>>+<[[-]<[>+<-]<]>[       if pivot greater then set V=S; else:
                [>>>]+<<<-<[<<[<<<]>>+>[>>>]<-]     swap smaller value into V
                <<[<<<]>[>>[>>>]<+<<[<<<]>-]        swap S into its place
            ]+<<<                       end else and set S=1 for return path
        ]                               subarray done (pivot was swapped in)
    ]+[->>>]>>                          end "if subarray exists"; go to right
]>[brainfuck.org>>>]                    done sorting whole array; output it

```
> 13 votes

---
Tags: code-challenge, sorting, brainfuck
---