EE 319K�Introduction to Embedded Systems

Lecture 7:�Data structures, �Finite state machines

Bard, Gerstlauer, Cuevas, Holt, Telang, Tiwari, Valvano, Yerraballi

Read Chapter 5 book, ebook Chapter 10

https://www.youtube.com/playlist?list=PLyg2vmIzGxXEle4_R2VA_J5uwTWktdWTu

7-1

Agenda

• Recap
• Indexed Addressing and Pointers
• In C: Address of (&), Pointer to (*)
• Data Structures: Arrays, Strings
• Functional Debugging
• Outline
• Heap on the TM4C123
• Use struct to create Data structures
• Finite State Machines, Linked data structures
• Traffic Light Example

Bard, Gerstlauer, Cuevas, Holt, Telang, Tiwari, Valvano, Yerraballi

EE319H

7-2

Data Structures

• Pointers are the basis for data structures

Organization of data

Functions to facilitate access

{

Abstract data type

​

Bard, Erez, Gerstlauer, Holt, Valvano, Yerraballi, Telang, Cuevas, Tiwari

http://users.ece.utexas.edu/%7Evalvano/arm/Heap_4C123.zip

EE319H

7-3

Pointer Review

• In assembly

p SPACE 4

Num1 SPACE 1

Num2 SPACE 1

Set1

LDR R0,=p ;=> p

LDR R1,=Num1 ;=> Num1

STR R1,[R0]

BX LR

Read

LDR R0,=p ;=> p

LDR R1,[R0] ;=>Num1 or Num2

LDRB R0,[R1]

BX LR

Bard, Erez, Gerstlauer, Holt, Valvano, Yerraballi, Telang, Cuevas, Tiwari

• Pointer steps
• Definition
• Initialization
• Deference

uint8_t Num1,Num2;

uint8_t *p;

void Set1(void){

p = &Num1;

}

void Set2(void){

p = &Num2;

}

uint8_t Read(void){

return *p;

}

{

{

7-4

Array Access with Pointers

• In assembly

p RN 3

sum RN 0

Sum7Primes

MOV sum,#0 ;sum = 0

LDR p,=Prime ;p = Prime

ADD R1,p,#14 ;&Prime[7]

lp LDRH R2,[p] ;*p

ADD sum,sum,R2 ;sum += ..

ADD p,p,#2 ;p++

CMP p,R1

BNE lp

BX LR

Bard, Erez, Gerstlauer, Holt, Valvano, Yerraballi, Telang, Cuevas, Tiwari

• Pointer steps
• Definition
• Initialization
• Deference

const uint16_t Prime[] = {1,2,3,5,7,11,13};

uint16_t Sum7Primes(void){

uint32_t sum;

const uint16_t *p;

sum = 0;

p = Prime;

do{

sum += *p;

p++;

}

while(p != &Prime[7]);

return sum;

}

7-5

Abstraction

• Software abstraction
• Define a problem with a minimal set of basic, abstract principles / concepts
• Separation of concerns via interface/policy mechanisms
• Straightforward, mechanical path to implementation

​

• Three advantages of abstraction are
1. it can be faster to develop
2. it is easier to debug (prove correct) and
3. it is easier to change

Bard, Gerstlauer, Cuevas, Holt, Telang, Tiwari, Valvano, Yerraballi

7-6

Finite State Machine (FSM) *

• What is a finite state machine?
• Inputs (sensors)
• Outputs (actuators)
• Controller
• State graph ↔ State table

Bard, Gerstlauer, Cuevas, Holt, Telang, Tiwari, Valvano, Yerraballi

7-7

Finite State Machine (FSM)

• Finite State Machines (FSMs)
• Set of inputs, outputs, states and transitions
• State graph defines input/output relationship
• What is a state?
• Description of current conditions
• What is a state graph?
• Graphical interconnection between states
• What is a controller?
• Software that inputs, outputs, changes state
• Accesses the state graph

Bard, Gerstlauer, Cuevas, Holt, Telang, Tiwari, Valvano, Yerraballi

https://www.youtube.com/playlist?list=PLyg2vmIzGxXEle4_R2VA_J5uwTWktdWTu

What I know

What I believe

7-8

Structures

Bard, Gerstlauer, Cuevas, Holt, Telang, Tiwari, Valvano, Yerraballi

struct player{

uint8_t Xpos; // first element

uint8_t Ypos; // second element

uint16_t LifePoints; // third element

};

typedef struct player player_t;

player_t Sprite;

int main(void){

Sprite.Xpos = 10;

Sprite.Ypos = 20;

Sprite.LifePoints = 12000;

A structure collects elements of different sizes and/or types into one object.

7-9

Structures

Bard, Gerstlauer, Cuevas, Holt, Telang, Tiwari, Valvano, Yerraballi

; Input: R0 points to a player_t

Xpos EQU 0

Ypos EQU 1

LifePoints EQU 2

MoveCenter MOV R1,#50

STRB R1,[R0,#Xpos]

STRB R1,[R0,#Ypos]

LDRH R1,[R0,#LifePoints]

LDR R2,=65535

CMP R1,R2 ;at max?

BHS skip

ADD R1,#1 ;more life

STRH R1,[R0,#LifePoints]

skip BX LR

// move to center and add life

void MoveCenter(player_t *pt){

pt->Xpos = 50;

pt->Ypos = 50;

if(pt->LifePoints < 65535){

pt->LifePoints++;

}

}

50

50

12001

7-10

Finite State Machine (FSM)

• Moore FSM
• output value depends only on the current state,
• inputs affect the state transitions
• significance is being in a state
• Input: when to change state
• Output: definition of being in that state

Bard, Gerstlauer, Cuevas, Holt, Telang, Tiwari, Valvano, Yerraballi

7-11

Finite State Machine (FSM)

• Moore FSM Execution Sequence
1. Perform output corresponding to the current state
2. Wait a prescribed amount of time (optional)
3. Read inputs
4. Change state, which depends on the input and the current state
5. Go back to 1. and repeat

​

Bard, Gerstlauer, Cuevas, Holt, Telang, Tiwari, Valvano, Yerraballi

7-12

Finite State Machine (FSM)

Bard, Gerstlauer, Cuevas, Holt, Telang, Tiwari, Valvano, Yerraballi

• Use Moore when the output is needed to be IN the state
• Use Mealy when the output is needed to CHANGE the state

7-13

FSM Implementation

• Data Structure embodies the FSM
• multiple identically-structured nodes
• statically-allocated fixed-size linked structures
• one-to-one mapping FSM state graph and software linked structure
• one structure for each state
• Linked Structure
• pointer (or link) to other nodes (define next states)
• Table structure
• indices to other nodes (define next states)

Bard, Gerstlauer, Cuevas, Holt, Telang, Tiwari, Valvano, Yerraballi

7-14

Traffic Light FSM

Bard, Gerstlauer, Cuevas, Holt, Telang, Tiwari, Valvano, Yerraballi

PE1=0, PE0=0 means no cars exist on either road

PE1=0, PE0=1 means there are cars on the East road

PE1=1, PE0=0 means there are cars on the North road

PE1=1, PE0=1 means there are cars on both roads

​

goN, PB5-0 = 100001 makes it green on North and red on East

waitN, PB5-0 = 100010 makes it yellow on North and red on East

goE, PB5-0 = 001100 makes it red on North and green on East

waitE, PB5-0 = 010100 makes it red on North and yellow on East

​

• Use Moore when the output is needed to be IN the state

7-15

STT ⬄ STG (EE319K)

Bard, Gerstlauer, Cuevas, Holt, Telang, Tiwari, Valvano, Yerraballi

struct State {

uint32_t Out;

uint32_t Time;

uint32_t Next[4];};

typedef const struct State State_t;

7-16

STT ⬄ STG (EE319H)

Bard, Gerstlauer, Cuevas, Holt, Telang, Tiwari, Valvano, Yerraballi

struct State {

uint32_t Out;

uint32_t Time;

const struct State *Next[4];};

typedef const struct State State_t;

7-17

STT ⬄ C (EE319K)

Bard, Gerstlauer, Cuevas, Holt, Telang, Tiwari, Valvano, Yerraballi

#define goN 0

#define waitN 1

#define goE 2

#define waitE 3

State_t FSM[4]={

{0x21,3000,{goN,waitN,goN,waitN}},

{0x22, 500,{goE,goE,goE,goE}},

{0x0C,3000,{goE,goE,waitE,waitE}},

{0x14, 500,{goN,goN,goN,goN}}};

7-18

STT ⬄ C (EE319H)

Bard, Gerstlauer, Cuevas, Holt, Telang, Tiwari, Valvano, Yerraballi

#define goN &FSM[0]

#define waitN &FSM[1]

#define goE &FSM[2]

#define waitE &FSM[3]

State_t FSM[4]={

{0x21,3000,{goN,waitN,goN,waitN}},

{0x22, 500,{goE,goE,goE,goE}},

{0x0C,3000,{goE,goE,waitE,waitE}},

{0x14, 500,{goN,goN,goN,goN}}};

7-19

FSM Engine in C (EE319K)

Bard, Gerstlauer, Cuevas, Holt, Telang, Tiwari, Valvano, Yerraballi

uint32_t S; // index to the current state

uint32_t Input;

int main(void){

PLL_Init(); // 80 MHz, Program 10.1

SysTick_Init(); // Program 10.2

// GPIO initialization

S = goN;

while(1){

GPIO_PORTB_DATA_R = FSM[S].Out; // set lights

SysTick_Wait10ms(FSM[S].Time);

Input = GPIO_PORTE_DATA_R&0x03; // read sensors

S = FSM[S].Next[Input];

}

}

7-20

FSM Engine in C (EE319H)

Bard, Gerstlauer, Cuevas, Holt, Telang, Tiwari, Valvano, Yerraballi

State_t *Pt; // state pointer

uint32_t Input;

int main(void){

PLL_Init(); // 80 MHz, Prog 4.6

SysTick_Init(); // Program 4.2.1

// GPIO initialization

Pt = goN;

while(1){

GPIO_PORTB_DATA_R = Pt->Out; // set lights

SysTick_Wait10ms(Pt->Time);

Input = GPIO_PORTE_DATA_R&0x03; // read sensors

Pt = Pt->Next[Input];

}

}

7-21

Next time: Lab 3 with FSM

PE1 is input

PE2 is output

Touch and release cycles

10% is 50,450ms

30% is 150,350ms

50% is 250,250ms

70% is 350,150ms

90% is 450,50ms

​

Start with 50% duty cycle

Bard, Gerstlauer, Cuevas, Holt, Valvano, Yerraballi

High

1

250ms

Low

0

250ms

0

0

What does this do?

7-22