1*9663SMark.Logan@Sun.COM /* 2*9663SMark.Logan@Sun.COM libparted - a library for manipulating disk partitions 3*9663SMark.Logan@Sun.COM Copyright (C) 2000, 2007 Free Software Foundation, Inc. 4*9663SMark.Logan@Sun.COM 5*9663SMark.Logan@Sun.COM This program is free software; you can redistribute it and/or modify 6*9663SMark.Logan@Sun.COM it under the terms of the GNU General Public License as published by 7*9663SMark.Logan@Sun.COM the Free Software Foundation; either version 3 of the License, or 8*9663SMark.Logan@Sun.COM (at your option) any later version. 9*9663SMark.Logan@Sun.COM 10*9663SMark.Logan@Sun.COM This program is distributed in the hope that it will be useful, 11*9663SMark.Logan@Sun.COM but WITHOUT ANY WARRANTY; without even the implied warranty of 12*9663SMark.Logan@Sun.COM MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13*9663SMark.Logan@Sun.COM GNU General Public License for more details. 14*9663SMark.Logan@Sun.COM 15*9663SMark.Logan@Sun.COM You should have received a copy of the GNU General Public License 16*9663SMark.Logan@Sun.COM along with this program. If not, see <http://www.gnu.org/licenses/>. 17*9663SMark.Logan@Sun.COM */ 18*9663SMark.Logan@Sun.COM 19*9663SMark.Logan@Sun.COM /** 20*9663SMark.Logan@Sun.COM * \file natmath.c 21*9663SMark.Logan@Sun.COM */ 22*9663SMark.Logan@Sun.COM 23*9663SMark.Logan@Sun.COM /** 24*9663SMark.Logan@Sun.COM * \addtogroup PedAlignment 25*9663SMark.Logan@Sun.COM * 26*9663SMark.Logan@Sun.COM * \brief Alignment constraint model. 27*9663SMark.Logan@Sun.COM * 28*9663SMark.Logan@Sun.COM * This part of libparted models alignment constraints. 29*9663SMark.Logan@Sun.COM * 30*9663SMark.Logan@Sun.COM * @{ 31*9663SMark.Logan@Sun.COM */ 32*9663SMark.Logan@Sun.COM 33*9663SMark.Logan@Sun.COM #include <config.h> 34*9663SMark.Logan@Sun.COM #include <stdlib.h> 35*9663SMark.Logan@Sun.COM #include <parted/parted.h> 36*9663SMark.Logan@Sun.COM #include <parted/debug.h> 37*9663SMark.Logan@Sun.COM #include <parted/natmath.h> 38*9663SMark.Logan@Sun.COM 39*9663SMark.Logan@Sun.COM /* Arrrghhh! Why doesn't C have tuples? */ 40*9663SMark.Logan@Sun.COM typedef struct { 41*9663SMark.Logan@Sun.COM PedSector gcd; /* "converges" to the gcd */ 42*9663SMark.Logan@Sun.COM PedSector x; 43*9663SMark.Logan@Sun.COM PedSector y; 44*9663SMark.Logan@Sun.COM } EuclidTriple; 45*9663SMark.Logan@Sun.COM 46*9663SMark.Logan@Sun.COM static const PedAlignment _any = { 47*9663SMark.Logan@Sun.COM .offset = 0, 48*9663SMark.Logan@Sun.COM .grain_size = 1 49*9663SMark.Logan@Sun.COM }; 50*9663SMark.Logan@Sun.COM 51*9663SMark.Logan@Sun.COM const PedAlignment* ped_alignment_any = &_any; 52*9663SMark.Logan@Sun.COM const PedAlignment* ped_alignment_none = NULL; 53*9663SMark.Logan@Sun.COM 54*9663SMark.Logan@Sun.COM /* This function returns "a mod b", the way C should have done it! 55*9663SMark.Logan@Sun.COM * Mathematicians prefer -3 mod 4 to be 3. Reason: division by N 56*9663SMark.Logan@Sun.COM * is all about adding or subtracting N, and we like our remainders 57*9663SMark.Logan@Sun.COM * to be between 0 and N - 1. 58*9663SMark.Logan@Sun.COM */ 59*9663SMark.Logan@Sun.COM PedSector 60*9663SMark.Logan@Sun.COM abs_mod (PedSector a, PedSector b) 61*9663SMark.Logan@Sun.COM { 62*9663SMark.Logan@Sun.COM if (a < 0) 63*9663SMark.Logan@Sun.COM return a % b + b; 64*9663SMark.Logan@Sun.COM else 65*9663SMark.Logan@Sun.COM return a % b; 66*9663SMark.Logan@Sun.COM } 67*9663SMark.Logan@Sun.COM 68*9663SMark.Logan@Sun.COM /* Rounds a number down to the closest number that is a multiple of 69*9663SMark.Logan@Sun.COM * grain_size. 70*9663SMark.Logan@Sun.COM */ 71*9663SMark.Logan@Sun.COM PedSector 72*9663SMark.Logan@Sun.COM ped_round_down_to (PedSector sector, PedSector grain_size) 73*9663SMark.Logan@Sun.COM { 74*9663SMark.Logan@Sun.COM return sector - abs_mod (sector, grain_size); 75*9663SMark.Logan@Sun.COM } 76*9663SMark.Logan@Sun.COM 77*9663SMark.Logan@Sun.COM #ifdef __sun 78*9663SMark.Logan@Sun.COM extern PedSector 79*9663SMark.Logan@Sun.COM #else 80*9663SMark.Logan@Sun.COM extern inline PedSector 81*9663SMark.Logan@Sun.COM #endif 82*9663SMark.Logan@Sun.COM ped_div_round_up (PedSector numerator, PedSector divisor) 83*9663SMark.Logan@Sun.COM { 84*9663SMark.Logan@Sun.COM return (numerator + divisor - 1) / divisor; 85*9663SMark.Logan@Sun.COM } 86*9663SMark.Logan@Sun.COM 87*9663SMark.Logan@Sun.COM #ifdef __sun 88*9663SMark.Logan@Sun.COM extern PedSector 89*9663SMark.Logan@Sun.COM #else 90*9663SMark.Logan@Sun.COM extern inline PedSector 91*9663SMark.Logan@Sun.COM #endif 92*9663SMark.Logan@Sun.COM ped_div_round_to_nearest (PedSector numerator, PedSector divisor) 93*9663SMark.Logan@Sun.COM { 94*9663SMark.Logan@Sun.COM return (numerator + divisor/2) / divisor; 95*9663SMark.Logan@Sun.COM } 96*9663SMark.Logan@Sun.COM 97*9663SMark.Logan@Sun.COM /* Rounds a number up to the closest number that is a multiple of 98*9663SMark.Logan@Sun.COM * grain_size. 99*9663SMark.Logan@Sun.COM */ 100*9663SMark.Logan@Sun.COM PedSector 101*9663SMark.Logan@Sun.COM ped_round_up_to (PedSector sector, PedSector grain_size) 102*9663SMark.Logan@Sun.COM { 103*9663SMark.Logan@Sun.COM if (sector % grain_size) 104*9663SMark.Logan@Sun.COM return ped_round_down_to (sector, grain_size) + grain_size; 105*9663SMark.Logan@Sun.COM else 106*9663SMark.Logan@Sun.COM return sector; 107*9663SMark.Logan@Sun.COM } 108*9663SMark.Logan@Sun.COM 109*9663SMark.Logan@Sun.COM /* Rounds a number to the closest number that is a multiple of grain_size. */ 110*9663SMark.Logan@Sun.COM PedSector 111*9663SMark.Logan@Sun.COM ped_round_to_nearest (PedSector sector, PedSector grain_size) 112*9663SMark.Logan@Sun.COM { 113*9663SMark.Logan@Sun.COM if (sector % grain_size > grain_size/2) 114*9663SMark.Logan@Sun.COM return ped_round_up_to (sector, grain_size); 115*9663SMark.Logan@Sun.COM else 116*9663SMark.Logan@Sun.COM return ped_round_down_to (sector, grain_size); 117*9663SMark.Logan@Sun.COM } 118*9663SMark.Logan@Sun.COM 119*9663SMark.Logan@Sun.COM /* This function returns the largest number that divides both a and b. 120*9663SMark.Logan@Sun.COM * It uses the ancient Euclidean algorithm. 121*9663SMark.Logan@Sun.COM */ 122*9663SMark.Logan@Sun.COM PedSector 123*9663SMark.Logan@Sun.COM ped_greatest_common_divisor (PedSector a, PedSector b) 124*9663SMark.Logan@Sun.COM { 125*9663SMark.Logan@Sun.COM PED_ASSERT (a >= 0, return 0); 126*9663SMark.Logan@Sun.COM PED_ASSERT (b >= 0, return 0); 127*9663SMark.Logan@Sun.COM 128*9663SMark.Logan@Sun.COM /* Put the arguments in the "right" format. (Recursive calls made by 129*9663SMark.Logan@Sun.COM * this function are always in the right format.) 130*9663SMark.Logan@Sun.COM */ 131*9663SMark.Logan@Sun.COM if (b > a) 132*9663SMark.Logan@Sun.COM return ped_greatest_common_divisor (b, a); 133*9663SMark.Logan@Sun.COM 134*9663SMark.Logan@Sun.COM if (b) 135*9663SMark.Logan@Sun.COM return ped_greatest_common_divisor (b, a % b); 136*9663SMark.Logan@Sun.COM else 137*9663SMark.Logan@Sun.COM return a; 138*9663SMark.Logan@Sun.COM } 139*9663SMark.Logan@Sun.COM 140*9663SMark.Logan@Sun.COM /** 141*9663SMark.Logan@Sun.COM * Initialize a preallocated piece of memory for an alignment object 142*9663SMark.Logan@Sun.COM * (used by PedConstraint). 143*9663SMark.Logan@Sun.COM * 144*9663SMark.Logan@Sun.COM * The object will represent all sectors \e s for which the equation 145*9663SMark.Logan@Sun.COM * <tt>s = offset + X * grain_size</tt> holds. 146*9663SMark.Logan@Sun.COM */ 147*9663SMark.Logan@Sun.COM int 148*9663SMark.Logan@Sun.COM ped_alignment_init (PedAlignment* align, PedSector offset, PedSector grain_size) 149*9663SMark.Logan@Sun.COM { 150*9663SMark.Logan@Sun.COM PED_ASSERT (align != NULL, return 0); 151*9663SMark.Logan@Sun.COM 152*9663SMark.Logan@Sun.COM if (grain_size < 0) 153*9663SMark.Logan@Sun.COM return 0; 154*9663SMark.Logan@Sun.COM 155*9663SMark.Logan@Sun.COM if (grain_size) 156*9663SMark.Logan@Sun.COM align->offset = abs_mod (offset, grain_size); 157*9663SMark.Logan@Sun.COM else 158*9663SMark.Logan@Sun.COM align->offset = offset; 159*9663SMark.Logan@Sun.COM align->grain_size = grain_size; 160*9663SMark.Logan@Sun.COM 161*9663SMark.Logan@Sun.COM return 1; 162*9663SMark.Logan@Sun.COM } 163*9663SMark.Logan@Sun.COM 164*9663SMark.Logan@Sun.COM /** 165*9663SMark.Logan@Sun.COM * Return an alignment object (used by PedConstraint), representing all 166*9663SMark.Logan@Sun.COM * PedSector's that are of the form <tt>offset + X * grain_size</tt>. 167*9663SMark.Logan@Sun.COM */ 168*9663SMark.Logan@Sun.COM PedAlignment* 169*9663SMark.Logan@Sun.COM ped_alignment_new (PedSector offset, PedSector grain_size) 170*9663SMark.Logan@Sun.COM { 171*9663SMark.Logan@Sun.COM PedAlignment* align; 172*9663SMark.Logan@Sun.COM 173*9663SMark.Logan@Sun.COM align = (PedAlignment*) ped_malloc (sizeof (PedAlignment)); 174*9663SMark.Logan@Sun.COM if (!align) 175*9663SMark.Logan@Sun.COM goto error; 176*9663SMark.Logan@Sun.COM 177*9663SMark.Logan@Sun.COM if (!ped_alignment_init (align, offset, grain_size)) 178*9663SMark.Logan@Sun.COM goto error_free_align; 179*9663SMark.Logan@Sun.COM 180*9663SMark.Logan@Sun.COM return align; 181*9663SMark.Logan@Sun.COM 182*9663SMark.Logan@Sun.COM error_free_align: 183*9663SMark.Logan@Sun.COM ped_free (align); 184*9663SMark.Logan@Sun.COM error: 185*9663SMark.Logan@Sun.COM return NULL; 186*9663SMark.Logan@Sun.COM } 187*9663SMark.Logan@Sun.COM 188*9663SMark.Logan@Sun.COM /** 189*9663SMark.Logan@Sun.COM * Free up memory associated with \p align. 190*9663SMark.Logan@Sun.COM */ 191*9663SMark.Logan@Sun.COM void 192*9663SMark.Logan@Sun.COM ped_alignment_destroy (PedAlignment* align) 193*9663SMark.Logan@Sun.COM { 194*9663SMark.Logan@Sun.COM if (align) 195*9663SMark.Logan@Sun.COM ped_free (align); 196*9663SMark.Logan@Sun.COM } 197*9663SMark.Logan@Sun.COM 198*9663SMark.Logan@Sun.COM /** 199*9663SMark.Logan@Sun.COM * Return a duplicate of \p align. 200*9663SMark.Logan@Sun.COM */ 201*9663SMark.Logan@Sun.COM PedAlignment* 202*9663SMark.Logan@Sun.COM ped_alignment_duplicate (const PedAlignment* align) 203*9663SMark.Logan@Sun.COM { 204*9663SMark.Logan@Sun.COM if (!align) 205*9663SMark.Logan@Sun.COM return NULL; 206*9663SMark.Logan@Sun.COM return ped_alignment_new (align->offset, align->grain_size); 207*9663SMark.Logan@Sun.COM } 208*9663SMark.Logan@Sun.COM 209*9663SMark.Logan@Sun.COM /* the extended Euclid algorithm. 210*9663SMark.Logan@Sun.COM * 211*9663SMark.Logan@Sun.COM * input: 212*9663SMark.Logan@Sun.COM * a and b, a > b 213*9663SMark.Logan@Sun.COM * 214*9663SMark.Logan@Sun.COM * output: 215*9663SMark.Logan@Sun.COM * gcd, x and y, such that: 216*9663SMark.Logan@Sun.COM * 217*9663SMark.Logan@Sun.COM * gcd = greatest common divisor of a and b 218*9663SMark.Logan@Sun.COM * gcd = x*a + y*b 219*9663SMark.Logan@Sun.COM */ 220*9663SMark.Logan@Sun.COM EuclidTriple 221*9663SMark.Logan@Sun.COM extended_euclid (int a, int b) 222*9663SMark.Logan@Sun.COM { 223*9663SMark.Logan@Sun.COM EuclidTriple result; 224*9663SMark.Logan@Sun.COM EuclidTriple tmp; 225*9663SMark.Logan@Sun.COM 226*9663SMark.Logan@Sun.COM if (b == 0) { 227*9663SMark.Logan@Sun.COM result.gcd = a; 228*9663SMark.Logan@Sun.COM result.x = 1; 229*9663SMark.Logan@Sun.COM result.y = 0; 230*9663SMark.Logan@Sun.COM return result; 231*9663SMark.Logan@Sun.COM } 232*9663SMark.Logan@Sun.COM 233*9663SMark.Logan@Sun.COM tmp = extended_euclid (b, a % b); 234*9663SMark.Logan@Sun.COM result.gcd = tmp.gcd; 235*9663SMark.Logan@Sun.COM result.x = tmp.y; 236*9663SMark.Logan@Sun.COM result.y = tmp.x - (a/b) * tmp.y; 237*9663SMark.Logan@Sun.COM return result; 238*9663SMark.Logan@Sun.COM } 239*9663SMark.Logan@Sun.COM 240*9663SMark.Logan@Sun.COM /** 241*9663SMark.Logan@Sun.COM * This function computes a PedAlignment object that describes the 242*9663SMark.Logan@Sun.COM * intersection of two alignments. That is, a sector satisfies the 243*9663SMark.Logan@Sun.COM * new alignment object if and only if it satisfies both of the original 244*9663SMark.Logan@Sun.COM * ones. (See ped_alignment_is_aligned() for the meaning of "satisfies") 245*9663SMark.Logan@Sun.COM * 246*9663SMark.Logan@Sun.COM * Apart from the trivial cases (where one or both of the alignment objects 247*9663SMark.Logan@Sun.COM * constraints have no sectors that satisfy them), this is what we're trying to 248*9663SMark.Logan@Sun.COM * do: 249*9663SMark.Logan@Sun.COM * - two input constraints: \p a and \p b. 250*9663SMark.Logan@Sun.COM * - the new grain_size is going to be the lowest common multiple of 251*9663SMark.Logan@Sun.COM * \p a->grain_size and \p b->grain_size 252*9663SMark.Logan@Sun.COM * - hard part - solve the simultaneous equations, for offset, where offset, 253*9663SMark.Logan@Sun.COM * X and Y are variables. (Note: offset can be obtained from either X or Y, 254*9663SMark.Logan@Sun.COM * by substituing into either equation) 255*9663SMark.Logan@Sun.COM * 256*9663SMark.Logan@Sun.COM * \code 257*9663SMark.Logan@Sun.COM * offset = \p a->offset + X * \p a->grain_size (1) 258*9663SMark.Logan@Sun.COM * offset = \p b->offset + Y * \p b->grain_size (2) 259*9663SMark.Logan@Sun.COM * \endcode 260*9663SMark.Logan@Sun.COM * 261*9663SMark.Logan@Sun.COM * or, abbreviated: 262*9663SMark.Logan@Sun.COM * 263*9663SMark.Logan@Sun.COM * \code 264*9663SMark.Logan@Sun.COM * o = Ao + X*Ag (1) 265*9663SMark.Logan@Sun.COM * o = Bo + Y*Bg (2) 266*9663SMark.Logan@Sun.COM * 267*9663SMark.Logan@Sun.COM * => Ao + X*Ag = Bo + Y*Bg (1) = (2) 268*9663SMark.Logan@Sun.COM * X*Ag - Y*Bg = Bo - Ao (3) 269*9663SMark.Logan@Sun.COM * \endcode 270*9663SMark.Logan@Sun.COM * 271*9663SMark.Logan@Sun.COM * As it turns out, there only exists a solution if (Bo - Ao) is a multiple 272*9663SMark.Logan@Sun.COM * of the GCD of Ag and Bg. Reason: all linear combinations of Ag and Bg are 273*9663SMark.Logan@Sun.COM * multiples of the GCD. 274*9663SMark.Logan@Sun.COM * 275*9663SMark.Logan@Sun.COM * Proof: 276*9663SMark.Logan@Sun.COM * 277*9663SMark.Logan@Sun.COM * \code 278*9663SMark.Logan@Sun.COM * A * Ag + B * Bg 279*9663SMark.Logan@Sun.COM * = A * (\p a * gcd) + B * (\p b * gcd) 280*9663SMark.Logan@Sun.COM * = gcd * (A * \p a + B * \p b) 281*9663SMark.Logan@Sun.COM * \endcode 282*9663SMark.Logan@Sun.COM * 283*9663SMark.Logan@Sun.COM * gcd is a factor of the linear combination. QED 284*9663SMark.Logan@Sun.COM * 285*9663SMark.Logan@Sun.COM * Anyway, \p a * Ag + \p b * Bg = gcd can be solved (for \p a, \p b and gcd) 286*9663SMark.Logan@Sun.COM * with Euclid's extended algorithm. Then, we just multiply through by 287*9663SMark.Logan@Sun.COM * (Bo - Ao) / gcd to get (3). 288*9663SMark.Logan@Sun.COM * 289*9663SMark.Logan@Sun.COM * i.e. 290*9663SMark.Logan@Sun.COM * \code 291*9663SMark.Logan@Sun.COM * A * Ag + B * Bg = gcd 292*9663SMark.Logan@Sun.COM * A*(Bo-Ao)/gcd * Ag + B(Bo-Ao)/gcd * Bg = gcd * (Bo-Ao)/gcd 293*9663SMark.Logan@Sun.COM * X*Ag - Y*Bg = Bo - Ao (3) 294*9663SMark.Logan@Sun.COM * 295*9663SMark.Logan@Sun.COM * X = A*(Bo-Ao)/gcd 296*9663SMark.Logan@Sun.COM * Y = - B*(Bo-Ao)/gcd 297*9663SMark.Logan@Sun.COM * \endcode 298*9663SMark.Logan@Sun.COM * 299*9663SMark.Logan@Sun.COM * then: 300*9663SMark.Logan@Sun.COM * \code 301*9663SMark.Logan@Sun.COM * o = Ao + X*Ag (1) 302*9663SMark.Logan@Sun.COM * = Ao + A*(Bo-Ao)/gcd*Ag 303*9663SMark.Logan@Sun.COM * o = Bo + Y*Bg (2) 304*9663SMark.Logan@Sun.COM * = Bo - B*(Bo-Ao)/gcd*Ag 305*9663SMark.Logan@Sun.COM * \endcode 306*9663SMark.Logan@Sun.COM * 307*9663SMark.Logan@Sun.COM * Thanks go to Nathan Hurst (njh@hawthorn.csse.monash.edu.au) for figuring 308*9663SMark.Logan@Sun.COM * this algorithm out :-) 309*9663SMark.Logan@Sun.COM * 310*9663SMark.Logan@Sun.COM * \note Returned \c NULL is a valid PedAlignment object, and can be used 311*9663SMark.Logan@Sun.COM for ped_alignment_*() function. 312*9663SMark.Logan@Sun.COM * 313*9663SMark.Logan@Sun.COM * \return a PedAlignment on success, \c NULL on failure 314*9663SMark.Logan@Sun.COM */ 315*9663SMark.Logan@Sun.COM PedAlignment* 316*9663SMark.Logan@Sun.COM ped_alignment_intersect (const PedAlignment* a, const PedAlignment* b) 317*9663SMark.Logan@Sun.COM { 318*9663SMark.Logan@Sun.COM PedSector new_grain_size; 319*9663SMark.Logan@Sun.COM PedSector new_offset; 320*9663SMark.Logan@Sun.COM PedSector delta_on_gcd; 321*9663SMark.Logan@Sun.COM EuclidTriple gcd_factors; 322*9663SMark.Logan@Sun.COM 323*9663SMark.Logan@Sun.COM 324*9663SMark.Logan@Sun.COM if (!a || !b) 325*9663SMark.Logan@Sun.COM return NULL; 326*9663SMark.Logan@Sun.COM 327*9663SMark.Logan@Sun.COM /*PED_DEBUG (0x10, "intersecting alignments (%d,%d) and (%d,%d)", 328*9663SMark.Logan@Sun.COM a->offset, a->grain_size, b->offset, b->grain_size); 329*9663SMark.Logan@Sun.COM */ 330*9663SMark.Logan@Sun.COM 331*9663SMark.Logan@Sun.COM if (a->grain_size < b->grain_size) { 332*9663SMark.Logan@Sun.COM const PedAlignment* tmp; 333*9663SMark.Logan@Sun.COM tmp = a; a = b; b = tmp; 334*9663SMark.Logan@Sun.COM } 335*9663SMark.Logan@Sun.COM 336*9663SMark.Logan@Sun.COM /* weird/trivial case: where the solution space for "a" or "b" is 337*9663SMark.Logan@Sun.COM * either empty or contains exactly one solution 338*9663SMark.Logan@Sun.COM */ 339*9663SMark.Logan@Sun.COM if (a->grain_size == 0 && b->grain_size == 0) { 340*9663SMark.Logan@Sun.COM if (a->offset == b->offset) 341*9663SMark.Logan@Sun.COM return ped_alignment_duplicate (a); 342*9663SMark.Logan@Sun.COM else 343*9663SMark.Logan@Sun.COM return NULL; 344*9663SMark.Logan@Sun.COM } 345*9663SMark.Logan@Sun.COM 346*9663SMark.Logan@Sun.COM /* general case */ 347*9663SMark.Logan@Sun.COM gcd_factors = extended_euclid (a->grain_size, b->grain_size); 348*9663SMark.Logan@Sun.COM 349*9663SMark.Logan@Sun.COM delta_on_gcd = (b->offset - a->offset) / gcd_factors.gcd; 350*9663SMark.Logan@Sun.COM new_offset = a->offset + gcd_factors.x * delta_on_gcd * a->grain_size; 351*9663SMark.Logan@Sun.COM new_grain_size = a->grain_size * b->grain_size / gcd_factors.gcd; 352*9663SMark.Logan@Sun.COM 353*9663SMark.Logan@Sun.COM /* inconsistency => no solution */ 354*9663SMark.Logan@Sun.COM if (new_offset 355*9663SMark.Logan@Sun.COM != b->offset - gcd_factors.y * delta_on_gcd * b->grain_size) 356*9663SMark.Logan@Sun.COM return NULL; 357*9663SMark.Logan@Sun.COM 358*9663SMark.Logan@Sun.COM return ped_alignment_new (new_offset, new_grain_size); 359*9663SMark.Logan@Sun.COM } 360*9663SMark.Logan@Sun.COM 361*9663SMark.Logan@Sun.COM /* This function returns the sector closest to "sector" that lies inside 362*9663SMark.Logan@Sun.COM * geom and satisfies the alignment constraint. 363*9663SMark.Logan@Sun.COM */ 364*9663SMark.Logan@Sun.COM static PedSector 365*9663SMark.Logan@Sun.COM _closest_inside_geometry (const PedAlignment* align, const PedGeometry* geom, 366*9663SMark.Logan@Sun.COM PedSector sector) 367*9663SMark.Logan@Sun.COM { 368*9663SMark.Logan@Sun.COM PED_ASSERT (align != NULL, return -1); 369*9663SMark.Logan@Sun.COM 370*9663SMark.Logan@Sun.COM if (!align->grain_size) { 371*9663SMark.Logan@Sun.COM if (ped_alignment_is_aligned (align, geom, sector) 372*9663SMark.Logan@Sun.COM && (!geom || ped_geometry_test_sector_inside (geom, 373*9663SMark.Logan@Sun.COM sector))) 374*9663SMark.Logan@Sun.COM return sector; 375*9663SMark.Logan@Sun.COM else 376*9663SMark.Logan@Sun.COM return -1; 377*9663SMark.Logan@Sun.COM } 378*9663SMark.Logan@Sun.COM 379*9663SMark.Logan@Sun.COM if (sector < geom->start) 380*9663SMark.Logan@Sun.COM sector += ped_round_up_to (geom->start - sector, 381*9663SMark.Logan@Sun.COM align->grain_size); 382*9663SMark.Logan@Sun.COM if (sector > geom->end) 383*9663SMark.Logan@Sun.COM sector -= ped_round_up_to (sector - geom->end, 384*9663SMark.Logan@Sun.COM align->grain_size); 385*9663SMark.Logan@Sun.COM 386*9663SMark.Logan@Sun.COM if (!ped_geometry_test_sector_inside (geom, sector)) 387*9663SMark.Logan@Sun.COM return -1; 388*9663SMark.Logan@Sun.COM return sector; 389*9663SMark.Logan@Sun.COM } 390*9663SMark.Logan@Sun.COM 391*9663SMark.Logan@Sun.COM /** 392*9663SMark.Logan@Sun.COM * This function returns the closest sector to \p sector that lies inside 393*9663SMark.Logan@Sun.COM * \p geom that satisfies the given alignment constraint \p align. It prefers 394*9663SMark.Logan@Sun.COM * sectors that are beyond \p sector (are not smaller than \p sector), 395*9663SMark.Logan@Sun.COM * but does not guarantee that this. 396*9663SMark.Logan@Sun.COM * 397*9663SMark.Logan@Sun.COM * \return a PedSector on success, \c -1 on failure 398*9663SMark.Logan@Sun.COM */ 399*9663SMark.Logan@Sun.COM PedSector 400*9663SMark.Logan@Sun.COM ped_alignment_align_up (const PedAlignment* align, const PedGeometry* geom, 401*9663SMark.Logan@Sun.COM PedSector sector) 402*9663SMark.Logan@Sun.COM { 403*9663SMark.Logan@Sun.COM PedSector result; 404*9663SMark.Logan@Sun.COM 405*9663SMark.Logan@Sun.COM PED_ASSERT (align != NULL, return -1); 406*9663SMark.Logan@Sun.COM 407*9663SMark.Logan@Sun.COM if (!align->grain_size) 408*9663SMark.Logan@Sun.COM result = align->offset; 409*9663SMark.Logan@Sun.COM else 410*9663SMark.Logan@Sun.COM result = ped_round_up_to (sector - align->offset, 411*9663SMark.Logan@Sun.COM align->grain_size) 412*9663SMark.Logan@Sun.COM + align->offset; 413*9663SMark.Logan@Sun.COM 414*9663SMark.Logan@Sun.COM if (geom) 415*9663SMark.Logan@Sun.COM result = _closest_inside_geometry (align, geom, result); 416*9663SMark.Logan@Sun.COM return result; 417*9663SMark.Logan@Sun.COM } 418*9663SMark.Logan@Sun.COM 419*9663SMark.Logan@Sun.COM /** 420*9663SMark.Logan@Sun.COM * This function returns the closest sector to \p sector that lies inside 421*9663SMark.Logan@Sun.COM * \p geom that satisfies the given alignment constraint \p align. It prefers 422*9663SMark.Logan@Sun.COM * sectors that are before \p sector (are not larger than \p sector), 423*9663SMark.Logan@Sun.COM * but does not guarantee that this. 424*9663SMark.Logan@Sun.COM * 425*9663SMark.Logan@Sun.COM * \return a PedSector on success, \c -1 on failure 426*9663SMark.Logan@Sun.COM */ 427*9663SMark.Logan@Sun.COM PedSector 428*9663SMark.Logan@Sun.COM ped_alignment_align_down (const PedAlignment* align, const PedGeometry* geom, 429*9663SMark.Logan@Sun.COM PedSector sector) 430*9663SMark.Logan@Sun.COM { 431*9663SMark.Logan@Sun.COM PedSector result; 432*9663SMark.Logan@Sun.COM 433*9663SMark.Logan@Sun.COM PED_ASSERT (align != NULL, return -1); 434*9663SMark.Logan@Sun.COM 435*9663SMark.Logan@Sun.COM if (!align->grain_size) 436*9663SMark.Logan@Sun.COM result = align->offset; 437*9663SMark.Logan@Sun.COM else 438*9663SMark.Logan@Sun.COM result = ped_round_down_to (sector - align->offset, 439*9663SMark.Logan@Sun.COM align->grain_size) 440*9663SMark.Logan@Sun.COM + align->offset; 441*9663SMark.Logan@Sun.COM 442*9663SMark.Logan@Sun.COM if (geom) 443*9663SMark.Logan@Sun.COM result = _closest_inside_geometry (align, geom, result); 444*9663SMark.Logan@Sun.COM return result; 445*9663SMark.Logan@Sun.COM } 446*9663SMark.Logan@Sun.COM 447*9663SMark.Logan@Sun.COM /* Returns either a or b, depending on which is closest to "sector". */ 448*9663SMark.Logan@Sun.COM static PedSector 449*9663SMark.Logan@Sun.COM closest (PedSector sector, PedSector a, PedSector b) 450*9663SMark.Logan@Sun.COM { 451*9663SMark.Logan@Sun.COM if (a == -1) 452*9663SMark.Logan@Sun.COM return b; 453*9663SMark.Logan@Sun.COM if (b == -1) 454*9663SMark.Logan@Sun.COM return a; 455*9663SMark.Logan@Sun.COM 456*9663SMark.Logan@Sun.COM if (abs (sector - a) < abs (sector - b)) 457*9663SMark.Logan@Sun.COM return a; 458*9663SMark.Logan@Sun.COM else 459*9663SMark.Logan@Sun.COM return b; 460*9663SMark.Logan@Sun.COM } 461*9663SMark.Logan@Sun.COM 462*9663SMark.Logan@Sun.COM /** 463*9663SMark.Logan@Sun.COM * This function returns the sector that is closest to \p sector, 464*9663SMark.Logan@Sun.COM * satisfies the \p align constraint and lies inside \p geom. 465*9663SMark.Logan@Sun.COM * 466*9663SMark.Logan@Sun.COM * \return a PedSector on success, \c -1 on failure 467*9663SMark.Logan@Sun.COM */ 468*9663SMark.Logan@Sun.COM PedSector 469*9663SMark.Logan@Sun.COM ped_alignment_align_nearest (const PedAlignment* align, const PedGeometry* geom, 470*9663SMark.Logan@Sun.COM PedSector sector) 471*9663SMark.Logan@Sun.COM { 472*9663SMark.Logan@Sun.COM PED_ASSERT (align != NULL, return -1); 473*9663SMark.Logan@Sun.COM 474*9663SMark.Logan@Sun.COM return closest (sector, ped_alignment_align_up (align, geom, sector), 475*9663SMark.Logan@Sun.COM ped_alignment_align_down (align, geom, sector)); 476*9663SMark.Logan@Sun.COM } 477*9663SMark.Logan@Sun.COM 478*9663SMark.Logan@Sun.COM /** 479*9663SMark.Logan@Sun.COM * This function returns 1 if \p sector satisfies the alignment 480*9663SMark.Logan@Sun.COM * constraint \p align and lies inside \p geom. 481*9663SMark.Logan@Sun.COM * 482*9663SMark.Logan@Sun.COM * \return \c 1 on success, \c 0 on failure 483*9663SMark.Logan@Sun.COM */ 484*9663SMark.Logan@Sun.COM int 485*9663SMark.Logan@Sun.COM ped_alignment_is_aligned (const PedAlignment* align, const PedGeometry* geom, 486*9663SMark.Logan@Sun.COM PedSector sector) 487*9663SMark.Logan@Sun.COM { 488*9663SMark.Logan@Sun.COM if (!align) 489*9663SMark.Logan@Sun.COM return 0; 490*9663SMark.Logan@Sun.COM 491*9663SMark.Logan@Sun.COM if (geom && !ped_geometry_test_sector_inside (geom, sector)) 492*9663SMark.Logan@Sun.COM return 0; 493*9663SMark.Logan@Sun.COM 494*9663SMark.Logan@Sun.COM if (align->grain_size) 495*9663SMark.Logan@Sun.COM return (sector - align->offset) % align->grain_size == 0; 496*9663SMark.Logan@Sun.COM else 497*9663SMark.Logan@Sun.COM return sector == align->offset; 498*9663SMark.Logan@Sun.COM } 499*9663SMark.Logan@Sun.COM 500*9663SMark.Logan@Sun.COM /** 501*9663SMark.Logan@Sun.COM * @} 502*9663SMark.Logan@Sun.COM */ 503*9663SMark.Logan@Sun.COM 504