codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
/* ICFP 2006 UM virtual machine */ #include <stdio.h> #include <stdlib.h> #include <string.h> typedef unsigned char uint8; typedef unsigned short uint16; typedef unsigned int uint32; typedef unsigned long long uint64; #define CompileTime_Assert( x ) extern char __ctassert[(x)]; uint32 const BUF_SIZE = 4*1024*1024; uint32 const MIN_ALLOC = 8; struct OPTYPE { void * m_op; uint32 *__restrict m_A; uint32 *__restrict m_B; }; uint32 s_buffer[BUF_SIZE*MIN_ALLOC]; uint32 *s_free = 0; inline uint32 *allocate( uint32 _size ) { uint32 *ptr; if( (_size < MIN_ALLOC) && s_free ) { ptr = s_free; s_free = (uint32*)*ptr; *ptr = _size; CompileTime_Assert( MIN_ALLOC == 8 ); // unroll ptr[1] = 0; ptr[2] = 0; ptr[3] = 0; ptr[4] = 0; ptr[5] = 0; ptr[6] = 0; ptr[7] = 0; } else { ptr = new uint32[_size+1]; *ptr = _size; memset(ptr+1,0,_size*4); } return ptr+1; } inline void destroy( void * _ptr ) { uint32 *ptr = ((uint32*)_ptr)-1; if( ((uint32)(ptr-s_buffer))<(BUF_SIZE*MIN_ALLOC) ) { *ptr = (uint)s_free; s_free = ptr; } else { delete[] ptr; } } CompileTime_Assert( sizeof(uint32) == sizeof(uint32 *) ); #define A (*ip->m_A) #define B (*ip->m_B) #define C (*ip->m_C) class VM { public: static void Go( uint32 *_arr0 ) { void * const labels[] = { &&HALT, &&HALT, &&HALT, &&HALT, &&HALT, &&HALT, &&HALT, &&HALT, &&OP_08, &&OP_09, &&OP_10, &&OP_11, &&OP_12 }; void * const OP00[] = { &&OP_00_0, &&OP_00_1, &&OP_00_2, &&OP_00_3, &&OP_00_4, &&OP_00_5, &&OP_00_6, &&OP_00_7, }; void * const OP01[] = { &&OP_01_0, &&OP_01_1, &&OP_01_2, &&OP_01_3, &&OP_01_4, &&OP_01_5, &&OP_01_6, &&OP_01_7, }; void * const OP02[] = { &&OP_02_0, &&OP_02_1, &&OP_02_2, &&OP_02_3, &&OP_02_4, &&OP_02_5, &&OP_02_6, &&OP_02_7, }; void * const OP03[] = { &&OP_03_0, &&OP_03_1, &&OP_03_2, &&OP_03_3, &&OP_03_4, &&OP_03_5, &&OP_03_6, &&OP_03_7, }; void * const OP04[] = { &&OP_04_0, &&OP_04_1, &&OP_04_2, &&OP_04_3, &&OP_04_4, &&OP_04_5, &&OP_04_6, &&OP_04_7, }; void * const OP05[] = { &&OP_05_0, &&OP_05_1, &&OP_05_2, &&OP_05_3, &&OP_05_4, &&OP_05_5, &&OP_05_6, &&OP_05_7, }; void * const OP06[] = { &&OP_06_0, &&OP_06_1, &&OP_06_2, &&OP_06_3, &&OP_06_4, &&OP_06_5, &&OP_06_6, &&OP_06_7, }; void * const OP13[] = { &&OP_13_0, &&OP_13_1, &&OP_13_2, &&OP_13_3, &&OP_13_4, &&OP_13_5, &&OP_13_6, &&OP_13_7, }; uint32 __restrict reg[8] = { 0, 0, 0, 0, 0, 0, 0, 0 }; OPTYPE * __restrict insns = new OPTYPE[(_arr0[-1]+3)&~3]; { for(uint i = 0; i < _arr0[-1]; i+=4 ) { insns[i+0].m_op = &&XLATE; insns[i+1].m_op = &&XLATE; insns[i+2].m_op = &&XLATE; insns[i+3].m_op = &&XLATE; } } register OPTYPE * __restrict ip = insns; // JIT compile XLATE: { uint32 const op = _arr0[ip-insns]; uint32 const opcode = (op>>28); switch( opcode ) { case 0: ip->m_op = OP00[((op>>6)&7)]; ip->m_A = reg+ ((op>>3)&7); ip->m_B = reg+ (op&7); goto *ip->m_op; case 1: ip->m_op = OP01[((op>>3)&7)]; ip->m_A = reg+ ((op>>6)&7); ip->m_B = reg+ (op&7); goto *ip->m_op; case 2: ip->m_op = OP02[((op>>6)&7)]; ip->m_A = reg+ ((op>>3)&7); ip->m_B = reg+ (op&7); goto *ip->m_op; case 3: ip->m_op = OP03[((op>>6)&7)]; ip->m_A = reg+ ((op>>3)&7); ip->m_B = reg+ (op&7); goto *ip->m_op; case 4: ip->m_op = OP04[((op>>6)&7)]; ip->m_A = reg+ ((op>>3)&7); ip->m_B = reg+ (op&7); goto *ip->m_op; case 5: ip->m_op = OP05[((op>>6)&7)]; ip->m_A = reg+ ((op>>3)&7); ip->m_B = reg+ (op&7); goto *ip->m_op; case 6: ip->m_op = OP06[((op>>6)&7)]; ip->m_A = reg+ ((op>>3)&7); ip->m_B = reg+ (op&7); goto *ip->m_op; case 13: ip->m_op = OP13[(op>>25)&7]; ip->m_A = (uint32*)(_arr0[ip-insns]&((1<<25)-1)); goto *ip->m_op; default: ip->m_op = labels[opcode]; ip->m_A = reg+ ((op>>3)&7); ip->m_B = reg+ (op&7); goto *ip->m_op; } } // ---------------------------------------- OP_00_0: if( !B ) { goto *(++ip)->m_op; } reg[0] = A; goto *(++ip)->m_op; OP_03_0: reg[0] = A + B; goto *(++ip)->m_op; OP_04_0: reg[0] = A * B; goto *(++ip)->m_op; OP_05_0: reg[0] = A / B; goto *(++ip)->m_op; OP_06_0: reg[0] = ~(A & B); goto *(++ip)->m_op; OP_00_1: if( !B ) { goto *(++ip)->m_op; } reg[1] = A; goto *(++ip)->m_op; OP_03_1: reg[1] = A + B; goto *(++ip)->m_op; OP_04_1: reg[1] = A * B; goto *(++ip)->m_op; OP_05_1: reg[1] = A / B; goto *(++ip)->m_op; OP_06_1: reg[1] = ~(A & B); goto *(++ip)->m_op; OP_00_2: if( !B ) { goto *(++ip)->m_op; } reg[2] = A; goto *(++ip)->m_op; OP_03_2: reg[2] = A + B; goto *(++ip)->m_op; OP_04_2: reg[2] = A * B; goto *(++ip)->m_op; OP_05_2: reg[2] = A / B; goto *(++ip)->m_op; OP_06_2: reg[2] = ~(A & B); goto *(++ip)->m_op; OP_00_3: if( !B ) { goto *(++ip)->m_op; } reg[3] = A; goto *(++ip)->m_op; OP_03_3: reg[3] = A + B; goto *(++ip)->m_op; OP_04_3: reg[3] = A * B; goto *(++ip)->m_op; OP_05_3: reg[3] = A / B; goto *(++ip)->m_op; OP_06_3: reg[3] = ~(A & B); goto *(++ip)->m_op; OP_00_4: if( !B ) { goto *(++ip)->m_op; } reg[4] = A; goto *(++ip)->m_op; OP_03_4: reg[4] = A + B; goto *(++ip)->m_op; OP_04_4: reg[4] = A * B; goto *(++ip)->m_op; OP_05_4: reg[4] = A / B; goto *(++ip)->m_op; OP_06_4: reg[4] = ~(A & B); goto *(++ip)->m_op; OP_00_5: if( !B ) { goto *(++ip)->m_op; } reg[5] = A; goto *(++ip)->m_op; OP_03_5: reg[5] = A + B; goto *(++ip)->m_op; OP_04_5: reg[5] = A * B; goto *(++ip)->m_op; OP_05_5: reg[5] = A / B; goto *(++ip)->m_op; OP_06_5: reg[5] = ~(A & B); goto *(++ip)->m_op; OP_00_6: if( !B ) { goto *(++ip)->m_op; } reg[6] = A; goto *(++ip)->m_op; OP_03_6: reg[6] = A + B; goto *(++ip)->m_op; OP_04_6: reg[6] = A * B; goto *(++ip)->m_op; OP_05_6: reg[6] = A / B; goto *(++ip)->m_op; OP_06_6: reg[6] = ~(A & B); goto *(++ip)->m_op; OP_00_7: if( !B ) { goto *(++ip)->m_op; } reg[7] = A; goto *(++ip)->m_op; OP_03_7: reg[7] = A + B; goto *(++ip)->m_op; OP_04_7: reg[7] = A * B; goto *(++ip)->m_op; OP_05_7: reg[7] = A / B; goto *(++ip)->m_op; OP_06_7: reg[7] = ~(A & B); goto *(++ip)->m_op; OP_08: A = (uint32)allocate(B); goto *(++ip)->m_op; OP_09: destroy((void*)B); goto *(++ip)->m_op; OP_10: fputc( B, stdout ); goto *(++ip)->m_op; OP_11: B = fgetc( stdin ); goto *(++ip)->m_op; // --- OP_01_0: A = (reg[0] ? ((uint32 *)reg[0]) : _arr0)[B] ; goto *(++ip)->m_op; OP_01_1: A = (reg[1] ? ((uint32 *)reg[1]) : _arr0)[B] ; goto *(++ip)->m_op; OP_01_2: A = (reg[2] ? ((uint32 *)reg[2]) : _arr0)[B] ; goto *(++ip)->m_op; OP_01_3: A = (reg[3] ? ((uint32 *)reg[3]) : _arr0)[B] ; goto *(++ip)->m_op; OP_01_4: A = (reg[4] ? ((uint32 *)reg[4]) : _arr0)[B] ; goto *(++ip)->m_op; OP_01_5: A = (reg[5] ? ((uint32 *)reg[5]) : _arr0)[B] ; goto *(++ip)->m_op; OP_01_6: A = (reg[6] ? ((uint32 *)reg[6]) : _arr0)[B] ; goto *(++ip)->m_op; OP_01_7: A = (reg[7] ? ((uint32 *)reg[7]) : _arr0)[B] ; goto *(++ip)->m_op; // --- OP_02_SMC: _arr0[A] = B; insns[A].m_op = &&XLATE; goto *(++ip)->m_op; OP_02_0: if( !reg[0] ) { goto OP_02_SMC; } ((uint32 *__restrict)reg[0])[A] = B; goto *(++ip)->m_op; OP_02_1: if( !reg[1] ) { goto OP_02_SMC; } ((uint32 *__restrict)reg[1])[A] = B; goto *(++ip)->m_op; OP_02_2: if( !reg[2] ) { goto OP_02_SMC; } ((uint32 *__restrict)reg[2])[A] = B; goto *(++ip)->m_op; OP_02_3: if( !reg[3] ) { goto OP_02_SMC; } ((uint32 *__restrict)reg[3])[A] = B; goto *(++ip)->m_op; OP_02_4: if( !reg[4] ) { goto OP_02_SMC; } ((uint32 *__restrict)reg[4])[A] = B; goto *(++ip)->m_op; OP_02_5: if( !reg[5] ) { goto OP_02_SMC; } ((uint32 *__restrict)reg[5])[A] = B; goto *(++ip)->m_op; OP_02_6: if( !reg[6] ) { goto OP_02_SMC; } ((uint32 *__restrict)reg[6])[A] = B; goto *(++ip)->m_op; OP_02_7: if( !reg[7] ) { goto OP_02_SMC; } ((uint32 *__restrict)reg[7])[A] = B; goto *(++ip)->m_op; // --- OP_12: if( !A ) { ip = insns+B; goto *ip->m_op; } { uint32 const *source = (uint32 const*)A; uint32 const dest = B; uint32 const size = source[-1]; if( size > _arr0[-1] ) { destroy(_arr0); delete[] insns; _arr0 = allocate(size); insns = new OPTYPE[(size+3)&~3]; } memcpy( _arr0, source, size*4 ); for(uint i = 0; i < size; i+=4 ) { insns[i+0].m_op = &&XLATE; insns[i+1].m_op = &&XLATE; insns[i+2].m_op = &&XLATE; insns[i+3].m_op = &&XLATE; } ip = insns+dest; goto XLATE; } // --- OP_13_0: reg[0] = (uint32)ip->m_A; goto *(++ip)->m_op; OP_13_1: reg[1] = (uint32)ip->m_A; goto *(++ip)->m_op; OP_13_2: reg[2] = (uint32)ip->m_A; goto *(++ip)->m_op; OP_13_3: reg[3] = (uint32)ip->m_A; goto *(++ip)->m_op; OP_13_4: reg[4] = (uint32)ip->m_A; goto *(++ip)->m_op; OP_13_5: reg[5] = (uint32)ip->m_A; goto *(++ip)->m_op; OP_13_6: reg[6] = (uint32)ip->m_A; goto *(++ip)->m_op; OP_13_7: reg[7] = (uint32)ip->m_A; goto *(++ip)->m_op; HALT: return; } }; int main( int argc, char const ** _argv ) { for(uint32 i = 0; i < (BUF_SIZE-1); i++) { s_buffer[i*MIN_ALLOC] = (uint)(&s_buffer[((i+1)*MIN_ALLOC)]); } s_buffer[(BUF_SIZE-1)*MIN_ALLOC] = 0; s_free = s_buffer; if( argc == 2 ) { FILE *file = fopen( _argv[1], "r" ); if( file ) { fseek( file, 0, SEEK_END ); uint32 fsize = ftell( file ); rewind( file ); uint32 size = (fsize+3)/4; uint32 *data = new uint32[size+1]; data[0] = size; data++; fread( data, 1, fsize, file ); // endian-reverse big-endian data for( uint32 i = 0; i < size; i++ ) { data[i] = ( data[i] >> 24 ) | (( data[i] >> 8 ) & 0x0000FF00) | (( data[i] << 8 ) & 0x00FF0000) | ( data[i] << 24 ); } fclose( file ); VM::Go( data ); // Leak data[] and let the OS clean it up after us } else { printf( "Couldn't open file %s for reading.\n", _argv[1] ); } } else { printf("Usage: icfp filename.um\n"); } return 0; };
Private
[
?
]
Run code
Submit