encode.c 30 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
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.           \
        */                                                          \
                                                                    \
        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;               \
            }                                                       \
                                                                    \
Moritz Hanke's avatar
Moritz Hanke committed
189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247
            switch (p & ~ 7) {                                      \
            case 0:                                                 \
                o[0] = a >> 56;                                     \
                o[1] = a >> 48;                                     \
                o[2] = a >> 40;                                     \
                o[3] = a >> 32;                                     \
                o[4] = a >> 24;                                     \
                o[5] = a >> 16;                                     \
                o[6] = a >> 8;                                      \
                o += 7;                                             \
                break;                                              \
            case 8:                                                 \
                o[0] = a >> 56;                                     \
                o[1] = a >> 48;                                     \
                o[2] = a >> 40;                                     \
                o[3] = a >> 32;                                     \
                o[4] = a >> 24;                                     \
                o[5] = a >> 16;                                     \
                a >>= 8;                                            \
                o += 6;                                             \
                break;                                              \
            case 16:                                                \
                o[0] = a >> 56;                                     \
                o[1] = a >> 48;                                     \
                o[2] = a >> 40;                                     \
                o[3] = a >> 32;                                     \
                o[4] = a >> 24;                                     \
                a >>= 16;                                           \
                o += 5;                                             \
                break;                                              \
            case 24:                                                \
                o[0] = a >> 56;                                     \
                o[1] = a >> 48;                                     \
                o[2] = a >> 40;                                     \
                o[3] = a >> 32;                                     \
                a >>= 24;                                           \
                o += 4;                                             \
                break;                                              \
            case 32:                                                \
                o[0] = a >> 56;                                     \
                o[1] = a >> 48;                                     \
                o[2] = a >> 40;                                     \
                a >>= 32;                                           \
                o += 3;                                             \
                break;                                              \
            case 40:                                                \
                o[0] = a >> 56;                                     \
                o[1] = a >> 48;                                     \
                a >>= 40;                                           \
                o += 2;                                             \
                break;                                              \
            case 48:                                                \
                *o++ = a >> 56;                                     \
                a >>= 48;                                           \
                break;                                              \
            default:                                                \
                a >>= 56;                                           \
                break;                                              \
            }                                                       \
248 249 250 251 252
        }                                                           \
                                                                    \
        *o = a;                                                     \
        state->cds = o;                                             \
        state->bits = p % 8;                                        \
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
253 254 255 256 257
    }

EMITBLOCK(0);
EMITBLOCK(1);

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
258
static void preprocess_unsigned(struct aec_stream *strm)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
259
{
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
260 261
    /**
       Preprocess RSI of unsigned samples.
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
262 263 264

       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
265 266
    */

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
267
    uint32_t D;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
268
    struct internal_state *state = strm->state;
269 270
    const uint32_t *x = state->data_raw;
    uint32_t *d = state->data_pp;
271 272
    uint32_t xmax = state->xmax;
    uint32_t rsi = strm->rsi * strm->block_size - 1;
273

274
    *d++ = x[0];
275
    while (rsi--) {
276 277
        if (x[1] >= x[0]) {
            D = x[1] - x[0];
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
278
            if (D <= x[0])
279
                *d = 2 * D;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
280
            else
281
                *d = x[1];
282
        } else {
283
            D = x[0] - x[1];
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
284
            if (D <= xmax - x[0])
285
                *d = 2 * D - 1;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
286
            else
287
                *d = xmax - x[1];
288
        }
289
        d++;
290
        x++;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
291
    }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
292
    state->ref = 1;
293
    state->uncomp_len = (strm->block_size - 1) * strm->bits_per_sample;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
294 295
}

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
296
static void preprocess_signed(struct aec_stream *strm)
297
{
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
298 299 300 301
    /**
       Preprocess RSI of signed samples.
    */

302
    int64_t D;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
303
    struct internal_state *state = strm->state;
304 305
    uint32_t *d = state->data_pp;
    int32_t *x = (int32_t *)state->data_raw;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
306
    uint64_t m = 1ULL << (strm->bits_per_sample - 1);
307 308 309
    int64_t xmax = state->xmax;
    int64_t xmin = state->xmin;
    uint32_t rsi = strm->rsi * strm->block_size - 1;
310

311 312 313
    *d++ = (uint32_t)x[0];
    x[0] = (x[0] ^ m) - m;

314
    while (rsi--) {
315 316 317 318 319
        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;
320
            else
321
                *d = xmax - x[1];
322
        } else {
323 324 325
            D = (int64_t)x[1] - x[0];
            if (D <= x[0] - xmin)
                *d = 2 * D;
326
            else
327
                *d = x[1] - xmin;
328
        }
329 330
        x++;
        d++;
331
    }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
332
    state->ref = 1;
