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 encoder
12: /// </summary>
13: public class RLGREncoder
14: {
15: // Constants used within the RLGR1/RLGR3 algorithm
16:
17: const int KPMAX = 80; // max value for kp or krp
18: const int LSGR = 3; // shift count to convert kp to k
19: const int UP_GR = 4; // increase in kp after a zero run in RL mode
20: const int DN_GR = 6; // decrease in kp after a nonzero symbol in RL mode
21: const int UQ_GR = 3; // increase in kp after nonzero symbol in GR mode
22: const int DQ_GR = 3; // decrease in kp after zero symbol in GR mode
23:
24: short[] inputData;
25: int nextInputIdx;
26: int bufferOffset = 0;
27: byte[] pBuffer;
28:
29: /// <summary>
30: /// Do ALGR encode to the input data.
31: /// </summary>
32: /// <param name="inputArr">Input data to be encoded.</param>
33: /// <param name="mode">The ALGR mode, can be RLGR1 or RLGR3.</param>
34: /// <returns>The encoded data.</returns>
35: public byte[] Encode(short[] inputArr, EntropyAlgorithm mode)
36: {
37: inputData = inputArr;
38: nextInputIdx = 0;
39: bufferOffset = 0; //offset&0xFFFFFFF8 = byte offset, offset&0x7 = bit offset
40: pBuffer = new byte[inputArr.Length];
41:
42: RLGR_Encode(mode);
43: int numbytes = bufferOffset >> 3;
44: int bitOffset = bufferOffset & 7;
45: if (bitOffset != 0) numbytes++;
46:
47: byte[] encodedBytes = new byte[numbytes];
48: Array.Copy(pBuffer, encodedBytes, encodedBytes.Length);
49: return encodedBytes;
50: }
51:
52: //
53: // Returns the next coefficient (a signed int) to encode, from the input stream
54: //
55: int GetNextInput()
56: {
57: return (int)inputData[nextInputIdx++];
58: }
59:
60: bool hasMoreData()
61: {
62: return (nextInputIdx <= inputData.Length - 1);
63: }
64:
65: //
66: // Emit bitPattern to the output bitstream.
67: // The bitPattern value represents a bit sequence that is generated by shifting
68: // new bits in from the right. If we take the binary representation of bitPattern,
69: // with N(numBits-1) being the leftmost bit position and 0 being the rightmost bit position,
70: // the mapping of bitPattern to the output bytes is as follows:
71: //
72: // bitPattern[N..0] -> byte[MSB..LSB] .. byte[MSB..LSB]
73: //
74: public void OutputBits(
75: int numBits, // number of bits in bitPattern
76: int bitPattern // bit pattern
77: )
78: {
79: int patternOffset = numBits - 1;
80:
81: while (patternOffset >= 0)
82: {
83: int bit = ((bitPattern & (1 << patternOffset)) != 0) ? 1 : 0;
84: OutputBit(1, bit);
85: patternOffset--;
86: }
87: }
88:
89: //
90: // Emit a bit (0 or 1), count number of times, to the output bitstream
91: //
92: void OutputBit(
93: int count, // number of times to emit the bit
94: int bit // 0 or 1
95: )
96: {
97: if (count == 0) return;
98:
99: for (int i = 0; i < count; i++)
100: {
101: int bitOffset = bufferOffset & 7;
102: int bufferBoundary = bufferOffset >> 3;
103: if (bit != 0) // bit 1
104: {
105: pBuffer[bufferBoundary] |= (byte)(1 << (7 - bitOffset));
106: }
107: else
108: {
109: pBuffer[bufferBoundary] &= (byte)(0xFF - ((byte)(1 << (7 - bitOffset))));
110: }
111: bufferOffset++;
112: }
113: }
114:
115: //
116: // Returns the least number of bits required to represent a given value
117: //
118: uint GetMinBits(
119: int val // returns ceil(log2(val))
120: )
121: {
122: uint m1 = (uint)Math.Ceiling(Math.Log(val, 2));
123: while ((val >> (int)m1) != 0)
124: {
125: m1++;
126: }
127: return m1;
128: }
129:
130: //
131: // Converts the input value to (2 * abs(input) - sign(input)),
132: // where sign(input) = (input < 0 ? 1 : 0) and returns it
133: //
134: uint Get2MagSign(
135: int input // input value
136: )
137: {
138: uint output = (uint)(2 * Math.Abs(input));
139: if (input < 0) output -= 1;
140: return output;
141: }
142:
143:
144: //
145: // Update the passed parameter and clamp it to the range [0,KPMAX]
146: // Return the value of parameter right-shifted by LSGR
147: //
148: int UpdateParam(
149: ref int param, // parameter to update
150: int deltaP // update delta
151: )
152: {
153: param += deltaP;
154: if (param > KPMAX) param = KPMAX;
155: if (param < 0) param = 0;
156: return (param >> LSGR);
157: }
158:
159:
160: //
161: // Outputs the Golomb/Rice encoding of a non-negative integer
162: //
163: void CodeGR(
164: ref int krp, // GR parameter, used and updated based on the input value
165: uint val // input non-negative value to be encoded
166: )
167: {
168: int kr = krp >> LSGR;
169:
170: // unary part of GR code
171:
172: uint vk = val >> kr;
173: OutputBit((int)vk, 1);
174: OutputBit(1, 0);
175:
176: // remainder part of GR code, if needed
177: if (kr != 0)
178: {
179: OutputBits(kr, (int)(val & ((1 << kr) - 1)));
180: }
181:
182: // update krp, only if it is not equal to 1
183: if (vk == 0)
184: {
185: UpdateParam(ref krp, -2);
186: }
187: else if (vk > 1)
188: {
189: UpdateParam(ref krp, (int)vk);
190: }
191: }
192:
193:
194: //
195: // Routine that outputs a stream of RLGR1/RLGR3-encoded bits
196: //
197: void RLGR_Encode(
198: EntropyAlgorithm rlgrMode // RLGR1 || RLGR3
199: )
200: {
201: // initialize the parameters
202: int k = 1;
203: int kp = 1 << LSGR;
204: //int kr = 1;
205: int krp = 1 << LSGR;
206:
207: // process all the input coefficients
208: while (hasMoreData())
209: {
210: int input;
211:
212: if (k != 0)
213: {
214: // RUN-LENGTH MODE
215:
216: // collect the run of zeros in the input stream
217: int numZeros = 0;
218: while ((input = GetNextInput()) == 0)
219: {
220: ++numZeros;
221: if (!hasMoreData()) break;
222: }
223:
224: // emit output zebros
225: int runmax = 1 << k;
226: while (numZeros >= runmax)
227: {
228: OutputBit(1, 0); // output a zero bit
229: numZeros -= runmax;
230: k = UpdateParam(ref kp, UP_GR); // update kp, k
231: runmax = 1 << k;
232: }
233:
234: // output a 1 to terminate runs
235: OutputBit(1, 1);
236:
237: // output the remaining run length using k bits
238: OutputBits(k, numZeros);
239:
240: if (input != 0)
241: {
242: // encode the nonzero value using GR coding
243:
244: int mag = Math.Abs(input); // absolute value of input coefficient
245: int sign = (input < 0 ? 1 : 0); // sign of input coefficient
246:
247: OutputBit(1, sign); // output the sign bit
248: CodeGR(ref krp, (uint)(mag - 1)); // output GR code for (mag - 1)
249:
250: k = UpdateParam(ref kp, -DN_GR);
251: }
252: }
253: else
254: {
255: // GOLOMB-RICE MODE
256:
257: if (rlgrMode == EntropyAlgorithm.CLW_ENTROPY_RLGR1)
258: {
259: // RLGR1 variant
260:
261: // convert input to (2*magnitude - sign), encode using GR code
262: uint twoMs = Get2MagSign(GetNextInput());
263: CodeGR(ref krp, twoMs);
264:
265: // update k, kp
266: if (twoMs == 0)
267: {
268: k = UpdateParam(ref kp, UQ_GR);
269: }
270: else
271: {
272: k = UpdateParam(ref kp, -DQ_GR);
273: }
274: }
275: else // rlgrMode == RLGR3
276: {
277: // RLGR3 variant
278:
279: // convert the next two input values to (2*magnitude - sign) and
280: // encode their sum using GR code
281:
282: uint twoMs1 = Get2MagSign(GetNextInput());
283: uint twoMs2 = 0;
284: if (hasMoreData())
285: {
286: twoMs2 = Get2MagSign(GetNextInput());
287: }
288:
289: uint sum2Ms = twoMs1 + twoMs2;
290:
291: CodeGR(ref krp, sum2Ms);
292:
293: // encode binary representation of the first input (twoMs1).
294: OutputBits((int)GetMinBits((int)sum2Ms), (int)twoMs1);
295:
296: // update k,kp for the two input values
297: if (twoMs1 != 0 && twoMs2 != 0)
298: {
299: k = UpdateParam(ref kp, -2 * DQ_GR);
300: }
301: else if (twoMs1 == 0 && twoMs2 == 0)
302: {
303: k = UpdateParam(ref kp, 2 * UQ_GR);
304: }
305: }
306: }
307: }
308: }
309:
310: }
311: }