Ongoing Project: RESM

JMP $FCE2
MarcWalters
Member
Member
Posts: 50
Joined: Wed Jun 11, 2014 2:33 pm
Location: Lake Macquarie, NSW, Australia

Ongoing Project: RESM

Post by MarcWalters » Fri Apr 06, 2018 8:48 am

The assembly board here is a little quiet, so I might throw one of my little pet projects into the ring for discussion.

I've stripped down an earlier 6502 implementation of UML State Charts and come up with something lighter and easier to use. The code presented here is fully working, but relies on some other framework routines that aren't provided. There should be enough to tinker with, though. Also, not shown here but worth noting is the Decision Table/Logic Engine that plugs into this RESM to reduce logic expression and evaluation into a manageable form. I'll post that elsewhere.

The code editor used is C64 Prg Studio.

I'll break it up into chunks with preceding comments.

There are two main sections here. The first shows the RESM. The second shows how an application is defined as a StateChart and Event Handlers.

First Part: Reactive Extended State Machine.
Reactive: Event-driven.
Extended: State Variables.

Variables and Event Handling is encapsulated and recursive. For example, an Event Handler can be defined in the Top State but no other states. During the application's lifetime, an event that occurs in any other state will be passed upwards through its parents until the appropriate handler is found.

The system is Run-To-Completion. With careful design around it, it should handle multiple threads with no problems.

Event ID's are not instances. It is the associated data passed with them that provides usable information.

Some important variables:
ApplicationState always contains the current State.
ActiveState always holds the temporary state for the currently handled event.
EventID holds the type of event only. Instance data is associated with it.
CurrentContext is still under development. Basically, I'm extending it to be contextual so different SMs and their Variables can be mapped into each other with no collision.

Code: Select all

; ----------------------------------------
; Reactive Extended State Machine

; ----------
; ZERO PAGE

; Vectors
zRESM_StateVec             = CompilerIndex_ZPAddr
zRESM_NextStateVec         = zRESM_StateVec + 2
zRESM_StateMapVec          = zRESM_NextStateVec + 2
zRESM_ApplicationState     = zRESM_StateMapVec + 2
zRESM_NextState            = zRESM_ApplicationState + 1
zRESM_ActiveState          = zRESM_NextState + 1
zRESM_EventID              = zRESM_ActiveState + 1
zRESM_CurrentContext       = zRESM_EventID + 1

; Bump CompilerIndex_ZPAddr for the next ZP allocation
CompilerIndex_ZPAddr = zRESM_CurrentContext + 1
; ----------

; Configuration
cRESM_MaxEvents        = 8
cRESM_MaxContexts      = 1

; Constant Indices
ciRESM_ParentID        = 0
ciRESM_EntryAction     = 1
ciRESM_ExitAction      = 3
ciRESM_EventCount      = 5
ciRESM_EventID         = 6

; TODO: Needs to be a queue. Add to top, take from bottom. Circular.
; Use multiples of 8 so it's easy to mask for pointer wrap-around.
; However, STK ensures fast response for related code. Might keep it a while.

TAB_RESM_EventPointer  byte 0 
TAB_RESM_EventStk      bytes cRESM_MaxEvents
TAB_LO_RESM_EventData  bytes cRESM_MaxEvents 
TAB_HI_RESM_EventData  bytes cRESM_MaxEvents 
Note: I use rA, rX and rY to refer to the CPU registers.

SetStateMap uses a (not shown here) memory management framework used to pass references to blocks of memory.

Code: Select all

; rA has HDL for StateMap
RESM_SetStateMap
         ldx #zRESM_StateMapVec
         jmp Block_AddrToVecAX
Start initialises the SM then loops until exit.

Code: Select all

RESM_Start
         ; Initialisation
         jsr RESM_Init

         ; Startup
         lda #0
         jsr RESM_Txn_Entry

         ; Lead event
         lda #EID_Start
         jsr RESM_Event_Raise

         ; Event handling loop
