commit fab3f1f6d96baa1752fe19789a6612bea4e3ccfb from: Omar Polo date: Wed Apr 27 18:39:18 2022 UTC initial import commit - /dev/null commit + fab3f1f6d96baa1752fe19789a6612bea4e3ccfb blob - /dev/null blob + 7e53061603dc8609f052bbd8a3be3f5ff01ca0b1 (mode 644) --- /dev/null +++ README.md @@ -0,0 +1,15 @@ +bfc -- a brainfuck compiler +=========================== + +bfc is a simple brainfuck compiler. It's written in Haskell because I +hate myself and outputs QBE because why not. + +Usage: + + $ bfc sources... > program.ssa + $ qbe program.ssa > program.S + $ cc -o program program.S && ./prog + +bfc reads from standard input if no arguments are given. + +bfc is release into the public domain. blob - /dev/null blob + cf65bfa5442dfa6cf9332c970fce8fb384d45dcd (mode 644) --- /dev/null +++ bfc.hs @@ -0,0 +1,194 @@ +-- This is free and unencumbered software released into the public domain. +-- +-- Anyone is free to copy, modify, publish, use, compile, sell, or +-- distribute this software, either in source code form or as a compiled +-- binary, for any purpose, commercial or non-commercial, and by any +-- means. +-- +-- In jurisdictions that recognize copyright laws, the author or authors +-- of this software dedicate any and all copyright interest in the +-- software to the public domain. We make this dedication for the benefit +-- of the public at large and to the detriment of our heirs and +-- successors. We intend this dedication to be an overt act of +-- relinquishment in perpetuity of all present and future rights to this +-- software under copyright law. +-- +-- THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +-- EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF +-- MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. +-- IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR +-- OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, +-- ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +-- OTHER DEALINGS IN THE SOFTWARE. +-- +-- For more information, please refer to + +module Main where + +import Text.Printf +import System.Environment as E + +data Token = Plus + | Minus + | Lesser + | Greater + | Point + | Comma + | BracketOpen + | BracketClose + deriving (Eq, Show) + +tokenize :: String -> [Token] +tokenize (x:xs) = + let table = [ ('-', Minus), ('+', Plus) + , ('<', Lesser), ('>', Greater) + , ('.', Point), (',', Comma) + , ('[', BracketOpen), (']', BracketClose) ] + token = lookup x table in + case token of + Just x -> x:(tokenize xs) + Nothing -> tokenize xs +tokenize _ = [] + +data Expr = Inc + | Dec + | ShiftLeft + | ShiftRight + | Input + | Output + | Loop [Expr] + deriving (Eq, Show) + +type AST = [Expr] + +data State = State ([AST], [Token]) deriving (Show) + +initialState tokens = State ([[]], tokens) + +finalize (State ([x], _)) = Just x +finalize _ = Nothing + +simplexpr :: Expr -> [AST] -> [Token] -> State +simplexpr e (x:xs) tokens = State ((x ++ [e]):xs, tokens) + +translate :: Token -> Expr +translate x = case x of + Plus -> Inc + Minus -> Dec + Lesser -> ShiftLeft + Greater -> ShiftRight + Point -> Output + Comma -> Input + +parser :: State -> Maybe State +parser (State (stack, (x:xs))) = + case x of + BracketOpen -> parser $ State ([]:stack, xs) + BracketClose -> case stack of + (y:ys) -> parser $ simplexpr (Loop y) (ys) xs + _ -> Nothing + _ -> parser $ simplexpr (translate x) stack xs +parser state = Just state + +parse :: [Token] -> Maybe AST +parse tokens = parser (initialState tokens) >>= finalize + +prologue = "export function w $main() {\n" ++ + "@start\n" ++ + " %.1 =l alloc8 8\n" ++ + " storel $tape, %.1" +epilogue = " ret 0\n" ++ + "}\n" ++ + "data $tape = align 8 { z 4096 }" + +-- subset of QBE that I need to convert the AST to +data Instruction = StoreW (Int, Int) -- storew a, b + | StoreL (Int, Int) -- storel a, b + | LoadW (Int, Int) -- a =w loadw b + | LoadL (Int, Int) -- a =w loadl b + | AddW (Int, Int, Int) -- a =w add b, c + | AddL (Int, Int, Int) -- a =l add b, c + | SubW (Int, Int, Int) -- a =w sub b, c + | SubL (Int, Int, Int) -- a =l sub b, c + | Call0 (Int, String) -- a =w call $b() + | Call1 (Int, String, Int) -- a =w call $b(w c) + | Jmp (Int) -- jmp a + | Jnz (Int, Int, Int) -- jnz a, @loop.b, @loop.c + | Label (Int) -- @loop.a + deriving (Eq) + +instance Show Instruction where + show x = + case x of + StoreW (a, b) -> printf " storew %%.%d, %%.%d" a b + StoreL (a, b) -> printf " storel %%.%d, %%.%d" a b + LoadW (a, b) -> printf " %%.%d =w loadw %%.%d" a b + LoadL (a, b) -> printf " %%.%d =l loadl %%.%d" a b + AddW (a, b, c) -> printf " %%.%d =w add %%.%d, %d" a b c + AddL (a, b, c) -> printf " %%.%d =l add %%.%d, %d" a b c + SubW (a, b, c) -> printf " %%.%d =w sub %%.%d, %d" a b c + SubL (a, b, c) -> printf " %%.%d =l sub %%.%d, %d" a b c + Call0 (a, fn) -> printf " %%.%d =w call $%s()" a fn + Call1 (a, fn, b) -> printf " %%.%d =w call $%s(w %%.%d)" a fn b + Jmp (a) -> printf " jmp @loop.%d" a + Jnz (a, b, c) -> printf " jnz %%.%d, @loop.%d, @loop.%d" a b c + Label (a) -> printf "@loop.%d" a + +-- I'm keeping the pointer to the current cell in the "%.1" +-- intermediary. It's always there because qbe allows to +-- storel %.X %.1 +-- even if it's a SSA. +cell = 1 + +compile' :: Int -> Int -> [AST] -> [[Instruction]] -> [Instruction] +compile' n h ((x:xs):ys) trail = + case x of + Inc -> LoadL(n+1, cell) : + LoadW(n+2, n+1) : + AddW(n+3, n+2, 1) : + StoreW(n+3, n+1) : + compile' (n+3) h (xs:ys) trail + Dec -> LoadL(n+1, cell) : + LoadW(n+2, n+1) : + SubW(n+3, n+2, 1) : + StoreW(n+3, n+1) : + compile' (n+3) h (xs:ys) trail + ShiftLeft -> LoadL(n+1, cell) : + SubL(n+2, n+1, 4) : + StoreL(n+2, cell) : + compile' (n+2) h (xs:ys) trail + ShiftRight -> LoadL(n+1, cell) : + AddL(n+2, n+1, 4) : + StoreL(n+2, cell) : + compile' (n+2) h (xs:ys) trail + Input -> Call0(n+1, "getchar") : + LoadL(n+2, cell) : + StoreW(n+1, n+2) : + compile' (n+2) h (xs:ys) trail + Output -> LoadL(n+1, cell) : + LoadW(n+2, n+1) : + Call1(n+3, "putchar", n+2) : + compile' (n+3) h (xs:ys) trail + Loop (ast) -> Label(h) : + LoadL(n+1, cell) : + LoadW(n+2, n+1) : + Jnz(n+2, h+1, h+2) : + Label(h+1) : + compile' (n+3) (h+3) (ast:(xs:ys)) ([Jmp(h), Label(h+2)]:trail) +compile' n h ([]:ys) (t:ts) = t ++ (compile' n h ys ts) +compile' _ _ _ _ = [] + +compile ast = compile' 1 1 [ast] [] + +compileProg program = do + let t = parse $ tokenize program in + case t of + Just ast -> do putStrLn prologue + mapM_ print (compile ast) + putStrLn epilogue + Nothing -> error "Compilation failed" + +parseArgs [] = getContents +parseArgs path = concat `fmap` mapM readFile path + +main = E.getArgs >>= parseArgs >>= compileProg blob - /dev/null blob + 9ec84d54e5ce9718bda83843c881e285d69c8cd0 (mode 644) --- /dev/null +++ examples/99bottles.bf @@ -0,0 +1,230 @@ +> 0 in the zeroth cell ++++++++>++++++++++[<+++++>-] 57 in the first cell or "9" ++++++++>++++++++++[<+++++>-] 57 in second cell or "9" +++++++++++ 10 in third cell +>+++++++++ 9 in fourth cell + +########################################## +### create ASCII chars in higher cells ### +########################################## + +>>++++++++[<++++>-] " " +>++++++++++++++[<+++++++>-] b ++>+++++++++++[<++++++++++>-] o +++>+++++++++++++++++++[<++++++>-] t +++>+++++++++++++++++++[<++++++>-] t +>++++++++++++[<+++++++++>-] l ++>++++++++++[<++++++++++>-] e ++>+++++++++++++++++++[<++++++>-] s +>++++++++[<++++>-] " " ++>+++++++++++[<++++++++++>-] o +++>++++++++++[<++++++++++>-] f +>++++++++[<++++>-] " " +>++++++++++++++[<+++++++>-] b ++>++++++++++[<++++++++++>-] e ++>++++++++++[<++++++++++>-] e +>+++++++++++++++++++[<++++++>-] r +>++++++++[<++++>-] " " ++>+++++++++++[<++++++++++>-] o +>+++++++++++[<++++++++++>-] n +>++++++++[<++++>-] " " +++>+++++++++++++++++++[<++++++>-] t +++++>++++++++++[<++++++++++>-] h ++>++++++++++[<++++++++++>-] e +>++++++++[<++++>-] " " +++>+++++++++++++[<+++++++++>-] w ++>++++++++++++[<++++++++>-] a +>++++++++++++[<+++++++++>-] l +>++++++++++++[<+++++++++>-] l +>+++++[<++>-] LF +++>+++++++++++++++++++[<++++++>-] t ++>++++++++++++[<++++++++>-] a ++++>+++++++++++++[<++++++++>-] k ++>++++++++++[<++++++++++>-] e +>++++++++[<++++>-] " " ++>+++++++++++[<++++++++++>-] o +>+++++++++++[<++++++++++>-] n ++>++++++++++[<++++++++++>-] e +>++++++++[<++++>-] " " +>++++++++++[<++++++++++>-] d ++>+++++++++++[<++++++++++>-] o +++>+++++++++++++[<+++++++++>-] w +>+++++++++++[<++++++++++>-] n +>++++++++[<++++>-] " " ++>++++++++++++[<++++++++>-] a +>+++++++++++[<++++++++++>-] n +>++++++++++[<++++++++++>-] d +>++++++++[<++++>-] " " +++>+++++++++++[<++++++++++>-] p ++>++++++++++++[<++++++++>-] a ++>+++++++++++++++++++[<++++++>-] s ++>+++++++++++++++++++[<++++++>-] s +>++++++++[<++++>-] " " ++>+++++++++++++[<++++++++>-] i +++>+++++++++++++++++++[<++++++>-] t +>++++++++[<++++>-] " " ++>++++++++++++[<++++++++>-] a +>+++++++++++++++++++[<++++++>-] r ++>+++++++++++[<++++++++++>-] o +>+++++++++++++[<+++++++++>-] u +>+++++++++++[<++++++++++>-] n +>++++++++++[<++++++++++>-] d +>+++++[<++>-] LF ++++++++++++++ CR + +[<]>>>> go back to fourth cell + +################################# +### initiate the display loop ### +################################# + +[ loop + < back to cell 3 + [ loop + [>]<< go to last cell and back to LF + .. output 2 newlines + [<]> go to first cell + + ################################### + #### begin display of characters### + ################################### + # + #.>.>>>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.> + #X X b o t t l e s o f b e e r + #.>.>.>.>.>.>.>.>.>.>.>. + #o n t h e w a l l N + #[<]> go to first cell + #.>.>>>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>>>>>>>>>>>>>.> + #X X b o t t l e s o f b e e r N + #.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.> + #t a k e o n e d o w n a n d p a s s + #.>.>.>.>.>.>.>.>.>. + #i t a r o u n d N + ##### + + [<]>> go to cell 2 + - subtract 1 from cell 2 + < go to cell 1 + + ######################## + ### display last line ## + ######################## + # + #.>.>>>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.> + #X X b o t t l e s o f b e e r + #.>.>.>.>.>.>.>.>.>.>. + #o n t h e w a l l + ##### + + [<]>>>- go to cell 3/subtract 1 + ] end loop when cell 3 is 0 + ++++++++++ add 10 to cell 3 + <++++++++++ back to cell 2/add 10 + <- back to cell 1/subtract 1 + [>]<. go to last line/carriage return + [<]> go to first line + +######################## +### correct last line ## +######################## +# +#.>.>>>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.> +#X X b o t t l e s o f b e e r +#.>.>.>.>.>.>.>.>.>.>. +#o n t h e w a l l +##### + + [<]>>>>- go to cell 4/subtract 1 +] end loop when cell 4 is 0 + +############################################################## +### By this point verses 99\10 are displayed but to work ### +### with the lower numbered verses in a more readable way ### +### we initiate a new loop for verses 9{CODE} that will not ### +### use the fourth cell at all ### +############################################################## + ++ add 1 to cell four (to keep it non\zero) +<-- back to cell 3/subtract 2 + +[ loop + [>]<< go to last cell and back to LF + .. output 2 newlines + [<]> go to first cell + + ################################### + #### begin display of characters### + ################################### + # + #>.>>>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.> + # X b o t t l e s o f b e e r + #.>.>.>.>.>.>.>.>.>.>.>. + #o n t h e w a l l N + #[<]> go to first cell + #>.>>>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>>>>>>>>>>>>>.> + # X b o t t l e s o f b e e r N + #.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.> + #t a k e o n e d o w n a n d p a s s + #.>.>.>.>.>.>.>.>.>. + #i t a r o u n d N + ##### + + [<]>> go to cell 2 + - subtract 1 from cell 2 + + ######################## + ### display last line ## + ######################## + # + #.>>>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.> + #X b o t t l e s o f b e e r + #.>.>.>.>.>.>.>.>.>.>. + #o n t h e w a l l + ##### + + [<]>>>- go to cell 3/subtract 1 +] end loop when cell 3 is 0 ++ add 1 to cell 3 to keep it non\zero + +[>]<. go to last line/carriage return +[<]> go to first line + +######################## +### correct last line ## +######################## +# +#>.>>>.>.>.>.>.>.>.>>.>.>.>.>.>.>.>.>.> +# X b o t t l e o f b e e r +#.>.>.>.>.>.>.>.>.>.>.<<<<. +#o n t h e w a l l +##### + +[>]<< go to last cell and back to LF +.. output 2 newlines +[<]> go to first line + +######################### +### the final verse ## +######################### +# +#>.>>>.>.>.>.>.>.>.>>.>.>.>.>.>.>.>.>.> +# X b o t t l e o f b e e r +#.>.>.>.>.>.>.>.>.>.>.>. +#o n t h e w a l l N +#[<]> go to first cell +#>.>>>.>.>.>.>.>.>.>>.>.>.>.>.>.>.>.>>>>>>>>>>>>>.> +# X b o t t l e o f b e e r N +#.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.> +#t a k e o n e d o w n a n d p a s s +#.>.>.>.>.>.>.>.>.>. +#i t a r o u n d N +#[>]< go to last line +#<<<.<<.<<<. +# n o +#[<]>>>> go to fourth cell +#>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.>.> +# b o t t l e s o f b e e r +#.>.>.>.>.>.>.>.>.>.>.>. +#o n t h e w a l l N +#####fin## + blob - /dev/null blob + 8fa0f72a362699262c965323c432de18935d0e1b (mode 644) --- /dev/null +++ examples/hello-word.bf @@ -0,0 +1 @@ +++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++. blob - /dev/null blob + 7b510ed74549dbf8bfea54f569210d55c5d988fe (mode 644) --- /dev/null +++ examples/mandlebrot.bf @@ -0,0 +1,146 @@ + A mandelbrot set fractal viewer in brainfuck written by Erik Bosman ++++++++++++++[->++>>>+++++>++>+<<<<<<]>>>>>++++++>--->>>>>>>>>>+++++++++++++++[[ +>>>>>>>>>]+[<<<<<<<<<]>>>>>>>>>-]+[>>>>>>>>[-]>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>[-]+ +<<<<<<<+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>>>+>>>>>>>>>>>>>>>>>>>>>>>>>> +>+<<<<<<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+[>>>>>>[>>>>>>>[-]>>]<<<<<<<<<[<<<<<<<<<]>> +>>>>>[-]+<<<<<<++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>>+<<<<<<+++++++[-[->>> +>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>>+<<<<<<<<<<<<<<<<[<<<<<<<<<]>>>[[-]>>>>>>[>>>>> +>>[-<<<<<<+>>>>>>]<<<<<<[->>>>>>+<<+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>> +[>>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<+<<]>>>>>>>>]<<<<<<<<<[<<<<<<< +<<]>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<<<]>>>>>>>>>+++++++++++++++[[ +>>>>>>>>>]+>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[ +>+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>[-<<<<+>>>>]<<<<[->>>>+<<<<<[->>[ +-<<+>>]<<[->>+>>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<< +<<[>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<< +[>[-]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+<<<<<<<<<]>>>>> +>>>>[>+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+ +<<<<<<[->>>[-<<<+>>>]<<<[->>>+>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>> +>>>>>>>]<<<<<<<<<[>>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<<]>>[->>>>>>>>>+<<<<<<<<<]<< ++>>>>>>>>]<<<<<<<<<[>[-]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<< +<]<+<<<<<<<<<]>>>>>>>>>[>>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>> +>>>>>>>>>>>>>>>>>>>>>>>]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>> +>>>>>]<<<<<<<<<-<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+>>>>>>>>>>>>>>>>>>>>>+<<<[<<<<<< +<<<]>>>>>>>>>[>>>[-<<<->>>]+<<<[->>>->[-<<<<+>>>>]<<<<[->>>>+<<<<<<<<<<<<<[<<<<< +<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>[-<<<<->>>>]+<<<<[->>>>-<[-<<<+>>>]<<<[-> +>>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<< +<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]<<<<<<<[->+>>>-<<<<]>>>>>>>>>+++++++++++++++++++ ++++++++>>[-<<<<+>>>>]<<<<[->>>>+<<[-]<<]>>[<<<<<<<+<[-<+>>>>+<<[-]]>[-<<[->+>>>- +<<<<]>>>]>>>>>>>>>>>>>[>>[-]>[-]>[-]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-]>>>>>>[>>>>> +[-<<<<+>>>>]<<<<[->>>>+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>[-<<<<<<<< +<+>>>>>>>>>]>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>>>>>>>]+>[- +]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[>+>>>>>>>>]<<< +<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+<<<<<<[->>[-<<+>>]< +<[->>+>+<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[>[->>>> +>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[>[-]<->>> +[-<<<+>[<->-<<<<<<<+>>>>>>>]<[->+<]>>>]<<[->>+<<]<+<<<<<<<<<]>>>>>>>>>[>>>>>>[-< +<<<<+>>>>>]<<<<<[->>>>>+<<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>+>>>>>>>> +]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+<<<<<<[->>[-<<+ +>>]<<[->>+>>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[> +[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[>[- +]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+<<<<<<<<<]>>>>>>>>> +[>>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> +]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+> +>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>]>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>++++++++ ++++++++[[>>>>>>>>>]<<<<<<<<<-<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[>>>>>>>>[-<<<<<<<+ +>>>>>>>]<<<<<<<[->>>>>>>+<<<<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>>[ +-]>>>]<<<<<<<<<[<<<<<<<<<]>>>>+>[-<-<<<<+>>>>>]>[-<<<<<<[->>>>>+<++<<<<]>>>>>[-< +<<<<+>>>>>]<->+>]<[->+<]<<<<<[->>>>>+<<<<<]>>>>>>[-]<<<<<<+>>>>[-<<<<->>>>]+<<<< +[->>>>->>>>>[>>[-<<->>]+<<[->>->[-<<<+>>>]<<<[->>>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-] ++>>>>>>[>>>>>>>>>]>+<]]+>>>[-<<<->>>]+<<<[->>>-<[-<<+>>]<<[->>+<<<<<<<<<<<[<<<<< +<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<<<< +[<<<<<<<<<]>>>>[-<<<<+>>>>]<<<<[->>>>+>>>>>[>+>>[-<<->>]<<[->>+<<]>>>>>>>>]<<<<< +<<<+<[>[->>>>>+<<<<[->>>>-<<<<<<<<<<<<<<+>>>>>>>>>>>[->>>+<<<]<]>[->>>-<<<<<<<<< +<<<<<+>>>>>>>>>>>]<<]>[->>>>+<<<[->>>-<<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>>+<<<]<< +<<<<<<<<<<]>>>>[-]<<<<]>>>[-<<<+>>>]<<<[->>>+>>>>>>[>+>[-<->]<[->+<]>>>>>>>>]<<< +<<<<<+<[>[->>>>>+<<<[->>>-<<<<<<<<<<<<<<+>>>>>>>>>>[->>>>+<<<<]>]<[->>>>-<<<<<<< +<<<<<<<+>>>>>>>>>>]<]>>[->>>+<<<<[->>>>-<<<<<<<<<<<<<<+>>>>>>>>>>]>]<[->>>>+<<<< +]<<<<<<<<<<<]>>>>>>+<<<<<<]]>>>>[-<<<<+>>>>]<<<<[->>>>+>>>>>[>>>>>>>>>]<<<<<<<<< +[>[->>>>>+<<<<[->>>>-<<<<<<<<<<<<<<+>>>>>>>>>>>[->>>+<<<]<]>[->>>-<<<<<<<<<<<<<< ++>>>>>>>>>>>]<<]>[->>>>+<<<[->>>-<<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>>+<<<]<<<<<<< +<<<<<]]>[-]>>[-]>[-]>>>>>[>>[-]>[-]>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>[-< +<<<+>>>>]<<<<[->>>>+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[ +[>>>>>>>>>]+>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+ +[>+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>[-<<<<+>>>>]<<<<[->>>>+<<<<<[->> +[-<<+>>]<<[->>+>+<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<< +<[>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[ +>[-]<->>>[-<<<+>[<->-<<<<<<<+>>>>>>>]<[->+<]>>>]<<[->>+<<]<+<<<<<<<<<]>>>>>>>>>[ +>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>]> +>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>[-]>>>>+++++++++++++++[[>>>>>>>>>]<<<<<<<<<-<<<<< +<<<<[<<<<<<<<<]>>>>>>>>>-]+[>>>[-<<<->>>]+<<<[->>>->[-<<<<+>>>>]<<<<[->>>>+<<<<< +<<<<<<<<[<<<<<<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>[-<<<<->>>>]+<<<<[->>>>-<[- +<<<+>>>]<<<[->>>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>> +>>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-<<<+>>>]<<<[->>>+>>>>>>[>+>>> +[-<<<->>>]<<<[->>>+<<<]>>>>>>>>]<<<<<<<<+<[>[->+>[-<-<<<<<<<<<<+>>>>>>>>>>>>[-<< ++>>]<]>[-<<-<<<<<<<<<<+>>>>>>>>>>>>]<<<]>>[-<+>>[-<<-<<<<<<<<<<+>>>>>>>>>>>>]<]> +[-<<+>>]<<<<<<<<<<<<<]]>>>>[-<<<<+>>>>]<<<<[->>>>+>>>>>[>+>>[-<<->>]<<[->>+<<]>> +>>>>>>]<<<<<<<<+<[>[->+>>[-<<-<<<<<<<<<<+>>>>>>>>>>>[-<+>]>]<[-<-<<<<<<<<<<+>>>> +>>>>>>>]<<]>>>[-<<+>[-<-<<<<<<<<<<+>>>>>>>>>>>]>]<[-<+>]<<<<<<<<<<<<]>>>>>+<<<<< +]>>>>>>>>>[>>>[-]>[-]>[-]>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-]>[-]>>>>>[>>>>>>>[-<<<<< +<+>>>>>>]<<<<<<[->>>>>>+<<<<+<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>+>[-<-<<<<+>>>> +>]>>[-<<<<<<<[->>>>>+<++<<<<]>>>>>[-<<<<<+>>>>>]<->+>>]<<[->>+<<]<<<<<[->>>>>+<< +<<<]+>>>>[-<<<<->>>>]+<<<<[->>>>->>>>>[>>>[-<<<->>>]+<<<[->>>-<[-<<+>>]<<[->>+<< +<<<<<<<<<[<<<<<<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>[-<<->>]+<<[->>->[-<<<+>>>]< +<<[->>>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]< +<<<<<<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-<<<+>>>]<<<[->>>+>>>>>>[>+>[-<->]<[->+ +<]>>>>>>>>]<<<<<<<<+<[>[->>>>+<<[->>-<<<<<<<<<<<<<+>>>>>>>>>>[->>>+<<<]>]<[->>>- +<<<<<<<<<<<<<+>>>>>>>>>>]<]>>[->>+<<<[->>>-<<<<<<<<<<<<<+>>>>>>>>>>]>]<[->>>+<<< +]<<<<<<<<<<<]>>>>>[-]>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<<<]]>>>>[-<<<<+> +>>>]<<<<[->>>>+>>>>>[>+>>[-<<->>]<<[->>+<<]>>>>>>>>]<<<<<<<<+<[>[->>>>+<<<[->>>- +<<<<<<<<<<<<<+>>>>>>>>>>>[->>+<<]<]>[->>-<<<<<<<<<<<<<+>>>>>>>>>>>]<<]>[->>>+<<[ +->>-<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>+<<]<<<<<<<<<<<<]]>>>>[-]<<<<]>>>>[-<<<<+>> +>>]<<<<[->>>>+>[-]>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<<<]>>>>>>>>>[>>>>>> +>>>]<<<<<<<<<[>[->>>>+<<<[->>>-<<<<<<<<<<<<<+>>>>>>>>>>>[->>+<<]<]>[->>-<<<<<<<< +<<<<<+>>>>>>>>>>>]<<]>[->>>+<<[->>-<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>+<<]<<<<<<<< +<<<<]]>>>>>>>>>[>>[-]>[-]>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-]>[-]>>>>>[>>>>>[-<<<<+ +>>>>]<<<<[->>>>+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>>[-<<<<<+>>>>> +]<<<<<[->>>>>+<<<+<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>> +>>>>>]+>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[>+>> +>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>[-<<<<+>>>>]<<<<[->>>>+<<<<<[->>[-<<+ +>>]<<[->>+>>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[> +[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[>[- +]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+<<<<<<<<<]>>>>>>>>> +[>+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+<<<< +<<[->>>[-<<<+>>>]<<<[->>>+>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>> +>>>]<<<<<<<<<[>>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<<]>>[->>>>>>>>>+<<<<<<<<<]<<+>>> +>>>>>]<<<<<<<<<[>[-]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+ +<<<<<<<<<]>>>>>>>>>[>>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>> +>>>>>>>>>>>>>>>>>>>]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>>>>>> +>]<<<<<<<<<-<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+>>>>>>>>>>>>>>>>>>>>>+<<<[<<<<<<<<<] +>>>>>>>>>[>>>[-<<<->>>]+<<<[->>>->[-<<<<+>>>>]<<<<[->>>>+<<<<<<<<<<<<<[<<<<<<<<< +]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>[-<<<<->>>>]+<<<<[->>>>-<[-<<<+>>>]<<<[->>>+< +<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]> +>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>->>[-<<<<+>>>>]<<<<[->>>>+<<[-]<<]>>]<<+>>>>[-<<<< +->>>>]+<<<<[->>>>-<<<<<<.>>]>>>>[-<<<<<<<.>>>>>>>]<<<[-]>[-]>[-]>[-]>[-]>[-]>>>[ +>[-]>[-]>[-]>[-]>[-]>[-]>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>[-]>>>>]<<<<<<<<< +[<<<<<<<<<]>+++++++++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>+>>>>>>>>>+<<<<<<<< +<<<<<<[<<<<<<<<<]>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+[-]>>[>>>>>>>>>]<<<<< +<<<<[>>>>>>>[-<<<<<<+>>>>>>]<<<<<<[->>>>>>+<<<<<<<[<<<<<<<<<]>>>>>>>[-]+>>>]<<<< +<<<<<<]]>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+>>[>+>>>>[-<<<<->>>>]<<<<[->>> +>+<<<<]>>>>>>>>]<<+<<<<<<<[>>>>>[->>+<<]<<<<<<<<<<<<<<]>>>>>>>>>[>>>>>>>>>]<<<<< +<<<<[>[-]<->>>>>>>[-<<<<<<<+>[<->-<<<+>>>]<[->+<]>>>>>>>]<<<<<<[->>>>>>+<<<<<<]< ++<<<<<<<<<]>>>>>>>-<<<<[-]+<<<]+>>>>>>>[-<<<<<<<->>>>>>>]+<<<<<<<[->>>>>>>->>[>> +>>>[->>+<<]>>>>]<<<<<<<<<[>[-]<->>>>>>>[-<<<<<<<+>[<->-<<<+>>>]<[->+<]>>>>>>>]<< +<<<<[->>>>>>+<<<<<<]<+<<<<<<<<<]>+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>+<<< +<<[<<<<<<<<<]>>>>>>>>>[>>>>>[-<<<<<->>>>>]+<<<<<[->>>>>->>[-<<<<<<<+>>>>>>>]<<<< +<<<[->>>>>>>+<<<<<<<<<<<<<<<<[<<<<<<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>>>>[-< +<<<<<<->>>>>>>]+<<<<<<<[->>>>>>>-<<[-<<<<<+>>>>>]<<<<<[->>>>>+<<<<<<<<<<<<<<[<<< +<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<< +<<[<<<<<<<<<]>>>>[-]<<<+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>-<<<<<[<<<<<<< +<<]]>>>]<<<<.>>>>>>>>>>[>>>>>>[-]>>>]<<<<<<<<<[<<<<<<<<<]>++++++++++[-[->>>>>>>> +>+<<<<<<<<<]>>>>>>>>>]>>>>>+>>>>>>>>>+<<<<<<<<<<<<<<<[<<<<<<<<<]>>>>>>>>[-<<<<<< +<<+>>>>>>>>]<<<<<<<<[->>>>>>>>+[-]>[>>>>>>>>>]<<<<<<<<<[>>>>>>>>[-<<<<<<<+>>>>>> +>]<<<<<<<[->>>>>>>+<<<<<<<<[<<<<<<<<<]>>>>>>>>[-]+>>]<<<<<<<<<<]]>>>>>>>>[-<<<<< +<<<+>>>>>>>>]<<<<<<<<[->>>>>>>>+>[>+>>>>>[-<<<<<->>>>>]<<<<<[->>>>>+<<<<<]>>>>>> +>>]<+<<<<<<<<[>>>>>>[->>+<<]<<<<<<<<<<<<<<<]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[>[-]<- +>>>>>>>>[-<<<<<<<<+>[<->-<<+>>]<[->+<]>>>>>>>>]<<<<<<<[->>>>>>>+<<<<<<<]<+<<<<<< +<<<]>>>>>>>>-<<<<<[-]+<<<]+>>>>>>>>[-<<<<<<<<->>>>>>>>]+<<<<<<<<[->>>>>>>>->[>>> +>>>[->>+<<]>>>]<<<<<<<<<[>[-]<->>>>>>>>[-<<<<<<<<+>[<->-<<+>>]<[->+<]>>>>>>>>]<< +<<<<<[->>>>>>>+<<<<<<<]<+<<<<<<<<<]>+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>> ++>>>>>>>>>>>>>>>>>>>>>>>>>>>+<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>>[-<<<<<<->>>>>>]+< +<<<<<[->>>>>>->>[-<<<<<<<<+>>>>>>>>]<<<<<<<<[->>>>>>>>+<<<<<<<<<<<<<<<<<[<<<<<<< +<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>>>>>[-<<<<<<<<->>>>>>>>]+<<<<<<<<[->>>>>>>> +-<<[-<<<<<<+>>>>>>]<<<<<<[->>>>>>+<<<<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>> +>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>[-]<<<++++ ++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>->>>>>>>>>>>>>>>>>>>>>>>>>>>-<<<<<<[<<<< +<<<<<]]>>>] +