decode.c 17.9 KB
Newer Older
1 2 3
/* Adaptive Entropy Decoder            */
/* CCSDS 121.0-B-1 and CCSDS 120.0-G-2 */

4 5 6 7 8 9
#include <config.h>

#if HAVE_STDINT_H
# include <stdint.h>
#endif

10 11 12 13 14
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
15
#include "libaec.h"
16
#include "decode.h"
17

18 19 20 21 22 23 24 25 26
#define FLUSH(KIND, PUTBLOCK)                                           \
    static void flush_##KIND(struct aec_stream *strm)                   \
    {                                                                   \
        int i;                                                          \
        int64_t x, d, th, D, lower, m, sample;                          \
        int64_t data;                                                   \
        struct internal_state *state = strm->state;                     \
                                                                        \
        if (state->pp) {                                                \
27 28
            if (state->flush_start == 0 && state->buf_i > 0) {          \
                state->last_out = state->buf[0];                        \
29 30 31 32 33 34 35 36 37 38 39 40
                                                                        \
                if (strm->flags & AEC_DATA_SIGNED) {                    \
                    m = 1ULL << (strm->bit_per_sample - 1);             \
                    /* Reference samples have to be sign extended */    \
                    state->last_out = ( state->last_out ^ m) - m;       \
                }                                                       \
                                                                        \
                data = state->last_out;                                 \
                PUTBLOCK;                                               \
                state->flush_start = 1;                                 \
            }                                                           \
                                                                        \
41 42
            for (i = state->flush_start; i < state->buf_i; i++) {       \
                d = state->buf[i];                                      \
43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62
                x = state->last_out;                                    \
                lower = x - state->xmin;                                \
                th = MIN(lower, state->xmax - x);                       \
                                                                        \
                if (d <= 2 * th) {                                      \
                    if (d & 1)                                          \
                        D = - (d + 1) / 2;                              \
                    else                                                \
                        D = d / 2;                                      \
                } else {                                                \
                    if (th == lower)                                    \
                        D = d - th;                                     \
                    else                                                \
                        D = th - d;                                     \
                }                                                       \
                data = x + D;                                           \
                state->last_out = data;                                 \
                PUTBLOCK;                                               \
            }                                                           \
        } else {                                                        \
63 64
            for (i = state->flush_start; i < state->buf_i; i++) {       \
                data = state->buf[i];                                   \
65 66 67
                PUTBLOCK;                                               \
            }                                                           \
        }                                                               \
68
        if (state->buf_i == state->buf_size) {                          \
69 70
            state->flush_start = 0;                                     \
        } else {                                                        \
71
            state->flush_start = state->buf_i;                          \
72 73
        }                                                               \
    }
74

75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127
FLUSH(msb_32,
      do {
          *strm->next_out++ = data >> 24;
          *strm->next_out++ = data >> 16;
          *strm->next_out++ = data >> 8;
          *strm->next_out++ = data;
      } while(0)
    )

FLUSH(msb_24,
      do {
          *strm->next_out++ = data >> 16;
          *strm->next_out++ = data >> 8;
          *strm->next_out++ = data;
      } while(0)
    )

FLUSH(msb_16,
      do {
          *strm->next_out++ = data >> 8;
          *strm->next_out++ = data;
      } while(0)
    )

FLUSH(lsb_32,
      do {
          *strm->next_out++ = data;
          *strm->next_out++ = data >> 8;
          *strm->next_out++ = data >> 16;
          *strm->next_out++ = data >> 24;
      } while(0)
    )

FLUSH(lsb_24,
      do {
          *strm->next_out++ = data;
          *strm->next_out++ = data >> 8;
          *strm->next_out++ = data >> 16;
      } while(0)
    )

FLUSH(lsb_16,
      do {
          *strm->next_out++ = data;
          *strm->next_out++ = data >> 8;
      } while(0)
    )

FLUSH(8,
      *strm->next_out++ = data;
    )

