Columbia COMS 1003 - Low-Level C Programming

Unformatted text preview:

GoalsLike Writing EnglishArithmeticSimple benchmarksSimple benchmarksC Arithmetic TriviaArithmetic LessonsBit ManipulationBit-manipulation basicsAdvanced bit manipulationFaking MultiplicationFaking MultiplicationFaking DivisionMulti-way branchesMicroblaze code for if-then-elseMicroblaze code for switch (1)Microblaze code for switch (2)Computing Discrete FunctionsComputing Discrete FunctionsFunction callsCode for foo()Strength ReductionUnoptimized array code (fragment)Unoptimized pointer code (fragment)Optimized array codeOptimized pointer codeHow Rapid is Rapid?Double-checkingFeatures in order of increasing costStorage Classes in CDynamic Storage AllocationDynamic Storage AllocationSimple Dynamic Storage AllocationDynamic Storage AllocationSimple Dynamic Storage AllocationStorage Classes ComparedMemory-Mapped I/OWith the MicroblazeAn exampleHW/SW Communication StylesHW/SW Communication: InterruptsUnix SignalsUART interrupts on the Microblaze UART interupts on the MicroblazeDebugging SkillsThe Edwards Way to DebugThe Xilinx Tool ChainThe .mhs FileThe .mss FileThe .ucf fileLow-Level C ProgrammingProf. Stephen A. [email protected], Summer 2006Low-Level C Programming – p. 1/51GoalsFunction is correctSource code is concise, readable, maintainableTime-critical sections of program run fast enoughObject code is small and efficientBasically, optimize the use of three resources:Execution timeMemoryDevelopment/maintenance timeLow-Level C Programming – p. 2/51Like Writing EnglishYou can say the same thing many different waysand mean the same thing.There are many different ways to say the samething.The same thing may be said different ways.There is more than one way to say it.Many sentences are equivalent.Be succinct.Low-Level C Programming – p. 3/51ArithmeticInteger Arithmetic FastestFloating-point arithmetic in hardware SlowerFloating-point arithmetic in software Very slow+, −×÷sqrt, sin, log, etc.yslowerLow-Level C Programming – p. 4/51Simple benchmarksfor (i = 0 ; i < 10000 ; ++i)/*arithmetic operation*/On my desktop Pentium 4 with good hardwarefloating-point support,Operator Time Operator Time+ (int) 1 + (double) 5*(int) 5*(double) 5/ (int) 12 / (double) 10« (int) 2 sqrt 28sin 48pow 275Low-Level C Programming – p. 5/51Simple benchmarksOn my Zaurus SL 5600, a 400 MHz Intel PXA250Xscale (ARM) processor:Operator Time+ (int) 1 + (double) 140*(int) 1*(double) 110/ (int) 7 / (double) 220« (int) 1 sqrt 500sin 3300pow 820Low-Level C Programming – p. 6/51C Arithmetic TriviaOperations on char, short, int, and longprobably run at the same speed (same ALU).Same for unsigned variantsint or long slower when they exceed machine’sword size.Operations onfloats performed in doubleprecision.float only useful for reducingmemory.Low-Level C Programming – p. 7/51Arithmetic LessonsTry to use integer addition/subtractionAvoid multiplication unless you have hardwareAvoid divisionAvoid floating-point, unless you have hardwareReally avoid math library functionsLow-Level C Programming – p. 8/51Bit ManipulationC has many bit-manipulation operators.& Bit-wise AND| Bit-wise OR^ Bit-wise XOR~ Negate (one’s complement)» Right-shift« Left-shiftPlus assignment versions of each.Low-Level C Programming – p. 9/51Bit-manipulation basicsa |= 0x4; /*Set bit 2*/b &= ˜0x4; /*Clear bit 2*/c &= ˜(1 << 3); /*Clear bit 3*/d ˆ= (1 << 5); /*Toggle bit 5*/e >>= 2; /*Divide e by 4*/Low-Level C Programming – p. 10/51Advanced bit manipulation/*Set b to the rightmost 1 in a*/b = a & (a ˆ (a - 1));/*Set d to the number of 1’s in c*/char c, d;d = (c & 0x55) + ((c & 0xaa) >> 1);d = (d & 0x33) + ((d & 0xcc) >> 2);d = (d & 0x0f) + ((d & 0xf0) >> 4);Low-Level C Programming – p. 11/51Faking MultiplicationAddition, subtraction, and shifting are fast. Cansometimes supplant multiplication.Like floating-point, not all processors have adedicated hardware multiplier.Recall the multiplication algorithm fromelementary school, but think binary:101011× 110110101110101100+1010110001000101111=43 + 43 « 2 + 43 « 3 = 559Low-Level C Programming – p. 12/51Faking MultiplicationEven more clever if you include subtraction:101011× 1110101011010101100+1010110001001011010=43 « 1 + 43 « 2 + 43 « 3= 43 « 4 - 43 « 2= 602Only usefulfor multiplication by a constantfor “simple” multiplicandswhen hardware multiplier not availableLow-Level C Programming – p. 13/51Faking DivisionDivision is a much more complicated algorithmthat generally involves decisions.However, division by a power of two is just a shift:a / 2 = a >> 1a / 4 = a >> 2a / 8 = a >> 3There is no general shift-and-add replacement fordivision, but sometimes you can turn it intomultiplication:a / 1.33333333= a*0.75= a*0.5 + a*0.25= a >> 1 + a >> 2Low-Level C Programming – p. 14/51Multi-way branchesif (a == 1)foo();else if (a == 2)bar();else if (a == 3)baz();else if (a == 4)qux();else if (a == 5)quux();else if (a == 6)corge();switch (a) {case 1:foo(); break;case 2:bar(); break;case 3:baz(); break;case 4:qux(); break;case 5:quux(); break;case 6:corge(); break;}Low-Level C Programming – p. 15/51Microblaze code for if-then-elselwi r3,r19,44 # fetch "a" from stackaddik r18,r0,1 # load constant 1cmp r18,r18,r3 # compare with "a"bnei r18,$L3 # skip if not equalbrlid r15,foo # call foonop # delay slotbri $L4 # branch to end$L3:lwi r3,r19,44 # fetch "a" from stackaddik r18,r0,2 # load constant 2cmp r18,r18,r3 # compare with "a"bnei r18,$L5 # skip if not equalbrlid r15,bar # call barnop # delay slotbri $L4 # branch to end$L5:Low-Level C Programming – p. 16/51Microblaze code for switch (1)addik r3,r22,-1xori r18,r3,5bgei r18,$L0blti r3,$L14 # Skip if less than 1bri $L1$L0:rsubik r18,r3,5blti r18,$L14 # Skip if greater than 6$L1:addk r3,r3,r3 # Multiply by fouraddk r3,r3,r3lwi r3,r3,$L21 # Fetch address from tablebra r3 # Branch to a case label.sdata2$L21: # Branch table.gpword $L15.gpword $L16.gpword $L17.gpword $L18.gpword $L19.gpword $L20Low-Level C Programming – p. 17/51Microblaze code for switch (2).text$L15: # case 1:brlid r15,foonopbri $L14$L16: # case 2:brlid r15,barnopbri $L14$L17: # case 3:brlid r15,baznopbri $L14$L18: # case 4:brlid r15,quxnopbri $L14$L19: # case 5:brlid r15,quuxnopbri $L14Low-Level C Programming – p. 18/51Computing Discrete FunctionsThere are many ways to compute a “random”function of one variable:/*OK, especially for sparse domain*/if (a == 0) x = 0;else if (a == 1) x = 4;else if (a


View Full Document

Columbia COMS 1003 - Low-Level C Programming

Download Low-Level C Programming
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 Low-Level C Programming 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 Low-Level C Programming 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?