MeterLogger
heatshrink_decoder.c
Go to the documentation of this file.
1 #include <stdlib.h>
2 #include <string.h>
3 #include "heatshrink_decoder.h"
4 
5 /* States for the polling state machine. */
6 typedef enum {
7  HSDS_EMPTY, /* no input to process */
8  HSDS_INPUT_AVAILABLE, /* new input, completely unprocessed */
9  HSDS_YIELD_LITERAL, /* ready to yield literal byte */
10  HSDS_BACKREF_INDEX_MSB, /* most significant byte of index */
11  HSDS_BACKREF_INDEX_LSB, /* least significant byte of index */
12  HSDS_BACKREF_COUNT_MSB, /* most significant byte of count */
13  HSDS_BACKREF_COUNT_LSB, /* least significant byte of count */
14  HSDS_YIELD_BACKREF, /* ready to yield back-reference */
15  HSDS_CHECK_FOR_MORE_INPUT, /* check if input is exhausted */
16 } HSD_state;
17 
18 #if HEATSHRINK_DEBUGGING_LOGS
19 #include <stdio.h>
20 #include <ctype.h>
21 #include <assert.h>
22 #define LOG(...) fprintf(stderr, __VA_ARGS__)
23 #define ASSERT(X) assert(X)
24 static const char *state_names[] = {
25  "empty",
26  "input_available",
27  "yield_literal",
28  "backref_index",
29  "backref_count",
30  "yield_backref",
31  "check_for_more_input",
32 };
33 #else
34 #define LOG(...) /* no-op */
35 #define ASSERT(X) /* no-op */
36 #endif
37 
38 typedef struct {
39  uint8_t *buf; /* output buffer */
40  size_t buf_size; /* buffer size */
41  size_t *output_size; /* bytes pushed to buffer, so far */
42 } output_info;
43 
44 #define NO_BITS ((uint32_t)-1)
45 
46 /* Forward references. */
47 static uint32_t get_bits(heatshrink_decoder *hsd, uint8_t count);
48 static void push_byte(heatshrink_decoder *hsd, output_info *oi, uint8_t byte);
49 
50 #if HEATSHRINK_DYNAMIC_ALLOC
51 heatshrink_decoder *heatshrink_decoder_alloc(uint16_t input_buffer_size,
52  uint8_t window_sz2,
53  uint8_t lookahead_sz2) {
54  if ((window_sz2 < HEATSHRINK_MIN_WINDOW_BITS) ||
55  (window_sz2 > HEATSHRINK_MAX_WINDOW_BITS) ||
56  (input_buffer_size == 0) ||
57  (lookahead_sz2 < HEATSHRINK_MIN_LOOKAHEAD_BITS) ||
58  (lookahead_sz2 > window_sz2)) {
59  return NULL;
60  }
61  size_t buffers_sz = (1 << window_sz2) + input_buffer_size;
62  size_t sz = sizeof(heatshrink_decoder) + buffers_sz;
64  if (hsd == NULL) { return NULL; }
65  hsd->input_buffer_size = input_buffer_size;
66  hsd->window_sz2 = window_sz2;
67  hsd->lookahead_sz2 = lookahead_sz2;
69  LOG("-- allocated decoder with buffer size of %zu (%zu + %u + %u)\n",
70  sz, sizeof(heatshrink_decoder), (1 << window_sz2), input_buffer_size);
71  return hsd;
72 }
73 
75  size_t buffers_sz = (1 << hsd->window_sz2) + hsd->input_buffer_size;
76  size_t sz = sizeof(heatshrink_decoder) + buffers_sz;
77  HEATSHRINK_FREE(hsd, sz);
78  (void)sz; /* may not be used by free */
79 }
80 #endif
81 
83  size_t buf_sz = 1 << HEATSHRINK_DECODER_WINDOW_BITS(hsd);
84  size_t input_sz = HEATSHRINK_DECODER_INPUT_BUFFER_SIZE(hsd);
85  memset(hsd->buffers, 0, buf_sz + input_sz);
86  hsd->state = HSDS_EMPTY;
87  hsd->input_size = 0;
88  hsd->input_index = 0;
89  hsd->bit_index = 0x00;
90  hsd->current_byte = 0x00;
91  hsd->output_count = 0;
92  hsd->output_index = 0;
93  hsd->head_index = 0;
94  hsd->bit_accumulator = 0x00000000;
95 }
96 
97 /* Copy SIZE bytes into the decoder's input buffer, if it will fit. */
99  uint8_t *in_buf, size_t size, size_t *input_size) {
100  if ((hsd == NULL) || (in_buf == NULL) || (input_size == NULL)) {
101  return HSDR_SINK_ERROR_NULL;
102  }
103 
104  size_t rem = HEATSHRINK_DECODER_INPUT_BUFFER_SIZE(hsd) - hsd->input_size;
105  if (rem == 0) {
106  *input_size = 0;
107  return HSDR_SINK_FULL;
108  }
109 
110  size = rem < size ? rem : size;
111  LOG("-- sinking %zd bytes\n", size);
112  /* copy into input buffer (at head of buffers) */
113  memcpy(&hsd->buffers[hsd->input_size], in_buf, size);
114  hsd->input_size += size;
115  if (hsd->state == HSDS_EMPTY) {
117  hsd->input_index = 0;
118  }
119  *input_size = size;
120  return HSDR_SINK_OK;
121 }
122 
123 
124 /*****************
125  * Decompression *
126  *****************/
127 
128 #define BACKREF_COUNT_BITS(HSD) (HEATSHRINK_DECODER_LOOKAHEAD_BITS(HSD))
129 #define BACKREF_INDEX_BITS(HSD) (HEATSHRINK_DECODER_WINDOW_BITS(HSD))
130 
131 // States
134  output_info *oi);
140  output_info *oi);
142 
144  uint8_t *out_buf, size_t out_buf_size, size_t *output_size) {
145  if ((hsd == NULL) || (out_buf == NULL) || (output_size == NULL)) {
146  return HSDR_POLL_ERROR_NULL;
147  }
148  *output_size = 0;
149 
150  output_info oi;
151  oi.buf = out_buf;
152  oi.buf_size = out_buf_size;
153  oi.output_size = output_size;
154 
155  while (1) {
156  LOG("-- poll, state is %d (%s), input_size %d\n",
157  hsd->state, state_names[hsd->state], hsd->input_size);
158  uint8_t in_state = hsd->state;
159  switch (in_state) {
160  case HSDS_EMPTY:
161  return HSDR_POLL_EMPTY;
163  hsd->state = st_input_available(hsd);
164  break;
165  case HSDS_YIELD_LITERAL:
166  hsd->state = st_yield_literal(hsd, &oi);
167  break;
169  hsd->state = st_backref_index_msb(hsd);
170  break;
172  hsd->state = st_backref_index_lsb(hsd);
173  break;
175  hsd->state = st_backref_count_msb(hsd);
176  break;
178  hsd->state = st_backref_count_lsb(hsd);
179  break;
180  case HSDS_YIELD_BACKREF:
181  hsd->state = st_yield_backref(hsd, &oi);
182  break;
184  hsd->state = st_check_for_input(hsd);
185  break;
186  default:
188  }
189 
190  /* If the current state cannot advance, check if input or output
191  * buffer are exhausted. */
192  if (hsd->state == in_state) {
193  if (*output_size == out_buf_size) { return HSDR_POLL_MORE; }
194  return HSDR_POLL_EMPTY;
195  }
196  }
197 }
198 
200  uint32_t bits = get_bits(hsd, 1); // get tag bit
201  if (bits) {
202  return HSDS_YIELD_LITERAL;
203  } else if (HEATSHRINK_DECODER_WINDOW_BITS(hsd) > 8) {
204  return HSDS_BACKREF_INDEX_MSB;
205  } else {
206  hsd->output_index = 0;
207  return HSDS_BACKREF_INDEX_LSB;
208  }
209 }
210 
212  output_info *oi) {
213  /* Emit a repeated section from the window buffer, and add it (again)
214  * to the window buffer. (Note that the repetition can include
215  * itself.)*/
216  if (*oi->output_size < oi->buf_size) {
217  uint32_t byte = get_bits(hsd, 8);
218  if (byte == NO_BITS) { return HSDS_YIELD_LITERAL; } /* out of input */
219  uint8_t *buf = &hsd->buffers[HEATSHRINK_DECODER_INPUT_BUFFER_SIZE(hsd)];
220  uint16_t mask = (1 << HEATSHRINK_DECODER_WINDOW_BITS(hsd)) - 1;
221  uint8_t c = byte & 0xFF;
222  LOG("-- emitting literal byte 0x%02x ('%c')\n", c, isprint(c) ? c : '.');
223  buf[hsd->head_index++ & mask] = c;
224  push_byte(hsd, oi, c);
226  } else {
227  return HSDS_YIELD_LITERAL;
228  }
229 }
230 
232  uint8_t bit_ct = BACKREF_INDEX_BITS(hsd);
233  ASSERT(bit_ct > 8);
234  uint32_t bits = get_bits(hsd, bit_ct - 8);
235  LOG("-- backref index (msb), got 0x%04x (+1)\n", bits);
236  if (bits == NO_BITS) { return HSDS_BACKREF_INDEX_MSB; }
237  hsd->output_index = bits << 8;
238  return HSDS_BACKREF_INDEX_LSB;
239 }
240 
242  uint8_t bit_ct = BACKREF_INDEX_BITS(hsd);
243  uint32_t bits = get_bits(hsd, bit_ct < 8 ? bit_ct : 8);
244  LOG("-- backref index (lsb), got 0x%04x (+1)\n", bits);
245  if (bits == NO_BITS) { return HSDS_BACKREF_INDEX_LSB; }
246  hsd->output_index |= bits;
247  hsd->output_index++;
248  uint8_t br_bit_ct = BACKREF_COUNT_BITS(hsd);
249  hsd->output_count = 0;
250  return (br_bit_ct > 8) ? HSDS_BACKREF_COUNT_MSB : HSDS_BACKREF_COUNT_LSB;
251 }
252 
254  uint8_t br_bit_ct = BACKREF_COUNT_BITS(hsd);
255  ASSERT(br_bit_ct > 8);
256  uint32_t bits = get_bits(hsd, br_bit_ct - 8);
257  LOG("-- backref count (msb), got 0x%04x (+1)\n", bits);
258  if (bits == NO_BITS) { return HSDS_BACKREF_COUNT_MSB; }
259  hsd->output_count = bits << 8;
260  return HSDS_BACKREF_COUNT_LSB;
261 }
262 
264  uint8_t br_bit_ct = BACKREF_COUNT_BITS(hsd);
265  uint32_t bits = get_bits(hsd, br_bit_ct < 8 ? br_bit_ct : 8);
266  LOG("-- backref count (lsb), got 0x%04x (+1)\n", bits);
267  if (bits == NO_BITS) { return HSDS_BACKREF_COUNT_LSB; }
268  hsd->output_count |= bits;
269  hsd->output_count++;
270  return HSDS_YIELD_BACKREF;
271 }
272 
274  output_info *oi) {
275  size_t count = oi->buf_size - *oi->output_size;
276  size_t i;
277  if (count > 0) {
278  if (hsd->output_count < count) count = hsd->output_count;
279  uint8_t *buf = &hsd->buffers[HEATSHRINK_DECODER_INPUT_BUFFER_SIZE(hsd)];
280  uint16_t mask = (1 << HEATSHRINK_DECODER_WINDOW_BITS(hsd)) - 1;
281  uint16_t neg_offset = hsd->output_index;
282  LOG("-- emitting %zu bytes from -%u bytes back\n", count, neg_offset);
283  ASSERT(neg_offset < mask + 1);
284  ASSERT(count <= 1 << BACKREF_COUNT_BITS(hsd));
285 
286  for (i=0; i<count; i++) {
287  uint8_t c = buf[(hsd->head_index - neg_offset) & mask];
288  push_byte(hsd, oi, c);
289  buf[hsd->head_index & mask] = c;
290  hsd->head_index++;
291  LOG(" -- ++ 0x%02x\n", c);
292  }
293  hsd->output_count -= count;
294  if (hsd->output_count == 0) { return HSDS_CHECK_FOR_MORE_INPUT; }
295  }
296  return HSDS_YIELD_BACKREF;
297 }
298 
300  return (hsd->input_size == 0) ? HSDS_EMPTY : HSDS_INPUT_AVAILABLE;
301 }
302 
303 /* Get the next COUNT bits from the input buffer, saving incremental progress.
304  * Returns NO_BITS on end of input, or if more than 31 bits are requested. */
305 static uint32_t get_bits(heatshrink_decoder *hsd, uint8_t count) {
306  int i;
307  if (count > 31) { return NO_BITS; }
308  LOG("-- popping %u bit(s)\n", count);
309 
310  /* If we aren't able to get COUNT bits, suspend immediately, because we
311  * don't track how many bits of COUNT we've accumulated before suspend. */
312  if (hsd->input_size == 0) {
313  if (hsd->bit_index < (1 << (count - 1))) { return NO_BITS; }
314  }
315 
316  for (i = 0; i < count; i++) {
317  if (hsd->bit_index == 0x00) {
318  if (hsd->input_size == 0) {
319  LOG(" -- out of bits, suspending w/ accumulator of %u (0x%02x)\n",
320  hsd->bit_accumulator, hsd->bit_accumulator);
321  return NO_BITS;
322  }
323  hsd->current_byte = hsd->buffers[hsd->input_index++];
324  LOG(" -- pulled byte 0x%02x\n", hsd->current_byte);
325  if (hsd->input_index == hsd->input_size) {
326  hsd->input_index = 0; /* input is exhausted */
327  hsd->input_size = 0;
328  }
329  hsd->bit_index = 0x80;
330  }
331  hsd->bit_accumulator <<= 1;
332  if (hsd->current_byte & hsd->bit_index) {
333  hsd->bit_accumulator |= 0x01;
334  if (0) {
335  LOG(" -- got 1, accumulator 0x%04x, bit_index 0x%02x\n",
336  hsd->bit_accumulator, hsd->bit_index);
337  }
338  } else {
339  if (0) {
340  LOG(" -- got 0, accumulator 0x%04x, bit_index 0x%02x\n",
341  hsd->bit_accumulator, hsd->bit_index);
342  }
343  }
344  hsd->bit_index >>= 1;
345  }
346 
347  uint32_t res = 0;
348  res = hsd->bit_accumulator;
349  hsd->bit_accumulator = 0x00000000;
350  if (count > 1) { LOG(" -- accumulated %08x\n", res); }
351  return res;
352 }
353 
355  if (hsd == NULL) { return HSDR_FINISH_ERROR_NULL; }
356  switch (hsd->state) {
357  case HSDS_EMPTY:
358  return HSDR_FINISH_DONE;
359 
360  /* If we want to finish with no input, but are in these states, it's
361  * because the 0-bit padding to the last byte looks like a backref
362  * marker bit followed by all 0s for index and count bits. */
367  return hsd->input_size == 0 ? HSDR_FINISH_DONE : HSDR_FINISH_MORE;
368 
369  /* If the output stream is padded with 0xFFs (possibly due to being in
370  * flash memory), also explicitly check the input size rather than
371  * uselessly returning MORE but yielding 0 bytes when polling. */
372  case HSDS_YIELD_LITERAL:
373  return hsd->input_size == 0 ? HSDR_FINISH_DONE : HSDR_FINISH_MORE;
374 
375  default:
376  return HSDR_FINISH_MORE;
377  }
378 }
379 
380 static void push_byte(heatshrink_decoder *hsd, output_info *oi, uint8_t byte) {
381  LOG(" -- pushing byte: 0x%02x ('%c')\n", byte, isprint(byte) ? byte : '.');
382  oi->buf[(*oi->output_size)++] = byte;
383  (void)hsd;
384 }
static HSD_state st_yield_literal(heatshrink_decoder *hsd, output_info *oi)
#define HEATSHRINK_FREE(P, SZ)
static HSD_state st_yield_backref(heatshrink_decoder *hsd, output_info *oi)
HSD_poll_res heatshrink_decoder_poll(heatshrink_decoder *hsd, uint8_t *out_buf, size_t out_buf_size, size_t *output_size)
#define memset(x, a, b)
Definition: platform.h:21
static HSD_state st_backref_count_msb(heatshrink_decoder *hsd)
#define HEATSHRINK_MAX_WINDOW_BITS
static HSD_state st_backref_index_lsb(heatshrink_decoder *hsd)
#define NULL
Definition: def.h:47
static void push_byte(heatshrink_decoder *hsd, output_info *oi, uint8_t byte)
#define HEATSHRINK_DECODER_WINDOW_BITS(BUF)
#define HEATSHRINK_MIN_WINDOW_BITS
heatshrink_decoder * heatshrink_decoder_alloc(uint16_t input_buffer_size, uint8_t window_sz2, uint8_t lookahead_sz2)
#define NO_BITS
static HSD_state st_input_available(heatshrink_decoder *hsd)
static HSD_state st_check_for_input(heatshrink_decoder *hsd)
#define LOG(...)
HSD_poll_res
static HSD_state st_backref_count_lsb(heatshrink_decoder *hsd)
#define isprint(c)
Definition: ip_addr.c:115
void heatshrink_decoder_free(heatshrink_decoder *hsd)
HSD_finish_res heatshrink_decoder_finish(heatshrink_decoder *hsd)
#define BACKREF_COUNT_BITS(HSD)
static heatshrink_decoder hsd
HSD_sink_res
void heatshrink_decoder_reset(heatshrink_decoder *hsd)
static HSD_state st_backref_index_msb(heatshrink_decoder *hsd)
HSD_sink_res heatshrink_decoder_sink(heatshrink_decoder *hsd, uint8_t *in_buf, size_t size, size_t *input_size)
static uint32_t get_bits(heatshrink_decoder *hsd, uint8_t count)
#define HEATSHRINK_MALLOC(SZ)
#define BACKREF_INDEX_BITS(HSD)
#define memcpy(x, a, b)
Definition: platform.h:22
HSD_state
HSD_finish_res
#define ASSERT(X)
size_t * output_size
#define HEATSHRINK_DECODER_INPUT_BUFFER_SIZE(BUF)
#define HEATSHRINK_MIN_LOOKAHEAD_BITS