aee.c 16.1 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
/* Adaptive Entropy Encoder            */
/* 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>

#include "libae.h"

#define ROS 5

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

enum
{
    M_NEW_BLOCK,
    M_GET_BLOCK,
    M_CHECK_ZERO_BLOCK,
    M_SELECT_CODE_OPTION,
    M_ENCODE_SPLIT,
    M_FLUSH_BLOCK,
    M_FLUSH_BLOCK_LOOP,
    M_ENCODE_UNCOMP,
    M_ENCODE_SE,
    M_ENCODE_ZERO,
};

typedef struct internal_state {
31 32 33
    int id_len;             /* bit length of code option identification key */
    int64_t last_in;        /* previous input for preprocessing */
    int64_t (*get_sample)(ae_streamp);
34 35 36
    int64_t xmin;           /* minimum integer for preprocessing */
    int64_t xmax;           /* maximum integer for preprocessing */
    int mode;               /* current mode of FSM */
37 38
    int i;                  /* counter for samples */
    int64_t *block_in;      /* input block buffer */
39 40
    uint8_t *block_out;     /* output block buffer */
    uint8_t *bp_out;        /* pointer to current output */
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
41
    size_t total_blocks;
42 43
    int bitp;               /* bit pointer to the next unused bit in accumulator */
    int block_deferred;     /* there is a block in the input buffer
44
                               but we first have to emit a zero block */
45 46 47 48 49 50
    int ref;                /* length of reference sample in current block
                               i.e. 0 or 1 depending on whether the block has
                               a reference sample or not */
    int zero_ref;           /* current zero block has a reference sample */
    int64_t zero_ref_sample;/* reference sample of zero block */
    int zero_blocks;        /* number of contiguous zero blocks */
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
51 52 53
#ifdef PROFILE
    int *prof;
#endif
54 55
} encode_state;

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
56 57 58
static int64_t get_lsb_32(ae_streamp strm)
{
    int64_t data;
59

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84
    data = *strm->next_in++;
    data |= *strm->next_in++ << 8;
    data |= *strm->next_in++ << 16;
    data |= *strm->next_in++ << 24;

    strm->avail_in -= 4;
    strm->total_in += 4;
    return data;
}

static int64_t get_lsb_16(ae_streamp strm)
{
    int64_t data;

    data = *strm->next_in++;
    data |= *strm->next_in++ << 8;

    strm->avail_in -= 2;
    strm->total_in += 2;
    return data;
}

static int64_t get_msb_32(ae_streamp strm)
{
    int64_t data;
85

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
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
    data = *strm->next_in++ << 24;
    data |= *strm->next_in++ << 16;
    data |= *strm->next_in++ << 8;
    data |= *strm->next_in++;

    strm->avail_in -= 4;
    strm->total_in += 4;
    return data;
}

static int64_t get_msb_16(ae_streamp strm)
{
    int64_t data;

    data = *strm->next_in++ << 8;
    data |= *strm->next_in++;

    strm->avail_in -= 2;
    strm->total_in += 2;
    return data;
}

static int64_t get_8(ae_streamp strm)
{
    strm->avail_in--;
    strm->total_in++;
    return *strm->next_in++;
}
114

115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133
int ae_encode_init(ae_streamp strm)
{
    int blklen;
    encode_state *state;

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

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

134 135
    if (strm->bit_per_sample > 16)
    {
136
        state->id_len = 5;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
137 138
        if (strm->flags & AE_DATA_MSB)
            state->get_sample = get_msb_32;
139
        else
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
140
            state->get_sample = get_lsb_32;
141 142 143
    }
    else if (strm->bit_per_sample > 8)
    {
144
        state->id_len = 4;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
145 146
        if (strm->flags & AE_DATA_MSB)
            state->get_sample = get_msb_16;
147
        else
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
148
            state->get_sample = get_lsb_16;
149
    }
150
    else
151
    {
152
        state->id_len = 3;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
153
        state->get_sample = get_8;
154 155 156 157 158 159 160 161 162 163 164 165
    }

    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;
    }
166

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
167 168 169 170 171 172 173 174 175
#ifdef PROFILE
    state->prof = (int *)malloc((strm->bit_per_sample + 2) * sizeof(int));
    if (state->prof == NULL)
    {
        return AE_MEM_ERROR;
    }
    memset(state->prof, 0, (strm->bit_per_sample + 2) * sizeof(int));
