/** @file ascii85.c
*
* @brief Ascii85 encoder and decoder
*
* @par
* @copyright Copyright © 2017 Doug Currie, Londonderry, NH, USA. All rights reserved.
*
* @par
* Permission is hereby granted, free of charge, to any person obtaining a copy of this software
* and associated documentation files (the "Software"), to deal in the Software without
* restriction, including without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the
* Software is furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included in all copies or
* substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING
* BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
* DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
**/
/* from: https://github.com/dcurrie/ascii85 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <stdbool.h>
enum ascii85_errs_e
{
ascii85_err_out_buf_too_small = -255,
ascii85_err_in_buf_too_large,
ascii85_err_bad_decode_char,
ascii85_err_decode_overflow
};
int32_t encode_ascii85 (const uint8_t *inp, int32_t in_length, char *outp, int32_t out_max_length);
int32_t decode_ascii85 (const char *inp, int32_t in_length, uint8_t *outp, int32_t out_max_length);
// From Wikipedia re: Ascii85 length...
// Adobe adopted the basic btoa encoding, but with slight changes, and gave it the name Ascii85.
// The characters used are the ASCII characters 33 (!) through 117 (u) inclusive (to represent
// the base-85 digits 0 through 84), together with the letter z (as a special case to represent
// a 32-bit 0 value), and white space is ignored. Adobe uses the delimiter "~>" to mark the end
// of an Ascii85-encoded string, and represents the length by truncating the final group: If the
// last block of source bytes contains fewer than 4 bytes, the block is padded with up to three
// null bytes before encoding. After encoding, as many bytes as were added as padding are
// removed from the end of the output.
// The reverse is applied when decoding: The last block is padded to 5 bytes with the Ascii85
// character "u", and as many bytes as were added as padding are omitted from the end of the
// output (see example).
// NOTE: The padding is not arbitrary. Converting from binary to base 64 only regroups bits and
// does not change them or their order (a high bit in binary does not affect the low bits in the
// base64 representation). In converting a binary number to base85 (85 is not a power of two)
// high bits do affect the low order base85 digits and conversely. Padding the binary low (with
// zero bits) while encoding and padding the base85 value high (with 'u's) in decoding assures
// that the high order bits are preserved (the zero padding in the binary gives enough room so
// that a small addition is trapped and there is no "carry" to the high bits).
// NOTE: ths implementation does not ignore white space!
//
// The motivation for this implementation is as a binary message wrapper for serial
// communication; in that application, white space is used for message framing.
static const uint8_t base_char = 33u; // '!' -- note that (85 + 33) < 128
static const int32_t ascii85_in_length_max = 65536;
static const bool ascii85_check_decode_chars = true;
#define ENDECODE_NUL_AS_Z 1
#if 0
static inline bool ascii85_char_ok (uint8_t c)
{
return ((c >= 33u) && (c <= 117u));
}
#endif
static inline bool ascii85_char_ng (uint8_t c)
{
return ((c < 33u) || (c > 117u));
}
/*!
* @brief encode_ascii85: encode binary input into Ascii85
* @param[in] inp pointer to a buffer of unsigned bytes
* @param[in] in_length the number of bytes at inp to encode
* @param[in] outp pointer to a buffer for the encoded data as c-string
* @param[in] out_max_length available space at outp in bytes; must be >= 5 * ceiling(in_length/4)
* @return number of bytes in the encoded value at outp if non-negative; error code from
* ascii85_errs_e if negative
* @par Possible errors include: ascii85_err_in_buf_too_large, ascii85_err_out_buf_too_small
*/
int32_t encode_ascii85 (const uint8_t *inp, int32_t in_length, char *outp, int32_t out_max_length)
{
// Note that (in_length + 3) below may overflow, but this is inconsequental
// since ascii85_in_length_max is < (INT32_MAX - 3), and we check in_length before
// using the calculated out_length.
//
int32_t out_length = (((in_length + 3) / 4) * 5); // ceiling
if (in_length > ascii85_in_length_max)
{
out_length = (int32_t )ascii85_err_in_buf_too_large;
}
else if (out_length > out_max_length)
{
out_length = (int32_t )ascii85_err_out_buf_too_small;
}
else
{
int32_t in_rover = 0;
out_length = 0; // we know we can increment by 5 * ceiling(in_length/4)
while (in_rover < in_length)
{
uint32_t chunk;
int32_t chunk_len = in_length - in_rover;
if (chunk_len >= 4)
{
chunk = (((uint32_t )inp[in_rover++]) << 24u);
chunk |= (((uint32_t )inp[in_rover++]) << 16u);
chunk |= (((uint32_t )inp[in_rover++]) << 8u);
chunk |= (((uint32_t )inp[in_rover++]) );
}
else
{
chunk = (((uint32_t )inp[in_rover++]) << 24u);
chunk |= ((in_rover < in_length) ? (((uint32_t )inp[in_rover++]) << 16u) : 0u);
chunk |= ((in_rover < in_length) ? (((uint32_t )inp[in_rover++]) << 8u) : 0u);
chunk |= ((in_rover < in_length) ? (((uint32_t )inp[in_rover++]) ) : 0u);
}
#ifdef ENDECODE_NUL_AS_Z
if (/*lint -e{506} -e{774}*/ (0u == chunk) && (chunk_len >= 4))
{
outp[out_length++] = (uint8_t )'z';
}
else
#endif
{
outp[out_length + 4] = (chunk % 85u) + base_char;
chunk /= 85u;
outp[out_length + 3] = (chunk % 85u) + base_char;
chunk /= 85u;
outp[out_length + 2] = (chunk % 85u) + base_char;
chunk /= 85u;
outp[out_length + 1] = (chunk % 85u) + base_char;
chunk /= 85u;
outp[out_length ] = (uint8_t )chunk + base_char;
// we don't need (chunk % 85u) on the last line since (((((2^32 - 1) / 85) / 85) / 85) / 85) = 82.278
if (chunk_len >= 4)
{
out_length += 5;
}
else
{
out_length += (chunk_len + 1); // see note above re: Ascii85 length
}
}
}
}
return out_length;
}
/*!
* @brief decode_ascii85: decode Ascii85 input to binary output
* @param[in] inp pointer to a buffer of Ascii85 encoded c-string
* @param[in] in_length the number of bytes at inp to decode
* @param[in] outp pointer to a buffer for the decoded data
* @param[in] out_max_length available space at outp in bytes; must be >= 4 * ceiling(in_length/5)
* @return number of bytes in the decoded value at outp if non-negative; error code from
* ascii85_errs_e if negative
* @par Possible errors include: ascii85_err_in_buf_too_large, ascii85_err_out_buf_too_small,
* ascii85_err_bad_decode_char, ascii85_err_decode_overflow
*/
int32_t decode_ascii85 (const char *inp, int32_t in_length, uint8_t *outp, int32_t out_max_length)
{
// Note that (in_length + 4) below may overflow, but this is inconsequental
// since ascii85_in_length_max is < (INT32_MAX - 4), and we check in_length before
// using the calculated out_length.
//
int32_t out_length = (((in_length + 4) / 5) * 4); // ceiling
if (in_length > ascii85_in_length_max)
{
out_length = (int32_t )ascii85_err_in_buf_too_large;
}
else if (out_length > out_max_length)
{
out_length = (int32_t )ascii85_err_out_buf_too_small;
}
else
{
int32_t in_rover = 0;
out_length = 0; // we know we can increment by 4 * ceiling(in_length/5)
while (in_rover < in_length)
{
uint32_t chunk;
int32_t chunk_len = in_length - in_rover;
#ifdef ENDECODE_NUL_AS_Z
if (/*lint -e{506} -e{774}*/ ((uint8_t )'z' == inp[in_rover]))
{
in_rover += 1;
chunk = 0u;
chunk_len = 5; // to make out_length increment correct
}
else
#endif
if (/*lint -e{506} -e{774}*/ascii85_check_decode_chars
&& ( ascii85_char_ng(inp[in_rover ])
|| ((chunk_len > 1) && ascii85_char_ng(inp[in_rover + 1]))
|| ((chunk_len > 2) && ascii85_char_ng(inp[in_rover + 2]))
|| ((chunk_len > 3) && ascii85_char_ng(inp[in_rover + 3]))
|| ((chunk_len > 4) && ascii85_char_ng(inp[in_rover + 4]))))
{
out_length = (int32_t )ascii85_err_bad_decode_char;
break; // leave while loop early to report error
}
else if (chunk_len >= 5)
{
chunk = inp[in_rover++] - base_char;
chunk *= 85u; // max: 84 * 85 = 7,140
chunk += inp[in_rover++] - base_char;
chunk *= 85u; // max: (84 * 85 + 84) * 85 = 614,040
chunk += inp[in_rover++] - base_char;
chunk *= 85u; // max: (((84 * 85 + 84) * 85) + 84) * 85 = 52,200,540
chunk += inp[in_rover++] - base_char;
// max: (((((84 * 85 + 84) * 85) + 84) * 85) + 84) * 85 = 4,437,053,040 oops! 0x108780E70
if (chunk > (UINT32_MAX / 85u))
{
// multiply would overflow
out_length = (int32_t )ascii85_err_decode_overflow; // bad input
break; // leave while loop early to report error
}
else
{
uint8_t addend = inp[in_rover++] - base_char;
chunk *= 85u; // multiply will not overflow due to test above
if (chunk > (UINT32_MAX - addend))
{
/// add would overflow
out_length = (int32_t )ascii85_err_decode_overflow; // bad input
break; // leave while loop early to report error
}
else
{
chunk += addend;
}
}
}
else
{
chunk = inp[in_rover++] - base_char;
chunk *= 85u; // max: 84 * 85 = 7,140
chunk += ((in_rover < in_length) ? (inp[in_rover++] - base_char) : 84u);
chunk *= 85u; // max: (84 * 85 + 84) * 85 = 614,040
chunk += ((in_rover < in_length) ? (inp[in_rover++] - base_char) : 84u);
chunk *= 85u; // max: (((84 * 85 + 84) * 85) + 84) * 85 = 52,200,540
chunk += ((in_rover < in_length) ? (inp[in_rover++] - base_char) : 84u);
// max: (((((84 * 85 + 84) * 85) + 84) * 85) + 84) * 85 = 4,437,053,040 oops! 0x108780E70
if (chunk > (UINT32_MAX / 85u))
{
// multiply would overflow
out_length = (int32_t )ascii85_err_decode_overflow; // bad input
break; // leave while loop early to report error
}
else
{
uint8_t addend = (uint8_t )((in_rover < in_length) ? (inp[in_rover++] - base_char) : 84u);
chunk *= 85u; // multiply will not overflow due to test above
if (chunk > (UINT32_MAX - addend))
{
/// add would overflow
out_length = (int32_t )ascii85_err_decode_overflow; // bad input
break; // leave while loop early to report error
}
else
{
chunk += addend;
}
}
}
outp[out_length + 3] = (chunk % 256u);
chunk /= 256u;
outp[out_length + 2] = (chunk % 256u);
chunk /= 256u;
outp[out_length + 1] = (chunk % 256u);
chunk /= 256u;
outp[out_length ] = (uint8_t )chunk;
// we don't need (chunk % 256u) on the last line since ((((2^32 - 1) / 256u) / 256u) / 256u) = 255
if (chunk_len >= 5)
{
out_length += 4;
}
else
{
out_length += (chunk_len - 1); // see note above re: Ascii85 length
}
}
}
return out_length;
}
int main(int argc, char **argv) {
char out_enc[BUFSIZ];
uint8_t out_dec[BUFSIZ];
size_t buflen;
int32_t siz_enc, siz_dec;
#if ENDECODE_NUL_AS_Z
printf("Encoding NUL characters won't work from cmdline!\n");
#endif
if (argc != 2) {
printf("usage: %s [BINARY-DATA]\n", (argc > 0 ? argv[0] : "null"));
exit(1);
}
memset(out_enc, 0, sizeof out_enc);
memset(out_dec, 0, sizeof out_dec);
buflen = strlen(argv[1]);
siz_enc = encode_ascii85((uint8_t *) argv[1], buflen, out_enc, sizeof out_enc - 1);
printf("Encoded: \"%.*s\"\n", siz_enc, (char *) out_enc);
siz_dec = decode_ascii85(out_enc, siz_enc, out_dec, sizeof out_dec - 1);
printf("Decoded: \"%.*s\"\n", siz_dec, (char *) out_dec);
if ((int32_t) buflen == siz_dec &&
memcmp(out_dec, argv[1], buflen) == 0)
{
printf("%s: Ok!\n", argv[0]);
} else printf("%s: FAIL!\n", argv[0]);
return 0;
}