Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Computer Architecture/Assembly > 8 - Searching and Sorting Integer Arrays > Flashcards

8 - Searching and Sorting Integer Arrays Flashcards

1
Q

If you wanted to find the next random number in a range specified, how would you do so?

Order of parameters pushed:

  1. lowest acceptable value
  2. highest acceptable value
  3. address of return value
A 
push esp
mov ebp, esp
mov eax, [esp+16]
sub eax, [ebp+12]
call RandomRange
add eax, [ebp+12]
mov [ebp+8], eax
pop esp
ret 12
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is the assembly code for bubble sort?

A

BubbleSort PROC USES eax ecx esi,
pArray:PTR DWORD,
Count:DWORD

  mov ecx, Count
  dec ecx
L1: push ecx   ;save outer loop
  mov esi, pArray
L2: mov eax[esi]
  cmp [esi+4], eax
  jg L3
  xchg eax, [esi+4]
L3: add esi, 4
  loop L2
  pop ecx     ;retrieve outer loop
  loop L1
L4:ret

BubbleSort ENDP

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What does the OFFSET operator do?

A

It returns the distance in BYTES, of a label from the beginning of its enclosing statement. (The operating system adds the segment address from the segment register).

.data (starts at 4000h)
bVal BYTE ?
wVal WORD ?

.code
mov esi, OFFSET bval ;ESI = 4000h
mov esi, OFFSET wVal ; ESI = 4001h

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What does the PTR operator do?

A

PTR overrides the default type of a label (variable), which provides the flexibility to access part of a variable.

.data
myDouble DWORD 12345678h

.code
mov ax, myDouble ; error
mov ax, WORD PTR myDouble; loads 5678h
mov ax, WORD PTR [myDouble+2]; AL =  1234h
mov al, BYTE PTR myDouble ;AL = 78h
mov al, BYTE PTR [myDouble+1]; AL = 56h
mov WORD PTR myDouble ;saves 1357h
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

How can the PTR operator be used to combine elements?

A

It will combine elements and move them into a larger operand. The IA-32 CPU will automatically reverse the bytes.

.data
myBytes BYTE 12h, 34h, 56h, 78h

.code
mov ax, WORD PTR myBytes ;AX = 3412h
mov ax, WORD PTR [myBytes+2] ; AX = 7856h
mov eax, DWORD PTR myBytes
;EAX = 78563412h
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

How does the TYPE operator work?

A

The TYPE operator returns the size, in bytes, of a single element of a data declaration.

.data
var1 BYTE ?
var2 WORD ?
var3 DWORD ?
var4 QWORD ?
.code
mov eax, TYPE var1 ;1
mov eax, TYPE var2 ;2
mov eax, TYPE var3 ;4
mov eax, TYPE var4 ; 8
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What does the LENGTHOF operator do?

A

LENGTHOF counts the number of elements in a single data declaration. (The comments are the number of elements in that data declaration).

.data
byte1 BYTE 10, 20, 30  ;3
list1 WORD 30 DUP(?) ;30
list2 DWORD 30 DUP (?) ;30
list3 DWORD 1, 2, 3, 4 ;4
digitStr BYTE "1234567",0 ;8

.code
mov ecx, LENGTHOF list1 ;30

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What does the SIZEOF operator do?

A

It returns a value that is equivalent to multiplying LENGTHOF by TYPE (i.e. size in bytes).

.data
byte1 BYTE 10, 20, 30  ;3
list1 WORD 30 DUP (?) ;60
list2 DWORD 30 DUP (?) ;120
list3 DWORD 1, 2, 3, 4  ;16
digitStr BYTE "1234567",0 ;8

.code
mov ecx, SIZEOF list1 ;ecx = 60

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

How do the SIZEOF and LENGTHOF oeprands deal with arrays declared across multiple lines?

A

They still include all lines belonging to the declaration (if each line except the last ends with a comma).

.data
list DWORD 10, 20,
30, 40,
50, 60