#endif

176
    state->block_in = (int64_t *)malloc(strm->block_size * sizeof(int64_t));
177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197
    if (state->block_in == NULL)
    {
        return AE_MEM_ERROR;
    }

    blklen = (strm->block_size * strm->bit_per_sample
              + state->id_len) / 8 + 1;

    state->block_out = (uint8_t *)malloc(blklen);
    if (state->block_out == NULL)
    {
        return AE_MEM_ERROR;
    }
    state->bp_out = state->block_out;
    state->bitp = 8;

    strm->total_in = 0;
    strm->total_out = 0;

    state->mode = M_NEW_BLOCK;

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
198
    state->total_blocks = 0;
199 200 201 202 203 204 205
    state->block_deferred = 0;
    state->zero_ref = 0;
    state->ref = 0;

    return AE_OK;
}

206
static inline void emit(encode_state *state, int64_t data, int bits)
207 208 209
{
    while(bits)
    {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
210
        data &= ((1ULL << bits) - 1);
211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227
        if (bits <= state->bitp)
        {
            data <<= state->bitp - bits;
            *state->bp_out += data;
            state->bitp -= bits;
            bits = 0;
        }
        else
        {
            *state->bp_out += data >> (bits - state->bitp);
            bits -= state->bitp;
            *++state->bp_out = 0;
            state->bitp = 8;
        }
    }
}

228
static inline void emitfs(encode_state *state, int fs)
229 230 231 232
{
    emit(state, 0, fs);
    emit(state, 1, 1);
}
233

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
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
#ifdef PROFILE
static inline void profile_print(ae_streamp strm)
{
    int i, total;
    encode_state *state;

    state = strm->state;
    fprintf(stderr, "Blocks encoded by each coding option\n");
    fprintf(stderr, "Zero blocks:  %i\n", state->prof[0]);
    total = state->prof[0];
    fprintf(stderr, "Second Ext.:  %i\n", state->prof[strm->bit_per_sample+1]);
    total += state->prof[strm->bit_per_sample+1];
    fprintf(stderr, "FS:           %i\n", state->prof[1]);
    total += state->prof[1];
    for (i = 2; i < strm->bit_per_sample - 1; i++)
    {
        fprintf(stderr, "k = %02i:       %i\n", i-1, state->prof[i]);
        total += state->prof[i];
    }
    fprintf(stderr, "Uncompressed: %i\n", state->prof[strm->bit_per_sample]);
    total += state->prof[strm->bit_per_sample];
    fprintf(stderr, "Total blocks: %i\n", total);
}
#endif

