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 34949 : crc_symbolic_execution::is_used_outside_the_loop (tree def)
43 : {
44 34949 : imm_use_iterator imm_iter;
45 34949 : gimple *use_stmt;
46 110015 : FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
47 : {
48 46430 : if (!flow_bb_inside_loop_p (m_crc_loop, use_stmt->bb))
49 : {
50 6313 : if (is_a<gphi *> (use_stmt)
51 6313 : && 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 6313 : }
58 28636 : return false;
59 : }
60 :
61 : /* Calculate value of the rhs operation of GS assignment statement
62 : and assign it to lhs variable. */
63 :
64 : bool
65 30369 : crc_symbolic_execution::execute_assign_statement (const gassign *gs)
66 : {
67 30369 : enum tree_code rhs_code = gimple_assign_rhs_code (gs);
68 30369 : tree lhs = gimple_assign_lhs (gs);
69 30369 : if (dump_file && (dump_flags & TDF_DETAILS))
70 26367 : fprintf (dump_file, "lhs type : %s \n",
71 26367 : get_tree_code_name (TREE_CODE (lhs)));
72 :
73 : /* This will filter some normal cases too. Ex. usage of array. */
74 30369 : if (TREE_CODE (lhs) != SSA_NAME)
75 : return false;
76 :
77 : /* Check uses only when m_output_crc is known. */
78 30363 : if (m_output_crc)
79 28636 : if (is_used_outside_the_loop (lhs))
80 : return false;
81 :
82 30363 : 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 30363 : tree op1 = gimple_assign_rhs1 (gs);
93 30363 : tree op2 = nullptr;
94 :
95 30363 : if (gimple_num_ops (gs) == 3)
96 27147 : op2 = gimple_assign_rhs2 (gs);
97 :
98 30363 : state *current_state = m_states.last ();
99 30363 : 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 6838 : crc_symbolic_execution::add_edge (edge e, auto_vec<edge> &stack)
111 : {
112 6838 : if (EDGE_COUNT (e->dest->succs) == 0)
113 : return false;
114 :
115 6838 : edge next_bb_edge = EDGE_SUCC (e->dest, 0);
116 6838 : if (next_bb_edge && next_bb_edge->dest == m_crc_loop->header)
117 : {
118 6102 : if (dump_file && (dump_flags & TDF_DETAILS))
119 5155 : fprintf (dump_file, "Completed one iteration. "
120 : "Won't iterate loop once more, yet.\n");
121 :
122 6102 : return keep_states ();
123 : }
124 : else
125 : {
126 736 : if (dump_file && (dump_flags & TDF_DETAILS))
127 551 : 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 736 : stack.quick_push (e);
132 : }
133 736 : 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 9993 : crc_symbolic_execution::add_next_bbs (basic_block cond_bb,
144 : state *new_branch_state,
145 : auto_vec<edge> &stack)
146 : {
147 9993 : edge true_edge;
148 9993 : edge false_edge;
149 9993 : extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
150 :
151 : /* When the condition depends on symbolic values. */
152 9993 : if (new_branch_state->get_last_cond_status () == CS_SYM)
153 : {
154 : /* Supported CRC cases may have only two states. */
155 3155 : 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 3155 : m_states.quick_push (new_branch_state);
165 :
166 3155 : if (dump_file && (dump_flags & TDF_DETAILS))
167 2656 : fprintf (dump_file, "Adding true and false edges into the stack.\n");
168 :
169 : /* Add outgoing edges to the stack. */
170 3155 : stack.quick_push (false_edge);
171 3155 : stack.quick_push (true_edge);
172 :
173 3155 : return true;
174 : }
175 : /* When the condition evaluates to true. */
176 6838 : else if (new_branch_state->get_last_cond_status () == CS_TRUE)
177 : {
178 6351 : if (dump_file && (dump_flags & TDF_DETAILS))
179 5339 : fprintf (dump_file, "Condition is true.\n");
180 6351 : add_edge (true_edge, stack);
181 : }
182 : /* When the condition evaluates to false. */
183 487 : else if (new_branch_state->get_last_cond_status () == CS_FALSE)
184 : {
185 487 : if (dump_file && (dump_flags & TDF_DETAILS))
186 367 : fprintf (dump_file, "Condition is false.\n");
187 487 : 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 6838 : delete new_branch_state;
200 6838 : 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 9993 : crc_symbolic_execution::add_condition (const gcond *cond,
219 : state *current_state,
220 : state *new_branch_state)
221 : {
222 9993 : tree lhs = gimple_cond_lhs (cond);
223 9993 : tree rhs = gimple_cond_rhs (cond);
224 9993 : 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 8445 : case NE_EXPR:
234 8445 : {
235 8445 : new_branch_state->add_not_equal_cond (lhs, rhs);
236 8445 : if (new_branch_state->get_last_cond_status () == CS_SYM)
237 1707 : 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 1547 : case LT_EXPR:
248 1547 : {
249 1547 : new_branch_state->add_less_than_cond (lhs, rhs);
250 1547 : if (new_branch_state->get_last_cond_status () == CS_SYM)
251 1448 : 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 9993 : crc_symbolic_execution::resolve_condition (const gcond *cond,
282 : auto_vec<edge> &stack)
283 : {
284 9993 : state *current_state = m_states.last ();
285 9993 : state *new_branch_state = new state (*current_state);
286 :
287 : /* Create new states and for true and false branches keep corresponding
288 : conditions. */
289 9993 : if (!add_condition (cond, current_state, new_branch_state))
290 : return false;
291 :
292 : /* Add true and false edges to the stack. */
293 9993 : 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 6574 : bool crc_symbolic_execution::add_final_state (state *final_state)
300 : {
301 6574 : if (m_final_states.length () < 2)
302 6574 : 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 6574 : return true;
311 : }
312 :
313 : /* Keep the state of the executed path in final states. */
314 :
315 6574 : bool crc_symbolic_execution::keep_states ()
316 : {
317 6574 : if (m_states.is_empty ())
318 : return false;
319 :
320 6574 : 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 6574 : m_states.pop ();
328 6574 : return true;
329 : }
330 :
331 : /* Execute gimple statements of BB.
332 : Keeping values of variables in the state. */
333 :
334 : bool
335 16376 : crc_symbolic_execution::execute_bb_gimple_statements (basic_block bb,
336 : auto_vec<edge> &stack)
337 : {
338 32752 : for (gimple_stmt_iterator bsi = gsi_start_bb (bb);
339 55617 : !gsi_end_p (bsi); gsi_next (&bsi))
340 : {
341 49246 : gimple *gs = gsi_stmt (bsi);
342 49246 : if (dump_file && (dump_flags & TDF_DETAILS))
343 : {
344 40340 : fprintf (dump_file, "Executing ");
345 40340 : print_gimple_stmt (dump_file, gs, dump_flags);
346 : }
347 49246 : switch (gimple_code (gs))
348 : {
349 30369 : case GIMPLE_ASSIGN:
350 30369 : {
351 30369 : if (!execute_assign_statement (as_a<const gassign *> (gs)))
352 16376 : return false;
353 : break;
354 : }
355 9993 : case GIMPLE_COND:
356 9993 : {
357 9993 : 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 6371 : edge out_edge;
381 6371 : edge_iterator ei;
382 12742 : FOR_EACH_EDGE (out_edge, ei, bb->succs)
383 6371 : if (out_edge->dest != m_crc_loop->header)
384 6371 : 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 12945 : crc_symbolic_execution::execute_bb_phi_statements (basic_block bb,
396 : edge incoming_edge)
397 : {
398 19519 : for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
399 6574 : gsi_next (&gsi))
400 : {
401 6574 : gphi *phi = gsi.phi ();
402 6574 : tree lhs = gimple_phi_result (phi);
403 :
404 : /* Check uses only when m_output_crc is known. */
405 6574 : if (m_output_crc)
406 6313 : if (is_used_outside_the_loop (lhs))
407 0 : return false;
408 :
409 : /* Don't consider virtual operands. */
410 13148 : if (virtual_operand_p (lhs))
411 0 : continue;
412 :
413 6574 : if (dump_file && (dump_flags & TDF_DETAILS))
414 : {
415 5509 : fprintf (dump_file, "Determining the value "
416 : "for the following phi.\n");
417 5509 : print_gimple_stmt (dump_file, phi, dump_flags);
418 : }
419 :
420 6574 : tree rhs = PHI_ARG_DEF_FROM_EDGE (phi, incoming_edge);
421 :
422 6574 : state *current_state = m_states.last ();
423 6574 : if (!current_state->do_operation (VAR_DECL, rhs, nullptr, lhs))
424 : return false;
425 : }
426 12945 : return true;
427 : }
428 :
429 : /* Execute all statements of BB.
430 : Keeping values of variables in the state. */
431 :
432 : bool
433 12945 : crc_symbolic_execution::execute_bb_statements (basic_block bb,
434 : edge incoming_edge,
435 : auto_vec<edge> &stack)
436 : {
437 12945 : if (!execute_bb_phi_statements (bb, incoming_edge))
438 : return false;
439 :
440 12945 : 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 241 : assign_known_vals_to_header_phis (state *state, class loop *crc_loop)
448 : {
449 241 : basic_block bb = crc_loop->header;
450 1086 : for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
451 845 : gsi_next (&gsi))
452 : {
453 :
454 845 : gphi *phi = gsi.phi ();
455 845 : tree lhs = gimple_phi_result (phi);
456 :
457 : /* Don't consider virtual operands. */
458 1690 : if (virtual_operand_p (lhs))
459 24 : continue;
460 :
461 821 : tree inital_val = PHI_ARG_DEF_FROM_EDGE (phi,
462 : loop_preheader_edge (crc_loop));
463 821 : if (TREE_CODE (inital_val) == INTEGER_CST)
464 : {
465 488 : if (dump_file && (dump_flags & TDF_DETAILS))
466 : {
467 365 : fprintf (dump_file, "First value of phi is a constant, "
468 : "assigning the number to ");
469 365 : print_generic_expr (dump_file, lhs, dump_flags);
470 365 : fprintf (dump_file, " variable.\n");
471 : }
472 488 : state->do_operation (VAR_DECL, inital_val,
473 : nullptr, lhs);
474 : }
475 : }
476 241 : }
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 2917 : assign_calc_vals_to_header_phis (const vec<state *> &prev_states,
484 : state *curr_state,
485 : class loop *crc_loop)
486 : {
487 2917 : basic_block bb = crc_loop->header;
488 13502 : for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
489 10585 : gsi_next (&gsi))
490 : {
491 10585 : gphi *phi = gsi.phi ();
492 10585 : tree lhs = gimple_phi_result (phi);
493 :
494 : /* Don't consider virtual operands. */
495 21170 : if (virtual_operand_p (lhs))
496 163 : continue;
497 10422 : tree inital_val = PHI_ARG_DEF_FROM_EDGE (phi,
498 : loop_preheader_edge (crc_loop));
499 10422 : if (TREE_CODE (inital_val) == INTEGER_CST)
500 : {
501 5848 : tree input_tree = PHI_ARG_DEF_FROM_EDGE (phi,
502 : loop_latch_edge (crc_loop));
503 5848 : value * val_st1 = prev_states[0]->get_value (input_tree),
504 5848 : *val_st2 = prev_states[1]->get_value (input_tree);
505 5848 : if (!state::is_bit_vector (val_st1)
506 5848 : || !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 5848 : 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 5848 : if (dump_file && (dump_flags & TDF_DETAILS))
530 : {
531 4972 : fprintf (dump_file, "Assigning calculated number to ");
532 4972 : print_generic_expr (dump_file, lhs, dump_flags);
533 4972 : fprintf (dump_file, " variable.\n");
534 : }
535 5848 : unsigned HOST_WIDE_INT calc_number
536 5848 : = state::make_number (val_st1);
537 5848 : tree calc_num_tree = build_int_cstu (TREE_TYPE (lhs),
538 5848 : calc_number);
539 5848 : curr_state->do_operation (VAR_DECL, calc_num_tree, nullptr, lhs);
540 : }
541 : }
542 : }
543 2917 : 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 3158 : crc_symbolic_execution::create_initial_state (class loop *crc_loop)
554 : {
555 3158 : state *curr_state = new state;
556 3158 : if (!m_final_states.is_empty ())
557 : {
558 2917 : if (!assign_calc_vals_to_header_phis (m_final_states, curr_state,
559 : crc_loop))
560 : return nullptr;
561 2917 : state::remove_states (&m_final_states);
562 : }
563 : else
564 241 : 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 3158 : crc_symbolic_execution::symb_execute_crc_loop ()
572 : {
573 3158 : if (dump_file && (dump_flags & TDF_DETAILS))
574 2659 : fprintf (dump_file, "\n\nExecuting the loop with symbolic values.\n\n");
575 :
576 3158 : state *curr_state = create_initial_state (m_crc_loop);
577 3158 : if (!curr_state)
578 : return false;
579 :
580 3158 : m_states.quick_push (curr_state);
581 :
582 3158 : auto_vec<edge> stack (m_crc_loop->num_nodes);
583 :
584 3158 : basic_block header_bb = m_crc_loop->header;
585 3158 : 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 19211 : while (!stack.is_empty ())
591 : {
592 : /* Look at the edge on the top of the stack. */
593 12895 : edge e = stack.last ();
594 12895 : stack.pop ();
595 :
596 : /* Get destination block of the edge. */
597 12895 : 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 12895 : if (!flow_bb_inside_loop_p (m_crc_loop, dest_bb))
602 : {
603 472 : m_is_last_iteration = true;
604 472 : if (!keep_states ())
605 : return false;
606 472 : continue;
607 : }
608 :
609 : /* Execute statements. */
610 12423 : if (!execute_bb_statements (dest_bb, e, stack))
611 : return false;
612 : }
613 : return true;
614 3158 : }
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 273 : determine_index (tree data, bool is_shift_left)
621 : {
622 273 : 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 129 : 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 273 : 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 273 : basic_block bb = crc_loop->header;
638 1248 : for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
639 975 : gsi_next (&gsi))
640 : {
641 :
642 975 : gphi *phi = gsi.phi ();
643 975 : tree lhs = gimple_phi_result (phi);
644 :
645 : /* Don't consider virtual operands. */
646 1950 : if (virtual_operand_p (lhs))
647 37 : continue;
648 :
649 938 : if ((data_phi && phi == data_phi) || (!data_phi && phi == crc_phi))
650 : {
651 273 : if (dump_file && (dump_flags & TDF_DETAILS))
652 : {
653 206 : fprintf (dump_file, "Assigning the required value to ");
654 206 : print_generic_expr (dump_file, lhs, dump_flags);
655 206 : fprintf (dump_file, " variable.\n");
656 : }
657 273 : polynomial_state->do_assign_pow2 (lhs,
658 273 : determine_index (lhs,
659 : is_shift_left));
660 : }
661 665 : else if (phi == crc_phi)
662 : {
663 116 : if (dump_file && (dump_flags & TDF_DETAILS))
664 : {
665 112 : fprintf (dump_file, "Assigning 0 value to ");
666 112 : print_generic_expr (dump_file, lhs, dump_flags);
667 112 : fprintf (dump_file, " variable.\n");
668 : }
669 116 : polynomial_state->do_operation (VAR_DECL,
670 116 : build_zero_cst (TREE_TYPE (lhs)),
671 : nullptr, lhs);
672 : }
673 : else
674 : {
675 549 : edge loop_preheader = loop_preheader_edge (crc_loop);
676 549 : tree inital_val = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader);
677 549 : if (TREE_CODE (inital_val) == INTEGER_CST)
678 : {
679 543 : if (dump_file && (dump_flags & TDF_DETAILS))
680 : {
681 410 : fprintf (dump_file, "First value of phi is a constant, "
682 : "assigning the number to ");
683 410 : print_generic_expr (dump_file, lhs, dump_flags);
684 410 : fprintf (dump_file, " variable.\n");
685 : }
686 543 : 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 273 : }
705 :
706 : /* Execute the loop, which calculates CRC with initial values,
707 : to calculate the polynomial. */
708 :
709 : bool
710 273 : crc_symbolic_execution::execute_crc_loop (gphi *crc_phi,
711 : gphi *data_phi,
712 : bool is_shift_left)
713 : {
714 273 : if (dump_file && (dump_flags & TDF_DETAILS))
715 206 : fprintf (dump_file, "\n\nTrying to calculate the polynomial.\n\n");
716 :
717 273 : m_states.quick_push (new state);
718 :
719 273 : basic_block bb = m_crc_loop->header;
720 273 : assign_vals_to_header_phis (m_states.last (), m_crc_loop, crc_phi, data_phi,
721 : is_shift_left);
722 :
723 273 : auto_vec<edge> stack (m_crc_loop->num_nodes);
724 :
725 273 : 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 783 : while (!stack.is_empty ())
731 : {
732 : /* Look at the edge on the top of the stack. */
733 522 : edge e = stack.last ();
734 522 : stack.pop ();
735 :
736 : /* Get dest block of the edge. */
737 522 : basic_block bb = e->dest;
738 :
739 : /* Execute only basic blocks of the m_crc_loop. */
740 522 : if (!flow_bb_inside_loop_p (m_crc_loop, bb))
741 0 : continue;
742 :
743 : /* Execute statements. */
744 522 : if (!execute_bb_statements (bb, e, stack))
745 : return false;
746 : }
747 :
748 261 : 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 273 : }
757 :
758 : /* Return true if all bits of the POLYNOMIAL are constants (0 or 1).
759 : Otherwise return false. */
760 :
761 : bool
762 261 : polynomial_is_known (const value *polynomial)
763 : {
764 6949 : for (size_t i = 0; i < polynomial->length (); i++)
765 : {
766 6688 : 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 273 : crc_symbolic_execution::extract_polynomial (gphi *crc_phi, gphi *data_phi,
780 : tree calculated_crc,
781 : bool is_shift_left)
782 : {
783 273 : if (!execute_crc_loop (crc_phi, data_phi, is_shift_left))
784 12 : return std::make_pair (nullptr, nullptr);
785 :
786 261 : 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 261 : 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 261 : if (dump_file && (dump_flags & TDF_DETAILS))
798 : {
799 194 : fprintf (dump_file, "Getting the value of ");
800 194 : print_generic_expr (dump_file, calculated_crc, dump_flags);
801 194 : fprintf (dump_file, " variable.\n");
802 : }
803 :
804 : /* Get the value (bit vector) of the tree (it may be the polynomial). */
805 261 : value *polynomial = polynomial_state->get_value (calculated_crc);
806 261 : 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 261 : 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 194 : fprintf (dump_file, "Polynomial's value is ");
820 194 : state::print_value (polynomial);
821 : }
822 :
823 : /* Check that polynomial's all bits are constants. */
824 261 : 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 261 : 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 36090 : is_one (value_bit *const_bit)
843 : {
844 36090 : return is_a<bit *> (const_bit)
845 36090 : && (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 205950 : is_a_valid_symb (value_bit *bit, tree crc_origin, size_t lfsr_bit_index)
854 : {
855 205950 : if (!is_a<symbolic_bit *> (bit))
856 : return false;
857 :
858 205950 : symbolic_bit *sym_bit = as_a<symbolic_bit *> (bit);
859 205950 : bool is_correct_index = (sym_bit->get_index () == lfsr_bit_index);
860 205950 : bool is_same_crc_origin = (sym_bit->get_origin () == crc_origin);
861 205950 : 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 36090 : is_a_valid_xor_one (value_bit *bit, tree crc_origin, size_t lfsr_bit_index)
876 : {
877 36090 : if (is_a<bit_xor_expression *> (bit))
878 : {
879 36090 : bit_xor_expression *xor_exp = as_a<bit_xor_expression *> (bit);
880 36090 : if (is_one (xor_exp->get_right ()))
881 36090 : return is_a_valid_symb (xor_exp->get_left (), crc_origin,
882 36090 : 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 6308 : may_be_xors_condition (tree crc_origin, value_bit *condition_exp,
894 : size_t sb_index)
895 : {
896 6308 : if (!crc_origin)
897 : return false;
898 :
899 6308 : 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 6308 : if (is_a<symbolic_bit *> (condition_exp))
907 : {
908 2802 : symbolic_bit *condition_symbolic = as_a<symbolic_bit *> (condition_exp);
909 2802 : return crc_origin == condition_symbolic->get_origin ()
910 2802 : && 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 3506 : else if (is_a<bit_xor_expression *> (condition_exp))
919 : {
920 3506 : bit_xor_expression *condition_xor_exp = as_a<bit_xor_expression *>
921 3506 : (condition_exp);
922 3506 : if (!(is_a<symbolic_bit *> (condition_xor_exp->get_left ())
923 3506 : && is_a<symbolic_bit *> (condition_xor_exp->get_right ())))
924 2 : return false;
925 :
926 3504 : symbolic_bit *cond_left
927 3504 : = as_a<symbolic_bit *> (condition_xor_exp->get_left ());
928 3504 : symbolic_bit *cond_right
929 3504 : = as_a<symbolic_bit *> (condition_xor_exp->get_right ());
930 3504 : bool cond_left_is_crc = (crc_origin == cond_left->get_origin ()
931 3504 : && sb_index == cond_left->get_index ());
932 3504 : bool cond_right_is_crc = (crc_origin == cond_right->get_origin ()
933 3504 : && sb_index == cond_right->get_index ());
934 3504 : 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 6308 : 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 6308 : if (final_state->get_conditions ().elements () != 1)
949 : return false;
950 :
951 6308 : auto condition_iter = final_state->get_conditions ().begin ();
952 6308 : 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 6308 : value_bit *cond_exp = (*condition_iter)->get_left ();
960 6308 : if (may_be_xors_condition (crc_origin, cond_exp, sb_index))
961 : {
962 6306 : if (!is_a<bit *> ((*condition_iter)->get_right ()))
963 : return false;
964 :
965 6306 : bit_condition *condition = as_a<bit_condition *> (*condition_iter);
966 6306 : unsigned char comparison_val
967 6306 : = as_a<bit *> ((*condition_iter)->get_right ())->get_val ();
968 6306 : if (condition->get_code () == EQ_EXPR)
969 4601 : return comparison_val == is_one;
970 1705 : if (condition->get_code () == NE_EXPR)
971 1705 : 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 6306 : 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 6306 : if (is_a<bit *> (lfsr))
990 : {
991 736 : if (!((is_a<bit *> (crc)
992 368 : && as_a<bit *> (crc)->get_val ()
993 368 : == 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 5938 : else if (is_a<symbolic_bit *> (lfsr))
1001 : {
1002 5938 : if (!(is_a<bit *> (crc)
1003 5938 : && (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 6306 : 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 6306 : if (sb_index == it_end - 1)
1018 : {
1019 3408 : if (dump_file && (dump_flags & TDF_DETAILS))
1020 3008 : fprintf (dump_file, "Checking 0 bit.\n");
1021 :
1022 3408 : 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 2898 : else if (sb_index == 0)
1027 : {
1028 2898 : if (dump_file && (dump_flags & TDF_DETAILS))
1029 2304 : fprintf (dump_file, "Checking %zu bit.\n", it_end);
1030 :
1031 2898 : 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 6306 : 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 6306 : if (!sb_match (lfsr, crc_state, sb_index, it_end, checked_sb_value))
1053 : return false;
1054 :
1055 212256 : for (; i < it_end; i++)
1056 : {
1057 205950 : if (dump_file && (dump_flags & TDF_DETAILS))
1058 175296 : 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 205950 : if (is_a<bit_xor_expression *> ((*lfsr)[i]))
1068 : {
1069 72180 : size_t index = (as_a<bit_xor_expression *> ((*lfsr)[i]))->get_left ()
1070 72180 : ->get_index ();
1071 : /* Check CRC value of xor branch. */
1072 72180 : if (checked_sb_value == 1)
1073 : {
1074 36090 : 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 36090 : 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 133770 : else if (is_a<symbolic_bit *> ((*lfsr)[i]))
1089 : {
1090 133770 : size_t index = (as_a<symbolic_bit *> ((*lfsr)[i]))->get_index ();
1091 133770 : 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 8287 : get_origin_of_crc_from_symb_bit (value_bit *crc_bit)
1109 : {
1110 8287 : if (is_a<symbolic_bit *> (crc_bit))
1111 6308 : 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 6308 : get_origin_of_crc (value_bit *crc_bit)
1122 : {
1123 6308 : tree origin = get_origin_of_crc_from_symb_bit (crc_bit);
1124 6308 : if (origin)
1125 : return origin;
1126 1979 : else if (is_a<bit_xor_expression *> (crc_bit))
1127 : {
1128 1979 : value_bit *crc_bit_left
1129 1979 : = as_a<bit_xor_expression *> (crc_bit)->get_left ();
1130 1979 : 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 3155 : 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 3155 : it_end = crc_size;
1148 3155 : if (is_bit_forward)
1149 : {
1150 1704 : sb_index = it_end - 1;
1151 1704 : it_beg = 1;
1152 : }
1153 : else
1154 : {
1155 1451 : it_beg = 0;
1156 1451 : sb_index = 0;
1157 1451 : --it_end;
1158 : }
1159 3155 : }
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 6308 : 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 6308 : if (dump_file && (dump_flags & TDF_DETAILS))
1181 : {
1182 5312 : fprintf (dump_file, "Starting to match the following CRC value: ");
1183 5312 : 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 6308 : tree crc_origin = get_origin_of_crc ((*crc_value)[it_beg]);
1189 6308 : if (!crc_origin)
1190 : return false;
1191 :
1192 6308 : 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 6306 : return lfsr_and_crc_bits_match (lfsr, crc_value, crc_origin,
1197 6306 : 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 3155 : is_xor_state (value *crc_value, size_t it_beg, size_t it_end)
1205 : {
1206 9571 : for (unsigned j = it_beg; j < it_end; ++j)
1207 9571 : 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 6310 : get_crc_val (tree calculated_crc, state *curr_state)
1216 : {
1217 6310 : 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 6310 : 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 6310 : value * crc_value = curr_state->get_value (calculated_crc);
1235 :
1236 6310 : 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 3158 : all_states_match_lfsr (value *lfsr, bool is_bit_forward, tree calculated_crc,
1250 : const vec<state *> &final_states)
1251 : {
1252 3158 : if (final_states.length () != 2)
1253 : {
1254 3 : if (dump_file && (dump_flags & TDF_DETAILS))
1255 3 : fprintf (dump_file, "The final states count isn't two.\n");
1256 3 : return false;
1257 : }
1258 :
1259 3155 : value *crc_xor_value = get_crc_val (calculated_crc, final_states[0]);
1260 3155 : 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 3155 : if ((crc_xor_value->length () != lfsr->length ())
1264 3155 : || (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 3155 : size_t it_beg, it_end, sb_index;
1274 3155 : init_sb_index_and_other_part_begin_end (it_beg, it_end, sb_index,
1275 3155 : crc_xor_value->length (),
1276 : is_bit_forward);
1277 :
1278 3155 : 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 3155 : 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 3155 : 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 3153 : 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 : }
|
