Part I Fundamentals
1 GNU/Linux Operating System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1 Basic GNU/Linux Usage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.1 System Calls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1.2 GNU/Linux introspection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.1.3 GNU coreutils . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2 Bash shell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.1 Bash shell scripting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3 External commands and programs in GNU/Linux . . . . . . . . . . . . . . . . 12
1.3.1 GNU regular expression syntax . . . . . . . . . . . . . . . . . . . . . . . . 13
1.4 Next steps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.5 OpenSSH: OpenBSD Secure Shell . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.6 Programming Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.6.1 C and C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.6.2 GNU FORTRAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.6.3 Ada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.6.4 Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.6.5 Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.6.6 Tcl/Tk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.6.7 Perl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.6.8 Common Lisp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
1.6.9 Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.6.10 Erlang . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.6.11 Smalltalk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.6.12 Scala . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
1.6.13 Google’s GO Programming Language . . . . . . . . . . . . . . . . . . . 31
1.6.14 X10 Language . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
1.6.15 Lua . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
1.7 Miscellaneous Topics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
1.7.1 VNC : Virtual Network Computing . . . . . . . . . . . . . . . . . . . . . 34
1.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2 Text processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.1 OpenOffice.org Suite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.2 TeX and LaTeX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.2.1 Lout Typesetting System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.2.2 SGML Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.2.3 Texinfo : GNU Documentation System . . . . . . . . . . . . . . . . . . 39
2.2.4 LyX Frontend . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.2.5 Texmaker LaTeX Editor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.2.6 PostScript and PDF Support . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.3 Scribus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.3.1 Citation management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.4 Document classification software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.4.1 GNU locate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.5 Wiki . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
Part II Software Engineering and Libraries
3 Software Engineering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.1 GCC : GNU Compiler Collection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.1.1 GCC Command-line Options . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.1.2 GCC Preprocessor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.1.3 GCC Support of OpenMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.1.4 GCC Advice Mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.1.5 GCC Attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.1.6 GCC : Inline Assembly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.1.7 GCC Intrinsics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.1.8 Compiling Java using GCC . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.1.9 Compiling Ada using GCC . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.1.10 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.2 Source Code Configuration Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.2.1 Introduction to Version Control Systems . . . . . . . . . . . . . . . . . 59
3.2.2 CVS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.2.3 SVN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.2.4 GIT. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.2.5 TkCVS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.2.6 Tinderbox . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.3 GNU Build System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.3.1 Autoconf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.3.2 Automake . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.3.3 Libtool . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.4 Automatic Build Dependency Management . . . . . . . . . . . . . . . . . . . . . 69
3.4.1 GNU make : automatic build dependency . . . . . . . . . . . . . . . . 69
3.4.2 SCONS : A software construction tool . . . . . . . . . . . . . . . . . . 71
3.4.3 CMAKE and QMake . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
3.5 Bugzilla : Defect Tracking System . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.6 Editing Source Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
3.6.1 Emacs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
3.6.2 Eclipse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
3.6.3 KDevelop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
3.7 Static Checks on Source Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
3.7.1 ctags . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
3.8 GNU gcov: Test Coverage Program . . . . . . . . . . . . . . . . . . . . . . . . . . 82
3.8.1 Compiling programs for gcov . . . . . . . . . . . . . . . . . . . . . . . . . 82
3.8.2 Running gcov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
3.9 Debug Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.9.1 GDB. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.9.2 Insight . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
3.10 Doxygen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
3.10.1 Using Doxygen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
3.11 Source Navigation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
3.12 Profilers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
3.12.1 GNU profiler : gprof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
3.12.2 Valgrind . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
3.13 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
4 Standard Libraries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
4.1 GNU C Library . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
4.2 C++ Library . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
4.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
5 Apache Portable Runtime (apr) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
5.1 APR Memory Pool . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
5.2 APR Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
5.3 APR Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
5.4 APR Thread Pool . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
5.5 File information, IO, and Memory mapped files . . . . . . . . . . . . . . . . . 119
5.6 Hash tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
5.7 Using Memcache with APR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
5.8 Shared memory with APR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
5.9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
6 Boost C++ Libraries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
6.1 Boost smart pointer and memory pool . . . . . . . . . . . . . . . . . . . . . . . . . 128
6.2 Boost asio framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
6.2.1 Boost IOStreams framework . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
6.3 Boost data structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
6.4 Boost Graph Library . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
6.5 Boost Spirit Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
6.6 Boost multi-threading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
6.7 Boost Python integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
6.8 Boost Generic Image Processing Library (GIL) . . . . . . . . . . . . . . . . . 141
6.9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
7 Performance Libraries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
7.1 Google perftools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
7.1.1 perftools : tcmalloc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
7.1.2 perftools : heap checker . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
7.1.3 perftools : heap profiler . . . . . . . . . . . . . . . . . . . . . . . . . . 148
7.1.4 perftools : cpu profiler . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
7.2 Boehm GC : garbage collection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
7.3 Using Boehm GC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
7.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
8 Compression Engines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
8.1 ZLIB Compression Library . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
8.1.1 Compression ratio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
8.1.2 gzip file access functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
8.1.3 Integration of zlib and gzip in Python . . . . . . . . . . . . . . . . . . . 160
8.2 LIBBZ2 and BZIP2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
8.2.1 Integration of bzip2 in Python . . . . . . . . . . . . . . . . . . . . . . . . . . 163
8.3 LZMA and XZ Utils . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
8.3.1 XZ Utils . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
8.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
9 Application Development Libraries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
9.1 RPC (remote procedure call) library . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
9.1.1 XDR : External Data Representation Library . . . . . . . . . . . . . 169
9.2 Checksum computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
9.2.1 MD5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
9.2.2 SHA1 checksum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
9.3 OpenSSL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
9.4 XML Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
9.4.1 Expat : XML processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
9.4.2 libXML : XML processing library . . . . . . . . . . . . . . . . . . . . . . 180
9.5 Berkeley DB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
9.5.1 DB open function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
9.5.2 Other Berkeley DB functions . . . . . . . . . . . . . . . . . . . . . . . . . . 183
9.6 Memcached Library . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
9.7 SWIG interface generator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
9.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
10 Hierarchical Data Format 5 : HDF5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
10.1 HDF5 files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
10.1.1 HDF5 API Naming Conventions . . . . . . . . . . . . . . . . . . . . . . . 193
10.2 Example of HDF5 API . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
10.2.1 Writing and Reading compound datatype in HDF5 . . . . . . . . 199
10.2.2 HDF5 Attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
10.2.3 References to objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
10.2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
11 Graphics and Image Processing Libraries . . . . . . . . . . . . . . . . . . . . . . . . . 201
11.1 Cairo: A Vector Drawing Library . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
11.2 Graphics File Formats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
11.2.1 libPNG: library for Portable Network Graphics . . . . . . . . . . . 205
11.2.2 Scalable Vector Graphics (SVG) . . . . . . . . . . . . . . . . . . . . . . . 208
11.2.3 GraphicsMagick and ImageMagick . . . . . . . . . . . . . . . . . . . . . 209
11.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
Part III Parallel and System Programming
12 Parallel Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
12.1 POSIX Thread Library (pthreads) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
12.1.1 Understanding pthread programming model . . . . . . . . . . . . . . 214
12.1.2 Pthreads Keys: using thread specific data . . . . . . . . . . . . . . . . 216
12.1.3 Pthreads Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
12.2 OpenMP: Open specification for Multi-processing . . . . . . . . . . . . . . . 218
12.3 MPI: Message Passing Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
12.3.1 Using Boost.MPI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
12.4 Other libraries and tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
12.4.1 Thread Building Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
12.4.2 CUDA : C Unified Device Architecture . . . . . . . . . . . . . . . . . . 232
12.4.3 SIMT in CUDA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
12.4.4 Compute Kernels in CUDA. . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
12.4.5 Compiling CUDA code with NVCC . . . . . . . . . . . . . . . . . . . . 235
12.4.6 OpenCL (Open Compute Language) . . . . . . . . . . . . . . . . . . . . 239
12.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
13 Compiler Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
13.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
13.2 Anatomy of a Compiler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
13.3 Lexical Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
13.3.1 GNU flex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
13.3.2 GNU m4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
13.3.3 GNU readline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249
13.3.4 getopt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249
13.4 YACC: Yet Another Compiler Compiler . . . . . . . . . . . . . . . . . . . . . . . 250
13.4.1 Boost SPIRIT Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
13.5 Code Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256
13.5.1 GNU Binutils . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256
13.5.2 GNU Binutils libelf and elfutils . . . . . . . . . . . . . . . . . . . . . . . . 264
13.5.3 GNU Binutils ld . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266
13.5.4 BFD: Binary File Descriptor Library . . . . . . . . . . . . . . . . . . . . 268
13.5.5 GNU lightning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269
13.5.6 ANTLR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
13.6 LLVM: Low Level Virtual Machine . . . . . . . . . . . . . . . . . . . . . . . . . . . 273
13.6.1 LLVM Core and LLVM IR . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273
13.6.2 LLVM dragonegg . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
13.6.3 LLVM System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280
13.6.4 Using Clang . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283
13.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284
Part IV Engineering and Mathematical Software
14 Scientific Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287
14.1 Computer Vision with OpenCV. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288
14.2 CImg: C Image Processing Toolkit . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
14.3 Binary Decision Diagram (bdd): CUDD Library . . . . . . . . . . . . . . . . . 291
14.4 FWTools: Open Source GIS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295
14.4.1 PROJ4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296
14.4.2 GDAL : Geospatial Data Abstraction Library and OGR . . . . 297
14.5 GNU Image Manipulation Program
14.6 Computational Fluid Dynamics using OpenFOAM. . . . . . . . . . . . . . . 300
14.7 Molecular Dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303
14.7.1 NAMD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304
14.7.2
14.7.3 Molecular Visualization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304
14.7.4 Foldng@Home . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
14.8 Audacity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306
14.8.1
14.9
14.9.1
14.9.2 Quantum GIS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308
15
15.1 Algorithmic Design and HDL Capture . . . . . . . . . . . . . . . . . . . . . . . . . 318
15.2 HDL Capture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318
15.3 BLIF Format in a nutshell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320
15.4
. . . . . . . . . . . . . . . . . . . . . . . . . . . 298
GROMACS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304
Sound Exchange : sox . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306
14.10 QCAD : 2d CAD Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309
VLSI CAD Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
14.11 BRL-CAD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311
GRASS GIS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307
14.12 Blender . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314
Geographical Information Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307
Schematic capture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323
14.13 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
15.4.1 Xcircuit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323
15.4.2 GNU gschem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324
15.5 Verilog Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325
15.5.1 Icarus Verilog Simulator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327
15.5.2 Pragmatic GPL cver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329
15.5.3 GTKWave: Waveform Viewer . . . . . . . . . . . . . . . . . . . . . . . . . 329
15.6 VHDL Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329
15.7 Alliance CAD System. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331
15.7.1 Alliance CAD VHDL processing . . . . . . . . . . . . . . . . . . . . . . . 331
15.7.2 Alliance CAD tool asimut . . . . . . . . . . . . . . . . . . . . . . . . . . . 331
15.7.3 VHDL Logic Synthesis using Alliance CAD tool Boom . . . . 332
15.7.4 Alliance CAD tool xsch schematic viewer . . . . . . . . . . . . . . 335
15.7.5 Gate level processing in Alliance CAD . . . . . . . . . . . . . . . . . . 335
15.7.6 Physical design with Alliance CAD . . . . . . . . . . . . . . . . . . . . . 339
15.7.7 Alliance CAD tool for standard-cell routing: nero . . . . . . . . 341
15.7.8 QUCS : Universal Circuit Simulator . . . . . . . . . . . . . . . . . . . . 343
15.8 Magic VLSI Editor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344
15.9 NGSpice SPICE Engine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345
15.9.1
15.9.2 Performing TRANSIENT analysis . . . . . . . . . . . . . . . . . . . . . . 347
15.9.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347
Elementary devices in SPICE . . . . . . . . . . . . . . . . . . . . . . . . . . 346
16 Math libraries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349
16.1 BLAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350
16.2 ATLAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351
16.3 LAPACK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351
16.4 NTL
16.5 GSL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352
16.6 GMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353
16.7
16.8 FFTW . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353
16.9
17 Mathematics Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357
17.1 Maxima . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358
17.2 GNU Octave . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358
17.3 R : Data analysis and Graphics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361
17.4
17.5 Pari . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370
17.6 Nauty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370
17.7 Axiom. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371
17.8 Reduce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352
GLPK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354
MPFR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353
16.10 COIN-OR: Comp. Infrastructure for OR . . . . . . . . . . . . . . . . . . . . . . 355
PSPP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365
16.10.1 Open Solver Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356
16.11 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356
17.9 Singular Computer Algebra System . . . . . . . . . . . . . . . . . . . . . . . . . . . 375
17.11
17.12
17.13
17.14
17.15
18 Artificial Intelligence and Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . 391
18.1
18.2
18.3 ACL2: automatic theorem proving . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394
18.4 . . . . . . . . . . . . . . . . . . . . 397
18.5 Representing floor-plans by k tuples . . . . . . . . . . . . . . . . . . . . . . . . . 398
18.6
18.7
18.8 LIBSVM : Support Vector Machines . . . . . . . . . . . . . . . . . . . . . . . . . . 405
18.8.1
18.9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408
polymake: software to analyze Polytopes . . . . . . . . . . . . . . . . . . . . . . . 379
Artificial Neural Networks : FANN. . . . . . . . . . . . . . . . . . . . . . . . . . . . 402
Other Math Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381
SVM Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406
17.10
GAUL : Genetic Algorithms Utility Library
17.11.1 Macaulay 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381
17.11.2 CoCoA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383
CGAL (Computer Geometry Algorithms and Library) . . . . . . . . . . . . 385
TeXMacs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 387
18.5.1 Sequence-pair Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 398
Introduction to AI Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391
ASA : Adaptive Simulated Annealing Library . . . . . . . . . . . . . . . . . . . 400
Sage
CLIPS: C Language Integrated Production System. . . . . . . . . . . . . . . 392
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 388
Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390
Part V Scientific Visualization
19 Information Visualization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411
19.1 Graphical User Interfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412
19.1.1 X Window System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412
19.1.2 GIMP Toolkit: GTK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413
19.1.3 Qt: Application development framework . . . . . . . . . . . . . . . . . 414
19.1.4 Qt’s application programming API . . . . . . . . . . . . . . . . . . . . . . 418
19.1.5 Other GUI Toolkits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 418
19.2 OpenGL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 427
19.2.1 GLUT : OpenGL Utility Toolkit . . . . . . . . . . . . . . . . . . . . . . . . 429
19.2.2 GLUI : GUI for OpenGL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 430
19.2.3 Using OpenGL from Python . . . . . . . . . . . . . . . . . . . . . . . . . . . 433
19.3 OGRE : OO Graphics Rendering Engine . . . . . . . . . . . . . . . . . . . . . . . 434
19.4 Graphviz: dot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435
19.4.1 DOT Language . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 436
19.5 gnuplot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 436
19.6 Grace/Xmgr . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 437
19.7 Xfig . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 438
19.8 Inkscape . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 439
19.9 PovRay : Ray Tracing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 440
19.10 gd (graphics drawing) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 442
20
20.1 Web Servers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455
20.1.1
20.1.2 YAWS: Yet Another Web Server . . . . . . . . . . . . . . . . . . . . . . . 456
20.1.3 LAMP Stack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456
20.2 Hadoop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457
20.3 Content Management with Joomla . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457
20.4 Virtualization and Cloud Computing. . . . . . . . . . . . . . . . . . . . . . . . . . . 458
20.4.1 Cloud computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459
20.4.2 Network and Cluster Monitoring . . . . . . . . . . . . . . . . . . . . . . . 460
20.4.3 Ganglia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460
20.5
20.5.1 Creating database using PostgreSQL . . . . . . . . . . . . . . . . . . . . 461
20.6 MySQL. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 464
20.7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 467
20.8
21 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473
A Websites of Open-Source Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . 475
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 481
19.11 asymptote . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443
PostgreSQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460
20.4.4
19.12 FreeType : Font Rendering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445
HTTP Server : Apache . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456
Web and Database Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455
SQLite
19.14 Geomview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 446
Nagios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460
19.15 HippoDraw. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 448
20.9
19.16 GGobi : multi-dimensional visualization . . . . . . . . . . . . . . . . . . . . . . . 448
Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471
19.17 ParaView and VTK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 449
19.13 Anti-grain geometry : AGG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 446
19.18 OpenDX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 452
CouchDB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 469
19.19 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454
· · · · · · (收起)