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