04/02/97

Numbering Systems

3 systems we will use in this class:

• Decimal
• Binary
• Hexidecimal

There is a difference between a numbers representation and the amount that it represents. Ex: 1010 = 10 in binary, 1,010 in decimal. 10₁₆ = 16 in decimal, not 10.

Examples:

123₁₀ = 1 * 10² + 2 * 10¹ + 3 * 10⁰ = 100 + 20 + 3 = 123

1010₂ = 1 * 2³ + 0 * 2² + 1 * 2¹ + 0 * 2⁰ = 8 + 0 + 2 + 0 = 10

Problem with binary representation: Have to write a lot of digits to represent integers. Ex: 101010111011111 ~= 30,000

Solution: It is easy to convert between binary and hexidecimal representations. Memorize the following chart:

Now you can quite easily convert from binary to hexidecimal numbers:

1010	1011	1011	1111	Divide the number into 4 bit nibbles
A	B	B	F	Conver each nibble into hexidecimal according to the chart

Conventions to Follow When Writing Decimal Numbers:

If we were to write 10256781056, it would be difficult to look at the number and right away tell if it were 100 million, 1 billion, 10 billion, etc. However, if we separate the number into triples with commas, as in 10,256,781,056, it is much easier to read and tell that the number is 10 billion... Likewise, when writing binary numbers, separate the digits into 4-bit nibbles, ex: 10111011 = 1011 1011. This way is much easier to read (as well as convert quickly to hexidecimal).

With n bits, we can represent 2ⁿ different values. As a convention, those values will be all integers on the range from 0 -> 2ⁿ - 1. Some common examples are:

Bit number 7 is the H.O. (High Order) bit, also called the most significant bit (MSB). Bit number 0 is the L.O. (Low Order) bit, also called the least significant bit (LSB). Likewise, a word can be divided in the H.O. and L.O. bytes (bits 15-8, and 7-0, respectively). It also follows that a dword can be divided into H.O. and L.O. words (bits 31-16, and 15-0, respectively).

04/04/97

Number representation systems

04/07/97

Shifts and Rotates

• Shifts
  • Left: Move all bits to the left one space. The H.O. bit is lost (actually stored in the flags) and a zero (0) is stored in the L.O. bit.
  • Right: Same as left, except the L.O. bit is lost and a zero is shifted into the H.O. bit.
  • Interesting points about shifts: A Shift-left (SHL) is the equivalent of multiplication by 2. A Shift-right (SHR) is the same as division by 2. In general, shifting to the left i times is the same as multiplying the original value by 2 ⁱ times. Using these operations instead of DIV & MUL is much faster! However, it should be noted that these shifts only work for unsigned values. Here's an example:

    1000 0000	-128
    0100 0000	SHR by one digit, the result is +64

    In order to use shifts on signed values, you must use an arithmetic shift.
  • Arithmetic Shifts: Same as regular shifts, except in Shift-right, the value of the L.O. bit is still lost, but the value of the H.O. bit is copied back into the H.O. bit. In C++, the shift operator (>>) performs an arithmetic shift.
• Rotates
  • Left: all of the bits are shifted to the left one bit, except instead of shifting in a zero and losing the H.O. bit, the H.O. bit is shifted into the L.O. bit.
  • Right: all bits shifted right, and the L.O. bit is shifted into the H.O. bit.
• What can all of this be used for?
  • These can be combined with masks to manipulate values as needed. Here's an example: Suppose that you are designing software to manipulate a hardware device where you need to read off four bits from an eight bit value, where the bits you want to read are in the pattern B = x1x2x0x3, where the x's are arbitrary values and the numbers are the bit positions that you want to read. You want to store those bit positions in a value A = xxxx3201. How will you do this?

    ((B SHL 3) AND 1000b) OR	Shift the 3 bit into the third value and mask off all the other bits
    ((B SHR 2) AND 101b) OR	Shift the value right 2 so that the 2 and 0 bits are in the proper place, then mask off all the other values
    ((B ROL 3) AND 10b)	Now shift the 1 bit into the proper place and mask it

  • More places where you may want to use bit manipulation:
    • ASCII character set: 'A' - 'Z' and 'a' - 'z' differ only by bit number 5. Therefore, to convert between upper and lower case, just flip bit number 5. '0' - '9' = 30h - 39h. To convert from ASCII to decimal digits, just subtract 30h. 'A' - 'Z' = 41h - 5Ah. Subtract 40h, and you get 1 - 26.

