15 213 The course that gives CMU its Zip Machine Level Programming IV Data Feb 5 2008 Structured Data class07 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 quad word GAS b w l q Bytes 1 2 4 8 C unsigned unsigned unsigned unsigned char short int long int x86 64 Floating Point 2 Stored operated on in floating point registers Intel Single Double Extended GAS s l t Bytes 4 8 10 12 16 C float double long double 15 213 S 08 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 IA32 char p 3 3 x86 64 x x x 4 x 8 x 8 x 12 x 16 15 213 x S 08 24 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 Type T Reference Type Value val 4 int 3 val val 1 int int x x 4 val 2 val 5 int int x 8 val 1 val i int int 5 x 4i int val 5 1 x 4 5 x 4 2 x 8 1 3 x 12 x 16 x 20 15 213 S 08 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 ucb 9 4 7 2 0 zip dig cmu 1 16 zip dig mit 20 0 36 zip dig ucb Notes 5 24 2 40 9 56 2 28 1 44 4 60 1 32 3 48 7 64 3 9 52 2 68 36 56 0 72 76 Declaration zip dig cmu equivalent to int cmu 5 Example arrays were allocated in successive 20 byte blocks Not guaranteed to happen in general 5 15 213 S 08 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 IA32 Memory Reference Code edx z eax dig movl edx eax 4 eax z dig 6 15 213 S 08 Referencing Examples zip dig cmu 1 16 zip dig mit 5 20 0 36 zip dig ucb 2 24 2 56 28 1 40 9 1 44 4 32 3 48 7 60 64 3 36 9 52 2 68 56 0 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 15 213 S 08 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 15 213 S 08 Array Loop Implementation IA32 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 15 213 S 08 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 15 213 S 08 Viewing as Multidimensional Array Declaration T A R C A 0 0 2D 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 15 213 S 08 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 15 213 S 08 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 IA32 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 15 213 S 08 Nested Array Element Access Array Elements A i j is element of type T Address A i C K j K A i j 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 15 213 S 08 Nested Array Element Access Code Array Elements pgh index dig is int Address pgh 20 index 4 dig IA32 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 …
View Full Document
Unlocking...