exp/norm: implementation of decomposition and composing functionality.

forminfo.go:
- Wrappers for table data.
- Per Form dispatch table.
composition.go:
- reorderBuffer type.  Implements decomposition, reordering, and composition.
- Note: decompose and decomposeString fields in formInfo could be replaced by
  a pointer to the trie for the respective form.  The proposed design makes
  testing easier, though.
normalization.go:
- Temporarily added panic("not implemented") methods to make the tests run.
  These will be removed again with the next CL, which will introduce the
  implementation.

R=r, rogpeppe, mpvl, rsc
CC=golang-dev
https://golang.org/cl/4875043

5 files changed, 709 insertions, 12 deletions

diff --git a/src/pkg/exp/norm/Makefile b/src/pkg/exp/norm/Makefile
index f14bc7025d..a4dfb43f7c 100644
--- a/src/pkg/exp/norm/Makefile
+++ b/src/pkg/exp/norm/Makefile
@@ -6,6 +6,9 @@ include ../../../Make.inc
 
 TARG=exp/norm
 GOFILES=\
+	composition.go\
+	forminfo.go\
+	normalize.go\
 	tables.go\
 	trie.go\
 
diff --git a/src/pkg/exp/norm/composition.go b/src/pkg/exp/norm/composition.go
new file mode 100644
index 0000000000..b2d2abaf63
--- /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
+}
diff --git a/src/pkg/exp/norm/composition_test.go b/src/pkg/exp/norm/composition_test.go
new file mode 100644
index 0000000000..195a0c1e8e
--- /dev/null
+++ b/src/pkg/exp/norm/composition_test.go
@@ -0,0 +1,138 @@
+// 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 "testing"
+
+// TestCase is used for most tests.
+type TestCase struct {
+	in  []int
+	out []int
+}
+
+type insertFunc func(rb *reorderBuffer, rune int) bool
+
+func insert(rb *reorderBuffer, rune int) bool {
+	b := []byte(string(rune))
+	return rb.insert(b, rb.f.info(b))
+}
+
+func insertString(rb *reorderBuffer, rune int) bool {
+	s := string(rune)
+	return rb.insertString(s, rb.f.infoString(s))
+}
+
+func runTests(t *testing.T, name string, rb *reorderBuffer, f insertFunc, tests []TestCase) {
+	for i, test := range tests {
+		rb.reset()
+		for j, rune := range test.in {
+			b := []byte(string(rune))
+			if !rb.insert(b, rb.f.info(b)) {
+				t.Errorf("%s:%d: insert failed for rune %d", name, i, j)
+			}
+		}
+		if rb.f.composing {
+			rb.compose()
+		}
+		if rb.nrune != len(test.out) {
+			t.Errorf("%s:%d: length = %d; want %d", name, i, rb.nrune, len(test.out))
+			continue
+		}
+		for j, want := range test.out {
+			found := int(rb.runeAt(j))
+			if found != want {
+				t.Errorf("%s:%d: runeAt(%d) = %U; want %U", name, i, j, found, want)
+			}
+		}
+	}
+}
+
+func TestFlush(t *testing.T) {
+	rb := &reorderBuffer{f: *formTable[NFC]}
+	out := make([]byte, 0)
+
+	out = rb.flush(out)
+	if len(out) != 0 {
+		t.Errorf("wrote bytes on flush of empty buffer. (len(out) = %d)", len(out))
+	}
+
+	for _, r := range []int("world!") {
+		insert(rb, r)
+	}
+
+	out = []byte("Hello ")
+	out = rb.flush(out)
+	want := "Hello world!"
+	if string(out) != want {
+		t.Errorf(`output after flush was "%s"; want "%s"`, string(out), want)
+	}
+	if rb.nrune != 0 {
+		t.Errorf("flush: non-null size of info buffer (rb.nrune == %d)", rb.nrune)
+	}
+	if rb.nbyte != 0 {
+		t.Errorf("flush: non-null size of byte buffer (rb.nbyte == %d)", rb.nbyte)
+	}
+}
+
+var insertTests = []TestCase{
+	{[]int{'a'}, []int{'a'}},
+	{[]int{0x300}, []int{0x300}},
+	{[]int{0x300, 0x316}, []int{0x316, 0x300}}, // CCC(0x300)==230; CCC(0x316)==220
+	{[]int{0x316, 0x300}, []int{0x316, 0x300}},
+	{[]int{0x41, 0x316, 0x300}, []int{0x41, 0x316, 0x300}},
+	{[]int{0x41, 0x300, 0x316}, []int{0x41, 0x316, 0x300}},
+	{[]int{0x300, 0x316, 0x41}, []int{0x316, 0x300, 0x41}},
+	{[]int{0x41, 0x300, 0x40, 0x316}, []int{0x41, 0x300, 0x40, 0x316}},
+}
+
+func TestInsert(t *testing.T) {
+	rb := &reorderBuffer{f: *formTable[NFD]}
+	runTests(t, "TestInsert", rb, insert, insertTests)
+}
+
+func TestInsertString(t *testing.T) {
+	rb := &reorderBuffer{f: *formTable[NFD]}
+	runTests(t, "TestInsertString", rb, insertString, insertTests)
+}
+
+var decompositionNFDTest = []TestCase{
+	{[]int{0xC0}, []int{0x41, 0x300}},
+	{[]int{0xAC00}, []int{0x1100, 0x1161}},
+	{[]int{0x01C4}, []int{0x01C4}},
+	{[]int{0x320E}, []int{0x320E}},
+	{[]int("음ẻ과"), []int{0x110B, 0x1173, 0x11B7, 0x65, 0x309, 0x1100, 0x116A}},
+}
+
+var decompositionNFKDTest = []TestCase{
+	{[]int{0xC0}, []int{0x41, 0x300}},
+	{[]int{0xAC00}, []int{0x1100, 0x1161}},
+	{[]int{0x01C4}, []int{0x44, 0x5A, 0x030C}},
+	{[]int{0x320E}, []int{0x28, 0x1100, 0x1161, 0x29}},
+}
+
+func TestDecomposition(t *testing.T) {
+	rb := &reorderBuffer{}
+	rb.f = *formTable[NFD]
+	runTests(t, "TestDecompositionNFD", rb, insert, decompositionNFDTest)
+	rb.f = *formTable[NFKD]
+	runTests(t, "TestDecompositionNFKD", rb, insert, decompositionNFKDTest)
+}
+
+var compositionTest = []TestCase{
+	{[]int{0x41, 0x300}, []int{0xC0}},
+	{[]int{0x41, 0x316}, []int{0x41, 0x316}},
+	{[]int{0x41, 0x300, 0x35D}, []int{0xC0, 0x35D}},
+	{[]int{0x41, 0x316, 0x300}, []int{0xC0, 0x316}},
+	// blocking starter
+	{[]int{0x41, 0x316, 0x40, 0x300}, []int{0x41, 0x316, 0x40, 0x300}},
+	{[]int{0x1100, 0x1161}, []int{0xAC00}},
+	// parenthesized Hangul, alternate between ASCII and Hangul.
+	{[]int{0x28, 0x1100, 0x1161, 0x29}, []int{0x28, 0xAC00, 0x29}},
+}
+
+func TestComposition(t *testing.T) {
+	rb := &reorderBuffer{f: *formTable[NFC]}
+	runTests(t, "TestComposition", rb, insert, compositionTest)
+}
diff --git a/src/pkg/exp/norm/forminfo.go b/src/pkg/exp/norm/forminfo.go
new file mode 100644
index 0000000000..ee3edb8ea7
--- /dev/null
+++ b/src/pkg/exp/norm/forminfo.go
@@ -0,0 +1,188 @@
+// 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
+
+// This file contains Form-specific logic and wrappers for data in tables.go.
+
+type runeInfo struct {
+	pos   uint8  // start position in reorderBuffer; used in composition.go
+	size  uint8  // length of UTF-8 encoding of this rune
+	ccc   uint8  // canonical combining class
+	flags qcInfo // quick check flags
+}
+
+// functions dispatchable per form
+type boundaryFunc func(f *formInfo, info runeInfo) bool
+type lookupFunc func(b []byte) runeInfo
+type lookupFuncString func(s string) runeInfo
+type decompFunc func(b []byte) []byte
+type decompFuncString func(s string) []byte
+
+// formInfo holds Form-specific functions and tables.
+type formInfo struct {
+	form Form
+
+	composing, compatibility bool // form type
+
+	decompose       decompFunc
+	decomposeString decompFuncString
+	info            lookupFunc
+	infoString      lookupFuncString
+	boundaryBefore  boundaryFunc
+	boundaryAfter   boundaryFunc
+}
+
+var formTable []*formInfo
+
+func init() {
+	formTable = make([]*formInfo, 4)
+
+	for i := range formTable {
+		f := &formInfo{}
+		formTable[i] = f
+		f.form = Form(i)
+		if Form(i) == NFKD || Form(i) == NFKC {
+			f.compatibility = true
+			f.decompose = decomposeNFKC
+			f.decomposeString = decomposeStringNFKC
+			f.info = lookupInfoNFKC
+			f.infoString = lookupInfoStringNFKC
+		} else {
+			f.decompose = decomposeNFC
+			f.decomposeString = decomposeStringNFC
+			f.info = lookupInfoNFC
+			f.infoString = lookupInfoStringNFC
+		}
+		if Form(i) == NFC || Form(i) == NFKC {
+			f.composing = true
+			f.boundaryBefore = compBoundaryBefore
+			f.boundaryAfter = compBoundaryAfter
+		} else {
+			f.boundaryBefore = decompBoundary
+			f.boundaryAfter = decompBoundary
+		}
+	}
+}
+
+func decompBoundary(f *formInfo, info runeInfo) bool {
+	if info.ccc == 0 && info.flags.isYesD() { // Implies isHangul(b) == true
+		return true
+	}
+	// We assume that the CCC of the first character in a decomposition
+	// is always non-zero if different from info.ccc and that we can return
+	// false at this point. This is verified by maketables.
+	return false
+}
+
+func compBoundaryBefore(f *formInfo, info runeInfo) bool {
+	if info.ccc == 0 && info.flags.isYesC() {
+		return true
+	}
+	// We assume that the CCC of the first character in a decomposition
+	// is always non-zero if different from info.ccc and that we can return
+	// false at this point. This is verified by maketables.
+	return false
+}
+
+func compBoundaryAfter(f *formInfo, info runeInfo) bool {
+	// This misses values where the last char in a decomposition is a
+	// boundary such as Hangul with JamoT.
+	// TODO(mpvl): verify this does not lead to segments that do
+	// not fit in the reorderBuffer.
+	return info.flags.isInert()
+}
+
+// We pack quick check data in 4 bits:
+//   0:    NFD_QC Yes (0) or No (1). No also means there is a decomposition.
+//   1..2: NFC_QC Yes(00), No (01), or Maybe (11)
+//   3:    Combines forward  (0 == false, 1 == true)
+// 
+// When all 4 bits are zero, the character is inert, meaning it is never
+// influenced by normalization.
+//
+// We pack the bits for both NFC/D and NFKC/D in one byte.
+type qcInfo uint8
+
+func (i qcInfo) isYesC() bool  { return i&0x2 == 0 }
+func (i qcInfo) isNoC() bool   { return i&0x6 == 0x2 }
+func (i qcInfo) isMaybe() bool { return i&0x4 != 0 }
+func (i qcInfo) isYesD() bool  { return i&0x1 == 0 }
+func (i qcInfo) isNoD() bool   { return i&0x1 != 0 }
+func (i qcInfo) isInert() bool { return i&0xf == 0 }
+
+func (i qcInfo) combinesForward() bool  { return i&0x8 != 0 }
+func (i qcInfo) combinesBackward() bool { return i&0x4 != 0 } // == isMaybe
+func (i qcInfo) hasDecomposition() bool { return i&0x1 != 0 } // == isNoD
+
+// Wrappers for tables.go
+
+// The 16-bit value of the decompostion tries is an index into a byte
+// array of UTF-8 decomposition sequences. The first byte is the number
+// of bytes in the decomposition (excluding this length byte). The actual
+// sequence starts at the offset+1.
+func decomposeNFC(b []byte) []byte {
+	p := nfcDecompTrie.lookupUnsafe(b)
+	n := decomps[p]
+	p++
+	return decomps[p : p+uint16(n)]
+}
+
+func decomposeNFKC(b []byte) []byte {
+	p := nfkcDecompTrie.lookupUnsafe(b)
+	n := decomps[p]
+	p++
+	return decomps[p : p+uint16(n)]
+}
+
+func decomposeStringNFC(s string) []byte {
+	p := nfcDecompTrie.lookupStringUnsafe(s)
+	n := decomps[p]
+	p++
+	return decomps[p : p+uint16(n)]
+}
+
+func decomposeStringNFKC(s string) []byte {
+	p := nfkcDecompTrie.lookupStringUnsafe(s)
+	n := decomps[p]
+	p++
+	return decomps[p : p+uint16(n)]
+}
+
+// Recomposition
+// We use 32-bit keys instead of 64-bit for the two codepoint keys.
+// This clips off the bits of three entries, but we know this will not
+// result in a collision. In the unlikely event that changes to
+// UnicodeData.txt introduce collisions, the compiler will catch it.
+// Note that the recomposition map for NFC and NFKC are identical.
+
+// combine returns the combined rune or 0 if it doesn't exist.
+func combine(a, b uint32) uint32 {
+	key := uint32(uint16(a))<<16 + uint32(uint16(b))
+	return recompMap[key]
+}
+
+// The 16-bit character info has the following bit layout:
+//    0..7   CCC value.
+//    8..11  qcInfo for NFC/NFD
+//   12..15  qcInfo for NFKC/NFKD
+func lookupInfoNFC(b []byte) runeInfo {
+	v, sz := charInfoTrie.lookup(b)
+	return runeInfo{0, uint8(sz), uint8(v), qcInfo(v >> 8)}
+}
+
+func lookupInfoStringNFC(s string) runeInfo {
+	v, sz := charInfoTrie.lookupString(s)
+	return runeInfo{0, uint8(sz), uint8(v), qcInfo(v >> 8)}
+}
+
+func lookupInfoNFKC(b []byte) runeInfo {
+	v, sz := charInfoTrie.lookup(b)
+	return runeInfo{0, uint8(sz), uint8(v), qcInfo(v >> 12)}
+}
+
+func lookupInfoStringNFKC(s string) runeInfo {
+	v, sz := charInfoTrie.lookupString(s)
+	return runeInfo{0, uint8(sz), uint8(v), qcInfo(v >> 12)}
+}
diff --git a/src/pkg/exp/norm/normalize.go b/src/pkg/exp/norm/normalize.go
index 81311bfcbd..e9d18dd9ea 100644
--- a/src/pkg/exp/norm/normalize.go
+++ b/src/pkg/exp/norm/normalize.go
@@ -31,45 +31,69 @@ const (
 )
 
 // Bytes returns f(b). May return b if f(b) = b.
