rfc3492.txt

bind 9.3结合mysql数据库

Network Working Group                                        A. Costello
Request for Comments: 3492                 Univ. of California, Berkeley
Category: Standards Track                                     March 2003


              Punycode: A Bootstring encoding of Unicode
       for Internationalized Domain Names in Applications (IDNA)

Status of this Memo

   This document specifies an Internet standards track protocol for the
   Internet community, and requests discussion and suggestions for
   improvements.  Please refer to the current edition of the "Internet
   Official Protocol Standards" (STD 1) for the standardization state
   and status of this protocol.  Distribution of this memo is unlimited.

Copyright Notice

   Copyright (C) The Internet Society (2003).  All Rights Reserved.

Abstract

   Punycode is a simple and efficient transfer encoding syntax designed
   for use with Internationalized Domain Names in Applications (IDNA).
   It uniquely and reversibly transforms a Unicode string into an ASCII
   string.  ASCII characters in the Unicode string are represented
   literally, and non-ASCII characters are represented by ASCII
   characters that are allowed in host name labels (letters, digits, and
   hyphens).  This document defines a general algorithm called
   Bootstring that allows a string of basic code points to uniquely
   represent any string of code points drawn from a larger set.
   Punycode is an instance of Bootstring that uses particular parameter
   values specified by this document, appropriate for IDNA.

Table of Contents

   1. Introduction...............................................2
       1.1 Features..............................................2
       1.2 Interaction of protocol parts.........................3
   2. Terminology................................................3
   3. Bootstring description.....................................4
       3.1 Basic code point segregation..........................4
       3.2 Insertion unsort coding...............................4
       3.3 Generalized variable-length integers..................5
       3.4 Bias adaptation.......................................7
   4. Bootstring parameters......................................8
   5. Parameter values for Punycode..............................8
   6. Bootstring algorithms......................................9



Costello                    Standards Track                     [Page 1]

RFC 3492                     IDNA Punycode                    March 2003


       6.1 Bias adaptation function.............................10
       6.2 Decoding procedure...................................11
       6.3 Encoding procedure...................................12
       6.4 Overflow handling....................................13
   7. Punycode examples.........................................14
       7.1 Sample strings.......................................14
       7.2 Decoding traces......................................17
       7.3 Encoding traces......................................19
   8. Security Considerations...................................20
   9. References................................................21
       9.1 Normative References.................................21
       9.2 Informative References...............................21
   A. Mixed-case annotation.....................................22
   B. Disclaimer and license....................................22
   C. Punycode sample implementation............................23
   Author's Address.............................................34
   Full Copyright Statement.....................................35

1. Introduction

   [IDNA] describes an architecture for supporting internationalized
   domain names.  Labels containing non-ASCII characters can be
   represented by ACE labels, which begin with a special ACE prefix and
   contain only ASCII characters.  The remainder of the label after the
   prefix is a Punycode encoding of a Unicode string satisfying certain
   constraints.  For the details of the prefix and constraints, see
   [IDNA] and [NAMEPREP].

   Punycode is an instance of a more general algorithm called
   Bootstring, which allows strings composed from a small set of "basic"
   code points to uniquely represent any string of code points drawn
   from a larger set.  Punycode is Bootstring with particular parameter
   values appropriate for IDNA.

1.1 Features

   Bootstring has been designed to have the following features:

   *  Completeness:  Every extended string (sequence of arbitrary code
      points) can be represented by a basic string (sequence of basic
      code points).  Restrictions on what strings are allowed, and on
      length, can be imposed by higher layers.

   *  Uniqueness:  There is at most one basic string that represents a
      given extended string.

   *  Reversibility:  Any extended string mapped to a basic string can
      be recovered from that basic string.



Costello                    Standards Track                     [Page 2]

RFC 3492                     IDNA Punycode                    March 2003


   *  Efficient encoding:  The ratio of basic string length to extended
      string length is small.  This is important in the context of
      domain names because RFC 1034 [RFC1034] restricts the length of a
      domain label to 63 characters.

   *  Simplicity:  The encoding and decoding algorithms are reasonably
      simple to implement.  The goals of efficiency and simplicity are
      at odds; Bootstring aims at a good balance between them.

   *  Readability:  Basic code points appearing in the extended string
      are represented as themselves in the basic string (although the
      main purpose is to improve efficiency, not readability).

   Punycode can also support an additional feature that is not used by
   the ToASCII and ToUnicode operations of [IDNA].  When extended
   strings are case-folded prior to encoding, the basic string can use
   mixed case to tell how to convert the folded string into a mixed-case
   string.  See appendix A "Mixed-case annotation".

