encode.c 25.6 KB
Newer Older
1
/**
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
2
 * @file encode.c
3
 *
4
 * @author Mathis Rosenhauer, Deutsches Klimarechenzentrum
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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
 * @author Moritz Hanke, Deutsches Klimarechenzentrum
 * @author Joerg Behrens, Deutsches Klimarechenzentrum
 * @author Luis Kornblueh, Max-Planck-Institut fuer Meteorologie
 *
 * @section LICENSE
 * Copyright 2012
 *
 * Mathis Rosenhauer,                 Luis Kornblueh
 * Moritz Hanke,
 * Joerg Behrens
 *
 * Deutsches Klimarechenzentrum GmbH  Max-Planck-Institut fuer Meteorologie
 * Bundesstr. 45a                     Bundesstr. 53
 * 20146 Hamburg                      20146 Hamburg
 * Germany                            Germany
 *
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above
 *    copyright notice, this list of conditions and the following
 *    disclaimer in the documentation and/or other materials provided
 *    with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
 * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
 * OF THE POSSIBILITY OF SUCH DAMAGE.
 *
47 48 49
 * @section DESCRIPTION
 *
 * Adaptive Entropy Encoder
50
 * Based on CCSDS documents 121.0-B-2 and 120.0-G-2
51 52
 *
 */
53

54 55 56 57 58 59
#include <config.h>

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

60 61
#include <stdio.h>
#include <stdlib.h>
62
#include <unistd.h>
63 64
#include <string.h>

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
65 66 67
#include "libaec.h"
#include "encode.h"
#include "encode_accessors.h"
68

69
/* Marker for Remainder Of Segment condition in zero block encoding */
70
#define ROS -1
71

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
72 73 74 75
static int m_get_block(struct aec_stream *strm);

static inline void emit(struct internal_state *state,
                        uint32_t data, int bits)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
76
{
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
77 78 79 80
    /**
       Emit sequence of bits.
     */

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
81 82 83
    if (bits <= state->bits) {
        state->bits -= bits;
        *state->cds += data << state->bits;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
84
    } else {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
85 86
        bits -= state->bits;
        *state->cds++ += (uint64_t)data >> bits;
87

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
88
        while (bits & ~7) {
89
            bits -= 8;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
90
            *state->cds++ = data >> bits;
91
        }
92

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
93 94
        state->bits = 8 - bits;
        *state->cds = data << state->bits;
95
    }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
96 97
}

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
98
static inline void emitfs(struct internal_state *state, int fs)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
99
{
100 101
    /**
       Emits a fundamental sequence.
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
102

103 104
       fs zero bits followed by one 1 bit.
     */
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
105

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
106
    for(;;) {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
107 108 109
        if (fs < state->bits) {
            state->bits -= fs + 1;
            *state->cds += 1U << state->bits;
110
            break;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
111
        } else {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
112 113 114
            fs -= state->bits;
            *++state->cds = 0;
            state->bits = 8;
115 116
        }
    }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
117
}
118

119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197
static inline void copy64(uint8_t *dst, uint64_t src)
{
    dst[0] = src >> 56;
    dst[1] = src >> 48;
    dst[2] = src >> 40;
    dst[3] = src >> 32;
    dst[4] = src >> 24;
    dst[5] = src >> 16;
    dst[6] = src >> 8;
    dst[7] = src;
}

#define EMITBLOCK_FS(ref)                                           \
    static inline void emitblock_fs_##ref(struct aec_stream *strm,  \
                                          int k)                    \
    {                                                               \
        int i;                                                      \
        int used; /* used bits in 64 bit accumulator */             \
        uint64_t acc; /* accumulator */                             \
        struct internal_state *state = strm->state;                 \
                                                                    \
        acc = (uint64_t)*state->cds << 56;                          \
        used = 7 - state->bits;                                     \
                                                                    \
        for (i = ref; i < strm->block_size; i++) {                  \
            used += (state->block[i] >> k) + 1;                     \
            if (used > 63) {                                        \
                copy64(state->cds, acc);                            \
                state->cds += 8;                                    \
                acc = 0;                                            \
                used &= 0x3f;                                       \
            }                                                       \
            acc |= 1ULL << (63 - used);                             \
        }                                                           \
                                                                    \
        copy64(state->cds, acc);                                    \
        state->cds += used >> 3;                                    \
        state->bits = 7 - (used & 7);                               \
    }

