10
\$\begingroup\$

I am working on the lossy 16 bit representation for 32 bit integers that catches all 32 bit range with precision depending on absolute value.

My idea is to store integer lv = sign(x)*ilog2(x) in first bite, and a tail that approximates the error x - 2^ilog2(x). In order to do that I divide possible error values in 256 bins and store the index of the bin.

To reconstruction of the integer value, I calculate sign(lv) * (2^lv) + bin_size * tail.

I have initial implementation for that, but my code have several problems.

  1. It is not as clear as I'd like to.
  2. short_int32_t(x) should be equal to -short_int32_t(-x) but it is not. I am pretty sure that it is possible to achieve it, but I am not sure how to do it not making code more ugly.
  3. Any performance suggestions welcome.

Look at functions void set(int32_t) and int32_t get():

template <typename T>
int32_t signum(T x) {
    return (T(0) < x) - (x < T(0));
}

inline int8_t signum_log2(int32_t x) {
    int8_t log2 = static_cast<int8_t>(8 * sizeof(int32_t) - __builtin_clz(abs(x)) - 1);
    static_assert(8 * sizeof(int32_t) == __builtin_clz(1) + 1, "log is wrong");
    return log2 * signum(x);
}

inline int8_t abs_log2(int32_t x) {
    static_assert(8 * sizeof(int32_t) == __builtin_clz(1) + 1, "log is wrong");
    return static_cast<int8_t>(8 * sizeof(int32_t) - __builtin_clz(abs(x)) - 1);
}


class short_int32_t {
public:
    short_int32_t(int32_t x) {
        set(x);
    }

    void operator=(int32_t x) {
        set(x);
    }

    bool operator<(short_int32_t x) {
        return m_log == x.m_log ? (signum(m_log) * m_tail < signum(x.m_log) * x.m_tail) : (m_log < x.m_log);
    }

    short_int32_t operator*(short_int32_t x) {
        return short_int32_t(get() * x.get());
    }

    short_int32_t operator+(short_int32_t x) {
        return short_int32_t(get() + x.get());
    }

    short_int32_t operator-(short_int32_t x) {
        return short_int32_t(get() - x.get());
    }

    short_int32_t operator*(int32_t x) {
        return short_int32_t(get() * x);
    }

    short_int32_t operator+(int32_t x) {
        return short_int32_t(get() + x);
    }

    short_int32_t operator-(int32_t x) {
        return short_int32_t(get() - x);
    }


    void set(int32_t x) {
        if (x == 0) {
            m_log = 0;
            m_tail = 0;
            return;
        }

        int8_t abs_log = abs_log2(x);
        int32_t interval = abs_log ? 1 << abs_log : 0;
        if (interval == abs(x)) {
            m_log = x < 0 ? -abs_log : abs_log;
            m_tail = 0;
            return;
        }

        int32_t bin_size = interval < 512 ? 1 : (x < 0 ? (interval >> 9) : (interval >> 8));

        m_log = x > 0 ? abs_log : -abs_log - 1;
        int32_t tail = x > 0 ? x - interval : ((1 << -m_log) + x);

        m_tail = tail / bin_size;
    }

    int32_t get() const {
        int32_t interval = 1 << abs(m_log);
        int32_t bin_size = interval < 512 ? 1 : (m_log < 0 ? (interval >> 9) : (interval >> 8));

        return signum(m_log) * interval + static_cast<int32_t>(m_tail) * bin_size;
    }

public:
    int8_t m_log;
    uint8_t m_tail;
};

short_int32_t operator*(int32_t x, short_int32_t y) {
    return y * x;
}

short_int32_t operator+(int32_t x, short_int32_t y) {
    return y + x;
}

short_int32_t operator-(int32_t x, short_int32_t y) {
    return short_int32_t(x - y.get());
}
\$\endgroup\$
4
\$\begingroup\$

A few improvements:

  1. Assignment operator (=) should return a reference to short_int32_t, returning *this in the implementation.

  2. Operator < or any other comparison/arithmetical operator for that matter, should be const, since they only read the object's state. E.g.: bool operator < (short_int32_t x) const.

  3. Where are the other comparison operators, BTW? I would expect at least ==,!=,<,>,<=,>=.

  4. get/set are good enough names, but wouldn't maybe set32 and get32 be more idiomatic in this case? Or perhaps even more explicit, such as fromInt32 and toInt32.

  5. Consider making those global inline functions member of the class, if they are never used elsewhere.

\$\endgroup\$
  • \$\begingroup\$ thanks, I am not adding all comparison operators since they are trivial and exists here only to show whole concept. My main interest is to improve implementation of get() and set() \$\endgroup\$ – Vasaka Oct 3 '14 at 4:29
3
\$\begingroup\$

I have a few things to add to what @glampert already said:

  • This line of code could probaby be improved:

    int32_t bin_size = interval < 512 ? 1 : (x < 0 ? (interval >> 9) : (interval >> 8));
    

    We know that the binary representations of \$8\$ and \$9\$ are \$0b1000\$ and \$0b1001\$. Therefore the condition x < 0 could be used as an integer representing either \$0b0000\$ or \$0b0001\$. Then, we could shift interval with 8 | (x < 0) to reduces the number of conditions:

    int32_t bin_size = interval < 512 ? 1 : (interval >> (8 | (x < 0)));
    

    I didn't time anything, but reducing the number of potential branches tends to improve performance. Time it anyway if you want to make sure it improves anything.

  • You are using abs all over the place. Is it the standard library std::abs? If so, then please fully qualify it with std::. It will make clear which function you are using.

  • Functions that do not modify the class and do not rely on the class internals to work are generally defined outside of the class. This is notably the case for arithmetic operators. In C++, namespace-level free functions are also part of the class interface, so don't hesitate to use them instead of member methods when it seems to make sense.

  • Avoid repeating yourself. You could implement signum_log2 in terms of abs_log2:

    return abs_log2(x) * signum(x);
    
\$\endgroup\$

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.