ARM汇编代写代做代考 FLOW CONTROL

程序代写 CS代考 / Algorithm算法代写代考, ARM汇编代写代考, c++代做, Java代写代考

FLOW CONTROL
Program Flow Control
• BY DEFAULT, the program counter is incremented by 4 when each instruction is executed (PC = PC + 4)
• next sequential instruction is then fetched, decoded and executed
• need to be able alter this sequential program flow in order to write more useful
programs
• normally a condition is tested and a decision made whether to execute
 the next sequential instruction OR  an instruction at a different address
• need to learn about condition code flags and branch instructions CS1021 © 2018 jones@scss.tcd.ie School of Computer Science and Statistics, Trinity College Dublin 9-Oct-18
1

FLOW CONTROL
Condition Code Flags
• CPU contains a Current Program Status Register (CPSR) containing 4 condition code flags
32 bits
4 20 8
Current Program Status Register (CPSR)
• the 4 flags can optionally reflect the result of an instruction (eg ADD, SUB)
N – negative N = MSB(result)
Z – zero Z = 1 if result == 0, Z = 0 if result != 0
N
Z
C
V
RESERVED
Control bits
C – carry
V – overflow
will discuss carry and overflow later
CS1021 © 2018 jones@scss.tcd.ie School of Computer Science and Statistics, Trinity College Dublin 9-Oct-18
2

FLOW CONTROL
Condition Code Flags
• the condition code flags are updated if the S bit, encoded in the machine code of the instruction, is set
32 bits 4214144 12
• at the assembly language level, an “S” is appended to the instruction mnemonic (eg. ADDS, SUBS, MOVS) to indicate that the instruction should update the condition code flags when executed
condition
0
0
I
opcode
S
Rn
Rd
OPERAND-2
CS1021 © 2018 jones@scss.tcd.ie School of Computer Science and Statistics, Trinity College Dublin 9-Oct-18
3

FLOW CONTROL
CMP Instruction
• the CMP instruction subtracts its operands (like a subtract instruction) and sets the condition code flags without storing the result
CMP R1, #3 ; set condition code flags to reflect result of R1 – 3
• the resulting condition codes allows the CPU to branch if the CMP operands were equal, not equal, less than, less than or equal, greater than or equal OR greater than each other (=, !=, <, <=, >=, >)
• since CMP always sets the condition code flags, here is no need for a CMPS mnemonic
CS1021 © 2018 jones@scss.tcd.ie School of Computer Science and Statistics, Trinity College Dublin 9-Oct-18
4

FLOW CONTROL
Branch Instructions (Bxx)
• BY DEFAULT, the CPU increments the PC by 4 (the size of one instruction) to “point to” the next sequential instruction in memory
• a branch instruction can modify the PC thus breaking the pattern of sequential execution
• Bxx L ; xx = condition
• branch instructions EITHER
1. unconditional OR
 always branches 2. conditional
 branches if condition TRUE
 executes next sequential instruction if condition FALSE  condition based on condition code flags
CS1021 © 2018 jones@scss.tcd.ie School of Computer Science and Statistics, Trinity College Dublin 9-Oct-18
5

FLOW CONTROL
Conditional Branch Instructions
Description
Symbol
C/C++/Java
Instruction
Mnemonic
Branch equal or not equal
equal
=
==
BEQ
EQual
not equal
≠
!=
BNE
Not Equal
unsigned branches
less than
< < BLO (or BCC) LOwer less than or equal ≤ <= BLS Lower or Same greater than or equal ≥ >=
BHS (or BCS)
Higher or Same
greater than
>
>
BHI
HIgher
signed branches
less than
< < BLT Less Than less than or equal ≤ <= BLE Less than or Equal greater than or equal ≥ >=
BGE
Greater than or Equal
greater than
>
>
BGT
Greater Than
branch on flags
Negative Set
BMI
MInus
Negative Clear
BPL
PLus
Carry Set
BCS (or BHS)
Carry Set
Carry Clear
BCC (or BLO)
Carry Clear
Overflow Set
BVS
oVerflow Set
Overflow Clear
BVC
oVerflow Clear
Zero Set
BEQ
EQual
Zero Clear
BNE
Not Equal
CS1021 © 2018 jones@scss.tcd.ie School of Computer Science and Statistics, Trinity College Dublin 9-Oct-18
6

FLOW CONTROL
Conditional Branch Instructions
• need signed and unsigned branches
 depends on whether CMP operands are being interpreted as signed or unsigned integers
• there also branch instructions that directly test the condition flags N, Z, C and V
CS1021 © 2018 jones@scss.tcd.ie School of Computer Science and Statistics, Trinity College Dublin 9-Oct-18
7

