A Few Notes On JUnit

JUnit is very cool, if you’re someone who writes code, you should take a look into it.

Here are some things you should know about JUnit:

• JUnit doesn’t let you order your test-cases. This means that if you have “Test B: Only valid if Test A passes”, you’re shit outta luck. The ‘official’ line is that test cases which depend on a custom ordering are ‘wrong’, and you should re-write them. There are two general work-arounds to this problem:
  1. Create generic ‘do things’ methods, and have your test cases call them. That way, you can ‘do thing 1’ in one test, then ‘do thing 1, then thing 2’ in another test, using an ‘assume’ on the output of thing 1 in test 2.
  2. Call your dependent test cases from other test cases, wrapping them in try-catch on AssertionError. This ensures that failing pre-conditions don’t cause your tests to fail.
• You can use asserts in @Before and @After methods. These will fail test cases just like asserts inside the test cases themselves.

Here is an example of using ‘assumes’ to create order in your test cases:


package com.example.test;

import static org.junit.Assert.fail;
import static org.junit.Assume.assumeNoException;

import org.junit.Test;

public class OrderTest {

@Test
public void test1() {
fail("test1 failed");
}

// This test depends on test1
@Test
public void test2() {
try {
test1();
} catch (AssertionError ex) {
assumeNoException(ex);
}

fail("test2 failed.");
}

}


In this example, test1 is run every time test2 is run, and if test1 fails due to an AssertionError (the error thrown by JUnit ‘fails’), test2 will not fail; the assumeNoException call will cause junit to (correctly) treat test2 as being ignored.

It should be noted that this technique means test1 will be run multiple times. For some people, this is trading one problem for another – “I want my tests to run in a known order” for “I want my tests to be run exactly once each”. If you need both of these requirements, then I’m afraid to say that JUnit just isn’t right for you.

Another example:


package com.example.test;

import static org.junit.Assert.assertTrue;
import static org.junit.Assume.assumeTrue;

import org.junit.Test;

public class OrderTest {

public boolean doThing1() {
return false;
}

public boolean doThing2() {
return true;
}

@Test
public void test1() {
assertTrue(doThing1());
}

// This test depends on test1
@Test
public void test2() {
assumeTrue(doThing1());
assertTrue(doThing2());
}

}


How To Write a JPEG Encoder In C and Python – Part 1

Over the course of a few posts, I’m going to show you how to write a JPEG encoder in C. And Python, because I want to see how it does in PyPy.

This post is the first part of this series, and intends to provide a High-Level overview of the JPEG standard; what a JPEG is, how it works, and an overview of the various parts of a JPEG encoding algorithm. I also aim to explain my methodology somewhat. This should let me focus on working code samples in the following posts.

The first major point I’d like to get across is that this is a problem that has been thoroughly solved over 20 years ago. I’m not breaking new ground here. Instead, I’m trying to present a really, really easy-to-follow guide on how to build one yourself. To anyone looking at building a JPEG encoder themselves, my advice to you is this: Read this post, then start building your own. When (hopefully if) you get stuck, refer to my later posts. This will make sure you don’t ‘skip ahead’ at any stage, as many people often do when writing JPEG encoders.

The second point is to stress that I am not writing an optimal encoder! This encoder is going to suck. There are only three criticisms of these posts I want to hear:

• My code has bugs
• My code could be refactored for clarity
• My writing is unclear or confusing, and could use re-wording (suggestions welcome!)

If you find yourself thinking “Hm, that looks inefficient” – Yes, it is. I’ve made the code as easy-to-follow as I can, often at the expense of efficiency.

It should also be pointed out that I’m going over ‘baseline’ JPEG here; there are other modes of JPEG, but this one is the first (and easiest) to implement. Perhaps in future I’ll go over progressive.

Documents and References

I’ll put my references up front; if you really want to understand, you should read these things:

• For a JPEG library you can use in production, you should probably use libjpeg – http://libjpeg.sourceforge.net
• The JPEG standard itself is laid out in: ITU T.81 – http://www.itu.int/rec/T-REC-T.81
• And you should also refer to JFIF, the de-facto standard for fully specifying images know as ‘JPEGs’ – http://www.w3.org/Graphics/JPEG/jfif3.pdf
• For a somewhat-readable single-file JPEG encoder written in AS3: http://code.google.com/p/as3corelib/source/browse/trunk/src/com/adobe/images/JPGEncoder.as

I’ve added that last link to the list, as having another source to lookat whilst you’re doing this is no doubt going to be invaluable (as it was to me).

So now lets get down to the details, and take a look at how you might take an RGB image and encode it into a “.jpeg” file:

High-Level JPEG

1. Convert the image from RGB to Planar YUV (technically YCbCR, hereafter referred to as YUV)
2. Break up the image into 8×8 ‘chunks’, treating Y, U and V as separate images
3. Transform each chunk of discrete data into the frequency domain using the Discrete Cosine Transformation
4. ‘Quantize’ each 8×8 block – Throw away some of the information to obtain better compression
5. Perform Run Length Coding of each 8×8 block – Group 0’s together
6. Huffman Encode each 8×8 Block
7. Write the file, with appropritate formatting and headers

I intend to go into detail about each of these steps, along with working sample code, in my following posts. Unlike some other guides, I’m going to actually write code that will output a JPEG at the end; this isn’t pseudocode I’m writing, its for realz.

For now, lets go over each of these steps, and determine what they actually mean.

Convert From RGB to YUV

Most sources of ‘RAW’ data take the form of a rectangle of RGB data. This is the mode that computer monitors operate at, or that cameras take images in. An image is divided into ‘pixels’, each of which contains 3 bytes representing Red, Green and Blue data.

One file format used to store raw-rgb data is PPM, which also happens to be the file format I use in my examples. See http://en.wikipedia.org/wiki/Netpbm_format for more information on PPM.

Please visit http://graphics.stanford.edu/~jowens/223b/examples.html and download ‘lena.ppm’, or alternatively please google and download “lena.ppm”, which is usually a 512×512 Raw RGB image used in basically every JPEG example anywhere ever. Hey, I’m a sucker for tradition.

So, RGB is Red-Blue-Green, one pixel is stored with all three color components, so for every 3 bytes read you get one pixel. Great, we understand now!

So whats this YUV then? Well, put simply, its a completely different way of seeing the world.

So, RGB. We have 3 values that, when combined, make a ‘color’. Lets say we have the bytes (0xFF, 0x00, 0x00) – Thats red. (0xFF, 0xFF, 0x00) – Thats yellow (red + green = yellow). We understand.

Now, imagine we have 3 little lights; a red light, a green light, and a blue light. And we’re trying to represent our color values using the lights. So we turn the red light on all the way, and we get red! Now we turn the green light on all the way, and we get yellow!

But that not all we get. Not only do we get a different color, we also get more light. In fact, we have twice the light!

YUV is essentially a representation of this concept; the Y stands for ‘luminance’, or “how bright is the light?”. Obviously, turning one light on all the way is 1/3 as bright as turning all 3 lights on at the same time. We then use the U and V components to specify the actually color, using a ‘color plane’. There are still 3 color components here, thats important to note; we’ve gone from color represented by ‘Turn these three lights on, each by this much’, to ‘Turn the lights on to be this bright, and make that brightness out of this combination of lights’.

Theres a little math involved, but once you take the variable ‘brightness’ out, you can figure out how to represent the combination of the 3 lights needed to make the desired color using only 2 numbers; thats U and V.

Chunk Image

This isn’t really a big step, but its important to note; JPEG breaks the image up into 8×8 chunks, and treats each separately. It also acts on Y, U and V as completely different greyscale images; hence the need for ‘planar’ YUV as input.

The 8×8 restriction also means that JPEG cannot store images which aren’t multiples of 8 width and height, and in the case of baseline images, 16. I’ll go into this restriction further in later posts, but for now thats just the way it is.

Transform into the Frequency Domain

The frequency what now?

This is a fancy term for some very cool mathematics. Essentially, we can think of an 8×8 grayscale block as being comprised of a set of 64 8×8 ‘base images’, merged together on top of each other. These images are all built from cosine functions at different frequencies in the X and Y directions.

In this step, we transform our image from being made up of 8×8 ‘pixels’ to being made up of 8×8 ‘images’. This transformation has some useful properties, one being that the human eye is much better able to see low-frequency sub-images than the high-frequency ones. This lets us throw away more data from high-frequency sub-images. I’ll elaborate more on this in a later post, don’t worry.

For now, just understand that we feed in an 8×8 image made of signed integers representing magnitude, and we get out an 8×8 image of signed data.

For futher reading, please read: http://en.wikipedia.org/wiki/Discrete_cosine_transform#Multidimensional_DCTs

Quantize – Throw data away

This step is part of what makes the transformation into the frequency domain so handy – We can throw some data away, and most human being won’t notice. Thats the theory underpinning this step at least.

We define an 8×8 ‘Quantization Matrix’, which just so happens to match the 8×8 blocks we just transformed.

Take each value in the 8×8 transformed image, divide it by some value corresponding to the position in the matrix.

