Clean up bitfield API a bit.

3 files changed, 204 insertions, 157 deletions

diff --git a/src/bitfield/bitarray.c b/src/bitfield/bitarray.c
new file mode 100644
index 00000000..8fbc941d
--- /dev/null
+++ b/src/bitfield/bitarray.c
@@ -0,0 +1,129 @@
+#include <bitfield/bitfield.h>
+#include <stddef.h>
+#include <limits.h>
+#include <string.h>
+
+#define PREPARE_FIRST_COPY()                                      \
+    do {                                                          \
+    if (bit_count >= (CHAR_BIT - destination_offset_modulo)) {              \
+        *destination &= reverse_mask[destination_offset_modulo];              \
+        bit_count -= CHAR_BIT - destination_offset_modulo;                  \
+    } else {                                                      \
+        *destination &= reverse_mask[destination_offset_modulo]               \
+              | reverse_mask_xor[destination_offset_modulo + bit_count + 1];\
+         c &= reverse_mask[destination_offset_modulo + bit_count    ];\
+        bit_count = 0;                                              \
+    } } while (0)
+
+static const uint8_t reverse_mask[] =
+    { 0x55, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff };
+static const uint8_t reverse_mask_xor[] =
+    { 0xff, 0x7f, 0x3f, 0x1f, 0x0f, 0x07, 0x03, 0x01, 0x00 };
+
+bool copyBits(const uint8_t* source_origin, const uint16_t source_length,
+        const uint16_t source_offset, uint16_t bit_count,
+        uint8_t* destination_origin, const uint16_t destination_length,
+        const uint16_t destination_offset) {
+    if(bit_count < 1) {
+        return false;
+    }
+
+    if(source_offset + bit_count > source_length * CHAR_BIT ||
+            destination_offset + bit_count > destination_length * CHAR_BIT ) {
+        return false;
+    }
+
+    const uint8_t* source = source_origin + (source_offset / CHAR_BIT);
+    uint8_t* destination = destination_origin + (destination_offset / CHAR_BIT);
+    int source_offset_modulo = source_offset % CHAR_BIT;
+    int destination_offset_modulo = destination_offset % CHAR_BIT;
+
+    if(source_offset_modulo == destination_offset_modulo) {
+        if(source_offset_modulo > 0) {
+            uint8_t c = reverse_mask_xor[destination_offset_modulo] & *source++;
+            PREPARE_FIRST_COPY();
+            *destination++ |= c;
+        }
+
+        int byte_len = bit_count / CHAR_BIT;
+        int bit_count_modulo = bit_count % CHAR_BIT;
+
+        if(byte_len > 0) {
+            memcpy(destination, source, byte_len);
+            source += byte_len;
+            destination += byte_len;
+        }
+
+        if(bit_count_modulo > 0) {
+            *destination &= reverse_mask_xor[bit_count_modulo];
+            *destination |= reverse_mask[bit_count_modulo] & *source;
+        }
+    } else {
+        int bit_diff_left_shift;
+        int bit_diff_right_shift;
+        uint8_t c;
+        /*
+         * Begin: Line things up on destination.
+         */
+        if(source_offset_modulo > destination_offset_modulo) {
+            bit_diff_left_shift = source_offset_modulo - destination_offset_modulo;
+            bit_diff_right_shift = CHAR_BIT - bit_diff_left_shift;
+
+            c = *source++ << bit_diff_left_shift;
+            c |= *source >> bit_diff_right_shift;
+            c &= reverse_mask_xor[destination_offset_modulo];
+        } else {
+            bit_diff_right_shift = destination_offset_modulo - source_offset_modulo;
+            bit_diff_left_shift = CHAR_BIT - bit_diff_right_shift;
+
+            c = *source >> bit_diff_right_shift &
+                    reverse_mask_xor[destination_offset_modulo];
+        }
+        PREPARE_FIRST_COPY();
+        *destination++ |= c;
+
+        /*
+         * Middle: copy with only shifting the source.
+         */
+        int byte_len = bit_count / CHAR_BIT;
+        while(--byte_len >= 0) {
+            c = *source++ << bit_diff_left_shift;
+            c |= *source >> bit_diff_right_shift;
+            *destination++ = c;
+        }
+
+        /*
+         * End: copy the remaing bits;
+         */
+        int bit_count_modulo = bit_count % CHAR_BIT;
+        if(bit_count_modulo > 0) {
+            c = *source++ << bit_diff_left_shift;
+            c |= *source >> bit_diff_right_shift;
+            c &= reverse_mask[bit_count_modulo];
+
+            *destination &= reverse_mask_xor[bit_count_modulo];
+            *destination |= c;
+        }
+    }
+    return true;
+}
+
+/**
+ * Find the ending bit of a bitfield within the final byte.
+ *
+ * Returns: a bit position from 0 to 7.
+ */
+static uint8_t findEndBit(const uint16_t startBit, const uint16_t numBits) {
+    int endBit = numBits % CHAR_BIT;
+    return endBit == 0 ? CHAR_BIT : endBit;
+}
+
+bool copyBitsRightAligned(const uint8_t source[], const uint16_t source_length,
+                const uint16_t offset, const uint16_t bit_count,
+                uint8_t* destination, const uint16_t destination_length) {
+    return copyBits(source, source_length, offset, bit_count, destination,
+            destination_length,
+            // provide a proper destination offset so the result is right
+            // aligned
+            CHAR_BIT - findEndBit(offset, bit_count));
+}
diff --git a/src/bitfield/bitfield.c b/src/bitfield/bitfield.c
index 834e443e..b0396413 100644
--- a/src/bitfield/bitfield.c
+++ b/src/bitfield/bitfield.c
@@ -5,124 +5,16 @@
 
 #define NIBBLE_SIZE (CHAR_BIT / 2)
 
