Thursday, July 31, 2008

Big table implementation in Brainfuck

In the past I had found an efficient way of implementing tables on the Brainfuck array. There were already some table implementations which used at least 2*n Brainfuck cells for storing an n sized table. My implementation needed only n+4.

Also, all known implementations had a limit of 256 cells (Or equal to the size of a cell on the Brainfuck array. For the rest of the post I will assume that the cell size is one byte).

During my road-trip to Spain, based on my old implementation, I found a new one that can use multiple indexes to implement tables of ANY size on the Brainfuck array. Additionally the table cell size can be any multiple of the Brainfuck array's cell size.

It uses a format similar to my old implementation: a head moving through the table while decreasing the index it carries, passing table data over it, until it finds the correct position,the it does it's job (read/write) and then it returns in the same way but using a copy of the index.

For a table with n cells of size k each the form of the header is:

  • k empty cells: When the head need's to move to the right, it will have to move the first k cells on it's right in these empty cells before moving itself k positions to the right (thus moving itself to the next indexed position)
  • n index cells: Before starting a read or write operation you will have to store the index here. The leftmost index is the most important. For example if the maximum possible value for an index is 9 (instead of 255) and you use two indexes, to access the 15th cell you would have to use 1 for the left index and 4 for the right index (not 5 because the numbering starts from 0).
  • k data cells: To write to the table you will have to put the data in these cells. If you read from the table, after the end of the read operation the read data will be here. These cells MUST be cleared before starting a read operation.
  • n empty (index) cells: While the index cells are reduced, these cells are increased so that, when the seek operation finishes, they will hold a copy of the original indexes which will be used for returning the head to the beginning of the table.

After the header the table data is assumed to be laying. n*k cells in total. For example for a size 400 table with 2 bytes per cell they would have this form:
Data 1 of index 0,0
Data 2 of index 0,0
Data 1 of index 0,255
Data 2 of index 0,255
Data 1 of index 1,0
Data 2 of index 2,0
Data 1 of index 1,1
Data 2 of index 2,1
Data 1 of index 1,143
Data 2 of index 1,143

So you will need 2*k+2*ceil(log256(n))+n*k cells on the Brainfuck array to store a table with n, k-sized cells. (ceil(log256(n)) is the number of the indexes)

Therefore the code needed to write or read from the table depends on n and k. I actually wrote some metacode that provided with n and k produces the corresponding code. I then turned the metacode into a Lua script. It's not well written but I believe that it works. I tried the following cases:
  1. Writing two values to a table with n<256 and k=1 and then reading them back.
  2. Writing two values to a table with 256<n<256^2 and k=2 and then reading them back.
and everything worked fine.

If you want to try the script yourself you download it from here.

Here is some example code:

n<256 k=1

256<n<256^2 k=1

1 comment:

Popular Posts