1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
|
using System;
using System.Numerics;
namespace Ryujinx.Horizon.Sdk.Ngc.Detail
{
class SbvSelect
{
private uint[] _array;
private BitVector32 _bv1;
private BitVector32 _bv2;
private SbvRank _sbvRank1;
private SbvRank _sbvRank2;
public bool Import(ref BinaryReader reader)
{
if (!reader.Read(out int arrayLength) ||
reader.AllocateAndReadArray(ref _array, arrayLength) != arrayLength)
{
return false;
}
_bv1 = new();
_bv2 = new();
_sbvRank1 = new();
_sbvRank2 = new();
return _bv1.Import(ref reader) &&
_bv2.Import(ref reader) &&
_sbvRank1.Import(ref reader, _bv1.BitLength) &&
_sbvRank2.Import(ref reader, _bv2.BitLength);
}
public void Build(ReadOnlySpan<uint> bitmap, int length)
{
int lengthInWords = (length + Set.BitsPerWord - 1) / Set.BitsPerWord;
int rank0Length = 0;
int rank1Length = 0;
if (lengthInWords != 0)
{
for (int index = 0; index < bitmap.Length; index++)
{
uint value = bitmap[index];
if (value != 0)
{
rank0Length++;
rank1Length += BitOperations.PopCount(value);
}
}
}
_bv1 = new(rank0Length);
_bv2 = new(rank1Length);
_array = new uint[rank0Length];
bool setSequence = false;
int arrayIndex = 0;
uint unsetCount = 0;
rank0Length = 0;
rank1Length = 0;
if (lengthInWords != 0)
{
for (int index = 0; index < bitmap.Length; index++)
{
uint value = bitmap[index];
if (value != 0)
{
if (!setSequence)
{
_bv1.TurnOn(rank0Length);
_array[arrayIndex++] = unsetCount;
setSequence = true;
}
_bv2.TurnOn(rank1Length);
rank0Length++;
rank1Length += BitOperations.PopCount(value);
}
else
{
unsetCount++;
setSequence = false;
}
}
}
_sbvRank1 = new(_bv1.Array, _bv1.BitLength);
_sbvRank2 = new(_bv2.Array, _bv2.BitLength);
}
public int Select(Set set, int index)
{
if (index < _bv2.BitLength)
{
int rank1PlainIndex = _sbvRank2.CalcRank1(index, _bv2.Array);
int rank0PlainIndex = _sbvRank1.CalcRank1(rank1PlainIndex - 1, _bv1.Array);
int value = (int)_array[rank0PlainIndex - 1] + (rank1PlainIndex - 1);
int baseBitIndex = 0;
if (value != 0)
{
baseBitIndex = value * 32;
int setBvLength = set.BitVector.BitLength;
int bitIndexBounded = baseBitIndex - 1;
if (bitIndexBounded >= setBvLength)
{
bitIndexBounded = setBvLength - 1;
}
index -= set.SbvRank.CalcRank1(bitIndexBounded, set.BitVector.Array);
}
return SelectPos(set.BitVector.Array[value], index) + baseBitIndex;
}
return -1;
}
public static int SelectPos(uint membershipBits, int bitIndex)
{
// Skips "bitIndex" set bits, and returns the bit index of the next set bit.
// If there is no set bit after skipping the specified amount, returns 32.
int bit;
int bitCount = bitIndex;
for (bit = 0; bit < sizeof(uint) * 8;)
{
if (((membershipBits >> bit) & 1) != 0)
{
if (bitCount-- == 0)
{
break;
}
bit++;
}
else
{
bit += BitOperations.TrailingZeroCount(membershipBits >> bit);
}
}
return bit;
}
}
}
|