.code
mov eax, LENGTHOF list ;6
mov ebx, SIZEOF list ;24

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

How can you use TYPE to do index scaling?

A

You can scale an indirect or indexed operand to the offset of an array element. This is done by multiplying the index by the array’s TYPE:

.data
listB BYTE 1, 2, 3, 4, 5, 6, 7
listW WORD 8, 9, 10, 11, 12, 13
listD DWORD 14, 15, 16, 17, 18, 19, 20, 21

.code
mov esi, 5
mov al, listB[esi * TYPE listB] ;al = 6
mov bx, listW [esi*TYPE listW] ;bx = 13
mov edx, listD[esi*TYPE listD] ;edx = 19
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

How can you declare a pointer variable that contains the offset of another variable?

A

The effect of the following is the same as “mov esi, OFFSET list”.

***Notice that you CANNOT dereference the pointer in one statement {[ptr]) because that’s a memory-to-memory operation!

.data
list DWORD 100 DUP(?)
ptr DWORD list

.code
mov esi, ptr
mov eax, [esi] ;EAX = @list

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

How would you calculate the sum of an array of 32-bit integers using register indexed addressing?

A

.data
intList DWORD 100h, 200h, 300h, 400h
ptrD DWORD initlist

.code
mov esi, ptrD  ;@ initList
mov ecx, LENGTHOF intList ;loop counter
mov eax, 0
L1:
add eax, [esi] ;add an integer
add esi, TYPE intList ;point to next integer
loop L1
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

How would you calculate the sum of an array of 32-bit integers in indexed mode (multiples)?

A

.data
intList DWORD 100h, 200h, 300h, 400h

.code 
mov esi, 0
mov eax, 0 ;zero the accumulator
L1:
add eax, intList[esi*TYPE intList]
inc esi
loop L1
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What are the five groups of string primitives?

A
  1. Move string data: MOVSB, MOVSW, MOVSD - these copy data from memory addressed by EDI.
  2. Compare strings: CMPSB, CMPSW, CMPSD - compare the contents of 2 memory locations addressed by EDI and ESI.
  3. Scan string - SCASB, SCASW, SCASD - compare the accumulator (AL, AX, or EAX) to the contents of memory addressed by ESI.
  4. Store string data: STOSB, STOSW, STOSD - store the accumulator contents into memory addressed by EDI.
  5. Load accumulator from string: LODSB, LODSW, LODSD - load memory addressed by ESI into the accumulator.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is a repeat prefix and what does it do?

A

The instruction repeats, using ECS as a counter. It permits you to process an entire array using a single instruction.

REP - Repeat while ECX > 0
REPZ, REPE - Repeat while zero flag is set and ECX > 0
REPNZ, REPNE - Repeat while the zero flag is clear and ECX > 0.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

How would you copy a 10-byte string from string1 to string2?

A

The repeat prefix first tests ECX>0 before executing MOVSB instruction. ESI and EDI are automatically incremented when MOVSB repeats (this behavior is controlled by the CPU’s direction flag)

cld ;clear direction flag
mov esi, OFFSET string1 ; ESI points to source
mov edi, OFFSET string 2 ; EDI points to target
mov ecx, 10 ; set counter to 10
rep movesb ;move 10 bytes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

How does the direction flag work?

A

ALWAYS set the direction flag before using string primitive instructions!

CLD clears the direction flag (forward direction), increments ESI and EDI, goes from low to high addresses.

STD sets the direction flag (reverse direction), decrements ESI and EDI, going from high to low addresses.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

How do MOVSB, MOVSW, and MOVSD work?

A

MOVSB, MOVSW, and MOVSD copy data from the memory location pointed to by ESI to the memory location pointed to by EDI. The two registers are either incremented or decremented automatically (based on the value of the direction flag).

MOVSB - 1
MOVSW -2
MOVSD - 4

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

How would you copy 20 DWORD integers from source to target?

A

.data
source DWORD 20 DUP (0FFFFFFFFh)
target DWORD 20 DUP(?)

