From 72c8155d9fc0eaeac72c053f46ebb7b231d4596a Mon Sep 17 00:00:00 2001 From: David Oberhollenzer Date: Tue, 31 Jan 2023 11:30:46 +0100 Subject: Reintegrate test code with library code Signed-off-by: David Oberhollenzer --- lib/util/test/base64_decode.c | 74 +++ lib/util/test/canonicalize_name.c | 78 +++ lib/util/test/epoch.c | 67 +++ lib/util/test/filename_sane.c | 94 ++++ lib/util/test/hex_decode.c | 66 +++ lib/util/test/is_memory_zero.c | 33 ++ lib/util/test/rbtree.c | 233 +++++++++ lib/util/test/str_table.c | 85 ++++ lib/util/test/threadpool.c | 168 +++++++ lib/util/test/words.txt | 1000 +++++++++++++++++++++++++++++++++++++ lib/util/test/xxhash.c | 66 +++ 11 files changed, 1964 insertions(+) create mode 100644 lib/util/test/base64_decode.c create mode 100644 lib/util/test/canonicalize_name.c create mode 100644 lib/util/test/epoch.c create mode 100644 lib/util/test/filename_sane.c create mode 100644 lib/util/test/hex_decode.c create mode 100644 lib/util/test/is_memory_zero.c create mode 100644 lib/util/test/rbtree.c create mode 100644 lib/util/test/str_table.c create mode 100644 lib/util/test/threadpool.c create mode 100644 lib/util/test/words.txt create mode 100644 lib/util/test/xxhash.c (limited to 'lib/util/test') diff --git a/lib/util/test/base64_decode.c b/lib/util/test/base64_decode.c new file mode 100644 index 0000000..8f22a86 --- /dev/null +++ b/lib/util/test/base64_decode.c @@ -0,0 +1,74 @@ +/* SPDX-License-Identifier: GPL-3.0-or-later */ +/* + * base64_decode.c + * + * Copyright (C) 2022 David Oberhollenzer + */ +#include "config.h" +#include "util/util.h" +#include "util/test.h" + +static const struct { + int result; + const char *in; + const char *out; +} test_vec[] = { + { 0, "", "" }, + { 0, "Zg", "f" }, + { 0, "Zg==", "f" }, + { 0, "Zm8=", "fo" }, + { 0, "Zm9v", "foo" }, + { 0, "Zm9vYg==", "foob" }, + { 0, "Zm9vYmE=", "fooba" }, + { 0, "Zm9vYmFy", "foobar" }, + { 0, "TGV0J3MgYWxsIGxvdmUgTGFpbiEK", "Let's all love Lain!\n" }, + { -1, "Zg==X", "XX" }, +}; + +int main(int argc, char **argv) +{ + sqfs_u8 buffer[256]; + size_t i, j; + (void)argc; (void)argv; + + for (i = 0; i < sizeof(test_vec) / sizeof(test_vec[0]); ++i) { + const size_t in_len = strlen(test_vec[i].in); + const size_t out_len = strlen(test_vec[i].out); + size_t real_out; + int ret; + + /* initialize the buffer */ + for (j = 0; j < sizeof(buffer); ++j) { + buffer[j] = (j % 2) ? 0xAA : 0x55; + } + + /* convert */ + real_out = sizeof(buffer); + ret = base64_decode(test_vec[i].in, in_len, buffer, &real_out); + + /* make sure pattern is un-touched after expected offset */ + j = (in_len / 4) * 3; + if (in_len % 4) + j += 3; + + for (; j < sizeof(buffer); ++j) { + TEST_ASSERT(buffer[j] == ((j % 2) ? 0xAA : 0x55)); + } + + /* check result */ + if (test_vec[i].result == 0) { + TEST_ASSERT(ret == 0); + TEST_EQUAL_UI(real_out, out_len); + ret = memcmp(buffer, test_vec[i].out, out_len); + TEST_ASSERT(ret == 0); + } else { + TEST_ASSERT(ret != 0); + TEST_EQUAL_UI(real_out, 0); + } + + fprintf(stderr, "CASE %lu OK\n", (unsigned long)i); + } + + return EXIT_SUCCESS; +} + diff --git a/lib/util/test/canonicalize_name.c b/lib/util/test/canonicalize_name.c new file mode 100644 index 0000000..9f81b04 --- /dev/null +++ b/lib/util/test/canonicalize_name.c @@ -0,0 +1,78 @@ +/* SPDX-License-Identifier: GPL-3.0-or-later */ +/* + * canonicalize_name.c + * + * Copyright (C) 2019 David Oberhollenzer + */ +#include "config.h" +#include "util/util.h" +#include "util/test.h" + +static const struct { + const char *in; + const char *out; +} must_work[] = { + { "", "" }, + { "/", "" }, + { "\\", "\\" }, + { "///", "" }, + { "\\\\\\", "\\\\\\" }, + { "/\\//\\\\/", "\\/\\\\" }, + { "foo/bar/test", "foo/bar/test" }, + { "foo\\bar\\test", "foo\\bar\\test" }, + { "/foo/bar/test/", "foo/bar/test" }, + { "\\foo\\bar\\test\\", "\\foo\\bar\\test\\" }, + { "///foo//bar//test///", "foo/bar/test" }, + { "./foo/././bar/test/./.", "foo/bar/test" }, + { "./foo/././", "foo" }, + { ".", "" }, + { "./", "" }, + { "./.", "" }, + { "foo/.../bar", "foo/.../bar" }, + { "foo/.test/bar", "foo/.test/bar" }, +}; + +static const char *must_not_work[] = { + "..", + "foo/../bar", + "../foo/bar", + "foo/bar/..", + "foo/bar/../", +}; + +int main(int argc, char **argv) +{ + char buffer[512]; + size_t i; + (void)argc; (void)argv; + + for (i = 0; i < sizeof(must_work) / sizeof(must_work[0]); ++i) { + strcpy(buffer, must_work[i].in); + + if (canonicalize_name(buffer)) { + fprintf(stderr, "Test case rejected: '%s'\n", + must_work[i].in); + return EXIT_FAILURE; + } + + if (strcmp(buffer, must_work[i].out) != 0) { + fprintf(stderr, "Expected result: %s\n", + must_work[i].out); + fprintf(stderr, "Actual result: %s\n", buffer); + return EXIT_FAILURE; + } + } + + for (i = 0; i < sizeof(must_not_work) / sizeof(must_not_work[0]); ++i) { + strcpy(buffer, must_not_work[i]); + + if (canonicalize_name(buffer) == 0) { + fprintf(stderr, "Test case accepted: '%s'\n", + must_not_work[i]); + fprintf(stderr, "Transformed into: '%s'\n", buffer); + return EXIT_FAILURE; + } + } + + return EXIT_SUCCESS; +} diff --git a/lib/util/test/epoch.c b/lib/util/test/epoch.c new file mode 100644 index 0000000..a04942e --- /dev/null +++ b/lib/util/test/epoch.c @@ -0,0 +1,67 @@ +/* SPDX-License-Identifier: GPL-3.0-or-later */ +/* + * epoch.c + * + * Copyright (C) 2019 David Oberhollenzer + */ +#include "config.h" +#include "util/util.h" +#include "util/test.h" + +#if defined(_WIN32) || defined(__WINDOWS__) +static void setenv(const char *key, const char *value, int overwrite) +{ + char buffer[128]; + (void)overwrite; + + snprintf(buffer, sizeof(buffer) - 1, "%s=%s", key, value); + buffer[sizeof(buffer) - 1] = '\0'; + + _putenv(buffer); +} + +static void unsetenv(const char *key) +{ + setenv(key, "", 0); +} +#endif + +int main(int argc, char **argv) +{ + sqfs_u32 ts; + (void)argc; (void)argv; + + unsetenv("SOURCE_DATE_EPOCH"); + ts = get_source_date_epoch(); + TEST_EQUAL_UI(ts, 0); + + setenv("SOURCE_DATE_EPOCH", "1337", 1); + ts = get_source_date_epoch(); + TEST_EQUAL_UI(ts, 1337); + + setenv("SOURCE_DATE_EPOCH", "0xCAFE", 1); + ts = get_source_date_epoch(); + TEST_EQUAL_UI(ts, 0); + + setenv("SOURCE_DATE_EPOCH", "foobar", 1); + ts = get_source_date_epoch(); + TEST_EQUAL_UI(ts, 0); + + setenv("SOURCE_DATE_EPOCH", "-12", 1); + ts = get_source_date_epoch(); + TEST_EQUAL_UI(ts, 0); + + setenv("SOURCE_DATE_EPOCH", "12", 1); + ts = get_source_date_epoch(); + TEST_EQUAL_UI(ts, 12); + + setenv("SOURCE_DATE_EPOCH", "4294967295", 1); + ts = get_source_date_epoch(); + TEST_EQUAL_UI(ts, 0xFFFFFFFF); + + setenv("SOURCE_DATE_EPOCH", "4294967296", 1); + ts = get_source_date_epoch(); + TEST_EQUAL_UI(ts, 0); + + return EXIT_SUCCESS; +} diff --git a/lib/util/test/filename_sane.c b/lib/util/test/filename_sane.c new file mode 100644 index 0000000..9c9930d --- /dev/null +++ b/lib/util/test/filename_sane.c @@ -0,0 +1,94 @@ +/* SPDX-License-Identifier: GPL-3.0-or-later */ +/* + * filename_sane.c + * + * Copyright (C) 2019 David Oberhollenzer + */ +#include "config.h" +#include "util/util.h" +#include "util/test.h" + +static const char *must_work[] = { + "foobar", + "test.txt", +#if !defined(_WIN32) && !defined(__WINDOWS__) && !defined(TEST_WIN32) + "\\foo", "foo\\", "foo\\bar", +#endif + NULL, +}; + +static const char *must_not_work[] = { + ".", + "..", + "/foo", + "foo/", + "foo/bar", + NULL, +}; + +static const char *must_not_work_here[] = { +#if defined(_WIN32) || defined(__WINDOWS__) || defined(TEST_WIN32) + "\\foo", "foo\\", "foo\\bar", + "foo", "fo:o", "fo\"o", + "fo|o", "fo?o", "fo*o", "fo\ro", + "CON", "PRN", "AUX", "NUL", + "COM1", "COM2", "LPT1", "LPT2", + "con", "prn", "aux", "nul", + "com1", "com2", "lpt1", "lpt2", + "AUX.txt", "aux.txt", "NUL.txt", "nul.txt", +#endif + NULL, +}; + +int main(int argc, char **argv) +{ + size_t i; + (void)argc; (void)argv; + + for (i = 0; must_work[i] != NULL; ++i) { + if (!is_filename_sane(must_work[i], false)) { + fprintf(stderr, "%s was rejected!\n", must_work[i]); + return EXIT_FAILURE; + } + + if (!is_filename_sane(must_work[i], true)) { + fprintf(stderr, + "%s was rejected when testing for " + "OS specific stuff!\n", must_work[i]); + return EXIT_FAILURE; + } + } + + for (i = 0; must_not_work[i] != NULL; ++i) { + if (is_filename_sane(must_not_work[i], false)) { + fprintf(stderr, "%s was accepted!\n", + must_not_work[i]); + return EXIT_FAILURE; + } + + if (is_filename_sane(must_not_work[i], true)) { + fprintf(stderr, + "%s was accepted when testing for " + "OS specific stuff!\n", must_not_work[i]); + return EXIT_FAILURE; + } + } + + for (i = 0; must_not_work_here[i] != NULL; ++i) { + if (!is_filename_sane(must_not_work_here[i], false)) { + fprintf(stderr, + "%s was rejected in the generic test!\n", + must_not_work_here[i]); + return EXIT_FAILURE; + } + + if (is_filename_sane(must_not_work_here[i], true)) { + fprintf(stderr, + "%s was accepted when testing for " + "OS specific stuff!\n", must_not_work_here[i]); + return EXIT_FAILURE; + } + } + + return EXIT_SUCCESS; +} diff --git a/lib/util/test/hex_decode.c b/lib/util/test/hex_decode.c new file mode 100644 index 0000000..21ac4e7 --- /dev/null +++ b/lib/util/test/hex_decode.c @@ -0,0 +1,66 @@ +/* SPDX-License-Identifier: GPL-3.0-or-later */ +/* + * hex_decode.c + * + * Copyright (C) 2022 David Oberhollenzer + */ +#include "config.h" +#include "util/util.h" +#include "util/test.h" + +static const struct { + int result; + const char *in; + const char *out; +} test_vec[] = { + { 0, "", NULL }, + { -1, "A", NULL }, + { 0, "AA", "\xAA" }, + { 0, "0A", "\x0A" }, + { 0, "A0", "\xA0" }, + { -1, "A0B", NULL }, + { 0, "A0BC", "\xA0\xBC" }, + { 0, "0123456789ABCDEF", "\x01\x23\x45\x67\x89\xAB\xCD\xEF" }, + { 0, "0123456789abcdef", "\x01\x23\x45\x67\x89\xAB\xCD\xEF" }, + { -1, "0123456789ABCDEFGH", NULL }, + { -1, "0123456789abcdefgh", NULL }, +}; + +int main(int argc, char **argv) +{ + sqfs_u8 buffer[256]; + size_t i, j; + (void)argc; (void)argv; + + for (i = 0; i < sizeof(test_vec) / sizeof(test_vec[0]); ++i) { + size_t in_len = strlen(test_vec[i].in); + size_t out_len = in_len / 2; + int ret; + + /* initialize the buffer */ + for (j = 0; j < sizeof(buffer); ++j) { + buffer[j] = (j % 2) ? 0xAA : 0x55; + } + + /* convert */ + ret = hex_decode(test_vec[i].in, in_len, + buffer, sizeof(buffer)); + + /* make sure pattern is un-touched after expected offset */ + for (j = out_len; j < sizeof(buffer); ++j) { + TEST_ASSERT(buffer[j] == ((j % 2) ? 0xAA : 0x55)); + } + + /* check result */ + if (test_vec[i].result == 0) { + TEST_ASSERT(ret == 0); + ret = memcmp(buffer, test_vec[i].out, out_len); + TEST_ASSERT(ret == 0); + } else { + TEST_ASSERT(ret != 0); + } + } + + return EXIT_SUCCESS; +} + diff --git a/lib/util/test/is_memory_zero.c b/lib/util/test/is_memory_zero.c new file mode 100644 index 0000000..f62b0bb --- /dev/null +++ b/lib/util/test/is_memory_zero.c @@ -0,0 +1,33 @@ +/* SPDX-License-Identifier: GPL-3.0-or-later */ +/* + * is_memory_zero.c + * + * Copyright (C) 2021 David Oberhollenzer + */ +#include "config.h" + +#include "util/test.h" +#include "util/util.h" + +int main(int argc, char **argv) +{ + unsigned char temp[1024]; + size_t i, j; + (void)argc; (void)argv; + + memset(temp, 0, sizeof(temp)); + + for (i = 0; i < sizeof(temp); ++i) { + TEST_ASSERT(is_memory_zero(temp, i)); + + for (j = 0; j < i; ++j) { + TEST_ASSERT(is_memory_zero(temp, i)); + temp[j] = 42; + TEST_ASSERT(!is_memory_zero(temp, i)); + temp[j] = 0; + TEST_ASSERT(is_memory_zero(temp, i)); + } + } + + return EXIT_SUCCESS; +} diff --git a/lib/util/test/rbtree.c b/lib/util/test/rbtree.c new file mode 100644 index 0000000..ca01c0d --- /dev/null +++ b/lib/util/test/rbtree.c @@ -0,0 +1,233 @@ +/* SPDX-License-Identifier: GPL-3.0-or-later */ +/* + * rbtree.c + * + * Copyright (C) 2020 David Oberhollenzer + */ +#include "config.h" + +#include "util/rbtree.h" +#include "util/test.h" + +static int key_compare(const void *ctx, const void *a, const void *b) +{ + (void)ctx; + return *((const sqfs_s32 *)a) - *((const sqfs_s32 *)b); +} + +static size_t count_nodes_dfs(rbtree_node_t *n) +{ + return 1 + (n->left == NULL ? 0 : count_nodes_dfs(n->left)) + + (n->right == NULL ? 0 : count_nodes_dfs(n->right)); +} + +static size_t min_depth(rbtree_node_t *n) +{ + size_t lhs, rhs; + + if (n == NULL) + return 0; + + lhs = min_depth(n->left) + 1; + rhs = min_depth(n->right) + 1; + + return lhs < rhs ? lhs : rhs; +} + +static size_t max_depth(rbtree_node_t *n) +{ + size_t lhs, rhs; + + if (n == NULL) + return 0; + + lhs = min_depth(n->left) + 1; + rhs = min_depth(n->right) + 1; + + return lhs > rhs ? lhs : rhs; +} + +static size_t get_ref_black_depth(rbtree_t *rb) +{ + rbtree_node_t *n; + size_t count = 0; + + for (n = rb->root; n != NULL; n = n->left) { + if (!n->is_red) + count += 1; + } + + return count; +} + +static void check_binary_tree_dfs(rbtree_node_t *n) +{ + const void *key = rbtree_node_key(n); + const void *cmp; + + if (n->left != NULL) { + cmp = rbtree_node_key(n->left); + TEST_ASSERT(key_compare(NULL, cmp, key) < 0); + + check_binary_tree_dfs(n->left); + } + + if (n->right != NULL) { + cmp = rbtree_node_key(n->right); + TEST_ASSERT(key_compare(NULL, cmp, key) > 0); + + check_binary_tree_dfs(n->right); + } +} + +static void check_colors_dfs(rbtree_node_t *n) +{ + if (n->is_red) { + TEST_ASSERT(n->left == NULL || !n->left->is_red); + TEST_ASSERT(n->right == NULL || !n->right->is_red); + } + + if (n->left != NULL) + check_colors_dfs(n->left); + + if (n->right != NULL) + check_colors_dfs(n->right); +} + +static void check_black_depth_dfs(rbtree_node_t *n, size_t ref, + size_t counter) +{ + if (!n->is_red) + counter += 1; + + if (n->left == NULL || n->right == NULL) + TEST_EQUAL_UI(counter, ref); + + if (n->left != NULL) + check_black_depth_dfs(n->left, ref, counter); + + if (n->right != NULL) + check_black_depth_dfs(n->right, ref, counter); +} + +static int check_subtrees_equal(const rbtree_node_t *lhs, + const rbtree_node_t *rhs, + size_t datasize) +{ + if (lhs == rhs) + return -1; + + if (lhs->value_offset != rhs->value_offset) + return -1; + + if ((lhs->is_red && !rhs->is_red) || (!lhs->is_red && rhs->is_red)) + return -1; + + if (memcmp(lhs->data, rhs->data, datasize) != 0) + return -1; + + if (lhs->left == NULL) { + if (rhs->left != NULL) + return -1; + } else { + if (rhs->left == NULL) + return -1; + + if (check_subtrees_equal(lhs->left, rhs->left, datasize)) + return -1; + } + + if (lhs->right == NULL) { + if (rhs->right != NULL) + return -1; + } else { + if (rhs->right == NULL) + return -1; + + if (check_subtrees_equal(lhs->right, rhs->right, datasize)) + return -1; + } + + return 0; +} + +int main(int argc, char **argv) +{ + size_t count, blkdepth, mind, maxd; + sqfs_s32 key, key2; + rbtree_t rb, copy; + rbtree_node_t *n; + sqfs_u64 value; + int ret; + (void)argc; (void)argv; + + TEST_ASSERT(rbtree_init(&rb, sizeof(sqfs_s32), + sizeof(sqfs_u64), key_compare) == 0); + + count = 0; + + for (key = -1000; key < 1000; ++key) { + /* lookup of current key must fail prior to insert */ + TEST_NULL(rbtree_lookup(&rb, &key)); + + /* previous key/value pairs must still be there */ + for (key2 = -1000; key2 < key; ++key2) { + n = rbtree_lookup(&rb, &key2); + TEST_NOT_NULL(n); + value = *((sqfs_u64 *)rbtree_node_value(n)); + TEST_EQUAL_UI((sqfs_u64)(key2 + 10000), value); + } + + /* insert key value pair */ + value = key + 10000; + TEST_ASSERT(rbtree_insert(&rb, &key, &value) == 0); + count += 1; + + /* check if the tree has the right number of nodes */ + TEST_EQUAL_UI(count_nodes_dfs(rb.root), count); + + /* check if it is still a binary tree */ + check_binary_tree_dfs(rb.root); + + /* root node must be black. Every red node + must have black children. */ + TEST_ASSERT(!rb.root->is_red); + check_colors_dfs(rb.root); + + /* every path from the root to a leave must have + the same number of black nodes. */ + blkdepth = get_ref_black_depth(&rb); + check_black_depth_dfs(rb.root, blkdepth, 0); + + /* longest root to leaf path must be at most + twice as long as the shortest. */ + mind = min_depth(rb.root); + maxd = max_depth(rb.root); + TEST_ASSERT(maxd <= mind * 2); + + /* lookup of current key must work after insert */ + n = rbtree_lookup(&rb, &key); + TEST_NOT_NULL(n); + value = *((sqfs_u64 *)rbtree_node_value(n)); + TEST_EQUAL_UI((sqfs_u64)(key + 10000), value); + } + + /* test if copy works */ + ret = rbtree_copy(&rb, ©); + TEST_EQUAL_I(ret, 0); + + TEST_EQUAL_UI(rb.key_size, copy.key_size); + TEST_EQUAL_UI(rb.key_size_padded, copy.key_size_padded); + TEST_EQUAL_UI(rb.value_size, copy.value_size); + TEST_ASSERT(rb.key_compare == copy.key_compare); + TEST_ASSERT(rb.root != copy.root); + + ret = check_subtrees_equal(rb.root, copy.root, + rb.key_size_padded + rb.value_size); + TEST_EQUAL_I(ret, 0); + + /* cleanup */ + rbtree_cleanup(&rb); + rbtree_cleanup(©); + return EXIT_SUCCESS; +} diff --git a/lib/util/test/str_table.c b/lib/util/test/str_table.c new file mode 100644 index 0000000..d4160eb --- /dev/null +++ b/lib/util/test/str_table.c @@ -0,0 +1,85 @@ +/* SPDX-License-Identifier: GPL-3.0-or-later */ +/* + * str_table.c + * + * Copyright (C) 2019 David Oberhollenzer + */ +#include "config.h" + +#include "util/str_table.h" +#include "io/file.h" +#include "compat.h" +#include "util/test.h" + +static char *strings[1000]; + +static int read_strings(void) +{ + istream_t *fp; + ssize_t ret; + char *line; + int i; + + fp = istream_open_file("words.txt"); + TEST_NOT_NULL(fp); + + for (i = 0; i < 1000; ++i) { + ret = istream_get_line(fp, &line, NULL, 0); + TEST_EQUAL_I(ret, 0); + + strings[i] = line; + } + + sqfs_drop(fp); + return 0; +} + +int main(int argc, char **argv) +{ + str_table_t table; + size_t i, j, idx; + const char *str; + (void)argc; (void)argv; + + TEST_ASSERT(chdir(TEST_PATH) == 0); + + if (read_strings()) + return EXIT_FAILURE; + + TEST_ASSERT(str_table_init(&table) == 0); + + for (i = 0; i < 1000; ++i) { + TEST_ASSERT(str_table_get_index(&table, strings[i], &idx) == 0); + + TEST_EQUAL_UI(idx, i); + + for (j = 0; j <= i; ++j) { + str = str_table_get_string(&table, j); + + TEST_NOT_NULL(str); + TEST_ASSERT(str != strings[i]); + TEST_STR_EQUAL(str, strings[j]); + } + + for (; j < 1000; ++j) + TEST_NULL(str_table_get_string(&table, j)); + } + + for (i = 0; i < 1000; ++i) { + TEST_ASSERT(str_table_get_index(&table, strings[i], &idx) == 0); + TEST_EQUAL_UI(idx, i); + + str = str_table_get_string(&table, i); + + TEST_NOT_NULL(str); + TEST_ASSERT(str != strings[i]); + TEST_STR_EQUAL(str, strings[i]); + } + + str_table_cleanup(&table); + + for (i = 0; i < 1000; ++i) + free(strings[i]); + + return EXIT_SUCCESS; +} diff --git a/lib/util/test/threadpool.c b/lib/util/test/threadpool.c new file mode 100644 index 0000000..cf54484 --- /dev/null +++ b/lib/util/test/threadpool.c @@ -0,0 +1,168 @@ +/* SPDX-License-Identifier: LGPL-3.0-or-later */ +/* + * threadpool.c + * + * Copyright (C) 2021 David Oberhollenzer + */ +#include "config.h" + +#include "util/threadpool.h" +#include "util/test.h" + +#if defined(_WIN32) || defined(__WINDOWS__) +#define WIN32_LEAN_AND_MEAN +#define VC_EXTRALEAN +#include + +static CRITICAL_SECTION mutex; +static unsigned int ticket; + +static void ticket_init(void) +{ + InitializeCriticalSection(&mutex); + ticket = 0; +} + +static void ticket_cleanup(void) +{ + DeleteCriticalSection(&mutex); + ticket = 0; +} + +static void ticket_wait(unsigned int value) +{ + for (;;) { + EnterCriticalSection(&mutex); + + if (value == ticket) { + ticket += 1; + LeaveCriticalSection(&mutex); + break; + } + + LeaveCriticalSection(&mutex); + SwitchToThread(); + } +} +#elif defined(HAVE_PTHREAD) +#include + +static pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER; +static unsigned int ticket; + +static void ticket_init(void) +{ + ticket = 0; +} + +static void ticket_cleanup(void) +{ +} + +static void ticket_wait(unsigned int value) +{ + for (;;) { + pthread_mutex_lock(&mutex); + + if (value == ticket) { + ticket += 1; + pthread_mutex_unlock(&mutex); + break; + } + + pthread_mutex_unlock(&mutex); + sched_yield(); + } +} +#else +static void ticket_init(void) +{ +} + +static void ticket_cleanup(void) +{ +} + +static void ticket_wait(unsigned int value) +{ + (void)value; +} +#endif + +static int worker(void *user, void *work_item) +{ + unsigned int value = *((unsigned int *)work_item); + (void)user; + + ticket_wait(value); + + *((unsigned int *)work_item) = 42; + return 0; +} + +static int worker_serial(void *user, void *work_item) +{ + (void)user; + *((unsigned int *)work_item) = 42; + return 0; +} + +static void test_case(thread_pool_t *pool) +{ + unsigned int values[10]; + unsigned int *ptr; + size_t i, count; + int ret; + + /* must return a sane value */ + count = pool->get_worker_count(pool); + TEST_ASSERT(count >= 1); + + /* dequeue on empty pool MUST NOT lock up */ + ptr = pool->dequeue(pool); + TEST_NULL(ptr); + + /* submit work items in reverse order */ + ticket_init(); + + for (i = 0; i < sizeof(values) / sizeof(values[0]); ++i) { + values[i] = (sizeof(values) / sizeof(values[0]) - 1) - i; + + ret = pool->submit(pool, values + i); + TEST_EQUAL_I(ret, 0); + } + + /* items must dequeue in the same order */ + for (i = 0; i < sizeof(values) / sizeof(values[0]); ++i) { + ptr = pool->dequeue(pool); + + TEST_NOT_NULL(ptr); + TEST_ASSERT(ptr == (values + i)); + TEST_EQUAL_UI(*ptr, 42); + } + + ticket_cleanup(); + + /* queue now empty */ + ptr = pool->dequeue(pool); + TEST_NULL(ptr); +} + +int main(int argc, char **argv) +{ + thread_pool_t *pool; + (void)argc; (void)argv; + + /* test the actual parallel implementation */ + pool = thread_pool_create(10, worker); + TEST_NOT_NULL(pool); + test_case(pool); + pool->destroy(pool); + + /* repeate the test with the serial reference implementation */ + pool = thread_pool_create_serial(worker_serial); + TEST_NOT_NULL(pool); + test_case(pool); + pool->destroy(pool); + return EXIT_SUCCESS; +} diff --git a/lib/util/test/words.txt b/lib/util/test/words.txt new file mode 100644 index 0000000..9496e14 --- /dev/null +++ b/lib/util/test/words.txt @@ -0,0 +1,1000 @@ +a +ability +able +about +above +accept +according +account +across +act +action +activity +actually +add +address +administration +admit +adult +affect +after +again +against +age +agency +agent +ago +agree +agreement +ahead +air +all +allow +almost +alone +along +already +also +although +always +American +among +amount +analysis +and +animal +another +answer +any +anyone +anything +appear +apply +approach +area +argue +arm +around +arrive +art +article +artist +as +ask +assume +at +attack +attention +attorney +audience +author +authority +available +avoid +away +baby +back +bad +bag +ball +bank +bar +base +be +beat +beautiful +because +become +bed +before +begin +behavior +behind +believe +benefit +best +better +between +beyond +big +bill +billion +bit +black +blood +blue +board +body +book +born +both +box +boy +break +bring +brother +budget +build +building +business +but +buy +by +call +camera +campaign +can +cancer +candidate +capital +car +card +care +career +carry +case +catch +cause +cell +center +central +century +certain +certainly +chair +challenge +chance +change +character +charge +check +child +choice +choose +church +citizen +city +civil +claim +class +clear +clearly +close +coach +cold +collection +college +color +come +commercial +common +community +company +compare +computer +concern +condition +conference +Congress +consider +consumer +contain +continue +control +cost +could +country +couple +course +court +cover +create +crime +cultural +culture +cup +current +customer +cut +dark +data +daughter +day +dead +deal +death +debate +decade +decide +decision +deep +defense +degree +Democrat +democratic +describe +design +despite +detail +determine +develop +development +die +difference +different +difficult +dinner +direction +director +discover +discuss +discussion +disease +do +doctor +dog +door +down +draw +dream +drive +drop +drug +during +each +early +east +easy +eat +economic +economy +edge +education +effect +effort +eight +either +election +else +employee +end +energy +enjoy +enough +enter +entire +environment +environmental +especially +establish +even +evening +event +ever +every +everybody +everyone +everything +evidence +exactly +example +executive +exist +expect +experience +expert +explain +eye +face +fact +factor +fail +fall +family +far +fast +father +fear +federal +feel +feeling +few +field +fight +figure +fill +film +final +finally +financial +find +fine +finger +finish +fire +firm +first +fish +five +floor +fly +focus +follow +food +foot +for +force +foreign +forget +form +former +forward +four +free +friend +from +front +full +fund +future +game +garden +gas +general +generation +get +girl +give +glass +go +goal +good +government +great +green +ground +group +grow +growth +guess +gun +guy +hair +half +hand +hang +happen +happy +hard +have +he +head +health +hear +heart +heat +heavy +help +her +here +herself +high +him +himself +his +history +hit +hold +home +hope +hospital +hot +hotel +hour +house +how +however +huge +human +hundred +husband +I +idea +identify +if +image +imagine +impact +important +improve +in +include +including +increase +indeed +indicate +individual +industry +information +inside +instead +institution +interest +interesting +international +interview +into +investment +involve +issue +it +item +its +itself +job +join +just +keep +key +kid +kill +kind +kitchen +know +knowledge +land +language +large +last +late +later +laugh +law +lawyer +lay +lead +leader +learn +least +leave +left +leg +legal +less +let +letter +level +lie +life +light +like +likely +line +list +listen +little +live +local +long +look +lose +loss +lot +love +low +machine +magazine +main +maintain +major +majority +make +man +manage +management +manager +many +market +marriage +material +matter +may +maybe +me +mean +measure +media +medical +meet +meeting +member +memory +mention +message +method +middle +might +military +million +mind +minute +miss +mission +model +modern +moment +money +month +more +morning +most +mother +mouth +move +movement +movie +Mr +Mrs +much +music +must +my +myself +name +nation +national +natural +nature +near +nearly +necessary +need +network +never +new +news +newspaper +next +nice +night +no +none +nor +north +not +note +nothing +notice +now +n't +number +occur +of +off +offer +office +officer +official +often +oh +oil +ok +old +on +once +one +only +onto +open +operation +opportunity +option +or +order +organization +other +others +our +out +outside +over +own +owner +page +pain +painting +paper +parent +part +participant +particular +particularly +partner +party +pass +past +patient +pattern +pay +peace +people +per +perform +performance +perhaps +period +person +personal +phone +physical +pick +picture +piece +place +plan +plant +play +player +PM +point +police +policy +political +politics +poor +popular +population +position +positive +possible +power +practice +prepare +present +president +pressure +pretty +prevent +price +private +probably +problem +process +produce +product +production +professional +professor +program +project +property +protect +prove +provide +public +pull +purpose +push +put +quality +question +quickly +quite +race +radio +raise +range +rate +rather +reach +read +ready +real +reality +realize +really +reason +receive +recent +recently +recognize +record +red +reduce +reflect +region +relate +relationship +religious +remain +remember +remove +report +represent +Republican +require +research +resource +respond +response +responsibility +rest +result +return +reveal +rich +right +rise +risk +road +rock +role +room +rule +run +safe +same +save +say +scene +school +science +scientist +score +sea +season +seat +second +section +security +see +seek +seem +sell +send +senior +sense +series +serious +serve +service +set +seven +several +sex +sexual +shake +share +she +shoot +short +shot +should +shoulder +show +side +sign +significant +similar +simple +simply +since +sing +single +sister +sit +site +situation +six +size +skill +skin +small +smile +so +social +society +soldier +some +somebody +someone +something +sometimes +son +song +soon +sort +sound +source +south +southern +space +speak +special +specific +speech +spend +sport +spring +staff +stage +stand +standard +star +start +state +statement +station +stay +step +still +stock +stop +store +story +strategy +street +strong +structure +student +study +stuff +style +subject +success +successful +such +suddenly +suffer +suggest +summer +support +sure +surface +system +table +take +talk +task +tax +teach +teacher +team +technology +television +tell +ten +tend +term +test +than +thank +that +the +their +them +themselves +then +theory +there +these +they +thing +think +third +this +those +though +thought +thousand +threat +three +through +throughout +throw +thus +time +to +today +together +tonight +too +top +total +tough +toward +town +trade +traditional +training +travel +treat +treatment +tree +trial +trip +trouble +true +truth +try +turn +TV +two +type +under +understand +unit +until +up +upon +us +use +usually +value +various +very +victim +view +violence +visit +voice +vote +wait +walk +wall +want +war +watch +water +way +we +weapon +wear +week +weight +well +west +western +what +whatever +when +where +whether +which +while +white +who +whole +whom +whose +why +wide +wife +will +win +wind +window +wish +with +within +without +woman +wonder +word +work +worker +world +worry +would +write +writer +wrong +yard +yeah +year +yes +yet +you +young +your +yourself diff --git a/lib/util/test/xxhash.c b/lib/util/test/xxhash.c new file mode 100644 index 0000000..17374fd --- /dev/null +++ b/lib/util/test/xxhash.c @@ -0,0 +1,66 @@ +/* SPDX-License-Identifier: GPL-3.0-or-later */ +/* + * xxhash.c + * + * Copyright (C) 2020 David Oberhollenzer + */ +#include "config.h" + +#include "util/util.h" +#include "util/test.h" + +static const struct { + const char *plaintext; + size_t psize; + sqfs_u32 digest; +} test_vectors[] = { + { + .plaintext = "\x9e", + .psize = 1, + .digest = 0xB85CBEE5, + }, + { + .plaintext = "\x9e\xff\x1f\x4b\x5e\x53\x2f\xdd" + "\xb5\x54\x4d\x2a\x95\x2b", + .psize = 14, + .digest = 0xE5AA0AB4, + }, + { + .plaintext = "\x9e\xff\x1f\x4b\x5e\x53\x2f\xdd" + "\xb5\x54\x4d\x2a\x95\x2b\x57\xae" + "\x5d\xba\x74\xe9\xd3\xa6\x4c\x98" + "\x30\x60\xc0\x80\x00\x00\x00\x00" + "\x00\x00\x00\x00\x00\x00\x00\x00" + "\x00\x00\x00\x00\x00\x00\x00\x00" + "\x00\x00\x00\x00\x00\x00\x00\x00" + "\x00\x00\x00\x00\x00\x00\x00\x00" + "\x00\x00\x00\x00\x00\x00\x00\x00" + "\x00\x00\x00\x00\x00\x00\x00\x00" + "\x00\x00\x00\x00\x00\x00\x00\x00" + "\x00\x00\x00\x00\x00\x00\x00\x00" + "\x00\x00\x00\x00\x00", + .psize = 101, + .digest = 0x018F52BC, + }, +}; + +int main(int argc, char **argv) +{ + sqfs_u32 hash; + size_t i; + (void)argc; (void)argv; + + for (i = 0; i < sizeof(test_vectors) / sizeof(test_vectors[0]); ++i) { + hash = xxh32(test_vectors[i].plaintext, test_vectors[i].psize); + + if (hash != test_vectors[i].digest) { + fprintf(stderr, "Test case " PRI_SZ " failed!\n", i); + fprintf(stderr, "Expected result: 0x%08X\n", + test_vectors[i].digest); + fprintf(stderr, "Actual result: 0x%08X\n", hash); + return EXIT_FAILURE; + } + } + + return EXIT_SUCCESS; +} -- cgit v1.2.3