Machine-Level Programming VII:Structured DataTopicsTopics Arrays Structs UnionsSystems I2Basic 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] intFloating PointFloating Point Stored & operated on in floating point registersIntel GAS Bytes CSingle s 4 floatDouble l 8 doubleExtended t 10/12 long double3Array AllocationBasic PrincipleBasic PrincipleT A[L]; Array of data type T and length L Contiguously allocated region of L * sizeof(T) byteschar string[12];x x + 12int val[5];xx + 4 x + 8 x + 12 x + 16 x + 20double a[4];x + 32x + 24xx + 8 x + 16char *p[3];xx + 4 x + 84Array AccessBasic PrincipleBasic PrincipleT A[L]; Array of data type T and length L Identifier A can be used as a pointer to array element 0ReferenceReferenceTypeTypeValueValueval[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 + 4 x + 8 x + 12 x + 16 x + 205Array ExampleNotesNotes Declaration “zip_dig cmu” equivalent to “int cmu[5]” Example arrays were allocated in successive 20 byte blocks 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 766Array Accessing ExampleMemory Reference CodeMemory 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 startingaddress of array Register %eax contains arrayindex Desired digit at 4*%eax + %edx Use memory reference(%edx,%eax,4)7Referencing 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-dependentNo guaranteed relative allocation of different arrayszip_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 76YesYesNoNoNoNoNoNo8int zd2int(zip_dig z){ int i; int zi = 0; for (i = 0; i < 5; i++) { zi = 10 * zi + z[i]; } return zi;}Array 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 topointer code Express in do-while formNo need to test at entrance9# %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 ImplementationRegistersRegisters%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;}10Nested Array Example 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#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 111Nested Array AllocationDeclarationDeclarationT A[R][C]; 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 Bytes12• !•! •Nested Array Row AccessRow VectorsRow Vectors A[i] is array of C elements Each element of type T Starting address A + i * C * KA[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 A+(R-1)*C*413Nested Array Row Access CodeRow VectorRow Vector pgh[index] is array of 5 intʼs Starting address pgh+20*indexCodeCode Computes and returns address Compute as pgh + 4*(index+4*index)int *get_pgh_zip(int index){ return pgh[index];} # %eax = indexleal (%eax,%eax,4),%eax # 5 * indexleal pgh(,%eax,4),%eax # pgh + (20 * index)14•!•!• Nested Array Element Access Array Elements Array Elements A[i][j] is element of type T Address A + (i * C + j) * K• !•! •A[i][j]A[i][j]