[iojs][emscripten] Call sudoku solver function implemented in C on iojs

libsudoku.c

// [sudoku solver in C11 for emscripten]
// emcc -Wall -Wextra -std=c11 libsudoku.c -o libsudoku.js \
//      -s EXPORTED_FUNCTIONS="['_sudoku','_output']" \
//      -s RESERVED_FUNCTION_POINTERS=20
//
// [Options for optimization and debug level]
//    -O0: no optimization (default)
//    -O1: remove debug info
//    -O2: minify JS code (.mem file generated. it is required for run)
//    -O3: more JS optimization
//    -g1: preserve whitespaces
//    -g2: preserve function names in JS code
//    -g3: preserve variable names in JS code
//    -g4: generate source maps (.map file generated)
#include <stdio.h>

// helpers for board data
static inline unsigned masks(unsigned i) {return i ? 1 << (i - 1) : 0;}
static inline unsigned row(unsigned i) {return i / 9;}
static inline unsigned col(unsigned i) {return i % 9;}
static inline unsigned blk(unsigned i) {return i / 27 * 3 + i % 9 / 3;}
extern void output(unsigned board[])
{
  char buffer[(9 + 3) * (9 + 3)];
  char* cur = buffer;
  for (unsigned y = 0; y < 9; y++) {
    for (unsigned x = 0; x < 9; x++) {
      *cur++ = board[y * 9 + x] > 0 ? board[y * 9 + x] + '0' : '.';
      if (x % 3 == 2) *cur++ = x == 8 ? '\n' : '|';
    }
    if (y == 8) {
      *cur++ = '\0';
    } else if (y % 3 == 2) {
      for (unsigned i = 0; i < 11; i++) *cur++ = i % 4 == 3 ? '+' : '-';
      *cur++ = '\n';
    }
  }
  puts(buffer);
}

// sudoku solver
typedef void (*sudoku_cb)(unsigned board[]);
typedef struct {
  unsigned board[81];
  unsigned rows[9], cols[9], blks[9];
  sudoku_cb callback;
} sudoku_t;

static void sudoku_init(sudoku_t* s, unsigned board[])
{
  for (unsigned i = 0; i < 81; i++) {
    const unsigned mask = masks(board[i]);
    s->rows[row(i)] |= mask, s->cols[col(i)] |= mask, s->blks[blk(i)] |= mask;
    s->board[i] = board[i];
  }
}

static void sudoku_solve(sudoku_t* s, unsigned i)
{
  if (i == 81) {
    s->callback(s->board);
  } else if (s->board[i] != 0) {
    sudoku_solve(s, i + 1);
  } else {
    const unsigned r = row(i), c = col(i), b = blk(i);
    const unsigned used = s->rows[r] | s->cols[c] | s->blks[b];
    for (unsigned v = 1; v <= 9; v++) {
      const unsigned mask = masks(v);
      if (used & mask) continue;
      s->board[i] = v;
      s->rows[r] |= mask, s->cols[c] |= mask, s->blks[b] |= mask;
      sudoku_solve(s, i + 1);
      s->rows[r] &= ~mask, s->cols[c] &= ~mask, s->blks[b] &= ~mask;
      s->board[i] = 0;
    }
  }
}

extern void sudoku(unsigned board[], sudoku_cb callback)
{
  sudoku_t s = {
    .board = {0}, .rows = {0}, .cols = {0}, .blks = {0}, .callback = callback};
  sudoku_init(&s, board);
  sudoku_solve(&s, 0);
}

Makefile

all: libsudoku.js sudoku.js sudoku
clean:
	rm -f libsudoku.js sudoku.js sudoku
	rm -f libsudoku.js.map sudoku.js.map
	rm -f libsudoku.js.mem sudoku.js.mem

# library for using functions in hand written JavaScript code
libsudoku.js: libsudoku.c
	emcc -g4 -Wall -Wextra -std=c11 $^ -o $@ \
		-s EXPORTED_FUNCTIONS="['_output', '_sudoku']" \
		-s RESERVED_FUNCTION_POINTERS=20

# whole console program as js code
sudoku.js: libsudoku.c sudoku-main.c
	emcc -O1 -Wall -Wextra -std=c11 $^ -o $@

# executable by c compiler
sudoku: libsudoku.c sudoku-main.c
	$(CC) -O3 -Wall -Wextra -std=c11 $^ -o $@

sudoku-call-libsudoku.js

// use emscripten generated "libsudoku.js" as a library
var libsudoku = require("./libsudoku.js");

// use ccall to call emscripten C function
var output = function (board) {
    // unsigned[] as Uint8Array view of Uint32Array
    var unsignedBoard = new Uint8Array(new Uint32Array(board).buffer);
    // ccall(cfuncname, return_type, argument_types, arguments)
    // type: "string", "number", "array" or undefined as return type
    return libsudoku.ccall("output", undefined, ["array"], [unsignedBoard]);
};

