aed.c 12.6 KB
Newer Older
1
2
3
4
5
6
7
8
9
/* Adaptive Entropy Decoder            */
/* CCSDS 121.0-B-1 and CCSDS 120.0-G-2 */

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <inttypes.h>
#include <string.h>

10
#include "libae.h"
11

12
13
#define SAFE (strm->avail_in >= state->in_blklen        \
              && strm->avail_out >= strm->block_size)
14
15
16
17

#define ROS 5

typedef struct internal_state {
18
19
    const uint8_t *next_in;
    uint32_t *next_out;
20
21
22
    int id;            /* option ID */
    uint32_t id_len;   /* bit length of code option identification key */
    int *id_table;     /* table maps IDs to states */
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
23
    size_t ref_int;    /* reference sample is every ref_int samples */
24
25
26
27
28
29
30
31
32
33
34
35
    uint32_t last_out; /* previous output for post-processing */
    int64_t xmin;      /* minimum integer for post-processing */
    int64_t xmax;      /* maximum integer for post-processing */
    int mode;          /* current mode of FSM */
    size_t in_blklen;  /* length of uncompressed input block
                          should be the longest possible block */
    size_t n, i;       /* counter for samples */
    uint32_t *block;   /* block buffer for split-sample options */
    int se;            /* set if second extension option is selected */
    uint64_t acc;      /* accumulator for currently used bit sequence */
    uint8_t bitp;      /* bit pointer to the next unused bit in accumulator */
    uint32_t fs;       /* last fundamental sequence in accumulator */
36
    int ref;           /* 1 if current block has reference sample */
37
38
39
40
} decode_state;

/* decoding table for the second-extension option */
static const uint32_t second_extension[36][2] = {
41
42
43
44
45
46
47
48
    {0, 0},
    {1, 1}, {1, 1},
    {2, 3}, {2, 3}, {2, 3},
    {3, 6}, {3, 6}, {3, 6}, {3, 6},
    {4, 10}, {4, 10}, {4, 10}, {4, 10}, {4, 10},
    {5, 15}, {5, 15}, {5, 15}, {5, 15}, {5, 15}, {5, 15},
    {6, 21}, {6, 21}, {6, 21}, {6, 21}, {6, 21}, {6, 21}, {6, 21},
    {7, 28}, {7, 28}, {7, 28}, {7, 28}, {7, 28}, {7, 28}, {7, 28}, {7, 28}
49
50
51
52
};

enum
{
53
54
55
56
57
58
59
60
61
62
63
64
    M_ID = 0,
    M_SPLIT,
    M_SPLIT_FS,
    M_SPLIT_OUTPUT,
    M_LOW_ENTROPY,
    M_LOW_ENTROPY_REF,
    M_ZERO_BLOCK,
    M_ZERO_OUTPUT,
    M_SE,
    M_SE_DECODE,
    M_UNCOMP,
    M_UNCOMP_COPY,
65
66
};

67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
static inline void u_put(ae_streamp strm, uint32_t sample)
{
    int64_t x, d, th, D;
    decode_state *state;

    state = strm->state;
    if (strm->pp && (strm->total_out % state->ref_int != 0))
    {
        d = sample;
        x = state->last_out;

        if ((x - state->xmin) < (state->xmax - x))
        {
            th = x - state->xmin;
        }
        else
        {
            th = state->xmax - x;
        }

        if (d <= 2*th)
        {
            if (d & 1)
                D = - (d + 1) / 2;
            else
                D = d / 2;
        } else {
            if (th == x)
                D = d - th;
            else
                D = th - d;
        }
        sample = x + D;
    }
101
    *state->next_out++ = state->last_out = sample;
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
    strm->avail_out--;
    strm->total_out++;
}

static inline uint32_t u_get(ae_streamp strm, unsigned int n)
{
    /**
       Unsafe get n bit from input stream

       No checking whatsoever. Read bits are dumped.
     */

    decode_state *state;

    state = strm->state;
    while (state->bitp < n)
    {
        strm->avail_in--;
        strm->total_in++;
121
        state->acc = (state->acc << 8) + *state->next_in++;
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
        state->bitp += 8;
    }
    state->bitp -= n;
    return (state->acc >> state->bitp) & ((1ULL << n) - 1);
}

static inline uint32_t u_get_fs(ae_streamp strm)
{
    /**
       Interpret a Fundamental Sequence from the input buffer.

       Essentially counts the number of 0 bits until a
       1 is encountered. TODO: faster version.
     */

    uint32_t fs = 0;

    while(u_get(strm, 1) == 0)
        fs++;

    return fs;
}

