ad-free and forever open

One year ago, I released four Android apps into the Play store. Today, they’ve finally made me enough money to retire. Yes! I can afford that cardboard box in the alleyway at last! (Seriously, if your average developer is making money from mobile ads it’s news to me.)

Since they’ve done their job, I’m pulling the ads and releasing the source. Check out Quencher, MtX, Iconist, and Freebeard on GitHub!

hiccups

Apologies for the downtime–been having some server issues lately. I’m redirecting to a new server until the DNS is complete. All should be back to normal soon.

building a 3D surface plotter

I’ve been rendering surfaces for a few years now, and have even written a couple of demos around the topic. An arbitrary surface plotter was a natural evolution: enter an equation and see the result in real time.

splott

I brought this Android app to a working demo, then decided I didn’t have a use-case or story for it, and decided to open it instead. The source code is on GitHub, and you may do whatever you like with it.

The bulk of the graphics code comes from my previous open-source release, 4est. I copied over the 3D toolkit, which includes an implementation of the marching-cubes algorithm for rendering arbitrary surfaces. The movement code has been simplified and folded into the renderer and surface view classes to allow the user to scroll “around” the rendered surface. The surface mapper converts a function of the form f(x, y, z) into a set of triangles that represent the surface, and draws them.

The important question: how to generate that f(x, y, z) function from user input?

Well, I knew I’d need a parser–or rather, a parser generator. I once had to create a compiler for a C-like scripting language, and the experience taught me one essential lesson. Never write a parser. For all but the simplest inputs, it’s easier to write a grammar that describes your symbols and syntax, then use a third-party tool to generate a parser from that grammar.

Back when I was writing C, I used the flex lexical analyzer (transforms an input stream into a sequence of defined tokens) and the bison parser generator. For Java, I discovered Antlr, which combines both of these functions into one tool. If you’re already familiar with context-free grammars, the syntax should be familiar enough, and if not, there are plenty of examples (and the documentation, though not free, is inexpensive).

With Antlr, I developed a grammar that could handle expressions of the form f(x, y, z)=g(x, y, z), and a compiler to interpret the output of the parser. At this point, all I needed was a way to actually solve the calculation for a given point (x, y, z).

My initial instinct was to create an actual Java (or rather, Dalvik) bytecode compiler, so the expression code would run with as little overhead as possible. I found the DexMaker library, which can generate Android code at run-time. Though I found DexMaker easy to use, and was able to produce a working expression compiler without much trouble, invoking the generated code created a significant problem.

Any code generated via this library has to be called using the reflection API, which requires creation of internal objects, and thus incurs overhead. The marching cubes algorithm must test the expression at several points to generate each triangle, and many thousands of triangles must be generated to produce enough of a surface to observe. Multiply the object-creation overhead by a hundred thousand and it’s a major performance problem. The app was taking nearly a minute to render even simple surfaces.

I removed the DexMaker code and tried again, creating a simple virtual machine that could perform a few operations and transcendental functions on its internal registers and return the result. Of course, the most significant feature of this VM was that it didn’t create any objects on execution. With this, the app was able to render even complex surfaces in under a second.

4est

Some months back, I was playing around with a game idea that never saw the light of day. I haven’t had a lot of time to develop it, and I’ve kind of lost interest anyway. The game would have been called 4est, as in forest–the original game took place in a forest. Here’s a current screenshot.

4est

Yeah, the concept’s drifted a bit. There’s not a whole lot there–3D and audio engines, mesh and texture generation, and some simple UI code–but I figured someone might be able to make use of it. It’s on GitHub, and you are free to do whatever you like with it.

making a more efficient android audio engine

I’ve written a few real-time audio engines for my Android projects. The prospect of writing real-time code in Java would have amused me not that long ago, but the JIT compiler makes it possible. There are still pitfalls to watch out for, of course. Most programmers understand that you shouldn’t allocate objects inside a tight loop, but some potential problems are less obvious.

Here’s a stripped-down version of an engine I wrote very early on.

package com.example;

import android.media.AudioFormat;
import android.media.AudioManager;
import android.media.AudioTrack;

/**
 * audio synthesizer engine
 */
public class Audio {

	// audio track object
	private AudioTrack track;
	
	// length of buffer in shorts
	private int bufferLength;
	
	// sampling rate in Hz
	private int sampleRate;
	
	// audio hardware buffer
	private short[] buffer;
	
	// tone generator
	private Whistler whistler;
	
	/**
	 * ctor
	 */
	public Audio() {
		new Thread() {
			public void run() {
				init();
				while (true) {
					loop();
				}
			}
		}.start();
		
	}

