3
\$\begingroup\$

I'd like to learn how I can optimize the following byte extension methods.

I'm targeting .NET Standard 2.0 but I'm curious if there are any ways to go about some of this functionality using features available in 2.1 (like Span<T>).

I feel like the ShiftRight, byte.HasSamePrefix, byte[].HasSamePrefix methods could be improved.

using System;

namespace SharpTorrent.Dht.Extensions
{
    /// <summary>
    /// This class provides static extension methods for the byte type.
    /// </summary>
    public static class ByteExtensions
    {
        /// <summary>
        /// Determine if the bit at the provided index is set (indexed from left-to-right).
        /// </summary>
        /// <param name="value">The byte whose index to check.</param>
        /// <param name="index">The bit index to check.</param>
        /// <returns>The mutated byte value</returns>
        public static bool IsBitSetAtIndex(
            this byte value
            , byte index
        ) => index > 7
            ? throw new IndexOutOfRangeException("Index must be between 0 and 7 inclusive.")
            : (value & (1 << 7 - index)) != 0;

        /// <summary>
        /// Set the bit value at the provided index (indexed from left-to-right).
        /// </summary>
        /// <param name="value">The byte value whose bit to set.</param>
        /// <param name="index">The index of the bit to set.</param>
        /// <returns>The mutated byte value</returns>
        public static byte SetBitAtIndex(
            this byte value
            , byte index
        ) => index > 7
            ? throw new IndexOutOfRangeException("Index must be between 0 and 7 inclusive.")
            : (byte) (value | (1 << 7 - index));

        /// <summary>
        /// Clear the bit value at the provided index (indexed from left-to-right).
        /// </summary>
        /// <param name="value">The byte value whose bit to clear.</param>
        /// <param name="index">The index of the bit to clear.</param>
        /// <returns>The mutated byte value</returns>
        public static byte ClearBitAtIndex(
            this byte value
            , byte index
        ) => index > 7
            ? throw new IndexOutOfRangeException("Index must be between 0 and 7 inclusive.")
            : (byte) (value & ~(1 << 7 - index));

        /// <summary>
        /// Toggle the bit value at the provided index (indexed from left-to-right).
        /// </summary>
        /// <param name="value">The byte value whose bit to toggle.</param>
        /// <param name="index">The index of the bit to toggle.</param>
        /// <returns>The mutated byte value</returns>
        public static byte ToggleBitAtIndex(
            this byte value
            , byte index
        ) => index > 7
            ? throw new IndexOutOfRangeException("Index must be between 0 and 7 inclusive.")
            : (byte) (value ^ (1 << 7 - index));


        /// <summary>
        /// Shift the bits of the provided byte array right by the provided distance. Bits will shift across byte
        /// boundaries in the array. Zero will be shifted in from the left. The sign of the byte array isn't considered.
        /// </summary>
        /// <param name="bytes">The byte array to shift.</param>
        /// <param name="distance">The distance to shift the bits.</param>
        /// <returns>The shifted byte array.</returns>
        public static byte[] ShiftRight(
            this byte[] bytes
            , uint distance = 1
        )
        {
            // For each index distance to shift the bits.
            for (var d = 0; d < distance; d++)
            {
                // For every byte in the array (MSB <- LSB).
                for (var i = bytes.Length - 1; i >= 0; i--)
                {
                    // Shift the current index right by one bit.
                    bytes[i] = (byte) (bytes[i] >> 1);

                    // Set the most significant bit if necessary.
                    if (i >= 1 && (bytes[i - 1] & 0x01) != 0)
                    {
                        bytes[i] |= (byte) (bytes[i] | 0x80);
                    }
                }
            }

            return bytes;
        }

        /// <summary>
        /// Mask off the the nth bit position of the byte starting from the left. Indexing is 0-based.
        /// 
        /// e.g. A value of 0xFF will produce the following:
        /// 
        /// 11111111 (0) -> 01111111
        /// 11111111 (1) -> 00111111
        /// 11111111 (2) -> 00011111
        /// 11111111 (3) -> 00001111
        /// 11111111 (4) -> 00000111
        /// 11111111 (5) -> 00000011
        /// 11111111 (6) -> 00000001
        /// 11111111 (7) -> 00000000
        /// </summary>
        /// <param name="value">The byte to mask.</param>
        /// <param name="maskIndex"></param>
        /// <returns>The masked byte value.</returns>
        public static byte MaskLeft(this byte value, byte maskIndex) => (byte) (value & (0xFF >> (maskIndex + 1)));

