[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[idn] comments on draft-ietf-idn-brace-00.txt
- To: "Adam M. Costello" <amc@cs.berkeley.edu>
- Subject: [idn] comments on draft-ietf-idn-brace-00.txt
- From: James Seng <James@Seng.cc>
- Date: Mon, 18 Sep 2000 02:10:24 +0800
- Cc: idn@ops.ietf.org
- Delivery-date: Sun, 17 Sep 2000 11:15:57 -0700
- Envelope-to: idn-data@psg.com
My comments are scattered in the draft in [JS:]
Reading it is difficult and confusing. (I feel like I am reading computer
codes :p) the requirement to maintain 3-4 separate stream is also scarely
(input buffer, output, LDH buffer, and bit queue) and while going thru, i
wonder if anything could go wrong...but of cos, I found none :)
In general, seem like a good ACE, with better compression than RACE. I suggest
reading up UTR#6 for more inspiration on Unicode compression :-)
For those who wish read more on compression, Ross Neil Williams' thesis
"Adaptive Data Compression" is a excellent start. Another book for beginner on
common compression is "The Data Compression Book" by Mark Nelson.
ps: If I make any mistake, feel free to shot me. i doing this on the plane
with my linux not operational => cant test the codes. *sigh*
-James Seng
[JS: Suggest to number your content so for easy discussion]
1. Design Goals of BRACE
1.1 Primary goals
Efficient encoding: Small ratio of encoded size to original size,
for all UTF-16 strings.
Uniqueness: Every UTF-16 string maps to at most one label.
Completeness: Every UTF-16 string maps to a label, provided it is
not too long. Restrictions on which UTF-16 strings are allowed is
purely a matter of policy.
Degeneration: All valid host name labels that do not end with the
BRACE signature "-8Q9" (or "-8q9") are the BRACE encodings of their
own UTF-16 representations.
1.2. Secondary goals
Conceptual simplicity: This has been somewhat compromised for the
sake of efficient encoding.
Readability: ASCII letters and digits in the original string are
represented literally in the encoded string. This comes for free
because it is the most efficient encoding anyway.
2. Overview
The encoded string alternates between two modes. ASCII letters,
digits, and hyphens in the Unicode string (which will henceforth be
called LDH characters) are encoded literally, except that hyphens
are doubled. Non-LDH codes in the Unicode string are encoded
using base-32 mode, in which each character of the encoded string
represents five bits. Single hyphens in the encoded string indicate
mode changes.
The base-32 mode uses exactly one of four styles. Half-row style is
used for Unicode strings in which all the non-LDH codes belong to
a single half-row (have the same upper 9 bits). Full-row style is
used for Unicode strings in which all the non-LDH codes belong to a
single row (have the same upper 8 bits) but not all the same half.
Mixed style is used when when many of the non-LDH characters (but
not all of them) belong to the same row. No-row style is used for
all other strings.
3. Base-32 characters
[JS: Rearranged to save some space..:-)]
"2" = 0 = 00000 "A" = 8 = 01000 "I" = 16 = 10000 "S" = 24 = 11000
"3" = 1 = 00001 "B" = 9 = 01001 "J" = 17 = 10001 "T" = 25 = 11001
"4" = 2 = 00010 "C" = 10 = 01010 "K" = 18 = 10010 "U" = 26 = 11010
"5" = 3 = 00011 "D" = 11 = 01011 "M" = 19 = 10011 "V" = 27 = 11011
"6" = 4 = 00100 "E" = 12 = 01100 "N" = 20 = 10100 "W" = 28 = 11100
"7" = 5 = 00101 "F" = 13 = 01101 "P" = 21 = 10101 "X" = 29 = 11101
"8" = 6 = 00110 "G" = 14 = 01110 "Q" = 22 = 10110 "Y" = 30 = 11110
"9" = 7 = 00111 "H" = 15 = 01111 "R" = 23 = 10111 "Z" = 31 = 11111
The digits "0" and "1" and the letters "O" and "L" ("l") are not
used, to avoid transcription errors.
The base-32 characters, like all characters in host name labels, are
case-insensitive, so they must be recognized in both upper and lower
case. However, since existing LDH labels are usually stored in
lower case, it is recommended that the base-32 portions of encoded
names be stored in upper case, to help humans easily pick out the
literal portions.
[JS: Suggest to remove above paragraph as it contains generalization.
Beside, BRACE should be case-insensitive.]
4. Encoding procedure
If the UTF-16 string contains more than 63 16-bit codes, it's too
long, so abort.
[JS: It is probably bad idea to check here. Since compression is
involved, you may want to look at the output string before determining
if it is too long. Beside, there are other ways to work around this,
for example, defining a concating sequence. e.g. "X." as a concat so
a long domain names A can become BRACE1X.BRACE2 which is valid]
If the upper bytes are all zero, and the string formed by the lower
bytes is a valid host name label and does not end with "-8Q9" or
"-8q9", output the low bytes and stop.
[JS: If all upper bytes are all zero, it is not sufficient to determine
it is a valid hostname. And it is inconsistent with your -> $1.00 <-
example. I also recommend that you define the tag "-8Q9" as a separate
place saying that it is subjected to changes in future.]
[JS: Your description while good, it is too specific on the algorithm.
It is probably more appropriate to describe the encoding then to give
the algorithm. I-D should give specification but not restrict how
implementation is done. Hence, I recommend to change the section below
to reflex this. And it will also make the I-D much easier to read and
understand. Same for Decoding :-)
I also suggest putting the selection of encoding style before the algo
so people are aware of the different method of encoding and how to shift
bit and how many bits to shift into the queue.]
The encoder needs a bit queue capable of holding up to 22 bits, a
buffer of LDH characters capable of holding up to 124 characters,
and a 4-value encoding style indicator. The LDH buffer is initially
empty. The initial contents of the bit queue, and the value of the
style indicator, depend on which encoding style is chosen (which
is explained below). Bit strings are enqueued and dequeued in
big-endian order (most significant bit first).
After choosing the style and initializing the bit queue, perform the
following actions:
while the bit queue contains at least 5 bits
dequeue 5 bits
output the corresponding base-32 character
endwhile
for each 16-bit code of the UTF-16 string (in order) do
if the code is 0x002D ("-", ASCII hyphen) then
append two hyphens to the ASCII buffer
[JS: I presumed you mean LDH buffer?]
else if the code is an LDH character then
if the LDH buffer contains no non-hyphens then
append one hyphen to the LDH buffer
endif
append the code to the LDH buffer
else (the code is not an LDH character)
if the LDH buffer contains any non-hyphens then
append one hyphen to the LDH buffer
endif
if the bit queue is empty then
output the LDH buffer and reset it to empty
endif
enqueue the bit string corresponding to the code
(the bit string depends on the encoding style)
dequeue 5 bits
output the corresponding base-32 character
output the LDH buffer and reset it to empty
while the bit queue contains at least 5 bits
dequeue 5 bits
output the corresponding base-32 character
endwhile
endif
endfor
if the bit queue is not empty
enqueue zero bits until it contains 5 bits
dequeue 5 bits
output the corresponding base-32 character
endif
output the LDH buffer
output the LDH characters "-8Q9"
If the total number of characters output was greater than 63, the
string is too long for a host name label.
Notice that a group of LDH characters appears in the output as soon
as all the bits of the preceeding non-LDH codes have appeared. The
base-32 character that appears just before the switch to literal
mode may contain at most four bits of information from the first
non-LDH character that comes after the LDH group.
5. Encoding styles
The choice of encoding style depends only on the codes in the UTF-16
string that are not LDH characters. It in no way depends on any LDH
codes that may be present.
Each code belongs to a particular half-row, which is given by its
upper 9 bits. If all of the non-LDH codes belong to the same
half-row, use half-row style: Initialize the bit queue by enqueuing
two 0 bits followed by the designated half-row number (the 9-bit
half-row number shared by all the codes). During the encoding
procedure the bit string corresponding to each code is its lower 7
bits.
If not all the non-LDH codes belong to the same half-row, but they
all belong to the same row (same upper 8 bits), use full-row style:
Initialize the bit queue by enqueuing a 0 bit, then a 1 bit, then
the designated row number (the 8-bit row number shared by all the
codes). During the encoding procedure the bit string corresponding
to each code is its lower 8 bits.
If not all non-LDH codes belong to the same row, then consider
using mixed style, which chooses a priviledged half-row. For each
half-row used by the non-LDH codes, count the number of codes that
belong to that half-row. Then, for each half-row, calculate M, the
number of base-32 characters that would be required if that half row
were chosen:
N = total number of non-LDH codes
H = number of non-LDH codes in the candidate half-row
C = number of non-LDH codes in the complementary half-row (the
one with the opposite lowest bit)
M = (2 + 9 + 18*(N - H - C) + 8*H + 9*C + 4) / 5
= 3 + (18*N - 10*H - 9*C) / 5
[JS: An explaination of how you arrive with the formula would be nice.
e.g. 2bit for encoding style, 9bit for half-row, N - H - C gives number
of uncompressed char taking 2+16bit each, half-row char take 1+7 bit each,
and complementary half-row takes 2+7 bit each and +4 to round up.]
(The division is integer division, which discards any remainder.)
Choose the half-row with the smallest M, breaking ties in favor of
lower-numbered half-rows. Compare this M with M', the number of
base-32 characters that would be required if no-row style were used:
M' = (2 + 16*N + 4) / 5 = (6 + 16*N) / 5
[JS: 2 bit for encoding style, 16bit for each character. +4 to round up]
[Shouldnt it be If M' <= smallest(M)]
If M' <= M, use no-row style: Initialize the bit queue by
enqueueing two 1 bits. There is no designated row number. During
the encoding procedure the bit string corresponding to each code is
the full 16-bit code itself.
If M < M', use mixed style: Initialize the bit queue by enqueueing
a 1 bit, then a 0 bit, then the designated 9-bit half-row number
(the one chosen above). During the encoding procedure the bit
string corresponding to each code is:
0 followed by the lower 7 bits if the code belongs to the chosen
half-row;
10 followed by the lower 7 bits if the code belongs to the
complementary half-row;
11 followed by the whole 16-bit code otherwise.
6. Decoding procedure
The following description assumes that UTF-16 output is desired.
If the input string does not end with "-8Q9" or "-8q9", output the
input string (converted from ASCII to UTF-16) and stop.
The decoder needs a bit queue capable of holding up to 22 bits. It
is initially empty. It also needs a literal-mode flag, which is
initially unset, and a 4-value style indicator.
Perform the following actions:
read the first character and enqueue its base-32 quintet
dequeue two bits and use them to set the style indicator
if the style uses a designated full/half row number then
while the queue does not contain enough bits to represent it
read the next character and enqueue its base-32
endwhile
dequeue enough bits to set the designated row (or half-row)
endif
for each remaining input character except the last four do
if the character is an ASCII hyphen then
if the next character is also an ASCII hyphen then
skip it
output an ASCII hyphen (converted to UTF-16)
else
toggle the literal-mode flag
endif
else if the literal-mode flag is set then
output the character (converted to UTF-16)
else (the literal-mode flag is clear)
enqueue the character's base-32 quintet
if the bit queue contains enough bits to represent a
UTF-16 code (which depends on the style indicator)
then
dequeue just enough bits to represent one code
output the code
endif
endif
endfor
At the end the bit queue may contain up to four 0 bits. If it
contains anything else, the input was invalid.
7. Comparison with RACE
BRACE is an extension of RACE [RACE01]. For Unicode strings
that contain no LDH characters and use the full-row or no-row
encoding styles, BRACE is virtually identical to RACE. For other
strings, BRACE produces a smaller encoding than RACE. For example,
the encoding is substantially more compact for Unicode strings
containing a substantial number of LDH characters, or containing
many Japanese kana with some kanji.
Unlike RACE, any LDH characters present in the Unicode string are
represented literally in the BRACE-encoded string. This may or may
not be useful, but it happens to be the most compact way to encode
LDH characters.
Whereas RACE uses a signature prefix, BRACE uses a signature suffix.
This makes it easy to guarantee that the encoded label never ends
with a hyphen, even if the original UTF-16 string does. (Whether
such a UTF-16 string should be allowed is a matter of policy, not
technical capability).
The main drawback of BRACE is its greater complexity.
[JS: Recommand to do a theorical comparsion as follows:
Given a UTF-16 string with X character:
a) If X can be encoded in half-row,
RACE = (8 + X*8 + 4)/5 = (12 + X*8)/5
BRACE = (2 + 9 + X*7 + 4) / 5 = 3 + (X*7)/5
RACE = BRACE when X<7 and BRACE become better when X>7
b) If X can be encoded in full-row,
RACE = (8 + X*8 + 4)/5 = (12 + X*8)/5
BRACE = (2 + 8 + X*8 + 4)/5 = (16 + X*8)/5
RACE is better.
c) If X cannot be compress
RACE = (8 + X*16 + 4)/5 = (12 + X*16)/5
BRACE = (2 + X*16 + 4)/5 = (6 + X*16)/5
BRACE is better.
d) If X contains LDH (Y) but the non-LDH can be encoded in half-row,
RACE = (8 + Y*16 + (X-Y)*8 + 4)/5 = (12 + X*8 + Y*8)/5
BRACE compression of LDH is more complex, depending on the LDH.
Best case is when Y is LD and in sequence, BRACE is Y+2
Worst case is when Y has alternate '-', BRACE is Y*2 + 2
BRACE = (2 + 9 + (X-Y)*7 + 4)/5 + 2 + (Y to Y*2)
Best case = 5 + (X*7 - Y*2)/5
Worst case = 5 + (X*7 + Y*3)/5
For latin script, in the worst case, BRACE become better when Y>4.
For non-latin script but contain LDH, BRACE is better generally.
e) If X contains LDH (Y) but the non-LDH can be encoded in full-row,
same treatment as above:
RACE = (8 + Y*16 + (X-Y)*8 + 4)/5 = (12 + X*8 + Y*8)/5
BRACE = (2 + 8 + (X-Y)*8 + 4)/5 + 2 + (Y to Y*2)
Best case = (24 + X*8 - Y*3)/5
Worst case = (24 + X*8 + Y*2)/5
For latin script, in the worst case, BRACE become better when Y>4.
For non-latin script but contain LDH, BRACE is better generally.
f) If X can be compressed by BRACE but not by RACE (when characters comes
from two or more rolls such as CJK), BRACE is better generally.
Would be better there are real data comparing the two algo]
8. Example strings
All of these examples use Japanese text, merely because that is the
only kind of non-English text that the author has lying around.
Example of no-row style:
An actual music group name coerced into the usual format for
host name labels:
AMURONAMIE-with-super-monkeys
AMURONAMIE stands for five kanji whose Unicode values are (in
order):
U+5B89 U+5BA4 U+5948 U+7F8E U+6075
The BRACE encoding is:
UVJ7FUAQCAHY982XA---with--super--monkeys-8Q9
(Note that the RACE encoding would have been 79 characters long,
and hence unusable.)
Example of mixed style:
An actual song title coerced into the usual format for host name
labels:
hello-another-way-SOREZORENOBASHO
SOREZORENOBASHO stands for five hiragana followed by two kanji,
whose Unicode values are (in order):
U+305D U+308C U+305E U+308C U+306E U+5834 U+6240
The BRACE encoding is:
JI7-hello--another--way---V3JHAEFVD2UFJ62-8Q9
Example of full-row style:
An actual song title, SONOSUPIIDODE, which stands for two
hiragana followed by four katakana followed by one hiragana,
whose Unicode values are:
U+305D U+306E U+30B9 U+30D4 U+30FC U+30C9 U+3067
The BRACE encoding is:
BIDPRDMP9WT7MI-8Q9
Example of half-row style:
An actual song title:
PAFIIdeRUNBA
PAFII stands for four katakana whose Unicode values are:
U+30D1 U+30D5 U+30A3 U+30FC
RUNBA stands for three katakana whose Unicode values are:
U+30EB U+30F3 U+30D0
The BRACE encoding is:
3IU8PAZT-de-PYGI-8Q9
Example of an ASCII string that breaks all the rules of host name
labels:
[JS: Take note of the inconsistency with the algo]
-> $1.00 <-
The BRACE encoding is:
229--T2B4-1-W-00-I9I---8Q9
9. Security considerations
Users expect each host name in DNS to be controlled by a single
authority. If a UTF-16 string could map to multiple labels, then
a UTF-16 host name could map to multiple real host names, each
controlled by a different authority, some of which could be spoofs
that hijack service requests intended for another. Therefore BRACE
is designed so that each UTF-16 string maps to a unique label.
However, there can still be multiple UTF-16 representations
of the "same" text, for various definitions of "same". This
problem is addressed by the Unicode standard under the topic of
canonicalization, but the issue needs to be studied further in the
context of host names.
Also, some text strings may be misleading or ambiguous to humans,
such as strings containing dots, slashes, at-signs, etc. Policies
for allowable Unicode strings need to be developed.
10. References
[IDN] Internationalized Domain Names (IETF working group),
http://www.i-d-n.net/, idn@ops.ietf.org.
[RACE01] Paul Hoffman, "RACE: Row-based ASCII Compatible Encoding
for IDN", 2000-Aug-31, draft-ietf-idn-race-01.
[RFC952] K. Harrenstien, M. Stahl, E. Feinler, "DOD Internet Host
Table Specification", 1985-Oct, RFC 952.
[RFC1034] P. Mockapetris, "Domain Names - Concepts and Facilities",
1987-Nov, RFC 1034.
[RFC1123] Internet Engineering Task Force, R. Braden (editor),
"Requirements for Internet Hosts -- Application and Support",
1989-Oct, RFC 1123.
[SACE] Dan Oscarsson, "Simple ASCII Compatible Encoding (SACE)",
draft-ietf-idn-sace.
[UNICODE] The Unicode Consortium, "The Unicode Standard",
http://www.unicode.org/unicode/standard/standard.html.
[UTF5] James Seng, Martin Duerst, Tin Wee Tan, "UTF-5, a
Transformation Format of Unicode and ISO 10646", draft-jseng-utf5.
11. Author
Adam M. Costello <amc@cs.berkeley.edu>
http://www.cs.berkeley.edu/~amc/
Appendix: Example implementation
[snip]
INTERNET-DRAFT expires 2001-Mar-14