Retro Console Dev

Yes, I am alive

2008-11-27T18:56:00.001Z

No, I didn't choke on a mince pie :)

I'm sorry for the lack of updates, both to the blog and to Daedalus. I've been working on Daedalus for about 10 years now, and those that have followed the project from the beginning will know that I have fairly regular periods of 'radio silence' followed by bursts of activity. I have lot of inertia, so once my interest shifts elsewhere it can take a long time to get me back on track. That's just the way I am.

This time around it's because I've been really busy with work. I don't want to go into specifics, but for the past couple of years I've been working on a high profile game, and since January most of my energy has gone into helping to get it finished.

I am unbelievably out of touch with the PSP scene. Recently, Kreationz got in touch to tell me about the progress that has been made with DaedalusX64. I was really pleased to hear that the project was being actively updated, particularly because I have a lot of respect for the people involved. The whole reason for making Daedalus open source was to give people the opportunity to learn from the source code and update it as needed, so it's great for this to be happening.

I can't guarantee that I'll have the time to actively help with DaedalusX64, or even that I'll be able to regularly update this blog. I thought it would be a good idea to give my public backing to DaedalusX64 so that the team can get on with rolling out updates. I probably won't be making a PSP release of Daedalus any time soon.

For what it's worth, I'm currently working on a new port of Daedalus. I'm going to keep the target platform secret for now, but I think it's very exciting. At the very least it means that I'm working on Daedalus again - I'm hoping to keep merging changes from DaedalusX64 back into the Daedalus source, and hopefully provide DaedalusX64 with one or two fixes of my own.

That's all for now. Apologies in advance if the next blog post is in December 2009 :)

-StrmnNrmn

Yuletide Update

2007-12-24T13:17:00.000Z

It's been a while since the last update so I wanted to give some news on how things are going with work towards the next release.

I've spent a lot of time working on getting the HLE audio code working on the Media Engine. I've been making steady progress, but it's been taking longer than I initially expected. Fortunately, I'm very close to getting all of the audio processing moved over to the ME - in fact I believe I have just one significant bug left to fix.

The issue seems to be a very odd synchronisation bug which causes the emulator to lock up when running the audio processing asynchronously. As with many of these types of bugs, it's proving quite hard to track down because as soon as I change the code to debug the problem, the issue goes away. A true Heisenbug :(

What's particularly annoying is that the bug is stopping me from measuring how much of a difference running the audio code on the ME makes. Hopefully I'll be able to fix the bug over the Christmas break and be able to publish some timings over the new year.

As part of this work, I've also been writing a general-purpose 'job manager', which coordinates batches of work between the main CPU and the ME. The idea is to build on top of J.F.'s MediaEngine.prx to provide a simple interface for queing up and dispatching work asynchronously. When a job is added to the queue, a flag indicates whether the job is suitable for running on the ME, or whether it should just be run asynchronously on the main CPU instead.

Initially just the audio processing will run through the job manager on the ME, but eventually it should be possible run other pieces of work asynchronously too. I'm hoping that it will eventually be possible to move parts of the HLE graphics processing to run asynchronously too, but I need to investigate things a bit more first. That's a job for future releases however.

Anyway, that's all for now. I'm off to eat mince pies and watch The Great Escape on tv. Merry Christmas everyone :)

-StrmnNrmn

R14 Progress

2007-11-25T23:21:00.001Z

It's been a while since I talked about R14 so I wanted to post a quick update on what I've been doing.

The Media Engine work has been going well. The job manager I talked about last week is now fairly functional and handles executing the audio upsampling code in 3 different modes: synchronously, asynchronously on the main processor, and asynchronously on the ME.

It's taken me a little longer to get the audio upsampling code working smoothly on the ME. I decided to focus on this initially (rather than Azimer's Audio HLE code) as it's a lot simpler and more self contained, but getting it working on the ME without any glitches required a little bit of work. I had to rewrite the simple ring buffer I was using to be lock-free. This is straightforward when dealing with a single reader thread and a single writer thread on the same processor, but a little more care is required when the reader and writer are operating on separate cores without cache coherency. I think getting this running glitch-free has helped prepare me well for the bigger task of getting Azimer's HLE code running asynchronously on the ME. I'll be working on this next.

Besides the ME work, I've had an interesting diversion getting some new font rendering working in Daedalus. I saw on the ps2dev.org forums that BenHur had released a library for rendering text using the PSP's built in fonts. I've always been a little unhappy with Daedalus's text rendering, and thought this would be a good opportunity to improve it. Here's a screenshot of the UI using BenHur's intraFont library (click through for a better-looking unscaled version):

I think this is looking a lot better than the previous font. The drop shadows really help make the text more readable. I also support multiple fonts for the first time, so the header text actually looks like header text :)

-StrmnNrmn

And the winner is...

2007-11-19T23:14:00.000Z

This has been one of the hardest posts I've had to write, because I know whichever entry I pick as winner of the icon competition, a lot of people are going to be disappointed that I didn't pick their favourite.

Trying to select a winner has forced me to think about what I wanted to get out of this competition. On the surface, the main goal of the competition was just to replace the ugly default icon on the PSP's XMB. However as I've checked out all the entries over the past couple of weeks, I've come to realise that the main objective of the competition should be to define an identity for Daedalus.

In the end, one of the main criteria I've used to select the winner is how well the design works as a logo, or identity, for the project as a whole. For this reason I've picked Patrick Ahmann's design:

I think Patrick's design is wonderfully clean and stylish, and the colours look especially crisp and vibrant on the PSP's screen*. The typography, particularly for the 'daedalus' logo is very simple and distinctive and I think it would work well as a logo on the web. What's more, I got quite excited about using the cog motif on the logo as a progress indicator on loading screens :)

So, well done Patrick!

I want to say a big 'thank you' to everyone who contributed. Many people put a lot of work into this and I'm really sorry that I could only pick one winner. I think the quality of the final 10 was excellent, so if you disagree with my choice hopefully there's something there for you :)

-StrmnNrmn

*annoyingly Blogger insists on downsampling the images above slightly, so they look a little fuzzy. Click through for the original versions...

Icon Competition - Shortlist

2007-11-17T12:50:00.000Z

I've just finished compiling a shortlist of what I think are the 10 best submissions for the icon competition.

I received just under 200 entries in total; I've been blown away by the response. Picking just 10 entries has been very difficult. In the end I had a 'longlist' of around 30 entries which I thought were superb, and it's taken me over an hour to whittle that down to just 10 entries.

Here is my shortlist, presented in the order they were submitted. Feel free to discuss these in the comments - I'll be reading your comments over the weekend, and I'll pick a final winner on Monday.

Thanks to everyone who entered - you're awesome!

-StrmnNrmn

Cladil

Pleaser

Pharonyk

Steven La

Victor Aguirre

Joël Dos Santos

Jay Mc

Patrick Ahmann

Hykypoo

juniorslick363

Edit 20/11/2007 12:00 Fix Pharonyk's name.

Last call for icons+backgrounds

2007-11-16T13:49:00.000Z

Just a reminder that today is the last day for sending in your entries to the icon competition. I'll be making the shortlist sometime tomorrow morning, so provided you get your entry to 12pm (that's noon - GMT!) on Saturday it will probably be included.

Once I've made a shortlist of what I feel are the 10 best submissions, I'll post them up here so that people can give their thoughts, before I pick a final winner on Monday.

-StrmnNrmn

Media Engine progress

2007-11-13T23:31:00.000Z

Over the weekend I described my plans for getting audio list processing working on the PSP's Media Engine. I'm making some decent progress so far. I've got Daedalus loading a kernel mode PRX to handle the ME nitty gritty, and I've managed to execute some test code on the ME successfully.

I've spent some time reviewing the audio code, trying to figure out if any bits are particularly amenable to running asynchronously, and trying to figure out if there is anything that is going to cause any problems when running this code on the ME. Fortunately it looks like all of Azimer's audio code is very straightforward C so there should be no problems getting it running on the ME once the synchronisation issues are dealt with. I've also realised that alongside the audio list processing there is also some expensive 44kHz upsampling code which will run very nicely on the ME too.

I have the feeling that debugging code on the ME is going to be particularly painful, so I want to try and catch as many of the obvious synchronisation bugs as early as possible. This evening I've started writing a job manager to 'simulate' executing code on the ME. The manager simply creates a thread which sits and waits for jobs to come in, mimicing the behaviour of the mediaengineprx. Once I've got the audio list processing running correctly through the job manager, I can easily switch things over to get these jobs running on the ME in parallel to the main core. That's the plan, anyway :)

-StrmnNrmn

Icons update (part 2)!

2007-11-11T13:31:00.000Z

..And the last update today (I promise!)

I just wanted to say that I've now received about 100 entries for the icon competition. I'm about halfway through the list so far; apologies if I've not responded to your entry yet.

I've had a lot more entries than I was expecting. Originally I was planning on posting all the entries so that people could comment on their favourites before I picked a winner. There are too many entries for me to be able to do that, so next weekend I'll pick my favourite 10 and show them instead.

I've had lots of entries from readers of PSP-Generation, so a big 'merci beaucoup' for that. It's certainly helping exercise my rusty French :)

There's just under a week left before the competition ends, so be sure to get your submission in shortly. Thanks for all the entries so far!

-StrmnNrmn

PS Remember it's 'daedalus' and not 'deadalus'. It's an easy mistake to make :)

Media Engine

2007-11-11T13:22:00.000Z

Earlier I discussed my plans for getting Daedalus's audio processing working on the PSP's Media Engine.

As I mentioned in that post, it's not just a case of changing some compiler setting to get this working. I've not spent much time investigating the ME so I may be wrong on a few of these points, but here are the current issues that I think need solving.