.code
cld ; direction = forward
mov ecx, LENGTHOF source ;set REP counter
mov esi, OFFSET source ; ESI points to source
mov edi, OFFSET target ; EDI points to target
rep movsd ;copy doublewords

After the array is copied, ESI and EDI point one position (4 bytes) beyond the end of each array.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

How do CMPSB, CMPSW, and CMPSD work?

A

Each compare a memory operand pointed to by ESI to a memory operand pointed to by EDI.

CMPSB - compare bytes
CMPSW - compare words
CMPSD - compare doublewords

You can use repeat prefixes, and the direction flag will determine whether ESI increments or decrements.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

How would you using CMPSD to jmp to L1 if source has a larger value than target?

A

.data
source DWORD 1234h
target DWORD 5678h

.code
mov esi, OFFSET source
mov edi, OFFSET target
cmpsd  ;compare doublewords
ja L1   ;jmp if source > target
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

How would you compare multiple DWORDS?

A

The REPE prefix repeats the comparing (incrementing ESI and EDI until ECX equals zero or a pair of doublewords are different).

.data
source DWORD 1234h
target DWORD 5678h

.code
mov esi, OFFSET source
mov edi, OFFSET target
cld
mov ecx, LENGTHOF source ; repetition counter
repe cmpsd   ; repeat while equal
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

How to the SCASB, SCASW, and SCASD work?

A

SCASB, SCASW, and SCAWD compare a value in AL/AX/EAX to a byte, word, or doubleword addressed by EDI.

You can use these to search for a value in a string or array. Combined with REPE/REPZ, it’s scanned while ECX>0 and the value in AL/AX/EAX matches each subsequent value in memory.

Combined with REPNE, it scans until either AL/AX/EAX match a value in memory or ECX = 0.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

How would you scan the string alpha for the letter F?

A

If the letter is found, EDI points one position beyond the matching character. If the letter is not found, JNZ exits.

.data
alpha BYTE “ABCEDFGH”,0

.code
mov edi, OFFSET alpha ;EDI points to the string
mov al, 'F' ;search for the letter F
mov ecx, LENTHOF alpha ;set the search count
cld
repne scasb ;repeat while not equal
jnz quit
dec edi ; found: back up EDI
25
Q

What do STOSB, STOSW, and STOSB do?

A

STOSB, STOSW, and STOSB store the contents of AL/AX/EAX respectively, in memory at offset pointed to by EDI, which increments or decrements (based on direction flag). When used with REP prefix, you can fill all elements of a string or array with a single value.

.data
count = 100
string1 BYTE Count DUP(?)

.code
mov al, 0FFh
mov edi, OFFSET string1 ;EDI points to target
mov ecx, Count  ; character count
cld  ; direction = forward
rep stosb  ;fill with contents of AL
26
Q

What do LODSB, LODSW, and LODSD do?

A

LODSB, LODSW, and LODSD load a byte or word from memory at AL/AX/EAX respectively. ESI is decremented or incremented (based on direction flag).

The REP prefix is rarely used with LODS because each new value loaded into the accumulator overwrites its previous contents. Instead, LODS is used to load a single value. In essence, it substitutes for the two instructions below:

mov al, [esi] ; move byte into AL
inc esi ;point to next byte

27
Q

How would you use LODSD and STOSD to multiply each element of a DWORD array by a constant value?

A

.data
array DWORD 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
multiplier DWORD 10

.code
main PROC
  cld
  mov esi, OFFSET array ;source 
  mov edi, esi ;destination
  mov ecx, LENGTHOF array ;loop
L1: lodsd   ;load [ESI] into EAX
  mul multiplier ; multiply by value
  stosd   ;store EAX into [EDI]
  loop L1
  exit
main ENDP
END main
28
Q

In reference to string parameters, which 32-bit register is known as the accumulator?

A

EAX

29
Q

Which instruction compares a 32-bit integer in the accumulator to the contents of memory, pointed to by EDI?

A

