Write Great Code - Volume 1, Understanding the Machine 2nd Edition (Randall Hyde) (z-library.sk, 1lib.sk, z-lib.sk)

📄 File Format: PDF

💾 File Size: 5.6 MB

📖 Read Online ⬇️ Download

Registered users can read the full content for free

Register as a Gaohf Library member to read the complete e-book online for free and enjoy a better reading experience.

📄 Page 1

R A N D A L L H Y D E W R I T E G R E A T C O D E / V O L U M E 1 2 N D E D I T I O N U N D E R S T A N D I N G T H E M A C H I N E

📄 Page 2

(This page has no text content)

📄 Page 3

PRAISE FOR THE FIRST EDITION OF WRITE GREAT CODE, VOLUME 1 “Today’s programmers can hardly keep up with the race against inhumane deadlines and new technologies; therefore, they rarely have a chance to learn the basics of computer architectures and the inner workings of their program- ming languages. This book fills in the gaps. I strongly recommend it.” —InformIT.com “[Write Great Code] isn’t your typical ‘teach yourself to program’ book. . . It’s relevant to all languages, and all levels of programming experience. . . Run, don’t walk, to buy and read this book.” —Bay area Large InsTaLLaTIon sysTem admInIsTraTors (BayLIsa) 5/5 stars: “[Write Great Code] fills in the blanks nicely and really could be part of a computer science degree required reading set. . . . Once this book is read, you will have a greater understanding and appreciation for code that is written efficiently—and you may just know enough to do that yourself. At least you will have a great start at the art of crafting efficient software.” —maccompanIon “Great fun to read.” —VsJ magazIne “Write Great Code, Volume 1: Understanding the Machine should be on the required reading list for anyone who wants to develop terrific code in any language without having to learn assembly language.” —WeBserVerTaLk

📄 Page 4

(This page has no text content)

📄 Page 5

by Randall Hyde San Francisco W R I T E G R E AT C O D E V O L U M E 1 2 N D E D I T I O N U n d e r s t a n d i n g t h e M a c h i n e

📄 Page 6

WRITE GREAT CODE, Volume 1: Understanding the Machine, 2nd Edition. Copyright © 2020 by Randall Hyde. All rights reserved. No part of this work may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording, or by any information storage or retrieval system, without the prior written permission of the copyright owner and the publisher. ISBN-10: 1-71850-036-X ISBN-13: 978-1-71850-036-5 Publisher: William Pollock Executive Editor: Barbara Yien Production Editor: Rachel Monaghan Developmental Editor: Athabasca Witschi Project Editor: Dapinder Dosanjh Cover and Interior Design: Octopod Studios Technical Reviewer: Anthony Tribelli Copyeditor: Rachel Monaghan Compositor: Danielle Foster Proofreader: James Fraleigh Illustrator: David Van Ness For information on distribution, translations, or bulk sales, please contact No Starch Press, Inc. directly: No Starch Press, Inc. 245 8th Street, San Francisco, CA 94103 phone: 1.415.863.9900; info@nostarch.com www.nostarch.com The Library of Congress issued the following Cataloging-in-Publication Data for the first edition of Volume 1: Hyde, Randall. Write great code : understanding the machine / Randall Hyde. p. cm. ISBN 1-59327-003-8 1. Computer programming. 2. Computer architecture. I. Title. QA76.6.H94 2004 005.1--dc22 2003017502 No Starch Press and the No Starch Press logo are registered trademarks of No Starch Press, Inc. Other product and company names mentioned herein may be the trademarks of their respective owners. Rather than use a trademark symbol with every occurrence of a trademarked name, we are using the names only in an editorial fashion and to the benefit of the trademark owner, with no intention of infringement of the trademark. The information in this book is distributed on an “As Is” basis, without warranty. While every precaution has been taken in the preparation of this work, neither the author nor No Starch Press, Inc. shall have any liability to any person or entity with respect to any loss or damage caused or alleged to be caused directly or indirectly by the information contained in it.

📄 Page 7

