trace.c

本程序是扫雷游戏在linux下可以运行的

#include "bomb.h"
#include <sys/types.h>
#include <sys/ptrace.h>
#include <signal.h>
#include <X11/Xlib.h>
#include <X11/StringDefs.h>
#include <X11/keysym.h>
#include <X11/extensions/XTest.h>
#define start_pointer 0x804ece8
#define block_pointer 0x804ed40
#define number_pointer 0x804ed44
#define times_pointer 0x804ecfc
#define row_pointer 0x804ea20
#define col_pointer 0x804ea24
#define lost_pointer 0x804ecec 


gint block_area;
gint number_area;
gint** my_block;
gint** num_block;
gint times = 1;
gint child;
gint change = 0;
gint first = 0;
gint MAX_ROW = 9;
gint MAX_COL = 9;

Display *dpy;

extern int errno;

void x_init ()
{
	dpy = XOpenDisplay (NULL);
}

void clear_area ()
{
	//clear old
	int i;
	if (my_block != NULL) {
		free (my_block[0]);
		free (my_block);
	}
	if (num_block != NULL) {
		free (num_block[0]);
		free (num_block);
	}
}

void reset_area ()
{
	int i;
//x ->row, y ->col
	//create new
	my_block = (gint**)g_malloc(MAX_ROW*sizeof(gint*));
	num_block = (gint**)g_malloc(MAX_ROW*sizeof(gint*));
	g_assert (my_block != NULL);
	g_assert (num_block != NULL);

	my_block[0] = (gint*)g_malloc (MAX_ROW*MAX_COL*sizeof(gint));
	num_block[0] = (gint*)g_malloc (MAX_ROW*MAX_COL*sizeof(gint));
	g_assert (my_block[0] != NULL);
	g_assert (num_block[0] != NULL);
	memset (my_block[0], 0, MAX_ROW*MAX_COL*sizeof(gint));
	memset (num_block[0], -1, MAX_ROW*MAX_COL*sizeof(gint));
	for (i = 0; i < MAX_ROW-1; i++) {
		my_block[i+1] = my_block[i] + MAX_COL;
		num_block[i+1] = num_block[i] + MAX_COL;	
	}
}

void dig_block (int x, int y)
{
	if (x < 0 || y < 0 || x >= MAX_ROW || y >= MAX_COL)
		return;
	if (my_block[x][y] == B_UNKNOW) {
		fprintf (stderr, "dig_block: r=%d, c=%d\n", x, y);
		XTestFakeMotionEvent (dpy, DefaultScreen(dpy),
				100+12+y*BLOCK_WIDTH,
				100+55+10+x*BLOCK_HEIGHT, 10);
		XTestFakeButtonEvent (dpy, 1, 1, 10);
		XFlush (dpy);
		XTestFakeButtonEvent (dpy, 1, 0, 10);
		XFlush (dpy);
	}
}

void dig_near (int x, int y)
{
	int i, j;
	for (i = x-1; i<= x+1; i++)
		for (j = y-1; j<= y+1; j++) {
			dig_block (i, j);
		}
}
int count_block_mark (int x, int y)
{
	if (x < 0 || y < 0 || x >=MAX_ROW || y>= MAX_COL){
		return 0;
	}
	if (num_block[x][y] == -2 ) {
			
		return 1;
	}
	return 0;
}


int count_near_mark (int x, int y)
{
	int i, j, num = 0;
	for (i = x-1; i <= x+1; i++)
		for (j = y-1; j<=y+1; j++) {
			num += count_block_mark (i, j);
		}
	return num;
}

int count_block_unknow (int x, int y)
{
	if (x < 0 || y < 0 || x >=MAX_ROW || y>= MAX_COL){
		return 0;
	}
	if (num_block[x][y] == -1) {
		return 1;
	}
	return 0;
}
// not right!
int count_near_unknow (int x, int y)
{
	int i, j, num = 0;
	for (i = x-1; i <= x+1; i++)
		for (j = y-1; j<=y+1; j++) {
			num += count_block_unknow (i, j);
		}
	return num;
}

