INTRODUCTION TO COMPUTING
INTRODUCTION TO COMPUTING BME 303
Popular in Course
Popular in Biomedical Engineering
verified elite notetaker
This 52 page Class Notes was uploaded by Karianne Harber on Sunday September 6, 2015. The Class Notes belongs to BME 303 at University of Texas at Austin taught by Orly Alter in Fall. Since its upload, it has received 20 views. For similar materials see /class/181683/bme-303-university-of-texas-at-austin in Biomedical Engineering at University of Texas at Austin.
Reviews for INTRODUCTION TO COMPUTING
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/06/15
BMESOS Intro to Computing Subroutines A subroutine is a program fragment that lives in user space performs a welldefined task is invoked called by another user program returns control to the calling 7 r0 ram when finished Like a service routine but not part of the OS not concerned with protecting hardware resources no special privilege required Reasons for subroutines reuse useful and debugged code without having to keep typing it in divide task among multiple programmers use vendorsupplied library of useful routines THE UNIVEMII39Y OI TLXAS AT AUSTIN BME303 Intro to Computing JSR Instruction 9 8 7 6 5 PCOffsetll l5 14 13 12 ll 10 4 3 2 l O JSR o 1 o 0I1I Jumps to a location like a branch but unconditional and saves current PC addr of next instruction in R7 saving the return address is called linking target address is PCrelative PC SextR100 bit 11 specifies addressing mode if1 PCrelative target address PC SextlR100 if 0 register target address contents of register IR86 THE UNIVERSITY OF TEXAS AT AUSTIN BME303 Intro to Computing JSR Register File PC SGXt 1 R10O Instruction Reg NOTE PC has already been incremented during instruction fetch stage THE UNIVERSITY OF TEXAS AT AUSTIN BME303 Intro to Computing JSRR nstructi0 1514131211109 8 7 6543210 JSRRIo 1 0 0IOI0 0H BaseIo 0 0 0 0 0 Just like JS except negister addressing mode target address is Base Register bit 11 specifies addressing mode What important feature does JSRR provide that JS does not THE UNIVERSITY OF TEXAS AT AUSTIN BME303 Intro to Computing JSRR Register File PC NOTE PC has already been incremented during instruction fetch stage THE UNIVERSITY OF TEXAS AT AUSTIN BMESOS Intro to Computing Returning from a Subroutine RET JMP R7 gets us back to the calling routine just like inside TRAP THE UNIVERSITY OF TLXAS AT AUSTIN BME303 Intro to Computing JSRJSRR Jump to Suhrnutine JSRR Assembler Formats JSR LABEL 5 58 What Is the memory range Encoding mu JSRR JSRR mu Does it remember previous PC Operatian Rum 1r mum 1 Ease pa sm IPCaffsetJJI Descriptiun n i is saved in R7 39 39 39 39 mutiue Then Ihe PC is loaded with me address of he isIniclion u the srdirmnine causing an II condiridndi jump In dim address The nddiess of the submuIine is obtained tom the base registei if bit I I 39 me address is Compule by signrleending nus mum and adding mis value Io Ihe incremented PCifbiI ii is I Examples JSR QUEUE Put the address u he instruction following JSR imo R7 Jump to QUEUE JSRR RX Put me address ioiiomng JSRR imo R7 Jump In me address contained in R3 THE UNIVERSITY OF TEXAS AT AUSTIN BMESOS Intro to Computing Summary of LC3 Jump Instructions Mnemonics Opcode PC 9 R7 Addressmg Mode JSR 0100 YES Direct JMP 0100 NO Base offset JSRR 1100 YES Base offset THE UNIVERSII39Y OI TLXAS AT AUSTIN BMESOS Intro to Computing Example Negate the value in To call a subroutine from a program Within 1024 instructions need to compute R4 R1 R3 R0 R3 0 copyR3toR0 JSR donComp negate ADD R4 R1 R0 addtoR1 donComp NOT R0 R0 iphits ADD R0 R0 1 addone RET return to caller Note Caller should save R0 if we ll need it later THE UNIVERSII39Y 0 TLXAS AT AUSTIN PassiFi39Emliriftf rii ibtion tofrom Subroutines Arguments A value passed in to a subroutine is called an argument This is a value needed by the subroutine to do its job Examples In 2sCom routine R0 is the numberto be negated In OUT service routine R0 is the characterto be printed In PUTS routine R0 is address of string to be printed Return Values A value passed out of a subroutine is called a return value This is the value that you called the subroutine to compute Examples In 2sCom routine nerated value is returned in R0 In GETC service routine character read from the keyboard is returned in R0 THE UNIVEMII39Y OI TLXAS AT AUSTIN BMESOS Intro to Computing Using Subroutines In order to use a subroutine a programmer mm know its address or a label that will be bound to its address its function what does it do NOTE The programmer does not need to know Mthe subroutine works but what changes are visible in the machine s state afterthe routine has run its arguments where to pass data in if any its return values where to get computed data if any THE UNIVERSITY OF TLXAS AT AUSTIN BME303 Intro to Computing Saving and Restore Registers Since subroutines are just like service routines we also need to save and resw v egwww f new Generally use calleesave strategy except for return values Save anything that the subroutine will alter internally that shouldn t be visible when the subroutine returns It s good practice to restore incoming arguments to their original values unless overwritten by return value Remember You MUST save R7 if you call any other subroutine or service routine TRAP Otherwise you won t be able to return to caller THE UNIVERSII39Y OI TLXAS AI39 AUSTIN BMESOS Intro to Computing Example 1 Write a subroutine FirstChar to find the E occurrence of a particular character in R0 in a string pointed to by R1 return pointer to character or to end of string NULL in R2 2 Use FirstChar to write CountChar which counts the number of occurrences of a particular character in R0 in a string pointed to by R1 return count in R2 Can write the second subroutine rst without knowing the implementation of FirstChar THE UNIVEMII39Y 0 TLXAS AT AUSTIN BMESOS Intro to Computing CountChar Algorithm using F I R1ltR21 save regs call FirstChar R3 lt MR2 save R7 since we re using JSR restore regs THE UNIVERSII39Y 0 TLXAS AT AUSTIN BMESOS Intro to Computing CountChar Implementation CountChar subroutine to count occurrences of a char CountChar ST R3 CCR3 save registers ST R4 CCR4 ST R7 CCR7 JSR alters R7 ST R1 CCRl save original string ptr initialize count to zero find next occurrence ptr in R2 see if char or null AND R4 R4 0 CCl JSR FirstChar LDR R3 R2 0 BRz CC2 ifnull no more chars ADD R4 R4 1 increment count ADD R1 R2 1 point to next char in string Banp CCl CC2 ADD R2 R4 O move return val count to R2 LD R3 CCR3 restore regs LD R4 CCR4 LD R1 CCRl LD R7 CCR7 RET and return THE UNIVERSII39Y 0 TLXAS AT AUSTIN BMESOS Intro to Computing FirstChar Algorithm return THE UNIVERSII39Y 0 TLXAS AT AUSTIN R1 is the pointer to string R3 The char retn39eved R0 the char to be counted BMESOS Intro to Computing FirstChar Implementation FirstChar subroutine to nd rst occurrence of a char FirstChar ST R3 FCR3 save registers ST R4 FCR4 save original char NOT R4 R0 negate R0 for comparisons ADD R4 R4 1 ADD R2 R1 0 initialize ptr to beginning of s rmg FCl LDR R3 R2 0 readcharacter BRz FCZ if null we39re done ADD R3 R3 R4 see if matches input char BRz FCZ if yes we39re done ADD R2 R2 1 increment pointer Banchl FCZ LD R3 FCR3 LD R4 FCR4 RET and return restore registers THE UNIVERSII39Y 0 TLXAS AT AUSTIN BMESOS Intro to Computing TRAP vs Subroutine JSR TRAP hardware control part of OS all users affected devree of rivile39es JSR written by the users or part ofthe library all users are not affected THE UNIVERSITY OF TEXAS AT AUSTIN BMESOS Intro to Computing Use of Subroutines Examples lt replaces a program fragment that s employed repeatedly within a given user or 08 program It is a program that realizes a function employed by many programs eg common arithmetic functions in a Math Library THE UNIVERSII39Y 0 TLXAS AT AUSTIN BMESOS Intro to Computing Library Routines Vendor may provide object les containing useful subroutines don t want to provide source code intellectual property assemblerlinker must support EXTERNAL symbols or starting address of routine must be supplied to user EXTERNAL SQRT LD R2 SQAddr load SQRTaddr JSRR R2 SQAddr SQRT Using JSR because no wn t know whether SQRT is within 1024 instructions THE UNIVEMII39Y 0 TLXAS AT AUSTIN BMESOS Intro to Computing Library Routines These are programs that are frequently employed by many users and may be part ofthe operating system However as distinguished from OS service routines library programs do not directly access privileged hardware resources eg lO device registers Examples Routines in a Math Library such as SQRT DIV MULT Problem determine length ofthe hypotenuse c of a right triangle given the lengths of its other two sides ab c2 a2 b2 or c SQRT SQUAREa SQUAREb SQRT call outside library SQUARE within the program THE UNlVERblI39Y 0 TLXAS AT AUSTIN BMESOS Intro to Computing Main Program ORIG 0X3000 LD R0 Side1 JSR SQUARE ADD R1 R0 0 LD R0 Side2 JSR SQUARE ADD R0 R0 R1 0T R0 Hypot HALT BLKW1 3 BLKW 1 4 BLKW 1 END R0 6 Side1 R0 6 R02 R1 6 Side12 w 6 Side2 R0 6 R02 R0 6 Side12 Side22 R0 6 SQRTR0 store result THE UNIVERSITY OF TEXAS AT AUSTIN BMESOS Intro to Computing SQUAR Subroutine The following subroutine s luares a I ositive integer N by adding a to itself N 1 times Squares the value in R0 a positive 20 integer Returns result to R0 Also uses GPRs R2 R3 without saverestore SQUARE ADD R2 R0 0 counter 6 n ADD R3 R0 0 tmp 6 n AGAIN ADD R2 R2 4 decrement counter BRZ DONE ADD R0 R0 R3 accumulate Banp AGAIN DONE RET R0 n2 THE UNIVERSITY OF TLXAS AT AUSTIN BME303 Intro to Computing SQRT HE UNIVERSITY OF TEXAS AT AUSTIN BMESOS Intro to Computing SQRT Question f need to com ute s uare roots but don t know anything about NewtonRaphson what do I do Answer Call on the SQRT routine in the Math Library Knowledge required by the user then reduces to knowing where to put the argument K and where to nd the result SQRTK THE UNIVERSII39Y 0 TLXAS AT AUSTIN BMESOS Intro to Computing ORIG 0x3000 39 EXTERNAL SQRT LD R0 Side1 JS SQUARE ADD R1 R0 0 LD R0 Side2 JSR SQUARE ADD R0 R0 R1 LD R4 BASE JSRR ST R0 Hypot HALT L SQRT BLKW1 3 BLKW1 4 BLKW1 END Solution R0 6 Side1 R0 6 R02 R1 6 Side12 R0 6 Side2 39 R0 2 0 6 Side12 7 Side22 i R 5 R016 SQRT R0 W yJSRR soreresu THE UNIVERSITY OF TEXAS AT AUSTIN BME303 Intro to Computing IQ Stacks chapter 10 Pas THE UNIVERSITY OF TEXAS AT AUSTIN BMESOS Intro to Computing Stack A stack is an abstract data type where the last data put in the stack is the rst data that comes out of the stack This is referred to as the LIFO Last In First Out property A write insertion operation is referred to as a push A read removal operation is reerred w as a pop THE UNIVERSITY OF TLXAS AT AUSTIN BMESOS Intro to Computing The Stack physio vreon Coin storage in an automobile armrest Initial State After After Three After One Push More Pushes One Pop First quarter out is the last quarter in Key characteristic Last In First Out LIFO THE UNIVERSII39Y 0 TLXAS AT AUSTIN BMESOS Intro to Computing Applications of Stack Stack cw upport a variety of useful tasks such as reversing strings matching parentheses brackets braces convertin from in x to post x notation evaluating arithmetic expressions Generally they are useful when im lementin39 recursive functions THE UNIVERSII39Y 0 TLXAS AT AUSTIN BMESOS Intro to Computing Arithmetic Using a Stack lnstead of registers some lSA39s use a stack for source and destination operations a zeroaddress machine Example ADD instruction pops two numbers from the stack adds them and pushes the result to the stack Evaluating ABCD using a stack 1 push A 2 PUSh B Why use a stack 3 A58 C Limited registers 539 bush D Convenient calling convention 6 ADD for subroutines 7 MULTIPLY Algorithm naturally expressed 8 pop result using FIFO data structure THE UNlVERblI39Y 0 TLXAS AT AUSTIN BMESOS Intro to Computing Implementatw urdware A hardware stack consists of a fixed number of registers which via commands from a control unit having push and pop inputs can pass their contents to and from neighboring registers Hence a hardware stack behaves in a manner similar to the coin holder example ie the register contents move in response to pushpop commands THE UNIVEMII39Y 0 TLXAS AT AUSTIN BMESOS Intro to Computing Implementat rdware Empty Initial state After 1 push After 3 pushes After 2 pops The elements already on the stack move THE UNIVERSII39Y 0 TLXAS AT AUSTIN BMESOS Intro to Computing Implementation SoftwareMemory This a much more common way to implement a stack in a computer It consists of a sequence of memory locations together with a stack pointer Le a general purpose register whose contents point to the top of the stack Data already stored does not mov THE UNIVEMII39Y 0 TLXAS AT AUSTIN BMESOS Intro to Computing Implementation SoftwareMemory Memoryimplemented stack 5 entries initial BASE location x4000 stack pointer R6 X3FFB X3FFB X3FFC X3FFC X3FFD X3FFD X3FFE X3FFE X3FFF X3FFF R6 R6 Initial state After 1 push After 3 pushes After 2 pops THE UNIVERSII39Y OI TLXAS AT AUSTIN BMESOS Intro to Computing PUSH R6 stack pointer R0 value to be pushed PUSH ADD R6 R6 1 decrement stack pointer STR R0 R6 0 store R0 in memor Initial state Final state THE UNIVERSer 0 TLXAS AT AUSTIN BMESOS Intro to Computing POP R6 stack pointer R0 popped value POP LDR R0 R6 0 load value into R0 ADD R6 R6 1 increment stack ointer Initial state Final state X3FFB X3FFB X3FFC X3FFC X3FFD X3FFD X3FFE X3FFE X3FFF X3FFF R0 R0 R6 R6 THE UNIVERSer 0 TLXAS AT AUSTIN BMESOS Intro to Computing Underflow and Overflow There are two situations for which a failure can occur using PUSH and POP operations Underflow A POP is attempted when the stack is em t the stack ointer oints to BASE 1 Overflow A PUSH is attempted when the stack is full the stack pointer points to the last memory location Hence let s try to embellish these operations so that such failures errors can be detected In a hardware stacK this would be achieved Via a sigBal on an output line from the stack control unI THE UNIVEMII39Y OI TLXAS AT AUSTIN BMESOS Intro to Computing Underflow Initial After1 o After2 o s X3FFB X3FFB X3FFB X3FFC X3FFC X3FFC X3FFD stack X3FFD X3FFD pointer X3FFE lt X3FFE X3FFE X3FFF X3FFF X3FFF 5 3 pointer THE UNIVERSer 0 TLXAS AT AUSTIN BMESOS Intro to Computing Overflow X3FFB X3FFC X3FFD X3FFE X3FFF stack Initial After 2 pushes pointer 4 suck X3FFB X3FFB 39 t 3FFC X3FFC THE UNIVERSer 0 TLXAS AT AUSTIN BMESOS Intro to Computing Testing for Underflow Assuming BASE x4000 stack pointer R6 and data register R0 under ow can be detected using the following POP subroutine POP LD R1 EMPTY Check if stack is empty ADD R2 R6 R1 BRz Failure YES Underflow LDR R0 R6 0 POP EMPTY FILL XCOOO 2 s complement of x4000 BASE Failure informs caller that under ow occurred THE UNIVEMII39Y 0 TLXAS AT AUSTIN BMESOS Intro to Computing Testing for Overflow Assuming a stack with 5 locations other assumptions are the same over ow can be detected using the following PUSH subroutine PUSH LD R1 MAX Check if stack is full ADD R2 R6 R1 BRz Failure YES overflow ADD R6 R6 1 PUSH STR R0 R6 0 RET MAX FILL XCOOS 2 s complement of X3FFB MAX Failure informs caller that over ow occurred THE UNIVERSII39Y 0 TLXAS AT AUSTIN BMESOS Intro to Computing Failure Report A failure to either POP or PUSH a value due to an empty or full stack respectively can be indicated by a value placed in an agreedupon register For example suppose R5 is used for this purpose where R5 1 Failure R5 O No failure Then the caller can determine whether a failure occurred by checking R5 after a return from POP or PUSH THE UNIVEMII39Y 0 TLXAS AT AUSTIN BME303 Intro to Computing POP Flowchart How does the PUSH routine owchart differ THE UNIVERSITY OF TEXAS AT AUSTIN BME303 Intro to Computing PUSH Flowchart PUSH 6 R0 THE UNIVERSITY OF TEXAS AT AUSTIN BMESOS Intro to Computing POP Subroutine with Failure Report POP LD R1 EMPTY ADD R2 R6 R1 BRz Failure LDR R0 R6 0 ADD R6 R6 1 AND R5 R5 0 R5 6 x0000 RET no underflow Failure AND R5R50 R5 6 x0001 R5R51 underflow 3BET39539 EMPTY FiLL xCOOO 0x4000 here does this return to THE UNIVERSITY OF TEXAS AT AUSTIN BMESOS Intro to Computing PUSH Subroutine with Failure Report PUSH Failure MAX LD ADD BRz ADD STR AND RET AND ADD RET FILL R1 MAX R2 R6 R1 Failure R6 R6 1 R0 R6 0 R5 R5 0 R5 GXOOOO no ovder ow R5 6 x0001 overflow R5R50 R5R51 X0005 THE UNIVERSITY OF TEXAS AT AUSTIN BMESOS Intro to Computing Interpretation of Failures POP the term failure is somewhat misleading since underflow can often serve as a meaningful end condition for some task that s been using the stack PUSH failure overflow means that the stack s capacity has been exhausted something which usually implies big trouble THE UNIVEMII39Y 0 TLXAS AT AUSTIN BMESOS Intro to Computing Calling These Subroutines The POP and PUSH subroutines permit us to use speci ed locations x3FFB x3FFF as a stack u n 5 entries If the calling program wants to push a value onto the stack it loads that value into R0 and then executes JSR PUSH Similarly to pop a value from the stack into R0 it executes the instruction JSR POP lfwe want to modify the location or size ofthe stack the values of BASE and MAX can be adjusted accordingly THE UNIVERSII39Y 0 TLXAS AT AUSTIN BMESOS Intro to Computing SaveRestore Responsibilities Since the subroutines POP and PUSH use GPRs R1 R2 and R5 they had best be savedrestored by either the caller or the callee For R1 and R2 it is better to have them savedrestored by the POP and PUSH subroutines that use them calleesave However the caller should saverestore R5 before a POP or PUSH if it s using R5 for other purposes caller save A calleesave in this instance makes no sense since R5 reports failure Information back to the caller THE UNIVERSII39Y 0 TLXAS AT AUSTIN Putting It All Together subroutines for carrying out the PUSH and 303 functions This program works with a stack consisting of memory 1ocations x4000 use through x4004 MAX 36 is the stack pointer POP ST R2Save2 39 are needed by POP 51 31save1 LD R1BASE 39 BASE contains x4000 ADD 313139 1 31 contains x3E 3 ADD 323631 Compare stack pointer to x3E E E 332 failex1t Branch if stack is emp 103 3036390 The actua1 quotpopquot ADD 3636391 Adjust stack pointer Banp success exit PUSH s39r 32save3 save registers that ST R1Save1 are needed by USH LD tains 4004 ADD 323631 Compare stack pointer to x4004 1332 failexit Branch if stack is full ADD 363639 1 Adjust tack pointer TR 3036390 The actua1 quotpush u successexit LD 31save1 3estore origina1 LD 32save2 register va1ues Ann 3535390 35 REIT failexit LD 31save1 3estore origina1 LD 32save2 register va1ues Ann 3535390 ADD 3535391 35 lt failure REIT BASE FILL xCOOl 39 BASE contains x4000 MAX FILL xCOOS save1 1111 x0000 Save2 E ILL x0000 BMESOS Intro to Computing Example OpAdd POP two values ADD then PUSH result STA RT Put back rst Put back both PUSH J J RETURN THE UNIVERSer 0 TLXAS AT AUSTIN
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'