|
| 1 | +// Licensed to the .NET Foundation under one or more agreements. |
| 2 | +// The .NET Foundation licenses this file to you under the MIT license. |
| 3 | +// See the LICENSE file in the project root for more information. |
| 4 | + |
| 5 | +using System; |
| 6 | +using System.Diagnostics; |
| 7 | +using System.Runtime.CompilerServices; |
| 8 | +using System.Runtime.InteropServices; |
| 9 | + |
| 10 | +namespace Microsoft.Data.Analysis |
| 11 | +{ |
| 12 | + // License for BitUtility |
| 13 | + // -------------------------------------- |
| 14 | + // This class is based on the code from Apache Arrow project |
| 15 | + // https://github.com/apache/arrow/blob/main/csharp/src/Apache.Arrow/BitUtility.cs |
| 16 | + // that is available in the public domain inder Apache-2.0 license. |
| 17 | + // You may obtain a copy of the License at: http://www.apache.org/licenses/LICENSE-2.0 |
| 18 | + internal static class BitUtility |
| 19 | + { |
| 20 | + private static ReadOnlySpan<byte> PopcountTable => new byte[] { |
| 21 | + 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, |
| 22 | + 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, |
| 23 | + 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, |
| 24 | + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, |
| 25 | + 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, |
| 26 | + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, |
| 27 | + 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, |
| 28 | + 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, |
| 29 | + }; |
| 30 | + |
| 31 | + private static ReadOnlySpan<byte> BitMask => new byte[] { |
| 32 | + 1, 2, 4, 8, 16, 32, 64, 128 |
| 33 | + }; |
| 34 | + |
| 35 | + // Faster to use when we already have a span since it avoids indexing |
| 36 | + public static bool IsValid(ReadOnlySpan<byte> bitMapBufferSpan, int index) |
| 37 | + { |
| 38 | + var nullBitMapSpanIndex = index / 8; |
| 39 | + var thisBitMap = bitMapBufferSpan[nullBitMapSpanIndex]; |
| 40 | + return IsBitSet(thisBitMap, index); |
| 41 | + } |
| 42 | + |
| 43 | + public static bool IsBitSet(byte curBitMap, int index) |
| 44 | + { |
| 45 | + return ((curBitMap >> (index & 7)) & 1) != 0; |
| 46 | + } |
| 47 | + |
| 48 | + public static bool IsBitClear(byte curBitMap, int index) |
| 49 | + { |
| 50 | + return ((curBitMap >> (index & 7)) & 1) == 0; |
| 51 | + } |
| 52 | + |
| 53 | + public static bool GetBit(byte data, int index) => |
| 54 | + ((data >> index) & 1) != 0; |
| 55 | + |
| 56 | + public static bool GetBit(ReadOnlySpan<byte> data, int index) => |
| 57 | + (data[index / 8] & BitMask[index % 8]) != 0; |
| 58 | + |
| 59 | + public static void ClearBit(Span<byte> data, int index) |
| 60 | + { |
| 61 | + data[index / 8] &= (byte)~BitMask[index % 8]; |
| 62 | + } |
| 63 | + |
| 64 | + public static void SetBit(Span<byte> data, int index) |
| 65 | + { |
| 66 | + data[index / 8] |= BitMask[index % 8]; |
| 67 | + } |
| 68 | + |
| 69 | + public static void SetBit(Span<byte> data, long index, bool value) |
| 70 | + { |
| 71 | + int idx = (int)(index / 8); |
| 72 | + int mod = (int)(index % 8); |
| 73 | + data[idx] = value |
| 74 | + ? (byte)(data[idx] | BitMask[mod]) |
| 75 | + : (byte)(data[idx] & ~BitMask[mod]); |
| 76 | + } |
| 77 | + |
| 78 | + /// <summary> |
| 79 | + /// Set the number of bits in a span of bytes starting |
| 80 | + /// at a specific index, and limiting to length. |
| 81 | + /// </summary> |
| 82 | + /// <param name="data">Span to set bits value.</param> |
| 83 | + /// <param name="index">Bit index to start counting from.</param> |
| 84 | + /// <param name="length">Maximum of bits in the span to consider.</param> |
| 85 | + /// <param name="value">Bit value.</param> |
| 86 | + public static void SetBits(Span<byte> data, long index, long length, bool value) |
| 87 | + { |
| 88 | + if (length == 0) |
| 89 | + return; |
| 90 | + |
| 91 | + var endBitIndex = index + length - 1; |
| 92 | + |
| 93 | + // Use simpler method if there aren't many values |
| 94 | + if (length < 20) |
| 95 | + { |
| 96 | + for (var i = index; i <= endBitIndex; i++) |
| 97 | + { |
| 98 | + SetBit(data, i, value); |
| 99 | + } |
| 100 | + return; |
| 101 | + } |
| 102 | + |
| 103 | + // Otherwise do the work to figure out how to copy whole bytes |
| 104 | + var startByteIndex = (int)(index / 8); |
| 105 | + var startBitOffset = (int)(index % 8); |
| 106 | + var endByteIndex = (int)(endBitIndex / 8); |
| 107 | + var endBitOffset = (int)(endBitIndex % 8); |
| 108 | + |
| 109 | + // If the starting index and ending index are not byte-aligned, |
| 110 | + // we'll need to set bits the slow way. If they are |
| 111 | + // byte-aligned, and for all other bytes in the 'middle', we |
| 112 | + // can use a faster byte-aligned set. |
| 113 | + var fullByteStartIndex = startBitOffset == 0 ? startByteIndex : startByteIndex + 1; |
| 114 | + var fullByteEndIndex = endBitOffset == 7 ? endByteIndex : endByteIndex - 1; |
| 115 | + |
| 116 | + // Bits we will be using to finish up the first byte |
| 117 | + if (startBitOffset != 0) |
| 118 | + { |
| 119 | + var slice = data.Slice(startByteIndex, 1); |
| 120 | + for (var i = startBitOffset; i <= 7; i++) |
| 121 | + SetBit(slice, i, value); |
| 122 | + } |
| 123 | + |
| 124 | + if (fullByteEndIndex >= fullByteStartIndex) |
| 125 | + { |
| 126 | + var slice = data.Slice(fullByteStartIndex, fullByteEndIndex - fullByteStartIndex + 1); |
| 127 | + byte fill = (byte)(value ? 0xFF : 0x00); |
| 128 | + |
| 129 | + slice.Fill(fill); |
| 130 | + } |
| 131 | + |
| 132 | + if (endBitOffset != 7) |
| 133 | + { |
| 134 | + var slice = data.Slice(endByteIndex, 1); |
| 135 | + for (int i = 0; i <= endBitOffset; i++) |
| 136 | + SetBit(slice, i, value); |
| 137 | + } |
| 138 | + } |
| 139 | + |
| 140 | + public static void ElementwiseAnd(ReadOnlySpan<byte> left, ReadOnlySpan<byte> right, Span<byte> result) |
| 141 | + { |
| 142 | + for (var i = 0; i < left.Length; i++) |
| 143 | + result[i] = (byte)(left[i] & right[i]); |
| 144 | + } |
| 145 | + |
| 146 | + /// <summary> |
| 147 | + /// Returns the population count (number of bits set) in a span of bytes starting |
| 148 | + /// at 0 bit and limiting to length of bits. |
| 149 | + /// </summary> |
| 150 | + /// <param name="span"></param> |
| 151 | + /// <param name="length"></param> |
| 152 | + /// <returns></returns> |
| 153 | + public static long GetBitCount(ReadOnlySpan<byte> span, long length) |
| 154 | + { |
| 155 | + var endByteIndex = (int)(length / 8); |
| 156 | + |
| 157 | + Debug.Assert(span.Length > endByteIndex); |
| 158 | + |
| 159 | + long count = 0; |
| 160 | + for (var i = 0; i < endByteIndex; i++) |
| 161 | + count += PopcountTable[span[i]]; |
| 162 | + |
| 163 | + var endBitOffset = (int)(length % 8); |
| 164 | + |
| 165 | + if (endBitOffset != 0) |
| 166 | + { |
| 167 | + var partialByte = span[endByteIndex]; |
| 168 | + for (var j = 0; j < endBitOffset; j++) |
| 169 | + { |
| 170 | + count += GetBit(partialByte, j) ? 0 : 1; |
| 171 | + } |
| 172 | + } |
| 173 | + |
| 174 | + return count; |
| 175 | + } |
| 176 | + } |
| 177 | +} |
0 commit comments