The Art of Assembly Language

Brief TOC 1 Full TOC 3 Why Would Anyone Learn This Stuff? 25 WhatÌs Wrong With Assembly Language 25 WhatÌs Right With Assembly Language? 28 Organization of This Text and Pedagogical Concerns 29 Obtaining Program Source Listings and Other Materials in This Text 31 1. Data Representation 33 Chapter Overview 33 Numbering Systems 33 A Review of the Decimal System 33 The Binary Numbering System 34 Binary Formats 35 Data Organization 35 Bits 36 Nibbles 36 Bytes 36 Words 37 Double Words 38 The Hexadecimal Numbering System 39 Arithmetic Operations on Binary and Hexadecimal Numbers 41 Logical Operations on Bits 42 Logical Operations on Binary Numbers and Bit Strings 44 Signed and Unsigned Numbers 45 Sign and Zero Extension 47 Shifts and Rotates 48 Bit Fields and Packed Data 50 The ASCII Character Set 50 Summary 53 Laboratory Exercises 55 Installing the Software 55 Data Conversion Exercises 56 Logical Operations Exercises 57 Sign and Zero Extension Exercises 58 Packed Data Exercises 59 Questions 60 Programming Projects 63 2. Boolean Algebra 65 Chapter Overview 65 Boolean Algebra 65 Boolean Functions and Truth Tables 67 Algebraic Manipulation of Boolean Expressions 70 Canonical Forms 71 Simplification of Boolean Functions 74 What Does This Have To Do With Computers, Anyway? 81 Correspondence Between Electronic Circuits and Boolean Functions 81 Combinatorial Circuits 82 Sequential and Clocked Logic 84 Okay, What Does It Have To Do With Programming, Then? 86 Generic Boolean Functions 87 Laboratory Exercises 91 Truth Tables and Logic Equations Exercises 92 Canonical Logic Equations Exercises 93 Optimization Exercises 94 Logic Evaluation Exercises 94 Programming Projects 99 Summary 100 Questions 102 3. System Organization 105 Chapter Overview 105 The Basic System Components 105 The System Bus 106 The Data Bus 106 The Address Bus 108 The Control Bus 108 The Memory Subsystem 109 The I/O Subsystem 114 System Timing 114 The System Clock 114 Memory Access and the System Clock 115 Wait States 117 Cache Memory 118 The 886, 8286, 8486, and 8686 ÏHypotheticalÓ Processors 121 CPU Registers 121 The Arithmetic & Logical Unit 122 The Bus Interface Unit 122 The Control Unit and Instruction Sets 122 The x86 Instruction Set 124 Addressing Modes on the x86 125 Encoding x86 Instructions 126 Step-by-Step Instruction Execution 129 The Differences Between the x86 Processors 131 The 886 Processor 132 The 8286 Processor 132 The 8486 Processor 138 The 8486 Pipeline 139 Stalls in a Pipeline 140 Cache, the Prefetch Queue, and the 8486 141 Hazards on the 8486 144 The 8686 Processor 145 I/O (Input/Output) 146 Interrupts and Polled I/O 148 Laboratory Exercises 150 The SIMx86 Program Ò Some Simple x86 Programs 150 Simple I/O-Mapped Input/Output Operations 153 Memory Mapped I/O 154 DMA Exercises 155 Interrupt Driven I/O Exercises 156 Machine Language Programming & Instruction Encoding Exercises 157 Self Modifying Code Exercises 158 Programming Projects 160 Summary 161 Questions 164 4. Memory Layout and Access 167 Chapter Overview 167 The 80x86 CPUs:A ProgrammerÌs View 167 8086 General Purpose Registers 168 8086 Segment Registers 169 8086 Special Purpose Registers 170 80286 Registers 170 80386/80486 Registers 171 80x86 Physical Memory Organization 172 Segments on the 80x86 173 Normalized Addresses on the 80x86 176 Segment Registers on the 80x86 177 The 80x86 Addressing Modes 177 8086 Register Addressing Modes 178 8086 Memory Addressing Modes 178 The Displacement Only Addressing Mode 178 The Register Indirect Addressing Modes 180 Indexed Addressing Modes 181 Based Indexed Addressing Modes 182 Based Indexed Plus Displacement Addressing Mode 182 An Easy Way to Remember the 8086 Memory Addressing Modes 184 Some Final Comments About 8086 Addressing Modes 184 80386 Register Addressing Modes 185 80386 Memory Addressing Modes 185 Register Indirect Addressing Modes 185 80386 Indexed, Base/Indexed, and Base/Indexed/Disp Addressing Modes 186 80386 Scaled Indexed Addressing Modes 187 Some Final Notes About the 80386 Memory Addressing Modes 187 The 80x86 MOV Instruction 188 Some Final Comments on the MOV Instructions 191 Laboratory Exercises 191 The UCR Standard Library for 80x86 Assembly Language Programmers 191 Editing Your Source Files 192 The SHELL.ASM File 192 Assembling Your Code with MASM 194 Debuggers and CodeViewë 195 A Quick Look at CodeView 195 The Source Window 196 The Memory Window 197 The Register Window 198 The Command Window 198 The Output Menu Item 199 The CodeView Command Window 199 The Radix Command (N) 199 The Assemble Command 200 The Compare Memory Command 200 The Dump Memory Command 202 The Enter Command 203 The Fill Memory Command 204 The Move Memory Command 204 The Input Command 205 The Output Command 205 The Quit Command 205 The Register Command 205 The Unassemble Command 206 CodeView Function Keys 206 Some Comments on CodeView Addresses 207 A Wrap on CodeView 208 Laboratory Tasks 208 Programming Projects 209 Summary 210 Questions 212 5. Variables and Data Structures 215 Chapter Overview 215 Some Additional Instructions: LEA, LES, ADD, and MUL 215 Declaring Variables in an Assembly Language Program 216 Declaring and Accessing Scalar Variables 217 Declaring and using BYTE Variables 218 Declaring and using WORD Variables 220 Declaring and using DWORD Variables 221 Declaring and using FWORD, QWORD, and TBYTE Variables 222 Declaring Floating Point Variables with REAL4, REAL8, and REAL10 222 Creating Your Own Type Names with TYPEDEF 223 Pointer Data Types 223 Composite Data Types 226 Arrays 226 Declaring Arrays in Your Data Segment 227 Accessing Elements of a Single Dimension Array 229 Multidimensional Arrays 230 Row Major Ordering 231 Column Major Ordering 235 Allocating Storage for Multidimensional Arrays 236 Accessing Multidimensional Array Elements in Assembly Language 237 Structures 238 Arrays of Structures and Arrays/Structures as Structure Fields 240 Pointers to Structures 241 Sample Programs 242 Simple Variable Declarations 242 Using Pointer Variables 244 Single Dimension Array Access 246 Multidimensional Array Access 247 Simple Structure Access 249 Arrays of Structures 251 Structures and Arrays as Fields of Another Structure 253 Pointers to Structures and Arrays of Structures 255 Laboratory Exercises 257 Programming Projects 258 Summary 259 Questions 261 6. The 80x86 Instruction Set 263 Chapter Overview 263 The Processor Status Register (Flags) 264 Instruction Encodings 265 Data Movement Instructions 266 The MOV Instruction 266 The XCHG Instruction 267 The LDS, LES, LFS, LGS, and LSS Instructions 268 The LEA Instruction 268 The PUSH and POP Instructions 269 The LAHF and SAHF Instructions 272 Conversions 272 The MOVZX, MOVSX, CBW, CWD, CWDE, and CDQ Instructions 272 The BSWAP Instruction 274 The XLAT Instruction 275 Arithmetic Instructions 275 The Addition Instructions: ADD, ADC, INC, XADD, AAA, and DAA 276 The ADD and ADC Instructions 276 The INC Instruction 278 The XADD Instruction 278 The AAA and DAA Instructions 278 The Subtraction Instructions: SUB, SBB, DEC, AAS, and DAS 279 The CMP Instruction 281 The CMPXCHG, and CMPXCHG8B Instructions 283 The NEG Instruction 283 The Multiplication Instructions: MUL, IMUL, and AAM 284 The Division Instructions: DIV, IDIV, and AAD 287 Logical, Shift, Rotate and Bit Instructions 289 The Logical Instructions: AND, OR, XOR, and NOT 289 The Shift Instructions: SHL/SAL, SHR, SAR, SHLD, and SHRD 290 SHL/SAL 291 SAR 292 SHR 293 The SHLD and SHRD Instructions 294 The Rotate Instructions: RCL, RCR, ROL, and ROR 296 RCL 297 RCR 297 ROL 298 ROR 298 The Bit Operations 299 TEST 300 The Bit Test Instructions: BT, BTS, BTR, and BTC 300 Bit Scanning: BSF and BSR 301 The ÏSet on ConditionÓ Instructions 301 I/O Instructions 304 String Instructions 304 Program Flow Control Instructions 306 Unconditional Jumps 306 The CALL and RET Instructions 309 The INT, INTO, BOUND, and IRET Instructions 312 The Conditional Jump Instructions 316 The JCXZ/JECXZ Instructions 319 The LOOP Instruction 320 The LOOPE/LOOPZ Instruction 320 The LOOPNE/LOOPNZ Instruction 321 Miscellaneous Instructions 322 Sample Programs 323 Simple Arithmetic I 323 Simple Arithmetic II 325 Logical Operations 326 Shift and Rotate Operations 328 Bit Operations and SETcc Instructions 330 String Operations 332 Conditional Jumps 333 CALL and INT Instructions 335 Conditional Jumps I 337 Conditional Jump Instructions II 338 Laboratory Exercises 340 The IBM/L System 340 IBM/L Exercises 347 Programming Projects 347 Summary 348 Questions 351 7. The UCR Standard Library 353 Chapter Overview 353 An Introduction to the UCR Standard Library 353 Memory Management Routines: MEMINIT, MALLOC, and FREE 354 The Standard Input Routines: GETC, GETS, GETSM 354 The Standard Output Routines: PUTC, PUTCR, PUTS, PUTH, PUTI, PRINT, and PRINTF 356 Formatted Output Routines: Putisize, Putusize, Putlsize, and Putulsize 360 Output Field Size Routines: Isize, Usize, and Lsize 360 Conversion Routines: ATOx, and xTOA 361 Routines that Test Characters for Set Membership 362 Character Conversion Routines: ToUpper, ToLower 363 Random Number Generation: Random, Randomize 363 Constants, Macros, and other Miscellany 364 Plus more! 364 Sample Programs 364 Stripped SHELL.ASM File 365 Numeric I/O 365 Laboratory Exercises 368 Obtaining the UCR Standard Library 368 Unpacking the Standard Library 369 Using the Standard Library 369 The Standard Library Documentation Files 370 Programming Projects 371 Summary 371 Questions 373 8. MASM: Directives & Pseudo-Opcodes 375 Chapter Overview 375 Assembly Language Statements 375 The Location Counter 377 Symbols 378 Literal Constants 379 Integer Constants 380 String Constants 381 Real Constants 381 Text Constants 382 Declaring Manifest Constants Using Equates 382 Processor Directives 384 Procedures 385 Segments 386 Segment Names 387 Segment Loading Order 388 Segment Operands 389 The ALIGN Type 389 The COMBINE Type 393 The CLASS Type 394 The Read-only Operand 395 The USE16, USE32, and FLAT Options 395 Typical Segment Definitions 396 Why You Would Want to Control the Loading Order 396 Segment Prefixes 397 Controlling Segments with the ASSUME Directive 397 Combining Segments: The GROUP Directive 400 Why Even Bother With Segments? 403 The END Directive 404 Variables 404 Label Types 405 How to Give a Symbol a Particular Type 405 Label Values 406 Type Conflicts 406 Address Expressions 407 Symbol Types and Addressing Modes 407 Arithmetic and Logical Operators 408 Coercion 410 Type Operators 412 Operator Precedence 416 Conditional Assembly 417 IF Directive 418 IFE directive 419 IFDEF and IFNDEF 419 IFB, IFNB 419 IFIDN, IFDIF, IFIDNI, and IFDIFI 420 Macros 420 Procedural Macros 420 Macros vs. 80x86 Procedures 424 The LOCAL Directive 426 The EXITM Directive 426 Macro Parameter Expansion and Macro Operators 427 A Sample Macro to Implement For Loops 429 Macro Functions 433 Predefined Macros, Macro Functions, and Symbols 434 Macros vs. Text Equates 438 Macros: Good and Bad News 439 Repeat Operations 440 The FOR and FORC Macro Operations 441 The WHILE Macro Operation 442 Macro Parameters 442 Controlling the Listing 444 The ECHO and %OUT Directives 444 The TITLE Directive 444 The SUBTTL Directive 444 The PAGE Directive 444 The .LIST, .NOLIST, and .XLIST Directives 445 Other Listing Directives 445 Managing Large Programs 445 The INCLUDE Directive 446 The PUBLIC, EXTERN, and EXTRN Directives 447 The EXTERNDEF Directive 448 Make Files 449 Sample Program 452 EX8.MAK 452 Matrix.A 452 EX8.ASM 453 GETI.ASM 462 GetArray.ASM 463 XProduct.ASM 465 Laboratory Exercises 467 Near vs. Far Procedures 467 Data Alignment Exercises 468 Equate Exercise 469 IFDEF Exercise 470 Make File Exercise 471 Programming Projects 473 Summary 473 Questions 476 9. Arithmetic and Logical Operations 479 Chapter Overview 479 Arithmetic Expressions 480 Simple Assignments 480 Simple Expressions 480 Complex Expressions 482 Commutative Operators 486 Logical (Boolean) Expressions 487 Multiprecision Operations 490 Multiprecision Addition Operations 490 Multiprecision Subtraction Operations 492 Extended Precision Comparisons 493 Extended Precision Multiplication 495 Extended Precision Division 497 Extended Precision NEG Operations 500 Extended Precision AND Operations 501 Extended Precision OR Operations 502 Extended Precision XOR Operations 502 Extended Precision NOT Operations 502 Extended Precision Shift Operations 502 Extended Precision Rotate Operations 504 Operating on Different Sized Operands 505 Machine and Arithmetic Idioms 506 Multiplying Without MUL and IMUL 507 Division Without DIV and IDIV 508 Using AND to Compute Remainders 508 Implementing Modulo-n Counters with AND 509 Testing an Extended Precision Value for 0FFFF..FFh 509 TEST Operations 509 Testing Signs with the XOR Instruction 510 Masking Operations 510 Masking Operations with the AND Instruction 510 Masking Operations with the OR Instruction 511 Packing and Unpacking Data Types 511 Tables 513 Function Computation via Table Look Up 513 Domain Conditioning 516 Generating Tables 517 Sample Programs 518 Converting Arithmetic Expressions to Assembly Language 518 Boolean Operations Example 520 64-bit Integer I/O 523 Packing and Unpacking Date Data Types 526 Laboratory Exercises 529 Debugging Programs with CodeView 529 Debugging Strategies 531 Locating Infinite Loops 531 Incorrect Computations 532 Illegal Instructions/Infinite Loops Part II 533 Debug Exercise I: Using CodeView to Find Bugs in a Calculation 533 Software Delay Loop Exercises 535 Programming Projects 9.12 Summary 536 Questions 538 10. Control Structures 541 Chapter Overview 541 Introduction to Decisions 541 IF..THEN..ELSE Sequences 542 CASE Statements 545 State Machines and Indirect Jumps 549 Spaghetti Code 551 Loops 551 While Loops 552 Repeat..Until Loops 552 LOOP..ENDLOOP Loops 553 FOR Loops 553 Register Usage and Loops 554 Performance Improvements 555 Moving the Termination Condition to the End of a Loop 555 Executing the Loop Backwards 557 Loop Invariant Computations 558 Unraveling Loops 559 Induction Variables 560 Other Performance Improvements 561 Nested Statements 562 Timing Delay Loops 564 Sample Program 567 Laboratory Exercises 572 The Physics of Sound 572 The Fundamentals of Music 573 The Physics of Music 574 The 8253/8254 Timer Chip 575 Programming the Timer Chip to Produce Musical Tones 575 Putting it All Together 576 Amazing Grace Exercise 577 Programming Projects 578 Summary 579 Questions 581 11. Procedures and Functions 585 Chapter Overview 585 Procedures 586 Near and Far Procedures 588 Forcing NEAR or FAR CALLs and Returns 588 Nested Procedures 589 Functions 592 Saving the State of the Machine 592 Parameters 594 Pass by Value 594 Pass by Reference 595 Pass by Value-Returned 595 Pass by Result 596 Pass by Name 596 Pass by Lazy-Evaluation 597 Passing Parameters in Registers 598 Passing Parameters in Global Variables 600 Passing Parameters on the Stack 601 Passing Parameters in the Code Stream 610 Passing Parameters via a Parameter Block 618 Function Results 620 Returning Function Results in a Register 621 Returning Function Results on the Stack 621 Returning Function Results in Memory Locations 622 Side Effects 622 Local Variable Storage 624 Recursion 626 Sample Program 630 Laboratory Exercises 638 Ex11_1.cpp 639 Ex11_1.asm 641 EX11_1a.asm 645 Programming Projects 652 Summary 653 Questions 655 12. Procedures: Advanced Topics 657 Chapter Overview 657 Lexical Nesting, Static Links, and Displays 657 Scope 658 Unit Activation, Address Binding, and Variable Lifetime 660 Static Links 660 Accessing Non-Local Variables Using Static Links 665 The Display 666 The 80286 ENTER and LEAVE Instructions 668 Passing Variables at Different Lex Levels as Parameters. 670 Passing Parameters by Value in a Block Structured Language 670 Passing Parameters by Reference, Result, and Value-Result in a Block Structured Language 671 Passing Parameters by Name and Lazy-Evaluation in a Block Structured Language 672 Passing Parameters as Parameters to Another Procedure 673 Passing Reference Parameters to Other Procedures 674 Passing Value-Result and Result Parameters as Parameters 675 Passing Name Parameters to Other Procedures 675 Passing Lazy Evaluation Parameters as Parameters 676 Parameter Passing Summary 676 Passing Procedures as Parameters 677 Iterators 681 Implementing Iterators Using In-Line Expansion 682 Implementing Iterators with Resume Frames 684 Sample Programs 687 An Example of an Iterator 687 Another Iterator Example 691 Laboratory Exercises 696 Iterator Exercise 696 The 80x86 Enter and Leave Instructions 702 Parameter Passing Exercises 708 Programming Projects 713 Summary 715 Questions 716 13. MS-DOS, PC-BIOS, and File I/O 717 Chapter Overview 718 The IBM PC BIOS 719 An Introduction to the BIOSÌ Services 719 INT 5- Print Screen 720 INT 10h - Video Services 720 INT 11h - Equipment Installed 722 INT 12h - Memory Available 722 INT 13h - Low Level Disk Services 722 INT 14h - Serial I/O 724 AH=0: Serial Port Initialization 724 AH=1: Transmit a Character to the Serial Port 725 AH=2: Receive a Character from the Serial Port 725 AH=3: Serial Port Status 725 INT 15h - Miscellaneous Services 726 INT 16h - Keyboard Services 726 AH=0: Read a Key From the Keyboard 727 AH=1: See if a Key is Available at the Keyboard 727 AH=2: Return Keyboard Shift Key Status 728 INT 17h - Printer Services 728 AH=0: Print a Character 729 AH=1: Initialize Printer 729 AH=2: Return Printer Status 729 INT 18h - Run BASIC 730 INT 19h - Reboot Computer 730 INT 1Ah - Real Time Clock 730 AH=0: Read the Real Time Clock 730 AH=1: Setting the Real Time Clock 731 An Introduction to MS-DOSë 731 MS-DOS Calling Sequence 732 MS-DOS Character Oriented Functions 732 MS-DOS Drive Commands 734 MS-DOS ÏObsoleteÓ Filing Calls 735 MS-DOS Date and Time Functions 736 MS-DOS Memory Management Functions 736 Allocate Memory 737 Deallocate Memory 737 Modify Memory Allocation 737 Advanced Memory Management Functions 738 MS-DOS Process Control Functions 739 Terminate Program Execution 739 Terminate, but Stay Resident 739 Execute a Program 740 MS-DOS ÏNewÓ Filing Calls 743 Open File 743 Create File 744 Close File 745 Read From a File 745 Write to a File 746 Seek (Move File Pointer) 746 Set Disk Transfer Address (DTA) 747 Find First File 747 Find Next File 748 Delete File 748 Rename File 748 Change/Get File Attributes 749 Get/Set File Date and Time 749 Other DOS Calls 750 File I/O Examples 752 Example #1: A Hex Dump Utility 752 Example #2: Upper Case Conversion 753 Blocked File I/O 755 The Program Segment Prefix (PSP) 757 Accessing Command Line Parameters 760 ARGC and ARGV 768 UCR Standard Library File I/O Routines 769 Fopen 769 Fcreate 770 Fclose 770 Fflush 770 Fgetc 770 Fread 771 Fputc 771 Fwrite 771 Redirecting I/O Through the StdLib File I/O Routines 771 A File I/O Example 773 Sample Program 776 Laboratory Exercises 781 Programming Projects 786 Summary 786 Questions 788 14. Floating Point Arithmetic 789 Chapter Overview 789 The Mathematics of Floating Point Arithmetic 789 IEEE Floating Point Formats 792 The UCR Standard Library Floating Point Routines 795 Load and Store Routines 796 Integer/Floating Point Conversion 797 Floating Point Arithmetic 798 Float/Text Conversion and Printff 798 The 80x87 Floating Point Coprocessors 799 FPU Registers 799 The FPU Data Registers 800 The FPU Control Register 800 The FPU Status Register 803 FPU Data Types 806 The FPU Instruction Set 807 FPU Data Movement Instructions 807 The FLD Instruction 807 The FST and FSTP Instructions 808 The FXCH Instruction 808 Conversions 809 The FILD Instruction 809 The FIST and FISTP Instructions 809 The FBLD and FBSTP Instructions 810 Arithmetic Instructions 810 The FADD and FADDP Instructions 810 The FSUB, FSUBP, FSUBR, and FSUBRP Instructions 811 The FMUL and FMULP Instructions 812 The FDIV, FDIVP, FDIVR, and FDIVRP Instructions 812 The FSQRT Instruction 813 The FSCALE Instruction 813 The FPREM and FPREM1 Instructions 813 The FRNDINT Instruction 814 The FXTRACT Instruction 814 The FABS Instruction 814 The FCHS Instruction 815 Comparison Instructions 815 The FCOM, FCOMP, and FCOMPP Instructions 815 The FUCOM, FUCOMP, and FUCOMPP Instructions 816 The FTST Instruction 816 The FXAM Instruction 816 Constant Instructions 816 Transcendental Instructions 817 The F2XM1 Instruction 817 The FSIN, FCOS, and FSINCOS Instructions 817 The FPTAN Instruction 817 The FPATAN Instruction 818 The FYL2X and FYL2XP1 Instructions 818 Miscellaneous instructions 818 The FINIT and FNINIT Instructions 818 The FWAIT Instruction 819 The FLDCW and FSTCW Instructions 819 The FCLEX and FNCLEX Instructions 819 The FLDENV, FSTENV, and FNSTENV Instructions 819 The FSAVE, FNSAVE, and FRSTOR Instructions 820 The FSTSW and FNSTSW Instructions 821 The FINCSTP and FDECSTP Instructions 821 The FNOP Instruction 821 The FFREE Instruction 821 Integer Operations 821 Sample Program: Additional Trigonometric Functions 822 Laboratory Exercises 828 FPU vs StdLib Accuracy 829 Programming Projects 14.8 Summary 832 Questions 835 15. Strings and Character Sets 837 Chapter Overview 837 The 80x86 String Instructions 837 How the String Instructions Operate 837 The REP/REPE/REPZ and REPNZ/REPNE Prefixes 838 The Direction Flag 839 The MOVS Instruction 840 The CMPS Instruction 844 The SCAS Instruction 846 The STOS Instruction 846 The LODS Instruction 847 Building Complex String Functions from LODS and STOS 848 Prefixes and the String Instructions 848 Character Strings 849 Types of Strings 849 String Assignment 850 String Comparison 852 Character String Functions 853 Substr 853 Index 856 Repeat 858 Insert 859 Delete 861 Concatenation 862 String Functions in the UCR Standard Library 863 StrBDel, StrBDelm 864 Strcat, Strcatl, Strcatm, Strcatml 865 Strchr 866 Strcmp, Strcmpl, Stricmp, Stricmpl 866 Strcpy, Strcpyl, Strdup, Strdupl 867 Strdel, Strdelm 868 Strins, Strinsl, Strinsm, Strinsml 869 Strlen 870 Strlwr, Strlwrm, Strupr, Struprm 870 Strrev, Strrevm 871 Strset, Strsetm 871 Strspan, Strspanl, Strcspan, Strcspanl 872 Strstr, Strstrl 873 Strtrim, Strtrimm 873 Other String Routines in the UCR Standard Library 874 The Character Set Routines in the UCR Standard Library 874 Using the String Instructions on Other Data Types 877 Multi-precision Integer Strings 877 Dealing with Whole Arrays and Records 878 Sample Programs 878 Find.asm 878 StrDemo.asm 880 Fcmp.asm 883 Laboratory Exercises 886 MOVS Performance Exercise #1 886 MOVS Performance Exercise #2 888 Memory Performance Exercise 890 The Performance of Length-Prefixed vs. Zero-Terminated Strings 892 Programming Projects 896 Summary 896 Questions 899 16. Pattern Matching 901 An Introduction to Formal Language (Automata) Theory 901 Machines vs. Languages 901 Regular Languages 902 Regular Expressions 903 Nondeterministic Finite State Automata (NFAs) 905 Converting Regular Expressions to NFAs 906 Converting an NFA to Assembly Language 908 Deterministic Finite State Automata (DFAs) 911 Converting a DFA to Assembly Language 913 Context Free Languages 918 Eliminating Left Recursion and Left Factoring CFGs 921 Converting REs to CFGs 923 Converting CFGs to Assembly Language 923 Some Final Comments on CFGs 930 Beyond Context Free Languages 930 The UCR Standard Library Pattern Matching Routines 931 The Standard Library Pattern Matching Functions 932 Spancset 932 Brkcset 933 Anycset 933 Notanycset 934 MatchStr 934 MatchiStr 934 MatchToStr 935 MatchChar 935 MatchToChar 936 MatchChars 936 MatchToPat 936 EOS 937 ARB 937 ARBNUM 938 Skip 938 Pos 939 RPos 939 GotoPos 939 RGotoPos 940 SL_Match2 940 Designing Your Own Pattern Matching Routines 940 Extracting Substrings from Matched Patterns 943 Semantic Rules and Actions 947 Constructing Patterns for the MATCH Routine 951 Some Sample Pattern Matching Applications 953 Converting Written Numbers to Integers 953 Processing Dates 959 Evaluating Arithmetic Expressions 966 A Tiny Assembler 971 The ÏMADVENTUREÓ Game 981 Laboratory Exercises 997 Checking for Stack Overflow (Infinite Loops) 997 Printing Diagnostic Messages from a Pattern 1002 Programming Projects 1006 Summary 1006 Questions 1009 17. Interrupts, Traps, and Exceptions 1011 80x86 Interrupt Structure and Interrupt Service Routines (ISRs) 1012 Traps 1015 Exceptions 1016 Divide Error Exception (INT 0) 1016 Single Step (Trace) Exception (INT 1) 1016 Breakpoint Exception (INT 3) 1017 Overflow Exception (INT 4/INTO) 1017 Bounds Exception (INT 5/BOUND) 1017 Invalid Opcode Exception (INT 6) 1020 Coprocessor Not Available (INT 7) 1020 Hardware Interrupts 1020 The 8259A Programmable Interrupt Controller (PIC) 1021 The Timer Interrupt (INT 8) 1023 The Keyboard Interrupt (INT 9) 1024 The Serial Port Interrupts (INT 0Bh and INT 0Ch) 1024 The Parallel Port Interrupts (INT 0Dh and INT 0Fh) 1024 The Diskette and Hard Drive Interrupts (INT 0Eh and INT 76h) 1025 The Real-Time Clock Interrupt (INT 70h) 1025 The FPU Interrupt (INT 75h) 1025 Nonmaskable Interrupts (INT 2) 1025 Other Interrupts 1025 Chaining Interrupt Service Routines 1026 Reentrancy Problems 1028 The Efficiency of an Interrupt Driven System 1030 Interrupt Driven I/O vs. Polling 1030 Interrupt Service Time 1031 Interrupt Latency 1032 Prioritized Interrupts 1036 Debugging ISRs 1036 Summary 1037 18. Resident Programs 1041 DOS Memory Usage and TSRs 1041 Active vs. Passive TSRs 1045 Reentrancy 1048 Reentrancy Problems with DOS 1048 Reentrancy Problems with BIOS 1049 Reentrancy Problems with Other Code 1050 The Multiplex Interrupt (INT 2Fh) 1050 Installing a TSR 1051 Removing a TSR 1053 Other DOS Related Issues 1055 A Keyboard Monitor TSR 1057 Semiresident Programs 1071 Summary 1080 19. Processes, Coroutines, and Concurrency 1081 DOS Processes 1081 Child Processes in DOS 1081 Load and Execute 1082 Load Program 1084 Loading Overlays 1085 Terminating a Process 1085 Obtaining the Child Process Return Code 1086 Exception Handling in DOS: The Break Handler 1086 Exception Handling in DOS: The Critical Error Handler 1087 Exception Handling in DOS: Traps 1091 Redirection of I/O for Child Processes 1091 Shared Memory 1094 Static Shared Memory 1094 Dynamic Shared Memory 1104 Coroutines 1119 Multitasking 1140 Lightweight and HeavyWeight Processes 1140 The UCR Standard Library Processes Package 1141 Problems with Multitasking 1142 A Sample Program with Threads 1143 Synchronization 1145 Atomic Operations, Test & Set, and Busy-Waiting 1148 Semaphores 1150 The UCR Standard Library Semaphore Support 1152 Using Semaphores to Protect Critical Regions 1152 Using Semaphores for Barrier Synchronization 1156 Deadlock 1162 Summary 1163 20. The PC Keyboard 1167 Keyboard Basics 1167 The Keyboard Hardware Interface 1173 The Keyboard DOS Interface 1181 The Keyboard BIOS Interface 1182 The Keyboard Interrupt Service Routine 1188 Patching into the INT 9 Interrupt Service Routine 1198 Simulating Keystrokes 1200 Stuffing Characters in the Type Ahead Buffer 1200 Using the 80x86 Trace Flag to Simulate IN AL, 60H Instructions 1201 Using the 8042 Microcontroller to Simulate Keystrokes 1206 Summary 1210 21. The PC Parallel Ports 1213 Basic Parallel Port Information 1213 The Parallel Port Hardware 1215 Controlling a Printer Through the Parallel Port 1216 Printing via DOS 1217 Printing via BIOS 1217 An INT 17h Interrupt Service Routine 1217 Inter-Computer Communications on the Parallel Port 1223 Summary 1236 22. The PC Serial Ports 1237 The 8250 Serial Communications Chip 1237 The Data Register (Transmit/Receive Register) 1238 The Interrupt Enable Register (IER) 1238 The Baud Rate Divisor 1239 The Interrupt Identification Register (IIR) 1240 The Line Control Register 1241 The Modem Control Register 1242 The Line Status Register (LSR) 1243 The Modem Status Register (MSR) 1244 The Auxiliary Input Register 1245 The UCR Standard Library Serial Communications Support Routines 1245 Programming the 8250 (Examples from the Standard Library) 1247 Summary 1258 23. The PC Video Display 1261 Memory Mapped Video 1261 The Video Attribute Byte 1262 Programming the Text Display 1263 Summary 1266 24. The PC Game Adapter 1269 Typical Game Devices 1269 The Game Adapter Hardware 1271 Using BIOSÌ Game I/O Functions 1273 Writing Your Own Game I/O Routines 1274 The Standard Game Device Interface (SGDI) 1276 Application ProgrammerÌs Interface (API) 1276 Read4Sw 1277 Read4Pots: 1277 ReadPot 1278 Read4: 1278 CalibratePot 1278 TestPotCalibration 1278 ReadRaw 1279 ReadSwitch 1279 Read16Sw 1279 Remove 1279 TestPresence 1279 An SGDI Driver for the Standard Game Adapter Card 1279 An SGDI Driver for the CH ProductsÌ Flight Stick Proë 1294 Patching Existing Games 1307 Summary 1320 25. Optimizing Your Programs 1323 Chapter Overview 25.1 When to Optimize, When Not to Optimize 1323 How Do You Find the Slow Code in Your Programs? 1325 Is Optimization Necessary? 1326 The Three Types of Optimization 1327 Improving the Implementation of an Algorithm 1329 Summary 1353 Appendix B: Annotated Bibliography 1355 Appendix C: Keyboard Scan Codes 1359 Appendix D: Instruction Set Reference 1369