1 // Copyright 2011 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.
7 // Trie table generator.
8 // Used by make*tables tools to generate a go file with trie data structures
9 // for mapping UTF-8 to a 16-bit value. All but the last byte in a UTF-8 byte
10 // sequence are used to lookup offsets in the index table to be used for the
11 // next byte. The last byte is used to index into a table with 16-bit values.
20 const maxSparseEntries = 16
22 type normCompacter struct {
23 sparseBlocks [][]uint64
29 func mostFrequentStride(a []uint64) int {
30 counts := make(map[int]int)
33 if stride := int(x) - v; v != 0 && stride >= 0 {
39 for stride, cnt := range counts {
40 if cnt > maxc || (cnt == maxc && stride < maxs) {
41 maxs, maxc = stride, cnt
47 func countSparseEntries(a []uint64) int {
48 stride := mostFrequentStride(a)
50 for _, tv := range a {
51 if int(tv)-v != stride {
61 func (c *normCompacter) Size(v []uint64) (sz int, ok bool) {
62 if n := countSparseEntries(v); n <= maxSparseEntries {
63 return (n+1)*4 + 2, true
68 func (c *normCompacter) Store(v []uint64) uint32 {
69 h := uint32(len(c.sparseOffset))
70 c.sparseBlocks = append(c.sparseBlocks, v)
71 c.sparseOffset = append(c.sparseOffset, uint16(c.sparseCount))
72 c.sparseCount += countSparseEntries(v) + 1
76 func (c *normCompacter) Handler() string {
77 return c.name + "Sparse.lookup"
80 func (c *normCompacter) Print(w io.Writer) (retErr error) {
81 p := func(f string, x ...interface{}) {
82 if _, err := fmt.Fprintf(w, f, x...); retErr == nil && err != nil {
87 ls := len(c.sparseBlocks)
88 p("// %sSparseOffset: %d entries, %d bytes\n", c.name, ls, ls*2)
89 p("var %sSparseOffset = %#v\n\n", c.name, c.sparseOffset)
92 p("// %sSparseValues: %d entries, %d bytes\n", c.name, ns, ns*4)
93 p("var %sSparseValues = [%d]valueRange {", c.name, ns)
94 for i, b := range c.sparseBlocks {
95 p("\n// Block %#x, offset %#x", i, c.sparseOffset[i])
97 stride := mostFrequentStride(b)
98 n := countSparseEntries(b)
99 p("\n{value:%#04x,lo:%#02x},", stride, uint8(n))
100 for i, nv := range b {
101 if int(nv)-v != stride {
103 p(",hi:%#02x},", 0x80+i-1)
106 p("\n{value:%#04x,lo:%#02x", nv, 0x80+i)
112 p(",hi:%#02x},", 0x80+len(b)-1)