Author Topic: Converting Arithmetic Expressions to Assembly  (Read 4593 times)

UniverseIsASimulation

• Regular Member
• Posts: 19
Converting Arithmetic Expressions to Assembly
« on: February 24, 2018, 06:50:31 AM »
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

• Member
• Posts: 8968
• Assembler is fun ;-)
Re: Converting Arithmetic Expressions to Assembly
« Reply #1 on: February 24, 2018, 07:23:33 AM »
Very cute What's behind, shunting yard?

Mikl__

• Member
• Posts: 725
Re: Converting Arithmetic Expressions to Assembly
« Reply #2 on: February 24, 2018, 09:51:46 AM »
This is a useful thing! Please write something else for converting integer arithmetic expressions... (Comments in Slovenian?)

UniverseIsASimulation

• Regular Member
• Posts: 19
Re: Converting Arithmetic Expressions to Assembly
« Reply #3 on: February 24, 2018, 04:53:48 PM »
Quote
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.
Quote
This is a useful thing!
Yes. And C compilers are even more useful, for the same reason.
Quote
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).
Quote
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--

• Administrator
• Member
• Posts: 6030
• Mnemonic Driven API Grinder
Re: Converting Arithmetic Expressions to Assembly
« Reply #4 on: February 24, 2018, 07:54:58 PM »
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 at movsd dot com
http://www.masm32.com

hutch--

• Administrator
• Member
• Posts: 6030
• Mnemonic Driven API Grinder
Re: Converting Arithmetic Expressions to Assembly
« Reply #5 on: February 25, 2018, 06:13:30 PM »
Sad to say the link is broken.
hutch at movsd dot com
http://www.masm32.com

UniverseIsASimulation

• Regular Member
• Posts: 19
Re: Converting Arithmetic Expressions to Assembly
« Reply #6 on: February 25, 2018, 09:48:30 PM »
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--

• Administrator
• Member
• Posts: 6030
• Mnemonic Driven API Grinder
Re: Converting Arithmetic Expressions to Assembly
« Reply #7 on: February 26, 2018, 03:24:59 AM »
How big is the download ? If it is under 512k, post it here.
hutch at movsd dot com
http://www.masm32.com

jj2007

• Member
• Posts: 8968
• Assembler is fun ;-)
Re: Converting Arithmetic Expressions to Assembly
« Reply #8 on: February 26, 2018, 04:40:25 AM »
It's huge, see attachment

UniverseIsASimulation

• Regular Member
• Posts: 19
Re: Converting Arithmetic Expressions to Assembly
« Reply #9 on: February 26, 2018, 06:16:52 AM »
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

• Member
• Posts: 8968
• Assembler is fun ;-)
Re: Converting Arithmetic Expressions to Assembly
« Reply #10 on: February 26, 2018, 08:16:59 AM »
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

• Member
• Posts: 333
Re: Converting Arithmetic Expressions to Assembly
« Reply #11 on: February 26, 2018, 08:41:17 AM »
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

C++ Mathematical Expression Library - uses mpir and mpfr

Code: [Select]
`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 stringsUser defined variables, vectors, strings, constants and function supportMultivariate function compositionMultiple sequence point and sub expression supportNumeric integration and differentiationVector 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, copyFile-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

Quote
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]
`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]          ..wmovsd xmm0, [rdx]                   ; F20F1002            | movsd v3, [pVariables]    .r.wmulsd xmm0, [rdx+8]                 ; F20F594208          | mulsd v3, [pVariables+8]  .r.xmovsd xmm1, [rdx]                   ; F20F100A            | movsd v4, [pVariables]    .r..wroundsd xmm1, xmm1, 9               ; 660F3A0BC909        | roundsd v4, v4, 9         ....xsubsd xmm0, xmm1                    ; F20F5CC1            | subsd v3, v4              ...xRxorpd xmm1, xmm1                    ; 660F57C9            | xorpd v5, v5              .... wsubsd xmm1, xmm0                    ; F20F5CC8            | subsd v5, v3              ...r xmaxsd xmm1, xmm0                    ; F20F5FC8            | maxsd v5, v3              ...R xmulsd xmm1, [rdx+16]                ; F20F594A10          | mulsd v5, [pVariables+16] .R.  xmulsd xmm1, [rax]                   ; F20F5908            | mulsd v5, [pConst]        . R  xmovsd [rcx], xmm1                   ; F20F1109            | movsd [pResult], v5       R    RL1:                                 ;                     |ret                                 ; C3                  |.align 8L2:                                 ;                     |.data CDCCCCCCCCCC2340RESULT: -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]
`OverviewSupported data types: double, integer, complex, boolean, string, arrayExtensible with custom operators (binary, infix or postfix)Extensible with custom functions with an arbitrary number of function argumentsSupport for an unlimited number of variables and constantsNo limit on expression complexityReads 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.FeaturesBy default the parser supports the following mathematical constants:The eulerian number with: e = 2.718281828459045235360287Pi with pi = 3.141592653589793238462643The imaginary unit with: i = sqrt(-1)Binary and ternary operatorsStandard operators: +, -, *, /, ^Assignment operators: =, +=, -=, *=, /=Logical operators: and, or, xor, ==, !=, >, <, <=, >=Bit manipulation: &, |, <<, >>String concatenation: //if then else conditionals with lazy evaluation: ?:Postfix OperatorsUnit postfixes (nano, micro, milli, kilo, giga, mega): n, mu, m, k, G, MTranspose operator: 'Infix OperatorsSign operator and type conversions: -, (float), (int)Special OperatorsMultidimensional index operator: a[1,2]Ternary if-then-else operator: (a<b) ? c:dIn-place array creation: {1,2,3}Predefined FunctionsStandard functions abs, sin, cos, tan, sinh, cosh, tanh, ln, log, log10, exp, sqrtUnlimited number of arguments: min, max, sumString functions: str2dbl, strlen, toupperComplex functions: real, imag, conj, arg, normArray 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]
`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 algorithmr = 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

• Regular Member
• Posts: 19
Re: Converting Arithmetic Expressions to Assembly
« Reply #12 on: February 27, 2018, 06:45:59 AM »
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]
`(echo (compile (parseArth (tokenizeArth "sqrt(a*a+b*b)"))))`would output something like:
Code: [Select]
`finitfld dword [a]fld dword [a]fmulp st1,st0fld dword [b]fld dword [b]fmulp st1,st0faddp st1,st0fsqrtfstp 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

• Member
• Posts: 259
• ObjAsm32 - ObjAsm64
Re: Converting Arithmetic Expressions to Assembly
« Reply #13 on: February 27, 2018, 07:33:58 AM »
Hello
Check the <SmplMath> project by qword here in the forum or at SourceForge https://sourceforge.net/projects/smplmath/

Biterider

jj2007

• Member
• Posts: 8968
• Assembler is fun ;-)
Re: Converting Arithmetic Expressions to Assembly
« Reply #14 on: February 27, 2018, 07:40:15 AM »
If you want to use your code for pre-processing assembly code, you may need a standalone JS compiler. Ever thought of that?