David Madore's programs

Contents

Programs are listed roughly in reverse chronological order.

• Contents
• Decide the satisfaction of an intuitionistic formula on a Kripke frame
• Compute an animation of accelerating to the speed of light
• Compute images of the sphere and the hyperbolic plane
• Compute images of Kerr black holes
• Compute projections of 4-polytopes
• Unicode Map for Android
• Mandelbrot fractal generator
• French calendar generator
• wipemem
• Rotating rings
• Crossword puzzles generator
• Computation of Moonshine coefficients
• arc4gen
• A socket manipulation program
• Psychedelic icosahedra generator
• Testris
• oggdump
• Gregorian calendar script
• An unfinished crypto package
• Superstrip
• ftpd-BSD
• A sort of VPN (Ethernet-over-UDP)
• A secret sharing program
• A Public Domain deflate implementation
• A MIDI writing library
• A MIDI to DSP synthesizer
• The Book of Infinity
• SIMPLE
• XLetters
• XLaby

Decide the satisfaction of an intuitionistic formula on a Kripke frame

I refer to this Wikipedia page as well as this SEP page for background definitions: this program uses a SAT-solver (by default, CryptoMiniSat) to evaluate whether a given inituitionistic propositional formula holds over a given finite (transitive) Kripke frame. The code is here on GitHub and as an example it was used to generate this summary table (see also this MathOverflow answer). CC0 license.

Compute an animation of accelerating to the speed of light

I've been asked to provide the program that was used to compute this video of a simulation of what one would see while uniformly accelerating up to 99.93% of the speed of light in 100s, illustrating the Doppler effect, aberration of light and time dilation (see the description under the video for more information, and see also this blog post in French). So here is the program (it's a Perl script, with very few comments, that requires ImageMagick and probably only runs under some kind of Unix/GNU/Linux system; also, it only computes the animation frames as .png files: creating the video from there is up to you): get the source here on my FTP site. Public Domain.

Compute images of the sphere and the hyperbolic plane

This program was written with the specific purpose of computing the frames this video illustrating different projections of the sphere and the hyperbolic plane and the parallel between them (see the video itself and this blog entry for more).

Get the program here for the sphere and here for hyperbolic plane on my FTP site. Each one is a single .c file: it's uncommented but compilation options should be fairly self-explanatory (the program takes a single argument, a real number modulo 1, giving the time parameter in the video; it produces a PPM image file). Public Domain.

Compute images of Kerr black holes

This program, in standard C99, computes a view of a Kerr black hole by raytracing its geodesics using first integrals of motion.

For some example images and videos that were produced with this program, and some explanations as to what these images mean in the first place, see this page.

Get the program here on my FTP site. It's a single .c file: read the comments at the beginning (and the previously mentioned page) for compilation and usage instructions. Public Domain.

Compute projections of 4-polytopes

This program, in Perl, is an attempt to visualize the 4-dimensional regular polytopes, especially those with a large number of edges (the 120-cell and the 600-cell), by viewing them as tesselations of the 3-sphere (e.g., the 120-cell is a tesselation of the 3-sphere by 120 regular dodecahedra: this is possible only because the 3-sphere is curved—regular dodecahedra cannot tile ordinary Euclidean space). The videos produced by this program can be seen on this YouTube playlist (or in higher quality here). Some mathematical comments are made in this blog post (in French). Let me just mention here that the views are computed by performing a gnomonic projection of the 3-sphere onto Euclidean 3-space (centered where the observer is), which works because the gnomonic projection preserves alignment, and preserves angles at the center of projection. The edges in the hemisphere containing the camera (the “cis” hemisphere) are displayed as textured 3D tubes, whereas those in the other hemisphere (the “trans” hemisphere) are displayed as thin red lines (in reality they should appear as tubes in a kind of revers perspective, getting larger the further away they are, but this is both too complicated to draw and too confusing to view).

Get the program here on my FTP site. It's a single .pl file: read the comments at the beginning for usage instructions. Public Domain.

Unicode Map for Android

