diff options
Diffstat (limited to 'src/pkg/exp/norm/composition.go')
| -rw-r--r-- | src/pkg/exp/norm/composition.go | 344 |
1 files changed, 344 insertions, 0 deletions
diff --git a/src/pkg/exp/norm/composition.go b/src/pkg/exp/norm/composition.go new file mode 100644 index 000000000..b2d2abaf6 --- /dev/null +++ b/src/pkg/exp/norm/composition.go @@ -0,0 +1,344 @@ +// Copyright 2011 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package norm + +import "utf8" + +const ( + maxCombiningChars = 30 + 2 // +2 to hold CGJ and Hangul overflow. + maxBackRunes = maxCombiningChars - 1 + maxNFCExpansion = 3 // NFC(0x1D160) + maxNFKCExpansion = 18 // NFKC(0xFDFA) + + maxRuneSizeInDecomp = 4 + // Need to multiply by 2 as we don't reuse byte buffer space for recombining. + maxByteBufferSize = 2 * maxRuneSizeInDecomp * maxCombiningChars // 256 +) + +// reorderBuffer is used to normalize a single segment. Characters inserted with +// insert() are decomposed and reordered based on CCC. The compose() method can +// be used to recombine characters. Note that the byte buffer does not hold +// the UTF-8 characters in order. Only the rune array is maintained in sorted +// order. flush() writes the resulting segment to a byte array. +type reorderBuffer struct { + rune [maxCombiningChars]runeInfo // Per character info. + byte [maxByteBufferSize]byte // UTF-8 buffer. Referenced by runeInfo.pos. + nrune int // Number of runeInfos. + nbyte uint8 // Number or bytes. + f formInfo +} + +// reset discards all characters from the buffer. +func (rb *reorderBuffer) reset() { + rb.nrune = 0 + rb.nbyte = 0 +} + +// flush appends the normalized segment to out and resets rb. +func (rb *reorderBuffer) flush(out []byte) []byte { + for i := 0; i < rb.nrune; i++ { + start := rb.rune[i].pos + end := start + rb.rune[i].size + out = append(out, rb.byte[start:end]...) + } + rb.reset() + return out +} + +// insertOrdered inserts a rune in the buffer, ordered by Canonical Combining Class. +// It returns false if the buffer is not large enough to hold the rune. +// It is used internally by insert. +func (rb *reorderBuffer) insertOrdered(info runeInfo) bool { + n := rb.nrune + if n >= maxCombiningChars { + return false + } + b := rb.rune[:] + cc := info.ccc + if cc > 0 { + // Find insertion position + move elements to make room. + for ; n > 0; n-- { + if b[n-1].ccc <= cc { + break + } + b[n] = b[n-1] + } + } + rb.nrune += 1 + pos := uint8(rb.nbyte) + rb.nbyte += info.size + info.pos = pos + b[n] = info + return true +} + +// insert inserts the given rune in the buffer ordered by CCC. +// It returns true if the buffer was large enough to hold the decomposed rune. +func (rb *reorderBuffer) insert(src []byte, info runeInfo) bool { + if info.size == 3 && isHangul(src) { + rune, _ := utf8.DecodeRune(src) + return rb.decomposeHangul(uint32(rune)) + } + pos := rb.nbyte + if info.flags.hasDecomposition() { + dcomp := rb.f.decompose(src) + for i := 0; i < len(dcomp); i += int(info.size) { + info = rb.f.info(dcomp[i:]) + if !rb.insertOrdered(info) { + return false + } + } + copy(rb.byte[pos:], dcomp) + } else { + if !rb.insertOrdered(info) { + return false + } + copy(rb.byte[pos:], src[:info.size]) + } + return true +} + +// insertString inserts the given rune in the buffer ordered by CCC. +// It returns true if the buffer was large enough to hold the decomposed rune. +func (rb *reorderBuffer) insertString(src string, info runeInfo) bool { + if info.size == 3 && isHangulString(src) { + rune, _ := utf8.DecodeRuneInString(src) + return rb.decomposeHangul(uint32(rune)) + } + pos := rb.nbyte + dcomp := rb.f.decomposeString(src) + dn := len(dcomp) + if dn != 0 { + for i := 0; i < dn; i += int(info.size) { + info = rb.f.info(dcomp[i:]) + if !rb.insertOrdered(info) { + return false + } + } + copy(rb.byte[pos:], dcomp) + } else { + if !rb.insertOrdered(info) { + return false + } + copy(rb.byte[pos:], src[:info.size]) + } + return true +} + +// appendRune inserts a rune at the end of the buffer. It is used for Hangul. +func (rb *reorderBuffer) appendRune(rune uint32) { + bn := rb.nbyte + sz := utf8.EncodeRune(rb.byte[bn:], int(rune)) + rb.nbyte += uint8(sz) + rb.rune[rb.nrune] = runeInfo{bn, uint8(sz), 0, 0} + rb.nrune++ +} + +// assignRune sets a rune at position pos. It is used for Hangul and recomposition. +func (rb *reorderBuffer) assignRune(pos int, rune uint32) { + bn := rb.nbyte + sz := utf8.EncodeRune(rb.byte[bn:], int(rune)) + rb.rune[pos] = runeInfo{bn, uint8(sz), 0, 0} + rb.nbyte += uint8(sz) +} + +// runeAt returns the rune at position n. It is used for Hangul and recomposition. +func (rb *reorderBuffer) runeAt(n int) uint32 { + inf := rb.rune[n] + rune, _ := utf8.DecodeRune(rb.byte[inf.pos : inf.pos+inf.size]) + return uint32(rune) +} + +// bytesAt returns the UTF-8 encoding of the rune at position n. +// It is used for Hangul and recomposition. +func (rb *reorderBuffer) bytesAt(n int) []byte { + inf := rb.rune[n] + return rb.byte[inf.pos : int(inf.pos)+int(inf.size)] +} + +// For Hangul we combine algorithmically, instead of using tables. +const ( + hangulBase = 0xAC00 // UTF-8(hangulBase) -> EA B0 80 + hangulBase0 = 0xEA + hangulBase1 = 0xB0 + hangulBase2 = 0x80 + + hangulEnd = hangulBase + jamoLVTCount // UTF-8(0xD7A4) -> ED 9E A4 + hangulEnd0 = 0xED + hangulEnd1 = 0x9E + hangulEnd2 = 0xA4 + + jamoLBase = 0x1100 // UTF-8(jamoLBase) -> E1 84 00 + jamoLBase0 = 0xE1 + jamoLBase1 = 0x84 + jamoLEnd = 0x1113 + jamoVBase = 0x1161 + jamoVEnd = 0x1176 + jamoTBase = 0x11A7 + jamoTEnd = 0x11C3 + + jamoTCount = 28 + jamoVCount = 21 + jamoVTCount = 21 * 28 + jamoLVTCount = 19 * 21 * 28 +) + +// Caller must verify that len(b) >= 3. +func isHangul(b []byte) bool { + b0 := b[0] + if b0 < hangulBase0 { + return false + } + b1 := b[1] + switch { + case b0 == hangulBase0: + return b1 >= hangulBase1 + case b0 < hangulEnd0: + return true + case b0 > hangulEnd0: + return false + case b1 < hangulEnd1: + return true + } + return b1 == hangulEnd1 && b[2] < hangulEnd2 +} + +// Caller must verify that len(b) >= 3. +func isHangulString(b string) bool { + b0 := b[0] + if b0 < hangulBase0 { + return false + } + b1 := b[1] + switch { + case b0 == hangulBase0: + return b1 >= hangulBase1 + case b0 < hangulEnd0: + return true + case b0 > hangulEnd0: + return false + case b1 < hangulEnd1: + return true + } + return b1 == hangulEnd1 && b[2] < hangulEnd2 +} + +// Caller must ensure len(b) >= 2. +func isJamoVT(b []byte) bool { + // True if (rune & 0xff00) == jamoLBase + return b[0] == jamoLBase0 && (b[1]&0xFC) == jamoLBase1 +} + +func isHangulWithoutJamoT(b []byte) bool { + c, _ := utf8.DecodeRune(b) + c -= hangulBase + return c < jamoLVTCount && c%jamoTCount == 0 +} + +// decomposeHangul algorithmically decomposes a Hangul rune into +// its Jamo components. +// See http://unicode.org/reports/tr15/#Hangul for details on decomposing Hangul. +func (rb *reorderBuffer) decomposeHangul(rune uint32) bool { + b := rb.rune[:] + n := rb.nrune + if n+3 > len(b) { + return false + } + rune -= hangulBase + x := rune % jamoTCount + rune /= jamoTCount + rb.appendRune(jamoLBase + rune/jamoVCount) + rb.appendRune(jamoVBase + rune%jamoVCount) + if x != 0 { + rb.appendRune(jamoTBase + x) + } + return true +} + +// combineHangul algorithmically combines Jamo character components into Hangul. +// See http://unicode.org/reports/tr15/#Hangul for details on combining Hangul. +func (rb *reorderBuffer) combineHangul() { + k := 1 + b := rb.rune[:] + bn := rb.nrune + for s, i := 0, 1; i < bn; i++ { + cccB := b[k-1].ccc + cccC := b[i].ccc + if cccB == 0 { + s = k - 1 + } + if s != k-1 && cccB >= cccC { + // b[i] is blocked by greater-equal cccX below it + b[k] = b[i] + k++ + } else { + l := rb.runeAt(s) // also used to compare to hangulBase + v := rb.runeAt(i) // also used to compare to jamoT + switch { + case jamoLBase <= l && l < jamoLEnd && + jamoVBase <= v && v < jamoVEnd: + // 11xx plus 116x to LV + rb.assignRune(s, hangulBase+ + (l-jamoLBase)*jamoVTCount+(v-jamoVBase)*jamoTCount) + case hangulBase <= l && l < hangulEnd && + jamoTBase < v && v < jamoTEnd && + ((l-hangulBase)%jamoTCount) == 0: + // ACxx plus 11Ax to LVT + rb.assignRune(s, l+v-jamoTBase) + default: + b[k] = b[i] + k++ + } + } + } + rb.nrune = k +} + +// compose recombines the runes in the buffer. +// It should only be used to recompose a single segment, as it will not +// handle alternations between Hangul and non-Hangul characters correctly. +func (rb *reorderBuffer) compose() { + // UAX #15, section X5 , including Corrigendum #5 + // "In any character sequence beginning with starter S, a character C is + // blocked from S if and only if there is some character B between S + // and C, and either B is a starter or it has the same or higher + // combining class as C." + k := 1 + b := rb.rune[:] + bn := rb.nrune + for s, i := 0, 1; i < bn; i++ { + if isJamoVT(rb.bytesAt(i)) { + // Redo from start in Hangul mode. Necessary to support + // U+320E..U+321E in NFKC mode. + rb.combineHangul() + return + } + ii := b[i] + // We can only use combineForward as a filter if we later + // get the info for the combined character. This is more + // expensive than using the filter. Using combinesBackward() + // is safe. + if ii.flags.combinesBackward() { + cccB := b[k-1].ccc + cccC := ii.ccc + blocked := false // b[i] blocked by starter or greater or equal CCC? + if cccB == 0 { + s = k - 1 + } else { + blocked = s != k-1 && cccB >= cccC + } + if !blocked { + combined := combine(rb.runeAt(s), rb.runeAt(i)) + if combined != 0 { + rb.assignRune(s, combined) + continue + } + } + } + b[k] = b[i] + k++ + } + rb.nrune = k +} |