To test the existing functionality of LilyVM and its assembler, I decided to implement a simple, well-known cryptography algorithm, RC4. It's not the kind that anyone should use today, because it's got a lot of known effective attacks against it, but it's an easy real-world example of a simple algorithm to play with.

I also like to use it as a random number generator.

Lessons learned tonight:

  • Some more addressing modes to handle things like de-reference pointers without separate load/store instructions would make things MUCH more concise. I think I can add more addressing modes without any overhead.
  • I thought about adding a "swap" instruction because it's done twice in this example. Still not sure about this one.
  • I need better debugging tools! (You'd think inspecting the state of your own VM would be easy.)
  • The code is getting a bit messy and needs a cleanup pass.
  • I really really really need a way to define arbitrary data. In this example I used instructions in place of data just so I had data to work with on the algorithm. Something to just occupy a block of some number of Words, literal numbers, and possibly literal strings would go a long way here.
  • Emacs's asm-mode is barely suitable for this. Maybe I just need to get used to it.
  • I ended up using the stack as though it was just a big series of registers. I guess it's how local variables really would be used normally, so maybe it's not so bad.
  • Being able to create labels that map to arbitrary values instead of just memory locations could have replaced a lot of the arbitrarily-numbered stack positions.
  • I lack sufficient error handling. I want to avoid excessive error checking, and I want to run in places where exceptions are disabled. (I'm looking at you, Unreal 4.) I might have to resort to the evil black magic that is setjmp()/longjmp().
  • I have need function calls. I have no kind of calling convention or anything. There was only a little bit of duplicated code here, though.

Here's the RC4 implementation I made a long time ago that I tested it against.

The actual code follows below. Excuse the lack of syntax highlighting. I guess I need to make the syntax a little more like some common assembler syntax to use an off-the-shelf syntax highlighter.

This code probably will not work for much longer because the assembler and VM are both works in progress. Not that it matters, because I still haven't actually put the source code out anywhere yet. This is mostly a message to any future users (and myself) that this code is not a good example to use.

Final disclaimer: There may be lots of bugs in this implementation.

;;; ----------------------------------------------------------------------
;;; Code section
;;; ----------------------------------------------------------------------

start:

;;; ----------------------------------------------------------------------
;;; Initialize state array and i, j variables

        mov 256 $0

cryptoFillLoop:

        add $0 -1 $0
        add $0 rc4_cryptostate $1
        store $0 $1
        brnz $0 cryptoFillLoop

        ;; null can be used instead of zero here, and the entire mov
        ;; instruction will omit the parameter Word for that.
        mov null *rc4_j             ; j = 0
        mov null *rc4_i             ; i = 0

;;; ----------------------------------------------------------------------
;;; Take the key and use it to initialize the state array

setKeyLoop:

        ;; Key length is hardcoded here until I have a better way to
        ;; specify it.
        div *rc4_i 8 null $4       ; keyval = key[i % 8] (8 is key length)
        add key $4 $4
        load $4 $4

        div $4 256 null $4         ; keyval %= 256

        add rc4_cryptostate *rc4_i $5
        load $5 $5

        add *rc4_j $5 *rc4_j       ; j += state[i]
        add *rc4_j $4 *rc4_j       ; j += keyval
        div *rc4_j 256 null *rc4_j ; j %= 256

        ;; Swap state[i] and state[j]
        add rc4_cryptostate *rc4_j $5
        add rc4_cryptostate *rc4_i $6
        load $5 $7
        load $6 $8
        store $7 $6
        store $8 $5

        ;; i++
        add *rc4_i 1 *rc4_i
        ;; loop if i != 256
        add *rc4_i -256 $3
        brnz $3 setKeyLoop

;;; ----------------------------------------------------------------------
;;; Get ready to encrypt

        ;; Reset i, j
        mov null *rc4_j
        mov null *rc4_i

        ;; Loop counter
        mov 0 $10

;;; ----------------------------------------------------------------------
;;; Encryption loop

encryptLoop:

        ;; i = (i + 1) % 256;
        add *rc4_i 1 *rc4_i
        div *rc4_i 256 null *rc4_i

        ;; j = (j + state[i]) % 256;
        add rc4_cryptostate *rc4_i $6 ; $6 = &state[i]
        load $6 $6                    ; $6 = *$6
        add *rc4_j $6 *rc4_j          ; j += $6
        div *rc4_j 256 null *rc4_j    ; j %= 256

        ;; Swap state[i] and state[j]
        add rc4_cryptostate *rc4_j $5
        add rc4_cryptostate *rc4_i $6
        load $5 $7
        load $6 $8
        store $7 $6
        store $8 $5

        add $7 $8 $9            ; $9 = state[i] + state[j]
        div $9 256 null $9      ; $9 %= 256

        ;; $9 = state[$9]
        add rc4_cryptostate $9 $9
        load $9 $9

        ;; At this point we have our byte of randomness from RC4, and
        ;; can go ahead and encrypt another byte with a xor.
        add $10 plaintext $11   ; Get a plaintext byte
        load $11 $12
        xor $12 $9 $12          ; XOR it
        store $12 $11           ; Store it right back to the same
                                ; buffer.

        ;; $10++
        add $10 1 $10
        ;; loop if $10 != 8
        add $10 -8 $11
        brnz $11 encryptLoop

;;; ----------------------------------------------------------------------
;;; Done!

        stop

;;; ----------------------------------------------------------------------
;;; Some empty space

        invalid
        invalid
        invalid
        invalid
        invalid
        invalid
        invalid
        invalid

;;; ----------------------------------------------------------------------
;;; Static variables
;;; ----------------------------------------------------------------------

        ;; The assembler lacks features to declare bytes or volumes of
        ;; space directly, so we're cheating for now and using
        ;; instructions with known opcode values to fill space.

        ;; Plaintext is just 8 Words of zero right now.

        .export plaintext
plaintext:
        invalid
        invalid
        invalid
        invalid
        invalid
        invalid
        invalid
        invalid

        ;; Can't declare words or bytes, so the machine code generated
        ;; from this snippet of assembly will be our key because I'm a
        ;; horrible person. It's 8 words long.

        .export key
key:    add 1 2 3
        add 4 5 6

        ;; rc4_j and rc4_i are the i and j variables from the RC4
        ;; algorithm.

        .export rc4_i
rc4_i:  invalid

        .export rc4_j
rc4_j:  invalid

        .export rc4_cryptostate
rc4_cryptostate:
        invalid
        ;; I guess the crypto state is the rest of memory.

It'll probably take a while before I get all the fixes and changes done I mentioned here. So I'm not sure when the next time I'll post is going to be.


Tags: [ gamedev ] [ coding ] [ lilyvm ]

comments powered by Disqus
Copyright © 2015 Clifford Jolly
All rights reserved