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  // See https://en.wikipedia.org/wiki/UTF-8
     8  package utf8
     9  
    10  // The conditions RuneError==unicode.ReplacementChar and
    11  // MaxRune==unicode.MaxRune are verified in the tests.
    12  // Defining them locally avoids this package depending on package unicode.
    13  
    14  // Numbers fundamental to the encoding.
    15  const (
    16  	RuneError = '\uFFFD'     // the "error" Rune or "Unicode replacement character"
    17  	RuneSelf  = 0x80         // characters below RuneSelf are represented as themselves in a single byte.
    18  	MaxRune   = '\U0010FFFF' // Maximum valid Unicode code point.
    19  	UTFMax    = 4            // maximum number of bytes of a UTF-8 encoded Unicode character.
    20  )
    21  
    22  // Code points in the surrogate range are not valid for UTF-8.
    23  const (
    24  	surrogateMin = 0xD800
    25  	surrogateMax = 0xDFFF
    26  )
    27  
    28  const (
    29  	t1 = 0b00000000
    30  	tx = 0b10000000
    31  	t2 = 0b11000000
    32  	t3 = 0b11100000
    33  	t4 = 0b11110000
    34  	t5 = 0b11111000
    35  
    36  	maskx = 0b00111111
    37  	mask2 = 0b00011111
    38  	mask3 = 0b00001111
    39  	mask4 = 0b00000111
    40  
    41  	rune1Max = 1<<7 - 1
    42  	rune2Max = 1<<11 - 1
    43  	rune3Max = 1<<16 - 1
    44  
    45  	// The default lowest and highest continuation byte.
    46  	locb = 0b10000000
    47  	hicb = 0b10111111
    48  
    49  	// These names of these constants are chosen to give nice alignment in the
    50  	// table below. The first nibble is an index into acceptRanges or F for
    51  	// special one-byte cases. The second nibble is the Rune length or the
    52  	// Status for the special one-byte case.
    53  	xx = 0xF1 // invalid: size 1
    54  	as = 0xF0 // ASCII: size 1
    55  	s1 = 0x02 // accept 0, size 2
    56  	s2 = 0x13 // accept 1, size 3
    57  	s3 = 0x03 // accept 0, size 3
    58  	s4 = 0x23 // accept 2, size 3
    59  	s5 = 0x34 // accept 3, size 4
    60  	s6 = 0x04 // accept 0, size 4
    61  	s7 = 0x44 // accept 4, size 4
    62  )
    63  
    64  const (
    65  	runeErrorByte0 = t3 | (RuneError >> 12)
    66  	runeErrorByte1 = tx | (RuneError>>6)&maskx
    67  	runeErrorByte2 = tx | RuneError&maskx
    68  )
    69  
    70  // first is information about the first byte in a UTF-8 sequence.
    71  var first = [256]uint8{
    72  	//   1   2   3   4   5   6   7   8   9   A   B   C   D   E   F
    73  	as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, // 0x00-0x0F
    74  	as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, // 0x10-0x1F
    75  	as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, // 0x20-0x2F
    76  	as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, // 0x30-0x3F
    77  	as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, // 0x40-0x4F
    78  	as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, // 0x50-0x5F
    79  	as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, // 0x60-0x6F
    80  	as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, // 0x70-0x7F
    81  	//   1   2   3   4   5   6   7   8   9   A   B   C   D   E   F
    82  	xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, // 0x80-0x8F
    83  	xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, // 0x90-0x9F
    84  	xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, // 0xA0-0xAF
    85  	xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, // 0xB0-0xBF
    86  	xx, xx, s1, s1, s1, s1, s1, s1, s1, s1, s1, s1, s1, s1, s1, s1, // 0xC0-0xCF
    87  	s1, s1, s1, s1, s1, s1, s1, s1, s1, s1, s1, s1, s1, s1, s1, s1, // 0xD0-0xDF
    88  	s2, s3, s3, s3, s3, s3, s3, s3, s3, s3, s3, s3, s3, s4, s3, s3, // 0xE0-0xEF
    89  	s5, s6, s6, s6, s7, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, // 0xF0-0xFF
    90  }
    91  
    92  // acceptRange gives the range of valid values for the second byte in a UTF-8
    93  // sequence.
    94  type acceptRange struct {
    95  	lo uint8 // lowest value for second byte.
    96  	hi uint8 // highest value for second byte.
    97  }
    98  
    99  // acceptRanges has size 16 to avoid bounds checks in the code that uses it.
   100  var acceptRanges = [16]acceptRange{
   101  	0: {locb, hicb},
   102  	1: {0xA0, hicb},
   103  	2: {locb, 0x9F},
   104  	3: {0x90, hicb},
   105  	4: {locb, 0x8F},
   106  }
   107  
   108  // FullRune reports whether the bytes in p begin with a full UTF-8 encoding of a rune.
   109  // An invalid encoding is considered a full Rune since it will convert as a width-1 error rune.
   110  func FullRune(p []byte) bool {
   111  	n := len(p)
   112  	if n == 0 {
   113  		return false
   114  	}
   115  	x := first[p[0]]
   116  	if n >= int(x&7) {
   117  		return true // ASCII, invalid or valid.
   118  	}
   119  	// Must be short or invalid.
   120  	accept := acceptRanges[x>>4]
   121  	if n > 1 && (p[1] < accept.lo || accept.hi < p[1]) {
   122  		return true
   123  	} else if n > 2 && (p[2] < locb || hicb < p[2]) {
   124  		return true
   125  	}
   126  	return false
   127  }
   128  
   129  // FullRuneInString is like FullRune but its input is a string.
   130  func FullRuneInString(s string) bool {
   131  	n := len(s)
   132  	if n == 0 {
   133  		return false
   134  	}
   135  	x := first[s[0]]
   136  	if n >= int(x&7) {
   137  		return true // ASCII, invalid, or valid.
   138  	}
   139  	// Must be short or invalid.
   140  	accept := acceptRanges[x>>4]
   141  	if n > 1 && (s[1] < accept.lo || accept.hi < s[1]) {
   142  		return true
   143  	} else if n > 2 && (s[2] < locb || hicb < s[2]) {
   144  		return true
   145  	}
   146  	return false
   147  }
   148  
   149  // DecodeRune unpacks the first UTF-8 encoding in p and returns the rune and
   150  // its width in bytes. If p is empty it returns ([RuneError], 0). Otherwise, if
   151  // the encoding is invalid, it returns (RuneError, 1). Both are impossible
   152  // results for correct, non-empty UTF-8.
   153  //
   154  // An encoding is invalid if it is incorrect UTF-8, encodes a rune that is
   155  // out of range, or is not the shortest possible UTF-8 encoding for the
   156  // value. No other validation is performed.
   157  func DecodeRune(p []byte) (r rune, size int) {
   158  	n := len(p)
   159  	if n < 1 {
   160  		return RuneError, 0
   161  	}
   162  	p0 := p[0]
   163  	x := first[p0]
   164  	if x >= as {
   165  		// The following code simulates an additional check for x == xx and
   166  		// handling the ASCII and invalid cases accordingly. This mask-and-or
   167  		// approach prevents an additional branch.
   168  		mask := rune(x) << 31 >> 31 // Create 0x0000 or 0xFFFF.
   169  		return rune(p[0])&^mask | RuneError&mask, 1
   170  	}
   171  	sz := int(x & 7)
   172  	accept := acceptRanges[x>>4]
   173  	if n < sz {
   174  		return RuneError, 1
   175  	}
   176  	b1 := p[1]
   177  	if b1 < accept.lo || accept.hi < b1 {
   178  		return RuneError, 1
   179  	}
   180  	if sz <= 2 { // <= instead of == to help the compiler eliminate some bounds checks
   181  		return rune(p0&mask2)<<6 | rune(b1&maskx), 2
   182  	}
   183  	b2 := p[2]
   184  	if b2 < locb || hicb < b2 {
   185  		return RuneError, 1
   186  	}
   187  	if sz <= 3 {
   188  		return rune(p0&mask3)<<12 | rune(b1&maskx)<<6 | rune(b2&maskx), 3
   189  	}
   190  	b3 := p[3]
   191  	if b3 < locb || hicb < b3 {
   192  		return RuneError, 1
   193  	}
   194  	return rune(p0&mask4)<<18 | rune(b1&maskx)<<12 | rune(b2&maskx)<<6 | rune(b3&maskx), 4
   195  }
   196  
   197  // DecodeRuneInString is like [DecodeRune] but its input is a string. If s is
   198  // empty it returns ([RuneError], 0). Otherwise, if the encoding is invalid, it
   199  // returns (RuneError, 1). Both are impossible results for correct, non-empty
   200  // UTF-8.
   201  //
   202  // An encoding is invalid if it is incorrect UTF-8, encodes a rune that is
   203  // out of range, or is not the shortest possible UTF-8 encoding for the
   204  // value. No other validation is performed.
   205  func DecodeRuneInString(s string) (r rune, size int) {
   206  	n := len(s)
   207  	if n < 1 {
   208  		return RuneError, 0
   209  	}
   210  	s0 := s[0]
   211  	x := first[s0]
   212  	if x >= as {
   213  		// The following code simulates an additional check for x == xx and
   214  		// handling the ASCII and invalid cases accordingly. This mask-and-or
   215  		// approach prevents an additional branch.
   216  		mask := rune(x) << 31 >> 31 // Create 0x0000 or 0xFFFF.
   217  		return rune(s[0])&^mask | RuneError&mask, 1
   218  	}
   219  	sz := int(x & 7)
   220  	accept := acceptRanges[x>>4]
   221  	if n < sz {
   222  		return RuneError, 1
   223  	}
   224  	s1 := s[1]
   225  	if s1 < accept.lo || accept.hi < s1 {
   226  		return RuneError, 1
   227  	}
   228  	if sz <= 2 { // <= instead of == to help the compiler eliminate some bounds checks
   229  		return rune(s0&mask2)<<6 | rune(s1&maskx), 2
   230  	}
   231  	s2 := s[2]
   232  	if s2 < locb || hicb < s2 {
   233  		return RuneError, 1
   234  	}
   235  	if sz <= 3 {
   236  		return rune(s0&mask3)<<12 | rune(s1&maskx)<<6 | rune(s2&maskx), 3
   237  	}
   238  	s3 := s[3]
   239  	if s3 < locb || hicb < s3 {
   240  		return RuneError, 1
   241  	}
   242  	return rune(s0&mask4)<<18 | rune(s1&maskx)<<12 | rune(s2&maskx)<<6 | rune(s3&maskx), 4
   243  }
   244  
   245  // DecodeLastRune unpacks the last UTF-8 encoding in p and returns the rune and
   246  // its width in bytes. If p is empty it returns ([RuneError], 0). Otherwise, if
   247  // the encoding is invalid, it returns (RuneError, 1). Both are impossible
   248  // results for correct, non-empty UTF-8.
   249  //
   250  // An encoding is invalid if it is incorrect UTF-8, encodes a rune that is
   251  // out of range, or is not the shortest possible UTF-8 encoding for the
   252  // value. No other validation is performed.
   253  func DecodeLastRune(p []byte) (r rune, size int) {
   254  	end := len(p)
   255  	if end == 0 {
   256  		return RuneError, 0
   257  	}
   258  	start := end - 1
   259  	r = rune(p[start])
   260  	if r < RuneSelf {
   261  		return r, 1
   262  	}
   263  	// guard against O(n^2) behavior when traversing
   264  	// backwards through strings with long sequences of
   265  	// invalid UTF-8.
   266  	lim := max(end-UTFMax, 0)
   267  	for start--; start >= lim; start-- {
   268  		if RuneStart(p[start]) {
   269  			break
   270  		}
   271  	}
   272  	if start < 0 {
   273  		start = 0
   274  	}
   275  	r, size = DecodeRune(p[start:end])
   276  	if start+size != end {
   277  		return RuneError, 1
   278  	}
   279  	return r, size
   280  }
   281  
   282  // DecodeLastRuneInString is like [DecodeLastRune] but its input is a string. If
   283  // s is empty it returns ([RuneError], 0). Otherwise, if the encoding is invalid,
   284  // it returns (RuneError, 1). Both are impossible results for correct,
   285  // non-empty UTF-8.
   286  //
   287  // An encoding is invalid if it is incorrect UTF-8, encodes a rune that is
   288  // out of range, or is not the shortest possible UTF-8 encoding for the
   289  // value. No other validation is performed.
   290  func DecodeLastRuneInString(s string) (r rune, size int) {
   291  	end := len(s)
   292  	if end == 0 {
   293  		return RuneError, 0
   294  	}
   295  	start := end - 1
   296  	r = rune(s[start])
   297  	if r < RuneSelf {
   298  		return r, 1
   299  	}
   300  	// guard against O(n^2) behavior when traversing
   301  	// backwards through strings with long sequences of
   302  	// invalid UTF-8.
   303  	lim := max(end-UTFMax, 0)
   304  	for start--; start >= lim; start-- {
   305  		if RuneStart(s[start]) {
   306  			break
   307  		}
   308  	}
   309  	if start < 0 {
   310  		start = 0
   311  	}
   312  	r, size = DecodeRuneInString(s[start:end])
   313  	if start+size != end {
   314  		return RuneError, 1
   315  	}
   316  	return r, size
   317  }
   318  
   319  // RuneLen returns the number of bytes in the UTF-8 encoding of the rune.
   320  // It returns -1 if the rune is not a valid value to encode in UTF-8.
   321  func RuneLen(r rune) int {
   322  	switch {
   323  	case r < 0:
   324  		return -1
   325  	case r <= rune1Max:
   326  		return 1
   327  	case r <= rune2Max:
   328  		return 2
   329  	case surrogateMin <= r && r <= surrogateMax:
   330  		return -1
   331  	case r <= rune3Max:
   332  		return 3
   333  	case r <= MaxRune:
   334  		return 4
   335  	}
   336  	return -1
   337  }
   338  
   339  // EncodeRune writes into p (which must be large enough) the UTF-8 encoding of the rune.
   340  // If the rune is out of range, it writes the encoding of [RuneError].
   341  // It returns the number of bytes written.
   342  func EncodeRune(p []byte, r rune) int {
   343  	// This function is inlineable for fast handling of ASCII.
   344  	if uint32(r) <= rune1Max {
   345  		p[0] = byte(r)
   346  		return 1
   347  	}
   348  	return encodeRuneNonASCII(p, r)
   349  }
   350  
   351  func encodeRuneNonASCII(p []byte, r rune) int {
   352  	// Negative values are erroneous. Making it unsigned addresses the problem.
   353  	switch i := uint32(r); {
   354  	case i <= rune2Max:
   355  		_ = p[1] // eliminate bounds checks
   356  		p[0] = t2 | byte(r>>6)
   357  		p[1] = tx | byte(r)&maskx
   358  		return 2
   359  	case i < surrogateMin, surrogateMax < i && i <= rune3Max:
   360  		_ = p[2] // eliminate bounds checks
   361  		p[0] = t3 | byte(r>>12)
   362  		p[1] = tx | byte(r>>6)&maskx
   363  		p[2] = tx | byte(r)&maskx
   364  		return 3
   365  	case i > rune3Max && i <= MaxRune:
   366  		_ = p[3] // eliminate bounds checks
   367  		p[0] = t4 | byte(r>>18)
   368  		p[1] = tx | byte(r>>12)&maskx
   369  		p[2] = tx | byte(r>>6)&maskx
   370  		p[3] = tx | byte(r)&maskx
   371  		return 4
   372  	default:
   373  		_ = p[2] // eliminate bounds checks
   374  		p[0] = runeErrorByte0
   375  		p[1] = runeErrorByte1
   376  		p[2] = runeErrorByte2
   377  		return 3
   378  	}
   379  }
   380  
   381  // AppendRune appends the UTF-8 encoding of r to the end of p and
   382  // returns the extended buffer. If the rune is out of range,
   383  // it appends the encoding of [RuneError].
   384  func AppendRune(p []byte, r rune) []byte {
   385  	// This function is inlineable for fast handling of ASCII.
   386  	if uint32(r) <= rune1Max {
   387  		return append(p, byte(r))
   388  	}
   389  	return appendRuneNonASCII(p, r)
   390  }
   391  
   392  func appendRuneNonASCII(p []byte, r rune) []byte {
   393  	// Negative values are erroneous. Making it unsigned addresses the problem.
   394  	switch i := uint32(r); {
   395  	case i <= rune2Max:
   396  		return append(p, t2|byte(r>>6), tx|byte(r)&maskx)
   397  	case i < surrogateMin, surrogateMax < i && i <= rune3Max:
   398  		return append(p, t3|byte(r>>12), tx|byte(r>>6)&maskx, tx|byte(r)&maskx)
   399  	case i > rune3Max && i <= MaxRune:
   400  		return append(p, t4|byte(r>>18), tx|byte(r>>12)&maskx, tx|byte(r>>6)&maskx, tx|byte(r)&maskx)
   401  	default:
   402  		return append(p, runeErrorByte0, runeErrorByte1, runeErrorByte2)
   403  	}
   404  }
   405  
   406  // RuneCount returns the number of runes in p. Erroneous and short
   407  // encodings are treated as single runes of width 1 byte.
   408  func RuneCount(p []byte) int {
   409  	np := len(p)
   410  	var n int
   411  	for ; n < np; n++ {
   412  		if c := p[n]; c >= RuneSelf {
   413  			// non-ASCII slow path
   414  			return n + RuneCountInString(string(p[n:]))
   415  		}
   416  	}
   417  	return n
   418  }
   419  
   420  // RuneCountInString is like [RuneCount] but its input is a string.
   421  func RuneCountInString(s string) (n int) {
   422  	for range s {
   423  		n++
   424  	}
   425  	return n
   426  }
   427  
   428  // RuneStart reports whether the byte could be the first byte of an encoded,
   429  // possibly invalid rune. Second and subsequent bytes always have the top two
   430  // bits set to 10.
   431  func RuneStart(b byte) bool { return b&0xC0 != 0x80 }
   432  
   433  const ptrSize = 4 << (^uintptr(0) >> 63)
   434  const hiBits = 0x8080808080808080 >> (64 - 8*ptrSize)
   435  
   436  func word[T string | []byte](s T) uintptr {
   437  	if ptrSize == 4 {
   438  		return uintptr(s[0]) | uintptr(s[1])<<8 | uintptr(s[2])<<16 | uintptr(s[3])<<24
   439  	}
   440  	return uintptr(uint64(s[0]) | uint64(s[1])<<8 | uint64(s[2])<<16 | uint64(s[3])<<24 | uint64(s[4])<<32 | uint64(s[5])<<40 | uint64(s[6])<<48 | uint64(s[7])<<56)
   441  }
   442  
   443  // Valid reports whether p consists entirely of valid UTF-8-encoded runes.
   444  func Valid(p []byte) bool {
   445  	// This optimization avoids the need to recompute the capacity
   446  	// when generating code for slicing p, bringing it to parity with
   447  	// ValidString, which was 20% faster on long ASCII strings.
   448  	p = p[:len(p):len(p)]
   449  
   450  	for len(p) > 0 {
   451  		p0 := p[0]
   452  		if p0 < RuneSelf {
   453  			p = p[1:]
   454  			// If there's one ASCII byte, there are probably more.
   455  			// Advance quickly through ASCII-only data.
   456  			// Note: using > instead of >= here is intentional. That avoids
   457  			// needing pointing-past-the-end fixup on the slice operations.
   458  			if len(p) > ptrSize && word(p)&hiBits == 0 {
   459  				p = p[ptrSize:]
   460  				if len(p) > 2*ptrSize && (word(p)|word(p[ptrSize:]))&hiBits == 0 {
   461  					p = p[2*ptrSize:]
   462  					for len(p) > 4*ptrSize && ((word(p)|word(p[ptrSize:]))|(word(p[2*ptrSize:])|word(p[3*ptrSize:])))&hiBits == 0 {
   463  						p = p[4*ptrSize:]
   464  					}
   465  				}
   466  			}
   467  			continue
   468  		}
   469  		x := first[p0]
   470  		size := int(x & 7)
   471  		accept := acceptRanges[x>>4]
   472  		switch size {
   473  		case 2:
   474  			if len(p) < 2 || p[1] < accept.lo || accept.hi < p[1] {
   475  				return false
   476  			}
   477  			p = p[2:]
   478  		case 3:
   479  			if len(p) < 3 || p[1] < accept.lo || accept.hi < p[1] || p[2] < locb || hicb < p[2] {
   480  				return false
   481  			}
   482  			p = p[3:]
   483  		case 4:
   484  			if len(p) < 4 || p[1] < accept.lo || accept.hi < p[1] || p[2] < locb || hicb < p[2] || p[3] < locb || hicb < p[3] {
   485  				return false
   486  			}
   487  			p = p[4:]
   488  		default:
   489  			return false // illegal starter byte
   490  		}
   491  	}
   492  	return true
   493  }
   494  
   495  // ValidString reports whether s consists entirely of valid UTF-8-encoded runes.
   496  func ValidString(s string) bool {
   497  	for len(s) > 0 {
   498  		s0 := s[0]
   499  		if s0 < RuneSelf {
   500  			s = s[1:]
   501  			// If there's one ASCII byte, there are probably more.
   502  			// Advance quickly through ASCII-only data.
   503  			// Note: using > instead of >= here is intentional. That avoids
   504  			// needing pointing-past-the-end fixup on the slice operations.
   505  			if len(s) > ptrSize && word(s)&hiBits == 0 {
   506  				s = s[ptrSize:]
   507  				if len(s) > 2*ptrSize && (word(s)|word(s[ptrSize:]))&hiBits == 0 {
   508  					s = s[2*ptrSize:]
   509  					for len(s) > 4*ptrSize && ((word(s)|word(s[ptrSize:]))|(word(s[2*ptrSize:])|word(s[3*ptrSize:])))&hiBits == 0 {
   510  						s = s[4*ptrSize:]
   511  					}
   512  				}
   513  			}
   514  			continue
   515  		}
   516  		x := first[s0]
   517  		size := int(x & 7)
   518  		accept := acceptRanges[x>>4]
   519  		switch size {
   520  		case 2:
   521  			if len(s) < 2 || s[1] < accept.lo || accept.hi < s[1] {
   522  				return false
   523  			}
   524  			s = s[2:]
   525  		case 3:
   526  			if len(s) < 3 || s[1] < accept.lo || accept.hi < s[1] || s[2] < locb || hicb < s[2] {
   527  				return false
   528  			}
   529  			s = s[3:]
   530  		case 4:
   531  			if len(s) < 4 || s[1] < accept.lo || accept.hi < s[1] || s[2] < locb || hicb < s[2] || s[3] < locb || hicb < s[3] {
   532  				return false
   533  			}
   534  			s = s[4:]
   535  		default:
   536  			return false // illegal starter byte
   537  		}
   538  	}
   539  	return true
   540  }
   541  
   542  // ValidRune reports whether r can be legally encoded as UTF-8.
   543  // Code points that are out of range or a surrogate half are illegal.
   544  func ValidRune(r rune) bool {
   545  	switch {
   546  	case 0 <= r && r < surrogateMin:
   547  		return true
   548  	case surrogateMax < r && r <= MaxRune:
   549  		return true
   550  	}
   551  	return false
   552  }
   553
View as plain text