1 /* radare - LGPL - Copyright 2019 - condret */
2
3 //#include <r_util.h>
4 #include <r_anal.h>
5 //#include <r_reg.h>
6 //#include <sdb.h>
7
8 typedef struct esil_dfg_reg_var_t {
9 ut32 from;
10 ut32 to;
11 RGraphNode *node;
12 } EsilDFGRegVar;
13
14 typedef struct r_anal_esil_dfg_filter_t {
15 RAnalEsilDFG *dfg;
16 RContRBTree *tree;
17 Sdb *results;
18 } RAnalEsilDFGFilter;
19
20 typedef struct r_anal_esil_dfg_const_reducer_t {
21 RAnalEsilDFGFilter filter;
22 RContRBTree *const_result_gnodes;
23 } RAnalEsilDFGConstReducer;
24
25 // TODO: simple const propagation - use node->type of srcs to propagate consts of pushed vars
26
r_anal_esil_dfg_node_new(RAnalEsilDFG * edf,const char * c)27 R_API RAnalEsilDFGNode *r_anal_esil_dfg_node_new(RAnalEsilDFG *edf, const char *c) {
28 RAnalEsilDFGNode *ret = R_NEW0 (RAnalEsilDFGNode);
29 ret->content = r_strbuf_new (c);
30 ret->idx = edf->idx++;
31 return ret;
32 }
33
_dfg_node_free(RAnalEsilDFGNode * free_me)34 static void _dfg_node_free(RAnalEsilDFGNode *free_me) {
35 if (free_me) {
36 r_strbuf_free (free_me->content);
37 free (free_me);
38 }
39 }
40
_rv_del_alloc_cmp(void * incoming,void * in,void * user)41 static int _rv_del_alloc_cmp(void *incoming, void *in, void *user) {
42 EsilDFGRegVar *rv_incoming = (EsilDFGRegVar *)incoming;
43 EsilDFGRegVar *rv_in = (EsilDFGRegVar *)in;
44 RAnalEsilDFG *dfg = (RAnalEsilDFG *)user;
45
46 if (dfg->malloc_failed) {
47 return -1;
48 }
49
50 // first handle the simple cases without intersection
51 if (rv_incoming->to < rv_in->from) {
52 return -1;
53 }
54 if (rv_in->to < rv_incoming->from) {
55 return 1;
56 }
57 if (rv_in->from == rv_incoming->from && rv_in->to == rv_incoming->to) {
58 return 0;
59 }
60
61 /*
62 the following cases are about intersection, here some ascii-art, so you understand what I do
63
64 =incoming=
65 =========in=========
66
67 split in into 2 and reinsert the second half (in2)
68 shrink first half (in1)
69
70 =incoming=
71 =in1= =in2=
72 */
73
74 if (rv_in->from < rv_incoming->from && rv_incoming->to < rv_in->to) {
75 EsilDFGRegVar *rv = R_NEW (EsilDFGRegVar);
76 if (!rv) {
77 dfg->malloc_failed = true;
78 return -1;
79 }
80 rv[0] = rv_in[0];
81 rv_in->to = rv_incoming->from - 1;
82 rv->from = rv_incoming->to + 1;
83 dfg->insert = rv;
84 return 1;
85 }
86
87 /*
88 =incoming=
89 =in=
90
91 enqueue the non-intersecting ends in the todo-queue
92 */
93
94 if (rv_incoming->from < rv_in->from && rv_in->to < rv_incoming->to) {
95 // lower part
96 EsilDFGRegVar *rv = R_NEW (EsilDFGRegVar);
97 if (!rv) {
98 dfg->malloc_failed = true;
99 return -1;
100 }
101 rv[0] = rv_incoming[0];
102 rv->to = rv_in->from - 1;
103 r_queue_enqueue (dfg->todo, rv);
104 // upper part
105 rv = R_NEW (EsilDFGRegVar);
106 if (!rv) {
107 dfg->malloc_failed = true;
108 return -1;
109 }
110 rv[0] = rv_incoming[0];
111 rv->from = rv_in->to + 1;
112 r_queue_enqueue (dfg->todo, rv);
113 return 0;
114 }
115
116 /*
117 =incoming=
118 =in=
119
120 similar to the previous case, but this time only enqueue 1 half
121 */
122
123 if (rv_incoming->from == rv_in->from && rv_in->to < rv_incoming->to) {
124 EsilDFGRegVar *rv = R_NEW (EsilDFGRegVar);
125 if (!rv) {
126 dfg->malloc_failed = true;
127 return -1;
128 }
129 rv[0] = rv_incoming[0];
130 rv->from = rv_in->to + 1;
131 r_queue_enqueue (dfg->todo, rv);
132 return 0;
133 }
134
135 /*
136 =incoming=
137 =in=
138 */
139
140 if (rv_incoming->from < rv_in->from && rv_in->to == rv_incoming->to) {
141 EsilDFGRegVar *rv = R_NEW (EsilDFGRegVar);
142 if (!rv) {
143 dfg->malloc_failed = true;
144 return -1;
145 }
146 rv[0] = rv_incoming[0];
147 rv->to = rv_in->from - 1;
148 r_queue_enqueue (dfg->todo, rv);
149 return 0;
150 }
151
152 /*
153 =incoming=
154 ===in===
155
156 shrink in
157
158 =incoming=
159 =in=
160 */
161
162 if (rv_in->to <= rv_incoming->to) {
163 rv_in->to = rv_incoming->from - 1;
164 return 1;
165 }
166
167 /*
168 =incoming=
169 ===in===
170
171 up-shrink in
172
173 =incoming=
174 ==in==
175 */
176
177 rv_in->from = rv_incoming->to + 1;
178 return -1;
179 }
180
_rv_ins_cmp(void * incoming,void * in,void * user)181 static int _rv_ins_cmp(void *incoming, void *in, void *user) {
182 EsilDFGRegVar *rv_incoming = (EsilDFGRegVar *)incoming;
183 EsilDFGRegVar *rv_in = (EsilDFGRegVar *)in;
184 return rv_incoming->from - rv_in->from;
185 }
186
_edf_reg_set(RAnalEsilDFG * dfg,const char * reg,RGraphNode * node)187 static bool _edf_reg_set(RAnalEsilDFG *dfg, const char *reg, RGraphNode *node) {
188 r_return_val_if_fail (dfg && !dfg->malloc_failed && reg, false);
189 char *_reg = r_str_newf ("reg.%s", reg);
190 if (!sdb_num_exists (dfg->regs, _reg)) {
191 //no assert to prevent memleaks
192 free (_reg);
193 return false;
194 }
195 EsilDFGRegVar *rv = R_NEW0 (EsilDFGRegVar);
196 if (!rv) {
197 free (_reg);
198 return false;
199 }
200
201 const ut64 v = sdb_num_get (dfg->regs, _reg, NULL);
202 free (_reg);
203 rv->from = (v & (UT64_MAX ^ UT32_MAX)) >> 32;
204 rv->to = v & UT32_MAX;
205 r_queue_enqueue (dfg->todo, rv);
206 while (!r_queue_is_empty (dfg->todo) && !dfg->malloc_failed) {
207 // rbtree api does sadly not allow deleting multiple items at once :(
208 rv = r_queue_dequeue (dfg->todo);
209 r_rbtree_cont_delete (dfg->reg_vars, rv, _rv_del_alloc_cmp, dfg);
210 if (dfg->insert && !dfg->malloc_failed) {
211 r_rbtree_cont_insert (dfg->reg_vars, dfg->insert, _rv_ins_cmp, NULL);
212 dfg->insert = NULL;
213 }
214 free (rv);
215 }
216 if (dfg->malloc_failed) {
217 while (!r_queue_is_empty (dfg->todo)) {
218 free (r_queue_dequeue (dfg->todo));
219 }
220 return false;
221 }
222 rv = R_NEW0 (EsilDFGRegVar);
223 rv->from = (v & (UT64_MAX ^ UT32_MAX)) >> 32;
224 rv->to = v & UT32_MAX;
225 rv->node = node;
226 r_rbtree_cont_insert (dfg->reg_vars, rv, _rv_ins_cmp, NULL);
227 return true;
228 }
229
_rv_find_cmp(void * incoming,void * in,void * user)230 static int _rv_find_cmp(void *incoming, void *in, void *user) {
231 EsilDFGRegVar *rv_incoming = (EsilDFGRegVar *)incoming;
232 EsilDFGRegVar *rv_in = (EsilDFGRegVar *)in;
233
234 RAnalEsilDFG *dfg = (RAnalEsilDFG *)user;
235 if (dfg->malloc_failed) {
236 return -1;
237 }
238
239 // first handle the simple cases without intersection
240 if (rv_incoming->to < rv_in->from) {
241 return -1;
242 }
243 if (rv_in->to < rv_incoming->from) {
244 return 1;
245 }
246
247 /*
248 =incoming=
249 =========in=========
250 */
251 if (rv_in->from <= rv_incoming->from && rv_incoming->to <= rv_in->to) {
252 return 0;
253 }
254
255 /*
256 =incoming=
257 =in=
258
259 enqueue the non-intersecting ends in the todo-queue
260 */
261 if (rv_incoming->from < rv_in->from && rv_in->to < rv_incoming->to) {
262 // lower part
263 EsilDFGRegVar *rv = R_NEW (EsilDFGRegVar);
264 if (!rv) {
265 dfg->malloc_failed = true;
266 return -1;
267 }
268 rv[0] = rv_incoming[0];
269 rv->to = rv_in->from - 1;
270 r_queue_enqueue (dfg->todo, rv);
271 // upper part
272 rv = R_NEW (EsilDFGRegVar);
273 if (!rv) {
274 dfg->malloc_failed = true;
275 return -1;
276 }
277 rv[0] = rv_incoming[0];
278 rv->from = rv_in->to + 1;
279 r_queue_enqueue (dfg->todo, rv);
280 return 0;
281 }
282
283 /*
284 =incoming=
285 =in=
286
287 similar to the previous case, but this time only enqueue 1 half
288 */
289 if (rv_in->from <= rv_incoming->from && rv_in->to < rv_incoming->to) {
290 EsilDFGRegVar *rv = R_NEW (EsilDFGRegVar);
291 if (!rv) {
292 dfg->malloc_failed = true;
293 return -1;
294 }
295 rv[0] = rv_incoming[0];
296 rv->from = rv_in->to + 1;
297 r_queue_enqueue (dfg->todo, rv);
298 return 0;
299 }
300
301 /*
302 =incoming=
303 =in=
304 */
305 EsilDFGRegVar *rv = R_NEW (EsilDFGRegVar);
306 if (!rv) {
307 dfg->malloc_failed = true;
308 return -1;
309 }
310 rv[0] = rv_incoming[0];
311 rv->to = rv_in->from - 1;
312 r_queue_enqueue (dfg->todo, rv);
313 return 0;
314 }
315
_edf_origin_reg_get(RAnalEsilDFG * dfg,const char * reg)316 static RGraphNode *_edf_origin_reg_get(RAnalEsilDFG *dfg, const char *reg) {
317 r_return_val_if_fail (dfg && reg, NULL);
318 char *_reg = r_str_newf ("reg.%s", reg);
319 if (!sdb_num_exists (dfg->regs, _reg)) {
320 free (_reg);
321 return NULL;
322 }
323 free (_reg);
324 char *origin_reg = r_str_newf ("ori.%s", reg);
325 RGraphNode *origin_reg_node = sdb_ptr_get (dfg->regs, origin_reg, 0);
326 if (origin_reg_node) {
327 free (origin_reg);
328 return origin_reg_node;
329 }
330 RGraphNode *reg_node = r_graph_add_node (dfg->flow, r_anal_esil_dfg_node_new (dfg, reg));
331 RAnalEsilDFGNode *_origin_reg_node = r_anal_esil_dfg_node_new (dfg, reg);
332 r_strbuf_appendf (_origin_reg_node->content, ":var_%d", dfg->idx++);
333 _origin_reg_node->type = R_ANAL_ESIL_DFG_BLOCK_VAR;
334 origin_reg_node = r_graph_add_node (dfg->flow, _origin_reg_node);
335 r_graph_add_edge (dfg->flow, reg_node, origin_reg_node);
336 sdb_ptr_set (dfg->regs, origin_reg, origin_reg_node, 0);
337 free (origin_reg);
338 return origin_reg_node;
339 }
340
_edf_reg_get(RAnalEsilDFG * dfg,const char * reg)341 static RGraphNode *_edf_reg_get(RAnalEsilDFG *dfg, const char *reg) {
342 r_return_val_if_fail (dfg && reg, NULL);
343 char *_reg = r_str_newf ("reg.%s", reg);
344 if (!sdb_num_exists (dfg->regs, _reg)) {
345 free (_reg);
346 return NULL;
347 }
348 EsilDFGRegVar *rv = R_NEW0 (EsilDFGRegVar);
349 if (!rv) {
350 free (_reg);
351 return NULL;
352 }
353 const ut64 v = sdb_num_get (dfg->regs, _reg, NULL);
354 free (_reg);
355 rv->from = (v & (UT64_MAX ^ UT32_MAX)) >> 32;
356 rv->to = v & UT32_MAX;
357 RQueue *parts = r_queue_new (8);
358 if (!parts) {
359 free (rv);
360 return NULL;
361 }
362 r_queue_enqueue (dfg->todo, rv);
363
364 // log2((search_rv.to + 1) - search_rv.from) maybe better?
365 // wat du if this fails?
366
367 RGraphNode *reg_node = NULL;
368 while (!r_queue_is_empty (dfg->todo)) {
369 rv = r_queue_dequeue (dfg->todo);
370 EsilDFGRegVar *part_rv = r_rbtree_cont_find (dfg->reg_vars, rv, _rv_find_cmp, dfg);
371 if (part_rv) {
372 r_queue_enqueue (parts, part_rv->node);
373 } else if (!reg_node) {
374 reg_node = _edf_origin_reg_get (dfg, reg);
375 //insert in the gap
376 part_rv = R_NEW (EsilDFGRegVar);
377 if (!part_rv) {
378 R_FREE (rv);
379 dfg->malloc_failed = true;
380 break;
381 }
382 part_rv[0] = rv[0];
383 part_rv->node = reg_node;
384 r_rbtree_cont_insert (dfg->reg_vars, part_rv, _rv_ins_cmp, NULL);
385 //enqueue for later merge
386 r_queue_enqueue (parts, reg_node);
387 } else {
388 //initial regnode was already created
389 //only need to insert in the tree
390 part_rv = R_NEW (EsilDFGRegVar);
391 if (!part_rv) {
392 R_FREE (rv);
393 dfg->malloc_failed = true;
394 break;
395 }
396 part_rv[0] = rv[0];
397 part_rv->node = reg_node;
398 r_rbtree_cont_insert (dfg->reg_vars, part_rv, _rv_ins_cmp, NULL);
399 }
400 free (rv);
401 }
402 reg_node = NULL; // is this needed?
403 if (dfg->malloc_failed) {
404 while (!r_queue_is_empty (dfg->todo)) {
405 free (r_queue_dequeue (dfg->todo));
406 }
407 goto beach; // Outside loop!
408 }
409 switch (parts->size) {
410 case 0:
411 break;
412 case 1:
413 reg_node = r_queue_dequeue (parts);
414 break;
415 default: {
416 RAnalEsilDFGNode *_reg_node = r_anal_esil_dfg_node_new (dfg, "merge to ");
417 if (!_reg_node) {
418 while (!r_queue_is_empty (dfg->todo)) {
419 free (r_queue_dequeue (dfg->todo));
420 }
421 dfg->malloc_failed = true;
422 goto beach;
423 }
424
425 r_strbuf_appendf (_reg_node->content, "%s:var_%d", reg, dfg->idx++);
426 reg_node = r_graph_add_node (dfg->flow, _reg_node);
427 if (!reg_node) {
428 _dfg_node_free (_reg_node);
429 while (!r_queue_is_empty (dfg->todo)) {
430 free (r_queue_dequeue (dfg->todo));
431 }
432 dfg->malloc_failed = true;
433 goto beach;
434 }
435 }
436 do {
437 r_graph_add_edge (dfg->flow, r_queue_dequeue (parts), reg_node);
438 } while (!r_queue_is_empty (parts));
439 break;
440 }
441 beach:
442 r_queue_free (parts);
443 return reg_node;
444 }
445
_edf_var_set(RAnalEsilDFG * dfg,const char * var,RGraphNode * node)446 static bool _edf_var_set(RAnalEsilDFG *dfg, const char *var, RGraphNode *node) {
447 r_return_val_if_fail (dfg && var, false);
448 char *_var = r_str_newf ("var.%s", var);
449 const bool ret = !sdb_ptr_set (dfg->regs, _var, node, 0);
450 free (_var);
451 return ret;
452 }
453
_edf_var_get(RAnalEsilDFG * dfg,const char * var)454 static RGraphNode *_edf_var_get(RAnalEsilDFG *dfg, const char *var) {
455 r_return_val_if_fail (dfg && var, NULL);
456 char *k = r_str_newf ("var.%s", var);
457 RGraphNode *ret = sdb_ptr_get (dfg->regs, k, NULL);
458 free (k);
459 return ret;
460 }
461
462 static bool edf_consume_2_set_reg(RAnalEsil *esil);
463 static bool edf_consume_2_push_1(RAnalEsil *esil);
464 static bool edf_consume_1_push_1(RAnalEsil *esil);
465 typedef void (*AddConstraintStringUseNewCB) (RStrBuf *result, const char *new_node_str);
466 static bool edf_use_new_push_1(RAnalEsil *esil, const char *op_string, AddConstraintStringUseNewCB cb);
467 typedef void (*AddConstraintStringConsume1UseOldNewCB) (RStrBuf *result, const char *consume_str, const char *old_node_str, const char *new_node_str);
468 static bool edf_consume_1_use_old_new_push_1(RAnalEsil *esil, const char *op_string, AddConstraintStringConsume1UseOldNewCB cb);
469
edf_eq_weak(RAnalEsil * esil)470 static bool edf_eq_weak(RAnalEsil *esil) {
471 RAnalEsilDFG *edf = (RAnalEsilDFG *)esil->user;
472 RGraphNode *o_old = edf->old; //node for esil->old
473 RGraphNode *o_new = edf->cur; //node for esil->cur
474 if (!edf_consume_2_set_reg (esil)) {
475 return false;
476 }
477 //work-around
478 edf->old = o_old ? o_old : NULL;
479 edf->cur = o_new ? o_new : NULL;
480 return true;
481 }
482
edf_zf_constraint(RStrBuf * result,const char * new_node_str)483 static void edf_zf_constraint(RStrBuf *result, const char *new_node_str) {
484 r_strbuf_appendf (result, ":(%s==0)", new_node_str);
485 }
486
edf_zf(RAnalEsil * esil)487 static bool edf_zf(RAnalEsil *esil) {
488 return edf_use_new_push_1 (esil, "$z", edf_zf_constraint);
489 }
490
edf_pf_constraint(RStrBuf * result,const char * new_node_str)491 static void edf_pf_constraint(RStrBuf *result, const char *new_node_str) {
492 r_strbuf_appendf (result, ":parity_of(%s)", new_node_str);
493 }
494
edf_pf(RAnalEsil * esil)495 static bool edf_pf(RAnalEsil *esil) {
496 return edf_use_new_push_1 (esil, "$p", edf_pf_constraint);
497 }
498
edf_cf_constraint(RStrBuf * result,const char * consume,const char * o,const char * n)499 static void edf_cf_constraint(RStrBuf *result, const char *consume, const char *o, const char *n) {
500 r_strbuf_appendf (result, ":((%s&mask(%s&0x3f))<(%s&mask(%s&0x3f)))",
501 n, consume, o, consume);
502 }
503
edf_cf(RAnalEsil * esil)504 static bool edf_cf(RAnalEsil *esil) {
505 return edf_consume_1_use_old_new_push_1 (esil, "$c", edf_cf_constraint);
506 }
507
edf_bf_constraint(RStrBuf * result,const char * consume,const char * o,const char * n)508 static void edf_bf_constraint(RStrBuf *result, const char *consume, const char *o, const char *n) {
509 r_strbuf_appendf (result, ":((%s&mask((%s+0x3f)&0x3f))<(%s& mask((%s+0x3f)&0x3f)))",
510 o, consume, n, consume);
511 }
512
edf_bf(RAnalEsil * esil)513 static bool edf_bf(RAnalEsil *esil) {
514 return edf_consume_1_use_old_new_push_1 (esil, "$b", edf_bf_constraint);
515 }
516
_edf_consume_2_set_reg(RAnalEsil * esil,const bool use_origin)517 static bool _edf_consume_2_set_reg(RAnalEsil *esil, const bool use_origin) {
518 const char *op_string = esil->current_opstr;
519 RAnalEsilDFG *edf = (RAnalEsilDFG *)esil->user;
520 char *dst = r_anal_esil_pop (esil);
521 char *src = r_anal_esil_pop (esil);
522
523 if (!src || !dst) {
524 free (dst);
525 free (src);
526 return false;
527 }
528
529 int dst_type = r_anal_esil_get_parm_type (esil, dst);
530 if (dst_type == R_ANAL_ESIL_PARM_INVALID) {
531 free (dst);
532 free (src);
533 return false;
534 }
535
536 const int src_type = r_anal_esil_get_parm_type (esil, src);
537 RGraphNode *src_node = NULL;
538 if (src_type == R_ANAL_ESIL_PARM_REG) {
539 src_node = _edf_reg_get (edf, src);
540 } else if (src_type == R_ANAL_ESIL_PARM_NUM) {
541 RGraphNode *n_value = r_graph_add_node (edf->flow, r_anal_esil_dfg_node_new (edf, src));
542 RAnalEsilDFGNode *ec_node = r_anal_esil_dfg_node_new (edf, src);
543 ec_node->type = R_ANAL_ESIL_DFG_BLOCK_CONST;
544 r_strbuf_appendf (ec_node->content, ":const_%d", edf->idx++);
545 src_node = r_graph_add_node (edf->flow, ec_node);
546 r_graph_add_edge (edf->flow, n_value, src_node);
547 } else {
548 src_node = _edf_var_get (edf, src);
549 }
550
551 RGraphNode *dst_node = use_origin ? _edf_origin_reg_get (edf, dst) : _edf_reg_get (edf, dst);
552 RGraphNode *old_dst_node = dst_node;
553
554 if (!src_node || !dst_node) {
555 free (src);
556 free (dst);
557 return false;
558 }
559
560 RAnalEsilDFGNode *eop_node = r_anal_esil_dfg_node_new (edf, src);
561 r_strbuf_appendf (eop_node->content, ",%s,%s", dst, op_string);
562 eop_node->type = R_ANAL_ESIL_DFG_BLOCK_GENERATIVE;
563 free (src);
564
565 RGraphNode *op_node = r_graph_add_node (edf->flow, eop_node);
566 r_graph_add_edge (edf->flow, dst_node, op_node);
567 r_graph_add_edge (edf->flow, src_node, op_node);
568 edf->old = old_dst_node;
569 RAnalEsilDFGNode *result = r_anal_esil_dfg_node_new (edf, dst);
570 result->type = R_ANAL_ESIL_DFG_BLOCK_RESULT | R_ANAL_ESIL_DFG_BLOCK_VAR;
571
572 r_strbuf_appendf (result->content, ":var_%d", edf->idx++);
573 dst_node = r_graph_add_node (edf->flow, result);
574 r_graph_add_edge (edf->flow, op_node, dst_node);
575 _edf_reg_set (edf, dst, dst_node);
576 edf->cur = dst_node;
577 free (dst);
578 return true;
579 }
580
edf_consume_2_use_set_reg(RAnalEsil * esil)581 static bool edf_consume_2_use_set_reg(RAnalEsil *esil) {
582 return _edf_consume_2_set_reg (esil, false);
583 }
584
edf_consume_2_set_reg(RAnalEsil * esil)585 static bool edf_consume_2_set_reg(RAnalEsil *esil) {
586 return _edf_consume_2_set_reg (esil, true);
587 }
588
edf_consume_2_push_1(RAnalEsil * esil)589 static bool edf_consume_2_push_1(RAnalEsil *esil) {
590 const char *op_string = esil->current_opstr;
591 RAnalEsilDFG *edf = (RAnalEsilDFG *)esil->user;
592 char *src[2] = { r_anal_esil_pop (esil), r_anal_esil_pop (esil) };
593
594 if (!src[0] || !src[1]) {
595 free (src[0]);
596 free (src[1]);
597 return false;
598 }
599 RAnalEsilDFGNode *eop_node = r_anal_esil_dfg_node_new (edf, src[1]);
600 r_strbuf_appendf (eop_node->content, ",%s,%s", src[0], op_string);
601 eop_node->type = R_ANAL_ESIL_DFG_BLOCK_RESULT | R_ANAL_ESIL_DFG_BLOCK_GENERATIVE;
602 RGraphNode *op_node = r_graph_add_node (edf->flow, eop_node);
603 RGraphNode *src_node[2];
604 bool const_result = true;
605 ut32 i;
606 for (i = 0; i < 2; i++) {
607 const int src_type = r_anal_esil_get_parm_type (esil, src[i]);
608 if (src_type == R_ANAL_ESIL_PARM_REG) {
609 src_node[i] = _edf_reg_get (edf, src[i]);
610 const_result = false;
611 } else if (src_type == R_ANAL_ESIL_PARM_NUM) {
612 RGraphNode *n_value = r_graph_add_node (edf->flow, r_anal_esil_dfg_node_new (edf, src[i]));
613 RAnalEsilDFGNode *ec_node = r_anal_esil_dfg_node_new (edf, src[i]);
614 ec_node->type = R_ANAL_ESIL_DFG_BLOCK_CONST;
615 r_strbuf_appendf (ec_node->content, ":const_%d", edf->idx++);
616 src_node[i] = r_graph_add_node (edf->flow, ec_node);
617 r_graph_add_edge (edf->flow, n_value, src_node[i]);
618 // todo: check op_type, not relevant for now since this is always OP_MATH atm
619 const_result &= true;
620 } else {
621 src_node[i] = _edf_var_get (edf, src[i]);
622 RAnalEsilDFGNode *ec_node = (RAnalEsilDFGNode *)src_node[i]->data;
623 const_result &= !!(ec_node->type & R_ANAL_ESIL_DFG_BLOCK_CONST);
624 }
625 r_graph_add_edge (edf->flow, src_node[i], op_node);
626 }
627
628 free (src[0]);
629 free (src[1]);
630
631 RAnalEsilDFGNode *result = r_anal_esil_dfg_node_new (edf, "result_");
632 result->type = R_ANAL_ESIL_DFG_BLOCK_RESULT;
633 if (const_result) {
634 result->type |= R_ANAL_ESIL_DFG_BLOCK_CONST;
635 }
636 r_strbuf_appendf (result->content, "%d", edf->idx++);
637 RGraphNode *result_node = r_graph_add_node (edf->flow, result);
638 r_graph_add_edge (edf->flow, op_node, result_node);
639 _edf_var_set (edf, r_strbuf_get (result->content), result_node);
640 r_anal_esil_push (esil, r_strbuf_get (result->content));
641 return true;
642 }
643
edf_consume_1_push_1(RAnalEsil * esil)644 static bool edf_consume_1_push_1(RAnalEsil *esil) {
645 const char *op_string = esil->current_opstr;
646 RAnalEsilDFG *edf = (RAnalEsilDFG *)esil->user;
647 char *src = r_anal_esil_pop (esil);
648 if (!src) {
649 return false;
650 }
651 RAnalEsilDFGNode *eop_node = r_anal_esil_dfg_node_new (edf, src);
652 r_strbuf_appendf (eop_node->content, ",%s", op_string);
653 eop_node->type = R_ANAL_ESIL_DFG_BLOCK_RESULT | R_ANAL_ESIL_DFG_BLOCK_GENERATIVE;
654 // esil operation node
655 RGraphNode *op_node = r_graph_add_node (edf->flow, eop_node);
656 // operation node, but in the rgraph
657 const int src_type = r_anal_esil_get_parm_type (esil, src);
658 RGraphNode *src_node = NULL;
659 bool const_result = false;
660 // is the result a const value?
661 // e.g.: 42,!,!,! => 0,!,! => 1,! => 0 => const_result
662 // 0xaabbccdd,[1] => not const result, bc memory read
663 const ut32 eop_type = ((RAnalEsilOp *)ht_pp_find (esil->ops, op_string, NULL))->type;
664 // no need to check pointer here, bc this cannot fail if this function got called
665 if (src_type == R_ANAL_ESIL_PARM_REG) {
666 src_node = _edf_reg_get (edf, src);
667 } else if (src_type == R_ANAL_ESIL_PARM_NUM) {
668 RGraphNode *n_value = r_graph_add_node (edf->flow, r_anal_esil_dfg_node_new (edf, src));
669 RAnalEsilDFGNode *ec_node = r_anal_esil_dfg_node_new (edf, src);
670 ec_node->type = R_ANAL_ESIL_DFG_BLOCK_CONST;
671 r_strbuf_appendf (ec_node->content, ":const_%d", edf->idx++);
672 src_node = r_graph_add_node (edf->flow, ec_node);
673 r_graph_add_edge (edf->flow, n_value, src_node);
674 const_result = (eop_type == R_ANAL_ESIL_OP_TYPE_MATH);
675 } else {
676 src_node = _edf_var_get (edf, src);
677 // cannot fail, bc src cannot be NULL
678 RAnalEsilDFGNode *ec_node = (RAnalEsilDFGNode *)src_node->data;
679 const_result = (eop_type == R_ANAL_ESIL_OP_TYPE_MATH) & !!(ec_node->type & R_ANAL_ESIL_DFG_BLOCK_CONST);
680 }
681
682 free (src);
683
684 r_graph_add_edge (edf->flow, src_node, op_node);
685
686 RAnalEsilDFGNode *result = r_anal_esil_dfg_node_new (edf, "result_");
687 result->type = R_ANAL_ESIL_DFG_BLOCK_RESULT;
688 if (const_result) {
689 result->type |= R_ANAL_ESIL_DFG_BLOCK_CONST;
690 }
691 r_strbuf_appendf (result->content, "%d", edf->idx++);
692 RGraphNode *result_node = r_graph_add_node (edf->flow, result);
693 r_graph_add_edge (edf->flow, op_node, result_node);
694 _edf_var_set (edf, r_strbuf_get (result->content), result_node);
695 r_anal_esil_push (esil, r_strbuf_get (result->content));
696 return true;
697 }
698
edf_consume_2_set_mem(RAnalEsil * esil)699 static bool edf_consume_2_set_mem(RAnalEsil *esil) {
700 const char *op_string = esil->current_opstr;
701 RAnalEsilDFG *edf = (RAnalEsilDFG *)esil->user;
702 char *dst = r_anal_esil_pop (esil);
703 char *src = r_anal_esil_pop (esil);
704
705 if (!src || !dst) {
706 free (dst);
707 free (src);
708 return 0;
709 }
710
711 int dst_type = r_anal_esil_get_parm_type (esil, dst);
712
713 const int src_type = r_anal_esil_get_parm_type (esil, src);
714 RGraphNode *src_node = NULL;
715 if (src_type == R_ANAL_ESIL_PARM_REG) {
716 src_node = _edf_reg_get (edf, src);
717 } else if (src_type == R_ANAL_ESIL_PARM_NUM) {
718 RGraphNode *n_value = r_graph_add_node (edf->flow, r_anal_esil_dfg_node_new (edf, src));
719 RAnalEsilDFGNode *ec_node = r_anal_esil_dfg_node_new (edf, src);
720 ec_node->type = R_ANAL_ESIL_DFG_BLOCK_CONST;
721 r_strbuf_appendf (ec_node->content, ":const_%d", edf->idx++);
722 src_node = r_graph_add_node (edf->flow, ec_node);
723 r_graph_add_edge (edf->flow, n_value, src_node);
724 } else {
725 src_node = _edf_var_get (edf, src);
726 }
727
728 RGraphNode *dst_node = _edf_reg_get (edf, dst);
729 if (!dst_node) {
730 dst_node = _edf_var_get (edf, dst);
731 }
732 //probably dead code
733 if (!dst_node) {
734 if (dst_type == R_ANAL_ESIL_PARM_REG) {
735 RGraphNode *n_reg = r_graph_add_node (edf->flow, r_anal_esil_dfg_node_new (edf, dst));
736 RAnalEsilDFGNode *ev_node = r_anal_esil_dfg_node_new (edf, dst);
737 ev_node->type = R_ANAL_ESIL_DFG_BLOCK_VAR | R_ANAL_ESIL_DFG_BLOCK_PTR;
738 r_strbuf_appendf (ev_node->content, ":var_ptr_%d", edf->idx++);
739 dst_node = r_graph_add_node (edf->flow, ev_node);
740 // _edf_reg_set (edf, dst, ev_node);
741 r_graph_add_edge (edf->flow, n_reg, dst_node);
742 }
743 // TODO: const pointers
744 }
745
746 if (!src_node || !dst_node) {
747 free (src);
748 free (dst);
749 return false;
750 }
751
752 RAnalEsilDFGNode *eop_node = r_anal_esil_dfg_node_new (edf, src);
753 r_strbuf_appendf (eop_node->content, ",%s,%s", dst, op_string);
754 eop_node->type = R_ANAL_ESIL_DFG_BLOCK_GENERATIVE;
755 free (src);
756
757 RGraphNode *op_node = r_graph_add_node (edf->flow, eop_node);
758 r_graph_add_edge (edf->flow, dst_node, op_node);
759 r_graph_add_edge (edf->flow, src_node, op_node);
760 RAnalEsilDFGNode *result = r_anal_esil_dfg_node_new (edf, dst);
761 // result->type = R_ANAL_ESIL_DFG_BLOCK_RESULT | R_ANAL_ESIL_DFG_BLOCK_GENERATIVE;
762 result->type = R_ANAL_ESIL_DFG_BLOCK_VAR;
763 r_strbuf_appendf (result->content, ":var_mem_%d", edf->idx++);
764 dst_node = r_graph_add_node (edf->flow, result);
765 r_graph_add_edge (edf->flow, op_node, dst_node);
766 free (dst);
767 return true;
768 }
769
edf_use_new_push_1(RAnalEsil * esil,const char * op_string,AddConstraintStringUseNewCB cb)770 static bool edf_use_new_push_1(RAnalEsil *esil, const char *op_string, AddConstraintStringUseNewCB cb) {
771 RAnalEsilDFG *edf = (RAnalEsilDFG *)esil->user;
772 RGraphNode *op_node = r_graph_add_node (edf->flow, r_anal_esil_dfg_node_new (edf, op_string));
773 RGraphNode *latest_new = edf->cur;
774 if (!latest_new) {
775 return 0;
776 }
777 RAnalEsilDFGNode *result = r_anal_esil_dfg_node_new (edf, "result_");
778 result->type = R_ANAL_ESIL_DFG_BLOCK_RESULT; // is this generative?
779 r_strbuf_appendf (result->content, "%d", edf->idx++);
780 if (cb) {
781 RAnalEsilDFGNode *e_new_node = (RAnalEsilDFGNode *)latest_new->data;
782 cb (result->content, r_strbuf_get (e_new_node->content));
783 }
784 RGraphNode *result_node = r_graph_add_node (edf->flow, result);
785 _edf_var_set (edf, r_strbuf_get (result->content), result_node);
786 r_graph_add_edge (edf->flow, latest_new, op_node);
787 r_graph_add_edge (edf->flow, op_node, result_node);
788 return r_anal_esil_push (esil, r_strbuf_get (result->content));
789 }
790
edf_consume_1_use_old_new_push_1(RAnalEsil * esil,const char * op_string,AddConstraintStringConsume1UseOldNewCB cb)791 static bool edf_consume_1_use_old_new_push_1(RAnalEsil *esil, const char *op_string, AddConstraintStringConsume1UseOldNewCB cb) {
792 RAnalEsilDFG *edf = (RAnalEsilDFG *)esil->user;
793 char *src = r_anal_esil_pop (esil);
794
795 if (!src) {
796 return false;
797 }
798 RAnalEsilDFGNode *eop_node = r_anal_esil_dfg_node_new (edf, src);
799 #if 0
800 eop_node->type = R_ANAL_ESIL_DFG_BLOCK_GENERATIVE;
801 #endif
802 r_strbuf_appendf (eop_node->content, ",%s", op_string);
803 RGraphNode *op_node = r_graph_add_node (edf->flow, eop_node);
804 const int src_type = r_anal_esil_get_parm_type (esil, src);
805 RGraphNode *src_node = NULL;
806 if (src_type == R_ANAL_ESIL_PARM_REG) {
807 src_node = _edf_reg_get (edf, src);
808 } else if (src_type == R_ANAL_ESIL_PARM_NUM) {
809 RGraphNode *n_value = r_graph_add_node (edf->flow, r_anal_esil_dfg_node_new (edf, src));
810 RAnalEsilDFGNode *ec_node = r_anal_esil_dfg_node_new (edf, src);
811 ec_node->type = R_ANAL_ESIL_DFG_BLOCK_CONST;
812 r_strbuf_appendf (ec_node->content, ":const_%d", edf->idx++);
813 src_node = r_graph_add_node (edf->flow, ec_node);
814 r_graph_add_edge (edf->flow, n_value, src_node);
815 } else {
816 src_node = _edf_var_get (edf, src);
817 }
818 free (src);
819
820 r_graph_add_edge (edf->flow, src_node, op_node);
821
822 RGraphNode *latest_new = edf->cur;
823 RGraphNode *latest_old = edf->old;
824 RAnalEsilDFGNode *result = r_anal_esil_dfg_node_new (edf, "result_");
825 result->type = R_ANAL_ESIL_DFG_BLOCK_RESULT; // propagate type here
826 r_strbuf_appendf (result->content, "%d", edf->idx++);
827 if (cb) {
828 RAnalEsilDFGNode *e_src_node = (RAnalEsilDFGNode *)src_node->data;
829 RAnalEsilDFGNode *e_new_node = (RAnalEsilDFGNode *)latest_new->data;
830 RAnalEsilDFGNode *e_old_node = (RAnalEsilDFGNode *)latest_old->data;
831 cb (result->content, r_strbuf_get (e_src_node->content),
832 r_strbuf_get (e_new_node->content), r_strbuf_get (e_old_node->content));
833 }
834 RGraphNode *result_node = r_graph_add_node (edf->flow, result);
835 _edf_var_set (edf, r_strbuf_get (result->content), result_node);
836 r_graph_add_edge (edf->flow, latest_new, op_node);
837 r_graph_add_edge (edf->flow, latest_old, op_node);
838 r_graph_add_edge (edf->flow, op_node, result_node);
839 return r_anal_esil_push (esil, r_strbuf_get (result->content));
840 }
841
r_anal_esil_dfg_new(RReg * regs)842 R_API RAnalEsilDFG *r_anal_esil_dfg_new(RReg *regs) {
843 if (!regs) {
844 return NULL;
845 }
846 RAnalEsilDFG *dfg = R_NEW0 (RAnalEsilDFG);
847 if (!dfg) {
848 return NULL;
849 }
850 dfg->flow = r_graph_new ();
851 if (!dfg->flow) {
852 free (dfg);
853 return NULL;
854 }
855 dfg->regs = sdb_new0 ();
856 if (!dfg->regs) {
857 r_graph_free (dfg->flow);
858 free (dfg);
859 return NULL;
860 }
861 // rax, eax, ax, ah, al => 8 should be enough
862 dfg->todo = r_queue_new (8);
863 if (!dfg->todo) {
864 sdb_free (dfg->regs);
865 r_graph_free (dfg->flow);
866 free (dfg);
867 return NULL;
868 }
869 dfg->reg_vars = r_rbtree_cont_newf (free);
870 if (!dfg->reg_vars) {
871 r_queue_free (dfg->todo);
872 sdb_free (dfg->regs);
873 r_graph_free (dfg->flow);
874 free (dfg);
875 return NULL;
876 }
877
878 // this is not exactly necessary
879 // could use RReg-API directly in the dfg gen,
880 // but sdb as transition table is probably faster
881 RRegItem *ri;
882 RListIter *ator;
883 r_list_foreach (regs->allregs, ator, ri) {
884 const ut32 from = ri->offset;
885 const ut32 to = from + ri->size - 1; // closed intervals because of FUCK YOU
886 const ut64 v = to | (((ut64)from) << 32);
887 char *reg = r_str_newf ("reg.%s", ri->name);
888 sdb_num_set (dfg->regs, reg, v, 0);
889 free (reg);
890 }
891 return dfg;
892 }
893
r_anal_esil_dfg_free(RAnalEsilDFG * dfg)894 R_API void r_anal_esil_dfg_free(RAnalEsilDFG *dfg) {
895 if (dfg) {
896 if (dfg->flow) {
897 RGraphNode *n;
898 RListIter *iter;
899 r_list_foreach (r_graph_get_nodes (dfg->flow), iter, n) {
900 n->free = (RListFree)_dfg_node_free;
901 }
902 r_graph_free (dfg->flow);
903 }
904 sdb_free (dfg->regs);
905 r_rbtree_cont_free (dfg->reg_vars);
906 r_queue_free (dfg->todo);
907 free (dfg);
908 }
909 }
910
r_anal_esil_dfg_expr(RAnal * anal,RAnalEsilDFG * dfg,const char * expr)911 R_API RAnalEsilDFG *r_anal_esil_dfg_expr(RAnal *anal, RAnalEsilDFG *dfg, const char *expr) {
912 if (!expr) {
913 return NULL;
914 }
915 RAnalEsil *esil = r_anal_esil_new (4096, 0, 1);
916 if (!esil) {
917 return NULL;
918 }
919 esil->anal = anal;
920
921 RAnalEsilDFG *edf = dfg ? dfg : r_anal_esil_dfg_new (anal->reg);
922 if (!edf) {
923 r_anal_esil_free (esil);
924 return NULL;
925 }
926
927 r_anal_esil_set_op (esil, "=", edf_consume_2_set_reg, 0, 2, R_ANAL_ESIL_OP_TYPE_REG_WRITE);
928 r_anal_esil_set_op (esil, ":=", edf_eq_weak, 0, 2, R_ANAL_ESIL_OP_TYPE_REG_WRITE);
929 r_anal_esil_set_op (esil, "$z", edf_zf, 1, 0, R_ANAL_ESIL_OP_TYPE_UNKNOWN);
930 r_anal_esil_set_op (esil, "$p", edf_pf, 1, 0, R_ANAL_ESIL_OP_TYPE_UNKNOWN);
931 r_anal_esil_set_op (esil, "$c", edf_cf, 1, 1, R_ANAL_ESIL_OP_TYPE_UNKNOWN);
932 r_anal_esil_set_op (esil, "$b", edf_bf, 1, 1, R_ANAL_ESIL_OP_TYPE_UNKNOWN);
933 r_anal_esil_set_op (esil, "^=", edf_consume_2_use_set_reg, 0, 2, R_ANAL_ESIL_OP_TYPE_MATH | R_ANAL_ESIL_OP_TYPE_REG_WRITE);
934 r_anal_esil_set_op (esil, "-=", edf_consume_2_use_set_reg, 0, 2, R_ANAL_ESIL_OP_TYPE_MATH | R_ANAL_ESIL_OP_TYPE_REG_WRITE);
935 r_anal_esil_set_op (esil, "+=", edf_consume_2_use_set_reg, 0, 2, R_ANAL_ESIL_OP_TYPE_MATH | R_ANAL_ESIL_OP_TYPE_REG_WRITE);
936 r_anal_esil_set_op (esil, "*=", edf_consume_2_use_set_reg, 0, 2, R_ANAL_ESIL_OP_TYPE_MATH | R_ANAL_ESIL_OP_TYPE_REG_WRITE);
937 r_anal_esil_set_op (esil, "/=", edf_consume_2_use_set_reg, 0, 2, R_ANAL_ESIL_OP_TYPE_MATH | R_ANAL_ESIL_OP_TYPE_REG_WRITE);
938 r_anal_esil_set_op (esil, "&=", edf_consume_2_use_set_reg, 0, 2, R_ANAL_ESIL_OP_TYPE_MATH | R_ANAL_ESIL_OP_TYPE_REG_WRITE);
939 r_anal_esil_set_op (esil, "|=", edf_consume_2_use_set_reg, 0, 2, R_ANAL_ESIL_OP_TYPE_MATH | R_ANAL_ESIL_OP_TYPE_REG_WRITE);
940 r_anal_esil_set_op (esil, "^=", edf_consume_2_use_set_reg, 0, 2, R_ANAL_ESIL_OP_TYPE_MATH | R_ANAL_ESIL_OP_TYPE_REG_WRITE);
941 r_anal_esil_set_op (esil, "+", edf_consume_2_push_1, 1, 2, R_ANAL_ESIL_OP_TYPE_MATH);
942 r_anal_esil_set_op (esil, "-", edf_consume_2_push_1, 1, 2, R_ANAL_ESIL_OP_TYPE_MATH);
943 r_anal_esil_set_op (esil, "&", edf_consume_2_push_1, 1, 2, R_ANAL_ESIL_OP_TYPE_MATH);
944 r_anal_esil_set_op (esil, "|", edf_consume_2_push_1, 1, 2, R_ANAL_ESIL_OP_TYPE_MATH);
945 r_anal_esil_set_op (esil, "^", edf_consume_2_push_1, 1, 2, R_ANAL_ESIL_OP_TYPE_MATH);
946 r_anal_esil_set_op (esil, "%", edf_consume_2_push_1, 1, 2, R_ANAL_ESIL_OP_TYPE_MATH);
947 r_anal_esil_set_op (esil, "*", edf_consume_2_push_1, 1, 2, R_ANAL_ESIL_OP_TYPE_MATH);
948 r_anal_esil_set_op (esil, "/", edf_consume_2_push_1, 1, 2, R_ANAL_ESIL_OP_TYPE_MATH);
949 r_anal_esil_set_op (esil, ">>", edf_consume_2_push_1, 1, 2, R_ANAL_ESIL_OP_TYPE_MATH);
950 r_anal_esil_set_op (esil, "<<", edf_consume_2_push_1, 1, 2, R_ANAL_ESIL_OP_TYPE_MATH);
951 r_anal_esil_set_op (esil, ">>>", edf_consume_2_push_1, 1, 2, R_ANAL_ESIL_OP_TYPE_MATH);
952 r_anal_esil_set_op (esil, ">>>", edf_consume_2_push_1, 1, 2, R_ANAL_ESIL_OP_TYPE_MATH);
953 r_anal_esil_set_op (esil, "!", edf_consume_1_push_1, 1, 1, R_ANAL_ESIL_OP_TYPE_MATH);
954 r_anal_esil_set_op (esil, "[1]", edf_consume_1_push_1, 1, 1, R_ANAL_ESIL_OP_TYPE_MEM_READ);
955 r_anal_esil_set_op (esil, "[2]", edf_consume_1_push_1, 1, 1, R_ANAL_ESIL_OP_TYPE_MEM_READ);
956 r_anal_esil_set_op (esil, "[4]", edf_consume_1_push_1, 1, 1, R_ANAL_ESIL_OP_TYPE_MEM_READ);
957 r_anal_esil_set_op (esil, "[8]", edf_consume_1_push_1, 1, 1, R_ANAL_ESIL_OP_TYPE_MEM_READ);
958 r_anal_esil_set_op (esil, "[16]", edf_consume_1_push_1, 1, 1, R_ANAL_ESIL_OP_TYPE_MEM_READ);
959 r_anal_esil_set_op (esil, "=[1]", edf_consume_2_set_mem, 0, 2, R_ANAL_ESIL_OP_TYPE_MEM_WRITE);
960 r_anal_esil_set_op (esil, "=[2]", edf_consume_2_set_mem, 0, 2, R_ANAL_ESIL_OP_TYPE_MEM_WRITE);
961 r_anal_esil_set_op (esil, "=[4]", edf_consume_2_set_mem, 0, 2, R_ANAL_ESIL_OP_TYPE_MEM_WRITE);
962 r_anal_esil_set_op (esil, "=[8]", edf_consume_2_set_mem, 0, 2, R_ANAL_ESIL_OP_TYPE_MEM_WRITE);
963
964 esil->user = edf;
965
966 r_anal_esil_parse (esil, expr);
967 r_anal_esil_free (esil);
968 return edf;
969 }
970
_dfg_node_filter_insert_cmp(void * incoming,void * in,void * user)971 static int _dfg_node_filter_insert_cmp(void *incoming, void *in, void *user) {
972 RAnalEsilDFGNode *incoming_node = (RAnalEsilDFGNode *)incoming;
973 RAnalEsilDFGNode *in_node = (RAnalEsilDFGNode *)in;
974 return incoming_node->idx - in_node->idx;
975 }
976
_dfg_gnode_reducer_insert_cmp(void * incoming,void * in,void * user)977 static int _dfg_gnode_reducer_insert_cmp(void *incoming, void *in, void *user) {
978 RGraphNode *incoming_gnode = (RGraphNode *)incoming;
979 RGraphNode *in_gnode = (RGraphNode *)in;
980 RAnalEsilDFGNode *incoming_node = (RAnalEsilDFGNode *)incoming_gnode->data;
981 RAnalEsilDFGNode *in_node = (RAnalEsilDFGNode *)in_gnode->data;
982 return in_node->idx - incoming_node->idx;
983 }
984
_dfg_filter_rev_dfs(RGraphNode * n,RAnalEsilDFGFilter * filter)985 static void _dfg_filter_rev_dfs(RGraphNode *n, RAnalEsilDFGFilter *filter) {
986 RAnalEsilDFGNode *node = (RAnalEsilDFGNode *)n->data;
987 switch (node->type) {
988 case R_ANAL_ESIL_DFG_BLOCK_CONST:
989 case R_ANAL_ESIL_DFG_BLOCK_VAR:
990 case R_ANAL_ESIL_DFG_BLOCK_PTR:
991 break;
992 case R_ANAL_ESIL_DFG_BLOCK_GENERATIVE:
993 r_rbtree_cont_insert (filter->tree, node, _dfg_node_filter_insert_cmp, NULL);
994 break;
995 case R_ANAL_ESIL_DFG_BLOCK_RESULT: // outnode must be result generator here
996 case R_ANAL_ESIL_DFG_BLOCK_RESULT | R_ANAL_ESIL_DFG_BLOCK_CONST: {
997 RGraphNode *previous = (RGraphNode *)r_list_get_top (n->in_nodes);
998 if (previous) {
999 sdb_ptr_set (filter->results, r_strbuf_get (node->content), previous, 0);
1000 }
1001 break;
1002 }
1003 }
1004 }
1005
_dfg_filter_rev_dfs_cb(RGraphNode * n,RGraphVisitor * vi)1006 static void _dfg_filter_rev_dfs_cb(RGraphNode *n, RGraphVisitor *vi) {
1007 _dfg_filter_rev_dfs (n, (RAnalEsilDFGFilter *)vi->data);
1008 }
1009
_dfg_const_reducer_rev_dfs_cb(RGraphNode * n,RGraphVisitor * vi)1010 static void _dfg_const_reducer_rev_dfs_cb(RGraphNode *n, RGraphVisitor *vi) {
1011 RAnalEsilDFGConstReducer *reducer = (RAnalEsilDFGConstReducer *)vi->data;
1012 RAnalEsilDFGNode *enode = (RAnalEsilDFGNode *)n->data;
1013 _dfg_filter_rev_dfs (n, &reducer->filter);
1014 r_queue_enqueue (reducer->filter.dfg->todo, n);
1015 if (enode->type == (R_ANAL_ESIL_DFG_BLOCK_CONST | R_ANAL_ESIL_DFG_BLOCK_RESULT)) {
1016 // n can only exist in the tree, if it is a const-result
1017 r_rbtree_cont_delete (reducer->const_result_gnodes, n, _dfg_gnode_reducer_insert_cmp, NULL);
1018 }
1019 }
1020
condrets_strtok(char * str,const char tok)1021 static char *condrets_strtok(char *str, const char tok) {
1022 if (!str) {
1023 return NULL;
1024 }
1025 ut32 i = 0;
1026 while (1 == 1) {
1027 if (!str[i]) {
1028 break;
1029 }
1030 if (str[i] == tok) {
1031 str[i] = '\0';
1032 return &str[i + 1];
1033 }
1034 i++;
1035 }
1036 return NULL;
1037 }
1038
get_resolved_expr(RAnalEsilDFGFilter * filter,RAnalEsilDFGNode * node)1039 static RStrBuf *get_resolved_expr(RAnalEsilDFGFilter *filter, RAnalEsilDFGNode *node) {
1040 char *expr = strdup (r_strbuf_get (node->content));
1041 RStrBuf *res = r_strbuf_new ("");
1042 if (!expr) { //empty expressions. can this happen?
1043 return res;
1044 }
1045 char *p, *q;
1046 // we can do this bc every generative node MUST end with an operator
1047 for (p = expr; (q = condrets_strtok (p, ',')); p = q) {
1048 RGraphNode *gn = sdb_ptr_get (filter->results, p, 0);
1049 if (!gn) {
1050 r_strbuf_appendf (res, ",%s,", p);
1051 } else {
1052 RStrBuf *r = get_resolved_expr (filter, (RAnalEsilDFGNode *)gn->data);
1053 r_strbuf_appendf (res, ",%s,", r_strbuf_get (r));
1054 r_strbuf_free (r);
1055 }
1056 }
1057 r_strbuf_appendf (res, "%s", p);
1058 free (expr);
1059 return res;
1060 }
1061
r_anal_esil_dfg_fold_const(RAnal * anal,RAnalEsilDFG * dfg)1062 R_API void r_anal_esil_dfg_fold_const(RAnal *anal, RAnalEsilDFG *dfg) {
1063 // sorted RContRBTree for graph-nodes that contain edf-nodes with const-result as type
1064 RAnalEsilDFGConstReducer reducer = { { dfg, NULL, NULL }, r_rbtree_cont_new () };
1065 RListIter *iter;
1066 RGraphNode *gnode;
1067 r_list_foreach (dfg->flow->nodes, iter, gnode) {
1068 RAnalEsilDFGNode *enode = (RAnalEsilDFGNode *)gnode->data;
1069 // insert const-result-nodes into the tree
1070 // sort key is enode->idx
1071 if (enode->type == (R_ANAL_ESIL_DFG_BLOCK_CONST | R_ANAL_ESIL_DFG_BLOCK_RESULT)) {
1072 r_rbtree_cont_insert (reducer.const_result_gnodes, gnode, _dfg_gnode_reducer_insert_cmp, NULL);
1073 }
1074 }
1075
1076 RAnalEsil *esil = r_anal_esil_new (4096, 0, 1);
1077 r_anal_esil_setup (esil, anal, 1, 0, 0);
1078 RGraphVisitor vi = { _dfg_const_reducer_rev_dfs_cb, NULL, NULL, NULL, NULL, &reducer };
1079 while ((gnode = (RGraphNode *)r_rbtree_cont_first (reducer.const_result_gnodes))) {
1080 // filter, remove gnodes from const-result-tree
1081 // during rdfs, run in esil, replace subtree with
1082 // const-nodes and fix str-reference if outnode exists
1083
1084 // filter
1085 reducer.filter.tree = r_rbtree_cont_new ();
1086 reducer.filter.results = sdb_new0 (); // I guess this can be done better
1087
1088 r_graph_dfs_node_reverse (dfg->flow, gnode, &vi);
1089
1090 // ok, so gnode here cannot contain a generative node, only const-results
1091 // get_resolved_expr expects a generative node
1092 // the predecessor of a const-result node is always a generative node
1093 RGraphNode *previous_gnode = (RGraphNode *)r_list_get_top (gnode->in_nodes);
1094 // it can never be NULL
1095
1096 RAnalEsilDFGNode *enode = (RAnalEsilDFGNode *)previous_gnode->data;
1097
1098 RStrBuf *filtered = get_resolved_expr (&reducer.filter, enode);
1099 {
1100 char *sanitized = r_str_replace (r_str_replace (strdup (r_strbuf_get (filtered)), ",,", ",", 1), ",,", ",", 1);
1101 r_strbuf_set (filtered, (sanitized[0] == ',') ? &sanitized[1] : sanitized);
1102 free (sanitized);
1103 }
1104 r_rbtree_cont_free (reducer.filter.tree);
1105 sdb_free (reducer.filter.results);
1106
1107 // running filtered const-expression in esil
1108 r_anal_esil_parse (esil, r_strbuf_get (filtered));
1109 char *reduced_const = r_anal_esil_pop (esil);
1110 r_strbuf_free (filtered);
1111
1112 // this part needs some explanation:
1113 // in _dfg_const_reducer_rev_dfs_cb all nodes that are traversed during
1114 // reverse dfs are enqueued in dfg->todo. reverse dfs in this context
1115 // ALWAYS starts with a const-result-node. Result-nodes ALWAYS have a
1116 // generative node as predecessor, which represent to operation.
1117 // An operation in esil, with the exception of $z and some custom operations,
1118 // have at least one operand, which is represented by at least one node in the dfg.
1119 // As a consequence of this, we can safely dequeue 2 nodes from the dfg->todo
1120 // without any checks and reuse them
1121
1122 gnode = (RGraphNode *)r_queue_dequeue (dfg->todo);
1123 enode = (RAnalEsilDFGNode *)gnode->data;
1124 RGraphNode *next_gnode = (RGraphNode *)r_list_get_top (gnode->out_nodes);
1125 if (next_gnode) {
1126 // Cannot assume that there is another operation
1127 // Fix string reference
1128 RAnalEsilDFGNode *next_enode = (RAnalEsilDFGNode *)next_gnode->data;
1129 char *fixed = r_str_replace (strdup (r_strbuf_get (next_enode->content)),
1130 r_strbuf_get (enode->content), reduced_const, 0);
1131 r_strbuf_set (next_enode->content, fixed);
1132 free (fixed);
1133 }
1134
1135 // replace subtree with const-nodes
1136 r_strbuf_setf (enode->content, "%s:const_%d", reduced_const, enode->idx);
1137 gnode = (RGraphNode *)r_queue_dequeue (dfg->todo);
1138 enode = (RAnalEsilDFGNode *)gnode->data;
1139 r_strbuf_set (enode->content, reduced_const);
1140 free (reduced_const);
1141
1142 while (!r_queue_is_empty (dfg->todo)) {
1143 gnode = (RGraphNode *)r_queue_dequeue (dfg->todo);
1144 enode = (RAnalEsilDFGNode *)gnode->data;
1145 _dfg_node_free (enode);
1146 r_graph_del_node (dfg->flow, gnode);
1147 }
1148 }
1149
1150 r_anal_esil_free (esil);
1151 r_rbtree_cont_free (reducer.const_result_gnodes);
1152 }
1153
r_anal_esil_dfg_filter(RAnalEsilDFG * dfg,const char * reg)1154 R_API RStrBuf *r_anal_esil_dfg_filter(RAnalEsilDFG *dfg, const char *reg) {
1155 if (!dfg || !reg) {
1156 return NULL;
1157 }
1158 RGraphNode *resolve_me = _edf_reg_get (dfg, reg);
1159 if (!resolve_me) {
1160 return NULL;
1161 }
1162
1163 // allocate stuff
1164 RAnalEsilDFGFilter filter = { dfg, r_rbtree_cont_new (), sdb_new0 () };
1165 RStrBuf *filtered = r_strbuf_new ("");
1166 RGraphVisitor vi = { _dfg_filter_rev_dfs_cb, NULL, NULL, NULL, NULL, &filter };
1167
1168 // dfs the graph starting at node of esp-register
1169 r_graph_dfs_node_reverse (dfg->flow, resolve_me, &vi);
1170
1171 if (filter.tree->root) {
1172 RBIter ator;
1173 RAnalEsilDFGNode *node;
1174 r_rbtree_cont_foreach (filter.tree, ator, node) {
1175 // resolve results to opstr here
1176 RStrBuf *resolved = get_resolved_expr (&filter, node);
1177 r_strbuf_append (filtered, r_strbuf_get (resolved));
1178 r_strbuf_free (resolved);
1179 }
1180 }
1181 {
1182 char *sanitized = r_str_replace (r_str_replace (strdup (r_strbuf_get (filtered)), ",,", ",", 1), ",,", ",", 1);
1183 r_strbuf_set (filtered, (sanitized[0] == ',') ? &sanitized[1] : sanitized);
1184 free (sanitized);
1185 }
1186 r_rbtree_cont_free (filter.tree);
1187 sdb_free (filter.results);
1188 return filtered;
1189 }
1190
r_anal_esil_dfg_filter_expr(RAnal * anal,const char * expr,const char * reg)1191 R_API RStrBuf *r_anal_esil_dfg_filter_expr(RAnal *anal, const char *expr, const char *reg) {
1192 if (!reg) {
1193 return NULL;
1194 }
1195 RAnalEsilDFG *dfg = r_anal_esil_dfg_expr (anal, NULL, expr);
1196 if (!dfg) {
1197 return NULL;
1198 }
1199 RStrBuf *filtered = r_anal_esil_dfg_filter (dfg, reg);
1200 r_anal_esil_dfg_free (dfg);
1201 return filtered;
1202 }
1203