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