encodings/base32.fz

# This file is part of the Fuzion language implementation.
#
# The Fuzion language implementation is free software: you can redistribute it
# and/or modify it under the terms of the GNU General Public License as published
# by the Free Software Foundation, version 3 of the License.
#
# The Fuzion language implementation is distributed in the hope that it will be
# useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
# License for more details.
#
# You should have received a copy of the GNU General Public License along with The
# Fuzion language implementation.  If not, see <https://www.gnu.org/licenses/>.


# -----------------------------------------------------------------------
#
#  Tokiwa Software GmbH, Germany
#
#  Source code of Fuzion standard library feature base32
#
# -----------------------------------------------------------------------

# Base32 encoding and decoding as defined in RFC 4648
# https://datatracker.ietf.org/doc/html/rfc4648#section-6
#
module:public base32(alphabet array u8, encoding_name String)
pre debug: (container.set_of_ordered alphabet).count = 32
is

  # decode a valid base32 character to 5 bits
  #
  module quintet_bits(n u8) =>
    if 65 <= n <= 90        # case A-Z
      n.as_u64 - 65

    else # 50 <= n <= 55      case 2-7
      n.as_u64 - 24


  # checks if a character is valid in the encoding
  #
  module is_valid(c u8) =>
    (65 <= c <= 90) || (50 <= c <= 55) # A-Z or 2-7


  # Encodes a given byte sequence in base32, output is padded to multiple of 8
  # returns a sequence of ascii values
  #
  public encode(data array u8) Sequence u8 =>

    # extract 8 quintets from 40 bits (of an u64)
    enc40(n u64) =>
      array u8 8 i->
        idx := ((n >> (35-i*5).as_u64) & 31).as_i32
        alphabet[idx]

    for
      res Sequence u8 := [], next        # the encoded data
      i := 0, i+1
      last_n u64 := 0, i %% 5 ?  0 : n
      b in data
      n := (last_n << 8) + b.as_u64
      next := if i%5=4 then res ++ enc40 n
              else          res
    else
      bit_len := data.length%5 * 8       # number of bits in last input block

      if bit_len = 0
        res
      else
        block_len := bit_len/5 + (bit_len%%5 ? 0 : 1)  # number ob characters in last block
        res ++ (enc40 (last_n<<((u64 40)-bit_len.as_u64))).slice 0 block_len ++ (array u8 (8-block_len) _->61)


  # Encodes a given byte sequence in base32, output is padded to multiple of 8
  # returns a string
  #
  public encode_to_string(data array u8) String =>
    String.type.from_bytes (encode data)


  # decodes a base32 string, decoding is strict as required by RFC 4648
  # lowercase letters, non alphabet characters, line breaks, missing padding cause errors
  # NYI: decoding does currently not reject encodings where the padding bits have not been set to zero prior to encoding
  #      therefore in some cases multiple encodings can be decoded to the same data
  #      See RFC4648 section 3.5: https://datatracker.ietf.org/doc/html/rfc4648#section-3.5
  #
  public decode_str(data String) outcome (array u8) =>
    decode data.utf8.as_array


  # decodes a sequence of ASCII characters, decoding is strict as required by RFC 4648
  # lowercase letters, non alphabet characters, line breaks, missing padding cause errors
  # NYI: decoding does currently not reject encodings where the padding bits have not been set to zero prior to encoding
  #      therefore in some cases multiple encodings can be decoded to the same data
  #      See RFC4648 section 3.5: https://datatracker.ietf.org/doc/html/rfc4648#section-3.5
  #
  public decode(data array u8) outcome (array u8) =>

    # determine size of padding, i.e. number of '=' (61 in ASCII) at the end
    pad_size :=
      for
        pad_len := 0, pad_len + (data[i] = 61 ? 1 : 0)
        i in (data.indices.reverse)
        _ in 1..6                             # padding can not be longer than 6
      while data[i] = 61
      else
        pad_len = 2 ? 1                       # padding can not be 2
                    : (pad_len = 5 ? 4        # padding can not be 5
                                   : pad_len)

    dec_input(i) =>

      if i >= data.length
        error "length of input data is not multiple of 8, as required by RFC4648"
      else
        c := data[i]

        # base32 alphabet character
        if (is_valid c)
          outcome (quintet_bits c)

        # padding character =
        else if c = 61
          if i < data.length - pad_size
            # only complain about pad car if length is ok, otherwise wrong length is probably more helpful
            if data.length%%8
              error """
                    padding character '=' not allowed within the input data, only at the very end, \
                    as required by RFC464 (padding length of 2 or 5 can never occur)"""
            else
              error "length of input data is not multiple of 8, as required by RFC4648"
          else outcome (u64 0)  # replace padding with zeros for decoding

        # line break
        else if c = 10 || c = 13
          error """
                line breaks are not allowed within encoded data, as required by RFC464, found \
                {if c=10 then "LF" else "CR"} at position $i"""

        # other non alphabet character
        else
          inv_char := String.type.from_bytes (data.slice i (i+4 > data.length ? data.length : i+4))
                            .substring_codepoint 0 1

          error "invalid $encoding_name input at byte position $i, decoding to unicode character '$inv_char'"

    for
      res := (Sequence u8).empty, res ++ bytes  # contains the decoded data at the end
      nxt := 0, nxt + 8
      last_err := false, is_err
      qnt_last Sequence (outcome u64) := (Sequence (outcome u64)).empty, quintets

    while nxt < data.length && !last_err
    do
      quintets := (nxt :: +1).map(i->dec_input i).take 8
      is_err := (quintets ∃ .is_error)

      # convert quintets in 40 bit number, break up in three bytes
      bits := if is_err then 0
              else quintets.map (.val)
                           .zip (((u64 35) :: -5).take 8) (<<)
                           .foldf (u64 0) (|)
      bytes := [(u64 32), 24, 16, 8, 0].map (i->(bits >> i).low8bits)

    else
      if last_err
        (qnt_last.filter (e -> e.is_error)).first.get.err
      else
        dump_size := 5 - ((40 - (pad_size * 5)) / 8)    # number of decoded bytes caused by zeroed padding
        outcome (res.take res.count-dump_size).as_array # remove zero bytes caused by padding


# Base32 encoding and decoding as defined in RFC 4648
# alphabet is A-Z, 2-7
#
public base32 base32 =>
  base32 "ABCDEFGHIJKLMNOPQRSTUVWXYZ234567".utf8.as_array "base32"