Add missing equation parser features (e.g. loop, megabuf)

[kblaschke]

Latest Milkdrop supports more equation functions and features than projectM. These new functions were introduced in Winamp 5.57 beta, when the devs switched to ns-eel2. Here's a list of currently unsupported functions:

• loop(var, statements; ...)
• while(cond)
• megabuf(n) (can be used as an lvalue!)
• gmegabuf(n) (can be used as an lvalue!)
• freembuf(block)
• memcpy(dst, src, numvals)
• memset(dst, val, numvals)
• exec2(stmt1, stmt2) (Returns the result of the second statement)
• exec3(stmt1, stmt2, smt3) (Returns the result of the third statement)
• invsqrt(f) (Fast inverse square root)

Some reverse engineering might be required to see how these functions work, as there's no end-user documentation.
Also, the megabufs are always global and do not follow the inheritance pattern of q vars. Some presets take advantage of this and use the megabuf to pass data between different equations. It might be hard to find such presets, but if there are some, it's quite important that projectM's order of rendering/calculating each part of a preset follows the exact same order as in Milkdrop.

[kblaschke]

Reading through the code, another hidden, undocumented feature met my eyes. The ns-eel2 library, introduced in one of the last Winamp releases, supports a few "preprocessor macros" that allow using a few math constants and hex values:

• $Xn converts a hexadecimal number into an integer, e.g. $XA000 will be replaced with 40960
• $PI is replaced with a float Pi constant, 3.141592653589793
• $E is replaced with e, 2.71828183
• $PHI is replaced with phi (the "golden cut number"), 1.61803399

I could not find any presets using these constants, probably because they're not documented anywhere and nobody bothered to read through the equation compiler code.

Also undocumented is the use of line comments starting with two backslashes \\ and multi-line comments using /* ... */.

Last but not least, projectM's equation parser can only parse one equation/statement per line, so if there are two or more statements separated by ;, only the first is parsed, the rest ignored, which will break a huge number of presets.

[kblaschke]

I've started with a parser rewrite, as the existing code is more complex than need be and really hard to fix as there's so much duplicated code.

My working branch can be found here for anyone interested in the progress:

https://github.com/kblaschke/projectm/tree/rewrite-preset-parser

[labkey-matthewb]

Nice. I am not a big fan of the current parser either. I actually started a branch too, if I recall the "flexibilty" of multiple expressions per line, plus expressions that continue across lines. Well it was a mess. https://github.com/mbellew/projectm/commits/qiparser

[revmischa]

Oh sweeeet! Want to open a draft PR?

Would be great to keep the JIT option for evaluating the expressions after parsing. That was by far the biggest bottleneck in terms of CPU. Or even better evaluate them in the GPU if such a thing is possible.

[labkey-matthewb]

I think evaluating expressions in the GPU would be a big lift. However, the pixel computations (PresetFrameIO.cpp) is a good candidate for moving to the GPU!

[kblaschke]

Should be doable in compute shaders using textures or storage buffer objects for the data. Yet I'd see this as a whole new feature, and it should be optional as not every device will have compute shader support. But if that works, it'll be really fast and leave the CPU with almost no load, while modern desktop GPUs should handle this with ease.

[kblaschke]

I actually started a branch too, if I recall the "flexibilty" of multiple expressions per line, plus expressions that continue across lines. Well it was a mess.

Oh yes, the whole parsing logic is messy, copied many times over and always expecting a variable plus = on the left side, which prevents using while(), loop() and [g]megabuf(index). With all the other small issues and given the line-by-line file parsing, it'd be almost impossible to refactor this code into something usable.

My new approach is quite similar to Milkdrop's, first reading all lines into a map and providing three functions to extract floats, ints and code blocks using the prefix. Code will already be stripped of comments when it comes out of that, and is a single string that can be parsed right away.

The code parser will also work very differently, but also similar to Milkdrop's ns-eel2 code:

• Strip all unnecessary stuff like remaining comments, newlines and spaces from the code.
• Preprocess the code and replace some constructs (e.g. ternary operators, assignment operators like =, += and [] operators for accessing megabuf data) with internal functions.
• Lex the remaining code, which will only have a few operators in it besides function calls.
• Build the call tree and ready it for execution.

I might write a technical article on how Milkdrop's code processing works. Sadly, we probably never will achieve the same speed as projectM needs to be portable and Milkdrop uses hand-written assembly code for most of the functions, glued together as a single block of instructions. This eliminates all the stack handling overhead and expensive VFT lookups, which projectM needs to do to traverse the expression tree.

LLVM's JIT is probably equally fast as Milkdrop's EEL if used properly, but it's a huge dependency in terms of size. We could try other JIT compilers, e.g. LuaJit, and see if these may perform well enough while adding less overhead.

[kblaschke]

Current plan is to use GNU Bison for parsing & lexing. NullSoft also used Bison to generate their parser in Milkdrop's EvalLib/ns-eel2, but the latest source code releases didn't contain the grammar input file. Luckily, an early Milkdrop source release still shipped with the cal.y file, so I can use this as a great starting point to generate the necessary code in projectM's new expression parser.

Just for building projectM, Bison won't be required as a dependency. Only if the expression parser or the grammar file is changed, Bison will be required to regenerate the parser code. CMake will simply check for Bison and add/run the appropriate build target if it's available.

[kblaschke]

I've started implementing the new expression compiler, currently as a playground project, which I'll later clean up and make it production-ready. With around 250 lines of Flex and Bison grammar, I've already created a working parser for the whole set of supported Milkdrop/ns-eel2 features, including comment exclusion and undocumented features like numeric constants and the gmem[index] and indexval[offset] megabuf accessors, without requiring any preprocessing.

Next up is implementing all the math and control functions and assemble them into an executable data structure, which is luckily quite straightforward.

I'll write everything in pure C for maximum speed and compatibility as a separate library. The code will be put under the liberal MIT license to make it useful in other, even closed-source and commercial projects.

If anyone is interested in the code, I've pushed it to GitHub:
https://github.com/kblaschke/projectm-eel

It probably won't compile most of the time as I'm pushing it in any state I leave it at the end of the day. You'll need Bison 3.8 and Flex 2.6 to generate the scanner and parser code.

[kblaschke]

Implementation is almost done, except for the memset and memcpy functions. The expression compiler ended up having a very similar interface as the ns-eel2 library, so I've written a small header file that wraps the projectM parser API inside the original ns-eel2 functions. Compiling it into Kodi's Milkdrop2 plug-in was actually way easier than integrating it in projectM, and there are no noticeable differences - same speed, same visuals.

Will now write test cases for all the small details like operator precedence, edge cases and possible errors like "integer division by zero" crashes.