Using COLTAB to make collation key tables
Graham Asher, 10th November 1999
Introduction
EPOC32 reads collation keys from tables. These tables not only map single Unicode characters to single keys, but map sequences of characters to sequences of keys. This system allows almost any kind of collation behaviour to be expressed. Each key is actually a triplet, giving three weights that can be used successively to make finer discriminations. There is an implicit fourth weight that is the Unicode value of the character itself, but that is not stored in the tables.

There can be two sets of tables. The first set provides the standard keys; the optional second set tailors them for a particular locale. See the definition of TCollationMethod in \e32\include\collate.h; iMainTable contains the standard keys and iOverrideTable the tailoring.

The tables used by EPOC are arrays of numbers written in the C++ source code in hexadecimal notation, and packed and encoded in various ways to make them more compact. This article explains how to use COLTAB to write this C++ code, translating from source data supplied by the Unicode Consortium, or other source data in the same format. It is followed by a case study; that of creating collation tables for Swedish.
COLTAB reference
COLTAB syntax
COLTAB is a Windows NT console application that requires a single command-line argument and a single option.

The argument is the locale name, which is used as a base for the names of the files that COLTAB reads and writes. The locale name can be one of the two special names “standard” and “wgl4”, in which case the standard data files are read, or anything else (usually the name of a language) in which case files providing specific collation rules for that language are read.

The option is ‘/a’. The organization of the default collation keys files provided by the Unicode Consortium have been slightly changed since Unicode version 3.0. Before and in Unicode 3.0, three keys files are provided. They are the base keys file, the composite keys file, and the string keys file. After Unicode 3.0, these three files are combined into one single file, which is the all keys file. When option ‘/a’ is not specified, COLTAB will try to find the three separated files, using the locale name as file name base. When option ‘a’ is specified, COLTAB will try to find the single keys file, using the locale name as file name base.

The input and output files are:

1. The base keys file. If the locale name is  “standard” or “wgl4” this is basekeys.txt (the standard base keys file supplied by the Unicode Consortium), otherwise it is <locale-name>_basekeys.txt.

2. The composite keys file. If the locale name is  “standard” or “wgl4” this is compkeys.txt (the standard base keys file supplied by the Unicode Consortium), otherwise it is <locale-name>_compkeys.txt.

3. The file of strings; sequences of Unicode characters that map to single collation keys. If the locale name is  “standard” or “wgl4” no strings file is read, otherwise it is <locale-name>_strings.txt.

3. The all keys file. If the locale name is “standard” or “wgl4” this is baseallkeys.txt (the standard all keys file supplied by the Unicode Consortium), otherwise it is <locale-name>_allkeys.txt.

4. The output C++ source file. This is ls_<locale-name>.cpp.
The format of the base keys file
Here are a few lines from basekeys.txt:

0044 ; [.0707.0020.0008.0044] % LATIN CAPITAL LETTER D
FF24 ; [.0707.0020.0009.FF24] % FULLWIDTH LATIN CAPITAL LETTER D; COMPAT
216E ; [.0707.0020.000A.216E] % ROMAN NUMERAL FIVE HUNDRED; COMPAT
24B9 ; [.0707.0020.000C.24B9] % CIRCLED LATIN CAPITAL LETTER D; COMPAT
010F ; [.0707.0031.0002.010F] % LATIN SMALL LETTER D WITH CARON; CANONSEQ

The format is

a four-digit hex number; the Unicode value of the character
a space, a semicolon, and a space (optionally, a single space can occur here rather then the three characters just mentioned; this is how the data files used to be before Unicode 3.0 was released in March 2000)
square brackets enclosing the four collation keys, each of which is a four-digit hex number preceded either by a full stop (meaning that this value is treated in the ordinary way) or an asterisk (meaning that this value is usually ignored)
a space
a percent sign
an optional comment that is usually the Unicode name of the character

In addition, the file can start with some comments (lines starting with a percent sign) followed by the revision number (e.g., ‘2.1.9 % version’) on a line of its own; this part is optional. Blank lines are ignored.

The four key values have the following conventional meanings:

Level-0 key (0707 in the first example line above): basic character identity. All Ds have 0707 as their level-0 key.

Level-1 key (0020): diacritic or modifier if any; 0020 means ‘no diacritic’, 0031 means ‘caron’, etc. There are too many of these to list here but values can easily be ascertained by looking at basekeys.txt.

Level-2 key (0008): case or other variation. Here are the conventional values used in basekeys.txt and compkeys.txt:

0002: default value; small letter; musical sign
0003: fullwidth small letter
0004: small letter used as Roman numeral or mathematical symbol
0005: script small letter
0006: circled small letter
0007: not used
0008: capital letter
0009: fullwidth capital letter
000A: capital letter used as Roman numeral or mathematical symbol
000B: script capital
000C: circled capital
000D: Hiragana small letter
000E: Hiragana letter
000F: Katakana small letter
0010: Halfwidth Katakana small letter
0011: Katakana letter
0012: Halfwidth Katakana letter
0013: Circled Katakana letter
0014: modifier, ideographic annotation, superscript
0015: subscript
0016: vertical presentation form
0017: initial (Arabic or other) presentation form
0018: medial presentation form
0019: final presentation form
001A: isolated presentation form
001B: non-breaking variant (non-break space, etc.)
001C: surrounded by square
001D: surrounded by square (not sure how this differs from 001C)
001E: vulgar fraction