Firstly in order to access the ME I need to be running in kernel mode. This requires either running Daedalus in kernel mode, or (preferably) creating a kernel mode PRX that encapsulates the required functionality. I think kernel mode rules out anyone running with v1.50 firmware (hence my earlier post - please respond to the poll if you haven't already done so!) Maybe one of the more savvy psp developers out there can correct me on this? If no-one is using v1.50 any more then maybe it isn't even an issue.

Another problem is that although the ME is essentially the same processor as the main core, it has a different memory map. This means that things like the VRAM is invisible to the ME, so any code ported to run on the ME would have to be written to operate on main memory. This isn't an issue for Daedalus's audio list processing, but it would cause problems if I wanted to move display list processing to the ME too.

Touching on the memory map issue, another problem is the lack of cache coherency between the two cores. I need to be careful when accessing the same areas of memory with both cores to correctly flush and invalidate the data caches. Ideally any shared memory should be kept to a minimum, but this is easier said than done when porting existing code, rather than writing new code.

For a similar reason, any code which needs to run on the ME should avoid making any calls to the runtime library, including doing any system memory allocation. System calls are also ruled out. This is fairly easy to guarantee if you're writing new code, but again, it's a lot harder if you're porting existing code.

I think that's most of the issues from the hardware side. There are also a number of issues to be solved to do with the way that Daedalus handles audio and display list processing.

On the N64, the audio and display lists are processed asynchronously by the RSP coprocessor. In Daedalus, I can identify when these tasks are queued up for the RSP, intercept them, and process them synchronously (using high-level emulation rather than simulating the RSP execution directly).

The key thing here is that as far as the emulated N64 is concerned, audio and display list processing currently happens instantaneously. As soon as it kicks off the RSP it gets a interrupt to inform it that processing has completed. The whole process is very deterministic and I'm worried that by processing these display lists asynchronously on the ME that a number of intermittent and hard-to-debug issues will crop up. On the other hand, processing these tasks asynchronously is much closer to the behaviour of a real N64, which may fix some timing-related issues. It will also allow Daedalus to exploit the inherent parallelism that N64 roms were designed to take advantage of.

My current plan for ME audio support in R14 is:

Create a kernel mode PRX and get Daedalus successfully loading and invoking functions (under all supported firmwares). I've just about done this.
Add the code to support initialising and running code on the ME to the PRX. Test invoking user mode functions from the main EBOOT.PBP. I'll probably be using J.F.'s great sample code as a reference for this. Thanks J.F.!
Rewrite the audio list processing code so that it can be invoked synchronously or asynchronously as required (via some kind of configuration option). When running asynchronously it can just be run from a separate high-priority thread to start with. I can use this to test for various synchronisation issues without going through the pain of trying to do this on the ME first.
Audit the audio list processing code to minimise any memory accesses or ensure that they are correctly synchronised with the main core/thread. Any crt or system calls need to be eliminated or abstracted away (e.g. printfs NOP when compiled to run on the ME).
Invoke audio list processing code from the ME.
Cross fingers.

So, that's the plan; I'll keep you updated on my progress. If anyone has any experience doing this kind of thing on the ME it would be great to hear your thoughts.

-StrmnNrmn

R13 Issues, R14 Plans

2007-11-11T11:34:00.000Z

Over the past week I've started making plans for what I want to do for R14.

To start with, R13 introduced a couple of issues which I want to fix. Firstly, a number of roms now no longer work with dynarec enabled, or show odd behaviour. For instance, Aerogauge now finishes the race as soon as the countdown completes. I've tracked this down to one of the dynarec optimisations I added in August, where I optimise fragments which jump back to themselves. This should be a 'safe' transformation, so it suggests there's a bug somewhere in my implementation. If I can't fix the bug in time for R14, I'll add a temporary setting to allow this optimisation to be disabled on a rom-by-rom basis (much like the 'dynarec stack optimisation' setting).

Secondly, it looks like something I changed for savestate support has broken the 'return to main menu' option. I added some logic to help ensure that when taking a snapshot for the savestate, the CPU is paused in a 'safe' state (i.e. no dynarec code is executing, nothing is running on the RSP, and nothing is executing in the branch delay slot.) It looks like I've messed something up which is causing the 'return to main menu' option to wait for a safe state before bailing out to the menu. Should be an easy one to fix.

Morgan suggested a nice idea in the comments, which is that I generate a thumbnail for the savestate as it is created to display alongside the slot in the UI. It's a little tricky to implement, as by the time the emulator is told to create a savestate, it has already obliterated the n64's framebuffer with the Daedalus UI. I'll have to do something quite clever like speculatively copy the n64's framebuffer into system memory every time you enter the Pause Menu, or create the screenshot on the first frame rendered after saving. Either way, I'd like to add this simple feature to R14.

Next on my list for R14 is to look at making more significant performance improvements. Over the months many people have been asking when I'd get around to implementing audio on the PSP's Media Engine. I've talked about this before, but always kept putting it off in order to work on easier optimisations.

The Media Engine is a bit of unknown territory for me. Even though it's practically identical to the main CPU, you can't just change a setting an suddenly have your code running on it. There are a number of small hurdles I have to overcome before I can get audio working on the ME, but this is my big goal for R14 (I'll save the technical discussion for the next post.) If all goes to plan this should mean that audio can always be enabled without a significant impact on framerate.

So in summary for R14: a few bug fixes, thumbnails for savestates, and audio without affecting framerate.

-StrmnNrmn

Firmware poll

2007-11-11T10:59:00.000Z

I'm interested in which firmware everyone is running on. It would be very helpful if you could reply to this post with a) which model of PSP you're using ('fat'/slim, revision # if known) and b) which firmware you're using.

I have two PSPs. I have an original Japanese PSP with v1.00 firmware which I use for development, and a UK PSP which usually runs the latest official firmware (v3.72 at the moment.)

I'm interested because I want to know if anyone still requires the v1.50 (kxploit) versions of Daedalus that I release. I also need to figure out if it's worth my time getting a slim PSP for developing with the v3.xx+ firmware.

Thanks!
-StrmnNrmn

Icons update!

2007-11-07T09:16:00.000Z

Well it's only been a couple of days, but I've received over 50 submissions to date - It's going to take me some time to go through them!

A couple of people have asked about the icon size. 134x74 or 140x80 are both fine.

Thanks for all the entries so far - there have been some really great ones. Keep them coming!

-StrmnNrmn

Icons for Daedalus

2007-11-05T21:04:00.000Z

I've never taken the time to add icons to the Daedalus EBOOT.PBP. Mostly it's just because I've been lazy (when I develop Daedalus I usually run it through psplink rather than the XMB, so I rarely see the frontend), but also because I've never found a suitable set of icons to use.

There are plenty of icon/background packs floating around for Daedalus, but I've been reluctant to use any of them; I need something that I can freely distribute, but also something that doesn't infringe on any trademarks.

I'd like to add icons and a background to Daedalus for the next release, so I'm opening a 'competition' to try and find the best design. The 'prize' will be full credit in the release notes and on the Daedalus About screen (including a link to your website if you wish). Here's what I'm looking for:

Background 480x272, preferably in .png format
Icon 134*74, preferably in .png format
No use of Nintendo's trademarks! This means no use of the "N64" or "Nintendo" logos. Sorry. Be inventive!
You must own the work you submit, and give me permission to use it with Daedalus PSP

Email your submissions to me (strmnnrmn@gmail.com). I'll post all the submissions I receive by 16th November on this site to get people's thoughts, and make a decision the following Monday (19th November - that's two weeks today!)

Of course if you don't like whatever decision I make, you're always welcome to repack the Daedalus EBOOT.PBP and use any of the other graphics people send in :)

Time to get mspaint fired up!

-StrmnNrmn

Daedalus PSP R13 Released

2007-11-04T18:53:00.000Z

I've just finished packing up R13 and uploading it to sourceforge:

Daedalus PSP R13 for v1.00 Firmware
Daedalus PSP R13 for v1.50+ Firmware
Daedalus PSP R13 Source

The most significant new feature is savestate support. You can now save your progress at any point, via the Pause Menu (accessed through hitting the Select button). Savestates are written out to the memory stick, and consume around a megabyte per slot. You can load up a savestate at any time from the Pause Menu, or via the front end (hit the right shoulder button to swap from the rom list to the savestate list.)

Other than savestates, the most significant change in R13 is a number of optimisations to the dynarec core which should give a 10-20% speedup depending on the title being played. I've tested these optimisations as much as I can, but if you find that roms which worked with R12 are now broken, try disabling 'dynamic recompilation' and/or 'dynarec stack optimisation' from the rom's preferences screen.

I haven't looked at compatibility at all in R13, so it's unlikely that any roms will have started working in R13.

I'm interested to hear your feedback on both of these features. Let me know if you have any problems with savestates, or if you've found roms are no longer working in R13. I'll try and keep on top of the comments pages over the next couple of weeks.

It's taken a LOT longer to get R13 out than I had hoped. I can't quite believe the last release was in June! I'm hoping now I've got this release out of the door I'll be able to get back to making small, more frequent releases.

-StrmnNrmn

Update A couple of things have cropped up in the comments. Firstly, when you create a savestate it can take a while - up to 10 seconds - during which time the screen is black. It will complete though - please be patient :). I'll have a look at adding a progress meter or something like that for R14.

There are a few titles that don't seem to be working well with some of the dynarec optimisations I added. If you're having problems, try turning off the 'dynarec stack optimisation' as discussed above.

Daedalus R13 Soon

2007-11-03T17:49:00.000Z

I've just about finished implementing the last couple of savestate features I talked about last week.

I've got a bit of polishing to do and a little bit more testing, but I'm hoping I should be able to release R13 sometime tomorrow (Sunday).

I'll post again then with a complete list of changes and links to the latest builds for you to download. See you then!

-StrmnNrmn

R13 close, honestly!

2007-10-25T11:10:00.000+01:00

Apologies again for the lack of updates. I know people get nervous when I don't update regularly, but I don't like to post when I have nothing new or exciting to talk about.

I'm very close to releasing R13, I've just been struggling to find the time to add the final finishing touches to the savestate support. I've found it hard to get into a regular working pattern since moving, so what should have been a 1 week job has ended up taking a month. Bioshock and Halo 3 haven't helped either.

Savestates are working very well. The current implementation provides 10 slots which are shared across all roms. You can save to any slot at any time from an option on the Pause menu, or choose to reload a previous savestate. In this way it works just like QuickSave/QuickLoad found in various PC games (I'm tempted to add a special slot for this to the top level of the Pause menu).

I use zlib to compress the savestates, so an 8MiB savestate compresses down to 1MiB (or even smaller if you're running games which don't use the Expansion Pak).

There are just a couple of things I need to finish off now before I can release. Firstly I need to check if the savestate you're loading is for a different rom than is currently loaded. If this is the case I need to scan through your available roms looking for the correct one, and load it. To make this efficient I need to get the RomDB which I use for the PC build working on the PSP.

The second thing I need to do is come up with a decent way of linking some metadata to the savestate so I can show this in the UI. Just simple stuff like the full name of the rom, time the savestate was created and the total time spent playing when it was created. I figure without this information it'll be quite difficult to figure out what it stored in each savestate slot. The alternative is to add a text entry system to the UI so you can name each savestate, but I think this will just delay things even more.

In summary R13 is really close and I've not forgotten about it. Just a few more things to sort out and it'll be ready for release.

-StrmnNrmn

Daedalus and the PSP Slim + Lite

2007-10-01T20:36:00.000+01:00

A number of people have been asking if Daedalus will support the PSP Slim and Lite (PSP-2000), and if it does, if it will take advantage of the extra 32MiB RAM to improve the speed of emulated roms.

I am planning on supporting 3.xx firmware, but not until I have a PSP with suitable firmware which I can test with directly. People will probably end up compiling the Daedalus source for 3.xx (and they're welcome to), but until I can verify everything directly myself these will have to remain 'unofficial' builds. If there is strong demand for a 3.xx version of Daedalus then I'll consider setting up a donations page with the aim of buying a Slim and Lite for development.

As for the additional 32MiB RAM that the PSP-2000 provides, it's unlikely that this will provide for faster emulation. I've spent a lot of time reducing Daedalus's memory requirements so that it runs comfortably in the 32MiB that the PSP-1000 provides (it's actually a fair bit less than this when you take out OS overheads etc.)

There are only two main areas of the emulator that would benefit from an increase in cache size. The first is the texture cache, which is only used when video memory is exhausted. I fixed a few bugs with this months ago which means that very few roms ever have to place textures in system memory.

The second place that would benefit from a cache increase is the ROM cache. In order to support roms larger than the PSP's system memory, I dyamically map pages of the ROM into the PSP's RAM on demand (rather like virtual memory on PCs.) If a page of the ROM that is requested isn't in the cache, I have to pause emulation as I load it from memory stick. Currently this cache size is 2MiB. It could be increased up to 32MiB which would fit most N64 roms comfortably, and would entirely eliminate paging while the emulator is running. This might give a small speedup, but I don't believe this is currently a significant issue even with the tiny 2MiB cache that is currently in use.

Increasing the dynarec buffers would be very unlikely to provide a speedup, as I've yet to see a rom where they fill up before they are flushed for some other reason (typically instruction cache invalidation.)

So in summary, yes, I will support the PSP Slim and Lite at some point, but no, it's unlikely to offer much of an improvement over the PSP-1000s (other than being slimmer and lighter, obviously :)

-StrmnNrmn

Back Online

2007-09-19T22:02:00.000+01:00

Apologies for the lack of updates. I've not had internet access at home since moving flat at the end of August. My ADSL was activated today so I'm finally up and running again. I can't believe how long it's taken!

Between the flat move and a busy few weeks at work (getting ready for the Tokyo Game Show) I've not had that much time to work on Daedalus, but I have made some progress on a really cool feature people have been asking for for some time, namely savestate support.

For those not familiar with savestates, the basic premise is very much like 'hibernate' or sleep modes on PCs and laptops. A savestate can be created at any point during emulation. At a later time the savestate can be reloaded to restore the emulator to the exact state it was in when the savestate was created.

What's really useful about savestates is that they work even if the underlying save mechanism used by a rom isn't supported properly. I'm hoping that by adding savestate support Daedalus will become significantly more usable for many roms. Savestates also make development a lot easier as it means I can jump straight into the middle of a game when debugging/profiling rather than sitting through the title sequence dozens of times.

I still have a little bit of work left to do on the savestate system, mostly on the UI side, but there are a number of additional optimisations I want to finish off before I release R13. I'm currently planning to get everything ready for release on either the weekend of the 29th Sept, or possibly the first weekend in October.

-StrmnNrmn

Whoops

2007-08-15T23:13:00.000+01:00

It turns out that exophase had already suggested two of the three optimisations I implemented this weekend in a conversation we had way back in February.

Whoops! It's been such a long time, I'd totally forgotten we'd talked about it. I really should pay more attention sometimes - if I had been you might have seen some of these improvements way back in R9. Sorry exophase - kudos for spotting this so long ago!

-StrmnNrmn

Interesting Dynarec Hack

2007-08-15T23:03:00.000+01:00

I was playing around with the code generation a couple of evenings ago, and realised that if I made a certain assumption, I could drastically speed up specific types of memory accesses.

When I discussed load/store handling on Sunday, I presented the new code that is typically generated for handling a load such as 'lw $t0, 0x24($t1)' on the N64:


  ADDIU     a0 = s1 + 0x0024    # add offset to base register
  SLT       t0 = (a0  BEQ       t0 != r0 --> _Trampoline_XYZ123 # branch to trampoline if invalid
  ADDU      a1 = a0 + s7        # add offset to emulated ram
  LW        s0 <- 0x0000(a1)    # load data

(I'll ignore all the extra code which is generated, and just concentrate on the 5 instructions above which correspond to the expected path of execution.)

Of the 5 instructions that are generated, two - the SLT and BEQ - are just there for performing error handling in the case that the address is invalid, a hardware register (i.e. for memory-mapped I/O), or a virtual address. I'll call this error handling for short.

If we were generating code in an idealised environment where we didn't have to perform error handling, we could drop the SLT/BEQ instructions to get this:


  ADDIU     a0 = s1 + 0x0024    # add offset to base register
  ADDU      a1 = a0 + s7        # add offset to emulated ram
  LW        s0 <- 0x0000(a1)    # load data

We could then optimise this even further and perform the offset calculation directly as a part of the LW instruction:


  ADDU      a1 = s1 + s7        # add offset to emulated ram
  LW        s0 <- 0x0024(a1)    # load data

In this idealised situation we could reduce an emulated load to just two instructions, with no branches. That's a pretty good saving!

The problem is that the environment we're generating code from is not 'ideal', and it's hard to know in advance of time which memory accesses are going to directly access physical ram, and which are going to access hardware registers or require virtual address translation. For that reason, we have to place a guard around every memory access to make sure that it behaves correctly. At least, that was the way I was thinking until earlier in the week.

What I realised on Monday is that I can make an assumption that lets me remove the error handling code for certain types of load/stores. The assumption is that when the N64 accesses any memory through the stack pointer ($sp) register, the address is always going to be valid, physical memory.

The assumption relies on the fact that most roms don't do anything particularly clever with their stack pointers - it gets set up for each thread to point at a valid region of memory then the game just runs along, pushing and popping values from it as the code executes. Of course, if the assumption is wrong then the emulator will just crash and grind to a halt in a unpredictable manner :)

It was straightforward to add a hack to the code generation to exploit this kind of behaviour, and the results have been better than I expected - I'm seeing at least a 10% speed up, and the code expansion factor (the ratio of generated bytes of instructions to input bytes) has dropped from around 5.0x to 4.0x. Stability has been excellent too - I've run about 8 roms with the hack so far, and all of them have run perfectly.

I think one of the reasons the hack has such an impact is that a lot of the memory accesses in a typical C program are through the stack. Here's an example snippet from the entry to a function on the N64, where the compiler emitted code to store the return address and arguments:


SW        ra -> 0x0014(sp)
SW        a0 -> 0x0058(sp)
SW        a1 -> 0x005c(sp)
SW        a2 -> 0x0060(sp)

When I look through disassembly for the roms I'm working on, it's very common to see lots of sequential loads/stores relative to the stack pointer like this.

Previously Daedalus generated around 20 instructions (including 5 branches) for the above snippet. With the hack, the generated code now looks like this:


ADDU      t1 = s1 + s7
SW        s4 -> 0x0014(t1)
ADDU      t1 = s1 + s7
SW        s3 -> 0x0058(t1)
ADDU      t1 = s1 + s7
SW        s2 -> 0x005c(t1)
ADDU      t1 = s1 + s7
SW        s5 -> 0x0060(t1)

8 instructions, 0 branches. What's more, it looks like with a little work, I could eliminate 3 redundant address calculations:


ADDU      t1 = s1 + s7
SW        s4 -> 0x0014(t1)
SW        s3 -> 0x0058(t1)
SW        s2 -> 0x005c(t1)
SW        s5 -> 0x0060(t1)

Now that would be efficient :)

I still want to do lots of testing with the hack. I want to find out if there are roms that don't work with the hack enabled, and how common a problem it is. It's such a significant optimisation though that I'm certain I'll be adding it as an option in Daedalus R13. The results of my testing will probably determine whether I default it to on or off though.

So far Daedalus R13 is shaping up to be significantly faster than R12. I'm still not sure when I'll be ready to release it, but you'll hear about it here first.

-StrmnNrmn

Dynarec Improvements

2007-08-13T00:01:00.000+01:00

I've had a fairly productive week working on optimising the Dynarec Engine. It's been a few months since I worked on improving the code generation (as opposed to simply fixing bugs), so it's taken me a while to get back up to speed.

At the end of each fragment, I perform a little housekeeping to check whether it's necessary to exit from the dynarec system to handle various events. For instance, if a vertical blank is due this can result in me calling out to the graphics code to flip the current display buffers. The check simply involves updating the N64's COUNT register, and checking to see whether there are any time-dependent interrupts to process (namely vertical blank or COMPARE interrupts.)

I had an idea on the train into work on Monday I realised that there were a couple of ways in which I could make this more efficient. Firstly, the mechanism I was using to keep track of pending events was relatively complex, involving maintaining doublely-linked lists of events. I realised that if I simplified this code it would make it much easier for the dynarec engine to update and check this structure directly rather than calling out to C code.

The other idea I had on the train was to split up the function I was calling to do this testing into two different versions. There are two ways that the dynarec engine can be exited - either through a normal instruction, or a branch delay instruction (i.e. an instruction immediately following a branch.) My handler function catered for both of these cases by taking a flag as an argument. I realised that by providing a separate version of this function for each type I could remove the need to pass this flag as an argument, which saved a couple of instructions from the epilogue of each fragment.

These two small changes only took a couple of hours to implement, but yielded a 3-5% speedup on the various roms I tested. They also slightly reduced the amount of memory needed for the dynarec system, improving cache usage along the way.

The next significant optimisation I made this week was to improve the way I was handling the code generation for load/stores. Here's what the generated code for 'lw $t0, 0x24($t1)' looks like in Daedalus R12 (assume t1 is cached in s1, and t0 is cached in s0 on the PSP):


  ADDIU     a0 = s1 + 0x0024     # add offset to base register
  SLT       t0 = (a0<s6)      # compare to upper limit
  ADDU      a1 = a0 + s7         # add offset to emulated ram
  BNEL      t0 != r0 --> cont # valid address?
  LW        s0 <- 0x0000(a1)  # load data
  J         _HandleLoadStore_XYZ123 # handle vmem, illegal access etc
  NOP
cont:
  # s0 now holds the loaded value,
  # or we've exited from dynarec with an exception

There are a couple of things to note here. Firstly, I use s6 and s7 on the PSP to hold two constants throughout execution. s6 is either 0x80400000 or 0x80800000 depending on whether the N64 being emulated has the Expansion Pak installed. s7 is set to be (emulated_ram_base - 0x80000000). Keeping these values in registers prevents me from using them for caching N64 registers, but the cost is far outweighed by the more streamlined code. As it happens, I also use s8 to hold the base pointer for most of the N64 CPU state (registers, pc, branch delay flag etc) for the same reason.

So the code first adds on the required offset. It then checks that the resulting address is in the range 0x80000000..0x80400000, and sets t0 to 1 if this is the case, or clears it otherwise*. It then adds on the offset (emulated_ram_base - 0x80000000) which gives it the translated address on the psp in a1. The use of BNEL 'Branch Not Equal Likely' is carefully chosen - the 'Likely' bit means that the following instruction is only executed if the branch is taken. If I had used a plain 'BNE', the emulator could often crash dereferencing memory with the following LW 'Load Word'.

Assuming the address is out of range, the branch and load are skipped, and control is passed to a specially constructed handler function. I've called it _HandleLoadStore_XYZ123 for the benefit of discussion, but the name isn't actually generated, it's just meant to indicate that it's unique for this memory access. The handler function is too complex to describe here, but it's sufficient to say that it returns control to the label 'cont' if the memory access was performed ok (e.g. it might have been a virtual address), else it bails out of the dynarec engine and triggers an exception.

When I originally wrote the above code I didn't think it was possible to improve it any further. I didn't like the J/NOP pair, but I saw them as a necessary evil. All 'off trace' code is generated in a second dynarec buffer which is about 3MiB from the primary buffer - too far for a branch which has a maximum range of +/-128KiB. I used the BNEL to skip past the Jump 'J' instruction which can transfer control anywhere in memory.

What I realised over the weekend was that I could place a 'trampoline' with a jump to the handler function immediately following the code for the fragment. Fragments tend to be relatively short - short enough to be within the range of a branch instruction. With this in mind, I rewrote the code generation for load and store instructions to remove the J/NOP pair from the main flow of the trace:


  ADDIU     a0 = s1 + 0x0024    # add offset to base register
  SLT       t0 = (a0<s6)     # compare to upper limit
  BEQ       t0 != r0 --> _Trampoline_XYZ123 # branch to trampoline if invalid
  ADDU      a1 = a0 + s7        # add offset to emulated ram
  LW        s0 <- 0x0000(a1) # load data
cont:
  # s0 now holds the loaded value,
  # or we've exited from dynarec with an exception
  #
  # rest of fragment code follows
  # ...
  
  
_Trampoline_XYZ123:
  # handler returns control to 'cont'
  J     _HandleLoadStore_XYZ123  
  NOP

The end result is that this removes two instructions from the main path through the fragment. Although in the common case five instructions are executed in both snippets of code, the second example is much more instruction cache friendly as the 'cold' J/NOP instructions are moved to the end of the fragment. I've heard that there is a performance penalty for branch-likely instructions on modern MIPS implementations, so it's nice to get rid of the BNEL too.

As with the first optimisation, this change yielded a further 3-5% speedup.

The final optimisation I've made this weekend is to improve the way I deal with fragments that loop back to themselves as they exit. Here's a simple example:


8018e014 LB        t8 <- 0x0000(a1)
8018e018 LB        t9 <- 0x0000(a0)
8018e01c ADDIU     a0 = a0 + 0x0001
8018e020 XOR       a2 = t8 ^ t9
8018e024 SLTU      a2 = (r0<a2)
8018e028 BEQ       a2 == r0 --> 0x8018e038
8018e02c ADDIU     a1 = a1 + 0x0001
8018e038 LB        t0 <- 0x0000(a0)
8018e03c NOP
8018e040 BEQ       t0 == r0 --> 0x8018e058
8018e044 NOP
8018e048 LB        t1 <- 0x0000(a1)
8018e04c NOP
8018e050 BNE       t1 != r0 --> 0x8018e014
8018e054 NOP

I'm not sure exactly what this code is doing - it looks like a loop implementing something like strcmp() - but it's one of the most executed fragments of code in the front end of Mario 64.

The key thing to notice about this fragment is that the last branch target loops back to the first instruction. In R12, I don't perform any specific optimisation for this scenario, so I flush any dirty registers that have been cached as I exit, and immediately reload them when I re-enter the fragment. Simplified pseudo-assembly for R12 looks something like this:


enter_8018e014:
  load n64 registers into cached regs
  
  perform various calculations on cached regs
  
  if some-condition
      flush dirty cached regs back to n64 regs
      goto enter_8018e038
  
  perform various calculations on cached regs
  
  flush dirty cached regs back to n64 regs
  
  if ok-to-continue
      goto enter_8018e014
exit_8018e014:
  ...
  
enter_8018e038:
 ...

The key thing to notice is that we load and flush the cached registers on every iteration through the loop. Ideally we'd just load them once, loop as much as possible, and then flush them back to memory before exiting. I've spent the day re-working the way the dynamic recompiler handles situations such as this. This is what the current code looks like:


enter_8018e014:
  load n64 registers into cached regs
  mark modified regs as dirty

loop: 
  perform various calculations on cached regs
  
  if some-condition
      flush dirty cached regs back to n64 regs
      goto enter_8018e038
  
  perform various calculations on cached regs
   
  if ok-to-continue
      goto loop

  flush dirty cached regs back to n64 regs
exit_8018e014:
  ...
  
enter_8018e038:
 ...

In this version, the registers are loaded and stored outside of the inner loop. They may still be flushed during the loop, but only if we branch to another trace. Before we enter the inner loop, we need to mark all the cached registers as being dirty, so that they're correctly flushed whenever we finally exit the loop.

This new method is much more efficient when it comes to handling tight-inner loops such as the assembly shown above. I still have some work to do in improving my register allocation, but the changes I've made today yield a 5-6% speedup. Combined with the other two optimisations I've described, I'm currently seeing an overall 10-15% speedup over R12.

I'm quite excited about the progress I've made so far with R13. I still have lots of ideas for other optimisations I want to implement for R13 which I'll talk about over the coming days. I don't have any release date in mind for R13 at the moment, so there's no point in asking me yet :)

-StrmnNrmn

*The SLT instruction is essentially doing 'bool inrange = address >= 0x80000000 && address < (0x80000000+ramsize)'. I think the fact that this can be expressed in a single instruction is both beautiful and extremely fortunate :)

Daedalus PSP under OSX

2007-08-02T23:58:00.000+01:00

I mentioned a few days ago that I've recently bought a Macbook Pro. I've never owned a Mac before so it's been a really interesting experience learning my way around. Initially I was planing on dual booting Windows XP via Boot Camp, but I quickly found that I could do almost everything I need to in OSX. I did install Parallels Desktop, I rarely find myself running any Windows apps.

One of the main things I need for day to day 'work' is the ability to compile and run Daedalus. The rest of this article describes the process of setting up the PSPSDK under OSX, and compiling Daedalus PSP for the first time. This post is really aimed at people who are interested in compiling Daedalus for themselves on OSX. Hopefully it will also be useful for other PSP homebrew developers who have been having problems getting the PSPSDK set up under OSX.

To install the PSPSDK I largely followed this guide on the ps2dev.org forums. I already had XCode and fink installed. Fink complained when I tried to install all the listed packages, and I had to remove one of them from the command line (I think it was autogen, but I can't really remember now.)

I've been using the most recent psptoolchain script, which was updated a few weeks ago, and I had to make a couple of modifications. In depends/check-ncurses.sh I had to change the check for ncurses to look for the OSX .dyliib file:


## Check for a ncurses library.
ls /usr/lib/libncurses.a 1> /dev/null ||
    ls /usr/lib/libncurses.dll.a ||
    { echo "ERROR: Install ncurses before continuing."; exit 1; }

became:


## Check for a ncurses library.
ls /usr/lib/libncurses.a 1> /dev/null ||
    ls /usr/lib/libncurses.dll.a ||
    ls /usr/lib/libncurses.dylib ||
    { echo "ERROR: Install ncurses before continuing."; exit 1; }

Secondly I had to make this change to scripts/001-binutils-2.16.1.sh. As urchin mentions on the ps2dev.org forum, ".m" is the extension for Objective C files in OSX. The '-r' tells make to ignore the built-in implicit rules, and everything works fine:

So:


## Compile and install.
make clean && make -j 2 && make install && make clean || { exit 1; }

became:


## Compile and install.
make clean && make -r -j 2 && make install && make clean || { exit 1; }

(note the '-r' flag on the second invocation of make.)

I left the psptoolchain script doing its stuff for a couple of hours, and when I came back to it everything seemed to have completed and installed correctly.

The next step was to get Daedalus PSP compiling. Somewhat naively I assumed Daedalus PSP would compile out of the box on OSX. As it turns out, I had to make a few small changes to get everything compiling nicely.

Firstly, I had to update the makefile so that it directly referenced psp-gcc and psp-g++. Normally, I build Daedalus PSP through a Visual Studio Makefile project, and I had used a couple of scripts from the ps2dev.org forums to format GCC's output into a format that Visual Studio understands, so that double clicking on an error in the output opens the corresponding file in the editor. I found a better way to handle this, so I changed the CC/CXX macros to refer to the original pspsdk tools.

The main problem I encountered was my arbitrary use of backslashes instead of forward slashes in #include directives, e.g.:


#include "Core\CPU.h"

should be:


#include "Core/CPU.h"

Another subtle error came from the way that I was instantiating static functions from templated classes which are defined in a namespace. An example will probably help explain. Here's the basic outline of the class I use to implement the singleton pattern:


namespace daedalus
{
 template< class T>
 class CSingleton
 {
 public:
  static bool Create();

  static T * Get() { return mpInstance; }

 private:
  T * mpInstance;
 };
}

The Create method for the singleton class is then implemented like this:


template<> bool CSingleton< CController >::Create()
{
 DAEDALUS_ASSERT_Q(mpInstance == NULL);
 
 mpInstance = new IController();

 return true;
}

For some reason this started failing when compiling Daedalus PSP under OSX:


Source/Core/PIF.cpp: At global scope:
Source/Core/PIF.cpp:250: error: specialization of 'static bool
 daedalus::CSingleton::Create() [with T = CController]' in different namespace
Source/Core/PIF.cpp:250: error:   from definition of 'static bool
 daedalus::CSingleton::Create() [with T = CController]'

Rather than being an OSX issue, I suspect that the reason this error started occurring was actually due to the PSPSDK using an updated version of GCC which is a bit stricter than the version I was using on Windows. Regardless, the fix was easy - the code just needed to be wrapped in the 'daedalus' namespace:


namespace daedalus
{
template<> bool CSingleton< CController >::Create()
{
 DAEDALUS_ASSERT_Q(mpInstance == NULL);
 
 mpInstance = new IController();

 return true;
}
}

(I've recently been going off the singleton pattern, but that's another story :)

With these changes Daedalus PSP compiles perfectly under OSX. On my 2.4 GHz Macbook Pro it takes just under 50 seconds. On my 2.4GHz Windows machine it takes over 2 minutes to compile, so I'm very impressed with the results.

I believe I've checked in all the required changes to the Daedalus SVN repository on SourceForge. If you decide to try compiling Daedalus PSP under OSX, let me know how you get on via the comments page (I'll be rejecting any off-topic comments to try and keep the discussion constructive)

-StrmnNrmn

333 MHz

2007-08-01T00:15:00.000+01:00

On startup Daedalus increases the default clock frequency of the PSP's cpu from 222MHz to 333MHz for a 'free' 50% speedup. I use 'free' in quotes because this comes at the expense of drawing more power so the battery runs out of charge faster.

I've been asked if I'm going to support 333MHz many times, so I wanted to put this question to rest for once and for all. The answer is yes - I believe this has been the case since R1 :)

-StrmnNrmn

Custom Controller Configurations

2007-07-30T23:45:00.000+01:00

A number of people have asked if I would be adding support for user-defined controller configurations in a future release of Daedalus. As it happens Daedalus has supported user-defined controller configurations from R7 onwards. From the readme file:

As of R7 Daedalus now allows user-configurable controls to be specified.
The desired controls can be chosen from the Rom Settings screen.

In order to define your own controller configuration you need to add a
new .ini file to the Daedalus/ControllerConfigs directory. There are a
few examples provided which should give an overview of what is possible.
I will look at providing a more thorough tutorial shortly.

The format really is quite simple, but it is very flexible and allows for a number of advanced configurations. Here is a simple configuration which is distributed with Daedalus (ControllerConfigs/dpad.ini):

Name=DPad
Description=By default the PSP DPad maps to the N64 DPad. Hold Circle to map to the CButtons.

[Buttons]
N64.Start = PSP.Start
N64.A = PSP.Cross
N64.B = PSP.Square
N64.Z = PSP.Triangle
N64.LTrigger = PSP.LTrigger
N64.RTrigger = PSP.RTrigger
N64.Up = !PSP.Circle & PSP.Up
N64.Down = !PSP.Circle & PSP.Down
N64.Left = !PSP.Circle & PSP.Left
N64.Right = !PSP.Circle & PSP.Right
N64.CUp = PSP.Circle & PSP.Up
N64.CDown = PSP.Circle & PSP.Down
N64.CLeft = PSP.Circle & PSP.Left
N64.CRight = PSP.Circle & PSP.Right

The file starts with two lines defining the name and description for the controller config. These strings are used in the UI when selecting configurations. The '[Buttons]' block defines the mapping from PSP controls to N64 controls. In this particular configuration the N64 d-pad is mapped to the PSP d-pad when the circle button is released. When circle is pressed, the PSP d-pad maps to the N64 c-buttons. This config is particularly useful for games which make heavy use of the d-pad.

In the [Buttons] section, the left hand side of each rule must consist of one of the following N64 control names:

Name	Description
N64.Start	The N64's start button
N64.A	The N64's A button
N64.B	The N64's B button
N64.Z	The N64's Z trigger
N64.LTrigger	The left trigger
N64.RTrigger	The right trigger
N64.Up	Up on the N64's d-pad
N64.Down	Down on the N64's d-pad
N64.Left	Left on the N64's d-pad
N64.Right	Right on the N64's d-pad
N64.CUp	The N64's C up button
N64.CDown	The N64's C down button
N64.CLeft	The N64's C left button
N64.CRight	The N64's C right button

N.B. There is currently no definition for the N64's analogue stick. By default this is always assumed to be bound to the PSP's analogue stick.

The right hand side of a rule consists of an expression defined from the following values:

Name	Description
PSP.Start	The PSP's start button
PSP.Cross	The PSP's cross button
PSP.Square	The PSP's square button
PSP.Triangle	The PSP's triangle button
PSP.Circle	The PSP's circle button
PSP.LTrigger	The PSP's left shoulder button
PSP.RTrigger	The PSP's right shoulder button
PSP.Up	Up on the PSP's d-pad
PSP.Down	Down on the PSP's d-pad
PSP.Left	Left on the PSP's d-pad
PSP.Right	Right on the PSP's d-pad

N.B. You cannot use the PSP's select button when defining controller configurations, as this is reserved for the emulator's use.

Values can be combined using a few simple operations to allow rules to be constructed with more complex behaviour. For instance, the following line:

N64.CUp = PSP.Circle & PSP.Up

Tells Daedalus to report that the N64 C up button is pressed when both the circle AND d-pad up buttons are pressed on the PSP. The NOT operator (!) can be used to invert a value, for instance:

N64.Up = !PSP.Circle & PSP.Up

This rule tells Daedalus to report that the N64 d-pad up button is pressed when the PSP's circle button is not pressed while the d-pad up button is being pressed.

The available logical operators are:

Operator	Description	Example
expr & expr	Returns the logical AND of the two expressions	N64.CUp=PSP.LTrigger & PSP.Up
expr \| expr	Returns the logical OR of the two expressions	N64.A=PSP.Cross \| PSP.Circle
!expr	Returns the logical NOT of the expression	N64.Up = !PSP.LTrigger & PSP.Up

You can also use parentheses to control the order of precedence, e.g.:

N64.CUp = PSP.Up | (PSP.LTrigger & PSP.Triangle)

Which defines a rule which defines that the N64 C up button is pressed when either up on the PSP d-pad is pressed, or when the left shoulder button and triangle are pressed.

No single controller mapping scheme can be provided which works well across all games, but using custom controller configs it should be possible to create a mapping which works well for any given game.

Post any questions you might have in the comment pages, and I'll do my best to answer them. If you come up with a good controller config for a game, email me (my name @gmail.com) and I'll look at adding it for distribution with future releases of Daedalus.

-StrmnNrmn

(Apologies - for some reason my template in Blogger really screws up when I place tables in he post and inserts a ton of whitespace before the table. I've never quite figured out how to fix it, so we'll just have to live with it :)

(Fixed post date :)

Recharged

2007-07-29T22:07:00.000+01:00

It's been quite a while since my last update. I was starting to feel a little worn out from all the work I'd been putting into the emulator over the past few months so since releasing R12 I've been taking a bit of a break from Daedalus to unwind and recharge my batteries.

It's been really nice just taking a bit of a break to do a few different things with my spare time. I spent a short while in Spain with my sister, and since I've been back I've been catching up with a bit of reading, watched a load of TV that I'd queued up and played through a few games I'd had gathering dust for a while. Sadly my 360 succumbed to the Red Ring of Death last week so it seems I might have been pushing it a bit too hard :)

I found a new flat in Guildford which I'll be moving to at the end of August. I'm quite excited about the move as I'll save a lot of time commuting. It currently takes me little over an hour to travel into work and it'll just be 15 minutes once I move. I'm hoping that cutting back on the commute should not only free up a couple of hours each day, but I'll also be a bit less knackered once I finish for the day.

I also picked up a Macbook Pro during my 'time off' and I've really been enjoying my new-found sense of computing freedom (I've been writing this post on the train on the way home from work.) It's the 17" 'lapzilla' model, and it's an absolute beast. It actually compiles Daedalus faster than my year old desktop PC which I find pretty impressive. I'll have some details and tutorials about compiling Daedalus PSP under OSX in the near future.

Now that I've had a bit of time off, I'm feeling very excited about getting cracking with R13. My main feeling is that I'd like to continue working on speeding up the emulator to try and improve the framerate for titles that are already working. From your comments on this blog and on other sites such as the DCEmu forums (the site seems to be down right now - I'll update with a link later) it seems that this is mostly what people are interested in seeing for the next release.

