aed.c 14.2 KB
Newer Older
1 2 3 4 5 6 7 8 9
/* Adaptive Entropy Decoder            */
/* CCSDS 121.0-B-1 and CCSDS 120.0-G-2 */

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <inttypes.h>
#include <string.h>

10
#include "libae.h"
11

12 13
#define MIN(a, b) (((a) < (b))? (a): (b))

14 15
#define SAFE (strm->avail_in >= state->in_blklen        \
              && strm->avail_out >= strm->block_size)
16 17 18 19

#define ROS 5

typedef struct internal_state {
20
    int id;            /* option ID */
21
    int id_len;        /* bit length of code option identification key */
22
    int *id_table;     /* table maps IDs to states */
23
    void (*put_sample)(ae_streamp, int64_t);
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
24
    int ref_int;       /* reference sample is every ref_int samples */
25
    int64_t last_out;  /* previous output for post-processing */
26 27 28
    int64_t xmin;      /* minimum integer for post-processing */
    int64_t xmax;      /* maximum integer for post-processing */
    int mode;          /* current mode of FSM */
29
    int in_blklen;     /* length of uncompressed input block
30
                          should be the longest possible block */
31 32
    int n, i;          /* counter for samples */
    int64_t *block;    /* block buffer for split-sample options */
33 34
    int se;            /* set if second extension option is selected */
    uint64_t acc;      /* accumulator for currently used bit sequence */
35 36
    int bitp;          /* bit pointer to the next unused bit in accumulator */
    int fs;            /* last fundamental sequence in accumulator */
37
    int ref;           /* 1 if current block has reference sample */
38
    int pp;            /* 1 if postprocessor has to be used */
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
39
    size_t samples_out;
40 41 42
} decode_state;

/* decoding table for the second-extension option */
43
static const int second_extension[36][2] = {
44 45 46 47 48 49 50 51
    {0, 0},
    {1, 1}, {1, 1},
    {2, 3}, {2, 3}, {2, 3},
    {3, 6}, {3, 6}, {3, 6}, {3, 6},
    {4, 10}, {4, 10}, {4, 10}, {4, 10}, {4, 10},
    {5, 15}, {5, 15}, {5, 15}, {5, 15}, {5, 15}, {5, 15},
    {6, 21}, {6, 21}, {6, 21}, {6, 21}, {6, 21}, {6, 21}, {6, 21},
    {7, 28}, {7, 28}, {7, 28}, {7, 28}, {7, 28}, {7, 28}, {7, 28}, {7, 28}
52 53 54 55
};

enum
{
56 57 58 59 60 61 62 63 64 65 66 67
    M_ID = 0,
    M_SPLIT,
    M_SPLIT_FS,
    M_SPLIT_OUTPUT,
    M_LOW_ENTROPY,
    M_LOW_ENTROPY_REF,
    M_ZERO_BLOCK,
    M_ZERO_OUTPUT,
    M_SE,
    M_SE_DECODE,
    M_UNCOMP,
    M_UNCOMP_COPY,
68 69
};

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
70 71 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
static void put_msb_32(ae_streamp strm, int64_t data)
{
    *strm->next_out++ = data >> 24;
    *strm->next_out++ = data >> 16;
    *strm->next_out++ = data >> 8;
    *strm->next_out++ = data;
    strm->avail_out -= 4;
    strm->total_out += 4;
}

static void put_msb_16(ae_streamp strm, int64_t data)
{
    *strm->next_out++ = data >> 8;
    *strm->next_out++ = data;
    strm->avail_out -= 2;
    strm->total_out += 2;
}

static void put_lsb_32(ae_streamp strm, int64_t data)
{
    *strm->next_out++ = data;
    *strm->next_out++ = data >> 8;
    *strm->next_out++ = data >> 16;
    *strm->next_out++ = data >> 24;
    strm->avail_out -= 4;
    strm->total_out += 4;
}

static void put_lsb_16(ae_streamp strm, int64_t data)
{
    *strm->next_out++ = data;
    *strm->next_out++ = data >> 8;
    strm->avail_out -= 2;
    strm->total_out += 2;
}
105

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
106 107 108 109 110 111
static void put_8(ae_streamp strm, int64_t data)
{
    *strm->next_out++ = data;
    strm->avail_out--;
    strm->total_out++;
}
112 113

static inline void u_put(ae_streamp strm, int64_t sample)
114 115 116 117 118
{
    int64_t x, d, th, D;
    decode_state *state;

    state = strm->state;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
119
    if (state->pp && (state->samples_out % state->ref_int != 0))
120 121 122
    {
        d = sample;
        x = state->last_out;
123
        th = MIN(x - state->xmin, state->xmax - x);
124 125 126 127 128 129 130 131 132 133 134 135 136 137 138

        if (d <= 2*th)
        {
            if (d & 1)
                D = - (d + 1) / 2;
            else
                D = d / 2;
        } else {
            if (th == x)
                D = d - th;
            else
                D = th - d;
        }
        sample = x + D;
    }
139 140
    state->last_out = sample;
    state->put_sample(strm, sample);
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
141
    state->samples_out++;
142 143
}

144
static inline int64_t u_get(ae_streamp strm, unsigned int n)
145 146 147 148 149 150 151 152 153 154 155 156 157 158
{
    /**
       Unsafe get n bit from input stream

       No checking whatsoever. Read bits are dumped.
     */

    decode_state *state;

    state = strm->state;
    while (state->bitp < n)
    {
        strm->avail_in--;
        strm->total_in++;
159
        state->acc = (state->acc << 8) | *strm->next_in++;
160 161 162 163 164 165
        state->bitp += 8;
    }
    state->bitp -= n;
    return (state->acc >> state->bitp) & ((1ULL << n) - 1);
}

166
static inline int u_get_fs(ae_streamp strm)
167 168 169 170 171 172 173 174
{
    /**
       Interpret a Fundamental Sequence from the input buffer.

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

175
    int fs = 0;
176 177 178 179 180 181 182 183

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

    return fs;
}

static inline void fast_split(ae_streamp strm)
184
{
185
    int i, k;
186 187 188 189 190
    decode_state *state;

    state = strm->state;
    k = state->id - 1;

191
    if (state->ref)
192
        u_put(strm, u_get(strm, strm->bit_per_sample));
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
193

194
    for (i = state->ref; i < strm->block_size; i++)
195 196
        state->block[i] = u_get_fs(strm) << k;

197
    for (i = state->ref; i < strm->block_size; i++)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
198
    {
199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214
        state->block[i] += u_get(strm, k);
        u_put(strm, state->block[i]);
    }
}

static inline void fast_zero(ae_streamp strm)
{
    int i = strm->state->i;

    while (i--)
        u_put(strm, 0);
}

static inline void fast_se(ae_streamp strm)
{
    int i;
215
    int64_t gamma, beta, ms, delta1;
216

217
    i = strm->state->ref;
218

219
    while (i < strm->block_size)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
220
    {
221 222 223 224
        gamma = u_get_fs(strm);
        beta = second_extension[gamma][0];
        ms = second_extension[gamma][1];
        delta1 = gamma - ms;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
225

226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241
        if ((i & 1) == 0)
        {
            u_put(strm, beta - delta1);
            i++;
        }
        u_put(strm, delta1);
        i++;
    }
}

static inline void fast_uncomp(ae_streamp strm)
{
    int i;

    for (i = 0; i < strm->block_size; i++)
        u_put(strm, u_get(strm, strm->bit_per_sample));
242 243 244 245
}

int ae_decode_init(ae_streamp strm)
{
246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262
    int i, modi;
    decode_state *state;

    /* Some sanity checks */
    if (strm->bit_per_sample > 32 || strm->bit_per_sample == 0)
    {
        return AE_ERRNO;
    }

    /* Internal state for decoder */
    state = (decode_state *) malloc(sizeof(decode_state));
    if (state == NULL)
    {
        return AE_MEM_ERROR;
    }
    strm->state = state;

263 264
    if (strm->bit_per_sample > 16)
    {
265
        state->id_len = 5;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
266 267
        if (strm->flags & AE_DATA_MSB)
            state->put_sample = put_msb_32;
268
        else
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
269
            state->put_sample = put_lsb_32;
270 271 272
    }
    else if (strm->bit_per_sample > 8)
    {
273
        state->id_len = 4;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
274 275
        if (strm->flags & AE_DATA_MSB)
            state->put_sample = put_msb_16;
276
        else
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
277
            state->put_sample = put_lsb_16;
278
    }
279
    else
280
    {
281
        state->id_len = 3;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
282 283
        state->put_sample = put_8;

284 285 286 287 288 289 290 291 292 293 294 295
    }

    if (strm->flags & AE_DATA_SIGNED)
    {
        state->xmin = -(1ULL << (strm->bit_per_sample - 1));
        state->xmax = (1ULL << (strm->bit_per_sample - 1)) - 1;
    }
    else
    {
        state->xmin = 0;
        state->xmax = (1ULL << strm->bit_per_sample) - 1;
    }
296 297

    state->ref_int = strm->block_size * strm->segment_size;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
298
    state->in_blklen = (strm->block_size * strm->bit_per_sample
299 300 301 302 303 304 305 306 307 308 309 310 311 312 313
                        + state->id_len) / 8 + 1;

    modi = 1UL << state->id_len;
    state->id_table = (int *)malloc(modi * sizeof(int));
    if (state->id_table == NULL)
    {
        return AE_MEM_ERROR;
    }
    state->id_table[0] = M_LOW_ENTROPY;
    for (i = 1; i < modi - 1; i++)
    {
        state->id_table[i] = M_SPLIT;
    }
    state->id_table[modi - 1] = M_UNCOMP;

314
    state->block = (int64_t *)malloc(strm->block_size * sizeof(int64_t));
315 316 317 318 319 320 321
    if (state->block == NULL)
    {
        return AE_MEM_ERROR;
    }
    strm->total_in = 0;
    strm->total_out = 0;

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
322
    state->samples_out = 0;
323
    state->bitp = 0;
324
    state->pp = strm->flags & AE_DATA_PREPROCESS;
325 326
    state->mode = M_ID;
    return AE_OK;
327 328
}

