Sunday, April 26, 2009

Elbow power: Things going *bump* in the night

Whenever some form of hardware doesn't work, many people bash it or elbow it, hoping and praying that this desperate measure might solve the problem. So, I figured, what if you could harness this form of kinetic input to control your computer

What if you could set the computer up so that when you slam it with your elbow, and like yours was the elbow of the Fonze, it kills Firefox (porn surfers rejoice), or renews your network connection, switches keyboard layout, switches desktop background, the possibilities are limited only by your imagination.

Disclaimer: Your computer will stand up to some degree of slapping and bashing about, it does have a breaking point. Use this at your own peril. I do not take responsibility for whatever damage you inflict upon your computer with this program.

Instead of buying expensive gyroscopes, accelerometers or hacking your wiimote, there's a very cheap way of making this a reality. The poor man's accelerometer is nothing but a computer mouse. Place it on top of your computer (make a casing for it if you want it to look neat). Now, the problem is how to read the data from the mouse. In Linux, this is a trivial matter. All hardware in Linux is a file, and you can simply open the mouse like any other old file.


Poor man's accelerometer.


What protocol the mouse device uses is a different pony. There's several mouse protocols, and they are all slightly different. The basic PS/2 protocol has 3 byte packets, where the first byte is buttons and some flags, and the second is relative motion in the X direction, and the third is relative motion in the Y direction. Older 2 button mice with no scroll wheel is generally PS/2 mice. Newer mice allow for longer packets, but they are generally backwards compatible with PS/2. There is more information on the protocol on Wikipedia if anyone is interested.

Great. So let's write a program that we can use to track jolts. The algorithm is going to be like this:

1. Open the device.
2. Read data from the file descriptor.
3. If the magnitude of the relative motion exceeds some threshold value, return from the program.

Add some red carpet code to allow customization, and you'll end up with this:

kinput.c
Makefile

Compile with make, and you're (hopefully) go.

Now that this helper program is done, what you need to do is write a shell script that performs some action when it detects a bump.

#!/bin/bash

# DISCLAIMER! Your computer will stand up to some degree of
# slapping and bashing about, it does have a breaking
# point. Use this at your own peril. I do not take
# responsibility for whatever damage you inflict upon
# your computer with this program.


KINPUT=/path/to/kinput # Change this to where you put kinput
MDEVICE=/dev/input/mouse1 # Change this to some appropriate device
THRESHOLD=10 # Increase this if it goes off too easily
TIMEOUT=1 # Change this to how long you want to sleep
# before waiting for another motion
WHAT="killall firefox-bin" # Change this to what you want performed on a bump

while [ 1 ]; do
if "$KINPUT" -d "$MDEVICE" -t "$THRESHOLD"; then
echo "Bump detected!"
eval "$WHAT"
else exit; fi # Exit if something has gone wrong
sleep "$TIMEOUT"; # Sleep a moment
done


... and that's it. Running this in the background will allow you to solve your problems with your elbow. Correctly configured, you should only need to nudge your computer slightly. Bashing your computer too hard may harm your hard disks and cause problems in the wiring, so you shouldn't do that.

You could conceivably also use this program to detect mouse motion for other purposes. Running it in the background in the login manager and tracking the regular mouse could allow you to set up your computer to grab snapshots with your webcam of everyone who tries to log into your computer (which may or may not be legal where you live/work) and then email them to you.

There are some problems that might arise with this though, the most likely is that you don't have permission to read from the mouse device. Instead of running the script as root (are you insane?), it's a lot better to allow the mouse device to be read by all users, or add trusted users to the same user group as the mouse.

Was reddited, some replies and comments

Yeah, so my previous two posts ended up on reddit and gizmodo, and got a fair amount of comments. Thank you for the 15 minutes of fame. It will naturally all go to my head, and I'll be expecting flamboyant Sovieteqsue monuments to be built depicting myself at any moment. ... On a more serious note, I figured I ought to reply to some of the comments I got here and on various other places:

Several people suggested that one could simply just pipe the data to the soundcard, like this
cat data > /dev/dsp
and then on the receiving end simply
cat /dev/dsp > data
In an ideal environment with no noise, no echoes and with hardware that has a completely ideal acoustic properties, this would probably work if you started broad casting and receiving at exactly the same moment. In the real world, all it does is produce a lot of noise.

Other people were upset over the fact that I did not use the best possible algorithms, suggesting that Fourier transforms is CPU intensive and I got crappy baud rate. This is all true, I could have used impulse response filters and gotten hundreds of kbps in speed out of it. But creating a high speed software modem wasn't the mission (and I never presented it as such). It was a hack, for the fun of it. What they are saying is basically that MacGyver would have been more effective if he simply carried a gun. He would unfortunately also have been no where near as entertaining to watch. I deliberately chose crude components (such as a DFTs filter instead of a FFT filter or a FIR filter) and simple algorithms to make it understandable for people who don't have degrees in signal processing.

Then there were the people that suggested I simply connected the two computers with male-male audio cables. This would have worked too. But I avoided this because of two reasons. The first reason is that I didn't have any cables of that nature laying about, and the second is that the laptop isn't grounded, which means that the stationary computer and the laptops don't share a common ground. Static buildup in the laptop might lead to a power surge upon connecting it to the laptop, that potentially could damage both of the computers, especially given the low end nature of laptop sound cards.

Wednesday, April 22, 2009

File transfer over sound card II: Phase Shift Keying

I've played around further with the file transfer over sound card idea, and developed a more advanced method that uses a technique called Phase Shift Keying. Similar techniques are used in wireless network connections.

Instead of coding data in the amplitude or frequency of the carrier signal, phase shift keying (as the name indicates) encodes it in the phase. It is significantly faster, partially because it doesn't waste as much time with silences, but also because it's more reliant.



I must admit it's a good thing I wasn't drinking coffee when tinkering with this technique, because it's very likely I would have blown coffee through my nose and onto the keyboard when I first saw transfer rates over around 200 baud, with no random garbling. I'm sure it's possible to go higher with better equipment than my cheaper-than-dirt headsets that came with my webcams.

How it works

The mathematics of the method is as following, if the signal is expressed as

S(t) = A0 sin(ωt + φ)

Then the Fourier transform of S would give you

Fω(S) = A0 e

Normally, one would simply discard the phase factor by taking the norm of the frequency coefficient, but for this we're going to make use of it. You can't just yank the phase out of the expression as it is though (phase is always relative to something). But! You can compare this phase with the phase of the last sample you got (this is called differential phase-shift keying, by the way).

So, I propose the following scheme:
Δφ Meaning
0 Still the same sample as last time
π / 2 Next bit is 1
π Next bit is 0
3 &pi / 2 New byte


This has several nice features. You can jump into the signal almost anywhere and at most one byte will be garbled. Furthermore, everything has an uniform length, so bit rate doesn't depend on how many ones and zeros is in the byte.

Modifying the fourier code from the last blog post on sonic file transfers, the following function will allow you to make use of the phase:

double fourier1p(double x_in[], double n, int length, double* phase_r, double* phase_i) {
double x_complex[2] = { 0, 0 };
int i;

for(i = 0; i < length; i++) {
x_complex[0] += x_in[i] * cos(M_PI * 2 * i * n / (double) length);
x_complex[1] += x_in[i] * sin(M_PI * 2 * i * n / (double) length);
}

double norm = sqrt(x_complex[0]*x_complex[0] + x_complex[1]*x_complex[1]);
*phase_i = x_complex[1] / norm;
*phase_r = x_complex[0] / norm;
return norm / length;
}



So how do we figure out the phase difference? Let φ be the phase of the current sample, and ψ be the phase of the previous sample.

ee-iψ = ei(φ - ψ) = cos(φ - ψ) + i sin(φ - ψ)

