CPSC 355 - Leonard Manzara - Awesome professor Notes up until Stack PDF

Preview

Summary

Leonard Manzara - Awesome professor
Notes up until Stack...

Description

Binary Numbers and Integer Representations Binary Numbers - Base 2 number - Use only the binary digi ts (b  its ) 0 and 1 -

Easy to encode on a computer, since only 2 states need to be distinguished (on/off) - Using voltages (example): - 0: 0 V - 1: 3.3 V - Using paper tape or cards: - 0: unpunched - 1: punched

-

Binary numbers are encoded using 1 or more bits in combination - I.e. 101 binary is decimal 5 - An N-bit register can hond 2^N bit patterns - A 4-bit register can hold 16 distinct bit patterns (4^2 = 16) - 0000, 0001, 0010, 0011....1111

Unsigned Integers - Encoded using binary numbers - Range: 0 to 2N -1, N = number of bits in register - E.g. 8-bit register: ranges from 0 to 255 - In binary, from 00000000 to 11111111 (255) Signed Integers - Are most commonly encoded using the two’s complement  representation - Range: -2N-1  to +2N-1  -1 - 4-bits: -8 to +7 - 8-bits: -128 to +127 - 16-bits: -32,768 to 32,767 - 32-bits: -2,147,483,648 to 2,147,483,647 - 64-bits: -263  to 263  -1 -

Negating a number is done by: - Take one’s complement - Toggle all 0’s to 1’s, and vice versa - Adding 1 to the result - Eg: find the bit pattern for -5 in a 4-bit register - +5 = 0101 - One’s complement : 1010 - Add 1: 1011

-

Negating a negative number: -5 = 1011 One’s complement : 0100 Add 1: 0101

-

All positive numbers will have a 0 in left-most bit - All negative numbers will have a 1 in left-most bit - Called the signed bit

-

The sign-magnitude  and one’s complement  representations are also possible - But awkward to handle in hardware - Have 2 zeros: +0 and -0 - Rarely used today (inefficient)

Hexadecimal Numbers - Base 16 numbers - Use digits 0,1,3,6....9,A,B,C,D,E,F - Used as a shorthand for denoting bit patterns - Each hex digit corresponds to a particular 4-bit pattern: 0 0000 1 0001 2 0010 ............... 9 1001 A 1010 B 1011 C 1100 D 1101 E 1110 F 1111 -

E.g: 0xF5A F 1111 5 0101 A 1010 Representing 12 bits in a compact way

Octal Numbers - Are base 8 numbers - Use digits 0-7 - Shorthand for denoting bit patterns - Each digit corresponds to a 3-bit pattern - Eg: 0756 - 0: used to reference octal number - 7 111 - 5 101 - 6 110 Bitwise operations BItwise Logical Instructions ● Manipulate one or more bits within a register ● AND ○ Truth table: A b a and b 0 0 0 0 1 0 1 0 0 1 1 1 ● Form (64-bit) : and Xd, Xn, Xm ○ Eg: mov x19, 0xAA // 1010 1010 Mov x20, 0xf0 // 1111 0000 And x21, x19, x20 // 1010 0000 ○ Note the 0xF0 forms a bitmask ■ It “masks out” all bits except bits 4-7 ● 32--bit and immediate forms also exist ○ Eg: mov w19, 0x55 //0101 0101 And w19, w19, 0xF //0000 1111 //0000 0101 ● ands sets or clears N and Z flags according to the result(V and C always cleared) ○ Eg: test if bit 3 is set in x20 … ands x19, x20, 0x8 b.eq bitclear Bitset: … Bitclear: ... ●

tst is an alias for ands ○ Form(64-bit)p : tst Xn,Xm ○ Alias for: ands xzr, Xn, Xm

○

●

● ●

●

●

● ●

●

Eg:

… tst b.eq bitset: … bitclear: … Inclusive OR ○ Truth table: A b 0 0 1 0 0 1 1 1

x20, 0x8 bitclear

a or b 0 1 1 1