Level-3 key: fallback key, used if all other keys yield equality; in basekeys.txt always the Unicode value of the character. This value is not stored in the tables generated by COLTAB.

The format of the composite keys file
This is exactly the same as the base keys file, except that there may be more than one group of collation keys. Here are a few sample lines (broken here because of the narrow page):

217A ; [.08D9.0020.0004.0078] [.079D.0020.0004.0069] % SMALL ROMAN NUMERAL ELEVEN;
COMPATSEQ
217B ; [.08D9.0020.0004.0078] [.079D.0020.0004.0069] [.079D.0020.0004.0069] %
SMALL ROMAN NUMERAL TWELVE; COMPATSEQ
216A ; [.08D9.0020.000A.0058] [.079D.0020.000A.0049] % ROMAN NUMERAL ELEVEN;
COMPATSEQ
216B ; [.08D9.0020.000A.0058] [.079D.0020.000A.0049] [.079D.0020.000A.0049] % ROMAN
NUMERAL TWELVE; COMPATSEQ
0149 ; [.091E.0020.0004.02BC] [.07FD.0020.0004.006E] % LATIN SMALL LETTER N
PRECEDED BY APOSTROPHE; COMPATSEQ
The format of the strings file
The strings file has the same format as compkeys.txt, except that there can be any number of Unicode characters at the start of the line, space-separated and each exactly 4 hex digits.

Each line associates a string of Unicode characters (sometimes known as a ‘collation grapheme’) with a collation key or sequence of collation keys. The collation system currently handles strings of up to 8 characters. For example, the following entry treats ‘ch’ as a single letter, as is done in traditional Spanish collation:

0063 0068 ; [.06FC.0020.0002.0063] % LATIN SMALL LETTER C followed by LATIN SMALL
LETTER H

You will have to supply all the case versions as separate entries. For ‘ch’ the variants ‘ch’, ‘Ch’ and ‘CH’ are needed; ‘cH’ should probably be omitted as not actually a case-variant of ‘ch’ but two separate letters.
The output file
COLTAB writes a C++ source file that looks like this (omitting irrelevant material):

static const TUint32 TheKey[] = 
	{
	0x21e0112,0x21e0113,0x2260112,0x2260112,0x2260113,0x2740112,
0x2740113,0x6c60178,	

	<many lines omitted >

	0xaa2011d,0xaa60105,0xaa6011d
	};

static const TUint32 TheIndex[] = 
	{
	0x37,0x10037,0x20037,0x30037,0x40037,0x50037,0x60037,0x70037,

	<many lines omitted >

	0xfb01001f,0xfb020021,0xfeff0037,0xfffc00fb,0xfffd00fc
	};

static const TUint16 TheStringElement[] = 
	{
	};

static const TUint32 TheStringIndex[] = 
	{
	};

static const TCollationKeyTable TheStandardTable = 
	{ TheKey, TheIndex, 517, TheStringElement, TheStringIndex, 0 };

The last declaration is the important one; all the preceding ones are components of it. The TCollationKeyTable structure that is declared can be used as one of the two elements of a TCollationMethod structure, which can be passed to one of the Mem::CompareC or TDesC16::CompareC functions.

Putting the output into EPOC
In an EPOC implementation collation rules are kept in two places. The standard rules, which form the base from which the tailoring or tailorings for a given locale differ, are encoded as constant static data in \e32\euser\unicode\collate.cpp. The locale-specific rules for the default locale are kept in \e32\elocl\ls_unic.cpp. Locale-specific rules for other locales are kept in other files of the form \e32\elocl\ls_<x>.cpp, where <x> will probably be the language name or locale code; this is yet to be decided.

The standard rules should be changed only when the Unicode organisation releases new collation key tables, or when EPOC changes.

Tailoring files containing locale-specific collation keys can be created whenever necessary by running COLTAB; for locales other than “wgl4” and “standard” COLTAB writes a complete source file that with small modifications (e.g., declaring a constant for the UID for the locale-specific collation rules) can be used directly as part of ELOCL.
Case Study: tailoring for the Swedish locale
Determine the collation rules
The first stage is to determine the collation rules for the locale in question. I will use Swedish as an example. Swedish uses the Latin script with some letters that require special treatment. It is a good rule, and one that I will follow here, that in all cases apart from the peculiarities that actually matter to the particular locale, the standard collation system should be used. For example, it is unnecessary and undesirable for the Swedish locale to sort Greek letters in a non-standard way. This means that the Swedish locale will be a relatively simple tailoring of the standard locale, which provides collation keys for the WGL4 character repertoire plus some useful control characters.

The rules that we need to express are as follows. (Note to experts in Swedish: these rules are meant as an example and may not follow actual Swedish practice, although I believe they are correct as far as they go.)

