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