malbolge20.c 8.88 KB
Newer Older
Masahiko Sakai's avatar
Masahiko Sakai committed
1 2 3 4 5
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <math.h>
6
#include <unistd.h>
Masahiko Sakai's avatar
Masahiko Sakai committed
7 8 9 10 11 12 13

#define ALLOCATED 1
#define UNALLOCATED 0

#ifdef __GNUC__
static inline
#endif
14
void exec(int flag[59049], unsigned int **mem, unsigned int init[59049][2] );
Masahiko Sakai's avatar
Masahiko Sakai committed
15 16 17 18

#ifdef __GNUC__
static inline
#endif
19 20
unsigned int op( unsigned int x, unsigned int y );
void make_init_mem(int id, unsigned int **mem, unsigned int init[59049][2]);
Masahiko Sakai's avatar
Masahiko Sakai committed
21 22 23 24 25 26 27 28 29

const char xlat1[] =
    "+b(29e*j1VMEKLyC})8&m#~W>qxdRp0wkrUo[D7,XTcA\"lI"
  ".v%{gJh4G\\-=O@5`_3i<?Z';FNQuY]szf$!BS/|t:Pn6^Ha";

const char xlat2[] =
    "5z]&gqtyfr$(we4{WP)H-Zn,[%\\3dL+Q;>U!pJS72FhOA1C"
  "B6v^=I_0/8|jsb9m<.TVac`uY*MK'X~xDl}REokN:#?G\"i@";
  FILE *f;
30
  FILE *fperror;
