4 * @author Mathis Rosenhauer, Deutsches Klimarechenzentrum
5 * @author Moritz Hanke, Deutsches Klimarechenzentrum
6 * @author Joerg Behrens, Deutsches Klimarechenzentrum
7 * @author Luis Kornblueh, Max-Planck-Institut fuer Meteorologie
10 * Copyright 2012 - 2014
12 * Mathis Rosenhauer, Luis Kornblueh
16 * Deutsches Klimarechenzentrum GmbH Max-Planck-Institut fuer Meteorologie
17 * Bundesstr. 45a Bundesstr. 53
18 * 20146 Hamburg 20146 Hamburg
21 * All rights reserved.
23 * Redistribution and use in source and binary forms, with or without
24 * modification, are permitted provided that the following conditions
27 * 1. Redistributions of source code must retain the above copyright
28 * notice, this list of conditions and the following disclaimer.
29 * 2. Redistributions in binary form must reproduce the above
30 * copyright notice, this list of conditions and the following
31 * disclaimer in the documentation and/or other materials provided
32 * with the distribution.
34 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
35 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
36 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
37 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
38 * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
39 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
40 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
41 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
42 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
43 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
44 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
45 * OF THE POSSIBILITY OF SUCH DAMAGE.
47 * @section DESCRIPTION
49 * Adaptive Entropy Decoder
50 * Based on CCSDS documents 121.0-B-2 and 120.0-G-2
70 #define BUFFERSPACE(strm) (strm->avail_in >= strm->state->in_blklen \
71 && strm->avail_out >= strm->state->out_blklen)
74 static void flush_##KIND(struct aec_stream *strm) \
76 uint32_t *bp, *flush_end; \
78 int64_t data, med, half_d, xmin, xmax; \
79 struct internal_state *state = strm->state; \
81 flush_end = state->rsip; \
83 if (state->flush_start == state->rsi_buffer \
84 && state->rsip > state->rsi_buffer) { \
85 state->last_out = *state->rsi_buffer; \
87 if (strm->flags & AEC_DATA_SIGNED) { \
88 m = 1ULL << (strm->bits_per_sample - 1); \
89 /* Reference samples have to be sign extended */ \
90 state->last_out = (state->last_out ^ m) - m; \
92 put_##KIND(strm, state->last_out); \
93 state->flush_start++; \
96 data = state->last_out; \
97 if (strm->flags & AEC_DATA_SIGNED) \
100 med = (state->xmax - state->xmin) / 2 + 1; \
102 xmin = state->xmin; \
103 xmax = state->xmax; \
105 for (bp = state->flush_start; bp < flush_end; bp++) { \
107 half_d = (d + 1) >> 1; \
110 if (half_d <= data - xmin) { \
119 if (half_d <= xmax - data) { \
128 put_##KIND(strm, data); \
130 state->last_out = data; \
132 for (bp = state->flush_start; bp < flush_end; bp++) \
133 put_##KIND(strm, *bp); \
135 state->flush_start = state->rsip; \
139 static inline void put_msb_32(struct aec_stream *strm, uint32_t data)
141 *strm->next_out++ = data >> 24;
142 *strm->next_out++ = data >> 16;
143 *strm->next_out++ = data >> 8;
144 *strm->next_out++ = data;
147 static inline void put_msb_24(struct aec_stream *strm, uint32_t data)
149 *strm->next_out++ = data >> 16;
150 *strm->next_out++ = data >> 8;
151 *strm->next_out++ = data;
154 static inline void put_msb_16(struct aec_stream *strm, uint32_t data)
156 *strm->next_out++ = data >> 8;
157 *strm->next_out++ = data;
160 static inline void put_lsb_32(struct aec_stream *strm, uint32_t data)
162 *strm->next_out++ = data;
163 *strm->next_out++ = data >> 8;
164 *strm->next_out++ = data >> 16;
165 *strm->next_out++ = data >> 24;
168 static inline void put_lsb_24(struct aec_stream *strm, uint32_t data)
170 *strm->next_out++ = data;
171 *strm->next_out++ = data >> 8;
172 *strm->next_out++ = data >> 16;
175 static inline void put_lsb_16(struct aec_stream *strm, uint32_t data)
177 *strm->next_out++ = data;
178 *strm->next_out++ = data >> 8;
181 static inline void put_8(struct aec_stream *strm, uint32_t data)
183 *strm->next_out++ = data;
194 static inline void check_rsi_end(struct aec_stream *strm)
197 Flush output if end of RSI reached
199 struct internal_state *state = strm->state;
201 if (state->rsip - state->rsi_buffer == state->rsi_size) {
202 state->flush_output(strm);
203 state->flush_start = state->rsi_buffer;
204 state->rsip = state->rsi_buffer;
208 static inline void put_sample(struct aec_stream *strm, uint32_t s)
210 struct internal_state *state = strm->state;
213 strm->avail_out -= state->bytes_per_sample;
217 static inline void fill_acc(struct aec_stream *strm)
219 int b = (63 - strm->state->bitp) >> 3;
222 strm->state->bitp += b << 3;
226 strm->state->acc = (strm->state->acc << 8) | *strm->next_in++;
228 strm->state->acc = (strm->state->acc << 8) | *strm->next_in++;
230 strm->state->acc = (strm->state->acc << 8) | *strm->next_in++;
232 strm->state->acc = (strm->state->acc << 8) | *strm->next_in++;
234 strm->state->acc = (strm->state->acc << 8) | *strm->next_in++;
236 strm->state->acc = (strm->state->acc << 8) | *strm->next_in++;
238 strm->state->acc = (strm->state->acc << 8) | *strm->next_in++;
243 static inline uint32_t direct_get(struct aec_stream *strm, unsigned int n)
246 Get n bit from input stream
248 No checking whatsoever. Read bits are dumped.
251 struct internal_state *state = strm->state;
257 return (state->acc >> state->bitp) & ((1ULL << n) - 1);
260 static inline uint32_t direct_get_fs(struct aec_stream *strm)
263 Interpret a Fundamental Sequence from the input buffer.
265 Essentially counts the number of 0 bits until a 1 is
270 #ifdef HAVE_DECL___BUILTIN_CLZLL
273 struct internal_state *state = strm->state;
275 state->acc &= ((1ULL << state->bitp) - 1);
277 while (state->acc == 0) {
283 #ifdef HAVE_DECL___BUILTIN_CLZLL
284 lz = __builtin_clzll(state->acc);
285 fs += lz + state->bitp - 64;
286 state->bitp = 63 - lz;
289 while ((state->acc & (1ULL << state->bitp)) == 0) {
297 static inline uint32_t bits_ask(struct aec_stream *strm, int n)
299 while (strm->state->bitp < n) {
300 if (strm->avail_in == 0)
303 strm->state->acc <<= 8;
304 strm->state->acc |= *strm->next_in++;
305 strm->state->bitp += 8;
310 static inline uint32_t bits_get(struct aec_stream *strm, int n)
312 return (strm->state->acc >> (strm->state->bitp - n))
316 static inline void bits_drop(struct aec_stream *strm, int n)
318 strm->state->bitp -= n;
321 static inline uint32_t fs_ask(struct aec_stream *strm)
323 if (bits_ask(strm, 1) == 0)
325 while ((strm->state->acc & (1ULL << (strm->state->bitp - 1))) == 0) {
326 if (strm->state->bitp == 1) {
327 if (strm->avail_in == 0)
330 strm->state->acc <<= 8;
331 strm->state->acc |= *strm->next_in++;
332 strm->state->bitp += 8;
340 static inline void fs_drop(struct aec_stream *strm)
346 static inline uint32_t copysample(struct aec_stream *strm)
348 if (bits_ask(strm, strm->bits_per_sample) == 0
349 || strm->avail_out == 0)
352 put_sample(strm, bits_get(strm, strm->bits_per_sample));
353 bits_drop(strm, strm->bits_per_sample);
357 static int m_id(struct aec_stream *strm)
359 struct internal_state *state = strm->state;
361 if (state->rsip == state->rsi_buffer) {
362 if(strm->flags & AEC_PAD_RSI)
363 state->bitp -= state->bitp % 8;
369 if (bits_ask(strm, state->id_len) == 0)
371 state->id = bits_get(strm, state->id_len);
372 bits_drop(strm, state->id_len);
373 state->mode = state->id_table[state->id];
378 static int m_split_output(struct aec_stream *strm)
380 struct internal_state *state = strm->state;
381 int k = state->id - 1;
384 if (bits_ask(strm, k) == 0 || strm->avail_out == 0)
386 *state->rsip++ += bits_get(strm, k);
387 strm->avail_out -= state->bytes_per_sample;
389 } while(++state->i < state->n);
396 static int m_split_fs(struct aec_stream *strm)
398 struct internal_state *state = strm->state;
399 int k = state->id - 1;
402 if (fs_ask(strm) == 0)
404 state->rsip[state->i] = state->fs << k;
406 } while(++state->i < state->n);
409 state->mode = m_split_output;
413 static int m_split(struct aec_stream *strm)
416 struct internal_state *state = strm->state;
418 if (BUFFERSPACE(strm)) {
422 *state->rsip++ = direct_get(strm, strm->bits_per_sample);
424 for (i = 0; i < strm->block_size - state->ref; i++)
425 state->rsip[i] = direct_get_fs(strm) << k;
427 for (i = state->ref; i < strm->block_size; i++)
428 *state->rsip++ += direct_get(strm, k);
430 strm->avail_out -= state->out_blklen;
438 if (copysample(strm) == 0)
440 state->n = strm->block_size - 1;
442 state->n = strm->block_size;
446 state->mode = m_split_fs;
450 static int m_zero_output(struct aec_stream *strm)
452 struct internal_state *state = strm->state;
455 if (strm->avail_out == 0)
464 static int m_zero_block(struct aec_stream *strm)
466 int i, zero_blocks, b, zero_bytes;
467 struct internal_state *state = strm->state;
469 if (fs_ask(strm) == 0)
471 zero_blocks = state->fs + 1;
474 if (zero_blocks == ROS) {
475 b = (state->rsip - state->rsi_buffer) / strm->block_size;
476 zero_blocks = MIN(strm->rsi - b, 64 - (b % 64));
477 } else if (zero_blocks > ROS) {
482 i = zero_blocks * strm->block_size - 1;
484 i = zero_blocks * strm->block_size;
486 zero_bytes = i * state->bytes_per_sample;
488 if (strm->avail_out >= zero_bytes) {
489 if (state->rsi_size - (state->rsip - state->rsi_buffer) < i)
492 memset(state->rsip, 0, i * sizeof(uint32_t));
494 strm->avail_out -= zero_bytes;
502 state->mode = m_zero_output;
506 static int m_se_decode(struct aec_stream *strm)
509 struct internal_state *state = strm->state;
511 while(state->i < strm->block_size) {
512 if (fs_ask(strm) == 0)
515 d1 = m - state->se_table[2 * m + 1];
517 if ((state->i & 1) == 0) {
518 if (strm->avail_out == 0)
520 put_sample(strm, state->se_table[2 * m] - d1);
524 if (strm->avail_out == 0)
526 put_sample(strm, d1);
535 static int m_se(struct aec_stream *strm)
539 struct internal_state *state = strm->state;
541 if (BUFFERSPACE(strm)) {
544 while (i < strm->block_size) {
545 m = direct_get_fs(strm);
546 d1 = m - state->se_table[2 * m + 1];
549 put_sample(strm, state->se_table[2 * m] - d1);
552 put_sample(strm, d1);
559 state->mode = m_se_decode;
560 state->i = state->ref;
564 static int m_low_entropy_ref(struct aec_stream *strm)
566 struct internal_state *state = strm->state;
568 if (state->ref && copysample(strm) == 0)
576 state->mode = m_zero_block;
580 static int m_low_entropy(struct aec_stream *strm)
582 struct internal_state *state = strm->state;
584 if (bits_ask(strm, 1) == 0)
586 state->id = bits_get(strm, 1);
588 state->mode = m_low_entropy_ref;
592 static int m_uncomp_copy(struct aec_stream *strm)
594 struct internal_state *state = strm->state;
597 if (copysample(strm) == 0)
605 static int m_uncomp(struct aec_stream *strm)
608 struct internal_state *state = strm->state;
610 if (BUFFERSPACE(strm)) {
611 for (i = 0; i < strm->block_size; i++)
612 *state->rsip++ = direct_get(strm, strm->bits_per_sample);
613 strm->avail_out -= state->out_blklen;
620 state->i = strm->block_size;
621 state->mode = m_uncomp_copy;
625 static void create_se_table(int *table)
630 for (i = 0; i < 13; i++) {
632 for (j = 0; j <= i; j++) {
634 table[2 * k + 1] = ms;
640 int aec_decode_init(struct aec_stream *strm)
643 struct internal_state *state;
645 if (strm->bits_per_sample > 32 || strm->bits_per_sample == 0)
646 return AEC_CONF_ERROR;
648 state = malloc(sizeof(struct internal_state));
650 return AEC_MEM_ERROR;
652 create_se_table(state->se_table);
656 if (strm->bits_per_sample > 16) {
659 if (strm->bits_per_sample <= 24 && strm->flags & AEC_DATA_3BYTE) {
660 state->bytes_per_sample = 3;
661 if (strm->flags & AEC_DATA_MSB)
662 state->flush_output = flush_msb_24;
664 state->flush_output = flush_lsb_24;
666 state->bytes_per_sample = 4;
667 if (strm->flags & AEC_DATA_MSB)
668 state->flush_output = flush_msb_32;
670 state->flush_output = flush_lsb_32;
672 state->out_blklen = strm->block_size
673 * state->bytes_per_sample;
675 else if (strm->bits_per_sample > 8) {
676 state->bytes_per_sample = 2;
678 state->out_blklen = strm->block_size * 2;
679 if (strm->flags & AEC_DATA_MSB)
680 state->flush_output = flush_msb_16;
682 state->flush_output = flush_lsb_16;
684 if (strm->flags & AEC_RESTRICTED) {
685 if (strm->bits_per_sample <= 4) {
686 if (strm->bits_per_sample <= 2)
691 return AEC_CONF_ERROR;
697 state->bytes_per_sample = 1;
698 state->out_blklen = strm->block_size;
699 state->flush_output = flush_8;
702 if (strm->flags & AEC_DATA_SIGNED) {
703 state->xmin = -(1ULL << (strm->bits_per_sample - 1));
704 state->xmax = (1ULL << (strm->bits_per_sample - 1)) - 1;
707 state->xmax = (1ULL << strm->bits_per_sample) - 1;
710 state->in_blklen = (strm->block_size * strm->bits_per_sample
711 + state->id_len) / 8 + 9;
713 modi = 1UL << state->id_len;
714 state->id_table = malloc(modi * sizeof(int (*)(struct aec_stream *)));
715 if (state->id_table == NULL)
716 return AEC_MEM_ERROR;
718 state->id_table[0] = m_low_entropy;
719 for (i = 1; i < modi - 1; i++) {
720 state->id_table[i] = m_split;
722 state->id_table[modi - 1] = m_uncomp;
724 state->rsi_size = strm->rsi * strm->block_size;
725 state->rsi_buffer = malloc(state->rsi_size * sizeof(uint32_t));
726 if (state->rsi_buffer == NULL)
727 return AEC_MEM_ERROR;
732 state->rsip = state->rsi_buffer;
733 state->flush_start = state->rsi_buffer;
736 state->pp = strm->flags & AEC_DATA_PREPROCESS;
741 int aec_decode(struct aec_stream *strm, int flush)
744 Finite-state machine implementation of the adaptive entropy
747 Can work with one byte input und one sample output buffers. If
748 enough buffer space is available, then faster implementations
749 of the states are called. Inspired by zlib.
752 struct internal_state *state = strm->state;
755 strm->total_in += strm->avail_in;
756 strm->total_out += strm->avail_out;
759 status = state->mode(strm);
760 } while (status == M_CONTINUE);
762 if (status == M_ERROR)
763 return AEC_DATA_ERROR;
765 state->flush_output(strm);
767 strm->total_in -= strm->avail_in;
768 strm->total_out -= strm->avail_out;
773 int aec_decode_end(struct aec_stream *strm)
775 struct internal_state *state = strm->state;
777 free(state->id_table);
778 free(state->rsi_buffer);
783 int aec_buffer_decode(struct aec_stream *strm)
787 status = aec_decode_init(strm);
788 if (status != AEC_OK)
791 status = aec_decode(strm, AEC_FLUSH);
792 aec_decode_end(strm);