About the Author Randall Hyde is the author of The Art of Assembly Language and Write Great Code, Volumes 1, 2, and 3 (all from No Starch Press), as well as Using 6502 Assembly Language and P-Source (Datamost). He is also the coauthor of Microsoft Macro Assembler 6.0 Bible (The Waite Group). Over the past 40 years, Hyde has worked as an embedded software/hardware engineer developing instrumentation for nuclear reactors, traffic control systems, and other consumer elec- tronics devices. He has also taught computer science at California State Polytechnic University, Pomona, and at the University of California, Riverside. His website is www.randallhyde.com/. About the Technical Reviewer Tony Tribelli has more than 35 years of experience in software development, including work on embedded device kernels and molecular modeling. He developed video games for 10 years at Blizzard Entertainment. He is currently a software develop- ment consultant and privately develops applications utilizing computer vision.

📄 Page 8

(This page has no text content)

📄 Page 9

B R I E F C O N T E N T S Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvii Chapter 1: What You Need to Know to Write Great Code . . . . . . . . . . . . . . . . . . . . . . 1 Chapter 2: Numeric Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 Chapter 3: Binary Arithmetic and Bit Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 Chapter 4: Floating-Point Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 Chapter 5: Character Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 Chapter 6: Memory Organization and Access . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 Chapter 7: Composite Data Types and Memory Objects . . . . . . . . . . . . . . . . . . . . . . 159 Chapter 8: Boolean Logic and Digital Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217 Chapter 9: CPU Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251 Chapter 10: Instruction Set Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283 Chapter 11: Memory Architecture and Organization . . . . . . . . . . . . . . . . . . . . . . . . 319 Chapter 12: Input and Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349 Chapter 13: Computer Peripheral Buses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367 Chapter 14: Mass Storage Devices and Filesystems . . . . . . . . . . . . . . . . . . . . . . . . . 381 Chapter 15: Miscellaneous Input and Output Devices . . . . . . . . . . . . . . . . . . . . . . . . 413 Afterword: Thinking Low-Level, Writing High-Level . . . . . . . . . . . . . . . . . . . . . . . . . . 425 Appendix A: ASCII Character Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 427 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443

📄 Page 10

(This page has no text content)

📄 Page 11

C O N T E N T S I N D E T A I L ACKNOWLEDGMENTS XVII 1 WHAT YOU NEED TO KNOW TO WRITE GREAT CODE 1 1.1 The Write Great Code Series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 What This Book Covers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Assumptions This Book Makes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 Characteristics of Great Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.5 The Environment for This Book . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.6 Additional Tips . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.7 For More Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2 NUMERIC REPRESENTATION 9 2.1 What Is a Number? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Numbering Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2.1 The Decimal Positional Numbering System . . . . . . . . . . . . . . . . . . . . 11 2.2.2 Radix (Base) Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2.3 The Binary Numbering System. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2.4 The Hexadecimal Numbering System . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2.5 The Octal Numbering System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.3 Numeric/String Conversions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.4 Internal Numeric Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.4.1 Bits. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.4.2 Bit Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.5 Signed and Unsigned Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.6 Useful Properties of Binary Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.7 Sign Extension, Zero Extension, and Contraction . . . . . . . . . . . . . . . . . . . . . . . . 26 2.8 Saturation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.9 Binary-Coded Decimal Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.10 Fixed-Point Representation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.11 Scaled Numeric Formats. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.12 Rational Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.13 For More Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3 BINARY ARITHMETIC AND BIT OPERATIONS 37 3.1 Arithmetic Operations on Binary and Hexadecimal Numbers . . . . . . . . . . . . . . . 37 3.1.1 Adding Binary Values. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.1.2 Subtracting Binary Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.1.3 Multiplying Binary Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.1.4 Dividing Binary Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

📄 Page 12