The real term will dominate if φ - ψ ~ nπ , and the imaginary term will dominate if φ - ψ ~ (n+1)π/2 and their sign will further tell you if n is odd or even.

The demodulation algorithm is fairly short:


double carrier_phase[2];
double carrier_strength = fourier1p(dbuffer, (float) length * carrier / (float)rate, length, &carrier_phase[0], &carrier_phase[1]);

if(carrier_strength < threshold) continue;

double delta_re = carrier_phase[0] * old_carrier_phase[0] + carrier_phase[1]*old_carrier_phase[1];
double delta_im = -carrier_phase[1]*old_carrier_phase[0] + carrier_phase[0] * old_carrier_phase[1];

if(delta_re * delta_re > delta_im * delta_im) { /* Phase difference is a multiple of pi */
if(delta_re > 0); /* No change */
else {
bit_data = bit_data * 2;
}
} else {
if(delta_im > 0) {
bit_data = bit_data * 2 + 1;
} else {
if(isprint(bit_data)) printf("%c", bit_data);
else printf("<%.2x>", bit_data);
bit_data = 0;
}
}
old_carrier_phase[0] = carrier_phase[0];
old_carrier_phase[1] = carrier_phase[1];




For several reasons, it's a good idea to use a pretty high carrier frequency for this method. At some point, your speaker or microphone will not be able to process the information, so you'll want to stay under that, but a high frequency will result in less perturbation of the signal since fairly few objects have eigenfrequencies in the 5 kHz range or higher, and even oscillation at harmonic frequencies drops off pretty significantly at such frequencies.

Sources

The complete source code for the program:

generate_psk.c
analyze_psk.c

You may have grabbed these the last time, but they are slightly altered now, so get them again:

fourier.h
fourier.c

You also need the playback and record programs I posted in the previous post. They haven't changed though.

playback.c
record.c


Using

Same old warning: Never try these programs with your headphones on. THEY MAKE LOUD NOISES! It is possible to configure these programs to make noises way louder than you ever imagined your headphones could make. You can damage your hearing when playing with audio programming. Tinnitus isn't fun.