Masahiko Sakai's avatar
Masahiko Sakai committed
31 32 33
int main( int argc, char **argv )
{

34
  unsigned int **mem;
Masahiko Sakai's avatar
Masahiko Sakai committed
35
  int flag[59049];// ブロックが使用済みか否か
36 37
  unsigned int init[59050][2]; // 各ブロックの最初2つ分の初期値を記憶
  unsigned int i,ii = 0;
Masahiko Sakai's avatar
Masahiko Sakai committed
38 39
  int x;

40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
  int opt, outf=0;
  char *usage="Usage: malbolge20 [-oh] prog-file\n";


  while ((opt = getopt(argc, argv, "o")) != -1) {
    switch (opt){
    case 'o': 
      outf=1;
      break;

    case 'h':
    default:
      fputs(usage, stderr);
      return (1);
    }
  }

Masahiko Sakai's avatar
Masahiko Sakai committed
57 58 59 60
  for(i=0;i<59049;i++){// フラグ初期化
    flag[i]=UNALLOCATED;
  }

61 62 63 64 65 66 67 68 69
  if ( outf ) {
    FILE *tmpf;
    if ( ( tmpf = fopen( "info", "w" ) ) != NULL )
    {
      fperror = tmpf;
    }
  } else   fperror = stdout;

  if ( (argc - optind) != 1 )
Masahiko Sakai's avatar
Masahiko Sakai committed
70
    {
71
      fputs(usage, stderr );
Masahiko Sakai's avatar
Masahiko Sakai committed
72 73
      return ( 1 );
    }
74
  if ( ( f = fopen( argv[optind], "r" ) ) == NULL )
Masahiko Sakai's avatar
Masahiko Sakai committed
75
    {
76
      fputs( "can't open input file\n", stderr );
Masahiko Sakai's avatar
Masahiko Sakai committed
77 78 79
      return ( 1 );
    }

80
  mem = (unsigned int **)malloc( sizeof(unsigned int) * 59049 );
Masahiko Sakai's avatar
Masahiko Sakai committed
81 82 83
  if ( mem == NULL )
    {
      fclose( f );
84 85
      fprintf(fperror, "Error: can't allocate memory\n" );
      fclose(fperror);
Masahiko Sakai's avatar
Masahiko Sakai committed
86 87 88 89 90
      return ( 1 );
    }

  int id=0;
  //第0ブロックのメモリ領域確保
91
  mem[id] = (unsigned int *)malloc( sizeof(unsigned int) * 59049 );
Masahiko Sakai's avatar
Masahiko Sakai committed
92 93 94
  if ( mem[id] == NULL )
    {
      fclose( f );
95 96
      fprintf(fperror, "Error: can't allocate memory\n" );
      fclose(fperror);
Masahiko Sakai's avatar
Masahiko Sakai committed
97 98 99 100 101 102 103 104 105 106 107 108 109
      return ( 1 );
    }
  flag[id]=ALLOCATED;

  //以下で入力プログラムの読み込み
  i=0;
  while ( ( x = getc( f ) ) != EOF )
    {
      if ( isspace( x ) ) continue;
      if ( x < 127 && x > 32 )
	{
	  if ( strchr( "ji*p</vo", xlat1[( x - 33 + ii ) % 94] ) == NULL )
	    {
110
              fprintf(fperror, "Error: invalid character (ascii=%d) in source file\n",x);
Masahiko Sakai's avatar
Masahiko Sakai committed
111 112
	      free( mem );
	      fclose( f );
113
	      fclose(fperror);
Masahiko Sakai's avatar
Masahiko Sakai committed
114 115 116
	      return ( 1 );
	    }
	}else{
117
        fprintf(fperror, "Error: invalid character (ascii=%d) in source file\n", x);
Masahiko Sakai's avatar
Masahiko Sakai committed
118 119
	free( mem );
	fclose( f );
120 121
	fclose(fperror);
      	return ( 1 );
Masahiko Sakai's avatar
Masahiko Sakai committed
122 123 124 125 126 127 128 129 130 131
      }
      mem[id][i++] = x;
      ii++;//通しの文字数
      if(i == 59049){//ブロック内の文字数が59049となった場合
	id++;//次のブロックに移る
	if ( id==59049 )//第59049ブロックとなった場合、メモリ不足
	  {
	    fputs( "input file too long\n", stderr );
	    free( mem );
	    fclose( f );
132
            fclose(fperror);
Masahiko Sakai's avatar
Masahiko Sakai committed
133 134 135
	    return ( 1 );
	  }
	//次ブロックのメモリ領域を確保
136
	mem[id] = (unsigned int *)malloc( sizeof(unsigned int) * 59049 );
Masahiko Sakai's avatar
Masahiko Sakai committed
137 138 139
	if ( mem[id] == NULL )
	  {
	    fclose( f );
140 141
            fprintf(fperror, "Error: can't allocate memory\n" );
            fclose(fperror);
Masahiko Sakai's avatar
Masahiko Sakai committed
142 143 144 145 146 147 148 149
	    return ( 1 );
	  }
	flag[id]=ALLOCATED;//第idブロックを使用済みに変更
	i=0;//ブロック内文字数を0に戻す
      }
    }
  fclose( f );//入力の読み込み終了
  //以下は使用中ブロックの余ったメモリの初期化処理
150 151 152 153
  if(id==0 && i<=1) {   // avoiding errors when null inputs
    fprintf( fperror, "Exited due to an empty input\n" );
    return(1);
  }
Masahiko Sakai's avatar
Masahiko Sakai committed
154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170
  if(i==0){
    mem[id][0] = op( mem[id-1][59048], mem[id-1][59047] );
    mem[id][1] = op( mem[id][0], mem[id-1][59048] );
    i=2;
  }else if(i==1){
    mem[id][1] = op( mem[id][0], mem[id-1][59048] );
    i=2;
  }
  while ( i < 59049 ){
    mem[id][i] = op( mem[id][i - 1], mem[id][i - 2] );
    i++;
  }//初期化処理ここまで

  make_init_mem(id, mem, init);//以降のブロックの遅延初期化を行うための準備

  exec( flag, mem, init );//実行
  free( mem );
171 172
  if(outf) fprintf(fperror,"Execution completed.\n");
  fclose(fperror);
Masahiko Sakai's avatar
Masahiko Sakai committed
173 174 175 176 177 178
  return ( 0 );
}


  /* 各ブロックの遅延初期化を行うための準備をする関数 */
  /* 各ブロックの最初の2ワードを計算し, initに格納 */