@Loop1   lda #254
         cmp $d012
         bne @Loop1

         inc $d020
         jsr RESM_Event_Assign
         dec $d020

         jsr ReadJoystick
         
         lda zRESM_ApplicationState
         cmp #255
         bne @Loop1
         rts
Init does what it seems. Initialisation.

Code: Select all

RESM_Init
         lda #0
         sta zRESM_ApplicationState
         sta TAB_RESM_EventPointer
         rts
Event_Raise will "raise" an event. Use it by loading rA with a valid EventID then call the subroutine. It sticks the Event and its variables onto a stack (not a queue).

Code: Select all

; rA EventType, rXY Argument Data or Address
RESM_Event_Raise       
         sty @SMC + 1
         ldy TAB_RESM_EventPointer
         sta TAB_RESM_EventStk,Y
         txa
         sta TAB_LO_RESM_EventData,Y
@SMC     lda #0
         sta TAB_HI_RESM_EventData,Y
         inc TAB_RESM_EventPointer
         rts
Event_Assign takes an Event from the Event Stack and tries to find its associated Event Handler in the application's current state or one of its parent states. If no handler is found the event is discarded. I intend to add handling for Event Deferment eventually.

Code: Select all

; Run-To-Completion! Keep the handlers short and don't block.
RESM_Event_Assign
         ; Pull Event from Stack
         ldx TAB_RESM_EventPointer
         beq @Exit

         dex
         stx TAB_RESM_EventPointer

         ; Get next unhandled Event
         lda TAB_RESM_EventStk,X
         sta zRESM_EventID

         ; Set the state Data Base Address
         lda zRESM_ApplicationState
         
@Loop_State 
         sta zRESM_ActiveState   ; This shows from which state an Action or Event was consumed
         jsr RESM_SetStateVector

         ; Seach through the current state's Event Handler list
         ldy #ciRESM_EventCount
         lda (zRESM_StateVec),Y
         sta @EventCount
         
         clc
         adc #ciRESM_EventCount
         tay

         ; Find a match
@Loop_MatchEvent    
         lda (zRESM_StateVec),Y
         cmp zRESM_EventID
         beq @ConsumeEvent
         dey
         cpy #ciRESM_EventCount
         bne @Loop_MatchEvent

         ; Recursive Search
         ldy #ciRESM_ParentID
         lda (zRESM_StateVec),Y
         cmp #255
         bne @Loop_State
@Exit    rts

@ConsumeEvent
         ; Calculate index to the State's designated EventHandler for that EventID
         lda PreCalc_Mul2L_GV - 3,Y ; Aligns with the values 6,8,10,...
         clc
         adc @EventCount
         tay
         
         ; Now at the correct position in the State data
         lda (zRESM_StateVec),Y
         sta @SMC_EventHandler + 1
         iny
         lda (zRESM_StateVec),Y
         sta @SMC_EventHandler + 2

         ; Load rA with EventID, rXY with Event Data
         ldx TAB_RESM_EventPointer ;zRESM_EventID
         ldy TAB_HI_RESM_EventData,X
         lda TAB_LO_RESM_EventData,X
         tax
         lda zRESM_EventID

@SMC_EventHandler
         jmp $FFFF

@EventCount byte 0
The following are internal utility subroutines.

Code: Select all

RESM_SetStateVector 
         asl
         tay
         lda (zRESM_StateMapVec),Y 
         sta zRESM_StateVec
         iny
         lda (zRESM_StateMapVec),Y
         sta zRESM_StateVec + 1
         rts

RESM_SetNextStateVector 
         asl
         tay
         lda (zRESM_StateMapVec),Y 
         sta zRESM_NextStateVec
         iny
         lda (zRESM_StateMapVec),Y
         sta zRESM_NextStateVec + 1
         rts
Transitions are important since there are three types: External, Local and Internal, each of which handle the automatic Entry and Exit actions slightly differently depending on the relationships between source and destination states.

Code: Select all

RESM_Txn_Local sta zRESM_NextState
         jsr RESM_SetNextStateVector

         ; If NextState is not a Child then do ExitAction 
         lda zRESM_ApplicationState

         ldy #ciRESM_ParentID
         cmp (zRESM_NextStateVec),Y
         beq @SkipExit

         ; Do Exit Action
         ldy #ciRESM_ExitAction
         jsr RESM_DoSMCJmp

