path: root/doc/draft/draft-ietf-idn-brace-00.txt

INTERNET-DRAFT                                          Adam M. Costello
draft-ietf-idn-brace-00.txt                                  2000-Sep-14
Expires 2001-Mar-14

       BRACE: Bi-mode Row-based ASCII-Compatible Encoding for IDN
                              version 0.1.2

Status of this Memo

    This document is an Internet-Draft and is in full conformance with
    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/ietf/1id-abstracts.txt

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

    Distribution of this document is unlimited.  Please send comments
    to the author at amc@cs.berkeley.edu, or to the idn working group
    at idn@ops.ietf.org.  A newer version of this specification may be
    available at http://www.cs.berkeley.edu/~amc/charset/brace

Abstract

    BRACE is a reversible function from Unicode (UTF-16) [UNICODE]
    text strings to host name labels.  Host name labels are defined by
    [RFC952] and [RFC1123] as case-insensitive strings of ASCII letters,
    digits, and hyphens, neither beginning nor ending with a hyphen.
    [RFC1034] restricts the length of labels to 63 characters.

Contents

    Primary goals
    Secondary goals
    Overview
    Encoding procedure
    Base-32 characters
    Encoding styles
    Decoding procedure
    Comparison with RACE
    Example strings
    Security considerations
    References
    Author
    Example implementation

Primary goals

    Efficient encoding:  Small ratio of encoded size to original size,
    for all UTF-16 strings.

    Uniqueness:  Every UTF-16 string maps to at most one label.

    Completeness:  Every UTF-16 string maps to a label, provided it is
    not too long.  Restrictions on which UTF-16 strings are allowed is
    purely a matter of policy.

    Degeneration:  All valid host name labels that do not end with the
    BRACE signature "-8Q9" (or "-8q9") are the BRACE encodings of their
    own UTF-16 representations.

Secondary goals

    Conceptual simplicity:  This has been somewhat compromised for the
    sake of efficient encoding.

    Readability:  ASCII letters and digits in the original string are
    represented literally in the encoded string.  This comes for free
    because it is the most efficient encoding anyway.

Overview

    The encoded string alternates between two modes.  ASCII letters,
    digits, and hyphens in the Unicode string (which will henceforth be
    called LDH characters) are encoded literally, except that hyphens
    are doubled.  Non-LDH codes in the Unicode string are encoded
    using base-32 mode, in which each character of the encoded string
    represents five bits.  Single hyphens in the encoded string indicate
    mode changes.

    The base-32 mode uses exactly one of four styles.  Half-row style is
    used for Unicode strings in which all the non-LDH codes belong to
    a single half-row (have the same upper 9 bits).  Full-row style is
    used for Unicode strings in which all the non-LDH codes belong to a
    single row (have the same upper 8 bits) but not all the same half.
    Mixed style is used when when many of the non-LDH characters (but
    not all of them) belong to the same row.  No-row style is used for
    all other strings.

Encoding procedure

    If the UTF-16 string contains more than 63 16-bit codes, it's too
    long, so abort.

    If the upper bytes are all zero, and the string formed by the lower
    bytes is a valid host name label and does not end with "-8Q9" or
    "-8q9", output the low bytes and stop.

    The encoder needs a bit queue capable of holding up to 22 bits, a
    buffer of LDH characters capable of holding up to 124 characters,
    and a 4-value encoding style indicator.  The LDH buffer is initially
    empty.  The initial contents of the bit queue, and the value of the
    style indicator, depend on which encoding style is chosen (which
    is explained below).  Bit strings are enqueued and dequeued in
    big-endian order (most significant bit first).

    After choosing the style and initializing the bit queue, perform the
    following actions:

        while the bit queue contains at least 5 bits
            dequeue 5 bits
            output the corresponding base-32 character
        endwhile

        for each 16-bit code of the UTF-16 string (in order) do
            if the code is 0x002D ("-", ASCII hyphen) then
                append two hyphens to the ASCII buffer
            else if the code is an LDH character then
                if the LDH buffer contains no non-hyphens then
                    append one hyphen to the LDH buffer
                endif

                append the code to the LDH buffer
            else (the code is not an LDH character)
                if the LDH buffer contains any non-hyphens then
                    append one hyphen to the LDH buffer
                endif

                if the bit queue is empty then
                    output the LDH buffer and reset it to empty
                endif

                enqueue the bit string corresponding to the code
                (the bit string depends on the encoding style)
                dequeue 5 bits
                output the corresponding base-32 character
                output the LDH buffer and reset it to empty

                while the bit queue contains at least 5 bits
                    dequeue 5 bits
                    output the corresponding base-32 character
                endwhile
            endif
        endfor

        if the bit queue is not empty
            enqueue zero bits until it contains 5 bits
            dequeue 5 bits
            output the corresponding base-32 character
        endif

        output the LDH buffer
        output the LDH characters "-8Q9"

    If the total number of characters output was greater than 63, the
    string is too long for a host name label.

    Notice that a group of LDH characters appears in the output as soon
    as all the bits of the preceeding non-LDH codes have appeared.  The
    base-32 character that appears just before the switch to literal
    mode may contain at most four bits of information from the first
    non-LDH character that comes after the LDH group.