static void put_sample(struct aec_stream *strm, uint32_t s)
128
{
129
    struct internal_state *state = strm->state;
130

131
    state->buf[state->buf_i++] = s;
132 133
    strm->avail_out -= state->byte_per_sample;
    strm->total_out += state->byte_per_sample;
134

135
    if (state->buf_i == state->buf_size) {
136
        state->flush_output(strm);
137
        state->buf_i = 0;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
138
    }
139 140
}

141
static int64_t u_get(struct aec_stream *strm, unsigned int n)
142 143
{
    /**
144
       Get n bit from input stream
145 146 147 148

       No checking whatsoever. Read bits are dumped.
     */

149
    struct internal_state *state = strm->state;
150

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
151
    while (state->bitp < n) {
152 153
        strm->avail_in--;
        strm->total_in++;
154
        state->acc = (state->acc << 8) | *strm->next_in++;
155 156 157 158 159 160
        state->bitp += 8;
    }
    state->bitp -= n;
    return (state->acc >> state->bitp) & ((1ULL << n) - 1);
}

161
static int64_t u_get_fs(struct aec_stream *strm)
162 163 164 165 166 167 168 169
{
    /**
       Interpret a Fundamental Sequence from the input buffer.

       Essentially counts the number of 0 bits until a
       1 is encountered. TODO: faster version.
     */

170
    int64_t fs = 0;
171 172 173 174 175 176 177

    while(u_get(strm, 1) == 0)
        fs++;

    return fs;
}

178
static void fast_split(struct aec_stream *strm)
179
{
180
    int i, k;
181
    struct internal_state *state= strm->state;
182 183 184

    k = state->id - 1;

185
    if (state->ref)
186
        put_sample(strm, u_get(strm, strm->bit_per_sample));
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
187

188
    for (i = state->ref; i < strm->block_size; i++)
189 190
        state->block[i] = u_get_fs(strm) << k;

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
191
    for (i = state->ref; i < strm->block_size; i++) {
192
        state->block[i] += u_get(strm, k);
193
        put_sample(strm, state->block[i]);
194 195 196
    }
}

197
static void fast_zero(struct aec_stream *strm)
198 199 200 201
{
    int i = strm->state->i;

    while (i--)
202
        put_sample(strm, 0);
203 204
}

205
static void fast_se(struct aec_stream *strm)
206 207
{
    int i;
208
    int64_t m, d1;
209
    struct internal_state *state= strm->state;
210

211
    i = state->ref;
212

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
213
    while (i < strm->block_size) {
214
        m = u_get_fs(strm);
215
        d1 = m - state->se_table[2 * m + 1];
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
216

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
217
        if ((i & 1) == 0) {
218
            put_sample(strm, state->se_table[2 * m] - d1);
219 220
            i++;
        }
221
        put_sample(strm, d1);
222 223 224 225
        i++;
    }
}

226
static void fast_uncomp(struct aec_stream *strm)
227 228 229 230
{
    int i;

    for (i = 0; i < strm->block_size; i++)
231
        put_sample(strm, u_get(strm, strm->bit_per_sample));
232 233
}

234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294
static uint32_t bits_ask(struct aec_stream *strm, int n)
{
    while (strm->state->bitp < n) {
        if (strm->avail_in == 0)
            return 0;
        strm->avail_in--;
        strm->total_in++;
        strm->state->acc <<= 8;
        strm->state->acc |= *strm->next_in++;
        strm->state->bitp += 8;
    }
    return 1;
}

static uint32_t bits_get(struct aec_stream *strm, int n)
{
    return (strm->state->acc >> (strm->state->bitp - n))
        & ((1ULL << n) - 1);
}

static void bits_drop(struct aec_stream *strm, int n)
{
    strm->state->bitp -= n;
}

static uint32_t fs_ask(struct aec_stream *strm)
{
    if (bits_ask(strm, 1) == 0)
        return 0;
    while ((strm->state->acc & (1ULL << (strm->state->bitp - 1))) == 0) {
        if (strm->state->bitp == 1) {
            if (strm->avail_in == 0)
                return 0;
            strm->avail_in--;
            strm->total_in++;
            strm->state->acc <<= 8;
            strm->state->acc |= *strm->next_in++;
            strm->state->bitp += 8;
        }
        strm->state->fs++;
        strm->state->bitp--;
    }
    return 1;
}

