Subversion Repositories openrisc

// 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
}