Jump to content

Efficient muldiv() and scale() functions for 2000 series

Recommended Posts

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
;   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                                         ;
Link to post
Share on other sites

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().

Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

  • Create New...