EMITBLOCK_FS(0);
EMITBLOCK_FS(1);

#define EMITBLOCK(ref)                                              \
    static inline void emitblock_##ref(struct aec_stream *strm,     \
                                       int k)                       \
    {                                                               \
        /**                                                         \
           Emit the k LSB of a whole block of input data.           \
        */                                                          \
                                                                    \
        int b;                                                      \
        uint64_t a;                                                 \
        struct internal_state *state = strm->state;                 \
        uint32_t *in = state->block + ref;                          \
        uint32_t *in_end = state->block + strm->block_size;         \
        uint64_t mask = (1ULL << k) - 1;                            \
        uint8_t *o = state->cds;                                    \
        int p = state->bits;                                        \
                                                                    \
        a = *o;                                                     \
                                                                    \
        while(in < in_end) {                                        \
            a <<= 56;                                               \
            p = (p % 8) + 56;                                       \
                                                                    \
            while (p > k && in < in_end) {                          \
                p -= k;                                             \
                a += ((uint64_t)(*in++) & mask) << p;               \
            }                                                       \
                                                                    \
            for (b = 56; b > (p & ~7); b -= 8)                      \
                *o++ = a >> b;                                      \
            a >>= b;                                                \
        }                                                           \
                                                                    \
        *o = a;                                                     \
        state->cds = o;                                             \
        state->bits = p % 8;                                        \
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
198 199 200 201 202
    }

EMITBLOCK(0);
EMITBLOCK(1);

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
203
static void preprocess_unsigned(struct aec_stream *strm)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
204
{
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
205 206
    /**
       Preprocess RSI of unsigned samples.
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
207 208 209

       Combining preprocessing and converting to uint32_t in one loop
       is slower due to the data dependance on x_i-1.
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
210 211
    */

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
212
    uint32_t D;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
213
    struct internal_state *state = strm->state;
214 215
    const uint32_t *x = state->data_raw;
    uint32_t *d = state->data_pp;
216 217
    uint32_t xmax = state->xmax;
    uint32_t rsi = strm->rsi * strm->block_size - 1;
218

219
    *d++ = x[0];
220
    while (rsi--) {
221 222
        if (x[1] >= x[0]) {
            D = x[1] - x[0];
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
223
            if (D <= x[0])
224
                *d = 2 * D;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
225
            else
226
                *d = x[1];
227
        } else {
228
            D = x[0] - x[1];
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
229
            if (D <= xmax - x[0])
230
                *d = 2 * D - 1;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
231
            else
232
                *d = xmax - x[1];
233
        }
234
        d++;
235
        x++;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
236
    }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
237
    state->ref = 1;
238
    state->uncomp_len = (strm->block_size - 1) * strm->bits_per_sample;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
239 240
}

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
241
static void preprocess_signed(struct aec_stream *strm)
242
{
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
243 244 245 246
    /**
       Preprocess RSI of signed samples.
    */

247
    int64_t D;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
248
    struct internal_state *state = strm->state;
249 250
    uint32_t *d = state->data_pp;
    int32_t *x = (int32_t *)state->data_raw;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
251
    uint64_t m = 1ULL << (strm->bits_per_sample - 1);
252 253 254
    int64_t xmax = state->xmax;
    int64_t xmin = state->xmin;
    uint32_t rsi = strm->rsi * strm->block_size - 1;
255

256 257 258
    *d++ = (uint32_t)x[0];
    x[0] = (x[0] ^ m) - m;

259
    while (rsi--) {
260 261 262 263 264
        x[1] = (x[1] ^ m) - m;
        if (x[1] < x[0]) {
            D = (int64_t)x[0] - x[1];
            if (D <= xmax - x[0])
                *d = 2 * D - 1;
265
            else
266
                *d = xmax - x[1];
267
        } else {
268 269 270
            D = (int64_t)x[1] - x[0];
            if (D <= x[0] - xmin)
                *d = 2 * D;
271
            else
272
                *d = x[1] - xmin;
273
        }
274 275
        x++;
        d++;
276
    }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
277
    state->ref = 1;
278
    state->uncomp_len = (strm->block_size - 1) * strm->bits_per_sample;
279
}
280

