Thursday, December 23, 2010

If you need newgrp, you dun goofed (and "setuidgid" may be the culprit)

Recently, on a machine with custom upstart init scripts, I couldn't figure out why I couldn't access serial ports or USB devices, even though my username was in the dialout and plugdev groups in /etc/group.

Running the "groups" command, I could see that my groupset only contained my own personal group:

$ groups
credentiality

I found that I could run "newgrp dialout" to get it added to my groupset:


$ newgrp dialout
$ groups
dialout credentiality

And looking online, I found various tricks people would use to run the commands they needed using newgrp.  (It's not trivial, since newgrp insists on creating a subshell).

But I kept getting the sense that newgrp should almost never be necessary anymore, now that modern unix systems have the notion of a groupset.

Turns out the culprit was "setuidgid", which we were using in the upstart scripts to run programs as me.  They said things like:

exec setuidgid credentiality startx

Now that I know to look for it, setuidgid's manpage points out that it "remov[es] all supplementary groups".  Which isn't very helpful if, for instance, a process needs to access files from both the "dialout" and "plugdev" groups.

Fortunately, there are several alternatives to setuidgid that preserve the group memberships you expect, and you can use the "groups" command to verify that:

# setuidgid credentiality groups
credentiality

# su -c groups credentiality
credentiality adm disk dialout cdrom floppy sudo audio dip video plugdev

# sudo -u credentiality groups
credentiality adm disk dialout cdrom floppy sudo audio dip video plugdev

# start-stop-daemon -c credentiality -S --exec /usr/bin/groups
credentiality adm disk dialout cdrom floppy sudo audio dip video plugdev

# # chpst is in package runit (yet another init system, ugh.), and lets you specify a list of groups explicitly:
# chpst -u credentiality:credentiality:plugdev:dialout groups
credentiality plugdev dialout

Thursday, December 02, 2010

Carmichael numbers and Fermat primality

I did some recreational mathematics today, and created this plot, showing the number of values for which a^(n-1) = 1 (mod n), for all composite n in the range [3..10000]:


The formula a^(n-1) mod n appears in Fermat's Little Theorem, which says that for prime values of n, the result will always be 1, no matter what a you choose.  If you get a value other than 1, you know that n is composite.

That's neat because it lets us test whether a given n is composite much more quickly than by trying to factor it.  We call that the Fermat Primality Test.  

However, the converse doesn't always hold: sometimes a^(n-1)=1 (mod n) even if n is composite.  When  that happens for some a and n, we say that a is a false witness for n, since it incorrectly suggests that n might be prime.

And that's what the above graph shows: how many false witnesses there are for each value n up to 10,000.  In particular, I scaled the y axis so that it shows the percentage of relatively prime a values that are false witnesses.

Carmichael Numbers

Most interesting are the vertical lines in the graph that reach all the way to the top.  Those are the falsest of the pseudoprimes (with respect to the Fermat test).  They're called the Carmichael Numbers, and I've always found them fascinating, because the smallest of them is 561!  That's the leftmost line in the graph that reaches all the way to the top.

Just how prime are you?

The other thing I was surprised to find in this graph are what we might call the halfway-prime numbers -- numbers for which half of the witnesses will suggest primality with the Fermat test.  And there are one-third-prime numbers, and so on.

Merry Christmas!

All that graphing got me wondering how often a^(n-1) produces numbers other than 1.  So I created this image, which shows increasing values of n as you work downward, and shows how often we get a remainder r.  r is shown on the X axis, while the number of times it came up is shown as a color:

 0=black, 1=dark gray, 2=light gray, 3=blue, 4=orange, 5=red, 6 or more = white

The other trick is that in number theory, we sometimes talk about negative remainders.  If you're working (mod 5), you might get remainders of 0,1,2,3,4, but since the next remainder after 4 is 0 again, sometimes it's easier to think of a remainder of 4 as -1.  So instead of 0,1,2,3,4, we call them 0,1,2,-2,-1, and that's what I've done here. 


Consider the topmost orange pixel in the above image.  It's the 5th pixel from the top, so that whole row represents n=5.  The orange pixel (and all the ones below it) are the "remainder=1" column.  The column to the left of it is the "remainder=0" column, and the one to the right is "remainder=2".  Since 5 is prime, we expect a^4 to be 1 (mod 5) for all 4 possible values of a: 1,2,3 and 4.  And indeed, orange is the color for 4.

Two pixels down, you'll see a white pixel telling us that 7 is prime, since a^6=1 (mod 7) for a=1,2,3,4,5,6.  In the above image, you can keep counting down from the orange pixel at n=5 and see all the primes as white pixels, with 31 at the very bottom.

Give me one of everything

One surprise to me was row 6 (just below the topmost orange pixel).  It has a solid dark gray line extending all the way across.  That means that the five values of a: 1,2,3,4,5 in the equation a^5 (mod 6) produced... the values 1,2,3,4,5!  (Try it: 2^5=32, mod 6=2.  3^5=243, mod 6=3.)

And you can see that lots of other numbers have this behavior: 10, 14, (but not 18!), 22, 26, 30 and so on.

I need a bigger tree

Here's how the image looks if we keep going all the way to 100:



Sunday, October 03, 2010

Bechdel Test: Aeon Flux

I had forgotten what a great movie Aeon Flux was.  I can't think of a more Bechdel-compliant action movie, it's visually stunning, and has a creative plot.

Monday, August 23, 2010

Escalation

The answer was in the stars. For some reason, Earthlings had founded universities, and those universities had supported thousands of astronomers for hundreds of years. They refined their techniques over the centuries, collecting databases of statistics on distant stars which no human could ever visit.

And then a grad student in cryptography had gotten fed up with her adviser and switched to astronomy. To familiarize herself with the star database, Li had fed the coordinates of all the known stars in the galaxy into a PRNG test suite used to assess the predictability of cryptographic random number generators.

She hadn't been surprised when the database failed the test; stars aren't randomly distributed, and as they later found, at least 7 different astronomical techniques had also added artificial patterns to the database. However, Li thought it amusing when the test suite claimed the values were generated by a Linear Feedback Shift Register, the simplistic random number generator included in most programming libraries. It had even helpfully produced the LFSR parameters which, with a few lines of code, would generate a sequence of numbers that the test suite thought were somehow related to the database values.

Li had shown it to her advisor, and over a few months they had toyed with the results at odd hours, musing on a publication about systemic errors in sky survey techniques, or perhaps uncovering evidence of fabrication by some unscrupulous astronomer. When Li's model started predicting locations of stars before they were discovered, they worked full time on it for 18 months before telling another soul: surely it would be seen as plagiarism, not prediction.

But in the end, the systemic errors were identified and eliminated, and Li was confirmed to have made the greatest scientific discovery in all of history: the universe they lived in was incontrovertibly a simulation. And moreover, whatever Gods had placed the stars in their galaxies had been lazy in their choice of random number generators, just as human programmers are. (This did create a certain smugness among the kind of cryptographers who used cryptograpic-strength PRNGs to shuffle music playlists.)

As news-show pundits spouted absurdities and mankind came to grips with the hand of God, scientists in all fields now knew what to look for, and found bugs aplenty.

And as the fabric of the universe resolved under our microscopes, it was the cryptographers once again who made a profoundly disturbing hypothesis. The universe was made of bits, and manipulated by algorithms. Far more bits than our computers had, and running algorithms more complex than mankind had ever managed. But we knew there were bugs. What if some of those bugs were also security holes?

Teenagers had been exploiting complex systems for years. A carefully crafted string of a few hundred unexpected characters could cause a buggy subroutine to turn a user into an administrator. Or, if the string was slightly off, crash the server. This was normally no concern to the budding hackers. But then, they usually weren't hacking their own life support.

When the politicians finally understood, the strictest laws were passed. But studying really isn't much different than hacking, and eventually we learned all about our host machine. And several of the shortcomings of our universe started looking tantalizingly exploitable.

Sunday, August 22, 2010

Ubuntu Lucid running alongside android on my phone

At first I thought running ubuntu on my phone would require blowing away the android OS, but that's not the case. Instead, an ubuntu filesystem gets mounted on the SD card, with all the system files set up right so that things like apt-get work. Some things don't work, I think because the android kernel isn't quite what the ubuntu apps expect, but you know you're doing well when firefox runs!

The nexusonehacks Ubuntu disk image worked great for me, but took forever to download and had a ton of stuff that I didn't need, like firefox and openoffice.org.

So I stripped it down to bare bones and upgraded it to lucid. Check it out: run a bare-bones Ubuntu Lucid filesystem alongside android on a froyo phone.

Friday, August 20, 2010

Native vim for android

Update: The vim binary has moved to the downloads page.

Update: Created a code.google.com project to keep stuff like this. Also, I got color syntax hilighting to work. See the README.txt in the vim/ directory of the repository.

Tonight I managed to compile vim to run natively on my android phone! My phone is rooted and running cyanogenmod CM6 rc3. Rooting is necessary to run vim, but cyanogen probably isn't necessary.

First I had to compile ncurses using the ndk. Follow that link and compile ncurses the way I did if you want to have any hope of compiling vim using these instructions.

Once I had ncurses built, I had to make just a few changes to vim to get it to work.

I downloaded vim from the mercurial archive, which as of today is pretty much the same as the 7.3 release, I think. I figured out how to call configure by trial and error:

vim_cv_memcpy_handles_overlap=no \
vim_cv_bcopy_handles_overlap=no \
vim_cv_memmove_handles_overlap=no \
vim_cv_stat_ignores_slash=no \
vim_cv_getcwd_broken=no \
vim_cv_tty_group=world \
vim_cv_terminfo=yes \
LDFLAGS="-L/path/to/ncurses-5.7/lib" \
CFLAGS="-I/path/to/ncurses-5.7/lib" \
vim_cv_toupper_broken=no \
CC=agcc.pl \
./configure --host=arm-eabi --with-tlib=ncurses

I got this error message: "could not compile program using uint32_t", and manually patched the configure script because I couldn't remember how to regenerate the script from the configure.in:
$as_echo_n "checking uint32_t is 32 bits... " >&6; }
if test "$cross_compiling" = yes; then :
  true