form(64 bit): orr Xd, Xn, Xm ○ 32 bit and immediate form also exist Eg: set bits 4 and 5 in x19 // set: make it 1, clear: make it 0 Mov x19, 0xAA // 1010 1010 Mov x20, 0x30 // 0011 0000 Orr x19, x19, x20 // 1011 1010 Mov is an alias of orr ○ Form: mov Xd, Xm ○ Alias for: orr Xd, Xzr, XM Exclusive OR ○ Truth table: A b a EOR b 0 0 0 1 0 1 0 1 1 1 1 0 form(64 bits) : eor Xd, Xn, X ○ 32 bit and immediate also exist Eg: toggle bits 0-3 in w20 Mov w20, 0x55 // 0101 0101 Eor w20, w20, 0xF0 // 0000 1111 // 0101 1010 Bit clear ○ Is actually AND NOT ○ Truth table: A b a and not b 0 0 0 1 0 1 0 1 0

● ●

1 1 0 form(64 bit): bic Xd, Xn, Xm ○ 32 bit also exist, immediate does not Eg: clear bits 2-5 … Mov x20, oxFF // 1111 1111 Mov x21, x3C // 0011 1100 Bic x20, x20, x21 // 1100 0011

Bitwise Logical Instructions - OR NOT - Truth Table: A B 0 0 0 1 1 0 1 1 -

OpCode Form (64 bit) - Orn Xd, Xn, Xm

-

NOT - Truth Table: A 1 0

A OR NOT B 1 0 1 1

NOT A 0 1

-

Implemented using mvn (move N  OT) Form (64 bit): mvn Xd, Xm Alias for: orn Xd, xzr, Xm

-

EOR NOT (or XOR) Truth table: A B A EOR NOT B 0 0 1 0 1 0 1 0 1 1 1 1 Form (64 bit): eon

Xd,

Xn,

Xm

Bitwise Shift Instructions Logical Shift Left - Form: lsl Xd, Xn, Xm - Xn: bit pattern to be shifted left - Xm: shift count (number to shift by) - 0 is shifted into rightmost bit Shifted our bits are lost LSL is quick way to do multiplication by a power of two - E.g. by 2n , where n is the shift count - 5*8 - mov x20, 5 //0000 0101 - mov x21, 3 //23 = 8 (shift count = 3) - lsl x19, x20, x21 //0010 1000 Logical Shift Right - Form: lsr Xd, Xn, Xm - 0 is shifted into leftmost bit LSR is quick way to do division by a power of two - Any Remainder is lost - E.g. 15/4 = 3 - mov x20, 15 //0000 1111 - mov x21, 2 //22 = 4 - lsr x19, x20, x21 //0000 0011 Does not work for negative signed integers - 32 bit form with immediate exist - 0 is inserted at bit 31 when using W operands Arithmetic Shift Right Form (64 bit): - Asr Xd, Xn, Xm - Xn: bit pattern to be shifted - Xm: shift count Sign bit is duplicated when shifting - Called sign extension ASR preserves the sign when dividing by a power of two - E.g. -8/2 = -4 mov x20, -8 //1111....1111 1000 mov x21, 1 //21 = 2 mov x19, x20, x21 //1111....1111 1100 32-bit and immediate forms exist - Bit 31 is the sign bit when using W operands

Rotate Right Form (64 bit): - ror Xd, Xn, Xm - Xn: bit pattern to be rotated - Xm: shift count - Bits shifted our on the right are inserted on the left

-

32 bit form uses bits 0-31 only

Sign/Zero Extend Operations - Signed Extend B  yte - Form (32-bit): sxtb Wd, Wn - Sign-extends bit 7 in Wn to bits 8-31 - E.g

-

-

-

-

mov

w20,

0xFF

sxtb E.g

w19,

w20

mov

w20,

0x7F

sxtb

w19,

w20

// 0000 ... 0000 1111 1111 ^sign bit // 1111 ... 1111 1111 1111

// 0000 ... 0000 0111 1111 ^sign bit // 0000 ... 0000 0111 1111

