Archive for the ‘computer’ Category

Fans and walks

Saturday, June 11th, 2005

Grrr, the IT group at work forcefully rebooted one of my work machines to install a patch, giving me only half an hour's notice and no opportunity to say "no, later". Trouble is, that machine has a fan problem (okay, a pen lid stuck in a non-essential fan to stop it rotating because it rattles) and whenever it reboots it sits at the BIOS screen saying "Fan failure - press F1 to continue" until I (or someone else) physically goes into my office and presses F1. There doesn't seem to be any way to disable this fan check. Fortunately I'm going out that way anyway this evening but it is still a bother.

I had a very pleasant walk to work and back yesterday through the arboretum (apart from the fact that it rained on me in Redmond). It was nice to leave my car at home for once but the entire journey took 70 minutes each way so I don't think I can afford the time to do that every day. I could shave quite a bit off that by cycling to the bus stop instead of walking but the walk through the woods was the best bit - I ought to try to find time to do that walk every week or two.

Mr Jenner on Channel 9

Wednesday, August 25th, 2004

Robert Scoble, a Technical Evangelist at Microsoft, just came around and interviewed me (and a few other people on our team) for Channel 9 - look for the video to be there in a week or two.

If I'd known I was going to be on TV I would have brushed my hair this morning.

A new blog

Thursday, July 29th, 2004

A new initiative at Microsoft means that everyone (at least in my division, not sure about others) has to spend at least 4 hours a month interacting with customers and partners. It's a good idea in principle but unfortunately I have never actually had occasion to seriously use the tools I write - I've never written any software targetting the .NET Compact Framework other than trivial programs to test my own work. Therefore I'm really not the person to answer the sort of questions my customers ask.

Fortunately I found a loophole - I have to interact with customers, but they don't necessarily have to be my customers. I've started a work blog here which talks about C++ and general programming techniques. I'll continue to post here just as frequently (posting here less frequently would be extremely difficult) and will continue to talk about the same things, as the sort of things I talk about here would probably not be appropriate for my work blog.

More geekism

Sunday, July 11th, 2004

