1 // SPDX-License-Identifier: BSD-3-Clause
2 //
3 // Copyright(c) 2016 Intel Corporation. All rights reserved.
4 //
5 // Author: Seppo Ingalsuo <seppo.ingalsuo@linux.intel.com>
6 // Liam Girdwood <liam.r.girdwood@linux.intel.com>
7 // Keyon Jie <yang.jie@linux.intel.com>
8
9 /* Binary GCD algorithm
10 * https://en.wikipedia.org/wiki/Binary_GCD_algorithm
11 */
12
13 #include <sof/audio/format.h>
14 #include <sof/math/numbers.h>
15 #include <stdint.h>
16
17 /* This function returns the greatest common divisor of two numbers
18 * If both parameters are 0, gcd(0, 0) returns 0
19 * If first parameters is 0 or second parameter is 0, gcd(0, b) returns b
20 * and gcd(a, 0) returns a, because everything divides 0.
21 */
22
gcd(int a,int b)23 int gcd(int a, int b)
24 {
25 if (a == 0)
26 return b;
27
28 if (b == 0)
29 return a;
30
31 /* If the numbers are negative, convert them to positive numbers
32 * gcd(a, b) = gcd(-a, -b) = gcd(-a, b) = gcd(a, -b)
33 */
34
35 if (a < 0)
36 a = -a;
37
38 if (b < 0)
39 b = -b;
40
41 int aux;
42 int k;
43
44 /* Find the greatest power of 2 that devides both a and b */
45 for (k = 0; ((a | b) & 1) == 0; k++) {
46 a >>= 1;
47 b >>= 1;
48 }
49
50 /* divide by 2 until a becomes odd */
51 while ((a & 1) == 0)
52 a >>= 1;
53
54 do {
55 /*if b is even, remove all factors of 2*/
56 while ((b & 1) == 0)
57 b >>= 1;
58
59 /* both a and b are odd now. Swap so a <= b
60 * then set b = b - a, which is also even
61 */
62 if (a > b) {
63 aux = a;
64 a = b;
65 b = aux;
66 }
67
68 b = b - a;
69
70 } while (b != 0);
71
72 /* restore common factors of 2 */
73 return a << k;
74 }
75
76 /* This function searches from vec[] (of length vec_length) integer values
77 * of n. The indexes to equal values is returned in idx[]. The function
78 * returns the number of found matches. The max_results should be set to
79 * 0 (or negative) or vec_length get all the matches. The max_result can be set
80 * to 1 to receive only the first match in ascending order. It avoids need
81 * for an array for idx.
82 */
find_equal_int16(int16_t idx[],int16_t vec[],int n,int vec_length,int max_results)83 int find_equal_int16(int16_t idx[], int16_t vec[], int n, int vec_length,
84 int max_results)
85 {
86 int nresults = 0;
87 int i;
88
89 for (i = 0; i < vec_length; i++) {
90 if (vec[i] == n) {
91 idx[nresults++] = i;
92 if (nresults == max_results)
93 break;
94 }
95 }
96
97 return nresults;
98 }
99
100 /* Return the smallest value found in the vector */
find_min_int16(int16_t vec[],int vec_length)101 int16_t find_min_int16(int16_t vec[], int vec_length)
102 {
103 int i;
104 int min = vec[0];
105
106 for (i = 1; i < vec_length; i++)
107 min = (vec[i] < min) ? vec[i] : min;
108
109 return min;
110 }
111
112 /* Return the largest absolute value found in the vector. Note that
113 * smallest negative value need to be saturated to preset as int32_t.
114 */
find_max_abs_int32(int32_t vec[],int vec_length)115 int32_t find_max_abs_int32(int32_t vec[], int vec_length)
116 {
117 int i;
118 int64_t amax = (vec[0] > 0) ? vec[0] : -vec[0];
119
120 for (i = 1; i < vec_length; i++) {
121 amax = (vec[i] > amax) ? vec[i] : amax;
122 amax = (-vec[i] > amax) ? -vec[i] : amax;
123 }
124
125 return SATP_INT32(amax); /* Amax is always a positive value */
126 }
127
128 /* Count the left shift amount to normalize a 32 bit signed integer value
129 * without causing overflow. Input value 0 will result to 31.
130 */
norm_int32(int32_t val)131 int norm_int32(int32_t val)
132 {
133 int c = 0;
134
135 /* count number of bits c that val can be right-shifted arithmetically
136 * until there is -1 (if val is negative) or 0 (if val is positive)
137 * norm of val will be 31-c
138 */
139 for (; val != -1 && val != 0; c++)
140 val >>= 1;
141
142 return 31 - c;
143 }
144
145 /**
146 * Basic CRC-32 implementation, based on pseudo-code from
147 * https://en.wikipedia.org/wiki/Cyclic_redundancy_check#CRC-32_algorithm
148 * 0xEDB88320 is the reversed polynomial representation
149 */
crc32(uint32_t base,const void * data,uint32_t bytes)150 uint32_t crc32(uint32_t base, const void *data, uint32_t bytes)
151 {
152 uint32_t crc = ~base;
153 uint32_t cur;
154 int i;
155 int j;
156
157 for (i = 0; i < bytes; ++i) {
158 cur = (crc ^ ((const uint8_t *)data)[i]) & 0xFF;
159
160 for (j = 0; j < 8; ++j)
161 cur = (cur & 1) ? (cur >> 1) ^ 0xEDB88320 : cur >> 1;
162
163 crc = cur ^ (crc >> 8);
164 }
165
166 return ~crc;
167 }
168