Base-32 characters

    "2" =  0 = 00000
    "3" =  1 = 00001
    "4" =  2 = 00010
    "5" =  3 = 00011
    "6" =  4 = 00100
    "7" =  5 = 00101
    "8" =  6 = 00110
    "9" =  7 = 00111
    "A" =  8 = 01000
    "B" =  9 = 01001
    "C" = 10 = 01010
    "D" = 11 = 01011
    "E" = 12 = 01100
    "F" = 13 = 01101
    "G" = 14 = 01110
    "H" = 15 = 01111
    "I" = 16 = 10000
    "J" = 17 = 10001
    "K" = 18 = 10010
    "M" = 19 = 10011
    "N" = 20 = 10100
    "P" = 21 = 10101
    "Q" = 22 = 10110
    "R" = 23 = 10111
    "S" = 24 = 11000
    "T" = 25 = 11001
    "U" = 26 = 11010
    "V" = 27 = 11011
    "W" = 28 = 11100
    "X" = 29 = 11101
    "Y" = 30 = 11110
    "Z" = 31 = 11111

    The digits "0" and "1" and the letters "O" and "L" ("l") are not
    used, to avoid transcription errors.

    The base-32 characters, like all characters in host name labels, are
    case-insensitive, so they must be recognized in both upper and lower
    case.  However, since existing LDH labels are usually stored in
    lower case, it is recommended that the base-32 portions of encoded
    names be stored in upper case, to help humans easily pick out the
    literal portions.

Encoding styles

    The choice of encoding style depends only on the codes in the UTF-16
    string that are not LDH characters.  It in no way depends on any LDH
    codes that may be present.

    Each code belongs to a particular half-row, which is given by its
    upper 9 bits.  If all of the non-LDH codes belong to the same
    half-row, use half-row style:  Initialize the bit queue by enqueuing
    two 0 bits followed by the designated half-row number (the 9-bit
    half-row number shared by all the codes).  During the encoding
    procedure the bit string corresponding to each code is its lower 7
    bits.

    If not all the non-LDH codes belong to the same half-row, but they
    all belong to the same row (same upper 8 bits), use full-row style:
    Initialize the bit queue by enqueuing a 0 bit, then a 1 bit, then
    the designated row number (the 8-bit row number shared by all the
    codes).  During the encoding procedure the bit string corresponding
    to each code is its lower 8 bits.

    If not all non-LDH codes belong to the same row, then consider
    using mixed style, which chooses a priviledged half-row.  For each
    half-row used by the non-LDH codes, count the number of codes that
    belong to that half-row.  Then, for each half-row, calculate M, the
    number of base-32 characters that would be required if that half row
    were chosen:

        N = total number of non-LDH codes
        H = number of non-LDH codes in the candidate half-row
        C = number of non-LDH codes in the complementary half-row (the
            one with the opposite lowest bit)
        M = (2 + 9 + 18*(N - H - C) + 8*H + 9*C + 4) / 5
          = 3 + (18*N - 10*H - 9*C) / 5

    (The division is integer division, which discards any remainder.)

    Choose the half-row with the smallest M, breaking ties in favor of
    lower-numbered half-rows.  Compare this M with M', the number of
    base-32 characters that would be required if no-row style were used:

        M' = (2 + 16*N + 4) / 5 = (6 + 16*N) / 5

    If M' <= M, use no-row style:  Initialize the bit queue by
    enqueueing two 1 bits.  There is no designated row number.  During
    the encoding procedure the bit string corresponding to each code is
    the full 16-bit code itself.

    If M < M', use mixed style:  Initialize the bit queue by enqueueing
    a 1 bit, then a 0 bit, then the designated 9-bit half-row number
    (the one chosen above).  During the encoding procedure the bit
    string corresponding to each code is:

        0 followed by the lower 7 bits if the code belongs to the chosen
        half-row;

        10 followed by the lower 7 bits if the code belongs to the
        complementary half-row;

        11 followed by the whole 16-bit code otherwise.

