Branch data Line data Source code
1 : : /* Execute symbolically all paths of the loop.
2 : : Calculate the value of the polynomial by executing loop with real values to
3 : : create LFSR state.
4 : : After each iteration check that final states of calculated CRC values match
5 : : determined LFSR.
6 : : Copyright (C) 2022-2024 Free Software Foundation, Inc.
7 : : Contributed by Mariam Arutunian <mariamarutunian@gmail.com>
8 : :
9 : : This file is part of GCC.
10 : :
11 : : GCC is free software; you can redistribute it and/or modify it under
12 : : the terms of the GNU General Public License as published by the Free
13 : : Software Foundation; either version 3, or (at your option) any later
14 : : version.
15 : :
16 : : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
17 : : WARRANTY; without even the implied warranty of MERCHANTABILITY or
18 : : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 : : for more details.
20 : :
21 : : You should have received a copy of the GNU General Public License
22 : : along with GCC; see the file COPYING3. If not see
23 : : <http://www.gnu.org/licenses/>. */
24 : :
25 : : #include "crc-verification.h"
26 : : #include "config.h"
27 : : #include "system.h"
28 : : #include "coretypes.h"
29 : : #include "backend.h"
30 : : #include "tree.h"
31 : : #include "gimple.h"
32 : : #include "ssa.h"
33 : : #include "gimple-iterator.h"
34 : : #include "tree-cfg.h"
35 : : #include "cfganal.h"
36 : : #include "tree-ssa-loop.h"
37 : :
38 : : /* Check whether defined variable is used outside the loop, only
39 : : CRC's definition is allowed to be used outside the loop. */
40 : :
41 : : bool
42 : 33591 : crc_symbolic_execution::is_used_outside_the_loop (tree def)
43 : : {
44 : 33591 : imm_use_iterator imm_iter;
45 : 33591 : gimple *use_stmt;
46 : 72221 : FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
47 : : {
48 : 44670 : if (!flow_bb_inside_loop_p (m_crc_loop, use_stmt->bb))
49 : : {
50 : 6040 : if (is_a<gphi *> (use_stmt)
51 : 6040 : && as_a<gphi *> (use_stmt) == m_output_crc)
52 : : return false;
53 : 0 : if (dump_file)
54 : 0 : fprintf (dump_file, "Defined variable is used outside the loop.\n");
55 : 0 : return true;
56 : : }
57 : 33591 : }
58 : 27551 : return false;
59 : : }
60 : :
61 : : /* Calculate value of the rhs operation of GS assigment statement
62 : : and assign it to lhs variable. */
63 : :
64 : : bool
65 : 29181 : crc_symbolic_execution::execute_assign_statement (const gassign *gs)
66 : : {
67 : 29181 : enum tree_code rhs_code = gimple_assign_rhs_code (gs);
68 : 29181 : tree lhs = gimple_assign_lhs (gs);
69 : 29181 : if (dump_file && (dump_flags & TDF_DETAILS))
70 : 26162 : fprintf (dump_file, "lhs type : %s \n",
71 : 26162 : get_tree_code_name (TREE_CODE (lhs)));
72 : :
73 : : /* This will filter some normal cases too. Ex. usage of array. */
74 : 29181 : if (TREE_CODE (lhs) != SSA_NAME)
75 : : return false;
76 : :
77 : : /* Check uses only when m_output_crc is known. */
78 : 29176 : if (m_output_crc)
79 : 27551 : if (is_used_outside_the_loop (lhs))
80 : : return false;
81 : :
82 : 29176 : if (gimple_num_ops (gs) != 2 && gimple_num_ops (gs) != 3)
83 : : {
84 : 0 : if (dump_file)
85 : 0 : fprintf (dump_file,
86 : : "Warning, encountered unsupported operation, "
87 : : "with %s code while executing assign statement!\n",
88 : : get_tree_code_name (rhs_code));
89 : 0 : return false;
90 : : }
91 : :
92 : 29176 : tree op1 = gimple_assign_rhs1 (gs);
93 : 29176 : tree op2 = nullptr;
94 : :
95 : 29176 : if (gimple_num_ops (gs) == 3)
96 : 26249 : op2 = gimple_assign_rhs2 (gs);
97 : :
98 : 29176 : state *current_state = m_states.last ();
99 : 29176 : return current_state->do_operation (rhs_code, op1, op2, lhs);
100 : : }
101 : :
102 : : /* Add E edge into the STACK if it doesn't have an immediate
103 : : successor edge going to the loop header.
104 : :
105 : : When loop counter is checked in the if condition,
106 : : we mustn't continue on real path as we want to stop the execution before
107 : : the second iteration. */
108 : :
109 : : bool
110 : 6528 : crc_symbolic_execution::add_edge (edge e, auto_vec<edge> &stack)
111 : : {
112 : 6528 : if (EDGE_COUNT (e->dest->succs) == 0)
113 : : return false;
114 : :
115 : 6528 : edge next_bb_edge = EDGE_SUCC (e->dest, 0);
116 : 6528 : if (next_bb_edge && next_bb_edge->dest == m_crc_loop->header)
117 : : {
118 : 5845 : if (dump_file && (dump_flags & TDF_DETAILS))
119 : 5123 : fprintf (dump_file, "Completed one iteration. "
120 : : "Won't iterate loop once more, yet.\n");
121 : :
122 : 5845 : return keep_states ();
123 : : }
124 : : else
125 : : {
126 : 683 : if (dump_file && (dump_flags & TDF_DETAILS))
127 : 543 : fprintf (dump_file, "Adding the edge into the stack.\n");
128 : :
129 : : /* If the result of the condition is true/false,
130 : : continue execution only by the true/false branch. */
131 : 683 : stack.quick_push (e);
132 : : }
133 : 683 : return true;
134 : : }
135 : :
136 : : /* Add next basic blocks of the conditional block COND_BB
137 : : for the execution path into the STACK.
138 : : If the condition depends on symbolic values, keep both edges.
139 : : If the condition is true, keep true edge, else - false edge.
140 : : Returns true if addition succeeds. Otherwise - false. */
141 : :
142 : : bool
143 : 9547 : crc_symbolic_execution::add_next_bbs (basic_block cond_bb,
144 : : state *new_branch_state,
145 : : auto_vec<edge> &stack)
146 : : {
147 : 9547 : edge true_edge;
148 : 9547 : edge false_edge;
149 : 9547 : extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
150 : :
151 : : /* When the condition depends on symbolic values. */
152 : 9547 : if (new_branch_state->get_last_cond_status () == CS_SYM)
153 : : {
154 : : /* Supported CRC cases may have only two states. */
155 : 3019 : if (m_states.length () == 2)
156 : : {
157 : 0 : if (dump_file && (dump_flags & TDF_DETAILS))
158 : 0 : fprintf (dump_file, "Going to add a new state, "
159 : : "but there's already two states.\n");
160 : 0 : return false;
161 : : }
162 : : /* Add true branch's state into the states.
163 : : False branch's state will be kept in the current state. */
164 : 3019 : m_states.quick_push (new_branch_state);
165 : :
166 : 3019 : if (dump_file && (dump_flags & TDF_DETAILS))
167 : 2640 : fprintf (dump_file, "Adding true and false edges into the stack.\n");
168 : :
169 : : /* Add outgoing edges to the stack. */
170 : 3019 : stack.quick_push (false_edge);
171 : 3019 : stack.quick_push (true_edge);
172 : :
173 : 3019 : return true;
174 : : }
175 : : /* When the condition evaluates to true. */
176 : 6528 : else if (new_branch_state->get_last_cond_status () == CS_TRUE)
177 : : {
178 : 6076 : if (dump_file && (dump_flags & TDF_DETAILS))
179 : 5304 : fprintf (dump_file, "Condition is true.\n");
180 : 6076 : add_edge (true_edge, stack);
181 : : }
182 : : /* When the condition evaluates to false. */
183 : 452 : else if (new_branch_state->get_last_cond_status () == CS_FALSE)
184 : : {
185 : 452 : if (dump_file && (dump_flags & TDF_DETAILS))
186 : 362 : fprintf (dump_file, "Condition is false.\n");
187 : 452 : add_edge (false_edge, stack);
188 : : }
189 : : else
190 : : {
191 : 0 : if (dump_file && (dump_flags & TDF_DETAILS))
192 : 0 : fprintf (dump_file, "Something went wrong "
193 : : "during handling conditional statement.\n");
194 : 0 : return false;
195 : : }
196 : :
197 : : /* When we continue execution of only one path,
198 : : there's no need of new state. */
199 : 6528 : delete new_branch_state;
200 : 6528 : return true;
201 : : }
202 : :
203 : : /* Add conditions depending on symbolic variables in the states.
204 : :
205 : : Keep conditions of each branch execution in its state.
206 : : Ex.
207 : : if (a == 0) // a's value is unknown
208 : :
209 : : new_branch_state.keep (a==0)
210 : : current_state.keep (a!=0)
211 : :
212 : : The condition is kept in the bit level.
213 : : For ex.
214 : : If a's size is 8 and its value is {symb_a, 0, 0, 0, 0, 0, 0, 0},
215 : : then for a == 0 we'll have symb_a == 0 condition. */
216 : :
217 : : bool
218 : 9547 : crc_symbolic_execution::add_condition (const gcond *cond,
219 : : state *current_state,
220 : : state *new_branch_state)
221 : : {
222 : 9547 : tree lhs = gimple_cond_lhs (cond);
223 : 9547 : tree rhs = gimple_cond_rhs (cond);
224 : 9547 : switch (gimple_cond_code (cond))
225 : : {
226 : 1 : case EQ_EXPR:
227 : 1 : {
228 : 1 : new_branch_state->add_equal_cond (lhs, rhs);
229 : 1 : if (new_branch_state->get_last_cond_status () == CS_SYM)
230 : 0 : current_state->add_not_equal_cond (lhs, rhs);
231 : : return true;
232 : : }
233 : 8189 : case NE_EXPR:
234 : 8189 : {
235 : 8189 : new_branch_state->add_not_equal_cond (lhs, rhs);
236 : 8189 : if (new_branch_state->get_last_cond_status () == CS_SYM)
237 : 1747 : current_state->add_equal_cond (lhs, rhs);
238 : : return true;
239 : : }
240 : 0 : case GT_EXPR:
241 : 0 : {
242 : 0 : new_branch_state->add_greater_than_cond (lhs, rhs);
243 : 0 : if (new_branch_state->get_last_cond_status () == CS_SYM)
244 : 0 : current_state->add_less_or_equal_cond (lhs, rhs);
245 : : return true;
246 : : }
247 : 1357 : case LT_EXPR:
248 : 1357 : {
249 : 1357 : new_branch_state->add_less_than_cond (lhs, rhs);
250 : 1357 : if (new_branch_state->get_last_cond_status () == CS_SYM)
251 : 1272 : current_state->add_greater_or_equal_cond (lhs, rhs);
252 : : return true;
253 : : }
254 : 0 : case GE_EXPR:
255 : 0 : {
256 : 0 : new_branch_state->add_greater_or_equal_cond (lhs, rhs);
257 : 0 : if (new_branch_state->get_last_cond_status () == CS_SYM)
258 : 0 : current_state->add_less_than_cond (lhs, rhs);
259 : : return true;
260 : : }
261 : 0 : case LE_EXPR:
262 : 0 : {
263 : 0 : new_branch_state->add_less_or_equal_cond (lhs, rhs);
264 : 0 : if (new_branch_state->get_last_cond_status () == CS_SYM)
265 : 0 : current_state->add_greater_than_cond (lhs, rhs);
266 : : return true;
267 : : }
268 : 0 : default:
269 : 0 : {
270 : 0 : if (dump_file && (dump_flags & TDF_DETAILS))
271 : 0 : fprintf (dump_file, "Unsupported condition.\n");
272 : : return false;
273 : : }
274 : : }
275 : : }
276 : :
277 : : /* Create new states for true and false branches.
278 : : Keep conditions in new created states. */
279 : :
280 : : bool
281 : 9547 : crc_symbolic_execution::resolve_condition (const gcond *cond,
282 : : auto_vec<edge> &stack)
283 : : {
284 : 9547 : state *current_state = m_states.last ();
285 : 9547 : state *new_branch_state = new state (*current_state);
286 : :
287 : : /* Create new states and for true and false branches keep corresponding
288 : : conditions. */
289 : 9547 : if (!add_condition (cond, current_state, new_branch_state))
290 : : return false;
291 : :
292 : : /* Add true and false edges to the stack. */
293 : 9547 : return add_next_bbs (cond->bb, new_branch_state, stack);
294 : : }
295 : :
296 : : /* If final states are less than two, add new FINAL_STATE and return true.
297 : : Otherwise, return false.
298 : : Supported CRC cases may not have more than two final states. */
299 : 6283 : bool crc_symbolic_execution::add_final_state (state *final_state)
300 : : {
301 : 6283 : if (m_final_states.length () < 2)
302 : 6283 : m_final_states.quick_push (final_state);
303 : : else
304 : : {
305 : 0 : if (dump_file)
306 : 0 : fprintf (dump_file,
307 : : "There are already two final states\n");
308 : 0 : return false;
309 : : }
310 : 6283 : return true;
311 : : }
312 : :
313 : : /* Keep the state of the executed path in final states. */
314 : :
315 : 6283 : bool crc_symbolic_execution::keep_states ()
316 : : {
317 : 6283 : if (m_states.is_empty ())
318 : : return false;
319 : :
320 : 6283 : if (!add_final_state (m_states.last ()))
321 : : {
322 : 0 : if (dump_file && (dump_flags & TDF_DETAILS))
323 : 0 : fprintf (dump_file, "Couldn't add final state.\n");
324 : 0 : return false;
325 : : }
326 : :
327 : 6283 : m_states.pop ();
328 : 6283 : return true;
329 : : }
330 : :
331 : : /* Execute gimple statements of BB.
332 : : Keeping values of variables in the state. */
333 : :
334 : : bool
335 : 15751 : crc_symbolic_execution::execute_bb_gimple_statements (basic_block bb,
336 : : auto_vec<edge> &stack)
337 : : {
338 : 31502 : for (gimple_stmt_iterator bsi = gsi_start_bb (bb);
339 : 53716 : !gsi_end_p (bsi); gsi_next (&bsi))
340 : : {
341 : 47523 : gimple *gs = gsi_stmt (bsi);
342 : 47523 : if (dump_file && (dump_flags & TDF_DETAILS))
343 : : {
344 : 40137 : fprintf (dump_file, "Executing ");
345 : 40137 : print_gimple_stmt (dump_file, gs, dump_flags);
346 : : }
347 : 47523 : switch (gimple_code (gs))
348 : : {
349 : 29181 : case GIMPLE_ASSIGN:
350 : 29181 : {
351 : 29181 : if (!execute_assign_statement (as_a<const gassign *> (gs)))
352 : 15751 : return false;
353 : : break;
354 : : }
355 : 9547 : case GIMPLE_COND:
356 : 9547 : {
357 : 9547 : return resolve_condition (as_a<const gcond *> (gs), stack);
358 : : }
359 : : /* Just skip debug statements. */
360 : : case GIMPLE_DEBUG:
361 : : break;
362 : 6 : default:
363 : 6 : {
364 : 6 : if (dump_file)
365 : 6 : fprintf (dump_file,
366 : : "Warning, encountered unsupported statement, "
367 : : "while executing gimple statements!\n");
368 : : return false;
369 : : }
370 : : }
371 : : }
372 : :
373 : : /* Add each outgoing edge of the current block to the stack,
374 : : despite the edges going to the loop header.
375 : : This code isn't reachable if the last statement of the basic block
376 : : is a conditional statement or return statement.
377 : : Those cases are handled separately.
378 : : We mustn't encounter edges going to the CRC loop header. */
379 : :
380 : 6193 : edge out_edge;
381 : 6193 : edge_iterator ei;
382 : 12386 : FOR_EACH_EDGE (out_edge, ei, bb->succs)
383 : 6193 : if (out_edge->dest != m_crc_loop->header)
384 : 6193 : stack.quick_push (out_edge);
385 : : else
386 : : return false;
387 : :
388 : : return true;
389 : : }
390 : :
391 : : /* Assign values of phi instruction to its result.
392 : : Keep updated values in the state. */
393 : :
394 : : bool
395 : 12476 : crc_symbolic_execution::execute_bb_phi_statements (basic_block bb,
396 : : edge incoming_edge)
397 : : {
398 : 18759 : for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
399 : 6283 : gsi_next (&gsi))
400 : : {
401 : 6283 : gphi *phi = gsi.phi ();
402 : 6283 : tree lhs = gimple_phi_result (phi);
403 : :
404 : : /* Check uses only when m_output_crc is known. */
405 : 6283 : if (m_output_crc)
406 : 6040 : if (is_used_outside_the_loop (lhs))
407 : 0 : return false;
408 : :
409 : : /* Don't consider virtual operands. */
410 : 12566 : if (virtual_operand_p (lhs))
411 : 0 : continue;
412 : :
413 : 6283 : if (dump_file && (dump_flags & TDF_DETAILS))
414 : : {
415 : 5473 : fprintf (dump_file, "Determining the value "
416 : : "for the following phi.\n");
417 : 5473 : print_gimple_stmt (dump_file, phi, dump_flags);
418 : : }
419 : :
420 : 6283 : tree rhs = PHI_ARG_DEF_FROM_EDGE (phi, incoming_edge);
421 : :
422 : 6283 : state *current_state = m_states.last ();
423 : 6283 : if (!current_state->do_operation (VAR_DECL, rhs, nullptr, lhs))
424 : : return false;
425 : : }
426 : 12476 : return true;
427 : : }
428 : :
429 : : /* Execute all statements of BB.
430 : : Keeping values of variables in the state. */
431 : :
432 : : bool
433 : 12476 : crc_symbolic_execution::execute_bb_statements (basic_block bb,
434 : : edge incoming_edge,
435 : : auto_vec<edge> &stack)
436 : : {
437 : 12476 : if (!execute_bb_phi_statements (bb, incoming_edge))
438 : : return false;
439 : :
440 : 12476 : return execute_bb_gimple_statements (bb, stack);
441 : : }
442 : :
443 : : /* If the phi statements' result variables have initial constant value in the
444 : : beginning of the loop, initialize those variables. */
445 : :
446 : : void
447 : 223 : assign_known_vals_to_header_phis (state *state, class loop *crc_loop)
448 : : {
449 : 223 : basic_block bb = crc_loop->header;
450 : 1001 : for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
451 : 778 : gsi_next (&gsi))
452 : : {
453 : :
454 : 778 : gphi *phi = gsi.phi ();
455 : 778 : tree lhs = gimple_phi_result (phi);
456 : :
457 : : /* Don't consider virtual operands. */
458 : 1556 : if (virtual_operand_p (lhs))
459 : 12 : continue;
460 : :
461 : 766 : tree inital_val = PHI_ARG_DEF_FROM_EDGE (phi,
462 : : loop_preheader_edge (crc_loop));
463 : 766 : if (TREE_CODE (inital_val) == INTEGER_CST)
464 : : {
465 : 451 : if (dump_file && (dump_flags & TDF_DETAILS))
466 : : {
467 : 358 : fprintf (dump_file, "First value of phi is a constant, "
468 : : "assigning the number to ");
469 : 358 : print_generic_expr (dump_file, lhs, dump_flags);
470 : 358 : fprintf (dump_file, " variable.\n");
471 : : }
472 : 451 : state->do_operation (VAR_DECL, inital_val,
473 : : nullptr, lhs);
474 : : }
475 : : }
476 : 223 : }
477 : :
478 : : /* If the phi statements' result variables have initial constant value in the
479 : : beginning of the loop, initialize those variables with
480 : : the value calculated during the previous iteration. */
481 : :
482 : : bool
483 : 2798 : assign_calc_vals_to_header_phis (const vec<state *> &prev_states,
484 : : state *curr_state,
485 : : class loop *crc_loop)
486 : : {
487 : 2798 : basic_block bb = crc_loop->header;
488 : 12942 : for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
489 : 10144 : gsi_next (&gsi))
490 : : {
491 : 10144 : gphi *phi = gsi.phi ();
492 : 10144 : tree lhs = gimple_phi_result (phi);
493 : :
494 : : /* Don't consider virtual operands. */
495 : 20288 : if (virtual_operand_p (lhs))
496 : 86 : continue;
497 : 10058 : tree inital_val = PHI_ARG_DEF_FROM_EDGE (phi,
498 : : loop_preheader_edge (crc_loop));
499 : 10058 : if (TREE_CODE (inital_val) == INTEGER_CST)
500 : : {
501 : 5610 : tree input_tree = PHI_ARG_DEF_FROM_EDGE (phi,
502 : : loop_latch_edge (crc_loop));
503 : 5610 : value * val_st1 = prev_states[0]->get_value (input_tree),
504 : 5610 : *val_st2 = prev_states[1]->get_value (input_tree);
505 : 5610 : if (!state::is_bit_vector (val_st1)
506 : 5610 : || !state::is_bit_vector (val_st2))
507 : : {
508 : 0 : if (dump_file && (dump_flags & TDF_DETAILS))
509 : : {
510 : 0 : fprintf (dump_file, "The calculated values of ");
511 : 0 : print_generic_expr (dump_file, input_tree, dump_flags);
512 : 0 : fprintf (dump_file, " variable is not constant.\n");
513 : : }
514 : 0 : return false;
515 : : }
516 : 5610 : else if (!state::check_const_value_equality (val_st1, val_st2))
517 : : {
518 : 0 : if (dump_file && (dump_flags & TDF_DETAILS))
519 : : {
520 : 0 : fprintf (dump_file, "The calculated values of ");
521 : 0 : print_generic_expr (dump_file, input_tree, dump_flags);
522 : 0 : fprintf (dump_file, " variable is different in the previous "
523 : : "iteration paths.\n");
524 : : }
525 : 0 : return false;
526 : : }
527 : : else
528 : : {
529 : 5610 : if (dump_file && (dump_flags & TDF_DETAILS))
530 : : {
531 : 4944 : fprintf (dump_file, "Assigning calculated number to ");
532 : 4944 : print_generic_expr (dump_file, lhs, dump_flags);
533 : 4944 : fprintf (dump_file, " variable.\n");
534 : : }
535 : 5610 : unsigned HOST_WIDE_INT calc_number
536 : 5610 : = state::make_number (val_st1);
537 : 5610 : tree calc_num_tree = build_int_cstu (TREE_TYPE (lhs),
538 : : calc_number);
539 : 5610 : curr_state->do_operation (VAR_DECL, calc_num_tree, nullptr, lhs);
540 : : }
541 : : }
542 : : }
543 : 2798 : return true;
544 : : }
545 : :
546 : : /* Create initial state of the CRC_LOOP's header BB variables which have
547 : : constant values.
548 : : If it is the first iteration of the loop, initialise variables with the
549 : : initial values, otherwise initialise the variable with the value calculated
550 : : during the previous execution. */
551 : :
552 : : state *
553 : 3021 : crc_symbolic_execution::create_initial_state (class loop *crc_loop)
554 : : {
555 : 3021 : state *curr_state = new state;
556 : 3021 : if (!m_final_states.is_empty ())
557 : : {
558 : 2798 : if (!assign_calc_vals_to_header_phis (m_final_states, curr_state,
559 : : crc_loop))
560 : : return nullptr;
561 : 2798 : state::remove_states (&m_final_states);
562 : : }
563 : : else
564 : 223 : assign_known_vals_to_header_phis (curr_state, crc_loop);
565 : : return curr_state;
566 : : }
567 : :
568 : : /* Symbolically execute the CRC loop, doing one iteration. */
569 : :
570 : : bool
571 : 3021 : crc_symbolic_execution::symb_execute_crc_loop ()
572 : : {
573 : 3021 : if (dump_file && (dump_flags & TDF_DETAILS))
574 : 2642 : fprintf (dump_file, "\n\nExecuting the loop with symbolic values.\n\n");
575 : :
576 : 3021 : state *curr_state = create_initial_state (m_crc_loop);
577 : 3021 : if (!curr_state)
578 : : return false;
579 : :
580 : 3021 : m_states.quick_push (curr_state);
581 : :
582 : 3021 : auto_vec<edge> stack (m_crc_loop->num_nodes);
583 : :
584 : 3021 : basic_block header_bb = m_crc_loop->header;
585 : 3021 : if (!execute_bb_gimple_statements (header_bb, stack))
586 : : return false;
587 : :
588 : : /* Successor BB's are added into the stack
589 : : from the execute_bb_gimple_statements function. */
590 : 18470 : while (!stack.is_empty ())
591 : : {
592 : : /* Look at the edge on the top of the stack. */
593 : 12428 : edge e = stack.last ();
594 : 12428 : stack.pop ();
595 : :
596 : : /* Get destination block of the edge. */
597 : 12428 : basic_block dest_bb = e->dest;
598 : :
599 : : /* Execute only basic blocks of the m_crc_loop.
600 : : At the end of the execution path save states in final states. */
601 : 12428 : if (!flow_bb_inside_loop_p (m_crc_loop, dest_bb))
602 : : {
603 : 438 : m_is_last_iteration = true;
604 : 438 : if (!keep_states ())
605 : : return false;
606 : 438 : continue;
607 : : }
608 : :
609 : : /* Execute statements. */
610 : 11990 : if (!execute_bb_statements (dest_bb, e, stack))
611 : : return false;
612 : : }
613 : : return true;
614 : 3021 : }
615 : :
616 : : /* Determine which bit of the DATA must be 1.
617 : : We assume that last bit must be 1. */
618 : :
619 : : unsigned HOST_WIDE_INT
620 : 254 : determine_index (tree data, bool is_shift_left)
621 : : {
622 : 254 : if (is_shift_left)
623 : : /* This won't work correctly in the case when data's size is larger,
624 : : but MSB is checked for the middle bit. */
625 : 123 : return tree_to_uhwi (TYPE_SIZE (TREE_TYPE (data))) - 1;
626 : : return 0;
627 : : }
628 : :
629 : : /* Assign appropriate values to data, CRC
630 : : and other phi results to calculate the polynomial. */
631 : :
632 : : void
633 : 254 : assign_vals_to_header_phis (state *polynomial_state, class loop *crc_loop,
634 : : gphi *crc_phi, gphi *data_phi,
635 : : bool is_shift_left)
636 : : {
637 : 254 : basic_block bb = crc_loop->header;
638 : 1158 : for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
639 : 904 : gsi_next (&gsi))
640 : : {
641 : :
642 : 904 : gphi *phi = gsi.phi ();
643 : 904 : tree lhs = gimple_phi_result (phi);
644 : :
645 : : /* Don't consider virtual operands. */
646 : 1808 : if (virtual_operand_p (lhs))
647 : 24 : continue;
648 : :
649 : 880 : if ((data_phi && phi == data_phi) || (!data_phi && phi == crc_phi))
650 : : {
651 : 254 : if (dump_file && (dump_flags & TDF_DETAILS))
652 : : {
653 : 202 : fprintf (dump_file, "Assigning the required value to ");
654 : 202 : print_generic_expr (dump_file, lhs, dump_flags);
655 : 202 : fprintf (dump_file, " variable.\n");
656 : : }
657 : 254 : polynomial_state->do_assign_pow2 (lhs,
658 : 254 : determine_index (lhs,
659 : : is_shift_left));
660 : : }
661 : 626 : else if (phi == crc_phi)
662 : : {
663 : 115 : if (dump_file && (dump_flags & TDF_DETAILS))
664 : : {
665 : 111 : fprintf (dump_file, "Assigning 0 value to ");
666 : 111 : print_generic_expr (dump_file, lhs, dump_flags);
667 : 111 : fprintf (dump_file, " variable.\n");
668 : : }
669 : 115 : polynomial_state->do_operation (VAR_DECL,
670 : 115 : build_zero_cst (TREE_TYPE (lhs)),
671 : : nullptr, lhs);
672 : : }
673 : : else
674 : : {
675 : 511 : edge loop_preheader = loop_preheader_edge (crc_loop);
676 : 511 : tree inital_val = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader);
677 : 511 : if (TREE_CODE (inital_val) == INTEGER_CST)
678 : : {
679 : 505 : if (dump_file && (dump_flags & TDF_DETAILS))
680 : : {
681 : 402 : fprintf (dump_file, "First value of phi is a constant, "
682 : : "assigning the number to ");
683 : 402 : print_generic_expr (dump_file, lhs, dump_flags);
684 : 402 : fprintf (dump_file, " variable.\n");
685 : : }
686 : 505 : polynomial_state->do_operation (VAR_DECL, inital_val,
687 : : nullptr, lhs);
688 : : }
689 : : else
690 : : {
691 : 6 : if (dump_file && (dump_flags & TDF_DETAILS))
692 : : {
693 : 6 : fprintf (dump_file, "First value of phi isn't constant, "
694 : : "assigning to ");
695 : 6 : print_generic_expr (dump_file, lhs, dump_flags);
696 : 6 : fprintf (dump_file, " variable.\n");
697 : : }
698 : 6 : polynomial_state->do_operation (VAR_DECL,
699 : 6 : build_zero_cst (TREE_TYPE (lhs)),
700 : : nullptr, lhs);
701 : : }
702 : : }
703 : : }
704 : 254 : }
705 : :
706 : : /* Execute the loop, which calculates CRC with initial values,
707 : : to calculate the polynomial. */
708 : :
709 : : bool
710 : 254 : crc_symbolic_execution::execute_crc_loop (gphi *crc_phi,
711 : : gphi *data_phi,
712 : : bool is_shift_left)
713 : : {
714 : 254 : if (dump_file && (dump_flags & TDF_DETAILS))
715 : 202 : fprintf (dump_file, "\n\nTrying to calculate the polynomial.\n\n");
716 : :
717 : 254 : m_states.quick_push (new state);
718 : :
719 : 254 : basic_block bb = m_crc_loop->header;
720 : 254 : assign_vals_to_header_phis (m_states.last (), m_crc_loop, crc_phi, data_phi,
721 : : is_shift_left);
722 : :
723 : 254 : auto_vec<edge> stack (m_crc_loop->num_nodes);
724 : :
725 : 254 : if (!execute_bb_gimple_statements (bb, stack))
726 : : return false;
727 : :
728 : : /* stack may not be empty. Successor BB's are added into the stack
729 : : from the execute_bb_gimple_statements function. */
730 : 729 : while (!stack.is_empty ())
731 : : {
732 : : /* Look at the edge on the top of the stack. */
733 : 486 : edge e = stack.last ();
734 : 486 : stack.pop ();
735 : :
736 : : /* Get dest block of the edge. */
737 : 486 : basic_block bb = e->dest;
738 : :
739 : : /* Execute only basic blocks of the m_crc_loop. */
740 : 486 : if (!flow_bb_inside_loop_p (m_crc_loop, bb))
741 : 0 : continue;
742 : :
743 : : /* Execute statements. */
744 : 486 : if (!execute_bb_statements (bb, e, stack))
745 : : return false;
746 : : }
747 : :
748 : 243 : if (m_final_states.length () != 1)
749 : : {
750 : 0 : if (dump_file && (dump_flags & TDF_DETAILS))
751 : 0 : fprintf (dump_file, "The number of states is not one when executed "
752 : : "the loop for calculating the polynomial.\n");
753 : 0 : return false;
754 : : }
755 : : return true;
756 : 254 : }
757 : :
758 : : /* Return true if all bits of the POLYNOMIAL are constants (0 or 1).
759 : : Otherwise return false. */
760 : :
761 : : bool
762 : 243 : polynomial_is_known (const value *polynomial)
763 : : {
764 : 6507 : for (size_t i = 0; i < polynomial->length (); i++)
765 : : {
766 : 6264 : if (!is_a<bit *> ((*polynomial)[i]))
767 : : return false;
768 : : }
769 : : return true;
770 : : }
771 : :
772 : : /* Execute the loop, which is expected to calculate CRC,
773 : : to extract polynomial, assigning real numbers to CRC and data.
774 : : Returns a pair, first value of the pair is the tree containing
775 : : the value of the polynomial, second is the calculated polynomial.
776 : : The pair may contain nullptr. */
777 : :
778 : : std::pair <tree, value *>
779 : 254 : crc_symbolic_execution::extract_polynomial (gphi *crc_phi, gphi *data_phi,
780 : : tree calculated_crc,
781 : : bool is_shift_left)
782 : : {
783 : 254 : if (!execute_crc_loop (crc_phi, data_phi, is_shift_left))
784 : 11 : return std::make_pair (nullptr, nullptr);
785 : :
786 : 243 : if (m_final_states.length () != 1)
787 : : {
788 : 0 : if (dump_file && (dump_flags & TDF_DETAILS))
789 : 0 : fprintf (dump_file, "The number of states isn't one "
790 : : "after executing the loop.\n");
791 : 0 : return std::make_pair (nullptr, nullptr);
792 : : }
793 : 243 : state *polynomial_state = m_final_states.last ();
794 : :
795 : : /* CALCULATED_CRC contains the value of the polynomial
796 : : after one iteration of the loop. */
797 : 243 : if (dump_file && (dump_flags & TDF_DETAILS))
798 : : {
799 : 191 : fprintf (dump_file, "Getting the value of ");
800 : 191 : print_generic_expr (dump_file, calculated_crc, dump_flags);
801 : 191 : fprintf (dump_file, " variable.\n");
802 : : }
803 : :
804 : : /* Get the value (bit vector) of the tree (it may be the polynomial). */
805 : 243 : value *polynomial = polynomial_state->get_value (calculated_crc);
806 : 243 : if (!polynomial)
807 : : {
808 : 0 : if (dump_file && (dump_flags & TDF_DETAILS))
809 : 0 : fprintf (dump_file, "Polynomial's value is null.\n");
810 : 0 : return std::make_pair (nullptr, nullptr);
811 : : }
812 : :
813 : 243 : if (dump_file && (dump_flags & TDF_DETAILS))
814 : : {
815 : : /* Note: It may not be the real polynomial.
816 : : If it's a bit reflected CRC,
817 : : then to get a real polynomial,
818 : : it must be reflected and 1 bit added. */
819 : 191 : fprintf (dump_file, "Polynomial's value is ");
820 : 191 : state::print_value (polynomial);
821 : : }
822 : :
823 : : /* Check that polynomial's all bits are constants. */
824 : 243 : if (!polynomial_is_known (polynomial))
825 : : {
826 : 0 : if (dump_file && (dump_flags & TDF_DETAILS))
827 : 0 : fprintf (dump_file, "Polynomial's value is not constant.\n");
828 : 0 : return std::make_pair (nullptr, nullptr);
829 : : }
830 : :
831 : 243 : return std::make_pair (calculated_crc, polynomial);
832 : : }
833 : :
834 : :
835 : : /**************************** LFSR MATCHING *********************************/
836 : :
837 : :
838 : : /* Return true if CONST_BIT value equals to 1.
839 : : Otherwise, return false. */
840 : :
841 : : bool
842 : 34970 : is_one (value_bit *const_bit)
843 : : {
844 : 34970 : return is_a<bit *> (const_bit)
845 : 34970 : && (as_a<bit *> (const_bit))->get_val () == 1;
846 : : }
847 : :
848 : : /* Return true if BIT is symbolic,
849 : : its index is same as LFSR bit's index (LFSR_BIT_INDEX)
850 : : and the origin is same as CRC_ORIGIN. */
851 : :
852 : : bool
853 : 199694 : is_a_valid_symb (value_bit *bit, tree crc_origin, size_t lfsr_bit_index)
854 : : {
855 : 199694 : if (!is_a<symbolic_bit *> (bit))
856 : : return false;
857 : :
858 : 199694 : symbolic_bit *sym_bit = as_a<symbolic_bit *> (bit);
859 : 199694 : bool is_correct_index = (sym_bit->get_index () == lfsr_bit_index);
860 : 199694 : bool is_same_crc_origin = (sym_bit->get_origin () == crc_origin);
861 : 199694 : return is_correct_index && is_same_crc_origin;
862 : : }
863 : :
864 : : /* Return true if the BIT is a valid crc[LFSR_BIT_INDEX] ^ 1,
865 : : where i is a whole number and left part's origin is same as CRC_ORIGIN.
866 : : LFSR_BIT_INDEX is the index of the LFSR bit from the same position as in CRC.
867 : :
868 : : If there is lfsr[8] at LFSR value vectors' 9-th bit,
869 : : when in the CRC vectors' 9-th bit's value must be
870 : : crc[8].
871 : :
872 : : Otherwise, return false. */
873 : :
874 : : bool
875 : 34970 : is_a_valid_xor_one (value_bit *bit, tree crc_origin, size_t lfsr_bit_index)
876 : : {
877 : 34970 : if (is_a<bit_xor_expression *> (bit))
878 : : {
879 : 34970 : bit_xor_expression *xor_exp = as_a<bit_xor_expression *> (bit);
880 : 34970 : if (is_one (xor_exp->get_right ()))
881 : 34970 : return is_a_valid_symb (xor_exp->get_left (), crc_origin,
882 : 34970 : lfsr_bit_index);
883 : : return false;
884 : : }
885 : : return false;
886 : : }
887 : :
888 : : /* Return true, if CONDITION_EXP checks CRC's MSB/LSB value
889 : : (under which xor is/not done).
890 : : Otherwise, return false. */
891 : :
892 : : bool
893 : 6036 : may_be_xors_condition (tree crc_origin, value_bit *condition_exp,
894 : : size_t sb_index)
895 : : {
896 : 6036 : if (!crc_origin)
897 : : return false;
898 : :
899 : 6036 : if (!condition_exp)
900 : : return false;
901 : :
902 : : /* The CONDITION_EXP of CRC may be a symbolic bit, if CRC is xor-ed with
903 : : the data, and updated CRC's significant bit is checked.
904 : : So, the CONDITION_EXP will be CRC's condition if it's origin is the same as
905 : : CRC_ORIGIN, and it's index equals to checked significant bit's index. */
906 : 6036 : if (is_a<symbolic_bit *> (condition_exp))
907 : : {
908 : 2546 : symbolic_bit *condition_symbolic = as_a<symbolic_bit *> (condition_exp);
909 : 2546 : return crc_origin == condition_symbolic->get_origin ()
910 : 2546 : && sb_index == condition_symbolic->get_index ();
911 : : }
912 : : /* The CONDITION_EXP of CRC may be a bit_xor_expression,
913 : : if CRC and data are xor-ed only for significant bit's check.
914 : : I.e. CONDITION_EXP in this case may be crc[]^data[].
915 : : So, the CONDITION_EXP will be CRC's condition if it's left or right
916 : : part's origin is the same as CRC_ORIGIN, and it's index equals to checked
917 : : significant bit's index. */
918 : 3490 : else if (is_a<bit_xor_expression *> (condition_exp))
919 : : {
920 : 3490 : bit_xor_expression *condition_xor_exp = as_a<bit_xor_expression *>
921 : 3490 : (condition_exp);
922 : 3490 : if (!(is_a<symbolic_bit *> (condition_xor_exp->get_left ())
923 : 3490 : && is_a<symbolic_bit *> (condition_xor_exp->get_right ())))
924 : 2 : return false;
925 : :
926 : 3488 : symbolic_bit *cond_left
927 : 3488 : = as_a<symbolic_bit *> (condition_xor_exp->get_left ());
928 : 3488 : symbolic_bit *cond_right
929 : 3488 : = as_a<symbolic_bit *> (condition_xor_exp->get_right ());
930 : 3488 : bool cond_left_is_crc = (crc_origin == cond_left->get_origin ()
931 : 3488 : && sb_index == cond_left->get_index ());
932 : 3488 : bool cond_right_is_crc = (crc_origin == cond_right->get_origin ()
933 : 3488 : && sb_index == cond_right->get_index ());
934 : 3488 : return cond_left_is_crc || cond_right_is_crc;
935 : : }
936 : : return false;
937 : : }
938 : :
939 : : /* Check whether the condition is checked for significant bit being 0 or 1.
940 : : If IS_ONE is 1, when check whether the significant bit is 1 (xor branch),
941 : : if 0, whether the significant bit is 0 (not xor branch). */
942 : :
943 : : bool
944 : 6036 : is_crc_xor_condition (tree crc_origin, unsigned char is_one,
945 : : size_t sb_index, state *final_state)
946 : : {
947 : : /* The CRC cases we detect must contain only one condition related to CRC. */
948 : 6036 : if (final_state->get_conditions ().elements () != 1)
949 : : return false;
950 : :
951 : 6036 : auto condition_iter = final_state->get_conditions ().begin ();
952 : 6036 : if (!is_a<bit_condition *> (*condition_iter))
953 : : return false;
954 : :
955 : : /* If the condition is for checking MSB/LSB, then
956 : : if is_one is 1 and the condition is for checking MSB/LSB being one, or
957 : : if is_one is 0 and condition is for checking MSB/LSB being 0
958 : : return true, otherwise - false. */
959 : 6036 : value_bit *cond_exp = (*condition_iter)->get_left ();
960 : 6036 : if (may_be_xors_condition (crc_origin, cond_exp, sb_index))
961 : : {
962 : 6034 : if (!is_a<bit *> ((*condition_iter)->get_right ()))
963 : : return false;
964 : :
965 : 6034 : bit_condition *condition = as_a<bit_condition *> (*condition_iter);
966 : 6034 : unsigned char comparison_val
967 : 6034 : = as_a<bit *> ((*condition_iter)->get_right ())->get_val ();
968 : 6034 : if (condition->get_code () == EQ_EXPR)
969 : 4289 : return comparison_val == is_one;
970 : 1745 : if (condition->get_code () == NE_EXPR)
971 : 1745 : return comparison_val != is_one;
972 : : return false;
973 : : }
974 : : return false;
975 : : }
976 : :
977 : : /* Check whether LSB/MSB of LFSR and calculated (maybe)CRC match.
978 : : If MSB is checked in the CRC loop, then here we check LSB, or vice versa.
979 : : CHECKED_SB_VALUE indicates which state of CRC value is checked.
980 : : If the CHECKED_SB_VALUE is 1 - then xor-ed CRC value is checked,
981 : : otherwise, not xor-ed is checked. */
982 : :
983 : : bool
984 : 6034 : given_sb_match (value_bit *crc, value_bit *lfsr,
985 : : unsigned short checked_sb_value)
986 : : {
987 : : /* If LFSR's MSB/LSB value is a constant (0 or 1),
988 : : then CRC's MSB/LSB must have the same value. */
989 : 6034 : if (is_a<bit *> (lfsr))
990 : : {
991 : 544 : if (!((is_a<bit *> (crc)
992 : 272 : && as_a<bit *> (crc)->get_val ()
993 : 272 : == as_a<bit *> (lfsr)->get_val ())))
994 : 0 : return false;
995 : : return true;
996 : : }
997 : : /* If LFSR's MSB/LSB value is a symbolic_bit
998 : : (that means MSB/LSB of the polynomial is 1),
999 : : then CRC's MSB/LSB must be equal to CHECKED_SB_VALUE. */
1000 : 5762 : else if (is_a<symbolic_bit *> (lfsr))
1001 : : {
1002 : 5762 : if (!(is_a<bit *> (crc)
1003 : 5762 : && (as_a<bit *> (crc)->get_val () == checked_sb_value)))
1004 : 0 : return false;
1005 : : return true;
1006 : : }
1007 : : return false;
1008 : : }
1009 : :
1010 : : /* Check whether significant bit of LFSR and calculated (maybe)CRC match. */
1011 : :
1012 : : bool
1013 : 6034 : sb_match (const value *lfsr, const value *crc_value, size_t sb_index,
1014 : : size_t it_end, unsigned short value)
1015 : : {
1016 : : /* If it's bit-forward CRC, check 0 bit's value. */
1017 : 6034 : if (sb_index == it_end - 1)
1018 : : {
1019 : 3312 : if (dump_file && (dump_flags & TDF_DETAILS))
1020 : 2976 : fprintf (dump_file, "Checking 0 bit.\n");
1021 : :
1022 : 3312 : if (!given_sb_match ((*crc_value)[0], (*lfsr)[0], value))
1023 : : return false;
1024 : : }
1025 : : /* If it's bit-reversed CRC, check last bit's value. */
1026 : 2722 : else if (sb_index == 0)
1027 : : {
1028 : 2722 : if (dump_file && (dump_flags & TDF_DETAILS))
1029 : 2304 : fprintf (dump_file, "Checking %zu bit.\n", it_end);
1030 : :
1031 : 2722 : if (!given_sb_match ((*crc_value)[it_end], (*lfsr)[it_end], value))
1032 : : return false;
1033 : : }
1034 : : else
1035 : : {
1036 : 0 : if (dump_file && (dump_flags & TDF_DETAILS))
1037 : 0 : fprintf (dump_file, "Significant bit index is incorrect.\n");
1038 : : }
1039 : : return true;
1040 : : }
1041 : :
1042 : : /* Match the CRC to the LFSR, where CRC's all bit values are
1043 : : symbolic_bit or symbolic_bit ^ 1, besides MSB/LSB (it may be constant). */
1044 : :
1045 : : bool
1046 : 6034 : lfsr_and_crc_bits_match (const value *lfsr, const value *crc_state,
1047 : : tree crc_origin, size_t i, size_t it_end,
1048 : : size_t sb_index, unsigned short checked_sb_value)
1049 : : {
1050 : :
1051 : : /* Check whether significant bits of LFSR and CRC match. */
1052 : 6034 : if (!sb_match (lfsr, crc_state, sb_index, it_end, checked_sb_value))
1053 : : return false;
1054 : :
1055 : 205728 : for (; i < it_end; i++)
1056 : : {
1057 : 199694 : if (dump_file && (dump_flags & TDF_DETAILS))
1058 : 175072 : fprintf (dump_file, "Checking %zu bit.\n", i);
1059 : :
1060 : : /* Check the case when in lfsr we have LFSR (i)^LFSR (SBi),
1061 : : where 0<i<LFSR_size and SBi is the index of MSB/LSB (LFSR_size-1/0).
1062 : : In that case in crc_state (resulting CRC)
1063 : : we must have crc (i) ^ 1 case, when condition is true
1064 : : and crc (i) when condition is false,
1065 : : (as CRC is xor-ed with the polynomial only if the LSB/MSB is one)
1066 : : where k is a whole number. */
1067 : 199694 : if (is_a<bit_xor_expression *> ((*lfsr)[i]))
1068 : : {
1069 : 69940 : size_t index = (as_a<bit_xor_expression *> ((*lfsr)[i]))->get_left ()
1070 : 69940 : ->get_index ();
1071 : : /* Check CRC value of xor branch. */
1072 : 69940 : if (checked_sb_value == 1)
1073 : : {
1074 : 34970 : if (!(is_a_valid_xor_one ((*crc_state)[i], crc_origin, index)))
1075 : : return false;
1076 : : }
1077 : : else /* Check CRC value of not xor branch. */
1078 : : {
1079 : 34970 : if (!(is_a_valid_symb ((*crc_state)[i], crc_origin, index)))
1080 : : return false;
1081 : : }
1082 : : }
1083 : : /* Check the case when in LFSR we have LFSR (i), where 0<i<LFSR_size.
1084 : : In that case in resulting CRC we must have crc (i) case,
1085 : : when condition is true or condition is false.
1086 : : If we have just LFSR (i), that means polynomial's i ± 1 bit is 0,
1087 : : so despite CRC is xor-ed or not, we will have crc (i). */
1088 : 129754 : else if (is_a<symbolic_bit *> ((*lfsr)[i]))
1089 : : {
1090 : 129754 : size_t index = (as_a<symbolic_bit *> ((*lfsr)[i]))->get_index ();
1091 : 129754 : if (!(is_a_valid_symb ((*crc_state)[i], crc_origin, index)))
1092 : : return false;
1093 : : }
1094 : : else
1095 : : {
1096 : 0 : if (dump_file && (dump_flags & TDF_DETAILS))
1097 : 0 : fprintf (dump_file, "Not expected expression in LFSR.\n");
1098 : 0 : return false;
1099 : : }
1100 : : }
1101 : : return true;
1102 : : }
1103 : :
1104 : : /* Return origin of CRC_BIT.
1105 : : The first tree in loop, from which CRC's calculation is started. */
1106 : :
1107 : : tree
1108 : 7991 : get_origin_of_crc_from_symb_bit (value_bit *crc_bit)
1109 : : {
1110 : 7991 : if (is_a<symbolic_bit *> (crc_bit))
1111 : 6036 : return as_a<symbolic_bit *> (crc_bit)->get_origin ();
1112 : : return nullptr;
1113 : : }
1114 : :
1115 : : /* Return origin of CRC_BIT. The first tree in loop, from which CRC's
1116 : : calculation is started. If the CRC_BIT is symbolic value, return its origin,
1117 : : otherwise return its left part's origin (right must be 1 if its CRC's
1118 : : value). */
1119 : :
1120 : : tree
1121 : 6036 : get_origin_of_crc (value_bit *crc_bit)
1122 : : {
1123 : 6036 : tree origin = get_origin_of_crc_from_symb_bit (crc_bit);
1124 : 6036 : if (origin)
1125 : : return origin;
1126 : 1955 : else if (is_a<bit_xor_expression *> (crc_bit))
1127 : : {
1128 : 1955 : value_bit *crc_bit_left
1129 : 1955 : = as_a<bit_xor_expression *> (crc_bit)->get_left ();
1130 : 1955 : return get_origin_of_crc_from_symb_bit (crc_bit_left);
1131 : : }
1132 : : return nullptr;
1133 : : }
1134 : :
1135 : : /* Determine and initialize significant bit index
1136 : : (if MSB is checked for CRC, then it's LSB index, and vice versa)
1137 : : and the remaining part's begin and end.
1138 : : SB_INDEX is the significant bit index.
1139 : : IT_BEG is the beginning of the remaining part.
1140 : : IT_END is the end of the remaining part. */
1141 : :
1142 : : void
1143 : 3019 : init_sb_index_and_other_part_begin_end (size_t &it_beg, size_t &it_end,
1144 : : size_t &sb_index, size_t crc_size,
1145 : : bool is_bit_forward)
1146 : : {
1147 : 3019 : it_end = crc_size;
1148 : 3019 : if (is_bit_forward)
1149 : : {
1150 : 1656 : sb_index = it_end - 1;
1151 : 1656 : it_beg = 1;
1152 : : }
1153 : : else
1154 : : {
1155 : 1363 : it_beg = 0;
1156 : 1363 : sb_index = 0;
1157 : 1363 : --it_end;
1158 : : }
1159 : 3019 : }
1160 : :
1161 : : /* Return true if CRC_STATE matches the LFSR, otherwise - false.
1162 : : LFSR - is created LFSR value for the given polynomial and CRC size.
1163 : : CRC_STATE - contains CRC's calculated value and execution path condition.
1164 : : IT_BEG and IT_END - are the border indexes of the value to be matched.
1165 : : SB_INDEX - is the significant bit index of the CRC value,
1166 : : which will be checked separately.
1167 : : IF MSB is checked for CRC, when sb_index will be the index of LSB.
1168 : : Otherwise, will be the index of MSB.
1169 : : CHECKED_SB_VALUE - is the significant bit's value (used for CRC's condition).
1170 : : If CHECKED_SB_VALUE is 1, it indicates that CRC_STATE is
1171 : : xor-ed path's state.
1172 : : If CHECKED_SB_VALUE is 0, then CRC_STATE is the state of the
1173 : : not xor branch. */
1174 : :
1175 : : bool
1176 : 6036 : lfsr_matches_crc_state (const value *lfsr, state *crc_state, value *crc_value,
1177 : : size_t it_beg, size_t it_end, size_t sb_index,
1178 : : unsigned short checked_sb_value)
1179 : : {
1180 : 6036 : if (dump_file && (dump_flags & TDF_DETAILS))
1181 : : {
1182 : 5280 : fprintf (dump_file, "Starting to match the following CRC value: ");
1183 : 5280 : state::print_value (crc_value);
1184 : : }
1185 : :
1186 : : /* Get the origin (name) of the calculated CRC value.
1187 : : All bits must have the same origin. */
1188 : 6036 : tree crc_origin = get_origin_of_crc ((*crc_value)[it_beg]);
1189 : 6036 : if (!crc_origin)
1190 : : return false;
1191 : :
1192 : 6036 : if (!is_crc_xor_condition (crc_origin, checked_sb_value, sb_index, crc_state))
1193 : : return false;
1194 : :
1195 : : /* Check whether CRC_VALUE and LFSR bits match. */
1196 : 6034 : return lfsr_and_crc_bits_match (lfsr, crc_value, crc_origin,
1197 : 6034 : it_beg, it_end, sb_index, checked_sb_value);
1198 : : }
1199 : :
1200 : : /* Return true if in the CRC_VALUE exists xor expression.
1201 : : Otherwise, return false. */
1202 : :
1203 : : bool
1204 : 3019 : is_xor_state (value *crc_value, size_t it_beg, size_t it_end)
1205 : : {
1206 : 8875 : for (unsigned j = it_beg; j < it_end; ++j)
1207 : 8875 : if ((*crc_value)[j]->get_type () == BIT_XOR_EXPRESSION)
1208 : : return true;
1209 : : return false;
1210 : : }
1211 : :
1212 : : /* Keep the value of calculated CRC. */
1213 : :
1214 : : value *
1215 : 6038 : get_crc_val (tree calculated_crc, state *curr_state)
1216 : : {
1217 : 6038 : if (!calculated_crc)
1218 : : {
1219 : 0 : if (dump_file && (dump_flags & TDF_DETAILS))
1220 : 0 : fprintf (dump_file, "Couldn't get the potential CRC variable.\n");
1221 : 0 : return nullptr;
1222 : : }
1223 : :
1224 : : /* When the calculated CRC is constant, it's not possible to determine
1225 : : whether the CRC has been calculated. */
1226 : 6038 : if (TREE_CODE (calculated_crc) == INTEGER_CST)
1227 : : {
1228 : 0 : if (dump_file && (dump_flags & TDF_DETAILS))
1229 : 0 : fprintf (dump_file, "Calculated CRC is a constant.\n");
1230 : 0 : return nullptr;
1231 : : }
1232 : :
1233 : : /* Get calculated return value. */
1234 : 6038 : value * crc_value = curr_state->get_value (calculated_crc);
1235 : :
1236 : 6038 : if (!crc_value)
1237 : : {
1238 : 0 : if (dump_file && (dump_flags & TDF_DETAILS))
1239 : 0 : fprintf (dump_file, "CRC is not in the state.\n");
1240 : 0 : return nullptr;
1241 : : }
1242 : : return crc_value;
1243 : : }
1244 : :
1245 : : /* Return true if all states from the FINAL_STATES match the LFSR,
1246 : : otherwise - false. */
1247 : :
1248 : : bool
1249 : 3021 : all_states_match_lfsr (value *lfsr, bool is_bit_forward, tree calculated_crc,
1250 : : const vec<state *> &final_states)
1251 : : {
1252 : 3021 : if (final_states.length () != 2)
1253 : : {
1254 : 2 : if (dump_file && (dump_flags & TDF_DETAILS))
1255 : 2 : fprintf (dump_file, "The final states count isn't two.\n");
1256 : 2 : return false;
1257 : : }
1258 : :
1259 : 3019 : value *crc_xor_value = get_crc_val (calculated_crc, final_states[0]);
1260 : 3019 : value *crc_not_xor_value = get_crc_val (calculated_crc, final_states[1]);
1261 : :
1262 : : /* LFSR's size must be equal to CRC's size. */
1263 : 3019 : if ((crc_xor_value->length () != lfsr->length ())
1264 : 3019 : || (crc_not_xor_value->length () != lfsr->length ()))
1265 : 0 : return false;
1266 : :
1267 : : /* Depending on whether it is bit-forward or reversed CRC,
1268 : : determine in which significant bit new value is added,
1269 : : to examine that bit separately.
1270 : : If in the CRC algorithm MSB (sb_index) is checked to be one for xor,
1271 : : then here we check LSB separately (marginal bit).
1272 : : If LSB (sb_index) is checked, then we separate MSB (marginal bit). */
1273 : 3019 : size_t it_beg, it_end, sb_index;
1274 : 3019 : init_sb_index_and_other_part_begin_end (it_beg, it_end, sb_index,
1275 : 3019 : crc_xor_value->length (),
1276 : : is_bit_forward);
1277 : :
1278 : 3019 : size_t xor_st_index = 0, not_xor_st_index = 1;
1279 : : /* If first is not xor's state,
1280 : : then the second state is assumed to be xor's state. */
1281 : 3019 : if (!is_xor_state (crc_xor_value, it_beg, it_end))
1282 : : {
1283 : 0 : std::swap (crc_xor_value, crc_not_xor_value);
1284 : 0 : xor_st_index = 1;
1285 : 0 : not_xor_st_index = 0;
1286 : : }
1287 : :
1288 : : /* If xor-ed CRC value doesn't match the LFSR value, return false. */
1289 : 3019 : if (!lfsr_matches_crc_state (lfsr, final_states[xor_st_index], crc_xor_value,
1290 : : it_beg, it_end, sb_index, 1))
1291 : : return false;
1292 : :
1293 : : /* If not xor-ed CRC value doesn't match the LFSR value, return false. */
1294 : 3017 : if (!lfsr_matches_crc_state (lfsr, final_states[not_xor_st_index],
1295 : : crc_not_xor_value, it_beg, it_end, sb_index, 0))
1296 : : return false;
1297 : :
1298 : : return true;
1299 : : }
|
