Wednesday, July 04, 2007

Daedalus disinformation

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!

Wednesday, June 27, 2007

Daedalus PSP R12 Released

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

Saturday, June 16, 2007

Multiplayer Thoughts

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

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

Thursday, June 14, 2007

Tracking down the SSB Dynarec Bug - Part 2

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

Tuesday, June 12, 2007

Tracking down the SSB Dynarec Bug

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

Sunday, June 10, 2007

Super Smash Bros - Dynarec Update

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

Tuesday, May 29, 2007

Status Update

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

Tuesday, May 15, 2007

Dynarec Fixes

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

Thursday, May 10, 2007

Goldeneye Update!

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

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

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

Wednesday, May 09, 2007

Early SSB Progress

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.

Sunday, May 06, 2007

Daedalus R11

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

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

Monday, April 30, 2007

R11 almost ready

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

Sunday, April 22, 2007

R11 Update

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

Thursday, April 05, 2007

R11 Plans

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

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

Monday, April 02, 2007

Daedalus R10

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