Transcript ppt

Conditional Processing
Computer Organization and Assembly Languages
Yung-Yu Chuang
2006/11/13
with slides by Kip Irvine
Assignment #2 CRC32 checksum
unsigned int crc32(const char* data,
size_t length)
{
// standard polynomial in CRC32
const unsigned int POLY = 0xEDB88320;
// standard initial value in CRC32
unsigned int reminder = 0xFFFFFFFF;
for(size_t i = 0; i < length; i++){
// must be zero extended
reminder ^= (unsigned char)data[i];
for(size_t bit = 0; bit < 8; bit++)
if(reminder & 0x01)
reminder = (reminder >> 1) ^ POLY;
else
reminder >>= 1;
}
return reminder ^ 0xFFFFFFFF;
}
Boolean and comparison instructions
•
•
•
•
•
•
•
•
CPU Status Flags
AND Instruction
OR Instruction
XOR Instruction
NOT Instruction
Applications
TEST Instruction
CMP Instruction
Status flags - review
• The Zero flag is set when the result of an operation
equals zero.
• The Carry flag is set when an instruction generates a
result that is too large (or too small) for the
destination operand.
• The Sign flag is set if the destination operand is
negative, and it is clear if the destination operand is
positive.
• The Overflow flag is set when an instruction generates
an invalid signed result.
• Less important:
– The Parity flag is set when an instruction generates an even number
of 1 bits in the low byte of the destination operand.
– The Auxiliary Carry flag is set when an operation produces a carry out
from bit 3 to bit 4
NOT instruction
• Performs a bitwise Boolean NOT operation on a
single destination operand
• Syntax: (no flag affected)
NOT destination
NOT
• Example:
mov al, 11110000b
not al
NOT
00111011
11000100
inverted
AND instruction
• Performs a bitwise Boolean AND operation
between each pair of matching bits in two
operands
• Syntax: (O=0,C=0,SZP)
AND destination, source
• Example:
mov al, 00111011b
and al, 00001111b
00111011
AND 0 0 0 0 1 1 1 1
cleared
00001011
bit extraction
unchanged
AND
OR instruction
• Performs a bitwise Boolean OR operation
between each pair of matching bits in two
operands
• Syntax: (O=0,C=0,SZP)
OR destination, source
• Example:
mov dl, 00111011b
or dl, 00001111b
00111011
OR 0 0 0 0 1 1 1 1
unchanged
00111111
set
OR
XOR instruction
• Performs a bitwise Boolean exclusive-OR
operation between each pair of matching bits
in two operands
• Syntax: (O=0,C=0,SZP)
XOR destination, source
• Example:
XOR
mov dl, 00111011b
xor dl, 00001111b
00111011
XOR 0 0 0 0 1 1 1 1
unchanged
00110100
inverted
XOR is a useful way to invert the bits in an operand and data encryption
Applications
(1 of 4)
• Task: Convert the character in AL to upper case.
• Solution: Use the AND instruction to clear bit 5.
mov al,'a‘
and al,11011111b
; AL = 01100001b
; AL = 01000001b
Applications
(2 of 4)
• Task: Convert a binary decimal byte into its
equivalent ASCII decimal digit.
• Solution: Use the OR instruction to set bits 4 and 5.
mov al,6
or al,00110000b
; AL = 00000110b
; AL = 00110110b
The ASCII digit '6' = 00110110b
Applications
(3 of 4)
• Task: Jump to a label if an integer is even.
• Solution: AND the lowest bit with a 1. If the
result is Zero, the number was even.
mov ax,wordVal
and ax,1
jz EvenValue
; low bit set?
; jump if Zero flag set
Applications
(4 of 4)
• Task: Jump to a label if the value in AL is not zero.
• Solution: OR the byte with itself, then use the JNZ
(jump if not zero) instruction.
or al,al
jnz IsNotZero
; jump if not zero
ORing any number with itself does not change its value.
String encryption
key
message
(plain text)
encoder
unintelligible string
(cipher text)
message
(plain text)
encoder
key
Encrypting a string
KEY = 239
.data
buffer BYTE BUFMAX DUP(0)
bufSize DWORD $-buffer
.code
mov ecx,bufSize
; loop counter
mov esi,0
; index 0 in buffer
L1:
xor buffer[esi],KEY ; translate a byte
inc esi
; point to next byte
loop L1
Message: Attack at dawn.
Cipher text: «¢¢Äîä-Ä¢-ïÄÿü-Gs
Decrypted: Attack at dawn.
TEST instruction
• Performs a nondestructive AND operation between each
pair of matching bits in two operands
• No operands are modified, but the flags are affected.
• Example: jump to a label if either bit 0 or bit 1 in AL is
set.
test al,00000011b
jnz ValueFound
• Example: jump to a label if neither bit 0 nor bit 1 in
AL is set.
test al,00000011b
jz
ValueNotFound
CMP instruction
(1 of 3)
• Compares the destination operand to the source
operand
– Nondestructive subtraction of source from destination
(destination operand is not changed)
• Syntax: (OSZCAP)
CMP destination, source
• Example: destination == source
mov al,5
cmp al,5
; Zero flag set
• Example: destination < source
mov al,4
cmp al,5
; Carry flag set
CMP instruction
(2 of 3)
• Example: destination > source
mov al,6
cmp al,5
; ZF = 0, CF = 0
(both the Zero and Carry flags are clear)
The comparisons shown so far were unsigned.
CMP instruction
(3 of 3)
The comparisons shown here are performed with
signed integers.
• Example: destination > source
mov al,5
cmp al,-2
; Sign flag == Overflow flag
• Example: destination < source
mov al,-1
cmp al,5
; Sign flag != Overflow flag
Conditions
unsigned
ZF
CF
destination<source
0
1
destination>source
0
0
destination=source
1
0
signed
flags
destination<source
SF != OF
destination>source
SF == OF
destination=source
ZF=1
Setting and clearing individual flags
and
or
or
and
stc
clc
al,
al,
al,
al,
0
1
80h
7Fh
;
;
;
;
;
;
set Zero
clear Zero
set Sign
clear Sign
set Carry
clear Carry
mov al, 7Fh
inc al
; set Overflow
or eax, 0
; clear Overflow
Conditional jumps
Conditional structures
• There are no high-level logic structures such as
if-then-else, in the IA-32 instruction set. But,
you can use combinations of comparisons and
jumps to implement any logic structure.
• First, an operation such as CMP, AND or SUB is
executed to modified the CPU flags. Second, a
conditional jump instruction tests the flags and
changes the execution flow accordingly.
CMP AL, 0
JZ L1
:
L1:
Jcond instruction
• A conditional jump instruction branches to a
label when specific register or flag conditions
are met
Jcond destination
•
1.
2.
3.
4.
Four groups: (some are the same)
based on specific flag values
based on equality between operands
based on comparisons of unsigned operands
based on comparisons of signed operands
Jumps based on specific flags
Jumps based on equality
Jumps based on unsigned comparisons
＞≧＜≦
Jumps based on signed comparisons
Examples
• Compare unsigned AX to BX, and copy the larger of
the two into a variable named Large
mov Large,bx
cmp ax,bx
jna Next
mov Large,ax
Next:
• Compare signed AX to BX, and copy the smaller of
the two into a variable named Small
mov
cmp
jnl
mov
Next:
Small,ax
bx,ax
Next
Small,bx
Examples
• Find the first even number in an array of unsigned
integers
.date
intArray DWORD 7,9,3,4,6,1
.code
...
mov ebx, OFFSET intArray
mov ecx, LENGTHOF intArray
L1:
test DWORD PTR [ebx], 1
jz
found
add ebx, 4
loop L1
...
BT (Bit Test) instruction
• Copies bit n from an operand into the Carry flag
• Syntax: BT bitBase, n
– bitBase may be r/m16 or r/m32
– n may be r16, r32, or imm8
• Example: jump to label L1 if bit 9 is set in the
AX register:
bt AX,9
jc L1
; CF = bit 9
; jump if Carry
• BTC bitBase, n: bit test and complement
• BTR bitBase, n: bit test and reset (clear)
• BTS bitBase, n: bit test and set
Conditional loops
LOOPZ and LOOPE
• Syntax:
LOOPE destination
LOOPZ destination
• Logic:
– ECX  ECX – 1
– if ECX != 0 and ZF=1, jump to destination
• The destination label must be between -128
and +127 bytes from the location of the
following instruction
• Useful when scanning an array for the first
element that meets some condition.
LOOPNZ and LOOPNE
• Syntax:
LOOPNZ destination
LOOPNE destination
• Logic:
– ECX  ECX – 1;
– if ECX != 0 and ZF=0, jump to destination
LOOPNZ example
The following code finds the first positive value in an array:
.data
array SWORD -3,-6,-1,-10,10,30,40,4
sentinel SWORD 0
.code
mov esi,OFFSET array
mov ecx,LENGTHOF array
next:
test WORD PTR [esi],8000h
; test sign bit
pushfd
; push flags on stack
add esi,TYPE array
popfd
; pop flags from stack
loopnz next
; continue loop
jnz quit
; none found
sub esi,TYPE array
; ESI points to value
quit:
Your turn
Locate the first nonzero value in the array. If none is
found, let ESI point to the sentinel value:
.data
array SWORD 50 DUP(?)
sentinel SWORD 0FFFFh
.code
mov esi,OFFSET array
mov ecx,LENGTHOF array
L1: cmp WORD PTR [esi],0
; check for zero
quit:
Solution
.data
array SWORD 50 DUP(?)
sentinel SWORD 0FFFFh
.code
mov esi,OFFSET array
mov ecx,LENGTHOF array
L1:cmp WORD PTR [esi],0 ;
pushfd
;
add esi,TYPE array
Popfd
;
loope next
;
jz quit
;
sub esi,TYPE array
;
quit:
check for zero
push flags on stack
pop flags from stack
continue loop
none found
ESI points to value
Conditional structures
Block-structured IF statements
Assembly language programmers can easily translate
logical statements written in C++/Java into assembly
language. For example:
if( op1 == op2 )
X = 1;
else
X = 2;
mov
cmp
jne
mov
jmp
L1: mov
L2:
eax,op1
eax,op2
L1
X,1
L2
X,2
Example
Implement the following pseudocode in assembly
language. All values are unsigned:
if( ebx <= ecx )
{
eax = 5;
edx = 6;
}
cmp
ja
mov
mov
next:
ebx,ecx
next
eax,5
edx,6
Example
Implement the following pseudocode in assembly
language. All values are 32-bit signed integers:
if( var1
var3 =
else
{
var3 =
var4 =
}
<= var2 )
10;
6;
7;
mov
cmp
jle
mov
mov
jmp
L1: mov
L2:
eax,var1
eax,var2
L1
var3,6
var4,7
L2
var3,10
Compound expression with AND
• When implementing the logical AND operator, consider
that HLLs use short-circuit evaluation
• In the following example, if the first expression is false,
the second expression is skipped:
if (al > bl) AND (bl > cl)
X = 1;
Compound expression with AND
if (al > bl) AND (bl > cl)
X = 1;
This is one possible implementation . . .
cmp al,bl
; first expression...
ja L1
jmp next
L1:
cmp bl,cl
; second expression...
ja L2
jmp next
L2:
; both are true
mov X,1
; set X to 1
next:
Compound expression with AND
if (al > bl) AND (bl > cl)
X = 1;
But the following implementation uses 29% less code
by reversing the first relational operator. We allow the
program to "fall through" to the second expression:
cmp
jbe
cmp
jbe
mov
next:
al,bl
next
bl,cl
next
X,1
;
;
;
;
;
first expression...
quit if false
second expression...
quit if false
both are true
Your turn . . .
Implement the following pseudocode in assembly
language. All values are unsigned:
if( ebx
&& ecx
{
eax =
edx =
}
cmp
ja
cmp
jbe
mov
mov
<= ecx
> edx )
5;
6;
ebx,ecx
next
ecx,edx
next
eax,5
edx,6
next:
(There are multiple correct solutions to this problem.)
Compound Expression with OR
• In the following example, if the first expression is true,
the second expression is skipped:
if (al > bl) OR (bl > cl)
X = 1;
Compound Expression with OR
if (al > bl) OR (bl > cl)
X = 1;
We can use "fall-through" logic to keep the code as
short as possible:
cmp al,bl
ja L1
cmp bl,cl
jbe next
L1:mov X,1
next:
; is AL > BL?
; yes
; no: is BL > CL?
; no: skip next statement
; set X to 1
WHILE Loops
A WHILE loop is really an IF statement followed by the
body of the loop, followed by an unconditional jump to
the top of the loop. Consider the following example:
while( eax < ebx)
eax = eax + 1;
_while:
cmp eax,ebx
jae _endwhile
inc eax
jmp _while
_endwhile:
;
;
;
;
check loop condition
false? exit loop
body of loop
repeat the loop
Your turn . . .
Implement the following loop, using unsigned 32-bit
integers:
while( ebx <= val1)
{
ebx = ebx + 5;
val1 = val1 - 1
}
_while:
cmp ebx,val1
ja _endwhile
add ebx,5
dec val1
jmp while
_endwhile:
; check loop condition
; false? exit loop
; body of loop
; repeat the loop
Example: IF statement nested in a loop
while(eax < ebx)
{
eax++;
if (ebx==ecx)
X=2;
else
X=3;
}
_while:
cmp
jae
inc
cmp
jne
mov
jmp
_else:
mov
jmp
_endwhile:
eax, ebx
_endwhile
eax
ebx, ecx
_else
X, 2
_while
X, 3
_while
Table-driven selection
• Table-driven selection uses a table lookup to
replace a multiway selection structure
(switch-case statements in C)
• Create a table containing lookup values and
the offsets of labels or procedures
• Use a loop to search the table
• Suited to a large number of comparisons
Table-driven selection
Step 1: create a table containing lookup values and
procedure offsets:
.data
CaseTable BYTE 'A'
; lookup value
DWORD Process_A
; address of procedure
EntrySize = ($ - CaseTable)
BYTE 'B'
DWORD Process_B
BYTE 'C'
DWORD Process_C
BYTE 'D'
DWORD Process_D
NumberOfEntries = ($ - CaseTable) / EntrySize
Table-driven selection
Step 2: Use a loop to search the table. When a match is
found, we call the procedure offset stored in the current
table entry:
mov ebx,OFFSET CaseTable ; point EBX to
mov ecx,NumberOfEntries ; loop counter
L1:cmp al,[ebx]
jne L2
call NEAR PTR [ebx + 1]
jmp L3
L2:add ebx,EntrySize
loop L1
L3:
required for procedure
pointers
the table
; match found?
; no: continue
; yes: call the procedure
; and exit the loop
; point to next entry
; repeat until ECX = 0
Application: finite-state machines
• A finite-state machine (FSM) is a graph structure that
changes state based on some input. Also called a statetransition diagram.
• We use a graph to represent an FSM, with squares or
circles called nodes, and lines with arrows between the
circles called edges (or arcs).
• A FSM is a specific instance of a more general structure
called a directed graph (or digraph).
• Three basic states, represented by nodes:
– Start state
– Terminal state(s)
– Nonterminal state(s)
Finite-state machines
• Accepts any sequence of symbols that puts it
into an accepting (final) state
• Can be used to recognize, or validate a
sequence of characters that is governed by
language rules (called a regular expression)
FSM Examples
• FSM that recognizes strings beginning with 'x',
followed by letters 'a'..'y', ending with 'z':
'a'..'y'
start
'x'
A
C
B
'z
'
• FSM that recognizes signed integers:
digit
C
digit
start
A
+,-
digit
B
Your turn . . .
• Explain why the following FSM does not work as
well for signed integers as the one shown on
the previous slide:
digit
digit
start
A
+,-
B
Implementing an FSM
digit
C
digit
start
A
+,-
digit
B
The following is code from
State A in the Integer FSM:
StateA:
call Getnext
; read next char into AL
cmp al,'+‘
; leading + sign?
je StateB
; go to State B
cmp al,'-‘
; leading - sign?
je StateB
; go to State B
call IsDigit
; ZF = 1 if AL = digit
jz StateC
; go to State C
call DisplayErrorMsg ; invalid input found
jmp Quit
Isdigit
Isdigit PROC
cmp al,’0’
jb
L1
cmp al,’9’
ja L1
test ax,0
L1: ret
Isdigit ENDP
Your turn
digit
C
digit
start
StateB:
call
call
jz
call
jmp
A
+,-
digit
B
Getnext
; read next char into AL
Isdigit
; ZF = 1 if AL is a digit
StateC
DisplayErrorMsg ; invalid input found
Quit
Implementing an FSM
digit
C
digit
start
StateC:
call
jz
call
jz
cmp
je
call
jmp
A
+,-
digit
B
Getnext
; read next char into AL
Quit
; quit if Enter pressed
Isdigit
; ZF = 1 if AL is digit
StateC
AL,ENTER_KEY ; Enter key pressed?
Quit
; yes: quit
DisplayErrorMsg ; no: invalid input
Quit
Finite-state machine example
• [sign]integer.[integer][exponent]
sign → {+|-}
exponent → E[{+|-}]integer
High-level directives
• .IF, .ELSE, .ELSEIF, and .ENDIF can be used to create
block-structured IF statements.
• Examples:
.IF eax > ebx
mov edx,1
.ELSE
mov edx,2
.ENDIF
.IF eax > ebx && eax > ecx
mov edx,1
.ELSE
mov edx,2
.ENDIF
• MASM generates "hidden" code for you, consisting of
code labels, CMP and conditional jump instructions.
Relational and logical operators
MASM-generated Code
.data
val1
DWORD 5
result DWORD ?
Generated code:
.code
mov eax,6
.IF eax > val1
mov result,1
.ENDIF
mov eax,6
cmp eax,val1
jbe @C0001
mov result,1
@C0001:
MASM automatically generates an unsigned jump (JBE).
The use of signed or unsigned comparison depends on data
type. If not defined (such as .IF eax>ebx), MASM sue
unsigned comparisons.
.REPEAT directive
Executes the loop body before testing the loop condition
associated with the .UNTIL directive.
Example:
; Display integers 1 – 10:
mov eax,0
.REPEAT
inc eax
call WriteDec
call Crlf
.UNTIL eax == 10
.WHILE directive
Tests the loop condition before executing the loop body
The .ENDW directive marks the end of the loop.
Example:
; Display integers 1 – 10:
mov eax,0
.WHILE eax < 10
inc eax
call WriteDec
call Crlf
.ENDW