1 /* radare - LGPL - Copyright 2009-2020 - pancake, nibble */
2
3 #include <r_core.h>
4 #include <r_util.h>
5 #include <r_cons.h>
6
7 #define mid_down_refline(a, r) ((r)->from > (r)->to && (a) < (r)->from && (a) > (r)->to)
8 #define mid_up_refline(a, r) ((r)->from < (r)->to && (a) > (r)->from && (a) < (r)->to)
9 #define mid_refline(a, r) (mid_down_refline (a, r) || mid_up_refline (a, r))
10 #define in_refline(a, r) (mid_refline (a, r) || (a) == (r)->from || (a) == (r)->to)
11
12 typedef struct refline_end {
13 int val;
14 bool is_from;
15 RAnalRefline *r;
16 } ReflineEnd;
17
cmp_asc(const struct refline_end * a,const struct refline_end * b)18 static int cmp_asc(const struct refline_end *a, const struct refline_end *b) {
19 return (a->val > b->val) - (a->val < b->val);
20 }
21
cmp_by_ref_lvl(const RAnalRefline * a,const RAnalRefline * b)22 static int cmp_by_ref_lvl(const RAnalRefline *a, const RAnalRefline *b) {
23 return (a->level < b->level) - (a->level > b->level);
24 }
25
refline_end_new(ut64 val,bool is_from,RAnalRefline * ref)26 static ReflineEnd *refline_end_new(ut64 val, bool is_from, RAnalRefline *ref) {
27 ReflineEnd *re = R_NEW0 (struct refline_end);
28 if (!re) {
29 return NULL;
30 }
31 re->val = val;
32 re->is_from = is_from;
33 re->r = ref;
34 return re;
35 }
36
add_refline(RList * list,RList * sten,ut64 addr,ut64 to,int * idx)37 static bool add_refline(RList *list, RList *sten, ut64 addr, ut64 to, int *idx) {
38 ReflineEnd *re1, *re2;
39 RAnalRefline *item = R_NEW0 (RAnalRefline);
40 if (!item) {
41 return false;
42 }
43 item->from = addr;
44 item->to = to;
45 item->index = *idx;
46 item->level = -1;
47 item->direction = (to > addr)? 1: -1;
48 *idx += 1;
49 r_list_append (list, item);
50
51 re1 = refline_end_new (item->from, true, item);
52 if (!re1) {
53 free (item);
54 return false;
55 }
56 r_list_add_sorted (sten, re1, (RListComparator)cmp_asc);
57
58 re2 = refline_end_new (item->to, false, item);
59 if (!re2) {
60 free (re1);
61 free (item);
62 return false;
63 }
64 r_list_add_sorted (sten, re2, (RListComparator)cmp_asc);
65 return true;
66 }
67
r_anal_reflines_free(RAnalRefline * rl)68 R_API void r_anal_reflines_free (RAnalRefline *rl) {
69 free (rl);
70 }
71
72 /* returns a list of RAnalRefline for the code present in the buffer buf, of
73 * length len. A RAnalRefline exists from address A to address B if a jmp,
74 * conditional jmp or call instruction exists at address A and it targets
75 * address B.
76 *
77 * nlines - max number of lines of code to consider
78 * linesout - true if you want to display lines that go outside of the scope [addr;addr+len)
79 * linescall - true if you want to display call lines */
r_anal_reflines_get(RAnal * anal,ut64 addr,const ut8 * buf,ut64 len,int nlines,int linesout,int linescall)80 R_API RList *r_anal_reflines_get(RAnal *anal, ut64 addr, const ut8 *buf, ut64 len, int nlines, int linesout, int linescall) {
81 RList *list, *sten;
82 RListIter *iter;
83 RAnalOp op;
84 struct refline_end *el;
85 const ut8 *ptr = buf;
86 const ut8 *end = buf + len;
87 ut8 *free_levels;
88 int sz = 0, count = 0;
89 ut64 opc = addr;
90
91 memset (&op, 0, sizeof (op));
92 /*
93 * 1) find all reflines
94 * 2) sort "from"s and "to"s in a list
95 * 3) traverse the list to find the minimum available level for each refline
96 * * create a sorted list with available levels.
97 * * when we encounter a previously unseen "from" or "to" of a
98 * refline, we occupy the lowest level available for it.
99 * * when we encounter the "from" or "to" of an already seen
100 * refline, we free that level.
101 */
102
103 list = r_list_newf (free);
104 if (!list) {
105 return NULL;
106 }
107 sten = r_list_newf ((RListFree)free);
108 if (!sten) {
109 goto list_err;
110 }
111 r_cons_break_push (NULL, NULL);
112 /* analyze code block */
113 while (ptr < end && !r_cons_is_breaked ()) {
114 if (nlines != -1) {
115 if (!nlines) {
116 break;
117 }
118 nlines--;
119 }
120 if (anal->maxreflines && count > anal->maxreflines) {
121 break;
122 }
123 addr += sz;
124 {
125 RPVector *metas = r_meta_get_all_at (anal, addr);
126 if (metas) {
127 void **it;
128 ut64 skip = 0;
129 r_pvector_foreach (metas, it) {
130 RIntervalNode *node = *it;
131 RAnalMetaItem *meta = node->data;
132 switch (meta->type) {
133 case R_META_TYPE_DATA:
134 case R_META_TYPE_STRING:
135 case R_META_TYPE_HIDE:
136 case R_META_TYPE_FORMAT:
137 case R_META_TYPE_MAGIC:
138 skip = r_meta_node_size (node);
139 goto do_skip;
140 default:
141 break;
142 }
143 }
144 do_skip:
145 r_pvector_free (metas);
146 if (skip) {
147 ptr += skip;
148 addr += skip;
149 goto __next;
150 }
151 }
152 }
153 if (!anal->iob.is_valid_offset (anal->iob.io, addr, 1)) {
154 const int size = 4;
155 ptr += size;
156 addr += size;
157 goto __next;
158 }
159
160 // This can segfault if opcode length and buffer check fails
161 r_anal_op_fini (&op);
162 int rc = r_anal_op (anal, &op, addr, ptr, (int)(end - ptr), R_ANAL_OP_MASK_BASIC | R_ANAL_OP_MASK_HINT);
163 if (rc <= 0) {
164 sz = 1;
165 goto __next;
166 }
167 sz = op.size;
168 if (sz <= 0) {
169 sz = 1;
170 goto __next;
171 }
172
173 /* store data */
174 switch (op.type) {
175 case R_ANAL_OP_TYPE_CALL:
176 if (!linescall) {
177 break;
178 }
179 case R_ANAL_OP_TYPE_CJMP:
180 case R_ANAL_OP_TYPE_JMP:
181 if ((!linesout && (op.jump > opc + len || op.jump < opc)) || !op.jump) {
182 break;
183 }
184 if (!add_refline (list, sten, addr, op.jump, &count)) {
185 r_anal_op_fini (&op);
186 goto sten_err;
187 }
188 // add false branch in case its set and its not a call, useful for bf, maybe others
189 if (!op.delay && op.fail != UT64_MAX && op.fail != addr + op.size) {
190 if (!add_refline (list, sten, addr, op.fail, &count)) {
191 r_anal_op_fini (&op);
192 goto sten_err;
193 }
194 }
195 break;
196 case R_ANAL_OP_TYPE_SWITCH:
197 {
198 RAnalCaseOp *caseop;
199 RListIter *iter;
200
201 // add caseops
202 if (!op.switch_op) {
203 break;
204 }
205 r_list_foreach (op.switch_op->cases, iter, caseop) {
206 if (!linesout && (op.jump > opc + len || op.jump < opc)) {
207 goto __next;
208 }
209 if (!add_refline (list, sten, op.switch_op->addr, caseop->jump, &count)) {
210 r_anal_op_fini (&op);
211 goto sten_err;
212 }
213 }
214 break;
215 }
216 }
217 __next:
218 ptr += sz;
219 }
220 r_anal_op_fini (&op);
221 r_cons_break_pop ();
222
223 free_levels = R_NEWS0 (ut8, r_list_length (list) + 1);
224 if (!free_levels) {
225 goto sten_err;
226 }
227 int min = 0;
228
229 r_list_foreach (sten, iter, el) {
230 if ((el->is_from && el->r->level == -1) || (!el->is_from && el->r->level == -1)) {
231 el->r->level = min + 1;
232 free_levels[min] = 1;
233 if (min < 0) {
234 min = 0;
235 }
236 while (free_levels[++min] == 1) {
237 ;
238 }
239 } else {
240 free_levels[el->r->level - 1] = 0;
241 if (min > el->r->level - 1) {
242 min = el->r->level - 1;
243 }
244 }
245 }
246
247 /* XXX: the algorithm can be improved. We can calculate the set of
248 * reflines used in each interval of addresses and store them.
249 * Considering r_anal_reflines_str is always called with increasing
250 * addresses, we can just traverse linearly the list of intervals to
251 * know which reflines need to be drawn for each address. In this way,
252 * we don't need to traverse again and again the reflines for each call
253 * to r_anal_reflines_str, but we can reuse the data already
254 * calculated. Those data will be quickly available because the
255 * intervals will be sorted and the addresses to consider are always
256 * increasing. */
257 free (free_levels);
258 r_list_free (sten);
259 return list;
260
261 sten_err:
262 list_err:
263 r_list_free (sten);
264 r_list_free (list);
265 return NULL;
266 }
267
r_anal_reflines_middle(RAnal * a,RList * list,ut64 addr,int len)268 R_API int r_anal_reflines_middle(RAnal *a, RList* /*<RAnalRefline>*/ list, ut64 addr, int len) {
269 if (a && list) {
270 RAnalRefline *ref;
271 RListIter *iter;
272 r_list_foreach (list, iter, ref) {
273 if ((ref->to > addr) && (ref->to < addr + len)) {
274 return true;
275 }
276 }
277 }
278 return false;
279 }
280
get_corner_char(RAnalRefline * ref,ut64 addr,bool is_middle_before)281 static const char* get_corner_char(RAnalRefline *ref, ut64 addr, bool is_middle_before) {
282 if (ref->from == ref->to) {
283 return "@";
284 }
285 if (addr == ref->to) {
286 if (is_middle_before) {
287 return (ref->from > ref->to) ? " " : "|";
288 }
289 return (ref->from > ref->to) ? "." : "`";
290 }
291 if (addr == ref->from) {
292 if (is_middle_before) {
293 return (ref->from > ref->to) ? "|" : " ";
294 }
295 return (ref->from > ref->to) ? "`" : ",";
296 }
297 return "";
298 }
299
add_spaces(RBuffer * b,int level,int pos,bool wide)300 static void add_spaces(RBuffer *b, int level, int pos, bool wide) {
301 if (pos != -1) {
302 if (wide) {
303 pos *= 2;
304 level *= 2;
305 }
306 if (pos > level + 1) {
307 const char *pd = r_str_pad (' ', pos - level - 1);
308 r_buf_append_string (b, pd);
309 }
310 }
311 }
312
fill_level(RBuffer * b,int pos,char ch,RAnalRefline * r,bool wide)313 static void fill_level(RBuffer *b, int pos, char ch, RAnalRefline *r, bool wide) {
314 int sz = r->level;
315 if (wide) {
316 sz *= 2;
317 }
318 const char *pd = r_str_pad (ch, sz - 1);
319 if (pos == -1) {
320 r_buf_append_string (b, pd);
321 } else {
322 int pdlen = strlen (pd);
323 if (pdlen > 0) {
324 r_buf_write_at (b, pos, (const ut8 *)pd, pdlen);
325 }
326 }
327 }
328
refline_kept(RAnalRefline * ref,bool middle_after,ut64 addr)329 static inline bool refline_kept(RAnalRefline *ref, bool middle_after, ut64 addr) {
330 if (middle_after) {
331 if (ref->direction < 0) {
332 if (ref->from == addr) {
333 return false;
334 }
335 } else {
336 if (ref->to == addr) {
337 return false;
338 }
339 }
340 }
341 return true;
342 }
343
344 // TODO: move into another file
345 // TODO: this is TOO SLOW. do not iterate over all reflines or gtfo
r_anal_reflines_str(void * _core,ut64 addr,int opts)346 R_API RAnalRefStr *r_anal_reflines_str(void *_core, ut64 addr, int opts) {
347 RCore *core = _core;
348 RCons *cons = core->cons;
349 RAnal *anal = core->anal;
350 RBuffer *b;
351 RBuffer *c;
352 RListIter *iter;
353 RAnalRefline *ref;
354 int l;
355 bool wide = opts & R_ANAL_REFLINE_TYPE_WIDE;
356 int dir = 0, pos = -1, max_level = -1;
357 bool middle_before = opts & R_ANAL_REFLINE_TYPE_MIDDLE_BEFORE;
358 bool middle_after = opts & R_ANAL_REFLINE_TYPE_MIDDLE_AFTER;
359 char *str = NULL;
360 char *col_str = NULL;
361
362 r_return_val_if_fail (cons && anal && anal->reflines, NULL);
363
364 RList *lvls = r_list_new ();
365 if (!lvls) {
366 return NULL;
367 }
368 r_list_foreach (anal->reflines, iter, ref) {
369 if (core->cons && core->cons->context->breaked) {
370 r_list_free (lvls);
371 return NULL;
372 }
373 if (in_refline (addr, ref) && refline_kept (ref, middle_after, addr)) {
374 r_list_add_sorted (lvls, (void *)ref, (RListComparator)cmp_by_ref_lvl);
375 }
376 }
377 b = r_buf_new ();
378 c = r_buf_new ();
379 r_buf_append_string (c, " ");
380 r_buf_append_string (b, " ");
381 r_list_foreach (lvls, iter, ref) {
382 if (core->cons && core->cons->context->breaked) {
383 r_list_free (lvls);
384 r_buf_free (b);
385 r_buf_free (c);
386 return NULL;
387 }
388 if ((ref->from == addr || ref->to == addr) && !middle_after) {
389 const char *corner = get_corner_char (ref, addr, middle_before);
390 const char ch = ref->from == addr ? '=' : '-';
391 const char ch_col = ref->from >= ref->to ? 't': 'd';
392 const char *col = (ref->from >= ref->to) ? "t" : "d";
393 if (!pos) {
394 int ch_pos = max_level + 1 - ref->level;
395 if (wide) {
396 ch_pos = ch_pos * 2 - 1;
397 }
398 r_buf_write_at (b, ch_pos, (ut8 *)corner, 1);
399 r_buf_write_at (c, ch_pos, (ut8 *)col, 1);
400 fill_level (b, ch_pos + 1, ch, ref, wide);
401 fill_level (c, ch_pos + 1, ch_col, ref, wide);
402 } else {
403 add_spaces (b, ref->level, pos, wide);
404 add_spaces (c, ref->level, pos, wide);
405 r_buf_append_string (b, corner);
406 r_buf_append_string (c, col);
407 if (!middle_before) {
408 fill_level (b, -1, ch, ref, wide);
409 fill_level (c, -1, ch_col, ref, wide);
410 }
411 }
412 if (!middle_before) {
413 dir = ref->to == addr ? 1 : 2;
414 }
415 pos = middle_before ? ref->level : 0;
416 } else {
417 if (!pos) {
418 continue;
419 }
420 add_spaces (b, ref->level, pos, wide);
421 add_spaces (c, ref->level, pos, wide);
422 if (ref->from >= ref->to) {
423 r_buf_append_string (b, ":");
424 r_buf_append_string (c, "t");
425 } else {
426 r_buf_append_string (b, "|");
427 r_buf_append_string (c, "d");
428 }
429 pos = ref->level;
430 }
431 if (max_level == -1) {
432 max_level = ref->level;
433 }
434 }
435 add_spaces (c, 0, pos, wide);
436 add_spaces (b, 0, pos, wide);
437 str = r_buf_to_string (b);
438 col_str = r_buf_to_string (c);
439 r_buf_free (b);
440 r_buf_free (c);
441 b = NULL;
442 c = NULL;
443 if (!str || !col_str) {
444 r_list_free (lvls);
445 //r_buf_free_to_string already free b and if that is the case
446 //b will be NULL and r_buf_free will return but if there was
447 //an error we free b here so in other words is safe
448 r_buf_free (b);
449 r_buf_free (c);
450 return NULL;
451 }
452 if (core->anal->lineswidth > 0) {
453 int lw = core->anal->lineswidth;
454 l = strlen (str);
455 if (l > lw) {
456 r_str_cpy (str, str + l - lw);
457 r_str_cpy (col_str, col_str + l - lw);
458 } else {
459 char pfx[128];
460 lw -= l;
461 memset (pfx, ' ', sizeof (pfx));
462 if (lw >= sizeof (pfx)) {
463 lw = sizeof (pfx)-1;
464 }
465 if (lw > 0) {
466 pfx[lw] = 0;
467 str = r_str_prepend (str, pfx);
468 col_str = r_str_prepend (col_str, pfx);
469 }
470 }
471 }
472 const char prev_col = col_str[strlen (col_str) - 1];
473 const char *arr_col = prev_col == 't' ? "tt ": "dd ";
474 str = r_str_append (str, (dir == 1) ? "-> "
475 : (dir == 2) ? "=< " : " ");
476 col_str = r_str_append (col_str, arr_col);
477
478 r_list_free (lvls);
479 RAnalRefStr *out = R_NEW0 (RAnalRefStr);
480 out->str = str;
481 out->cols = col_str;
482 return out;
483 }
484
r_anal_reflines_str_free(RAnalRefStr * refstr)485 R_API void r_anal_reflines_str_free(RAnalRefStr *refstr) {
486 free (refstr->str);
487 free (refstr->cols);
488 free (refstr);
489 }
490