333
    state->uncomp_len = (strm->block_size - 1) * strm->bits_per_sample;
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
static uint64_t block_fs(struct aec_stream *strm, int k)
{
    /**
       Sum FS of all samples in block for given splitting position.
    */

    int i;
    uint64_t fs = 0;
    struct internal_state *state = strm->state;

    for (i = 0; i < strm->block_size; i += 8)
        fs +=
            (uint64_t)(state->block[i + 0] >> k)
            + (uint64_t)(state->block[i + 1] >> k)
            + (uint64_t)(state->block[i + 2] >> k)
            + (uint64_t)(state->block[i + 3] >> k)
            + (uint64_t)(state->block[i + 4] >> k)
            + (uint64_t)(state->block[i + 5] >> k)
            + (uint64_t)(state->block[i + 6] >> k)
            + (uint64_t)(state->block[i + 7] >> k);

    if (state->ref)
        fs -= (uint64_t)(state->block[0] >> k);

    return fs;
}

363
static uint32_t assess_splitting_option(struct aec_stream *strm)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
364 365 366 367 368
{
    /**
       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
369
       the same position into k LSB and bits_per_sample - k MSB. The
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389
       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.
     */

390
    int k;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
391 392 393 394 395 396 397 398 399 400 401 402 403
    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;
404
    no_turn = k == 0;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
405 406 407
    dir = 1;

    for (;;) {
408
        fs_len = block_fs(strm, k);
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445
        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;
}

446
static uint32_t assess_se_option(struct aec_stream *strm)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
447 448 449 450
{
    /**
       Length of CDS encoded with Second Extension option.

451
       If length is above limit just return UINT32_MAX.
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
452 453 454 455
    */

    int i;
    uint64_t d;
456
    uint32_t len;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
457 458 459 460 461 462 463 464
    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 */
465 466
        if (d > state->uncomp_len) {
            len = UINT32_MAX;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
467 468
            break;
        } else {
469
            len += d * (d + 1) / 2 + state->block[i + 1];
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
470 471 472 473 474
        }
    }
    return len;
}

475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499
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;
    }
}

500 501 502 503 504 505
/*
 *
 * FSM functions
 *
 */

506
static int m_flush_block_resumable(struct aec_stream *strm)
507
{
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
508
    /**
509
       Slow and restartable flushing
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
510
    */
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
511
    struct internal_state *state = strm->state;
512

513 514 515 516 517 518 519 520 521 522 523
    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;
524 525 526
    }
}

527
static int m_flush_block(struct aec_stream *strm)
528
{
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
529
    /**
530
       Flush block in direct_out mode by updating counters.
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
531

532
       Fall back to slow flushing if in buffered mode.
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
533
    */
534
    int n;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
535
    struct internal_state *state = strm->state;
536

537 538 539 540
    if (state->direct_out) {
        n = state->cds - strm->next_out;
        strm->next_out += n;
        strm->avail_out -= n;
541 542
        state->mode = m_get_block;
        return M_CONTINUE;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
543
    }
544

545 546 547
    state->i = 0;
    state->mode = m_flush_block_resumable;
    return M_CONTINUE;
548
}
549

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
550
static int m_encode_splitting(struct aec_stream *strm)
551
{
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
552
    struct internal_state *state = strm->state;
553
    int k = state->k;
554

555
    emit(state, k + 1, state->id_len);
556

557
    if (state->ref)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
558
    {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
559
        emit(state, state->block[0], strm->bits_per_sample);
560
        emitblock_fs_1(strm, k);
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
561 562
        if (k)
            emitblock_1(strm, k);
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
563 564 565
    }
    else
    {
566
        emitblock_fs_0(strm, k);
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
567 568
        if (k)
            emitblock_0(strm, k);
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
569
    }
570

571 572
    return m_flush_block(strm);
}
573

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
574
static int m_encode_uncomp(struct aec_stream *strm)
575
{
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
576
    struct internal_state *state = strm->state;
577

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
578
    emit(state, (1U << state->id_len) - 1, state->id_len);
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
579
    emitblock_0(strm, strm->bits_per_sample);
580

581 582
    return m_flush_block(strm);
}
583

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
584
static int m_encode_se(struct aec_stream *strm)
585 586
{
    int i;
587
    uint32_t d;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
588
    struct internal_state *state = strm->state;
589

590 591
    emit(state, 1, state->id_len + 1);
    if (state->ref)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
592
        emit(state, state->block[0], strm->bits_per_sample);
593

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
594
    for (i = 0; i < strm->block_size; i+= 2) {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
595 596
        d = state->block[i] + state->block[i + 1];
        emitfs(state, d * (d + 1) / 2 + state->block[i + 1]);
597
    }
598

599 600
    return m_flush_block(strm);
}
601

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
602
static int m_encode_zero(struct aec_stream *strm)
603
{
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
604
    struct internal_state *state = strm->state;
605

606
    emit(state, 0, state->id_len + 1);
607

608
    if (state->zero_ref)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
609
        emit(state, state->zero_ref_sample, strm->bits_per_sample);
610

611 612 613 614 615 616
    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);
