Developer's Guide

XaoS is free software under the GPL. One of the most significant rights its license grants to you is the right to freely get, study and improve its source code. XaoS has open development model. Source is available on GitHub and pull requests are welcome and encouraged. This guide is intended to give prospective developers a good orientation for hacking on XaoS's codebase.

Supported Platforms

XaoS is built on the Qt platform. XaoS has thus far been tested with the following versions:

Qt 5.12.2-1 on Ubuntu 19.04
Qt 5.9.5 on Ubuntu 18.04.2
Qt 5.12.6 on Windows 10
Qt 5.12.6 on macOS Catalina
Qt 5.7.1 on Raspbian (April 2019)

At the moment the following versions do not work:

Qt 5.5.1 on Ubuntu 16.04

Build Instructions

XaoS can be built using either qmake or the Qt Creator IDE from the XaoS.pro project file in the main directory. Further build instructions will be updated before the final 4.0 release.

Prerequisites

Ubuntu and Debian

Install the following packages:

build-essential
qttools5-dev-tools
qt5-default

Windows

Download the Qt installer from https://www.qt.io/download-qt-installer

Install the following options:

Default items
Qt 5.12.6 for MINGW 7.3.0 32-bit and 64-bit
MINGW 7.3.0 32-bit and 64-bit (under Developer and Design Tools)
Qt Installer Framework 3.2

macOS

Install Xcode according to these instructions: https://doc.qt.io/qt-5/macos.html

Download the Qt installer from https://www.qt.io/download-qt-installer

Install the following options:

Default items
Qt 5.12.6 for macOS

Building from the Command Line

After cloning the repository, issue the commands qmake && make in the root folder of XaoS.
Change directory to bin and start the executable ./xaos.

Building from Qt Creator

Start Qt Creator.
Start a new project by importing the repository https://github.com/xaos-project/XaoS with Git Clone.
Select Desktop Qt 5.14.0 MinGW 32-bit at Build & Run.
Click on the green Run icon on the left grey panel.

Historical Perspective

XaoS is quite an old codebase, originating in 1996. It was originally designed for extreme portability, supporting Linux, DOS, Windows, MacOS, and even more obscure operating systems like OS/2, BeOS, and Plan 9. The lower level code was encapsulated in a modular driver system that allowed a minimal amount of code to be written in order to port it to a new operating system.

When I (J.B. Langston) initially got involved with the project in 2006, I found this architecture quite elegant, and it allowed me to quickly write several new drivers for Mac OS X, GTK+ and Qt, with minimal effort. The downside is that XaoS suffered from the lowest common denominator, making it difficult to add features that aren't supported by every platform that it targets. This means it hasn't kept up with modern expectations and the UI is a bit weird. Also, the code was riddled with #ifdefs, which made it hard to understand and modify.

Thus, when I reengaged with the project in 2019, Zoltan and I made the decision to abandon the goal of extreme portability in favor of standardizing on Qt, which will allow us to write a modern GUI targeting the three major desktop platforms (Linux, Mac, and Windows) with less code and less effort. Qt also opens the door to mobile platforms, although App Stores present licensing challenges with the GPL.

Since making this decision, I have undertaken a major refactoring effort. First, I deleted the old drivers for everything but Qt. Next, I merged the Qt driver code with the generic UI code, slowly moving more functionality into Qt's purview. I have replaced external dependencies (libpng and gettext) with Qt equivalents and added modern text rendering which supports TrueType fonts and non-Latin scripts. I have removed lots of old cross-platform code that is no longer needed when POSIX compatibility is much more universal (even on Windows), as well as features that are no longer necessary, such as the "Ugly UI" and dithering support for non-truecolor visuals. I have changed all the existing C sources to C++ and fixed any compilation errors that ensued.

These changes have reduced the overall lines of code in XaoS from 86,000 at its peak to 29,000 today, while still retaining all the important functionality. The libraries described below remain in XaoS in mostly unmodified form, but some of them are redundant with functionality provided by Qt or the C++ standard library, so even more code could be removed in the future. Much of the documentation below comes from Jan Hubicka, the original author of XaoS. Sections of the original document which are no longer applicable since the Qt unification have been removed. Comments regarding each library's future viability have been to the end of each section under Future Plans.

Thus far, these changes haven't resulted in a lot of user-visible features, but I believe they are laying the groundwork to much more productive development of features going forward.

Lay of the Land

XaoS source code is laid out in the directory structures described here.

src: The source code for XaoS, further subdivided as follows:
- include: header files used throughout the XaoS project.
- engine: source for the core zooming engine, fractal formulae, and filters used by XaoS to render fractal images.
- util: various utility libraries used by other code within XaoS.
- sffe: the SegFault Formula Evaluator used to generate fractal images from user-defined formulae.
- ui-hlp: files that provide file processing and animation functionality on top of the core XaoS rendering engine. Also includes the Function Registry which will eventually be more closely integrated with the user interface.
- ui: Qt-specific user interface, including the main entry point ot XaoS.
i18n: Internationalization files for Qt Linguist.
catalogs: Language specific message catalogs for tutorials.
tutorials: xaf scripts used to present tutorials in the help menu.
examples: Example XaoS parameters submitted by users and developers. These can be accessed from the Load Random Example item on the File menu.
installer: Qt Installer Framework files used to create the Windows Installer for XaoS.
tools: various scripts useful for development or deployment on supported platforms.
xdg: Files used to create XaoS desktop environment shortcuts on Linux distributions.
doc: Documentation files installed with XaoS. Mostly outdated in favor of online documentation.

The following sections provide insight into each major area of the XaoS code.

Algorithms

XaoS implements several novel algorithms which are described here.

The main idea behind XaoS is that it is not necessary to calculate the whole image in every frame; most pixels were already calculated by the previous frames. You usually don’t have exactly the pixels you want, but all within a range lower than a step between pixels are acceptable. That is why the image flickers a bit and why points do not blink randomly as in recalculated animations.

This document describes some of the most important algorithms in XaoS:

Saving Previous Pixels
Approximation Algorithm
Moving Pixels to New Positions
Calculating New Pixels
Symmetry
Calculation of Mandelbrot Set
Dynamic Resolution
Autopilot

Saving Previous Pixels

Ideally, all recalculated points should be saved and used for building successive frames. I could not figure out a practical way to implement this. To save all frames for half an hour would require 24 Mb of memory, and searching the saved frames would be more computationally expensive than recalculating an entirely new frame.

One way was later used by the program Frang. It remembers all pixels as triplets of (x,y,value), and when it builds a new image, it draws all the pixels that it remembers to that image and then browses the image and fills it with new pixels. (Possibly an RLE encoding should be used for calculated pixels to conserve memory.) Frang actually uses an algorithm that takes away pixels from the screen, so it behaves in exactly the same way as the algorithm described here. On the other hand, this method seems to require much more memory than XaoS’ algorithm, and drawing pixels/browsing the image costs quite a lot, so the algorithm described here seems to be faster, since it never requires examining the whole image, and the new image is constructed using block move operations.

For this reason, only the last generated frame is used as a reference. This way the memory requirements are proportional to xsize * ysize. It can be shown that this method is only about 2–5% slower during zooming. (Of course unzooming back to once browsed areas is much slower.)

Because only the previous frame is used, another optimization can be performed: The imaginary and real parts of the calculated image are not precise, since they are the result of successive iterations of the algorithm. In order to prevent errors from being propagated to the following frames, their exact coordinates need to be known. Fortunately, it isn’t necessary to save their values since it is known that all real components in a row and all imaginary components in a column are equal. Thus, the only things that must be saved are the real components for every row and the imaginary components for every column.

This allows for a substantial speed-up in approximation because the calculation requires less data. Of course, some rows and columns fall out of the threshold and new ones need to be calculated to fill in the gaps in the frame.

Obviously, much less work is done than in a brute-force calculation: there are only xsize + ysize calculations instead of xsize * ysize. So the main loop in XaoS looks like this:

Make approximations for rows
Make approximations for columns
Move old pixels to their new positions
Calculate pixels for which there is no good approximation for their row
Calculate pixels for which there is no good approximation for their column, but there is one for their row

Approximation Algorithm

Introduction to problem

You can see that the approximation algorithm is central to the implementation of XaoS. If a guess is incorrect the image will look strange, boundaries will not be smooth and the zoom will flicker. On the other hand, if it adds more new rows or columns than required, zooming will become much slower. Also, if doubling should happen (i.e., using an old row or column more than once) the resolution will lower and the image will look jagged. It is important to keep the increasing imaginary and real components in the correct order. If a row and column of complex coordinates follows one with higher coordinate values, an improved approximation can be attained by swapping their values.

The algorithm needs to be relatively fast. It is only used for xsize + ysize values, but if its speed is proportional to O(n^2), it can be slower than a whole recalculation of the image. Speeds of O(n) or O(n * log(n)) are acceptable.