Signed Extend H  alfword - Form (32-bit): sxth Wd, Wn - Sign-extends bit 15 in Wn to bits 16-31 64-bit forms exist - E.g. sxth x19, w20 Signed Extend W  ord - (64-bit ONLY):sxtw Xd, Wn - Sign-Extends bit 31 to bits 32-63 Unsigned Extend B  yte - (32-bit ONLY):uxtb Wd, Wn - Zero-extends bits 8-31 - E.g. mov uxtb

w20, w19,

0xFF w20

//0000 ... 0000 1111 11111 //0000 ... 0000 1111 11111

-

Unsigned Extend H  alfword - (32-bit ONLY):uxth Wd, - Zero-extends bits 16-31

Wn

Readings and Exercises - P & H: Section 2.6 - ARMv8 Instruction Set Overview: - Section 5.4, subsections 2, 5, 7, 8 - Section 5.5, subsections 3, 4 Binary Arithmetic Modulus Arithmetic - Constraints numbers to the range 0 to M-1, where M is the modulus - CPUs normally do modulus arithmetic - Calculation results must fit into a fixed-size register - If n is the size in bits, them M  = 2n - E.g: M  is 16 for a 4-bit register (42 = 16) - Unsigned integers range from 0 to 15 (0000 to 1111) -

Any carry out is ignored when using ordinary arithmetic instructions E.g. 9 + 8 = 17 - But actually gives (9+8) mod  16 on a 4-bit CPU: 9: 1001 8: 1000 ----------------1 0001 ^^Carry our ignored

-

Instructions like adds or subs  do set the carry flag - Can be used to do extended precision arithmetic

Binary Addition -

Single bits can be added together using the following rules:

Carry in

a

b

Carry out

sum

0

0

0

0

0

0

0

1

0

1

0

1

0

0

1

0

1

1

1

0

1

0

0

0

1

1

0

1

1

0

1

1

0

1

0

1

1

1

1

1

A full adder  circuit implements these rules in hardware:

-

Multi-bit numbers can be summed together using a full adder for each bit:

Subtraction - Is done in the ALU by negating the subtrahend, and then adding - Reuses the addition circuitry, thus minimizing hardware complexity - 4-bit example: 7 - 5 = 7 + (-5) = 2 7 0111 +(-5) 1011 ---------------------------

1 0010 ^^ carry our ignored Signed Number Branching Conditions Signed branch instructions use the N, Z, V flags: (notes) -

The subs instruction (alias of cmp ) sets the flags using these rules (64-bit form): - N = (Xd == 1) - Will check the left most bit of a 64-bit register, if = 1, it is even - Z = (Xd == 0) - WIll check - V = ((Xn & ~Xm & ~Xd) | (~Xn & Xm & ~Xd)) - Overflow occurs when the sign bits for Xn, Xm, a  nd Xd  are: - 1 0 0, or 0 1 1 - 4-bit example: -8 - 5 is -13, which is out of range (the modulus result is 3)

-

1000 -01 0 1 same as: 0011 ^^ V set to 1, N to 0, Z to 0 -8 != 5, since Z == 0 -8 < 5, since N != V -8 -8, since Z == 0, && N == V - 0 >= -8, since N == V

0000 +1000 1000

Unsigned Arithmetic - Uses the same registers and hardware operations as signed arithmetic - However, one interprets the data as unsigned numbers - When adding a carry our (C = 1) indicates overflow 4-bit example: 15 + 1 15 + 1 = 16, which is not in range 1111 + 0001 1 0 0 0 0 Answer will be 0 (because of overflow) Unsigned Number Branching Conditions - Ignore N and V flags, since they have no meaning for unsigned integers:

Name

Meaning

C equivalent

Flags

eq

equal

==

Z == 1

ne

Not equal

!=

Z == 0

hi (unlike gt)

Unsigned higher

>

C == 1 && Z == 0

hs (unlike ge)

Unsigned higher or same

>=

C == 1

Lo (unlike lt)

Unsigned lower

<

C == 0

ls (unlike le)

Unsigned lower or same...