Subject: [idn] Re: permission <draft-ietf-idn-ace37-00.txt (attach)

From: "Edmon" <[email-masked]>
Date: Thu, 5 Jul 2001 11:48:53 -0400

Hi all,

I was unaware that the workgroup no longer accepts new drafts.  Anyway, I
have drafted a new ACE based on the simplicity of DUDE which has hugely
improved compression.  Worst case scenario CJK could have 21 han characters!
Attached below is a copy of the draft (for my original submission), you can
also find it at http://www.dnsii.org/idn-ace37-00.txt (easier to read) and
hopefully in the i-d-n.net website soon.

ACE37 is based on the one-pass one-mode scheme of DUDE (diiferential XOR),
then utilizes a simple code block shifting (similar to the reference points
in the AMC series) to hugely increase the capacity for CJK (worst case
scenario 21 han characters!) and then utilizes base-32 for compression (as
in LACE) (DUDE and AMC-w/v uses base-32 only for flagging).  In addition to
base-32, a base-4 scheme is introduced by using the remaining characters
{wxyz}.  These contain 2 bits of character information and doubles as an
indicator for codepoint brackets.  All the while, the algorithm is kept to
be as simple as DUDE.

Hopefully you might find that it is interesting and appropriate to be
considered as an ACE within the IETF.  Afterall, it was intended to be an
integrated version of the three primary ACEs: DUDE, LACE and the AMC series,
identified by the ACE design team report.

Looking forward to all your inputs.

Edmon

PS. I have created an Excel worksheet to illustrate the Encoding and
Decoding procedures as well you can find them at
http://www.dnsii.org/ace37/ace37-encode.xls and
http://www.dnsii.org/ace37/ace37-decode.xls respectively.

----- Original Message -----
From: "Marc Blanchet" <[email-masked]>
To: "Natalia Syracuse" <[email-masked]>; <[email-masked]>;
<[email-masked]>
Cc: <[email-masked]>
Sent: Thursday, July 05, 2001 8:50 AM
Subject: Re: permission <draft-ietf-idn-ace37-00.txt (attach)

