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
6#ifndef _GCREFMAP_H_
7#define _GCREFMAP_H_
8
9#include "sigbuilder.h"
10
11//
12// The GCRef map is used to encode GC type of arguments for callsites. Logically, it is sequence <pos, token> where pos is
13// position of the reference in the stack frame and token is type of GC reference (one of GCREFMAP_XXX values).
14//
15// - The encoding always starts at the byte boundary. The high order bit of each byte is used to signal end of the encoding
16// stream. The last byte has the high order bit zero. It means that there are 7 useful bits in each byte.
17// - "pos" is always encoded as delta from previous pos.
18// - The basic encoding unit is two bits. Values 0, 1 and 2 are the common constructs (skip single slot, GC reference, interior
19// pointer). Value 3 means that extended encoding follows.
20// - The extended information is integer encoded in one or more four bit blocks. The high order bit of the four bit block is
21// used to signal the end.
22// - For x86, the encoding starts by size of the callee poped stack. The size is encoded using the same mechanism as above (two bit
23// basic encoding, with extended encoding for large values).
24
25/////////////////////////////////////////////////////////////////////////////////////
26// A utility class to encode sequence of GC summaries for a callsite
27
28class GCRefMapBuilder
29{
30 int m_PendingByte; // Pending value, not yet written out
31
32 int m_Bits; // Number of bits in pending byte. Note that the trailing zero bits are not written out,
33 // so this can be more than 7.
34
35 int m_Pos; // Current position
36
37 SigBuilder m_SigBuilder;
38
39 // Append single bit to the stream
40 void AppendBit(int bit)
41 {
42 if (bit != 0)
43 {
44 while (m_Bits >= 7)
45 {
46 m_SigBuilder.AppendByte((BYTE)(m_PendingByte | 0x80));
47 m_PendingByte = 0;
48 m_Bits -= 7;
49 }
50
51 m_PendingByte |= (1 << m_Bits);
52 }
53
54 m_Bits++;
55 }
56
57 void AppendTwoBit(int bits)
58 {
59 AppendBit(bits & 1);
60 AppendBit(bits >> 1);
61 }
62
63 void AppendInt(int val)
64 {
65 do {
66 AppendBit(val & 1);
67 AppendBit((val >> 1) & 1);
68 AppendBit((val >> 2) & 1);
69
70 val >>= 3;
71
72 AppendBit((val != 0) ? 1 : 0);
73 }
74 while (val != 0);
75 }
76
77public:
78 GCRefMapBuilder()
79 : m_PendingByte(0), m_Bits(0), m_Pos(0)
80 {
81 }
82
83#ifdef _TARGET_X86_
84 void WriteStackPop(int stackPop)
85 {
86 if (stackPop < 3)
87 {
88 AppendTwoBit(stackPop);
89 }
90 else
91 {
92 AppendTwoBit(3);
93 AppendInt(stackPop - 3);
94 }
95 }
96#endif
97
98 void WriteToken(int pos, int gcRefMapToken)
99 {
100 int posDelta = pos - m_Pos;
101 m_Pos = pos + 1;
102
103 if (posDelta != 0)
104 {
105 if (posDelta < 4)
106 {
107 // Skipping by one slot at a time for small deltas produces smaller encoding.
108 while (posDelta > 0)
109 {
110 AppendTwoBit(0);
111 posDelta--;
112 }
113 }
114 else
115 {
116 AppendTwoBit(3);
117 AppendInt((posDelta - 4) << 1);
118 }
119 }
120
121 if (gcRefMapToken < 3)
122 {
123 AppendTwoBit(gcRefMapToken);
124 }
125 else
126 {
127 AppendTwoBit(3);
128 AppendInt(((gcRefMapToken - 3) << 1) | 1);
129 }
130 }
131
132 void Flush()
133 {
134 if ((m_PendingByte & 0x7F) != 0 || m_Pos == 0)
135 m_SigBuilder.AppendByte((BYTE)(m_PendingByte & 0x7F));
136
137 m_PendingByte = 0;
138 m_Bits = 0;
139
140 m_Pos = 0;
141 }
142
143 PVOID GetBlob(DWORD * pdwLength)
144 {
145 return m_SigBuilder.GetSignature(pdwLength);
146 }
147
148 DWORD GetBlobLength()
149 {
150 return m_SigBuilder.GetSignatureLength();
151 }
152};
153
154/////////////////////////////////////////////////////////////////////////////////////
155// A utility class to decode a GC summary for a callsite
156
157class GCRefMapDecoder
158{
159 PTR_BYTE m_pCurrentByte;
160 int m_PendingByte;
161 int m_Pos;
162
163 FORCEINLINE int GetBit()
164 {
165 int x = m_PendingByte;
166 if (x & 0x80)
167 {
168 x = *m_pCurrentByte++;
169 x |= ((x & 0x80) << 7);
170 }
171 m_PendingByte = x >> 1;
172 return x & 1;
173 }
174
175 FORCEINLINE int GetTwoBit()
176 {
177 int result = GetBit();
178 result |= GetBit() << 1;
179 return result;
180 }
181
182 int GetInt()
183 {
184 int result = 0;
185
186 int bit = 0;
187 do {
188 result |= GetBit() << (bit++);
189 result |= GetBit() << (bit++);
190 result |= GetBit() << (bit++);
191 }
192 while (GetBit() != 0);
193
194 return result;
195 }
196
197public:
198 GCRefMapDecoder(PTR_BYTE pBlob)
199 : m_pCurrentByte(pBlob), m_PendingByte(0x80), m_Pos(0)
200 {
201 }
202
203 BOOL AtEnd()
204 {
205 return m_PendingByte == 0;
206 }
207
208#ifdef _TARGET_X86_
209 UINT ReadStackPop()
210 {
211 int x = GetTwoBit();
212
213 if (x == 3)
214 x = GetInt() + 3;
215
216 return x;
217 }
218#endif
219
220 int CurrentPos()
221 {
222 return m_Pos;
223 }
224
225 int ReadToken()
226 {
227 int val = GetTwoBit();
228 if (val == 3)
229 {
230 int ext = GetInt();
231 if ((ext & 1) == 0)
232 {
233 m_Pos += (ext >> 1) + 4;
234 return GCREFMAP_SKIP;
235 }
236 else
237 {
238 m_Pos++;
239 return (ext >> 1) + 3;
240 }
241 }
242 m_Pos++;
243 return val;
244 }
245};
246
247#endif // _GCREFMAP_H_
248