Cyrus Harmon's new completely useless blog



posted by cyrus in Lisp


Work continues on CLEM (Common-Lisp Egregious Matrix), my matrix math package for common-lisp. CLEM now has a bunch of macros which generate type-specific methods for various matrix operations so that I can do fast, non-consing matrix math operations like addition, multiplication, etc... CLEM uses the MOP to define a standard-matrix-class which serves as the meta-class for matrix classes. This allows one to define typed matrix classes as subclasses of matrix, with class attributes stored in the instance of the metaclass. So now we have matrices for {u,s}b-{8,16,32}, fixnum, integer, single-float, double-float, float, real, complex, number, and even t, although this last one is probably suspect.

In addition to the matrix types and the standard matrix operations (add, subtr, scalar multiply, matrix multiply, hadamard product, abs, log, etc...), aggregate operations (min, max, variance, sum), CLEM supports discrete convolution, affine transformation and a couple different types of interpolation, morphological operations (dilate, and erode), and thresholding. Most of these are relatively non-consing, although there are probably a few cases that need to be re-written in the new macro scheme.

Overall, it seems to work, but it is rather slow to compile and results in large fasl files. this shouldn't be too big of a problem, as I'd rather have a fast matrix package that took a while to compile than a slow package that compiles quickly.

Speeds are decent. I approach naive C algorithms and get to within a factor of 10 for highly-optimized matrix multiplication hand-coded in assembly. More benchmarking and further attention to things like the size of the blocks for the blocked matrix multiply would probably be a good thing.


Using CLEM, I've developed a trivial image representation/manipulation package. I should probably follow the lisp tradition of calling this trivial-image except that this isn't really trivial, as it requires CLEM. I've thought about trying to abstract away the core matrix stuff from CLEM into a package that works on arrays, and then trivial-image could use that (trivial-matrix?), but I'm getting sidetracked. ch-image supports images of a few types including ub8, rgb8 and argb8. Adding additional types should be straightforward and I hope to work on this soon.


ch-image is nice, but rather useless if you can't get images into and out of it. This is where ch-imageio comes in. ch-imageio does the conversion between either files in various formats, or from the results of other file reading packages that load the image files into their own format. Currently, ch-imageio supports the following: 1) reading and writing JPEG via the cl-jpeg library, 2) reading and writing TIFF files via libtiff using interfaces defined by gcc-xml-ffi, and 3) writing PNGs using Zach Beane's SALZA library.


gcc-xml-ffi generates FFI definitions from C (and C++ code, sort of) using gcc-xml-ffi. Currently, it spits out sb-alien definitions, although the original incarnation did UFFI. In theory, other backends, like CMUCL's alien interface and CFFI should be fairly trivial, but I haven't gotten around to it yet. UFFI isn't really adequate here as it doesn't support callbacks.


To facilitate generating xml files from gcc-xml and for generating common-lisp FFI declaration files from gcc-xml-ffi, I've made some extensions to asdf. I've also aped the SBCL asdf extensions for dealing with unix-dsos. This is a straightforward thing that everybody seems to do, but the less-obvious part, for me, was how to package them up in such a way that these extensions can be used by other asdf systems. ch-asdf was my attempt at solving this and allows me to add :unix-dso components without having to redefine what a unix-dso is and what is load and compile methods are in every asd file. Also, I can declare a component as a gcc-xml-c-source-file and the right things happen. Dependencies are sort of tracked, but there are a couple places where things break down. In any event, it makes writing asdf systems for packages that use gcc-xml-ffi and unix-dsos much easier.


tiff-ffi uses gcc-xml-ffi (and ch-asdf) to wrap the libtiff library. There are also some rather trivial glue functions that help facilitate things a bit. ch-imageio uses this to read and write TIFF files.


carbon-ffi allows one, in theory, to develop native Mac OS applications using SBCL. This sort of works and I have some screenshots of simple apps. I've even built "package"-style apps that allow for double-click launching. The negatives are that this is Carbon only (no Cocoa) and that in order to make this work one needs to use some undocumented Apple API functions. This proved to be a huge pain as getting this to work properly exposed some issues with SBCLs stack alignment where we were not properly aligning the stack on a 16-byte boundary, which was making AltiVec rather unhappy.


Similar to the carbon-ffi, this is an FFI wrapper for quicktime. This also suffered from the stack alignment issue, but these are now fixed. Now one can use the QuickTime API from SBCL directly to make and read movies, etc... I havent't tried the GUI stuff (QT movie playing functionality, e.g., but it should work).


I have implemented a version of the congealing algorithm in common-lisp. This uses clem and the various image stuff to learn a set of transforms that bring a stack of images into registration and can learn the shape of the item represented in the stack of images.


I have begun to connect SBCL up with R so that I can evaluate R expressions from common-lisp using the R C API and can get the results back to lisp. Next steps are to have a representation of lisp data objects in R and vice versa so that I can, for instance, call lisp functions from R and to connect up the R plotting stuff so that I can make nice plots from SBCL. This is an area where a clean common-lisp API that wraps the R graphing APIs might be a nice thing.


ch-photo is a library based around FFI definitions to the dcraw package to read NEF and DNG files (come to think of it, this should be rolled into ch-imageio, but that hasn't happened yet). In addition, ch-photo contains some scripts for importing RAW files and for organizing them into file system heirarchies based on date of import and file type.


fftw-ffi is a wrapper for the fftw (Fastest Fourier Transform in the West) library. In addition to the FFI stuff, there are routines to translate data between ch-image and fftw compatible representations so that one can use fftw to do ffts of images in ch-image.

SBCL stack alignment issues

In order to get carbon-ffi and quicktime-ffi working properly, I had to fix some bugs with stack alignment on ppc. Thanks to Gary Byers for pointing out the bug after I was at wits end with bizarre results coming back from quicktime due to misaligned stack data being munged by altivec (without complaints). These have no been fixed and everything seems to be OK here.

callback fixes

The SBCL developers have been working on adding callbacks to SBCL. The initial ppc port had a number of bugs that caused problems with non-32-bit arguments, long longs, mixing arguments of different sizes, etc... Raymond Toy fixed a bunch of these problems for CMUCL and I ported these over to SBCL. After the initial round of fixes, there were some more problems with how the arguments got pulled off of the stack in the lisp trampoline, but these have been fixed as well. These patches have not yet hit the tree, but hopefully this will happen after the 0.9.8 release.

SBCL sb-alien field alignment issues

Finally, in order to make the carbon-ffi and quicktime-ffi packages work properly, I had to deal with the fact that some of the MacOS toolbox data structures use a bizarre alignment scheme that is a holdover from the m68k days. The bad news is that a lot of these are core structures for things like graphics and IO. In order to support these weird alignments, Apple's hacked up version of GCC has some pragma directives that take care of the alignment issue. Fortunately for me, someone else must have been having similar problems as the CVS versions of gcc-xml started dumping out the offset of structure members. Now that the quasi-compiler was giving me this information, I had to hack up SBCL's alien interface to allow me to use it to specify non-standard alignment of struct elements. This works and now we can properly use these funky MacOS structures.

Ok, that's the overview. One of the main missing pieces is documentation. I need to go back in and document all of this stuff soon. Perhaps that will be my first New Year's Resolution: I well document as much or more code than I write this year.

Happy New Year,