x86 assembly (on Win32)
“SPEED!” seems to be hugely important here, and we all know nothing beats assembly language in that regard. So, let’s do that in assembly!
This is an implementation of the language in x86 assembly language (in NASM syntax), with the numbers stored and interpreted as unsigned 32-bit integers, using the native x86 stack directly. Stack underflow, and overflow during any arithmetic operation (or division by zero) is a runtime error, terminating the program with an error message.
global _start
extern _GetCommandLineA@0
extern _GetStdHandle@4
extern _CreateFileA@28
extern _GetFileSize@8
extern _LocalAlloc@8
extern _ReadFile@20
extern _CloseHandle@4
extern _WriteFile@20
section .text
; ---------------------------------------------------------------------------------------
; Initialization
; ---------------------------------------------------------------------------------------
_start:
; Retrieve command line
CALL _GetCommandLineA@0
; Skip argv[0]
MOV ESI, EAX
XOR EAX, EAX
skipuntilspace:
MOV AL, [ESI]
INC ESI
TEST EAX, EAX
JE missingparam
CMP EAX, ' '
JNE skipuntilspace
INC ESI
; Open the file
PUSH 0
PUSH 80h
PUSH 3
PUSH 0
PUSH 1
PUSH 80000000h
PUSH ESI
CALL _CreateFileA@28
CMP EAX, -1
JE cannotopenfile
; Get its size
PUSH EAX
PUSH 0
PUSH EAX
CALL _GetFileSize@8
PUSH EAX
; Allocate memory buffer
PUSH EAX
PUSH 0
CALL _LocalAlloc@8
TEST EAX, EAX
MOV ESI, EAX
JZ outofmemory
POP ECX
POP EAX
PUSH EAX
; Store end-of-program pointer
MOV [programend], ESI
ADD [programend], ECX
; Read the file contents
PUSH 0
PUSH buff
PUSH ECX
PUSH ESI
PUSH EAX
CALL _ReadFile@20
TEST EAX, EAX
JZ cannotopenfile
; Close the file
CALL _CloseHandle@4
; ---------------------------------------------------------------------------------------
; Main loop of the interpreter
; ---------------------------------------------------------------------------------------
; Store the end of stack into EBP
MOV EBP, ESP
; Push an initial 0 onto the stack
XOR EAX, EAX
PUSH EAX
mainloop:
; Load the next opcode, if not end of program
XOR EAX, EAX
CMP ESI, [programend]
MOV AL, [ESI]
JAE endloop
LEA ESI, [ESI+1]
; Check if the opcode is valid
CMP EAX, (maxop - opcodetable) / 8
JA fault_invalidopcode
; Check for required stack space
MOV ECX, [opcodetable + 8 * EAX + 4]
LEA EDI, [ESP + ECX]
CMP EDI, EBP
JA fault_stackunderflow
; Jump to the respective opcode handler
MOV EAX, [opcodetable + 8 * EAX]
JMP EAX
; ---------------------------------------------------------------------------------------
; Implementation of the specific operations
; ---------------------------------------------------------------------------------------
; ************** CAT 0000 (0): Concatenate (Combine top two numbers in a stack as if they were a string. ex: 12,5 -> 125)
op_concatenate:
POP EBX
POP EAX
MOV ECX, EAX
MOV EDI, 10
concat_loop:
XOR EDX, EDX
SHL EBX, 1
DIV EDI
LEA EBX, [4 * EBX + EBX]
TEST EAX, EAX
JNZ concat_loop
ADD EBX, ECX
PUSH EBX
JMP mainloop
; ************** INC 0001 (1): Increment (Add 1 to the number on the top of the stack)
op_increment:
POP EAX
ADD EAX, 1
PUSH EAX
JNC mainloop
JMP fault_intoverflow
; ************** DEC 0010 (2): Decrement (Subtract one from the number at the top of the stack)
op_decrement:
POP EAX
SUB EAX, 1
PUSH EAX
JNC mainloop
JMP fault_intoverflow
; ************** MUL 0011 (3): Multiply (Multiply the top two numbers in the stack)
op_multiply:
POP EAX
POP EDX
MUL EDX
TEST EDX, EDX
PUSH EAX
JZ mainloop
JMP fault_intoverflow
; ************** DIV 0100 (4): Divide (Divide the 2nd-to-top number by the top number on the stack)
op_divide:
POP ECX
TEST ECX, ECX
POP EAX
JZ fault_dividebyzero
XOR EDX, EDX
DIV ECX
PUSH EAX
JMP mainloop
; ************** MOD 0101 (5): Add (Add the top two numbers on the stack)
op_add:
POP EAX
ADD [ESP], EAX
JNC mainloop
JMP fault_intoverflow
; ************** SUB 0110 (6): Subtract (Subtract the top number on the stack from the one below it)
op_subtract:
POP EAX
SUB [ESP], EAX
JNC mainloop
JMP fault_intoverflow
; ************** EXP 0111 (7): Exponent (Calculate the second-to-top number to the power of the top number)
op_exponent:
POP ECX
POP EBX
MOV EAX, 1
exploop:
TEST ECX, 1
JZ expnomult
MUL EBX
TEST EDX, EDX
JNZ fault_intoverflow
expnomult:
SHR ECX, 1
JZ expdone
XCHG EAX, EBX
MUL EAX
TEST EDX, EDX
XCHG EAX, EBX
JZ exploop
JMP fault_intoverflow
expdone:
PUSH EAX
JMP mainloop
; ************** MOD 1000 (8): Modulus: (Find the second-to-top number modulo the top one)
op_modulus:
POP ECX
TEST ECX, ECX
POP EAX
JZ fault_dividebyzero
XOR EDX, EDX
IDIV ECX
PUSH EDX
JMP mainloop
; ************** ROR 1001 (9): Rotate Right (Shift the stack down one. The number on the bottom is now on the top)
op_rotright:
MOV EAX, [EBP - 4]
LEA ECX, [EBP - 4]
SUB ECX, ESP
MOV EDX, ESI
SHR ECX, 2
LEA EDI, [EBP - 4]
LEA ESI, [EBP - 8]
STD
REP MOVSD
MOV [ESP], EAX
CLD
MOV ESI, EDX
JMP mainloop
; ************** ROL 1010 (A): Rotate Left (Shift the stack up one. The number on the top is now on the bottom)
op_rotleft:
MOV EAX, [ESP]
LEA ECX, [EBP - 4]
SUB ECX, ESP
MOV EDX, ESI
SHR ECX, 2
LEA ESI, [ESP + 4]
MOV EDI, ESP
REP MOVSD
MOV [EBP - 4], EAX
MOV ESI, EDX
JMP mainloop
; ************** DUP 1011 (B): Duplicate (Copy the top number so that it appears twice. ex: 4,1 becomes 4,1,1)
op_duplicate:
PUSH DWORD [ESP]
JMP mainloop
; ************** DU2 1100 (C): Double Duplicate (Copy the top two numbers on the stack. ex: 4,1,2 becomes 4,1,2,1,2)
op_dblduplicate:
PUSH DWORD [ESP+4]
PUSH DWORD [ESP+4]
JMP mainloop
; ************** SWP 1101 (D): Swap (Swap the top two numbers on the stack. ex: 4,1,2 becomes 4,2,1)
op_swap:
POP EAX
POP EDX
PUSH EAX
PUSH EDX
JMP mainloop
; ************** SW2 1110 (E): Double Swap (Swap the top two numbers with two below them.ex: 1,2,3,4,5 becomes 1,4,5,2,3)
op_dblswap:
POP EAX
POP EBX
POP ECX
POP EDX
PUSH EBX
PUSH EAX
PUSH EDX
PUSH ECX
JMP mainloop
; ************** POP 1111 (F): Delete/Pop (Remove the number at the top of the stack)
op_pop:
POP EAX
JMP mainloop
; ---------------------------------------------------------------------------------------
; End of the program: print out the resulting stack and exit
; ---------------------------------------------------------------------------------------
endloop:
MOV ESI, ESP
printloop:
CMP ESI, EBP
JNB exit
MOV EAX, [ESI]
MOV EBX, ESI
PUSH EBX
CALL printnum
POP EBX
LEA ESI, [EBX + 4]
JMP printloop
exit:
MOV ESP, EBP
;POP EAX
XOR EAX, EAX
RET
; ---------------------------------------------------------------------------------------
; Faults
; ---------------------------------------------------------------------------------------
fault_invalidopcode:
MOV EAX, err_invalidopcode
JMP fault
fault_stackunderflow:
MOV EAX, err_stackunderflow
JMP fault
fault_dividebyzero:
MOV EAX, err_dividebyzero
JMP fault
fault_intoverflow:
MOV EAX, err_intoverflow
JMP fault
fault:
CALL print
MOV EAX, crlf
CALL print
MOV ESP, EBP
MOV EAX, 1
RET
missingparam:
MOV EAX, err_missingparameter
JMP fault
cannotopenfile:
MOV EAX, err_cannotopenfile
JMP fault
outofmemory:
MOV EAX, err_outofmemory
JMP fault
; ---------------------------------------------------------------------------------------
; Helper functions
; ---------------------------------------------------------------------------------------
printnum:
MOV EBX, 10
CALL printnumrec
MOV EAX, crlf
JMP print
printnumrec:
PUSH EAX
PUSH EDX
XOR EDX, EDX
DIV EBX
TEST EAX, EAX
JZ printnumend
CALL printnumrec
printnumend:
MOV EAX, EDX
CALL printdigit
POP EDX
POP EAX
RET
printdigit:
ADD EAX, '0'
MOV [printbuff], EAX
MOV EAX, printbuff
JMP print
print:
MOV ESI, EAX
PUSH 0
PUSH buff
CALL strlen
PUSH EAX
PUSH ESI
PUSH -11
CALL _GetStdHandle@4
PUSH EAX
CALL _WriteFile@20
RET
strlen:
XOR ECX, ECX
strlen_loop:
CMP BYTE [ESI+ECX], 0
JE strlen_end
LEA ECX, [ECX+1]
JMP strlen_loop
strlen_end:
MOV EAX, ECX
RET
; ---------------------------------------------------------------------------------------
; Data
; ---------------------------------------------------------------------------------------
section .data
; Table of opcode handlers and required stack space (in bytes, i.e. 4*operands)
opcodetable:
DD op_concatenate, 8
DD op_increment, 4
DD op_decrement, 4
DD op_multiply, 8
DD op_divide, 8
DD op_add, 8
DD op_subtract, 8
DD op_exponent, 8
DD op_modulus, 8
DD op_rotright, 0
DD op_rotleft, 0
DD op_duplicate, 4
DD op_dblduplicate, 8
DD op_swap, 8
DD op_dblswap, 16
DD op_pop, 4
maxop:
crlf DB 13, 10, 0
err_invalidopcode DB "Invalid opcode", 0
err_stackunderflow DB "Stack underflow", 0
err_dividebyzero DB "Division by zero", 0
err_intoverflow DB "Integer overflow", 0
err_missingparameter: DB "Missing parameter: Use nexlang file.bin", 0
err_cannotopenfile: DB "Unable to open input file", 0
err_outofmemory: DB "Not enough memory", 0
section .bss
programend RESD 1
printbuff RESD 1
buff RESD 1
To compile this, use something like
nasm.exe -fwin32 nexlang.asm
ld -o nexlang.exe -e _start nexlang.obj -s -lkernel32
The program receives the name of the binary file containing the program on the command line (e.g. nexlang.exe testprg.bin). When finished, it prints the final contents of the stack to standard output in a human-readable format.
To help with testing, save the following into nex.def:
%define CAT DB 00h
%define INC DB 01h
%define DEC DB 02h
%define MUL DB 03h
%define DIV DB 04h
%define ADD DB 05h
%define SUB DB 06h
%define EXP DB 07h
%define MOD DB 08h
%define ROR DB 09h
%define ROL DB 0Ah
%define DUP DB 0Bh
%define DU2 DB 0Ch
%define SWP DB 0Dh
%define SW2 DB 0Eh
%define POP DB 0Fh
And then write your NEX (“non-existing”, as named in the question title) programs using the above-defined mnemonics, and compile with something like
nasm.exe -p nex.def -o prg.bin prg.nex
E.g. for the original test case, use the following prg.nex:
INC ; 1
INC ; 2
INC ; 3
INC ; 4
DUP ; 4 4
DU2 ; 4 4 4 4
ADD ; 8 4 4
DU2 ; 8 4 8 4 4
ADD ; 12 8 4 4
DUP ; 12 12 8 4 4
ROR ; 4 12 12 8 4
ADD ; 16 12 8 4
And finally, for the “2014” challenge, use the following 14-byte NEX program:
DUP ; 0 0
DUP ; 0 0 0
INC ; 1 0 0
INC ; 2 0 0
SWP ; 0 2 0
CAT ; 20 0
SWP ; 0 20
INC ; 1 20
DUP ; 1 1 20
INC ; 2 1 20
INC ; 3 1 20
INC ; 4 1 20
CAT ; 14 20
CAT ; 2014
