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
}