computer « Reenigne blog

Archive for the ‘computer’ Category

Sampling keyboard

Thursday, July 3rd, 2008

I'd like to write a piece of software which makes it trivially easy to record and instantaneously play back sound. This piece of software would be operated by holding down keys on the computer's keyboard. For example:

Holding down 'R' records whatever goes into the computer's microphone while the key is held down and stored in the next unused buffer.
Holding down 'P' plays back all the buffers at the same time (until the last buffer runs out or the key is released, whichever happens first).
Holding down 'B' does both (with appropriate cancellation of the output signal from the input signal).

This software would enable a truly epic (and slightly shorter than normal) reading of the children's book "Doggies". For those unfamiliar with the book, there are ten dogs, each of which has a different bark ("Woof", "Yap yap", "Ruff ruff ruff" etc.). On the first page the first dog barks, on the second page the first and second dogs bark and so on.

With the aid of this software, the human reader/operator need only make each dog sound once. Furthermore, all the dog sounds would be heard simultaneously, making the immediate vicinity sound like a dog pound by page ten.

I'm sure there are other uses too, but this was the inspiration.

Posted in books, computer, fatherhood, humour | No Comments »

PAL version of demo machine

Wednesday, July 2nd, 2008

The demo machine described the other day could easily be generalized to PAL output. There are some complexities though. Because of the missing quarter cycle of the carrier frequency per line, the PAL signal for a still image repeats every 4 frames. This means that in order to do the same "extremely simple, highly standards-compliant demo" that was possible on the original demo machine for NTSC, we need 2.7Mb of sample data. Let's run with this and round up the PAL machine's memory to 4Mb - rather than making the PAL machine as similar as possible to the NTSC machine, we should take the opportunity to introduce some variety.

Similarly, the CPU clock speed for the PAL machine should be (exactly) 17.734475MHz.

Generating interesting standard PAL signals does have some complications that NTSC signals don't have. Because of the 25Hz offset, the colour carrier frequency starts at a different phase on each line, meaning that a sprite needs to have different sample data depending on its vertical position. I expect that most demos written for the machine would use one of three simplications of the PAL standard (as most if not all computers and consoles that generate PAL signals did):

eliminate the 25Hz offset so that the colour carrier phase repeats every 4 lines
use a whole number of subcarrier cycles per line (making the chroma patterns vertical)
eliminate interlacing, doubling the frame rate at the expense of halving the vertical resolution

These simplifications change the horizontal and vertical retrace frequencies slightly from the standard 15.625KHz and 50Hz rates, but not so much that real hardware is likely to fail to display the intended image.

Posted in computer, emulation, inventions, video | No Comments »

NTSC decoder

Tuesday, July 1st, 2008

I want to write a piece of software that simulates a colour television (well, monitor really). It would really be a filter - the input is a sampled, quantized composite (CVBS) signal at some sample rate and the output is a series of video frames scaled to some resolution. I'd want the composite->RGB transformation to be done at the same time as the horizontal scaling to maximize quality whilst minimizing computation time. That means dynamically generating the appropriate filter kernel for a particular pixel width and sample rate.

