malbolge.c

// CC0, do whatever
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <stdbool.h>

#include <sys/mman.h>
#include <signal.h>
#include <unistd.h>

#define i8    int8_t
#define u8   uint8_t
#define i16  int16_t
#define u16 uint16_t
#define i32  int32_t
#define u32 uint32_t
#define i64  int64_t
#define u64 uint64_t

#define INLINE  static inline __attribute__((always_inline))
#define NOINLINE __attribute__((noinline))
#define UNLIKELY(X) __builtin_expect(X, 0)
#define LIKELY(X) __builtin_expect(X, 1)
#define assert(X) if (!(X)) __builtin_unreachable();
#define COMPUTED_GOTO 1



// ############################## malbolge things ##############################
#ifndef REGULAR
  #define REGULAR 0 // implement regular 10-bit malboge
#endif

#if REGULAR

typedef u32 W;
#define SIZE 10
#define END 59049ULL // 3^10

#else


typedef u32 W;
#define SIZE 19
#define END 1162261467ULL // 3^19

// typedef u32 W;
// #define SIZE 20 // even sizes don't work for whatever reason :/
// #define END 3486784401ULL // 3^20

// typedef u64 W;
// #define SIZE 21
// #define END 10460353203ULL // 3^21

// typedef u64 W;
// #define SIZE 23
// #define END 94143178827ULL // 3^23


#endif
static const char* translation = "                                 5z]&gqtyfr$(we4{WP)H-Zn,[%\\3dL+Q;>U!pJS72FhOA1CB6v^=I_0/8|jsb9m<.TVac`uY*MK'X~xDl}REokN:#?G\"i@";
static const u8 crz[] =  {1,0,0, 9, 1,0,2, 9, 2,2,1};
static const u8 crz2[] = {4,3,3,1,0,0,1,0,0,9,9,9,9,9,9,9,4,3,5,1,0,2,1,0,2,9,9,9,9,9,9,9,5,5,4,2,2,1,2,2,1,9,9,9,9,9,9,9,4,3,3,1,0,0,7,6,6,9,9,9,9,9,9,9,4,3,5,1,0,2,7,6,8,9,9,9,9,9,9,9,5,5,4,2,2,1,8,8,7,9,9,9,9,9,9,9,7,6,6,7,6,6,4,3,3,9,9,9,9,9,9,9,7,6,8,7,6,8,4,3,5,9,9,9,9,9,9,9,8,8,7,8,8,7,5,5,4,9,9,9,9,9,9,9};
// uint16_t crz2[16*9];
// for (int y = 0; y < 9; y++) for (int x = 0; x < 9; x++) crz2[x*16 + y] = crz[(y%3)+3*(x%3)] + crz[(y/3)+3*(x/3)]*3;

INLINE W crazy(W a, W d) {
  W result = 0; W k = 1;
  for(int pos = 0; pos < SIZE/2; pos++) {
    W am=a%9; W ad = a/9;
    W dm=d%9; W dd = d/9;
    result+= k * crz2[am + 16*dm];
    a = ad; d = dd; k*= 9;
  }
  if (SIZE&1) {
    W am=a%3; W ad = a/3;
    W dm=d%3; W dd = d/3;
    result+= k * crz[am + 4*dm];
    a = ad; d = dd; k*= 3;
  }
  return result;
}
INLINE W rotate(W x) {
  W t = END/3;
  #if REGULAR
    W mod = x%3;
    W div = x/3;
    return div + mod*t;
  #else
    W base = x%t;
    W mod = base%3;
    W div = base/3;
    return div + mod*(t/3) + (x-base);
  #endif
}
INLINE W increment(W x) {
  W r = x+1;
  #if REGULAR
  if (UNLIKELY(r==END)) return 0;
  #else
  // if (UNLIKELY(r%(END/3)==0)) return r - (END/3); // kind of necessary to be correct (maybe not for the D register increment?) but eh things work fine without
  #endif
  return r;
}



// horrible hack for printing trits in printf
char buffers[16][SIZE+1];
int currBuf = 0;
char* str_trit(W x) {
  char* buf = buffers[currBuf++&15];
  buf[SIZE] = 0;
  for (int i = 0; i < SIZE; i++) {
    buf[SIZE-i-1] = '0' + x%3;
    x/= 3;
  }
  return buf;
}
void print_trit(W x) {
  printf("%s", str_trit(x));
}



// ############################## memory management ##############################
static u64 pageSize;
static W* mem;
static u64 memSize = END*sizeof(W);
static bool sigOn = false;
static W pattern[6];

void enable(void* base_addr, u64 len) {
  // int err = mprotect(base_addr, len, PROT_READ|PROT_WRITE);
  // if (err != 0) {
  //   printf("Failed to change memory protection\n");
  //   exit(1);
  // }
  // mmap appears to be _slightly_ faster
  void* addr = mmap(base_addr, len, PROT_READ|PROT_WRITE, MAP_POPULATE|MAP_PRIVATE|MAP_ANON|MAP_FIXED, -1, 0);
  if (addr==MAP_FAILED) {
    printf("Failed to change memory protection\n");
    exit(1);
  }
}

void handleSegfault(int num, siginfo_t* si, void* vcontext) {
  void* addr = si->si_addr;
  
  if (!sigOn) {
    printf("SIGSEGV before file has been loaded!\n");
    exit(1);
  }
  if (addr < (void*)mem || addr > (void*)mem+memSize) {
    printf("SIGSEGV outside of allocated memory, on what would be memory offset %ld\n", (W*)addr - mem);
    exit(1);
  }
  
  void* addr_base = (void*)((u64)addr & ~(pageSize-1));
  #if DEBUG
  printf("Allocating at %p because %p; ", addr_base, addr);
  #endif
  enable(addr_base, pageSize);
  
  W* curr = addr_base;
  i64 off = (curr-mem) % (END/3);
  for (i32 i = 0; i < pageSize; i+= sizeof(W)) *curr++ = pattern[off++%6];
}

u64 roundUp(u64 v) {
  return ((v-1) & ~(pageSize-1)) + pageSize;
}




