I'm working on a PS2 homebrew application (a cheat device similar to my "ps2rd Cheat Device GUI" project... it's the sequel ). The main improvement is that it can load a very large code list (thousands of games) in a few seconds by using a binary database format separated into relevant sections (game titles and offsets to cheat structures at the top, followed by the cheat structures at the end). Anyway I've run into a problem where the application will work fine in PCSX2, but hangs on real hardware. I'm 99% sure it's hanging when I deference a pointer after increment it. My other hunch is that PCSX2's dynarec is simplifying something that would normally cause an exception, but unfortunately the interpreter appears to be broken on new releases so I can't confirm this. dbBuff points to the first byte of the database, which is already loaded before this function is called. I've confirmed where it's hanging by displaying debug messages on the screen using gsKit. The line that it hangs on is in bold. Here's a snippet of the code: edit: This might be easier to read: http://pastie.org/9545296 edit2: The database spec. might help too: http://pastie.org/9545305 Right now this way of searching through the database is pretty inefficient (it compares each game title until it finds a match, which means finding a game name at the end of the database will take several seconds). But I'm just frustrated that it's freezing here. I can provide more/all source code if anyone is willing to take a closer look. I realize this isn't much of a development forum, but maybe someone can shed light on why this may be happening. Thanks!
Looks fine at first glance, can't see what would go wrong unless maybe you're eventually going out of bounds (with different behavior on emu and HW). Possibly an off-by-one in dbHeader->numTitles?
Possibly, but I don't think so. One detail I forgot to mention: on real hardware, this function only crashes after the first time it's called from what I've noticed. The first time it's called, it'll work as it should without crashing.
I assume the LHU generated as part of "... = *(u16*)dbTitleBuffer" causes an address error exception. How do you guarantee that dbTitleBuffer is always even at this point? I did not see any alignment checks or other logic that would ensure that... Remember that the MIPS, in contrast to your x86, absolutely hates unaligned accesses. You may want to try reading both bytes of the u16 separately, then reconstruct the value yourself (memcpy would be overkill). It should also be possible to use a struct with an u16 field and something like __attribute__((packed)) on it, in order to make the compiler do the dirty work, but unfortunately I do not remember the exact syntax GCC uses for that.
That ended up being the issue, thanks for the suggestion! Because the string for the game name can be any length, the data immediately after it would have a good chance of being misaligned. I've now replaced the original line where it crashed as well as a line under it that would just as likely cause a crash. Here are the new lines: Kind of ugly, but I'm glad GCC didn't try to optimize it to an LHU instruction. Tested it on real hardware and it works like a charm
You also want a faster way to find a game by its title? Try with a 32/64 bit hash and compare that, it will be way faster than strncmp.
Yup, your code is probably causing a (data) bus error. Try setting PCSX2's EE to interpreter mode. You can catch bus errors that way, although some bug within it might cause PCSX2 to get stuck during gsKit initialization... For debugging on real (retail) hardware, go for either Kermit or RDB. Kermit should be more reliable at this point though, although RDB will allow you to use the network port instead. But if it's just a simple checksum that you plan to use, two similar titles with the same characters (which are not in the same order) will end up with the same checksum. Anyway, the EE is quite fast, so wouldn't the use of strncmp consume a negligable amount of time?
Even with a complex hash there is a chance that two strings will have the same hash (known as a collision). So you need to store a linked list of entries with matching hashes and then call strcmp on those. With a good hash algorithm and a low number of entries you are likely to only need to call strcmp on a string once, however you still need to find the linked list of entries. If the data is sorted into strcmp order then another alternative is to use a binary search. You'll call strcmp more than a hashtable but the code will be simpler and it has the other advantage you can display it in order if you wish. I A binary search also has the advantage that strncmp will also find an entry (not necessarily the first, so you have to sequentially scan backwards). Using a hash is terrible if you want to be able to do partial searches because you have to calculate the hash for every single item. Calling your calchashcode() function will have a very similar overhead to just calling strncmp. If the list can be edited at run time then the most balanced solution is to use a linked list. You can use a binary search on a linked list as long as you know the count and have a head and tail pointer. I had to switch to a merge sort when loading millions of records from an ascii file, but if the user is doing the editing then an insertion sort should be fine. Calling strncmp 1000 times is slower than calling it 10 times. In similar situations (it was x86 but in the 90's) there was a measurable improvement. However I probably had thousands of entries and was doing something like tens of thousands of lookups. My conclusion was that with strcmp you have to fetch data from ram and then stall until it arrives to make a comparison, but the only way to measure it is to write the code and run it on real hardware.
I'd just keep all non-string data as structs, and grouped together by type, with offsets into a stringdata area at the end of the db instead of 'inside' each entry. That'd allow e.g. using a simple binary search, as well as enable the compiler to do the right thing with regards to struct member alignment.
If you have multiple strings then that is the way to do it. If there is one string then you can use a struct with a char array at the end, but only allocate enough ram to contain the struct and the string. If you pad it so that the struct starts on an even boundary it will cost 0.5 bytes on average, while using a pointer will always cost 4 bytes. If you're storing this on disk in the same format then that will probably mean you won't want to store pointers anyway.