@SkipExit 
         ; If NextState is not the Parent then do EntryAction
         ldy #ciRESM_ParentID
         lda (zRESM_StateVec),Y
         tay

         ; Enter new state BEFORE calling (or not) its Entry Action
         lda zRESM_NextStateVec
         sta zRESM_StateVec
         lda zRESM_NextStateVec + 1
         sta zRESM_StateVec + 1
         lda zRESM_NextState
         sta zRESM_ApplicationState

         cpy zRESM_ApplicationState 
         beq @SkipEntry

         ; Do Entry Action
         ldy #ciRESM_EntryAction
         jsr RESM_DoSMCJmp

@SkipEntry rts

RESM_Txn_External 
         sta zRESM_NextState

         ; Transition Exit
         lda zRESM_ApplicationState
         jsr RESM_SetStateVector
         ldy #ciRESM_ExitAction
         jsr RESM_DoSMCJmp

         ; Next State

         lda zRESM_NextState
         
         ; Transition Entry
RESM_Txn_Entry 
         sta zRESM_ApplicationState
         jsr RESM_SetStateVector
         ldy #ciRESM_EntryAction
         jmp RESM_DoSMCJmp
This is the cleanup routine that is done when a Kill or Stop type of event is serviced.

Code: Select all

         ; Recurse through Parent States while calling their Exit Actions
RESM_Txn_RecursiveExit 
         lda zRESM_ApplicationState
RESM_Txn_RecursiveExit_E 
         jsr RESM_SetStateVector
         ldy #ciRESM_ExitAction
         jsr RESM_DoSMCJmp

         ldy #ciRESM_ParentID
         lda (zRESM_StateVec),Y
         sta zRESM_ApplicationState
         cmp #255
         bne RESM_Txn_RecursiveExit_E
         rts
An internal routine used to access Event Handlers.

Code: Select all

RESM_DoSMCJmp lda (zRESM_StateVec),Y
         sta @SMC + 1
         iny
         lda (zRESM_StateVec),Y
         sta @SMC + 2

@SMC     jmp $FFFF
PART 2: State and Event Definitions

A statemap needs to be defined. It's a series of tables and pointers. The RESM is given the start address, in this example it's StateMap_1, to work with.

Assign a reference to a chunk of memory. This reference can be passed around to other subroutines which will use it, its meta-data and the memory area. These references are managed by a framework that handles the availability pool, structs, de/serialisation and arrays and lists. For reasons of space I won't show the code for all that in this post.

Code: Select all

; Create Data Block
Create_StateMap_1
         lda #0   ; Length param 
         ldx #<StateMap_1
         ldy #>StateMap_1
         jsr Block_Create
         sta StateMap_1_HDL
         rts
StateMap_1_HDL is where the reference to StateMap_1 is stored.

Code: Select all

; States
StateMap_1_HDL    byte 0

StateMap_1        word SM1_Main, SM1_Game, SM1_WaitToStart

; ------------------------------------------------------------------------------
; State IDs
ciSM1_Main          = 0
ciSM1_Game          = 1
ciSM1_WaitToStart   = 2
; ------------------------------------------------------------------------------
This is the topmost state which is the parent of all the others. It has no parent (255).
A state is structed as follows:
1. byte Parent's StateID (255 = no parent)
2. address Entry Action, address Exit Action
3. byte Count Of Events handled by this state
4. byte Event ID, ... (number of Event IDs = Count Of Events)
5. address Event Handler, ... (number of Event Handlers = Count Of Events, and corresponds to the Event ID above)

Code: Select all

SM1_Main
@ParentID         byte 255 
@EntryExitActions word EA_SM1_Main, XA_SM1_Main 
@EventCount       byte 2
@EventID          byte EID_Start, EID_Stop 
@EventHandler     word EH_Start,  EH_Stop 

