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