程序代写代做代考 compiler C assembly go arm android Carnegie Mellon

程序代写 CS代考 / android, ARM汇编代写代考, compiler, C语言代写

Carnegie Mellon
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
1
14
–
513
18
–
613

Carnegie Mellon
Bits, Bytes, and Integers – Part 2
15-213/18-213/14-513/15-513/18-613: Introduction to Computer Systems 3rd Lecture, September 8, 2020
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
2

Carnegie Mellon
Assignment Announcements
 Lab 0 available via course web page and Autolab. ▪ Due Thurs. Sept. 10, 11:59:59pm ET
▪ No grace days. No late submissions!
 Lab 1 available after 5 pm via Autolab
▪ Due Thurs, Sept. 17, 11:59:59pm ET
▪ Read instructions carefully: writeup, bits.c, tests.c
▪ Quirky software infrastructure
▪ Based on lectures 2, 3, and 4 (CS:APP Chapter 2)
▪ After today you will know everything for the integer problems ▪ Floating point covered Thursday Sept. 10
 In-Person Recitations
▪ We will email students with their in-person recitation status based
on the survey on Piazza (fill out before class 9/10 or be uncounted)
▪ First recitations (in-person and remote) are 9/14 Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
3

Carnegie Mellon
Bootcamps
 Wednesday Sept 9 @ 7-9 pm ET
▪ GCC and Build Automation
 Friday Sept 11 @ 7-9 pm ET
▪ Debugging and GDB
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
4

Carnegie Mellon
Summary From Last Lecture
 Representing information as bits
 Bit-level manipulations
 Integers
▪ Representation: unsigned and signed
▪ Conversion, casting
▪ Expanding, truncating
▪ Addition, negation, multiplication, shifting
 Representations in memory, pointers, strings  Summary
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
5

Carnegie Mellon
Encoding Integers Unsigned w−1
B2U(X) =
Two’s Complement w−2
x 2i
B2T(X)
= −x w−1
2w−1 +
 i=0
x 2i i
Sign Bit
i i=0
Two’s Complement Examples (w = 5)
10 =
-10 =
8+2 = 10
-16+4+2 = -10
-16
8
4
2
1
0
1
0
1
0
-16
8
4
2
1
1
0
1
1
0
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
6

Carnegie Mellon
Unsigned & Signed Numeric Values  Equivalence
▪ Same encodings for nonnegative values
 Uniqueness
▪ Every bit pattern represents
unique integer value
▪ Each representable integer has unique bit encoding

X
B2U(X) B2T(X)
0000
00
0001
11
0010
22
0011
33
0100
44
0101
55
0110
66
0111
77
1000
8 –8
1001
9 –7
1010
10 –6
1011
11 –5
1100
12 –4
1101
13 –3
1110
14 –2
1111
15 –1
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
7
Expression containing signed
and unsigned int:
int is cast to unsigned

Carnegie Mellon
Sign Extension and Truncation  Sign Extension
 Truncation
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
8

Carnegie Mellon
Global Thermonuclear War
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
11

Carnegie Mellon
 Misunderstanding integers can lead to the end of the world as we know it!
 Thule (Qaanaaq), Greenland
 US DoD “Site J” Ballistic Missile Early Warning System (BMEWS)
 10/5/60: world nearly ends
 Missile radar echo: 1/8s
 BMEWS reports: 75s echo(!)
 1000s of objects reported
 NORAD alert level 5:
▪ Immediate incoming nuclear attack!!!!
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
12

Carnegie Mellon
 Kruschev was in NYC 10/5/60 (weird time to attack) ▪ someone in Qaanaaq said “why not go check outside?”
 “Missiles” were actually THE MOON RISING OVER NORWAY
 Expected max distance: 3000 mi; Moon distance: .25M miles!  .25M miles % sizeof(distance) = 2200mi.
 Overflow of distance nearly caused nuclear apocalypse!! Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
13

Carnegie Mellon
Today: Bits, Bytes, and Integers
 Representing information as bits
 Bit-level manipulations
 Integers
▪ Representation: unsigned and signed
▪ Conversion, casting
▪ Expanding, truncating
▪ Addition, negation, multiplication, shifting
 Representations in memory, pointers, strings  Summary
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
14

