• Javascript Virtual Machine

    by  • September 3, 2011 • .Net, HTML5, Journal, Programming • 0 Comments

    Many years ago I had to wave goodbye to my collection of Psion handheld computers as I put them on sale on eBay. They were incredible computers and way ahead of their time. Over the years I had owned the series 3, 3a, 3mx, Revo, Series 5 and 5mx. The only one I never got a chance to own was the Series 7, the top of the line colour machine which looking back, was the forerunner to Netbooks by at least 8 years.

    However I am not here to talk about the devices themselves, but the great programming language and runtime contained within called OPL. I spent years developing on OPL and when I finally gave up on my Psion computers I then built a virtual machine and language runtime to allow me to use all my applications on my windows mobile device. This involved wrapping system calls, creating virtual machines to handle file operations and the bespoke file types used on the handheld machines.

    In time work progressed and I eventually ported the project over to Silverlight, allowing me to run any OPO application from a web browser. This proved very tricky at the time as Silverlight at that time did not include the WritableBitmap class so I had to ‘regigger’ some code to make pixel based graphics work with Silverlight as it by default worked with Vector graphics. I created a pixel level graphics library that wrote out to a 2D array that was then passed to a PNG encoder (for lossless compression) and then piped into a picture object.

    So once graphics were sorted and recoded I finally had a runtime in the browser.

    But with HTML5, times are a changing and so are the ways that people are accessing content on the Internet. Silverlight wasn’t the great champion against Flash that Microsoft had hoped, and Flash itself has fallen from grace, mainly because it is useless on Mobile devices.

    HTML5 has brought us the canvas element, audio element, background workers and a whole host of other improvements. This coupled with the incredible increase in Javascript virtual machine performance has meant running a Javascript based Virtual Machine in the browser has finally become a reality.

    You can have a look at the progress over at http://www.MrPfister.com/src/CaffeinedOPO/TestFramework.html

    How it works?

    The Virtual Machine is split into several segments, covering reading the source file, memory management, OpCode processing, String processing and the variable stack.

    Interpreter vs JIT’er?

    As the byte code isn’t being compiled and run natively but instead run using a Javascript virtual machine, we have the choice of either having a JIT’er or interpreting OpCodes one by one. A JIT’er is a Just-In-Time Compiler, it would work by scanning ahead in the byte code and converting it to Javascript which is run directly instead of running the OpCode processing code. This would give a small performance increase to code run multiple times however would be far more complex. In the end I choose a purely interpreted route after messing around testing a JIT’er implementation that uses HTML5 local storage as the JIT cache I found the performance gains were minimal or none, and cost a lot more in terms of required Javascript code that needed to be downloaded.

    OPO itself is a Stack based programming language, it uses 16 & 32 bit Integers, Doubles, Floats and Strings. OPL programmes are converted to OPO byte code, for use in the Javascript runtime this byte code needs to be converted into Hex so it can be embedded easily into web pages or Javascript strings. The virtual machine converts this back to a byte array using a simple Hex to Byte Array converter:

    function Hex2Bytes(s) {
      r=[];
      for (var i=0; i<s.length; i++) {
        r.push(parseInt(s[i] + s[++i], 16));
      }
      return r;
    }
    

    The application declares memory usage at various stages. Firstly as the application is read, memory is allocated to global variables, then as procedures are called and placed on the stack, memory is allocated from the heap and assigned to the function. Calls to various OpCodes can allocate additional memory from the heap, a bit like using ALLOC. Below is my implementation of a memory manager, the only issue is that it doesn’t compact space after it is deallocated and thus can become easily fragmented. My initial workaround is just to use a larger memory allocation.

    var Mem = function(size) {
      // Alloc the memory
      this.m = new Array(size);
      
      // saves which cells memory belongs to
      // Layout: A/D, Size, Offset
      this.c = [[0,size,0]];
      
      // Peek at the contents of a memory address
      this.peek = function(i) {
        return this.m[i];
      };
      
      // Allocate in memory contents of a certain size
      this.alloc = function(s) {
        wO('Allocating ' + s + 'bytes of memory');
        for(var i = 0; i< this.c.length; i++) {
          var l = this.c[i][1], o = this.c[i][2];
          if (this.c[i][0] == 0 && l >= s) {
            // Cell is deallocated and has more or equal to the required length
            if (l == s) {
              // Equal sizes, reallocate cell
              this.c[i][0] = 1;
              return o;
            } else {
              // Cell has more space than allocation, reallocate and create new
              this.c[i][0] = 1;
              this.c[i][1] = s;
              
              // Create new cell
              this.c.push([0, l - s, o + s]);
              return o;
            }
          }
        }
        // Allocation failed due to lack of space.
        return -1;
      };
      
      // Deallocate memory at a certain start point
      this.dealloc = function(s) {
        for (var i = 0; i < this.c.length; i++) {
          if (this.c[i][2] == s) {
            this.c[i][0] = 0;
            return 1;
          }
        }
        return -1;
      }
      
      // Reallocate the size of a memory structure
      this.realloc = function(s, n) {
        for (var i = 0; i < this.c.length; i++) {
          if (this.c[i][2] == s) {
            var l = this.c[i][1], o = this.c[i][2];
            if (n > l) {
              // New Allocation is larger
              var a = this.alloc(n);
              
              // Copy the data from the old location to the new
              this.m.splice(a,l,this.m.slice(s,l));
            } else if (n < l) {
              // New Allocation is smaller
              this.c[i][1] = n;
              
              // Create new empty cell
              this.c.push([0, l - n, o + s]);
              return;
            }
          }
        }
      }
      
      // Copy a memory sequence into memory
      this.set = function(o, v) {
        if (o >= 0 && o < this.m.length) {
          this.m.splice(o,v.length, v);
        }
      }
    }
    

    Strings are stored in an interesting format in the byte code. Strings have a maximum length of 255, and the current length is represented by the first byte in the sequence. To read a string from the byte array representing the byte code I use the following function where a represents the a and o represents the offset.

    function CStr(a,o) {
      var l = a[o], r = "";
      for (var i = o + 1; i<=o+l; i++) {
        r += String.fromCharCode(a[i]);
      }
      return r;
    }
    

    Like strings integers were interesting, they are stored in the byte code as a sequence of bytes which are converted to 16, 32 and 64 bit signed integers along with 64bit float. In C# the conversion was easy using the BitConverter class, however in Javascript we needed to be a bit more hands on.

    function i16(a,o) {
        return iC(a,o,2);
    }
    
    function i32(a,o) {
        return iC(a,o,4);
    }
    
    function iC(a,o,l) {
        var r = 0;
        for (var i=0; i<l; i++) {
          r += a[i + o] << (i * 8);
        }
        return r;
    }
    

    More to come shortly on how an OPO file is read…

    About

    Software engineer. Tea drinker

    http://MrPfister.com

    Leave a Reply

    Your email address will not be published. Required fields are marked *