source packed in images.

I'm sick of posting source code in the text. I want to be able to upload any file, but all they let you upload is images. I wrote some c++ code to input any file and embed the contents as the pixels of an image (will only work with lossless encoding). The source code for this example is in one of the small images in this blog (the other is the python source of the previous posting). Too bad I couldn't upload a tga,tiff,or pgm, because those files you could just open as text and see the source. I leave it up to you to extract the code from the png.

Hint: convert to pgm (gray-scale) and open with an image editor.

convert image.png p.pgm
cat p.pgm

pyJoy

We just watched Control the other night and both my girlfriend and I liked a poster in the movie. Not knowing that this was an album cover, I immediately thought I should make something like that. So I wrote a script in a couple minutes to generate some images. Source code:

import cairo, sys
import math, random

def gen_row(w, smth=10, shft=0.2, wid=0.5):
    mid = w/2
    shft = mid*shft
    wid = mid*wid

    vals = [0]*w
    for x in xrange(0, w):
        sc = (x-random.uniform(mid-wid, mid+wid))/random.uniform(wid*0.9, wid*1.1)
        sc = math.exp(-sc*sc/2)
        ht = random.uniform(0,sc)
        vals[x] = ht

    for i in xrange(0, smth):
        v = [0]*w
        for x in xrange(1, w-1):
            v[x] = (vals[x] + vals[x-1] + vals[x+1])/3
        vals = v

    return vals

w, h = 256, 512
x0, sc = 4, 20
wid = 0.2

if len(sys.argv)>=3:
    w = int(sys.argv[1])
    h = int(sys.argv[2])

if len(sys.argv)>=4:
    wid = float(sys.argv[3])

surf = cairo.SVGSurface('joy.svg', w, h)
ctx  = cairo.Context(surf)

for y in xrange(10, h, 5):

    ctx.move_to(x0, y)
    row = gen_row(w, wid=wid)
    
    for x in xrange(x0, w-x0):
        ctx.line_to(x, y-row[x]*sc)

    ctx.set_source_rgba(0,0,0,1)
    ctx.stroke_preserve()

    ctx.set_source_rgba(1,1,1,1)
    ctx.line_to(w-x0, y+10)
    ctx.line_to(0, y+10)
    ctx.line_to(0, y)    
    ctx.fill()
    
surf.finish()

how slow is dynamic_cast?

I was wondering how slow dynamic_cast really is the other day when I considering designing something in a way that would require it's use. The other alternatives is to have some a virtual functions that performs a cast (requires the parent class to know about all children) or have a virtual function that exposes the type followed by a cast.

One of the first references I found on the web indicated the virtual-function-then-cast approach being up to 20x faster.
http://www.nerdblog.com/2006/12/how-slow-is-dynamiccast.html

That reference didn't provide code, so I wrote a quick test with the hierarchy of following classes:

ClassA, ClassB: public ClassA, and ClassC: public ClassB.

My tests suggest that this approach is about 5x faster when compiled with g++ -O3 (same speed with no optimization). For my application dynamic_cast should be perfectly fine.

Times for 3*100 million cast and function evaluations (in a smidge more than trivial loop)

Not optimized:

mycast 0m13.879s
dynamic_cast 0m0.060s


Optimized

mycast 0m0.919s
dynamic_cast 0m4.729s


a.h

class AClassA{
 public:
  static const int flag = 0x1;

  AClassA(){}
  virtual ~AClassA(){}

  virtual int name() const ;

  int a(){return 1;}
};

class BClassB: public AClassA {
public:
  static const int flag = 0x2;

  BClassB(){}
  virtual ~BClassB(){}

  int name() const ;

  int b(){return 2;}
};

class CClassC: public BClassB {
public:
  static const int flag = 0x4;
  CClassC(){}
  virtual ~CClassC(){}

  int name() const ;

  int c(){return 3;}
};

a.cc

#include "a.h"

#ifdef use_mycast
#warning "using mycast"
#define caster mycast
#define extras
#else
#define caster dynamic_cast
#define extras *
#endif

int AClassA::name() const {return AClassA::flag;}

int BClassB::name() const {return AClassA::flag | BClassB::flag;}

int CClassC::name() const {return AClassA::flag | BClassB::flag | CClassC::flag;}

template 
T * mycast(AClassA * a){
  if(a->name() & T::flag)return (T*)a;
}

int func_dcast(AClassA * a){
  CClassC * c = caster(a);
  if(c)return c->c();
  else {
    BClassB * b = caster(a);
    if(b)return b->b();
  }
  return a->a();
}

