0
\$\begingroup\$

I recently learned about using fixed point arithmetic on embedded systems without floating point hardware, so I decided to code it. I tried to write in good style, but emphasized speed over style.

One hard problem I encountered was to convert the number to a string. I coded up the following in my internal class; the macros aren't leaked to the user. The intent of using macros is so that I could easily make a new function for a data-type of uint32_t, uint16_t, and so on, but also have different length of the fractional bits.

Unfortunately, my algorithm requires a larger data-type to actually compute the fractional representation, so it's not trivial to make a fractional type for say uint64_t, as there are no larger types. Also, it fails on signed integers. How is the snprint function?

#define FIXMATH_INTERNAL_DIGIT_TO_CHAR(x)\
  (x) == 0 ? (char) '0'\
: (x) == 1 ? (char) '1'\
: (x) == 2 ? (char) '2'\
: (x) == 3 ? (char) '3'\
: (x) == 4 ? (char) '4'\
: (x) == 5 ? (char) '5'\
: (x) == 6 ? (char) '6'\
: (x) == 7 ? (char) '7'\
: (x) == 8 ? (char) '8'\
:/*(x)==9*/  (char) '9'

// We convert the fixed point number type to a string via the following algorithm:
// Let fixed = w.f
// Output the integer `w` to the string, then append '.'
// Now we need to convert `f` to a string. `f` is a binary decimal, so note the following:
// 2**-1 = 0.5
// 2**-2 = 0.25
// 2**-3 = 0.125
// 2**-4 = 0.0625
// Basically, we get increasing powers of 5 on the right. This is true because we operate
// in base 10. So to convert `f` to a string:
//
// powerOf5 = 1; acc = 0;
// for (bit b : f) {  // starting from the left
//     powerOf5 *= 5; // advance power of 5 so we start at 0.5
//     acc *= 10; // Notice that the decimal place needs to shift as we multiply by powers of 5
//     if (b) acc += powerOf5;
// }
//
// Now `acc` contains an integer representation of the string we want. Add this to our
// output string. However *remember leading 0s.*
#define FIXMATH_INTERNAL_DEF_SNPRINT(/* The type of fixed-point we are dealing with      */ FIX_T,\
                                     /* A printf specifier that handles the data type    */ PRTYPE,\
                                     /* The storage type for FIX_T. PRTYPE matches this  */ STORAGE_T,\
                                     /* A bigger storage type that holds >= 5**bitlen(f) */SUPER_STORAGE_T,\
                                     /* The width of STORAGE_T. w + F, where we have w.f */ N,\
                                     /* The width of the fractional part of the number   */ F)\
void cutils_fixmath_internal_ ## FIX_T ## _snprint(const FIX_T *self, const size_t n, char *writeTo) {\
    STORAGE_T wholeParts = self->data >> F;            /* `w` where the fix_t is of the form w.f */\
    STORAGE_T fracParts = self->data & ((1 << F) - 1); /* `f` where the fix_t is of the form w.f */\
    char wholeString[N - F + 1]; /* Stores the whole part of the number w.f */ \
    size_t numWholeChars = sprintf(wholeString, "%" PRTYPE ".", wholeParts);\
    SUPER_STORAGE_T powerOf5 = 1;\
    SUPER_STORAGE_T acc = 0;\
    for (size_t i = 0; i < F; i++) {\
        powerOf5 *= 5;\
        acc *= 10;\
        if (fracParts & (1 << (F - i - 1))) {\
            acc += powerOf5;\
        }\
    }\
    /* At this point, note that `acc` stores an integer representation of the fractional string. */\
    char fracString[F + 1]; /* Always output at least M decimal places, +1 for the '\0' */\
    memset(fracString, '0', F); /* Account for leading 0s! */\
    fracString[F] = '\0';\
    size_t fracStringIndex = F - 1; /* Where do we store the next digit? */\
    while (acc > 0) { /* Iterate from the rightmost digit to the leftmost; more efficient */\
        fracString[fracStringIndex] = FIXMATH_INTERNAL_DIGIT_TO_CHAR(acc % 10);\
        acc /= 10;\
        fracStringIndex--;\
    }\
    strncpy(writeTo, wholeString, n); /* Copy our 'w.' string to the output */\
    strncpy(writeTo + numWholeChars, fracString, n - numWholeChars); /* Append the 'f' string to the output */\
}

Here is an example class:

typedef struct ufix8_f4_t
{
    uint8_t data;
    struct ufix8_f4_t(*add)(const struct ufix8_f4_t *self, const struct ufix8_f4_t *other);
    void             (*addEq)(struct ufix8_f4_t *self, const struct ufix8_f4_t *other);
    struct ufix8_f4_t(*sub)(const struct ufix8_f4_t *self, const struct ufix8_f4_t *other);
    void             (*subEq)(struct ufix8_f4_t *self, const struct ufix8_f4_t *other);
    struct ufix8_f4_t(*mul)(const struct ufix8_f4_t *self, const struct ufix8_f4_t *other);
    void             (*mulEq)(struct ufix8_f4_t *self, const struct ufix8_f4_t *other);
    struct ufix8_f4_t(*div)(const struct ufix8_f4_t *self, const struct ufix8_f4_t *other);
    void             (*divEq)(struct ufix8_f4_t *self, const struct ufix8_f4_t *other);
    void             (*snprint)(const struct ufix8_f4_t *self, const size_t n, char *writeTo);
}          ufix8_f4_t;

I can define the snprint function for this via:

FIXMATH_INTERNAL_DEF_SNPRINT(ufix8_f4_t, PRIu8, uint8_t, uint16_t, 8, 4);

(naturally, I'd need to have to include string.h, inttypes.h, and stdio.h).

This snprint would expand to:

void cutils_fixmath_internal_ufix8_f4_t_snprint(const ufix8_f4_t *self, const size_t n, char *writeTo) {
    uint8_t     wholeParts    = self->data >> 4;
    uint8_t     fracParts     = self->data & ((1 << 4) - 1);
    char        wholeString[8 - 4 + 1];
    size_t      numWholeChars = sprintf(wholeString, "%" "u" ".", wholeParts);
    uint16_t    powerOf5      = 1;
    uint16_t    acc           = 0;
    for (size_t i             = 0; i < 4; i++) {
        powerOf5 *= 5;
        acc *= 10;
        if (fracParts & (1 << (4 - i - 1))) { acc += powerOf5; }
    }
    char        fracString[4 + 1];
    memset(fracString, '0', 4);
    fracString[4] = '\0';
    size_t fracStringIndex = 4 - 1;
    while (acc > 0) {
        fracString[fracStringIndex] =
                (acc % 10) == 0 ? (char) '0' : (acc % 10) == 1 ? (char) '1' : (acc % 10) == 2 ? (char) '2' :
                                                                              (acc % 10) == 3 ? (char) '3' :
                                                                              (acc % 10) == 4 ? (char) '4' :
                                                                              (acc % 10) == 5 ? (char) '5' :
                                                                              (acc % 10) == 6 ? (char) '6' :
                                                                              (acc % 10) == 7 ? (char) '7' :
                                                                              (acc % 10) == 8 ? (char) '8' : (char) '9';
        acc /= 10;
        fracStringIndex--;
    }
    strncpy(writeTo, wholeString, n);
    strncpy(writeTo + numWholeChars, fracString, n - numWholeChars);
};
\$\endgroup\$
6
\$\begingroup\$

A simpler solution

You can print the fractional part of your fixed point number by simply multiplying by 10 and taking the whole part as your next digit. It's just like what you would do with a float. So instead of what you wrote for the fractional part, it would be like this (for 4.4 fixed point):

while (fracParts > 0) {
    fracParts *= 10;
    fracString[fracStringIndex++] = '0' + (fracParts >> 4);
    fracParts &= ((1 << 4) - 1);
}
fracString[fracStringIndex] = '\0';

Converting from digit to character

Your macro FIXMATH_INTERNAL_DIGIT_TO_CHAR is frightening. You can convert from int to char with just '0' + digit.

\$\endgroup\$
  • \$\begingroup\$ Can I rely on '0' + digit being the right digit? I somehow thought that char wasn't guaranteed to be ASCII \$\endgroup\$ – Justin Oct 30 '15 at 14:06
  • 1
    \$\begingroup\$ Just answering my previous question: Although the characters aren't necessarily ASCII, it's guaranteed that '0' through '9' or consecutive \$\endgroup\$ – Justin Oct 30 '15 at 15:07
  • \$\begingroup\$ I find it kind of funny that I didn't figure out the easy solution, but instead found a more mathematically interesting solution. \$\endgroup\$ – Justin Oct 30 '15 at 15:07
  • 1
    \$\begingroup\$ @Justin It happens all the time that we write overly complex code, because we often only see one solution. I think it's because once we head down a certain path, we get tunnel vision and can't see anything else. That's why code reviews are useful, because another person can bring a whole new perspective to the situation. \$\endgroup\$ – JS1 Oct 30 '15 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.