There are a number of different areas I can investigate to help improve performance. The two main possibilities I want to investigate are working on further dynarec improvements, and looking at making use the Media Engine. To start with I'm going to explore both of these areas and try and figure out which would give the biggest 'bang for buck' for R13. I'll post and update on R13 when I have more details.

-StrmnNrmn

PS Thanks for all your comments while I've been away. I have about 100 left to approve which I'll start to go through now.

Daedalus disinformation

2007-07-04T08:24:00.000+01:00

I was quite interested to read this article over at pspupdates.qj.net:

StrmnNrmn sent us an email recently that really got us thinking about how far Daedalus has come from its humble beginnings more than a year ago. Not only does he give us some prime information about the direction of Daedalus, but he also mentions just how long it might take him to actually get everything running properly.

I never emailed pspupdates.qj.net, so it looks like someone has been deliberately trying to mislead them. It goes on to say:

R13 might actually use Bios files now

I have no idea what this actually means! The information doesn't seem to be particularly malicious, but I didn't write it. Anything I have to say about Daedalus, I'll talk about here, on this blog. It'll be another week or so before I can update regularly, so any other 'information' you hear that's not directly from this blog is likely to be a hoax.

-StrmnNrmn

I can't seem to find any way of contacting the author of the story at QJ.net (Victor B), but if they read this I'd appreciate an update to the story linking to this response. Thanks!

Update pspupdates.qj.net have posted an update to the story. I just wanted to express my thanks for clarifying the situation so quickly. Thanks Victor!

Daedalus PSP R12 Released

2007-06-27T00:25:00.001+01:00

I've just finished uploading the latest build of Daedalus PSP:

Daedalus PSP R12 for v1.00 Firmware
Daedalus PSP R12 for v1.50+ Firmware
Daedalus PSP R12 Source

As usual it will take 20-30 minutes for the files to propagate across the Sourceforge mirrors, so please be patient :)

Here is the list of changes:

[!] Fixed issue preventing Goldeneye from being loaded.
[!] Fixed dynarec for Goldeneye.
[!] Fixed dynarec for Super Smash Bros.
[!] Fix various texturing issues with 4bpp and small or non power-of-2 textures.
[!] Fix TexRect instructions with negative s/t components.
[!] Fixed the HUD in Mario 64 (broken in R11.)
[!] Fixed lights in F3DEX2 microcodes.
[+] Correctly implement instruction fetch exceptions, improving compatibility.
[+] Improved floating point compatibility.
[+] Correctly handle mask_s/mask_t tile values.
[+] Implemented a few custom blend modes.
[+] Screenshots just cover visible viewport.

If you've been following the updates on this blog over the past month the most obvious change is that Super Smash Bros. is now running well with dynarec enabled, and many graphical glitches have now been resolved. The compatibility fixes were specifically aimed at Super Smash Bros. but may well fix issues with other roms too. Overall SSB is looking and playing much better than it was in R11, but even at 30-40fps it's still not running at fullspeed yet. There are a few graphical issues that still need resolving, but all in all it's starting to feel very playable with frameskip set to 1 or 2.

Goldeneye is also running in R12. Although the intro sequence is running very quickly and with few noticable graphical issues, a lot more work is needed to it running at a playable framerate in-game. I think it's a good start though, and something to get excited about for the future :)

Otherwise R12 just has a fewm minor compatibility and graphical fixes - there are no optimisations for this build.

As always, leave your feedback on the comments pages. I read all your comments and I'll do my best to reply to any questions you raise. I'm particularly interested to hear if any roms which were broken in previous releases are now running in R12.

Enjoy!

-StrmnNrmn

Multiplayer Thoughts

2007-06-16T11:22:00.000+01:00

In response to a recent post, Zeus asked an interesting question:

I know you've probably been bugged by people on this before, but how hard would multi-player be to implement? More importantly, do you think that there is enough bandwidth, and low enough lag, to allow a host-client multiplayer setup to be playable? (ie, with one psp "hosting" the game and doing the emulation, while the other(s) just receive screen-captures and send back user-input) Or do you think that distributing the computational workload would be a better approach? (at the very minimum, the audio processor shouldn't be too horrible to move to the client psp(s) )

I have thought about multiplayer a great deal, but I've never made any plans to work on it - there didn't seem to be much point getting multiplayer working before there were a few multiplayer games running quickly and glitch free. Now that MarioKart and Super Smash Bros. are both working reasonably well, there's obviously going to be a lot more demand for multiplayer support. Before I raise expectations and get anyone's hopes up, I should mention that this isn't likely to happen any time soon.

It would be possible to go down the route of having a host psp which performs emulation and broadcasts the screen to client psps. Sony's Remote Play between the PS3 and PSP shows that this kind of 'dumb terminal' approach can work in the right situations. That's with the PS3 doing the grunt work of compressing the framebuffer and sending it over to the PSP. For for a PSP running Daedalus as a host, I'm not quite sure there would be enough spare horsepower to compress the framebuffer and audio and then send it to 1 or more connected clients.

Also, I don't think that it would be possible to decouple the audio processing from the main cpu thread so that this work could be distributed to one of the clients. Although the audio and graphics processing is notionally run in parallel on the RSP (the N64's coprocessor), access is still serialised between audio and graphics tasks so they have to be completed in order. Performing audio processing on a client PSP would just mean that graphics processing on the host would have to wait until the results of the audio processing were received.

The approach that I'd been considering was running Daedalus in lockstep across 2 or more connected PSPs. As I mentioned previously Daedalus can run deterministically if external inputs such as pad input and timing sources are synchronised. What this would mean would be that every time the rom queried the pad status, each connected psp would have to synchronise its view of the pad input with the host. This would mean sending just 64 bytes across the network from the client to the host and back. This information would have to be sent over a TCP connection rather than UDP as we have to ensure that every PSP sees the exact same input (actually, client->host communication is a bit less critical so it may be possible to transmit this information over UDP if it helps improve lag.)

One really cool feature about this approach is that as each PSP would be responsible for rendering its own display, it would be possible to scale up each viewport to fill the display; rather than playing 4-player Mario Kart or Goldeneye at 160x120, you'd be able to play at 320x240 (or 480x272 if you wanted to scale it up to entirely fill the PSP's screen).

As I said at the start of the post, this isn't something that's likely to happen any time soon, but if and when it does happen, it will be amazing :)

-StrmnNrmn

R12 Release Date

2007-06-16T11:12:00.000+01:00

A number of people have been asking in the comments when R12 is going to be released.

There are still a number of things I want to work on. Now that Super Smash Bros. is running nice and quickly with dynarec enabled, I want to spend a week or so polishing the graphics and trying to make it as playable as possible. Although Goldeneye is running with dynarec in R12, it still needs a lot of work before its playable, so I'm not going to spend any more time on it for R12.

I'm going on holiday at the end of June, so I'd like to have R12 released before then. I'll aim for next weekend (23rd/24th June) but it may end up being as late as the 26th/27th.

-StrmnNrmn

Tracking down the SSB Dynarec Bug - Part 2

2007-06-14T00:30:00.000+01:00

On Monday I talked about the fragment simulator and how this could be used to help track down bugs in the dynarec implementation. In this post I'm going to talk a bit about a tool I use mostly for regression testing, but also to help determine the exact point at which the fragment simulator and the interpretative core go out of sync. It's a bit of a long post, so apologies in advance :)

Daedalus can be compiled with a flag which enables a special 'synchronisation' mode. This build configuration creates an instance of a synchronisation class which can be initialised in one of two modes - either as a producer or as a consumer. At various points during program execution I pass information about the internal state of the emulator to the synchroniser for processing. In the case of the producer, it simply writes this data out to a file on disk. The consumer is a bit more interesting; it reads data of the required size from disk, and compares this 'baseline' value against the value provided by the emulator. If these two values are found to be different, the synchroniser knows that things have drifted out of sync and it can trigger a breakpoint and drop out into the debugger.

This technique relies on the fact that the emulator is deterministic, i.e. running the emulator twice in a row with the same inputs generates exactly the same results. By 'inputs' this means not just the same rom image, but external inputs such as data from the controller must match exactly too. Obviously pressing buttons on the controller in exactly the same order with the same timings would be impossible to duplicate, so the other function the synchroniser performs is to record input from the pad in the case of the producer, or play input back in the case of the consumer. Other external input, such as calls to timer functions (e.g. time(), QueryPerformanceCounter() or rdtsc) can be synchronised in the same way.

The synchroniser works with as few or as many sync points as you provide. For debugging very simple problems, you can get away with just checking the value of the program counter as each instruction is executed. For more tricky problems you can end up adding many more sync points - for instance you can synchronise the entire register set after every instruction to ensure that the synchroniser catches any instruction which generates a different result from the baseline.

I add sync points to Daedalus using a set of macros. When synchronisation is enabled, the macros expand out to calls to a virtual method on a global instance of the synchroniser class. An example sync point in the code might look like this:


u32 pc = gCPUState.CurrentPC;

SYNCH_POINT( DAED_SYNC_REG_PC, pc );

OpCode op;
if( CPU_FetchInstruction( pc, &op ) )
{
    CPU_Execute( pc, op );
}

The interesting line here is the SYNC_POINT macro, which synchronises on the current program counter value. For producers, this just writes the value of 'pc' to disk. For consumers, it checks that the value we have for 'pc' matches the one read from disk.

The DAED_SYNC_REG_PC argument is simply a flag to describe what is being synchronised. Another global constant allows easy control of what is synchronised:


enum ESynchFlags
{
 DAED_SYNC_NONE  = 0x00000000,

 DAED_SYNC_REG_GPR = 0x00000001,
 DAED_SYNC_REG_CPU0 = 0x00000002,
 DAED_SYNC_REG_CCR0 = 0x00000004,
 DAED_SYNC_REG_CPU1 = 0x00000008,
 DAED_SYNC_REG_CCR1 = 0x00000010,

 DAED_SYNC_REG_PC = 0x00000020,
 DAED_SYNC_FRAGMENT_PC = 0x00000040,
};

static const u32 DAED_SYNC_MASK(DAED_SYNC_REG_PC);

#define  SYNCH_POINT( flags, x, msg ) \
 if ( DAED_SYNC_MASK & (flags) )  \
  CSynchroniser::SynchPoint( x, msg )

If I want to enable more thorough debugging, I can change DAED_SYNC_MASK and OR in more values:


static const u32 DAED_SYNC_MASK(DAED_SYNC_REG_PC|DAED_SYNC_REG_GPR);

Changing the mask value requires the emulator to be rebuilt from scratch and the baseline synch file to be recreated. This is a bit time consuming but doing it in this way means that the compiler can optimise out any synch points which we aren't interested in, keeping things running as quickly as possible.

One problem with this technique is that the synchroniser can quickly generate a massive amount of data, so much that most of the execution time is spent shifting this data to or from disk, slowing debugging to a crawl. In the example I gave on Monday, it can sometimes take over 500 million instructions before things go out of sync. Even when just synchronising on the program counter, that's over 2GiB of data that needs to be read/written to disk. When you throw in more sync points such as register sets (the GPR registers on their own are around 256 bytes) this can very quickly become impractical. To get around these limitations in Daedalus I gzip the stream of data on the fly which compresses the data significantly. Another trick I use is to hash each register set to a 32bit value and synchronise on this value instead. When using both these techniques the sync files typically end up around 100-200MiB, which is much more manageable.

One of the main uses of this synchronisation code is for regression testing optimisations I've made. I can take a 'known good' build of the emulator and initialise the synchronisation class as a producer to generate a baseline sync file. I can then take a modified version of Daedalus with the optimisations that I want to test, and initialise the synchroniser as a consumer. If the synchroniser detects that things have gone out of sync, then I know that my changes are buggy, and I can investigate why they're not working as planned. It's worth noting that even if everything stays in sync, this isn't a guarantee that my changes are bug-free, but it's a pretty good indication that they're ok.

I also use the synchronisation code to debug tricky dynarec issues. When debugging these types of problems I typically start off by disabling the dynarec engine and setting up the synchroniser to produce a baseline for testing. I'll then re-enable dynarec, but using the fragment simulator with precise interrupt handling (see the end of Monday's post for more on this) and run Daedalus with the synchroniser in consumer mode. Theoretically, as soon as the dynarec code gets out of sync with the interpretative core, the breakpoint triggers and I can investigate things more closely in the debugger.

This is exactly the process I used to track down the Super Smash Bros. bug. When I ran the emulator with the synchroniser in consumer mode, it detected that the program counter was different from the expected baseline value after exactly 387,939,387 instructions had been executed. I'd like to think that an error rate of 2.57e-7% wasn't all that bad, but apparently it is :)

Now that I knew the point at which the emulator was going out of synch, I set a few breakpoints in the emulator to see what exactly was happening. My usual trick is to disassemble the executed instructions just before and after things diverge, and see what's different. Here are snippets from the 'good' and 'bad' logs as things go out of sync:


Count 171f7c35: PC: 80132500: LW        ra <- 0x0014(sp)
Count 171f7c36: PC: 80132504: ADDIU     sp = sp + 0x0018
Count 171f7c37: PC: 80132508: JR        ra
Count 171f7c38: PC: 8013250c: NOP
Count 171f7c39: PC: 80132ae8: JAL       0x80131fb0        ?
Count 171f7c3a: PC: 80132aec: NOP
Count 171f7c3b: PC: 80131fb0: ADDIU     sp = sp + 0xffd8
Count 171f7c3c: PC: 80131fb4: SW        ra -> 0x0024(sp)
Count 171f7c3d: PC: 80131fb8: SW        s0 -> 0x0020(sp)
Count 171f7c3e: PC: 80131fbc: CLEAR     a0 = 0
Count 171f7c3f: PC: 80131fc0: CLEAR     a1 = 0


Count 171f7c35: PC: 80132500: LW        ra <- 0x0014(sp)
Count 171f7c36: PC: 80132504: ADDIU     sp = sp + 0x0018
Count 171f7c37: PC: 80132508: JR        ra
Count 171f7c38: PC: 8013250c: NOP
Count 171f7c39: PC: 80132ae8: MTC1      at -> FP06
Count 171f7c3a: PC: 80132aec: NOP
Count 171f7c3b: PC: 80132af0: SWC1      FP06 -> 0x0018(a0)
Count 171f7c3c: PC: 80132af4: LBU       v0 <- 0x4ad1(v0)
Count 171f7c3d: PC: 80132af8: ADDIU     at = r0 + 0x0008
Count 171f7c3e: PC: 80132afc: BEQ       v0 == at --> 0x80132b24
Count 171f7c3f: PC: 80132b00: ADDIU     at = r0 + 0x0009

I've highlighted the instruction at which the synchroniser detected the PCs were out of sync. In the good trace (top) the PC is 0x80131fb0, but in the bad trace it's 0x80132af0. If you have particularly sharp eyes, you'll notice something else - two instructions before the code goes out of sync, the good trace executes a jump instruction to 0x80131fb0, but the bad trace is performing a MTC1 op (Move To Coprocessor 1)

This provides a particularly good example of one of the main weaknesses with the synchroniser - it's only as good as the synch points you set up. Because I was just synching on the program counter, it didn't detect the fact that the emulator executed an entirely different opcode two instructions previously. In this particular case I was fortunate in that the real source of the problem was very close to the location identified by the synchroniser, but sometimes the cause and effect can be separated by many thousands of instructions.

Fortunately it's easy enough to add new synch points in the code to detect issues like this, but adding too many synch points causes the emulator to slow to a crawl and makes debugging impractical. I've found the best approach is to start off with as few synch points defined as possible (ideally just the program counter) and slowly introduce more synchpoints as required. This is all very easy to do using the DAED_SYNC_MASK flag discussed above.

Getting back to SSB, it looked like I had found the root cause of the problem - somehow the rom was replacing the instructions in memory, essentially a form of self-modifying code (it's more likely it was just loading a new section of code into RAM from ROM, but it's still essentially self-modifying). The dynarec system was oblivious to these changes and so it ended up trying to execute stale instructions that it had cached when creating the fragment, potentially many thousands of cycles ago.

Dealing with self modifying code in dynamic code generators is generally very tricky. In Daedalus I've been relying on the fact that most roms are well-behaved and flush the instruction cache when they modify memory containing executable code. When I detect a instruction cache invalidate (through the MIPS CACHE opcode) I simply dump the entire contents of the fragment cache and start from scratch. This might sound a little heavy handed, but the way that I link fragments together makes it very hard to unlink small sections of code that has been invalided. Flushing the cache is very quick, safe and has a few advantages such as purging cold traces that are no longer being executed any more.

Ironically, the reason the dynarec was failing to cope with SSB wasn't due to a bug in Daedalus - it was due to a bug in SSB that just never happened to be a problem on a real N64. After updating memory with the new instructions SSB should have been invalidating the instruction cache to ensure that it didn't contain stale code, but for whatever reason it failed to do this. The only reason the rom runs correctly on a real N64 is that by the time it comes to execute the modified instructions, the instruction cache has been refilled a number of times and so the stale instructions are no longer cached.

Even though this isn't Daedalus's bug, it still needs to work around the problem. I'll leave this discussion for a future post though - this one is long enough as it is :)

-StrmnNrmn

Tracking down the SSB Dynarec Bug

2007-06-12T00:20:00.000+01:00

Yesterday I said I'd provide some more details about the Super Smash Bros. dynarec fix. The actual fix is fairly straightforward, but I thought the process of tracking down the issue was quite interesting and worthy of a couple of blog posts.

When I first started looking at SSB I noted that although the game ran fine without dynarec, it would always hang when trying to enter the main entry with dynarec enabled.

I've been programming professionally for around 6 years now and I can safely say that debugging dynarec bugs is one of the hardest categories of problems I've ever had to work on. For a start, because the code is generated on the fly, you don't have the luxury of source level debugging, and without spending time reverse engineering the original rom image, you don't even know what the generated dynarec code is meant to be doing. It's very much like working blindfolded.

And it gets even worse. I've fixed dynarec problems in the past which were the result of generating incorrect code for a fragment over 500 million instructions into emulation. This would be bad enough, but it can be many thousands of instructions later before this causes emulation finally diverges from the correct path. Just identifying the exact point at which the emulation starts to diverge from the correct sequence of instructions can be like finding a needle in particularly large haystack. While blindfolded :)

Over the years of trying to debug problems like these I've built up a set of tools and learned a few tricks along the way which you might find quite interesting. Although I'm going to talk about them in the context of tracking down this dynarec issue, I've found some of the techniques useful in solving other problems so you might find other ways of applying them too.

One of the first things I do when trying to identify a dynarec issue with Daedalus is to see if the problem is reproducible on the PC build of the emulator. Although it is possible to use GDB with PSPLink, I've never got this up and running and I'm much more comfortable debugging with Visual Studio. Also, working with the PC build is usually much faster than working with the PSP build (debug builds run around 10x faster on the PC, and build times are much quicker.)

Not all dynarec issues can be debugged in this way - the PSP and PC builds have different code generation back-ends (i.e. MIPS and x86 code generation respectively) so bugs in the MIPS code generation won't usually be reproducible in the PC build. The dynarec system in Daedalus shares a common frontend (trace selection and recording) between the two platforms, which means that if I can reproduce the problem on both platforms, I can narrow down the likely location of the bug to this area.

Fortunately this particular bug manifested itself in both the PC and the PSP builds, so I knew that if I fixed the bug on the PC build, it should fix the PSP build too. What I needed to find out next is what the emulator was doing differently when dynarec was enabled compared to when it was disabled.

If dynarec is running without errors, then the sequence of executed instructions should exactly match that executed with dynarec disabled. If I could log details about all the instructions executed with dynarec disabled, and again with dynarec enabled, I should be able to compare the two logs to figure out the exact point at which dynarec is going out of sync. This all relies on the fact that the emulator is totally deterministic, i.e. that running the emulator twice in succession with the same settings should give exactly the same results.

Unfortunately, for a variety of reasons my dynarec solution doesn't produce identical results to interpretation, the main reason being that for performance reasons I can only handle vertical blank and timer interrupts on the boundaries between fragments. For example, with dynarec disabled, the first vertical blank interrupt might occur exactly on the 625,000th instruction, but with dynarec enabled with might not occur until the 625,015th instruction. This means that the logs diverge at the instant the first VBL fires, and never regain synchronisation.

When I was originally developing the new dynarec system I put a lot of effort into writing a fragment simulator, the idea being that rather than executing the native assembly code for a given trace, I could keep track of the instructions making up the trace and interpret these individually instead. Theoretically fragment simulation is identical to dynarec code execution, even down to the way I handle VBLs and timer interrupts, and it's been very useful at identifying bugs in the dynarec code generation. What's particularly useful about fragment simulation however is that I can enable a setting which makes it handle interrupts exactly in the same way as the non-dynarec core, i.e. interrupts are handled precisely rather than on fragment boundaries.

Essentially Daedalus has four modes of operation:

Dynarec + fragment execution
Dynarec + fragment simulation (imprecise interrupt handling)
Dynarec + fragment simulation (precise interrupt handling)
Interpretative core

This tool is particularly powerful, because if I can ensure that dynarec+fragment execution is equivalent to dynarec+fragment simulation, and that dynarec+fragment simulation is equivalent to running the interpretative core, then I can use the transitive properties of these relations to ensure that dynarec+fragment execution is equivalent to running the interpretative core. Fragment simulation allows me to bridge the gap between these two modes of operation which would otherwise be very difficult to compare.

I think that's long enough for one post. Tomorrow I'll talk about how I used this technique to help track down the SSB dynarec bug.

-StrmnNrmn

Super Smash Bros - Dynarec Update

2007-06-10T16:00:00.000+01:00

This is just a quick update to let everyone know I've finally figured out why the dynarec wasn't working in Super Smash Bros. The problem has taken a lot longer to identify than I'd hoped - in part because it was a particularly tricky bug but also because I've not had as much time to work on Daedalus recently as I would have liked.

Anyway, I managed to spend a few hours this weekend isolating the problem, and after a little experimentation I've been able to come up with a temporary workaround. With the fix in place SSB is running at around 30-40fps in game on the PSP, which is very exciting.

Now that I've identified the problem my next job is to come up with a permanent, robust solution to help fix similar problems in other roms. I also want to add some improved checks in the debug build to help spot other situations where this problem arises.

For those that are interested I'll post an update shortly (within the next day or so) with some of the technical details.

-StrmnNrmn

Status Update

2007-05-29T22:38:00.001+01:00

It's been a couple of weeks since the last update. As people tend to get a bit nervous when I don't update regularly, I just wanted to let everyone know that I'm ok and still thinking about getting R12 ready :)

I'm still in the middle of looking at fixing the various dynarec bugs which are keeping Super Smash Bros from working with Dynarec enabled. I've not made as much progress as I would have liked since the last post, as I've been very busy with work and various other commitments. Hopefully I should get a bit more time to work on R12 from the end of this week. I'll post an update as soon as I have more news to report on.

-StrmnNrmn

Dynarec Fixes

2007-05-15T23:53:00.000+01:00

In the previous update I mentioned that the dynarec wasn't working with Goldeneye:

...I can still only get the rom running with dynarec disabled on the PSP, so the framerate is currently just 6-7 fps. Interestingly it runs fine with dynarec on the PC with the same set of changes, so this indicates a bug somewhere in the PSP dynarec implementation.