// ############################## main ##############################
__attribute__((hot))
int main(int argc, char* argv[]) {
  pageSize = sysconf(_SC_PAGESIZE);
  
  mem = mmap(NULL, memSize, PROT_NONE, MAP_NORESERVE|MAP_PRIVATE|MAP_ANON, -1, 0);
  W* tmp = mem; W* mem = tmp;
  #if DEBUG
  printf("mem = %p\n", mem);
  #endif
  struct sigaction action;
  memset(&action, 0, sizeof(struct sigaction));
  action.sa_flags = SA_SIGINFO;
  action.sa_sigaction = handleSegfault;
  sigaction(SIGSEGV, &action, NULL);
  
  // open file
  FILE* file = fopen(argv[1],"rb");
  fseek(file, 0, SEEK_END);
  u64 size = ftell(file);
  rewind(file);
  
  // allocate starting memory
  u64 sizeRounded = roundUp(size);
  enable(mem, sizeRounded*sizeof(W));
  
  // convert file to memory
  u64 off = 0;
  char data[1024];
  while (size) {
    int am = LIKELY(size>1024)? 1024 : size;
    int _ = fread(&data, 1, am, file);
    #pragma GCC unroll 8
    for (int i = 0; i < am; i++) {
      W w = data[i];
      if (w!=' ' && w!='\r' && w!='\n') mem[off++] = w;
    }
    size-= am;
  }
  
  // pad memory
  while (off < sizeRounded) {
    mem[off] = crazy(mem[off-1], mem[off-2]);
    off++;
  }
  
  { // prepare pattern for further allocations
    W n2 = mem[off-2];
    W n1 = mem[off-1];
    u64 off2 = off;
    for (int i = 0; i < 6; i++) {
      W n0 = crazy(n1, n2);
      pattern[off2%6] = n0;
      n2 = n1;
      n1 = n0;
      off2++;
    }
  }
  sigOn = true;
  
  // W t = 6392438068%END; print_trit(t); putchar(10); print_trit(rotate(t)); putchar(10); exit(1);
  
  W c, a;
  c = a = 0;
  W* d = mem;
  
  #if !COMPUTED_GOTO || DEBUG || REGULAR // ############################## regular switch ##############################
  while (1) {
    #if REGULAR
    W ins = (c + mem[c]) % 94;
    #else
    assert(c<END);
    W c_area = c/(END/3);
    W c_base = c%(END/3);
    const W a1_off = 94 - ((END-1)/6 - 29524)%94; // 29524 = (3^11-1)/6
    const W a2_off = 94 - ((END-1)/3 - 59048)%94; // 59048 = (3^11-1)/3
    // printf("%d %d\n", a1_off, a2_off); exit(0);
    
    // W ins = (c_base + mem[c] + (c_area==0? 0 : c_area==1? a1_off : a2_off)) % 94;
    // static const int offs[] = {0, a1_off, a2_off};
    // W ins = (c_base + mem[c] + offs[c_area]) % 94;
    static const int offs[] = {0, ((i64)a1_off - (i64)(END/3))%94+94, ((i64)a2_off - (i64)(2*(END/3))%94+94)};
    W ins = (c + mem[c] + offs[c_area]) % 94;
    
    #endif
    #if DEBUG
    printf("c=%s,d=%s,a=%s; ins %2d; [d]=%s; ", str_trit(c), str_trit(d-mem), str_trit(a), (i32)ins, str_trit(*d));fflush(stdout);
    #endif
    switch (ins) {
      case 4:
        c = *d;
        break;
      case 5:
        putchar(a);fflush(stdout);
        break;
      case 23:;
        int chr = getchar();
        a = chr==EOF? END-1 : chr;
        break;
      case 39:
        a = *d = rotate(*d);
        break;
      case 40:
        d = mem + *d;
        break;
      case 62:
        a = *d = crazy(a, *d);
      case 68:
        break;
      case 81:
        putchar(10);
        return 0;
      default:
        break;
    }
    #if DEBUG
    printf("[nd]=%s\n", str_trit(*d));fflush(stdout);
    if (mem[c]<33 | mem[c]>126) {
      printf("Invalid value at [c]: %s; c=%s\n", str_trit(mem[c]), str_trit(c));
      exit(1);
    }
    #endif
    mem[c] = translation[mem[c]];
    c = increment(c);
    d = mem+increment(d-mem);
  }
  #else // ############################## computed goto version ##############################
  {
    const W a1_off = 94 - ((END-1)/6 - 29524)%94; // 29524 = (3^11-1)/6
    const W a2_off = 94 - ((END-1)/3 - 59048)%94; // 59048 = (3^11-1)/3
    static const int offs[] = {0, ((i64)a1_off - (i64)(END/3))%94+94, ((i64)a2_off - (i64)(2*(END/3))%94+94)};
    static const void* jmps[94];
    for (int i = 0; i < 94; i++) jmps[i] = &&INS_DEF;
    jmps[4] = &&INS_4;
    jmps[5] = &&INS_5;
    jmps[23] = &&INS_23;
    jmps[39] = &&INS_39;
    jmps[40] = &&INS_40;
    jmps[62] = &&INS_62;
    jmps[68] = &&INS_68;
    jmps[81] = &&INS_81;
    
    #define JUMP { W c_area = c/(END/3); W ins = (c + mem[c] + offs[c_area]) % 94; goto *jmps[ins]; }
    
    JUMP;
    
    #define NEXT \
    mem[c] = translation[mem[c]]; \
    c = increment(c); \
    d++; JUMP \
    
    INS_4:
      c = *d;
      NEXT;
    INS_5:
      putchar(a);fflush(stdout);
      NEXT;
    INS_23:;
      int chr = getchar();
      a = chr==EOF? END-1 : chr;
      NEXT;
    INS_39:
      a = *d = rotate(*d);
      NEXT;
    INS_40:
      d = mem + *d;
      NEXT;
    INS_62:
      a = *d = crazy(a, *d);
    INS_68:
      NEXT;
    INS_81:
      putchar(10);
      return 0;
    INS_DEF:
      NEXT;
  }
  #endif
}