I finally got my 8253 timer project finished. One minor hurdle that I didn't anticipate is that MESS's abstraction of the host computer's soundcard and its emulated CPU aren't synchronized. The soundcard is supposed to request samples from the emulated CPU at 44.1KHz, but according to the emulated CPU it seems to be doing it slightly faster than that (or the emulated CPU is running slightly slow by the soundcard's standard) so my buffer keeps underrunning.

The way to fix this is to tell the CPU to generate samples at a slightly higher rate (according to its clock) so that the soundcard and the CPU stay in sync. The trouble is, I don't know exactly how much faster the soundcard is than the CPU. Besides which, it seems to fluctuate and the ratio may even be completely different on a different machine.

The next thing I tried was dynamically adjusting the sample rate 60 times a second to the value which was calculated for the previous time-period. The problem with this was that the variations in the sample rate could sometimes be quite large, and the resulting "flutter" of the emulated computer's soundtrack sounded absolutely awful. Also, the buffer might now be slightly less full than optimal (leaving little room for further error) or slightly more full than optimal (causing the soundtrack to "lag" behind the graphics a bit). Clearly the most elegant way to solve this would be to smooth out these variations in such a way that the average sample rate over long time would be correct.

Next, I set up a running total of the "drift" time, and adjusted the sample rate in proportion to this. Of course, this caused the sample rate to oscillate around the correct value - I needed some damping to remove "energy" from the system. A couple of pages of calculations later I had modelled the system with a second order differential equation and solved for the critical damping value. After some tweaking of the buffer length and time-constant values it now works wonderfully - no buffer underruns, no noticable flutter and the graphics and sound are fairly well synchronized.

The only problem now is the aliasing - the 8253 timer in the PC can generate frequencies of up to almost 600KHz, and because of the rather unscientific way I'm downsampling that high-frequency waveform down to 44,100Hz (roughly) all the harmonics too high for the soundcard to play are aliased down to frequencies between 0 and 22,050KHz (roughly) so when you attempt to play a square wave, you get a whole pile of harmonics you weren't expecting and it sounds rather less than perfect. Since the sampling rate drifts up and down, playing a constant high-pitched tone makes all sorts of swooping noises. I wonder if it would be feasable to use a proper finite impulse response filter to downsample while removing all the frequencies that are too high-pitched to play...

For those rare few of you for who are not interested in all this geek stuff, here are some rather spectacular mazes.

Geekism and gunkism

Tuesday, June 22nd, 2004

One of my ongoing projects is getting old computer games (particularly the old Windmill Software games) to run properly on modern hardware. One technique for doing this that I have recently been experimenting with is emulation - specifically, the Multiple Emulator Super System. This is almost there, as it features cycle-exact emulation of an 8088 processor and hardware-level emulation of a CGA card, thus getting the graphics and speed just right for these old games.

The one place MESS falls down is its emulation of the 8253 Programmable Interval Timer. This small but very important circuit exists almost unchanged in every PC ever made (as well as a number of other computers such as the Telenova Compis, the INDATA DAI, the Sharp MZ-700 and the Tesla PMD-85).

In modern operating systems, the 8253 is used by the task scheduler to interrupt whatever the machine is currently doing so that another program can get a chance at running, but these old games used it for advanced sound effects and "random" number generation. As such, they generally pushed it to the limits of its capabilities, so a very accurate emulation is needed to get these games to work properly.

The 8253 is well documented but unfortunately (though understandably) all the documentation available is written for people who want to program the thing or build a computer a which uses it, rather than for people who want to duplicate its functionality in an emulator. So there are a number of obscure edge-cases like "what happens if you do x, but half way through you do y" which aren't documented. In the interests of accuracy, I want to get these edge cases to work just as they would on the real hardware.

I'm finding myself having to do some real science to figure out the internals of this chip - formulating hypotheses and devising and running experiments to prove or disprove these hypotheses, and gradually constructing a "grand unified theory of the 8253" (if you will). Sometimes it's pretty straightforward, but other times tne observations must be made indirectly. For example, some of these experiments require timing as accurate as a millionth of a second, but this is a fraction of the time it takes to actually read data from or write data to the device in question. So the only way to do these experiments is to fire a whole load of data at the chip ("tuned" to maximize the probability of creating the desired event), record what comes back and then sort through the results (sometimes using statistical methods) to figure out if the edge case that I'm trying to reproduce actually happened, and if so what the result was. If the experiment is run enough times, hopefully the event I'm looking for will actually happen. It's quite a lot like doing high energy particle physics, except I'm searching for logic gates instead of Higgs bosons.


The bathroom sink was draining really slowly, so I decided to remove the U-bend and clean it out. You would not believe the evil things that lurked in there - a foul-smelling black, grey and green sludge held together with human hair. I would have taken a picture of it, but it was so unholy I doubt it would show up in photographs (like vampires in that respect). Hours and a long hot shower later, I still feel dirty.

Lethargy

Monday, March 29th, 2004

I have reached new heights of laziness. Instead of standing up, walking to the other end of the table (which is, ooo, a good 6 feet away) and changing the track on Winamp I used VNC to log into my other computer and changed the track that way.

I am so proud of myself.

Evil Attack Squirrel of Death!

Wednesday, December 10th, 2003

This is one badass squirrel.

I am tired. I stayed up last night fixing a friend's computer, which had become infested with spyware. I say infested and I really mean it - this thing was absolutely chock full of the stuff. I don't think I've ever seen it get so bad - there seemed to be more bad applications there than good ones (certainly the "run at startup" section of the registry was less than half the size by the time I had finished). Goodness only knows what they had been doing with it to get it in that state.

In computer folklore there is a story about two programs called Robin Hood and Friar Tuck which would act together to prevent either of them from being terminated. Well, it seems that spyware authors have discovered this technique. Not only that, but if you try to rename one of the exe files (so the other process can't restart it when it's terminated) the other process will create another copy of itself, with a random name, in your Windows\System32 directory. That, ladies and gentlemen, is true evil. I've never even seen this behaviour in a virus. The only way to get rid of it is to have a specially written app that will find all of these processes in memory and kill them all at once (fortunately, such apps exist - seems I'm not the first person to try to get rid of this thing).

At least I've got all my Christmas shopping done (I just hope it all arrives in time).

Fractal gallery

Friday, November 2nd, 2001

For those of you who can't get enough of fractal pictures, here are some of my favorites. The orbit types were created with programs of my own devising, written with DJGPP and Allegro. The others were created with Fractint, at 1600x1200 and resampled to 800x600.

Ultima maps

Friday, November 2nd, 2001

Warning! You will find major spoilers here if you haven't completed these games yet!

Maps from Ultima VI

Britannian surface

Dungeon level 1

Dungeon level 2

Dungeon level 3

Dungeon level 4

Gargoyle surface


Maps from Savage Empire

Eodon Valley surface

Myrmidex caves

Surface level caves

Underground city of Kotl


Maps from Martian Dreams

Mars surface

Mines

Dream World

Dream World

Mine and underground parts of Martian city

Coal mine and power plant


About the maps

The scale of these maps is 1 pixel per step. The data is stored in the files MAP and CHUNKS and isn't too difficult to decode, but colouring is fiddly. To colour these maps I modified the MAP and CHUNKS files to find out what tile each number corresponds to. The tiles are as follows:

Ultima VI (left), Savage Empire (centre), Martian Dreams (right)

Note that these aren't all the graphics from the games because there are two types of tile. The other tiles are object tiles, the positions and types of which are stored in the files in the SAVEGAME folder. Going to a finer scale would be rather pointless without deciphering this data. For example, you can see even at this scale that the buildings are empty.

It would be really cool to make a 1:1 scale map including all the objects, equivalent to the Eagle Eye spell. Unfortunately it would be a bit too large for your web browser - stored as a GIF file each large map would take up at least 70Mb! However, it would look nice scaled down (even better than these maps at the same scale) and it would be good to have a program that would let you scroll around and zoom into/out of the map. It would also be nice to create a census of all the characters in the games and find out the purpose (if any) of the message "Winona Ryder is a really hot babe" in Savage Empire and Martian Dreams. I may do these things someday.

Surprising stuff the maps revealed

I was surprised that the maps in Ultima VI actually form a three dimensional structure - if you scale up the small maps to the size of the large one then all the cave entrances, holes and ladders line up. The same is not true of Savage Empire and Martian Dreams. In fact, in Savage Empire the "level" isn't even related to the 3 dimensional configuration of the world.

The authors embedded hidden information into the maps as you can see - SMB (Stephen Beeman) in Savage Empire and Gryphon (Philip Brogden) in Martian Dreams. There are also some hidden areas in the poles of Mars. I don't know if these have any purpose in the game or not - I'll tell you when I've completed it.

Although the "shape of the world" is supposed to be flat in Ultima VI and Savage Empire and spherical in Martian Dreams, the true shape of each world is a torus or doughnut. If you could walk off the left you would reappear at the same place on the right, and if you could walk off the top you would reappear at the same place on the bottom. In fact you can see this effect in the Savage Empire maps: there is a river which disappears off the top and reappears on the bottom on the surface, and the rightmost walls of the underground city are on the left. This is used in Martian Dreams to create a cylindrical (okay, spherical...) world rather than a flat one.

Savage Empire uses only 4 of the 6 levels. Level 5 is empty but level 6 contains the gargoyle world straight out of Ultima VI! It doesn't quite make sense because some of the chunks (8x8 blocks of tiles) are different, but it's clearly the same map.

Links

These maps were inspired by those of Otmar Lendl. Check them out, he's got some of Ultima IV and Ultima V as well.

Mobygames entries for Ultima VI, Savage Empire and Martian Dreams.

Bartholomew Melnicki has gone much further and started plotting objects on the maps. Check it out!

Non-hierarchical filing systems

Thursday, June 21st, 2001

Traditionally, hierarchical systems have been used to store information - a particular fact might be in a particular paragraph on a particular piece of paper, which is stored in a particular folder in a particular drawer of a particular filing cabinet in a particular office on a particular floor of a particular building in a particular city of a particular country of the world.

This is also the manner in which computers tend to store information. On a Windows system there is the "My computer" icon, under which there are a number of drives, each of which can contain files and subfolders. On a Unix system there is "/" (root) under which there are subdirectories (on my Debian GNU/Linux installation these include "/bin", "/dev", "/home", "/lib", "/lost+found", "/tmp", "/usr", "/var"). Again these contain files and subdirectories which can also contain files and subdirectories. A particular piece of information (file) is located by specifying an ordered list of folders - for example, this document might be found at "/home/andrew/work/website/andrew/computer/hierarchy.html" on a Unix system, or "C:\Work\Website\Andrew\computer\hierarchy.html" on a Windows system.