// use cwrap to call emscripten C function with callback
var sudoku = function sudoku(board, callback) {
    // NOTE: For using addFunction(),
    //    emcc option "-s REQUIRED_FUNCTION_POINTERS=10" (more than 1) required
    var callbackPtr = libsudoku.Runtime.addFunction(function (resultPtr) {
        var r = new Uint32Array(libsudoku.HEAPU8.buffer, resultPtr, 81);
        // NOTE: copy memory value as array for async use in callback(like IO)
        callback([].slice.call(r));
    });
    var unsignedBoard = new Uint8Array(new Uint32Array(board).buffer);
    sudoku._cfunc(unsignedBoard, callbackPtr);
    libsudoku.Runtime.removeFunction(callbackPtr);
};
// pointer as a "number"
sudoku._cfunc = libsudoku.cwrap("sudoku", undefined, ["array", "number"]);


// main
if (process.argv.length <= 2) {
    // example problem from http://rosettacode.org/wiki/Sudoku
    var problem = [
        8, 5, 0, 0, 0, 2, 4, 0, 0,
        7, 2, 0, 0, 0, 0, 0, 0, 9,
        0, 0, 4, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 1, 0, 7, 0, 0, 2,
        3, 0, 5, 0, 0, 0, 9, 0, 0,
        0, 4, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 8, 0, 0, 7, 0,
        0, 1, 7, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 3, 6, 0, 4, 0
    ];
    console.log("[problem]");
    output(problem);
    console.log("[solution]");
    //sudoku(problem, output);
    /**/
    sudoku(problem, function (board) {
        var buf = "";
        for (var y = 0; y < 9; y++) {
            for (var x = 0; x < 9; x++) {
                buf += board[y*9 + x] > 0 ? board[y*9 + x].toString() : ".";
                if (x % 3 === 2) buf += x === 8 ? "\n" : "|";
            }
            if (y === 2 || y === 5) buf += "---+---+---\n";
        }
        console.log(buf);
    });
    /**/
} else {
    for (var i = 2; i < process.argv.length; i++) {
        var problem = Array(81);
        for (var j = 0; j < 81; j++) {
            var ch = process.argv[i].charCodeAt(j);
            problem[j] = 0 <= ch && ch <= 9 ? v : 0;
        }
        console.log("[problem]");
        output(problem);
        console.log("[solution]");
        sudoku(problem, output);
    }
}

sudoku-main.c

#include <stdio.h>

extern void output(unsigned board[]);
typedef void (*sudoku_cb)(unsigned board[]);
extern void sudoku(unsigned board[], sudoku_cb callback);

// example problem from http://rosettacode.org/wiki/Sudoku
static unsigned problem[] = {
  8, 5, 0, 0, 0, 2, 4, 0, 0,
  7, 2, 0, 0, 0, 0, 0, 0, 9,
  0, 0, 4, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 1, 0, 7, 0, 0, 2,
  3, 0, 5, 0, 0, 0, 9, 0, 0,
  0, 4, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 8, 0, 0, 7, 0,
  0, 1, 7, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 3, 6, 0, 4, 0
};

extern int main(int argc, char* argv[])
{
  if (argc <= 1) {
    puts("[problem]");
    output(problem);
    puts("[solutions]");
    sudoku(problem, output);
  } else {
    for (int i = 1; i < argc; i++) {
      char ch = -1;
      for (int c = 0; c < 81; c++) {
        if (ch == '\0') {
          problem[c] = 0;
        } else {
          ch = argv[i][c];
          problem[c] = '0' <= ch && ch <= '9' ? ch - '0' : 0;
        }
      }
      puts("[problem]");
      output(problem);
      puts("[solution]");
      sudoku(problem, output);
    }
  }
  return 0;
}

Profile

$ time ./sudoku
real    0m0.020s
user    0m0.015s
sys 0m0.002s

$ time iojs sudoku-call-libsudoku.js
real    0m0.355s
user    0m0.313s
sys 0m0.037s

$ time iojs sudoku.js
real    0m0.888s
user    0m0.312s
sys 0m0.045s

---

Profile from https://gist.github.com/bellbind/2415a53ff67b28233d94

$ time iojs sudoku-backtrack.js
real    0m0.723s
user    0m0.684s
sys 0m0.030s

$ time iojs sudoku-function.js
real    0m1.984s
user    0m1.771s
sys 0m0.060s

$ time iojs sudoku-list.js
real    0m2.210s
user    0m2.134s
sys 0m0.049s

$ time iojs sudoku.js
real    0m2.682s
user    0m2.584s
sys 0m0.056s

$ time ./sudoku
real    0m0.018s
user    0m0.012s
sys 0m0.002s

Used emscripten 1.33.0