libgo/go/exp/norm/trie.go

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