#include "crc-verification.h"
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "tree.h"
#include "gimple.h"
#include "ssa.h"
#include "gimple-iterator.h"
#include "tree-cfg.h"
#include "cfganal.h"
#include "tree-ssa-loop.h"

Include dependency graph for crc-verification.cc:

Functions
void	assign_known_vals_to_header_phis (state state, class loop crc_loop)

bool	assign_calc_vals_to_header_phis (const vec< state * > &prev_states, state curr_state, class loop crc_loop)

unsigned HOST_WIDE_INT	determine_index (tree data, bool is_shift_left)

void	assign_vals_to_header_phis (state polynomial_state, class loop crc_loop, gphi crc_phi, gphi data_phi, bool is_shift_left)

bool	polynomial_is_known (const value *polynomial)

bool	is_one (value_bit *const_bit)

bool	is_a_valid_symb (value_bit *bit, tree crc_origin, size_t lfsr_bit_index)

bool	is_a_valid_xor_one (value_bit *bit, tree crc_origin, size_t lfsr_bit_index)

bool	may_be_xors_condition (tree crc_origin, value_bit *condition_exp, size_t sb_index)

bool	is_crc_xor_condition (tree crc_origin, unsigned char is_one, size_t sb_index, state *final_state)

bool	given_sb_match (value_bit crc, value_bit lfsr, unsigned short checked_sb_value)

bool	sb_match (const value lfsr, const value crc_value, size_t sb_index, size_t it_end, unsigned short value)

bool	lfsr_and_crc_bits_match (const value lfsr, const value crc_state, tree crc_origin, size_t i, size_t it_end, size_t sb_index, unsigned short checked_sb_value)

tree	get_origin_of_crc_from_symb_bit (value_bit *crc_bit)

tree	get_origin_of_crc (value_bit *crc_bit)

void	init_sb_index_and_other_part_begin_end (size_t &it_beg, size_t &it_end, size_t &sb_index, size_t crc_size, bool is_bit_forward)

bool	lfsr_matches_crc_state (const value lfsr, state crc_state, value *crc_value, size_t it_beg, size_t it_end, size_t sb_index, unsigned short checked_sb_value)

bool	is_xor_state (value *crc_value, size_t it_beg, size_t it_end)

value *	get_crc_val (tree calculated_crc, state *curr_state)

bool	all_states_match_lfsr (value lfsr, bool is_bit_forward, tree calculated_crc, const vec< state > &final_states)

Function Documentation

◆ all_states_match_lfsr()

bool all_states_match_lfsr	(	value *	lfsr,
		bool	is_bit_forward,
		tree	calculated_crc,
		const vec< state * > &	final_states )

Return true if all states from the FINAL_STATES match the LFSR,
otherwise - false.

References dump_file, dump_flags, get_crc_val(), init_sb_index_and_other_part_begin_end(), is_xor_state(), lfsr_matches_crc_state(), and TDF_DETAILS.

Referenced by crc_optimization::loop_calculates_crc().

◆ assign_calc_vals_to_header_phis()

bool assign_calc_vals_to_header_phis	(	const vec< state * > &	prev_states,
		state *	curr_state,
		class loop *	crc_loop )

If the phi statements' result variables have initial constant value in the
beginning of the loop, initialize those variables with
the value calculated during the previous iteration.

References build_int_cstu(), dump_file, dump_flags, gimple_phi_result(), gsi_end_p(), gsi_next(), gsi_start_phis(), loop::header, loop_latch_edge(), loop_preheader_edge(), PHI_ARG_DEF_FROM_EDGE, print_generic_expr(), TDF_DETAILS, TREE_CODE, TREE_TYPE, and virtual_operand_p().

Referenced by crc_symbolic_execution::create_initial_state().

◆ assign_known_vals_to_header_phis()

void assign_known_vals_to_header_phis	(	state *	state,
		class loop *	crc_loop )

If the phi statements' result variables have initial constant value in the
beginning of the loop, initialize those variables.

References dump_file, dump_flags, gimple_phi_result(), gsi_end_p(), gsi_next(), gsi_start_phis(), loop::header, loop_preheader_edge(), PHI_ARG_DEF_FROM_EDGE, print_generic_expr(), TDF_DETAILS, TREE_CODE, and virtual_operand_p().

Referenced by crc_symbolic_execution::create_initial_state().

◆ assign_vals_to_header_phis()

