Most programming languages evolved awkwardly during the transition from ASCII to 16-bit UCS-2 to full Unicode. They contain internationalization features that often aren’t portable or don’t suffice.
Unicode is more than a numbering scheme for the characters of every language – although that in itself is a useful accomplishment. Unicode also includes characters’ case, directionality, and alphabetic properties. The Unicode standard and specifications describe the proper way to divide words and break lines, sort text, format numbers, display text in different directions, split/combine/reorder vowels South Asian languages, and determine when characters may look visually confusable.
Human languages are highly varied and internally inconsistent, and any application which treats strings as more than an opaque byte stream must embrace the complexity. Realistically this means using a mature third-party library.
This article illustrates text processing ideas with example programs. We’ll use the International Components for Unicode (ICU) library, which is mature, portable, and powers the international text processing behind many products and operating systems.
IBM (the maintainers of ICU) officially support a C, C++ and Java API. We’ll use the C API here for a better view into the internals. Many languages have bindings to the library, so these concepts should be applicable to your language of choice.
Table of Contents:
Concepts
Before getting into the example code, it’s important to learn the terminology. Let’s start at the most basic question.
What is a “character?”
“Character” is an overloaded term. What a native speaker of a language identifies as a letter or symbol is often stored as multiple values in the internal Unicode representation. The representation is further obscured by an additional encoding in memory, on disk, or during network transmission.
Let’s start at the abstraction closest to the user: the grapheme cluster. A “grapheme” is a graphical unit that a reader recognizes as a single element of the writing system. It’s the character as a user would understand it. For example, 山, ä and క్క are graphemes. Pieces of a single grapheme always stay together in print; breaking them apart is either nonsense or changes the meaning of the symbol. They are rendered as “glyphs,” i.e. markings on paper or screen which vary by font, style, or position in a word.
You might imagine that Unicode assigns each grapheme a unique number, but that is not true. It would be wasteful because there is a combinatorial explosion between letters and diacritical marks. For instance (o, ô, ọ, ộ) and (a, â, ạ, ậ) follow a pattern. Rather than assigning a distinct number to each, it’s more efficient to assign a number to o and a, and then to each of the combining marks. The graphemes can be built from letters and combining marks e.g. ậ = a + ◌̂ + ◌̣.
In reality Unicode takes both approaches. It assigns numbers to basic letters and combining marks, but also to some of their more common combinations. Many graphemes can thus be created in more than one way. For instance ộ can be specified in five ways:
- A: U+006f (o) + U+0302 (◌̂) + U+0323 (◌̣)
- B: U+006f (o) + U+0323 (◌̣) + U+0302 (◌̂)
- C: U+00f4 (ô) + U+0323 (◌̣)
- D: U+1ecd (ọ) + U+0302 (◌̂)
- E: U+1ed9 (ộ)
The numbers (written U+xxxx) for each abstract character and each combining symbol are called “codepoints.” Every Unicode string is expressed as a list of codepoints. As illustrated above, multiple strings of codepoints may render into the same sequence of graphemes.
To meaningfully compare strings codepoint by codepoint for equality, both strings should both be represented in a consistent way. A standardized choice of codepoint decomposition for graphemes is called a “normal form.”
One choice is to decompose a string into as many codepoints as possible like examples A and B (with a weighting factor of which combining marks should come first). That is called Normalization Form Canonical Decomposition (NFD). Another choice is to do the opposite and use the fewest codepoints possible like example E. This is called Normalization Form Canonical Composition (NFC).
A core concept to remember is that, although codepoints are the building blocks of text, they don’t match up 1-1 with user-perceived characters (graphemes). Operations such as taking the length of an array of codepoints, or accessing arbitrary array positions are typically not useful for Unicode programs. Programs must also be mindful of the combining characters, like diacritical marks, when inserting or deleting codepoints. Inserting U+0061 into the asterisk position U+006f U+0302 (*) U+0323 changes the string “ộ” into “ôạ” rather than “ộa”.
Glyphs vs graphemes
It’s not just fonts that cause graphemes to be rendered into varying glyphs. The rules of some languages cause glyphs to change through contextual shaping. For instance the Arabic letter “heh” has four forms, depending on which sides are flanked by letters. When isolated it appears as ﻩ and in the final/initial/medial position in a word it appears as ﻪ/ﻫ/ﻬ respectively. Similarly, Greek displays lower-case sigma differently at the end of the word (final form) than elsewhere. Some glyphs change based on visual order. In a right-to-left language the starting parenthesis “(” mirrors to display as “)”.
Not only do individual graphemes’ glyphs vary, graphemes can combine to form single glyphs. One way is through ligatures. The latin letters “fi” often join the dot of the i with the curve of the f (presentation form U+FB01 fi). Another way is language irregularity. The Arabic ا and ل, when contiguous, must form ﻻ.
Conversely, a single grapheme can split into multiple glyphs. For instance in some Indic languages, vowels can split and surround preceding consonants. In Bengali, U+09CC ৌ surrounds U+09AE ম to become মৌ . Try placing a cursor at the end of this text box and pressing backspace:
How are codepoints encoded?
In 1990, Unicode codepoints were 16 bits wide. That choice turned out to be too small for the symbols and languages people wanted to represent, so the committee extended the standard to 21 bits. That’s fine in the abstract, but how the 21 bits are stored in memory or communicated between computers depends on practical factors.
It’s an unusual memory size. Computer hardware doesn’t typically access memory in 21-bit chunks. Networking protocols, too, are better geared toward transmitting eight bits at a time. Thus, codepoints are broken into sequences of more conventionally sized blocks called code units for persistence on disk, transmission over networks, and manipulation in memory.
The Unicode Transformation Formats (UTF) describe different ways to map between codepoints and code units. The transformation formats are named after the bit width of their code units (7, 8, 16, or 32), as well as the endianness (BE or LE). For instance: UTF-8, or UTF-16BE. In addition to the UTFs, there’s another – more complex – encoding called Punycode. It is designed to conform with the limited ASCII character subset used for Internet host names.
A final bit of terminology. A “plane” is a continuous group of 65,536 code points. There are 17 planes, identified by the numbers 0 to 16. Plane 0 is the Basic Multilingual Plane (BMP), which contains most commonly-used characters. The higher planes (1 through 16) are called “supplementary planes.”
Which encoding should you choose?
For transmission and storage, use UTF-8. Programs which move ASCII data can handle it without modification. Machine endianness does not affect UTF-8, and the byte-sized units work well in networks and filesystems.
Some sites, like UTF-8 Everywhere go even further and recommend using UTF-8 for internal manipulation of text in program memory. However, I would suggest you use whatever encoding your Unicode library favors for this. You’ll be performing operations through the library API, not directly on code units. As we’re seeing, there is too much complexity between glyphs, graphemes, codepoints and code units to be manipulating the units directly. Use the encoding preferred by your library and convert to/from UTF-8 at the edges of the program.
It’s unwise to use UTF-32 to store strings in memory. In this encoding it’s true that every code unit can hold a full codepoint. However, the relationship between codepoints and glyphs isn’t straightforward, so there isn’t a programmatic advantage to storing the string this way.
UTF-32 also wastes at minimum 11 (32 – 21) bits per codepoint, and typically more. For instance, UTF-16 requires only one 16-bit code unit to encode points in the Base Multilingual Plane (the most commonly encountered points). Thus UTF-32 can typically double the space required for the BMP.
There are times to manipulate UTF-32, such as when examining a single codepoint. We’ll see examples below.
ICU example programs
The programs in this article are ready to compile and run. They require the ICU C library called ICU4C, which is available on most platforms through the operating system package manager.
ICU provides five libraries for linking (we need the first two):
| Package | Contents |
|---|---|
| icu-uc | Common (uc) and Data (dt/data) libraries |
| icu-io | Ustdio/iostream library (icuio) |
| icu-i18n | Internationalization (in/i18n) library |
| icu-le | Layout Engine |
| icu-lx | Paragraph Layout |
To use ICU4C, set the compiler and linker flags with pkg-config in your Makefile. (Pkg-config may also need to be installed on your computer.)
CFLAGS = -std=c99 -pedantic -Wall -Wextra
`pkg-config --cflags icu-uc icu-io`
LDFLAGS = `pkg-config --libs icu-uc icu-io`The examples in this article conform to the C89 standard, but we specify C99 in the Makefile because the ICU header files use C99-style (//) comments.
Generating random codepoints
To start getting a feel for ICU’s I/O and codepoint manipulation, let’s make a program to output completely random (but valid) codepoints. You could use this program as a basic fuzz tester, to see whether its output confuses other programs. A real fuzz tester ought to have the ability to take an explicit seed for repeatable output, but we will omit that functionality from our simple demo.
This program has limited portability because it gets entropy from /dev/urandom, a Unix device. To generate good random numbers using only the C standard library, see my other article. Also POSIX provides pseudo-random number functions.
/* for constants like EXIT_FAILURE */
#include A note about the mysterious U_UNASSIGNED category, the “non-characters.” These are code points that are permanently reserved in the Unicode Standard for internal use. They are not recommended for use in open interchange of Unicode text data. The Unicode Standard sets aside 66 non-character code points. The last two code points of each plane are noncharacters (U+FFFE and U+FFFF on the BMP). In addition, there is a contiguous range of another 32 noncharacter code points in the BMP: U+FDD0…U+FDEF.
Applications are free to use any of these noncharacter code points internally. They have no standard interpretation when exchanged outside the context of internal use. They are not illegal in interchange, nor does their presence cause Unicode text to be ill-formed.
Manipulating codepoints
We discussed non-characters in the previous section, but there are also Private Use codepoints. Unlike non-characters, those for private use are designated for interchange between systems. However the precise meaning and glyphs for these characters is specific to the organization using them. The same codepoints can be used for different things by different people.
Unicode provides a large area for private use. Both a small code block in the BMP, as well as two entire planes: 15 and 16. Because no browser or text editor will render PUA codepoints beyond (typically) empty boxes, we can exploit plane 15 to make a visually confusing code. Ultimately it’s a cheesy transposition cypher, but it’s kind of fun.
Below is a program to shift characters in the BMP to/from plane 15, the Private Use Area A. Example output of an encoded string:
#include Examining UTF-8 code units
So far we’ve been working entirely with complete codepoints. This next example gets into their representation as code units in a transformation format, namely UTF-8. We will read the codepoint as a hexadecimal program argument, and convert it to between 1-4 bytes in UTF-8, and print the hex values of those bytes.
/*** utf8.c ***/
#include Suppose you compile this to a program named utf8. Here are some examples:
# ascii characters are unchanged
$ ./utf8 61
0: 61
# other codepoints require more bytes
$ ./utf8 1F41A
0: f09f909a
# format is compatible with "xxd"
$ ./utf8 1F41A | xxd -r
🐚
# surrogates (used in UTF-16) are not valid codepoints
$ ./utf8 DC00
Invalid codepoint: U+DC00Reading lines into internal UTF-16 representation
Unlimited line length
Here’s a useful helper function named u_wholeline() which reads a line of any length into a dynamically allocated buffer. It reads as UChar*, which is ICU’s standard UTF-16 code unit array.
/* to properly test realloc */
#include Limited line length
The previous example reads an entire line. However, reading a limited number of code units from UTF-16 lines is more tricky. Truncating a Unicode string is always a little dangerous due to possibly splitting a word and breaking contextual shaping.
UTF-16 also has surrogate pairs, which are how that translation format expresses codepoints outside the BMP. Ending a UTF-16 string early can split surrogate pairs without the proper precaution.
The following example reads lines in chunks of at most three UTF-16 code units at a time. If it reads two consecutive codepoints from supplementary planes it will fail. The program accepts a “fix” argument to make it push a final unpaired surrogate back onto the stream for a future read.
/*** codeunit.c ***/
#include If the program reads two weird numerals 𝟘𝟙 (different from 01), neither of which are in the BMP, it finds one codepoint but chokes on the broken pair:
$ echo -n 𝟘𝟙 | ./codeunit
UTF-16 : d835 dfd8 d835
Error? : U_INVALID_CHAR_FOUND
Codepoints: 1d7d8
UTF-16 : dfd9
Error? : U_INVALID_CHAR_FOUND
Codepoints:However if we pass the “fix” argument, the program will read two complete codepoints:
$ echo -n 𝟘𝟙 | ./codeunit fix
UTF-16 : d835 dfd8
Error? : U_ZERO_ERROR
Codepoints: 1d7d8
UTF-16 : d835 dfd9
Error? : U_ZERO_ERROR
Codepoints: 1d7d9Perhaps a better way to read a line with limited length is to use a “break iterator” to stop on a word boundary. We’ll see more about that later.
Our next example will rather laboriously remove diacritical marks from a string. There’s an easier way to do this called “transformation,” but doing it manually provides an opportunity to decompose characters and iterate over them with the U16_NEXT macro.
/*** nomarks.c ***/
#include Here’s an example of running the program:
$ echo "résumé façade" | ./nomarks
resume facadeTransformation
ICU provides a rich domain specific language for transforming strings. For example, our entire program in the previous section can be replaced by the transformation NFD; [:Nonspacing Mark:] Remove; NFC. This means to perform a canonical decomposition, remove nonspacing marks, and then canonically compose again. (In fact our program above didn’t re-compose.)
The program below echoes stdin to stdout, but passes the output through a transformation.
/*** trans-stream.c ***/
#include As mentioned, it can emulate our earlier “nomarks” program:
$ echo "résumé façade" | ./trans "NFD; [:Nonspacing Mark:] Remove; NFC"
resume facadeIt can also transliterate between scripts like this:
$ echo "miirekkaḍiki veḷutunnaaru?" | ./trans "Telugu"
మీరెక్కడికి వెళుతున్నఅరు?Applying the transformation to a stream with u_fsettransliterator is a simple way to do things. However I did discover and file an ICU bug which will be fixed in version 65.1.
A more robust way to apply transformations is by manipulating UChar strings directly. The technique is also probably more applicable in real applications.
Here’s a rewrite of trans-stream that operates on strings directly:
/*** trans-string.c ***/
#include Punycode
Punycode is a representation of Unicode within the limited ASCII character subset used for internet host names. If you enter a non-ASCII URL into a web browser navigation bar, the browser translates to Punycode before making the actual DNS lookup.
The encoding is part of the more general process of Internationalizing Domain Names in Applications (IDNA), which also normalizes the string.
Note that not all Unicode strings can be successfully encoded. For instance codepoints like “⒈” include a period in the glyph and are used for numbered lists. Converting that dot to the ASCII hostname would inadvertently specify a subdomain. ICU turns the offending character into U+FFFD (the “replacement character”) in the output and returns an error.
The following program uses uidna_nameToASCII or uidna_nameToUnicode as needed to translate between Unicode and punycode.
/*** puny.c ***/
#include Example of using the program:
$ echo "façade.com" | ./puny
xn--faade-zra.com
# not every string is allowed
$ echo "a⒈.com" | ./puny
Bad input.
a�.comChanging case
The C standard library has functions like toupper which operate on a single character at a time. ICU has equivalents like u_toupper, but working on single codepoints isn’t sufficient for proper casing. Let’s examine the program and see why.
/*** pointcase.c ***/
#include # not quite right, ß should become SS:
$ echo "Die große Stille" | ./pointcase upper
DIE GROßE STILLE
# also wrong, final sigma should be ς:
$ echo "ΣΊΣΥΦΟΣ" | ./pointcase lower
σίσυφοσAs you can see, some graphemes need to “expand” into a greater number, and others are position-sensitive. To do this properly, we have to operate on entire strings rather than individual characters. Here is a program to do it right:
/*** strcase.c ***/
#include This works better.
$ echo "Die große Stille" | ./strcase upper
DIE GROSSE STILLE
$ echo "ΣΊΣΥΦΟΣ" | ./strcase lower
σίσυφοςCounting words and graphemes
Let’s make a version of wc (the Unix word count program) that knows more about Unicode. Our version will properly count grapheme clusters and word boundaries.
For example, regular wc gets confused by the ancient Ogham script. This was a series of notches scratched into fence posts, and has a space character which is nonblank.
$ echo "ᚈᚐ ᚋᚓ ᚔ ᚍᚏᚐ " | wc
1 1 37One word, you say? Puh-leaze, if your program can’t handle Medieval Irish carvings then I want nothing to do with it. Here’s one that can:
/*** uwc.c ***/
#include Much better:
$ echo "ᚈᚐ ᚋᚓ ᚔ ᚍᚏᚐ " | ./uwc
locale : en_US.UTF-8
Grapheme: 14
Word : 4
Line : 1String search
When comparing strings, we can be more or less strict. A familiar example is case sensitivity, but Unicode provides other options. Comparing strings for equality is a degenerate case of sorting, where the strings must not only be determined as equal, but put in order. Sorting is called “collation” and the Unicode collation algorithm supports multiple levels of increasing strictness.
| Level | Description |
|---|---|
| Primary | base characters |
| Secondary | accents |
| Tertiary | case/variant |
| Quaternary | punctuation |
Each level acts as a tie-breaker when strings match in previous levels. When searching we can choose how deep to check before declaring strings equal. To illustrate, consider a text file called words.txt containing these words:
Cooperate
coöperate
COÖPERATE
co-operate
final
fidesWe will write a program called ugrep, where we can specify a comparison level and search string. If we search for “cooperate” and allow comparisons up to the tertiary level it matches nothing:
$ ./ugrep 3 cooperate < words.txt
# it's an exact match, no resultsIt is possible to shift certain “ignorable” characters (like ‘-’) down to the quaternary level while conducting the original level 3 search:
$ ./ugrep 3i cooperate < words.txt
4: co-operateDoing the same search at the secondary level disregards case, but is still sensitive to accents.
$ ./ugrep 2 cooperate < words.txt
1: CooperateOnce again, can allow ignorables at this level.
$ ./ugrep 2i cooperate < words.txt
1: Cooperate
4: co-operateFinally, going only to the primary level, we match words with the same base letters, modulo case and accents.
$ ./ugrep 1 cooperate < words.txt
1: Cooperate
2: coöperate
3: COÖPERATENote that the idea of a “base character” is dependent on locale. In Swedish, the letters o and ö are quite distinct, and not minor variants as in English. Setting the locale prior to search restricts the results even at the primary level.
$ LC_COLLATE=sv_SE ./ugrep 1 cooperate < fun.txt
1: CooperateOne note about the tertiary level. It distinguishes not just case, but ligature presentation forms.
$ ./ugrep 3 fi < words.txt
6: fides
# vs
$ ./ugrep 2 fi < words.txt
5: final
6: fidesPretty flexible, right? Let’s see the code.
/*** ugrep.c ***/
#include Comparing strings modulo normalization
In the concepts section, we saw a single grapheme can be constructed with different combinations of codepoints. In many cases when comparing strings for equality, we’re most interested in the strings being perceived by the user in the same way rather than a simple byte-for-byte match.
The ICU library provides a unorm_compare function which returns a value similar to strcmp, and acts in a normalization independent way. It normalizes both strings incrementally while comparing them, so it can stop early if it finds a difference.
Here is code to check that the five ways of representing ộ are equivalent:
#include Output:
0 == 1: 0
1 == 2: 0
2 == 3: 0
3 == 4: 0
4 == 0: 0A return value of 0 means the strings are equal.
Confusable strings
Because Unicode introduces so many graphemes, there are more possibilities for scammers to confuse people using lookalike glyphs. For instance, domains like adoḅe.com or pаypal.com (with Cyrillic а) can direct unwary visitors to phishing sites. ICU contains an entire module for detecting “confusables,” those strings which are known to look too similar when rendered in common fonts. Each string is assigned a “skeleton” such that confusable strings get the same skeleton.
For an example, see my utility utofu. It has a little extra complexity with sqlite access code, so I am not reproducing it here. It’s designed to check Unicode strings to detect changes over time that might be spoofing.
The method of operation is this:
- Read line as UTF-8
- Convert to Normalization Form C for consistency
- Calculate skeleton string
- Insert UTF-8 version of normalized input and its skeleton into a database if the skeleton doesn’t already exist
- Compare the normalized input string to the string in the database having corresponding skeleton. If not an exact match die with an error.
Further reading
Unicode and internationalization is a huge topic. I could only scratch the surface in this article. I read and enjoyed sections from these books and reference materials, and would recommend them:
