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