SM1_Game
@ParentID         byte ciSM1_Main
@EntryExitActions word EA_SM1_Game, XA_SM1_Game
@EventCount       byte 2
@EventID          byte EID_BallHit, EID_Joystick   
@EventHandler     word EH_BallHit, EH_Joystick_InGame 

SM1_WaitToStart
@ParentID         byte ciSM1_Main
@EntryExitActions word EA_SM1_WaitToStart, XA_Null
@EventCount       byte 1
@EventID          byte EID_Joystick   
@EventHandler     word EH_Joystick_InWait 
Statically defined State Variables. The colours are arrayed for three different contexts. Default context is 0.

Code: Select all

; State Variables
SM1_Main_BdrColour  byte Color_LtG, Color_Yel, Color_LtR
SM1_Main_BgdColour  byte Color_Blk, Color_Gr1, Color_Blu

SM1_Main_HiScore  byte 0
SM1_Game_Score    byte 0
SM1_Game_Lives    byte 0
Note that although these EventIDs are unique, they are used only to express the TYPE of event, not a concrete instance. For example, a KeyPress event would carry in its associated variables defining information such as the keycode and shift type.

Code: Select all

; ------------------------------------------------------------------------------
; Events IDs
EID_Null          = 0
EID_Start         = 1
EID_Stop          = 2
EID_Joystick      = 3
EID_BallHit       = 4
; ------------------------------------------------------------------------------
Event Handlers are self-explanatory. A subroutine whose address lies in a State's @EventHandler table.
The code in the handler can do anything - trigger transitions, raise other events, read and write State Variables.

Some of the example code in here shows inline parameters. Yep, the code is not provided, so just assume the inline Print works as implied.

The default Start routine prints an introductory message then triggers a local transition to one of the child states.

In the Wait handler, the JoyStick event has pushed the Fire and Direction information into the CPU registers, hence the cpx upon entry.

Code: Select all

; Event Handlers
EH_Start
         jsr i_QPrint
         byte 0,0,Color_Yel
         null '----- State/Event Test -----'

         ; New State
         lda #ciSM1_WaitToStart
         jmp RESM_Txn_Local

EH_Stop  jmp RESM_Txn_RecursiveExit

EH_Joystick_InWait
         ; Guard Condition
         ; Initiate an External Transition to the Game State
         cpx #cJoystick_Fire
         bne @Exit
         lda #ciSM1_Game
         jsr RESM_Txn_External
@Exit    rts

EH_Joystick_InGame
         ; Guard Condition
         ; Initiate an External Transition to the Game State
         cpx #cJoystick_Left
         bne @Cont

@Cont    cpx #cJoystick_Right
         bne @Exit

@Exit    rts

EH_BallHit 
         rts
Entry and Exit Actions are executed whenever a state is, respectively, entered or exited.
For example, when a new game screen state is entered, an Entry Action would clear the screen and print an introduction to the level. It's worth pointing out that these non-traditional UML-style Extended States avoid the potential messy explosion of events, states and variables. They're also fast, sparsely defined and can significantly reduce the amount of code otherwise needed.

Code: Select all

; ----------------------------------------
; Entry Actions
EA_Null  rts

EA_SM1_Main
         jsr ScreenClear
         lda SM1_Main_BdrColour
         sta $D020
         lda SM1_Main_BgdColour
         sta $D021
         lda #0
         sta SM1_Main_HiScore
         rts

EA_SM1_WaitToStart
         jsr i_QPrint
         byte 5,10,Color_Wht
         null '*** PRESS FIRE TO BEGIN ***'
         rts

EA_SM1_Game
         lda #3
         sta SM1_Game_Lives
         lda #0
         sta SM1_Game_Score

         ; Draw Game Screen
         ; ...
         rts

; ----------------------------------------
; Exit Actions
XA_Null  rts

XA_SM1_Main rts

XA_SM1_Game rts

XA_SM1_WaitToStart rts
One major omission here is automatic handling of transitions between non-neighbouring states. The code to find the Least Common Ancestor and to walk the tree in the correct order is simple, but can be a big hit to the CPU due to the dynamic search.