You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
521 lines
16 KiB
521 lines
16 KiB
#include "heatshrink_config.h"
|
|
#ifdef HEATSHRINK_HAS_THEFT
|
|
|
|
#include <stdint.h>
|
|
#include <ctype.h>
|
|
#include <assert.h>
|
|
#include <string.h>
|
|
#include <sys/time.h>
|
|
|
|
#include "heatshrink_encoder.h"
|
|
#include "heatshrink_decoder.h"
|
|
#include "greatest.h"
|
|
#include "theft.h"
|
|
#include "greatest_theft.h"
|
|
|
|
#if !HEATSHRINK_DYNAMIC_ALLOC
|
|
#error Must set HEATSHRINK_DYNAMIC_ALLOC to 1 for this test suite.
|
|
#endif
|
|
|
|
SUITE(properties);
|
|
|
|
typedef struct {
|
|
int limit;
|
|
int fails;
|
|
int dots;
|
|
} test_env;
|
|
|
|
typedef struct {
|
|
size_t size;
|
|
uint8_t buf[];
|
|
} rbuf;
|
|
|
|
static void *rbuf_alloc_cb(struct theft *t, theft_hash seed, void *env) {
|
|
test_env *te = (test_env *)env;
|
|
//printf("seed is 0x%016llx\n", seed);
|
|
|
|
size_t sz = (size_t)(seed % te->limit) + 1;
|
|
rbuf *r = malloc(sizeof(rbuf) + sz);
|
|
if (r == NULL) { return THEFT_ERROR; }
|
|
r->size = sz;
|
|
|
|
for (size_t i = 0; i < sz; i += sizeof(theft_hash)) {
|
|
theft_hash s = theft_random(t);
|
|
for (uint8_t b = 0; b < sizeof(theft_hash); b++) {
|
|
if (i + b >= sz) { break; }
|
|
r->buf[i + b] = (uint8_t) (s >> (8*b)) & 0xff;
|
|
}
|
|
}
|
|
|
|
return r;
|
|
}
|
|
|
|
static void rbuf_free_cb(void *instance, void *env) {
|
|
free(instance);
|
|
(void)env;
|
|
}
|
|
|
|
static uint64_t rbuf_hash_cb(void *instance, void *env) {
|
|
rbuf *r = (rbuf *)instance;
|
|
(void)env;
|
|
return theft_hash_onepass(r->buf, r->size);
|
|
}
|
|
|
|
/* Make a copy of a buffer, keeping NEW_SZ bytes starting at OFFSET. */
|
|
static void *copy_rbuf_subset(rbuf *cur, size_t new_sz, size_t byte_offset) {
|
|
if (new_sz == 0) { return THEFT_DEAD_END; }
|
|
rbuf *nr = malloc(sizeof(rbuf) + new_sz);
|
|
if (nr == NULL) { return THEFT_ERROR; }
|
|
nr->size = new_sz;
|
|
memcpy(nr->buf, &cur->buf[byte_offset], new_sz);
|
|
/* printf("%zu -> %zu\n", cur->size, new_sz); */
|
|
return nr;
|
|
}
|
|
|
|
/* Make a copy of a buffer, but only PORTION, starting OFFSET in
|
|
* (e.g. the third quarter is (0.25 at +0.75). Rounds to ints. */
|
|
static void *copy_rbuf_percent(rbuf *cur, float portion, float offset) {
|
|
size_t new_sz = cur->size * portion;
|
|
size_t byte_offset = (size_t)(cur->size * offset);
|
|
return copy_rbuf_subset(cur, new_sz, byte_offset);
|
|
}
|
|
|
|
/* How to shrink a random buffer to a simpler one. */
|
|
static void *rbuf_shrink_cb(void *instance, uint32_t tactic, void *env) {
|
|
rbuf *cur = (rbuf *)instance;
|
|
|
|
if (tactic == 0) { /* first half */
|
|
return copy_rbuf_percent(cur, 0.5, 0);
|
|
} else if (tactic == 1) { /* second half */
|
|
return copy_rbuf_percent(cur, 0.5, 0.5);
|
|
} else if (tactic <= 18) { /* drop 1-16 bytes at start */
|
|
const int last_tactic = 1;
|
|
const size_t drop = tactic - last_tactic;
|
|
if (cur->size < drop) { return THEFT_DEAD_END; }
|
|
return copy_rbuf_subset(cur, cur->size - drop, drop);
|
|
} else if (tactic <= 34) { /* drop 1-16 bytes at end */
|
|
const int last_tactic = 18;
|
|
const size_t drop = tactic - last_tactic;
|
|
if (cur->size < drop) { return THEFT_DEAD_END; }
|
|
return copy_rbuf_subset(cur, cur->size - drop, 0);
|
|
} else if (tactic == 35) {
|
|
/* Divide every byte by 2, saturating at 0 */
|
|
rbuf *cp = copy_rbuf_percent(cur, 1, 0);
|
|
if (cp == NULL) { return THEFT_ERROR; }
|
|
for (size_t i = 0; i < cp->size; i++) { cp->buf[i] /= 2; }
|
|
return cp;
|
|
} else if (tactic == 36) {
|
|
/* subtract 1 from every byte, saturating at 0 */
|
|
rbuf *cp = copy_rbuf_percent(cur, 1, 0);
|
|
if (cp == NULL) { return THEFT_ERROR; }
|
|
for (size_t i = 0; i < cp->size; i++) {
|
|
if (cp->buf[i] > 0) { cp->buf[i]--; }
|
|
}
|
|
return cp;
|
|
} else {
|
|
(void)env;
|
|
return THEFT_NO_MORE_TACTICS;
|
|
}
|
|
|
|
return THEFT_NO_MORE_TACTICS;
|
|
}
|
|
|
|
static void rbuf_print_cb(FILE *f, void *instance, void *env) {
|
|
rbuf *r = (rbuf *)instance;
|
|
(void)env;
|
|
fprintf(f, "buf[%zd]:\n ", r->size);
|
|
uint8_t bytes = 0;
|
|
for (size_t i = 0; i < r->size; i++) {
|
|
fprintf(f, "%02x", r->buf[i]);
|
|
bytes++;
|
|
if (bytes == 16) {
|
|
fprintf(f, "\n ");
|
|
bytes = 0;
|
|
}
|
|
}
|
|
fprintf(f, "\n");
|
|
}
|
|
|
|
static struct theft_type_info rbuf_info = {
|
|
.alloc = rbuf_alloc_cb,
|
|
.free = rbuf_free_cb,
|
|
.hash = rbuf_hash_cb,
|
|
.shrink = rbuf_shrink_cb,
|
|
.print = rbuf_print_cb,
|
|
};
|
|
|
|
static theft_progress_callback_res
|
|
progress_cb(struct theft_trial_info *info, void *env) {
|
|
test_env *te = (test_env *)env;
|
|
if ((info->trial & 0xff) == 0) {
|
|
printf(".");
|
|
fflush(stdout);
|
|
te->dots++;
|
|
if (te->dots == 64) {
|
|
printf("\n");
|
|
te->dots = 0;
|
|
}
|
|
}
|
|
|
|
if (info->status == THEFT_TRIAL_FAIL) {
|
|
te->fails++;
|
|
rbuf *cur = info->args[0];
|
|
if (cur->size < 5) { return THEFT_PROGRESS_HALT; }
|
|
}
|
|
|
|
if (te->fails > 10) {
|
|
return THEFT_PROGRESS_HALT;
|
|
}
|
|
return THEFT_PROGRESS_CONTINUE;
|
|
}
|
|
|
|
/* For an arbitrary input buffer, it should never get stuck in a
|
|
* state where the data has been sunk but no data can be polled. */
|
|
static theft_trial_res prop_should_not_get_stuck(void *input) {
|
|
/* Make a buffer large enough for the output: 4 KB of input with
|
|
* each 16 bits becoming up to 16 bytes will fit in a 64 KB buffer.
|
|
* (4 KB of input comes from `env.limit = 1 << 12;` below.) */
|
|
uint8_t output[64 * 1024];
|
|
heatshrink_decoder *hsd = heatshrink_decoder_alloc((64 * 1024L) - 1, 12, 4);
|
|
if (hsd == NULL) { return THEFT_TRIAL_ERROR; }
|
|
|
|
rbuf *r = (rbuf *)input;
|
|
|
|
size_t count = 0;
|
|
HSD_sink_res sres = heatshrink_decoder_sink(hsd, r->buf, r->size, &count);
|
|
if (sres != HSDR_SINK_OK) { return THEFT_TRIAL_ERROR; }
|
|
|
|
size_t out_sz = 0;
|
|
HSD_poll_res pres = heatshrink_decoder_poll(hsd, output, sizeof(output), &out_sz);
|
|
if (pres != HSDR_POLL_EMPTY) { return THEFT_TRIAL_FAIL; }
|
|
|
|
HSD_finish_res fres = heatshrink_decoder_finish(hsd);
|
|
heatshrink_decoder_free(hsd);
|
|
if (fres != HSDR_FINISH_DONE) { return THEFT_TRIAL_FAIL; }
|
|
|
|
return THEFT_TRIAL_PASS;
|
|
}
|
|
|
|
static bool get_time_seed(theft_seed *seed)
|
|
{
|
|
struct timeval tv;
|
|
if (-1 == gettimeofday(&tv, NULL)) { return false; }
|
|
*seed = (theft_seed)((tv.tv_sec << 32) | tv.tv_usec);
|
|
/* printf("seed is 0x%016llx\n", *seed); */
|
|
return true;
|
|
}
|
|
|
|
TEST decoder_fuzzing_should_not_detect_stuck_state(void) {
|
|
// Get a random number seed based on the time
|
|
theft_seed seed;
|
|
if (!get_time_seed(&seed)) { FAIL(); }
|
|
|
|
/* Pass the max buffer size for this property (4 KB) in a closure */
|
|
test_env env = { .limit = 1 << 12 };
|
|
|
|
theft_seed always_seeds = { 0xe87bb1f61032a061 };
|
|
|
|
struct theft *t = theft_init(0);
|
|
struct theft_cfg cfg = {
|
|
.name = __func__,
|
|
.fun = prop_should_not_get_stuck,
|
|
.type_info = { &rbuf_info },
|
|
.seed = seed,
|
|
.trials = 100000,
|
|
.progress_cb = progress_cb,
|
|
.env = &env,
|
|
|
|
.always_seeds = &always_seeds,
|
|
.always_seed_count = 1,
|
|
};
|
|
|
|
theft_run_res res = theft_run(t, &cfg);
|
|
theft_free(t);
|
|
printf("\n");
|
|
GREATEST_ASSERT_EQm("should_not_get_stuck", THEFT_RUN_PASS, res);
|
|
PASS();
|
|
}
|
|
|
|
static theft_trial_res prop_encoded_and_decoded_data_should_match(void *input) {
|
|
uint8_t e_output[64 * 1024];
|
|
uint8_t d_output[64 * 1024];
|
|
heatshrink_encoder *hse = heatshrink_encoder_alloc(12, 4);
|
|
if (hse == NULL) { return THEFT_TRIAL_ERROR; }
|
|
heatshrink_decoder *hsd = heatshrink_decoder_alloc(4096, 12, 4);
|
|
if (hsd == NULL) { return THEFT_TRIAL_ERROR; }
|
|
|
|
rbuf *r = (rbuf *)input;
|
|
|
|
size_t e_input_size = 0;
|
|
HSE_sink_res esres = heatshrink_encoder_sink(hse,
|
|
r->buf, r->size, &e_input_size);
|
|
if (esres != HSER_SINK_OK) { return THEFT_TRIAL_ERROR; }
|
|
if (e_input_size != r->size) { printf("FAIL %d\n", __LINE__); return THEFT_TRIAL_FAIL; }
|
|
|
|
HSE_finish_res efres = heatshrink_encoder_finish(hse);
|
|
if (efres != HSER_FINISH_MORE) { printf("FAIL %d\n", __LINE__); return THEFT_TRIAL_FAIL; }
|
|
|
|
size_t e_output_size = 0;
|
|
HSE_poll_res epres = heatshrink_encoder_poll(hse,
|
|
e_output, sizeof(e_output), &e_output_size);
|
|
if (epres != HSER_POLL_EMPTY) { printf("FAIL %d\n", __LINE__); return THEFT_TRIAL_FAIL; }
|
|
|
|
size_t count = 0;
|
|
HSD_sink_res sres = heatshrink_decoder_sink(hsd, e_output, e_output_size, &count);
|
|
if (sres != HSDR_SINK_OK) { return THEFT_TRIAL_ERROR; }
|
|
|
|
size_t d_output_size = 0;
|
|
HSD_poll_res pres = heatshrink_decoder_poll(hsd, d_output,
|
|
sizeof(d_output), &d_output_size);
|
|
if (pres != HSDR_POLL_EMPTY) { printf("FAIL %d\n", __LINE__); return THEFT_TRIAL_FAIL; }
|
|
if (d_output_size != r->size) {
|
|
printf("FAIL %d\n", __LINE__); return THEFT_TRIAL_FAIL;
|
|
}
|
|
|
|
if (0 != memcmp(d_output, r->buf, d_output_size)) {
|
|
return THEFT_TRIAL_FAIL;
|
|
}
|
|
|
|
HSD_finish_res fres = heatshrink_decoder_finish(hsd);
|
|
if (fres != HSDR_FINISH_DONE) { printf("FAIL %d\n", __LINE__); return THEFT_TRIAL_FAIL; }
|
|
|
|
heatshrink_encoder_free(hse);
|
|
heatshrink_decoder_free(hsd);
|
|
return THEFT_TRIAL_PASS;
|
|
}
|
|
|
|
|
|
TEST encoded_and_decoded_data_should_match(void) {
|
|
test_env env = { .limit = 1 << 11 };
|
|
|
|
theft_seed seed;
|
|
if (!get_time_seed(&seed)) { FAIL(); }
|
|
|
|
struct theft *t = theft_init(0);
|
|
struct theft_cfg cfg = {
|
|
.name = __func__,
|
|
.fun = prop_encoded_and_decoded_data_should_match,
|
|
.type_info = { &rbuf_info },
|
|
.seed = seed,
|
|
.trials = 1000000,
|
|
.env = &env,
|
|
.progress_cb = progress_cb,
|
|
};
|
|
|
|
theft_run_res res = theft_run(t, &cfg);
|
|
theft_free(t);
|
|
printf("\n");
|
|
ASSERT_EQ(THEFT_RUN_PASS, res);
|
|
PASS();
|
|
}
|
|
|
|
static size_t ceil_nine_eighths(size_t sz) {
|
|
return sz + sz/8 + (sz & 0x07 ? 1 : 0);
|
|
}
|
|
|
|
static theft_trial_res
|
|
prop_encoding_data_should_never_increase_it_by_more_than_an_eighth_at_worst(void *input) {
|
|
uint8_t output[32 * 1024];
|
|
heatshrink_encoder *hse = heatshrink_encoder_alloc(12, 4);
|
|
if (hse == NULL) { return THEFT_TRIAL_ERROR; }
|
|
|
|
rbuf *r = (rbuf *)input;
|
|
|
|
size_t input_size = 0;
|
|
HSE_sink_res esres = heatshrink_encoder_sink(hse,
|
|
r->buf, r->size, &input_size);
|
|
if (esres != HSER_SINK_OK) { return THEFT_TRIAL_ERROR; }
|
|
/* Assumes data fits in one sink, failure here means buffer must be larger. */
|
|
if (input_size != r->size) { printf("FAIL %d\n", __LINE__); return THEFT_TRIAL_FAIL; }
|
|
|
|
HSE_finish_res efres = heatshrink_encoder_finish(hse);
|
|
if (efres != HSER_FINISH_MORE) { printf("FAIL %d\n", __LINE__); return THEFT_TRIAL_FAIL; }
|
|
|
|
size_t output_size = 0;
|
|
HSE_poll_res epres = heatshrink_encoder_poll(hse,
|
|
output, sizeof(output), &output_size);
|
|
if (epres != HSER_POLL_EMPTY) { printf("FAIL %d\n", __LINE__); return THEFT_TRIAL_FAIL; }
|
|
|
|
size_t ceil_9_8s = ceil_nine_eighths(r->size);
|
|
if (output_size > ceil_9_8s) {
|
|
return THEFT_TRIAL_FAIL;
|
|
}
|
|
|
|
heatshrink_encoder_free(hse);
|
|
return THEFT_TRIAL_PASS;
|
|
}
|
|
|
|
TEST encoding_data_should_never_increase_it_by_more_than_an_eighth_at_worst(void) {
|
|
test_env env = { .limit = 1 << 11 };
|
|
|
|
theft_seed seed;
|
|
if (!get_time_seed(&seed)) { FAIL(); }
|
|
|
|
struct theft *t = theft_init(0);
|
|
struct theft_cfg cfg = {
|
|
.name = __func__,
|
|
.fun = prop_encoding_data_should_never_increase_it_by_more_than_an_eighth_at_worst,
|
|
.type_info = { &rbuf_info },
|
|
.seed = seed,
|
|
.trials = 10000,
|
|
.env = &env,
|
|
.progress_cb = progress_cb,
|
|
};
|
|
|
|
theft_run_res res = theft_run(t, &cfg);
|
|
theft_free(t);
|
|
printf("\n");
|
|
ASSERT_EQ(THEFT_RUN_PASS, res);
|
|
PASS();
|
|
}
|
|
|
|
static theft_trial_res
|
|
prop_encoder_should_always_make_progress(void *instance) {
|
|
uint8_t output[64 * 1024];
|
|
heatshrink_encoder *hse = heatshrink_encoder_alloc(8, 4);
|
|
if (hse == NULL) { return THEFT_TRIAL_ERROR; }
|
|
|
|
rbuf *r = (rbuf *)instance;
|
|
|
|
size_t sunk = 0;
|
|
int no_progress = 0;
|
|
|
|
while (1) {
|
|
if (sunk < r->size) {
|
|
size_t input_size = 0;
|
|
HSE_sink_res esres = heatshrink_encoder_sink(hse,
|
|
&r->buf[sunk], r->size - sunk, &input_size);
|
|
if (esres != HSER_SINK_OK) { return THEFT_TRIAL_ERROR; }
|
|
sunk += input_size;
|
|
} else {
|
|
HSE_finish_res efres = heatshrink_encoder_finish(hse);
|
|
if (efres == HSER_FINISH_DONE) {
|
|
break;
|
|
} else if (efres != HSER_FINISH_MORE) {
|
|
printf("FAIL %d\n", __LINE__);
|
|
return THEFT_TRIAL_FAIL;
|
|
}
|
|
}
|
|
|
|
size_t output_size = 0;
|
|
HSE_poll_res epres = heatshrink_encoder_poll(hse,
|
|
output, sizeof(output), &output_size);
|
|
if (epres < 0) { return THEFT_TRIAL_ERROR; }
|
|
if (output_size == 0 && sunk == r->size) {
|
|
no_progress++;
|
|
if (no_progress > 2) {
|
|
return THEFT_TRIAL_FAIL;
|
|
}
|
|
} else {
|
|
no_progress = 0;
|
|
}
|
|
}
|
|
|
|
heatshrink_encoder_free(hse);
|
|
return THEFT_TRIAL_PASS;
|
|
}
|
|
|
|
TEST encoder_should_always_make_progress(void) {
|
|
test_env env = { .limit = 1 << 15 };
|
|
|
|
theft_seed seed;
|
|
if (!get_time_seed(&seed)) { FAIL(); }
|
|
|
|
struct theft *t = theft_init(0);
|
|
struct theft_cfg cfg = {
|
|
.name = __func__,
|
|
.fun = prop_encoder_should_always_make_progress,
|
|
.type_info = { &rbuf_info },
|
|
.seed = seed,
|
|
.trials = 10000,
|
|
.env = &env,
|
|
.progress_cb = progress_cb,
|
|
};
|
|
|
|
theft_run_res res = theft_run(t, &cfg);
|
|
theft_free(t);
|
|
printf("\n");
|
|
ASSERT_EQ(THEFT_RUN_PASS, res);
|
|
PASS();
|
|
}
|
|
|
|
static theft_trial_res
|
|
prop_decoder_should_always_make_progress(void *instance) {
|
|
uint8_t output[64 * 1024];
|
|
heatshrink_decoder *hsd = heatshrink_decoder_alloc(512, 8, 4);
|
|
if (hsd == NULL) { return THEFT_TRIAL_ERROR; }
|
|
|
|
rbuf *r = (rbuf *)instance;
|
|
|
|
size_t sunk = 0;
|
|
int no_progress = 0;
|
|
|
|
while (1) {
|
|
if (sunk < r->size) {
|
|
size_t input_size = 0;
|
|
HSD_sink_res sres = heatshrink_decoder_sink(hsd,
|
|
&r->buf[sunk], r->size - sunk, &input_size);
|
|
if (sres != HSER_SINK_OK) { return THEFT_TRIAL_ERROR; }
|
|
sunk += input_size;
|
|
} else {
|
|
HSD_finish_res fres = heatshrink_decoder_finish(hsd);
|
|
if (fres == HSDR_FINISH_DONE) {
|
|
break;
|
|
} else if (fres != HSDR_FINISH_MORE) {
|
|
printf("FAIL %d\n", __LINE__);
|
|
return THEFT_TRIAL_FAIL;
|
|
}
|
|
}
|
|
|
|
size_t output_size = 0;
|
|
HSD_poll_res pres = heatshrink_decoder_poll(hsd,
|
|
output, sizeof(output), &output_size);
|
|
if (pres < 0) { return THEFT_TRIAL_ERROR; }
|
|
if (output_size == 0 && sunk == r->size) {
|
|
no_progress++;
|
|
if (no_progress > 2) {
|
|
return THEFT_TRIAL_FAIL;
|
|
}
|
|
} else {
|
|
no_progress = 0;
|
|
}
|
|
}
|
|
|
|
heatshrink_decoder_free(hsd);
|
|
return THEFT_TRIAL_PASS;
|
|
}
|
|
|
|
TEST decoder_should_always_make_progress(void) {
|
|
test_env env = { .limit = 1 << 15 };
|
|
|
|
theft_seed seed;
|
|
if (!get_time_seed(&seed)) { FAIL(); }
|
|
|
|
struct theft *t = theft_init(0);
|
|
struct theft_cfg cfg = {
|
|
.name = __func__,
|
|
.fun = prop_decoder_should_always_make_progress,
|
|
.type_info = { &rbuf_info },
|
|
.seed = seed,
|
|
.trials = 10000,
|
|
.env = &env,
|
|
.progress_cb = progress_cb,
|
|
};
|
|
|
|
theft_run_res res = theft_run(t, &cfg);
|
|
theft_free(t);
|
|
printf("\n");
|
|
ASSERT_EQ(THEFT_RUN_PASS, res);
|
|
PASS();
|
|
}
|
|
|
|
SUITE(properties) {
|
|
RUN_TEST(decoder_fuzzing_should_not_detect_stuck_state);
|
|
RUN_TEST(encoded_and_decoded_data_should_match);
|
|
RUN_TEST(encoding_data_should_never_increase_it_by_more_than_an_eighth_at_worst);
|
|
RUN_TEST(encoder_should_always_make_progress);
|
|
RUN_TEST(decoder_should_always_make_progress);
|
|
}
|
|
#else
|
|
struct because_iso_c_requires_at_least_one_declaration;
|
|
#endif
|
|
|