decode.c 18.1 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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75
#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;                     \
                                                                        \
        state->flush_end = MIN(state->buf_size, state->buf_next_out);   \
                                                                        \
        if (state->pp) {                                                \
            if (state->flush_start == 0 && state->flush_end > 0) {      \
                state->last_out = state->buf_out[0];                    \
                                                                        \
                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;                                 \
            }                                                           \
                                                                        \
            for (i = state->flush_start; i < state->flush_end; i++) {   \
                d = state->buf_out[i];                                  \
                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 {                                                        \
            for (i = state->flush_start; i < state->flush_end; i++) {   \
                data = state->buf_out[i];                               \
                PUTBLOCK;                                               \
            }                                                           \
        }                                                               \
        if (state->flush_end == state->buf_size) {                      \
            state->flush_start = 0;                                     \
        } else {                                                        \
            state->flush_start = state->flush_end;                      \
        }                                                               \
    }
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 128 129
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)
130
{
131
    struct internal_state *state = strm->state;
132

133 134 135
    state->buf_out[state->buf_next_out++] = s;
    strm->avail_out -= state->byte_per_sample;
    strm->total_out += state->byte_per_sample;
136

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

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

       No checking whatsoever. Read bits are dumped.
     */

151
    struct internal_state *state = strm->state;
152

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

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

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

172
    int64_t fs = 0;
173 174 175 176 177 178 179

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

    return fs;
}

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

    k = state->id - 1;

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

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

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

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

    while (i--)
204
        put_sample(strm, 0);
205 206
}

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

213
    i = state->ref;
214

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

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

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

    for (i = 0; i < strm->block_size; i++)
233
        put_sample(strm, u_get(strm, strm->bit_per_sample));
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 295 296
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;
297

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

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

307
    if (state->pp && state->buf_next_out == 0)
308 309 310 311
        state->ref = 1;
    else
        state->ref = 0;

312 313 314 315
    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);
316 317 318 319 320 321 322 323 324 325 326
    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 {
327 328 329 330 331
        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);
332 333 334 335 336 337 338 339 340 341 342
    } 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 {
343 344 345 346
        if (fs_ask(strm) == 0)
            return M_EXIT;
        state->block[state->i] = fs_get(strm);
        fs_drop(strm);
347 348 349 350 351 352 353 354 355 356 357
    } 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;

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

    if (state->ref) {
365 366
        if (copysample(strm) == 0)
            return M_EXIT;
367 368 369 370 371 372 373 374 375 376 377 378 379 380
        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;

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

    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;

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

    if (zero_blocks == ROS) {
402
        b = state->buf_next_out / strm->block_size;
403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428
        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) {
429 430 431
        if (fs_ask(strm) == 0)
            return M_EXIT;
        m = fs_get(strm);
432
        d1 = m - state->se_table[2 * m + 1];
433 434

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

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

    state->mode = m_id;
    return M_CONTINUE;
}

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

456
    if (SAFE(strm)) {
457 458 459 460 461 462 463 464 465 466 467 468 469 470
        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;

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

    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;

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

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

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

    state->mode = m_id;
    return M_CONTINUE;
}

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

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

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

523 524 525 526 527 528 529 530 531 532 533 534 535 536 537
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
538
int aec_decode_init(struct aec_stream *strm)
539
{
540
    int i, modi;
541
    struct internal_state *state;
542 543

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

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

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

    create_se_table(state->se_table);

556 557
    strm->state = state;

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

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

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

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

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

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

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

619 620 621 622 623
    state->buf_size = strm->rsi * strm->block_size;
    state->buf_out = (uint32_t *)malloc(state->buf_size * sizeof(uint32_t));
    if (state->buf_out == NULL)
        return AEC_MEM_ERROR;

624 625 626
    strm->total_in = 0;
    strm->total_out = 0;

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

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
636
int aec_decode(struct aec_stream *strm, int flush)
637
{
638 639 640 641 642 643 644 645 646
    /**
       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.
    */

647 648 649 650
    struct internal_state *state= strm->state;

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

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

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

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
666
int aec_buffer_decode(struct aec_stream *strm)
667 668 669 670 671 672 673 674 675 676 677
{
    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;
}