oPossum 1,083 Posted March 2, 2013 Share Posted March 2, 2013 One of the limitations of the C language is that multiplication truncates the result to match the size of the multiplicands. So if you multiply two 16 bit numbers, the result is limited to 16 bits despite 32 bits being needed to represent all possible results. The fix for this is to cast one of the multiplicands to a larger type. Unfortunately this results in the use of a multiply library routine that is larger and slower than necessary. Division has a similar problem - the quotient, dividend, and divisor are all the same size. The way I fix these limitations is to write assembly code that is compact, efficient, and well suited to specific tasks. The muldiv() function provided here will take 16 bit unsigned values and do a multiply to a 32 bit intermediate result and then divide back down to 16 bits. It makes some simple tests on the arguments to optimize the code path. One specific case where this muldiv() function is useful is scaling one range of values to another. For example taking the 0 to 1023 range of a 10 bit ADC and scaling to some actual unit of measure. A helper function function can be used to allow clearly written code... uint16_t muldiv_u16(uint16_t a, uint16_t b, uint16_t c); inline uint16_t scale_u16(uint16_t in, uint16_t in_low, uint16_t in_high, uint16_t out_low, uint16_t out_high) { // For guaranteed correct results: // in_low <= in <= in_high // in_low < in_high // out_low < out_high // return out_low + muldiv_u16(in - in_low, out_high - out_low + 1, in_high - in_low + 1); } Sample usage... // Read 10 bit ADC value - range of 0 to 1023 const uint16_t adc = readADC(); // ADC reference votlage is 2.5V, so convert to a range of 0 to 2500 mV const uint16_t mv = scale_u16(adc, 0, 1023, 0, 2500); Note that there are constraints on the values passed to the function. All are unsinged 16 bit integers, and must fall withing the constraints to ensure a correct return value. Signed integers can also be used because the constraints will result in unsigned values being passed to the muldiv() function... inline int16_t scale_i16(int16_t in, int16_t in_low, int16_t in_high, int16_t out_low, int16_t out_high) { // For guaranteed correct results: // in_low <= in <= in_high // in_low < in_high // out_low < out_high // return out_low + muldiv_u16(in - in_low, out_high - out_low + 1, in_high - in_low + 1); } The in_low <= in constraint can easily be removed if needed... int16_t scale_i16x(int16_t in, int16_t in_low, int16_t in_high, int16_t out_low, int16_t out_high) { // For guaranteed correct results: // in_low < in_high // out_low < out_high // -32768 <= return <= 32767 // return (in < in_low) ? out_low - muldiv_u16(in_low - in, out_high - out_low + 1, in_high - in_low + 1) : out_low + muldiv_u16(in - in_low, out_high - out_low + 1, in_high - in_low + 1); } The other constraints could be reduced or eliminated using C++ templates. (exercise for the user) ; ; Copyright (C) 2013 Kevin Timmerman ; ; This program is free software: you can redistribute it and/or modify ; it under the terms of the GNU General Public License as published by ; the Free Software Foundation, either version 3 of the License, or ; (at your option) any later version. ; ; This program is distributed in the hope that it will be useful, ; but WITHOUT ANY WARRANTY; without even the implied warranty of ; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the ; GNU General Public License for more details. ; ; You should have received a copy of the GNU General Public License ; along with this program. If not, see <http://www.gnu.org/licenses/>. ; .cdecls C, LIST, "msp430.h" ; ; .text ; ; ; return a * b / c .def muldiv_u16 ; uint16_t muldiv_u16(uint16_t a, uint16_t b, uint16_t c) .def muldiv_u8 ; uint8_t muldiv_u8(uint8_t a, uint8_t b, uint8_t c) ; ; muldiv_u16: ; ; --- Multiply --- push R10 ; Accumulator MSW push R11 ; Accumulator LSW ; R12 a ; R13 b ; R14 c ; R15 b shift register LSW ; clr R11 ; Clear accumulator LSW mov R12, R10 ; Copy a to accumulator MSW ; (assume multiply by zero) tst R13 ; Multiply by zero? jeq div16 ; Yes, skip multiply... cmp R12, R13 ; Make R12 smaller than R13 to jhs no_swap16 ; do multiply as quickly as possible xor R12, R13 ; xor R13, R12 ; xor R12, R13 ; no_swap16: ; clr R10 ; Clear accumulator MSW clr R15 ; Clear MSW of b shift clrc ; jmp mul16_begin ; mul16_add: ; add R13, R11 ; Add b to accumulator addc R15, R10 ; mul16_shift: ; rla R13 ; Shift b rlc R15 ; mul16_begin: ; rrc R12 ; Shift a, test lsb jc mul16_add ; lsb is 1, add b... jne mul16_shift ; lsb is 0, but more 1 bits remain... ; ; --- Divide --- ; R13/R10/R11 Dividend / Quotient shift register ; R14 Divisor ; R15 Bit count div16: ; mov R10, R12 ; Copy MSW of accumulator to result ; (assume divide by zero) tst R14 ; Divide by zero? jz div16_exit ; Yes, all done... mov #1, R15 ; 16 bit quotient div16_shift: ; R10 <- R11 rla R11 ; Shift rlc R10 ; ; Greater than or equal to divisor? jc div16_sub ; Yes... cmp R14, R10 ; jlo div16_next ; No... div16_sub: ; sub R14, R10 ; Yes, subtract bis #1, R11 ; Set bit in result div16_next: ; rla R15 ; Dec bit count jne div16_shift ; Next bit... mov R11, R12 ; Return result in R12 div16_exit: ; pop R11 ; pop R10 ; ret ; NatureTM, Rickta59, xpg and 2 others 5 Quote Link to post Share on other sites
oPossum 1,083 Posted March 3, 2013 Author Share Posted March 3, 2013 First post updated with improved assembly code. Forgot to mention that the when 0 is passed to the second or third argument of muldiv() it is interpreted as 2^16 (65536, 0x10000). This allows the full 16 bit range to be used as in and/or out ranges with scale(). Quote Link to post Share on other sites
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.