Such a thing would be particularly useful for emulating old computers and consoles which generated a composite colour signal directly (including the demo machine of yesterday's post). In particular, it would render colour artifacts and interlacing perfectly). It would also be useful for simulating (for example) how an image would look on a TV for applications like DVD mastering.

This is the kind of image it will be able to generate (this mock-up was done at fixed resolution and not in real time):

No high-frequency chroma filtering was done on this image, so you can see the chroma artifacts. I wanted to include an animation showing the dot-crawl effects, but animated GIFs don't go up to 60fps. It does look uncannily like a TV screen though.

Writing this filter might even inspire me to fix up the NTSC emulation in MESS and improve the video emulation of machines like CGA, Apple II, CoCo and Atari 400/800.

Posted in emulation, video | 1 Comment »

Demo machine

Monday, June 30th, 2008

If one were to design a computer specifically for the purpose of having Oldskool-style demos written for it, what would it be like?

I came up with a few requirements:

Oldskool "feel"
Attractive output: sampled sound and realistic looking (still) images can be achieved very easily
The more skilled the programmer, the better effects can be achieved - very great skill is required for the best effects
Hardware as simple as possible
Easy to emulate
Fun to program

To get that Oldskool feel but still allow realistic looking still images, I decided to base it around a composite NTSC signal. It turns out there is a standard for digital composite NTSC signals - SMPTE 244M, so I just picked the 8-bit version of that. The video hardware is about as simple as video hardware could possibly be - just an 8-bit DAC that repeatedly cycles through a consecutive region of memory and dumps the bytes to the output at a frequency of 14.318MHz (4 times the color carrier frequency). This is also the CPU clock speed (the CPU is in sync with the pixel clock).

Technically, a still image in this format that is fully NTSC compliant requires 955,500 bytes (933Kb) of memory (2 frames*910*525) because the color carrier phase alternates between frames. Given that the machine's memory size should be a power of 2 (so that we can map 32-bit addresses to physical addresses just by clearing the top bits) I decided to give it 1Mb (any more and it stops being so Oldskool). This doesn't necessarily mean that you need to use almost all the memory to store the framebuffer - by tweaking the burst/sync patterns you can get a 912*525 (468Kb) interlaced mode where you only need one frame, or a 912*262 (233Kb) non-interlaced mode (again with only frame), both of which should be compatible with any composite monitor. These have usable resolutions (including the overscan area) of about 720*480 and 720*240 respectively (with respective CGA-esque pixel aspect ratios of 5:6 and 5:12). So this gives a nice bit of flexibility to software with no extra hardware complexity.

One disadvantage of this setup is that it may be possible for software to damage some composite monitors by creating sync pulses too often. So one would probably want to use an emulator when testing/debugging programs! Also, scrolling is fiddly because you have to move the image data independently of the sync/burst pulses. There are block move instructions which can move 4 pixels per clock to help with this, though.

Audio is done in a very similar way to video - set the beginning and end of the region of memory and the hardware cycles through that memory range turning bytes into samples and putting them through a DAC. Another register is used to set the sample rate (I decided a fixed rate would be too inflexible).

Programs are just 1Mb memory images which are dumped into RAM. The first two words of RAM are the instruction pointer and the stack pointer, so execution starts at the address pointed to by the word at 0. I/O registers are also at the start of the memory region.

Most instructions are 1 cycle long (with the exception of instructions like the equivalents of "REP MOVSB" and "REP STOSB") to enable effects that require cycle counting to be done as easily as possible. Most instructions are 1 byte long (with the exception of instructions that have a 1-byte, 2-byte or 4-byte immediate argument). The CPU is 32-bit (to make addressing that 1Mb of memory easy). The architecture is stack machine based (kind of like Java) - I have a soft spot for such architectures because they're really easy to write decent compilers for (registers are helpful at the hardware level for making processors fast, but that isn't a particular concern here). Devolving the CPU has some ideas for generating a good instruction set.

Because of the cycle counting and simplicity requirements, there are no hardware interrupts - all timing must be done by cycle counting. This also means that there are no instructions whose purpose is to determine some value N and take O(N) time to do it - so no "REP SCASB" in this architecture. I don't think that is very useful for demos anyway, and it's a non-goal of this design to be suitable for general purpose computing tasks like searching and parsing.

It would be pretty easy to generalize this architecture to make a games machine - just have a register whose bits reflect the up/down status of controller buttons.

Now, while I'd like to believe that building such a machine would revitalize the Oldskool demo scene by providing a new focal point, I suspect a more realistic point of view is that because programming such a machine would be such a non-applicable skill, because the limitations of the machine constrain the possible effects, and because there would be none of the nostalgia inspired by actual Oldskool hardware, nobody would actually be interested. But it's still an interesting exercise!

Posted in emulation, inventions | 3 Comments »