void assign_vals_to_header_phis	(	state *	polynomial_state,
		class loop *	crc_loop,
		gphi *	crc_phi,
		gphi *	data_phi,
		bool	is_shift_left )

Assign appropriate values to data, CRC
and other phi results to calculate the polynomial.

References build_zero_cst(), determine_index(), dump_file, dump_flags, gimple_phi_result(), gsi_end_p(), gsi_next(), gsi_start_phis(), loop::header, loop_preheader_edge(), PHI_ARG_DEF_FROM_EDGE, print_generic_expr(), TDF_DETAILS, TREE_CODE, TREE_TYPE, and virtual_operand_p().

Referenced by crc_symbolic_execution::execute_crc_loop().

◆ determine_index()

unsigned HOST_WIDE_INT determine_index	(	tree	data,
		bool	is_shift_left )

Determine which bit of the DATA must be 1.
We assume that last bit must be 1.

References tree_to_uhwi(), TREE_TYPE, and TYPE_SIZE.

Referenced by assign_vals_to_header_phis().

◆ get_crc_val()

value * get_crc_val	(	tree	calculated_crc,
		state *	curr_state )

Keep the value of calculated CRC.

References dump_file, dump_flags, TDF_DETAILS, and TREE_CODE.

Referenced by all_states_match_lfsr().

◆ get_origin_of_crc()

tree get_origin_of_crc ( value_bit * crc_bit )

Return origin of CRC_BIT.  The first tree in loop, from which CRC's
calculation is started.  If the CRC_BIT is symbolic value, return its origin,
otherwise return its left part's origin (right must be 1 if its CRC's
value).

References as_a(), get_origin_of_crc_from_symb_bit(), and is_a().

Referenced by lfsr_matches_crc_state().

◆ get_origin_of_crc_from_symb_bit()

tree get_origin_of_crc_from_symb_bit ( value_bit * crc_bit )

Return origin of CRC_BIT.
The first tree in loop, from which CRC's calculation is started.

References as_a(), and is_a().

Referenced by get_origin_of_crc().

◆ given_sb_match()

bool given_sb_match	(	value_bit *	crc,
		value_bit *	lfsr,
		unsigned short	checked_sb_value )

Check whether LSB/MSB of LFSR and calculated (maybe)CRC match.
If MSB is checked in the CRC loop, then here we check LSB, or vice versa.
CHECKED_SB_VALUE indicates which state of CRC value is checked.
If the CHECKED_SB_VALUE is 1 - then xor-ed CRC value is checked,
otherwise, not xor-ed is checked.

References as_a(), and is_a().

Referenced by sb_match().

◆ init_sb_index_and_other_part_begin_end()

void init_sb_index_and_other_part_begin_end	(	size_t &	it_beg,
		size_t &	it_end,
		size_t &	sb_index,
		size_t	crc_size,
		bool	is_bit_forward )

Determine and initialize significant bit index
(if MSB is checked for CRC, then it's LSB index, and vice versa)
and the remaining part's begin and end.
SB_INDEX is the significant bit index.
IT_BEG is the beginning of the remaining part.
IT_END is the end of the remaining part.

Referenced by all_states_match_lfsr().

◆ is_a_valid_symb()

bool is_a_valid_symb	(	value_bit *	bit,
		tree	crc_origin,
		size_t	lfsr_bit_index )

Return true if BIT is symbolic,
its index is same as LFSR bit's index (LFSR_BIT_INDEX)
and the origin is same as CRC_ORIGIN.

References as_a(), and is_a().

Referenced by is_a_valid_xor_one(), and lfsr_and_crc_bits_match().

◆ is_a_valid_xor_one()

bool is_a_valid_xor_one	(	value_bit *	bit,
		tree	crc_origin,
		size_t	lfsr_bit_index )

Return true if the BIT is a valid crc[LFSR_BIT_INDEX] ^ 1,
where i is a whole number and left part's origin is same as CRC_ORIGIN.
LFSR_BIT_INDEX is the index of the LFSR bit from the same position as in CRC.

If there is lfsr[8] at LFSR value vectors' 9-th bit,
when in the CRC vectors' 9-th bit's value must be
crc[8].

Otherwise, return false.

References as_a(), is_a(), is_a_valid_symb(), and is_one().

Referenced by lfsr_and_crc_bits_match().

◆ is_crc_xor_condition()

bool is_crc_xor_condition	(	tree	crc_origin,
		unsigned char	is_one,
		size_t	sb_index,
		state *	final_state )

Check whether the condition is checked for significant bit being 0 or 1.
If IS_ONE is 1, when check whether the significant bit is 1 (xor branch),
if 0, whether the significant bit is 0 (not xor branch).

References as_a(), is_a(), is_one(), and may_be_xors_condition().

Referenced by lfsr_matches_crc_state().

◆ is_one()

bool is_one ( value_bit * const_bit )

Return true if CONST_BIT value equals to 1.
Otherwise, return false.

References as_a(), and is_a().

Referenced by is_a_valid_xor_one(), and is_crc_xor_condition().

◆ is_xor_state()

bool is_xor_state	(	value *	crc_value,
		size_t	it_beg,
		size_t	it_end )

Return true if in the CRC_VALUE exists xor expression.
Otherwise, return false.

Referenced by all_states_match_lfsr().

◆ lfsr_and_crc_bits_match()

bool lfsr_and_crc_bits_match	(	const value *	lfsr,
		const value *	crc_state,
		tree	crc_origin,
		size_t	i,
		size_t	it_end,
		size_t	sb_index,
		unsigned short	checked_sb_value )

Match the CRC to the LFSR, where CRC's all bit values are
symbolic_bit or symbolic_bit ^ 1, besides MSB/LSB (it may be constant).

References as_a(), dump_file, dump_flags, i, is_a(), is_a_valid_symb(), is_a_valid_xor_one(), sb_match(), and TDF_DETAILS.

Referenced by lfsr_matches_crc_state().

◆ lfsr_matches_crc_state()

bool lfsr_matches_crc_state	(	const value *	lfsr,
		state *	crc_state,
		value *	crc_value,
		size_t	it_beg,
		size_t	it_end,
		size_t	sb_index,
		unsigned short	checked_sb_value )

Return true if CRC_STATE matches the LFSR, otherwise - false.
LFSR - is created LFSR value for the given polynomial and CRC size.
CRC_STATE - contains CRC's calculated value and execution path condition.
IT_BEG and IT_END - are the border indexes of the value to be matched.
SB_INDEX - is the significant bit index of the CRC value,
           which will be checked separately.
           IF MSB is checked for CRC, when sb_index will be the index of LSB.
           Otherwise, will be the index of MSB.
CHECKED_SB_VALUE - is the significant bit's value (used for CRC's condition).
           If CHECKED_SB_VALUE is 1, it indicates that CRC_STATE is
           xor-ed path's state.
           If CHECKED_SB_VALUE is 0, then CRC_STATE is the state of the
           not xor branch.

References dump_file, dump_flags, get_origin_of_crc(), is_crc_xor_condition(), lfsr_and_crc_bits_match(), and TDF_DETAILS.

Referenced by all_states_match_lfsr().

◆ may_be_xors_condition()

bool may_be_xors_condition	(	tree	crc_origin,
		value_bit *	condition_exp,
		size_t	sb_index )

Return true, if CONDITION_EXP checks CRC's MSB/LSB value
(under which xor is/not done).
Otherwise, return false.

References as_a(), and is_a().

Referenced by is_crc_xor_condition().

◆ polynomial_is_known()

bool polynomial_is_known ( const value * polynomial )

Return true if all bits of the POLYNOMIAL are constants (0 or 1).
Otherwise return false.

References i, and is_a().

Referenced by crc_symbolic_execution::extract_polynomial().

◆ sb_match()

bool sb_match	(	const value *	lfsr,
		const value *	crc_value,
		size_t	sb_index,
		size_t	it_end,
		unsigned short	value )

Check whether significant bit of LFSR and calculated (maybe)CRC match.

References dump_file, dump_flags, given_sb_match(), and TDF_DETAILS.

Referenced by lfsr_and_crc_bits_match().

Functions

Function Documentation

◆ all_states_match_lfsr()

◆ assign_calc_vals_to_header_phis()

◆ assign_known_vals_to_header_phis()

◆ assign_vals_to_header_phis()

◆ determine_index()

◆ get_crc_val()

◆ get_origin_of_crc()

◆ get_origin_of_crc_from_symb_bit()

◆ given_sb_match()

◆ init_sb_index_and_other_part_begin_end()

◆ is_a_valid_symb()

◆ is_a_valid_xor_one()

◆ is_crc_xor_condition()

◆ is_one()

◆ is_xor_state()

◆ lfsr_and_crc_bits_match()

◆ lfsr_matches_crc_state()

◆ may_be_xors_condition()

◆ polynomial_is_known()

◆ sb_match()