encode.c 21.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 13 14 15 16
#include <config.h>

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

17 18
#include <stdio.h>
#include <stdlib.h>
19
#include <unistd.h>
20 21
#include <string.h>

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
22 23 24
#include "libaec.h"
#include "encode.h"
#include "encode_accessors.h"
25

26
/* Marker for Remainder Of Segment condition in zero block encoding */
27
#define ROS -1
28 29 30

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

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
31 32 33 34 35 36 37 38 39 40 41 42 43
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
44
{
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
45 46 47 48 49
    /**
       Emit sequence of bits.
     */

    if (bits <= state->bit_p) {
50 51
        state->bit_p -= bits;
        *state->cds_p += data << state->bit_p;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
52
    } else {
53
        bits -= state->bit_p;
54
        *state->cds_p++ += (uint64_t)data >> bits;
55

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
56
        while (bits & ~7) {
57
            bits -= 8;
58
            *state->cds_p++ = data >> bits;
59
        }
60

61 62
        state->bit_p = 8 - bits;
        *state->cds_p = data << state->bit_p;
63
    }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
64 65
}

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
66
static inline void emitfs(struct internal_state *state, int fs)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
67
{
68 69
    /**
       Emits a fundamental sequence.
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
70

71 72
       fs zero bits followed by one 1 bit.
     */
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
73

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
74 75
    for(;;) {
        if (fs < state->bit_p) {
76 77
            state->bit_p -= fs + 1;
            *state->cds_p += 1 << state->bit_p;
78
            break;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
79
        } else {
80 81 82
            fs -= state->bit_p;
            *++state->cds_p = 0;
            state->bit_p = 8;
83 84
        }
    }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
85
}
86

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
87
#define EMITBLOCK(ref)                                          \
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
88 89
    static inline void emitblock_##ref(struct aec_stream *strm, \
                                       int k)                   \
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
90 91 92
    {                                                           \
        int b;                                                  \
        uint64_t a;                                             \
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
93
        struct internal_state *state = strm->state;             \
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
94 95 96 97 98 99 100 101
        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
102
        while(in < in_end) {                                    \
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
103 104 105
            a <<= 56;                                           \
            p = (p % 8) + 56;                                   \
                                                                \
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
106
            while (p > k && in < in_end) {                      \
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123
                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
124
static void preprocess_unsigned(struct aec_stream *strm)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
125 126
{
    int i;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
127
    int64_t theta, Delta, prev;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
128
    struct internal_state *state = strm->state;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
129

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

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
132
    for (i = 1; i < strm->rsi * strm->block_size; i++) {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
133 134 135
        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
136

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

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
149
static void preprocess_signed(struct aec_stream *strm)
150
{
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
151 152
    int i, m;
    int64_t theta, Delta, prev, sample;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
153
    struct internal_state *state = strm->state;
154

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

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
158
    for (i = 1; i < strm->rsi * strm->block_size; i++) {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
159 160 161 162 163
        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
164
        if (0 <= Delta && Delta <= theta) {
165
            state->block_buf[i] = 2 * Delta;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
166
        } else if (-theta <= Delta && Delta < 0) {
167 168
            state->block_buf[i] = 2
                * (Delta < 0 ? -(uint64_t)Delta : Delta) - 1;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
169
        } else {
170 171
            state->block_buf[i] = theta
                + (Delta < 0 ? -(uint64_t)Delta : Delta);
172
        }
173
    }
174
}
175

176 177 178 179 180 181
/*
 *
 * FSM functions
 *
 */

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
182
static int m_get_block(struct aec_stream *strm)
183
{
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
184
    struct internal_state *state = strm->state;
185

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

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
201
    if (state->blocks_avail == 0) {
202 203
        state->ref = 1;
        state->block_p = state->block_buf;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
204

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
205
        if (strm->avail_in >= state->block_len * strm->rsi) {
206
            state->get_block(strm);
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
207
            state->blocks_avail = strm->rsi - 1;
208

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
209
            if (strm->flags & AEC_DATA_PREPROCESS)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
210
                state->preprocess(strm);
211

212
            return m_check_zero_block(strm);
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
213
        } else {
214 215 216
            state->i = 0;
            state->mode = m_get_block_cautious;
        }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
217
    } else {
218 219 220 221
        state->ref = 0;
        state->block_p += strm->block_size;
        state->blocks_avail--;
        return m_check_zero_block(strm);
222
    }
223
    return M_CONTINUE;
224 225
}

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
226
static int input_empty(struct aec_stream *strm)
227
{
228
    int j;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
229 230 231 232 233 234 235 236 237 238 239 240
    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;
            }
241

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
242 243 244 245 246
            emit(state, 0, state->bit_p);
            if (state->direct_out == 0)
                *strm->next_out++ = *state->cds_p;
            strm->avail_out--;
            strm->total_out++;
247

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
248
            return M_EXIT;
249 250
        }
    }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
251 252 253 254 255 256 257 258 259 260 261 262 263 264

    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);
265

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
266
    state->blocks_avail = strm->rsi - 1;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
267
    if (strm->flags & AEC_DATA_PREPROCESS)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
268
        state->preprocess(strm);
269 270

    return m_check_zero_block(strm);
271 272
}

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
273
static int m_check_zero_block(struct aec_stream *strm)
274
{
275
    int i;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
276
    struct internal_state *state = strm->state;
277 278

    i = state->ref;
279
    while(i < strm->block_size && state->block_p[i] == 0)
280 281
        i++;

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
282 283
    if (i == strm->block_size) {
        if (state->zero_blocks == 0) {
284
            state->zero_ref = state->ref;
285
            state->zero_ref_sample = state->block_p[0];
286
        }
287

288
        state->zero_blocks++;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
289

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
290
        if ((strm->rsi - state->blocks_avail) % 64 == 0) {
291 292 293 294 295 296 297
            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
298
    } else if (state->zero_blocks) {
299 300 301 302
        /* The current block isn't zero but we have to emit a previous
         * zero block first. The current block will be handled
         * later.
         */
303 304
        state->block_p -= strm->block_size;
        state->blocks_avail++;
305 306
        state->mode = m_encode_zero;
        return M_CONTINUE;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
307
    }
308 309
    state->mode = m_select_code_option;
    return M_CONTINUE;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
310 311
}

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
312
static uint64_t block_fs(struct aec_stream *strm, int k)
313
{
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342
    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;
}
343

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
344 345
static int count_splitting_option(struct aec_stream *strm)
{
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392
    /**
       Find the best point for splitting samples in a block.

       In Rice coding each sample in a block of samples is split at
       the same position into k LSB and bit_per_sample - k MSB. The
       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. Two
       additional checks are used to speed up the process:

       1. If we are increasing k to find the minimum then we know that
       k+1 will at most eliminate the FS part. OTOH we gain block_size
       bits in length through the increased binary part. So if the FS
       lenth is already less than the block size then the length of
       the CDS for k+1 will be larger than for k. The same can be done
       for decreasing k.

       2. If 1. is not the case then we have to continue looking. The
       next step would be to increase k by one and evaluate the CDS
       length. A lower limit for the k+1 FS length is
       0.5*(FS_len-block_size). If half of that is more than
       block_size then we can skip k+1 altogether. This reduces to the
       condition:

       if (fs_len > 5 * block_size)
           k++;

       We can be repeat this step while the condition is met to skip
       several k.
     */

    int k, k_min;
    int this_bs; /* Block size of current block */
    int min_dir; /* 1 if we saw a decrease in CDS length */
    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) */

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
393
    struct internal_state *state = strm->state;
394

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
395 396
    this_bs = strm->block_size - state->ref;
    len_min = UINT64_MAX;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
397 398 399
    k = k_min = state->k;
    dir = 1;
    min_dir = 0;
400

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
401
    for (;;) {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
402 403
        fs_len = block_fs(strm, k);
        len = fs_len + this_bs * (k + 1);
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
404 405

        if (len < len_min) {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
406 407 408
            if (len_min < UINT64_MAX)
                min_dir = 1;

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
409
            len_min = len;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
410
            k_min = k;
411

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
412
            if (dir) {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
413
                if (fs_len < this_bs) {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
414
                    goto reverse;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
415 416
                } else {
                    while (fs_len > 5 * this_bs) {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
417
                        k++;
418 419
                        fs_len /= 5;
                    }
420
                }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
421 422 423 424 425

                if (k >= state->kmax)
                    goto reverse;
                else
                    k++;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
426
            } else {
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
427 428 429 430
                if (fs_len >= this_bs || k == 0)
                    break;

                k--;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
431
            }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
432 433
        } else {
            goto reverse;
434
        }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
435 436 437 438 439 440 441 442 443
        continue;

    reverse:
        if (min_dir || state->k == 0)
            break;

        k = state->k - 1;
        dir = 0;
        min_dir = 1;
444
    }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
445
    state->k = k_min;
446

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
447 448 449 450 451 452 453 454 455 456 457 458
    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
459 460
        d = (uint64_t)state->block_p[i]
            + (uint64_t)state->block_p[i + 1];
461
        /* we have to worry about overflow here */
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
462 463
        if (d > limit) {
            len = UINT64_MAX;
464
            break;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
465 466 467
        } else {
            len += d * (d + 1) / 2
                + (uint64_t)state->block_p[i + 1];
468 469
        }
    }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
470 471 472 473 474 475 476
    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;
477

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
478 479 480 481
    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);
482

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
483 484
    if (split_len < uncomp_len) {
        if (split_len < se_len)
485 486 487
            return m_encode_splitting(strm);
        else
            return m_encode_se(strm);
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
488
    } else {
489 490 491 492 493 494
        if (uncomp_len <= se_len)
            return m_encode_uncomp(strm);
        else
            return m_encode_se(strm);
    }
}
495

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
496
static int m_encode_splitting(struct aec_stream *strm)
497 498
{
    int i;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
499
    struct internal_state *state = strm->state;
500
    int k = state->k;
501

502
    emit(state, k + 1, state->id_len);
503

504
    if (state->ref)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
505
    {
506
        emit(state, state->block_p[0], strm->bit_per_sample);
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
507 508 509 510 511 512 513 514 515 516
        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);
    }
517

518 519
    return m_flush_block(strm);
}
520

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

525
    emit(state, (1 << state->id_len) - 1, state->id_len);
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
526
    emitblock_0(strm, strm->bit_per_sample);
527

528 529
    return m_flush_block(strm);
}
530

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
531
static int m_encode_se(struct aec_stream *strm)
532 533
{
    int i;
534
    uint32_t d;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
535
    struct internal_state *state = strm->state;
536

537 538
    emit(state, 1, state->id_len + 1);
    if (state->ref)
539
        emit(state, state->block_p[0], strm->bit_per_sample);
540

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
541
    for (i = 0; i < strm->block_size; i+= 2) {
542 543
        d = state->block_p[i] + state->block_p[i + 1];
        emitfs(state, d * (d + 1) / 2 + state->block_p[i + 1]);
544
    }
545

546 547
    return m_flush_block(strm);
}
548

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

553
    emit(state, 0, state->id_len + 1);
554

555 556
    if (state->zero_ref)
        emit(state, state->zero_ref_sample, strm->bit_per_sample);
557

558 559 560 561 562 563
    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);
564

565 566 567
    state->zero_blocks = 0;
    return m_flush_block(strm);
}
568

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
569
static int m_flush_block(struct aec_stream *strm)
570
{
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
571 572 573 574 575
    /**
       Flush block in direct_out mode by updating counters.

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

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
579
    if (state->direct_out) {
580
        n = state->cds_p - strm->next_out;
581 582 583 584 585 586
        strm->next_out += n;
        strm->avail_out -= n;
        strm->total_out += n;
        state->mode = m_get_block;
        return M_CONTINUE;
    }
587

588 589 590 591 592
    state->i = 0;
    state->mode = m_flush_block_cautious;
    return M_CONTINUE;
}

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
593
static int m_flush_block_cautious(struct aec_stream *strm)
594
{
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
595 596 597 598
    /**
       Slow and restartable flushing
    */
    struct internal_state *state = strm->state;
599

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
600
    while(state->cds_buf + state->i < state->cds_p) {
601 602 603
        if (strm->avail_out == 0)
            return M_EXIT;

604
        *strm->next_out++ = state->cds_buf[state->i];
605 606 607 608 609 610 611 612 613 614 615 616 617
        strm->avail_out--;
        strm->total_out++;
        state->i++;
    }
    state->mode = m_get_block;
    return M_CONTINUE;
}

/*
 *
 * API functions
 *
 */