Decoding procedure

    The following description assumes that UTF-16 output is desired.

    If the input string does not end with "-8Q9" or "-8q9", output the
    input string (converted from ASCII to UTF-16) and stop.

    The decoder needs a bit queue capable of holding up to 22 bits.  It
    is initially empty.  It also needs a literal-mode flag, which is
    initially unset, and a 4-value style indicator.

    Perform the following actions:

        read the first character and enqueue its base-32 quintet
        dequeue two bits and use them to set the style indicator

        if the style uses a designated full/half row number then
          while the queue does not contain enough bits to represent it
            read the next character and enqueue its base-32
          endwhile

          dequeue enough bits to set the designated row (or half-row)
        endif

        for each remaining input character except the last four do
            if the character is an ASCII hyphen then
                if the next character is also an ASCII hyphen then
                    skip it
                    output an ASCII hyphen (converted to UTF-16)
                else
                    toggle the literal-mode flag
                endif
            else if the literal-mode flag is set then
                output the character (converted to UTF-16)
            else (the literal-mode flag is clear)
                enqueue the character's base-32 quintet

                if the bit queue contains enough bits to represent a
                    UTF-16 code (which depends on the style indicator)
                then
                    dequeue just enough bits to represent one code
                    output the code
                endif
            endif
        endfor

    At the end the bit queue may contain up to four 0 bits.  If it
    contains anything else, the input was invalid.

Comparison with RACE

    BRACE is an extension of RACE [RACE01].  For Unicode strings
    that contain no LDH characters and use the full-row or no-row
    encoding styles, BRACE is virtually identical to RACE.  For other
    strings, BRACE produces a smaller encoding than RACE.  For example,
    the encoding is substantially more compact for Unicode strings
    containing a substantial number of LDH characters, or containing
    many Japanese kana with some kanji.

    Unlike RACE, any LDH characters present in the Unicode string are
    represented literally in the BRACE-encoded string.  This may or may
    not be useful, but it happens to be the most compact way to encode
    LDH characters.

    Whereas RACE uses a signature prefix, BRACE uses a signature suffix.
    This makes it easy to guarantee that the encoded label never ends
    with a hyphen, even if the original UTF-16 string does.  (Whether
    such a UTF-16 string should be allowed is a matter of policy, not
    technical capability).

    The main drawback of BRACE is its greater complexity.