Some simple algorithms to solve it

Initially, a very simple algorithm was used:

Find the old row/column nearest the row/column that needs to be regenerated. If the difference between them is less than one step (step = (end - beginning) / resolution) then use it. Otherwise, recalculate a new one.

Finding the nearest row/column pair is very simple since it is always greater than or equal to the pair needing to be generated.

Surprisingly, this simple algorithm has almost all the problems described above. Doubling was fixed by lowering the limit to step / 2. This caused a considerable slowdown so the limit was returned to step. Instead, the algorithm was changed to search for only row/column pairs that are greater than the previous frame’s row/column pairs. This is the algorithm that was used in version 1.0.

This algorithm still added too many new rows and columns, and did not generate smooth boundaries. For version 1.1 a heuristic was added that preferred approximating rows/columns with lower values. This way it did not occupy possible rows/columns for the next approximation. The result was a speedup by a magnitude of four. In versions 1.1 to 2.0 many improvements were made to the heuristic to give it added performance. The following example tries to explain how complicated the problem is (O is the old coordinates and X is the values to be approximated):

        X1        X2        X3        X4        X5        X6        X7
O1 O2                    O3 O4 O5                   O6 O7 O8

The normal algorithm will aproximate X1 by O2, X3 by O4 but nothing more. For the algorithm with threshold step instead of step / 2:

  O2 to X1
  O3 to X2
  O4 to X3
  O5 to X4
  O6 to X5
  O8 to X6

But this will fail with X7. The second algorithm which relies on lower values will do the following:

  O1 to X1
  O3 to X2
  O4 to X3
  O5 to X4
  O6 to X5
  O7 to X6
  O8 to X7

O1 to X1 is wrong. And there is many and many other situations that may occur. But you may see that the normal algorithm will calculate 4 new rows/columns but the heuristic saves all of these calculations.

Current algorithms used

In version 2.1 work on this heuristic was disabled after I discovered a surprisingly simple algorithm that solves all these problems. First I decided to exactly define the “best approximation”. This should be done by defining a price for every approximation and choose the approximation with the lowest price. Prices are defined as such:

Approximating row/column x by y costs dist(x, y) ^ 2.

This prefers two smaller approximation errors before a single larger error and describes my goal quite well.

The cost for adding a new row/column specifies when it is better to do a bad approximation and when to add a new row/column. I use (4 * step) * (4 * step). This means that the approximation is acceptable when dist(x, y) < 4 * step. Otherwise, adding a new row/column costs less. Now the best approximation is known. All that is required is a fast algorithm to do this. Surprisingly, this is possible in linear time using a relatively simple dynamic algorithm. It uses approximations of length < n to make a guess at the length of n. It can start by approximating one row/column and then again for two, three up to xsize/ysize rows/columns.

The algorithm starts by calculating prices for all possible new positions for old row/column 1. Because of the pricing there are maximally 8 new positions. (Other ones must cost more than adding new row/column). Of course it is possible that there are no new positions.

For calculating the price of approximations for row/column 2 I may use the previous column: Try new position n. Calculate the price and add the best approximation for the previous (row/column 1) that uses a new position lower than n (thus prohibiting doubling or swapping). This should be one of 8 positions or (eventually) adding a new one and not using row/column 1 at all.

The same method can be used for the rest of the rows/columns. At the end the best price may be found for the last row/column and return by the way it was calculated. (For this I need the saved “calculated using” values.) At this step the best approximation has been determined.

To fill the table, 9 * n steps are required and n steps to backtrack to the best approximation. The only problem is that this algorithm is still a little slow (chiefly because of slow memory access on the Intel architectures). But, with some optimizing, it works well.

This algorithm is almost perfect except that it occasionally adds new rows/columns to the wrong locations — it does not prefer to add new rows/columns into holes — but it does not seem that this is a real problem. The last optimization made was based upon the fact that added rows/columns do not have the exact real and imaginary components calculated by (beginning + x * step) but lie at the average of their left and right neighbors. This makes the boundaries smooth and distributes coordinates better. It also has the added benefit of making the input better for future approximations.

Another danger during implementation of this algorithm is that adding new rows/columns into their ideal positions could cause misordered results, since some rows/columns could be off more than the distance between them. To avoid this, I use an algorithm that always examines the start and end of a block of new rows/columns and linearly interpolates the value between them. Special care needs to be taken with the blocks that start at the beginning or finish at the end.

Implementation should be much faster using custom fixed-point routines — first recalculate values such that 0 means start of image and 65536 means end. Than calculation is much cleaner. Values <0 and >65536 are off screen, calculation is independent of scale, and many things should be recalculated — like tables for calculating price from distance. Also dividing the main loops into many specialized parts and avoiding filling unnecessary parts of tables helps. So current algorithm in XaoS is about 5 or 6 times faster than first naive implementation.

Moving Pixels to New Positions

Since XaoS is using the approximation algorithm the following table is filled for every row/column:

calculate
oldpoint
position

calculate is 1 if the current row/column is new and needs to be calculated or 0 if no old pixels need to be moved. oldpoint is a pointer to the old row/column that corresponds to the new one. This pixel needs to be copied to the new location. position is the real and imaginary components of the coordinates used for future approximations. Because almost all points will be moved, the solution seems to be simple: for every new point look at the row and column table; copy it if required.

There is the problem that this minimally needs three memory reads for every pixel (read calculate, oldpoint and index of old point). This is too slow, so a small optimization is performed. Instead of rewriting the piece of code in assembly, normal memcpy is used to move blocks of pixels to their new locations. This minimizes the internal loop and access can be done more quickly since memcpy is usually optimized for each architecture.

Using the row table, a list of blocks to move for every row is created. With this new table all the pixels can be moved quickly. This increased the speed of XaoS by about four times and made this function so fast that it is no longer a problem. (In fact, it takes much less time than all other parts of XaoS.)

Calculating New Pixels

The above optimizations make XaoS very fast, but another 30% increase in speed is acquired by using a clever method for calculating the new pixels. Many methods are known for saving calculations during the generation of fractal images. The most powerful is boundary detection. It relies on the fact that the Mandelbrot Set is connected with lakes. You need only one pixel at the boundary, then can traverse the whole set and fill the solid area inside. This method saves many calculations but is too complex for adding just one line. Many claim that it does not introduce any errors, but this is not true. It is possible for a connected part of the lake to be so small that it is not visible in smaller resolutions. In this case, boundary detection misses the whole area. This algorithm is actually used just for calculating of new images (i.e. at the startup).

XaoS uses modification of method known as solid guessing. The pixels at the boundaries of a rectangle are calculated. If they are all the same you may assume that this rectangle does not does not contain anything and fill it.

This algorithm is further modified to operate on added lines. For this it is at least as good as boundary detection and produces more tangible errors. When adding a single line, the upper and lower line may be examined for the nearest three pixels. If they are all the same then it is assumed that 9x9 pixels are the same. This disables all calculations inside solid areas and calculates as many points as boundary detection. The only possibility of creating a larger error with this method as opposed to boundary detection is in the instance that the shape of the set is so sharp that it does not set any of the tested points but comes from the right (i.e., uncalculated) location. This situation is not very common.

Later, rules were added for new rows and columns that crossed each other. In this instance you can test only four pixels. This situation is very rare. It is hoped that it does not introduce many errors.

If multiple blocks of new lines need to be calculated there are no reference pixels to use for solid guessing. Interlacing does the trick. By calculating the odd lines without any guessing, the guessing algorithm is now possible for the remaining uncalculated lines. This simple trick saves about 30% of the calculation of the main Mandelbrot image.

A similar approximation can also be done for the X coordinate. This makes it possible to improve solid guessing at even pixels because all surrounding pixels are available, further reducing errors.

Symmetry

Many fractals are horizontally or vertically symmetrical. This is implemented in the approximation code. When there is no good approximation available, try to mirror the opposite side if the line is available.

This method primarily speeds up the initial image.

Calculation of the Mandelbrot Set

The internal Mandelbrot calculation loop is unrolled — it calculates the first 8 iterations using the normal method, and then it expects that number of iterations will probably be large, so it switches into a mode where it calculates iterations in blocks of 8 with one bailout test at the end. When the bailout is attained, saved values from previous iterations are restored and the last 8 iterations are recalculated slowly to get exact values. This especially helps on the Pentium, where conditionals in floating point code are slow.

Another optimization is periodicity checking. XaoS has loops with and without periodicity checks. In most cases it uses the no-periodicity-checking version. The periodicity check version is used just in the case where some inside-set pixel has been found during the solid guessing phase. This is done mainly because the periodicity checking version of the loop is significantly slower.

Dynamic Resolution

The above optimizations often do not help enough and image calculation is still too slow. One option was to reduce the framerate, but a framerate lower than 5 frames per second is unbearable. Another option is simply to calculate only the details that can be determined within a time interval.

