MeterLogger
Data Structures | Macros | Enumerations | Functions
heatshrink_encoder.c File Reference
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include "heatshrink_encoder.h"
Include dependency graph for heatshrink_encoder.c:

Go to the source code of this file.

Data Structures

struct  output_info
 

Macros

#define LOG(...)   /* no-op */
 
#define ASSERT(X)   /* no-op */
 
#define MATCH_NOT_FOUND   ((uint16_t)-1)
 

Enumerations

enum  HSE_state {
  HSES_NOT_FULL, HSES_FILLED, HSES_SEARCH, HSES_YIELD_TAG_BIT,
  HSES_YIELD_LITERAL, HSES_YIELD_BR_INDEX, HSES_YIELD_BR_LENGTH, HSES_SAVE_BACKLOG,
  HSES_FLUSH_BITS, HSES_DONE
}
 
enum  {
  FLAG_IS_FINISHING = 0x01, FLAG_HAS_LITERAL = 0x02, FLAG_ON_FINAL_LITERAL = 0x04, FLAG_BACKLOG_IS_PARTIAL = 0x08,
  FLAG_BACKLOG_IS_FILLED = 0x10
}
 

Functions

static uint16_t get_input_offset (heatshrink_encoder *hse)
 
static uint16_t get_input_buffer_size (heatshrink_encoder *hse)
 
static uint16_t get_lookahead_size (heatshrink_encoder *hse)
 
static void add_tag_bit (heatshrink_encoder *hse, output_info *oi, uint8_t tag)
 
static int can_take_byte (output_info *oi)
 
static int is_finishing (heatshrink_encoder *hse)
 
static int backlog_is_partial (heatshrink_encoder *hse)
 
static int backlog_is_filled (heatshrink_encoder *hse)
 
static int on_final_literal (heatshrink_encoder *hse)
 
static void save_backlog (heatshrink_encoder *hse)
 
static int has_literal (heatshrink_encoder *hse)
 
static void push_bits (heatshrink_encoder *hse, uint8_t count, uint8_t bits, output_info *oi)
 
static uint8_t push_outgoing_bits (heatshrink_encoder *hse, output_info *oi)
 
static void push_literal_byte (heatshrink_encoder *hse, output_info *oi)
 
heatshrink_encoderheatshrink_encoder_alloc (uint8_t window_sz2, uint8_t lookahead_sz2)
 
void heatshrink_encoder_free (heatshrink_encoder *hse)
 
void heatshrink_encoder_reset (heatshrink_encoder *hse)
 
HSE_sink_res heatshrink_encoder_sink (heatshrink_encoder *hse, uint8_t *in_buf, size_t size, size_t *input_size)
 
static uint16_t find_longest_match (heatshrink_encoder *hse, uint16_t start, uint16_t end, const uint16_t maxlen, uint16_t *match_length)
 
static void do_indexing (heatshrink_encoder *hse)
 
static HSE_state st_step_search (heatshrink_encoder *hse)
 
static HSE_state st_yield_tag_bit (heatshrink_encoder *hse, output_info *oi)
 
static HSE_state st_yield_literal (heatshrink_encoder *hse, output_info *oi)
 
static HSE_state st_yield_br_index (heatshrink_encoder *hse, output_info *oi)
 
static HSE_state st_yield_br_length (heatshrink_encoder *hse, output_info *oi)
 
static HSE_state st_save_backlog (heatshrink_encoder *hse)
 
static HSE_state st_flush_bit_buffer (heatshrink_encoder *hse, output_info *oi)
 
HSE_poll_res heatshrink_encoder_poll (heatshrink_encoder *hse, uint8_t *out_buf, size_t out_buf_size, size_t *output_size)
 
HSE_finish_res heatshrink_encoder_finish (heatshrink_encoder *hse)
 

Macro Definition Documentation

◆ ASSERT

#define ASSERT (   X)    /* no-op */

Definition at line 39 of file heatshrink_encoder.c.

Referenced by push_bits(), and st_step_search().

◆ LOG

#define LOG (   ...)    /* no-op */

◆ MATCH_NOT_FOUND

#define MATCH_NOT_FOUND   ((uint16_t)-1)

Definition at line 57 of file heatshrink_encoder.c.

Referenced by find_longest_match(), and st_step_search().

Enumeration Type Documentation

◆ anonymous enum

anonymous enum
Enumerator
FLAG_IS_FINISHING 
FLAG_HAS_LITERAL 
FLAG_ON_FINAL_LITERAL 
FLAG_BACKLOG_IS_PARTIAL 
FLAG_BACKLOG_IS_FILLED 

Definition at line 43 of file heatshrink_encoder.c.

◆ HSE_state

enum HSE_state
Enumerator
HSES_NOT_FULL 
HSES_FILLED 
HSES_SEARCH 
HSES_YIELD_TAG_BIT 
HSES_YIELD_LITERAL 
HSES_YIELD_BR_INDEX 
HSES_YIELD_BR_LENGTH 
HSES_SAVE_BACKLOG 
HSES_FLUSH_BITS 
HSES_DONE 

Definition at line 6 of file heatshrink_encoder.c.

6  {
7  HSES_NOT_FULL, /* input buffer not full enough */
8  HSES_FILLED, /* buffer is full */
9  HSES_SEARCH, /* searching for patterns */
10  HSES_YIELD_TAG_BIT, /* yield tag bit */
11  HSES_YIELD_LITERAL, /* emit literal byte */
12  HSES_YIELD_BR_INDEX, /* yielding backref index */
13  HSES_YIELD_BR_LENGTH, /* yielding backref length */
14  HSES_SAVE_BACKLOG, /* copying buffer to backlog */
15  HSES_FLUSH_BITS, /* flush bit buffer */
16  HSES_DONE, /* done */
17 } HSE_state;
HSE_state

Function Documentation

◆ add_tag_bit()

static void add_tag_bit ( heatshrink_encoder hse,
output_info oi,
uint8_t  tag 
)
static

Definition at line 413 of file heatshrink_encoder.c.

References LOG, and push_bits().

Referenced by st_yield_tag_bit().