> I'm sorry but the new wg policy is to not accept draft unless there is a
> demonstrated support. But drafts are _highly_ encouraged to be published
as
> individual submissions. I would recommend to put idn in the filename and
> use this filenaming convention: draft-<yourname>-idn-ace37-00.txt. After
> publication in the internet-draft, the author should announce it in the wg
> mailing list and I'll put a reference to it in the wg web page.
>
> So please publish it as individual submission.
>
> Marc.
>
> At/À 08:34 2001-07-05 -0400, Natalia Syracuse you wrote/vous écriviez:
> >
> >
> >
> >Internet Draft                                 Edmon Chung, Neteka Inc.
> ><draft-ietf-idn-ace37-00.txt>                  David Leung, Neteka Inc.
> >                                                               June 2001
> >
> >
> >
> >           ACE Utilizing All 37 Alphanumeric Characters (ACE37)
> >
> >
> >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 reader is cautioned not to depend on the values that appear in
> >    examples to be current or complete, since their purpose is primarily
> >    educational.  Distribution of this memo is unlimited.
> >
> >    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.
> >
> >Abstract
> >
> >    ACE37 is a combination of DUDE-02, AMC-W/V and LACE.  ACE37 utilizes
> >    the simple one pass algorithm of DUDE, the character block
> >    considerations of AMC-W/V and the Base-32 compression of LACE.  It
> >    also fully utilizes entire LDH set currently allowed in the DNS (A-
> >    z, 0-9 and "-") within its character repertoire to optimize
> >    performance and compression.  Even for the worst-case scenario in
> >    ACE37, any name can have 21 characters including Chinese, Japanese
> >    and Korean names. Two Excel spreadsheets for ACE37 encoding and
> >    decoding can be found at http://www.dnsii.org/ace37/ace37-encode.xls
> >    and http://www.dnsii.org/ace37/ace37-decode.xls respectively.
> >
> >    While DUDE-02 provides a very efficient differential mechanism, its
> >    compression is inefficient as it fails to take advantage of the
> >    base-32 scheme in using all 5-bits for character information.  The
> >    AMC series is highly efficient in compression but requires
> >    complicated mode changes and therefore inefficient in process.  LACE
> >    is rather moderate and requires a two-pass mechanism but utilizes
> >    base-32 for good compression.
> >
> >
> >Chung & Leung                                                  [Page 1]
> >ACE37       ACE Utilizing All 37 Alphanumeric Characters      July 2001
> >
> >    ACE37 uses simple character block shifting to achieve the
> >    compression efficiency of the AMC series, retains the one-pass and
> >    one mode XOR differential mechanism used by DUDE while embracing the
> >    base-32 compression used by LACE for efficient character bit
> >    information.
> >
> >Terminology
> >
> >    The key words "MUST", "SHALL", "REQUIRED", "SHOULD", "RECOMMENDED",
> >    and "MAY" in this document are to be interpreted as described in RFC
> >    2119 [RFC2119].
> >
> >    LDH: Letters, Digits and Hyphens: a string of characters that
> >    consists only hyphens ("-"), English letters (A-z) and digits (0-9),
> >    which might not be a result of an algorithm for transcoding
> >    multilingual characters. For example: whatever-you-want.example
> >
> >    ACE - ASCII Compatible Encoding: a string of characters resulting
> >    from a particular algorithm for transforming multilingual character
> >    information into an alphanumeric form acceptable by the existing
> >    DNS.  For example: bq--3bhc2zmh.tld.  In essence, ACE is a subset of
> >    LDH.
> >
> >    Hexadecimal values are shown preceeded by "0x".  For example, 0x60
> >    is decimal 96.  Binary values are shown preceeded by "0b" for
> >    example "0b1000" is decimal 8.  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 (or
> >    hexadecimal numbers) is denoted by two hexadecimal numbers separated
> >    by "..", with no prefixes.
> >
> >    Octets: sequences of 8 bits; Quintets: sequences of 5 bits;
> >    Quartets: sequences of 4 bits; Duplets: sequences of 2 bits.
> >
> >    XOR: bitwise exclusive or.  Given 2 nonnegative integers A and B, A
> >    XOR B is the nonnegative integer value whose binary representation
> >    is 1 wherever A and B disagrees, and 0 wherever they agree.
> >
> >Table Of Contents
> >
> >    1. Introduction....................................................3
> >    2. Code Block Shifting.............................................4
> >    3. Base-32 Characters..............................................5
> >    4. Base-4 Characters...............................................6
> >
> >    5. LDH Considerations..............................................9
> >    6. Encoding Procedure..............................................9
> >    7. Decoding Procedure.............................................11
> >    8. Examples.......................................................13
> >    9. Summary & Comparisons..........................................15
> >    10. Security Considerations.......................................16
> >    11. References....................................................16
> >
> >Chung & Leung                                                  [Page 2]
> >ACE37       ACE Utilizing All 37 Alphanumeric Characters      July 2001
> >
> >1. Introduction
> >
> >    ACE37 takes into account the recommendations and findings of the ACE
> >    design team to create a "super-ACE" that incorporates the key
> >    advantages of the various considered ACEs without complicated mode
> >    changes.  The encoding (Section 6) and decoding (Section 7) process
> >    is largely similar to and as simple as DUDE-02.  The encoding
> >    processes for ACE37 in comparison with DUDE-02 could be summarized:
> >
> >         ACE37 Encoding Procedure     |     DUDE Encoding Procedure
> >     ---------------------------------+---------------------------------
> >     (1) let initial prev = 0x00      | (1) let initial prev = 0x60
> >     (2) if n = LDH output "-n"       | (2) if n = hyphen output "-"
> >     (3) code block shift to obtain   | (3) diff = prev XOR n
> >           ACE37 shifted n (Section 2)| (4) prepend "0" to the last
> >     (4) diff = prev XOR n            |      quartet and "1" to others
> >     (5) output in appropriate base-4 | (5) output a base-32 character
> >           and base-32 form           |      for each corresponding
> >           (Sections 3&4)             |      quintet
> >     (6) let prev = n                 | (6) let prev = n
> >
> >    Similarly, the decoding process can be described and compared:
> >
> >         ACE37 Decoding Procedure     |     DUDE Decoding Procedure
> >     ---------------------------------+---------------------------------
> >     (1) let initial prev = 0x00      | (1) let initial prev = 0x60
> >     (2) if char = hyphen discard "-" | (2) if char = hyphen consume
> >           and output next char       |       and output 0x002D
> >     (3) consume and convert char into| (3) consume and convert to
> >           duplets and quintets       |       quintets until encoun-
> >           (according to Sections 3&4)|       erring a quintet with "0"
> >     (4) concatenate to form diff     |       as first bit
> >           (based on Sections 4.1&4.2)| (4) strip all first bits off
> >     (5) let prev = prev XOR diff     | (5) concatente to form diff
> >     (6) reverse code block shifting  | (6) let prev = prev XOR diff
> >     (7) output Unicode code point    | (7) output Unicode code point
> >
> >    The features of ACE37 include:
> >
> >    Unique & Reversible - the ACE37 encoding scheme yields a unique and
> >    consistent result string for a given set of Unicode code points.
> >    The encoded string could be decoded back to the original Unicode
> >    code points without loss of character data.
> >
> >    Simple - ACE37 utilizes a one-pass system and the XOR differential
> >    function to encode and decode.  Code block shifting is done by a
> >    simple calculation instead of mapping or creation of arbitrary
> >    reference points. Complex mode changes are not required.
> >
> >    Spacious - With the code block shifting coupled with a base-32
> >    scheme, ACE37 can accommodate up to 21 unique Han characters
> >    (including CJK) within the 63 octets allowed by the DNS.  Other
> >    Latin based scripts can reach up to 31 characters.
> >Chung & Leung                                                  [Page 3]
> >ACE37       ACE Utilizing All 37 Alphanumeric Characters      July 2001
> >
> >
> >    Completeness - any sequence of Unicode code points
> >    (U+0000..U+10FFFF) could be encoded.  Restrictions of allowed code
> >    points is not discussed, but is expected that Nameprep [Nameprep]
> >    will be used prior to ACE37 encoding.
> >
> >    In essence, it captures the focus criterions discussed by the
> >    workgroup ACE design team - reversibility, simplicity and
> >    compression capability.  Moreover, ACE37 utilizes a very simple code
> >    block shifting (Section 2) mechanism to allow up to any 21 CJK
> >    ideographs to be encoded within the 63-octet constraint.
> >
> >2. Code Block Shifting
> >
> >    While the DNS was not originally designed for multilingual
> >    characters, Unicode was not designed with the DNS in mind and
> >    therefore code points were apparently not allocated in an ACE-
> >    friendly way.
> >
> >    The AMC series [AMC-W & AMC-V] utilizes a number of reference points
> >    to achieve better compression efficiency by anticipating and
> >    minimizing delta between characters.  For ACE37, a much simpler
> >    rendering is used.  More specifically, the entire character block
> >    U+3000..U+9FFF for CJK ideographs is shifted down by 0x3000.  That
> >    is U+3000 will become 0x0000, U+4000 becomes 0x1000, and so on.  To
> >    compensate for the downwards shift, the general script and symbol
> >    characters in U+0000..U+2FFF will be shifted upwards by 0x7000.
> >    Therefore, U+0100 will become 0x7100, U+2000 becomes 0x9000, and so
> >    on.  All other code points (U+A000..U+10FFFF) are unchanged.
> >
> >       Original Unicode Allocation   |     ACE37 Code Block Shifted
> >     --------------------------------|-------------------------------
> >       General Scripts  U+0000 -+    |     +- 0x0000 CJK Misc
> >                        U+1000  |    |     |  0x1000 CJK Ideographs
> >                                +-   |  -> |  0x2000
> >       Symbols          U+2000 -+ \  | /   |  0x3000
> >                                   \ |/    |  0x4000
> >       CJK Misc         U+3000 -+   \/     |  0x5000
> >       CJK Ideographs   U+4000  |   /\     +- 0x6000
> >                        U+5000  |  / |\
> >                        U+6000  +--  | \   +- 0x7000 General Scripts
> >                        U+7000  |    |  -> |  0x8000
> >                        U+8000  |    |     |
> >                        U+9000 -+    |     +- 0x9000 Symbols
> >                                     |
> >       Hangul           U+A000 -+    |     +- 0xA000 Hangul
> >                        U+B000  |    |     |  0xB000
> >                        U+C000  +----|---> |  0xC000
> >                        U+D000  |    |     |  0xD000
> >         :                 :   -+    |     +-    :      :
> >                                     |
> >
> >
> >Chung & Leung                                                  [Page 4]
> >ACE37       ACE Utilizing All 37 Alphanumeric Characters      July 2001
> >
> >    This shifting effectively moves the entire Han library to within
> >    0x6FFF and therefore could be represented in 15-bits or exactly 3
> >    base-32 characters.  (details on base-32 characters in Section 3)
> >
> >    For example, the Chinese character for <change> with the original
> >    Unicode code point at U+8F49, will be shifted to 0x5F49 and can be
> >    represented in 3 quintets, and in turn with 3 base-32 characters:
> >
> >                     Character: <change>
> >            Unicode Code Point: U+8F49
> >                 ACE37 Shifted: 0x5F49
> >        Corresponding Quartets: 0101 1111 0100 1001
> >            Resulting Quintets: 10111 11010 01001
> >                       Base-32: nq9   (further discussed in Section 3)
> >
> >    This in turn means that any Chinese character could be represented
> >    with 3 base-32 characters making the total possible characters
> >    within a label, even without further compression introduced by the
> >    XOR differential process (Section 6), to be at least 21.  The ACE37
> >    code block shifting process could be described as follows:
> >
> >       for each input code point = n
> >       if n <= 9FFF
> >          n = n - 0x3000      /*downwards shifting*/
> >          if n <= 0
> >             n = 0x9FFF + n   /*compensation for U+0000..U+2FFF*/
> >
> >    The character block shifting introduced here is extremely simple and
> >    utilizes simple calculation that requires no mapping function.  At
> >    the same time, it achieves the goal in adjusting the Unicode
> >    allocation so that it becomes more ACE friendly.
> >
> >3. Base-32 Characters
> >
> >    Base-32 characters are used in LACE for compression, while DUDE-02
> >    and the AMC series only utilizes it for quartet flagging to indicate
> >    the last quartet of each encoded code point.  ACE37 utilizes base-32
> >    characters for compression while base-4 characters, which will be
> >    introduced in Section 4, determine the compressed code point
> >    brackets.
> >
> >    The following table shows the 32 base-32 characters and their
> >    corresponding quintets:
> >
> >    Base-32 Character =to= Corresponding Quintet
> >        0 = 00000       8 = 01000       g = 10000       o = 11000
> >        1 = 00001       9 = 01001       h = 10001       p = 11001
> >        2 = 00010       a = 01010       i = 10010       q = 11010
> >        3 = 00011       b = 01011       j = 10011       r = 11011
> >        4 = 00100       c = 01100       k = 10100       s = 11100
> >        5 = 00101       d = 01101       l = 10101       t = 11101
> >        6 = 00110       e = 01110       m = 10110       u = 11110
> >        7 = 00111       f = 01111       n = 10111       v = 11111
> >Chung & Leung                                                  [Page 5]
> >ACE37       ACE Utilizing All 37 Alphanumeric Characters      July 2001
> >
> >
> >    With this layout of base-32 characters, it is also possible to
> >    implement a computation based base-32 conversion instead of having
> >    to resort to mapping and lookup tables:
> >
> >       For each quintet = q
> >           if q <= 0x0F
> >              then hex dump q to form base-32 character
> >           if 0x10 <= q <= 0x1F
> >              then q = q - 0x10
> >                 and char(q + 0x67) to form base-32 character
> >
> >    Note that 0x67 is the code value for the letter "g".  Therefore, for
> >    example if the quintet is 0b10001 its base-32 character can be
> >    obtained by:
> >
> >       0x10 <= q=0b10001=0x11 <= 0x1F
> >       therefore q = q - 0x10 = 0x11 - 0x10 = 0x01
> >             and base-32 character = char(0x01 + 0x67)
> >                 char(0x68) = "h"
> >
> >4. Base-4 Characters
> >
> >    ACE37 goes beyond the 32 characters (base-32) to include the
> >    remaining 4 characters {w,x,y,z} in the alphabet.  These base-4
> >    characters enable ACE37 to better utilize the existing "resources"
> >    (the allowed characters) to represent IDN character information,
> >    therefore making it's encoding more efficient.
> >
> >    The set of base-4 characters are {w,x,y,z} and will be used to
> >    represent the following duplets (duplets are groups containing 2
> >    bits):
> >
> >    Base-4 Character =to= Corresponding Duplet
> >                   w   =  00
> >                   x   =  01
> >                   y   =  10
> >                   z   =  11
> >
> >4.1 Base-4 Indicators
> >
> >    Base-4 characters while carrying character information, also doubles
> >    as an indicator for code point brackets.  In DUDE-02, an extra bit
> >    was pre-pended to each quartet.  The last quartet of each encoded
> >    code point will be pre-pended with "0", marking the end of the code
> >    point.  In ACE37, base-4 characters will determine the length
> >    (number of ACE37 characters) of the encoded code point.  Actually,
> >    to be more precise, the encoded bits are in fact the "diff" and not
> >    the code point itself (diff carries the same meaning as in DUDE-02
> >    and is further discussed in Sections 6 & 7)
> >
> >
> >
> >Chung & Leung                                                  [Page 6]
> >ACE37       ACE Utilizing All 37 Alphanumeric Characters      July 2001
> >
> >    The following table explains how base-4 characters are combined with
> >    base-32 characters to form a representation of a diff (key: b4=base-
> >    4, b32=base-32):
> >
> >              diff value         |bits|       ACE37 Form
> >        -------------------------|----|----------------------------
> >                  diff<=0x7F     |  7 | <b4><b32>
> >            0x80<=diff<=0x7FFF   | 15 | <b32><b32><b32>
> >          0x8000<=diff<=0x1FFFF  | 17 | w<b4><b32><b32><b32>
> >         0x20000<=diff<=0xFFFFF  | 20 | ww<b32><b32><b32><b32>
> >        0x100000<=diff<=0x10FFFF | 22 | <b4>w<b32><b32><b32><b32>
> >
> >    Note that the "bits" column represents the maximum number of
> >    significant bits for the given diff value.  For example when
> >    diff<=0x7F, the maximum value is 0b1111111, therefore the number of
> >    significant bits is 7.
> >
> >    Note also that to encode a 17-bit diff, the letter "w" is used as an
> >    indicator to distinguish the sequence from the 7 bit diff where a
> >    base-32 character is expected to follow a base-4 character.  Since
> >    "w" represents "00" that has no value, it will not be used in the
> >    base-4 representation for a 17-bit diff (if a "00" is used, it means
> >    that there are only 15 significant bits and therefore should use the
> >    15 bit diff form).  This is the case for the 20-bit form as well.
> >    The "w" is used as an arbitrary indicator in the 22-bit form and
> >    MUST be discarded during decoding.
> >
> >    By analyzing the ACE37 form, an encoded string could be successfully
> >    returned to its original form.  There is no overlap and the form can
> >    be determined precisely.  The following 5 rules dictate the 5
> >    different ACE37 forms:
> >
> >    (1) Encode: if diff<=0x7F
> >        Decode: if first character is <b4> AND next character NOT <b4>
> >                Then it MUST be in 7-bit form: <b4><b32>
> >
> >    (2) Encode: if 0x80<=diff<=0x7FFF
> >        Decode: if first character is <b32>
> >                Then it MUST be a 15-bit form: <b32><b32><b32>
> >
> >    (3) Encode: if 0x8000<=diff<=0x1FFFF
> >        Decode: if first character is "w" AND next character is <b4>
> >                   AND NOT "w"
> >                Then it MUST be in 17-bit form: w<b4><b32><b32><b32>
> >
> >    (4) Encode: if 0x20000<=diff<=0xFFFFF
> >        Decode: if first character is "w" AND next character is "w"
> >                Then it MUST be in 20-bit form: ww<b32><b32><b32><b32>
> >
> >    (5) Encode: if 0x80<=diff<=0x7FFF
> >        Decode: if first character is <b4> AND NOT "w"
> >                   AND next character is "w"
> >                Then it MUST be 22-bit form: <b4>w<b32><b32><b32><b32>
> >Chung & Leung                                                  [Page 7]
> >ACE37       ACE Utilizing All 37 Alphanumeric Characters      July 2001
> >
> >
> >    Note that the ACE37 scheme can effectively encode a diff of up to 22
> >    significant bits or 0x3FFFFF.  The Unicode code points are expected
> >    to range only between 0x0000..0x10FFFF, therefore ACE37 will be able
> >    to handle any Unicode code point.
> >
> >    Additionally, base-4 characters (and sometimes base-32 characters)
> >    could be used for mixed-case annotation.  This optional mixed-case
> >    annotation mechanism is discussed in Appendix B.
> >
> >4.2 First Code Point Considerations
> >
> >    There are additional considerations for the first code point that is
> >    encoded or decoded to ensure that if the first code point is within
> >    the first Unicode plane (U+0000..U+FFFF), it will not occupy more
> >    than 4 ACE37 characters.
> >
> >    This special consideration affects only Rules (1), (3) and (4)
> >    explained in Section 4.1.  Rule (1) is discarded for the first code
> >    point, therefore any diff under 0x7FFF will be in the form
> >    <b32><b32><b32>.  The form for Rule (3) becomes simply
> >    <b4><b32><b32><b32> without the "w" indicator.  Similarly, the form
> >    for Rule (4) becomes w<b32><b32><b32><b32> with one less "w".
> >
> >    The first code point considerations can be summarized in the
> >    following 4 rules:
> >
> >    (a) Encode: if diff<=0x7FFF
> >        Decode: if first character is <b32>
> >                Then it MUST be in 15-bit form: <b32><b32><b32>
> >
> >    (b) Encode: if 0x8000<=diff<=0x1FFFF
> >        Decode: if first character is <b4> AND NOT "w"
> >                Then it MUST be in 17-bit form: <b4><b32><b32><b32>
> >
> >    (c) Encode: if 0x20000<=diff<=0xFFFFF
> >        Decode: if first character is "w"
> >                Then it MUST be in 20-bit form: w<b32><b32><b32><b32>
> >
> >    (d) Encode & Decode: same as Rule (5) in Section 4.1
> >
> >    Besides special considerations for base-4 character usage, prev
> >    setting is also specially considered for the first code point.  As
> >    laid out in Section 6, in order to detect for the first code point,
> >    the prev is evaluated.  If prev = 0x00, it is assumed that it is the
> >    first code point as 0x00 SHOULD not be a permitted character for
> >    input.  When an LDH is the first code point, there is a need to make
> >    a special consideration.  Regularly, if n = LDH is encountered
> >    (Section 5), it will be output as "-n" and prev is not changed.
> >    However, if the first code point is an LDH, after outputting "-n",
> >    prev is updated to = lowercase(n).  This is to ensure and maintain
> >    that only the first code point coming in will have a prev = 0x00.
> >
> >Chung & Leung                                                  [Page 8]
> >ACE37       ACE Utilizing All 37 Alphanumeric Characters      July 2001
> >
> >5. LDH Considerations
> >
> >    Finally, the 37th character of the entire LDH repertoire, the hyphen
> >    will be used to indicate LDH exceptions.  Extending the hyphen
> >    consideration of DUDE-02, ACE37 gives special consideration for the
> >    entire LDH repertoire.  All LDH characters will be encoded "as is"
> >    with the addition of a leading hyphen.  For example, the character
> >    "a" will be encoded within ACE37 as "-a".  The hyphen character "-"
> >    will be encoded as "--".
> >
> >    This ensures that each LDH character will only take up 2 character
> >    spaces within an ACE37 encoded string and also will allow
> >    administrators to see the actual characters, similar to the AMC
> >    series.  Unlike the AMC series however, the hyphen is not used to
> >    indicate an ongoing mode change, but only the following character.
> >    Therefore retaining the simplicity of the DUDE-02 single-mode,
> >    single-pass philosophy.
> >
> >6. Encoding Procedure
> >
> >    Similar to DUDE, all ordering of bits and quartets is big-endian.
> >    The following describes the encoding procedure:
> >
> >    Set initial value for prev = 0x00
> >    for each input code point = n
> >       if n is an LDH {A-z, 0-9, -}
> >          output "-n"                   (Section 5: LDH Considerations)
> >          if prev = 0x00                (Section 4.2: First Code Point)
> >             let prev = lowercase(n)
> >       else perform code block shifting (Section 2: Code Block Shifting)
> >       let diff = prev XOR n            (n after code block shifting)
> >       if diff<=0x7F --------------------------------------+
> >          and if this is the first code point (Section 4.2)|
> >          then output 15-bit form: <b32><b32><b32>         |
> >          else, output 7-bit form: <b4><b32>               |
> >       if 0x80<=diff<=0x7FFF                               +-(Section 4:
> >          output 15-bit form: <b32><b32><b32>              |   Base-4
> >       if 0x8000<=diff<=0x1FFFF                            | Characters)
> >          and if this is the first code point (Section 4.2)|
> >          output 17-bit form: w<b4><b32><b32><b32>         |
> >       if 0x20000<=diff<=0xFFFFF                           |
> >          output 20-bit form: ww<b32><b32><b32><b32>       |
> >       if 0x100000<=diff<=0x10FFFF                         |
> >          output 22-bit form: <b4>w<b32><b32><b32><b32> ---+
> >       let prev = n
> >    end and obtain next n and return to: "for each input code point = n"
> >
> >    The following is a more comprehensive pseudo code:
> >
> >    let prev = 0x00
> >    for each input integer n (in order) do begin
> >       if n = "-" or "0..9" or "A..Z" or "a..z"
> >       then output "hyphen"+"char(n)"
> >Chung & Leung                                                  [Page 9]
> >ACE37       ACE Utilizing All 37 Alphanumeric Characters      July 2001
> >
> >          if prev = 0x00
> >             let prev = lowercase(n)
> >
> >       else begin
> >          if n = 0x00
> >             then error and abort
> >          if n <= 9FFF
> >          n = n - 0x30
> >             if n < 0
> >             then n = 9FFF + n
> >
> >          let diff = prev XOR n
> >
> >          if diff <= 0x7F
> >             if prev = 0x00
> >             then output with 3 base-32 characters
> >          else, output first 2 bits with a base-4 character {wxyz}
> >             and remaining 5 bits with 1 base-32 character
> >
> >          if 0x80 <= diff <= 0x7FFF
> >          then output all 15 bits with base-32 characters
> >
> >          if 0x8000 <= diff <= 0xFFFF
> >             if prev = 0x00
> >             then output first 2 bits with a base-4 {xyz} (except w)
> >             and output remaining 15 bits with base-32
> >          else, output "w"
> >             and output first 2 bits with a base-4 {xyz} (except w]
> >             and output remaining 15 bits with base-32
> >
> >          if 0x10000 <= diff <= 0x1FFFF
> >          then output "w"
> >             and output first 2 bits with a base-4 {xyz} (except w)
> >             and output remaining 15 bits with base-32
> >
> >          if 0x20000 <= diff <= 0xFFFFFF
> >          then output "w"
> >             and output all 20 bits with base-32 characters
> >
> >          if 0x100000 <= diff <= 0x10FFFF
> >          then output first 2 bits with a base-4 {xyz} (except w)
> >             and output "w"
> >             and output remaining 15 bits with base-32
> >
> >          let prev = n
> >       end
> >    end
> >
> >    Nameprep [NAMEPREP] is not discussed in this document, but is
> >    expected that it be implemented for IDN.  Hence, regardless of the
> >    code point presented, an encoder MUST not produce an incorrect
> >    output.  The encoder must fail if it encounters a negative input
> >    value.
> >Chung & Leung                                                 [Page 10]
> >ACE37       ACE Utilizing All 37 Alphanumeric Characters      July 2001
> >
> >
> >    The initial value used is 0x00 so that all domains beginning with a
> >    CJK ideograph or within row 0 (U+0000..U+0FFF) will be shorter.
> >    Note that after the code block shifting (Section 2), the entire Han
> >    library is within 0x0000..0x6FFF, while row 0 is fitted to
> >    0x7000..0x7FFF.  Therefore by using an initial value of 0x00 the
> >    diff for all Han and row 0 characters will be less than 0x7FFF.  The
> >    initial value is also used as a check point for the first code point
> >    considerations (Section 4.2).
> >
> >    Additionally, an optional mixed-case annotation mechanism is
> >    discussed in Appendix B.
> >
> >7. Decoding Procedure
> >
> >    A thorough description of the decoding rules, except for the final
> >    reversal of the code block shifting has been presented in Sections
> >    4.1 and 4.2.  The following description is a brief representation of
> >    the decoding procedure:
> >
> >    let prev = 0x00
> >    while the input string is not exhausted
> >       if present character = hyphen               (Section 5: LDH
> >          discard and output next character         Considerations)
> >       else, depending on the presented form       (Section 4)
> >          convert into duplets and quintets        (Section 4 & 3)
> >          and concatenate to form diff
> >       let prev = prev XOR diff
> >       reverse code block shifting:                (Section 2)
> >          if prev<=0x9FFF
> >             and if prev<=0x6FFF
> >                    output character = prev + 0x3000
> >             else, output character = prev - 0x7000
> >          else output character = prev
> >       output character
> >    End
> >
> >    The following is a more comprehensive pseudo code for the decoding
> >    precedure:
> >
> >    let prev = 0x00
> >    while the input string is not exhausted do begin
> >       if present character = hyphen    /*Section 5:LDH Considerations*/
> >       then consume and discard hyphen
> >          and obtain the next character
> >          and output character
> >          if prev = 0x00                /*Section 4.2:First Code Point*/
> >             let prev = code block shifted lowercase output character
> >
> >       else,
> >          if present character = Base-32 characters (0..v)
> >             consume present character and next 2 characters
> >             and convert them to quintets according to Base-32
> >Chung & Leung                                                 [Page 11]
> >ACE37       ACE Utilizing All 37 Alphanumeric Characters      July 2001
> >
> >             concatenate the resulting quintets to form diff
> >             /*15 bit form, 0x80<=diff<=0x7FFF*/
> >
> >          if present character = Base-4 characters {xyz} and NOT w
> >             consume present character
> >                and convert it to a duplet according to Base-4
> >
> >             if prev = 0x00
> >                obtain and consume next 3 characters
> >                and convert them to quintets according to Base-32
> >                concatenate duplet with the 3 quintets to form diff
> >                /*first code point: 17 bit form, 0x8000<=diff<=0x1FFFF*/
> >
> >             else, if next character = Base-32 character (0..v)
> >                then consume and convert to quintet according to Base-32
> >                concatenate duplet with the quintet to form diff
> >                /*7 bit form, diff<=0x7F*/
> >
> >             else, obtain next character
> >             if next character = Base-4 characters {xyz} and NOT w
> >                then fail and indicate error
> >
> >             else, if next character = w
> >                then consume and discard w and obtain next 4 characters
> >                consume and convert characters to
> >                   quintets according to Base-32
> >                concatenate duplet with the 4 quintets to form diff
> >                /*22 bit form, 0x100000<=diff<=0x10FFFF*/
> >
> >          if present character = w
> >             discard "w" and obtain next character
> >
> >             if next character = Base-4 characters {xyz} and NOT w
> >
> >                and if prev = 0x00
> >                    obtain and consume next 4 characters
> >                    and convert characters to quintets based on Base-32
> >                    concatenate the 4 quintets to form diff
> >                    /*first code point: 20 bit form,*/
> >                    /*0x20000<=diff<=0xFFFFFF       */
> >
> >                else, consume and convert to duplet according to Base-4
> >                   and obtain and consume next 3 characters
> >                   and convert to quintets according to Base-32
> >                   concatenate duplet with the 3 quintets to form diff
> >                   /*17 bit form, 0x8000<=diff<=0x1FFFF*/
> >
> >             else, if next character = w
> >                then consume and discard w
> >                and obtain and consume next 4 characters
> >                   and convert to quintets according to Base-32
> >                concatenate duplet the 4 quintets to form diff
> >                /*20 bit form, 0x20000<=diff<=0xFFFFFF*/
> >Chung & Leung                                                 [Page 12]
> >ACE37       ACE Utilizing All 37 Alphanumeric Characters      July 2001
> >
> >
> >             else, if next character = Base-32 character (0..v)
> >                then convert to quintet according to Base-32
> >                set quintet to diff
> >                /*7 bit form, diff<=0x7F*/
> >
> >          fail upon encountering a non-ACE37 character
> >             or end-of-input
> >
> >          let prev = prev XOR diff
> >
> >          if prev <= 0x9FFF                /*reversal of the code    */
> >             and if prev <= 6FFF           /*block shifting described*/
> >             output = prev + 0x3000        /*in Section 2            */
> >             else, output = prev - 0x7000
> >          else, output prev
> >       end
> >    end
> >    encode the output sequence and compare it to the input string
> >    fail if they do not match (case insensitively)
> >
> >8. Examples
> >
> >    ACE37 is likely to be implemented with an ACE prefix in the form
> >    "xx--".  The actual prefix to be used is not discussed in this
> >    document.  The following examples are taken from the mailing list as
> >    well as from DUDE-02 and the AMC series.  The resulting ACE37 string
> >    is compared with that using DUDE:
> >
> >    (A) JPNIC (the registry of .jp domain)
> >
> >    Unicode: U+793E U+56E3 U+6CD5 U+4EBA U+65E5 U+672C U+30CD U+30C3
> >             U+30C8 U+30EF U+30FC U+30AF U+30A4 U+30F3 U+30D5 U+30A9
> >             U+30E1 U+30FC U+30B7 U+30E7 U+30F3 U+30BB U+30F3 U+30BF
> >             U+30FC
> >      ACE37: i9urut6hm8jfaqv0m9dv1wewbx7wjyjwbynx6zsy8wtybygwky8y8ycy3
> >             (57 char)
> >    DUDE-02: (error: result string exceeds 59 characters*)
> >             Note: 59 characters is the maximum allowable when the ACE
> >             prefix "xx--" is included
> >
> >
> >    (B) A health-insurance organization in Tokyo
> >
> >    Unicode: U+6771 U+4EAC U+90FD U+60C5 U+5831 U+30B5 U+30FC U+30D3
> >             U+30B9 U+7523 U+696D U+5065 U+5EB7 U+4FDD U+967A U+7D44
> >             U+5408
> >      ACE37: drhaetvihk1o67ka44y9xfzahcqv2e6883micbaud7apuqac (48 char)
> >    DUDE-02: (error: result string exceeds 59 characters)
> >
> >
> >
> >
> >Chung & Leung                                                 [Page 13]
> >ACE37       ACE Utilizing All 37 Alphanumeric Characters      July 2001
> >
> >    (C) 6 hangul syllables
> >
> >    Unicode: U+C138 U+ACC4 U+C758 U+BAA8 U+B4E0 U+C0AC
> >      ACE37: xg9orfsqssvfg3i8t2c (19 char)
> >    DUDE-02: 6txiy79ny53nz79a8wizwwn (23 char)
> >
> >
> >    (D) maji<de>koi<suru>5<byou><mae>  (Latin, hiragana, kanji)
> >
> >    Unicode: U+006D U+0061 U+006A U+0069 U+3067 U+006B U+006F U+0069
> >             U+3059 U+308B U+0035 U+79D2 U+524D
> >      ACE37: -m-a-j-is0a-k-o-xu06i-5iapqsv (30 char)
> >    DUDE-02: pnmdvssqvssnegvsva7cvs5qz38hu53r (32 char)
> >
> >
> >    (E) <pafii>de<runba>  (Latin, katakana)
> >
> >    Unicode: U+30D1 U+30D5 U+30A3 U+30FC U+0064 U+0065 U+30EB U+30F3
> >             U+30D0
> >      ACE37: 06hw4zmyv-d-ewnwox3 (19 char)
> >    DUDE-02: vs5bezgxrvs3ibvs2qtiud (22 char)
> >
> >
> >    (F) <sono><supiido><de>  (hiragana, katakana)
> >
> >    Unicode: U+305D U+306E U+30B9 U+30D4 U+30FC U+30C9 U+3067
> >      ACE37: 02txj06nzdx8xl05e (17 char)
> >    DUDE-02: vsvpvd7hypuivf4q (16 char)
> >
> >
> >    (G) 2 Arbitrary Plane Two Code Points
> >
> >    Unicode: U+261AF U+261BF
> >      ACE37: w4odfwg (7 char)
> >    DUDE-02: uyt6rta (7 char)
> >
> >
> >    (H) Czech: Pro<ccaron>prost<ecaron>nemluv<iacute><ccaron>esky
> >
> >    Unicode: U+0050 U+0072 U+006F U+010D U+0070 U+0072 U+006F U+0073
> >             U+0074 U+011B U+006E U+0065 U+006D U+006C U+0075 U+0076
> >             U+00ED U+010D U+0065 U+0073 U+006B U+0079
> >      ACE37: -p-r-o0bt-p r-o-s-twm-n-e-m-l-u-v0fm0f0-e-s-k-y (47 char)
> >    DUDE-02: vauctptyctzpctptnhtyrtzfmibtjd3mt8atyitgtitc (44 char)
> >
> >
> >    (I) Chinese
> >
> >    Unicode: U+4ED5 U+5011 U+7232 U+4EC0 U+9EBD U+4E0D U+8AAA U+4E2D
> >             U+6587
> >      ACE37: 7mmfm7oh3n7is3ts5gh57h47ata (27 char)
> >    DUDE-02: w85gt86huuudv69c7szp7s5a6w4h6w2hu54k (36 char)
> >
> >Chung & Leung                                                 [Page 14]
> >ACE37       ACE Utilizing All 37 Alphanumeric Characters      July 2001
> >
> >9. Summary & Comparisons
> >
> >    In summary, ACE37 is based on the DUDE-02 process with an improved
> >    compression scheme for code point sequences that are less likely to
> >    cluster too closely together, such as CJK ideographs.
> >
> >    Since it is the design team's indication that generally 30
> >    characters should be good enough and that there are a lot of concern
> >    from the Asian community that 14-15 characters is definitely
> >    limiting and that few indication from the Latin community that
> >    length is really a concern, ACE37 have set its objective to increase
> >    the possible number of characters in a worse case scenario closer to
> >    20 characters.
> >
> >    ACE37 have succeeded in creating a very simple variation based on
> >    the primary ACEs identified by the design team to create an ACE that
> >    achieves dramatically better performance for CJK characters while
> >    maintaining the simplicity of DUDE.
> >
> >    Key Improvements of ACE37 over DUDE-02
> >    - much more spacious for Han characters.  Improved worst-case
> >      scenario to 21 Han ideographs by introducing code block shifting
> >      and utilizing fully base-32 characters
> >    - no need to arbitrarily pre-pend flagging bits to identify code
> >      point brackets.  Instead base-4 characters and diff forms are used
> >    - base-32 and base-4 characters can be easily computed instead of
> >      mapped using lookup tables
> >
> >    Key Improvements of ACE37 over the AMC series
> >    - a more simple process, utilizing the one-pass differential
> >      mechanism from DUDE-02
> >    - a much more simple code block shifting process is used in ACE37 to
> >      achieve a similar goal for the complex multiple reference point
> >      system used by the AMC series
> >    - base-32 and base-4 characters can be easily computed instead of
> >      mapped using lookup tables
> >
> >    Key Improvements of ACE37 over LACE
> >    - a more simple process, utilizing the one-pass differential
> >      mechanism from DUDE-02
> >    - much more spacious for Han characters.  Improved worst-case
> >      scenario to 21 Han ideographs by introducing code block shifting
> >      and utilizing fully base-32 characters
> >    - base-32 and base-4 characters can be easily computed instead of
> >      mapped using lookup tables
> >
> >    Two Excel spreadsheet for ACE37 encoding and decoding can be found
> >    at http://www.dnsii.org/ace37/ace37-encode.xls and
> >    http://www.dnsii.org/ace37/ace37-decode.xls respectively.  This
> >    illustrates the simplicity of ACE37 and provides a handy tool for
> >    checking ACE37 encoding and decoding algorithms.  The ACE37-encode
> >    spreadsheet also includes a DUDE-encode worksheet.
> >
> >Chung & Leung                                                 [Page 15]
> >ACE37       ACE Utilizing All 37 Alphanumeric Characters      July 2001
> >
> >10. Security Considerations
> >
> >    This document does not talk about DNS security issues, and it is
> >    believed that the proposal does not introduce additional security
> >    problems not already existent and/or anticipated by adding
> >    multilingual characters to DNS and/or using ACE.
> >
> >11. References
> >
> >    [AMC-W]   Adam M. Costello, "AMC-ACE-W version 0.1.0", May 31, 2001.
> >
> >    [AMC-V]   Adam M. Costello, "AMC-ACE-V version 0.1.0", May 31, 2001.
> >
> >    [DUDE-02] Mark Welter, Brian W. Spolarich & Adam M.
> >              Costello, "Differential Unicode Domain Encoding (DUDE)",
> >              June 7, 2001.
> >
> >    [LACE]    Mark Davis, IBM & Paul Hoffman, IMC & VPNC, "LACE: Length-
> >              based ASCII Compatible Encoding for IDN", January 5, 2001.
> >
> >    [Nameprep]Paul Hoffman, IMC & VPNC & Marc Blanchet, ViaGenie,
> >              "Preparation of Internationalized Host Names", February
> >              24, 2001
> >
> >Appendix A. Acknowledgements
> >
> >    The ACE37 draft is a combination of DUDE-02, the AMC series and
> >    LACE, and takes into consideration the report of the ACE design
> >    team.  The authors would therefore like to thank the authors of
> >    DUDE-02 - Mark Welter, Brian W. Spolarich & Adam M. Costello; the
> >    authors of the AMC series - Adam M.Costello; the authors of LACE -
> >    Mark Davis & Paul Hoffman; and, the ACE design team and its advisors
> >    - Adam M. Costello, Paul Hoffman, Makoto Ishisone, David Laurence,
> >    Brian Spolarich, Rick Wesson, Marc Blanchet, Patrik Faltstrom and
> >    Erik Nordmark for their inspirations.
> >
> >Appendix B. Mixed-case annotation
> >
> >    This section is taken from DUDE and modified for ACE37
> >
> >    In order to use ACE37 to represent case-insensitive Unicode strings,
> >    higher layers need to case-fold the Unicode strings prior to ACE37
> >    encoding.  The encoded string can, however, use mixed-case base-4
> >    characters as an annotation telling how to convert the folded
> >    Unicode string into a mixed-case Unicode string for display
> >    purposes.
> >
> >    Each Unicode code point (unless it is an LDH) is represented by a
> >    sequence of base-4 and base-32 characters, the first of which is
> >    mostly a base-4 character, which is always a letter {wxyz} (as
> >    opposed to a digit).  If that letter is uppercase, it is a
> >    suggestion that the Unicode character be mapped to uppercase (if
> >
> >Chung & Leung                                                 [Page 16]
> >ACE37       ACE Utilizing All 37 Alphanumeric Characters      July 2001
> >
> >    possible); if the letter is lowercase, it is a suggestion that the
> >    Unicode character be mapped to lowercase (if possible).
> >
> >    If the code point is an LDH, for example "a", it will be represented
> >    as "-a".  To mark the case for an LDH, simply set the LDH to the
> >    desired case following the "-".  Fir example if an uppercase "A" is
> >    desired, the encoded form SHOULD be "-A".
> >
> >    Note that there is a possibility that no base-4 character is present
> >    for a code point representation.  That is the case for a 15-bit diff
> >    form.  In this case, the base-32 characters will be used for case
> >    suggestion (if possible), similar to that discussed for using a
> >    base-4 character.  However, also note that there is a very remote
> >    possibility that all 3 base-32 characters are digits.  If this
> >    happens, case unfolding will be aborted.  Since case annotation is
> >    an optional feature and used for display purposes only, this is not
> >    considered to be a major concern.  Moreover, the possibility of this
> >    happening is truly remote at only (32639/27)/1114109 or just 0.1%
> >    chance of happening.
> >
> >    ACE37 encoders and decoders are not required to support these
> >    annotations, and higher layers need not use them.
> >
> >    For example:  In order to suggest that example (H) in Section 8:
> >    "Examples" be displayed as:
> >    Czech: Pro<ccaron(uppercase)>prost<ecaron(uppercase)>
> >           nemLUV<iacute(lowercase)><ccaron(lowercase)>esky
> >
> >    one could capitalize the ACE37 encoding as:
> >      ACE37: -P-r-o0BT-p-r-o-s-tWM-n-e-m-L-U-V0fm0f0-e-s-k-y (47 char)
> >
> >Authors:
> >
> >Edmon Chung
> >Neteka Inc.
> >2462 Yonge St. Toronto,
> >Ontario, Canada M4P 2H5
> >[email-masked]
> >
> >David Leung
> >Neteka Inc.
> >2462 Yonge St. Toronto,
> >Ontario, Canada M4P 2H5
> >[email-masked]
> >
> >
> >
> >
> >
> >
> >
> >
> >
> >Chung & Leung                                                 [Page 17]
>

