Systems I Machine Level Programming VII Structured Data Topics 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 GAS s l t Bytes 4 8 10 12 C float double long double 2 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 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 x 4 x 8 3 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 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 4 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 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 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 Guaranteed Yes No No No Out of range behavior implementation dependent No guaranteed relative allocation of different arrays 7 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 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 8 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 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 9 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 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 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 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 12 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 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 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 4 dig 5 index pgh 4 dig 20 index 15 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 136 156 Value Guaranteed pgh 3 3 76 20 3 4 3 148 2 Yes pgh 2 5 76 20 2 4 5 136 1 Yes pgh 2 1 76 20 2 4 1 112 3 Yes pgh 4 1 76 20 4 4 1 152 1 Yes pgh 0 19 76 20 0 4 19 152 1 Yes pgh 0 1 76 20 0 4 1 …
View Full Document
Unlocking...