1 /*
2 Copyright 2014 David Robillard <http://drobilla.net>
3
4 Permission to use, copy, modify, and/or distribute this software for any
5 purpose with or without fee is hereby granted, provided that the above
6 copyright notice and this permission notice appear in all copies.
7
8 THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9 WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10 MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11 ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12 WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13 ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14 OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
15 */
16
17 #ifndef ZIX_TRIE_UTIL_H
18 #define ZIX_TRIE_UTIL_H
19
20 #ifdef __SSE4_2__
21 # include <smmintrin.h>
22 #endif
23
24 #ifdef ZIX_TRIE_LINEAR_SEARCH
25
26 /** Return the index of `k` in `keys`, or `n` if not found. */
27 ZIX_PRIVATE size_t
zix_trie_find_key(const uint8_t * const keys,const size_t n,const uint8_t k)28 zix_trie_find_key(const uint8_t* const keys, const size_t n, const uint8_t k)
29 {
30 for (size_t i = 0; i < n; ++i) {
31 if (keys[i] == k) {
32 assert(keys[i] >= k);
33 return i;
34 }
35 }
36 return n;
37 }
38
39 #else
40
41 /** Return the index of the first element in `keys` >= `k`, or `n`. */
42 ZIX_PRIVATE size_t
zix_trie_find_key(const uint8_t * const keys,const size_t n,const uint8_t k)43 zix_trie_find_key(const uint8_t* const keys, const size_t n, const uint8_t k)
44 {
45 size_t first = 0;
46 size_t len = n;
47 while (len > 0) {
48 const size_t half = len >> 1;
49 const size_t i = first + half;
50 if (keys[i] < k) {
51 const size_t chop = half + 1;
52 first += chop;
53 len -= chop;
54 } else {
55 len = half;
56 }
57 }
58 assert(first == n || keys[first] >= k);
59 return first;
60 }
61
62 #endif
63
64 #if !defined (__SSE4_2__) || !defined(NDEBUG)
65
66 ZIX_PRIVATE size_t
zix_trie_change_index_c(const uint8_t * a,const uint8_t * b,size_t len)67 zix_trie_change_index_c(const uint8_t* a, const uint8_t* b, size_t len)
68 {
69 for (size_t i = 0; i < len; ++i) {
70 if (a[i] != b[i]) {
71 return i;
72 }
73 }
74 return len;
75 }
76
77 #endif
78
79 #ifdef __SSE4_2__
80
81 ZIX_PRIVATE size_t
zix_trie_change_index_sse(const uint8_t * a,const uint8_t * b,const size_t len)82 zix_trie_change_index_sse(const uint8_t* a, const uint8_t* b, const size_t len)
83 {
84 const size_t veclen = len & ~(sizeof(__m128i) - 1);
85 size_t i = 0;
86 for (; i < veclen; i += sizeof(__m128i)) {
87 const __m128i r = _mm_loadu_si128((const __m128i*)(a + i));
88 const __m128i s = _mm_loadu_si128((const __m128i*)(b + i));
89 const int index = _mm_cmpistri(
90 r, s, _SIDD_SBYTE_OPS|_SIDD_CMP_EQUAL_EACH|_SIDD_NEGATIVE_POLARITY);
91
92 if (index != sizeof(__m128i)) {
93 assert(i + index == change_index_c(a, b, len));
94 return i + index;
95 }
96 }
97
98 const __m128i r = _mm_loadu_si128((const __m128i*)(a + i));
99 const __m128i s = _mm_loadu_si128((const __m128i*)(b + i));
100 const size_t l = len - i;
101 const int index = _mm_cmpestri(
102 r, l, s, l,
103 _SIDD_SBYTE_OPS|_SIDD_CMP_EQUAL_EACH|_SIDD_MASKED_NEGATIVE_POLARITY);
104
105 assert(i + index == change_index_c(a, b, len));
106 return i + index;
107 }
108
109 #endif
110
111 ZIX_PRIVATE size_t
zix_trie_change_index(const uint8_t * a,const uint8_t * b,const size_t len)112 zix_trie_change_index(const uint8_t* a, const uint8_t* b, const size_t len)
113 {
114 #ifdef __SSE4_2__
115 return zix_trie_change_index_sse(a, b, len);
116 #else
117 return zix_trie_change_index_c(a, b, len);
118 #endif
119 }
120
121 #endif /* ZIX_TRIE_UTIL_H */
122