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