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