How can I find the data structure that represents mine layout of Minesweeper in memory?
Solution 1:
Part 1 of 3
If you are serious into reverse engineering - forget about trainers and cheat engines.
Good reverse engineer should first get to know OS, core API functions, program general structure (what is run loop, windows structures, event handling routines), file format (PE). Petzold's classics "Programming Windows" can help (www.amazon.com/exec/obidos/ISBN=157231995X) as well as online MSDN.
First you should think about where minefield initialization routine can be called. I thought of following:
- When you launch the game
- When you click happy face
- When you click Game->New or press F2
- When you change level difficulty
I decided to check out F2 accelerator command.
To find accelerator handling code you are to find window message handling procedure (WndProc). It can be traced down by CreateWindowEx and RegisterClass calls.
To read:
- CreateWindowEx http://msdn.microsoft.com/en-us/library/ms632680%28VS.85%29.aspx
- RegisterClass http://msdn.microsoft.com/en-us/library/ms633586%28VS.85%29.aspx
- Petzold's Chapter 3 "Windows and Messages"
Open up IDA, Imports window, find "CreateWindow*", jump to it and use "Jump xref to operand (X)" command to see where it is called. There should be just one call.
Now look above for RegisterClass function and it's parameter WndClass.lpfnWndProc. I already named function mainWndProc in my case.
.text:0100225D mov [ebp+WndClass.lpfnWndProc], offset mainWndProc
.text:01002264 mov [ebp+WndClass.cbClsExtra], edi
.text:01002267 mov [ebp+WndClass.cbWndExtra], edi
.text:0100226A mov [ebp+WndClass.hInstance], ecx
.text:0100226D mov [ebp+WndClass.hIcon], eax
.text:01002292 call ds:RegisterClassW
Hit Enter on function name (use 'N' to rename it to something better)
Now take a look at
.text:01001BCF mov edx, [ebp+Msg]
This is message id, which in case of F2 button press should contain WM_COMMAND value. You are to find where it is compared to 111h. It can be done either by tracing down edx in IDA or by setting conditional breakpoint in WinDbg and pressing F2 in the game.
Either way leads to something like
.text:01001D5B sub eax, 111h
.text:01001D60 jz short loc_1001DBC
Right click on 111h and use "Symbolic constant" -> "Use standard symbolic constant", type WM_ and Enter. You should now have
.text:01001D5B sub eax, WM_COMMAND
.text:01001D60 jz short loc_1001DBC
It is an easy way to find out message id values.
To understand accelerator handling check out:
- Using Keyboard Accelerators
- Resource hacker (http://angusj.com/resourcehacker/)
It's quite a lot of text for a single answer. If you are interested I can write another couple of posts. Long story short minefield stored as an array of bytes [24x36], 0x0F shows that byte is not used (playing smaller field), 0x10 - empty field, 0x80 - mine.
Part 2 of 3
Ok, let's go on with F2 button.
According to Using Keyboard Accelerators when F2 button is pressed wndProc function
... receives a WM_COMMAND or WM_SYSCOMMAND message. The low-order word of the wParam parameter contains the identifier of the accelerator.
Ok, we already found where WM_COMMAND is processed, but how to determine corresponding wParam parameter value? This is where Resource hacker comes into play. Feed it with binary and it shows you everything. Like accelerators table for me.
alt text http://files.getdropbox.com/u/1478671/2009-07-29_161532.jpg
You can see here, that F2 button corresponds to 510 in wParam.
Now let's get back to code, that handles WM_COMMAND. It compares wParam with different constants.
.text:01001DBC HandleWM_COMMAND: ; CODE XREF: mainWndProc+197j
.text:01001DBC movzx eax, word ptr [ebp+wParam]
.text:01001DC0 mov ecx, 210h
.text:01001DC5 cmp eax, ecx
.text:01001DC7 jg loc_1001EDC
.text:01001DC7
.text:01001DCD jz loc_1001ED2
.text:01001DCD
.text:01001DD3 cmp eax, 1FEh
.text:01001DD8 jz loc_1001EC8
Use context menu or 'H' keyboard shortcut to display decimal values and you can see our jump
.text:01001DBC HandleWM_COMMAND: ; CODE XREF: mainWndProc+197j
.text:01001DBC movzx eax, word ptr [ebp+wParam]
.text:01001DC0 mov ecx, 528
.text:01001DC5 cmp eax, ecx
.text:01001DC7 jg loc_1001EDC
.text:01001DC7
.text:01001DCD jz loc_1001ED2
.text:01001DCD
.text:01001DD3 cmp eax, 510
.text:01001DD8 jz loc_1001EC8 ; here is our jump
It leads to code chunk that calls some proc and exits wndProc.
.text:01001EC8 loc_1001EC8: ; CODE XREF: mainWndProc+20Fj
.text:01001EC8 call sub_100367A ; startNewGame ?
.text:01001EC8
.text:01001ECD jmp callDefAndExit ; default
Is that the function that initiates new game? Find that out in the last part! Stay tuned.
Part 3 of 3
Let's take a look at the first part of that function
.text:0100367A sub_100367A proc near ; CODE XREF: sub_100140C+CAp
.text:0100367A ; sub_1001B49+33j ...
.text:0100367A mov eax, dword_10056AC
.text:0100367F mov ecx, uValue
.text:01003685 push ebx
.text:01003686 push esi
.text:01003687 push edi
.text:01003688 xor edi, edi
.text:0100368A cmp eax, dword_1005334
.text:01003690 mov dword_1005164, edi
.text:01003696 jnz short loc_10036A4
.text:01003696
.text:01003698 cmp ecx, dword_1005338
.text:0100369E jnz short loc_10036A4
There are two values (dword_10056AC, uValue) read into registers eax and ecx and compared to another two values (dword_1005164, dword_1005338).
Take a look at actual values using WinDBG ('bp 01003696'; on break 'p eax; p ecx') - they seemed like minefield dimensions for me. Playing with custom minefield size showed that first pair are new dimensions and second - current dimensions. Let's set new names.
.text:0100367A startNewGame proc near ; CODE XREF: handleButtonPress+CAp
.text:0100367A ; sub_1001B49+33j ...
.text:0100367A mov eax, newMineFieldWidth
.text:0100367F mov ecx, newMineFieldHeight
.text:01003685 push ebx
.text:01003686 push esi
.text:01003687 push edi
.text:01003688 xor edi, edi
.text:0100368A cmp eax, currentMineFieldWidth
.text:01003690 mov dword_1005164, edi
.text:01003696 jnz short loc_10036A4
.text:01003696
.text:01003698 cmp ecx, currentMineFieldHeight
.text:0100369E jnz short loc_10036A4
A little bit later new values overwrite current and subroutine is called
.text:010036A7 mov currentMineFieldWidth, eax
.text:010036AC mov currentMineFieldHeight, ecx
.text:010036B2 call sub_1002ED5
And when I saw it
.text:01002ED5 sub_1002ED5 proc near ; CODE XREF: sub_1002B14:loc_1002B1Ep
.text:01002ED5 ; sub_100367A+38p
.text:01002ED5 mov eax, 360h
.text:01002ED5
.text:01002EDA
.text:01002EDA loc_1002EDA: ; CODE XREF: sub_1002ED5+Dj
.text:01002EDA dec eax
.text:01002EDB mov byte ptr dword_1005340[eax], 0Fh
.text:01002EE2 jnz short loc_1002EDA
I was completely sure that I found minefield array. Cause of cycle which inits 360h bytes length array (dword_1005340 ) with 0xF.
Why 360h = 864? There are some cues below that row takes 32 bytes and 864 can be divided by 32, so array can hold 27*32 cells (although UI allows max 24*30 field, there is one byte padding around array for borders).
Following code generates minefield top and bottom borders (0x10 byte). I hope you can see loop iteration in that mess ;) I had to use paper and pen
.text:01002EE4 mov ecx, currentMineFieldWidth
.text:01002EEA mov edx, currentMineFieldHeight
.text:01002EF0 lea eax, [ecx+2]
.text:01002EF3 test eax, eax
.text:01002EF5 push esi
.text:01002EF6 jz short loc_1002F11 ;
.text:01002EF6
.text:01002EF8 mov esi, edx
.text:01002EFA shl esi, 5
.text:01002EFD lea esi, dword_1005360[esi]
.text:01002EFD
.text:01002F03 draws top and bottom borders
.text:01002F03
.text:01002F03 loc_1002F03: ; CODE XREF: sub_1002ED5+3Aj
.text:01002F03 dec eax
.text:01002F04 mov byte ptr MineField?[eax], 10h ; top border
.text:01002F0B mov byte ptr [esi+eax], 10h ; bottom border
.text:01002F0F jnz short loc_1002F03
.text:01002F0F
.text:01002F11
.text:01002F11 loc_1002F11: ; CODE XREF: sub_1002ED5+21j
.text:01002F11 lea esi, [edx+2]
.text:01002F14 test esi, esi
.text:01002F16 jz short loc_1002F39
And the rest of subroutine draws left and right borders
.text:01002F18 mov eax, esi
.text:01002F1A shl eax, 5
.text:01002F1D lea edx, MineField?[eax]
.text:01002F23 lea eax, (MineField?+1)[eax+ecx]
.text:01002F23
.text:01002F2A
.text:01002F2A loc_1002F2A: ; CODE XREF: sub_1002ED5+62j
.text:01002F2A sub edx, 20h
.text:01002F2D sub eax, 20h
.text:01002F30 dec esi
.text:01002F31 mov byte ptr [edx], 10h
.text:01002F34 mov byte ptr [eax], 10h
.text:01002F37 jnz short loc_1002F2A
.text:01002F37
.text:01002F39
.text:01002F39 loc_1002F39: ; CODE XREF: sub_1002ED5+41j
.text:01002F39 pop esi
.text:01002F3A retn
Smart usage of WinDBG commands can provide you cool minefield dump (custom size 9x9). Check out the borders!
0:000> db /c 20 01005340 L360
01005340 10 10 10 10 10 10 10 10-10 10 10 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f ................................
01005360 10 0f 0f 0f 0f 0f 0f 0f-0f 0f 10 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f ................................
01005380 10 0f 0f 0f 0f 0f 0f 0f-0f 0f 10 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f ................................
010053a0 10 0f 0f 0f 0f 0f 0f 0f-0f 0f 10 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f ................................
010053c0 10 0f 0f 0f 0f 0f 0f 0f-0f 0f 10 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f ................................
010053e0 10 0f 0f 0f 0f 0f 0f 0f-0f 0f 10 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f ................................
01005400 10 0f 0f 0f 0f 0f 0f 0f-0f 0f 10 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f ................................
01005420 10 0f 0f 0f 0f 0f 0f 0f-0f 0f 10 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f ................................
01005440 10 0f 0f 0f 0f 0f 0f 0f-0f 0f 10 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f ................................
01005460 10 0f 0f 0f 0f 0f 0f 0f-0f 0f 10 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f ................................
01005480 10 10 10 10 10 10 10 10-10 10 10 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f ................................
010054a0 0f 0f 0f 0f 0f 0f 0f 0f-0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f ................................
010054c0 0f 0f 0f 0f 0f 0f 0f 0f-0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f ................................
010054e0 0f 0f 0f 0f 0f 0f 0f 0f-0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f ................................
Hmm, looks like I'll need another post to close the topic
Solution 2:
It seems like you are trying to disassemble the source but what you need to do is look at the memory space of the running program. The hex editor HxD has a feature that lets you just that.
Once you're in the memory space, it is a matter of taking snapshots of the memory while you mess around with the board. Isolate what changes versus what doesn't. When you think you have a handle on where the data structure lies in hex memory, try editing it while it is in memory and see if the board changes as a result.
The process you want is not unlike building a 'trainer' for a video game. Those are usually based on finding where values like health and ammo live in memory and changing them on the fly. You may be able to find some good tutorials on how to build game trainers.