Example strings

    All of these examples use Japanese text, merely because that is the
    only kind of non-English text that the author has lying around.

    Example of no-row style:

        An actual music group name coerced into the usual format for
        host name labels:

            AMURONAMIE-with-super-monkeys

        AMURONAMIE stands for five kanji whose Unicode values are (in
        order):

            U+5B89 U+5BA4 U+5948 U+7F8E U+6075

        The BRACE encoding is:

            UVJ7FUAQCAHY982XA---with--super--monkeys-8Q9

        (Note that the RACE encoding would have been 79 characters long,
        and hence unusable.)

    Example of mixed style:

        An actual song title coerced into the usual format for host name
        labels:

            hello-another-way-SOREZORENOBASHO

        SOREZORENOBASHO stands for five hiragana followed by two kanji,
        whose Unicode values are (in order):

            U+305D U+308C U+305E U+308C U+306E U+5834 U+6240

        The BRACE encoding is:

            JI7-hello--another--way---V3JHAEFVD2UFJ62-8Q9

    Example of full-row style:

        An actual song title, SONOSUPIIDODE, which stands for two
        hiragana followed by four katakana followed by one hiragana,
        whose Unicode values are:

            U+305D U+306E U+30B9 U+30D4 U+30FC U+30C9 U+3067

        The BRACE encoding is:

            BIDPRDMP9WT7MI-8Q9

    Example of half-row style:

        An actual song title:

            PAFIIdeRUNBA

        PAFII stands for four katakana whose Unicode values are:

            U+30D1 U+30D5 U+30A3 U+30FC

        RUNBA stands for three katakana whose Unicode values are:

            U+30EB U+30F3 U+30D0

        The BRACE encoding is:

            3IU8PAZT-de-PYGI-8Q9

    Example of an ASCII string that breaks all the rules of host name
    labels:

        -> $1.00 <-

    The BRACE encoding is:

        229--T2B4-1-W-00-I9I---8Q9

Security considerations

    Users expect each host name in DNS to be controlled by a single
    authority.  If a UTF-16 string could map to multiple labels, then
    a UTF-16 host name could map to multiple real host names, each
    controlled by a different authority, some of which could be spoofs
    that hijack service requests intended for another.  Therefore BRACE
    is designed so that each UTF-16 string maps to a unique label.

    However, there can still be multiple UTF-16 representations
    of the "same" text, for various definitions of "same".  This
    problem is addressed by the Unicode standard under the topic of
    canonicalization, but the issue needs to be studied further in the
    context of host names.

    Also, some text strings may be misleading or ambiguous to humans,
    such as strings containing dots, slashes, at-signs, etc.  Policies
    for allowable Unicode strings need to be developed.

References

    [IDN] Internationalized Domain Names (IETF working group),
    http://www.i-d-n.net/, idn@ops.ietf.org.

    [RACE01] Paul Hoffman, "RACE: Row-based ASCII Compatible Encoding
    for IDN", 2000-Aug-31, draft-ietf-idn-race-01.

    [RFC952] K. Harrenstien, M. Stahl, E. Feinler, "DOD Internet Host
    Table Specification", 1985-Oct, RFC 952.

    [RFC1034] P. Mockapetris, "Domain Names - Concepts and Facilities",
    1987-Nov, RFC 1034.

    [RFC1123] Internet Engineering Task Force, R. Braden (editor),
    "Requirements for Internet Hosts -- Application and Support",
    1989-Oct, RFC 1123.

    [SACE] Dan Oscarsson, "Simple ASCII Compatible Encoding (SACE)",
    draft-ietf-idn-sace.

    [UNICODE] The Unicode Consortium, "The Unicode Standard",
    http://www.unicode.org/unicode/standard/standard.html.

    [UTF5] James Seng, Martin Duerst, Tin Wee Tan, "UTF-5, a
    Transformation Format of Unicode and ISO 10646", draft-jseng-utf5.

Author

    Adam M. Costello <amc@cs.berkeley.edu>
    http://www.cs.berkeley.edu/~amc/


Example implementation


/* brace.c 0.1.1 (2000-Sep-09-Sat)        */
/* Adam M. Costello <amc@cs.berkeley.edu> */

/* This is ANSI C code implementing BRACE version 0.1.*. */

/* Public interface (would normally go in its own .h file): */

enum {
  brace_encoder_in_max = 63,
  brace_encoder_out_max = 4 + (6 + 16 * brace_encoder_in_max) / 5 + 1,
  brace_decoder_in_max = 63 + 1,
  brace_decoder_out_max = brace_decoder_in_max - 1
};

    /* The above constants are the maximum array sizes */
    /* that the encoder/decoder will accept/produce    */
    /* (including null terminators for ASCII strings). */

