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.
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.
Protected _mem As New ArrayList
Protected _memptr As Long
Protected _progptr As Long
The increase and decrease commands amount to acting upon a specific item in the arrayList of integers.
_mem(_memptr) = CLng(_mem(_memptr)) + 1
_progptr += 1
'...Decrease value
_mem(_memptr) = CLng(_mem(_memptr)) - 1
_progptr += 1
The "move pointer" commands amount to increasing or decreasing the pointer variable.
_memptr += 1
If _mem.Count = _memptr Then
_mem.Add(0)
End If
_progptr += 1
'...decrease pointer
_memptr -= 1
_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.
_outStream &= ChrW(_mem(_memptr))
_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.
Protected Function findMatchingBracket(ByVal CodeStr As String, ByVal currentPosition As Long) As Long
Dim openBrackets = 1
While openBrackets > 0
currentPosition += 1
If CodeStr(currentPosition) = "[" Then
openBrackets += 1
ElseIf CodeStr(currentPosition) = "]" Then
openBrackets -= 1
End If
End While
Return currentPosition
End Function
To keep track of all the left brackets, all I need is a stack.
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.
LoopStack.Push(_progptr)
If _mem(_memptr) <> 0 Then
_progptr += 1
Else
_progptr = findMatchingBracket(CodeStr, _progptr)
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.
Dim tempptr As Long = LoopStack.Pop()
If _mem(_memptr) <> 0 Then
_progptr = tempptr
Else
_progptr += 1
End If
I include checking for an input command, but this will be a no-op. The interpreter will ignore it and move along.
'Implement user input
_progptr += 1
Also, if the character encountered is not one of these 8, the interpreter will simply move along without doing anything.
Here's the entire interpreter function:
Public Function EvalBF(ByVal CodeStr As String) As String
Dim token As Char
_memptr = 0
_progptr = 0
_mem.Add(0)
_outStream = ""
While _progptr < CodeStr.Length
token = CodeStr(_progptr)
Select Case token
Case ">"
_memptr += 1
If _mem.Count = _memptr Then
_mem.Add(0)
End If
_progptr += 1
Case "<"
_memptr -= 1
_progptr += 1
Case "+"
_mem(_memptr) = CLng(_mem(_memptr)) + 1
_progptr += 1
Case "-"
_mem(_memptr) = CLng(_mem(_memptr)) - 1
_progptr += 1
Case "."
_outStream &= ChrW(_mem(_memptr))
_progptr += 1
Case ","
'Implement user input
_progptr += 1
Case "["
LoopStack.Push(_progptr)
If _mem(_memptr) <> 0 Then
_progptr += 1
Else
_progptr = findMatchingBracket(CodeStr, _progptr)
End If
Case "]"
Dim tempptr As Long = LoopStack.Pop()
If _mem(_memptr) <> 0 Then
_progptr = tempptr
Else
_progptr += 1
End If
Case Else
_progptr += 1
End Select
End While
Return _outStream
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:
Protected Function strTimes(ByVal str As String, ByVal times As Long) As String
Dim endstr As String = ""
For i As Integer = 0 To times - 1
endstr += str
Next
Return endstr
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:
Protected Function findClosestBin(ByVal val As Integer, ByVal bins() As Integer, ByVal currbin As Integer)
Dim minBin As Integer = 0
For b As Integer = 1 To bins.Length - 1
If Math.Abs(val - bins(b)) < Math.Abs(val - bins(minBin)) Then
minBin = b
End If
Next
If Math.Abs(val - bins(minBin)) > Math.Abs(val - bins(currbin)) Then
Return currbin
End If
Return minBin
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:
Protected Function printDifference(ByVal diff As Integer, ByVal poschar As String, ByVal negchar As String) As String
Dim str = ""
Dim b As Integer = 0
While b < Math.Abs(diff)
If diff > 0 Then
str &= poschar
Else
str &= negchar
End If
b += 1
End While
Return str
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:
Protected Function writeBins(ByVal numBins As Integer, ByVal diff As Integer) As String
Dim str = strTimes("+", diff) + "["
For i As Integer = 1 To numBins - 1
str &= ">" + strTimes("+", i + 1)
Next
str &= strTimes("<", numBins - 1) + "-]"
str &= strTimes("+", diff)
Return str
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):
Protected Function Dumbtext2BF(ByVal textstr As String, ByVal numBins As Short)
If numBins <= 0 Then
Throw New Exception("error: too few bins")
End If
Dim bins(numBins - 1) As Integer
Dim diff As Integer = Math.Floor(127 / numBins)
For i As Integer = 0 To numBins - 1
bins(i) = (i + 1) * diff
Next
Dim codestr As String = writeBins(numBins, diff)
Dim counter As Long = 0
Dim currbin As Integer = 0
Dim newbin As Integer = 0
Dim c As Integer
While (counter < textstr.Length)
c = AscW(textstr(counter))
newbin = findClosestBin(c, bins, currbin)
codestr &= printDifference(newbin - currbin, ">", "<")
codestr &= printDifference(c - bins(newbin), "+", "-")
codestr &= "."
currbin = newbin
bins(newbin) = c
counter += 1
End While
Return codestr
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:
Public Function Text2BF(ByVal textstr As String) As String
Dim bestbin As Short = 1
Dim results(32) As Long
Dim beststr As String = ""
Dim resultstr As String = ""
For i As Integer = 1 To 32
Dim str = Dumbtext2BF(textstr, i)
results(i - 1) = str.length
If results(i - 1) < results(bestbin - 1) Then
beststr = str
bestbin = i
End If
resultstr &= i & ": " & results(i) & "\n"
Next
Return beststr
End Function
The zip contains the entire Brainfuck project.
brainfuck.zip
Home
Downloads
Towards steganography I: a Brainfuck code generator and interpreter in VB.Net
Binary Clock
