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:  }