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

Description

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