BrainZ

BrainZ (say "Brain zee") is a brainfuck equivalent created by User:None1. It is brainfuck compressed with Huffman compression.

Steps to write a program

1. Write a program in brainfuck, we take the cat program

+[,.]

as an example.

2. Convert the program to binary using the following table.

BrainZ	Brainfuck
1	+
01	-
001	>
0001	<
00001	[
000001	]
0000001	.
00000001	,

In the example, we get:

100001000000010000001000001

3. Group the bits 8 by 8 and convert them into bytes, if the number of bits is not a multiple of 8, Then just add zeros in the end until it is (these zeros will not affect the program's behavior, since all the commands in BrainZ ends with 1), then you get a valid BrainZ program.

In the example, we get (in hex dump):

84 04 08 20

Here is an encoder in Python, it generates raw bytes of BrainZ programs from brainfuck programs, making the conversion easier.

def encode(bf):
    d='+-><[].,'
    r=''
    res=[]
    for i in bf:
        r+='0'*d.index(i)+'1'
    r+='0'*((-len(r))%8)
    for i in range(len(r)//8):
        res.append(int(r[i*8:i*8+8],2))
    return bytes(res)

Compression Rate

In the best case (when all the commands are +), its compression rate is 12.5%.

In the worst case (when all the commands are ,), its compression rate is 100%.

However, in most brainfuck programs, + exists more frequently than -, which exists more frequently than >, which exists more frequently than <, which exists more frequently than [ and ], which exists more frequently than ., which exists more frequently than ,. That makes its performace better, and much better than the compression method used in Binaryfuck.

Example Programs

The following programs are in hex dump.

Cat Program

84 04 08 20

Hello World

FF 09 F0 9C F3 CC 44 45 04 CC A4 C2 20 8A 09 20 4A A0 7F 81 03 C0 92 04 50 22 07 81 55 50 2A AA A0 49 81 38 10

The program is 37 bytes long, compressed from this brainfuck program:

++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.

as a comparison, the same program compressed with Binaryfuck, is 40 bytes long.

Nope. interpreter

FC 27 FF E2 82 40 9F FE 13 FF 8A 09 81 81 55 55 54 09 F8 4F FC 50 4C 08

brainfuck interpreter

24 C2 14 12 42 83 99 FE 11 F2 71 41 C9 99 F8 4E 7F 11 41 92 40 47 08 48 52 41 10 92 08 8A 08 84 41 19 21 20 90 8C A1 08 CA 09 04 42 10 A0 88 38 A1 1F F9 08 A5 04 90 49 04 11 10 44 11 08 44 12 10 90 49 09 20 C2 22 08 84 41 19 28 24 24 18 52 41 11 11 08 44 41 10 88 31 10 CC 45 09 53 11 42 62 12 62 28 20 82 42 32 82 20 E4 A9 09 04 90 92 08 22 21 26 21 08 82 20 90 84 44 11 08 83 0A 32 50 88 CE 50 8A 42 23 25 04 10 44 26 28 24 12 12 09 04 84 90 49 04 44 24 C9 92 08 88 52 49 24 90 44 42 40 92 49 24 11 10 94 92 48 22 21 20 24 90 44 42 64 11 10 C4 41 10 40

Made from this brainfuck self interpreter.

Turing completeness

It is of course Turing complete since brainfuck is.