Checksum calculation

Here you can talk about anything not covered by the other forums. Please post in the Tech Support forum for problems using Snes9x.
Post Reply
xprism
Snes9x White Belt
Posts: 4
Joined: Sun Nov 15, 2020 7:33 am

Checksum calculation

Post by xprism » Sun Nov 15, 2020 7:41 am

Hi, I'd like to know how snes9x does the calculation of the "Actual checksum" for odd sized SNES roms.

I have a rom hack thats 27MBits and want to know how it is performed. I know how the algorithm works for power-of-2-roms and evenly sized roms (e.g. 10/12/20MBit), but not for snes9x's implementation for odd sized ones. Can't find much info on that while searching the internet either.

I attempted to read the relevant parts of the source code (memmap.cpp) but didn't understand what was going on in the checksum_mirror_sum function.

User avatar
OV2
Official Win32 Porter/Dev
Posts: 668
Joined: Thu Aug 30, 2007 10:15 pm

Re: Checksum calculation

Post by OV2 » Thu Nov 19, 2020 5:00 pm

There is no difference in the calculation for a 20MBit and a 27MBit ROM.

What caused you problems in checksum_mirror_sum? Maybe you can describe how you think it is calculated for a 20Mbit ROM?

xprism
Snes9x White Belt
Posts: 4
Joined: Sun Nov 15, 2020 7:33 am

Re: Checksum calculation

Post by xprism » Fri Nov 20, 2020 11:06 am

OV2 wrote:
Thu Nov 19, 2020 5:00 pm
There is no difference in the calculation for a 20MBit and a 27MBit ROM.

What caused you problems in checksum_mirror_sum? Maybe you can describe how you think it is calculated for a 20Mbit ROM?
From what I understand, for a 20MBit ROM, its (Sum of the first 16MBit) + 4*(Sum of the last 4MBit), remaining 4MBit is added till size of the ROM is a power of 2. However, for a 27MBit ROM, adding 11 to 16 won't give me a power of 2.