259 260 261 262 263 264 265
int ae_encode(ae_streamp strm, int flush)
{
    /**
       Finite-state machine implementation of the adaptive entropy
       encoder.
    */

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
266 267 268
    int i, j, k, zb;
    int64_t k_len[strm->bit_per_sample - 2];
    int64_t k_len_min, se_len, blk_head;
269
    int64_t d;
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 297 298 299 300 301 302 303 304 305 306 307 308
    int64_t theta, Delta;

    encode_state *state;

    state = strm->state;

    for (;;)
    {
        switch(state->mode)
        {
        case M_NEW_BLOCK:
            if (state->zero_blocks == 0)
            {
                /* copy leftover from last block */
                *state->block_out = *state->bp_out;
                state->bp_out = state->block_out;
            }

            if(state->block_deferred)
            {
                state->block_deferred = 0;
                state->mode = M_SELECT_CODE_OPTION;
                break;
            }

            state->i = 0;
            state->mode = M_GET_BLOCK;

        case M_GET_BLOCK:
            do
            {
                if (strm->avail_in == 0)
                {
                    if (flush == AE_FLUSH)
                    {
                        if (state->i > 0)
                        {
                            /* pad block with zeros if we have
                               a partial block */
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
309 310
                            state->block_in[state->i] = state->block_in[state->i - 1];
                            fprintf(stderr, "padding %lx\n", state->block_in[state->i]);
311 312 313 314 315 316 317
                        }
                        else
                        {
                            /* Pad last output byte with 1 bits
                               if user wants to flush, i.e. we got
                               all input there is.
                            */
318
                            emit(state, 0xff, state->bitp);
319
                            *strm->next_out++ = *state->bp_out;
320 321
                            strm->avail_out--;
                            strm->total_out++;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
322 323 324 325
#ifdef PROFILE
                            profile_print(strm);
#endif
                            goto req_buffer;
326 327
                        }
                    }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
328 329 330 331
                    else
                    {
                        goto req_buffer;
                    }
332 333 334
                }
                else
                {
335
                    state->block_in[state->i] = state->get_sample(strm);
336 337 338 339 340
                }
            }
            while (++state->i < strm->block_size);

            /* preprocess block if needed */
341
            if (strm->flags & AE_DATA_PREPROCESS)
342 343 344 345
            {
                /* If this is the first block in a segment
                   then we need to insert a reference sample.
                */
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
346
                if(state->total_blocks % strm->segment_size == 0)
347 348 349 350 351 352 353 354 355 356 357 358 359
                {
                    state->ref = 1;
                    state->last_in = state->block_in[0];
                }
                else
                {
                    state->ref = 0;
                }

                for (i = state->ref; i < strm->block_size; i++)
                {
                    theta = MIN(state->last_in - state->xmin,
                                state->xmax - state->last_in);
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
360
                    Delta = state->block_in[i] - state->last_in;
361 362 363 364 365 366 367 368 369 370 371
                    if (0 <= Delta && Delta <= theta)
                        d = 2 * Delta;
                    else if (-theta <= Delta && Delta < 0)
                        d = 2 * llabs(Delta) - 1;
                    else
                        d = theta + llabs(Delta);

                    state->last_in = state->block_in[i];
                    state->block_in[i] = d;
                }
            }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
372
            state->total_blocks++;
373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395
            state->mode = M_CHECK_ZERO_BLOCK;

        case M_CHECK_ZERO_BLOCK:
            zb = 1;
            for (i = state->ref; i < strm->block_size && zb; i++)
                if (state->block_in[i] != 0) zb = 0;

            if (zb)
            {
                /* remember ref on first zero block */
                if (state->zero_blocks == 0)
                {
                    state->zero_ref = state->ref;
                    state->zero_ref_sample = state->block_in[0];
                }

                state->zero_blocks++;

                if ((strm->total_in / strm->block_size)
                    % strm->segment_size == 0)
                {
                    if (state->zero_blocks > ROS)
                        state->zero_blocks = ROS;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
396 397 398
#ifdef PROFILE
                    state->prof[0] += state->zero_blocks;
#endif
399 400 401 402 403 404 405 406
                    state->mode = M_ENCODE_ZERO;
                    break;
                }
                state->mode = M_NEW_BLOCK;
                break;
            }
            else if (state->zero_blocks)
            {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
407 408 409
#ifdef PROFILE
                state->prof[0] += state->zero_blocks;
#endif
410 411 412 413 414 415 416 417 418 419 420 421
                state->mode = M_ENCODE_ZERO;
                /* The current block isn't zero but we have to
                   emit a previous zero block first. The
                   current block has to be handled later.
                */
                state->block_deferred = 1;
                break;
            }

            state->mode = M_SELECT_CODE_OPTION;

        case M_SELECT_CODE_OPTION:
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
422 423 424 425 426
            /* If zero block isn't an option then count length of
               sample splitting options */

            /* Encoded block always starts with ID and possibly a
               reference sample. */
427
            if (state->ref)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
428 429 430
                blk_head = state->id_len + strm->bit_per_sample;
            else
                blk_head = state->id_len;
431 432 433 434 435 436 437 438 439 440

            for (j = 0; j < strm->bit_per_sample - 2; j++)
                k_len[j] = blk_head;

            /* Count bits for sample splitting options */
            for (i = state->ref; i < strm->block_size; i++)
                for (j = 0; j < strm->bit_per_sample - 2; j++)
                    k_len[j] += (state->block_in[i] >> j) + 1 + j;

            /* Baseline is the size of an uncompressed block */
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
441
            k_len_min = state->id_len + strm->block_size * strm->bit_per_sample;
442 443 444 445 446
            k = strm->bit_per_sample;

            /* See if splitting option is better */
            for (j = 0; j < strm->bit_per_sample - 2; j++)
            {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
447
                if (k_len[j] < k_len_min)
448 449
                {
                    k = j;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
450
                    k_len_min = k_len[j];
451 452 453 454 455 456
                }
            }

            /* Count bits for 2nd extension */
            se_len = blk_head + 1;

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
457
            for (i = 0; i < strm->block_size && k_len_min > se_len; i+= 2)
458 459
            {
                d = state->block_in[i] + state->block_in[i + 1];
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
460 461 462 463 464
                /* we have to worry about overflow here */
                if (d > k_len_min)
                    se_len = d;
                else
                    se_len += d * (d + 1) / 2 + state->block_in[i + 1];
465 466 467
            }

            /* Decide which option to use */
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
468
            if (k_len_min <= se_len)
469 470 471
            {
                if (k == strm->bit_per_sample)
                {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
472 473 474
#ifdef PROFILE
                    state->prof[k]++;
#endif
475 476 477 478 479
                    state->mode = M_ENCODE_UNCOMP;
                    break;
                }
                else
                {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
480 481 482
#ifdef PROFILE
                    state->prof[k + 1]++;
#endif
483 484 485 486 487
                    state->mode = M_ENCODE_SPLIT;
                }
            }
            else
            {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
488 489 490
#ifdef PROFILE
                state->prof[strm->bit_per_sample + 1]++;
#endif
491 492 493 494 495
                state->mode = M_ENCODE_SE;
                break;
            }

        case M_ENCODE_SPLIT:
496
            emit(state, k + 1, state->id_len);
497
            if (state->ref)
498
                emit(state, state->block_in[0], strm->bit_per_sample);
499 500

            for (i = state->ref; i < strm->block_size; i++)
501
                emitfs(state, state->block_in[i] >> k);
502 503

            for (i = state->ref; i < strm->block_size; i++)
504
                emit(state, state->block_in[i], k);
505 506 507 508 509 510 511

            state->mode = M_FLUSH_BLOCK;

        case M_FLUSH_BLOCK:
            if (strm->avail_in == 0 && flush == AE_FLUSH)
            {
                /* pad last byte with 1 bits */
512
                emit(state, 0xff, state->bitp);
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
513 514 515
#ifdef PROFILE
                profile_print(strm);
#endif
516 517 518 519 520 521 522 523
            }
            state->i = 0;
            state->mode = M_FLUSH_BLOCK_LOOP;

        case M_FLUSH_BLOCK_LOOP:
            while(state->block_out + state->i < state->bp_out)
            {
                if (strm->avail_out == 0)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
524 525 526 527
                {
#ifdef PROFILE
                    profile_print(strm);
#endif
528
                    goto req_buffer;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
529
                }
530

531
                *strm->next_out++ = state->block_out[state->i];
532 533 534 535 536 537 538 539
                strm->avail_out--;
                strm->total_out++;
                state->i++;
            }
            state->mode = M_NEW_BLOCK;
            break;

        case M_ENCODE_UNCOMP:
540
            emit(state, 0x1f, state->id_len);
541
            for (i = 0; i < strm->block_size; i++)
542
                emit(state, state->block_in[i], strm->bit_per_sample);
543 544 545 546 547

            state->mode = M_FLUSH_BLOCK;
            break;

        case M_ENCODE_SE:
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
548
            emit(state, 1, state->id_len + 1);
549
            if (state->ref)
550
                emit(state, state->block_in[0], strm->bit_per_sample);
551 552 553 554

            for (i = 0; i < strm->block_size; i+= 2)
            {
                d = state->block_in[i] + state->block_in[i + 1];
555
                emitfs(state, d * (d + 1) / 2 + state->block_in[i + 1]);
556 557 558 559 560 561
            }

            state->mode = M_FLUSH_BLOCK;
            break;

        case M_ENCODE_ZERO:
562
            emit(state, 0, state->id_len + 1);
563 564
            if (state->zero_ref)
            {
565
                emit(state, state->zero_ref_sample, strm->bit_per_sample);
566
            }
567
            emitfs(state, state->zero_blocks - 1);
568 569 570 571 572 573 574 575 576 577 578 579
            state->zero_blocks = 0;
            state->mode = M_FLUSH_BLOCK;
            break;

        default:
            return AE_STREAM_ERROR;
        }
    }

req_buffer:
    return AE_OK;
}