libfreerdp-codec/rfx_rlgr.c

   1 /**
   2  * FreeRDP: A Remote Desktop Protocol client.
   3  * RemoteFX Codec Library - RLGR
   4  *
   5  * Copyright 2011 Vic Lee
   6  *
   7  * Licensed under the Apache License, Version 2.0 (the "License");
   8  * you may not use this file except in compliance with the License.
   9  * You may obtain a copy of the License at
  10  *
  11  *     http://www.apache.org/licenses/LICENSE-2.0
  12  *
  13  * Unless required by applicable law or agreed to in writing, software
  14  * distributed under the License is distributed on an "AS IS" BASIS,
  15  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  16  * See the License for the specific language governing permissions and
  17  * limitations under the License.
  18  */
  19
  20 /**
  21  * This implementation of RLGR refers to
  22  * [MS-RDPRFX] 3.1.8.1.7.3 RLGR1/RLGR3 Pseudocode
  23  */
  24
  25 #include <stdio.h>
  26 #include <stdlib.h>
  27 #include <string.h>
  28 #include <freerdp/utils/memory.h>
  29 #include "rfx_bitstream.h"
  30
  31 #include "rfx_rlgr.h"
  32
  33 /* Constants used within the RLGR1/RLGR3 algorithm */
  34 #define KPMAX   (80)  /* max value for kp or krp */
  35 #define LSGR    (3)   /* shift count to convert kp to k */
  36 #define UP_GR   (4)   /* increase in kp after a zero run in RL mode */
  37 #define DN_GR   (6)   /* decrease in kp after a nonzero symbol in RL mode */
  38 #define UQ_GR   (3)   /* increase in kp after nonzero symbol in GR mode */
  39 #define DQ_GR   (3)   /* decrease in kp after zero symbol in GR mode */
  40
  41 /* Gets (returns) the next nBits from the bitstream */
  42 #define GetBits(nBits, r) rfx_bitstream_get_bits(bs, nBits, r)
  43
  44 /* From current output pointer, write "value", check and update buffer_size */
  45 #define WriteValue(value) \
  46 { \
  47         if (buffer_size > 0) \
  48                 *dst++ = (value); \
  49         buffer_size--; \
  50 }
  51
  52 /* From current output pointer, write next nZeroes terms with value 0, check and update buffer_size */
  53 #define WriteZeroes(nZeroes) \
  54 { \
  55         int nZeroesWritten = (nZeroes); \
  56         if (nZeroesWritten > buffer_size) \
  57                 nZeroesWritten = buffer_size; \
  58         if (nZeroesWritten > 0) \
  59         { \
  60                 memset(dst, 0, nZeroesWritten * sizeof(sint16)); \
  61                 dst += nZeroesWritten; \
  62         } \
  63         buffer_size -= (nZeroes); \
  64 }
  65
  66 /* Returns the least number of bits required to represent a given value */
  67 #define GetMinBits(_val, _nbits) \
  68 { \
  69         uint32 _v = _val; \
  70         _nbits = 0; \
  71         while (_v) \
  72         { \
  73                 _v >>= 1; \
  74                 _nbits++; \
  75         } \
  76 }
  77
  78 /* Converts from (2 * magnitude - sign) to integer */
  79 #define GetIntFrom2MagSign(twoMs) (((twoMs) & 1) ? -1 * (sint16)(((twoMs) + 1) >> 1) : (sint16)((twoMs) >> 1))
  80
  81 /*
  82  * Update the passed parameter and clamp it to the range [0, KPMAX]
  83  * Return the value of parameter right-shifted by LSGR
  84  */
  85 #define UpdateParam(_param, _deltaP, _k) \
  86 { \
  87         _param += _deltaP; \
  88         if (_param > KPMAX) \
  89                 _param = KPMAX; \
  90         if (_param < 0) \
  91                 _param = 0; \
  92         _k = (_param >> LSGR); \
  93 }
  94
  95 /* Outputs the Golomb/Rice encoding of a non-negative integer */
  96 #define GetGRCode(krp, kr, vk, _mag) \
  97         vk = 0; \
  98         _mag = 0; \
  99         /* chew up/count leading 1s and escape 0 */ \
 100         do { \
 101                 GetBits(1, r); \
 102                 if (r == 1) \
 103                         vk++; \
 104                 else \
 105                         break; \
 106         } while (1); \
 107         /* get next *kr bits, and combine with leading 1s */ \
 108         GetBits(*kr, _mag); \
 109         _mag |= (vk << *kr); \
 110         /* adjust krp and kr based on vk */ \
 111         if (!vk) { \
 112                 UpdateParam(*krp, -2, *kr); \
 113         } \
 114         else if (vk != 1) { \
 115                 UpdateParam(*krp, vk, *kr); /* at 1, no change! */ \
 116         }
 117
 118 int rfx_rlgr_decode(RLGR_MODE mode, const uint8* data, int data_size, sint16* buffer, int buffer_size)
 119 {
 120         int k;
 121         int kp;
 122         int kr;
 123         int krp;
 124         uint16 r;
 125         sint16* dst;
 126         RFX_BITSTREAM* bs;
 127
 128         int vk;
 129         uint16 mag16;
 130
 131         bs = xnew(RFX_BITSTREAM);
 132         rfx_bitstream_attach(bs, data, data_size);
 133         dst = buffer;
 134
 135         /* initialize the parameters */
 136         k = 1;
 137         kp = k << LSGR;
 138         kr = 1;
 139         krp = kr << LSGR;
 140
 141         while (!rfx_bitstream_eos(bs) && buffer_size > 0)
 142         {
 143                 int run;
 144                 if (k)
 145                 {
 146                         int mag;
 147                         uint32 sign;
 148
 149                         /* RL MODE */
 150                         while (!rfx_bitstream_eos(bs))
 151                         {
 152                                 GetBits(1, r);
 153                                 if (r)
 154                                         break;
 155                                 /* we have an RL escape "0", which translates to a run (1<<k) of zeros */
 156                                 WriteZeroes(1 << k);
 157                                 UpdateParam(kp, UP_GR, k); /* raise k and kp up because of zero run */
 158                         }
 159
 160                         /* next k bits will contain remaining run or zeros */
 161                         GetBits(k, run);
 162                         WriteZeroes(run);
 163
 164                         /* get nonzero value, starting with sign bit and then GRCode for magnitude -1 */
 165                         GetBits(1, sign);
 166
 167                         /* magnitude - 1 was coded (because it was nonzero) */
 168                         GetGRCode(&krp, &kr, vk, mag16)
 169                         mag = (int) (mag16 + 1);
 170
 171                         WriteValue(sign ? -mag : mag);
 172                         UpdateParam(kp, -DN_GR, k); /* lower k and kp because of nonzero term */
 173                 }
 174                 else
 175                 {
 176                         uint32 mag;
 177                         uint32 nIdx;
 178                         uint32 val1;
 179                         uint32 val2;
 180
 181                         /* GR (GOLOMB-RICE) MODE */
 182                         GetGRCode(&krp, &kr, vk, mag16) /* values coded are 2 * magnitude - sign */
 183                         mag = (uint32) mag16;
 184
 185                         if (mode == RLGR1)
 186                         {
 187                                 if (!mag)
 188                                 {
 189                                         WriteValue(0);
 190                                         UpdateParam(kp, UQ_GR, k); /* raise k and kp due to zero */
 191                                 }
 192                                 else
 193                                 {
 194                                         WriteValue(GetIntFrom2MagSign(mag));
 195                                         UpdateParam(kp, -DQ_GR, k); /* lower k and kp due to nonzero */
 196                                 }
 197                         }
 198                         else /* mode == RLGR3 */
 199                         {
 200                                 /*
 201                                  * In GR mode FOR RLGR3, we have encoded the
 202                                  * sum of two (2 * mag - sign) values
 203                                  */
 204
 205                                 /* maximum possible bits for first term */
 206                                 GetMinBits(mag, nIdx);
 207
 208                                 /* decode val1 is first term's (2 * mag - sign) value */
 209                                 GetBits(nIdx, val1);
 210
 211                                 /* val2 is second term's (2 * mag - sign) value */
 212                                 val2 = mag - val1;
 213
 214                                 if (val1 && val2)
 215                                 {
 216                                         /* raise k and kp if both terms nonzero */
 217                                         UpdateParam(kp, -2 * DQ_GR, k);
 218                                 }
 219                                 else if (!val1 && !val2)
 220                                 {
 221                                         /* lower k and kp if both terms zero */
 222                                         UpdateParam(kp, 2 * UQ_GR, k);
 223                                 }
 224
 225                                 WriteValue(GetIntFrom2MagSign(val1));
 226                                 WriteValue(GetIntFrom2MagSign(val2));
 227                         }
 228                 }
 229         }
 230
 231         xfree(bs);
 232
 233         return (dst - buffer);
 234 }
 235
 236 /* Returns the next coefficient (a signed int) to encode, from the input stream */
 237 #define GetNextInput(_n) \
 238 { \
 239         if (data_size > 0) \
 240         { \
 241                 _n = *data++; \
 242                 data_size--; \
 243         } \
 244         else \
 245         { \
 246                 _n = 0; \
 247         } \
 248 }
 249
 250 /* Emit bitPattern to the output bitstream */
 251 #define OutputBits(numBits, bitPattern) rfx_bitstream_put_bits(bs, bitPattern, numBits)
 252
 253 /* Emit a bit (0 or 1), count number of times, to the output bitstream */
 254 #define OutputBit(count, bit) \
 255 {       \
 256         uint16 _b = (bit ? 0xFFFF : 0); \
 257         int _c = (count); \
 258         for (; _c > 0; _c -= 16) \
 259                 rfx_bitstream_put_bits(bs, _b, (_c > 16 ? 16 : _c)); \
 260 }
 261
 262 /* Converts the input value to (2 * abs(input) - sign(input)), where sign(input) = (input < 0 ? 1 : 0) and returns it */
 263 #define Get2MagSign(input) ((input) >= 0 ? 2 * (input) : -2 * (input) - 1)
 264
 265 /* Outputs the Golomb/Rice encoding of a non-negative integer */
 266 #define CodeGR(krp, val) rfx_rlgr_code_gr(bs, krp, val)
 267
 268 static void rfx_rlgr_code_gr(RFX_BITSTREAM* bs, int* krp, uint32 val)
 269 {
 270         int kr = *krp >> LSGR;
 271
 272         /* unary part of GR code */
 273
 274         uint32 vk = (val) >> kr;
 275         OutputBit(vk, 1);
 276         OutputBit(1, 0);
 277
 278         /* remainder part of GR code, if needed */
 279         if (kr)
 280         {
 281                 OutputBits(kr, val & ((1 << kr) - 1));
 282         }
 283
 284         /* update krp, only if it is not equal to 1 */
 285         if (vk == 0)
 286         {
 287                 UpdateParam(*krp, -2, kr);
 288         }
 289         else if (vk > 1)
 290         {
 291                 UpdateParam(*krp, vk, kr);
 292         }
 293 }
 294
 295 int rfx_rlgr_encode(RLGR_MODE mode, const sint16* data, int data_size, uint8* buffer, int buffer_size)
 296 {
 297         int k;
 298         int kp;
 299         int krp;
 300         RFX_BITSTREAM* bs;
 301         int processed_size;
 302
 303         bs = xnew(RFX_BITSTREAM);
 304         rfx_bitstream_attach(bs, buffer, buffer_size);
 305
 306         /* initialize the parameters */
 307         k = 1;
 308         kp = 1 << LSGR;
 309         krp = 1 << LSGR;
 310
 311         /* process all the input coefficients */
 312         while (data_size > 0)
 313         {
 314                 int input;
 315
 316                 if (k)
 317                 {
 318                         int numZeros;
 319                         int runmax;
 320                         int mag;
 321                         int sign;
 322
 323                         /* RUN-LENGTH MODE */
 324
 325                         /* collect the run of zeros in the input stream */
 326                         numZeros = 0;
 327                         GetNextInput(input);
 328                         while (input == 0 && data_size > 0)
 329                         {
 330                                 numZeros++;
 331                                 GetNextInput(input);
 332                         }
 333
 334                         // emit output zeros
 335                         runmax = 1 << k;
 336                         while (numZeros >= runmax)
 337                         {
 338                                 OutputBit(1, 0); /* output a zero bit */
 339                                 numZeros -= runmax;
 340                                 UpdateParam(kp, UP_GR, k); /* update kp, k */
 341                                 runmax = 1 << k;
 342                         }
 343
 344                         /* output a 1 to terminate runs */
 345                         OutputBit(1, 1);
 346
 347                         /* output the remaining run length using k bits */
 348                         OutputBits(k, numZeros);
 349
 350                         /* note: when we reach here and the last byte being encoded is 0, we still
 351                            need to output the last two bits, otherwise mstsc will crash */
 352
 353                         /* encode the nonzero value using GR coding */
 354                         mag = (input < 0 ? -input : input); /* absolute value of input coefficient */
 355                         sign = (input < 0 ? 1 : 0);  /* sign of input coefficient */
 356
 357                         OutputBit(1, sign); /* output the sign bit */
 358                         CodeGR(&krp, mag ? mag - 1 : 0); /* output GR code for (mag - 1) */
 359
 360                         UpdateParam(kp, -DN_GR, k);
 361                 }
 362                 else
 363                 {
 364                         /* GOLOMB-RICE MODE */
 365
 366                         if (mode == RLGR1)
 367                         {
 368                                 uint32 twoMs;
 369
 370                                 /* RLGR1 variant */
 371
 372                                 /* convert input to (2*magnitude - sign), encode using GR code */
 373                                 GetNextInput(input);
 374                                 twoMs = Get2MagSign(input);
 375                                 CodeGR(&krp, twoMs);
 376
 377                                 /* update k, kp */
 378                                 /* NOTE: as of Aug 2011, the algorithm is still wrongly documented
 379                                    and the update direction is reversed */
 380                                 if (twoMs)
 381                                 {
 382                                         UpdateParam(kp, -DQ_GR, k);
 383                                 }
 384                                 else
 385                                 {
 386                                         UpdateParam(kp, UQ_GR, k);
 387                                 }
 388                         }
 389                         else /* mode == RLGR3 */
 390                         {
 391                                 uint32 twoMs1;
 392                                 uint32 twoMs2;
 393                                 uint32 sum2Ms;
 394                                 uint32 nIdx;
 395
 396                                 /* RLGR3 variant */
 397
 398                                 /* convert the next two input values to (2*magnitude - sign) and */
 399                                 /* encode their sum using GR code */
 400
 401                                 GetNextInput(input);
 402                                 twoMs1 = Get2MagSign(input);
 403                                 GetNextInput(input);
 404                                 twoMs2 = Get2MagSign(input);
 405                                 sum2Ms = twoMs1 + twoMs2;
 406
 407                                 CodeGR(&krp, sum2Ms);
 408
 409                                 /* encode binary representation of the first input (twoMs1). */
 410                                 GetMinBits(sum2Ms, nIdx);
 411                                 OutputBits(nIdx, twoMs1);
 412
 413                                 /* update k,kp for the two input values */
 414
 415                                 if (twoMs1 && twoMs2)
 416                                 {
 417                                         UpdateParam(kp, -2 * DQ_GR, k);
 418                                 }
 419                                 else if (!twoMs1 && !twoMs2)
 420                                 {
 421                                         UpdateParam(kp, 2 * UQ_GR, k);
 422                                 }
 423                         }
 424                 }
 425         }
 426
 427         processed_size = rfx_bitstream_get_processed_bytes(bs);
 428         xfree(bs);
 429
 430         return processed_size;
 431 }