brainf*ckのコードの意味がやっと分かったのでメモ。

プログラム

brainf*ckの文法はウィキペディアにも書いてあるので、
インタープリタの実装自体は分かりやすいけど、実際に"A"を表示させる方法が分かりづらかったと。。

"A"を表示するコード

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

ここで出てくる記号の意味を簡単に書くと、

  1. ：ポインタの指す値をインクリメント
  • ：ポインタの指す値をデクリメント

>：ポインタをインクリメント<：ポインタをデクリメント
[と]：cのwhile文みたいなもの
.：ポインタの指す値を出力

brainf*ckは配列とその配列の要素を指すポインタを使います。

static char buffer[BUFFER_SIZE];
static char *buf_ptr = buffer;

brainf*ckのコードを読んで、処理を行うときはポインタを操作してあげてます。
bufferは0で初期化しておく必要があります。

ここで"A"を表示する流れを絵にしてみると、
メモリのレイアウトがこんな感じだとして（□がメモリ1バイト、■はポインタが指しているアドレスと思ってくださいな）

low　　　　　　　　　　　　　　　high
■□□□□□□□□□□□□□□□□□

初期状態ではポインタは先頭のアドレスを指す。

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

そして"A"を表示するコードを見ていくと・・・
1.最初の"["までは8個の"+"で構成されているので、■で指しているアドレスの値は8になります。
　この例だと、先頭アドレスが指す要素はループのカウンタ、次が表示用の要素となってます。
2.そして、"["と"]"で囲まれたループに入る
3.ループの最初ではポインタをインクリメントして、下のようになります。

low　　　　　　　　　　　　　　　high
□■□□□□□□□□□□□□□□□□

4.次に8個の"+"で構成されているので、■で指しているアドレスの値は8になります。
5.ポインタをデクリメントして、ポインタの指す場所を変えます。

low　　　　　　　　　　　　　　　high
■□□□□□□□□□□□□□□□□□

6.そして"-"でポインタの指す値をデクリメントすることで、このポインタの指すアドレスの値は7になります。
7.まだループは終わらないので、またポインタをインクリメントして、

low　　　　　　　　　　　　　　　high
□■□□□□□□□□□□□□□□□□

8.そして、8個の"+"があるから■で指しているアドレスの値は16に。ということを繰り返します。
9.ループは8回、ループ内でのポインタの指す値のインクリメントが8回あるので■の値は8*8=64となります。
10.ループから抜けたら、ポインタをインクリメントして、

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

　このような形にする。

low　　　　　　　　　　　　　　　high
□■□□□□□□□□□□□□□□□□

11.そして、"+"でポインタの指す要素をインクリメントすることで値が10進数で65（16進数で0x41）になります。
12.最後にこのポインタの指す要素（0x41）を表示するとめでたく"A"が表示されることになります キタ――(゜∀゜)――!!

こっちはなんとなく書いてみたインタープリタ。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <sys/mman.h>
#include <unistd.h>
#include <fcntl.h>

/* To display 'Hello World! */
#define HELLO_STRING "++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>."

/* To display 'A'' */
//#define HELLO_STRING "++++++++[>++++++++<-]>+."

#define BUFFER_SIZE 30000

static char buffer[BUFFER_SIZE];
static char *buf_ptr = buffer;

void do_interrepret(char *buf)
{
	unsigned int idx = 0;
	unsigned int line = 1;

	if (!buf) 
		return ;

	while (*buf) {
		switch (*buf) {
		case '>':
			buf_ptr++;
			break;
		case '<':
			buf_ptr--;
			break;
		case '+':
			(*buf_ptr)++;
			break;
		case '-':
			(*buf_ptr)--;
			break;
		case '.':
			putchar(*buf_ptr);
			break;
		case ',':
			(*buf_ptr) = getchar();
			break;
		case '[':
			if (*buf_ptr == 0x0) {
				while (*buf++ != ']')
					; /* do nothing */
			}
			break;
		case ']':
			if (*buf_ptr != 0x0) {
				while (*buf-- != '[')
					; /* do nothing */
			}
			break;
		case '\n':
			line++;
			idx = 0;
			break;
		default:
			printf("unknown char %d(line %d index %d)\n", *buf_ptr, line, idx);
			exit(-1);
		}
		
		idx++;
		buf++;
	}

}

char *read_from_file(char *name)
{
	void *buf;
	struct stat st;
	int fd;
	char *ret = NULL;

	fd = open(name, O_RDONLY);
	if (fd < 0) {
		fprintf(stderr, "file(%s) open error\n", name);
		exit(-1);
	}

	stat(name, &st);
	buf = mmap(NULL, st.st_size, PROT_READ, MAP_SHARED, fd, 0);
	if (*(int *) buf == -1) {
		fprintf(stderr, "mmap error\n");
		exit(-1);
	}

	ret = strdup(buf);

	munmap(ret, st.st_size);
	close(fd);
	
	return ret;

}

int main(int argc, char **argv)
{
	char *buf = NULL;

	if (argc == 2)
		buf = read_from_file(argv[1]);
	else
		buf = strdup(HELLO_STRING); 

	do_interrepret(buf);

	free(buf);

	return 0;
}