c++/src/kj/encoding.c++

// Copyright (c) 2017 Cloudflare, Inc.; Sandstorm Development Group, Inc.; and contributors
// Licensed under the MIT License:
//
// 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 "encoding.h"
#include "vector.h"
#include "debug.h"

namespace kj {

namespace {

#define GOTO_ERROR_IF(cond) if (KJ_UNLIKELY(cond)) goto error

inline void addChar32(Vector<char16_t>& vec, char32_t u) {
  // Encode as surrogate pair.
  u -= 0x10000;
  vec.add(0xd800 | (u >> 10));
  vec.add(0xdc00 | (u & 0x03ff));
}

inline void addChar32(Vector<char32_t>& vec, char32_t u) {
  vec.add(u);
}

template <typename T>
EncodingResult<Array<T>> encodeUtf(ArrayPtr<const char> text, bool nulTerminate) {
  Vector<T> result(text.size() + nulTerminate);
  bool hadErrors = false;

  size_t i = 0;
  while (i < text.size()) {
    byte c = text[i++];
    if (c < 0x80) {
      // 0xxxxxxx -- ASCII
      result.add(c);
      continue;
    } else if (KJ_UNLIKELY(c < 0xc0)) {
      // 10xxxxxx -- malformed continuation byte
      goto error;
    } else if (c < 0xe0) {
      // 110xxxxx -- 2-byte
      byte c2;
      GOTO_ERROR_IF(i == text.size() || ((c2 = text[i]) & 0xc0) != 0x80); ++i;
      char16_t u = (static_cast<char16_t>(c  & 0x1f) <<  6)
                 | (static_cast<char16_t>(c2 & 0x3f)      );

      // Disallow overlong sequence.
      GOTO_ERROR_IF(u < 0x80);

      result.add(u);
      continue;
    } else if (c < 0xf0) {
      // 1110xxxx -- 3-byte
      byte c2, c3;
      GOTO_ERROR_IF(i == text.size() || ((c2 = text[i]) & 0xc0) != 0x80); ++i;
      GOTO_ERROR_IF(i == text.size() || ((c3 = text[i]) & 0xc0) != 0x80); ++i;
      char16_t u = (static_cast<char16_t>(c  & 0x0f) << 12)
                 | (static_cast<char16_t>(c2 & 0x3f) <<  6)
                 | (static_cast<char16_t>(c3 & 0x3f)      );

      // Disallow overlong sequence.
      GOTO_ERROR_IF(u < 0x0800);

      // Flag surrogate pair code points as errors, but allow them through.
      if (KJ_UNLIKELY((u & 0xf800) == 0xd800)) {
        if (result.size() > 0 &&
            (u & 0xfc00) == 0xdc00 &&
            (result.back() & 0xfc00) == 0xd800) {
          // Whoops, the *previous* character was also an invalid surrogate, and if we add this
          // one too, they'll form a valid surrogate pair. If we allowed this, then it would mean
          // invalid UTF-8 round-tripped to UTF-16 and back could actually change meaning entirely.
          // OTOH, the reason we allow dangling surrogates is to allow invalid UTF-16 to round-trip
          // to UTF-8 without loss, but if the original UTF-16 had a valid surrogate pair, it would
          // have been encoded as a valid single UTF-8 codepoint, not as separate UTF-8 codepoints
          // for each surrogate.
          goto error;
        }

        hadErrors = true;
      }

      result.add(u);
      continue;
    } else if (c < 0xf8) {
      // 11110xxx -- 4-byte
      byte c2, c3, c4;
      GOTO_ERROR_IF(i == text.size() || ((c2 = text[i]) & 0xc0) != 0x80); ++i;
      GOTO_ERROR_IF(i == text.size() || ((c3 = text[i]) & 0xc0) != 0x80); ++i;
      GOTO_ERROR_IF(i == text.size() || ((c4 = text[i]) & 0xc0) != 0x80); ++i;
      char32_t u = (static_cast<char32_t>(c  & 0x07) << 18)
                 | (static_cast<char32_t>(c2 & 0x3f) << 12)
                 | (static_cast<char32_t>(c3 & 0x3f) <<  6)
                 | (static_cast<char32_t>(c4 & 0x3f)      );

      // Disallow overlong sequence.
      GOTO_ERROR_IF(u < 0x10000);

      // Unicode ends at U+10FFFF
      GOTO_ERROR_IF(u >= 0x110000);

      addChar32(result, u);
      continue;
    } else {
      // 5-byte and 6-byte sequences are not legal as they'd result in codepoints outside the
      // range of Unicode.
      goto error;
    }

  error:
    result.add(0xfffd);
    hadErrors = true;
    // Ignore all continuation bytes.
    while (i < text.size() && (text[i] & 0xc0) == 0x80) {
      ++i;
    }
  }

  if (nulTerminate) result.add(0);

  return { result.releaseAsArray(), hadErrors };
}

}  // namespace

EncodingResult<Array<char16_t>> encodeUtf16(ArrayPtr<const char> text, bool nulTerminate) {
  return encodeUtf<char16_t>(text, nulTerminate);
}

EncodingResult<Array<char32_t>> encodeUtf32(ArrayPtr<const char> text, bool nulTerminate) {
  return encodeUtf<char32_t>(text, nulTerminate);
}

EncodingResult<String> decodeUtf16(ArrayPtr<const char16_t> utf16) {
  Vector<char> result(utf16.size() + 1);
  bool hadErrors = false;

  size_t i = 0;
  while (i < utf16.size()) {
    char16_t u = utf16[i++];

    if (u < 0x80) {
      result.add(u);
      continue;
    } else if (u < 0x0800) {
      result.addAll<std::initializer_list<char>>({
        static_cast<char>(((u >>  6)       ) | 0xc0),
        static_cast<char>(((u      ) & 0x3f) | 0x80)
      });
      continue;
    } else if ((u & 0xf800) == 0xd800) {
      // surrogate pair
      char16_t u2;
      if (KJ_UNLIKELY(i == utf16.size()                         // missing second half
                   || (u & 0x0400) != 0                         // first half in wrong range
                   || ((u2 = utf16[i]) & 0xfc00) != 0xdc00)) {  // second half in wrong range
        hadErrors = true;
        goto threeByte;
      }
      ++i;

      char32_t u32 = (((u & 0x03ff) << 10) | (u2 & 0x03ff)) + 0x10000;
      result.addAll<std::initializer_list<char>>({
        static_cast<char>(((u32 >> 18)       ) | 0xf0),
        static_cast<char>(((u32 >> 12) & 0x3f) | 0x80),
        static_cast<char>(((u32 >>  6) & 0x3f) | 0x80),
        static_cast<char>(((u32      ) & 0x3f) | 0x80)
      });
      continue;
    } else {
    threeByte:
      result.addAll<std::initializer_list<char>>({
        static_cast<char>(((u >> 12)       ) | 0xe0),
        static_cast<char>(((u >>  6) & 0x3f) | 0x80),
        static_cast<char>(((u      ) & 0x3f) | 0x80)
      });
      continue;
    }
  }

  result.add(0);
  return { String(result.releaseAsArray()), hadErrors };
}

EncodingResult<String> decodeUtf32(ArrayPtr<const char32_t> utf16) {
  Vector<char> result(utf16.size() + 1);
  bool hadErrors = false;

  size_t i = 0;
  while (i < utf16.size()) {
    char32_t u = utf16[i++];

    if (u < 0x80) {
      result.add(u);
      continue;
    } else if (u < 0x0800) {
      result.addAll<std::initializer_list<char>>({
        static_cast<char>(((u >>  6)       ) | 0xc0),
        static_cast<char>(((u      ) & 0x3f) | 0x80)
      });
      continue;
    } else if (u < 0x10000) {
      if (KJ_UNLIKELY((u & 0xfffff800) == 0xd800)) {
        // no surrogates allowed in utf-32
        hadErrors = true;
      }
      result.addAll<std::initializer_list<char>>({
        static_cast<char>(((u >> 12)       ) | 0xe0),
        static_cast<char>(((u >>  6) & 0x3f) | 0x80),
        static_cast<char>(((u      ) & 0x3f) | 0x80)
      });
      continue;
    } else {
      GOTO_ERROR_IF(u >= 0x110000);  // outside Unicode range
      result.addAll<std::initializer_list<char>>({
        static_cast<char>(((u >> 18)       ) | 0xf0),
        static_cast<char>(((u >> 12) & 0x3f) | 0x80),
        static_cast<char>(((u >>  6) & 0x3f) | 0x80),
        static_cast<char>(((u      ) & 0x3f) | 0x80)
      });
      continue;
    }

  error:
    result.addAll(StringPtr(u8"\ufffd"));
    hadErrors = true;
  }

  result.add(0);
  return { String(result.releaseAsArray()), hadErrors };
}

namespace {

#if __GNUC__ >= 8 && !__clang__
// GCC 8's new class-memaccess warning rightly dislikes the following hacks, but we're really sure
// we want to allow them so disable the warning.
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wclass-memaccess"
#endif

template <typename To, typename From>
Array<To> coerceTo(Array<From>&& array) {
  static_assert(sizeof(To) == sizeof(From), "incompatible coercion");
  Array<wchar_t> result;
  memcpy(&result, &array, sizeof(array));
  memset(&array, 0, sizeof(array));
  return result;
}

template <typename To, typename From>
ArrayPtr<To> coerceTo(ArrayPtr<From> array) {
  static_assert(sizeof(To) == sizeof(From), "incompatible coercion");
  return arrayPtr(reinterpret_cast<To*>(array.begin()), array.size());
}

template <typename To, typename From>
EncodingResult<Array<To>> coerceTo(EncodingResult<Array<From>>&& result) {
  return { coerceTo<To>(Array<From>(kj::mv(result))), result.hadErrors };
}

#if __GNUC__ >= 8 && !__clang__
#pragma GCC diagnostic pop
#endif

template <size_t s>
struct WideConverter;

template <>
struct WideConverter<sizeof(char)> {
  typedef char Type;

