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

Cover
Title Page
Copyright Page
Dedication
Contents
Acknowledgments
Preface
1 Welcome Aboard
1.1 What We Will Try to Do
1.2 How We Will Get There
1.3 Two Recurring Themes
1.3.1 The Notion of Abstraction
1.3.2 Hardware vs. Software
1.4 A Computer System
1.4.1 A (Very) Little History for a (Lot) Better Perspective
1.4.2 The Parts of a Computer System
1.5 Two Very Important Ideas
1.6 Computers as Universal Computational Devices
1.7 How Do We Get the Electrons to Do the Work?
1.7.1 The Statement of the Problem
1.7.2 The Algorithm
1.7.3 The Program
1.7.4 The ISA
1.7.5 The Microarchitecture
1.7.6 The Logic Circuit
1.7.7 The Devices
Exercises
2 Bits, Data Types, and Operations
2.1 Bits and Data Types
2.1.1 The Bit as the Unit of Information
2.1.2 Data Types
2.2 Integer Data Types
2.2.1 Unsigned Integers
2.2.2 Signed Integers
2.3 2’s Complement Integers
2.4 Conversion Between Binary and Decimal
2.4.1 Binary to Decimal Conversion
2.4.2 Decimal to Binary Conversion
2.4.3 Extending Conversion to Numbers with Fractional Parts
2.5 Operations on Bits—Part I: Arithmetic
2.5.1 Addition and Subtraction
2.5.2 Sign-Extension
2.5.3 Overflow
2.6 Operations on Bits—Part II: Logical Operations
2.6.1 A Logical Variable
2.6.2 The AND Function
2.6.3 The OR Function
2.6.4 The NOT Function
2.6.5 The Exclusive-OR Function
2.6.6 DeMorgan’s Laws
2.6.7 The Bit Vector
2.7 Other Representations
2.7.1 Floating Point Data Type (Greater Range, Less Precision)
2.7.2 ASCII Codes
2.7.3 Hexadecimal Notation
Exercises
3 Digital Logic Structures
3.1 The Transistor
3.2 Logic Gates
3.2.1 The NOT Gate (Inverter)
3.2.2 OR and NOR Gates
3.2.3 Why We Can’t Simply Connect P-Type to Ground
3.2.4 AND and NAND Gates
3.2.5 Gates with More Than Two Inputs
3.3 Combinational Logic Circuits
3.3.1 Decoder
3.3.2 Mux
3.3.3 A One-Bit Adder (a.k.a. a Full Adder)
3.3.4 The Programmable Logic Array (PLA)
3.3.5 Logical Completeness
3.4 Basic Storage Elements
3.4.1 The R-S Latch
3.4.2 The Gated D Latch
3.5 The Concept of Memory
3.5.1 Address Space
3.5.2 Addressability
3.5.3 A 22-by-3-Bit Memory
3.6 Sequential Logic Circuits
3.6.1 A Simple Example: The Combination Lock
3.6.2 The Concept of State
3.6.3 The Finite State Machine and Its State Diagram
3.6.4 The Synchronous Finite State Machine
3.6.5 The Clock
3.6.6 Example: A Danger Sign
3.7 Preview of Coming Attractions: The Data Path of the LC-3
Exercises
4 The von Neumann Model
4.1 Basic Components
4.1.1 Memory
4.1.2 Processing Unit
4.1.3 Input and Output
4.1.4 Control Unit
4.2 The LC-3: An Example von Neumann Machine
4.3 Instruction Processing
4.3.1 The Instruction
4.3.2 The Instruction Cycle (NOT the Clock Cycle!)
4.3.3 Changing the Sequence of Execution
4.3.4 Control of the Instruction Cycle
4.3.5 Halting the Computer (the TRAP Instruction)
4.4 Our First Program: A Multiplication Algorithm
Exercises
5 The LC-3
5.1 The ISA: Overview
5.1.1 Memory Organization
5.1.2 Registers
5.1.3 The Instruction Set
5.1.4 Opcodes
5.1.5 Data Types
5.1.6 Addressing Modes
5.1.7 Condition Codes
5.2 Operate Instructions
5.2.1 ADD, AND, and NOT
5.2.2 Immediates
5.2.3 The LEA Instruction (Although Not Really an Operate)
5.3 Data Movement Instructions
5.3.1 PC-Relative Mode
5.3.2 Indirect Mode
5.3.3 Base+offset Mode
5.3.4 An Example
5.4 Control Instructions
5.4.1 Conditional Branches
5.4.2 Two Methods of Loop Control
5.4.3 The JMP Instruction
5.4.4 The TRAP Instruction
5.5 Another Example: Counting Occurrences of a Character
5.6 The Data Path Revisited
5.6.1 Basic Components of the Data Path
5.6.2 The Instruction Cycle Specific to the LC-3
Exercises
6 Programming
6.1 Problem Solving
6.1.1 Systematic Decomposition
6.1.2 The Three Constructs: Sequential, Conditional, Iterative
6.1.3 LC-3 Control Instructions to Implement the Three Constructs
6.1.4 The Character Count Example from Chapter 5, Revisited
6.2 Debugging
6.2.1 Debugging Operations
6.2.2 Use of an Interactive Debugger
Exercises
7 Assembly Language
7.1 Assembly Language Programming—Moving Up a Level
7.2 An Assembly Language Program
7.2.1 Instructions
7.2.2 Pseudo-Ops (AssemblerDirectives)
7.2.3 Example: The Character Count Example of Section 5.5, Revisited Again!
7.3 The Assembly Process
7.3.1 Introduction
7.3.2 A Two-Pass Process
7.3.3 The First Pass: Creating the Symbol Table
7.3.4 The Second Pass: Generating the Machine Language Program
7.4 Beyond the Assembly of a Single Assembly Language Program
7.4.1 The Executable Image
7.4.2 More than One Object File
Exercises
8 Data Structures
8.1 Subroutines
8.1.1 The Call/Return Mechanism
8.1.2 JSR(R)—The Instruction That Calls the Subroutine
8.1.3 Saving and Restoring Registers
8.1.4 Library Routines
8.2 The Stack
8.2.1 The Stack—An Abstract Data Type
8.2.2 Two Example Implementations
8.2.3 Implementation in Memory
8.2.4 The Complete Picture
8.3 Recursion, a Powerful Technique When Used Appropriately
8.3.1 Bad Example Number 1: Factorial
8.3.2 Fibonacci, an Even Worse Example
8.3.3 The Maze, a Good Example
8.4 The Queue
8.4.1 The Basic Operations: Remove from Front, Insert at Rear
8.4.2 Wrap-Around
8.4.3 How Many Elements Can We Store in a Queue?
8.4.4 Tests for Underflow, Overflow
8.4.5 The Complete Story
8.5 Character Strings
Exercises
9 I/O
9.1 Privilege, Priority, and the Memory Address Space
9.1.1 Privilege and Priority
9.1.2 Organization of Memory
9.2 Input/Output
9.2.1 Some Basic Characteristics of I/O
9.2.2 Input from the Keyboard
9.2.3 Output to the Monitor
9.2.4 A More Sophisticated Input Routine
9.2.5 Implementation of Memory-Mapped I/O, Revisited
9.3 Operating System Service Routines (LC-3 Trap Routines)
9.3.1 Introduction
9.3.2 The Trap Mechanism
9.3.3 The TRAP Instruction
9.3.4 The RTI Instruction: To Return Control to the Calling Program
9.3.5 A Summary of the Trap Service Routine Process
9.3.6 Trap Routines for Handling I/O
9.3.7 A Trap Routine for Halting the Computer
9.3.8 The Trap Routine for Character Input (One Last Time)
9.3.9 PUTS: Writing a Character String to the Monitor
9.4 Interrupts and Interrupt-Driven I/O
9.4.1 What Is Interrupt-Driven I/O?
9.4.2 Why Have Interrupt-Driven I/O?
9.4.3 Two Parts to the Process
9.4.4 Part I: Causing the Interrupt to Occur
9.4.5 Part II: Handling the Interrupt Request
9.4.6 An Example
9.4.7 Not Just I/O Devices
9.5 Polling Revisited, Now That We Know About Interrupts
9.5.1 The Problem
9.5.2 The Solution
Exercises
10 A Calculator
10.1 Data Type Conversion
10.1.1 Example: A Bogus Program: 2 + 3 = e
10.1.2 Input Data (ASCII to Binary)
10.1.3 Display Result (Binary to ASCII)
10.2 Arithmetic Using a Stack
10.2.1 The Stack as Temporary Storage
10.2.2 An Example
10.2.3 OpAdd, OpMult, and OpNeg
10.3 The Calculator
10.3.1 Functionality
10.3.2 Code
Exercises
11 Introduction to C/C++ Programming
11.1 Our Objective
11.2 Bridging the Gap
11.3 Translating High-Level Language Programs
11.3.1 Interpretation
11.3.2 Compilation
11.3.3 Pros and Cons
11.4 The C/C++ Programming Languages
11.4.1 The Origins of C and C++
11.4.2 How We Will Approach C and C++
11.4.3 The Compilation Process
11.4.4 Software Development Environments
11.5 A Simple Example in C
11.5.1 The Function main
11.5.2 Formatting, Comments, and Style
11.5.3 The C Preprocessor
11.5.4 Input and Output
11.6 Summary
Exercises
12 Variables and Operators
12.1 Introduction
12.2 Variables
12.2.1 Four Basic Data Types
12.2.2 Choosing Identifiers
12.2.3 Scope: Local vs. Global
12.2.4 More Examples
12.3 Operators
12.3.1 Expressions and Statements
12.3.2 The Assignment Operator
12.3.3 Arithmetic Operators
12.3.4 Order of Evaluation
12.3.5 Bitwise Operators
12.3.6 Relational Operators
12.3.7 Logical Operators
12.3.8 Increment /Decrement Operators
12.3.9 Expressions with Multiple Operators
12.4 Problem Solving Using Operators
12.5 Tying It All Together
12.5.1 Symbol Table
12.5.2 Allocating Space for Variables
12.5.3 A Comprehensive Example
12.6 Additional Topics
12.6.1 Variations of the Basic Types
12.6.2 Literals, Constants, and Symbolic Values
12.6.3 Additional C Operators
12.7 Summary
Exercises
13 Control Structures
13.1 Introduction
13.2 Conditional Constructs
13.2.1 The if Statement
13.2.2 The if-else Statement
13.3 Iteration Constructs
13.3.1 The while Statement
13.3.2 The for Statement
13.3.3 The do-while Statement
13.4 Problem Solving Using Control Structures
13.4.1 Problem 1: Approximating the Value of ?
13.4.2 Problem 2: Finding Prime Numbers Less Than 100
13.4.3 Problem 3: Analyzing an E-mail Address
13.5 Additional C Control Structures
13.5.1 The switch Statement
13.5.2 The break and continue Statements
13.5.3 An Example: Simple Calculator
13.6 Summary
Exercises
14 Functions
14.1 Introduction
14.2 Functions in C
14.2.1 A Function with a Parameter
14.2.2 Example: Area of a Ring
14.3 Implementing Functions in C
14.3.1 Run-Time Stack
14.3.2 Getting It All to Work
14.3.3 Tying It All Together
14.4 Problem Solving Using Functions
14.4.1 Problem 1: Case Conversion
14.4.2 Problem 2: Pythagorean Triples
14.5 Summary
Exercises
15 Testing and Debugging
15.1 Introduction
15.2 Types of Errors
15.2.1 Syntactic Errors
15.2.2 Semantic Errors
15.2.3 Algorithmic Errors
15.2.4 Specification Errors
15.3 Testing
15.3.1 Black-Box Testing
15.3.2 White-Box Testing
15.4 Debugging
15.4.1 Ad Hoc Techniques
15.4.2 Source-Level Debuggers
15.5 Programming for Correctness
15.5.1 Nailing Down the Specifications
15.5.2 Modular Design
15.5.3 Defensive Programming
15.6 Summary
Exercises
16 Pointers and Arrays
16.1 Introduction
16.2 Pointers
16.2.1 Declaring Pointer Variables
16.2.2 Pointer Operators
16.2.3 Passing a Reference Using Pointers
16.2.4 Null Pointers
16.2.5 Demystifying the Syntax
16.2.6 An Example Problem Involving Pointers
16.3 Arrays
16.3.1 Declaring and Using Arrays
16.3.2 Examples Using Arrays
16.3.3 Arrays as Parameters
16.3.4 Strings in C
16.3.5 The Relationship Between Arrays and Pointers in C
16.3.6 Problem Solving: Insertion Sort
16.3.7 Common Pitfalls with Arrays in C
16.3.8 Variable-Length Arrays
16.3.9 Multidimensional Arrays in C
16.4 Summary
Exercises
17 Recursion
17.1 Introduction
17.2 What Is Recursion?
17.3 Recursion vs. Iteration
17.4 Towers of Hanoi
17.5 Fibonacci Numbers
17.6 Binary Search
17.7 Escaping a Maze
17.8 Summary
Exercises
18 I/O in C
18.1 Introduction
18.2 The C Standard Library
18.3 I/O, One Character at a Time
18.3.1 I/O Streams
18.3.2 putchar
18.3.3 getchar
18.3.4 Buffered I/O
18.4 Formatted I/O
18.4.1 printf
18.4.2 scanf
18.4.3 Variable Argument Lists
18.5 I/O from Files
18.6 Summary
Exercises
19 Dynamic Data Structures in C
19.1 Introduction
19.2 Structures
19.2.1 typedef
19.2.2 Implementing Structures in C
19.3 Arrays of Structures
19.4 Dynamic Memory Allocation
19.4.1 Dynamically Sized Arrays
19.5 Linked Lists
19.5.1 Support Functions
19.5.2 Adding a Node to a Linked List
19.5.3 Deleting Node from a Linked List
19.5.4 Arrays vs. Linked Lists
19.6 Summary
Exercises
20 Introduction to C++
20.1 Essential C++
20.2 Going from C to C++
20.2.1 Compiling C++ Code
20.2.2 Namespaces
20.2.3 Input and Output
20.2.4 Pass by Reference
20.2.5 Function Overloading
20.2.6 Dynamic Allocation
20.2.7 Compilation to Machine Version
20.3 Classes
20.3.1 Methods
20.3.2 Access Specifiers
20.3.3 Constructors
20.3.4 Advanced Topics
20.4 Containers and Templates
20.4.1 Vectors
20.4.2 Templates
20.5 Summary
Exercises
A The LC-3 ISA
A.1 Overview
A.2 The Instruction Set
A.3 Interrupt and Exception Processing
A.3.1 Interrupts
A.3.2 Exceptions
B From LC-3 to x86
B.1 LC-3 Features and Corresponding x86 Features
B.1.1 Instruction Set
B.1.2 Memory
B.1.3 Internal State
B.2 The Format and Specification of x86 Instructions
B.2.1 Prefix
B.2.2 Opcode
B.2.3 ModR/M Byte
B.2.4 SIB Byte
B.2.5 Displacement
B.2.6 Immediate
B.3 An Example
C The Microarchitecture of the LC-3
C.1 Overview
C.2 The State Machine
C.3 The Data Path
C.4 The Control Structure
C.5 The TRAP Instruction
C.6 Memory-Mapped I/O
C.7 Interrupt and Exception Control
C.7.1 Initiating an Interrupt
C.7.2 Returning from an Interrupt or Trap Service Routine, RTI
C.7.3 Initiating an Exception
C.8 Control Store
D The C Programming Language
D.1 Overview
D.2 C Conventions
D.2.1 Source Files
D.2.2 Header Files
D.2.3 Comments
D.2.4 Literals
D.2.5 Formatting
D.2.6 Keywords
D.3 Types
D.3.1 Basic Data Types
D.3.2 Type Qualifiers
D.3.3 Storage Class
D.3.4 Derived Types
D.3.5 typedef
D.4 Declarations
D.4.1 Variable Declarations
D.4.2 Function Declarations
D.5 Operators
D.5.1 Assignment Operators
D.5.2 Arithmetic Operators
D.5.3 Bit-Wise Operators
D.5.4 Logical Operators
D.5.5 Relational Operators
D.5.6 Increment/Decrement Operators
D.5.7 Conditional Expression Operators
D.5.8 Pointer, Array, and Structure Operators
D.5.9 sizeof
D.5.10 Order of Evaluation
D.5.11 Type Conversions
D.6 Expressions and Statements
D.6.1 Expressions
D.6.2 Statements
D.7 Control
D.7.1 If
D.7.2 If-else
D.7.3 Switch
D.7.4 While
D.7.5 For
D.7.6 Do-while
D.7.7 Break
D.7.8 continue
D.7.9 return
D.8 The C Preprocessor
D.8.1 Macro Substitution
D.8.2 File Inclusion
D.9 Some Standard Library Functions
D.9.1 I/O Functions
D.9.2 String Functions
D.9.3 Math Functions
D.9.4 Utility Functions
E Useful Tables
E.1 Commonly Used Numerical Prefixes
E.2 Standard ASCII codes
E.3 Powers of 2
F Solutions to Selected Exercises