My favorite programming font

Saturday, June 28th, 2008

Many colleagues, on seeing my screen for the first time, have been horrified at how small the text on my screen is. I tend to use 1600x1200 monitors, and a 6x8 pixel font for coding purposes. I have good vision at normal head/screen distances and I like to be able to see a lot of text at once (I can see the "big picture" and also the details without having to explicitly zoom).

My preferred font is the 6 point Terminal font that comes with Windows. When I started my new job, I switched to a Linux machine for most of my day-to-day work and one thing that took me a long time to figure out was how to get my terminal windows to display this font. I got it working in XTerm but copy and paste works better in Gnome terminal, which refused to acknowledge any non-TrueType fonts or even bitmap fonts in a TrueType package.

I eventually went through the same route that this guy went through to create his fonts - I extracted the bitmaps from the .fon file and turned them into outlines by creating a square for each dark pixel. The resulting .ttf file is 30 times as big as the original bitmap but it seems to work fine with everything I've thrown at it.

Here is the resulting TrueType font and here is what it looks like:

Posted in computer | 1 Comment »

Plug-ins should not be in the same address space as the main process

Friday, June 27th, 2008

After some thought I have come to the conclusion that a software architecture which allows third-party code to run in the same process as the main program is a bad idea.

The first problem with such an architecture is reliability - how do you protect yourself against bugs in the third-party code? The short answer is that you can't - the plugin has the ability to stomp all over your process's invariants. The best you can do is terminate the process when such a situation is detected.

The second problem is that a compiler can't reason about the third-party code (it might not even exist at compile time). This means that there are all kinds of checks and optimizations that cannot be performed (like some of the stack tricks I mentioned a while ago).

The third problem is that one cannot tell what code the plug-in will rely on - if it sticks to documented interfaces that's okay, but (either deliberately or accidentally) a plug-in might rely on undocumented behavior which causes the plug-in to break if the program is updated. This forces the program to have ugly kludges to keep old plug-ins working.