Rows/columns not calculated are simply approximated by referencing the nearest row/column. The result is an image with larger pixels. One problem is the fact that the order of calculating the rows/columns is significant. Previous versions of XaoS simply calculated all rows from top to bottom and then columns from left to right. Using the dynamic resolution code with this algorithm would result in distorted images. This was solved by adding a priority to every row/column and calculating the high priority row/column first. The algorithm for adding these priorities is as follows:

Find middle row/column of uncalculated block. Priority is the size of the block (in floating point coordinates)
Start function for left block and right block

This function produces quite good results. It tends to make same-sized rectangles on the whole image and does not depend on resolution.

Another interesting optimization is that during the zoom it is more advantageous to calculate rows/columns in the center of the zoom instead of the borders since these will be in the viewport longer and the user is usually focusing on the center of the zoom anyhow.

This is done by simply adding to the calculated priority normal_priority / (abs(newposition - oldposition) / step + 1). This prefers rows/columns that do not move a great deal. (Of course, unzooming uses the reverse of this formula.)

The last variable to consider is the time interval for one frame. Setting it too low makes the calculation slow. Setting it too high makes the framerate too low. So the amount of time spent in other parts of the program is calculated and multiplied by 5 to determine the interval. If this indicates a framerate lower than 15FPS, 15FPS is used instead, since slower animations are unacceptable. On the other hand, if it is higher than 35FPS, it is set to 35FPS, since a higher framerate than that is just wasting computer resources. When the image is not animating, this value is changed, so a framerate between 5FPS and 15FPS is selected. This ensures that images are calculated quickly after zooming stops.

Autopilot

Another interesting algorithm controls the autopilot. It is actually quite simple. Interesting parts are found at the boundaries of the set. It randomly looks around and zooms to the first area containing both outside and inside set points. Some fractals (such as the Newton) do not have points inside the set at all. In this case it selects a point where many (more than 2) different colors are around. (i.e., It zooms into noisy areas.)

In the instance that there are no such areas, the autopilot will unzoom. It also detects oscillations / vacillations and breaks them.

The current implementation also does detection of out of range numbers; randomly chosen points are chosen near the old one, to avoid frequent changes of direction.

Threads

Since version 3.0, XaoS has supported multithreading. Most of XaoS routines should be threaded easily — for example moveoldpoints just divides image into n equal parts and each part is computed by one processor. The only unthreaded part is the realloc table calculation routines. I don’t see any way to parallelize it except for calculating both x and y approximations simultaneously (using two processors).

Another interesting algorithm to parallelize is boundary trace; see the comments in src/engine/btrace.c for discussion of the current implementation. The only problem I see in the current implementation is the possibility that calculation is divided into too many parts (realloc tables, move points, calculate, symmetries, dynamic resolution) causing too much synchronization between each part. So this may be too slow on a real SMP box.

This description should be useful for those who want to port XaoS to multiprocessor platforms, and those who want to implement a filter or other relatively computationally expensive code. Note that the thread library uses nothread calls as a degenerate case when only one thread is used, when the host does not allow multi-threading or it is not an SMP architecture (since this library is used only to distribute calculation into other CPUs).

XaoS thread library is a simple map of a few functions required by XaoS to the system’s library for threads.

It has the following variables:

Variable: ethreads
This is set to 1 in the case that threads are enabled
Variable: nthreads
Number of threads

It provides the following functions:

Function: void xth_init (int threads)
This function initializes the threading library (starts threads, sets ethread to 1 and nthreads to n. threads parameter should be set to 0 for auto-detection, or to the number of threads the user wants. If threads is set to 1, the threading library is disabled and the following functions are mapped to the nothread_ equivalents defined in xthread.h.

Note that all threads are not interchangeable — there is a main thread (the one that called xth_init) that communicates with drivers, controls calculation, and so on, and there are child threads that are waiting for orders from the main thread. The latter threads can’t use any functions from the xthread library.
Function: void xth_uninit (void)
This function un-initializes the thread library — kills child threads and sets ethread to 0 and nthreads to 1.
Function: void xth_function (xfunction *function, void *data, int range)
This function is used when the engine wants to perform some operation on the image in parallel. It is expected to wait until all threads are ready, then start function on all threads, including the control one, with the following parameters: data — the same as data passed to xth_function, taskinfo — pointer to a platform-dependent taskinfo structure (defined in xthread.h), but must have at least a field n, that holds the thread number (where the control thread is numbered 0 and other threads are numbered in the range 1 – nthreads). The next two parameters are the range of images across which the function is expected to work. xth_function is expected to divide range into nthreads equal pieces and pass to each thread the start of a piece and the start of the next piece (range for the last one). The function does not wait for other threads to finish at the end, but returns immediately to main thread after function returns.

This function is called approx. 5–10 times per frame.
Function: void xth_sync (void)
This function waits until all threads are ready for the next order from the main task.

This function is called approx 5–10 times per frame.
Function: void xth_bgjob (xfunction *function, void *data)
This function is expected to behave as follows: if there are any threads waiting for orders, ask one of them to call function with similar conventions as in xth_function except that the range parameters are set to 0. Otherwise it starts function in the foreground, as usual.

This function is called once per frame.
Function: void xth_nthread (struct taskinfo *s)
This function should be used to determine the current thread number. Do not use taskinfo->n instead, since if threads are disabled this will be defined to 0 to allow the optimizer to perform better optimizations. This function can be called by all threads.
Function: void xth_lock (int n)
Function: void xth_unlock (int n)
Lock/unlock lock number n. At least MAXSEMAPHORS locks must be available.
Note that locks are used for very short fragments of code, so they need to be fast; so spinlocks may be better than classical Dijkstra semaphores (although this is untested). They are called once per calculated line/row during zoom and once per approx 10 pixels during calculation of a new image.
Function: void xth_sleep (int n, int l)
Expected to atomically unlock lock l and sleep in queue n. At least MAXCONDS queues must be available. After the function is woken up, lock l again. This mechanism is used by the new image calculation algorithm, but it is designed to minimize its calls, so I expect it should be called once or twice.
Function: void xth_wakeup (int n)
Wake up some thread from queue n. The lock used by sleep calls is locked in this case. The function should wake up all threads if a single-thread awaken is not supported by the host API.

With luck, this function will not be called at all; it will be called by the new image calculation routines when the queue is empty. This happens when there are 50 threads or thereabouts, but happens rarely at two or eight threads in my tests.
Function: void xth_wakeall (int n)
Similar to wakeup but wake up all threads.

Future Plans

Some of the mulithreading code in XaoS is buggy (notably, multithreaded boundary trace deadlocks). It was written before multi-core systems were common and I don't know if it was originally tested on a real multicore system where race conditions would have been evident. The thread library is a thin wrapper around pthreads. The existing code can be fixed, but rewriting multithreaded code in OpenMP might make the threaded code easier to understand and potentially reduce surface area for bugs.

Timers

Timers allow you to measure time since last reset, pause them or set handlers and intervals. In the current implementation, handlers are not yet activated at the given interval. Since timer library is not asynchronous, you must activate them yourself.

For activating groups are used. You should process a group at some place in your program, whereupon all timers in the group are checked and their handlers activated if required. When the time spent since last activation is higher than the interval, the handler is activated more than once. Also, the interval to next invocation is calculated to keep frequency. Simple scheduling is performed for handler — handler is activated just once and then all other timers are checked before it is activated again. You can also define a multihandler — a handler that is activated just once and receives as an argument a count of intervals.

There are two special groups — asyncgroup. Timers in this group are activated asynchronously (as though they were called from interrupts). Thisis not recommended, since the asynchronicity brings many problems and usually isn’t required. Also it does not work on many platforms. syncgroup is the default group. The program is expected to process it quite often. If you don’t need to use more than one group, you should use this one.

Time in timerlib is bit strange, since it does not flow continuously but jumps. It is updated every time you call tl_updatetime. I did this in order to minimize context switches, but later I found this scheme very useful, since you normally look up the timer, do something and then reset it and don’t want to worry about any time spent between lookup and reset. This helps to keep frequency of timers exact w/o any errors caused by such situations. At the other hand you need to call tl_updatetime at least once in your main loop.

Maybe you don’t know why you’d want to create more groups, but I found it quite useful. For example, an autopilot in XaoS has such a special group — I need to call it approx. every 1/20 of second, but just at one place in the program. Invocation of the autopilot when calculation is active would produce incorrect results, so I have a special group for autopilot and process it in just one place where I am sure it is safe.

Timers can also be emulated. You can stop them and then control the flow of time for given timer. This should be quite useful; for example, when you want to precalculate animation at a given framerate.

To control a group of timers, you can create emulators, which are just other timers controlled by you. They are useful in cases where you want to emulate fixed framerates (for animation rendering) or suchlike.

Time functions

Function: void tl_update_time (void)
Update time used by timerlib. This must be called at least once in the main loop otherwise time will not flow. See above.
Function: void tl_sleep (int time)
Sleep for the given time. Similar to usleep in POSIX.

Group functions

Function: tl_group* tl_create_group (void)
Allocate and initialize the group header. Returns NULL when malloc fails.
Function: void tl_free_group (tl_group *group)
Free memory storage used by group structure.
Function: int tl_process_group (tl_group *group, int *activated)
Process timers in group and activate their handlers. Returns time until next invocation; the main loop should sleep for that long. The activated parameter is either NULL, or a pointer to a variable that is set to the number of activated handlers.

Timer functions

Function: tl_timer* tl_create_timer (void)
Create timer structure.
Function: void tl_free_timer (tl_timer *timer)
Free memory storage used by timer structure.
Function: void tl_reset_timer (tl_timer *timer);
Reset timer to current time (the time of last actication of tl_update_time).
Function: int tl_lookup_timer (tl_timer *timer);
Return time since last call of tl_reset_timer or last activation of handler.
Function: void tl_set_interval (tl_timer *timer, int interval);
Function: void tl_set_handler (tl_timer *timer, void (*handler) (void *), void *userdata);
Function: void tl_set_multihandler (tl_timer *timer, void (*handler) (void *,int),void *userdata);
Handler, multihandler and interval control functions
Function: void tl_add_timer (tl_group *group, tl_timer *timer)
Add timer to given group. A timer should be in only one group.
Function: void tl_stop_timer (tl_timer *timer)
Function: void tl_resume_timer (tl_timer *timer)
Stop and resume timer.
Function: void tl_slowdown_timer (tl_timer *timer,int time)
The time in the timer is moved back to the given time.

Emulator functions

Function: struct timeemulator *tl_create_emulator (void);
This function creates new a emulator — you need to create one first before emulating.
Function: void tl_free_emulator (struct timeemulator *t);
Destroy emulator’s data.
Function: void tl_elpased (struct timeemulator *t, int elpased);
Move emulated time.
Function: void tl_emulate_timer (struct timer *t, struct timeemulator *e);
Set timer to the emulated mode; the passage of time is now controlled by the emulator e. All other behavior of timer keeps unchanged.
Function: void tl_unemulate_timer (struct timer *t);
Disable emulated mode for the timer.

Example main loop

while(1)
{
  time=tl_process_group(syncgroup,activated); /*Call game control functions*/
  update_keys();
  if(activated) /*something changed*/
    display();
  else tl_sleep(time);
}

Future Plans

The platform dependent portions of this library have been reimplemented using the C++ std::chrono library so different APIs are no longer necessary on different platforms. It should be possible to use Qt Timers directly in the GUI portions of the code instead of this library.

The library is also used by lower-level code in XaoS, where several bugs have been observed. First, the frame time calculation doesn't seem very accurate, so that zooming motion becomes jerky when rendering gets behind. Any frame rate drop below 60Hz on a modern LCD monitor will result in noticeable stutter. Also, the emulation of animation timers during animation rendering does not seem very accurate. When a morphview is executed during a render, it will go slightly faster than an actual zoom, and when a new animateview command is reached, the view will jump back several frames since the rendering got ahead of the location that was expected.

To alleviate these bugs, additional work will be needed. Whether we fix this library or rewrite the animation recording and rendering code in terms of std::chrono remains to be seen.

Palettes and Images

The aim of the palette library is to provide a relatively abstract interface to the various visuals, and hide differences in the hardware and driver implementations. Fixed color, pseudocolor, grayscale and truecolor visuals should be handled in almost the same way.

It provides the palette structure, containing a palette. You might allocate new colors here (you give an RGB value and the corresponding pixel is returned), interpolate colors where possible, cycle colors and so on.

Every palette contains two parts — the preallocated color cells and the actual palette. For instance, this could be used to allow the GUI the possibility to allocate static, unchanging colors for its texts and dialogs, while the rest of the palette is under the control of different parts of XaoS.

This library also contains a set of functions to allocate different palettes used by other parts of XaoS. I expected that different parts of XaoS could share the same palette. This hasn’t happened yet, but the functions are kept here just in case.

The image library is built on top of the palette library, providing functionality for handling actual image data. Each image is represented by one or two frame-buffers (useful for double-buffering). One frame-buffer is called ‘current’ and the other ‘old’. They are flipped by a special function. The program can draw into either of them.

Frame-buffers are held as a set of pointers to scan-lines. This provides more flexibility than more obvious representations, because tricks like sub-windows and flipped bitmaps are possible. It’s also fast, since you should avoid one multiplication.

The last significant information the image structure holds is of course the bpp depth. It is counted in bytes, and ranges from 0–4 (where 0 is used for 1bit bitmaps).

Future Plans

The emphasis on multiple bit depths by this library is outdated when even a limited platform like the Raspberry Pi supports truecolor visuals. Now that the code is compiling as C++, it would be possible to use templates for much of what is currently done via preprocessor abuse. Code could be simplified further by removing support for unneeded bit depths. As is, 256 color support needs to remain for the palette emulation to support color cycling, and the edge detection and 3D filters seem to support only 16-bit images. It should be possible to update the 16-bit dependent libraries to support truecolor, and modern computer are fast enough that color cycling could probably be emulated on a palette larger than 256 colors.

In addition, the grlib library provides many graphics primitives such as line drawing that can be done better using the Qt QImage and QPainter classes. The text rendering has already been replaced by native Qt rendering to support TrueType fonts and non-Latin scripts. Further reimplmentation of drawing primitives using Qt and adding more advanced primitives is a future goal.

Filters

This is a brief description of the filter system used internally by XaoS. Filters in XaoS provide an object oriented interface to every part of the XaoS engine. The main filter is the zooming engine implemented in zoom.c. Active filters are kept in a queue — in the beginnning there is just the zooming engine, but at any later time additional filters (stereogram generation, and so on) can be inserted into the middle of the queue.

When calculating, every filter should use data calculated by the filter immediately before it in the queue, which that filter placed into the image it passes to its child. For example, the stereogram filter should take the fractal generated by the zooming engine and create a stereogram from it (assuming that the zooming engine is immediately after the zooming engine in the filter queue).

This makes XaoS’s code more flexible and makes future enhancements easy (perhaps a different zooming engine, or image rotation, other special effects, plug-ins or some other funny stuff) since the enhancements are forced to be decoupled by the filter library, and since each filter has a degree of control over filters that follow it in the queue. For instance, the stereogram filter should change the palette, force the zooming engine to change the depth, width and height of the calculated image to fit its needs, and so on.

This document mainly describes the creation of a filter like the stereogram generator — i.e. a filter placed into the middle of the queue — since I don’t expect there will be many people creating “terminal” filters (zooming engines/user interface layers). Note that different user interfaces are possible, since the user interface layer is not the real user interface, just a set of high level functions that should be called by the main application, like set_view. So if you want to use XaoS as a calculation engine in your program this document is probably not for you.

Each filter is defined by a filteraction structure, as follows::

struct filteraction {
  char *name;
  char *shortname;
  int flags;
  struct filter *(*getinstance)(struct filteraction *a);
  void (*destroyinstance)(struct filter *f);
  int (*doit)(struct filter *f,int flags,int time);
  int (*requirement)(struct filter *f,struct requirements *r);
  int (*initialize)(struct filter *f,struct initdata *i);
  void (*convertup)(struct filter *f,int *x,int *y);
  void (*convertdown)(struct filter *f,int *x,int *y);
  void (*removefilter)(struct filter *f);
};

This structure describes unchanging parameters to the filter (like its name) and a basic set of methods required for communication with the rest of XaoS. The name field is a comparatively long description of the filter’s name, such as “A random dot stereogram generator”. name is displayed by the ugly interface in the Filters menu, so it is expected to be descriptive (but shorter than 30 characters). The short name is a one word long name for the filter, like “stereogram”. This name is used in save files and command line parameters; everywhere that the user might need to write it, so writing a long descriptive name would just be wasteful of time and disk space.

The flags field is reserved for future enhancements and is expected to be 0 for now.

Instance creation / destruction

Functions getinstance and destroyinstance are equivalent to the constructor and destructor in object-oriented languages. getinstance is expected to create and fill out the following structure:

struct filter {
  struct filter *next,*previous;
  struct queue *queue;
  struct filteraction *action;
  struct image *image,*childimage;
  struct requirements req;
  struct fractal_context *fractalc;
  void *data;
  char *name;
  int flags;
  void (*wait_function) (struct filter *f);
  /*stuff for wait_function*/
  int pos,max,incalculation,readyforinterrupt,interrupt;
  char *pass;
};

Although this structure seems to be long and complex, most of the fields are currently unused, and the rest of them are filled out automatically by a helper function:

Function: struct filter * createfilter (struct filteraction *fa);
This function should be used to do the dirty work of instance creation and fill out the filter structure. The only possibly interesting field is data, a pointer reserved for the filter’s internal use; it can be a pointer to the filter’s internal variables if required. This is what a getinstance implementation that allocates such an additional structure might look like:
```
static struct filter *getinstance(struct filteraction *a)
{
      struct filter *f = createfilter(a);    /*create filter structure*/
      struct stereogramdata *i=calloc(sizeof(*i),1);
                                             /*allocate internal variables*/
      /*initialize your variables here*/
      f->data=i;                             /*add pointer to internal data*/
      return (f);
}
```
If nothing similar is required you can simply put creatfilter into the getinstance field.

destroyinstance is expected to free the memory used by the filter structure and all the filter’s internal data. To free the filter structure use the normal free call. An implementation of such function should look something like :

static void destroyinstance(struct filter *f)
{
     destroyinheredimage(f);
     free(f->data);
     free(f);
}

The meaning of destroyinheredimage will be described later.

Initialization

During the initialization phase, each filter says to its parent what kind of images it supports (which should depend on the images that it’s child has said it supported), the parent chooses the best supported image format for its purpose and gives that to the child (while passing that information on up the queue of filters). Initialization is done in two passes:

The first pass starts at the lowest filter in the queue (zoom, by default); each filter passes a requirements structure to its parent.

The second pass starts at the highest filter (the ui filter), and each filter passes to its child an image and some other stuff. Then calculation should begin.

The queue needs to be reinitialized after creating, resizing, adding or removing a filter, and similar operations.

The first pass is implemented using the require function. This function is expected to look at the child’s requirements it received as a parameter, fill out its own requirements structure, and call the require function of its parent filter.

struct requirements {
  int nimages;
  int supportedmask;
  int flags;
};

The nimages field should be set to 1 or 2. When it is 2, the parent filter must pass the image in two buffers (double-buffered). Note that if it is 1, the parent should pass the image in two buffers, but is not required to.

supportedmask is a mask giving the image types supported by the filter. Valid image types are:

C256
A normal 8bpp image with palette
TRUECOLOR24
A 24bpp truecolor image with 8 bits for each color.
TRUECOLOR16
A 16bpp truecolor image
TRUECOLOR
A 32bpp truecolor image with 8 bits for each color.
LARGEITER
A 16bpp image, but without colors. The pixels are expected to hold an iteration count; it could also be thought of as a 16bpp grayscale image.
SMALLITER
Similar to LARGEITER, but 8bpp.

If you don’t want to worry about palettes, color allocations and so on, but just want to do some non-display operation with a bitmap, you probably only care about the image depth and not the precise meaning of the pixels; in that case, you can use one of the bitmasks MASK1BPP for 8 bit images, MASK2BPP for 16 bit and so on.

The final field in the requirements structure is flags. It’s a mask composed from the following constants:

IMAGEDATA
Set this if your filter requires the data from previous frame untouched. When this is not set, filters can reuse your image and change it. But some filters, like motion blur or the zooming engine, require data from the previous frame to construct the new one; for such filters, this flag should be set.

There are no more flags supported at the moment. The require function should also save the child’s requirements structure into filter->req for later use by the initialize pass. The code for a requirement function might look like

static int requirement(struct filter *f,struct requirements *r)
{
  f->req=*r;    /*Save an child's requirements*/
  r->nimages=1; /*Just one image is required*/
  r->flags&=~IMAGEDATA;/*unset the imagedata field*/
  r->supportedmask=C256|TRUECOLOR|HICOLOR|REALCOLOR;
                /*mask of all supported image types*/
  return (f->next->action->requirement(f->next, r));
                /*call parent*/
}

The next pass is the main initialization pass. It goes in the opposite order (from parent to child, from the top of the queue to the bottom, in the same direction as image flow), and the child receives some stuff from the parent (such as images). The initialize function receives an initdata structure:

struct initdata {
  void (*wait_function) (struct filter *f);
  struct image *image;
  struct fractal_context *fractalc;
  int flags;
};

wait_function points to a function called by the filter during calculation that lets the parent filter (usually the user interface layer) inform the user of calculation progress. image is an image expected to be filled with an image in the calculation phase. fractalc is a pointer to a structure that will contain information about the fractal itself during calculation (formula type and so on). flags is a mask of the following constants:

DATALOST
This is set if the data in the previous image was lost (if the image was cleared or resized or freshly allocated). Filters that use data from previous frames should pay attention to this flag. The zooming engine, for example, recalculates the whole image if this flag is set, since all pixels from the previous frame were lost. Note that data will also be lost if the filter receives a different image than in the previous initialization (since some filter before it in the queue was removed).

Inheritance is carried out using these functions:

Function: void inhermisc (struct filter *f,struct initdata *i);
This function sets fields in the filter structure like fractalc or wait_func. Inheritance of images is quite complex, since the new image needs to be prepared for the child filter. In order to save memory it is highly recommended to use the same image — or at least the same memory — for data when passing to the child, but this is not allays possible. The following function implements a heuristic to reuse the image where possible:
Function: int inherimage (struct filter *f,struct initdata *data, int flags, int width, int height, struct palette *palette, float pixelwidth, float pixelheight)
You should call this function in your initialize pass. It fills out image and childimage in the filter structure, and prepares initdata and image for the child. Note that in some cases it may fail and return 0. In this case the filter is expected to interrupt initialization and return 0 too.

The flags parameter is a mask of the following constants:
- IMAGEDATA
  Set if your filter requires data from the previous frame.
- TOUCHDATA
  Set if your filter touches data in the output image. This is the usual case, but some filters, like interlace or subwindow, don’t touch the image data at all.
- NEWIMAGE
  Set if your filter cannot use the same image for output as it uses for input (that is, if the two images must be distinct blocks of memory).
width and height are the width and height of the image you want to pass to the child; it should be set to 0 if you want the same width/height as in the parent image. palette is the palette of the image you want to pass; set to NULL if the palette should be inherited from the parent’s image (as is usual). pixelwidth and pixelheight give the physical size of a pixel in centimeters; if set to 0 they are inherit from the parent’s image.

If you use the inherimage mechanism, you must also call destroyinheredimage in the destroyinstance function and updateinheredimage at the beginning of the calculate function.

Example implementation:

static int initialize(struct filter *f,struct initdata *i)
{struct stereogramdata *s=f->data;
  inhermisc(f,i);
  if(!inherimage(f,i,TOUCHIMAGE,0,0,NULL,0,0) return 0;
  /*initialize here*/
  return(f->previous->action->initialize(f->previous,i));
}

Also note that the fractal context holds a pointer to the fractal’s palette. If you don’t change the image’s palette everything is OK; but if the child’s image differs from the parent’s, there should be two behaviors — the fractal’s palette is the child’s one (this is common in color conversion filters, going from 8bpp to TrueColor and suchlike), or the fractal’s palette is the parent’s one (like in the edge detection filter). By default the fractal’s palette is set to the parent’s one, because this is most likely to be generally useful; anything else requires explicit work from the parent to set up the child’s new palette.

This can be changed by the setfractalpalette call, which has two parameters — the filter structure, and the new palette. When you pass the child’s palette as palette, the fractal’s palette will be changed to the child’s. If you pass NULL, changing the palette will be disabled (as in the motion blur filter in 8bpp mode). This is only changeable if you still have access to the fractal’s palette; some parent might have already redirected the palette beforehand, in which case this function does nothing.

Calculation

The calculation is done using the doit function:

Function: int (*doit)(struct filter *f,int flags,int time)
This function is expected to call the child’s calculation function when required, and apply its filter to the child’s output.

The flags are mostly undefined; only INTERRUPTIBLE is defined for now, and that is mainly for the zooming engine so I do not describe it here. Nonetheless, the filter is expected to pass the flags to its child. Finally, time is the time in milliseconds that expired since the last doit call. It can be used to calculate the animation speed, perhaps in an attempt to keep the speed constant.

Calculation loops return a bitmask composed of the following flags:

ANIMATION
Set if the filter performs some animation, and expects that its calculation function will be called again soon.
CHANGED
Set if something changed in the output image (the usual case).
INEXACT
This is enabled by the zooming engine in INTERRUPTIBLE mode in case the time was exceeded.

Most doit functions change the image. The image structure contains following fields that might be significant to filters:

bytesperpixel
Number of bytes per pixel (image depth).
palette
Palette of image.
currlines
Array of pointers to the beginning of each scanline in the image.
oldlines
Like currlines, but for the previous image, when double-buffering is enabled.
nimages
Set to 2 when double-buffering is active.
flipimage
Pointer to a function that flips oldlines and currlines.

The palette structure contains the following significant fields:

type
Type of palette/image (C256, TRUECOLOR etc...)
size
The number of allocated entries in the palette.
pixels
The array of allocated entries; a conversion table mapping from the iteration number to a pixel value.
rgb
RGB values for pixels (NULL for TRUECOLOR, HICOLOR and similar paletteless types)

To make writing calculation loops for different bit-depths easier, pixel8_t, pixel16_t and pixel32_t are predefined. You also can use preprocessor magic as the edge detection filter does; this lets you write calculation loops just once, using cpixel_t, and the code will be compiled for every bitmap depth. See the edge detection filter (src/engine/edge.c and src/engine/edged.c) for implementation details.

Coordinate conversion

The convertup and convertdown functions are used for converting screen coordinates to a position in the fractal and back. convertup receives coordinates in the child’s image, and is expected to convert them into coordinates in the parent’s image and call the parent’s convertup function.

convertdown is the reverse of convertup (going from parent to child).

If coordinates correspond 1:1 you should use convertupgeneric and convertdowngeneric; otherwise, the implementation should look something like this:

static void convertup(struct filter *f,int *x,int *y)
{
    *y*=2;
    *x*=2;
    if(f->next!=NULL) f->next->action->convertup(f->next,x,y);
}
static void convertdown(struct filter *f,int *x,int *y)
{
    *y/=2;
    *x/=2;
    if(f->previous!=NULL) f->previous->action->convertdown(f->previous,x,y);
}

Filter removal

Before the filter is removed from the queue, the removefilter function is called. It is expected to clean up anything that the filter changed.

In most cases, it should be left at NULL.

Filter registration

Once the filteraction structure is filled, the filter is ready, and you should try to enable it. To enable it in the user interface you need to edit src/ui-hlp/ui_helper.c, add the filter to the uih_filters structure, and increase uih_nfilters. Note that the order of filters in uih_filter defines the order of the filters in the filter queue.

Future Plans

The filter system is integral to the core of the XaoS engine. I don't anticipate that much of this code will be replaced, but it could be refactored into C++ object oriented code. The underlying C code is already fairly object oriented so it is a natural fit. Also, certain portions of the code could benefit from template instantiation to avoid the current use of includes to provide generic code.

Fractal Formulae

Formulas are defined in formulas.cpp. Also of interest is fractal.h which defines many of the data structures referenced, and docalc.h, which contains the generic calculation routines that are customized for each individual formula. Calculation is governed by the fractal context, which contains information like the current formula, the seed (for julia sets), the palette, and so on.

In formulas.cpp, you will find some lines containing macros starting with #define VARIABLES or similar, and ending with #include "docalc.h".

Every time docalc.h is included, it generates a different set of functions. It depends upon how the preceeding macros are defined. Following is a brief description of how formulas are defined in the macros.

Mandelbrot's original formula is z=z^2+c which means z[next]=z[previous]^2+c. Here c represents the pixel coordinates and z[0] is usually 0 (if perturbation was not added).

In the following code z[previous] is described by (zre;zim) and z[next] will also be zre and zim after the calculation is done. c is described by (pre;pim). Finally rp and ip are helper variables, mostly for checking the bailout (which usually means abs(z)>=4; see BTEST).

Formulas can use both basic C operations and some convenience macros (c_mul, c_pow3, etc.), which are defined in include/cmplx.h.

After defining the macros, you must put the description of your formula at the end of the structure named formulas (just before the last entry for user defined formulas. You can make it similar to the existing formula descriptions. The fields defined for each fractal are as follows:

FORMULAMAGIC
CALC function (default calculation function)
PERI function (calculation with periodicity checking)
SCALC function (calculation with smooth palette)
SPERI function (smooth palette and periodicity checking)
JULIA function (calculation in julia mode)
{"Name of Mandelbrot", "Name of Julia"}
"short name"
Default position: {x_translate, y_translate, ?, scale}
hassymmetry (0 or 1)
isMandelbrot (or Julia, at startup)
pre -- real part of Julia seed
pim -- imag part of Julia seed
{{}, {}... } structures about the symmetries of the outcoloring modes}
{{}, {}... } structures about the symmetries of the incoloring modes}

These format of the symmetry information is:

{vertical_symmetry, horizontal_symmetry, size_of_other_symmetries, other_symmetries}

Horizontal and vertical symmetries can be INT_MAX or 0, where INT_MAX means no symmetry, 0 means symmetry.

The next two entries are like {... 2, sym6} {... 2, sym8} or {... 6, sym16}

Flags, such as MANDEL_BTRACE or JULIA_BTRACE, which enables boundary tracing on new images in Mandelbrot or Julia mode, respectively. Also, there is a special SFFE_FRACTAL flag that is only used for the user defined formula (last entry).

Future Plans

This file is one of the more egregious cases of preprocessor abuse in XaoS, and that's saying something. The repeated inclusion of docalc.h could possibly be replaced by C++ templates, with templates defined on the functions in docalc.h referencing inline methods defined in a formula class corresponding to the current macros. This is assuming we could guarantee that the compiler would inline the functions defined in the formula class. If there is a better way to do this, I invite any C++ experts who may be reading this to tell me.

I would also very much like to implement arbitrary precision in some form. Currently on x86/x64, XaoS uses long double by default, which provides 80-bits of precision. Most other platforms such as ARM are limited to 64-bits by default. It is possible to optionally compile XaoS with support for 128-bit __float128 numbers on GCC. However, rendering performance is noticeably slow, even on modern computers with multitheading enabled.

Given that __float128 is too slow to do real-time zooming comfortably on a modern computer, I am sure that MPFR would be even slower, perhaps even unusable. However, one approach that might make arbitrary precision viable is Perturbation Theory used in Kalles Fraktaler 2 and SuperFractalThing. Perturbation Theory only requires calculating the orbits of a single point in arbitrary precision, then the rest of the points in the image can be calculated using floating point double precision, relative to this reference point. I have not investigated how readily adaptable this approach would be for XaoS's zooming algorthim, but it's worthy of some research.

User-Defined Formulae

User defined formulae are provided by the SFFE library by Mateusz Malczak. Syntax for user formulas is documented here. The following implementation details were taken from Mateusz's blog.

SFFE is an easy to extend math parser, that is able to efficiently evaluate math formulas in complex number space.

Here are some notes and details on how it is built.

Design Goals

The first step was to create a simple math parser for real numbers. Keeping in mind, that it has to be fast and will be used only for function evaluation I made these basic assumptions:

ignore variables modification (assignment)
ignore all logical operations
set of numbers independent (ℝ, ℂ);
precision independent
easy to extend
make it fast

Design

The basic task is to transform a math expression x * sin( 2 * x / y ) into corresponding stack notation (prefix or reverse Polish notation).

x y / 2 * sin 2 * (rpn)
x 2 x * y / sin * (prefix)

Arithmetic notations are then transformed into bytecode (or operators stack/tree) and expression value can be evaluated.

The problem with this simplified approach is that stack needs to be fixed (or even rebuild) every time we want to calculate an expression value. Because the parser is going to be used in loops, this is something we should avoid and the internal stack stucture should never be modified. There should be no extra steps before and after expression value is evaluated. Moreover there should be no memory operations during this operation.

The whole process can be divided into to two parts with two corresponding modules

parser - used only once to parse input expression and transform it into bytecode
evaluator - evaluate the value of the expression using input variables

It doesn't matter how fast parser is; it only needs to be reliable. To be honest it is slow, complicated and a bit memory consuming.

I have only focused on evaluator implementation. Its internal structure should fulfill this set of rules.

expession evaluation should be an in-situ operation.
evaluator should never change its state - in terms of its internal structure (no stack manipulation) and in terms of consumed memory.
changing the input variables should not result in any memory operations.

Implementation

Parser module

The parser is responsible for translating the input formula string into some kind of bytecode.

Lexical and syntactic analysis use a simple context-free grammar for math expressions. Implementation depends on the set of numbers we are working with (ℝ or ℂ).
Tokenization - convert input an expression x * sin( 2 * x / y ) into tokenized form and keep track of all tokens n * f( n * n / n )
Bytecode generator (eq. operation stack builder) - covert tokenized expression into bytecode

+---+---+---+---+---+---+---+---+
| n | n | n | * | n | / | f | * |
+---+---+---+---+---+---+---+---+

Evaluator module

The evaluator is just a bytecode interpreter. It takes input variables and evaluates expression value. In this particular case bytecode is just a variation of operations stack rather that a typical bytecode. It cannot be saved and reused in compiled form.

use prefix notation
use operation pipeline
don't include store operands on operations stack

Summary

parser can be used for any set of numbers and precision
parser is easy to extend (new functions, constants)
evaluator can be reused with different input variables
expression evaluation is an in-situ operation (in terms of structure and memory usage)

Code

Finally the heart of math parser implementation.

sfNumber sffe_eval(sffe * const parser)
{
    register sfopr *optro;
    register sfopr *optr = parser->oprs;
    register sfopr *optrl = parser->oprs + parser->oprCount;
    optro = optr;
    for (optr = optr; optr != optrl; optr += 1, optro += 1) {
    optro->arg->parg = optro->arg - 1;
    optr->arg->parg = optr->f(optr->arg)->parg;
    };
    return *(parser->result);
};

Example

Parse debug trace

|-----------------------------------------
+ > lib/src/sffe.c[504] - parsing
|-----------------------------------------
| input (len.=30): |(-1+2*3(sin(x+1)-1/x))/(2*x+1)|
| check (len.=30): |(-1+2*3(SIN(X+1)-1/X))/(2*X+1)|
| compiled expr.: |(n+n*n*(f(n+n)-n/n))/(n*n+n)|
| operations: 10
| numbers,vars: 10
| stack not.: nnn*nn+fnn/-*+nn*n+/
| numbers:  -1 2 3 -1 -1 1 -1 -1 1 -1 -1 -1 -1 -1 2 -1 -1 1 -1 -1
| functions fnctbl: [+] [*] [*] [SIN] [+] [-] [/] [/] [*] [+]
| functions used ptrs: __addr_dump__
| compiled in  0.000094 s
|-----------------------------------------
+ < lib/src/sffe.c[1020] - parsing
|-----------------------------------------

Future Plans

Error detection by the parser is in serious need of improvement. It is easy to crash XaoS by giving the parser bad input. The parser should reject bad input instead of trying to interpret too many corner cases. The use of ; to separate function parameters rather than , is unexpected and the {re;im} notation for complex numbers is also strange. Fixing these issues is a high priority.

Until recently, SFFE crashed immediately when multithreading was enabled because the evaluation function is not thread safe. However, this has been solved by creating a thread local interpreter for each thread and adding code to set the formula on each of the thread local interpreters.

Due to the number of crashes and lack of continued involvement from Mateusz, replacing this with another formula evaluation library has been considered.

ExprTk would be a potential candidate. It performs significantly better than most other formula evaluation libraries on benchmarks, but it is extremely complex with over 30K lines of code (more than the entire XaoS codebase). It increases XaoS's compiled size from under 1MB to over 6MB. It has problems compiling on Windows due to the fact that all 30K lines are in a single header, which exceeds the maximum allowable segment size.

Finally, it does not natively support complex math. Initial experiments were done to add complex number support and integrate it with XaoS, to the point that it could be used to render a Mandelbrot set (using z*z+c as the formula). It seemed to be somewhat, but not markedly faster than SFFE based on entirely unscientific measurements. However, the changes were rolled back, primarily due to code size, but also due to the additional effort required to fully support complex numbers.

The other possible candidate is muParserX, which supports complex math already, but it is considerably slower than other formula evaluation libraries on the benchmarks and would likely be significantly slower than SFFE.

AsmJit is a library which provides a C++ interface to JIT assembly on x86(-64) and ARM platforms. It is used by muParserSSE (a sister project to muParserX), but muParserSSE doesn't support complex math or precision greater than 64-bit doubles. However, it's possible AsmJit might eventually be used to improve the performance of SFFE.

Function Registry

XaoS has an ui helper library, which provides functionality used by the user interface. All its useful functions are registered into a central registry. This registry is used to generate menus and dialogs as well as command line options or scripting language; so it is a very significant thing in XaoS design.

This is not just useful for those who want to hack XaoS ui-helper layer itself, but also for developers who want to work on the user interface, who will use these functions to interface with XaoS inner layers.

Knowledge of this part is thus essential for many developers. Please pay attention. :)

