WIXLIB

Computer Organization &Assembly LanguagesIntroductionPu-Jen Cheng2008/09/15

Course Administration Instructor: Pu-Jen Cheng (CSIE u.tw/ pjcheng Class Hours: 2:00pm-5:00pm, Monday Classroom: CSIE R102 TA(s): 戴瑋彥 b93705014@ntu.edu.tw Course Information:Announce: http://www.csie.ntu.edu.tw/ pjcheng/course/asm2008/Q&A: bbs://ptt.cc CSIE ASM

TextbookAssembly Language for Intel-Based Computers, 5th Edition,by Kip Irvine, Prentice-Hall, 2006 http://www.asmirvine.com

References Computer Systems: A Programmer's PerspectiveBy Randal E. Bryant and David R. O'Hallaron,Prentice Hallhttp://csapp.cs.cmu.edu/The Art of Assembly LanguageBy Randy Hyde,http://webster.cs.ucr.edu/AoA/Windows/PDFs/0 PDFIndexWin.htmlSystem Software: An Introduction to SystemsProgrammingBy Leland L. BeckAddison-Wesley

Pre-requisite Experiences in writing programs in a high-levellanguage such as C, C , and Java

Course Grading (tentative) Assignments (55%)Class participation (5%)Midterm exam (20%)Final exam (20%)

Materials Some materials used in this course are adapted from¾¾¾¾The slides prepared by Kip Irvine for the book, Assembly Languagefor Intel-Based Computers, 5th Ed.The slides prepared by S. Dandamudi for the book, Introduction toAssembly Language Programming, 2nd Ed.Introduction to Computer Systems,Systems class/15213-f05/www/)Assembly Language & Computer Organization, NTU(http://www.csie.ntu.edu.tw/ e.ntu.edu.tw/ acpang/course/asm 2004)

What is Assembly Language First Glance at Assembly Language

Translating LanguagesEnglish: Display the sum of A times B plus C.C : cout (A * B C);Assembly Language:mov eax,Amul Badd eax,Ccall WriteIntIntel Machine Language:A1 00000000F7 25 0000000403 05 00000008E8 00500000

A Simple Example in VC

View/Debug Windows/Disassembly

gcc -s prog.c

The Compilation System

First Glance at Assembly Language Low-level language¾¾ One-to-one correspondence between assemblylanguage and machine language instructions¾ Each instruction performs a much lower-level taskcompared to a high-level language instructionMost high-level language instructions need more thanone assembly instructionFor most assembly language instructions, there is amachine language equivalentDirectly influenced by the instruction set andarchitecture of the processor (CPU)

Comparisons with High-level Languages Advantages of Assembly Languages¾Space-efficiency(e.g. hand-held device softwares, etc)¾Time-efficiency(e g Real-time applications,(e.g.applications etc )¾Accessibility to system hardwares(e.g., Network interfaces, device drivers, video games, etc) Advantages of High-level Languages¾¾¾DevelopmentMaintenance (Readability)Portability (compiler, virtual machine)

Comparisons with High-level Languages (cont.)

Why Taking the Course?Basic Concepts ofComputerOrganizationComputer DesignThis CourseComputer OrganizationComputer r, Linker, LoaderCompiler, Operating System,

“I really don’t think that you can write a book forserious computer programmers unless you areable to discuss low-level details.”Donald Knuth (高德納)The Art of Computer Programminghttp://en.wikipedia.org/wiki/Donald Knuth

Course Coverage Basic ConceptsIA-32 Processor ArchitectureAssembly Language FundamentalsData Transfers, Addressing, and ArithmeticProceduresConditional ProcessingInteger ArithmeticAdvanced ProceduresStrings and ArraysStructures and MacrosHigh-Level Language InterfaceAssembler, Linker, and LoaderOther Advanced Topics (optional)

What You Will Learn Basic principles of computer architectureIA-32 processors and memory managementBasic assembly programming skillsHow high-level language is translated to assemblyHow assembly is translated to machine codeHow application program communicates with OSInterface between assembly to high-level language

Performance: Multiword Arithmetic Longhand multiplication¾Final 128-bit result in P:A P : 0; count : 64A : multiplier; B : multiplicandwhile (count 0)if (LSB of A 1)then P : P BCF : carry generated by P Belse CF : 0end ifshift right CF:P:A by one bit positioncount : count-1end while01011101010101010101

Example A 11012 (13)B 01012 (5)After P BCFPAfter the shiftACFPAInitial state?00001101----------Iteration 1001011101?00101110Iteration 2000101110?00010111Iteration 3001100111?00110011Iteration 4010000011?01000001

Time Comparison5Timee (seconds)4C version32ASM version10020406080100Number of calls (in millions)Multiplication time comparison on a 2.4-GHz Pentium 4 system

Chapter 1: Basic Concept Virtual Machine ConceptData RepresentationBoolean Operations

Translating LanguagesEnglish: Display the sum of A times B plus C.C : cout (A * B C);Assembly Language:mov eax,Amul Badd eax,Ccall WriteIntIntel Machine Language:A1 00000000F7 25 0000000403 05 00000008E8 00500000

Virtual MachinesAbstractions for computersMachine-independentHigh-Level LanguageLevel 5Assembly LanguageLevel 4Operating SystemLevel 3Instruction SetArchitectureLevel 2MicroarchitectureLevel 1Digital LogicLevel 0Machine-specific

High-Level Language Level 5Application-oriented languages¾ C , Java, Pascal, Visual Basic . . .Programs compile into assembly language(Level 4)

Assembly Language Level 4Instruction mnemonics that have a oneto-one correspondence to machinelanguageCalls functions written at the operatingsystem level (Level 3)Programs are translated into machinelanguage (Level 2)

Operating System Level 3Provides services to Level 4 programsTranslated and run at the instruction setarchitecture level (Level 2)

Instruction Set Architecture Level 2Also known as conventional machinelanguageExecuted by Level 1 (microarchitecture)program

Microarchitecture Level 1Interprets conventional machineinstructions (Level 2)Executed by digital hardware (Level 0)

Digital Logic Level 0CPU, constructed from digital logic gatesSystem busMemorynext: Data Representation

Data Representation Binary Numbers¾ Binary AdditionInteger Storage SizesHexadecimal Integersg¾¾ Translating between decimal and hexadecimalHexadecimal subtractionSigned Integers¾ Translating between binary and decimalBinary subtractionFractional Binary NumbersCharacter StorageMachine Words

Binary Representation Electronic Implementation¾¾Easy to store with bistable elementsReliably transmitted on noisy and inaccurate wires

Binary Numbers Digits are 1 and 0¾¾ 1 true0 falseMSB – most significant bitLSB – least significant bitBit numbering:MSBLSB1011001010011100150

Binary Numbers Each digit (bit) is either 1 or 0Each bit represents a power of 2:Every binarynumber is asum of powersof 2111111112726252423222120

Translating Binary to DecimalWeighted positional notation shows how tocalculate the decimal value of each binary bit:dec (Dn-1 2n-1) (Dn-2 2n-2) . (D1 21) (D0 20)D binary digitbinary 00001001 decimal 9:(1 23) (1 20) 9

Translating Unsigned Decimal to Binary Repeatedly divide the decimal integer by 2.Each remainder is a binary digit in the translated value:37 100101

Binary Addition Starting with the LSB, add each pair of digits, include thecarry if present. bit 76543210

Integer Storage SizesStandard sizes:byteworddoublewordquadword8163264What is the largest unsigned integer that may be stored in 20 bits?

Large Measurements Kilobyte (KB), 210 bytesMegabyte (MB), 220 bytesGigabyte (GB), 230 bytesTerabyte (TB), 240 bytesPetabyte, 250 bytesExabyte, 260 bytesZettabyte, 270 bytesYottabyte, 280 bytesGoogol, 10100

Hexadecimal IntegersBinary values are represented in hexadecimal.

Translating Binary to Hexadecimal Each hexadecimal digit corresponds to 4 binarybits.Example: Translate the binary integer000101101010011110010100 to hexadecimal:

Converting Hexadecimal to Decimal Multiply each digit by its corresponding power of16:dec (D3 163) (D2 162) (D1 161) (D0 160) Hex 1234 equals (1 163) (2 162) (3 161) (4 160), or decimal 4,660.Hex 3BA4 equals (3 163) (11 * 162) (10 161) (4 160), or decimal 15,268.

Powers of 16 Used when calculating hexadecimal values up to 8digits long:

Converting Decimal to Hexadecimaldecimal 422 1A6 hexadecimal

Hexadecimal Addition Divide the sum of two digits by the number base (16).The quotient becomes the carry value, and the remainderis the sum digit.36427828456D128588016A4BB521 / 16 1, rem 5Important skill: Programmers frequently add andsubtract the addresses of variables and instructions.

Hexadecimal Subtraction When a borrow is required from the digit to the left,add 16 (decimal) to the current digit's value:16 5 21C6A224 175472EPractice: The address of var1 is 00400020. Theaddress of the next variable after var1 is 0040006A.How many bytes are used by var1?

Signed IntegersThe highest bit indicates the sign. 1 negative, 0 positive sign bit11110110Negative00001010PositiveIf the highest digit of a hexadecimal integer is 7, thevalue is negative. Examples: 8A, C5, A2, 9D

Forming the Two's Complement Bitwise NOT of the number and add 1Note that 00000001 11111111 00000000

8-bit Two's Complement Integers

Binary SubtractionWhen subtracting A – B, convert B to its two'scomplement Add A to (–B)0000110000001100– 000000111111110100001001Advantages for 2’s complement: No two 0’s Sign bit Remove the need for separate circuits for addand sub

Ranges of Signed Integers The highest bit is reserved for the sign. This limitsthe range:

Fractional Binary Numbers2i2i–1421 b2 b1 b0 .b–11 b–22 b–33 1/21/41/8 Representation¾¾b–j bi bi–11 2–jBits to right of “binary point” represent fractionalpowers of 2ikb 2 kRepresents rational number:k j

Examples of Fractional Binary Numbers Value5-3/42-7/863/64 ivide by 2 by shifting right¾ Multiply by 2 by shifting left¾ Numbers of form 0.111111 2 just below 1.0i 1/2 1/4 1/8 1/2 1.0 Use notation 1.0 – ε¾

Representable Numbers LimitationCan only exactly represent numbers of the form¾ Other numbers have repeating bit representations¾ Value1/3/1/51/10Representation0.0101010101[01] 20.001100110011[0011] 20.0001100110011[0011] 2

Converting Real Numbers Binary real to decimal real Decimal real to binary real4.5625 100.10012

True or False IfIfIfIfIfIfIfIfxxxxxxxx 0 then x 1 0 0 then x * 2 0 y then -x -y 0 then -x 0 0 then -x 0 0 then (( !x – 1 ) & x ) x 0 && y 0 then x * y 0 0 then ((x x 31) 1) 0

Character Storage Character sets¾¾¾¾ Null-terminated String¾ Standard ASCII (0 – 127)Extended ASCII (0 – 255)ANSI (0 – 255)Unicode (0 – 65,535)65 535)Array of characters followed by a null byteUsing the ASCII table¾back inside cover of book

Machine Words Machine Has “Word Size”¾¾Nominal size of integer-valued data Including addressesMost current machines use 32 bits (4 bytes) words Limits addresses to 4GB Becoming too small for memory-intensive applicationsHigh-end systems use 64 bits (8 bytes) words19 bytes Potential address space 1.8 X 10 x86-64 machines support 48-bit addresses: 256 TerabytesMachines support multiple data formats Fractions or multiples of word size Always integral number of bytes ¾¾Users can access 3GB

Word-Oriented Memory Organization32-bit 64-bitWords Words Addresses Specify ByteLocations¾¾Address of first bytey inwordAddresses of successivewords differ by 4 (32-bit)or 8 (64-bit)Addr 0000?Addr 0000?Addr 0004?Addr 0008?Addr 0012?Addr 0008?Bytes 0110012001300140015

Data Representations Sizes of C Objects (in Bytes)¾C Data Type Typical 32-bit unsigned4 int4 long int4 char1 short2 float4 double8 char *4 Or any other pointerIntel IA3244412484x86-6444412488

Byte Ordering How should bytes within multi-byte word beordered in memory?Conventions¾¾Big Endian: Sun, PPC Mac LeastL t significanti ifit byteb t hash highesthi h t addressddLittle Endian: x86 Least significant byte has lowest address

Byte Ordering Example Big Endian¾ Little Endian¾ Least significant byte has highest addressLeast significant byte has lowest addressExample¾¾Variable x has 4-byte representation 0x01234567Address given by &x is 0x100Big Endian0x100 0x101 0x102 0x10301Little Endian2345670x100 0x101 0x102 0x10367452301