413  {
414  LOG("-- adding tag bit: %d\n", tag);
415  push_bits(hse, 1, tag, oi);
416 }
static void push_bits(heatshrink_encoder *hse, uint8_t count, uint8_t bits, output_info *oi)
#define LOG(...)
Here is the call graph for this function:
Here is the caller graph for this function:

◆ backlog_is_filled()

static int backlog_is_filled ( heatshrink_encoder hse)
static

Definition at line 479 of file heatshrink_encoder.c.

References FLAG_BACKLOG_IS_FILLED, and heatshrink_encoder::flags.

Referenced by st_step_search().

Here is the caller graph for this function:

◆ backlog_is_partial()

static int backlog_is_partial ( heatshrink_encoder hse)
static

Definition at line 475 of file heatshrink_encoder.c.

References FLAG_BACKLOG_IS_PARTIAL, and heatshrink_encoder::flags.

Referenced by save_backlog(), and st_step_search().

Here is the caller graph for this function:

◆ can_take_byte()

static int can_take_byte ( output_info oi)
static

Definition at line 491 of file heatshrink_encoder.c.

References output_info::buf_size, and output_info::output_size.

Referenced by st_flush_bit_buffer(), st_yield_br_index(), st_yield_br_length(), st_yield_literal(), and st_yield_tag_bit().

491  {
492  return *oi->output_size < oi->buf_size;
493 }
size_t * output_size
Here is the caller graph for this function:

◆ do_indexing()

static void do_indexing ( heatshrink_encoder hse)
static

Definition at line 432 of file heatshrink_encoder.c.

References heatshrink_encoder::buffer, get_input_offset(), HEATSHRINK_ENCODER_INDEX, hs_index::index, heatshrink_encoder::input_size, and memset.

Referenced by heatshrink_encoder_poll(), and heatshrink_encoder_sink().

432  {
433 #if HEATSHRINK_USE_INDEX
434  /* Build an index array I that contains flattened linked lists
435  * for the previous instances of every byte in the buffer.
436  *
437  * For example, if buf[200] == 'x', then index[200] will either
438  * be an offset i such that buf[i] == 'x', or a negative offset
439  * to indicate end-of-list. This significantly speeds up matching,
440  * while only using sizeof(uint16_t)*sizeof(buffer) bytes of RAM.
441  *
442  * Future optimization options:
443  * 1. Since any negative value represents end-of-list, the other
444  * 15 bits could be used to improve the index dynamically.
445  *
446  * 2. Likewise, the last lookahead_sz bytes of the index will
447  * not be usable, so temporary data could be stored there to
448  * dynamically improve the index.
449  * */
450  struct hs_index *hsi = HEATSHRINK_ENCODER_INDEX(hse);
451  uint16_t last[256];
452  memset(last, 0xFF, sizeof(last));
453 
454  uint8_t * const data = hse->buffer;
455  int16_t * const index = hsi->index;
456 
457  const uint16_t input_offset = get_input_offset(hse);
458  const uint16_t end = input_offset + hse->input_size;
459 
460  for (uint16_t i=0; i<end; i++) {
461  uint8_t v = data[i];
462  uint16_t lv = last[v];
463  index[i] = lv;
464  last[v] = i;
465  }
466 #else
467  (void)hse;
468 #endif
469 }
#define memset(x, a, b)
Definition: platform.h:21
#define HEATSHRINK_ENCODER_INDEX(HSE)
int16_t index[]
static uint16_t get_input_offset(heatshrink_encoder *hse)
Here is the call graph for this function:
Here is the caller graph for this function:

◆ find_longest_match()

static uint16_t find_longest_match ( heatshrink_encoder hse,
uint16_t  start,
uint16_t  end,
const uint16_t  maxlen,
uint16_t *  match_length 
)
static

Definition at line 497 of file heatshrink_encoder.c.

References heatshrink_encoder::buffer, HEATSHRINK_ENCODER_INDEX, hs_index::index, LOG, and MATCH_NOT_FOUND.

Referenced by heatshrink_encoder_sink(), and st_step_search().

498  {
499  LOG("-- scanning for match of buf[%u:%u] between buf[%u:%u] (max %u bytes)\n",
500  end, end + maxlen, start, end + maxlen - 1, maxlen);
501  uint8_t *buf = hse->buffer;
502 
503  uint16_t match_maxlen = 0;
504  uint16_t match_index = MATCH_NOT_FOUND;
505  const uint16_t break_even_point = 3;
506  uint16_t len = 0;
507  uint8_t * const needlepoint = &buf[end];
508 #if HEATSHRINK_USE_INDEX
509  struct hs_index *hsi = HEATSHRINK_ENCODER_INDEX(hse);
510  int16_t pos = hsi->index[end];
511 
512  while (pos >= start) {
513  uint8_t * const pospoint = &buf[pos];
514  len = 0;
515 
516  /* Only check matches that will potentially beat the current maxlen.
517  * This is redundant with the index if match_maxlen is 0, but the
518  * added branch overhead to check if it == 0 seems to be worse. */
519  if (pospoint[match_maxlen] != needlepoint[match_maxlen]) {
520  pos = hsi->index[pos];
521  continue;
522  }
523 
524  for (len = 1; len < maxlen; len++) {
525  if (pospoint[len] != needlepoint[len]) break;
526  }
527 
528  if (len > match_maxlen) {
529  match_maxlen = len;
530  match_index = pos;
531  if (len == maxlen) { break; } /* won't find better */
532  }
533  pos = hsi->index[pos];
534  }
535 #else
536  for (int16_t pos=end - 1; pos >= start; pos--) {
537  uint8_t * const pospoint = &buf[pos];
538  if ((pospoint[match_maxlen] == needlepoint[match_maxlen])
539  && (*pospoint == *needlepoint)) {
540  for (len=1; len<maxlen; len++) {
541  if (0) {
542  LOG(" --> cmp buf[%d] == 0x%02x against %02x (start %u)\n",
543  pos + len, pospoint[len], needlepoint[len], start);
544  }
545  if (pospoint[len] != needlepoint[len]) { break; }
546  }
547  if (len > match_maxlen) {
548  match_maxlen = len;
549  match_index = pos;
550  if (len == maxlen) { break; } /* don't keep searching */
551  }
552  }
553  }
554 #endif
555 
556  if (match_maxlen >= break_even_point) {
557  LOG("-- best match: %u bytes at -%u\n",
558  match_maxlen, end - match_index);
559  *match_length = match_maxlen;
560  return end - match_index;
561  }
562  LOG("-- none found\n");
563  return MATCH_NOT_FOUND;
564 }
#define MATCH_NOT_FOUND
#define HEATSHRINK_ENCODER_INDEX(HSE)
#define LOG(...)
int16_t index[]
Here is the caller graph for this function:

◆ get_input_buffer_size()

static uint16_t get_input_buffer_size ( heatshrink_encoder hse)
static

Definition at line 422 of file heatshrink_encoder.c.

References HEATSHRINK_ENCODER_WINDOW_BITS.

Referenced by get_input_offset(), heatshrink_encoder_alloc(), heatshrink_encoder_sink(), save_backlog(), and st_step_search().

422  {
423  return (1 << HEATSHRINK_ENCODER_WINDOW_BITS(hse));
424  (void)hse;
425 }
#define HEATSHRINK_ENCODER_WINDOW_BITS(HSE)
Here is the caller graph for this function:

◆ get_input_offset()

static uint16_t get_input_offset ( heatshrink_encoder hse)
static

Definition at line 418 of file heatshrink_encoder.c.

References get_input_buffer_size().

Referenced by do_indexing(), heatshrink_encoder_sink(), push_literal_byte(), and st_step_search().

418  {
419  return get_input_buffer_size(hse);
420 }
static uint16_t get_input_buffer_size(heatshrink_encoder *hse)
Here is the call graph for this function:
Here is the caller graph for this function:

◆ get_lookahead_size()

static uint16_t get_lookahead_size ( heatshrink_encoder hse)
static

Definition at line 427 of file heatshrink_encoder.c.

References HEATSHRINK_ENCODER_LOOKAHEAD_BITS.

Referenced by st_step_search().

427  {
428  return (1 << HEATSHRINK_ENCODER_LOOKAHEAD_BITS(hse));
429  (void)hse;
430 }
#define HEATSHRINK_ENCODER_LOOKAHEAD_BITS(HSE)
Here is the caller graph for this function:

◆ has_literal()

static int has_literal ( heatshrink_encoder hse)
static

Definition at line 487 of file heatshrink_encoder.c.

References FLAG_HAS_LITERAL, and heatshrink_encoder::flags.

Referenced by st_save_backlog().

487  {
488  return (hse->flags & FLAG_HAS_LITERAL);
489 }
Here is the caller graph for this function:

◆ heatshrink_encoder_alloc()

heatshrink_encoder* heatshrink_encoder_alloc ( uint8_t  window_sz2,
uint8_t  lookahead_sz2 
)

Definition at line 78 of file heatshrink_encoder.c.

References get_input_buffer_size(), heatshrink_encoder_reset(), HEATSHRINK_FREE, HEATSHRINK_MALLOC, HEATSHRINK_MAX_WINDOW_BITS, HEATSHRINK_MIN_LOOKAHEAD_BITS, HEATSHRINK_MIN_WINDOW_BITS, hse, LOG, heatshrink_encoder::lookahead_sz2, NULL, heatshrink_encoder::search_index, hs_index::size, and heatshrink_encoder::window_sz2.

Referenced by compress_and_expand_and_check(), data_with_simple_repetition_should_match_with_absurdly_tiny_buffers(), data_without_duplication_should_match_with_absurdly_tiny_buffers(), encode(), encoder_alloc_should_reject_invalid_arguments(), encoder_poll_should_detect_repeated_substring(), encoder_poll_should_detect_repeated_substring_and_preserve_trailing_literal(), encoder_poll_should_indicate_when_no_input_is_provided(), encoder_poll_should_reject_nulls(), encoder_should_emit_data_without_repetitions_as_literal_sequence(), encoder_should_emit_series_of_same_byte_as_literal_then_backref(), encoder_sink_should_accept_input_when_it_will_fit(), encoder_sink_should_accept_partial_input_when_some_will_fit(), encoder_sink_should_reject_nulls(), and gen().

79  {
80  if ((window_sz2 < HEATSHRINK_MIN_WINDOW_BITS) ||
81  (window_sz2 > HEATSHRINK_MAX_WINDOW_BITS) ||
82  (lookahead_sz2 < HEATSHRINK_MIN_LOOKAHEAD_BITS) ||
83  (lookahead_sz2 > window_sz2)) {
84  return NULL;
85  }
86 
87  /* Note: 2 * the window size is used because the buffer needs to fit
88  * (1 << window_sz2) bytes for the current input, and an additional
89  * (1 << window_sz2) bytes for the previous buffer of input, which
90  * will be scanned for useful backreferences. */
91  size_t buf_sz = (2 << window_sz2);
92 
93  heatshrink_encoder *hse = HEATSHRINK_MALLOC(sizeof(*hse) + buf_sz);
94  if (hse == NULL) { return NULL; }
95  hse->window_sz2 = window_sz2;
96  hse->lookahead_sz2 = lookahead_sz2;
98 
99 #if HEATSHRINK_USE_INDEX
100  size_t index_sz = buf_sz*sizeof(uint16_t);
101  hse->search_index = HEATSHRINK_MALLOC(index_sz + sizeof(struct hs_index));
102  if (hse->search_index == NULL) {
103  HEATSHRINK_FREE(hse, sizeof(*hse) + buf_sz);
104  return NULL;
105  }
106  hse->search_index->size = index_sz;
107 #endif
108 
109  LOG("-- allocated encoder with buffer size of %zu (%u byte input size)\n",
110  buf_sz, get_input_buffer_size(hse));
111  return hse;
112 }
#define HEATSHRINK_FREE(P, SZ)
uint16_t size
#define HEATSHRINK_MAX_WINDOW_BITS
#define NULL
Definition: def.h:47
#define HEATSHRINK_MIN_WINDOW_BITS
#define LOG(...)
static uint16_t get_input_buffer_size(heatshrink_encoder *hse)
#define HEATSHRINK_MALLOC(SZ)
struct hs_index * search_index
void heatshrink_encoder_reset(heatshrink_encoder *hse)
#define HEATSHRINK_MIN_LOOKAHEAD_BITS
static heatshrink_encoder hse
Here is the call graph for this function:
Here is the caller graph for this function:

◆ heatshrink_encoder_finish()

HSE_finish_res heatshrink_encoder_finish ( heatshrink_encoder hse)

Definition at line 260 of file heatshrink_encoder.c.

References FLAG_IS_FINISHING, heatshrink_encoder::flags, HSER_FINISH_DONE, HSER_FINISH_ERROR_NULL, HSER_FINISH_MORE, HSES_DONE, HSES_FILLED, HSES_NOT_FULL, LOG, NULL, and heatshrink_encoder::state.

Referenced by compress_and_expand_and_check(), data_with_simple_repetition_should_match_with_absurdly_tiny_buffers(), data_without_duplication_should_match_with_absurdly_tiny_buffers(), encoder_finish_should_reject_nulls(), encoder_poll_should_detect_repeated_substring(), encoder_poll_should_detect_repeated_substring_and_preserve_trailing_literal(), encoder_should_emit_data_without_repetitions_as_literal_sequence(), encoder_should_emit_series_of_same_byte_as_literal_then_backref(), encoder_sink_read(), and gen().

260  {
261  if (hse == NULL) { return HSER_FINISH_ERROR_NULL; }
262  LOG("-- setting is_finishing flag\n");
263  hse->flags |= FLAG_IS_FINISHING;
264  if (hse->state == HSES_NOT_FULL) { hse->state = HSES_FILLED; }
266 }
#define NULL
Definition: def.h:47
#define LOG(...)
Here is the caller graph for this function:

◆ heatshrink_encoder_free()

void heatshrink_encoder_free ( heatshrink_encoder hse)

Definition at line 114 of file heatshrink_encoder.c.

References HEATSHRINK_ENCODER_WINDOW_BITS, and HEATSHRINK_FREE.

Referenced by compress_and_expand_and_check(), data_with_simple_repetition_should_match_with_absurdly_tiny_buffers(), data_without_duplication_should_match_with_absurdly_tiny_buffers(), encode(), encoder_poll_should_detect_repeated_substring(), encoder_poll_should_detect_repeated_substring_and_preserve_trailing_literal(), encoder_poll_should_indicate_when_no_input_is_provided(), encoder_poll_should_reject_nulls(), encoder_should_emit_data_without_repetitions_as_literal_sequence(), encoder_should_emit_series_of_same_byte_as_literal_then_backref(), encoder_sink_should_accept_input_when_it_will_fit(), encoder_sink_should_accept_partial_input_when_some_will_fit(), encoder_sink_should_reject_nulls(), and gen().

114  {
115  size_t buf_sz = (2 << HEATSHRINK_ENCODER_WINDOW_BITS(hse));
116 #if HEATSHRINK_USE_INDEX
117  size_t index_sz = sizeof(struct hs_index) + hse->search_index->size;
118  HEATSHRINK_FREE(hse->search_index, index_sz);
119  (void)index_sz;
120 #endif
121  HEATSHRINK_FREE(hse, sizeof(heatshrink_encoder) + buf_sz);
122  (void)buf_sz;
123 }
#define HEATSHRINK_FREE(P, SZ)
uint16_t size
#define HEATSHRINK_ENCODER_WINDOW_BITS(HSE)
struct hs_index * search_index
Here is the caller graph for this function:

◆ heatshrink_encoder_poll()

HSE_poll_res heatshrink_encoder_poll ( heatshrink_encoder hse,
uint8_t *  out_buf,
size_t  out_buf_size,
size_t output_size 
)

Definition at line 198 of file heatshrink_encoder.c.

References output_info::buf, output_info::buf_size, do_indexing(), heatshrink_encoder::flags, HSER_POLL_EMPTY, HSER_POLL_ERROR_MISUSE, HSER_POLL_ERROR_NULL, HSER_POLL_MORE, HSES_DONE, HSES_FILLED, HSES_FLUSH_BITS, HSES_NOT_FULL, HSES_SAVE_BACKLOG, HSES_SEARCH, HSES_YIELD_BR_INDEX, HSES_YIELD_BR_LENGTH, HSES_YIELD_LITERAL, HSES_YIELD_TAG_BIT, LOG, NULL, output_info::output_size, st_flush_bit_buffer(), st_save_backlog(), st_step_search(), st_yield_br_index(), st_yield_br_length(), st_yield_literal(), st_yield_tag_bit(), and heatshrink_encoder::state.

Referenced by compress_and_expand_and_check(), data_with_simple_repetition_should_match_with_absurdly_tiny_buffers(), data_without_duplication_should_match_with_absurdly_tiny_buffers(), encoder_poll_should_detect_repeated_substring(), encoder_poll_should_detect_repeated_substring_and_preserve_trailing_literal(), encoder_poll_should_indicate_when_no_input_is_provided(), encoder_poll_should_reject_nulls(), encoder_should_emit_data_without_repetitions_as_literal_sequence(), encoder_should_emit_series_of_same_byte_as_literal_then_backref(), encoder_sink_read(), and gen().