329 330 331 332 333 334 335 336 337 338 339
int ae_decode_end(ae_streamp strm)
{
    decode_state *state;

    state = strm->state;
    free(state->block);
    free(state->id_table);
    free(state);
    return AE_OK;
}

340 341 342 343 344 345 346 347
#define ASK(n)                                           \
    do {                                                 \
        while (state->bitp < (unsigned)(n))              \
        {                                                \
            if (strm->avail_in == 0) goto req_buffer;    \
            strm->avail_in--;                            \
            strm->total_in++;                            \
            state->acc <<= 8;                            \
348
            state->acc |= *strm->next_in++;              \
349 350
            state->bitp += 8;                            \
        }                                                \
351
    } while (0)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
352

353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386
#define GET(n)                                                  \
    ((state->acc >> (state->bitp - (n))) & ((1ULL << (n)) - 1))

#define DROP(n) state->bitp -= (unsigned)(n)

#define ASKFS()                          \
    do {                                 \
        ASK(1);                          \
        state->fs = 0;                   \
        while (GET(state->fs + 1) == 0)  \
        {                                \
            state->fs++;                 \
            ASK(state->fs + 1);          \
        }                                \
    } while(0)

#define GETFS() state->fs

#define DROPFS() DROP(state->fs + 1)

#define PUT(sample)                                \
    do {                                           \
        if (strm->avail_out == 0) goto req_buffer; \
        u_put(strm, (sample));                     \
    } while (0)

#define COPYSAMPLE()                    \
    do {                                \
        ASK(strm->bit_per_sample);      \
        PUT(GET(strm->bit_per_sample)); \
        DROP(strm->bit_per_sample);     \
    } while (0)


