GoalsLike Writing EnglishArithmeticSimple benchmarksSimple benchmarksC Arithmetic TriviaArithmetic LessonsBit ManipulationBit-manipulation basicsAdvanced bit manipulationFaking MultiplicationFaking MultiplicationFaking DivisionMulti-way branchesNios code for if-then-elseNios code for switch (1)Nios code for switch (2)Computing Discrete FunctionsComputing Discrete FunctionsFunction callsCode for foo()(unoptimized)Code for foo()(optimized)Strength ReductionUnoptimized array code (fragment)Unoptimized pointer code (fragment)Optimized (--O2)array codeOptimized (--O2)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/OMemory-Mapped I/O Access in CWhat's With the Volatile?Altera I/OHW/SW Communication StylesHW/SW Communication: InterruptsUnix SignalsInterrupts under Altera (1)Interrupts under Altera (2)Debugging SkillsThe Edwards Way to DebugLow-Level C ProgrammingCSEE W4840Prof. Stephen A. EdwardsColumbia UniversitySpring 2007Low-Level C Programming – p. 1/49GoalsFunction 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/49Like 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/49ArithmeticInteger Arithmetic FastestFloating-point arithmetic in hardware SlowerFloating-point arithmetic in software Very slow+, −×÷sqrt, sin, log, etc.yslowerLow-Level C Programming – p. 4/49Simple 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/49Simple 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/49C 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 on floats performed in doubleprecision. float only useful for reducing memory.Low-Level C Programming – p. 7/49Arithmetic 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/49Bit 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/49Bit-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/49Advanced 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/49Faking 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/49Faking 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/49Faking 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/49Multi-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/49Nios code for if-then-elseldw r2, 0(fp) # Fetch a from stackcmpnei r2, r2, 1 # Compare with 1bne r2, zero, .L2 # If not 1, jump to L2call foo # Call foo()br .L3 # branch out.L2:ldw r2, 0(fp) # Fetch a from stack (again!)cmpnei r2, r2, 2 # Compare with 2bne r2, zero, .L4 # If not 1, jump to L4call bar # Call bar()br .L3 # branch out.L4:Low-Level C Programming – p. 16/49Nios code for switch (1)ldw r2, 0(fp) # Fetch acmpgeui r2, r2, 7 # Compare with 7bne r2, zero, .L2 # Branch if greater or equalldw r2, 0(fp) # Fetch amuli r3, r2, 4 # Multiply by 4movhi r2, %hiadj(.L9) # Load address .L9addi r2, r2, %lo(.L9)add r2, r3, r2 # = a*4 + .L9ldw r2, 0(r2) # Fetch from jump tablejmp r2 # Jump to label.section .rodata.align 2.L9:.long .L2 # Branch table.long .L3.long .L4.long .L5.long .L6.long .L7.long .L8Low-Level C Programming – p. 17/49Nios code for switch (2).section .text.L3:call foobr .L2.L4:call barbr .L2.L5:call bazbr .L2.L6:call quxbr .L2.L7:call quuxbr .L2.L8:call corge.L2:Low-Level C Programming – p. 18/49Computing 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 == 2) x = 7;else if (a == 3) x = 2;else if (a == 4) x = 8;else if (a == 5) x = 9;Low-Level C Programming – p. 19/49Computing Discrete
View Full Document
Unlocking...