I've spent a couple of evenings investigating this problem, and I've finally had a bit of luck in determining the root cause. As I suspected it was due to a bug in the PSP dynarec implementation - it turns out that I was fiddling addresses to compensate for the different endianness of the PSP twice (essentially having the same effect as not compensating in the first place).

The fix was very easy to implement (just a single line of code). It's quite a significant bug, so I'm hoping that it will fix dynarec issues with a few other roms too. Unfortunately it looks like the bug which is preventing dynarec working with Super Smash Bros. is a different issue, so I'll have to spend some more time investigating that.

I'm pleased to say that Goldeneye is now running fine with dynarec, so it now boots and runs the intro sequence very quickly. Although the intro and menu run at around 30-60fps, in-game is still very slow (around 5-8fps) so I need to profile this and see what's going on.

As I've hinted above, the next job is to have a look why dynarec is causing Super Smash Bros to hang. A cursory look revealed that it's still broken even when I disable most of the native code generation and directly call the interpretive instruction handlers from the compiled fragment. Because of this I think the problem has something to do with how traces are selected and the resulting fragments are linked together. I'll know more later in the week.

-StrmnNrmn

Goldeneye Update!

2007-05-10T21:41:00.000+01:00

Ok, I know the last thing I said yesterday was:

Anyway, given the work involved Goldeneye isn't an immediate priority, but I am thinking about it.

I couldn't quite resist having a quick hack to see if I could get Goldeneye working using the third method I outlined. It turned out to be relatively painless to crowbar in the required changes, and I'm pleased to say that I've managed to get Goldeneye booting again! :)

With the changes, Daedalus now dynamically pages the Goldeneye ROM into the PSP's RAM so that it no longer requires a free 12 MiB. I now check the instruction pointer on every instruction fetch in the interpretive core*, and raise a TLB Read Miss exception if required. If this happens, it causes Goldeneye's exception handler to realise that the required code isn't in memory, and to load it in from ROM before continuing execution.

So here are the first screenshots of Goldeneye running under Daedalus R12 - you can see there are a handful of graphical glitches to sort out, particularly on the main menu:

Not bad for an hour's work!

There's still quite a long way to go though. Firstly, I can still only get the rom running with dynarec disabled on the PSP, so the framerate is currently just 6-7 fps. Interestingly it runs fine with dynarec on the PC with the same set of changes, so this indicates a bug somewhere in the PSP dynarec implementation. Secondly, I've not been able to get in-game yet - it just seems to hang with a black screen shortly after starting to load the level. I've not figured out whether this is just running very slowly without dynarec and taking its time, or if there's another bug to be fixed somewhere.

Getting the rom booting is a great first step though - it can only continue to improve from here :)

-StrmnNrmn

*I probably want to tidy things up to avoid doing this for most other roms as it can be quite expensive - especially if dynarec is disabled.

Goldeneye

2007-05-10T00:30:00.000+01:00

While I'm at it with the blog updates, I also invesitgated why Goldeneye no longer works in Daedalus (it did run with some of the very early releases, but stopped working some time ago.)

Goldeneye is quite an unusual game in that it's one of the few titles that executes code from virtual memory. I'm not sure exactly why it does this, but I suspect that it's to allow it to free up as much RAM as possible. It sets up a virtual memory range for the code, and pages in chunks of data to physical RAM as required (i.e. on TLB miss exceptions). I guess this means that it can just keep a few dozen KiB of code in RAM at a time, rather than the entire code segment.

Anway, emulating this accurately is incredibly slow - for every instruction that is executed, the emulator needs to check whether the instruction fetch would cause a TLB miss exception, and if so invoke the N64's exception handler. This is quite a time consuming process, so I tend to cheat and assume that the instruction pointer is in physical memory.

To get around this problem with Goldenye, I set up a couple of bogus entries in Daedalus' memory map that point directly to the correct region in the ROM image. In a way it's as if the N64 has a much larger TLB, and all the pages are permenantly mapped.

Normally (i.e. on the PC version of Daedalus) this all works fine. The problem as far as the PSP version is concerned is that the rom (all 12 MiB for Goldeneye) must be permenantly loaded into memory, and there just isn't enough memory left to do this anymore. As most N64 roms are simply far too large to fit in the PSP's RAM, I have to page chunks in from the memory stick on demand (pretty similar to what Goldeneye was doing on the N64 really :D)

So, there are a few possibilities for getting Goldeneye to work:

Permenantly disable dynarec for Goldeneye, and reuse the dynarec buffers (6MiB) the expansion pak (unneeded anyway, 4MiB) and anything else I can scavenge, to fit the rom in a contiguous block in memory.
Investigate a way of getting the memory-mapping hack to work with rom caching.
Re-examine how I handle TLB miss exceptions for instruction fetches, and implement them correctly.

Of all of these, the first solution is probably the easiest, but it's a bit hacky (I'd have to allocate a 12 MiB for Goldeneye at startup, and carve this up for different subsystems if other roms were run).

The second solution is a bit less horrible, but I'm still not sure it's possible without checking the instruction pointer for every instruction that's executed (and paging in chunks of ROM as required).

That leaves the third solution which is probably the most work, but I think will be the most stable solution in the long run. It may also help a few other roms that are using similar techniques to Goldeneye to run correctly. If I can get it to work in conjunction with the current dynarec implementation, it shouldn't even be any slower than the current hack that's in place.

Anyway, given the work involved Goldeneye isn't an immediate priority, but I am thinking about it.

-StrmnNrmn

R11 Mario HUD Issue

2007-05-10T00:00:00.000+01:00

As a few people have pointed out on the R11 release comments page, I broke the HUD in Mario 64 in R11 :(

I investigated a little, and it turns out it was due to a tiny change I made sometime on Saturday. Basically I changed the alpha threshold test from >= to >, and so nothing with an alpha of 0 is ever rendered. This shouldn't be an issue, except for the bizarre render states that Mario sets up to render its HUD.

I don't think this is a too significant issue as Mario is just as playable in R10. I'd rather release R12 a little early to fix this than mess around releasing an R11b version or whatnot. We'll see how things go with the SSB work.

-StrmnNrmn

Early SSB Progress

2007-05-09T23:50:00.000+01:00

As I mentioned on Sunday, my main focus for R12 is to fix whatever's causing the dynarec to hang with SSB, but to start with I've spent a little time looking into fixing some of the graphical issues plaguing Super Smash Bros.

In the end I fixed four or five separate problems which were all causing quite significant glitches.

The first bug was that I was assuming that the fixed-point texture coordinates specified in the TexRect (i.e. 2d textured rectangle) commands were unsigned. It turns out that they're actually signed - SSB just happens to be one of the few roms that ever specifies negative values.

The next issue was that I was ignoring the RDP tile* mask parameters, and assuming that the tile width and height always defined the extents for both wrapping and clamping. As it turns out, the mask values (if set) define how many bits from the texture coordinate to accept - all the other bits from the texture coordinate are ignored. This means that if a tile defines a mask of 5, the texture will wrap every 2^5, or 32 texels. What's quite interesting about the N64 is that it lets you define different limit for clamping than for wrapping. For instance, you can wrap every 32 texels, but clamp the texture to a coordinate of 100 (i.e. after the texture has repeated 3 and a bit times.) It turns out this is exactly what SSB was doing.

A related issue was that as the PSP only supports textures with power-of-2 dimensions, I have to pad out non-power-of-2 textures from the n64 with empty space. As I was assuming that the n64 always clamped at power of 2 boundaries, it meant that the PSP occasionally displayed texels from bits of the texture that I hadn't initialised. To get around this I just manually repeat the last column/row of the texture when converting it on the PSP.

Another issue I fixed was relating to how I handled 'swizzled'** textures that were not an even number of texels. In the second screenshot on the left below, you can see a fringe of corrupt pixels down the right-hand side of each character's icon. This was due to me not correctly handling all of the texels the swizzled rows, but it only happened when the rows were not a multiple of 8 bytes (in the example below, the textures were 30x32 texels at 16bpp). Again, this is something SSB does that I've not seen in other roms.

I fixed a bug relating to how I was recolouring textures. In order to support some of the N64's more complex combiner modes on the PSP, I need to replace the RGB channels of a texture while maintaining the existing alpha channel. As it turns out, I wasn't handling this correctly for textures that weren't a power of 2. This is what is messing up the black background behind the 'Super Smash Bros' text on the first screenshot. Whoops.

Wow! That's quite a few bugs! Here's a few screenshots, with SSB running in R11 on the left, and the R12 work-in-progress on the right:

What's quite nice is that even though I've been fixing these with SSB in mind, there are likely to be lots of other roms which I've not tested that are relying on the same behaviour.

Graphically SSB is looking pretty slick, so now it's on to chasing down that dynarec bug :)

-StrmnNrmn

* The RDP has 8 tile attribute descriptors, which are used to tell the RDP how to interpret the data loaded into it's 4KiB of texture memory. They define properties such as the tile's format, width, height and whether to clamp or wrap and so on.

** On the N64, all odd rows in a texture have pairs of texels alternated (or more precisely pairs of 4-bytes of data.) The reason for this is that the N64's texture memory is composed of two separate banks of 2KiB, and organising texels like this allows for multiple texels to be accessed simultaneously when sampling from the texture. I use the term 'swizzled' loosely as it's quite a different process than swizzled textures on modern consoles (such as the PSP and the Xbox (see page 28)), even if it is performed for similar reasons.

Daedalus R11

2007-05-06T13:17:00.000+01:00

Daedalus R11 is finally here. It took a little longer than I expected to merge the changes across to the sourceforge subversion repository but I got there in the end :)

Anyway, here are the latest files:

Daedalus PSP R11 for v1.00 Firmware
Daedalus PSP R11 for v1.50+ Firmware
Daedalus PSP R11 Source

Here's the changelist:

[*] Large overhaul of rom settings and preferences. All settings should now be persistant.
[+] Native support for palettised textures for faster rendering and less memory usage.
[+] Provided a fixed size pool for all texture memory, to limit memory usage.
[+] Expansion Pak enabled by default.
[!] Updated rom info database to include save mechanism for many roms.
[!] Fix memory leak in texture cache.
[!] Fixed conversion of RGBA/32bpp textures with odd alignments.
[!] Fix crash which occurred when recolouring textures in low memory situations.
[^] Large rewrite of texture cache to reduce memory usage and improve performance.
[^] Various optimisations to the way textures are looked up in the cache and installed.
[^] Optimise offsetting/scaling of texture coordinates.
[^] Improve performance of dynarec fragment cache and reduce memory fragmentation.

As always, let me know your thoughts on the comments pages. I don't always have time to reply to all of the comments, but I do read every one of them.

-StrmnNrmn

R11 Sometime on Sunday

2007-05-06T02:45:00.000+01:00

I'm very close to having R11 ready for release, and I'm aiming to have everything finished some time tomorrow morning (that's Sunday morning, UK time.)

I've spent the day putting in number of changes to the way that Daedalus allocates memory for various lookup tables. Namely, I've replaced a couple of stl maps I was using to keep track of cached textures and dynarec fragments with sorted vectors, which should help reduce fragmentation and improve cache usage. Basically it should make things even more stable and give another small speedup.

I've also been through and updated the rom.ini file I talked about a couple of weeks ago to make sure that it contains accurate information for the save type. I noticed that many of the entries for European roms were undefined, which can cause various compatibility problems. Hopefully this should mean that a few more European roms are working in R11.

Finally I realised that there was a dynarec issue which was preventing Super Smash Bros from going in-game. Although that's not fixed (that's something for R12) I have disabled dynarec for SSB by default. With my various texture cache fixes SSB is now running in-game, albeit with messed up graphics and at just 15 fps. Here's a teaser screenshot of SSB running in R11:

Given how many people have been asking for SSB compatibility to be improved, I'm pretty sure this is going to be my main focus for R12. If I can fix the dynarec issue it looks like this is going to run at a solid 25-30fps or more.

Anyway, check back sometime over the next 12 hours for R11 (I'm off to bed for now, let's hope I don't lie in :)

-StrmnNrmn

R11 almost ready

2007-04-30T00:33:00.000+01:00

Following on from last week's work, I've been busy fixing a few more issues relating to the way Daedalus handles textures.

To start with, I refactored the way that n64-format textures are converted to psp-format textures. Previously, I was converting the textures at the point at which they were loaded into texture memory on the n64. A result of this was that in order to support mirroring, I needed to keep a copy of the converted pixels in RAM. By moving the conversion process closer to the point that the textures are actually used on the psp, I've been able to remove this buffer and perform conversion and mirroring in the same step. This has approximately halved the memory needed for each texture, and is slightly faster than the previous approach.

The most significant change I've made is to fix a memory leak in the texture cache. I mentioned last week that I'd discovered that the texture cache was the biggest culprit for soaking up memory. It turned out that despite my fixes and support for 4-bit and 8-bit palettised textures, I was still running out of memory in certain situations. I did a bit more investigating, and discovered a resource leak that had been in the texture cache since it was first written (probably 7 or 8 years ago now!)

It turned out that in certain situations, several textures would hash to the same bucket in the hash table that I was using. This wasn't normally a problem, but occasionally the process which purges old textures from the cache was accidentally leaking textures. This was wasting video memory and causing the leaked textures to be re-converted on next frame.

The fix ended up being a very simple one-line change, and as a result the texture cache is now 100% leak-free. As an added bonus, it seems that the change has resulted in a nice 4-5% speedup - I suspect this is because the leaked textures are now no-longer being unnecessarily reconverted.

The final bit of work I've been doing is setting up a fixed-size pool for allocating textures from (well, there are actually two pools - one for fast VRAM and another of standard RAM for when this runs out). Despite the various improvements and fixes I've made to reduce the amount of memory being consumed by the texture cache, I wanted to put a hard limit on how much memory can ever be used. This change means that if the limit is ever reached, I just display white textures until some texture memory is freed up a little later. Previously Daedalus would just keep allocating RAM until it ran out of memory and crashed, so the new solution is much nicer :)

All in all I'm very happy with the state of R11. The changes I've made mean that I can permanently allocate 8MB for the Expansion Pak, and not worry about running out of memory. A welcome side-effect to all the texture changes I've made is an approximate 5-10% speedup over R11. On top of this Daedalus now remembers your preferences for each rom, so it's a little nicer to use.

I've still got a few small things to polish, but I'm hoping to release R11 by the weekend.

-StrmnNrmn

R11 Update

2007-04-22T19:41:00.000+01:00

Wow, it's been far longer than I'd intended to give this update. I had a great time in Spain, and came back and spent a few evenings playing through Crackdown. It was quite nice to take a break for a few days :)

Since then I've been working on the various features I promised for R11.

I talked a bit about the texture cache being the main culprit for gobbling up memory while the emulator is running. When I started profiling this in detail, I realised that one of the worst offenders for memory consumption was mirrored texture support for 4 or 8-bit palettised textures. There were actually two main problems which were exacerbating the problem.

Firstly, I've never handled palettised textures directly in Daedalus. By that, I mean that rather than converting the palettised texture on the n64 to a palettised texture on the PSP, I've been converting it to a 32-bit RGBA texture. This means that on the n64, a 64x64 pixel 4-bit palettised texture would take up 2KiB. By converting this up to a 32-bit RGBA texture on the PSP, it takes 16KiB - an eightfold increase in memory usage.

The second issue which was compounding the problem was that the PSP doesn't have support for mirrored textures. In order to support this feature I have to manually duplicate and mirror the texture. This means that a 64x64 texture mirrored along the S and T axes on the n64 will become a 128x128 texture on the PSP.

The main problem I was getting due to running out of memory was due to the heavy use of mirrored 4-bit palettised textures in some games. A 64x64 4-bit palettised texture that took up 2KiB on the n64 would consume a huge 64KiB on the PSP - a 32-fold increase! The problem was that certain games were using dozens of such textures in a single display list, and the available memory was rapidly being exhausted.

So over the past couple of weeks I've been working on rewriting Daedalus's texture handling so that it supports 4-bit and 8-bit palettised textures directly. This has taken a lot more time than I'd anticipated because of the number of places in the codebase which have to fiddle around with texture data directly. I also spent a week trying to track down two horrible bugs (both of which turned out to be brain-dead logic errors on my part).

The great thing about this work is that not only does supporting palettised textures directly save a lot of memory, it also has a number of small performance benefits. Generating less texture data generally means a bit less work for the CPU (well, less cache usage), so converting palettised textures is now a bit quicker. Palettised textures are also a lot more efficient to render with (mostly due to the fact that they consume less bus bandwidth and can make better use of the PSP's texture cache.)

The other big chunk of work I've been bashing away at is improving the way that I handle preferences for individual roms. One of the big problems with the current setup with Daedalus is that the main daedalus.ini file consists of both global rom-specific details (such as the rom's name, save type, comments etc) and local user-defined preferences (such as whether to enable speed sync, disable dynarec etc). This means that I can't ship a new version of daedalus.ini without wiping out people's local preferences.

What I've done now is split daedalus.ini into two files. roms.ini will contain global rom-specific details, and an updated version will be distributed with every version of Daedalus from now on. If I know dynarec causes a certain rom to fail to run, I can add a setting for this in roms.ini, and everyone will be able to pick up the change in the next release. Another good example is the SaveType field; every version of Super Mario 64 uses a 4k EEPROM, and so once this is set up in roms.ini it should never need tweaking.

The other file I created is called preferences.ini. This file won't ship with Daedalus - the emulator will create this the first time you change some settings when playing a rom, and update it with any further changes that you make. This means that when you copy a fresh build of Daedalus across to your memory stick, the new build will pick up your existing preferences.ini file and so remember all of your settings.

The settings that Daedalus will currently remember for each rom are:

Texture Update Check
Frameskip
Limit Framerate
Dynamic Recompilation (used to override the setting in roms.ini if you're having problems with dynarec)
Audio
Adjust Frequency
Controller

I'll be adding to this list over the coming months, as more options become configurable.

One other thing that will be stored in preferences.ini (which I've not coded yet) is all of the options from the 'Global Settings' page - stuff like the viewport size, stick deadzone, whether to display the framerate or not, etc.

So R11 is shaping up pretty nicely, even if it's taken a bit longer than I'd hoped. I have a few more things to work on, but I'll try to keep you all updated a bit more frequently as I work towards the next release.

-StrmnNrmn

R11 Plans

2007-04-05T02:20:00.000+01:00

I had planned on posting this update on Monday, but I've spent the last couple of nights catching up on a few games that I've not had chance to play since they were released (Crackdown on the 360 and Afterburner : Black Falcon on the PSP for the curious :)

For R11 I'm hoping to fix the Expansion Pak support for once and for all. Memory is currently very tight, so I need to look at shaving off a few hundered KB here and there. Almost all the memory Daedalus uses is allocated up front - there are very few dynamic allocations at runtime, with the biggest culprit being the texture cache. So for R11 I want to introduce a pooled allocator for the texture cache, which will mean that when it runs out of memory, you just get white textures appearing rather than a hard crash.

The other feature I want to improve in R11 is the way that global settings and per-rom settings are handled. At the moment Daedalus discards any changes to settings that you make when you restart your PSP, and it can be incredibly tedious setting things up every time you run a game. This is quite a small feature to add, but I think it will make the emulator much nicer to use.

Behind the scenes, I want to spend a short while working on some scripts to handle packaging new releases for distribution. Current I do all of this by hand, and it's one of the things I least enjoy about the project. Hopefully, the more automated I can make this, the more frequently I'm likely to release builds :)

I'd like to get all these changes done and release R11 within a couple of weeks. I have a couple of busy weekends coming up, so I'm not going to specify an exact date. You can expect it before May though (I'll try not to be a couple of days late this time :)

R11 is essentially going to be a compatibility release - hopefully the Expansion Pak support will lead to a few more roms running (Majora's Mask being one I've already verified). Looking further ahead, R12 will be back to concentrating on speed (as it happened, R10 achieved a 10-15% speedup without having implemented the majority of the optimisations I had planned :)

-StrmnNrmn

PS Off to Spain again over the Easter bank holiday weekend. Back on Tuesday :)

R10 Reception

2007-04-05T02:10:00.000+01:00

I just wanted to say a quick thank you for all the feedback I've received on the R10 release. I'd been looking at it as quite a small update, but people seem to be very happy about the incremental speedup and new features such as frameskip and so on. I found releasing R10 within 4-5 weeks of R9 was really hard work, but I'm now convinced that releasing smaller updates more regularly is the right way to go. I'll be following this post with some details about the plans for R11.

Finally, it turns out that this blog had over 40,000 visits over Sunday/Monday, which is incredible - thanks for continuing to read :)

-StrmnNrmn

Daedalus R10

2007-04-02T00:44:00.000+01:00

This is a few hours later than I'd hoped, but here's R10:

Daedalus PSP R10 for v1.00 Firmware
Daedalus PSP R10 for v1.50+ Firmware
Daedalus PSP R10 Source

This is the changelist:


[+] Added frameskip option.
[+] Added framerate limiting option.
[+] Added adjustable stick deadzone.
[+] Allow pause menu to be activated even when rom emulation has hung.
[!] Fix crash when no roms found, added explanatory message.
[!] Fix flickering when small number of roms found.
[^] Fix texture hash frequency check.
[^] Finally got code compiling with -O3 optimisation flag in GCC.
[^] Use VFPU for InvSqrt (thanks hlide!)
[^] Improved VFPU code for clipping and tnl (thanks Raphael!)
[^] Improved inlining of AddTri.
[^] Reduced time spent searching for overridden blend modes.
[~] Remove debug console in public release builds (smaller footprint and slight speedup.)

I'll post tomorrow with details on what I want to work on for R11. In the meantime, enjoy!

-StrmnNrmn

R10 Countdown

2007-03-29T23:47:00.000+01:00

I'm in the process of tidying up my current build so that I can release R10 over the next few days.

There are a number of features/optimisations still on my TODO list, but as I promised last month, I'd like to release R10 by the end of March. I think frequent, small updates are better than keeping everyone waiting months between releases.

Although R10 will be a smaller update than R9, there are some great improvements (most of which I've already talked about):

An approximate 10-15% speedup
Frameskip, framerate limiting and stick deadzone tuning
Various small bugfixes

I'm hoping to have everything ready by Sunday afternoon at the latest.

One feature which might not make it is the Expansion Pak support. I mentioned that I'd finally fixed the bug that was preventing this from working, but I've been having difficulty resolving the various memory issues that it causes when enabled. Rather than delay R10, I'd prefer to disable the Expansion Pak support for now and release R11 early - as soon as I've fixed the underlying problem. I'll keep you posted.

-StrmnNrmn

Frameskip

2007-03-21T08:56:00.000Z

A couple of people have been commenting about the mysterious frameskip version of Daedalus R9 which appeared a short while ago. I'm not going to link to it because I can't verify where it came from. That said, I've not checked my email for a week so maybe the author has emailed me about it :)

Anyway, it just so happens that I implemented frameskip in R10 on Sunday, so expect this to be a supported feature in the next official release. I had been planning to add this to R9, but I forgot :) It's no big deal - it's about 20 lines of code.

It does give a slight speedup, but not always as much as you'd expect. For instance, skipping every other frame won't double the framerate, as not all the time is spent rendering. Paradoxically, it tends to have more of an effect on roms that are already running fairly fast. Hopefully for some roms it will make the different between them being barely playable and playable though.

There are a few other things people have been asking about which I will implement for R10 too:

A configurable deadzone for the stick
A configurable framerate limiter

-StrmnNrmn

A look inside Daedalus

2007-03-20T23:41:00.000Z

(This is quite technical post, probably only of interest to other C++/PSP developers.)

Since I fixed the issue stopping the Expansion Pak support from working, I've been testing daedalus with the feature enabled to see if the added pressure on available RAM causes any new issues. Most roms that I've been tested have been running perfectly, but I've been experiencing occasional crashes through running out of memory. I believe this is due to a small leak somewhere, so in an effort to track it down I've been improving the tools I use to track memory usage.

