Add support for sub-byte aligned writes to lib/Support/Endian.h

[tejohnson]

Summary

As per Duncan's review for D12536, I extracted the sub-byte bit aligned
reading and writing code into lib/Support. Added calls from
BackpatchWord.

I made the support general instead of tailoring it to the specific
use case and data type in the BackpatchWord case. However, I am not
sure how to add unit testing for the other data types. I did test it
for signed types with negative values to ensure the shifting/masking
handled the sign bit properly, by temporarily adding some write/read
calls into llvm operating on a temporary array.

[tejohnson]

• Implement review suggestion for assertion checking code.
  
  Duncan, let me know if you want me to pursue any more unittesting (and any pointers on how to do that would be great) before commit.

[tejohnson]

• Add unittests.

[dexonsmith]

LGTM.

llvm/trunk/include/llvm/Bitcode/BitstreamWriter.h

public:
 
   //===--------------------------------------------------------------------===//
   // Basic Primitives for emitting bits to the stream.
   //===--------------------------------------------------------------------===//
 
   /// Backpatch a 32-bit word in the output at the given bit offset
   /// with the specified value.
   void BackpatchWord(uint64_t BitNo, unsigned NewWord) {
+    using namespace llvm::support;
     unsigned ByteNo = BitNo / 8;
-    if ((BitNo & 7) == 0) {
-      // Already 8-bit aligned
-      support::endian::write32le(&Out[ByteNo], NewWord);
-    } else {
-      uint64_t CurDWord = support::endian::read64le(&Out[ByteNo]);
-      unsigned StartBit = BitNo & 7;
-      // Currently expect to backpatch 0-value placeholders.
-      assert(((CurDWord >> StartBit) & 0xffffffff) == 0);
-      CurDWord |= NewWord << StartBit;
-      support::endian::write64le(&Out[ByteNo], CurDWord);
-    }
+    assert((!endian::readAtBitAlignment<uint32_t, little, unaligned>(
+               &Out[ByteNo], BitNo & 7)) &&
+           "Expected to be patching over 0-value placeholders");
+    endian::writeAtBitAlignment<uint32_t, little, unaligned>(
+        &Out[ByteNo], NewWord, BitNo & 7);
   }
 
   void Emit(uint32_t Val, unsigned NumBits) {
     assert(NumBits && NumBits <= 32 && "Invalid value size!");
     assert((Val & ~(~0U >> (32-NumBits))) == 0 && "High bits set!");
     CurValue |= Val << CurBit;
     if (CurBit + NumBits < 32) {
       CurBit += NumBits;

llvm/trunk/include/llvm/Support/Endian.h

template<typename value_type,
          std::size_t alignment>
 inline void write(void *memory, value_type value) {
   value = byte_swap<value_type, endian>(value);
   memcpy(LLVM_ASSUME_ALIGNED(memory,
            (detail::PickAlignment<value_type, alignment>::value)),
          &value,
          sizeof(value_type));
 }
+
+/// Read a value of a particular endianness from memory, for a location
+/// that starts at the given bit offset within the first byte.
+template <typename value_type, endianness endian, std::size_t alignment>
+inline value_type readAtBitAlignment(const void *memory, uint64_t startBit) {
+  assert(startBit < 8);
+  if (startBit == 0)
+    return read<value_type, endian, alignment>(memory);
+  else {
+    // Read two values and compose the result from them.
+    value_type val[2];
+    memcpy(&val[0],
+           LLVM_ASSUME_ALIGNED(
+               memory, (detail::PickAlignment<value_type, alignment>::value)),
+           sizeof(value_type) * 2);
+    val[0] = byte_swap<value_type, endian>(val[0]);
+    val[1] = byte_swap<value_type, endian>(val[1]);
+
+    // Shift bits from the lower value into place.
+    unsigned lowerVal = val[0] >> startBit;
+    // Mask off upper bits after right shift in case of signed type.
+    unsigned numBitsFirstVal = (sizeof(value_type) * 8) - startBit;
+    lowerVal &= (1 << numBitsFirstVal) - 1;
+
+    // Get the bits from the upper value.
+    unsigned upperVal = val[1] & ((1 << startBit) - 1);
+    // Shift them in to place.
+    upperVal <<= numBitsFirstVal;
+
+    return lowerVal | upperVal;
+  }
+}
+
+/// Write a value to memory with a particular endianness, for a location
+/// that starts at the given bit offset within the first byte.
+template <typename value_type, endianness endian, std::size_t alignment>
+inline void writeAtBitAlignment(void *memory, value_type value,
+                                uint64_t startBit) {
+  assert(startBit < 8);
+  if (startBit == 0)
+    write<value_type, endian, alignment>(memory, value);
+  else {
+    // Read two values and shift the result into them.
+    value_type val[2];
+    memcpy(&val[0],
+           LLVM_ASSUME_ALIGNED(
+               memory, (detail::PickAlignment<value_type, alignment>::value)),
+           sizeof(value_type) * 2);
+    val[0] = byte_swap<value_type, endian>(val[0]);
+    val[1] = byte_swap<value_type, endian>(val[1]);
+
+    // Mask off any existing bits in the upper part of the lower value that
+    // we want to replace.
+    val[0] &= (1 << startBit) - 1;
+    // Now shift in the new bits
+    val[0] |= value << startBit;
+
+    // Mask off any existing bits in the lower part of the upper value that
+    // we want to replace.
+    val[1] &= ~((1 << startBit) - 1);
+    // Next shift the bits that go into the upper value into position.
+    unsigned numBitsFirstVal = (sizeof(value_type) * 8) - startBit;
+    unsigned upperVal = value >> numBitsFirstVal;
+    // Mask off upper bits after right shift in case of signed type.
+    upperVal &= (1 << startBit) - 1;
+    val[1] |= upperVal;
+
+    // Finally, rewrite values.
+    val[0] = byte_swap<value_type, endian>(val[0]);
+    val[1] = byte_swap<value_type, endian>(val[1]);
+    memcpy(LLVM_ASSUME_ALIGNED(
+               memory, (detail::PickAlignment<value_type, alignment>::value)),
+           &val[0], sizeof(value_type) * 2);
+  }
+}
 } // end namespace endian
 
 namespace detail {
 template<typename value_type,
          endianness endian,
          std::size_t alignment>
 struct packed_endian_specific_integral {
   operator value_type() const {

llvm/trunk/unittests/Support/EndianTest.cpp

TEST(Endian, Read) {
   EXPECT_EQ(BigAsHost, (endian::read<int32_t, big, unaligned>(bigval)));
   int32_t LittleAsHost = 0x02030400;
   EXPECT_EQ(LittleAsHost,(endian::read<int32_t, little, unaligned>(littleval)));
 
   EXPECT_EQ((endian::read<int32_t, big, unaligned>(bigval + 1)),
             (endian::read<int32_t, little, unaligned>(littleval + 1)));
 }
 
+TEST(Endian, ReadBitAligned) {
+  // Simple test to make sure we properly pull out the 0x0 word.
+  unsigned char littleval[] = {0x3f, 0x00, 0x00, 0x00, 0xc0, 0xff, 0xff, 0xff};
+  unsigned char bigval[] = {0x00, 0x00, 0x00, 0x3f, 0xff, 0xff, 0xff, 0xc0};
+  EXPECT_EQ(
+      (endian::readAtBitAlignment<int, little, unaligned>(&littleval[0], 6)),
+      0x0);
+  EXPECT_EQ((endian::readAtBitAlignment<int, big, unaligned>(&bigval[0], 6)),
+            0x0);
+  // Test to make sure that signed right shift of 0xf0000000 is masked
+  // properly.
+  unsigned char littleval2[] = {0x00, 0x00, 0x00, 0xf0, 0x00, 0x00, 0x00, 0x00};
+  unsigned char bigval2[] = {0xf0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00};
+  EXPECT_EQ(
+      (endian::readAtBitAlignment<int, little, unaligned>(&littleval2[0], 4)),
+      0x0f000000);
+  EXPECT_EQ((endian::readAtBitAlignment<int, big, unaligned>(&bigval2[0], 4)),
+            0x0f000000);
+}
+
+TEST(Endian, WriteBitAligned) {
+  // This test ensures that signed right shift of 0xffffaa is masked
+  // properly.
+  unsigned char bigval[8] = {0x00};
+  endian::writeAtBitAlignment<int32_t, big, unaligned>(bigval, (int)0xffffaaaa,
+                                                       4);
+  EXPECT_EQ(bigval[0], 0xff);
+  EXPECT_EQ(bigval[1], 0xfa);
+  EXPECT_EQ(bigval[2], 0xaa);
+  EXPECT_EQ(bigval[3], 0xa0);
+  EXPECT_EQ(bigval[4], 0x00);
+  EXPECT_EQ(bigval[5], 0x00);
+  EXPECT_EQ(bigval[6], 0x00);
+  EXPECT_EQ(bigval[7], 0x0f);
+
+  unsigned char littleval[8] = {0x00};
+  endian::writeAtBitAlignment<int32_t, little, unaligned>(littleval,
+                                                          (int)0xffffaaaa, 4);
+  EXPECT_EQ(littleval[0], 0xa0);
+  EXPECT_EQ(littleval[1], 0xaa);
+  EXPECT_EQ(littleval[2], 0xfa);
+  EXPECT_EQ(littleval[3], 0xff);
+  EXPECT_EQ(littleval[4], 0x0f);
+  EXPECT_EQ(littleval[5], 0x00);
+  EXPECT_EQ(littleval[6], 0x00);
+  EXPECT_EQ(littleval[7], 0x00);
+}
+
 TEST(Endian, Write) {
   unsigned char data[5];
   endian::write<int32_t, big, unaligned>(data, -1362446643);
   EXPECT_EQ(data[0], 0xAE);
   EXPECT_EQ(data[1], 0xCA);
   EXPECT_EQ(data[2], 0xB6);
   EXPECT_EQ(data[3], 0xCD);
   endian::write<int32_t, big, unaligned>(data + 1, -1362446643);