Lines Matching defs:*
2 * Interval functions
3 * Copyright (c) 2000 by Abramo Bagnara <abramo@alsa-project.org>
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.
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.
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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
22 #define SND_INTERVAL_C
23 #define SND_INTERVAL_INLINE
25 #include <sys/types.h>
26 #include <limits.h>
27 #include "pcm_local.h"
29 static inline void div64_32(u_int64_t *n, u_int32_t d, u_int32_t *rem)
31 *rem = *n % d;
32 *n /= d;
35 static inline unsigned int div32(unsigned int a, unsigned int b,
36 unsigned int *r)
38 if (b == 0) {
39 *r = 0;
40 return UINT_MAX;
42 *r = a % b;
43 return a / b;
46 static inline unsigned int div_down(unsigned int a, unsigned int b)
48 if (b == 0)
49 return UINT_MAX;
50 return a / b;
53 static inline unsigned int div_up(unsigned int a, unsigned int b)
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;
65 static inline unsigned int mul(unsigned int a, unsigned int b)
67 if (a == 0)
68 return 0;
69 if (div_down(UINT_MAX, a) < b)
70 return UINT_MAX;
71 return a * b;
74 static inline unsigned int add(unsigned int a, unsigned int b)
76 if (a >= UINT_MAX - b)
77 return UINT_MAX;
78 return a + b;
81 static inline unsigned int sub(unsigned int a, unsigned int b)
83 if (a > b)
84 return a - b;
85 return 0;
88 static inline unsigned int muldiv32(unsigned int a, unsigned int b,
89 unsigned int c, unsigned int *r)
91 u_int64_t n = (u_int64_t) a * b;
92 if (c == 0) {
93 assert(n > 0);
94 *r = 0;
95 return UINT_MAX;
97 div64_32(&n, c, r);
98 if (n >= UINT_MAX) {
99 *r = 0;
100 return UINT_MAX;
102 return n;
105 int snd_interval_refine_min(snd_interval_t *i, unsigned int min, int openmin)
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;
118 if (i->integer) {
119 if (i->openmin) {
120 i->min++;
121 i->openmin = 0;
124 if (snd_interval_checkempty(i)) {
125 snd_interval_none(i);
126 return -EINVAL;
128 return changed;
131 int snd_interval_refine_max(snd_interval_t *i, unsigned int max, int openmax)
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;
144 if (i->integer) {
145 if (i->openmax) {
146 i->max--;
147 i->openmax = 0;
150 if (snd_interval_checkempty(i)) {
151 snd_interval_none(i);
152 return -EINVAL;
154 return changed;
157 /* r <- v */
158 int snd_interval_refine(snd_interval_t *i, const snd_interval_t *v)
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;
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;
179 if (!i->integer && v->integer) {
180 i->integer = 1;
181 changed = 1;
183 if (i->integer) {
184 if (i->openmin) {
185 i->min++;
186 i->openmin = 0;
188 if (i->openmax) {
189 i->max--;
190 i->openmax = 0;
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;
198 return changed;
201 int snd_interval_refine_first(snd_interval_t *i)
203 if (snd_interval_empty(i))
204 return -ENOENT;
205 if (snd_interval_single(i))
206 return 0;
207 i->max = i->min;
208 i->openmax = i->openmin;
209 if (i->openmax)
210 i->max++;
211 return 1;
214 int snd_interval_refine_last(snd_interval_t *i)
216 if (snd_interval_empty(i))
217 return -ENOENT;
218 if (snd_interval_single(i))
219 return 0;
220 i->min = i->max;
221 i->openmin = i->openmax;
222 if (i->openmin)
223 i->min--;
224 return 1;
227 int snd_interval_refine_set(snd_interval_t *i, unsigned int val)
229 snd_interval_t t;
230 t.empty = 0;
231 t.min = t.max = val;
232 t.openmin = t.openmax = 0;
233 t.integer = 1;
234 return snd_interval_refine(i, &t);
237 void snd_interval_add(const snd_interval_t *a, const snd_interval_t *b, snd_interval_t *c)
239 if (a->empty || b->empty) {
240 snd_interval_none(c);
241 return;
243 c->empty = 0;
244 c->min = add(a->min, b->min);
245 c->openmin = (a->openmin || b->openmin);
246 c->max = add(a->max, b->max);
247 c->openmax = (a->openmax || b->openmax);
248 c->integer = (a->integer && b->integer);
251 void snd_interval_sub(const snd_interval_t *a, const snd_interval_t *b, snd_interval_t *c)
253 if (a->empty || b->empty) {
254 snd_interval_none(c);
255 return;
257 c->empty = 0;
258 c->min = sub(a->min, b->max);
259 c->openmin = (a->openmin || b->openmax);
260 c->max = add(a->max, b->min);
261 c->openmax = (a->openmax || b->openmin);
262 c->integer = (a->integer && b->integer);
265 void snd_interval_mul(const snd_interval_t *a, const snd_interval_t *b, snd_interval_t *c)
267 if (a->empty || b->empty) {
268 snd_interval_none(c);
269 return;
271 c->empty = 0;
272 c->min = mul(a->min, b->min);
273 c->openmin = (a->openmin || b->openmin);
274 c->max = mul(a->max, b->max);
275 c->openmax = (a->openmax || b->openmax);
276 c->integer = (a->integer && b->integer);
279 void snd_interval_div(const snd_interval_t *a, const snd_interval_t *b, snd_interval_t *c)
281 unsigned int r;
282 if (a->empty || b->empty) {
283 snd_interval_none(c);
284 return;
286 c->empty = 0;
287 c->min = div32(a->min, b->max, &r);
288 c->openmin = (r || a->openmin || b->openmax);
289 if (b->min > 0) {
290 c->max = div32(a->max, b->min, &r);
291 if (r) {
292 c->max++;
293 c->openmax = 1;
294 } else
295 c->openmax = (a->openmax || b->openmin);
296 } else {
297 c->max = UINT_MAX;
298 c->openmax = 0;
300 c->integer = 0;
303 /* a * b / c */
304 void snd_interval_muldiv(const snd_interval_t *a, const snd_interval_t *b,
305 const snd_interval_t *c, snd_interval_t *d)
307 unsigned int r;
308 if (a->empty || b->empty || c->empty) {
309 snd_interval_none(d);
310 return;
312 d->empty = 0;
313 d->min = muldiv32(a->min, b->min, c->max, &r);
314 d->openmin = (r || a->openmin || b->openmin || c->openmax);
315 d->max = muldiv32(a->max, b->max, c->min, &r);
316 if (r) {
317 d->max++;
318 d->openmax = 1;
319 } else
320 d->openmax = (a->openmax || b->openmax || c->openmin);
321 d->integer = 0;
324 /* a * b / k */
325 void snd_interval_muldivk(const snd_interval_t *a, const snd_interval_t *b,
326 unsigned int k, snd_interval_t *c)
328 unsigned int r;
329 if (a->empty || b->empty) {
330 snd_interval_none(c);
331 return;
333 c->empty = 0;
334 c->min = muldiv32(a->min, b->min, k, &r);
335 c->openmin = (r || a->openmin || b->openmin);
336 c->max = muldiv32(a->max, b->max, k, &r);
337 if (r) {
338 c->max++;
339 c->openmax = 1;
340 } else
341 c->openmax = (a->openmax || b->openmax);
342 c->integer = 0;
345 /* a * k / b */
346 void snd_interval_mulkdiv(const snd_interval_t *a, unsigned int k,
347 const snd_interval_t *b, snd_interval_t *c)
349 unsigned int r;
350 if (a->empty || b->empty) {
351 snd_interval_none(c);
352 return;
354 c->empty = 0;
355 c->min = muldiv32(a->min, k, b->max, &r);
356 c->openmin = (r || a->openmin || b->openmax);
357 if (b->min > 0) {
358 c->max = muldiv32(a->max, k, b->min, &r);
359 if (r) {
360 c->max++;
361 c->openmax = 1;
362 } else
363 c->openmax = (a->openmax || b->openmin);
364 } else {
365 c->max = UINT_MAX;
366 c->openmax = 0;
368 c->integer = 0;
371 void snd_interval_print(const snd_interval_t *i, snd_output_t *out)
373 if (snd_interval_empty(i))
374 snd_output_printf(out, "NONE");
375 else if (i->min == 0 && i->openmin == 0 &&
376 i->max == UINT_MAX && i->openmax == 0)
377 snd_output_printf(out, "ALL");
378 else if (snd_interval_single(i) && i->integer)
379 snd_output_printf(out, "%u", snd_interval_value(i));
380 else
381 snd_output_printf(out, "%c%u %u%c",
382 i->openmin ? '(' : '[',
383 i->min, i->max,
384 i->openmax ? ')' : ']');
387 #if 0
388 static void boundary_abs(int a, int adir, int *b, int *bdir)
390 if (a < 0 || (a == 0 && adir < 0)) {
391 *b = -a;
392 *bdir = -adir;
393 } else {
394 *b = a;
395 *bdir = adir;
398 #endif
400 void boundary_sub(int a, int adir, int b, int bdir, int *c, int *cdir)
402 adir = adir < 0 ? -1 : (adir > 0 ? 1 : 0);
403 bdir = bdir < 0 ? -1 : (bdir > 0 ? 1 : 0);
404 *c = a - b;
405 *cdir = adir - bdir;
406 if (*cdir == -2) {
407 assert(*c > INT_MIN);
408 (*c)--;
409 } else if (*cdir == 2) {
410 assert(*c < INT_MAX);
411 (*c)++;
415 int boundary_lt(unsigned int a, int adir, unsigned int b, int bdir)
417 assert(a > 0 || adir >= 0);
418 assert(b > 0 || bdir >= 0);
419 if (adir < 0) {
420 a--;
421 adir = 1;
422 } else if (adir > 0)
423 adir = 1;
424 if (bdir < 0) {
425 b--;
426 bdir = 1;
427 } else if (bdir > 0)
428 bdir = 1;
429 return a < b || (a == b && adir < bdir);
432 /* Return 1 if min is nearer to best than max */
433 int boundary_nearer(int min, int mindir, int best, int bestdir, int max, int maxdir)
435 int dmin, dmindir;
436 int dmax, dmaxdir;
437 boundary_sub(best, bestdir, min, mindir, &dmin, &dmindir);
438 boundary_sub(max, maxdir, best, bestdir, &dmax, &dmaxdir);
439 return boundary_lt(dmin, dmindir, dmax, dmaxdir);