Blogging from Boston

I'm currently at the National Science Teacher Association (NSTA) national meeting in Boston. I'm just here to help out with the ANDRILL booth and get some much needed face to face time with my co-workers (something we don't often get since I work remotely). The trip has been fun so far, though not as productive as being at home.

I took a few minutes today to fix a bug in the Simile Timeline depth code--when scrolling the timeline, the overview bars would get out of sync. If you're using the depth unit extension, please grab the latest version or check out the diff. I've also updated the Simile Grails plugin, so you may want to update your version from the repository. It fixes the same depth bug and updates the SimileTagLib to work a bit more independently from the domain classes.

A Java on Linux Aside

So I promised a technical post but I ran into a few problems Friday afternoon that ate several hours of my evening. I was trying to deploy a Grails webapp onto a CentOS server of mine. CentOS wasn't by choice, it was dictated to me. I have much more experience with Debian and it's related derivatives like Ubuntu. Anyhow, I was trying to deploy a Grails app but it required Java 1.5/5 and all that was installed was Java 1.4.2. And to make things worse, it was the GCJ version of Java. I understand the philosophical arguments behind what the GCJ folks' reasoning. Sun's Java licensing terms wouldn't allow Linux distros to re-distribute the code. The GCJ have put together a completely free, completely re-distributable version of Java. The problem is, it just doesn't always work as well as Sun's JDK. The blame is as much the application developers as it is GCJ. But to make a long story short, my Grails webapp wouldn't work with "Java" as it is installed on CentOS.


This Java problem is/was (now that new versions of Java are open source) common to all distros. One thing that surprised me about CentOS, was that they didn't have a repository with Java pre-built and packaged. On Ubuntu, all I had to do was add a "non-free" repository and I could install the Sun JDK straightaway. And, once installed, it integrated directly with the system. On CentOS, I had to download the Java binary from Sun. Then I had to download a source RPM from another place. Then I had to manually edit the RPM spec file to match the version of the JDK I got. And then I had to setup an RPM build environment and rebuild the Java RPM with the binary bits from Sun. That ended up taking over an hour to get everything set up properly.

Once I finally got the RPM built, I thought my troubles were over. I manually installed the shiny new RPMs that I built, updated the alternatives, and checked to ensure that 'java -version' was calling the Sun JDK. So done and done I thought, but I was wrong. Imagine my surprise when I started up Tomcat 5 and it was still using the GCJ version of Java. What gives?! I made sure the default Java was the Sun JDK. So then I decided I'd never need the GCJ Java, so I decided to uninstall it completely. Imagine my surprise when Tomcat 5 decided it needed to uninstall itself with the GCJ Java.

I fiddled around with it for another hour trying to get things to work with no luck. So I ended up manually installing both the Sun JDK and Tomcat 5 in /opt and will manage it myself. This finally got things to the point where I could deploy my Grails app however, I lose all of the system integration. A user on the server can no longer just type java and expect it to work. They have to fiddle with their path and their JAVA_HOME variables to make things work. I guess the biggest disappointment to me was that I ended up settling on the solution that I had used several years ago while working on RedHat boxes. After all these years, and the advent of their 'yum' package management system, and even generating packages by hand, you still can't get the Sun JDK package to integrate properly with RedHat/CentOS.

I'm not saying it's RedHat's or CentOS's fault. I guess I've just had better experience with Debian/Ubuntu. I don't know if it's me and my rusty experience with RedHat-based distros, the (lack of) documentation, or the package management system. I'm sure it's a bit of all of them.

All in all, the Java situation is a mess on all of the major platforms. I think Windows got their growing pains out of the way early with the whole Microsoft Java fiasco. On Linux, it's been the inability to re-distribute the Sun JDK because of licensing issues. That should improve now that the newer versions of Sun's JDK are open source. Finally, the Java situation on Macs is wearing my patience pretty thin. It's about time Apple gets a version of Java 6 out that runs on my laptop. I've already shelled out the money to upgrade to Leopard with the expectation that I'd be able to get the next version of Java.

In the next post, I'll be talking about some work I've been doing with Simile Timeline.

rotateLeftAndFlipInSitu

Recently I was working with some large (200MB) vertically-oriented core images in Java. I needed a way to rotate these images CCW so they were horizontally-oriented and flip them vertically for display on an OpenGL canvas. It's a pretty easy task if you're using the Java2D API:

       // get our dimensions
       final int w = image.getWidth();
       final int h = image.getHeight();

       // create our new image and graphics
       final BufferedImage out = new BufferedImage(h, w, image.getType());
       final Graphics2D g2 = out.createGraphics();

       // setup up an affine transformation
       final AffineTransform at = AffineTransform.getRotateInstance(Math
               .toRadians(-90.0), h / 2, w / 2);
       at.translate((h - w) / 2, (w - h) / 2);
       g2.drawRenderedImage(image, at);
       g2.dispose();
       return out;

That snippet will rotate your image to the left. If you twiddle with the affine transform, you can also get it to flip the image for you. The only problem with this approach is that it requires you allocate a second image to hold the results of the transformation. So rotating a 200MB image actually requires 400MB of memory (give or take). This isn't a big deal if I only ever needed to rotate one large image at a time, but in the application, I didn't know how many large images the user was going to be working with at a time. So I decided to see if I could do the rotation in O(1) space complexity.

It turns out that this is actually a pretty difficult problem. It's been studied since the 70s under the guise of "in-situ transposition of a rectangular matrix". Once I found this out, it became a personal quest to come up with a solution. In the end, I was successful:

  // get our sample model and data buffer
  final SampleModel model = image.getSampleModel();
  final DataBuffer db = image.getRaster().getDataBuffer();

  final int w = model.getWidth();
  final int h = model.getHeight();
  final int[] t1 = new int[model.getNumBands()];
  final int[] t2 = new int[model.getNumBands()];

  // transpose
  int i, j, k, movesLeft;
  for (i = 0, movesLeft = w * h; movesLeft > 0; i++) {
   for (j = pred(i, w, h); j > i; j = pred(j, w, h)) {
    // spin
   }

   if (j < i) {
    continue;
   }
   for (k = i, j = pred(i, w, h); j != i; k = j, j = pred(j, w, h)) {
    // get our pixels
    model.getPixel(k % w, k / w, t1, db);
    model.getPixel(j % w, j / w, t2, db);

    // swap them
    model.setPixel(k % w, k / w, t2, db);
    model.setPixel(j % w, j / w, t1, db);
    --movesLeft;
   }
   --movesLeft;
  }

  // now return a new image with an updated sample model
  final WritableRaster raster = Raster.createWritableRaster(model
    .createCompatibleSampleModel(h, w), db, null);
  return new BufferedImage(image.getColorModel(), raster, image
    .isAlphaPremultiplied(), null);

with pred() defined as:

  return (i % h) * w + (i / h);

This algorithm works. It'll rotate the image in place. Thus, if you could load the image in the first place, you shouldn't run out of memory when you rotate it.

With that being said, this approach is pretty naive. There are numerous optimizations that could be implemented, from increasing the amount of temporary storage you use to optimizing the look up so you spend less time spinning.

In the end, I didn't end up using the code in production. It was a fun exercise to work through, though.