Unsigned Addition
Operands: w bits True Sum: w+1 bits
u +v
u+v UAddw(u , v)
0
1
Carnegie Mellon
•••
•••
•••
•••
Discard Carry: w bits
 Standard Addition Function
0000
▪ Ignores carry output
 Implements Modular Arithmetic
s = UAddw(u,v) = u+v mod2w
1
2
unsigned char
1110 1001 E9 223 + 11010101 +D5 +213
1 1011 1110 1BE 446 1011 1110 BE 190
8
2
3
3
0001
0010
0011
4
4
0100
5
7
5
6
6
7
0101
0110
0111
8
9
9
A
10
1000
1001
1010
B
11
1011
C
12
D
13
1100
E
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
15
F
0
14
15
1101
1110
1111

Carnegie Mellon
Visualizing (Mathematical) Integer Addition
Add4(u , v)
 Integer Addition
▪ 4-bit integers u, v
▪ Compute true sum Add4(u , v)
▪ Values increase linearly with u and v
▪ Forms planar surface
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
16
Integer Addition
32 28 24
20 16 12
14
12
10 8
8 46v
0
0
4
22
u4
6
8 10 12 14
0

Carnegie Mellon
Visualizing Unsigned Addition
 Wraps Around ▪ If true sum ≥ 2w ▪ At most once
True Sum
2w+1
Overflow
2w 0
Overflow
14 6 12
10 8v
6 4
Modular Sum
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
17
UAdd4(u , v)
16 14 12
10 8
4 2 0
0
u
246 2
8 10 12
0
14

Carnegie Mellon
Two’s Complement Addition
Operands: w bits u
•••
+v u+v
•••
True Sum: w+1 bits
Discard Carry: w bits TAddw(u , v)
•••
•••
 TAdd and UAdd have Identical Bit-Level Behavior
▪ Signed vs. unsigned addition in C:
int s, t, u, v;
s = (int) ((unsigned) u + (unsigned) v); t =u+v
▪Willgive s==t
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
1110 1001 E9 -23 + 11010101 +D5 +-43
1 1011 1110 1BE -66 1011 1110 BE -66
18

Carnegie Mellon
TAdd Overflow  Functionality
▪ True sum requires w+1 bits
▪ Drop off MSB
▪ Treat remaining bits as
2’s comp. integer
True Sum
0 111…1 0 100…0
0 011…1 0 000…0
1 100…0 1 011…1
1 000…0
2w–1 2w –1–1
0
–2w –1 –2w
PosOver
TAdd Result
011…1 000…0 100…0
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
19
NegOver

Carnegie Mellon
Visualizing 2’s Complement Addition NegOver
 Values
▪ 4-bit two’s comp.
▪ Range from -8 to +7
 Wraps Around ▪ If sum  2w–1
▪ Becomes negative
▪ At most once ▪ If sum < –2w–1 ▪ Becomes positive ▪ At most once Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 20 8 6 4 2 0 TAdd4(u , v) 6 -2 4 -4 -6 -8 -8 -6 -4 -2 u -6 2 0 -2 -4 v 024 -8 6 PosOver Carnegie Mellon Characterizing TAdd  Functionality ▪ True sum requires w+1 bits Positive Overflow ▪ Drop off MSB ▪ Treat remaining bits as 2’s comp. integer TAdd(u , v) >0
v
<0 TAddw(u,v) = 2w u+v TMinw u+vTMaxw Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 21 <0 u >0 Negative Overflow
w−1
u+v+2w u+v TMin (NegOver)
u+v−2w−1 TMax u+v
 2w w (PosOver)

Carnegie Mellon
Multiplication
 Goal: Computing Product of w-bit numbers x, y
▪ Either signed or unsigned
 But, exact results can be bigger than w bits ▪ Unsigned: up to 2w bits
▪ Result range: 0 ≤ x * y ≤ (2w – 1) 2 = 22w – 2w+1 + 1 ▪ Two’s complement min (negative): Up to 2w-1 bits
▪ Result range: x * y ≥ (–2w–1)*(2w–1–1) = –22w–2 + 2w–1
▪ Two’s complement max (positive): Up to 2w bits, but only for (TMinw)2
▪ Result range: x * y ≤ (–2w–1) 2 = 22w–2
 So, maintaining exact results…
