Looking for the RNG in PowerMonger

[arkiruthis]

Hi everyone,

TL;DR Version:
I'm trying to find the random number generator process that PowerMonger uses. I'm familiar with the Amiga plugin in Ghidra, but the problem is that the game data is packed on the floppy image (or Disk1 file in the WHDLoad version) and I'm not quite sure how to unpack it to isolate the main executable for loading into Ghidra. My main objective at the moment is isolating and unpacking this main game exe.

Long Version
The RNG had to be consistent (e.g., rather than scan beam based) as it's used in the map generation to generate the same results and was ported to different architectures and consoles. I think I know what I'm looking for, an unusual combination of XOR and shifts on loaded data. I _think_ I found it in the DOS x86 dissassembly, but I generally find x86 and real mode memory decyphering horrible and fancy my chances in 68k more.

I already understand how the MAPDATA.DAT is used, I just need to generate the same sequence of numbers from the seeds and see how the PowerMonger runtime does that.

I'm using a raw 880Kb image of my original PowerMonger disk. At the offset 0x1600 the file listing is shown.

44 49 52 00 00 00 00 00 00 01 00 01 00 00 00 00 // DIR.............
53 54 41 52 54 5f 55 50 00 02 00 0a 00 00 bf f4 // START_UP......¿ô
49 4e 54 52 4f 44 41 54 00 0b 00 4a 00 05 76 c4 // INTRODAT...J..vÄ
52 55 4e 5f 50 52 4f 47 00 4b 00 56 00 01 03 88 // RUN_PROG.K.V....
54 45 58 54 55 52 45 53 00 57 00 58 00 00 1f a8 // TEXTURES.W.X...¨
51 41 5a 2e 50 41 4b 00 00 59 00 5b 00 00 35 a4 // QAZ.PAK..Y.[..5¤
53 50 52 49 54 45 31 36 00 5c 00 5c 00 00 0f 5c // SPRITE16.\.\...\
53 50 52 49 54 45 38 2e 00 5d 00 5e 00 00 22 14 // SPRITE8..].^..".
53 50 52 49 54 45 32 34 00 5f 00 5f 00 00 15 9c // SPRITE24._._....
53 50 52 49 54 45 33 32 00 60 00 61 00 00 21 ac // SPRITE32.`.a..!¬
43 41 50 47 52 41 50 48 00 62 00 63 00 00 2b 9c // CAPGRAPH.b.c...
46 58 2e 50 41 4b 00 00 00 64 00 72 00 01 40 c4 // FX.PAK...d.r..@Ä
4d 41 50 2e 50 41 4b 00 00 73 00 82 00 01 4d 08 // MAP.PAK..s....M.
4d 41 50 44 41 54 41 2e 00 83 00 86 00 00 43 ec // MAPDATA.......Cì
45 4e 44 5f 50 49 43 31 00 87 00 89 00 00 3f e8 // END_PIC1......?è
45 4e 44 2e 50 41 4b 00 00 8a 00 97 00 01 20 90 // END.PAK....... .
4c 4f 53 45 2e 50 41 4b 00 98 00 9d 00 00 73 a0 // LOSE.PAK......s.
57 49 4e 2e 50 41 4b 00 00 9e 00 9f 00 00 28 04 // WIN.PAK.......(.

I'm guessing that RUN_PROG is what I'm looking for. If we use that as an example, I'm guessing that the 2 long words after the file name describe the OFFSET and LENGTH of the file.

I'm pretty confident that the LENGTH is straightforward byte representation, as the intro was huge (358k, about 1/2 the disk).

However, I'm having difficulty deciphering the OFFSET. I'm looking at the raw hex and trying to find the last block that might be WIN.PAK and then go back from that address to correlate the offset shown. 0xd9400 visually looks to be where the WIN.PAK starts, but I'm not sure how to correlate that to the offset 0x009e009f shown in the file listing (edit - is it START / END ?). The LENGTH looks good, because if I do a relative offset from what visually looks like the final byte of WIN.PAK I pretty much end up at the start of the block.

Also, providing I can strip out the data block for RUN_PROG, I'm not even sure what the packing type is. Any help would be appreciated.

[Don_Adan]

Looks like start block, end block, size in bytes.
$4b×512 start offset
$56×512 end offset (can be plus 512)
$00010388 size of RUN_PROG

[arkiruthis]

Originally Posted by Don_Adan

