1/*
2 * Copyright (c) 1997-2003 by The XFree86 Project, Inc.
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a
5 * copy of this software and associated documentation files (the "Software"),
6 * to deal in the Software without restriction, including without limitation
7 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8 * and/or sell copies of the Software, and to permit persons to whom the
9 * Software is furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice shall be included in
12 * all copies or substantial portions of the Software.
13 *
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
17 * THE COPYRIGHT HOLDER(S) OR AUTHOR(S) BE LIABLE FOR ANY CLAIM, DAMAGES OR
18 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
19 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
20 * OTHER DEALINGS IN THE SOFTWARE.
21 *
22 * Except as contained in this notice, the name of the copyright holder(s)
23 * and author(s) shall not be used in advertising or otherwise to promote
24 * the sale, use or other dealings in this Software without prior written
25 * authorization from the copyright holder(s) and author(s).
26 */
27
28/*
29 * LCM() and scanLineWidth() are:
30 *
31 * Copyright 1997 through 2004 by Marc Aurele La France (TSI @ UQV), tsi@xfree86.org
32 *
33 * Permission to use, copy, modify, distribute, and sell this software and its
34 * documentation for any purpose is hereby granted without fee, provided that
35 * the above copyright notice appear in all copies and that both that copyright
36 * notice and this permission notice appear in supporting documentation, and
37 * that the name of Marc Aurele La France not be used in advertising or
38 * publicity pertaining to distribution of the software without specific,
39 * written prior permission.  Marc Aurele La France makes no representations
40 * about the suitability of this software for any purpose.  It is provided
41 * "as-is" without express or implied warranty.
42 *
43 * MARC AURELE LA FRANCE DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
44 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS.  IN NO
45 * EVENT SHALL MARC AURELE LA FRANCE BE LIABLE FOR ANY SPECIAL, INDIRECT OR
46 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
47 * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
48 * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
49 * PERFORMANCE OF THIS SOFTWARE.
50 *
51 * Copyright 1990,91,92,93 by Thomas Roell, Germany.
52 * Copyright 1991,92,93    by SGCS (Snitily Graphics Consulting Services), USA.
53 *
54 * Permission to use, copy, modify, distribute, and sell this software
55 * and its documentation for any purpose is hereby granted without fee,
56 * provided that the above copyright notice appear in all copies and
57 * that both that copyright notice and this  permission notice appear
58 * in supporting documentation, and that the name of Thomas Roell nor
59 * SGCS be used in advertising or publicity pertaining to distribution
60 * of the software without specific, written prior permission.
61 * Thomas Roell nor SGCS makes no representations about the suitability
62 * of this software for any purpose. It is provided "as is" without
63 * express or implied warranty.
64 *
65 * THOMAS ROELL AND SGCS DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS
66 * SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
67 * FITNESS, IN NO EVENT SHALL THOMAS ROELL OR SGCS BE LIABLE FOR ANY
68 * SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER
69 * RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF
70 * CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
71 * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
72 */
73
74/*
75 * Authors: Dirk Hohndel <hohndel@XFree86.Org>
76 *          David Dawes <dawes@XFree86.Org>
77 *          Marc La France <tsi@XFree86.Org>
78 *          ... and others
79 *
80 * This file includes helper functions for mode related things.
81 */
82
83#ifdef HAVE_XORG_CONFIG_H
84#include <xorg-config.h>
85#endif
86
87#include <X11/X.h>
88#include "xf86Modes.h"
89#include "os.h"
90#include "servermd.h"
91#include "globals.h"
92#include "xf86.h"
93#include "xf86Priv.h"
94#include "edid.h"
95
96static void
97printModeRejectMessage(int index, DisplayModePtr p, int status)
98{
99    char *type;
100
101    if (p->type & M_T_BUILTIN)
102	type = "built-in ";
103    else if (p->type & M_T_DEFAULT)
104	type = "default ";
105    else if (p->type & M_T_DRIVER)
106	type = "driver ";
107    else
108	type = "";
109
110    xf86DrvMsg(index, X_INFO, "Not using %smode \"%s\" (%s)\n", type, p->name,
111	       xf86ModeStatusToString(status));
112}
113
114/*
115 * xf86GetNearestClock --
116 *	Find closest clock to given frequency (in kHz).  This assumes the
117 *	number of clocks is greater than zero.
118 */
119int
120xf86GetNearestClock(ScrnInfoPtr scrp, int freq, Bool allowDiv2,
121    int DivFactor, int MulFactor, int *divider)
122{
123    int nearestClock = 0, nearestDiv = 1;
124    int minimumGap = abs(freq - scrp->clock[0]);
125    int i, j, k, gap;
126
127    if (allowDiv2)
128	k = 2;
129    else
130	k = 1;
131
132    /* Must set this here in case the best match is scrp->clock[0] */
133    if (divider != NULL)
134	*divider = 0;
135
136    for (i = 0;  i < scrp->numClocks;  i++) {
137	for (j = 1; j <= k; j++) {
138	    gap = abs((freq * j) - ((scrp->clock[i] * DivFactor) / MulFactor));
139	    if ((gap < minimumGap) ||
140		((gap == minimumGap) && (j < nearestDiv))) {
141		minimumGap = gap;
142		nearestClock = i;
143		nearestDiv = j;
144		if (divider != NULL)
145		    *divider = (j - 1) * V_CLKDIV2;
146	    }
147	}
148    }
149    return nearestClock;
150}
151
152/*
153 * xf86ModeStatusToString
154 *
155 * Convert a ModeStatus value to a printable message
156 */
157
158const char *
159xf86ModeStatusToString(ModeStatus status)
160{
161    switch (status) {
162    case MODE_OK:
163	return "Mode OK";
164    case MODE_HSYNC:
165	return "hsync out of range";
166    case MODE_VSYNC:
167	return "vrefresh out of range";
168    case MODE_H_ILLEGAL:
169	return "illegal horizontal timings";
170    case MODE_V_ILLEGAL:
171	return "illegal vertical timings";
172    case MODE_BAD_WIDTH:
173	return "width requires unsupported line pitch";
174    case MODE_NOMODE:
175	return "no mode of this name";
176    case MODE_NO_INTERLACE:
177	return "interlace mode not supported";
178    case MODE_NO_DBLESCAN:
179	return "doublescan mode not supported";
180    case MODE_NO_VSCAN:
181	return "multiscan mode not supported";
182    case MODE_MEM:
183	return "insufficient memory for mode";
184    case MODE_VIRTUAL_X:
185	return "width too large for virtual size";
186    case MODE_VIRTUAL_Y:
187	return "height too large for virtual size";
188    case MODE_MEM_VIRT:
189	return "insufficient memory given virtual size";
190    case MODE_NOCLOCK:
191	return "no clock available for mode";
192    case MODE_CLOCK_HIGH:
193	return "mode clock too high";
194    case MODE_CLOCK_LOW:
195	return "mode clock too low";
196    case MODE_CLOCK_RANGE:
197	return "bad mode clock/interlace/doublescan";
198    case MODE_BAD_HVALUE:
199	return "horizontal timing out of range";
200    case MODE_BAD_VVALUE:
201	return "vertical timing out of range";
202    case MODE_BAD_VSCAN:
203	return "VScan value out of range";
204    case MODE_HSYNC_NARROW:
205	return "horizontal sync too narrow";
206    case MODE_HSYNC_WIDE:
207	return "horizontal sync too wide";
208    case MODE_HBLANK_NARROW:
209	return "horizontal blanking too narrow";
210    case MODE_HBLANK_WIDE:
211	return "horizontal blanking too wide";
212    case MODE_VSYNC_NARROW:
213	return "vertical sync too narrow";
214    case MODE_VSYNC_WIDE:
215	return "vertical sync too wide";
216    case MODE_VBLANK_NARROW:
217	return "vertical blanking too narrow";
218    case MODE_VBLANK_WIDE:
219	return "vertical blanking too wide";
220    case MODE_PANEL:
221	return "exceeds panel dimensions";
222    case MODE_INTERLACE_WIDTH:
223	return "width too large for interlaced mode";
224    case MODE_ONE_WIDTH:
225        return "all modes must have the same width";
226    case MODE_ONE_HEIGHT:
227        return "all modes must have the same height";
228    case MODE_ONE_SIZE:
229        return "all modes must have the same resolution";
230    case MODE_NO_REDUCED:
231        return "monitor doesn't support reduced blanking";
232    case MODE_BANDWIDTH:
233	return "mode requires too much memory bandwidth";
234    case MODE_BAD:
235	return "unknown reason";
236    case MODE_ERROR:
237	return "internal error";
238    default:
239	return "unknown";
240    }
241}
242
243/*
244 * xf86ShowClockRanges() -- Print the clock ranges allowed
245 * and the clock values scaled by ClockMulFactor and ClockDivFactor
246 */
247void
248xf86ShowClockRanges(ScrnInfoPtr scrp, ClockRangePtr clockRanges)
249{
250    ClockRangePtr cp;
251    int MulFactor = 1;
252    int DivFactor = 1;
253    int i, j;
254    int scaledClock;
255
256    for (cp = clockRanges; cp != NULL; cp = cp->next) {
257	DivFactor = max(1, cp->ClockDivFactor);
258	MulFactor = max(1, cp->ClockMulFactor);
259	if (scrp->progClock) {
260	    if (cp->minClock) {
261		if (cp->maxClock) {
262		    xf86DrvMsg(scrp->scrnIndex, X_INFO,
263			"Clock range: %6.2f to %6.2f MHz\n",
264			(double)cp->minClock / 1000.0,
265			(double)cp->maxClock / 1000.0);
266		} else {
267		    xf86DrvMsg(scrp->scrnIndex, X_INFO,
268			"Minimum clock: %6.2f MHz\n",
269			(double)cp->minClock / 1000.0);
270		}
271	    } else {
272		if (cp->maxClock) {
273		    xf86DrvMsg(scrp->scrnIndex, X_INFO,
274			"Maximum clock: %6.2f MHz\n",
275			(double)cp->maxClock / 1000.0);
276		}
277	    }
278	} else if (DivFactor > 1 || MulFactor > 1) {
279	    j = 0;
280	    for (i = 0; i < scrp->numClocks; i++) {
281		scaledClock = (scrp->clock[i] * DivFactor) / MulFactor;
282		if (scaledClock >= cp->minClock && scaledClock <= cp->maxClock) {
283		    if ((j % 8) == 0) {
284			if (j > 0)
285			    xf86ErrorF("\n");
286			xf86DrvMsg(scrp->scrnIndex, X_INFO, "scaled clocks:");
287		    }
288		    xf86ErrorF(" %6.2f", (double)scaledClock / 1000.0);
289		    j++;
290		}
291	    }
292	    xf86ErrorF("\n");
293	}
294    }
295}
296
297static Bool
298modeInClockRange(ClockRangePtr cp, DisplayModePtr p)
299{
300    return ((p->Clock >= cp->minClock) &&
301	    (p->Clock <= cp->maxClock) &&
302	    (cp->interlaceAllowed || !(p->Flags & V_INTERLACE)) &&
303	    (cp->doubleScanAllowed ||
304	     ((p->VScan <= 1) && !(p->Flags & V_DBLSCAN))));
305}
306
307/*
308 * xf86FindClockRangeForMode()    [... like the name says ...]
309 */
310static ClockRangePtr
311xf86FindClockRangeForMode(ClockRangePtr clockRanges, DisplayModePtr p)
312{
313    ClockRangePtr cp;
314
315    for (cp = clockRanges; ; cp = cp->next)
316	if (!cp || modeInClockRange(cp, p))
317	    return cp;
318}
319
320
321/*
322 * xf86HandleBuiltinMode() - handles built-in modes
323 */
324static ModeStatus
325xf86HandleBuiltinMode(ScrnInfoPtr scrp,
326		      DisplayModePtr p,
327		      DisplayModePtr modep,
328		      ClockRangePtr clockRanges,
329		      Bool allowDiv2)
330{
331    ClockRangePtr cp;
332    int extraFlags = 0;
333    int MulFactor = 1;
334    int DivFactor = 1;
335    int clockIndex;
336
337    /* Reject previously rejected modes */
338    if (p->status != MODE_OK)
339	return p->status;
340
341    /* Reject previously considered modes */
342    if (p->prev)
343        return MODE_NOMODE;
344
345    if ((p->type & M_T_CLOCK_C) == M_T_CLOCK_C) {
346	/* Check clock is in range */
347	cp = xf86FindClockRangeForMode(clockRanges, p);
348	if (cp == NULL){
349	    modep->type = p->type;
350	    p->status = MODE_CLOCK_RANGE;
351	    return MODE_CLOCK_RANGE;
352	}
353	DivFactor = cp->ClockDivFactor;
354	MulFactor = cp->ClockMulFactor;
355	if (!scrp->progClock) {
356	    clockIndex = xf86GetNearestClock(scrp, p->Clock, allowDiv2,
357					     cp->ClockDivFactor,
358					     cp->ClockMulFactor, &extraFlags);
359	    modep->Clock = (scrp->clock[clockIndex] * DivFactor)
360		/ MulFactor;
361	    modep->ClockIndex	= clockIndex;
362	    modep->SynthClock	= scrp->clock[clockIndex];
363	    if (extraFlags & V_CLKDIV2) {
364		modep->Clock /= 2;
365		modep->SynthClock /= 2;
366	    }
367	} else {
368	    modep->Clock = p->Clock;
369	    modep->ClockIndex = -1;
370	    modep->SynthClock = (modep->Clock * MulFactor)
371		/ DivFactor;
372	}
373	modep->PrivFlags = cp->PrivFlags;
374    } else {
375	if(!scrp->progClock) {
376            modep->Clock = p->Clock;
377	    modep->ClockIndex = p->ClockIndex;
378	    modep->SynthClock = p->SynthClock;
379	} else {
380	    modep->Clock = p->Clock;
381	    modep->ClockIndex = -1;
382	    modep->SynthClock = p->SynthClock;
383	}
384	modep->PrivFlags = p->PrivFlags;
385    }
386    modep->type            = p->type;
387    modep->HDisplay        = p->HDisplay;
388    modep->HSyncStart      = p->HSyncStart;
389    modep->HSyncEnd        = p->HSyncEnd;
390    modep->HTotal          = p->HTotal;
391    modep->HSkew           = p->HSkew;
392    modep->VDisplay        = p->VDisplay;
393    modep->VSyncStart      = p->VSyncStart;
394    modep->VSyncEnd        = p->VSyncEnd;
395    modep->VTotal          = p->VTotal;
396    modep->VScan           = p->VScan;
397    modep->Flags           = p->Flags | extraFlags;
398    modep->CrtcHDisplay    = p->CrtcHDisplay;
399    modep->CrtcHBlankStart = p->CrtcHBlankStart;
400    modep->CrtcHSyncStart  = p->CrtcHSyncStart;
401    modep->CrtcHSyncEnd    = p->CrtcHSyncEnd;
402    modep->CrtcHBlankEnd   = p->CrtcHBlankEnd;
403    modep->CrtcHTotal      = p->CrtcHTotal;
404    modep->CrtcHSkew       = p->CrtcHSkew;
405    modep->CrtcVDisplay    = p->CrtcVDisplay;
406    modep->CrtcVBlankStart = p->CrtcVBlankStart;
407    modep->CrtcVSyncStart  = p->CrtcVSyncStart;
408    modep->CrtcVSyncEnd    = p->CrtcVSyncEnd;
409    modep->CrtcVBlankEnd   = p->CrtcVBlankEnd;
410    modep->CrtcVTotal      = p->CrtcVTotal;
411    modep->CrtcHAdjusted   = p->CrtcHAdjusted;
412    modep->CrtcVAdjusted   = p->CrtcVAdjusted;
413    modep->HSync           = p->HSync;
414    modep->VRefresh        = p->VRefresh;
415    modep->Private         = p->Private;
416    modep->PrivSize        = p->PrivSize;
417
418    p->prev = modep;
419
420    return MODE_OK;
421}
422
423/*
424 * xf86LookupMode
425 *
426 * This function returns a mode from the given list which matches the
427 * given name.  When multiple modes with the same name are available,
428 * the method of picking the matching mode is determined by the
429 * strategy selected.
430 *
431 * This function takes the following parameters:
432 *    scrp         ScrnInfoPtr
433 *    modep        pointer to the returned mode, which must have the name
434 *                 field filled in.
435 *    clockRanges  a list of clock ranges.   This is optional when all the
436 *                 modes are built-in modes.
437 *    strategy     how to decide which mode to use from multiple modes with
438 *                 the same name
439 *
440 * In addition, the following fields from the ScrnInfoRec are used:
441 *    modePool     the list of monitor modes compatible with the driver
442 *    clocks       a list of discrete clocks
443 *    numClocks    number of discrete clocks
444 *    progClock    clock is programmable
445 *
446 * If a mode was found, its values are filled in to the area pointed to
447 * by modep,  If a mode was not found the return value indicates the
448 * reason.
449 */
450
451ModeStatus
452xf86LookupMode(ScrnInfoPtr scrp, DisplayModePtr modep,
453	       ClockRangePtr clockRanges, LookupModeFlags strategy)
454{
455    DisplayModePtr p, bestMode = NULL;
456    ClockRangePtr cp;
457    int i, k, gap, minimumGap = CLOCK_TOLERANCE + 1;
458    double refresh, bestRefresh = 0.0;
459    Bool found = FALSE;
460    int extraFlags = 0;
461    int clockIndex = -1;
462    int MulFactor = 1;
463    int DivFactor = 1;
464    int ModePrivFlags = 0;
465    ModeStatus status = MODE_NOMODE;
466    Bool allowDiv2 = (strategy & LOOKUP_CLKDIV2) != 0;
467    int n;
468    const int types[] = {
469	M_T_BUILTIN | M_T_PREFERRED,
470	M_T_BUILTIN,
471	M_T_USERDEF | M_T_PREFERRED,
472	M_T_USERDEF,
473	M_T_DRIVER | M_T_PREFERRED,
474	M_T_DRIVER,
475	0
476    };
477    const int ntypes = sizeof(types) / sizeof(int);
478
479    strategy &= ~(LOOKUP_CLKDIV2 | LOOKUP_OPTIONAL_TOLERANCES);
480
481    /* Some sanity checking */
482    if (scrp == NULL || scrp->modePool == NULL ||
483	(!scrp->progClock && scrp->numClocks == 0)) {
484	ErrorF("xf86LookupMode: called with invalid scrnInfoRec\n");
485	return MODE_ERROR;
486    }
487    if (modep == NULL || modep->name == NULL) {
488	ErrorF("xf86LookupMode: called with invalid modep\n");
489	return MODE_ERROR;
490    }
491    for (cp = clockRanges; cp != NULL; cp = cp->next) {
492	/* DivFactor and MulFactor must be > 0 */
493	cp->ClockDivFactor = max(1, cp->ClockDivFactor);
494	cp->ClockMulFactor = max(1, cp->ClockMulFactor);
495    }
496
497    /* Scan the mode pool for matching names */
498    for (n = 0; n < ntypes; n++) {
499	int type = types[n];
500	for (p = scrp->modePool; p != NULL; p = p->next) {
501
502	    /* scan through the modes in the sort order above */
503	    if ((p->type & type) != type)
504		continue;
505
506	    if (strcmp(p->name, modep->name) == 0) {
507
508		/* Skip over previously rejected modes */
509		if (p->status != MODE_OK) {
510		    if (!found)
511			status = p->status;
512		    continue;
513		}
514
515		/* Skip over previously considered modes */
516		if (p->prev)
517		    continue;
518
519		if (p->type & M_T_BUILTIN) {
520		    return xf86HandleBuiltinMode(scrp, p,modep, clockRanges,
521			    allowDiv2);
522		}
523
524		/* Check clock is in range */
525		cp = xf86FindClockRangeForMode(clockRanges, p);
526		if (cp == NULL) {
527		    /*
528		     * XXX Could do more here to provide a more detailed
529		     * reason for not finding a mode.
530		     */
531		    p->status = MODE_CLOCK_RANGE;
532		    if (!found)
533			status = MODE_CLOCK_RANGE;
534		    continue;
535		}
536
537		/*
538		 * If programmable clock and strategy is not
539		 * LOOKUP_BEST_REFRESH, the required mode has been found,
540		 * otherwise record the refresh and continue looking.
541		 */
542		if (scrp->progClock) {
543		    found = TRUE;
544		    if (strategy != LOOKUP_BEST_REFRESH) {
545			bestMode = p;
546			DivFactor = cp->ClockDivFactor;
547			MulFactor = cp->ClockMulFactor;
548			ModePrivFlags = cp->PrivFlags;
549			break;
550		    }
551		    refresh = xf86ModeVRefresh(p);
552		    if (p->Flags & V_INTERLACE)
553			refresh /= INTERLACE_REFRESH_WEIGHT;
554		    if (refresh > bestRefresh) {
555			bestMode = p;
556			DivFactor = cp->ClockDivFactor;
557			MulFactor = cp->ClockMulFactor;
558			ModePrivFlags = cp->PrivFlags;
559			bestRefresh = refresh;
560		    }
561		    continue;
562		}
563
564		/*
565		 * Clock is in range, so if it is not a programmable clock, find
566		 * a matching clock.
567		 */
568
569		i = xf86GetNearestClock(scrp, p->Clock, allowDiv2,
570			cp->ClockDivFactor, cp->ClockMulFactor, &k);
571		/*
572		 * If the clock is too far from the requested clock, this
573		 * mode is no good.
574		 */
575		if (k & V_CLKDIV2)
576		    gap = abs((p->Clock * 2) -
577			    ((scrp->clock[i] * cp->ClockDivFactor) /
578				cp->ClockMulFactor));
579		else
580		    gap = abs(p->Clock -
581			    ((scrp->clock[i] * cp->ClockDivFactor) /
582				cp->ClockMulFactor));
583		if (gap > minimumGap) {
584		    p->status = MODE_NOCLOCK;
585		    if (!found)
586			status = MODE_NOCLOCK;
587		    continue;
588		}
589		found = TRUE;
590
591		if (strategy == LOOKUP_BEST_REFRESH) {
592		    refresh = xf86ModeVRefresh(p);
593		    if (p->Flags & V_INTERLACE)
594			refresh /= INTERLACE_REFRESH_WEIGHT;
595		    if (refresh > bestRefresh) {
596			bestMode = p;
597			DivFactor = cp->ClockDivFactor;
598			MulFactor = cp->ClockMulFactor;
599			ModePrivFlags = cp->PrivFlags;
600			extraFlags = k;
601			clockIndex = i;
602			bestRefresh = refresh;
603		    }
604		    continue;
605		}
606		if (strategy == LOOKUP_CLOSEST_CLOCK) {
607		    if (gap < minimumGap) {
608			bestMode = p;
609			DivFactor = cp->ClockDivFactor;
610			MulFactor = cp->ClockMulFactor;
611			ModePrivFlags = cp->PrivFlags;
612			extraFlags = k;
613			clockIndex = i;
614			minimumGap = gap;
615		    }
616		    continue;
617		}
618		/*
619		 * If strategy is neither LOOKUP_BEST_REFRESH or
620		 * LOOKUP_CLOSEST_CLOCK the required mode has been found.
621		 */
622		bestMode = p;
623		DivFactor = cp->ClockDivFactor;
624		MulFactor = cp->ClockMulFactor;
625		ModePrivFlags = cp->PrivFlags;
626		extraFlags = k;
627		clockIndex = i;
628		break;
629	    }
630	}
631	if (found) break;
632    }
633    if (!found || bestMode == NULL)
634	return status;
635
636    /* Fill in the mode parameters */
637    if (scrp->progClock) {
638        modep->Clock		= bestMode->Clock;
639	modep->ClockIndex	= -1;
640	modep->SynthClock	= (modep->Clock * MulFactor) / DivFactor;
641    } else {
642	modep->Clock		= (scrp->clock[clockIndex] * DivFactor) /
643				    MulFactor;
644	modep->ClockIndex	= clockIndex;
645	modep->SynthClock	= scrp->clock[clockIndex];
646	if (extraFlags & V_CLKDIV2) {
647	    modep->Clock /= 2;
648	    modep->SynthClock /= 2;
649	}
650    }
651    modep->type                 = bestMode->type;
652    modep->PrivFlags		= ModePrivFlags;
653    modep->HDisplay		= bestMode->HDisplay;
654    modep->HSyncStart		= bestMode->HSyncStart;
655    modep->HSyncEnd		= bestMode->HSyncEnd;
656    modep->HTotal		= bestMode->HTotal;
657    modep->HSkew		= bestMode->HSkew;
658    modep->VDisplay		= bestMode->VDisplay;
659    modep->VSyncStart		= bestMode->VSyncStart;
660    modep->VSyncEnd		= bestMode->VSyncEnd;
661    modep->VTotal		= bestMode->VTotal;
662    modep->VScan		= bestMode->VScan;
663    modep->Flags		= bestMode->Flags | extraFlags;
664    modep->CrtcHDisplay		= bestMode->CrtcHDisplay;
665    modep->CrtcHBlankStart	= bestMode->CrtcHBlankStart;
666    modep->CrtcHSyncStart	= bestMode->CrtcHSyncStart;
667    modep->CrtcHSyncEnd		= bestMode->CrtcHSyncEnd;
668    modep->CrtcHBlankEnd	= bestMode->CrtcHBlankEnd;
669    modep->CrtcHTotal		= bestMode->CrtcHTotal;
670    modep->CrtcHSkew		= bestMode->CrtcHSkew;
671    modep->CrtcVDisplay		= bestMode->CrtcVDisplay;
672    modep->CrtcVBlankStart	= bestMode->CrtcVBlankStart;
673    modep->CrtcVSyncStart	= bestMode->CrtcVSyncStart;
674    modep->CrtcVSyncEnd		= bestMode->CrtcVSyncEnd;
675    modep->CrtcVBlankEnd	= bestMode->CrtcVBlankEnd;
676    modep->CrtcVTotal		= bestMode->CrtcVTotal;
677    modep->CrtcHAdjusted	= bestMode->CrtcHAdjusted;
678    modep->CrtcVAdjusted	= bestMode->CrtcVAdjusted;
679    modep->HSync		= bestMode->HSync;
680    modep->VRefresh		= bestMode->VRefresh;
681    modep->Private		= bestMode->Private;
682    modep->PrivSize		= bestMode->PrivSize;
683
684    bestMode->prev = modep;
685
686    return MODE_OK;
687}
688
689/*
690 * xf86CheckModeForMonitor
691 *
692 * This function takes a mode and monitor description, and determines
693 * if the mode is valid for the monitor.
694 */
695ModeStatus
696xf86CheckModeForMonitor(DisplayModePtr mode, MonPtr monitor)
697{
698    int i;
699
700    /* Sanity checks */
701    if (mode == NULL || monitor == NULL) {
702	ErrorF("xf86CheckModeForMonitor: called with invalid parameters\n");
703	return MODE_ERROR;
704    }
705
706    DebugF("xf86CheckModeForMonitor(%p %s, %p %s)\n",
707	   mode, mode->name, monitor, monitor->id);
708
709    /* Some basic mode validity checks */
710    if (0 >= mode->HDisplay || mode->HDisplay > mode->HSyncStart ||
711	mode->HSyncStart >= mode->HSyncEnd || mode->HSyncEnd >= mode->HTotal)
712	return MODE_H_ILLEGAL;
713
714    if (0 >= mode->VDisplay || mode->VDisplay > mode->VSyncStart ||
715	mode->VSyncStart >= mode->VSyncEnd || mode->VSyncEnd >= mode->VTotal)
716	return MODE_V_ILLEGAL;
717
718    if (monitor->nHsync > 0) {
719	/* Check hsync against the allowed ranges */
720	float hsync = xf86ModeHSync(mode);
721	for (i = 0; i < monitor->nHsync; i++)
722	    if ((hsync > monitor->hsync[i].lo * (1.0 - SYNC_TOLERANCE)) &&
723		(hsync < monitor->hsync[i].hi * (1.0 + SYNC_TOLERANCE)))
724		break;
725
726	/* Now see whether we ran out of sync ranges without finding a match */
727	if (i == monitor->nHsync)
728	    return MODE_HSYNC;
729    }
730
731    if (monitor->nVrefresh > 0) {
732	/* Check vrefresh against the allowed ranges */
733	float vrefrsh = xf86ModeVRefresh(mode);
734	for (i = 0; i < monitor->nVrefresh; i++)
735	    if ((vrefrsh > monitor->vrefresh[i].lo * (1.0 - SYNC_TOLERANCE)) &&
736		(vrefrsh < monitor->vrefresh[i].hi * (1.0 + SYNC_TOLERANCE)))
737		break;
738
739	/* Now see whether we ran out of refresh ranges without finding a match */
740	if (i == monitor->nVrefresh)
741	    return MODE_VSYNC;
742    }
743
744    /* Force interlaced modes to have an odd VTotal */
745    if (mode->Flags & V_INTERLACE)
746	mode->CrtcVTotal = mode->VTotal |= 1;
747
748    /*
749     * This code stops cvt -r modes, and only cvt -r modes, from hitting 15y+
750     * old CRTs which might, when there is a lot of solar flare activity and
751     * when the celestial bodies are unfavourably aligned, implode trying to
752     * sync to it. It's called "Protecting the user from doing anything stupid".
753     * -- libv
754     */
755
756    if (xf86ModeIsReduced(mode)) {
757        if (!monitor->reducedblanking && !(mode->type & M_T_DRIVER))
758            return MODE_NO_REDUCED;
759    }
760
761    if ((monitor->maxPixClock) && (mode->Clock > monitor->maxPixClock))
762	return MODE_CLOCK_HIGH;
763
764    return MODE_OK;
765}
766
767/*
768 * xf86CheckModeSize
769 *
770 * An internal routine to check if a mode fits in video memory.  This tries to
771 * avoid overflows that would otherwise occur when video memory size is greater
772 * than 256MB.
773 */
774static Bool
775xf86CheckModeSize(ScrnInfoPtr scrp, int w, int x, int y)
776{
777    int bpp = scrp->fbFormat.bitsPerPixel,
778	pad = scrp->fbFormat.scanlinePad;
779    int lineWidth, lastWidth;
780
781    if (scrp->depth == 4)
782	pad *= 4;		/* 4 planes */
783
784    /* Sanity check */
785    if ((w < 0) || (x < 0) || (y <= 0))
786	return FALSE;
787
788    lineWidth = (((w * bpp) + pad - 1) / pad) * pad;
789    lastWidth = x * bpp;
790
791    /*
792     * At this point, we need to compare
793     *
794     *	(lineWidth * (y - 1)) + lastWidth
795     *
796     * against
797     *
798     *	scrp->videoRam * (1024 * 8)
799     *
800     * These are bit quantities.  To avoid overflows, do the comparison in
801     * terms of BITMAP_SCANLINE_PAD units.  This assumes BITMAP_SCANLINE_PAD
802     * is a power of 2.  We currently use 32, which limits us to a video
803     * memory size of 8GB.
804     */
805
806    lineWidth = (lineWidth + (BITMAP_SCANLINE_PAD - 1)) / BITMAP_SCANLINE_PAD;
807    lastWidth = (lastWidth + (BITMAP_SCANLINE_PAD - 1)) / BITMAP_SCANLINE_PAD;
808
809    if ((lineWidth * (y - 1) + lastWidth) >
810	(scrp->videoRam * ((1024 * 8) / BITMAP_SCANLINE_PAD)))
811	return FALSE;
812
813    return TRUE;
814}
815
816/*
817 * xf86InitialCheckModeForDriver
818 *
819 * This function checks if a mode satisfies a driver's initial requirements:
820 *   -  mode size fits within the available pixel area (memory)
821 *   -  width lies within the range of supported line pitches
822 *   -  mode size fits within virtual size (if fixed)
823 *   -  horizontal timings are in range
824 *
825 * This function takes the following parameters:
826 *    scrp         ScrnInfoPtr
827 *    mode         mode to check
828 *    maxPitch     (optional) maximum line pitch
829 *    virtualX     (optional) virtual width requested
830 *    virtualY     (optional) virtual height requested
831 *
832 * In addition, the following fields from the ScrnInfoRec are used:
833 *    monitor      pointer to structure for monitor section
834 *    fbFormat     pixel format for the framebuffer
835 *    videoRam     video memory size (in kB)
836 *    maxHValue    maximum horizontal timing value
837 *    maxVValue    maximum vertical timing value
838 */
839
840ModeStatus
841xf86InitialCheckModeForDriver(ScrnInfoPtr scrp, DisplayModePtr mode,
842			      ClockRangePtr clockRanges,
843			      LookupModeFlags strategy,
844			      int maxPitch, int virtualX, int virtualY)
845{
846    ClockRangePtr cp;
847    ModeStatus status;
848    Bool allowDiv2 = (strategy & LOOKUP_CLKDIV2) != 0;
849    int i, needDiv2;
850
851    /* Sanity checks */
852    if (!scrp || !mode || !clockRanges) {
853	ErrorF("xf86InitialCheckModeForDriver: "
854		"called with invalid parameters\n");
855	return MODE_ERROR;
856    }
857
858    DebugF("xf86InitialCheckModeForDriver(%p, %p %s, %p, 0x%x, %d, %d, %d)\n",
859	   scrp, mode, mode->name , clockRanges, strategy, maxPitch,  virtualX, virtualY);
860
861    /* Some basic mode validity checks */
862    if (0 >= mode->HDisplay || mode->HDisplay > mode->HSyncStart ||
863	mode->HSyncStart >= mode->HSyncEnd || mode->HSyncEnd >= mode->HTotal)
864	return MODE_H_ILLEGAL;
865
866    if (0 >= mode->VDisplay || mode->VDisplay > mode->VSyncStart ||
867	mode->VSyncStart >= mode->VSyncEnd || mode->VSyncEnd >= mode->VTotal)
868	return MODE_V_ILLEGAL;
869
870    if (!xf86CheckModeSize(scrp, mode->HDisplay, mode->HDisplay,
871				 mode->VDisplay))
872        return MODE_MEM;
873
874    if (maxPitch > 0 && mode->HDisplay > maxPitch)
875	return MODE_BAD_WIDTH;
876
877    if (virtualX > 0 && mode->HDisplay > virtualX)
878	return MODE_VIRTUAL_X;
879
880    if (virtualY > 0 && mode->VDisplay > virtualY)
881	return MODE_VIRTUAL_Y;
882
883    if (scrp->maxHValue > 0 && mode->HTotal > scrp->maxHValue)
884	return MODE_BAD_HVALUE;
885
886    if (scrp->maxVValue > 0 && mode->VTotal > scrp->maxVValue)
887	return MODE_BAD_VVALUE;
888
889    /*
890     * The use of the DisplayModeRec's Crtc* and SynthClock elements below is
891     * provisional, in that they are later reused by the driver at mode-set
892     * time.  Here, they are temporarily enlisted to contain the mode timings
893     * as seen by the CRT or panel (rather than the CRTC).  The driver's
894     * ValidMode() is allowed to modify these so it can deal with such things
895     * as mode stretching and/or centering.  The driver should >NOT< modify the
896     * user-supplied values as these are reported back when mode validation is
897     * said and done.
898     */
899    /*
900     * NOTE: We (ab)use the mode->Crtc* values here to store timing
901     * information for the calculation of Hsync and Vrefresh. Before
902     * these values are calculated the driver is given the opportunity
903     * to either set these HSync and VRefresh itself or modify the timing
904     * values.
905     * The difference to the final calculation is small but imortand:
906     * here we pass the flag INTERLACE_HALVE_V regardless if the driver
907     * sets it or not. This way our calculation of VRefresh has the same
908     * effect as if we do if (flags & V_INTERLACE) refresh *= 2.0
909     * This dual use of the mode->Crtc* values will certainly create
910     * confusion and is bad software design. However since it's part of
911     * the driver API it's hard to change.
912     */
913
914    if (scrp->ValidMode) {
915
916	xf86SetModeCrtc(mode, INTERLACE_HALVE_V);
917
918	cp = xf86FindClockRangeForMode(clockRanges, mode);
919	if (!cp)
920	    return MODE_CLOCK_RANGE;
921
922	if (cp->ClockMulFactor < 1)
923	    cp->ClockMulFactor = 1;
924	if (cp->ClockDivFactor < 1)
925	    cp->ClockDivFactor = 1;
926
927	/*
928	 * XXX  The effect of clock dividers and multipliers on the monitor's
929	 *      pixel clock needs to be verified.
930	 */
931	if (scrp->progClock) {
932	    mode->SynthClock = mode->Clock;
933	} else {
934	    i = xf86GetNearestClock(scrp, mode->Clock, allowDiv2,
935				    cp->ClockDivFactor, cp->ClockMulFactor,
936				    &needDiv2);
937	    mode->SynthClock = (scrp->clock[i] * cp->ClockDivFactor) /
938		cp->ClockMulFactor;
939	    if (needDiv2 & V_CLKDIV2)
940		mode->SynthClock /= 2;
941	}
942
943	status = (*scrp->ValidMode)(scrp->scrnIndex, mode, FALSE,
944				    MODECHECK_INITIAL);
945	if (status != MODE_OK)
946	    return status;
947
948	if (mode->HSync <= 0.0)
949	    mode->HSync = (float)mode->SynthClock / (float)mode->CrtcHTotal;
950	if (mode->VRefresh <= 0.0)
951	    mode->VRefresh = (mode->SynthClock * 1000.0)
952		/ (mode->CrtcHTotal * mode->CrtcVTotal);
953    }
954
955    mode->HSync = xf86ModeHSync(mode);
956    mode->VRefresh = xf86ModeVRefresh(mode);
957
958    /* Assume it is OK */
959    return MODE_OK;
960}
961
962/*
963 * xf86CheckModeForDriver
964 *
965 * This function is for checking modes while the server is running (for
966 * use mainly by the VidMode extension).
967 *
968 * This function checks if a mode satisfies a driver's requirements:
969 *   -  width lies within the line pitch
970 *   -  mode size fits within virtual size
971 *   -  horizontal/vertical timings are in range
972 *
973 * This function takes the following parameters:
974 *    scrp         ScrnInfoPtr
975 *    mode         mode to check
976 *    flags        not (currently) used
977 *
978 * In addition, the following fields from the ScrnInfoRec are used:
979 *    maxHValue    maximum horizontal timing value
980 *    maxVValue    maximum vertical timing value
981 *    virtualX     virtual width
982 *    virtualY     virtual height
983 *    clockRanges  allowable clock ranges
984 */
985
986ModeStatus
987xf86CheckModeForDriver(ScrnInfoPtr scrp, DisplayModePtr mode, int flags)
988{
989    ClockRangePtr cp;
990    int i, k, gap, minimumGap = CLOCK_TOLERANCE + 1;
991    int extraFlags = 0;
992    int clockIndex = -1;
993    int MulFactor = 1;
994    int DivFactor = 1;
995    int ModePrivFlags = 0;
996    ModeStatus status = MODE_NOMODE;
997
998    /* Some sanity checking */
999    if (scrp == NULL ||	(!scrp->progClock && scrp->numClocks == 0)) {
1000	ErrorF("xf86CheckModeForDriver: called with invalid scrnInfoRec\n");
1001	return MODE_ERROR;
1002    }
1003    if (mode == NULL) {
1004	ErrorF("xf86CheckModeForDriver: called with invalid modep\n");
1005	return MODE_ERROR;
1006    }
1007
1008    /* Check the mode size */
1009    if (mode->HDisplay > scrp->virtualX)
1010	return MODE_VIRTUAL_X;
1011
1012    if (mode->VDisplay > scrp->virtualY)
1013	return MODE_VIRTUAL_Y;
1014
1015    if (scrp->maxHValue > 0 && mode->HTotal > scrp->maxHValue)
1016	return MODE_BAD_HVALUE;
1017
1018    if (scrp->maxVValue > 0 && mode->VTotal > scrp->maxVValue)
1019	return MODE_BAD_VVALUE;
1020
1021    for (cp = scrp->clockRanges; cp != NULL; cp = cp->next) {
1022	/* DivFactor and MulFactor must be > 0 */
1023	cp->ClockDivFactor = max(1, cp->ClockDivFactor);
1024	cp->ClockMulFactor = max(1, cp->ClockMulFactor);
1025    }
1026
1027    if (scrp->progClock) {
1028	/* Check clock is in range */
1029	for (cp = scrp->clockRanges; cp != NULL; cp = cp->next) {
1030	    if (modeInClockRange(cp, mode))
1031	        break;
1032	}
1033	if (cp == NULL) {
1034	    return MODE_CLOCK_RANGE;
1035	}
1036	/*
1037	 * If programmable clock the required mode has been found
1038	 */
1039    	DivFactor = cp->ClockDivFactor;
1040	MulFactor = cp->ClockMulFactor;
1041	ModePrivFlags = cp->PrivFlags;
1042    } else {
1043	 status = MODE_CLOCK_RANGE;
1044	/* Check clock is in range */
1045	for (cp = scrp->clockRanges; cp != NULL; cp = cp->next) {
1046	    if (modeInClockRange(cp, mode)) {
1047		/*
1048	 	 * Clock is in range, so if it is not a programmable clock,
1049		 * find a matching clock.
1050		 */
1051
1052		i = xf86GetNearestClock(scrp, mode->Clock, 0,
1053			   cp->ClockDivFactor, cp->ClockMulFactor, &k);
1054		/*
1055		 * If the clock is too far from the requested clock, this
1056		 * mode is no good.
1057		 */
1058		if (k & V_CLKDIV2)
1059		    gap = abs((mode->Clock * 2) -
1060			      ((scrp->clock[i] * cp->ClockDivFactor) /
1061			       cp->ClockMulFactor));
1062		else
1063		    gap = abs(mode->Clock -
1064			      ((scrp->clock[i] * cp->ClockDivFactor) /
1065			       cp->ClockMulFactor));
1066		if (gap > minimumGap) {
1067		    status = MODE_NOCLOCK;
1068		    continue;
1069		}
1070
1071		DivFactor = cp->ClockDivFactor;
1072		MulFactor = cp->ClockMulFactor;
1073		ModePrivFlags = cp->PrivFlags;
1074		extraFlags = k;
1075		clockIndex = i;
1076		break;
1077	    }
1078	}
1079	if (cp == NULL)
1080	    return status;
1081    }
1082
1083    /* Fill in the mode parameters */
1084    if (scrp->progClock) {
1085	mode->ClockIndex	= -1;
1086	mode->SynthClock	= (mode->Clock * MulFactor) / DivFactor;
1087    } else {
1088	mode->Clock		= (scrp->clock[clockIndex] * DivFactor) / MulFactor;
1089	mode->ClockIndex	= clockIndex;
1090	mode->SynthClock	= scrp->clock[clockIndex];
1091	if (extraFlags & V_CLKDIV2) {
1092	    mode->Clock /= 2;
1093	    mode->SynthClock /= 2;
1094	}
1095    }
1096    mode->PrivFlags		= ModePrivFlags;
1097
1098    return MODE_OK;
1099}
1100
1101static int
1102inferVirtualSize(ScrnInfoPtr scrp, DisplayModePtr modes, int *vx, int *vy)
1103{
1104    float aspect = 0.0;
1105    MonPtr mon = scrp->monitor;
1106    xf86MonPtr DDC;
1107    int x = 0, y = 0;
1108    DisplayModePtr mode;
1109
1110    if (!mon) return 0;
1111    DDC = mon->DDC;
1112
1113    if (DDC && DDC->ver.revision >= 4) {
1114	/* For 1.4, we might actually get native pixel format.  How novel. */
1115	if (PREFERRED_TIMING_MODE(DDC->features.msc)) {
1116		for (mode = modes; mode; mode = mode->next) {
1117		    if (mode->type & (M_T_DRIVER | M_T_PREFERRED)) {
1118			x = mode->HDisplay;
1119			y = mode->VDisplay;
1120			goto found;
1121		    }
1122		}
1123	}
1124	/*
1125	 * Even if we don't, we might get aspect ratio from extra CVT info
1126	 * or from the monitor size fields.  TODO.
1127	 */
1128    }
1129
1130    /*
1131     * Technically this triggers if either is zero.  That wasn't legal
1132     * before EDID 1.4, but right now we'll get that wrong. TODO.
1133     */
1134    if (!aspect) {
1135	if (!mon->widthmm || !mon->heightmm)
1136	    aspect = 4.0/3.0;
1137	else
1138	    aspect = (float)mon->widthmm / (float)mon->heightmm;
1139    }
1140
1141    /* find the largest M_T_DRIVER mode with that aspect ratio */
1142    for (mode = modes; mode; mode = mode->next) {
1143	float mode_aspect, metaspect;
1144	if (!(mode->type & (M_T_DRIVER|M_T_USERDEF)))
1145	    continue;
1146	mode_aspect = (float)mode->HDisplay / (float)mode->VDisplay;
1147	metaspect = aspect / mode_aspect;
1148	/* 5% slop or so, since we only get size in centimeters */
1149	if (fabs(1.0 - metaspect) < 0.05) {
1150	    if ((mode->HDisplay > x) && (mode->VDisplay > y)) {
1151		x = mode->HDisplay;
1152		y = mode->VDisplay;
1153	    }
1154	}
1155    }
1156
1157    if (!x || !y) {
1158	xf86DrvMsg(scrp->scrnIndex, X_WARNING,
1159		   "Unable to estimate virtual size\n");
1160	return 0;
1161    }
1162
1163found:
1164    *vx = x;
1165    *vy = y;
1166
1167    xf86DrvMsg(scrp->scrnIndex, X_INFO,
1168	       "Estimated virtual size for aspect ratio %.4f is %dx%d\n",
1169	       aspect, *vx, *vy);
1170
1171    return 1;
1172}
1173
1174/* Least common multiple */
1175static unsigned int
1176LCM(unsigned int x, unsigned int y)
1177{
1178    unsigned int m = x, n = y, o;
1179
1180    while ((o = m % n))
1181    {
1182        m = n;
1183        n = o;
1184    }
1185
1186    return (x / n) * y;
1187}
1188
1189/*
1190 * Given various screen attributes, determine the minimum scanline width such
1191 * that each scanline is server and DDX padded and any pixels with imbedded
1192 * bank boundaries are off-screen.  This function returns -1 if such a width
1193 * cannot exist.
1194 */
1195static int
1196scanLineWidth(
1197    unsigned int     xsize,         /* pixels */
1198    unsigned int     ysize,         /* pixels */
1199    unsigned int     width,         /* pixels */
1200    unsigned long    BankSize,      /* char's */
1201    PixmapFormatRec *pBankFormat,
1202    unsigned int     nWidthUnit     /* bits */
1203)
1204{
1205    unsigned long nBitsPerBank, nBitsPerScanline, nBitsPerScanlinePadUnit;
1206    unsigned long minBitsPerScanline, maxBitsPerScanline;
1207
1208    /* Sanity checks */
1209
1210    if (!nWidthUnit || !pBankFormat)
1211        return -1;
1212
1213    nBitsPerBank = BankSize * 8;
1214    if (nBitsPerBank % pBankFormat->scanlinePad)
1215        return -1;
1216
1217    if (xsize > width)
1218        width = xsize;
1219    nBitsPerScanlinePadUnit = LCM(pBankFormat->scanlinePad, nWidthUnit);
1220    nBitsPerScanline =
1221        (((width * pBankFormat->bitsPerPixel) + nBitsPerScanlinePadUnit - 1) /
1222         nBitsPerScanlinePadUnit) * nBitsPerScanlinePadUnit;
1223    width = nBitsPerScanline / pBankFormat->bitsPerPixel;
1224
1225    if (!xsize || !(nBitsPerBank % pBankFormat->bitsPerPixel))
1226        return (int)width;
1227
1228    /*
1229     * Scanlines will be server-pad aligned at this point.  They will also be
1230     * a multiple of nWidthUnit bits long.  Ensure that pixels with imbedded
1231     * bank boundaries are off-screen.
1232     *
1233     * It seems reasonable to limit total frame buffer size to 1/16 of the
1234     * theoretical maximum address space size.  On a machine with 32-bit
1235     * addresses (to 8-bit quantities) this turns out to be 256MB.  Not only
1236     * does this provide a simple limiting condition for the loops below, but
1237     * it also prevents unsigned long wraparounds.
1238     */
1239    if (!ysize)
1240        return -1;
1241
1242    minBitsPerScanline = xsize * pBankFormat->bitsPerPixel;
1243    if (minBitsPerScanline > nBitsPerBank)
1244        return -1;
1245
1246    if (ysize == 1)
1247        return (int)width;
1248
1249    maxBitsPerScanline =
1250        (((unsigned long)(-1) >> 1) - minBitsPerScanline) / (ysize - 1);
1251    while (nBitsPerScanline <= maxBitsPerScanline)
1252    {
1253        unsigned long BankBase, BankUnit;
1254
1255        BankUnit = ((nBitsPerBank + nBitsPerScanline - 1) / nBitsPerBank) *
1256            nBitsPerBank;
1257        if (!(BankUnit % nBitsPerScanline))
1258            return (int)width;
1259
1260        for (BankBase = BankUnit;  ;  BankBase += nBitsPerBank)
1261        {
1262            unsigned long x, y;
1263
1264            y = BankBase / nBitsPerScanline;
1265            if (y >= ysize)
1266                return (int)width;
1267
1268            x = BankBase % nBitsPerScanline;
1269            if (!(x % pBankFormat->bitsPerPixel))
1270                continue;
1271
1272            if (x < minBitsPerScanline)
1273            {
1274                /*
1275                 * Skip ahead certain widths by dividing the excess scanline
1276                 * amongst the y's.
1277                 */
1278                y *= nBitsPerScanlinePadUnit;
1279                nBitsPerScanline +=
1280                    ((x + y - 1) / y) * nBitsPerScanlinePadUnit;
1281                width = nBitsPerScanline / pBankFormat->bitsPerPixel;
1282                break;
1283            }
1284
1285            if (BankBase != BankUnit)
1286                continue;
1287
1288            if (!(nBitsPerScanline % x))
1289                return (int)width;
1290
1291            BankBase = ((nBitsPerScanline - minBitsPerScanline) /
1292                (nBitsPerScanline - x)) * BankUnit;
1293        }
1294    }
1295
1296    return -1;
1297}
1298
1299/*
1300 * xf86ValidateModes
1301 *
1302 * This function takes a set of mode names, modes and limiting conditions,
1303 * and selects a set of modes and parameters based on those conditions.
1304 *
1305 * This function takes the following parameters:
1306 *    scrp         ScrnInfoPtr
1307 *    availModes   the list of modes available for the monitor
1308 *    modeNames    (optional) list of mode names that the screen is requesting
1309 *    clockRanges  a list of clock ranges
1310 *    linePitches  (optional) a list of line pitches
1311 *    minPitch     (optional) minimum line pitch (in pixels)
1312 *    maxPitch     (optional) maximum line pitch (in pixels)
1313 *    pitchInc     (mandatory) pitch increment (in bits)
1314 *    minHeight    (optional) minimum virtual height (in pixels)
1315 *    maxHeight    (optional) maximum virtual height (in pixels)
1316 *    virtualX     (optional) virtual width requested (in pixels)
1317 *    virtualY     (optional) virtual height requested (in pixels)
1318 *    apertureSize size of video aperture (in bytes)
1319 *    strategy     how to decide which mode to use from multiple modes with
1320 *                 the same name
1321 *
1322 * In addition, the following fields from the ScrnInfoRec are used:
1323 *    clocks       a list of discrete clocks
1324 *    numClocks    number of discrete clocks
1325 *    progClock    clock is programmable
1326 *    monitor      pointer to structure for monitor section
1327 *    fbFormat     format of the framebuffer
1328 *    videoRam     video memory size
1329 *    maxHValue    maximum horizontal timing value
1330 *    maxVValue    maximum vertical timing value
1331 *    xInc         horizontal timing increment (defaults to 8 pixels)
1332 *
1333 * The function fills in the following ScrnInfoRec fields:
1334 *    modePool     A subset of the modes available to the monitor which
1335 *		   are compatible with the driver.
1336 *    modes        one mode entry for each of the requested modes, with the
1337 *                 status field filled in to indicate if the mode has been
1338 *                 accepted or not.
1339 *    virtualX     the resulting virtual width
1340 *    virtualY     the resulting virtual height
1341 *    displayWidth the resulting line pitch
1342 *
1343 * The function's return value is the number of matching modes found, or -1
1344 * if an unrecoverable error was encountered.
1345 */
1346
1347int
1348xf86ValidateModes(ScrnInfoPtr scrp, DisplayModePtr availModes,
1349		  const char **modeNames, ClockRangePtr clockRanges,
1350		  int *linePitches, int minPitch, int maxPitch, int pitchInc,
1351		  int minHeight, int maxHeight, int virtualX, int virtualY,
1352		  int apertureSize, LookupModeFlags strategy)
1353{
1354    DisplayModePtr p, q, r, new, last, *endp;
1355    int i, numModes = 0;
1356    ModeStatus status;
1357    int linePitch = -1, virtX = 0, virtY = 0;
1358    int newLinePitch, newVirtX, newVirtY;
1359    int modeSize;					/* in pixels */
1360    Bool validateAllDefaultModes = FALSE;
1361    Bool userModes = FALSE;
1362    int saveType;
1363    PixmapFormatRec *BankFormat;
1364    ClockRangePtr cp;
1365    ClockRangePtr storeClockRanges;
1366    int numTimings = 0;
1367    range hsync[MAX_HSYNC];
1368    range vrefresh[MAX_VREFRESH];
1369    Bool inferred_virtual = FALSE;
1370
1371    DebugF("xf86ValidateModes(%p, %p, %p, %p,\n\t\t  %p, %d, %d, %d, %d, %d, %d, %d, %d, 0x%x)\n",
1372	   scrp, availModes, modeNames, clockRanges,
1373	   linePitches, minPitch, maxPitch, pitchInc,
1374	   minHeight, maxHeight, virtualX, virtualY,
1375	   apertureSize, strategy
1376	   );
1377
1378    /* Some sanity checking */
1379    if (scrp == NULL || scrp->name == NULL || !scrp->monitor ||
1380	(!scrp->progClock && scrp->numClocks == 0)) {
1381	ErrorF("xf86ValidateModes: called with invalid scrnInfoRec\n");
1382	return -1;
1383    }
1384    if (linePitches != NULL && linePitches[0] <= 0) {
1385	ErrorF("xf86ValidateModes: called with invalid linePitches\n");
1386	return -1;
1387    }
1388    if (pitchInc <= 0) {
1389	ErrorF("xf86ValidateModes: called with invalid pitchInc\n");
1390	return -1;
1391    }
1392    if ((virtualX > 0) != (virtualY > 0)) {
1393	ErrorF("xf86ValidateModes: called with invalid virtual resolution\n");
1394	return -1;
1395    }
1396
1397    /*
1398     * If requested by the driver, allow missing hsync and/or vrefresh ranges
1399     * in the monitor section.
1400     */
1401    if (strategy & LOOKUP_OPTIONAL_TOLERANCES) {
1402	strategy &= ~LOOKUP_OPTIONAL_TOLERANCES;
1403    } else {
1404	const char *type = "";
1405        Bool specified = FALSE;
1406
1407	if (scrp->monitor->nHsync <= 0) {
1408	    if (numTimings > 0) {
1409		scrp->monitor->nHsync = numTimings;
1410		for (i = 0; i < numTimings; i++) {
1411		    scrp->monitor->hsync[i].lo = hsync[i].lo;
1412		    scrp->monitor->hsync[i].hi = hsync[i].hi;
1413		}
1414	    } else {
1415		scrp->monitor->hsync[0].lo = 31.5;
1416		scrp->monitor->hsync[0].hi = 48.0;
1417		scrp->monitor->nHsync = 1;
1418	    }
1419	    type = "default ";
1420	} else {
1421            specified = TRUE;
1422        }
1423	for (i = 0; i < scrp->monitor->nHsync; i++) {
1424	    if (scrp->monitor->hsync[i].lo == scrp->monitor->hsync[i].hi)
1425	      xf86DrvMsg(scrp->scrnIndex, X_INFO,
1426			 "%s: Using %shsync value of %.2f kHz\n",
1427			 scrp->monitor->id, type,
1428			 scrp->monitor->hsync[i].lo);
1429	    else
1430	      xf86DrvMsg(scrp->scrnIndex, X_INFO,
1431			 "%s: Using %shsync range of %.2f-%.2f kHz\n",
1432			 scrp->monitor->id, type,
1433			 scrp->monitor->hsync[i].lo,
1434			 scrp->monitor->hsync[i].hi);
1435	}
1436
1437	type = "";
1438	if (scrp->monitor->nVrefresh <= 0) {
1439	    if (numTimings > 0) {
1440		scrp->monitor->nVrefresh = numTimings;
1441		for (i = 0; i < numTimings; i++) {
1442		    scrp->monitor->vrefresh[i].lo = vrefresh[i].lo;
1443		    scrp->monitor->vrefresh[i].hi = vrefresh[i].hi;
1444		}
1445	    } else {
1446		scrp->monitor->vrefresh[0].lo = 50;
1447		scrp->monitor->vrefresh[0].hi = 70;
1448		scrp->monitor->nVrefresh = 1;
1449	    }
1450	    type = "default ";
1451	} else {
1452            specified = TRUE;
1453        }
1454	for (i = 0; i < scrp->monitor->nVrefresh; i++) {
1455	    if (scrp->monitor->vrefresh[i].lo == scrp->monitor->vrefresh[i].hi)
1456	      xf86DrvMsg(scrp->scrnIndex, X_INFO,
1457			 "%s: Using %svrefresh value of %.2f Hz\n",
1458			 scrp->monitor->id, type,
1459			 scrp->monitor->vrefresh[i].lo);
1460	    else
1461	      xf86DrvMsg(scrp->scrnIndex, X_INFO,
1462			 "%s: Using %svrefresh range of %.2f-%.2f Hz\n",
1463			 scrp->monitor->id, type,
1464			 scrp->monitor->vrefresh[i].lo,
1465			 scrp->monitor->vrefresh[i].hi);
1466	}
1467
1468        type = "";
1469	if (!scrp->monitor->maxPixClock && !specified) {
1470            type = "default ";
1471            scrp->monitor->maxPixClock = 65000.0;
1472        }
1473	if (scrp->monitor->maxPixClock) {
1474	    xf86DrvMsg(scrp->scrnIndex, X_INFO,
1475		       "%s: Using %smaximum pixel clock of %.2f MHz\n",
1476		       scrp->monitor->id, type,
1477		       (float)scrp->monitor->maxPixClock / 1000.0);
1478	}
1479    }
1480
1481    /*
1482     * Store the clockRanges for later use by the VidMode extension.
1483     */
1484    storeClockRanges = scrp->clockRanges;
1485    while (storeClockRanges != NULL) {
1486	storeClockRanges = storeClockRanges->next;
1487    }
1488    for (cp = clockRanges; cp != NULL; cp = cp->next,
1489	   	storeClockRanges = storeClockRanges->next) {
1490	storeClockRanges = xnfalloc(sizeof(ClockRange));
1491	if (scrp->clockRanges == NULL)
1492	    scrp->clockRanges = storeClockRanges;
1493	memcpy(storeClockRanges, cp, sizeof(ClockRange));
1494    }
1495
1496    /* Determine which pixmap format to pass to scanLineWidth() */
1497    if (scrp->depth > 4)
1498	BankFormat = &scrp->fbFormat;
1499    else
1500	BankFormat = xf86GetPixFormat(scrp, 1);	/* >not< scrp->depth! */
1501
1502    if (scrp->xInc <= 0)
1503        scrp->xInc = 8;		/* Suitable for VGA and others */
1504
1505#define _VIRTUALX(x) ((((x) + scrp->xInc - 1) / scrp->xInc) * scrp->xInc)
1506
1507    /*
1508     * Determine maxPitch if it wasn't given explicitly.  Note linePitches
1509     * always takes precedence if is non-NULL.  In that case the minPitch and
1510     * maxPitch values passed are ignored.
1511     */
1512    if (linePitches) {
1513	minPitch = maxPitch = linePitches[0];
1514	for (i = 1; linePitches[i] > 0; i++) {
1515	    if (linePitches[i] > maxPitch)
1516		maxPitch = linePitches[i];
1517	    if (linePitches[i] < minPitch)
1518		minPitch = linePitches[i];
1519	}
1520    }
1521
1522    /* Initial check of virtual size against other constraints */
1523    scrp->virtualFrom = X_PROBED;
1524    /*
1525     * Initialise virtX and virtY if the values are fixed.
1526     */
1527    if (virtualY > 0) {
1528	if (maxHeight > 0 && virtualY > maxHeight) {
1529	    xf86DrvMsg(scrp->scrnIndex, X_ERROR,
1530		       "Virtual height (%d) is too large for the hardware "
1531		       "(max %d)\n", virtualY, maxHeight);
1532	    return -1;
1533	}
1534
1535	if (minHeight > 0 && virtualY < minHeight) {
1536	    xf86DrvMsg(scrp->scrnIndex, X_ERROR,
1537		       "Virtual height (%d) is too small for the hardware "
1538		       "(min %d)\n", virtualY, minHeight);
1539	    return -1;
1540	}
1541
1542	virtualX = _VIRTUALX(virtualX);
1543	if (linePitches != NULL) {
1544	    for (i = 0; linePitches[i] != 0; i++) {
1545		if ((linePitches[i] >= virtualX) &&
1546		    (linePitches[i] ==
1547		     scanLineWidth(virtualX, virtualY, linePitches[i],
1548				   apertureSize, BankFormat, pitchInc))) {
1549		    linePitch = linePitches[i];
1550		    break;
1551		}
1552	    }
1553	} else {
1554	    linePitch = scanLineWidth(virtualX, virtualY, minPitch,
1555				      apertureSize, BankFormat, pitchInc);
1556	}
1557
1558	if ((linePitch < minPitch) || (linePitch > maxPitch)) {
1559	    xf86DrvMsg(scrp->scrnIndex, X_ERROR,
1560		       "Virtual width (%d) is too large for the hardware "
1561		       "(max %d)\n", virtualX, maxPitch);
1562	    return -1;
1563	}
1564
1565	if (!xf86CheckModeSize(scrp, linePitch, virtualX, virtualY)) {
1566	    xf86DrvMsg(scrp->scrnIndex, X_ERROR,
1567		      "Virtual size (%dx%d) (pitch %d) exceeds video memory\n",
1568		      virtualX, virtualY, linePitch);
1569	    return -1;
1570	}
1571
1572	virtX = virtualX;
1573	virtY = virtualY;
1574	scrp->virtualFrom = X_CONFIG;
1575    } else if (!modeNames || !*modeNames) {
1576	/* No virtual size given in the config, try to infer */
1577	/* XXX this doesn't take m{in,ax}Pitch into account; oh well */
1578	inferred_virtual = inferVirtualSize(scrp, availModes, &virtX, &virtY);
1579	if (inferred_virtual)
1580	    linePitch = scanLineWidth(virtX, virtY, minPitch, apertureSize,
1581				      BankFormat, pitchInc);
1582    }
1583
1584    /* Print clock ranges and scaled clocks */
1585    xf86ShowClockRanges(scrp, clockRanges);
1586
1587    /*
1588     * If scrp->modePool hasn't been setup yet, set it up now.  This allows the
1589     * modes that the driver definitely can't use to be weeded out early.  Note
1590     * that a modePool mode's prev field is used to hold a pointer to the
1591     * member of the scrp->modes list for which a match was considered.
1592     */
1593    if (scrp->modePool == NULL) {
1594	q = NULL;
1595	for (p = availModes; p != NULL; p = p->next) {
1596	    status = xf86InitialCheckModeForDriver(scrp, p, clockRanges,
1597						   strategy, maxPitch,
1598						   virtX, virtY);
1599
1600	    if (status == MODE_OK) {
1601		status = xf86CheckModeForMonitor(p, scrp->monitor);
1602	    }
1603
1604	    if (status == MODE_OK) {
1605		new = xnfalloc(sizeof(DisplayModeRec));
1606		*new = *p;
1607		new->next = NULL;
1608		if (!q) {
1609		    scrp->modePool = new;
1610		} else {
1611		    q->next = new;
1612		}
1613		new->prev = NULL;
1614		q = new;
1615		q->name = xnfstrdup(p->name);
1616	        q->status = MODE_OK;
1617	    } else {
1618		printModeRejectMessage(scrp->scrnIndex, p, status);
1619	    }
1620	}
1621
1622	if (scrp->modePool == NULL) {
1623	    xf86DrvMsg(scrp->scrnIndex, X_WARNING, "Mode pool is empty\n");
1624	    return 0;
1625	}
1626    } else {
1627	for (p = scrp->modePool; p != NULL; p = p->next) {
1628	    p->prev = NULL;
1629	    p->status = MODE_OK;
1630	}
1631    }
1632
1633    /*
1634     * Allocate one entry in scrp->modes for each named mode.
1635     */
1636    while (scrp->modes)
1637	xf86DeleteMode(&scrp->modes, scrp->modes);
1638    endp = &scrp->modes;
1639    last = NULL;
1640    if (modeNames != NULL) {
1641	for (i = 0; modeNames[i] != NULL; i++) {
1642	    userModes = TRUE;
1643	    new = xnfcalloc(1, sizeof(DisplayModeRec));
1644	    new->prev = last;
1645	    new->type = M_T_USERDEF;
1646	    new->name = xnfstrdup(modeNames[i]);
1647	    if (new->prev)
1648		new->prev->next = new;
1649	    *endp = last = new;
1650	    endp = &new->next;
1651	}
1652    }
1653
1654    /* Lookup each mode */
1655#ifdef RANDR
1656    if (!xf86Info.disableRandR
1657#ifdef PANORAMIX
1658	&& noPanoramiXExtension
1659#endif
1660	)
1661	validateAllDefaultModes = TRUE;
1662#endif
1663
1664    for (p = scrp->modes; ; p = p->next) {
1665	Bool repeat;
1666
1667	/*
1668	 * If the supplied mode names don't produce a valid mode, scan through
1669	 * unconsidered modePool members until one survives validation.  This
1670	 * is done in decreasing order by mode pixel area.
1671	 */
1672
1673	if (p == NULL) {
1674	    if ((numModes > 0) && !validateAllDefaultModes)
1675		break;
1676
1677	    validateAllDefaultModes = TRUE;
1678	    r = NULL;
1679	    modeSize = 0;
1680	    for (q = scrp->modePool;  q != NULL;  q = q->next) {
1681		if ((q->prev == NULL) && (q->status == MODE_OK)) {
1682		    /*
1683		     * Deal with the case where this mode wasn't considered
1684		     * because of a builtin mode of the same name.
1685		     */
1686		    for (p = scrp->modes; p != NULL; p = p->next) {
1687			if ((p->status != MODE_OK) &&
1688			    !strcmp(p->name, q->name))
1689			    break;
1690		    }
1691
1692		    if (p != NULL)
1693			q->prev = p;
1694		    else {
1695			/*
1696			 * A quick check to not allow default modes with
1697			 * horizontal timing parameters that CRTs may have
1698			 * problems with.
1699			 */
1700			if (!scrp->monitor->reducedblanking &&
1701			    (q->type & M_T_DEFAULT) &&
1702			    ((double)q->HTotal / (double)q->HDisplay) < 1.15)
1703			    continue;
1704
1705			if (modeSize < (q->HDisplay * q->VDisplay)) {
1706			    r = q;
1707			    modeSize = q->HDisplay * q->VDisplay;
1708			}
1709		    }
1710		}
1711	    }
1712
1713	    if (r == NULL)
1714		break;
1715
1716	    p = xnfcalloc(1, sizeof(DisplayModeRec));
1717	    p->prev = last;
1718	    p->name = xnfstrdup(r->name);
1719	    if (!userModes)
1720		p->type = M_T_USERDEF;
1721	    if (p->prev)
1722		p->prev->next = p;
1723	    *endp = last = p;
1724	    endp = &p->next;
1725	}
1726
1727	repeat = FALSE;
1728    lookupNext:
1729	if (repeat && ((status = p->status) != MODE_OK))
1730	    printModeRejectMessage(scrp->scrnIndex, p, status);
1731	saveType = p->type;
1732	status = xf86LookupMode(scrp, p, clockRanges, strategy);
1733	if (repeat && status == MODE_NOMODE)
1734	    continue;
1735	if (status != MODE_OK)
1736	    printModeRejectMessage(scrp->scrnIndex, p, status);
1737	if (status == MODE_ERROR) {
1738	    ErrorF("xf86ValidateModes: "
1739		   "unexpected result from xf86LookupMode()\n");
1740	    return -1;
1741	}
1742	if (status != MODE_OK) {
1743	    if (p->status == MODE_OK)
1744		p->status = status;
1745	    continue;
1746	}
1747	p->type |= saveType;
1748	repeat = TRUE;
1749
1750	newLinePitch = linePitch;
1751	newVirtX = virtX;
1752	newVirtY = virtY;
1753
1754	/*
1755	 * Don't let non-user defined modes increase the virtual size
1756	 */
1757	if (!(p->type & M_T_USERDEF) && (numModes > 0)) {
1758	    if (p->HDisplay > virtX) {
1759		p->status = MODE_VIRTUAL_X;
1760		goto lookupNext;
1761	    }
1762	    if (p->VDisplay > virtY) {
1763		p->status = MODE_VIRTUAL_Y;
1764		goto lookupNext;
1765	    }
1766	}
1767	/*
1768	 * Adjust virtual width and height if the mode is too large for the
1769	 * current values and if they are not fixed.
1770	 */
1771	if (virtualX <= 0 && p->HDisplay > newVirtX)
1772	    newVirtX = _VIRTUALX(p->HDisplay);
1773	if (virtualY <= 0 && p->VDisplay > newVirtY) {
1774	    if (maxHeight > 0 && p->VDisplay > maxHeight) {
1775		p->status = MODE_VIRTUAL_Y;	/* ? */
1776		goto lookupNext;
1777	    }
1778	    newVirtY = p->VDisplay;
1779	}
1780
1781	/*
1782	 * If virtual resolution is to be increased, revalidate it.
1783	 */
1784	if ((virtX != newVirtX) || (virtY != newVirtY)) {
1785	    if (linePitches != NULL) {
1786		newLinePitch = -1;
1787		for (i = 0; linePitches[i] != 0; i++) {
1788		    if ((linePitches[i] >= newVirtX) &&
1789			(linePitches[i] >= linePitch) &&
1790			(linePitches[i] ==
1791			 scanLineWidth(newVirtX, newVirtY, linePitches[i],
1792				       apertureSize, BankFormat, pitchInc))) {
1793			newLinePitch = linePitches[i];
1794			break;
1795		    }
1796		}
1797	    } else {
1798		if (linePitch < minPitch)
1799		    linePitch = minPitch;
1800		newLinePitch = scanLineWidth(newVirtX, newVirtY, linePitch,
1801					     apertureSize, BankFormat,
1802					     pitchInc);
1803	    }
1804	    if ((newLinePitch < minPitch) || (newLinePitch > maxPitch)) {
1805		p->status = MODE_BAD_WIDTH;
1806		goto lookupNext;
1807	    }
1808
1809	    /*
1810	     * Check that the pixel area required by the new virtual height
1811	     * and line pitch isn't too large.
1812	     */
1813	    if (!xf86CheckModeSize(scrp, newLinePitch, newVirtX, newVirtY)) {
1814		p->status = MODE_MEM_VIRT;
1815		goto lookupNext;
1816	    }
1817	}
1818
1819	if (scrp->ValidMode) {
1820	    /*
1821	     * Give the driver a final say, passing it the proposed virtual
1822	     * geometry.
1823	     */
1824	    scrp->virtualX = newVirtX;
1825	    scrp->virtualY = newVirtY;
1826	    scrp->displayWidth = newLinePitch;
1827	    p->status = (scrp->ValidMode)(scrp->scrnIndex, p, FALSE,
1828					  MODECHECK_FINAL);
1829
1830	    if (p->status != MODE_OK) {
1831	        goto lookupNext;
1832	    }
1833	}
1834
1835	/* Mode has passed all the tests */
1836	virtX = newVirtX;
1837	virtY = newVirtY;
1838	linePitch = newLinePitch;
1839	p->status = MODE_OK;
1840	numModes++;
1841    }
1842
1843    /*
1844     * If we estimated the virtual size above, we may have filtered away all
1845     * the modes that maximally match that size; scan again to find out and
1846     * fix up if so.
1847     */
1848    if (inferred_virtual) {
1849	int vx = 0, vy = 0;
1850	for (p = scrp->modes; p; p = p->next) {
1851	    if (p->HDisplay > vx && p->VDisplay > vy) {
1852		vx = p->HDisplay;
1853		vy = p->VDisplay;
1854	    }
1855	}
1856	if (vx < virtX || vy < virtY) {
1857	    const int types[] = {
1858		M_T_BUILTIN | M_T_PREFERRED,
1859		M_T_BUILTIN,
1860		M_T_DRIVER | M_T_PREFERRED,
1861		M_T_DRIVER,
1862		0
1863	    };
1864	    const int ntypes = sizeof(types) / sizeof(int);
1865	    int n;
1866
1867	    /*
1868	     * We did not find the estimated virtual size. So now we want to
1869	     * find the largest mode available, but we want to search in the
1870	     * modes in the order of "types" listed above.
1871	     */
1872	    for (n = 0; n < ntypes; n++) {
1873		int type = types[n];
1874
1875		vx = 0; vy = 0;
1876		for (p = scrp->modes; p; p = p->next) {
1877		    /* scan through the modes in the sort order above */
1878		    if ((p->type & type) != type)
1879			continue;
1880		    if (p->HDisplay > vx && p->VDisplay > vy) {
1881			vx = p->HDisplay;
1882			vy = p->VDisplay;
1883		    }
1884		}
1885		if (vx && vy)
1886		    /* Found one */
1887		    break;
1888	    }
1889	    xf86DrvMsg(scrp->scrnIndex, X_WARNING,
1890		       "Shrinking virtual size estimate from %dx%d to %dx%d\n",
1891		       virtX, virtY, vx, vy);
1892	    virtX = _VIRTUALX(vx);
1893	    virtY = vy;
1894	    for (p = scrp->modes; p; p = p->next) {
1895		if (numModes > 0) {
1896		    if (p->HDisplay > virtX)
1897			p->status = MODE_VIRTUAL_X;
1898		    if (p->VDisplay > virtY)
1899			p->status = MODE_VIRTUAL_Y;
1900		    if (p->status != MODE_OK) {
1901			numModes--;
1902			printModeRejectMessage(scrp->scrnIndex, p, p->status);
1903		    }
1904		}
1905	    }
1906	    if (linePitches != NULL) {
1907		for (i = 0; linePitches[i] != 0; i++) {
1908		    if ((linePitches[i] >= virtX) &&
1909			(linePitches[i] ==
1910			scanLineWidth(virtX, virtY, linePitches[i],
1911				      apertureSize, BankFormat, pitchInc))) {
1912			linePitch = linePitches[i];
1913			break;
1914		    }
1915		}
1916	    } else {
1917		linePitch = scanLineWidth(virtX, virtY, minPitch,
1918					  apertureSize, BankFormat, pitchInc);
1919	    }
1920	}
1921    }
1922
1923    /* Update the ScrnInfoRec parameters */
1924
1925    scrp->virtualX = virtX;
1926    scrp->virtualY = virtY;
1927    scrp->displayWidth = linePitch;
1928
1929    if (numModes <= 0)
1930	return 0;
1931
1932    /* Make the mode list into a circular list by joining up the ends */
1933    p = scrp->modes;
1934    while (p->next != NULL)
1935	p = p->next;
1936    /* p is now the last mode on the list */
1937    p->next = scrp->modes;
1938    scrp->modes->prev = p;
1939
1940    if (minHeight > 0 && virtY < minHeight) {
1941	xf86DrvMsg(scrp->scrnIndex, X_ERROR,
1942		   "Virtual height (%d) is too small for the hardware "
1943		   "(min %d)\n", virtY, minHeight);
1944	return -1;
1945    }
1946
1947    return numModes;
1948}
1949
1950/*
1951 * xf86DeleteMode
1952 *
1953 * This function removes a mode from a list of modes.
1954 *
1955 * There are different types of mode lists:
1956 *
1957 *  - singly linked linear lists, ending in NULL
1958 *  - doubly linked linear lists, starting and ending in NULL
1959 *  - doubly linked circular lists
1960 *
1961 */
1962
1963void
1964xf86DeleteMode(DisplayModePtr *modeList, DisplayModePtr mode)
1965{
1966    /* Catch the easy/insane cases */
1967    if (modeList == NULL || *modeList == NULL || mode == NULL)
1968	return;
1969
1970    /* If the mode is at the start of the list, move the start of the list */
1971    if (*modeList == mode)
1972	*modeList = mode->next;
1973
1974    /* If mode is the only one on the list, set the list to NULL */
1975    if ((mode == mode->prev) && (mode == mode->next)) {
1976	*modeList = NULL;
1977    } else {
1978	if ((mode->prev != NULL) && (mode->prev->next == mode))
1979	    mode->prev->next = mode->next;
1980	if ((mode->next != NULL) && (mode->next->prev == mode))
1981	    mode->next->prev = mode->prev;
1982    }
1983
1984    free(mode->name);
1985    free(mode);
1986}
1987
1988/*
1989 * xf86PruneDriverModes
1990 *
1991 * Remove modes from the driver's mode list which have been marked as
1992 * invalid.
1993 */
1994
1995void
1996xf86PruneDriverModes(ScrnInfoPtr scrp)
1997{
1998    DisplayModePtr first, p, n;
1999
2000    p = scrp->modes;
2001    if (p == NULL)
2002	return;
2003
2004    do {
2005	if (!(first = scrp->modes))
2006	    return;
2007	n = p->next;
2008	if (p->status != MODE_OK) {
2009	    xf86DeleteMode(&(scrp->modes), p);
2010	}
2011	p = n;
2012    } while (p != NULL && p != first);
2013
2014    /* modePool is no longer needed, turf it */
2015    while (scrp->modePool) {
2016	/*
2017	 * A modePool mode's prev field is used to hold a pointer to the
2018	 * member of the scrp->modes list for which a match was considered.
2019	 * Clear that pointer first, otherwise xf86DeleteMode might get
2020	 * confused
2021	 */
2022	scrp->modePool->prev = NULL;
2023	xf86DeleteMode(&scrp->modePool, scrp->modePool);
2024    }
2025}
2026
2027
2028/*
2029 * xf86SetCrtcForModes
2030 *
2031 * Goes through the screen's mode list, and initialises the Crtc
2032 * parameters for each mode.  The initialisation includes adjustments
2033 * for interlaced and double scan modes.
2034 */
2035void
2036xf86SetCrtcForModes(ScrnInfoPtr scrp, int adjustFlags)
2037{
2038    DisplayModePtr p;
2039
2040    /*
2041     * Store adjustFlags for use with the VidMode extension. There is an
2042     * implicit assumption here that SetCrtcForModes is called once.
2043     */
2044    scrp->adjustFlags = adjustFlags;
2045
2046    p = scrp->modes;
2047    if (p == NULL)
2048	return;
2049
2050    do {
2051	xf86SetModeCrtc(p, adjustFlags);
2052	DebugF("%sMode %s: %d (%d) %d %d (%d) %d %d (%d) %d %d (%d) %d\n",
2053	       (p->type & M_T_DEFAULT) ? "Default " : "",
2054	       p->name, p->CrtcHDisplay, p->CrtcHBlankStart,
2055	       p->CrtcHSyncStart, p->CrtcHSyncEnd, p->CrtcHBlankEnd,
2056	       p->CrtcHTotal, p->CrtcVDisplay, p->CrtcVBlankStart,
2057	       p->CrtcVSyncStart, p->CrtcVSyncEnd, p->CrtcVBlankEnd,
2058	       p->CrtcVTotal);
2059	p = p->next;
2060    } while (p != NULL && p != scrp->modes);
2061}
2062
2063void
2064xf86PrintModes(ScrnInfoPtr scrp)
2065{
2066    DisplayModePtr p;
2067    float hsync, refresh = 0;
2068    char *desc, *desc2, *prefix, *uprefix;
2069
2070    if (scrp == NULL)
2071	return;
2072
2073    xf86DrvMsg(scrp->scrnIndex, scrp->virtualFrom, "Virtual size is %dx%d "
2074	       "(pitch %d)\n", scrp->virtualX, scrp->virtualY,
2075	       scrp->displayWidth);
2076
2077    p = scrp->modes;
2078    if (p == NULL)
2079	return;
2080
2081    do {
2082	desc = desc2 = "";
2083	hsync = xf86ModeHSync(p);
2084	refresh = xf86ModeVRefresh(p);
2085	if (p->Flags & V_INTERLACE) {
2086	    desc = " (I)";
2087	}
2088	if (p->Flags & V_DBLSCAN) {
2089	    desc = " (D)";
2090	}
2091	if (p->VScan > 1) {
2092	    desc2 = " (VScan)";
2093	}
2094	if (p->type & M_T_BUILTIN)
2095	    prefix = "Built-in mode";
2096	else if (p->type & M_T_DEFAULT)
2097	    prefix = "Default mode";
2098	else if (p->type & M_T_DRIVER)
2099	    prefix = "Driver mode";
2100	else
2101	    prefix = "Mode";
2102	if (p->type & M_T_USERDEF)
2103	    uprefix = "*";
2104	else
2105	    uprefix = " ";
2106	if (hsync == 0 || refresh == 0) {
2107	    if (p->name)
2108		xf86DrvMsg(scrp->scrnIndex, X_CONFIG,
2109			   "%s%s \"%s\"\n", uprefix, prefix, p->name);
2110	    else
2111		xf86DrvMsg(scrp->scrnIndex, X_PROBED,
2112			   "%s%s %dx%d (unnamed)\n",
2113			   uprefix, prefix, p->HDisplay, p->VDisplay);
2114	} else if (p->Clock == p->SynthClock) {
2115	    xf86DrvMsg(scrp->scrnIndex, X_CONFIG,
2116			"%s%s \"%s\": %.1f MHz, %.1f kHz, %.1f Hz%s%s\n",
2117			uprefix, prefix, p->name, p->Clock / 1000.0,
2118			hsync, refresh, desc, desc2);
2119	} else {
2120	    xf86DrvMsg(scrp->scrnIndex, X_CONFIG,
2121			"%s%s \"%s\": %.1f MHz (scaled from %.1f MHz), "
2122			"%.1f kHz, %.1f Hz%s%s\n",
2123			uprefix, prefix, p->name, p->Clock / 1000.0,
2124			p->SynthClock / 1000.0, hsync, refresh, desc, desc2);
2125	}
2126	if (hsync != 0 && refresh != 0)
2127	    xf86PrintModeline(scrp->scrnIndex,p);
2128	p = p->next;
2129    } while (p != NULL && p != scrp->modes);
2130}
2131