URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [libgo/] [go/] [exp/] [norm/] [trie.go] - Blame information for rev 747

Details | Compare with Previous | View Log


// 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
 
type valueRange struct {
        value  uint16 // header: value:stride
        lo, hi byte   // header: lo:n
}
 
type trie struct {
        index        []uint8
        values       []uint16
        sparse       []valueRange
        sparseOffset []uint16
        cutoff       uint8 // indices >= cutoff are sparse
}
 
// lookupValue determines the type of block n and looks up the value for b.
// For n < t.cutoff, the block is a simple lookup table. Otherwise, the block
// is a list of ranges with an accompanying value. Given a matching range r,
// the value for b is by r.value + (b - r.lo) * stride.
func (t *trie) lookupValue(n uint8, b byte) uint16 {
        if n < t.cutoff {
                return t.values[uint16(n)<<6+uint16(b&maskx)]
        }
        offset := t.sparseOffset[n-t.cutoff]
        header := t.sparse[offset]
        lo := offset + 1
        hi := lo + uint16(header.lo)
        for lo < hi {
                m := lo + (hi-lo)/2
                r := t.sparse[m]
                if r.lo <= b && b <= r.hi {
                        return r.value + uint16(b-r.lo)*header.value
                }
                if b < r.lo {
                        hi = m
                } else {
                        lo = m + 1
                }
        }
        return 0
}
 
const (
        t1 = 0x00 // 0000 0000
        tx = 0x80 // 1000 0000
        t2 = 0xC0 // 1100 0000
        t3 = 0xE0 // 1110 0000
        t4 = 0xF0 // 1111 0000
        t5 = 0xF8 // 1111 1000
        t6 = 0xFC // 1111 1100
        te = 0xFE // 1111 1110
 
        maskx = 0x3F // 0011 1111
        mask2 = 0x1F // 0001 1111
        mask3 = 0x0F // 0000 1111
        mask4 = 0x07 // 0000 0111
)
 
// lookup returns the trie value for the first UTF-8 encoding in s and
// the width in bytes of this encoding. The size will be 0 if s does not
// hold enough bytes to complete the encoding. len(s) must be greater than 0.
func (t *trie) lookup(s []byte) (v uint16, sz int) {
        c0 := s[0]
        switch {
        case c0 < tx:
                return t.values[c0], 1
        case c0 < t2:
                return 0, 1
        case c0 < t3:
                if len(s) < 2 {
                        return 0, 0
                }
                i := t.index[c0]
                c1 := s[1]
                if c1 < tx || t2 <= c1 {
                        return 0, 1
                }
                return t.lookupValue(i, c1), 2
        case c0 < t4:
                if len(s) < 3 {
                        return 0, 0
                }
                i := t.index[c0]
                c1 := s[1]
                if c1 < tx || t2 <= c1 {
                        return 0, 1
                }
                o := uint16(i)<<6 + uint16(c1)&maskx
                i = t.index[o]
                c2 := s[2]
                if c2 < tx || t2 <= c2 {
                        return 0, 2
                }
                return t.lookupValue(i, c2), 3
        case c0 < t5:
                if len(s) < 4 {
                        return 0, 0
                }
                i := t.index[c0]
                c1 := s[1]
                if c1 < tx || t2 <= c1 {
                        return 0, 1
                }
                o := uint16(i)<<6 + uint16(c1)&maskx
                i = t.index[o]
                c2 := s[2]
                if c2 < tx || t2 <= c2 {
                        return 0, 2
                }
                o = uint16(i)<<6 + uint16(c2)&maskx
                i = t.index[o]
                c3 := s[3]
                if c3 < tx || t2 <= c3 {
                        return 0, 3
                }
                return t.lookupValue(i, c3), 4
        }
        // Illegal rune
        return 0, 1
}
 