Looks like start block, end block, size in bytes.
$4b×512 start offset
$56×512 end offset (can be plus 512)
$00010388 size of RUN_PROG

Thanks Don! Yeah, when chatting with someone about this we assumed it was 512 block size.

Just now I had a thought to simply divide the guessed address location by the start offset and got a reliable block size of 0x1600 and this seems to be the multiplier for them and gets me to the right positions. Unusual block size, but it seems to work out.

Now to see if it really is as simple as using xfdmaster...

[paraj]

Looks like it's track numbers (first and final [inclusive]). Matches up well with the size. I.e. RUN_PROG is probably found at 0x00067200-0x00077588 in the ADF file.

[Don_Adan]

Sorry, i was wrong, this is track value.
then 5632 bytes, not 512 bytes

[meynaf]

Originally Posted by arkiruthis

My main objective at the moment is isolating and unpacking this main game exe.

Have you tried to install the game with whdload ? Some installers extract the files rather than using disk images.
You may also have a look at the Atari ST version. IIRC this version uses plain files.

[arkiruthis]

Originally Posted by meynaf

Have you tried to install the game with whdload ? Some installers extract the files rather than using disk images.

Unfortunately WHDload seems to just use the raw floppy image (as Disk1)

Originally Posted by meynaf

You may also have a look at the Atari ST version. IIRC this version uses plain files.

Ah, that's interesting! Maybe the ST version is just a TOS executable.

I wrote a small script to trim out the RUN_PROG in the amiga version, but xfddecrunch doesn't seem to think that it's packed at all.

Ghidra didn't seem to recognise it as an executable for the Amiga plugin, but it's possible that the instructions start literally at that point in the file (i.e., no chunk header, etc.). I probably shouldn't have expected it to recognise it as a run of the mill executable.

So at that point I loaded it into ReSource (which I am very unfamiliar with, sadly). This is what it spit out for the first part of the file. I'm not sure if this is quite right.

	MOVEM.L	D1-D7/A0-A6,-(SP)
	MOVEA.L	#$1400,A1
	MOVE.L	(-4,A1),D0
	JSR	($1022).L
	MOVE.L	A3,D0
	JSR	($1400).L
	MOVEM.L	(SP)+,D1-D7/A0-A6
	RTS

	MOVEA.L	A1,A0
	ADDA.L	D0,A0
	MOVEA.L	-(A0),A2
	ADDA.L	A1,A2
	MOVE.L	-(A0),D5
	MOVE.L	-(A0),D0
... etc.

[paraj]

It's uncompressed and loaded (complete tracks) to address $1000 (boot block ignores the size field).

EDIT: I.e. in ghidra import it as a "Raw binary", language = 68000, options -> Base Address = 1000

EDIT2: Sorry only the start is uncompressed. Rest is compressed Some kind of powerpacker variant. Have to run now, but looks familiar..

[Aladin]

It would be great to have a WHDLOAD version with uncompressed files (for translation, for example).

[paraj]

Decrunched "RUN_PROG" in the zone (loaded at $1400).

Format is not PP, but also simple (and stupid) LZ that I've seen before:
LONG CompressedSize
LONG UncompressedSize
LONG InputChecksum (EOR of all input longs, must be 0 at the end)
LONG CompressedData[CompressedSize/4]

Compressed data is in reverse as is the output. Bits are read LSB->MSB. First long contains 0..31 bits (most significant bit is set to indicate end).

Format:
0 0 -> Literal run of length 1+get_bits(3)
0 1 -> Match, offset bits=8, length=2
1 0 0 -> Match, offset bits=9, length=3
1 0 1 -> Match, offset bits=10, length=4
1 1 0 -> Match, offset bits=12, length=1+get_bits(8) [also seen format that used 8 bits for offset here!]
1 1 1 -> Literal run of length 9+get_bits(8)

Anybody know what it's called?

"START_UP" (loaded at $1000) doesn't seem to be compressed (handling the intro sequence).

[arkiruthis]

Thanks for looking into this paraj! Well done on identifying the format. Alas my level of knowledge isn't quite up to depacking this just yet.

So I had another strategy, based on my recollection that you can remove the floppy once in-game. I know that when loaded into memory it won't be the same every time, so I set up a 500+ 1MB chip Amiga in WinUAE, loaded PowerMonger from my original disk and once past the protection I saved the 1024kb raw RAM data, but also the savestate so I could restore it in future sessions. I found that with the WinUAE debugger and the Ghidra dissassembly (68k, start address 0) I was able to match up between the 2. Downside is obviously I can't compare address locations with others as mine will be unique.

