© 1997 Jan Hubicka

Permission is granted to make and distribute verbatim copies of this manual provided the copyright notice and this permission notice are preserved on all copies.

XaoS 3.1.1
**********

A real-time interactive fractal zoomer
Hacker's guide
Feb 5, 2005

This manual contains documentation for those who are interested in studying and improving the XaoS sources or using them in other programs. It includes a description of the algorithm and documentation of those parts of XaoS that I think might be useful for others.

Overview of the XaoS design
***************************

XaoS is divided into several ``libraries'' (some of them have been merged together; nonetheless the conceptual divisions are there and they can be separated easily).

Understanding the design philosophy should help you to navigate in the sources. I also expect that much of the lower level stuff may be useful in other projects, since it is designed to be fairly generic.

So here is an overview, from the lowest level stuff to the highest.

Palette and image library
=========================

The sources for this are in the directory src/filter. 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).

Filter library
==============

Sources are available in src/filter. This library controls the process of image creation. It handles a queue of filters, where each filter modifies the image in some way. The filters at the beginning and end of the queue are special; the first filter is usually the actual fractal engine which creates the image, and the last filter is usually the user interface helper library.

Xthread library
===============

This library provides an interface to various multi-threading libraries; currently the BeOS, plan9 and POSIX implementations are available. It allows the running of various functions in parallel, and provides some synchronization primitives (semaphores). It is simple, but has all the functionality required for the XaoS engine.

Fractal library
===============

Sources are available in src/engine/, headers in fractal.h. This library contains the actual fractal calculation routines. It is governed by a fractal context, which contains information like the current formula, the seed (for julia sets), the palette, and so on.

Functions for calculating the various fractal types and various coloring modes are also available here.

Zooming engine and other filters.
=================================

Sources are available in src/engine/. This is the actual zooming engine filter. It is fairly independent of the fractal library, so it could possibly be used for zooming other stuff. (It has already been used for zooming large scale images containing maps of Hungary).

The file ui_helper contains the implementation of all filters not already mentioned, and a structure containing all functions exported from the filter to the user interface. One other terminal filter is implemented --- the Julia morpher. Other filters add special effects (such as motion blur), or do conversions (such as rotation or dithering).

Timer library
=============

This library provides many useful timing primitives (such as timers). It is used by some other programs too.

xio library
===========

This library aims to provide a unified, portable interface to the file system. Some strange systems (such as MacOS) have a very different filesystem API to UNIX; perhaps they don't represent filenames as a string, use special structures, or something; this library abstracts away from all that.

xshl library
============

