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// NativeFormatReader
7//
8// Utilities to read native data from images
9// ---------------------------------------------------------------------------
10
11#pragma once
12
13// To reduce differences between C# and C++ versions
14#define byte uint8_t
15#define uint uint32_t
16
17#define UInt16 uint16_t
18#define UInt32 uint32_t
19#define UInt64 uint64_t
20
21namespace NativeFormat
22{
23 class NativeReader;
24 typedef DPTR(NativeReader) PTR_NativeReader;
25
26 class NativeReader
27 {
28 PTR_BYTE _base;
29 uint _size;
30
31 public:
32 NativeReader()
33 {
34 _base = NULL;
35 _size = 0;
36 }
37
38 NativeReader(PTR_BYTE base_, uint size)
39 {
40 _base = base_;
41 _size = size;
42 }
43
44 void ThrowBadImageFormatException()
45 {
46 _ASSERTE(false);
47
48#ifndef DACCESS_COMPILE
49 // Failfast instead of throwing, to avoid violating NOTHROW contracts of callers
50 EEPOLICY_HANDLE_FATAL_ERROR(COR_E_BADIMAGEFORMAT);
51#endif
52 }
53
54 uint EnsureOffsetInRange(uint offset, uint lookAhead)
55 {
56 if ((int)offset < 0 || offset + lookAhead >= _size)
57 ThrowBadImageFormatException();
58 return offset;
59 }
60
61 byte ReadUInt8(uint offset)
62 {
63 if (offset >= _size)
64 ThrowBadImageFormatException();
65 return *(_base + offset); // Assumes little endian and unaligned access
66 }
67
68 UInt16 ReadUInt16(uint offset)
69 {
70 if ((int)offset < 0 || offset + 1 >= _size)
71 ThrowBadImageFormatException();
72 return *dac_cast<PTR_USHORT>(_base + offset); // Assumes little endian and unaligned access
73 }
74
75 UInt32 ReadUInt32(uint offset)
76 {
77 if ((int)offset < 0 || offset + 3 >= _size)
78 ThrowBadImageFormatException();
79 return *dac_cast<PTR_UINT32>(_base + offset); // Assumes little endian and unaligned access
80 }
81
82 uint DecodeUnsigned(uint offset, uint * pValue)
83 {
84 if (offset >= _size)
85 ThrowBadImageFormatException();
86
87 uint val = *(_base + offset);
88 if ((val & 1) == 0)
89 {
90 *pValue = (val >> 1);
91 offset += 1;
92 }
93 else
94 if ((val & 2) == 0)
95 {
96 if (offset + 1 >= _size)
97 ThrowBadImageFormatException();
98 *pValue = (val >> 2) |
99 (((uint)*(_base + offset + 1)) << 6);
100 offset += 2;
101 }
102 else
103 if ((val & 4) == 0)
104 {
105 if (offset + 2 >= _size)
106 ThrowBadImageFormatException();
107 *pValue = (val >> 3) |
108 (((uint)*(_base + offset + 1)) << 5) |
109 (((uint)*(_base + offset + 2)) << 13);
110 offset += 3;
111 }
112 else
113 if ((val & 8) == 0)
114 {
115 if (offset + 3 >= _size)
116 ThrowBadImageFormatException();
117 *pValue = (val >> 4) |
118 (((uint)*(_base + offset + 1)) << 4) |
119 (((uint)*(_base + offset + 2)) << 12) |
120 (((uint)*(_base + offset + 3)) << 20);
121 offset += 4;
122 }
123 else
124 if ((val & 16) == 0)
125 {
126 *pValue = ReadUInt32(offset + 1);
127 offset += 5;
128 }
129 else
130 {
131 ThrowBadImageFormatException();
132 }
133
134 return offset;
135 }
136
137 int DecodeSigned(uint offset, int * pValue)
138 {
139 if (offset >= _size)
140 ThrowBadImageFormatException();
141
142 int val = *(_base + offset);
143 if ((val & 1) == 0)
144 {
145 *pValue = val >> 1;
146 offset += 1;
147 }
148 else if ((val & 2) == 0)
149 {
150 if (offset + 1 >= _size)
151 ThrowBadImageFormatException();
152 *pValue = (val >> 2) |
153 (((int)*(_base + offset + 1)) << 6);
154 offset += 2;
155 }
156 else if ((val & 4) == 0)
157 {
158 if (offset + 2 >= _size)
159 ThrowBadImageFormatException();
160 *pValue = (val >> 3) |
161 (((int)*(_base + offset + 1)) << 5) |
162 (((int)*(_base + offset + 2)) << 13);
163 offset += 3;
164 }
165 else if ((val & 8) == 0)
166 {
167 if (offset + 3 >= _size)
168 ThrowBadImageFormatException();
169 *pValue = (val >> 4) |
170 (((int)*(_base + offset + 1)) << 4) |
171 (((int)*(_base + offset + 2)) << 12) |
172 (((int)*(_base + offset + 3)) << 20);
173 offset += 4;
174 }
175 else if ((val & 16) == 0)
176 {
177 *pValue = (int)ReadUInt32(offset + 1);
178 offset += 5;
179 }
180 else
181 {
182 ThrowBadImageFormatException();
183 }
184
185 return offset;
186 }
187
188#ifdef _MSC_VER
189#pragma warning(push)
190#pragma warning(disable : 4702) // Disable unreachable code warning
191#endif
192 uint SkipInteger(uint offset)
193 {
194 EnsureOffsetInRange(offset, 0);
195
196 PTR_BYTE data = (_base + offset);
197 if ((*data & 1) == 0)
198 {
199 return offset + 1;
200 }
201 else if ((*data & 2) == 0)
202 {
203 return offset + 2;
204 }
205 else if ((*data & 4) == 0)
206 {
207 return offset + 3;
208 }
209 else if ((*data & 8) == 0)
210 {
211 return offset + 4;
212 }
213 else if ((*data & 16) == 0)
214 {
215 return offset + 5;
216 }
217 else if ((*data & 32) == 0)
218 {
219 return offset + 9;
220 }
221 else
222 {
223 ThrowBadImageFormatException();
224 return offset;
225 }
226 }
227
228#ifndef DACCESS_COMPILE
229 const BYTE* GetBlob(uint offset)
230 {
231 EnsureOffsetInRange(offset, 0);
232 return _base + offset;
233 }
234#endif
235#ifdef _MSC_VER
236#pragma warning(pop)
237#endif
238 };
239
240 class NativeParser
241 {
242 PTR_NativeReader _pReader;
243 uint _offset;
244
245 public:
246 NativeParser()
247 : _pReader(PTR_NULL), _offset(0)
248 {
249 }
250
251 NativeParser(PTR_NativeReader pReader, uint offset)
252 {
253 _pReader = pReader;
254 _offset = offset;
255 }
256
257 NativeReader * GetNativeReader() { return _pReader; }
258
259 uint GetOffset() { return _offset; }
260 void SetOffset(uint value) { _offset = value; }
261
262 void ThrowBadImageFormatException()
263 {
264 _pReader->ThrowBadImageFormatException();
265 }
266
267 byte GetUInt8()
268 {
269 byte val = _pReader->ReadUInt8(_offset);
270 _offset += 1;
271 return val;
272 }
273
274 uint GetUnsigned()
275 {
276 uint value;
277 _offset = _pReader->DecodeUnsigned(_offset, &value);
278 return value;
279 }
280
281 int GetSigned()
282 {
283 int value;
284 _offset = _pReader->DecodeSigned(_offset, &value);
285 return value;
286 }
287
288 uint GetRelativeOffset()
289 {
290 uint pos = _offset;
291
292 int delta;
293 _offset = _pReader->DecodeSigned(_offset, &delta);
294
295 return pos + (uint)delta;
296 }
297
298#ifndef DACCESS_COMPILE
299 const BYTE * GetBlob()
300 {
301 return _pReader->GetBlob(_offset);
302 }
303#endif
304
305 void SkipInteger()
306 {
307 _offset = _pReader->SkipInteger(_offset);
308 }
309
310 NativeParser GetParserFromRelativeOffset()
311 {
312 return NativeParser(_pReader, GetRelativeOffset());
313 }
314 };
315
316 class NativeArray
317 {
318 PTR_NativeReader _pReader;
319 uint _baseOffset;
320 uint _nElements;
321 byte _entryIndexSize;
322
323 static const uint _blockSize = 16;
324
325 public:
326 NativeArray()
327 : _pReader(PTR_NULL), _nElements(0)
328 {
329 }
330
331 NativeArray(PTR_NativeReader pReader, uint offset)
332 : _pReader(pReader)
333 {
334 uint val;
335 _baseOffset = pReader->DecodeUnsigned(offset, &val);
336
337 _nElements = (val >> 2);
338 _entryIndexSize = (val & 3);
339 }
340
341 uint GetCount()
342 {
343 return _nElements;
344 }
345
346 bool TryGetAt(uint index, uint * pOffset)
347 {
348 if (index >= _nElements)
349 return false;
350
351 uint offset;
352 if (_entryIndexSize == 0)
353 {
354 offset = _pReader->ReadUInt8(_baseOffset + (index / _blockSize));
355 }
356 else if (_entryIndexSize == 1)
357 {
358 offset = _pReader->ReadUInt16(_baseOffset + 2 * (index / _blockSize));
359 }
360 else
361 {
362 offset = _pReader->ReadUInt32(_baseOffset + 4 * (index / _blockSize));
363 }
364 offset += _baseOffset;
365
366 for (uint bit = _blockSize >> 1; bit > 0; bit >>= 1)
367 {
368 uint val;
369 uint offset2 = _pReader->DecodeUnsigned(offset, &val);
370 if (index & bit)
371 {
372 if ((val & 2) != 0)
373 {
374 offset = offset + (val >> 2);
375 continue;
376 }
377 }
378 else
379 {
380 if ((val & 1) != 0)
381 {
382 offset = offset2;
383 continue;
384 }
385 }
386
387 // Not found
388 if ((val & 3) == 0)
389 {
390 // Matching special leaf node?
391 if ((val >> 2) == (index & (_blockSize - 1)))
392 {
393 offset = offset2;
394 break;
395 }
396 }
397 return false;
398 }
399
400 *pOffset = offset;
401 return true;
402 }
403 };
404
405 class NativeHashtable
406 {
407 PTR_NativeReader _pReader;
408 uint _baseOffset;
409 uint _bucketMask;
410 byte _entryIndexSize;
411
412 NativeParser GetParserForBucket(uint bucket, uint * pEndOffset)
413 {
414 uint start, end;
415
416 if (_entryIndexSize == 0)
417 {
418 uint bucketOffset = _baseOffset + bucket;
419 start = _pReader->ReadUInt8(bucketOffset);
420 end = _pReader->ReadUInt8(bucketOffset + 1);
421 }
422 else if (_entryIndexSize == 1)
423 {
424 uint bucketOffset = _baseOffset + 2 * bucket;
425 start = _pReader->ReadUInt16(bucketOffset);
426 end = _pReader->ReadUInt16(bucketOffset + 2);
427 }
428 else
429 {
430 uint bucketOffset = _baseOffset + 4 * bucket;
431 start = _pReader->ReadUInt32(bucketOffset);
432 end = _pReader->ReadUInt32(bucketOffset + 4);
433 }
434
435 *pEndOffset = end + _baseOffset;
436 return NativeParser(_pReader, _baseOffset + start);
437 }
438
439 public:
440 NativeHashtable() : _pReader(PTR_NULL), _baseOffset(0), _bucketMask(0), _entryIndexSize(0)
441 {
442 }
443
444 NativeHashtable(NativeParser& parser)
445 {
446 uint header = parser.GetUInt8();
447
448 _pReader = dac_cast<PTR_NativeReader>(parser.GetNativeReader());
449 _baseOffset = parser.GetOffset();
450
451 int numberOfBucketsShift = (int)(header >> 2);
452 if (numberOfBucketsShift > 31)
453 _pReader->ThrowBadImageFormatException();
454 _bucketMask = (uint)((1 << numberOfBucketsShift) - 1);
455
456 byte entryIndexSize = (byte)(header & 3);
457 if (entryIndexSize > 2)
458 _pReader->ThrowBadImageFormatException();
459 _entryIndexSize = entryIndexSize;
460 }
461
462 bool IsNull() { return _pReader == NULL; }
463
464 //
465 // The enumerator does not conform to the regular C# enumerator pattern to avoid paying
466 // its performance penalty (allocation, multiple calls per iteration)
467 //
468 class Enumerator
469 {
470 NativeParser _parser;
471 uint _endOffset;
472 byte _lowHashcode;
473
474 public:
475 Enumerator(NativeParser parser, uint endOffset, byte lowHashcode)
476 {
477 _parser = parser;
478 _endOffset = endOffset;
479 _lowHashcode = lowHashcode;
480 }
481
482 bool GetNext(NativeParser& entryParser)
483 {
484 while (_parser.GetOffset() < _endOffset)
485 {
486 byte lowHashcode = _parser.GetUInt8();
487
488 if (lowHashcode == _lowHashcode)
489 {
490 entryParser = _parser.GetParserFromRelativeOffset();
491 return true;
492 }
493
494 // The entries are sorted by hashcode within the bucket. It allows us to terminate the lookup prematurely.
495 if (lowHashcode > _lowHashcode)
496 {
497 _endOffset = _parser.GetOffset(); // Ensure that extra call to GetNext returns null parser again
498 break;
499 }
500
501 _parser.SkipInteger();
502 }
503
504 return false;
505 }
506 };
507
508 // The recommended code pattern to perform lookup is:
509 //
510 // NativeHashtable::Enumerator lookup = hashtable.Lookup(dwHashCode);
511 // NativeParser entryParser;
512 // while (lookup.GetNext(entryParser))
513 // {
514 // ... read entry using entryParser ...
515 // }
516 //
517 Enumerator Lookup(int hashcode)
518 {
519 uint endOffset;
520 uint bucket = ((uint)hashcode >> 8) & _bucketMask;
521 NativeParser parser = GetParserForBucket(bucket, &endOffset);
522
523 return Enumerator(parser, endOffset, (byte)hashcode);
524 }
525 };
526}
527