15 213 The course that gives CMU its Zip Machine Level Programming IV Structured Data Sept 18 2003 Topics Arrays Structs Unions class08 ppt 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 15 213 F 03 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 x 12 int val 5 x x 4 x 8 x 12 x 16 x 20 double a 4 x x 8 x 16 x 24 x 32 char p 3 x 3 x 4 x 8 15 213 F 03 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 int val 5 1 x Reference 4 5 2 x 8 x 4 Type Value val 4 int 3 val val 1 val 2 val 5 val 1 val i int int int int int int x x 4 x 8 5 x 4i 1 3 x 12 x 16 x 20 15 213 F 03 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 5 20 0 36 zip dig ucb 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 Notes 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 F 03 Array Accessing Example Computation Register edx contains starting address of array Register eax contains array index Desired digit at 4 eax edx int get digit zip dig z int dig return z dig Use memory reference edx eax 4 Memory Reference Code edx z eax dig movl edx eax 4 eax z dig 6 15 213 F 03 Referencing Examples zip dig cmu 1 16 zip dig mit 5 20 0 36 zip dig ucb 24 2 40 9 56 2 28 1 44 4 60 1 32 3 48 7 64 3 36 9 52 2 68 56 0 72 76 Code Does Not Do Any Bounds Checking Reference mit 3 mit 5 mit 1 cmu 15 Address 36 36 36 16 4 3 4 5 4 1 4 15 Value 48 56 32 76 3 9 3 Guaranteed Yes No No No Out of range behavior implementation dependent 7 No guaranteed relative allocation of different arrays 15 213 F 03 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 F 03 Array Loop Implementation Registers ecx z eax zi ebx zend Computations 10 zi z implemented as z 2 zi 4 zi z increments by 4 9 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 F 03 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 F 03 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 A 0 C 1 A R 1 0 A R 1 C 1 Array Size 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 A A R 1 R 1 0 C 1 4 R C Bytes 11 15 213 F 03 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 F 03 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 15 213 F 03 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 15 213 F 03 Nested Array Element Access Code Array Elements pgh index dig is int Address pgh 20 index 4 dig Code int get pgh digit int index int dig return pgh index dig 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 4 dig 5 index pgh 4 dig 20 index 15 213 F 03 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 …
View Full Document
Unlocking...