x 3 .2 Logical Operations on Bits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3 .3 Logical Operations on Binary Numbers and Bit Strings . . . . . . . . . . . . . . . . . . . . 44 3 .4 Useful Bit Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3 .4 .1 Testing Bits in a Bit String Using AND . . . . . . . . . . . . . . . . . . . . . . . . 45 3 .4 .2 Testing a Set of Bits for Zero/Not Zero Using AND . . . . . . . . . . . . . . 45 3 .4 .3 Comparing a Set of Bits Within a Binary String . . . . . . . . . . . . . . . . . 46 3 .4 .4 Creating Modulo-n Counters Using AND . . . . . . . . . . . . . . . . . . . . . . 47 3 .5 Shifts and Rotates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3 .6 Bit Fields and Packed Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3 .7 Packing and Unpacking Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3 .8 For More Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4 FLOATING-POINT REPRESENTATION 61 4 .1 Introduction to Floating-Point Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 4 .2 IEEE Floating-Point Formats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 4 .2 .1 Single-Precision Floating-Point Format . . . . . . . . . . . . . . . . . . . . . . . . 67 4 .2 .2 Double-Precision Floating-Point Format . . . . . . . . . . . . . . . . . . . . . . . 69 4 .2 .3 Extended-Precision Floating-Point Format . . . . . . . . . . . . . . . . . . . . . . 69 4 .2 .4 Quad-Precision Floating-Point Format . . . . . . . . . . . . . . . . . . . . . . . . 70 4 .3 Normalization and Denormalized Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 4 .4 Rounding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 4 .5 Special Floating-Point Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 4 .6 Floating-Point Exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 4 .7 Floating-Point Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 4 .7 .1 Floating-Point Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 4 .7 .2 Floating-Point Addition and Subtraction . . . . . . . . . . . . . . . . . . . . . . 75 4 .7 .3 Floating-Point Multiplication and Division . . . . . . . . . . . . . . . . . . . . . 86 4 .8 For More Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 5 CHARACTER REPRESENTATION 95 5 .1 Character Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 5 .1 .1 The ASCII Character Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 5 .1 .2 The EBCDIC Character Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 5 .1 .3 Double-Byte Character Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 5 .1 .4 The Unicode Character Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 5 .1 .5 Unicode Code Points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 5 .1 .6 Unicode Code Planes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 5 .1 .7 Surrogate Code Points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 5 .1 .8 Glyphs, Characters, and Grapheme Clusters . . . . . . . . . . . . . . . . . . 103 5 .1 .9 Unicode Normals and Canonical Equivalence . . . . . . . . . . . . . . . . . 105 5 .1 .10 Unicode Encodings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 5 .1 .11 Unicode Combining Characters . . . . . . . . . . . . . . . . . . . . . . . . . . 108 5 .2 Character Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 5 .2 .1 Character String Formats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 5 .2 .2 Types of Strings: Static, Pseudo-Dynamic, and Dynamic . . . . . . . . . . 116 5 .2 .3 Reference Counting for Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 5 .2 .4 Delphi Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 5 .2 .5 Custom String Formats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

📄 Page 13

xi 5 .3 Character Set Data Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 5 .3 .1 Powerset Representation of Character Sets . . . . . . . . . . . . . . . . . . . 119 5 .3 .2 List Representation of Character Sets . . . . . . . . . . . . . . . . . . . . . . . 120 5 .4 Designing Your Own Character Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 5 .4 .1 Designing an Efficient Character Set . . . . . . . . . . . . . . . . . . . . . . . 122 5 .4 .2 Grouping the Character Codes for Numeric Digits . . . . . . . . . . . . . . 123 5 .4 .3 Grouping Alphabetic Characters . . . . . . . . . . . . . . . . . . . . . . . . . . 123 5 .4 .4 Comparing Alphabetic Characters . . . . . . . . . . . . . . . . . . . . . . . . . 125 5 .4 .5 Grouping Other Characters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 5 .5 For More Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 6 MEMORY ORGANIZATION AND ACCESS 131 6 .1 The Basic System Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 6 .1 .1 The System Bus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 6 .2 Physical Organization of Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 6 .2 .1 8-Bit Data Buses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 6 .2 .2 16-Bit Data Buses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 6 .2 .3 32-Bit Data Buses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 6 .2 .4 64-Bit Data Buses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 6 .2 .5 Small Accesses on Non-80x86 Processors . . . . . . . . . . . . . . . . . . . 141 6 .3 Big-Endian vs . Little-Endian Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 6 .4 The System Clock . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 6 .4 .1 Memory Access and the System Clock . . . . . . . . . . . . . . . . . . . . . . 148 6 .4 .2 Wait States . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 6 .4 .3 Cache Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 6 .5 CPU Memory Access . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 6 .5 .1 The Direct Memory Addressing Mode . . . . . . . . . . . . . . . . . . . . . . 155 6 .5 .2 The Indirect Addressing Mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 6 .5 .3 The Indexed Addressing Mode . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 6 .5 .4 The Scaled-Index Addressing Modes . . . . . . . . . . . . . . . . . . . . . . . 157 6 .6 For More Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 7 COMPOSITE DATA TYPES AND MEMORY OBJECTS 159 7 .1 Pointer Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 7 .1 .1 Pointer Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 7 .1 .2 Pointers and Dynamic Memory Allocation . . . . . . . . . . . . . . . . . . . . 161 7 .1 .3 Pointer Operations and Pointer Arithmetic . . . . . . . . . . . . . . . . . . . . 162 7 .2 Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 7 .2 .1 Array Declarations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 7 .2 .2 Array Representation in Memory . . . . . . . . . . . . . . . . . . . . . . . . . . 170 7 .2 .3 Accessing Elements of an Array . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 7 .2 .4 Multidimensional Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 7 .3 Records/Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 7 .3 .1 Records in Pascal/Delphi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 7 .3 .2 Records in C/C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 7 .3 .3 Records in HLA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 7 .3 .4 Records (Tuples) in Swift . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 7 .3 .5 Memory Storage of Records . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184

