CPSC 213 Introduction to Computer Systems
Winter Session 2019, Term 2
Unit 1a — Jan 13
Memory and Numbers
1
Unit 1a Overview
‣ Reading
• Companion: 2.2.2
• Textbook: 2.1 – 2.3
‣ Learning Objectives … you should be able to …
• describe the relationship between bits, bytes, shorts, longs and quads
– using the names for these things in Java, C, and assembly
• determine whether an address is aligned to a given size
• translate between integers and values stored in memory for both big- and little- endian machines
• evaluate and write Java expressions using bitwise operators (&, |, <<, >>, and >>>)
• determine when sign extension is unwanted and how to eliminate it in Java
• evaluate and write C expressions that include type casting and the addressing operators (& and *)
• translate integer values by hand (no calculator) between binary and hexadecimal, subtract hexadecimal numbers and convert small numbers between binary and decimal
2
Question 0.3
class A {
static int s = 0;
int i;
A () {
s = s + 1;
i = s; }
}
class Main {
static A a0, a1;
public static void main(String[] args) {
a0 = new A();
a1 = new A();
a0 = a1;
a1.i = a1.i + 1;
out.printf (“a0.i=%d a1.i=%d\n”, a0.i, a1.i);
}
}
‣ What prints when main() executes?
(A) a0.i=0 a1.i=2 (D) a0.i=3 a1.i=3
(B) a0.i=1 a1.i=3 (E) none of the above (C) a0.i=2 a1.i=3
Draw a Picture
class A {
static int s = 0;
int i;
A () {
s = s + 1;
i = s; }
}
class Main {
static A a0, a1;
}
a0
a1
i 1
32
s
the class “A”
public static void main(String[] args) {
a0 = new A();
a1 = new A();
a0 = a1;
a1.i = a1.i + 1;
out.printf (“a0.i=%d a1.i=%d\n”, a0.i, a1.i);
}
i
0
0
2
1
2
1
In the Machine
a0
a1
i1
32
i
the class “A”
i
‣ All state is stored in a single, main memory • each byte has a unique numeric address
‣ Variable
• name for memory location that has an address, a size and a value
• some are allocated statically (compiler) and some dynamically (execution)
‣ Pointer (aka Reference)
• variable whose value is a memory addresses
0
2
1
Question 0.4
class B {
int val;
B (int val) {this.val = val;}
int add (B x, B y) {
this.val = this.val + x.val;
this.val = this.val + y.val;
return this.val;
}
public static void main (String[] args) {
B a = new B (4);
B b = a;
B c = a;
out.println (a.add (b, c));
}
}
‣ What prints when main() executes? (A) 4 (D) 16
(B) 8 (E) none of the above (C) 12
Draw a Picture
class B {
int val;
B (int val) {this.val = val;}
int add (B x, B y) {
this.val = this.val + x.val;
this.val = this.val + y.val;
return this.val;
}
public static void main (String[] args) {
B a = new B (4);
B b = a;
B c = a;
out.println (a.add (b, c));
}
}
a b c
this
val 14
8
8
4
6 x
y
In the Machine
a
b cy
‣ There is just one object
• allocated storage space in memory when “new” executes • object is “named” by its memory address — a number
‣ Pointer variables
• stored in memory too
• their value is the memory address of the object • every variable stores the same number
val 1
4
8
this 6x
A Simple Computing Machine
CPU
Address Data
Memory
‣ Memory
• stores data encoded as bits
• program instructions and state (variables, objects, etc.)
‣ CPU
• reads instruction and data from memory
• performs specified computation and writes result back to memory
‣ Example • C = A +B
• memory stores: add instruction, and variables A, B and C
• CPU reads instruction and values of A and B, adds values and writes result to C
9
Memory
an ADDRESS names each byte (0..big number)
Memory is a big bag of BYTEs
a BY TE (8 bits)
READ value of N BYTEs READ value of BYTE
starting at ADDRESS X with ADDRESS X
CPU
Memory
WRITE new values V0..N-1 into N BYTEs starting at ADDRESS X
10
Memory
Micron MT4C1024 128KB RAM, zeptobars.org
Memory
Micron MT4C1024 128KB RAM, zeptobars.org
Memory
Micron MT4C1024 128KB RAM, zeptobars.org
Memory Summary
‣ Naming
• unit of addressing is a byte (8 bits)
• every byte of memory has a unique address
• some machines have 32-bit memory addresses, some have 64
– our machine will have 32 ‣ Access
• lots of things are too big to fit in a single byte
– unsigned numbers > 255, signed numbers < -128 or > 127, most instructions, etc.
Memory
• CPU accesses memory in contiguous, power-of-two-size chunks of bytes
# bytes
1 2 4 8
# bits
C
Java Asm b byte
Integer Data Types by Size
8
char
byte
16
short
short
32
int
int
w word l long q quad
We will use only 32-bit integers
64
long
long
• address of a chunk is address of first byte
14
First, Numbers and Humans
01001011110100110010100111 ? ‣ Sometimes we are interested in integer value of chunk of bytes
• base 10 is natural for this
‣ Sometimes we are more interested in bits themselves
• memory addresses are big numbers that name power-of-two size things
• we do not usually care what the base-10 value of an address is • we’d like a power-of-two sized way to name addresses
‣ We might use base-2, binary
• a small 256-byte memory has addresses 02 to 111111112
• if you don’t have subscripts, 111111112 is written as 0b11111111 • but, as addresses get bigger, this is tedious
‣ Once we used base-8, octal
• 64-KB memory addresses go up to 11111111111111112 = 1777778 • if you don’t have subscripts, 1777778 is written as 0177777
• but, as addresses got bigger, this got tedious too
‣ Now we use base-16, hexadecimal
• 4-GB memory addresses go up to 377777777778 = ffffffff16
• if you don’t have subscripts, ffffffff16 is written as 0xffffffff 15
Binary ↔ Hex is Easy
01101010010101010000111010100011
How many bits in a hex “digit”, a nibble?
0110 1010 0101 0101 0000 1110 1010 0011
ConsiderONEnibbleatatime:8xi4 +4xi3 +2xi2 +1xi1
6a550ea3 0x6a550ea3
Its easy to see the value of each byte (i.e., two nibbles)
0x6a 0x55 0x0e 0xa3
16
Question 1a.1: Hexadecimal Notation
‣ Which of these statements is true
A. The Java constants 16 and 0x10 are exactly the same integer
B. 16 and 0x10 are different integers C. Neither
D. I don’t know
17
Subtracting Hex Numbers
‣ We use Hex for addresses
• while we don’t really care what their base-10 value is
• we sometimes compute the size of things by subtracting two addresses – and that will then be in decimal
‣ Subtracting in Hex 0x2000 – 0x1ff0 = ?
• you could convert both numbers to decimal, but that might be too hard
• you can subtract in hex
– carry is 0x10 == 16
– to subtract a..f digits convert to their decimal value
• or you can use two’s compliment addition
– negate a number of complimenting and incrementing it
• -x == !x + 1
– complimenting in hex is easy
• swap 1’s and 0’s
• need a quick switch to/from binary
1
0x1f00
-0x1ff0
———————
‣ Converting Hex to Decimal
• not too bad for small numbers … tedious for large ones
• 0xijkl = i*163 + j*162 + k*161 + l*160 0x10 == 18
0x2000
-0x1ff0
———————
0
!0x1ff0 == 0xffffe00f
-0x1ff0 == !0x1ff0 + 1
== 0xffffe010
0x2000 – 0x1ff0 == 0x2000 + 0xffffe010
== 0x10
1*16 + 0 == 16
1 0x1f00 -0x1ff0 ——————— 0 0010
Question 1a.2: Subtracting in Hex
‣ Object A is at address 0x10d4 and object B at 0x1110. They are stored contiguously in memory (i.e., they are adjacent to each other). How big is A?
A. 16 bytes
B. 48 bytes
C. 60 bytes
D. 80 bytes
E. You can’t tell for sure from the information given
19
Making Integers from Bytes
‣ Our first architectural decision
• assembling memory bytes into integers
Memory
We will use Big Endian
‣ Consider 4-byte memory word and 32-bit integer • it has memory addresses i, i+1, i+2, and i+3
• we’ll just say its “at address i and is 4 bytes long”
• e.g., the word at address 4 is in bytes 4, 5, 6 and 7.
‣ Big or Little Endian
• we could start addressing at the BIG END of the number
• or we could start at the LITTLE END (Intel)
Integer bits Integer bits
20
…
i
i+ 1
i+ 2
i+ 3
…
i
i+ 1
i+ 2
i+ 3
i+ 3
i+ 2
i+ 1
i
2
2
31 to 2
24
23 to 2 2
16
15 to 2 2
8
7 2
0 to 2
31 to 2
24
23 to 2 2
2
16
15 to 2
0 7 to 2
8
2
Question 1a.3: Endianness
‣ What is the Little-Endian integer value at address 4 below?
A. 0x1c04b673 B. 0xc1406b37 C. 0x73b6041c D. 0x376b40c1 E. none of these
Memory
Addr
0x0:
0x1:
0x2:
0x3:
0x4:
0x5:
0x6:
0x7:
Value
0xfe
0x32
0x87
0x9a
0x73
0xb6
0x04
0x1c
21
In Assignment: Endianness.java
public static void main (String[] args) {
Byte mem[] = new Byte[4];
try {
for (int i=0; i<4; i++)
mem [i] = Integer.valueOf (args[i], 16) .byteValue();
} catch (Exception e) {
}
int bi = bigEndianValue
int li = littleEndianValue (mem);
...
Load 4 byte values provided on “command line” into memory in sequence.
‣ Complete this program
• implement bigEndianValue and littleEndianValue
‣ Run in for various byte sequences
• four command-line arguments are for consecutive byte values, in hex
• for example typing the following at UNIX shell command line
address 0
address 3
- java Endianness 0 0 0 1
- java Endianness 1 0 0 0
- java Endianness ff ff ff ff
should print big-endian value of 1
should print little-endian value of 1
should print value of -1 for both
(mem);
22
Some addresses are better than others
‣ Address Alignment
• we could allow any number to address a 4-byte integer, e.g. ✗
* disallowed on many architectures
* allowed on Intel, but usually slower example ....
✔
e.g., a word contains exactly two complete shorts
• but, better for hardware is to require addresses be aligned - an address is aligned to size x if the address mod x is zero
‣
Alignment to power-of-two size
- smaller things always fit completely inside of bigger things
- address computations are achieved by shifting bits; e.g., array-element address from index
&a[i] == &a[0] + i*(s==2^j) == &a[0] + i << j 23
Advantages of Power-of-Two Alignment
‣ Memory Implementation Detail (simplified)
• memory is actually organized internally into larger chunks called blocks • lets say a block is 16 bytes
• every memory access, internally requires accessing one of these blocks • you’ll see in 313 that this relates to memory caches
‣ Anyway ...
• a CPU memory access looks like this
- Read/Write N bytes starting at address A
• the memory converts this to
- R/W N bytes starting at Oth byte of block B (O is the block offset and B is the block number) - blocks are numbered, such that block 0 contains addresses 0 .. 15
• how is this simplified IF
- N is a power of 2 and
- A is aligned (i.e., A mod N == 0)?
24
Question 1a.4: Alignment
‣ Which of the following statement (s) is (are) true?
A. the address 0x6 (1102) is aligned for addressing a short
B. the address 0x6 (1102) is aligned for addressing an int (i.e., 4-bytes)
C. the address 0x14 (101002) is aligned for addressing an int
D. the address 0x14 (101002) is aligned for addressing a long (i.e., 8- bytes)
25
Shifting Bits
‣ Shifting multiplies or divides by power of 2
• shifting left b bits is the same multiplying by 2b 0x6 >> 1 == 1102 >> 1
• shifting right is the same as dividing by 2b
== 112 == 0x3
‣ But, what about negative numbers
• recall that negative numbers are represented in two’s complement form • -6 == 0xfa == 111110102 (i.e., 111110102 + 000001102 == 0)
• -6 / 2 == -3, but 111110102 shifted right is 011111012 == 125, not -3
‣ There are two kinds of right shifts
• SIGNED “>>” shifts, but keeps high-order bit (the sign bit) the same
– 6- >> 1 == 111111012 == -3 (i.e., 111111012 + 000000112 == 0) • UNSIGNED “>>>”, shifts and sets high-order bit to 0
– -6 >>> 1 == 011111012 … 0xfa >>> 1 == 0x7d
• In Java you choose the operator. In C you choose the data type.
– C as both signed and unsigned integer data types and no “>>>”. Java has only signed.
26
Extending an Integer
‣ Extending is
• when you increase the number of bytes used to store an integer
byte b = -6;
int i=b;
out.printf (“b: 0x%x %d, i: 0x%x %d\n”, b, b, i, i);
• what prints? b: 0xfa -6, i: 0xfffffffa -6
‣ Signed Extension
• used with signed numbers (everything in Java is signed)
• copies sign bit into upper, empty bits of the extended number
‣ Zero Extension
• used with unsigned numbers (e.g., in C)
• sets upper, empty bits to 0
• you can force zero-extension by MASKING using logical, bit-wise AND:
int u=b&0xff;
out.printf (“u: 0x%x %d\n”, u, u);
u: 0xfa 250
27
Truncating an Integer
‣ You can also go the other way • more bits to fewer bits
int i = -6;
byte b = i;
out.printf (“b: 0x%x %d, i: 0x%x %d\n”, b, b, i, i);
• what could go wrong?
– If i is 256, what is b? What if i is 128?
‣ Java warns you
• if you truncate an integer without an explicit cast as above
– “Possible Loss of Precision”
• you get rid of the warning by explicitly casting
– the cast has no effect on the value of b
– it just tells the compiler that you know what your doing … obviously, be sure you do
int i = -6;
byte b = (byte) i;
out.printf (“b: 0x%x %d, i: 0x%x %d\n”, b, b, i, i);
28
Question 1a.5: Shifting
What is the value of i after this Java statement executes?
int i = ((byte) 0x8b) << 16;
A. 0x8b
B. 0x0000008b C. 0x008b0000 D. 0xff8b0000 E. None of these
29
Question 1a.6: Masking
What is the value of i after this Java statement executes?
int i = 0xff8b0000 & 0x00ff0000;
A. 0xffff0000 B. 0xff8b0000 C. 0x008b0000 D. 0x8b000000 E. None of these
30