        /// <summary>
        /// Mask off the the nth bit position of the byte starting from the right. Indexing is 0-based.
        /// 
        /// e.g. A value of 0xFF will produce the following:
        /// 
        /// 11111111 (0) -> 11111110
        /// 11111111 (1) -> 11111100
        /// 11111111 (2) -> 11111000
        /// 11111111 (3) -> 11110000
        /// 11111111 (4) -> 11100000
        /// 11111111 (5) -> 11000000
        /// 11111111 (6) -> 10000000
        /// 11111111 (7) -> 00000000
        /// </summary>
        /// <param name="value"></param>
        /// <param name="maskIndex"></param>
        /// <returns></returns>
        public static byte MaskRight(this byte value, byte maskIndex) => (byte) (value & (0xFF << (maskIndex + 1)));


        /// <summary>
        /// Determine if two bytes share a common prefix from left-to-right. Indexing is 0-based.
        /// </summary>
        /// <param name="value">The first value.</param>
        /// <param name="second">The value to compare against.</param>
        /// <param name="bitIndex">The prefix index to check up to.</param>
        /// <returns>Whether or not the two bytes share a matching prefix.</returns>
        /// <exception cref="IndexOutOfRangeException">Thrown when a bit index greater than 7 is provided.</exception>
        public static bool HasSamePrefix(this byte value, byte second, byte bitIndex)
        {
            if (bitIndex > 7)
            {
                throw new IndexOutOfRangeException("Index must be between 0 and 7 inclusive.");
            }

            if (bitIndex == 7)
            {
                return value.IsBitSetAtIndex(7) == second.IsBitSetAtIndex(7);
            }

            var maskIndex = (byte) (6 - bitIndex);

            return value.MaskRight(maskIndex) == second.MaskRight(maskIndex);
        }

        /// <summary>
        /// Determine if the byte arrays share a common prefix from left-to-right. Indexing is 0-based.
        /// </summary>
        /// <param name="first">The first byte array.</param>
        /// <param name="second">The byte array to compare against.</param>
        /// <param name="bitIndex">The bit index to check up to.</param>
        /// <returns></returns>
        /// <exception cref="IndexOutOfRangeException">
        /// Thrown when the bit index is greater than the number of bits in the smallest byte array.
        /// </exception>
        public static bool HasSamePrefix(
            this byte[] first
            , byte[] second
            , int bitIndex
        )
        {
            var maxIndex = Math.Min(first.Length, second.Length) - 1;
            var endByteIndex = bitIndex / 8;
            var byteIndex = 0;

            if (endByteIndex > maxIndex)
            {
                throw new IndexOutOfRangeException("Bit index exceeds bit index of smallest array.");
            }

            for (; byteIndex < endByteIndex; byteIndex++)
            {
                if (first[byteIndex] != second[byteIndex])
                {
                    return false;
                }
            }

            return first[byteIndex].HasSamePrefix(
                second[byteIndex]
                , (byte) (7 - bitIndex % 8)
            );
        }
    }
}
\$\endgroup\$
7
  • 1
    \$\begingroup\$ I have rolled back your last edit. Please do not add the updated code to the question as it's getting confusing this way. You should post a self-answer instead. \$\endgroup\$
    – t3chb0t
    Oct 3, 2019 at 16:39
  • \$\begingroup\$ This updated code was @harold solution but cleaned up. I want to avoid taking credit for someone else's answer. I think removing the code actually hurts others who are looking for a solution as now they must roll their own. \$\endgroup\$
    – masterwok
    Oct 3, 2019 at 16:43
  • 1
    \$\begingroup\$ Please see What should I do when someone answers my question? - Do not add an improved version of the code after receiving an answer. Including revised versions of the code makes the question confusing, especially if someone later reviews the newer code. \$\endgroup\$
    – t3chb0t
    Oct 3, 2019 at 16:45
  • 1
    \$\begingroup\$ Posting a self-answer. If you want to show everyone how you improved your code, but don't want to ask another question, then post an answer to your own question. Self-answers are acceptable on Stack Exchange sites, and even encouraged \$\endgroup\$
    – t3chb0t
    Oct 3, 2019 at 16:45
  • 1
    \$\begingroup\$ BTW about the now removed code, I'm pretty sure you can't skip zeroing out the "top". \$\endgroup\$
    – harold
    Oct 3, 2019 at 20:17

