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  // first is information about the first byte in a UTF-8 sequence.
    65  var first = [256]uint8{
    66  	//   1   2   3   4   5   6   7   8   9   A   B   C   D   E   F
    67  	as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, // 0x00-0x0F
    68  	as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, // 0x10-0x1F
    69  	as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, // 0x20-0x2F
    70  	as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, // 0x30-0x3F
    71  	as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, // 0x40-0x4F
    72  	as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, // 0x50-0x5F
    73  	as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, // 0x60-0x6F
    74  	as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, // 0x70-0x7F
    75  	//   1   2   3   4   5   6   7   8   9   A   B   C   D   E   F
    76  	xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, // 0x80-0x8F
    77  	xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, // 0x90-0x9F
    78  	xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, // 0xA0-0xAF
    79  	xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, // 0xB0-0xBF
    80  	xx, xx, s1, s1, s1, s1, s1, s1, s1, s1, s1, s1, s1, s1, s1, s1, // 0xC0-0xCF
    81  	s1, s1, s1, s1, s1, s1, s1, s1, s1, s1, s1, s1, s1, s1, s1, s1, // 0xD0-0xDF
    82  	s2, s3, s3, s3, s3, s3, s3, s3, s3, s3, s3, s3, s3, s4, s3, s3, // 0xE0-0xEF
    83  	s5, s6, s6, s6, s7, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, // 0xF0-0xFF
    84  }
    85  
    86  // acceptRange gives the range of valid values for the second byte in a UTF-8
    87  // sequence.
    88  type acceptRange struct {
    89  	lo uint8 // lowest value for second byte.
    90  	hi uint8 // highest value for second byte.
    91  }
    92  
    93  // acceptRanges has size 16 to avoid bounds checks in the code that uses it.
    94  var acceptRanges = [16]acceptRange{
    95  	0: {locb, hicb},
    96  	1: {0xA0, hicb},
    97  	2: {locb, 0x9F},
    98  	3: {0x90, hicb},
    99  	4: {locb, 0x8F},
   100  }
   101  
   102  // FullRune reports whether the bytes in p begin with a full UTF-8 encoding of a rune.
   103  // An invalid encoding is considered a full Rune since it will convert as a width-1 error rune.
   104  func FullRune(p []byte) bool {
   105  	n := len(p)
   106  	if n == 0 {
   107  		return false
   108  	}
   109  	x := first[p[0]]
   110  	if n >= int(x&7) {
   111  		return true // ASCII, invalid or valid.
   112  	}
   113  	// Must be short or invalid.
   114  	accept := acceptRanges[x>>4]
   115  	if n > 1 && (p[1] < accept.lo || accept.hi < p[1]) {
   116  		return true
   117  	} else if n > 2 && (p[2] < locb || hicb < p[2]) {
   118  		return true
   119  	}
   120  	return false
   121  }
   122  
   123  // FullRuneInString is like FullRune but its input is a string.
   124  func FullRuneInString(s string) bool {
   125  	n := len(s)
   126  	if n == 0 {
   127  		return false
   128  	}
   129  	x := first[s[0]]
   130  	if n >= int(x&7) {
   131  		return true // ASCII, invalid, or valid.
   132  	}
   133  	// Must be short or invalid.
   134  	accept := acceptRanges[x>>4]
   135  	if n > 1 && (s[1] < accept.lo || accept.hi < s[1]) {
   136  		return true
   137  	} else if n > 2 && (s[2] < locb || hicb < s[2]) {
   138  		return true
   139  	}
   140  	return false
   141  }
   142  
   143  // DecodeRune unpacks the first UTF-8 encoding in p and returns the rune and
   144  // its width in bytes. If p is empty it returns ([RuneError], 0). Otherwise, if
   145  // the encoding is invalid, it returns (RuneError, 1). Both are impossible
   146  // results for correct, non-empty UTF-8.
   147  //
   148  // An encoding is invalid if it is incorrect UTF-8, encodes a rune that is
   149  // out of range, or is not the shortest possible UTF-8 encoding for the
   150  // value. No other validation is performed.
   151  func DecodeRune(p []byte) (r rune, size int) {
   152  	n := len(p)
   153  	if n < 1 {
   154  		return RuneError, 0
   155  	}
   156  	p0 := p[0]
   157  	x := first[p0]
   158  	if x >= as {
   159  		// The following code simulates an additional check for x == xx and
   160  		// handling the ASCII and invalid cases accordingly. This mask-and-or
   161  		// approach prevents an additional branch.
   162  		mask := rune(x) << 31 >> 31 // Create 0x0000 or 0xFFFF.
   163  		return rune(p[0])&^mask | RuneError&mask, 1
   164  	}
   165  	sz := int(x & 7)
   166  	accept := acceptRanges[x>>4]
   167  	if n < sz {
   168  		return RuneError, 1
   169  	}
   170  	b1 := p[1]
   171  	if b1 < accept.lo || accept.hi < b1 {
   172  		return RuneError, 1
   173  	}
   174  	if sz <= 2 { // <= instead of == to help the compiler eliminate some bounds checks
   175  		return rune(p0&mask2)<<6 | rune(b1&maskx), 2
   176  	}
   177  	b2 := p[2]
   178  	if b2 < locb || hicb < b2 {
   179  		return RuneError, 1
   180  	}
   181  	if sz <= 3 {
   182  		return rune(p0&mask3)<<12 | rune(b1&maskx)<<6 | rune(b2&maskx), 3
   183  	}
   184  	b3 := p[3]
   185  	if b3 < locb || hicb < b3 {
   186  		return RuneError, 1
   187  	}
   188  	return rune(p0&mask4)<<18 | rune(b1&maskx)<<12 | rune(b2&maskx)<<6 | rune(b3&maskx), 4
   189  }
   190  
   191  // DecodeRuneInString is like [DecodeRune] but its input is a string. If s is
   192  // empty it returns ([RuneError], 0). Otherwise, if the encoding is invalid, it
   193  // returns (RuneError, 1). Both are impossible results for correct, non-empty
   194  // UTF-8.
   195  //
   196  // An encoding is invalid if it is incorrect UTF-8, encodes a rune that is
   197  // out of range, or is not the shortest possible UTF-8 encoding for the
   198  // value. No other validation is performed.
   199  func DecodeRuneInString(s string) (r rune, size int) {
   200  	n := len(s)
   201  	if n < 1 {
   202  		return RuneError, 0
   203  	}
   204  	s0 := s[0]
   205  	x := first[s0]
   206  	if x >= as {
   207  		// The following code simulates an additional check for x == xx and
   208  		// handling the ASCII and invalid cases accordingly. This mask-and-or
   209  		// approach prevents an additional branch.
   210  		mask := rune(x) << 31 >> 31 // Create 0x0000 or 0xFFFF.
   211  		return rune(s[0])&^mask | RuneError&mask, 1
   212  	}
   213  	sz := int(x & 7)
   214  	accept := acceptRanges[x>>4]
   215  	if n < sz {
   216  		return RuneError, 1
   217  	}
   218  	s1 := s[1]
   219  	if s1 < accept.lo || accept.hi < s1 {
   220  		return RuneError, 1
   221  	}
   222  	if sz <= 2 { // <= instead of == to help the compiler eliminate some bounds checks
   223  		return rune(s0&mask2)<<6 | rune(s1&maskx), 2
   224  	}
   225  	s2 := s[2]
   226  	if s2 < locb || hicb < s2 {
   227  		return RuneError, 1
   228  	}
   229  	if sz <= 3 {
   230  		return rune(s0&mask3)<<12 | rune(s1&maskx)<<6 | rune(s2&maskx), 3
   231  	}
   232  	s3 := s[3]
   233  	if s3 < locb || hicb < s3 {
   234  		return RuneError, 1
   235  	}
   236  	return rune(s0&mask4)<<18 | rune(s1&maskx)<<12 | rune(s2&maskx)<<6 | rune(s3&maskx), 4
   237  }
   238  
   239  // DecodeLastRune unpacks the last UTF-8 encoding in p and returns the rune and
   240  // its width in bytes. If p is empty it returns ([RuneError], 0). Otherwise, if
   241  // the encoding is invalid, it returns (RuneError, 1). Both are impossible
   242  // results for correct, non-empty UTF-8.
   243  //
   244  // An encoding is invalid if it is incorrect UTF-8, encodes a rune that is
   245  // out of range, or is not the shortest possible UTF-8 encoding for the
   246  // value. No other validation is performed.
   247  func DecodeLastRune(p []byte) (r rune, size int) {
   248  	end := len(p)
   249  	if end == 0 {
   250  		return RuneError, 0
   251  	}
   252  	start := end - 1
   253  	r = rune(p[start])
   254  	if r < RuneSelf {
   255  		return r, 1
   256  	}
   257  	// guard against O(n^2) behavior when traversing
   258  	// backwards through strings with long sequences of
   259  	// invalid UTF-8.
   260  	lim := end - UTFMax
   261  	if lim < 0 {
   262  		lim = 0
   263  	}
   264  	for start--; start >= lim; start-- {
   265  		if RuneStart(p[start]) {
   266  			break
   267  		}
   268  	}
   269  	if start < 0 {
   270  		start = 0
   271  	}
   272  	r, size = DecodeRune(p[start:end])
   273  	if start+size != end {
   274  		return RuneError, 1
   275  	}
   276  	return r, size
   277  }
   278  
   279  // DecodeLastRuneInString is like [DecodeLastRune] but its input is a string. If
   280  // s is empty it returns ([RuneError], 0). Otherwise, if the encoding is invalid,
   281  // it returns (RuneError, 1). Both are impossible results for correct,
   282  // non-empty UTF-8.
   283  //
   284  // An encoding is invalid if it is incorrect UTF-8, encodes a rune that is
   285  // out of range, or is not the shortest possible UTF-8 encoding for the
   286  // value. No other validation is performed.
   287  func DecodeLastRuneInString(s string) (r rune, size int) {
   288  	end := len(s)
   289  	if end == 0 {
   290  		return RuneError, 0
   291  	}
   292  	start := end - 1
   293  	r = rune(s[start])
   294  	if r < RuneSelf {
   295  		return r, 1
   296  	}
   297  	// guard against O(n^2) behavior when traversing
   298  	// backwards through strings with long sequences of
   299  	// invalid UTF-8.
   300  	lim := end - UTFMax
   301  	if lim < 0 {
   302  		lim = 0
   303  	}
   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  	// Negative values are erroneous. Making it unsigned addresses the problem.
   344  	switch i := uint32(r); {
   345  	case i <= rune1Max:
   346  		p[0] = byte(r)
   347  		return 1
   348  	case i <= rune2Max:
   349  		_ = p[1] // eliminate bounds checks
   350  		p[0] = t2 | byte(r>>6)
   351  		p[1] = tx | byte(r)&maskx
   352  		return 2
   353  	case i > MaxRune, surrogateMin <= i && i <= surrogateMax:
   354  		r = RuneError
   355  		fallthrough
   356  	case i <= rune3Max:
   357  		_ = p[2] // eliminate bounds checks
   358  		p[0] = t3 | byte(r>>12)
   359  		p[1] = tx | byte(r>>6)&maskx
   360  		p[2] = tx | byte(r)&maskx
   361  		return 3
   362  	default:
   363  		_ = p[3] // eliminate bounds checks
   364  		p[0] = t4 | byte(r>>18)
   365  		p[1] = tx | byte(r>>12)&maskx
   366  		p[2] = tx | byte(r>>6)&maskx
   367  		p[3] = tx | byte(r)&maskx
   368  		return 4
   369  	}
   370  }
   371  
   372  // AppendRune appends the UTF-8 encoding of r to the end of p and
   373  // returns the extended buffer. If the rune is out of range,
   374  // it appends the encoding of [RuneError].
   375  func AppendRune(p []byte, r rune) []byte {
   376  	// This function is inlineable for fast handling of ASCII.
   377  	if uint32(r) <= rune1Max {
   378  		return append(p, byte(r))
   379  	}
   380  	return appendRuneNonASCII(p, r)
   381  }
   382  
   383  func appendRuneNonASCII(p []byte, r rune) []byte {
   384  	// Negative values are erroneous. Making it unsigned addresses the problem.
   385  	switch i := uint32(r); {
   386  	case i <= rune2Max:
   387  		return append(p, t2|byte(r>>6), tx|byte(r)&maskx)
   388  	case i > MaxRune, surrogateMin <= i && i <= surrogateMax:
   389  		r = RuneError
   390  		fallthrough
   391  	case i <= rune3Max:
   392  		return append(p, t3|byte(r>>12), tx|byte(r>>6)&maskx, tx|byte(r)&maskx)
   393  	default:
   394  		return append(p, t4|byte(r>>18), tx|byte(r>>12)&maskx, tx|byte(r>>6)&maskx, tx|byte(r)&maskx)
   395  	}
   396  }
   397  
   398  // RuneCount returns the number of runes in p. Erroneous and short
   399  // encodings are treated as single runes of width 1 byte.
   400  func RuneCount(p []byte) int {
   401  	np := len(p)
   402  	var n int
   403  	for i := 0; i < np; {
   404  		n++
   405  		c := p[i]
   406  		if c < RuneSelf {
   407  			// ASCII fast path
   408  			i++
   409  			continue
   410  		}
   411  		x := first[c]
   412  		if x == xx {
   413  			i++ // invalid.
   414  			continue
   415  		}
   416  		size := int(x & 7)
   417  		if i+size > np {
   418  			i++ // Short or invalid.
   419  			continue
   420  		}
   421  		accept := acceptRanges[x>>4]
   422  		if c := p[i+1]; c < accept.lo || accept.hi < c {
   423  			size = 1
   424  		} else if size == 2 {
   425  		} else if c := p[i+2]; c < locb || hicb < c {
   426  			size = 1
   427  		} else if size == 3 {
   428  		} else if c := p[i+3]; c < locb || hicb < c {
   429  			size = 1
   430  		}
   431  		i += size
   432  	}
   433  	return n
   434  }
   435  
   436  // RuneCountInString is like [RuneCount] but its input is a string.
   437  func RuneCountInString(s string) (n int) {
   438  	ns := len(s)
   439  	for i := 0; i < ns; n++ {
   440  		c := s[i]
   441  		if c < RuneSelf {
   442  			// ASCII fast path
   443  			i++
   444  			continue
   445  		}
   446  		x := first[c]
   447  		if x == xx {
   448  			i++ // invalid.
   449  			continue
   450  		}
   451  		size := int(x & 7)
   452  		if i+size > ns {
   453  			i++ // Short or invalid.
   454  			continue
   455  		}
   456  		accept := acceptRanges[x>>4]
   457  		if c := s[i+1]; c < accept.lo || accept.hi < c {
   458  			size = 1
   459  		} else if size == 2 {
   460  		} else if c := s[i+2]; c < locb || hicb < c {
   461  			size = 1
   462  		} else if size == 3 {
   463  		} else if c := s[i+3]; c < locb || hicb < c {
   464  			size = 1
   465  		}
   466  		i += size
   467  	}
   468  	return n
   469  }
   470  
   471  // RuneStart reports whether the byte could be the first byte of an encoded,
   472  // possibly invalid rune. Second and subsequent bytes always have the top two
   473  // bits set to 10.
   474  func RuneStart(b byte) bool { return b&0xC0 != 0x80 }
   475  
   476  // Valid reports whether p consists entirely of valid UTF-8-encoded runes.
   477  func Valid(p []byte) bool {
   478  	// This optimization avoids the need to recompute the capacity
   479  	// when generating code for p[8:], bringing it to parity with
   480  	// ValidString, which was 20% faster on long ASCII strings.
   481  	p = p[:len(p):len(p)]
   482  
   483  	// Fast path. Check for and skip 8 bytes of ASCII characters per iteration.
   484  	for len(p) >= 8 {
   485  		// Combining two 32 bit loads allows the same code to be used
   486  		// for 32 and 64 bit platforms.
   487  		// The compiler can generate a 32bit load for first32 and second32
   488  		// on many platforms. See test/codegen/memcombine.go.
   489  		first32 := uint32(p[0]) | uint32(p[1])<<8 | uint32(p[2])<<16 | uint32(p[3])<<24
   490  		second32 := uint32(p[4]) | uint32(p[5])<<8 | uint32(p[6])<<16 | uint32(p[7])<<24
   491  		if (first32|second32)&0x80808080 != 0 {
   492  			// Found a non ASCII byte (>= RuneSelf).
   493  			break
   494  		}
   495  		p = p[8:]
   496  	}
   497  	n := len(p)
   498  	for i := 0; i < n; {
   499  		pi := p[i]
   500  		if pi < RuneSelf {
   501  			i++
   502  			continue
   503  		}
   504  		x := first[pi]
   505  		if x == xx {
   506  			return false // Illegal starter byte.
   507  		}
   508  		size := int(x & 7)
   509  		if i+size > n {
   510  			return false // Short or invalid.
   511  		}
   512  		accept := acceptRanges[x>>4]
   513  		if c := p[i+1]; c < accept.lo || accept.hi < c {
   514  			return false
   515  		} else if size == 2 {
   516  		} else if c := p[i+2]; c < locb || hicb < c {
   517  			return false
   518  		} else if size == 3 {
   519  		} else if c := p[i+3]; c < locb || hicb < c {
   520  			return false
   521  		}
   522  		i += size
   523  	}
   524  	return true
   525  }
   526  
   527  // ValidString reports whether s consists entirely of valid UTF-8-encoded runes.
   528  func ValidString(s string) bool {
   529  	// Fast path. Check for and skip 8 bytes of ASCII characters per iteration.
   530  	for len(s) >= 8 {
   531  		// Combining two 32 bit loads allows the same code to be used
   532  		// for 32 and 64 bit platforms.
   533  		// The compiler can generate a 32bit load for first32 and second32
   534  		// on many platforms. See test/codegen/memcombine.go.
   535  		first32 := uint32(s[0]) | uint32(s[1])<<8 | uint32(s[2])<<16 | uint32(s[3])<<24
   536  		second32 := uint32(s[4]) | uint32(s[5])<<8 | uint32(s[6])<<16 | uint32(s[7])<<24
   537  		if (first32|second32)&0x80808080 != 0 {
   538  			// Found a non ASCII byte (>= RuneSelf).
   539  			break
   540  		}
   541  		s = s[8:]
   542  	}
   543  	n := len(s)
   544  	for i := 0; i < n; {
   545  		si := s[i]
   546  		if si < RuneSelf {
   547  			i++
   548  			continue
   549  		}
   550  		x := first[si]
   551  		if x == xx {
   552  			return false // Illegal starter byte.
   553  		}
   554  		size := int(x & 7)
   555  		if i+size > n {
   556  			return false // Short or invalid.
   557  		}
   558  		accept := acceptRanges[x>>4]
   559  		if c := s[i+1]; c < accept.lo || accept.hi < c {
   560  			return false
   561  		} else if size == 2 {
   562  		} else if c := s[i+2]; c < locb || hicb < c {
   563  			return false
   564  		} else if size == 3 {
   565  		} else if c := s[i+3]; c < locb || hicb < c {
   566  			return false
   567  		}
   568  		i += size
   569  	}
   570  	return true
   571  }
   572  
   573  // ValidRune reports whether r can be legally encoded as UTF-8.
   574  // Code points that are out of range or a surrogate half are illegal.
   575  func ValidRune(r rune) bool {
   576  	switch {
   577  	case 0 <= r && r < surrogateMin:
   578  		return true
   579  	case surrogateMax < r && r <= MaxRune:
   580  		return true
   581  	}
   582  	return false
   583  }
   584
View as plain text