Introduction to Computer EngineeringChapter 6 ProgrammingSolving Problems using a ComputerStepwise RefinementProblem StatementThree Basic ConstructsSequentialConditionalIterativeProblem Solving SkillsLC-3 Control InstructionsCode for ConditionalCode for IterationExample: Counting CharactersRefining BRefining B1Refining B2 and B3The Last Step: LC-3 InstructionsDebuggingDebugging OperationsLC-3 SimulatorTypes of ErrorsTracing the ProgramExample 1: MultiplyDebugging the Multiply ProgramExample 2: Summing an Array of NumbersDebugging the Summing ProgramExample 3: Looking for a 5Debugging the Fives ProgramExample 4: Finding First 1 in a WordDebugging the First-One ProgramDebugging: Lessons LearnedIntroduction to Computer EngineeringCS/ECE 252, Spring 2008Prof. David A. WoodComputer Sciences DepartmentUniversity of Wisconsin – MadisonChapter 6Programming6-3Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Solving Problems using a ComputerMethodologies for creating computer programsthat perform a desired function.Problem Solving•How do we figure out what to tell the computer to do?•Convert problem statement into algorithm,using stepwise refinement.•Convert algorithm into LC-3 machine instructions.Debugging•How do we figure out why it didn’t work?•Examining registers and memory, setting breakpoints, etc.Time spent on the first can reduce time spent on the second!6-4Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Stepwise RefinementAlso known as systematic decomposition.Start with problem statement: “We wish to count the number of occurrences of a characterin a file. The character in question is to be input fromthe keyboard; the result is to be displayed on the monitor.”Decompose task into a few simpler subtasks.Decompose each subtask into smaller subtasks,and these into even smaller subtasks, etc....until you get to the machine instruction level.6-5Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Problem StatementBecause problem statements are written in English,they are sometimes ambiguous and/or incomplete.•Where is “file” located? How big is it, or how do I knowwhen I’ve reached the end?•How should final count be printed? A decimal number?•If the character is a letter, should I count bothupper-case and lower-case occurrences?How do you resolve these issues?•Ask the person who wants the problem solved, or•Make a decision and document it.6-6Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Three Basic ConstructsThere are three basic ways to decompose a task:TaskSubtask 1Subtask 2Subtask 1 Subtask 2TestconditionSubtaskTestconditionSequential Conditional IterativeTrueTrueFalseFalse6-7Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.SequentialDo Subtask 1 to completion,then do Subtask 2 to completion, etc.Get characterinput fromkeyboardExamine file andcount the numberof characters thatmatchPrint numberto the screenCount and print theoccurrences of acharacter in a file6-8Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.ConditionalIf condition is true, do Subtask 1;else, do Subtask 2.Test character.If match, incrementcounter.Count = Count + 1file char= input?True False6-9Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.IterativeDo Subtask over and over, as long as the test condition is true.Check each element ofthe file and count thecharacters that match.Check next char andcount if matches.more charsto check?TrueFalse6-10Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Problem Solving SkillsLearn to convert problem statementinto step-by-step description of subtasks.•Like a puzzle, or a “word problem” from grammar school math.What is the starting state of the system?What is the desired ending state?How do we move from one state to another?•Recognize English words that correlate to three basic constructs:“do A then do B”  sequential“if G, then do H”  conditional“for each X, do Y”  iterative“do Z until W”  iterative6-11Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.LC-3 Control InstructionsHow do we use LC-3 instructions to encodethe three basic constructs?Sequential•Instructions naturally flow from one to the next,so no special instruction needed to gofrom one sequential subtask to the next.Conditional and Iterative•Create code that converts condition into N, Z, or P.Example:Condition: “Is R0 = R1?”Code: Subtract R1 from R0; if equal, Z bit will be set.•Then use BR instruction to transfer control to the proper subtask.6-12Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Code for ConditionalGenerateConditionInstructionA0000BSubtask 1CSubtask 2N extSubtaskD? C0000 111 DSubtask 1TestC onditionTrue FalseSubtask 2NextSubtaskExact bits dependon conditionbeing testedPC offset toaddress CPC offset toaddress DUnconditional branchto Next SubtaskAssuming all addresses are close enough that PC-relative branch can be used.6-13Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Code for IterationGenerateConditionInstructionA0000BSubtaskCN extSubtask? C0000 111 ASubtaskTestC onditionTrueFalseNextSubtaskExact bits dependon conditionbeing testedPC offset toaddress CPC offset toaddress AUnconditional branchto retest conditionAssuming all addresses are on the same page.6-14Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Example: Counting CharactersInput a character. Thenscan a file, countingoccurrences of thatcharacter. Finally, displayon the monitor the numberof occurrences of thecharacter (up to 9).STARTSTOPInitialize: Put initial valuesinto all locations that will beneeded to carry out thistask.- Input a character.- Set up a pointer to the firstlocation of the file that willbe scanned.- Get the first character fromthe file.- Zero the register that holdsthe count.STARTSTOPScan the file, location bylocation, incrementing thecounter if the charactermatches.Display the count on themonitor.ABCInitial refinement: Big task intothree sequential subtasks.6-15Copyright © The