Discussion:
BrainFuck 6502 Interpreter in 135 bytes for the Apple ][
(too old to reply)
Michael
2008-12-19 07:54:17 UTC
Permalink
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!




; 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 ***@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
a***@gmail.com
2008-12-20 00:00:39 UTC
Permalink
On Dec 18, 11:54 pm, Michael <***@gmail.com> wrote:
> 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
c***@freenet.de
2009-01-02 15:12:38 UTC
Permalink
On Dec 20 2008, 1:00 am, ***@gmail.com wrote:
>
> 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
lyricalnanoha
2008-12-20 13:53:57 UTC
Permalink
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
2008-12-25 20:40:49 UTC
Permalink
On Dec 20, 5:53 am, lyricalnanoha
<***@usotsuki.hoshinet.org> wrote:
> 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.

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 ***@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
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
Toinet
2008-12-26 05:15:23 UTC
Permalink
I have never heard of BrainFuck before Michael's post and I am quite
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
2009-01-01 16:16:38 UTC
Permalink
Toinet a écrit :
> 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
2009-01-01 21:12:56 UTC
Permalink
On 1 jan, 17:16, Babar de Saint Cyr <***@free.fr>
wrote:
> Toinet a écrit :
>
> > 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

Oh m'sieur Babar !

Bonne année,

antoine
Michael AppleWin Debugger Dev
2015-07-14 15:54:30 UTC
Permalink
Necro'ing an old thread.

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.)
w***@gmail.com
2015-07-15 03:34:31 UTC
Permalink
Am Mittwoch, 15. Juli 2015 00:54:31 UTC+9 schrieb Michael AppleWin Debugger Dev:
> Necro'ing an old thread.
>
> 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.)

Now what I want to see is a 6502 emulator written in Brainfuck running on an Apple II.
Michael AppleWin Debugger Dev
2015-07-16 15:30:45 UTC
Permalink
On Tuesday, July 14, 2015 at 8:34:32 PM UTC-7, ***@gmail.com wrote:

> Now what I want to see is a 6502 emulator written in Brainfuck running on an Apple II.

Haha, that's a pure masochist put sick (ingenious) thought. That would have _horrible_ emulation speed though!
w***@gmail.com
2015-07-18 08:33:53 UTC
Permalink
Am Freitag, 17. Juli 2015 00:30:45 UTC+9 schrieb Michael AppleWin Debugger Dev:
> On Tuesday, July 14, 2015 at 8:34:32 PM UTC-7, ***@gmail.com wrote:
>
> > Now what I want to see is a 6502 emulator written in Brainfuck running on an Apple II.
>
> Haha, that's a pure masochist put sick (ingenious) thought. That would have _horrible_ emulation speed though!


I decided to think about this and I have come up with a way to write
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 PC of current block to PC of next block
<[->>>>>>>>>>+<<<<<<<<<<] 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.
p***@gmail.com
2015-07-28 19:49:02 UTC
Permalink
> I decided to think about this and I have come up with a way to write
> 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.
p***@gmail.com
2015-07-15 23:17:07 UTC
Permalink
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
2015-07-16 14:43:06 UTC
Permalink
On Wednesday, July 15, 2015 at 4:17:08 PM UTC-7, ***@gmail.com wrote:
> 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.

Good catch! Fixed!

> I have it down to 159 bytes.

Whoa! Damn, nice! Are you doing parenthesis matching?!
p***@gmail.com
2015-07-16 15:40:31 UTC
Permalink
> > I have it down to 159 bytes.
>
> Whoa! Damn, nice! Are you doing parenthesis matching?!

Of course - I based it on your original code! :-)
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
2015-07-17 20:12:20 UTC
Permalink
On Thursday, July 16, 2015 at 8:40:32 AM UTC-7, ***@gmail.com wrote:

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
Steve Nickolas
2015-07-18 02:48:56 UTC
Permalink
On Fri, 17 Jul 2015, Michael AppleWin Debugger Dev wrote:

> On Thursday, July 16, 2015 at 8:40:32 AM UTC-7, ***@gmail.com wrote:
>
> 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
>

I'm pretty sure he's one and the same. ;)

-uso.
p***@gmail.com
2015-07-18 06:55:20 UTC
Permalink
> > 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
> >
>
> I'm pretty sure he's one and the same. ;)