-#define PREPARE_FIRST_COPY()                                      \
-    do {                                                          \
-    if (source_length >= (CHAR_BIT - destination_offset_modulo)) {              \
-        *destination     &= reverse_mask[destination_offset_modulo];              \
-        source_length -= CHAR_BIT - destination_offset_modulo;                  \
-    } else {                                                      \
-        *destination     &= reverse_mask[destination_offset_modulo]               \
-              | reverse_mask_xor[destination_offset_modulo + source_length + 1];\
-         c       &= reverse_mask[destination_offset_modulo + source_length    ];\
-        source_length = 0;                                              \
-    } } while (0)
-
-/**
- * Find the ending bit of a bitfield within the final byte.
- *
- * Returns: a bit position from 0 to 7.
- */
-static uint8_t findEndBit(const uint16_t startBit, const uint16_t numBits) {
-    int endBit = numBits % CHAR_BIT;
-    return endBit == 0 ? CHAR_BIT : endBit;
-}
-
-
-// TODO can probably remove this
-static int byteForBit(const uint16_t startBit) {
-    return startBit / CHAR_BIT;
+uint64_t bitmask(const uint8_t numBits) {
+    return (((uint64_t)0x1) << numBits) - 1;
 }
 
-/* Thanks to
- * http://stackoverflow.com/questions/3534535/whats-a-time-efficient-algorithm-to-copy-unaligned-bit-arrays
- */
-static void bitarray_copy(const uint8_t* source_origin, int source_offset,
-        int source_length, uint8_t* destination_origin, int destination_offset) {
-    static const uint8_t reverse_mask[] =
-        { 0x55, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff };
-    static const uint8_t reverse_mask_xor[] =
-        { 0xff, 0x7f, 0x3f, 0x1f, 0x0f, 0x07, 0x03, 0x01, 0x00 };
-
-    if(source_length < 1) {
-        return;
-    }
-
-    const uint8_t* source = source_origin + byteForBit(source_offset);
-    uint8_t* destination = destination_origin + byteForBit(destination_offset);
-    int source_offset_modulo = source_offset % CHAR_BIT;
-    int destination_offset_modulo = destination_offset % CHAR_BIT;
-
-    if(source_offset_modulo == destination_offset_modulo) {
-        if(source_offset_modulo > 0) {
-            uint8_t c = reverse_mask_xor[destination_offset_modulo] & *source++;
-            PREPARE_FIRST_COPY();
-            *destination++ |= c;
-        }
-
-        int byte_len = source_length / CHAR_BIT;
-        int source_length_modulo = source_length % CHAR_BIT;
-
-        if(byte_len > 0) {
-            memcpy(destination, source, byte_len);
-            source += byte_len;
-            destination += byte_len;
-        }
-
-        if(source_length_modulo > 0) {
-            *destination &= reverse_mask_xor[source_length_modulo];
-            *destination |= reverse_mask[source_length_modulo] & *source;
-        }
-    } else {
-        int bit_diff_left_shift;
-        int bit_diff_right_shift;
-        uint8_t c;
-        /*
-         * Begin: Line things up on destination.
-         */
-        if(source_offset_modulo > destination_offset_modulo) {
-            bit_diff_left_shift = source_offset_modulo - destination_offset_modulo;
-            bit_diff_right_shift = CHAR_BIT - bit_diff_left_shift;
-
-            c = *source++ << bit_diff_left_shift;
-            c |= *source >> bit_diff_right_shift;
-            c &= reverse_mask_xor[destination_offset_modulo];
-        } else {
-            bit_diff_right_shift = destination_offset_modulo - source_offset_modulo;
-            bit_diff_left_shift = CHAR_BIT - bit_diff_right_shift;
-
-            c = *source >> bit_diff_right_shift &
-                    reverse_mask_xor[destination_offset_modulo];
-        }
-        PREPARE_FIRST_COPY();
-        *destination++ |= c;
-
-        /*
-         * Middle: copy with only shifting the source.
-         */
-        int byte_len = source_length / CHAR_BIT;
-        while(--byte_len >= 0) {
-            c = *source++ << bit_diff_left_shift;
-            c |= *source >> bit_diff_right_shift;
-            *destination++ = c;
-        }
-
-        /*
-         * End: copy the remaing bits;
-         */
-        int source_length_modulo = source_length % CHAR_BIT;
-        if(source_length_modulo > 0) {
-            c = *source++ << bit_diff_left_shift;
-            c |= *source >> bit_diff_right_shift;
-            c &= reverse_mask[source_length_modulo];
-
-            *destination &= reverse_mask_xor[source_length_modulo];
-            *destination |= c;
-        }
+static uint16_t bitsToBytes(uint32_t bits) {
+    uint8_t byte_count = bits / CHAR_BIT;
+    if(bits % CHAR_BIT != 0) {
+        ++byte_count;
     }
-}
-
-uint64_t bitmask(const uint8_t numBits) {
-    return (((uint64_t)0x1) << numBits) - 1;
+    return byte_count;
 }
 
 uint64_t getBitField(uint64_t data, const uint16_t startBit,
@@ -131,24 +23,18 @@ uint64_t getBitField(uint64_t data, const uint16_t startBit,
     if(!bigEndian) {
         data = __builtin_bswap64(data);
     }
-    getBits(startBit, numBits, (const uint8_t*)&data,
-            CHAR_BIT * sizeof(uint64_t),
-            bigEndian ? ENDIANNESS_BIG_ENDIAN : ENDIANNESS_LITTLE_ENDIAN,
-            result);
-    // TODO the result has already been shifted to be aligned right, so if we
-    // try and bswap here it's going to be screwed up unless it was byte aligned
+    copyBitsRightAligned((const uint8_t*)&data, sizeof(data), startBit, numBits,
+            result, sizeof(result));
     uint64_t int_result = 0;
-    // TODO should the API return the byte length of data in the result array?
-    // i think yes.
-    uint8_t byte_count = numBits / CHAR_BIT;
-    if(numBits % CHAR_BIT != 0) {
-        ++byte_count;
-    }
 
-    // TODO wow, can't believe this works, but something is clearly wrong with
-    // the API!
-    for(int i = 0; i < byte_count; i++) {
-        int_result |= result[byte_count - i - 1] << (CHAR_BIT * i);
+    if(!bigEndian) {
+        // we need to swap the byte order of the array to get it into a
+        // uint64_t, but it's been right aligned so we have to be more careful
+        for(int i = 0; i < bitsToBytes(numBits); i++) {
+            int_result |= result[bitsToBytes(numBits) - i - 1] << (CHAR_BIT * i);
+        }
+    } else {
+        int_result = *(uint64_t*)result;
     }
     return int_result;
 }
@@ -157,19 +43,20 @@ uint64_t getBitField(uint64_t data, const uint16_t startBit,
  * TODO it would be nice to have a warning if you call with this a value that
  * won't fit in the number of bits you've specified it should use.
  */
-void setBitField(uint64_t* data, uint64_t value, int startBit, int numBits) {
-    int shiftDistance = 64 - startBit - numBits;
+void setBitField(uint64_t* data, uint64_t value, const uint16_t startPos,
+        const uint16_t numBits) {
+    int shiftDistance = 64 - startPos - numBits;
     value <<= shiftDistance;
     *data &= ~(bitmask(numBits) << shiftDistance);
     *data |= value;
 }
 
-uint8_t nthByte(uint64_t source, int byteNum) {
+uint8_t nthByte(const uint64_t source, const uint16_t byteNum) {
     return (source >> (64 - ((byteNum + 1) * CHAR_BIT))) & 0xFF;
 }
 
 uint8_t getNibble(const uint8_t nibble_index, const uint8_t data[],
-        const uint8_t length, Endianness endianness) {
+        const uint8_t length) {
     uint8_t byte_index = nibble_index / 2;
     uint8_t result;
     if(byte_index < length) {
@@ -182,18 +69,10 @@ uint8_t getNibble(const uint8_t nibble_index, const uint8_t data[],
     return result;
 }
 
-// TODO getBytes, return status and store in output parameter
 uint8_t getByte(const uint8_t byte_index, const uint8_t data[],
-        const uint8_t length, Endianness endianness) {
+        const uint8_t length) {
     if(byte_index < length) {
         return data[byte_index];
     }
     return 0;
 }
-
-void getBits(const uint16_t start_index, const uint16_t field_size,
-        const uint8_t data[], const uint8_t length, Endianness endianness,
-        uint8_t* result) {
-    bitarray_copy(data, start_index, field_size, result,
-            CHAR_BIT - findEndBit(start_index, field_size));
-}
diff --git a/src/bitfield/bitfield.h b/src/bitfield/bitfield.h
index ce68b949..bf5c9b7d 100644
--- a/src/bitfield/bitfield.h
+++ b/src/bitfield/bitfield.h
@@ -8,20 +8,57 @@
 extern "C" {
 #endif
 
-typedef enum {
-    ENDIANNESS_LITTLE_ENDIAN,
-    ENDIANNESS_BIG_ENDIAN
-} Endianness;
-
 uint8_t getNibble(const uint8_t nibble_index, const uint8_t data[],
-        const uint8_t length, Endianness endianness);
+        const uint8_t length);
 
 uint8_t getByte(const uint8_t byte_index, const uint8_t data[],
-        const uint8_t length, Endianness endianness);
+        const uint8_t length);
+
+/* Public: Copy a range of bits from one bit array to another.
+ *
+ * The range does not need to be byte aligned, and the source and destination do
+ * not have to be the same size (as long as the desitnation has enough room to
+ * fit the range).
+ *
+ * A bit array with regards to this function always has the leftmost bit in byte
+ * 0, i.e. bit index is the leftmost bit of byte 0. Endianness does not matter.
+ *
+ * Thanks to
+ * http://stackoverflow.com/questions/3534535/whats-a-time-efficient-algorithm-to-copy-unaligned-bit-arrays
+ * for the implementation of the algorithm.
+ *
+ * source_origin - the source array.
+ * source_length - the total length of the source array in bytes,
+ *      for range checking.
+ * source_offset - an offset in bits to start the copy from the source array.
+ *      Specify 0 to start from source_origin.
+ * bit_count - the number of bits to copy.
+ * destination_origin - the destination array.
+ * desitnation_length - the total length of the destination array in bytes,
+ *      for range checking.
+ * destination_offset - an offset in bits to start placing the copied range into
+ *      the destination array. Specify 0 to start from the beginning of the
+ *      destination. If you are copying a range not aligned on a byte, you
+ *      probably want to set this to a positive offset to right the resulting
+ *      bits in the destination.
+ *
+ * Returns true if the copy was successful and false if the range exceeded the
+ * size of the source or destination, or if the range size negative or 0.
+ */
+bool copyBits(const uint8_t* source_origin, const uint16_t source_length,
+        const uint16_t source_offset, uint16_t bit_count,
+        uint8_t* destination_origin, const uint16_t destination_length,
+        const uint16_t destination_offset);
+
+bool copyBitsRightAligned(const uint8_t source[], const uint16_t source_length,
+                const uint16_t offset, const uint16_t bit_count,
+                uint8_t* destination, const uint16_t destination_length);
 
-void getBits(const uint16_t start_index, const uint16_t field_size,
-        const uint8_t data[], const uint8_t length, Endianness endianness,
-        uint8_t* result);
+// TODO using uint64_t everywhere for CAN message payload is kind of cute, but
+// in actuality a CAN message may have a smaller payload, and it makes all of
+// these functions not applicable to other data sizes. It's also fairly
+// inefficient on 32-bit platforms. how much work is it to switch vi-firmware
+// to using uint8_t*?
 
 /* Public: Reads a subset of bits from a byte array.
  *
@@ -55,7 +92,8 @@ void getBits(const uint16_t start_index, const uint16_t field_size,
  *
  * Returns the value of the requested bit field.
  */
-uint64_t getBitField(uint64_t data, const uint16_t startPos, const uint16_t numBits, bool bigEndian);
+uint64_t getBitField(uint64_t data, const uint16_t startPos,
+        const uint16_t numBits, bool bigEndian);
 
 /* Public: Set the bit field in the given data array to the new value.
  *
@@ -63,7 +101,8 @@ uint64_t getBitField(uint64_t data, const uint16_t startPos, const uint16_t numB
  * value - the value to set in the bit field.
  * startPos - the starting index of the bit field (beginning from 0).
  */
-void setBitField(uint64_t* data, uint64_t value, int startPos, int numBits);
+void setBitField(uint64_t* data, uint64_t value, const uint16_t startPos,
+        const uint16_t numBits);
 
 /* Public: Retreive the nth byte out of 8 bytes in a uint64_t.
  *
@@ -72,7 +111,7 @@ void setBitField(uint64_t* data, uint64_t value, int startPos, int numBits);
  *
  * Returns the requested byte from the source bytes.
  */
-uint8_t nthByte(uint64_t source, int byteNum);
+uint8_t nthByte(const uint64_t source, const uint16_t byteNum);
 
 #ifdef __cplusplus
 }