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 "pcm_local.h" 26#include <sys/types.h> 27#include <limits.h> 28 29static inline void div64_32(uint64_t *n, uint32_t d, uint32_t *rem) 30{ 31 *rem = *n % d; 32 *n /= d; 33} 34 35static 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 46static 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 53static 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 65static 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 74static 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 81static inline unsigned int sub(unsigned int a, unsigned int b) 82{ 83 if (a > b) 84 return a - b; 85 return 0; 86} 87 88static 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 105int 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 131int 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 */ 158int 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 201int 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 217int 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 233int 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 243void 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 257void 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 271void 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 285void 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 */ 310void 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 */ 331void 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 */ 352void 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 377void 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 394static 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 406void 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 421int 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 */ 439int 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