INTERNET-DRAFT
draft-kwiatkowski-base85-for-xml-00.txt                   P. Kwiatkowski
Category: Experimental
Expires: March 2003                                       September 2002


                   A Base-85 Encoding Suitable for XML


Status of this Memo

   This document is an Internet-Draft and is subject to all provisions
   of Section 10 of RFC2026.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups.  Note that
   other groups may also distribute working documents as Internet-
   Drafts.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/1id-abstracts.html

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html


Abstract

   This memo proposes a base85 text encoding for arbitrary binary data
   that is suitable for use in XML documents.  This encoding requires
   approximately 15/16 of the space of the MIME Base64 encoding that is
   currently supported as a primitive datatype in the XML Schema
   definition language.  In a UTF-8 encoded XML entity, Base85 therefore
   has 3/4 of the overhead of Base64.













Kwiatkowski               Expires - March 2003                  [Page 1]


                   A Base-85 Encoding Suitable for XML    September 2002


Table of Contents

   1. Introduction...................................................2
   2. Basic Encoding.................................................3
      2.1 Digits.....................................................3
      2.2 Mapping....................................................4
   3. Additional Features............................................5
      3.1 Padding....................................................5
      3.2 Zero-Compression...........................................6
   4. Detailed Example...............................................6
      4.1 Encoding...................................................6
      4.2 Decoding...................................................8
   5. Comparison with Base64.........................................9
   Security Considerations...........................................9
   Normative References..............................................9
   Informative References...........................................10
   Acknowledgments..................................................10
   Author's Address.................................................10


1. Introduction

   The XML Schema definition language includes "base64Binary" as a
   primitive datatype for representing arbitrary binary information as
   text.  The data is encoded using MIME's Base64 Content-Transfer-
   Encoding [MIME].  MIME uses a 65-character subset of US-ASCII to
   fulfill the portability requirements of a mail encoding, but since
   XML documents must support all Unicode characters, there is no reason
   to limit the choice of characters so strictly.

   Base-85 encodings are a well-understood technique to encode 4 octets
   of arbitrary data in 5 printable characters, using an alphabet of
   only 85 distinct characters.  Examples include PostScript's
   ASCII85Encode Filter and the btoa/atob utilities.  However, these
   indiscriminately use a contiguous range of printable characters.

   Since certain characters must be escaped in XML content, a non-
   contiguous set of characters must be used to represent the 85
   "digits" needed for the encoding, but these can easily be mapped to
   and from the numbers 0-84 in constant time.  A similar approach is
   described in RFC 1924 [Elz], but it must be emphasized that while
   that document was an "April 1" satire, the present memo is a serious
   proposal.

   MIME's Base64 also requires that the number of characters in the
   encoded text must always be a multiple of 4, and uses a special
   padding character if necessary.  There is no analogous requirement in
   the present proposal, although an optional padding character is
   supported.


Kwiatkowski               Expires - March 2003                  [Page 2]


                   A Base-85 Encoding Suitable for XML    September 2002


