15 213 Machine Level Programming IV Data Sept 19 2007 Structured Data Arrays Structs Unions Data Control class07 ppt Buffer overflow 15 213 F 07 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 Intro to Computer Systems Fall 2007 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 IA32 char p 3 x x 4 x 8 x 12 x86 64 3 x 15 213 Intro to Systems x Computer 8 Fall 2007 x 16 x 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 z Type T int val 5 1 x Reference 4 5 2 x 4 x 8 1 3 x 12 x 16 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 15 213 Intro tox Computer 4 i Systems Fall 2007 x 20 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 z Not guaranteed to happen in general 5 15 213 Intro to Computer Systems Fall 2007 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 IA32 Memory Reference Code edx z eax dig movl edx eax 4 eax z dig 6 15 213 Intro to Computer Systems Fall 2007 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 7 Guaranteed Yes No No No Out of range behavior implementation dependent z No guaranteed relative allocation of different arrays 15 213 Intro to Computer Systems Fall 2007 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 Transformed Version As generated by GCC Eliminate loop variable i Convert array code to pointer code Express in do while form z No need to test at entrance 8 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 Intro to Computer Systems Fall 2007 Array Loop Implementation IA32 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 Intro to Computer Systems Fall 2007 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 Declaration zip dig pgh 4 equivalent to int pgh 4 5 z Variable pgh denotes array of 4 elements Allocated contiguously z Each element is an array of 5 int s Allocated contiguously 10 156 Row Major ordering of all elements guaranteed 15 213 Intro to Computer Systems Fall 2007 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 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 4 R C Bytes 11 15 213 Intro to Computer Systems Fall 2007 A A R 1 R 1 0 C 1 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 R 1 A A i R 1 C 1 0 A i C 4 15 213 Intro to Computer Systems Fall 2007 A R 1 C 4 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 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 Intro to Computer Systems Fall 2007 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 i C j 4 14 15 213 Intro to Computer Systems Fall 2007 A R 1 0 A R 1 C 4 A R 1 C 1 Nested Array Element Access Code Array Elements pgh index dig is int Address pgh 20 …
View Full Document
Unlocking...