179
void make_init_mem(int id, unsigned int **mem, unsigned int init[59049][2]){
Masahiko Sakai's avatar
Masahiko Sakai committed
180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209
  int i,j;
  int x, y, temp0, temp1;
  int num0[3][3] = {{0, 1, 2}, {0, 1, 1}, {0, 2, 2}, };
  int num1[3][3] = {{1, 0, 0}, {1, 0, 2}, {2, 1, 2}, };

  init[id+1][0]=op( mem[id][59048], mem[id][59047] );
  init[id+1][1]=op( init[id+1][0],  mem[id][59048] );
  id++;
  for(i=id;i<59049;i++){
    temp0=init[id][0];
    temp1=init[id][1];
    init[id+1][0]=0;
    init[id+1][1]=0;
    for(j=0;j<20;j++){
      x = temp0 % 3;
      y = temp1 % 3;
      init[id+1][0] += num0[x][y]*pow(3.0,j);
      init[id+1][1] += num1[x][y]*pow(3.0,j);
      temp0 = temp0/3;
      temp1 = temp1/3;
    }
    id++;
  }
}

#ifdef __GNUC__
static inline
#endif

/* JMPとMOV_Dの時に呼ばれ, その処理を実行する. */
210
void mem_manage(unsigned int *reg_addr, unsigned int num, int *id, unsigned int **mem, unsigned int init[59049][2], int flag[59049]){
Masahiko Sakai's avatar
Masahiko Sakai committed
211 212 213 214 215 216 217 218 219 220 221 222
  int new_reg_addr=0;
  int new_id;
  int i;
  new_id=num/59049;
  for(i=0;i<10;i++){
    new_reg_addr += (num % 3)*pow(3.0,i);
    num = num/3;
  }
  *reg_addr=new_reg_addr;

  /* 初期化されていないブロックだった場合、初期化する*/
  if(flag[new_id]==UNALLOCATED){ //すでに初期化済みかチェック
223
    mem[new_id] = (unsigned int *)malloc( sizeof(unsigned int) * 59049 );
Masahiko Sakai's avatar
Masahiko Sakai committed
224 225 226
    if ( mem[new_id] == NULL ){
      fclose( f );
      free(mem);
227 228
      fprintf(fperror, "Error: can't allocate memory\n");
      fclose(fperror);
Masahiko Sakai's avatar
Masahiko Sakai committed
229 230 231 232 233 234 235 236 237 238 239 240 241 242 243
      exit ( 1 );
    }
    mem[new_id][0] = init[new_id][0];
    mem[new_id][1] = init[new_id][1];
    i=2;
    while ( i < 59049 ){
      mem[new_id][i] = op( mem[new_id][i-1], mem[new_id][i-2] );
      i++;
    }
    flag[new_id]=ALLOCATED;
  }
  *id=new_id;
}

/* 命令実行後のインクリメント. increment(c, c_id)*/
244
void increment(unsigned int *reg_addr, int *id, int flag[59049], unsigned int **mem, unsigned int init[59049][2]){
Masahiko Sakai's avatar
Masahiko Sakai committed
245 246 247 248 249 250 251
  int i;
  if ( *reg_addr == 59048 ){
    if(*id == 59048){
      *id = 0; *reg_addr = 0;
    }else{
      *id+=1; *reg_addr=0;
      if(flag[*id]==UNALLOCATED){ //すでに初期化済みかチェック
252
	mem[*id] = (unsigned int *)malloc( sizeof(unsigned int) * 59049 );
Masahiko Sakai's avatar
Masahiko Sakai committed
253 254
	if ( mem[*id] == NULL ){
	  fclose( f );
255 256
          fprintf(fperror, "Error: can't allocate memory\n");
          fclose(fperror);
Masahiko Sakai's avatar
Masahiko Sakai committed
257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272
	  exit ( 1 );
	}
	mem[*id][0] = init[*id][0];
	mem[*id][1] = init[*id][1];
	for(i=2; i<59049; i++ ){
	  mem[*id][i] = op( mem[*id][i-1], mem[*id][i-2] );
	}
	flag[*id]=ALLOCATED;
      }
    }
  }else {
    *reg_addr += 1;
  }
}


