Memory upgrade

Some months back, I picked up a 1GB DIMM at a computer fair. It was cheap, which was about the only thing going for it, but I thought I’d take a chance on it. When I got home I plugged it into my PC, and it all started going horribly wrong. Needless to say, a few minutes later I was running memtest+ and finding millions of errors.
Continue reading

Posted in Electronics | Comments Off on Memory upgrade

Monotone hooks

I am now officially impressed with the extensibility of monotone.

Continue reading

Posted in Uncategorized | Comments Off on Monotone hooks

Web security

There are so many popular web applications around nowadays. Blogs, CMSs, Forums, Webmail, Site Administration, Project Management, Wikis, and many more. Yet I’m shocked at the lack of understanding of web security even among the authors of some of the most widely deployed applications.

Continue reading

Posted in Uncategorized | Comments Off on Web security

Playing with hardware

I decided to have a play around with digital hardware. Having been exposed to some verilog at work, and seen that FPGA development boards have become quite affordable, I thought I’d have a go.

Continue reading

Posted in Electronics | Comments Off on Playing with hardware

HP LaserJet 1010 and “Unsupported Personality: PCL”

I’ve had a HP LaserJet 1010 for a few years, and I used to have it directly connected to my server, running lpd and samba. When I first set this up, I was plagued by “Unsupported Personality: PCL” errors. After much messing about, it was partially fixed, at least enough that Windows would happily print via samba, and I could occasionally print from NetBSD systems. Sure, I sometimes had to reset the printer, but most of the time it worked well enough.

Recently I switched to CUPS, because it made it easier to run the print spooler on my server while physically connecting the printer to my NSLU2, in a different room. Ever since this switch, the “Unsupported Personality: PCL” errors have been back with a vengeance, along with other types of problems such as raw PJL/PCL being printed as plain text.

Continue reading

Posted in Uncategorized | Comments Off on HP LaserJet 1010 and “Unsupported Personality: PCL”

Why not to mow the lawn while making pizza

This is perhaps an instantiation of Murphy’s Law, mixed in with a little bit of a rant.

Pizza is good. Pizza is the staple diet of geeks all around the world. Pizza is especially good when it’s home made. So I decided to make some.

Now, the dough takes time to rise, and the sauce takes time to simmer, and the lawn was in desperate need of mowing. What could possibly go wrong?

Continue reading

Posted in Uncategorized | 2 Comments

NSLU2 and NetBSD

I did some rearranging of the network infrastructure in my house recently. The main aim was to move anything that made noise 24/7 into a cupboard out of the way. The downside is that it left the printer and a bunch of USB serial ports without anything to plug into.

The solution? A Linksys NSLU2 running NetBSD.

Continue reading

Posted in NetBSD | Comments Off on NSLU2 and NetBSD

Monotone databases

For various reasons, I had ended up with a bunch of monotone databases copied all over the place. Clearly this was unsustainable, and I’d always planned that if I got to that point, I’d set up a single central database for all my projects in a place where I could easily sync with it regardless of where I was working.

I don’t know why, but this always felt like significant effort, and so I’d been putting it off.

I finally took the plunge, and it was far easier than I’d imagined. In fact, once I’d created a user, decided on the filename for the database file and the name of the server key, it was trivial.

For bonus points, (read) access control is on the basis of per-branch patterns, so I can selectively make things available to people without sharing projects which aren’t ready for wider consumption.

Posted in Uncategorized | Comments Off on Monotone databases

Sudoku solver

I’ve been working on my sudoku solver.

It’s not the most efficient sudoku solver, by a long way. But the goal is not really just to solve sudoku. It’s to solve sudoku using pure logic, and to be able to show a logical path to the solution. If I wanted to just solve sudoku, I’d implement DLX.

The basic principles are quite simple. The problem is expressed in terms of logical statements constructed as disjunctions of predicates, where a predicate takes the form of “Box (X,Y) contains Z”, or “Box (X, Y) does not contain Z”.

