1 // Copyright (C) 2016 Lukas Lalinsky
2 // Distributed under the MIT license, see the LICENSE file for details.
3
4 #ifndef CHROMAPRINT_UTILS_H_
5 #define CHROMAPRINT_UTILS_H_
6
7 #if defined(HAVE_CONFIG_H)
8 #include <config.h>
9 #endif
10
11 #include <math.h>
12 #include <stddef.h>
13 #include <stdint.h>
14 #include <limits.h>
15 #include <algorithm>
16 #include <limits>
17 #include <iterator>
18 #include "debug.h"
19
20 #define CHROMAPRINT_DISABLE_COPY(ClassName) \
21 ClassName(const ClassName &); \
22 void operator=(const ClassName &);
23
24 namespace chromaprint {
25
26 #ifndef HAVE_ROUND
round(double x)27 static inline double round(double x)
28 {
29 if (x >= 0.0)
30 return floor(x + 0.5);
31 else
32 return ceil(x - 0.5);
33 }
34 #endif
35
36 template<class RandomAccessIterator>
37 void PrepareHammingWindow(RandomAccessIterator first, RandomAccessIterator last, double scale = 1.0)
38 {
39 int i = 0;
40 const auto size = std::distance(first, last);
41 while (first != last) {
42 *first++ = scale * (0.54 - 0.46 * cos(i++ * 2.0 * M_PI / (size - 1)));
43 }
44 }
45
46 template <typename InputIt, typename WindowIt, typename OutputIt>
ApplyWindow(InputIt first,InputIt last,WindowIt & window,OutputIt & output)47 void ApplyWindow(InputIt first, InputIt last, WindowIt &window, OutputIt &output)
48 {
49 auto input = first;
50 while (input != last) {
51 *output = *input * *window;
52 ++input;
53 ++window;
54 ++output;
55 }
56 }
57
58 template<class Iterator>
Sum(Iterator first,Iterator last)59 typename std::iterator_traits<Iterator>::value_type Sum(Iterator first, Iterator last)
60 {
61 typename std::iterator_traits<Iterator>::value_type sum = 0;
62 while (first != last) {
63 sum += *first;
64 ++first;
65 }
66 return sum;
67 }
68
69 template<class Iterator>
EuclideanNorm(Iterator first,Iterator last)70 typename std::iterator_traits<Iterator>::value_type EuclideanNorm(Iterator first, Iterator last)
71 {
72 typename std::iterator_traits<Iterator>::value_type squares = 0;
73 while (first != last) {
74 squares += *first * *first;
75 ++first;
76 }
77 return (squares > 0) ? sqrt(squares) : 0;
78 }
79
80 template<class Iterator, class Func>
81 void NormalizeVector(Iterator first, Iterator last, Func func, double threshold = 0.01)
82 {
83 double norm = func(first, last);
84 if (norm < threshold) {
85 std::fill(first, last, 0.0);
86 }
87 else {
88 while (first != last) {
89 *first /= norm;
90 ++first;
91 }
92 }
93 }
94
GrayCode(int i)95 inline int GrayCode(int i)
96 {
97 static const unsigned char CODES[] = { 0, 1, 3, 2 };
98 return CODES[i];
99 }
100
IndexToFreq(int i,int frame_size,int sample_rate)101 inline double IndexToFreq(int i, int frame_size, int sample_rate)
102 {
103 return double(i) * sample_rate / frame_size;
104 }
105
FreqToIndex(double freq,int frame_size,int sample_rate)106 inline int FreqToIndex(double freq, int frame_size, int sample_rate)
107 {
108 return (int)round(frame_size * freq / sample_rate);
109 }
110
111 template<class T>
IsNaN(T value)112 inline bool IsNaN(T value)
113 {
114 return value != value;
115 }
116
FreqToBark(double f)117 inline double FreqToBark(double f)
118 {
119 double z = (26.81 * f) / (1960.0 + f) - 0.53;
120
121 if (z < 2.0) {
122 z = z + 0.15 * (2.0 - z);
123 } else if (z > 20.1) {
124 z = z + 0.22 * (z - 20.1);
125 }
126
127 return z;
128 }
129
130 // https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
131 #define CHROMAPRINT_POPCNT_IMPL(T) \
132 v = v - ((v >> 1) & (T)~(T)0/3); \
133 v = (v & (T)~(T)0/15*3) + ((v >> 2) & (T)~(T)0/15*3); \
134 v = (v + (v >> 4)) & (T)~(T)0/255*15; \
135 c = (T)(v * ((T)~(T)0/255)) >> (sizeof(T) - 1) * CHAR_BIT; \
136
137 #ifdef __GNUC__
138 #define CHROMAPRINT_POPCNT_IMPL_32 c = __builtin_popcount(v);
139 #define CHROMAPRINT_POPCNT_IMPL_64 c = __builtin_popcountll(v);
140 #else
141 #define CHROMAPRINT_POPCNT_IMPL_32 CHROMAPRINT_POPCNT_IMPL(uint32_t)
142 #define CHROMAPRINT_POPCNT_IMPL_64 CHROMAPRINT_POPCNT_IMPL(uint64_t)
143 #endif
144
145 template<typename T, int Size, bool IsSigned>
146 struct _CountSetBits_Impl {
Do_CountSetBits_Impl147 static unsigned int Do(T v) {
148 return T::not_implemented;
149 }
150 };
151
152 template<typename T>
CountSetBits(T v)153 inline unsigned int CountSetBits(T v) {
154 return _CountSetBits_Impl<T, sizeof(T), std::numeric_limits<T>::is_signed>::Do(v);
155 }
156
157 template<typename T, int Size>
158 struct _CountSetBits_Impl<T, Size, true> {
159 static unsigned int Do(T v) {
160 return CountSetBits(SignedToUnsigned(v));
161 }
162 };
163
164 template<typename T>
165 struct _CountSetBits_Impl<T, 4, false> {
166 static unsigned int Do(T v) {
167 unsigned int c;
168 CHROMAPRINT_POPCNT_IMPL_32;
169 return c;
170 }
171 };
172
173 template<typename T>
174 struct _CountSetBits_Impl<T, 8, false> {
175 static unsigned int Do(T v) {
176 unsigned int c;
177 CHROMAPRINT_POPCNT_IMPL_64;
178 return c;
179 }
180 };
181
182 #undef CHROMAPRINT_POPCNT_IMPL
183 #undef CHROMAPRINT_POPCNT_IMPL_32
184 #undef CHROMAPRINT_POPCNT_IMPL_64
185
186 template<typename T>
187 inline unsigned int HammingDistance(T a, T b) {
188 return CountSetBits(a ^ b);
189 }
190
191 }; // namespace chromaprint
192
193 #endif
194