If plug-ins are run as separate processes communicating with the main program via well-defined IPC protocols, all these problems are solved. The down-side is that these protocols are likely to be a little more difficult to code against and (depending on the efficiency of the operating system's IPC implementation) may also be significantly slower. The speed problem seems unlikely to be insurmountable though - current OSes can play back HD video which involves the uncompressed video stream crossing the user/kernel boundary - few applications are likely to need IPC bandwidth greater than that.

Posted in language, security | 2 Comments »

I want to run as root

Wednesday, June 25th, 2008

With all the hype about Vista's User Access Control functionality, an important point seems to have gone largely unsaid. UAC protects the integrity of the operating system, but does nothing for the user's files. If I run some bad software in a non-user account, it can still read my financial documents, delete my photos etc. These things are much more difficult to fix than the problems UAC does prevent (which can be fixed by reinstalling the operating system).

The trend towards more Unix-like operating system structure annoys me somewhat. I want to run as root/admin all the time. If ask the for some critical system files, the operating system shouldn't second guess me, it should just do what I asked. I have been running Windows systems as administrator for years and it has never been a problem for me in practice. I don't ever want to have to input my password for machines that I own that I'm sitting in front of (remote access is different).

I think a better security model for a single-user machine would be not to authorize individual commands but to authorize programs. When a piece of software is downloaded from the internet and run, the OS calls it makes should be sandboxed. If it attempts to modify the system directories the OS should fake it so the system directories are not modified but so that it looks to that application like they have been. Private user files should just not appear to be present at all (not even findable but read-locked).

Vista is actually capable of this to some extent but it is only used as a last resort, to enable legacy programs to run. Applications released since Vista tend to have manifests which allow them to fail instead of get lied to - I don't think a program should even have the ability to tell that it is being lied to - if I want to lie to my media player and tell it that the sound output is going to a speaker when in fact it is going to a file, I should be able to do that. This is similar (but not quite the same) as a chroot jail in Unix, though chroot is not intended to be used as a sandbox for untrusted applications.

I suppose that, having said all that, what Microsoft have done in Vista does make sense for them - in the long run it will probably reduce support calls and promote development of software that requires only the minimum of privileges to run. I just wish I could turn it off completely without the annoying side-effects.

Posted in security | No Comments »

Hakmem 2

Thursday, June 19th, 2008

I found the original hakmem to be a terrific read when I discovered it years ago - some really interesting bits of mathematics, puzzles, short programs, algorithms and hardware hacks. There is material enough in there to inspire several lifetimes worth of research.

But the world has come a long way in 36 years, and I think we're overdue for a sequel. I'm not the only person who thinks so.

Things that should be in Hakmem 2:

Quake's fast inverse square root.
Simon Tatham's Infinity Machine.
Puzzle: Solve Tetris on a grid of width 4. Tetris can only be lost, never won, so solving it means finding an algorithm that allows one to play indefinitely no matter what pieces are given. Btw, Tetris on a grid of width 4 is a fun game - very different strategies apply than for normal Tetris though.
Crash course in geometric algebra.
Hardware: The Joule Thief.
Use of space filling curves to make 2D maps of 1D spaces (or n-D binary spaces).
Techniques for drawing fractals (IFS, L-systems, escape time)
Solutions to Pentominoes on various grids
How to draw the INT curve from Godel, Escher, Bach (there are some clues here).
Top ten Perl one-liners.
Software Transactional Memory
Parsing using Parsing Expression Grammars

As well as a compendium of handy techniques, hakmems can be thought of as a zeitgeist - a gauge of what hackers are (or should be) thinking about at the time they were written.

Come to think of it, a lot of my blog entries would make good Hakmem 2 entries. Hmm...

Posted in computer | No Comments »

Weather for computers

Sunday, June 8th, 2008

I think some people who use computers daily find that there is something kind of monotonous about them. They're always the same, day in day out. Once you've got used to the quirks of your machine (which you need to do to be productive) there are no surprises anymore.

People who work in the big blue-ceilinged room however (in many places) have weather and seasons to deal with. I suspect the variation helps their job satisfaction.

Suppose one wrote an application for giving computers some equivalent of weather. It would subtly modify the desktop theme on a day-to-day basis (sometimes even more often), changing colours slightly, modifying the screen brightness, perhaps adding rain or snow effects in the background. Nothing that gets in the way of what you're doing too much, it just adds a little unpredictability and variation to ones day. I suspect such an application could be quite popular if done well.

Posted in computer | No Comments »

Rendering rings of teleportation

Wednesday, June 4th, 2008

Rings of teleportation are very handy things to have around. The surface bounded by one ring is equated with the surface bounded by the other, so if you put something through one ring it will come out through the other. (Like the portals in "Portal", but more portable). They don't exist, of course, but this technicality doesn't prevent us from drawing pictures of them.

Writing code to render these things is an interesting exercise. It's easy to do with a ray tracer - if a ray intersects the disc inside one ring, just continue it to the equivalent point on the other ring.

Once that's working, you can put the rings side-by-side so that light goes around in circles - if you put your eye point in the middle you can see an infinite tunnel.

A trick you can play is to reverse the orientation of one of the rings so that you look through one ring, out of the other to an object, the object will appear to you to be inverted, as in a mirror image.

Another trick is to make the rings different sizes, or shapes. As long as there is a 1:1 function equating points on one surface with points on the other, it works fine.

However, having rings of different sizes or non-circular shapes opens the possibility of putting one ring through the other. What happens then? It seems like the "infinite tunnel" then becomes a real thing rather than just an optical effect, but where does the second ring exist in real space? It seems that the only place it can appear is through the other side of the first ring, but that would mean that every point in space appears in an infinite number of places - this seems like it would have rather drastic consequences.

So it seems more likely that the second ring would be prevented from going through the first somehow (perhaps a ring edge would get in the way).

Posted in graphics, physics | No Comments »

Reenigne blog