There is essentially one logical deduction rule used. Two statements are resolved to produce one or more new statements by finding a eliminating complementary terms and joining up the result with an OR. For example, “(8,7) isn’t 5 or (8,8) isn’t 5” can be resolved with “(8,8) is 5” to produce “(8,7) isn’t 5”.

There is a constraint on the knowledge base which is that no statement can be equal to, or be a subset of, any other statement.

For (some kind of) efficiency, statements with a smaller number of terms are looked at first. Looking at a term involves resolving it with all other statements with which it can be resolved.

This converges pretty quickly for simple sudoku grids, but can take much longer for hard ones. So far I’ve tried it on some of the hardest “unsolvable” puzzles I’ve been able to find on the Internet, and while it does take a very long time for those (over an hour for some puzzles) it does eventually converge and give a correct result.

Perhaps one of the more interesting aspects of a solution using this method is that the solver can construct a DAG of the entire proof. The downside of this is that I now have to figure out a way of actually presenting that DAG in a simple enough way that it can be understood by a human. Some sort of pattern matching on the graph to remove “obvious” steps could be one way to go.

For kicks, I tried constructing a dot file from the DAG generated by solving a relatively simple sudoku puzzle, and passing it through dot. The result is an unpleasantly large 110 megabyte postscript file, spanning 285 pages.

I’m looking forward to finding some way to express the proofs more intuitively.

Posted in Uncategorized | Comments Off on Sudoku solver

Introducing Lightscript

For a week covering the new year’s celebrations at the start of this year, I ran a lightshow for the IS, which is a pretty cool event for young speakers of Esperanto. It’s the second such event for which I’ve provided lighting, and I was keen to learn some lessons from the first time round.

This time I had a few more lights to play with, and I wanted to have proper control. My lighting desk is perfect for smallish shows using static lights, such as theatrical events. It’s not so great at controlling intelligent fixtures. Last time, I spent far too much time actively playing on flash buttons (the sound to light feature on the desk is awful), and unplugging the DMX input to the scanners to put them into standalone mode. This time the room was bigger, I didn’t want to buy enough cable to do two DMX runs around the room in order to be able to separate the static and intelligent control signals, and I had more lights to flash than I had fingers.

The answer was pretty clear at this point – to buy a DMX interface for a PC.

Now here’s the rub – most of the free software out there for DMX control is next to useless when you start trying to do complex things. I wanted the flexibility to set up a multipurpose lighting rig, and flick instantly between sedate theatrical lighting, live rock bands, and night-time disco. And along with that, I wanted enough intelligence in the controller that I could leave it on automatic while I went to bed, or at the very least sufficiently automatic that the DJ could operate it by pressing no more than a couple of buttons.

I was fortunate enough to realise this some months before the event, and I decided that the best way to approach this would be to write my own control software.

After a number of initial ideas which resembled all-singing all-dancing GUIs with 3D rendering and intuitive drag-and-drop functionality, I realised that this was an unrealistic approach given the timeframe. I also realised that actually most of that was totally unnecessary. As a programmer, I should find a light scripting language a more hospitable environment anyway. And thus was born the idea of lightscript.

The implementation was very much a learning experience in the practicalities of standard computer science topics. The architecture I went with consisted of a compiler and a virtual machine. Linked into the virtual machine were a number of modules which did things which would be impractical or inefficient to implement within the script itself. Those modules covered things such as I/O, DSP and 3D maths.

The language itself ended up being fairly C-like in syntax, although a lot simpler in terms of language features. This was mostly because C-like syntax was fairly easy to achieve using lex and yacc, and it is something I would like to revisit in future versions of the system.

The compiler uses lex and yacc to deal with parsing, and then builds an AST. I went with an AST rather than directly trying to generate code from yacc’s semantic actions in order to make it easier to extend the compiler in the future, for example by adding optimisation. Currently, code is generated from the AST.

Code generation posed a few interesting problems. I’d chosen a very simple virtual machine model – basically no more than a stack machine, with an instruction pointer and a stack pointer. Each thread has its own stack. Local variables, function arguments and intermediate values are kept on the stack, and all stack accesses are relative to the stack pointer. Keeping track of the stack pointer became something of a challenge, and a large part of the debugging process involved finding cases where the stack pointer differed from what the compiler believed it should be.

