Code blog

August 6th, 2011

It's been a year since I last wrote something here, but I haven't been idle. I made a resolution to write some code every day and commit some kind of functional change to my GitHub repository each day, even if it's just a one line change. So far I've kept to it pretty well (apart from travel days). I'm adding more stuff there all the time, most of it brand new but some of it is stuff that I wrote previously and which hadn't been under version control before (updated to work with the library code I'm also committing). I know my github workflow is rather unusual - lots of projects in one repository and commits corresponding to days rather than to features. But the version control is mainly for my benefit at the moment (since it's just me working on this stuff) - I just want to have all this backed up offsite, to be able to see previous versions and to have a record of what code I wrote when. The current set of subdirectories under of the main repository is:

  • 4to8 - little program I wrote to convert the audio data for the game Fire! by New Deal Productions from 4-bit to 8-bit format so that I could play it back properly.
  • 8088 - various projects relating to the original IBM PC/XT - a cycle-exact emulator and a demo I'm working on.
  • UnityALFE - a compiled language I'm playing about with. This name is a bit overloaded, I might call it ALFE (A Language For Everything) instead.
  • codec - an idea I had for a method of compressing audio with extremely low playback overhead. Doesn't currently work, and I have no idea if it ever will.
  • collage - a program to genarate a header image to use on this blog (not yet finished).
  • crc32 - a handy utility for computing CRC32 checksums of files.
  • crtsim - a CRT simulator.
  • euclids_orchard - a program to generate a Euclid's Orchard image.
  • fractals - some fractal plotter programs. Currently there is only one - a zoomable Bifurcation fractal.
  • image_resample - my custom image resampler.
  • include - various libraries used in multiple projects.
  • intervals - code and simulator for my intervals bar toy that is in progress.
  • multifunction - a program to search for useful multifunction gates.
  • oscilloscope - an oscilloscope program based on an idea I had for rendering waveforms. Not really started.
  • perceptual - a program to find maximally distributed colours in perceptual colour space.
  • primes - prime number experiments.
  • ravioli - an idea I had for eliminating memory fragmentation.
  • run_random - recursively enumerates all files in a directory and then picks one at random to run.
  • strobe - an Arduino program for a strobe light with controllable duty cycle and accurately controllable frequency.
  • test - some unit tests for libraries in the include subdirectory.
  • tone_matrix - the code for my physical tone matrix.

I'll blog more about these in upcoming entries. And I'll try to remember to update this list as I add more projects to the repository.

Posted in blogging, computer | No Comments »

Politics simulator

August 6th, 2010

I've occasionally thought it would be fun to have a computer game where you start out with some land, some people and some natural resources, and your job is to found a country and run it. You get to write your constitution, set up laws and so on and see how things unfold. You might also play the part of a politician once the country is set up. You might get voted out, which changes the set of powers you have (and makes the main next objective "get back into power"). Maybe there are other countries on the "virtual planet" - you can invade them, embargo them, make treaties with them etc. They have their own objectives. You get problems thrown at you (war, dissent, natural disaster and so on) and have to make changes to your policies to try to keep everybody happy.

Given the similarities between writing laws and writing code, I suspect this might devolve into a "programming game" style activity (albeit with a rather more political type of geekiness). I also suspect that there are so many aspects of human activity that would need to be simulated that making it realistic would be an overwhelmingly large task. But of course it doesn't need to be perfectly realistic to be fun - it may be fun enough with just easy-to-implement large-scale economic features.

Posted in games | 3 Comments »

Transverse wave

August 5th, 2010

Right after creating the original Simple Harmonic Motion program, I wondered what would happen if you connected lots of masses and springs together in a line. I came up with what I've now translated into this:

Controls are the same - dragging the mouse moves one end of the "string", the leftmost slider (or the + and - keys) controls the tension and the rightmost one (or the < and > keys) controls the friction.

Source code.

Posted in applets | No Comments »

Simple Harmonic Motion

August 4th, 2010