281
static uint32_t assess_splitting_option(struct aec_stream *strm)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
282 283 284 285 286
{
    /**
       Length of CDS encoded with splitting option and optimal k.

       In Rice coding each sample in a block of samples is split at
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
287
       the same position into k LSB and bits_per_sample - k MSB. The
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307
       LSB part is left binary and the MSB part is coded as a
       fundamental sequence a.k.a. unary (see CCSDS 121.0-B-2). The
       function of the length of the Coded Data Set (CDS) depending on
       k has exactly one minimum (see A. Kiely, IPN Progress Report
       42-159).

       To find that minimum with only a few costly evaluations of the
       CDS length, we start with the k of the previous CDS. K is
       increased and the CDS length evaluated. If the CDS length gets
       smaller, then we are moving towards the minimum. If the length
       increases, then the minimum will be found with smaller k.

       For increasing k we know that we will gain block_size bits in
       length through the larger binary part. If the FS lenth is less
       than the block size then a reduced FS part can't compensate the
       larger binary part. So we know that the CDS for k+1 will be
       larger than for k without actually computing the length. An
       analogue check can be done for decreasing k.
     */

308
    int i, k;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
309 310 311 312 313 314 315 316 317 318 319 320 321
    int k_min;
    int this_bs; /* Block size of current block */
    int no_turn; /* 1 if we shouldn't reverse */
    int dir; /* Direction, 1 means increasing k, 0 decreasing k */
    uint64_t len; /* CDS length for current k */
    uint64_t len_min; /* CDS length minimum so far */
    uint64_t fs_len; /* Length of FS part (not including 1s) */

    struct internal_state *state = strm->state;

    this_bs = strm->block_size - state->ref;
    len_min = UINT64_MAX;
    k = k_min = state->k;
322
    no_turn = k == 0;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
323 324 325
    dir = 1;

    for (;;) {
326 327 328
        fs_len = 0;
        for (i = state->ref; i < strm->block_size; i++)
            fs_len += (uint64_t)(state->block[i] >> k);
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365
        len = fs_len + this_bs * (k + 1);

        if (len < len_min) {
            if (len_min < UINT64_MAX)
                no_turn = 1;

            len_min = len;
            k_min = k;

            if (dir) {
                if (fs_len < this_bs || k >= state->kmax) {
                    if (no_turn)
                        break;
                    k = state->k - 1;
                    dir = 0;
                    no_turn = 1;
                } else {
                    k++;
                }
            } else {
                if (fs_len >= this_bs || k == 0)
                    break;
                k--;
            }
        } else {
            if (no_turn)
                break;
            k = state->k - 1;
            dir = 0;
            no_turn = 1;
        }
    }
    state->k = k_min;

    return len_min;
}

366
static uint32_t assess_se_option(struct aec_stream *strm)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
367 368 369 370
{
    /**
       Length of CDS encoded with Second Extension option.

371
       If length is above limit just return UINT32_MAX.
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
372 373 374 375
    */

    int i;
    uint64_t d;
376
    uint32_t len;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
377 378 379 380 381 382 383 384
    struct internal_state *state = strm->state;

    len = 1;

    for (i = 0; i < strm->block_size; i+= 2) {
        d = (uint64_t)state->block[i]
            + (uint64_t)state->block[i + 1];
        /* we have to worry about overflow here */
385 386
        if (d > state->uncomp_len) {
            len = UINT32_MAX;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
387 388
            break;
        } else {
389
            len += d * (d + 1) / 2 + state->block[i + 1];
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
390 391 392 393 394
        }
    }
    return len;
}