void print_block ()
{
	int i, j;
	for (i = 0; i < MAX_ROW; i++) {
		for (j = 0; j< MAX_COL; j++) {
			fprintf (stderr, "%d\t", num_block[i][j]);
		}
		fprintf (stderr, "\n");
	}
}

void scan_block ()
{
	long bomb;
	int i, j, status;

	kill (child, SIGSTOP);
	wait(&status);
	//stop traced process
	for (i = 0; i < MAX_ROW; i++) {
		for (j = 0; j < MAX_COL; j++) {
			bomb = ptrace (PTRACE_PEEKTEXT, child,
			block_area+i*MAX_COL*sizeof(int)+j*sizeof(int));
			if (bomb == -1) {
				fprintf (stderr, "peek failed in scan block:%d\n", errno);
				kill (child, SIGKILL);
				exit(1);
			}
			if (my_block[i][j] != bomb) {
				change = 1;
				my_block[i][j] = bomb;
				if (my_block[i][j] == B_ONE) {
					bomb = ptrace (PTRACE_PEEKTEXT, child,
					number_area+i*MAX_COL*sizeof(int)+j*sizeof(int));
					if (bomb == -1) {
						fprintf (stderr, "peek failed in scan block 2:%d\n", errno);
						kill (child, SIGKILL);
						exit(1);
					}
					num_block[i][j] = bomb;
				}
				else if (my_block[i][j] == B_MARK) {
					num_block[i][j] = -2;
				}
				else if (my_block[i][j] == B_UNKNOW) {
					num_block[i][j] = -1;
				}
				else if (my_block[i][j] == B_NO) {
					num_block[i][j] = 0;
				}
				//ugly code!
			}
		}
	}
	ptrace (PTRACE_CONT, child, NULL, NULL);
	//and start it again;
}

int is_definite (int i, int j)
{
	int unknow, mark;
	if (num_block[i][j] <= 0)
		return -2;
	unknow = count_near_unknow (i, j);
	mark = count_near_mark (i, j);
	//fprintf (stderr, "block %d, %d:\t%d %d %d\n", i, j,
	//					unknow, mark, num_block[i][j]);
	if (num_block[i][j] == (unknow + mark) && unknow != 0) {
	//case 1: all the unknow should mark
		return 1;
	}
	if (num_block[i][j] == mark && unknow != 0) {
	//case 2: all the unknow should dig
		return 2;
	}
	return -1;
}

void mark_block (int i, int j)
{
	if (i < 0 || j < 0 || i >= MAX_ROW || j>= MAX_COL) 
		return;
	if (my_block[i][j] == B_UNKNOW) {
		fprintf (stderr, "mark block: r=%d c=%d\n", i, j);
		XTestFakeMotionEvent (dpy, DefaultScreen(dpy),
				100+12+j*BLOCK_WIDTH,
				100+60+10+i*BLOCK_HEIGHT, 10);
		XTestFakeButtonEvent (dpy, 3, 1, 10);
		XFlush (dpy);
		sleep (1);
		XTestFakeButtonEvent (dpy, 3, 0, 10);
		XFlush (dpy);

	}
}
	
void mark_near (int x, int y)
{
	int i, j;
	for (i = x-1; i<= x+1; i++)
		for (j = y-1; j<= y+1; j++) {
			mark_block (i, j);
		}
}

int find_definite ()
{
	int i, j, r;
	for (i = 0; i < MAX_ROW; i++)
		for (j = 0; j < MAX_COL; j++) {
			r = is_definite (i, j);
			if(r == 1) {
				mark_near (i, j);
				return 0;
			}
			else if (r == 2) {
				dig_near (i, j);
				return 0;
			}
/*
		fprintf (stderr, "find definite:r:%d c:%d\n", i, j);
				return 0;
*/
		}
	return -1;
}
		
void assume (int i, int j)
{
	my_block[i][j] = B_MARK;
	num_block[i][j] = -2;
}
void unassume (int i, int j)
{
	my_block[i][j] = B_UNKNOW;
	num_block[i][j] = -1;
}