void brace_encode(
  unsigned int input_length,
  unsigned short *input,
  char output[brace_encoder_out_max] );

    /* brace_encode() converts UTF-16 input to null-terminated */
    /* BRACE-encoded ASCII output.  The input_length must not  */
    /* exceed brace_encoder_in_max, and the output array must  */
    /* have at least the size indicated below.  Under those    */
    /* constraints, this function never fails.                 */

int brace_decode(
  char *input,
  unsigned int *output_length,
  unsigned short output[brace_decoder_out_max] );

    /* brace_decode() converts null-terminated BRACE-encoded ASCII   */
    /* input to UTF-16 output.  The input length (including the null */
    /* terminator) must not exceed brace_encoder_in_max, and output  */
    /* array must have at least the size indicated below.  Returns 1 */
    /* on success, 0 if the input was malformed.  If 0 is returned   */
    /* the output array may contain garbage, but *output_length will */
    /* not have been affected.                                       */


/* Implementation (would normally go in its own .c file): */

#include <assert.h>

static const char base32[] = {
  50, 51, 52, 53, 54, 55, 56, 57, 65, 66, 67, 68, 69, 70, 71, 72,
  73, 74, 75, 77, 78, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90
};

/* We can't use string literals for ASCII characters because */
/* an ANSI C compiler does not necessarily use ASCII.        */

enum encoding_style {
  half_row_style = 0,
  full_row_style = 1,
  mixed_style    = 2,
  no_row_style   = 3
};

/* is_ldh(code) returns 1 if the UTF-16 code represents an LDH */
/* character (ASCII letter, digit, or hyphen), 0 otherwise.    */

static int is_ldh(unsigned short code)
{
  if (code ==  45) return 1;
  if (code <   48) return 0;
  if (code <=  57) return 1;
  if (code <   65) return 0;
  if (code <=  90) return 1;
  if (code <   97) return 0;
  if (code <= 122) return 1;
  return 0;
}

