Hello,
the last days I've worked on an small, recursive mathematical expression evaluator. The evaluation is done in double precision using SSE2 and - if needed - the FPU. Variables and constants (called symbols) can be passed to the evaluator using linked lists. For expressions the usual operator precedence applies: e.g. -2^2+2*3 == -4+6
Currently the functionality is split in two functions (and modules), the core-parser/evaluator evaluate_expressio(...) and an extended interpreter evaluate_script(...) that adds some kind of 'scripting' capacities.
The function evaluate_expressio() does not depend on any library. evaluate_script() use GlobalAlloc/Free(). Both functions are TCHAR aware, but the expression must contain only ASCII characters.
It might be interesting for you that the parser use SSE2 for testing characters (pcmpeqb\w+pmovmskb) - the idea is to break long dependency chains that comes up through several combined conditions: e.g.:
.if !eax || eax == ';' || eax == ',' ...
I've also found that the instruction PSADBW (Packed Sum of Absolute Differences of Bytes) can be used to get a look up value:
; xmm1 -> each byte contains the current character (--> PUNPCKxxx)
; xmm2 = zero
pcmpeqb xmm1,char_mask ; test for match
pand xmm1,lut_msk ; apply lookup value (should be greater than zero)
psadbw xmm1,xmm2 ; possible LUT value is in WORD xmm1[0] or xmm1[4]
movdqa xmm2,xmm1
psrldq xmm1,8
por xmm2,xmm1 ; LUT value in low WORD of xmm0
movd eax,xmm1
(the parser use the above method to test for operators and get their precedence)
In the attachment all needed files and some examples.
For a detailed description of the functions evaluate_expressio() and evaluate_script() , see the include files
mee.inc and mee_extended.inc.
feed back is welcome!
regards, qWord
BTW: jWasm or ML v8+ v6.15+ is needed for building.
I don't claim my maths is up to scratch but all 3 examples seem to work OK. The speed of the complex formula in the GUI version is fast. :t
Quote from: hutch-- on July 02, 2013, 01:19:40 AMThe speed of the complex formula in the GUI version is fast. :t
It could be much faster. I forgot to mention that the algorithm does not set up an abstract syntax tree or similar. Because of that, loop bodies are parsed for each iteration, which of course is suboptimal. However, for single expressions it is OK :biggrin:
Not "yet another parser" - this looks like a full-fledged interpreter :t
define i, n=10,
x=-2*pi, step=4*pi/(n-1),
y1[n+1], y2[n+1], y3[n+1];
while (i<=n)
(
y1[i] = sin(x),
y2[i] = e^-abs(x)*sin(2*pi*x),
y3[i] = limit(tan(0.7*(x-pi)),-10,10),
x = x + step,
i = i + 1
);
define y4[n=6],
factorial(x)
(
if(x>0)(
x*factorial(x-1)
) else (
1
)
);
for(i=0,i<n,i=i+1)
(
y4[i]=(factorial(i))
);
P.S.: It needs JWasm to build, ML 6.15 chokes.
Quote from: jj2007 on July 02, 2013, 03:04:56 AMML 6.15 chokes.
...also, IIRC this version also produce wrong opcodes for some SSE2 instructions.
Hi qWord,
rock solid work. Thank you. :t
Gunther