News Item: : Towards steganography I: a Brainfuck code generator and interpreter in VB.Net
(Category: Misc)
Posted by yiangos
Monday 06 July 2009 - 14:52:57

In order to develop the steganography project I described earlier, I'll need a class that can convert any given text to a Brainfuck program, and also to "run" such a program to reproduce the original text. It turns out, this is not that difficult.

The easier part is the interpreter. A Brainfuck program source code can have only 8 different characters, each of which stands for a different command. Also, Brainfuck assumes that there is a memory organized in 1 byte slots, an input stream and an output stream. Finally, there needs to be a command pointer, that points to the command being executed.

The output stream will be replaced by a string.

1. Protected _outStream As String

I won't deal with the input stream here, as the interpreter I need will only be used on programs that print "hard coded" strings.

The 1-byte memory slots will be simulated by an arraylist of integers. A 64-bit integer variable will play the role of the pointer, and another 64-bit integer will play the role of the command pointer.

1. Protected _mem As New ArrayList
2.  Protected _memptr As Long
3.  Protected _progptr As Long

The increase and decrease commands amount to acting upon a specific item in the arrayList of integers.

1. _mem(_memptr) = CLng(_mem(_memptr)) + 1
2.  _progptr += 1
3. '...Decrease value
4. _mem(_memptr) = CLng(_mem(_memptr)) - 1
5. _progptr += 1

The "move pointer" commands amount to increasing or decreasing the pointer variable.

1. _memptr += 1
2. If _mem.Count = _memptr Then
3.     _mem.Add(0)
4. End If
5. _progptr += 1
6. '...decrease pointer
7. _memptr -= 1
8. _progptr += 1

The print command amounts to adding another character to the end of the string The character will be the one with charcter code equal to the value of the element in the "memory" arraylist pointed by the "pointer" variable.

1.  
2. _outStream &= ChrW(_mem(_memptr))
3. _progptr += 1

The two flow control commands are somewhat trickier. I need to implement a bracket matching subroutine, and I also need code to execute whenever the command pointer hits one of these, as well as keep track of all left brackets I've passed through. So here goes:

The bracket matching subroutine will be run whenever the command pointer hits a left bracket, and its job will be to find the corresponding right bracket. To that end, we need to keep track of opening and closing brackets. So, we need a counter for counting currently open brackets. This will be an integer variable initialized at 1 (we already have an oen bracket, the one that made the original call to the subroutine). The subroutine will then scan the program code, starting at the command pointer position, increase its counter whenever it encounters a left bracket, and decrease its counter whenever it encounters a right bracket. When the counter reaches 0, that's where the initial left bracket has its matching right bracket. The subroutine should return the position of that right bracket.

1. Protected Function findMatchingBracket(ByVal CodeStr As String, ByVal currentPosition As Long) As Long
2.     Dim openBrackets = 1
3.     While openBrackets > 0
4.         currentPosition += 1
5.         If CodeStr(currentPosition) = "[" Then
6.             openBrackets += 1
7.         ElseIf CodeStr(currentPosition) = "]" Then
8.             openBrackets -= 1
9.         End If
10.     End While
11.     Return currentPosition
12. End Function

To keep track of all the left brackets, all I need is a stack.

1. Protected LoopStack As New Stack(Of Long)

So, when the command pointer encounters a left bracket, the program should first of all, push its position on top of the stack. Then it will check the value at the memory slot pointed by the memory pointer. If zero, call the aforementioned subroutine, otherwise, simply move along.

1. LoopStack.Push(_progptr)
2. If _mem(_memptr) <> 0 Then
3.     _progptr += 1
4. Else
5.     _progptr = findMatchingBracket(CodeStr, _progptr)
6. End If

When the command pointer encounters a right bracket, the program should first pop a value from the stack. Since we're talking about bracket matching, the position popped will undoubtedyt be the position of its matching left bracket. Then check the value at the memory slot pointed by the memory pointer. If nonzero, move the command pointer to the position popped. Otherwise, simply move along.

