Connelly - Technical

Allegro 'libgif' animation library

2009-07-07T02:27:00.000-07:00

From 2001, an Allegro library for loading GIF animations as a BITMAP pointer that automatically animates (due to an installed timer callback routine). Simplifies animation to the point of:

BITMAP *bmp = load_gif(filename, 0);
...
draw_sprite(screen, bmp, x, y);    /* BITMAP automatically changes with time. */

(Source)

The original code is by Paul Bartrum. My changes are in the public domain. Thanks to Marco Antônio for helping me find my own code...

forkmap, threadmap

2008-07-23T14:59:00.000-07:00

I have an 8 core machine, so vanilla Python increasingly annoys me by running roughly 200*8 times slower than optimized C code (I use OpenMP), rather than 200 times slower than C.

To use more cores, I occasionally use these parallel map functions in Python:

threadmap spawns a number of threads equal to the number of cores, and distributes work across threads. forkmap requires Cygwin, Mac, or Unix, and does the same thing with fork() and pipe(), basically to get around GIL restrictions in regular Python. Probably a better solution is to use a Python implementation such as IronPython which doesn't have the GIL, but the FFIs for CPython libraries seem spotty in these other Python implementations.

Merely using parallel map() functions is rather limiting; OpenMP-style syntax should probably be added to Python at some point, after the GIL is removed. (As the number of processor cores goes to infinity, either the GIL will be removed or Python will become irrelevant, as languages with similar syntax and fine-grain locking will take over.)

There are libraries which implement parallelism by using spawn() instead of fork() to get Windows compatibility without Cygwin, but I couldn't figure out how exactly these libraries were spawning new copies of my code, so due to lack of documentation on this point I used other solutions.

C++ foreach

2008-03-15T19:14:00.001-07:00

I can never remember the C++ for-each loop syntax. Thus, a helper macro I use:

#define for_each(type, it, L) for (type::iterator (it) = (L).begin(); (it) != (L).end(); ++(it))

If L has type T, usage is:

for_each(T, it, L) {
  printf("%d\n", (*it));
}

If you're only using gcc, one can use __typeof__ [1] to simplify this.

RK45 in Python

2007-11-04T09:28:00.000-08:00

Runge-Kutta 4th and 5th order adaptive ODE integrator. Generally the scipy integrators will be easier to use, unless you specifically need RK45.
(Code)

Filter numpy images with FFT, Python

2007-09-12T21:53:00.000-07:00

Generic linear filter support is not currently built into the Python Imaging Library. This module lets you filter a numpy array against an arbitrary kernel:

>>> I = numpy.asarray(Image.open('test.jpg'))
>>> I = filter(I, [[-1,0,1],[-2,0,2],[-1,0,1]])/8+128
>>> Image.fromarray(numpy.uint8(I)).show()

The Fast Fourier Transform (FFT) is used. The FFT routine included with numpy isn't particularly fast (c.f. FFTW [1]), and in any case using the transform isn't as efficient as applying the filter naively for small filter sizes. Also, for separable kernels (e.g. the Gaussian kernel), it is often faster to perform two 1D convolutions in sequence. However, for large images and filters, using an FFT for convolution is often faster than other approaches. (If an image and filter contain a total of N pixels, then this algorithm takes O(NlogN) time, which is the fastest known time complexity algorithm for the general problem.) Public domain.

Update: A number of image filtering operations are provided in numarray (in the module numpy.numarray.nd_image), such as filtering, image morphology, distance transforms, and segmentation; see [2].

(Source)

framecap - Capture camera input with Allegro, C++

2007-06-04T15:51:00.000-07:00

Requires OpenCV, Allegro, and pthreads. Captures frames from a webcam. Usage:

CAPTURE *cap = create_capture();
BITMAP *bmp = capture_frame(cap);

Use capture_frame_nb to capture a frame in nonblocking mode (a NULL pointer is returned if no frame is available). Should work on Mac OS X, Linux, Windows; only tested on Windows.

(Source)

pfm - Read/write 1 and 3 channel PFM files

2007-04-30T18:44:00.000-07:00

PFM files are mxnx1 or mxnx3 arrays of floats. C++ code to read/write the format (public domain).
(Source)

OpenCV camera and AVI input

2007-04-04T16:37:00.000-07:00

To convert a video to a format that OpenCV can read:

  $ mencoder in.avi -ovc raw -vf format=i420 -o out.avi

This is necessary because OpenCV uses platform specific video libraries, and the intersection of their supported formats is DIB/I420/IYUV. To capture input from a camera or an AVI file, use the following C++ code: [1]. To capture frames in a nonblocking manner in Python, use: [2] with Gary Bishop's cvtypes [3].

Burrows-Wheeler transform in Python

2007-04-03T11:24:00.000-07:00

def bwt(s):
  s = s + '\0'
  return ''.join([x[-1] for x in
         sorted([s[i:] + s[:i] for i in range(len(s))])])

def ibwt(s):
  L = [''] * len(s)
  for i in range(len(s)):
    L = sorted([s[i] + L[i] for i in range(len(s))])
  return [x for x in L if x.endswith('\0')][0][:-1]

The Burrows-Wheeler transform [1] is an invertible mathematical transformation which tends to clump related sequences of data together; hence it is useful as a pre-pass for some compression algorithms. The BWT domain in the above code excludes the null character; to include the null character, modify the transformation to also output the row of sorted([s[i:] + s[:i]...]) on which s occurs, then in IBWT simply return this row after the for loop. The Python code above is not particularly fast.

How to put a video on the Web

2007-04-01T17:12:00.000-07:00

Install FFMPEG [1], use ffmpeg -i in.avi out.swf, then place <embed src="out.swf" width="400" height="300" loop="false" quality="high"></embed> in your HTML. Optionally, use the -s argument after -i in FFMPEG to change the resolution. If you want playback controls, output to a .flv file instead, download FlowPlayer [1], and modify their example HTML to point to your .flv video.

Ubuntu Linux postinstall notes

2007-02-17T09:24:00.000-08:00

After installing an operating system, there are always a zillion changes I have to make to get the operating system operational. I'm new to Linux, so I thought I'd post up a list of changes I made after installing Ubuntu to help out others. These are mostly basic changes such as enabling all software packages, choosing a fast repository, mounting FAT32 drives, making Ctrl+Alt+Del bring up a task manager, installing multimedia software, changing the system DPI, trying to disable the trash feature, and adding an Open Terminal option to the desktop.
(Document)

Eigenvectors of 3x3 symmetric matrix

2007-02-09T17:56:00.000-08:00

A C++ source and header file to compute eigenvectors/values of a 3x3 symmetric matrix. Potentially easier than installing EISPACK, LAPACK, or Gandalf if you only need this single function. Takes about 6000 clock cycles per call on my Pentium 4. Public domain. [1]

Incremental flash backup tool

2006-10-15T05:08:00.000-07:00

I recently decided that I would back up my documents to a high capacity flash disk. Thus I wrote a backup tool.
Features:

Dead simple. Something you'd write in an hour, so it won't mess you up by having volumes of code, weird interfaces, complicated man pages, or obscure back up formats.
The flash disk is a mirrored filesystem, so no special tools are required to read the backup.
The existing backed-up filesystem is updated if the backup command is re-issued.
Specified directories are recursively copied; hidden files are not copied. Thus one can flag large files that should not be backed up: make them hidden.
Eventually needs support for checksums, but I'm not too worried at the moment.

The program is public domain. Download and run it. Copy its example backup command line into a shell script. In my case, I use something similar to:

% python backup.py D:\ D:\Documents D:\Code G:\Backup

(Source Code)

Intelligent Minesweeper

2006-08-06T02:35:00.000-07:00

A game of Minesweeper, with moves suggested by the entail module I posted earlier. The entail module contains a propositional logic inference algorithm: it lets one determine whether any given expression of binary variables follows logically from a set of assumptions:

>>> s = AssumptionSet(['a => b => c <=> a'])
>>> s.implies('a <=> b')
True
>>> s.assume('c')
>>> s.implies('a')
True

It is rather uncanny how complicated mathematical relationships can be derived ex nihilo using only the entail module. For the Minesweeper game, when the user chooses "Suggest Move," I add only the knowledge that the player possesses to an AssumptionSet, and then suggest a move if the logic algorithm can deduce that any given square is free of a mine. The result is a perfect deterministic minesweeper AI: if any given move on the board can be made safely, then the AI will suggest that square. If no move can be made safely, then no suggestion will be made. Note that this is also an experiment with using HTML widgets in lieu of using a widget toolkit such as wxPython, so bear with the strange appearance of the window.

(Screenshot) (EXE) (Source) (Module entail) (All public domain).

Real-time hair animation

2006-06-16T01:03:00.000-07:00

I used the Verlet integration and relaxation method described by Thomas Jakobsen in "Advanced Character Physics" [1] coupled with the animation techniques suggested by Chang, Jin, and Yu in [2] to make a fast hair simulation. My resulting video [3] was captured in real-time. The program can actually be sped up significantly by placing bounding boxes around individual quads, vertices, and segments; however, I ran into bugs when I tried to do this, so I left that optimization out for now. The results are interesting because they indicate that in video games, hair can be animated in real-time with relative ease. The source code has been placed in the public domain.
(Video) (Writeup) (Source Code)

Automatic Python imports with autoimp

2006-06-10T21:48:00.000-07:00

I got sick of writing "import X" in Python. So, I created the public domain module autoimp, which imports all modules automatically:

>>> from autoimp import *
>>> os.stat('.')
>>> Image.open('test.bmp')
>>> pylab.plot([1,2],[3,4])
>>> scipy.linalg.eig([[1,2],[3,4]])
>>> ...

Thus one no longer needs to write "import X". It would take too long to load every module when one writes "from autoimp import *", so the imported modules are actually proxy objects which lazily load when they are first used.
(Module Website)

Programming Language Productivity

2006-05-18T17:26:00.000-07:00

Norvig [1] commented on two productivity studies by Prechelt [2] and Garret [3]. The results for the productivity of the languages isn't immediately apparent, so I extracted the relevant information as a "productivity summary" [4]. The results strongly indicate that programmers who solve a problem with fewer lines of code are more productive, irrespective of the language used. Thus languages which are more succinct could be said to be more productive.

For entertainment purposes, I solved the given problem in Python; it took me 1 hour 10 minutes, with 31 lines of code. I spent 10 minutes reading the problem, and 40 minutes fixing mistakes that I had made due to not reading the problem carefully enough. There is a lesson here...

(Productivity Summary) (My Solution)

Eight queens in Python

2006-05-10T17:06:00.000-07:00

An elegant way to find all solutions to the 8-queens problem: generate all 8-castles solutions by a permutations() generator and filter the diagonals by checking that the set of diagonals represented has 8 elements. I implemented this algorithm in Python (17 lines) and C++ (66 lines).
(Python Code) (C++ Code)

Shedskin benchmarks

2006-04-28T18:27:00.000-07:00

Shedskin [1] is an experimental Python to C++ compiler. I benchmarked it for some of the microbenchmarks in The Computer Language Shootout [2]. The results are interesting: for some benchmarks, the compiled Python code runs at nearly the speed of C.
(These benchmarks are out of date, so I removed the link).

rencode -- Reduced length encodings

2006-01-23T02:52:00.000-08:00

A space-efficient Python serialization module based on bencode,
which can be used to decode strings from untrusted sources. Works well for complex, heterogeneous data structures with many small elements. The encodings take considerably less space than bencode, gherkin, and Recipe 415503 [1] for that use case, and this module is faster, too. (Source code), (Comparison).

Allegro Quick Reference in Japanese

2005-12-17T00:15:00.000-08:00

The Allegro Quick Reference guide that I wrote in 2002 [1] has been translated into Japanese [2] by Ohsawa Hirotaka. Cool.

Search the Web in Python

2005-12-16T23:43:00.000-08:00

Query 6 search engines in Python. (Module website).

MPI matrix multiplication and inversion

2005-12-07T14:41:00.000-08:00

MPI matrix multiplication and inversion routines, written for a physics class that I took last year. The code is modular, and more flexible than the matrix multiplication codes I found on the Web (I couldn't find any simple MPI matrix inversion routines on the Web). The PDF document is public domain. (Algorithms and Code).

See also: ScaLAPACK.

Moore's law

2005-11-13T15:07:00.000-08:00

For the past 5 years, CPU speeds have been increasing roughly linearly. That's right, for processor speeds, Moore's law does not currently apply.

FFT polynomial multiplication

2005-11-12T22:03:00.000-08:00

It's easier than you might think:

>>> def fft_mul(C1, C2):
...   d = len(C1)+len(C2)-1
...   c1 = FFT.fft(list(C1) + [0] * (d-len(C1)))
...   c2 = FFT.fft(list(C2) + [0] * (d-len(C2)))
...   return list(FFT.inverse_fft(c1*c2)[:d].real)
...
>>> fft_mul([1,2,3],[4,5]) # (1+2*x+3*x**2)*(4+5*x)
[4.0, 13.0, 22.0, 15.0]

Takes O(n logn) time. The idea is to right pad each polynomial with enough zeros so that the cyclic convolution becomes a noncyclic convolution. For more speed, pad c1 and c2 so each has power-of-2 length. (Source Code).

I posted the algorithm [1] on Wikipedia (alternate link: [2]).

Trigonometry proved

2005-11-06T19:54:00.000-08:00

Common trigonometric identities, proved in one page.

pysam -- Python I2P SAM library

2005-11-06T16:47:00.000-08:00

A Python I2P SAM library, emulates the Python socket module. I haven't updated it in a while, but it works. (Main Page).

Hogwarts Security

2005-11-06T15:21:00.000-08:00

Wow. I thought I'd seen it all. Then I find the world's most famous cryptographer talking about security in the sixth Harry Potter book. Yes, I'm talking about Bruce Schneier, author of Applied Cryptography. That made me smile. The guy is also a judge for a proposed Tor GUI. Which makes me wonder: is he now interested in anonymous networks?

Propositional logic in Python

2005-10-29T00:49:00.000-07:00

Propositional logic inference via compressed truth tables. Module entail is presumably slower than your industrial-grade C inference algorithm, but logical statements are given as Python expressions, and entailment can be checked at the interactive prompt. This makes the module easy to use, and fun. (Source Code).

Ventiloquate

2005-10-23T23:04:00.000-07:00

Hyperventilate + loquacious = ventiloquate, to freak out and speak too much, too fast, and use way more breath than is actually needed to explain the idea. I assumed that this word existed, but I guess it actually doesn't.

Basic factorization algorithms

2005-10-14T15:30:00.000-07:00

A paper which gives pseudocode and the reasoning behind some basic factorization algorithms: Fermat factorization, Pollard rho, Pollard p-1, and Brent's method. Public domain. (PDF document).

Memoization with cache clear on return of last function call

2005-10-08T18:29:00.000-07:00

Memoization is nice, but in dynamic programming, it can eat up ever-increasing amounts of memory as your memoized function is called with various arguments. A simple solution is to clear the cache when the last function call returns. (Python Recipe).

mw2html -- Export Mediawiki to static, traditional website

2005-10-06T20:49:00.000-07:00

mw2html is a Python program which exports a Mediawiki site to a traditional-looking HTML site. No indices are generated, and Wikipedia sidebars and extra formatting are removed to give a simple, streamlined site (you can substitute in your own sidebars if you wish). The outputted HTML source code is Monobook-specific and rather verbose at the moment. But the sites thus exported don't look bad. (Source code).

List of bits in Python

2005-10-04T21:56:00.000-07:00

A memory compacted list of bits (uses 1 byte per every 8 elements). Instantiate from a list or string of bits. Otherwise behaves just like the builtin Python list class. Uses the ListMixin class also published on this page. (Source code).

Why books suck

2005-10-02T22:10:00.000-07:00

An essay. Click comments for the text.

Timing a function (pytime)

2005-10-02T19:13:00.000-07:00

Python's timing facilities are...unPythonic. Module timeit requires you to specify the number of iterations for the timing loop. But that number varies according to the speed of the machine you're running on, level of optimization of your code, etc. It's more Pythonic to calculate the number of iterations in the timing procedure. As so: (Source code).

Python htmldata module

2005-10-02T19:00:00.000-07:00

Extract and modify URLs in an HTML/XHTML/CSS document. Translate HTML/XHTML documents to and from list data structures. Use cases: robots, proxy CGI scripts, filtering of HTML and CSS, and flexible wget-like mirroring. (Module website).

List mixin for Python

2005-10-02T18:50:00.000-07:00

You can use UserDict.DictMixin to create custom dictionary classes. Now you can use listmixin.ListMixin to create custom list classes. (Source code).

Infinity in Python

2005-10-02T18:48:00.000-07:00

Negative infinity:

>>> None < -1e308
True

Positive infinity:

>>> () > 1e308
True

Modified Dijkstra's algorithm in Python

2005-10-02T18:32:00.000-07:00

Algorithm: perform a breadth-first search, always expand the vertex with the smallest cost, and don't remove duplicate vertices in the cost-priority-queue.

This algorithm turns out to be nearly equivalent to Dijkstra's algorithm. For n vertices and m edges, it requires O(n+m) space, O(m*log(m)) time, and always finds the shortest path.

The strategy of not removing duplicate vertices is particularly helpful in Python, where the builtin priority queue class doesn't support the DECREASE-KEY operation. See my comment at David Eppstein's recipe (the comment is public domain).

AI algorithms in Python

2005-10-02T18:26:00.000-07:00

Uninformed search algorithms: breadth-first, depth-first, depth-limited, uniform cost, iterative deepening DFS, and bidirectional (in both tree and graph modes). (Source code).

Informed search algorithms: greedy best-first, beam, A* (in both tree and graph modes). (Source code).

Literary warfare against the end of history

2004-11-30T02:14:00.000-08:00

The author dpa has some thoughts on the end of literacy. I posted a lengthy response to his writing. See dpa's blog, or my mirrored copy.

Political commentary

2004-11-25T01:59:00.000-08:00

I posted some commentary on 3rd political parties in the United States to 1. Or see my mirrored copy.