encode.c 20.7 KB
Newer Older
1
/**
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
2
 * @file encode.c
3 4 5 6
 * @author Mathis Rosenhauer, Deutsches Klimarechenzentrum
 * @section DESCRIPTION
 *
 * Adaptive Entropy Encoder
7
 * Based on CCSDS documents 121.0-B-2 and 120.0-G-2
8 9
 *
 */
10 11 12

#include <stdio.h>
#include <stdlib.h>
13
#include <unistd.h>
14 15 16
#include <inttypes.h>
#include <string.h>

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
17 18 19
#include "libaec.h"
#include "encode.h"
#include "encode_accessors.h"
20

21
/* Marker for Remainder Of Segment condition in zero block encoding */
22
#define ROS -1
23 24 25

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

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
26 27 28 29 30 31 32 33 34 35 36 37 38
static int m_get_block(struct aec_stream *strm);
static int m_get_block_cautious(struct aec_stream *strm);
static int m_check_zero_block(struct aec_stream *strm);
static int m_select_code_option(struct aec_stream *strm);
static int m_flush_block(struct aec_stream *strm);
static int m_flush_block_cautious(struct aec_stream *strm);
static int m_encode_splitting(struct aec_stream *strm);
static int m_encode_uncomp(struct aec_stream *strm);
static int m_encode_se(struct aec_stream *strm);
static int m_encode_zero(struct aec_stream *strm);

static inline void emit(struct internal_state *state,
                        uint32_t data, int bits)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
39
{
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
40 41 42 43 44
    /**
       Emit sequence of bits.
     */

    if (bits <= state->bit_p) {
45 46
        state->bit_p -= bits;
        *state->cds_p += data << state->bit_p;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
47
    } else {
48
        bits -= state->bit_p;
49
        *state->cds_p++ += (uint64_t)data >> bits;
50

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
51
        while (bits & ~7) {
52
            bits -= 8;
53
            *state->cds_p++ = data >> bits;
54
        }
55

56 57
        state->bit_p = 8 - bits;
        *state->cds_p = data << state->bit_p;
58
    }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
59 60
}

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
61
static inline void emitfs(struct internal_state *state, int fs)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
62
{
63 64
    /**
       Emits a fundamental sequence.
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
65

66 67
       fs zero bits followed by one 1 bit.
     */
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
68

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
69 70
    for(;;) {
        if (fs < state->bit_p) {
71 72
            state->bit_p -= fs + 1;
            *state->cds_p += 1 << state->bit_p;
73
            break;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
74
        } else {
75 76 77
            fs -= state->bit_p;
            *++state->cds_p = 0;
            state->bit_p = 8;
78 79
        }
    }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
80
}
81

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
82
#define EMITBLOCK(ref)                                          \
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
83 84
    static inline void emitblock_##ref(struct aec_stream *strm, \
                                       int k)                   \
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
85 86 87
    {                                                           \
        int b;                                                  \
        uint64_t a;                                             \
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
88
        struct internal_state *state = strm->state;             \
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
89 90 91 92 93 94 95 96
        uint32_t *in = state->block_p + ref;                    \
        uint32_t *in_end = state->block_p + strm->block_size;   \
        uint64_t mask = (1ULL << k) - 1;                        \
        uint8_t *o = state->cds_p;                              \
        int p = state->bit_p;                                   \
                                                                \
        a = *o;                                                 \
                                                                \
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
97
        while(in < in_end) {                                    \
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
98 99 100
            a <<= 56;                                           \
            p = (p % 8) + 56;                                   \
                                                                \
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
101
            while (p > k && in < in_end) {                      \
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118
                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_p = o;                                       \
        state->bit_p = p % 8;                                   \
    }

EMITBLOCK(0);
EMITBLOCK(1);

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
119
static void preprocess_unsigned(struct aec_stream *strm)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
120 121
{
    int i;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
122
    int64_t theta, Delta, prev;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
123
    struct internal_state *state = strm->state;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
124

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
125
    prev = state->block_buf[0];
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
126

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
127
    for (i = 1; i < strm->rsi * strm->block_size; i++) {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
128 129 130
        theta = MIN(prev, state->xmax - prev);
        Delta = (int64_t)state->block_buf[i] - prev;
        prev = state->block_buf[i];
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
131

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
132
        if (0 <= Delta && Delta <= theta) {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
133
            state->block_buf[i] = 2 * Delta;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
134
        } else if (-theta <= Delta && Delta < 0) {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
135 136
            state->block_buf[i] = 2
                * (Delta < 0 ? -(uint64_t)Delta : Delta) - 1;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
137
        } else {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
138 139
            state->block_buf[i] = theta
                + (Delta < 0 ? -(uint64_t)Delta : Delta);
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
140 141 142 143
        }
    }
}

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
144
static void preprocess_signed(struct aec_stream *strm)
145
{
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
146 147
    int i, m;
    int64_t theta, Delta, prev, sample;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
148
    struct internal_state *state = strm->state;
149

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
150 151
    m = 64 - strm->bit_per_sample;
    prev = ((int64_t)state->block_buf[0] << m) >> m;
152

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
153
    for (i = 1; i < strm->rsi * strm->block_size; i++) {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
154 155 156 157 158
        theta = MIN(prev - state->xmin, state->xmax - prev);
        sample = ((int64_t)state->block_buf[i] << m) >> m;
        Delta = sample - prev;
        prev = sample;

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
159
        if (0 <= Delta && Delta <= theta) {
160
            state->block_buf[i] = 2 * Delta;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
161
        } else if (-theta <= Delta && Delta < 0) {
162 163
            state->block_buf[i] = 2
                * (Delta < 0 ? -(uint64_t)Delta : Delta) - 1;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
164
        } else {
165 166
            state->block_buf[i] = theta
                + (Delta < 0 ? -(uint64_t)Delta : Delta);
167
        }
168
    }
169
}
170

171 172 173 174 175 176
/*
 *
 * FSM functions
 *
 */

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
177
static int m_get_block(struct aec_stream *strm)
178
{
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
179
    struct internal_state *state = strm->state;
180

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
181 182
    if (strm->avail_out > state->cds_len) {
        if (!state->direct_out) {
183 184 185
            state->direct_out = 1;
            *strm->next_out = *state->cds_p;
            state->cds_p = strm->next_out;
186
        }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
187 188
    } else {
        if (state->zero_blocks == 0 || state->direct_out) {
189
            /* copy leftover from last block */
190 191
            *state->cds_buf = *state->cds_p;
            state->cds_p = state->cds_buf;
192
        }
193
        state->direct_out = 0;
194
    }
195

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
196
    if (state->blocks_avail == 0) {
197 198
        state->ref = 1;
        state->block_p = state->block_buf;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
199

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
200
        if (strm->avail_in >= state->block_len * strm->rsi) {
201
            state->get_block(strm);
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
202
            state->blocks_avail = strm->rsi - 1;
203

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
204
            if (strm->flags & AEC_DATA_PREPROCESS)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
205
                state->preprocess(strm);
206

207
            return m_check_zero_block(strm);
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
208
        } else {
209 210 211
            state->i = 0;
            state->mode = m_get_block_cautious;
        }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
212
    } else {
213 214 215 216
        state->ref = 0;
        state->block_p += strm->block_size;
        state->blocks_avail--;
        return m_check_zero_block(strm);
217
    }
218
    return M_CONTINUE;
219 220
}

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
221
static int input_empty(struct aec_stream *strm)
222
{
223
    int j;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
224 225 226 227 228 229 230 231 232 233 234 235
    struct internal_state *state = strm->state;

    if (state->flush == AEC_FLUSH) {
        if (state->i > 0) {
            for (j = state->i; j < strm->rsi * strm->block_size; j++)
                state->block_buf[j] = state->block_buf[state->i - 1];
            state->i = strm->rsi * strm->block_size;
        } else {
            if (state->zero_blocks) {
                state->mode = m_encode_zero;
                return M_CONTINUE;
            }
236

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
237 238 239 240 241
            emit(state, 0, state->bit_p);
            if (state->direct_out == 0)
                *strm->next_out++ = *state->cds_p;
            strm->avail_out--;
            strm->total_out++;
242

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
243
            return M_EXIT;
244 245
        }
    }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
246 247 248 249 250 251 252 253 254 255 256 257 258 259

    return M_EXIT;
}

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

    do {
        if (strm->avail_in > 0)
            state->block_buf[state->i] = state->get_sample(strm);
        else
            return input_empty(strm);
    } while (++state->i < strm->rsi * strm->block_size);
260

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
261
    state->blocks_avail = strm->rsi - 1;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
262
    if (strm->flags & AEC_DATA_PREPROCESS)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
263
        state->preprocess(strm);
264 265

    return m_check_zero_block(strm);
266 267
}

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
268
static int m_check_zero_block(struct aec_stream *strm)
269
{
270
    int i;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
271
    struct internal_state *state = strm->state;
272 273

    i = state->ref;
274
    while(i < strm->block_size && state->block_p[i] == 0)
275 276
        i++;

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
277 278
    if (i == strm->block_size) {
        if (state->zero_blocks == 0) {
279
            state->zero_ref = state->ref;
280
            state->zero_ref_sample = state->block_p[0];
281
        }
282

283
        state->zero_blocks++;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
284

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
285
        if ((strm->rsi - state->blocks_avail) % 64 == 0) {
286 287 288 289 290 291 292
            if (state->zero_blocks > 4)
                state->zero_blocks = ROS;
            state->mode = m_encode_zero;
            return M_CONTINUE;
        }
        state->mode = m_get_block;
        return M_CONTINUE;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
293
    } else if (state->zero_blocks) {
294 295 296 297
        /* The current block isn't zero but we have to emit a previous
         * zero block first. The current block will be handled
         * later.
         */
298 299
        state->block_p -= strm->block_size;
        state->blocks_avail++;
300 301
        state->mode = m_encode_zero;
        return M_CONTINUE;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
302
    }
303 304
    state->mode = m_select_code_option;
    return M_CONTINUE;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
305 306
}

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
307
static uint64_t block_fs(struct aec_stream *strm, int k)
308
{
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337
    int j;
    uint64_t fs;
    struct internal_state *state = strm->state;

    fs = (uint64_t)(state->block_p[1] >> k)
        + (uint64_t)(state->block_p[2] >> k)
        + (uint64_t)(state->block_p[3] >> k)
        + (uint64_t)(state->block_p[4] >> k)
        + (uint64_t)(state->block_p[5] >> k)
        + (uint64_t)(state->block_p[6] >> k)
        + (uint64_t)(state->block_p[7] >> k);

    if (strm->block_size > 8)
        for (j = 1; j < strm->block_size / 8; j++)
            fs +=
                (uint64_t)(state->block_p[j * 8 + 0] >> k)
                + (uint64_t)(state->block_p[j * 8 + 1] >> k)
                + (uint64_t)(state->block_p[j * 8 + 2] >> k)
                + (uint64_t)(state->block_p[j * 8 + 3] >> k)
                + (uint64_t)(state->block_p[j * 8 + 4] >> k)
                + (uint64_t)(state->block_p[j * 8 + 5] >> k)
                + (uint64_t)(state->block_p[j * 8 + 6] >> k)
                + (uint64_t)(state->block_p[j * 8 + 7] >> k);

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

    return fs;
}
338

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
339 340 341 342 343
static int count_splitting_option(struct aec_stream *strm)
{
    int i, k, this_bs, looked_bothways, direction;
    uint64_t len, len_min, fs_len;
    struct internal_state *state = strm->state;
344

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
345 346
    this_bs = strm->block_size - state->ref;
    len_min = UINT64_MAX;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
347
    i = k = state->k;
348 349
    direction = 1;
    looked_bothways = 0;
350

351
    /* Starting with splitting position of last block. Look left and
352 353
     * possibly right to find new minimum.
     */
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
354 355 356 357 358 359
    for (;;) {
        fs_len = block_fs(strm, i);
        len = fs_len + this_bs * (i + 1);

        if (len < len_min) {
            if (len_min < UINT64_MAX) {
360
                /* We are moving towards the minimum so it cant be in
361 362
                 * the other direction.
                 */
363
                looked_bothways = 1;
364
            }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
365
            len_min = len;
366
            k = i;
367

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
368 369
            if (direction == 1) {
                if (fs_len < this_bs) {
370
                    /* Next can't get better because what we lose by
371 372 373 374
                     * additional uncompressed bits isn't compensated
                     * by a smaller FS part. Vice versa if we are
                     * coming from the other direction.
                     */
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
375
                    if (looked_bothways) {
376
                        break;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
377
                    } else {
378 379 380
                        direction = -direction;
                        looked_bothways = 1;
                        i = state->k;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
381
                    }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
382 383
                } else {
                    while (fs_len > 5 * this_bs) {
384 385 386
                        i++;
                        fs_len /= 5;
                    }
387
                }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
388
            } else if (fs_len > this_bs) {
389
                /* Since we started looking the other way there is no
390 391
                 * need to turn back.
                 */
392 393
                break;
            }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
394
        } else {
395 396 397
            /* Stop looking for better option if we don't see any
             * improvement.
             */
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
398 399 400 401 402 403 404
            if (looked_bothways) {
                break;
            } else {
                direction = -direction;
                looked_bothways = 1;
                i = state->k;
            }
405 406
        }
        if (i + direction < 0
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
407
            || i + direction >= strm->bit_per_sample - 2) {
408 409
            if (looked_bothways)
                break;
410

411 412 413 414 415 416 417
            direction = -direction;
            looked_bothways = 1;
            i = state->k;
        }
        i += direction;
    }
    state->k = k;
418

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
419 420 421 422 423 424 425 426 427 428 429 430
    return len_min;
}

static int count_se_option(uint64_t limit, struct aec_stream *strm)
{
    int i;
    uint64_t d, len;
    struct internal_state *state = strm->state;

    len = 1;

    for (i = 0; i < strm->block_size; i+= 2) {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
431 432
        d = (uint64_t)state->block_p[i]
            + (uint64_t)state->block_p[i + 1];
433
        /* we have to worry about overflow here */
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
434 435
        if (d > limit) {
            len = UINT64_MAX;
436
            break;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
437 438 439
        } else {
            len += d * (d + 1) / 2
                + (uint64_t)state->block_p[i + 1];
440 441
        }
    }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
442 443 444 445 446 447 448
    return len;
}

static int m_select_code_option(struct aec_stream *strm)
{
    uint64_t uncomp_len, split_len, se_len;
    struct internal_state *state = strm->state;
449

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
450 451 452 453
    uncomp_len = (strm->block_size - state->ref)
        * strm->bit_per_sample;
    split_len = count_splitting_option(strm);
    se_len = count_se_option(split_len, strm);
454

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
455 456
    if (split_len < uncomp_len) {
        if (split_len < se_len)
457 458 459
            return m_encode_splitting(strm);
        else
            return m_encode_se(strm);
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
460
    } else {
461 462 463 464 465 466
        if (uncomp_len <= se_len)
            return m_encode_uncomp(strm);
        else
            return m_encode_se(strm);
    }
}
467

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

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

476
    if (state->ref)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
477
    {
478
        emit(state, state->block_p[0], strm->bit_per_sample);
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
479 480 481 482 483 484 485 486 487 488
        for (i = 1; i < strm->block_size; i++)
            emitfs(state, state->block_p[i] >> k);
        if (k) emitblock_1(strm, k);
    }
    else
    {
        for (i = 0; i < strm->block_size; i++)
            emitfs(state, state->block_p[i] >> k);
        if (k) emitblock_0(strm, k);
    }
489

490 491
    return m_flush_block(strm);
}
492

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

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

500 501
    return m_flush_block(strm);
}
502

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

509 510
    emit(state, 1, state->id_len + 1);
    if (state->ref)
511
        emit(state, state->block_p[0], strm->bit_per_sample);
512

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

518 519
    return m_flush_block(strm);
}
520

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

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

527 528
    if (state->zero_ref)
        emit(state, state->zero_ref_sample, strm->bit_per_sample);
529

530 531 532 533 534 535
    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);
536

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

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
541
static int m_flush_block(struct aec_stream *strm)
542
{
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
543 544 545 546 547
    /**
       Flush block in direct_out mode by updating counters.

       Fall back to slow flushing if in buffered mode.
    */
548
    int n;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
549
    struct internal_state *state = strm->state;
550

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
551
    if (state->direct_out) {
552
        n = state->cds_p - strm->next_out;
553 554 555 556 557 558
        strm->next_out += n;
        strm->avail_out -= n;
        strm->total_out += n;
        state->mode = m_get_block;
        return M_CONTINUE;
    }
559

560 561 562 563 564
    state->i = 0;
    state->mode = m_flush_block_cautious;
    return M_CONTINUE;
}

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
565
static int m_flush_block_cautious(struct aec_stream *strm)
566
{
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
567 568 569 570
    /**
       Slow and restartable flushing
    */
    struct internal_state *state = strm->state;
571

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
572
    while(state->cds_buf + state->i < state->cds_p) {
573 574 575
        if (strm->avail_out == 0)
            return M_EXIT;

576
        *strm->next_out++ = state->cds_buf[state->i];
577 578 579 580 581 582 583 584 585 586 587 588 589
        strm->avail_out--;
        strm->total_out++;
        state->i++;
    }
    state->mode = m_get_block;
    return M_CONTINUE;
}

/*
 *
 * API functions
 *
 */
590

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
591
int aec_encode_init(struct aec_stream *strm)
592
{
593
    int bs, bsi;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
594
    struct internal_state *state;
595 596

    if (strm->bit_per_sample > 32 || strm->bit_per_sample == 0)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
597
        return AEC_CONF_ERROR;
598 599 600 601 602

    if (strm->block_size != 8
        && strm->block_size != 16
        && strm->block_size != 32
        && strm->block_size != 64)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
603
        return AEC_CONF_ERROR;
604 605

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

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
608
    state = (struct internal_state *)malloc(sizeof(struct internal_state));
609
    if (state == NULL)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
610
        return AEC_MEM_ERROR;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
611 612

    memset(state, 0, sizeof(struct internal_state));
613 614
    strm->state = state;

615 616 617 618 619
    bs = strm->block_size >> 3;
    bsi = 0;
    while (bs >>= 1)
        bsi++;

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
620
    if (strm->bit_per_sample > 16) {
621
        /* 24/32 input bit settings */
622 623
        state->id_len = 5;

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
624 625
        if (strm->bit_per_sample <= 24
            && strm->flags & AEC_DATA_3BYTE) {
626
            state->block_len = 3 * strm->block_size;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
627
            if (strm->flags & AEC_DATA_MSB) {
628 629
                state->get_sample = get_msb_24;
                state->get_block = get_block_funcs_msb_24[bsi];
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
630
            } else {
631 632
                state->get_sample = get_lsb_24;
                state->get_block = get_block_funcs_lsb_24[bsi];
633
            }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
634
        } else {
635
            state->block_len = 4 * strm->block_size;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
636
            if (strm->flags & AEC_DATA_MSB) {
637 638
                state->get_sample = get_msb_32;
                state->get_block = get_block_funcs_msb_32[bsi];
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
639
            } else {
640 641 642 643
                state->get_sample = get_lsb_32;
                state->get_block = get_block_funcs_lsb_32[bsi];
            }
        }
644
    }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
645
    else if (strm->bit_per_sample > 8) {
646 647
        /* 16 bit settings */
        state->id_len = 4;
648
        state->block_len = 2 * strm->block_size;
649

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
650
        if (strm->flags & AEC_DATA_MSB) {
651
            state->get_sample = get_msb_16;
652
            state->get_block = get_block_funcs_msb_16[bsi];
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
653
        } else {
654
            state->get_sample = get_lsb_16;
655 656
            state->get_block = get_block_funcs_lsb_16[bsi];
        }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
657
    } else {
658 659
        /* 8 bit settings */
        state->id_len = 3;
660
        state->block_len = strm->block_size;
661 662

        state->get_sample = get_8;
663
        state->get_block = get_block_funcs_8[bsi];
664 665
    }

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
666
    if (strm->flags & AEC_DATA_SIGNED) {
667 668
        state->xmin = -(1ULL << (strm->bit_per_sample - 1));
        state->xmax = (1ULL << (strm->bit_per_sample - 1)) - 1;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
669
        state->preprocess = preprocess_signed;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
670
    } else {
671 672
        state->xmin = 0;
        state->xmax = (1ULL << strm->bit_per_sample) - 1;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
673
        state->preprocess = preprocess_unsigned;
674 675
    }

676 677 678
    state->block_buf = (uint32_t *)malloc(strm->rsi
                                         * strm->block_size
                                         * sizeof(uint32_t));
679
    if (state->block_buf == NULL)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
680
        return AEC_MEM_ERROR;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
681

682
    state->block_p = state->block_buf;
683

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
684
    /* Largest possible CDS according to specs */
685 686 687
    state->cds_len = (5 + 64 * 32) / 8 + 3;
    state->cds_buf = (uint8_t *)malloc(state->cds_len);
    if (state->cds_buf == NULL)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
688
        return AEC_MEM_ERROR;
689

690 691 692
    strm->total_in = 0;
    strm->total_out = 0;

693 694 695
    state->cds_p = state->cds_buf;
    *state->cds_p = 0;
    state->bit_p = 8;
696 697
    state->mode = m_get_block;

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
698
    return AEC_OK;
699 700
}

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
701
int aec_encode(struct aec_stream *strm, int flush)
702 703 704 705 706
{
    /**
       Finite-state machine implementation of the adaptive entropy
       encoder.
    */
707
    int n;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
708
    struct internal_state *state;
709 710 711 712 713
    state = strm->state;
    state->flush = flush;

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

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
714
    if (state->direct_out) {
715 716 717 718 719 720 721 722
        n = state->cds_p - strm->next_out;
        strm->next_out += n;
        strm->avail_out -= n;
        strm->total_out += n;

        *state->cds_buf = *state->cds_p;
        state->cds_p = state->cds_buf;
        state->direct_out = 0;
723
    }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
724
    return AEC_OK;
725 726
}

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
727
int aec_encode_end(struct aec_stream *strm)
728
{
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
729
    struct internal_state *state = strm->state;
730

731 732
    free(state->block_buf);
    free(state->cds_buf);
733
    free(state);
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
734
    return AEC_OK;
735
}