intern.go

Documentation: k8s.io/kube-openapi/pkg/internal/third_party/go-json-experiment/json

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