As you can imagine, this throws away a lot of data. Typical values in the quantization matrix might be anywhere between 16-100. This is the really ‘lossy’ stage in the JPEG encoder.

After the division, we round to the nearest integer.

Run-Length Coding

As you are probably familiar with, integer division often leads to Zeros. In the case of JPEG, this is a great thing, as we happen to have a very clever way of encoding zeros (more on that next).

Image we had the following data:

5, 0, 0, 0, 0, 6

JPEG encodes this data as:

5, 4 O’s, 6

Huffman Encoding

This is the part of JPEG encoders that so many people have a hard time explaining, and I’m actually going to split up my discussion of this particular topic into two posts later on.

For now, its important to note: JPEGs don’t huffman encode Values Themselves. JPEGs huffman encode a byte, made of two distinct values:

4 Bits (A Nibble) – How many zeroes precede this value in the bitstream?
4 Bits (A Nibble) – How large is the following value?

We then put the value into the JPEG bitstream. Imagine the value ‘6’ in binary – 0110. How many bits did that take? 4 (1 is used to indicate sign). How many 0’s precede this value? 4. So JPEG writes the following to the bitstream:

Huffman_encode(4 << 4 + 4)
write: 0110

Write the file, with appropriate headers

The JPEG header isn’t amazingly complicated, but it can be really annoying. For now, lets just say the JPEG Headers we write to disk look something like:

• I’m a JPEG
• I’m a JFIF JPEG
• Some cruft
• I’m this big
• More cruft
• These are the Quantization Matrixes I use
• These are the Huffman Tables I use
• Here is some data
• Huffman-Coded Bitstream
• I was a JPEG

I’ll go over how to actually write all these headers into the bitstream in later posts. For now, the important things to understand are that We always write our Quantization Tables and Huffman Tables into the JPEG, there are no ‘defaults’.

This also means we have complete control over the huffman tables and quantization matrixes. I, for one, am happy to use the defaults.

Closing Words

And thats the JPEG high-level overview! In my next post, I’ll be going over how to convert from lena.ppm to lena.yuv, and writing a simple test app that shows how to do this and display both files back using SDL.

This was the last post that won’t include a fully-functional code snippet for you to digest, I promise.

I hope this helps someone.

Simplest Way To Read a Site using Java

Here is the simplest method I’ve found to use apache HttpClient to open a website.

This is useful as a ‘starting point’ for more complicated web interaction, and I’m putting here as a reminder to my future self:

import java.io.InputStream;
import java.io.StringWriter;

import org.apache.commons.io.IOUtils;
import org.apache.http.HttpEntity;
import org.apache.http.HttpResponse;
import org.apache.http.StatusLine;
import org.apache.http.client.HttpClient;
import org.apache.http.client.methods.HttpGet;
import org.apache.http.impl.client.DefaultHttpClient;

public class Tester {

    public static void main(String[] args) throws Exception {

        // Setup our request
    	HttpClient client = new DefaultHttpClient();
    	HttpGet httpget = new HttpGet("http://www.google.com");

        // Execute the request
    	HttpResponse response = client.execute(httpget);

        // Retrieve the status and entity
    	StatusLine status = response.getStatusLine();
    	HttpEntity entity = response.getEntity();

    	if (status != null) {
    	    System.out.println(status.getStatusCode() + " - " + status.getReasonPhrase());
    	}
    	
    	if (entity != null) {
    	    InputStream instream = entity.getContent();
    	    StringWriter writer = new StringWriter();
    	    IOUtils.copy(instream, writer, "UTF-8");

            // TODO: Something fun with the webpage content
    	    System.out.print(writer.toString());
    	}
    }

}

For further reading, the HttpClient documentation is excellent:

http://hc.apache.org/httpcomponents-client-ga/tutorial/html/fundamentals.html

My Vimrc.

Here is what I use as my vimrc. Comments, suggestions and critiques welcomed.

set nocompatible
set autoindent
set smartindent
set tabstop=4
set shiftwidth=4
set expandtab
set smarttab
set ai
set si
set showmatch
set ruler
set incsearch
filetype plugin on
set autoread
set backspace=eol,start,indent
set ignorecase
set hlsearch
set noerrorbells
set novisualbell
set t_vb=
set tm=500
syntax enable


Things I need to install on Ubuntu

An ongoing list:

(This is in order of when I realized I needed them)

• NVidia driver
• Chromium
• Bazaar
• Vim
• LAMP Stack (Apache, Php, Mysql)
• Adobe AIR Runtime (for Pandora)
• CompizConfig Manager
• rtorrent
• Selenium
• Xvfb