273
void exec( int flag[59049], unsigned int **mem, unsigned int init[59049][2] )
Masahiko Sakai's avatar
Masahiko Sakai committed
274
{
275
  unsigned int a = 0, c = 0, d = 0;
Masahiko Sakai's avatar
Masahiko Sakai committed
276 277 278 279 280
  int x;
  int c_id=0, d_id=0;
  for (;;)
    {
      if ( mem[c_id][c] < 33 || mem[c_id][c] > 126 ) {
281 282
        fprintf(fperror,"Error: enterring into an infinite loop.\n");
        fclose(fperror);
Masahiko Sakai's avatar
Masahiko Sakai committed
283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324
	exit(1);
	//continue; // もともとの処理
	}
      switch ( xlat1[( mem[c_id][c] - 33 + (c+c_id*59049) ) % 94] )
	{
	case 'j': //MOV_D
	  mem_manage(&d, mem[d_id][d], &d_id, mem, init, flag);
	  break;
	case 'i': //JMP
	  mem_manage(&c, mem[d_id][d], &c_id, mem, init, flag);
	  break;
	case '*': //ROT
	  a = mem[d_id][d] = mem[d_id][d] / 3 + mem[d_id][d] % 3 * pow(3,19);
	  break;
	case 'p': // OPR
	  a = mem[d_id][d] = op( a, mem[d_id][d] );
	  break;
	case '<'://OUTPUT
	         #if '\n' != 10
	  if ( x == 10 ) putc( '\n', stdout );else
	           #endif
	    putc( a, stdout );
	  break;
	case '/'://INPUT
	  x = getc( stdin );
	         #if '\n' != 10
	  if ( x == '\n' ) a = 10; else
	           #endif
	    if ( x == EOF ) a = 59049 ; else a = x;
	  break;
	case 'v':return;//HALT
	}
      mem[c_id][c] = xlat2[mem[c_id][c] - 33];
      increment(&c, &c_id, flag, mem, init);
      increment(&d, &d_id, flag, mem, init);
    }
}

#ifdef __GNUC__
static inline
#endif

325
unsigned int op( unsigned int x, unsigned int y )
Masahiko Sakai's avatar
Masahiko Sakai committed
326
{
327 328
  unsigned int i = 0, j;
    static const unsigned int p9[10] =
Masahiko Sakai's avatar
Masahiko Sakai committed
329
      { 1, 9, 81, 729, 6561 ,59049, 531441, 4782969, 43046721, 387420489};
330
      static const unsigned int o[9][9] =
Masahiko Sakai's avatar
Masahiko Sakai committed
331 332 333 334 335 336 337 338 339 340 341 342 343 344 345
	{
	  { 4, 3, 3, 1, 0, 0, 1, 0, 0 },
	  { 4, 3, 5, 1, 0, 2, 1, 0, 2 },
	  { 5, 5, 4, 2, 2, 1, 2, 2, 1 },
	  { 4, 3, 3, 1, 0, 0, 7, 6, 6 },
	  { 4, 3, 5, 1, 0, 2, 7, 6, 8 },
	  { 5, 5, 4, 2, 2, 1, 8, 8, 7 },
	  { 7, 6, 6, 7, 6, 6, 4, 3, 3 },
	  { 7, 6, 8, 7, 6, 8, 4, 3, 5 },
	  { 8, 8, 7, 8, 8, 7, 5, 5, 4 },
	};
      for ( j = 0; j < 10 ; j++ )
	i += o[y / p9[j] % 9][x / p9[j] % 9] * p9[j];
      return ( i );
}