395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419
static void init_output(struct aec_stream *strm)
{
    /**
       Direct output to next_out if next_out can hold a Coded Data
       Set, use internal buffer otherwise.
    */

    struct internal_state *state = strm->state;

    if (strm->avail_out > state->cds_len) {
        if (!state->direct_out) {
            state->direct_out = 1;
            *strm->next_out = *state->cds;
            state->cds = strm->next_out;
        }
    } else {
        if (state->zero_blocks == 0 || state->direct_out) {
            /* copy leftover from last block */
            *state->cds_buf = *state->cds;
            state->cds = state->cds_buf;
        }
        state->direct_out = 0;
    }
}

420 421 422 423 424 425
/*
 *
 * FSM functions
 *
 */

426
static int m_flush_block_resumable(struct aec_stream *strm)
427
{
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
428
    /**
429
       Slow and restartable flushing
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
430
    */
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
431
    struct internal_state *state = strm->state;
432

433 434 435 436 437 438 439 440 441 442 443
    int n = MIN(state->cds - state->cds_buf - state->i, strm->avail_out);
    memcpy(strm->next_out, state->cds_buf + state->i, n);
    strm->next_out += n;
    strm->avail_out -= n;
    state->i += n;

    if (strm->avail_out == 0) {
        return M_EXIT;
    } else {
        state->mode = m_get_block;
        return M_CONTINUE;
444 445 446
    }
}

447
static int m_flush_block(struct aec_stream *strm)
448
{
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
449
    /**
450
       Flush block in direct_out mode by updating counters.
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
451

452
       Fall back to slow flushing if in buffered mode.
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
453
    */
454
    int n;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
455
    struct internal_state *state = strm->state;
456

457 458 459 460
    if (state->direct_out) {
        n = state->cds - strm->next_out;
        strm->next_out += n;
        strm->avail_out -= n;
461 462
        state->mode = m_get_block;
        return M_CONTINUE;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
463
    }
464

465 466 467
    state->i = 0;
    state->mode = m_flush_block_resumable;
    return M_CONTINUE;
468
}
469

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
470
static int m_encode_splitting(struct aec_stream *strm)
471
{
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
472
    struct internal_state *state = strm->state;
473
    int k = state->k;
474

475
    emit(state, k + 1, state->id_len);
476

477
    if (state->ref)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
478
    {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
479
        emit(state, state->block[0], strm->bits_per_sample);
480
        emitblock_fs_1(strm, k);
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
481 482
        if (k)
            emitblock_1(strm, k);
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
483 484 485
    }
    else
    {
486
        emitblock_fs_0(strm, k);
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
487 488
        if (k)
            emitblock_0(strm, k);
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
489
    }
490

491 492
    return m_flush_block(strm);
}
493

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
494
static int m_encode_uncomp(struct aec_stream *strm)
495
{
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
496
    struct internal_state *state = strm->state;
497

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
498
    emit(state, (1U << state->id_len) - 1, state->id_len);
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
499
    emitblock_0(strm, strm->bits_per_sample);
500

501 502
    return m_flush_block(strm);
}
503

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
504
static int m_encode_se(struct aec_stream *strm)
505 506
{
    int i;
507
    uint32_t d;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
508
    struct internal_state *state = strm->state;
509

510 511
    emit(state, 1, state->id_len + 1);
    if (state->ref)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
512
        emit(state, state->block[0], strm->bits_per_sample);
513

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
514
    for (i = 0; i < strm->block_size; i+= 2) {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
515 516
        d = state->block[i] + state->block[i + 1];
        emitfs(state, d * (d + 1) / 2 + state->block[i + 1]);
517
    }
518

519 520
    return m_flush_block(strm);
}
521

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
522
static int m_encode_zero(struct aec_stream *strm)
523
{
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
524
    struct internal_state *state = strm->state;
525

526
    emit(state, 0, state->id_len + 1);
527

528
    if (state->zero_ref)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
529
        emit(state, state->zero_ref_sample, strm->bits_per_sample);
530

531 532 533 534 535 536
    if (state->zero_blocks == ROS)
        emitfs(state, 4);
    else if (state->zero_blocks >= 5)
        emitfs(state, state->zero_blocks);
    else
        emitfs(state, state->zero_blocks - 1);
537

538 539 540
    state->zero_blocks = 0;
    return m_flush_block(strm);
}
541

