Converting Arithmetic Expressions to Assembly

[UniverseIsASimulation]

Hey, guys!
New here. I've just made a simple web-app that attempts to convert arithmetic expressions to i486-compatible assembly:
Arithmetic expression to assembly converter
I've tried to test it (using Flat Assembler), and to me it seems like it produces correct results. However, I am not a professional programmer, so I would like to hear from some experts.

[jj2007]

Very cute :t What's behind, shunting yard?

[Mikl__]

This is a useful thing! Please write something else for converting integer arithmetic expressions... (Comments in Slovenian?)

[UniverseIsASimulation]

What's behind, shunting yard?

There is no codebehind. It's just a few recursive algorithms implemented in 600 lines of JavaScript, you can see all by looking at the source code. Shunting Yard would be faster, but it would also be harder to implement. The difference isn't really visible on arithmetic expressions, which are always relatively short.

This is a useful thing!

Yes. And C compilers are even more useful, for the same reason.

Please write something else for converting integer arithmetic expressions

That wouldn't be easy. The algorithms I've made assume the existence of a stack (like the FPU-stack). I could make a stack of the general-purpose registers (eax,ebx,ecx,edx,edi,esi...), but that would be extremely inefficient. I could make a stack in RAM, but then it would be much like using a C compiler (it would be very hard to reassemble a program compiled for MacOS to run in DOS).

Comments in Slovenian?

Close enough. They are in Croatian. Google Translate usually does a good job translating from Croatian to English.

Anyway, can you confirm that my web-app produces the correct code? Again, I've only tested it a little in Flat Assembler.

[hutch--]

Sounds like an interesting tool, I would not worry about what its written in as it produces code, not runs it. I note you mentioned .486 compatible instructions and if you are catering for very old OS versions and hardware it would make sense but if you are addressing anything later in either 32 or 64 bit software, there may be better choices in instructions.

[hutch--]

Sad to say the link is broken.

[UniverseIsASimulation]

It's not. My website sleeps from 22 to 23 PM UTC+1. If I want to make it accessible 24h/day, I'd have to pay for the hosting, and now it's free.

[hutch--]

How big is the download ? If it is under 512k, post it here.

[jj2007]

It's huge, see attachment 8)

[UniverseIsASimulation]

It's a JavaScript file (around 600 lines) intended to be embedded on a web-page (like one I linked to). I am not sure how I could post it here.
I think the webpage is up right now and that it will be up for the next 2 hours. Then it will be down for an hour, and then it will be up for 23 hours.
Maybe you can download it and post it here, if you think that's a good idea.

[jj2007]

Download the zip file I attached above, and just double-click on the only file in the archive. Astonishingly, it produces fine assembler code. I have not tested it thoroughly, but this is obviously a fine project, compliments.

[LiaoMi]

Hello everybody,

I decided to collect here some alternative solutions that we can use in our projects, some of them can generate high-performance code  :P

C++ Mathematical Expression Library - uses mpir and mpfr

Code Select Expand

The ExprTk library has the following capabilities:
Mathematical operators (+, -, *, /, %, ^)
Functions (min, max, avg, sum, abs, ceil, floor, round, roundn, exp, log, log10, logn, pow, root, sqrt, clamp, inrange, swap)
Trigonometry (sin, cos, tan, acos, asin, atan, atan2, cosh, cot, csc, sec, sinh, tanh, d2r, r2d, d2g, g2d, hyp)
Equalities & Inequalities (=, ==, <>, !=, <, <=, >, >=)
Assignment (:=, +=, -=, *=, /=, %=)
Logical operators (and, nand, nor, not, or, xor, xnor, mand, mor)
Control structures (if-then-else, ternary conditional, switch case, return-statement)
Loop structures (while loop, for loop, repeat until loop, break, continue)
Optimization of expressions (constant folding, strength reduction, operator coupling, special functions and dead code elimination)
String operations (equalities, inequalities, logical operators, concatenation and sub-ranges)
Expression local variables, vectors and strings
User defined variables, vectors, strings, constants and function support
Multivariate function composition
Multiple sequence point and sub expression support
Numeric integration and differentiation
Vector Processing: BLAS-L1 (axpy, axpby, axpb), all/any-true/false, count, rotate-left/right, shift-left/right, sort, nth_element, iota, sum, kahan-sum, dot-product, copy
File-IO package (routines include: open, close, read, write, getline, support for binary and text modes)
Support for various numeric types (float, double, long double, MPFR/GMP)
Single header implementation, no building required. No external dependencies.
Completely portable (Compiled and executed upon: x86 x86-64, ARMv7/8, POWER6/7 and AVR32)