// lookupString returns the trie value for the first UTF-8 encoding in s and
// the width in bytes of this encoding. The size will be 0 if s does not
// hold enough bytes to complete the encoding. len(s) must be greater than 0.
func (t *trie) lookupString(s string) (v uint16, sz int) {
        c0 := s[0]
        switch {
        case c0 < tx:
                return t.values[c0], 1
        case c0 < t2:
                return 0, 1
        case c0 < t3:
                if len(s) < 2 {
                        return 0, 0
                }
                i := t.index[c0]
                c1 := s[1]
                if c1 < tx || t2 <= c1 {
                        return 0, 1
                }
                return t.lookupValue(i, c1), 2
        case c0 < t4:
                if len(s) < 3 {
                        return 0, 0
                }
                i := t.index[c0]
                c1 := s[1]
                if c1 < tx || t2 <= c1 {
                        return 0, 1
                }
                o := uint16(i)<<6 + uint16(c1)&maskx
                i = t.index[o]
                c2 := s[2]
                if c2 < tx || t2 <= c2 {
                        return 0, 2
                }
                return t.lookupValue(i, c2), 3
        case c0 < t5:
                if len(s) < 4 {
                        return 0, 0
                }
                i := t.index[c0]
                c1 := s[1]
                if c1 < tx || t2 <= c1 {
                        return 0, 1
                }
                o := uint16(i)<<6 + uint16(c1)&maskx
                i = t.index[o]
                c2 := s[2]
                if c2 < tx || t2 <= c2 {
                        return 0, 2
                }
                o = uint16(i)<<6 + uint16(c2)&maskx
                i = t.index[o]
                c3 := s[3]
                if c3 < tx || t2 <= c3 {
                        return 0, 3
                }
                return t.lookupValue(i, c3), 4
        }
        // Illegal rune
        return 0, 1
}
 
// lookupUnsafe returns the trie value for the first UTF-8 encoding in s.
// s must hold a full encoding.
func (t *trie) lookupUnsafe(s []byte) uint16 {
        c0 := s[0]
        if c0 < tx {
                return t.values[c0]
        }
        if c0 < t2 {
                return 0
        }
        i := t.index[c0]
        if c0 < t3 {
                return t.lookupValue(i, s[1])
        }
        i = t.index[uint16(i)<<6+uint16(s[1])&maskx]
        if c0 < t4 {
                return t.lookupValue(i, s[2])
        }
        i = t.index[uint16(i)<<6+uint16(s[2])&maskx]
        if c0 < t5 {
                return t.lookupValue(i, s[3])
        }
        return 0
}
 
// lookupStringUnsafe returns the trie value for the first UTF-8 encoding in s.
// s must hold a full encoding.
func (t *trie) lookupStringUnsafe(s string) uint16 {
        c0 := s[0]
        if c0 < tx {
                return t.values[c0]
        }
        if c0 < t2 {
                return 0
        }
        i := t.index[c0]
        if c0 < t3 {
                return t.lookupValue(i, s[1])
        }
        i = t.index[uint16(i)<<6+uint16(s[1])&maskx]
        if c0 < t4 {
                return t.lookupValue(i, s[2])
        }
        i = t.index[uint16(i)<<6+uint16(s[2])&maskx]
        if c0 < t5 {
                return t.lookupValue(i, s[3])
        }
        return 0
}

Browse

Tools

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [libgo/] [go/] [exp/] [norm/] [trie.go] - Blame information for rev 747

