# HG changeset patch # User Mario de Sousa # Date 1339612992 -3600 # Node ID 99a284cec1f2dcd71cf2747833ebb0b47f4bf025 # Parent 76bad71998960c18ce470c0abe4f0daac4faf418 Add 'dimension' parameter to subrange_c, fill it correctly, and use it. diff -r 76bad7199896 -r 99a284cec1f2 absyntax/absyntax.def --- a/absyntax/absyntax.def Wed Jun 13 14:21:30 2012 +0100 +++ b/absyntax/absyntax.def Wed Jun 13 19:43:12 2012 +0100 @@ -315,7 +315,8 @@ SYM_REF2(subrange_specification_c, integer_type_name, subrange) /* signed_integer DOTDOT signed_integer */ -SYM_REF2(subrange_c, lower_limit, upper_limit) +/* dimension will be filled in during stage 3 (array_range_check_c) with the number of elements in this subrange */ +SYM_REF2(subrange_c, lower_limit, upper_limit, unsigned long long int dimension;) /* enumerated_type_name ':' enumerated_spec_init */ SYM_REF2(enumerated_type_declaration_c, enumerated_type_name, enumerated_spec_init) diff -r 76bad7199896 -r 99a284cec1f2 stage3/array_range_check.cc --- a/stage3/array_range_check.cc Wed Jun 13 14:21:30 2012 +0100 +++ b/stage3/array_range_check.cc Wed Jun 13 19:43:12 2012 +0100 @@ -44,6 +44,8 @@ #include "array_range_check.hh" +#include // required for std::numeric_limits + #define FIRST_(symbol1, symbol2) (((symbol1)->first_order < (symbol2)->first_order) ? (symbol1) : (symbol2)) #define LAST_(symbol1, symbol2) (((symbol1)->last_order > (symbol2)->last_order) ? (symbol1) : (symbol2)) @@ -79,13 +81,19 @@ current_display_error_level = 0; } + + array_range_check_c::~array_range_check_c(void) { } + + int array_range_check_c::get_error_count() { return error_count; } + + void array_range_check_c::check_dimension_count(array_variable_c *symbol) { int dimension_count; symbol_c *var_decl; @@ -97,6 +105,8 @@ STAGE3_ERROR(0, symbol, symbol, "Number of subscripts/indexes does not match the number of subscripts/indexes in the array's declaration (array has %d indexes)", dimension_count); } + + void array_range_check_c::check_bounds(array_variable_c *symbol) { list_c *l; /* the subscript_list */ symbol_c *var_decl; @@ -128,6 +138,71 @@ } } + + + + + + + + +/*************************/ +/* B.1 - Common elements */ +/*************************/ +/**********************/ +/* B.1.3 - Data types */ +/**********************/ +/********************************/ +/* B 1.3.3 - Derived data types */ +/********************************/ + +/* signed_integer DOTDOT signed_integer */ +/* dimension will be filled in during stage 3 (array_range_check_c) with the number of elements in this subrange */ +// SYM_REF2(subrange_c, lower_limit, upper_limit, unsigned long long int dimension) +void *array_range_check_c::visit(subrange_c *symbol) { + unsigned long long int dimension = 0; // we use unsigned long long instead of uint64_t since it might just happen to be larger than uint64_t in the platform used for compiling this code!! + +/* Determine the size of the array... */ + if (VALID_CVALUE( int64, symbol->upper_limit) && VALID_CVALUE( int64, symbol->lower_limit)) { + // do the sums in such a way that no overflow is possible... even during intermediate steps used by compiler! + // remember that the result (dimension) is unsigned, while the operands are signed!! + // dimension = GET_CVALUE( int64, symbol->upper_limit) - VALID_CVALUE( int64, symbol->lower_limit); + if (VALID_CVALUE( int64, symbol->lower_limit) >= 0) { + dimension = GET_CVALUE( int64, symbol->upper_limit) - GET_CVALUE( int64, symbol->lower_limit); + } else { + dimension = -GET_CVALUE( int64, symbol->lower_limit); + dimension += GET_CVALUE( int64, symbol->upper_limit); + } + } else if (VALID_CVALUE(uint64, symbol->upper_limit) && VALID_CVALUE(uint64, symbol->lower_limit)) { + dimension = GET_CVALUE(uint64, symbol->upper_limit) - VALID_CVALUE(uint64, symbol->lower_limit); + } else if (VALID_CVALUE(uint64, symbol->upper_limit) && VALID_CVALUE( int64, symbol->lower_limit)) { + if (VALID_CVALUE( int64, symbol->lower_limit) >= 0) { + dimension = GET_CVALUE( int64, symbol->upper_limit) - GET_CVALUE( int64, symbol->lower_limit); + } else { + unsigned long long int lower_ull; + lower_ull = -GET_CVALUE( int64, symbol->lower_limit); + dimension = GET_CVALUE( int64, symbol->upper_limit) + lower_ull; + /* TODO: check this overflow test, it does not seem to be working. I don't have to go now... Will check later. */ + if (dimension < lower_ull) + STAGE3_ERROR(0, symbol, symbol, "Number of elements in array subrange exceeds maximum number of elements (%llu).", std::numeric_limits< unsigned long long int >::max()); + } + } else ERROR; + + /* correct value for dimension is actually ---> dimension = upper_limit - lower_limit + 1 + * Up to now, we have only determined dimension = upper_limit - lower_limit + * We must first check whether this last increment will cause an overflow! + */ + if (dimension == std::numeric_limits< unsigned long long int >::max()) + STAGE3_ERROR(0, symbol, symbol, "Number of elements in array subrange exceeds maximum number of elements (%llu).", std::numeric_limits< unsigned long long int >::max()); + + /* correct value for dimension is actually ---> dimension = upper_limit - lower_limit + 1 */ + dimension++; + + symbol->dimension = dimension; + return NULL; +} + + /*********************/ /* B 1.4 - Variables */ /*********************/ @@ -147,7 +222,9 @@ /***********************/ /* B 1.5.1 - Functions */ /***********************/ +// SYM_REF4(function_declaration_c, derived_function_name, type_name, var_declarations_list, function_body) void *array_range_check_c::visit(function_declaration_c *symbol) { + symbol->var_declarations_list->accept(*this); // required for visiting subrange_c search_varfb_instance_type = new search_varfb_instance_type_c(symbol); // search_var_instance_decl = new search_var_instance_decl_c(symbol); symbol->function_body->accept(*this); @@ -161,7 +238,9 @@ /*****************************/ /* B 1.5.2 - Function blocks */ /*****************************/ +// SYM_REF3(function_block_declaration_c, fblock_name, var_declarations, fblock_body) void *array_range_check_c::visit(function_block_declaration_c *symbol) { + symbol->var_declarations->accept(*this); // required for visiting subrange_c search_varfb_instance_type = new search_varfb_instance_type_c(symbol); // search_var_instance_decl = new search_var_instance_decl_c(symbol); symbol->fblock_body->accept(*this); @@ -175,7 +254,9 @@ /**********************/ /* B 1.5.3 - Programs */ /**********************/ +// SYM_REF3(program_declaration_c, program_type_name, var_declarations, function_block_body) void *array_range_check_c::visit(program_declaration_c *symbol) { + symbol->var_declarations->accept(*this); // required for visiting subrange_c search_varfb_instance_type = new search_varfb_instance_type_c(symbol); // search_var_instance_decl = new search_var_instance_decl_c(symbol); symbol->function_block_body->accept(*this); diff -r 76bad7199896 -r 99a284cec1f2 stage3/array_range_check.hh --- a/stage3/array_range_check.hh Wed Jun 13 14:21:30 2012 +0100 +++ b/stage3/array_range_check.hh Wed Jun 13 19:43:12 2012 +0100 @@ -54,6 +54,18 @@ virtual ~array_range_check_c(void); int get_error_count(); + /*************************/ + /* B.1 - Common elements */ + /*************************/ + /**********************/ + /* B.1.3 - Data types */ + /**********************/ + /********************************/ + /* B 1.3.3 - Derived data types */ + /********************************/ + /* NOTE: we may later want to move this to a visitor that will focus on analysing the data type declarations! */ + void *visit(subrange_c *symbol); + /*********************/ /* B 1.4 - Variables */ /*********************/ diff -r 76bad7199896 -r 99a284cec1f2 stage3/constant_folding.cc --- a/stage3/constant_folding.cc Wed Jun 13 14:21:30 2012 +0100 +++ b/stage3/constant_folding.cc Wed Jun 13 19:43:12 2012 +0100 @@ -217,8 +217,6 @@ - - /* NOTE: * Most of the conditions to detect overflows on signed and unsigned integer operations were adapted from * https://www.securecoding.cert.org/confluence/display/seccode/INT32-C.+Ensure+that+operations+on+signed+integers+do+not+result+in+overflow?showComments=false diff -r 76bad7199896 -r 99a284cec1f2 stage4/generate_c/generate_c.cc --- a/stage4/generate_c/generate_c.cc Wed Jun 13 14:21:30 2012 +0100 +++ b/stage4/generate_c/generate_c.cc Wed Jun 13 19:43:12 2012 +0100 @@ -31,6 +31,7 @@ #include #include + #include "../../util/symtable.hh" #include "../../util/dsymtable.hh" #include "../../absyntax/visitor.hh" @@ -53,6 +54,12 @@ #define STAGE4_ERROR(symbol1, symbol2, ...) {stage4err("while generating C code", symbol1, symbol2, __VA_ARGS__); exit(EXIT_FAILURE);} +/* Macros to access the constant value of each expression (if it exists) from the annotation introduced to the symbol_c object by constant_folding_c in stage3! */ +/* NOTE: The following test is correct in the presence of a NULL pointer, as the logical evaluation will be suspended as soon as the first condition is false! */ +#define VALID_CVALUE(dtype, symbol) ((NULL != (symbol)->const_value_##dtype) && (symbol_c::cs_const_value == (symbol)->const_value_##dtype->status)) +#define GET_CVALUE(dtype, symbol) ((symbol)->const_value_##dtype->value) + + /***********************************************************************/ @@ -782,19 +789,18 @@ /* signed_integer DOTDOT signed_integer */ //SYM_REF2(subrange_c, lower_limit, upper_limit) void *visit(subrange_c *symbol) { - int dimension = extract_int64_value(symbol->upper_limit) - extract_int64_value(symbol->lower_limit) + 1; switch (current_mode) { case arrayname_im: current_array_name += "_"; { std::stringstream ss; - ss << dimension; + ss << symbol->dimension; current_array_name += ss.str(); } break; case arraydeclaration_im: s4o_incl.print("["); - s4o_incl.print_integer(dimension); + s4o_incl.print_integer(symbol->dimension); s4o_incl.print("]"); default: generate_c_typedecl_c::visit(symbol); diff -r 76bad7199896 -r 99a284cec1f2 stage4/generate_c/generate_c_typedecl.cc --- a/stage4/generate_c/generate_c_typedecl.cc Wed Jun 13 14:21:30 2012 +0100 +++ b/stage4/generate_c/generate_c_typedecl.cc Wed Jun 13 19:43:12 2012 +0100 @@ -75,15 +75,15 @@ basetypedeclaration_t current_basetypedeclaration; - void print_integer(unsigned int integer) { - char str[10]; - sprintf(str, "%d", integer); + void print_integer(unsigned long long int integer) { + char str[24]; + sprintf(str, "%llu", integer); s4o.print(str); } - void print_integer_incl(unsigned int integer) { - char str[10]; - sprintf(str, "%d", integer); + void print_integer_incl(unsigned long long int integer) { + char str[24]; + sprintf(str, "%llu", integer); s4o_incl.print(str); } @@ -255,8 +255,7 @@ case array_td: if (current_basetypedeclaration == arraysubrange_bd) { s4o_incl.print("["); - dimension = extract_int64_value(symbol->upper_limit) - extract_int64_value(symbol->lower_limit) + 1; - print_integer_incl(dimension); + print_integer_incl(symbol->dimension); s4o_incl.print("]"); } else diff -r 76bad7199896 -r 99a284cec1f2 stage4/generate_c/generate_c_vardecl.cc --- a/stage4/generate_c/generate_c_vardecl.cc Wed Jun 13 14:21:30 2012 +0100 +++ b/stage4/generate_c/generate_c_vardecl.cc Wed Jun 13 19:43:12 2012 +0100 @@ -22,6 +22,8 @@ * used in safety-critical situations without a full and competent review. */ +#include // required for std::numeric_limits + class initialization_analyzer_c: public null_visitor_c { public: typedef enum { @@ -74,9 +76,9 @@ private: int current_dimension; - int array_size; - int defined_values_count; - int current_initialization_count; + unsigned long long int array_size; + unsigned long long int defined_values_count; + unsigned long long int current_initialization_count; public: generate_c_array_initialization_c(stage4out_c *s4o_ptr): generate_c_typedecl_c(s4o_ptr) {} @@ -124,7 +126,7 @@ if (array_default_initialization != NULL && defined_values_count < array_size) array_default_initialization->accept(*this); if (defined_values_count < array_size) { - for (int i = defined_values_count; i < array_size; i++) { + for (unsigned long long int i = defined_values_count; i < array_size; i++) { if (defined_values_count > 0) s4o.print(","); array_default_value->accept(*this); @@ -211,14 +213,17 @@ /* signed_integer DOTDOT signed_integer */ //SYM_REF2(subrange_c, lower_limit, upper_limit) void *visit(subrange_c *symbol) { - int dimension = extract_int64_value(symbol->upper_limit) - extract_int64_value(symbol->lower_limit) + 1; switch (current_mode) { case arraysize_am: - array_size *= dimension; + /* res = a * b; ---> Check for overflow by pre-condition: If (UINT_MAX / a) < b => overflow! */ + if ((std::numeric_limits< unsigned long long int >::max() / array_size) < symbol->dimension) + STAGE4_ERROR(symbol, symbol, "The array containing this subrange has a total number of elements larger than the maximum currently supported (%llu).", + std::numeric_limits< unsigned long long int >::max()); + array_size *= symbol->dimension; break; case typedecl_am: s4o.print("_"); - s4o.print_integer(dimension); + s4o.print_integer(symbol->dimension); break; default: break; @@ -260,14 +265,14 @@ /* integer '(' [array_initial_element] ')' */ /* array_initial_element may be NULL ! */ void *visit(array_initial_elements_c *symbol) { - int initial_element_number; + unsigned long long int initial_element_number; switch (current_mode) { case initializationvalue_am: initial_element_number = extract_int64_value(symbol->integer); if (current_initialization_count < defined_values_count) { - int temp_element_number = 0; - int diff = defined_values_count - current_initialization_count; + unsigned long long int temp_element_number = 0; + unsigned long long int diff = defined_values_count - current_initialization_count; if (diff <= initial_element_number) temp_element_number = initial_element_number - diff; current_initialization_count += initial_element_number - 1; @@ -281,7 +286,7 @@ current_initialization_count += initial_element_number - 1; if (defined_values_count + initial_element_number > array_size) ERROR; - for (int i = 0; i < initial_element_number; i++) { + for (unsigned long long int i = 0; i < initial_element_number; i++) { if (i > 0) s4o.print(","); if (symbol->array_initial_element != NULL) { @@ -1407,9 +1412,8 @@ /* signed_integer DOTDOT signed_integer */ //SYM_REF2(subrange_c, lower_limit, upper_limit) void *visit(subrange_c *symbol) { - long long dimension = extract_int64_value(symbol->upper_limit) - extract_int64_value(symbol->lower_limit) + 1; s4o.print("_"); - print_integer(dimension); + print_integer(symbol->dimension); return NULL; }