2 Answers 2

3
\$\begingroup\$

ShiftRight does not need to be a series of shift-by-1 operations.

An other approach is:

  1. shift whole bytes, by a distance of distance / 8
  2. shift the bytes by distance % 8, while shifting in bits from the next byte

I have to be a little careful here because you used an unsual byte order (lowest order byte last) and you're doing this in-place. Here's an attempt (not debugged):

// move bytes to shift by multiples of 8
int byteDistance = (int)(distance / 8);
for (int i = bytes.Length - 1; i >= byteDistance; i--)
{
    bytes[i] = bytes[i - byteDistance];
}
// zero out the "top" of the array
for (int i = byteDistance - 1; i >= 0; i--)
{
    bytes[i] = 0;
}

// bit-granular shift by the remainder of the distance
int bitShift = (int)(distance % 8);
for (int i = bytes.Length - 1; i >= 1; i--)
{
    int twoBytes = bytes[i] | (bytes[i - 1] << 8);
    bytes[i] = (byte)(twoBytes >> bitShift);
}
bytes[0] >>= bitShift;

Some variants may be interesting:

  • The last loop can iterate less, stopping at the part of the array that was left zero by the byte-granular shift.
  • The last loop could be unrolled, packing more bytes into an int and making "better use" of the integer shift.
  • With Span<T> and primarily targeting 64bit, we could MemoryMarshal.Cast the Span<byte> to an Span<uint>, then do a similar thing as above but with two uint in an ulong rather than two byte in an int. It takes some care with arrays with length not a multiple of 4, of course.

Notable non-possibility:

  • An other new thing in Standard 2.1 thing is System.Numerics.Vector, but it still lacks bit-shifts (I've heard they will probably be added someday), so it can't be used for this, even though the hardware can do it.
\$\endgroup\$
1
  • \$\begingroup\$ Oh, thank you for sharing your solution. I spent hours looking at this method and would've never thought to combine bytes using an int or shift over multiples of 8. I stepped through it on paper the other night and it makes perfect sense. Thank you for also expanding on variations and for going into Vector and Span. \$\endgroup\$
    – masterwok
    Sep 30, 2019 at 0:36
2
\$\begingroup\$

Review

  • The postfix AtIndex is too verbose. You don't have any other operations like AtMask or anything and the index is provided as argument. So I would prefer IsBitSet over IsBitSetAtIndex etc.
  • The index is sometimes a byte, sometimes a uint. I would not bother with such level of (over-)engineered type picks. Stick with the common type for an index int. You can always add argument checks for bounds.
  • You can replace 1 << 7 - index with 1 << index in your operations. This is written more compactly and is a well known bit operation technique. Right-to-left indexes are more common in bitwise systems.
\$\endgroup\$
2
  • \$\begingroup\$ Thank you for your feedback. I've implemented your first two recommended changes. As for the third recommendation, given an index of 0 would produce the following 1 << 7 - 0 (10000000) and 1 << 0 (00000001). My intention was for bits to be indexed from left-to-right. For example, in the method IsBitSet providing an index of 0 would check if the first bit on the left side of the byte is set. Is it more common to index from right-to-left when dealing with bitwise operations? \$\endgroup\$
    – masterwok
    Sep 29, 2019 at 5:37
  • 2
    \$\begingroup\$ I did expect right-to-left: math.stackexchange.com/questions/891445/…. But if you want to change the direction, I don't see a real issue. Just make sure to document your specification. \$\endgroup\$
    – dfhwze
    Sep 29, 2019 at 7:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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