2. Basic Encoding

   The two main design decisions for a binary-as-text encoding are the
   subset of printable characters used and the mapping between the
   binary octets and characters.

   2.1 Digits

      The 85 characters chosen in this proposal to serve as "digits" in
      the encoded string are as follows:

         0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefg
         hijklmnopqrstuvwxy!#$()*+,-./:;=?@^`{|}~z_

      This set, and certain aspects of the above ordering, have been
      selected carefully.  Of the 95 printable ASCII characters
      (including the space character), all but 10 must be used.  The
      alphanumeric characters are obvious candidates for inclusion.  The
      space character is excluded so that Base85-encoded values will be
      single tokens.

      The XML standard places further constraints on the choice of
      characters [XML].  The ampersand character (&) and the left angle
      bracket (<) are excluded since these must be escaped in XML
      attribute values.  The right angle bracket (>) must be escaped
      when it appears in the string "]]>", so it is safest to exclude
      that character and therefore guarantee that Base85-encoded data
      can be used in any context.  The single-quote character (') must
      be escaped in attribute values delimited by single-quotes, and the
      double-quote character (") must be escaped in attribute values
      delimited by double-quotes.  To avoid constraining the choice of
      quote character for an attribute value containing a Base85-encoded
      string, both of these characters are excluded.  Finally, since
      parameter entity references can appear in general entity value
      literals, and use a percent-sign (%) as a leading delimiter, this
      character is also excluded.

      This leaves the following 26 printable ASCII characters, 3 more of
      which can be excluded:

         !#$()*+,-./:;=?@[\]^_`{|}~

      The backslash (\) is a sensible choice for exclusion since it is
      often used as an escape character.  Finally, the left square
      bracket ([) and right square bracket (]) can serve as useful
      delimiters for base85-encoded data in the midst of text strings,
      and are therefore excluded from the set.




Kwiatkowski               Expires - March 2003                  [Page 3]


                   A Base-85 Encoding Suitable for XML    September 2002


      This alphabet of 85 characters is mapped to the numbers 0-84 in
      the order shown above.  Note that the characters for the decimal
      digits and the upper-case letters from A to F are deliberately
      mapped to the numbers they represent in hexadecimal.

   2.2 Mapping

      As with other base-85 schemes, octets in the binary stream are
      divided into groups ("quanta") of four.  Each quantum is then
      converted to a 32-bit unsigned integer, which is in turn
      repeatedly divided by 85.  The remainders form the digits of the
      Base85 "number", and these digits in the range 0-84 are mapped to
      the alphabet of characters defined above.

      Two interesting, and independent, design decisions are the order
      in which the remainders are listed in the encoded string, and how
      the octets are converted to a single integer.  While most encoded
      strings will not be human-readable, very small 32-bit integers
      will result in recognizable strings if a big-endian format is used
      for the remainders.  However, these 32-bit integers will only have
      values of interest if a) the binary data happens to represent 32-
      bit integers, and b) the system architecture's endianness matches
      that chosen for the octet-to-integer conversion.

      A big-endian format therefore seems sensible for the remainders,
      given that XML is intended to be human-readable when possible.  As
      for the octet-to-integer conversion, Network Byte Ordering (big-
      endian) is the natural choice for an XML encoding.  Since this is
      only to improve readability in rare cases, there is no good reason
      to parameterize an encoding with its endianness.

      The following example shows 8 octets of data (in hex notation) and
      the corresponding 10 characters in the Base85-encoded string:

         [00, 00, 00, 01, 00, 00, 00, 0F] => "000010000F"

      If the number of octets to be converted is not an integral
      multiple of 4, the trailing 1, 2 or 3 bytes are converted using
      the same rules to 2, 3 or 4 characters respectively:

         [00, 00, 00, 01, 00, 00, 0F]     => "00001000F"
         [00, 00, 00, 01, 00, 0F]         => "0000100F"
         [00, 00, 00, 01, 0F]             => "000010F"

      When a Base85-encoded string is to be converted back into binary,
      it is assumed that the number of characters to be converted is
      known (MIME's Base64 makes this assumption, too, as the padding
      character is not always present).  The conversion of the last
      quantum is handled as a special case.


Kwiatkowski               Expires - March 2003                  [Page 4]


                   A Base-85 Encoding Suitable for XML    September 2002


3. Additional Features

   Base-85 encodings leverage the fact that 85^5 > 2^32.  Actually, 83 *
   85^4 and 84^2 * 85^3 are also larger than 2^32, so it is possible to
   reserve certain values for one or two Base85 digits and use those to
   convey additional information.

   3.1 Padding

      Some applications might prefer Base85-encoded strings to be padded
      to a given fixed length.  A character outside the Base85 alphabet
      could be used, but the application would then be responsible for
      trimming the extra characters before passing the string to a
      standard Base85 converter.

      It is possible to instead use one of the 85 characters as a
      padding character by disallowing it as the least significant digit
      in an encoded quantum.  So, the last digit is effectively in "base
      84" and the encoding/decoding algorithms must divide/multiply by
      84 once instead of 85.  The padding character is therefore the
      character that maps to the value 84; the underscore (_) is chosen
      for this purpose.

      The following examples illustrate the range of possible encoded
      strings:

         "00000" => [00, 00, 00, 00]
         "zL@33" => [FF, FF, FF, FF]
         "0000_" => [00, 00, 00]
         "Rs$$_" => [FF, FF, FF]
         "000__" => [00, 00]
         "9FF__" => [FF, FF]
         "00___" => [00]
         "33___" => [FF]

      Any number of underscores can be appended to an encoded string
      without altering its value.  To remove the padding, the decoder
      simply has to strip trailing underscores from the string.

      Optional padding implies that a round-trip conversion from text to
      binary and back again might not yield the original text.  However,
      as long a client that cares about round-trip preservation passes
      consistent desired lengths to the encoder, the encoded text will
      always be the same.  An encoding with no padding can be considered
      the canonical form of a Base85-encoded string.