---

From: Marc Blanchet <[email-masked]>
Date: Thu, 05 Jul 2001 12:08:02 -0400

At/À 11:48 2001-07-05 -0400, Edmon you wrote/vous écriviez:
>Hi all,
>
>I was unaware that the workgroup no longer accepts new drafts.

see:

Message-Id: <[email-masked]>
Date: Tue, 26 Jun 2001 00:05:28 -0400
To: [email-masked]
From: Marc Blanchet <[email-masked]>
Subject: [idn] wg next steps

and:

Message-Id: <[email-masked]>
Date: Fri, 29 Jun 2001 08:06:14 -0400
To: [email-masked]
From: Marc Blanchet <[email-masked]>
Subject: [idn] document pools active

And, as I wrote in the email, you are _encouraged_ to submit as individual 
submission. The only difference is filename and no listing in the ietf idn 
wg charter web page.

Marc.

>   Anyway, I

---

From: "Edmon" <[email-masked]>
Date: Thu, 5 Jul 2001 14:32:41 -0400

Hi Marc,
Sorry about all the fuss about trying to submit this draft. Truly.

In any case, please refer to http://www.dnsii.org/idn-ace37-00.txt for my
draft on ACE37.  In essence, the following is what ACE37 tries to achieve.

   and Korean names.