▪ would need to keep expanding word size with each product computed ▪ is done in software, if needed
▪ e.g., by “arbitrary precision” arithmetic packages Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
22

Carnegie Mellon
Unsigned Multiplication in C
•••
Operands: w bits
True Product: 2*w bits
u *v
•••
u · v
•••
•••
UMultw(u , v)  Standard Multiplication Function
▪ Ignores high order w bits
 Implements Modular Arithmetic
•••
Discard w bits: w bits
UMultw(u , v)=
u · v mod 2w
1110 1001
* 11010101 * D5 * 213
1100 0001 1101 1101 C1DD 49629
1101 1101 DD 221
E9 233
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
23

Carnegie Mellon
Signed Multiplication in C
Operands: w bits
True Product: 2*w bits
Discard w bits: w bits
•••
u *v
u·v
TMultw(u , v)
•••
•••
•••
•••
 Standard Multiplication Function
▪ Ignores high order w bits
▪ Some of which are different for signed vs. unsigned multiplication
▪ Lower bits are the same
1110 1001
* 11010101 * D5 * -43
0000 0011 1101 1101 03DD 989
E9 -23
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
1101 1101 DD -35
24

Carnegie Mellon
Power-of-2 Multiply with Shift
 Operation
▪u << kgivesu * 2k ▪ Both signed and unsigned k ••• Operands: w bits True Product: w+k bits Discard k bits: w bits  Examples ▪u<<3 u * 2k u · 2k TMultw(u , 2k) 0 ••• 0 1 0 ••• 0 0 ••• 0 ••• 0 0 UMultw(u , 2k) ••• 0 ••• 0 0 == u*8 ▪(u<<5)–(u<<3)== u*24 ▪ Most machines shift and add faster than multiply ▪ Compiler generates this code automatically Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 25 Carnegie Mellon Unsigned Power-of-2 Divide with Shift  Quotient of Unsigned by Power of 2 ▪ u >> k gives  u / 2k 
▪ Uses logical shift
•••
•••
u / 2k
u / 2k  u / 2k 
k
Operands: Division:
Result:
Binary Point
0
•••
0
1
0
•••
0
0
0
•••
0
0
•••
.
•••
0
•••
0
0
•••
Division
Computed
Hex
Binary
x
15213
15213
3B 6D
00111011 01101101
x >> 1
7606.5
7606
1D B6
00011101 10110110
x >> 4
950.8125
950
03 B6
00000011 10110110
x >> 8
59.4257813
59
00 3B
00000000 00111011
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
26

Carnegie Mellon
Signed Power-of-2 Divide with Shift
 Quotient of Signed by Power of 2 ▪ x >> k gives  x / 2k 
▪ Uses arithmetic shift
▪ Rounds wrong direction when x < 0 k ••• ••• Operands: Division: Result: x / 2k x / 2k RoundDown(x / 2k) Binary Point . 0 ••• 0 1 0 ••• 0 0 0 ••• ••• 0 ••• ••• Division Computed Hex Binary x -15213 -15213 C4 93 11000100 10010011 x >> 1
-7606.5
-7607
E2 49
11100010 01001001
x >> 4
-950.8125
-951
FC 49
11111100 01001001
x >> 8
-59.4257813
-60
FF C4
11111111 11000100
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
27
•••

Carnegie Mellon
Correct Power-of-2 Divide
 Quotient of Negative Number by Power of 2 ▪ Want x / 2k  (Round Toward 0)