In the improved tracker I override the global new and delete operators, which lets me perform some logging on every allocation/deallocation made during the course of executing the emulator (this isn't quite true, as I don't currently log calls to malloc etc, but it's good enough for my purposes). At the start of each overriden implementation, I keep track of the calling function's return address with the following snippet of code:


u32 ra;
asm volatile
(
    "sw $ra, %0\n"
    : "+m"(ra) : : "memory"
);

I log this return address along with the allocation size and the returned pointer for every call to new and new[]. For calls to delete and delete[], I just log the address of the memory being freed and the caller's address. This data is all logged to disk across the USB connection using PSPLink.

The logfiles look a little like this:


Allocating         36 bytes - 09c40620 - RA is 08953a94
Allocating[]     8192 bytes - 09c40a00 - RA is 0895e8bc
Allocating         12 bytes - 09c3fce0 - RA is 08964898
Allocating         12 bytes - 09c40970 - RA is 089648b0
Allocating         12 bytes - 09c409d0 - RA is 089648c8
Allocating         12 bytes - 09c408e0 - RA is 089648e0
Allocating         20 bytes - 091ceb20 - RA is 089645e8
Freeing   09c3fce0 - RA is 08962374
Freeing   09c40970 - RA is 089621fc

In order to analyse the results I've written a PC tool which scans through the logfile one line at a time 'replaying' the allocations and deallocations in the same order that they occured on the PSP. The analyser keeps track of the current state of allocations at any point in time, matching up any calls to delete with the corresponding call to new. This means that at any given time the tool has a complete list of all outstanding allocations.

I can discover any memory leaks by shutting down the emulator and continuing to record the logfile while it frees up all allocated resources. By replaying the logfile the analyser can identify any leaks, as these are (mostly) the only remaining allocations at the end of the logfile. I can then run the corresponding return addresses through psp-addr2line to discover where the leaked memory is being allocated from.

The other cool feature of the tool is that it builds up a graphical representation of the state of memory allocations at any point in time. This is really useful for figuring out where all the available RAM is going.

Here's a picture showing where most of the PSP's memory is being used while emulating Mario 64 (I've added the labels on by hand, the tool doesn't do that :)

Each pixel corresponds to 16 bytes of RAM. The smallest blocks are 64x64x16 bytes = 64KB. 1MB chunks are formed from 4x4 64KB blocks. The black space corresponds to both unallocated memory, and also memory allocated outside of the tracker (e.g. calls to malloc, memory used by PSPLink, the CRT, static data areas etc.) You can see that the "Emulated RAM" accounts for just over 8MB - this is because I enabled the Expansion Pak while testing. Dynarec currently uses about 6MB - Ideally I'd like to reduce this down to around 4MB soon.

You'll notice that almost all the memory Daedalus uses is for these big fixed-size allocations. What little dynamic allocation it does at runtime is limited to:

Keeping track of hot-trace hit counts in the Dynamo implementation
Textures and texture caching

As it turns out, the out-of-memory issues I've been having have been due to the texture cache going crazy and chewing up around 3MB of memory (typically it just uses 200-300KB or so). I've not figured out the root cause yet, but the tool has helped point me in the right direction.

All in all I think this is a pretty nifty utility as it stands, but I've been thinking about a few features that would make it even better:

Log the time and current frame alongside each allocation/deallocation. The analyser can then use this information to see how much 'churn' there is over time. Minimising this should help improve performance and reduce fragmentation.
Every memory allocation has a small housekeeping overhead (for alignment, keeping track of the allocation size etc). The tool could generate a histogram of allocation sizes to demonstrate how much memory is being wasted through tiny allocations, and give some indication of where pooling or freelists might help.

These are probably features for some point down the line however :)

That pretty much sums up the tool. If this code (either for the tracker or the logfile analyser) would be useful to anyone, let me know and I'll add it to Subversion alongside the rest of the Daedalus code with R10.

StrmnNrmn

Daedalus R10 Optimisation Progress

2007-03-18T23:13:00.000Z

I didn't mean to leave it quite so long since last weekend's update, but I've been working hard on a number of optmisations for R10. Oddly enough these are mostly new issues that I've found - most of them don't exist in the list of tasks I came up with a couple of weeks ago. I think that shows how much scope there is for optimising Daedalus!

Firstly, I finally managed to get Daedalus compiling with GCC's '-O3' setting. This flag turns on all of the optimisations that GCC provides. When I've tried to enable this flag in the past I've had numerous strange crashes and odd behaviour, so all releases of Daedalus to date have been compiled with -O1.

I updated my local installation of the PSPSDK last weekend and decided to try the -O3 setting again. I was pleased to find that Daedalus ran without crashing, but there was still some odd behaviour which I eventually tracked down to my use of the famous InvSqrt function. You can read a bit more about my findings on the pspdev forums.

Enabling -O3 tends to slightly increase the code size (the EBOOT.PBP has increased from around 850KB to 900KB), but the speedup is quite noticable - my estimate is that Daedalus runs around 5% faster with -O3 over -O1.

As a result of the thread I started on the pspdev forums, hlide and Raphael both came up with some great suggestions for how I could optimise my use of the VFPU.

When I originally wrote the VFPU code for TnL and clipping there were still many undocumented/unsupported functions. A few months down the line and hlide and co have discovered a couple of instructions which are perfect for my needs - namely vuc2i and vc2i. These two functions take a 32-bit value comprising of 4 (un)signed 8-bit chars and unpack them into a vector of 4 32-bit fixed point numbers. It turns out that these instructions are perfect for converting the N64's packed colour and normal values into a format I can use in the VFPU code.

The various VFPU tweaks I've made have given Daedalus another 5% or so speedup.

The final set of changes I've been working on this week have been to do with how I handle certain blend modes. Some of the N64 blend modes are too complex for the PSP to deal with precisely, so I have a large table of 'override' blend modes which allow me to make as good an approximation of the N64 mode as possible. It turned out that looking up these blend modes was very expensive, so I've rewritten how this is handled to make it more efficient. The end result is another small speedup.

Overall these three changes give a combined 10-15% speedup on the various games I've tested, although there are roms that lie outside this range (some show an even greater speedup while others are more or less unaffected by the changes).

There's still quite a lot more in the way of optimisations that I want to get in for Daedalus R10 (mostly stuff I mentioned earlier) so hopefully these numbers will improve even further over the next couple of weeks.

-StrmnNrmn

Weekend update

2007-03-10T12:23:00.000Z

It's been a busy week at work, what with catching up after my week off and GDC, so I've not managed to post as many updates as I'd have liked.

On Daedalus I've been starting to take a look at the list of potential optimisations I listed and working out what to tackle first. To help me do this my first job is to do some work on Daedalus's profiler, to try and figure out where the biggest wins are going to come from. Hopefully I'll be able to report back with some interesting findings this weekend.

On a related note, I've spent the morning looking at converting the source control I'm using at sourceforge from CVS to Subversion. I've been meaning to do this for some time. I've never really been a fan of CVS, and as I'm using Subversion for other projects at work and at home I thought it made sense to migrate Daedalus over too.

So you can now access the latest Daedalus source* through Subversion:


svn co https://daedalus-n64.svn.sourceforge.net/svnroot/daedalus-n64/trunk daedalus-n64

With CVS I usually only updated the source alongside every release. Ideally the repository would contain an up-to-date copy of my local build, but I've had problems in the past where people have distributed 'intermediate' builds of Daedalus PSP, bugs and all. I only ever release new builds when I think there are enough new features and its stable enough to make it worthwhile for people to download and install; updating a source a bit less frequently gives me a bit more control and helps prevent everyone's time being wasted with intermediate builds. I think that I'm going to continue with this policy for the time being. We'll see how it goes.

-StrmnNrmn

*This is still just the R8 source which I lifted from CVS today. I'm in the process of testing whether this compiles OK, then I'll refresh the repository with all the changes from R9. I'll update this post when the R9 source is available.

Edit: R9 source commited to Subversion, all seems to be compiling OK.

R10 Plan of Action

2007-03-06T08:02:00.000Z

Before I went away on holiday I asked you what you thought I should look at working on for the next release of Daedalus. Over 200 of you replied, and I've greatly enjoyed reading what you've had to say. There were some brilliant suggestions, so many thanks for your contributions.

It seems pretty clear to me that speed is the single biggest issue that most people want to see addressed. Many people also mentioned compatibility and savestate or save game support, but in nowhere near the same kind of numbers as those wanting speed improvements.

Based on your feedback my current plan is to release Daedalus R10 at the end of March, focusing mostly on speed improvements. If I can fit in any easy compatibility fixes, I'll do this too*.

Several people have asked what possibilities remain for optimisation. Here's a short list of things I know need more work:

In many games, a lot of the time spent executing dynamically recompiled code is doing things which can potentially be emulated at a high level. For instance, over 5% of the time spent executing dynarec code in Mario64 is just converting matrices from floating point to fixed point format. Another 4-5% of the time is spent in a loop invalidating areas of the data cache (which is irrelevent in an emulator.)
Some of the most expensive fragments are those which branch to themselves (i.e. those doing many loops). I can optimise for this to avoid loading and flushing cached registers on each iteration through the loop.
I can implement a frameskip option (I had intended to implement this for R9, but forgot!)
I can make use of the Media Engine (as Exophase suggested in conversation, as the ME can't access VRAM, it might make more sense to execute Audio and Display Lists on the main CPU, and run the N64 CPU emulation on the PSP ME)
There are certain situations where I fail to create fragments in the dynamic recompiler - for instance if the code being recompiled writes to a hardware register, this triggers an interrupt and causes fragment generation to be aborted. I should be able to deal with situations such as this more gracefully.
The fragment generator can do a lot more to improve register caching, and eliminating redundant 64-bit operations.
There are many situations where N64 roms busy wait. I detect very simple occurances of this, but not all of them. If I manually identify more complex examples I can have the fragment generator optimise them away.
Some roms are causing the dynarec fragment cache to be repeatedly dumped and recreated (I think Banjo Kazooie is one example of this). Fixing this may just involve tweaking a couple of magic numbers.
I currently optimise memory accesses under the assumption that most accesses are in the range 0x80000000 - 0x80800000, which is incorrect in the case of roms that make heavy use of virtual memory, or access RAM through the mirrored range at 0xa0000000. I can improve the trace recorder to collect information on which range a memory access fell in, and generate code to speculatively optimise for this.
Now that the dynarec engine is producing much better code, the cost of display list processing is becoming more significant, and may finally be worth profiling and optimising.

That's quite a big list, so I doubt I'll be able to work on these things before the end of March, but I think it shows there's still a lot of scope for further optimisation.

-StrmnNrmn

*Just this morning, I figured out why the Expansion Pak support was broken, so Majora's Mask and a couple of other games relying on this are booting correctly now :)

Back!

2007-03-04T20:01:00.000Z

Just a quick post to say that I'm back safe and well from skiing. It was awesome! As an added bonus I made it through the week without breaking any bones :)

Lots of people posted with their thoughts on what I should work on for R10 - many thanks for all your feedback. I'll post an update with my plans shortly (probably sometime tomorrow, after I've recovered from the travelling.)

-StrmnNrmn

Please please please

2007-02-22T13:11:00.000Z

If you're referencing posts on this site on your website/forums etc, please make some effort to quote relevant parts of the post rather than copying the entire text verbatim onto your site.

I've seen the entire body of the previous post quoted in its entirety on a couple of forums, including the line "Please reply to this post with your opinions on what I should work on next." Visitors to those sites are getting confused and posting their suggestions on the external forum, rather than on this blog. Unfortunately it's very unlikely that I'll read or be able to respond to people's comments on other sites.

Thanks!
StrmnNrmn

Plans for R10

2007-02-22T10:32:00.000Z

Now that R9 is finally available, I'm ready to start making plans for R10. Firstly, I really don't want to leave it so long between releases again. The longer I leave between releases, the more hype builds up, and the harder it is to meet people's expectations. I prefer the idea of doing fairly frequent, incremental releases rather than relasing versions with huge sets of changes periodically.

So I'm currently planning to release R10 sometime around the end of March. The question is, what should I focus on?

The areas which clearly need lots of work are speed and compatibility. Unfortunately it's a bit of a chicken-and-egg situation - if the emulator runs slowly, it doesn't matter if certains roms don't run, because they'd still be unplayable. On the other hand, there's no point in having an ultra-fast emulator if it doesn't run the games people want to play. As I see it, I have to keep working on both of these things - in the long term, it doesn't make sense to concentrate on one and not the other.

I think the best approach is to alternate on work between the two areas. R9 saw significant speed improvements, but almost no progress with compatibility, so I'm currently leaning towards trying to get a few of the more popular titles running. But you're the ones who are going to be using the emulator, so I want to hear your views on what I should work on next.

Please reply to this post with your opinions on what I should work on next. Have a good play with R9 to see what's changed - maybe some things are working better than you expected. Maybe some things are no longer working? Here are a few suggestions:

Speed. Make it faster generally? Is there a specific game that runs slowly which you'd like to see an improvement with?
Compatibility. Should I work on FlashRAM support? Is there a specific game that doesn't boot, or crashes the emulator? Does your favourite game boot, but then crash when you try to start playing?
Audio. The audio support is quite new. Are there certain games where it doesn't work? Should I try to improve the audio so it's less choppy?
Graphics. Maybe your favourite game runs, but there are significant graphical glitches?
Save Games. Save game support is currently 'in' for EEPROM and MemPak based saves, but very flaky. Should I work on improving this so you don't lose your hard-earned progress?
Savestate. Would it be better for me to implement savestate support, so you can save an resume a game at any point?

As I mentioned earlier, I'm going to be away all next week, but I'll try to post as many comments as I can before then. When I get back I'll work through the comments and announce what I'm going to concentrate on for R10

-StrmnNrmn

Daedalus R9 - Rejoice!

2007-02-22T01:00:00.000Z

I've been working hard making the last few changes for Daedalus R9, and I'm pleased to say that it's now ready for download:

Daedalus PSP R9 for v1.00 Firmware
Daedalus PSP R9 for v1.50+ Firmware
Daedalus PSP R9 Extras (a few preview pictures for the UI etc)
Daedalus PSP R9 Source

I've talked a bit about what's in this release, so I'll not repeat everything here. Here's a summary though:

* Faster
* New UI
* Audio
* Various graphical fixes

Please note - as audio support is very much 'beta' at the moment, it's disabled by default. You can enable the setting either in the front-end, or from the pause menu.

Please also note: To keep the distribution size down, I've not included any 'preview' pictures for the rom selector alongside the emulator. You can download and extract the 'Extras' file above for a few sample previews. It should be easy enough for people to create their own preview pictures - see the readme.txt for more details.

That's about it for now. Please post comments with any immediate feedback. I'm going to be a bit busy for a few days (and then I'm off skiing on Sunday for a week), but I'll try to reply to as many questions as I can in the meantime. I'll also try to get the ball rolling with my initial thoughts on stuff I want to do for R10.

[Edit 1:07AM - You may need to wait a few minutes for sourceforge's mirrors to synchronise. Sorry :) ]

Enjoy,
-StrmnNrmn

R9 Status Update

2007-02-18T22:46:00.000Z

It's been a couple of days since my last post, so I wanted to give a quick update on what's left on my R9 TODO list.

I've been working over the weekend at fixing a number of outstanding graphical glitches, putting in place a system to automatically translate n64 blend modes to the psp. This should hopefully nearly eradicate nearly all of the purple and black textures that have shown up all over the place in previous releases. This is quite an interesting feature from a technical point of view, so I'll talk about this in a bit more depth once R9 is out.
I have a few glitches in the new UI to fix (e.g. audio can't be disabled once the rom has started, controller can't be remapped once the rom has started).
I need to hook up a few things to the new UI (e.g. 'reset to main menu', 'take screenshot' etc)

As you can see, it's quite a short list now, so I'm still on track for releasing R9 by next weekend :)

-StrmnNrmn

Audio Support in Daedalus R9

2007-02-14T21:29:00.000Z

Last week I said that I'd talk a bit about the audio support I've been working on. I want to describe how it was implemented, and continue with what to expect from it in R9 and how it affects performance.

I'd been putting off implementing audio support for a number of reasons. Firstly, I just didn't think that the emulator was running fast enough to spare any extra time doing other work. Secondly, because it wasn't running fast enough, I knew the resulting audio would sound horrible and choppy. Finally, I knew that writing an audio list processor from scratch was going to be very time consuming and error prone.

Maybe it's worth going into a little more detail about that last point.

Most audio and graphics processing on the N64 is handled through audio lists and display lists (very similar to an OpenGL display list). These lists are sequences of simple instructions which are usually constructed by the CPU as the game is running. I used the word 'usually', because it's possible to generate the lists offline, and just execute them at runtime as required.

One way of thinking about the audio and display lists is as a very simple scripting language. Each instruction in the list performs a trivial operation, like copying a block of sample data to another region of memory, interpolating samples from two buffers and storing the result in another and so on. The format of the instructions in the lists has been very carefully designed so that they can be efficiently operated on by the N64's coprocessor, the RSP. The RSP is a very fast processor with SIMD instructions (i.e. instructions which operate on multiple pieces of data - much like SSE on x86 based processors), and it's ideally suited to performing the kind of jobs required in processing audio data or transforming and lighting geometry. The code which executes on the RSP is often called 'microcode'.

The nice thing about audio and display lists is that they can be executed asynchronously by the RSP while the CPU is off doing other work. The CPU just needs to copy a small block of data (describing the task at hand) to the RSP's local memory, and then kick it off. The CPU then goes off doing some other work (updating the game logic for instance.) At some point, the RSP finishes processing the audio or display list, and signals the CPU that it's finished its work through an interrupt. The CPU can then queue up the next available job to the RSP for processing.

There are two ways in which an emulator can handle audio or display lists. The first method is to emulate the RSP at a very low level. This means emulating the RSP as a separate processor, emulating the microcode which has been written to decode and process the audio and display lists. This is what's known as LLE (low-level emulation). The other approach is HLE (high-level emulation). This involves interpreting and processing the audio and display lists manually, ignoring the emulation of the RSP and the microcode entirely.

The HLE approach is typically much, much faster than emulating the task at a low level. This speed comes as a price though, as rather than 'just' writing code to emulate the RSP core, a separate implementation must be written for every task that you want to emulate. This would be fairly simple if there was a single format for audio lists, and a single format for display lists. Unfortunately though, over the years Nintendo released a number of different versions of the microcode controlling these tasks, and many of these changes resulted in different formats for the audio lists and display lists.

Last time I checked, there were 3 major audio list formats, and 5 (6?) major display list formats. Some features of the list formats are similar between versions, but typically they're all very different, and large portions must be reverse engineered from scratch.

So, back to audio support in Daedalus. I had come to the point with implementing various dynarec improvements that I felt it was worth looking into audio to get an idea how how well it would work, and how much of a performance hit there was. As I was saying, one of the reasons I'd been putting off implementing audio support was that I knew that taking a high-level approach was going to be time consuming and error prone. The alternative, low level emulation, just wasn't practical from a performance point of view.

In the end, I decided to see if I could find the source for a PC audio plugin, and adapt this for use with Daedalus. I was fortunate enough to discover that Azimer had made the source for v0.55 of his audio plugin available (Azimer - if you're reading this, please drop me a line to say hello :) My reasoning was that if I could get something up and running in a couple of evenings then I could figure out how much work would be involved in getting it polished. If it looked like it was going to be too much work then I could revert all my changes and at most I'd have wasted just a few hours.

In the end it all went incredibly well. Azimer's source was very self-contained, with just a couple of hooks to implement to get it working. There were a few small issues to solve like having to upsample the output to 44.1KHz (as the PSP output is fixed at this frequency), but nothing that took more than a couple of hours.

So, how does it sound? Well, it's pretty variable. It sounds great in places where there's a high enough framerate to keep the audio buffer full. Mario 64 is pretty good for this - it seems 25fps is a minimum to avoid any choppiness in the output. When the framerate drops lower than this the audio quality does start to suffer significantly. On the plus side, it seems to be decoding everything correctly in all the roms I've tested so for, which means that the quality is only going to improve as I make further improvements to the performance of the emulator.

Which brings me to my next point - how does enabling audio support affect the performance of the emulator? I've not had chance to measure this empirically, but it probably slows things down by about 10-20%. Given that R9 is running about 40-100% faster than R8, you should be able to run R9 with audio and still see a small speedup. In any case, I've added an option to enable or disable the audio in the front-end (this is also accessible from the pause menu while the rom is running).

So, that's just about the story so far with audio support in Daedalus. There's clearly a lot more work to do, but the good news is that audio support is in, and working, and is only going to improve with time. Later this week I'll talk a bit about future improvements, including methods for reducing the impact that audio processing has on performance.

-StrmnNrmn

Revamped UI Sneak Peek

2007-02-13T01:11:00.000Z

Here's a sneak peek of the revamped UI I've been working on:

[Edit - 9:22 AM] Please don't read anything into the list of titles shown in the screenshot above! I haven't been working on compatibility in R9 (with the exception of a few PIF fixes), so it's unlikely that anything which was broken in R8 is now working. Once R9 is released I'll hold a straw poll to see if you want me to focus on compatibility in R10, and if so, which titles.

-StrmnNrmn

The rest of the time...

2007-02-12T23:59:00.000Z

On Thursday I gave this short Daedalus-centric list of things I chose between when I have some free time:

Do some new development on Daedalus
Play games/watch TV/relax
Reply to a few emails/comments, post a new entry here

I gave a long list of stuff I've been working on that represents the first bullet point over the past 5-6 months. I thought it might be interesting to list a few of the things covered by the second bullet point in the same period of time:

Dead Rising
I decided to finish CoD2 on Veteran
I picked up Prey, PE6 and Burnout Revenge preowned
I finally got a Nintendo DS Lite...
...and got hooked on Advance Wars : DS
I started playing more football
Gears of War
I rejoined the gym
I got readdicted to Lumines
I watched Prison Break
Marvel Ultimate Alliance on the PSP
I got a Wii
I changed jobs
Tony Hawk's Project 8
Celebrated Christmas
Visited Spain
Battlestar Galactica S2
Company of Heroes
Trauma Center
Viva Pinata

There's quite a lot of Xbox 360 games on that list. Curse my inexplicable addiction to accruing gamerpoints! Most of the DS and PSP games have just been from the hours spent commuting to and from work - I don't tend to use either much around the house.

By far the most significant item on that list for me was changing jobs. I don't really want to go into too many specific details, so I'll just say that I'm working in games again now and leave it at that. It's nice to have a new platform to explore, and get paid for doing it. I have a nicer commute to work in the morning too. It takes the same time, but I'm travelling against the main flow of people so I can stretch out with my PSP/DS and have a carriage to myself rather than squeezing into an overcrowded train each morning.

Anyway, enough of the offtopic banter! I just wanted to give you some idea of the other things I've been up to in my absence from the blogowebs.

-StrmnNrmn

A few answers

2007-02-11T12:30:00.000Z

A few common questions cropped up in yesterday's post so I thought I'd deal with them here so everyone could see the responses.

Firstly, lots of people were asking about the possibility of moving the audio processing to ME. I'm really keen on doing this, but I'm not very familiar with the ME yet so I need to spend a few hours investigating it before I can figure out how much work is involved. Maybe I can do a few technical posts about the ME as I find out more about it?

A few people were asking about an ingame menu and screen size. gotwake424 said:

will there be an ingame menu? that will let you change the size of the screen and other stuff in game?

xabier:

i have just one question: you have mentioned viewport scaling/screen ratio a few months ago. is that going to be featured in Release 9 of daedalus? and i think that i heard somewhere that it should speed up the emulator a little with the new scaling, is that true?

flyinghippo:

One of your earlier posts showed your progress on implementing a 4:3 screen ratio. Would this possibly have any effect on the framerate?

reuben:

A while ago you noted that you had been working on viewport scaling. Will that be implemented in the upcoming release?

I'm currently working on the in game menu - this is the last main thing I want to squeeze into R9. With this you'll be able to change the screen size while the rom is running, as well as a few other things (toggle audio on/off, swap controls etc).
I doubt that knocking the screen size down will help the framerate all that much, as the framerate is still largely limited by the cost of CPU emulation rather than rendering.

From philip:

Do you have plans to implement frameskipping? That would greatly improve the speed, and shouldn't be too hard to add.

on the rise1:

have you ever thought or messed about putting in frameskipping in the emulator?

Now that audio support is in, I think frameskipping makes a lot more sense. I'll see if I can squeeze this in for R9 too.

yatahaze:

can Daedalus run under 300mhz? would that boost those numbers in the table even more?

Unfortunately Daedalus is already clocking everything at the maximum frequency, so there won't be an easy win there :(

imitiaz:

Are the rom files you are using zipped or unzipped? Will the extensions of the rom files even matter anymore?

I was using unzipped rom files. The extension shouldn't matter, provided it's recognised (.v64, .z64, .rom etc) Daedalus should always figure out the correct thing to do with a given rom. I suggest you use a tool like RomCenter to manage the naming of all your roms, and extract them to the roms directory on your PSP as required.

sroon said:

Will expansion pack be inplented in your blessed R9?

The expansion pak should already be supported: 'Expansion Pak: Yes' in the Rom Settings screen (just before the rom launches). If it's not working, it's a bug, and it'll be easy to fix.

nick:

Have you always been able to add audio support? Or did you hold it back because of the slow framerate?

I've been holding off because of the framerate - I just thought it would sound horrible. The framerate is still a limiting factor with audio support, I'll talk a bit more about this soon.

jeffrey said:

Is there any official way to support your work? Either through paypal donations or whatever?

No, not currently. To be honest, I'm a bit uncomfortable about accepting money for this. Financial reward has never been a motivating factor for me, I do this because it's an interesting project with lots of juicy technical problems to solve. If I was to ever accept donations, it would be for a specific goal (e.g. if I broke my development psp and it needed replacing, or to pay for hosting/bandwidth etc).

andrew said:

The best update possible for R9 is an icon for the PSP menu.

Yes, I know :) I do like the Pochi Style icons. I emailed him asking for permission to use them with Daedalus, if I get the go ahead I'll bundle them with R9 by default.

A few people were asking for videos of the work in progress. I'm not all that keen on doing this as I'd rather spend the time getting the final few features in place and releasing early rather than spending the time making videos. You'll be able to play with it yourselves soon enough :)

As for a release date, I'm going skiing for a week on the 25th February, and I'd like to have R9 out before then.

-StrmnNrmn

Speedup Details

2007-02-10T14:30:00.001Z

In my long-overdue update on Thursday I explained how some of the work I've been doing on the dynarec engine has produced a significant speedup. This post will give a few numbers to give an idea of what you can expect in R9.

The table below shows the framerate for various scenes in R8 with a column showing the framerate for the build I'm currently testing effectively R9). The final column shows the relative speedup:

R8 framerate	Current framerate	Speedup
8	12	x1.5
38	52	x1.4
18	25	x1.4
18	24	x1.3
8	13	x1.6
39	55	x1.4
6	10	x1.7
5	9	x1.8
21	27	x1.3
9	11	x1.2
17	23	x1.4
16	33	x2.1
12	24	x2.0
12	20	x1.7
22	35	x1.6
21	27	x1.3
10	18	x1.8
75	90	x1.2
20	25	x1.3
21	29	x1.4

Clearly there's a significant improvement in framerate. On average, games are running about 40% faster, but in many cases the framerate has almost doubled. Subjectively, the difference means that many games are feeling a lot more responsive and playable now. Anything over 20fps 'feels' pretty good, but my long-term goal is to get this up to 30fps for as many titles as possible.

I noticed a couple of interesting differences between the two builds when running the tests, and you can see some of these in the new screenshots. Firstly, notice that the shadows in Super Mario 64 are all nice and round. This is due to the 'mirrored texture support' that I mentioned in Thursday's update (this also fixes the star that opens over Mario's head in the title sequence).