Xshl stands for XaoS simple hypertext library. It contains a fairly universal engine parsing an `xshl' language, similar to HTML, with some additions and many restrictions. It can render text for both proportional and monospaced fonts, in various sizes.

help library
============

This is built on top of the xshl and xio libraries. It can read help files containing help chapters, can parse keywords in chapters, and so on.

xmenu library
=============

This is the XaoS function registry. All functions from UI-Helper library are registered in the registry. From this registry the menus, dialogs, command line options and scripting language are built.

Catalog library
===============

This is a library for handling message catalogs. It should read catalogs and convert keywords into an actual message.

PNG library
===========

This library provides a function for saving an image from the Image library to a file, in PNG format. Other formats could be added as well if required.

UI-helper library
=================

This library controls all the low-level stuff and provides a high-level interface to it. It has functions for playing animations, zooming/un-zooming and suchlike. It all the other libraries heavily. It doesn't implement functions for handling menus and such, but could be helpful for such implementations, because of the function registry database.

Ugly interface
==============

This is currently the only real user interface for XaoS (there is another, wich is used for rendering animations, but it is not a user interface as users understand the term). It is built above the UI-helper library and provides functions for drawing menus, dialogs and so on.  It has drivers for many platforms, and can be easily ported to others.

In the future, it should be quite easily extended to let drivers specify their own menu/dialog handling code; so it should be possible to give it a ``native'' look on each platform.

It can also operate in a mode where the GUI drawing routines are disabled; the function registry database is transferred through a pipe to an external program, which should build the menus and act as an external user interface, sending back commands in the scripting language (presumably representing things that the user has done). This provides another way to give a native look to the ugly interface, and could also be used to interface other scripting languages to XaoS.

The ugly interface has one serious limitation --- for historical reasons, it is coded to handle just one window (the rest of XaoS can probably do multiple windows, but this is untested), so in windowed environments it is impossible to open multiple menus with fractals. On the other hand, this limitation is not so important once external GUIs enter the picture, as they could just start multiple XaoS engines. This is also preferred because it brings extra robustness, multitasking and some other advantages. That's why I don't plan to remove this limitation yet.

Driver API description
**********************

To port XaoS successfully to some platform you need:

  * An ISO C compatible optimizing compiler. Note that an optimizing compiler is really required, since XaoS is coded to be a good target for optimizations and doesn't have many routines coded in assembly; so if you will use a bad compiler, you will notice drastic slowdowns (a slowdown of 10x or more). Some compilers have serious problems compiling XaoS; this applies to most DOS compilers (Watcom C, Borland C, Microsoft C) for instance.  They generate incorrect code or crash during compilation. I highly recommend using the GNU C compiler, but even some versions of GNU C have difficulty. Please read compilers.txt for more information.

  * A fast way to avoid division by zero/overflow and other floating point exceptions. XaoS is carefully coded to not crash in this case, but doesn't have any tests to avoid such situations; expect random results in such cases.  Many platforms provide a means to switch coprocessor into a mode where 1/0 produces Inf and so on. If there is no such means, try to use some kind of signal handler that will ignore such exceptions.

     The ``normal'' solution --- add ifs to avoid division by zero --- is almost impossible. Division is quite easy to check for, but other cases (such as overflows) are much harder. I don't think it is possible to avoid all crashes just by adding ifs.

     XaoS doesn't depend on IEEE arithmetic. The result in the sort of edge cases where IEEE makes a difference is mostly undefined. XaoS usually works well with compiler switches for inexact math enabled (such as -ffast-math in GCC), but, of course, there are no guarantees. For example on Alphas this is not true, since they usually generate exceptions in that case.

  * A text or graphics output device. If you only have a text output device you may use the AA driver, which renders fractals into high quality ASCII art. In this case you might want to skip this chapter, download AA-lib (http://www.ta.jcu.cz/aa) and read the porting chapter of AAlib manual. A graphics device must be one of:

       * 8 bits per pixel with user definable palette C256, static palette FIXEDCOLOR, or static grayscale GRAYSCALE

       * 16 bits per pixel with arbitrary bits per color TRUECOLOR

       * 24 bits per pixel with 8 bits per color, arbitrary order TRUECOLOR24

       * 32 bits per pixel with arbitrary order of colors, where each color fits in exactly one byte TRUECOLOR

       * 1 bit per pixel bitmap, either least or most significant bit first

     Please contact me if you have a different kind of device. Some modes (like mis-ordered truecolor modes) could be added really easily if required.  Note that mono/4/16 colors devices will probably never be supported internally by XaoS, since I expect they will be slower than 8bpp, so XaoS will internally work in 8bpp and then convert to 1/2/4bpp. Contact me if you want to write such a converter. (For bitmap one already exists --- see dither.c.)

  * Some way to save images. By default XaoS uses libpng, which is ported to many platforms, but there are many platforms where it isn't ported yet. If your system has some standard image format which is easier to handle than .png, contact me and I will show you how to add such support to XaoS (see png.c).

  * Stdio compatible library (this is a problem on the Mac and BeOS). XaoS has an abstract layer above stdio, so it can use other input/output libraries too. You could write another implementation of this layer, called xio. See xio.h, xstdio.c, and xstdio_mac.h for an example.

The ugly interface is designed to make writing new drivers as easy as possible. Use the file ui_template when starting to write a new driver from scratch. You need to write only a few functions, filling out the following table:

     struct ui_driver {
       char *name;
       int (*init)(void);            /*initializing function. returns 0 if fail*/
       void (*getsize)(int *,int *);	/*get current size..in full-screen versions
                                       i.e svga and dos asks user for it*/
       void (*processevents)(int,int *,int *,int *,int *);
                                     /*processevents..calls ui_resize,ui_key
                                       also returns positions of mouse..
                                       waits for event if first parameter is
                                       1*/
       void (*getmouse)(int *,int *,int *);
                                     /*returns current mouse positions*/
       void (*uninit)();             /*called before exit*/
       int (*set_color)(int,int,int,int);
                                     /*alloc palette color and returns number*/
       int (*set_range)(ui_palette *palette,int start,int end)
                                     /*Set palette range*/
       void (*print)(int,int,char *);/*prints text*/
       void (*display)();            /*displays bitmap*/
       int (*alloc_buffers)(char **buffer1,char **buffer2);/*makes buffers*/
       void (*free_buffers)(char *buffer1,char *buffer2);/*frees buffers*/
       void (*flip_buffers)(void);   /*prints text*/
       void (*mousetype) (int type); /*Change mouse cursor*/
       void (*flush) (void);         /*Flush current state to screen*/
       int textwidth;                /*width of text*/
       int textheight;		/*height of text*/
       struct params *params;        /*command line parameters*/
       int flags;
       float width,height;
       int maxwidth,maxheight;
       int imagetype;
       int palettestart,paletteend,maxentries;
       int rmask, gmask, bmask;
       struct gui_driver gui_driver;
     };

Functions
=========

ui uses the following functions to communicate with a driver:

 -- Function: init
     Initializes the driver and returns 1 on success and 0 on failure.

 -- Function: getsize (int *WIDTH, int *HEIGHT)
     Returns the size of screen (or window) in x and y dimensions.

 -- Function: processevents (int WAIT, int *X,int *Y, int *BUTTONMASK, int &KEYS)
     Gets new keyboard/mouse events. Parameters are:

     wait
          If 1, the function can block, waiting indefinitely for the next event, otherwise it just determines if something's already arrived. This is useful on multi-tasked OSes, where eating unnecessary CPU time on busy-waiting is discouraged.

     *x,*y
          Returns the current mouse coordinates.

     *b
          Returns a mouse button bitmask of BUTTON1, BUTTON2, and BUTTON3.

     *k
          Returns a cursor key bitmask:

          1
               left

          2
               right

          4
               up

          8
               down

     The function calls ui_key (ASCII character) and ui_resize if required. For special keys use UIKEY_UP, UIKEY_DOWN, etc. See ui.h for a complete list of these constants.

     In case of problems freeing/allocating inside processevents you may call ui_call_resize, which calls resize later outside this function.

 -- Function: uninit
     Uninitialises driver---called before exit.

 -- Function: set_range (ui_palette *PALETTE, int START, int END)
     This is the preferred way to set the palette (the other way is with set_color). When IMAGETYPE is UI_C256 (256 color with palette) one of these two functions must be used. In truecolor modes they are unused. If direct palette access is possible on your platform, define this function. The function is expected to set all color cells between START and END to colors defined in PALETTE. UI_PALETTE is array of UI_RGB elements. PALETTE[0] is the color of entry number START. UI_RGB is an array of char.  PALETTE[0][0] is the red field of entry number START, PALETTE[0][1] is the green and PALETTE[0][2] is the blue. 0 means black and 255 means full intensity. Use NULL if your driver doesn't support this call.

 -- Function: set_color (int R, int G, int B, int INIT)
     This is a secondary way to set the palette, that should be used at platforms w/o direct palette access (like X11 or static color schemes). It receives the RGB value of the color, and returns the index of the color cell with this color, or -1 if no more color cells are available. The INIT parameter is set to 1 when this function is called for the first time on a given palette; set_color is then expected to free all color entries previously allocated. Use NULL if your driver doesn't support this call.

 -- Function: print (int X,int Y, char *TEXT)
     Prints text to screen at position x/y. This function is a bit archaic (XaoS now uses its own functions drawing directly to the buffer in most cases), but in some cases --- initialization messages or calculation --- the functions are unusable, so we still need this primitive. In the C256 mode you can rely on the first allocated color always being black and the second being white.

 -- Function: display (void)
     Displays current buffer on screen

 -- Function: alloc_buffers (char **BUFFER1,char **BUFFER2)
     Allocates two buffers that can hold a bitmap the size of the screen. Also sets the current buffer to BUFFER1. Since version 2.1, this returns the scan-line size in bytes (usually the screen width) or 0 on failure. This is useful on systems that allocate a bitmap bigger than the window/screen (divisible by 4 or thereabouts).

 -- Function: free_buffers (char *BUFFER1, char *BUFFER2)
     Frees allocated buffers.

 -- Function: flip_buffer (void)
     Flips buffers --- sets the current buffer to the other one.

 -- Function: flush (void)
     This function should be used by drivers with buffered output to flush those buffers. Other drivers should set it to NULL.

 -- Function: mousetype (int type)
     This function is used to change the mouse cursor. TYPE has the following values:

     NORMALMOUSE
          This pointer is that usually displayed, while the UI waits for user input.

     WAITMOUSE
          This pointer is displayed when the UI is busy (perhaps the famous hourglass) or you may use that defined in ui_dos --- a Mandelbrot set.

     REPLAYMOUSE
          This pointer is displayed during replay. There should be none in fullscreen drivers, since a blinking mouse cursor during replay looks ugly. On windowed systems, disabling the mouse looks ugly, so it should be some funny cursor.

     You should use NULL if your driver doesn't support this.

Other information
=================

Some additional variables are also used to inform the ui library about the driver. All these values can be changed by init functions in case they were unknown beforehand.

textheight, textwidth
     Width and height of your font

palettestart, paletteend
     First and last palette entry that can be changed. You should use this to avoid changing entries reserved for the window system, UI objects, mouse, etc.

rmask, gmask, bmask
     These fields are used in truecolor modes to specify where each color is defined.

maxentries;
     Number of allocatable entries. Normally should be PALETTESTART-PALETTEEND

imagetype
     Defines the type of image. Should be one of the following values:

     UI_C256
          The classical 256 color with palette scheme used by most older graphics adapters. You should also use it for static-color schemes, but they are not well supported in current versions of XaoS.

     UI_TRUECOLOR
          32bpp truecolor mode

     UI_TRUECOLOR24
          24bpp truecolor mode

     UI_TRUECOLOR16
          16bpp truecolor mode

What follows is not required to get the driver working at first, so you may skip to registering driver on the first read and return here later.

params
     You may define command line options for your driver.

     They are defined using a PARAMS structure like:

            static struct params params[]={
              {"-mode",P_NUMBER,&defmode,
                "Select graphics mode(same number as in interactive menu)"},
              {NULL,0,NULL,NULL}  /*this MUST be last option field*/
            };

     where every line is one parameter. The list ends with {NULL,0,NULL,NULL}. The first field is the option name. The second field is the parameter type:

     P_SWITCH
          No parameter --- variable is just set to 1 if the option is supplied.

     P_NUMBER
          Integer number

     P_STRING
          String

     P_FLOAT
          Floating point number (variable is float)

     The third element is a pointer to a variable that is changed if the option is supplied. (For instance, it is int* for P_NUMBER or P_SWITCH.) The last element is help text displayed by ui -h.

width,height
     See FLAGS. May be set to 0.0, 0.0 at the start.

maxwidth,maxheight
     See FLAGS. May be set to 0,0 at the start.

FLAGS
     This variable says more about your driver. A good starting value is 0. But for the final version it is recommended to read the following carefully.

     Flags are uppercase constants and should be set as follows:

     ASYNC_PALETTE | RANDOM_PALETTE_SIZE

     The following flag constants are supported:

     RANDOM_PALETTE_SIZE
          States that the palette is randomly sized. This is used in X where the palette is shared between many programs. By default XaoS allocates all available colors up to 256. This is not very nice to other applications in X, so this flag states that that a random number of colors (in the range 8--256) are allocated.

          When this variable is off XaoS expects that the same number of colors is always available.

     UPDATE_AFTER_RESIZE
          Causes the screen to be recalculated and redrawn upon a resize, even if its size has not changed, in case the resize procedure destroys data in XaoS' buffers.

     RESIZE_COMMAND
          Some drivers (mainly the fullscreen ones) may ask the user for the size and color depth to use, in the function get_size. It would be nice to let the user change this parameter at runtime and force XaoS to reinitialize all its images. This is done with the ui_resize call

          In windowed drivers, this is called by external window-system events, but in fullscreen drivers you'll need a key or menu item for this. You could add this function directly into XaoS's function registry (see for example the GGI driver) --- it is useful mainly when you want to use a size selection dialog that is standard for your environment, or let XaoS use its default one. For example, see the SVGAlib or DOS driver.

     Screen/window size information:

     Xaos needs to know the exact physical size of displayed images. This is required for random dot stereograms and also for keeping the aspect ratio of fractals correct (do not make them wide in 640x200 resolution etc.) At least one of the following values should be defined (given in the order I prefer)

     SCREENSIZE
          The WIDTH/HEIGHT values specify the exact size of the screen/window in centimeters

     PIXELSIZE
          The WIDTH/HEIGHT values specify the exact size of one pixel in centimeters. This is better for windowed environments, where the window size is often changed.

     FULLSCREEN
          The driver runs fullscreen. XaoS automatically uses the default screen size (29.0cm x 21.5cm)

     RESOLUTION
          The driver does not know the exact screen size, but knows the resolution used (in the WIDTH/HEIGHT variables); XaoS automatically calculates pixel width using width = 29.0cm/maxwidth and height = 21.5/maxheight.

     Of course the default width and height can be changed by command line options. You may also use combinations like:

     SCREENSIZE | FULLSCREEN
          The best for fullscreen drivers

     PIXELSIZE | RESOLUTION
          The best for windowed drivers

     FULLSCREEN
          For fullscreen drivers that have no idea about screen size...

     Do not forget to set the WIDTH, HEIGHT, MAXWIDTH, MAXHEIGHT fields if required.

gui_driver
     See the next section for description.

Registering the driver
======================

Once you've done the above, you just register the driver in drivers.c and you may compile :) You can use ui_template.c as a driver template.

You may also look at the xthreads library description if you are porting XaoS to some SMP platform.

Please let me know if you want to start to code a driver.

Writing a GUI driver
********************

XaoS has a builtin GUI. Many operating systems have native GUI toolkits and XaoS default GUI might look strange there. To avoid this problem, you might write an external GUI program (see eui section) or write mappings from the XaoS GUI functions to the native ones. The advantage of an external GUI process is multitasking; XaoS is not thread safe and the GUI must be synchronous with calculation.  Also, the ugly interface code currently doesn't support multiple windows (although this should be solved in the future).  This solution is suitable mainly for those systems where two cooperating programs sharing one window is a problem (like Windows).

To write a GUI driver you need to fill out the following structure:

     struct gui_driver
     {
        void (*setrootmenu)(struct uih_context *c, char *name);
        void (*enabledisable)(struct uih_context *c, char *name);
        void (*menu)(struct uih_context *c, char *name);
        void (*dialog)(struct uih_context *c, char *name);
        void (*help)(struct uih_context *c, char *name);
     };

All functions have a uih_context parameter. You don't need to worry about its contents; just pass it to the functions that require it. This parameter is for multiple window support, which is not implemented yet.

The setrootmenu function draws the root menu according to the menu called name. To get the menu fields you might use the following piece of code:

     #include <ui.h>
     #include <xmenu.h>

     ....

     int i;
     menuitem *item;
     for (i = 0; (item = menu_item (name, i)) != NULL; i++)
        {
           if (item->type == MENU_SUBMENU) {
     	      /* This field is a submenu. You might call a function to
     	         construct the submenu here. item->shortname contains
     		 the name for the submenu.  */
           }
           /* Add menu field here.

              You might check flags here:
              item->flags&MENUFLAG_CHECKBOX
     	   field has a checkbox
              item->flags&MENUFLAG_RADIO
     	   field is part of a radio button group. In the current
                implementation, there is one radio button group per menu.

     	 in both cases you can call menu_enabled(uih, item) to see
     	 if the item is checked or not.

              item->name contains the field's text

     	 item->key contains a hotkey (a one letter string in the
              current implementation)
        }

Once the field is selected, call the function ui_menuactivate(item, NULL) where item is a pointer to the menuitem record of the selected field.

The enabledisable function is called when the checkbox or radiobutton state is changed. The name parameter is the same as the item->shortname of the changed field, so you need to search all the menus, compare name to item->shortname, and if it matches, call menu_enabled to get the new state. For radiobuttons, only enable events are noticed. Your code is expected to automatically disable all other radiobuttons in the same submenu.

The menu function works similarly to setrootmenu, but displays a popup menu.

The dialog function is called for dialogs. The function should look like:

     menuitem *item = menu_findcommand(name);
     menudialog *dialog = menu_getdialog(uih, item);
     int i;
     for(i=0; dialog[i].question; i++)
     {
        /* Construct dialog, where the left side contains labels with
         dialog[i].question, and the right side contains input entities based on the
         dialog[i].type. Dialog[i].type is one of the following:

         DIALOG_INT: integer value input. The default value is: dialog[i].defint
         DIALOG_FLOAT: floating point input value (long double, where available).
         Default value is dialog: dialog[i].deffloat
         DIALOG_COORD: complex value floating point input (two floats), default
         values are dialog[i].deffloat and dialog[i].deffloat2
         DIALOG_STRING: string input. Default value is dialog[i].defstr
         DIALOG_IFILE: input file
         DIALOG_OFILE: output file
              default mask is dialog[i].defstr
         DIALOG_CHOICE: choice between various strings.
              cast dialog[i].defstr to char ** to get a pointer to a NULL
              terminated array of choices.
     }

Once the dialog is filled by the user, gui_driver is expected to allocate an array of union dialogparam:

     dialogparam *p = calloc (sizeof (*p), nitems);

and fill in the selected values. p[i].dint is used to pass an integer value, or the number of a DIALOG_CHOICE selection, p[i].number is used for floating point numbers, p[i].dstring for strings and filenames, p[i].dcoord[0] and p[i].dcoord[1] for complex values.

The string values are expected to be in separately malloced chunks. Once the array is filled, call ui_menuactivate(item, p).

The function help is used to display help about a given topic. To implement it you could either convert XaoS help file to some native format, or use the xshl library to render the help page for you. To render an xshl page use:

     #include <xshl.h>
     xshl_line *lines;
     int getwidth (void *data, int flags, char *text)
     {
     	return width of text with given flags
     	flags is mask of the following:
              XSHL_BIG - large text
              XSHL_EMPH - emphasized text
              XSHL_MONOSPACE - monospaced text (typewriter)
              XSHL_LINK - line (should be underlined or suchlike)
              XSHL_WHITE
              XSHL_RED
              XSHL_BLACK - color of text (not very meaningful here)
              XSHL_RIGHTALIGN
              XSHL_CENTERALIGN - alignment of text

     }
     lines = help_make (name, getwidth, textheight, largetextheight);
     if (lines == NULL)
       lines = help_make ("main", getwidth, textheight, largetextheight);

Now you might use lines to draw the help. It is a pointer to the array of structures:

     struct xshl_line {
       int y;
       struct xshl_item *first;
     };

Y is the position of the line from the beginning of the text, and FIRST is a pointer to the blocks of text on the line. The last line contains a NULL pointer in the first section.

first is a linked list of xshl_item structures:

     struct xshl_item {
       struct xshl_context c;
       char *text;
       int x;
       int width;
       struct xshl_item *next;
     };

You can draw text at position x (and y from the line record) using the text style described by xshl_context:

     struct xshl_context {
     	  int flags;
     	  char *linktext;
     };

flags has the same meaning as in the getwidth section. linktext is the name of the next help page when the field has the XSHL_LINK atribute.

For an example of gui_driver, see the win32 driver code.

Writing an external user interface
**********************************

This part describes how to make an external user interface --- that is, a separate program which constructs a window with all menus and dialogs. It uses the XaoS engine to calculate the fractal as a separate process. This design brings many advantages --- the external GUI implementation could have a ``native look'' for given platform and could contain many extensions (perhaps multiple windows). Also all calculation is done while multitasking, so the user interface is usable even when the engine is busy.

The X Window System provides a way for programs to draw into others' windows --- the ``master'' program creates window the sub-window where it wants to put the fractal, then calls the engine with -windowid NUMBER_OF_WINDOW parameters. Instead of creating a new window, the engine uses uses the specified window. The most famous example of such cooperation is probably ghostscript/ghostview.

Other windowed environments probably provide similar means for for cooperation. In most others it will probably be implemented using shared memory, so it should work on most platforms, I expect.

Of course, you might also design the UI as a separate button box in another window, like most animation players, or ImageMagick do. In fact, the external GUI could be very similar in style to ImageMagick...

Basic concept
=============

The UI implementation has a function to disable its GUI functions.  Because of the function registry, all its menus and dialogs are described in a fairly simple database, which is also mapped to the Scheme-like scripting language. The external UI implementation can just translate the user's actions into this scripting language and send that through the pipe.

The commands, menus, and dialogs should be created automatically from the database, so the UI doesn't need to have special code for each XaoS feature. At the beginning it should use XaoS' (print_menus) command to force it to send information about the database, then build menus using this information.

For this you only need some equivalent to UNIX pipes, so again I expect it is doable on most platforms.

Starting XaoS as a slave process
================================

One of the first things the engine needs to do is to initialize XaoS in the right mode to work as a slave process. For this you need to do several things:

  * Open the pipe

  * Disable the builtin GUI

  * Read the menu hierarchy (this is optional --- GUI can also have all menus coded into it. But it is not recommended, since it will cause problems with adding new features in future)

Opening pipe is done via the -pipe option. It takes one parameter, the name of the FIFO you want to use. If you specify ``-'', XaoS will read input from stdin.

To disable the XaoS GUI use -nogui. This will disable all menus, dialogs and help text.

To read the menu hierarchy, just add -print_menus parameter and then parse XaoS's output. This will print the whole menu hierarchy. If you are building menus at the time they are selected, you might prefer to use the print_menu command, which prints just one menu without its submenus; its output could be immediately used for building a menu. The command takes one string parameter, the name the menu you want to print; i.e., to print the root menu use -print_menu root.

Under the X Window System you also need to specify the -windowid; also the -shared option is quite recommended. Otherwise in pseudocolor visuals XaoS will create its own colormap, wich will likely collide with the UI's colormap, and either XaoS or the UI will have wrong colors. If you have any idea how to avoid this, let me know.

You might also let the user specify some extra parameters from the command line, by simply adding those options to the end of the command line. The -nogui and -print_menus commands must be first for a simple reason: XaoS parses its command line early in initialization. Some commands (like -print_menus) should be processed at this time, while others (like -loadpos need a working engine. Such commands are queued and processed later, once the engine is initialized. XaoS never reorders commands; if an option that requires queuing is located before -print_menus on the command line, it will queue -print_menus too. This will cause the menus to be printed much later, slowing startup.

So the proper calling sequence for the user interface under X should look like:

     xaos -nogui -print_menus -windowid <id> -share -pipe - [OTHER OPTIONS]

Parsing the menu structure
==========================

The structure is printed menu by menu. Each menu contains a header, some entries, then endmenu. The listing from print_menus is terminated by endmenus.

The header starts with menu and then contains a menu identifier, and the menu's full name, e.g.

     menu "fractal" "Fractal"

Each entry which follows has its own line. It starts with a menu type, which should be submenu or menuentry.

submenu has a similar format to the header --- the full menu name, and an identifier.

The next few fields are menuentry-related. It has an entry type, which could be normal, radio or checkbox. radio and checkbox are followed by on or off specifying whether it is enabled or disabled by default. (The radio-buttons don't have explicit information about which group they belong to. For now I expect that each menu contains just one such group, so it is clear in any case.)

A set of flags should follow. Currently two flags are defined: dialog, wich specifies that the function has a dialog box, and dialogatdisable. By default, dialogs for check-boxed functions are displayed only when the checkboxes are enabled. The second flag reverses this behaviour. It is currently used for the mandelbrot function, which behaves in this way; when you disable it, the user is prompted for the Julia seed.

So a specification should look something like this:

     menu fractal "Fractal"
     submenu "formulae" "mformula"
     submenu "Incoloring mode" "mincoloring"
     submenu "Outcoloring mode" "moutcoloring"
     submenu "Plane" "mplane"
     submenu "Palette" "palette"
     menuentry "Mandelbrot mode" "uimandelbrot" checkbox off dialogatdisable dialog
     menuentry "Perturbation" "uiperturbation" checkbox off dialog
     menuentry "View" "uiview" normal dialog
     menuentry "Reset to defaults" "initstate" normal
     endmenu

Activating functions and dialogs
================================

Once the menu structure is built and the user selects some item, it should be activated. This is done by a simple command: (NAME). Once ``)'' is sent, the command is executed by XaoS.

Check-boxed functions has one extra parameter --- #t to enable them and #f to disable. So if you want to enable the autopilot item, send: autopilot #t

Radio-buttons don't have any such parameter, because disabling radio-buttons makes no sense.

If the item has a dialog enabled, the engine expects that the UI will make the dialog first, ask the user for values and then pass back a function with parameters. But first, the UI needs to know what parameters the function expects.  This is done by sending the command (print_dialog "NAME").  XaoS replies with a dialog specification very similar to the menu specification.

This has the header dialog followed by the name of the function being described. Then one dialog entry per line is sent, started by dialogentry, followed by the question the UI should display. Next is a type, which should be one of the following:

integer
     Integer number such as 123

float
     Floating point number such as 123.123

string
     String such as "ahoj"

keyword
     String such as 'ahoj. Keywords are mostly similar to strings, except that they can not contain spaces. They are used, for example, for specifying types of formulae. Strings are used for printing text and so on.

inputfile

outputfile
     Here the UI should display a file selection dialogs. With outputfile it is also a good idea to check whether the file exists and ask the user if he wants to overwrite it.

onoff
     Boolean value (#f, or #t)

complex
     Complex value --- two floating point numbers such as 123.123 123.123

choice
     Choice between some keywords. The keywords are sent after choice, enclosed in { }.

The last information on the line is the default value, in the same format as the examples above. For files, the default value is in the format "[PREFIX]*[EXTENSION]".

Some examples:

     customdialog "uiview"
     dialogentry "center:" complex 0.000000 0.000000
     dialogentry "Radius:" float 0.000000
     dialogentry "Angle:" float 0.000000
     enddialog

     dialog "load"
     dialogentry "Filename:" inputfile "fract*.xpf"
     enddialog

     customdialog "color"
     dialogentry "Color" choice {white black red }white
     enddialog

To activate a function, send a command consisting of the function name followed by a sequence of parameters, mapped one-to-one to dialog box fields, in the same order as those fields. The parameters have the same format as in the above examples; checkbox fields return #t and #f. For instance:

     (uiview 0 0 0.5 0)
     (load "text.xpf")
     (color 'white)

Synchronization
===============

In some cases, XaoS can change radio-box and check-box values itself (when user presses a key, or loads some file, for instance). All such changes are sent to the GUI so that it can update what the user sees correspondingly. They are sent to standard output in the following format:

     checkbox "name" on/off
     radio "name" on/off

Your GUI code should parse this and change its menus when necessary.

XaoS's menus can contain multiple distinct trees. In some cases (like when animation replay is active) the root of the menu structure should change. To indicate this to the GUI, XaoS sends a command:

     root "name"

Also, the user can press keys which normally display menus, dialogs or help. If XaoS has the keyboard focus, it will receive these instead of the GUI. XaoS sends commands to indicate this:

     menu "name"
     dialog "name"
     help "topic"

All these commands should be taken into account by the GUI, or could be ignored (not recommended!)

help
====

XaoS's help is in a simple hypertext language. In order to simplify its parsing, I've made xshl and help libraries. Making a help window with these libraries should be quite easy; just call the help function:
 -- Function: struct xshl_line *help_make (char *COMMAND, int GETWIDTH (void *, int FLAGS, char *TEXT), int WIDTH, int SMALLHEIGHT, int BIGHEIGHT);

and you will receive a stream of text with coordinates describing where to display the text into the shared window.

The command parameter is the help topic. The getwidth function returns the width of a given piece of text. width is the width of the window, smallheight is the height of the small font, and bigheight is the height of the big font.

Please ask me for more details if necessary.

And thats all. Good luck with coding.

UI-helper library
*****************

UI helper library takes care of all of XaoS' engine functions and features and provides a higher level API which is quite easy to understand. If you want to write a completely new user interface (a replacement for the ugly interface --- not just new bindings for native menus or external user interfaces) or you want to use the XaoS engine in your program, you will probably want to use this library.

Its API has many calls and features. This section gives a brief overview of its calls. Please ask me for details.

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 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.

XaoS thread library
*******************

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.

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 filters are the user interface implemented in ui_helper.c and the zooming engine implemented in zoom.c. Active filters are kept in a queue --- in the beginnning there are just two filters here (zoom and ui), 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.

Then it is high time to start experimenting.

Good luck!

Algorithm description
*********************

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 stuff 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.

SMP support
===========

Since version 3.0 XaoS supports SMP. This is done using threads. 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 paralellize 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.

The timer library
*****************

Timer library is a library originally written for timing in XaoS; but I found it useful in many other programs (like demonstrations, games, animation players and other stuff that needs to be timed). So you should read this description and possibly use it in your application and save some coding time.

There are many ways to design a timed application (such as a game)

 1. Read user input, move baddies, display and loop again.

     This way has one disadvantage; the speed of game depends on the speed of the computer.  This was acceptable in olden times where the only processor was the Z80 :) but now with a wide variety of hardware with widely differing speeds such a loop is unacceptable.

 2. Read user input, measure time since last loop and calculate step for baddies, move baddies for set step, display and loop again.

     This way fixes the problem with speed. But moving baddies just for calculated step, that should differ a much is quite complex, usually introduces complex calculation, floating/fixedpoint math and other unnecessary stuff that makes program long and introduces many bugs.

 3. Set a fixed framerate that is high enough to make the game smooth but low enough to do the whole internal loop in time. The internal loop then looks like this: read user input, move baddies, display, measure time spent in loop, sleep until next frame.

     This is quite a popular scheme but has another disadvantage --- game can not be designed to use the whole CPU power, since on slower computers internal loop would longer than is available for one frame, so the game will run slowly again.

 4. To take away disadvantage of previous method, many games time just the moving of baddies and user input. Other stuff like displaying should be done in the `untimed' rest of the time. In DOS games moving and user input is often done in an asynchronous interrupt and drawing runs as the main loop. This solves the case where the drawing of the game takes a significantly longer time than the moving of baddies. This is quite common so this scheme works well.

 5. The previous scheme still has one problem --- since the timer interrupt works asynchronously, there could be many race conditions: if moving takes a longer time than the time reserved for it, the computer can crash. So this scheme should be enhanced into a synchronous one with exactly the same result but avoiding the problem with race conditions:

     Read user input, measure the time spent by the loop and calculate how many simulated frame interrupts were activated since last activation: if zero, sleep until simulated interrupt, move baddies as many times as required, display, and loop again.

     This is a combination of 4 and 3 and seems to be the most comfortable way for writing games, but since the main loop is now quite complex many games don't do that.

 6. there is still one small problem. Method 5 expects that moving takes a significantly smaller time than displaying. This may not be the truth. A simple work around is to write a moving routine that should move for x moves in a faster way than calling move x times. This is often possible, and makes extension to scheme 5 easy. This scheme allows you to use a very large maximal framerate (say 100FPS) and to have the same results as method 2 (which is the maximally exact method)

As you can see, designing the main loop isn't so easy. This is just a very simple example: a more advanced application might want to move one set of baddies at one framerate and another at a different framerate. This requires two such timings. Another complication is that there are many different ways to measure time exactly on different platforms. Under Linux you can measure using gettimeofday, but under DOS this is exact to just 1/18 of second and thats too low for smooth animation, and so on.

That's why I decided to design a portable easy to use timer library, that makes it easy to implement all methods described above, combinations of them, and much more.  During the design I took care of the following things: quality of timing, how easy to use it is, speed, portability and to minimise unexpected situations (like race conditions in asynchronous interrupts and so on)

The name of the game
====================

The timer library operates with timers. They should be created, you can measure time since last reset, pause them or set handler and interval. But handler is 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);
     }

XaoS 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, but also for authors of drivers, who can use this to add new driver dependent functions into XaoS's menu. The external user interface is also based on the registry.  The main idea behind external user interfaces (currently one for Tcl/Tk and Gtk is under development) is this: XaoS transfers its registry to the interface (using asimple description language). The user interface starts XaoS in its window and builds menus and dialogs based on the registry. Then, once user selects some function, the user interface creates a command in XaoS' scripting language and sends it back to XaoS' engine.

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)