From 106e333e0dca830690a98ca75efbac20883dc664 Mon Sep 17 00:00:00 2001 From: Sebastian Huber Date: Sat, 13 Mar 2021 10:46:21 +0100 Subject: validation: Optimize transition map This change significantly reduces the size of the generated source code as well as the read-only data size. --- rtemsspec/tests/test_validation.py | 341 ++++++++++--------------------------- rtemsspec/validation.py | 121 +++++++------ 2 files changed, 160 insertions(+), 302 deletions(-) diff --git a/rtemsspec/tests/test_validation.py b/rtemsspec/tests/test_validation.py index b64b0cf1..a3e32b72 100644 --- a/rtemsspec/tests/test_validation.py +++ b/rtemsspec/tests/test_validation.py @@ -624,216 +624,67 @@ static T_fixture Directive_Fixture = { .initial_context = &Directive_Instance }; -static const uint8_t Directive_TransitionMap[][ 2 ] = { - { - Directive_Post_Status_InvAddr, - Directive_Post_Id_NullPtr - }, { - Directive_Post_Status_InvName, - Directive_Post_Id_Nop - }, { - Directive_Post_Status_InvAddr, - Directive_Post_Id_NullPtr - }, { - Directive_Post_Status_InvName, - Directive_Post_Id_Nop - }, { - Directive_Post_Status_InvAddr, - Directive_Post_Id_NullPtr - }, { - Directive_Post_Status_InvName, - Directive_Post_Id_Nop - }, { - Directive_Post_Status_InvAddr, - Directive_Post_Id_NullPtr - }, { - Directive_Post_Status_InvName, - Directive_Post_Id_Nop - }, { - Directive_Post_Status_InvAddr, - Directive_Post_Id_NullPtr - }, { - Directive_Post_Status_InvName, - Directive_Post_Id_Nop - }, { - Directive_Post_Status_InvAddr, - Directive_Post_Id_NullPtr - }, { - Directive_Post_Status_InvName, - Directive_Post_Id_Nop - }, { - Directive_Post_Status_InvAddr, - Directive_Post_Id_NullPtr - }, { - Directive_Post_Status_Ok, - Directive_Post_Id_Self - }, { - Directive_Post_Status_InvAddr, - Directive_Post_Id_NullPtr - }, { - Directive_Post_Status_Ok, - Directive_Post_Id_Self - }, { - Directive_Post_Status_InvAddr, - Directive_Post_Id_NullPtr - }, { - Directive_Post_Status_Ok, - Directive_Post_Id_Self - }, { - Directive_Post_Status_InvAddr, - Directive_Post_Id_NullPtr - }, { - Directive_Post_Status_Ok, - Directive_Post_Id_Self - }, { - Directive_Post_Status_InvAddr, - Directive_Post_Id_NullPtr - }, { - Directive_Post_Status_Ok, - Directive_Post_Id_Self - }, { - Directive_Post_Status_InvAddr, - Directive_Post_Id_NullPtr - }, { - Directive_Post_Status_Ok, - Directive_Post_Id_Self - }, { - Directive_Post_Status_InvAddr, - Directive_Post_Id_NullPtr - }, { - Directive_Post_Status_Ok, - Directive_Post_Id_LocalTask - }, { - Directive_Post_Status_InvAddr, - Directive_Post_Id_NullPtr - }, { +typedef struct { + uint16_t Skip : 1; + uint16_t Pre_Name_NA : 1; + uint16_t Pre_Node_NA : 1; + uint16_t Pre_Id_NA : 1; + uint16_t Post_Status : 3; + uint16_t Post_Id : 3; +} Directive_Entry; + +#define E( x0, x1, x2, x3, x4, x5) { x0, x1, x2, x3, \\ + Directive_Post_Status_##x4, Directive_Post_Id_##x5 } + +static const Directive_Entry +Directive_Map[] = { + E( 0, 0, 0, 0, InvAddr, NullPtr ), + E( 0, 0, 0, 0, InvName, Nop ), + E( 0, 0, 0, 0, InvAddr, NullPtr ), + E( 0, 0, 0, 0, InvName, Nop ), + E( 0, 0, 0, 0, InvAddr, NullPtr ), + E( 0, 0, 0, 0, InvName, Nop ), + E( 0, 0, 0, 0, InvAddr, NullPtr ), + E( 0, 0, 0, 0, InvName, Nop ), + E( 0, 0, 0, 0, InvAddr, NullPtr ), + E( 0, 0, 0, 0, InvName, Nop ), + E( 0, 0, 0, 0, InvAddr, NullPtr ), + E( 0, 0, 0, 0, InvName, Nop ), + E( 0, 0, 0, 0, InvAddr, NullPtr ), + E( 0, 0, 0, 0, Ok, Self ), + E( 0, 0, 0, 0, InvAddr, NullPtr ), + E( 0, 0, 0, 0, Ok, Self ), + E( 0, 0, 0, 0, InvAddr, NullPtr ), + E( 0, 0, 0, 0, Ok, Self ), + E( 0, 0, 0, 0, InvAddr, NullPtr ), + E( 0, 0, 0, 0, Ok, Self ), + E( 0, 0, 0, 0, InvAddr, NullPtr ), + E( 0, 0, 0, 0, Ok, Self ), + E( 0, 0, 0, 0, InvAddr, NullPtr ), + E( 0, 0, 0, 0, Ok, Self ), + E( 0, 0, 0, 0, InvAddr, NullPtr ), + E( 0, 0, 0, 0, Ok, LocalTask ), + E( 0, 0, 0, 0, InvAddr, NullPtr ), #if defined(RTEMS_MULTIPROCESSING) - Directive_Post_Status_Ok, - Directive_Post_Id_RemoteTask + E( 0, 0, 0, 0, Ok, RemoteTask ), #else - Directive_Post_Status_InvName, - Directive_Post_Id_Nop + E( 0, 0, 0, 0, InvName, Nop ), #endif - }, { - Directive_Post_Status_InvAddr, - Directive_Post_Id_NullPtr - }, { - Directive_Post_Status_InvName, - Directive_Post_Id_Nop - }, { - Directive_Post_Status_InvAddr, - Directive_Post_Id_NullPtr - }, { - Directive_Post_Status_Ok, - Directive_Post_Id_LocalTask - }, { - Directive_Post_Status_InvAddr, - Directive_Post_Id_NullPtr - }, { + E( 0, 0, 0, 0, InvAddr, NullPtr ), + E( 0, 0, 0, 0, InvName, Nop ), + E( 0, 0, 0, 0, InvAddr, NullPtr ), + E( 0, 0, 0, 0, Ok, LocalTask ), + E( 0, 0, 0, 0, InvAddr, NullPtr ), #if defined(RTEMS_MULTIPROCESSING) - Directive_Post_Status_Ok, - Directive_Post_Id_RemoteTask + E( 0, 0, 0, 0, Ok, RemoteTask ), #else - Directive_Post_Status_InvName, - Directive_Post_Id_Nop + E( 0, 0, 0, 0, InvName, Nop ), #endif - }, { - Directive_Post_Status_InvAddr, - Directive_Post_Id_NullPtr - }, { - Directive_Post_Status_Ok, - Directive_Post_Id_LocalTask - } + E( 0, 0, 0, 0, InvAddr, NullPtr ), + E( 0, 0, 0, 0, Ok, LocalTask ) }; -static const struct { - uint8_t Skip : 1; - uint8_t Pre_Name_NA : 1; - uint8_t Pre_Node_NA : 1; - uint8_t Pre_Id_NA : 1; -} Directive_TransitionInfo[] = { - { - 0, 0, 0, 0 - }, { - 0, 0, 0, 0 - }, { - 0, 0, 0, 0 - }, { - 0, 0, 0, 0 - }, { - 0, 0, 0, 0 - }, { - 0, 0, 0, 0 - }, { - 0, 0, 0, 0 - }, { - 0, 0, 0, 0 - }, { - 0, 0, 0, 0 - }, { - 0, 0, 0, 0 - }, { - 0, 0, 0, 0 - }, { - 0, 0, 0, 0 - }, { - 0, 0, 0, 0 - }, { - 0, 0, 0, 0 - }, { - 0, 0, 0, 0 - }, { - 0, 0, 0, 0 - }, { - 0, 0, 0, 0 - }, { - 0, 0, 0, 0 - }, { - 0, 0, 0, 0 - }, { - 0, 0, 0, 0 - }, { - 0, 0, 0, 0 - }, { - 0, 0, 0, 0 - }, { - 0, 0, 0, 0 - }, { - 0, 0, 0, 0 - }, { - 0, 0, 0, 0 - }, { - 0, 0, 0, 0 - }, { - 0, 0, 0, 0 - }, { -#if defined(RTEMS_MULTIPROCESSING) - 0, 0, 0, 0 -#else - 0, 0, 0, 0 -#endif - }, { - 0, 0, 0, 0 - }, { - 0, 0, 0, 0 - }, { - 0, 0, 0, 0 - }, { - 0, 0, 0, 0 - }, { - 0, 0, 0, 0 - }, { -#if defined(RTEMS_MULTIPROCESSING) - 0, 0, 0, 0 -#else - 0, 0, 0, 0 -#endif - }, { - 0, 0, 0, 0 - }, { - 0, 0, 0, 0 - } -}; +#undef E static void Directive_Action( Directive_Context *ctx ) { @@ -857,7 +708,7 @@ T_TEST_CASE_FIXTURE( Directive, &Directive_Fixture ) ctx->pcs[ 0 ] < Directive_Pre_Name_NA; ++ctx->pcs[ 0 ] ) { - if ( Directive_TransitionInfo[ index ].Pre_Name_NA ) { + if ( Directive_Map[ index ].Pre_Name_NA ) { ctx->pcs[ 0 ] = Directive_Pre_Name_NA; index += ( Directive_Pre_Name_NA - 1 ) * Directive_Pre_Node_NA @@ -869,7 +720,7 @@ T_TEST_CASE_FIXTURE( Directive, &Directive_Fixture ) ctx->pcs[ 1 ] < Directive_Pre_Node_NA; ++ctx->pcs[ 1 ] ) { - if ( Directive_TransitionInfo[ index ].Pre_Node_NA ) { + if ( Directive_Map[ index ].Pre_Node_NA ) { ctx->pcs[ 1 ] = Directive_Pre_Node_NA; index += ( Directive_Pre_Node_NA - 1 ) * Directive_Pre_Id_NA; @@ -880,12 +731,14 @@ T_TEST_CASE_FIXTURE( Directive, &Directive_Fixture ) ctx->pcs[ 2 ] < Directive_Pre_Id_NA; ++ctx->pcs[ 2 ] ) { - if ( Directive_TransitionInfo[ index ].Pre_Id_NA ) { + Directive_Entry entry; + + if ( Directive_Map[ index ].Pre_Id_NA ) { ctx->pcs[ 2 ] = Directive_Pre_Id_NA; index += ( Directive_Pre_Id_NA - 1 ); } - if ( Directive_TransitionInfo[ index ].Skip ) { + if ( Directive_Map[ index ].Skip ) { ++index; continue; } @@ -894,11 +747,9 @@ T_TEST_CASE_FIXTURE( Directive, &Directive_Fixture ) Directive_Pre_Node_Prepare( ctx, ctx->pcs[ 1 ] ); Directive_Pre_Id_Prepare( ctx, ctx->pcs[ 2 ] ); Directive_Action( ctx ); - Directive_Post_Status_Check( - ctx, - Directive_TransitionMap[ index ][ 0 ] - ); - Directive_Post_Id_Check( ctx, Directive_TransitionMap[ index ][ 1 ] ); + entry = Directive_Map[ index ]; + Directive_Post_Status_Check( ctx, entry.Post_Status ); + Directive_Post_Id_Check( ctx, entry.Post_Id ); ++index; } } @@ -2184,48 +2035,29 @@ static T_fixture Action2_Fixture = { .initial_context = &Action2_Instance }; -static const uint8_t Action2_TransitionMap[][ 2 ] = { - { - Action2_Post_A_X, - Action2_Post_B_Y - }, { - Action2_Post_A_Y, - Action2_Post_B_NA - }, { - Action2_Post_A_X, - Action2_Post_B_X - }, { - Action2_Post_A_X, - Action2_Post_B_Y - }, { - Action2_Post_A_Y, - Action2_Post_B_NA - }, { - Action2_Post_A_NA, - Action2_Post_B_NA - } -}; - -static const struct { +typedef struct { uint8_t Skip : 1; uint8_t Pre_A_NA : 1; uint8_t Pre_B_NA : 1; -} Action2_TransitionInfo[] = { - { - 0, 0, 0 - }, { - 0, 1, 0 - }, { - 0, 0, 0 - }, { - 0, 0, 0 - }, { - 0, 1, 0 - }, { - 1, 0, 0 - } + uint8_t Post_A : 2; + uint8_t Post_B : 2; +} Action2_Entry; + +#define E( x0, x1, x2, x3, x4) { x0, x1, x2, Action2_Post_A_##x3, \\ + Action2_Post_B_##x4 } + +static const Action2_Entry +Action2_Map[] = { + E( 0, 0, 0, X, Y ), + E( 0, 1, 0, Y, NA ), + E( 0, 0, 0, X, X ), + E( 0, 0, 0, X, Y ), + E( 0, 1, 0, Y, NA ), + E( 1, 0, 0, NA, NA ) }; +#undef E + static void Action2_Prepare( Action2_Context *ctx ) { /* Prepare */ @@ -2261,7 +2093,7 @@ void Action2_Run( int *a, int b, int *c ) ctx->pcs[ 0 ] < Action2_Pre_A_NA; ++ctx->pcs[ 0 ] ) { - if ( Action2_TransitionInfo[ index ].Pre_A_NA ) { + if ( Action2_Map[ index ].Pre_A_NA ) { ctx->pcs[ 0 ] = Action2_Pre_A_NA; index += ( Action2_Pre_A_NA - 1 ) * Action2_Pre_B_NA; @@ -2272,12 +2104,14 @@ void Action2_Run( int *a, int b, int *c ) ctx->pcs[ 1 ] < Action2_Pre_B_NA; ++ctx->pcs[ 1 ] ) { - if ( Action2_TransitionInfo[ index ].Pre_B_NA ) { + Action2_Entry entry; + + if ( Action2_Map[ index ].Pre_B_NA ) { ctx->pcs[ 1 ] = Action2_Pre_B_NA; index += ( Action2_Pre_B_NA - 1 ); } - if ( Action2_TransitionInfo[ index ].Skip ) { + if ( Action2_Map[ index ].Skip ) { ++index; continue; } @@ -2286,8 +2120,9 @@ void Action2_Run( int *a, int b, int *c ) Action2_Pre_A_Prepare( ctx, ctx->pcs[ 0 ] ); Action2_Pre_B_Prepare( ctx, ctx->pcs[ 1 ] ); Action2_Action( ctx ); - Action2_Post_A_Check( ctx, Action2_TransitionMap[ index ][ 0 ] ); - Action2_Post_B_Check( ctx, Action2_TransitionMap[ index ][ 1 ] ); + entry = Action2_Map[ index ]; + Action2_Post_A_Check( ctx, entry.Post_A ); + Action2_Post_B_Check( ctx, entry.Post_B ); Action2_Cleanup( ctx ); ++index; } diff --git a/rtemsspec/validation.py b/rtemsspec/validation.py index 77450fb8..358d7f37 100644 --- a/rtemsspec/validation.py +++ b/rtemsspec/validation.py @@ -30,6 +30,7 @@ import itertools import math import os import re +import textwrap from typing import Any, Dict, List, NamedTuple, Optional, Tuple from rtemsspec.content import CContent, CInclude, enabled_by_to_exp, \ @@ -484,8 +485,15 @@ def _condition_index_to_enum(prefix: str, tuple([f"{prefix}_{condition['name']}"] + [ f"{prefix}_{condition['name']}_{state['name']}" for state in condition["states"] - ] + [f"{prefix}_{condition['name']}_NA"]) - for index, condition in enumerate(conditions)) + ] + [f"{prefix}_{condition['name']}_NA"]) for condition in conditions) + + +def _condition_index_to_name(conditions: List[Any]) -> _ConditionIndexToEnum: + return tuple( + tuple( + itertools.chain((state["name"] + for state in condition["states"]), ["NA"])) + for condition in conditions) def _add_condition_enum(content: CContent, @@ -509,6 +517,8 @@ class _ActionRequirementTestItem(_TestItem): f"{self.ident}_Pre", item["pre-conditions"]) self._post_index_to_enum = _condition_index_to_enum( f"{self.ident}_Post", item["post-conditions"]) + self._post_index_to_state = _condition_index_to_name( + item["post-conditions"]) self._pre_state_to_index = _state_to_index(item["pre-conditions"]) self._post_state_to_index = _state_to_index(item["post-conditions"]) self._pre_index_to_condition = dict( @@ -613,7 +623,7 @@ class _ActionRequirementTestItem(_TestItem): "defined by transition map entry " f"{transition_map[map_index][0].map_entry_index}") transition_map[map_index].append( - _Transition(enabled_by, post_cond, " " + ", ".join(info), + _Transition(enabled_by, post_cond, ", ".join(info), trans_index)) def _add_default(self, trans_index: int, transition_map: _TransitionMap, @@ -622,7 +632,7 @@ class _ActionRequirementTestItem(_TestItem): if not transition: transition.append( _Transition( - "1", post_cond, " " + + "1", post_cond, ", ".join(info + ["0"] * self._pre_condition_count), trans_index)) @@ -663,20 +673,26 @@ class _ActionRequirementTestItem(_TestItem): self._add_default(trans_index, transition_map, info, post_cond) return transition_map - def _post_condition_enumerators(self, conditions: Any) -> str: - return ",\n".join( - f" {self._post_index_to_enum[index][condition + 1]}" - for index, condition in enumerate(conditions)) + def _get_entry(self, variant: _Transition) -> str: + entry = f"E( {variant.info}, " + ", ".join( + self._post_index_to_state[cond_index][state_index] + for cond_index, state_index in enumerate( + variant.post_conditions)) + " )," + wrapper = textwrap.TextWrapper() + wrapper.initial_indent = " " + wrapper.subsequent_indent = " " + wrapper.width = 75 + return "\n".join(wrapper.wrap(entry)) + + def _get_entry_bits(self) -> int: + bits = self._pre_condition_count + 1 + for enum in self._post_index_to_enum: + bits += math.ceil(math.log2(len(enum))) + return 2**max(math.ceil(math.log2(bits)), 3) def _add_transition_map(self, content: CContent) -> None: transition_map = self._get_transition_map() - content.add([ - "static const uint8_t " - f"{self.ident}_TransitionMap[][ {self._post_condition_count} ]" - " = {", " {" - ]) - map_elements = [] - info_elements = [] + entries = [] for map_index, transistions in enumerate(transition_map): if not transistions or transistions[0].enabled_by != "1": raise ValueError( @@ -684,43 +700,48 @@ class _ActionRequirementTestItem(_TestItem): "entry for pre-condition set " f"{{{self._map_index_to_pre_conditions(map_index)}}}") if len(transistions) == 1: - map_elements.append( - self._post_condition_enumerators( - transistions[0].post_conditions)) - info_elements.append(transistions[0].info) + entries.append(self._get_entry(transistions[0])) else: ifelse = "#if " - map_enumerators = [] # type: List[str] - info_enumerators = [] # type: List[str] + enumerators = [] # type: List[str] for variant in transistions[1:]: - map_enumerators.append(ifelse + variant.enabled_by) - info_enumerators.append(ifelse + variant.enabled_by) - map_enumerators.append( - self._post_condition_enumerators( - variant.post_conditions)) - info_enumerators.append(variant.info) + enumerators.append(ifelse + variant.enabled_by) + enumerators.append(self._get_entry(variant)) ifelse = "#elif " - map_enumerators.append("#else") - info_enumerators.append("#else") - map_enumerators.append( - self._post_condition_enumerators( - transistions[0].post_conditions)) - info_enumerators.append(transistions[0].info) - map_enumerators.append("#endif") - info_enumerators.append("#endif") - map_elements.append("\n".join(map_enumerators)) - info_elements.append("\n".join(info_enumerators)) - content.append(["\n }, {\n".join(map_elements), " }", "};"]) - pre_bits = 2**max(math.ceil(math.log2(self._pre_condition_count + 1)), - 3) - content.add("static const struct {") + enumerators.append("#else") + enumerators.append(self._get_entry(transistions[0])) + enumerators.append("#endif") + entries.append("\n".join(enumerators)) + bits = self._get_entry_bits() + content.add("typedef struct {") with content.indent(): - content.append(f"uint{pre_bits}_t Skip : 1;") + content.append(f"uint{bits}_t Skip : 1;") for condition in self["pre-conditions"]: + content.append(f"uint{bits}_t Pre_{condition['name']}_NA : 1;") + for condition in self["post-conditions"]: + state_bits = math.ceil(math.log2(len(condition["states"]) + 1)) content.append( - f"uint{pre_bits}_t Pre_{condition['name']}_NA : 1;") - content.add([f"}} {self.ident}_TransitionInfo[] = {{", " {"]) - content.append(["\n }, {\n".join(info_elements), " }", "};"]) + f"uint{bits}_t Post_{condition['name']} : {state_bits};") + content.add(f"}} {self.ident}_Entry;") + pre_count = 1 + self._pre_condition_count + entry = ("#define E( " + ", ".join( + f"x{index}" + for index in range(pre_count + self._post_condition_count) + ) + ") { " + ", ".join( + itertools.chain((f"x{index}" for index in range(pre_count)), ( + f"{self.ident}_Post_{condition['name']}_##x{pre_count + index}" + for index, condition in enumerate(self["post-conditions"])))) + + " }") + wrapper = textwrap.TextWrapper() + wrapper.initial_indent = "" + wrapper.subsequent_indent = " " + wrapper.width = 77 + content.add(" \\\n".join(wrapper.wrap(entry))) + content.add( + [f"static const {self.ident}_Entry", f"{self.ident}_Map[] = {{"]) + entries[-1] = entries[-1].replace("),", ")") + content.append(entries) + content.append(["};", "", "#undef E"]) def _add_call(self, content: CContent, key: str, name: str) -> None: if self[key] is not None: @@ -728,7 +749,7 @@ class _ActionRequirementTestItem(_TestItem): content.call_function(None, f"{self.ident}_{name}", ["ctx"]) def _add_loop_body(self, content: CContent) -> None: - with content.condition(f"{self.ident}_TransitionInfo[ index ].Skip"): + with content.condition(f"{self.ident}_Map[ index ].Skip"): content.append(["++index;", "continue;"]) content.add_blank_line() self._add_call(content, "test-prepare", "Prepare") @@ -737,12 +758,12 @@ class _ActionRequirementTestItem(_TestItem): content.call_function(None, f"{enum[0]}_Prepare", ["ctx", f"ctx->pcs[ {index} ]"]) self._add_call(content, "test-action", "Action") - transition_map = f"{self.ident}_TransitionMap" + content.append(f"entry = {self.ident}_Map[ index ];") for index, enum in enumerate(self._post_index_to_enum): content.gap = False content.call_function( None, f"{enum[0]}_Check", - ["ctx", f"{transition_map}[ index ][ {index} ]"]) + ["ctx", f"entry.Post_{self._post_index_to_name[index]}"]) self._add_call(content, "test-cleanup", "Cleanup") content.append("++index;") @@ -753,8 +774,10 @@ class _ActionRequirementTestItem(_TestItem): end = self._pre_index_to_enum[index][-1] with content.for_loop(f"{var} = {begin}", f"{var} < {end}", f"++{var}"): + if index + 1 == self._pre_cond_count: + content.add(f"{self.ident}_Entry entry;") name = self._item['pre-conditions'][index]["name"] - pre_na = f"{self.ident}_TransitionInfo[ index ].Pre_{name}_NA" + pre_na = f"{self.ident}_Map[ index ].Pre_{name}_NA" with content.condition(pre_na): content.append(f"{var} = {end};") content.append(f"index += ( {end} - 1 )") -- cgit v1.2.3