-func (f Form) Bytes(b []byte) []byte
+func (f Form) Bytes(b []byte) []byte {
+	panic("not implemented")
+}
 
 // String returns f(s).
-func (f Form) String(s string) string
+func (f Form) String(s string) string {
+	panic("not implemented")
+}
 
 // IsNormal returns true if b == f(b).
-func (f Form) IsNormal(b []byte) bool
+func (f Form) IsNormal(b []byte) bool {
+	panic("not implemented")
+}
 
 // IsNormalString returns true if s == f(s).
-func (f Form) IsNormalString(s string) bool
+func (f Form) IsNormalString(s string) bool {
+	panic("not implemented")
+}
 
 // Append returns f(append(out, b...)).
 // The buffer out must be empty or equal to f(out).
-func (f Form) Append(out, b []byte) []byte
+func (f Form) Append(out, b []byte) []byte {
+	panic("not implemented")
+}
 
 // AppendString returns f(append(out, []byte(s))).
 // The buffer out must be empty or equal to f(out).
-func (f Form) AppendString(out []byte, s string) []byte
+func (f Form) AppendString(out []byte, s string) []byte {
+	panic("not implemented")
+}
 
 // QuickSpan returns a boundary n such that b[0:n] == f(b[0:n]).
 // It is not guaranteed to return the largest such n.
