CS 105 Tour of the Black Holes of Computing Machine Level Programming IV Structured Data Topics X86 4 ppt Arrays Structs Unions Basic Data Types Integral Stored operated on in general registers Signed vs unsigned depends on instructions used Intel byte word double word GAS b w l Bytes 1 2 4 C unsigned char unsigned short unsigned int Floating Point Stored operated on in floating point registers Intel Single Double Extended 2 GAS s l t Bytes 4 8 10 12 C float double long double 105 Array Allocation Basic Principle T A L Array of data type T and length L Contiguously allocated region of L sizeof T bytes char string 12 x 12 x int val 5 x double a 4 x x 4 x 8 x 8 x 16 x 12 x 16 x 24 x 20 x 32 char p 3 x 3 x 4 x 8 105 Array Access Basic Principle T A L Array of data type T and length L Identifier A can be used as a pointer to array element 0 Reference Type Value val 4 int 3 val int 5 x val 1 val 2 int int x 4 x 8 val 5 val 1 int int 5 val i int x 4i acts like int int val 5 1 x 4 5 x 4 2 x 8 1 3 x 12 x 16 x 20 105 Array Example typedef int zip dig 5 zip dig cmu 1 5 2 1 3 zip dig mit 0 2 1 3 9 zip dig hmc 9 1 7 1 1 zip dig cmu 1 16 zip dig mit 20 0 36 zip dig hmc Notes 5 24 2 40 9 56 2 28 1 44 1 60 1 32 3 48 7 64 3 9 52 1 68 36 56 1 72 Declaration zip dig cmu equivalent to int cmu 5 Example arrays were allocated in successive 20 byte blocks 76 Not guaranteed to happen in general 5 105 Array Accessing Example Computation Register edx contains starting address of array Register eax contains array index Desired digit at 4 eax edx Use memory reference edx eax 4 int get digit zip dig z int dig return z dig Memory Reference Code edx z eax dig movl edx eax 4 eax z dig 6 105 Referencing Examples zip dig cmu 1 16 zip dig mit 5 20 0 36 zip dig hmc 2 24 2 56 28 1 40 9 1 44 1 32 3 48 7 60 64 3 36 9 52 1 68 56 1 72 76 Code Does Not Do Any Bounds Checking Reference Address Value mit 3 36 4 3 48 3 mit 5 36 4 5 56 9 mit 1 36 4 1 32 3 cmu 15 16 4 15 76 7 Guaranteed Out of range behavior implementation dependent No guaranteed relative allocation of different arrays Yes No No No 105 Array Loop Example Original Source Transformed Version As generated by GCC Eliminate loop variable i Convert array code to pointer code Express in do while form No need to test at entrance 8 int zd2int zip dig z int i int zi 0 for i 0 i 5 i zi 10 zi z i return zi int zd2int zip dig z int zi 0 int zend z 4 do zi 10 zi z z while z zend return zi 105 Array Loop Implementation Registers ecx z eax zi ebx zend Computations 10 zi z implemented as 2 zi 4 zi z increments by 4 9 z ecx z xorl eax eax leal 16 ecx ebx L59 leal eax eax 4 edx movl ecx eax addl 4 ecx leal eax edx 2 eax cmpl ebx ecx jle L59 int zd2int zip dig z int zi 0 int zend z 4 do zi 10 zi z z while z zend return zi zi 0 zend z 4 5 zi z z zi z 2 5 zi z zend if goto loop 105 Nested Array Example define PCOUNT 4 zip dig pgh PCOUNT 1 5 2 0 6 1 5 2 1 3 1 5 2 1 7 1 5 2 2 1 zip dig pgh 4 1 5 2 0 6 1 5 2 1 3 1 5 2 1 7 1 5 2 2 1 76 96 116 136 156 Declaration zip dig pgh 4 equivalent to int pgh 4 5 Variable pgh denotes array of 4 elements Allocated contiguously Each element is an array of 5 int s Allocated contiguously Row Major ordering of all elements guaranteed 10 105 Nested Array Allocation Declaration T A R C A 0 0 Array of data type T R rows C columns Type T element requires K bytes Array Size A 0 C 1 A R 1 0 A R 1 C 1 R C K bytes Arrangement Row Major Ordering int A R C A A A A 0 0 1 1 0 C 1 0 C 1 11 4 R C Bytes A A R 1 R 1 0 C 1 105 Nested Array Row Access Row Vectors A i is array of C elements Each element of type T Starting address A i C K int A R C A 0 A 0 0 A 12 A i A 0 C 1 A i 0 A i C 4 A R 1 A A i R 1 C 1 0 A R 1 C 1 A R 1 C 4 105 Nested Array Row Access Code int get pgh zip int index return pgh index Row Vector pgh index is array of 5 int s Starting address pgh 20 index Code Computes and returns address Compute as pgh 4 index 4 index eax index leal eax eax 4 eax 5 index leal pgh eax 4 eax pgh 20 index 13 105 Nested Array Element Access Array Elements A i j A i j is element of type T Address A i C j K int A R C A 0 A 0 0 A A i A 0 C 1 A i j A R 1 A i C 4 A R 1 0 A R 1 C 1 A R 1 C 4 A i C j 4 14 105 Nested Array Element Access Code Array Elements pgh index dig is int Address pgh 20 index 4 dig Code Computes address pgh 4 dig 4 index 4 index movl performs memory reference ecx dig eax index leal 0 ecx 4 edx leal eax eax 4 eax movl pgh edx eax 4 eax 15 int get pgh digit int index int dig return pgh index dig 4 dig 5 index pgh 4 dig 20 index 105 Strange Referencing Examples zip dig pgh 4 1 5 2 0 6 1 5 2 1 3 1 5 2 1 7 1 5 2 2 1 76 96 Reference Address 116 156 Value Guaranteed pgh 3 3 76 20 3 4 3 148 2 pgh 2 5 76 20 2 4 5 136 1 pgh 2 1 76 20 2 4 1 112 3 pgh 4 1 76 20 4 …
View Full Document
Unlocking...