1// Copyright 2014 The Go Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style 3// license that can be found in the LICENSE file. 4 5// +build ignore 6 7package main 8 9// This file contains definitions for interpreting the trie value of the case 10// trie generated by "go run gen*.go". It is shared by both the generator 11// program and the resultant package. Sharing is achieved by the generator 12// copying gen_trieval.go to trieval.go and changing what's above this comment. 13 14// info holds case information for a single rune. It is the value returned 15// by a trie lookup. Most mapping information can be stored in a single 16-bit 16// value. If not, for example when a rune is mapped to multiple runes, the value 17// stores some basic case data and an index into an array with additional data. 18// 19// The per-rune values have the following format: 20// 21// if (exception) { 22// 15..5 unsigned exception index 23// 4 unused 24// } else { 25// 15..8 XOR pattern or index to XOR pattern for case mapping 26// Only 13..8 are used for XOR patterns. 27// 7 inverseFold (fold to upper, not to lower) 28// 6 index: interpret the XOR pattern as an index 29// or isMid if case mode is cIgnorableUncased. 30// 5..4 CCC: zero (normal or break), above or other 31// } 32// 3 exception: interpret this value as an exception index 33// (TODO: is this bit necessary? Probably implied from case mode.) 34// 2..0 case mode 35// 36// For the non-exceptional cases, a rune must be either uncased, lowercase or 37// uppercase. If the rune is cased, the XOR pattern maps either a lowercase 38// rune to uppercase or an uppercase rune to lowercase (applied to the 10 39// least-significant bits of the rune). 40// 41// See the definitions below for a more detailed description of the various 42// bits. 43type info uint16 44 45const ( 46 casedMask = 0x0003 47 fullCasedMask = 0x0007 48 ignorableMask = 0x0006 49 ignorableValue = 0x0004 50 51 inverseFoldBit = 1 << 7 52 isMidBit = 1 << 6 53 54 exceptionBit = 1 << 3 55 exceptionShift = 5 56 numExceptionBits = 11 57 58 xorIndexBit = 1 << 6 59 xorShift = 8 60 61 // There is no mapping if all xor bits and the exception bit are zero. 62 hasMappingMask = 0xff80 | exceptionBit 63) 64 65// The case mode bits encodes the case type of a rune. This includes uncased, 66// title, upper and lower case and case ignorable. (For a definition of these 67// terms see Chapter 3 of The Unicode Standard Core Specification.) In some rare 68// cases, a rune can be both cased and case-ignorable. This is encoded by 69// cIgnorableCased. A rune of this type is always lower case. Some runes are 70// cased while not having a mapping. 71// 72// A common pattern for scripts in the Unicode standard is for upper and lower 73// case runes to alternate for increasing rune values (e.g. the accented Latin 74// ranges starting from U+0100 and U+1E00 among others and some Cyrillic 75// characters). We use this property by defining a cXORCase mode, where the case 76// mode (always upper or lower case) is derived from the rune value. As the XOR 77// pattern for case mappings is often identical for successive runes, using 78// cXORCase can result in large series of identical trie values. This, in turn, 79// allows us to better compress the trie blocks. 80const ( 81 cUncased info = iota // 000 82 cTitle // 001 83 cLower // 010 84 cUpper // 011 85 cIgnorableUncased // 100 86 cIgnorableCased // 101 // lower case if mappings exist 87 cXORCase // 11x // case is cLower | ((rune&1) ^ x) 88 89 maxCaseMode = cUpper 90) 91 92func (c info) isCased() bool { 93 return c&casedMask != 0 94} 95 96func (c info) isCaseIgnorable() bool { 97 return c&ignorableMask == ignorableValue 98} 99 100func (c info) isNotCasedAndNotCaseIgnorable() bool { 101 return c&fullCasedMask == 0 102} 103 104func (c info) isCaseIgnorableAndNotCased() bool { 105 return c&fullCasedMask == cIgnorableUncased 106} 107 108func (c info) isMid() bool { 109 return c&(fullCasedMask|isMidBit) == isMidBit|cIgnorableUncased 110} 111 112// The case mapping implementation will need to know about various Canonical 113// Combining Class (CCC) values. We encode two of these in the trie value: 114// cccZero (0) and cccAbove (230). If the value is cccOther, it means that 115// CCC(r) > 0, but not 230. A value of cccBreak means that CCC(r) == 0 and that 116// the rune also has the break category Break (see below). 117const ( 118 cccBreak info = iota << 4 119 cccZero 120 cccAbove 121 cccOther 122 123 cccMask = cccBreak | cccZero | cccAbove | cccOther 124) 125 126const ( 127 starter = 0 128 above = 230 129 iotaSubscript = 240 130) 131 132// The exceptions slice holds data that does not fit in a normal info entry. 133// The entry is pointed to by the exception index in an entry. It has the 134// following format: 135// 136// Header 137// byte 0: 138// 7..6 unused 139// 5..4 CCC type (same bits as entry) 140// 3 unused 141// 2..0 length of fold 142// 143// byte 1: 144// 7..6 unused 145// 5..3 length of 1st mapping of case type 146// 2..0 length of 2nd mapping of case type 147// 148// case 1st 2nd 149// lower -> upper, title 150// upper -> lower, title 151// title -> lower, upper 152// 153// Lengths with the value 0x7 indicate no value and implies no change. 154// A length of 0 indicates a mapping to zero-length string. 155// 156// Body bytes: 157// case folding bytes 158// lowercase mapping bytes 159// uppercase mapping bytes 160// titlecase mapping bytes 161// closure mapping bytes (for NFKC_Casefold). (TODO) 162// 163// Fallbacks: 164// missing fold -> lower 165// missing title -> upper 166// all missing -> original rune 167// 168// exceptions starts with a dummy byte to enforce that there is no zero index 169// value. 170const ( 171 lengthMask = 0x07 172 lengthBits = 3 173 noChange = 0 174) 175 176// References to generated trie. 177 178var trie = newCaseTrie(0) 179 180var sparse = sparseBlocks{ 181 values: sparseValues[:], 182 offsets: sparseOffsets[:], 183} 184 185// Sparse block lookup code. 186 187// valueRange is an entry in a sparse block. 188type valueRange struct { 189 value uint16 190 lo, hi byte 191} 192 193type sparseBlocks struct { 194 values []valueRange 195 offsets []uint16 196} 197 198// lookup returns the value from values block n for byte b using binary search. 199func (s *sparseBlocks) lookup(n uint32, b byte) uint16 { 200 lo := s.offsets[n] 201 hi := s.offsets[n+1] 202 for lo < hi { 203 m := lo + (hi-lo)/2 204 r := s.values[m] 205 if r.lo <= b && b <= r.hi { 206 return r.value 207 } 208 if b < r.lo { 209 hi = m 210 } else { 211 lo = m + 1 212 } 213 } 214 return 0 215} 216 217// lastRuneForTesting is the last rune used for testing. Everything after this 218// is boring. 219const lastRuneForTesting = rune(0x1FFFF) 220