1.2 Interaction of protocol parts

   Punycode is used by the IDNA protocol [IDNA] for converting domain
   labels into ASCII; it is not designed for any other purpose.  It is
   explicitly not designed for processing arbitrary free text.

2. Terminology

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in BCP 14, RFC 2119
   [RFC2119].

   A code point is an integral value associated with a character in a
   coded character set.

   As in the Unicode Standard [UNICODE], Unicode code points are denoted
   by "U+" followed by four to six hexadecimal digits, while a range of
   code points is denoted by two hexadecimal numbers separated by "..",
   with no prefixes.

   The operators div and mod perform integer division; (x div y) is the
   quotient of x divided by y, discarding the remainder, and (x mod y)
   is the remainder, so (x div y) * y + (x mod y) == x.  Bootstring uses
   these operators only with nonnegative operands, so the quotient and
   remainder are always nonnegative.

   The break statement jumps out of the innermost loop (as in C).




Costello                    Standards Track                     [Page 3]

RFC 3492                     IDNA Punycode                    March 2003


   An overflow is an attempt to compute a value that exceeds the maximum
   value of an integer variable.

3. Bootstring description

   Bootstring represents an arbitrary sequence of code points (the
   "extended string") as a sequence of basic code points (the "basic
   string").  This section describes the representation.  Section 6
   "Bootstring algorithms" presents the algorithms as pseudocode.
   Sections 7.1 "Decoding traces" and 7.2 "Encoding traces" trace the
   algorithms for sample inputs.

   The following sections describe the four techniques used in
   Bootstring.  "Basic code point segregation" is a very simple and
   efficient encoding for basic code points occurring in the extended
   string: they are simply copied all at once.  "Insertion unsort
   coding" encodes the non-basic code points as deltas, and processes
   the code points in numerical order rather than in order of
   appearance, which typically results in smaller deltas.  The deltas
   are represented as "generalized variable-length integers", which use
   basic code points to represent nonnegative integers.  The parameters
   of this integer representation are dynamically adjusted using "bias
   adaptation", to improve efficiency when consecutive deltas have
   similar magnitudes.

3.1 Basic code point segregation

   All basic code points appearing in the extended string are
   represented literally at the beginning of the basic string, in their
   original order, followed by a delimiter if (and only if) the number
   of basic code points is nonzero.  The delimiter is a particular basic
   code point, which never appears in the remainder of the basic string.
   The decoder can therefore find the end of the literal portion (if
   there is one) by scanning for the last delimiter.

3.2 Insertion unsort coding

   The remainder of the basic string (after the last delimiter if there
   is one) represents a sequence of nonnegative integral deltas as
   generalized variable-length integers, described in section 3.3.  The
   meaning of the deltas is best understood in terms of the decoder.

   The decoder builds the extended string incrementally.  Initially, the
   extended string is a copy of the literal portion of the basic string
   (excluding the last delimiter).  The decoder inserts non-basic code
   points, one for each delta, into the extended string, ultimately
   arriving at the final decoded string.




Costello                    Standards Track                     [Page 4]

RFC 3492                     IDNA Punycode                    March 2003


   At the heart of this process is a state machine with two state
   variables: an index i and a counter n.  The index i refers to a
   position in the extended string; it ranges from 0 (the first
   position) to the current length of the extended string (which refers
   to a potential position beyond the current end).  If the current
   state is <n,i>, the next state is <n,i+1> if i is less than the
   length of the extended string, or <n+1,0> if i equals the length of
   the extended string.  In other words, each state change causes i to
   increment, wrapping around to zero if necessary, and n counts the
   number of wrap-arounds.

   Notice that the state always advances monotonically (there is no way
   for the decoder to return to an earlier state).  At each state, an
   insertion is either performed or not performed.  At most one
   insertion is performed in a given state.  An insertion inserts the
   value of n at position i in the extended string.  The deltas are a
   run-length encoding of this sequence of events: they are the lengths
   of the runs of non-insertion states preceeding the insertion states.
   Hence, for each delta, the decoder performs delta state changes, then
   an insertion, and then one more state change.  (An implementation
   need not perform each state change individually, but can instead use
   division and remainder calculations to compute the next insertion
   state directly.)  It is an error if the inserted code point is a
   basic code point (because basic code points were supposed to be
   segregated as described in section 3.1).

   The encoder's main task is to derive the sequence of deltas that will
   cause the decoder to construct the desired string.  It can do this by
   repeatedly scanning the extended string for the next code point that
   the decoder would need to insert, and counting the number of state
   changes the decoder would need to perform, mindful of the fact that
   the decoder's extended string will include only those code points
   that have already been inserted.  Section 6.3 "Encoding procedure"
   gives a precise algorithm.

3.3 Generalized variable-length integers

   In a conventional integer representation the base is the number of
   distinct symbols for digits, whose values are 0 through base-1.  Let
   digit_0 denote the least significant digit, digit_1 the next least
   significant, and so on.  The value represented is the sum over j of
   digit_j * w(j), where w(j) = base^j is the weight (scale factor) for
   position j.  For example, in the base 8 integer 437, the digits are
   7, 3, and 4, and the weights are 1, 8, and 64, so the value is 7 +
   3*8 + 4*64 = 287.  This representation has two disadvantages:  First,
   there are multiple encodings of each value (because there can be
   extra zeros in the most significant positions), which is inconvenient




Costello                    Standards Track                     [Page 5]

RFC 3492                     IDNA Punycode                    March 2003


   when unique encodings are needed.  Second, the integer is not self-
   delimiting, so if multiple integers are concatenated the boundaries
   between them are lost.

   The generalized variable-length representation solves these two
   problems.  The digit values are still 0 through base-1, but now the
   integer is self-delimiting by means of thresholds t(j), each of which
   is in the range 0 through base-1.  Exactly one digit, the most
   significant, satisfies digit_j < t(j).  Therefore, if several
   integers are concatenated, it is easy to separate them, starting with
   the first if they are little-endian (least significant digit first),
   or starting with the last if they are big-endian (most significant
   digit first).  As before, the value is the sum over j of digit_j *
   w(j), but the weights are different:

      w(0) = 1
      w(j) = w(j-1) * (base - t(j-1)) for j > 0

   For example, consider the little-endian sequence of base 8 digits
   734251...  Suppose the thresholds are 2, 3, 5, 5, 5, 5...  This
   implies that the weights are 1, 1*(8-2) = 6, 6*(8-3) = 30, 30*(8-5) =
   90, 90*(8-5) = 270, and so on.  7 is not less than 2, and 3 is not
   less than 3, but 4 is less than 5, so 4 is the last digit.  The value
   of 734 is 7*1 + 3*6 + 4*30 = 145.  The next integer is 251, with
   value 2*1 + 5*6 + 1*30 = 62.  Decoding this representation is very
   similar to decoding a conventional integer:  Start with a current
   value of N = 0 and a weight w = 1.  Fetch the next digit d and
   increase N by d * w.  If d is less than the current threshold (t)
   then stop, otherwise increase w by a factor of (base - t), update t
   for the next position, and repeat.

   Encoding this representation is similar to encoding a conventional
   integer:  If N < t then output one digit for N and stop, otherwise
   output the digit for t + ((N - t) mod (base - t)), then replace N
   with (N - t) div (base - t), update t for the next position, and
   repeat.

   For any particular set of values of t(j), there is exactly one
   generalized variable-length representation of each nonnegative
   integral value.

   Bootstring uses little-endian ordering so that the deltas can be
   separated starting with the first.  The t(j) values are defined in
   terms of the constants base, tmin, and tmax, and a state variable
   called bias:

      t(j) = base * (j + 1) - bias,
      clamped to the range tmin through tmax



Costello                    Standards Track                     [Page 6]

RFC 3492                     IDNA Punycode                    March 2003


   The clamping means that if the formula yields a value less than tmin
   or greater than tmax, then t(j) = tmin or tmax, respectively.  (In
   the pseudocode in section 6 "Bootstring algorithms", the expression
   base * (j + 1) is denoted by k for performance reasons.)  These t(j)
   values cause the representation to favor integers within a particular
   range determined by the bias.

3.4 Bias adaptation

   After each delta is encoded or decoded, bias is set for the next
   delta as follows:

   1. Delta is scaled in order to avoid overflow in the next step:

         let delta = delta div 2

      But when this is the very first delta, the divisor is not 2, but
      instead a constant called damp.  This compensates for the fact
      that the second delta is usually much smaller than the first.

   2. Delta is increased to compensate for the fact that the next delta
      will be inserting into a longer string:

         let delta = delta + (delta div numpoints)

      numpoints is the total number of code points encoded/decoded so
      far (including the one corresponding to this delta itself, and
      including the basic code points).

   3. Delta is repeatedly divided until it falls within a threshold, to