trie.go 1.7 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071
  1. // Copied from the golang.org/x/text repo; DO NOT EDIT
  2. // Copyright 2016 The Go Authors. All rights reserved.
  3. // Use of this source code is governed by a BSD-style
  4. // license that can be found in the LICENSE file.
  5. package idna
  6. // appendMapping appends the mapping for the respective rune. isMapped must be
  7. // true. A mapping is a categorization of a rune as defined in UTS #46.
  8. func (c info) appendMapping(b []byte, s string) []byte {
  9. index := int(c >> indexShift)
  10. if c&xorBit == 0 {
  11. s := mappings[index:]
  12. return append(b, s[1:s[0]+1]...)
  13. }
  14. b = append(b, s...)
  15. if c&inlineXOR == inlineXOR {
  16. // TODO: support and handle two-byte inline masks
  17. b[len(b)-1] ^= byte(index)
  18. } else {
  19. for p := len(b) - int(xorData[index]); p < len(b); p++ {
  20. index++
  21. b[p] ^= xorData[index]
  22. }
  23. }
  24. return b
  25. }
  26. // Sparse block handling code.
  27. type valueRange struct {
  28. value uint16 // header: value:stride
  29. lo, hi byte // header: lo:n
  30. }
  31. type sparseBlocks struct {
  32. values []valueRange
  33. offset []uint16
  34. }
  35. var idnaSparse = sparseBlocks{
  36. values: idnaSparseValues[:],
  37. offset: idnaSparseOffset[:],
  38. }
  39. var trie = newIdnaTrie(0)
  40. // lookup determines the type of block n and looks up the value for b.
  41. // For n < t.cutoff, the block is a simple lookup table. Otherwise, the block
  42. // is a list of ranges with an accompanying value. Given a matching range r,
  43. // the value for b is by r.value + (b - r.lo) * stride.
  44. func (t *sparseBlocks) lookup(n uint32, b byte) uint16 {
  45. offset := t.offset[n]
  46. header := t.values[offset]
  47. lo := offset + 1
  48. hi := lo + uint16(header.lo)
  49. for lo < hi {
  50. m := lo + (hi-lo)/2
  51. r := t.values[m]
  52. if r.lo <= b && b <= r.hi {
  53. return r.value + uint16(b-r.lo)*header.value
  54. }
  55. if b < r.lo {
  56. hi = m
  57. } else {
  58. lo = m + 1
  59. }
  60. }
  61. return 0
  62. }