Thursday, May 26, 2011

Huffman and the STL

A while back I wrote a Huffman encoder using the C++ STL (Standard Template Library). It worked, but then a co-worker of mine took it upon himself to see how many lines of code he could squeeze out of my implementation. So, in the intervening years I always had this in the back of my head to revisit this and create a compact Huffman encoder with C++ and STL.

So, given a spare moment I wrote carved out a little chunk of code--probably not the absolute smallest in number of lines, but compact none the less. I'm sure a version in Perl would end up being far more compact, but then it would be written in Perl.

The code ends up looking simple and neat, which is one of things I love about using the STL.

See for yourself. The encoding calculation is below, with what is really just a scan for the frequency of occurrence of an ascii character.

vector ct_coll(256);
for (int i = 0; i < input.length(); ++i) {
  ct_coll[input[i]]._c = input[i];
  ++ct_coll[input[i]];
}
//now sort and build tree
multiset freq_coll;
copy(ct_coll.begin(),ct_coll.end(),inserter(freq_coll,freq_coll.begin()));
while (freq_coll.size() > 1) {
  freq_coll.insert(Data(new Data(*freq_coll.begin()),new Data(*++freq_coll.begin())));
  freq_coll.erase(freq_coll.begin());freq_coll.erase(freq_coll.begin());
}
//assign value
Data d = *freq_coll.begin();
assign_code(d);

Thursday, May 19, 2011

How to see sounds with a Ruben's tube (Sound and Fire!)

DISCLAIMER: Nothing in this post is software/code related.

But who cares it's really cool none-the-less.

A bit of background first. I've been working on demonstrating the science of waves at my kids elementary school for the past 3 years now. At about 2 weeks out I start asking myself this question:

What experiment/trick can I perform to help the kids visualize a pressure wave?

We use a slinkys, use a spectrum analyizers, watch a video of the tacoma narrows bridge, etc.But what can I do that really is an attention grabber and helps cement the concept for these grade school kids? And can it rate high on the coolness factor?

So, the idea of building a Ruben's Tube looked light it might fit the bill here. A Ruben's tube basically is an experiement where sound affects fire--how cool is that? Pretty damn cool that's what I say. I asked my cohort (Ross) and wife (who helps to organize the whole affair) if this would fly... And to my complete surprise no one said NO.

So we went off and built us a Ruben's tube...

What exactly is a Ruben's tube? A Ruben's Tube is a length of tube filled with flammable gas (propane) with small regularly spaced holes. The tube is sealed at one end and capped at the other end with a speaker. The gas has nowhere to escape but through these little holes. And the sound (via the speaker) creates a standing wave (at the right frequency that is) that affects the gas pressure along the length of tube. This results is varying flame height based on the location of the hole and the degree of particle motion due to the standing wave. This would be a sine wave of flames along the length of the tube.

When a resonant frequency is pumped into the tube a standing wave will disturb the gas at the points where the motion in the p-wave is the greatest and suppress the gas leaving the tube at holes located at these points. Likewise holes near where the p-wave motion is less will then to escape at a greater velocity.

That mostly makes sense to me (having a bit of a background with acoustics myself).

This required a trip to a local scrapyard (for the tube), the nearby Lowes, and then expropriating a small speaker from Brian's speaker system. And a big ole tank of propane gas. After much drilling, and fitting and drilling we ended up with a 72 hole ruben's tube, about 4 feet in length.

Below we are in the middle of drilling the 72 hole array (that's Ross doing the work with Brian supervising).



The mostly assembled tube is here (sans propane tank connector):


With a closeup of the speaker end of the tube (tube and speaker are 2 inches in diameter):





So, the darn thing worked, but really really wants a sheltered place. Given that no such place exists anywhere in windscape of San Francisco, below video of the contraption working (briefly before the wind gets the better of it). I apologize for the wonky orientation of the video--next time I'll get that straight (the tube really is stationary in a horizontal position). The amplitude modulation of the waves shows up in the last few seconds of the video.



What we discovered what the tube could be shorted (i.e. fewer holes), or we need more pressure and we have to do this in an enclosed space (i.e. NO WIND).

Next up (when I get around to it) will be video of the Ruben's tube playing to "When the levee breaks".

Thursday, May 12, 2011

Implementing a stand-in "loading" image in javascript

First of all Happy Bike to Work day (BTW DAY)!

This is something like my 12th BTW day and I love seeing the masses of bicyclists out on the road especially on this day.

Now on to the subject of this post...

This had me a bit flummoxed, until I nailed down the magic way to set this up. Basically what I wanted to be able to was insert a stock image in place of a slower loading image. This slower loading (well, technically stream) ends up taking seconds to bring up after the page has finished rendering.

What was happening without this was I was staring a big empty rectangle after loading of the page, and thought it would be much much nicer to put in a pretty, albeit temporary, image in place.

The solution involves setting two image tags in the same div section. One visible and one hidden. Something like this:

<div id='stream_temp' style='visibility:visible;'>
  <img height=450 width=600 src='img/camera.jpg' alt='videoFull' border='4' >
  </img>
</div>

<div id='stream' style='visibility:hidden;display:none;'>
  <img onload='displayStream()' height=450 width=600 
    src='my_stream&scrH=450&scrW=600'
    alt='videoFull' border='4' ></img>
</div>

Thursday, May 5, 2011

Generating a random key

I want to keep this little block of code around as it might just come in handy in the future, not that it's terribly complex.

The key generator relies on /dev/urandom to help generate a random key. There's another file on the system call /dev/random. The difference between these two is that the command to open and read from /dev/random will block until enough system entropy has occurred on the system, whereas a call to open /dev/urandom will immediately succeed regardless of the entropy on the system. Meaning your key may not be secure at the point the value is read.

This should only really be of concern if the key is being generated somewhere close in time during the boot process.