Line No.	Rev	Author	Line
1	747	jeremybenn	`// 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.`
4
5			`package norm`
6
7			`type valueRange struct {`
8			`value uint16 // header: value:stride`
9			`lo, hi byte // header: lo:n`
10			`}`
11
12			`type trie struct {`
13			`index []uint8`
14			`values []uint16`
15			`sparse []valueRange`
16			`sparseOffset []uint16`
17			`cutoff uint8 // indices >= cutoff are sparse`
18			`}`
19
20			`// lookupValue determines the type of block n and looks up the value for b.`
21			`// For n < t.cutoff, the block is a simple lookup table. Otherwise, the block`
22			`// is a list of ranges with an accompanying value. Given a matching range r,`
23			`// the value for b is by r.value + (b - r.lo) * stride.`
24			`func (t *trie) lookupValue(n uint8, b byte) uint16 {`
25			`if n < t.cutoff {`
26			`return t.values[uint16(n)<<6+uint16(b&maskx)]`
27			`}`
28			`offset := t.sparseOffset[n-t.cutoff]`
29			`header := t.sparse[offset]`
30			`lo := offset + 1`
31			`hi := lo + uint16(header.lo)`
32			`for lo < hi {`
33			`m := lo + (hi-lo)/2`
34			`r := t.sparse[m]`
35			`if r.lo <= b && b <= r.hi {`
36			`return r.value + uint16(b-r.lo)*header.value`
37			`}`
38			`if b < r.lo {`
39			`hi = m`
40			`} else {`
41			`lo = m + 1`
42			`}`
43			`}`
44			`return 0`
45			`}`
46
47			`const (`
48			`t1 = 0x00 // 0000 0000`
49			`tx = 0x80 // 1000 0000`
50			`t2 = 0xC0 // 1100 0000`
51			`t3 = 0xE0 // 1110 0000`
52			`t4 = 0xF0 // 1111 0000`
53			`t5 = 0xF8 // 1111 1000`
54			`t6 = 0xFC // 1111 1100`
55			`te = 0xFE // 1111 1110`
56
57			`maskx = 0x3F // 0011 1111`
58			`mask2 = 0x1F // 0001 1111`
59			`mask3 = 0x0F // 0000 1111`
60			`mask4 = 0x07 // 0000 0111`
61			`)`
62
63			`// lookup returns the trie value for the first UTF-8 encoding in s and`
64			`// the width in bytes of this encoding. The size will be 0 if s does not`
65			`// hold enough bytes to complete the encoding. len(s) must be greater than 0.`
66			`func (t *trie) lookup(s []byte) (v uint16, sz int) {`
67			`c0 := s[0]`
68			`switch {`
69			`case c0 < tx:`
70			`return t.values[c0], 1`
71			`case c0 < t2:`
72			`return 0, 1`
73			`case c0 < t3:`
74			`if len(s) < 2 {`
75			`return 0, 0`
76			`}`
77			`i := t.index[c0]`
78			`c1 := s[1]`
79			`if c1 < tx \|\| t2 <= c1 {`
80			`return 0, 1`
81			`}`
82			`return t.lookupValue(i, c1), 2`
83			`case c0 < t4:`
84			`if len(s) < 3 {`
85			`return 0, 0`
86			`}`
87			`i := t.index[c0]`
88			`c1 := s[1]`
89			`if c1 < tx \|\| t2 <= c1 {`
90			`return 0, 1`
91			`}`
92			`o := uint16(i)<<6 + uint16(c1)&maskx`
93			`i = t.index[o]`
94			`c2 := s[2]`
95			`if c2 < tx \|\| t2 <= c2 {`
96			`return 0, 2`
97			`}`
98			`return t.lookupValue(i, c2), 3`
99			`case c0 < t5:`
100			`if len(s) < 4 {`
101			`return 0, 0`
102			`}`
103			`i := t.index[c0]`
104			`c1 := s[1]`
105			`if c1 < tx \|\| t2 <= c1 {`
106			`return 0, 1`
107			`}`
108			`o := uint16(i)<<6 + uint16(c1)&maskx`
109			`i = t.index[o]`
110			`c2 := s[2]`
111			`if c2 < tx \|\| t2 <= c2 {`
112			`return 0, 2`
113			`}`
114			`o = uint16(i)<<6 + uint16(c2)&maskx`
115			`i = t.index[o]`
116			`c3 := s[3]`
117			`if c3 < tx \|\| t2 <= c3 {`
118			`return 0, 3`
119			`}`
120			`return t.lookupValue(i, c3), 4`
121			`}`
122			`// Illegal rune`
123			`return 0, 1`
124			`}`
125
126			`// lookupString returns the trie value for the first UTF-8 encoding in s and`
127			`// the width in bytes of this encoding. The size will be 0 if s does not`
128			`// hold enough bytes to complete the encoding. len(s) must be greater than 0.`
129			`func (t *trie) lookupString(s string) (v uint16, sz int) {`
130			`c0 := s[0]`
131			`switch {`
132			`case c0 < tx:`
133			`return t.values[c0], 1`
134			`case c0 < t2:`
135			`return 0, 1`
136			`case c0 < t3:`
137			`if len(s) < 2 {`
138			`return 0, 0`
139			`}`
140			`i := t.index[c0]`
141			`c1 := s[1]`
142			`if c1 < tx \|\| t2 <= c1 {`
143			`return 0, 1`
144			`}`
145			`return t.lookupValue(i, c1), 2`
146			`case c0 < t4:`
147			`if len(s) < 3 {`
148			`return 0, 0`
149			`}`
150			`i := t.index[c0]`
151			`c1 := s[1]`
152			`if c1 < tx \|\| t2 <= c1 {`
153			`return 0, 1`
154			`}`
155			`o := uint16(i)<<6 + uint16(c1)&maskx`
156			`i = t.index[o]`
157			`c2 := s[2]`
158			`if c2 < tx \|\| t2 <= c2 {`
159			`return 0, 2`
160			`}`
161			`return t.lookupValue(i, c2), 3`
162			`case c0 < t5:`
163			`if len(s) < 4 {`
164			`return 0, 0`
165			`}`
166			`i := t.index[c0]`
167			`c1 := s[1]`
168			`if c1 < tx \|\| t2 <= c1 {`
169			`return 0, 1`
170			`}`
171			`o := uint16(i)<<6 + uint16(c1)&maskx`
172			`i = t.index[o]`
173			`c2 := s[2]`
174			`if c2 < tx \|\| t2 <= c2 {`
175			`return 0, 2`
176			`}`
177			`o = uint16(i)<<6 + uint16(c2)&maskx`
178			`i = t.index[o]`
179			`c3 := s[3]`
180			`if c3 < tx \|\| t2 <= c3 {`
181			`return 0, 3`
182			`}`
183			`return t.lookupValue(i, c3), 4`
184			`}`
185			`// Illegal rune`
186			`return 0, 1`
187			`}`
188
189			`// lookupUnsafe returns the trie value for the first UTF-8 encoding in s.`
190			`// s must hold a full encoding.`
191			`func (t *trie) lookupUnsafe(s []byte) uint16 {`
192			`c0 := s[0]`
193			`if c0 < tx {`
194			`return t.values[c0]`
195			`}`
196			`if c0 < t2 {`
197			`return 0`
198			`}`
199			`i := t.index[c0]`
200			`if c0 < t3 {`
201			`return t.lookupValue(i, s[1])`
202			`}`
203			`i = t.index[uint16(i)<<6+uint16(s[1])&maskx]`
204			`if c0 < t4 {`
205			`return t.lookupValue(i, s[2])`
206			`}`
207			`i = t.index[uint16(i)<<6+uint16(s[2])&maskx]`
208			`if c0 < t5 {`
209			`return t.lookupValue(i, s[3])`
210			`}`
211			`return 0`
212			`}`
213
214			`// lookupStringUnsafe returns the trie value for the first UTF-8 encoding in s.`
215			`// s must hold a full encoding.`
216			`func (t *trie) lookupStringUnsafe(s string) uint16 {`
217			`c0 := s[0]`
218			`if c0 < tx {`
219			`return t.values[c0]`
220			`}`
221			`if c0 < t2 {`
222			`return 0`
223			`}`
224			`i := t.index[c0]`
225			`if c0 < t3 {`
226			`return t.lookupValue(i, s[1])`
227			`}`
228			`i = t.index[uint16(i)<<6+uint16(s[1])&maskx]`
229			`if c0 < t4 {`
230			`return t.lookupValue(i, s[2])`
231			`}`
232			`i = t.index[uint16(i)<<6+uint16(s[2])&maskx]`
233			`if c0 < t5 {`
234			`return t.lookupValue(i, s[3])`
235			`}`
236			`return 0`
237			`}`