#  as_fn_error "could not compile program using uint32_t." "$LINENO" 5
else

I also got an "undefined reference to sysinfo" error due to an android bug that omitted the sysinfo() call. So I commented out the HAVE_SYSINFO and HAVE_SYSINFO_MEM_UNIT lines in src/auto/config.h.

I think that was it! Once it finished compiling, I copied over the runtime/ directory and the src/vim binary to /data/vim on my phone. I did an "export VIMRUNTIME=/data/vim/runtime", and vim worked great!

Once I got my VIMRUNTIME set, I was able to ":syntax on", although I'm not getting any color. But otherwise it seems to work great!

You can find a tarball of vim for android on the Downloads page: look for vim-7.3-android-binary.tar.gz. There's also a tarred-up copy of my build directory, although I'm not sure why anyone would want that.

Compile ncurses for android

Update: The tarball of my ncurses build directory has moved to the downloads page.  (Also, agcc -> agcc.pl thanks to Interarticle)

I got the crazy notion to try to compile a native vim binary for android, and one of its dependencies is libncurses.

Make sure you have the ndk installed and working.

You'll need the agcc wrapper, a perl script that creates appropriate command line arguments for arm-eabi-gcc. I learned today that the order of arguments to gcc can be quite significant while linking. I kept getting errors about the "__aeabi_unwind_cpp_pr0" symbol and common functions like printf not being found when it tried to link.

So I hacked Vlad's hacked agcc to make sure that libgcc.a and libc.a get put at the end of the command line, which seems to be necessary for static linking. Here's my hacked version of Vlad's agcc.

Make sure both agcc and arm-eabi-gcc are in your path.

Download ncurses-5.7.tar.gz.

Run configure:
CC=agcc.pl ./configure --host=arm-eabi --without-cxx-binding

When I tried to build, I got errors saying "'struct lconv' has no member named 'decimal_point'"", because android has a broken locale implementation.

So I commented out the HAVE_LOCALE_H line from include/ncurses_cfg.h. (Is there a better way to force configure to set a value like that during the ./configure process?)

It might be possible to build ncurses with the C++ binding, but I didn't try.

Once I had all that fixed, the make ran just fine, and I ended up with lib/libncurses.a.

Extract boot.img from an android phone

(I did this on my rooted, boot-unlocked nexus one (HTC Passion) running cyanogen cm6. Cyanogen is probably not necessary, but boot-unlocking and rooting are).

This tutorial pointed me in the right direction.

I did:
$ adb pull /dev/mtd/mtd2 boot.img-from-phone

Then put it right back using:
$ adb reboot bootloader
[wait for bootloader to come up]
$ sudo ./fastboot flash boot boot.img-from-phone
$ sudo ./fastboot reboot

I could have also taken it apart and replaced the kernel with my own.

Wednesday, August 18, 2010

Nexus One (HTC Passion): compile and flash a kernel

Update 2: my camera doesn't work with the custom kernel. no idea why. Also, I figured out how to extract the boot.img from the phone directly.

Update: mention how to update the bcm4329.ko wifi driver so that wifi will work again.

This page will tell you how to download and compile the android kernel, and try it out on your phone temporarily (without writing it to flash) using "fastboot boot zImage".

Assuming that worked, here's how to actually write the kernel to the phone's flash.

By this point you should already have fastboot. You'll also need a phone with an unlocked bootloader and probably rooted as well.

You'll also need the boot.img from your phone. It seems to be possible to pull it off a working phone, but I didn't try that. I'm running cyanogen 6, and the boot.img was in the update-cm-6.0.0-N1-RC3-signed.zip.

Next you need to unpack it using the split_bootimg perl script which I found in this tutorial.

That produced output like this:
$ ./split_bootimg.pl boot.img
Page size: 2048 (0x00000800)
Kernel size: 2206592 (0x0021ab80)
Ramdisk size: 167182 (0x00028d0e)
Second size: 0 (0x00000000)
Board name: 
Command line: no_console_suspend=1 msmsdcc_sdioirq=1 wire.search_count=5
Writing boot.img-kernel ... complete.
Writing boot.img-ramdisk.gz ... complete.

Next, you need mkbootimg. Supposedly you can use "fastboot flash:raw" to avoid this, but it didn't work for me. mkbootimg comes with the (multi-gigabyte) android sources, so I ended up downloading a pre-compiled mkbootimg binary, which made me feel dirty, but saved me many hours of downloading and compiling.

Constructing the right command line for mkbootimg was a pain, but eventually I was able to build a my-boot.img identical to the original:

./mkbootimg --kernel boot.img-kernel --ramdisk boot.img-ramdisk.gz -o my-boot.img --cmdline 'no_console_suspend=1 msmsdcc_sdioirq=1 wire.search_count=5' --base 0x20000000

The boot.img-kernel and boot.img-ramdisk.gz came from split_bootimg, as did the --cmdline string. The "--base 0x20000000" is specific to the N1 (aka nexus one aka HTC passion).

Once you get the boot.img constructed properly, reboot into the bootloader by holding down the trackball while you boot (or use "adb reboot-bootloader"). Then:
$ sudo ./fastboot flash boot my-boot.img
$ sudo ./fastboot reboot

If you get it wrong, your phone will hang at the screen with the unlocked padlock forever. Pull the battery to cold boot and reboot into the bootloader again.

(Nexus One / HTC Passion): If that worked, you may find that "wifi" under Settings... on the phone just says "error". That's because the bcm4329.ko kernel module doesn't match the kernel version.

Here's the bcm4329.ko that matches this 2.6.32 kernel (which has the serial port enabled).

The kernel module lives in /system/lib/modules/. The /system filesystem was mounted read-only on my phone, so from the root shell on my phone (adb shell) I remounted it read-write and then backed up the original kernel module, so that I can switch back to the old kernel if I need to:
# mount -oremount,rw /system
# cp /system/lib/modules/bcm4329.ko /sdcard/bcm4329.ko-orig

Then I copied over the file with "adb push bcm4329.ko /system/lib/modules/", then remounted /system back to read-only:
# mount -oremount,ro /system

It started working immediately.

Sunday, August 15, 2010

Giving native Android C apps access to the Android API through SL4A

UPDATE: this is slightly more mature now. Check out http://code.google.com/p/android-cruft/wiki/SL4AC

Today I played around with the Android NDK, a C compiler for Android. The Android folks make it very clear that it's only intended for making ordinary Java-based Android apps faster, by running a few selected functions down at the bare metal.

So it only comes with a few basic libraries which don't support things like reading the sensors and taking photos.

Enter SL4A, Scripting Languages for Android (formerly "ASE", the Android Scripting Environment). SL4A is a neat Android app that makes it very easy to write simple Android apps in many popular scripting languages like Python, Perl, Ruby and TCL. SL4A exposes a useful subset of the Android API in a clever way: by setting up a JSON RPC server. That way, each language only needs to implement a thin RPC client layer to access the whole SL4A API.

So today I managed to get the excellent Jansson C-language JSON library to compile with the NDK, making it possible for native C apps to access the Android API through SL4A, just as its normally supported languages can.

It works just fine as either a native Android binary or from a host machine, so you could also use it to control your phone from a C program running on a host computer.

Here's the ndk-to-sl4a.c source code, public domain. See the comments in the header for instructions on how to compile and run it.

If you're the trusting sort, you can also download a binary for froyo or for (ubuntu/lucid) linux. But you should still go through the comments in the source file to see how to set up SL4A first.

Native android C program using ndk

Big update: I updated agcc.pl to work with the latest NDK release, and called it agcc2.pl. Here is the new blog post.

Update: link to agcc.pl works now. Update 2: link to agcc.pl *actually* works now?

The Android NDK isn't really intended to write standalone binaries, but this tutorial got me most of the way there. But some path changes in android-ndk-r4b broke the agcc wrapper, so I had to modify it to point to the right includes and libraries.

Here's what should be a complete HOWTO for linux. It probably requires a rooted phone at the least, in order to upload and run arbitrary binaries. I'm running a pre-release of cyanogenmod CM6.

1. Download and unpack android-sdk_r06-linux_x86.tgz and android-ndk-r4b-linux-x86.zip.

2. Add android-ndk-r4b/build/prebuilt/linux-x86/arm-eabi-4.4.0/bin and android-sdk-linux_86/tools/ to your PATH. (cd into each of those directories and then run "export PATH=$PATH:`pwd`")

