Mercurialradare2 / file revision
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | raw | help
libr/diff/diff.c
author pancake@pair
Sat, 04 Feb 2012 03:51:22 +0100
changeset 2007 ef840cc3d292
parent 1772 9b4af93d5460
permissions -rw-r--r--
* Initial support for the z80 CPU
- assembler, disassembler and basic code analysis
- code analysis is very primitive atm 
     1 /* radare - LGPL - Copyright 2009-2010 pancake<nopcode.org> */
     2 
     3 #include <r_diff.h>
     4 
     5 R_API RDiff *r_diff_new(ut64 off_a, ut64 off_b) {
     6 	RDiff *d = R_NEW (RDiff);
     7 	if (d) {
     8 		d->delta = 1;
     9 		d->user = NULL;
    10 		d->off_a = off_a;
    11 		d->off_b = off_b;
    12 	}
    13 	return d;
    14 }
    15 
    16 R_API RDiff *r_diff_free(RDiff *d) {
    17 	free (d);
    18 	return NULL;
    19 }
    20 
    21 R_API int r_diff_set_callback(RDiff *d, RDiffCallback callback, void *user) {
    22 	d->callback = callback;
    23 	d->user = user;
    24 	return 1;
    25 }
    26 
    27 R_API int r_diff_set_delta(RDiff *d, int delta) {
    28 	d->delta = delta;
    29 	return 1;
    30 }
    31 
    32 R_API int r_diff_buffers_static(RDiff *d, const ut8 *a, int la, const ut8 *b, int lb) {
    33 	int i, len;
    34 	int hit = 0;
    35 	la = R_ABS(la);
    36 	lb = R_ABS(lb);
    37 	if (la != lb) {
    38 	 	len = R_MIN(la, lb);
    39 		fprintf(stderr,
    40 			"Buffer truncated to %d bytes (%d not compared)\n",
    41 			len, R_ABS(lb-la));
    42 	} else len = la;
    43 	for(i = 0; i<len; i++) {
    44 		if (a[i]!=b[i]) {
    45 			hit++;
    46 		} else {
    47 			if (hit>0) {
    48 				struct r_diff_op_t o = {
    49 					.a_off = d->off_a+i-hit, .a_buf = a+i-hit, .a_len = hit,
    50 					.b_off = d->off_b+i-hit, .b_buf = b+i-hit, .b_len = hit 
    51 				};
    52 				d->callback (d, d->user, &o);
    53 				hit = 0;
    54 			}
    55 		}
    56 	}
    57 	if (hit>0) {
    58 		struct r_diff_op_t o = {
    59 			.a_off = d->off_a+i-hit, .a_buf = a+i-hit, .a_len = hit,
    60 			.b_off = d->off_b+i-hit, .b_buf = b+i-hit, .b_len = hit 
    61 		};
    62 		d->callback (d, d->user, &o);
    63 		hit = 0;
    64 	}
    65 	return 0;
    66 }
    67 
    68 R_API int r_diff_buffers_radiff(RDiff *d, const ut8 *a, int la, const ut8 *b, int lb) {
    69 	char *ptr, *str, buf[64];
    70 	FILE *fd;
    71 	char oop = 0;
    72 	int ret, atl, btl, hit;
    73 	ut8 at[128], bt[128];
    74 	ut64 ooa, oob;
    75 
    76 	hit = atl = btl = 0;
    77 	ooa = oob = 0LL;
    78 	oop = -1;
    79 
    80 	r_file_dump (".a", a, la);
    81 	r_file_dump (".b", b, lb);
    82 	r_sys_cmd ("radiff -d .a .b | rsc uncolor > .d");
    83 	fd = fopen (".d", "r");
    84 
    85 	while (!feof (fd)) {
    86 		ut64 oa, ob; // offset
    87 		int ba, bb = 0; // byte
    88 		char op; // operation
    89 
    90 		oa = ob = 0LL;
    91 		if (!fgets (buf, 63, fd))
    92 			break;
    93 		if (feof (fd))
    94 			break;
    95 		str = buf;
    96 
    97 		ptr = strchr (buf, ' ');
    98 		if (!ptr) continue;
    99 		*ptr='\0';
   100 		sscanf (str, "0x%08"PFMT64x"", &oa);
   101 
   102 		str = r_str_ichr (ptr+1, ' ');
   103 		if (*str!='|'&&*str!='>'&&*str!='<') {
   104 			ptr = strchr (str, ' ');
   105 			if (!ptr) continue;
   106 			*ptr='\0';
   107 			sscanf (str, "%02x", &ba);
   108 		} else ba = 0;
   109 
   110 		str = r_str_ichr (ptr+1, ' ');
   111 		ptr = strchr (str, ' ');
   112 		if (!ptr) continue;
   113 		*ptr='\0';
   114 		sscanf (str, "%c", &op);
   115 
   116 		str = r_str_ichr (ptr+1, ' ');
   117 		if (str[0]!='0' || str[1]!='x') {
   118 			ptr = strchr(str, ' ');
   119 			if (!ptr) continue;
   120 			*ptr = '\0';
   121 			sscanf (str, "%02x", &bb);
   122 		}
   123 
   124 		str = ptr+1;
   125 		ptr = strchr (str, '\n');
   126 		if (!ptr) continue;
   127 		*ptr='\0';
   128 		sscanf (str, "0x%08"PFMT64x"", &ob);
   129 
   130 		if (oop == op || oop==-1) {
   131 			if (hit == 0) {
   132 				ooa = oa;
   133 				oob = ob;
   134 			}
   135 			at[atl] = ba;
   136 			bt[btl] = bb;
   137 			switch (op) {
   138 			case '|':
   139 				atl++;
   140 				btl++;
   141 				break;
   142 			case '>':
   143 				btl++;
   144 				break;
   145 			case '<':
   146 				atl++;
   147 				break;
   148 			}
   149 			hit++;
   150 		} else {
   151 			if (hit>0) {
   152 				struct r_diff_op_t o = {
   153 					.a_off = ooa, .a_buf = at, .a_len = atl,
   154 					.b_off = oob, .b_buf = bt, .b_len = btl
   155 				};
   156 				ret = d->callback(d, d->user, &o);
   157 					break;
   158 				atl = btl = 0;
   159 				hit = 0;
   160 				if (!ret)
   161 					break;
   162 			}
   163 		}
   164 		oop = op;
   165 	}
   166 	if (hit>0) {
   167 		struct r_diff_op_t o = {
   168 			.a_off = ooa, .a_buf = at, .a_len = atl,
   169 			.b_off = oob, .b_buf = bt, .b_len = btl
   170 		};
   171 		if (!d->callback (d, d->user, &o))
   172 			return 0;
   173 		atl = btl = 0;
   174 		hit = 0;
   175 	}
   176 	fclose(fd);
   177 	unlink(".a");
   178 	unlink(".b");
   179 	unlink(".d");
   180 	return 0;
   181 }
   182 
   183 R_API int r_diff_buffers(RDiff *d, const ut8 *a, ut32 la, const ut8 *b, ut32 lb) {
   184 	if (d->delta)
   185 		return r_diff_buffers_delta (d, a, la, b, lb);
   186 	return r_diff_buffers_static (d, a, la, b, lb);
   187 }
   188 
   189 /* TODO: Move into r_util maybe? */
   190 R_API int r_diff_buffers_distance(RDiff *d, const ut8 *a, ut32 la, const ut8 *b, ut32 lb,
   191 		ut32 *distance, double *similarity) {
   192 	int i, j, cost, tmin, **m;
   193 
   194 	if (!a || !b || la < 1 || lb < 1)
   195 		return R_FALSE;
   196 
   197 	if ((m = malloc ((la+1) * sizeof(int*))) == NULL)
   198 		return R_FALSE;
   199 	for(i = 0; i <= la; i++)
   200 		if ((m[i] = malloc ((lb+1) * sizeof(int))) == NULL)
   201 			return R_FALSE;
   202 
   203 	for (i = 0; i <= la; i++)
   204 		m[i][0] = i;
   205 	for (j = 0; j <= lb; j++)
   206 		m[0][j] = j;
   207 
   208 	for (i = 1; i <= la; i++) {
   209 		for (j = 1; j <= lb; j++) {
   210 			if (a[i-1] == b[j-1])
   211 				cost = 0;
   212 			else cost = 1;
   213 			tmin = R_MIN (m[i-1][j] + 1, m[i][j-1] + 1);
   214 			m[i][j] = R_MIN (tmin, m[i-1][j-1] + cost);
   215 		}
   216 	}
   217 	
   218 	if (distance != NULL)
   219 		*distance = m[la][lb];
   220 	if (similarity != NULL) {
   221 		if (la == 0 || lb == 0)
   222 			*similarity = 0;
   223 		else
   224 			*similarity = (double)1 - (double)(m[la][lb])/(double)(R_MAX(la, lb));
   225 	}
   226 
   227 	for(i = 0; i <= la; i++)
   228 		free (m[i]);
   229 	free (m);
   230 
   231 	return R_TRUE;
   232 }
radare2