SCASD - scans the string and compares it to memory, as opposed to CMPSD, which compares two strings to each other.

It’s used to search for a particular string within a string.

30
Q

Which index register is used by the STOSD instruction?

A

EDI

31
Q

Which instruction copies data from the memory location addressed by ESI into AX?

A

LODSW - this loads from memory into a register.

32
Q

What does the REPZ prefix do for a CMPSB instruction?

A

REPZ means to repeat while they are the same, so when combined with CMPSB (which compares two strings), you’d keep iterating until a letter was different.

33
Q

What are the two methods of arranging the rows and columns of a 2D array?

A
  1. row-major order (most common) - the first row appears at the beginning of the memory block, and the last element of the first row is followed by the first element of the second row.
  2. column-major order - elements in the first column appear at the beginning of the memory block. The last element in the first column is followed in memory by the first element of the second column.
34
Q

What are base-index operands?

A

You produce an offset address by adding the values of ANY general purpose registers (base and index).

.data
array WORD 1000h, 2000h, 3000h

.code
mov ebx, OFFSET array
mov esi, 2
mov ax, [ebx+esi] ;AX = 2000h
mov edi, OFFSET array
mov ecx, 4
mov ax, [edi + ecx] ; AX = 3000h
mov ebp, OFFSET array
mov esi, 0
mov ax [ebp+esi] ; AX = 1000h
35
Q

How can you create a Rowsize variable to keep track of your 2D matrix using base-index operand?

A

typeB BYTE 10h, 20h, 30h, 40h, 50h
Rowsize = ($-tableB)
BYTE 60h, 70h, 80h, 90h, 0A0h
BYTE 0B0h, 0C0h, 0D0h, 0E0h, 0F0h

Find the size of the first row (and every row). In EBX, use the table’s offset plus (rowsize * row_index) for the row offset, and set ESI to the column index.

row_index = 1
column_index = 2
mov ebx, OFFSET tableB
add ebx, Rowsize * row_index
mov esi, column_index
mov al, [ebx+esi] ;AL = 80h
36
Q

What are base-index-displacement operands?

A

They combine a displacement, base register, index register, and an optional scale factor to produce an effective address.

[base+index+displacement]
displacement[base+index]

Displacement can be the name of a variable or a constant expression. In 32-bit mode, any general purpose 32-bit registers may be used for the base and index.

For 2D arrrays, the displacement can be an array name, the base operand can hold the row offset, and the index operand can hold the column offset.

37
Q

What is an example of base-index-displacement accessing element typeD[1][2] in a 2D matrix?

A 
.data
typeD DWORD 10h, 20h, 30h, 40h, 50h
Rowsize = ($-tableB)
DWORD 60h, 70h, 80h, 90h, 0A0h
DWORD 0B0h, 0C0h, 0D0h, 0E0h, 0F0h

.code
mov ebx, Rowsize
mov esi, 2 ;column index
mov eax, tableD[ebx + esi*TYPE tableD]

38
Q

In 32-bit mode, which registers can be used in a base-index operand?

A

All the general purpose 32-bit registers.

39
Q

Suppose a 2D array of doublewords has 3 logical rows and 4 logical columns. If ESI is used as the row index, what value is added to ESI to move from one row to the next?

A

Since the size of a row is 4*4 = 16, you’d add 16 to get to the next row.

40
Q

In 32-bit mode, should you use EBP to address an array?

A

No. EBP should be reserved as a base pointer for the current procedure’s stack frame.

41
Q

How do you convert infix to postfix?

A

Fully parenthesize infix, using operator precedence. Then, parse the expression left to right, constructing a binary tree.

Left parenthesis, go left.
Operand, insert.
Operator, go up, insert, and go right
Right parenthesis - go up

A post order traversal (left, right, root) gives postfix expression.

42
Q

How do you convert from postfix to infix?

A

Diagram the expression as a binary tree, and then do in-order traversal (left, root, right).

43
Q

How do you evaluate RPN expressions?

A

Parse expressions left to right, creating a stack of operands.