The implementation of the registry is in xmenu.c, and the header is xmenu.h. For historical reasons, it talks about menus and dialogs (it was originally designed for the GUI). I am keeping this terminology, since it is quite clean and easy to understand instead of talking in some cryptic abstract terms.

Function description

To add a function into the database, you need to put a description into the menuitem structure. It has the following definition:

typedef struct menuitem
  {
    char *menuname;
    char *key;
    char *name;
    char *shortname;
    int type;
    int flags;
    void (*function) ();
    int iparam;
    void *pparam;
    int (*control) (struct uih_context *);
    menudialog *(*dialog) (struct uih_context *);
  }
menuitem;

Variable: menuname
Name of menu (or category) the function belongs in. The root of all categories is called "root". XaoS also uses an "animroot" when animation replay is active. If you are adding a function, it is better to add it into some subcategory like "ui" (which will place it into the UI menu) or to create a new category for your functions, which will appear as a submenu of the main menu in the UI.
Variable: key
ASCII code of the hotkey that activates this function. Use NULL if none.
Variable: name
Longer name of the function, used in the menu entry, or xaos --help listing.
Variable: shortname
One-word name of function used in command language and other references to the function.
Variable: type
Type of function — this is not the return type. type should be one of the following constants:
- MENU_SUBMENU
  A submenu. This is not a function, but a name for the submenu. You can fill in the key, name, and shortname. The name of this new submenu is placed in the field pparam.