Some 14 years ago when learning about second order differential equations, simulating physical systems on computers and simple harmonic motion, I wrote this DOS program which (because it's kind of fun to play with) I have now translated into flash:

The idea is very simple - it's just a mass (the white ball) with a green pen, connected to a point by a piece of elastic (the white line). The point doesn't move except when the mouse button is held down, when it moves to the mouse pointer location. This means that the mouse is essentially the forcing function for a 2D, second-order linear differential equation. Which means that (depending on the parameters) the mass follows the mouse pointer, possibly smoothing out its motion, possibly oscillating around it.

There are two slider controls on the right - the leftmost one (or the + and - keys) controls the tension and the rightmost one (or the < and > keys) controls the friction. Press escape to clear the screen.

Source code.

Posted in applets | 1 Comment »

Virtual physical tone matrix

July 28th, 2010

Here's a virtual version of my physical tone matrix, implemented in Flash, so you can play along at home:

Much of the code is a direct translation from the C code in the non-virtual version, so it works in a way very close to the real thing. Even the sample rate and frame rate are close (though they are not synchronized - it's not a cycle-exact simulation).

Click or drag on the screen to turn the lights on and off.

The knobs are (from top left) sustain, tempo, tuning and volume. Above and between the sustain and tempo knobs is the escape switch, which brings up or closes a menu of funcions. These are, from top left:

  • Sine wave (default)
  • Square wave
  • Triangle wave
  • Sawtooth wave
  • Random wave
  • Pattern editor (default)
  • Coarse waveform editor
  • Fine waveform editor (not particularly useful or easy to use)
  • Tuning editor
  • Miscellaneous editor
  • Save current pattern/waveform/tuning/settings to EEPROM
  • Load current pattern/waveform/tuning/settings from EEPROM
  • Toggle life mode
  • Toggle random mode
  • Toggle microtone keyboard mode

The miscellaneous editor shows 6 rectangles. Clockwise from top-right these are:

  • Patterns per loop (a 5-bit binary number) - if this is not 1, then whenever the pattern reaches the right a new pattern is loaded from EEPROM.
  • Fixed tuning - just disables the tuning knob. This exists in order to allow the tuning to be set more accurately on the non-virtual version, not really necessary on the virtual version
  • Update noise continually - when set, the waveform is continually updated with random data, so all frequencies sound the same. This is slightly different to the "random wave" waveform preset, where the 256 waveform components are initialized with random numbers but then don't change, so there are some audible differences between playing them at different frequencies.
  • Beats per pattern - repeat before the pattern gets all the way to the right, useful for rhythms that don't factor into 16.
  • Sustain override - overrides the function of the sustain knob so that this parameter can be set digitally.
  • Tempo override (a 16-bit binary number) - must be greater than 0x200 to work - smaller numbers are faster).

The EEPROM save/load functions load or save the data for the current editing mode (pattern, coarse waveform, fine waveform, tuning or miscellaneous). To use them, press save or load. The screen then shows the current EEPROM contents. Click on a location to choose where to save to or load from. Depending on the editing mode, 2-8 lights will be lit per "saved file".

Fun things to try:

  • Put the PTM in random mode and light 10-16 lights. Then just sit back and listen to some randomly generated music for a while.
  • Draw a glider or Lightweight spaceship, put the PTM in life mode and turn the tempo all the way up to maximum.
  • Make a horizontal line in pattern editor mode, turn the sustain all the way up so that the sound is continuous, then switch to the coarse waveform editor (which was inspired by this). Click and drag around to move the "sliders" and see what sounds you can make.
  • Make sure the pattern editor is empty and then switch to microtone keyboard mode. The lit lights correspond to the white notes on a piano keyboard - the unlit lights are the frequencies in-between (i.e. it's a 34-TET instrument). Try to play or tune or make some weird music. Trying the different preset waveforms is fun in this mode.
  • (Advanced) Try to create a different tuning such as major scale or chromatic (instead of the default pentatonic) using the tuning editor. Each line of the tuning editor represents a frequency as a 16-bit binary number (LSB on the left), in units of roughly 0.24Hz (16Mhz / 226).
  • (Advanced) Make some patterns and save them in consecutive locations in EEPROM, starting at the top left. Then use the "patterns per loop" setting in the miscellaneous editor to play them back in sequence and make a tune longer than 16 notes.

The copy and paste functions on the right-click menu work and are compatible with the original Tone Matrix applet.

Source code is here.

Posted in computer | 2 Comments »

Map reprojection

July 26th, 2010

Ever wondered what a standard equirectangular projection map of the world would look like if the poles were in different places? Wonder no more! Just click and drag on the map below to move a piece of the world to somewhere else on the map - the rest will follow.

Flash is the best way to do this sort of thing in terms of market penetration, but Actionscript is surprisingly difficult to get started with. Adobe's tools are great, I'm sure, if you want to make animated vector movies but in trying to learn how to use them to do programmatically generated stuff like this I just got lost. Perhaps I just haven't discovered the right bit of documentation. I eventually found this to be a way in to the maze.

I hope to write some more fun little web toys like this in the coming weeks.

Edit: source code.

Posted in maps | 2 Comments »

Credit card designed for internet shopping

July 23rd, 2010

It seems like it would be possible to make a great deal of money by creating a payment system better than credit cards. Paypal has come closest to doing this, but has a lot of problems.

How could one make credit cards better? It would be very difficult to get your payment system into as many retailers as Visa and Mastercard, so perhaps aiming for a niche would be a good idea. One such niche might be internet purchases. Develop a payment system/credit card designed specifically for internet purchases and it could be very popular.

One major difference between a payment system designed for the internet and one predating it is that one could authenticate the transaction, not the identity. Whenever you buy something online, you put in your card number as usual but then (unlike with normal credit cards) there is an extra step - you log into the payment system's website and approve the requested transaction. Until you have done that, the merchant doesn't get any money (and won't deliver the goods). This cuts out all "stolen card" type fraud, since the thief would also need to steal your payment system password (which never goes anywhere near the merchant). This would allow this payment system to undercut the existing credit card issuers and become competitive. Fraud caused by loss of the payment system password would be treated the same as fraud caused by the loss of any other online banking password (which I think varies from place to place).

This system would still need a "chargeback" mechanism to combat fraud from merchants (and mechanisms to combat fraudulent chargebacks) but my impression is that the costs of these are small compared to the "stolen card" costs.

With suitable cellphone applications for authorization, the system could even be used for brick-and-mortar stores as well.

Unlike Paypal, this system would actually be able to lend money like a credit card, it wouldn't need to be linked to a bank account or credit card.

Posted in economics, Uncategorized | 2 Comments »

USB device classes and usage pages

July 22nd, 2010

The Universal Serial Bus interface specification includes various fields to specify what kind of device is plugged into a computer, and what numbers correspond to what buttons, lights and so on on the device. All these are documented in the Human Interface Device Usage Tables. When I discovered this, it provided me with some amusement as alongside the normal mice, keyboards, scanners there are some more exotic devices. Section 5, which describes "Simulation Controls" (i.e. standardized controllers for operating various simulators). As well as the ones you'd expect like a steering wheel (Usage ID C8) and a flight yoke (Usage ID 24) there are such controls as "Standard spaceship controls" (Usage ID 04).

I had no idea that spaceship controls were standardized. I suppose it makes sense, so that once you learn how to fly one sort of spaceship you could (in principle, in some sort of emergency situation) have some chance of operaing an unfamiliar craft. Of course, if that emergency situation is being kidnapped by aliens you're probably out of luck as I doubt any alien spaceship designers have read the USB specification documents.

What's even funnier is the "Standard magic carpet controls" (Usage ID 0B). Being a magical (not to mention fictional) mode of transportation, it seems quite amazing that magic carpets have standardized control mechanisms. You'd think the interface would be something as indistinguishable-from-sufficiently-advanced-technology as "just think about where you want it to go", but the USB documents go into quite some detail about how to fly a magic carpet:

Allows a device to be generally classified as one that uses the standard control of a magic carpet. This control is a bar, grasped by both hands, that controls the Yaw, Pitch and Roll of the carpet.

The bar, at which the pilot sits, may be pushed forward or pulled back to cause the carpet to dive or rise, respectively. In the zero position, the carpet is in level flight. Pushing forward on the bar causes the carpet to nose down and generates negative values. Pulling back on the bar causes the carpet to nose up and generates positive values.

Turning the bar turns the carpet. In the zero position, the carpet travels straight ahead. Pulling back on the right side turns the carpet to the right and generates positive values. Pulling back on the left side turns the carpet to the left and generates negative values.

Rotating the bar rolls the carpet. In the zero position, the carpet travels level. Rotating the bar in a clockwise direction rolls the carpet to the right and generates positive values. Rotating the bar in the counterclockwise direction rolls the carpet to the left and generates negative values.

So there you go - now if you find yourself in a Persian golden-age fairy tale, you know how to get around.

Posted in computer | No Comments »

Time derivative accounting

July 21st, 2010

Sometimes I think it would make things simpler if, when I logged onto my bank's website, there were two sorts of transactions listed. One would the normal sort: "x dollars paid to y on date z". The other sort would be "x dollars per month paid to y since date z". For example, my monthly mortgage payment would be listed as a single transaction, not a separate one each month.

Certain calculations are much easier when done with time derivative values. For example, interest on my mortgage accumulates daily but the payments are monthly, so to figure out what is actually owed at any time requires a lengthy spreadsheet or complicated program. If the interest accumulated continuously, and the payment also happened continuously, the calculations would be much simpler.

Normally, interest is specified as a percentage by which a debt grows. But to know what that really means, you have to specify how long it takes to grow by that much - this can lead to confusion (deliberate or accidental). It would be much better if interest was specified as a growth constant f (with standard units of Hz, bizarrely enough), such that if you have a debt x_0 at time 0 and changes only because of interest (no payments or fees) then after time t the debt will have grown to xe^{tf}. If you are also making payments at the rate of r per unit time, then the debt x is given by the differential equation \displaystyle \frac{dx}{dt} = xf - r which has the solution

\displaystyle x = \frac{r}{f} + (x_0 - \frac{r}{f})e^{ft}

Hence one can easily solve for the time it takes to repay the loan:

\displaystyle t = \frac{log(-\frac{r}{x_0f - r})}{f}

Or you can solve for the repayment rate if you want to repay the loan in a specific amount of time:

\displaystyle r = \frac{x_0fe^{ft}}{e^{ft} - 1}

Similarly, one can do calculations around retirement savings. Suppose you have x_0 in retirement savings today and the inflation growth constant is i. If you are saving at a rate of r e^{it} and investing in something with a growth rate of f, and you want to retire when you can maintain an income of y e^{it}.

The amount you need in savings at retirement is x in:

\displaystyle \frac{dx}{dt} = xf - ye^{it} = xi

Plugging this into the equation for the savings rate while working:

\displaystyle \frac{dx}{dt} = xf + re^{it}

Gives:

\displaystyle y = r+(x_0(f-i)-r)e^{(f-i)t}

Solving for retirement time:

\displaystyle t = \frac{\log(\frac{-r}{x_0(f-i)-r})}{f-i}

Or savings rate:

\displaystyle r = \frac{e^{ft}x_0(f-i)}{-e^{it}+e^{ft}}

Of course, all that assumes you can get a fixed rate of return and that inflation stays constant. In reality, these variables are constantly changing. There's also the matter of risk to consider - trading off means for variances, but you get the idea.

The current inflation rate is about 300 picoHertz. The highest recorded hyperinflation is about 6000000 picoHertz (6 microHertz).

How should payment rates be specified in user interfaces? "Dollars per month" is probably the most meaningful multiplier - to make it consistent we should use a standard average month length of 2629746 seconds. Current balance would be updated continuously supposing that the paying of salary and recurring bills could also be paid continuously. One would want to take care to set limits on the payment rate for bills (just as one does with direct debits) so that a mistake at the gas company doesn't instantly wipe out your savings.

Further derivatives could be taken into account so that one could pay exponentially increasing bills like the retirement savings above without making any adjustments. The ultimate outcome of this would be to link everything to inflation and display/specify amounts in "year 2000 dollars" (for example) - in other words, the Inflation-linked currency I've written about before.

Posted in economics | No Comments »

Musical toy design

July 20th, 2010

I've been thinking about how to create the interval bars instrument/toy as a sort of sequel to the physical tone matrix. Here's some of the design space I've explored.

First I wondered how we could sense the relative position of each bar in space. I fairly quickly decided that putting a tiny microcontroller in each of the bars would probably be the best way. The root box queries the bar it's connected to, which then sends back its length, orientation (i.e. which of the 4 connectors it is being queried through) whether its switch is being touched or not. This bar then performs the same query on the bars connected to its three other connectors, sends this information back to the root and so on, walking the tree. A program to transmit a few bits of data, walk one node of a ternary tree and then pass back another string of bits sounds very simple, but as we'll see there are a lot of complications.

The first microcontroller I looked at was the cheapest one I could find, the PIC10F200. This thing is seriously cheap and seriously tiny (both physically and software-wise). It has 16 *bytes* of memory (same as a single SSE register), runs at 4MHz and can run programs that are up to 256 instructions long. It also costs just 30 cents in large quantities. I thought it would be an fun programming challenge to fit such a simple program into such a tiny space.

Unfortunately, I failed in this endeavour because the PIC10F200 only has 4 IO pins (6 pins altogether - the other two are power and ground). Only 3 of them can be used for output. I needed at least 5 pins - one for each directional connector and one for the switch. I tried to figure out some way of addressing each direction with a unique pair of IO pins but couldn't figure out a scheme that would actually work.

So then I decided to go for the next PIC up, the PIC12F508. This has 6 IO pins (perfect), 512 instructions, 25 bytes of RAM and costs $0.41 in large quantities. I bought a pile of them. The PIC16F54 is even cheaper ($0.39), has 12 IO pins and runs up to 20MHz but has no internal oscillator.

I originally figured that I would drive all the PICs with a single external clock to make it easy to keep them in sync. However, I discovered a major problem with this approach - these microcontrollers don't have a external clock oscillator mode. You can use the internal oscillator, an external crystal or an external RC timebase. It might be possible to use an external clock in EXTRC or XT mode but it's out of spec, might damage the microcontroller, might be unstable, might degrade the clock signal and might cause one of the other IO pins to be unavailable. Also, even with cycle exact code there is complexity in the timing because each instruction takes 4 or 8 clock cycles, and you can't control which of the 4 phases you get.

So I decided to use the internal oscillator. It's factory calibrated to +/- 1% so I should be able to synchronize two PICs just by adding appropriate delay loops, making sure that signal pulses are long enough to cover all the possible times when they might be read, and that the reader waits until the pulse is certain to have started before attempting the read. Programming in cycle-exact assembler is difficult enough when there's only one CPU to worry about, but when you're writing code that's going to run in sync on two CPUs and all timing is done by cycle counting and the CPUs have slightly different clock rates it's a nightmare!

The first version of my program took too much space (everything was unrolled and I had different code paths for each orientation). I got it to fit by moving some of the code into subroutines (you have to choose which code you put in subroutines carefully, since the stack only has two levels) but didn't have much space for delay loops.

So I rewrote it to avoid storing the "which port is the parent" and "which port is the child" information in the program counter. Now it only checks this information when reading from or writing to a pin, or checking all the pins to see which direction a signal will come from first. Takes less than half of the available space - brilliant.

The next problem is that only two microcontrollers can be communicating at once (one talking, one listening). If three are trying to communicate at once, eventually the middle one is going to face a time when it has to talk to both of the other two within a certain amount of time, and won't be able to satisfy the conflicting demands. So when a microcontroller is getting a bit of data from a child, it has to tell the parent to wait and we can't have a "bucket brigade" of bits. This means that we get quadratically slower as we get further from the root. Counting the cycles, I realized that (even before all the delay loops had been added) we were outside of our cycle budget to get a reasonably small latency.

To get the "bucket brigade" back, I realized that we had to have a way to synchronize all the microcontrollers at once. We can't use an external cycle clock for this but what about a much slower "heartbeat" signal shared between all the microcontrollers, coming in on the spare pin?

The idea is this: each microcontroller has a state variable. On each heartbeat, each microcontroller jumps to a subroutine corresponding to its state. This subroutine reads the pins set in the previous cycle, sets output pins for the next cycle and updates the state variable for the next cycle before going back to waiting for the next heartbeat. All the waiting is done at once, and we no longer have the precise timing difficulties we have before - as long as we have rules like "how late you can read the inputs", "how early you can set the outputs" and "how long the heartbeat can take" everything should work out just right. I think we can get much better performance with this system.

The musical toy is really about melody and harmony, but under the covers it's rhythm that makes it work.

Posted in hardware | 2 Comments »

« Older Entries
Newer Entries »