int main(int ac, char * av[]){
  const int ntrials = 100000000;
  int sums[8] = {0,0,0,0};

  AClassA a;
  BClassB b;
  CClassC c;

  for(int i=0; i!=ntrials; i++){
    sums[func_dcast(&a)]++;
    sums[func_dcast(&b)]++;
    sums[func_dcast(&c)]++;
  }
  printf("%d %d %d %d\n", sums[0], sums[1], sums[2], sums[3]);
  return 0;
}

makefile

all:
   g++ a.cc -Duse_mycast -o mycast.opt -O3 -fno-rtti
   g++ a.cc -Duse_mycast -o mycast -fno-rtti
   g++ a.cc -o dcast.opt -O3
   g++ a.cc -o dcast

test.sh

echo "Unoptimized (mycast then dcast)"
time ./mycast | grep real
time ./dcast  | grep real
echo "Optimimzed (mycast then dcast)"
time ./mycast.opt | grep real
time ./dcast.opt | grep real

Bitten again...and again

I think my poor long term memory is causing me to run into the same problems over and over again. One of the dumbest oversights I've made in the past (when I had no experience using a laptop), was forgetting to enable the wireless on the case before trying to connect to a network. Yesterday I was given a laptop to fix and wasn't given any indication of what was wrong. Upon booting, it seemed like someone had attempted a fresh install but had failed to complete installing all the drivers. I figured this was the only problem and set out to install the drivers. Before attempting to get wifi working I checked for the wifi toggle on the case and didn't find one; I then checked in the bios and there was only a disable or use last state option. So I just figured it was on, got driver installed which had option to enable/disable radio. After several driver installs and related utility installs with no luck when scanning for networks I noticed the function key to turn on the wifi. Can't believe I didn't look for it from the start. I knew it wasn't on but continued to repeatedly do something that wasn't working.

Another bite in the ass that I am sure I have received before (although not sure when) is due to gl_ClipVertex not being set in OpenGL shaders. I had a working graphics demo that was using reflections for water and used user-defined clip planes for rendering the reflection. The rendering is based on a scene graph that has shader nodes. Originally the rendering of the reflected image wasn't under a default shader node, meaning it was using the fixed-function pipeline. After improving the scene, everything was changed to use a different default shader, and all of a sudden the reflection wasn't correct. Assuming the change had something to do with the scene-graph, or traversal of it, I spent a bunch of time digging through other code looking for the problem, when it reality it was that I wasn't setting gl_ClipVertex. I have no idea why you would want gl_ClipVertex to be different than gl_Position. But that doesn't matter. All that matters is that I never make this mistake again.

MinGW "ln -s"

I just spent about an hour looking for a problem that didn't exist, and it is all due to the fact that "ln -s" doesn't do what I expected it to in Msys/MinGW. I have an project that uses plugins for most of the UI and assumes that the plugins reside in a specific directory (./plugins in the application directory). Most of the time I use a cross-compiler so I don't have to leave linux land. When developing in windows, with release/debug targets, I link the plugin directory to the release directory that my plugins are compiled in (ln -s plugins/release plugins). The only reason plugins have ever not loaded was due to them missing some flags during link, or when one of my plugins has the same name as a core library that I use (only because the dll's aren't prefixed with "lib" like they are in linux). Anyway, some plugins were not loading, and I couldn't figure out why--trying of course the obvious aforementioned problems. As it turned out, the linked plugin directory was not being updated with the newly compiled plugins, meaning the minor changes that I made, which would have resulted in valid plugins, were not being used. Anyhow, I spent far too long on this until realizing that the sym link was not a sym link at all.

Lighting rod simulation

