第1章 大脑是最好的优化器 1
1．1 代码优化中人的因素 1
1．2 何谓高性能 1
1．3 编写高性能代码的原则 2
1．3．1 明确目的 2
1．3．2 制定总体规划 3
1．3．3 制定大量的小规划 3
1．3．4 明确布局 7
1．3．5 知道重要部分 8
1．3．6 考虑多种方法 9
1．3．7 知道应付意义 11
1．4 小结 14
第2章 汇编优化 15
2．1 汇编语言最优化的独特性 15
2．2 指令：个别与整体 15
2．3 汇编的特征 16
2．3．1 低效转化 16
2．3．2 独立性 17
2．3．3 学无止境 18
2．4 开动脑筋 18
第3章 综计时器 20
3．1 掌握和使用综计时 20
3．2 粗心的代价 20
3．3 综计时器 21
3．3．1 综计时器是一种手段不是目标 30
3．3．2 综计时器的开始 30
3．4 计时与PC机 31
3．5 停止综计时器 33
3．6 报告计时结果 33
3．7 关于综计时器的几点说明 34
3．8 综计时器使用举例 35
3．9 长周期综计时器 36
3．10 长周期综计时器的使用举例 54
3．11 在C中使用综计时器 58
3．12 仔细优化汇编程序 60
3．13 综计时器是一种好的工具 61
第4章 时钟周期耗费的本质 62
4．1 PC硬件如何影响代码性能 62
4．2 时钟周期耗费的因素 62
4．3 时钟周期耗费的特点 63
4．4 8位数据总线时钟周期耗费 64
4．4．1 8位数据总线的限制 65
4．4．2 如何克服8位总线时钟周期耗费 66
4．5 指令预取队列时钟周期耗费 68
4．5．1 不要相信技术手册上的执行时间 69
4．5．2 指令执行时间是不定的 70
4．5．3 估计全面执行时间 74
4．5．4 如何克服指令队列的时钟周期耗费 74
4．5．5 继续讨论8088 75
4．6 DRAM刷新 75
4．6．1 PC中DRAM刷新的方式 76
4．6．2 DRAM刷新的影响 77
4．6．3 如何克服DRAM刷新的时钟周期耗费 78
4．7 等待状态 79
4．8 显示适配器时钟周期耗费 80
4．8．1 显示适配器时钟周期耗费的影响 82
4．8．2 如何克服显示适配器时钟周期耗费 85
4．8．3 时钟周期耗费总结 86
4．8．4 结束语 86
第5章 使用可重用块进行优化 87
5．1 使用可重用块搜索文件 87
5．3 采取强制技术 88
5．2 避开字符串 88
5．4 使用memchr（） 89
5．5 明确重点 94
5．6 跟踪执行 95
第6章 透过表面价值 96
6．1 机器指令无所不能 96
6．2 通过内存寻址进行数学运算 98
6．3 使用LEA指令倍乘，无需使用2的幂次运算 100
第7章 局部优化 101
7．1 介于算法一级和时钟周期计算一级的优化 101
7．3 LOOP指令与JCXZ指令的教训 102
7．2 不需要LOOP 102
7．4 局部优化 103
7．5 展开循环 105
7．5．1 使用表进行循环移位和偏移 109
7．5．2 关于NOT指令 110
7．5．3 带/不带进位标志增加 110
第8章 使用汇编语言加速C程序 112
8．1 如果有助于加快速度，不妨换一种语言 112
8．4 多段处理问题 113
8．2 尽量不在汇编中使用函数调用 113
8．3 栈帧（Stack frame）速度太慢 113
8．5 使速度到达极致 115
第9章 读者使我成功 128
9．1 从另一个角度看LEA指令 128
9．2 Kennedy的工作 129
9．3 加速乘法操作 131
9．4 不断优化搜索代码 131
9．5 快速排序 138
9．6 全32位除法 139
9．7 重新讨论最佳位置（Sweet Spot） 142
9．8 核心时钟周期计算 143
9．9 硬件相关的远程跳转 144
9．10 设置32位寄存器，时间因素和空间因素的权衡 145
第10章 耐心编码，使速度更快 146
10．1 草率编码导致性能低下 146
10．2 笨拙的直接求解方法 147
10．3 递归 152
第11章 286和386的研究 157
11．1 新的寄存器、新的指令、新的速度、新的复杂度 157
11．2 我们熟悉的Intel处理器 157
11．3 286和386的保护模式 158
11．4 时钟周期耗费的本质——讨论之二 158
11．4．1 系统等待状态 159
11．4．2 数据对齐 161
11．5 代码对齐 163
11．5．2 对齐方式和栈 165
11．5．1 386上的对齐方式 165
11．5．3 DRAM刷新的时钟周期耗费——不可改变 166
11．5．4 显示适配器的时钟周期耗费 166
11．6 286的新指令和新特性 167
11．7 386的新指令和新特性 168
11．7．1 286和386的优化规则讨论之一 169
11．7．2 286和386的优化规则讨论之二 169
11．8 286的POPE指令 171
12．1 486不仅仅是个快速的386 176
第12章 486的研究之一 176
12．2 优化的规则 177
12．2．1 变址寻址的弊端 177
12．2．2 提前计算指针 178
12．3 给程序员的告诫 180
12．3．1 栈寻址以及地址流水线 181
12．3．2 使用字节寄存器的问题之一 182
12．3．3 使用字节寄存器的问题之二 183
12．3．4 计算486程序运行的时间 184
12．4 补充说明 185
第13章 486的研究之二 186
13．1 流水线及损耗 186
13．2 BSWAP比读者想象的更有用 188
13．3 存储器数据的压栈和弹栈 190
13．4 最佳的1位平移和循环移位 191
13．5 32位寻址模式 192
第14章 Boyer-Moore串搜索方法 194
14．1 一个最佳搜索算法的实现 194
14．2 串搜索回顾 194
14．3 Boyer-Moore算法 195
14．4 Boyer-Moore算法的优缺点 198
14．5 Boyer-Moore算法的进一步优化 206
第15章 链表 211
15．1 链表前言 211
15．2 链表 212
15．3 哑元和标记 214
15．4 循环链表 216
15．5 24个字节编程 221
16．2 快速统计单词数 223
第16章 代码的优化永无止境 223
16．1 结果比手段重要 223
16．3 挑战和冒险 232
16．3．1 选择最好的算法 232
16．3．2 不要想当然 233
16．4 巧妙优化的奇迹 233
16．5 优化的级别 238
16．6 二级优化：新视角 241
16．6．1 三级优化：突破 242
16．6．2 小结 245
第17章 游戏Life的优化 246
17．1 算法优化 246
17．2 Conway的游戏 246
17．3 运行时间分布 252
17．4 抽象的优缺点 253
17．5 C++优化的重要性 259
17．6 创造性思维 262
17．6．1 再次分析任务 262
17．6．2 相邻单元记录方法的实现 263
17．6．3 一生的挑战 270
第18章 奇妙的Life 271
18．1 优化的限制条件 271
18．2 打破限制条件 271
18．3 神奇的驱动表 272
18．4 使用变化表跟踪变化 287
18．5 外行对QLIFE的看法 289
第19章 Pentium 291
19．1 优化的历史 291
19．2 优化作为艺术的回归 291
19．3 Pentium综述 292
19．3．1 跨越cache块取指 292
32．2 扩展的256色模式 293
19．3．2 cache的组织方式 293
19．4 更快地寻址 294
19．5 分枝预测 295
19．6 Pentium的各种特点 296
19．6．1 比较486与Pentium的优化 296
19．6．2 超标量 297
20．2 流水线并行 298
第20章Pentium优化规则 298
20．1 在超标量体系结构中的优化 298
20．3 V流水线能执行的指令 300
20．4 执行的一致性 303
20．5 超标量的注意事项 307
第21章 充分利用V流水线 309
21．1 充分利用两条流水线 309
21．2 地址相关（AGI） 309
21．3 寄存器冲突 312
21．4 确定指令运行所在的流水线 313
21．5 在运行中优化 314
第22章 综级优化 321
22．1 简要回顾 321
22．2 综级优化 321
23．2 VGA 327
第23章 VGA的硬件结构和特性 327
23．1 标准PC图形的重点 327
23．3 介绍VGA编程 328
23．4 VGA内核 328
23．4．1 线性位面和真VGA模式 330
23．4．2 平滑绘制 343
23．4．3 颜色位面操作 345
23．4．4 页面翻转 346
23．5 VGA的不兼容性 348
23．6 一切还刚刚开始 348
23．7 关于宏汇编 348
24．1 一次从图形存储器中取出4个字节 349
24．2 VGA的编程；运用ALU和锁存器 349
第24章 使用VGA进行并行处理 349
24．3 ALU/锁存器演示程序注意事项 356
第25章 VGA中的数据控制部件 359
25．1 桶形移位器、位屏蔽和设置/复位部件 359
25．2 VGA的数据循环移位 359
25．3 位屏蔽部件 360
25．4 VGA的设置/复位电路 367
25．4．1 设置所有位面以形成一种颜色 370
25．4．2 各位面独立操作 373
25．5 设置/复位部件注意事项 375
25．6 双字节OUT指令注意事项 376
26．1 关于写模式3 377
26．2 陌生的写模式3 377
第26章 VGA的写模式3 377
26．3 保存寄存器位的注意事项 393
第27章 VGA的写模式2 394
27．1 写模式2，大位图块以及文本一图形共存 394
27．2 写模式2和设置/复位部件 394
27．2．1 写模式2处理举例 394
27．2．2 写模式2拷贝大位图块 396
27．2．3 写模式2绘制基于颜色模板的线条 402
27．3 写模式2和设置/复位部件的权衡 409
27．4 VGA模式13H简介 409
27．5 文本模式/图形模式切换 410
28．2 读模式0 416
28．1 读模式简介 416
第28章 读VGA显存 416
28．3 读模式1 422
28．4 读模式1特殊情况 426
第29章 屏幕保存和其他VGA内幕 431
29．1 VGA操作综述 431
29．2 保存和恢复 431
29．3 从64种颜色中选取16种颜色 439
29．4 越界颜色 446
29．5 一个好的清屏器 447
29．6 修改VGA寄存器 449
第30章 拆分屏幕 451
30．1 拆分屏幕简介 451
30．2 拆分屏幕的工作原理 451
30．2．1 拆分屏幕的实现 452
30．2．2 不要混淆两种拆分屏幕操作 461
30．3 设置相关寄存器 461
30．4 EGA拆分屏幕的问题 462
30．5 拆分屏幕和绘制 462
30．6 设置/读出寄存器注意事项 472
30．7 其他模式的拆分屏幕 474
30．8 拆分屏幕的安全性 474
第31章 VGA更高的256色分辨率 475
31．1 到底是320×200还是320×400？ 475
31．2 为什么是320×200？ 475
31．3 320×400的256色模式 476
31．3．1 320×400模式中显存结构 476
31．3．2 像素读、写 478
31．4 两个256色页面 486
31．5 其他的思考 492
32．1 使256色模式和标准VGA模式一样快 493
第32章 360×480 256色模式 493
32．3 360×480 256色模式 494
32．4 360×480 256色模式工作原理 504
32．4．1 每屏480个扫描行 504
32．4．2 每个扫描行360个像素 504
32．4．3 在360×480 256色模式中访问显存 505
33．2 VGA颜色产生原理 507
第33章 调色板RAM及DAC寄存器 507
33．1 VGA颜色产生的基础 507
33．2．1 调色板RAM 508
33．2．2 DAC 509
33．2．3 颜色选择寄存器的颜色页面调度 509
33．2．4 256色模式 510
33．2．5 设置调色板RAM 510
33．2．6 DAC设置 511
33．3 不能调用BIOS时的处理 511
33．4 举例说明DAC的设置 512
第34章 不通过写像素改变颜色 518
34．1 实时操作DAC颜色的特殊效果 518
34．2 颜色循环 518
34．3 核心问题 519
34．3．1 通过BIOS装载DAC 519
34．3．2 直接装载DAC 520
34．4 颜色循环的测试程序 521
34．5 有效的颜色循环方法 528
34．6 补充说明 529
34．6．1 DAC屏蔽 529
34．6．2 读DAC 529
34．6．3 结束语 530
第35章 Bresenham线段绘制算法 531
35．1 Bresenham线段绘制算法的实现与优化 531
35．2 关于线段绘制 531
35．3 Bresenham的线段绘制算法 532
35．4 使用C语言实现 535
35．4．1 分析EVGALine函数 541
35．4．2 绘制每一条线段 543
35．4．3 绘制每一个像素 543
35．5 C语言实现程序的讨论 544
35．6 汇编语言实现的Bresenham算法 545
第36章Bresenham步距长度片算法 554
36．1 采用步距长度片方法的快速Bresenham算法 554
36．2 步距长度片原理 555
36．3 步距长度片的实现 557
36．4 步距长度片的详细讨论 558
第37章 步距长度片绘制算法的优化 567
37．1 对步距长度片绘制算法的大力优化 567
37．2 快速步距长度片方法 567
37．2．1 步距长度片方法的速度 575
37．2．2 进一步的优化 576
38．1 高效快速地绘制多边形 577
38．2 填充的多边形 577
第38章 多边形原操作 577
38．3如何拼接多边形 579
38．4 填充不重叠的凸多边形 580
第39章 快速的凸多边形填充算法 580
38．5 其它 589
39．1 多边形的快速填充 590
39．2 快速凸多边形填充 591
39．2．1 快速绘制 592
39．2．2 快速边扫描 594
39．3 最后的方法：汇编语言 597
39．4 更快的边扫描方法 600
第40章 复杂多边形的简化 605
40．1 处理不规则的多边形区域 605
40．2 填充任意的多边形 605
40．3 复杂多边形填充的实现 614
40．3．1 关于活跃边的再讨论 618
40．3．2 关于性能的讨论 618
40．4 非凸多边形 620
第41章 多边形命名的重要性 622
41．1 把一个数据结构概念化时名称很重要 622
41．2 术语的使用 622
第42章 Wu的反走样算法 636
42．1 使用Wu的算法的反走样线快速绘制 636
42．2 Wu的反走样算法 636
42．3 绘制以及亮度和为1 638
42．4 Wu反走样算法的样本 641
43．1 有限颜色的简单和快速动画方法 655
第43章 位面动画 655
43．2 基本概念——位面 656
43．3 位面动画的实现 659
43．4 位面动画的局限 671
43．5 剪切和页面翻转 673
43．6 关于PC上的动画 673
44．2 计算机动画的几个问题 675
44．3 一个页面翻转动画演示 675
44．1 页面翻转的局限 675
第44章 使用拆分屏幕的页面翻转 675
44．3．1 写模式3 689
44．3．2 文本绘制 691
44．3．3 页面翻转 691
44．4 引入拆分屏幕 693
第45章 “脏矩形”动画 695
45．1 小狗Sam的故事 695
45．2 狗的启迪 695
45．3 VGA访问 696
45．4 “脏矩形”动画 697
45．5 “脏矩形”动画的实现 699
45．6 高分辨率的VGA页面翻转 705
45．7 页面翻转的另一改进 709
第46章 使用屏蔽图像的“脏矩形”动画 711
46．1 优化“脏矩形”动画 711
46．2 “脏矩形”动画探讨之二 711
46．3 屏蔽图像 723
46．4 内部的动画 723
46．5 绘制顺序和显示质量 724
47．2 模式X的特性 725
第47章 模式X：神奇的256色VGA模式 725
47．1 VGA松布的“动画优化”模式介绍 725
47．3 选择320×240 256色模式 726
47．4 从模式X的角度进行设计 733
47．5 硬件加速 738
第48章 模式X对锁存器的使用 743
48．1 动画的最好视频显示模式 743
48．2 模式X中的显存分配 749
48．3 在显存中拷贝像素块 751
48．4 小结 758
49．1 如何充分发挥VGA的性能 759
49．2 屏蔽拷贝 759
第49章 模式X的256色动画 759
49．2．1 快速屏蔽拷贝 762
49．2．2 注意事项 769
49．3 动画 769
49．4 模式X动画的实现 769
49．5 模式X印象 776
50．1 使用模式X的3D动画 778
第50章 三维动画 778
50．2 3D绘制的参考文献 779
50．3 3D绘制流水线 779
50．3．1 投影 781
50．3．2 平移 781
50．3．3 旋转 781
50．4 3D编程举例 783
50．5 小结 794
51．2 有一个可见面的多边形 795
第51章 背面删除方法 795
51．1 使用背面删除方法消去不可见面 795
51．3 递增变换 805
51．4 对象表示 808
第52章 快速3D动画：使用X-Sharp 810
52．1 一个通用的3D动画软件包 810
52．2 本章的演示程序 810
52．3 一个新的动画框架：X- Sharp 826
52．4 实时动画的三个关键之处 826
52．4．1 缺点 827
52．4．2 运行时间分配 828
第53章 最高速度及其它 829
53．1 提高3D动画速度的真理 829
53．2 最高速度第一部分：汇编语言 829
53．3 最高速度第二部分：查找表 837
53．3．1 不可见面 838
53．3．2 舍入 841
53．4 球的3D动画 841
54．2 对以前处理器的支持 842
第54章 3D浓淡处理 842
54．1 使3D动画对象具有真实表面 842
54．3 浓淡 861
54．3．1 环境浓淡 862
54．3．2 漫反射浓淡 862
54．4 浓淡的实现 865
第55章 256色模式中的颜色表示 868
55．1 用RGB模式表示X- Sharp中的颜色 868
55．2 颜色模型 868
55．3 从Bit Man那里得到收益 873
第56章 纹理映射 880
56．1 使用快速纹理映射 880
56．2 快速的脏纹理映射原理 881
56．2．1 使纹理映射更容易 881
56．2．2 DDA纹理映射注意事项 883
56．3 快速纹理映射方法的实现 884
57．2 视觉效果 892
57．1实现快速、光滑纹理映射的经验规则 892
第57章 多边形纹理映射的优化 892
57．3 定点算法的缺陷 893
57．4 纹理映射，与方向无关 894
57．5 把纹理映射到多边形 896
第58章 纹理映射的优化 905
58．1 使用最佳方法优化纹理映射 905
58．2 纹理映射的缺陷 906
58．2．1 固定思维的优化 906
58．2．2 完全不同的角度 908
58．3 最终的优化 910
58．4 关于纹理映射的几点说明 916
第59章 BSP树 918
59．1 BSP树的概念 918
59．2 BSP树 919
59．2．1 可见性判别 919
59．2．2 BSP树的局限 920
59．3 建立BSP树 921
59．4 BSP树的顺序遍历 925
59．4．1 完全了解 927
59．4．2 测量与学习 929
59．5 BSP树参考资料 931
第60章 编译BSP树 933
60．1 BSP树的实现 933
60．2 编译BSP树 934
60．2．1 参数线段 934
60．2．3 BSP编译器 936
60．2．2 参数线段裁剪 936
60．3 优化BSP树 943
60．4 有待研究的BSP优化 944
第61章 参照物 945
61．1 3D图形的数学基础 945
61．1．1 3D数学 945
61．1．2 基本定义 946
61．2 点积 946
61．3 叉积和多边形法向量 948
61．4 利用点积的符号 950
61．5 点积用于投影 951
第62章BSP绘制算法 954
62．1 优化被编译的BSP树 954
62．2 基于BSP的绘制 955
62．3 绘制流水线 965
62．3．1 观察者移动 965
62．3．2 变换到视空间 966
62．3．3 裁剪 966
62．3．4 投影到屏幕空间 967
62．3．5 遍历、背面删除及绘制 968
62．4 关于BSP绘制程序的几点说明 969
第63章 实时3D处理的浮点操作 970
63．1 紧急事件的处理 970
63．2 浮点操作的新概念 971
63．3 Pentium的FP优化 971
63．4 FXCH指令 973
63．5 点积优化 974
63．6 叉积优化 975
63．7 变换优化 976
63．9 舍入控制 978
63．8 投影优化 978
63．10 不再使用3D定点 979
第64章 Quake的可视表面判别 980
64．1 可见性判别 980
64．2 VSD：最难的三维问题 981
64．3 Quake级的结构 981
64．4 背面删除和可视表面判别 982
64．5 重复绘制 983
64．6 beam树 984
64．7．1 光线投射子划分 985
64．7 三维引擎 985
64．7．2 不需要顶点的表面 986
64．7．3 绘制缓存 986
64．7．4 基于段的绘制 986
64．7．5 孔洞 986
64．8 突破 986
64．9 简化并不断尝试新事物 987
64．11 参考书 988
64．10 学以致用 988
第65章 3D裁剪 989
65．1 信息交流 989
65．2 3D裁剪的基础 990
65．3 多边形裁剪 992
65．3．1 裁剪到视体内 995
65．3．2 程序65-3的技巧 1001
65．4 视空间裁剪的优点 1002
65．5 进一步学习 1003
第66章Quake中面的消隐 1004
66．1 不可见面的Z序消隐 1004
66．2 创造性的变化和不可见表面 1004
66．2．1 绘制运动对象 1004
66．2．2 性能影响 1005
66．2．3 改进与均衡性能 1005
66．3 跨度排序 1006
66．4 边排序关键值 1010
66．4．2 Quake和Z排序 1011
66．4．1 1/z方程的推导 1011
66．5 排序方法的取舍 1012
第67章 实现跨度排列 1013
67．1 实现独立的跨度排序 1013
67．2 Quake和跨度排序 1013
67．3 按1/z进行跨度排序的类型 1015
67．3．1 相交跨度排序 1015
67．3．2 邻接跨度排序 1015
67．3．3 独立跨度排序 1016
67．4 1/z跨度排序的实现 1017
第68章Quake的光照模型 1029
68．1 做感兴趣的事 1029
68．2 光照难题 1029
68．3Gouraud浓淡方法 1030
68．3．1 Gouraud浓淡方法的问题 1030
68．3．2 透视校正 1031
68．4 寻求其他光照方法 1032
68．4．1 分离光照和光栅化 1033
68．4．2 尺寸和速度 1034
68．5 表面cache 1035
68．5．1 均值映射(Mipmapping) 1035
68．5．2 关于表面cache的最后两点说明 1036
第69章 表面cache和 Quake的三角形模型 1037
69．1 保持理智 1037
69．2 与硬件相关的表面cache 1038
69．2．1 使用图形卡构造纹理 1038
69．3．1 快速绘制三角形模型 1039
69．3 绘制三角形模型 1039
69．2．2 作为Alpha纹理的光照图 1039
69．3．2 子像素的精度换取速度 1041
69．3．3 一种无效的方法 1041
69．3．4 一种有效的方法 1042
69．3．5 其他可能有效的方法 1046
第70章 Quake: 回顾和展望 1047
70．1 预处理基本空间 1048
70．2 可能可见集（PVS） 1049
70．4 绘制基本空间 1050
70．3 几乎发生的改变 1050
70．5．1 光照 1052
70．5．2 动态光照 1052
70．5 光栅化 1052
70．6 实体 1053
70．6．1 BSP模型 1053
70．6．2 多边形模型和Z-buffer 1054
70．6．3 再分割光栅化程序 1055
70．6．4 特殊效果 1055
70．7．1 Verite Quake 1056
70．6．5 粒子 1056
70．7 Quake推入市场后我们的计划 1056
70．7．2 GL Quake 1057
70．7．3 WinQuake 1058
70．7．4 QuakeWorld 1058
70．7．5 Quake 2 1060
70．8 展望 1061
著后语 1063