static uint32_t fs_get(struct aec_stream *strm)
{
    return strm->state->fs;
}

static void fs_drop(struct aec_stream *strm)
{
    strm->state->fs = 0;
    strm->state->bitp--;
}

static uint32_t copysample(struct aec_stream *strm)
{
    if (bits_ask(strm, strm->bit_per_sample) == 0
        || strm->avail_out == 0)
        return 0;
295

296 297 298 299
    put_sample(strm, bits_get(strm, strm->bit_per_sample));
    bits_drop(strm, strm->bit_per_sample);
    return 1;
}
300 301 302 303 304

static int m_id(struct aec_stream *strm)
{
    struct internal_state *state = strm->state;

305
    if (state->pp && state->buf_i == 0)
306 307 308 309
        state->ref = 1;
    else
        state->ref = 0;

310 311 312 313
    if (bits_ask(strm, state->id_len) == 0)
        return M_EXIT;
    state->id = bits_get(strm, state->id_len);
    bits_drop(strm, state->id_len);
314 315 316 317 318 319 320 321 322 323 324
    state->mode = state->id_table[state->id];

    return M_CONTINUE;
}

static int m_split_output(struct aec_stream *strm)
{
    struct internal_state *state = strm->state;
    int k = state->id - 1;

    do {
325 326 327 328 329
        if (bits_ask(strm, k) == 0
            || strm->avail_out == 0)
            return M_EXIT;
        put_sample(strm, (state->block[state->i] << k) + bits_get(strm, k));
        bits_drop(strm, k);
330 331 332 333 334 335 336 337 338 339 340
    } while(state->i--);

    state->mode = m_id;
    return M_CONTINUE;
}

static int m_split_fs(struct aec_stream *strm)
{
    struct internal_state *state = strm->state;

    do {
341 342 343 344
        if (fs_ask(strm) == 0)
            return M_EXIT;
        state->block[state->i] = fs_get(strm);
        fs_drop(strm);
345 346 347 348 349 350 351 352 353 354 355
    } while(state->i--);

    state->i = state->n - 1;
    state->mode = m_split_output;
    return M_CONTINUE;
}

static int m_split(struct aec_stream *strm)
{
    struct internal_state *state = strm->state;

356
    if (SAFE(strm)) {
357 358 359 360 361 362
        fast_split(strm);
        state->mode = m_id;
        return M_CONTINUE;
    }

    if (state->ref) {
363 364
        if (copysample(strm) == 0)
            return M_EXIT;
365 366 367 368 369 370 371 372 373 374 375 376 377 378
        state->n = strm->block_size - 1;
    } else {
        state->n = strm->block_size;
    }

    state->i = state->n - 1;
    state->mode = m_split_fs;
    return M_CONTINUE;
}

static int m_zero_output(struct aec_stream *strm)
{
    struct internal_state *state = strm->state;

379 380 381 382 383
    do {
        if (strm->avail_out == 0)
            return M_EXIT;
        put_sample(strm, 0);
    } while(--state->i);
384 385 386 387 388 389 390 391 392 393

    state->mode = m_id;
    return M_CONTINUE;
}

static int m_zero_block(struct aec_stream *strm)
{
    int zero_blocks, b;
    struct internal_state *state = strm->state;

394 395 396 397
    if (fs_ask(strm) == 0)
        return M_EXIT;
    zero_blocks = fs_get(strm) + 1;
    fs_drop(strm);
398 399

    if (zero_blocks == ROS) {
400
        b = state->buf_i / strm->block_size;
401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426
        zero_blocks = MIN(strm->rsi - b, 64 - (b % 64));
    } else if (zero_blocks > ROS) {
        zero_blocks--;
    }

    if (state->ref)
        state->i = zero_blocks * strm->block_size - 1;
    else
        state->i = zero_blocks * strm->block_size;

    if (strm->avail_out >= state->i * state->byte_per_sample) {
        fast_zero(strm);
        state->mode = m_id;
        return M_CONTINUE;
    }

    state->mode = m_zero_output;
    return M_CONTINUE;
}