Have been talking with a friend about simulating and rendering electricity for some other projects recently. I encountered a self-contained paper (http://www.cs.unc.edu/~geom/LIGHTNING/lightning.pdf) on the subject and spent a little time this evening hacking up a quick implementation of the simulating a bolt. It's way simpler than I expected, and gives me one more reason to be glad (yes I'm glad) I'm friends, I'm friends, with the Laplace/Poisson equations.

Anyhow, a crappy rendering using a coarse grid (no tracing lines, or anything fancy), blurred and combined with the gimp. I guess blogger doesn't like the gif I uploaded, so this entire post was a waste.

Voronoi

I can officially almost add 2D delaunay triangulation (or voronoi diagrams) to the list of things I have implemented (if I actually had a list it would be pretty long by now). But why bother, you ask? Well, every time I have needed Delaunay, which is more often than you would think, I seemed to end up using popen with the program qhull and writing my input data to a file and reading from the popen (or by setting up a fifo to do the writing with dup/dup2). Although this works, it is nice to have a lightweight version.

Anyway, this is blog more about debugging than anything. I implemented a version of Fortune's algorithm (from Computational Geometry: Algorithms and Applications) without using an AvlTree (yeah, I know it is not quite n*log(n), but it is fast enough). The implementation is rather straightforward, but I stumbled on a few oversights. First, was determining when the breakpoints on the beach line will converge, and second was the allowance of the sweep line to move in the reverse direction for circle events.

For the first problem, I ended up just computing the circumcenter of the 3 points, hypothetically moving the sweep-line to its y-coordinate and testing whether the breakpoints were close enough to each other. Detecting these events incorrectly will result in the data structure representation of the beach line becoming inconsistent. This for the most part made everything almost work.

Unfortunately, while checking for possible circle events, I was throwing away those events that should have already happened (e.g., y-coordinate greater than current sweep line). This turns out to be a no-no, as when I removed this check (after looking several other places for the source of the problem) everything worked great. Just finished running a script to check the triangulations with those returned from Octave, and the number of triangles seems to check out, so I am assuming that the results are okay--not very thorough, I know, but the ones I inspected visually seemed to be identical.

There are several algorithms that are named after people (e.g., Dijkstra), that seem like they are rather obvious and someone surely others would have come up with if. I'm not so sure Fortune's algorithm fits into this category.

Anyway, it sure looks neat to watch it in action. I almost gave up looking for the problem this evening. I wonder how many problems were really close to being solved and just needed a little more perseverance. I'm glad I wasted about 2 hours looking for these problems, even if I never end up using this code. Still some cleaning up to do.

Back from Japan

Got back from Japan the day before last, and although I thought I was over Jet lag it appears I am not. As my extra early wakefulness is due to Japan, it is appropriate that I write something about Japan, namely some trip details, during it.

I went to Japan on last minute notice, where by last minute I mean I booked my flight a week before it departed. My primary reason for going was to force myself to do things that I felt like saying no to as a friend had just recently asked me if I wanted to join him on his journey. I met up with the so called friend and another friend in the airport at Vancouver before connecting to Tokyo--where we would meet up with a Japanase friend that was hosting us.

The trip was meant to be more of relaxing than tourist, with plenty of skateboarding and casual sightseeing. Tokyo harbours some crazy skate spots, plenty of marble ledges and crazy rails. Everywhere we went we saw flatbars that were potentially skateable. We did end up skating quite a bit, some parks and several street spots, but it turned out that transportation from our resident Tokyo satellite to the scattered Tokyo spots limited the number of spots we could hit. The skateboarders in Japan were super fun to skate with; always good vibes, and they would always be stoked on tricks landed. The skaters all had crazy pop.

Skateboarding aside, much of the trip, at least from my perspective, was lived with a beer in hand: beer while walking, shopping, driving in cars, or riding the trains. Not because I am a heavy drinker, but because it was acceptable (or was it) and available. I arrived in Japan a recent vegetarian, with hopes of sticking to my eating habits. This turned out to be rather difficult, as most dishes had meat in them and a translator was not always on hand during ordering to decode the menus or make special requests. The food, restaurant or convenience store, was pretty much always good. Once I overcame the meat eating aspect, I started to enjoy the seafood as well--something I hadn't been a fan of in the past. Before going, others told me how they missed even the convenience store food; I now understand what they meant.

Of course, many aspects of life appeared to be the same in Tokyo as they are in Canada. Besides the long commute from the Tokyo suberb we stayed at (1 hour by train), the other main things had to be never ending little technological advances such as their toilets, mechanical sushi vendors at restaurants, and coffee vending machines with video display of the coffee being made. Public toilets rarely had soap. Smoking is still acceptable in restaurants, so I smoked. Drink vending machines are everywhere, and they contain cold coffee lattes--I drank several of these daily. Hot brewed coffee is harder to come by than a cold latte (from a vending machine); a grande cup of hot from Starbucks is about 400 yen (roughly $4CAN), where strangely a specialty latte was not too much more. Things like pizza and fries were also fairly expensive. Transit was also fairly expensive, our daily train commute costing upwards of $10 one way (car travel was even worse due to highway tolls). All these little things aside, one of the most notable differences was the overall tolerance of the Japanese people. Even when someone getting cut off by another driver (or bike, or person), they didn't seem to get frustrated or upset like they would have here in North America. Another testament to Japan is how safe you feel there. How could it be any other way, when you can leave your bike without locking it and know it will be there when you return.

Japan was great, the people are nice, the food is good, and there is cold coffee everywhere. I'm happy that we didn't completely do the tourist thing on this trip, as it gives me another good reason to return to Japan. Also, my camera broke in a sake induced drunken bike ride, so I'll have to return just to take the pictures I would have taken.

Jimmy and the coconuts

This blog is about transformations, and random internet walks. Earlier today I was searching for "Jimmy and the coconuts" because I heard Ryan Adams refer to himself and the Cardinals by that moniker at a recent show.

There weren't very many hits for the search, but among the unrelated hits was a site from Waterloo's math pages. http://www.math.uwaterloo.ca/navigation/ideas/Zeno/zenologic.shtml#. The phrase isn't in that page, but some of the puzzles on that page are sort of fun.

There is a puzzle about word transformation, and I thought it related nicely to the irrelevance of following random web links. I was too lazy to think about how to transform the word [snow] into [rain] by one letter word transformations (see the page), with the sequence giving valid words. Instead, I cooked up a quick python script that uses a shell command to test the validness of the words, and does a breadth-first search to find the transformation (sure, a-star would be faster to run, but this only took a couple minutes to write). Anyway, I have no idea who is reading this, or how you got here, maybe it was from searching for Jimmy and the coconuts. Either way, on initial inspection this page is guaranteed to be irrelevant, and because of that it actually is relevant.

The transformation from the listed program gives: ['snow', 'snot', 'soot', 'loot', 'loon', 'loin', 'lain', 'rain']. Based on "spell"'s dictionary.

#!/usr/bin/python
import os, sys, struct, string

# Prune out the words that are not in the dictionary.  Uses spell. replace with your own
# if you want to use.  
def remove_invalid(cands):
    f = file('/tmp/cands.txt', 'w')
    for cand in cands : f.write('%s\n'%cand)
    f.close()
    f = os.popen('spell < /tmp/cands.txt', 'r')
    lines = f.readlines()
    lines = [l.strip() for l in lines]
    for c in lines: cands.remove(c)
    return cands

# Yeah, I was in a hurry, I'm sure there is a better way to get the ascii chars out
# of a string, instead of using the interpreter and the doc strings to find something that worked
def word_neighbors(str):
    cands = [];
    asc = string.ascii_letters
    for i in xrange(0, len(str)):
        for j in xrange(1, 26):
            b = struct.unpack('b', str[i])
            b = (b[0] + j - 97) % 26
            cands = cands + [str[0:i] + asc[b] + str[(i+1):]]
    return cands

if len(sys.argv)<=2:
    print 'Need two strings of the same length'
    sys.exit(1)
if (len(sys.argv[1])!=len(sys.argv[2])):
    print 'Strings arent same length'

w1 = sys.argv[1].lower()
w2 = sys.argv[2].lower()

q = remove_invalid(word_neighbors(w1))

neighs = word_neighbors(w1)
remove_invalid(neighs)

Q = neighs
vis = {}
parent = {}
for n in neighs: parent[n] = w1

while len(Q):
    e = Q.pop()
    if e == w2:
        break
    vis[e] = 1
    neighs = remove_invalid(word_neighbors(e))
    for n in neighs:
        if (n not in vis) & (n not in Q):
            parent[n] = e
            Q = [n] + Q

if e == w2:
    print 'Found transformation:'
    tform = []
    while e != w1:
        tform = [e] + tform
        e = parent[e]
    tform = [w1] + tform
    print tform
    sys.exit(0)
else:
    print 'Did not find a transformation'
    sys.exit(1)

Cross-compiling matlab mex files from linux for windows

With the help of a properly set up cross-compiler (there is a cross-tool setup script on the SDL site, I believe), it is not really a problem to cross-compile windows mex files from linux.

You will need the matlab headers and "*.lib" files from the "extern/win32/lcc" directory. Armed with these, a working version of WINE, the gnumex utility (http://gnumex.sourceforge.net/), as well as some of the MinGW binutils (nm.exe, as.exe), you can generate the def files for the libs. Then it is a matter of setting the compile flags properly. I did this by using the parts of the gnumex source to generate the .def files.

Dlltool info:
http://www.cygwin.com/cygwin-ug-net/dll.html

Time-Dependent

Feeling nervous, anxious, self-conscious. This will all be done in about 75 minutes. Read it then to see if your feelings were justified; probably not. This is life. I wonder if deep down inside I will actually miss feeling this way; probably not. Hopefully no one shows, it will make it easier. Would have been nice to record and share; Look back on it, embarrassed or not. 15 minutes left. The rest of today will be a write-off--guaranteed. Maybe get some new shoes, go skating, drink some coffee. This is all just killing time. Already feeling the heart beat. I wish I could extract this feeling and distribute to all the listeners. Maybe they would understand then. Worst decision ever. Well, at least personally. Wonder where I would be now if I had chosen differently. Whatever, it is just a life.