387 388
int ae_decode(ae_streamp strm, int flush)
{
389 390 391 392 393 394 395 396 397
    /**
       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.
    */

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
398
    int zero_blocks;
399
    int64_t gamma, beta, ms, delta1;
400 401 402 403 404 405 406 407 408 409
    int k;
    decode_state *state;

    state = strm->state;

    for (;;)
    {
        switch(state->mode)
        {
        case M_ID:
410
            if (state->pp
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
411
                && (state->samples_out / strm->block_size) % strm->segment_size == 0)
412 413 414 415 416 417 418
                state->ref = 1;
            else
                state->ref = 0;

            ASK(state->id_len);
            state->id = GET(state->id_len);
            DROP(state->id_len);
419 420 421 422 423 424 425 426 427 428 429
            state->mode = state->id_table[state->id];
            break;

        case M_SPLIT:
            if (SAFE)
            {
                fast_split(strm);
                state->mode = M_ID;
                break;
            }

430
            if (state->ref)
431 432 433 434 435 436 437 438 439
            {
                COPYSAMPLE();
                state->n = strm->block_size - 1;
            }
            else
            {
                state->n = strm->block_size;
            }

440
            state->i = state->n - 1;
441 442 443 444 445 446
            state->mode = M_SPLIT_FS;

        case M_SPLIT_FS:
            do
            {
                ASKFS();
447
                state->block[state->i] = GETFS();
448 449
                DROPFS();
            }
450
            while(state->i--);
451

452
            state->i = state->n - 1;
453
            state->mode = M_SPLIT_OUTPUT;
454

455
        case M_SPLIT_OUTPUT:
456 457 458 459
            k = state->id - 1;
            do
            {
                ASK(k);
460
                PUT((state->block[state->i] << k) + GET(k));
461 462
                DROP(k);
            }
463
            while(state->i--);
464 465 466 467 468 469 470 471 472 473 474

            state->mode = M_ID;
            break;

        case M_LOW_ENTROPY:
            ASK(1);
            state->id = GET(1);
            DROP(1);
            state->mode = M_LOW_ENTROPY_REF;

        case M_LOW_ENTROPY_REF:
475
            if (state->ref)
476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493
                COPYSAMPLE();

            if(state->id == 1)
            {
                state->mode = M_SE;
                break;
            }

            state->mode = M_ZERO_BLOCK;

        case M_ZERO_BLOCK:
            ASKFS();
            zero_blocks = GETFS() + 1;
            DROPFS();

            if (zero_blocks == ROS)
            {
                zero_blocks =  strm->segment_size - (
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
494
                    (state->samples_out / strm->block_size)
495 496 497 498
                    % strm->segment_size);
            }


499
            if (state->ref)
500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529
                state->i = zero_blocks * strm->block_size - 1;
            else
                state->i = zero_blocks * strm->block_size;

            if (strm->avail_out >= state->i)
            {
                fast_zero(strm);
                state->mode = M_ID;
                break;
            }

            state->mode = M_ZERO_OUTPUT;

        case M_ZERO_OUTPUT:
            do
                PUT(0);
            while(--state->i);

            state->mode = M_ID;
            break;

        case M_SE:
            if (SAFE)
            {
                fast_se(strm);
                state->mode = M_ID;
                break;
            }

            state->mode = M_SE_DECODE;
530
            state->i = state->ref;
531 532

        case M_SE_DECODE:
533
            while(state->i < strm->block_size)
534 535
            {
                ASKFS();
536 537 538 539 540 541 542 543 544 545 546 547
                gamma = GETFS();
                beta = second_extension[gamma][0];
                ms = second_extension[gamma][1];
                delta1 = gamma - ms;

                if ((state->i & 1) == 0)
                {
                    PUT(beta - delta1);
                    state->i++;
                }

                PUT(delta1);
548
                state->i++;
549
                DROPFS();
550 551
            }

552
            state->mode = M_ID;
553
            break;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
554

555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577
        case M_UNCOMP:
            if (SAFE)
            {
                fast_uncomp(strm);
                state->mode = M_ID;
                break;
            }

            state->i = strm->block_size;
            state->mode = M_UNCOMP_COPY;

        case M_UNCOMP_COPY:
            do
                COPYSAMPLE();
            while(--state->i);

            state->mode = M_ID;
            break;

        default:
            return AE_STREAM_ERROR;
        }
    }
578 579

req_buffer:
580
    return AE_OK;
581
}