Preface iv
1 Welcome Aboard 1
1.1 What We Will Tryto Do 1
1.2 How We Will Get There 1
1.3 Two Recurring Themes 3
1.3.1 The Notion of Abstraction 3
1.3.2 Hardware vs. Software 5
1.4 A Computer System 7
1.4.1 A (Very) Little History for a(Lot) Better Perspective 8
1.4.2 The Parts of a Computer System 10
1.5 Two Very Important Ideas 11
1.6 Computersas Universal Computational Devices 12
1.7 How Do We Getthe Electrons to Do the Work? 14
1.7.1 The Statement of the Problem 14
1.7.2 The Algorithm 16
1.7.3 The Program 16
1.7.4 The ISA 17
1.7.5 The Microarchitecture 18
1.7.6 The Logic Circuit 19
1.7.7 The Devices 19
Exercises 20
2 Bits, Data Types, and Operations 25
2.1 Bits and Data Types 25
2.1.1 The Bitas the Unit of Information 25
2.1.2 Data Types 26
2.2 Integer Data Types 26
2.2.1 Unsigned Integers 26
2.2.2 Signed Integers 27
2.3 2’s Complement Integers 29
2.4 Conversion Between Binary and Decimal 31
2.4.1 Binary to Decimal Conversion 31
2.4.2 Decimal to Binary Conversion 32
2.4.3 Extending Conversion to Numbers with Fractional Parts 33
2.5 Operations on Bits—Part I: Arithmetic 34
2.5.1 Addition and Subtraction 34
2.5.2 Sign-Extension 36
2.5.3 Overflow 36
2.6 Operations on Bits—Part II:Logical Operations 38
2.6.1 ALogical Variable 38
2.6.2 The AND Function 38
2.6.3 The OR Function 39
2.6.4 The NOT Function 40
2.6.5 The Exclusive-OR Function 40
2.6.6 De Morgan’s Laws 41
2.6.7 The Bit Vector 42
2.7 Other Representations 43
2.7.1 Floating Point Data Type (Greater Range, Less Precision) 43
2.7.2 ASCII Codes 47
2.7.3 Hexadecimal Notation 48
Exercises 49
3 Digital Logic Structures 59
3.1 The Transistor 59
3.2 Logic Gates 61
3.2.1 The NOT Gate (Inverter) 61
3.2.2 OR and NOR Gates 62
3.2.3 Why We Can’t Simply Connect P-Type to Ground 64
3.2.4 AND and NAND Gates 65
3.2.5 Gates with More Than Two Inputs 66
3.3 Combinational Logic Circuits 67
3.3.1 Decoder 67
3.3.2 Mux 68
3.3.3 A One-Bit Adder (a.k.a.a Full Adder) 69
3.3.4 The Programmable Logic Array(PLA)71
3.3.5 Logical Completeness 72
3.4 Basic Storage Elements 73
3.4.1 The R-S Latch 73
3.4.2 The Gated D Latch 74
3.5 The Concept of Memory 75
3.5.1 Address Space 75
3.5.2 Addressability 76
3.5.3 A22-by-3-Bit Memory 76
3.6 Sequential Logic Circuits 78
3.6.1 A Simple Example: The Combination Lock 79
3.6.2 The Concept of State 80
3.6.3 The Finite State Machine and Its State Diagram 82
3.6.4 The Synchronous Finite State Machine 85
3.6.5 The Clock 86
3.6.6 Example: A Danger Sign 87
3.7 Preview of Coming Attractions: The Data Path of the LC-3 93
Exercises 95
4 The von Neumann Model 121
4.1 Basic Components 121
4.1.1 Memory 122
4.1.2 Processing Unit123
4.1.3 Inputand Output 124
4.1.4 Control Unit 125
4.2 The LC-3: An Examplevon Neumann Machine 125
4.3 Instruction Processing 127
4.3.1 The Instruction 127
4.3.2 The Instruction Cycle (NOT the Clock Cycle!) 130
4.3.3 Changing the Sequence of Execution 132
4.3.4 Control of the Instruction Cycle 134
4.3.5 Halting the Computer (the TRAP Instruction) 136
4.4 Our First Program: A Multiplication Algorithm 137
Exercises 139
5 The LC-3 145
5.1 The ISA: Overview 145
5.1.1 Memory Organization 146
5.1.2 Registers 146
5.1.3 The Instruction Set147
5.1.4 Opcodes 149
5.1.5 Data Types 149
5.1.6 Addressing Modes 150
5.1.7 Condition Codes 150
5.2 Operate Instructions 151
5.2.1 ADD, AND, and NOT 151
5.2.2 Immediates 152
5.2.3 The LEA Instruction (Although Not Really an Operate) 154
5.3 Data Movement Instructions 155
5.3.1 PC-Relative Mode 156
5.3.2 Indirect Mode158
5.3.3 Base+offset Mode 159
5.3.4 An Example 160
5.4 Control Instructions 161
5.4.1 Conditional Branches162
5.4.2 Two Methods of Loop Control165
5.4.3 The JMP Instruction 169
5.4.4 The TRAP Instruction 169
5.5 Another Example: Counting Occurrences of a Character 170
5.6 The Data Path Revisited 173
5.6.1 Basic Components of the Data Path 175
5.6.2 The Instruction Cycle Specificto the LC-3 176
Exercises 177
6 Programming 203
6.1 Problem Solving 203
6.1.1 Systematic Decomposition 203
6.1.2 The Three Constructs: Sequential, Conditional, Iterative 204
6.1.3 LC-3 Control Instructions to Implement the Three Constructs 205
6.1.4 The Character Count Example from Chapter5, Revisited 206
6.2 Debugging 210
6.2.1 Debugging Operations 211
6.2.2 Use of an Interactive Debugger 212
Exercises 220
7 Assembly Language 231
7.1 Assembly Language Programming—Moving UpaLevel 231
7.2 An Assembly Language Program 232
7.2.1 Instructions 233
7.2.2 Pseudo-Ops (Assembler Directives) 236
7.2.3 Example: The Character Count Example of Section5.5, Revisited Again! 238
7.3 The Assembly Process 240
7.3.1 Introduction 240
7.3.2 A Two-Pass Process 240
7.3.3 The First Pass: Creating the Symbol Table 241
7.3.4 The Second Pass: Generating the Machine Language Program 242
7.4 Beyond the Assembly of a Single Assembly Language Program 243
7.4.1 The Executable Image 244
7.4.2 More than One Object File 244
Exercises 245
8 DataStructures 263
8.1 Subroutines 263
8.1.1 The Call/Return Mechanism 265
8.1.2 JSR(R)—The Instruction That Callsthe Subroutine 266
8.1.3 Saving and Restoring Registers 267
8.1.4 Library Routines 269
8.2 The Stack 273
8.2.1 The Stack—An Abstract Data Type 273
8.2.2 Two Example Implementations 273
8.2.3 Implementation in Memory 274
8.2.4 The Complete Picture 278
8.3 Recursion, a Powerful Technique When Used Appropriately 280
8.3.1 Bad Example Number 1: Factorial 280
8.3.2 Fibonacci, an Even Worse Example 285
8.3.3 The Maze, a Good Example 288
8.4 The Queue 294
8.4.1 The Basic Operations: Remove from Front, Insertat Rear 295
8.4.2 Wrap-Around 295
8.4.3 How Many Elements Can We Storeina Queue? 296
8.4.4 Tests for Underflow, Overflow 297
8.4.5 The Complete Story 298
8.5 Character Strings 300
Exercises 304
9 I/O 313
9.1 Privilege, Priority, and the Memory Address Space 314
9.1.1 Privilege and Priority 314
9.1.2 Organization of Memory 316
9.2 Input/Output 317
9.2.1 Some Basic Characteristics of I/O 317
9.2.2 Input from the Keyboard 320
9.2.3 Output to the Monitor 322
9.2.4 A More Sophisticated Input Routine 325
9.2.5 Implementation of Memory-Mapped I/O, Revisited 326
9.3 Operating System Service Routines(LC-3 Trap Routines)327
9.3.1 Introduction 327
9.3.2 The Trap Mechanism 329
9.3.3 The TRAP Instruction 330
9.3.4 The RTI Instruction: To Return Controlto the Calling Program 331
9.3.5 A Summary of the Trap Service Routine Process 331
9.3.6 Trap Routines for Handling I/O 333
9.3.7 A Trap Routine for Halting the Computer 335
9.3.8 The Trap Routine for Character Input(One Last Time)336
9.3.9 PUTS: Writinga Character String to the Monitor 338
9.4 Interrupts and Interrupt-Driven I/O 339
9.4.1 What Is Interrupt-Driven I/O? 339
9.4.2 Why Have Interrupt-Driven I/O? 340
9.4.3 Two Parts to the Process 341
9.4.4 Part I:Causing the Interrupt to Occur 341
9.4.5 Part II: Handling the Interrupt Request 344
9.4.6 An Example 347
9.4.7 Not Just I/O Devices 349
9.5 Polling Revisited, Now That We Know About Interrupts 350
9.5.1 The Problem 350
9.5.2 The Solution 351
Exercises 352
10 A Calculator 379
10.1 Data Type Conversion 380
10.1.1 Example: A Bogus Program: 2+3=e 381
10.1.2 Input Data(ASCII to Binary) 381
10.1.3 Display Result(Binary to ASCII) 385
10.2 Arithmetic Usinga Stack 387
10.2.1 The Stackas Temporary Storage 387
10.2.2 An Example 388
10.2.3 OpAdd, OpMult, and OpNeg 389
10.3 The Calculator 395
10.3.1 Functionality 395
10.3.2 Code 396
Exercises 402
11 Introduction to C/C++ Programming 405
11.1 Our Objective 405
11.2 Bridging the Gap 406
11.3 Translating High-Level Language Programs 410
11.3.1 Interpretation 410
11.3.2 Compilation 411
11.3.3 Pros and Cons 411
11.4 The C/C++ Programming Languages 411
11.4.1 The Origins of C and C++ 411
11.4.2 How We Will Approach C and C++ 412
11.4.3 The Compilation Process 413
11.4.4 Software Development Environments 415
11.5 A Simple Examplein C 415
11.5.1 The Functionmain 415
11.5.2 Formatting, Comments, and Style 417
11.5.3 The C Preprocessor 418
11.5.4 Input and Output 419
11.6 Summary 422
Exercises 422
12 Variables and Operators 425
12.1 Introduction 425
12.2 Variables 425
12.2.1 Four Basic Data Types 426
12.2.2 Choosing Identifiers 429
12.2.3 Scope: Localvs. Global 429
12.2.4 More Examples 431
12.3 Operators 432
12.3.1 Expressions and Statements 433
12.3.2 The Assignment Operator 433
12.3.3 Arithmetic Operators 434
12.3.4 Order of Evaluation 435
12.3.5 Bitwise Operators 436
12.3.6 Relational Operators 437
12.3.7 Logical Operators 438
12.3.8 Increment/Decrement Operators 439
12.3.9 Expressions with Multiple Operators 441
12.4 Problem Solving Using Operators 441
12.5 Tying It All Together 444
12.5.1 Symbol Table 444
12.5.2 Allocating Space for Variables 445
12.5.3 A Comprehensive Example447
12.6 Additional Topics 449
12.6.1 Variations of the Basic Types 450
12.6.2 Literals, Constants, and Symbolic Values 451
12.6.3 Additional C Operators 452
12.7 Summary 453
Exercises 453
13 Control Structures 457
13.1 Introduction 457
13.2 Conditional Constructs 457
13.2.1 The if Statement 458
13.2.2 Theif-else Statement 460
13.3 Iteration Constructs 464
13.3.1 The while Statement 464
13.3.2 The for Statement 466
13.3.3 Thedo-while Statement 471
13.4 Problem Solving Using Control Structures 472
13.4.1 Problem 1: Approximating the Value of π 472
13.4.2 Problem 2: Finding Prime Numbers Less Than 100 474
13.4.3 Problem 3: Analyzing an E-mail Address 477
13.5 Additional C Control Structures 480
13.5.1 The switch Statement 480
13.5.2 The break and continue Statements 482
13.5.3 An Example: Simple Calculator 482
13.6 Summary 484
Exercises 484
14 Functions 491
14.1 Introduction 491
14.2 Functionsin C 492
14.2.1 A Function with a Parameter 492
14.2.2 Example: Area of a Ring 495
14.3 Implementing Functions in C 497
14.3.1 Run-Time Stack 497
14.3.2 Getting It All to Work 500
14.3.3 Tying It All Together 505
14.4 Problem Solving Using Functions 507
14.4.1 Problem 1: Case Conversion 507
14.4.2 Problem 2: Pythagorean Triples 508
14.5 Summary 510
Exercises 511
15 Testing and Debugging 517
15.1 Introduction 517
15.2 Types of Errors 518
15.2.1 Syntactic Errors 519
15.2.2 Semantic Errors 519
15.2.3 Algorithmic Errors 521
15.2.4 Specification Errors 522
15.3 Testing 523
15.3.1 Black-Box Testing 524
15.3.2 White-Box Testing 524
15.4 Debugging 525
15.4.1 Ad Hoc Techniques 526
15.4.2 Source-Level Debuggers 526
15.5 Programming for Correctness 528
15.5.1 Nailing Downthe Specifications 529
15.5.2 Modular Design 529
15.5.3 Defensive Programming 530
15.6 Summary 531
Exercises 532
16 Pointers and Arrays 537
16.1 Introduction 537
16.2 Pointers 537
16.2.1 Declaring Pointer Variables 539
16.2.2 Pointer Operators 540
16.2.3 Passinga Reference Using Pointers 541
16.2.4 Null Pointers 543
16.2.5 Demystifying the Syntax 543
16.2.6 An Example Problem Involving Pointers 544
16.3 Arrays 545
16.3.1 Declaring and Using Arrays 546
16.3.2 Examples Using Arrays 547
16.3.3 Arraysas Parameters 550
16.3.4 Stringsin C 552
16.3.5 The Relationship Between Arrays and Pointersin C 554
16.3.6 Problem Solving: Insertion Sort 556
16.3.7 Common Pitfalls with Arrays in C 559
16.3.8 Variable-Length Arrays 559
16.3.9 Multidimensional Arrays in C 561
16.4 Summary 563
Exercises 563
17 Recursion 569
17.1 Introduction 569
17.2 What Is Recursion? 570
17.3 Recursion vs. Iteration 57
117.4 Towers of Hanoi 572
17.5 Fibonacci Numbers 576
17.6 Binary Search 581
17.7 Escapinga Maze 583
17.8 Summary 586
Exercises 587
18 I/Oin C 593
18.1 Introduction 593
18.2 The C Standard Library 593
18.3 I/O, One Character at a Time 594
18.3.1 I/O Streams 594
18.3.2 putchar 595
18.3.3 getchar 595
18.3.4 Buffered I/O 595
18.4 Formatted I/O 597
18.4.1 printf 597
18.4.2 scanf 599
18.4.3 Variable Argument Lists 601
18.5 I/O from Files 602
18.6 Summary 605
Exercises 605
19 Dynamic Data Structuresin C 607
19.1 Introduction 607
19.2 Structures 608
19.2.1 typedef 610
19.2.2 Implementing Structuresin C 611
19.3 Arrays of Structures 611
19.4 Dynamic Memory Allocation 614
19.4.1 Dynamically Sized Arrays 616
19.5 Linked Lists 618
19.5.1 Support Functions 620
19.5.2 Addinga Node to a Linked List 622
19.5.3 Deleting Node from a Linked List 625
19.5.4 Arrays vs. Linked Lists 626
19.6 Summary 628
Exercises 629
20 Introduction to C++ 633
20.1 Essential C++ 633
20.2 Going from C to C++ 634
20.2.1 Compiling C++ Code 634
20.2.2 Namespaces 636
20.2.3 Input and Output 636
20.2.4 Pass by Reference 637
20.2.5 Function Overloading 638
20.2.6 Dynamic Allocation 639
20.2.7 Compilation to Machine Version 639
20.3 Classes 639
20.3.1 Methods 640
20.3.2 Access Specifiers 642
20.3.3 Constructors 644
20.3.4 Advanced Topics 645
20.4 Containers and Templates 647
20.4.1 Vectors 647
20.4.2 Templates 649
20.5 Summary 649
Exercises 650
A The LC-3 ISA 653
A.1 Overview 653
A.2 The Instruction Set 655
A.3 Interrupt and Exception Processing 675
A.3.1 Interrupts 676
A.3.2 Exceptions 676
B From LC-3 to x86 679
B.1 LC-3 Features and Corresponding x86 Features 680
B.1.1 Instruction Set 680
B.1.2 Memory 685
B.1.3 Internal State 687
B.2 The Formatand Specification of x86 Instructions 690
B.2.1 Prefix 691
B.2.2 Opcode 691
B.2.3 Mod R/M Byte 692
B.2.4 SIB Byte 693
B.2.5 Displacement 693
B.2.6 Immediate 693
B.3 AnExample 695
C The Microarchitecture of the LC-3 699
C.1 Overview 699
C.2 The State Machine 701
C.3 The Data Path 703
C.4 The Control Structure 706
C.5 The TRAP Instruction 710
C.6 Memory-Mapped I/O7 11
C.7 Interrupt and Exception Control 712
C.7.1 Initiating an Interrupt 714
C.7.2 Returning from an Interruptor Trap Service Routine, RTI 717
C.7.3 Initiating an Exception 717
C.8 Control Store 719
D The C Programming Language 721
D.1 Overview 721
D.2 C Conventions 721
D.2.1 Source Files 721
D.2.2 Header Files 721
D.2.3 Comments 722
D.2.4 Literals 722
D.2.5 Formatting 724
D.2.6 Keywords 724
D.3 Types 725
D.3.1 Basic Data Types 725
D.3.2 Type Qualifiers 726
D.3.3 Storage Class 728
D.3.4 Derived Types 728
D.3.5 typedef 731
D.4 Declarations 731
D.4.1 Variable Declarations 731
D.4.2 Function Declarations 732
D.5 Operators 733
D.5.1 Assignment Operators 733
D.5.2 Arithmetic Operators 734
D.5.3 Bit-Wise Operators 734
D.5.4 Logical Operators 735
D.5.5 Relationa lOperators 735
D.5.6 Increment/Decrement Operators 736
D.5.7 Conditional Expression Operators 736
D.5.8 Pointer, Array, and Structure Operators 737
D.5.9 size of 738
D.5.10 Order of Evaluation 738
D.5.11 Type Conversions 739
D.6 Expressions and Statements 740
D.6.1 Expressions 740
D.6.2 Statements 740
D.7 Control 741
D.7.1 If 741
D.7.2 If-else 741
D.7.3 Switch 742
D.7.4 While 743
D.7.5 For 743
D.7.6 Do-while 744
D.7.7 Break 744
D.7.8 continue 745
D.7.9 return 745
D.8 The CPreprocessor 746
D.8.1 Macro Substitution 746
D.8.2 FileInclusion 747
D.9 Some Standard Library Functions 747
D.9.1 I/O Functions 747
D.9.2 String Functions 749
D.9.3 Math Functions 750
D.9.4 Utility Functions 750
E Useful Tables 753
E.1 Commonly Used Numerical Prefixes 753
E.2 Standard ASCII codes 754
E.3 Powers of 2 755
F Solutions to Selected Exercises 757