代写代考 COMPARING 64-BIT INTEGERS – cscodehelp代写
By default, statements are executed sequentially in both C and assembly:
statement statement … statement
Order of execution
Copyright By cscodehelp代写 加微信 cscodehelp
However….
Decisions imply departure from sequential execution:
Then statement
HLL versus Assembly
• In assembly, all statements arranged vertically, so we rearrange the flowchart:
Then statement
Then statement
This arrangement requires a “goto”
FALSE test
if (test == FALSE) goto L1
Then-statement L1: ….
Then statement
This is similar to assembly, where decisions are implemented as a test followed by an instruction that branches (or not) depending on the result of the test.
COMPARE INSTRUCTIONS
Decisions in assembly require a two instruction sequence. A com- pare instruction compares two operands, followed by a conditional branch instruction that makes the actual decision to branch or not.
Instruction
CMP Rn,Op2
Updates flags N,Z,C and V
Compare Negative
CMN Rn,Op2
Op2 may be a small constant, a register, or a shifted register.
CMP is identical to the SUBS instruction, but discards the actual difference. The assembler automatically replaces CMP Rn,─constant by CMN Rn,constant
TEST INSTRUCTIONS
Instruction
TST Rn,Op2
Updates flags N and Z; if shifted, Op2 may affect C flag
Test Equivalence
TEQ Rn,Op2
TST is used to test whether any of the bits in Rn specified by Op2 are 1’s. TEQ is used to test whether Rn = Op2 without affecting the C or V flags.
CONDITIONAL BRANCH INSTRUCTIONS
If-then statement in C
Equivalent C code using goto and label
int32_t s32 ;
if (s32 > 10) then statement •••
int32_t s32 ;
if (s32 <= 10) goto L1 ;
then statement
Equivalent if-then statement in assembly
LDR R0,=s32// R0 <-- &s32
LDR R0,[R0]// CMP requires operand to be in a register CMP R0,10 // Compare s32 to 10 and ...
BLE L1 // if (s32 <= 10) goto L1
then statement
Decisions in assembly are like an if statement that controls a goto statement.
A conditional branch instruction is written as “B” followed a condition code.
CONDITIONAL BRANCH INSTRUCTIONS
7 > 12 ? unsigned 01112 > 11002 ? (FALSE)
Signed and unsigned require different condition codes for magnitude comparisons!
HI (Higher Than)
HS (Higher Than or Same)
LO (Lower Than)
LS (Lower Than or Same)
EQ (Equal)
NE (Not Equal)
GT (Greater Than)
GE (Greater Than or Equal)
LT (Less Than)
LE (Less Than or Equal)
EQ (Equal)
NE (Not Equal)
CHOOSING THE CONDITION
You can’t use the same condition as used in C to control an if-statement.
If a condition doesn’t include the equality case, the opposite must. Vice-Versa!
COMPLETE CONDITION LIST
NE Not equal
GE Signed ≥ (“Greater than or Equal”) LT Signed < ("Less Than")
GT Signed > (“Greater Than”)
LE Signed ≤ (“Less than or Equal”)
Z = 1 || N ≠ V
EQ and NE are same for
signed and unsigned.
HS (CS) LO (CC) HI
Unsigned ≥ (“Higher or Same”) or Carry Set C = 1 Unsigned < ("Lower") or Carry Clear
Unsigned > (“Higher”)
Unsigned ≤ (“Lower or Same”) C = 0 || Z = 1
These are used for
Z = 0 && N = V
signed comparisons
Minus/negative
Plus – positive or zero (non-negative)
No overflow
AL Always (unconditional)
These are used for
C = 1 && Z = 0
unsigned comparisons
(Rarely used)
Never used. Included for completeness.
IF-THEN-ELSE SEQUENCES
C Source Code
Converted to goto
Assembly Code
int32_t s32 ;
if (s32 > 0)
then state
then statement
else statement
int32_t s32 ;
if (s32 <= 0) goto L2;
then statement
else statement
LDR R0,=s32 // is s32 > 0 ? LDR R0,[R0]
then statement
B L3 // skip over else!!
L3: … // end of the if
else statement
else statement
Without the unconditional branch, the else statement will always be executed!
IF-THEN-ELSE SEQUENCES
C Source Code
Assembly Code
int32_t s32 ;
if (s32 == 1)
else if (s32 == 2)
else if (s32 == 3)
statement #1
statement #1
statement #2
statement #2
statement #3
statement #3
LDR R0,=s32 // R0 <-- &s32 LDR R0,[R0] // Is s32 > 0 ? CMP R0,1
statement #1
statement #1
// skip to end!
stateemmentt#2#2
L3: CMP R0,3 BNE L4
// skip to end!
statement #3
statement #3
// end of chain
These unconditional branches insure that only one statement is executed.
COMPARING 64-BIT INTEGERS
if (a64 > b64) then statement else Celse statement
LDR R0,=a64 // R0 <-- &a64
LDRD R0,R1,[R0] // get a64 (R0=LS Half; R1=MS Half) LDR R2,=b64 // R2 <-- &b64
LDRD R2,R3,[R2] // get b64 (R2=LS Half; R3=MS Half)
BGT L1 BLT L2 CMP R0,R2 BLS L2
L1: then statement B L3
L2: else statement L3: ...
// compare most-significant halves
// use BHI if operands are unsigned
// use BLO if operands are unsigned
// MS halves ==, compare LS halves
// use BLS for both signed and unsigned
// a64 > b64
// a64 <= b64
This solution is based on comparing digits in a most- to-least significant order.
COMPARING 64-BIT INTEGERS
if (a64 > b64) then statement else C else statement
LDR R0,=a64 // R0 <-- &a64
LDRD R0,R1,[R0] // get a64 (R0 = LS Half; R1 = MS Half) LDR R2,=b64 // R2 <-- &b64
LDRD R2,R3,[R2] // get b64 (R2 = LS Half; R3 = MS Half)
SUBS R0,R0,R2 SBCS R1,R1,R3 BLE L1
then statement
// subtract LS halves, capture borrow // subtract MS halves w/brw; set flags // use BLS if operands are unsigned
else statement
// a64 > b64
// a64 <= b64
Faster approach uses a 64- bit subtraction to eliminate unnecessary branching.
Every branch taken causes a delay to refill the instruction pipeline, reducing performance. If-Then (IT) blocks avoid this by selectively enabling or disabling the execute phase of one to four instructions.
C Source Code
Corresponding Assembly Code
int32_t a, b, c ;
if (a > 0) b = 1 ; else c = 2 ;
The “IT Block”
LDR R0,[⋯]//Isa>0?
ITTEE GT //controls4instructions
LDRGT STR LDR STR
R0,=1 // yes: b 1 R0,[⋯]
R0,=2 // no: c2 R0,[⋯]
These suffixes specify the condition that enables the instruction and must match the condition code, the T’s and the E’s used in the IT instruction.
This specifies the condition that enables the next instruction.
Up to 3 additional instructions can be controlled by appending T’s or E’s.
A fast 64-bit unsigned max function
// uint64_t uMax64(uint64_t u1, uint64_t u2)
.global uMax64 .align .thumb_func
uMax64: SUBS
SBCS R12,R3,R1 // set flags, discard result
R12,R2,R0 // perform a 64-bit subtract
HI // if (u2 > u1) …
R1,R3 // then return u2 instead of u1 R0,R2 // by copying u2 into R1.R0
BX LR // return .end
Using IT Blocks to Reduce Code Size
Instructions within an IT block never affect the flags – ADD is 32-bits (4 bytes) outside of an IT block
– ADD is 16-bits (2 bytes) inside an IT block
(Assembler replaces ADD inside IT block with ADDS since the ‘S’ has no effect and the ADDS allows a 16-bit representation.)
16 instruction bytes
10 instruction bytes
ADD R0,R0,R1 // 4 bytes ADD R0,R0,R1 // 4 bytes ADD R0,R0,R1 // 4 bytes ADD R0,R0,R1 // 4 bytes
ITTTT AL ADDAL R0,R0,R1 ADDAL R0,R0,R1 ADDAL R0,R0,R1 ADDAL R0,R0,R1
// 2 bytes // 2 bytes // 2 bytes // 2 bytes // 2 bytes
COMPOUND CONDITIONALS
• Example: if (x > 10 && x < 20) y = 0 ;
• In assembly, this must be separated into two separate “compare – conditional branch” sequences, similar to:
if (x > 10) if (x <= 10) goto L1 ; if (x <= 10) goto L1 ; {{{
if (x < 20) y = 0 ; if (x < 20) y = 0 ; if (x >= 20) goto L2 ; } } y= 0 ;
COMPOUND LOGICAL OR
if (x < –100 || x > +100)
then statement
if (x < –100) goto L1 ;
if (x > +100) goto L1 ; goto L2 ;
then statement
One condition per statement, each controlling a goto.
When you see this pattern, the last goto can be eliminated.
C statements now easily map 1-to-1 into assembly
LDR R0,[⋯] // R0 <-- x
CMP R0,-100 // if (x < –100) BLT L1 // gotoL1
CMP R0,100 // if (x <= +100) BLE L2 // gotoL2
last goto eliminated by reversing the last compare.
if(x< –100) goto L1; L1:
then statement
if(x<=+100) goto L2;
then statement
COMPOUND LOGICAL AND
if (x >= –100 && x <= +100) then statement
Invert the entire condition so the if controls a goto.
if (!(x >= –100 && x <= +100)) goto L1 ;
then statement
Use DeMorgan’s Law to replace && by ||.
if (x < –100 || x > +100) goto L1 ;
then statement
Separate the conditions as we did before.
C statements now easily map 1-to-1 into assembly
LDR R0,[⋯] // R0 <-- x
CMP R0,-100 // if (x < –100) BLT L1 // goto L1 CMP R0,100 // if (x > +100) BGT L1 // goto L1
then statement
if (x < –100) goto L1 ;
if (x > +100) goto L1 ;
then statement
COMPOUND CONDITIONALS
Summary with else statements
Compound Conditional in C
Rewritten with goto’s and labels
Assembly language version
if (x > 0 && x < 9)
then statement
else statement
if (x <= 0) goto L1 ;
if (x >= 9) goto L1 ;
then statement
else statement
LDR R0,[⋯]//R0x CMP RO,0
then statement
else statement
if (x == 0 || x == 9)
then statement
else statement
if (x == 0) goto L1 ;
if (x != 9) goto L2 ;
then statement else statement
LDR R0,[⋯]//R0x CMP R0,0
then statement
else statement
Another Approach: Compound AND
if (x >= –100 && x <= +100)
then statement
(3) Identify conditional branch instructions
No BLT L1 -100?
X <= +100?
then statement
(1) Layout flowchart
boxes vertically.
LDR R0,[⋯]//R0x CMP R0,-100
CMP R0,+100
(4) Translate to assembly
ththeenn-statemeentnt L1: ...
(2) Identify needed labels
Another Approach: Compound OR
if (x < –100 || x > +100)
then statement
(1) Initial flowchart
(2) Layout flowchart
boxes vertically.
LDR R0,[⋯] CMP R0,-100 BLT L1
CMP R0,+100 BLE L2
then statement
+100? BLE L2 L1: Yes
then statement
(3) Identify needed labels
(3) Identify conditional branch instructions
(5) Translate to assembly
then-statement
then statement
WRITING LOOPS
Instruction
Compare and Branch if Zero
CBZ Rn,label
Branch to label If Rn=0
Compare and Branch if Non-Zero
CBNZ Rn,label
Branch to label If Rn≠0
CMP R0,0 BEQ L1
CMP R0,0 BNE L1
Sometimes used at the top of a while or for loop
Sometimes used at the bottom of a do-while loop
WRITING LOOPS
// uint32_t Factorial(uint32_t n)
.global Factorial .align .thumb_func
Factorial:
done: MOVS.N R0,R1 BX LR
Loop initialization
Test for completion
MOVS.N R1,1 // initialize: Factorial = 1
CBZ R0,done // check n: Done if n is 0
MULS.N R1,R1,R0 // factorial *= n
SUBS.N R0,R0,1 // decrement n and update flags B top // branch to top of loop
Body of the loop
// leave result in R0 // return
Unconditional branch to repeat the loop.
WRITING LOOPS
// uint32_t gcd(uint32_t u1, uint32_t u2)
.global gcd
.align Test for completion .thumb_func
// This loop needs no initialization
CMP R0,R1 // continue? (u1 != u2) BEQ done
ITE HI // loop body and update: SUBHI R0,R0,R1 // u1 <- u1 – u2 SUBLS R1,R1,R0 // u2 <- u2 – u1
B gcd // branch to top of loop
done: BX LR // return: R0 = gcd(u1,u2)
Unconditional branch to repeat the loop.
Body of the loop
for (initialization; condition; update) {
loopBody ; }
initialization ; while (condition)
{ loopBody ; update ;
initialization ;
L1: if (!condition) goto L2 ;
loopBody ;
goto L1 ; // repeat
initialization ; while (1)
if (!condition) break ; loopBody ;
WHILE LOOP WITH COMPOUND CONDITIONAL
while (1) {
if (!condition1 || !condition2) break ; loopBody ;
while (condition1 && condition2) {
loopBody ;
while (1) {
if (!condition1) goto L1 ; if (!condition2) goto L1 ;
loopBody ;
L0: if (!condition1) goto L1 ; if (!condition2) goto L1 ;
loopBody ;
goto L0 ; L1:
WHILE LOOP WITH COMPOUND CONDITIONAL
while (condition1 || condition2) {
loopBody ;
while (1) {
if (condition1 || condition2) goto L1 ;
break ; L1: loopBody;
while (1) {
if (condition1) goto L1 ; if (condition2) goto L1 ; goto L2;
loopBody ;
L0: if(condition1)gotoL1; if (condition2) goto L1 ; goto L2 ;
L1: loopBody ; goto L0 ;
DO-WHILE LOOP WITH COMPOUND CONDITIONAL
loopBody ;
if ( condition1 || condition2) continue ; break ;
} while (1) ;
loopBody ;
} while (condition1 || condition2) ;
loopBody ;
if (condition1) continue ; if (condition2) continue ; break ;
} while(1) ;
L0: loopBody ;
if (condition1) goto L0 ; if (condition2) goto L0 ;
DO-WHILE LOOP WITH COMPOUND CONDITIONAL
loopBody ;
} while (condition1 && condition2) ;
loopBody ;
if (condition1 && condition2) continue ; break ;
} while (1) ;
L0: loopBody ;
if (!condition1) goto L1 ; if (!condition2) goto L1 ; goto L0 ;
loopBody ;
if (!condition1 || !condition2) break ; } while(1) ;
程序代写 CS代考 加微信: cscodehelp QQ: 2235208643 Email: kyit630461@163.com
