| | Quiss
Registered: Nov 2016 Posts: 52 |
Computing the length of 6502 instructions
Had to share this. Imagine you're working on a decruncher, deinterleaver, code generator, or something along those lines. You probably, so far, had to pull in a 256 byte table that encodes the length of each 6502 instruction. Sure, that table compresses well, but it seems a bit wasteful, nonetheless.
The below code snippet instead computes the length of an instruction (opcode in A) on the fly. It's based on code from JBW (from the 90s), which 0xF and I spent some time shortening, and making aware of illegal opcodes:
LDX #$00 // LENGTH
CMP #$20 // JSR
BEQ LEN2
AND #$9D
BEQ LEN0 // RTI / RTS
ASL
CMP #$12
BEQ LEN1
AND #$1A
CMP #$10
BCC LEN1
BEQ LEN0
LEN2
INX
LEN1
INX
LEN0
Note that it treats BRK as a single-byte instruction, and for four of the KILs ($12, $32, $52, $72) it says they are two bytes. But the rest is by the book. |
|
| | Krill
Registered: Apr 2002 Posts: 3098 |
That's pretty cool. :)
"Sure, that table compresses well, but it seems a bit wasteful, nonetheless." - Wondering about actual difference after compression.
With separately crunched opcode and operand streams, the idioms change, such that "LDA #0 : TAX" becomes a bad idea suddenly, and using "LDA #0 : LDX #0" instead pays off.
The re-interleaving code isn't subject to this, of course, but that length table is rather compressible indeed.
Anyways, nice one! =) |
| | ChristopherJam
Registered: Aug 2004 Posts: 1424 |
Oh, nice. I'll have to see how that compares to the 256 byte table that BitPickler uses - I already chose the latter over a 32 byte table of 256 bitpairs; the bigger table compressed better than the smaller table+bitpair extraction code.
Your code could be handy for a limited workspace decruncher, too.
Those exceptions are quite a nuisance; I did do a bit of experimentation with a less accurate length function, to see if the compression losses resulting from using an inaccurate deinterleave were less than the space saved on the reinterleaver, but no dice.
(Oh, and FWIW, the compressed table occupies about 41 bytes of my recrunch of artefacts) |
| | Sparta
Registered: Feb 2017 Posts: 52 |
Nice Quiss! :) This may be the best compression of the 256-byte table. |
| | Krill
Registered: Apr 2002 Posts: 3098 |
Quoting SpartaNice Quiss! :) This may be the best compression of the 256-byte table. Makes me wonder whether crunchers like CJam's automagically nix out unreferenced table indices for even better compression. =) |
| | Martin Piper
Registered: Nov 2007 Posts: 739 |
Does anyone have the table as a raw binary to download? |
| | Krill
Registered: Apr 2002 Posts: 3098 |
Quoting Martin PiperDoes anyone have the table as a raw binary to download? Oddly specific request.
Does text do? 0, // 00, brk
1, // 01, ora (zp,x)
0, // 02, jam
1, // 03, slo (zp,x)
0, // 04, nop
1, // 05, ora zp
1, // 06, asl zp
1, // 07, slo zp
0, // 08, php
1, // 09, ora #imm
0, // 0a, asl
1, // 0b, anc #imm
2, // 0c, nop abs
2, // 0d, ora abs
2, // 0e, asl abs
2, // 0f, slo abs
1, // 10, bpl rel
1, // 11, ora (zp),y
0, // 12, jam
1, // 13, slo (zp),y
1, // 14, nop zp,x
1, // 15, ora zp,x
1, // 16, asl zp,x
1, // 17, slo zp,x
0, // 18, clc
2, // 19, ora abs,y
0, // 1a, nop
2, // 1b, slo abs,y
2, // 1c, nop abs,x
2, // 1d, ora abs,x
2, // 1e, asl abs,x
2, // 1f, slo abs,x
2, // 20, jsr abs
1, // 21, and (zp,x)
0, // 22, jam
1, // 23, rla (zp,x)
1, // 24, bit zp
1, // 25, and zp
1, // 26, rol zp
1, // 27, rla zp
0, // 28, plp
1, // 29, and #imm
0, // 2a, rol
1, // 2b, anc #imm
2, // 2c, bit abs
2, // 2d, and abs
2, // 2e, rol abs
2, // 2f, rla abs
1, // 30, bmi rel
1, // 31, and (zp),y
0, // 32, jam
1, // 33, rla (zp),y
1, // 34, nop zp,x
1, // 35, and zp,x
1, // 36, rol zp,x
1, // 37, rla zp,x
0, // 38, sec
2, // 39, and abs,y
0, // 3a, nop
1, // 3b, rla abs,y
2, // 3c, nop abs,x
2, // 3d, and abs,x
2, // 3e, rol abs,x
2, // 3f, rla abs,x
0, // 40, rti
1, // 41, eor (zp,x)
0, // 42, jam
1, // 43, sre (zp,x)
1, // 44, nop zp
1, // 45, eor zp
1, // 46, lsr zp
1, // 47, sre zp
0, // 48, pha
1, // 49, eor #imm
0, // 4a, lsr
1, // 4b, asl #imm
2, // 4c, jmp abs
2, // 4d, eor abs
2, // 4e, lsr abs
2, // 4f, sre abs
1, // 50, bvs rel
1, // 51, eor (zp),y
0, // 52, jam
1, // 53, sre (zp),y
1, // 54, nop zp,x
1, // 55, eor zp,x
1, // 56, lsr zp,x
1, // 57, sre zp,x
0, // 58, cli
2, // 59, eor abs,y
0, // 5a, nop
2, // 5b, sre abs,y
2, // 5c, nop abs,x
2, // 5d, eor abs,x
2, // 5e, lsr abs,x
2, // 5f, sre abs,x
0, // 60, rts
1, // 61, adc (zp,x)
0, // 62, jam
1, // 63, rra (zp,x)
1, // 64, nop zp
1, // 65, adc zp
1, // 66, ror zp
1, // 67, rra zp
0, // 68, pla
1, // 69, adc #imm
0, // 6a, ror
1, // 6b, arr #imm
2, // 6c, jmp (abs)
2, // 6d, adc abs
2, // 6e, ror abs
2, // 6f, rra abs
1, // 70, bvs rel
1, // 71, adc (zp),y
0, // 72, jam
1, // 73, rra (zp),y
1, // 74, nop zp,x
1, // 75, adc zp,x
1, // 76, ror zp,x
1, // 77, rra zp,x
0, // 78, sei
2, // 79, adc abs,y
0, // 7a, nop
2, // 7b, rra abs,y
2, // 7c, nop abs,x
2, // 7d, adc abs,x
2, // 7e, ror abs,x
2, // 7f, rra abs,x
1, // 80, nop #imm
1, // 81, sta (zp,x)
1, // 82, nop #imm
1, // 83, sax (zp,x)
1, // 84, sty zp
1, // 85, sta zp
1, // 86, stx zp
1, // 87, sax zp
0, // 88, dey
1, // 89, nop #imm
0, // 8a, txa
1, // 8b, xaa #imm
2, // 8c, sty abs
2, // 8d, sta abs
2, // 8e, stx abs
2, // 8f, sax abs
1, // 90, bcc rel
1, // 91, sta (zp),y
0, // 92, jam
1, // 93, ahx (zp),y
1, // 94, sty zp,x
1, // 95, sta zp,x
1, // 96, stx zp,y
1, // 97, sax zp,y
0, // 98, tya
2, // 99, sta abs,y
0, // 9a, txs
2, // 9b, tas abs,y
2, // 9c, shf abs,x
2, // 9d, sta abs,x
2, // 9e, shx abs,y
2, // 9f, ahx abs,y
1, // a0, ldy #imm
1, // a1, lda (zp,x)
1, // a2, ldx #imm
1, // a3, lax (zp,x)
1, // a4, ldy zp
1, // a5, lda zp
1, // a6, ldx zp
1, // a7, lax zp
0, // a8, tay
1, // a9, lda #imm
0, // aa, tax
1, // ab, lax #imm
2, // ac, ldy abs
2, // ad, lda abs
2, // ae, ldx abs
2, // af, lax abs
1, // b0, bcs rel
1, // b1, lda (zp),y
0, // b2, jam
1, // b3, lax (zp),y
1, // b4, ldy zp,x
1, // b5, lda zp,x
1, // b6, ldx zp,y
1, // b7, lax zp,y
0, // b8, clv
2, // b9, lda abs,y
0, // ba, tsx
2, // bb, las abs,y
2, // bc, ldy abs,x
2, // bd, lda abs,x
2, // be, ldx abs,y
2, // bf, lax abs,y
1, // c0, cpy #imm
1, // c1, cmp (zp,x)
1, // c2, nop #imm
1, // c3, dcp (zp,x)
1, // c4, cpy zp
1, // c5, cmp zp
1, // c6, dec zp
1, // c7, dcp zp
0, // c8, iny
1, // c9, cmp #imm
0, // ca, dex
1, // cb, sbx #imm
2, // cc, cpy abs
2, // cd, cmp abs
2, // ce, dec abs
2, // cf, dcp abs
1, // d0, bne rel
1, // d1, cmp (zp),y
0, // d2, jam
1, // d3, dcp (zp),y
1, // d4, nop zp,x
1, // d5, cmp zp,x
1, // d6, dec zp,x
1, // d7, dcp zp,x
0, // d8, cld
2, // d9, cmp abs,y
0, // da, nop
2, // db, dcp abs,y
2, // dc, nop abs,x
2, // dd, cmp abs,x
2, // de, dec abs,x
2, // df, dcp abs,x
1, // e0, cpx #imm
1, // e1, sbc (zp,x)
1, // e2, nop #imm
1, // e3, isc (zp,x)
1, // e4, cpx zp
1, // e5, sbc zp
1, // e6, inc zp
1, // e7, isc zp
0, // e8, inx
1, // e9, sbc #imm
0, // ea, nop
1, // eb, sbc #imm
2, // ec, cpx abs
2, // ed, sbc abs
2, // ee, inc abs
2, // ef, isc abs
1, // f0, beq rel
1, // f1, sbc (zp),y
0, // f2, jam
1, // f3, isc (zp),y
1, // f4, nop zp,x
1, // f5, sbc zp,x
1, // f6, inc zp,x
1, // f7, isc zp,x
0, // f8, sed
2, // f9, sbc abs,y
0, // fa, nop
2, // fb, isc abs,y
2, // fc, nop abs,x
2, // fd, sbc abs,x
2, // fe, inc abs,x
2, // ff, isc abs,x |
| | cadaver
Registered: Feb 2002 Posts: 1163 |
Very nice! This is definitely going to the loadable code relocator in Steel Ranger 2 :) Previously I had a shitload more code to decode lengths from a 32-byte packed table. |
| | Krill
Registered: Apr 2002 Posts: 3098 |
Quoting cadavera shitload more code to decode lengths from a 32-byte packed table. You encode [0,1,2] in a single bit? :-O |
| | ChristopherJam
Registered: Aug 2004 Posts: 1424 |
Haha no, I just can't do arithmetic apparently.
Ok, a 41-bytes-compressed table to replace a 64 byte thing makes more sense now :D
(hmm, someone could try encoding it in base 3?) |
| | Krill
Registered: Apr 2002 Posts: 3098 |
Quoting ChristopherJam(hmm, someone could try encoding it in base 3?) Have fun optimising the shit out of your divmod routine! =) |
... 2 posts hidden. Click here to view all posts.... |
Previous - 1 | 2 - Next | |