I am truly excited about the idea and think that it provides a better
solution based on the findings of the ACE design team report.  Perhaps there
are still a number of holes in it, but I think the general direction: to
combine the primary ACEs in a DUDE mode, is a good way to go.

Edmon

---

From: "Soobok Lee" <[email-masked]>
Date: Fri, 6 Jul 2001 07:45:54 +0900

Hi,

When the diff value is less than 0xF, what is the ACE37 form for it ?

And any example C doe for ACE37  available on the web ?

Thanks.

Soobok

----- Original Message -----
From: "Edmon" <[email-masked]>
To: "Natalia Syracuse" <[email-masked]>; "David Leung"
<[email-masked]>; "Marc Blanchet" <[email-masked]>;
<[email-masked]>
Cc: <[email-masked]>
Sent: Friday, July 06, 2001 12:48 AM
Subject: [idn] Re: permission <draft-ietf-idn-ace37-00.txt (attach)

---

From: "Edmon" <[email-masked]>
Date: Thu, 5 Jul 2001 19:13:24 -0400

> Hi,
Great hearing from you.  Actually, I sh
ould give you some credit cause you sta
rted the codepoint reordering thing fir
st, though the ACE37 idea really came a
bout earlier than I saw your draft.  An
yway, I think my code block shifting me
chanism is much more simple and can suc
cessfully get 21+ han ideographs which
is much more acceptable than DUDE's cur
rent state.