617

618 619 620
    state->zero_blocks = 0;
    return m_flush_block(strm);
}
621

622
static int m_select_code_option(struct aec_stream *strm)
623
{
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
624
    /**
625 626
       Decide which code option to use.
    */
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
627

628 629
    uint32_t split_len;
    uint32_t se_len;
630 631 632
    struct internal_state *state = strm->state;

    split_len = assess_splitting_option(strm);
633
    se_len = assess_se_option(strm);
634

635
    if (split_len < state->uncomp_len) {
636 637 638 639 640
        if (split_len < se_len)
            return m_encode_splitting(strm);
        else
            return m_encode_se(strm);
    } else {
641
        if (state->uncomp_len <= se_len)
642 643 644 645 646 647 648 649 650 651 652 653 654
            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
655
    */
656

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
657
    struct internal_state *state = strm->state;
658 659
    uint32_t *p = state->block + state->ref;
    uint32_t *end = state->block + strm->block_size;
660

661 662 663 664 665 666 667
    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
668
             * flagged and handled later.
669
             */
670
            state->block_nonzero = 1;
671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688
            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;
        }
689 690 691
        state->mode = m_get_block;
        return M_CONTINUE;
    }
692
}
693

694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710
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) {
711 712 713 714
                    do
                        state->data_raw[state->i] =
                            state->data_raw[state->i - 1];
                    while(++state->i < strm->rsi * strm->block_size);
715 716
                } else {
                    emit(state, 0, state->bits);
717
                    if (strm->avail_out > 0) {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
718
                        if (!state->direct_out)
719 720 721
                            *strm->next_out++ = *state->cds;
                        strm->avail_out--;
                    }
722 723 724 725 726 727 728 729
                    return M_EXIT;
                }
            } else {
                return M_EXIT;
            }
        }
    } while (++state->i < strm->rsi * strm->block_size);

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
730
    if (strm->flags & AEC_DATA_PREPROCESS)
731 732 733
        state->preprocess(strm);

    return m_check_zero_block(strm);
734 735
}

736
static int m_get_block(struct aec_stream *strm)
737
{
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
738
    /**
739 740 741 742
       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
743
    */
744

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
745
    struct internal_state *state = strm->state;
746

747 748 749 750 751 752
    init_output(strm);

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

755
    if (state->blocks_avail == 0) {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
756
        state->blocks_avail = strm->rsi - 1;
757 758
        state->block = state->data_pp;

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
759
        if (strm->avail_in >= state->rsi_len) {
760
            state->get_rsi(strm);
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
761
            if (strm->flags & AEC_DATA_PREPROCESS)
762
                state->preprocess(strm);
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
763

764 765 766 767 768 769
            return m_check_zero_block(strm);
        } else {
            state->i = 0;
            state->mode = m_get_rsi_resumable;
        }
    } else {
770 771 772 773
        if (state->ref) {
            state->ref = 0;
            state->uncomp_len = strm->block_size * strm->bits_per_sample;
        }
774 775 776
        state->block += strm->block_size;
        state->blocks_avail--;
        return m_check_zero_block(strm);
777 778 779 780 781 782 783 784 785
    }
    return M_CONTINUE;
}

/*
 *
 * API functions
 *
 */