  static EncodingResult<Array<char>> encode(ArrayPtr<const char> text, bool nulTerminate) {
    auto result = heapArray<char>(text.size() + nulTerminate);
    memcpy(result.begin(), text.begin(), text.size());
    if (nulTerminate) result.back() = 0;
    return { kj::mv(result), false };
  }

  static EncodingResult<kj::String> decode(ArrayPtr<const char> text) {
    return { kj::heapString(text), false };
  }
};

template <>
struct WideConverter<sizeof(char16_t)> {
  typedef char16_t Type;

  static inline EncodingResult<Array<char16_t>> encode(
      ArrayPtr<const char> text, bool nulTerminate) {
    return encodeUtf16(text, nulTerminate);
  }

  static inline EncodingResult<kj::String> decode(ArrayPtr<const char16_t> text) {
    return decodeUtf16(text);
  }
};

template <>
struct WideConverter<sizeof(char32_t)> {
  typedef char32_t Type;

  static inline EncodingResult<Array<char32_t>> encode(
      ArrayPtr<const char> text, bool nulTerminate) {
    return encodeUtf32(text, nulTerminate);
  }

  static inline EncodingResult<kj::String> decode(ArrayPtr<const char32_t> text) {
    return decodeUtf32(text);
  }
};

}  // namespace

EncodingResult<Array<wchar_t>> encodeWideString(ArrayPtr<const char> text, bool nulTerminate) {
  return coerceTo<wchar_t>(WideConverter<sizeof(wchar_t)>::encode(text, nulTerminate));
}
EncodingResult<String> decodeWideString(ArrayPtr<const wchar_t> wide) {
  using Converter = WideConverter<sizeof(wchar_t)>;
  return Converter::decode(coerceTo<const Converter::Type>(wide));
}

// =======================================================================================

namespace {

const char HEX_DIGITS[] = "0123456789abcdef";
// Maps integer in the range [0,16) to a hex digit.

const char HEX_DIGITS_URI[] = "0123456789ABCDEF";
// RFC 3986 section 2.1 says "For consistency, URI producers and normalizers should use uppercase
// hexadecimal digits for all percent-encodings.

static Maybe<uint> tryFromHexDigit(char c) {
  if ('0' <= c && c <= '9') {
    return c - '0';
  } else if ('a' <= c && c <= 'f') {
    return c - ('a' - 10);
  } else if ('A' <= c && c <= 'F') {
    return c - ('A' - 10);
  } else {
    return nullptr;
  }
}

static Maybe<uint> tryFromOctDigit(char c) {
  if ('0' <= c && c <= '7') {
    return c - '0';
  } else {
    return nullptr;
  }
}

}  // namespace

String encodeHex(ArrayPtr<const byte> input) {
  return strArray(KJ_MAP(b, input) {
    return heapArray<char>({HEX_DIGITS[b/16], HEX_DIGITS[b%16]});
  }, "");
}

EncodingResult<Array<byte>> decodeHex(ArrayPtr<const char> text) {
  auto result = heapArray<byte>(text.size() / 2);
  bool hadErrors = text.size() % 2;

  for (auto i: kj::indices(result)) {
    byte b = 0;
    KJ_IF_MAYBE(d1, tryFromHexDigit(text[i*2])) {
      b = *d1 << 4;
    } else {
      hadErrors = true;
    }
    KJ_IF_MAYBE(d2, tryFromHexDigit(text[i*2+1])) {
      b |= *d2;
    } else {
      hadErrors = true;
    }
    result[i] = b;
  }

  return { kj::mv(result), hadErrors };
}

String encodeUriComponent(ArrayPtr<const byte> bytes) {
  Vector<char> result(bytes.size() + 1);
  for (byte b: bytes) {
    if (('A' <= b && b <= 'Z') ||
        ('a' <= b && b <= 'z') ||
        ('0' <= b && b <= '9') ||
        b == '-' || b == '_' || b == '.' || b == '!' || b == '~' || b == '*' || b == '\'' ||
        b == '(' || b == ')') {
      result.add(b);
    } else {
      result.add('%');
      result.add(HEX_DIGITS_URI[b/16]);
      result.add(HEX_DIGITS_URI[b%16]);
    }
  }
  result.add('\0');
  return String(result.releaseAsArray());
}

String encodeUriFragment(ArrayPtr<const byte> bytes) {
  Vector<char> result(bytes.size() + 1);
  for (byte b: bytes) {
    if (('?' <= b && b <= '_') || // covers A-Z
        ('a' <= b && b <= '~') || // covers a-z
        ('&' <= b && b <= ';') || // covers 0-9
        b == '!' || b == '=' || b == '#' || b == '$') {
      result.add(b);
    } else {
      result.add('%');
      result.add(HEX_DIGITS_URI[b/16]);
      result.add(HEX_DIGITS_URI[b%16]);
    }
  }
  result.add('\0');
  return String(result.releaseAsArray());
}

String encodeUriPath(ArrayPtr<const byte> bytes) {
  Vector<char> result(bytes.size() + 1);
  for (byte b: bytes) {
    if (('@' <= b && b <= '[') || // covers A-Z
        ('a' <= b && b <= 'z') ||
        ('0' <= b && b <= ';') || // covers 0-9
        ('&' <= b && b <= '.') ||
        b == '_' || b == '!' || b == '=' || b == ']' ||
        b == '^' || b == '|' || b == '~' || b == '$') {
      result.add(b);
    } else {
      result.add('%');
      result.add(HEX_DIGITS_URI[b/16]);
      result.add(HEX_DIGITS_URI[b%16]);
    }
  }
  result.add('\0');
  return String(result.releaseAsArray());
}

String encodeUriUserInfo(ArrayPtr<const byte> bytes) {
  Vector<char> result(bytes.size() + 1);
  for (byte b: bytes) {
    if (('A' <= b && b <= 'Z') ||
        ('a' <= b && b <= 'z') ||
        ('0' <= b && b <= '9') ||
        ('&' <= b && b <= '.') ||
        b == '_' || b == '!' || b == '~' || b == '$') {
      result.add(b);
    } else {
      result.add('%');
      result.add(HEX_DIGITS_URI[b/16]);
      result.add(HEX_DIGITS_URI[b%16]);
    }
  }
  result.add('\0');
  return String(result.releaseAsArray());
}

String encodeWwwForm(ArrayPtr<const byte> bytes) {
  Vector<char> result(bytes.size() + 1);
  for (byte b: bytes) {
    if (('A' <= b && b <= 'Z') ||
        ('a' <= b && b <= 'z') ||
        ('0' <= b && b <= '9') ||
        b == '-' || b == '_' || b == '.' || b == '*') {
      result.add(b);
    } else if (b == ' ') {
      result.add('+');
    } else {
      result.add('%');
      result.add(HEX_DIGITS_URI[b/16]);
      result.add(HEX_DIGITS_URI[b%16]);
    }
  }
  result.add('\0');
  return String(result.releaseAsArray());
}

EncodingResult<Array<byte>> decodeBinaryUriComponent(
    ArrayPtr<const char> text, DecodeUriOptions options) {
  Vector<byte> result(text.size() + options.nulTerminate);
  bool hadErrors = false;

  const char* ptr = text.begin();
  const char* end = text.end();
  while (ptr < end) {
    if (*ptr == '%') {
      ++ptr;

      if (ptr == end) {
        hadErrors = true;
      } else KJ_IF_MAYBE(d1, tryFromHexDigit(*ptr)) {
        byte b = *d1;
        ++ptr;
        if (ptr == end) {
          hadErrors = true;
        } else KJ_IF_MAYBE(d2, tryFromHexDigit(*ptr)) {
          b = (b << 4) | *d2;
          ++ptr;
        } else {
          hadErrors = true;
        }
        result.add(b);
      } else {
        hadErrors = true;
      }
    } else if (options.plusToSpace && *ptr == '+') {
      ++ptr;
      result.add(' ');
    } else {
      result.add(*ptr++);
    }
  }

  if (options.nulTerminate) result.add(0);
  return { result.releaseAsArray(), hadErrors };
}

// =======================================================================================

namespace _ { // private

String encodeCEscapeImpl(ArrayPtr<const byte> bytes, bool isBinary) {
  Vector<char> escaped(bytes.size());

  for (byte b: bytes) {
    switch (b) {
      case '\a': escaped.addAll(StringPtr("\\a")); break;
      case '\b': escaped.addAll(StringPtr("\\b")); break;
      case '\f': escaped.addAll(StringPtr("\\f")); break;
      case '\n': escaped.addAll(StringPtr("\\n")); break;
      case '\r': escaped.addAll(StringPtr("\\r")); break;
      case '\t': escaped.addAll(StringPtr("\\t")); break;
      case '\v': escaped.addAll(StringPtr("\\v")); break;
      case '\'': escaped.addAll(StringPtr("\\\'")); break;
      case '\"': escaped.addAll(StringPtr("\\\"")); break;
      case '\\': escaped.addAll(StringPtr("\\\\")); break;
      default:
        if (b < 0x20 || b == 0x7f || (isBinary && b > 0x7f)) {
          // Use octal escape, not hex, because hex escapes technically have no length limit and
          // so can create ambiguity with subsequent characters.
          escaped.add('\\');
          escaped.add(HEX_DIGITS[b / 64]);
          escaped.add(HEX_DIGITS[(b / 8) % 8]);
          escaped.add(HEX_DIGITS[b % 8]);
        } else {
          escaped.add(b);
        }
        break;
    }
  }

  escaped.add(0);
  return String(escaped.releaseAsArray());
}

} // namespace

EncodingResult<Array<byte>> decodeBinaryCEscape(ArrayPtr<const char> text, bool nulTerminate) {
  Vector<byte> result(text.size() + nulTerminate);
  bool hadErrors = false;

  size_t i = 0;
  while (i < text.size()) {
    char c = text[i++];
    if (c == '\\') {
      if (i == text.size()) {
        hadErrors = true;
        continue;
      }
      char c2 = text[i++];
      switch (c2) {
        case 'a' : result.add('\a'); break;
        case 'b' : result.add('\b'); break;
        case 'f' : result.add('\f'); break;
        case 'n' : result.add('\n'); break;
        case 'r' : result.add('\r'); break;
        case 't' : result.add('\t'); break;
        case 'v' : result.add('\v'); break;
        case '\'': result.add('\''); break;
        case '\"': result.add('\"'); break;
        case '\\': result.add('\\'); break;

        case '0':
        case '1':
        case '2':
        case '3':
        case '4':
        case '5':
        case '6':
        case '7': {
          uint value = c2 - '0';
          for (uint j = 0; j < 2 && i < text.size(); j++) {
            KJ_IF_MAYBE(d, tryFromOctDigit(text[i])) {
              ++i;
              value = (value << 3) | *d;
            } else {
              break;
            }
          }
          if (value >= 0x100) hadErrors = true;
          result.add(value);
          break;
        }

        case 'x': {
          uint value = 0;
          while (i < text.size()) {
            KJ_IF_MAYBE(d, tryFromHexDigit(text[i])) {
              ++i;
              value = (value << 4) | *d;
            } else {
              break;
            }
          }
          if (value >= 0x100) hadErrors = true;
          result.add(value);
          break;
        }

        case 'u': {
          char16_t value = 0;
          for (uint j = 0; j < 4; j++) {
            if (i == text.size()) {
              hadErrors = true;
              break;
            } else KJ_IF_MAYBE(d, tryFromHexDigit(text[i])) {
              ++i;
              value = (value << 4) | *d;
            } else {
              hadErrors = true;
              break;
            }
          }
          auto utf = decodeUtf16(arrayPtr(&value, 1));
          if (utf.hadErrors) hadErrors = true;
          result.addAll(utf.asBytes());
          break;
        }

        case 'U': {
          char32_t value = 0;
          for (uint j = 0; j < 8; j++) {
            if (i == text.size()) {
              hadErrors = true;
              break;
            } else KJ_IF_MAYBE(d, tryFromHexDigit(text[i])) {
              ++i;
              value = (value << 4) | *d;
            } else {
              hadErrors = true;
              break;
            }
          }
          auto utf = decodeUtf32(arrayPtr(&value, 1));
          if (utf.hadErrors) hadErrors = true;
          result.addAll(utf.asBytes());
          break;
        }

        default:
          result.add(c2);
      }
    } else {
      result.add(c);
    }
  }

  if (nulTerminate) result.add(0);
  return { result.releaseAsArray(), hadErrors };
}

// =======================================================================================
// This code is derived from libb64 which has been placed in the public domain.
// For details, see http://sourceforge.net/projects/libb64

// -------------------------------------------------------------------
// Encoder

namespace {

typedef enum {
  step_A, step_B, step_C
} base64_encodestep;

typedef struct {
  base64_encodestep step;
  char result;
  int stepcount;
} base64_encodestate;

const int CHARS_PER_LINE = 72;

void base64_init_encodestate(base64_encodestate* state_in) {
  state_in->step = step_A;
  state_in->result = 0;
  state_in->stepcount = 0;
}

char base64_encode_value(char value_in) {
  static const char* encoding = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
  if (value_in > 63) return '=';
  return encoding[(int)value_in];
}

int base64_encode_block(const char* plaintext_in, int length_in,
                        char* code_out, base64_encodestate* state_in, bool breakLines) {
  const char* plainchar = plaintext_in;
  const char* const plaintextend = plaintext_in + length_in;
  char* codechar = code_out;
  char result;
  char fragment;

  result = state_in->result;

  switch (state_in->step) {
    while (1) {
      KJ_FALLTHROUGH;
  case step_A:
      if (plainchar == plaintextend) {
        state_in->result = result;
        state_in->step = step_A;
        return codechar - code_out;
      }
      fragment = *plainchar++;
      result = (fragment & 0x0fc) >> 2;
      *codechar++ = base64_encode_value(result);
      result = (fragment & 0x003) << 4;
      KJ_FALLTHROUGH;
  case step_B:
      if (plainchar == plaintextend) {
        state_in->result = result;
        state_in->step = step_B;
        return codechar - code_out;
      }
      fragment = *plainchar++;
      result |= (fragment & 0x0f0) >> 4;
      *codechar++ = base64_encode_value(result);
      result = (fragment & 0x00f) << 2;
      KJ_FALLTHROUGH;
  case step_C:
      if (plainchar == plaintextend) {
        state_in->result = result;
        state_in->step = step_C;
        return codechar - code_out;
      }
      fragment = *plainchar++;
      result |= (fragment & 0x0c0) >> 6;
      *codechar++ = base64_encode_value(result);
      result  = (fragment & 0x03f) >> 0;
      *codechar++ = base64_encode_value(result);

      ++(state_in->stepcount);
      if (breakLines && state_in->stepcount == CHARS_PER_LINE/4) {
        *codechar++ = '\n';
        state_in->stepcount = 0;
      }
    }
  }
  /* control should not reach here */
  return codechar - code_out;
}

int base64_encode_blockend(char* code_out, base64_encodestate* state_in, bool breakLines) {
  char* codechar = code_out;

  switch (state_in->step) {
  case step_B:
    *codechar++ = base64_encode_value(state_in->result);
    *codechar++ = '=';
    *codechar++ = '=';
    ++state_in->stepcount;
    break;
  case step_C:
    *codechar++ = base64_encode_value(state_in->result);
    *codechar++ = '=';
    ++state_in->stepcount;
    break;
  case step_A:
    break;
  }
  if (breakLines && state_in->stepcount > 0) {
    *codechar++ = '\n';
  }

  return codechar - code_out;
}

}  // namespace

String encodeBase64(ArrayPtr<const byte> input, bool breakLines) {
  /* set up a destination buffer large enough to hold the encoded data */
  // equivalent to ceil(input.size() / 3) * 4
  auto numChars = (input.size() + 2) / 3 * 4;
  if (breakLines) {
    // Add space for newline characters.
    uint lineCount = numChars / CHARS_PER_LINE;
    if (numChars % CHARS_PER_LINE > 0) {
      // Partial line.
      ++lineCount;
    }
    numChars = numChars + lineCount;
  }
  auto output = heapString(numChars);
  /* keep track of our encoded position */
  char* c = output.begin();
  /* store the number of bytes encoded by a single call */
  int cnt = 0;
  size_t total = 0;
  /* we need an encoder state */
  base64_encodestate s;

  /*---------- START ENCODING ----------*/
  /* initialise the encoder state */
  base64_init_encodestate(&s);
  /* gather data from the input and send it to the output */
  cnt = base64_encode_block((const char *)input.begin(), input.size(), c, &s, breakLines);
  c += cnt;
  total += cnt;

  /* since we have encoded the entire input string, we know that
     there is no more input data; finalise the encoding */
  cnt = base64_encode_blockend(c, &s, breakLines);
  c += cnt;
  total += cnt;
  /*---------- STOP ENCODING  ----------*/

  KJ_ASSERT(total == output.size(), total, output.size());

  return output;
}

// -------------------------------------------------------------------
// Decoder

namespace {

typedef enum {
  step_a, step_b, step_c, step_d
} base64_decodestep;

struct base64_decodestate {
  bool hadErrors = false;
  size_t nPaddingBytesSeen = 0;
  // Output state. `nPaddingBytesSeen` is not guaranteed to be correct if `hadErrors` is true. It is
  // included in the state purely to preserve the streaming capability of the algorithm while still
  // checking for errors correctly (consider chunk 1 = "abc=", chunk 2 = "d").