This is how things have always been done, and it is generally taken for that this is how it will always be done. That doesn't mean it's the best way, however. Modern systems are breaking down the boundaries of their hierarchies. For some time, Unix systems have had a facility called "symlinking", whereby an entry can be created in a directory which is neither a file not a subdirectory by a placeholder leading to another file somewhere else on the hierarchy. This can be likened to an entry in a dictionary for a synonym, or a piece of paper in a filing cabinet saying "this document is in folder x in cabinet y". Thus you can effectively have two copies of the document, but not use precious space having two copies (plus, if the document is edited, you don't get out of date versions cropping up).

Windows, too, is catching up. The "Single Instance Store" is more of a space saving device than an organizational tool, though - if you have two identical copies of a file on your hard disk, it puts them both on the same physical place on the hard disk. If you change one of the two files, then it creates a copy and modifies that rather than modifying both files.

The trouble is that in any given hierarchy, there is more than one place you might want to put a given file. Take the typical MP3 collection, for example. Do you classify by artist, or genre, or name of song, or stuff them all in together? At the moment this is left up to personal preference, but that's not necessarily the best way of doing things. I organize my MP3s by artist, except for the songs by artists whom I only have one song by, which I put all in together in my MP3 "root". This has it's advantages (I can see at a glance all of the artists and a good fraction of the song titles, the root folder isn't too unweily and I don't always have to go into a subfolder to see what songs I have by a given artist) and it's disadvantages (I have to do a search to find out the artist if I only know the song name, there's no concept of genre, because of the fact that Windows lists all the folders before any of the files, I occasionally find I have duplicates and if I get another song by an artist I only have one song by, the previous song get moved, which means it doesn't get played until I rebuild the playlist).

What is needed is a new filing system, one in which the searching, sorting and linking operations needed to overcome the disadvantages in any hierarchical system are made fundamental operations of the system - one in which the needs of the users rather than technical considerations are put first.

What I envision is a system whereby a file is located by one or more keywords in much the same way as you use a search engine to locate a document on the world wide web. So you could enter "music Frank_Sinatra" to get a list of music files by Frank Sinatra or "music Mack_The_Knife" to get a list of recordings of that song (possibly by various different artists). The key point is that the system doesn't distinguish between "music/Frank_Sinatra/Mack_The_Knife" and "music/Mack_The_Knife/Frank_Sinatra". Or even between either of those and "Frank_Sinatra/Mack_The_Knife/music" - it's completely commutative.

This system is much more reliable than a search engine, though, because a search engine indexes all words in a document, whereas this system just indexes "filenames" which are a lot less haphazard. A "filename" on this system might look something like this:
Media: Recorded music
Format: MP3
Artist: Frank Sinatra
Title: Mack The Knife
Size: 3,703,497 bytes
Length: 4:24
Bitrate: 112Kbps
Last modified: 15th January 2000, 02:10
Comments: ...

And so on, with any other infomation relevant to that file. This might seem a bit unwieldy for a filename, but remember that all this information is stored by the computer anyway (usually twice, in the case of an MP3 file, because of the ID3 tag) and with a bit of careful programming it should be possible to consider this the "filename" with minimal extra overhead.

Obviously not all fields are relevant to all files (for example, "Bitrate" would have no meaning for a text file, but "Written by" would). It is important that exactly which fields are present is flexible, and that new fields can be added that weren't necessarily even thought of when the filing system was designed.

So now operations which would previously have been classed as searches are classed in the way that simply looking in the contents of a particular directory are now. You could even make it work the same by having ordering the fields in some way. For example, "media" might be a fundamental class, equivalent to a directory in the root directory. Upon opening "media" the computer would show the different types of media files you have on your computer: "recorded music, musical score, photographs, drawings, movies, animations, web pages". Upon opening "recorded music" you might then be faced with a list of artists, and so on, just like it works today. But you aren't limited to that order. Upon opening "media" you could also choose to go directly to "artist" and see various different types of file associated with a particular artist.

It is probably best left up to the user to configure which items appear by default in the "root directory" - for example someone who did lots of things with music on their computer might choose to put a link to "music" there whilst someone who just had a few music files might just leave it in "media". The system provides an infrastructure whereby people can organize their files and make them easy to search and browse through, but is also very flexible.

Where the system really comes into its own is if it is linked to other computers. You could search for media by "Frank Sinatra" not just on your own hard disk, but in *the entire world*. You could see what someone's been doing lately by searching for files they have written (and made public) and sorting them in order of date. The possibilities are almost limitless.

Of course, there's still the problem of designing user interfaces to access this information easily. It's taken decades to perfect an interface to access files in the current, hierarchical system (in my opinion, the "Explorer" in Microsoft Windows 95 is the best and friendliest file management interface yet designed, although it still has its flaws) but hopefully what has been learnt from that will make it possible to implement an interface for the new system much more quickly.

If you're interested in this subject, there is now a mailing list devoted to discussing it. Join by clicking
here.