Example Expressions

sqrt(1 - (x^2))
clamp(-1,sin(2 * pi * x) + cos(y / 2 * pi),+1)
sin(2 * x)
if (((x + 2) == 3) and ((y + 5) <= 9),1 + w, 2 / z)
inrange(-2,m,+2) == (({-2 <= m} and [m <= +2]) ? 1 : 0)
({1 / 1} * [1 / 2] + (1 / 3)) - {1 / 4} ^ [1 / 5] + (1 / 6) -({1 / 7} + [1 / 8]*(1 / 9))
a * exp(2 * t) + c
z := x + sin(2 * pi / y)
2x + 3y + 4z + 5w == 2 * x + 3 * y + 4 * z + 5 * w
3(x + y) / 2 + 1 == 3 * (x + y) / 2 + 1
(x + y)3 + 1 / 4 == (x + y) * 3 + 1 / 4
(x + y)z + 1 / 2 == (x + y) * z + 1 / 2
(sin(x/pi)cos(2y) + 1)==(sin(x / pi) * cos(2 * y) + 1)
while(x <= 100) { x += 1; }
x <= 'abc123' and (y in ('AStr' + 'ing')) or ('1x2y3z' != z)
('REX' + x like '*123*') or ('a123b' ilike y)

http://www.partow.net/programming/exprtk/index.html
https://github.com/ArashPartow/exprtk

Mathematical Expression Parser and JIT Compiler

Code Select Expand

When executed the output of the application would be something like:

[AST-INITIAL]
* [Binary]
  * [Binary]
    - [Unary]
      - [Unary]
        abs [Unary]
          - [Binary]
            * [Binary]
              x
              y
            floor [Unary]
              x
    z
  - [Binary]
    12.900000
    3.000000

[AST-FINAL]
* [Binary]
  * [Binary]
    abs [Unary]
      - [Binary]
        * [Binary]
          x
          y
        floor [Unary]
          x
    z
  9.900000

[ASSEMBLY]
L0:                                 ;                     |                           ..
lea rax, [L2]                       ; 488D05........      | lea pConst, [L2]          ..w
movsd xmm0, [rdx]                   ; F20F1002            | movsd v3, [pVariables]    .r.w
mulsd xmm0, [rdx+8]                 ; F20F594208          | mulsd v3, [pVariables+8]  .r.x
movsd xmm1, [rdx]                   ; F20F100A            | movsd v4, [pVariables]    .r..w
roundsd xmm1, xmm1, 9               ; 660F3A0BC909        | roundsd v4, v4, 9         ....x
subsd xmm0, xmm1                    ; F20F5CC1            | subsd v3, v4              ...xR
xorpd xmm1, xmm1                    ; 660F57C9            | xorpd v5, v5              .... w
subsd xmm1, xmm0                    ; F20F5CC8            | subsd v5, v3              ...r x
maxsd xmm1, xmm0                    ; F20F5FC8            | maxsd v5, v3              ...R x
mulsd xmm1, [rdx+16]                ; F20F594A10          | mulsd v5, [pVariables+16] .R.  x
mulsd xmm1, [rax]                   ; F20F5908            | mulsd v5, [pConst]        . R  x
movsd [rcx], xmm1                   ; F20F1109            | movsd [pResult], v5       R    R
L1:                                 ;                     |
ret                                 ; C3                  |
.align 8
L2:                                 ;                     |
.data CDCCCCCCCCCC2340

RESULT: -1885.514400

https://github.com/kobalicek/mathpresso

muparserx - Math Parser Library
A C++ Library for Parsing Expressions with Strings, Complex Numbers, Vectors, Matrices and more.

Code Select Expand

Overview
Supported data types: double, integer, complex, boolean, string, array
Extensible with custom operators (binary, infix or postfix)
Extensible with custom functions with an arbitrary number of function arguments
Support for an unlimited number of variables and constants
No limit on expression complexity
Reads binary, hexadecimal, complex, integer and string values from expressions and can be extended to read user defined values as well.
Supports a large variety of predefined operators, functions and constants.
Written in standard compliant C++ code with no external dependencies.
Features
By default the parser supports the following mathematical constants:

The eulerian number with: e = 2.718281828459045235360287
Pi with pi = 3.141592653589793238462643
The imaginary unit with: i = sqrt(-1)
Binary and ternary operators
Standard operators: +, -, *, /, ^
Assignment operators: =, +=, -=, *=, /=
Logical operators: and, or, xor, ==, !=, >, <, <=, >=
Bit manipulation: &, |, <<, >>
String concatenation: //
if then else conditionals with lazy evaluation: ?:
Postfix Operators
Unit postfixes (nano, micro, milli, kilo, giga, mega): n, mu, m, k, G, M
Transpose operator: '
Infix Operators
Sign operator and type conversions: -, (float), (int)
Special Operators
Multidimensional index operator: a[1,2]
Ternary if-then-else operator: (a<b) ? c:d
In-place array creation: {1,2,3}
Predefined Functions
Standard functions abs, sin, cos, tan, sinh, cosh, tanh, ln, log, log10, exp, sqrt
Unlimited number of arguments: min, max, sum
String functions: str2dbl, strlen, toupper
Complex functions: real, imag, conj, arg, norm
Array functions: sizeof, eye, ones, zeros

http://beltoforion.de/article.php?a=muparserx&hl=en
https://github.com/beltoforion/muparserx

Blaze is an open-source, high-performance C++ math library for dense and sparse arithmetic. With its state-of-the-art Smart Expression Template implementation Blaze combines the elegance and ease of use of a domain-specific language with HPC-grade performance, making it one of the most intuitive and fastest C++ math libraries available.

The Blaze library offers ...

... high performance through the integration of BLAS libraries and manually tuned HPC math kernels
... vectorization by SSE, SSE2, SSE3, SSSE3, SSE4, AVX, AVX2, AVX-512, FMA, and SVML
... parallel execution by OpenMP, HPX, C++11 threads and Boost threads
... the intuitive and easy to use API of a domain specific language
... unified arithmetic with dense and sparse vectors and matrices
... thoroughly tested matrix and vector arithmetic
... completely portable, high quality C++ source code

A Complex Example
The following example is much more sophisticated. It shows the implementation of the Conjugate Gradient (CG) algorithm (http://en.wikipedia.org/wiki/Conjugate_gradient) by means of the Blaze library:

In this example it is not important to understand the CG algorithm itself, but to see the advantage of the API of the Blaze library. In the Blaze implementation we will use a sparse matrix/dense vector multiplication for a 2D Poisson equation using NxN unknowns. It becomes apparent that the core of the algorithm is very close to the mathematical formulation and therefore has huge advantages in terms of readability and maintainability, while the performance of the code is close to the expected theoretical peak performance:

Code Select Expand

const size_t NN( N*N );

blaze::CompressedMatrix<double,rowMajor> A( NN, NN );
blaze::DynamicVector<double,columnVector> x( NN, 1.0 ), b( NN, 0.0 ), r( NN ), p( NN ), Ap( NN );
double alpha, beta, delta;

// ... Initializing the sparse matrix A

// Performing the CG algorithm
r = b - A * x;
p = r;
delta = (r,r);

for( size_t iteration=0UL; iteration<iterations; ++iteration )
{
   Ap = A * p;
   alpha = delta / (p,Ap);
   x += alpha * p;
   r -= alpha * Ap;
   beta = (r,r);
   if( std::sqrt( beta ) < 1E-8 ) break;
   p = r + ( beta / delta ) * p;
   delta = beta;
}

[UniverseIsASimulation]

Wow, that's great! How did you learn C++? I've been trying to learn C++ for five years, and I am still not able to do anything in it. Good that I finally gave up and found out there are languages that are easier to learn, such as JavaScript. I've only been learning JavaScript for a few months, and I am able to do much more than I was able to after learning C++ for five years.

Anyway, my idea for a relatively large project is to make LLAP, a LISP-like Assembly Preprocessor. Namely, many, if not most of the, assembly-language preprocessors are Turing-complete. However, very few of them provide functions that are actually relevant to low-level programming. I think it would be a good idea to make a preprocessor in which it's easy (as it's in LISP) to do complicated string manipulation at the compile-time, and which also has built-in functions for converting arithmetic expressions to assembly (which can be tedious to do manually).
For instance:

Code Select Expand

(echo (compile (parseArth (tokenizeArth "sqrt(a*a+b*b)"))))
would output something like:

Code Select Expand


finit
fld dword [a]
fld dword [a]
fmulp st1,st0
fld dword [b]
fld dword [b]
fmulp st1,st0
faddp st1,st0
fsqrt
fstp dword [result]

Do you think that's a good idea? Right now, I don't know enough informatics to do it myself, and I don't have much time to learn that because I am already doing bad at school (and we don't even have informatics at school). If you think that's a good idea, I might do it after a few years.

[Biterider]

Hello
Check the <SmplMath> project by qword here in the forum or at SourceForge https://sourceforge.net/projects/smplmath/


Biterider

[jj2007]

If you want to use your code for pre-processing assembly code, you may need a standalone JS compiler. Ever thought of that?