You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@mynewt.apache.org by je...@apache.org on 2020/03/04 07:49:52 UTC
[mynewt-core] branch master updated: Add base62 encoder/decoder
This is an automated email from the ASF dual-hosted git repository.
jerzy pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/mynewt-core.git
The following commit(s) were added to refs/heads/master by this push:
new 426a011 Add base62 encoder/decoder
426a011 is described below
commit 426a0112a8c796247c29ffadca89885872bdf9c8
Author: Jerzy Kasenberg <je...@codecoup.pl>
AuthorDate: Mon Feb 24 13:53:35 2020 +0100
Add base62 encoder/decoder
Base62 encoding code and unit tests.
---
encoding/base62/include/base62/base62.h | 75 ++++++++++
encoding/base62/pkg.yml | 25 ++++
encoding/base62/selftest/pkg.yml | 29 ++++
encoding/base62/selftest/src/encoding_test.c | 43 ++++++
.../selftest/src/testcases/base62_encoding.c | 69 +++++++++
.../base62/selftest/src/testcases/base62_errors.c | 56 ++++++++
.../selftest/src/testcases/base62_invalid_args.c | 48 +++++++
encoding/base62/src/base62.c | 155 +++++++++++++++++++++
8 files changed, 500 insertions(+)
diff --git a/encoding/base62/include/base62/base62.h b/encoding/base62/include/base62/base62.h
new file mode 100755
index 0000000..56d661b
--- /dev/null
+++ b/encoding/base62/include/base62/base62.h
@@ -0,0 +1,75 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+#ifndef __UTIL_BASE62_H
+#define __UTIL_BASE62_H
+
+#include <stdint.h>
+#include <string.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#define BASE62_DECODE_OK 0
+#define BASE62_DECODE_ERROR -1
+#define BASE62_INVALID_ARG -2
+#define BASE62_INSUFFICIENT_MEM -3
+
+/**
+ * @brief Function transforms any data to base 62 encoded text.
+ *
+ * @note null terminator is not added
+ *
+ * @param data data to encode
+ * @param input_size number of bytes to encode
+ * @param encoded_text pointer to output buffer with encoded text, must be at least
+ * of the same size as input_size
+ * @param output_size maximum output buffer length
+ * on exit this variable holds encoded text size.
+ *
+ * @return 0 when output buffer was filled
+ * BASE62_INSUFFICIENT_MEM if output buffer was too small
+ * BASE62_INVALID_ARG if one of the pointers is NULL
+ */
+int base62_encode(const void *data, unsigned int input_size,
+ char *encoded_text, unsigned int *output_size);
+
+/**
+ * @brief Decode base62 encoded text
+ *
+ * @param encoded_text base62 encoded text
+ * @param text_length length of text to decode
+ * @param output_data pointer to output buffer for decoded data
+ * @param output_size pointer to variable that holds output buffer size on input
+ * and actual decoded data length on output
+ *
+ * @return BASE62_DECODE_OK on success
+ * BASE62_INVALID_ARG when output_size is NULL
+ * BASE62_INSUFFICIENT_MEM if output size is insufficient for decoded text
+ * BASE62_DECODE_ERROR if input text is base62 malformed
+ *
+ */
+int base62_decode(const char *encoded_text, unsigned int text_length,
+ void *output_data, unsigned int *output_size);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* __UTIL_BASE62_H__ */
diff --git a/encoding/base62/pkg.yml b/encoding/base62/pkg.yml
new file mode 100755
index 0000000..3fd083f
--- /dev/null
+++ b/encoding/base62/pkg.yml
@@ -0,0 +1,25 @@
+#
+# Licensed to the Apache Software Foundation (ASF) under one
+# or more contributor license agreements. See the NOTICE file
+# distributed with this work for additional information
+# regarding copyright ownership. The ASF licenses this file
+# to you under the Apache License, Version 2.0 (the
+# "License"); you may not use this file except in compliance
+# with the License. You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing,
+# software distributed under the License is distributed on an
+# "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+# KIND, either express or implied. See the License for the
+# specific language governing permissions and limitations
+# under the License.
+#
+
+pkg.name: encoding/base62
+pkg.description: Library containing base62 encoding functions
+pkg.author: "Apache Mynewt <de...@mynewt.apache.org>"
+pkg.homepage: "http://mynewt.apache.org/"
+pkg.keywords:
+ - base62
diff --git a/encoding/base62/selftest/pkg.yml b/encoding/base62/selftest/pkg.yml
new file mode 100755
index 0000000..5502c17
--- /dev/null
+++ b/encoding/base62/selftest/pkg.yml
@@ -0,0 +1,29 @@
+# Licensed to the Apache Software Foundation (ASF) under one
+# or more contributor license agreements. See the NOTICE file
+# distributed with this work for additional information
+# regarding copyright ownership. The ASF licenses this file
+# to you under the Apache License, Version 2.0 (the
+# "License"); you may not use this file except in compliance
+# with the License. You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing,
+# software distributed under the License is distributed on an
+# "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+# KIND, either express or implied. See the License for the
+# specific language governing permissions and limitations
+# under the License.
+#
+pkg.name: encoding/base62/selftest
+pkg.type: unittest
+pkg.description: "Base62 encoding/decoding unit tests."
+pkg.author: "Apache Mynewt <de...@mynewt.apache.org>"
+pkg.homepage: "http://mynewt.apache.org/"
+pkg.keywords:
+
+pkg.deps:
+ - "encoding/base62"
+ - "@apache-mynewt-core/test/testutil"
+ - "@apache-mynewt-core/sys/console/stub"
+ - "@apache-mynewt-core/sys/log/stub"
diff --git a/encoding/base62/selftest/src/encoding_test.c b/encoding/base62/selftest/src/encoding_test.c
new file mode 100755
index 0000000..1615527
--- /dev/null
+++ b/encoding/base62/selftest/src/encoding_test.c
@@ -0,0 +1,43 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+#include <assert.h>
+#include <stddef.h>
+#include "os/mynewt.h"
+#include "testutil/testutil.h"
+
+TEST_CASE_DECL(base62_invalid_args)
+TEST_CASE_DECL(base62_encoding)
+TEST_CASE_DECL(base62_errors)
+
+TEST_SUITE(base62_test_suite)
+{
+ base62_invalid_args();
+ base62_encoding();
+ base62_errors();
+}
+
+int
+main(int argc, char **argv)
+{
+ base62_invalid_args();
+ base62_encoding();
+ base62_errors();
+
+ return tu_any_failed;
+}
diff --git a/encoding/base62/selftest/src/testcases/base62_encoding.c b/encoding/base62/selftest/src/testcases/base62_encoding.c
new file mode 100755
index 0000000..71e71a0
--- /dev/null
+++ b/encoding/base62/selftest/src/testcases/base62_encoding.c
@@ -0,0 +1,69 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+#include <string.h>
+#include "testutil/testutil.h"
+
+#include <base62/base62.h>
+
+static char plaint_text_01[] = "1";
+static char encoded_text_01[] = "n";
+
+static char plaint_text_02[] = "Quick brown fox jumps over the lazy dog";
+static char encoded_text_02[] = "1eorxj7biGe3bv0IyYT85oZ2Tivm8BrQyOhZsW9HjnJUifYBtq0Sl";
+
+TEST_CASE_SELF(base62_encoding)
+{
+ char encoded_text[100];
+ char decoded_text[100];
+
+ unsigned int input_len, output_len;
+ int rc;
+
+ input_len = strlen(plaint_text_01);
+ output_len = 100;
+ rc = base62_encode(plaint_text_01, input_len, encoded_text, &output_len);
+ TEST_ASSERT(rc == BASE62_DECODE_OK);
+ TEST_ASSERT(strlen(encoded_text_01) == output_len);
+ encoded_text[output_len] = 0;
+ TEST_ASSERT(strcmp(encoded_text, encoded_text_01) == 0);
+
+ input_len = strlen(plaint_text_01);
+ output_len = 100;
+ rc = base62_decode(encoded_text_01, input_len, decoded_text, &output_len);
+ TEST_ASSERT(rc == BASE62_DECODE_OK);
+ TEST_ASSERT(strlen(plaint_text_01) == output_len);
+ decoded_text[output_len] = 0;
+ TEST_ASSERT(strcmp(plaint_text_01, decoded_text) == 0);
+
+ input_len = strlen(plaint_text_02);
+ output_len = 100;
+ rc = base62_encode(plaint_text_02, input_len, encoded_text, &output_len);
+ TEST_ASSERT(rc == BASE62_DECODE_OK);
+ TEST_ASSERT(strlen(encoded_text_02) == output_len);
+ encoded_text[output_len] = 0;
+ TEST_ASSERT(strcmp(encoded_text, encoded_text_02) == 0);
+
+ input_len = strlen(encoded_text_02);
+ output_len = 100;
+ rc = base62_decode(encoded_text_02, input_len, decoded_text, &output_len);
+ TEST_ASSERT(rc == BASE62_DECODE_OK);
+ TEST_ASSERT(strlen(plaint_text_02) == output_len);
+ decoded_text[output_len] = 0;
+ TEST_ASSERT(strcmp(plaint_text_02, decoded_text) == 0);
+}
diff --git a/encoding/base62/selftest/src/testcases/base62_errors.c b/encoding/base62/selftest/src/testcases/base62_errors.c
new file mode 100755
index 0000000..3609d05
--- /dev/null
+++ b/encoding/base62/selftest/src/testcases/base62_errors.c
@@ -0,0 +1,56 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+#include <string.h>
+#include "testutil/testutil.h"
+
+#include <base62/base62.h>
+
+static char invalid_text_01[] = "1eorxj7biGe3bv0IyYT85oZ2Tivm'8BrQyOhZsW9HjnJUifYBtq0Sl";
+
+static char plaint_text_02[] = "Quick brown fox jumps over the lazy dog";
+static char encoded_text_02[] = "1eorxj7biGe3bv0IyYT85oZ2Tivm8BrQyOhZsW9HjnJUifYBtq0Sl";
+
+TEST_CASE_SELF(base62_errors)
+{
+ char encoded_text[100];
+ char decoded_text[100];
+
+ unsigned int input_len, output_len;
+ int rc;
+
+ /* Invalid character in encoded text */
+ input_len = strlen(invalid_text_01);
+ output_len = 100;
+ rc = base62_decode(invalid_text_01, input_len, decoded_text, &output_len);
+ TEST_ASSERT(rc == BASE62_DECODE_ERROR);
+
+ /* Insufficient space for decoded text */
+ input_len = strlen(plaint_text_02);
+ output_len = input_len;
+ rc = base62_encode(plaint_text_02, input_len, encoded_text, &output_len);
+ TEST_ASSERT(rc == BASE62_INSUFFICIENT_MEM);
+ TEST_ASSERT(strlen(encoded_text_02) == output_len);
+
+ /* Insufficient space for decoded text */
+ input_len = strlen(plaint_text_02);
+ output_len = strlen(encoded_text_02) - 1;
+ rc = base62_encode(plaint_text_02, input_len, encoded_text, &output_len);
+ TEST_ASSERT(rc == BASE62_INSUFFICIENT_MEM);
+ TEST_ASSERT(strlen(encoded_text_02) == output_len);
+}
diff --git a/encoding/base62/selftest/src/testcases/base62_invalid_args.c b/encoding/base62/selftest/src/testcases/base62_invalid_args.c
new file mode 100755
index 0000000..e4dc542
--- /dev/null
+++ b/encoding/base62/selftest/src/testcases/base62_invalid_args.c
@@ -0,0 +1,48 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+#include <string.h>
+#include "testutil/testutil.h"
+
+#include <base62/base62.h>
+
+TEST_CASE_SELF(base62_invalid_args)
+{
+ char plain_text[] = "Quick brown fox jumps over the lazy dog";
+ char encoded_text[100];
+
+ unsigned int input_len, output_len;
+ int rc;
+
+ input_len = strlen(plain_text);
+ output_len = 100;
+ rc = base62_encode(plain_text, input_len, NULL, &output_len);
+ TEST_ASSERT(rc == BASE62_INVALID_ARG);
+
+ output_len = 100;
+ rc = base62_encode(NULL, input_len, encoded_text, &output_len);
+ TEST_ASSERT(rc == BASE62_INVALID_ARG);
+
+ output_len = 100;
+ rc = base62_encode(plain_text, input_len, encoded_text, NULL);
+ TEST_ASSERT(rc == BASE62_INVALID_ARG);
+
+ output_len = input_len - 1;
+ rc = base62_encode(plain_text, input_len, encoded_text, &output_len);
+ TEST_ASSERT(rc == BASE62_INVALID_ARG);
+}
diff --git a/encoding/base62/src/base62.c b/encoding/base62/src/base62.c
new file mode 100755
index 0000000..503d090
--- /dev/null
+++ b/encoding/base62/src/base62.c
@@ -0,0 +1,155 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+#include <stdint.h>
+#include <ctype.h>
+#include <base62/base62.h>
+
+/**
+ * Function that returns symbol character from it's ordinal value.
+ */
+typedef uint8_t encode_symbol_t(unsigned int ordinal);
+
+/**
+ * Function to convert symbol from encoded text to it's ordinal number.
+ */
+typedef int decode_symbol_t(uint8_t digit_symbol);
+
+static int
+base_n_normalize(const uint8_t *data, size_t size, decode_symbol_t *decoder,
+ uint8_t *normalized)
+{
+ size_t i;
+ int symbol_ordinal_number;
+
+ for (i = 0; i < size; ++i) {
+ symbol_ordinal_number = decoder(data[i]);
+ if (symbol_ordinal_number < 0) {
+ return -1;
+ }
+ normalized[i] = symbol_ordinal_number;
+ }
+ return 0;
+}
+
+static int
+base_n_encode(const uint8_t *data, unsigned int data_size,
+ unsigned int src_base, decode_symbol_t *symbol_decoder,
+ unsigned int dst_base, encode_symbol_t *symbol_encoder,
+ uint8_t *encoded, unsigned int *encoded_size)
+{
+ size_t i;
+ const uint8_t *dividend;
+ uint8_t *quotient;
+ size_t dividend_size;
+ size_t reminder;
+ size_t accumulator;
+ uint8_t *limit;
+ uint8_t *result;
+ size_t extra_bytes_needed = 0;
+
+ if (encoded_size == NULL || data == NULL || encoded == NULL || *encoded_size < data_size) {
+ return BASE62_INVALID_ARG;
+ }
+
+ if (base_n_normalize(data, data_size, symbol_decoder, encoded)) {
+ return BASE62_DECODE_ERROR;
+ }
+
+ limit = encoded + *encoded_size;
+ result = limit;
+ dividend_size = data_size;
+
+ while (dividend_size) {
+ reminder = 0;
+ dividend = encoded;
+ quotient = encoded;
+ for (i = 0; i < dividend_size; ++i) {
+ accumulator = *dividend++ + (reminder * src_base);
+ reminder = accumulator % dst_base;
+ *quotient = (uint8_t)(accumulator / dst_base);
+ if (*quotient || quotient != encoded) {
+ quotient++;
+ }
+ }
+ if (result > quotient) {
+ *--result = symbol_encoder(reminder);
+ } else {
+ extra_bytes_needed++;
+ }
+ dividend_size = quotient - encoded;
+ }
+ *encoded_size = limit - result + extra_bytes_needed;
+
+ if (0 == extra_bytes_needed) {
+ memmove(encoded, result, *encoded_size);
+ }
+
+ return extra_bytes_needed ? BASE62_INSUFFICIENT_MEM : BASE62_DECODE_OK;
+}
+
+static uint8_t
+encode_62(unsigned int ordinal)
+{
+ static const char base62_chars[62] =
+ "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
+
+ return base62_chars[ordinal];
+}
+
+static int
+decode_256(uint8_t digit_symbol)
+{
+ return digit_symbol;
+}
+
+static int
+decode_62(uint8_t digit_symbol)
+{
+ if (isupper(digit_symbol)) {
+ return digit_symbol - 'A' + 10;
+ } else if (islower(digit_symbol)) {
+ return digit_symbol - 'a' + 36;
+ } else if (isdigit(digit_symbol)) {
+ return digit_symbol - '0';
+ }
+ return -1;
+}
+
+static uint8_t
+encode_256(unsigned int ordinal)
+{
+ return (uint8_t)ordinal;
+}
+
+int
+base62_encode(const void *data, unsigned int input_size,
+ char *encoded_text, unsigned int *output_size)
+{
+ return base_n_encode(data, input_size, 256, decode_256,
+ 62, encode_62, (uint8_t *)encoded_text, output_size);
+}
+
+int
+base62_decode(const char *encoded_text, unsigned int length,
+ void *output_data, unsigned int *output_size)
+{
+ return base_n_encode((const uint8_t *)encoded_text, length, 62, decode_62,
+ 256, encode_256, output_data, output_size);
+}