📄 Page 14

xii 7 .4 Discriminant Unions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 7 .4 .1 Unions in C/C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 7 .4 .2 Unions in Pascal/Delphi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 7 .4 .3 Unions in Swift . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 7 .4 .4 Unions in HLA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 7 .4 .5 Memory Storage of Unions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 7 .4 .6 Other Uses of Unions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 7 .5 Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192 7 .5 .1 Inheritance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194 7 .5 .2 Class Constructors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198 7 .5 .3 Polymorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 7 .5 .4 Abstract Methods and Abstract Base Classes . . . . . . . . . . . . . . . . . . 202 7 .6 Classes in C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 7 .6 .1 Abstract Member Functions and Classes in C++ . . . . . . . . . . . . . . . 206 7 .6 .2 Multiple Inheritance in C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206 7 .7 Classes in Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208 7 .8 Classes in Swift . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 7 .9 Protocols and Interfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210 7 .10 Generics and Templates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213 7 .11 For More Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215 8 BOOLEAN LOGIC AND DIGITAL DESIGN 217 8 .1 Boolean Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 8 .1 .1 The Boolean Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 8 .1 .2 Boolean Postulates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 8 .1 .3 Boolean Operator Precedence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220 8 .2 Boolean Functions and Truth Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220 8 .3 Function Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 8 .4 Algebraic Manipulation of Boolean Expressions . . . . . . . . . . . . . . . . . . . . . . . 223 8 .5 Canonical Forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 8 .5 .1 Sum-of-Minterms Canonical Form and Truth Tables . . . . . . . . . . . . . . 225 8 .5 .2 Algebraically Derived Sum-of-Minterms Canonical Form . . . . . . . . . 227 8 .5 .3 Product-of-Maxterms Canonical Form . . . . . . . . . . . . . . . . . . . . . . . 228 8 .6 Simplification of Boolean Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229 8 .7 What Does This Have to Do with Computers, Anyway? . . . . . . . . . . . . . . . . . . 237 8 .7 .1 Correspondence Between Electronic Circuits and Boolean Functions . 238 8 .7 .2 Combinatorial Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239 8 .7 .3 Sequential and Clocked Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245 8 .8 For More Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249 9 CPU ARCHITECTURE 251 9 .1 Basic CPU Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252 9 .2 Decoding and Executing Instructions: Random Logic vs . Microcode . . . . . . . . . . 254 9 .3 Executing Instructions, Step by Step . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255 9 .3 .1 The mov Instruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256 9 .3 .2 The add Instruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257

📄 Page 15