To transfer a file (let's transfer /etc/fstab again), put the microphone next to the speaker, pre-type the following on the transmitting computer (without running it):

>./generate_psk -r 48000 -c 8000 -b 100 /etc/fstab | ./playback -r 48000

Type the following on the receiving computer:

>./record -r 48000 > mydata

Press enter on the transmitting computer. Be quiet (this should be fairly quick. Maybe 30 seconds?) When the high pitched noise stops, press Ctrl+C on the receiving computer's terminal.

Running
./analyze_psk -r 48000 -c 8000 -b 100 mydata
on the receiving computer should retreive the message.

The parameters are
-r : Sample rate -- carrier frequency and signal quality
-c : Carrier frequency -- limits baud rate and signal quality
-b : Baud rate -- determines how fast the transfer is

What works and doesn't with the sampling rates and frequencies is a bit tricky. It all boils down to Nyquist-Shannon. That theorem is all innocent looking, until you make it mad. Then it turns green and grows three times it's size and goes on a furious rampage through your hopes and dreams.

Anyways, have fun experimenting with this technique.

2011 update: Moved the sources to a github repo.

Saturday, April 18, 2009

File transfer over sound card

Before I even start, a word of warning: Never try these programs with your headphones on. THEY MAKE LOUD NOISES! It is possible to configure these programs to make noises way louder than you ever imagined your headphones could make. You can damage your hearing when playing with audio programming. Tinnitus isn't fun.

This will be you if you don't take my warning seriously:



Background and problem

I have an old laptop laying about. A while back, I was in a bit of trouble getting it to work. It's so old that several parts of it has shut down. The USB system is fried, and it can't read modern burned DVD:s. I needed to move software to it to get the network up and running again. The only peripheral that was working (besides the keyboard and the screen) was the sound card. It was running an old version of Slackware.

Ah, I thought, and wrote a program that encoded data in sound. When I did it back then I used a bad algorithm. It was very noise sensitive and tried to do too much at the same time. As of then, I've improved (and simplified) the concept to using a sort of pulse width modulation (an idea I got when I read about the ZX Spectrum Tape Loader.)

The basic protocol is trivial:

For every character:

For every bit:
Send a short pulse if the bit is 1.
Send a long pulse if the bit is 0.
Send a silence.
Send a very long pulse (4 times as long as the shortest pulse).
Send a silence.


This is nice and not very error prone. The end-of-byte signal means that errors don't taint their neighbors.

The crux isn't the signal generation (which is laughably trivial), it is the analysis on the receiving end; or rather dealing with the noise in the signal. The naive implementation would be to sum the square of the signal amplitude over time periods--the presence of a sine wave would converge towards some value and a silent signal would converge towards 0. In a noisy signal, it almost always converges towards something non-zero, so no such luck.

So, the second approach would be to use a Fourier transform, to select the part of the spectrum where our signal resides (400 Hz is what I chose).

A simple implementation of such a function looks like this:

double fourier1(double x_in[], double n, int length) {
double x_complex[2] = { 0, 0 };
int i;

for(i = 0; i < length; i++) {
x_complex[0] += x_in[i] * cos(M_PI * 2 * i * n / (double) length);
x_complex[1] += x_in[i] * sin(M_PI * 2 * i * n / (double) length);
}
return sqrt(x_complex[0]*x_complex[0] + x_complex[1]*x_complex[1]) / (double) length;
}


Where x_in is a series of numbers between -1 and 1, and n is the modified frequency (which is to say: length * frequency / rate). This function would give you a number corresponding to how much of a given frequency is in a sample. But you can do one better: Harmonics. Almost every loudspeaker will produce some level of harmonics even though the signal broadcasted is a plain sine wave with no harmonics.

So, to check if our signal is in a given segment, the following code can be used:
double sum = 0;
for(harmonic = 1; 2*harmonic < length / frq; harmonic++) {
sum += fourier1(data, frq * harmonic, length);
}


To check if the signal is present in a given signal, you must compare this against some form of threshold. What's a good threshold varies with noise. A bad threshold value may either cause the program to interpret random noise as meaningful data, or reject good data as random noise.

if(sum > threshold) { /* Signal is present in data block */ }
else { /* Signal isn't present */ }


The protocol described above can be realized with the following code:

if(sum < threshold) {
if(signal_length) {
if(signal_length > 10) {
if(bit != 0) printf("(?)");
bit = 0;
signal_length = 0;
} else {
bit_data = 2 * bit_data + (signal_length < 6);
if(++bit == 8) {
printf("%c", bit_data);
fflush(NULL);
bit = 0;
}
}
signal_length = 0;
}
} else {
signal_length++;
}


This does work. It's not just some crazy pipe dream. Following is all the code you need for transferring files from two computers using their soundcards.



Garbled transfers like this may soon arrive through a soundcard near you.


Utility programs

Before I get deeper into to the main program, I'm going to contribute some utility programs. record and playback. They are both wrappers for OSS, and reads and digests data from the soundcard; or writes digested data to the soundcard at given sample rates. They deal in signed char arrays only, and may convert them for the soundcard. Exactly what they do and how they work is a bit off topic, so I'll just post the code listings.

playback.c
record.c

The broadcasting end
As previously discussed, the broadcasting part of the program is pretty simple. The only real gotcha is the sample rate factor in the frequency. Since we're generating a signal with N bytes per second, we must decrease our frequencies by a factor 1/N. Beyond that, it's really quite trivial.

generate.c

The math parts
Almost there now. We just need some fourier transforms and things of such nature. The analysis end of the program can also make a XPM file of the frequency spectrum of the input, which is why you see a bunch of XPM code.

fourier.c
fourier.h

Finally... the receiving end

Most of what this one does has already been discussed. The threshold is hard-coded. You may want to change it or whatever.

analyze.c

... one file to compile them all, and into objects link them

Makefile

To compile, you just run
> make

Using the programs

Before I get to actually using the programs, I repeat my warning: Never try these programs with your headphones on. THEY MAKE LOUD NOISES! It is possible to configure these programs to make noises way louder than you ever imagined your headphones could make. You can damage your hearing when playing with audio programming. Tinnitus isn't fun.

Not there yet. It's quite an elaborate matter to use all these programs. First you'll want to generate your raw sound data. Let's transfer /etc/fstab (don't do this as root! Something might go horribly wrong!)

