1 /* 2 * Copyright (c) 2015 Rimvydas Jasinskas 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice unmodified, this list of conditions, and the following 10 * disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 16 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 17 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 18 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 19 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 20 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 24 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 25 */ 26 27 /* 28 * Standard math function to compute biggest common divisor, 29 * based on Euclids algorithm. 30 * 31 * Long implementation adapted-from: 32 * lib/libc/stdlib/getopt_long.c 33 * 34 * Uses: 35 * 64-bit values; 36 * simplified loop form [if(MIN(a,b) == 0) return MAX(a,b)]; 37 * swap() arguments just in case.. 38 */ 39 40 #ifndef _GCD_H 41 #define _GCD_H 42 43 #include <linux/kernel.h> 44 45 static inline uint64_t gcd64(uint64_t a, uint64_t b) __pure2; 46 47 /* 48 * Compute the greatest common divisor of a and b. 49 */ 50 static inline uint64_t 51 gcd64(uint64_t a, uint64_t b) 52 { 53 uint64_t c; 54 55 if (a < b) 56 swap(a, b); 57 58 if (b == 0) 59 return a; 60 61 while ((c = a % b) != 0) { 62 a = b; 63 b = c; 64 } 65 66 return (b); 67 } 68 69 static inline unsigned long 70 gcd(unsigned long a, unsigned long b) 71 { 72 return gcd64(a, b); 73 } 74 75 #endif /* _GCD_H */ 76