WinAli - Virtual CPU for understanding assembly language

8

1

WinAli is a model assembler for Windows. It emulates a real CPU and is meant to help students learning and understanding the Assembly language.

German Wikipedia article: http://de.wikipedia.org/wiki/WinAli (there is no english article at the moment)

In case you want to test your produced output: Link to Google Drive (the program itself is in German but is easy to use even if you don't understand German)

Some information about WinAli (data and syntax)

Data types:

The only data type in WinAli is a 2 byte long "Integer" which is in fact a Smallint or short. So you don't have to take care of correct types. This is also rounded when dividing.

Variables and constants:

Variables are defined like this after the commands:

name DS F
  • name is obviously the name of the variable
  • DS is the keyword for a new variable
  • F defines the length of the variable in bits; this is zero-based and hexadecimal so F = 16 bits

Constants are very similar:

name DC value
  • name is simply the name of the constant
  • DC is the keyword for a new constant
  • value is the value assigned to that constant e.g. two DC '2'
  • You don't need to specify constants at the end of the code. You can also write them inline with the LDA (load) operation e.g. LDA 0,'2'. This loads "2" into register 0 (the accumulator).
Syntax:

The code is aligned into 4 columns which are separated by a space or tab:

label command params comment
  • label is used for the b label command (goto label) and is often skipped.
  • command one of the commands listed below.
  • params one or two parameters with at least one register and if needed another register, variable, stack or address; these parameters are separated by a comma (,).
  • comments (optional) a comment prefixed with ; or * until the end of the line.

Small code reference:

There are more commands but for this challenge you only need those:

  • INI A Stores the next user input into variable A
  • OUTI A Outputs the value the variable A is holding. You can't use a register here for some reason.
  • LDA 0,A Loads the value of A into register 0
  • STA 0,A Stores the value of register 0 into the variable A
  • ADD 0,A Adds the value of A to the value of register 0
  • SUB 0,A Multiplies the value of A with the value of register 0
  • DIV 0,A Divides the value of A by the value of register 0
  • EOJ Defines the end of the job i.e. executable code. Variable and constant declarations begin after this mark.

Not explicitly needed for this challenge:

  • program START 0 Sets the first address to be executed to 0 i.e. the next line (program is just the name of the program but is needed for the compiler)
  • END program Ends the program i.e. stop executing, even if other operations would follow

Your challenge!

Write a program or script that takes a mathematical expression with constant numbers and variables and outputs the WinAli code that takes all variables as input and outputs the result of that expression.

  • You don't need to output the START and END commands
  • Even though there are 16 registers defined in WinAli we only use register 0, which is the accumulator for all calculations
  • You can't use two variables as parameters of a command. You have to save all your results into the accumulator (register 0)
  • The input is always on the form of either x:=(a+b)/c or simply (a+b)/c, you decide
  • You only need to take care of + - * / (ADD, SUB, MUL, DIV), so no complex calculations like roots, squares or even sinus
  • Tip: Try to first extract simple expressions with only 2 arguments e.g. a:=a+b then x:=a/c
  • Tip: Your program is allowed to use additional (auxiliary) variables if you can't overwrite variables that are not used later in your code. Define them as h1 DS F.
  • Tip: Empty lines are useless. Try to avoid them. (You really don't need them)

Example:

Mathematical expression:
 x := (a+b)*c

Expected output (empty lines are for easier reading):
    INI a
    INI b
    INI c

    LDA 0,a
    ADD 0,b
    MUL 0,c
    STA 0,a

    OUTI a
    EOJ
a   DS F
b   DS F
c   DS F

Scoring:

Your score is defined by the length of your code + the length of the output of the following expressions:

x:=a+b+c*c/d

x:=(a+b)/c-d

x:=a-b*c-d/e

x:=2*a-b*c+d
  • -10% if your code can handle unary minus in expressions.

In case of a tie, the answer that produces the shortest working WinAli code wins.

The solutions may not be hardcoded in any way. I will validate each answer with additional expressions to make sure your answer is correct.

GiantTree

Posted 2014-11-05T18:10:05.840

Reputation: 885

What exactly is a mathematical expression? For example are negative constants allowed? Unary minus? Variable names longer than one letter? – nutki – 2014-11-06T19:15:02.537

Do the input directives (INI x) need to follow any specific order? – nutki – 2014-11-06T19:16:43.507

@nutki a mathematical expression is meant like a simple x=a+b so no solving of complex equations, negative constants are allowed, variable names can be more than one letter (ab is not a*b), INI x can be put where ever you like there is no specific order needed as it stores the next input into the give variable but it would be nice if they follow the order a-z instead of being random – GiantTree – 2014-11-06T20:00:15.773

@nutki by unary minus you mean things like MUL 0,-a? this is not possible because there are no negative addresses (a is just a pointer to a value), but you can subtract the value from 0 to get the negative representation (SUB 0,a) and then work with this negative value; you may even be able to store this in the original variable. – GiantTree – 2014-11-06T20:06:12.650

I meant unary minus in the input expression so for example x:=-a*b or x:=a/-(b+c). Since the input order is not specified I guess we have to use the same variables names in the WinAli code, is that the case? With those restrictions are there identifiers that are never on the input? For example can h1 be an input variable name? – nutki – 2014-11-06T21:41:49.617

@nutki for the simplicity of this challenge you don't need to take care of unary minus (in your first example you only have to add a 0 in front of that - though), input variable names are supposed to be one character only so h1 is no input variable. To make the resulting WinAli code easier to understand, variable names should persist so the input of a is the same in both the expression and the code (a in x:=a*b is the same as in INI a). If your program can handle unary minus than I allow -10% to your score. – GiantTree – 2014-11-06T22:49:53.933

Since output size counts to the score is it OK to remove the initial tabs? – nutki – 2014-11-07T09:35:40.593

@nutki because the tabs are necessary for the code to work it counts towards the score. The first tabs separate the jump markers from the command. – GiantTree – 2014-11-07T13:32:47.503

One more question: are negative constants allowed? I assumed so and spend significant characters on supporting likes of -5*a, a+-10 etc. But I don't see any indication in the description. – nutki – 2014-11-07T19:57:16.373

@nutki sure, all values between -32768 and 32767 (16bit) can be stored in a constant. Not supporting those should invalidate an answer. – GiantTree – 2014-11-07T20:06:48.380

Answers

4

Perl 5: 948, 355 code + 593 output

After some golfing. Previous shorter version did not properly parse (a+b)-4*c.

%m=split'\b','-SUB+ADD/DIV*MUL<LDA>STA';$i='(\w+|(?<!\w|\))-\d+)';
$_=<>;@x{@y=/([a-z]\w*)/gi}=@y;print"\tINI $_
"for@x=keys%x;
$f=$_,$x.="<$&>".($g=(grep$f!~$_,a..zz)[0]),$x{$g}=s/@/$g/
while s|\($i\)|$1|g,s|$i[*/]$i|@|||s|$i[+-]$i|@|;$_="$x
\tOUTI $_\tEOJ
";s/>$i<\1//g;s!(^|\b)[-+/*<>]!\n\t$m{$&} 0,!g;
s!-?\d+$!'$&'!mg;print;print"$_\tDS F
"for keys%x

Example use:

$perl winali.pl <<<"2*a-b*c+d"
    INI b
    INI a
    INI d
    INI c

    LDA 0,'2'
    MUL 0,a
    STA 0,a
    LDA 0,b
    MUL 0,c
    STA 0,b
    LDA 0,a
    SUB 0,b
    ADD 0,d
    STA 0,b
    OUTI b
    EOJ
b   DS F
a   DS F
d   DS F
c   DS F

nutki

Posted 2014-11-05T18:10:05.840

Reputation: 3 634

Verified. Would be nice if the input is sorted alphabetically. Just one tip: empty lines are ignored so they may reduce your output length a little bit – GiantTree – 2014-11-07T19:04:07.300

Some optimizations you could do: remove the trailing new line – GiantTree – 2014-11-07T19:12:53.373

With the above optimizations your output will be 585 bytes long (8 bytes less) – GiantTree – 2014-11-07T19:13:37.010

Trailing newline can be removed at no code cost, but to remove an empty line after INI would probably cost more than 4 characters of code. – nutki – 2014-11-07T19:59:09.010

oh, then just remove the trailing newline, it's not needed and will save you 4 bytes :) – GiantTree – 2014-11-07T20:02:58.173