at the REF link there is the "source" or the base that produce the bf ( automatically produced). Direct link
einstein1969
BrainF*** Interpreter in Batch
Moderator: DosItHelp
-
einstein1969
- Expert
- Posts: 960
- Joined: 15 Jun 2012 13:16
- Location: Italy, Rome
Re: BrainF*** Interpreter in Batch
@Aacini
at the REF link there is the "source" or the base that produce the bf ( automatically produced). Direct link
einstein1969
at the REF link there is the "source" or the base that produce the bf ( automatically produced). Direct link
einstein1969
Re: BrainF*** Interpreter in Batch
einstein1969 wrote:I want identify this code in the hanoi.bf It's possible?Code: Select all
macro delay()
{
var a = 200;
while (a) {
var b = 200;
while (b) {
var c = 100;
while (c) c -= 1;
b -= 1;
}
a -= 1;
}
}
There is not necessity to DELAY...
einstein1969
The delay macro can be easily identified in hanoi.bp parsed file created by my BF interpreter Version 2.1, because it is the only part in such file that have the number 200:
Code: Select all
;[629] +.>>>>>>]<<]<<<<<<+++++++++++++.<<[-]+++++++++++++++++++++++++++++++++++++++
"code[13371]=. 1"
"code[13372]=> 6"
"code[13373]=] 13367"
"code[13374]=< 2"
"code[13375]=] 13335"
"code[13376]=< 6"
"code[13377]=+ 13"
"code[13378]=. 1"
"code[13379]=< 2" // var a
"code[13380]== 200" // = 200;
"code[13381]=[ 13393" // while (a) {
;[630] ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
;[631] ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
;[632] +++++++++[>[-]++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
"code[13382]=> 1" // var b
"code[13383]== 200" // = 200;
"code[13384]=[ 13390" // while (b) {
;[633] ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
;[634] ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++[>[-]+++++++++
"code[13385]=> 1" // var c
"code[13386]== 100" // = 100;
"code[13387]== 0" // while (c) c -= 1;
;[635] ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
;[636] +++++++++++++++[-]<-]<-]<<<<<]<<<<+>>>>[-]>[-]<<<<<[->>>>>+<<<<<]>>>>>[-<+<<
"code[13388]=< 1" // b
"code[13389]=- 1" // -= 1;
"code[13390]=] 13384" // }
"code[13391]=< 1" // a
"code[13392]=- 1" // -= 1;
"code[13393]=] 13381" // }
"code[13394]=< 5"
"code[13395]=] 5168"
In order to eliminate this macro from the original code, modify such lines this way:
- Change line 629 from this:
Code: Select all
+.>>>>>>]<<]<<<<<<+++++++++++++.<<[-]+++++++++++++++++++++++++++++++++++++++
to this:Code: Select all
+.>>>>>>]<<]<<<<<<+++++++++++++.<< - Delete lines 630 - 635
- Change line 636 from this:
Code: Select all
+++++++++++++++[-]<-]<-]<<<<<]<<<<+>>>>[-]>[-]<<<<<[->>>>>+<<<<<]>>>>>[-<+<<
to this:Code: Select all
<<<<<]<<<<+>>>>[-]>[-]<<<<<[->>>>>+<<<<<]>>>>>[-<+<<
Antonio
-
einstein1969
- Expert
- Posts: 960
- Joined: 15 Jun 2012 13:16
- Location: Italy, Rome
Re: BrainF*** Interpreter in Batch
Thanks Antonio!
I have correct the Hanoi.bf
This is the corrected version. Hanoi_Mod.bf
I try to create an VT100 emulator (see thread). But I have difficult to realize external. I think that internal is more easy.
einstein1969
I have correct the Hanoi.bf
This is the corrected version. Hanoi_Mod.bf
I try to create an VT100 emulator (see thread). But I have difficult to realize external. I think that internal is more easy.
einstein1969
-
einstein1969
- Expert
- Posts: 960
- Joined: 15 Jun 2012 13:16
- Location: Italy, Rome
Re: BrainF*** Interpreter in Batch
New version = new test.
Triangle.bf
===========
the time of execute of dbenham version 3.0 for small files is impressive!
For the Hanoi have choice the modified version Hanoi_mod.bf . Then have misured, when output a line of char, the time elapsed.
Hanoi_mod.bf
============
the version 3.0 of Aacini is now very fast for big files. But is not fastest.
Await the version of dbenham with PAGING!!!
einstein1969
Triangle.bf
===========
Extract Subs:
-------------
Aacini 3.0 12:46:39,07 - 12:46:39,65 Elapsed 58 cs
Parse:
------
JWinslow23 about 100 cs
dbenham 2.0 17:52:39,35 - 17:52:39,59 elapsed 24 cs
Aacini 2.1 17:41:46,55 - 17:41:48,98 elapsed 243 cs
dbenham 2.0 optimized about 25 cs
JWinslow23 optimized about 180 cs
Aacini 3.0 12:46:39,65 - 12:46:40,16 Elapsed 51 cs
dbenham 3.0 Parsing code Elapsed time 21 cs
Prepare memory:
---------------
JWinslow23 about 300 cs
JWinslow23 optimized about 800 cs
Loading parsed file:
--------------------
Aacini 2.1 18:08:33,67 - 18:08:33,70 elapsed 3 cs
Saving parsed file:
-------------------
Aacini 2.1 17:41:48,99 - 17:41:49,05 elapsed 6 cs
Run:
----
JWinslow23 about 75-100 cycles/s
dbenham 2.0 about 800 cycles/s
Aacini 2.1 about 750 cycles/s
dbenham 2.0 opt. about 800 cycles/s
JWinslow23 opt. about 130-140 cycles/s
dbenham 2.0 opt.12:59:28,01 - 12:59:17,77 Elapsed 85.26 s
Aacini 3.0 12:44:38,88 - 12:45:51,94 Elapsed 73.06 s
dbenham 3.0 Execute : Elapsed time 30.61 s
the time of execute of dbenham version 3.0 for small files is impressive!
For the Hanoi have choice the modified version Hanoi_mod.bf . Then have misured, when output a line of char, the time elapsed.
Hanoi_mod.bf
============
Parse:
------
dbenham 3.0 Elapsed time 425.08 s
Aacini 3.0 Extracting sub. 15:48:12,54 - 15:49:34,61 Elapsed 82.07 s
Aacini 3.0 Parsing sub. 15:49:34,63 - 15:49:55,75 Elapsed 21.12 s
denham 2.0 Mod 15:56:20,22 - 15:57:00,75 Elapsed 40.53 s
denham 3.0 Mod Elapsed time = 37.33 s
Run:
----
dbenham 3.0 15:32:18,53 - 15:40:14,48 Elapsed 484.05 s
Aacini 3.0 15:49:56,00 - 15:51:05,40 - 15:52:11,86 Elapsed 69.04 s 135.86 s
denham 2.0 mod 15:57:11,33 - 15:57:54,29 - 15:58:33,32 Elapsed 42.96 s 81.99 s
denham 3.0 mod 17:57:20,63 - 17:57:50,81 - 17:58:17,16 Elapsed 30.18 s 56.53 s
the version 3.0 of Aacini is now very fast for big files. But is not fastest.
Await the version of dbenham with PAGING!!!
einstein1969
Re: BrainF*** Interpreter in Batch
At long last my version 4 is ready 
The major new features are:
- Ability to read input from a file
- Ability to implement pseudo code paging. It defaults to a code page size of 100. But the -c option can override the default.
- Ability to implement pseudo array paging. It defaults to array paging off.
- Additional run-time stats are printed out: cycles, codePageFaults, arraySize, arrayPageFaults. Useful when trying to optimize the paging options for performance.
- Ability to specify a limit to the number of execution cycles. A handy option when testing hanoi
I reconsidered about how to go about memory management. Sophisticated management that tracks frequency of use is just to damn expensive, so the management needs to be simplistic.
I looked at Einstein1969's random approach, and realized there is no need to test for code erasure action if the requested code is already in memory. This can lead to unnecessary page faults. Better to only check for erasure when a new code address needs to be added to memory. I then looked at the random aspect. It is elegant, but the options for frequency of erasure are limited: approximately 10%, 1%, or 0.1% chance. My tests with hanoi showed that the random approach is optimal when the chance is ~2%, which required a slightly more complicated random test. Another drawback is the random element introduces more variability in performance from run to run.
I opted to maintain a count of the number of code ops currently in memory, and erase code memory when the count reaches the specified page size. Tests with hanoi showed optimal performance at page size of 100 to be slightly better than that of the random approach at ~2%, and the performance was more consistent from run to run. So I opted to use the fixed page size, even though it requires a bit more code. Note that my dynamic interpreter macro drops the page management entirely if the total number of ops is <= the page size.
I've tested the mechanics of the array paging, and it appears to work. But I don't really have a program to test whether it is effective at improving performance for programs that require a large memory array.
I really like the dynamic interpreter macro. I am able to create fairly optimized code for any given set of options. Be sure to check out the -m option so you can see the actual interpreter code that is generated for a given set of options.
Note that the triangle has slightly more code than my default code page size, so it invokes a bit of paging. This slows it down just a bit. The best performance is achieved by disabling code paging with -c "" . You could also disable it in this case by using -c 200 , but the threshold depends on the size of the code.
The interpreter has a lot of options, which means it requires a lot of testing, more than I have been able to achieve. I had successfully tested all the options at one point, but there is a possibility that a new feature may have broken an option that previously worked. Let me know if you find bugs.
Here is version 4:
Dave Benham
The major new features are:
- Ability to read input from a file
- Ability to implement pseudo code paging. It defaults to a code page size of 100. But the -c option can override the default.
- Ability to implement pseudo array paging. It defaults to array paging off.
- Additional run-time stats are printed out: cycles, codePageFaults, arraySize, arrayPageFaults. Useful when trying to optimize the paging options for performance.
- Ability to specify a limit to the number of execution cycles. A handy option when testing hanoi
I reconsidered about how to go about memory management. Sophisticated management that tracks frequency of use is just to damn expensive, so the management needs to be simplistic.
I looked at Einstein1969's random approach, and realized there is no need to test for code erasure action if the requested code is already in memory. This can lead to unnecessary page faults. Better to only check for erasure when a new code address needs to be added to memory. I then looked at the random aspect. It is elegant, but the options for frequency of erasure are limited: approximately 10%, 1%, or 0.1% chance. My tests with hanoi showed that the random approach is optimal when the chance is ~2%, which required a slightly more complicated random test. Another drawback is the random element introduces more variability in performance from run to run.
I opted to maintain a count of the number of code ops currently in memory, and erase code memory when the count reaches the specified page size. Tests with hanoi showed optimal performance at page size of 100 to be slightly better than that of the random approach at ~2%, and the performance was more consistent from run to run. So I opted to use the fixed page size, even though it requires a bit more code. Note that my dynamic interpreter macro drops the page management entirely if the total number of ops is <= the page size.
I've tested the mechanics of the array paging, and it appears to work. But I don't really have a program to test whether it is effective at improving performance for programs that require a large memory array.
I really like the dynamic interpreter macro. I am able to create fairly optimized code for any given set of options. Be sure to check out the -m option so you can see the actual interpreter code that is generated for a given set of options.
Note that the triangle has slightly more code than my default code page size, so it invokes a bit of paging. This slows it down just a bit. The best performance is achieved by disabling code paging with -c "" . You could also disable it in this case by using -c 200 , but the threshold depends on the size of the code.
The interpreter has a lot of options, which means it requires a lot of testing, more than I have been able to achieve. I had successfully tested all the options at one point, but there is a possibility that a new feature may have broken an option that previously worked. Let me know if you find bugs.
Here is version 4:
Code: Select all
::BF.BAT - BrainF*** interpreter in Batch, dbenham version 4.0
::
:: Usage:
::
:: bf sourceFile [-option [value]]...
::
:: Options
::
:: -i Filename = read Input from file Filename.
::
:: -z = <Ctrl-Z> terminates keyboard input (forces EOF).
::
:: -e Value = EOF value: Sets value read into memory upon End-Of-File.
:: Default is no change to memory.
::
:: -ee = terminate with Error if attempt is made to read past EOF.
::
:: -eo = terminate with Error if +/- results in Overflow.
::
:: -em = terminate with Error if < yields a negative Memory address.
::
:: -ea = terminate with Error on Any fault. Same as -ee -eo -em
::
:: -s = Silent mode. Don't print initialization messages, elapsed
:: times, or run statistics. Also disables the -l option.
::
:: -d Filename = Dump the parsed op codes to Filename.
:: Use con to print to screen.
::
:: -m Filename = write the interpreter Macro to Filename.
:: Use con to print to screen.
::
:: -t = Trace mode: Show op address/value, memory address/value
:: each cycle.
::
:: -# Count = Enables # op: Show current state. Count specifies the number
:: of values to display before and after the current address.
:: BUG ALERT: Some array values may not display properly if
:: Count > 0 and array members are swapped out to disk. This is
:: never a problem if -a is undefined.
::
:: -p = Parse only.
::
:: -c Count = Code memory (default = 100). Maximum amount of code allowed
:: to reside in memory at one time. Unlimited if undefined.
:: Excess code is swapped out to disk.
::
:: -a Count = Array memory (default = unlimited). Maximum number of array
:: members allowed to reside in memory at one time. Unlimited
:: if undefined. Excess array members are swapped out to disk.
::
:: -l Count = Limit the number of execution cycles to Count.
:: Ignored if -s enabled. Default is no limit (undefined).
::
:: The memory array consists of unsigned bytes. Increment and decrement
:: operations simply wrap when the limits are exceeded unless -eo is specified.
::
:: The memory array is unbounded both to the left and right. If -em is specified
:: then the array is unbounded to the right only.
::
:: In theory, the code pointer can range from 0 to 2147483647,
:: and the memory pointer can range from -2147483648 to 2147483647.
:: But performance will become unbearably long before those limits are
:: reached.
::
:: BF.BAT can only read input from a file supplied as a command line option, or
:: the keyboard. Input will fail if data is piped into BF.BAT or if stdin is
:: redirected to a file.
::
:: During keyboard input, the <Enter> key is read as <CR>. All other inputs are
:: normal. Any byte value (except 0x00) may be entered by holding down the <Alt>
:: key and entering a decimal code on the numeric keypad. The only way to enter
:: <LF> is via <Alt> and the numeric keypad.
::
:: This code was written by Dave Benham (aka dbenham)
:: with major contributions from Antonio Perez Ayala (aka Aacini),
:: and important suggestions for memory management from einstein1969.
::
:: Development efforts can be traced at
:: http://www.dostips.com/forum/viewtopic.php?f=3&t=5751
@echo off
:: Rentry point when running the bf program
if "%~1" equ ":run" ( rem
%bfInterpreter%
) %input%
:: Clear environment except for critical standard values
setlocal disableDelayedExpansion
for /f "eol== delims==" %%V in ('set^|findstr /rc:"^[^=]*!"') do set "%%V="
set "preserve= TEMP TMP PATH PATHEXT COMSPEC PRESERVE "
setlocal enableDelayedExpansion
for /f "eol== delims==" %%V in ('set') do (
if defined %%V if "!preserve: %%V =!" equ "!preserve!" set "%%V="
)
set "preserve="
:: Validate parameters
if "%~1" equ "" >&2 echo Usage: %~N0 filename.ext&exit /b 1
if not exist "%~1" >&2 echo File not found: %1&exit /b 1
:: Define options
set options=-d:"" -s: -z: -e:"" -m:"" -ee: -eo: -em: -ea: -t: -#:"" -p: -i:"" -c:100 -a:"" -l:""
:: Set option defaults
for %%O in (%options%) do for /f "tokens=1,* delims=:" %%A in ("%%O") do set "%%A=%%~B"
:loop Parse the option arguments
if not "%~2"=="" (
set "test=!options:*%~2:=! "
if "!test!"=="!options! " (
echo Error: Invalid option %~2
exit /b 1
) else if "!test:~0,1!"==" " (
set "%~2=1"
) else (
set "%~2=%~3"
shift /2
)
shift /2
goto :loop
)
:: Begin macro defnitions --------------
:: Define LF to contain a linefeed (0x0A) character
set ^"LF=^
^" The above empty line is critical - DO NOT REMOVE
:: define a newline with line continuation
set ^"\n=^^^%LF%%LF%^%LF%%LF%^^"
set showTime=(%\n%
for /f "tokens=1-4 delims=:.," %%a in ("^!t1: =0^!"^) do set /a "t1=(((1%%a*60)+1%%b)*60+1%%c)*100+1%%d-36610100"%\n%
for /f "tokens=1-4 delims=:.," %%a in ("^!t2: =0^!"^) do set /a "t2=(((1%%a*60)+1%%b)*60+1%%c)*100+1%%d-36610100"%\n%
set /a "tDiff=t2-t1"%\n%
if ^^!tDiff^^! lss 0 set /a tDiff+=24*60*60*100%\n%
set /a "s=tDiff/100, f=tDiff+100"%\n%
echo Elapsed time = ^^!s^^!.^^!f:~-2^^! s%\n%
^)
if defined -ea (
set -eo=1
set -em=1
set -ee=1
)
if defined -eo (
set "inc=set /a m[%%A]+=%%C&if ^!m[%%A]^! gtr 255 >&2 echo ^!LF^!ERROR: Overflow at ip=%%I mp=%%A&exit 1"
set "dec=set /a m[%%A]-=%%C&if ^!m[%%A]^! lss 0 >&2 echo ^!LF^!ERROR: Overflow at ip=%%I mp=%%A&exit 1"
) else (
set inc=set /a "m[%%A]=(m[%%A]+%%C)&255"
set dec=set /a "m[%%A]=(m[%%A]-%%C)&255"
)
if defined -em (
set "leftError=&if ^!mp^! lss 0 >&2 echo ^!LF^!ERROR: Invalid memory access at ip=%%I mp=%%A&exit 1"
)
if defined -t set trace=%\n%
echo c[%%I]=^^!c[%%I]^^! m[%%A]=^^!m[%%A]^^!
if defined -e set ^"setEOF=set /a "m[%%A]=!-e!"^"
if defined -z set eofMacros=1
if defined -i set eofMacros=1
if defined eofMacros (
set "ifNotEOF=if not defined EOF"
set ifSub=else if "^!key:~-1^!" equ "^!SUB^!" (%\n%
endlocal^&endlocal%\n%
set EOF=1%\n%
!setEOF!%\n%
^)
if defined -ee (
set "elsePastEOF= else >&2 echo ^!LF^!ERROR: Read past EOF at ip=%%I mp=%%A&exit 1 "
) else if defined -e (
set "elsePastEOF= else !setEOF! "
)
)
if defined -i (
set ^"getInput=else if "%%B" equ "," ( for /l %%N in (1 1 %%C^) do !ifNotEOF! (%\n%
set "key="%\n%
set /p "key="%\n%
if defined key (set /a "m[%%A]=0x^!key^!"^) else ( !setEOF!%\n%
set EOF=1%\n%
^)%\n%
^)!elsePastEOF!^) ^"
) else (
set ^"getInput=else if "%%B" equ "," (for /l %%N in (1 1 %%C^) do !ifNotEOF! (%\n%
set "key="%\n%
set "CtrlC=1"%\n%
setlocal disableDelayedExpansion%\n%
for /f "delims=" %%K in (%\n%
'xcopy /w "%~f0" "%~f0" 2^^^^^>nul'%\n%
^) do if not defined key (set "key=%%K"^) else set "CtrlC="%\n%
setlocal enableDelayedExpansion%\n%
if defined CtrlC (%\n%
endlocal^&endlocal%\n%
set "m[%%A]=3"%\n%
^) else if "^!key^!" equ "^!line1^!" (%\n%
endlocal^&endlocal%\n%
set "m[%%A]=10"%\n%
^) else if "^!key:~-1^!" equ "^!CR^!" (%\n%
endlocal^&endlocal%\n%
set "m[%%A]=13"%\n%
^) !ifSub! else (%\n%
^>key.bf_tmp echo(^^!key:~-1^^!%\n%
endlocal^&endlocal%\n%
for /f "delims=." %%K in ('findstr /lg:key.bf_tmp *.bf_chr'^) do set "m[%%A]=%%K"%\n%
^)%\n%
^)!elsePastEOF!^) ^"
)
if defined -# (
set #=#
set #Parse=else if "%%b" equ "#" (%\n%
set /a "ip+=1, #Found=1, clr=0"%\n%
^>c[^^!ip^^!].bf_tmp echo #%\n%
^)
if !-#! equ 0 (
set ^"#Exec=else if "%%B" equ "#" (%\n%
set /a next=ip+1%\n%
set "msg="%\n%
^<c[^^!next^^!].bf_tmp set /p "msg="%\n%
echo c[^^!next^^!]=^^!msg^^! m[%%A]=^^!m[%%A]^^!%\n%
^) ^"
) else set ^"#Exec=else if "%%B" equ "#" (%\n%
set /a next=ip+1, m1=mp-!-#!, m2=mp-1, m3=mp+1, m4=mp+!-#!%\n%
set "msg="%\n%
^<c[^^!next^^!].bf_tmp set /p "msg="%\n%
set "msg=c[^!next^!]=^!msg^! mp=%%A: "%\n%
for /l %%N in (^^!m1^^! 1 ^^!m2^^!^) do set "msg=^!msg^!| ^!m[%%N]^! "%\n%
set "msg=^!msg^!< ^!m[%%A]^! >"%\n%
for /l %%N in (^^!m3^^! 1 ^^!m4^^!^) do set "msg=^!msg^! ^!m[%%N]^! |"%\n%
echo ^^!msg^^!%\n%
^) ^"
)
if not defined -s (
set "getCycles=, cycles+=1"
set "getCodePageFaults=, codePageFaults+=1"
set "getArrayStats=, aSize+=1"
set "getArrayPageFaults=, arrayPageFautls+=1"
set showStats=%\n%
^>stats.bf_tmp (echo cycles=^^!cycles^^! codePageFaults=^^!codePageFaults^^!%\n%
echo arraySize=^^!aSize^^! arrayPageFaults=^^!arrayPageFaults^^!^)
if defined -l set getCycles=!getCycles! ^& if ^^!cycles^^! equ !-l! (!showStats!%\n%
exit 0%\n%
^)
)
if defined -c set codePaging=%\n%
if not defined c[%%I] if exist c[%%I].bf_tmp (%\n%
if ^^!cdCnt^^! equ !-c! (%\n%
for /f "delims==" %%A in ('set c[') do set "%%A="%\n%
set cdCnt=0%\n%
)%\n%
set /a cdCnt+=1!getCodePageFaults!%\n%
^<c[%%I].bf_tmp set /p "c[%%I]="%\n%
)
if defined -a (
set arrayPaging=if not defined m[%%A] (%\n%
if ^^!aCnt^^! equ !-a! for /f "tokens=1,2 delims==" %%a in ('set m['^) do (%\n%
^>%%a.bf_tmp echo %%b%\n%
set %%a=%\n%
set aCnt=0%\n%
^)%\n%
if exist m[%%A].bf_tmp (%\n%
^<m[%%A].bf_tmp set /p m[%%A]=%\n%
set /a arrayPageFaults+=1%\n%
^) else set /a m[%%A]=0!getArrayStats!%\n%
set /a aCnt+=1%\n%
^)
) else set "arrayPaging=if not defined m[%%A] set /a m[%%A]=0!getArrayStats!"
:: End macro definition ------------------
:: Create character files if they don't already exist
if not defined -s (
echo ----------------------------
echo Begin Initialization
echo Testing ASCII character files.
)
set "needChars="
for /l %%N in (0 1 255) do for %%F in (%%N.bf_chr) do if "%%~zF" neq "1" set "needChars=1"
if defined needChars (
if not defined -s (
echo Creating ASCII character files...
set "t1=!time!"
)
call :genAllChr
if not defined -s (
set t2=!time!
%showTime%
)
)
:: Parse the input file
if not defined -i goto :skipInput
if not defined -s (
<nul set /p "=Parsing input."
set t1=!time!
)
if not exist "!-i!" >&2 echo ERROR: Input file "!-i!" not found & exit 1
if exist "!-i!\" >&2 echo ERROR: Input file "!-i!" not found & exit 1
copy 0.bf_chr compare.bf_tmp >nul
set /a size=skipStart=1
for %%F in ("!-i!") do set inSize=%%~zF
for /l %%N in (1 1 32) do if !size! lss !inSize! set /a "size*=2" & type compare.bf_tmp >>compare.bf_tmp
fc /b "!-i!" compare.bf_tmp | findstr /rxc:"........: .. .." >diff.bf_tmp
>input.bf_tmp (
for /f "tokens=1,2 delims=:[] " %%A in (diff.bf_tmp) do (
set /a skipEnd=0x%%A
for /l %%N in (!skipStart! 1 !skipEnd!) do echo 00
echo %%B
set /a skipStart=skipEnd+2
if "!skipStart:~-3!" equ "000" <nul set /p "=." >&2
)
for /l %%N in (!skipStart! 1 !inSize!) do echo 00
)
set "input=<input.bf_tmp"
if not defined -s (
set t2=!time!
echo(
%showTime%
)
:skipInput
:: Parse the code and for each op, store the op followed by a number.
:: For [ and ] the number represents the address of the matching loop boundary
:: For all other ops the number represents the repeat count for that op.
:: Optionally treats # as an additional show state op code with constant count.
:: Optimization collapses [-] into special 0 op (no count).
:: Detects if input is not used so getInput can be removed from interpreter loop.
:: Treats loops at beginning or immedieately following ] as comments (ignores them)
if not defined -s (
<nul set /p "=Parsing code."
set "parseProgress=set /a n=(n+1^^)%%500&if ^!n^! equ 0 <nul set /p "=.""
set "t1=!time!"
)
2>nul del c[*.bf_tmp
for %%C in (+ - "<" ">" . "," #) do set "comment%%~C=0"
set /a ip=comment]=-1, sp=count=comment=0, comment[=1
cmd /u /c type %1|find /v ""|findstr "[+\-<>.,[\]!#!]" >src.bf_tmp
for /f %%b in (src.bf_tmp) do ( %parseProgress%
if !comment! gtr 0 (
set /a comment+=!comment%%b!
) else if "!lastOp!" equ "%%b" (
set /a count+=1
) else (
if defined lastOp (
set "test="
if !clr! equ 1 if !lastOp! equ - if !count! equ 1 set /a clr=test=2
if not defined test set clr=0
set /a ip+=1
>c[!ip!].bf_tmp echo !lastOp! !count!
set "lastOp="
)
if "%%b" equ "[" (
if defined comment (set /a comment+=1) else (
set /a "ip+=1, sp+=1, clr=1"
set /a "stack[!sp!]=ip"
)
) else if "%%b" equ "]" for %%s in (!sp!) do (
if !clr! equ 2 (
>c[!stack[%%s]!].bf_tmp echo 0
del c[!ip!].bf_tmp
set /a "ip-=1, sp-=1"
) else (
set /a ip+=1, sp-=1
>c[!ip!].bf_tmp echo ] !stack[%%s]!
>c[!stack[%%s]!].bf_tmp echo [ !ip!
)
set /a "clr=comment=0"
) %#Parse% else (
set "comment="
set "lastOp=%%b"
set /a "count=1"
if "%%b" equ "," set inputRequired=1
)
)
)
if defined lastOp (
set /a ip+=1
>c[!ip!].bf_tmp echo %lastOp% %count%
)
if not defined -s (
set "t2=!time!"
echo(
%showTime%
)
:: Error if unbalanced brackets
if %sp% neq 0 >&2 echo ERROR: Unbalanced brackets&exit /b 1
if defined comment if "%comment%" neq "0" >&2 echo ERROR: Unbalanced brackets&exit /b 1
:: Dump the parsed op codes
if defined -d (for /l %%N in (0 1 !ip!) do (
<c[%%N].bf_tmp set /p "msg="
echo c[%%N]=!msg!
)) >"!-d!"
:: Disable code paging if code length does not exceed -cp
if not defined -c set "-c=!ip!
if !ip! leq !-c! (
set "codePaging="
for /l %%N in (0 1 !ip!) do <c[%%N].bf_tmp set /p "c[%%N]="
)
:: Undefine getInput and/or #Parse if not needed
if not defined inputRequired set "getInput="
if not defined #Found set "#Exec="
:: Define CR to hold <CarriageReturn> for use in input routine
for /f %%A in ('copy /Z "%~dpf0" nul') do set "CR=%%A"
:: Define SUB to hold <0x1A>
for /f "delims=" %%A in (26.bf_chr) do set "SUB=%%A"
:: Establish line one of input routine for this locale
set "line1="
for /f "delims=" %%L in (
'echo .^|xcopy /w "%~f0" "%~f0" 2^>nul'
) do if not defined line1 set "line1=%%L"
set "line1=!line1:~0,-1!"
:: Create final interpreter macro
set bfInterpreter=^
set /a "ip=mp=cdCnt=cycles=aCnt=aSize=0"%\n%
for /l %%. in () do for %%I in (^^!ip^^!) do (!codePaging!%\n%
for /f "tokens=1-3" %%A in ("^!mp^! ^!c[%%I]^!") do (%\n%
!arrayPaging!!trace!%\n%
if "%%B" equ "+" (%\n%
!inc!%\n%
) else if "%%B" equ "-" (%\n%
!dec!%\n%
) else if "%%B" equ "0" (%\n%
set "m[%%A]=0"%\n%
) else if "%%B" equ ">" (%\n%
set /a "mp+=%%C"%\n%
) else if "%%B" equ "<" (%\n%
set /a "mp-=%%C"!leftError!%\n%
) else if "%%B" equ "[" (%\n%
if "^!m[%%A]^!" equ "0" set "ip=%%C"%\n%
) else if "%%B" equ "]" (%\n%
if "^!m[%%A]^!" neq "0" set "ip=%%C"%\n%
) else if "%%B" equ "." for /l %%N in (1 1 %%C) do (%\n%
if "^!m[%%A]^!" equ "26" (set /p "=^!SUB^!" ^<nul) else type ^^!m[%%A]^^!.bf_chr%\n%
) !getInput!!#Exec!else (!showStats!%\n%
exit 0%\n%
)%\n%
set /a ip+=1!getCycles!%\n%
)%\n%
)
:: Print out the finalized brainF*** interpreter macro
if defined -m >"!-m!" echo bfInterpreter=!lf!!bfInterpreter:%%=%%%%!
if not defined -s (
echo Initialization complete
echo ============================
set t1=%time%
)
(call )
if defined -p goto :quit
:: Launch the interpreter
cmd /v:on /c "%~f0" :run&&(call )||(call)
set "err=%errolevel%
if not defined -s (
set t2=%time%
echo(
echo ============================
%showTime%
if exist stats.bf_tmp type stats.bf_tmp
)
:quit
del *.bf_tmp
exit /b %err%
:genAllChr
::This code creates 256 1 byte files, one for each possible byte value.
::This is encoded in a macro way to be called asynchronously with start cmd /c
::Teamwork of carlos, penpen, aGerman, dbenham, einstein1969
::Tested under Win7 and XP
setlocal disableDelayedExpansion
set ^"genchr=(^
for /l %%N in (%%A !cnt! 255) do (^
if %%N equ 26 (^
copy /y nul + nul /a 26.bf_chr /a ^>nul^
) else (if %%N geq 35 if %%N leq 126 if %%N neq 61 (^
^<nul set /p "=!ascii:~%%N,1!" ^>%%N.bf_chr^
))^&^
if not exist %%N.bf_chr (^
makecab /d compress=off /d reserveperdatablocksize=26 /d reserveperfoldersize=%%N %%A.tmp %%N.bf_chr ^>nul^&^
type %%N.bf_chr ^| ((for /l %%n in (1 1 38) do pause)^>nul^&findstr "^^" ^>%%N.temp)^&^
^>nul copy /y %%N.temp /a %%N.bf_chr /b^&^
del %%N.temp^
)^
))^&^
del %%A.tmp^"
del /f /q /a *bf.chr >nul 2>&1
set "ascii= #$%%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~"
set /a cnt=number_of_processors
if %cnt% lss 1 set cnt=1
if %cnt% gtr 256 set cnt=256
set /a "end=cnt-1"
for /l %%A in (0 1 %end%) do (
type nul >%%A.tmp
if %%A equ %end% (
cmd /q /v:on /c "%genchr%"
) else (
start "" /b cmd /q /v:on /c "%genchr%"
)
)
:genAllChr.check
for /l %%N in (0 1 %end%) do if exist %%N.tmp goto :genAllChr.check
exit /b
Dave Benham
Re: BrainF*** Interpreter in Batch
Aacini's ansisys.exe utility sure is handy when used with hanoi.bf.
Here are the results of running the modified hanoi.bf (minus the delay loop), with a limit of 3 million execution cycles. I modified my script a bit to put a PAUSE before beginning the execution so that I could capture the initialization output. I also added 20 ECHO( upon program exit so that the run stats do not clobber the "graphical" display.
The first ~20 minutes are spent establishing the starting position. It then took ~12 minutes to perform 3 moves, plus mid way through the 4th.
Assuming the remainder of the program is somewhat linear, I estimate it would take between 24 and 36 hours to run to completion on my PC (511 moves).
Dave Benham
Here are the results of running the modified hanoi.bf (minus the delay loop), with a limit of 3 million execution cycles. I modified my script a bit to put a PAUSE before beginning the execution so that I could capture the initialization output. I also added 20 ECHO( upon program exit so that the run stats do not clobber the "graphical" display.
Code: Select all
C:\test\bf>bf3 hanoi2.bf -l 3000000 | ansisys
----------------------------
Begin Initialization
Testing ASCII character files.
Parsing code....................................................................
......................................
Elapsed time = 33.46 s
Initialization complete
============================
Press any key to continue . . .
<screen is cleared, and then...>
Towers of Hanoi in Brainf*ck
Written by Clifford Wolf <http://www.clifford.at/bfcpu/>
xXXXXXXXXXXXXXx
xXXXXXXXXXXXXXXXXXx
xXXXXXXXXXXXXXXXXXXXXXx
xXXXXXXXXXXXXXXXXXXXXXXXXXx
xXXXXXXXXXXXXXXXXXXXXXXXXXXXXXx
xXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXx
----------------------------------- -----------------------------------
xXx
xXXXXXx
-----------------------------------
============================
Elapsed time = 1943.18 s
cycles=3000000 codePageFaults=76849
arraySize=180 arrayPageFaults=
C:\test\bf>
The first ~20 minutes are spent establishing the starting position. It then took ~12 minutes to perform 3 moves, plus mid way through the 4th.
Assuming the remainder of the program is somewhat linear, I estimate it would take between 24 and 36 hours to run to completion on my PC (511 moves).
Dave Benham
-
einstein1969
- Expert
- Posts: 960
- Joined: 15 Jun 2012 13:16
- Location: Italy, Rome
Re: BrainF*** Interpreter in Batch
Hi Dave,
I have studied your 4.0 version. Is really well done!
The speed is near the top and the idea of macro personalized is fantastic.
I have an idea for take of other 20% or more of execution time
Every cycles the BF execute one istruction, that is a SET.
A mechanism similar pipeline is execute 2 instruction per "clock" tic.
This is equivalent to execute instead:
two set:
I have measured that with 2 istruction take 20% off. (with 3 about 30%)
This ratio decrement if environment size increase.
But the problem is traducing the istruction to generic istruction for mantein the code small.
I remeber a thread in there you had found a way to get to 4 expansions.
Maybe it can be useful. I will search!
Edit : This Interesting expansion experiment
einstein1969
I have studied your 4.0 version. Is really well done!
The speed is near the top and the idea of macro personalized is fantastic.
I have an idea for take of other 20% or more of execution time
Every cycles the BF execute one istruction, that is a SET.
A mechanism similar pipeline is execute 2 instruction per "clock" tic.
This is equivalent to execute instead:
Code: Select all
SET /A .....
two set:
Code: Select all
SET /A instructionA, instructionB
I have measured that with 2 istruction take 20% off. (with 3 about 30%)
This ratio decrement if environment size increase.
But the problem is traducing the istruction to generic istruction for mantein the code small.
I remeber a thread in there you had found a way to get to 4 expansions.
Maybe it can be useful. I will search!
Edit : This Interesting expansion experiment
einstein1969
Re: BrainF*** Interpreter in Batch
Pipelining operations into one cycle - great idea It makes a HUGE difference. The triangle is twice as fast on my machine. And hanoi is nearly twice as fast, without bothering to optimize the code page size.
I completely redesigned most of the op codes. Each of the following can be expressed as a single SET /A expression, expressed as an S op code:
+
-
<
>
[
]
[-]
The following can be concatenated indefinitely:
+
-
[-]
Also, the above can be combined with any one of the following:
<
>
[
]
The code stored for each cycle is significantly greater. But most cycles pipeline at least 2 operations, so there are significantly fewer lines. The interpreter macro is much smaller (and faster). It only has to define at most 4 operations: S . , # It may have as few as two: S and .
I did not take the time to figure out an optimal code page size - I kept the default at 100. I suspect it should be smaller.
Another optimization I made is to completely wipe out the environment at the start of the interpreter macro, except for the code and a few constants. I had to include the full path to XCOPY and FINDSTR in the macro since PATH is no longer defined. It looks odd that the macro erases itself, but it works.
So here is my version 5. I've done even less testing than before. I won't be surprised if I've managed to break one of the options.
Code: Select all
::BF.BAT - BrainF*** interpreter in Batch, dbenham version 5.0
::
:: Usage:
::
:: bf sourceFile [-option [value]]...
::
:: Options
::
:: -i Filename = read Input from file Filename.
::
:: -z = <Ctrl-Z> terminates keyboard input (forces EOF).
::
:: -e Value = EOF value: Sets value read into memory upon End-Of-File.
:: Default is no change to memory.
::
:: -ee = terminate with Error if attempt is made to read past EOF.
::
:: -eo = terminate with Error if +/- results in Overflow.
::
:: -em = terminate with Error if < yields a negative Memory address.
::
:: -ea = terminate with Error on Any fault. Same as -ee -eo -em
::
:: -s = Silent mode. Don't print initialization messages, elapsed
:: times, or run statistics. Also disables the -l option.
::
:: -d Filename = Dump the parsed op codes to Filename.
:: Use con to print to screen.
::
:: -m Filename = write the interpreter Macro to Filename.
:: Use con to print to screen.
::
:: -t = Trace mode: Show op address/value, memory address/value
:: each cycle.
::
:: -# Count = Enables # op: Show current state. Count specifies the number
:: of values to display before and after the current address.
:: BUG ALERT: Some array values may not display properly if
:: Count > 0 and array members are swapped out to disk. This is
:: never a problem if -a is undefined.
::
:: -p = Parse only.
::
:: -c Count = Code memory (default = 100). Maximum amount of code allowed
:: to reside in memory at one time. Unlimited if undefined.
:: Excess code is swapped out to disk.
::
:: -a Count = Array memory (default = unlimited). Maximum number of array
:: members allowed to reside in memory at one time. Unlimited
:: if undefined. Excess array members are swapped out to disk.
::
:: -l Count = Limit the number of execution cycles to Count.
:: Ignored if -s enabled. Default is no limit (undefined).
::
:: The memory array consists of unsigned bytes. Increment and decrement
:: operations simply wrap when the limits are exceeded unless -eo is specified.
::
:: The memory array is unbounded both to the left and right. If -em is specified
:: then the array is unbounded to the right only.
::
:: In theory, the code pointer can range from 0 to 2147483647,
:: and the memory pointer can range from -2147483648 to 2147483647.
:: But performance will become unbearably long before those limits are
:: reached.
::
:: BF.BAT can only read input from a file supplied as a command line option, or
:: the keyboard. Input will fail if data is piped into BF.BAT or if stdin is
:: redirected to a file.
::
:: During keyboard input, the <Enter> key is read as <CR>. All other inputs are
:: normal. Any byte value (except 0x00) may be entered by holding down the <Alt>
:: key and entering a decimal code on the numeric keypad. The only way to enter
:: <LF> is via <Alt> and the numeric keypad.
::
:: This code was written by Dave Benham (aka dbenham)
:: with major contributions from Antonio Perez Ayala (aka Aacini),
:: and einstein1969.
::
:: Development efforts can be traced at
:: http://www.dostips.com/forum/viewtopic.php?f=3&t=5751
@echo off
:: Rentry point when running the bf program
if "%~1" equ ":run" ( rem
%bfInterpreter%
) %input%
:: Clear environment except for critical standard values
setlocal disableDelayedExpansion
for /f "eol== delims==" %%V in ('set^|findstr /rc:"^[^=]*!"') do set "%%V="
set "preserve= TEMP TMP PATH PATHEXT COMSPEC PRESERVE "
setlocal enableDelayedExpansion
for /f "eol== delims==" %%V in ('set') do (
if defined %%V if "!preserve: %%V =!" equ "!preserve!" set "%%V="
)
set "preserve="
:: Validate parameters
if "%~1" equ "" >&2 echo Usage: %~N0 filename.ext&exit /b 1
if not exist "%~1" >&2 echo File not found: %1&exit /b 1
:: Define options
set options=-d:"" -s: -z: -e:"" -m:"" -ee: -eo: -em: -ea: -t: -#:"" -p: -i:"" -c:100 -a:"" -l:""
:: Set option defaults
for %%O in (%options%) do for /f "tokens=1,* delims=:" %%A in ("%%O") do set "%%A=%%~B"
:loop Parse the option arguments
if not "%~2"=="" (
set "test=!options:*%~2:=! "
if "!test!"=="!options! " (
echo Error: Invalid option %~2
exit /b 1
) else if "!test:~0,1!"==" " (
set "%~2=1"
) else (
set "%~2=%~3"
shift /2
)
shift /2
goto :loop
)
:: Begin macro defnitions --------------
:: Define LF to contain a linefeed (0x0A) character
set ^"LF=^
^" The above empty line is critical - DO NOT REMOVE
:: define a newline with line continuation
set ^"\n=^^^%LF%%LF%^%LF%%LF%^^"
set showTime=(%\n%
for /f "tokens=1-4 delims=:.," %%a in ("^!t1: =0^!"^) do set /a "t1=(((1%%a*60)+1%%b)*60+1%%c)*100+1%%d-36610100"%\n%
for /f "tokens=1-4 delims=:.," %%a in ("^!t2: =0^!"^) do set /a "t2=(((1%%a*60)+1%%b)*60+1%%c)*100+1%%d-36610100"%\n%
set /a "tDiff=t2-t1"%\n%
if ^^!tDiff^^! lss 0 set /a tDiff+=24*60*60*100%\n%
set /a "s=tDiff/100, f=tDiff+100"%\n%
echo Elapsed time = ^^!s^^!.^^!f:~-2^^! s%\n%
^)
if defined -ea (
set -eo=1
set -em=1
set -ee=1
)
if defined -eo (
set "inc=over|=(m[^^^!mp^^^!]+=^!count^!)&-256"
set "dec=over|=(m[^^^!mp^^^!]-=^!count^!)&-256"
set overError=%\n%
if ^^!over^^! neq 0 ^>^&2 echo ^^!LF^^!ERROR: Overflow at ip=%%I mp=%%A^&exit 1
) else (
set "inc=m[^^^!mp^^^!]=(m[^^^!mp^^^!]+^!count^!)&255"
set "dec=m[^^^!mp^^^!]=(m[^^^!mp^^^!]-^!count^!)&255"
)
if defined -em (
set leftError=%\n%
if ^^!mp^^! lss 0 ^>^&2 echo ^^!LF^^!ERROR: Invalid memory access at ip=%%I mp=%%A^&exit 1
)
if defined -t set trace=%\n%
echo c[%%I]=^^!c[%%I]^^! m[%%A]=^^!m[%%A]^^!
if defined -e set ^"setEOF=set /a "m[%%A]=!-e!"^"
if defined -z set eofMacros=1
if defined -i set eofMacros=1
if defined eofMacros (
set "ifNotEOF=if not defined EOF"
set ifSub=else if "^!key:~-1^!" equ "^!SUB^!" (%\n%
endlocal^&endlocal%\n%
set EOF=1%\n%
!setEOF!%\n%
^)
if defined -ee (
set "elsePastEOF= else >&2 echo ^!LF^!ERROR: Read past EOF at ip=%%I mp=%%A&exit 1 "
) else if defined -e (
set "elsePastEOF= else !setEOF! "
)
)
if defined -i (
set ^"getInput=else if "%%B" equ "," ( for /l %%N in (1 1 %%C^) do !ifNotEOF! (%\n%
set "key="%\n%
set /p "key="%\n%
if defined key (set /a "m[%%A]=0x^!key^!"^) else ( !setEOF!%\n%
set EOF=1%\n%
^)%\n%
^)!elsePastEOF!^) ^"
) else for %%F in (findstr.exe) do (
set ^"getInput=else if "%%B" equ "," (for /l %%N in (1 1 %%C^) do !ifNotEOF! (%\n%
set "key="%\n%
set "CtrlC=1"%\n%
setlocal disableDelayedExpansion%\n%
for /f "delims=" %%K in (%\n%
'^^^^^""%%~dp$path:Fxcopy.exe" /w "%~f0" "%~f0" 2^^^^^>nul^^^^^"'%\n%
^) do if not defined key (set "key=%%K"^) else set "CtrlC="%\n%
setlocal enableDelayedExpansion%\n%
if defined CtrlC (%\n%
endlocal^&endlocal%\n%
set "m[%%A]=3"%\n%
^) else if "^!key^!" equ "^!line1^!" (%\n%
endlocal^&endlocal%\n%
set "m[%%A]=10"%\n%
^) else if "^!key:~-1^!" equ "^!CR^!" (%\n%
endlocal^&endlocal%\n%
set "m[%%A]=13"%\n%
^) !ifSub! else (%\n%
^>key.bf_tmp echo(^^!key:~-1^^!%\n%
endlocal^&endlocal%\n%
for /f "delims=." %%K in ('^^^^^""%%~$path:F" /lg:key.bf_tmp *.bf_chr^^^^^"'^) do set "m[%%A]=%%K"%\n%
^)%\n%
^)!elsePastEOF!^) ^"
)
if defined -# (
set #=#
set #Parse=else if "%%b" equ "#" (%\n%
if defined lastCmd (%\n%
set /a ip+=1%\n%
^>c[^^!ip^^!].bf_tmp echo S "^^!lastCmd:~0,-1^^!"%\n%
set "lastCmd="%\n%
^)%\n%
set /a "ip+=1, #Found=1, clr=0"%\n%
^>c[^^!ip^^!].bf_tmp echo #%\n%
^)
if !-#! equ 0 (
set ^"#Exec=else if "%%B" equ "#" (%\n%
set /a next=ip+1%\n%
set "msg="%\n%
^<c[^^!next^^!].bf_tmp set /p "msg="%\n%
echo c[^^!next^^!]=^^!msg^^! m[%%A]=^^!m[%%A]^^!%\n%
^) ^"
) else set ^"#Exec=else if "%%B" equ "#" (%\n%
set /a next=ip+1, m1=mp-!-#!, m2=mp-1, m3=mp+1, m4=mp+!-#!%\n%
set "msg="%\n%
^<c[^^!next^^!].bf_tmp set /p "msg="%\n%
set "msg=c[^!next^!]=^!msg^! mp=%%A: "%\n%
for /l %%N in (^^!m1^^! 1 ^^!m2^^!^) do set "msg=^!msg^!| ^!m[%%N]^! "%\n%
set "msg=^!msg^!< ^!m[%%A]^! >"%\n%
for /l %%N in (^^!m3^^! 1 ^^!m4^^!^) do set "msg=^!msg^! ^!m[%%N]^! |"%\n%
echo ^^!msg^^!%\n%
^) ^"
)
if not defined -s (
set "getCycles=, cycles+=1"
set "getCodePageFaults=, codePageFaults+=1"
set "getArrayStats=, aSize+=1"
set "getArrayPageFaults=, arrayPageFautls+=1"
set showStats=%\n%
^>stats.bf_tmp (echo cycles=^^!cycles^^! codePageFaults=^^!codePageFaults^^!%\n%
echo arraySize=^^!aSize^^! arrayPageFaults=^^!arrayPageFaults^^!^)
if defined -l set getCycles=!getCycles! ^& if ^^!cycles^^! equ !-l! (!showStats!%\n%
exit 0%\n%
^)
)
if defined -c set codePaging=%\n%
if not defined c[%%I] if exist c[%%I].bf_tmp (%\n%
if ^^!cdCnt^^! equ !-c! (%\n%
for /f "delims==" %%A in ('set c[') do set "%%A="%\n%
set cdCnt=0%\n%
)%\n%
set /a cdCnt+=1!getCodePageFaults!%\n%
^<c[%%I].bf_tmp set /p "c[%%I]="%\n%
)
if defined -a (
set arrayPaging=if not defined m[%%A] (%\n%
if ^^!aCnt^^! equ !-a! for /f "tokens=1,2 delims==" %%a in ('set m['^) do (%\n%
^>%%a.bf_tmp echo %%b%\n%
set %%a=%\n%
set aCnt=0%\n%
^)%\n%
if exist m[%%A].bf_tmp (%\n%
^<m[%%A].bf_tmp set /p m[%%A]=%\n%
set /a arrayPageFaults+=1%\n%
^) else set /a m[%%A]=0!getArrayStats!%\n%
set /a aCnt+=1%\n%
^)
) else set "arrayPaging=if not defined m[%%A] set /a m[%%A]=0!getArrayStats!"
:: End macro definition ------------------
:: Create character files if they don't already exist
if not defined -s (
echo ----------------------------
echo Begin Initialization
echo Testing ASCII character files.
)
set "needChars="
for /l %%N in (0 1 255) do for %%F in (%%N.bf_chr) do if "%%~zF" neq "1" set "needChars=1"
if defined needChars (
if not defined -s (
echo Creating ASCII character files...
set "t1=!time!"
)
call :genAllChr
if not defined -s (
set t2=!time!
%showTime%
)
)
:: Parse the input file
if not defined -i goto :skipInput
if not defined -s (
<nul set /p "=Parsing input."
set t1=!time!
)
if not exist "!-i!" >&2 echo ERROR: Input file "!-i!" not found & exit 1
if exist "!-i!\" >&2 echo ERROR: Input file "!-i!" not found & exit 1
copy 0.bf_chr compare.bf_tmp >nul
set /a size=skipStart=1
for %%F in ("!-i!") do set inSize=%%~zF
for /l %%N in (1 1 32) do if !size! lss !inSize! set /a "size*=2" & type compare.bf_tmp >>compare.bf_tmp
fc /b "!-i!" compare.bf_tmp | findstr /rxc:"........: .. .." >diff.bf_tmp
>input.bf_tmp (
for /f "tokens=1,2 delims=:[] " %%A in (diff.bf_tmp) do (
set /a skipEnd=0x%%A
for /l %%N in (!skipStart! 1 !skipEnd!) do echo 00
echo %%B
set /a skipStart=skipEnd+2
if "!skipStart:~-3!" equ "000" <nul set /p "=." >&2
)
for /l %%N in (!skipStart! 1 !inSize!) do echo 00
)
set "input=<input.bf_tmp"
if not defined -s (
set t2=!time!
echo(
%showTime%
)
:skipInput
:: Parse the code. Consecutive op codes are coalesced into one op with a count.
:: Optionally treats # as an additional show state op code (withoug coalesce).
:: Optimization collapses [-] into a special clear value op.
:: + - < > [ ] [-] are all converted into an S op followed by a SET /A expression.
:: Consecutive + - and [-] are concatenated into one op. If followed by
:: < > [ or ] then that op is also concatenated, but that is the limit for one op.
:: . and , are stored as themselves, followed by the count.
:: # is stored as itself without a count
:: Detects if input is not used so getInput can be removed from interpreter loop.
:: Treats loops at beginning or immedieately following ] as comments (ignores them)
if not defined -s (
<nul set /p "=Parsing code."
set "parseProgress=set /a n=(n+1^^)%%500&if ^!n^! equ 0 <nul set /p "=.""
set "t1=!time!"
)
2>nul del c[*.bf_tmp
for %%C in (+ - "<" ">" . "," #) do set "comment%%~C=0"
set /a ip=comment]=-1, sp=count=comment=0, comment[=1
cmd /u /c type %1|find /v ""|findstr "[+\-<>.,[\]!#!]" >src.bf_tmp
for /f %%b in (src.bf_tmp) do ( %parseProgress%
if !comment! gtr 0 (
set /a comment+=!comment%%b!
) else if "!lastOp!" equ "%%b" (
set /a count+=1
) else (
if defined lastOp (
set "test="
if !clr! equ 1 if !lastOp! equ - if !count! equ 1 set /a clr=test=2
if not defined test set clr=0
if "!lastOp!" equ "+" (
set "lastCmd=!lastCmd!%inc%,"
) else if "!lastOp!" equ "-" (
set "lastCmd=!lastCmd!!delim!%dec%,"
) else (
set /a ip+=1
if "!lastOp!" equ ">" (
>c[!ip!].bf_tmp echo S "!lastCmd!mp+=!count!"
) else if "!lastOp!" equ "<" (
>c[!ip!].bf_tmp echo S "!lastCmd!mp-=!count!"
) else (
if defined lastCmd (
>c[!ip!].bf_tmp echo S "!lastCmd:~0,-1!"
set /a ip+=1
)
>c[!ip!].bf_tmp echo !lastOp! !count!
)
set "lastCmd="
)
set "lastOp="
)
if "%%b" equ "[" (
if defined comment (set /a comment+=1) else (
set /a "ip+=1, sp+=1, clr=1"
set /a "stack[!sp!]=ip"
set "stackCmd[!sp!]=!lastCmd!"
set "lastCmd="
)
) else if "%%b" equ "]" for %%s in (!sp!) do (
if !clr! equ 2 (
set "lastCmd=!stackCmd[%%s]!m[^!mp^!]=0,"
set /a "ip-=1, sp-=1"
) else (
set /a ip+=1, sp-=1, count=ip-stack[%%s]
>c[!ip!].bf_tmp echo S "!lastCmd!ip-=^^^!^^^!m[^!mp^!]*!count!"
>c[!stack[%%s]!].bf_tmp echo S "!stackCmd[%%s]!ip+=^^^!m[^!mp^!]*!count!"
set "lastCmd="
)
set /a "clr=comment=0"
) %#Parse% else (
set "comment="
set "lastOp=%%b"
set /a "count=1"
if "%%b" equ "," set inputRequired=1
)
)
)
if defined lastOp (
set /a ip+=1
(
if "!lastOp!" equ "+" (
echo S "!lastCmd!%inc%"
) else if "!lastOp!" equ "-" (
echo S "!lastCmd!%dec%"
) else if "!lastOp!" equ ">" (
echo S "!lastCmd!mp+=!count!"
) else if "!lastOp!" equ "<" (
echo S "!lastCmd!mp-=!count!"
) else (
echo S "!lastCmd:~0,-1!"
echo !lastOp! !count!
)
)>c[!ip!].bf_tmp
) else if defined lastCmd (
set /a ip+=1
>c[!ip!].bf_tmp echo S "!lastCmd:~0,-1!"
)
if not defined -s (
set "t2=!time!"
echo(
%showTime%
)
:: Error if unbalanced brackets
if %sp% neq 0 >&2 echo ERROR: Unbalanced brackets&exit /b 1
if defined comment if "%comment%" neq "0" >&2 echo ERROR: Unbalanced brackets&exit /b 1
:: Dump the parsed op codes
if defined -d (for /l %%N in (0 1 !ip!) do (
<c[%%N].bf_tmp set /p "msg="
echo c[%%N]=!msg!
)) >"!-d!"
:: Disable code paging if code length does not exceed -cp
if not defined -c set "-c=!ip!
if !ip! leq !-c! (
set "codePaging="
for /l %%N in (0 1 !ip!) do <c[%%N].bf_tmp set /p "c[%%N]="
)
:: Undefine getInput and/or #Parse if not needed
if not defined inputRequired set "getInput="
if not defined #Found set "#Exec="
:: Define CR to hold <CarriageReturn> for use in input routine
for /f %%A in ('copy /Z "%~dpf0" nul') do set "CR=%%A"
:: Define SUB to hold <0x1A>
for /f "delims=" %%A in (26.bf_chr) do set "SUB=%%A"
:: Establish line one of input routine for this locale
set "line1="
for /f "delims=" %%L in (
'echo .^|xcopy /w "%~f0" "%~f0" 2^>nul'
) do if not defined line1 set "line1=%%L"
set "line1=!line1:~0,-1!"
:: Create final interpreter macro
set bfInterpreter=^
for /f "delims==" %%V in ('set^^^^^|findstr /bv "c[ line1= CR= SUB="') do set "%%V="%\n%
set /a "ip=mp=cdCnt=cycles=aCnt=aSize=over=0"%\n%
for /l %%. in () do for %%I in (^^!ip^^!) do (!codePaging!%\n%
for /f "tokens=1-3" %%A in ("^!mp^! ^!c[%%I]^!") do (%\n%
!arrayPaging!!trace!%\n%
if "%%B" equ "S" (%\n%
set /a "%%C"!overError!!leftError!%\n%
) else if "%%B" equ "." for /l %%N in (1 1 %%C) do (%\n%
if "^!m[%%A]^!" equ "26" (set /p "=^!SUB^!" ^<nul) else type ^^!m[%%A]^^!.bf_chr%\n%
) !getInput!!#Exec!else (!showStats!%\n%
exit 0%\n%
)%\n%
set /a ip+=1!getCycles!%\n%
)%\n%
)
:: Print out the finalized brainF*** interpreter macro
if defined -m >"!-m!" echo bfInterpreter=!lf!!bfInterpreter:%%=%%%%!
if not defined -s (
echo Initialization complete
echo ============================
set t1=%time%
)
(call )
if defined -p goto :quit
:: Launch the interpreter
cmd /v:on /c "%~f0" :run&&(call )||(call)
set "err=%errolevel%
if not defined -s (
set t2=%time%
echo(
echo ============================
%showTime%
if exist stats.bf_tmp type stats.bf_tmp
)
:quit
del *.bf_tmp
exit /b %err%
:genAllChr
::This code creates 256 1 byte files, one for each possible byte value.
::This is encoded in a macro way to be called asynchronously with start cmd /c
::Teamwork of carlos, penpen, aGerman, dbenham, einstein1969
::Tested under Win7 and XP
setlocal disableDelayedExpansion
set ^"genchr=(^
for /l %%N in (%%A !cnt! 255) do (^
if %%N equ 26 (^
copy /y nul + nul /a 26.bf_chr /a ^>nul^
) else (if %%N geq 35 if %%N leq 126 if %%N neq 61 (^
^<nul set /p "=!ascii:~%%N,1!" ^>%%N.bf_chr^
))^&^
if not exist %%N.bf_chr (^
makecab /d compress=off /d reserveperdatablocksize=26 /d reserveperfoldersize=%%N %%A.tmp %%N.bf_chr ^>nul^&^
type %%N.bf_chr ^| ((for /l %%n in (1 1 38) do pause)^>nul^&findstr "^^" ^>%%N.temp)^&^
^>nul copy /y %%N.temp /a %%N.bf_chr /b^&^
del %%N.temp^
)^
))^&^
del %%A.tmp^"
del /f /q /a *bf.chr >nul 2>&1
set "ascii= #$%%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~"
set /a cnt=number_of_processors
if %cnt% lss 1 set cnt=1
if %cnt% gtr 256 set cnt=256
set /a "end=cnt-1"
for /l %%A in (0 1 %end%) do (
type nul >%%A.tmp
if %%A equ %end% (
cmd /q /v:on /c "%genchr%"
) else (
start "" /b cmd /q /v:on /c "%genchr%"
)
)
:genAllChr.check
for /l %%N in (0 1 %end%) do if exist %%N.tmp goto :genAllChr.check
exit /b
Dave Benham
Re: BrainF*** Interpreter in Batch
Dave, I am a little confused by your last post:
I am confused specifically about which ones of the points you presented before are new features in your version 5.
The idea of concatenate several repeated operators and execute they with a count is present since my Version 2.0 and your first version based on that:
For example, this code: ">>>>>>" is executed as: "set /a mp+=6"
"Optimization collapses [-] into a special clear value op". This feature first appeared in my version 2.1:
I am afraid I don't understand what you mean with "Consecutive + - and [-] are concatenated into one op". For example, this code "++++++ ----" could be concatenated into one "set /A m[%mp%]+=2" (or several >>>> followed by <<<<<< could be concatenated into one "set /A mp-=2"); however, such code have no sense and should not appear in any well-written BF program. The only useful combination of this type is place several +++ or --- after the current cell was cleared: "[-]+++..." or "[-]---..." that may be collapsed into a single "set /A m[%mp%]=N", as described in my version 2.1.
The execution of "[" and "]" is performed via an "if" command, not a "set /A" one, so I don't understand what you mean with: "Each of the following can be expressed as a single SET /A expression: + - < > [ ] [-]" or "Also, + - [-] can be combined with any one of the following: < > [ ]". How do you combine a "[" or "]" with "+" or "-" in a single SET /A expression?
Really, the only new feature here is to combine several "+++" or "---" followed by several ">>>>" or "<<<<" in a single "set /A m[%mp%]+=3, mp+=4". Note that the opposite order (first modify mp, then modify m[%mp%]) is NOT possible in the same SET /A command.
So finally, I want to state the most confusing point of your post:
This speed difference is noted when you compare your new version 5 vs. which one version?. I really want to know which ones of the previous points have your prior version! Is hard to me to belive that just by grouping the "+++" or "---" followed by ">>>>" or "<<<<" in the same SET /A commands the program run twice as fast!!!
Antonio
dbenham wrote:
It makes a HUGE difference. The triangle is twice as fast on my machine. And hanoi is nearly twice as fast, without bothering to optimize the code page size.
I completely redesigned most of the op codes. Each of the following can be expressed as a single SET /A expression, expressed as an S op code:
+
-
<
>
[
]
[-]
The following can be concatenated indefinitely:
+
-
[-]
Also, the above can be combined with any one of the following:
<
>
[
]
I am confused specifically about which ones of the points you presented before are new features in your version 5.
The idea of concatenate several repeated operators and execute they with a count is present since my Version 2.0 and your first version based on that:
dbenham wrote:Great ideas Antonio - consolidating consecutive identical ops into one op with a count does make a huge performance difference
For example, this code: ">>>>>>" is executed as: "set /a mp+=6"
"Optimization collapses [-] into a special clear value op". This feature first appeared in my version 2.1:
Aacini wrote:Code: Select all
rem Version 2.1: - Small bug fixed when "*" or "~" characters appear in the input file
rem - Delete *all* variables, excepting the parsed program code and "PATH"
rem - Optimize "[-]" loop as m[%mp%]=0
rem - Optimize "[-]+++..." or "[-]---..." constructs as m[%mp%]=N or m[%mp%]=-N
I am afraid I don't understand what you mean with "Consecutive + - and [-] are concatenated into one op". For example, this code "++++++ ----" could be concatenated into one "set /A m[%mp%]+=2" (or several >>>> followed by <<<<<< could be concatenated into one "set /A mp-=2"); however, such code have no sense and should not appear in any well-written BF program. The only useful combination of this type is place several +++ or --- after the current cell was cleared: "[-]+++..." or "[-]---..." that may be collapsed into a single "set /A m[%mp%]=N", as described in my version 2.1.
The execution of "[" and "]" is performed via an "if" command, not a "set /A" one, so I don't understand what you mean with: "Each of the following can be expressed as a single SET /A expression: + - < > [ ] [-]" or "Also, + - [-] can be combined with any one of the following: < > [ ]". How do you combine a "[" or "]" with "+" or "-" in a single SET /A expression?
Really, the only new feature here is to combine several "+++" or "---" followed by several ">>>>" or "<<<<" in a single "set /A m[%mp%]+=3, mp+=4". Note that the opposite order (first modify mp, then modify m[%mp%]) is NOT possible in the same SET /A command.
So finally, I want to state the most confusing point of your post:
dbenham wrote:It makes a HUGE difference. The triangle is twice as fast on my machine. And hanoi is nearly twice as fast, without bothering to optimize the code page size.
This speed difference is noted when you compare your new version 5 vs. which one version?. I really want to know which ones of the previous points have your prior version! Is hard to me to belive that just by grouping the "+++" or "---" followed by ">>>>" or "<<<<" in the same SET /A commands the program run twice as fast!!!
Antonio
-
einstein1969
- Expert
- Posts: 960
- Joined: 15 Jun 2012 13:16
- Location: Italy, Rome
Re: BrainF*** Interpreter in Batch
Antonio,
Your version use a similar RLE compression on the code. This Is HUGE increment in execution too!
The version 4 and previus of dbenham use your tecnic.
The version 5 merge two consecutive instruction into one.
+ instruction with + instruction for example is not existent due your RLE compression on the code.
Other combination of code is considerated and if possible the code execute two instruction on one cycle.
Example of code:
This use 1 SET instead of 2 SET for cycle.
You used this tecnic in your work!
the version 5.0 is about double fast respect the version 4.0
Einstein1969
Your version use a similar RLE compression on the code. This Is HUGE increment in execution too!
The version 4 and previus of dbenham use your tecnic.
The version 5 merge two consecutive instruction into one.
+ instruction with + instruction for example is not existent due your RLE compression on the code.
Other combination of code is considerated and if possible the code execute two instruction on one cycle.
Example of code:
Code: Select all
c[0]=S "mp+=1"
c[10]=S "mp+=2"
c[11]=S "m[!mp!]=(m[!mp!]+2)&255,mp+=3"
c[12]=S "m[!mp!]=(m[!mp!]+1)&255,mp+=3"
c[13]=S "m[!mp!]=(m[!mp!]+1)&255,mp-=10"
c[14]=S "ip+=^!m[!mp!]*66"
c[15]=S "m[!mp!]=(m[!mp!]-1)&255,ip+=^!m[!mp!]*3"
c[16]=S "m[!mp!]=(m[!mp!]-1)&255,mp+=1"
c[17]=S "m[!mp!]=(m[!mp!]+1)&255,mp-=1"
c[18]=S "ip-=^!^!m[!mp!]*3"
c[19]=S "mp+=1"
c[1]=S "m[!mp!]=(m[!mp!]+4)&255,ip+=^!m[!mp!]*3"
c[20]=S "ip+=^!m[!mp!]*5"
c[21]=S "m[!mp!]=(m[!mp!]-1)&255,mp-=1"
c[22]=S "m[!mp!]=(m[!mp!]+1)&255,mp+=3"
c[23]=. 1
c[24]=S "mp-=2"
c[25]=S "ip-=^!^!m[!mp!]*5"
c[26]=S "mp+=3"
c[27]=S "ip+=^!m[!mp!]*24"
c[28]=S "ip+=^!m[!mp!]*22"
c[29]=S "m[!mp!]=(m[!mp!]-1)&255,mp+=1"
c[2]=S "mp-=1"
c[30]=S "m[!mp!]=(m[!mp!]+8)&255,ip+=^!m[!mp!]*3"
c[31]=S "mp+=1"
c[32]=S "m[!mp!]=(m[!mp!]+4)&255,mp-=1"
c[33]=S "m[!mp!]=(m[!mp!]-1)&255,ip-=^!^!m[!mp!]*3"
c[34]=S "mp+=1"
c[35]=. 1
c[36]=S "mp-=2"
c[37]=S "ip+=^!m[!mp!]*3"
c[38]=S "m[!mp!]=(m[!mp!]-1)&255,mp+=1"
c[39]=S "m[!mp!]=(m[!mp!]+1)&255,mp-=1"
c[3]=S "m[!mp!]=(m[!mp!]+8)&255,mp+=1"
c[40]=S "ip-=^!^!m[!mp!]*3"
c[41]=S "m[!mp!]=(m[!mp!]+1)&255,mp+=1"
c[42]=S "ip+=^!m[!mp!]*4"
c[43]=S "m[!mp!]=(m[!mp!]-1)&255,mp+=1"
c[44]=S "m[!mp!]=(m[!mp!]+10)&255,mp-=2"
c[45]=S "m[!mp!]=(m[!mp!]+1)&255,mp+=1"
c[46]=S "ip-=^!^!m[!mp!]*4"
c[47]=S "mp+=1"
c[48]=. 1
c[49]=S "m[!mp!]=0,mp+=1"
c[4]=S "m[!mp!]=(m[!mp!]-1)&255,ip-=^!^!m[!mp!]*3"
This use 1 SET instead of 2 SET for cycle.
You used this tecnic in your work!
the version 5.0 is about double fast respect the version 4.0
Einstein1969
-
einstein1969
- Expert
- Posts: 960
- Joined: 15 Jun 2012 13:16
- Location: Italy, Rome
Re: BrainF*** Interpreter in Batch
dbenham wrote::shock: Pipelining operations into one cycle - great idea
It makes a HUGE difference. The triangle is twice as fast on my machine. And hanoi is nearly twice as fast, without bothering to optimize the code page size.
I completely redesigned most of the op codes. Each of the following can be expressed as a single SET /A expression, expressed as an S op code:
+
-
<
>
[
]
[-]
The following can be concatenated indefinitely:
+
-
[-]
Also, the above can be combined with any one of the following:
<
>
[
]
The code stored for each cycle is significantly greater. But most cycles pipeline at least 2 operations, so there are significantly fewer lines. The interpreter macro is much smaller (and faster). It only has to define at most 4 operations: S . , # It may have as few as two: S and .
I did not take the time to figure out an optimal code page size - I kept the default at 100. I suspect it should be smaller.
Another optimization I made is to completely wipe out the environment at the start of the interpreter macro, except for the code and a few constants. I had to include the full path to XCOPY and FINDSTR in the macro since PATH is no longer defined. It looks odd that the macro erases itself, but it works.
So here is my version 5. I've done even less testing than before. I won't be surprised if I've managed to break one of the options.
...
Dave Benham
wow wow wow!
We have doubled the previus speed!
Next step? a little more speed. This is very difficult... but we will do!
The execution of Hanoi_MOD.bf is now fast but more speed is necessary for a reasonable speed (for demo porpouse)
How increment the speed?
These are some tricks:
- - problem with TMP/TEMP/USERPROFILE and FOR/F
I think that may set TMP=C:\ or other short path and leave the TMP variable.
(about 5-10% OFF) - - use the counter of infinite loop. This drop off one variable in some cases. Examples for variable "cycles"
- - Remove other not used variables.
- - Fine Tuning for Order of variable in the environment. Variables most used at the TOP.
- - Reduce dimension of variables name and code for example C_1223=S ...
- - It is possible merge 3 instructions into one?
- - Other Ideas?
EDIT : the set /a ip+=1 instruction can be merged with precedence SET and replicated. The performance could be increase.
einstein1969
Last edited by einstein1969 on 23 Jul 2014 09:21, edited 3 times in total.
Re: BrainF*** Interpreter in Batch
@Antonio
Your optimization to combine consecutive like operations into a single operation was a first critical step. But it never performs more than one computation per cycle (disregarding input/output). A given cycle either manipulates the value of m[mp], or the value of mp, or the value of ip. It never combines the computations.
einstein1969's idea to combine multiple computations into one SET /A statement was another critical step. Especially when I realized I could implement [ and ] as a single SET /A computation. The performance gain arises in three ways:
1) SET /A "A+=5,B+=10" is faster than SET /A "A+=5" & SET /A "B+=10"
2) + - < > [ ] 0 are now all represented as a single S op instead of as 7 distinct ops. This makes the interpreter macro smaller, and therefor faster.
3) Because multiple computations are combined into a single complex S op, there are significantly fewer cycles, again improving performance.
My version 5 also throws in the optimization of undefining nearly all variables at the start of the interpreter, leaving just code and a few constants.
Here is the triangle.bf test program:
Here is the result running my version 4:
And here is the result running my version 5
Notice the large discrepancy in the number of cycles.
Here is the derived macro interpreter for version 4 (bf4.txt)
Here is the derived macro interpreter for version 5 (bf5.txt)
A significant reduction in complexity!
Here is the derived instruction set for version 4 (triangle4.txt)
Here is the derived instruction set for version 5 (triangle5.txt)
More memory due to more complex notation, but more than compensated for by efficiency of fewer lines of code, as well as efficiency of combining multiple computations in one SET /A.
Dave Benham
Your optimization to combine consecutive like operations into a single operation was a first critical step. But it never performs more than one computation per cycle (disregarding input/output). A given cycle either manipulates the value of m[mp], or the value of mp, or the value of ip. It never combines the computations.
einstein1969's idea to combine multiple computations into one SET /A statement was another critical step. Especially when I realized I could implement [ and ] as a single SET /A computation. The performance gain arises in three ways:
1) SET /A "A+=5,B+=10" is faster than SET /A "A+=5" & SET /A "B+=10"
2) + - < > [ ] 0 are now all represented as a single S op instead of as 7 distinct ops. This makes the interpreter macro smaller, and therefor faster.
3) Because multiple computations are combined into a single complex S op, there are significantly fewer cycles, again improving performance.
My version 5 also throws in the optimization of undefining nearly all variables at the start of the interpreter, leaving just code and a few constants.
Here is the triangle.bf test program:
Code: Select all
[ This program prints Sierpinski triangle on 80-column display. ]
>
+ +
+ +
[ < + +
+ +
+ + + +
> - ] >
+ + + + + + + +
[ >
+ + + +
< - ] >
> + + > > > + >
> > + <
< < < < < < < <
< [ - [ - > + <
] > [ - < + > > > . < < ] > > >
[ [
- > + +
+ + + +
+ + [ > + + + +
< - ] >
. < < [ - > + <
] + > [ - > + +
+ + + + + + + + < < + > ] > . [
- ] > ]
] + < < < [ - [
- > + < ] + > [
- < + > > > - [ - > + < ] + + >
[ - < - > ] < <
< ] < < < < ] + + + + + + + + +
+ . + + + . [ - ] < ] + + + + +
* * * * * M a d e * B y : * N Y Y R I K K I * 2 0 0 2 * * * * *
Here is the result running my version 4:
Code: Select all
D:\test\bf>bf4 triangle.bf -c "" -m bf4.txt -d triangle4.txt
----------------------------
Begin Initialization
Testing ASCII character files.
Parsing code.
Elapsed time = 0.38 s
Initialization complete
============================
*
* *
* *
* * * *
* *
* * * *
* * * *
* * * * * * * *
* *
* * * *
* * * *
* * * * * * * *
* * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
* *
* * * *
* * * *
* * * * * * * *
* * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
* * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
============================
Elapsed time = 16.40 s
cycles=51913 codePageFaults=
arraySize=107 arrayPageFaults=
And here is the result running my version 5
Code: Select all
D:\test\bf>bf5 triangle.bf -c "" -m bf5.txt -d triangle5.txt
----------------------------
Begin Initialization
Testing ASCII character files.
Parsing code.
Elapsed time = 0.42 s
Initialization complete
============================
*
* *
* *
* * * *
* *
* * * *
* * * *
* * * * * * * *
* *
* * * *
* * * *
* * * * * * * *
* * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
* *
* * * *
* * * *
* * * * * * * *
* * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
* * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
============================
Elapsed time = 7.92 s
cycles=33623 codePageFaults=
arraySize=107 arrayPageFaults=
Notice the large discrepancy in the number of cycles.
Here is the derived macro interpreter for version 4 (bf4.txt)
Code: Select all
bfInterpreter=
set /a "ip=mp=cdCnt=cycles=aCnt=aSize=0"
for /l %%. in () do for %%I in (!ip!) do (
for /f "tokens=1-3" %%A in ("!mp! !c[%%I]!") do (
if not defined m[%%A] set /a m[%%A]=0, aSize+=1
if "%%B" equ "+" (
set /a "m[%%A]=(m[%%A]+%%C)&255"
) else if "%%B" equ "-" (
set /a "m[%%A]=(m[%%A]-%%C)&255"
) else if "%%B" equ "0" (
set "m[%%A]=0"
) else if "%%B" equ ">" (
set /a "mp+=%%C"
) else if "%%B" equ "<" (
set /a "mp-=%%C"
) else if "%%B" equ "[" (
if "!m[%%A]!" equ "0" set "ip=%%C"
) else if "%%B" equ "]" (
if "!m[%%A]!" neq "0" set "ip=%%C"
) else if "%%B" equ "." for /l %%N in (1 1 %%C) do (
if "!m[%%A]!" equ "26" (set /p "=!SUB!" <nul) else type !m[%%A]!.bf_chr
) else (
>stats.bf_tmp (echo cycles=!cycles! codePageFaults=!codePageFaults!
echo arraySize=!aSize! arrayPageFaults=!arrayPageFaults!)
exit 0
)
set /a ip+=1, cycles+=1
)
)
Here is the derived macro interpreter for version 5 (bf5.txt)
Code: Select all
bfInterpreter=
for /f "delims==" %%V in ('set^|findstr /bv "c[ line1= CR= SUB="') do set "%%V="
set /a "ip=mp=cdCnt=cycles=aCnt=aSize=over=0"
for /l %%. in () do for %%I in (!ip!) do (
for /f "tokens=1-3" %%A in ("!mp! !c[%%I]!") do (
if not defined m[%%A] set /a m[%%A]=0, aSize+=1
if "%%B" equ "S" (
set /a "%%C"
) else if "%%B" equ "." for /l %%N in (1 1 %%C) do (
if "!m[%%A]!" equ "26" (set /p "=!SUB!" <nul) else type !m[%%A]!.bf_chr
) else (
>stats.bf_tmp (echo cycles=!cycles! codePageFaults=!codePageFaults!
echo arraySize=!aSize! arrayPageFaults=!arrayPageFaults!)
exit 0
)
set /a ip+=1, cycles+=1
)
)
A significant reduction in complexity!
Here is the derived instruction set for version 4 (triangle4.txt)
Code: Select all
c[0]=> 1
c[1]=+ 4
c[2]=[ 7
c[3]=< 1
c[4]=+ 8
c[5]=> 1
c[6]=- 1
c[7]=] 2
c[8]=> 1
c[9]=+ 8
c[10]=[ 15
c[11]=> 1
c[12]=+ 4
c[13]=< 1
c[14]=- 1
c[15]=] 10
c[16]=> 2
c[17]=+ 2
c[18]=> 3
c[19]=+ 1
c[20]=> 3
c[21]=+ 1
c[22]=< 10
c[23]=[ 119
c[24]=- 1
c[25]=[ 30
c[26]=- 1
c[27]=> 1
c[28]=+ 1
c[29]=< 1
c[30]=] 25
c[31]=> 1
c[32]=[ 39
c[33]=- 1
c[34]=< 1
c[35]=+ 1
c[36]=> 3
c[37]=. 1
c[38]=< 2
c[39]=] 32
c[40]=> 3
c[41]=[ 76
c[42]=[ 75
c[43]=- 1
c[44]=> 1
c[45]=+ 8
c[46]=[ 51
c[47]=> 1
c[48]=+ 4
c[49]=< 1
c[50]=- 1
c[51]=] 46
c[52]=> 1
c[53]=. 1
c[54]=< 2
c[55]=[ 60
c[56]=- 1
c[57]=> 1
c[58]=+ 1
c[59]=< 1
c[60]=] 55
c[61]=+ 1
c[62]=> 1
c[63]=[ 70
c[64]=- 1
c[65]=> 1
c[66]=+ 10
c[67]=< 2
c[68]=+ 1
c[69]=> 1
c[70]=] 63
c[71]=> 1
c[72]=. 1
c[73]=0
c[74]=> 1
c[75]=] 42
c[76]=] 41
c[77]=+ 1
c[78]=< 3
c[79]=[ 112
c[80]=- 1
c[81]=[ 86
c[82]=- 1
c[83]=> 1
c[84]=+ 1
c[85]=< 1
c[86]=] 81
c[87]=+ 1
c[88]=> 1
c[89]=[ 110
c[90]=- 1
c[91]=< 1
c[92]=+ 1
c[93]=> 3
c[94]=- 1
c[95]=[ 100
c[96]=- 1
c[97]=> 1
c[98]=+ 1
c[99]=< 1
c[100]=] 95
c[101]=+ 2
c[102]=> 1
c[103]=[ 108
c[104]=- 1
c[105]=< 1
c[106]=- 1
c[107]=> 1
c[108]=] 103
c[109]=< 3
c[110]=] 89
c[111]=< 4
c[112]=] 79
c[113]=+ 10
c[114]=. 1
c[115]=+ 3
c[116]=. 1
c[117]=0
c[118]=< 1
c[119]=] 23
c[120]=+ 5
Here is the derived instruction set for version 5 (triangle5.txt)
Code: Select all
c[0]=S "mp+=1"
c[1]=S "m[!mp!]=(m[!mp!]+4)&255,ip+=^!m[!mp!]*3"
c[2]=S "mp-=1"
c[3]=S "m[!mp!]=(m[!mp!]+8)&255,mp+=1"
c[4]=S "m[!mp!]=(m[!mp!]-1)&255,ip-=^!^!m[!mp!]*3"
c[5]=S "mp+=1"
c[6]=S "m[!mp!]=(m[!mp!]+8)&255,ip+=^!m[!mp!]*3"
c[7]=S "mp+=1"
c[8]=S "m[!mp!]=(m[!mp!]+4)&255,mp-=1"
c[9]=S "m[!mp!]=(m[!mp!]-1)&255,ip-=^!^!m[!mp!]*3"
c[10]=S "mp+=2"
c[11]=S "m[!mp!]=(m[!mp!]+2)&255,mp+=3"
c[12]=S "m[!mp!]=(m[!mp!]+1)&255,mp+=3"
c[13]=S "m[!mp!]=(m[!mp!]+1)&255,mp-=10"
c[14]=S "ip+=^!m[!mp!]*66"
c[15]=S "m[!mp!]=(m[!mp!]-1)&255,ip+=^!m[!mp!]*3"
c[16]=S "m[!mp!]=(m[!mp!]-1)&255,mp+=1"
c[17]=S "m[!mp!]=(m[!mp!]+1)&255,mp-=1"
c[18]=S "ip-=^!^!m[!mp!]*3"
c[19]=S "mp+=1"
c[20]=S "ip+=^!m[!mp!]*5"
c[21]=S "m[!mp!]=(m[!mp!]-1)&255,mp-=1"
c[22]=S "m[!mp!]=(m[!mp!]+1)&255,mp+=3"
c[23]=. 1
c[24]=S "mp-=2"
c[25]=S "ip-=^!^!m[!mp!]*5"
c[26]=S "mp+=3"
c[27]=S "ip+=^!m[!mp!]*24"
c[28]=S "ip+=^!m[!mp!]*22"
c[29]=S "m[!mp!]=(m[!mp!]-1)&255,mp+=1"
c[30]=S "m[!mp!]=(m[!mp!]+8)&255,ip+=^!m[!mp!]*3"
c[31]=S "mp+=1"
c[32]=S "m[!mp!]=(m[!mp!]+4)&255,mp-=1"
c[33]=S "m[!mp!]=(m[!mp!]-1)&255,ip-=^!^!m[!mp!]*3"
c[34]=S "mp+=1"
c[35]=. 1
c[36]=S "mp-=2"
c[37]=S "ip+=^!m[!mp!]*3"
c[38]=S "m[!mp!]=(m[!mp!]-1)&255,mp+=1"
c[39]=S "m[!mp!]=(m[!mp!]+1)&255,mp-=1"
c[40]=S "ip-=^!^!m[!mp!]*3"
c[41]=S "m[!mp!]=(m[!mp!]+1)&255,mp+=1"
c[42]=S "ip+=^!m[!mp!]*4"
c[43]=S "m[!mp!]=(m[!mp!]-1)&255,mp+=1"
c[44]=S "m[!mp!]=(m[!mp!]+10)&255,mp-=2"
c[45]=S "m[!mp!]=(m[!mp!]+1)&255,mp+=1"
c[46]=S "ip-=^!^!m[!mp!]*4"
c[47]=S "mp+=1"
c[48]=. 1
c[49]=S "m[!mp!]=0,mp+=1"
c[50]=S "ip-=^!^!m[!mp!]*22"
c[51]=S "ip-=^!^!m[!mp!]*24"
c[52]=S "m[!mp!]=(m[!mp!]+1)&255,mp-=3"
c[53]=S "ip+=^!m[!mp!]*21"
c[54]=S "m[!mp!]=(m[!mp!]-1)&255,ip+=^!m[!mp!]*3"
c[55]=S "m[!mp!]=(m[!mp!]-1)&255,mp+=1"
c[56]=S "m[!mp!]=(m[!mp!]+1)&255,mp-=1"
c[57]=S "ip-=^!^!m[!mp!]*3"
c[58]=S "m[!mp!]=(m[!mp!]+1)&255,mp+=1"
c[59]=S "ip+=^!m[!mp!]*13"
c[60]=S "m[!mp!]=(m[!mp!]-1)&255,mp-=1"
c[61]=S "m[!mp!]=(m[!mp!]+1)&255,mp+=3"
c[62]=S "m[!mp!]=(m[!mp!]-1)&255,ip+=^!m[!mp!]*3"
c[63]=S "m[!mp!]=(m[!mp!]-1)&255,mp+=1"
c[64]=S "m[!mp!]=(m[!mp!]+1)&255,mp-=1"
c[65]=S "ip-=^!^!m[!mp!]*3"
c[66]=S "m[!mp!]=(m[!mp!]+2)&255,mp+=1"
c[67]=S "ip+=^!m[!mp!]*3"
c[68]=S "m[!mp!]=(m[!mp!]-1)&255,mp-=1"
c[69]=S "m[!mp!]=(m[!mp!]-1)&255,mp+=1"
c[70]=S "ip-=^!^!m[!mp!]*3"
c[71]=S "mp-=3"
c[72]=S "ip-=^!^!m[!mp!]*13"
c[73]=S "mp-=4"
c[74]=S "ip-=^!^!m[!mp!]*21"
c[75]=S "m[!mp!]=(m[!mp!]+10)&255"
c[76]=. 1
c[77]=S "m[!mp!]=(m[!mp!]+3)&255"
c[78]=. 1
c[79]=S "m[!mp!]=0,mp-=1"
c[80]=S "ip-=^!^!m[!mp!]*66"
c[81]=S "m[!mp!]=(m[!mp!]+5)&255"
More memory due to more complex notation, but more than compensated for by efficiency of fewer lines of code, as well as efficiency of combining multiple computations in one SET /A.
Dave Benham
Re: BrainF*** Interpreter in Batch
Dave:
I already knew most parts of your explanation. After understood it, I think the most important point in your version 5 is what I asked this way:
... that in your previous explanation appear this way:
But you did NOT explained how this is achieved! (It is obvious, jeb?
)
After reviewed the code generated by the macro interpreter of version 5, I realized that this code:
... (that imply a change in IP to an absolute address) may be executed in a single SET /A command changing the absolute address by an offset relative to current IP, and then conditionally add it to IP via "!" operator:
And this is a REALLY CLEVER IDEA!
Antonio
I already knew most parts of your explanation. After understood it, I think the most important point in your version 5 is what I asked this way:
Aacini wrote:The execution of "[" and "]" is performed via an "if" command, not a "set /A" one, so I don't understand what you mean with: "Each of the following can be expressed as a single SET /A expression: + - < > [ ] [-]" or "Also, + - [-] can be combined with any one of the following: < > [ ]". How do you combine a "[" or "]" with "+" or "-" in a single SET /A expression?
... that in your previous explanation appear this way:
dbenham wrote:einstein1969's idea to combine multiple computations into one SET /A statement was another critical step. Especially when I realized I could implement [ and ] as a single SET /A computation.
But you did NOT explained how this is achieved! (It is obvious, jeb?
)After reviewed the code generated by the macro interpreter of version 5, I realized that this code:
Code: Select all
) else if "%%B" equ "[" (
if "!m[%%A]!" equ "0" set "ip=%%C"
... (that imply a change in IP to an absolute address) may be executed in a single SET /A command changing the absolute address by an offset relative to current IP, and then conditionally add it to IP via "!" operator:
Code: Select all
set /A "ip+=^!m[!mp!]*3"
And this is a REALLY CLEVER IDEA!
Antonio
-
einstein1969
- Expert
- Posts: 960
- Joined: 15 Jun 2012 13:16
- Location: Italy, Rome
Re: BrainF*** Interpreter in Batch
Few consideration about final performance tuning.
When the performance are near the top one might think that every thing that you will not produce a big change.
But it is not. Just because we are a low consumption of CPU every little achievement is very much in proportion.
einstein1969
When the performance are near the top one might think that every thing that you will not produce a big change.
But it is not. Just because we are a low consumption of CPU every little achievement is very much in proportion.
einstein1969
Re: BrainF*** Interpreter in Batch
I've implemented the following enhancements for version 6:
1) Keyboard input was extracted from the main interpreter macro and moved to a CALLed subroutine. This doesn't help hanoi or the triangle, but it provides a major performance boost for computationally intense programs that also require keyboard input because the main loop is much smaller. Since the program will be waiting for user input anyway, the slight delay introduced by CALL should be unnoticeable. The subroutine is immediately below the interpreter loop to maximize performance.
2) I implemented einstein1969's idea to use the outer FOR /L loop to track the cycle count and implement the limit. This is an obvious optimization that I should have thought of. It think it boosts performance a bit, but I'm not sure. It certainly isn't a significant improvement. The default limit is 0x80000000, which results in an infinite loop. The high positive value can never be reached because the signed value roles over to a negative number after 0x7FFFFFFF.
version 6
Dave Benham
1) Keyboard input was extracted from the main interpreter macro and moved to a CALLed subroutine. This doesn't help hanoi or the triangle, but it provides a major performance boost for computationally intense programs that also require keyboard input because the main loop is much smaller. Since the program will be waiting for user input anyway, the slight delay introduced by CALL should be unnoticeable. The subroutine is immediately below the interpreter loop to maximize performance.
2) I implemented einstein1969's idea to use the outer FOR /L loop to track the cycle count and implement the limit. This is an obvious optimization that I should have thought of. It think it boosts performance a bit, but I'm not sure. It certainly isn't a significant improvement. The default limit is 0x80000000, which results in an infinite loop. The high positive value can never be reached because the signed value roles over to a negative number after 0x7FFFFFFF.
version 6
Code: Select all
::BF.BAT - BrainF*** interpreter in Batch, dbenham version 6.0
::
:: Usage:
::
:: bf sourceFile [-option [value]]...
::
:: Options
::
:: -i Filename = read Input from file Filename.
::
:: -z = <Ctrl-Z> terminates keyboard input (forces EOF).
::
:: -e Value = EOF value: Sets value read into memory upon End-Of-File.
:: Default is no change to memory.
::
:: -ee = terminate with Error if attempt is made to read past EOF.
::
:: -eo = terminate with Error if +/- results in Overflow.
::
:: -em = terminate with Error if < yields a negative Memory address.
::
:: -ea = terminate with Error on Any fault. Same as -ee -eo -em
::
:: -s = Silent mode. Don't print initialization messages, elapsed
:: times, or run statistics. Also disables the -l option.
::
:: -d Filename = Dump the parsed op codes to Filename.
:: Use con to print to screen.
::
:: -m Filename = write the interpreter Macro to Filename.
:: Use con to print to screen.
::
:: -t = Trace mode: Show op address/value, memory address/value
:: each cycle.
::
:: -# Count = Enables # op: Show current state. Count specifies the number
:: of values to display before and after the current address.
:: BUG ALERT: Some array values may not display properly if
:: Count > 0 and array members are swapped out to disk. This is
:: never a problem if -a is undefined.
::
:: -p = Parse only.
::
:: -c Count = Code memory (default = 100). Maximum amount of code allowed
:: to reside in memory at one time. Unlimited if undefined.
:: Excess code is swapped out to disk.
::
:: -a Count = Array memory (default = unlimited). Maximum number of array
:: members allowed to reside in memory at one time. Unlimited
:: if undefined. Excess array members are swapped out to disk.
::
:: -l Count = Limit the number of execution cycles to Count.
:: Default is no limit (0x80000000).
::
:: The memory array consists of unsigned bytes. Increment and decrement
:: operations simply wrap when the limits are exceeded unless -eo is specified.
::
:: The memory array is unbounded both to the left and right. If -em is specified
:: then the array is unbounded to the right only.
::
:: In theory, the code pointer can range from 0 to 2147483647,
:: and the memory pointer can range from -2147483648 to 2147483647.
:: But performance will become unbearably long before those limits are
:: reached.
::
:: BF.BAT can only read input from a file supplied as a command line option, or
:: the keyboard. Input will fail if data is piped into BF.BAT or if stdin is
:: redirected to a file.
::
:: During keyboard input, the <Enter> key is read as <CR>. All other inputs are
:: normal. Any byte value (except 0x00) may be entered by holding down the <Alt>
:: key and entering a decimal code on the numeric keypad. The only way to enter
:: <LF> is via <Alt> and the numeric keypad.
::
:: This code was written by Dave Benham (aka dbenham)
:: with major contributions from Antonio Perez Ayala (aka Aacini),
:: and einstein1969.
::
:: Development efforts can be traced at
:: http://www.dostips.com/forum/viewtopic.php?f=3&t=5751
@echo off
:: Rentry point when running the bf program
if "%~1" equ ":run" (
%_bf_Interpreter%
exit 0
) %_bf_input%
if 1==0 (
:getInput
::
%_bf_getInputSub%
exit /b
)
:: Clear environment except for critical standard values
setlocal disableDelayedExpansion
for /f "eol== delims==" %%V in ('set^|findstr /rc:"^[^=]*!"') do set "%%V="
set "preserve= TEMP TMP PATH PATHEXT COMSPEC PRESERVE "
setlocal enableDelayedExpansion
for /f "eol== delims==" %%V in ('set') do (
if defined %%V if "!preserve: %%V =!" equ "!preserve!" set "%%V="
)
set "preserve="
:: Validate parameters
if "%~1" equ "" >&2 echo Usage: %~N0 filename.ext&exit /b 1
if not exist "%~1" >&2 echo File not found: %1&exit /b 1
:: Define options
set options=-d:"" -s: -z: -e:"" -m:"" -ee: -eo: -em: -ea: -t: -#:"" -p: -i:"" -c:100 -a:"" -l:0x80000000
:: Set option defaults
for %%O in (%options%) do for /f "tokens=1,* delims=:" %%A in ("%%O") do set "%%A=%%~B"
:loop Parse the option arguments
if not "%~2"=="" (
set "test=!options:*%~2:=! "
if "!test!"=="!options! " (
echo Error: Invalid option %~2
exit /b 1
) else if "!test:~0,1!"==" " (
set "%~2=1"
) else (
set "%~2=%~3"
shift /2
)
shift /2
goto :loop
)
:: Begin macro defnitions --------------
:: Define LF to contain a linefeed (0x0A) character
set ^"LF=^
^" The above empty line is critical - DO NOT REMOVE
:: define a newline with line continuation
set ^"\n=^^^%LF%%LF%^%LF%%LF%^^"
set showTime=(%\n%
for /f "tokens=1-4 delims=:.," %%a in ("^!t1: =0^!"^) do set /a "t1=(((1%%a*60)+1%%b)*60+1%%c)*100+1%%d-36610100"%\n%
for /f "tokens=1-4 delims=:.," %%a in ("^!t2: =0^!"^) do set /a "t2=(((1%%a*60)+1%%b)*60+1%%c)*100+1%%d-36610100"%\n%
set /a "tDiff=t2-t1"%\n%
if ^^!tDiff^^! lss 0 set /a tDiff+=24*60*60*100%\n%
set /a "s=tDiff/100, f=tDiff+100"%\n%
echo Elapsed time = ^^!s^^!.^^!f:~-2^^! s%\n%
^)
if defined -ea (
set -eo=1
set -em=1
set -ee=1
)
if defined -eo (
set "inc=over|=(m[^^^!mp^^^!]+=^!count^!)&-256"
set "dec=over|=(m[^^^!mp^^^!]-=^!count^!)&-256"
set overError=%\n%
if ^^!over^^! neq 0 ^>^&2 echo ^^!LF^^!ERROR: Overflow at ip=%%I mp=%%A^&exit 1
) else (
set "inc=m[^^^!mp^^^!]=(m[^^^!mp^^^!]+^!count^!)&255"
set "dec=m[^^^!mp^^^!]=(m[^^^!mp^^^!]-^!count^!)&255"
)
if defined -em (
set leftError=%\n%
if ^^!mp^^! lss 0 ^>^&2 echo ^^!LF^^!ERROR: Invalid memory access at ip=%%I mp=%%A^&exit 1
)
if defined -t set trace=%\n%
echo c[%%I]=^^!c[%%I]^^! m[%%A]=^^!m[%%A]^^!
if defined -e set ^"setEOF=set /a "m[%%A]=!-e!"^"
if defined -z set eofMacros=1
if defined -i set eofMacros=1
if defined eofMacros (
set "ifNotEOF=if not defined EOF"
set ifSub=else if "^!key:~-1^!" equ "^!SUB^!" (%\n%
endlocal^&endlocal%\n%
set EOF=1%\n%
!setEOF!%\n%
^)
if defined -ee (
set "elsePastEOF= else >&2 echo ^!LF^!ERROR: Read past EOF at ip=%%I mp=%%A&exit 1 "
) else if defined -e (
set "elsePastEOF= else !setEOF! "
)
)
if defined -i (
set ^"getInput=else if "%%B" equ "," ( for /l %%N in (1 1 %%C^) do !ifNotEOF! (%\n%
set "key="%\n%
set /p "key="%\n%
if defined key (set /a "m[%%A]=0x^!key^!"^) else ( !setEOF!%\n%
set EOF=1%\n%
^)%\n%
^)!elsePastEOF!^) ^"
) else for %%F in (findstr.exe) do (
set ^"getInput=else if "%%B" equ "," (%\n%
call :getInput%\n%
^) ^"
set ^"_bf_getInputSub= for %%. in (x^) do for /l %%N in (1 1 %%C^) do !ifNotEOF! (%\n%
set "key="%\n%
set "CtrlC=1"%\n%
setlocal disableDelayedExpansion%\n%
for /f "delims=" %%K in (%\n%
'^^^^^""%%~dp$path:Fxcopy.exe" /w "%~f0" "%~f0" 2^^^^^>nul^^^^^"'%\n%
^) do if not defined key (set "key=%%K"^) else set "CtrlC="%\n%
setlocal enableDelayedExpansion%\n%
if defined CtrlC (%\n%
endlocal^&endlocal%\n%
set "m[%%A]=3"%\n%
^) else if "^!key^!" equ "^!line1^!" (%\n%
endlocal^&endlocal%\n%
set "m[%%A]=10"%\n%
^) else if "^!key:~-1^!" equ "^!CR^!" (%\n%
endlocal^&endlocal%\n%
set "m[%%A]=13"%\n%
^) !ifSub! else (%\n%
^>key.bf_tmp echo(^^!key:~-1^^!%\n%
endlocal^&endlocal%\n%
for /f "delims=." %%K in ('^^^^^""%%~$path:F" /lg:key.bf_tmp *.bf_chr^^^^^"'^) do set "m[%%A]=%%K"%\n%
^)%\n%
^)!elsePastEOF!^"
)
if defined -# (
set #=#
set #Parse=else if "%%b" equ "#" (%\n%
if defined lastCmd (%\n%
set /a ip+=1%\n%
^>c[^^!ip^^!].bf_tmp echo S "^^!lastCmd:~0,-1^^!"%\n%
set "lastCmd="%\n%
^)%\n%
set /a "ip+=1, #Found=1, clr=0"%\n%
^>c[^^!ip^^!].bf_tmp echo #%\n%
^)
if !-#! equ 0 (
set ^"#Exec=else if "%%B" equ "#" (%\n%
set /a next=ip+1%\n%
set "msg="%\n%
^<c[^^!next^^!].bf_tmp set /p "msg="%\n%
echo c[^^!next^^!]=^^!msg^^! m[%%A]=^^!m[%%A]^^!%\n%
^) ^"
) else set ^"#Exec=else if "%%B" equ "#" (%\n%
set /a next=ip+1, m1=mp-!-#!, m2=mp-1, m3=mp+1, m4=mp+!-#!%\n%
set "msg="%\n%
^<c[^^!next^^!].bf_tmp set /p "msg="%\n%
set "msg=c[^!next^!]=^!msg^! mp=%%A: "%\n%
for /l %%N in (^^!m1^^! 1 ^^!m2^^!^) do set "msg=^!msg^!| ^!m[%%N]^! "%\n%
set "msg=^!msg^!< ^!m[%%A]^! >"%\n%
for /l %%N in (^^!m3^^! 1 ^^!m4^^!^) do set "msg=^!msg^! ^!m[%%N]^! |"%\n%
echo ^^!msg^^!%\n%
^) ^"
)
if not defined -s (
set "getCodePageFaults=, codePageFaults+=1"
set "getArrayStats=, aSize+=1"
set "getArrayPageFaults=, arrayPageFautls+=1"
set showStats=%\n%
^>stats.bf_tmp (echo cycles=%%. codePageFaults=^^!codePageFaults^^!%\n%
echo arraySize=^^!aSize^^! arrayPageFaults=^^!arrayPageFaults^^!^)
if "!-l!" neq "0x80000000" set limitStats=%\n%
for %%. in (!-l!^) do (!showStats!%\n%
^)
)
if defined -c set codePaging=%\n%
if not defined c[%%I] if exist c[%%I].bf_tmp (%\n%
if ^^!cdCnt^^! equ !-c! (%\n%
for /f "delims==" %%A in ('set c[') do set "%%A="%\n%
set cdCnt=0%\n%
)%\n%
set /a cdCnt+=1!getCodePageFaults!%\n%
^<c[%%I].bf_tmp set /p "c[%%I]="%\n%
)
if defined -a (
set arrayPaging=if not defined m[%%A] (%\n%
if ^^!aCnt^^! equ !-a! for /f "tokens=1,2 delims==" %%a in ('set m['^) do (%\n%
^>%%a.bf_tmp echo %%b%\n%
set %%a=%\n%
set aCnt=0%\n%
^)%\n%
if exist m[%%A].bf_tmp (%\n%
^<m[%%A].bf_tmp set /p m[%%A]=%\n%
set /a arrayPageFaults+=1%\n%
^) else set /a m[%%A]=0!getArrayStats!%\n%
set /a aCnt+=1%\n%
^)
) else set "arrayPaging=if not defined m[%%A] set /a m[%%A]=0!getArrayStats!"
:: End macro definition ------------------
:: Create character files if they don't already exist
if not defined -s (
echo ----------------------------
echo Begin Initialization
echo Testing ASCII character files.
)
set "needChars="
for /l %%N in (0 1 255) do for %%F in (%%N.bf_chr) do if "%%~zF" neq "1" set "needChars=1"
if defined needChars (
if not defined -s (
echo Creating ASCII character files...
set "t1=!time!"
)
call :genAllChr
if not defined -s (
set t2=!time!
%showTime%
)
)
:: Parse the input file
if not defined -i goto :skipInput
if not defined -s (
<nul set /p "=Parsing input."
set t1=!time!
)
if not exist "!-i!" >&2 echo ERROR: Input file "!-i!" not found & exit 1
if exist "!-i!\" >&2 echo ERROR: Input file "!-i!" not found & exit 1
copy 0.bf_chr compare.bf_tmp >nul
set /a size=skipStart=1
for %%F in ("!-i!") do set inSize=%%~zF
for /l %%N in (1 1 32) do if !size! lss !inSize! set /a "size*=2" & type compare.bf_tmp >>compare.bf_tmp
fc /b "!-i!" compare.bf_tmp | findstr /rxc:"........: .. .." >diff.bf_tmp
>input.bf_tmp (
for /f "tokens=1,2 delims=:[] " %%A in (diff.bf_tmp) do (
set /a skipEnd=0x%%A
for /l %%N in (!skipStart! 1 !skipEnd!) do echo 00
echo %%B
set /a skipStart=skipEnd+2
if "!skipStart:~-3!" equ "000" <nul set /p "=." >&2
)
for /l %%N in (!skipStart! 1 !inSize!) do echo 00
)
set "_bf_input=<input.bf_tmp"
if not defined -s (
set t2=!time!
echo(
%showTime%
)
:skipInput
:: Parse the code. Consecutive op codes are coalesced into one op with a count.
:: Optionally treats # as an additional show state op code (withoug coalesce).
:: Optimization collapses [-] into a special clear value op.
:: + - < > [ ] [-] are all converted into an S op followed by a SET /A expression.
:: Consecutive + - and [-] are concatenated into one op. If followed by
:: < > [ or ] then that op is also concatenated, but that is the limit for one op.
:: . and , are stored as themselves, followed by the count.
:: # is stored as itself without a count
:: Detects if input is not used so getInput can be removed from interpreter loop.
:: Treats loops at beginning or immedieately following ] as comments (ignores them)
if not defined -s (
<nul set /p "=Parsing code."
set "parseProgress=set /a n=(n+1^^)%%500&if ^!n^! equ 0 <nul set /p "=.""
set "t1=!time!"
)
2>nul del c[*.bf_tmp
for %%C in (+ - "<" ">" . "," #) do set "comment%%~C=0"
set /a ip=comment]=-1, sp=count=comment=0, comment[=1
cmd /u /c type %1|find /v ""|findstr "[+\-<>.,[\]!#!]" >src.bf_tmp
for /f %%b in (src.bf_tmp) do ( %parseProgress%
if !comment! gtr 0 (
set /a comment+=!comment%%b!
) else if "!lastOp!" equ "%%b" (
set /a count+=1
) else (
if defined lastOp (
set "test="
if !clr! equ 1 if !lastOp! equ - if !count! equ 1 set /a clr=test=2
if not defined test set clr=0
if "!lastOp!" equ "+" (
set "lastCmd=!lastCmd!%inc%,"
) else if "!lastOp!" equ "-" (
set "lastCmd=!lastCmd!!delim!%dec%,"
) else (
set /a ip+=1
if "!lastOp!" equ ">" (
>c[!ip!].bf_tmp echo S "!lastCmd!mp+=!count!"
) else if "!lastOp!" equ "<" (
>c[!ip!].bf_tmp echo S "!lastCmd!mp-=!count!"
) else (
if defined lastCmd (
>c[!ip!].bf_tmp echo S "!lastCmd:~0,-1!"
set /a ip+=1
)
>c[!ip!].bf_tmp echo !lastOp! !count!
)
set "lastCmd="
)
set "lastOp="
)
if "%%b" equ "[" (
if defined comment (set /a comment+=1) else (
set /a "ip+=1, sp+=1, clr=1"
set /a "stack[!sp!]=ip"
set "stackCmd[!sp!]=!lastCmd!"
set "lastCmd="
)
) else if "%%b" equ "]" for %%s in (!sp!) do (
if !clr! equ 2 (
set "lastCmd=!stackCmd[%%s]!m[^!mp^!]=0,"
set /a "ip-=1, sp-=1"
) else (
set /a ip+=1, sp-=1, count=ip-stack[%%s]
>c[!ip!].bf_tmp echo S "!lastCmd!ip-=^^^!^^^!m[^!mp^!]*!count!"
>c[!stack[%%s]!].bf_tmp echo S "!stackCmd[%%s]!ip+=^^^!m[^!mp^!]*!count!"
set "lastCmd="
)
set /a "clr=comment=0"
) %#Parse% else (
set "comment="
set "lastOp=%%b"
set /a "count=1"
if "%%b" equ "," set inputRequired=1
)
)
)
if defined lastOp (
set /a ip+=1
(
if "!lastOp!" equ "+" (
echo S "!lastCmd!%inc%"
) else if "!lastOp!" equ "-" (
echo S "!lastCmd!%dec%"
) else if "!lastOp!" equ ">" (
echo S "!lastCmd!mp+=!count!"
) else if "!lastOp!" equ "<" (
echo S "!lastCmd!mp-=!count!"
) else (
echo S "!lastCmd:~0,-1!"
echo !lastOp! !count!
)
)>c[!ip!].bf_tmp
) else if defined lastCmd (
set /a ip+=1
>c[!ip!].bf_tmp echo S "!lastCmd:~0,-1!"
)
if not defined -s (
set "t2=!time!"
echo(
%showTime%
)
:: Error if unbalanced brackets
if %sp% neq 0 >&2 echo ERROR: Unbalanced brackets&exit /b 1
if defined comment if "%comment%" neq "0" >&2 echo ERROR: Unbalanced brackets&exit /b 1
:: Dump the parsed op codes
if defined -d (for /l %%N in (0 1 !ip!) do (
<c[%%N].bf_tmp set /p "msg="
echo c[%%N]=!msg!
)) >"!-d!"
:: Disable code paging if code length does not exceed -cp
if not defined -c set "-c=!ip!
if !ip! leq !-c! (
set "codePaging="
for /l %%N in (0 1 !ip!) do <c[%%N].bf_tmp set /p "c[%%N]="
)
:: Undefine getInput and/or #Parse if not needed
if not defined inputRequired set "getInput=" & set "_bf_getInputSub="
if not defined #Found set "#Exec="
:: Define CR to hold <CarriageReturn> for use in input routine
for /f %%A in ('copy /Z "%~dpf0" nul') do set "CR=%%A"
:: Define SUB to hold <0x1A>
for /f "delims=" %%A in (26.bf_chr) do set "SUB=%%A"
:: Establish line one of input routine for this locale
set "line1="
for /f "delims=" %%L in (
'echo .^|xcopy /w "%~f0" "%~f0" 2^>nul'
) do if not defined line1 set "line1=%%L"
set "line1=!line1:~0,-1!"
:: Create final interpreter macro
set _bf_Interpreter=^
for /f "delims==" %%V in ('set ^^^^^|findstr /brc:"[^^ ]*=" ^^^^^|findstr /blv "c[ line1= CR= SUB= _bf_getInputSub="') do set "%%V="%\n%
set /a "ip=mp=cdCnt=cycles=aCnt=aSize=over=0"%\n%
for /l %%. in (0 1 !-l!) do for %%I in (^^!ip^^!) do (!codePaging!%\n%
for /f "tokens=1-3" %%A in ("^!mp^! ^!c[%%I]^!") do (%\n%
!arrayPaging!!trace!%\n%
if "%%B" equ "S" (%\n%
set /a "%%C"!overError!!leftError!%\n%
) else if "%%B" equ "." for /l %%N in (1 1 %%C) do (%\n%
if "^!m[%%A]^!" equ "26" (set /p "=^!SUB^!" ^<nul) else type ^^!m[%%A]^^!.bf_chr%\n%
) !getInput!!#Exec!else (!showStats!%\n%
exit 0%\n%
)%\n%
set /a ip+=1%\n%
)%\n%
)!limitStats!
:: Print out the finalized brainF*** interpreter macro
if defined -m >"!-m!" (
echo - - - - - - - - - - - - - - - - - - - - - -
echo _bf_Interpreter=!lf!!_bf_Interpreter:%%=%%%%!
if defined _bf_getInputSub (
echo - - - - - - - - - - - - - - - - - - - - - -
echo _bf_getInputSub=!lf!!_bf_getInputSub:%%=%%%%!
)
echo - - - - - - - - - - - - - - - - - - - - - -
)
if not defined -s (
echo Initialization complete
echo ============================
set t1=%time%
)
(call )
if defined -p goto :quit
:: Launch the interpreter
cmd /v:on /c "%~f0" :run&&(call )||(call)
set "err=%errolevel%
if not defined -s (
set t2=%time%
echo(
echo ============================
%showTime%
if exist stats.bf_tmp type stats.bf_tmp
)
:quit
del *.bf_tmp
exit /b %err%
:genAllChr
::This code creates 256 1 byte files, one for each possible byte value.
::This is encoded in a macro way to be called asynchronously with start cmd /c
::Teamwork of carlos, penpen, aGerman, dbenham, einstein1969
::Tested under Win7 and XP
setlocal disableDelayedExpansion
set ^"genchr=(^
for /l %%N in (%%A !cnt! 255) do (^
if %%N equ 26 (^
copy /y nul + nul /a 26.bf_chr /a ^>nul^
) else (if %%N geq 35 if %%N leq 126 if %%N neq 61 (^
^<nul set /p "=!ascii:~%%N,1!" ^>%%N.bf_chr^
))^&^
if not exist %%N.bf_chr (^
makecab /d compress=off /d reserveperdatablocksize=26 /d reserveperfoldersize=%%N %%A.tmp %%N.bf_chr ^>nul^&^
type %%N.bf_chr ^| ((for /l %%n in (1 1 38) do pause)^>nul^&findstr "^^" ^>%%N.temp)^&^
^>nul copy /y %%N.temp /a %%N.bf_chr /b^&^
del %%N.temp^
)^
))^&^
del %%A.tmp^"
del /f /q /a *bf.chr >nul 2>&1
set "ascii= #$%%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~"
set /a cnt=number_of_processors
if %cnt% lss 1 set cnt=1
if %cnt% gtr 256 set cnt=256
set /a "end=cnt-1"
for /l %%A in (0 1 %end%) do (
type nul >%%A.tmp
if %%A equ %end% (
cmd /q /v:on /c "%genchr%"
) else (
start "" /b cmd /q /v:on /c "%genchr%"
)
)
:genAllChr.check
for /l %%N in (0 1 %end%) do if exist %%N.tmp goto :genAllChr.check
exit /b
Dave Benham