Still early days, but I did find some interesting things going on when pressing Random Map.

000125f0 2f 01           move.l     D1,-(SP)=>local_4
000125f2 20 39 00        move.l     (DAT_000535ce).l,D0  ; = A82B2D6Dh
         05 35 ce
000125f8 66 06           bne.b      LAB_00012600
000125fa 20 3c 00        move.l     #0xbc614e,D0 ; This is 12345678, which is unusual.
         bc 61 4e
                     LAB_00012600                        ; XREF[1]:     000125f8(j)  
00012600 22 3c bb        move.l     #-0x44bf19d3,D1 ; Weirdly large number, 1153374675, not a prime though...
         40 e6 2d
00012606 61 00 00 84     bsr.w      FUN_0001268c   ; Seems to do some shifting and masking on D0/D1 and returns D0    
0001260a 23 c0 00        move.l     D0,(DAT_000535ce).l  ; Stores it
         05 35 ce
00012610 e0 88           lsr.l      #0x8,D0        ; shift a byte, or divide by 256
00012612 02 80 00        andi.l     #0x7fff,D0     ; keep within 32k, could be index to the map data? (64 x 128 x 4bytes)
         00 7f ff
00012618 22 1f           move.l     (SP)+,D1
0001261a 4e 75           rts

This subroutine gets called from quite a few places (and during the map generation phase). What I found interesting was the 2 constants. One being "12345678" and the other an arbitrary large number.

Possibly 12345678 is used if D0 wasn't set up first?

I'm not sure this is related to the RNG though,as it seems to strip it down to 32k size before coming back. Though maybe it stores it in case the caller wants the long word version.

My 68k isn't great, so I may be completely misunderstanding this.

[paraj]

Originally Posted by arkiruthis

Thanks for looking into this paraj! Well done on identifying the format. Alas my level of knowledge isn't quite up to depacking this just yet.

You don't need to. When I wrote "Decrunched "RUN_PROG" in the zone (loaded at $1400)." it means that I put the decrunched in "The Zone!" (link in the menu bar at the top, next to the "Donate" link). You need to perform the steps described in the FAQ to get access.


Usually one off large files/copyrighted stuff gets put there rather than as an attachment.

Originally Posted by arkiruthis

So I had another strategy, based on my recollection that you can remove the floppy once in-game. I know that when loaded into memory it won't be the same every time, so I set up a 500+ 1MB chip Amiga in WinUAE, loaded PowerMonger from my original disk and once past the protection I saved the 1024kb raw RAM data, but also the savestate so I could restore it in future sessions. I found that with the WinUAE debugger and the Ghidra dissassembly (68k, start address 0) I was able to match up between the 2. Downside is obviously I can't compare address locations with others as mine will be unique.

Still early days, but I did find some interesting things going on when pressing Random Map.

000125f0 2f 01           move.l     D1,-(SP)=>local_4
000125f2 20 39 00        move.l     (DAT_000535ce).l,D0  ; = A82B2D6Dh
         05 35 ce
000125f8 66 06           bne.b      LAB_00012600
000125fa 20 3c 00        move.l     #0xbc614e,D0 ; This is 12345678, which is unusual.
         bc 61 4e
                     LAB_00012600                        ; XREF[1]:     000125f8(j)  
00012600 22 3c bb        move.l     #-0x44bf19d3,D1 ; Weirdly large number, 1153374675, not a prime though...
         40 e6 2d
00012606 61 00 00 84     bsr.w      FUN_0001268c   ; Seems to do some shifting and masking on D0/D1 and returns D0    
0001260a 23 c0 00        move.l     D0,(DAT_000535ce).l  ; Stores it
         05 35 ce
00012610 e0 88           lsr.l      #0x8,D0        ; shift a byte, or divide by 256
00012612 02 80 00        andi.l     #0x7fff,D0     ; keep within 32k, could be index to the map data? (64 x 128 x 4bytes)
         00 7f ff
00012618 22 1f           move.l     (SP)+,D1
0001261a 4e 75           rts

This subroutine gets called from quite a few places (and during the map generation phase). What I found interesting was the 2 constants. One being "12345678" and the other an arbitrary large number.

Possibly 12345678 is used if D0 wasn't set up first?