618

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
619
int aec_encode_init(struct aec_stream *strm)
620
{
621
    int bs, bsi;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
622
    struct internal_state *state;
623 624

    if (strm->bit_per_sample > 32 || strm->bit_per_sample == 0)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
625
        return AEC_CONF_ERROR;
626 627 628 629 630

    if (strm->block_size != 8
        && strm->block_size != 16
        && strm->block_size != 32
        && strm->block_size != 64)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
631
        return AEC_CONF_ERROR;
632 633

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

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
636
    state = (struct internal_state *)malloc(sizeof(struct internal_state));
637
    if (state == NULL)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
638
        return AEC_MEM_ERROR;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
639 640

    memset(state, 0, sizeof(struct internal_state));
641 642
    strm->state = state;

643 644 645 646 647
    bs = strm->block_size >> 3;
    bsi = 0;
    while (bs >>= 1)
        bsi++;

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
648
    if (strm->bit_per_sample > 16) {
649
        /* 24/32 input bit settings */
650 651
        state->id_len = 5;

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
652 653
        if (strm->bit_per_sample <= 24
            && strm->flags & AEC_DATA_3BYTE) {
654
            state->block_len = 3 * strm->block_size;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
655
            if (strm->flags & AEC_DATA_MSB) {
656 657
                state->get_sample = get_msb_24;
                state->get_block = get_block_funcs_msb_24[bsi];
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
658
            } else {
659 660
                state->get_sample = get_lsb_24;
                state->get_block = get_block_funcs_lsb_24[bsi];
661
            }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
662
        } else {
663
            state->block_len = 4 * strm->block_size;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
664
            if (strm->flags & AEC_DATA_MSB) {
665 666
                state->get_sample = get_msb_32;
                state->get_block = get_block_funcs_msb_32[bsi];
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
667
            } else {
668 669 670 671
                state->get_sample = get_lsb_32;
                state->get_block = get_block_funcs_lsb_32[bsi];
            }
        }
672
    }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
673
    else if (strm->bit_per_sample > 8) {
674 675
        /* 16 bit settings */
        state->id_len = 4;
676
        state->block_len = 2 * strm->block_size;
677

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
678
        if (strm->flags & AEC_DATA_MSB) {
679
            state->get_sample = get_msb_16;
680
            state->get_block = get_block_funcs_msb_16[bsi];
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
681
        } else {
682
            state->get_sample = get_lsb_16;
683 684
            state->get_block = get_block_funcs_lsb_16[bsi];
        }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
685
    } else {
686 687
        /* 8 bit settings */
        state->id_len = 3;
688
        state->block_len = strm->block_size;
689 690

        state->get_sample = get_8;
691
        state->get_block = get_block_funcs_8[bsi];
692 693
    }

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
694
    if (strm->flags & AEC_DATA_SIGNED) {
695 696
        state->xmin = -(1ULL << (strm->bit_per_sample - 1));
        state->xmax = (1ULL << (strm->bit_per_sample - 1)) - 1;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
697
        state->preprocess = preprocess_signed;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
698
    } else {
699 700
        state->xmin = 0;
        state->xmax = (1ULL << strm->bit_per_sample) - 1;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
701
        state->preprocess = preprocess_unsigned;
702 703
    }

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

706 707 708
    state->block_buf = (uint32_t *)malloc(strm->rsi
                                         * strm->block_size
                                         * sizeof(uint32_t));
709
    if (state->block_buf == NULL)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
710
        return AEC_MEM_ERROR;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
711

712
    state->block_p = state->block_buf;
713

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
714
    /* Largest possible CDS according to specs */
715 716 717
    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
718
        return AEC_MEM_ERROR;
719

720 721 722
    strm->total_in = 0;
    strm->total_out = 0;

723 724 725
    state->cds_p = state->cds_buf;
    *state->cds_p = 0;
    state->bit_p = 8;
726 727
    state->mode = m_get_block;

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
728
    return AEC_OK;
729 730
}

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
731
int aec_encode(struct aec_stream *strm, int flush)
732 733 734 735 736
{
    /**
       Finite-state machine implementation of the adaptive entropy
       encoder.
    */
737
    int n;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
738
    struct internal_state *state;
739 740 741 742 743
    state = strm->state;
    state->flush = flush;

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

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
744
    if (state->direct_out) {
745 746 747 748 749 750 751 752
        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;
753
    }
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
754
    return AEC_OK;
755 756
}

Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
757
int aec_encode_end(struct aec_stream *strm)
758
{
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
759
    struct internal_state *state = strm->state;
760

761 762
    free(state->block_buf);
    free(state->cds_buf);
763
    free(state);
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
764
    return AEC_OK;
765
}