542
static int m_select_code_option(struct aec_stream *strm)
543
{
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
544
    /**
545 546
       Decide which code option to use.
    */
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
547

548 549
    uint32_t split_len;
    uint32_t se_len;
550 551 552
    struct internal_state *state = strm->state;

    split_len = assess_splitting_option(strm);
553
    se_len = assess_se_option(strm);
554

555
    if (split_len < state->uncomp_len) {
556 557 558 559 560
        if (split_len < se_len)
            return m_encode_splitting(strm);
        else
            return m_encode_se(strm);
    } else {
561
        if (state->uncomp_len <= se_len)
562 563 564 565 566 567 568 569 570 571 572 573 574
            return m_encode_uncomp(strm);
        else
            return m_encode_se(strm);
    }
}

static int m_check_zero_block(struct aec_stream *strm)
{
    /**
       Check if input block is all zero.

       Aggregate consecutive zero blocks until we find !0 or reach the
       end of a segment or RSI.
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
575
    */
576

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
577
    struct internal_state *state = strm->state;
578 579
    uint32_t *p = state->block + state->ref;
    uint32_t *end = state->block + strm->block_size;
580

581 582 583 584 585 586 587
    while(p < end && *p == 0)
        p++;

    if (p < end) {
        if (state->zero_blocks) {
            /* The current block isn't zero but we have to emit a
             * previous zero block first. The current block will be
588
             * flagged and handled later.
589
             */
590
            state->block_nonzero = 1;
591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608
            state->mode = m_encode_zero;
            return M_CONTINUE;
        }
        state->mode = m_select_code_option;
        return M_CONTINUE;
    } else {
        state->zero_blocks++;
        if (state->zero_blocks == 1) {
            state->zero_ref = state->ref;
            state->zero_ref_sample = state->block[0];
        }
        if (state->blocks_avail == 0
            || (strm->rsi - state->blocks_avail) % 64 == 0) {
            if (state->zero_blocks > 4)
                state->zero_blocks = ROS;
            state->mode = m_encode_zero;
            return M_CONTINUE;
        }
609 610 611
        state->mode = m_get_block;
        return M_CONTINUE;
    }
612
}
613

614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630
static int m_get_rsi_resumable(struct aec_stream *strm)
{
    /**
       Get RSI while input buffer is short.

       Let user provide more input. Once we got all input pad buffer
       to full RSI.
    */

    struct internal_state *state = strm->state;

    do {
        if (strm->avail_in > 0) {
            state->data_raw[state->i] = state->get_sample(strm);
        } else {
            if (state->flush == AEC_FLUSH) {
                if (state->i > 0) {
631 632 633 634
                    do
                        state->data_raw[state->i] =
                            state->data_raw[state->i - 1];
                    while(++state->i < strm->rsi * strm->block_size);
635 636
                } else {
                    emit(state, 0, state->bits);
637
                    if (strm->avail_out > 0) {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
638
                        if (!state->direct_out)
639 640 641
                            *strm->next_out++ = *state->cds;
                        strm->avail_out--;
                    }
642 643 644 645 646 647 648 649
                    return M_EXIT;
                }
            } else {
                return M_EXIT;
            }
        }
    } while (++state->i < strm->rsi * strm->block_size);

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
650
    if (strm->flags & AEC_DATA_PREPROCESS)
651 652 653
        state->preprocess(strm);

    return m_check_zero_block(strm);
654 655
}

