Introduction to Computing Systems: From Bits & Gates to C & Beyond

Cover......Page 1
Title Page......Page 4
Copyright Page......Page 5
Dedication......Page 6
Contents......Page 8
Acknowledgments......Page 26
Preface......Page 16
1.2 How We Will Get There......Page 30
1.3.1 The Notion of Abstraction......Page 32
1.3.2 Hardware vs. Software......Page 34
1.4 A Computer System......Page 36
1.4.1 A (Very) Little History for a (Lot) Better Perspective......Page 37
1.4.2 The Parts of a Computer System......Page 39
1.5 Two Very Important Ideas......Page 40
1.6 Computers as Universal Computational Devices......Page 41
1.7.1 The Statement of the Problem......Page 43
1.7.3 The Program......Page 45
1.7.4 The ISA......Page 46
1.7.5 The Microarchitecture......Page 47
1.7.7 The Devices......Page 48
Exercises......Page 49
2.1.1 The Bit as the Unit of Information......Page 54
2.2.1 Unsigned Integers......Page 55
2.2.2 Signed Integers......Page 56
2.3 2’s Complement Integers......Page 58
2.4.1 Binary to Decimal Conversion......Page 60
2.4.2 Decimal to Binary Conversion......Page 61
2.4.3 Extending Conversion to Numbers with Fractional Parts......Page 62
2.5.1 Addition and Subtraction......Page 63
2.5.3 Overflow......Page 65
2.6.2 The AND Function......Page 67
2.6.3 The OR Function......Page 68
2.6.5 The Exclusive-OR Function......Page 69
2.6.6 DeMorgan’s Laws......Page 70
2.6.7 The Bit Vector......Page 71
2.7.1 Floating Point Data Type (Greater Range, Less Precision)......Page 72
2.7.2 ASCII Codes......Page 76
2.7.3 Hexadecimal Notation......Page 77
Exercises......Page 78
3.1 The Transistor......Page 88
3.2.1 The NOT Gate (Inverter)......Page 90
3.2.2 OR and NOR Gates......Page 91
3.2.3 Why We Can’t Simply Connect P-Type to Ground......Page 93
3.2.4 AND and NAND Gates......Page 94
3.2.5 Gates with More Than Two Inputs......Page 95
3.3.1 Decoder......Page 96
3.3.2 Mux......Page 97
3.3.3 A One-Bit Adder (a.k.a. a Full Adder)......Page 98
3.3.4 The Programmable Logic Array (PLA)......Page 100
3.3.5 Logical Completeness......Page 101
3.4.1 The R-S Latch......Page 102
3.4.2 The Gated D Latch......Page 103
3.5.1 Address Space......Page 104
3.5.3 A 22-by-3-Bit Memory......Page 105
3.6 Sequential Logic Circuits......Page 107
3.6.1 A Simple Example: The Combination Lock......Page 108
3.6.2 The Concept of State......Page 109
3.6.3 The Finite State Machine and Its State Diagram......Page 111
3.6.4 The Synchronous Finite State Machine......Page 114
3.6.5 The Clock......Page 115
3.6.6 Example: A Danger Sign......Page 116
3.7 Preview of Coming Attractions: The Data Path of the LC-3......Page 122
Exercises......Page 124
4.1 Basic Components......Page 150
4.1.1 Memory......Page 151
4.1.2 Processing Unit......Page 152
4.1.3 Input and Output......Page 153
4.2 The LC-3: An Example von Neumann Machine......Page 154
4.3.1 The Instruction......Page 156
4.3.2 The Instruction Cycle (NOT the Clock Cycle!)......Page 159
4.3.3 Changing the Sequence of Execution......Page 161
4.3.4 Control of the Instruction Cycle......Page 163
4.3.5 Halting the Computer (the TRAP Instruction)......Page 165
4.4 Our First Program: A Multiplication Algorithm......Page 166
Exercises......Page 168
5.1 The ISA: Overview......Page 174
5.1.2 Registers......Page 175
5.1.3 The Instruction Set......Page 176
5.1.5 Data Types......Page 178
5.1.7 Condition Codes......Page 179
5.2.1 ADD, AND, and NOT......Page 180
5.2.2 Immediates......Page 181
5.2.3 The LEA Instruction (Although Not Really an Operate)......Page 183
5.3 Data Movement Instructions......Page 184
5.3.1 PC-Relative Mode......Page 185
5.3.2 Indirect Mode......Page 187
5.3.3 Base+offset Mode......Page 188
5.3.4 An Example......Page 189
5.4 Control Instructions......Page 190
5.4.1 Conditional Branches......Page 191
5.4.2 Two Methods of Loop Control......Page 194
5.4.4 The TRAP Instruction......Page 198
5.5 Another Example: Counting Occurrences of a Character......Page 199
5.6 The Data Path Revisited......Page 202
5.6.1 Basic Components of the Data Path......Page 204
5.6.2 The Instruction Cycle Specific to the LC-3......Page 205
Exercises......Page 206
6.1.1 Systematic Decomposition......Page 232
6.1.2 The Three Constructs: Sequential, Conditional, Iterative......Page 233
6.1.3 LC-3 Control Instructions to Implement the Three Constructs......Page 234
6.1.4 The Character Count Example from Chapter 5, Revisited......Page 235
6.2 Debugging......Page 239
6.2.1 Debugging Operations......Page 240
6.2.2 Use of an Interactive Debugger......Page 241
Exercises......Page 249
7.1 Assembly Language Programming—Moving Up a Level......Page 260
7.2 An Assembly Language Program......Page 261
7.2.1 Instructions......Page 262
7.2.2 Pseudo-Ops (AssemblerDirectives)......Page 265
7.2.3 Example: The Character Count Example of Section 5.5, Revisited Again!......Page 267
7.3.2 A Two-Pass Process......Page 269
7.3.3 The First Pass: Creating the Symbol Table......Page 270
7.3.4 The Second Pass: Generating the Machine Language Program......Page 271
7.4 Beyond the Assembly of a Single Assembly Language Program......Page 272
7.4.2 More than One Object File......Page 273
Exercises......Page 274
8.1 Subroutines......Page 292
8.1.1 The Call/Return Mechanism......Page 294
8.1.2 JSR(R)—The Instruction That Calls the Subroutine......Page 295
8.1.3 Saving and Restoring Registers......Page 296
8.1.4 Library Routines......Page 298
8.2.2 Two Example Implementations......Page 302
8.2.3 Implementation in Memory......Page 303
8.2.4 The Complete Picture......Page 307
8.3.1 Bad Example Number 1: Factorial......Page 309
8.3.2 Fibonacci, an Even Worse Example......Page 314
8.3.3 The Maze, a Good Example......Page 317
8.4 The Queue......Page 323
8.4.2 Wrap-Around......Page 324
8.4.3 How Many Elements Can We Store in a Queue?......Page 325
8.4.4 Tests for Underflow, Overflow......Page 326
8.4.5 The Complete Story......Page 327
8.5 Character Strings......Page 329
Exercises......Page 333
9 I/O......Page 342
9.1.1 Privilege and Priority......Page 343
9.1.2 Organization of Memory......Page 345
9.2.1 Some Basic Characteristics of I/O......Page 346
9.2.2 Input from the Keyboard......Page 349
9.2.3 Output to the Monitor......Page 351
9.2.4 A More Sophisticated Input Routine......Page 354
9.2.5 Implementation of Memory-Mapped I/O, Revisited......Page 355
9.3.1 Introduction......Page 356
9.3.2 The Trap Mechanism......Page 358
9.3.3 The TRAP Instruction......Page 359
9.3.5 A Summary of the Trap Service Routine Process......Page 360
9.3.6 Trap Routines for Handling I/O......Page 362
9.3.7 A Trap Routine for Halting the Computer......Page 364
9.3.8 The Trap Routine for Character Input (One Last Time)......Page 365
9.3.9 PUTS: Writing a Character String to the Monitor......Page 367
9.4.1 What Is Interrupt-Driven I/O?......Page 368
9.4.2 Why Have Interrupt-Driven I/O?......Page 369
9.4.4 Part I: Causing the Interrupt to Occur......Page 370
9.4.5 Part II: Handling the Interrupt Request......Page 373
9.4.6 An Example......Page 376
9.4.7 Not Just I/O Devices......Page 378
9.5.1 The Problem......Page 379
9.5.2 The Solution......Page 380
Exercises......Page 381
10 A Calculator......Page 408
10.1 Data Type Conversion......Page 409
10.1.2 Input Data (ASCII to Binary)......Page 410
10.1.3 Display Result (Binary to ASCII)......Page 414
10.2.1 The Stack as Temporary Storage......Page 416
10.2.2 An Example......Page 417
10.2.3 OpAdd, OpMult, and OpNeg......Page 418
10.3.1 Functionality......Page 424
10.3.2 Code......Page 425
Exercises......Page 431
11.1 Our Objective......Page 434
11.2 Bridging the Gap......Page 435
11.3.1 Interpretation......Page 439
11.4.1 The Origins of C and C++......Page 440
11.4.2 How We Will Approach C and C++......Page 441
11.4.3 The Compilation Process......Page 442
11.5.1 The Function main......Page 444
11.5.2 Formatting, Comments, and Style......Page 446
11.5.3 The C Preprocessor......Page 447
11.5.4 Input and Output......Page 448
Exercises......Page 451
12.2 Variables......Page 454
12.2.1 Four Basic Data Types......Page 455
12.2.3 Scope: Local vs. Global......Page 458
12.2.4 More Examples......Page 460
12.3 Operators......Page 461
12.3.2 The Assignment Operator......Page 462
12.3.3 Arithmetic Operators......Page 463
12.3.4 Order of Evaluation......Page 464
12.3.5 Bitwise Operators......Page 465
12.3.6 Relational Operators......Page 466
12.3.7 Logical Operators......Page 467
12.3.8 Increment /Decrement Operators......Page 468
12.4 Problem Solving Using Operators......Page 470
12.5.1 Symbol Table......Page 473
12.5.2 Allocating Space for Variables......Page 474
12.5.3 A Comprehensive Example......Page 476
12.6 Additional Topics......Page 478
12.6.1 Variations of the Basic Types......Page 479
12.6.2 Literals, Constants, and Symbolic Values......Page 480
12.6.3 Additional C Operators......Page 481
Exercises......Page 482
13.2 Conditional Constructs......Page 486
13.2.1 The if Statement......Page 487
13.2.2 The if-else Statement......Page 489
13.3.1 The while Statement......Page 493
13.3.2 The for Statement......Page 495
13.3.3 The do-while Statement......Page 500
13.4.1 Problem 1: Approximating the Value of ��......Page 501
13.4.2 Problem 2: Finding Prime Numbers Less Than 100......Page 503
13.4.3 Problem 3: Analyzing an E-mail Address......Page 506
13.5.1 The switch Statement......Page 509
13.5.3 An Example: Simple Calculator......Page 511
Exercises......Page 513
14.1 Introduction......Page 520
14.2.1 A Function with a Parameter......Page 521
14.2.2 Example: Area of a Ring......Page 524
14.3.1 Run-Time Stack......Page 526
14.3.2 Getting It All to Work......Page 529
14.3.3 Tying It All Together......Page 534
14.4.1 Problem 1: Case Conversion......Page 536
14.4.2 Problem 2: Pythagorean Triples......Page 537
14.5 Summary......Page 539
Exercises......Page 540
15.1 Introduction......Page 546
15.2 Types of Errors......Page 547
15.2.2 Semantic Errors......Page 548
15.2.3 Algorithmic Errors......Page 550
15.2.4 Specification Errors......Page 551
15.3 Testing......Page 552
15.3.2 White-Box Testing......Page 553
15.4 Debugging......Page 554
15.4.2 Source-Level Debuggers......Page 555
15.5 Programming for Correctness......Page 557
15.5.2 Modular Design......Page 558
15.5.3 Defensive Programming......Page 559
15.6 Summary......Page 560
Exercises......Page 561
16.2 Pointers......Page 566
16.2.1 Declaring Pointer Variables......Page 568
16.2.2 Pointer Operators......Page 569
16.2.3 Passing a Reference Using Pointers......Page 570
16.2.5 Demystifying the Syntax......Page 572
16.2.6 An Example Problem Involving Pointers......Page 573
16.3 Arrays......Page 574
16.3.1 Declaring and Using Arrays......Page 575
16.3.2 Examples Using Arrays......Page 576
16.3.3 Arrays as Parameters......Page 579
16.3.4 Strings in C......Page 581
16.3.5 The Relationship Between Arrays and Pointers in C......Page 583
16.3.6 Problem Solving: Insertion Sort......Page 585
16.3.8 Variable-Length Arrays......Page 588
16.3.9 Multidimensional Arrays in C......Page 590
Exercises......Page 592
17.1 Introduction......Page 598
17.2 What Is Recursion?......Page 599
17.3 Recursion vs. Iteration......Page 600
17.4 Towers of Hanoi......Page 601
17.5 Fibonacci Numbers......Page 605
17.6 Binary Search......Page 610
17.7 Escaping a Maze......Page 612
17.8 Summary......Page 615
Exercises......Page 616
18.2 The C Standard Library......Page 622
18.3.1 I/O Streams......Page 623
18.3.4 Buffered I/O......Page 624
18.4.1 printf......Page 626
18.4.2 scanf......Page 628
18.4.3 Variable Argument Lists......Page 630
18.5 I/O from Files......Page 631
Exercises......Page 634
19.1 Introduction......Page 636
19.2 Structures......Page 637
19.2.1 typedef......Page 639
19.3 Arrays of Structures......Page 640
19.4 Dynamic Memory Allocation......Page 643
19.4.1 Dynamically Sized Arrays......Page 645
19.5 Linked Lists......Page 647
19.5.1 Support Functions......Page 649
19.5.2 Adding a Node to a Linked List......Page 651
19.5.3 Deleting Node from a Linked List......Page 654
19.5.4 Arrays vs. Linked Lists......Page 655
19.6 Summary......Page 657
Exercises......Page 658
20.1 Essential C++......Page 662
20.2.1 Compiling C++ Code......Page 663
20.2.3 Input and Output......Page 665
20.2.4 Pass by Reference......Page 666
20.2.5 Function Overloading......Page 667
20.3 Classes......Page 668
20.3.1 Methods......Page 669
20.3.2 Access Specifiers......Page 671
20.3.3 Constructors......Page 673
20.3.4 Advanced Topics......Page 674
20.4.1 Vectors......Page 676
20.5 Summary......Page 678
Exercises......Page 679
A.1 Overview......Page 682
A.2 The Instruction Set......Page 684
A.3 Interrupt and Exception Processing......Page 704
A.3.2 Exceptions......Page 705
B From LC-3 to x86......Page 708
B.1.1 Instruction Set......Page 709
B.1.2 Memory......Page 714
B.1.3 Internal State......Page 716
B.2 The Format and Specification of x86 Instructions......Page 719
B.2.2 Opcode......Page 720
B.2.3 ModR/M Byte......Page 721
B.2.6 Immediate......Page 722
B.3 An Example......Page 724
C.1 Overview......Page 728
C.2 The State Machine......Page 730
C.3 The Data Path......Page 732
C.4 The Control Structure......Page 735
C.5 The TRAP Instruction......Page 739
C.6 Memory-Mapped I/O......Page 740
C.7 Interrupt and Exception Control......Page 741
C.7.1 Initiating an Interrupt......Page 743
C.7.3 Initiating an Exception......Page 746
C.8 Control Store......Page 748
D.2.2 Header Files......Page 750
D.2.4 Literals......Page 751
D.2.6 Keywords......Page 753
D.3.1 Basic Data Types......Page 754
D.3.2 Type Qualifiers......Page 755
D.3.4 Derived Types......Page 757
D.4.1 Variable Declarations......Page 760
D.4.2 Function Declarations......Page 761
D.5.1 Assignment Operators......Page 762
D.5.3 Bit-Wise Operators......Page 763
D.5.5 Relational Operators......Page 764
D.5.7 Conditional Expression Operators......Page 765
D.5.8 Pointer, Array, and Structure Operators......Page 766
D.5.10 Order of Evaluation......Page 767
D.5.11 Type Conversions......Page 768
D.6.2 Statements......Page 769
D.7.2 If-else......Page 770
D.7.3 Switch......Page 771
D.7.5 For......Page 772
D.7.7 Break......Page 773
D.7.9 return......Page 774
D.8.1 Macro Substitution......Page 775
D.9.1 I/O Functions......Page 776
D.9.2 String Functions......Page 778
D.9.4 Utility Functions......Page 779
E.1 Commonly Used Numerical Prefixes......Page 782
E.2 Standard ASCII codes......Page 783
E.3 Powers of 2......Page 784
F Solutions to Selected Exercises......Page 786