199  {
200  if ((hse == NULL) || (out_buf == NULL) || (output_size == NULL)) {
201  return HSER_POLL_ERROR_NULL;
202  }
203  if (out_buf_size == 0) {
204  LOG("-- MISUSE: output buffer size is 0\n");
205  return HSER_POLL_ERROR_MISUSE;
206  }
207  *output_size = 0;
208 
209  output_info oi;
210  oi.buf = out_buf;
211  oi.buf_size = out_buf_size;
212  oi.output_size = output_size;
213 
214  while (1) {
215  LOG("-- polling, state %u (%s), flags 0x%02x\n",
216  hse->state, state_names[hse->state], hse->flags);
217 
218  uint8_t in_state = hse->state;
219  switch (in_state) {
220  case HSES_NOT_FULL:
221  return HSER_POLL_EMPTY;
222  case HSES_FILLED:
223  do_indexing(hse);
224  hse->state = HSES_SEARCH;
225  break;
226  case HSES_SEARCH:
227  hse->state = st_step_search(hse);
228  break;
229  case HSES_YIELD_TAG_BIT:
230  hse->state = st_yield_tag_bit(hse, &oi);
231  break;
232  case HSES_YIELD_LITERAL:
233  hse->state = st_yield_literal(hse, &oi);
234  break;
235  case HSES_YIELD_BR_INDEX:
236  hse->state = st_yield_br_index(hse, &oi);
237  break;
239  hse->state = st_yield_br_length(hse, &oi);
240  break;
241  case HSES_SAVE_BACKLOG:
242  hse->state = st_save_backlog(hse);
243  break;
244  case HSES_FLUSH_BITS:
245  hse->state = st_flush_bit_buffer(hse, &oi);
246  case HSES_DONE:
247  return HSER_POLL_EMPTY;
248  default:
249  LOG("-- bad state %s\n", state_names[hse->state]);
250  return HSER_POLL_ERROR_MISUSE;
251  }
252 
253  if (hse->state == in_state) {
254  /* Check if output buffer is exhausted. */
255  if (*output_size == out_buf_size) return HSER_POLL_MORE;
256  }
257  }
258 }
static void do_indexing(heatshrink_encoder *hse)
static HSE_state st_step_search(heatshrink_encoder *hse)
static HSE_state st_yield_br_length(heatshrink_encoder *hse, output_info *oi)
#define NULL
Definition: def.h:47
static HSE_state st_yield_literal(heatshrink_encoder *hse, output_info *oi)
static HSE_state st_yield_tag_bit(heatshrink_encoder *hse, output_info *oi)
#define LOG(...)
static HSE_state st_save_backlog(heatshrink_encoder *hse)
static HSE_state st_yield_br_index(heatshrink_encoder *hse, output_info *oi)
static HSE_state st_flush_bit_buffer(heatshrink_encoder *hse, output_info *oi)
size_t * output_size
Here is the call graph for this function:
Here is the caller graph for this function:

◆ heatshrink_encoder_reset()

void heatshrink_encoder_reset ( heatshrink_encoder hse)

Definition at line 126 of file heatshrink_encoder.c.

References heatshrink_encoder::bit_index, heatshrink_encoder::buffer, heatshrink_encoder::current_byte, heatshrink_encoder::flags, HEATSHRINK_ENCODER_WINDOW_BITS, HSES_NOT_FULL, heatshrink_encoder::input_size, heatshrink_encoder::match_length, heatshrink_encoder::match_scan_index, memset, heatshrink_encoder::outgoing_bits, heatshrink_encoder::outgoing_bits_count, and heatshrink_encoder::state.

Referenced by compress_and_expand_and_check(), and heatshrink_encoder_alloc().

126  {
127  size_t buf_sz = (2 << HEATSHRINK_ENCODER_WINDOW_BITS(hse));
128  memset(hse->buffer, 0, buf_sz);
129  hse->input_size = 0;
130  hse->state = HSES_NOT_FULL;
131  hse->match_scan_index = 0;
132  hse->flags = 0;
133  hse->bit_index = 0x80;
134  hse->current_byte = 0x00;
135  hse->match_length = 0;
136 
137  hse->outgoing_bits = 0x0000;
138  hse->outgoing_bits_count = 0;
139 
140  #ifdef LOOP_DETECT
141  hse->loop_detect = (uint32_t)-1;
142  #endif
143 }
#define memset(x, a, b)
Definition: platform.h:21
#define HEATSHRINK_ENCODER_WINDOW_BITS(HSE)
Here is the caller graph for this function:

◆ heatshrink_encoder_sink()

HSE_sink_res heatshrink_encoder_sink ( heatshrink_encoder hse,
uint8_t *  in_buf,
size_t  size,
size_t input_size 
)

Definition at line 145 of file heatshrink_encoder.c.

References heatshrink_encoder::buffer, do_indexing(), find_longest_match(), get_input_buffer_size(), get_input_offset(), hse, HSER_SINK_ERROR_MISUSE, HSER_SINK_ERROR_NULL, HSER_SINK_OK, HSES_FILLED, HSES_NOT_FULL, heatshrink_encoder::input_size, is_finishing(), LOG, memcpy, NULL, hs_index::size, st_flush_bit_buffer(), st_save_backlog(), st_step_search(), st_yield_br_index(), st_yield_br_length(), st_yield_literal(), st_yield_tag_bit(), and heatshrink_encoder::state.

Referenced by compress_and_expand_and_check(), data_with_simple_repetition_should_match_with_absurdly_tiny_buffers(), data_without_duplication_should_match_with_absurdly_tiny_buffers(), encoder_poll_should_detect_repeated_substring(), encoder_poll_should_detect_repeated_substring_and_preserve_trailing_literal(), encoder_should_emit_data_without_repetitions_as_literal_sequence(), encoder_should_emit_series_of_same_byte_as_literal_then_backref(), encoder_sink_read(), encoder_sink_should_accept_input_when_it_will_fit(), encoder_sink_should_accept_partial_input_when_some_will_fit(), encoder_sink_should_reject_nulls(), and gen().

146  {
147  if ((hse == NULL) || (in_buf == NULL) || (input_size == NULL)) {
148  return HSER_SINK_ERROR_NULL;
149  }
150 
151  /* Sinking more content after saying the content is done, tsk tsk */
152  if (is_finishing(hse)) { return HSER_SINK_ERROR_MISUSE; }
153 
154  /* Sinking more content before processing is done */
155  if (hse->state != HSES_NOT_FULL) { return HSER_SINK_ERROR_MISUSE; }
156 
157  uint16_t write_offset = get_input_offset(hse) + hse->input_size;
158  uint16_t ibs = get_input_buffer_size(hse);
159  uint16_t rem = ibs - hse->input_size;
160  uint16_t cp_sz = rem < size ? rem : size;
161 
162  memcpy(&hse->buffer[write_offset], in_buf, cp_sz);
163  *input_size = cp_sz;
164  hse->input_size += cp_sz;
165 
166  LOG("-- sunk %u bytes (of %zu) into encoder at %d, input buffer now has %u\n",
167  cp_sz, size, write_offset, hse->input_size);
168  if (cp_sz == rem) {
169  LOG("-- internal buffer is now full\n");
170  hse->state = HSES_FILLED;
171  }
172 
173  return HSER_SINK_OK;
174 }
uint16_t size
static int is_finishing(heatshrink_encoder *hse)
#define NULL
Definition: def.h:47
#define LOG(...)
static uint16_t get_input_buffer_size(heatshrink_encoder *hse)
static uint16_t get_input_offset(heatshrink_encoder *hse)
#define memcpy(x, a, b)
Definition: platform.h:22
Here is the call graph for this function:
Here is the caller graph for this function:

◆ is_finishing()

static int is_finishing ( heatshrink_encoder hse)
static

Definition at line 471 of file heatshrink_encoder.c.

References FLAG_IS_FINISHING, and heatshrink_encoder::flags.

Referenced by heatshrink_encoder_sink(), st_save_backlog(), and st_step_search().

471  {
472  return hse->flags & FLAG_IS_FINISHING;
473 }
Here is the caller graph for this function:

◆ on_final_literal()

static int on_final_literal ( heatshrink_encoder hse)
static

Definition at line 483 of file heatshrink_encoder.c.

References FLAG_ON_FINAL_LITERAL, and heatshrink_encoder::flags.

Referenced by st_yield_literal().

Here is the caller graph for this function:

◆ push_bits()

static void push_bits ( heatshrink_encoder hse,
uint8_t  count,
uint8_t  bits,
output_info oi 
)
static

Definition at line 587 of file heatshrink_encoder.c.

References ASSERT, heatshrink_encoder::bit_index, output_info::buf, heatshrink_encoder::current_byte, LOG, and output_info::output_size.

Referenced by add_tag_bit(), push_literal_byte(), and push_outgoing_bits().

588  {
589  ASSERT(count <= 8);
590  LOG("++ push_bits: %d bits, input of 0x%02x\n", count, bits);
591 
592  /* If adding a whole byte and at the start of a new output byte,
593  * just push it through whole and skip the bit IO loop. */
594  if (count == 8 && hse->bit_index == 0x80) {
595  oi->buf[(*oi->output_size)++] = bits;
596  } else {
597  for (int i=count - 1; i>=0; i--) {
598  bool bit = bits & (1 << i);
599  if (bit) { hse->current_byte |= hse->bit_index; }
600  if (0) {
601  LOG(" -- setting bit %d at bit index 0x%02x, byte => 0x%02x\n",
602  bit ? 1 : 0, hse->bit_index, hse->current_byte);
603  }
604  hse->bit_index >>= 1;
605  if (hse->bit_index == 0x00) {
606  hse->bit_index = 0x80;
607  LOG(" > pushing byte 0x%02x\n", hse->current_byte);
608  oi->buf[(*oi->output_size)++] = hse->current_byte;
609  hse->current_byte = 0x00;
610  }
611  }
612  }
613 }
#define LOG(...)
#define ASSERT(X)
size_t * output_size
Here is the caller graph for this function:

◆ push_literal_byte()

static void push_literal_byte ( heatshrink_encoder hse,
output_info oi 
)
static

Definition at line 615 of file heatshrink_encoder.c.

References heatshrink_encoder::buffer, get_input_offset(), isprint, LOG, heatshrink_encoder::match_scan_index, and push_bits().

Referenced by st_yield_literal().

615  {
616  uint16_t processed_offset = hse->match_scan_index - 1;
617  uint16_t input_offset = get_input_offset(hse) + processed_offset;
618  uint8_t c = hse->buffer[input_offset];
619  LOG("-- yielded literal byte 0x%02x ('%c') from +%d\n",
620  c, isprint(c) ? c : '.', input_offset);
621  push_bits(hse, 8, c, oi);
622 }
static void push_bits(heatshrink_encoder *hse, uint8_t count, uint8_t bits, output_info *oi)
#define LOG(...)
#define isprint(c)
Definition: ip_addr.c:115
static uint16_t get_input_offset(heatshrink_encoder *hse)
Here is the call graph for this function:
Here is the caller graph for this function:

◆ push_outgoing_bits()

static uint8_t push_outgoing_bits ( heatshrink_encoder hse,
output_info oi 
)
static

Definition at line 566 of file heatshrink_encoder.c.

References LOG, heatshrink_encoder::outgoing_bits, heatshrink_encoder::outgoing_bits_count, and push_bits().

Referenced by st_yield_br_index(), and st_yield_br_length().

566  {
567  uint8_t count = 0;
568  uint8_t bits = 0;
569  if (hse->outgoing_bits_count > 8) {
570  count = 8;
571  bits = hse->outgoing_bits >> (hse->outgoing_bits_count - 8);
572  } else {
573  count = hse->outgoing_bits_count;
574  bits = hse->outgoing_bits;
575  }
576 
577  if (count > 0) {
578  LOG("-- pushing %d outgoing bits: 0x%02x\n", count, bits);
579  push_bits(hse, count, bits, oi);
580  hse->outgoing_bits_count -= count;
581  }
582  return count;
583 }
static void push_bits(heatshrink_encoder *hse, uint8_t count, uint8_t bits, output_info *oi)
#define LOG(...)
Here is the call graph for this function:
Here is the caller graph for this function:

◆ save_backlog()

static void save_backlog ( heatshrink_encoder hse)
static

Definition at line 624 of file heatshrink_encoder.c.

References backlog_is_partial(), heatshrink_encoder::buffer, FLAG_BACKLOG_IS_FILLED, FLAG_BACKLOG_IS_PARTIAL, heatshrink_encoder::flags, get_input_buffer_size(), heatshrink_encoder::input_size, and heatshrink_encoder::match_scan_index.

Referenced by st_save_backlog().

