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// NibbleStream reader and writer.
5
6
7#ifndef _NIBBLESTREAM_H_
8#define _NIBBLESTREAM_H_
9
10#include "contract.h"
11#include "sigbuilder.h"
12
13typedef BYTE NIBBLE;
14
15//-----------------------------------------------------------------------------
16// Helpers for compression routines.
17//-----------------------------------------------------------------------------
18// This class allows variable-length compression of DWORDs.
19//
20// A value can be stored using one or more nibbles. 3 bits of a nibble are used
21// to store 3 bits of the value, and the top bit indicates if the following nibble
22// contains rest of the value. If the top bit is not set, then this
23// nibble is the last part of the value.
24// The higher bits of the value are written out first, and the lowest 3 bits
25// are written out last.
26//
27// In the encoded stream of bytes, the lower nibble of a byte is used before
28// the high nibble.
29//
30// A binary value ABCDEFGHI (where A is the highest bit) is encoded as
31// the follow two bytes : 1DEF1ABC XXXX0GHI
32//
33// Examples :
34// 0 => X0
35// 1 => X1
36//
37// 7 => X7
38// 8 => 09
39// 9 => 19
40//
41// 0x3F (63) => 7F
42// 0x40 (64) => F9 X0
43// 0x41 (65) => F9 X1
44//
45// 0x1FF (511) => FF X7
46// 0x200 (512) => 89 08
47// 0x201 (513) => 89 18
48
49class NibbleWriter
50{
51public:
52 NibbleWriter()
53 {
54 LIMITED_METHOD_CONTRACT;
55
56 m_fPending = false;
57 }
58
59 void Flush()
60 {
61 if (m_fPending)
62 m_SigBuilder.AppendByte(m_PendingNibble);
63 }
64
65 PVOID GetBlob(DWORD * pdwLength)
66 {
67 return m_SigBuilder.GetSignature(pdwLength);
68 }
69
70 DWORD GetBlobLength()
71 {
72 return m_SigBuilder.GetSignatureLength();
73 }
74
75//.............................................................................
76// Writer methods
77//.............................................................................
78
79
80 // Write a single nibble to the stream.
81 void WriteNibble(NIBBLE i)
82 {
83 CONTRACTL
84 {
85 THROWS;
86 GC_NOTRIGGER;
87 }
88 CONTRACTL_END;
89
90 _ASSERTE(i <= 0xF);
91
92 if (m_fPending)
93 {
94 // Use the high nibble after the low nibble is used
95 m_SigBuilder.AppendByte(m_PendingNibble | (i << 4));
96 m_fPending = false;
97 }
98 else
99 {
100 // Use the low nibble first
101 m_PendingNibble = i;
102 m_fPending = true;
103 }
104 }
105
106 // Write an unsigned int via variable length nibble encoding.
107 // We use the bit scheme:
108 // 0ABC (if 0 <= dw <= 0x7)
109 // 1ABC 0DEF (if 0 <= dw <= 0x7f)
110 // 1ABC 1DEF 0GHI (if 0 <= dw <= 0x7FF)
111 // etc..
112
113 void WriteEncodedU32(DWORD dw)
114 {
115 CONTRACTL
116 {
117 THROWS;
118 GC_NOTRIGGER;
119 }
120 CONTRACTL_END;
121
122 // Fast path for common small inputs
123 if (dw <= 63)
124 {
125 if (dw > 7)
126 {
127 WriteNibble((NIBBLE) ((dw >> 3) | 8));
128 }
129
130 WriteNibble((NIBBLE) (dw & 7));
131 return;
132 }
133
134 // Note we must write this out with the low terminating nibble (0ABC) last b/c the
135 // reader gets nibbles in the same order we write them.
136 int i = 0;
137 while ((dw >> i) > 7)
138 {
139 i+= 3;
140 }
141 while(i > 0)
142 {
143 WriteNibble((NIBBLE) ((dw >> i) & 0x7) | 0x8);
144 i -= 3;
145 }
146 WriteNibble((NIBBLE) dw & 0x7);
147 }
148
149 // Write a signed 32 bit value.
150 void WriteEncodedI32(int x)
151 {
152 CONTRACTL
153 {
154 THROWS;
155 GC_NOTRIGGER;
156 }
157 CONTRACTL_END;
158
159 DWORD dw = (x < 0) ? (((-x) << 1) + 1) : (x << 1);
160 WriteEncodedU32(dw);
161 };
162
163protected:
164 NIBBLE m_PendingNibble; // Pending value, not yet written out.
165 bool m_fPending;
166
167 // SigBuilder is a convenient helper class for writing out small blobs
168 SigBuilder m_SigBuilder;
169};
170
171//-----------------------------------------------------------------------------
172
173class NibbleReader
174{
175public:
176 NibbleReader(PTR_BYTE pBuffer, size_t size)
177 {
178 LIMITED_METHOD_CONTRACT;
179 SUPPORTS_DAC;
180 _ASSERTE(pBuffer != NULL);
181
182 m_pBuffer = pBuffer;
183 m_cBytes = size;
184 m_cNibble = 0;
185 }
186
187 // Get the index of the next Byte.
188 // This tells us how many bytes (rounding up to whole bytes) have been read.
189 // This is can be used to extract raw byte data that may be embedded on a byte boundary in the nibble stream.
190 size_t GetNextByteIndex()
191 {
192 LIMITED_METHOD_CONTRACT;
193 SUPPORTS_DAC;
194
195 return (m_cNibble + 1) / 2;
196 }
197
198 NIBBLE ReadNibble()
199 {
200 CONTRACTL
201 {
202 THROWS;
203 GC_NOTRIGGER;
204 SUPPORTS_DAC;
205 }
206 CONTRACTL_END;
207
208 NIBBLE i = 0;
209 // Bufer should have been allocated large enough to hold data.
210 if (!(m_cNibble / 2 < m_cBytes))
211 {
212 // We should never get here in a normal retail scenario.
213 // We could wind up here if somebody provided us invalid data (maybe by corrupting an ngenned image).
214 EX_THROW(HRException, (E_INVALIDARG));
215 }
216
217 BYTE p = m_pBuffer[m_cNibble / 2];
218 if ((m_cNibble & 1) == 0)
219 {
220 // Read the low nibble first
221 i = (NIBBLE) (p & 0xF);
222 }
223 else
224 {
225 // Read the high nibble after the low nibble has been read
226 i = (NIBBLE) (p >> 4) & 0xF;
227 }
228 m_cNibble++;
229
230 return i;
231 }
232
233 // Read an unsigned int that was encoded via variable length nibble encoding
234 // from NibbleWriter::WriteEncodedU32.
235 DWORD ReadEncodedU32()
236 {
237 CONTRACTL
238 {
239 THROWS;
240 GC_NOTRIGGER;
241 SUPPORTS_DAC;
242 }
243 CONTRACTL_END;
244
245 DWORD dw =0;
246
247#if defined(_DEBUG) || defined(DACCESS_COMPILE)
248 int dwCount = 0;
249#endif
250
251 // The encoding is variably lengthed, with the high-bit of every nibble indicating whether
252 // there is another nibble in the value. Each nibble contributes 3 bits to the value.
253 NIBBLE n;
254 do
255 {
256#if defined(_DEBUG) || defined(DACCESS_COMPILE)
257 // If we've already read 11 nibbles (with 3 bits of usable data each), then we
258 // should be done reading a 32-bit integer.
259 // Avoid working with corrupted data and potentially long loops by failing
260 if(dwCount > 11)
261 {
262 _ASSERTE_MSG(false, "Corrupt nibble stream - value exceeded 32-bits in size");
263#ifdef DACCESS_COMPILE
264 DacError(CORDBG_E_TARGET_INCONSISTENT);
265#endif
266 }
267 dwCount++;
268#endif
269
270 n = ReadNibble();
271 dw = (dw << 3) + (n & 0x7);
272 } while((n & 0x8) > 0);
273
274 return dw;
275 }
276
277 int ReadEncodedI32()
278 {
279 CONTRACTL
280 {
281 THROWS;
282 GC_NOTRIGGER;
283 SUPPORTS_DAC;
284 }
285 CONTRACTL_END;
286
287 DWORD dw = ReadEncodedU32();
288 int x = dw >> 1;
289 return (dw & 1) ? (-x) : (x);
290 }
291
292protected:
293 PTR_BYTE m_pBuffer;
294 size_t m_cBytes; // size of buffer.
295 size_t m_cNibble; // Which nibble are we at?
296};
297
298
299
300#endif // _NIBBLESTREAM_H_
301