  base64_decodestep step = step_a;
  char plainchar = 0;
};

int base64_decode_value(char value_in) {
  // Returns either the fragment value or: -1 on whitespace, -2 on padding, -3 on invalid input.
  //
  // Note that the original libb64 implementation used -1 for invalid input, -2 on padding -- this
  // new scheme allows for some simpler error checks in steps A and B.

  static const signed char decoding[] = {
    -3,-3,-3,-3,-3,-3,-3,-3,  -3,-1,-1,-3,-1,-1,-3,-3,
    -3,-3,-3,-3,-3,-3,-3,-3,  -3,-3,-3,-3,-3,-3,-3,-3,
    -1,-3,-3,-3,-3,-3,-3,-3,  -3,-3,-3,62,-3,-3,-3,63,
    52,53,54,55,56,57,58,59,  60,61,-3,-3,-3,-2,-3,-3,
    -3, 0, 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,-3,-3,-3,-3,-3,
    -3,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,-3,-3,-3,-3,-3,

    -3,-3,-3,-3,-3,-3,-3,-3,  -3,-3,-3,-3,-3,-3,-3,-3,
    -3,-3,-3,-3,-3,-3,-3,-3,  -3,-3,-3,-3,-3,-3,-3,-3,
    -3,-3,-3,-3,-3,-3,-3,-3,  -3,-3,-3,-3,-3,-3,-3,-3,
    -3,-3,-3,-3,-3,-3,-3,-3,  -3,-3,-3,-3,-3,-3,-3,-3,
    -3,-3,-3,-3,-3,-3,-3,-3,  -3,-3,-3,-3,-3,-3,-3,-3,
    -3,-3,-3,-3,-3,-3,-3,-3,  -3,-3,-3,-3,-3,-3,-3,-3,
    -3,-3,-3,-3,-3,-3,-3,-3,  -3,-3,-3,-3,-3,-3,-3,-3,
    -3,-3,-3,-3,-3,-3,-3,-3,  -3,-3,-3,-3,-3,-3,-3,-3,
  };
  static_assert(sizeof(decoding) == 256, "base64 decoding table size error");
  return decoding[(unsigned char)value_in];
}

int base64_decode_block(const char* code_in, const int length_in,
                        char* plaintext_out, base64_decodestate* state_in) {
  const char* codechar = code_in;
  char* plainchar = plaintext_out;
  signed char fragment;

  if (state_in->step != step_a) {
    *plainchar = state_in->plainchar;
  }

#define ERROR_IF(predicate) state_in->hadErrors = state_in->hadErrors || (predicate)

  switch (state_in->step)
  {
    while (1)
    {
      KJ_FALLTHROUGH;
  case step_a:
      do {
        if (codechar == code_in+length_in) {
          state_in->step = step_a;
          state_in->plainchar = '\0';
          return plainchar - plaintext_out;
        }
        fragment = (signed char)base64_decode_value(*codechar++);
        // It is an error to see invalid or padding bytes in step A.
        ERROR_IF(fragment < -1);
      } while (fragment < 0);
      *plainchar    = (fragment & 0x03f) << 2;
      KJ_FALLTHROUGH;
  case step_b:
      do {
        if (codechar == code_in+length_in) {
          state_in->step = step_b;
          state_in->plainchar = *plainchar;
          // It is always an error to suspend from step B, because we don't have enough bits yet.
          // TODO(someday): This actually breaks the streaming use case, if base64_decode_block() is
          //   to be called multiple times. We'll fix it if we ever care to support streaming.
          state_in->hadErrors = true;
          return plainchar - plaintext_out;
        }
        fragment = (signed char)base64_decode_value(*codechar++);
        // It is an error to see invalid or padding bytes in step B.
        ERROR_IF(fragment < -1);
      } while (fragment < 0);
      *plainchar++ |= (fragment & 0x030) >> 4;
      *plainchar    = (fragment & 0x00f) << 4;
      KJ_FALLTHROUGH;
  case step_c:
      do {
        if (codechar == code_in+length_in) {
          state_in->step = step_c;
          state_in->plainchar = *plainchar;
          // It is an error to complete from step C if we have seen incomplete padding.
          // TODO(someday): This actually breaks the streaming use case, if base64_decode_block() is
          //   to be called multiple times. We'll fix it if we ever care to support streaming.
          ERROR_IF(state_in->nPaddingBytesSeen == 1);
          return plainchar - plaintext_out;
        }
        fragment = (signed char)base64_decode_value(*codechar++);
        // It is an error to see invalid bytes or more than two padding bytes in step C.
        ERROR_IF(fragment < -2 || (fragment == -2 && ++state_in->nPaddingBytesSeen > 2));
      } while (fragment < 0);
      // It is an error to continue from step C after having seen any padding.
      ERROR_IF(state_in->nPaddingBytesSeen > 0);
      *plainchar++ |= (fragment & 0x03c) >> 2;
      *plainchar    = (fragment & 0x003) << 6;
      KJ_FALLTHROUGH;
  case step_d:
      do {
        if (codechar == code_in+length_in) {
          state_in->step = step_d;
          state_in->plainchar = *plainchar;
          return plainchar - plaintext_out;
        }
        fragment = (signed char)base64_decode_value(*codechar++);
        // It is an error to see invalid bytes or more than one padding byte in step D.
        ERROR_IF(fragment < -2 || (fragment == -2 && ++state_in->nPaddingBytesSeen > 1));
      } while (fragment < 0);
      // It is an error to continue from step D after having seen padding bytes.
      ERROR_IF(state_in->nPaddingBytesSeen > 0);
      *plainchar++   |= (fragment & 0x03f);
    }
  }

#undef ERROR_IF

  /* control should not reach here */
  return plainchar - plaintext_out;
}

}  // namespace

EncodingResult<Array<byte>> decodeBase64(ArrayPtr<const char> input) {
  base64_decodestate state;

  auto output = heapArray<byte>((input.size() * 6 + 7) / 8);

  size_t n = base64_decode_block(input.begin(), input.size(),
      reinterpret_cast<char*>(output.begin()), &state);

  if (n < output.size()) {
    auto copy = heapArray<byte>(n);
    memcpy(copy.begin(), output.begin(), n);
    output = kj::mv(copy);
  }

  return EncodingResult<Array<byte>>(kj::mv(output), state.hadErrors);
}

String encodeBase64Url(ArrayPtr<const byte> bytes) {
  // TODO(perf): Rewrite as single pass?
  // TODO(someday): Write decoder?

  auto base64 = kj::encodeBase64(bytes);

  for (char& c: base64) {
    if (c == '+') c = '-';
    if (c == '/') c = '_';
  }

  // Remove trailing '='s.
  kj::ArrayPtr<const char> slice = base64;
  while (slice.size() > 0 && slice.back() == '=') {
    slice = slice.slice(0, slice.size() - 1);
  }

  return kj::str(slice);
}

} // namespace kj