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