Memory

04/09/97

Computer architecture continued...

04/11/97

Quick disucssion on memory and CPU clock speed and relation to overall system performance:

• Basically, the CPU can only function as quickly as the memory does. Most of today's memory operates at ~ 15 MHz. Regardless of how fast the processor is operating (25 MHz 386, or a 200 MHz Pentium), it can really only operate as fast as the memory, because a majority of those cycles will be wasted on wait states until the memory returns the required data. The example given to explain this phenomenon is that of a quarter-mile drag race between a Volkswagon (the 386) and a Ferrari (the Pentium), where there is a 25 mile per hour speed limit (and neither driver breaks the law). The Ferrari will accelerate to 25 much faster, but in the end, will only win by the difference in the time it took to get up to 25 MPH. This small gain in speed does not justify the price between the Ferrari and the Volkswagon (or the 386 and the Pentium!)
• However, the limitation of the memory can be overcome by inserting a cache, an extremely fast memory that will provide the required data in 1 clock cycle, so that no wait states need to be inserted. The drag race model is now changed to represent a race where there is no speed limit, but the race can only be completed in a certain amount of time. This way, the Ferrari (Pentium) can drive around in circles at 200 MPH all he wants, but will still get to the finish line at the same time as the Volkswagon. This is how a Pentium goes much faster than a 386, but is still limited by the speed (or lack thereof) of the memory.
• The cache takes advantage of the principle of Locality of Reference to feed data into the cache that has a good chance of being needed. There are two types:
  • Temporal Locality: Referenced data has a good chance of being needed again soon (due to loops in programs).
  • Spacial Locality: For some data referenced, other data that is close to that data in memory (either before or after) is likely to be accessed soon (due to sequential execution of instructions in programs).

Segments continued...
Segmented Addresses - Take the format seg:offset, where seg is 16 bits, allowing up to 65,535 segments, and offset is:

• 16 bits on the 8086 - 80286 : Allows 64K segments
• 32 bits on the 80386 and higher : Allows 4 GB segments

Consider the following HLL code fragment:
int i, j
i = 100
How will these instructions be represented in assembly? The compiler will create a symbol table where the label will be stored along with it's address in memory.

name	address
i	1000h
j	1004h

So, if we want to set i to 100, then the instruction will be MOV DS:[1000h], 100.

How does the PC access memory?
The MOV instruction is the primary way to access memory. It takes the following form:
MOV dest, src
Where dest and src must take one of the following forms:

dest	src
reg	reg/mem
reg/mem	reg
reg/mem	constant

Some points to note about the MOV instruction:

• There are no memory to memory moves! Therefore, if you want to do something like a = b, you must use a register
  MOV AX, b
  MOV a, AX
  
• The size of the operands must be the same.

Addressing Modes on the 8086
There are 17 different addressing modes on the 8086. On the 80386 and above, there are something like 1000! You will not be required to know the 80386 modes, but you must memorize the 17 8086 addressing modes.

• Direct/Displacement Only : Has a 1 byte instruction code and a 2 byte offset. By default, the data is assumed to be in the data segment. However, you can also specify to access data in a different segment. Examples:

  MOV AX, [1000h]	Moves data from DS:1000h into AX
  MOV AX, ES:[1000h]	Moves data from ES:1000h into AX

• Memory Dereference : Basically the same as dest = *src. The location to dereference must be in BX, DI, SI, or BP. The first three default into the data segement, while BP defaults into the stack segment. Examples:

  MOV AX, [BX]	Suppose the value in BX is 1000h, move the data from DS:[1000h] into AX
  MOV AX, [BP]	Suppose tha value in BP is 1000h, move the data from SS:[1000h] into AX

04/14/97

Addressing modes continued...

• MOV reg, disp
• MOV reg, [bx|si|di|bp] : Move value pointed at by bx|si|di|bp into reg.
• MOV reg, [bx|si|di|bp + disp] : The sum of bx|si|di|bp and displacement is used to point at the value in memory to load into reg.
• MOV reg, [bx|bp + si|di] : Adds to registers together, sum is offset into either data segment or stack segment, depending if bx or bp is used, respectively.
• MOV reg, [bx|bp + si|di + disp] : The two regsiters and the displacement are added to form the pointer into memory.