656
static int m_get_block(struct aec_stream *strm)
657
{
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
658
    /**
659 660 661 662
       Provide the next block of preprocessed input data.

       Pull in a whole Reference Sample Interval (RSI) of data if
       block buffer is empty.
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
663
    */
664

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
665
    struct internal_state *state = strm->state;
666

667 668 669 670 671 672
    init_output(strm);

    if (state->block_nonzero) {
        state->block_nonzero = 0;
        state->mode = m_select_code_option;
        return M_CONTINUE;
673
    }
674

675
    if (state->blocks_avail == 0) {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
676
        state->blocks_avail = strm->rsi - 1;
677 678
        state->block = state->data_pp;

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
679
        if (strm->avail_in >= state->rsi_len) {
680
            state->get_rsi(strm);
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
681
            if (strm->flags & AEC_DATA_PREPROCESS)
682
                state->preprocess(strm);
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
683

684 685 686 687 688 689
            return m_check_zero_block(strm);
        } else {
            state->i = 0;
            state->mode = m_get_rsi_resumable;
        }
    } else {
690 691 692 693
        if (state->ref) {
            state->ref = 0;
            state->uncomp_len = strm->block_size * strm->bits_per_sample;
        }
694 695 696
        state->block += strm->block_size;
        state->blocks_avail--;
        return m_check_zero_block(strm);
697 698 699 700 701 702 703 704 705
    }
    return M_CONTINUE;
}

/*
 *
 * API functions
 *
 */