Yes, that's me. Also the 6-sided Toy Shop
(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?

Yes, so I traded performance for size.

> > A 65C02 version would be even smaller, because it could use the JMP (addr,X) instead of PHA style.

> Ironically I was looking at this a couple of days ago wondering if I could shrink the dispatch down ... I hardly ever remember any of the "new" 65C02 upcodes but that is an interesting idea! I'm not sure if you the ASL would be smaller then the PHA, PHA, RTS stuff though ...

I came to the same conclusion. While it's a nice instruction, there's the loss of 8 bytes to store the high part of the address.
I considered running the code from the stack instead, which introduces some potential savings, but the risk of corruption is significant.
Michael AppleWin Debugger Dev
2015-07-17 20:40:00 UTC
Permalink
On Thursday, July 16, 2015 at 8:40:32 AM UTC-7, ***@gmail.com wrote:
> > > I have it down to 159 bytes.
> >
> > Whoa! Damn, nice! Are you doing parenthesis matching?!
>
> Of course - I based it on your original code! :-)

HA-HA! Nice!

> 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)
BNE NEXT ; D0 06 ; ignore non-tokens, allows for comments
LDA #$03 ; A9 03 ; high byte of this code address
PHA ; 48 ;
LDA OPFUNCPTR,X ; B5 F8 ; function pointer table (address)
PHA ; 48 ;
NEXT
DEX ; CA ;
BPL FIND_OP ; 10 F3 ;
LDA (DATA),Y ; B1 40 ; optimization: common code
TAX ; AA ; cache value
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
TAX ; AA ; cache value
EXIT
RTS ; 60 ; 1) exit to caller,

BF_INC
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
BF_OUT
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.

Is ACME really that popular? I probably should look into cross-compiling one of these days and stop hand-assembling :-)

> 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.

Haha, that's a really nasty hack, er, clever optimization. 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.

Ironically I was looking at this a couple of days ago wondering if I could shrink the dispatch down ... I hardly ever remember any of the "new" 65C02 upcodes but that is an interesting idea! I'm not sure if you the ASL would be smaller then the PHA, PHA, RTS stuff though ...

Absolutely beautiful hack / optimizations.
p***@gmail.com
2015-07-28 00:01:29 UTC
Permalink
I just got it down to 152 bytes, but with a performance hit - when ']' is seen, the counter is no longer checked, it simply performs the regular search for the matching '[', and lets that one do the check.
It also supports 256 levels of nesting reliably now.
p***@gmail.com
2015-07-28 19:47:59 UTC
Permalink
> I just got it down to 152 bytes

Ooh, now 144 bytes. Once I realised that cur_depth is redundant (the value is arbitrary, the only requirement is that the value before matches the value after), it was easy.
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.
Michael AppleWin Debugger Dev
2015-07-30 15:33:46 UTC
Permalink
On Tuesday, July 28, 2015 at 12:48:01 PM UTC-7, ***@gmail.com wrote:
> > I just got it down to 152 bytes
>
> Ooh, now 144 bytes. Once I realised that cur_depth is redundant (the value is arbitrary, the only requirement is that the value before matches the value after), it was easy.
> 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.

I haven't had tikme to study your changes, but 144 bytes ... Damn! _Only_ 4 chars above a tweet! Although I don't think you can tweet binary data, go figure :-)
m***@libero.it
2015-07-30 16:01:44 UTC
Permalink
tweet binary data

It's time to go back to BinHex!

Marco Verpelli
w***@gmail.com
2015-07-31 13:13:25 UTC
Permalink
Am Mittwoch, 29. Juli 2015 04:48:01 UTC+9 schrieb ***@gmail.com:
> > I just got it down to 152 bytes
>
> Ooh, now 144 bytes. Once I realised that cur_depth is redundant (the value is arbitrary, the only requirement is that the value before matches the value after), it was easy.
> 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.

I've finally gone and read your code. It's quite clever.
However, I would really prefer a version that didn't rely on Applesoft, even though that's one of the clever bits.
p***@gmail.com
2015-07-31 15:55:50 UTC
Permalink
> I've finally gone and read your code. It's quite clever.
> However, I would really prefer a version that didn't rely on Applesoft, even though that's one of the clever bits.

The only AppleSoft dependencies are for intially clearing the buffer. That part was from Michael's original code, so I can't take any credit for that.
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.
Loading...