Structured Data I:Homogenous DataFebruary 8, 2001Topics• Arrays–Single–Nested• Pointers–Multilevel Arrays• Optimized Array Codeclass08.ppt15-213“The course that gives CMU its Zip!”CS 213 S’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 doublePointer• Stored & operated on in general registersIntel GAS Bytes CDouble l 8char *CS 213 S’01–3 –class08.pptArray AllocationBasic PrincipleT A[L];• Array named A of data type T with L elements • 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 + 4x + 8CS 213 S’01–4 –class08.pptArray AccessBasic PrincipleT A[L];• Array named A 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 S’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_digcmu={1,5,2,1,3};zip_digmit={0,2,1,3,9};zip_digucb={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 S’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 starting address of array• Register %eax contains array index• Desired digit at 4*%eax + %edx• Use memory reference (%edx,%eax,4)CS 213 S’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 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 76CS 213 S’01–8 –class08.pptint zd2int(zip_dig z){int i;intzi=0;for(i=0;i<5;i++){zi=10*zi+z[i];}return zi;}Array Loop ExampleOriginal Sourceint zd2int(zip_dig z){intzi=0;int*zend=z+4;do {zi=10*zi+*z;z++;} while(z <= zend);return zi;}Transformed Version• Eliminate loop variable i• Convert array code to pointer code• Express in do-while form–No need to test at entranceCS 213 S’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){intzi=0;int*zend=z+4;do {zi=10*zi+*z;z++;} while(z <= zend);return zi;}CS 213 S’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 S’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 S’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 S’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 S’01–14 –class08.pptNested Array Element AccessArray 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 S’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 S’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 S’01–17 –class08.pptMulti-Level Array Example• Variable univdenotes array of 3 elements• Each element is a pointer–4 bytes• Each pointer points to array of int’s zip_digcmu={1,5,2,1,3};zip_digmit={0,2,1,3,9};zip_digucb={9,4,7,2,0};#define UCOUNT 3int *univ[UCOUNT] = {mit, cmu, ucb};361601656164168univcmu1 5 2 1 316 20 24 28
View Full Document