Moved to its own page (so I can more easily create a link to it from the app's about popup).

Mandelbrot fractal generator

I wrote this after playing with fraqtive and being upset that I couldn't zoom beyond the limit of double-precision floating point real numbers. Its interface is quite primitive, it doesn't have the nifty bells and whistles fraqtive has, it will only compute the (standard, quadratic) Mandelbrot set, but it does have two nice basic features: arbitrary precision (“deep zoom”) thanks to the GMP library and support for multiple processors/cores. It has both a batch mode (generate a single PNG image) and an interactive mode, selectable at compile time. Also, it's Public Domain: if it breaks, you get to keep both pieces.

For some example images and videos that were produced with this program (and also some explanations as to how the colors are chosen), see this page.

Get the program from the misc/mandel/ directory on my FTP site. It's a single .c file: read the comments at the beginning for compilation and usage instructions. Public Domain.

French calendar generator

This is a simple Perl script, using Cairo (and Παν語), to generate pretty PDF color calendars (in French) such as this one, with French holidays on them, phases of the Moon, seasons (twelve a year, aka signs of the zodiac), geeky stuff like Julian dates or ISO week numbers, and a very primitive iCalendar format parser (which basically can just read the output of Korganizer). It should be pretty easy to adapt for another country. You'll need Astro::MoonPhase to use it.

Get the program here on my FTP site. It's a single .pl file: read the comments at the beginning for usage instructions. Public Domain.

wipemem

This is a multiboot executable (for Intel x86) which does something extremely stupid: it wipes the computer's memory and then reboots. I used this because I needed to clear the ECC bits on my RAM prior to boot (and for various reasons I didn't want to use the BIOS to do it); now that Linux has a CONFIG_MEMTEST option, it has probably become utterly useless. However, this program can still serve as an example of how to write a primitive multiboot executable.

Get the program from the misc/wipemem/ directory on my FTP site. It's tarball with a Makefile. Public Domain.

Rotating rings

This program (of which there is an OpenGL wrapper) or perhaps (I can't quite remember which is which) its older version (also with an OpenGL wrapper) was used to compute various pretty videos of rings turning inertially: number 1, number 2, number 3 and number 4 (cf. also a related video of Poinsot polhode). More physical explanations (in French) are on my blog here and there, but the bottom line is that there is no force acting on the rings, it's an experiment in purely inertial movement of a complex solid.

There isn't much explanation as to how to use this program, so you'll have to figure it out by yourself if you're interested. Public Domain.

Crossword puzzles generator

This program generates a crossword puzzle (square) grid whose position of black squares is predefined—actually computed as a solution of the chess queens puzzle. It works fairly well provided you have a good dictionary file (by default it reads /usr/share/dict/words, but that's generally not good because it doesn't contain all two-letter words and distinguishes between upper- and lowercase). See also my blog post on this subject (in French).

Get it here on my FTP site. It's a single .c file: read the comments at the beginning for usage instructions, but you'll probably have to modify it in various ways before use (to change WIDTH and HEIGHT, to decide placement of black squares, etc.). Public Domain.

Computation of Moonshine coefficients

A Python program to compute the first coefficients of the Moonshine functions (McKay-Thompson series) (to complete the Online Encyclopedia of Integer Sequences) by using the action of generalized Hecke operators (or “replicability”). John McKay pointed out to me that the approach I use is very inefficient. Precomputed data is here.

Get it here on my FTP site. It's a single .py file: read the comments at the beginning for some explanations as to how it works. There is also a companion program for computing just the j invariant (and precomputed data here). Public Domain.

arc4gen

A self-standing ARC4 generator which can be used for various purposes (in a memory test, for example, or for CPU stress-testing). See my blog post on this subject.

Get it here on my FTP site. It's a single .c file: read the comments at the beginning for compilation and usage instructions. There is also a Debian package. Public Domain.

A socket manipulation program

A simple program to manipulate sockets under Unix (possibly Linux-specific, though). Initially I wrote this because netcat had no IPv6 support. Now I strongly recommend the wonderful socat program, however.

Get it here on my FTP site. It's a single .c file: read the comments at the beginning for compilation and usage instructions. Public Domain.

Psychedelic icosahedra generator

The CGI program which generated the image on the left, which is not a fractal but looks like one: it's actually a color plot of the icosihedral invariant function iterated twice (composed with random homographic functions). More explanations can be found in my blog post concerning this program.

Get it here on my FTP site. It's a single .c file: should be trivial to compile—however, it's a CGI, so if you want to use it in other ways (e.g. to save the image in a file) you'll need to modify it yourself. Public Domain.

Testris

Everyone who's played Tetris knows that feeling that the computer is purposefully offering the wrong pieces. This program makes that feeling true: the computer actually does try to be nasty and give you pieces that will annoy you (it does a minimax search a few levels deep, while trying to preserve a semblance of equal distribution of pieces; sometimes it really gives a random piece, though); the score function isn't good, however. There is also a game of Pentris, which is the obvious generalization of Tetris (pieces are dropped at random without trying to be nasty, but it's still much harder than Tetris). Written in Gtk+2 and could serve as an example program for it, but it's a bit ugly unfortunately.

Get it here on my FTP site (and here for Pentris). It's a single .c file: read the comments at the beginning for compilation and usage instructions. Public Domain.

oggdump

Tries to do a low-level dump of packets in an Ogg format file (for Vorbis, Speex and Theora contents, selectable at compile time). I didn't check recently to see whether API changes hadn't broken everything.

Get it here on my FTP site. It's a single .c file: read the comments at the beginning for compile-time configuration directives. Public Domain.

Gregorian calendar script

The source file of a CGI script to compute a Gregorian solar and lunar calendar (such as this one). See my page on calendars for more explanations. Get it here on my FTP site. It's a single .py file—however, it's a CGI, so if you want to use it in other ways (e.g. to save the calendar in a file) you'll need to modify it yourself. Public Domain.

An unfinished crypto package

I had started coding a number of (symmetric) cryptographic primitives (block ciphers and hash functions, and some trivial OpenPGP stuff like ASCII armor) with the intention of making them available in the Public Domain under a uniform coding standard and API convention. I didn't get much written, but there might still be some useful stuff there (there are working implementations of Blowfish, Twofish, MD5 and SHA1 and a minuscule portion of OpenPGP).

Get it here on my FTP site. It's a messy tarball with no explanations whatsoever, so you'll have to sort it out. Public Domain.

Superstrip

This was written as a birthday present for a friend who likes his programs lean and mean: it takes an ELF file (only ELF32, however: ELF64 support was initially intended, but never implemented) and drastically removes any sections not mapped in memory. This will destroy dynamically linked executables, but statically linked ones will be stripped to a much greater extent than the strip utility does.

Get it here on my FTP site. It's a single .c file: read the comments at the beginning for compilation and usage instructions. Public Domain.

ftpd-BSD

From the end of '99 up to about the end of 2000, I maintained a (somewhat popular) Linux port of OpenBSD's FTP server (this maintainership was then briefly taken over by W. L. Estes, who released one more version, numbered 0.3.3). As you can probably guess by the dates involved, this program is now completely obsolete, it probably has more security holes than a pound of Swiss cheese, and should no longer be used. If you have need for a fast and secure (and free) FTP server, I suggest using vsftpd, which is released under the GNU General Public License.

All versions of ftpd-BSD are archived in the ftpd-BSD/ directory on my FTP site (version 0.3.3 is in the contrib/ subdirectory). License is BSD.

A sort of VPN (Ethernet-over-UDP)

This program uses the Linux TUN/TAP device to implement a sort-of VPN. I used this at a time when I didn't have a fixed IP address. Get it here on my FTP site. It's a single .c file: read the comments at the beginning for compilation and usage instructions. Public Domain.

A secret sharing program

An implementation of Shamir's “secret sharing” algorithm. That is, this program will let you take a secret file (and a number of pieces of random data of the same size) and split it into N (anything up to 255) pieces such that any M (anything up to N) among them can be used to reconstruct the secret, but less than M will give absolutely no information on the secret. This might be useful to entrust a secret (e.g., key escrow) to a number of friends whom you trust collectively but not all individually. Note that there is no protection against certain types of attack (such as a shareholder revealing an incorrect version of his share to gain knowledge of the others' shares). Also, command-line syntax is a bit awful.

Get it here on my FTP site. It's a single .c file (probably very portable, i.e., should work under just about any OS): read the comments at the beginning for usage instructions. Public Domain.

A Public Domain deflate implementation

This is more a toy than a serious program (it was written to prove a concept in a quine), but it performs deflate (aka gunzip) format decompression (in an utterly non-robust way: e.g., it doesn't even read the CRC). It's not a program, merely a set of routines. Get them here on my FTP site. It's simple .c file. Public Domain.

A MIDI writing library

This is a set of routines to write MIDI files from C programs, also with Guile (Scheme) bindings. It comes with a couple of examples (two of Bach's preludes from the well-tempered clavier, in C major and D major, BWV 846&850, which can also be found on my MIDI files page) to demonstrate how one can write a MIDI file from Guile.

Note that Guile's interface is very fickle, so the Scheme bindings have broken several times. Last time I fixed this was in 2007, maybe this has broken again, I don't know.

Get the library (and accompanying examples) from the midiwrite/ directory on my FTP site. It's tarball with a Makefile. Public Domain.

A MIDI to DSP synthesizer

This is to Timidity as a raft is to an ocean liner: it converts a MIDI file to DSP data (in this case, raw data), in other words, it “plays” MIDI files. But this program uses no patches, only very trivial synthesizers, so it sounds awful (though this can be quite funny, actually). But it could be useful to scavenge for MIDI reading routines or something of the sort.

Get it here on my FTP site. It's a single .c file: read the comments at the beginning for compilation and usage instructions. Public Domain.

The Book of Infinity

The Book of Infinity, or jistae beuzi zhdakakepo, is a CGI trap for web spiders which do not conform to the robots.txt standard (or various similar exclusion patterns): it presents an infinite (or virtually infinite) number of Web pages, with fixed contents, for them to crawl. An example is currently at http://www.eleves.ens.fr/cgi-bin/infinity/.

Get the generating program from the infinity/ directory on my FTP site (the working version is the one called infinity.tar.gz: the ones called newinfi-date.tgz were attempts at a full rewrite which never saw the day). The code states that it's under the GNU General Public License, but I hereby override this and place it in the Public Domain.

SIMPLE

SIMPLE Is a Macro Processing Language Element (why element? because I needed something to stand for the ‘E’ and I couldn't think of anything better): it's a macro language, not entirely unsimilar to m4 (but with the important difference that it handles strings of tokens rather than strings of characters) plus a vague syntactic feel of HTML and a vague semantic feel of Scheme. It's probably not good for much (except writing obfuscated code?) and it's certainly inefficient. But it does come with a rather extensive documentation. In fact, the documentation is possibly more interesting than the language itself because it provides a rather detailed explanation as to what a macro processing language is and how it works; the code might be of pedagogical interest to illustrate how one can write a simple interpreter in C.

SIMPLE is now in an abandoned state and will no longer be maintained. But it doesn't seem to have bitrotten yet.

Get the implementation from the simple/ directory on my FTP site. It's tarball with a Makefile generated by automake and other nasty things. The code states that it's under the GNU General Public License, but I hereby override this and place it in the Public Domain.

XLetters

XLetters (catch falling words) is a game for the X Window System to practice your typing skill. The goal is to type the falling words before they reach the bottom. I wrote this with Péter Horvai.

It is now in an abandoned state and will no longer be maintained. I believe it still works, though. A newer version (but possibly also abandoned), with some i18n support, has been developed by Adrian Daerr: you can find it over here.

Get my version from the xletters/ directory on my FTP site. It's tarball with a (shudder!) IMakefile (beware! the tarball extracts in the current directory). GNU General Public License.

XLaby

XLaby (or X Labyrinth — the aMAZEment) is a labyrinth game for the X Window System that is played directly with the mouse pointer (that is, the walls of the maze block the mouse pointer: this is done with a fun but nasty hack with an invisible window). It is a pure Xlib program. I wrote this with Péter Horvai.

It is now in an abandoned state and will no longer be maintained. I believe it still works, though. But it have a number of things which are perhaps not really bugs but at least pretty nasty features (one being the way it tries to keep its window on top—something it has to do for the hack to work).

Get it from the xlaby/ directory on my FTP site. It's tarball with a (shudder!) IMakefile (beware! the tarball extracts in the current directory). GNU General Public License.