- MENU_NOPARAM
  A normal function without any parameters. When activated, function will be called with a pointer to uih_context as its parameter.
- MENU_INT
  This should be used to simplify entering of many similar functions (handled by just one universal function in the C code). The function is handled in the same way as MENU_NOPARAM, but also one integer parameter taken from iparam is passed in.
- MENU_STRING
  Similar to MENU_INT but uses a string instead of an integer.
- MENU_DIALOG
  If your function needs some paramters, use the dialog structure to describe them. In the scripting language your function then have parameters; in the user interface, a dialog will be displayed. pparam must point to array of dialog entries (writing them will be described later). If your function has just one parameter described in the dialog structure, it will be called in the normal C way — if you want a string parameter, one pointer pointing to a string (in addition to uih_context) will be passed to the functions.
  
  If multiple parameters are requested, it is impossible to call function in a C way without a special wrapper for each case. So it will receive a pointer to an array of dialogparam unions, wich contain one entry for each parameter. dialogparam is declared as follows:
```
typedef union
  {
    char *dstring;
    int dint;
    number_t number;
    number_t dcoord[2];
    xio_path dpath;
    void *dummy;
  }
dialogparam;
```
- MENU_CDIALOG
  In some cases, it is useful to add some context specific default values to the dialog structure. In this case you might use this type instead. In this case the function dialog is called first, and it is expected to return a pointer to the correct dialog structure. The dialog structure must lie in static storage (since it is not freed), and must always have the same fields, and differ only in the default values. This function must also work correctly even when the pointer to uih_context is NULL, since it is often called in the initialization stages (parameter parsing etc.)