static inline void fast_split(ae_streamp strm)
146
{
147
    int i, k;
148
149
150
151
152
    decode_state *state;

    state = strm->state;
    k = state->id - 1;

153
    if (state->ref)
154
155
    {
        u_put(strm, u_get(strm, strm->bit_per_sample));
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
156
157
    }

158
    for (i = state->ref; i < strm->block_size; i++)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
159
    {
160
161
162
        state->block[i] = u_get_fs(strm) << k;
    }

163
    for (i = state->ref; i < strm->block_size; i++)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
164
    {
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
        state->block[i] += u_get(strm, k);
        u_put(strm, state->block[i]);
    }
}

static inline void fast_zero(ae_streamp strm)
{
    int i = strm->state->i;

    while (i--)
        u_put(strm, 0);
}

static inline void fast_se(ae_streamp strm)
{
    int i;
    uint32_t gamma, beta, ms, delta1;

183
    i = strm->state->ref;
184
185

    while (i < strm->bit_per_sample)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
186
    {
187
188
189
190
        gamma = u_get_fs(strm);
        beta = second_extension[gamma][0];
        ms = second_extension[gamma][1];
        delta1 = gamma - ms;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
191

192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
        if ((i & 1) == 0)
        {
            u_put(strm, beta - delta1);
            i++;
        }
        u_put(strm, delta1);
        i++;
    }
}

static inline void fast_uncomp(ae_streamp strm)
{
    int i;

    for (i = 0; i < strm->block_size; i++)
        u_put(strm, u_get(strm, strm->bit_per_sample));
208
209
210
211
}

int ae_decode_init(ae_streamp strm)
{
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
    int i, modi;
    decode_state *state;

    /* Some sanity checks */
    if (strm->bit_per_sample > 32 || strm->bit_per_sample == 0)
    {
        return AE_ERRNO;
    }

    /* Internal state for decoder */
    state = (decode_state *) malloc(sizeof(decode_state));
    if (state == NULL)
    {
        return AE_MEM_ERROR;
    }
    strm->state = state;

    if (16 < strm->bit_per_sample)
        state->id_len = 5;
    else if (8 < strm->bit_per_sample)
        state->id_len = 4;
    else
        state->id_len = 3;

    state->ref_int = strm->block_size * strm->segment_size;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
237
    state->in_blklen = (strm->block_size * strm->bit_per_sample
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
                        + state->id_len) / 8 + 1;

    modi = 1UL << state->id_len;
    state->id_table = (int *)malloc(modi * sizeof(int));
    if (state->id_table == NULL)
    {
        return AE_MEM_ERROR;
    }
    state->id_table[0] = M_LOW_ENTROPY;
    for (i = 1; i < modi - 1; i++)
    {
        state->id_table[i] = M_SPLIT;
    }
    state->id_table[modi - 1] = M_UNCOMP;

    state->block = (uint32_t *)malloc(strm->block_size * sizeof(uint32_t));
    if (state->block == NULL)
    {
        return AE_MEM_ERROR;
    }
    strm->total_in = 0;
    strm->total_out = 0;
    state->xmin = 0;
    state->xmax = (1ULL << strm->bit_per_sample) - 1;

    state->bitp = 0;
    state->mode = M_ID;
    return AE_OK;
266
267
}

268
269
270
271
272
273
274
275
276
277
278
#define ASK(n)                                           \
    do {                                                 \
        while (state->bitp < (unsigned)(n))              \
        {                                                \
            if (strm->avail_in == 0) goto req_buffer;    \
            strm->avail_in--;                            \
            strm->total_in++;                            \
            state->acc <<= 8;                            \
            state->acc |= (uint64_t)(*state->next_in++); \
            state->bitp += 8;                            \
        }                                                \
279
    } while (0)
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
280

281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
#define GET(n)                                                  \
    ((state->acc >> (state->bitp - (n))) & ((1ULL << (n)) - 1))

#define DROP(n) state->bitp -= (unsigned)(n)

#define ASKFS()                          \
    do {                                 \
        ASK(1);                          \
        state->fs = 0;                   \
        while (GET(state->fs + 1) == 0)  \
        {                                \
            state->fs++;                 \
            ASK(state->fs + 1);          \
        }                                \
    } while(0)

#define GETFS() state->fs

#define DROPFS() DROP(state->fs + 1)

#define PUT(sample)                                \
    do {                                           \
        if (strm->avail_out == 0) goto req_buffer; \
        u_put(strm, (sample));                     \
    } while (0)

#define COPYSAMPLE()                    \
    do {                                \
        ASK(strm->bit_per_sample);      \
        PUT(GET(strm->bit_per_sample)); \
        DROP(strm->bit_per_sample);     \
    } while (0)


315
316
int ae_decode(ae_streamp strm, int flush)
{
317
318
319
320
321
322
323
324
325
326
    /**
       Finite-state machine implementation of the adaptive entropy
       decoder.

       Can work with one byte input und one sample output buffers. If
       enough buffer space is available, then faster implementations
       of the states are called. Inspired by zlib.
    */

    size_t zero_blocks;
327
    uint32_t gamma, beta, ms, delta1;
328
329
330
331
    int k;
    decode_state *state;

    state = strm->state;
332
333
    state->next_in = strm->next_in;
    state->next_out = strm->next_out;
334
335
336
337
338
339

    for (;;)
    {
        switch(state->mode)
        {
        case M_ID:
340
            if (strm->pp
341
342
343
344
345
346
347
348
                && (strm->total_out / strm->block_size) % strm->segment_size == 0)
                state->ref = 1;
            else
                state->ref = 0;

            ASK(state->id_len);
            state->id = GET(state->id_len);
            DROP(state->id_len);
349
350
351
352
353
354
355
356
357
358
359
            state->mode = state->id_table[state->id];
            break;

        case M_SPLIT:
            if (SAFE)
            {
                fast_split(strm);
                state->mode = M_ID;
                break;
            }

360
            if (state->ref)
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
            {
                COPYSAMPLE();
                state->n = strm->block_size - 1;
            }
            else
            {
                state->n = strm->block_size;
            }

            state->i = state->n;
            state->mode = M_SPLIT_FS;

        case M_SPLIT_FS:
            do
            {
                ASKFS();
377
                state->block[state->i] = GETFS();
378
379
380
381
382
                DROPFS();
            }
            while(--state->i);

            state->i = state->n;
383
            state->mode = M_SPLIT_OUTPUT;
384

385
        case M_SPLIT_OUTPUT:
386
387
388
389
            k = state->id - 1;
            do
            {
                ASK(k);
390
                PUT((state->block[state->i] << k) + GET(k));
391
392
393
394
395
396
397
398
399
400
401
402
403
404
                DROP(k);
            }
            while(--state->i);

            state->mode = M_ID;
            break;

        case M_LOW_ENTROPY:
            ASK(1);
            state->id = GET(1);
            DROP(1);
            state->mode = M_LOW_ENTROPY_REF;

        case M_LOW_ENTROPY_REF:
405
            if (state->ref)
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
                COPYSAMPLE();

            if(state->id == 1)
            {
                state->mode = M_SE;
                break;
            }

            state->mode = M_ZERO_BLOCK;

        case M_ZERO_BLOCK:
            ASKFS();
            zero_blocks = GETFS() + 1;
            DROPFS();

            if (zero_blocks == ROS)
            {
                zero_blocks =  strm->segment_size - (
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
424
                    (strm->total_out / strm->block_size)
425
426
427
428
                    % strm->segment_size);
            }


429
            if (state->ref)
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
                state->i = zero_blocks * strm->block_size - 1;
            else
                state->i = zero_blocks * strm->block_size;

            if (strm->avail_out >= state->i)
            {
                fast_zero(strm);
                state->mode = M_ID;
                break;
            }

            state->mode = M_ZERO_OUTPUT;

        case M_ZERO_OUTPUT:
            do
                PUT(0);
            while(--state->i);

            state->mode = M_ID;
            break;

        case M_SE:
            if (SAFE)
            {
                fast_se(strm);
                state->mode = M_ID;
                break;
            }

            state->mode = M_SE_DECODE;
460
            state->i = state->ref;
461
462

        case M_SE_DECODE:
463
            while(state->i < strm->bit_per_sample)
464
465
            {
                ASKFS();
466
467
468
469
470
471
472
473
474
475
476
477
                gamma = GETFS();
                beta = second_extension[gamma][0];
                ms = second_extension[gamma][1];
                delta1 = gamma - ms;

                if ((state->i & 1) == 0)
                {
                    PUT(beta - delta1);
                    state->i++;
                }

                PUT(delta1);
478
                state->i++;
479
                DROPFS();
480
481
            }

482
            state->mode = M_ID;
483
            break;
Mathis Rosenhauer's avatar
Mathis Rosenhauer committed
484

485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
        case M_UNCOMP:
            if (SAFE)
            {
                fast_uncomp(strm);
                state->mode = M_ID;
                break;
            }

            state->i = strm->block_size;
            state->mode = M_UNCOMP_COPY;

        case M_UNCOMP_COPY:
            do
                COPYSAMPLE();
            while(--state->i);

            state->mode = M_ID;
            break;

        default:
            return AE_STREAM_ERROR;
        }
    }
508
509

req_buffer:
510
511
    strm->next_in = state->next_in;
    strm->next_out = state->next_out;
512
    return AE_OK;
513
}