1: //------------------------------------------------------------------------------
2: // Copyright (c) Microsoft Corporation. All rights reserved.
3: //------------------------------------------------------------------------------
4:
5: using System;
6: using System.Collections.Generic;
7:
8: namespace Microsoft.Protocols.TestTools.StackSdk.RemoteDesktop.Rdprfx
9: {
10: /// <summary>
11: /// The RLGR decoder
12: /// </summary>
13: public class RLGRDecoder
14: {
15: // Constants used within the RLGR1/RLGR3 algorithm
16: const int KPMAX = 80; // max value for kp or krp
17: const int LSGR = 3; // shift count to convert kp to k
18: const int UP_GR = 4; // increase in kp after a zero run in RL mode
19: const int DN_GR = 6; // decrease in kp after a nonzero symbol in RL mode
20: const int UQ_GR = 3; // increase in kp after nonzero symbol in GR mode
21: const int DQ_GR = 3; // decrease in kp after zero symbol in GR mode
22:
23: List<short> decodedList;
24: byte[] encodedBytes = null;
25: //BitArray bitsToDecode = null;
26: int dataOffset = 0;
27:
28: /// <summary>
29: /// ALGR decode the input data.
30: /// </summary>
31: /// <param name="encodedData">The input data to be decoded.</param>
32: /// <param name="rlgrMode">The RLGR mode.</param>
33: /// <param name="lengthToDecode">The expected decoding size.</param>
34: /// <returns></returns>
35: public short[] Decode(byte[] encodedData, EntropyAlgorithm rlgrMode, int lengthToDecode)
36: {
37: encodedBytes = encodedData;
38: //bitsToDecode = new BitArray(encodedData);
39: dataOffset = 0;
40: decodedList = new List<short>();
41: this.RLGR_Decode(rlgrMode, lengthToDecode);
42: return decodedList.ToArray();
43: }
44:
45: //
46: // Gets (returns) the next nBits from the bitstream
47: // The layout of N bits in the bitstream with regard to a byte array is:
48: // [0..N] -> [0..7](MSB..LSB),[8..15](MSB..LSB) ...,
49: // where (MSB..LSB) denotes a byte.
50: //
51: uint GetBits(uint nBits)
52: {
53: uint output = 0;
54: int outOffset = (int)nBits - 1;
55: while (outOffset >= 0)
56: {
57: int bitOffset = dataOffset & 7;
58: int byteOffset = dataOffset >> 3;
59: //uint outBit = (uint)(bitsToDecode.Get(bitOffset++) ? 1:0);
60: uint outBit = (uint)((encodedBytes[byteOffset] & (byte)(1 << (7 - bitOffset))) == 0 ? 0 : 1);
61: output |= (outBit << outOffset--);
62: dataOffset++;
63: }
64: return output;
65: }
66:
67:
68: //
69: // From current output pointer, write "value", check and update *termsToDecode
70: //
71: void WriteValue(
72: int value,
73: ref int termsToDecode
74: )
75: {
76: if (termsToDecode > 0)
77: {
78: this.decodedList.Add((short)value);
79: termsToDecode--;
80: }
81: }
82:
83:
84: //
85: // From current output pointer, write next nZeroes terms with value 0;
86: // check and update *termsToDecode
87: //
88: void WriteZeroes(
89: uint nZeroes,
90: ref int termsToDecode
91: )
92: {
93: for (int i = 0; i < nZeroes && termsToDecode > 0; i++)
94: {
95: WriteValue(0, ref termsToDecode);
96: }
97: }
98:
99:
100: //
101: // Returns the least number of bits required to represent a given value
102: //
103: uint GetMinBits(
104: uint val// returns ceil(log2(val))
105: )
106: {
107: uint m1 = (uint)Math.Ceiling(Math.Log(val, 2));
108: while ((val >> (int)m1) != 0)
109: {
110: m1++;
111: }
112: return m1;
113: }
114:
115: //
116: // Converts from (2 * magnitude - sign) to integer
117: //
118: int GetIntFrom2MagSign(
119: uint twoMs
120: )
121: {
122:
123: uint sign = twoMs & 1;
124: int vl = (int)(twoMs + sign) / 2;
125: if (sign == 1) vl *= (-1); //<0
126: return vl;
127: }
128:
129: //
130: // Update the passed parameter and clamp it to the range [0,KPMAX]
131: // Return the value of parameter right-shifted by LSGR
132: //
133: int UpdateParam(
134: ref int param, // parameter to update
135: int deltaP // update delta
136: )
137: {
138: param += deltaP;// adjust parameter
139: if (param > KPMAX) param = KPMAX;// max clamp
140: if (param < 0) param = 0;// min clamp
141: return (param >> LSGR);
142: }
143:
144: //
145: // Outputs the Golomb/Rice encoding of a non-negative integer
146: //
147: uint GetGRCode(
148: ref int krp,
149: ref int kr
150: )
151: {
152: uint vk;
153: uint mag;
154:
155: // chew up/count leading 1s and escape 0
156: for (vk = 0; GetBits(1) == 1; )
157: {
158: vk++;
159: }
160:
161: // get next *kr bits, and combine with leading 1s
162: mag = (uint)((vk << kr) | GetBits((uint)(kr)));
163:
164:
165: // adjust kpr and kr based on vk
166: if (vk == 0)
167: {
168: kr = UpdateParam(ref krp, -2);
169: }
170: else if (vk != 1)// at 1, no change!
171: {
172: kr = UpdateParam(ref krp, (int)vk);
173: }
174:
175: return (mag);
176: }
177:
178: //
179: // Routine that reads and decodes stream of RLGR data
180: //
181: void RLGR_Decode(
182: EntropyAlgorithm rlgrMode, // RLGR1 || RLGR3
183: int lenToDecode
184: )
185: {
186: int termsToDecode = lenToDecode;
187: // initialize the parameters
188: int k = 1;
189: int kp = k << LSGR;
190: int kr = 1;
191: int krp = kr << LSGR;
192:
193: while (termsToDecode > 0)
194: {
195: int run;
196:
197: if (k != 0)
198: {
199: // RL MODE
200: while (GetBits(1) == 0)
201: {
202: if (termsToDecode > 0)
203: {
204: // we have an RL escape "0", which translates to a run (1<<k) of zeros
205: WriteZeroes((uint)(1 << k), ref termsToDecode);
206: k = UpdateParam(ref kp, UP_GR); // raise k and kp up because of zero run
207: }
208: else
209: {
210: break;
211: }
212: }
213:
214: if (termsToDecode > 0)
215: {
216: // next k bits will contain remaining run of zeros
217: run = (int)GetBits((uint)k);
218: WriteZeroes((uint)run, ref termsToDecode);
219: }
220:
221: if (termsToDecode > 0)
222: {
223: // get nonzero value, starting with sign bit and
224: // then GRCode for magnitude - 1
225: uint sign = GetBits(1);
226:
227: // magnitude - 1 was coded (because it was nonzero)
228: int mag = (int)GetGRCode(ref krp, ref kr) + 1;
229:
230: WriteValue(sign != 0 ? -mag : mag, ref termsToDecode);
231: k = UpdateParam(ref kp, -DN_GR); // lower k and kp because of nonzero term
232: }
233: }
234: else
235: {
236: // GR (GOLOMB-RICE) MODE
237: uint mag = GetGRCode(ref krp, ref kr); // values coded are 2*magnitude - sign
238:
239: if (rlgrMode == EntropyAlgorithm.CLW_ENTROPY_RLGR1)
240: {
241: if (mag == 0)
242: {
243: WriteValue(0, ref termsToDecode);
244: k = UpdateParam(ref kp, UQ_GR); // raise k and kp due to zero
245: }
246: else
247: {
248: WriteValue(GetIntFrom2MagSign(mag), ref termsToDecode);
249: k = UpdateParam(ref kp, -DQ_GR); // lower k and kp due to nonzero
250: }
251:
252: }
253: else // rlgrMode == RLGR3
254: {
255: // In GR mode FOR RLGR3, we have encoded the
256: // sum of two (2*mag - sign) values
257:
258: // maximum possible bits for first term
259: uint nIdx = GetMinBits(mag);
260:
261: // decode val1 is first term's (2*mag - sign) value
262: uint val1 = GetBits(nIdx);
263:
264: // val2 is second term's (2*mag - sign) value
265: uint val2 = mag - val1;
266:
267: if (val1 != 0 && val2 != 0)
268: {
269: // raise k and kp if both terms nonzero
270: k = UpdateParam(ref kp, -2 * DQ_GR);
271: }
272: else if (val1 == 0 && val2 == 0)
273: {
274: // lower k and kp if both terms zero
275: k = UpdateParam(ref kp, 2 * UQ_GR);
276: }
277:
278:
279: WriteValue(GetIntFrom2MagSign(val1), ref termsToDecode);
280: if (termsToDecode > 0)
281: {
282: WriteValue(GetIntFrom2MagSign(val2), ref termsToDecode);
283: }
284: }
285: }
286: }
287: }
288:
289: }
290: }