5 * Copyright 2012 - 2015
7 * Mathis Rosenhauer, Moritz Hanke, Joerg Behrens
8 * Deutsches Klimarechenzentrum GmbH
10 * 20146 Hamburg Germany
13 * Max-Planck-Institut fuer Meteorologie
18 * All rights reserved.
20 * Redistribution and use in source and binary forms, with or without
21 * modification, are permitted provided that the following conditions
24 * 1. Redistributions of source code must retain the above copyright
25 * notice, this list of conditions and the following disclaimer.
26 * 2. Redistributions in binary form must reproduce the above
27 * copyright notice, this list of conditions and the following
28 * disclaimer in the documentation and/or other materials provided
29 * with the distribution.
31 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
32 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
33 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
34 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
35 * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
36 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
37 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
38 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
39 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
40 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
41 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
42 * OF THE POSSIBILITY OF SUCH DAMAGE.
44 * @section DESCRIPTION
46 * Adaptive Entropy Encoder
47 * Based on CCSDS documents 121.0-B-2 and 120.0-G-3
57 #include "encode_accessors.h"
59 static int m_get_block(struct aec_stream *strm);
61 static inline void emit(struct internal_state *state,
62 uint32_t data, int bits)
65 Emit sequence of bits.
68 if (bits <= state->bits) {
70 *state->cds += (uint8_t)(data << state->bits);
73 *state->cds++ += (uint8_t)((uint64_t)data >> bits);
77 *state->cds++ = (uint8_t)(data >> bits);
80 state->bits = 8 - bits;
81 *state->cds = (uint8_t)(data << state->bits);
85 static inline void emitfs(struct internal_state *state, int fs)
88 Emits a fundamental sequence.
90 fs zero bits followed by one 1 bit.
94 if (fs < state->bits) {
95 state->bits -= fs + 1;
96 *state->cds += 1U << state->bits;
106 static inline void copy64(uint8_t *dst, uint64_t src)
108 dst[0] = (uint8_t)(src >> 56);
109 dst[1] = (uint8_t)(src >> 48);
110 dst[2] = (uint8_t)(src >> 40);
111 dst[3] = (uint8_t)(src >> 32);
112 dst[4] = (uint8_t)(src >> 24);
113 dst[5] = (uint8_t)(src >> 16);
114 dst[6] = (uint8_t)(src >> 8);
115 dst[7] = (uint8_t)src;
118 static inline void emitblock_fs(struct aec_stream *strm, int k, int ref)
121 uint32_t used; /* used bits in 64 bit accumulator */
122 uint64_t acc; /* accumulator */
123 struct internal_state *state = strm->state;
125 acc = (uint64_t)*state->cds << 56;
126 used = 7 - state->bits;
128 for (i = ref; i < strm->block_size; i++) {
129 used += (state->block[i] >> k) + 1;
131 copy64(state->cds, acc);
136 acc |= UINT64_C(1) << (63 - used);
139 copy64(state->cds, acc);
140 state->cds += used >> 3;
141 state->bits = 7 - (used & 7);
144 static inline void emitblock(struct aec_stream *strm, int k, int ref)
147 Emit the k LSB of a whole block of input data.
151 struct internal_state *state = strm->state;
152 uint32_t *in = state->block + ref;
153 uint32_t *in_end = state->block + strm->block_size;
154 uint64_t mask = (UINT64_C(1) << k) - 1;
155 uint8_t *o = state->cds;
164 while (p > k && in < in_end) {
166 a += ((uint64_t)(*in++) & mask) << p;
171 o[0] = (uint8_t)(a >> 56);
172 o[1] = (uint8_t)(a >> 48);
173 o[2] = (uint8_t)(a >> 40);
174 o[3] = (uint8_t)(a >> 32);
175 o[4] = (uint8_t)(a >> 24);
176 o[5] = (uint8_t)(a >> 16);
177 o[6] = (uint8_t)(a >> 8);
181 o[0] = (uint8_t)(a >> 56);
182 o[1] = (uint8_t)(a >> 48);
183 o[2] = (uint8_t)(a >> 40);
184 o[3] = (uint8_t)(a >> 32);
185 o[4] = (uint8_t)(a >> 24);
186 o[5] = (uint8_t)(a >> 16);
191 o[0] = (uint8_t)(a >> 56);
192 o[1] = (uint8_t)(a >> 48);
193 o[2] = (uint8_t)(a >> 40);
194 o[3] = (uint8_t)(a >> 32);
195 o[4] = (uint8_t)(a >> 24);
200 o[0] = (uint8_t)(a >> 56);
201 o[1] = (uint8_t)(a >> 48);
202 o[2] = (uint8_t)(a >> 40);
203 o[3] = (uint8_t)(a >> 32);
208 o[0] = (uint8_t)(a >> 56);
209 o[1] = (uint8_t)(a >> 48);
210 o[2] = (uint8_t)(a >> 40);
215 o[0] = (uint8_t)(a >> 56);
216 o[1] = (uint8_t)(a >> 48);
221 *o++ = (uint8_t)(a >> 56);
235 static void preprocess_unsigned(struct aec_stream *strm)
238 Preprocess RSI of unsigned samples.
240 Combining preprocessing and converting to uint32_t in one loop
241 is slower due to the data dependance on x_i-1.
245 struct internal_state *state = strm->state;
246 const uint32_t *restrict x = state->data_raw;
247 uint32_t *restrict d = state->data_pp;
248 uint32_t xmax = state->xmax;
249 int rsi = (int)strm->rsi * strm->block_size - 1;
253 state->ref_sample = x[0];
255 for (i = 0; i < rsi; i++) {
256 if (x[i + 1] >= x[i]) {
264 if (D <= xmax - x[i])
265 d[i + 1] = 2 * D - 1;
267 d[i + 1] = xmax - x[i + 1];
270 state->uncomp_len = (strm->block_size - 1) * strm->bits_per_sample;
273 static void preprocess_signed(struct aec_stream *strm)
276 Preprocess RSI of signed samples.
280 struct internal_state *state = strm->state;
281 int32_t *restrict x = (int32_t *)state->data_raw;
282 uint32_t *restrict d = state->data_pp;
283 int32_t xmax = (int32_t)state->xmax;
284 int32_t xmin = (int32_t)state->xmin;
285 int rsi = (int)strm->rsi * strm->block_size - 1;
286 uint32_t m = UINT64_C(1) << (strm->bits_per_sample - 1);
290 state->ref_sample = x[0];
292 x[0] = (x[0] ^ m) - m;
294 for (i = 0; i < rsi; i++) {
295 x[i + 1] = (x[i + 1] ^ m) - m;
296 if (x[i + 1] < x[i]) {
297 D = (uint32_t)(x[i] - x[i + 1]);
298 if (D <= (uint32_t)(xmax - x[i]))
299 d[i + 1] = 2 * D - 1;
301 d[i + 1] = xmax - x[i + 1];
303 D = (uint32_t)(x[i + 1] - x[i]);
304 if (D <= (uint32_t)(x[i] - xmin))
307 d[i + 1] = x[i + 1] - xmin;
310 state->uncomp_len = (strm->block_size - 1) * strm->bits_per_sample;
313 static inline uint64_t block_fs(struct aec_stream *strm, int k)
316 Sum FS of all samples in block for given splitting position.
321 struct internal_state *state = strm->state;
323 for (i = 0; i < strm->block_size; i++)
324 fs += (uint64_t)(state->block[i] >> k);
329 static uint32_t assess_splitting_option(struct aec_stream *strm)
332 Length of CDS encoded with splitting option and optimal k.
334 In Rice coding each sample in a block of samples is split at
335 the same position into k LSB and bits_per_sample - k MSB. The
336 LSB part is left binary and the MSB part is coded as a
337 fundamental sequence a.k.a. unary (see CCSDS 121.0-B-2). The
338 function of the length of the Coded Data Set (CDS) depending on
339 k has exactly one minimum (see A. Kiely, IPN Progress Report
342 To find that minimum with only a few costly evaluations of the
343 CDS length, we start with the k of the previous CDS. K is
344 increased and the CDS length evaluated. If the CDS length gets
345 smaller, then we are moving towards the minimum. If the length
346 increases, then the minimum will be found with smaller k.
348 For increasing k we know that we will gain block_size bits in
349 length through the larger binary part. If the FS lenth is less
350 than the block size then a reduced FS part can't compensate the
351 larger binary part. So we know that the CDS for k+1 will be
352 larger than for k without actually computing the length. An
353 analogue check can be done for decreasing k.
358 int this_bs; /* Block size of current block */
359 int no_turn; /* 1 if we shouldn't reverse */
360 int dir; /* Direction, 1 means increasing k, 0 decreasing k */
361 uint64_t len; /* CDS length for current k */
362 uint64_t len_min; /* CDS length minimum so far */
363 uint64_t fs_len; /* Length of FS part (not including 1s) */
365 struct internal_state *state = strm->state;
367 this_bs = strm->block_size - state->ref;
368 len_min = UINT64_MAX;
369 k = k_min = state->k;
374 fs_len = block_fs(strm, k);
375 len = fs_len + this_bs * (k + 1);
378 if (len_min < UINT64_MAX)
385 if (fs_len < this_bs || k >= state->kmax) {
395 if (fs_len >= this_bs || k == 0)
409 return (uint32_t)len_min;
412 static uint32_t assess_se_option(struct aec_stream *strm)
415 Length of CDS encoded with Second Extension option.
417 If length is above limit just return UINT32_MAX.
422 struct internal_state *state = strm->state;
423 uint32_t *block = state->block;
427 for (i = 0; i < strm->block_size; i += 2) {
428 d = (uint64_t)block[i] + (uint64_t)block[i + 1];
429 len += d * (d + 1) / 2 + block[i + 1] + 1;
430 if (len > state->uncomp_len)
433 return (uint32_t)len;
436 static void init_output(struct aec_stream *strm)
439 Direct output to next_out if next_out can hold a Coded Data
440 Set, use internal buffer otherwise.
443 struct internal_state *state = strm->state;
445 if (strm->avail_out > CDSLEN) {
446 if (!state->direct_out) {
447 state->direct_out = 1;
448 *strm->next_out = *state->cds;
449 state->cds = strm->next_out;
452 if (state->zero_blocks == 0 || state->direct_out) {
453 /* copy leftover from last block */
454 *state->cds_buf = *state->cds;
455 state->cds = state->cds_buf;
457 state->direct_out = 0;
467 static int m_flush_block_resumable(struct aec_stream *strm)
470 Slow and restartable flushing
472 struct internal_state *state = strm->state;
474 int n = (int)MIN((size_t)(state->cds - state->cds_buf - state->i),
476 memcpy(strm->next_out, state->cds_buf + state->i, n);
478 strm->avail_out -= n;
481 if (strm->avail_out == 0) {
484 state->mode = m_get_block;
489 static int m_flush_block(struct aec_stream *strm)
492 Flush block in direct_out mode by updating counters.
494 Fall back to slow flushing if in buffered mode.
497 struct internal_state *state = strm->state;
499 #ifdef ENABLE_RSI_PADDING
500 if (state->blocks_avail == 0
501 && strm->flags & AEC_PAD_RSI
502 && state->block_nonzero == 0
504 emit(state, 0, state->bits % 8);
507 if (state->direct_out) {
508 n = (int)(state->cds - strm->next_out);
510 strm->avail_out -= n;
511 state->mode = m_get_block;
516 state->mode = m_flush_block_resumable;
520 static int m_encode_splitting(struct aec_stream *strm)
522 struct internal_state *state = strm->state;
525 emit(state, k + 1, state->id_len);
527 emit(state, state->ref_sample, strm->bits_per_sample);
529 emitblock_fs(strm, k, state->ref);
531 emitblock(strm, k, state->ref);
533 return m_flush_block(strm);
536 static int m_encode_uncomp(struct aec_stream *strm)
538 struct internal_state *state = strm->state;
540 emit(state, (1U << state->id_len) - 1, state->id_len);
542 state->block[0] = state->ref_sample;
543 emitblock(strm, strm->bits_per_sample, 0);
544 return m_flush_block(strm);
547 static int m_encode_se(struct aec_stream *strm)
551 struct internal_state *state = strm->state;
553 emit(state, 1, state->id_len + 1);
555 emit(state, state->ref_sample, strm->bits_per_sample);
557 for (i = 0; i < strm->block_size; i+= 2) {
558 d = state->block[i] + state->block[i + 1];
559 emitfs(state, d * (d + 1) / 2 + state->block[i + 1]);
562 return m_flush_block(strm);
565 static int m_encode_zero(struct aec_stream *strm)
567 struct internal_state *state = strm->state;
569 emit(state, 0, state->id_len + 1);
572 emit(state, state->zero_ref_sample, strm->bits_per_sample);
574 if (state->zero_blocks == ROS)
576 else if (state->zero_blocks >= 5)
577 emitfs(state, state->zero_blocks);
579 emitfs(state, state->zero_blocks - 1);
581 state->zero_blocks = 0;
582 return m_flush_block(strm);
585 static int m_select_code_option(struct aec_stream *strm)
588 Decide which code option to use.
593 struct internal_state *state = strm->state;
595 if (state->id_len > 1)
596 split_len = assess_splitting_option(strm);
598 split_len = UINT32_MAX;
599 se_len = assess_se_option(strm);
601 if (split_len < state->uncomp_len) {
602 if (split_len < se_len)
603 return m_encode_splitting(strm);
605 return m_encode_se(strm);
607 if (state->uncomp_len <= se_len)
608 return m_encode_uncomp(strm);
610 return m_encode_se(strm);
614 static int m_check_zero_block(struct aec_stream *strm)
617 Check if input block is all zero.
619 Aggregate consecutive zero blocks until we find !0 or reach the
620 end of a segment or RSI.
624 struct internal_state *state = strm->state;
625 uint32_t *p = state->block;
627 for (i = 0; i < strm->block_size; i++)
631 if (i < strm->block_size) {
632 if (state->zero_blocks) {
633 /* The current block isn't zero but we have to emit a
634 * previous zero block first. The current block will be
635 * flagged and handled later.
637 state->block_nonzero = 1;
638 state->mode = m_encode_zero;
641 state->mode = m_select_code_option;
644 state->zero_blocks++;
645 if (state->zero_blocks == 1) {
646 state->zero_ref = state->ref;
647 state->zero_ref_sample = state->ref_sample;
649 if (state->blocks_avail == 0
650 || (strm->rsi - state->blocks_avail) % 64 == 0) {
651 if (state->zero_blocks > 4)
652 state->zero_blocks = ROS;
653 state->mode = m_encode_zero;
656 state->mode = m_get_block;
661 static int m_get_rsi_resumable(struct aec_stream *strm)
664 Get RSI while input buffer is short.
666 Let user provide more input. Once we got all input pad buffer
670 struct internal_state *state = strm->state;
673 if (strm->avail_in >= state->bytes_per_sample) {
674 state->data_raw[state->i] = state->get_sample(strm);
676 if (state->flush == AEC_FLUSH) {
678 state->blocks_avail = state->i / strm->block_size - 1;
679 if (state->i % strm->block_size)
680 state->blocks_avail++;
682 state->data_raw[state->i] =
683 state->data_raw[state->i - 1];
684 while(++state->i < strm->rsi * strm->block_size);
686 /* Finish encoding by padding the last byte with
688 emit(state, 0, state->bits);
689 if (strm->avail_out > 0) {
690 if (!state->direct_out)
691 *strm->next_out++ = *state->cds;
701 } while (++state->i < strm->rsi * strm->block_size);
703 if (strm->flags & AEC_DATA_PREPROCESS)
704 state->preprocess(strm);
706 return m_check_zero_block(strm);
709 static int m_get_block(struct aec_stream *strm)
712 Provide the next block of preprocessed input data.
714 Pull in a whole Reference Sample Interval (RSI) of data if
715 block buffer is empty.
718 struct internal_state *state = strm->state;
722 if (state->block_nonzero) {
723 state->block_nonzero = 0;
724 state->mode = m_select_code_option;
728 if (state->blocks_avail == 0) {
729 state->blocks_avail = strm->rsi - 1;
730 state->block = state->data_pp;
732 if (strm->avail_in >= state->rsi_len) {
733 state->get_rsi(strm);
734 if (strm->flags & AEC_DATA_PREPROCESS)
735 state->preprocess(strm);
737 return m_check_zero_block(strm);
740 state->mode = m_get_rsi_resumable;
745 state->uncomp_len = strm->block_size * strm->bits_per_sample;
747 state->block += strm->block_size;
748 state->blocks_avail--;
749 return m_check_zero_block(strm);
754 static void cleanup(struct aec_stream *strm)
756 struct internal_state *state = strm->state;
758 if (strm->flags & AEC_DATA_PREPROCESS && state->data_raw)
759 free(state->data_raw);
761 free(state->data_pp);
771 int aec_encode_init(struct aec_stream *strm)
773 struct internal_state *state;
775 if (strm->bits_per_sample > 32 || strm->bits_per_sample == 0)
776 return AEC_CONF_ERROR;
778 if (strm->flags & AEC_NOT_ENFORCE) {
779 /* All even block sizes are allowed. */
780 if (strm->block_size & 1)
781 return AEC_CONF_ERROR;
783 /* Only allow standard conforming block sizes */
784 if (strm->block_size != 8
785 && strm->block_size != 16
786 && strm->block_size != 32
787 && strm->block_size != 64)
788 return AEC_CONF_ERROR;
791 if (strm->rsi > 4096)
792 return AEC_CONF_ERROR;
794 state = malloc(sizeof(struct internal_state));
796 return AEC_MEM_ERROR;
798 memset(state, 0, sizeof(struct internal_state));
800 state->uncomp_len = strm->block_size * strm->bits_per_sample;
802 if (strm->bits_per_sample > 16) {
803 /* 24/32 input bit settings */
806 if (strm->bits_per_sample <= 24
807 && strm->flags & AEC_DATA_3BYTE) {
808 state->bytes_per_sample = 3;
809 if (strm->flags & AEC_DATA_MSB) {
810 state->get_sample = aec_get_msb_24;
811 state->get_rsi = aec_get_rsi_msb_24;
813 state->get_sample = aec_get_lsb_24;
814 state->get_rsi = aec_get_rsi_lsb_24;
817 state->bytes_per_sample = 4;
818 if (strm->flags & AEC_DATA_MSB) {
819 state->get_sample = aec_get_msb_32;
820 state->get_rsi = aec_get_rsi_msb_32;
822 state->get_sample = aec_get_lsb_32;
823 state->get_rsi = aec_get_rsi_lsb_32;
827 else if (strm->bits_per_sample > 8) {
828 /* 16 bit settings */
830 state->bytes_per_sample = 2;
832 if (strm->flags & AEC_DATA_MSB) {
833 state->get_sample = aec_get_msb_16;
834 state->get_rsi = aec_get_rsi_msb_16;
836 state->get_sample = aec_get_lsb_16;
837 state->get_rsi = aec_get_rsi_lsb_16;
841 if (strm->flags & AEC_RESTRICTED) {
842 if (strm->bits_per_sample <= 4) {
843 if (strm->bits_per_sample <= 2)
848 return AEC_CONF_ERROR;
853 state->bytes_per_sample = 1;
855 state->get_sample = aec_get_8;
856 state->get_rsi = aec_get_rsi_8;
858 state->rsi_len = strm->rsi * strm->block_size * state->bytes_per_sample;
860 if (strm->flags & AEC_DATA_SIGNED) {
861 state->xmax = UINT32_MAX >> (32 - strm->bits_per_sample + 1);
862 state->xmin = ~state->xmax;
863 state->preprocess = preprocess_signed;
866 state->xmax = UINT32_MAX >> (32 - strm->bits_per_sample);
867 state->preprocess = preprocess_unsigned;
870 state->kmax = (1U << state->id_len) - 3;
872 state->data_pp = malloc(strm->rsi
875 if (state->data_pp == NULL) {
877 return AEC_MEM_ERROR;
880 if (strm->flags & AEC_DATA_PREPROCESS) {
881 state->data_raw = malloc(strm->rsi
884 if (state->data_raw == NULL) {
886 return AEC_MEM_ERROR;
889 state->data_raw = state->data_pp;
892 state->block = state->data_pp;
899 state->cds = state->cds_buf;
902 state->mode = m_get_block;
907 int aec_encode(struct aec_stream *strm, int flush)
910 Finite-state machine implementation of the adaptive entropy
914 struct internal_state *state = strm->state;
916 state->flush = flush;
917 strm->total_in += strm->avail_in;
918 strm->total_out += strm->avail_out;
920 while (state->mode(strm) == M_CONTINUE);
922 if (state->direct_out) {
923 n = (int)(state->cds - strm->next_out);
925 strm->avail_out -= n;
927 *state->cds_buf = *state->cds;
928 state->cds = state->cds_buf;
929 state->direct_out = 0;
931 strm->total_in -= strm->avail_in;
932 strm->total_out -= strm->avail_out;
936 int aec_encode_end(struct aec_stream *strm)
938 struct internal_state *state = strm->state;
942 if (state->flush == AEC_FLUSH && state->flushed == 0)
943 status = AEC_STREAM_ERROR;
948 int aec_buffer_encode(struct aec_stream *strm)
952 status = aec_encode_init(strm);
953 if (status != AEC_OK)
955 status = aec_encode(strm, AEC_FLUSH);
956 if (status != AEC_OK) {
960 return aec_encode_end(strm);