As for checksum_mirror_sum, this is what I think its doing:
- mask is defined to be 64MBit in memmap.h, its divided by 2 until its equal to the largest power of 2 within the size of the ROM (not sure about this part, i'm making a guess)
- part 1 of the checksum is calculated normally, with no mirroring, from start to mask
- next_length = remaining part of ROM (length - mask)
- if next_length is nonzero:

Code: Select all

checksum_mirror_sum(start + mask, next_length, mask >> 1);
not sure what happens here

Code: Select all

while (next_length < mask){ next_length += next_length; part2 += part2;}
part2 is added to itself as next_length advances to the end of the ROM

Code: Select all

length = mask + mask;
not sure what's the purpose of this either
- function outputs part1 (non-mirrored part) + part2 (mirrored portion)

User avatar
OV2
Official Win32 Porter/Dev
Posts: 668
Joined: Thu Aug 30, 2007 10:15 pm

Re: Checksum calculation

Post by OV2 » Sun Nov 22, 2020 2:20 pm

For non power of two sizes the idea is to take the largest power of two block, then look at the remaining size in power of two parts, and mirror until you have another block of the largest size. Then the end result is also a power of two.
If you have multiple smaller parts you always mirror the smallest part first until it matches the next largest part, then mirror that whole group. (Which is the same as calculating the checksum recursively, which is what the function does)

So as you said for your 20MBit ROM you have one 16MBit part, then you take the remaining 4Mbit part and mirror this until you have another 16MBit part, and the end result is 32MBit.

For the 27MBit ROM you have one 16MBit part, one 8MBit part, one 2MBit part and one 1MBit part. You take the largest part, then try to create another 16MBit part from the rest. We already have an 8MBit part, so we need to create another 8MBit from the rest. We mirror the 1MBit part, which then matches the 2MBit part, and thus have a 4MBit part. We mirror this resulting 4MBit part, creating a 8MBit part, which combined with the existing 8MBit part creates the 16MBit part we need to end up with 32MBit.
xprism wrote:
Fri Nov 20, 2020 11:06 am
As for checksum_mirror_sum, this is what I think its doing:
- mask is defined to be 64MBit in memmap.h, its divided by 2 until its equal to the largest power of 2 within the size of the ROM (not sure about this part, i'm making a guess)
Correct, that is looking for the largest remaining power of two block.
xprism wrote:
Fri Nov 20, 2020 11:06 am

Code: Select all

checksum_mirror_sum(start + mask, next_length, mask >> 1);
not sure what happens here
It calculates the checksum over the remaining part, starting with one power of two size smaller than currently used. So in your 20MBit example above you start with the 16MBit block, then this calculates the checksum for the remaining 4MBit (and also returns the created length, in the example this would be 4MBit - the created length will always be a power of 2).

In the 27MBit example this would calculate the checksum over the remaining 11MBit, and would already return 16MBit (with sub-calls in the 8MBit part, where it would return 4MBit, and in the 2MBit part where it would return 2MBit).
xprism wrote:
Fri Nov 20, 2020 11:06 am

Code: Select all

while (next_length < mask){ next_length += next_length; part2 += part2;}
part2 is added to itself as next_length advances to the end of the ROM

Code: Select all

length = mask + mask;
not sure what's the purpose of this either
This takes care of doing the mirroring until the created block is as large as the current block (and skips the mirroring if the created sub-block is already large enough).

In your 20MBit example the sub-checksum is for 4MBit, so this would be added four times to match the 16MBit part.

In the 27MBit example this would mirror the 1MBit part once to match the 2MBit part, then mirror the returned 4MBit part once to match the 8MBit part.

xprism
Snes9x White Belt
Posts: 4
Joined: Sun Nov 15, 2020 7:33 am

Re: Checksum calculation

Post by xprism » Mon Nov 23, 2020 2:23 pm

OV2 wrote:
Sun Nov 22, 2020 2:20 pm
For non power of two sizes the idea is to take the largest power of two block, then look at the remaining size in power of two parts, and mirror until you have another block of the largest size. Then the end result is also a power of two.
If you have multiple smaller parts you always mirror the smallest part first until it matches the next largest part, then mirror that whole group. (Which is the same as calculating the checksum recursively, which is what the function does)
Thanks for the detailed explanation! I reimplemented the algo in python, and it matches with snes9x's output (with the small number of roms I've tested so far).

However, I'm curious on what happens if the ROM is not a whole number of megabits, e.g. 27.75MBits. Am I right to assume it gets split into 16+8+2+1+0.5(2 power -1)+0.25(2 power -2). Then the last 0.25MBits is mirrored to match the 0.5MBit, so now we have a 1MBit part, and then the last 4MBits are mirrored once to match the 8MBit, so we'd have 16+ 8+ 2*(2+1+0.5+0.25+0.25mirrored) = 32MBit.

But what if it's a recurring decimal number of MBits? Or if the size, when expressed in MBits, has many decimal places?

User avatar
OV2
Official Win32 Porter/Dev
Posts: 668
Joined: Thu Aug 30, 2007 10:15 pm

Re: Checksum calculation

Post by OV2 » Mon Nov 23, 2020 3:57 pm

As long as the ROM has a size that is a multiple of 512KB, then this mirror algorithm is used (and it works the same below 1MB as above).
If it is not a multiple of 512KB, then it simply calculates the sum over the whole orignial ROM size, without any mirroring.

From the Checksum_Calculate function:

Code: Select all

		if (CalculatedSize & 0x7fff)
			sum = checksum_calc_sum(ROM, CalculatedSize);
		else
		{
			uint32	length = CalculatedSize;
			sum = checksum_mirror_sum(ROM, length);
		}

xprism
Snes9x White Belt
Posts: 4
Joined: Sun Nov 15, 2020 7:33 am

Re: Checksum calculation

Post by xprism » Tue Nov 24, 2020 12:29 pm

OV2 wrote:
Mon Nov 23, 2020 3:57 pm
As long as the ROM has a size that is a multiple of 512KB, then this mirror algorithm is used (and it works the same below 1MB as above).
If it is not a multiple of 512KB, then it simply calculates the sum over the whole orignial ROM size, without any mirroring.
Got it, thanks again!

Post Reply