void brace_encode(
  unsigned int input_length,
  unsigned short *input,
  char output[brace_encoder_out_max] )
{
  unsigned long queue;
  enum encoding_style style;
  unsigned short half_rows[brace_encoder_in_max],
                 half_row_counts[brace_encoder_in_max];
  unsigned int num_nonldh, num_half_rows, i, half_row, j, queue_length,
               best_half_row, next_literal_position, non_hyphen_flag,
               next_base32_position, code;

  assert(input_length <= brace_encoder_in_max);

  /* Count the non-LDH codes and half-rows: */

  num_nonldh = 0;
  num_half_rows = 0;

  for (i = 0;  i < input_length;  ++i) {
    if (is_ldh(input[i])) continue;
    ++num_nonldh;
    half_row = input[i] >> 7;

    for (j = 0;  j < num_half_rows;  ++j) {
      if (half_rows[j] == half_row) {
        ++half_row_counts[j];
        break;
      }
    }

    if (j == num_half_rows) {
      half_rows[num_half_rows] = half_row;
      half_row_counts[num_half_rows] = 1;
      ++num_half_rows;
    }
  }

  /* If the input is already a valid label and does not end */
  /* with the BRACE signature, output it and we're done:    */

  if (num_nonldh == 0 &&                     /* all codes are LDH and */
      input[0] != 45 &&                      /* first not hyphen and  */
      input[input_length - 1] != 45 &&       /* last not hyphen and   */
      !( input[input_length - 1] == 57 &&    /* last four not -8Q9    */
         ( input[input_length - 2] == 81 ||
           input[input_length - 2] == 113  ) &&   /* (or -8q9) */
         input[input_length - 3] == 56 &&
         input[input_length - 4] == 45 ) ) {
    for (i = 0;  i < input_length;  ++i) output[i] = input[i];
    output[input_length] = 0;  /* null terminator */
    return;
  }

  /* Choose an encoding style and initialize the bit queue: */

  if (num_half_rows == 1) {
    style = half_row_style;
    queue_length = 11;
    queue = half_rows[0];
  }
  else if ( num_half_rows == 2 &&
            (half_rows[0] >> 1) == (half_rows[1] >> 1) ) {
    style = full_row_style;
    queue_length = 10;
    queue = (1 << 8) | (half_rows[0] >> 1);
  }
  else {
    unsigned int M, H, C, Mprime, best_M = 230;  /* M is always < 230 */

    /* Find the best half-row for mixed style: */

    best_half_row = 512;  /* half_row is always < 512 */

    for (i = 0;  i < num_half_rows;  ++i) {
      half_row = half_rows[i];
      H = half_row_counts[i];
      C = 0;

      for (j = 0;  j < num_half_rows;  ++j) {
        if (j != i && (half_rows[j] >> 1) == (half_row >> 1)) {
          C = half_row_counts[j];
          break;
        }
      }

      M = 3 + (18 * num_nonldh - 10*H - 9*C) / 5;

      if (M < best_M || (M == best_M && half_row < best_half_row)) {
        best_M = M;
        best_half_row = half_row;
      }
    }

    /* Compare mixed style to no-row style: */

    Mprime = (6 + 16 * num_nonldh) / 5;

    if (Mprime <= best_M) {
      style = no_row_style;
      queue_length = 2;
      queue = 3;
    }
    else {
      style = mixed_style;
      queue_length = 11;
      queue = (1 << 10) | best_half_row;
    }
  }

  /* Flush the bit queue: */

  next_base32_position = 0;

  while (queue_length >= 5) {
    queue_length -= 5;
    output[next_base32_position++] =
      base32[(queue >> queue_length) & 0x1f];
  }

  /* To avoid unnecessary copies, we use the output       */
  /* array itself for the LDH buffer.  The following      */
  /* equalities should hold whenever the buffer is empty: */

  next_literal_position = next_base32_position + (queue_length > 0);
  non_hyphen_flag = 0;  /* set whenever buffer contains a non-hyphen */

  /* Main encoding loop: */

  for (i = 0;  i < input_length;  ++i) {
    code = input[i];

    if (code == 45) {
      /* Encode a hyphen as two hyphens into the buffer: */
      output[next_literal_position++] = 45;
      output[next_literal_position++] = 45;
    }
    else if (is_ldh(code)) {
      if (!non_hyphen_flag) {
        /* Indicate a change to literal mode: */
        output[next_literal_position++] = 45;
        non_hyphen_flag = 1;
      }

      /* Encode the LDH character literally: */
      output[next_literal_position++] = code;
    }
    else { /* non-LDH code */
      if (non_hyphen_flag) {
        /* Indicate a change to base-32 mode: */
        output[next_literal_position++] = 45;
        non_hyphen_flag = 0;  /* we will empty the buffer */
      }

      /* If the bit queue is empty, flush the LDH buffer: */

      if (queue_length == 0) {
        next_base32_position = next_literal_position;
      }

      /* Enqueue the bit string corresponding to the code: */

      if (style == half_row_style) {
        queue = (queue << 7) | (code & 0x7f);
        queue_length += 7;
      }
      else if (style == full_row_style) {
        queue = (queue << 8) | (code & 0xff);
        queue_length += 8;
      }
      else if (style == no_row_style) {
        queue = (queue << 16) | code;
        queue_length += 16;
      }
      else /* style == mixed_style */ {
        if ((code >> 7) == best_half_row) {
          queue = (queue << 8) | (code & 0x7f);
          queue_length += 8;
        }
        else if ((code >> 8) == (best_half_row >> 1)) {
          queue = (queue << 9) | (1 << 8) | (code & 0x7f);
          queue_length += 9;
        }
        else {
          queue = (queue << 18) | (3ul << 16) | code;
          queue_length += 18;
        }
      }

      /* Output one base-32 character: */
      queue_length -= 5;
      output[next_base32_position] =
        base32[(queue >> queue_length) & 0x1f];

      if (next_base32_position == next_literal_position) {
        /* LDH buffer is already empty. */
        ++next_base32_position;
      }
      else {
        /* Flush the LDH buffer: */
        next_base32_position = next_literal_position;
      }

      /* next_literal_position is momentarily invalid, */
      /* but we know the LDH buffer is empty.          */

      /* Flush the bit queue: */

      while (queue_length >= 5) {
        queue_length -= 5;
        output[next_base32_position++] =
          base32[(queue >> queue_length) & 0x1f];
      }

      /* Fix next_literal_position: */
      next_literal_position = next_base32_position + (queue_length > 0);
    }

    assert(next_literal_position < brace_encoder_out_max);
  }

  /* Flush the bit queue: */

  if (queue_length > 0) {
    assert(queue_length < 5);
    output[next_base32_position] =
      base32[(queue << (5 - queue_length)) & 0x1f];
  }

  /* Flushing the LDH buffer at this point is a no-op. */

  /* Output "-8Q9" and the null terminator: */

  assert(next_literal_position + 4 < brace_encoder_out_max);
  output[next_literal_position++] = 45;
  output[next_literal_position++] = 56;
  output[next_literal_position++] = 81;
  output[next_literal_position++] = 57;
  output[next_literal_position] = 0;
}