Secondly, the jerky/shaky screen that was affecting Mario Kart 64 now seems to be fixed. I'm not quite sure what was causing this, but I'm glad it's fixed :)

Next, notice that the text is Quest 64 is now fixed. In R8 this was horribly corrupted. This is due to the fixing a few texture conversion bugs as I was introducing proper support for 16 bit textures.

Finally, the texture on the floor in Quest 64 is now fixed. Again, I'm not totally sure what change is responsible for this, but it's nice to see it working correctly.

One final thing to note is that these figures were obtained by running the emulator with 'optimal' settings. For the current build, this includes disabling audio output. I'll talk a bit about audio support soon, including a bit about its impact on performance.

-StrmnNrmn

Comment Moderation

2007-02-10T10:22:00.000Z

You might have noticed that I've introduced a new policy of moderating comments for each post. There are a couple of reasons for this, but mainly this is because I wanted to have some control over the nature of the debate following each post.

In the past my posts have fallen into two main categories - general Daedalus updates, and more technical posts about some of the specifics. For the techincal posts I want to encourage more detailed discussion, so I'l only be approving comments which I believe are going to help stimulate this. This means I'll be rejecting comments about unrelated issues ("when is the next release?", "make it go faster please" etc). Please don't take this personally!

For general updates, the policy will be pretty much the same as it has been, i.e. anything goes - although I'll still be rejecting duplicate posts or anything totally off topic.

Cheers
-StrmnNrmn

Behold! An update!

2007-02-08T08:40:00.000Z

Wow, it's been a long time since the last update. A really long time. How did that happen?

I've always found it quite hard to find the time to update the blog. Usually when I have some free time in the evenings (that's free time spent doing things other than eating, socialising, and getting stuff ready for work), the choices I have are:

Do some new development on Daedalus
Play games/watch TV/relax
Reply to a few emails/comments, post a new entry here

Unfortunately over the past half year or so the first two bullet points have won out. So, apologies for neglecting the 'outside world' for so long. On the plus side, the existance of the first bullet points means that I have lots of exciting new developments to talk about over the next few days :)

I'm going to finish off this reintroduction with a broad overview of some of the stuff I've been working on. This is all stuff that will be present in R9, which I'd like to release this month.

Added support for RGBA 4444 and 5551 textures, saving a bunch of memory in the front end.
Tidied up all the texture conversion code, fixing a few bugs in the process
Fixed the width/height of FillRect calls in 1 and 2 cycle mode (fixed a few small graphical issues)
Fixed a blending bug (fixed a few small graphical issues)
Use 16-bit textures on the PSP to represent 16-bit N64 textures. Saves time converting, saves memory, and faster rendering
Added mirrored texture support (this fixes lots of small graphical glitches)
Fixed a LoadTile bug, allowing a couple of hacks to be removed (this also fixes various small graphical glitches)
Added some new blend modes for various roms
Fixed the Tri2 command for F3DLX microcodes
Fixed a bug in busy-wait detection (this wasn't working correctly with dynarec code, net result is a small speedup)
Fixed a few dynarec stability issues (relating to exceptions occuring mid-trace)
Added audio support :)
Added the ability to dump textures (developer builds only at the moment)
Fixed screenshots. Again.
Implemented cmp.s, cvt.s, cvt.w, mtc1, mfc1, bc1f, bc1t, j, cfc1, ctc1, daddu, trunc.w.s, bc1t, bc1f, bc1tl, bcifl, bnel, beql, blezl, bgtzl, bltzl, blezl in dynarec (this gives a decent speedup)
Avoid setting the branch delay flag and current PC in generated dynarec code unless absolutely necessary (this gives another small speedup)
Much better memory access handling in dynamically recompiled code (this gives a BIG speedup :)
Use a second code buffer for generated dynarec code, to avoid polluting the instruction cache (this gives another small speedup)
Further improve the memory access handling in generated dynarec code (another small speedup)
Fix register usage analysis for lwc1/swc1/mfc1/mtc1 which was preventing base registers used in these instructions from being cached (another small speedup)
Have compensation blocks restore nobbled registers, so on-trace code does't need to reload (another small speedup)

There's quite a lot in that list, so I highlighted the two most significant points. In summary R9 will be much faster, with audio support. I'll write a bit more about these changes in particular over the next few days (promise!)

-StrmnNrmn

PIF fixes

2006-09-25T20:56:00.000+01:00

It's about time I posted an update with news of some of the things I've been working on! Annoyingly the '.' key on my keyboard has decided to stop working so apologies in advance for any dodgy punctuation :)

I've been having a look at fixing a couple of issues related to the way that Daedalus handles the N64 PIF (peripheral interface) emulation. The PIF is responsible for a number of different functions, including:

Reading the controller status

Reading/writing to the eeprom

Reading/writing to the controller mempak

Access to the PIF is controlled through a 64 byte region of memory. Writing to this area triggers the PIF to interpret the block of data as a sequence of commands (such as those listed above), and the CPU can read back from this region to obtain the results.

Correctly handling the way the block is formatted is key to emuating the PIF accurately. Over the years I've rewritten this code several times as I've fixed bugs, each time fixing certain incorrect assumptions made during the previous version. Usually these assumptions were made on incredibly useful, but incomplete information (such as early docs from LaC (*waves*) ) which described how to use the PIF rather than how to emulate it. Unfortunately there was lots of gaps in this information and so I'd keep finding roms that used the PIF is various ways that I'd not taken into account.

A few years ago I stumbled across something rather amazing - a document which described the PIF hardware in great detail. Not only was it very thorough - including details on all the various formatting commands I'd spent hours reverse engineering - it also included an insane amount of detail on things such as the chip timings and the even method by which the PIF is used as a 'security system' to lock out pirated roms.

What was this document? Did I find it tucked away on some obscure N64 hacking site? No - it was US Patent 6,394,905, filed by Nintendo in September 2000. Genius!

There are actually a whole series of N64 patents (see 5,426,762 and 4,799,635 for a couple of other similar examples.) It's not all good news though because unfortunately they're all written in a horribly convulted form of Legalese:

There are six JoyChannels available in the present exemplary embodiment. Each Channel's transmit data and receive data byte sizes are all independently assignable by setting size parameters. In the exemplary embodiment, all six channels size parameter setups are required, whether they are used or not.

Ouch.

This is the statement I spotted a couple of weeks ago that explained why one of the previous assumptions I'd made wasn't working in all cases:

If the 64 bit CPU 100 wants to change JoyChannel's Tx/RxData assignment, a 32 bit format flag is used, where a certain bit(s) specify the desired format. For example, when Wr64B or Wr4B is issued when this flag is "1", PIF executes each JoyChannel's Tx/RxData assignment based on each channel's Tx/Rx Size. In other words, unless this flag is set to "1" with Wr64B or Wr4B, Tx/RxData area assignment does not change. After Tx/RxData assignment, this flag is reset to "0" automatically.

After painfully wading through the text, it's basically saying that if you write a '1' to the last byte of the PIF block, you need to reformat all the channels. Otherwise you just assume the same formatting as the previous command.

The bug that I've since fixed was actually caused by two problems. Firstly, I was reformatting the channels regardless of how this last byte was set. I'd assumed that it was always set to '1' by the CPU to indicate that a command was ready, and set to '0' by the PIF when it was finished executing. In a few roms I was seeing '0' being written, but I didn't know why. Quite often when I saw them do this they'd hang shortly aftwerwards.

The other problem that contributed to the bug was that I was accidentally overwritting the 'Tx/RxData assignment' area with 0 as I was processing the PIF block (actually, I was clearing the top 4 bits of each byte, rather than just the top 2). This meant that when I reformatted the Tx/RxData assigments the areas were smaller than expected, so the PIF handling code would abort and return with failure.

These two problems combined to cause certain roms to get confused and hang when trying to access the mempak. The total fix was a few dozen lines of code to separate out the PIF formatting from the command execution, and a single-line fix for the second issue. All the roms I found exhibiting this issue now make further progress (hooray!) There may well be other issues that have been resolved with this fix too :)

It's bedtime for me now (well, maybe a little Dead Rising on the 360 first :) I'll try and get back into the habit of updating a bit more often from this week on. Sorry if I've not replied to your email - it's not personal, it's just me being rubbish.

-StrmnNrmn

I'm still alive

2006-09-17T21:44:00.000+01:00

I just wanted to apologise for the lack of updates recently. In between commitments at work and at home I've not had much time to work on Daedalus over the past couple of weeks. Fortunately things are quietening down again so I should have some free time to work on the next release of the emulator this week. Rest assured I'll keep you up to date with all the new developments.

-StrmnNrmn

Viewport scaling

2006-09-06T22:17:00.000+01:00

It's been a fairly slow week for progress on Daedalus. I've had a few busy days with work, and I was away over the weekend so I've not had much time to work on Daedalus since my last update.

One thing I have managed to implement is viewport scaling however. After the previous release I received an email from Chris Meyer-Rassow which had a couple of interesting points. He suggested that I should have a look at providing a setting to allow the emulator to run with an aspect ratio of 4:3, rather than strecthing everything to fit the PSP's 16:9 (or 15.88236:9 to be accurate :)

I had been meaning to add this option for some time, and as it was only a small change I decided to implement this feature for the next release. I've added 3 different modes, as shown the in screenshots below. The first mode simply scales the graphics up to fit the PSP's screen (this is no different from the current release of the emulator):

This renders at 480x272. Notice how the vertial lines for the 't' and 'f' characters look slightly too heavy. This is as a result of scaling the graphics up to fit the PSP's screen. (As an aside, this screenshot clearly shows another issue that I need to address - the zfighting which is clearly visible in the carpet. I have a couple of ideas for fixing this.)

The next shot shows the same scene with the new unscaled 4:3 viewport setting:

This renders at 320x240, and so avoids scaling up any of the graphics. You can see that the problems with the 'f' and 't characters has gone. On the downside, there's a lot of 'wasted' space around the screen.

The final settings shows the new scaled 4:3 viewport setting:

This maintains a 4:3 ratio (so we maintain the correct aspect ratio), but scales things up to 362x272 to make full use of the screen's height. We waste a little less space with this mode, but some of the original problems with the text are still visible.

In the end all three options are a trade off between making full use of the screen and quality. In the next release it will be possible to adjust this setting as the emulator is running so you can pick whichever one looks best for the rom you're currently running.

As a result of doing this work with the viewport, I also fixed a couple of bugs related to how I was emulating the N64's viewport. When I originally wrote the graphics code for the PSP version of Daedalus, I forgot to handle the N64's viewport scaling/translation, which causes problems rendering certain scenes, as demonstrated in Aerogauge below:

Notice how the car is being rendered off-centre (it should be in the top right hand corner). After my viewport fixes, the same scene now looks like this:

The same change also fixes various minor glitches in a number of other roms (including Mariokart and Waverace), so it's a nice bugfix to get in for the next release.

-StrmnNrmn

Display List Debugger

2006-08-30T23:20:00.000+01:00

I've been working on a few new features which I'm eager to talk about, but I thought it would be interesting to give some details about some of the tools I use to help me debug various problems with the emulator.

Some of the hardest problems to identify and fix are various graphical issues that crop up when running certain roms. Sometimes it's unhandled combiner modes (this is what results in the purple-and-black textures seen in so many screenshots). Other times there are black or white polygons, or scrambled textures and so on. Sometimes the screen is just totally black :)

When I'm trying to figure out what's causing a particular problem my first step is to recompile Daedalus with the Display List Debugger enabled. If you've been playing with the source, this is done by setting CFLAGS = $(DEBUG_DLIST_CFLAGS) in the Makefile, and linking in Source/PSPGraphics/DisplayListDebugger.o.

The debugger is accessed by pausing emulation and hitting the right trigger button. You need to have PSPLink set up in order to use it, as I didn't want to clutter up the display with various debbuging output. When the debugger is activated, it keeps the emulator paused and replays the current display list over and over. The first thing is does is dump out a list of all the commands in the display list to a logfile which looks something like this (I've edited it somewhat to create a simple example):


[00066] 0x00214290: 01060040 802143b0 G_GBI1_MTX
    Command: ModelView Load Push Length 64 Address 0x002143b0
     +1.00000     +0.00000     +0.00000     +0.00000
     +0.00000     +1.00000     +0.00000     +0.00000
     +0.00000     +0.00000     +1.00000     +0.00000
     +0.00000   +160.00000     +0.00000     +1.00000

[00067] 0x001c1118: bb000001 ffffffff G_GBI1_TEXTURE
    Level: 0 Tile: 0 enabled
    ScaleS: 0.999985, ScaleT: 0.999985
[00068] 0x001c1120: 04f00100 0a000000 G_GBI0_VTX
    Address 0x001c1000, v0: 0, Num: 16, Length: 0x0100
 #00 Flags: 0x0000 Pos: { 0.000000, 60.000000,-1.000000} 
 #01 Flags: 0x0000 Pos: { 80.000000, 60.000000,-1.000000}
 #02 Flags: 0x0000 Pos: { 80.000000, 80.000000,-1.000000}
[00069] 0x001c1130: bf000000 00000a14 G_GBI1_TRI1
   Tri: 0,1,2

What this is showing is a matrix being loaded (command 0066), texturing being enabled (0067), a bunch of vertices being loaded (0068) and then a triangle being rendered (0069). (That's quite a lot of work to display a single trinangle! In reality the n64 would load up batches of vertices and render multiple triangles at a time.)

The display list debugger also provides a number of other useful features. The first is the Combiner Explorer. This is how it looks in PSPLink:

This displays all the different combiners used in a scene, and allows them to be enabled or disabled individually. When they're disabled, it replaces the triangle with a big green and black texture, like so:

In each of these cases a single combiner was disabled, showing how different combiners are used to achieve different effects in the scene.

This tool is invaluable in debugging combiners as I add them, to ensure that they're doing what I think they're doing.

The Texture Explorer displays all the textures used in the scene. It looks like this in PSPLink:

It allows individual textures to be displayed on the PSP so I can ensure that they're being decoded correctly:

The final function I want to demonstrate is the ability to terminate the display list at a given point. That is, if a display list has 1000 commands, I can stop it after at any point during rendering to see what the scene looks like. The example pasted above shows a snippet of 4 commands from 66-69, typically there may be 3000-5000 commands in a display list - the Mario scene above is composed of 3614 commands.

Being able to stop the display list like this is really useful, because it allows me to see the exact command at which a given triangle in the scene is drawn. Let's say that we're trying to figure out why the triangles making up Mario's feet are coming out in the wrong colour. What we'd do is render the display list command by command until the specific triangle we were interested in appeared on-screen. At this point we'd be able to determine the command number, and cross-reference this with the display list log which was dumped at the beginning. Usually looking a few lines before this point in the log will reveal the source of the problem.

I hope this has provided a little insight into how I go about debugging some of Daedalus' graphical problems. I'll leave you with a sequence of shots showing how Mario 64 looks as it's rendered from start to finish:

-StrmnNrmn

Something for the weekend - R8

2006-08-25T23:21:00.000+01:00

I got back from my trip yesterday and I've spent a few hours today putting together the final changes for Daedalus PSP R8.

You can grab the latest files from SourceForge.

Here's the changelist:


[^] Replaced all uses of sceCtrlReadBufferPositive with sceCtrlPeekBufferPositive.
[^] Various known value optimisations for the dynamic recompilation engine.
[^] Various texture cache optimisations and rendering optimisations.
[+] Implemented a new clipping method which is more efficient and gives better results.
[-] Removed 'tesselate large triangles' setting.
[+] Added option to reset emulator to the main menu.
[^] No longer use index buffers for rendering.
[^] Implement matrix multiplication using VFPU.
[^] Implement vertex transform and lighting code using VFPU.
[^] Implement clipping code using VFPU.
[^] Minor AddTri optimisations.
[^] Free background and font textures while emulator is running to free VRAM.
[!] Fixed bug in default controller config (c-down and dpad-down were broken)

It should be pretty obvious that most of the changes in R8 are optimisations. This build is significantly faster than R7, which is a significant achievement considering how much R7 had achieved in this area. Here's an updated view of the framerate table I introduced a couple of months ago and updated recently:

Scene	R4 fps	R5 fps	R7-beta fps	R8 fps
Mario Head	3	6	8	8
Mario Main Menu	14	25	30	38
Mario Peach Letter	6-7	11	13	18
Mario Flyby (under bridge)	6	10	12	17
Mario In Game	5-6	9	11	15
Mario Kart Nintendo logo	10	23	24	35
Mario Kart Flag	6	11	13	16
Mario Kart Menu	7	11	13	14
Zelda Nintendo Logo	20	23	?	70
Zelda Start Menu	2-3	4	?	8
Zelda Main Menu	10	13	?	40

I think the numbers speak for themselves. What's particularly impressive is that the R8 results are so high, despite having the new clipping code enabled by default. By implementing the triangle clipping code and the transform and lighting code using the PSP's VFPU I've managed to keep the additional cost to a minimum.

With the previous release, I also mentioned a list of things I had planned for R8. I decided to put them on hold while I pursued the various optimisations in R8, so I'll be looking at working on them for the next release.

Have fun - I'm going to wade through the past couple of weeks worth of emails that have built up while I've been putting this build together :)

-StrmnNrmn

Away for a couple of days

2006-08-22T11:04:00.000+01:00

I've made some great progress on getting the new clipping code working with the PSP's VFPU. Actually, so far I've just been working on getting various matrix/vector routines and the transform and lighting (TnL) code working with the VFPU and I'm seeing very good results so far. The TnL code is around 2-3 times as fast running through the VFPU compared to the CPU. This gives around a 0.5-1.0fps speedup in the various roms I've been testing.

Unfortunately I have to put the clipping work on hold until the end of the week as I'm heading home for a few days to see my family. In the meantime, I've answered a few of your comments about clipping on the previous post.

Also, here are a few amusing 'outtakes' as I was trying to get the VFPU TnL code working:

Hmm, something wrong with the indexing I think

Something is definitely wrong with the transform matrix (or else Lakitu is drunk :)

M.C. Escher would be proud

Whoops.

-StrmnNrmn

Triangle Clipping

2006-08-20T16:55:00.000+01:00

After Wednesday's news I wanted to keep everyone up to date with what I've been working on over the past few days.

With Wednesday's changes incorporated, I reprofiled a few roms to see where most of the CPU time was going. Things have changed considerably since I initially talked about deciding what to optimise. Looking at the profiler for Mario 64 the time spent executing display lists is now a much more significant fraction of the total time spent on each frame. Back around R3/R4 only around 20% of the time was spent here. With the latest build display list processing now accounts for around 35-40% of the time. The display list processing hasn't become any slower, it's just becoming more significant as I've optimised the CPU emulation.

One of the settings I mentioned was worth disabling for a speed boost when I released R7 was the 'Tesselate Large Triangles' option. When this setting is enabled, it causes the display list processor to recursively break up large triangles into smaller pieces. This has been necessary to overcome the PSPs poor hardware clipping support; without breaking the triangles up into smaller pieces, the PSP will often fail to render large triangles as shown below:

Super Mario 64 without clipping

The large triangles that make up the floor that Mario is standing on are rejected by the PSP, leaving a large hole where the floor should be. By breaking the triangles into smaller pieces before attempting to render them, it reduces the chance that the PSP will decide to discard them.

There were a few problems with the 'Tesselate Large Triangles' setting which I've been working on overcoming this weekend. Firstly, it's not perfect - there were plenty of cases where visible triangles would still be culled even when they had been subdivided 3-4 times (which generates 27-81 triangles for each input triangle!). This was always quite noticable in games with a relatively low camera, such as racing games. The other big problem with this setting was that it was very slow - often adding over 20ms per frame.

This setting was always intended as a quick fix rather than a long term solution, so I've been looking at fixing both of these problems over the past few days. I started by ripping out all the exisiting polygon clipping and tesselation code and starting from scratch. After a couple of days of hacking I've finally got a replacement system that seems to be clipping everything I've thrown at it perfectly. Here's a shot of the same location in Mario 64:

Super Mario 64 with new clipping code

Now that I have a working version of the code in place, I'm going to look at optimising it. At the moment the new clipping code is roughly as expensive as the tesselation code, but due to the way it's implemented I think it should be much easier to make work with the PSP's VFPU, as I can process batches of vertices in parallel. Ideally I'd like to get this change into the next release, so I'm going to hold off putting the R8 build together until it's ready. I'll let you know how I get on.

-StrmnNrmn

Unexpected optmisations

2006-08-16T22:45:00.000+01:00

One of the things that I find most rewarding about programming is when you discover an unexpected improvement or optimisation by accident. You can spend weeks carefully tuning and optimising code, only to stumble across a glaring inefficiency in your code which you've never spotted before. One quick change and your application is suddenly noticably faster.

