1 Welcome Aboard 1
1.1 What We Will Tryto Do 1
1.2 How We Will Get There 2
1.3 Two Recurring Themes 3
1.3.1 The Notion of Abstraction 3
1.3.2 Hardware versus Software 5
1.4 A Computer System 7
1.5 Two Very Important Ideas 9
1.6 Computers as Universal Computational Devices 9
1.7 How Do We Get the Electrons to Do the Work？ 12
1.7.1 The Statement of the Problem 13
1.7.2 The Algorithm 13
1.7.3 The Program 14
1.7.4 The ISA 14
1.7.5 The Microarchitecture 15
1.7.6 The Logic Circuit 16
1.7.7 The Devices 16
1.7.8 Putting It Together 16
Exercises 17
2 Bits， Data Types， and Operations 21
2.1 Bits and Data Types 21
2.1.1 The Bit as the Unit of Information 21
2.1.2 Data Types 22
2.2 Integer Data Types 23
2.2.1 Unsigned Integers 23
2.2.2 Signed Integers 23
2.3 2’s Complement Integers 25
2.4 Binary-Decimal Conversion 27
2.4.1 Binary to Decimal Conversion 27
2.4.2 Decimal to Binary Conversion 28
2.5 Operations on Bits-Part Ⅰ：Arithmetic 29
2.5.1 Addition and Subtraction 29
2.5.2 Sign-Extension 30
2.5.3 Overflow 31
2.6 Operations on Bits-Part Ⅱ：Logical Operations 33
2.6.1 The AND Function 33
2.6.2 The OR Function 34
2.6.3 The NOT Function 35
2.6.4 The Exclusive-OR Function 35
2.7 Other Representations 36
2.7.1 The Bit Vector 36
2.7.2 Floating Point Data Type 37
2.7.3 ASCII Codes 40
2.7.4 Hexadecimal Notation 41
Exercises 43
3 Digital Logic Structures 51
3.1 The Transistor 51
3.2 Logic Gates 53
3.2.1 The NOT Gate （Inverter） 53
3.2.2 OR and NOR Gates 54
3.2.3 AND and NAND Gates 56
3.2.4 DeMorgan’s Law 58
3.2.5 Larger Gates 58
3.3 Combinational Logic Circuits 59
3.3.1 Decoder 59
3.3.2 Mux 60
3.3.3 Full Adder 61
3.3.4 The Programmable Logic Array（PLA） 63
3.3.5 Logical Completeness 64
3.4 Basic Storage Elements 64
3.4.1 The R-S Latch 64
3.4.2 The Gated D Latch 66
3.4.3 A Register 66
3.5 The Concept of Memory 67
3.5.1 Address Space 68
3.5.2 Addressability 68
3.5.3 A 2 2-by-3-Bit Memory 68
3.6 Sequential Logic Circuits 70
3.6.1 A Simple Example：The Combination Lock 71
3.6.2 The Concept of State 72
3.6.3 Finite State Machines 74
3.6.4 An Example：The Complete Implementation of a Finite State Machine 77
3.7 The Data Path of the LC-3 80
Exercises 82
4 The von Neumann Model 97
4.1 Basic Components 97
4.1.1 Memory 98
4.1.2 Processing Unit 99
4.1.3 Input and Output 100
4.1.4 Control Unit 100
4.2 The LC-3：An Example von Neumann Machine 101
4.3 Instruction Processing 103
4.3.1 The Instruction 103
4.3.2 The Instruction Cycle 104
4.4 Changing the Sequence of Execution 107
4.4.1 Control of the Instruction Cycle 108
4.5 Stopping the Computer 110
Exercises 111
5 The LC-3 115
5.1 The ISA：Overview 115
5.1.1 Memory Organization 116
5.1.2 Registers 116
5.1.3 The Instruction Set 117
5.1.4 Opcodes 117
5.1.5 Data Types 118
5.1.6 Addressing Modes 118
5.1.7 Condition Codes 120
5.2 Operate Instructions 120
5.3 Data Movement Instructions 123
5.3.1 PC-Relative Mode 124
5.3.2 Indirect Mode 125
5.3.3 Base+offset Mode 127
5.3.4 Immediate Mode 128
5.3.5 An Example 129
5.4 Control Instructions 130
5.4.1 Conditional Branches 131
5.4.2 An Example 132
5.4.3 Two Methods for Loop Control 135
5.4.4 Example： Adding a Column of Numbers Using a Sentinel 135
5.4.5 The JMP Instruction 136
5.4.6 The TRAP Instruction 137
5.5 Another Example： Counting Occurrences of a Character 138
5.6 The Data Path Revisited 141
5.6.1 Basic Components of the Data Path 141
5.6.2 The Instruction Cycle 144
Exercises 145
6 Programming 155
6.1 Problem Solving 155
6.1.1 Systematic Decomposition 155
6.1.2 The Three Constructs：Sequential，Conditional，Iterative 156
6.1.3 LC-3 Control Instructions to Implement the Three Constructs 157
6.1.4 The Character Count Example from Chapter 5，Revisited 158
6.2 Debugging 162
6.2.1 Debugging Operations 163
6.2.2 Examples： Use of the Interactive Debugger 164
Exercises 172
7 Assembly Language 177
7.1 Assembly Language Programming-Moving Up a Level 177
7.2 An Assembly Language Program 178
7.2.1 Instructions 179
7.2.2 Pseudo-ops （Assembler Directives） 182
7.2.3 Example： The Character Count Example of Section 5.5，Revisited 183
7.3 The Assembly Process 185
7.3.1 Introduction 185
7.3.2 A Two-Pass Process 185
7.3.3 The First Pass： Creating the Symbol Table 186
7.3.4 The Second Pass： Generating the Machine Language Program 187
7.4 Beyond the Assembly of a Single Assembly Language Program 188
7.4.1 The Executable Image 189
7.4.2 More than One Object File 189
Exercises 190
8 I/O 199
8.1 I/O Basics 199
8.1.1 Device Registers 199
8.1.2 Memory-Mapped I/O versus Special Input/Output Instructions 200
8.1.3 Asynchronous versus Synchronous 200
8.1.4 Interrupt-Driven versus Palling 202
8.2 Input from the Keyboard 202
8.2.1 Basic Input Registers （the KBDR and the KBSR） 202
8.2.2 The Basic Input Service Routine 202
8.2.3 Implementation of Memory-Mapped Input 203
8.3 Output to the Monitor 204
8.3.1 Basic Output Registers （the DDR and the DSR） 204
8.3.2 The Basic Output Service Routine 205
8.3.3 Implementation of Memory-Mapped Output 206
8.3.4 Example： Keyboard Echo 207
8.4 A More Sophisticated Input Routine 207
8.5 Interrupt-Driven I/O 209
8.5.1 What Is Interrupt-Driven I/O？ 209
8.5.2 Why Have Interrupt-Driven I/O？ 210
8.5.3 Generation of the Interrupt Signal 211
8.6 Implementation of Memory-Mapped I/O，Revisited 214
Exercises 215
9 TRAP Routines and Subroutines 219
9.1 LC-3 TRAP Routines 219
9.1.1 Introduction 219
9.1.2 The TRAP Mechanism 220
9.1.3 The TRAP Instruction 221
9.1.4 The Complete Mechanism 222
9.1.5 TRAP Routines for Handling I/O 225
9.1.6 TRAP Routine for Halting the Computer 225
9.1.7 Saving and Restoring Registers 229
9.2 Subroutines 230
9.2.1 The Call/Return Mechanism 230
9.2.2 The JSR（R） Instruction 232
9.2.3 The TRAP Routine for Character Input， Revisited 233
9.2.4 PUTS： Writing a Character String to the Monitor 235
9.2.5 Library Routines 235
Exercises 240
10 And， Finally…The Stack 251
10.1 The Stack：Its Basic Structure 251
10.1.1 The Stack-An Abstract Data Type 251
10.1.2 Two Example Implementations 252
10.1.3 Implementation in Memory 253
10.1.4 The Complete Picture 257
10.2 Interrupt-Driven I/O （Part 2） 258
10.2.1 Initiate and Service the Interrupt 259
10.2.2 Return from the Interrupt 261
10.2.3 An Example 262
10.3 Arithmetic Using a Stack 264
10.3.1 The Stack as Tempora Storage 264
10.3.2 An Example 265
10.3.3 OpAdd， OpMult， and OpNeg 265
10.4 Data Type Conversion 272
10.4.1 Example： The Bogus Program：2+3=e 272
10.4.2 ASCII to Binary 273
10.4.3 Binary to ASCII 276
10.5 Our Final Example： The Calculator 278
Exercises 283
11 Introduction to Programmingin C 289
11.1 Our Objective 289
11.2 Bridging the Gap 290
11.3 Translating High-Level Language Programs 292
11.3.1 Interpretation 292
11.3.2 Compilation 293
11.3.3 Pros and Cons 293
11.4 The C Programming Language 293
11.4.1 The C Compiler 295
11.5 A Simple Example 297
11.5.1 The Function main 297
11.5.2 Formatting， Comments，and Style 299
11.5.3 The C Preprocessor 300
11.5.4 Input and Output 301
11.6 Summary 304
Exercises 305
12 Variables and Operators 307
12.1 Introduction 307
12.2 Variables 308
12.2.1 Three Basic Data Types：int，char，double 308
12.2.2 Choosing Identifiers 310
12.2.3 Scope：Local versus Global 311
12.2.4 More Examples 313
12.3 Operators 314
12.3.1 Expressions and Statements 315
12.3.2 The Assignment Operator 316
12.3.3 Arithmetic Operators 317
12.3.4 Order of Evaluation 318
12.3.5 Bitwise Operators 319
12.3.6 Relational Operators 320
12.3.7 Logical Operators 322
12.3.8 Increment /Decrement Operators 322
12.3.9 Expressions with Multiple Operators 324
12.4 Problem Solving Using Operators 324
12.5 Tying it All Together 326
12.5.1 Symbol Table 326
12.5.2 Allocating Space for Variables 328
12.5.3 A Comprehensive Example 331
12.6 Additional Topics 332
12.6.1 Variations of the Three Basic Types 332
12.6.2 Literals，Constants，and Symbolic Values 334
12.6.3 Storage Class 335
12.6.4 Additional C Operators 336
12.7 Summary 337
Exercises 338
13 Control Structures 343
13.1 Introduction 343
13.2 Conditional Constructs 344
13.2.1 The if Statement 344
13.2.2 The if-else Statement 347
13.3 Iteration Constructs 350
13.3.1 The while Statement 350
13.3.2 The for Statement 353
13.3.3 The do-while Statement 358
13.4 Problem Solving Using Control Structures 359
13.4.1 Problem 1：Approximating the Value of π 360
13.4.2 Problem 2：Finding Prime Numbers Less than 100 362
13.4.3 Problem 3：Analyzing an E-mail Address 366
13.5 Additional C Control Structures 368
13.5.1 The switch Statement 368
13.5.2 The break and continue Statements 370
13.5.3 An Example：Simple Calculator 370
13.6 Summary 372
Exercises 372
14 Functions 379
14.1 Introduction 379
14.2 Functions in C 380
14.2.1 A Function with a Parameter 380
14.2.2 Example： Area of a Ring 384
14.3 Implementing Functions in C 385
14.3.1 Run-Time Stack 385
14.3.2 Getting It All to Work 388
14.3.3 Tying It All Together 393
14.4 Problem Solving Using Functions 394
14.4.1 Problem 1：Case Conversion 395
14.4.2 Problem 2：Pythagorean Triples 397
14.5 Summary 398
Exercises 399
15 Testing and Debugging 407
15.1 Introduction 407
15.2 Types of Errors 408
15.2.1 Syntactic Errors 409
15.2.2 Semantic Errors 409
15.2.3 Algorithmic Errors 411
15.3 Testing 412
15.3.1 Black-Box Testing 412
15.3.2 White-Box Testing 413
15.4 Debugging 414
15.4.1 Ad Hoc Techniques 414
15.4.2 Source-Level Debuggers 415
15.5 Programming for Correctness 417
15.5.1 Nailing Down the Specification 417
15.5.2 Modular Design 418
15.5.3 Defensive Programming 418
15.6 Summary 419
Exercises 421
16 Pointers and Arrays 427
16.1 Introduction 427
16.2 Pointers 428
16.2.1 Declaring Polnter Variables 429
16.2.2 Pointer Operators 430
16.2.3 Passing a Reference Using Pointers 432
16.2.4 Null Pointers 433
16.2.5 Demystifying the Syntax 434
16.2.6 An Example Problem Involving Pointers 434
16.3 Arrays 436
16.3.1 Declaring and Using Arrays 436
16.3.2 Examples Using Arrays 438
16.3.3 Arrays as Parameters 440
16.3.4 Strings in C 441
16.3.5 The Relationship Between Arrays and Pointers in C 446
16.3.6 Problem Solving：Insertion Sort 446
16.3.7 Common Pitfalls with Arrays in C 449
16.4 Summary 451
Exercises 451
17 Recursion 457
17.1 Introduction 457
17.2 What Is Recursion？ 458
17.3 Recursion versus Iteration 459
17.4 Towers of Hanoi 460
17.5 Fibonacci Numbers 464
17.6 Binary Search 468
17.7 Integer to ASCII 471
17.8 Summary 473
Exercises 473
18 I/O i n C 481
18.1 Introduction 481
18.2 The C Standard Library 481
18.3 I/O，One Character at a Time 482
18.3.1 I/O Streams 482
18.3.2 putchar 483
18.3.3 getchar 463
18.3.4 Buffered I/O 483
18.4 Formatted I/O 485
18.4.1 printf 485
18.4.2 scanf 487
18.4.3 Variable Argument Lists 489
18.5 I/O from Files 491
18.6 Summary 493
Exercises 494
19 Data Structures 497
19.1 Introduction 497
19.2 Structures 498
19.2.1 typedef 500
19.2.2 Implementing Structures in C 501
19.3 Arrays of Structures 502
19.4 Dynamic Memory Allocation 504
19.4.1 Dynamically Sized Arrays 506
19.5 Linked Lists 508
19.5.1 An Example 510
19.6 Summary 516
Exercises 517
A The LC-3 ISA 521
A.1 Overview 521
A.2 Notation 523
A.3 The Instruction Set 523
A.4 Interrupt and Exception Processing 543
A.4.1 Interrupts 543
A.4.2 Exceptions 544
B From LC-3 to x86 547
B.1 LC-3 Features and Corresponding x86Features 548
B.1.1 Instruction Set 548
B.1.2 Memory 553
B.1.3 Internal State 553
B.2 The Format and Specification of x86Instructions 557
B.2.1 Prefix 558
B.2.2 Opcode 559
B.2.3 ModR/M Byte 559
B.2.4 SIB Byte 560
B.2.5 Displacement 560
B.2.6 Immediate 560
B.3 An Example 562
C The Microarchitecture of the LC-3 565
C.1 Overview 565
C.2 The State Machine 567
C.3 The Data Path 569
C.4 The Control Structure 569
C.5 Memory-Mapped I/O 575
C.6 Interrupt and Exception Control 576
C.6.1 Initiating an Interrupt 579
C.6.2 Returning from an Interrupt，RTI 581
C.6.3 The Illegal Opcode Exception 582
C.7 Control Store 583
D The C Programming Language 585
D.1 Overview 585
D.2 C Conventions 585
D.2.1 Source Files 585
D.2.2 Header Files 585
D.2.3 Comments 586
D.2.4 Literals 586
D.2.5 Formatting 588
D.2.6 Keywords 588
D.3 Types 589
D.3.1 Basic Data Types 589
D.3.2 Type Qualifiers 590
D.3.3 Storage Class 591
D.3.4 Derived Types 592
D.3.5 typedef 594
D.4 Declarations 595
D.4.1 Variable Declarations 595
D.4.2 Function Declarations 596
D.5 Operators 596
D.5.1 Assignment Operators 597
D.5.2 Arithmetic Operators 597
D.5.3 Bit-wise Operators 598
D.5.4 Logical Operators 598
D.5.5 Relational Operators 599
D.5.6 Increment/Decrement Operators 599
D.5.7 Conditional Expression 600
D.5.8 Pointer，Array，and Structure Operators 600
D.5.9 sizeof 601
D.5.10 Order of Evaluation 602
D.5.11 Type Conversions 602
D.6 Expressions and Statements 603
D.6.1 Expressions 603
D.6.2 Statements 604
D.7 Control 604
D.7.1 If 604
D.7.2 If-else 605
D.7.3 Switch 605
D.7.4 While 606
D.7.5 For 607
D.7.6 Do-while 607
D.7.7 Break 608
D.7.8 continue 608
D.7.9 return 609
D.8 The C Preprocessor 609
D.8.1 Macro substitution 609
D.8.2 File inclusion 610
D.9 Some Standard Library Functions 610
D.9.1 I/O Functions 611
D.9.2 String Functions 612
D.9.3 Math Functions 613
D.9.4 Utility Functions 613
E Useful Tables 615
E.1 Commonly Used Numerical Prefixes 615
E.2 Standard ASCII codes 616
E.3 Powers of 2 617
F Solutions to Selected Exercises 619