/* base32_decode() converts a base-32 character to a value from  */
/* 0 to 31.  If the character is valid, its value is written to  */
/* *quintet and 1 is returned.  Otherwise, *value is not changed */
/* and 0 is returned.                                            */

static int base32_decode(char c, unsigned int *quintet)
{
  if (c <  50) return 0;
  if (c <= 57) { *quintet = c - 50; return 1; }
  if (c <  65) return 0;
  if (c >= 97) c -= 32;
  if (c <= 75) { *quintet = c - 57; return 1; }
  if (c == 76) return 0;
  if (c <= 78) { *quintet = c - 58; return 1; }
  if (c == 79) return 0;
  if (c <= 90) { *quintet = c - 59; return 1; }
  return 0;
}

int brace_decode(
  char *input,
  unsigned int *output_length,
  unsigned short output[brace_decoder_out_max] )
{
  unsigned long queue;
  unsigned int i, input_length, queue_length, literal_mode_flag,
               quintet, n, next_code_position;
  enum encoding_style style;
  unsigned short common_prefix;
  char c;

  /* Check whether input ends with "-8Q9": */

  for (i = 0;  input[i];  ++i) assert(i < brace_decoder_in_max);

  if (!(input[i-1] == 57 && input[i-3] == 56 &&
        input[i-4] == 45 && (input[i-2] == 81 || input[i-2] == 113))) {

    /* Copy input to output and we're done: */

    for (i = 0;  input[i];  ++i) output[i] = input[i];
    assert(i <= brace_decoder_out_max);
    *output_length = i;
    return 1;
  }

  /* Initialize using the first base-32 character: */

  input_length = i;
  i = 0;
  if (!base32_decode(input[i], &quintet)) return 0;
  queue = quintet;
  queue_length = 3;
  literal_mode_flag = 0;
  style = quintet >> 3;

  /* Determine common_prefix: */

  if (style == no_row_style) n = 0;
  else if (style == full_row_style) n = 8;
  else n = 9;

  while (queue_length < n) {
    if (!base32_decode(input[++i], &quintet)) return 0;
    queue = (queue << 5) | quintet;
    queue_length += 5;
  }

  common_prefix = (queue >> (queue_length - n)) << (16 - n);
  queue_length -= n;

  /* Main decoding loop: */

  next_code_position = 0;

  while (++i < input_length - 4) {
    c = input[i];

    if (c == 45) {
      if (input[i+1] == 45) {
        ++i;
        output[next_code_position++] = 45;  /* "--" means "-" */
      }
      else literal_mode_flag ^= 1;  /* "-" toggles literal mode */
    }
    else if (literal_mode_flag) { /* literal non-hyphen */
      output[next_code_position++] = c;
    }
    else { /* base-32 character */
      /* Enqueue the corresponding quintet: */
      if (!base32_decode(c, &quintet)) return 0;
      queue = (queue << 5) | quintet;
      queue_length += 5;

      /* If the queue contains enough bits for a UTF-16 code, */
      /* dequeue them, decode them, and output the code:      */

      if (style == no_row_style && queue_length >= 16) {
        output[next_code_position++] =
          (queue >> (queue_length - 16)) & 0xffff;
        queue_length -= 16;
      }
      else if (style == full_row_style && queue_length >= 8) {
        output[next_code_position++] =
          common_prefix | ((queue >> (queue_length - 8)) & 0xff);
        queue_length -= 8;
      }
      else if (style == half_row_style && queue_length >= 7) {
        output[next_code_position++] =
          common_prefix | ((queue >> (queue_length - 7)) & 0x7f);
        queue_length -= 7;
      }
      else if (style == mixed_style) {
        n = (queue >> (queue_length - 2)) & 3;  /* top 2 bits */

        if (n <= 1 && queue_length >= 8) {
          output[next_code_position++] =
            common_prefix | ((queue >> (queue_length - 8)) & 0x7f);
          queue_length -= 8;
        }
        else if (n == 2  && queue_length >= 9) {
          output[next_code_position++] = (common_prefix ^ 0x80) |
            ((queue >> (queue_length - 9)) & 0x7f);
          queue_length -= 9;
        }
        else if (n == 3 && queue_length >= 18) {
          output[next_code_position++] =
            (queue >> (queue_length - 18)) & 0xffff;
          queue_length -= 18;
        }
      }
    }
  }

  assert(next_code_position <= brace_decoder_out_max);

  /* Check that the bit queue contains only zeros, at most four: */

  if (queue_length > 4) return 0;
  if ((queue & ((1 << queue_length) - 1)) != 0) return 0;

  /* Set the output length and we're done: */

  *output_length = next_code_position;
  return 1;
}


