.HTML "Modern Unicode Requires Modern Solutions".TLModern Unicode Requires Modern Solutions.AUJacob Moody.ABPlan 9 has a history with Unicode, the authors of which weredirectly involved with the creation and first system-wideimplementation of UTF-8. This should come as no surprise with thefocus on plaintext that permeated UNIX, and how that focus had carriedover into Plan 9. However, the world around Unicode has changed muchsince its early versions, becoming more complex and detailoriented as the version number climbs higher. While Plan 9 from BellLabs was never updated to any major version of Unicode beyond the first,9front has made incremental progress over the years in adopting newerstandards. We aim to evaluate the current state of the union withUnicode support, and different natural languages at large, within thecurrent 9front system, both where the system is at now and where wewould like it to go..AE.EQdelim $$.EN.SHBackground.PP.FSFirst presented in a slightly different form at the 10th International Workshop on Plan 9..FE.LPComputers do not handle abstract notions such as naturallanguage particularly well, so we rely on standards for representing naturallanguage as a sequence of numbers. The mapping ofnumbers to natural language characters is known as a characterencoding. While there have been many character encodingsinvented and used over the years, the one that has seen the mostwidespread adoption now is Unicode. Unicode is unique among othercharacter encodings before it in the fact that it plans to have asingle encoding for all natural languages, done in such a way that asingle document could contain language samples from all naturallanguages without out of band code page switching or the like (as wascommon before Unicode)..LPWith Unicode's goal of serving every natural language and thevast differences between natural languages there comes a need forcareful definition of terms that the standard uses[Glossary].To ensure some clarity let us get some of these definitions out in front:.TSl l^ ^l ll ll l^ ^.Abstract Character	A unit of information used for the organization, control,	or representation of textual data.Codepoint	Any value within the Unicode codespace. In convention with	traditional plan 9 terminology, we use rune as a synonym for codepoint.Encoded Character	A codepoint which has been mapped to an abstract characterGrapheme	A minimally distinctive unit of writing in the context of a particular	writing systemGlyph	The actual, concrete image of a glyph representation having been	rasterized or otherwise imaged onto some display surface..TE.LPWith that being said, let us define how these terms relate. Broadlyabstract characters are information that we wish to encode in thecharacter encoding, this is everything from graphemes, to grammarmarkings, to components of a letter, to informational controlcharacters. Unicode gives us a large bit space to work with, so acodepoint is a single index into that bitspace, the standard thengives us the mapping for relating these codepoints to abstractcharacters. A large majority (but not all) of encoded charactersrepresent graphemes. Graphemes are just one possible categorythat an encoded character can be within. Unicode only really defines theseencoded characters, the rendering and presentation of these encodedcharacters is the responsibility of the rendering layer who takesencoded characters as input and outputs glyph images..LPThe code space of Unicode is currently 21 bits, and with computinghardware mostly rounding that up to 32 bits, that can be a non-trivialamount of storage for large amounts of text. For this the Unicodestandard also defines a few compact encoding schemes, the mostpopular of which is.CW UTF-8 ,encoding the Unicode bit space within a variable number of bytes up to four..LPUnicode also provides multiple codepoints (or a sequence ofcodepoints) for representing the same abstract character. A largechunk of these characters are those which have been identified asbeing composed out of two or more subcomponents. The most commonexample of this are characters that have diacritical markings, whichcan either be represented as one codepoint for the "precomposed"variant or as a series of codepoints with the base codepoint firstfollowed by codepoints which denote individual diacritical markings..LPConsidering that there are multiple different representations of thesame abstract character, there is a method to normalize a series ofcodepoints into a consistent representation for semantic comparisons.The Unicode standard[UAX#15] does define a process for conducting thisnormalization, and provides 4 different forms to normalize to:.TSl l.NFC	Precomposed codepointsNFD	Decomposed codepointsNFKC	Precomposed compatibility codepointsNFKD	Decomposed compatibility codepoints.TE.LPThe compatibility forms here do additional conversion of specialformatted character sets such as codepoints for specific fonts,rotated variants, and so on into their basecounterparts. This operation loses some information regarding theoriginal codepoints thus is separated from typical normalization. Thereare some additional rules that are part of normalization so as toenable checking the semantic equivalence between any two sequence of codepoints..SHExisting Unicode in Plan 9.LPPlan 9 was an early adopter of Unicode, but never reached fullcompliance for any standard version of Unicode during its history.Pike et al put in a lot of work for handling UTF-8consistently within the system[Pike93] and a majority of the system wasupdated to handle codepoints. Plan 9's initial support couldbe defined succinctly as supporting "21-bit ASCII encoded as \f(CWUTF-8\fR",where each codepoint is assumed to be exactly one abstractcharacter and interfaces broadly assume that mutations to text (iebackspace in a text editor and the like) operate only on single codepoints as well. The result of this is that the system can only reallyhandle precomposed Unicode in any sort of ergonomic way, however Plan9 is very consistent in this level of support and has been ever since itslast official release..LPPlan 9 had initially only been written to support Unicode version 1.0(16-bit code space), so one of the earliest contributions from the communitywas to update this to the modern 21-bit code space. This work was firstdone in 9atom[9atom], and was later done in 9front. This includeswork to make more of the system Unicode aware that wasn'tpreviously. The version of awk which ships with the system is a notableexample. There were also some smaller changes like updates to theinput "compose" sequences to allow a wider range of codepoints andallowing users to manually input them by typing out theirdirect value in hexadecimal. However even with that work therehave been portions of 9front that had yet to still be updated pastUnicode version 1.0..SHUsing Tables to Keep Pace.LPThe work being presented in this paper largely started with wanting toupdate some of the existing interfaces within the system, namely the.CW isalpharune (2)set of functions, in order to not only bring them up to date,but also allow their adaptation to future versions of the standards.To that end, the Unicode consortium publishes aseries of informational databases[UAX#44] in an awk-friendly format. Plan 9 usersmay be familiar with one of these data files as the original.CW /lib/unicodewas a cut-down and reformatted version of the UnicodeCharacter Database (UnicodeData.txt). These files are updated andmaintained as the Unicode versions change, so the natural course ofaction seemed to be to read these files as input to generate code thatcould be then used to implement whatever functions we may need..LPTo better illustrate the input data, below is an excerpt of UnicodeData.txtfor U+2468. Each line of UnicodeData.txt corresponds to a single codepoint,with various properties of said codepoint separated by semicolons. Boththe keys and values for each field are documented by the Unicode standard[UAX#44]..P1; look -b 16 2468 /lib/ucd/UnicodeData.txt 2468;CIRCLED DIGIT NINE;No;0;ON;<circle> 0039;;9;9;N;;;;;.P2.LPThe parsing of these text input files is largely unremarkable, we readin one line at a time and denote properties and conversions as we moveourselves along. The challenge comes in picking and generating areasonable data structure for the function implementations to use,balancing both the size of the data structure in memory along with theruntime complexity for walking the data structure. Plan 9 binariesare currently quite small in comparison to the hardware available, sowe had decided to err on the side of increasing the binaries sizein exchange for better performance.Because of this we decided to implement direct lookuptables, using codepoints as an index and having an O(1) lookup timefor the vast majority of keys..LPWith that said, multiple arrays each with$2 sup 21$entries is quiteuntenable even given the potential performance savings. To mitigatethis we can use properties of the distribution of abstract charactersover the Unicode code space to our advantage. Unicode code space isdistributed up into chunks, with natural language roughly beingcontained within their own contiguous range of codepoints. Thismeans that for many of the properties we care about there are hotspotsand coldspots throughout the code space. As an example, you couldconsider the.CW toupperrune ()function, which largely is only applicableto natural languages which feature distinct letter cases. Manyeastern Asian languages have no concept of casing so those regionsof the Unicode code space don't need defined values. This makesthe lookup table quite sparse, and therefore a good candidatefor some method of compression. This is not unique to lettercasing, and in fact all of the lookup tables for.CW isalpharune (2)end up being sparse tables..LPTo compress the lookup table, we use a data structure that [Gillam02]referred to as a compact array. We start by breaking up the lookuptable into equally sized segments, then walk those segments and findany overlap (full or partial) between them. We can then remove any ofthe overlapped entries within the table. In order to access theseoverlapped segments we then need a higher level lookup table whichpoints into these segments of the lower table. In order to use asingle key (a codepoint in our case) for indexing in to both tables,we split up the bits within the key into two different portions, thetop bits indexing in to the top table, the result of which is added tothe bottom bits in order to index in to the bottom table..LPGiven how large the code space is for Unicode, it becomes beneficialto do not just one layer of compacting, but two, where the higherlookup table is compacted with the same method, resulting in a new toplevel lookup table. This splits up the codepoint into three parts,the result of the top level table being used to index themiddle table which is then used to index the bottom table whichcontains our desired value. The following code illustrates an exampleof this lookup method:.P1#define upperindex1(x) (((x)>>(4+7))&0x3FF)#define upperindex2(x) (((x)>>4)&0x7F)#define upperoffset(x) ((x)&0xF)#define upperlkup(x) (_upperdata[_upperidx2[_upperidx1[upperindex1(x)]	+ upperindex2(x)] + upperoffset(x)]).P2In this example, the top ten bits of the codepoint index the top levelindex, the result of which is combined with the next 7 bits of thecodepoint, with that result of that being added to the remaining 4bits of the codepoint. Which amount of bits to use for each section isnot exactly clear, so we brute forced the smallest table size throughtesting all possible values..LPOf course in order for this to be effective we need to ensure that thevalues of our lookup table are sparse. For simple property values thisis typically already the case, and for functions like.CW toupperrune ()we can instead store a delta between the current rune and the desiredrune, which gives us nice runs of zero values for anything without adefined transformation. Using this method we've gotten the followingresults for the.CW isalpharune (2)set of functions:.TSl ll n.Table	Size (bytes)toupper	12436tolower	11754totitle	12180is*rune	24184total	60554.TE.LPThe.CW is*rune ()table here merges all of the different categories intoone table as a bit field, one bit per possible category, so the resultis less sparse than the other tables. We find the expense of 60KB tobe well worth the benefits gained from the ease of upgrade, andconstant time lookup speed..SHKeeping Composure.LPRecall that normalization is the process of transforming a series ofUnicode codepoints into a canonical variant for a given target format.In order to do this, we'll need tables that map individual codepointsto their transformed values for each format, their composed or decomposedvariants. We can use tables largely similar to the ones described above, withsome extras where needed to handle more specific edge cases..LPFor decomposition our lookup key is the same as before, the codepointof the rune we wish to decompose. However the value of the table getsa bit more complex. The most straightforward approach would be tocombine the two new runes as one value, but this is fairly painfulfor the table size. We'd need a 42-bit value, which would have to berounded up to 64. Not only are we wasting over a third of the storagespace due to the rounding, but using 64-bit values would be quiteonerous for our 32-bit systems. As it turns out however, there is aheavy bias for the new decomposed runes to reside within the lower 16bit code space. In the latest version of Unicode at the time ofwriting (16.0) there are only 158 runes that result in decompositionsabove the 16-bit code space. It becomes easiest then to have ourcompact array use 32-bit values (two 16-bit codepoints), and thenhave an exceptions table which stores those 158 runes.The base table values for these exception runes are instead givenwithin a small portion of the Unicode private space (0xEEEE on up),with the difference from the start of the exception being used to index the list of exceptions.This allows us to maintain our constant time lookups, even whenaccessing members of the exception range..LPRecomposition required a different approach with similar constraintsas the decomposition. Instead of packing two runes into the output ofthe table we instead need to pack two runes into the input of ourlookup, and produce one rune as output. The bias towards the 16-bitcode space remains, so we can limit our main lookup table to takingtwo 16-bit runes as input and outputting a single 16-bit rune.For exceptions, (where either the input runes or output runes exceed 16 bits)we use a similar exception table. However in this case we have to search thislinearly because otherwise we would need to increase the table size to accomodatethe larger lookup keys. The differences from decomposition make it much harder to make use ofour existing lookup table, so we instead opted to implement a hashtable..LPA hash table is going to have a worse average lookup time compared toour compact arrays (assuming moderate collision), but stays within thesame ballpark of performance and size as our compact array. Becausewe're generating this table at build time instead of at run time, we haveto find a way of embedding the entire structure in a contiguous blockof memory. This is easy to accomplish for our first result of thehash function, where we have one large chunk of memory: we hash ourinput key then modulo it by the size of our initial memory buffer.For collisions however we need to find some way of chaining theresults in a way that can be searched until a key matches. For this wecreate another array that is appended onto the first.The main entry points are chained to thecollisions by embedding a numeric offset from the start of thecollision space. This results in a hash table entry that looks like thefollowing:.P1struct KV {	uint key;	ushort val;	ushort next;};.P2In the interest of saving as much space as possible for the generatedarray, we can compact this struct into a series of paired integers, thefirst being the merger of the two 16-bit codepoints, and the secondbeing the merger of the value and optionally the offset to the collision space..LPAs with choosing the constants for compact arrays, we found anoptimal size for the original hash array versus the collision arraylargely through brute force. Given the Unicode standard at the timeof writing, we are using 512 initial buckets, which forces 555 entriesinto the collision array. With a hash function that provides areasonable equal distribution, this should average to roughly only onecollision per entry. Using these two data structures results inthe following generated table sizes:.TSl ll n.Table	Size (bytes)decomp	20108recomp	8536.TE.SHNormalizing Theory.LPWith composition handled we can then start to tackle normalizing astring to one form or the other. The implementation of Unicodenormalization can be quite finicky and there are plenty ofconsiderations for how the input must be fed to result in conformantoutput. However before we can get into those, we need some additionaltables that will be used in the normalization process..LPThe first additional table we need is one that stores the.I "Combining Character Class".CW (ccc)of a codepoint, this is, the value which identifiesthe attaching property of the character. A value of non-zerosignifies that the codepoint is an attacher, the specific valuedenoting the group of attachers that it belongs to.Typically only one attacher out of each group may be consideredfor attachment to a base codepoint.The ccc value is also used to ensure the ordering of attachingcodepoints is consistent in.CW NFDformatted strings[UAX#15].The other value we need is the Quick Check (qc)value of a codepoint which is used to determine where a normalizationcontext ends in certain situations. We'll elaborate on this furtherin the following section. Our existing compactarray structure works well enough for these lookup tables as is,resulting in the following sizes:.TSl ll n.Table	Size (bytes)ccc	9738qc	7878.TE.LPThe abstract logic for normalization is described in [UAX#15] and isas follows:.P11. Decompose every rune possible in the string until it   can no longer be decomposed2. For codepoints without a ccc of zero, conduct a   stable sort of them based on their ccc value3. If we are normalizing to NFC, recursively recompose code   points in the string until there is nothing more to recompose.P2.LPThe main challenge for normalization then is designing an algorithmthat can do all of this on a single pass of the string. To accomplishthis, we iterate through a string and accumulate runes into a context.A context conceptually aims to localize the effect of normalization, breakingit down into chunks, such that a chunk can be processed independantly.This allows very large strings to be processed piecewise and withinreasonable memory boundaries. We implemented the context by using a stack,which is cleared and reused for multiple contexts as we parse through the string.The process by which we construct the first part of our context is as follows:.P11. Take the next rune from the string and push it onto our stack2. If the following rune has a ccc not equal to zero,   push it on the stack. Repeat until we encounter a rune with a   ccc of zero.3. Perform a stable sort of the stack by the ccc value of the codepoints.P2.LPAt this point if we are normalizing to a decomposed form (NFD) our contextis finished and may be flushed. Continuing the process again for the nextrune in the string..LPIf we're recomposing, we now must classify which type of context that we havebefore we continue.   Here we split into one of two recomposition strategies based on whichtype of context we have. Strategy A is used for sequences of codepointswhich have attachers (ccc of non-zero), and strategy B for sequencesof composable base runes (ccc of zero)..LP.P1ccc of non zero/Strategy A1.  Use the base codepoint as the left hand side input to our    recomposition2.  Use the next immediate codepoint as the right hand side input    to our recomposition.2a. If a match is found, replace the base rune with the new result    and discard the right hand size codepoint. The new codepoint will    be used as the base codepoint for further iterations.2b. If a match isn't found, skip through all other codepoints    in the stack that have the same ccc as the failed match.3.  Return to step 1 with and continue to attempt matches with    remaining codepoints in the stack until the stack is depleted..P2.LP.P1ccc of zero/Strategy B1.  Continue to pull codepoints on to the stack from the input    string until we reach a boundary, as described by the    Quick Check value.2.  Walk through each codepoint in the stack, attempting to    compose it with the codepoint immediately to the right of it.2a. If a match is found, replace the left hand side codepoint with    the result, and discard the right hand side codepoint.2b. If you don't find a match, continue through the stack with    the new left hand side being the current right hand side.3.  Go back to step 1 if any recomposition was found until we make a    pass without any recompositions..P2.LPAfter either of these two steps the resulting stack can be flushed outas normalized output. The stipulation to bypass other runes which havethe same ccc (step 2b in strategy A) is stipulated by the standard[UAX#15]and required for a conformant implementation..LPThere does exist an edge case in normalization, as the standard itselfputs no limit on the amount of attaching codepoints that may be given to abase codepoint. This can be seen in what is typicallyreferred to as "zalgo text", where a single base codepoint is givena large amount of attachers to produce a "glitchy" appearence.While there is no natural language whichrelies on a large number of attaching codepoints, it remains an edgecase our algorithm must come to terms with. In order to perform thisnormalization within a bounded memory constraint we need to pick somereasonable maximum amount of attaching codepoints that we plan to support.Unicode defined a subset of normalized text referred to as"Stream-Safe text"[UAX#15] which dictates that no more than 30 attaching codepoints may be given to a base codepoint, and for sequences larger than that,attaching codepoints can be broken up with.CW U+034F(Combining Grapheme Joiner). We implement this recommendation, which means ouralgorithm will insert a CGJ into a text stream if we encounter largeenough runs. This is required if we want to output properly normalizedtext, as without it the ccc context would grow to a length that wouldbe untenable to sort. The CGJ acts as a new base, and codepointswhich attach to it can be sorted independently of those on the basecodepoint. The rendering layer should be able to interpret theattaching codepoints on the CGJ as part of the previous base codepoint..SHNormalization Interface.LPWith the general algorithm for normalization figured out we need todecide on an interface for exposing this to other programs. Due to thenature of normalization this can be somewhat complicated to do well.As illustrated earlier, context expansion in both types of contextcontinues until we find the beginning of the next context. In strategyA it is until we find a ccc of zero and in strategy B it is until wefind qc boundary. This means that for most normalization we need to

Lines 1–500 of 696. Load more