In my daily job I rely heavily on debuggers and profilers to discover bottlenecks in the working on the Xbox, Microsoft provided some excellent performance analysis tools (I see they've finally released PIX for Windows). These days I tend to use AQtime as I'm PC based (it's also one of the few profilers I've found that can handle the size of our libraries at work without grinding to a shuddering halt.)

Without these kind of tools it's a lot tougher profiling on the PSP. Over the past few months I've built a number of custom profiling tools into Daedalus to help me figure out where all the time is going, but the numbers I get out tend to be quite vague, and there's usually quite a large margin of error. I think this explains why the unexpected optimisation I've just found went undiscovered for so long.

A couple of days ago I was browsing the ps2dev forums and came across this post. I was about to back out after a quick scan, when I noticed this comment from Soatome:

PeterM wrote:
but one waits for the vblank

...and that's sceCtrlReadBufferPositive (which you're using)
you should use sceCtrlPeekBufferPositive instead.

That's when I realised that when Daedalus was emulating a rom, it was stalling for a frame every time the rom read the status of the pad*. In other words by changing one line of code in Daedalus from


sceCtrlReadBufferPositive


sceCtrlPeekBufferPositive

I could get on average an instant 1fps speedup across all roms. What's more, I knew some roms read from the pad multiple times each frame, so they would see an even great speedup.

Frustratingly I had to wait a couple of days before I could try this out. As I mentioned earlier I'm in the process up moving over to a new PC, and I had just moved Perforce over but hadn't set up the pspsdk, which required Cygwin. Daedalus requires libpng and zlib so I had to download and build them too. Then I had to set up Psplink, PuTTY and a whole host of other tools. You get the picture...

Last night I finally managed to get a new build together with the updated code, and the results were every bit as good as I'd expected. In some cases I had to restart the rom just to make sure I wasn't mistaken. I know most of you just want to see some numbers, so here's a few of my observations:

Mario now runs at at steady 15fps in most places, and around 20fps indoors etc (it reaches over 35fps in the main menu, and close to 30 in some scenes.) Zelda now runs at around 8fps in game, and up to 20fps in certain places. The 'nintendo' logo at the start runs at over 90fps :D The MarioKart Nintendo logo now runs at 30fps, and the main menu (with the flag) runs at a solid 15fps. In game it's a comfortable 12fps. Starfox runs at around 15fps - the intro runs at 25-30fps. Quest64 runs at 20fps.

So all in all it's a pretty amazing improvement for a single-line change. Having said that, I think it would be a mistake to assume that this is an instant fix that will suddenly make everything fully-playable. Although some of the framerates I list above are excellent - faster than an native n64 even - not all roms show this improvement. Don't assume that all roms now run at 15+fps (because they don't.) There's still a lot more work to do to get from a sluggish 8fps to a more playable 15fps (in Zelda for instance). I still need to save a lot more cycles in order to support other features such as sound.

Because this change makes such a big improvement I'm going to try and get another release out sooner rather than later. I don't like releasing builds too often as I think each revision should something worthwhile, but I think this qualifies :) There are a couple of other optimisations I want to get in this build, so while it might be ready this weekend, sometime early next week is more likely. The new features I had planned for this build will have to wait until R9.

As always, I'll keep you posted.

-StrmnNrmn

*This actually reminds me of a funny story from one of the Xbox games I was working on. We were investigating a sudden slowdown that had been appeared a few days previously. Somehow I realised that the framerate doubled when you unplugged all the controllers. As it turned out someone was accidentally reinitialising the USB hub every frame, and removing the all controllers prevented this from happening.

R7 released!

2006-08-13T20:16:00.000+01:00

I've just uploaded R7 to SourceForge. Here's the changelist:


[^] Avoid checking for interrupts in dynarec code in most situations.
[^] Optimise dynarec Load/Store instructions to avoid checking for interrupts directly.
[^] Implemented the remaining 32-bit integer instructions in the dynarec.
[^] Implemented the remaining commong load/store instructions in the dynarec.
[^] Implemented JAL/JR in dynarec.
[^] Optimised various texture cache related features.
[^] Added various known value optimisations to the dynarec engine.
[^] Link together blocks even when they exit with branch likely instructions.
[+] Added option to allow frequency of texture update checks to be reduced.
[+] Added the ability to configure buttons
[!] Fixed a couple of compatibility issues caused by the dynarec.
[!] Fixed a couple of issues related to self-modifying code and the dynarec.
[!] Fixed issues with the framerate counter flickering.

Daedalus R7 for v1.00
Daedalus R7 for v1.50
Daedalus R7 Source

The main emphasis has been on improving the framerate of as many roms as possible, but I've also made some significant fixes to the dynarec engine which should improve compatibility for a few roms where this was causing problems before.

There are two settings you should be aware of if you're looking at getting the fastest possible framerate. The first is on the global settings page (that's the one you see on the main menu as soon as you boot up). You'll want to set 'Tesselate Large Triangles' to No here. The next option that helps boost the framerate is set 'Texture Update Check' to Disabled on the Rom Settings screen. A combination of these two options give a significant speedup in various roms.

In R7 I've also added the ability to define your own custom controller configurations. You can define a new controller mapping by adding a new .ini file to the Daedalus/ControllerConfigs directory. There are a few examples in there already, and I'll look at posting a brief tutorial up here sometime soon. If you come up with a new mapping you think would be useful then email me (my address is in the readme.txt) and I'll post it up here and add it to a later release.

I think R8 is going to continue to focus on improving the framerate. I still have a lot of optimisations I want to get in, and I think these will help improve the framerate even further. I also want to spend a little time improving the front end, as it's getting harder for me to add new settings and options in there. I also want to add an option for changing some of the settings while a rom is running (i.e. I think it's time we had an in-game menu.) Another thing I'll look at for R8 is saving settings between runs of the emulator - this way Daedalus will remember which controller setup you prefer for each rom. Finally I want to add an option to quit back to the main menu without having to restart Daedalus.

Phew! That's quite a big list. I can't guarantee I'll be able to add all that for the next release, but that's what I'm currently aiming for. I think it's more important to try and release regularly (i.e. every 3-4 weeks) rather than try and cram everything into one go, so some of these features might move back to R9 if I slip behind.

My first job though is to move my development environment over from my old PC to the new 'beast'. I've had to put this release together through a Remote Desktop Connection to the old PC and I can't bear to do that any longer. It'll probably take a few days to get everything set up on the new PC, but it should be a lot less painful in the long run :)

-StrmnNrmn

Nearly there

2006-08-13T17:55:00.000+01:00

I've just about finished work on the custom controller configuration. Once I've finished testing everything is working as expected I'll begin the process of putting the release together. This can be quite involved as it requires updating all the documentation, packaging all the necessary files and uploading to SourceForge etc. Hopefully it shouldn't take more than a couple of hours. Next post will be with full details of all the changes and the download links etc.

-StrmnNrmn

R7 close

2006-08-10T23:23:00.000+01:00

I'm getting close to finishing everything I want to get into R7. I've just spent a little time tidying up a few loose ends (little things like the way screenshots are handled). The one last substantial bit of work I want to get done is support for custom controller configs. I think this should be a few hours work, so I expect I'll finish this sometime on Saturday or Sunday, with a release following shortly afterwards.

I got a new PC on Tuesday and this has slowed things down a little bit as I've spent a couple of evenings this week seeing just how stupidly fast it is. This is what I went for in the end:

GIGABYTE GA-965P-DQ6 motherboard

Intel Core 2 Duo E6600 CPU (the X6800 would have been nice, but I couldn't really justify spending over £700 on a processor :)

Corsair Twin2X2048-6400C4 (2GB pair of 800MHz DDR2 SDRAM)

GIGABYTE GV-3D1-7950-RH GeForce 7950 GX2

400GB Western Digital WD4000KS Caviar SE16 (Amusingly its 16MB cache is almost as large as the first hard drive I had on the Amiga :)

I've got it all hooked up to my Dell 2405fpw and it's awesome. It's nice to finally be able to play games at the 2405's native 1920x1200 resolution without it chugging along :D

-StrmnNrmn

Trigonometry Wars

2006-08-06T23:38:00.000+01:00

While you're waiting for R7, my good friend 71M has just released the first version of Trigonometry Wars. It's awesome, check it out!

More R7 Optimisations

2006-08-06T22:27:00.000+01:00

It's been a while since my last post, but I've still been hard at work with various optimisations for Daedalus R7.

Although my main focus is on improving the dynamic recompiler, I've been looking at optimising a couple of other areas that I noticed were fairly expensive. The texture cache is one of the areas that I spent time tuning this week. This cache is used to avoid converting textures from the native n64 formats to psp formats every frame. I made a couple of fixes to improve the hashing function which gives much faster lookups in certain situations (such as tiled backdrops). I also provided an option to change the frequency at which the texture cache checks for updates to the textures. Many roms look fine when this check is entirely disabled, and this can give quite a nice speed boost.

My main focus has continued to be on the dynamic recompiler. I've made a couple more bugfixes in this area. One bugfix involved detecting when roms were using self-modifying code. The fix involved dumping the contents of the dynarec cache so that the code is correctly regenerated for the updated instructions. This fix solves a couple of issues I was seeing with Quest64, and I'm sure it will help improve compatibility with a number of other roms too.

The other dynarec issue I fixed was related to the way I was handling certain types of branch instructions. The MIPS processor has a set of 'branch likely' instructions which work slightly differently to regular branches and so I handle them separately in the dynamic recompiler. It turned out that I had forgotten to link together code fragments when they exited through a branch likely instruction. This fix gives a nice little speedup.

The biggest bit of new development I've been doing on the dynarec is on optimising for various situations where I can determine the contents of a given register at the time I'm compiling the code. As an example, many roms use the following sequence to load an integer value from memory at a specific address:


LUI    $t0, 0x8033      // Load Upper Immediate - i.e. load t0 with 0x80330000
LW     $t0, 0x1234($t0) // Load Word - i.e. load t0 with the value at 0x80331234

Previously I'd generate code for both of these instructions on the PSP. The LUI instruction is easy (if t0 is cached on the PSP then this is just one instruction). The LW is a lot more tricky. I have to call a function to convert the address on the n64 (0x80331234 in this case) to the address in the emulated memory on the PSP. Then I have to read from that address, or trigger an exception in the emulator if the memory address is invalid.

With the changes I've just made, when I encounter the LUI instruction (or other instructions involving loading constant values into registers) I keep track of the fact that I've loaded t0 with 0x80330000. When I come to process the LW instruction, I can now determine that the desired address is 0x80331234. I can then map that address directly to the required location on the PSP, avoiding a function call in the generated code. By avoiding the function call I no longer need to flush cached registers back out to memory. Also, because I can tell in advance that the address lies in RAM (and isn't referencing a hardware register for instance) then I can also omit the code testing for an exception. Finally, in situations like the example above, I can don't need to generate any code for the initial LUI (as the register is immediately overwritten with the loaded value.)

In summary this is a very nice optimisation - it generates fewer instructions (reducing the size of the dynarec code), it avoids unnecessarily flushing out cached registers, it avoids generating exception handling code, and it can eliminate redundant instructions (the initial LUI). In the best case, for 2 source instructions it will generate just 3 output instructions, compared to 12-13 for the unoptimised case.

Unfortunately this approach only works with load and store instructions where the address can be determined in advance, but from the roms I've examined so far around 10-15% of the load/store instructions can be optimised in this way, which is enough to give a measurable benefit.

I'm going to spend the rest of this week seeing which other parts of the dynarec engine can benefit from similar approaches. I have a couple of other features to implement (configurable controllers etc), if that all goes to plan I'll try and prepare R7 for a release next weekend.

-StrmnNrmn

Fixed!

2006-07-29T18:00:00.000+01:00

I'm very pleased to be able to say that I've finally managed to fix the nasty bug I blogged about on Thursday.

I'll go into more details in a later post, but in essence the problem was due to very rare situations where the trace recorder would exit a trace when there was still a branch delay instruction pending. This caused the fragment generator to inadvertently skip the branch instruction, causing the odd behaviour I was seeing.

For reference, here are some updated figures for Super Mario 64 and Mario Kart (initial results are from a previous post). Generally the current changes seem to indicate an overall speedup of 20%-25%, which is great for a few days work. What's even better is that I've still not implemented all the optimisations that I have planned for R7, so hopefully these numbers will look even better soon.

Scene	R4 Framerate (Hz)	R5 Framerate (Hz)	Current Framerate (Hz)
Mario Head	3	6	8
Mario Main Menu	14	25	30
Mario Peach Letter	6-7	11	13
Mario Flyby (under bridge)	6	10	12
Mario In Game	5-6	9	11
Mario Kart Nintendo logo	10	23	24
Mario Kart Flag	6	11	13
Mario Kart Menu	7	11	13

(I'll update with results from Zelda shortly - I have to go to a BBQ now!)

-StrmnNrmn

Captain Morgan's compatibility results

2006-07-27T23:23:00.000+01:00

It looks like Captain Morgan has put a lot of effort into doing compatibility testing with Daedalus R6. Thanks Cap'n! (thanks for your email too - I promise I'll get back to you just as soon as sort this issue out!)

[Update]

Don't miss Wally*Won_Kenobie's R6 compatibility list, which is also excellent. Wally has been collecting missing_mux.txt files for me too, for which I am indebted :)

-StrmnNrmn

A great optimisation/bugfix..

2006-07-27T22:18:00.001+01:00

..with a catch.

This week I've been posting about various speedups I've been making by implementing various opcodes in the new dynarec engine. Although I have implemented most of the commonly used opcodes now, after my previous post I decided to add some temporary logging to the emulator to see how often the remaining unhandled opcodes were being used. Two that immediately jumped out at me were JAL (Jump And Link, which is used to perform a function call) and JR (Jump Register, which is used to return from a function call.)

These two instructions are very heavily used, and I was surprised to realise that I'd not implemented them! They're pretty easy to code - in fact, due to the way I construct the instruction traces that are fed into the dynamic recompiler I could effectively ignore the JAL instruction and JR just required a couple of lines of code.

So far so good. I was expecting a modest speedup - maybe another 2-3% on top of all the previous changes I've made this week. After compiling and running the new code, I was amazed to see an improvement of over 10%! Surprised with the figures I was seeing, I did a full rebuild and checked the results again with several different roms. They all showed the same kind of speedup.

I've been programming (and more importantly debugging) long enough now when I should trust my instincts - call it my programming 'Spider-Sense' tingling if you will, but I knew something didn't quite add up :). In situations like this in the past, rather than taking an unexpected speedup for granted I've spent time investigating the root cause to find out exactly what's going on. At the very least I'll simply satisfy my own curiosity, but often I'll find some useful information along the way too (e.g. other related improvements and optimisations etc.)

So I started looking through the code and rerunning a few roms to try and get a handle on what was causing such a significant improvement. After a short while I realised that all the roms were now generating a lot more potential traces for the dynarec engine to consider for recompiling. This confused me even more, because this behaviour should slow the emulator down rather than speed it up. Another puzzling thing was that the only observable behaviour of my changes should be the speed of emulation - but it looked like my change was somehow changing the flow of execution in the rom.

After bit more head scratching and debugging, I finally realised what had happened. In making my changes, I had inadvertently fixed a bug in the dynarec engine that was causing the recompiled code to jump back out to the interpreter whenever a JAL instruction was encountered! This bug had been in the dynarec engine since the first day or so, but because its only side effect was to slow down the emulator rather than something more obvious (i.e. a crash!) it had remained undetected for a couple of months.

So I had figured out what the reason for the 10% speedup was, and I could finally get to bed safe in the knowledge that I had fixed a nasty, subtle bug along the way. Brilliant!

It was only then that I noticed a couple of new problems that I hadn't seen before: The emulator began hanging in places that had previously been fine - such as Peach's letter at the start of Mario 64. On the occasions the emulator managed to get past that point, I found out that Mario wouldn't move or jump (but strangely the c-buttons and pause menu worked fine)

:(

I've spent the last couple of evenings trying to figure out why fixing one bug is causing another. I've finally managed to find a way of reliably reproducing a hang within a few seconds of starting the emulator up. This is important because my best chance of identifying and fixing the problem is to be able to run the PC build of the emulator with my 'fragment simulator' enabled. The simulator is very slow however (about 100x slower than running the emulator normally), which is why it's important to find a way of reliably reproducing the bug very early on in the emulation.

So that's what I've been up to over the past couple of days, and why I haven't been able to reply to people's emails or comments on this blog. Now that I can reproduce the bug in the fragment simulator I'm confident that I can get to the bottom of it. I'll keep you posted with any developments and try to go through emails/comments just as soon as I've cracked it.

-StrmnNrmn

Further dynarec optimisation

2006-07-26T00:36:00.000+01:00

I've spent the last couple of evenings working on adding support for additional instructions to the dynamic recompiler. With every instruction I add, the generated code becomes a bit more efficient as I can avoid various bookeeping work (such as flushing all the cached registers out to memory.)

I've added code to handle the following ops:

MULT, MULTU (multiply, multiply unsigned)

DIV, DIVU (divide, divide unsigned)

MFLO, MFHI (move from lo/hi)

MTLO, MTHI (move to lo/hi)

LB, LBU (load byte, load byte unsigned)

LH, LHU (load halfword, load halfword unsigned)

So far I'm seeing around a 5-6% speedup with these changes (on top of the 10-12% speedup I talked about on Sunday). I am generating slightly more code as a result of this work, but given the large savings I made over the weekend this isn't much of an issue.

My next job is to look at optimising the remaining load/store instructions - I just have LWU/SB/SH to do (ignoring the 64 bit instructions for now). Once that's done I'm going to have a look at optimising sequences of load/store operations by caching the base address between uses. I think that should give a significant speed up for memory intensive chunks of code.

-StrmnNrmn

A productive weekend

2006-07-23T23:27:00.000+01:00

I've had a fairly productive weekend. I've been working on a few improvements on the dynamic recompiler, and I've managed to both decrease the amount of memory it's using (by approximately 10-12%), and increase the emulator's speed (by around 7-10%).

I don't want to get into too many details just yet, as I'm planning on putting together a more detailed post with all the gory details (and a few graphs :) later in the week.

In a related change, I've also managed to identify and fix an issue (read 'bug') with the dynarec that may have been causing stability problems on v1.0 firmware PSPs. This may explain some of the differences in stability users of the different builds have been seeing.

-StrmnNrmn

Windows CE device emulator source

2006-07-19T23:58:00.000+01:00

For anyone reading this blog with an interest in emulator development, Microsoft have just released their Windows CE device emulator as shared source.

As the post mentions, it includes the source for an ARM -> x86 JIT compiler which makes interesting reading, (take a peek at armcpu.cpp)

-StrmnNrmn

R6 Released

2006-07-19T00:59:00.000+01:00

I've got to keep this short as blogger.com is going down in 5 minutes :(

Change log:

[+] Added over 50 new combiner modes
[+] Added support for c-buttons
[+] Load roms from ms0:\N64 in addition to local roms directory
[!] Fixed backface culling issues
[!] Correctly implemented flipping to avoid flickering with certain roms
[!] Plugged memory leak in texture handling code, fixing various crashes
[!] Fixed issue which caused screenshot function to hang the emulator

You can grab it here.

For R6 I've mostly been focusing on fixing a number of graphical issues (namely adding combiner modes to popular roms). I've also managed to add a couple of nice usability improvements (in particular mapping the c buttons to the dpad, using the circle button to toggle back to the n64 dpad)*. I've also been able to track down a couple of bugs that affected stability.

I've still not decided what to concentrate my attention on for R7. The main areas are:

Speed

Compatibility

Graphics

Usability

These are all quite broad areas, but it would be good to get a feeling for what people are most interested in seeing improved. Any comments would be most appreciated.

-StrmnNrmn

* I should point out that I had dozens of people suggest this to me via email and through comments on this blog, so I can't take any credit for this idea :)

R6 up within the hour..

2006-07-19T00:07:00.000+01:00

I had to pull a long shift at work (14 hours!) so I've only just got in. I'm in the process of rebuilding a release build, updating docs, zipping things etc and should have a new build uploaded by 1am (BST). It looks like blogger.com is down at 5pm (PST) so if I don't post an update soon, check the SourceForge site for the update.

-StrmnNrmn

R6 Tomorrow (hopefully!)

2006-07-17T23:13:00.000+01:00

I don't mean to tease, but I am hoping to release the next build of Daedalus PSP tomorrow. I've spent the last couple of days polishing a number of graphical issues and I need to set myself a target date otherwise I'll just keep tinkering for ages :) I'll have a longer post tomorrow with details of the changes that have made it into R6.

In the meantime, I've answered a few of the most recent questions on the previous comments page.

-StrmnNrmn

Graphical fixes

2006-07-11T22:54:00.000+01:00

Here are a few of the significant graphical fixes I've made so far for R6.

Firstly, I managed to fix the horrible flickering that happened when running various roms (Paper Mario was a good example). It turned out that I was making an assumption that roms executed exactly one display list per frame. I assumed that each display list would clear the screen, render everything, and then wait for the screen to flip. As it turns out, some roms execute multiple display lists per frame. In the case of Paper Mario it executes 2 display lists per frame (one which clears the screen, then another which renders everything). By making sure that I only flip after the second display list executes, I avoid the flickering (the actual solution is a little more involved but this is the general idea).

The next significant glitch I've fixed was to do with backface culling of triangles. Basically, when I ported the graphics engine over from the PC version, I forgot to implement the two or three lines of code which handles this. It was a very small fix, but it corrects a number of significant graphical issues (notably all the walls getting in the way in Quest 64).

Finally, I've managed to track down and fix a significant memory leak in the texture handling code. I believe this was causing many of the random crashes that were occuring when leaving the emulator running for several minutes or more (basically through running out of memory). Before applying the fix I found that the Super Mario 64 would crash within 4-5 minutes. After applying the fix I've been able to run Mario with no problems for over 30 minutes.

I'll keep you posted as to when you can expect a new release. I'm quite excited about the memory leak fix, so I'd like to get a new release out as soon as I can implement some of the other things I promised for R6.

-StrmnNrmn

PS I know I've been crap at replying to emails :( I'm hoping to get this release out and then I'll spend a few hours sorting out my mailbox and replying to various comments here.

Congratulations Italy!

2006-07-09T22:11:00.000+01:00

Congratulations to Italy on their win tonight!

Just a quick note to apologise for the lack of updates recently. I've been busy with work for the past couple of weeks, but hopefully it should be business as usual now. I'll try to post a more interesting update tomorrow or on Tuesday.

-StrmnNrmn

Deciding what to optimise

2006-06-26T22:10:00.000+01:00

Whenever I start to answer questions on the comment pages I always end up going into too much detail for a quick response and end up deciding to put up a new post instead. I hope this isn't too annoying :)

In response to Plans for R6 xiringu and ukcuf16 had a couple of interesting suggestions for performance improvements.

First up, from xiringu:

instead of working with a 300x200 screen, work with only half height 150x200 and then display an empty line every other line to get the final 300x200.

That's an interesting idea - it's a trick that's been used by demo coders for years to get a few extra fps. I'm not sure this is going to provide all that much of a speedup to Daedalus though :( The reason for this is that currently rendering only contributes a small amount to the overall cost of each frame, so even if rendering time was totally eliminated, the framerate wouldn't change much. As an example, let's take something like Zelda which currently runs at around 4 fps. At 4fps it means each frame takes 1000/4 = 250 milliseconds to render each frame, which is broken down something like this:

CPU emulation: 200 ms
Display list parsing: 40 ms
Rendering: 10 ms
Total: 200 + 40 + 10 = 250 ms (i.e. 1000/250 = 4fps)

Assuming that we could totally eliminate the rendering time, this would now look like:

CPU emulation: 200 ms
Display list parsing: 40 ms
Rendering: 0 ms (no cost)
Total: 200 + 40 = 240 ms (i.e. 1000/240 = 4.17fps)

So the very best we could hope for in this case would be a .17fps improvement in the framerate :(

ukcuf16 wrote:

Just wanted to ask if there is ever going to be frame skip in later versions :)

What ukcuf16 is suggesting is that the emulator renders one frame, then skips the next. Alternating frames like this should halve the cost of rendering, at the cost of making the framerate a little less smooth.

Again, this is an interesting idea, but I don't really see this having much impact on the framerate as things stand at the moment. Working out the potential speedup is a little more complicated, as we have to take the average time over two frames. The numbers look something like this:

Frame1 CPU emulation: 200 ms
Frame1 Display list parsing: 40 ms
Frame1 Rendering: 10 ms
Frame2 CPU emulation: 200 ms
Frame2 Display list parsing: 0 ms (skipped)
Frame2 Rendering: 0 ms (skipped)
Total: 200 + 40 + 10 + 200 = 450 ms
Average: 450 / 2 = 225 ms (i.e. 1000/225 = 4.44fps)

So even implementing a frame skip mechanism would only give a tiny 0.5fps speedup.

To take this example to its ultimate conclusion, let's assume that I could somehow eliminate the entire cost of display list parsing and rendering:

CPU emulation: 200 ms
Display list parsing: 0 ms (no cost)
Rendering: 0 ms (no cost)
Total: 200 ms (i.e. 1000/200 = 5fps)

Even if I could somehow (magically) reduce the cost of rendering to 0 milliseconds, we'd still only see a 1fps speedup. However, if I can halve the cost of CPU emulation (which is much more likely given the speedups already seen with the new dynarec engine) this is what the calculations look like:

CPU emulation: 100 ms (now twice as fast)
Display list parsing: 40 ms
Rendering: 10 ms
Total: 100 + 40 + 10 = 150 ms (i.e. 1000/150 = 6.66fps)

At the moment I feel that there are more gains to come from optimising the CPU emulation, which is why I've been concentrating on this area recently. As the cost of CPU emulation falls relative to rendering then the ideas suggested by xiringu and ukcug16 will start to become more attractive.

-StrmnNrmn

Source code rant - update

2006-06-22T23:08:00.000+01:00

I was going to post these responses on the comments page, but I was worried that they'd get buried and I have a few important points to make.

From laxer3a:

Now you start to see why the TYL emu source was released shifted by one version from the bin. :-)

I was thinking about doing this, but it's important that people are able to tinker with the source as they please. I usually only ever have the time to refresh the CVS depot when I release anyway, but if other people get involved in the project then this will need to happen more regularly.

gregnoid wrote:

Naa, this pre-release is just a fake !
Becaus PspMonkey had not compiled this.

I need to make it clear I was ranting about PSdonkey, not PSmonkey. I have a lot of respect for PSmonkey and I wouldn't want people to think I was criticising him. It's unfortunate that so many people confuse the two names. Remember: donkey = large four-legged member of the horse family (likes hay, sombreros etc). Monkey = amusing, cheeky primate (likes bananas, mischief, etc) :)

