1 /*
2 * Interval functions
3 * Copyright (c) 2000 by Abramo Bagnara <abramo@alsa-project.org>
4 *
5 *
6 * This library is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU Lesser General Public License as
8 * published by the Free Software Foundation; either version 2.1 of
9 * the License, or (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU Lesser General Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this library; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
19 *
20 */
21
22 #define SND_INTERVAL_C
23 #define SND_INTERVAL_INLINE
24
25 #include <sys/types.h>
26 #include <limits.h>
27 #include "pcm_local.h"
28
div64_32(uint64_t * n,uint32_t d,uint32_t * rem)29 static inline void div64_32(uint64_t *n, uint32_t d, uint32_t *rem)
30 {
31 *rem = *n % d;
32 *n /= d;
33 }
34
div32(unsigned int a,unsigned int b,unsigned int * r)35 static inline unsigned int div32(unsigned int a, unsigned int b,
36 unsigned int *r)
37 {
38 if (b == 0) {
39 *r = 0;
40 return UINT_MAX;
41 }
42 *r = a % b;
43 return a / b;
44 }
45
div_down(unsigned int a,unsigned int b)46 static inline unsigned int div_down(unsigned int a, unsigned int b)
47 {
48 if (b == 0)
49 return UINT_MAX;
50 return a / b;
51 }
52
div_up(unsigned int a,unsigned int b)53 static inline unsigned int div_up(unsigned int a, unsigned int b)
54 {
55 unsigned int r;
56 unsigned int q;
57 if (b == 0)
58 return UINT_MAX;
59 q = div32(a, b, &r);
60 if (r)
61 ++q;
62 return q;
63 }
64
mul(unsigned int a,unsigned int b)65 static inline unsigned int mul(unsigned int a, unsigned int b)
66 {
67 if (a == 0)
68 return 0;
69 if (div_down(UINT_MAX, a) < b)
70 return UINT_MAX;
71 return a * b;
72 }
73
add(unsigned int a,unsigned int b)74 static inline unsigned int add(unsigned int a, unsigned int b)
75 {
76 if (a >= UINT_MAX - b)
77 return UINT_MAX;
78 return a + b;
79 }
80
sub(unsigned int a,unsigned int b)81 static inline unsigned int sub(unsigned int a, unsigned int b)
82 {
83 if (a > b)
84 return a - b;
85 return 0;
86 }
87
muldiv32(unsigned int a,unsigned int b,unsigned int c,unsigned int * r)88 static inline unsigned int muldiv32(unsigned int a, unsigned int b,
89 unsigned int c, unsigned int *r)
90 {
91 uint64_t n = (uint64_t) a * b;
92 if (c == 0) {
93 assert(n > 0);
94 *r = 0;
95 return UINT_MAX;
96 }
97 div64_32(&n, c, r);
98 if (n >= UINT_MAX) {
99 *r = 0;
100 return UINT_MAX;
101 }
102 return n;
103 }
104
snd_interval_refine_min(snd_interval_t * i,unsigned int min,int openmin)105 int snd_interval_refine_min(snd_interval_t *i, unsigned int min, int openmin)
106 {
107 int changed = 0;
108 if (snd_interval_empty(i))
109 return -ENOENT;
110 if (i->min < min) {
111 i->min = min;
112 i->openmin = openmin;
113 changed = 1;
114 } else if (i->min == min && !i->openmin && openmin) {
115 i->openmin = 1;
116 changed = 1;
117 }
118 if (i->integer) {
119 if (i->openmin) {
120 i->min++;
121 i->openmin = 0;
122 }
123 }
124 if (snd_interval_checkempty(i)) {
125 snd_interval_none(i);
126 return -EINVAL;
127 }
128 return changed;
129 }
130
snd_interval_refine_max(snd_interval_t * i,unsigned int max,int openmax)131 int snd_interval_refine_max(snd_interval_t *i, unsigned int max, int openmax)
132 {
133 int changed = 0;
134 if (snd_interval_empty(i))
135 return -ENOENT;
136 if (i->max > max) {
137 i->max = max;
138 i->openmax = openmax;
139 changed = 1;
140 } else if (i->max == max && !i->openmax && openmax) {
141 i->openmax = 1;
142 changed = 1;
143 }
144 if (i->integer) {
145 if (i->openmax) {
146 i->max--;
147 i->openmax = 0;
148 }
149 }
150 if (snd_interval_checkempty(i)) {
151 snd_interval_none(i);
152 return -EINVAL;
153 }
154 return changed;
155 }
156
157 /* r <- v */
snd_interval_refine(snd_interval_t * i,const snd_interval_t * v)158 int snd_interval_refine(snd_interval_t *i, const snd_interval_t *v)
159 {
160 int changed = 0;
161 if (snd_interval_empty(i))
162 return -ENOENT;
163 if (i->min < v->min) {
164 i->min = v->min;
165 i->openmin = v->openmin;
166 changed = 1;
167 } else if (i->min == v->min && !i->openmin && v->openmin) {
168 i->openmin = 1;
169 changed = 1;
170 }
171 if (i->max > v->max) {
172 i->max = v->max;
173 i->openmax = v->openmax;
174 changed = 1;
175 } else if (i->max == v->max && !i->openmax && v->openmax) {
176 i->openmax = 1;
177 changed = 1;
178 }
179 if (!i->integer && v->integer) {
180 i->integer = 1;
181 changed = 1;
182 }
183 if (i->integer) {
184 if (i->openmin) {
185 i->min++;
186 i->openmin = 0;
187 }
188 if (i->openmax) {
189 i->max--;
190 i->openmax = 0;
191 }
192 } else if (!i->openmin && !i->openmax && i->min == i->max)
193 i->integer = 1;
194 if (snd_interval_checkempty(i)) {
195 snd_interval_none(i);
196 return -EINVAL;
197 }
198 return changed;
199 }
200
snd_interval_refine_first(snd_interval_t * i)201 int snd_interval_refine_first(snd_interval_t *i)
202 {
203 const unsigned int last_max = i->max;
204
205 if (snd_interval_empty(i))
206 return -ENOENT;
207 if (snd_interval_single(i))
208 return 0;
209 i->max = i->min;
210 if (i->openmin)
211 i->max++;
212 /* only exclude max value if also excluded before refine */
213 i->openmax = (i->openmax && i->max >= last_max);
214 return 1;
215 }
216
snd_interval_refine_last(snd_interval_t * i)217 int snd_interval_refine_last(snd_interval_t *i)
218 {
219 const unsigned int last_min = i->min;
220
221 if (snd_interval_empty(i))
222 return -ENOENT;
223 if (snd_interval_single(i))
224 return 0;
225 i->min = i->max;
226 if (i->openmax)
227 i->min--;
228 /* only exclude min value if also excluded before refine */
229 i->openmin = (i->openmin && i->min <= last_min);
230 return 1;
231 }
232
snd_interval_refine_set(snd_interval_t * i,unsigned int val)233 int snd_interval_refine_set(snd_interval_t *i, unsigned int val)
234 {
235 snd_interval_t t;
236 t.empty = 0;
237 t.min = t.max = val;
238 t.openmin = t.openmax = 0;
239 t.integer = 1;
240 return snd_interval_refine(i, &t);
241 }
242
snd_interval_add(const snd_interval_t * a,const snd_interval_t * b,snd_interval_t * c)243 void snd_interval_add(const snd_interval_t *a, const snd_interval_t *b, snd_interval_t *c)
244 {
245 if (a->empty || b->empty) {
246 snd_interval_none(c);
247 return;
248 }
249 c->empty = 0;
250 c->min = add(a->min, b->min);
251 c->openmin = (a->openmin || b->openmin);
252 c->max = add(a->max, b->max);
253 c->openmax = (a->openmax || b->openmax);
254 c->integer = (a->integer && b->integer);
255 }
256
snd_interval_sub(const snd_interval_t * a,const snd_interval_t * b,snd_interval_t * c)257 void snd_interval_sub(const snd_interval_t *a, const snd_interval_t *b, snd_interval_t *c)
258 {
259 if (a->empty || b->empty) {
260 snd_interval_none(c);
261 return;
262 }
263 c->empty = 0;
264 c->min = sub(a->min, b->max);
265 c->openmin = (a->openmin || b->openmax);
266 c->max = add(a->max, b->min);
267 c->openmax = (a->openmax || b->openmin);
268 c->integer = (a->integer && b->integer);
269 }
270
snd_interval_mul(const snd_interval_t * a,const snd_interval_t * b,snd_interval_t * c)271 void snd_interval_mul(const snd_interval_t *a, const snd_interval_t *b, snd_interval_t *c)
272 {
273 if (a->empty || b->empty) {
274 snd_interval_none(c);
275 return;
276 }
277 c->empty = 0;
278 c->min = mul(a->min, b->min);
279 c->openmin = (a->openmin || b->openmin);
280 c->max = mul(a->max, b->max);
281 c->openmax = (a->openmax || b->openmax);
282 c->integer = (a->integer && b->integer);
283 }
284
snd_interval_div(const snd_interval_t * a,const snd_interval_t * b,snd_interval_t * c)285 void snd_interval_div(const snd_interval_t *a, const snd_interval_t *b, snd_interval_t *c)
286 {
287 unsigned int r;
288 if (a->empty || b->empty) {
289 snd_interval_none(c);
290 return;
291 }
292 c->empty = 0;
293 c->min = div32(a->min, b->max, &r);
294 c->openmin = (r || a->openmin || b->openmax);
295 if (b->min > 0) {
296 c->max = div32(a->max, b->min, &r);
297 if (r) {
298 c->max++;
299 c->openmax = 1;
300 } else
301 c->openmax = (a->openmax || b->openmin);
302 } else {
303 c->max = UINT_MAX;
304 c->openmax = 0;
305 }
306 c->integer = 0;
307 }
308
309 /* a * b / c */
snd_interval_muldiv(const snd_interval_t * a,const snd_interval_t * b,const snd_interval_t * c,snd_interval_t * d)310 void snd_interval_muldiv(const snd_interval_t *a, const snd_interval_t *b,
311 const snd_interval_t *c, snd_interval_t *d)
312 {
313 unsigned int r;
314 if (a->empty || b->empty || c->empty) {
315 snd_interval_none(d);
316 return;
317 }
318 d->empty = 0;
319 d->min = muldiv32(a->min, b->min, c->max, &r);
320 d->openmin = (r || a->openmin || b->openmin || c->openmax);
321 d->max = muldiv32(a->max, b->max, c->min, &r);
322 if (r) {
323 d->max++;
324 d->openmax = 1;
325 } else
326 d->openmax = (a->openmax || b->openmax || c->openmin);
327 d->integer = 0;
328 }
329
330 /* a * b / k */
snd_interval_muldivk(const snd_interval_t * a,const snd_interval_t * b,unsigned int k,snd_interval_t * c)331 void snd_interval_muldivk(const snd_interval_t *a, const snd_interval_t *b,
332 unsigned int k, snd_interval_t *c)
333 {
334 unsigned int r;
335 if (a->empty || b->empty) {
336 snd_interval_none(c);
337 return;
338 }
339 c->empty = 0;
340 c->min = muldiv32(a->min, b->min, k, &r);
341 c->openmin = (r || a->openmin || b->openmin);
342 c->max = muldiv32(a->max, b->max, k, &r);
343 if (r) {
344 c->max++;
345 c->openmax = 1;
346 } else
347 c->openmax = (a->openmax || b->openmax);
348 c->integer = 0;
349 }
350
351 /* a * k / b */
snd_interval_mulkdiv(const snd_interval_t * a,unsigned int k,const snd_interval_t * b,snd_interval_t * c)352 void snd_interval_mulkdiv(const snd_interval_t *a, unsigned int k,
353 const snd_interval_t *b, snd_interval_t *c)
354 {
355 unsigned int r;
356 if (a->empty || b->empty) {
357 snd_interval_none(c);
358 return;
359 }
360 c->empty = 0;
361 c->min = muldiv32(a->min, k, b->max, &r);
362 c->openmin = (r || a->openmin || b->openmax);
363 if (b->min > 0) {
364 c->max = muldiv32(a->max, k, b->min, &r);
365 if (r) {
366 c->max++;
367 c->openmax = 1;
368 } else
369 c->openmax = (a->openmax || b->openmin);
370 } else {
371 c->max = UINT_MAX;
372 c->openmax = 0;
373 }
374 c->integer = 0;
375 }
376
snd_interval_print(const snd_interval_t * i,snd_output_t * out)377 void snd_interval_print(const snd_interval_t *i, snd_output_t *out)
378 {
379 if (snd_interval_empty(i))
380 snd_output_printf(out, "NONE");
381 else if (i->min == 0 && i->openmin == 0 &&
382 i->max == UINT_MAX && i->openmax == 0)
383 snd_output_printf(out, "ALL");
384 else if (snd_interval_single(i) && i->integer)
385 snd_output_printf(out, "%u", snd_interval_value(i));
386 else
387 snd_output_printf(out, "%c%u %u%c",
388 i->openmin ? '(' : '[',
389 i->min, i->max,
390 i->openmax ? ')' : ']');
391 }
392
393 #if 0
394 static void boundary_abs(int a, int adir, int *b, int *bdir)
395 {
396 if (a < 0 || (a == 0 && adir < 0)) {
397 *b = -a;
398 *bdir = -adir;
399 } else {
400 *b = a;
401 *bdir = adir;
402 }
403 }
404 #endif
405
boundary_sub(int a,int adir,int b,int bdir,int * c,int * cdir)406 void boundary_sub(int a, int adir, int b, int bdir, int *c, int *cdir)
407 {
408 adir = adir < 0 ? -1 : (adir > 0 ? 1 : 0);
409 bdir = bdir < 0 ? -1 : (bdir > 0 ? 1 : 0);
410 *c = a - b;
411 *cdir = adir - bdir;
412 if (*cdir == -2) {
413 assert(*c > INT_MIN);
414 (*c)--;
415 } else if (*cdir == 2) {
416 assert(*c < INT_MAX);
417 (*c)++;
418 }
419 }
420
boundary_lt(unsigned int a,int adir,unsigned int b,int bdir)421 int boundary_lt(unsigned int a, int adir, unsigned int b, int bdir)
422 {
423 assert(a > 0 || adir >= 0);
424 assert(b > 0 || bdir >= 0);
425 if (adir < 0) {
426 a--;
427 adir = 1;
428 } else if (adir > 0)
429 adir = 1;
430 if (bdir < 0) {
431 b--;
432 bdir = 1;
433 } else if (bdir > 0)
434 bdir = 1;
435 return a < b || (a == b && adir < bdir);
436 }
437
438 /* Return 1 if min is nearer to best than max */
boundary_nearer(int min,int mindir,int best,int bestdir,int max,int maxdir)439 int boundary_nearer(int min, int mindir, int best, int bestdir, int max, int maxdir)
440 {
441 int dmin, dmindir;
442 int dmax, dmaxdir;
443 boundary_sub(best, bestdir, min, mindir, &dmin, &dmindir);
444 boundary_sub(max, maxdir, best, bestdir, &dmax, &dmaxdir);
445 return boundary_lt(dmin, dmindir, dmax, dmaxdir);
446 }
447
448