1. Dim tempptr As Long = LoopStack.Pop()
2. If _mem(_memptr) <> 0 Then
3.     _progptr = tempptr
4. Else
5.     _progptr += 1
6. End If

I include checking for an input command, but this will be a no-op. The interpreter will ignore it and move along.

1. 'Implement user input
2. _progptr += 1

Also, if the character encountered is not one of these 8, the interpreter will simply move along without doing anything.

1. _progptr += 1

Here's the entire interpreter function:

1.        Public Function EvalBF(ByVal CodeStr As String) As String
2.             Dim token As Char
3.             _memptr = 0
4.             _progptr = 0
5.             _mem.Add(0)
6.             _outStream = ""
7.             While _progptr < CodeStr.Length
8.                 token = CodeStr(_progptr)
9.                 Select Case token
10.                     Case ">"
11.                         _memptr += 1
12.                         If _mem.Count = _memptr Then
13.                             _mem.Add(0)
14.                         End If
15.                         _progptr += 1
16.                     Case "<"
17.                         _memptr -= 1
18.                         _progptr += 1
19.                     Case "+"
20.                         _mem(_memptr) = CLng(_mem(_memptr)) + 1
21.                         _progptr += 1
22.                     Case "-"
23.                         _mem(_memptr) = CLng(_mem(_memptr)) - 1
24.                         _progptr += 1
25.                     Case "."
26.                         _outStream &= ChrW(_mem(_memptr))
27.                         _progptr += 1
28.                     Case ","
29.                         'Implement user input
30.                         _progptr += 1
31.                     Case "["
32.                         LoopStack.Push(_progptr)
33.                         If _mem(_memptr) <> 0 Then
34.                             _progptr += 1
35.                         Else
36.                             _progptr = findMatchingBracket(CodeStr, _progptr)
37.                         End If
38.                     Case "]"
39.                         Dim tempptr As Long = LoopStack.Pop()
40.                         If _mem(_memptr) <> 0 Then
41.                             _progptr = tempptr
42.                         Else
43.                             _progptr += 1
44.                         End If
45.                     Case Else
46.                         _progptr += 1
47.                 End Select
48.             End While
49.             Return _outStream
50.         End Function

The code generator requires a bit more thought. As there is more than one way to write a program in Brainfuck that prints a string, we need to have a consistent way of finding the shortest (or an adequately short) source code. It seems that one easy way of writing a program like the one we want (that simply prints a hard-coded message) is to prepopulate some slots with some values, and then increase or decrease the slot with value that's closest to the character code we want to print. Then print the character and start looking for the closest slot to the next letter, and so on.

Apparently, the number of prepopulated slots will have a dramatic effect on the length of the code. Oh, what the heck, let's waste some cpu cycles and memory, and generate programs for the same output string, using up to 32 initial slots, and choose the one with the shortest code.

So, first of all, we need a function that outputs the same characted a specified number of times. If you've seen a Brainfuck program, you'll know that there are lots of "+", "-", ">" and "<" sequences, so this helper function will come in quite handy:

1. Protected Function strTimes(ByVal str As String, ByVal times As Long) As String
2.     Dim endstr As String = ""
3.     For i As Integer = 0 To times - 1
4.         endstr += str
5.     Next
6.     Return endstr
7. End Function

The above function will be used once we know which slot to alter, and how much to alter it. So, we need a function that finds which slot is the closest to the value we need to store:

1. Protected Function findClosestBin(ByVal val As Integer, ByVal bins() As Integer, ByVal currbin As Integer)
2.     Dim minBin As Integer = 0
3.     For b As Integer = 1 To bins.Length - 1
4.         If Math.Abs(val - bins(b)) < Math.Abs(val - bins(minBin)) Then
5.             minBin = b
6.         End If
7.     Next
8.     If Math.Abs(val - bins(minBin)) > Math.Abs(val - bins(currbin)) Then
9.         Return currbin
10.     End If
11.     Return minBin
12. End Function

A few things to note here:

• val is the integer value we wish to store.
• bins() is the array that holds the slots we're using.
• currbin is the slot currently pointed at by the pointer.

