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 := end - UTFMax
   267  	if lim < 0 {
   268  		lim = 0
   269  	}
   270  	for start--; start >= lim; start-- {
   271  		if RuneStart(p[start]) {
   272  			break
   273  		}
   274  	}
   275  	if start < 0 {
   276  		start = 0
   277  	}
   278  	r, size = DecodeRune(p[start:end])
   279  	if start+size != end {
   280  		return RuneError, 1
   281  	}
   282  	return r, size
   283  }
   284  
   285  // DecodeLastRuneInString is like [DecodeLastRune] but its input is a string. If
   286  // s is empty it returns ([RuneError], 0). Otherwise, if the encoding is invalid,
   287  // it returns (RuneError, 1). Both are impossible results for correct,
   288  // non-empty UTF-8.
   289  //
   290  // An encoding is invalid if it is incorrect UTF-8, encodes a rune that is
   291  // out of range, or is not the shortest possible UTF-8 encoding for the
   292  // value. No other validation is performed.
   293  func DecodeLastRuneInString(s string) (r rune, size int) {
   294  	end := len(s)
   295  	if end == 0 {
   296  		return RuneError, 0
   297  	}
   298  	start := end - 1
   299  	r = rune(s[start])
   300  	if r < RuneSelf {
   301  		return r, 1
   302  	}
   303  	// guard against O(n^2) behavior when traversing
   304  	// backwards through strings with long sequences of
   305  	// invalid UTF-8.
   306  	lim := end - UTFMax
   307  	if lim < 0 {
   308  		lim = 0
   309  	}
   310  	for start--; start >= lim; start-- {
   311  		if RuneStart(s[start]) {
   312  			break
   313  		}
   314  	}
   315  	if start < 0 {
   316  		start = 0
   317  	}
   318  	r, size = DecodeRuneInString(s[start:end])
   319  	if start+size != end {
   320  		return RuneError, 1
   321  	}
   322  	return r, size
   323  }
   324  
   325  // RuneLen returns the number of bytes in the UTF-8 encoding of the rune.
   326  // It returns -1 if the rune is not a valid value to encode in UTF-8.
   327  func RuneLen(r rune) int {
   328  	switch {
   329  	case r < 0:
   330  		return -1
   331  	case r <= rune1Max:
   332  		return 1
   333  	case r <= rune2Max:
   334  		return 2
   335  	case surrogateMin <= r && r <= surrogateMax:
   336  		return -1
   337  	case r <= rune3Max:
   338  		return 3
   339  	case r <= MaxRune:
   340  		return 4
   341  	}
   342  	return -1
   343  }
   344  
   345  // EncodeRune writes into p (which must be large enough) the UTF-8 encoding of the rune.
   346  // If the rune is out of range, it writes the encoding of [RuneError].
   347  // It returns the number of bytes written.
   348  func EncodeRune(p []byte, r rune) int {
   349  	// This function is inlineable for fast handling of ASCII.
   350  	if uint32(r) <= rune1Max {
   351  		p[0] = byte(r)
   352  		return 1
   353  	}
   354  	return encodeRuneNonASCII(p, r)
   355  }
   356  
   357  func encodeRuneNonASCII(p []byte, r rune) int {
   358  	// Negative values are erroneous. Making it unsigned addresses the problem.
   359  	switch i := uint32(r); {
   360  	case i <= rune2Max:
   361  		_ = p[1] // eliminate bounds checks
   362  		p[0] = t2 | byte(r>>6)
   363  		p[1] = tx | byte(r)&maskx
   364  		return 2
   365  	case i < surrogateMin, surrogateMax < i && i <= rune3Max:
   366  		_ = p[2] // eliminate bounds checks
   367  		p[0] = t3 | byte(r>>12)
   368  		p[1] = tx | byte(r>>6)&maskx
   369  		p[2] = tx | byte(r)&maskx
   370  		return 3
   371  	case i > rune3Max && i <= MaxRune:
   372  		_ = p[3] // eliminate bounds checks
   373  		p[0] = t4 | byte(r>>18)
   374  		p[1] = tx | byte(r>>12)&maskx
   375  		p[2] = tx | byte(r>>6)&maskx
   376  		p[3] = tx | byte(r)&maskx
   377  		return 4
   378  	default:
   379  		_ = p[2] // eliminate bounds checks
   380  		p[0] = runeErrorByte0
   381  		p[1] = runeErrorByte1
   382  		p[2] = runeErrorByte2
   383  		return 3
   384  	}
   385  }
   386  
   387  // AppendRune appends the UTF-8 encoding of r to the end of p and
   388  // returns the extended buffer. If the rune is out of range,
   389  // it appends the encoding of [RuneError].
   390  func AppendRune(p []byte, r rune) []byte {
   391  	// This function is inlineable for fast handling of ASCII.
   392  	if uint32(r) <= rune1Max {
   393  		return append(p, byte(r))
   394  	}
   395  	return appendRuneNonASCII(p, r)
   396  }
   397  
   398  func appendRuneNonASCII(p []byte, r rune) []byte {
   399  	// Negative values are erroneous. Making it unsigned addresses the problem.
   400  	switch i := uint32(r); {
   401  	case i <= rune2Max:
   402  		return append(p, t2|byte(r>>6), tx|byte(r)&maskx)
   403  	case i < surrogateMin, surrogateMax < i && i <= rune3Max:
   404  		return append(p, t3|byte(r>>12), tx|byte(r>>6)&maskx, tx|byte(r)&maskx)
   405  	case i > rune3Max && i <= MaxRune:
   406  		return append(p, t4|byte(r>>18), tx|byte(r>>12)&maskx, tx|byte(r>>6)&maskx, tx|byte(r)&maskx)
   407  	default:
   408  		return append(p, runeErrorByte0, runeErrorByte1, runeErrorByte2)
   409  	}
   410  }
   411  
   412  // RuneCount returns the number of runes in p. Erroneous and short
   413  // encodings are treated as single runes of width 1 byte.
   414  func RuneCount(p []byte) int {
   415  	np := len(p)
   416  	var n int
   417  	for ; n < np; n++ {
   418  		if c := p[n]; c >= RuneSelf {
   419  			// non-ASCII slow path
   420  			return n + RuneCountInString(string(p[n:]))
   421  		}
   422  	}
   423  	return n
   424  }
   425  
   426  // RuneCountInString is like [RuneCount] but its input is a string.
   427  func RuneCountInString(s string) (n int) {
   428  	for range s {
   429  		n++
   430  	}
   431  	return n
   432  }
   433  
   434  // RuneStart reports whether the byte could be the first byte of an encoded,
   435  // possibly invalid rune. Second and subsequent bytes always have the top two
   436  // bits set to 10.
   437  func RuneStart(b byte) bool { return b&0xC0 != 0x80 }
   438  
   439  // Valid reports whether p consists entirely of valid UTF-8-encoded runes.
   440  func Valid(p []byte) bool {
   441  	// This optimization avoids the need to recompute the capacity
   442  	// when generating code for p[8:], bringing it to parity with
   443  	// ValidString, which was 20% faster on long ASCII strings.
   444  	p = p[:len(p):len(p)]
   445  
   446  	// Fast path. Check for and skip 8 bytes of ASCII characters per iteration.
   447  	for len(p) >= 8 {
   448  		// Combining two 32 bit loads allows the same code to be used
   449  		// for 32 and 64 bit platforms.
   450  		// The compiler can generate a 32bit load for first32 and second32
   451  		// on many platforms. See test/codegen/memcombine.go.
   452  		first32 := uint32(p[0]) | uint32(p[1])<<8 | uint32(p[2])<<16 | uint32(p[3])<<24
   453  		second32 := uint32(p[4]) | uint32(p[5])<<8 | uint32(p[6])<<16 | uint32(p[7])<<24
   454  		if (first32|second32)&0x80808080 != 0 {
   455  			// Found a non ASCII byte (>= RuneSelf).
   456  			break
   457  		}
   458  		p = p[8:]
   459  	}
   460  	n := len(p)
   461  	for i := 0; i < n; {
   462  		pi := p[i]
   463  		if pi < RuneSelf {
   464  			i++
   465  			continue
   466  		}
   467  		x := first[pi]
   468  		if x == xx {
   469  			return false // Illegal starter byte.
   470  		}
   471  		size := int(x & 7)
   472  		if i+size > n {
   473  			return false // Short or invalid.
   474  		}
   475  		accept := acceptRanges[x>>4]
   476  		if c := p[i+1]; c < accept.lo || accept.hi < c {
   477  			return false
   478  		} else if size == 2 {
   479  		} else if c := p[i+2]; c < locb || hicb < c {
   480  			return false
   481  		} else if size == 3 {
   482  		} else if c := p[i+3]; c < locb || hicb < c {
   483  			return false
   484  		}
   485  		i += size
   486  	}
   487  	return true
   488  }
   489  
   490  // ValidString reports whether s consists entirely of valid UTF-8-encoded runes.
   491  func ValidString(s string) bool {
   492  	// Fast path. Check for and skip 8 bytes of ASCII characters per iteration.
   493  	for len(s) >= 8 {
   494  		// Combining two 32 bit loads allows the same code to be used
   495  		// for 32 and 64 bit platforms.
   496  		// The compiler can generate a 32bit load for first32 and second32
   497  		// on many platforms. See test/codegen/memcombine.go.
   498  		first32 := uint32(s[0]) | uint32(s[1])<<8 | uint32(s[2])<<16 | uint32(s[3])<<24
   499  		second32 := uint32(s[4]) | uint32(s[5])<<8 | uint32(s[6])<<16 | uint32(s[7])<<24
   500  		if (first32|second32)&0x80808080 != 0 {
   501  			// Found a non ASCII byte (>= RuneSelf).
   502  			break
   503  		}
   504  		s = s[8:]
   505  	}
   506  	n := len(s)
   507  	for i := 0; i < n; {
   508  		si := s[i]
   509  		if si < RuneSelf {
   510  			i++
   511  			continue
   512  		}
   513  		x := first[si]
   514  		if x == xx {
   515  			return false // Illegal starter byte.
   516  		}
   517  		size := int(x & 7)
   518  		if i+size > n {
   519  			return false // Short or invalid.
   520  		}
   521  		accept := acceptRanges[x>>4]
   522  		if c := s[i+1]; c < accept.lo || accept.hi < c {
   523  			return false
   524  		} else if size == 2 {
   525  		} else if c := s[i+2]; c < locb || hicb < c {
   526  			return false
   527  		} else if size == 3 {
   528  		} else if c := s[i+3]; c < locb || hicb < c {
   529  			return false
   530  		}
   531  		i += size
   532  	}
   533  	return true
   534  }
   535  
   536  // ValidRune reports whether r can be legally encoded as UTF-8.
   537  // Code points that are out of range or a surrogate half are illegal.
   538  func ValidRune(r rune) bool {
   539  	switch {
   540  	case 0 <= r && r < surrogateMin:
   541  		return true
   542  	case surrogateMax < r && r <= MaxRune:
   543  		return true
   544  	}
   545  	return false
   546  }
   547
View as plain text