static int m_se_decode(struct aec_stream *strm)
{
    int64_t m, d1;
    struct internal_state *state = strm->state;

    while(state->i < strm->block_size) {
427 428 429
        if (fs_ask(strm) == 0)
            return M_EXIT;
        m = fs_get(strm);
430
        d1 = m - state->se_table[2 * m + 1];
431 432

        if ((state->i & 1) == 0) {
433 434 435
            if (strm->avail_out == 0)
                return M_EXIT;
            put_sample(strm, state->se_table[2 * m] - d1);
436 437 438
            state->i++;
        }

439 440 441
        if (strm->avail_out == 0)
            return M_EXIT;
        put_sample(strm, d1);
442
        state->i++;
443
        fs_drop(strm);
444 445 446 447 448 449 450 451 452 453
    }

    state->mode = m_id;
    return M_CONTINUE;
}

static int m_se(struct aec_stream *strm)
{
    struct internal_state *state = strm->state;

454
    if (SAFE(strm)) {
455 456 457 458 459 460 461 462 463 464 465 466 467 468
        fast_se(strm);
        state->mode = m_id;
        return M_CONTINUE;
    }

    state->mode = m_se_decode;
    state->i = state->ref;
    return M_CONTINUE;
}

static int m_low_entropy_ref(struct aec_stream *strm)
{
    struct internal_state *state = strm->state;

469 470
    if (state->ref && copysample(strm) == 0)
        return M_EXIT;
471 472 473 474 475 476 477 478 479 480 481 482 483 484

    if(state->id == 1) {
        state->mode = m_se;
        return M_CONTINUE;
    }

    state->mode = m_zero_block;
    return M_CONTINUE;
}

static int m_low_entropy(struct aec_stream *strm)
{
    struct internal_state *state = strm->state;

485 486 487 488
    if (bits_ask(strm, 1) == 0)
        return M_EXIT;
    state->id = bits_get(strm, 1);
    bits_drop(strm, 1);
489 490 491 492 493 494 495 496
    state->mode = m_low_entropy_ref;
    return M_CONTINUE;
}

static int m_uncomp_copy(struct aec_stream *strm)
{
    struct internal_state *state = strm->state;

497 498 499 500
    do {
        if (copysample(strm) == 0)
            return M_EXIT;
    } while(--state->i);
501 502 503 504 505 506 507 508 509

    state->mode = m_id;
    return M_CONTINUE;
}

static int m_uncomp(struct aec_stream *strm)
{
    struct internal_state *state = strm->state;

510
    if (SAFE(strm)) {
511 512 513 514 515 516 517 518 519 520
        fast_uncomp(strm);
        state->mode = m_id;
        return M_CONTINUE;
    }

    state->i = strm->block_size;
    state->mode = m_uncomp_copy;
    return M_CONTINUE;
}

