libparted/cs/natmath.c

   1 /*
   2     libparted - a library for manipulating disk partitions
   3     Copyright (C) 2000, 2007-2012 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 static 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 /* Rounds a number up to the closest number that is a multiple of
  78  * grain_size.
  79  */
  80 PedSector
  81 ped_round_up_to (PedSector sector, PedSector grain_size)
  82 {
  83         if (sector % grain_size)
  84                 return ped_round_down_to (sector, grain_size) + grain_size;
  85         else
  86                 return sector;
  87 }
  88
  89 /* Rounds a number to the closest number that is a multiple of grain_size. */
  90 PedSector
  91 ped_round_to_nearest (PedSector sector, PedSector grain_size)
  92 {
  93         if (sector % grain_size > grain_size/2)
  94                 return ped_round_up_to (sector, grain_size);
  95         else
  96                 return ped_round_down_to (sector, grain_size);
  97 }
  98
  99 /* This function returns the largest number that divides both a and b.
 100  * It uses the ancient Euclidean algorithm.
 101  */
 102 PedSector
 103 ped_greatest_common_divisor (PedSector a, PedSector b)
 104 {
 105         PED_ASSERT (a >= 0);
 106         PED_ASSERT (b >= 0);
 107
 108         /* Put the arguments in the "right" format.  (Recursive calls made by
 109          * this function are always in the right format.)
 110          */
 111         if (b > a)
 112                 return ped_greatest_common_divisor (b, a);
 113
 114         if (b)
 115                 return ped_greatest_common_divisor (b, a % b);
 116         else
 117                 return a;
 118 }
 119
 120 /**
 121  * Initialize a preallocated piece of memory for an alignment object
 122  * (used by PedConstraint).
 123  *
 124  * The object will represent all sectors \e s for which the equation
 125  * <tt>s = offset + X * grain_size</tt> holds.
 126  */
 127 int
 128 ped_alignment_init (PedAlignment* align, PedSector offset, PedSector grain_size)
 129 {
 130         PED_ASSERT (align != NULL);
 131
 132         if (grain_size < 0)
 133                 return 0;
 134
 135         if (grain_size)
 136                 align->offset = abs_mod (offset, grain_size);
 137         else
 138                 align->offset = offset;
 139         align->grain_size = grain_size;
 140
 141         return 1;
 142 }
 143
 144 /**
 145  * Return an alignment object (used by PedConstraint), representing all
 146  * PedSector's that are of the form <tt>offset + X * grain_size</tt>.
 147  */
 148 PedAlignment*
 149 ped_alignment_new (PedSector offset, PedSector grain_size)
 150 {
 151         PedAlignment*   align;
 152
 153         align = (PedAlignment*) ped_malloc (sizeof (PedAlignment));
 154         if (!align)
 155                 goto error;
 156
 157         if (!ped_alignment_init (align, offset, grain_size))
 158                 goto error_free_align;
 159
 160         return align;
 161
 162 error_free_align:
 163         free (align);
 164 error:
 165         return NULL;
 166 }
 167
 168 /**
 169  * Free up memory associated with \p align.
 170  */
 171 void
 172 ped_alignment_destroy (PedAlignment* align)
 173 {
 174         free (align);
 175 }
 176
 177 /**
 178  * Return a duplicate of \p align.
 179  */
 180 PedAlignment*
 181 ped_alignment_duplicate (const PedAlignment* align)
 182 {
 183         if (!align)
 184                 return NULL;
 185         return ped_alignment_new (align->offset, align->grain_size);
 186 }
 187
 188 /* the extended Euclid algorithm.
 189  *
 190  * input:
 191  *      a and b, a > b
 192  *
 193  * output:
 194  *      gcd, x and y, such that:
 195  *
 196  *      gcd = greatest common divisor of a and b
 197  *      gcd = x*a + y*b
 198  */
 199 static EuclidTriple _GL_ATTRIBUTE_PURE
 200 extended_euclid (int a, int b)
 201 {
 202         EuclidTriple    result;
 203         EuclidTriple    tmp;
 204
 205         if (b == 0) {
 206                 result.gcd = a;
 207                 result.x = 1;
 208                 result.y = 0;
 209                 return result;
 210         }
 211
 212         tmp = extended_euclid (b, a % b);
 213         result.gcd = tmp.gcd;
 214         result.x = tmp.y;
 215         result.y = tmp.x - (a/b) * tmp.y;
 216         return result;
 217 }
 218
 219 /**
 220  * This function computes a PedAlignment object that describes the
 221  * intersection of two alignments.  That is, a sector satisfies the
 222  * new alignment object if and only if it satisfies both of the original
 223  * ones.  (See ped_alignment_is_aligned() for the meaning of "satisfies")
 224  *
 225  * Apart from the trivial cases (where one or both of the alignment objects
 226  * constraints have no sectors that satisfy them), this is what we're trying to
 227  * do:
 228  *  - two input constraints: \p a and \p b.
 229  *  - the new grain_size is going to be the lowest common multiple of
 230  *  \p a->grain_size and \p b->grain_size
 231  *  - hard part - solve the simultaneous equations, for offset, where offset,
 232  *  X and Y are variables.  (Note: offset can be obtained from either X or Y,
 233  *  by substituing into either equation)
 234  *
 235  * \code
 236  *      offset = \p a->offset + X * \p a->grain_size            (1)
 237  *      offset = \p b->offset + Y * \p b->grain_size            (2)
 238  * \endcode
 239  *
 240  * or, abbreviated:
 241  *
 242  * \code
 243  *      o = Ao + X*Ag           (1)
 244  *      o = Bo + Y*Bg           (2)
 245  *
 246  *  =>  Ao + X*Ag    = Bo + Y*Bg     (1) = (2)
 247  *      X*Ag - Y*Bg  = Bo - Ao  (3)
 248  * \endcode
 249  *
 250  * As it turns out, there only exists a solution if (Bo - Ao) is a multiple
 251  * of the GCD of Ag and Bg.  Reason: all linear combinations of Ag and Bg are
 252  * multiples of the GCD.
 253  *
 254  * Proof:
 255  *
 256  * \code
 257  *      A * Ag + B * Bg
 258  *      = A * (\p a * gcd) + B * (\p b * gcd)
 259  *      = gcd * (A * \p a + B * \p b)
 260  * \endcode
 261  *
 262  * gcd is a factor of the linear combination.  QED
 263  *
 264  * Anyway, \p a * Ag + \p b * Bg = gcd can be solved (for \p a, \p b and gcd)
 265  * with Euclid's extended algorithm.  Then, we just multiply through by
 266  * (Bo - Ao) / gcd to get (3).
 267  *
 268  * i.e.
 269  * \code
 270  *      A * Ag + B * Bg                         = gcd
 271  *      A*(Bo-Ao)/gcd * Ag + B(Bo-Ao)/gcd * Bg  = gcd * (Bo-Ao)/gcd
 272  *      X*Ag - Y*Bg                             = Bo - Ao               (3)
 273  *
 274  *      X = A*(Bo-Ao)/gcd
 275  *      Y = - B*(Bo-Ao)/gcd
 276  * \endcode
 277  *
 278  * then:
 279  * \code
 280  *      o = Ao + X*Ag                   (1)
 281  *        = Ao + A*(Bo-Ao)/gcd*Ag
 282  *      o = Bo + Y*Bg                   (2)
 283  *        = Bo - B*(Bo-Ao)/gcd*Ag
 284  * \endcode
 285  *
 286  * Thanks go to Nathan Hurst (njh@hawthorn.csse.monash.edu.au) for figuring
 287  * this algorithm out :-)
 288  *
 289  * \note Returned \c NULL is a valid PedAlignment object, and can be used
 290         for ped_alignment_*() function.
 291  *
 292  * \return a PedAlignment on success, \c NULL on failure
 293  */
 294 PedAlignment*
 295 ped_alignment_intersect (const PedAlignment* a, const PedAlignment* b)
 296 {
 297         PedSector       new_grain_size;
 298         PedSector       new_offset;
 299         PedSector       delta_on_gcd;
 300         EuclidTriple    gcd_factors;
 301
 302
 303         if (!a || !b)
 304                 return NULL;
 305
 306         /*PED_DEBUG (0x10, "intersecting alignments (%d,%d) and (%d,%d)",
 307                         a->offset, a->grain_size, b->offset, b->grain_size);
 308         */
 309
 310         if (a->grain_size < b->grain_size) {
 311                 const PedAlignment*     tmp;
 312                 tmp = a; a = b; b = tmp;
 313         }
 314
 315         /* weird/trivial case: where the solution space for "a" or "b" is
 316          * either empty or contains exactly one solution
 317          */
 318         if (a->grain_size == 0 && b->grain_size == 0) {
 319                 if (a->offset == b->offset)
 320                         return ped_alignment_duplicate (a);
 321                 else
 322                         return NULL;
 323         }
 324
 325         /* general case */
 326         gcd_factors = extended_euclid (a->grain_size, b->grain_size);
 327
 328         delta_on_gcd = (b->offset - a->offset) / gcd_factors.gcd;
 329         new_offset = a->offset + gcd_factors.x * delta_on_gcd * a->grain_size;
 330         new_grain_size = a->grain_size * b->grain_size / gcd_factors.gcd;
 331
 332         /* inconsistency => no solution */
 333         if (new_offset
 334             != b->offset - gcd_factors.y * delta_on_gcd * b->grain_size)
 335                 return NULL;
 336
 337         return ped_alignment_new (new_offset, new_grain_size);
 338 }
 339
 340 /* This function returns the sector closest to "sector" that lies inside
 341  * geom and satisfies the alignment constraint.
 342  */
 343 static PedSector _GL_ATTRIBUTE_PURE
 344 _closest_inside_geometry (const PedAlignment* align, const PedGeometry* geom,
 345                           PedSector sector)
 346 {
 347         PED_ASSERT (align != NULL);
 348
 349         if (!align->grain_size) {
 350                 if (ped_alignment_is_aligned (align, geom, sector)
 351                     && (!geom || ped_geometry_test_sector_inside (geom,
 352                                                                   sector)))
 353                         return sector;
 354                 else
 355                         return -1;
 356         }
 357
 358         if (sector < geom->start)
 359                 sector += ped_round_up_to (geom->start - sector,
 360                                            align->grain_size);
 361         if (sector > geom->end)
 362                 sector -= ped_round_up_to (sector - geom->end,
 363                                            align->grain_size);
 364
 365         if (!ped_geometry_test_sector_inside (geom, sector))
 366                 return -1;
 367         return sector;
 368 }
 369
 370 /**
 371  * This function returns the closest sector to \p sector that lies inside
 372  * \p geom that satisfies the given alignment constraint \p align.  It prefers
 373  * sectors that are beyond \p sector (are not smaller than \p sector),
 374  * but does not guarantee that this.
 375  *
 376  * \return a PedSector on success, \c -1 on failure
 377  */
 378 PedSector
 379 ped_alignment_align_up (const PedAlignment* align, const PedGeometry* geom,
 380                         PedSector sector)
 381 {
 382         PedSector       result;
 383
 384         PED_ASSERT (align != NULL);
 385
 386         if (!align->grain_size)
 387                 result = align->offset;
 388         else
 389                 result = ped_round_up_to (sector - align->offset,
 390                                           align->grain_size)
 391                          + align->offset;
 392
 393         if (geom)
 394                 result = _closest_inside_geometry (align, geom, result);
 395         return result;
 396 }
 397
 398 /**
 399  * This function returns the closest sector to \p sector that lies inside
 400  * \p geom that satisfies the given alignment constraint \p align.  It prefers
 401  * sectors that are before \p sector (are not larger than \p sector),
 402  * but does not guarantee that this.
 403  *
 404  * \return a PedSector on success, \c -1 on failure
 405  */
 406 PedSector
 407 ped_alignment_align_down (const PedAlignment* align, const PedGeometry* geom,
 408                           PedSector sector)
 409 {
 410         PedSector       result;
 411
 412         PED_ASSERT (align != NULL);
 413
 414         if (!align->grain_size)
 415                 result = align->offset;
 416         else
 417                 result = ped_round_down_to (sector - align->offset,
 418                                             align->grain_size)
 419                          + align->offset;
 420
 421         if (geom)
 422                 result = _closest_inside_geometry (align, geom, result);
 423         return result;
 424 }
 425
 426 /* Returns either a or b, depending on which is closest to "sector". */
 427 static PedSector
 428 closest (PedSector sector, PedSector a, PedSector b)
 429 {
 430         if (a == -1)
 431                 return b;
 432         if (b == -1)
 433                 return a;
 434
 435         if (abs (sector - a) < abs (sector - b))
 436                 return a;
 437         else
 438                 return b;
 439 }
 440
 441 /**
 442  * This function returns the sector that is closest to \p sector,
 443  * satisfies the \p align constraint and lies inside \p geom.
 444  *
 445  * \return a PedSector on success, \c -1 on failure
 446  */
 447 PedSector
 448 ped_alignment_align_nearest (const PedAlignment* align, const PedGeometry* geom,
 449                              PedSector sector)
 450 {
 451         PED_ASSERT (align != NULL);
 452
 453         return closest (sector, ped_alignment_align_up (align, geom, sector),
 454                         ped_alignment_align_down (align, geom, sector));
 455 }
 456
 457 /**
 458  * This function returns 1 if \p sector satisfies the alignment
 459  * constraint \p align and lies inside \p geom.
 460  *
 461  * \return \c 1 on success, \c 0 on failure
 462  */
 463 int
 464 ped_alignment_is_aligned (const PedAlignment* align, const PedGeometry* geom,
 465                           PedSector sector)
 466 {
 467         if (!align)
 468                 return 0;
 469
 470         if (geom && !ped_geometry_test_sector_inside (geom, sector))
 471                 return 0;
 472
 473         if (align->grain_size)
 474                 return (sector - align->offset) % align->grain_size == 0;
 475         else
 476                 return sector == align->offset;
 477 }
 478
 479 /**
 480  * @}
 481  */