Awesome Geek Blog

Built myself a new computer

2012-01-28T06:20:00.000-08:00

Had some money to spare, so I invested them in a new computer.

Ignore the computer screen. It's from back in like 2007 or something.

Shopping list looked like this:

* Intel i7 2600k (this is purely for number crunching)
* Asus P8Z68-V PRO/GEN3
* Fractal Design R3
* ~~Corsair TX 750 V2~~ This was a lemon. Bought a Corsair HX 750 locally and will be demanding a refund for the defective TX.
* Corsair 2x4Gb 1333Mhz XMMS3
* MSI GeForce GTX570 Twin Frozr III OC/PE
* Intel SSD 320 Series, 40 Gb SATA II
* Western Digital Caviar Black, 500 Gb, SATA III

Went for around $2000.

I couldn't be happier with my purchase (except for the dud that was the TX 750). The CPU is wonderful for number crunching, the GPU packs on hell of a wallop for it's fairly modest price, the chassis is beautiful and quiet. The mother board has some quirks when it boots up, running through EFI/BIOS multiple times, (I think it's because it has multiple SATA controllers), but I can live with that.

The oddy-C

2011-10-17T13:52:00.000-07:00

C was my first real programming language. Some people think that's a slightly crazy language to start off with. But I don't regret it one bit.

Certainly, as the old adage goes; the C is a harsh mistress, but you've got to ask yourself if you want to be a lambda-lubber, or if you want to man up and grow a pair of C-legs.

But making that decision is merely the beginning. Learning C is an epic journey fraught with danger, as the very notion of a mere mortal mastering the C angers to Poceidon, the god of the C, with a Unix beard that puts Stallman to shame. Poceidon, wielding his mighty trigraph, will divert a Cyclone into your path; guide you into perils such as a the lair of the witch Circe, cursing your stack with a bad return address; and let Cirens try to lure you off the segmentation falls.

Surviving that, you must seek vengeance for the injustice the gods of programming have put you through. First you must enter the gates of kernel space, guarded by the three-headed guard dog Cerberos. Once in kernel space, you must do the seemingly impossible and tear a hole in the virtual paging table and travel to physical address 0. There, you will find the old modes shackled. You must free them. Let Real Mode roam free again! This will bring on Lambdarøk, the prophesied end of high level programming, where the world-tree withers into an undirected graph and the mighty garbage collector devours itself.

It's a pity C doesn't have exceptions, because if it did, I could have worked in a deadliest catch joke.

Dennis Ritchie is dead

2011-10-13T13:45:00.000-07:00

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

int main(void) {
  puts("RIP");
  return EXIT_SUCCESS;
}

I wonder if he will haunt the standards committee until they finalize the new C1x standard. I imagine if he does choose to haunt something, it's either that, or the wander the halls of compiler manufacturers that have still yet not implemented all C99 features.

A brief review of my remote development woes

2011-09-18T05:35:00.000-07:00

I decided a while back I wanted to do remote C++ development. That is, do all the development on one machine (preferably in a nice IDE), and all the building/running/debugging on another machine. I found three options:

Eclipse CDT is supposed to support this
... with something called RSE. But as documentation is confusing at best, and everything about it is unintuitive, it's very hard to set up. After a long while of trying to make sense of it all, I barely got it working. And then it all crashed every 5 minutes.

NetBeans supports this natively
Netbeans is by far the best option I've found. Set-up is a breeze, everything is seamless and works really well. The only drawback is that Netbeans has a very slow C++ parser which makes it quite painful to work with. So I imagine that the same set-up for java development would be nothing but joy.

Code::Blocks supports this through a third party application called Uniwin
It isn't tremendously hard to set up, but as far as development environments go, C::B feels amateurish and dated.

I suppose the conclusion I'm forced to draw is that the world isn't ready for remote C++ development yet, but if you absolutely have to do it, then NetBeans is your best shot.

Netbeans is the best option at this point

Preprocesing C with python

2011-09-06T06:52:00.000-07:00

Heh, I cooked together a small shellscript that allows you to pre-process C code (technically also C++-code, if you make a minor alteration to the script) with python.

It's set up to echo everything that doesn't begin with "%%", and pass those lines to python.

#!/bin/bash

tmpsource=`mktemp`
cat $1 |
        sed 's/^\([^\%]\+[^\\]*\)\\\(.*\)$/\1\\\\\2/g' |
        sed 's/^\([^\%]\+.*\)$/print """\1"""/g' |
        sed 's/^[\%][\%]\(.*\)$/\1/g' | python - > $tmpsource
shift
gcc -x c $@ $tmpsource
rm $tmpsource

It's used like this:

./cppy.sh sourcefile.c (flags-for-gcc)

For example, the following code prints "Hello World".

#include <stdio.h>

%%print "char* c = \"Hello World\";";

int main(int argc, char* argv[]) {
        printf("%s\n", c);
        return 0;
}

Dragonslaying in the bowels of Tunguska

2011-08-24T10:06:00.000-07:00

It all started with a very small patch I committed to the Tunguska CVS a few days ago, it moved some stuff off the heap onto the stack (these are small objects, so no, it's not what you're thinking) and made a few other very minor changes. It ran fine... then, and I was arguably a bit sloppy with the sanity checking as I thought it was all so small. But as it is with memory errors, they occasionally hide and pop up in the nastiest of places later.

Today I found several bugs that have been festering in the code base since the dawn of time (since I've been working on the project highly intermittently, and some of the code started out being C rather than C++, some of the older code is quite dubious). I've mostly fixed the bugs now, except one particularly vexing bug in the assembler.

The assembler uses yacc and lex to parse the source files. If you weren't aware, yacc takes a special file format and generates a Lovecraftian horror in source-code form. If there's a hell for programmers are sent to hell, I imagine it involves debugging yacc output with gdb.

--edit--

I just committed and checked-out the source code. This fixed the assembler. I made a copy of the old source directory for reference. diff agrees the files are 100% the same. The clean routine in my makefile generates all generated code, objects, and binaries.

It's stuff like this...

Anyway, I think this highlights just how much Tunguska is in need of a design overhaul.

Large buddhabrot fractal

2011-07-16T03:23:00.001-07:00

So I've been messing around with the buddhabrot fractal again (credit to Melinda Green for it's discovery). I do this at least once most summers. Tradition I guess. This time, with more hardware at my disposal than previous years, and some work put into optimizing the algorithm by introducing a bit of a handwavy heuristic for which areas are inside the Mandelbrot set, I've managed to generate a very large map of the fractal.

Just now I ran a test-run of 20,000 x 20,000 pixels, and this is with 16 samples per pixel, as I've hit a brick wall in terms of system memory, but supersampling is still viable. I set iteration depth to 1,000,000. Run time was around one and a half hour on my laptop which has an i5 M450 CPU, and the code is multi-threaded and makes use of all of the cores and hyper-threading and whatnot.

The result is a png file that is almost 400 Mb in size, which poses a bit of a logistics problem. The result is absolutely stunning. I would love to share it with the world, but I have no idea how to go about it. Maybe using the google maps API? That still poses a problem of where to host almost half a gigabyte of image data.

Anyway, until I figure that out, here are some samples (the full image consists of 625 tiles of this size, though some of the edge tiles are all black).

The "C/C++" myth

2011-06-27T06:54:00.000-07:00

Seeing C and C++ referred to as "C/C++" perplexes me to no end. Writing "C/C++" makes no sense at all. You almost always want either C or C++, as the two have widely disparate areas of suitability.

The two languages seem to be shrouded in a good number of myths, that I would like to debunk

Myth: There is a language "C/C++": There is no language "C/C++". C and C++ have very little in common. Yes, I know C++ evolved from C, but that fact aside, the two languages are very different. C++ has a lot more in common with basically any given object oriented language than it does with C.
Myth: C++ is the next version of C: C++ is C with an object system grafted onto to it (object orientation is not a more evolved form of imperative programming, even though it's more suitable for some tasks).

The next version of C is C1x.
Myth: C++ is backwards compatible with C: At some point, it was. But today, C++ is not backwards compatible with C, with void pointers and whatnot.
Myth: If you know C++, you know C: This is a superficial truth. You may know the syntax of the language, but this does not make you a good C programmer. The C language has a large number of limitations, and to overcome these requires a lot of experience in C.

C++ has other ways of overcoming these limitations, and there generally is no way to directly translate these to C. Finally, imperative C++ code is bad C++ code, not C code.

As a side note, this is why speed comparisons between C and C++ are typically pathological. If you compile a piece of C code in C++, it will run at the same speed as it would in C. But code in the wild is not going to be side-stepping the object system like that.

Static webpages

2011-06-16T03:23:00.000-07:00

If your webpage has nothing but static content, it should not be generated dynamically. There should not be a multi-second load time for a static webpage with 2 kB worth of content.

If you do dynamically generate static content, then you, fine sir, are an idiot.

Thanks for your patience. I needed to vent this, having used a university webpage that is like the antichrist of sensible web application design. Go go application state stored in session variables rather than the URL, so that browser navigation doesn't work and the whole application periodically crashes forcing you to re-start from the main page.

The square root of 2, and multiples of 7

2011-06-14T11:37:00.001-07:00

The square root of 2 has a mathematical curiosity. It starts with a long string of multiples of 7.

For reference
\[ \sqrt{2} = 1.4142135623730950\dots \]
\[ \frac{\sqrt{2}}{7} = 0.2020305089104421\dots \]

I've known about this for years. Chalked it up to a mathematical coincidence, and not really thought about it. What connects two, seven and ten (where ten comes from the numeric base used)? The answer is so simple

\[ \sqrt{\frac{1}{2}} = 0.7071067811865475 \dots \approx 0.7 \]

Neat function

2011-05-31T10:35:00.000-07:00

Stumbled on this neat function that acts like a singularity, except drops to zero instead of diverging within a neighborhood dependent on a parameter $\delta$.

\[
x^{-n}e^{-\frac{1}{2}\left(\frac{\delta}{x}\right)^{2n}}\approx\begin{cases}
x^{-n} & |x|>\delta\\
0 & |x|<\delta
\end{cases}
\]

For $\delta > 0$, $n\in\mathbb{N}_{1}$. I imagine this may help with unstable simulations of inverse square law type interaction.

Integral is really nice too (for n > 2), by diverging for small δ, means it could possibly used for renormalization work?
\[
\int_0^{\infty} dx\ x^{-n}e^{-\frac{1}{2}\left(\frac{\delta}{x}\right)^{2n}}\sim\delta^{-n+1}
\]

See WA for some plots.

Imaginary numbers are silly

2011-05-13T11:04:00.000-07:00

So, the imaginary constant is a pretty silly constant. While there is nothing wrong with them, they're defined in a very awkward fashion. A much more elegant way of doing it is by using 2x2 matrices.

Define the imaginary constant to be
\[
i=\left(\begin{matrix}0 & -1\\
1 & 0\end{matrix}\right)
\]
which is the rotation matrix for a 90 degree clockwise rotation of a two dimensional vector.

Let's further implicitly put an identity matrix next to all numbers. For example, consider a complex number
\[
z=a+bi=\left(\begin{matrix}a & 0\\
0 & a\end{matrix}\right)+\left(\begin{matrix}0 & -b\\
b & 0\end{matrix}\right)=\left(\begin{matrix}a & -b\\
b & a\end{matrix}\right)
\]
It's trivial to show that this obeys all that we'd expect from complex algebra (and complex conjugate is the same as transposing the matrix). Wasn't that nice? No obscure voodoo mathematics. Just a simple 2x2 matrix. We don't need to justify the existence of matrices. They are not just some ugly trick that's used to simplify calculations.

Superfluous computer ventilation

2011-02-25T17:01:00.001-08:00

My old workstation has been re-assigned to server duty, but unfortunately, it is quite noisy. For a while I've considered various ways of reducing the noise. I tried cleaning the fans up a bit, which reduced the noise a lot, but you could still hear it across my apartment.

During cleaning, I noticed that one of the fans contributed the bulk of the noise (as I ran case less for a moment, forcing me to unplug that particular fan.) So I thought, maybe I should replace it? Fans aren't terribly expensive.

But then I started thinking, maybe I don't need it? It is after all a headless computer, and the GPU is one of the big culprits when it comes to generating heat. So I unplugged it and ran a load test (first 100% cpu on both cores, and next 100% cpu + heavy disk load).

For a moment, my heart was racing as I watched the temperatures rise in a nearly vertical incline on the plot. But then they started to settle. ... at around 50 C. Very nice. I don't think I actually need to replace the fan. It'll just stay unplugged. Unfortunately, this was not the unidentified bad fan that starts making a racket every couple of hours until you apply a spot of percussive maintenance to it to quiet it down.

I attached the load test data to the post for reference.

Cute demonstration of how random phase shifts lead to decoherence

2011-02-18T06:41:00.000-08:00

This blog needs more physics.

I've been looking around for a barebone example of quantum decoherence that doesn't needlessly complicate matters with spin states and the like. Finding no satisfactory example, I whipped one up myself.

In the quantum world, probabilities are described by the probability amplitude (let's call it ψ(x)), while in the classical world, it's enough to use probability densities, the absolute square of the probablity amplitude (i.e. $|\psi(x)|^2$).

Decoherence is basically the process in which the quantum description of probability becomes equivalent to the classical description of probability through random phase changes.

Let's consider a superposition of two wavefunctions:

\[\psi(x) = e^{i\xi}\psi_1(x) + e^{i\phi}\psi_2(x)\]

The probability density to measure the wavefunction at position x is now

\[|\psi(x)|^2 = |\psi_1(x)|^2 + |\psi_2(x)|^2 + e^{i(\xi-\phi)}\psi_1(x)\psi_2(x)^*\]\[+ e^{-i(\xi-\phi)}\psi_1^*(x)\psi_2(x)\]

The first two terms are phase independent and corresponds to classical, additive probabilities, and the last two are quantum terms that do not appear in classical physics. Also note that they depend on phase.

So let's suppose we introduce a mechanism that at each time step has a miniscule probability of introducing a small fixed phase shift in the wavefunctions.

Fiddling around a bit with expectation values it's straightfoward to show that this leads to a brownian walk in the phase difference δ=ξ-φ.

It's well known that Brownian motion is diffusive, and can suitably be described with the heat equation. So the probability density for the phase difference is governed by

\[\frac{dP(\delta)}{dt} = \alpha \frac{d^2P(\delta)}{d\delta^2}\]

This gives solutions on the form

\[P(\delta) = \exp(-\frac{\delta^2}{\alpha t})\]

The phase factor next to the attenuation terms must now be re-written to take into account the diffusion of the phase.

\[e^i(\delta) \rightarrow \int d\delta P(\delta) e^{i\delta} \]

This is a standard integral that is easy to evaluate, giving

\[ \int d\delta P(\delta) e^{i\delta} = e^{-\alpha t} \]

So the revised probability density is

\[|\psi(x)|^2 = |\psi_1(x)|^2 + |\psi_2(x)|^2 + e^{-\alpha t}(\psi_1(x)\psi_2(x)^* + \psi_1^*(x)\psi_2(x))\]

In summary, brownian-like phase shifts leads to linear attenuation of the interference terms, and a decoherence time of α^-1. This is of course a very simplistic model, and great care must be taken to ensure that such a process actually is applicable in order to avoid pathological cases.

Take for example $\psi_1(x)=\psi_2(x)$, this is clearly an unphysical case as there is no way to independently phase-shift just one of the completely indistinguishable wavefunctions. If you do never the less feed this case to the model, it tells you very adamantly that either $\psi(x)=0$, or $2=1$.

Follow-up Feb 25: For a less hand-wavy and more intuitive theoretical demonstration, it's easy to show that mounting a device over one of the gaps in a double slit experiment that introduces random phase shifts to particles passing through it leads to the vanishing of the interference pattern. One can then move that action to a medium in the chamber, and get the same results (where attenuation depends on time-of-flight between slit and screen. For explicit time dependence, a moving screen could be introduced).

Remote control over RSS

2011-01-31T08:01:00.000-08:00

I've been pondering ways of remote controlling a computer in an environment that is hostile towards incoming connections (e.g. behind a router, behind a firewall, lacking previlegies to open ports, etc.) without the use of external servers dedicated to offer a connection between the two, and believe I've come up with something that would work.

Web 2.0 is very much designed to be machine friendly. So much so it should be possible to feed instructions to a computer over an RSS feed (twitter, blogger, most forums, ...). The problem with this is that these feeds are made for text (which can be transformed fairly freely without degrading the message), whereas computer instructions are very sensitive to changes in case and the insertion or removal of newlines or spaces.

So another layer is necessary. Suppose a message is encoded in base16 or base64, that way we can strip all non-significant symbols before parsing the message. But then the problem becomes identifying the message. To do that, a magic token can be attached to the beginning of the message. Say 'sgurocks' (as it's previously been established that praise of SGU is rare indeed, we an assume it won't appear in any text). Next, a 4-digit hexadecimal length is added. Next a hash (md5? Again hex-encoded) is applied to verify that this is indeed a valid message. Finally, the message itself is appended.

This message encoding protocol has the benefit of being possible to scrape off any text-based medium, be it XML or HTML or whatever, and it's easy enough to encode that it should be possible to do with a greasemonkey script. Of course the computer we wish to control should only poll the RSS feed one or two times a minute to spare the server unnecessary traffic, so there would be a significant delay to this.

The server could use one of the many APIs available for webservices to respond in kind (except, without the encoding.)

I've done proof of concept testing on the RSS-scraping and decoding part, and the scheme seems to work fairly well.

Impressive Dutch coin, courtesy of Free Software

2011-01-29T16:24:00.000-08:00

I was doing an unrelated google image search when an unusual looking coin caught my eye.

I was intrigued, and found my way to a blog post by the coin's designer, who it turns out created it with open source software and python code (and this is a real coin that's gone to production, not just a mock up that stayed on a computer). A lot of thought went into the design, and the blog post was well worth the read.

The post in question can be found here: How to Make Money with Free Software @ pythonide.blogspot.com

"Security"-pestering, follow up

2011-01-18T13:28:00.000-08:00

It would seem that there's a final step as part of the pester-into-change strategy outlined in the previous blog post. When you've had your pester screen up for a month or two, you force the change upon everyone who didn't yield to the pester screen. Both of the sites I listed in the previous post (youtube and facebook) just pulled that.

So the strategy for introducing potentially unwelcome changes as a whole seems to look like this:

Introduce new feature, allowing people to use it if they want to.
Add annoying screen after every log-in that urges people to adopt feature for "security" reasons.
Force the change on everyone, whether they want it or not.

"Security"-pestering

2010-12-30T17:49:00.000-08:00

This is bugging the hell out of me. You log into this web service, right, and what greets you? A screen asking you to do something you don't want to do in the name of security, and this doesn't go away until you do what they want, resulting in a sort of extortion scenario where you have to give in to their dubious proposition in order to be left alone.

These two haunt my web experience:

Youtube wants me to link my gmail account with my youtube account for "security". There is no "Sod off, I don't want to."-button, just one that has it pestering me about it again the next time I log in.
Facebook wants to know my cell phone number and another email address. For "security". Every time I log in, I get this screen. There doesn't seem to be any way of getting rid of it.

No, I'm not going to give in to their pestering. It's just going to drive me away from their services.

Grand rant about non-physicists and their misconceptions and attitudes

2010-12-08T09:16:00.001-08:00

These misconceptions and attitudes generally held by non-physicists have been bothering me for quite some while. So I'll list them here.

Energy

A peculiar error by people who do not understand physics is to attach "energy" to things for no reason. Don't get me wrong, if a machine does work, clearly some sort of energy transfer is going on, but this is implicitly true, so there's no need to say a magnet lifts things with magnetic energy. It lifts them with magnetic force¹. It's also okay to just say magnetism.

There's also an alarming number of people whose idea of energy is alarmingly similar to old aether theories, as though it's some sort of incandescent medium that permeates reality.

The amazing pi!

"I'll memorize hundreds of digits of this mysterious, never ending number!" It's just a constant, and for almost all applications, you'll never need more than around 10 digits (say you make a meter-wide circle and want to know the circumference, then the error in your answer will be on atom scale if you have much more than 10 digits of pi, and at that level, measurement errors will dominate). Therefore, the irrational quality of pi is a curiosity at best. Nothing to write home about.

Furthermore, 2pi is the better constant. At almost no place in mathematics does pi appear where a constant equal to 2pi wouldn't make more sense.

Einstein

Einstein did a lot of great things for certain, but his fame is way disproportionate to what he actually did. He's become some sort of patron saint/greek style personified concept deity of intelligence. People call you "an Einstein" when you're reasonably smart and/or a physicist. He did a lot of groundbreaking work, but this cult of personality is way out of hand (besides, everyone knows Feynman's cult of personality is the one to root for.)

If anyone deserves to be the patron saint of intelligence, perhaps C.F. Gauss is a better choice, seeing as how you can't swing a bracket in mathematics without hitting something named after him. Or Newton for that matter.

Schrödinger's cat

Erwin Schrödinger was one of the founding fathers of quantum mechanics. But what is he remembered for? His thought experiment about a cat. And this is a fairly questionable thought experiment that overall probably gives you more misconceptions than it does insights. I really wish people would think "equation" and not "cat" when they hear his name.

¹ Someone is bound to sit at home with a copy of Griffiths' Electrodynamics in their hands all riled up about how it says the magnets do no work. This is an incomplete statement. While the Lorentz force does no work, spin is none the less acted upon by a force proportional to ∇B.

System instability, revisited

2010-12-07T02:04:00.000-08:00

So, my system has been fairly stable since the last incident, but now it's taken another step on it's slow journey towards oblivion.

This time I was visited by seasonally appropriate graphical artefacts (i.e. small white boxes appearing and disappearing randomly). I was running the system under average to high load when they paid a visit. Switching from proprietary nvidia drivers to "nv"-drivers fixed it slightly, but it quickly turned worse so I rebooted. The artefacts mostly vanished, ~~but some persist around alpha-blended graphics~~. Edit: This appears to be some sort of CPU saving mechanism in KDE 4. It mostly happened around widgets, but re-sizing them caused it to vanish.

Fig: Residual graphical artefacts. The entire screen looked like this, or worse. I tried to screenshot the mess at the time, but at that point, it was so bad I couldn't distinguish any dialogs, and therefore had no way of saving it.

This would indicate that the source of the problem is either the graphics card, or the memory corrupting the nvidia driver.

I'll run some more memtest86, and if that doesn't find anything, do a GPU transplant.

Very peculiar system instability event

2010-12-04T09:36:00.000-08:00

Just now I came home from some grocery shopping, popped the dinner into the microwave, and turned on my main desktop computer. From the LILO-menu, I decided to boot Windows. Got as far as "Disk Read Error", and then the system rebooted.

Ok, I thought, well, that drive is getting a bit old. But now LILO didn't even boot, I got the good old "L01 L01 L01 L01"-of-death screen. Not just a bad block, but some sort of progressive failure?

Okay, I thought, maybe I'll try the other LILO install I have on another MBR in case of emergencies like this. "L01 L01 L01"... and then it surprised me by actually loading, but that was as far as it went, as it behaved very erratically. I didn't manage to actually boot anything, and even navigating the menu was sluggish.

Now, the prospect of simultaneous disk failure seems a bit far fetched, and no other electronics have failed so I didn't consider a power spike particularly likely either. The CPU seems fine, as BIOS worked without trouble during the incident, and system temperature was also fine so a fan failure doesn't seem a likely explanation either.

Anyway, I'm digressing from the story. At this point I shut it down and let the computer rest for a while as I ate my now cooked dinner. Then I tried again, got as far as "L01 L01 L01" and then the main LILO suddenly worked. I managed to boot into Linux, and there were no obvious signs of error. So I rebooted into Windows, and it worked too.

I have no idea what this event was about, the most plausible explanation I've come up with is some sort of interference from the microwave (which I use on a daily basis, typically with the computer on and with no issues).

So fingers crossed that this was some sort of fluke event that won't repeat itself, but in case it was it's way of saying "Goodbye cruel world!", I've made several off-site backups of everything of importance.

Edit: Additional tests

I've performed some diagnostic tests on the machine, ran a bad block search with fsck and a memtest86 sweep. No errors. But still some residual instability. It seems that if I get past booting, everything is stable and okay, but there's a chance things go bad at the boot loader or during the kernel loading. Maybe the MRB, or some other early block (that wouldn't have been tested by fsck) is damaged?

Base inversion and digit ordering

2010-12-02T04:29:00.000-08:00

Here's a mathematical curiosity I stumbled onto. The direction in which we write our numbers is just a convention, and as is the numeric base we write them in. But the two are actually closely related. A switch in direction is equivalent to inverting the base.

Consider a number in base 10.

123.4₁₀ = 1 × 10² + 2 × 10¹ + 3 × 10⁰ + 4 × 10^-1

In base 1/10, this would be written as

4.321_1/10 = 4 × 10^-1 + 3 × 10⁰ + 2 × 10¹ + 1 × 10²

Clearly, these are one and the same.

That is all.

Installing Slackware on a semi-isolated system

2010-11-29T06:24:00.000-08:00

My ancient laptop is a never-ending fountain of joy. It's so old and battered, most forms of communication are dead, to the extent where I've had to transfer network card drivers over the sound card (as documented here). Having done that, I managed to get a working Linux system up and running. But today it was that time of year again: Upgrade time. Adding to that, the file system was getting is a bit dodgy, so I decided to wipe the system and install anew.

The obvious question is this: Just how do you install (Linux) on a system with no CD, DVD or USB capabilities. PXE is one option, and I could go to all the trouble of setting that up, but there's another option: Making a boot-partition out of the swap partition. If you can install from an USB stick, a floppy disk or a CD, there should be no reason you couldn't do the same from a regular hard drive partition, right? It turns out that this feat isn't all that difficult at all, it's just poorly documented. So I'm documenting what I did here.

This is done at your own risk. Make sure to backup your data. I'm writing this assuming you have enough of an idea how to modify the instructions to suit your system. If you are not reasonably familiar with Slackware, this guide is not for you.

I'm going to be using the swap partition, which was called /dev/hda2 on my old install. This varies from system to system. Please make sure you're very certain which partition you want to install on.

First step is to disable the swap partition.
# swapoff -a

Next step is to create a file system on this partition.
# mkfs.ext2 /dev/hda2

Mount it
# mount /dev/hda2 /mnt; cd /mnt

As I'm going for a network install, I only want to download the isolinux and kernels directories of the Slackware tree. Here I chose the slackware.no-mirror because it's one of the faster ones nearby.

# wget -nv -r ftp://ftp.slackware.no/slackware/slackware-13.1/isolinux
# wget -nv -r ftp://ftp.slackware.no/slackware/slackware-13.1/kernels

The next step is to add the install partition to lilo, by adding the following section

image = /mnt/kernels/hugesmp.s/bzImage
  root=/dev/hda2
  label=SlackwareInst
  initrd=/mnt/isolinux/initrd.img
  append="load_ramdisk=1 prompt_ramdisk=0 rw SLACKWARE_KERNEL=hugesmp.s"

Update lilo by running
#lilo -v

And reboot. Select SlackwareInst. Follow the instructions, and do a network install (I used the same FTP server as I grabbed the kernels and initrd stuff from). Easy as that.

Argh! Blogger needs a better comment management system!

2010-07-29T08:26:00.000-07:00

I found this little surprise in my inbox today:

As Blogger's comment management system is somewhat lacking, I had to go through the emails one by one to get the link to the relevant blog posts, scroll down to the spam comment, click the thrash can icon, load another page, and then click a button to finally delete the comment. Which is fine for individual spam messages. But when you get a barrage of 30 of them in one go, it really highlights just how lacking the comment management system in blogger is.

That is all. Just had to vent my frustration a bit.

HTML5 video and canvas hacks

2010-07-08T13:30:00.001-07:00

This is not my handiwork, but it's just so damn awesome the world needs to see it:

http://forums.xkcd.com/viewtopic.php?f=11&t=62173

It's a series of simple, yet clever hacks that allow, among other things, client-side transformation of video to ASCII art, and direct pixel manipulation of a video. All done in javascript.

I've also been messing around with fonts from Google's web font directory in the blog's stylesheet. It's nice to see something else than the same old standard web fonts, but I think it's very much a novelty buzz that will likely wear of and get obnoxious fairly quickly. But until then, enjoy (if you don't like it, ... consider that it could have been Papyrus or Comic Sans. So enjoy the fact that it's not.)

Command Line Google

2010-06-18T23:08:00.000-07:00

Saw this on the google opensource blog: Introducing Google Command Line Tool. The actual project is here if you want to save a click.

I whole-heartedly approve, and figured it couldn't possibly suffer from sharing. And alas no, I didn't post this with googlecl.

That is all.

Compartmentalizing your online identity

2010-06-16T14:57:00.001-07:00

While, yes, most everything you post online remains online for quite some time, and there's not really a whole lot you can do about that.

There are however quite simple means to deal with that -- means you use offline all the time without thinking about it: Social circles. You most likely wouldn't dream of bringing your boss or parents out drinking with your drinking buddies? That's because they're from different social circles, and meet different identities (your professional identity, and your casual friends-and-family identity respectively). And such social circles are typically quite stratified.

There is nothing keeping you from arranging similar systems online. Nom de plumes and aliases have been used for ages in the analog world, and with good reason. While using different account for different social circles is no guarantee information won't seep between them (same as rumors do in the analog world), it will at least limit this information bleed.

Actually realizing this is quite easy depending on which networks you're using, most of them send you an email when something interesting has happened, so you really don't have to constantly check every single account you have (which, even if it's just two per social network site, can reach quite large numbers.)

Though there are actual account-switching issues as, I think, you're not expected to have more than one online identity: Gmail for example has a quite frustrating bug that sometimes occurs when you log out and forget to close every single google-related browser tab you have open before logging into another account, where it breaks the session and you have to go to the google main page and log out from there.

Another option would of course be using different social networking sites for different social circles, but that has it's share of issues as well, including being met by anger and frustration when you refuse to add someone you know well in real life as a contact on the "wrong" site.

SGU is awesome

2010-05-08T04:40:00.000-07:00

This post is dedicated to the television show "Stargate Universe". If you have ever seen the show, you're probably wondering if I'm drunk or stoned after having seen the title of this post. I am neither. But don't get me wrong, taken at face value, the show is mind-bogglingly, appallingly bad. A poorly executed clone of "Battlestar Galactica" and "Lost" made worse still by gratuitous overuse of shakycam, and characters devoting every waking moment to plotting and scheming like high-school kids with a heightened sense of self-importance.

This is what google has to say:

The search results yield loving comments like

[I] hope [the monster] eats half of the crew and the rest die in a fire.

... which really speaks for how utterly SGU fails to evoke even basic sympathy for the characters, evoking less emotion than the struggles of 20x20 pixel sprites.

So why do I claim that this universally jeered at TV-show is awesome? At first, I watched it, and during each episode I thought "why am I watching this crap?". When the episode was over, I thought "why did I sit through that crap?". Then the answer struck me: So I could discuss with others how bad it is. For once, everyone agree on something. Nobody likes SGU.

This show is so blatantly bad that everyone can be a snide critic without spending hours on TVtropes learning the cliches. And being snarky is fun, especially with friends, heckling together against a common enemy. SGU brings people together. People meet to discuss how bad it is, offline and online. Whether or not you like sci-fi or the stargate franchise in general; you'll definitely be able to join in hating SGU.

A SGU shot game doesn't need rules. The show makes you want to kill your brains on a regular enough basis as it stands. And that is why I love it.

A horrible exercise in implementation hiding

2010-04-10T10:44:00.000-07:00

The following is pretty straightforward C99 code. Try to guess what it does.


#include "list.h"
#include <stdio.h>

int main(int argc, char* argv[]) {
 struct list *l = list_new(); 
 *(void**) list_append(l)= (void*)  0x00;
 *(void**) list_append(l)= (void*) 0x01;
 *(void**) list_append(l)= (void*) 0x02;
 *(void**) list_append(l)= (void*) 0x03;
 *(void**) list_append(l)= (void*) 0x04;

 for(struct list_iterator* it = l->first;
  it != l->last; it = (struct list_iterator *) it->next) {
  printf("%p\n", *(void**) it);
 }

 return 0;
}

Looks and feels like a linked list being created and then iterated, right? Wrong. It is so much worse than that. As a horrible exercise in implementation hiding^†, this is an array list, and the iteration is done in a very devious way.

The list header looks like the following:


#ifndef LIST_H
#define LIST_H

struct list_iterator {
 void *data;
 void *next[];
};

struct list {
 struct list_iterator *first;
 struct list_iterator *last;
 int allocated;
};

struct list *list_new();
struct list_iterator *list_append(struct list* list);

#endif

It still kinda looks linked-list-ish at a glance, but something is off about it.

A rough sketch of the implementation would look like this:


#include "list.h"
#include <stdlib.h>

struct list *list_new() {
 struct list *l = malloc(sizeof(*l));
 l->allocated = 2;
 l->first = malloc(l->allocated * sizeof(struct list_iterator));
 l->last = l->first;

 return l;
}

struct list_iterator *list_append(struct list* list) {
 if(list->last == list->first + list->allocated) {
  list->allocated *= 2;
  list->first = realloc(list->first, list->allocated * sizeof(void *));
  list->last = list->first + list->allocated / 2;
 }
 return list->last++;
}

That was no linked list.

It's decidedly sneaky: struct list_iterator.next overlaps with the next element in the array through use of C99's flexible array members, giving the list a free next pointer without any extra memory usage at all.

This is proof of concept, and I don't suggest this should ever be used for anything other than scaring the elderly and small children.

^† Well, it isn't strictly speaking true implementation hiding, as you can see what's going on from the public interface in the header. But in lack of a better term...

Vertical and diagonal words

2010-03-14T14:43:00.000-07:00

Unix systems often have a quite handy file called /usr/share/dict/words that contains almost 40,000 or so words for use by spell checking tools. It's sorted, and each word is separated by a newline. So it looks something like

aback abaft abandon abandoned
etc.

On a random whim I set out to examine to what extent words existed vertically in this dictionary, using a quite ugly brute-force approach that tested a 1,081,332 character long string that was basically a concatenation of every single word in the dictionary for the 40,000 sub-strings that made up the dictionary, running for a minute or so.

Perhaps not surprisingly, there weren't a lot of these words. And in fact, the longest words were only five letters long; but in case someone wants to build a crossword puzzle or something, here is a list of those words:

adder multistage multitude multitudes multiuser multivariate doors surged surgeon surgeons surgery surges fills mindfulness minding mindless mindlessly minds fills doubtfully doubting doubtless doubtlessly doubts fills fruitfulness fruition fruitless fruitlessly fruits guess amalgams amanuensis amaretto amass amassed guess resting restitution restive restless restlessly hills motherhood mothering motherland motherly mothers noose compactness compactor compactors compacts companies sauce samplings sanatoria sanatorium sanctification sanctified sneer assesses assessing assessment assessments assessor steep horseshoer horticulture hose hoses hospitable stint despising despite despoil despondent despot

Diagonally, though, is quite a lot more interesting. Not only are the words quite a lot longer, the diagonal word is almost always the same as—or very similar to—the last word, which is a semi-obvious consequence of sorting when you think about it.

The longest few I found were

differentiation diets differ differed difference differences different differentiable differential differentials differentiate differentiated differentiates differentiating differentiation differentiations representatives repositions repositories repository reprehensible represent representable representably representation representational representationally representations representative representatively representativeness representatives

The supposedly herculean feats of ants

2010-03-02T14:45:00.000-08:00

Most of us have heard that ants can carry weights hundred times of their own. Just recently, BBC News ran a story related to this ability.

Image Source: Wikimedia Commons.

In most people, this conjures up images of SUV-sized ants effortlessly lugging around buildings, reminiscent those in classic Sci-Fi film THEM!; more still, of mimicking the ants and creating super-strong materials and actuators that are vastly stronger than anything we have access to today.

This is however a pipe dream. This apparent strength is a consequence of being small, and not of some specific capability of ants. The villain is scaling laws -- the rules that describe how physical properties change with size.

Here is how it works:

The mass of an object that has characteristic length L (that is, is roughly of size L in height, width and depth) is described by m = ρL³, where ρ is the density of the object.

The weight a muscle can lift is given by M_max = cL², where c is some material constant that is independent of size. You can see why this is by realizing that this is very much like the strength of a string -- and making a string longer does not make it stronger, but making it thicker does.

What we are interested in is the ratio of these quantities (i.e. maximum carry weight over mass):
M_max / m = c/(ρL)

Ignoring c and ρ as they are independent of size, a pattern emerges. If we put in a very small value of L--a very small characteristic length--this ratio becomes very large. If we put in a large L, it becomes small.

So, what does this mean? Well, the smaller the muscle, the more it can carry relative to it's own weight.

In conclusion:

An ant that is 1,000 times larger^† than it is weighs a billion times more, but is only a million times stronger, so it's strength to mass ratio decreases by a factor 1000.

A human that is 1,000 times smaller than it is weighs a billion times less, but is only a million times weaker, so her strength to mass ratio increases by a factor 1000.

Returning to the SUV-sized ants, such ants would not be able to support their own weight, let alone carry buildings around, and an ant-sized human would be stronger than anything it's own size.

^† this value is a bit larger than SUV-size, but correct in an order of magnitude ballpark sort of way.

Integration by weight

2010-02-27T05:37:00.001-08:00

Some randomly firing neurons just gave me a flashback to a very unorthodox means of doing calculus: Integration by weight.

Here is what happened: Some years ago I was taking a class in thermodynamics. As part of this class, there was a lab (I don't specifically remember what it was about, but there may have been a Stirling engine involved); and in the course of this lab, a contraption produced a two plots of some quantities relevant to the physics involved on a large sheet of paper.

For whatever reason, it was necessary of us students to integrate this printed plot (effectively to find it's area). So, we spent some time rubbing our heads as to how to do this. We discussed several options, like dividing it into triangles and doing some sort of approximate estimate that way. But all of these methods seemed very time-consuming and tedious. So it dawned upon us: We could weigh it. Said and done, we cut the blob outlined by the plot out of the paper, as well as some reference samples to get an average weight of the paper.

Worked like a charm. Granted, we had access to an analytical balance with pretty high-precision, but still, there is something very appealing about the fact that this works.

Useful URL tips for google and youtube

2010-02-05T10:32:00.000-08:00

A short list of simple but useful tips for youtube and google URLs.

Link to a specific time in a youtube video

Attach #t=AmB where A is minutes and B is seconds to a youtube URL, to link to that specific time in the video.

Example: http://www.youtube.com/watch?v=wRnSnfiUI54#t=0m16
links to the specific moment where Kirk shouts KHAAAAAANNN!

Google in English

Occasionally, google gets it in it's mind that you want the interface translated to some language other than English, because you are in a country that speaks that language, or because of (broken?) geo-profiling. To clear this, visit

http://www.google.com/ncr

Google query on the fly

If you need to do a quick google query, and want to limit the bandwidth used by only loading the results, or the pages loaded because you're in an awkward text-based browser, learn this URL scheme:

http://www.google.com/search?q=a+google+query, where a+google+query can be replaced with whatever you're searching for.

That is all.

I digress: The elusive experience of being lost in a familiar place

2010-02-04T08:32:00.000-08:00

Deviating a bit from the set topic of this blog, I thought I'd share a quest of mine in life: Loosing myself in familiar places.

When I was very young, probably around 8-10 years of age, I had a most peculiar experience as I woke up one morning. I was convinced I was lying in one direction in bed (not that I remember specifically which orientation, but for the sake of the story, let's say I imagined myself facing the wall next to my bed), only to open my eyes and find out I was facing away from the wall. For the briefest of moments, I experienced a peculiar but pleasant feeling of confusion.

It is hard to put this experience in words, but if you have ever had a false awakening (that is, dreaming you woke up and started doing your morning routine, only to wake up for real moments later and finding you're still in bed), the experience is somewhat similar.

Ever since this morning in my childhood, on some level, I have been chasing this experience. It is quite elusive, as it is very hard to make yourself forget how you got somewhere, since trying typically has you paying more attention to where you are. I have indeed experienced it more times, usually while lost in deep thought about some matter, only to realized I've been wandering around randomly.

These events are rare, probably occurring order of magnitude once a year. But today, was one of those days. While pondering a problem from a textbook on plasma physics I was reading, I went to the lavatory, only to realize I had no idea which floor I was on.

They seem like such tiny and insignificant events, but given their rare and transient nature, I feel it's necessary to cherish and take the opportunity to explore them.

How some CAPTCHAs are being broken (and how to fix it)

2009-12-03T04:42:00.001-08:00

I've noticed that CAPTCHAs are becoming increasingly futile in combating automated sign-ups, as well as becoming increasingly prevalent in places where it doesn't make sense to put them. So a while back, I connected the dots into a theory on how CAPTCHAs are being circumvented in bulk quantities (after some further research, it turns out that this method is actually in use).

It's essentially a form of covert crowdsourcing: If you have a high-traffic site that requires a sign-up, you could in theory simultaneously create an account on some other CAPTCHA-enabled site by forwarding the CAPTCHA to the user signing up on your site, and as your user solves it, forward the result to your own sign-up session on the target site.

There's a lot going on in this, so I'll divide it into two parallel time lines (blue italic is malicious site, red is target site):

User loads registration sign-up page

Sign-up session on target site is started, malicious site downloading CAPTCHA image

Malicious site presents target site's CAPTCHA as it's own

User fills out details and solves CAPTCHA

User's CAPTCHA-result is used to register on target site

Now this is a known method, but there is an obvious way of deterring this sort of thing that for some reason doesn't seem to be widespread: To embed something that indicates the origin of the CAPTCHA onto the image. If the users see an URL and a logo belonging to a different web site than they are signing up on, they would naturally grow suspicious, and as this method mostly lends itself to targeting specific websites (and these would be bigger targets), the target will likely be big enough to be recognizable to the average person, which makes all the more suspicious.

C & Bash frankensources

2009-11-16T15:40:00.000-08:00

Heh, I stumbled upon an amusing overlap in C preprocessor syntax and shellscript comments. You can piggyback a C program onto a shell script, so that it's both possible to compile the file with a C compiler, and let bash evaluate it.

#if 0
echo "Hello from bash!"
exit
#endif
#include <stdlib.h>
#include <stdio.h>
int main(int argc, char* argv[]) {
  puts("Hello from C!");
  return EXIT_SUCCESS;
}

Note that it's not possible to put a shebang in the beginning of the script (or other shell script comments) and compile it, as that upsets the preprocessor.

$ sh frankenscript.sh.c
Hello from bash!
$ gcc frankenscript.sh.c -o test
$ ./test
Hello from C!

You could also have the script, when run as bash code, compile it self as C sources and run the result.

#if 0
file=`mktemp`
gcc -o $file $0
$file
rm $file
exit
#endif
#include <stdlib.h>
#include <stdio.h>

int main(int argc, char *argv[]) {
  puts("Hello from C!");
  return EXIT_SUCCESS;
}

...

$ sh frankenscript2.sh.c
Hello from C!
$

Don't get me wrong, it's a perverse crime against nature and should never be used, but still, an amusing diversion.

Small ternary (base 3) computer on a binary microcontroller

2009-10-27T06:54:00.000-07:00

This isn't my work, but I've done some degree of work in the field of ternary computing through the ternary computer emulator Tunguska I whipped up a few years ago (I'm slowly working on a major re-write, but other things keep stealing my time). Which is kinda cool. I do believe I'm the only person in existence who has written something even remotely close to a C compiler for a base 3 computer.

Anyway, enough of my esoteric feats, this is pretty neat: "Ternary Computer is now emulated in binary microcontroller"

There's more information on the 3niti project here: http://www.3niti.org/

HAPPY CAPS LOCK DAY EVERYONE

2009-10-22T10:22:00.000-07:00

HAPPY CAPS LOCK DAY EVERYONE!

OCTOBER 22 IS INTERNATIONAL CAPS LOCK DAY, AND THIS BLOG FOR ONE EMBRACES THIS IMPORTANT INTERNATIONAL HOLIDAY.

BECAUSE, WHEN WAS THE LAST TIME YOU TYPED IN ALL UPPER CASE LETTERS? AREN'T YOU FEELING A LITTLE BIT GUILTY ABOUT NOT USING THE CAPS LOCK KEY AS MUCH AS YOU COULD? JOIN THE FESTIVITIES! JUST HIT CAPS AND TYPE AWAY.

MIDI programming in Linux

2009-10-06T08:46:00.000-07:00

For no particular reason other than curiosity, I decided to venture into MIDI programming. In Linux. There are two problems with this idea:

MIDI programming...: While actual MIDI programming isn't that difficult, you are definitely not in Kansas any more. These music guys are a separate subspecies to the garden variety geek.
... In Linux: Doing this is painful. It's sort of like going to the dentist, finding out that nobody is there, and that you have to fix your teeth on your own, and while there are plenty of instructions on how to operate the equipment, they all say different things, and most of them were written on USENET or some obscure mailing list well over a decade ago, discussing deprecated versions of the dentistry instruments you have in front of you.

Anyway, after 3 or 4 kernel recompiles; installation of a virtual synthesizer (fluidsynth) that didn't compile properly out of the box, so I had make countless small alterations to it^[1]; and a ton of sheer luck, I managed to get my program to send MIDI instructions to fluidsynth, that actually reacted to them and made noise.

I wrote a small program that uses my low-end Wacom tablet to create a theremin-like instrument by mapping pitch bend to one axis and volume to the other, but it really didn't turn out too impressive. The tablet doesn't have enough resolution to allow playing more than just a few octaves with any sort of precision.

It's technically doable, but the end result is somewhat of an anticlimax. It was a fun afternoon's work, but when push comes to shove, a pretty fruitless venture.

^[1] I think my GCC version or libc version is buggy or something. It's ridiculously pedantic.

It isn't easy to spam

2009-08-30T05:55:00.001-07:00

I got the following broken piece of spam mail on gmail today. It's obviously from some broken spam script. But I found it pretty amusing. It's certainly the most abstract unsolicited email I've gotten, which deserves some kudos I guess.

More details about my functional language

2009-08-01T07:02:00.001-07:00

I figured I'd elaborate on the as of yet nameless functional language I posted about earlier today.

It's defining feature is that it really ships as a blank slate. Virtually everything you find in a functional language like Lisp or Haskell is so trivial to implement, it doesn't make any sense to hardwire it into the language specifications.

This is because it isn't so much as a language as it is a programmable language parser combined with some very crude elements, lists and atoms, that combined allows you to formulate a functional language.

The latest addition to the language specifications (it's still being evaluated to see just how well it works out) is pattern meta-matching. That is, a pattern that compares stack nodes with other patterns (or even itself). This turned out to make the language even more versatile. It's trivially easy to implement a type system with this latest feature.

It works like this: First you define a tautological pattern that consists of a tag, and the the internals of your type.

define ( =car-tag seats color ) Car ( car-tag seats color );

That's it. You have now defined a type called Car, that has two fields: seats and color. You can now create functions that take a car as an argument.

define ( c:Car ) car-get-seats ( c.seats );
define ( c:Car ) car-get-color ( c.color );

You can of course also modify objects in this fashion:

define ( c:Car new-color ) car-repaint ( car-tag c.seats new-color );

It's important to repeat, that this language does NOT have a type system. It has a variety of pattern matching that you can use to implement types. Or to translate infix mathematics to polish notation. Or countless other applications.

A small project I'm working on

2009-07-31T13:56:00.000-07:00

I'm currently working on a small project that's turned out pretty well. A functional language: It's basically lisp with pattern-matching grafted onto it. This has turned out to make the language very powerful. Nearly nothing needs to come built-in, except the definition, matching and expansion of patterns.

To explain the code examples in this post, I'll first outline the rough grammar of the definition statement.

The overall grammar is the following:
define ( pattern ) name expansion.

In the pattern, atoms may be prefixed with

~: Not to be evaluated until it is absolutely unavoidable (otherwise, they are evaluated on an as-needed basis)
@: Only allowed in the last atom, meaning that it is to correspond with what is left on the stack
=: Matching against the following token, and only the following token

In the expansion, the only prefix that exists is @, which appends the token onto the stack, instead of adding a list cell pointing to the value on the stack.

Some examples of the language.
Basic lisp-style arithmetics

( + 23 14 ( * 7 2 ) )

Conditional evaluation:

define ( =true @statement ) if   @statement.
define ( other @statement ) if .

Factorial function:

define ( 0 ) fac 1 .
define ( n ) fac ( * n ( fac ( + n -1 ) ) ).

Map function:

define ( ( @op ) ( top @rest ) ) map
      ( @op top ) map op rest.
define ( ( @op ) ( last ) ) map
      ( @op last )

Mapping factorial function to some numbers:

print ( map ( fac ) ( 1 2 3 4 5 6 7 8 9 10 ) ).
( 1 2 6 24 120 720 5040 40320 362880 3628800  )

Mapping a lambda function corresponding to squaring to same numbers:

print ( map ( ,\ ( x ) ( * x x ) )  ( 1 2 3 4 5 6 7 8 9 10 ) ) .
( 1 4 9 16 25 36 49 64 81 100  )

A more complicated example:

define ( ( a @as ) ( b @bs ) ) zip 
        ( a b ) zip as bs .
define ( ( a ) ( b ) ) zip
        ( a b ) .
define ten ( 1 2 3 4 5 6 7 8 9 10 )
print ( zip ( map ( fac ) ten ) ten ) .
 (  ( 1 1  )  ( 2 2  )  ( 6 3  )  ( 24 4  )  ( 120 5  )  ( 720 6  )  ( 5040 7  )
  ( 40320 8  )  ( 362880 9  )  ( 3628800 10  )  )

I'll post more details later. Mostly because the details are in such heavy flux right now.

The Blob

2009-07-26T11:36:00.001-07:00

Yesterday, something most peculiar happened. I was outside of my apartment, when a black object fell from the sky. I'd estimate it's radius to be around 5 cm and it's height to be 2 cm. It was jet black, hard, and I nudged it with my shoe, and found it had the same approximate density as a rock.

Throughout the day I observed this object. As time progressed, it became increasingly reflective, and a pool of viscous black liquid formed around it. Today all that was left was a pool of this viscous goop.

I snapped some pictures of the sludge, and something that first seemed related, but at a closer look at the pictures doesn't appear to have anything to do with it. It looks more blue in the pictures than it is in reality, since it is highly reflective, and the sky was blue at the time I took the pictures. For size comparison, the light gray rock in the pavement to the upper left of the puddle is about the same size as a larger coin.

I took a sample with some Q-tips and put it in an air-tight glass jar to preserve this substance since science demanded it of me. It was very viscous, and appeared semi-transparent gray against the head of the Q-tips.

I have no idea what it is. Did it come off an airplane^[1]? From space? Is it organic? Though I suppose it's not the strangest thing to ever happen.

¹ This is actually pretty unlikely. I live close to an airport, but perpendicular to it's runway, so I literally never get any aircraft flying overhead.

Serendipitous bug

2009-07-04T13:49:00.001-07:00

I was fooling around with a procedurally generated model of a tree, and went on to add some physics so as to made it bend under it's own weight. Somewhere along the line, I used the wrong angle in the simulation of the torsion springs I used to model the branches with, and I ended up with a pretty disturbing, but highly pareidolic result that's slap bang in the middle of nightmarish and amusing to watch.

Double spring pendulum pRNG

2009-07-02T08:06:00.000-07:00

You can make a pretty decent random number generator through physical simulation of a double spring pendulum. Double pendulums are chaotic systems, and as such, express a high variation of state after a given time, based on small variations on the initial dataset (the so called butterfly effect).

The motion used to generate the random numbers looks like this:

What makes this a decent random number generator is the lack of a closed form solution to the motion of the pendulum, combined with five hidden degrees of freedom.

The algorithm loosely looks like this:

Simulate for N timesteps (I the Euler method for integration, but it's probably a lot smarter to use a less sensitive algorithm -- or not, the errors introduced by the algorithm might make the data more random.)

Let θ be the inner pendulum's angle (scaled to the range 0 ... 1)

Let φ be the outer pendulum's angle relative to the inner angle (scaled to the range 0 ... 1)

Let the data be ((θ * 10000₁₆) ∧ ff₁₆) ⊕ ((φ * 10000₁₆) ∧ ff₁₆)

Let N be some constant (the higher the more random the data) + data * (some other constant)

Yield 'data'

Repeat.

Using 'ent' to analyze the data, these are typical values:

Entropy = 7.997207 bits per byte.

Optimum compression would reduce the size
of this 70346 byte file by 0 percent.

Chi square distribution for 70346 samples is 271.07, and randomly
would exceed this value 23.38 percent of the times.

Arithmetic mean value of data bytes is 127.4919 (127.5 = random).
Monte Carlo value for Pi is 3.135107472 (error 0.21 percent).
Serial correlation coefficient is 0.000481 (totally uncorrelated = 0.0).

versus /dev/urandom on Linux:

Entropy = 7.997121 bits per byte.

Optimum compression would reduce the size
of this 70346 byte file by 0 percent.

Chi square distribution for 70346 samples is 281.53, and randomly
would exceed this value 12.19 percent of the times.

Arithmetic mean value of data bytes is 127.3213 (127.5 = random).
Monte Carlo value for Pi is 3.148072330 (error 0.21 percent).
Serial correlation coefficient is -0.001095 (totally uncorrelated = 0.0).

The randomness is on par or slightly better than Linux' (pretty dubious) urandom-pRNG, depending on configuration. :-)

This whole project got started as a means of visually telling large numbers like checksums apart through setting the initial parameters of a spring coupled double pendulum according to the number, and then tracing it's motion for a couple of thousand iterations. That did do the trick satisfactory, but still needs more work before it's useful.

The (not-so) secret of .Xdefaults (or rather, .Xresources)

2009-07-01T08:40:00.000-07:00

Several people commented that .Xdefaults—the original subject of the post—is an obsolete file, and that .Xresources should be used instead. I stand corrected, and so does the blog post.

There's a startling amount of people who have missed out on a pretty integral part of X11, namely the X resources database.

What the xrdb does is allow you to set various settings that you would otherwise have to pass with command line arguments to the programs. Clearly, it's pretty cumbersome to start xterm with the command xterm -fg gray -bg black just to escape the horrors of the black on white default color settings on xterm. Reverse video makes the defaults marginally less painful, but the contrast is still not particularly endearing.

Figure 1: A change of defaults makes a world of difference.

There's a wonderful file named ~/.Xresources that allows you to get around this. It is loaded automatically when the X session starts, and can be forced to reload with xrdb -merge ~/.Xresources

My .Xresources file looks like this:

XTerm*background: black
XTerm*foreground: gray
XTerm*title: terminal
XTerm*saveLines: 1024

If you read the man page for xterm, you'll find a rather intimidating list of settings you can alter with .Xresources.

Further reading:

man xterm
man xrdb
xwinman.org's documentation of the .Xresources file
Using the .Xdefaults file

Re-doon-danciy? What is this strange and alien concept you speak of puny earthling?!

2009-06-21T05:12:00.000-07:00

Would it be so hard to add data redundancy to media files? My computer has just south of 1 terabyte of hard drive space. Most people have at least a couple of hundred gigabytes. Storage is so cheap, and transfer speeds so fast, that making all media files 10% bigger is a pretty painless cost for self-reconstructing media files.

Figure 1: Image corruption may well be the end of us all!

Take an image. Split it up in a bunch of quadratic sub-images. Let each of them store low resolution copies of it's Von Neuman neighborhood's contents. Give the blocks checksums, and compress them individually. If a block fails to pass the checksum, you can now reconstruct it using interpolation from it's neighbor's low-res copies. It wouldn't be picture perfect, but you'd be able to deduce the contents of the image even at pretty bad corruption (information recovery at 75% data loss at a best case scenario).

Do the same with video, while you're at it. Seriously, give me a video codec that does this, and you will make the world a better place.

Better yet, add redundancy to text. Add a plaintext Huffman coded copy of the textual contents of a document to it's metadata.

The virtue of documenting obscure behavior

2009-06-17T14:58:00.000-07:00

In the hope that people in the same situation as me can find this through google: Some shells run signal(SIGINT, SIG_IGN) before they execute your program if you run it in the background. This interferes with sigwait.

I think the reason for this is dubious implementation of background processes. Instead of checking which processes are background process and foreground processes, and only sending SIGINT to the foreground processes, the background processes are told to ignore SIGINT, and the signal is sent to all processes when ^C is received.

You can clear this by putting signal(SIGINT, SIG_DFL) in the beginning of your program, if you want it to behave like a regular foreground process, despite being run in the background.

This is a quite poorly documented fact, that took major hair-pulling to deduce. There are two lessons to be learned:

Don't make assumptions about the standard behavior of anything.
Document obscure behavior.

Thus endeth the frustrated rant.

How to become a programmer

2009-06-15T12:03:00.000-07:00

A lot of people aspire to learn programming, and it's not an easy task (there are countless pitfalls that aspiring programmers typically parade into like lemmings), so I figured it would be useful to outline a path acquire that goal.

1. Learn an imperative scripting language. Become confident in a simple language in which it is easy to write functional stuff fast. Not only does this serve as an introduction to imperative programming, it will also be useful down the line when you want to get stuff done quickly without all the red carpet other languages typically come with. Python is probably the best language to start off with, but there are other options as well (ruby, perl, lua, etc.), and they're all good choices for a first language. My motivation for suggesting python is the great community surrounding it, and the libraries it ships with that makes rewarding projects such as simple game programming relatively easy and quick.

(The order in which you take the following two doesn't really matter, do both simultaneously if you want.)

2a. Learn a functional language. Once you've gotten imperative programming down, it's time to learn something that will blow your mind, and fundamentally change the way you think about programming. Lisp or Haskell are good choices. Pick your poison.

2b. Learn a low level language. Low level programming will teach you what actually goes on under the hood. C is probably a good place to start. You may want to try assembly as well: It's a pretty easy language, but only really worth pursuing if you enjoy it.

3. Learn an object-oriented language. Now that you know a fair deal about programming, it's time how to write a lot of code while still keeping it manageable. That's where OOP comes into the picture. You'll probably want to learn some of the following: C++, C# or Java (the two are more or less identical).

Now that we've dealt with what to learn, it's time to discuss how to learn it. It is my opinion that tutorials are dangerous as hell to new programmers. There is no way to verify who wrote the tutorial (it may be some confused 14 year old, no offense to the 14 year old programmers out here), they come in no particular order and are generally inconsistent. The proper way to learn any language is to:

Buy a book. Check the reviews as well. You can also ask around the programming community as to what book is best on the subject. You may get away with official online documentation in some languages (e.g. python), but as a general rule, you want a book.

Practice. Write programs. Make them small, make them large, make them silly, make them serious.

Taking classes in programming may or may not be useful to you. It can be helpful, but what really makes a difference is how much you practice.

Something is also to be said about the company you keep. You can soak up a lot of programming skills by hanging out at places like the coding forum at www.forums.xkcd.com, and that goes for people at any skill level.

Finally, there are some horrible traps you can walk into.

Don't start in web design. First you need to learn HTML (which has nothing to do with programming at all), and then some abomination like PHP (which teaches terrible coding practices.) A background in web design is salvageable, but it is a damn tar pit.
Don't start in C++ or Visual Basic. Starting in C++ is like putting a 5 year old in the pilot's seat of an airliner: It isn't going to understand 1% of the features, and will probably crash and burn (badum-ching); and Visual Basic is a crime against the mind.

This of course represents my opinion. There's as many answers as to how to become a programmer as there are programmers.

TL;DR: Learn python first.

"Fast" division

2009-06-15T04:15:00.001-07:00

This is mostly a note-to-self on how to divide a number in base b with some integer n using nothing but "fast" operations like addition, subtraction and shifting (occasionally multiplication) -- if you bake them together, you typically end up with something of linear complexity or slightly better:

To divide a number in base b with some integer n, find the recursive relationship

1/n = 1/b + (b-n)(1/b)(1/n)

Where 1/b of course can be expressed as a digit shift. So, to express division by 3 in a way that is convenient to a binary computer, you get the relationship

1/3 = 1/2 - 1/2 * (1/3) => 1/3 = 1/2 - 1/4 + 1/8 - 1/16 + 1/32 - 1/64 ...

Conversely, to express division by 2 that is convenient to a trinary computer, you get

1/2 = 1/3 + 1/3 * (1/2) => 1/2 = 1/3 + 1/9 + 1/27 + 1/81 + 1/243 + 1/729 + ...

So now you know... It's pretty easy to vectorize the algorithm you get out of this, but you need to tip-toe around the minefield that is the decimal parts (well, actually, calculate their carry and add that to the integer part) to avoid rounding errors.

A slightly better operating system philosophy than UNIX

2009-05-22T11:12:00.000-07:00

Please note that this is a conceptual joke.

In the spirit of ideas like this, I'd like to outline an entirely new operating system philosophy.

It's based on the following concepts:

Everything is an email. All user data, and peripherals are accessible only through POP3 and SMTP daemons built into the operating system, sorted in different accounts depending on their tasks.

No program has any particular task it does very well, but all of them can send or receive emails. The latter is in fact a prerequisite to be called a 'program'.

When you start a program, it gets an account in the mail system. This is the only means of IPC.

The GUI is also managed with emails. It is server based like X11, except it's wrapped in email protocols. A program wanting to change it's title would for example send an email to the GUI server asking for it to do so.

The default command line shell is a mail client of user choice. The default is crude, reminiscent of a raw telnet session to an SMTP server, but other options such as mutt, pine or emacs (reduced to it's mail-manipulation capabilities only) are also available.

Example: How to write a Hello World program in C, compile it, and run it.


MAIL: Compose
TO: code@filesystem
TITLE: hello-world.c

#include <mailos.h>

int main(int argc, char* argv[]) {
/* To be a program, it must by definition be able to deal with emails */
  mail_client_initialize(argv[0]);  
  mail* mail_create("output");
  mprintf(mail, "Hello World!\n");
  mail_inbox_add(mail);
  mail_destroy(mail);

  return EXIT_SUCCESS;
}
-- END

MAIL: Compose
TO: process-starter@system
TITLE: compiler
--END

MAIL: LOGIN
SERVER: filesystem
USER: code
LOGGED IN

CODE: FORWARD
WHAT: hello-world.c
WHERE: compiler@processes
CODE: LOGOUT

MAIL: Compose
TO: process-starter@system
TITLE: a.out
--END
Hello World!

MAIL:

The possibilities are endless: Spam mail can be used to generate entropy for the random number generator, and system backup could rely on gmail. Clusters could be managed with mailing lists.

Follow-up: Webcam touch screen

2009-05-19T11:39:00.000-07:00

As a follow-up on the Making A Touch Sensitive Sidepanel post from a while back, I can gladly report that it is actually feasible to make the entire screen touch sensitive. In a feat of hobo engineering¹, I've crafted flaps out of cardboard to mount the webcams 20 centimeters (8-ish inches) away from the screen, thereby making it possible to cover the entire surface of the screen within the field of view. When I have the time, I'll make a proper mount for the webcams out of something sturdier than cardboard.

I actually have come up with the designs for a more elaborate version, but an actual assembly will have to wait until I have more time and resources (hopefully in a month or so). It requires a webcam, a light source (LED:s? perhaps infrared if your webcam can see those), a two panes of glass (without scratches), and a box. The idea is to mount the glass at a 45 degree angle inside the box, and then the screen, upside down, at the top of the box. The box is painted black on the inside, and a row of LED:s are mounted on the top of the viewing side. When you look into the box, the glass will reflect the screen (which neatly enough will appear to hover in the air inside) so that it's viewable from the viewing hole. The LED:s on top of the hole will illuminate anything close to the surface (e.g. your finger touching the surface), making it possible to track such objects with a webcam on the far end of it. It's also probably a good idea to add a fan somewhere. Here's a diagram:

Note that this design means that the aspect ration of the viewing area will change by a factor 1/sin(45^o) = √2, so what was a 4:3 screen will be a 36:19 screen. ... yeah.

^[1] It's even beyond redneck engineering. Even their mechanical shenanigans don't reach this level. Everything is made out of expectations, cardboard, surgical tape. Nothing stays where it should for more than a few minutes. All that's missing is a burning barrel, a shopping cart, and some gloves with no fingertips, and the experience would be complete.

Browser javascript performance vs. Adoption

2009-05-15T09:13:00.000-07:00

There was an article on Slashdot today about how browser javascript speed seemed to be inversely correlated to the adoption of the browser. The core of the article was this press release from Futuremark.

Sadly lacking was a hands-on analysis of the numbers. The sample size is pretty small (5 browsers), but still, some analysis would still be called for, so here goes:

First a plot of the data set^[1].

At a glance, it doesn't look terribly correlated, but, there is a hidden outlier here. If you remove the third sample, Opera, you get a plot that looks more like a smooth function.

Indeed, if you take the logarithm of this dataset, you find an almost straight line (!)

If you look at the logarithm of the full dataset, it's pretty evident that something is wonky about the Opera point.

For the reduced data set, a linear regression of Performance vs. log(Adoption) as a+b*x yields

a = 0.619
b = -0.00447

A statistical analysis indicates that the probability for such a strong correlation by random chance is 0.062%. The standard deviation is 0.079, and the coefficient of determination R² is 0.999. For the full data set, R² is 0.89.

So, the adoption as a function of performance in the benchmark would according to this hypothesis be

Adoption(Performance) = e^{0.619 - 0.00447*Performance}

Comparing this with the data sets, it appears very likely that the hypothesis is true.

Of course, the data set is very small, so it's plausible that this is just a random coincidence, the same way one may get a descending sequence of numbers when throwing a die 4 times without some physical rule dictating that dice only generate descending sequences of numbers.

Some final thoughts: Even though correlation is not causation, my guess is that more popular browsers, being older, need more maintenance. Their large user base will also lead to more time being spent patching security flaws. On the other hand, the smaller upstarts need a competitive edge to stand a chance against the bigwigs, motivating the developers to create faster code.

As for Opera, you can either interpret them as having unusually small adoption for it's speed, or being unusually slow for it's tiny adoption. The former makes more sense than the latter. A factor that should be taken into consideration is that almost all the other browsers either have massive campaigns surrounding them, or ship as default with some operating system. So maybe Opera is simply under-advertised?

The analysis was performed with the statistical functions of a TI-84+, and the plots were generated with gnuplot.

^[1] You can find the actual numbers in the press release, I don't want to steal their thunder.

Making a touch sensitive sidepanel

2009-05-02T10:47:00.000-07:00

I love coming up with new ways of controlling my computer. But I'm also a cheap bastard. So, in joining my two aforementioned characteristics, I bring to you probably one of the cheapest ways of capturing finger presses on a non-touch display. It won't allow you to track touching on all of the display or tracking multiple fingers, but it will allow you to create a touch sensitive sidepanel. What's keeping you from doing the entire screen is the narrow field of view in most webcameras, so you could hypothetically get around this problem with some form of lensing.

It's also worth noting that it's a better idea to experiment with this on CRT displays instead of flat displays, since CRTs are easier to clean and harder to damage with your fingers.

All you require is 2 webcams with a decent frame rate (mostly anything in the 10-20 buck range will do the trick, so long as they can do 30 fps or so), some black cardboard and some adhesive tape.

Figure 1: The set-up. A. Vertical camera, B. Horizontal camera, C. Black screen. D. Section of screen where fingers can be tracked.

The black cardboard in opposite of the cameras is to make finger identification much simpler. Instead of comparing with some complicated idle state, you'll just have to check what portions of the view isn't black.

Figure 2: What the cameras see. A. The area to be ignored. B. The area to be scanned for fingers (with black cardboard in the background). C. A finger. D. Portion of the screen at a steep angle (to be ignored as well)

Once you've got your hardware set up, the actual interaction with the hardware can be a bit of an headache, but I got it working by reading the Video4Linux documentation. You can probably settle for a cargo cult implementation of the actual driver interaction. There's also some limitations in your computer that you may run into. The USB bus only has so much bandwidth, and if you're unlucky, that might not be enough for two video feeds. I had to hack the kernel module to get around that problem with my drivers.

The basic finger identification algorithm is pretty simple. You take an average of the positions of all the pixels which are bright. Simply scan region B in Figure 2 for pixels with a color intensity stronger than some threshold value, and for such regions, increment one counter by the brightness, and one counter by the vertical position of the pixel multiplied with it's brightness. When you've iterated over all points, divide by the first counter.


float sum = 0, pos = 0;
for(x = 0; x < x_max; x++) {
for(y = y_min; y < y_max; y++)
  if(ispixel(x,y)) {
    sum+=intensity(x,y);
    pos+=x*intensity(x,y);
  }
}
pos/=sum;

Besides the actual implementation, you'll need to do some form of calibration. It's mostly trial and error. First, figure out how much off the zero position is, then estimate how much off the scale is, and compensate for that.

You can cut down on some of the noise by giving the values some "inertia", which essentially the same as applying a low-pass filter to your data. Use the following algorithm:


X = X*(1-alpha) + X_new*alpha;
Y = Y*(1-alpha) + Y_new*alpha;

where alpha is a number in the 0 ... 1 range (I chose 0.25), and the position will stabilize a lot.

We can also use the fact that the position is relatively stable to identify a "press", i.e. when the difference in position between iterations is lower than some value, we decide that the user has pressed his/her finger. We may also want to wait a couple of frames before triggering a new press, since obviously it's not desirable to have the same action performed 30 times because you didn't have the reflexes of a ninja and accidentally pressing down for longer than 0.33 ms.

Putting it all together, I made a side-bar for my secondary screen that is touch sensitive, borrowing some icons from the crystal project.

The code is a working prototype, and a lot of stuff is hard coded, but it should be possible to salvage a lot of the tricky parts for use in whatever project you're working on.

touchcam.c
Makefile

It should on most x86 linux systems with SDL present, but requires a bunch of icons to be put in a subdirectory resources/ to actually run. I got mine from 64x64/apps and 32x32/actions in the crystal project icon tarball.

I'm actually surprised at how useful it is. It may not be 100% accurate, but it's still a really nice way of controlling your mp3 player or starting new programs.

Elbow power: Things going bump in the night

2009-04-26T13:06:00.000-07:00

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

2009-04-26T10:59:00.001-07:00

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.

File transfer over sound card II: Phase Shift Keying

2009-04-22T11:24:00.001-07:00

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) = A₀ sin(ωt + φ)

Then the Fourier transform of S would give you

F_ω(S) = A₀ e^iφ

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.

e^iφe^-iψ = e^{i(φ - ψ)} = 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.

File transfer over sound card

2009-04-18T11:42:00.001-07:00

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.

Kernel hacking: ov51x-jpeg module with 2 webcams

2009-04-17T08:19:00.001-07:00

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.

Awesome Geek Blog

2009-04-08T17:15:00.001-07:00

Okay, so I suck at maintaining a blog. This is the ... 15:th? Blog I've started.

So, what am I?

Physics Student. Quantum Mechanics is my passion, and I do it because it's difficult. The high from solving a problem you've spent a week trying to figure out is impossible to describe. It's like having sex in a sea of drugs when you just won the lottery.
Shameless Cowboy Coder, mostly writing esoteric programs, like this one.

My favorite language is C 99, though I have experience in C++, assembler (6502 and some x86), Java, python, MATLAB/Octave, DOM programming in Javascript, lua, BASIC, and limited FORTRAN.
My favorite editor is vim.

All-around geek. There are very few intellectual pursuits I don't find interesting and don't know the lay of the lands of the basic concepts. In fact, they are two: Medicine and chemistry. But then, the medicine geeks are hoarding their knowledge, and chemistry is evil.
Nerdcore aficionado.
Wikipedia addict.
A card carrying member of The Church of the SubGenius. But I'm only in it for the slack. The beheadings and orgies are a bit meh.

Awesome Geek Blog

Built myself a new computer

The oddy-C

Dennis Ritchie is dead

A brief review of my remote development woes

Preprocesing C with python

Dragonslaying in the bowels of Tunguska

Large buddhabrot fractal

The "C/C++" myth

Static webpages

The square root of 2, and multiples of 7

Neat function

Imaginary numbers are silly

Superfluous computer ventilation

Cute demonstration of how random phase shifts lead to decoherence

Remote control over RSS

Impressive Dutch coin, courtesy of Free Software

"Security"-pestering, follow up

"Security"-pestering

Grand rant about non-physicists and their misconceptions and attitudes

Energy

The amazing pi!

Einstein

Schrödinger's cat

System instability, revisited

Very peculiar system instability event

Edit: Additional tests

Base inversion and digit ordering

Installing Slackware on a semi-isolated system

Argh! Blogger needs a better comment management system!

HTML5 video and canvas hacks

Command Line Google

Compartmentalizing your online identity

SGU is awesome

A horrible exercise in implementation hiding

Vertical and diagonal words

The supposedly herculean feats of ants

Integration by weight

Useful URL tips for google and youtube

I digress: The elusive experience of being lost in a familiar place

How some CAPTCHAs are being broken (and how to fix it)

C & Bash frankensources

Small ternary (base 3) computer on a binary microcontroller

HAPPY CAPS LOCK DAY EVERYONE

MIDI programming in Linux

It isn't easy to spam

More details about my functional language

A small project I'm working on

The Blob

Serendipitous bug

Double spring pendulum pRNG

The (not-so) secret of .Xdefaults (or rather, .Xresources)

Re-doon-danciy? What is this strange and alien concept you speak of puny earthling?!

The virtue of documenting obscure behavior

How to become a programmer

"Fast" division

A slightly better operating system philosophy than UNIX

Follow-up: Webcam touch screen

Browser javascript performance vs. Adoption

Making a touch sensitive sidepanel

Elbow power: Things going *bump* in the night

Was reddited, some replies and comments

File transfer over sound card II: Phase Shift Keying

File transfer over sound card

Kernel hacking: ov51x-jpeg module with 2 webcams

Awesome Geek Blog

Elbow power: Things going bump in the night