void set_impossible (int i, int j)
{
	if (i < 0 || j < 0 || i >=MAX_ROW || j>= MAX_COL)
		return;
	if (num_block[i][j] == -1) {
		num_block[i][j] = -3;
	}
}
void unset_impossible()
{
	int i, j;
	for (i = 0; i < MAX_ROW; i++)
		for (j = 0; j < MAX_COL; j++) {
			if (num_block[i][j] == -3)
				num_block[i][j] = -1;
		}
}
int set_full (int i, int j)
{
	int unknow, mark, m, n;
	if (num_block[i][j] <= 0)
		return -2;
	unknow = count_near_unknow (i, j);
	mark = count_near_mark (i, j);
	if (mark == num_block[i][j] && unknow != 0) {
		for (m = i-1; m <= i+1; m++)
			for (n = j-1; n<= j+1; n++) {
				set_impossible (m, n);
			}
		return 0;
	}
	return -1;
}

int it_is_impossible (int i, int j)
{
	int unknow, mark, m, n;
	if (num_block[i][j] <= 0)
		return -2;
	unknow = count_near_unknow (i, j);
	mark = count_near_mark (i, j);
	
	if (mark > num_block[i][j])
	//will it happen???
		return 0;
	if (unknow < (num_block[i][j] - mark))
	//after setting some impossible, unknow will be less
		return 0;
	return -1;
}

int find_impossible ()
{
	int i, j;
	for (i = 0; i < MAX_ROW; i++)
		for (j = 0; j < MAX_COL; j++) {
			set_full (i, j);
		}
	for (i = 0; i < MAX_ROW; i++)
		for (j = 0; j < MAX_COL; j++) {
			if (! it_is_impossible (i, j)) {
				unset_impossible ();
				return 0;
			}
		}
	unset_impossible ();
	return -1;
}
	
int one_step_assume ()
{
	int i, j;
	for (i = 0; i < MAX_ROW; i++)
		for (j = 0; j < MAX_COL; j++) {
			if (my_block[i][j] != B_UNKNOW)
				continue;	
			assume (i, j);
			if (! find_impossible ()) {
				unassume (i, j);
				dig_block (i, j);
				return 0;
			}
			unassume (i, j);
		}
	return -1;
}

void rand_try ()
{
	int i, j;
	for (i = 0; i < MAX_ROW; i++)
		for (j = 0; j < MAX_COL; j++)
			if (my_block[i][j] == B_UNKNOW) {
				dig_block (i, j);
				return;
			}
//			else fprintf (stderr, "%d\t", my_block[i][j]);
}

void try_auto ()
{
	fprintf (stderr, "ok, let's have a try\n");
	if (! find_definite ())
		return;
	if (! one_step_assume ()) {
	/* perhaps we will do better for two or more steps assumption
	but that's a NP problem, i won't try it
	*/
		fprintf (stderr, "\t find assume\n");
		return;
	}
	//if (! find_definite ())
	//	return;
	fprintf (stderr, "sorry, i have no idea\n");
	rand_try ();	
}


int get_data_by_address (int address)
{
	int data;
	int status;
	kill (child, SIGSTOP);
	wait (&status);
	data = ptrace (PTRACE_PEEKTEXT, child, address);
	if (data < 0) {
		fprintf (stderr, "peek failed in get %x:%d\n",
					address, errno);
		exit (1);
	}
	ptrace (PTRACE_CONT, child, NULL, NULL);
	return data;
}

int get_block_area ()
{
	//read twice to get block_area
	int block_area;
	int tmp;
	int status;
	kill (child, SIGSTOP);	
	wait (&status);
	tmp = ptrace (PTRACE_PEEKTEXT, child, block_pointer);
	if (tmp < 0) {
		fprintf (stderr, "peek failed in get block 1:%d\n", errno);
		exit (1);
	}
	block_area = ptrace (PTRACE_PEEKTEXT, child, tmp);
	if (block_area < 0) {
		fprintf (stderr, "peek failed in get block 2:%d\n", errno);
		exit (1);
	}
	if ((status = ptrace (PTRACE_CONT, child, NULL, NULL)) < 0){
		fprintf (stderr, "cont failed in get block:%d\n", errno);
		exit (1);
	}
	return block_area;
}

int get_number_area ()
{
	//read twice to get number_area
	int number_area;
	int tmp;
	int status;
	kill (child, SIGSTOP);	
	wait (&status);
	tmp = ptrace (PTRACE_PEEKTEXT, child, number_pointer);
	if (tmp < 0) {
		fprintf (stderr, "peek failed in number 1:%d\n", errno);
		exit (1);
	}
	number_area = ptrace (PTRACE_PEEKTEXT, child, tmp);
	if (number_area < 0) {
		fprintf (stderr, "peek failedin number 2:%d\n", errno);
		exit (1);
	}
	ptrace (PTRACE_CONT, child, NULL, NULL);
	return number_area;
}


int main(void)
{
	long bomb;
	int status, i, j, tmp_times, tmp_row, tmp_col;
	char t;
	

	
	child = fork();
	if (child == 0) {
		fprintf (stderr, "trace me\n");
		if (ptrace (PTRACE_TRACEME) < 0) {
			fprintf (stderr, "trace failed:%d\n", errno);
		}
		fprintf (stderr, "child start\n");
		if (execlp ("./bomb", "bomb") < 0) {
			fprintf (stderr, "exec failed:%d\n", errno);
		}
	}
	x_init ();
	
	//wait (&status);
	//sleep (3);
	//if (ptrace (PTRACE_ATTACH, child) < 0) {
	//	fprintf (stderr, "attach failed:%d\n", errno);
	//}
	wait (&status);
	if (ptrace (PTRACE_CONT, child, NULL, NULL) < 0) {
		fprintf (stderr, "cont failed:%d\n", errno);
	}
	sleep (1);
	//ok, finish preparetion

	//start manually
	/*
	while (get_data_by_address (start_pointer) == 0) {
		sleep (1);
	}
	*/
	//start auto
	XTestFakeMotionEvent (dpy, DefaultScreen(dpy),
			100+30,
			100+30, 10);
	XTestFakeButtonEvent (dpy, 1, 1, 10);
	XFlush (dpy);
	sleep (1);
	XTestFakeButtonEvent (dpy, 1, 0, 10);
	XFlush (dpy);
	sleep (1);
	first = 1;
	times = tmp_times;
	tmp_row = get_data_by_address (row_pointer);
	tmp_col = get_data_by_address (col_pointer);
	MAX_ROW = tmp_row;
	MAX_COL = tmp_col;
	block_area = get_block_area();
	number_area = get_number_area();
	reset_area ();
	//scan_block ();
	while (1) {
		//sleep (1);
		tmp_times = get_data_by_address (times_pointer);
		if (get_data_by_address (start_pointer) == 0) {
			int lost = get_data_by_address (lost_pointer);
			myout ("not start\n");
			fprintf (stderr, "lost=%d\n", lost);
			kill (child, SIGKILL);
			if (!lost) {
				myout ("win\n");
				system ("touch win");
			}
			else {
				myout ("lost\n");
			}
			return ;
			sleep (1);
			continue;
		}
		if (tmp_times > times) {
			sleep (1);
			memset (my_block[0], 0, MAX_ROW*MAX_COL*sizeof(gint));
			memset (num_block[0], -1, MAX_ROW*MAX_COL*sizeof(gint));
			times = tmp_times;
			tmp_row = get_data_by_address (row_pointer);
			tmp_col = get_data_by_address (col_pointer);
			if (tmp_row != MAX_ROW || tmp_col != MAX_COL) {
				clear_area ();
				MAX_ROW = tmp_row;
				MAX_COL = tmp_col;
				reset_area ();
				block_area = get_block_area();
				number_area = get_number_area();
			}
			while (get_data_by_address (start_pointer) == 0) {
				sleep (1);
			}
			first = 1;
		}
		scan_block ();
/*		if (change == 1 || first == 1) {
			first = 0;
			change = 0;
			sleep (1);
		}
*/
		if (change == 0)
			sleep (0); //penalty
		print_block();
		try_auto ();
	}
}