624  {
625  size_t input_buf_sz = get_input_buffer_size(hse);
626 
627  uint16_t msi = hse->match_scan_index;
628 
629  /* Copy processed data to beginning of buffer, so it can be
630  * used for future matches. Don't bother checking whether the
631  * input is less than the maximum size, because if it isn't,
632  * we're done anyway. */
633  uint16_t rem = input_buf_sz - msi; // unprocessed bytes
634  uint16_t shift_sz = input_buf_sz + rem;
635 
636  memmove(&hse->buffer[0],
637  &hse->buffer[input_buf_sz - rem],
638  shift_sz);
639 
640  if (backlog_is_partial(hse)) {
641  /* The whole backlog is filled in now, so include it in scans. */
643  } else {
644  /* Include backlog, except for the first lookahead_sz bytes, which
645  * are still undefined. */
647  }
648  hse->match_scan_index = 0;
649  hse->input_size -= input_buf_sz - rem;
650 }
static uint16_t get_input_buffer_size(heatshrink_encoder *hse)
static int backlog_is_partial(heatshrink_encoder *hse)
Here is the call graph for this function:
Here is the caller graph for this function:

◆ st_flush_bit_buffer()

static HSE_state st_flush_bit_buffer ( heatshrink_encoder hse,
output_info oi 
)
static

Definition at line 398 of file heatshrink_encoder.c.

References heatshrink_encoder::bit_index, output_info::buf, can_take_byte(), heatshrink_encoder::current_byte, HSES_DONE, HSES_FLUSH_BITS, LOG, and output_info::output_size.

Referenced by heatshrink_encoder_poll(), and heatshrink_encoder_sink().

399  {
400  if (hse->bit_index == 0x80) {
401  LOG("-- done!\n");
402  return HSES_DONE;
403  } else if (can_take_byte(oi)) {
404  LOG("-- flushing remaining byte (bit_index == 0x%02x)\n", hse->bit_index);
405  oi->buf[(*oi->output_size)++] = hse->current_byte;
406  LOG("-- done!\n");
407  return HSES_DONE;
408  } else {
409  return HSES_FLUSH_BITS;
410  }
411 }
#define LOG(...)
static int can_take_byte(output_info *oi)
size_t * output_size
Here is the call graph for this function:
Here is the caller graph for this function:

◆ st_save_backlog()

static HSE_state st_save_backlog ( heatshrink_encoder hse)
static

Definition at line 382 of file heatshrink_encoder.c.

References FLAG_ON_FINAL_LITERAL, heatshrink_encoder::flags, has_literal(), HSES_FLUSH_BITS, HSES_NOT_FULL, HSES_YIELD_TAG_BIT, is_finishing(), LOG, and save_backlog().

Referenced by heatshrink_encoder_poll(), and heatshrink_encoder_sink().

382  {
383  if (is_finishing(hse)) {
384  /* copy remaining literal (if necessary) */
385  if (has_literal(hse)) {
387  return HSES_YIELD_TAG_BIT;
388  } else {
389  return HSES_FLUSH_BITS;
390  }
391  } else {
392  LOG("-- saving backlog\n");
393  save_backlog(hse);
394  return HSES_NOT_FULL;
395  }
396 }
static int is_finishing(heatshrink_encoder *hse)
#define LOG(...)
static int has_literal(heatshrink_encoder *hse)
static void save_backlog(heatshrink_encoder *hse)
Here is the call graph for this function:
Here is the caller graph for this function:

◆ st_step_search()

static HSE_state st_step_search ( heatshrink_encoder hse)
static

Definition at line 268 of file heatshrink_encoder.c.

References ASSERT, backlog_is_filled(), backlog_is_partial(), find_longest_match(), FLAG_HAS_LITERAL, heatshrink_encoder::flags, get_input_buffer_size(), get_input_offset(), get_lookahead_size(), HSES_SAVE_BACKLOG, HSES_YIELD_TAG_BIT, heatshrink_encoder::input_size, is_finishing(), LOG, heatshrink_encoder::match_length, MATCH_NOT_FOUND, heatshrink_encoder::match_pos, heatshrink_encoder::match_scan_index, and heatshrink_encoder::window_sz2.

Referenced by heatshrink_encoder_poll(), and heatshrink_encoder_sink().

268  {
269  uint16_t window_length = get_input_buffer_size(hse);
270  uint16_t lookahead_sz = get_lookahead_size(hse);
271  uint16_t msi = hse->match_scan_index;
272  LOG("## step_search, scan @ +%d (%d/%d), input size %d\n",
273  msi, hse->input_size + msi, 2*window_length, hse->input_size);
274 
275  bool fin = is_finishing(hse);
276  if (msi >= hse->input_size - (fin ? 0 : lookahead_sz)) {
277  /* Current search buffer is exhausted, copy it into the
278  * backlog and await more input. */
279  LOG("-- end of search @ %d, saving backlog\n", msi);
280  return HSES_SAVE_BACKLOG;
281  }
282 
283  uint16_t input_offset = get_input_offset(hse);
284  uint16_t end = input_offset + msi;
285 
286  uint16_t start = 0;
287  if (backlog_is_filled(hse)) { /* last WINDOW_LENGTH bytes */
288  start = end - window_length + 1;
289  } else if (backlog_is_partial(hse)) { /* clamp to available data */
290  start = end - window_length + 1;
291  if (start < lookahead_sz) { start = lookahead_sz; }
292  } else { /* only scan available input */
293  start = input_offset;
294  }
295 
296  uint16_t max_possible = lookahead_sz;
297  if (hse->input_size - msi < lookahead_sz) {
298  max_possible = hse->input_size - msi;
299  }
300 
301  uint16_t match_length = 0;
302  uint16_t match_pos = find_longest_match(hse,
303  start, end, max_possible, &match_length);
304 
305  if (match_pos == MATCH_NOT_FOUND) {
306  LOG("ss Match not found\n");
307  hse->match_scan_index++;
308  hse->flags |= FLAG_HAS_LITERAL;
309  hse->match_length = 0;
310  return HSES_YIELD_TAG_BIT;
311  } else {
312  LOG("ss Found match of %d bytes at %d\n", match_length, match_pos);
313  hse->match_pos = match_pos;
314  hse->match_length = match_length;
315  ASSERT(match_pos < 1 << hse->window_sz2 /*window_length*/);
316 
317  return HSES_YIELD_TAG_BIT;
318  }
319 }
#define MATCH_NOT_FOUND
static int is_finishing(heatshrink_encoder *hse)
static int backlog_is_filled(heatshrink_encoder *hse)
#define LOG(...)
static uint16_t find_longest_match(heatshrink_encoder *hse, uint16_t start, uint16_t end, const uint16_t maxlen, uint16_t *match_length)
static uint16_t get_input_buffer_size(heatshrink_encoder *hse)
static uint16_t get_lookahead_size(heatshrink_encoder *hse)
static int backlog_is_partial(heatshrink_encoder *hse)
#define ASSERT(X)
static uint16_t get_input_offset(heatshrink_encoder *hse)
Here is the call graph for this function:
Here is the caller graph for this function:

