internationalization.html [plain text]
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<!-- warning this is a UTF-8 file. please don't pretend it's ISO-8859. -->
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta name="revision"
content="$Id: internationalization.html,v 1.7 2003/10/22 18:50:05 rjs3 Exp $" />
<meta name="author" content="Larry Greenfield" />
<title>internationalization</title>
</head>
<body>
<h1>charset code</h1>
<h2>introduction</h2>
<p>Cyrus currently transcodes characters to a canonical UTF-8 form for
searching. The base spec of IMAP4 only requires understanding multiple
character sets to properly implement SEARCH. Since the base spec came
out, several extensions have been proposed that require further
charset support: SORT, THREAD, and the Sieve subsystem. As of this
writing, Cyrus doesn't correctly support these other commands.</p>
<p>Cyrus currently only believes in 16-bit characters. Technically,
Unicode has up to 21-bit characters (expressible in UTF-16 and 3-byte
UTF-8) and ISO 10646 allows up to 31-bit characters (though ISO's
current policy is to not allocate any characters outside of the 21-bit
Unicode range). The lower 16-bit characters make up the basic
multilingual plane (BMP) where the majority of languages live. This
restriction is apparent in <tt>charset.c:writeutf8()</tt>, the UTF-8
decoders, and the Unicode canonicalization table used by Cyrus. Since
Cyrus's known character sets (except for UTF-8) don't contain any
characters off of the BMP this isn't seen to be a major problem.</p>
<p>Throughout this text, Unicode and ISO 10646 will be used
interchangible to refer to the 16-bit character set of the BMP,
regardless of encoding. "Character", unless otherwise specified,
refers to a single Unicode character <tt>ffff</tt> or under. </p>
<h2>cyrus canonical form</h2>
<p>Since when users search e-mail messages it's much easier for them
to eliminate false positives than realize there are hits that aren't
displayed, the Cyrus searching algorithm errs on the side of more
matches. Before comparing any two strings, Cyrus puts them in a
canonical form. Logically, the process works as follows:</p>
<ul>
<li> the input string is translated into a sequence of Unicode
characters. </li>
<li> each character is transformed into lowercase. (For some
characters, a single uppercase character may transform into multiple
lowercase characters.) </li>
<li> each character is fully decomposed. </li>
<li> all whitespace (Unicode general categories starting with
<tt>Z</tt>) is removed. </li>
<li> combining diacritical marks, such as the accent on é, are
removed. (These are Unicode characters <tt>0300</tt>-<tt>03ff</tt>.)
</li>
<li> certain characters are expanded to alternative spellings using
ASCII characters, such as "æ" to "ae". </li>
<li> the output characters are then encoded in UTF-8. </li>
</ul>
<p>The actual transcoding does all of these steps at once with the aid
of tables, carefully built at compile-time.</p>
<p>The central part of Cyrus's internationalization support is it's
transcoding routines in <tt>lib/charset.[ch]</tt>, and
<tt>lib/chartable.[ch]</tt>. Cyrus's transcoding routines are very
elegant and very compact, thus somewhat intimidating. During
compilation, Cyrus builds up a large number of tables (see <a
href="#mkchartable">mkchartable</a>) and uses them so that it never
has to consider more than a single octet at a time while outputing the
Cyrus canonical form for an input string.</p>
<h2>external interface</h2>
<p>
<tt>lib/charset.h</tt> is the public interface for Cyrus lib clients
to get character canonicalization and searching support. In contains
the following functions:</p>
<dl>
<dt><tt>char *charset_convert(const char *s, int charset, char *buf,
int bufsz)</tt></dt>
<dd> Given a string <i>s</i> in charset <i>charset</i>, decode it into
canonical form in <i>buf</i>. <i>buf</i> must be reallocable and
currently at least size <i>bufsz</i>.</dd>
<dt><tt>char *charset_decode_mimeheader(const char *s, char *buf, int
bufsz)</tt></dt> <dd> Given a string <i>s</i> containing possible MIME
encoded substrings (per RFC 2047), decode into canonical form in
<i>buf</i>. <i>buf</i> must be reallocable and currently at least size
<i>bufsz</i>.</dd>
<dt><tt>charset_index charset_lookupname(const char *name)</tt></dt>
<dd> Given <i>name</i> return the Cyrus charset index. 0 always
represents US-ASCII. The returned charset_index may be saved in a
file; it is stable and is an integer. If this version of Cyrus does
not support the charset, <tt>CHARSET_UNKNOWN_CHARSET</tt> is
returned.</dd>
<dt><tt>comp_pat *charset_compilepat(const char *s)</tt></dt>
<dd>
Compiles a NUL-terminated canonicalized string <i>s</i> into a
Boyer-Moore table for fast searching. I'll describe these <a
href="#comp_pat">compiled patterns</a> later. </dd>
<dt><tt>void charset_freepat(comp_pat *pat)</tt></dt>
<dd> Frees a pattern previously return by <tt>charset_compilepat()</tt>.</dd>
<dt><tt>int charset_searchstring(const char *substr, comp_pat *pat,
const char *s, int len)</tt></dt>
<dd> Searches for a canonicalized string <i>substr</i> in the
canonicalized string <i>s</i>. <i>s</i> is of length <i>len</i>.
<i>substr</i> must have been previously compiled into <i>pat</i>.
Returns non-zero for a hit, zero for no match.
</dd>
<dt><tt>int charset_searchfile(const char *substr, comp_pat *pat,
const char *msg_base, int mapnl, int len,
charset_index charset, int encoding)</tt></dt>
<dd>
Searches for the canonicalized string <i>substr</i> with compiled
pattern <i>pat</i> in a large buffer starting at <i>msg_base</i> of
length <i>len</i>. The large buffer is of charset <i>charset</i> with
the encoding <i>encoding</i>. <tt>charset_searchfile()</tt> will
dynamically unencode and canonicalize the search text looking for
<i>substr</i>. (If <i>mapnl</i> is set, the buffer has only <tt>\n</tt>
instead of <tt>\r\n</tt>, but the length assumes that each <tt>\n</tt>
is dynamically converted to <tt>\r\n</tt>. This feature is deprecated.)
</dd>
<dt><tt>char *charset_decode_mimebody(const char *msg_base, int len,
int encoding, char **buf, int *bufsz,
int *outlen)</tt></dt>
<dd>
Decode the MIME body part (per RFC 2045) located in the large buffer
starting at <i>msg_base</i> of length <i>len</i>. The large buffer is of
encoding <i>encoding</i>. <tt>charset_decode_mimebody()</tt> will decode
into <i>buf</i>. <i>buf</i> must be reallocable and currently at least size
<i>bufsz</i>. The number of decoded bytes is returned in <i>outlen</i>.</dd>
<dt><tt>charset_extractfile()</tt></dt>
<dd> Used by <tt>squatter</tt> and possibly other text indexing engines,
but not described here.</dd>
</dl>
<h2>the TRANSLATE macro: using the transcoding tables</h2>
<p>The external interface is implemented with the help of the
<tt>START</tt> and <tt>TRANSLATE</tt> macros:</p>
<dl>
<dt><tt>void START(struct decode_state *state, const unsigned char
(*table)[256][4])</tt></dt>
<dd>
<tt>START</tt> initializes <i>state</i> to be ready for transcoding of the
charset translation table given with <i>table</i>. The starting active
table is always the first one in the list passed in.</dd>
<dt><tt>void TRANSLATE(struct decode_state *state, unsigned char
input, unsigned char *outbuf, unsigned outindex)</tt></dt>
<dd>
<tt>TRANSLATE</tt> takes four parameters: <i>state</i> is the current
state of the translation; it must have been initialized with
<tt>START</tt> and is modified by <tt>TRANSLATE</tt>; <i>input</i> is
one octet of input from the stream to be transcoded; <i>outbuf</i> is
a pointer to the start of the buffer to write output characters;
<i>outindex</i> is the index where this translation should be
written. The size of <i>outbuf</i> must be at least <i>outindex +
charset_max_translation</i>.
</dd>
</dl>
<p>Each charset consists of a set of one or more tables; the
<i>table</i> parameter passed into <tt>START</tt> is the first of
these tables and the others are adjacent in memory. Characters are
transcoded by indexing into the active table with <i>input</i> and
examining the 4 octet translation. The 4 octet translation may consist
of 0–3 character translations followed by a control code or a
series of control codes. In effect, the translation for a given octet
is a mini-program that consists either of UTF-8 octets or control
codes. One of the control codes RET, END, JSR, or JMP must occur in
the 4 octet translation.</p>
<h3>control codes</h3>
<p>Control codes are represented by uppercase US-ASCII characters
since no uppercase characters can appear in the output translation
(recall that Cyrus canonical form downcases). Any uppercase US-ASCII
character (<tt>[A .. Z]</tt>) is thus interpreted specially by the
<tt>TRANSLATE</tt> virtual machine. Any other octet encountered as an
output translation is presumed to be part of the UTF-8 output
sequence and copied to the output.</p>
<p>The names of control codes are actually C pre-processor defines to
uppercase US-ASCII characters. As the mnenomics are easier to
understand, I use them in discussing their semantics.</p>
<h3>control code reference</h3>
<p><tt>TRANSLATE</tt> recognizes the following "normal" control
codes:</p>
<dl>
<dt>XLT</dt>
<dd>This is the first octet of the four octet sequence, indicating
that the desired translation is larger than 3 UTF-8 octets. The next
two octets represent an offset to look up in the special
chartables_long_translations[] table. After that translation is copied
to the outbuf, the final octet is interpreted (it must be either a RET
or an END).</dd>
<dt>JSR</dt>
<dd>The <tt>TRANSLATE</tt> virtual machine has a stack, fixed at size
1. A JSR copies address of the current active table to the stack and
transitions to the active table given by the next two octets. (For
instance, table 1 would be the next table after the table given as a
parameter to <tt>START</tt>.) Translation of the current octet stops
after encountering a JSR.
<p>JSRs are useful for converting a two octet input character: the
first octet in the character will make a JSR to some table; the second
octet will produce a translation and RET to the current table.
</p>
<p>Since the virtual machine has a fixed size stack, it would be
highly unusual for the virtual machine to encounter two different JSRs
without an intervening RET.</p></dd>
<dt>JMP</dt>
<dd> Similiar to JSR, but does not change the stack. It is the
equivalent of a goto. JMPs are useful to deal with modal input
character sets (such as an escape in ISO-2022-JP, see <a
href="#mkchartable">how the tables are generated</a>).</dd>
<dt>RET</dt>
<dd>Indicates that we are done translating this input octet and we should
return to the previous active table. It might appear as the first of
the 4 translation octets, in which case this input character
translates into nothing (it might be whitespace, for instance).</dd>
<dt>END</dt>
<dd>Indicates we are done translating this input octet. When
<tt>TRANSLATE</tt> is next called, that input octet will be
interpreted against the current active table; the stack does not
change. </dd>
</dl>
<p>In addition, it recognizes the following "special" control codes
for charsets that aren't easily represented by a set of tables, UTF-8
and UTF-7:</p>
<dl>
<dt>U7F </dt>
<dd>UTF-7 consists of US-ASCII characters and a special escape
character that indicates a transition to base-64 encoded UTF-16
characters. The virtual machine has built in code to handle the base64
decoding. In UTF-7's base64, 8 input octets result in 3 characters, so
the tables would be rather large.</dd>
<dt>U7N</dt>
<dd>This indicates that the current octet is the continuation of the
base-64 section.</dd>
<dt>U83</dt>
<dd>One and two character UTF-8 sequences are handled normally in the
charset code. To keep the table size down, 3 octet sequences are
handled specially. U83 indicates that the current input octet is the
start of a three character sequence. It is also an implicit jump to
the 2nd table in the UTF-8 sequence, ending this translation.</dd>
<dt>U83_2</dt>
<dd>This input octet 2nd of 3-octet UTF-8 input, with an implicit
jump to the 3rd table. </dd>
<dt>U83_3</dt>
<dd>3rd octet of a 3-octet UTF-8 input. This produces the output
characters and has an implicit jump to the 1st table of UTF-8.</dd>
</dl>
<p>Finally, it's useful to mention the special character
<tt>EMPTY</tt> which is guaranteed not to match any character. It is
also represented by an uppercase US-ASCII character.
<h2 id="comp_pat">searching and compiled patterns</h2>
<h3>boyer-moore</h3>
<p>brief description of boyer-moore xxx</p>
<h3>cyrus implementation</h3>
<p>why two arrays? us-ascii optimization, really kinda useless now
xxx</p>
<p>meta-data stored at the end xxx</p>
<h2 id="mkchartable">generating the tables: <tt>mkchartable</tt></h2>
<p>The program <tt>mkchartable</tt> is used to generate the charset
transcoding tables used by TRANSLATE. These tables are carefully
constructed so no more than a single octet need be examined at a time;
this octet results in either an output stream of UTF-8 characters
being generated or some sort of state change.</p>
<p><tt>mkchartable</tt> uses three different sorts of input files to
generate these tables. These files are located in the
<tt>lib/charset</tt> directory.</p>
<h3 id="charset_tables">charset tables</h3>
<p>Each charset file maps a single charset to the corresponding
Unicode characters. For the US-ASCII and ISO-8859-x character sets
this is trivial: each input byte corresponds to a single Unicode
character. (Actually, some ISO-8859-x octets do not map to any Unicode
character. In that case, the file either does not contain that octet
or map it to "<tt>????</tt>".)</p>
<p>Other character sets are trickier. For instance, GB-2312 has both
single and double byte characters, but is still a simple map from
input character to output character. More complicated are modal
character encodings. For instance, ISO-2022-JP starts in US-ASCII mode
and uses <tt>1B</tt> as an escape character followed by another two
characters to select a new mode.</p>
<p>The input charset labels modes with "<tt>:</tt>" followed by the
mode name. The starting mode "<tt>US-ASCII</tt>" in ISO-2022-JP is
preceeded by "<tt>:US-ASCII</tt>". Mode transitions are denoted by a
Unicode conversion of "<tt>>newmode</tt>" or
"<tt>:newmode</tt>". To denote that the octet <tt>42</tt> transitions
into the "<tt>US-ASCII</tt>" mode, the charset file has "<tt>42
>US-ASCII</tt>". The mode names themselves are arbitrary labels and
have no effect on the output.</p>
<p>The input charset labels modes with ":" followed by the mode name.
The mode name is optionally followed by a space and the
"<tt><</tt>" character. If the "<tt><</tt>" character is
present, then all translations will be followed by a RET instruction
instead of an END instruction.</p>
<p>The transition "<tt>>newmode</tt>" results in a JSR instruction
being generated. A JMP instruction is generated by a transition of
"<tt>:newmode</tt>".</p>
<p>The input byte can be specified as "<tt>*</tt>". This is used to
define the "default action" which is used for input bytes that are not
otherwise defined for the mode. If the default action is not
explicitly stated, it is a translation to EMPTY.</p>
<h3>unicode data table</h3>
<p>The <tt>unidata2.txt</tt> file is verbatim from the Unicode
standard. More recent versions should be available <a
href="http://www.unicode.org/xxx">from their website</a>. Each entry
in the file describers a Unicode character by the following
properties, seperated by semicolons:</p>
<ul>
<li>code point (16-bit character value) in hex</li>
<li>character name (unused by Cyrus)</li>
<li>general category, such as whitespace or puncuation</li>
<li>the canonical combining class (unused)</li>
<li>bidirection chategory (unused)</li>
<li>character decomposition</li>
<li>decimal digit value (unused)</li>
<li>digit value (unused, and, no, I don't know the difference)</li>
<li>numeric value including fractions (unused)</li>
<li>mirrored character (unused)</li>
<li>Unicode 1.0 name (unused)</li>
<li>comment (unused)</li>
<li>upper case equivalent (unused)</li>
<li>lower case equivalent</li>
</ul>
<p>In general, Cyrus uses the lower case equivalent if there is one,
and the decomposed value otherwise.</p>
<h3>unicode fixup table</h3>
<p>The <tt>unifix.txt</tt> file contains Cyrus-specific mappings for
characters. It overrides the <tt>unidata2.txt</tt> table. Each rule in
the file is explained with a comment. It's helpful to remember that
the Unicode general categories starting with <tt>Z</tt> represent
whitespace, and whitespace is always removed.</p>
<h3>generating <tt>chartable.c</tt></h3>
<p>how <tt>mkchartable</tt> works: collapses the encoding modes, the
unicode translations, and other normalizations into the output tables
described above xxx</p>
<h2>for the future</h2>
<h3>Sieve/ACAP comparators</h3>
<h3>adjustable normalization?</h3>
<p>The use of uppercase US-ASCII characters is one of the annoyances
in trying to generalize the charset transcoding. If we continue to
restrict the characters under consideration to the BMP, switching to
UTF-8 control codes that start 4 or 5 byte sequences is possible.</p>
<p>Another possibility is to use a NUL character as an escape
sequence, though this increases the size of each control code by 1
octet.</p>
<h3>handle >2 octet input characters</h3>
<h3>make UTF-8 more regular</h3>
<p>consider whether we really need U83, U83_2, U83_3. also consider
changing <tt>{ U83, 0, 0, 0 }</tt> translations to <tt>{ U83, JMP, 0, 1
}</tt> sequences to at least eliminate the implicit jump.</p>
<h3>require minimal UTF-8 characters</h3>
<h2>references</h2>
<p>xxx</p>
<ul>
<li>[UNICODE] Unicode / ISO 10646</li>
<li>[UTF-8] utf-8 RFC</li>
<li>[UTF-7] utf-7 RFC</li>
<li>[BM] boyer-moore</li>
<li>[ACAP] the comparators reference. see section XXX of RFC 2244.</li>
</ul>
</body>
</html>