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
7#include "common.h"
8#include "decodemd.h"
9
10/*
11encoding patterns:
12 0 10x 110xxx 1110xxxxxxx 11110xxxxxxxxxxxxxxx 111110xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
13 0 1,2 3-10 11-138 139-32905 32906-big
14*/
15
16#define MAX_HEADER 5
17#define BASE_0 0
18#define BASE_1 1
19#define BASE_2 (0x2+0x1)
20#define BASE_3 (0x8+0x2+0x1)
21#define BASE_4 (0x80+0x8+0x2+0x1)
22#define BASE_5 (0x8000+0x80+0x8+0x2+0x1)
23#define BASE_6 (0x80000000+0x8000+0x80+0x8+0x2+0x1)
24const unsigned decode_base[MAX_HEADER+2] = {BASE_0, BASE_1, BASE_2, BASE_3, BASE_4, BASE_5, BASE_6};
25#define BIT_LENGTH_0 0
26#define BIT_LENGTH_1 1
27#define BIT_LENGTH_2 3
28#define BIT_LENGTH_3 7
29#define BIT_LENGTH_4 15
30#define BIT_LENGTH_5 31
31#define BIT_LENGTH_6 63
32const unsigned decode_bitlength[MAX_HEADER+2] =
33 {
34 BIT_LENGTH_0,
35 BIT_LENGTH_1,
36 BIT_LENGTH_2,
37 BIT_LENGTH_3,
38 BIT_LENGTH_4,
39 BIT_LENGTH_5,
40 BIT_LENGTH_6
41 };
42
43#define END_DECODED BASE_3
44const BYTE decoded_end[1] = {END_DECODED };
45const BYTE decoded_0_0_0_0[5] = {0,0,0,0,END_DECODED };
46const BYTE decoded_0_1[3] = {0,1,END_DECODED };
47const BYTE decoded_0_2[3] = {0,2,END_DECODED };
48const BYTE decoded_1_0[3] = {1,0,END_DECODED };
49const BYTE decoded_2_0[3] = {2,0,END_DECODED };
50const BYTE decoded_1_0_0[4] = {1,0,0,END_DECODED };
51const BYTE decoded_2_0_0[4] = {2,0,0,END_DECODED };
52#define decoded_0 &decoded_0_0_0_0[3]
53#define decoded_0_0 &decoded_0_0_0_0[2]
54#define decoded_0_0_0 &decoded_0_0_0_0[1]
55#define decoded_1 &decoded_0_1[1]
56#define decoded_2 &decoded_0_2[1]
57const BYTE decoded_3[2] = {3, END_DECODED };
58const BYTE decoded_4[2] = {4, END_DECODED };
59const BYTE decoded_5[2] = {5, END_DECODED };
60const BYTE decoded_6[2] = {6, END_DECODED };
61const BYTE decoded_7[2] = {7, END_DECODED };
62const BYTE decoded_8[2] = {8, END_DECODED };
63const BYTE decoded_9[2] = {9, END_DECODED };
64const BYTE decoded_10[2] = {10, END_DECODED };
65
66#define INBITS(s) (s > MAX_HEADER)
67#define INHEADER(s) (s <= MAX_HEADER)
68#define PARTIALBITS(s) ((s>>8)&0xFF)
69#define NUMBERGOTTEN(s) (((s)>>16)&0xFF)
70#define HEADER(s) ((s>>24)&0xFF)
71#define DECODING_HEADER(n) n
72#define DOING_BITS (MAX_HEADER+1)
73#define DECODING_BITS(partial, got, header) (DOING_BITS+(partial<<8)+(got<<16)+(header<<24))
74#define DECODING_ERROR ((unsigned) -1)
75#define MASK(len) (~(~0u <<len))
76#define MASK64(len) ((~((~((unsigned __int64)0))<<len)))
77#define BITS_PER_BYTE (sizeof(BYTE)*8)
78
79const Decoder::Decode emptyDecode = {decoded_end, DECODING_HEADER(0)};
80
81const Decoder::Decode transition[6][16] =
82{
83 //header(0)
84 {
85 { decoded_0_0_0_0, DECODING_HEADER(0) }, // 0000
86 { decoded_0_0_0, DECODING_HEADER(1) }, // 0001
87 { decoded_0_0, DECODING_BITS(0,0,1) }, // 0010
88 { decoded_0_0, DECODING_HEADER(2) }, // 0011
89 { decoded_0_1, DECODING_HEADER(0) }, // 0100
90 { decoded_0_2, DECODING_HEADER(0) }, // 0101
91 { decoded_0, DECODING_BITS(0,0,2) }, // 0110
92 { decoded_0, DECODING_HEADER(3) }, // 0111
93 { decoded_1_0, DECODING_HEADER(0) }, // 1000
94 { decoded_1, DECODING_HEADER(1) }, // 1001
95 { decoded_2_0, DECODING_HEADER(0) }, // 1010
96 { decoded_2, DECODING_HEADER(1) }, // 1011
97 { decoded_end, DECODING_BITS(0,1,2) }, // 1100
98 { decoded_end, DECODING_BITS(1,1,2) }, // 1101
99 { decoded_end, DECODING_BITS(0,0,3) }, // 1110
100 { decoded_end, DECODING_HEADER(4) }, // 1111
101 },
102 //header(1)
103 {
104 { decoded_1_0_0, DECODING_HEADER(0) }, // 1 0000
105 { decoded_1_0, DECODING_HEADER(1) }, // 1 0001
106 { decoded_1, DECODING_BITS(0,0,1) }, // 1 0010
107 { decoded_1, DECODING_HEADER(2) }, // 1 0011
108 { decoded_2_0_0, DECODING_HEADER(0) }, // 1 0100
109 { decoded_2_0, DECODING_HEADER(1) }, // 1 0101
110 { decoded_2, DECODING_BITS(0,0,1) }, // 1 0110
111 { decoded_2, DECODING_HEADER(2) }, // 1 0111
112 { decoded_end, DECODING_BITS(0,2,2) }, // 1 1000
113 { decoded_end, DECODING_BITS(1,2,2) }, // 1 1001
114 { decoded_end, DECODING_BITS(2,2,2) }, // 1 1010
115 { decoded_end, DECODING_BITS(3,2,2) }, // 1 1011
116 { decoded_end, DECODING_BITS(0,1,3) }, // 1 1100
117 { decoded_end, DECODING_BITS(1,1,3) }, // 1 1101
118 { decoded_end, DECODING_BITS(0,0,4) }, // 1 1110
119 { decoded_end, DECODING_HEADER(5) }, // 1 1111
120 },
121 //header(2)
122 {
123 { decoded_3, DECODING_HEADER(0) }, // 11 0000
124 { decoded_4, DECODING_HEADER(0) }, // 11 0001
125 { decoded_5, DECODING_HEADER(0) }, // 11 0010
126 { decoded_6, DECODING_HEADER(0) }, // 11 0011
127 { decoded_7, DECODING_HEADER(0) }, // 11 0100
128 { decoded_8, DECODING_HEADER(0) }, // 11 0101
129 { decoded_9, DECODING_HEADER(0) }, // 11 0110
130 { decoded_10, DECODING_HEADER(0) }, // 11 0111
131 { decoded_end, DECODING_BITS(0,2,3) }, // 11 1000
132 { decoded_end, DECODING_BITS(1,2,3) }, // 11 1001
133 { decoded_end, DECODING_BITS(2,2,3) }, // 11 1010
134 { decoded_end, DECODING_BITS(3,2,3) }, // 11 1011
135 { decoded_end, DECODING_BITS(0,1,4) }, // 11 1100
136 { decoded_end, DECODING_BITS(1,1,4) }, // 11 1101
137 { decoded_end, DECODING_BITS(0,0,5) }, // 11 1110
138 { decoded_end, DECODING_ERROR }, // 11 1111
139 },
140 //header(3)
141 {
142 { decoded_end, DECODING_BITS(0,3,3) },
143 { decoded_end, DECODING_BITS(1,3,3) },
144 { decoded_end, DECODING_BITS(2,3,3) },
145 { decoded_end, DECODING_BITS(3,3,3) },
146 { decoded_end, DECODING_BITS(4,3,3) },
147 { decoded_end, DECODING_BITS(5,3,3) },
148 { decoded_end, DECODING_BITS(6,3,3) },
149 { decoded_end, DECODING_BITS(7,3,3) },
150 { decoded_end, DECODING_BITS(0,2,4) },
151 { decoded_end, DECODING_BITS(1,2,4) },
152 { decoded_end, DECODING_BITS(2,2,4) },
153 { decoded_end, DECODING_BITS(3,2,4) },
154 { decoded_end, DECODING_BITS(0,1,5) },
155 { decoded_end, DECODING_BITS(1,1,5) },
156 { decoded_end, DECODING_ERROR },
157 { decoded_end, DECODING_ERROR },
158 },
159 //header(4)
160 {
161 { decoded_end, DECODING_BITS(0,3,4) },
162 { decoded_end, DECODING_BITS(1,3,4) },
163 { decoded_end, DECODING_BITS(2,3,4) },
164 { decoded_end, DECODING_BITS(3,3,4) },
165 { decoded_end, DECODING_BITS(4,3,4) },
166 { decoded_end, DECODING_BITS(5,3,4) },
167 { decoded_end, DECODING_BITS(6,3,4) },
168 { decoded_end, DECODING_BITS(7,3,4) },
169 { decoded_end, DECODING_BITS(0,2,5) },
170 { decoded_end, DECODING_BITS(1,2,5) },
171 { decoded_end, DECODING_BITS(2,2,5) },
172 { decoded_end, DECODING_BITS(3,2,5) },
173 { decoded_end, DECODING_ERROR },
174 { decoded_end, DECODING_ERROR },
175 { decoded_end, DECODING_ERROR },
176 { decoded_end, DECODING_ERROR },
177 },
178 //header(5)
179 {
180 { decoded_end, DECODING_BITS(0,3,5) },
181 { decoded_end, DECODING_BITS(1,3,5) },
182 { decoded_end, DECODING_BITS(2,3,5) },
183 { decoded_end, DECODING_BITS(3,3,5) },
184 { decoded_end, DECODING_BITS(4,3,5) },
185 { decoded_end, DECODING_BITS(5,3,5) },
186 { decoded_end, DECODING_BITS(6,3,5) },
187 { decoded_end, DECODING_BITS(7,3,5) },
188 { decoded_end, DECODING_ERROR },
189 { decoded_end, DECODING_ERROR },
190 { decoded_end, DECODING_ERROR },
191 { decoded_end, DECODING_ERROR },
192 { decoded_end, DECODING_ERROR },
193 { decoded_end, DECODING_ERROR },
194 { decoded_end, DECODING_ERROR },
195 { decoded_end, DECODING_ERROR },
196 }
197};
198
199// --------------------------------------------------------
200void Decoder::Nibbles::SetContents( PTR_BYTE bytes)
201{
202 STATIC_CONTRACT_LEAF;
203
204 next = 2;
205 data = bytes;
206}
207
208// --------------------------------------------------------
209BYTE Decoder::Nibbles::Next()
210{
211 STATIC_CONTRACT_NOTHROW;
212 STATIC_CONTRACT_GC_NOTRIGGER;
213 STATIC_CONTRACT_FORBID_FAULT;
214 STATIC_CONTRACT_SUPPORTS_DAC;
215
216 BYTE result = Read();
217 next++;
218 return result;
219}
220
221// --------------------------------------------------------
222BYTE Decoder::Nibbles::Read()
223{
224 STATIC_CONTRACT_LEAF;
225 STATIC_CONTRACT_SUPPORTS_DAC;
226
227 if (next >= 2)
228 {
229 BYTE d = *data++;
230 next = 0;
231 nibbles[1] = d & 0xF;
232 nibbles[0] = d>>4;
233 }
234 return nibbles[next];
235}
236
237// --------------------------------------------------------
238unsigned Decoder::Nibbles::Bits(unsigned number)
239{
240 STATIC_CONTRACT_NOTHROW;
241 STATIC_CONTRACT_GC_NOTRIGGER;
242 STATIC_CONTRACT_FORBID_FAULT;
243 STATIC_CONTRACT_SUPPORTS_DAC;
244
245 unsigned n = number;
246 unsigned result = 0;
247 while (n >= 4 )
248 {
249 result = (result<<4) | Next();
250 n -= 4;
251 }
252 if (n > 0)
253 {
254 BYTE last = Read();
255 result = (result<<n) | (last>>(4-n));
256 nibbles[next] &= (0xF>>n);
257 }
258 return result;
259}
260
261// --------------------------------------------------------
262void Decoder::Init(PTR_BYTE bytes)
263{
264 STATIC_CONTRACT_NOTHROW;
265 STATIC_CONTRACT_GC_NOTRIGGER;
266 STATIC_CONTRACT_FORBID_FAULT;
267 STATIC_CONTRACT_SUPPORTS_DAC_HOST_ONLY;
268
269 state = emptyDecode;
270 data.SetContents(bytes);
271// signedNumbers = FALSE;
272}
273
274// --------------------------------------------------------
275Decoder::Decoder(PTR_BYTE bytes)
276{
277 STATIC_CONTRACT_WRAPPER;
278 Init(bytes);
279}
280
281// --------------------------------------------------------
282Decoder::Decoder()
283{
284 STATIC_CONTRACT_LEAF;
285 STATIC_CONTRACT_SUPPORTS_DAC;
286}
287
288// --------------------------------------------------------
289unsigned Decoder::Next()
290{
291 STATIC_CONTRACT_NOTHROW;
292 STATIC_CONTRACT_GC_NOTRIGGER;
293 STATIC_CONTRACT_FORBID_FAULT;
294 STATIC_CONTRACT_SUPPORTS_DAC;
295
296tryagain:
297 unsigned result = *state.decoded;
298 if (result != END_DECODED)
299 {
300 state.decoded++;
301 return result;
302 }
303 if (INHEADER(state.next))
304 {
305 state = transition[state.next][data.Next()];
306 goto tryagain;
307 }
308 //must be getting bits
309 _ASSERTE(INBITS(state.next));
310 unsigned index = HEADER(state.next);
311 unsigned bitsNeeded = decode_bitlength[index]-NUMBERGOTTEN(state.next);
312 result = (PARTIALBITS(state.next)<<bitsNeeded)+data.Bits(bitsNeeded)+decode_base[index];
313 state = emptyDecode;
314 unsigned skip = bitsNeeded % 4; // this works since we are always 4-bit aligned
315 if (skip > 0)
316 {
317#ifdef _PREFAST_
318#pragma warning(push)
319#pragma warning(disable:26000) // "Suppress PREFast warning about index overflow"
320#endif
321 // state.next is always 0, because we did "state = emptyDecode;" above
322 state = transition[state.next][data.Next()];
323#ifdef _PREFAST_
324#pragma warning(pop)
325#endif
326 state.decoded += skip;
327 }
328 return result;
329}
330
331// --------------------------------------------------------
332signed Decoder::NextSigned()
333{
334 STATIC_CONTRACT_NOTHROW;
335 STATIC_CONTRACT_GC_NOTRIGGER;
336 STATIC_CONTRACT_FORBID_FAULT;
337 STATIC_CONTRACT_SUPPORTS_DAC;
338
339 signed v = (signed) Next();
340 return (v & 1) ? (v+1)>>1 : -(v>>1);
341}
342
343// --------------------------------------------------------
344PTR_BYTE Decoder::End()
345{
346 STATIC_CONTRACT_LEAF;
347 STATIC_CONTRACT_SUPPORTS_DAC;
348
349 return data.data;
350}
351
352// --------------------------------------------------------
353Encoder::Encoder(BYTE *buffer) : encoding(0), unusedBits(BITS_PER_BYTE),
354 done(FALSE), signedNumbers(FALSE), index(0)
355{
356 STATIC_CONTRACT_LEAF;
357
358 this->buffer = buffer;
359}
360
361// --------------------------------------------------------
362void Encoder::ContainsNegatives(BOOL b)
363{
364 STATIC_CONTRACT_LEAF;
365
366 signedNumbers = b;
367}
368void Encoder::EncodeSigned(signed value)
369{
370 STATIC_CONTRACT_NOTHROW;
371 STATIC_CONTRACT_GC_NOTRIGGER;
372 STATIC_CONTRACT_FORBID_FAULT;
373
374
375 if (!signedNumbers)
376 {
377 _ASSERTE(value>=0);
378 Encode(value);
379 return;
380 }
381 unsigned v = (value <= 0 ) ? (-value)<<1 : (value<<1)-1;
382 Encode(v);
383}
384
385// --------------------------------------------------------
386void Encoder::Encode(unsigned value)
387{
388 STATIC_CONTRACT_NOTHROW;
389 STATIC_CONTRACT_GC_NOTRIGGER;
390 STATIC_CONTRACT_FORBID_FAULT;
391
392
393 if (value < BASE_1)
394 {
395 Add(0, 1);
396 return;
397 }
398 if (value < BASE_2)
399 {
400 Add((0x1<<(1+BIT_LENGTH_1))+(value-BASE_1), 2+BIT_LENGTH_1);
401 return;
402 }
403 if (value < BASE_3)
404 {
405 Add((0x3<<(1+BIT_LENGTH_2))+(value-BASE_2), 3+BIT_LENGTH_2);
406 return;
407 }
408 if (value < BASE_4)
409 {
410 Add((0x7<<(1+BIT_LENGTH_3))+(value-BASE_3), 4+BIT_LENGTH_3);
411 return;
412 }
413 if (value < BASE_5)
414 {
415 Add((0xf<<(1+BIT_LENGTH_4))+(value-BASE_4), 5+BIT_LENGTH_4);
416 return;
417 }
418 if (value < BASE_6)
419 {
420 unsigned __int64 value64 = (unsigned __int64) value;
421 Add64((((unsigned __int64)0x1f)<<(1+BIT_LENGTH_5))+(value64-BASE_5), 6+BIT_LENGTH_5);
422 return;
423 }
424 _ASSERTE(!"Too big");
425}
426
427// --------------------------------------------------------
428void Encoder::Encode(signed value, BOOL isSigned)
429{
430 STATIC_CONTRACT_NOTHROW;
431 STATIC_CONTRACT_GC_NOTRIGGER;
432 STATIC_CONTRACT_FORBID_FAULT;
433
434 if (isSigned)
435 EncodeSigned(value);
436 else
437 {
438 _ASSERTE(((signed)((unsigned) value)) == value);
439 Encode((unsigned) value);
440 }
441}
442
443// --------------------------------------------------------
444void Encoder::Add(unsigned value, unsigned length)
445{
446 STATIC_CONTRACT_NOTHROW;
447 STATIC_CONTRACT_GC_NOTRIGGER;
448 STATIC_CONTRACT_FORBID_FAULT;
449
450 _ASSERTE(!done);
451 while (length >= unusedBits)
452 {
453 length -= unusedBits;
454 encoding = (encoding<<unusedBits)+static_cast<BYTE>(value>>(length));
455 value = (value & MASK(length));
456 if (buffer) buffer[index++] = encoding;
457 else index++;
458 encoding = 0;
459 unusedBits = BITS_PER_BYTE;
460 }
461 encoding = (encoding<<length)+static_cast<BYTE>(value);
462 unusedBits -= length;
463}
464
465// --------------------------------------------------------
466void Encoder::Add64(unsigned __int64 value, unsigned length)
467{
468 STATIC_CONTRACT_NOTHROW;
469 STATIC_CONTRACT_GC_NOTRIGGER;
470 STATIC_CONTRACT_FORBID_FAULT;
471
472 _ASSERTE(!done);
473 while (length >= unusedBits)
474 {
475 length -= unusedBits;
476 encoding = (encoding<<unusedBits)+((BYTE)(value>>(length)));
477 value = (value & MASK64(length));
478 if (buffer) buffer[index++] = encoding;
479 else index++;
480 encoding = 0;
481 unusedBits = BITS_PER_BYTE;
482 }
483 encoding = (encoding<<length)+(BYTE)value;
484 unusedBits -= length;
485}
486
487// --------------------------------------------------------
488void Encoder::Done()
489{
490 LIMITED_METHOD_CONTRACT;
491
492 done = TRUE;
493 if (unusedBits == BITS_PER_BYTE) return;
494 encoding = (encoding<<unusedBits);
495 if (buffer) buffer[index++] = encoding;
496 else index++;
497}
498
499// --------------------------------------------------------
500unsigned Encoder::Contents(BYTE** contents)
501{
502 STATIC_CONTRACT_LEAF;
503
504 _ASSERTE(done && buffer && contents);
505 *contents = buffer;
506 return index;
507}
508
509// --------------------------------------------------------
510unsigned Encoder::Length()
511{
512 STATIC_CONTRACT_LEAF;
513
514 _ASSERTE(done);
515 return index;
516}
517
518