First, attach the microphone on the receiving end to the speakers on the transmitting end. Use duct tape or whatever. I had an old hands free headset that I wrapped so that the microphone was held in place by the earpiece.





On the transmitting computer, run the following command:
> ./generate -b 25 -r 48000 -o out.data /etc/fstab


Enter, but do not start the following on the transmitting computer:
> ./playback -r 48000 < out.data # don't press enter yet!


Now, on the receiving computer, run the following command:
> ./record -r 48000 -o out.recdata

Note that out.recdata will grow very fast. In this case, 48000 bytes/second.

Run the command pre-typed in the transmitting computer's terminal. Be very quitet, and listen to the noise coming from of the speaker. This may take quite some time. Practice your Zen. Find enlightenment. When the noise stops, press Ctrl+C on the receiving computer.

Run the following command on the receiving computer:
> ./analyze -b 25 out.recdata


Watch a semi-garbled /etc/fstab be printed across your screen. The -b switch is to be taken with a grain of salt. It is proportional to how fast the transfer is. It must (obviously) be the same on the receiving and the transmitting end. I've gotten it to work at -b 50 -r 48000. Sample rate (-r) increases the processing time, but it also allows faster transfers. There are a few fixed possible sample rates, 8000 always works, others that are supported by most soundcards are 11025,16000,22050,24000,32000,44100 and 48000.

So, in summary: -b determines how fast the transfer is, and the maximum possible transfer speed is limited by the sampling rate.

If it doesn't work, try playing what you recorded with playback. If you can hear and distinguish the beeps, then so should the computer be able to. If record or playback fails, chances are you don't have permissions to access /dev/dsp. If all you get is character salad, fiddle with threshold in analyze.c.



An even more elaborate version of this program is described in File Transfer Over Sound Card II - Phase Shift Keying.

2011 update: Moved the sources to a github repo.

Friday, April 17, 2009

Kernel hacking: ov51x-jpeg module with 2 webcams

This is partially a note-to-self, and pretty esoteric. If you don't get what I'm talking about, don't worry. This probably doesn't apply to you.

I have sent this fix to the module creator, but until a solution becomes available in the actual module, I'm sharing the information here.

The following changes are made entirely at your own peril. I take absolutely no responsibility for whatever doom it may bring upon your computer. It may cause your computer to go up in flames, your girlfriend to cheat on you and horribly disfiguring and agonizing diseases to be inflicted upon you. Don't say I didn't warn you.

I have had problems with getting the ov51x-jpeg kernel module to accept multiple webcams with my OV519 cameras. I'm quite simply running out of USB bandwidth. Now the module has built in functionality to handle this: You modprobe with the argument "cams=2". This did not work for me. I was still using too much bandwidth.

If you make the following alteration to ov51x-jpeg-1.5.9.

File: ov51x-jpeg-core.c
5435 case BRG_OV519:
5436 if (cams == 1) size = 896;
5437 else if (cams == 2) size = 512;
5438 else {

is changed into
5435 case BRG_OV519:
5436 if (cams == 1) size = 896;
5437 else if (cams == 2) size = 512;
5438 else if (cams == 3) size = 384;
5439 else {


Unload the ov51x-jpeg module. Recompile the module sources. Load with

modprobe ov51x-jpeg cams=3

... and it works. At least for me.