	/**
	 * startup and initialization  
	 */
	private void init() {
		sampleRate = AudioTrack.getNativeOutputSampleRate(
				AudioManager.STREAM_MUSIC);

		bufferLength = AudioTrack.getMinBufferSize(
				sampleRate, 
				AudioFormat.CHANNEL_OUT_MONO, 
				AudioFormat.ENCODING_PCM_16BIT);

		buffer = new short[bufferLength];
		
		whistler = new Whistler(0.002f, 0.75f);
		whistler.setPitch(440);
		
		track = new AudioTrack(
				AudioManager.STREAM_MUSIC,
				sampleRate,
				AudioFormat.CHANNEL_OUT_MONO,
				AudioFormat.ENCODING_PCM_16BIT,
				bufferLength * 2, // length in bytes
				AudioTrack.MODE_STREAM);
		
		if (track.getState() != AudioTrack.STATE_INITIALIZED) {
			throw new RuntimeException("Couldn't initialize AudioTrack object");
		}
		
		track.setStereoVolume(1, 1);
		track.play();
	}
	
	/**
	 * main audio pump loop
	 */
	private void loop() {
		for (int i = 0; i < buffer.length; i++) {
			buffer[i] = (short)(whistler.get() * 32767);
		}
		track.write(buffer, 0, buffer.length);
	}

	/**
	 * generates a breathy tone at specified freqency
	 */
	class Whistler {

		float noiseFactor, limiter, qFactor;
		float t0, t1, t2;
		
		public Whistler(float nf, float lm) {
			noiseFactor = nf;
			limiter = lm;
			t2 = 0.001f;
		}
		
		public void setPitch(float f) {
			qFactor = (float)(1 / Math.pow(sampleRate / (2 * Math.PI * f), 2));
		}
		
		public float get() {
			t2 = (float)(-qFactor * t0 + noiseFactor * Math.random() * Math.signum(-t2) - t2 * limiter);
			t1 += t2;
			t0 += t1;
			return t0;
		}
	}
}

The heart of this engine is the Whistler inner class. It’s a noise-driven oscillator that produces a breathy sound, like a person whistling. Now, the code works, but the audio tends to drop a lot, especially if the CPU is busy with other things. Running a DDMS trace on the app produces this output.

audio1

Notice that the “audio pump” thread is almost completely black–it’s constantly running. That’s bad. What’s going on? Let’s zoom in.

audio2

Each of those colored blocks represents a function call. Though the JIT compiler can transform Java to native code, function calls still have overhead. To optimize our real-time code, we’ll have to reduce the number of functions we call inside our loops. Let’s start by replacing Whistler.get() with something that doesn’t require a function call for every sample we place in the buffer.

public class Audio {

	... snipped ...
	
	private void loop() {
		whistler.fill();
		track.write(buffer, 0, buffer.length);
	}

	class Whistler {

		... snipped ...

		public void fill() {
			for (int i = 0; i < buffer.length; i++) {
				t2 = (float)(-qFactor * t0 + noiseFactor * Math.random() * Math.signum(-t2) - t2 * limiter);
				t1 += t2;
				t0 += t1;
				buffer[i] = (short)(t0 * 32767);
			}
		}
	}
}

Our new function fill accesses the buffer variable of the outer class directly. Now, one function call fills the entire buffer! How does that affect our DDMS trace?

audio3

The audio pump thread is still going like mad. What’s the problem?

audio4

One of the top function calls listed in the trace is Audio.access$3, which you might recognize as a Java internal symbol. In order to facilitate access between inner and outer classes, the JIT compiler generates static accessor functions of the form class$access<number>. In this case, it’s referring to the buffer variable that we allocate in the outer Audio class, and access within the inner Whistler class. So, by accessing the outer class variable, we’re still making a function call within the loop. Fortunately, we can eliminate this call simply by passing the buffer as a parameter.

public class Audio {

	... snipped ...

	private void loop() {
		whistler.fill(buffer);
		track.write(buffer, 0, buffer.length);
	}

	class Whistler {

		... snipped ...

		public void fill(short[] b) {
			for (int i = 0; i < b.length; i++) {
				t2 = (float)(-qFactor * t0 + noiseFactor * Math.random() * Math.signum(-t2) - t2 * limiter);
				t1 += t2;
				t0 += t1;
				b[i] = (short)(t0 * 32767);
			}
		}
	}
}

Now, our efforts are starting to show results.

audio5

The audio pump thread is no longer a solid black line. We’re cutting down on the amount of work it has to do. However, we can do more. We know that function calls create overhead. Can we eliminate them?

There are two function calls in the fill function: Math.random() and Math.signum(). The first returns a random double value, and the second returns -1 for a negative number, 1 for a positive number, and 0 for zero. Let’s substitute our own code for these functions.

class Whistler {

	float noiseFactor, limiter, qFactor;
	float t0, t1, t2;
	long noise;
	
	public Whistler(float nf, float lm) {
		noiseFactor = nf;
		limiter = lm;
		t2 = 0.001f;
		noise = System.currentTimeMillis();
	}
	
	public void setPitch(float f) {
		qFactor = (float)(1 / Math.pow(sampleRate / (2 * Math.PI * f), 2));
	}
	
	public void fill(short[] b) {
		for (int i = 0; i < b.length; i++) { 
			
			float random = (float)(noise >> 16) / (float)(0xffffffffL);
			noise = (noise * 25214903917L + 11L) & 0xffffffffffffL;

			int signum = (t2 > 0 ? -1 : 1);
			
			t2 = (float)(-qFactor * t0 + noiseFactor * random * signum - t2 * limiter);
			t1 += t2;
			t0 += t1;
			b[i] = (short)(t0 * 32767);
			noise = (noise * 25214903917L + 11L) & 0xffffffffffffL;
		}
	}
}

Here, we’ve implemented a simple random number generator by taking a seed value (the current time in milliseconds) and multiplying/adding prime numbers to that value on each trip through the loop. (This is an example of a linear congruential RNG.) The signum function has been replaced with a ternary expression (we don’t need the zero->0 case). There are no longer any function calls in the loop. How does it look in DDMS?

audio6

Wow! The audio thread looks nearly idle. Removing function calls from inner loops eliminates a rather significant amount of overhead, and allows you to do a lot more in your audio engine.

link: the movie game

Hey, remember that guy who was in that thing? With what’s-her-name? What else was he in? With who? If you find yourself asking questions like this–or better yet, answering them–then I’ve got a game for you.

L.I.N.K. The Movie Game is a round-robin style movie trivia game created and designed by Shawn Pirelli of Blubird Studios, and programmed by myself. You can play with 2, 3, or 4 players. Start off with a movie title, and let the next player try to name an actor from it. The next player might name another actor from the same film, or mix things up by naming another film the last actor appeared in. How long can you keep it going? You’ve got 30 seconds to find out!

tablet6

Check the game out on Google Play, and visit Blubird Studios for more information!

iconist for android

You know, my website or application could really use some clip art. Not the cartoony kind, though, and not the kind where people from the 70’s are playing tennis. No, I need something abstract-looking, like those fancy curly things at the top of newspapers. Or maybe like a Rorschach test. Yes, that’s definitely what I want. Oh, and there has to be lots of it.

If you’ve ever said anything like that, today’s your lucky day. 

7in

Iconist generates abstract clip art. Lots of it, as a matter of fact. Scroll through a list of 65,000 clips, then reshuffle and scroll though another. And another. You want four levels of detail? It’s there. Monochrome, two colors, three colors, four colors? We got that. Custom sizes from 64 x 64 to 2048 x 2048? All yours. Mirror it horizontally or vertically, or both–or don’t mirror it at all. It’s up to you. Tap your favorites and they’re sent to the Android Gallery, where you can share them, upload them, or just gaze rapturously at them. Your call. Available FREE on Google Play.

microtonal explorer for android

It’s a human tendency to assume that the things we grow up with are natural–just the way things are meant to be. Take music, for example. As Bill Gates famously observed, “Twelve tones ought to be enough for anybody.” Or maybe that was Mozart. Anyway, those of us in the West might think the equal tempered twelve-tone scale is natural (even though it took thousands of years and loads of adventures to arrive in its present form), but there are lots of people out there with a different opinion. Here’s a nice little app that lets you explore a musical space that might be completely new to you.

7in-play

Microtonal eXplorer (MtX) allows you to create scales with any number of tones and any arrangement of intervals, then play riffs and chords from your new scale. Name your scale and save it in the database for later. Pull it out again whenever you feel like a little trip.

The application is available FREE on Google Play.

a better beard for christmas

I’ve just pushed a new version of Freebeard to the Play Store. It should be ready in a few hours–hopefully just in time for everyone getting a new Android tablet or phone in their stockings tomorrow.

I’ve completely rewritten the melody/rhythm generator algorithms. As I mentioned in an earlier post, I built a “chain of chains”, using a Markov chain to index an array of Markov chains in an effort to create recurring patterns. While I like some of what it did, I found it a little too unpredictable and prone to noodling. So, I had to come up with something new.

My solution was our old friend, Perlin noise. I created some one-dimensional discrete noise functions and found they worked nicely, especially for melodies. Using a small seed array gives a sort of “modulation” effect, like picking a four note riff and moving it up and down the scale.

Time for a little holiday cheer. Peace!

klammer: videophone for android

A month ago, I spent a couple of weeks developing a Wi-Fi Direct videophone app for  Android. I had some ideas about creating an outdoorsy chatty thing that would have worked even when you were far away from a wireless access point.

Unfortunately, Wi-Fi Direct has a fairly limited range, to the point that if you’re close enough for the videophone to work, you’re close enough to just wave the other person over. So, maybe not the best use of time. On the other hand, I did get a little experience with the technology, plus audio and video codecs, so that’s a plus.

Anyway, the source itself is now on GitHub, and you’re free to do what you like with it.