Introduction to 64 Bit Intel Assembly Language Programming for Linux

This book is an assembly language programming textbook introducing programmers to 64 bit Intel assembly language. The book is intended as a first assembly language book for programmers experienced in high level programming in a language like C or C++. The assembly programming is performed using the yasm assembler (much like the nasm assembler) under the Linux operating system. The book primarily teaches how to write assembly code compatible with C programs. The reader will learn to call C functions from assembly language and to call assembly functions from C in addition to writing complete programs in assembly language. The gcc compiler is used for C programming. The book starts early emphasizing using the gdb debugger to debug programs. Being able to single-step assembly programs is critical in learning assembly programming. Highlights of the book include doing input/output programming using the Linux system calls and the C library, implementing data structures in assembly language and high performance assembly language programming. A companion web site has a collection of PDF slides which instructors can use for in-class presentations and source code for sample programs. Early chapters of the book rely on using the debugger to observe program behavior. After a chapter on functions, the user is prepared to use printf and scanf from the C library to perform I/O. The chapter on data structures covers singly linked lists, doubly linked circular lists, hash tables and binary trees. Test programs are presented for all these data structures. There is a chapter on optimization techniques and 3 chapters on specific optimizations. One chapter covers how to efficiently count the 1 bits in an array with the most efficient version using the recently-introduced popcnt instruction. Another chapter covers using SSE instructions to create an efficient implementation of the Sobel filtering algorithm. The final high performance programming chapter discusses computing correlation between data in 2 arrays. There is an AVX implementation which achieves 20.5 GFLOPs on a single core of a Core i7 CPU. Introduction to 64 Bit Intel Assembly Language Programming for Linux 1 Preface 5 Acknowledgements 7 Contents 9 Chapter 1: Introduction 17 1.1 Why study assembly language? 18 1.2 What is a computer? 20 1.2.1 Bytes 20 1.2.2 Program execution 20 1.3 Machine language 21 1.4 Assembly language 22 1.5 Assembling and linking 24 Chapter 2: Numbers 27 2.1 Binary numbers 27 2.2 Hexadecimal numbers 29 2.3 Integers 32 2.3.1 Binary addition 34 2.3.2 Binary multiplication 35 2.4 Floating point numbers 36 2.4.1 Converting decimal numbers to floats 39 2.4.2 Converting floats to decimal 40 2.4.3 Floating point addition 40 2.4.4 Floating point multiplication 41 Chapter 3: Computer memory 43 3.1 Memory mapping 43 3.2 Process memory model in Linux 44 3.3 Memory example 46 3.4 Examining memory with gdb 48 3.4.1 Printing with gdb 48 3.4.2 Examining memory 50 Chapter 4: Memory mapping in 64 bit mode 53 4.1 The memory mapping register 53 4.2 Page Map Level 4 54 4.3 Page Directory Pointer Table 55 4.4 Page Directory Table 55 4.5 Page Table 55 4.6 Large pages 56 4.7 CPU Support for Fast Lookups 56 Chapter 5: Registers 59 5.1 Moving a constant into a register 61 5.2 Moving values from memory into registers 62 5.3 Moving values from a register into memory 65 5.4 Moving data from one register to another 65 Chapter 6: A little bit of math 67 6.1 Negation 67 6.2 Addition 68 6.3 Subtraction 70 6.4 Multiplication 71 6.5 Division 73 6.6 Conditional move instructions 73 6.7 Why move to a register? 74 Chapter 7: Bit operations 77 7.1 Not operation 77 7.2 And operation 78 7.3 Or operation 79 7.4 Exclusive or operation 80 7.5 Shift operations 81 7.6 Bit testing and setting 83 7.7 Extracting and filling a bit field 84 Chapter 8: Branching and looping 87 8.1 Unconditional jump 87 8.2 Conditional jump 89 8.2.1 Simple if statement 90 8.2.2 If/else statement 91 8.2.3 If/else-if/else statement 91 8.3 Looping with conditional jumps 92 8.3.1 While loops 92 8.3.2 Do-while loops 96 8.3.3 Counting loops 98 8.4 Loop instructions 98 8.5 Repeat string (array) instructions 99 8.5.1 String instructions 99 Chapter 9: Functions 105 9.1 The stack 105 9.2 Call instruction 106 9.3 Return instruction 107 9.4 Function parameters and return value 107 9.5 Stack frames 108 9.6 Recursion 110 Chapter 10: Arrays 115 10.1 Array address computation 115 10.2 General pattern for memory references 117 10.3 Allocating arrays 119 10.4 Processing arrays 120 10.4.1 Creating the array 120 10.4.2 Filling the array with random numbers 121 10.4.3 Printing the array 122 10.4.4 Finding the minimum value 123 10.4.5 Main program for the array minimum 123 10.5 Command line parameter array 125 Chapter 11: Floating point instructions 131 11.1 Floating point registers 131 11.2 Moving data to/from floating point registers 132 11.2.1 Moving scalars 132 11.2.2 Moving packed data 133 11.3 Addition 133 11.4 Subtraction 134 11.5 Multiplication and division 135 11.6 Conversion 135 11.6.1 Converting to a different length floating point 135 11.6.2 Converting floating point to/from integer 136 11.7 Floating point comparison 136 11.8 Mathematical functions 137 11.8.1 Minimum and maximum 138 11.8.2 Rounding 138 11.8.3 Square roots 139 11.9 Sample code 139 11.9.1 Distance in 3D 139 11.9.2 Dot product of 3D vectors 140 11.9.3 Polynomial evaluation 140 Chapter 12: System calls 145 12.1 32 bit system calls 146 12.2 64 bit system calls 146 12.3 C wrapper functions 147 12.3.1 open system call 148 12.3.2 read and write system calls 149 12.3.3 lseek system call 150 12.3.4 close system call 151 Chapter 13: Structs 153 13.1 Symbolic names for offsets 154 13.2 Allocating and using an array of structs 156 Chapter 14: Using the C stream I/O functions 159 14.1 Opening a file 160 14.2 fscanf and fprintf 161 14.3 fgetc and fputc 161 14.4 fgets and fputs 162 14.5 fread and fwrite 163 14.6 fseek and ftell 164 14.7 fclose 165 Chapter 15: Data structures 167 15.1 Linked lists 167 15.1.1 List node structure 168 15.1.2 Creating an empty list 168 15.1.3 Inserting a number into a list 169 15.1.4 Traversing the list 169 15.2 Doubly-linked lists 172 15.2.1 Doubly-linked list node structure 173 15.2.2 Creating a new list 173 15.2.3 Inserting at the front of the list 174 15.2.4 List traversal 175 15.3 Hash tables 176 15.3.1 A good hash function for integers 177 15.3.2 A good hash function for strings 177 15.3.3 Hash table node structure and array 178 15.3.4 Function to find a value in the hash table 178 15.3.5 Insertion code 179 15.3.6 Printing the hash table 180 15.3.7 Testing the hash table 181 15.4 Binary trees 182 15.4.1 Binary tree node and tree structures 183 15.4.2 Creating an empty tree 183 15.4.3 Finding a key in a tree 184 15.4.4 Inserting a key into the tree 185 15.4.5 Printing the keys in order 186 Chapter 16: High performance assembly programming 191 16.1 General optimization strategies 191 16.2 Use a better algorithm 192 16.3 Use C or C++ 193 16.4 Efficient use of cache 193 16.5 Common subexpression elimination 195 16.6 Strength reduction 195 16.7 Use registers efficiently 196 16.8 Use fewer branches 196 16.9 Convert loops to branch at the bottom 196 16.10 Unroll loops 197 16.11 Merge loops 199 16.12 Split loops 199 16.13 Interchange loops 199 16.14 Move loop invariant code outside loops 200 16.15 Remove recursion 200 16.16 Eliminate stack frames 201 16.17 Inline functions 201 16.18 Reduce dependencies to allow super-scalar execution 201 16.19 Use specialized instructions 202 Chapter 17: Counting bits in an array 205 17.1 C function 205 17.2 Counting 1 bits in assembly 206 17.3 Precomputing the number of bits in each byte 209 17.4 Using the popcnt instruction 210 Chapter 18: Sobel filter 213 18.1 Sobel in C 214 18.2 Sobel computed using SSE instructions 215 Chapter 19: Computing Correlation 223 19.1 C implementation 223 19.2 Implementation using SSE instructions 224 19.3 Implementation using AVX instructions 227 Appendix A: Using gdb 233 A.1 Preparing for gdb 233 A.2 Starting 235 A.3 Quitting 235 A.4 Setting break points 235 A.5 Running 235 A.6 Printing a trace of stack frames 236 A.7 Examining registers 238 A.8 Examining memory 239 Appendix B: Using scanf and printf 241 B.1 scanf 241 B.2 printf 243 Appendix C: Using macros in yasm 245 C.1 Single line macros 245 C.2 Multi-line macros 246 C.3 Preprocessor variables 248 Appendix D: Sources for more information 249 D.1 yasm user manual 249 D.2 nasm user manual 249 D.3 Dr. Paul Carter's free assembly book 249 D.4 64 bit Machine Level Programming 249 D.5 GDB Manual 250 D.6 DDD Manual 250 D.7 Intel Documentation 250 Index 251