1. 	The letters å, ä, and ö (a-ring, a-umlaut and o-umlaut) are separate letters, placed in that order after z. They are not to be treated as accented letters.
2. 	The letters v and w are identical for the purposes of collation.
3. 	The letters ü and y are identical for the purposes of collation.

Create tailoring data
Here is the tailoring data. 

The equivalence of v and w is indicated by a tailored base keys file that should be called (following COLTAB’s conventions) swedish_basekeys.txt. Creating this is simple; just copy the basekeys.txt entries for V (U+0056) and v (U+0076) but change the Unicode values to 0057 and 0077.

0057 [.08C5.0020.0008.0057] % W equivalent to V
0077 [.08C5.0020.0002.0077] % w equivalent to v

The letters å, ä, ö and ü must be treated in the data as strings of Unicode values, that is of bases plus accents, associated with single keys. (There is no need to create entries for the composed versions, because the EPOC collation system dissects them as it goes along). Use the combining diacritics; most are in the Unicode range U+0300—U+0361. For example, U+030A is combining ring above. In general you have to use the combined character’s canonical decomposition.

The primary collation keys for å, ä, and ö are assigned by making use of the convenient gaps between existing key values. The last ‘z’ is U+0291, Latin small letter z with curl, which has the primary key 08F5. The next entry is for U+0292, Latin small letter ezh, which has the primary key 08F9. This leaves a gap of 3 unused primary keys, 08F6—08F8, which can be used for å, ä, and ö. Of course, if there were more interpolated values, other primary keys would need to be reassigned.

This gives us the following strings file, which is called swedish_strings.txt:

0061 030A [.08F6.0020.0002.00E5] % a-ring after z
0061 0308 [.08F7.0020.0002.00E4] % a-umlaut after a-ring
006F 0308 [.08F8.0020.0002.00F6] % o-umlaut after a-umlaut
0041 030A [.08F6.0020.0008.00C5] % A-ring after Z
0041 0308 [.08F7.0020.0008.00C4] % A-umlaut after A-ring
004F 0308 [.08F8.0020.0008.00D6] % O-umlaut after A-umlaut
0075 0308 [.08DD.0020.0002.00FC] % u-umlaut equivalent to y
0055 0308 [.08DD.0020.0008.00FC] % U-umlaut equivalent to Y

There is a third input file, the composite keys. We don’t need to supply any tailorings for composite keys, so we use an empty file called swedish_compkeys.txt.
Run COLTAB and make the locale-specific file of collation data
Using the files just described, run COLTAB:

coltab swedish

The output is a new file, ls_swedish.cpp:
// Copyright (c) 2000-2009 Nokia Corporation and/or its subsidiary(-ies).// All rights reserved.// This component and the accompanying materials are made available// under the terms of the License "Symbian Foundation License v1.0"// which accompanies this distribution, and is available// at the URL "http://www.symbianfoundation.org/legal/sfl-v10.html".//// Initial Contributors:// Nokia Corporation - initial contribution.//// Contributors://// Description:// 
LS_SWEDISH.CPP// 
// 
// //

/*
The LCharSet object used by the Swedish locale.
Generated by COLTAB.
*/

#include "ls_std.h"
#include <collate.h>
const TUint KUidSwedishCollationMethod = /* FILL THIS IN */;

static const TUint32 TheSwedishKey[] = 
	{
	0x8f60109,0x8f70109,0x8f80109,0x8f60121,0x8f70121,0x8f80121,0x8dd0109,0x8dd0121,
	0x8c50121,0x8c50109,
	};

static const TUint32 TheSwedishIndex[] = 
	{
	0x570008,0x770009,
	};

static const TUint16 TheSwedishStringElement[] = 
	{
	0x2,0x61,0x30a,0x2,0x61,0x308,0x2,0x6f,
	0x308,0x2,0x41,0x30a,0x2,0x41,0x308,0x2,
	0x4f,0x308,0x2,0x75,0x308,0x2,0x55,0x308,
	};

static const TUint32 TheSwedishStringIndex[] = 
	{
	0xc0004,0x90003,0xf0005,0x150007,0x30001,0x0,0x60002,0x120006,
	};

static const TCollationKeyTable TheSwedishTable = 
	{ TheSwedishKey, TheSwedishIndex, 2, TheSwedishStringElement, TheSwedishStringIndex, 8 };

static const TCollationMethod TheCollationMethod[] = 
	{
		{
		KUidSwedishCollationMethod, // the method for the locale
		NULL, // use the standard table as the main table
		&TheSwedishTable, // the locale values override the standard values
		0 // the flags are standard
		},
		{
		KUidBasicCollationMethod, // the standard unlocalised method
		NULL, // null means use the standard table
		NULL, // there's no override table
		0 // the flags are standard
		}
	};

static const TCollationDataSet TheCollationDataSet =
	{
	TheCollationMethod,
	2
	};

// The one and only locale character set object.
const LCharSet TheCharSet =
	{
	NULL,
	&TheCollationDataSet
	};