15 213 The course that gives CMU its Zip Machine Level Programming IV Structured Data Sept 19 2002 Topics class08 ppt n Arrays n Structs n Unions Basic Data Types Types Integral n Stored operated on in general registers n 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 n 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 02 Array Allocation Basic Principle T A L n n 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 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 15 213 F 02 Array Access Basic Principle T A L n n 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 4 x 8 Type Value val 4 int 3 val int x val 1 int x 4 val 2 int x 8 val 5 int val 1 int 5 val i int x 4i 1 3 x 12 x 16 x 20 15 213 F 02 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 n Declaration zip dig cmu equivalent to int cmu 5 n Example arrays were allocated in successive 20 byte blocks l Not guaranteed to happen in general 5 15 213 F 02 Array Accessing Example Computation n n n n 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 02 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 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 n 7 Guaranteed Yes No No No Out of range behavior implementation dependent l No guaranteed relative allocation of different arrays 15 213 F 02 Array Loop Example Original Source Transformed Version n n As generated by GCC Eliminate loop variable i n Convert array code to pointer code n Express in do while form l 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 02 Array Loop Implementation Implementation Registers ecx z eax zi ebx zend Computations 10 zi z implemented as z 2 zi 4 zi n z increments by 4 n 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 02 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 n 96 116 136 156 Declaration zip dig pgh 4 equivalent to int pgh 4 5 l Variable pgh denotes array of 4 elements Allocated contiguously l Each element is an array of 5 int s Allocated contiguously n 10 Row Major ordering of all elements guaranteed 15 213 F 02 Nested Array Allocation Allocation Declaration T A R C A 0 0 n Array of data type T n R rows C columns n Type T element requires K bytes A 0 C 1 A R 1 0 A R 1 C 1 Array Size n R C K bytes Arrangement n 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 02 Nested Array Row Access Row Vectors n n n 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 02 Nested Array Row Access Code Code int get pgh zip int index return pgh index Row Vector n pgh index is array of 5 int s n Starting address pgh 20 index Code n n 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 02 Nested Array Element Access Array Elements n n 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 02 Nested Array Element Access Code Code Array Elements pgh index dig is int n n Address pgh 20 index 4 dig Code n int get pgh digit int index int dig return pgh index dig Computes address pgh 4 dig 4 index 4 index n movl performs memory reference ecx dig eax index leal 0 ecx 4 edx leal eax eax …
View Full Document
Unlocking...