BrainFuck 6502 Interpreter in 135 bytes for the Apple ][
Michael
The only known bug (or lack of feature) is EOF isn't handled. I
didn't feel like "bloating" the code with a few more bytes :-)
Enjoy!
; Title: BrainFuck Interpreter
; File: BF6502A2.Ver2.s
; CPU: 6502
; Platform: Apple ][ //e
; By: Michael Pohoreski
; Date: Dec, 2008
; Description: 135 Byte Interpreter of BrainFuck (Version 2)
; License: BSD "Sharing is Caring!"
;
; Reference: http://en.wikipedia.org/wiki/Brainfuck
; > ++pData;
; < --pData;
; + ++(*pData);
; - --(*pData);
; . putchar(*pData);
; , *pData=getchar();
; [ while (*pData) {
; ] }
;
; Note: Select, Copy, then Shift-INS to paste into AppleWin, or
manually enter...
CALL-151
300:20 E2 F3 A9 06 85 3C A9 08 85 3D
30B:A0 00 84 40 A9 20 85 41
313:20 1D 03 20 C2 FC A0 00 F0 F6 // interpret
31D:B1 3C D0 02 68 68 // fetch
323:A2 07 DD 77 03 F0 04 CA 10 F8 60 // find op
32E:A9 03 48 BD 7F 03 48 18 B1 40 60 // exec
339:4C 11 FE // bf_next
33C:A5 40 D0 02 C6 41 C6 40 60 // bf_prev
345:69 02 18 // bf_inc
348:E9 00 A0 00 91 40 60 // bf_dec
34F:20 0C FD 29 7F 10 F4 // bf_in
356:09 80 4C ED FD // bf_out
35B:D0 19 20 C2 FC B1 3C C9 5D D0 F7 // bf_if
366:F0 0E A5 3C D0 02 C6 3D C6 3C B1 3C C9 5B D0 F2 60 // bf_end
377:2C 2E 5B 3C 5D 3E 2D 2B
37F:4E 55 5A 3B 65 38 47 44
FA62G
0 "++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<
+++++++++++++++.>.+++.------.--------.>+.>."
REM Hello World!
CALL 768
REM http://esolangs.org/wiki/Talk:Brainfuck
0 "++++++++[->-[->-[->-[-]<]<]<]"
REM -n/a-
CALL 768
0 ">++++++++[<++++++++++>-]<[>+>+<<-]>-.>-----.>"
REM OK
CALL 768
0 "+++++++++++++[>+++++++++>++++++++>++++++++>+++++<<<<-]>-.>.---.>++++
+.<----.<.>>+++++.<++++++++.>++++++.<----.----.<.-.>>+.----------.<<+
+.>>>-.<<<++++.>.+++++++.>..>------------------.<<-----.>.>.<-.<<+."
REM thematri...@yahoo.co.nz
CALL 768
0 "++++++++[->-[->-[->-[-]<]<]<]>++++++++[<++++++++++>-]<[>+>+<<-]
>-.>-----.>"
; Source
;pCode EQU $3C ; can't use $00C0, used by AppleSoft!
;pData EQU $FE ; shouldn't use $00DA, used by AppleSoft: LINENUMONERR
BFPC EQU $3C ; BFPC/pCode same as A1L/H
DATA EQU $40 ; DATA/pData same as A3L/H
HGR EQU $F3E2
HGR EQU $F3D8
COUT EQU $FDED
RDKEY EQU $FD0C
NXTA1_8 EQU $FCC2 ; standard entry point is NXTA1 = $FCBA
STOR_6 EQU $FE11 ; standard entry point is STOR = $FE0B
.ORG $300
; JSR HGR2 ; 20 D8 F3 ; If want 16K of data space... uncomment
JSR HGR ; 20 E2 F3 ; Clear 8K of data space
LDA #$06 ; A9 06 ; $0806 first Applesoft token
STA BFPC ; 85 3C
LDA #$08 ; A9 08 ; $0806 first Applesoft token
STA BFPC+1 ; 85 3D
LDY #$00 ; A0 00 ; use HGR page 1 for data ...
STY DATA ; 84 40
; UNDO optimization: HGR sets current HiRes page pointer, E6 = $20
LDA #$20 ; A9 20
STA DATA+1 ; 85 41
INTERPRET
JSR FETCH ; 20 1D 03
JSR NXTA1+8 ; 20 C2 FC
LDY #$00 ; A0 00 ; because COUT trashes Y
BEQ INTERPRET ; F0 F6 ; branch always
FETCH
LDA (BFPC),Y ; B1 3C
BNE FIND_OP ; D0 02
EXIT
PLA ; 68
PLA ; 68
; optimization: intentional-fall through : RTS after not finding
opcode
FIND_OP
LDX #$07 ; A2 07 ; 8 Instructions
.1
CMP OPCHAR,X ; DD 77 03 ; table of opcodes (char)
BEQ EXEC ; F0 04
DEX ; CA
BPL .1 ; 10 F8
; Note: (alternative) optimization: intentional fall-through: bad-
opcode so skip next instruction
; and fall into into INC_PC, but this is no longer stands compliant
-- as it
; skips two opcodes instead of one on a invalid opcode
RTS ; 60
EXEC
LDA #$03 ; A9 03 ; high byte of this code address
PHA ; 48
LDA OPFUNCPTR,X ; BD 7F 03 ; function pointer table (address)
PHA ; 48
CLC ; 18 ; optimization: common code
LDA (DATA),Y ; B1 40 ; optimization: common code
RTS ; 60 ; relative jsr
BF_NEXT
; optimization: use monitor rom STOR: BF_NEXT -> STOR+6 = $FE11
; INC DATA ; E6 E5
; BNE .1 ; D0 02
; INC DATA+1 ; E6 E6
;.1
; RTS ; 60
;FE11
; INC A3L ; E6 40
; BNE RTS5 ; D0
; INC A3H ; E6 41
;RTS5 RTS ; 60
JMP STOR+6 ; 4C 11 FE
BF_PREV
LDA DATA ; A5 40
BNE .1 ; D0 02
DEC DATA+1 ; C6 41
.1
DEC DATA ; C6 40
RTS ; 60
BF_INC
ADC #$02 ; 69 02 ; optimization: n+2-1 = n+1
CLC ; 18 ; optimization: fall-through into BF_INCDEC
BF_DEC
SBC #$00 ; E9 00
BF_INCDEC
LDY #$00 ; A0 00
STA (DATA),Y ; 91 40
RTS ; 60
BF_IN
JSR RDKEY ; 20 0C FD ; trashes Y
AND #$7F ; 29 7F ; convert 8-bit Apple Text to 7-bit ASCII
BPL BF_INCDEC ; 10 F4 ; optmization: BPL BF_INCDEC (10 F4)
BF_OUT
ORA #$80 ; 09 80 ; output Hi-Bit Apple Text !
JMP COUT ; 4C ED FD ; trashes A, Y
BF_IF ; if( !*pData ) pc = ']'
BNE .3 ; D0 19 ; optimization: BEQ .1, therefore BNE RTS
; RTS
; optimization: JSR INC_PC -> JSR NXTA1+8 = $FCC2
;INC_PC -> NXTA1+8 = $FCC2
; INC BFPC ; E6 3C
; BNE .1 ; D0 02
; INC BFPC+1 ; E6 3D
;.1
; RTS ; 60
.1
JSR NXTA1+8 ; 20 C2 FC
LDA (BFPC), Y ; B1 3C
CMP ']' ; C9 5D
BNE .1 ; D0 F7
.2
; optimization: intentional-fall through: remove RTS -- we got here
if BEQ, so exit...
BF_END ; if( !*pData ) pc = '['
BEQ .3 ; F0 0E ; optimization: BNE .1, therefore BEQ RTS
.1
LDA BFPC ; A5 3C
BNE .2 ; D0 02
DEC BFPC+1 ; C6 3D
.2
DEC BFPC ; C6 3C
LDA (BFPC),Y ; B1 3C
CMP '[' ; C9 5B
BNE .1 ; D0 F2
.3
RTS ; 60
OPCHAR DA ",.[<]>-+" ; sorted: 2B 2C 2D 2E 3C 3E 5B 5D
OPFUNCPTR ; sorted by usage: least commonly called to most frequently
called
DFB BF_IN -1 ; , 2C
DFB BF_OUT -1 ; . 2E
DFB BF_IF -1 ; [ 5B
DFB BF_PREV-1 ; < 3C
DFB BF_END -1 ; ] 5D
DFB BF_NEXT-1 ; > 3E
DFB BF_DEC -1 ; - 2D
DFB BF_INC -1 ; + 2B
// AppleWin symbols...
SYM BRAINFUCK = 300
SYM LASTVARS = 303
SYM INTERPRET = 313
SYM FETCH = 31D
SYM EXIT = 320
SYM FIND_OP = 323
SYM EXEC = 32E
SYM BF_NEXT = 339 // > 3E
SYM BF_NEXT_1 = 33B
SYM BF_PREV = 33C // < 3C
SYM BF_PREV_1 = 342
SYM BF_INC = 345 // + 2B
SYM BF_DEC = 348 // - 2D
SYM BF_INCDEC = 34A
SYM BF_IN = 34F // , 2C
SYM BF_OUT = 356 // . 2E
SYM BF_IF = 35B // [ 5B
SYM BF_IF_1 = 35D
SYM BF_IF_2 = 35E
SYM BF_END = 366 // ] 5D
SYM BF_END_1 = 368
SYM BF_END_2 = 36E
SYM BF_END_3 = 376
SYM NXTA1_8 = FCC2
SYM STOR_6 = FE11
SYM OPCHAR = 377
SYM OPFUNCPTR = 37F
Notes:
Apple Specific Optimizations:
- use F800 rom code :-)
1) INC_PC -> NXTA1+8 = $FCC2
INC BFPC ; E6 3C
BNE .1 ; D0 02
INC BFPC+1 ; E6 3D
.1
RTS ; 60
FE11
INC A3L ; E6 40
BNE RTS5 ; D0
INC A3H ; E6 41
RTS5 RTS ; 60
2) BF_NEXT -> STOR+6 = $FE11
INC PDATA ; E6 40
BNE .1 ; D0 02
INC PDATA+1 ; E6 41
.1
RTS ; 60
FE11
INC A3L ; E6 40
BNE RTS5 ; D0
INC A3H ; E6 41
RTS5 RTS ; 60
aiia...@gmail.com
> Let me know if you find corrections, or optimizations :)
http://en.wikipedia.org/wiki/Brainfuck#Hello_World.21
ugggh you're crazy...
source code for "hello world" is:
++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++
++++++++++++.>.+++.------.--------.>+.>.
yikes
lyricalnanoha
On Thu, 18 Dec 2008, Michael wrote:
> Let me know if you find corrections, or optimizations :)
>
> The only known bug (or lack of feature) is EOF isn't handled. I
> didn't feel like "bloating" the code with a few more bytes :-)
>
> Enjoy!
Wow, and I thought I'd gotten it small with 192 bytes for a 65C02. o.O
-uso.
Michael
The 195 byte version is impressive! Good Job!
ARGH! The prev version didn't handle nested brackets. Here is the 187
byte version that does.
If I do another version, I could add matching bracket detection, and
EOF support. We'll see. A program is never done...
; Title: BrainFuck Interpreter
; File: BF6502A2.Ver3.s
: CPU: 6502
; Platform: Apple ][ //e
; By: Michael Pohoreski
; Date: Dec, 2008
; Description: 187 Byte Interpreter of BrainFuck (Version 3 - nested
if/then support)
; License: BSD "Sharing is Caring!"
;
; http://groups.google.com/group/comp.emulators.apple2/browse_thread/thread/3a6dc92aa0d9a040
;
; Definition:
; http://en.wikipedia.org/wiki/Brainfuck
;
; Reference Tests
; http://esoteric.sange.fi/brainfuck/bf-source/prog/tests.b
;
; Examples
; http://esoteric.sange.fi/brainfuck/bf-source/prog/
; http://esolangs.org/wiki/Brainfuck#Implementations
; http://www.muppetlabs.com/~breadbox/bf/standards.html
; http://software.xfx.net/utilities/vbbfck/index.php
;
; http://nesdev.parodius.com/6502.txt
;
; > ++pData;
; < --pData;
; + ++(*pData);
; - --(*pData);
; . putchar(*pData);
; , *pData=getchar();
; [ while (*pData) { // if( *pData == 0 ), pCode = find_same_depth
( ']' );
; ] } // if( *pData != 0 ), pCode = find_same_depth
( '[' );
;
; Note: Select then Shift-INS to paste into AppleWin, or manually
enter...
CALL-151
300: 20 D8 F3 20 E2 F3
306: A0 00 84 3C 84 40 84 EE
30E: A9 60 85 3D A9 20 85 41
316: B1 3C F0 1F 20 24 03 20 C2 FC A0 00 F0 F2
324: A2 07 D5 F0 F0 04 CA 10 F9 60
32E: A9 03 48 B5 F8 48 18 B1 40 60
338: 4C 11 FE
33B: A5 40 D0 02 C6 41 C6 40 60
344: 69 02 18
347: E9 00
349: A0 00 91 40 60
34E: 20 0C FD 29 7F 10 F4
355: 09 80 4C ED FD
35A: E6 EE B1 40 D0 E3 A5 EE 85 EF
364: 20 C2 FC B1 3C C9 5B D0 04 E6 EF D0 F3
371: C9 5D D0 EF A5 EE C5 EF F0 C8 C6 EF 18 90 E4
380: C6 EE B1 40 F0 BD A5 EE 85 EF
38A: A5 3C D0 02 C6 3D
390: C6 3C B1 3C C9 5D D0 04 C6 EF D0 EE
39C: C9 5B D0 EA A5 EE C5 EF F0 9D E6 EF 18 90 DF
F0: 2C 2E 5B 3C 5D 3E 2D 2B
F8: 4D 54 59 3A 7F 37 46 43
// AppleWin symbols...
SYM CUR_DEPTH = EE
SYM NUM_BRACKET = EF
SYM BRAINFUCK = 300
SYM FETCH = 316
SYM INTERPRET = 324
SYM FIND_OP = 326
SYM EXEC = 32E
SYM EXIT = 337
SYM BF_NEXT = 338 // > 3E
SYM BF_PREV = 33B // < 3C
SYM BF_PREV_1 = 341
SYM EXIT_2 = 343
SYM BF_INC = 344 // + 2B
SYM BF_DEC = 347 // - 2D
SYM STORE_DATA = 349
SYM BF_IN = 34E // , 2C
SYM BF_OUT = 355 // . 2E
SYM BF_IF = 35A // [ 5B
SYM BF_IF_2 = 364
SYM BF_IF_4 = 371
SYM BF_FI = 380 // ] 5D
SYM BF_FI_2 = 38A
SYM BF_FI_3 = 390
SYM BF_FI_4 = 39C
SYM NXTA1_8 = FCC2
SYM STOR_6 = FE11
SYM OPCODE = F0
SYM OPFUNCPTR = F8
;
=====================================================================
; Examples
0 "++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<
+++++++++++++++.>.+++.------.--------.>+.>."
REM Hello World!
CALL -151
6000<806.900M
FA62G
CALL 768
REM http://esolangs.org/wiki/Talk:Brainfuck
0 "++++++++[->-[->-[->-[-]<]<]<]"
CALL-151
6000<806.900M
FA62G
CALL 768
REM -n/a-
0 ">++++++++[<++++++++++>-]<[>+>+<<-]>-.>-----.>"
REM OK
CALL 768
0 "+++++++++++++[>+++++++++>++++++++>++++++++>+++++<<<<-]>-.>.---.>++++
+.<----.<.>>+++++.<++++++++.>++++++.<----.----.<.-.>>+.----------.<<+
+.>>>-.<<<++++.>.+++++++.>..>------------------.<<-----.>.>.<-.<<+."
REM thematri...@yahoo.co.nz
CALL 768
0 "++++++++[->-[->-[->-[-]<]<]<]>++++++++[<++++++++++>-]<[>+>+<<-]
>-.>-----.>"
CALL -151
6000<806.900M
FA62G
CALL 768
0 "++++[>++++++<-]>[>+++++>+++++++<<-]>>++++<[[>[[>>+<<-]<]>>>-]>-[>+>
+<<-]>]+++++[>+++++++<<++>-]>.<<."
REM Need 32K data!!!
REM Prints #
CALL -151
2000:0
2001<2000.BFFEM
FA62G
CALL 768
;
=====================================================================
; Source
OPCODE .EQ $F0
OPFUNCPTR .EQ $F8
CUR_DEPTH .EQ $EE; // current nested depth
NUM_BRACKET .EQ $EF; // depth to find[]
;STACK_L .EQ $0800
;STACK_H .EQ $0900
NXTA1_8 .EQ $FCC2 ; standard entry point is NXTA1 = $FCBA
STOR_8 .EQ $FE11 ; standard entry point is STOR = $FE0B
;pCode .EQ $3C ; can't use $00C0, used by AppleSoft!
;pData .EQ $FE ; shouldn't use $00DA, used by AppleSoft: LINENUMONERR
BFPC .EQ $3C ; BFPC/pCode same as A1L/H
DATA .EQ $40 ; DATA/pData same as A3L/H
HGR2 .EQ $F3E2
HGR .EQ $F3D8
COUT .EQ $FDED
RDKEY .EQ $FD0C
NXTA1 .EQ $FCBA
NXTA1_8 .EQ $FCC2
STOR .EQ $FE0B
STOR_6 .EQ $FE11
CLRTEXT .EQ $C050
SETTEXT .EQ $C051
.ORG $300
; The old start address of $0806 = first Applesoft token
; STA CLRTEXT ; 8D 50 C0 ; // C051 or C050
JSR HGR2 ; 20 D8 F3 ; Clear top 8K of data
JSR HGR ; 20 E2 F3 ; Clear bot 8K of data
LDY #$00 ; A0 00 ;
STY BFPC ; 84 3C ;
STY DATA ; 84 40 ;
STY CUR_DEPTH ; 84 EE ;
; ; Optional: $08/$10 for small code ($0800..$0FFF =
2K) / large data ($1000..$BFFF = 44K)
; ; DEFAULT: $60/$20 for big code ($6000..$BFFF =
24K) / medium data ($2000..$5FFF = 16K)
LDA #$60 ; A9 60 ; Start CODE buffer
STA BFPC+1 ; 85 3D ;
LDA #$20 ; A9 20 ; Start DATA buffer
STA DATA+1 ; 85 41 ;
FETCH
LDA (BFPC),Y ; B1 3C ;
BEQ EXIT ; F0 1F ;
JSR INTERPRET ; 20 24 03 ;
JSR NXTA1+8 ; 20 C2 FC ;
LDY #$00 ; A0 00 ; because COUT trashes Y
BEQ FETCH ; F0 F2 ; branch always
INTERPRET
LDX #$07 ; A2 07 ; 8 Instructions
FIND_OP
CMP OPCODE,X ; D5 F0 ; table of opcodes (char)
BEQ EXEC ; F0 03 ;
DEX ; CA ;
BPL FIND_OP ; 10 F9 ;
RTS ; 60 ;
EXEC
LDA #$03 ; A9 03 ; high byte of this code address
PHA ; 48 ;
LDA OPFUNCPTR,X ; B5 F8 ; function pointer table (address)
PHA ; 48 ;
CLC ; 18 ; optimization: common code
LDA (DATA),Y ; B1 40 ; optimization: common code
EXIT
RTS ; 60 ; 1) exit to caller, 2) relative jsr to our bf_*(),
or 3) exit our bf_*()
BF_NEXT
JMP STOR+6 ; 4C 11 FE ;
BF_PREV
LDA DATA ; A5 40 ;
BNE .1 ; D0 02 ;
DEC DATA+1 ; C6 41 ;
.1 DEC DATA ; C6 40 ;
EXIT_2
RTS ; 60 ;
BF_INC
ADC #$02 ; 69 02 ; optimization: n+2-1 = n+1
CLC ; 18 ; optimization: fall-through into BF_INCDEC
BF_DEC
SBC #$00 ; E9 00 ;
STORE_DATA
LDY #$00 ; A0 00 ;
STA (DATA),Y ; 91 40 ;
RTS ; 60 ;
BF_IN
JSR RDKEY ; 20 0C FD ; trashes Y
AND #$7F ; 29 7F ; convert 8-bit Apple Text to 7-bit ASCII
BPL STORE_DATA ; 10 F4 ;
; CMP #$0D ; C9 0D ;
; BNE STORE_DATA ; D0 F5 ;
; LDA #$0A ; A9 0A ;
; BPL STORE_DATA ; 10 F2 ; optmization: BPL BF_INCDEC (10 F4)
BF_OUT
ORA #$80 ; 09 80 ; output Hi-Bit Apple Text !
; CMP #$8A ; C9 8A ;
; BNE .1 ; D0 02 ;
; LDA #8D ; A9 8D ; map newline 0A to 8D
.1 JMP COUT ; 4C ED FD ; trashes A, Y
BF_IF ; ; if( *pData == 0 ) pc = ']'
INC CUR_DEPTH ; E6 EE ; *** depth++
LDA (DATA),Y ; B1 40 ; optimization: common code
BNE EXIT_2 ; D0 E3 ; optimization: BEQ .1, therefore BNE RTS
LDA CUR_DEPTH ; A5 EE ; match_depth = depth
STA NUM_BRACKET ; 85 EF ;
.2
JSR NXTA1+8 ; 20 C2 FC ; ***
LDA (BFPC), Y ; B1 3C ;
CMP '[' ; C9 5B ; ***
BNE .4 ; D0 04 ;
INC NUM_BRACKET ; E6 EF ; *** inc stack
BNE .2 ; D0 F3 ;
.4
CMP ']' ; C9 5D ; ***
BNE .2 ; D0 EF ;
LDA CUR_DEPTH ; A5 EE ;
CMP NUM_BRACKET ; C5 EF ;
BEQ EXIT_2 ; F0 C8 ;
DEC NUM_BRACKET ; C6 EF ; *** dec stack
CLC ; 18 ;
BCC .2 ; 90 E4 ;
BF_FI ; ; if( *pData != 0 ) pc = '['
DEC CUR_DEPTH ; C6 EE ; depth--
LDA (DATA),Y ; B1 40 ;
BEQ EXIT_2 ; F0 BD ; optimization: BNE .1, therefore BEQ RTS
LDA CUR_DEPTH ; A5 EE ; match_depth = depth
STA NUM_BRACKET ; 85 EF ;
.2
LDA BFPC ; A5 3C ;
BNE .3 ; D0 02 ;
DEC BFPC+1 ; C6 3D ;
.3
DEC BFPC ; C6 3C ;
LDA (BFPC),Y ; B1 3C ;
CMP ']' ; C9 5D ;
BNE .4 ; D0 04 ;
DEC NUM_BRACKET ; C6 EF ; dec stack
BNE .2 ; D0 EE ;
.4
CMP '[' ; C9 5B ;
BNE .2 ; D0 EA ;
LDA CUR_DEPTH ; A5 EE ;
CMP NUM_BRACKET ; C5 EF ;
BEQ EXIT_2 ; F0 9D ;
INC NUM_BRACKET ; E6 EF ; dec stack
CLC ; 18 ;
BCC .2 ; 90 DF ;
.ORG $F0
OPCODE DA ",.[<]>-+" ; sorted: 2B 2C 2D 2E 3C 3E 5B 5D
Toinet
impressed by both his coding and the language.
The use of the HGR memory space for data and its initialization are
great ideas ;-)
A 65c816 version could be a good starting point for people I know who
discover the IIgs...
antoine
Babar de Saint Cyr
> A 65c816 version could be a good starting point for people I know who
> discover the IIgs...
>
> antoine
We hope you do!
Et bonne année 2009 :D
Babar
Toinet
wrote:
Oh m'sieur Babar !
Bonne année,
antoine
calib...@freenet.de
>
> http://en.wikipedia.org/wiki/Brainfuck#Hello_World.21
>
> ugggh you're crazy...
Visit this:
http://esoteric.voxelperfect.net/wiki/Main_Page
And click on "Browsing the joke language list" for more mischief.
Those guys (and possibly gals) have way too much time at their
hands to create that stuff.
The other link ("Browsing the language list") isn't necessarily
better,
though. The language "0x29A" isn't named as obvious as "Brainfuck"
but does exactly the same. Its author calls the paradigm
"dysfunctional
programming"...
bye
Marcus
Michael AppleWin Debugger Dev
All code and examples are now in GitHub:
* https://github.com/Michaelangel007/brainfuck6502
No new functionality, but did a massive cleanup with comments and switched assembler directives to Merlin.
My hope is one day the native AppleWin assembler will be able to read and assemble this natively. (Still a few years off as I have a few games to ship first, but we'll see.)
wss...@gmail.com
peter....@gmail.com
I have it down to 159 bytes.
Michael AppleWin Debugger Dev
> I checked - the source doesn't compile because of a missing symbol (BF_END instead of BF_FI). HGR and HGR2 are also duplicated but reversed in the second case.
> I have it down to 159 bytes.
Michael AppleWin Debugger Dev
> Now what I want to see is a 6502 emulator written in Brainfuck running on an Apple II.
peter....@gmail.com
>
> Whoa! Damn, nice! Are you doing parenthesis matching?!
https://github.com/peterferrie/brainfuck6502
I changed the assembler to ACME for cross-compile support, but it's close enough to Merlin that you could change it back.
There is one horrible trick in there - to save a byte, the find_op doesn't stop immediately on finding a match. Instead, it continues to search for what becomes the low byte of the function pointer. So... you must make sure that the address doesn't match any of the tokens. I had to move some of the routines around to avoid exactly that.
A 65C02 version would be even smaller, because it could use the JMP (addr,X) instead of PHA style.
Michael AppleWin Debugger Dev
You wouldn't happen to be the same Peter Ferrie that wrote the 2-sided 16-sector version of Prince of Persia by chance??
* http://pferrie.host22.com/misc/lowlevel14.htm
Michael AppleWin Debugger Dev
> >
> > Whoa! Damn, nice! Are you doing parenthesis matching?!
>
> Of course - I based it on your original code! :-)
> https://github.com/peterferrie/brainfuck6502
Hell yeah, source code :-)
Now you got me curious to see what the hell you did to get it down to 159 bytes ...
Now this is just brilliant ... always loops 7 times but saves 1 byte
FIND_OP
CMP OPCODE,X ; D5 F0 ; table of opcodes (char)
PHA ; 48 ;
PHA ; 48 ;
NEXT
DEX ; CA ;
BPL FIND_OP ; 10 F3 ;
EXIT
Ah! You shadowed to the X register. I knew I should of used that extra register. :-)
LDA (DATA),Y ; B1 40 ; optimization: common code
RTS ; 60 ; 1) exit to caller,
INX ; E8 ; optimization: n+2-1 = n+1
INX ; E8 ; optimization: n+2-1 = n+1
BF_DEC
DEX ; CA ;
TXA ; 8A ;
Another very nice hack to save 2 bytes.
BF_IN
JSR RDKEY ; 20 0C FD ; trashes Y
EOR #$80 ; 49 80 ; convert 7-bit ASCII
; convert 8-bit Apple
BPL STORE_DATA ; 10 13 ; always for input
All in all, absolutely beautiful optimizations! Damn impressive. 3L33T assembly coding skills. :-)
> I changed the assembler to ACME for cross-compile support, but it's close enough to Merlin that you could change it back.
> There is one horrible trick in there - to save a byte, the find_op doesn't stop immediately on finding a match. Instead, it continues to search for what becomes the low byte of the function pointer. So... you must make sure that the address doesn't match any of the tokens. I had to move some of the routines around to avoid exactly that.
> A 65C02 version would be even smaller, because it could use the JMP (addr,X) instead of PHA style.
Absolutely beautiful hack / optimizations.
Steve Nickolas
-uso.
peter....@gmail.com
> >
> > * http://pferrie.host22.com/misc/lowlevel14.htm
> >
>
> I'm pretty sure he's one and the same. ;)
(http://pferrie.host22.com/misc/lowlevel15.htm)
and the 1-sided Conan
(http://pferrie.host22.com/misc/lowlevel16.htm).
:-)
...among other things.
> If I'm reading this correctly, you always loop 7 times?
> > A 65C02 version would be even smaller, because it could use the JMP (addr,X) instead of PHA style.
I considered running the code from the stack instead, which introduces some potential savings, but the risk of corruption is significant.
wss...@gmail.com
a CPU emulator in Brainfuck (*BF from now on). However I have now
probably wasted too much time on this so I will stop with an explanation
and a small amount of sample code. Obviously there could be errors in the
supplied code. I haven't tested it, but I think the idea is sound.
The fundamental idea is that you have to carry the emulated CPU
state with you as you move around the BF array. Assume
a simple machine as below:
I) The Machine
256 bytes memory
Registers
A: 8 bits
PC: 8 bits
Flags
Carry
Zero
Opcode Instructions
0 put
1 get
2 clc
3 sec
4 asl
5 rol
6 lsr
7 ror
8 stz <abs>
9 lda <imm>
10 lda <abs>
11 add <abs>
12 adc <imm>
13 sbc <abs>
14 sbc <imm>
15 cmp <abs>
16 cmp <imm>
17 bra <rel>
18 bcc <rel>
19 bcs <rel>
20 beq <rel>
21 bne <rel>
2) The representation in BF
The machine state, consisting of the registers and flags, along with
some storage for each instruction and operand and a few scratch locations
(one of which is quite important) will be duplicated throughout the
BF array, once for each memory cell of the emulated CPU.
So the BF array will be organized like this:
|Mem|Inst|Arg|AddrScr|MathScr|Xbit|C|N|A|PC|
|Mem|Inst|Arg|AddrScr|MathScr|Xbit|C|N|A|PC|
|Mem|Inst|Arg|AddrScr|MathScr|Xbit|C|N|A|PC|
|Mem|Inst|Arg|AddrScr|MathScr|Xbit|C|N|A|PC|
...
Where each 'Mem' is a byte of emulated CPU memory, and the rest
is the machine state of the emulated CPU. 'AddrScr', 'MathScr', and
'Xbit' are the scratch locations. 'Xbit' is important because it
is used to control execution of emulated CPU instructions in addition
to other use as a scratch location.
3) The BF code
3a) Decode and Dispatch
If we assume that we begin the execution of an emulated CPU instruction
with the BF data pointer pointing at an emulated CPU memory cell ('Mem'
above), then the emulated instruction decoding and dispatch can
look something like this:
>[-] clear Inst
>>[-]<<< clear AddrScr
[->+>>+<<<] copy Mem to Inst and AddrScr
>>>[-<<<+>>>] copy AddrScr back to Mem
>>[-]+<<<< set Xbit and return to inst
At this point we have copied the opcode into the Inst location, ready
to decode. Xbit has been set to 1 to signal that no instruction
emulation code has yet been executed.
The decode and dispatch looks like this:
[-[-[-
...
]>>>>[instruction #2]<<<<
]>>>>[instruction #1]<<<<
]>>>>[instruction #0]<<<<
'Inst' is decremented repeatedly until it is zero. When it is
zero, the code at the end of the loop will execute. That code
advances to Xbit and, if Xbit is not zero, the emulation code
for the decoded instruction will execute, otherwise (if Xbit is
zero), the emulation code will be skipped and the current level
of the decode loop will be exited. As Xbit is still zero, the
enclosing level of the decode loop will also be exited until
the entire decode construct has been exited.
Obviously it is critically important that each instruction
emulation routine set Xbit to zero to ensure that no other
emulation routine will execute.
3b) Sample instruction emulation
Here are implementations of the simplest instructions. The BF
code for each implementation fits in to the slots labeled
"instruction #0", "instruction #1", etc. above. Each instruction
emulation routine assumes that it begins with the BF data pointer
pointing at Xbit, as above.
PUT : output the contents of A
>>>.<<<[-] advance to A, output it, return to Xbit, clear Xbit
GET : input a byte to A
>>>,<<<[-] as with PUT
CLC : clear Carry flag
>[-]<[-] advance to C, clear C, return to Xbit, clear Xbit.
SEC: set Carry flag
>[-]+<[-] advance to C, clear C, increment C, return to Xbit
clear Xbit.
ASL: shift A left, high bit to Carry flag
(This routine adds A to itself. It is written to avoid
the assumption that a BF cell will wrap backwards from
0 to $FF)
<[-]<[-]>>>[-]+>> clear AddrScr & MathScr, set C to 1
[-<<<<+<+>>>>>] copy A to AddrScr & MathScr
<<<<< move to AddrScr
[->+ decr AddrScr, incr MathScr
[>>-<<]>>+<< increment C if MathScr overflows
(always increment C, but first decrement
it - for net zero - unless MathScr is
zero, which is the overflow condition)
<] loop until done
>>>- decrement C (so it is now either 0 or 1)
<<[->>>>+<<<<] copy MathScr to A
>[-] clear Xbit
ROL: rotate A left, C to low bit, high bit to C
(very similar to ASL)
[-]>[-<+>] copy C to Xbit, clearing C
<<[-]<[-]>>>+>> clear AddrScr & MathScr, set C to 1
[-<<<<+<+>>>>>] copy A to AddrScr & MathScr
<<<<< move to AddrScr
[->+ decr AddrScr, incr MathScr
[>>-<<]>>+<< increment C if MathScr overflows
(always increment C, but first decrement
it - for net zero - unless MathScr is
zero, which is the overflow condition)
<] loop until done
>>>- decrement C (so it is now either 0 or 1)
<<[->>>>+<<<<] copy MathScr to A
>[->>>+<<<] clear Xbit, adding it to A
LSR: shift A right, low bit to Carry flag
(This routine increments a scratch register once for
every two decrements of A, with a check to catch the
low bit and copy to C)
<[-]>>[-]>> clear MathScr & C, move to A
[- decr A
[+<<<<->>+>>] if A=0, incr A, decr MathScr, set C
-<<<<+>>>>] decr A, incr MathScr
<<<[-] clear Xbit
ROR: shift A right, C to high bit, low bit to C
(very similar to LSR)
[-]>[-<+>] copy C to Xbit, clearing C
<<[-]>>>> clear MathScr & move to A
[- decr A
[+<<<<->>+>>] if A=0, incr A, decr MathScr, set C
-<<<<+>>>>] decr A, incr MathScr
<<<[->>> if Xbit set, clear it and add 128 to A
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
<<<]
3c) Altering PC
After an instruction has been emulated, it is necessary to move on
to the next instruction. Assuming that the PC is merely advanced to
the next location, this can be done by simply copying the entire
machine state to the next 'block' and then looping back to the
dispatch code. In order to make sure the core emulation loop
continues as desired, the BF data pointer can be left pointing at
one of the scratch locations containing a guaranteed non-zero value.
Code to do this can be something like the following, assuming the
data pointer is pointed at Xbit (as it should be following the
decode/dispatch loop):
>>>>>>>>>>>>>> advance to PC of next 'block'
[-]<[-]<[-]<[-]< clear all locations except 'Mem'
<[->>>>>>>>>>+<<<<<<<<<<] copy A
<[->>>>>>>>>>+<<<<<<<<<<] copy N
<[->>>>>>>>>>+<<<<<<<<<<] copy C
>>>> advance to 'Mem' of next block, ready to
execute the opcode contained therein.
I decided that I had wasted enough time before getting complete
sample code for branches, so consider it an exercise for the
reader. It will probably require copying the machine state
successively until the destination is reached.
peter....@gmail.com
It also supports 256 levels of nesting reliably now.
peter....@gmail.com
This version also avoids the hack with the placement of the routines - the find_op loop exits immediately on a match, just like it should.
peter....@gmail.com
> a CPU emulator in Brainfuck (*BF from now on). However I have now
> probably wasted too much time on this so I will stop with an explanation
> and a small amount of sample code. Obviously there could be errors in the
> supplied code. I haven't tested it, but I think the idea is sound.
I'm still trying to comprehend this. :-)
Writing the interpreter was much easier by comparison.
Michael AppleWin Debugger Dev
mver...@libero.it
It's time to go back to BinHex!
Marco Verpelli
wss...@gmail.com
However, I would really prefer a version that didn't rely on Applesoft, even though that's one of the clever bits.
peter....@gmail.com
> However, I would really prefer a version that didn't rely on Applesoft, even though that's one of the clever bits.
You can clear the buffer yourself (and must do so for larger arrays). The other calls are strictly monitor calls which are present in Integer Basic, too.
A universal buffer init would cost about 18 bytes.