I'm not sure this is related to the RNG though,as it seems to strip it down to 32k size before coming back. Though maybe it stores it in case the caller wants the long word version.

My 68k isn't great, so I may be completely misunderstanding this.

Since the program is loaded at a fixed address, your numbers will match everyone else's


And yes, that sure looks like a random number generator. The function at 1268c returns the lower 32-bits of multiplying D0 and D1 (i.e. like UMult32).



So it's doing something like this:

uint32_t RandomSeed;
uint32_t rand(void)
{
  if (RandomSeed == 0) {
    RandomSeed = 12345678;
  }
  RandomSeed *= 3141592621; // This constant also looks familiar... :)
  return (RandomSeed >> 8) & 0x7fff;
}

[phx]

Originally Posted by paraj

Format:
0 0 -> Literal run of length 1+get_bits(3)
0 1 -> Match, offset bits=8, length=2
1 0 0 -> Match, offset bits=9, length=3
1 0 1 -> Match, offset bits=10, length=4
1 1 0 -> Match, offset bits=12, length=1+get_bits(8) [also seen format that used 8 bits for offset here!]
1 1 1 -> Literal run of length 9+get_bits(8)

Anybody know what it's called?

Bytekiller?
https://eab.abime.net/showthread.php...ght=bytekiller

[paraj]

Originally Posted by phx

Bytekiller?
https://eab.abime.net/showthread.php...ght=bytekiller

Yes, that's it, thanks! Strange, I did try searching for the source a bytekiller decruncher (because I remembered the name though not the method it uses), but didn't find any. Now multiple seem to show up when I search. Oh well, didn't try that hard.

[arkiruthis]

Originally Posted by paraj

Usually one off large files/copyrighted stuff gets put there rather than as an attachment.

Aha! Yup, grabbed it, thanks.

Originally Posted by paraj

And yes, that sure looks like a random number generator. The function at 1268c returns the lower 32-bits of multiplying D0 and D1 (i.e. like UMult32).

RandomSeed *= 3141592621; // This constant also looks familiar... :)

Haha! I should have picked up on that. I was using the Hex mode of the Windows Calculator, and of course +/- doesn't convert it to unsigned, so I totally missed it was that!

Thanks, yeah I've distilled down the RNG and as you say it's literally a 32bit unsigned multiplication. I've even now found the routines where it loads from the seed data vs generating a level randomly. So it's going really well. Thank you everyone for your help on this.

[arkiruthis]

Cracked it!

As I always suspected, it's a "brownian" walk across the landscape where you push up the heightfield as you go. There's then a number of smoothing passes which take the jagged landscape and make it more natural.

Tonight in a test program I generated the first level map using the original seed data from the first level of the game and got the identical map out.

[copse]

Nice work! Can I ask what your project is? A remake?

[arkiruthis]

I've documented my findings in case anyone looks for this in future.

https://github.com/arkiruthis/powermonger-terrain

Originally Posted by copse

Nice work! Can I ask what your project is? A remake?

I'm pondering a port to the Acorn Archimedes, specifically Mode 13 (320x256 256 colors). I have an interest in both 68k and ARM. The Archimedes had a fixed palette, so it's a little bit tricky (it's not easily remappable like VGA). But having fun so far.

Litttle terrain demo running on Archimedes:
https://twitter.com/nickluvsretro/st...538440704?s=20

Though I think I'd have to make it just a "in the flavor of" tribute, rather than a port. EA are a little... spicy.. when it comes to their IP.

[copse]

How goes the project @arkiruthis?

[arkiruthis]

Originally Posted by copse

How goes the project @arkiruthis?

Sorry, I didn't see there'd been replies here. Yeah, pretty good. I put in the sprites and also got some formations working. If you have a working adblocker following YT's latest purge, there's some footage here. Performance here on stock Acorn A3020.

[ Show youtube player ]

I am considering switching to a new game IP rather than a port for 2 reasons.
1. Potential issues around EA assets if I wanted to host it.
2. PowerMonger is 320x200, but the Archimedes uses 320x256 so everything is squished.

I'm still looking for the Bresenham Triangle-Fill algorithm in the Amiga PowerMonger though. I'm using a DDA (which is very fast), but fixed-point DDA causes cracks when vertices are close together, whereas Bresenham triangles (usually with edge lists) tend to maintain mesh cohesion well.

If anyone has any ideas what to look for, I'd appreciate it. I did note some functions in Ghidra which looked possible, but I'm not really sure.