intern.go 2.5 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586
  1. // Copyright 2022 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. package json
  5. import (
  6. "encoding/binary"
  7. "math/bits"
  8. )
  9. // stringCache is a cache for strings converted from a []byte.
  10. type stringCache = [256]string // 256*unsafe.Sizeof(string("")) => 4KiB
  11. // makeString returns the string form of b.
  12. // It returns a pre-allocated string from c if present, otherwise
  13. // it allocates a new string, inserts it into the cache, and returns it.
  14. func makeString(c *stringCache, b []byte) string {
  15. const (
  16. minCachedLen = 2 // single byte strings are already interned by the runtime
  17. maxCachedLen = 256 // large enough for UUIDs, IPv6 addresses, SHA-256 checksums, etc.
  18. )
  19. if c == nil || len(b) < minCachedLen || len(b) > maxCachedLen {
  20. return string(b)
  21. }
  22. // Compute a hash from the fixed-width prefix and suffix of the string.
  23. // This ensures hashing a string is a constant time operation.
  24. var h uint32
  25. switch {
  26. case len(b) >= 8:
  27. lo := binary.LittleEndian.Uint64(b[:8])
  28. hi := binary.LittleEndian.Uint64(b[len(b)-8:])
  29. h = hash64(uint32(lo), uint32(lo>>32)) ^ hash64(uint32(hi), uint32(hi>>32))
  30. case len(b) >= 4:
  31. lo := binary.LittleEndian.Uint32(b[:4])
  32. hi := binary.LittleEndian.Uint32(b[len(b)-4:])
  33. h = hash64(lo, hi)
  34. case len(b) >= 2:
  35. lo := binary.LittleEndian.Uint16(b[:2])
  36. hi := binary.LittleEndian.Uint16(b[len(b)-2:])
  37. h = hash64(uint32(lo), uint32(hi))
  38. }
  39. // Check the cache for the string.
  40. i := h % uint32(len(*c))
  41. if s := (*c)[i]; s == string(b) {
  42. return s
  43. }
  44. s := string(b)
  45. (*c)[i] = s
  46. return s
  47. }
  48. // hash64 returns the hash of two uint32s as a single uint32.
  49. func hash64(lo, hi uint32) uint32 {
  50. // If avalanche=true, this is identical to XXH32 hash on a 8B string:
  51. // var b [8]byte
  52. // binary.LittleEndian.PutUint32(b[:4], lo)
  53. // binary.LittleEndian.PutUint32(b[4:], hi)
  54. // return xxhash.Sum32(b[:])
  55. const (
  56. prime1 = 0x9e3779b1
  57. prime2 = 0x85ebca77
  58. prime3 = 0xc2b2ae3d
  59. prime4 = 0x27d4eb2f
  60. prime5 = 0x165667b1
  61. )
  62. h := prime5 + uint32(8)
  63. h += lo * prime3
  64. h = bits.RotateLeft32(h, 17) * prime4
  65. h += hi * prime3
  66. h = bits.RotateLeft32(h, 17) * prime4
  67. // Skip final mix (avalanche) step of XXH32 for performance reasons.
  68. // Empirical testing shows that the improvements in unbiased distribution
  69. // does not outweigh the extra cost in computational complexity.
  70. const avalanche = false
  71. if avalanche {
  72. h ^= h >> 15
  73. h *= prime2
  74. h ^= h >> 13
  75. h *= prime3
  76. h ^= h >> 16
  77. }
  78. return h
  79. }