10
\$\begingroup\$

For an embedded project I want to shift a (byte) array left by a certain amount of bits. I've built this template function to do so:

template <typename T>
constexpr void shift_array_left(T *arr, const size_t size, const size_t bits, const bool zero = false) {
    const size_t chunks = bits / (8 * sizeof(T));

    if (chunks >= size) {
        if (zero) {
            memset(arr, 0, size);
        }
        return;
    }

    if (chunks) {
        memmove(arr, arr + chunks, size - chunks);
        if (zero) {
            memset(arr + size - chunks, 0, chunks);
        }
    }

    const size_t left = bits % (8 * sizeof(T));

    // If we have non directly addressable bits left we need to move the whole thing one by one.
    if (left) {
        const size_t right = (8 * sizeof(T)) - left;
        const size_t l = size - chunks - 1;
        for (size_t i = 0; i < l; i++) {
            arr[i] = ((arr[i] << left) & ~left) | (arr[i+1] >> right);
        }
        arr[l] = (arr[l] << left) & ~left;
    }
}

Some questions I have:

  1. I inferred from the memmove and memcpy relationships that memmove doesn't guarantee zeroing out any 'gap' created. Can I do away with the zeroing parts?

  2. This function only makes sense for unsigned integer types, what is the best way to force the compiler to only accept these, without repeating function bodies?

I'd, of course, appreciate any further feedback / criticism.

Update: Live example in compiler explorer: https://godbolt.org/g/I3qDsL

\$\endgroup\$
  • \$\begingroup\$ Please do not edit the code. Doing so makes the answers invalid, which is why it is against site policy. \$\endgroup\$ – Donald.McLean May 26 '17 at 11:53
  • \$\begingroup\$ My apologies, it was certainly not my intention to make answers (look) invalid. I've read up on related policies. \$\endgroup\$ – Stefan May 26 '17 at 12:07
5
\$\begingroup\$

For the second question you can use type_traits(is_unsigned) and enable_if. http://en.cppreference.com/w/cpp/types/is_unsigned http://en.cppreference.com/w/cpp/types/enable_if

For the first question: The main difference between memmove and memcpy is that memmove can be used to relocate a piece of memory to somewhere that overlaps the memory block that you're trying to move. And therefore the original pointer will no longer be valid. So I think it's up to you how you want your function to behave, if you want the parts to be zeroed or not or leave it too the user.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the type traits suggestion, the compiler error messages aren't pretty, but it works. I've changed the template signature to: \$\endgroup\$ – Stefan May 26 '17 at 11:03
  • \$\begingroup\$ template <typename T, typename std::enable_if<std::is_unsigned<T>::value>::type* = nullptr>. I've already added a user selectable option to zero out the abandoned memory, but I'm still not 100% clear on what exactly happens with the memory abandoned by memmove. My guess is nothing: no use / reclaim, just 'dead' until end of stack frame or delete call. \$\endgroup\$ – Stefan May 26 '17 at 11:10
  • \$\begingroup\$ Is memcpy/memmove even safe to use in an embedded context? malloc is not available in most embedded compilers because dynamic memory allocation on an embedded system is dangerous. Is memcpy/memmove still safe? \$\endgroup\$ – user9993 May 26 '17 at 12:46
  • \$\begingroup\$ @user9993 memcpy() should be safe in embedded contexts, it does no memory allocations. memmove() requires a temporary array, so it'd depend on how that's allocated for your implementation. \$\endgroup\$ – user2296177 May 26 '17 at 17:32
0
\$\begingroup\$

Your code is not portable because you assume that the number of bits in a char are 8. There is no such guarantee in C++.

Simply include the <climits> header and replace your magic constant 8 by CHAR_BIT.

\$\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.