src/aed.c

   1 /* Adaptive Entropy Decoder            */
   2 /* CCSDS 121.0-B-1 and CCSDS 120.0-G-2 */
   3
   4 #include <stdio.h>
   5 #include <unistd.h>
   6 #include <stdlib.h>
   7 #include <inttypes.h>
   8 #include <string.h>
   9
  10 #include "aecd.h"
  11
  12 #define ASK(n)                                                                                  \
  13     do {                                                                                                \
  14                 while (state->bitp < (unsigned)(n))                             \
  15                 {                                                                                               \
  16                         if (strm->avail_in == 0) goto req_buffer;       \
  17                         strm->avail_in--;                                                       \
  18                         strm->total_in++;                                                       \
  19                         state->acc <<= 8;                                                       \
  20                         state->acc |= (uint64_t)(*strm->next_in++);     \
  21                         state->bitp += 8;                                                       \
  22                 }                                                                                               \
  23         } while (0)
  24
  25 #define GET(n)                                                                                                  \
  26     ((state->acc >> (state->bitp - (n))) & ((1ULL << (n)) - 1))
  27
  28 #define DROP(n)                                           \
  29     do {                                                          \
  30         state->bitp -= (unsigned)(n); \
  31     } while (0)
  32
  33 #define ASKFS()                                                  \
  34         do {                                                             \
  35                 ASK(1);                                                  \
  36                 state->fs = 0;                                   \
  37                 while (GET(state->fs + 1) == 0)  \
  38                 {                                                                \
  39                         state->fs++;                             \
  40                         ASK(state->fs + 1);                      \
  41                 }                                                                \
  42         } while(0)
  43
  44 #define GETFS() \
  45         state->fs
  46
  47 #define DROPFS()                         \
  48         do {                                     \
  49                 DROP(state->fs + 1); \
  50         } while(0)
  51
  52 #define REFBLOCK(strm) (strm->pp && (strm->total_out / strm->block_size) \
  53                                                 % strm->segment_size == 0)
  54 #define ROS 5
  55
  56 typedef struct internal_state {
  57         uint32_t id_len;   /* bit length of code option identification key */
  58         int *id_table;     /* table maps IDs to states */
  59         size_t ref_int;    /* reference sample is every ref_int samples */
  60         uint32_t last_out; /* previous output for post-processing */
  61         int64_t xmin;      /* minimum integer for post-processing */
  62         int64_t xmax;      /* maximum integer for post-processing */
  63         int mode;          /* current mode of FSM */
  64         int pushed_mode;   /* originating mode for generic modes */
  65         size_t count, i;   /* total number of samples in block and current sample */
  66         int k;             /* k for split-sample options */
  67         uint32_t *block;   /* block buffer for split-sample options */
  68         uint64_t acc;      /* accumulator for currently used bit sequence */
  69         uint8_t bitp;      /* bit pointer to the next unused bit in accumulator */
  70         uint32_t fs;       /* last fundamental sequence in accumulator */
  71         uint32_t delta1;   /* interim result we need to keep for SE option */
  72 } decode_state;
  73
  74 /* decoding table for the second-extension option */
  75 static const uint32_t second_extension[36][2] = {
  76         {0, 0},
  77         {1, 1}, {1, 1},
  78         {2, 3}, {2, 3}, {2, 3},
  79         {3, 6}, {3, 6}, {3, 6}, {3, 6},
  80         {4, 10}, {4, 10}, {4, 10}, {4, 10}, {4, 10},
  81         {5, 15}, {5, 15}, {5, 15}, {5, 15}, {5, 15}, {5, 15},
  82         {6, 21}, {6, 21}, {6, 21}, {6, 21}, {6, 21}, {6, 21}, {6, 21},
  83         {7, 28}, {7, 28}, {7, 28}, {7, 28}, {7, 28}, {7, 28}, {7, 28}, {7, 28}
  84 };
  85
  86 enum
  87 {
  88         M_ID = 0,
  89         M_SPLIT,
  90         M_SPLIT_FS,
  91         M_SPLIT_BITS,
  92         M_SPLIT_OUTPUT,
  93         M_LOW_ENTROPY,
  94         M_ZERO_BLOCK,
  95         M_SE,
  96         M_SE_DECODE,
  97         M_GAMMA_GET,
  98         M_GAMMA_OUTPUT_0,
  99         M_GAMMA_OUTPUT_1,
 100         M_ZERO_OUTPUT,
 101         M_UNCOMP,
 102         M_UNCOMP_COPY,
 103         M_SAMPLE_GET,
 104         M_SAMPLE_OUTPUT
 105 };
 106
 107 static inline int output(ae_streamp strm, uint32_t out)
 108 {
 109         /**
 110            Outputs a post-processed sample.
 111
 112            If no post-processor is present then output unaltered.
 113          */
 114
 115         int64_t x, d, th, D;
 116         decode_state *state;
 117
 118         if (strm->avail_out == 0)
 119         {
 120                 return AE_STREAM_END;
 121         }
 122
 123         state = strm->state;
 124         if (strm->pp && (strm->total_out % state->ref_int != 0))
 125         {
 126                 d = out;
 127                 x = state->last_out;
 128
 129                 if ((x - state->xmin) < (state->xmax - x))
 130                 {
 131                         th = x - state->xmin;
 132                 }
 133                 else
 134                 {
 135                         th = state->xmax - x;
 136                 }
 137
 138                 if (d <= 2*th)
 139                 {
 140                         if (d & 1)
 141                                 D = - (d + 1) / 2;
 142                         else
 143                                 D = d / 2;
 144                 } else {
 145                         if (th == x)
 146                                 D = d - th;
 147                         else
 148                                 D = th - d;
 149                 }
 150                 out = x + D;
 151         }
 152         *strm->next_out++ = state->last_out = out;
 153         strm->avail_out--;
 154         strm->total_out++;
 155         return AE_OK;
 156 }
 157
 158 int ae_decode_init(ae_streamp strm)
 159 {
 160         int i, modi;
 161         decode_state *state;
 162
 163         /* Some sanity checks */
 164         if (strm->bit_per_sample > 32 || strm->bit_per_sample == 0)
 165         {
 166                 return AE_ERRNO;
 167         }
 168
 169         /* Internal state for decoder */
 170         state = (decode_state *) malloc(sizeof(decode_state));
 171         if (state == NULL)
 172         {
 173                 return AE_MEM_ERROR;
 174         }
 175         strm->state = state;
 176
 177         if (16 < strm->bit_per_sample)
 178                 state->id_len = 5;
 179         else if (8 < strm->bit_per_sample)
 180                 state->id_len = 4;
 181         else
 182                 state->id_len = 3;
 183
 184         state->ref_int = strm->block_size * strm->segment_size;
 185
 186         modi = 1UL << state->id_len;
 187         state->id_table = (int *)malloc(modi * sizeof(int));
 188         if (state->id_table == NULL)
 189         {
 190                 return AE_MEM_ERROR;
 191         }
 192         state->id_table[0] = M_LOW_ENTROPY;
 193         for (i = 1; i < modi - 1; i++)
 194         {
 195                 state->id_table[i] = M_SPLIT;
 196         }
 197         state->id_table[modi - 1] = M_UNCOMP;
 198
 199         state->block = (uint32_t *)malloc(strm->block_size * sizeof(uint32_t));
 200         if (state->block == NULL)
 201         {
 202                 return AE_MEM_ERROR;
 203         }
 204         strm->total_in = 0;
 205         strm->total_out = 0;
 206         state->xmin = 0;
 207         state->xmax = (1ULL << strm->bit_per_sample) - 1;
 208
 209         state->bitp = 0;
 210         state->mode = M_ID;
 211         return AE_OK;
 212 }
 213
 214 int ae_decode(ae_streamp strm, int flush)
 215 {
 216         int id;
 217         size_t zero_blocks;
 218         uint32_t gamma, beta, ms;
 219         decode_state *state;
 220
 221         state = strm->state;
 222
 223         for (;;)
 224         {
 225                 /* Slow but restartable finite-state machine implementation
 226                    of the adaptive entropy decoder. Can work with one byte
 227                    input und one sample output buffers. Inspired by zlib.
 228
 229                    TODO: Fast version with prior buffer size checking.
 230                  Flush modes like in zlib
 231                  */
 232                 switch(state->mode)
 233                 {
 234                 case M_ID:
 235                         ASK(3);
 236                         id = GET(3);
 237                         DROP(3);
 238                         state->mode = state->id_table[id];
 239                         state->k = id - 1;
 240                         break;
 241
 242                 case M_SPLIT:
 243                         state->count = strm->block_size;
 244                         state->i = 0;
 245                         state->mode = M_SPLIT_FS;
 246                         if (REFBLOCK(strm))
 247                         {
 248                                 state->pushed_mode = M_SPLIT_FS;
 249                                 state->mode = M_SAMPLE_GET;
 250                                 state->count--;
 251                                 break;
 252                         }
 253
 254                 case M_SPLIT_FS:
 255                         while(state->i < state->count)
 256                         {
 257                                 ASKFS();
 258                                 state->block[state->i] = GETFS() << state->k;
 259                                 DROPFS();
 260                                 state->i++;
 261                         }
 262                         state->i = 0;
 263                         state->mode = M_SPLIT_BITS;
 264
 265                 case M_SPLIT_BITS:
 266                         while(state->i < state->count)
 267                         {
 268                                 ASK(state->k);
 269                                 state->block[state->i] |= GET(state->k);
 270                                 DROP(state->k);
 271                                 state->i++;
 272                         }
 273                         state->i = 0;
 274                         state->mode = M_SPLIT_OUTPUT;
 275
 276                 case M_SPLIT_OUTPUT:
 277                         while(state->i < state->count)
 278                         {
 279                                 if (output(strm, state->block[state->i]) == AE_OK)
 280                                 {
 281                                         state->i++;
 282                                 }
 283                                 else
 284                                 {
 285                                         goto req_buffer;
 286                                 }
 287                         }
 288                         state->mode = M_ID;
 289                         break;
 290
 291                 case M_LOW_ENTROPY:
 292                         ASK(1);
 293                         if(GET(1))
 294                         {
 295                                 state->mode = M_SE;
 296                         }
 297                         else
 298                         {
 299                                 state->mode = M_ZERO_BLOCK;
 300                         }
 301                         DROP(1);
 302                         if (REFBLOCK(strm))
 303                         {
 304                                 state->pushed_mode = state->mode;
 305                                 state->mode = M_SAMPLE_GET;
 306                         }
 307                         break;
 308
 309                 case M_ZERO_BLOCK:
 310                         ASKFS();
 311                         zero_blocks = GETFS() + 1;
 312                         DROPFS();
 313                         if (zero_blocks == ROS)
 314                         {
 315                                 zero_blocks =  strm->segment_size - (
 316                                         (strm->total_out / strm->block_size)
 317                                         % strm->segment_size);
 318                         }
 319                         state->count = zero_blocks * strm->block_size;
 320                         if (REFBLOCK(strm))
 321                         {
 322                                 state->count--;
 323                         }
 324                         state->mode = M_ZERO_OUTPUT;
 325
 326                 case M_ZERO_OUTPUT:
 327                         while(state->count > 0 && output(strm, 0) == AE_OK)
 328                         {
 329                                 state->count--;
 330                         }
 331                         if (state->count == 0)
 332                         {
 333                                 state->mode = M_ID;
 334                         }
 335                         else
 336                         {
 337                                 goto req_buffer;
 338                         }
 339                         break;
 340
 341                 case M_SE:
 342                         state->count = strm->bit_per_sample / 2;
 343                         state->mode = M_SE_DECODE;
 344
 345                 case M_SE_DECODE:
 346                         if(state->count > 0)
 347                         {
 348                                 state->count--;
 349                                 state->mode = M_GAMMA_GET;
 350                         }
 351                         else
 352                         {
 353                                 state->mode = M_ID;
 354                                 break;
 355                         }
 356                 case M_GAMMA_GET:
 357                         ASKFS();
 358                         state->mode = M_GAMMA_OUTPUT_0;
 359
 360                 case M_GAMMA_OUTPUT_0:
 361                         gamma = GETFS();
 362                         beta = second_extension[gamma][0];
 363                         ms = second_extension[gamma][1];
 364                         state->delta1 = gamma - ms;
 365                         if (!(REFBLOCK(strm) && state->count == strm->bit_per_sample / 2 - 1))
 366                         {
 367                                 if (output(strm, beta - state->delta1) != AE_OK)
 368                                         goto req_buffer;
 369                         }
 370                         DROPFS();
 371                         state->mode = M_GAMMA_OUTPUT_1;
 372
 373                 case M_GAMMA_OUTPUT_1:
 374                         if (output(strm, state->delta1) != AE_OK)
 375                                 goto req_buffer;
 376
 377                         state->mode = M_SE_DECODE;
 378                         break;
 379
 380                 case M_UNCOMP:
 381                         state->count = strm->block_size;
 382                         state->mode = M_UNCOMP_COPY;
 383
 384                 case M_UNCOMP_COPY:
 385                         if(state->count > 0)
 386                         {
 387                                 state->count--;
 388                                 state->pushed_mode = M_UNCOMP_COPY;
 389                                 state->mode = M_SAMPLE_GET;
 390                         }
 391                         else
 392                         {
 393                                 state->mode = M_ID;
 394                         }
 395                         break;
 396
 397                 case M_SAMPLE_GET:
 398                         ASK(strm->bit_per_sample);
 399                         state->mode = M_SAMPLE_OUTPUT;
 400
 401                 case M_SAMPLE_OUTPUT:
 402                         if (output(strm, GET(strm->bit_per_sample)) == AE_OK)
 403                         {
 404                                 DROP(strm->bit_per_sample);
 405                                 state->mode = state->pushed_mode;
 406                         }
 407                         else
 408                         {
 409                                 goto req_buffer;
 410                         }
 411                         break;
 412
 413                 default:
 414                         return AE_STREAM_ERROR;
 415                 }
 416         }
 417
 418 req_buffer:
 419         return AE_OK;
 420 }