path: root/doc/xaosdev.texinfo

\input texinfo   @c -*-texinfo-*-

@c Use A4 paper - If you don't like that, remove the following 3 lines.
@iftex
@afourpaper
@end iftex

@setfilename xaosdev.info
@settitle A fast real-time interactive fractal zoomer --- hacker's guide
@dircategory Graphics
@direntry 
* XaoS: (xaosdev).               The fast real-time interactive fractal zoomer
                                 (developers documentation)
@end direntry


@ifinfo
@copyright{} 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.

@end ifinfo

@c %**end of header

@set VERSION    3.1.1
@set DATE       Feb 5, 2005

@titlepage

@title XaoS @value{VERSION}
@subtitle A fast real-time fractal zoomer --- hacker's guide

@author Jan Hubi@v cka
@tex
Dukelsk\'ych bojovn\'\i ku 1944 
@end tex
@*
390 03 T@'abor @*
Czech Republic

Email: @code{jh@@ucw.cz}

@value{DATE}

@page
@vskip 0pt plus 1filll
@vskip 0pt plus 1filll

@copyright{} 1997 @tex Jan Hubi\v cka 
@end tex

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.

@end titlepage

@c %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@node   Top, , (dir), (dir)

@ifinfo
@top XaoS @value{VERSION}
@flushright 1.0
A real-time interactive fractal zoomer
Hacker's guide
@value{DATE}
@end flushright

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.
@end ifinfo

@menu
* design::		Overview of the XaoS design
* driver::		Driver API description
* gui-driver::		Writing user interface driver
* eui::			Writing an external user interface
* ui-helper::		UI helper library
* xthreads::		XaoS thread library
* filters::		Filters
* algorithm::		Algorithm description
* timerlib::		The timer library
* registry::		XaoS function registry
* index::		Function command and variable index
@end menu

@node design, driver ,Top ,Top
@chapter 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.

@section Palette and image library

@findex image
@findex palette
The sources for this are in the directory @code{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 @code{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).

@section Filter library
Sources are available in @code{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.

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

@section Fractal library
Sources are available in @code{src/engine/}, headers in @code{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.

@section Zooming engine and other filters.
Sources are available in @code{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 @code{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).

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

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

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

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

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

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

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

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

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

@node driver, gui-driver ,design ,Top
@chapter Driver API description

To port XaoS successfully to some platform you need:

@itemize @bullet
@item
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 @code{compilers.txt} for more
information.
@item
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 @code{if}s 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 @code{if}s.

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 @code{-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.
@item
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:

@findex C256
@findex FIXEDCOLOR
@findex GRAYSCALE
@findex TRUECOLOR
@findex TRUECOLOR24
@findex TRUECOLOR32
@itemize @bullet
@item 8 bits per pixel with user definable palette @code{C256}, static palette @code{FIXEDCOLOR}, or static grayscale @code{GRAYSCALE}
@item 16 bits per pixel with arbitrary bits per color @code{TRUECOLOR}
@item 24 bits per pixel with 8 bits per color, arbitrary order @code{TRUECOLOR24}
@item 32 bits per pixel with arbitrary order of colors, where each color fits in exactly one byte @code{TRUECOLOR}
@item 1 bit per pixel bitmap, either least or most significant bit first
@end itemize

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 @code{dither.c}.)
@item
Some way to save images. By default XaoS uses @code{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
@code{.png}, contact me and I will show you how to add such support to XaoS (see
@code{png.c}).
@item
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 @code{xio}. See
@code{xio.h}, @code{xstdio.c}, and @code{xstdio_mac.h} for an example.
@end itemize

The ugly interface is designed to make writing new drivers as easy as possible.
Use the file @code{ui_template} when starting to write a new driver from
scratch. You need to write only a few functions, filling out the following
table:
@findex ui_driver
@example
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;
@};
@end example

@section Functions

@code{ui} uses the following functions to communicate with a driver:

@defun init
  Initializes the driver and returns 1 on success and 0 on failure.
@end defun
@defun getsize (int *@var{width}, int *@var{height})
  Returns the size of screen (or window) in x and y dimensions.
@end defun
@defun processevents (int @var{wait}, int *@var{x},int *@var{y}, int *@var{buttonmask}, int &@var{keys})
  Gets new keyboard/mouse events. Parameters are:
  @table @var
  @item 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.
  @item *x,*y
    Returns the current mouse coordinates.
  @item *b 
    Returns a mouse button bitmask of @code{BUTTON1}, @code{BUTTON2}, and @code{BUTTON3}.
  @item *k 
    Returns a cursor key bitmask:
    @table @code
    @item 1 
    @key{left}
    @item 2 
    @key{right}
    @item 4 
    @key{up}
    @item 8 
    @key{down}
    @end table
    @end table
    The function calls @code{ui_key} (ASCII character) and @code{ui_resize}
    if required. For special keys use @code{UIKEY_UP}, @code{UIKEY_DOWN}, etc.
    See @code{ui.h} for a complete list of these constants.

    In case of problems freeing/allocating inside @code{processevents} you may 
    call @code{ui_call_resize}, which calls resize later outside this function.
@end defun

@defun uninit
 Uninitialises driver---called before exit.
@end defun

@defun set_range (ui_palette *@var{palette}, int @var{start}, int @var{end})
This is the preferred way to set the palette (the other way is with
@code{set_color}). When @var{imagetype} is @code{UI_C256} (256 color with
palette) one of these two functions @emph{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 @var{start}
and @var{end} to colors defined in @var{palette}. @var{ui_palette} is array of
@var{ui_rgb} elements. @var{palette[0]} is the color of entry number
@var{start}. @var{ui_rgb} is an array of @code{char}.  @var{palette[0][0]} is
the red field of entry number @var{start}, @var{palette[0][1]} is the green and
@var{palette[0][2]} is the blue. @code{0} means black and @code{255} means full
intensity. Use @code{NULL} if your driver doesn't support this call.
@end defun

@defun set_color (int @var{r}, int @var{g}, int @var{b}, int @var{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 @var{init} parameter is
  set to 1 when this function is called for the first time on a given
  palette; @code{set_color} is then expected to free all color entries
  previously allocated. Use @code{NULL} if your driver doesn't support
  this call.
@end defun

@defun print (int @var{x},int @var{y}, char *@var{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
  @code{C256} mode you can rely on the first allocated color always being
  black and the second being white.
@end defun

@defun display (void)
  Displays current buffer on screen
@end defun

@defun alloc_buffers (char **@var{buffer1},char **@var{buffer2})
  Allocates two buffers that can hold a bitmap the size of the screen.
  Also sets the current buffer to @var{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).
@end defun

@defun free_buffers (char *@var{buffer1}, char *@var{buffer2})
  Frees allocated buffers.
@end defun

@defun flip_buffer (void)
  Flips buffers --- sets the current buffer to the other one.
@end defun

@defun flush (void)
  This function should be used by drivers with buffered output to flush
  those buffers. Other drivers should set it to @code{NULL}.
@end defun

@defun mousetype (int type)
   This function is used to change the mouse cursor. @var{type} has the
   following values:
   @table @code
   @item NORMALMOUSE
     This pointer is that usually displayed, while the UI waits for user
     input.
   @item 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.
   @item 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.
   @end table
   You should use @code{NULL} if your driver doesn't support this.
@end defun

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

@table @var
@item textheight, textwidth
  Width and height of your font
@item 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.
@item rmask, gmask, bmask
  These fields are used in truecolor modes to specify where each color is
  defined.
@item maxentries;
  Number of allocatable entries. Normally should be
  @var{palettestart}-@var{paletteend}
@item imagetype
  Defines the type of image. Should be one of the following values:
@findex UI_C256
@findex UI_FIXEDCOLOR
@findex UI_GRAYSCALE
@findex UI_TRUECOLOR
@findex UI_TRUECOLOR24
@findex UI_TRUECOLOR32
  @table @code
  @item 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.
  @item UI_TRUECOLOR
    32bpp truecolor mode
  @item UI_TRUECOLOR24
    24bpp truecolor mode
  @item UI_TRUECOLOR16
    16bpp truecolor mode
  @end table
@end table

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

@table @var

@item params
  You may define command line options for your driver.

  They are defined using a @var{params} structure like:
@findex params
  @example
  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*/
  @};
  @end example

  where every line is one parameter. The list ends with @code{@{NULL,0,NULL,NULL@}}.
  The first field is the option name.
  The second field is the parameter type:
@findex P_SWITCH
@findex P_NUMBER
@findex P_STRING
@findex P_FLOAT
  @table @code
    @item P_SWITCH 
    No parameter --- variable is just set to 1 if the option is supplied.
    @item P_NUMBER 
    Integer number
    @item P_STRING 
    String
    @item P_FLOAT 
    Floating point number (variable is float)
  @end table
  The third element is a pointer to a variable that is changed if the option is
  supplied. (For instance, it is @code{int*} for @code{P_NUMBER} or
  @code{P_SWITCH}.)
  The last element is help text displayed by @code{ui -h}.


@item width,height
  See @var{flags}. May be set to @code{0.0, 0.0} at the start.

@item maxwidth,maxheight
  See @var{flags}. May be set to 0,0 at the start.

@item @var{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:

  @code{ASYNC_PALETTE | RANDOM_PALETTE_SIZE}

  The following flag constants are supported:

  @table @code
@findex RANDOM_PALETTE_SIZE
@findex UPDATE_AFTER_RESIZE
@findex RESIZE_COMMAND
  @item 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.
  @item 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.
  @item RESIZE_COMMAND
    Some drivers (mainly the fullscreen ones) may ask the user for the size
    and color depth to use, in the function @code{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 @code{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.
  @end table

  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)
@findex SCREENSIZE
@findex PIXELSIZE
@findex FULLSCREEN
@findex RESOLUTION
  @table @code
    @item SCREENSIZE
     The @var{width}/@var{height} values specify the exact size of the
     screen/window in centimeters
    @item PIXELSIZE
     The @var{width}/@var{height} values specify the exact size of one pixel in
     centimeters. This is better for windowed environments, where the window
     size is often changed.
    @item FULLSCREEN
     The driver runs fullscreen. XaoS automatically uses the default screen size
     (29.0cm x 21.5cm)
    @item RESOLUTION
     The driver does not know the exact screen size, but knows the resolution
     used (in the @var{width}/@var{height} variables); XaoS automatically
     calculates pixel width using width = 29.0cm/maxwidth and height =
     21.5/maxheight.
   @end table
   Of course the default width and height can be changed by command line
   options. You may also use combinations like:
   
   @table @code
   @item SCREENSIZE | FULLSCREEN 
   The best for fullscreen drivers
   @item PIXELSIZE | RESOLUTION 
   The best for windowed drivers
   @item FULLSCREEN 
   For fullscreen drivers that have no idea about screen size...  
   @end table

   Do not forget to set the @var{width}, @var{height}, @var{maxwidth},
   @var{maxheight} fields if required.

@item gui_driver
   See the next section for description.
@end table


@section Registering the driver

Once you've done the above, you just register the driver in @code{drivers.c} and
you may compile :) You can use @code{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.

@node gui-driver, eui ,driver ,Top
@chapter 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:
@example
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);
@};
@end example

All functions have a @code{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 @code{setrootmenu} function draws the root menu according to the menu called
@code{name}. To get the menu fields you might use the following piece of code:
@example
#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)
   @}
@end example
Once the field is selected, call the function @code{ui_menuactivate(item, NULL)}
where @code{item} is a pointer to the @code{menuitem} record of the selected
field.

The @code{enabledisable} function is called when the checkbox or radiobutton
state is changed. The @code{name} parameter is the same as the
@code{item->shortname} of the changed field, so you need to search all the
menus, compare @code{name} to @code{item->shortname}, and if it matches, call
@code{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 @code{menu} function works similarly to @code{setrootmenu}, but displays a
popup menu.

The @code{dialog} function is called for dialogs. The function should look like:
@example
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.
@}
@end example
Once the dialog is filled by the user, @code{gui_driver} is expected to allocate
an array of union @code{dialogparam}:
@example
dialogparam *p = calloc (sizeof (*p), nitems);
@end example
and fill in the selected values. @code{p[i].dint} is used to pass an integer
value, or the number of a DIALOG_CHOICE selection, @code{p[i].number} is used
for floating point numbers, @code{p[i].dstring} for strings and filenames,
@code{p[i].dcoord[0]} and @code{p[i].dcoord[1]} for complex values.

The string values are expected to be in separately @code{malloc}ed chunks. Once
the array is filled, call @code{ui_menuactivate(item, p)}.

The function @code{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:
@example
#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);

@end example
Now you might use @code{lines} to draw the help. It is a pointer to the array of
structures:
@example
struct xshl_line @{
  int y;
  struct xshl_item *first;
@};
@end example
@var{y} is the position of the line from the beginning of the text, and
@var{first} is a pointer to the blocks of text on the line. The last line
contains a @code{NULL} pointer in the first section.

@code{first} is a linked list of @code{xshl_item} structures:
@example
struct xshl_item @{
  struct xshl_context c;
  char *text;
  int x;
  int width;
  struct xshl_item *next;
@};
@end example

You can draw @code{text} at position @code{x} (and @code{y} from the line
record) using the text style described by @code{xshl_context}:
@example
struct xshl_context @{
	  int flags;
	  char *linktext;
@};
@end example
@code{flags} has the same meaning as in the @code{getwidth}
section. @code{linktext} is the name of the next help page when the field has
the @code{XSHL_LINK} atribute.

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




@node eui, ui-helper ,gui-driver ,Top
@chapter 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 @code{-windowid} @var{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...

@section 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' @code{(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.

@section 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:


@itemize @bullet
@item Open the pipe
@item Disable the builtin GUI
@item 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)
@end itemize

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

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

To read the menu hierarchy, just add @code{-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
@code{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 @code{-print_menu root}.

Under the X Window System you also need to specify the @code{-windowid}; also
the @code{-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 @code{-nogui}
and @code{-print_menus} commands must be first for a simple reason: XaoS parses
its command line early in initialization. Some commands (like
@code{-print_menus}) should be processed at this time, while others (like
@code{-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 @code{-print_menus} on the
command line, it will queue @code{-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:


@example
xaos -nogui -print_menus -windowid <id> -share -pipe - @var{[other options]}
@end example

@section Parsing the menu structure

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

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

@example
menu "fractal" "Fractal"
@end example

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

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

The next few fields are @code{menuentry}-related. It has an entry type, which
could be @code{normal}, @code{radio} or @code{checkbox}. @code{radio} and
@code{checkbox} are followed by @code{on} or @code{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: @code{dialog},
wich specifies that the function has a dialog box, and
@code{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 @code{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:

@example
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
@end example

@section 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: @code{(@var{name})}. Once
``@code{)}'' is sent, the command is executed by XaoS.

Check-boxed functions has one extra parameter --- @code{#t} to enable them and
@code{#f} to disable. So if you want to enable the @code{autopilot} item, send:
@code{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 @code{(print_dialog
"@var{name}")}.  XaoS replies with a dialog specification very similar to the
menu specification.

This has the header @code{dialog} followed by the name of the function being
described. Then one dialog entry per line is sent, started by
@code{dialogentry}, followed by the question the UI should display. Next is a
type, which should be one of the following:
@table @code
@item integer
Integer number such as @code{123}
@item float
Floating point number such as @code{123.123}
@item string
String such as @code{"ahoj"}
@item keyword
String such as @code{'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.
@item inputfile
@item outputfile
Here the UI should display a file selection dialogs. With @code{outputfile} it
is also a good idea to check whether the file exists and ask the user if he
wants to overwrite it.
@item onoff
Boolean value (@code{#f}, or @code{#t})
@item complex
Complex value --- two floating point numbers such as @code{123.123 123.123}
@item choice
Choice between some keywords. The keywords are sent after @code{choice},
enclosed in @code{@{} @code{@}}.
@end table
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
@code{"@var{[prefix]}*@var{[extension]}"}.

Some examples:

@example
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

@end example

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 @code{#t} and @code{#f}. For instance:

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

@section 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:

@example
checkbox "name" on/off
radio "name" on/off
@end example

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:

@example
root "name"
@end example

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:

@example
menu "name"
dialog "name"
help "topic"
@end example

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

@section 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:
@deftypefn Function struct xshl_line *help_make (char *@var{command}, int @var{getwidth} (void *, int @var{flags}, char *@var{text}), int @var{width}, int @var{smallheight}, int @var{bigheight});
@end deftypefn
and you will receive a stream of text with coordinates describing where to
display the text into the shared window.

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

Please ask me for more details if necessary.

And thats all. Good luck with coding.

@node ui-helper, xthreads ,eui ,Top
@chapter 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.

@section initialization

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

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

For details about creating palettes see @code{ui.c} or ask me.

To create an image, call:

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

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

Then it is time to fire up the main library:

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

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

@example
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 */
    @}
@}
@end example
It can set @code{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:

@example
  uih_loadcatalog (uih, "english");
@end example

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

@section 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:

@example
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*/
  @}
@end example

@section Calling functions

The UI helper library has many functions declared in @code{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 @code{ui_helper} library is not reentrant, so you can't call most
of these functions from the @code{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:

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

@section closing library

This is done using: 

@example
  uih_freecontext (uih);
@end example

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

@node xthreads, filters ,ui-helper ,Top
@chapter 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:

@deffn Variable ethreads
This is set to 1 in the case that threads are enabled
@end deffn

@deffn Variable nthreads
Number of threads
@end deffn

It provides the following functions:

@deftypefn Function {void} xth_init (int @var{threads})
This function initializes the threading library (starts threads, sets
@var{ethread} to @code{1} and @var{nthreads} to @var{n}. @var{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 @code{nothread_} equivalents defined in
@code{xthread.h}.

Note that all threads are not interchangeable --- there is a main thread (the
one that called @code{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.
@end deftypefn

@deftypefn Function {void} xth_uninit (void)
This function un-initializes the thread library --- kills child threads and sets
@var{ethread} to 0 and @var{nthreads} to 1.
@end deftypefn

@deftypefn Function {void} xth_function (xfunction *@var{function}, void *data, int @var{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 @var{function} on all threads, including the control one, with the
following parameters: @var{data} --- the same as @var{data} passed to
@code{xth_function}, @var{taskinfo} --- pointer to a platform-dependent
@code{taskinfo} structure (defined in @code{xthread.h}), but must have at least
a field @code{n}, that holds the thread number (where the control thread is
numbered 0 and other threads are numbered in the range 1 -- @var{nthreads}).
The next two parameters are the range of images across which the function is
expected to work. @code{xth_function} is expected to divide @var{range} into
@var{nthreads} equal pieces and pass to each thread the start of a piece and the
start of the next piece (@var{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 @var{function} returns.

This function is called approx. 5--10 times per frame.
@end deftypefn

@deftypefn 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.
@end deftypefn

@deftypefn Function {void} xth_bgjob (xfunction *@var{function}, void *@var{data})
This function is expected to behave as follows: if there are any threads waiting
for orders, ask one of them to call @var{function} with similar conventions as
in @code{xth_function} except that the @var{range} parameters are set to 0.
Otherwise it starts function in the foreground, as usual.

This function is called once per frame.
@end deftypefn

@deftypefn Function {void} xth_nthread (struct taskinfo *@var{s})
This function should be used to determine the current thread number. Do not use
@code{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.
@end deftypefn

@deftypefn Function {void} xth_lock (int @var{n})
@end deftypefn
@deftypefn Function {void} xth_unlock (int @var{n})
Lock/unlock lock number @var{n}. At least @code{MAXSEMAPHORS} locks must be
available.
@findex MAXSEMAPHORS

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.
@end deftypefn

@findex MAXCONDS
@deftypefn Function {void} xth_sleep (int @var{n}, int @var{l})
Expected to atomically unlock lock @var{l} and sleep in queue @var{n}.  At least
@code{MAXCONDS} queues must be available.  After the function is woken up, lock
@var{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.
@end deftypefn

@deftypefn Function {void} xth_wakeup (int @var{n})
Wake up some thread from queue @var{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.
@end deftypefn

@deftypefn Function {void} xth_wakeall (int @var{n})
Similar to wakeup but wake up all threads.
@end deftypefn


@node filters, algorithm ,xthreads ,Top
@chapter 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
@code{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 @var{filteraction} structure, as follows::
@findex filteraction
@example
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);
@};
@end example
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
@var{name} field is a comparatively long description of the filter's name, such
as ``A random dot stereogram generator''. @var{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.

@section Instance creation / destruction

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

@findex filter
@example
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;
@};
@end example
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:

@deftypefn Function {struct filter *} createfilter (struct filteraction *@var{fa});

This function should be used to do the dirty work of instance creation and fill
out the @var{filter} structure. The only possibly interesting field is
@var{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
@code{getinstance} implementation that allocates such an additional structure
might look like:

@findex getinstance
@example
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);
@}
@end example

If nothing similar is required you can simply put @code{creatfilter} into the
@var{getinstance} field.

@end deftypefn

@code{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 @code{free} call. An implementation of such function should look
something like
:
@example
static void destroyinstance(struct filter *f)
@{
     destroyinheredimage(f);
     free(f->data);
     free(f);
@}
@end example
The meaning of @code{destroyinheredimage} will be described later.


@section 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 @var{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 @code{require} function. This function
is expected to look at the child's requirements it received as a parameter, fill
out its own @var{requirements} structure, and call the @code{require} function
of its parent filter.
@findex requirements
@example
struct requirements @{
  int nimages;
  int supportedmask;
  int flags;
@};
@end example
The @var{nimages} field should be set to 1 or 2. When it is 2, the parent filter
@emph{must} pass the image in two buffers (double-buffered). Note that if it is
1, the parent @emph{should} pass the image in two buffers, but is not required
to.

@var{supportedmask} is a mask giving the image types supported by the
filter. Valid image types are:
@findex C256
@findex FIXEDCOLOR
@findex GRAYSCALE
@findex TRUECOLOR
@findex TRUECOLOR24
@findex TRUECOLOR32
@table @code
@item C256
  A normal 8bpp image with palette
@item TRUECOLOR24
  A 24bpp truecolor image with 8 bits for each color.
@item TRUECOLOR16
  A 16bpp truecolor image
@item TRUECOLOR
  A 32bpp truecolor image with 8 bits for each color.
@item 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.
@item SMALLITER
  Similar to @code{LARGEITER}, but 8bpp.
@end table

@findex MASK1BPP
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 @code{MASK1BPP} for 8 bit images,
@code{MASK2BPP} for 16 bit and so on.

The final field in the @var{requirements} structure is @var{flags}. It's a mask
composed from the following constants:

@table @code
@item 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.
@end table
There are no more flags supported at the moment. The @code{require} function
should also save the child's @code{requirements} structure into
@var{filter->req} for later use by the initialize pass. The code for a
@code{requirement} function might look like
@example
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*/
@}
@end example
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 @code{initialize} function receives an @var{initdata}
structure:
@findex initdata
@example
struct initdata @{
  void (*wait_function) (struct filter *f);
  struct image *image;
  struct fractal_context *fractalc;
  int flags;
@};
@end example
@var{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. @var{image} is an image expected to be filled with an
image in the calculation phase. @var{fractalc} is a pointer to a structure that
will contain information about the fractal itself during calculation (formula
type and so on). @var{flags} is a mask of the following constants:
@table @code
@item 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
 @var{image} than in the previous initialization (since some filter before it in
 the queue was removed).
@end table
Inheritance is carried out using these functions:

@deftypefn Function void inhermisc (struct filter *@var{f},struct initdata *@var{i});

This function sets fields in the filter structure like @var{fractalc} or
@var{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:
@end deftypefn
@deftypefn Function int inherimage (struct filter *@var{f},struct initdata *@var{data}, int @var{flags}, int @var{width}, int @var{height}, struct palette *@var{palette}, float @var{pixelwidth}, float @var{pixelheight}) 
You should call this function in your @code{initialize} pass. It fills out
@var{image} and @var{childimage} in the @var{filter} structure, and prepares
@var{initdata} and @var{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 @var{flags} parameter is a mask of the following constants:
@table @code
@item IMAGEDATA
  Set if your filter requires data from the previous frame.
@item 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.
@item 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).
@end table
@var{width} and @var{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. @var{palette} is the palette of the image you want to pass;
set to @code{NULL} if the palette should be inherited from the parent's image
(as is usual).  @var{pixelwidth} and @var{pixelheight} give the physical size of
a pixel in centimeters; if set to 0 they are inherit from the parent's image.
@end deftypefn

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

Example implementation:
@example
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));
@}
@end example
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 @code{setfractalpalette} call, which has two
parameters --- the @var{filter} structure, and the new palette. When you pass
the child's palette as @var{palette}, the fractal's palette will be changed to
the child's. If you pass @code{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.


@section Calculation

The calculation is done using the @code{doit} function:

@deftypefn 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 @var{flags} are mostly undefined; only @code{INTERRUPTIBLE} is defined for
now, and @emph{that} is mainly for the zooming engine so I do not describe it
here. Nonetheless, the filter is expected to pass the @var{flags} to its
child. Finally, @var{time} is the time in milliseconds that expired since the
last @code{doit} call. It can be used to calculate the animation speed, perhaps
in an attempt to keep the speed constant.

@end deftypefn

Calculation loops return a bitmask composed of the following flags:
@findex ANIMATION
@findex CHANGED
@findex INEXACT
@table @code
@item ANIMATION
 Set if the filter performs some animation, and expects that its calculation
 function will be called again soon.
@item CHANGED
 Set if something changed in the output image (the usual case).
@item INEXACT
 This is enabled by the zooming engine in @code{INTERRUPTIBLE} mode in case the
 @var{time} was exceeded.
@end table

Most @code{doit} functions change the image. The @var{image} structure contains
following fields that might be significant to filters:
@findex image
@table @code
@item bytesperpixel
  Number of bytes per pixel (image depth).
@item palette
  Palette of image.
@item currlines
  Array of pointers to the beginning of each scanline in the image.
@item oldlines
  Like @var{currlines}, but for the previous image, when double-buffering is
  enabled.
@item nimages
  Set to 2 when double-buffering is active.
@item flipimage
  Pointer to a function that flips @var{oldlines} and @var{currlines}.
@end table

The @var{palette} structure contains the following significant fields:

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

To make writing calculation loops for different bit-depths easier,
@code{pixel8_t}, @code{pixel16_t} and @code{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 @code{cpixel_t}, and the code will be
compiled for every bitmap depth.  See the edge detection filter
(@code{src/engine/edge.c} and @code{src/engine/edged.c}) for implementation
details.


@section Coordinate conversion

The @code{convertup} and @code{convertdown} functions are used for converting
screen coordinates to a position in the fractal and back. @code{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 @code{convertup}
function.

@code{convertdown} is the reverse of @code{convertup} (going from parent to
child).

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

@example
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);
@}
@end example

@section Filter removal

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

In most cases, it should be left at @code{NULL}.

@section Filter registration

Once the @var{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
@code{src/ui-hlp/ui_helper.c}, add the filter to the @var{uih_filters}
structure, and increase @var{uih_nfilters}. Note that the order of filters in
@var{uih_filter} defines the order of the filters in the filter queue.

Then it is high time to start experimenting.

Good luck!
@node algorithm, timerlib, filters ,Top
@chapter 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:
   @itemize @bullet
     @item Saving Previous Pixels
     @item Approximation Algorithm
     @item Moving Pixels to New Positions
     @item Calculating New Pixels
     @item Symmetry
     @item Calculation of Mandelbrot Set
     @item Dynamic Resolution
     @item Autopilot
    @end itemize   

@section 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 @sc{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 @math{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 @math{xsize + ysize} calculations instead of
@math{xsize * ysize}. So the main loop in XaoS looks like this:
   @itemize @bullet
     @item Make approximations for rows
     @item Make approximations for columns
     @item Move old pixels to their new positions
     @item Calculate pixels for which there is no good approximation for
       their row
     @item Calculate pixels for which there is no good approximation for
       their column, but there is one for their row
    @end itemize

@section Approximation Algorithm

  @unnumberedsubsec 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 @math{xsize + ysize}
values, but if its speed is proportional to @math{O(n^2)}, it can be
slower than a whole recalculation of the image. Speeds of @math{O(n)} or @math{O(n * log(n))} are acceptable.

  @unnumberedsubsec 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
  (@math{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 @math{step / 2.}
This caused a considerable slowdown so the limit was returned to @math{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):
@example
        X1        X2        X3        X4        X5        X6        X7
O1 O2                    O3 O4 O5                   O6 O7 O8
@end example

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

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

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

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

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.

  @unnumberedsubsec 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 @math{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 @math{(4 * step)
* (4 * step)}. This means that the approximation is acceptable when
@math{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
@math{length < n} to make a guess at the length of @math{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, @math{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 (@math{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.

@section Moving Pixels to New Positions

Since XaoS is using the approximation algorithm the following table is
filled for every row/column:
   @itemize @bullet
     @item calculate
     @item oldpoint
     @item position
   @end itemize

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

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

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

@section 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.
   
@section 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:
@itemize @bullet
  @item Find middle row/column of uncalculated block. Priority is the size
    of the block (in floating point coordinates)
  @item Start function for left block and right block
@end itemize

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
@math{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.

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

@section SMP support
Since version 3.0 XaoS supports SMP. This is done using threads. Most of
XaoS routines should be threaded easily --- for example
@code{moveoldpoints} just divides image into @math{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 @math{x} and @math{y} approximations
simultaneously (using two processors). Another interesting algorithm to
parallelize is boundary trace; see the comments in
@code{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.

@node timerlib, registry,algorithm ,Top
@chapter 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)

@enumerate
@item
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.

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

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

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

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

@item
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
@math{x} moves in a faster way than calling move @math{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)
@end enumerate

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 @code{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)

@section The name of the game

The timer library operates with @dfn{timers}. They should be created, you can
measure time since last reset, pause them or set @dfn{handler} and
@dfn{interval}. But handler is not yet activated at the given interval. Since
timer library is not asynchronous, you must activate them yourself.

For activating @dfn{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 --- @code{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. @code{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 @code{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 @code{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 @dfn{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.

@section Time functions

@deftypefn 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.
@end deftypefn
@deftypefn Function void tl_sleep (int @var{time})
Sleep for the given @var{time}. Similar to @code{usleep} in @sc{POSIX}.
@end deftypefn
@section Group functions

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

@deftypefn Function tl_timer* tl_create_timer (void)
Create timer structure.
@end deftypefn
@deftypefn Function void tl_free_timer (tl_timer *@var{timer})
Free memory storage used by timer structure.
@end deftypefn
@deftypefn Function void tl_reset_timer (tl_timer *@var{timer});
Reset timer to current time (the time of last actication of @code{tl_update_time}).
@end deftypefn
@deftypefn Function int tl_lookup_timer (tl_timer *@var{timer});
Return time since last call of tl_reset_timer or last activation of handler.
@end deftypefn
@deftypefn Function void tl_set_interval (tl_timer *@var{timer}, int @var{interval});
@end deftypefn
@deftypefn Function void tl_set_handler (tl_timer *@var{timer}, void (*@var{handler}) (void *),void *userdata);
@end deftypefn
@deftypefn Function void tl_set_multihandler (tl_timer *@var{timer}, void (*@var{handler}) (void *,int),void *userdata);

Handler, multihandler and interval control functions
@end deftypefn


@deftypefn Function void tl_add_timer (tl_group *@var{group}, tl_timer *@var{timer})
Add timer to given group. A timer should be in only one group.
@end deftypefn
@deftypefn Function void tl_stop_timer (tl_timer *@var{timer})
@end deftypefn
@deftypefn Function void tl_resume_timer (tl_timer *@var{timer})
Stop and resume timer.
@end deftypefn

@deftypefn Function void tl_slowdown_timer (tl_timer *@var{timer},int @var{time})
The time in the timer is moved back to the given time.
@end deftypefn

@section Emulator functions
@deftypefn Function struct timeemulator *tl_create_emulator (void);
This function creates new a emulator --- you need to create one first before
emulating.
@end deftypefn
@deftypefn Function void tl_free_emulator (struct timeemulator *@var{t});
Destroy emulator's data.
@end deftypefn
@deftypefn Function void tl_elpased (struct timeemulator *@var{t}, int @var{elpased});
Move emulated time.
@end deftypefn
@deftypefn Function void tl_emulate_timer (struct timer *@var{t}, struct timeemulator *@var{e});
Set timer to the emulated mode; the passage of time is now controlled by the
emulator @var{e}. All other behavior of timer keeps unchanged.
@end deftypefn
@deftypefn Function void tl_unemulate_timer (struct timer *@var{t});
Disable emulated mode for the timer.
@end deftypefn
@section Example main loop

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

@node registry, index,timerlib ,Top
@chapter 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@footnote{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 @code{xmenu.c}, and the header is
@code{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.

@section Function description

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

@findex menuitem
@example
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;
@end example

@defvar menuname
Name of menu (or category) the function belongs in. The root of all categories
is called @code{"root"}. XaoS also uses an @code{"animroot"} when animation
replay is active. If you are adding a function, it is better to add it into some
subcategory like @code{"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.
@end defvar

@defvar key
@sc{ASCII} code of the hotkey that activates this function. Use @code{NULL} if
none.
@end defvar

@defvar name
Longer name of the function, used in the menu entry, or @code{xaos --help}
listing.
@end defvar

@defvar shortname
One-word name of function used in command language and other references to
the function.
@end defvar

@defvar type
Type of function --- this is @emph{not} the return type. @var{type} should be
one of the following constants:
@table @code
@findex MENU_SUBMENU
@item MENU_SUBMENU
   A submenu. This is not a function, but a name for the submenu. You can fill
   in the @var{key}, @var{name}, and @var{shortname}. The name of this new
   submenu is placed in the field @var{pparam}.
@findex MENU_NOPARAM
@item MENU_NOPARAM
   A normal function without any parameters. When activated,
   @var{function} will be called with a pointer to @code{uih_context} as its
   parameter.
@findex MENU_INT
@item MENU_INT
   This should be used to simplify entering of many similar functions (handled
   by just one universal function in the C code). The @var{function} is handled
   in the same way as @code{MENU_NOPARAM}, but also one integer parameter taken
   from @code{iparam} is passed in.
@findex MENU_STRING
@item MENU_STRING
   Similar to @code{MENU_INT} but uses a string instead of an integer.
@findex MENU_DIALOG
@item 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. @var{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 @code{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 @code{dialogparam} unions, wich contain
   one entry for each parameter. @code{dialogparam} is declared as follows:
@example
typedef union
  @{
    char *dstring;
    int dint;
    number_t number;
    number_t dcoord[2];
    xio_path dpath;
    void *dummy;
  @}
dialogparam;
@end example
@findex MENU_CDIALOG
@item 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 @var{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
   @code{uih_context} is @code{NULL}, since it is often called in the
   initialization stages (parameter parsing etc.)
@end table
@end defvar
@defvar flags
The @var{flags} are used to set additional information about the function:
@table @code
@findex MENUFLAG_CHECKBOX
@item 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 @var{control}, which returns @code{1} when enabled and
@code{0} when disabled.  In order to let external GUIs work correctly you also
need to call @code{uih_updatemenus("name")} every time the state of this
function changes.

In the scripting language, this adds a single parameter, either @code{#t} or
@code{#f}. The engine then calls the function only when necessary. When
@code{#t}, a dialog is requested; when @code{#f}, the function is called just as
@code{NOPARAM}. I.e. the dialog is displayed only when enabling the feature.

@findex MENUFLAG_DIALOGATDISABLE
@item MENUFLAG_DIALOGATDISABLE
Display dialog on disabling of this checkbox feature, instead of on enabling.
@findex MENUFLAG_RADIO
@item MENUFLAG_RADIO
Other features act like radio-buttons. Control functions in this case receive
the same parameter as is defined for @code{MENU_INT} or @code{MENU_STRING}
types, and is expected to return @code{1} when enabled and @code{0}
otherwise. You also need to call @code{uih_updatemenus} when the value is
changed. No special parameter is added in the scripting language.

@findex MENUFLAG_INTERRUPT
@item MENUFLAG_INTERRUPT
Interrupt current calculation when this function is called (used by functions
with cause recalculation of the screen)

@findex MENUFLAG_INCALC
@item MENUFLAG_INCALC
By default XaoS queues functions and calls them later when they are activated in
the calculation. This flag disables this feature.

@findex MENUFLAG_ATSTARTUP
@item 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.

@findex MENUFLAG_NOMENU
@item MENUFLAG_NOMENU
If set, the function will not be visible in the menu.

@findex MENUFLAG_NOPLAY
@item MENUFLAG_NOPLAY
If set, the function will not be available as a command in scripts (and therefore
won't be usable by external GUIs).

@findex MENUFLAG_NOOPTION
@item MENUFLAG_NOOPTION
If set, the function will not be available as a command line option.
@end table
@end defvar

@section 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 @code{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 @code{MENU_NOPARAM} function, use the following macro:
@defun MENUNOP (menuname, key, name, shortname, flags, function)
@end defun
Similar macros exist for other types too. They end in @code{CB} or @code{RB} for
check-boxed or radio-box functions. See @code{src/ui-hlp/menu.c} for a large
number of example definitions. They should look like this:

@findex menuitem
@example
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),
           ...
@end example

@section Dialog description
A dialog description is similar to a menuitem. It is an array of the following
structures:
@example
typedef struct dialog
  @{
    char *question;
    int type;
    int defint;
    char *defstr;
    number_t deffloat;
    number_t deffloat2;
  @}
menudialog;
@end example
It is terminated by an element with the @var{question} pointer set to
@code{NULL}.

The @var{question} contains the string the UI should display when it asks for
this field.

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

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

To write dialog structures, as with menus, use macros defined in @code{xmenu.h}
like:
@example
DIALOGSTR(question,default)
@end example
The definition should look like:

@findex menudialog
@example
static menudialog uih_viewdialog[] =
@{
  DIALOGCOORD ("center:", 0, 0),
  DIALOGFLOAT ("Radius:", 1),
  DIALOGFLOAT ("Angle:", 0),
  @{NULL@}
@};
@end example
@section Modifying the registry
@deftypefn Function void menu_add (menuitem *@var{item}, int @var{n});
Add an array of @var{n} items to the database.
@end deftypefn
@deftypefn Function void menu_delete (menuitem *@var{items}, int @var{n});
Remove an array of @var{n} items from the database.
@end deftypefn
@section Querying registry
@deftypefn Function menuitem* menu_findkey (char *@var{key}, char *@var{root});
Find item for given key. @var{root} is menu to start (submenus are searched
recursively).
@end deftypefn
@deftypefn Function menuitem* menu_findcommand (char *@var{name});
Find item for given short name.
@end deftypefn
@deftypefn Function char* menu_fullname (char *@var{menu}); 
Return a long name for a menu, given a short name.
@end deftypefn
@deftypefn Function menuitem* menu_item (char *@var{menu}, int @var{n}); 
Return the @var{n}th entry in the @var{menu}. Return @code{NULL} if that entry
does not exist.
@end deftypefn
@deftypefn Function int menu_enabled (menuitem *@var{item}, struct uih_context *@var{c}); 
Check whether the given item is activated (for check-boxed and radio-boxed
functions).
@end deftypefn
@deftypefn Function int menu_havedialog (menuitem *@var{item}, struct uih_context *@var{c});
Return whether this function has an associated dialog.
@end deftypefn
@defun menu_getdialog (@var{context}, @var{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).
@end defun
@deftypefn Function int menu_available (menuitem *@var{item}, char *@var{root});
Check whether an item is available as one of the entries of @var{root} (or it's
submenus)
@end deftypefn

@node    index,     , registry, Top
@c        node-name,    next, previous,        up
@unnumbered Index of functions, variables, types and constants

@printindex fn

@contents
@bye