-func (f Form) QuickSpan(b []byte) int
+func (f Form) QuickSpan(b []byte) int {
+	panic("not implemented")
+}
 
 // QuickSpanString returns a boundary n such that b[0:n] == f(s[0:n]).
 // It is not guaranteed to return the largest such n.
-func (f Form) QuickSpanString(s string) int
+func (f Form) QuickSpanString(s string) int {
+	panic("not implemented")
+}
 
 // FirstBoundary returns the position i of the first boundary in b.
 // It returns len(b), false if b contains no boundaries.
-func (f Form) FirstBoundary(b []byte) (i int, ok bool)
+func (f Form) FirstBoundary(b []byte) (i int, ok bool) {
+	panic("not implemented")
+}
 
 // FirstBoundaryInString return the position i of the first boundary in s.
 // It returns len(s), false if s contains no boundaries.
-func (f Form) FirstBoundaryInString(s string) (i int, ok bool)
+func (f Form) FirstBoundaryInString(s string) (i int, ok bool) {
+	panic("not implemented")
+}
 
 // LastBoundaryIn returns the position i of the last boundary in b.
 // It returns 0, false if b contains no boundary.
-func (f Form) LastBoundary(b []byte) (i int, ok bool)
+func (f Form) LastBoundary(b []byte) (i int, ok bool) {
+	panic("not implemented")
+}
 
 // LastBoundaryInString returns the position i of the last boundary in s.
 // It returns 0, false if s contains no boundary.
-func (f Form) LastBoundaryInString(s string) (i int, ok bool)
+func (f Form) LastBoundaryInString(s string) (i int, ok bool) {
+	panic("not implemented")
+}