How Software Works

Table of Contents

1. Cover Page
2. Title Page
3. Copyright Page
4. About the Author
5. About the Technical Reviewer
6. Brief Contents
7. Contents in Detail
8. Acknowledgments
9. Introduction
   1. Who This Book Is For
   2. Topics Covered
   3. Behind the Magic
10. Chapter 1: Encryption
    1. The Goal of Encryption
    2. Transposition: Same Data, Different Order
       1. Cipher Keys
       2. Attacking the Encryption
    3. Substitution: Replacing Data
       1. Varying the Substitution Pattern
       2. Key Expansion
    4. The Advanced Encryption Standard
       1. Binary Basics
          1. Decimal Versus Binary
          2. Bitwise Operations
          3. Converting Data to Binary Form
       2. AES Encryption: The Big Picture
       3. Key Expansion in AES
       4. AES Encryption Rounds
       5. Block Chaining
       6. Why AES Is Secure
       7. Possible AES Attacks
    5. The Limits of Private-Key Encryption
11. Chapter 2: Passwords
    1. Transforming a Password into a Number
       1. Properties of Good Hash Functions
          1. Full Use of All Bits
          2. No Reversibility
          3. Avalanche
    2. The MD5 Hash Function
       1. Encoding the Password
       2. Bitwise Operations
          1. Binary Addition
          2. Bitwise NOT
          3. Bitwise OR
          4. Bitwise AND
       3. MD5 Hashing Rounds
       4. Meeting the Criteria of a Good Hash Function
    3. Digital Signatures
       1. The Problem of Identity
       2. Collision Attacks
    4. Passwords in Authentication Systems
       1. The Dangers of Password Tables
       2. Hashing Passwords
       3. Dictionary Attacks
       4. Hash Tables
       5. Hash Chaining
       6. Iterative Hashing
       7. Salting Passwords
       8. Are Password Tables Safe?
    5. Password Storage Services
    6. A Final Thought
12. Chapter 3: Web Security
    1. How Public-Key Cryptography Solves the Shared Key Problem
    2. Math Tools for Public-Key Cryptography
       1. Invertible Functions
       2. One-Way Functions
       3. Trapdoor Functions
          1. Prime Numbers
          2. Coprime Numbers
          3. Prime Factors
    3. The RSA Encryption Method
       1. Creating the Keys
          1. Step 1
          2. Step 2
          3. Step 3
          4. Step 4
          5. Step 5
       2. Encrypting Data with RSA
          1. Step 1
          2. Step 2
          3. Step 3
          4. Step 4
       3. RSA Effectiveness
       4. RSA Use in the Real World
          1. Bidirectional Transmission
          2. Key Size
          3. Long Plaintexts and Performance
          4. Combining Systems
       5. RSA for Authentication
          1. Authentication Using RSA
          2. Identity Authorities
    4. Security on the Web: HTTPS
       1. Handshaking
          1. Step 1
          2. Step 2
          3. Step 3
          4. Step 4
          5. Step 5
       2. Transmitting Data Under HTTPS
          1. Data Encryption
          2. Block Chaining
          3. Message Authentication Code
    5. The Shared Key Problem Solved?
13. Chapter 4: Movie CGI
    1. Software for Traditional Animation
       1. How Digital Images Work
       2. How Colors Are Defined
       3. How Software Makes Cel Animations
          1. Transforming Drawings into Models
          2. Automatic Tweening
          3. Positioning and Scaling
          4. “Ink and Paint” for Digital Images
          5. Blending into Any Background
       4. From Cel Animation Software to Rendered 2D Graphics
    2. Software for 3D CGI
       1. How 3D Scenes Are Described
       2. The Virtual Camera
       3. Direct Lighting
          1. The Distance Effect
          2. The Diffuse Reflection Effect
          3. The Specular Reflection Effect
       4. Global Illumination
       5. How Light Is Traced
          1. Why Light Is Traced Backward
          2. How Ray Tracing Models Real-World Effects
       6. Full-Scene Anti-Aliasing
    3. Combining the Real and the Fake
    4. The Ideal of Movie-Quality Rendering
14. Chapter 5: Game Graphics
    1. Hardware for Real-Time Graphics
    2. Why Games Don’t Ray Trace
    3. All Lines and No Curves
    4. Projection Without Ray Tracing
    5. Rendering Triangles
       1. The Painter’s Algorithm
       2. Depth Buffering
    6. Real-Time Lighting
    7. Shadows
    8. Ambient Light and Ambient Occlusion
    9. Texture Mapping
       1. Nearest-Neighbor Sampling
       2. Bilinear Filtering
       3. Mipmaps
       4. Trilinear Filtering
    10. Reflections
    11. Faking Curves
        1. Distant Impostors
        2. Bump Mapping
        3. Tessellation
    12. Anti-Aliasing in Real Time
        1. Supersampling
        2. Multisampling
        3. Post-Process Anti-Aliasing
    13. The Rendering Budget
    14. What’s Next for Game Graphics
15. Chapter 6: Data Compression
    1. Run-Length Encoding
    2. Dictionary Compression
       1. The Basic Method
       2. Huffman Encoding
    3. Reorganizing Data for Better Compression
       1. Predictive Encoding
       2. Quantization
    4. JPEG Images
       1. A Different Way to Store Colors
       2. The Discrete Cosine Transform
       3. The DCT for Two Dimensions
       4. Compressing the Results
       5. JPEG Picture Quality
    5. Compressing High-Definition Video
       1. Temporal Redundancy
       2. MPEG-2 Video Compression
          1. Groups of Frames
          2. Temporal Compression
       3. Video Quality with Temporal Compression
    6. The Present and Future of Video Compression
16. Chapter 7: Search
    1. Defining the Search Problem
    2. Putting Data in Order
       1. Selection Sort
       2. Quicksort
    3. Binary Search
    4. Indexing
    5. Hashing
    6. Web Search
       1. Ranking Results
       2. Using the Index Effectively
    7. What’s Next for Web Search
17. Chapter 8: Concurrency
    1. Why Concurrency Is Needed
       1. Performance
       2. Multiuser Environments
       3. Multitasking
    2. How Concurrency Can Fail
    3. Making Concurrency Safe
       1. Read-Only Data
       2. Transaction-Based Processing
       3. Semaphores
          1. How Semaphores Prevent Race Conditions
          2. How Semaphores Are Made
    4. The Problem of Indefinite Waits
       1. Orderly Queues
       2. Starvation from Circular Waits
    5. Performance Issues of Semaphores
    6. What’s Next for Concurrency
18. Chapter 9: Map Routes
    1. What a Map Looks Like to Software
       1. Best-First Search
       2. Reusing Prior Search Results
    2. Finding All the Best Routes at Once
       1. Floyd’s Algorithm
       2. Storing Route Directions
    3. The Future of Routing
19. Index