521 522 523 524 525 526 527 528 529 530 531 532 533 534 535
static void create_se_table(int *table)
{
    int i, j, k, ms;

    k = 0;
    for (i = 0; i < 13; i++) {
        ms = k;
        for (j = 0; j <= i; j++) {
            table[2 * k] = i;
            table[2 * k + 1] = ms;
            k++;
        }
    }
}

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
536
int aec_decode_init(struct aec_stream *strm)
537
{
538
    int i, modi;
539
    struct internal_state *state;
540 541

    if (strm->bit_per_sample > 32 || strm->bit_per_sample == 0)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
542
        return AEC_CONF_ERROR;
543

544
    state = (struct internal_state *) malloc(sizeof(struct internal_state));
545
    if (state == NULL)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
546
        return AEC_MEM_ERROR;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
547

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
548
    state->se_table = (int *) malloc(182 * sizeof(int));
549 550 551 552 553
    if (state->se_table == NULL)
        return AEC_MEM_ERROR;

    create_se_table(state->se_table);

554 555
    strm->state = state;

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
556
    if (strm->bit_per_sample > 16) {
557
        state->id_len = 5;
558

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
559
        if (strm->bit_per_sample <= 24 && strm->flags & AEC_DATA_3BYTE) {
560
            state->byte_per_sample = 3;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
561
            if (strm->flags & AEC_DATA_MSB)
562
                state->flush_output = flush_msb_24;
563
            else
564
                state->flush_output = flush_lsb_24;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
565
        } else {
566
            state->byte_per_sample = 4;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
567
            if (strm->flags & AEC_DATA_MSB)
568
                state->flush_output = flush_msb_32;
569
            else
570
                state->flush_output = flush_lsb_32;
571 572 573
        }
        state->out_blklen = strm->block_size
            * state->byte_per_sample;
574
    }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
575
    else if (strm->bit_per_sample > 8) {
576
        state->byte_per_sample = 2;
577
        state->id_len = 4;
578
        state->out_blklen = strm->block_size * 2;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
579
        if (strm->flags & AEC_DATA_MSB)
580
            state->flush_output = flush_msb_16;
581
        else
582
            state->flush_output = flush_lsb_16;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
583
    } else {
584
        state->byte_per_sample = 1;
585
        state->id_len = 3;
586
        state->out_blklen = strm->block_size;
587
        state->flush_output = flush_8;
588 589
    }

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
590
    if (strm->flags & AEC_DATA_SIGNED) {
591 592
        state->xmin = -(1ULL << (strm->bit_per_sample - 1));
        state->xmax = (1ULL << (strm->bit_per_sample - 1)) - 1;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
593
    } else {
594 595 596
        state->xmin = 0;
        state->xmax = (1ULL << strm->bit_per_sample) - 1;
    }
597

598
    state->ref_int = strm->block_size * strm->rsi;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
599
    state->in_blklen = (strm->block_size * strm->bit_per_sample
600 601 602
                        + state->id_len) / 8 + 1;

    modi = 1UL << state->id_len;
603
    state->id_table = malloc(modi * sizeof(int (*)(struct aec_stream *)));
604
    if (state->id_table == NULL)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
605
        return AEC_MEM_ERROR;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
606

607
    state->id_table[0] = m_low_entropy;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
608
    for (i = 1; i < modi - 1; i++) {
609
        state->id_table[i] = m_split;
610
    }
611
    state->id_table[modi - 1] = m_uncomp;
612

613
    state->block = (int64_t *)malloc(strm->block_size * sizeof(int64_t));
614
    if (state->block == NULL)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
615
        return AEC_MEM_ERROR;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
616

617
    state->buf_size = strm->rsi * strm->block_size;
618 619
    state->buf = (uint32_t *)malloc(state->buf_size * sizeof(uint32_t));
    if (state->buf == NULL)
620 621
        return AEC_MEM_ERROR;

622 623 624
    strm->total_in = 0;
    strm->total_out = 0;

625
    state->buf_i = 0;
626
    state->flush_start = 0;
627
    state->bitp = 0;
628
    state->fs = 0;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
629
    state->pp = strm->flags & AEC_DATA_PREPROCESS;
630
    state->mode = m_id;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
631
    return AEC_OK;
632 633
}

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
634
int aec_decode(struct aec_stream *strm, int flush)
635
{
636 637 638 639 640 641 642 643 644
    /**
       Finite-state machine implementation of the adaptive entropy
       decoder.

       Can work with one byte input und one sample output buffers. If
       enough buffer space is available, then faster implementations
       of the states are called. Inspired by zlib.
    */

645 646 647 648
    struct internal_state *state= strm->state;

    while (state->mode(strm) == M_CONTINUE);
    state->flush_output(strm);
649 650
    return AEC_OK;
}
651

652 653
int aec_decode_end(struct aec_stream *strm)
{
654
    struct internal_state *state= strm->state;
655

656 657
    free(state->block);
    free(state->id_table);
658
    free(state->se_table);
659
    free(state->buf);
660
    free(state);
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
661
    return AEC_OK;
662
}
663

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
664
int aec_buffer_decode(struct aec_stream *strm)
665 666 667 668 669 670 671 672 673 674 675
{
    int status;

    status = aec_decode_init(strm);
    if (status != AEC_OK)
        return status;

    status = aec_decode(strm, AEC_FLUSH);
    aec_decode_end(strm);
    return status;
}