Transcript Ch. 6 Pointers and Data Structures

Ch. 6 Pointers and Data
Structures
From the text by Valvano:
Introduction to Embedded Systems:
Interfacing to the Freescale 9S12
Objectives
• Implement pointers using indexed addressing
modes
• Use pointers to access arrays, strings,
structures, tables, and matrices
• Present finite-state machines as an abstractive
design methodology
• Describe how the paged memory system allows
memory sizes above 64KiB
• Present minimally intrusive methods for
functional debugging
6.1 Indexed Addressing Modes
Used to Implement Pointers
• 9S12 has 15 addressing modes.
• 9 are related to pointers.
• Assembly—pointers are implemented
using indexed addressing.
• The address is placed into RegisterX or
RegisterY, then the data is accessed using
indexed addressing mode.
Figure 6.2, page 193
• Pointers—PT, SP, GetPt, PutPt
• Arrows show the memory location to
which they point.
• Shaded regions represent data.
• Array or string —simple structure with
multiple, equal-sized elements—the
pointer points to the first element then the
indexed addressing mode is used to
access the rest of the structure.
Figure 6.2 (cont.)
• The Stack —SP points to the top element
of the stack.
• Linked List – contains some data
elements that are pointers.
• FIFO Queue – important for I/O
programming.
6.1.1 Indexed Addressing Mode
• Uses a fixed offset with the 16-bit registers (X, Y,
SP, and PC).
• The offsets that are possible include:
– 5-bits (-16 to +15)
– 9-bits (-256 to + 127)
– 16- bits
• Example of 5 bit indexing: (5C is index mode
operand—1 byte)
–
–
–
–
$6A5C staa -4,Y ; [Y-4] = Reg A
Assume RegA is $56, RegY is $0823
$0823 -4 = $081F
See Figure 6.3
More Examples of Indexed
Addressing Mode
• Example of 9-bit indexed mode requires 2
bytes to encode the operand:
– $6AE840
staa $40,Y ; [Y+$40] = Reg A
– See Figure 6.4 (note: $40 + $8023 = $8063)
• Example of 16-bit indexed mode requires
3 bytes to encode the operand:
– $6AEA2000 staa $200,Y ; [Y + $200] =RegA
– See Figure 6.5 (note: $200 + $0823=$0A23)
6.1.2 Auto Pre/Post Decrement/Increment
Indexed Addressing Mode
• The 16-bit pointers are used (X, Y, SP).
• These pointers are modified either before
(PRE) or after (POST) the access of the
memory.
• Used for accessing memory sequentially.
• Example: Post-increment addressing.
– Staa 1,Y+ ; Store a copy of value in Reg A at
2345, then Reg Y = 2346.
– More examples on the bottom of page 195.
Other Addressing Modes
• 6.1.3 Accumulator-Offset Indexed
Addressing mode—Accumulator A,B, or D are
used with registers X, Y, SP, and PC.
– Example: staa B,Y
– Efficient for accessing arrays.
• 6.1.4 Indexed-Indirect Addressing Mode
– A fixed offset of 16 bits is used (X, Y, SP or PC).
– A second address is fetched; the load or store is
operated on the second address.
– Useful when data structures include pointers (pg.
196).
And More Addressing Modes
• 6.1.5 Accumulator D Offset Indexed-Indirect
Addressing Mode.
– Also useful when data structures includes pointers.
– Offset is in D and is added to X, Y, SP, or PC.
• 6.1.6 Post-Byte machine Coded for Indexed
Addressing
• 6.1.7 Load Effective Address Instructions
• 6.1.8 Call-By-Reference Parameter Passing
6.2 Arrays
• Random Access
– Read and write data in any order.
– Allowed for all indexed data structures.
– An indexed data structure has elements of the
same size—it is accessed knowing the name
of the structure, the size of the elements and
the number of elements.
6.2 (cont.)
• Sequential access
– The elements are read and written in order.
– Examples: strings, linked lists, stacks,
queues, and trees.
• Arrays
– Made of elements of equal precision and
allows random access.
– Length is the number of elements.
– Origin is the index of the first element.
Example 6.1
• Write a stepper module to control the read/write
head of an audio tape recorder.
– Three public functions
• Initialization
• Rotate one step clockwise
• Rotate one step counterclockwise
– Stepper motor has four digital control lines
• To make it spin, output 5, 6, 10, and 9 over and over.
• To make it spin in the opposite direction, output the values in
reverse order.
• Figure 6.9 illustrates the byte array.
• Program 6.1 shows the code (fcb means form constant byte)
Example 6.2
• Design an exponential function y=10x, with
a 16-bit output.
– X is an input from 0 to 4.
– Figure 6.10 illustrates a word array
– Program 6.2 (page 201) illustrates the use of
the array (fdb means form double byte and is
used to define word constants.)
Termination Codes
• Termination codes can be used to handle
variable length.
• Table 6.3 illustrates typical termination
codes.
• Program 6.3 illustrates the use of the null
termination code.
• Program 6.4 illustrates a pointer method to
access the array.
6.3 Strings
• A data structure with equal-sized elements
that are only accessed sequentially.
• The length of the string is stored in the first
position, when data can take on any value;
thus termination codes are not needed.
Example 6.3
• Example 6.3 (page 203)
– Write software to output a sequence of
values to a digital to analog converter.
– The length is stored in the first byte:
• Data1
•
• Data2
•
fcb
fcb
fcb
fcb
4
;length
0,50,100,50 ;data
8
0,25,50,75,100,75,50,25
Example 6.3 (cont.)
• The DAC is connected to Port T.
• The function (subroutine) DAC outputs the string
data to the digital to analog converter.
– DAC ldab 0,x
;length
– loop
inx
;next element
–
ldaa 0,x ;data
–
staa PTT ;out to the dig/analog conv
–
decb
–
bne loop
–
rts
Example 6.3 (cont.)
• main
•
• mloop
•
•
•
lds
#$4000
movb #$FF, DDRT
ldx
#Data1 ;first string
bsr
DAC
ldx
#Data2 ;second string
bra
mloop
Example 6.4
• Write software to output a ASCII string to
the serial port.
• Call by reference parameter passing is
used—a pointer to the string will be
passed.
• See Program 6.6, page 204.
6.4 Matrices
• Two dimensional data structure accessed
by rows and columns.
• Figure 6.11 illustrates “row major” and
“column major”.
• Program 6.8 illustrates a function to
access a two by three column-major
matrix. (page 205)
Example 6.5
• Develop a set of driver functions to
manipulate a 32 by 12 graphics display.
• Bit arrays are used to store pixel values.
• 0 represents a blank, 1 turns on a pixel.
• Program 6.11, 6.12 and 6.13 illustrate the
access, modification, and reading of the bit
matrix.
Structures
• A structure has elements with different
types and/or precisions.
• Program 6.14 is an assembly language
example of a structure.
Tables
• A table is a collection of identically sized
structures.
• Fig. 6.14 shows a table made up of a
simple data base.
• Program 6.16 (page 211)
Trees
• A graph is a general linked structure
without limitations.
6.8 Finite-State Machines with
Statically Allocated Linked
Structures
• 6.8.1 Abstraction
– Allows the definition of complex problems
using basic abstract building blocks.
– Finite-State-Machine is a basic abstraction.
Finite State Machines
• Execution of a Moore FSM
– 1. Perform output, which depends on the
current state.
– 2. Wait a prescribed amount of time (optional)
– 3. Input
– 4. Go to next state, which depends on the
input and the current state.
Finite State Machines (cont.)
• Mealy FSM
– 1. Wait a prescribed amount of time (optional)
– 2. Input
– 3. Perform output, which depends on the input
and the current state
– 4. Go to next state, which depends on the
input and the current state
Finite State Machines (cont.)
• Sequence should be documented before
state graph is drawn.
• States are drawn as circles
• Arrows are drawn from one state to
another (with the input causing the
transition).
Linked-Structure of Nodes
• Each node defines one state.
• One or more of the entries in the node is a
pointer (or link).
• Embedded systems usually have statically
allocated fixed-size linked structures.
• In simple embedded systems, the state
graph is fixed and stored in nonvolatile
memory.
6.8.2 Moore FSMs
• Outputs are only a function of current
state.
– Example 6.6 Traffic Light Problem
6.8.3 Mealy Finite-State Machines
• Outputs depend on both the input and the
current state.
• Arrows specify both output and next state.
• Used when the output is needed to cause
the state to change.
• Example 6.7 Four-Legged Trotting Robot.
6.8.4 Functional Abstraction Within
FSMs
• Input is obtained by calling a function.
• Output process involves calling a function.
• Function calls adds a layer of abstraction
between the FSM and the I/O at the ports.
• Example 6.8—Vending Machine
• Example 6.9—Robot that Sits, stands, and
lies down.
6.9 Dynamically Allocated
Structures
• Dynamic Memory Allocation is used to reuse
memory and provide for efficient use of RAM.
• Fixed allocation used in previous examples (size
of data structures is specified in the assembly
code).
• With dynamic allocation, the size and location of
the data structures is determined at run time (not
assembly time).
• Heap—a chunk of RAM that is
– 1. Dynamically allocated by the program
– 2. Used by the program to store information
– 3. Dynamically released by the program when
the structure is no longer needed.
• Implementation of dynamic allocation
requires the management of a heap.
6.9.1 Fixed-Block Memory
Manager
• Figure 6.27
– Initial state of the heap has all of the free blocks
linked in a list.
• Program 6.28
– Shows the global structures for the heap, defined in
RAM.
– SIZE—number of 8-bit bytes in each block.
– NUM—number of blocks to be managed.
– FreePt--points to the first free block.
• Program 6.29
– Software that that partitions the heap into blocks and
links them together.