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