15 213 The course that gives CMU its Zip Structured Data I Homogenous Data Sept 21 2000 Topics Arrays Single Nested Pointers Multilevel Arrays Optimized Array Code class08 ppt Basic Data Types Integral Stored operated on in general registers Signed vs unsigned depends on instructions used Intel GAS Bytes C byte b 1 unsigned char word w 2 unsigned short double word l 4 unsigned int Floating Point Stored operated on in floating point registers Intel GAS Bytes C Single s 4 float Double l 8 double Extended t 10 12 long double class08 ppt 2 CS 213 F 00 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 char p 3 x class08 ppt x 4 3 x 8 CS 213 F 00 x 32 Array Access Basic Principle T A L Array of data type T and length L Identifier A can be used as a pointer to starting element of the array int val 5 1 x Reference val 4 val val 1 val 2 val 5 val 1 val i class08 ppt 5 x 4 2 x 8 Type Value int int int int int int int 3 x x 4 x 8 5 x 4i 4 1 3 x 12 x 16 x 20 CS 213 F 00 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 class08 ppt 5 CS 213 F 00 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 class08 ppt 6 CS 213 F 00 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 9 52 2 68 36 56 0 72 76 Code Does Not Do Any Bounds Checking Reference Address Value Guaranteed mit 3 36 4 3 48 3 Yes mit 5 36 4 5 56 9 No mit 1 36 4 1 32 3 No cmu 15 16 4 15 76 No Out of range behavior implementation dependent No guranteed relative allocation of different arrays class08 ppt 7 CS 213 F 00 Array Loop Example int zd2int zip dig z int i int zi 0 for i 0 i 5 i zi 10 zi z i return zi Original Source int zd2int zip dig z int zi 0 int zend z 4 do zi 10 zi z z while z zend return zi Transformed Version Eliminate loop variable i Convert array code to pointer code Express in do while form No need to test at entrance class08 ppt 8 CS 213 F 00 Array Loop Implementation int zd2int zip dig z int zi 0 int zend z 4 do zi 10 zi z z while z zend return zi Registers ecx eax ebx z zi zend Computations 10 zi z implemented as z 2 zi 4 zi z increments by 4 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 class08 ppt 9 zi 0 zend z 4 5 zi z z zi z 2 5 zi z zend if goto loop CS 213 F 00 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 class08 ppt 10 CS 213 F 00 Nested Array Allocation Declaration T A R C Array of data type T R rows C columns Type T element requires K bytes a 0 0 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 class08 ppt 11 CS 213 F 00 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 i A 0 C 1 A A i 0 A i C 4 class08 ppt 12 A R 1 A A i R 1 C 1 0 A R 1 C 4 CS 213 F 00 A R 1 C 1 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 class08 ppt 13 CS 213 F 00 Nested Array Element Access Array Elements A i j is element of type T Address A i C j K A i j int A R C A 0 A 0 0 A i A 0 C 1 A A i j A R 1 A i C 4 A R 1 0 A R 1 C 4 A i C j 4 class08 ppt 14 CS 213 F 00 A R 1 C 1 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 class08 ppt 15 4 dig 5 index pgh 4 dig 20 index CS 213 F 00 …
View Full Document
Unlocking...