1 /* 2 * Interval functions 3 * Copyright (c) 2000 by Abramo Bagnara <abramo (at) 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 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 29 static inline void div64_32(u_int64_t *n, u_int32_t d, u_int32_t *rem) 30 { 31 *rem = *n % d; 32 *n /= d; 33 } 34 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 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 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 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 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 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 88 static inline unsigned int muldiv32(unsigned int a, unsigned int b, 89 unsigned int c, unsigned int *r) 90 { 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; 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 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 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 */ 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 201 int snd_interval_refine_first(snd_interval_t *i) 202 { 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; 212 } 213 214 int snd_interval_refine_last(snd_interval_t *i) 215 { 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; 225 } 226 227 int snd_interval_refine_set(snd_interval_t *i, unsigned int val) 228 { 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); 235 } 236 237 void snd_interval_add(const snd_interval_t *a, const snd_interval_t *b, snd_interval_t *c) 238 { 239 if (a->empty || b->empty) { 240 snd_interval_none(c); 241 return; 242 } 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); 249 } 250 251 void snd_interval_sub(const snd_interval_t *a, const snd_interval_t *b, snd_interval_t *c) 252 { 253 if (a->empty || b->empty) { 254 snd_interval_none(c); 255 return; 256 } 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); 263 } 264 265 void snd_interval_mul(const snd_interval_t *a, const snd_interval_t *b, snd_interval_t *c) 266 { 267 if (a->empty || b->empty) { 268 snd_interval_none(c); 269 return; 270 } 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); 277 } 278 279 void snd_interval_div(const snd_interval_t *a, const snd_interval_t *b, snd_interval_t *c) 280 { 281 unsigned int r; 282 if (a->empty || b->empty) { 283 snd_interval_none(c); 284 return; 285 } 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; 299 } 300 c->integer = 0; 301 } 302 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) 306 { 307 unsigned int r; 308 if (a->empty || b->empty || c->empty) { 309 snd_interval_none(d); 310 return; 311 } 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; 322 } 323 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) 327 { 328 unsigned int r; 329 if (a->empty || b->empty) { 330 snd_interval_none(c); 331 return; 332 } 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; 343 } 344 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) 348 { 349 unsigned int r; 350 if (a->empty || b->empty) { 351 snd_interval_none(c); 352 return; 353 } 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; 367 } 368 c->integer = 0; 369 } 370 371 void snd_interval_print(const snd_interval_t *i, snd_output_t *out) 372 { 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 ? ')' : ']'); 385 } 386 387 #if 0 388 static void boundary_abs(int a, int adir, int *b, int *bdir) 389 { 390 if (a < 0 || (a == 0 && adir < 0)) { 391 *b = -a; 392 *bdir = -adir; 393 } else { 394 *b = a; 395 *bdir = adir; 396 } 397 } 398 #endif 399 400 void boundary_sub(int a, int adir, int b, int bdir, int *c, int *cdir) 401 { 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)++; 412 } 413 } 414 415 int boundary_lt(unsigned int a, int adir, unsigned int b, int bdir) 416 { 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); 430 } 431 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) 434 { 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); 440 } 441 442