786

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
787
int aec_encode_init(struct aec_stream *strm)
788
{
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
789
    struct internal_state *state;
790

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
791
    if (strm->bits_per_sample > 32 || strm->bits_per_sample == 0)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
792
        return AEC_CONF_ERROR;
793 794 795 796 797

    if (strm->block_size != 8
        && strm->block_size != 16
        && strm->block_size != 32
        && strm->block_size != 64)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
798
        return AEC_CONF_ERROR;
799 800

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

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
803
    state = malloc(sizeof(struct internal_state));
804
    if (state == NULL)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
805
        return AEC_MEM_ERROR;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
806 807

    memset(state, 0, sizeof(struct internal_state));
808 809
    strm->state = state;

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
810
    if (strm->bits_per_sample > 16) {
811
        /* 24/32 input bit settings */
812 813
        state->id_len = 5;

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
814
        if (strm->bits_per_sample <= 24
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
815
            && strm->flags & AEC_DATA_3BYTE) {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
816
            state->rsi_len = 3;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
817
            if (strm->flags & AEC_DATA_MSB) {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
818 819
                state->get_sample = aec_get_msb_24;
                state->get_rsi = aec_get_rsi_msb_24;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
820
            } else {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
821 822
                state->get_sample = aec_get_lsb_24;
                state->get_rsi = aec_get_rsi_lsb_24;
823
            }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
824
        } else {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
825
            state->rsi_len = 4;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
826
            if (strm->flags & AEC_DATA_MSB) {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
827 828
                state->get_sample = aec_get_msb_32;
                state->get_rsi = aec_get_rsi_msb_32;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
829
            } else {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
830 831
                state->get_sample = aec_get_lsb_32;
                state->get_rsi = aec_get_rsi_lsb_32;
832 833
            }
        }
834
    }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
835
    else if (strm->bits_per_sample > 8) {
836 837
        /* 16 bit settings */
        state->id_len = 4;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
838
        state->rsi_len = 2;
839

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
840
        if (strm->flags & AEC_DATA_MSB) {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
841 842
            state->get_sample = aec_get_msb_16;
            state->get_rsi = aec_get_rsi_msb_16;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
843
        } else {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
844 845
            state->get_sample = aec_get_lsb_16;
            state->get_rsi = aec_get_rsi_lsb_16;
846
        }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
847
    } else {
848 849
        /* 8 bit settings */
        state->id_len = 3;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
850
        state->rsi_len = 1;
851

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
852 853
        state->get_sample = aec_get_8;
        state->get_rsi = aec_get_rsi_8;
854
    }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
855
    state->rsi_len *= strm->rsi * strm->block_size;
856

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
857
    if (strm->flags & AEC_DATA_SIGNED) {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
858 859
        state->xmin = -(1ULL << (strm->bits_per_sample - 1));
        state->xmax = (1ULL << (strm->bits_per_sample - 1)) - 1;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
860
        state->preprocess = preprocess_signed;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
861
    } else {
862
        state->xmin = 0;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
863
        state->xmax = (1ULL << strm->bits_per_sample) - 1;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
864
        state->preprocess = preprocess_unsigned;
865 866
    }

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

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
869 870 871
    state->data_pp = malloc(strm->rsi
                            * strm->block_size
                            * sizeof(uint32_t));
872
    if (state->data_pp == NULL)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
873
        return AEC_MEM_ERROR;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
874

875
    if (strm->flags & AEC_DATA_PREPROCESS) {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
876 877 878
        state->data_raw = malloc(strm->rsi
                                 * strm->block_size
                                 * sizeof(uint32_t));
879 880 881 882 883 884
        if (state->data_raw == NULL)
            return AEC_MEM_ERROR;
    } else {
        state->data_raw = state->data_pp;
    }

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
885
    state->block = state->data_pp;
886

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
887
    /* Largest possible CDS according to specs */
888
    state->cds_len = (5 + 64 * 32) / 8 + 3;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
889
    state->cds_buf = malloc(state->cds_len);
890
    if (state->cds_buf == NULL)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
891
        return AEC_MEM_ERROR;
892

893 894 895
    strm->total_in = 0;
    strm->total_out = 0;

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
896 897 898
    state->cds = state->cds_buf;
    *state->cds = 0;
    state->bits = 8;
899 900
    state->mode = m_get_block;

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
901
    return AEC_OK;
902 903
}

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
904
int aec_encode(struct aec_stream *strm, int flush)
905 906 907 908 909
{
    /**
       Finite-state machine implementation of the adaptive entropy
       encoder.
    */
910
    int n;
911 912
    struct internal_state *state = strm->state;

913
    state->flush = flush;
914 915
    strm->total_in += strm->avail_in;
    strm->total_out += strm->avail_out;
916 917 918

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

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
919
    if (state->direct_out) {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
920
        n = state->cds - strm->next_out;
921 922 923
        strm->next_out += n;
        strm->avail_out -= n;

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
924 925
        *state->cds_buf = *state->cds;
        state->cds = state->cds_buf;
926
        state->direct_out = 0;
927
    }
928 929
    strm->total_in -= strm->avail_in;
    strm->total_out -= strm->avail_out;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
930
    return AEC_OK;
931 932
}

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
933
int aec_encode_end(struct aec_stream *strm)
934
{
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
935
    struct internal_state *state = strm->state;
936

937 938 939
    if (strm->flags & AEC_DATA_PREPROCESS)
        free(state->data_raw);
    free(state->data_pp);
940
    free(state->cds_buf);
941
    free(state);
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
942
    return AEC_OK;
943
}
944

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
945
int aec_buffer_encode(struct aec_stream *strm)
946 947 948 949 950 951 952
{
    int status;

    status = aec_encode_init(strm);
    if (status != AEC_OK)
        return status;
    status = aec_encode(strm, AEC_FLUSH);
953
    if (strm->avail_in > 0)
954 955 956 957 958
        status = AEC_DATA_ERROR;

    aec_encode_end(strm);
    return status;
}