Variable: flags
The flags are used to set additional information about the function:
- MENUFLAG_CHECKBOX
  Some features act like check-boxes — i.e. repeated calls to the function toggle the features. In menus it is useful to add a check-box for this function indicating whether the feature is on or off. This flag adds such a check-box.
  
  So that the UI can determine the current state of the checkbox, you need to define the function control, which returns 1 when enabled and 0 when disabled. In order to let external GUIs work correctly you also need to call uih_updatemenus("name") every time the state of this function changes.
  
  In the scripting language, this adds a single parameter, either #t or #f. The engine then calls the function only when necessary. When #t, a dialog is requested; when #f, the function is called just as NOPARAM. I.e. the dialog is displayed only when enabling the feature.
- MENUFLAG_DIALOGATDISABLE
  Display dialog on disabling of this checkbox feature, instead of on enabling.
- MENUFLAG_RADIO
  Other features act like radio-buttons. Control functions in this case receive the same parameter as is defined for MENU_INT or MENU_STRING types, and is expected to return 1 when enabled and 0 otherwise. You also need to call uih_updatemenus when the value is changed. No special parameter is added in the scripting language.
- MENUFLAG_INTERRUPT
  Interrupt current calculation when this function is called (used by functions with cause recalculation of the screen)
- MENUFLAG_INCALC
  By default XaoS queues functions and calls them later when they are activated in the calculation. This flag disables this feature.
- MENUFLAG_ATSTARTUP
  By default XaoS queues functions and them calls later when they are activated as command line parameters (in case the engine is not fully initialized yet). This flag disables this feature.
- MENUFLAG_NOMENU
  If set, the function will not be visible in the menu.
- MENUFLAG_NOPLAY
  If set, the function will not be available as a command in scripts (and therefore won’t be usable by external GUIs).
- MENUFLAG_NOOPTION
  If set, the function will not be available as a command line option.

Initializing the menuitem structure as a static variable

In most cases, menuitems should be written as static variables. Because the contents of this structure could change in future, please use one of the macros defined in xmenu.h. They provide a cleaner and easier to extend way to define these entries than does doing it by hand.

For example to define a MENU_NOPARAM function, use the following macro:

Function: MENUNOP (menuname, key, name, shortname, flags, function)

Similar macros exist for other types too. They end in CB or RB for check-boxed or radio-box functions. See src/ui-hlp/menu.c for a large number of example definitions. They should look like this:

