libgo/go/unicode/utf8/utf8.go

   1 // Copyright 2009 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 utf8 implements functions and constants to support text encoded in
   6 // UTF-8. It includes functions to translate between runes and UTF-8 byte sequences.
   7 package utf8
   8
   9 import "unicode" // only needed for a couple of constants
  10
  11 // Numbers fundamental to the encoding.
  12 const (
  13         RuneError = unicode.ReplacementChar // the "error" Rune or "replacement character".
  14         RuneSelf  = 0x80                    // characters below Runeself are represented as themselves in a single byte.
  15         UTFMax    = 4                       // maximum number of bytes of a UTF-8 encoded Unicode character.
  16 )
  17
  18 const (
  19         t1 = 0x00 // 0000 0000
  20         tx = 0x80 // 1000 0000
  21         t2 = 0xC0 // 1100 0000
  22         t3 = 0xE0 // 1110 0000
  23         t4 = 0xF0 // 1111 0000
  24         t5 = 0xF8 // 1111 1000
  25
  26         maskx = 0x3F // 0011 1111
  27         mask2 = 0x1F // 0001 1111
  28         mask3 = 0x0F // 0000 1111
  29         mask4 = 0x07 // 0000 0111
  30
  31         rune1Max = 1<<7 - 1
  32         rune2Max = 1<<11 - 1
  33         rune3Max = 1<<16 - 1
  34         rune4Max = 1<<21 - 1
  35 )
  36
  37 func decodeRuneInternal(p []byte) (r rune, size int, short bool) {
  38         n := len(p)
  39         if n < 1 {
  40                 return RuneError, 0, true
  41         }
  42         c0 := p[0]
  43
  44         // 1-byte, 7-bit sequence?
  45         if c0 < tx {
  46                 return rune(c0), 1, false
  47         }
  48
  49         // unexpected continuation byte?
  50         if c0 < t2 {
  51                 return RuneError, 1, false
  52         }
  53
  54         // need first continuation byte
  55         if n < 2 {
  56                 return RuneError, 1, true
  57         }
  58         c1 := p[1]
  59         if c1 < tx || t2 <= c1 {
  60                 return RuneError, 1, false
  61         }
  62
  63         // 2-byte, 11-bit sequence?
  64         if c0 < t3 {
  65                 r = rune(c0&mask2)<<6 | rune(c1&maskx)
  66                 if r <= rune1Max {
  67                         return RuneError, 1, false
  68                 }
  69                 return r, 2, false
  70         }
  71
  72         // need second continuation byte
  73         if n < 3 {
  74                 return RuneError, 1, true
  75         }
  76         c2 := p[2]
  77         if c2 < tx || t2 <= c2 {
  78                 return RuneError, 1, false
  79         }
  80
  81         // 3-byte, 16-bit sequence?
  82         if c0 < t4 {
  83                 r = rune(c0&mask3)<<12 | rune(c1&maskx)<<6 | rune(c2&maskx)
  84                 if r <= rune2Max {
  85                         return RuneError, 1, false
  86                 }
  87                 return r, 3, false
  88         }
  89
  90         // need third continuation byte
  91         if n < 4 {
  92                 return RuneError, 1, true
  93         }
  94         c3 := p[3]
  95         if c3 < tx || t2 <= c3 {
  96                 return RuneError, 1, false
  97         }
  98
  99         // 4-byte, 21-bit sequence?
 100         if c0 < t5 {
 101                 r = rune(c0&mask4)<<18 | rune(c1&maskx)<<12 | rune(c2&maskx)<<6 | rune(c3&maskx)
 102                 if r <= rune3Max {
 103                         return RuneError, 1, false
 104                 }
 105                 return r, 4, false
 106         }
 107
 108         // error
 109         return RuneError, 1, false
 110 }
 111
 112 func decodeRuneInStringInternal(s string) (r rune, size int, short bool) {
 113         n := len(s)
 114         if n < 1 {
 115                 return RuneError, 0, true
 116         }
 117         c0 := s[0]
 118
 119         // 1-byte, 7-bit sequence?
 120         if c0 < tx {
 121                 return rune(c0), 1, false
 122         }
 123
 124         // unexpected continuation byte?
 125         if c0 < t2 {
 126                 return RuneError, 1, false
 127         }
 128
 129         // need first continuation byte
 130         if n < 2 {
 131                 return RuneError, 1, true
 132         }
 133         c1 := s[1]
 134         if c1 < tx || t2 <= c1 {
 135                 return RuneError, 1, false
 136         }
 137
 138         // 2-byte, 11-bit sequence?
 139         if c0 < t3 {
 140                 r = rune(c0&mask2)<<6 | rune(c1&maskx)
 141                 if r <= rune1Max {
 142                         return RuneError, 1, false
 143                 }
 144                 return r, 2, false
 145         }
 146
 147         // need second continuation byte
 148         if n < 3 {
 149                 return RuneError, 1, true
 150         }
 151         c2 := s[2]
 152         if c2 < tx || t2 <= c2 {
 153                 return RuneError, 1, false
 154         }
 155
 156         // 3-byte, 16-bit sequence?
 157         if c0 < t4 {
 158                 r = rune(c0&mask3)<<12 | rune(c1&maskx)<<6 | rune(c2&maskx)
 159                 if r <= rune2Max {
 160                         return RuneError, 1, false
 161                 }
 162                 return r, 3, false
 163         }
 164
 165         // need third continuation byte
 166         if n < 4 {
 167                 return RuneError, 1, true
 168         }
 169         c3 := s[3]
 170         if c3 < tx || t2 <= c3 {
 171                 return RuneError, 1, false
 172         }
 173
 174         // 4-byte, 21-bit sequence?
 175         if c0 < t5 {
 176                 r = rune(c0&mask4)<<18 | rune(c1&maskx)<<12 | rune(c2&maskx)<<6 | rune(c3&maskx)
 177                 if r <= rune3Max {
 178                         return RuneError, 1, false
 179                 }
 180                 return r, 4, false
 181         }
 182
 183         // error
 184         return RuneError, 1, false
 185 }
 186
 187 // FullRune reports whether the bytes in p begin with a full UTF-8 encoding of a rune.
 188 // An invalid encoding is considered a full Rune since it will convert as a width-1 error rune.
 189 func FullRune(p []byte) bool {
 190         _, _, short := decodeRuneInternal(p)
 191         return !short
 192 }
 193
 194 // FullRuneInString is like FullRune but its input is a string.
 195 func FullRuneInString(s string) bool {
 196         _, _, short := decodeRuneInStringInternal(s)
 197         return !short
 198 }
 199
 200 // DecodeRune unpacks the first UTF-8 encoding in p and returns the rune and its width in bytes.
 201 // If the encoding is invalid, it returns (RuneError, 1), an impossible result for correct UTF-8.
 202 func DecodeRune(p []byte) (r rune, size int) {
 203         r, size, _ = decodeRuneInternal(p)
 204         return
 205 }
 206
 207 // DecodeRuneInString is like DecodeRune but its input is a string.
 208 // If the encoding is invalid, it returns (RuneError, 1), an impossible result for correct UTF-8.
 209 func DecodeRuneInString(s string) (r rune, size int) {
 210         r, size, _ = decodeRuneInStringInternal(s)
 211         return
 212 }
 213
 214 // DecodeLastRune unpacks the last UTF-8 encoding in p and returns the rune and its width in bytes.
 215 // If the encoding is invalid, it returns (RuneError, 1), an impossible result for correct UTF-8.
 216 func DecodeLastRune(p []byte) (r rune, size int) {
 217         end := len(p)
 218         if end == 0 {
 219                 return RuneError, 0
 220         }
 221         start := end - 1
 222         r = rune(p[start])
 223         if r < RuneSelf {
 224                 return r, 1
 225         }
 226         // guard against O(n^2) behavior when traversing
 227         // backwards through strings with long sequences of
 228         // invalid UTF-8.
 229         lim := end - UTFMax
 230         if lim < 0 {
 231                 lim = 0
 232         }
 233         for start--; start >= lim; start-- {
 234                 if RuneStart(p[start]) {
 235                         break
 236                 }
 237         }
 238         if start < 0 {
 239                 start = 0
 240         }
 241         r, size = DecodeRune(p[start:end])
 242         if start+size != end {
 243                 return RuneError, 1
 244         }
 245         return r, size
 246 }
 247
 248 // DecodeLastRuneInString is like DecodeLastRune but its input is a string.
 249 // If the encoding is invalid, it returns (RuneError, 1), an impossible result for correct UTF-8.
 250 func DecodeLastRuneInString(s string) (r rune, size int) {
 251         end := len(s)
 252         if end == 0 {
 253                 return RuneError, 0
 254         }
 255         start := end - 1
 256         r = rune(s[start])
 257         if r < RuneSelf {
 258                 return r, 1
 259         }
 260         // guard against O(n^2) behavior when traversing
 261         // backwards through strings with long sequences of
 262         // invalid UTF-8.
 263         lim := end - UTFMax
 264         if lim < 0 {
 265                 lim = 0
 266         }
 267         for start--; start >= lim; start-- {
 268                 if RuneStart(s[start]) {
 269                         break
 270                 }
 271         }
 272         if start < 0 {
 273                 start = 0
 274         }
 275         r, size = DecodeRuneInString(s[start:end])
 276         if start+size != end {
 277                 return RuneError, 1
 278         }
 279         return r, size
 280 }
 281
 282 // RuneLen returns the number of bytes required to encode the rune.
 283 func RuneLen(r rune) int {
 284         switch {
 285         case r <= rune1Max:
 286                 return 1
 287         case r <= rune2Max:
 288                 return 2
 289         case r <= rune3Max:
 290                 return 3
 291         case r <= rune4Max:
 292                 return 4
 293         }
 294         return -1
 295 }
 296
 297 // EncodeRune writes into p (which must be large enough) the UTF-8 encoding of the rune.
 298 // It returns the number of bytes written.
 299 func EncodeRune(p []byte, r rune) int {
 300         // Negative values are erroneous.  Making it unsigned addresses the problem.
 301         if uint32(r) <= rune1Max {
 302                 p[0] = byte(r)
 303                 return 1
 304         }
 305
 306         if uint32(r) <= rune2Max {
 307                 p[0] = t2 | byte(r>>6)
 308                 p[1] = tx | byte(r)&maskx
 309                 return 2
 310         }
 311
 312         if uint32(r) > unicode.MaxRune {
 313                 r = RuneError
 314         }
 315
 316         if uint32(r) <= rune3Max {
 317                 p[0] = t3 | byte(r>>12)
 318                 p[1] = tx | byte(r>>6)&maskx
 319                 p[2] = tx | byte(r)&maskx
 320                 return 3
 321         }
 322
 323         p[0] = t4 | byte(r>>18)
 324         p[1] = tx | byte(r>>12)&maskx
 325         p[2] = tx | byte(r>>6)&maskx
 326         p[3] = tx | byte(r)&maskx
 327         return 4
 328 }
 329
 330 // RuneCount returns the number of runes in p.  Erroneous and short
 331 // encodings are treated as single runes of width 1 byte.
 332 func RuneCount(p []byte) int {
 333         i := 0
 334         var n int
 335         for n = 0; i < len(p); n++ {
 336                 if p[i] < RuneSelf {
 337                         i++
 338                 } else {
 339                         _, size := DecodeRune(p[i:])
 340                         i += size
 341                 }
 342         }
 343         return n
 344 }
 345
 346 // RuneCountInString is like RuneCount but its input is a string.
 347 func RuneCountInString(s string) (n int) {
 348         for _ = range s {
 349                 n++
 350         }
 351         return
 352 }
 353
 354 // RuneStart reports whether the byte could be the first byte of
 355 // an encoded rune.  Second and subsequent bytes always have the top
 356 // two bits set to 10.
 357 func RuneStart(b byte) bool { return b&0xC0 != 0x80 }
 358
 359 // Valid reports whether p consists entirely of valid UTF-8-encoded runes.
 360 func Valid(p []byte) bool {
 361         i := 0
 362         for i < len(p) {
 363                 if p[i] < RuneSelf {
 364                         i++
 365                 } else {
 366                         _, size := DecodeRune(p[i:])
 367                         if size == 1 {
 368                                 // All valid runes of size of 1 (those
 369                                 // below RuneSelf) were handled above.
 370                                 // This must be a RuneError.
 371                                 return false
 372                         }
 373                         i += size
 374                 }
 375         }
 376         return true
 377 }
 378
 379 // ValidString reports whether s consists entirely of valid UTF-8-encoded runes.
 380 func ValidString(s string) bool {
 381         for i, r := range s {
 382                 if r == RuneError {
 383                         // The RuneError value can be an error
 384                         // sentinel value (if it's size 1) or the same
 385                         // value encoded properly. Decode it to see if
 386                         // it's the 1 byte sentinel value.
 387                         _, size := DecodeRuneInString(s[i:])
 388                         if size == 1 {
 389                                 return false
 390                         }
 391                 }
 392         }
 393         return true
 394 }