PowerPoint Presentation
Memory, Data, & Addressing II
http://xkcd.com/138/
CMPT 295
L03: Memory & Data II
Roadmap
2
car *c = malloc(sizeof(car));
c->miles = 100;
c->gals = 17;
float mpg = get_mpg(c);
free(c);
Car c = new Car();
c.setMiles(100);
c.setGals(17);
float mpg =
c.getMPG();
Java:
C:
Assembly language:
Machine code:
0111010000011000
100011010000010000000010
1000100111000010
110000011111101000011111
Computer system:
OS:
Memory & data
Arrays & structs
Integers & floats
RISC V assembly
Procedures & stacks
Executables
Memory & caches
Processor Pipeline
Performance
Parallelism
CMPT 295
L03: Memory & Data II
2
Review
If the word size of a machine is 64-bits, which of the following is usually true? (pick all that apply)
64 bits is the size of a pointer
64 bits is the size of an integer
64 bits is the width of a register
(True/False) By looking at the bits stored in memory, I can tell if a particular 4-bytes is being used to represent an integer, floating point number, or instruction.
If the size of a pointer on a machine is 6 bits, the address space is how many bytes?
3
CMPT 295
L03: Memory & Data II
Memory, Data, and Addressing
Representing information as bits and bytes
Organizing and addressing data in memory
Manipulating data in memory using C
Boolean algebra and bit-level manipulations
4
CMPT 295
L03: Memory & Data II
Before we can get into how we use memory, we have to introduce some C syntax to help us describe what we’re doing
Addresses and Pointers in C
& = “address of” operator
* = “value at address” or “dereference” operator
int* ptr;
int x = 5;
int y = 2;
ptr = &x;
y = 1 + *ptr;
5
Declares a variable, ptr, that is a pointer to
(i.e. holds the address of) an int in memory
Declares two variables, x and y, that hold ints, and initializes them to 5 and 2, respectively
Sets ptr to the address of x
(“ptr points to x”)
Sets y to “1 plus the value stored at the address held by ptr. Because ptr points to x, this is equivalent to y=1+x;
“Dereference ptr”
What is *(&y) ?
* is also used with variable declarations
CMPT 295
L03: Memory & Data II
Now we’re going to talk about how all of this looks in C…
* means a pointer to an int
& gets the address of the variable
* on a pointer dereferences it
Note two slightly different uses of * here, in declarations and as a unary operator
Assignment in C
A variable is represented by a location
Declaration ≠ initialization (initially holds “garbage”)
int x, y;
x is at address 0x04, y is at 0x18
6
x
y
0x00
0x01
0x02
0x03
A7
00
32
00
00
01
29
F3
EE
EE
EE
EE
FA
CE
CA
FE
26
00
00
00
00
00
10
00
01
00
00
00
FF
00
F4
96
DE
AD
BE
EF
00
00
00
00
0x00
0x04
0x08
0x0C
0x10
0x14
0x18
0x1C
0x20
0x24
CMPT 295
L03: Memory & Data II
Assignment in C
A variable is represented by a location
Declaration ≠ initialization (initially holds “garbage”)
int x, y;
x is at address 0x04, y is at 0x18
7
x
y
0x00
0x01
0x02
0x03
00
01
29
F3
01
00
00
00
0x00
0x04
0x08
0x0C
0x10
0x14
0x18
0x1C
0x20
0x24
32-bit example
(pointers are 32-bits wide)
little-endian
CMPT 295
L03: Memory & Data II
Assignment in C
left-hand side = right-hand side;
LHS must evaluate to a location
RHS must evaluate to a value (could be an address)
Store RHS value at LHS location
int x, y;
x = 0;
8
00
01
29
F3
00
00
00
00
x
y
0x00
0x01
0x02
0x03
01
00
00
00
0x00
0x04
0x08
0x0C
0x10
0x14
0x18
0x1C
0x20
0x24
& = “address of”
* = “dereference”
32-bit example
(pointers are 32-bits wide)
CMPT 295
L03: Memory & Data II
Assignment in C
left-hand side = right-hand side;
LHS must evaluate to a location
RHS must evaluate to a value (could be an address)
Store RHS value at LHS location
int x, y;
x = 0;
y = 0x3CD02700;
9
00
00
00
00
01
00
00
00
00
27
D0
3C
x
y
0x00
0x01
0x02
0x03
0x00
0x04
0x08
0x0C
0x10
0x14
0x18
0x1C
0x20
0x24
little endian!
& = “address of”
* = “dereference”
32-bit example
(pointers are 32-bits wide)
CMPT 295
L03: Memory & Data II
Assignment in C
left-hand side = right-hand side;
LHS must evaluate to a location
RHS must evaluate to a value (could be an address)
Store RHS value at LHS location
int x, y;
x = 0;
y = 0x3CD02700;
x = y + 3;
Get value at y, add 3, store in x
10
00
00
00
00
00
27
D0
3C
03
27
D0
3C
x
y
0x00
0x01
0x02
0x03
0x00
0x04
0x08
0x0C
0x10
0x14
0x18
0x1C
0x20
0x24
& = “address of”
* = “dereference”
32-bit example
(pointers are 32-bits wide)
CMPT 295
L03: Memory & Data II
Assignment in C
left-hand side = right-hand side;
LHS must evaluate to a location
RHS must evaluate to a value (could be an address)
Store RHS value at LHS location
int x, y;
x = 0;
y = 0x3CD02700;
x = y + 3;
Get value at y, add 3, store in x
int* z;
z is at address 0x20
11
03
27
D0
3C
00
27
D0
3C
x
y
0x00
0x01
0x02
0x03
0x00
0x04
0x08
0x0C
0x10
0x14
0x18
0x1C
0x20
0x24
z
DE
AD
BE
EF
& = “address of”
* = “dereference”
32-bit example
(pointers are 32-bits wide)
CMPT 295
L03: Memory & Data II
Assignment in C
left-hand side = right-hand side;
LHS must evaluate to a location
RHS must evaluate to a value (could be an address)
Store RHS value at LHS location
int x, y;
x = 0;
y = 0x3CD02700;
x = y + 3;
Get value at y, add 3, store in x
int* z = &y + 3;
Get address of y, “add 3”, store in z
12
03
27
D0
3C
00
27
D0
3C
x
y
0x00
0x01
0x02
0x03
0x00
0x04
0x08
0x0C
0x10
0x14
0x18
0x1C
0x20
0x24
z
24
00
00
00
Pointer arithmetic
& = “address of”
* = “dereference”
32-bit example
(pointers are 32-bits wide)
CMPT 295
L03: Memory & Data II
13
CMPT 295
L03: Memory & Data II
Pointer Arithmetic
Pointer arithmetic is scaled by the size of target type
In this example, sizeof(int) = 4
int* z = &y + 3;
Get address of y, add 3*sizeof(int), store in z
&y = 0x18
24 + 3*(4) = 36
Pointer arithmetic can be dangerous!
Can easily lead to bad memory accesses
Be careful with data types and casting
14
= 1*161 + 8*160 = 24
= 2*161 + 4*160 = 0x24
CMPT 295
L03: Memory & Data II
Assignment in C
int x, y;
x = 0;
y = 0x3CD02700;
x = y + 3;
Get value at y, add 3, store in x
int* z = &y + 3;
Get address of y, add 12, store in z
*z = y;
What does this do?
15
03
27
D0
3C
00
27
D0
3C
x
y
0x00
0x01
0x02
0x03
0x00
0x04
0x08
0x0C
0x10
0x14
0x18
0x1C
0x20
0x24
z
24
00
00
00
& = “address of”
* = “dereference”
32-bit example
(pointers are 32-bits wide)
CMPT 295
L03: Memory & Data II
Assignment in C
int x, y;
x = 0;
y = 0x3CD02700;
x = y + 3;
Get value at y, add 3, store in x
int* z = &y + 3;
Get address of y, add 12, store in z
*z = y;
Get value of y, put in address
stored in z
16
03
27
D0
3C
00
27
D0
3C
x
y
0x00
0x01
0x02
0x03
0x00
0x04
0x08
0x0C
0x10
0x14
0x18
0x1C
0x20
0x24
z
24
00
00
00
00
27
D0
3C
The target of a pointer is also a location
& = “address of”
* = “dereference”
32-bit example
(pointers are 32-bits wide)
CMPT 295
L03: Memory & Data II
Arrays in C
Declaration: int a[6];
17
0x00
0x08
0x10
0x18
0x20
0x28
0x30
0x38
0x40
0x48
a[0]
a[2]
a[4]
a (array name) returns the array’s address
Arrays are adjacent locations in memory storing the same type of data object
element type
name
number of
elements
a[1]
a[3]
a[5]
0x4
0xC
0x5
0xD
0x6
0xE
0x7
0xF
0x0
0x8
0x1
0x9
0x2
0xA
0x3
0xB
64-bit example
(pointers are 64-bits wide)
CMPT 295
L03: Memory & Data II
Arrays Basics
Pitfall: An array in C does not know its own length, and its bounds are not checked!
We can accidentally access off the end of an array
We must pass the array and its size to any procedure that is going to manipulate it
Mistakes with array bounds cause segmentation faults and bus errors
Be careful! These are VERY difficult to find
(You’ll learn how to debug these in lab)
18
CMPT 295
L03: Memory & Data II
Arrays in C
Declaration: int a[6];
Indexing: a[0] = 0x015f;
a[5] = a[0];
19
0x00
0x08
0x10
0x18
0x20
0x28
0x30
0x38
0x40
0x48
a[0]
a[2]
a[4]
0x4
0xC
0x5
0xD
0x6
0xE
0x7
0xF
0x0
0x8
0x1
0x9
0x2
0xA
0x3
0xB
00
00
01
5F
00
00
01
5F
&a[i] is the address of a[0] plus i times the element size in bytes
Arrays are adjacent locations in memory storing the same type of data object
a (array name) returns the array’s address
CMPT 295
L03: Memory & Data II
Arrays in C
Declaration: int a[6];
Indexing: a[0] = 0x015f;
a[5] = a[0];
No bounds a[6] = 0xBAD;
checking: a[-1] = 0xBAD;
20
0x00
0x08
0x10
0x18
0x20
0x28
0x30
0x38
0x40
0x48
a[0]
a[2]
a[4]
0x4
0xC
0x5
0xD
0x6
0xE
0x7
0xF
0x0
0x8
0x1
0x9
0x2
0xA
0x3
0xB
00
00
01
5F
00
00
01
5F
00
00
0B
AD
00
00
0B
AD
&a[i] is the address of a[0] plus i times the element size in bytes
Arrays are adjacent locations in memory storing the same type of data object
a (array name) returns the array’s address
CMPT 295
L03: Memory & Data II
00
00
01
5F
Arrays in C
Declaration: int a[6];
Indexing: a[0] = 0x015f;
a[5] = a[0];
No bounds a[6] = 0xBAD;
checking: a[-1] = 0xBAD;
Pointers: int* p;
p = a;
p = &a[0];
*p = 0xA;
21
00
00
00
0A
0x00
0x08
0x10
0x18
0x20
0x28
0x30
0x38
0x40
0x48
a[0]
a[2]
a[4]
0x4
0xC
0x5
0xD
0x6
0xE
0x7
0xF
0x0
0x8
0x1
0x9
0x2
0xA
0x3
0xB
00
00
01
5F
00
00
0B
AD
00
00
0B
AD
p
equivalent
00
00
00
10
00
00
00
00
&a[i] is the address of a[0] plus i times the element size in bytes
Arrays are adjacent locations in memory storing the same type of data object
a (array name) returns the array’s address
CMPT 295
L03: Memory & Data II
array indexing = address arithmetic
(both scaled by the size of the type)
00
00
01
5F
Arrays in C
Declaration: int a[6];
Indexing: a[0] = 0x015f;
a[5] = a[0];
No bounds a[6] = 0xBAD;
checking: a[-1] = 0xBAD;
Pointers: int* p;
p = a;
p = &a[0];
*p = 0xA;
p[1] = 0xB;
*(p+1) = 0xB;
p = p + 2;
22
00
00
00
0A
0x00
0x08
0x10
0x18
0x20
0x28
0x30
0x38
0x40
0x48
a[0]
a[2]
a[4]
0x4
0xC
0x5
0xD
0x6
0xE
0x7
0xF
0x0
0x8
0x1
0x9
0x2
0xA
0x3
0xB
00
00
01
5F
00
00
0B
AD
00
00
0B
AD
p
equivalent
00
00
00
10
00
00
00
00
equivalent
00
00
00
0B
&a[i] is the address of a[0] plus i times the element size in bytes
Arrays are adjacent locations in memory storing the same type of data object
a (array name) returns the array’s address
CMPT 295
L03: Memory & Data II
array indexing = address arithmetic
(both scaled by the size of the type)
Arrays in C
Declaration: int a[6];
Indexing: a[0] = 0x015f;
a[5] = a[0];
No bounds a[6] = 0xBAD;
checking: a[-1] = 0xBAD;
Pointers: int* p;
p = a;
p = &a[0];
*p = 0xA;
p[1] = 0xB;
*(p+1) = 0xB;
p = p + 2;
*p = a[1] + 1;
23
0x00
0x08
0x10
0x18
0x20
0x28
0x30
0x38
0x40
0x48
a[0]
a[2]
a[4]
0x4
0xC
0x5
0xD
0x6
0xE
0x7
0xF
0x0
0x8
0x1
0x9
0x2
0xA
0x3
0xB
equivalent
equivalent
00
00
00
0A
00
00
01
5F
00
00
0B
AD
00
00
0B
AD
00
00
00
18
00
00
00
00
00
00
00
0B
p
00
00
00
0C
&a[i] is the address of a[0] plus i times the element size in bytes
Arrays are adjacent locations in memory storing the same type of data object
a (array name) returns the array’s address
CMPT 295
L03: Memory & Data II
Arrays Stored Differently Than Pointers
void foo() {
int *p, a[4], x;
p = &x;
*p = 1; // or p[0]
printf(“*p:%u, p:%u, &p:%u\n”,*p,p,&p);
*a = 2; // or a[0]
printf(“*a:%u, a:%u, &a:%u\n”,*a,a,&a);
}
24
?
…
…
?
?
40
2
1
*p:1, p:40, &p:20
*a:2, a:24, &a:24
K&R: “An array__.
name is not
a variable”.
a
24
?
0
4
8
12
16
20
24
28
32
36
40
44
48
…
p
x
CMPT 295
L03: Memory & Data II
Remember to animate
Representing strings
C-style string stored as an array of bytes (char*)
Elements are one-byte ASCII codes for each character
No “String” keyword, unlike Java
25
32 space 48 0 64 @ 80 P 96 ` 112 p
33 ! 49 1 65 A 81 Q 97 a 113 q
34 ” 50 2 66 B 82 R 98 b 114 r
35 # 51 3 67 C 83 S 99 c 115 s
36 $ 52 4 68 D 84 T 100 d 116 t
37 % 53 5 69 E 85 U 101 e 117 u
38 & 54 6 70 F 86 V 102 f 118 v
39 ’ 55 7 71 G 87 W 103 g 119 w
40 ( 56 8 72 H 88 X 104 h 120 x
41 ) 57 9 73 I 89 Y 105 I 121 y
42 * 58 : 74 J 90 Z 106 j 122 z
43 + 59 ; 75 K 91 [ 107 k 123 {
44 , 60 < 76 L 92 \ 108 l 124 |
45 - 61 = 77 M 93 ] 109 m 125 }
46 . 62 > 78 N 94 ^ 110 n 126 ~
47 / 63 ? 79 O 95 _ 111 o 127 del
ASCII: American Standard Code for Information Interchange
CMPT 295
L03: Memory & Data II
I pronounce it ‘char’, you can also call it ‘care’ if you care to
Null-Terminated Strings
Example: “Donald Trump” stored as a 13-byte array
Last character followed by a 0 byte (‘\0’)
(a.k.a. “null terminator”)
Must take into account when allocating space in memory
Note that ‘0’ ≠ ‘\0’ (i.e. character 0 has non-zero value)
How do we compute the length of a string?
Traverse array until null terminator encountered
26
Decimal:.. 68 111 110 97 108 100 32 84 114 117 109 112 0
Hex:.. 0x44 0x6F 0x6E 0x61 0x6C 0x64 0x20 0x54 0x72 0x75 0x6D 0x70 0x00
Text:.. D o n a l d T r u m p \0
CMPT 295
L03: Memory & Data II
Also strlen() in #include
char s[6] = “12345”;
Endianness and Strings
Byte ordering (endianness) is not an issue for 1-byte values
The whole array does not constitute a single value
Individual elements are values; chars are single bytes
27
C (char = 1 byte)
0x31 = 49 decimal = ASCII ‘1’
33
34
31
32
35
00
33
34
31
32
35
00
0x00
0x01
0x02
0x03
0x04
0x05
0x00
0x01
0x02
0x03
0x04
0x05
‘1’
‘2’
‘3’
‘4’
‘5’
‘\0’
IA32, x86-64
(little-endian)
SPARC
(big-endian)
String literal
CMPT 295
L03: Memory & Data II
void show_bytes(char* start, int len) {
int i;
for (i = 0; i < len; i++)
printf("%p\t0x%.2x\n", start+i, *(start+i));
printf("\n");
}
Examining Data Representations
Code to print byte representation of data
Any data type can be treated as a byte array by casting it to char
C has unchecked casts !! DANGER !!
28
printf directives:
%p Print pointer
\t Tab
%x Print value as hex
\n New line
CMPT 295
L03: Memory & Data II
%p: prefix “0x” automatically printed
Examining Data Representations
Code to print byte representation of data
Any data type can be treated as a byte array by casting it to char
C has unchecked casts !! DANGER !!
29
void show_bytes(char* start, int len) {
int i;
for (i = 0; i < len; i++)
printf("%p\t0x%.2x\n", start+i, *(start+i));
printf("\n");
}
void show_int(int x) {
show_bytes( (char *) &x, sizeof(int));
}
CMPT 295
L03: Memory & Data II
%p: prefix “0x” automatically printed
show_bytes Execution Example
Result (Linux x86-64):
Note: The addresses will change on each run (try it!), but fall in same general range
30
int x = 12345; // 0x00003039
printf("int x = %d;\n",x);
show_int(x); // show_bytes((char *) &x, sizeof(int));
int x = 12345;
0x7fffb7f71dbc 0x39
0x7fffb7f71dbd 0x30
0x7fffb7f71dbe 0x00
0x7fffb7f71dbf 0x00
CMPT 295
L03: Memory & Data II
Summary
Assignment in C results in value being put in memory location
Pointer is a C representation of a data address
& = “address of” operator
* = “value at address” or “dereference” operator
Pointer arithmetic scales by size of target type
Convenient when accessing array-like structures in memory
Be careful when using – particularly when casting variables
Arrays are adjacent locations in memory storing the same type of data object
Strings are null-terminated arrays of characters (ASCII)
31
CMPT 295
L03: Memory & Data II
Assignment in C - Handout
left-hand side = right-hand side;
LHS must evaluate to a location
RHS must evaluate to a value
Store RHS value at LHS location
int x, y;
x = 0;
y = 0x3CD02700;
x = y + 3;
int* z = &y + 3;
*z = y;
x
y
0x00
0x01
0x02
0x03
0x00
0x04
0x08
0x0C
0x10
0x14
0x18
0x1C
0x20
0x24
z
& = “address of”
* = “dereference”
32-bit example
(pointers are 32-bits wide)
CMPT 295
L03: Memory & Data II
array indexing = address arithmetic
(both scaled by the size of the type)
Arrays in C - Handout
Declaration: int a[6];
Indexing: a[0] = 0x015f;
a[5] = a[0];
No bounds a[6] = 0xBAD;
checking: a[-1] = 0xBAD;
Pointers: int* p;
p = a;
p = &a[0];
*p = 0xA;
p[1] = 0xB;
*(p+1) = 0xB;
p = p + 2;
*p = a[1] + 1;
0x00
0x08
0x10
0x18
0x20
0x28
0x30
0x38
0x40
0x48
a[0]
a[2]
a[4]
0x4
0xC
0x5
0xD
0x6
0xE
0x7
0xF
0x0
0x8
0x1
0x9
0x2
0xA
0x3
0xB
equivalent
equivalent
p
&a[i] is the address of a[0] plus i times the element size in bytes
Arrays are adjacent locations in memory storing the same type of data object
a (array name) returns the array’s address
CMPT 295
L03: Memory & Data II
/docProps/thumbnail.jpeg