FLOW CONTROL
Using branch instructions in Assembly Language • example
B L1
… L1 …
CMP R0, #42 BEQ L2
…
L2 …
; unconditional branch to L1
; set condition code flags ; conditional branch to L2
• labels start in column 1 (otherwise column 1 should be empty except for comments)
• labels must NOT begin with a digit (0..9)
• labels can contain UPPER and lower case letters, digits and _ (underscore)
• labels are case sensitive (mylabel is not the same as MyLabel)
8
• labels must be unique within an assembly language file CS1021 © 2018 jones@scss.tcd.ie School of Computer Science and Statistics, Trinity College Dublin 9-Oct-18

FLOW CONTROL
Compute the absolute value
• write assembly language instructions to compute the absolute value of the signed integer stored in register R1
• algorithm expressed in pseudo-code and as a flowchart if (v < 0) v = -v; • flowchart has a diamond shaped decision boxes with No and Yes exit points • statement v = -v is conditionally executed (if v < 0) • flowcharts considered old-fashioned by some, but they are a good way of illustrating how an algorithm works N Y v < 0? if (v < 0) { // brackets NOT necessary v=-v; //inthiscasesincev=-v; } // is a single statement CS1021 © 2018 jones@scss.tcd.ie School of Computer Science and Statistics, Trinity College Dublin 9-Oct-18 9 v = -v flowchart FLOW CONTROL Compute the absolute value ... • -v computed by calculating 0 - v CMP R1, #0 BGE L1 RSB R1, R1, #0 L1 ... ; v < 0 ? ; >= (opposite condition to < in pseudo code) ; v = 0 - v • note the use of RSB (reverse subtract) • signed branch since v is a signed integer • RSB executed if v < 0 CS1021 © 2018 jones@scss.tcd.ie School of Computer Science and Statistics, Trinity College Dublin 9-Oct-18 10 FLOW CONTROL Compute the maximum of 3 values • write assembly language instructions to compute the maximum value of 3 signed integers a, b and c • algorithm expressed in pseudo-code and as a flowchart max = a; if (b > max)
max = b; if (c > max)
max = c
• statements max = b and max = c are conditionally executed depending on the values of a, b and c
N
Y
N
Y
b > max?
CS1021 © 2018 jones@scss.tcd.ie School of Computer Science and Statistics, Trinity College Dublin 9-Oct-18
11
max = a
max = b
c > max?
max = c
flowchart

FLOW CONTROL
Compute the maximum of 3 values …
• assume the maximum value stored in R0
• assume the 3 variables a, b and c are stored in R1, R2 and R3 respectively
MOV R0, R1 CMP R2, R0 BLE L1 MOV R0, R2
; max = a
; b > max ?
; <= (opposite condition to > in pseudo code) ; max = b
; c < max ? ; <= (opposite condition to > in pseudo code) ; max = c
L1 CMP
BLE L2
MOV R0, R3 L2 …
R3, R0
• signed branches as a, b and c are signed integers CS1021 © 2018 jones@scss.tcd.ie School of Computer Science and Statistics, Trinity College Dublin 9-Oct-18
12

FLOW CONTROL
Compute n!
• write assembly language instructions to compute n factorial
• algorithm expressed in pseudo-code and as a flowchart
n = 6;
r = 1;
while (n > 1) {
r = r * n;
n = n – 1; }
• n is modified by algorithm
• value of r each time around loop
r = 1, r = 1*6, r=1*6*5, r = 1*6*5*4, r = 1*6*5*4*3, r = 1*6*5*4*3*2
• r = 720 = 6!
CS1021 © 2018 jones@scss.tcd.ie School of Computer Science and Statistics, Trinity College Dublin 9-Oct-18
N
Y
n=6 r=1
n > 1?
r = r*n n=n-1
13

FLOW CONTROL
Compute n! …
• result in R0 and n in R1
MOV R1, #6 MOV R0, #1
; n = 6 ; r = 1
; n > 1 ?
; <= (opposite condition to > in pseudo code) ; r = r*n
; n = n – 1
; repeat
L1 CMP
BLS L2
MUL R0, R1, R0 SUB R1, R1, #1 B L1
R1, #1
L2 …
• unsigned branch (a signed branch would work equally well here)
CS1021 © 2018 jones@scss.tcd.ie School of Computer Science and Statistics, Trinity College Dublin 9-Oct-18
14

FLOW CONTROL
Compute the nth Fibonacci Number
• write an assembly language program to compute the nth Fibonacci number Fn
• the nth Fibonacci number is defined recursively as follows
Fn = Fn-1 + Fn-2 where F0 = 0 and F1 = 1 • 0,1,1,2,3,5,8,…
edges case
n <= 0? n such that result > 232 – 1 ? n such that result > 231 – 1 ?
which applies depends on whether integers are interpreted as being signed or unsigned
n = 6;
fa = 0;
fb = 1;
while (n > 1) {
tmp = fb; fb = fa + fb; fa = tmp;
n = n – 1;
pseudo code
}
CS1021 © 2018 jones@scss.tcd.ie School of Computer Science and Statistics, Trinity College Dublin 9-Oct-18
15

FLOW CONTROL
Compute the nth Fibonacci Number …
• store result and fb in R0, fa in R1, n in R2 and tmp in R3
MOV R2, #6 MOV R1, #0 MOV R0, #1
; n =6 ; fa = 0 ;fb=1
; n >1 ?
; <= (opposite condition to > in pseudo code) ;tmp=fa
; fb = fb + fa
; fa = tmp
; n =n – 1
; repeat
L0 CMP
BLE L1
MOV R3, R0 ADD R0, R0, R1 MOV R1, R3 SUB R2, R2, #1 B L0
R2, #1
L1 …
• signed branch (BLE branch less than or equal)
• unsigned branch BLS (branch lower or same) would also work here CS1021 © 2018 jones@scss.tcd.ie School of Computer Science and Statistics, Trinity College Dublin 9-Oct-18
16

FLOW CONTROL
IF … THEN … ELSE
if (x < 9) { x = x + 1; // assume x in R1 // execute if condition TRUE // execute if condition FALSE ; x < 9? ; >= (opposite condition to < in pseudo-code) ; x = x + 1 ; skip else ; x = 0 } else { x = 0; } CMP BGE ADD B R1, #9 L1 R1, R1, #1 L2 R1, #0 L1 MOV L2 ... • signed branches (assume x is a signed integer) • must remember to skip ELSE part if condition TRUE CS1021 © 2018 jones@scss.tcd.ie School of Computer Science and Statistics, Trinity College Dublin 9-Oct-18 17 FLOW CONTROL Conditional AND if ((x > 40) && (x < 50)) { y = y + 1; } else { z = z + 1; } // && (AND) // s0 // s1 • if both comparisons TRUE then execute s0 else execute s1 • comparisons made in order, left to right • called “conditional AND” since second comparison doesn’t need to be made if first comparison FALSE • if both comparisons TRUE, execute s0 and branch to end of construct (skip s1) • if either comparison FALSE, execute s1 CS1021 © 2018 jones@scss.tcd.ie School of Computer Science and Statistics, Trinity College Dublin 9-Oct-18 18 FLOW CONTROL Conditional AND ... • x in R1, y in R2 and z in R3 CMP R1, #40 BLE L1 CMP R1, #50 BGE L1 ADD R2, R2, #1 B L2 • R3, R3, #1 signed branches (assume x is a signed integer) L1 ADD L2 ; if x > 40 ; goto L1 ; if x < 50 ; goto L1 ; y = y + 1 ; goto L2 ; z = z + 1 (opposite condition to pseudo-code) (opposite condition to pseudo-code) (s0 executed if condition TRUE) (skip else statement) (s1 executed if condition FALSE) CS1021 © 2018 jones@scss.tcd.ie School of Computer Science and Statistics, Trinity College Dublin 9-Oct-18 19 FLOW CONTROL Conditional OR if ((x == 40) || (x == 50)) { y = y + 1; } else { z = z + 1; } // || (OR) // s0 // s1 • if either comparison TRUE then execute s0 else execute s1 • comparisons made in order, left to right • called “conditional OR” since second comparison doesn’t need to made if first one is TRUE • assume x in R1, y in R2 and z in R3 CS1021 © 2018 jones@scss.tcd.ie School of Computer Science and Statistics, Trinity College Dublin 9-Oct-18 20 FLOW CONTROL Conditional OR ... CMP R1, #40 BEQ L1 CMP R1, #50 BNE L2 L2 ADD L3 ; if x == 40 ; goto L1 ; if x == 50 ; goto L1 ; y = y + 1 ; goto L3 ; z = z + 1 (opposite condition to pseudo code) (s0 executed if condition TRUE) (skip s1) (s1 executed if condition FALSE) L1 ADD B L3 • one way to generate code R2, R2, #1 R3, R3, #1 CS1021 © 2018 jones@scss.tcd.ie School of Computer Science and Statistics, Trinity College Dublin 9-Oct-18 21 FLOW CONTROL More on the Condition Code Flags • 4 condition code flags N, Z, C and V • Negative (N) – set if MSB(result) == 1 • Zero (Z) – set if result == 0 • Carry (C) • Overflow (V) discuss in more detail now CS1021 © 2018 jones@scss.tcd.ie School of Computer Science and Statistics, Trinity College Dublin 9-Oct-18 22 FLOW CONTROL CARRY Flag on Addition • what happens if two 8 bit unsigned integers are added and the result is too large to fit in 8 bits? • adding two 8 bit unsigned integers can produce a 9 bit result • extra bit stored in the CARRY flag hex 0x70 + 0xA0 1 0x10 CARRY unsigned 112 + 160 272 = CARRY(256) + 16 • CARRY flag shown in RED • with 32 bit addition, CARRY flag has a value of 232 CS1021 © 2018 jones@scss.tcd.ie School of Computer Science and Statistics, Trinity College Dublin 9-Oct-18 23 FLOW CONTROL 64 bit Addition using CARRY flag • ARM CPU hardware performs 32 bit operations • how can two 64 bit integers be added ? • use two registers to store each 64 bit integer 64 bits 32 MS bits R0 R2 32 LS bits R1 R3 • R0:R1 and R2:R3 used to store 64 bit integers • R0 and R2 contain the 32 most significant bits • R1 and R3 contain the 32 least significant bits • compute R0:R1 = R0:R1 + R2:R3 CS1021 © 2018 jones@scss.tcd.ie School of Computer Science and Statistics, Trinity College Dublin 9-Oct-18 24 FLOW CONTROL 64 bit Addition using CARRY flag ... • add least significant 32 bits using ADDS (will set CARRY flag) • add most significant bits using ADC (add with CARRY) 32 MS bits 32 LS bits R0 (2) add using ADC R2 R1 (1) add using ADDS R3 ADDS R1, R1, R3 ADC R0, R0, R2 ; add least significant bits and set CARRY ; add most significant bits with CARRY • method can be extended to 96, 128, ... bit addition • large binary keys (and arithmetic) used in public key encryption (256 bit keys) CS1021 © 2018 jones@scss.tcd.ie School of Computer Science and Statistics, Trinity College Dublin 9-Oct-18 25 FLOW CONTROL BORROW on Subtraction • what happens if subtracting a larger 8 bit unsigned integers from a smaller one? • results in a BORROW hex 0x70 - 0xA0 1 0xD0 unsigned 112 - 160 - 48 = BORROW(-256) + 208 (0xD0) BORROW • BORROW shown in RED CS1021 © 2018 jones@scss.tcd.ie School of Computer Science and Statistics, Trinity College Dublin 9-Oct-18 26 FLOW CONTROL CARRY Flag on Subtraction ... • turns out that BORROW = NOT CARRY (or CARRY = NOT BORROW) • illustrate by performing subtraction by adding the 2’s complement • 0x70 – 0xA0 • 2’s complement 0xA0 = 0x5F + 1 = 0x60 hex 0x70 + 0x60 0 0xD0 CARRY unsigned 112 - 160 - 48 = BORROW(-256) + 208 (0xD0) • CARRY = 0 shown in RED, therefore BORROW = 1 CS1021 © 2018 jones@scss.tcd.ie School of Computer Science and Statistics, Trinity College Dublin 9-Oct-18 27 FLOW CONTROL 64 bit Subtraction using CARRY flag • compute R0:R1 = R0:R1 - R2:R3 • subtract least significant 32 bits using SUBS (will set CARRY flag) • subtract most significant bits using SBC (subtract with CARRY) 32 MS bits 32 LS bits R0 (2) subtract using SBC R2 R1 (1) subtract using SUBS R3 • ALSO RSC reverse subtract with CARRY • dst = src2 – src1 + CARRY - 1 SUBS R1, R1, R3 SBC R0, R0, R2 ; subtract least significant bits and set CARRY ; subtract most significant bits with CARRY • SBC should really be subtract with BORROW! since dst = src1 - src2 + CARRY - 1 • if BORROW (CARRY = 0) dst = src1 - src2 - 1 (if NOT BORROW dst = src1 - src2) CS1021 © 2018 jones@scss.tcd.ie School of Computer Science and Statistics, Trinity College Dublin 9-Oct-18 28 FLOW CONTROL OVERFLOW flag • if the result of an addition or subtraction is outside the signed number range then an OVERFLOW occurs • determined by testing the MSB of the source operands and result • for addition r = a + b V = 1 if MSB(a) == MSB(b) && MSB(r) != MSB(a) • for subtraction r = a – b V = 1 if MSB(a) != MSB(b) && MSB(r) != MSB(a) CS1021 © 2018 jones@scss.tcd.ie School of Computer Science and Statistics, Trinity College Dublin 9-Oct-18 29 FLOW CONTROL Example Condition Code Flags after CMP instruction • compare 0x70000000 with 0xA0000000 LDR R0, =0x70000000 LDR R1, =0xA0000000 CMP R0, R1 ; R0 = 0x70000000 ; R1 = 0xA0000000 ; set flags on result of 0x70000000 – 0xA0000000 • CMP always sets the four condition code flags • N=1 • Z= 0 • C = 0 (BORROW = 1) • V =1 hex 0x70000000 - 0xA0000000 0 0xD0000000 CARRY - unsigned 1,879,048,192 2,684,354,560 -805,306,368 signed 1,879,048,192 - -1,610,612,736 3,489,660,928 • remember for subtraction V = 1 if MSB(a) != MSB(b) && MSB(r) != MSB(a) CS1021 © 2018 jones@scss.tcd.ie School of Computer Science and Statistics, Trinity College Dublin 9-Oct-18 30 FLOW CONTROL Example Condition Code Flags after CMP instruction ... • unsigned interpretation 0xD0000000 = 3,489,660,928 (1,879,048,192 - 2,684,354,560 = -805,306,368) subtracting a larger integer from a smaller one BORROW = 1 (CARRY = 0) signed interpretation 0xD0000000 = -805,306,368 (1,879,048,192 + 1,610,612,736 = 3,489,660,928) result not in range  OVERFLOW = 1 (two minuses make a +) unsigned branches - test CARRY and ZERO flags signed branches test - OVERFLOW and ZERO flags • • • CS1021 © 2018 jones@scss.tcd.ie School of Computer Science and Statistics, Trinity College Dublin 9-Oct-18 31 FLOW CONTROL Check using uVision stop after CMP instruction condition code flags CS1021 © 2018 jones@scss.tcd.ie School of Computer Science and Statistics, Trinity College Dublin 9-Oct-18 32 FLOW CONTROL Branch Instructions in Machine Code • branch instructions are encoded in machine code as follows 32 bits 44 24 • 4 bit condition field determines which condition is tested if (condition) { PC = PC + 8 + 4*offset; // condition TRUE } else { PC = PC + 4; // condition FALSE } • since instructions are 4 bytes, offset is multiplied by 4 (equivalent to appending two least significant zero bits) before being signed extended and added to the PC • due to the fetch-decode-execute pipeline, the PC has increased by 8 by the time this addition takes place (assembler takes this into account when calculating offsets) condition 0 0 1 0 offset CS1021 © 2018 jones@scss.tcd.ie School of Computer Science and Statistics, Trinity College Dublin 9-Oct-18 33 FLOW CONTROL Branch Condition field Bxx code Condition Code Flag Evaluation EQ 0000 Z set NE 0001 Z clear CS / HS 0010 C set CC / LO 0011 C clear MI 0100 N set PL 0101 N clear VS 0110 V set VC 0111 V clear HI 1000 C set and Z clear LS 1001 C clear or Z set GE 1010 N set and V set, or N clear and V clear LT 1011 N set and V clear, or N clear and V set GT 1100 Z clear, or N set and V set, or N clear and V clear LE 1101 Z set, or N set and V clear, or N clear and V set none / AL 1110 ALWAYS 1110 RESERVED CS1021 © 2018 jones@scss.tcd.ie School of Computer Science and Statistics, Trinity College Dublin 9-Oct-18 34 C set = higher or same C clear = lower FLOW CONTROL Unconditional Branch Instruction Example CS1021 © 2018 jones@scss.tcd.ie School of Computer Science and Statistics, Trinity College Dublin 9-Oct-18 35 machine code for unconditional branch FLOW CONTROL Unconditional Branch Instruction Example • assembly language L B L ; unconditional branch to L • instruction @ address 0x00000014 • machine code 0xEAFFFFFE 44 24 • 0xEA => unconditional branch
• offset => 0xFFFFFE
• sign extend 24 bit offset to 32 bits => 0xFFFFFFFE
• multiply by 4 (by appending two least significant zero bits) => 0xFFFFFFFF8
• PC = PC + 8 + 0xFFFFFFF8
• PC = 0x00000014 + 0x00000008 + 0xFFFFFFF8 => 0x00000014
• unconditional branch to itself [an infinite loop]
32 bits
condition
1
0
1
0
offset
CS1021 © 2018 jones@scss.tcd.ie School of Computer Science and Statistics, Trinity College Dublin 9-Oct-18
36

Related Posts