Global variables are handled by internal functions – functions which are defined and implemented within the interpreter. These actually turned out to be the easiest variable handling in the compiler.

Floating point calculations were something of an afterthought, and are an area which could do with some redesign for the next version. Currently, there is only one storage type, because the size of a stack entry is fixed. Different storage sizes would require much more type knowledge than the compiler currently has. In the interests of speed of implementation, the compiler was taught just about enough about floating point to use floating point operations where required, most of the time. Places where this doesn’t yet work well are where the type of a value isn’t known, such as a function return value. Functions aren’t yet typed.

Another interesting thing that came up was the need to return multiple values. The syntax here is slightly different, in that you can have a comma-separated list of lvalues to which you assign the result of a function. Internally, it’s a kind of call-by-value function call scheme in which every function call has an implicit argument allocated for the return value, which is copied to the lvalue on completion of the function. If more than one item appears in the lvalue, some of the proper arguments are also copied. This is useful, although the syntax and some of the implementation details are up for review.

To avoid having to write another parser for assembly syntax, as is common in many compiler suites, I stored instructions internally in a linked list prior to generation of binary code. Printing them out as assembly instructions is also supported as a debugging option. As the binary format allows for variable length offsets in branches, a number of passes through the list have to be made to determine the branch lengths required for each instruction, and thus how big the instruction will be. Finally the code in written out to a binary file along with a header containing a symbol table of function entry points.

The simplicity of the virtual machine model means that the implementation of the virtual machine can be straightforward. The inner loop does a quick check to see if it needs to invoke the scheduler, and if not, decodes and executes an instruction. Some sanity checks are also performed to ensure that the program counter and stack pointer are both valid at all times. The thread is killed if bad things start happening.

A table of internal functions is kept. While some of these are pretty mundane things like global variable handling, printing strings and numbers, thread creation, wait and wakeup, this is also how the I/O and processing modules hook into the VM.

There are modules for DMX output, MIDI input (my lighting desk is good enough to provide a MIDI output, so I can use physical sliders and buttons for a UI) and mouse input. These are straightforward I/O modules.

A more interesting module is the beatdetect module. It takes input from /dev/sound, and performs some funky DSP to provide beat detection. I will most likely describe this module in a separate post.

Also likely to be described at a later date is the 3D module. This exists to perform mapping between 3D world coordinates and pan/tilt values for moving lights. It stores calibration data in persistent storage (a file), and provides the ability for the script to work in 3D world coordinates. This way, all the lights can operate in the same coordinate system, and the 3D mapping module can do the final translations before output is sent to the devices.

Getting the beatdetect and map3d modules right took a significant part of the total development time, and turned out to be much more difficult than I had originally imagined. But the effort paid off, because I was able to put together a decent lightshow, which was able to be driven from a microphone dangling above the DJ’s head, in combination with the occasional push of a button on the lighting desk to control high level aspects such as the choice of pattern, and strobing. Manual control of the lights by means of the mouse also made for an exciting new type of effect.

The few hours before the first night were nerve-racking. After getting beatdetect and map3d working satisfactorily, I had implemented switch statements in the compiler. They weren’t essential, but they made the script code much simpler. So I had converted large chunks of the script code to use switch statements where appropriate. Unfortunately, I hadn’t noticed straight away that certain cases in the switch implementation could leave the stack with a different number of items on it. Of course, when I finaly hit such a case, it was two hours before the first night’s show. I finally nailed the bug on the head barely five minutes before the start of the show.

I was quite proud though, that after that compiler bug, the system was solid and robust enough to go through a week of abuse and many nights of unsupervised running without a single crash. That way the payoff of putting all the complexity in the compiler, and keeping the VM simple.

There are many refinements I want to make in lightscript, and a number of things need to be redesigned. After sorting out some of the more ugly issues, I plan to release the code under an open source license.

Posted in Lightscript | Comments Off on Introducing Lightscript