These forms make up the 17 addressing modes on the 8086. Here are some interesting points to note:

• MOV [bx], i : This is not a valid instruction because it is a memory-to-memory move ([bx] is a memory addressing mode)
• The MOV reg, [bx|si|di|bp + disp] mode is often used to index into an array, where the base address of the array is loaded into disp. Here's an example:
  To set A[i] = 0:
  MOV BX, i
  MOV AL, 0
  MOV [BX + A], AL
  

  Notice, a sematically equivalent way to do the last command would be MOV A[BX], AL, which looks more like a High Level Langauge array access.

• Only valid registers to use in addressing modes are bx, si, di, and bp
• Trick for memorizing memory addressing modes:

  disp

  bx bp

  si di

  Take 0 or 1 item from each column.

Assembly Langauge Programming

Shell.asm - template file for writing programs. Contains four segments directives to use for programming:

cseg	Code segment : all machine instructions go here
dseg	Data segment : declare variables here
sseg	Stack segment : where values go when you use push and pop; you don't need to worry about this segment.
zzzzzzseg	Heap where data is allocated dynamically with malloc and free

Point to Note: it is the programs responsibility to make sure that the CS register points at the code segment and that the DS register points at the data segment. However, you won't need to worry about this either, because it is already done for you in the Shell.asm file.
Here's another point: For each of your programs, make a copy of the Shell.asm file and delete the comments that tell you where to put things. These are only for your benefit, and are not reasonable comments. Remove them.

Segment definitions in Assembly Dseg

Desg	segment	para	public	'data'
Name of segment	Identifier	Align the segment on 16-bit boundaries	Other modules can see the segment	For identifying this segment when there are other segments with the same name.
ends

Variables in the Dseg are global.

Variable declarations in Assembly

 name		type	value(s) 

• Do not indent declarations. Start them in column 1.
• Start the type field in column 17 (2 tab stops)
• Start the value field in column 25 (3rd tab stop)
• Variable names are the same as in C (letter followed by letters, numbers, and underscores).
• Types are: byte, sbyte, word, sword, dword, sdword
• If you would rather use C-like types (char, integer, float), use the MASM typedef directive:
  

  
  char 		typedef byte
  
  integer		typedef	sword
  
  

• INT is a reserved word in MASM (for interrupt).
• To initialize a value to undefined, type ? in the value field. Example:
  

  
  A		integer	?
  
  

04/16/97

Variable declarations continued...

integer		typedef	sword

char		typedef byte

longint		typedef sdword



Dseg		segment	...

i		integer	0

j		integer 10

a		char	'A'

b		longint ?

Dseg		ends

mov ax, i <==> mov ax, ds:[0] 

mov cx, j <==> mov cx, ds:[2] 



; The next two lines do ax = i



mov bx, 0 

mov ax, [bx] 		

Array declarations

Dseg		segment

i		integer	0,1,2,3

Dseg		ends

mov	bx, 0

mov	ax, [bx+i]		; ax = i[0]

mov	bx, 2	

mov	cx, [bx+i]		; cx = i[1]

• If you try to load i[1] byt loading bx with 1, it will not work because you will get the H.O. byte of i[0] and and the L.O. byte of i[1]. You must load bx with the index (1) times the size of the element (2 bytes). In general: a[index] = BaseAddress(A) + (index * size_of_element)
  

Characters

Dseg		segment

A		char	'R','A','N','D','Y'

B		char	'RANDY', 0

C		char	'Randy', ' Hyde', 0

D		char	'Randy Hyde',0

E		char	'Randy'

		char	' Hyde'

		byte	0

Dseg		ends

In this data segment declaration, A & B are equivalent, as are C, D, and E.

This leads to new way to declare arrays:

Dseg		segment

A		char	64 dup(?)

Dseg		ends

04/18/97

Arrays

Consider the following data segment declarations:

Dseg		segment	...

A		word	64 dup(?)

B		word	64 dup(0,1,2,3)

S		byte	256 dup('stack')

D		word	4 dup(4 dup(?))

Dseg		ends

D		word	16 dup(?)

Row-Major and Column-Major Ordering

Suppose you have a two-dimensional array B declared as follows:

B		word	4 dup(4 dup(?))

• Row Major Ordering: Travel across each row of the array and put each item in sequentially in memory.
• Column Major Ordering: Basically the same as Row Major, except that you traverse down the columns.

Here are formulas to use for both schemes, supposing you want to access B[y,x]

• Row Major: Base(B) + [(Y * row_size) + X] * element_size
• Col Major: Base(B) + [(X * col_size) + Y] * element_size

mov	bx, i

imul 	bx, 4		; multiply by rowsize

add	bx, j

add	bx, bx		; multiply by element size (2)

mov	ax, B[bx]

04/21/97

Structures and Pointers

A structure in assembly language is basically the same as a C++ class. For example:

Declaring Structures
In C++:	In Assembly:
Struct { int i; int j; float f; } MyStruct;	MyStruct struct i sword ? j sword ? f real4 ? MyStruct ends
Using Structures
MyStruct m; m.i = ... m.j = ... m.f = ...	m MyStruct {} mov m.i, ... mov m.j, ... mov m.f, ...

Array of structs:
Declaring:

x		MyStruct 10dup({})

mov	bx, index

imul	bx, 8		; multiply by the size of the struct

mov	x[bx].i, 0	

imul	bx, sizeof(MyStruct)

• You don't have to compute the size of the struct (which can be complicated for large structres)
• The computed size of the struct is automatically changed by the assembler if you add or delete fields, so you don't have to go through your program and change them all by hand.

Pointers

2 types:

• Far: 32-bits, consists of the segment and offset within that segment.
• Near: 16-bits, just an offset in a segment.

Declaring pointers: (in data segment)

I		word	?

myPtr		dword	I 		; declare a far pointer to I

myNPtr		word	I		; initialize myNPtr with address of I

mov	ES, myPtr+2			

mov	BX, myPtr

mov	AX, ES:[BX]			; mov ax, I

 les	bx, myPtr 

l*s	reg, 32-bit value

Problems with far pointers: They are larger and instructions used to access them are slow.

Problems with near pointers: Only holds the offset, so you have to know what segment the data is in. However, they are smaller and you can use the mov instruction to access them, instead of l*s (which is much slower).

Physical address: Suppose you have a seg:offset address, xxxx:yyyy, how do you compute the physical address in memory where it will be mapped?

xxxx0	Append a zero to the segment
+yyyy	Add the offset
ppppp	Result is physical address in memory

Given this method, where would the following addresses be mapped? 100:1000 & 200:0.

100:1000	200:0
1000	2000	Append zero to segment
1000	0000	Add in offset
2000	2000	Physical address

Both of these addresses map to the same spot in memory. If we were to compare pointers to each of these two values, the program would say they are the same, when really they are different. In reality, for any possible address, there are 16 possible forms to access it. The solution: Normalized Addresses, of the form xxxx:y. Insert a colon between the least significant digit and the one before it.

04/23/97

Delcaring Constants in Assembly:

RowSize=4

ColSize=4

; in data segment...

MatrixOne	word	RowSize dup(ColSize dup(?)) ; creates 4 x 4 matrix

2 attributes of a variable in memory: value and address. Example: consider the following data segment declaration:

I	word	10

Ptr	dword 	I

J	word	20

lea	ax, J

mov	Ptr, ax	

mov	Ptr+2, ds	

lea	ax, J

mov	word ptr Ptr, ax

mov	word ptr Ptr+2, ds

les	bx, Ptr

mov	es:[bx], ax		; Ptr now points at J (which was stored in ax)

lea	ax, i

int *pi;

int i;

pi=&i;	

mov	[bx], const

mov	word ptr [bx], const

Dynamic memory allocation:

malloc: routine will allocate memory on the stack and return a pointer to it in es:di. The amount of bytes allocated is specified by the value in the cx register. Example: consider the following declaration of a 64 x 16 matrix of words in the data segment:

 

A	word	64 dup(16 dup(?))

mov	cx, 64*16*2		; cx now holds number of byte to allocate 

				; (rowsize * colsize * itemsize)

malloc				; allocate memory on heap

mov	word ptr A, di		; set A equal to the pointer to the newly

mov	word ptr A+2, es	; allocated memory

; the following 4 instruction compute the index using row-major ordering

mov	bx, y			

imul	bx, 16

add	bx, x

