tag:blogger.com,1999:blog-93182222024-03-18T16:53:06.434-07:00Connelly - TechnicalPublic domain code.Connelly Barneshttp://www.blogger.com/profile/02568908952592933174noreply@blogger.comBlogger43125tag:blogger.com,1999:blog-9318222.post-67125094865794158522009-07-07T02:27:00.000-07:002009-07-07T02:35:17.156-07:00Allegro 'libgif' animation libraryFrom 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:<br /><br /><code>BITMAP *bmp = load_gif(filename, 0);<br />...<br />draw_sprite(screen, bmp, x, y); /* BITMAP automatically changes with time. */</code><br /><br />(<a href="http://www.connellybarnes.com/code/c/animate-0.2.zip">Source</a>)<br /><br />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...Connelly Barneshttp://www.blogger.com/profile/02568908952592933174noreply@blogger.com24tag:blogger.com,1999:blog-9318222.post-76602792091213310582008-07-23T14:59:00.000-07:002008-07-23T15:15:14.616-07:00forkmap, threadmapI 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.<br /><br />To use more cores, I occasionally use these parallel map functions in Python:<ul><li><a href="http://www.connellybarnes.com/code/python/threadmap">threadmap</a><br /><li><a href="http://www.connellybarnes.com/code/python/forkmap">forkmap</a><br /></ul><code>threadmap</code> spawns a number of threads equal to the number of cores, and distributes work across threads. <code>forkmap</code> 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.<br /><br />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.)<br /><br />There are <a href="http://wiki.python.org/moin/ParallelProcessing">libraries</a> 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.Connelly Barneshttp://www.blogger.com/profile/02568908952592933174noreply@blogger.com7tag:blogger.com,1999:blog-9318222.post-82111666682498425042008-03-15T19:14:00.001-07:002008-03-18T13:07:09.586-07:00C++ foreachI can never remember the C++ for-each loop syntax. Thus, a helper macro I use:<br /><ul><code>#define for_each(type, it, L) for (type::iterator (it) = (L).begin(); (it) != (L).end(); ++(it))</code></ul>If L has type T, usage is:<ul><pre>for_each(T, it, L) {<br /> printf("%d\n", (*it));<br />}<br /></pre></ul>If you're only using gcc, one can use __typeof__ <a href="http://anthony.liekens.net/index.php/Computers/CppForeach">[1]</a> to simplify this.Connelly Barneshttp://www.blogger.com/profile/02568908952592933174noreply@blogger.com15tag:blogger.com,1999:blog-9318222.post-39892303762786609872007-11-04T09:28:00.000-08:002007-11-04T15:29:38.878-08:00RK45 in PythonRunge-Kutta 4th and 5th order adaptive ODE integrator. Generally the <a href="http://www.scipy.org/">scipy</a> integrators will be easier to use, unless you specifically need RK45.<br />(<a href="http://www.connellybarnes.com/code/python/rk45">Code</a>)Connelly Barneshttp://www.blogger.com/profile/02568908952592933174noreply@blogger.com7tag:blogger.com,1999:blog-9318222.post-84587173745795379102007-09-12T21:53:00.000-07:002007-12-21T15:25:41.933-08:00Filter numpy images with FFT, PythonGeneric linear filter support is not currently built into the Python Imaging Library. This module lets you filter a numpy array against an arbitrary kernel:<ul><code>>>> I = numpy.asarray(Image.open('test.jpg'))<br />>>> I = filter(I, [[-1,0,1],[-2,0,2],[-1,0,1]])/8+128<br />>>> Image.fromarray(numpy.uint8(I)).show()<br /></ul></code>The Fast Fourier Transform (FFT) is used. The FFT routine included with numpy isn't particularly fast (c.f. FFTW <a href="http://www.fftw.org/">[1]</a>), 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(<i>N</i>log<i>N</i>) time, which is the fastest known time complexity algorithm for the general problem.) Public domain.<br /><br />Update: A number of image filtering operations are provided in <code>numarray</code> (in the module <code>numpy.numarray.nd_image</code>), such as filtering, image morphology, distance transforms, and segmentation; see <a href="http://structure.usc.edu/numarray/module-numarray.ndimage.html">[2]</a>.<br /><br />(<a href="http://www.connellybarnes.com/code/python/filterfft">Source</a>)Connelly Barneshttp://www.blogger.com/profile/02568908952592933174noreply@blogger.com8tag:blogger.com,1999:blog-9318222.post-89655147715792714912007-06-04T15:51:00.000-07:002007-06-04T19:26:24.685-07:00framecap - Capture camera input with Allegro, C++Requires OpenCV, Allegro, and pthreads. Captures frames from a webcam. Usage:<ul><pre>CAPTURE *cap = create_capture();<br />BITMAP *bmp = capture_frame(cap);</pre></ul>Use <code>capture_frame_nb</code> 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.<br /><br />(<a href="http://www.connellybarnes.com/code/c/framecap-0.2.0.zip">Source</a>)Connelly Barneshttp://www.blogger.com/profile/02568908952592933174noreply@blogger.com13tag:blogger.com,1999:blog-9318222.post-59454915101997707542007-04-30T18:44:00.000-07:002007-05-04T14:03:51.047-07:00pfm - Read/write 1 and 3 channel PFM filesPFM files are <i>m</i>x<i>n</i>x1 or <i>m</i>x<i>n</i>x3 arrays of floats. C++ code to read/write the format (public domain).<br />(<a href="http://www.connellybarnes.com/code/c/pfm-1.0.0.zip">Source</a>)Connelly Barneshttp://www.blogger.com/profile/02568908952592933174noreply@blogger.com7tag:blogger.com,1999:blog-9318222.post-19015407395000943342007-04-04T16:37:00.000-07:002007-04-10T18:47:31.360-07:00OpenCV camera and AVI inputTo convert a video to a format that OpenCV can read:<br /><pre> $ mencoder in.avi -ovc raw -vf format=i420 -o out.avi</pre>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: <a href="http://www.connellybarnes.com/code/c/opencv_input.cpp">[1]</a>. To capture frames in a nonblocking manner in Python, use: <a href="http://www.connellybarnes.com/code/python/nonblocking_showcam.zip">[2]</a> with Gary Bishop's <code>cvtypes</code> <a href="http://wwwx.cs.unc.edu/~gb/wp/blog/2007/02/04/python-opencv-wrapper-using-ctypes/">[3]</a>.Connelly Barneshttp://www.blogger.com/profile/02568908952592933174noreply@blogger.com7tag:blogger.com,1999:blog-9318222.post-83111896417785459422007-04-03T11:24:00.000-07:002007-09-13T05:23:29.321-07:00Burrows-Wheeler transform in Python<pre>def bwt(s):<br /> s = s + '\0'<br /> return ''.join([x[-1] for x in<br /> sorted([s[i:] + s[:i] for i in range(len(s))])])<br /><br />def ibwt(s):<br /> L = [''] * len(s)<br /> for i in range(len(s)):<br /> L = sorted([s[i] + L[i] for i in range(len(s))])<br /> return [x for x in L if x.endswith('\0')][0][:-1]</pre>The Burrows-Wheeler transform <a href="http://en.wikipedia.org/wiki/Burrows-Wheeler_transform">[1]</a> 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 <code>sorted([s[i:] + s[:i]...])</code> on which <code>s</code> occurs, then in IBWT simply return this row after the for loop. The Python code above is not particularly fast.Connelly Barneshttp://www.blogger.com/profile/02568908952592933174noreply@blogger.com2tag:blogger.com,1999:blog-9318222.post-72688650666165597662007-04-01T17:12:00.000-07:002007-04-01T17:13:16.054-07:00How to put a video on the WebInstall FFMPEG <a href="http://ffdshow.faireal.net/mirror/ffmpeg/">[1]</a>, use <code>ffmpeg -i in.avi out.swf</code>, then place <code><embed src="out.swf" width="400" height="300" loop="false" quality="high"></embed></code> in your HTML. Optionally, use the <code>-s</code> argument after <code>-i</code> in FFMPEG to change the resolution. If you want playback controls, output to a <code>.flv</code> file instead, download FlowPlayer <a href="http://flowplayer.sourceforge.net/">[1]</a>, and modify their example HTML to point to your <code>.flv</code> video.Connelly Barneshttp://www.blogger.com/profile/02568908952592933174noreply@blogger.com3tag:blogger.com,1999:blog-9318222.post-1171733547157797992007-02-17T09:24:00.000-08:002007-02-19T02:30:38.506-08:00Ubuntu Linux postinstall notesAfter installing an operating system, there are always a zillion changes I have to make to get the operating system <i>operational</i>. 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.<br />(<a href="http://www.connellybarnes.com/documents/linux_postinstall_notes.txt">Document</a>)Connelly Barneshttp://www.blogger.com/profile/02568908952592933174noreply@blogger.com1tag:blogger.com,1999:blog-9318222.post-1171072775655024542007-02-09T17:56:00.000-08:002007-02-09T18:07:08.243-08:00Eigenvectors of 3x3 symmetric matrixA 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. <a href="http://www.connellybarnes.com/code/c/eig3-1.0.0.zip">[1]</a>Connelly Barneshttp://www.blogger.com/profile/02568908952592933174noreply@blogger.com33tag:blogger.com,1999:blog-9318222.post-1160915228515039922006-10-15T05:08:00.000-07:002008-10-27T15:00:11.767-07:00Incremental flash backup toolI recently decided that I would back up my documents to a high capacity flash disk. Thus I wrote a backup tool.<br />Features:<ul><li>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.<br /><li>The flash disk is a mirrored filesystem, so no special tools are required to read the backup.<br /><li>The existing backed-up filesystem is updated if the backup command is re-issued.<br /><li>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.<br /><li>Eventually needs support for checksums, but I'm not too worried at the moment.<br /></ul>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:<br /><br /><code> % python backup.py D:\ D:\Documents D:\Code G:\Backup</code><br /><br />(<a href="http://www.connellybarnes.com/code/python/backup">Source Code</a>)Connelly Barneshttp://www.blogger.com/profile/02568908952592933174noreply@blogger.com1tag:blogger.com,1999:blog-9318222.post-1154858972545251032006-08-06T02:35:00.000-07:002008-10-27T14:59:15.505-07:00Intelligent MinesweeperA game of Minesweeper, with moves suggested by the <code>entail</code> module I posted earlier. The <code>entail</code> 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:<br /><ul><pre>>>> s = AssumptionSet(['a => b => c <=> a'])<br />>>> s.implies('a <=> b')<br />True<br />>>> s.assume('c')<br />>>> s.implies('a')<br />True<br /></pre></ul>It is rather uncanny how complicated mathematical relationships can be derived <i>ex nihilo</i> using only the <code>entail</code> module. For the Minesweeper game, when the user chooses "Suggest Move," I add only the knowledge that the player possesses to an <code>AssumptionSet</code>, 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.<br /><br />(<a href="http://www.connellybarnes.com/code/python/mine-screen.png">Screenshot</a>) (<a href="http://www.connellybarnes.com/code/python/mine-exe.zip">EXE</a>) (<a href="http://www.connellybarnes.com/code/python/mine-src.zip">Source</a>) (<a href="http://www.connellybarnes.com/code/python/entail">Module entail</a>) (All public domain).Connelly Barneshttp://www.blogger.com/profile/02568908952592933174noreply@blogger.com4tag:blogger.com,1999:blog-9318222.post-1150445600795938482006-06-16T01:03:00.000-07:002008-10-27T14:57:46.801-07:00Real-time hair animationI used the Verlet integration and relaxation method described by Thomas Jakobsen in "Advanced Character Physics" <a href="http://www.teknikus.dk/tj/gdc2001.htm">[1]</a> coupled with the animation techniques suggested by Chang, Jin, and Yu in <a href="http://www-sal.cs.uiuc.edu/~yyz/research/hair/">[2]</a> to make a fast hair simulation. My resulting video <a href="http://www.princeton.edu/~csbarnes/documents/hair/connelly_hair_movie.avi">[3]</a> 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.<br />(<a href="http://www.connellybarnes.com/documents/hair/connelly_hair_movie.avi">Video</a>) (<a href="http://www.connellybarnes.com/documents/hair/">Writeup</a>) (<a href="http://www.connellybarnes.com/documents/hair/connelly_source.zip">Source Code</a>)Connelly Barneshttp://www.blogger.com/profile/02568908952592933174noreply@blogger.com99tag:blogger.com,1999:blog-9318222.post-1150011002992137382006-06-10T21:48:00.000-07:002008-10-27T14:56:56.064-07:00Automatic Python imports with autoimpI got sick of writing "<code>import X</code>" in Python. So, I created the public domain module <code>autoimp</code>, which imports all modules automatically:<pre>>>> from autoimp import *<br />>>> os.stat('.')<br />>>> Image.open('test.bmp')<br />>>> pylab.plot([1,2],[3,4])<br />>>> scipy.linalg.eig([[1,2],[3,4]])<br />>>> ...</pre>Thus one no longer needs to write "<code>import X</code>". It would take too long to load every module when one writes "<code>from autoimp import *</code>", so the imported modules are actually proxy objects which lazily load when they are first used.<br />(<a href="http://www.connellybarnes.com/code/autoimp/">Module Website</a>)Connelly Barneshttp://www.blogger.com/profile/02568908952592933174noreply@blogger.com9tag:blogger.com,1999:blog-9318222.post-1148002350658279852006-05-18T17:26:00.000-07:002008-10-27T14:56:12.148-07:00Programming Language ProductivityNorvig <a href="http://www.norvig.com/java-lisp.html">[1]</a> commented on two productivity studies by Prechelt <a href="http://page.mi.fu-berlin.de/~prechelt/Biblio/jccpprtTR.pdf">[2]</a> and Garret <a href="http://www.flownet.com/gat/papers/lisp-java.pdf">[3]</a>. The results for the productivity of the languages isn't immediately apparent, so I extracted the relevant information as a "productivity summary" <a href="http://www.connellybarnes.com/documents/language_productivity.pdf">[4]</a>. 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.<br /><br />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...<br /><br />(<a href="http://www.connellybarnes.com/documents/language_productivity.pdf">Productivity Summary</a>) (<a href="http://www.connellybarnes.com/code/python/prechelt">My Solution</a>)Connelly Barneshttp://www.blogger.com/profile/02568908952592933174noreply@blogger.com7tag:blogger.com,1999:blog-9318222.post-1147306226318084772006-05-10T17:06:00.000-07:002008-10-27T14:55:27.880-07:00Eight queens in PythonAn 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).<br />(<a href="http://www.connellybarnes.com/code/python/queens">Python Code</a>) (<a href="http://www.connellybarnes.com/code/python/queens.cpp">C++ Code</a>)Connelly Barneshttp://www.blogger.com/profile/02568908952592933174noreply@blogger.com4tag:blogger.com,1999:blog-9318222.post-1146274408283321512006-04-28T18:27:00.000-07:002008-10-27T14:54:43.280-07:00Shedskin benchmarksShedskin <a href="http://sourceforge.net/projects/shedskin/">[1]</a> is an experimental Python to C++ compiler. I benchmarked it for some of the microbenchmarks in The Computer Language Shootout <a href="http://shootout.alioth.debian.org/">[2]</a>. The results are interesting: for some benchmarks, the compiled Python code runs at nearly the speed of C.<br />(These benchmarks are out of date, so I removed the link).Connelly Barneshttp://www.blogger.com/profile/02568908952592933174noreply@blogger.com1tag:blogger.com,1999:blog-9318222.post-1138014204866874532006-01-23T02:52:00.000-08:002007-11-19T03:02:36.858-08:00rencode -- Reduced length encodingsA space-efficient Python serialization module based on bencode,<br />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 <a href="http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/415503">[1]</a> for that use case, and this module is faster, too. (<a href="http://www.connellybarnes.com/code/python/rencode">Source code</a>), (<a href="http://www.connellybarnes.com/code/python/rencode_compare.txt">Comparison</a>).Connelly Barneshttp://www.blogger.com/profile/02568908952592933174noreply@blogger.com3tag:blogger.com,1999:blog-9318222.post-1134807510809956142005-12-17T00:15:00.000-08:002008-10-27T14:47:41.726-07:00Allegro Quick Reference in JapaneseThe Allegro Quick Reference guide that I wrote in 2002 <a href="http://www.connellybarnes.com/documents/quick_reference.html">[1]</a> has been translated into Japanese <a href="http://www.ayu.ics.keio.ac.jp/~osawa/allegro/reference.html">[2]</a> by Ohsawa Hirotaka. Cool.Connelly Barneshttp://www.blogger.com/profile/02568908952592933174noreply@blogger.com4tag:blogger.com,1999:blog-9318222.post-1134805534614649422005-12-16T23:43:00.000-08:002008-10-27T13:41:45.125-07:00Search the Web in PythonQuery 6 search engines in Python. (<a href="http://www.connellybarnes.com/code/web_search/">Module website</a>).Connelly Barneshttp://www.blogger.com/profile/02568908952592933174noreply@blogger.com1tag:blogger.com,1999:blog-9318222.post-1133995958547486192005-12-07T14:41:00.000-08:002008-10-27T13:40:08.895-07:00MPI matrix multiplication and inversionMPI 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. (<a href="http://www.connellybarnes.com/documents/ph417_mpi_project.pdf">Algorithms and Code</a>).<br /><br />See also: <a href="http://www.netlib.org/scalapack/">ScaLAPACK</a>.Connelly Barneshttp://www.blogger.com/profile/02568908952592933174noreply@blogger.com5tag:blogger.com,1999:blog-9318222.post-1131933622557273942005-11-13T15:07:00.000-08:002008-10-27T13:39:20.972-07:00Moore's lawFor the past 5 years, CPU speeds have been <a href="http://www.connellybarnes.com/documents/cpu_speed.pdf">increasing roughly linearly</a>. That's right, for processor speeds, Moore's law does not currently apply.Connelly Barneshttp://www.blogger.com/profile/02568908952592933174noreply@blogger.com5tag:blogger.com,1999:blog-9318222.post-1131863404531015482005-11-12T22:03:00.000-08:002008-10-27T13:38:04.499-07:00FFT polynomial multiplicationIt's easier than you might think:<pre>>>> def fft_mul(C1, C2):<br />... d = len(C1)+len(C2)-1<br />... c1 = FFT.fft(list(C1) + [0] * (d-len(C1)))<br />... c2 = FFT.fft(list(C2) + [0] * (d-len(C2)))<br />... return list(FFT.inverse_fft(c1*c2)[:d].real)<br />...<br />>>> fft_mul([1,2,3],[4,5]) # (1+2*x+3*x**2)*(4+5*x)<br />[4.0, 13.0, 22.0, 15.0]</pre>Takes O(<i>n</i> log<i>n</i>) 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 <code>c1</code> and <code>c2</code> so each has power-of-2 length. (<a href="http://www.connellybarnes.com/code/python/poly_mul">Source Code</a>).<br /><br />I posted the algorithm <a href="http://en.wikipedia.org/wiki/Discrete_Fourier_transform#Outline_of_DFT_polynomial_multiplication_algorithm">[1]</a> on Wikipedia (alternate link: <a href="http://en.wikipedia.org/w/index.php?title=Discrete_Fourier_transform&oldid=31278814#Outline_of_DFT_polynomial_multiplication_algorithm">[2]</a>).Connelly Barneshttp://www.blogger.com/profile/02568908952592933174noreply@blogger.com7