fuchsia / third_party / mesa / 2cbf6ace6fb6b7c4b8ce2b886e8f58cd0107ce45 / . / src / util / fast_urem_by_const.h

/* | |

* Copyright © 2010 Valve Software | |

* | |

* Permission is hereby granted, free of charge, to any person obtaining a | |

* copy of this software and associated documentation files (the "Software"), | |

* to deal in the Software without restriction, including without limitation | |

* the rights to use, copy, modify, merge, publish, distribute, sublicense, | |

* and/or sell copies of the Software, and to permit persons to whom the | |

* Software is furnished to do so, subject to the following conditions: | |

* | |

* The above copyright notice and this permission notice (including the next | |

* paragraph) shall be included in all copies or substantial portions of the | |

* Software. | |

* | |

* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR | |

* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, | |

* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL | |

* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER | |

* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING | |

* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS | |

* IN THE SOFTWARE. | |

*/ | |

#include <stdint.h> | |

/* | |

* Code for fast 32-bit unsigned remainder, based off of "Faster Remainder by | |

* Direct Computation: Applications to Compilers and Software Libraries," | |

* available at https://arxiv.org/pdf/1902.01961.pdf. | |

* | |

* util_fast_urem32(n, d, REMAINDER_MAGIC(d)) returns the same thing as | |

* n % d for any unsigned n and d, however it compiles down to only a few | |

* multiplications, so it should be faster than plain uint32_t modulo if the | |

* same divisor is used many times. | |

*/ | |

#define REMAINDER_MAGIC(divisor) \ | |

((uint64_t) ~0ull / (divisor) + 1) | |

/* | |

* Get bits 64-96 of a 32x64-bit multiply. If __int128_t is available, we use | |

* it, which usually compiles down to one instruction on 64-bit architectures. | |

* Otherwise on 32-bit architectures we usually get four instructions (one | |

* 32x32->64 multiply, one 32x32->32 multiply, and one 64-bit add). | |

*/ | |

static inline uint32_t | |

_mul32by64_hi(uint32_t a, uint64_t b) | |

{ | |

#ifdef HAVE_UINT128 | |

return ((__uint128_t) b * a) >> 64; | |

#else | |

/* | |

* Let b = b0 + 2^32 * b1. Then a * b = a * b0 + 2^32 * a * b1. We would | |

* have to do a 96-bit addition to get the full result, except that only | |

* one term has non-zero lower 32 bits, which means that to get the high 32 | |

* bits, we only have to add the high 64 bits of each term. Unfortunately, | |

* we have to do the 64-bit addition in case the low 32 bits overflow. | |

*/ | |

uint32_t b0 = (uint32_t) b; | |

uint32_t b1 = b >> 32; | |

return ((((uint64_t) a * b0) >> 32) + (uint64_t) a * b1) >> 32; | |

#endif | |

} | |

static inline uint32_t | |

util_fast_urem32(uint32_t n, uint32_t d, uint64_t magic) | |

{ | |

uint64_t lowbits = magic * n; | |

uint32_t result = _mul32by64_hi(d, lowbits); | |

assert(result == n % d); | |

return result; | |

} | |