xiii 9 .3 .3 The jnz Instruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258 9 .3 .4 The loop Instruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259 9 .4 RISC vs . CISC: Improving Performance by Executing More, Faster, Instructions . . 259 9 .5 Parallelism: The Key to Faster Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260 9 .5 .1 Functional Units . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263 9 .5 .2 The Prefetch Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265 9 .5 .3 Conditions That Hinder the Performance of the Prefetch Queue . . . . . 267 9 .5 .4 Pipelining: Overlapping the Execution of Multiple Instructions . . . . . . 267 9 .5 .5 Instruction Caches: Providing Multiple Paths to Memory . . . . . . . . . . 272 9 .5 .6 Pipeline Hazards . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273 9 .5 .7 Superscalar Operation: Executing Instructions in Parallel . . . . . . . . . . 275 9 .5 .8 Out-of-Order Execution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277 9 .5 .9 Register Renaming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277 9 .5 .10 VLIW Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278 9 .5 .11 Parallel Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279 9 .5 .12 Multiprocessing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280 9 .6 For More Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281 10 INSTRUCTION SET ARCHITECTURE 283 10 .1 The Importance of Instruction Set Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284 10 .2 Basic Instruction Design Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285 10 .2 .1 Choosing Opcode Length . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287 10 .2 .2 Planning for the Future . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289 10 .2 .3 Choosing Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289 10 .2 .4 Assigning Opcodes to Instructions . . . . . . . . . . . . . . . . . . . . . . . . 290 10 .3 The Y86 Hypothetical Processor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291 10 .3 .1 Y86 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291 10 .3 .2 Y86 Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291 10 .3 .3 Operand Types and Addressing Modes on the Y86 . . . . . . . . . . . . 293 10 .3 .4 Encoding Y86 Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293 10 .3 .5 Examples of Encoding Y86 Instructions . . . . . . . . . . . . . . . . . . . . . 296 10 .3 .6 Extending the Y86 Instruction Set . . . . . . . . . . . . . . . . . . . . . . . . . 300 10 .4 Encoding 80x86 Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301 10 .4 .1 Encoding Instruction Operands . . . . . . . . . . . . . . . . . . . . . . . . . . 303 10 .4 .2 Encoding the add Instruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310 10 .4 .3 Encoding Immediate (Constant) Operands on the x86 . . . . . . . . . . 314 10 .4 .4 Encoding 8-, 16-, and 32-Bit Operands . . . . . . . . . . . . . . . . . . . . 315 10 .4 .5 Encoding 64-Bit Operands . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316 10 .4 .6 Alternate Encodings for Instructions . . . . . . . . . . . . . . . . . . . . . . . 316 10 .5 Implications of Instruction Set Design to the Programmer . . . . . . . . . . . . . . . . . 317 10 .6 For More Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317 11 MEMORY ARCHITECTURE AND ORGANIZATION 319 11 .1 The Memory Hierarchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319 11 .2 How the Memory Hierarchy Operates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322 11 .3 Relative Performance of Memory Subsystems . . . . . . . . . . . . . . . . . . . . . . . . . 324

📄 Page 16

xiv 11 .4 Cache Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326 11 .4 .1 Direct-Mapped Cache . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326 11 .4 .2 Fully Associative Cache . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327 11 .4 .3 n-Way Set Associative Cache . . . . . . . . . . . . . . . . . . . . . . . . . . . 328 11 .4 .4 Cache-Line Replacement Policies . . . . . . . . . . . . . . . . . . . . . . . . . 329 11 .4 .5 Cache Write Policies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330 11 .4 .6 Cache Use and Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331 11 .5 NUMA and Peripheral Devices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332 11 .6 Virtual Memory, Memory Protection, and Paging . . . . . . . . . . . . . . . . . . . . . . 332 11 .7 Writing Software That Is Cognizant of the Memory Hierarchy . . . . . . . . . . . . . 336 11 .8 Runtime Memory Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338 11 .8 .1 Static and Dynamic Objects, Binding, and Lifetime . . . . . . . . . . . . 339 11 .8 .2 The Code, Read-Only, and Constant Sections . . . . . . . . . . . . . . . . 340 11 .8 .3 The Static Variables Section . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341 11 .8 .4 The Storage Variables Section . . . . . . . . . . . . . . . . . . . . . . . . . . . 341 11 .8 .5 The Stack Section . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342 11 .8 .6 The Heap Section and Dynamic Memory Allocation . . . . . . . . . . . . 342 11 .9 For More Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348 12 INPUT AND OUTPUT 349 12 .1 Connecting a CPU to the Outside World . . . . . . . . . . . . . . . . . . . . . . . . . . . 350 12 .2 Other Ways to Connect Ports to the System . . . . . . . . . . . . . . . . . . . . . . . . . . 353 12 .3 I/O Mechanisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354 12 .3 .1 Memory-Mapped I/O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354 12 .3 .2 I/O-Mapped Input/Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355 12 .3 .3 Direct Memory Access . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355 12 .4 I/O Speed Hierarchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356 12 .5 System Buses and Data Transfer Rates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357 12 .5 .1 Performance of the PCI Bus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359 12 .5 .2 Performance of the ISA Bus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359 12 .5 .3 The AGP Bus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 360 12 .6 Buffering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 360 12 .7 Handshaking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361 12 .8 Timeouts on an I/O Port . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362 12 .9 Interrupts and Polled I/O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363 12 .10 Protected-Mode Operation and Device Drivers . . . . . . . . . . . . . . . . . . . . . . 364 12 .10 .1 The Device Driver Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365 12 .10 .2 Communication with Device Drivers . . . . . . . . . . . . . . . . . . . . . . 365 12 .11 For More Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366 13 COMPUTER PERIPHERAL BUSES 367 13 .1 The Small Computer System Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367 13 .1 .1 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 368 13 .1 .2 Improvements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369 13 .1 .3 SCSI Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370 13 .1 .4 SCSI Advantages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372