static menuitem menuitems[] =   /*XaoS menu specifications */
{
  SUBMENU ("", NULL, "Root menu", "root"),
  SUBMENU ("", NULL, "Replay only commands", "plc"),
  MENUNOP ("comm", NULL, "print menus specifications of all menus",
           "print_menus", MENUFLAG_NOMENU|MENUFLAG_NOPLAY|MENUFLAG_ATSTARTUP,
           uih_printallmenus),
           ...

Dialog description

A dialog description is similar to a menuitem. It is an array of the following structures:

typedef struct dialog
  {
    char *question;
    int type;
    int defint;
    char *defstr;
    number_t deffloat;
    number_t deffloat2;
  }
menudialog;

It is terminated by an element with the question pointer set to NULL.

The question contains the string the UI should display when it asks for this field.

type should be one of the following values: DIALOG_INT, DIALOG_FLOAT, DIALOG_STRING, DIALOG_KEYSTRING (the difference between string and keystring is that in the scripting language string is passed as "hello", but keystring is passed as a Scheme keyword: 'hello), DIALOG_IFILE (input file), DIALOG_OFILE, DIALOG_CHOICE (choice between different keystrings), DIALOG_ONOFF (boolean parameter), DIALOG_COORD (two floats — a complex number)

Set the corresponding def* field to set the default value. In the case of files, use a string in the format "[prefix]*[extension]". For type DIALOG_CHOICE set defstr to a pointer to an array of strings, terminated by a NULL entry.

To write dialog structures, as with menus, use macros defined in xmenu.h like:

DIALOGSTR(question,default)

The definition should look like:

static menudialog uih_viewdialog[] =
{
  DIALOGCOORD ("center:", 0, 0),
  DIALOGFLOAT ("Radius:", 1),
  DIALOGFLOAT ("Angle:", 0),
  {NULL}
};

Modifying the registry

Function: void menu_add (menuitem *item, int n);
Add an array of n items to the database.
Function: void menu_delete (menuitem *items, int n);
Remove an array of n items from the database.

Querying registry

Function: menuitem* menu_findkey (char *key, char *root);
Find item for given key. root is menu to start (submenus are searched recursively).
Function: menuitem* menu_findcommand (char *name);
Find item for given short name.
Function: char* menu_fullname (char *menu);
Return a long name for a menu, given a short name.
Function: menuitem* menu_item (char *menu, int n);
Return the nth entry in the menu. Return NULL if that entry does not exist.
Function: int menu_enabled (menuitem *item, struct uih_context *c);
Check whether the given item is activated (for check-boxed and radio-boxed functions).
Function: int menu_havedialog (menuitem *item, struct uih_context *c);
Return whether this function has an associated dialog.
Function: menu_getdialog (context, m)
This macro returns a pointer to the dialog structure for a given menu item. (If the item doesn’t have a dialog, garbage is returned).
Function: int menu_available (menuitem *item, char *root);
Check whether an item is available as one of the entries of root (or it’s submenus)

Future Plans

The function registry is currently central to the operation of XaoS, including both the User Interface and processing of position and animation files. However, its rigid structure is the primary limiting factor in implementing more advanced user interfaces. Its use in the UI may eventually it may be phased out entirely. It may be retained in vestigial form in order to maintain backwards compatibility with XaoS position and animation files, since the registry controls both the UI menus and the scripting language used by the files.

Writing a QObject-based wrapper for the UI helper library would be the preferred way to implement more advanced UI features since this would allow it to send and receive signals from the Qt based UI. The QObject wrapper could also be used to provide JavaScript scripting capability for all XaoS functionality, and JavaScript could eventually replace the XaoS scripting language as the primary animation format, while position files could be reimplemented as JSON.

User Interface

The user interface, located in the ui directory is implemented using Qt. The main.cpp file contains the entry point to XaoS, which initializes various subsystems, processes command line arguments, and instantiates a MainWindow, which presents the primary UI for XaoS. Many of the methods in MainWindow encapsulate the ui-hlp library, which the function registry, file handling, and animation processing on top of the XaoS engine.

What follows is a somewhat simplified explanation of how to instantiate and initialize a ui-hlp context from a user interface. For more detailed implementation details, refer to the methods in MainWindow.

Initialization

To initialize the UI helper library, you need to prepare a palette and image. The palette is created using the palette library call createpalette. Creating a truecolor palette should look like this:

  struct palette *pal = createpalette (0, 0, TRUECOLOR, 0, 0, NULL,
                                       NULL, NULL, NULL);

For details about creating palettes see ui.c or ask me.

To create an image, call:

  struct *image img = create_image_mem (width, height, 2, pal,
                                        pixelwidth, pixelheight);

This creates an image in memory. If you want to create it in your own buffers, you might use create_image_cont or create_image calls. Again see ui.c.

Then it is time to fire up the main library:

  struct uih_context *uih = uih_mkcontext (0, img, passfunc,
                                           NULL, NULL);

The passfunc is called when the engine is calculating. It might process external events and display progress information. It should look like this:

static int
ui_passfunc (struct uih_context *c, int display, char *text, float percent)
{
  /*process events */
  if (uih->display)
    {
      uih_drawwindows (uih);
      /*display */
    }
  if (display)
    {
      if (percent)
    sprintf (str, "%s %3.2f%%        ", text, (double) percent);
      else
    sprintf (str, "%s          ", text);
      /*display it */
    }
}

It can set uih->interrupt if it wants to interrupt the current calculation (whereupon the main calculation loop will return to its caller).

You can also load the catalog file in order to make tutorials work:

  uih_loadcatalog (uih, "english");

Once this is done, the ui_helper library is fully functional and you can enter the main loop.

Main loop

The UI helper library does not have any timing primitives; so it expects a standard form of main loop. It asks it caller to redisplay a changed image when necessary. The library also uses the generic timerlib library for its timing, for which see elsewhere in this document.

The main loop should look like this:

while (1)
  {
    if (uih->display)
      {
    uih_prepare_image (uih);
    uih_drawwindows(uih);
    /*display current image buffer*/
      }
    uih_update (uih, mousex, mousey, buttons);
    if ((time = tl_process_group (syncgroup, NULL)) != -1 &&
        !uih->inanimation) {
        /*relax for the given time in usec - wait for events etc..*/
    }
    /*and repeat*/
  }

Calling functions

The UI helper library has many functions declared in ui_helper.h for various actions. There are too many of them to describe here, but their names are quite informative, so I hope you will not have problems.

(You could also use the XaoS function registry, which does all this stuff for you; you will just draw menus and dialogs based on this registry and all features will be automatically made available. If you are writing an ordinary user interface, this is the preferred way.)

Note that the ui_helper library is not reentrant, so you can’t call most of these functions from the passfunc. If you are using the registry, the activating function handles this automatically and queues functions when necessary. To process them you need to flush the queue in the main loop as follows:

static void
processbuffer (void)
{
  menuitem *item;
  dialogparam *d;
  if (uih->incalculation)
    return;
  while ((item = menu_delqueue (&d)) != NULL)
    {
      menu_menuactivate (item, d);
    }
}

Closing the library

This is done using:

  uih_freecontext (uih);

One user of this library is the ugly interface code in XaoS; see the src/ui directory. Another, much simpler user is src/ui-hlp/render.c, which does animation rendering.

Future Plans

Future plans for the User Interface are closely intertwined with plans for encapsulating the interface for the UI helper library (see above). Some specific features I would like to add, which are impaired by the current function registry include:

Ability to save favorites for later recall:
- Favorite palettes
- Favorite user formulas
- Favorite locations (bookmarks)
Customizable keyboard shortcuts (ability to assign any key to any action)
Gradient editing and ability to save and load Fractint map files or GIMP gradients
Simplified and improved rendering of images and animations in a separate window
JavaScript wrapper for XaoS functions
Blockly or scratch-like animation scripting
Customizable preferences which save automatically independent of xpf files
Ability to preview different fractal formulae, coloring modes, and palettes using thumbnails

Developer's Guide

Table of Contents

Supported Platforms

Build Instructions

Prerequisites

Ubuntu and Debian

Windows

macOS

Building from the Command Line

Building from Qt Creator

Historical Perspective

Lay of the Land

Algorithms

Saving Previous Pixels

Approximation Algorithm

Introduction to problem

Some simple algorithms to solve it

Current algorithms used

Moving Pixels to New Positions

Calculating New Pixels

Symmetry

Calculation of the Mandelbrot Set

Dynamic Resolution

Autopilot

Threads

Future Plans

Timers

Time functions

Group functions

Timer functions

Emulator functions

Example main loop

Future Plans

Palettes and Images

Future Plans

Filters

Instance creation / destruction

Initialization

Calculation

Coordinate conversion

Filter removal

Filter registration

Future Plans

Fractal Formulae

Future Plans

User-Defined Formulae

Design Goals

Design

Implementation

Parser module

Evaluator module

Summary

Code

Example

Future Plans

Function Registry

Function description

Initializing the menuitem structure as a static variable

Dialog description

Modifying the registry

Querying registry

Future Plans

User Interface

Initialization

Main loop

Calling functions

Closing the library

Future Plans

Clone this wiki locally