Machine-Level Programming IV:DataSept. 20, 2006Machine-Level Programming IV:DataSept. 20, 2006Structured DataStructured Data Arrays Structs UnionsData/ControlData/Control Buffer overflowclass07.ppt15-213“The course that gives CMU its Zip!”–2–15-213, F’06Basic Data TypesBasic Data TypesIntegralIntegral Stored & operated on in general registers Signed vs. unsigned depends on instructions usedIntel GAS Bytes Cbyte b 1[unsigned] charword w 2[unsigned] shortdouble word l 4[unsigned] intquad word q 8[unsigned] long int (x86-64)Floating PointFloating Point Stored & operated on in floating point registersIntel GAS Bytes CSingle s 4 floatDouble l 8 doubleExtended t 10/12/16 long double–3–15-213, F’06Array AllocationArray AllocationBasic PrincipleBasic PrincipleT A[L]; Array of data type T and length L Contiguously allocated region of L * sizeof(T) byteschar string[12];xx + 12int val[5];xx + 4x + 8 x + 12 x + 16 x + 20double a[4];x + 32x + 24xx + 8 x + 16char *p[3];xx + 8 x + 16x + 24xx + 4x + 8 x + 12IA32x86-64–4–15-213, F’06Array AccessArray AccessBasic PrincipleBasic PrincipleT A[L]; Array of data type T and length L Identifier A can be used as a pointer to array element 0zType T*ReferenceReferenceTypeTypeValueValueval[4] int 3val int * xval+1 int * x + 4&val[2] int * x + 8val[5] int ??*(val+1) int 5val + i int * x + 4 i1 5 2 1 3int val[5];xx + 4x + 8 x + 12 x + 16 x + 20–5–15-213, F’06Array ExampleArray ExampleNotesNotes Declaration “zip_dig cmu” equivalent to “int cmu[5]” Example arrays were allocated in successive 20 byte blocksz Not guaranteed to happen in generaltypedef 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 5 2 1 316 20 24 28 32 36zip_dig mit;0 2 1 3 936 40 44 48 52 56zip_dig ucb;9 4 7 2 056 60 64 68 72 76–6–15-213, F’06Array Accessing ExampleArray Accessing ExampleIA32 Memory Reference CodeIA32 Memory Reference Codeint get_digit(zip_dig z, int dig){return z[dig];}# %edx = z# %eax = digmovl (%edx,%eax,4),%eax # z[dig]ComputationComputation Register %edx contains starting address of array Register %eax contains array index Desired digit at 4*%eax + %edx Use memory reference (%edx,%eax,4)–7–15-213, F’06Referencing ExamplesReferencing ExamplesCode Does Not Do Any Bounds Checking!Code Does Not Do Any Bounds Checking!ReferenceReferenceAddressAddressValueValueGuaranteed?Guaranteed?mit[3] 36 + 4* 3 = 48 3mit[5] 36 + 4* 5 = 56 9mit[-1] 36 + 4*-1 = 32 3cmu[15] 16 + 4*15 = 76 ?? Out of range behavior implementation-dependentzNo guaranteed relative allocation of different arrays zip_dig cmu;1 5 2 1 316 20 24 28 32 36zip_dig mit;0 2 1 3 936 40 44 48 52 56zip_dig ucb;9 4 7 2 056 60 64 68 72 76YesYesNoNoNoNoNoNo–8–15-213, F’06int zd2int(zip_dig z){int i;int zi = 0;for (i = 0; i < 5; i++) {zi = 10 * zi + z[i];}return zi;}Array Loop ExampleArray Loop ExampleOriginal SourceOriginal Sourceint zd2int(zip_dig z){int zi = 0;int *zend = z + 4;do {zi = 10 * zi + *z;z++;} while (z <= zend);return zi;}Transformed VersionTransformed Version As generated by GCC Eliminate loop variable i Convert array code to pointer code Express in do-while formzNo need to test at entrance–9–15-213, F’06# %ecx = zxorl %eax,%eax# zi = 0leal 16(%ecx),%ebx # zend = z+4.L59:leal (%eax,%eax,4),%edx # 5*zimovl (%ecx),%eax # *zaddl $4,%ecx # z++leal (%eax,%edx,2),%eax # zi = *z + 2*(5*zi)cmpl %ebx,%ecx # z : zendjle .L59 # if <= goto loopArray Loop Implementation (IA32)Array Loop Implementation (IA32)RegistersRegisters%ecx z%eax zi%ebx zendComputationsComputations 10*zi + *z implemented as *z + 2*(zi+4*zi)z++ increments by 4int zd2int(zip_dig z){int zi = 0;int *zend = z + 4;do {zi = 10 * zi + *z;z++;} while(z <= zend);return zi;}# %ecx = zxorl %eax,%eax # zi = 0leal 16(%ecx),%ebx# zend = z+4.L59:leal (%eax,%eax,4),%edx # 5*zimovl (%ecx),%eax # *zaddl $4,%ecx # z++leal (%eax,%edx,2),%eax # zi = *z + 2*(5*zi)cmpl %ebx,%ecx # z : zendjle .L59 # if <= goto loopint zd2int(zip_dig z){int zi = 0;int *zend = z + 4;do {zi = 10 * zi + *z;z++;} while(z <= zend);return zi;}# %ecx = zxorl %eax,%eax # zi = 0leal 16(%ecx),%ebx # zend = z+4.L59:leal (%eax,%eax,4),%edx# 5*zimovl (%ecx),%eax# *zaddl $4,%ecx # z++leal (%eax,%edx,2),%eax# zi = *z + 2*(5*zi)cmpl %ebx,%ecx # z : zendjle .L59 # if <= goto loopint zd2int(zip_dig z){int zi = 0;int *zend = z + 4;do {zi = 10 * zi + *z;z++;} while(z <= zend);return zi;}# %ecx = zxorl %eax,%eax # zi = 0leal 16(%ecx),%ebx # zend = z+4.L59:leal (%eax,%eax,4),%edx # 5*zimovl (%ecx),%eax # *zaddl $4,%ecx# z++leal (%eax,%edx,2),%eax # zi = *z + 2*(5*zi)cmpl %ebx,%ecx # z : zendjle .L59 # if <= goto loopint zd2int(zip_dig z){int zi = 0;int *zend = z + 4;do {zi = 10 * zi + *z;z++;} while(z <= zend);return zi;}# %ecx = zxorl %eax,%eax # zi = 0leal 16(%ecx),%ebx # zend = z+4.L59:leal (%eax,%eax,4),%edx # 5*zimovl (%ecx),%eax # *zaddl $4,%ecx # z++leal (%eax,%edx,2),%eax # zi = *z + 2*(5*zi)cmpl %ebx,%ecx# z : zendjle .L59# if <= goto loopint zd2int(zip_dig z){int zi = 0;int *zend = z + 4;do {zi = 10 * zi + *z;z++;} while(z <= zend);return zi;}–10–15-213, F’06Nested Array ExampleNested Array Example Declaration “zip_dig pgh[4]” equivalent to “int pgh[4][5]”z Variable pgh denotes array of 4 elements» Allocated contiguouslyz Each element is an array of 5 int’s» Allocated contiguously “Row-Major” ordering of all elements guaranteed#define PCOUNT 4zip_dig pgh[PCOUNT] = {{1, 5, 2, 0, 6},{1, 5, 2, 1, 3 },{1, 5, 2, 1, 7 },{1, 5, 2, 2, 1 }};zip_digpgh[4];76 96 116 136 1561 5 2 0 6 1 5 2 1 3 1 5 2 1 7 1 5 2 2 1–11–15-213, F’06Viewing as Multidimensional ArrayViewing as Multidimensional ArrayDeclarationDeclarationT A[R][C]; 2D array of data type T R rows, C columns Type T element requires KbytesArray SizeArray Size R * C * K bytesArrangementArrangement Row-Major OrderingA[0][0] A[0][C-1]A[R-1][0]••••••A[R-1][C-1]••••••int A[R][C];A[0][0]A[0][C-1]•••A[1][0]A[1][C-1]•••A[R-1][0]A[R-1][C-1]••••••4*R*C Bytes–12–15-213, F’06•••Nested Array Row AccessNested Array Row AccessRow VectorsRow Vectors A[i] is array of C elements Each element of type T Starting address A + i * (C * K)A[i][0]A[i][C-1]•••A[i]A[R-1][0]A[R-1][C-1]•••A[R-1]•••AA[0][0]A[0][C-1]•••A[0]int A[R][C];A+i*C*4
View Full Document