So what this function essentially does, is pretty simple: it iterates over all slots (the bins() array) and checks to see which slot is the closest (either higher or lower) to the desired value (val). It then returns that slot's position.

Next thing we need, is a way to know ehether we need to increase or decrease the value at the slot with the closest value to the desired:

1. Protected Function printDifference(ByVal diff As Integer, ByVal poschar As String, ByVal negchar As String) As String
2.     Dim str = ""
3.     Dim b As Integer = 0
4.     While b < Math.Abs(diff)
5.         If diff > 0 Then
6.             str &= poschar
7.         Else
8.             str &= negchar
9.         End If
10.         b += 1
11.     End While
12.     Return str
13. End Function

Indeed, this function returns the increase operator "+" if the value at the slot is lower than the desired, and the decrease operator "-" if the value at the slot is higher.

Finally, we need a helper function that prepopulates a specified number of slots. What we'll do, is use populate the first of the slots with a high enough value, and then fill the next ones with increasing values. To this end, we'll use a loop on the value of the first slot, and add an increasing amount to each of the other slots, while decreasing the value of the first one. At the end, we restore its original value:

1. Protected Function writeBins(ByVal numBins As Integer, ByVal diff As Integer) As String
2.     Dim str = strTimes("+", diff) + "["
3.     For i As Integer = 1 To numBins - 1
4.         str &= ">" + strTimes("+", i + 1)
5.     Next
6.     str &= strTimes("<", numBins - 1) + "-]"
7.     str &= strTimes("+", diff)
8.     Return str
9. End Function

We now have all we need, except for the optimal number of slots to prepopulate. As I said, we'll find that by brute force.

We start by creating a function that generates the Brainfuck program we need, using a specific number of slots to prepopulate (this number being passed as argument):

1. Protected Function Dumbtext2BF(ByVal textstr As String, ByVal numBins As Short)
2.     If numBins <= 0 Then
3.         Throw New Exception("error: too few bins")
4.     End If
5.     Dim bins(numBins - 1) As Integer
6.     Dim diff As Integer = Math.Floor(127 / numBins)
7.     For i As Integer = 0 To numBins - 1
8.         bins(i) = (i + 1) * diff
9.     Next
10.     Dim codestr As String = writeBins(numBins, diff)
11.     Dim counter As Long = 0
12.     Dim currbin As Integer = 0
13.     Dim newbin As Integer = 0
14.     Dim c As Integer
15.     While (counter < textstr.Length)
16.         c = AscW(textstr(counter))
17.         newbin = findClosestBin(c, bins, currbin)
18.         codestr &= printDifference(newbin - currbin, ">", "<")
19.         codestr &= printDifference(c - bins(newbin), "+", "-")
20.         codestr &= "."
21.         currbin = newbin
22.         bins(newbin) = c
23.         counter += 1
24.     End While
25.     Return codestr
26. End Function

Pretty straight forward: after the initial check that the number of slots (numbins) is positive, we prepopulate the slots starting with the integer division of 128 (last character code for ascii) to the number of slots.

We then get the message and assign values one character at a time. Each character we assign successfully, we also print, thus "freeing" the slot it was "occupying".We go on like that until there are no more characters in the message.

We're almost done. In a huge waste of cpu cycles, we use brute force to find the shortest generated code for the same string:

1. Public Function Text2BF(ByVal textstr As String) As String
2.     Dim bestbin As Short = 1
3.     Dim results(32) As Long
4.     Dim beststr As String = ""
5.     Dim resultstr As String = ""
6.     For i As Integer = 1 To 32
7.         Dim str = Dumbtext2BF(textstr, i)
8.         results(i - 1) = str.length
9.         If results(i - 1) < results(bestbin - 1) Then
10.             beststr = str
11.             bestbin = i
12.         End If
13.         resultstr &= i & ": " & results(i) & "\n"
14.     Next
15.     Return beststr
16. End Function

The zip contains the entire Brainfuck project.

---

This news item is from Midnight blogging
( http://yiannis.vavouranakis.gr/myblog/news.php?extend.40 )