706

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
707
int aec_encode_init(struct aec_stream *strm)
708
{
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
709
    struct internal_state *state;
710

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
711
    if (strm->bits_per_sample > 32 || strm->bits_per_sample == 0)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
712
        return AEC_CONF_ERROR;
713 714 715 716 717

    if (strm->block_size != 8
        && strm->block_size != 16
        && strm->block_size != 32
        && strm->block_size != 64)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
718
        return AEC_CONF_ERROR;
719 720

    if (strm->rsi > 4096)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
721
        return AEC_CONF_ERROR;
722

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
723
    state = malloc(sizeof(struct internal_state));
724
    if (state == NULL)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
725
        return AEC_MEM_ERROR;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
726 727

    memset(state, 0, sizeof(struct internal_state));
728 729
    strm->state = state;

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
730
    if (strm->bits_per_sample > 16) {
731
        /* 24/32 input bit settings */
732 733
        state->id_len = 5;

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
734
        if (strm->bits_per_sample <= 24
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
735
            && strm->flags & AEC_DATA_3BYTE) {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
736
            state->rsi_len = 3;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
737
            if (strm->flags & AEC_DATA_MSB) {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
738 739
                state->get_sample = aec_get_msb_24;
                state->get_rsi = aec_get_rsi_msb_24;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
740
            } else {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
741 742
                state->get_sample = aec_get_lsb_24;
                state->get_rsi = aec_get_rsi_lsb_24;
743
            }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
744
        } else {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
745
            state->rsi_len = 4;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
746
            if (strm->flags & AEC_DATA_MSB) {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
747 748
                state->get_sample = aec_get_msb_32;
                state->get_rsi = aec_get_rsi_msb_32;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
749
            } else {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
750 751
                state->get_sample = aec_get_lsb_32;
                state->get_rsi = aec_get_rsi_lsb_32;
752 753
            }
        }
754
    }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
755
    else if (strm->bits_per_sample > 8) {
756 757
        /* 16 bit settings */
        state->id_len = 4;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
758
        state->rsi_len = 2;
759

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
760
        if (strm->flags & AEC_DATA_MSB) {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
761 762
            state->get_sample = aec_get_msb_16;
            state->get_rsi = aec_get_rsi_msb_16;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
763
        } else {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
764 765
            state->get_sample = aec_get_lsb_16;
            state->get_rsi = aec_get_rsi_lsb_16;
766
        }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
767
    } else {
768 769
        /* 8 bit settings */
        state->id_len = 3;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
770
        state->rsi_len = 1;
771

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
772 773
        state->get_sample = aec_get_8;
        state->get_rsi = aec_get_rsi_8;
774
    }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
775
    state->rsi_len *= strm->rsi * strm->block_size;
776

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
777
    if (strm->flags & AEC_DATA_SIGNED) {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
778 779
        state->xmin = -(1ULL << (strm->bits_per_sample - 1));
        state->xmax = (1ULL << (strm->bits_per_sample - 1)) - 1;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
780
        state->preprocess = preprocess_signed;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
781
    } else {
782
        state->xmin = 0;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
783
        state->xmax = (1ULL << strm->bits_per_sample) - 1;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
784
        state->preprocess = preprocess_unsigned;
785 786
    }

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
787 788
    state->kmax = (1U << state->id_len) - 3;

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
789 790 791
    state->data_pp = malloc(strm->rsi
                            * strm->block_size
                            * sizeof(uint32_t));
792
    if (state->data_pp == NULL)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
793
        return AEC_MEM_ERROR;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
794

795
    if (strm->flags & AEC_DATA_PREPROCESS) {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
796 797 798
        state->data_raw = malloc(strm->rsi
                                 * strm->block_size
                                 * sizeof(uint32_t));
799 800 801 802 803 804
        if (state->data_raw == NULL)
            return AEC_MEM_ERROR;
    } else {
        state->data_raw = state->data_pp;
    }

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
805
    state->block = state->data_pp;
806

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
807
    /* Largest possible CDS according to specs */
808
    state->cds_len = (5 + 64 * 32) / 8 + 3;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
809
    state->cds_buf = malloc(state->cds_len);
810
    if (state->cds_buf == NULL)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
811
        return AEC_MEM_ERROR;
812

813 814 815
    strm->total_in = 0;
    strm->total_out = 0;

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
816 817 818
    state->cds = state->cds_buf;
    *state->cds = 0;
    state->bits = 8;
819 820
    state->mode = m_get_block;

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
821
    return AEC_OK;
822 823
}

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
824
int aec_encode(struct aec_stream *strm, int flush)
825 826 827 828 829
{
    /**
       Finite-state machine implementation of the adaptive entropy
       encoder.
    */
830
    int n;
831 832
    struct internal_state *state = strm->state;

833
    state->flush = flush;
834 835
    strm->total_in += strm->avail_in;
    strm->total_out += strm->avail_out;
836 837 838

    while (state->mode(strm) == M_CONTINUE);

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
839
    if (state->direct_out) {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
840
        n = state->cds - strm->next_out;
841 842 843
        strm->next_out += n;
        strm->avail_out -= n;

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
844 845
        *state->cds_buf = *state->cds;
        state->cds = state->cds_buf;
846
        state->direct_out = 0;
847
    }
848 849
    strm->total_in -= strm->avail_in;
    strm->total_out -= strm->avail_out;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
850
    return AEC_OK;
851 852
}

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
853
int aec_encode_end(struct aec_stream *strm)
854
{
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
855
    struct internal_state *state = strm->state;
856

857 858 859
    if (strm->flags & AEC_DATA_PREPROCESS)
        free(state->data_raw);
    free(state->data_pp);
860
    free(state->cds_buf);
861
    free(state);
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
862
    return AEC_OK;
863
}
864

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
865
int aec_buffer_encode(struct aec_stream *strm)
866 867 868 869 870 871 872
{
    int status;

    status = aec_encode_init(strm);
    if (status != AEC_OK)
        return status;
    status = aec_encode(strm, AEC_FLUSH);
873
    if (strm->avail_in > 0)
874 875 876 877 878
        status = AEC_DATA_ERROR;

    aec_encode_end(strm);
    return status;
}