add	bx, bx

les	di, A			; load es:di with the base address of the

				; array (previosly stored in A)

mov	es:[di+bx], ax		; use base + offset addressing mode to 

				; access array element.

Accessing fields in structures through pointers:

Suppose you have the following structure, and pointer to that structrue, declared in the data segment:

S		struct

i		word	?

j		word 	?

...

S		ends

MyStruct	S	{}

SPtr		dword	MyStruct

les	di, SPtr

mov	ax, es:[di].i

mov	ax, es:[di].S.i 	

04/25/97

Introduction to the UCR Standard Library

04/28/97

Stack Operations

push mem/reg	sp = sp-2 ss:[sp] = mem/reg
pop mem/reg	mem/reg = ss:[sp] sp = sp+2

Points to note about stack:

• As you push values onto the stack, it grows downward in memory.
• Stack pointer keeps track of where the stack is in the stack segment.
• Why use stack? Store values. Consider the following example:

  
  push	ax
  
  ; series of instructions affecting ax
  
  pop 	ax			; restores original value of ax
  
  

• You must pop registers in the opposite order that they were pushed in. Example:

  
  push 	ax
  
  push	bx
  
  push	cx
  
  push	dx
  
  ...
  
  pop	ax
  
  pop	bx
  
  pop	cx
  
  pop	dx
  
  

  In this example, ax will get the old value of dx, bx will get cx's old value, and so on.
• The stack is a LIFO data structure - Last In, First Out.
• Functions and Procedures should preserve the value of registers. Stack is the main way this is achieved. At the beginning of such a routine, push all of the registers that the routine will be using to complete it's computations. Right before returning, pop all the registers back off the stack (in reverse order) to restore their original values.
• Call and return also use the stack. Consider the following:

  
  myputs	proc	near
  
  ...
  
  	ret
  
  myputs	endp
  
  ...
  
  call 	myputs
  
  

  When the call myputs instruction is executed, the location of the next instruction to execute (stored in the IP register) is pushed onto the stack. Then, control is transfered over to myputs. When myputs is done, the ret instruction will pop IP off the stack, and execute that instruction (the next instruction after the call instruction) next.

Here's the code for myputs:

; assumes es:di points to a string to print 

myputs		proc	near

		push	di		; save di, since we'll be changing it's value

whilelp:	mov	al, es:[di]

		cmp	al, 0		; check for zero byte (end of string)

		je	done

		putc			; print character in al

		inc 	di		

		jmp	whilelp

done:		pop	di		; restore di's old value

		ret

myputs		endp

• Pushing values and forgetting to pop them
• Popping values you havn't pushed
• Popping values in the same order you pushed them (should be reverse order)

Here is the code for getu, which reads an unsigned integer from the stdin.

; Assumes:

; In data segment ... 

; Input		byte	(128dup(?))

geti		proc	near

		push 	es

		push	di

BadNum:		lesi	Input		; es:di points at Input string

		gets			; reads string into es:di (Input)

SkipSpcs:	cmp	byte ptr es:[di], ' '

		jne	notspace

		inc	di

		jmp	SkipSpcs

NotSpace:	cmp	byte ptr es:[di], '0'

		jb	RetryMsg

		cmp	byte ptr es:[di], '9'

		jna	GoodNum

RetryMsg:	print

		byte "Invalid Integer, try again.",cr,lf,0

		jmp	BadNum

GoodNum:	atou			; convert string to unsigned int

		pop	di

		pop	es

		ret

getu		endp

04/30/97

Text Equates Text Equates (defined using the testequ directive) are used to literally substitute one substring for another. You define text equates in the following manner:

name		textequ	

geti		textequ	

Parameter Passing

There are many different methods of passing parameters and places of passing them. The main ways we will study is pass by reference & pass by value. The main place we'll be passing our parameters is on the stack. Heres an example:

; ReadArray[i][j] - assumes pointer to the array to read values into 

;                   passed as parameter in es:di

ReadArray	proc	near

		getu			; returns unsigned int in ax

		mov	bx, i

		imul	bx, numcols	 

		add	bx, j

		add	bx, bx	

		mov 	es:[di+bx], ax

ReadArray	endp

		lesi	A1		; es:di holds base address of A1

		ReadArray	

		lesi	A2		; es:di holds base address of A2

		ReadArray