Structured Data:Sept. 20, 2001Topics• Arrays• Structs• Unionsclass08.ppt15-213“The course that gives CMU its Zip!”CS 213 F’01– 2 –class08.pptBasic Data TypesIntegral• 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 Point• Stored & operated on in floating point registersIntel GAS Bytes CSingle s 4 floatDouble l 8 doubleExtended t 10/12 long doubleCS 213 F’01– 3 –class08.pptArray AllocationBasic 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 + 8CS 213 F’01– 4 –class08.pptArray AccessBasic PrincipleT A[L];• Array of data type T and length L• Identifier A can be used as a pointer to starting element of the arrayReference Type Valueval[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 + 20CS 213 F’01– 5 –class08.pptArray ExampleNotes• 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 76CS 213 F’01– 6 –class08.pptArray Accessing ExampleMemory Reference Codeint get_digit (zip_dig z, int dig){ return z[dig];} # %edx = z # %eax = digmovl (%edx,%eax,4),%eax # z[dig]Computation• Register %edx contains startingaddress of array• Register %eax contains arrayindex• Desired digit at 4*%eax + %edx• Use memory reference(%edx,%eax,4)CS 213 F’01– 7 –class08.pptReferencing ExamplesCode Does Not Do Any Bounds Checking!Reference Address Value Guaranteed?mit[3] 36 + 4* 3 = 48 3 Yesmit[5] 36 + 4* 5 = 56 9 Nomit[-1] 36 + 4*-1 = 32 3 Nocmu[15] 16 + 4*15 = 76 ?? No• 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 76CS 213 F’01– 8 –class08.pptint 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 Sourceint zd2int(zip_dig z){ int zi = 0; int *zend = z + 4; do { zi = 10 * zi + *z; z++; } while(z <= zend); return zi;}Transformed Version• As generated by GCC• Eliminate loop variable i• Convert array code topointer code• Express in do-while form–No need to test atentranceCS 213 F’01– 9 –class08.ppt# %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 ImplementationRegisters%ecx z%eax zi%ebx zendComputations• 10*zi + *zimplemented 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;}CS 213 F’01– 10 –class08.pptNested 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 1CS 213 F’01– 11 –class08.pptNested Array AllocationDeclarationT A[R][C];• Array of data type T• R rows• C columns• Type T element requires K bytesArray Size• R * C * K bytesArrangement• 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 BytesCS 213 F’01– 12 –class08.ppt• • •Nested Array Row AccessRow 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*4CS 213 F’01– 13 –class08.pptNested Array Row Access CodeRow Vector• pgh[index] is array of 5 int’s• Starting address pgh+20*indexCode• 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)CS 213 F’01– 14 –class08.pptNested Array Element Access Array Elements• A[i][j] is element of type T• Address A + (i * C + j) * K• • •A[i][j]A[i][j] • • •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*4• • • A+(i*C+j)*4CS 213 F’01– 15 –class08.pptNested Array Element Access CodeArray Elements• pgh[index][dig] is int• Address: pgh + 20*index + 4*digCode• Computes addresspgh + 4*dig + 4*(index+4*index)• movl performs memory referenceint get_pgh_digit (int index, int dig){ return pgh[index][dig];}# %ecx = dig# %eax = indexleal 0(,%ecx,4),%edx # 4*digleal (%eax,%eax,4),%eax # 5*indexmovl pgh(%edx,%eax,4),%eax # *(pgh + 4*dig + 20*index)CS 213 F’01– 16 –class08.pptStrange Referencing ExamplesReference Address Value Guaranteed?pgh[3][3] 76+20*3+4*3 = 148 2 Yespgh[2][5] 76+20*2+4*5 = 136 1 Yespgh[2][-1] 76+20*2+4*-1 = 112 3 Yespgh[4][-1] 76+20*4+4*-1 = 152 1 Yespgh[0][19] 76+20*0+4*19 = 152 1 Yespgh[0][-1] 76+20*0+4*-1 = 72 ?? No• Code does not do any bounds checking• Ordering of elements within array guaranteedzip_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 1CS 213 F’01– 17 –class08.pptMulti-Level Array Example• Variable univdenotes array of 3elements• Each element is apointer–4 bytes• Each pointer pointsto array of int’szip_dig cmu = { 1, 5, 2, 1, 3 };zip_dig mit = { 0, 2, 1, 3, 9 };zip_dig ucb = { 9, 4,
View Full Document
Unlocking...