/* Wrapper for testing (would normally go in a separate .c file): */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static void usage(char **argv)
{
  fprintf(stderr,
    "%s -e reads big-endian UTF-16 and writes BRACE-format ASCII.\n"
    "%s -d reads BRACE-format ASCII and writes big-endian UTF-16.\n"
    , argv[0], argv[0]);
  exit(EXIT_FAILURE);
}

static void fail(const char *msg)
{
  fputs(msg,stderr);
  exit(EXIT_FAILURE);
}

static const char input_too_large[] = "input is too large\n";

int main(int argc, char **argv)
{
  unsigned int input_length;

  if (argc != 2) usage(argv);
  if (argv[1][0] != '-') usage(argv);
  if (argv[1][2] != '\0') usage(argv);

  if (argv[1][1] == 'e') {
    unsigned short input[brace_encoder_in_max];
    char output[brace_encoder_out_max];
    int hi, lo;

    /* Read the UTF-16 input string: */

    input_length = 0;

    for (;;) {
      hi = getchar();
      lo = getchar();

      if (lo == EOF) {
        if (hi != EOF) fail("input contained an odd number of bytes\n");
        break;
      }

      if (input_length == brace_encoder_in_max) fail(input_too_large);

      if (hi > 0xff || lo > 0xff) {
        fail("input bytes do not fit in 8 bits\n");
      }

      input[input_length++] =
        (unsigned short) hi << 8 | (unsigned short) lo;
    }

    /* Encode, and output the result: */

    brace_encode(input_length, input, output);
    if (strlen(output) > brace_decoder_in_max) fail(input_too_large);
    fputs(output,stdout);
    return EXIT_SUCCESS;
  }

  if (argv[1][1] == 'd') {
    char input[brace_decoder_in_max];
    unsigned short output[brace_decoder_out_max];
    unsigned int output_length, i;
    size_t n;

    /* Read the BRACE-encoded ASCII input string: */

    n = fread(input, 1, brace_decoder_in_max, stdin);
    if (n == brace_decoder_in_max) fail(input_too_large);
    input[n] = 0;

    /* Decode, and output the result: */

    if (!brace_decode(input, &output_length, output)) {
      fail("input was malformed\n");
    }

    for (i = 0;  i < output_length;  ++i) {
      putchar(output[i] >> 8);
      putchar(output[i] & 0xff);
    }

    return EXIT_SUCCESS;
  }

  usage(argv);
  return EXIT_SUCCESS;  /* not reached, but quiets compiler warning */
}



                   INTERNET-DRAFT expires 2001-Mar-14