1N/A libparted - a library for manipulating disk partitions 1N/A Copyright (C) 2000, 2007-2010 Free Software Foundation, Inc. 1N/A This program is free software; you can redistribute it and/or modify 1N/A it under the terms of the GNU General Public License as published by 1N/A the Free Software Foundation; either version 3 of the License, or 1N/A (at your option) any later version. 1N/A This program is distributed in the hope that it will be useful, 1N/A but WITHOUT ANY WARRANTY; without even the implied warranty of 1N/A MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1N/A GNU General Public License for more details. 1N/A You should have received a copy of the GNU General Public License 1N/A * \addtogroup PedAlignment 1N/A * \brief Alignment constraint model. 1N/A * This part of libparted models alignment constraints. 1N/A/* Arrrghhh! Why doesn't C have tuples? */ 1N/A/* This function returns "a mod b", the way C should have done it! 1N/A * Mathematicians prefer -3 mod 4 to be 3. Reason: division by N 1N/A * is all about adding or subtracting N, and we like our remainders 1N/A * to be between 0 and N - 1. 1N/A/* Rounds a number down to the closest number that is a multiple of 1N/A/* Rounds a number up to the closest number that is a multiple of 1N/A/* Rounds a number to the closest number that is a multiple of grain_size. */ 1N/A/* This function returns the largest number that divides both a and b. 1N/A * It uses the ancient Euclidean algorithm. 1N/A /* Put the arguments in the "right" format. (Recursive calls made by 1N/A * this function are always in the right format.) 1N/A * Initialize a preallocated piece of memory for an alignment object 1N/A * (used by PedConstraint). 1N/A * The object will represent all sectors \e s for which the equation 1N/A * <tt>s = offset + X * grain_size</tt> holds. 1N/A * Return an alignment object (used by PedConstraint), representing all 1N/A * PedSector's that are of the form <tt>offset + X * grain_size</tt>. 1N/A * Free up memory associated with \p align. 1N/A * Return a duplicate of \p align. 1N/A/* the extended Euclid algorithm. 1N/A * gcd, x and y, such that: 1N/A * gcd = greatest common divisor of a and b 1N/A * This function computes a PedAlignment object that describes the 1N/A * intersection of two alignments. That is, a sector satisfies the 1N/A * new alignment object if and only if it satisfies both of the original 1N/A * ones. (See ped_alignment_is_aligned() for the meaning of "satisfies") 1N/A * Apart from the trivial cases (where one or both of the alignment objects 1N/A * constraints have no sectors that satisfy them), this is what we're trying to 1N/A * - two input constraints: \p a and \p b. 1N/A * - the new grain_size is going to be the lowest common multiple of 1N/A * \p a->grain_size and \p b->grain_size 1N/A * - hard part - solve the simultaneous equations, for offset, where offset, 1N/A * X and Y are variables. (Note: offset can be obtained from either X or Y, 1N/A * by substituing into either equation) 1N/A * offset = \p a->offset + X * \p a->grain_size (1) 1N/A * offset = \p b->offset + Y * \p b->grain_size (2) 1N/A * => Ao + X*Ag = Bo + Y*Bg (1) = (2) 1N/A * X*Ag - Y*Bg = Bo - Ao (3) 1N/A * As it turns out, there only exists a solution if (Bo - Ao) is a multiple 1N/A * of the GCD of Ag and Bg. Reason: all linear combinations of Ag and Bg are 1N/A * multiples of the GCD. 1N/A * = A * (\p a * gcd) + B * (\p b * gcd) 1N/A * = gcd * (A * \p a + B * \p b) 1N/A * gcd is a factor of the linear combination. QED 1N/A * Anyway, \p a * Ag + \p b * Bg = gcd can be solved (for \p a, \p b and gcd) 1N/A * with Euclid's extended algorithm. Then, we just multiply through by 1N/A * (Bo - Ao) / gcd to get (3). 1N/A * A * Ag + B * Bg = gcd 1N/A * A*(Bo-Ao)/gcd * Ag + B(Bo-Ao)/gcd * Bg = gcd * (Bo-Ao)/gcd 1N/A * X*Ag - Y*Bg = Bo - Ao (3) 1N/A * Y = - B*(Bo-Ao)/gcd 1N/A * = Ao + A*(Bo-Ao)/gcd*Ag 1N/A * = Bo - B*(Bo-Ao)/gcd*Ag 1N/A * Thanks go to Nathan Hurst (njh@hawthorn.csse.monash.edu.au) for figuring 1N/A * this algorithm out :-) 1N/A * \note Returned \c NULL is a valid PedAlignment object, and can be used 1N/A for ped_alignment_*() function. 1N/A * \return a PedAlignment on success, \c NULL on failure 1N/A /*PED_DEBUG (0x10, "intersecting alignments (%d,%d) and (%d,%d)", 1N/A a->offset, a->grain_size, b->offset, b->grain_size); 1N/A * either empty or contains exactly one solution 1N/A /* inconsistency => no solution */ 1N/A/* This function returns the sector closest to "sector" that lies inside 1N/A * geom and satisfies the alignment constraint. 1N/A * This function returns the closest sector to \p sector that lies inside 1N/A * \p geom that satisfies the given alignment constraint \p align. It prefers 1N/A * sectors that are beyond \p sector (are not smaller than \p sector), 1N/A * but does not guarantee that this. 1N/A * \return a PedSector on success, \c -1 on failure 1N/A * This function returns the closest sector to \p sector that lies inside 1N/A * \p geom that satisfies the given alignment constraint \p align. It prefers 1N/A * sectors that are before \p sector (are not larger than \p sector), 1N/A * but does not guarantee that this. 1N/A * \return a PedSector on success, \c -1 on failure 1N/A/* Returns either a or b, depending on which is closest to "sector". */ 1N/A * This function returns the sector that is closest to \p sector, 1N/A * satisfies the \p align constraint and lies inside \p geom. 1N/A * \return a PedSector on success, \c -1 on failure 1N/A * This function returns 1 if \p sector satisfies the alignment 1N/A * constraint \p align and lies inside \p geom. 1N/A * \return \c 1 on success, \c 0 on failure