> When the diff value is less than 0xF,
what is the ACE37 form for it ?
When diff<=0x7F it will be in the 7bit
form, that is
<b4><b32>

the reason <b4> has to be used is that
it signifies how many more characters a
re used for the particular codepoint (or
what I termed as codepoint bracket).  If
only a <b32> is used, then you wont know
whether it is a 15 bit form or a 22 bit
form.
Therefore, if diff=0xF, ACE37=wf

> And any example C doe for ACE37  avai
lable on the web ?
Not yet, David & I will work on it and
post it on the web if more people are i
nterested in the idea and think that it
could be better than DUDE.  For now you
can check out my excel worksheet to see
how it works. http://www.dnsii.org/ace3
7/ace37-encode.xls (for encoding), http
://www.dnsii.org/ace37/ace37-decode.xls
(for decoding).

Edmon

> > > >Chung & Leung
[Page 6]
> > > >    The following table explains
how base-4 characters are combined
> with
> > > >    base-32 characters to form a
representation of a diff (key:
> b4=base-
> > improved compression.  Worst case s
cenario CJK could have 21 han
> characters!
> > Attached below is a copy of the dra
ft (for my original submission), you
> can
> > then utilizes a simple code block s
hifting (similar to the reference
> points
> > in LACE) (DUDE and AMC-w/v uses bas
e-32 only for flagging).  In addition
> to
> > integrated version of the three pri
mary ACEs: DUDE, LACE and the AMC
> series,

---

From: "Adam M. Costello" <[email-masked]>
Date: Thu, 5 Jul 2001 23:18:37 +0000

Edmon <[email-masked]> wrote:

> Worst case scenario CJK could have 21 han characters!

That's assuming the encoded string can be up to 63 octets.  For IDNA
the limit is 59 octets, in which case ACE37 can support up to 19 Han
characters, same as several other ACEs (but better than DUDE's 15).

But I'm pretty sure that ACE37 is less efficient than DUDE for all
non-CJK scripts.

> All the while, the algorithm is kept to be as simple as DUDE.

It doesn't look as simple as DUDE to me.  To me it looks no simpler than
AMC-ACE-W, which is as efficient as ACE37 for CJK, as efficient as DUDE
for single-row scripts, and more efficient than DUDE for Latin-based
scripts.  Whereas AMC-ACE-W's complexity is in a state machine, ACE37's
complexity is in encoding/recognizing lots of different patterns.  I
know nothing about Excel (and do not have it), but maybe patterns are
easier than state machines in Excel, and maybe ACE37 appears simpler
than AMC-ACE-W when both are implemented in Excel.

By the way, I'm now in the process of tweaking AMC-ACE-Z, which is as
simple as AMC-ACE-W (if not simpler) and also more efficient.  A draft
will be coming soon, along with an evaluation of many ACE proposals.
Edmon, if you'd like to provide me with a C implementation of ACE37, I
can include it in the evaluation.  You are welcome (and even encouraged)
to use my example implementation of DUDE as a template.

AMC

---

From: "Edmon" <[email-masked]>
Date: Fri, 6 Jul 2001 11:54:53 -0400

> characters, same as several other ACEs (but better than DUDE's 15).

DUDE's support for 15 characters is also based on 63 octets. It would be 14
if it is 59 octets.

> But I'm pretty sure that ACE37 is less efficient than DUDE for all

Yup, there is a trade off definitely.  However, it seems that the CJK
community is more concerned about the issue so we should take this into
consideration when striking a balance.

> AMC-ACE-W, which is as efficient as ACE37 for CJK

AMC-ACE-W will not always achieve 19 characters with the 4 extra charcters
in front, whereas ACE37 will.

> Whereas AMC-ACE-W's complexity is in a state machine, ACE37's

True to an extent, but ACE37 operates under the same mode throughout,
similar to the DUDE concept.

> to use my example implementation of DUDE as a template.

Will do so asap.

Edmon

---

From: Maurizio Codogno <[email-masked]>
Date: Fri, 6 Jul 2001 18:07:52 +0200

In die Fri, 6 Jul 2001 11:54:53 -0400

> consideration when striking a balance.

Given that we may spare two strings to indicate ACE, would it be feasible
to use one for CJK scripts and another for the other scripts, making it 
impossible to use the wrong coding (this is necessary to assure unique 
labels), or do you think it is too complicated?

ciao, .mau.

---

From: "Adam M. Costello" <[email-masked]>
Date: Fri, 6 Jul 2001 22:13:06 +0000

Edmon <[email-masked]> wrote:

> DUDE's support for 15 characters is also based on 63 octets. It would
> be 14 if it is 59 octets.

I was basing it on 59 octets.  In the worst case, DUDE would require
60 octets for 15 Han characters, but the worst case virtually never
happens.  In the thousands of names that JPNIC tried, it never happened.
59 octets happened a few times, but I think the typical length was 58 or
57.  So DUDE can almost always support 15 characters, but usually cannot
support 16.  I think the boundary between "usually fits" and "usually
fails" is more useful than the "always fits" number.

AMC

---

From: "Edmon" <[email-masked]>
Date: Mon, 9 Jul 2001 09:08:10 -0400

One thing I forgot to point out:

From: "Adam M. Costello" <[email-masked]>
> complexity is in encoding/recognizing lots of different patterns.

DUDE uses a similar algorithm to determine the significance of diff, which
in turn determines how many b32 characters to use:

diff value                                    DUDE Form
----------------------------------------------------------------------------
diff<=0xF                                 <"0"+quartet>
0x10<=diff<=0xFF                  <"1"+quartet><"0"+quartet>
0x100<=diff<=0xFFF              <"1"+quartet><"1"+quartet><"0"+quartet>
0x1000<=diff<=0xFFFF
<"1"+quartet><"1"+quartet><"1"+quartet><"0"+quartet>
0x10000<=diff<=0xFFFFF
<"1"+quartet><"1"+quartet><"1"+quartet><"1"+quartet><"0"+quartet>
0x100000<=diff<=0x10FFFF
<"1"+quartet><"1"+quartet><"1"+quartet><"1"+quartet><"1"+quartet><"0"+quarte
t>

Here you see that there are 6 different scenarios as opposed to ACE37's 5
scenarios.  Both DUDE and ACE37 needs to determine the significant bits of
the resulting diff to come up with the correct form.  So perhaps it doesnt
look as simple (because I created these charts in the draft), but in effect
it is the same.  You could refer to the procedure comparison I did in my
draft in Section 1
<http://www.ietf.org/internet-drafts/draft-chung-idn-ace37-00.txt>

Edmon

---

From: "Edmon" <[email-masked]>
Date: Mon, 9 Jul 2001 18:14:53 -0400

> fails" is more useful than the "always fits" number.

I dont think this is very true for Chinese.  Most of the time, characters
would come from different rows causing DUDE to have to use 4 characters for
each Chinese ideograph.  In anycase, if you compare "usually fits" then
ACE37 should still out perform DUDE by a magnitude of at least 5 codepoints,
cause 19 codepoints is the "worst case" scenario (with the 59-octet limit),
but it is likely that it would "usually fit" 20-21 codepoints.  As in my
example with JPNIC in Japanese, it has 25 (>21) codepoints and ACE37 can
still handle it, whereas DUDE fails.

I think the point I am trying to make is that ACE37 greatly increases the
capacity for CJK ideographs, which has been identified as an undeniable
concern through the discussion on this mailing list, without requiring a
complex algorithm and utilizes the simplicity of DUDE.

Edmon

---

From: Paul Hoffman / IMC <[email-masked]>
Date: Mon, 9 Jul 2001 15:34:50 -0700

At 6:14 PM -0400 7/9/01, Edmon wrote:
>the
>concern through the discussion on this mailing list

The fact that a few people have expressed the concern without ever 
giving any evidence for it is not "undeniable". So far, there has 
been *no* evidence that a 15-character limit would restrict names 
that would be used for a significant number of real-live, 
actually-used host names. If you have any evidence to the contrary 
(that is, names that would actually be used in DNS names), please say 
so ASAP.

The concerns have all been for companies that want to register their 
legal names. Well, the DNS will *never* allow all the companies that 
want their legal names to do so. In the United States and throughout 
Europe, legal company names include spaces, commas, periods, 
apostrophes, ampersands, and so on. Those are not going to be allowed 
in IDN names, so those companies will not be able to register their 
legal names.

--Paul Hoffman, Director
--Internet Mail Consortium

---

From: "Adam M. Costello" <[email-masked]>
Date: Mon, 9 Jul 2001 23:04:09 +0000

Edmon <[email-masked]> wrote:

> I think the point I am trying to make is that ACE37 greatly increases
> the capacity for CJK ideographs

Yes, it certainly does (and also reduces the capacity for non-CJK
characters).

> without requiring a complex algorithm

I agree that the amount of complexity it adds to DUDE is not great, but
I think it's comparable to the amount of complexity that AMC-ACE-W adds
to DUDE.  DUDE does not have six different patterns, it has only one
pattern, because they're all handled by the same logic:

  To encode diff:

    for (tmp = diff >> 4, k = 1;  tmp != 0;  ++k, tmp >>= 4);
    out += k;
    output[out - 1] = base32[diff & 0xF];

    for (j = 2;  j <= k;  ++j) {
      diff >>= 4;
      output[out - j] = base32[0x10 | (diff & 0xF)];
    }

  To decode diff:

    /* invariant: c == input[in] */

    for (diff = 0;  ;  c = input[++in]) {
      q = base32_decode(c);
      if (q == base32_invalid) return dude_bad_input;
      diff = (diff << 4) | (q & 0xF);
      if (q >> 4 == 0) break;
    }

ACE37, on the other hand, must have separate logic for each pattern,
right?

By the way, I don't advocate AMC-ACE-W, because it's inferior to
AMC-ACE-Z, for which there will be a draft soon.

AMC

---

From: "Soobok Lee" <[email-masked]>
Date: Tue, 10 Jul 2001 09:35:46 +0900

This WG  should focus on issues of AVERAGE length of ACE lables.

We have not enough time for the debate around max ACE label length.
We have already many useful ACE alternatives 
to overcome this 14-han barrier easily.

bare DUDE produces  long and complex ACE lables for average length of
han/hangul domains, while DUDE's algorithm seems to be simple.
We have no justification for why we should sacrifice 
label simplicity for code simplicity, 
while we already have very HUGE mapping tables 
and algorithms in NAMEPREP and KC Norm.
ACE codes are written once and copied and executed many times.
Output label simplicity matters.

No one has provided the right reason 
to exclude needs for the following names. 
What does it GIVE us  to ban people from registering them?
What does ACE code simplicity give us ?

Soobok
--------------------------------------------------------------------

ONE EVIDENCE from Chinese Gov for domains of 16 han letters.

(SC1) Simplified Chinese String  1 : ( 16 letters )
      <ministry of foreign trade and economic cooperation, PRC>
      u+4e2d u+534e u+4eba u+6c11 u+5171 u+548c u+56fd u+5bf9
      u+5916 u+8d38 u+6613 u+7ecf u+6d4e u+5408 u+4f5c u+90e8

      DUDE-02 : w8wpt7ydt79euu4mv7yax9puzb7seu8r7wuq85umt27ntv2bv3wgt\
                5xe795e ( 60 chars )
      LDUDE   : xswjuzru6nu7fv7kv4gutrwgb7mbwiu6cuzqqxm
                ( 39 chars, 35.0% shorter )
      AMCW    : w8up29ps5kdst5uh7ygsup29pm3cb39n8tknpb39hkygswhdysupa\
                qd ( 55 chars )
      LAMCW   : xsujwxgu3kwwrv3fwvduunykm5ab9jwvmuwfmta
                ( 39 chars )

ANOTHER EVIDENCE from korean site names of 18 hangeul letters.

(K3) Korean String 3:  ( 18 hangul syllables )
      U+C804 U+AD6D U+C2E4 U+C9C1 U+B178 U+C219 U+C790 U+B300
      U+CC45 U+C885 U+AD50 U+C2DC U+BBFC U+B2E8 U+CCB4 U+D611
      U+C758 U+D68C

      DUDE-02 : 62yEyxyJy92J5uFz25JzvyBx2Jzw3Az9wFw6Ayx7Fy92Nz3uA3tEz8\
                xNt44FttwJtt7E ( 68 chars )
      LDUDE   : 5szAtBtvBt7Mt2Qv4Qu7KtFt5It3MuEvAtvDyJCtuC4G4J
                ( 46 chars,  32% shorter )
      AMCW    : 62sEFmpKzeNqbGm2Ks3M6sG2aPcfNefFksKy6I96GziPfwRstM42Rwn
                ( 55 chars )
      LAMCW   : 5stAsB5tvAGhmGmgG2mGatsE5t7JGbhsDvD5tsAyIK5swJ8RwG
                ( 50 chars )

Average lenght hangeul domain:

    (K4) Korean String 4:  ( 7 hangul syllables )
      <Hynics Semiconductor in korean>
      U+D558 U+C774 U+B2C9 U+C2A4 U+BC18 U+B3C4 U+CCB4        

      DUDE-02 : 7xvItuuNzx5PzsyPz85N97Nz9zA
                ( 27 chars )
      LDUDE   : 5s3C4F5Q7PtwRtMK
                ( 16 chars,  40% shorter )
      AMCW    : 7xxIM5wGyjKxeJa2G8ePfw
                ( 22 chars )
      LAMCW   : 5s9CxH8JvE5tzMyAK
                ( 17 chars )

---

From: Paul Hoffman / IMC <[email-masked]>
Date: Mon, 9 Jul 2001 20:51:16 -0700

At 9:35 AM +0900 7/10/01, Soobok Lee wrote:
>?This WG  should focus on issues of AVERAGE length of ACE lables.

That is an opinion. There has been a different opinion of many other 
people that the WG should focus on getting an algorithm good enough 
for the vast majority of likely names. If you think the discussion 
needs to be opened again, you should speak with the WG chairs. 
However, you need to be much more specific than saying "AVERAGE".

There are three kinds of averages (mean, median, and mode); of those, 
clearly we do not want to consider mode. How do you intend to measure 
either mean or median? All of the ACEs proposed so far have different 
means and medians for different scripts. They also have different 
means and medians for names that contain characters from only one 
script versus names that contain characters from two (such as names 
that are based on a non-Latin script but use Latin hyphens or digits).

>We have not enough time for the debate around max ACE label length.

It seems like nine months is plenty of time. Could you say how much 
longer you think is appropriate?

>       u+5916 u+8d38 u+6613 u+7ecf u+6d4e u+5408 u+4f5c u+90e8

Two questions:
- Do you expect them to actually use that name? Or would they instead 
use one that is easier to remember?

- Why would they use "PRC" at the end if this name will be in the .cn 
TLD or, hopefully, in the TLD that will express the name "China" in 
the Chinese language?

As for the new subject line, it is difficult to see how a wide 
consensus moving forwards is "derailed". If we were at a technical 
impasse, that could be considered derailment, but certainly doesn't 
described the WG as it stands now.

--Paul Hoffman, Director

---

From: Keith Moore <[email-masked]>
Date: Tue, 10 Jul 2001 00:37:27 -0400

> This WG  should focus on issues of AVERAGE length of ACE lables.

why?  do you have some evidence that this has a significant
effect on performance of ANY protocol?

---

From: "Soobok Lee" <[email-masked]>
Date: Tue, 10 Jul 2001 13:59:43 +0900

I am not sure  what you mean by "significant" effect.

I think shorter ACE labels benefits  :

 1. save momory resources
     shorter IDN zone file
     save memory space of  intermediate DNS/Web cache servers
     shorter log file for dns/web/mail transactions
     shorter Http cookie cache entries 

 2. reduce traffic
    shorter DNS queries
    shorter HTTP host: header value
    shorter SMTP session from to:  and rcpt to: tags
    
 3. for human
    more easy to transcript
    good for administrators to manage leaked ACE labels
    registrants cannot avoid ACE labels now and near future

For, <Samsung Electronics  in Korean> ( 4 hangul syllables)

U+C0BC U+C131 U+C804 U+C790

DUDE-02  : 6s7Nt2P3vF93E      13       
LDUDE     : 5s7AB4BB             8 ( 5 chars, 38% shorter )

<Hyundai  Develpoment Company in Korean> ( 6 syllables)
U+D604 U+B300 U+C0B0 U+C5C5 U+AC1C U+BC1C

DUDE-02  : 7yyEyxsEzv5AxzFy37JtssA    ( 23 )
LDUDE     : 5syMRtAB3FB                      11 ( 12 chars, 52% shorter )

---

From: Keith Moore <[email-masked]>
Date: Tue, 10 Jul 2001 01:01:38 -0400

> I am not sure  what you mean by "significant" effect.

I mean the burden is on you to demonstrate that it's worth
the trouble that would be required to further reduce the 
average length of label representation, and you haven't yet
provided any support for this argument.

the question is not whether there are benefits, the question
is whether they are worth the extra complexity and overhead,
and the additional delay in getting IDNs out the door.

Keith

---

From: "Soobok Lee" <[email-masked]>
Date: Tue, 10 Jul 2001 14:50:59 +0900

We already have ACE alternatives ** NOW **.

How much time  do you expect  to be taken
in order to improve or replace DUDE ?
1 week or 1 month of delay?  That's too long to wait for?

Can you demonstrate  whom  and how much
code simplicity  benefits ?  ACE codes are compiled into
binary codes in *HUGE* NAMEPREP & KC Norm libraries.

soobok

----- Original Message ----- 
From: "Keith Moore" <[email-masked]>
To: "Soobok Lee" <[email-masked]>
Cc:<[email-masked]>; "Paul Hoffman / IMC" <[email-masked]>
Sent: Tuesday, July 10, 2001 2:01 PM
Subject: Re: [idn] THis WG derailed ?

---

From: Martin Duerst <[email-masked]>
Date: Tue, 10 Jul 2001 15:07:15 +0900

>     shorter SMTP session from to:  and rcpt to: tags

Can you give an estimate of what percentage of overall transfer/
storage will be for Hangul/Han domain names? I'm very sure this
is extremely low, also because the average Han/Hangul names will
be quite short.

>     registrants cannot avoid ACE labels now and near future

I consider that a good reason against any kind of ACE.
It doesn't, in my opinion, give any reason for any kind
of length arguments. If administrators ever have to deal
with ACE (I very much hope they don't), they will do that
by cut/copy/paste, where length is rather irrelevant.

Regards,    Martin.

---

From: "Soobok Lee" <[email-masked]>
Date: Tue, 10 Jul 2001 15:39:56 +0900

Please don't worry about my strong-worded subject  "...derailed".

DUDE , in a  case, supports up to 56 han/hangeul letters
in a label (a letter repeated 56 times). if anyone ever registers it,
the median average becomes 28. Let's ignore it.

Both mean (weighted) average and mode (most frequent value) 
average are not relevant to our works, i think.  

What I mean by "average domains", is  that we should
consider overall compression efficiency for samples of 
various lengths of domains that are likely to be registered, 
not only for *rare* marginal cases of very long domains which
can mislead us to lose our right focus. That's the point.
 
And many useful DUDE-alternatives are not expensive.
Lengthy tables do not add complexity, but only require 
time for careful evaluation and preparations as that for 
nameprep and kc norm.

Soobok

---

From: Marc Blanchet <[email-masked]>
Date: Tue, 10 Jul 2001 09:27:07 -0400

changed to subject to a more appropriate one!

>This WG  should focus on issues of AVERAGE length of ACE lables.

Don't understand why. Average number of octets doesn't help me.
However, the max length do change the maximum length of chars that I may use.

I probably don't understand your point.

Marc.

---

From: Keith Moore <[email-masked]>
Date: Tue, 10 Jul 2001 09:24:22 -0400

> 1 week or 1 month of delay?  That's too long to wait for?

Based on long experience with IETF working groups, if people
don't like the idea almost immediately, the additional time
spent debating the details can require six to eighteen months.
I'm not exaggerating.  Groups get very slow after they've been
around a while.

and yes, that's too long to wait.

---

From: Dave Crocker <[email-masked]>
Date: Tue, 10 Jul 2001 08:02:39 -0400

>I think shorter ACE labels benefits  :

#1 and #2 are correct, theoretically but not practically.  That is, it is 
valid to claim that one string being a single character shorter than 
another character can save resources.  However practical system behavior 
will show no measurable difference between the two.

In fact there is a very strong argument which says that packet- or 
datagram-oriented systems are entirely dominated by the overhead of 
processing a data segment, rather than the length of the segment.

>   3. for human

All of the proposed encoding schemes are horrible for humans.

d/

----------
Dave Crocker  <mailto:[email-masked]>
Brandenburg InternetWorking  <http://www.brandenburg.com>
tel +1.408.246.8253;  fax +1.408.273.6464

---

From: "Edmon" <[email-masked]>
Date: Tue, 10 Jul 2001 16:50:52 -0400

> Yes, it certainly does (and also reduces the capacity for non-CJK

Agreed.  From the discussions here however, it seems that CJK capacity is of
more concern than non-CJK.  I have heard quite a few raise the issue that 15
characters for CJK is not enough, but I think generally, non-CJK having ~30
codepoint capacity is ok.  Also this was suggested by the ACE design team.

> pattern, because they're all handled by the same logic:
Yes, I agree that there is an amount of complexity added to DUDE, and you
also agree that the amount is small.
Additionally, ACE37 maintains the one-mode system that I think is comparably
less complex than a separate state machine that is required by AMC-ACE-W.

Edmon

---

From: "Adam M. Costello" <[email-masked]>
Date: Tue, 10 Jul 2001 20:55:16 +0000

Edmon <[email-masked]> wrote:

> Additionally, ACE37 maintains the one-mode system that I think is
> comparably less complex than a separate state machine that is required
> by AMC-ACE-W.

Then you will like AMC-ACE-Z better than AMC-ACE-W, because it is
a one-mode system with fewer state variables.  Compared to ACE37,
AMC-ACE-Z is more subtle but requires less code to implement (I think),
is equally efficient for Han, and much more efficient for all other
scripts.

http://www.cs.berkeley.edu/~amc/charset/amc-ace-z.gz

I'm in the process of cleaning up the presentation.  I'll submit an
internet draft soon.

AMC

---

From: "James Seng/Personal" <[email-masked]>
Date: Wed, 11 Jul 2001 14:16:33 +0800

As with all compression algorithm, there is an 'entropy' which is the
mininum length (or max compression) you can achieve by eliminating extra
information. Beyond that, you can achieve better compression for some
particular string by causing other strings to expand, ie, you have two
set: compressed strings and expanded strings. It is a give-and-take.

Thus, the idea is that if we do have a compression algorithm, then we
want to have the more oftenly occured string to be in the compressed
set. Thus, an rearrangment algorithm like LSB which basically rearrange
the certain characters so that it can be compressed better is generally
a good idea.

OTOH, we do not know whether this rearragement will produce better
compression in the long run. It may turn out that those strings which
falls in the expanded strings set is more oftenly used in future.

There is always a holy grail of compression. And we could spend donkey
years arguing over it and never get to our goal, ie, IDN. Lets not
forget that and hopefully we can get IDN in a timely fashion.

-James Seng

---

From: "James Seng/Personal" <[email-masked]>
Date: Thu, 12 Jul 2001 20:34:28 +0800

There are approximately 2000 very commonly used chinese characters which
we will learn by primary school. a typical chinese can survive day to
day knowing about 4000 to 5000 han ideograph. I believe it is the
similar with Korean and Japanese. Not all ideograph are equal.

But my experience ends here. I am not sure if it is applicable to other
scripts or how it should be. OTOH, there aint many scripts which used
more than 255 block like CJK.

-James Seng

----- Original Message -----
From: "Martin Duerst" <[email-masked]>
To: "Soobok Lee" <[email-masked]>; "James Seng/Personal"
<[email-masked]>; <[email-masked]>
Sent: Thursday, July 12, 2001 6:07 PM
Subject: Re: [idn] Re: ave length, best compression etc

> At 10:31 01/07/12 +0900, Soobok Lee wrote:
>
> >The most frequent 256 Han letters has cumulative frequency sum
> >     of 58.2% and for the cases of top 512,1024,2048 and 4096 ones,
> >     it reaches 72.8,85.9,95.4 and 99.4%, respectively.
> >    4096 is roughly close to the size of Simplified Chinese Character
sets.
>
> By the way, how do you weight simplified, traditional, Japanese,
> and Korean when they use different codepoints?
>
> Regards,   Martin.
>

---

From: Martin Duerst <[email-masked]>
Date: Thu, 12 Jul 2001 19:07:50 +0900

At 10:31 01/07/12 +0900, Soobok Lee wrote:

>    4096 is roughly close to the size of Simplified Chinese Character sets.

Regards,   Martin.

---

From: "Soobok Lee" <[email-masked]>
Date: Thu, 12 Jul 2001 22:19:41 +0900

First 512 (or more) letters in my reordering table were
manually chosen from frequent business category names
and region names in taiwan/china/japan.
They are placed to reflect word adjacencies.
SC/TC pairs are placed together in this 512 letters.

For ordering of other letters following the first 512 ones,
I merged two relative letter frequency distribution data sets with 
SC:TC=1:1 weight allocation ( excluding the first 512 letters).

a SC letter and its TC counterpart (and even Kanji counterpart)
should have been treated as one letter and placed together, 
but not in my current reordering table  which therefore
might favor the common letters of SC and TC character sets
over SC-only and TC-only letters. 
 
I am reading CNNIC-submitted draft on SC/TC
tranformation , which is a good source of  TC/SC pairs
for my next version of reordering tables.

Regards,

Soobok

----- Original Message -----
sets.