Kwiatkowski               Expires - March 2003                  [Page 5]


                   A Base-85 Encoding Suitable for XML    September 2002


   3.2 Zero-Compression

      The public-domain btoa/atob utilities use the 'z' character to
      represent the special case of a quantum of 4 zero bytes.  Base85
      can use the same trick, without having to reserve an 86th
      character, by disallowing 'z' as the most significant digit in an
      encoded quantum.  This only affects the encoding/decoding of 5-
      character quanta, in which the most significant digit can have a
      maximum value of 83.  The 'z' character is deliberately mapped to
      the value 83 in the Base85 alphabet.  While the underscore
      normally represents the value 84, if it is used as the most
      significant digit of a 5-character quantum, it is mapped to 83
      instead.

      If a decoder encounters a 'z' character at the beginning of a
      quantum, that character is interpreted as an entire quantum of 4
      zero bytes.  To ensure that round-trip conversions yield the same
      result, the quantum "00000" is considered an encoding violation.

      The following examples incorporate this modification:

         "00000" => encoding violation
         "z"     => [00, 00, 00, 00]
         "zL@33" => [00, 00, 00, 00, CA, C1, 73]
         "_L@33" => [FF, FF, FF, FF]
         "0000_" => [00, 00, 00]
         "000__" => [00, 00]
         "00___" => [00]
         "zz00_" => [00, 00, 00, 00, 00, 00, 00, 00, 00]
         "_00zz" => [FF, 35, 5A, 1B]


4. Detailed Example

   This section walks through the encoding and decoding of a sample
   octet sequence in more detail.

   4.1 Encoding

      Beginning with the octet sequence:

         [FF, 3E, 79, 5F, 00, 00, 00, 00, 3C, C3]

      we isolate the first quantum of four octets and convert them to a
      single unsigned integer:

         FF3E795F hex = 4282284383 decimal




Kwiatkowski               Expires - March 2003                  [Page 6]


                   A Base-85 Encoding Suitable for XML    September 2002


      To obtain the least significant encoded digit, we divide by 84 and
      note the remainder:

         4282284383 / 84 = 50979575 rem 83

      To obtain the remaining digits, from least to most significant, we
      repeatedly divide by 85 and note the remainders:

           50979575 / 85 = 599759   rem 60
             599759 / 85 = 7055     rem 84
               7055 / 85 = 83       rem 0
                 83 / 85 = 0        rem 83

      (The last division is clearly unnecessary in practice.)

      This yields the following digits (shown in decimal):

         (83, 0, 84, 60, 83)

      These values are then used as indices into the Base85 alphabet,
      observing the exception that a leading 83 is represented with an
      underscore, rather than the 'z' character.  We obtain the string:

         "_0_yz"

      Proceeding to the next quantum, we find four zero bytes, which we
      represent with a single 'z' character.  Our encoded string is now:

         "_0_yzz"

      For the remaining quantum of 2 octets, we use the same process as
      for the first quantum, but generate 3 encoded digits instead of 5:

         3CC3 hex = 15555 decimal

         15555 / 84 = 185 rem 15
           185 / 85 = 2   rem 15
             2 / 85 = 0   rem 2

      These digits map straightforwardly to the string "2FF", yielding
      the final encoding string:

         "_0_yzz2FF"

      This can be padded with an arbitrary number of underscores.  In
      this example, we'll assume the client wishes to pad it to a total
      of 16 characters:

         "_0_yzz2FF_______"