📄 Page 17

xv 13 .2 The IDE/ATA Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372 13 .2 .1 The SATA Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374 13 .2 .2 Fibre Channel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374 13 .3 The Universal Serial Bus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374 13 .3 .1 USB Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374 13 .3 .2 USB Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376 13 .3 .3 Types of USB Transmissions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377 13 .3 .4 USB-C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379 13 .3 .5 USB Device Drivers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380 13 .4 For More Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380 14 MASS STORAGE DEVICES AND FILESYSTEMS 381 14 .1 Disk Drives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381 14 .1 .1 Floppy Disk Drives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382 14 .1 .2 Hard Drives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382 14 .1 .3 RAID Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 388 14 .1 .4 Optical Drives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389 14 .1 .5 CD, DVD, and Blu-ray Drives . . . . . . . . . . . . . . . . . . . . . . . . . . . 390 14 .2 Tape Drives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 392 14 .3 Flash Storage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393 14 .4 RAM Disks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395 14 .5 Solid-State Drives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395 14 .6 Hybrid Drives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 396 14 .7 Filesystems on Mass Storage Devices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 396 14 .7 .1 Sequential Filesystems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397 14 .7 .2 Efficient File Allocation Strategies . . . . . . . . . . . . . . . . . . . . . . . . . 399 14 .8 Writing Software That Manipulates Data on a Mass Storage Device . . . . . . . . 407 14 .8 .1 File Access Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407 14 .8 .2 Synchronous and Asynchronous I/O . . . . . . . . . . . . . . . . . . . . . . 409 14 .8 .3 The Implications of I/O Type . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409 14 .8 .4 Memory-Mapped Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410 14 .9 For More Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411 15 MISCELLANEOUS INPUT AND OUTPUT DEVICES 413 15 .1 Exploring Specific PC Peripheral Devices . . . . . . . . . . . . . . . . . . . . . . . . . . . 413 15 .1 .1 The Keyboard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414 15 .1 .2 The Standard PC Parallel Port . . . . . . . . . . . . . . . . . . . . . . . . . . . 415 15 .1 .3 Serial Ports . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417 15 .2 Mice, Trackpads, and Other Pointing Devices . . . . . . . . . . . . . . . . . . . . . . . . 417 15 .3 Joysticks and Game Controllers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419 15 .4 Sound Cards . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419 15 .4 .1 How Audio Interface Peripherals Produce Sound . . . . . . . . . . . . . . 420 15 .4 .2 The Audio and MIDI File Formats . . . . . . . . . . . . . . . . . . . . . . . . . 422 15 .4 .3 Programming Audio Devices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423 15 .5 For More Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424

📄 Page 18

xvi AFTERWORD: THINKING LOW-LEVEL, WRITING HIGH-LEVEL 425 A ASCII CHARACTER SET 427 GLOSSARY 431 INDEX 443

📄 Page 19

A C K N O W L E D G M E N T S Many people have read and reread every word, symbol, and punctuation mark in this book in order to produce a better result. Kudos to the follow- ing people for their careful work on the second edition: development editor Athabasca Witschi, copyeditor/production editor Rachel Monaghan, and proofreader James Fraleigh. I would like to take the opportunity to graciously thank Anthony Tribelli, a longtime friend, who went well beyond the call of duty when doing a technical review of this book. He pulled every line of code out of this book (including snippets) and compiled and ran it to make sure it worked properly. His suggestions and opinions throughout the technical review process have dramatically improved the quality of this work. Of course, I would also like to thank all the countless readers over the years who’ve emailed suggestions and corrections, many of which have found their way into this second edition. Thanks to all of you, Randall Hyde

📄 Page 20

(This page has no text content)