Machine-Level Programming IV: Structured DataBasic Data TypesArray AllocationArray AccessArray ExampleArray Accessing ExampleReferencing ExamplesArray Loop ExampleArray Loop ImplementationNested Array ExampleNested Array AllocationNested Array Row AccessNested Array Row Access CodeNested Array Element AccessNested Array Element Access CodeStrange Referencing ExamplesMulti-Level Array ExampleElement Access in Multi-Level ArrayArray Element AccessesSlide 20Using Nested ArraysDynamic Nested ArraysDynamic Array MultiplicationOptimizing Dynamic Array Mult.Dynamic Arrays with PointersStructuresGenerating Pointer to a Structure MemberStructure Referencing (Cont.)AlignmentSpecific Cases of AlignmentSatisfying Alignment within StructuresLinux vs. WindowsOverall Alignment RequirementOrdering Elements in StructureArrays of StructuresAccessing Element within ArraySatisfying Alignment in StructureUnion AllocationUsing Union to Access Bit PatternsByte Ordering RevisitedByte Ordering ExampleByte Ordering Example (Cont).Byte Ordering on x86Byte Ordering on SunSummaryMachine-Level Programming IV:Structured DataMachine-Level Programming IV:Structured DataTopicsTopicsArraysStructsUnionsX86.4.pptCS 105“Tour of the Black Holes of Computing– 2 –105Basic Data TypesBasic Data TypesIntegralIntegralStored & operated on in general registersSigned vs. unsigned depends on instructions usedIntel GAS Bytes Cbyte b 1 [unsigned] charword w 2 [unsigned] shortdouble word l 4 [unsigned] intFloating PointFloating PointStored & operated on in floating point registersIntel GAS Bytes CSingle s 4 floatDouble l 8 doubleExtended t 10/12 long double– 3 –105Array AllocationArray AllocationBasic PrincipleBasic PrincipleT A[L];Array of data type T and length LContiguously 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 + 8– 4 –105Array AccessArray AccessBasic PrincipleBasic PrincipleT A[L];Array of data type T and length LIdentifier A can be used as a pointer to array element 0ReferenceReferenceTypeTypeValueValueval[4] int 3val int[5] x (acts like int *)val+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 + 20– 5 –105Array ExampleArray ExampleNotesNotesDeclaration “zip_dig cmu” equivalent to “int cmu[5]”Example arrays were allocated in successive 20 byte blocksNot 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 hmc = { 9, 1, 7, 1, 1 };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 hmc;9 1 7 1 156 60 64 68 72 76– 6 –105Array Accessing ExampleArray 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]ComputationComputationRegister %edx contains starting address of arrayRegister %eax contains array indexDesired digit at 4*%eax + %edxUse memory reference (%edx,%eax,4)– 7 –105Referencing 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-dependentNo 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 hmc;9 1 7 1 156 60 64 68 72 76YesYesNoNoNoNoNoNo– 8 –105int 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 VersionAs generated by GCCEliminate loop variable iConvert array code to pointer codeExpress in do-while formNo need to test at entrance– 9 –105# %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 ImplementationArray 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;}– 10 –105Nested Array ExampleNested Array ExampleDeclaration “zip_dig pgh[4]” equivalent to “int pgh[4][5]”Variable pgh denotes array of 4 elements»Allocated contiguouslyEach element is an array of 5 int’s»Allocated contiguously“Row-Major” ordering of all elements
View Full Document