3. Plug your phone in via USB and run "sudo adb start-server" to start the daemon in the background (as root so that it can access the USB device. If you accidentally start the daemon as yourself and can't talk to your phone, run "adb kill-server" to kill it, then "sudo adb start-server" to restart it as root.)

4. Make sure you can run "adb" (from the SDK) and "arm-eabi-gcc" (from the NDK) so that you know your PATH is set up right.

5. Grab my copy of the agcc wrapper hacked for android-ndk-r4b. "chmod 755" it so you can run it.

6. Create the "hello, world" .c file:
#include <stdio.h>

int main() {
  printf("Hello, world!\n");
}

7. Ready to compile! "$ agcc.pl -o hello hello.c"

8. Copy the binary to /data: "adb push hello /data/"

9. Run it! I did that by SSHing into the phone, but you can also just "adb shell".
# cd /data
# ./hello
Hello, world!

Friday, August 06, 2010

Simple kalman filter example

There are a ton of Kalman filter overviews online, and lots of them give a general overview of what they do, but then they all hit a wall of variables and matrices, and fail to give good simple examples.

The best guide I found is a PDF scan of a much-faxed copy of Roger M. du Plessis' 1967 classic "Poor Man's Explanation of Kalman Filtering".

His paper is great because he starts with a single-variable filter (no matrices!) with no control component and no prediction algorithm. I'm going to try to give an even simpler example with softer terminology and more hand-waving.

Kalman filters are a way to take a bunch of noisy measurements of something, and perhaps also some predictions of how that something is changing, and maybe even some forces we're applying to that something, and to efficiently compute an accurate estimate of that something's true value.

Let's say we want to measure the temperature in a room. We think it's about 72 degrees, plus or minus 2 degrees. And we have a thermometer that gives uniformly random results within a range of +/-5 degrees of the true temperature.

We take a measurement with the thermometer and it reads 75. So what's our best estimate of the true temperature? Kalman filters use a weighted average to pick a point somewhere between our 72 degree guess and the 75 degree measurement. If the weight is large (approaching 1.0), we mostly trust our thermometer. If the weight is small, we mostly trust our guess and ignore the thermometer.

Here's how we choose the optimal weight, given the accuracy of our guess and the accuracy of the thermometer:

weight = temperature_variance / (temperature_variance + thermometer_variance)
0.29 = 2 / (2+5)

If temperature_variance were very large compared to thermometer_variance, weight would approach 1.0. That is, we'd ignore our guess and just use the measured value. Likewise, if thermometer_variance dominated, the weight would approach 0, and we'd put very little trust in our thermometer readings.

29% weight means we'll trust our guess more than the thermometer, which makes sense, because we think our guess is good to +/-2 degrees, whereas the thermometer was only good to +/-5.

Now we do the weighted average:

estimate = guess + weight*(measurement - guess)
72.87 = 72 + 0.29*(75-72)

or equivalently

estimate = (1-weight)*guess + weight*measurement
72.87 = 0.71*72 + 0.29*75

That is, we went 29% of the way from 72 to 75, or equivalently, we took 71% of the guess plus 29% of the measurement.

There's one last thing to compute: how confident we are in our estimate of 72.87 degrees. That equation is:

                      temperature_variance*thermometer_variance 
estimate_variance =   -----------------------------------------
                    (temperature_variance + thermometer_variance)

1.43 = 2*5 / (2+5)

So we think our estimate is correct to +/-1.43 degrees.

Now we have a guess that the temperature in the room is 72.87 degrees, +/-1.43 degrees. And we still have a thermometer that tells the temperature +/-5 degrees.

That's basically the situation where we started, so we can run the whole algorithm again:

First we compute the weight, using our new, more accurate guess confidence:

weight = temperature_variance / (temperature_variance + thermometer_variance)
0.22 = 1.43 / (1.43+5)


We take a measurement, and this time let's say it comes up as 71 degrees.

Now we can compute the weighted average of our old guess and our new measurement:

estimate = guess + weight*(measurement - guess)
72.46 = 72.87 + 0.22*(71-72.87)

And the new confidence level:

                      temperature_variance*thermometer_variance 
estimate_variance =   -----------------------------------------
                    (temperature_variance + thermometer_variance)

1.11 = 1.43*5 / (1.43+5)

So after the second measurement, we estimate that the actual temperature is 72.46 degrees, +/-1.11 degrees.

Kalman filters are nice because we don't have to remember the whole history of measurements and estimates. We just keep track of our most recent estimate and our confidence level in that estimate.

If we decide to turn on the air conditioner, so that the temperature in the room starts decreasing, we can expand our calculations to include that "control" variable, and use it to update our estimates by "predicting" how much colder it'll be at each measurement. Once I figure out how to do that, maybe I'll post a more complicated example :)

Tuesday, July 27, 2010

Plotting complex polynomials with octave and octaviz (vtk)

I got to wondering what happens when you feed complex numbers into polynomials, so I poked around and found the awesome vtk library binding for the octave language, called octaviz.  (octave is a free implementation of the MATLAB language).


When we plot z = f(x), where x and z are complex numbers, we get 4 dimensions to plot, so I shifted each point in the surface plot N units + or - in the Y direction, where N is the imaginary part of the output.  The color also indicates how far each point was stretched in the + or - Y direction. 

#!/usr/bin/octave

global a = 1
global b = 0
global c = 0

function z = polynomial (i,j)
  global a
  global b
  global c
  x = i + (j * 1j);
  z = a*x*x + b*x + c;
end

[I,J] = meshgrid(-1:0.2:1);
REAL = arrayfun(@real, arrayfun(@polynomial, I, J));
IMAG = arrayfun(@imag, arrayfun(@polynomial, I, J));
vtk_surf(I,J+IMAG,REAL, IMAG);

input ("Orient it the way you want it before I save.");
vtk_print('polynomial.jpg', '-djpeg');
input ("Done!");

Wednesday, July 21, 2010

Borges

The stoics teach that we should not complain of life--the door of the prison is open.
-august 25, 1983

Thursday, July 15, 2010

Things I hate: externalized costs in programming

Bob adds a feature to handle a situation that someday might arise. Alice then discovers a production failure caused by that feature. Good luck removing the feature: doing that might cause a production failure someday!

python-tk: tkinter photo doesn't work inside a function

Wow, python-tk sucks. When I create the photo inside a function, it gets garbage-collected because it's not smart enough to know that the label is using it. So I have to manually keep it from being deallocated (in this case, by making it global). Also, I'd really like to use after_idle instead of after, but it never gets around to actually updating the display.

#!/usr/bin/python

import Tkinter
import ImageTk,Image

root = Tkinter.Tk()
root.geometry('+640+480')

old_label = None
label = None
photo = None
def display_image(root, image):
global old_label
global label
global photo

root.geometry('%dx%d' % (image.size[0], image.size[1]))

photo = ImageTk.PhotoImage(image)

label = Tkinter.Label(root, image=photo)
label.place(x=0,y=0,width=image.size[0],height=image.size[1])

if old_label is not None:
old_label.destroy()

old_label = label

def image_loop():
global root
print '.'
image = get_image()
display_image(root, image)
root.after(1000,image_loop)

image_loop()

root.mainloop()

python plumbing: PIL Image from data string

Today I wanted to use netcat (nc) to send a JPEG image file over a network to a python script so that I can manipulate it with PIL, the python imaging library.

PIL has fromstring and frombuffer methods, but I couldn't get them to work. But I found the ImageFile module, which let me feed the data in as it came off the socket.

To serve up the images, I did this from the shell:

while true ; do nc -q 0 -l -p 12345 < foo.jpg ; done


Then this python script received and displayed an image:

#!/usr/bin/python

import socket
from PIL import ImageFile

tcp = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
tcp.connect(('127.0.0.1', 12345))
tcp.send("1000 4")

file = open("bar.jpg", "w")
parser = ImageFile.Parser()

while 1:
jpgdata = tcp.recv(65536)
if not jpgdata:
tcp.close()
break

parser.feed(jpgdata)
file.write(jpgdata)

file.close()
image = parser.close()
image.show()

Saturday, July 10, 2010

Xorg window redraw: workaround by forcing update

When using Sketchup in wine on my ubuntu linux machine, I find that it doesn't update the screen properly. For instance, if I hit control-A to select everything, I don't see the selection until I do something else. That is, the screen seems to be one update behind.

Here's a workaround that works with Sketchup: in a separate terminal, I run:

$ watch -n 0.3 xrefresh -geometry 1x1+500+500

That uses xrefresh to create a 1x1 pixel x11 window at 500,500 on the screen every 0.3 seconds. That's enough to get sketchup to redraw itself.

If that's not enough, you can run xrefresh without the -geometry option to have it draw a window the size of the entire screen. But that's a lot more distracting.

Thursday, July 08, 2010

libgphoto2 / gphoto2 build from svn and install locally

Today I wanted to make a patch against gphoto2 (the command-line interface to libgphoto2) without overwriting the version installed by ubuntu.

So I needed to download libgphoto2 and gphoto2 from subversion and then install it to a local directory.