▪ Compute as  (x+2k-1)/ 2k 
▪ In C: (x + (1<> k ▪ Biases dividend toward 0
Case 1: No rounding
Dividend: Divisor:
k
1
•••
0
•••
0
0
u
+2k –1 / 2k
Binary Point
0
•••
0
0
1
•••
1
1
1
•••
1
•••
1
1
0
•••
0
1
0
•••
0
0
u/2k  .
01
•••
1
1
1
•••
1
•••
1
1
Biasing has no effect
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
28

Carnegie Mellon
Correct Power-of-2 Divide (Cont.)
Case 2: Rounding
Dividend:
k +2k –1
Incremented by 1
/ 2k
x/2k  .
1
•••
•••
x
0
•••
0
0
1
•••
1
1
1
•••
•••
Binary Point
0
•••
0
1
0
•••
0
0
Divisor:
01
•••
1
1
1
•••
•••
Biasing adds 1 to final result
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
29
Incremented by 1

Carnegie Mellon
Negation: Complement & Increment  Negate through complement and increase
~x + 1 == -x
 Example
▪ Observation: ~x + x == 1111…111 == -1
1
0
0
1
1
1
0
1
x + ~x
-1
0
1
1
0
0
0
1
0
1
1
1
1
1
1
1
1
x = 15213
Decimal
Hex
Binary
x
15213
3B 6D
00111011 01101101
~x
-15214
C4 92
11000100 10010010
~x+1
-15213
C4 93
11000100 10010011
y
-15213
C4 93
11000100 10010011
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
30

Carnegie Mellon
Complement & Increment Examples x= 0
Decimal
Hex
Binary
0
0
00 00
00000000 00000000
~0
-1
FF FF
11111111 11111111
~0+1
0
00 00
00000000 00000000
x = TMin
Decimal
Hex
Binary
x
-32768
80 00
10000000 00000000
~x
32767
7F FF
01111111 11111111
~x+1
-32768
80 00
10000000 00000000
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
31
Canonical counter example

Carnegie Mellon
Today: Bits, Bytes, and Integers
 Representing information as bits
 Bit-level manipulations
 Integers
▪ Representation: unsigned and signed
▪ Conversion, casting
▪ Expanding, truncating
▪ Addition, negation, multiplication, shifting ▪ Summary
 Representations in memory, pointers, strings
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
32

Carnegie Mellon
Arithmetic: Basic Rules  Addition:
▪ Unsigned/signed: Normal addition followed by truncate, same operation on bit level
▪ Unsigned: addition mod 2w
▪ Mathematical addition + possible subtraction of 2w
▪ Signed: modified addition mod 2w (result in proper range)
▪ Mathematical addition + possible addition or subtraction of 2w
 Multiplication:
▪ Unsigned/signed: Normal multiplication followed by truncate,
same operation on bit level
▪ Unsigned: multiplication mod 2w
▪ Signed: modified multiplication mod 2w (result in proper range)
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
33

Carnegie Mellon
Quiz Time!
Check out:
https://canvas.cmu.edu/courses/17808
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
37

Carnegie Mellon
Today: Bits, Bytes, and Integers
 Representing information as bits
 Bit-level manipulations
 Integers
▪ Representation: unsigned and signed
▪ Conversion, casting
▪ Expanding, truncating
▪ Addition, negation, multiplication, shifting ▪ Summary
 Representations in memory, pointers, strings
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
38

Carnegie Mellon
Byte-Oriented Memory Organization
•••
 Programs refer to data by address
▪ Conceptually, envision it as a very large array of bytes
▪ In reality, it’s not, but can think of it that way ▪ An address is like an index into that array
▪ and, a pointer variable stores an address
 Note: system provides private address spaces to each “process” ▪ Think of a process as a program being executed
▪ So, a program can clobber its own data, but not that of others
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
39

Carnegie Mellon
Machine Words
 Any given computer has a “Word Size” ▪ Nominal size of integer-valued data
▪ and of addresses
▪ Until recently, most machines used 32 bits (4 bytes) as word size
▪ Limits addresses to 4GB (232 bytes)
▪ Increasingly, machines have 64-bit word size
▪ Potentially, could have 18 EB (exabytes) of addressable memory ▪ That’s 18.4 X 1018
▪ Machines still support multiple data formats
▪ Fractions or multiples of word size
▪ Always integral number of bytes Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
40

Carnegie Mellon
Word-Oriented Memory Organization
 Addresses Specify Byte Locations
▪ Address of first byte in word
▪ Addresses of successive words differ
by 4 (32-bit) or 8 (64-bit)
32-bit 64-bit
Bytes Addr.
0000
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010
0011
0012
0013
0014
0015
Words
Words
Addr =
0000 ??
Addr =
0004 ??
Addr =
0008 ??
Addr =
0012 ??
Addr =
0000 ??
Addr =
0008 ??
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
41

Carnegie Mellon
Example Data Representations
C Data Type
Typical 32-bit
Typical 64-bit
x86-64
char
1
1
1
short
2
2
2
int
4
4
4
long
4
8
8
float
4
4
4
double
8
8
8
pointer
4
8
8
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
42

Carnegie Mellon
Byte Ordering
 So, how are the bytes within a multi-byte word ordered in memory?
 Conventions
▪ Big Endian: Sun (Oracle SPARC), PPC Mac, Internet
▪ Least significant byte has highest address
▪ Little Endian: x86, ARM processors running Android, iOS, and Linux
▪ Least significant byte has lowest address
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
43

Carnegie Mellon
Byte Ordering Example
 Example
▪ Variable x has 4-byte value of 0x01234567 ▪ Address given by &x is 0x100
Big Endian Little Endian
0x100 0x101 0x102 0x103
0x100 0x101 0x102 0x103
01
23
45
67
67
45
23
01
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
44

Carnegie Mellon
Representing Integers
int A = 15213;
long int C = 15213;
IA32, x86-64 Sun
IA32 x86-64 Sun
6D
3B
00
00
00
00
3B
6D
6D
3B
00
00
6D
3B
00
00
00
00
00
00
00
00
3B
6D
int B = -15213;
IA32, x86-64 Sun
93
C4
FF
FF
FF
FF
C4
93
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
45
Decimal: 15213
Binary: 0011 1011 0110 1101 Hex: 3B6D
Two’s complement representation
Increasing addresses

Carnegie Mellon
Examining Data Representations  Code to Print Byte Representation of Data
▪ Casting pointer to unsigned char * allows treatment as a byte array
Printf directives:
%p: Print pointer
%x: Print Hexadecimal
typedef unsigned char *pointer;
void show_bytes(pointer start, size_t len){
size_t i;
for (i = 0; i < len; i++) printf(”%p\t0x%.2x\n",start+i, start[i]); printf("\n"); } Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 46 Carnegie Mellon show_bytes Execution Example int a = 15213; printf("int a = 15213;\n"); show_bytes((pointer) &a, sizeof(int)); Result (Linux x86-64): Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 47 int a = 15213; 0x7fffb7f71dbc 6d 0x7fffb7f71dbd 3b 0x7fffb7f71dbe 00 0x7fffb7f71dbf 00 Carnegie Mellon Representing Pointers Sun IA32 x86-64 int B = -15213; int *P = &B; EF FF FB 2C AC 28 F5 FF 3C 1B FE 82 FD 7F 00 00 Different compilers & machines assign different locations to objects Even get different results each time run program Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 48 Carnegie Mellon Representing Strings  Strings in C ▪ Represented by array of characters ▪ Each character encoded in ASCII format ▪ Standard 7-bit encoding of character set ▪ Character “0” has code 0x30 – Digit i has code 0x30+i ▪ String should be null-terminated ▪ Final character = 0  Compatibility ▪ Byte ordering not an issue char S[6] = "18213"; IA32 Sun 31 38 32 31 33 00 31 38 32 31 33 00 Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 49 Carnegie Mellon Reading Byte-Reversed Listings  Disassembly ▪ Text representation of binary machine code ▪ Generated by program that reads the machine code  Example Fragment Address Instruction Code 8048365: 5b 8048366: 81 c3 ab 12 00 00 804836c: 83 bb 28 00 00 00 00 Assembly Rendition pop %ebx add $0x12ab,%ebx cmpl $0x0,0x28(%ebx)  Deciphering Numbers ▪ Value: ▪ Pad to 32 bits: ▪ Split into bytes: ▪ Reverse: 0x12ab 0x000012ab 00 00 12 ab ab 12 00 00 Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 50 Carnegie Mellon Summary  Representing information as bits  Bit-level manipulations  Integers ▪ Representation: unsigned and signed ▪ Conversion, casting ▪ Expanding, truncating ▪ Addition, negation, multiplication, shifting  Representations in memory, pointers, strings  Summary Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 52

Related Posts