-
Notifications
You must be signed in to change notification settings - Fork 4
/
ascii85.c
353 lines (316 loc) · 14.1 KB
/
ascii85.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
/** @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.
**/
#include "ascii85.h"
#include <stdint.h>
#include <stdbool.h>
// 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_decode_z_for_zero = true;
static const bool ascii85_encode_z_for_zero = true;
static const bool ascii85_check_decode_chars = true;
#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
* @param[in] out_max_length available space at outp in bytes; must be >=
* ascii85_get_max_encoded_length(in_length)
* @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, uint8_t *outp, int32_t out_max_length)
{
int32_t out_length = ascii85_get_max_encoded_length(in_length);
if (out_length < 0)
{
// ascii85_get_max_encoded_length() already returned an error, so return that
}
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);
}
if (/*lint -e{506} -e{774}*/ascii85_encode_z_for_zero && (0u == chunk) && (chunk_len >= 4))
{
outp[out_length++] = (uint8_t )'z';
}
else
{
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 unsigned bytes
* @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 >=
* ascii85_get_max_decoded_length(in_length)
* @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 uint8_t *inp, int32_t in_length, uint8_t *outp, int32_t out_max_length)
{
int32_t out_length = ascii85_get_max_decoded_length(in_length);
if (out_length < 0)
{
// get_max_decoded_length() already returned an error, so return that
}
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;
if (/*lint -e{506} -e{774}*/ascii85_decode_z_for_zero && ((uint8_t )'z' == inp[in_rover]))
{
in_rover += 1;
chunk = 0u;
chunk_len = 5; // to make out_length increment correct
}
else 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;
}
/*!
* @brief ascii85_get_max_encoded_length: get the maximum length a block of data will encode to
* @param[in] in_length the number of data bytes to encode
* @return maximum number of bytes the encoded buffer could be if non-negative; error code from
* ascii85_errs_e if negative
* @par Possible errors include: ascii85_err_in_buf_too_large
*/
int32_t ascii85_get_max_encoded_length (int32_t in_length)
{
int32_t out_length;
if ((in_length < 0) || (in_length > ascii85_in_length_max))
{
out_length = (int32_t )ascii85_err_in_buf_too_large;
}
else
{
// (in_length + 3) will not overflow since ascii85_in_length_max
// is < (INT32_MAX - 3), and similar reasoning for the final * 5
out_length = ((in_length + 3) / 4) * 5; // ceiling
}
return out_length;
}
/*!
* @brief ascii85_get_max_encoded_length: get the maximum length a block of data will decode to
* @param[in] in_length the number of encoded bytes to decode
* @return maximum number of bytes the decoded buffer could be if non-negative; error code from
* ascii85_errs_e if negative
* @par Possible errors include: ascii85_err_in_buf_too_large
*/
int32_t ascii85_get_max_decoded_length (int32_t in_length)
{
int32_t out_length;
if ((in_length < 0) || (in_length > ascii85_in_length_max))
{
out_length = (int32_t )ascii85_err_in_buf_too_large;
}
else if (/*lint -e{506} -e{774}*/ascii85_decode_z_for_zero)
{
out_length = in_length * 4;
}
else
{
// (in_length + 4) will not overflow since ascii85_in_length_max
// is < (INT32_MAX - 4)
out_length = ((in_length + 4) / 5) * 4; // ceiling
}
return out_length;
}