|
Packit Service |
4d2de5 |
// Copyright 2011 The Go Authors. All rights reserved.
|
|
Packit Service |
4d2de5 |
// Use of this source code is governed by a BSD-style
|
|
Packit Service |
4d2de5 |
// license that can be found in the LICENSE file.
|
|
Packit Service |
4d2de5 |
|
|
Packit Service |
4d2de5 |
// +build ignore
|
|
Packit Service |
4d2de5 |
|
|
Packit Service |
4d2de5 |
// Trie table generator.
|
|
Packit Service |
4d2de5 |
// Used by make*tables tools to generate a go file with trie data structures
|
|
Packit Service |
4d2de5 |
// for mapping UTF-8 to a 16-bit value. All but the last byte in a UTF-8 byte
|
|
Packit Service |
4d2de5 |
// sequence are used to lookup offsets in the index table to be used for the
|
|
Packit Service |
4d2de5 |
// next byte. The last byte is used to index into a table with 16-bit values.
|
|
Packit Service |
4d2de5 |
|
|
Packit Service |
4d2de5 |
package main
|
|
Packit Service |
4d2de5 |
|
|
Packit Service |
4d2de5 |
import (
|
|
Packit Service |
4d2de5 |
"fmt"
|
|
Packit Service |
4d2de5 |
"io"
|
|
Packit Service |
4d2de5 |
)
|
|
Packit Service |
4d2de5 |
|
|
Packit Service |
4d2de5 |
const maxSparseEntries = 16
|
|
Packit Service |
4d2de5 |
|
|
Packit Service |
4d2de5 |
type normCompacter struct {
|
|
Packit Service |
4d2de5 |
sparseBlocks [][]uint64
|
|
Packit Service |
4d2de5 |
sparseOffset []uint16
|
|
Packit Service |
4d2de5 |
sparseCount int
|
|
Packit Service |
4d2de5 |
name string
|
|
Packit Service |
4d2de5 |
}
|
|
Packit Service |
4d2de5 |
|
|
Packit Service |
4d2de5 |
func mostFrequentStride(a []uint64) int {
|
|
Packit Service |
4d2de5 |
counts := make(map[int]int)
|
|
Packit Service |
4d2de5 |
var v int
|
|
Packit Service |
4d2de5 |
for _, x := range a {
|
|
Packit Service |
4d2de5 |
if stride := int(x) - v; v != 0 && stride >= 0 {
|
|
Packit Service |
4d2de5 |
counts[stride]++
|
|
Packit Service |
4d2de5 |
}
|
|
Packit Service |
4d2de5 |
v = int(x)
|
|
Packit Service |
4d2de5 |
}
|
|
Packit Service |
4d2de5 |
var maxs, maxc int
|
|
Packit Service |
4d2de5 |
for stride, cnt := range counts {
|
|
Packit Service |
4d2de5 |
if cnt > maxc || (cnt == maxc && stride < maxs) {
|
|
Packit Service |
4d2de5 |
maxs, maxc = stride, cnt
|
|
Packit Service |
4d2de5 |
}
|
|
Packit Service |
4d2de5 |
}
|
|
Packit Service |
4d2de5 |
return maxs
|
|
Packit Service |
4d2de5 |
}
|
|
Packit Service |
4d2de5 |
|
|
Packit Service |
4d2de5 |
func countSparseEntries(a []uint64) int {
|
|
Packit Service |
4d2de5 |
stride := mostFrequentStride(a)
|
|
Packit Service |
4d2de5 |
var v, count int
|
|
Packit Service |
4d2de5 |
for _, tv := range a {
|
|
Packit Service |
4d2de5 |
if int(tv)-v != stride {
|
|
Packit Service |
4d2de5 |
if tv != 0 {
|
|
Packit Service |
4d2de5 |
count++
|
|
Packit Service |
4d2de5 |
}
|
|
Packit Service |
4d2de5 |
}
|
|
Packit Service |
4d2de5 |
v = int(tv)
|
|
Packit Service |
4d2de5 |
}
|
|
Packit Service |
4d2de5 |
return count
|
|
Packit Service |
4d2de5 |
}
|
|
Packit Service |
4d2de5 |
|
|
Packit Service |
4d2de5 |
func (c *normCompacter) Size(v []uint64) (sz int, ok bool) {
|
|
Packit Service |
4d2de5 |
if n := countSparseEntries(v); n <= maxSparseEntries {
|
|
Packit Service |
4d2de5 |
return (n+1)*4 + 2, true
|
|
Packit Service |
4d2de5 |
}
|
|
Packit Service |
4d2de5 |
return 0, false
|
|
Packit Service |
4d2de5 |
}
|
|
Packit Service |
4d2de5 |
|
|
Packit Service |
4d2de5 |
func (c *normCompacter) Store(v []uint64) uint32 {
|
|
Packit Service |
4d2de5 |
h := uint32(len(c.sparseOffset))
|
|
Packit Service |
4d2de5 |
c.sparseBlocks = append(c.sparseBlocks, v)
|
|
Packit Service |
4d2de5 |
c.sparseOffset = append(c.sparseOffset, uint16(c.sparseCount))
|
|
Packit Service |
4d2de5 |
c.sparseCount += countSparseEntries(v) + 1
|
|
Packit Service |
4d2de5 |
return h
|
|
Packit Service |
4d2de5 |
}
|
|
Packit Service |
4d2de5 |
|
|
Packit Service |
4d2de5 |
func (c *normCompacter) Handler() string {
|
|
Packit Service |
4d2de5 |
return c.name + "Sparse.lookup"
|
|
Packit Service |
4d2de5 |
}
|
|
Packit Service |
4d2de5 |
|
|
Packit Service |
4d2de5 |
func (c *normCompacter) Print(w io.Writer) (retErr error) {
|
|
Packit Service |
4d2de5 |
p := func(f string, x ...interface{}) {
|
|
Packit Service |
4d2de5 |
if _, err := fmt.Fprintf(w, f, x...); retErr == nil && err != nil {
|
|
Packit Service |
4d2de5 |
retErr = err
|
|
Packit Service |
4d2de5 |
}
|
|
Packit Service |
4d2de5 |
}
|
|
Packit Service |
4d2de5 |
|
|
Packit Service |
4d2de5 |
ls := len(c.sparseBlocks)
|
|
Packit Service |
4d2de5 |
p("// %sSparseOffset: %d entries, %d bytes\n", c.name, ls, ls*2)
|
|
Packit Service |
4d2de5 |
p("var %sSparseOffset = %#v\n\n", c.name, c.sparseOffset)
|
|
Packit Service |
4d2de5 |
|
|
Packit Service |
4d2de5 |
ns := c.sparseCount
|
|
Packit Service |
4d2de5 |
p("// %sSparseValues: %d entries, %d bytes\n", c.name, ns, ns*4)
|
|
Packit Service |
4d2de5 |
p("var %sSparseValues = [%d]valueRange {", c.name, ns)
|
|
Packit Service |
4d2de5 |
for i, b := range c.sparseBlocks {
|
|
Packit Service |
4d2de5 |
p("\n// Block %#x, offset %#x", i, c.sparseOffset[i])
|
|
Packit Service |
4d2de5 |
var v int
|
|
Packit Service |
4d2de5 |
stride := mostFrequentStride(b)
|
|
Packit Service |
4d2de5 |
n := countSparseEntries(b)
|
|
Packit Service |
4d2de5 |
p("\n{value:%#04x,lo:%#02x},", stride, uint8(n))
|
|
Packit Service |
4d2de5 |
for i, nv := range b {
|
|
Packit Service |
4d2de5 |
if int(nv)-v != stride {
|
|
Packit Service |
4d2de5 |
if v != 0 {
|
|
Packit Service |
4d2de5 |
p(",hi:%#02x},", 0x80+i-1)
|
|
Packit Service |
4d2de5 |
}
|
|
Packit Service |
4d2de5 |
if nv != 0 {
|
|
Packit Service |
4d2de5 |
p("\n{value:%#04x,lo:%#02x", nv, 0x80+i)
|
|
Packit Service |
4d2de5 |
}
|
|
Packit Service |
4d2de5 |
}
|
|
Packit Service |
4d2de5 |
v = int(nv)
|
|
Packit Service |
4d2de5 |
}
|
|
Packit Service |
4d2de5 |
if v != 0 {
|
|
Packit Service |
4d2de5 |
p(",hi:%#02x},", 0x80+len(b)-1)
|
|
Packit Service |
4d2de5 |
}
|
|
Packit Service |
4d2de5 |
}
|
|
Packit Service |
4d2de5 |
p("\n}\n\n")
|
|
Packit Service |
4d2de5 |
return
|
|
Packit Service |
4d2de5 |
}
|