1N/A/*
1N/A libparted - a library for manipulating disk partitions
1N/A Copyright (C) 2000, 2007-2010 Free Software Foundation, Inc.
1N/A
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
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
1N/A You should have received a copy of the GNU General Public License
1N/A along with this program. If not, see <http://www.gnu.org/licenses/>.
1N/A*/
1N/A
1N/A/**
1N/A * \file natmath.c
1N/A */
1N/A
1N/A/**
1N/A * \addtogroup PedAlignment
1N/A *
1N/A * \brief Alignment constraint model.
1N/A *
1N/A * This part of libparted models alignment constraints.
1N/A *
1N/A * @{
1N/A */
1N/A
1N/A#include <config.h>
1N/A#include <stdlib.h>
1N/A#include <parted/parted.h>
1N/A#include <parted/debug.h>
1N/A#include <parted/natmath.h>
1N/A
1N/A/* Arrrghhh! Why doesn't C have tuples? */
1N/Atypedef struct {
1N/A PedSector gcd; /* "converges" to the gcd */
1N/A PedSector x;
1N/A PedSector y;
1N/A} EuclidTriple;
1N/A
1N/Astatic const PedAlignment _any = {
1N/A .offset = 0,
1N/A .grain_size = 1
1N/A};
1N/A
1N/Aconst PedAlignment* ped_alignment_any = &_any;
1N/Aconst PedAlignment* ped_alignment_none = NULL;
1N/A
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 */
1N/Astatic PedSector
1N/Aabs_mod (PedSector a, PedSector b)
1N/A{
1N/A if (a < 0)
1N/A return a % b + b;
1N/A else
1N/A return a % b;
1N/A}
1N/A
1N/A/* Rounds a number down to the closest number that is a multiple of
1N/A * grain_size.
1N/A */
1N/APedSector
1N/Aped_round_down_to (PedSector sector, PedSector grain_size)
1N/A{
1N/A return sector - abs_mod (sector, grain_size);
1N/A}
1N/A
1N/A/* Rounds a number up to the closest number that is a multiple of
1N/A * grain_size.
1N/A */
1N/APedSector
1N/Aped_round_up_to (PedSector sector, PedSector grain_size)
1N/A{
1N/A if (sector % grain_size)
1N/A return ped_round_down_to (sector, grain_size) + grain_size;
1N/A else
1N/A return sector;
1N/A}
1N/A
1N/A/* Rounds a number to the closest number that is a multiple of grain_size. */
1N/APedSector
1N/Aped_round_to_nearest (PedSector sector, PedSector grain_size)
1N/A{
1N/A if (sector % grain_size > grain_size/2)
1N/A return ped_round_up_to (sector, grain_size);
1N/A else
1N/A return ped_round_down_to (sector, grain_size);
1N/A}
1N/A
1N/A/* This function returns the largest number that divides both a and b.
1N/A * It uses the ancient Euclidean algorithm.
1N/A */
1N/APedSector
1N/Aped_greatest_common_divisor (PedSector a, PedSector b)
1N/A{
1N/A PED_ASSERT (a >= 0, return 0);
1N/A PED_ASSERT (b >= 0, return 0);
1N/A
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 */
1N/A if (b > a)
1N/A return ped_greatest_common_divisor (b, a);
1N/A
1N/A if (b)
1N/A return ped_greatest_common_divisor (b, a % b);
1N/A else
1N/A return a;
1N/A}
1N/A
1N/A/**
1N/A * Initialize a preallocated piece of memory for an alignment object
1N/A * (used by PedConstraint).
1N/A *
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 */
1N/Aint
1N/Aped_alignment_init (PedAlignment* align, PedSector offset, PedSector grain_size)
1N/A{
1N/A PED_ASSERT (align != NULL, return 0);
1N/A
1N/A if (grain_size < 0)
1N/A return 0;
1N/A
1N/A if (grain_size)
1N/A align->offset = abs_mod (offset, grain_size);
1N/A else
1N/A align->offset = offset;
1N/A align->grain_size = grain_size;
1N/A
1N/A return 1;
1N/A}
1N/A
1N/A/**
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 */
1N/APedAlignment*
1N/Aped_alignment_new (PedSector offset, PedSector grain_size)
1N/A{
1N/A PedAlignment* align;
1N/A
1N/A align = (PedAlignment*) ped_malloc (sizeof (PedAlignment));
1N/A if (!align)
1N/A goto error;
1N/A
1N/A if (!ped_alignment_init (align, offset, grain_size))
1N/A goto error_free_align;
1N/A
1N/A return align;
1N/A
1N/Aerror_free_align:
1N/A free (align);
1N/Aerror:
1N/A return NULL;
1N/A}
1N/A
1N/A/**
1N/A * Free up memory associated with \p align.
1N/A */
1N/Avoid
1N/Aped_alignment_destroy (PedAlignment* align)
1N/A{
1N/A free (align);
1N/A}
1N/A
1N/A/**
1N/A * Return a duplicate of \p align.
1N/A */
1N/APedAlignment*
1N/Aped_alignment_duplicate (const PedAlignment* align)
1N/A{
1N/A if (!align)
1N/A return NULL;
1N/A return ped_alignment_new (align->offset, align->grain_size);
1N/A}
1N/A
1N/A/* the extended Euclid algorithm.
1N/A *
1N/A * input:
1N/A * a and b, a > b
1N/A *
1N/A * output:
1N/A * gcd, x and y, such that:
1N/A *
1N/A * gcd = greatest common divisor of a and b
1N/A * gcd = x*a + y*b
1N/A */
1N/Astatic EuclidTriple
1N/Aextended_euclid (int a, int b)
1N/A{
1N/A EuclidTriple result;
1N/A EuclidTriple tmp;
1N/A
1N/A if (b == 0) {
1N/A result.gcd = a;
1N/A result.x = 1;
1N/A result.y = 0;
1N/A return result;
1N/A }
1N/A
1N/A tmp = extended_euclid (b, a % b);
1N/A result.gcd = tmp.gcd;
1N/A result.x = tmp.y;
1N/A result.y = tmp.x - (a/b) * tmp.y;
1N/A return result;
1N/A}
1N/A
1N/A/**
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 *
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 * do:
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 *
1N/A * \code
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 * \endcode
1N/A *
1N/A * or, abbreviated:
1N/A *
1N/A * \code
1N/A * o = Ao + X*Ag (1)
1N/A * o = Bo + Y*Bg (2)
1N/A *
1N/A * => Ao + X*Ag = Bo + Y*Bg (1) = (2)
1N/A * X*Ag - Y*Bg = Bo - Ao (3)
1N/A * \endcode
1N/A *
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 *
1N/A * Proof:
1N/A *
1N/A * \code
1N/A * A * Ag + B * Bg
1N/A * = A * (\p a * gcd) + B * (\p b * gcd)
1N/A * = gcd * (A * \p a + B * \p b)
1N/A * \endcode
1N/A *
1N/A * gcd is a factor of the linear combination. QED
1N/A *
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 *
1N/A * i.e.
1N/A * \code
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 *
1N/A * X = A*(Bo-Ao)/gcd
1N/A * Y = - B*(Bo-Ao)/gcd
1N/A * \endcode
1N/A *
1N/A * then:
1N/A * \code
1N/A * o = Ao + X*Ag (1)
1N/A * = Ao + A*(Bo-Ao)/gcd*Ag
1N/A * o = Bo + Y*Bg (2)
1N/A * = Bo - B*(Bo-Ao)/gcd*Ag
1N/A * \endcode
1N/A *
1N/A * Thanks go to Nathan Hurst (njh@hawthorn.csse.monash.edu.au) for figuring
1N/A * this algorithm out :-)
1N/A *
1N/A * \note Returned \c NULL is a valid PedAlignment object, and can be used
1N/A for ped_alignment_*() function.
1N/A *
1N/A * \return a PedAlignment on success, \c NULL on failure
1N/A */
1N/APedAlignment*
1N/Aped_alignment_intersect (const PedAlignment* a, const PedAlignment* b)
1N/A{
1N/A PedSector new_grain_size;
1N/A PedSector new_offset;
1N/A PedSector delta_on_gcd;
1N/A EuclidTriple gcd_factors;
1N/A
1N/A
1N/A if (!a || !b)
1N/A return NULL;
1N/A
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 */
1N/A
1N/A if (a->grain_size < b->grain_size) {
1N/A const PedAlignment* tmp;
1N/A tmp = a; a = b; b = tmp;
1N/A }
1N/A
1N/A /* weird/trivial case: where the solution space for "a" or "b" is
1N/A * either empty or contains exactly one solution
1N/A */
1N/A if (a->grain_size == 0 && b->grain_size == 0) {
1N/A if (a->offset == b->offset)
1N/A return ped_alignment_duplicate (a);
1N/A else
1N/A return NULL;
1N/A }
1N/A
1N/A /* general case */
1N/A gcd_factors = extended_euclid (a->grain_size, b->grain_size);
1N/A
1N/A delta_on_gcd = (b->offset - a->offset) / gcd_factors.gcd;
1N/A new_offset = a->offset + gcd_factors.x * delta_on_gcd * a->grain_size;
1N/A new_grain_size = a->grain_size * b->grain_size / gcd_factors.gcd;
1N/A
1N/A /* inconsistency => no solution */
1N/A if (new_offset
1N/A != b->offset - gcd_factors.y * delta_on_gcd * b->grain_size)
1N/A return NULL;
1N/A
1N/A return ped_alignment_new (new_offset, new_grain_size);
1N/A}
1N/A
1N/A/* This function returns the sector closest to "sector" that lies inside
1N/A * geom and satisfies the alignment constraint.
1N/A */
1N/Astatic PedSector
1N/A_closest_inside_geometry (const PedAlignment* align, const PedGeometry* geom,
1N/A PedSector sector)
1N/A{
1N/A PED_ASSERT (align != NULL, return -1);
1N/A
1N/A if (!align->grain_size) {
1N/A if (ped_alignment_is_aligned (align, geom, sector)
1N/A && (!geom || ped_geometry_test_sector_inside (geom,
1N/A sector)))
1N/A return sector;
1N/A else
1N/A return -1;
1N/A }
1N/A
1N/A if (sector < geom->start)
1N/A sector += ped_round_up_to (geom->start - sector,
1N/A align->grain_size);
1N/A if (sector > geom->end)
1N/A sector -= ped_round_up_to (sector - geom->end,
1N/A align->grain_size);
1N/A
1N/A if (!ped_geometry_test_sector_inside (geom, sector))
1N/A return -1;
1N/A return sector;
1N/A}
1N/A
1N/A/**
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 *
1N/A * \return a PedSector on success, \c -1 on failure
1N/A */
1N/APedSector
1N/Aped_alignment_align_up (const PedAlignment* align, const PedGeometry* geom,
1N/A PedSector sector)
1N/A{
1N/A PedSector result;
1N/A
1N/A PED_ASSERT (align != NULL, return -1);
1N/A
1N/A if (!align->grain_size)
1N/A result = align->offset;
1N/A else
1N/A result = ped_round_up_to (sector - align->offset,
1N/A align->grain_size)
1N/A + align->offset;
1N/A
1N/A if (geom)
1N/A result = _closest_inside_geometry (align, geom, result);
1N/A return result;
1N/A}
1N/A
1N/A/**
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 *
1N/A * \return a PedSector on success, \c -1 on failure
1N/A */
1N/APedSector
1N/Aped_alignment_align_down (const PedAlignment* align, const PedGeometry* geom,
1N/A PedSector sector)
1N/A{
1N/A PedSector result;
1N/A
1N/A PED_ASSERT (align != NULL, return -1);
1N/A
1N/A if (!align->grain_size)
1N/A result = align->offset;
1N/A else
1N/A result = ped_round_down_to (sector - align->offset,
1N/A align->grain_size)
1N/A + align->offset;
1N/A
1N/A if (geom)
1N/A result = _closest_inside_geometry (align, geom, result);
1N/A return result;
1N/A}
1N/A
1N/A/* Returns either a or b, depending on which is closest to "sector". */
1N/Astatic PedSector
1N/Aclosest (PedSector sector, PedSector a, PedSector b)
1N/A{
1N/A if (a == -1)
1N/A return b;
1N/A if (b == -1)
1N/A return a;
1N/A
1N/A if (abs (sector - a) < abs (sector - b))
1N/A return a;
1N/A else
1N/A return b;
1N/A}
1N/A
1N/A/**
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 *
1N/A * \return a PedSector on success, \c -1 on failure
1N/A */
1N/APedSector
1N/Aped_alignment_align_nearest (const PedAlignment* align, const PedGeometry* geom,
1N/A PedSector sector)
1N/A{
1N/A PED_ASSERT (align != NULL, return -1);
1N/A
1N/A return closest (sector, ped_alignment_align_up (align, geom, sector),
1N/A ped_alignment_align_down (align, geom, sector));
1N/A}
1N/A
1N/A/**
1N/A * This function returns 1 if \p sector satisfies the alignment
1N/A * constraint \p align and lies inside \p geom.
1N/A *
1N/A * \return \c 1 on success, \c 0 on failure
1N/A */
1N/Aint
1N/Aped_alignment_is_aligned (const PedAlignment* align, const PedGeometry* geom,
1N/A PedSector sector)
1N/A{
1N/A if (!align)
1N/A return 0;
1N/A
1N/A if (geom && !ped_geometry_test_sector_inside (geom, sector))
1N/A return 0;
1N/A
1N/A if (align->grain_size)
1N/A return (sector - align->offset) % align->grain_size == 0;
1N/A else
1N/A return sector == align->offset;
1N/A}
1N/A
1N/A/**
1N/A * @}
1N/A */