$ sudo apt-get install automake autoconf libtool gettext pkg-config subversion build-essential
$ mkdir gphoto-svn
$ cd gphoto-svn
$ svn checkout https://gphoto.svn.sourceforge.net/svnroot/gphoto/trunk/libgphoto2
$ cd libgphoto2
$ autoreconf -is
$ mkdir -p /tmp/gphoto2/local
$ ./configure --prefix=/tmp/gphoto2/local
$ make
$ make install
$ # neat, libgphoto2 installed to /tmp/gphoto2/local
$ cd ..
$ svn checkout https://gphoto.svn.sourceforge.net/svnroot/gphoto/trunk/gphoto2
$ cd gphoto2
$ autoreconf -is
$ ./configure --prefix=/tmp/gphoto2/local --with-libgphoto2=/tmp/gphoto2/local
$ make
$ # make install is optional; I just ran ./gphoto2/gphoto2 directly
$ # edited files, then "make" to rebuild

Earth Source / pals4wood sucks

American business is doomed. I needed to buy several thousand dollars worth of plywood. My friend recommended "PALS", a local distributor. Great, let's go to their website.

Hm, no price list online. That sucks. I guess I'll email them a list of what I need. Hm, the email bounced: mailbox full. Let's try one of the other sales reps, and mention the bounce so they can fix it. Nope, that one also bounces. Okaaayyy, well at least one of them has a @yahoo.com address listed. That's pretty sketchy, but maybe they just can't seem to get their mail service right.

Weeks go by, no answer. Thanks, guys. Something that I was ready to take care of weeks ago, credit card in hand, has been on my mind ever since, while I wait to see if you'll ever get around to answering.

I give up and order from their competitor. They don't have prices online either, so I get to go back and forth with their sales guy about what I want and what they have over the course of a week or so. And I finally give up on PALS, call in to the competitor, wait for him to pull up the email, give him my credit card info, and place the order.

Now, out of some perverse sense of business ethics, I decide to try one last time to reach PALS and let them know how broken their website is.

Searching again for "pals plywood", the first result is for "earth source forest products", whose website makes no mention of PALS. Maybe everything's fixed now?

I send them an email to info@pals4wood, the email address listed on the new website. That message bounces back (mailbox full) too, but also sends me an autoresponse... telling me to call them. Seriously, guys?

Okay, sure, why not? I'm already in it this far. I call the toll-free number listed in the email. Rings forever. Whee! Let's try the Oakland branch. Ah ha, somebody answers! Oops, wrong number.

That's right, the company with two websites, both of which list numerous email addresses, all broken, lists the wrong phone number to call when you email their info address. FML.

Wednesday, July 07, 2010

Borges

The Secret Miracle

The date was set for March 29, at 9:00 A.M. That delay ... was caused by the administrative desire to work impersonally and deliberately, as vegetables do, or planets.

----

The Aleph

I do, however, recall these lines from a satire in which he lashed out vehemently against bad poets:

This one fits the poem with a coat of mail
Of erudition; that one, with gala pomps and circumstance.
Both flail their absurd pennons to no avail,
Neglecting, poor wretches, the factor sublime -- its LOVELINESS!

It was only out of concern that he might create an army of implacable and powerful enemies, he told me, that he did not fearlessly publish the poem.

----


The Aleph (1949)

"I picture him," he said with an animation that was rather unaccountable, "in his study, as though in the watchtower of a great city, surrounded by telephones, telegraphs, phonographs, the latest in radio-telephone and motion-picture and magic-lantern equipment, and glossaries and calendars and timetables and bulletins..."

He observed that for a man so equipped, the act of traveling was supererogatory; this twentieth century of ours had upended the fable Muhammad and the mountain -- mountains nowadays did in fact come to the modern Muhammad.

Saturday, July 03, 2010

ubuntu hardy firefox 3.6.6 freezes

After today's apt-get dist-upgrade on my hardy (ubuntu 8.04) machine, firefox would freeze almost immediately and had to be killed.

Turns out there are two copies of libflashplayer.so that can get installed, one by the flashplugin-nonfree package, and one by the adobe-flashplayer .deb package that adobe distributes.

sudo apt-get remove flashplugin-nonfree and then a reinstall of the install_flash_player_10_linux.deb from adobe fixes the freeze, and also upgraded me from flash9 to flash10.

Friday, July 02, 2010

conservation of responsibility

Job descriptions usually specify that they want people with good teamwork skills. That can be good, but often it means sending out lots of emails asking other people for opinions.

In my last blog post I claimed that capacity for responsibility is a scarce resource.

So lately I've been trying to reduce the number of interrupts and decisions required for decisions that come along.

Example:

me: I'm in town. Want to have lunch?
Robert: sure!
me: [checks calendar] How about Thursday or Friday?
Robert: [checks calendar] Great, let's do Friday.
me: [checks calendar] 1pm sound okay?
Robert: sure
me: [adds it to our calendars]

Totals: 7 messages, 5 decisions, 4 uses of calendar. And that's just to *schedule* it. Without even talking about where to meet. Both of us still have to check our calendars on Friday and meet at the right time.

That could have been reduced to:
me: [adds lunch to our calendars with "hey, I'm in town" to the description]

Each time someone contacts us, we get a little anticipatory shot of stress as we get ready to read it and find out whether it's good, bad or boring. Reducing that can free up a lot of responsibility for more important tasks.

code.google.com bugs

Trying to report a bug in code.google.com project hosting, I couldn't find anything by searching for "code.google.com bugs", "google code bugs", "code.google.com issues", etc. Turns out the bug tracker is under the "support" project. (Link goes to the issues page).

Maybe this will make it more findable.

Responsibility as a bottleneck

I'm lucky enough to work at a company that tries give me all the resources I need to get my job done. Yet I've felt overwhelmed a lot lately, even, no especially when I find myself goofing off a lot. And it's because I've exceeded my capacity for responsibility.

I got the idea from hyperbole and a half, and it explains a lot of phenomena in our society.

Let's say I decide to take a for-fun class a the local college. And it's time to go to class now.

Oh wait, the car is parked at another building. And it's low on gas; should I fill up before I go? And my books are at home. Do without them?

You now have 4 things to do or decisions to make, all before class starts. Classes have about 16 - 48 class sessions. If going to class each time involves 4 little tasks, that's up to 200 little obstacles you'll have to handle, just to get to all the classes. Then there's registration, books, tests, and assignments. No wonder people don't take more classes on their own.

Calendars help, but how do you schedule keeping the gas tank full? Or remembering where you parked?

Here's the point: there's a limit to the number of things I can keep track of, and the number of decisions I can make in a day. And that holds me back more than my capacity to do the "actual" labor required to execute those decisions.

I don't surf the internet like a zombie for hours because the internet is so interesting or addicting. It's because it's stateless. I don't have to remember what I see, or take action on it in three days' time, or have it cascade into dozens of other pressing tasks.

Thursday, July 01, 2010

"Unknown end tag for </a>" error on code.google.com wiki page

See http://code.google.com/p/support/issues/detail?id=4171. I was trying to link to an image, and it apparently wants a closing <img> before it can handle the </a>

Wednesday, June 30, 2010

Space-filling fabric

I just got back my Hilbert Curve space-filling fabric from spoonflower, a site that'll print any image onto a variety of fabrics.



Space-filling fabric is suitable for tiling any plain spots on your walls, or for topological application. For storage, fold into a moebius strip and store in a Klein Bottle.

(The “Hilbert Curve” is a recursive space-filling function. If we color the corners of each square instead instead of drawing lines between them, we get the pattern you see below.)



Source code and images available at http://lunkwill.org/src/hilbert/.

Tuesday, June 29, 2010

Technical curriculum sucks

My wife just posted to her blog about how much she's enjoying the math classes she's taking at the community college.

She always did well in math, and had a friend/rival in elementary school who she always competed with to be the best in her math studies. Then in 6th grade, her teacher wouldn't let her move on to the fast track because she hadn't done enough homework to get an A, even though she was acing the tests.

Apart from feeling cheated, she was now also behind in the expected progression for technical fields. She studied English in college, and never got past college algebra.

Now she's back in school, thinking of doing a graduate degree in engineering. So she's at the community college, where she's supposed to take several years worth of prerequisites outside her final department, to get the math and science core she feels like she needs just to apply to a good grad school.

Likewise, my cousin loved astronomy in high school, where they had a neat research-oriented pilot program. Her project was to study historical photos of nebulas to see if expansion could be tracked over decades.

I encouraged her to take more when she got to college, but when she saw how many math and other science classes she'd have to take as prerequisites, she also decided to major in English.

One last related anecdote: I just met Sridhar Vembu last weekend. He found such a brain drain from the indian universities that he had trouble hiring for his indian software company. So he started a trade school. He takes 17-year-old poor kids with interest and a cursory hint of aptitude, and teaches them programming (while giving them a stipend and feeding them). The curriculum covers programming, english and math in that order of importance, and in that order of preference. The kids hate abstraction and math notation, but later appreciate it more after they've spent a few months solving practical problems in web programming. After 6-9 months, almost all of them start working for the company, and they do just as well as the college grads. As he puts it, "math is the new sanskrit".

Oh, and I believe he's taking about half and half girls/boys. (Except that more of the girls get recruited away by the colleges.)

spreadshirt sucks

You'd think that after 10 years of e-commerce, that shopping carts would be a solved problem. I just sent this feedback to spreadshirt.com.