Kwiatkowski               Expires - March 2003                  [Page 7]


                   A Base-85 Encoding Suitable for XML    September 2002


   4.2 Decoding

      To decode the above string, we begin by stripping off all trailing
      underscore characters:

         "_0_yzz2FF"

      We then inspect the first character to see if it is a 'z'.  Since
      it is not, we isolate the first quantum of 5 characters and map
      them to decimal values based on their position in the Base85
      alphabet.  Since this is a quantum of size 5, we observe the
      exception that a leading underscore maps to 83 instead of the
      usual 84 (note that leading underscores will only arise with
      quanta of size 5):

         (83, 0, 84, 60, 83)

      We now convert this to a single integer by following a process
      that corresponds to the repeated division above:

           ((((83 * 85) + 0) * 85 + 84) * 85 + 60) * 84 + 83
         = 4282284383 decimal
         = FF3E795F hex

      Performing a big-endian conversion to bytes, we have the initial
      octets:

         [FF, 3E, 79, 5F]

      Examining the remainder of the string:

         "z2FF"

      we note that the first character is now a 'z'.  This is
      immediately consumed as a quantum and 4 zero bytes are appended to
      the decoded result:

         [FF, 3E, 79, 5F, 00, 00, 00, 00]

      The remainder of the string is a single quantum comprising 3
      characters, since it does not begin with a 'z':

         "2FF"

      We map these characters to the decimal digits (2, 15, 15) and once
      again multiply and add repeatedly to obtain a single integer:





Kwiatkowski               Expires - March 2003                  [Page 8]


                   A Base-85 Encoding Suitable for XML    September 2002


           ((2 * 85) + 15) * 84 + 15
         = 15555 decimal
         = 3CC3 hex

      Applying a big-endian conversion and appending the resulting
      octets to the decoded data, we get the final result:

         [FF, 3E, 79, 5F, 00, 00, 00, 00, 3C, C3]


5. Comparison with Base64

   In a UTF-8 encoded XML entity, Base85-encoded data will be about 25
   percent larger than the unencoded data.  In other character
   encodings, such as UTF-16, Base85 may be far from optimal, but it
   will still compare favorably with Base64.

   Asymptotically, Base85 encoded data requires 15/16 (93.75%) of the
   storage needed by Base64.  For long runs of zero bytes, this figure
   shrinks to 3/16 (18.75%).  The comparison is slightly more favorable
   for shorter blocks of data.  Ignoring zero-compression, data blocks
   of 1 to 32 bytes in length will require, on average, 89.84% of the
   space needed by Base64 (this is largely due to the padding
   requirement in Base64).  In particular, 128-bit numbers can be
   represented with just 20 characters in Base85, compared to 24 in
   Base64, so the ratio is 83.33% for that common case.

   Put another way, Base85 asymptotically has only 3/4 of the overhead
   of Base64 (in a UTF-8 encoded entity).  For a 128-bit number, it has
   1/2 the overhead.


Security Considerations

   Since binary data is typically not human-readable, Base85 encoding
   will not enhance the security of a system in any significant way.  It
   will not have any detrimental effect, either.


Normative References

   [XML]     Extensible Markup Language (XML) 1.0 (Second Edition),
             T. Bray, J. Paoli, C. M. Sperberg-McQueen, E. Maler (Eds.)
             http://www.w3.org/TR/2000/REC-xml-20001006, 6 October 2000.







Kwiatkowski               Expires - March 2003                  [Page 9]


                   A Base-85 Encoding Suitable for XML    September 2002


Informative References

   [MIME]    Multipurpose Internet Mail Extensions (MIME) Part One:
             Format of Internet Message Bodies, N. Freed, N. Borenstein,
             RFC 2045, November 1996.

   [Elz]     A Compact Representation of IPv6 Addresses, R. Elz,
             RFC 1924, 1 April 1996
             (Once again, the present memo is a serious proposal,
             despite the fact that it references an "April 1" RFC.)


Acknowledgments

   I wish to thank Robert Elz for promptly answering my questions
   regarding his memo.


Author's Address

   Paul Kwiatkowski
   PMB 785
   15600 NE 8th Street, Suite B1
   Bellevue, WA  98008
   USA

   Email: paulkw@paulkw.com
























Kwiatkowski               Expires - March 2003                 [Page 10]