Operand - push onto stack
Operator - pop 2 operands, perform operation, push result onto stack

Single value remaining on stack is value of expression.

44
Q

What are the main features of the IA-32 floating point processor (FPU)?

A
  1. Runs in parallel with integer processor. The circuits are designed for fast computation (e.g with 3D graphics).
  2. Registers implemented as “pushdown” stack.
  3. Usually programmed as a 0-address machine
  4. CPU/FPU exchange data through memory.
45
Q

How is the FPU programmed?

A

As a “pushdown” stack. If you push more than 8 values, the “bottom” of the stack is lost!!

Operations are defined for the “top” one or two registers, although registers can be referenced by name - ST(x).

ST = ST(0) = top of stack. The registers are 80-bit registers (the left most is sign bit, next 15 are exponent, and 64 left are normalized mantissa.

Be sure to use FINIT to initialize the FPU register stack before any other FPU instructions!

46
Q

What is the format for floating point unit instructions?

A

OPCODE
OPCODE destination
OPCODE destination, source

One register MUST be ST(0).

47
Q

What are the add/subtract instructions for floating point numbers?

A

Generally, they are the same except they start with ‘F’ - FSUB, FADD, etc.

However, to specify that a value is being used with an integer, use the special instructions that start with ‘FI’ - FISUB, FIADD, etc.

48
Q

What does FLD MemVar do?

A

It pushes all the values in the registers down by one and loads ST(0) with MemVar.

49
Q

What does FST MemVar do?

A

It moves the top of the stack to memory, but leaves the result in ST(0).

50
Q

What does FSTP MemVar do?

A

It’s like FST, but it also pops the top of the stack to memory, moving all the registers up by one.

51
Q

How would FADD affect the floating point register stack?

A

FADD would pop the top two numbers, add them together, and then push the result onto the top of the stack.

52
Q

How would you create a floating point program for X+(Z*Y)?

A

.data
varX REAL10 2.5
varY REAL10 -1.8
varZ REAL10 ?

.code
FINIT
FLD varX ;push X
FLD varY ;push Y
FLD varZ ;push Z
FMUL ;Z*Y onto top of stack
FADD ;adds X to Z*Y
FSTP result ; result = X+Z*Y
53
Q

How would you calculate the dot product for floating point?

A

array REAL10 6.0, 2.0, 4.5, 3.2

main PROC
  finit
  fld array ;push 6.0
  fld array+10 ;push 2.0
  fmul  ;ST(0) = 6*2
  fld array+20 ;push 4.5
  fld array+30 ;push 3.2
  fmul ;ST(0) = 4.5*3.2
  fadd ;ST(0) = ST(0) + ST(1)
  fstp dotProduct ;pop stack into memory
  exit
main ENDP
END main
54
Q

How do you read and write floats using the Irvine Library?

A

ReadFloat - gets keyboard input into ST(0)

WriteFloat - displays ST(0) contents in floating point format

55
Q

What are the methods for accessing specific array elements?

A
  1. Indexed
  2. Register indirect
  3. Based indexed
56
Q

What is indexed addressing?

A

The array name, with the “distance” to element in a register. (used with globally declared arrays)

mov edi, 0
mov list[edi]], eax ;list[0]
add edi, 4
mov list[edi], ebx ;list[1]

57
Q

What is register indirect addressing?

A

The actual address of the array element is in the register (used when list is passed by reference).

mov esi, [ebp+8]
mov eax, [esi]   ;list[0] into eax
add esi, 4
add eax, [esi]   ;add list[1]
add esi, 16
mov [esi], eax   ;move sum to list[5]
58
Q

What is base-indexed addressing?

A

Starting address is in one register, and the offset is in another.

mov edx, [ebp+8]
mov ecx, 20
mov eax, [edx+ecx]  ;list[5] to eax
mov ebx, 4
add eax, [edx+ebx]   ;add list[1]
mov[edx+ecx], eax  ;send to list[5]

Computer Architecture/Assembly (11 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions