New work on the Jiffle compiler

Jiffle is a scripting language for raster algebra. It can be used for stand-alone applications, or as the basis for image or map calculators (e.g. the JGrassTools Mapcalc module). If you haven't met Jiffle yet, take a look at the user guide and some of the previous posts about the language such as Jiffle meets Mandelbrot and Jiffle plays the Game of Life.

The Jiffle compiler is built on the fabulous ANTLR parser generator. To date, Jiffle has used ANTLR version 3 and many compilation tasks such as syntax checking, optimization and translation to Java sources involve Java code embedded directly within the ANTLR grammar files. It all works but it's messy, brittle and hard to follow.

We are now moving to ANTLR version 4 which encourages a very different approach with simpler, language-neutral grammars processed by visitors and/or listeners coded as ordinary Java classes. This promises to make the Jiffle compiler sources much easier to understand, maintain and extend.

For Jiffle users, few if any changes will be evident on the outside at first: the Jiffle language itself will stay the same and all existing scripts will still run. The high-level parts of the API for Java clients (e.g. the JiffleBuilder class) will also remain much as they are. But later on, the new compiler will make it easier to add new language features and extend the API.

Stay tuned...

Jiffle version 0.2.1 released

Version 0.2.1 of the Jiffle image scripting language is now available from the Maven Central repository. This updates Jiffle to depend on JAITools version 1.3.0.

If you haven't met Jiffle yet, take a look at the user guide and some of the previous posts about the language such as Jiffle meets Mandelbrot and Jiffle plays the Game of Life.

The sources for this version can be retrieved from the Jiffle Git repository (see the releases branch and the 0.2.1 tag):

  git clone https://jiffle.googlecode.com/git

Share and enjoy !

JAI-tools version 1.1.1 and Jiffle version 0.1.0 released

The JAI-tools team is pleased to announce the combined release of new versions of JAI-tools and Jiffle. This is the first release since Jiffle moved into a separate project with its own versioning (see previous post).

The new versions are now available from the Maven Central repository and mirror sites.

You can checkout the sources from:

http://jai-tools.googlecode.com/svn/tags/1.1.1

http://jiffle.googlecode.com/svn/tags/0.1.0

To search for particular changes of interest go to the issue tracker for each project.

Thanks to Andrea Aime and Daniele Romagnoli for their work on this release, and also Ian Turton and Manuel Bossant for contributions and bug spotting.

JAI-tools version 1.1.1

This is a minor release which includes bug fixes and improvements, but also some new features. Notable items:

• ROIGeometry now has more methods implemented and improved performance.
• Problems with clipping and setting rendering hints have been fixed in the DiskMemImageGraphics class.
• KernelFactory has been expanded and can now generate many standard kernel types including cosine, Gaussian, Epanechnikov and quartic.
• Improvements to the utility Swing widgets.
• A new CompareOp class for comparison of double and float values taking into account absolute or proportional tolerance.

Jiffle version 0.1.0

This is the first release of the Jiffle scripting language under its own version numbering. The new jars are jt-jiffle-language-0.1.0.jar and jt-jiffle-demo-0.1.0.jar.

The main change from the version that was included with JAI-tools 1.1.0 is support for user-defined coordinates. This separates the bounds and resolution of the processing area from those of the source and destination images. It means that within your Jiffle script, you can work with whatever type of coordinates are best suited to your application, e.g. geographic, proportional, or arbitrary cartesian coordinates. When running a script, CoordinateTransform objects are used to convert between user coordinates and pixel positions in each source and destination image.

The separation of processing and image coordinates can be handy even when you are working directly with pixel positions. You can use it to deal with non-overlapping source and destination images, or as a device to sub-sample or over-sample source images.

As well as the new coordinate support, there have been some small extensions to Jiffle's syntax and a general tidy-up of the code base and javadocs.

Share and enjoy.

Jiffle leaves home to grow up

Although it's usually the other way around (grow up then leave home) sometimes things don't turn out as planned...

For Jiffle, the scripting language developed as part of JAI-tools, what was originally planned was compatibility with the r.mapcalc raster algebra language used in GRASS GIS, but recently we decided that this was too limiting and it would be better to set Jiffle free and have its development driven purely by our brilliant ideas (plus the moderating influence of user feedback).

Like all great ambitions, this one quickly ran aground on the rocks of practical constraint. Being a module in a Maven-based project, Jiffle had the same version number as all of the other JAI-tools modules, but this didn't fit well with allowing Jiffle's syntax and code-base to be more fluid (ie. lots of changes breaking backwards-compatibility). So it was decided to separate Jiffle out from the JAI-tools project.

Jiffle now has its own site: http://code.google.com/p/jiffle/ and it's been re-versioned to 0.1.x to make it clear to users that substantial changes can be expected. Despite leaving home, Jiffle will retain its close relationship to JAI-tools, with the same project team developing both.

Unfortunately, this has created a certain amount of version chaos. At Maven Central you can find:

• jt-jiffle-1.1.0.jar (as part of the most recent JAI-tools release)
• jiffle-1.0.1.jar (from the previous release before the "jt-" prefix was adopted)
• And soon: jt-jiffle-language-0.1.0.jar (the new jar name being required to avoid future clashes with previous versions)

It's hard to see how we could have made it much more confusing.

Here's what to do:

• For JAI-tools version 1.1.0, use jt-jiffle-1.1.0
• With later JAI-tools releases, swap over to the most recent version of jt-jiffle-language

If you you use Maven as your build tool it will cut through much of this confusion for you because the dependency relationship between different versions of JAI-tools and Jiffle will be contained in each project's pom.xml file.

The next post will show off some of the new Jiffle language features to prove that all of this chaos has been worth it :)

Jiffle plays the Game of Life

After showing off with fractals in the last Jiffle demo, it seemed only natural to delve back in time for another classic to illustrate new features and uses of the language. And nothing could be more classic than John Conway's Game of Life: a cellular simulation with simple rules that can display exceptionally complex behaviour. If you're not familiar with Life, this Wikipedia article is a good place to start. You can also marvel at the compendious collection of Life patterns at LifeWiki:

The Java Swing program shown in the screen-shot above uses a Jiffle runtime object as a simulation engine to play Life. Two different Jiffle scripts are used: one which simulates a world with edges; and a second where the world is a toroid, ie. opposite edges of the image are joined to form a continuous surface. In both scripts the world is an image where an unoccupied location is represented by pixel value 0 and an occupied location by pixel value 1.

Here is the entire script for the world with edges:

       options { outside = 0; } 

       n = 0; 
       foreach (iy in -1:1) { 
         foreach (ix in -1:1) { 
           n += world[ix, iy]; 
         } 
       } 

       n -= world; 
       nextworld = (n == 3) || (world && n==2);

The expression world[ix, iy] accesses a relative neighbour location. For example world[-1, 1] would get the value of a pixel at (x-1, y+1) where x and y are the ordinates of the current pixel.

The two foreach loops use integer sequence syntax, startValue:endValue, to iterate over the 3x3 neighbourhood centred on the current pixel and count the number of occupied cells (those with a value of 1). The rules of Life are expressed only in terms of the number of neighbouring cells occupied, so we adjust the value of n by subtracting the value of the current pixel.

The options block at the top of the script sets a value to be returned for any neighbour positions that are beyond the bounds of the image. Without this option, the runtime object would throw an Exception at the very first pixel when trying to access the relative neighbour position world[-1, -1].

The final line of the script expresses all of the Game of Life rules in a single statement ! It uses naked conditional statements which return 1 or 0.

A second Jiffle script provides an alternative version of the simulation, where the image representing the world is treated as a toroid:

       n = 0; 
       foreach (iy in -1:1) { 
         yy = y() + iy; 
         yy = if (yy < 0, height() - 1, yy); 
         yy = if (yy >= height(), 0, yy); 

         foreach (ix in -1:1) { 
           xx = x() + ix; 
           xx = if (xx < 0, width()-1, xx); 
           xx = if (xx >= width(), 0, xx); 
           n += world[$xx, $yy]; 
         } 
       } 
 
       n -= world; 
       nextworld = (n == 3) || (world && n==2);

This script works with absolute rather than relative neighbour positions. These are indicated by the $ prefix. When a neighbour position is beyond an edge, it is adjusted to the corresponding position at the opposite edge. Note that we don't need the outside option in this script.

The Game of Life is an iterative simulation where the output for time t becomes the input for time t+1. To accomplish this, the demo program caches the runtime objects compiled from the Jiffle scripts, and uses them repeatedly with two images which are represented by the variables world and nextworld in the scripts. These images are simply swapped between source and destination roles at each time step as shown in this code fragment...

       activeRuntime.setSourceImage(WORLD_NAME, curWorld);
       activeRuntime.setDestinationImage(NEXT_WORLD_NAME, nextWorld);
       activeRuntime.evaluateAll(null);
       
       TiledImage temp = curWorld;
       curWorld = nextWorld;
       nextWorld = temp;

You can view and download the complete source code for this program from the JAI-tools web site.

Jiffle meets Mandelbrot

The Jiffle scripting language has been getting some new bells and whistles recently. While the idea is still to keep the language small and simple, by adding a few extra constructs it becomes much more flexible.

Above is the JiffleDemo application showing a script that uses two of these new constructs, scoped variables and loops, to generate a binary image of the Mandelbrot set. Below is the script itself (it is one of the examples distributed with JAI-tools).

The "init" block is where you declare variables that you want to remain in scope throughout processing. Jiffle calls these image-scope variables. Variables declared outside this block are termed pixel-scope, ie. their values are discarded after each pixel is processed. In the Java runtime class that the Jiffle compiler creates, the image-scope variables are class fields while the pixel-scope variables are local to the evaluate method called to process each destination image pixel. The runtime class is also provided with a getter method for the image-scope variables so you can retrieve them after running the script. You could use this, for instance, to count pixels that are in a certain value range.

The script below uses an until-loop (lifted from Ruby) for the iterative calculation. Jiffle also offers a while-loop and I'm musing about adding some kind of for-loop syntax as well.

/*
 * An example Jiffle script: draws a binary
 * image of the Mandelbrot set. Adapted from
 * C code at http://warp.povusers.org/Mandelbrot/
 *
 * Author: Michael Bedward
 */

/* We declare variables that we want to remain
 * in scope between pixels in the 'init' block.
 * The functions  width() and height() return
 * the dimensions of the destination area.
 */
init {
  MaxIter = 30;
  MinRe = -2.0;
  MaxRe = 1.0;
  MinIm = -1.2;
  MaxIm = MinIm + (MaxRe-MinRe) * height() / width();
  Re_scale = (MaxRe-MinRe)/(width()-1);
  Im_scale = (MaxIm-MinIm)/(height()-1);
}

/* Calculations performed for each pixel.
 * The functions x() and y() return current
 * pixel coordinates.
 */
c_im = MaxIm - y()*Im_scale;
c_re = MinRe + x()*Re_scale;

Z_re = c_re;
Z_im = c_im;

outside = 0;
n = 0;

/* Jiffle has an 'until' loop construct */
until (n >= MaxIter || outside) {
    Z_re2 = Z_re*Z_re;
    Z_im2 = Z_im*Z_im;
    outside = if (Z_re2 + Z_im2 > 4);
    Z_im = 2*Z_re*Z_im + c_im;
    Z_re = Z_re2 - Z_im2 + c_re;
    n++ ;
}

/* The variable 'result' represents the
 * destination image (you can use any name
 * you like in your own scripts).
 */
result = outside;

As an aside, I recall using much the same algorithm, though in FORTRAN, to generate Mandelbrot set images on an 80286 PC last century. Some people never change...

Images in a jiffy: speeding up Jiffle with Janino

Jiffle is a scripting language for raster algebra dreamed up by myself and Andrea Antonello. You can use it to create, combine and analyse raster (pixel) images. It's based on the r.mapcalc language for map calculations in the GRASS GIS program.

The idea of Jiffle is to let you concentrate on the interesting bits rather than having to write the incredibly tedious boiler plate code that is normally required to work with image data using Java. The image here of a simple trigonometric function was created with this script...

xc = width() / 2
yc = height() / 2
dx = (x()-xc)/xc
dy = (y()-yc)/yc
d = sqrt(dx^2 + dy^2)
outImg = sin(8 * PI * d)


The Jiffle parser, developed using ANTLR, converts a script like the one above into a tree representation of the expressions (Abstract Syntax Tree or AST). Up until now, running the script involved walking this tree multiple times (once per destination image pixel) and executing the expression like an interpreter. While this worked, it was much too slow to process large images.

Enter Janino, which advertises itself (quite accurately) as a "super-small, super-fast Java™ compiler". One of things you can do with Janino is to compile source and load the resulting bytecode in-memory. To apply this to Jiffle, I first replaced the ANTLR grammar for the run-time tree walker with one that translates an AST into a Java method body. For example, the script above is translated to this...

        double xc=_width / 2.0;
        double yc=_height / 2.0;
        double dx=(_x - xc) / xc;
        double dy=(_y - yc) / yc;
        double d=Math.sqrt(Math.pow(dx, 2.0) + Math.pow(dy, 2.0));
        writeToImage("out", _x, _y, _band, Math.sin(25.132741228718345 * d));

Next, I created a new interface JiffleRuntime and a template for an implementing class that looks like this...

import jaitools.jiffle.runtime.JiffleRuntime;

import java.awt.image.RenderedImage;
import java.awt.image.WritableRenderedImage;
import java.util.HashMap;
import java.util.Map;
import javax.media.jai.iterator.RandomIter;
import javax.media.jai.iterator.RandomIterFactory;
import javax.media.jai.iterator.WritableRandomIter;

public class JiffleRuntimeImpl implements JiffleRuntime {
    
    /* 
     * Note not using generics here because they are not
     * supported by Janino.
     */
    private Map images = new HashMap();
    private Map readers = new HashMap();
    private Map writers = new HashMap();
    
    private double _width;
    private double _height;
    
    public void evaluate(int _x, int _y, int _band) {
        // COMPILER_BREAK
        
        throw new UnsupportedOperationException("Method body to be provided by Jiffle compiler");
        
        // COMPILER_RESUME
    }
    
    public double readFromImage(String imageName, int x, int y, int band) {
        RandomIter iter = (RandomIter) readers.get(imageName);
        return iter.getSampleDouble(x, y, band);
    }
    
    public void writeToImage(String imageName, int x, int y, int band, double value) {
        WritableRandomIter iter = (WritableRandomIter) writers.get(imageName);
        iter.setSample(x, y, band, value);
    }
    
    public void setDestinationImage(String imageName, WritableRenderedImage image) {
        images.put(imageName, image);
        
        if (images.size() == 1) {
            _width = image.getWidth();
            _height = image.getHeight();
        }
        
        writers.put(imageName, RandomIterFactory.createWritable(image, null));
    }

    public void setSourceImage(String imageName, RenderedImage image) {
        images.put(imageName, image);
        readers.put(imageName, RandomIterFactory.create(image, null));
    }

}

The Jiffle compiler inserts the generated statements into the evaluate method of this class...

    public void evaluate(int _x, int _y, int _band) {
        double xc=_width / 2.0;
        double yc=_height / 2.0;
        double dx=(_x - xc) / xc;
        double dy=(_y - yc) / yc;
        double d=Math.sqrt(Math.pow(dx, 2.0) + Math.pow(dy, 2.0));
        writeToImage("out", _x, _y, _band, Math.sin(25.132741228718345 * d));
    }

Now we have the run-time class source as a String in memory, we compile it with Janino's SimpleCompiler class and retrieve the resulting executable bytecode as shown here...

        SimpleCompiler compiler = new SimpleCompiler();
        compiler.cook(runtimeSource);
        Class clazz = compiler.getClassLoader().loadClass(PACKAGE_NAME + "." + RUNTIME_CLASS_NAME);
        runtimeInstance = (JiffleRuntime) clazz.newInstance();

And voila ! The Jiffle script has now been compiled into a form that will run at the speed of the JVM, hundreds of time faster than the original tree walking approach.

Janino doesn't handle generic collections or var-arg method calls so some work-arounds were required in the parser grammars and Jiffle's run-time support classes to deal with this. For example, instead of generating this source...

double foo = JiffleFunctions.median(x1, x2, x3, x4, x5);

We change the median method to expect a Double array and have the compiler generate this...

double foo = JiffleFunctions.median(new Double[]{x1, x2, x3, x4, x5});