DOC PREVIEW
Harvey Mudd CS 105 - Machine­Level Programming IV: Structured Data

This preview shows page 1-2-3-21-22-23-43-44-45 out of 45 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 45 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 DataTopicsTopicsArraysStructsUnionsX86.4.pptCS 105“Tour of the Black Holes of Computing– 2 –105Basic 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] intFloating PointFloating PointStored & 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 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 + 8– 4 –105Array 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 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 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 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]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 –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-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 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 VersionAs generated by GCCEliminate loop variable iConvert array code to pointer codeExpress in do-while formNo 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 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


View Full Document

Harvey Mudd CS 105 - Machine­Level Programming IV: Structured Data

Documents in this Course
Processes

Processes

25 pages

Processes

Processes

27 pages

Load more
Download Machine­Level Programming IV: Structured Data
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Machine­Level Programming IV: Structured Data and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Machine­Level Programming IV: Structured Data 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?