psdonkey said:

About the pre R5 build that I made. Yes I did change a couple of minor things in the source code and things seemed to run a tad bit better. However, after reviewing your updated R5 release, none of the changes that I made in the other build had any effect in this new R5 build that you released. In fact most of what I did was clean up some of the excess code and I can see that you already did this in your R5 release.

I appreciate you clearing up the situation and making your source available - thanks for doing this. I really wasn't expecting to see this happen, so accept my apologies for the criticism I levied in my previous post. I had a bit of a Hulk rage going on and it wasn't really justified.

You make a really good point about having a shared directory for roms between Daedalus and Monkey64 - I'll look at rolling this change into the next official release (R6). If you're really keen on helping contribute to Daedalus then I think you should drop me an email and we can talk about the possibility adding you as a contributor on sourceforge.

-StrmNrmn

Plans for R6

2006-06-22T22:31:00.000+01:00

I'm back from Spain now. I had a great time in Barcelona, it's a bit of a shame to be back :)

I'm planning to have quite a quick turnaround on for the next release, i.e. hopefully I'll have something ready by the end of next week, or early July. I want to concentrate on fixing a bunch of graphical issues (adding new combine modes to fix various pink+black textures etc). I'm also going to look at reducing memory requirements - I think the stability problems associated with running the emulator with dynarec for an extended period of time are a result of running out of memory. This should also help to improve the Expansion Pak support. If I get enough time I'll look at adding support for configuring the controls on a rom by rom basis. Finally, I also want to look at improving savegame support.

-StrmnNrmn

PS Congrats Ghana + Australia :D

Away for a few days

2006-06-16T09:42:00.000+01:00

I'm going to Spain for a few days to celebrate a friend's birthday. I'll be back on Monday sometime, so I'll try and respond to various questions/issues about the R5 release then.

Buenos nachos! :)

PSdonkey's build

2006-06-15T01:05:00.000+01:00

PSdonkey made this comment when releasing a pre-release of R5 last week:

I went ahead and compiled the new source for everyone and also added a couple of minor changes to the source for speed improvements.

As I have no way of getting in touch with him directly, I'd like to ask him publicly if he could forward me a set of diffs for the 'speed improvements' he applied. Not just because this is a requirement of the GPL (the license under which the Daedalus PSP source is made available), but because I think it would be beneficial to the project to apply these changes to the main source tree. Having said that, I suspect PSdonkey might simply have been attempting to take partial credit for several weeks development work. I'll let you know if I receive any diffs...

Daedalus PSP R5

2006-06-15T00:49:00.000+01:00

I've just uploaded the R5 release to sourceforge. Here's the changelist:

[+] New DynaRec engine, resulting in significant performance improvements
[+] New front end - ability to toggle a couple of options (more to come)
[+] Save game first pass (eeprom4k, eeprom16k and mempak)
[^] Various interpreting engine optimisations
[~] Use .png fileformat for background images, save ~380KB
[~] Stripped out unnecessary code, save ~250KB

By far the most substantial change was the addition of the new dynarec engine. As detailed in previous posts, this is still some way from completion but is already providing significant benefits (around a 2x increase in speed in many roms).

I've also added the groundwork for a new front end and implemented a first-pass of the savegame system. The savegame support isn't fully tested so I'm expecting a few teething problems - please post any bug reports on the sourceforge site (preferably!), the comments page or email me (check the readme.txt..)

I'm not too sure what I want to concentrate on next. It's been over a month since the last release and I think that it would be a good idea to knock out the next few releases in quick succession, to help me pick up some momentum that I've lost. If I aim to do this I'll probably concentrate on some nice (but quick) improvements such as various graphical fixes, savegame support and per-rom control configuration. Any suggestions welcome :)

Linkage:

R5 Source
R5 for v1.00
R5 for v1.50

Brief Update

2006-06-13T23:50:00.000+01:00

This is just a brief update as it's been a while since my last post. I'm hoping to release a new build tomorrow, possibly Thursday at latest. I was planning on making an official release last weekend, but I got sidetracked polishing a few things. I've got a slight bit more to finalise, but there should be a couple of nice little additions since the source drop last week.

Source updated

2006-06-05T23:55:00.000+01:00

Earlier this evening I updated the project CVS repository with the latest version of the code. Normally I only do this when I release a new build, but I know people have been playing with the code and have expressed an interest in seeing the latest developments.

I'm not quite ready to release a new binary yet (still a few more optimisations I want to make and various bugs to fix first), but I'll try and do this within the coming week.

Incidentally, updating the source normally only takes 20 minutes or so, but it took a good couple of hours tonight. Sourceforge updated their CVS service recently (May 12th) and as a result I had to spend a couple of hours updating WinCVS, generating new SSH keys and the like. Hopefully it won't be so painful next time around, or I might just lose the will to live.

As a more general update, I cleared a couple of things from my TODO list sorted this weekend. I'm caching floating point registers for most of the single-precision Cop1 instructions, which are now implemented directly in the dynarec code. I've not timed this in depth yet, but it's shaving 10-20ms/frame off the intro to Mario 64 (Mario's Head), which is particularly FPU heavy (i.e. I'm getting ~160ms/frame rather than ~180ms)

Finally I need to have a good think about how to go about optimising the double-precision floating point performance. As the PSP doesn't have hardware support for double precision floating point this is currently very expensive (i.e. adding 2 doubles on the n64 takes just one instruction - on the psp this balloons to several hundred as it all has to be done in software).

Currently I cheat and cast all the double-precision floats to single-precision values before performing the calculations. Although this is much faster it obviously loses a lot of precision, so I need to be careful it's not going to break any roms. Also even the float->double/double->float conversions are pretty expensive so it's still not an ideal solution. Fortunately not many roms seem to use double-precision maths extensively (presumably because it was relatively expensive on the n64), and where they do use it they don't seem to be too sensitive to the fact that I'm throwing most of their mantissa away :)

Some initial benchmarks

2006-05-31T22:08:00.000+01:00

I've been really busy working on the new dynarec engine, so I've not been posting as frequently as I'd like. I've made a lot of progress in the following areas:

Most integer arithmetic and logical instructions now implemented (i.e I'm now generating optimised assembly for these instructions rather than calling a generic function to handle them

Regsiter caching implemented (although I'm only using a greedy allocation algorithm at the moment, as I've not yet fully implemented the fast linear scan algorithm I talked about in the previous post)

I'm directly linking all direct branches to compiled fragments

I'm linking to all indirect branch targets

So far I'd say I'm around 40-50% through the work on the dynarec engine.

Now for some stats :) The following table compares the framerates at various points (previous framerate is for the R4 release of Daedalus, current framerate is for my most recent development build):

Scene	Previous Framerate (Hz)	Current Framerate (Hz)
Mario Head	3	6
Mario Main Menu	14	25
Mario Peach Letter	6-7	11
Mario Flyby (under bridge)	6	10
Mario In Game	5-6	9
Mario Kart Nintendo logo	10	23
Mario Kart Flag	6	11
Mario Kart Menu	7	11
Zelda Nintendo Logo	20	23
Zelda Start Menu	2-3	4
Zelda Main Menu	10	13

Overall I'd say the dynarec is currently achieving up to a 100% speedup in the roms I've tested, which I'm very excited about. Mario is certainly starting to feel a lot more playable, and the Mario Kart menus are a lot more responsive now.

I specifically included Zelda in the results because I'm not seeing the same kind of results there, so I need to take a closer look at what's going on there (it's quite possible it's just using a few of the arithmetic and logical ops I've not spent time optimising yet).

A twofold improvement in framerate is pretty good, but I now think I can do a lot better. Here's the list of things I currently have on my 'TODO' list:

Fully implement all the remaining integer ops (including all the 64 bit instructions)

Finalise implementation of the fast linear scan register allocation algorithm

Keep track of 'known' values for specific registers and use this to optimise the generated code (e.g. most of the time the top half of the N64's 64 bit registers is just sign extended from the lower half)

Cache the memory location pointer to by the N64 stack pointer (SP) and optimise load/stores using this register as a base pointer

Optimise all memory access instructions (currently all the cached registers get flushed for all memory accesses other than LW/SW/LWC1 and SWC1)

Detect and optimise 'busy wait' loops (e.g. many roms sit in a tight loop waiting for the next vertical blank interrupt to fire which is just wasting cycles on the PSP)

Implement all the branching instructions (I've currently only implemented BNE, BEQ, BLEZ and BGTZ)

Implement instructions and register caching for all the cop1 (floating point coprocessor) instructions. (I think this will give a huge speedup.)

Although the list is quite short, there's quite a lot of work there. What I'm quite excited about is that I think these changes will start to provide significant speedups as they're implemented. I don't want to get too far ahead of myself, but I'm starting to feel that certain roms are going to be very playable in the not too distant future.

I'm going to try and release a new version of the emulator soon. Unfortunately it's probably not going to be this weekend (due to various social commitments); towards the end of the following week is more likely. I'd certainly like to get a version released before the World Cup starts and all my free time is taken up watching football :)

-StrmnNrmn

A few more details

2006-05-23T22:56:00.000+01:00

Laxer3A (of SnesTYL fame) made an insightful point in the comments page of the previous post (I hope he doesn't mind me quoting him):

What you are generating actually seems more like "threaded code" to me than actually a real dynarec.

I entirely agree with his description "threaded code" for the way I'm approaching the new dynarec engine. I want to stress tha this is just the early stages. The intention is to develop a stable platform from which I can incrementally move towards what would be considered more conventional dynamic code generation. I want (and now have) a nice solid platform from which I can implement things in chunks of 2-3 hours, which I can easily fit into an evening after work.

So I'm currently in the process of replacing generic calls to handle individual opcodes with specialised code which avoids the function call overhead and can hardcode register locations and immediate values. I can also optimise certain things very well. As an example there is no 'mov' instruction on the MIPS architecture so you quite often see ops like 'or a0, a1, r0' (which just ORs the value in a1 with 0 and stores the result in a0). I can write the code to handle OR to simplify this particular situation by just directly copying the contents of register a1 to a0, and therefore avoid the logical operation altogether.

As another example, here's the code I wrote last night to handle LUI (the operation to load a 16 bit value into the upper half of the low-32 bits of the N64 register):

LUI( PspReg_T0, immediate );
SetVar( &gGPR[rt]._u32[0], PspReg_T0 );

if (immediate >= 0)
{
SetVar( &gGPR[rt]._u32[1], PspReg_R0 ); // Clear tops bits
}
else
{
SRA( PspReg_T1, PspReg_T0, 0x1f );
SetVar( &gGPR[rt]._u32[1], PspReg_T1 ); // Set top bits
}

In the code I talked about on Sunday, handling this instruction would involve 13 ops: 2 to load the value of the opcode into the argument register, and another to call the 10 op-long function 'R4300_LUI' (Daedalus's instruction handler for LUI).

With the code above this is reduced to 4 ops in the worst case (if the immediate value is negative), or just 3 ops if the value is positive. Also, there is no branching. To give a speicifc example, this N64 opcode:

LUI at, 0x8034

now causes this PSP code to be generated:

LUI t0, 0x8034
SW t0, 8(s0) ; s0 points to the emulated register set
SRA t1, t0, 0x1f
SW t1, 12(s0)

My intention is to spend the next few days reimplementing the most commonly used opcodes in this way. By that point I think the major overhead will shift from the cost of all of the function calls to the generic handlers to the cost of storing loading the emulated registers each time they're referenced (you'll notice in the snippet above I call SW twice - once for each half of the 64 bit N64 register.)

From previous experience, register caching is where the real speedups come from with dynamic recompilation. Memory accesses are typically an order of magnitude slower than register access so anything I can do to avoid them in the recompiled code will be a huge improvement.

If anyone is curious, I've been reading these two papers on fast register allocation for dynamic code generation:

Linear Scan Register Allocation - Poletto, Sarkar. 1999
A fast, memory-efficient register allocation framework for embedded systems - Thammanur, Pande. 2004

-StrmnNrmn

[Edit 23:40 - fix markup]

DynaRec status

2006-05-21T22:28:00.000+01:00

Just a quick update on the dynarec status, as I know a lot of people are more interested in this than the grizly details of branch delay instructions :)

Last weekend (13/14 May) I managed to assemble the fragment buffers into native x86 code, and execute this dynamically. I spent some time debating whether to target MIPS or Intel initially, but I decided that it would be a lot easier for me to debug the code generation on the PC than it would be to debug code gen on the PSP.

In the end I'm glad I started with the PC as it allowed me to fix a number of hairy problems without going down the torturous path of debugging self modifying code on the PSP with just a few printf() statements to help track down any problems.

To start with on the x86 code generation, all I did was convert my fragment simulator loop directly into assembly. So the generated code for each instruction in the fragment looked something like this:

set current pc
set branch delay flag
get op code in ECX
call handler for specified op code (from R4300.cpp)
if ( exception set ) exit to exception handler
if ( branch instruction and branch taken ) exit to branch handler

So a fragment with 100 instructions in would have this block repeated 100 times (with different pc, delay flag constants etc).

This generated a lot of assembly (i.e. 200KB or so of N64 instructions would generate over 4MB of x86 assembly, i.e. an expansion of around 2000%). At this point I wasn't interested in performance though - I wanted to make sure that I was preserving the behaviour of the fragment simulator as much as possible. The exception and branch handlers mentioned in the pseudo code above warrant more detailed description, but I'll leave that for another post.

At this point I spent a few hours debugging, but generally everything was working pretty well. The emulator was currently running around the same speed with 'dynarec' enabled as with it disabled (I use quotes because there isn't really much 'dynamic' about this code yet).

I spent the rest of the weekend and the early part of last week trying to optimise the generated assembly and see what I could get away with removing. One of the first things to go was setting the program counter before executing each instruction. The only instructions that need to know this tend to be branching instructions (which are relative and need to know the current PC to work out their target address) and other instructions that can potentially fire exceptions. The vast majority of instructions don't need to know the current PC though (e.g. arithmetic ops, logical ops etc).

Next I had a look at reworking things so I only needed to explicitly set the branch delay flag if a branch delay slot was actually active. I made the precondition that the branch delay slot was always clear, and explicitly set/cleared it when I knew the state needed to change.

Finally I removed exception handling from all the instructions I knew to be safe. For instance, I know ANDI (and immediate) can never throw an exception. As I only perform counter updates at the end of the block, an exception can never be fired when executing this instruction.

After all these changes I had an instruction execution block which looked something like this:

if ( pc needed ) set current pc
if ( branch delay instruction )set branch delay flag
get op code in ECX
call handler for specified op code (from R4300.cpp)
if ( can throw exception and exception set ) exit to exception handler
if ( branch instruction and branch taken ) exit to branch handler

This meant that the vast majority of instructions looked as follows:

get op code in ECX
call handler for specified op code (from R4300.cpp)

So I had nice big fragments like this:

...
get op code in ECX
call handler for specified op code (from R4300.cpp)
get op code in ECX
call handler for specified op code (from R4300.cpp)
get op code in ECX
call handler for specified op code (from R4300.cpp)
get op code in ECX
call handler for specified op code (from R4300.cpp)
...

Essentially I removed the vast majority of the instruction fetch/decoding overhead from the emulation.

With this version of the dynarec, 200KB of N64 code was now generating just 2MB of x86 assembly (i.e. an expansion ratio of around 1000%). The PC version was running around 60% faster with dynarec enabled than with it disabled, which is a pretty significant speedup (although this is still very early in the process).

What's also important is that this is before I've done any real optimisation of the generated code. For each instruction I'm still calling the generic instruction handler which has the overhead of figuring out which source registers to use, which register is the destination etc. The *real* speedup comes from generating code to handle op codes explicitly, as you remove all this decoding overhead along with the overhead of jumping to another function. Once you've removed most of the generic instruction handling you can start looking at caching register values to minimise the amount of memory that's being moved around.

With the PC version up and running fairly successfully, I've spent this weekend getting the PSP code generation working. I don't want to go into too many details (as I want to go into more depth in future posts), but I know people are keen to hear some news about how this is going.

I got the basic code generation working on Saturday morning (thankfully I'd already resolved most of the tricky issues in developing the x86 version the previous weekend). I spent most of Saturday afternoon fixing some really horrible instruction cache related bugs. I'm still not 100% sure I've fixed them, but it seems very stable at the moment. At the moment I'm at the same stage with the PSP version of the dynarec that I was with the PC version last weekend - the code generation is running fine (and executing on the PSP without crashing more importantly :) but I've only just started looking at optimising things. It's still too early to speculate on numbers for the performance improvement it will give. Currently it's running around 10% faster with dynarec enabled, but it's still very early days.

More soon.

-StrmnNrmn

Branch delay instructions

2006-05-21T20:14:00.000+01:00

Well it's been a little longer than I intended since my last post. I've been busy with work, and when I've had free time I've found it hard to drag myself away from the compiler for long enough to post an update :)

In my last post on the subject, I left saying that I was trying to iron out bugs in the fragment 'simulator' and was about to start work on native code generation. I want to pick up from that point, but first I wanted to talk about about branch delay instructions and how they effect the implementation of emulators and the new DynaRec work I've been doing.

The couple of bugs in the fragment simulator were indeed to do with exceptions and interrupts triggering in unexpected places. The problem occurred if an exception was triggered in the branch delay slot following a jump instruction.

In case you're not familiar with the MIPS architecture, after branch instruction has been executed (but before control arrives at the target instruction), the CPU executes the instruction immediately following the branch. So to give an example, this is a block of mips code that calls the function foo( 6, 3 ):


li  a0, 6    # load the first argument
jal foo      # call foo
li  a1, 3    # load the second argument
# the result is returned in v0 here
...

foo:
jr   ra           # return
add  v0, a0, a1   # add the arguments, store result in v0

If you've never read MIPS assembly before this will probably look a little strange.
When we call foo with 'jal foo' (Jump and Link), we don't set the second argument until after the jump to 'foo'! Notice also that we calculate the return value for foo after we return with the Jump Register (JR) instruction.

The reason this code works is because of the branch delay slots. When the call to foo is executed ('jal foo') the CPU keeps going for one more instruction and executes 'li a1, 3'. Control then jumps to the start of 'foo', where the CPU immediately executes 'jr ra', jumping back to where it just came from. Again, the CPU executes the following instruction, calculating the sum of the arguments and returning the result in v0.

Although this seems rather pointless and unnecessarily complicated, it serves a very good purpose. With most modern CPUs the instruction execution is pipelined, which means that the processor breaks down the work into discrete chunks (fetch instruction, decode instruction, execute, commit etc), and executes multiple instructions in parallel. Wikipedia (as always) explains this in a lot more detail.

With many architectures the CPU has to throw away the contents of the pipeline when a branch is executed, as the subsequent instructions may refer to data (register or memory contents) that is invalid until after the call has completed. With certain architectures (including MIPS), the engineers decided that it was wasteful to throw away all this work on every branch, and designed the processor to continue processing the pipeline until the subsequent instruction had completed.

What this means is that when writing code for MIPS processors, you have to be careful that your branch delay slot doesn't have any unintended side effects. For maximum efficiency you also have to be careful to try and do useful work in the branch delay slot (rather than just filling it with a NOP for instance). Normally this isn't an issue as the compiler generates all the code for you, but it's certainly an issue if you're writing assembly. It's also been a very important consideration when I've been writing the code generation for the new DynaRec (I'll cover this in a later post).

So, how do branch delay instructions effect emulators? Although they help pipelined CPUs to improve performance, they require emulators to do bit of extra bookeeping and this slows things down slightly and adds complexity. Every time daedalus interprets an instruction it has to check if a branch was taken, and if so set a flag to indicate that a branch delay instruction is due to be executed. When the branch delay instruction is executed, the flag is cleared and the emulator sets the program counter to the original target of the branch.

This is all fairly straight forward, but complications arise when exceptions fire as a branch delay slot is due to be executed. In the example above, what would happen if an interrupt fired immediately before the branch delay instruction 'li a1, 3' was executed? Normally once the interrupt has been handled, the operating system restores control by jumping to the instruction that was due to be executed, allowing the program to run from that point. If this happened in our example above, a1 would be loaded with the value of 3, but the jump to 'foo' that was originally delayed will never take place. The code would continue running without ever calling 'foo'!

In order to handle this situation, when an exception (or interrupt) is triggered, the CPU sets a flag in the 'cause' register. The operating system keeps track of this flag, along with the program counter where the exception fired and various other bits of information. When it's done handling the exception, the operating system uses this information to allow the CPU to correctly restore control to the code that was originally executing. In our example above, the CPU would see that the branch delay flag is set in the cause register, and restore control to the jal instruction immediately preceeding the instruction where the interrupt occured.

It should be fairly clear that there's quite a lot that must be taken care of by the emulator to make sure that the program executes as intended. This is all fairly simple to keep track of when processing instructions individually, but it becomes more complicated when you start to dynamically recompile the code.

The bugs that I mentioned at the start of this post were caused because I wasn't correctly setting the branch delay flag for instructions causing exceptions in branch delay slots. When I build fragments for the dynamic recompiler I avoid triggering certain types of interrupts (e.g. vertical blank and timer interrupts) in the middle of the fragment to reduce the overhead of having to add the code to handle these situations. Unfortunately there are many other types of exceptions that can occur in the middle of a fragment, such as page faults, I/O completion interrupts etc. It turns out these are very rare, but unfortunately not rare enough to save me from a full day of debugging :(

This was a little more detailed than I was originally planning. Branch delay instructions are quite a simple concept on the surface, but they can cause all sorts of complexities when it comes to dynamic recompilation. Fortunately I feel very confident that I've now fixed all the branch delay related bugs in the dynamic recompiler, so hopefully I shouldn't have to think too much about them again in the near future.

I'll follow up this post with a quick update on the state of the new dynarec engine.

-StrmnNrmn

Wikipedia entry on branch delay slots

Monkey 64 v2.0

2006-05-13T10:23:00.000+01:00

I turn my back for two days and PSMonkey has released v2.0 of his emulator! Congrats PSMonkey - keep up the good work!