Revert stop_character_mask to a complement.
[cppcodec.git] / cppcodec / detail / stream_codec.hpp
1 /**
2  *  Copyright (C) 2015 Topology LP
3  *  Copyright (C) 2018 Jakob Petsovits
4  *  All rights reserved.
5  *
6  *  Permission is hereby granted, free of charge, to any person obtaining a copy
7  *  of this software and associated documentation files (the "Software"), to
8  *  deal in the Software without restriction, including without limitation the
9  *  rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
10  *  sell copies of the Software, and to permit persons to whom the Software is
11  *  furnished to do so, subject to the following conditions:
12  *
13  *  The above copyright notice and this permission notice shall be included in
14  *  all copies or substantial portions of the Software.
15  *
16  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17  *  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18  *  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
19  *  THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20  *  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21  *  FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
22  *  IN THE SOFTWARE.
23  */
24
25 #ifndef CPPCODEC_DETAIL_STREAM_CODEC
26 #define CPPCODEC_DETAIL_STREAM_CODEC
27
28 #include <limits>
29 #include <stdlib.h> // for abort()
30 #include <stdint.h>
31
32 #include "../parse_error.hpp"
33 #include "config.hpp"
34
35 namespace cppcodec {
36 namespace detail {
37
38 using alphabet_index_t = uint_fast16_t;
39
40 template <typename Codec, typename CodecVariant>
41 class stream_codec
42 {
43 public:
44     template <typename Result, typename ResultState> static void encode(
45             Result& encoded_result, ResultState&, const uint8_t* binary, size_t binary_size);
46
47     template <typename Result, typename ResultState> static void decode(
48             Result& binary_result, ResultState&, const char* encoded, size_t encoded_size);
49
50     static constexpr size_t encoded_size(size_t binary_size) noexcept;
51     static constexpr size_t decoded_max_size(size_t encoded_size) noexcept;
52 };
53
54 template <bool GeneratesPadding> // default for CodecVariant::generates_padding() == false
55 struct padder {
56     template <typename CodecVariant, typename Result, typename ResultState, typename EncodedBlockSizeT>
57     CPPCODEC_ALWAYS_INLINE void operator()(Result&, ResultState&, EncodedBlockSizeT) { }
58 };
59
60 template<> // specialization for CodecVariant::generates_padding() == true
61 struct padder<true> {
62     template <typename CodecVariant, typename Result, typename ResultState, typename EncodedBlockSizeT>
63     CPPCODEC_ALWAYS_INLINE void operator()(
64             Result& encoded, ResultState& state, EncodedBlockSizeT num_padding_characters)
65     {
66         for (EncodedBlockSizeT i = 0; i < num_padding_characters; ++i) {
67             data::put(encoded, state, CodecVariant::padding_symbol());
68         }
69     }
70 };
71
72 template <size_t I>
73 struct enc {
74     // Block encoding: Go from 0 to (block size - 1), append a symbol for each iteration unconditionally.
75     template <typename Codec, typename CodecVariant, typename Result, typename ResultState>
76     static CPPCODEC_ALWAYS_INLINE void block(Result& encoded, ResultState& state, const uint8_t* src)
77     {
78         using EncodedBlockSizeT = decltype(Codec::encoded_block_size());
79         constexpr static const EncodedBlockSizeT SymbolIndex = static_cast<EncodedBlockSizeT>(I - 1);
80
81         enc<I - 1>().template block<Codec, CodecVariant>(encoded, state, src);
82         data::put(encoded, state, CodecVariant::symbol(Codec::template index<SymbolIndex>(src)));
83     }
84
85     // Tail encoding: Go from 0 until (runtime) num_symbols, append a symbol for each iteration.
86     template <typename Codec, typename CodecVariant, typename Result, typename ResultState,
87             typename EncodedBlockSizeT = decltype(Codec::encoded_block_size())>
88     static CPPCODEC_ALWAYS_INLINE void tail(
89             Result& encoded, ResultState& state, const uint8_t* src, EncodedBlockSizeT num_symbols)
90     {
91         constexpr static const EncodedBlockSizeT SymbolIndex = Codec::encoded_block_size() - I;
92         constexpr static const EncodedBlockSizeT NumSymbols = SymbolIndex + static_cast<EncodedBlockSizeT>(1);
93
94         if (num_symbols == NumSymbols) {
95             data::put(encoded, state, CodecVariant::symbol(Codec::template index_last<SymbolIndex>(src)));
96             padder<CodecVariant::generates_padding()> pad;
97 #ifdef _MSC_VER
98             pad.operator()<CodecVariant>(encoded, state, Codec::encoded_block_size() - NumSymbols);
99 #else
100             pad.template operator()<CodecVariant>(encoded, state, Codec::encoded_block_size() - NumSymbols);
101 #endif
102             return;
103         }
104         data::put(encoded, state, CodecVariant::symbol(Codec::template index<SymbolIndex>(src)));
105         enc<I - 1>().template tail<Codec, CodecVariant>(encoded, state, src, num_symbols);
106     }
107 };
108
109 template<> // terminating specialization
110 struct enc<0> {
111     template <typename Codec, typename CodecVariant, typename Result, typename ResultState>
112     static CPPCODEC_ALWAYS_INLINE void block(Result&, ResultState&, const uint8_t*) { }
113
114     template <typename Codec, typename CodecVariant, typename Result, typename ResultState,
115             typename EncodedBlockSizeT = decltype(Codec::encoded_block_size())>
116     static CPPCODEC_ALWAYS_INLINE void tail(Result&, ResultState&, const uint8_t*, EncodedBlockSizeT)
117     {
118         abort(); // Not reached: block() should be called if num_symbols == block size, not tail().
119     }
120 };
121
122 template <typename Codec, typename CodecVariant>
123 template <typename Result, typename ResultState>
124 inline void stream_codec<Codec, CodecVariant>::encode(
125         Result& encoded_result, ResultState& state,
126         const uint8_t* src, size_t src_size)
127 {
128     using encoder = enc<Codec::encoded_block_size()>;
129
130     const uint8_t* src_end = src + src_size;
131
132     if (src_size >= Codec::binary_block_size()) {
133         src_end -= Codec::binary_block_size();
134
135         for (; src <= src_end; src += Codec::binary_block_size()) {
136             encoder::template block<Codec, CodecVariant>(encoded_result, state, src);
137         }
138         src_end += Codec::binary_block_size();
139     }
140
141     if (src_end > src) {
142         auto remaining_src_len = src_end - src;
143         if (!remaining_src_len || remaining_src_len >= Codec::binary_block_size()) {
144             abort();
145             return;
146         }
147         auto num_symbols = Codec::num_encoded_tail_symbols(static_cast<uint8_t>(remaining_src_len));
148         encoder::template tail<Codec, CodecVariant>(encoded_result, state, src, num_symbols);
149     }
150 }
151
152 // Range & lookup table generation, see
153 // http://stackoverflow.com/questions/13313980/populate-an-array-using-constexpr-at-compile-time
154 // and http://cplusadd.blogspot.ca/2013/02/c11-compile-time-lookup-tablearray-with.html
155
156 template<unsigned... Is> struct seq {};
157
158 template<unsigned N, unsigned... Is>
159 struct gen_seq : gen_seq<N - 4, N - 4, N - 3, N - 2, N - 1, Is...> {
160     // Clang up to 3.6 has a limit of 256 for template recursion,
161     // so pass a few more symbols at once to make it work.
162     static_assert(N % 4 == 0, "I must be divisible by 4 to eventually end at 0");
163 };
164 template<unsigned... Is>
165 struct gen_seq<0, Is...> : seq<Is...> {};
166
167 template <size_t N>
168 struct lookup_table_t {
169     alphabet_index_t lookup[N];
170     static constexpr size_t size = N;
171 };
172
173 template<typename LambdaType, unsigned... Is>
174 constexpr lookup_table_t<sizeof...(Is)> make_lookup_table(seq<Is...>, LambdaType value_for_index) {
175     return { { value_for_index(Is)... } };
176 }
177
178 template<unsigned N, typename LambdaType>
179 constexpr lookup_table_t<N> make_lookup_table(LambdaType evalFunc) {
180     return make_lookup_table(gen_seq<N>(), evalFunc);
181 }
182
183 // CodecVariant::symbol() provides a symbol for an index.
184 // Use recursive templates to get the inverse lookup table for fast decoding.
185
186 template <typename T>
187 static CPPCODEC_ALWAYS_INLINE constexpr size_t num_possible_values()
188 {
189     return static_cast<size_t>(
190             static_cast<intmax_t>(std::numeric_limits<T>::max())
191                     - static_cast<intmax_t>(std::numeric_limits<T>::min()) + 1);
192 }
193
194 template <typename CodecVariant, alphabet_index_t InvalidIdx, size_t I>
195 struct index_if_in_alphabet {
196     static CPPCODEC_ALWAYS_INLINE constexpr alphabet_index_t for_symbol(char symbol)
197     {
198         return (CodecVariant::symbol(
199                     static_cast<alphabet_index_t>(CodecVariant::alphabet_size() - I)) == symbol)
200             ? static_cast<alphabet_index_t>(CodecVariant::alphabet_size() - I)
201             : index_if_in_alphabet<CodecVariant, InvalidIdx, I - 1>::for_symbol(symbol);
202     }
203 };
204 template <typename CodecVariant, alphabet_index_t InvalidIdx>
205 struct index_if_in_alphabet<CodecVariant, InvalidIdx, 0> { // terminating specialization
206     static CPPCODEC_ALWAYS_INLINE constexpr alphabet_index_t for_symbol(char)
207     {
208         return InvalidIdx;
209     }
210 };
211
212 template <typename CodecVariant, size_t I>
213 struct padding_searcher {
214     static CPPCODEC_ALWAYS_INLINE constexpr bool exists_padding_symbol()
215     {
216         // Clang up to 3.6 has a limit of 256 for template recursion,
217         // so pass a few more symbols at once to make it work.
218         static_assert(I % 4 == 0, "I must be divisible by 4 to eventually end at 0");
219
220         return CodecVariant::is_padding_symbol(
221                         static_cast<char>(num_possible_values<char>() - I - 4))
222                 || CodecVariant::is_padding_symbol(
223                         static_cast<char>(num_possible_values<char>() - I - 3))
224                 || CodecVariant::is_padding_symbol(
225                         static_cast<char>(num_possible_values<char>() - I - 2))
226                 || CodecVariant::is_padding_symbol(
227                         static_cast<char>(num_possible_values<char>() - I - 1))
228                 || padding_searcher<CodecVariant, I - 4>::exists_padding_symbol();
229     }
230 };
231 template <typename CodecVariant>
232 struct padding_searcher<CodecVariant, 0> { // terminating specialization
233     static CPPCODEC_ALWAYS_INLINE constexpr bool exists_padding_symbol() { return false; }
234 };
235
236 template <typename CodecVariant>
237 struct alphabet_index_info
238 {
239     static constexpr const size_t num_possible_symbols = num_possible_values<char>();
240
241     static constexpr const alphabet_index_t padding_idx = 1 << 8;
242     static constexpr const alphabet_index_t invalid_idx = 1 << 9;
243     static constexpr const alphabet_index_t eof_idx = 1 << 10;
244     static constexpr const alphabet_index_t stop_character_mask{~0xFFu};
245
246     static constexpr const bool padding_allowed = padding_searcher<
247             CodecVariant, num_possible_symbols>::exists_padding_symbol();
248
249     static CPPCODEC_ALWAYS_INLINE constexpr bool allows_padding()
250     {
251         return padding_allowed;
252     }
253     static CPPCODEC_ALWAYS_INLINE constexpr bool is_padding(alphabet_index_t idx)
254     {
255         return allows_padding() ? (idx == padding_idx) : false;
256     }
257     static CPPCODEC_ALWAYS_INLINE constexpr bool is_invalid(alphabet_index_t idx) { return idx == invalid_idx; }
258     static CPPCODEC_ALWAYS_INLINE constexpr bool is_eof(alphabet_index_t idx) { return idx == eof_idx; }
259     static CPPCODEC_ALWAYS_INLINE constexpr bool is_stop_character(alphabet_index_t idx)
260     {
261         return (idx & stop_character_mask) != 0;
262     }
263
264 private:
265     static CPPCODEC_ALWAYS_INLINE constexpr
266     alphabet_index_t valid_index_or(alphabet_index_t a, alphabet_index_t b)
267     {
268         return a == invalid_idx ? b : a;
269     }
270
271     using idx_if_in_alphabet = index_if_in_alphabet<
272             CodecVariant, invalid_idx, CodecVariant::alphabet_size()>;
273
274     static CPPCODEC_ALWAYS_INLINE constexpr alphabet_index_t index_of(char symbol)
275     {
276         return valid_index_or(idx_if_in_alphabet::for_symbol(symbol),
277             CodecVariant::is_eof_symbol(symbol) ? eof_idx
278             : CodecVariant::is_padding_symbol(symbol) ? padding_idx
279             : invalid_idx);
280     }
281
282     // GCC <= 4.9 has a bug with retaining constexpr when passing a function pointer.
283     // To get around this, we'll create a callable with operator() and pass that one.
284     // Unfortunately, MSVC prior to VS 2017 (for MinSizeRel or Release builds)
285     // chokes on this by compiling the project in 20 minutes instead of seconds.
286     // So let's define two separate variants and remove the old GCC one whenever we
287     // decide not to support GCC < 5.0 anymore.
288 #if defined(__GNUC__) && !defined(__clang__) && __GNUC__ < 5
289     struct index_at {
290         CPPCODEC_ALWAYS_INLINE constexpr alphabet_index_t operator()(size_t symbol) const {
291             return index_of(CodecVariant::normalized_symbol(static_cast<char>(symbol)));
292         }
293     };
294 #else
295     static CPPCODEC_ALWAYS_INLINE constexpr alphabet_index_t index_at(size_t symbol)
296     {
297         return index_of(CodecVariant::normalized_symbol(static_cast<char>(symbol)));
298     }
299 #endif
300
301 public:
302     struct lookup {
303         static CPPCODEC_ALWAYS_INLINE alphabet_index_t for_symbol(char symbol)
304         {
305 #if defined(__GNUC__) && !defined(__clang__) && __GNUC__ < 5
306             static constexpr const auto t = make_lookup_table<num_possible_symbols>(index_at());
307 #else
308             static constexpr const auto t = make_lookup_table<num_possible_symbols>(&index_at);
309 #endif
310             static_assert(t.size == num_possible_symbols,
311                     "lookup table must cover each possible (character) symbol");
312             return t.lookup[static_cast<uint8_t>(symbol)];
313         }
314     };
315 };
316
317 //
318 // At long last! The actual decode/encode functions.
319
320 template <typename Codec, typename CodecVariant>
321 template <typename Result, typename ResultState>
322 inline void stream_codec<Codec, CodecVariant>::decode(
323         Result& binary_result, ResultState& state,
324         const char* src_encoded, size_t src_size)
325 {
326     using alphabet_index_lookup = typename alphabet_index_info<CodecVariant>::lookup;
327     const char* src = src_encoded;
328     const char* src_end = src + src_size;
329
330     alphabet_index_t alphabet_indexes[Codec::encoded_block_size()] = {};
331     alphabet_indexes[0] = alphabet_index_info<CodecVariant>::eof_idx;
332
333     alphabet_index_t* const alphabet_index_start = &alphabet_indexes[0];
334     alphabet_index_t* const alphabet_index_end = &alphabet_indexes[Codec::encoded_block_size()];
335     alphabet_index_t* alphabet_index_ptr = &alphabet_indexes[0];
336
337     while (src < src_end) {
338         if (CodecVariant::should_ignore(*src)) {
339             ++src;
340             continue;
341         }
342         *alphabet_index_ptr = alphabet_index_lookup::for_symbol(*src);
343         if (alphabet_index_info<CodecVariant>::is_stop_character(*alphabet_index_ptr)) {
344             break;
345         }
346         ++src;
347         ++alphabet_index_ptr;
348
349         if (alphabet_index_ptr == alphabet_index_end) {
350             Codec::decode_block(binary_result, state, alphabet_indexes);
351             alphabet_index_ptr = alphabet_index_start;
352         }
353     }
354
355     if (alphabet_index_info<CodecVariant>::is_invalid(*alphabet_index_ptr)) {
356         throw symbol_error(*src);
357     }
358     ++src;
359
360     alphabet_index_t* last_index_ptr = alphabet_index_ptr;
361     if (alphabet_index_info<CodecVariant>::is_padding(*last_index_ptr)) {
362         if (last_index_ptr == alphabet_index_start) {
363             // Don't accept padding at the start of a block.
364             // The encoder should have omitted that padding altogether.
365             throw padding_error();
366         }
367         // We're in here because we just read a (first) padding character. Try to read more.
368         // Count with last_index_ptr, but store in alphabet_index_ptr so we don't
369         // overflow the array in case the input data is too long.
370         ++last_index_ptr;
371         while (src < src_end) {
372             *alphabet_index_ptr = alphabet_index_lookup::for_symbol(*(src++));
373
374             if (alphabet_index_info<CodecVariant>::is_eof(*alphabet_index_ptr)) {
375                 *alphabet_index_ptr = alphabet_index_info<CodecVariant>::padding_idx;
376                 break;
377             }
378             if (!alphabet_index_info<CodecVariant>::is_padding(*alphabet_index_ptr)) {
379                 throw padding_error();
380             }
381
382             ++last_index_ptr;
383             if (last_index_ptr > alphabet_index_end) {
384                 throw padding_error();
385             }
386         }
387     }
388
389     if (last_index_ptr != alphabet_index_start)  {
390         if ((CodecVariant::requires_padding()
391                     || alphabet_index_info<CodecVariant>::is_padding(*alphabet_index_ptr)
392                     ) && last_index_ptr != alphabet_index_end)
393         {
394             // If the input is not a multiple of the block size then the input is incorrect.
395             throw padding_error();
396         }
397         if (alphabet_index_ptr >= alphabet_index_end) {
398             abort();
399             return;
400         }
401         Codec::decode_tail(binary_result, state, alphabet_indexes,
402                 static_cast<size_t>(alphabet_index_ptr - alphabet_index_start));
403     }
404 }
405
406 template <typename Codec, typename CodecVariant>
407 inline constexpr size_t stream_codec<Codec, CodecVariant>::encoded_size(size_t binary_size) noexcept
408 {
409     using C = Codec;
410
411     // constexpr rules make this a lot harder to read than it actually is.
412     return CodecVariant::generates_padding()
413             // With padding, the encoded size is a multiple of the encoded block size.
414             // To calculate that, round the binary size up to multiple of the binary block size,
415             // then convert to encoded by multiplying with { base32: 8/5, base64: 4/3 }.
416             ? (binary_size + (C::binary_block_size() - 1)
417                     - ((binary_size + (C::binary_block_size() - 1)) % C::binary_block_size()))
418                     * C::encoded_block_size() / C::binary_block_size()
419             // No padding: only pad to the next multiple of 5 bits, i.e. at most a single extra byte.
420             : (binary_size * C::encoded_block_size() / C::binary_block_size())
421                     + (((binary_size * C::encoded_block_size()) % C::binary_block_size()) ? 1 : 0);
422 }
423
424 template <typename Codec, typename CodecVariant>
425 inline constexpr size_t stream_codec<Codec, CodecVariant>::decoded_max_size(size_t encoded_size) noexcept
426 {
427     using C = Codec;
428
429     return CodecVariant::requires_padding()
430             ? (encoded_size / C::encoded_block_size() * C::binary_block_size())
431             : (encoded_size / C::encoded_block_size() * C::binary_block_size())
432                     + ((encoded_size % C::encoded_block_size())
433                             * C::binary_block_size() / C::encoded_block_size());
434 }
435
436 } // namespace detail
437 } // namespace cppcodec
438
439 #endif // CPPCODEC_DETAIL_STREAM_CODEC