Your shopping cart sucks. I bought a shirt from you through reddit.com, and I'm pretty sure I told it to order 3 shirts, but you only shipped and billed me for 1. So once I received it, I followed the link from the receipt to reorder. But clicking on the order number did nothing. My javascript console tells me that load_order() is undefined. I very nearly gave up at that point. So I went to spreadshirt.com directly, and clicked around until I found my order history there, and load_order() is defined from there. So somebody screwed up the javascript includes.
But it gets better. I ordered 5 shirts this time, looked for an "update" button and didn't find one, and clicked to continue the order. Only on the last page of the order process did I notice that the quantity was still at 1.

So I clicked on my shopping cart to back up the process and fix it. That showed me the item I was trying to order, and I clicked to proceed. But you were actually showing me the last page of the process again, so clicking committed the order... for one shirt.

Now on my fourth trip through the system, you at least gave me the option to cancel the order (thank you), and I once again repeated the process. And this time I found the "refresh" arrows next to the quantity. Protip: it's not actually that hard to have javascript code check the value of the quantity field when people click the button to go to the next page. You're throwing away orders and pissing people off when you expect your customers to find and click a button to tell your page something it should already know.

Finally, heading to the contact page, I get to enter a captcha (even though I'm already logged in) and type in a little tiny textbox to send you feedback, because you don't want to have to deal with the horrors of actually publishing an email address, even though you demand mine as part of the order process.

Friday, June 18, 2010

g++ error "does not exist in this scope" in karmic/lucid

g++-4.4 breaks backward compatibility for some stupid reason, so things that compiled just fine on earlier systems now break with errors like "stdout does not exist in this scope".

To fix, sudo apt-get install g++-4.2, then make sure your Makefiles or whatever are set to use g++-4.2 instead of just g++. You could probably also just apt-get remove g++-4.4, but I'm not sure if that'd break anything.

Thursday, June 17, 2010

OS statistics from wikimedia

It's surprisingly hard to find statistics on linux distribution popularity by version number.

But wikipedia to the rescue. Their squid logs break down user-agent string statistics by OS. Here's the May 2010 report:

http://stats.wikimedia.org/archive/squid_reports/2010-05/SquidReportOperatingSystems.htm

Linux seems to account for about 2% of all browsing. It looks like some browsers just report "Linux" as their OS, unfortunately. But among os-versioned browser strings, it looks like Ubuntu dominates linux distros by about 10:1, and almost all Ubuntu users are running either Lucid or Karmic (about 50/50).

Wednesday, June 16, 2010

GoogleCL rocks

indeed.

Saturday, June 12, 2010

Intuitively simple way to calculate sin and cos

A few years ago my brother in law asked how pi is calculated, and we found that it can be done as a reasonably intuitive algorithm, without any advanced math.

Ever since then, I've wondered if sines and cosines could also be calculated simply. Here's what I came up with. Please let me know if you know of a simpler way, where "simpler" means relying on fewer or more elementary mathematical principles.

Sines and cosines let us translate an angle in a right triangle into the length of one of is sides. But what is an angle? Well, on a unit circle, a 45 degree slice cuts off an arc that's 45/360ths the length of the circumference. We can cut that slice in half by finding the midpoint between the two ends of the arc, then extending that line out until it touches the edge of the circle. That slice represents 22.5 degrees. Since we have a point on the unit circle and we know its angle, the point's X and Y coordinates tell us the cosine and sine, respectively, of that angle. (And since the points are on a circle with a radius of 1, we know the hypotenuse of the right triangles is always of length 1).

Here's the same concept in pictures:





And here's python code that starts with the two points shown in the pictures, and keeps finding midpoints between them (recursively) until it gets a close enough approximation to any angle you want.


#!/usr/bin/python
"""
Released into the public domain, 12 June 2010

This program calculates the sine and cosine of an angle in a geometrically
intuitive way.

Here's how it works:

Start with a unit circle and observe that the points (1,0) and (0,1) on the
circumference of the circle are separated by 90 degrees.

The midpoint between those two points, (0.5, 0.5), bisects that 90
degree angle, forming two 45 degree angles. We can extend the line from
the origin through (0.5, 0.5) until it reaches the circumference of the unit
circle (that is, until its distance from the origin is 1), and we get
(0.707, 0.707). Thus we know that the cosine and sine of 45 degrees are both
0.707.

Likewise, we can find the cosine and sine of 22.5 degrees by taking
the midpoint between (0.707, 0.707) and (1,0), then scaling the line until
it reaches the circumference. And we can find the cosine and sine of
67.5 degrees by taking the midpoint between (0.707, 0.707) and (0, 1).

We can continue to bisect angles until we get arbitrarily close to any
angle we choose. The allowable angular error is set below as MAX_THETA_ERROR.

Note that this method is agnostic to the angular units we use. If we start off
by telling the program that (0,1) and (1,0) are separated by an angle of 90,
then the program will return a result measured in degrees.

If instead we say that (0,1) and (1,0) are separated by pi/2, we'll get a
result in radians.
"""

import math

MAX_THETA_ERROR=0.01

def cos_sin(theta, x1,y1,theta1, x2,y2,theta2):
"""cos_sin returns the (cosine,sine) of a value within MAX_THETA_ERROR
units of theta, given two points (x1,y1) and (x2,y2) that live
at angular posisions theta1 and theta2 on the unit circle. theta,
theta1 and theta2 must all have the same kind of angular unit (degrees,
radians, etc.), but this function doesn't care what that unit is or
how many of them make up a circle.

theta2 must be greater than theta1, and (x1,y1) and (x2,y2) must be
points on the circumference of the unit circle, less than 180 degrees
apart.

for example, cos_sin(30.0, 0.0,1.0,0.0, 1,0,0.0,90.0) returns
(0.866089312575, 0.499889290387), which are the cosine and sine of 30.
"""

# Uncomment this to see the successive approximations
#print "target: %.2f. (%.2f, %.2f)=%.2f (%.2f,%.2f)=%.2f" % \
# (theta, x1, y1, theta1, x2, y2, theta2)

# if one of the points is close enough to theta, we're done!
if (abs(theta1 - theta) < MAX_THETA_ERROR):
return (x1,y1)
if (abs(theta2 - theta) < MAX_THETA_ERROR):
return (x2,y2)

# the midpoint is just the average of the two points
x_midpoint = (x1 + x2) / 2.0;
y_midpoint = (y1 + y2) / 2.0;

# scale (x_midpoint,y_midpoint) by 1/midpoint_length to get a point
# exactly 1 unit away from the origin
midpoint_length = math.sqrt(x_midpoint*x_midpoint + y_midpoint*y_midpoint)
x_midpoint = x_midpoint / midpoint_length
y_midpoint = y_midpoint / midpoint_length

# the midpoint bisects the angle between the two points
theta_midpoint = (theta1 + theta2) / 2.0;

# figure out which side of the midpoint our target value theta lives on,
# and bisect the extended midpoint with one of the original points to get
# closer to the target
if (theta >= theta_midpoint):
return cos_sin(theta, x_midpoint, y_midpoint, theta_midpoint, x2, y2, theta2)
else:
return cos_sin(theta, x1, y1, theta1, x_midpoint, y_midpoint, theta_midpoint)

angle = 30.0
(cosine, sine) = cos_sin(angle, 1.0,0.0,0.0, 0.0,1.0,90.0)
print "The cosine of %.2f is %.2f" % (angle, cosine)
print "The sine of %.2f is %.2f" % (angle, sine)

Thursday, June 03, 2010

Going from odometry to position in a two-wheeled robot

My robot has two drive wheels on which I have odometry (plus some casters that we'll ignore). I want to use the odometry from the wheel encoders to keep track of where I've gone since I started counting.

Let's say the right wheel moves b inches while the left wheel moved a inches during some time interval. Assume b > a. Then if we let the robot keep moving forever with those wheel speeds, the robot will make a big circle counterclockwise on the floor about some point X. We want to find X so that we can use a and b to find the new wheel positions on the floor.



We want to find ra, the distance from the left wheel to X.

We start by imagining the circumference of the circle the left wheel would travel in: ca. ca = 2*pi*ra. The right wheel's circle will have a radius of ra+w, where w is the wheelbase of the robot.

Since the two wheels are circling the same point on the floor with the axle always pointing toward the center of the circles, we know the distances a and b will constitute the same proportion of their respective circles. (If a goes all the way around its circle, b must have gone all the way around its circle too. Likewise if a goes 1/10th of the way around, etc.)

So we know that a/ca = b/cb, which is also the proportion of the circle we traveled (if a/ca = 0.10 then we've gone 10% around the circle). Substitute and solve and we get ra = w*a / (b-a).

Great! Now we know our radius of curvature.

Next, we want to find X, the actual point on the floor that we're circling. We start by finding theta, the angle we moved around the circle, by simply multiplying a/ca by 360 (for example, 0.10 * 360 = 36 degrees). If we want it in radians instead of degrees, it's even simpler, since multiplying by 2*PI cancels out the 2*PI in ca, leaving just a/ra.



We know that the point X is ra inches to the left of Pa, along a line which also passes through Pb. (X, Pa and Pb are 2-dimensional points). We get a vector from Pb to Pa with (Pa-Pb), make it length 1 by dividing by w, then multiply by ra so it's the right length to reach from Pa to X. Then we add it to Pa so that the vector ends at X.

Now we can find the updated wheel locations on the floor by rotating Pa and Pb by theta degrees around the point X. How do we do that? Well, we translate everything so that X is at the origin, then use a rotation matrix to rotate by theta, then translate back so that X is where it started:



Here's code that implements all of that (with saner variable names), plus the case where both wheels move the same amount):


// Just some math to turn wheel odometry into position updates
// Released into the public domain 3 June 2010

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

#define PI (3.14159)

#define WHEELBASE (12.0)

// left wheel
double Lx = -WHEELBASE/2.0;
double Ly = 0.0;

// right wheel
double Rx = WHEELBASE/2.0;
double Ry = 0.0;


// given distances traveled by each wheel, updates the
// wheel position globals
void update_wheel_position(double l, double r) {

if (fabs(r - l) < 0.001) {
// If both wheels moved about the same distance, then we get an infinite
// radius of curvature. This handles that case.

// find forward by rotating the axle between the wheels 90 degrees
double axlex = Rx - Lx;
double axley = Ry - Ly;

double forwardx, forwardy;
forwardx = -axley;
forwardy = axlex;

// normalize
double length = sqrt(forwardx*forwardx + forwardy*forwardy);
forwardx = forwardx / length;
forwardy = forwardy / length;

// move each wheel forward by the amount it moved
Lx = Lx + forwardx * l;
Ly = Ly + forwardy * l;

Rx = Rx + forwardx * r;
Ry = Ry + forwardy * r;

return;
}

double rl; // radius of curvature for left wheel
rl = WHEELBASE * l / (r - l);

printf("Radius of curvature (left wheel): %.2lf\n", rl);

double theta; // angle we moved around the circle, in radians
// theta = 2 * PI * (l / (2 * PI * rl)) simplifies to:
theta = l / rl;

printf("Theta: %.2lf radians\n", theta);

// Find the point P that we're circling
double Px, Py;

Px = Lx + rl*((Lx-Rx)/WHEELBASE);
Py = Ly + rl*((Ly-Ry)/WHEELBASE);

printf("Center of rotation: (%.2lf, %.2lf)\n", Px, Py);

// Translate everything to the origin
double Lx_translated = Lx - Px;
double Ly_translated = Ly - Py;

double Rx_translated = Rx - Px;
double Ry_translated = Ry - Py;

printf("Translated: (%.2lf,%.2lf) (%.2lf,%.2lf)\n",
Lx_translated, Ly_translated,
Rx_translated, Ry_translated);

// Rotate by theta
double cos_theta = cos(theta);
double sin_theta = sin(theta);

printf("cos(theta)=%.2lf sin(theta)=%.2lf\n", cos_theta, sin_theta);

double Lx_rotated = Lx_translated*cos_theta - Ly_translated*sin_theta;
double Ly_rotated = Lx_translated*sin_theta + Ly_translated*sin_theta;

double Rx_rotated = Rx_translated*cos_theta - Ry_translated*sin_theta;
double Ry_rotated = Rx_translated*sin_theta + Ry_translated*sin_theta;

printf("Rotated: (%.2lf,%.2lf) (%.2lf,%.2lf)\n",
Lx_rotated, Ly_rotated,
Rx_rotated, Ry_rotated);

// Translate back
Lx = Lx_rotated + Px;
Ly = Ly_rotated + Py;

Rx = Rx_rotated + Px;
Ry = Ry_rotated + Py;
}

main(int argc, char **argv) {
if (argc != 3) {
printf("Usage: %s left right\nwhere left and right are distances.\n",
argv[0]);
return 1;
}

double left = atof(argv[1]);
double right = atof(argv[2]);

printf("Old wheel positions: (%lf,%lf) (%lf,%lf)\n",
Lx, Ly, Rx, Ry);
update_wheel_position(left, right);
printf("New wheel positions: (%lf,%lf) (%lf,%lf)\n",
Lx, Ly, Rx, Ry);
}

Wednesday, June 02, 2010

atmel atmega32 avr-libc interrupt example

Edit: Fixed a bug in the example code where I tried to do _BV(foo|bar), which doesn't work at all. Changed them to (_BV(foo) | _BV(bar)). Also added a #define for _BV in case you don't already have it. I think this code is correct, but I haven't tried it.

I wanted to read a pair of quadrature encoders with my atmega32, so I needed to enable the INT0 and INT1 pins. Incidentally, if you don't mind throwing away half the resolution of your encoder, you can get away with using only one interrupt per encoder. (You put one of the pair of sensors on an interrupt, and the other one on a regular GPIO pin. You get interrupts half as often, and the other sensor tells you which way you moved).

Here's the code I used. The compiler complained about using obsolete avr-libc identifiers, but it seems to work fine.


#include <avr/interrupt.h>
#include <avr/signal.h>

// Just count the number of interrupts we see
int interrupt_counter = 0;
SIGNAL(SIG_INTERRUPT0) {
interrupt_counter++;
}

// I got lots of random resets until I added this handler.  So apparently you shouldn't enable
// an interrupt unless you have a handler installed.
SIGNAL(SIG_INTERRUPT1) {
interrupt_counter++;
}

And then in my init code:

#define _BV(x) (1 << (x))

// setup for servicing INT0, INT1 interrupt pins

// generate an interrupt on any logical change
MCUCR |= _BV(ISC10);
MCUCR &= ~_BV(ISC11);

MCUCR |= _BV(ISC00);
MCUCR &= ~_BV(ISC01);

// enable the interrupt pins
GICR |= _BV(INT1) | _BV(INT0);


// Set d2 and d3 to be inputs
DDRD &= ~(_BV(PD2) | _BV(PD3));

// Pullups off
PORTD &= ~(_BV(PD2) | _BV(PD3));

Thursday, May 27, 2010

Another test post

Wow, I love posting to blogger from the command line

Monday, May 24, 2010

Test post

This post generated via the gdata API

Monday, May 17, 2010

Getting my ar5212 wifi card to search for an access point

On ubuntu karmic, I uninstalled network-manager and tried to configure my Thinkpad T41p's ar5212 wireless connection manually.

iwconfig wlan0 essid MyEssid
iwconfig wlan0 txpower auto

When I run iwconfig, it says "not associated" and doesn't appear to be looking for an AP. It'll stay like this forever.

But if I run dhclient wlan0, within a few seconds it'll associate and get an address as expected.

Friday, May 14, 2010

sudo sucks

sudo helpfully won't let you do anything as root anymore if you disturb its precious 440 permissions. Because, you know, having root be able to write the file would be INSECURE. FML.

Edit: Whee!! It even helpfully segfaults on karmic:


$ sudo bash
sudo: /etc/sudoers is mode 0640, should be 0440
Segmentation fault

Monday, May 10, 2010

Avoiding the annoying "no write since last change" vim message

Whenever I'm on a new machine, it drives me nuts when the default vi install won't let me :bn without saving first. Adding ":set hidden" to my .vimrc fixes that, letting me switch buffers without saving first.

Sunday, April 25, 2010

Working with named pipes in tcl

Today I wanted to pipe lines of output from a C program into a TCL program using a named pipe, so that I didn't have to start them up at the same time. First I created the pipe with mkfifo:

$ mkfifo foo

Then here's the magic incantation in TCL to open the pipe and run a function every time something comes in:

set fifo [open "foo" {RDWR NONBLOCK}]
fconfigure $fifo -blocking 1
proc read_fifo {} {
global fifo

gets $fifo x
puts "x is $x"
}
fileevent $fifo readable read_fifo

Then when I write to the fifo, my program prints them:

$ echo "asdf" > foo

Make sure you write newlines when you write to the fifo so that gets doesn't block (or use read instead).

Saturday, April 24, 2010

Chicken tortilla casserole

Quick and easy.

1 can cream of mushroom soup
1 can cream of celery soup
1 onion, chopped
3 boneless chicken breasts, diced
1 can chopped tomatoes (or use fresh tomatoes)
1 small can green chiles (or fresh)
1 small can olives
4 or more corn tortillas, cut into strips
8-16 ounces grated mozzarella or cheddar cheese
1 cup salsa

Mix up all the liquid and small stuff in a glass 9x13" casserole dish, then mix in the tortillas and chicken. Top with cheese. 350F for one hour.

Sunday, April 18, 2010

v4l2 example

Update: Updated the sample code to spit out a grayscale ASCII PGM on stdout so you can actually see what it's
capturing.

Looks like the video4linux project could use a convenience library for people who want to do simple things. But at least they have good example code.

The official v4l2 example worked pretty well for me. It worked fine with my capture card, but I got "VIDIOC_S_FMT error 22, Invalid argument" errors when I tried it with my webcam. Switching to "V4L2_PIX_FMT_YUV420" from "V4L2_PIX_FMT_YUYV" fixed it. I also simplified it a bit, taking out the command line options, MMAP code and the USERP (which didn't work for me anyway). It gets the example down from 675 lines to a little under 300, and makes it a little closer to my purposes.


/*
* V4L2 video capture example
*
* This program can be used and distributed without restrictions.
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#include <fcntl.h> /* low-level i/o */
#include <unistd.h>
#include <errno.h>
#include <malloc.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <sys/time.h>
#include <sys/mman.h>
#include <sys/ioctl.h>

#include <asm/types.h> /* for videodev2.h */

#include <linux/videodev2.h>

#define CLEAR(x) memset (&(x), 0, sizeof (x))

struct buffer {
void *start;
size_t length;
};

static int fd = -1;
struct buffer *buffers = NULL;
static unsigned int n_buffers = 0;

static void errno_exit(const char *s) {
fprintf (stderr, "%s error %d, %s\n", s, errno, strerror (errno));

exit (EXIT_FAILURE);
}

static int xioctl(int fd, int request, void * arg) {
int r;

do r = ioctl (fd, request, arg);
while (-1 == r && EINTR == errno);

return r;
}

static void process_image(const void *p) {
fputc ('.', stdout);
fflush (stdout);
}

static int read_frame(void) {
struct v4l2_buffer buf;
unsigned int i;

if (-1 == read (fd, buffers[0].start, buffers[0].length)) {
switch (errno) {
case EAGAIN:
return 0;

case EIO:
/* Could ignore EIO, see spec. */
/* fall through */

default:
errno_exit ("read");
}
}

process_image (buffers[0].start);

return 1;
}

static void mainloop(void) {
unsigned int count;

count = 100;

while (count-- > 0) {
for (;;) {
fd_set fds;
struct timeval tv;
int r;

FD_ZERO (&fds);
FD_SET (fd, &fds);

/* Timeout. */
tv.tv_sec = 2;
tv.tv_usec = 0;

r = select (fd + 1, &fds, NULL, NULL, &tv);

if (-1 == r) {
if (EINTR == errno)
continue;

errno_exit ("select");
}

if (0 == r) {
fprintf (stderr, "select timeout\n");
exit (EXIT_FAILURE);
}

if (read_frame ())
break;

/* EAGAIN - continue select loop. */
}
}
}

static void uninit_device(void) {
unsigned int i;

free (buffers[0].start);
free (buffers);
}

static void init_read(unsigned int buffer_size) {
buffers = calloc (1, sizeof (*buffers));

if (!buffers) {
fprintf (stderr, "Out of memory\n");
exit (EXIT_FAILURE);
}

buffers[0].length = buffer_size;
buffers[0].start = malloc (buffer_size);

if (!buffers[0].start) {
fprintf (stderr, "Out of memory\n");
exit (EXIT_FAILURE);
}
}

static void init_device(char *dev_name) {
struct v4l2_capability cap;
struct v4l2_cropcap cropcap;
struct v4l2_crop crop;
struct v4l2_format fmt;
unsigned int min;

if (-1 == xioctl (fd, VIDIOC_QUERYCAP, &cap)) {
if (EINVAL == errno) {
fprintf (stderr, "%s is no V4L2 device\n",
dev_name);
exit (EXIT_FAILURE);
} else {
errno_exit ("VIDIOC_QUERYCAP");
}
}

if (!(cap.capabilities & V4L2_CAP_VIDEO_CAPTURE)) {
fprintf (stderr, "%s is no video capture device\n",
dev_name);
exit (EXIT_FAILURE);
}

if (!(cap.capabilities & V4L2_CAP_READWRITE)) {
fprintf (stderr, "%s does not support read i/o\n",
dev_name);
exit (EXIT_FAILURE);
}

/* Select video input, video standard and tune here. */

CLEAR (cropcap);

cropcap.type = V4L2_BUF_TYPE_VIDEO_CAPTURE;

if (0 == xioctl (fd, VIDIOC_CROPCAP, &cropcap)) {
crop.type = V4L2_BUF_TYPE_VIDEO_CAPTURE;
crop.c = cropcap.defrect; /* reset to default */

if (-1 == xioctl (fd, VIDIOC_S_CROP, &crop)) {
switch (errno) {
case EINVAL:
/* Cropping not supported. */
break;
default:
/* Errors ignored. */
break;
}
}
} else {
/* Errors ignored. */
}


CLEAR (fmt);

fmt.type = V4L2_BUF_TYPE_VIDEO_CAPTURE;
fmt.fmt.pix.width = 640;
fmt.fmt.pix.height = 480;

// This worked with my capture card, but bombed with
// "VIDIOC_S_FMT error 22, Invalid argument" on my Logitech QuickCam Pro 4000
// fmt.fmt.pix.pixelformat = V4L2_PIX_FMT_YUYV;
// This worked on the logitech:
fmt.fmt.pix.pixelformat = V4L2_PIX_FMT_YUV420;

fmt.fmt.pix.field = V4L2_FIELD_INTERLACED;

if (-1 == xioctl(fd, VIDIOC_S_FMT, &fmt))
errno_exit("VIDIOC_S_FMT");

/* Note VIDIOC_S_FMT may change width and height. */

/* Buggy driver paranoia. */
min = fmt.fmt.pix.width * 2;
if (fmt.fmt.pix.bytesperline < min)
fmt.fmt.pix.bytesperline = min;
min = fmt.fmt.pix.bytesperline * fmt.fmt.pix.height;
if (fmt.fmt.pix.sizeimage < min)
fmt.fmt.pix.sizeimage = min;

init_read (fmt.fmt.pix.sizeimage);
}

static void close_device(void) {
if (-1 == close (fd))
errno_exit ("close");

fd = -1;
}

static void open_device(char *dev_name) {
struct stat st;

if (-1 == stat (dev_name, &st)) {
fprintf (stderr, "Cannot identify '%s': %d, %s\n",
dev_name, errno, strerror (errno));
exit (EXIT_FAILURE);
}

if (!S_ISCHR (st.st_mode)) {
fprintf (stderr, "%s is no device\n", dev_name);
exit (EXIT_FAILURE);
}

fd = open (dev_name, O_RDWR /* required */ | O_NONBLOCK, 0);

if (-1 == fd) {
fprintf (stderr, "Cannot open '%s': %d, %s\n",
dev_name, errno, strerror (errno));
exit (EXIT_FAILURE);
}
}

int main(int argc, char **argv) {
char *dev_name = "/dev/video1";

open_device(dev_name);
init_device(dev_name);
mainloop();
uninit_device();
close_device();

exit(EXIT_SUCCESS);
return 0;
}

Friday, April 16, 2010

ubuntu karmic grub error: "no such device" uuid/search nonsense

After cloning my recent karmic koala (9.10) install to another machine, I was annoyed that it wouldn't boot. It said:


error: no such device: ....

Failed to boot default entries.


Karmic now locates disk by UUID instead of the more traditional /dev/sda notation, which sucks when you want to clone a disk. But it's easy enough to fix.

To get it to boot once, use "e" from the grub menu to edit the command line. Remove the entire line that says:


search --no-floppy --fs-uuid --set ...


Then change the root= option in the next line to use /dev/sda1 instead of mounting by UUID:


/libux/boot/vmlinuz-... root=/dev/sda1 ro quiet splash


Then hit control-x to boot with those settings.

To fix it for good once the system boots, sudo gedit /etc/default/grub and uncomment this line:


# Uncomment if you don't want GRUB to pass "root=UUID=xxx" parameter to Linux
GRUB_DISABLE_LINUX_UUID=true


Next, sudo gedit /etc/fstab and replace the UUID=... with /dev/sda1 for the / partition and /dev/sda5 for the swap partition (assuming you had ubuntu use the whole disk during install).

Finally, sudo gedit /usr/lib/grub/grub-mkconfig_lib and find this line (line 174 for me):


echo "search --no-floppy --fs-uuid --set ${fs_uuid}"


Change it to:


echo ""


Finally, sudo update-grub2 to write the changes to disk. Then cross your fingers and reboot.

Wednesday, April 14, 2010

Running gnome applications over ssh

If you "ssh -X" into some machine and can run X apps fine, but can't run some gnome apps, and get errors about dbus sockets, run "export `dbus-launch`" from your ssh session to set up the environment variables you need.

Sunday, April 11, 2010

Ubuntu Linux Sketchup using Wine

Update2: I found a much more general solution to the redraw problem.

Update: I'm not sure if that worked or not. I think it improved the situation, but didn't fix the refresh problems entirely.

I've been using Sketchup successfully for quite a while now in Ubuntu linux. The trick was to install the wine PPA in order to get a more recent version of wine than Ubuntu distributes by default.

However, at home I had screen update problems: for instance, when I'd mouse over a face with the push/pull tool, it wouldn't draw in the crosshatching until I left the face.

But today I figured out how to solve the refresh problems, thanks to a comment in the wine appdb entry for sketchup 7. I ran nvidia-settings, then set:

NVIDIA X Server Settings manager checked
Antialiasing Settings - Override Application - Off
Anisotropic Filtering - Override Application - 1x

The next time I started up sketchup, it worked fine.

Saturday, April 10, 2010

balancethebudget.com

This is a pretty neat site that shows how the federal budget breaks down and lets you try your hand at balancing the budget:

http://balancethebudget.com/#

Seems to be unbiased. I was recently surprised by these numbers about state and local spending, which show, for instance, that we actually spend more on education tha...n defense. So it'd be interesting to see state and local budgets represented as well:

http://www.usgovernmentspending.com/year2006_0.html

I'd also like it to break down my own tax burden, since it's hard to contextualize billions and trillions. I'd rather see it as: "you spent $17 this year on farm subsidies, $7313 on defense, $7819 on public schools..."

I also think it'd be neat to let people see what would happen if individual tax checks went directly to specific programs, until those programs filled up. That is, I could enter my approximate income or how much my total tax burden was. Then a roulette wheel would spin, and it'd have a N percent chance of landing in the "defense" category, since defense uses N% of the budget. Then it'd drill down into the defense budget, making weighted-random choices until it tells me that my entire burden went to buying 8% of a single missile, for example.

Friday, April 09, 2010

Android Scripting Environment: launch a script from adb

ASE is pretty slick; makes it very easy to do simple things in Android. Here's how to launch a script from the command line after using "adb shell" to get a shell prompt:


# Launch an activity in the background:
$ am start -a com.google.ase.action.LAUNCH_SCRIPT -n com.google.ase/.activity.AseServiceLauncher -e com.google.ase.extra.SCRIPT_NAME test.py

# Launch an activity in a new terminal:
$ am start -a com.google.ase.action.LAUNCH_TERMINAL -n com.google.ase/.activity.AseServiceLauncher -e com.google.ase.extra.SCRIPT_NAME test.py


And here's the java file where they name all the intents in ASE.

Tuesday, March 16, 2010

calcdeps.py "Missing provider" error

Today I was trying to use the Google Closure compiler to build a single .js file out of several source files and their closure library dependencies:

closure-library-read-only/closure/bin/calcdeps.py -p closure-library-read-only -i bar.js -i foo.js -o compiled -c closure-compiler/compiler.jar > compiled.js

I kept getting errors like this:

Exception: Missing provider for (foo.Foo)

That sucked, since foo.js with its goog.Provide("foo.Foo") was right in the same directory with bar.js, and I even specified it explicitly on the command line.

Turns out I needed to specify "-p ." so that it'd look in the current directory for the dependency. So with a command line of:

closure-library-read-only/closure/bin/calcdeps.py -p . -p closure-library-read-only -i bar.js -i foo.js -o compiled -c closure-compiler/compiler.jar > compiled.js

I got:

Exception: Duplicate provide (goog.async.DeferredList) in ...

That seemed even weirder. Turns out calcdeps doesn't like having the same subdirectory show up twice in -p arguments. That is, "-p ." and "-p closure-library-read-only" was causing it to find the closure library twice. Okay, so we take out the second -p:

closure-library-read-only/closure/bin/calcdeps.py -p . -i bar.js -i foo.js -o compiled -c closure-compiler/compiler.jar > compiled.js

Now I get:

ERROR - namespace "foo.Foo" cannot be provided twice

Almost there: it doesn't like having foo.js explicitly provided. This actually worked:

closure-library-read-only/closure/bin/calcdeps.py -p . -i bar.js -o compiled -c closure-compiler/compiler.jar > compiled.js

Sunday, March 14, 2010

Universal Muses

The universe halted. This would have been traumatic for its inhabitants, had they been able to notice. But their brains had halted along with everything else, so they didn't mind.

"More elevator music. I'm telling you, happiness doesn't make for good art," said Cyn.

"I suppose you're right. I guess I just have a soft spot for them." Fob sighed, twiddling the values in the configuration file.

He pressed a button and erased the 10e80 particle simulation. 175 billion galaxies ceased to be simulated.

Cyn softened. "Look at it this way:the suffering is what gives their lives meaning. No suffering means no art, and no art means there's no point wasting computer time on them." Cyn and Fob shared time on a supercomputer with 10^73 gigabytes of memory, or about 100 times the number of particles in our universe. It had been respectable when it was built, but was starting to show its age.

"Yeah, I guess," said Fob, distracted. "How about this? I'm going to restore the water planet from the pre-life checkpoint, but turn up the resource saturation and sunlight, so they'll really eat each other alive."

"If you really think that'll help. At least turn up the quantum granularity so it doesn't take forever to run."

Fob laughed. "Okay, okay. The poor physicists. Maybe they'll start writing requiems."

Life bloomed and ended. Then bloomed again, and ended. On the third try it caught.

"Giant lizards. Cute."

Cyn and Fob searched the history books, as soon as there were history books. "Hey, some of this architecture is pretty good."

Fob checked another result. "And check out the music. There's a whole cluster of them right around 1800."

"Meh, it's okay. Make this one go deaf and see what happens."

Monday, March 01, 2010

XMPP / asmack / android / Google Talk

OK, I finally figured out how to send and receive XMPP instant messages from my gmail account using asmack with an Android 2.1 AVD. For some reason, the event-driven message receive code doesn't work, but this polling example code does. Here's my latest source:


// DON'T FORGET TO INCLUDE THE INTERNET PERMISSION IN YOUR MANIFEST.XML

package com.example.HelloFormStuff;

import android.app.Activity;
import android.os.Bundle;
import android.util.Log;
import android.view.View;
import android.view.View.OnClickListener;
import android.widget.Button;

import org.jivesoftware.smack.Chat;
import org.jivesoftware.smack.ChatManager;
import org.jivesoftware.smack.MessageListener;
import org.jivesoftware.smack.PacketCollector;
import org.jivesoftware.smack.XMPPConnection;
import org.jivesoftware.smack.XMPPException;
import org.jivesoftware.smack.filter.AndFilter;
import org.jivesoftware.smack.filter.FromContainsFilter;
import org.jivesoftware.smack.filter.PacketFilter;
import org.jivesoftware.smack.filter.PacketTypeFilter;
import org.jivesoftware.smack.packet.Message;
import org.jivesoftware.smack.packet.Packet;

public class HelloFormStuffActivity extends Activity {
public int state = 0;
private static final String TAG = "HelloFormStuffActivity";

/** Called when the activity is first created. */
@Override
public void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);

new Thread(new Runnable() {
public void run() {
//XMPPConnection xmpp = new XMPPConnection("jabber.iitsp.com");
XMPPConnection xmpp = new XMPPConnection("gmail.com");
try {
xmpp.connect();

// for other jabber accounts, truncate after the @
//xmpp.login("username", "password");

// for gtalk / gmail, include the @
xmpp.login("your-gmail-account@gmail.com", "your-gmail-password");

} catch (XMPPException e) {
Log.v(TAG, "Failed to connect to " + xmpp.getHost());
e.printStackTrace();
}
ChatManager chatmanager = xmpp.getChatManager();
Chat newChat = chatmanager.createChat("friend@gmail.com", new MessageListener() {
// THIS CODE NEVER GETS CALLED FOR SOME REASON
public void processMessage(Chat chat, Message message) {
try {
Log.v(TAG, "Got:" + message.getBody());
chat.sendMessage(message.getBody());
} catch (XMPPException e) {
Log.v(TAG, "Couldn't respond:" + e);
}
Log.v(TAG, message.toString());
}
});

// Send something to friend@gmail.com
try {
newChat.sendMessage("OMNOMNOM");
} catch (XMPPException e) {
Log.v(TAG, "couldn't send:" + e.toString());
}

// Accept only messages from friend@gmail.com
PacketFilter filter
= new AndFilter(new PacketTypeFilter(Message.class),
new FromContainsFilter("friend@gmail.com"));

// Collect these messages
PacketCollector collector = xmpp.createPacketCollector(filter);

while(true) {
Packet packet = collector.nextResult();

if (packet instanceof Message) {
Message msg = (Message) packet;
// Process message
Log.v(TAG, "Got message:" + msg.getBody());
}
}

}

}).start();

//setContentView(this);
}
}

Friday, February 26, 2010

Android XMPP

Update: working code for send/receive over XMPP from gtalk / non-gtalk accounts

So, apparently XMPP support was briefly part of the official android SDK, but they took it out again.

There's a respected library called "smack", but it doesn't work with android out of the box.

There's a hack of smack for android called asmack, and that seems to work for me, at least for sending messages.

I haven't figured out how to make it work with talk.google.com, but I created an account at jabber.iitsp.com and was successful in sending an IM from my android.


package com.example.HelloFormStuff;

import android.app.Activity;
import android.media.MediaPlayer;
import android.os.Bundle;
import android.view.View;
import android.view.View.OnClickListener;
import android.widget.Button;
import android.widget.Toast;

import org.jivesoftware.smack.Chat;
import org.jivesoftware.smack.ChatManager;
import org.jivesoftware.smack.ConnectionConfiguration;
import org.jivesoftware.smack.MessageListener;
import org.jivesoftware.smack.XMPPConnection;
import org.jivesoftware.smack.XMPPException;
import org.jivesoftware.smack.packet.Message;

public class HelloFormStuffActivity extends Activity {
public int state = 0;

/** Called when the activity is first created. */
@Override
public void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
//setContentView(R.layout.main);

XMPPConnection xmpp = new XMPPConnection("jabber.iitsp.com");
try {
xmpp.connect();
xmpp.login("username","password"); // just username, no @ sign
} catch (XMPPException e) {
// TODO Auto-generated catch block
System.out.println("Failed to connect to " + xmpp.getHost());
e.printStackTrace();
}
ChatManager chatmanager = xmpp.getChatManager();
Chat newChat = chatmanager.createChat("destination@example.com", new MessageListener() {
public void processMessage(Chat chat, Message message) {
Toast.makeText(HelloFormStuffActivity.this, message.toString(), Toast.LENGTH_SHORT).show();
}
});

try {
newChat.sendMessage("IMing from my android");
} catch (XMPPException e) {
Toast.makeText(HelloFormStuffActivity.this, "ERROR", Toast.LENGTH_SHORT).show();
}
...


Don't forget to add the INTERNET permission to the manifest.xml, or you'll get "not connected" exceptions.