◆ st_yield_br_index()

static HSE_state st_yield_br_index ( heatshrink_encoder hse,
output_info oi 
)
static

Definition at line 350 of file heatshrink_encoder.c.

References can_take_byte(), HEATSHRINK_ENCODER_LOOKAHEAD_BITS, HSES_YIELD_BR_INDEX, HSES_YIELD_BR_LENGTH, LOG, heatshrink_encoder::match_length, heatshrink_encoder::match_pos, heatshrink_encoder::outgoing_bits, heatshrink_encoder::outgoing_bits_count, and push_outgoing_bits().

Referenced by heatshrink_encoder_poll(), and heatshrink_encoder_sink().

351  {
352  if (can_take_byte(oi)) {
353  LOG("-- yielding backref index %u\n", hse->match_pos);
354  if (push_outgoing_bits(hse, oi) > 0) {
355  return HSES_YIELD_BR_INDEX; /* continue */
356  } else {
357  hse->outgoing_bits = hse->match_length - 1;
359  return HSES_YIELD_BR_LENGTH; /* done */
360  }
361  } else {
362  return HSES_YIELD_BR_INDEX; /* continue */
363  }
364 }
#define LOG(...)
static uint8_t push_outgoing_bits(heatshrink_encoder *hse, output_info *oi)
static int can_take_byte(output_info *oi)
#define HEATSHRINK_ENCODER_LOOKAHEAD_BITS(HSE)
Here is the call graph for this function:
Here is the caller graph for this function:

◆ st_yield_br_length()

static HSE_state st_yield_br_length ( heatshrink_encoder hse,
output_info oi 
)
static

Definition at line 366 of file heatshrink_encoder.c.

References can_take_byte(), HSES_SEARCH, HSES_YIELD_BR_LENGTH, LOG, heatshrink_encoder::match_length, heatshrink_encoder::match_scan_index, and push_outgoing_bits().

Referenced by heatshrink_encoder_poll(), and heatshrink_encoder_sink().

367  {
368  if (can_take_byte(oi)) {
369  LOG("-- yielding backref length %u\n", hse->match_length);
370  if (push_outgoing_bits(hse, oi) > 0) {
371  return HSES_YIELD_BR_LENGTH;
372  } else {
373  hse->match_scan_index += hse->match_length;
374  hse->match_length = 0;
375  return HSES_SEARCH;
376  }
377  } else {
378  return HSES_YIELD_BR_LENGTH;
379  }
380 }
#define LOG(...)
static uint8_t push_outgoing_bits(heatshrink_encoder *hse, output_info *oi)
static int can_take_byte(output_info *oi)
Here is the call graph for this function:
Here is the caller graph for this function:

◆ st_yield_literal()

static HSE_state st_yield_literal ( heatshrink_encoder hse,
output_info oi 
)
static

Definition at line 338 of file heatshrink_encoder.c.

References can_take_byte(), FLAG_HAS_LITERAL, heatshrink_encoder::flags, HSES_FLUSH_BITS, HSES_SEARCH, HSES_YIELD_LITERAL, HSES_YIELD_TAG_BIT, heatshrink_encoder::match_length, on_final_literal(), and push_literal_byte().

Referenced by heatshrink_encoder_poll(), and heatshrink_encoder_sink().

339  {
340  if (can_take_byte(oi)) {
341  push_literal_byte(hse, oi);
342  hse->flags &= ~FLAG_HAS_LITERAL;
343  if (on_final_literal(hse)) { return HSES_FLUSH_BITS; }
344  return hse->match_length > 0 ? HSES_YIELD_TAG_BIT : HSES_SEARCH;
345  } else {
346  return HSES_YIELD_LITERAL;
347  }
348 }
static int on_final_literal(heatshrink_encoder *hse)
static void push_literal_byte(heatshrink_encoder *hse, output_info *oi)
static int can_take_byte(output_info *oi)
Here is the call graph for this function:
Here is the caller graph for this function:

◆ st_yield_tag_bit()

static HSE_state st_yield_tag_bit ( heatshrink_encoder hse,
output_info oi 
)
static

Definition at line 321 of file heatshrink_encoder.c.

References add_tag_bit(), can_take_byte(), HEATSHRINK_BACKREF_MARKER, HEATSHRINK_ENCODER_WINDOW_BITS, HEATSHRINK_LITERAL_MARKER, HSES_YIELD_BR_INDEX, HSES_YIELD_LITERAL, HSES_YIELD_TAG_BIT, heatshrink_encoder::match_length, heatshrink_encoder::match_pos, heatshrink_encoder::outgoing_bits, and heatshrink_encoder::outgoing_bits_count.

Referenced by heatshrink_encoder_poll(), and heatshrink_encoder_sink().

322  {
323  if (can_take_byte(oi)) {
324  if (hse->match_length == 0) {
326  return HSES_YIELD_LITERAL;
327  } else {
329  hse->outgoing_bits = hse->match_pos - 1;
331  return HSES_YIELD_BR_INDEX;
332  }
333  } else {
334  return HSES_YIELD_TAG_BIT; /* output is full, continue */
335  }
336 }
#define HEATSHRINK_ENCODER_WINDOW_BITS(HSE)
#define HEATSHRINK_BACKREF_MARKER
static void add_tag_bit(heatshrink_encoder *hse, output_info *oi, uint8_t tag)
#define HEATSHRINK_LITERAL_MARKER
static int can_take_byte(output_info *oi)
Here is the call graph for this function:
Here is the caller graph for this function: