/*
 * Copyright 1993-2003 NVIDIA, Corporation
 * Copyright 2007-2009 Stuart Bennett
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
 * THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF
 * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

#include <subdev/bios.h>
#include <subdev/bios/pll.h>

#include "pll.h"

static int
getMNP_single(struct nouveau_subdev *subdev, struct nvbios_pll *info, int clk,
	      int *pN, int *pM, int *pP)
{
	/* Find M, N and P for a single stage PLL
	 *
	 * Note that some bioses (NV3x) have lookup tables of precomputed MNP
	 * values, but we're too lazy to use those atm
	 *
	 * "clk" parameter in kHz
	 * returns calculated clock
	 */
	struct nouveau_bios *bios = nouveau_bios(subdev);
	int minvco = info->vco1.min_freq, maxvco = info->vco1.max_freq;
	int minM = info->vco1.min_m, maxM = info->vco1.max_m;
	int minN = info->vco1.min_n, maxN = info->vco1.max_n;
	int minU = info->vco1.min_inputfreq;
	int maxU = info->vco1.max_inputfreq;
	int minP = info->min_p;
	int maxP = info->max_p_usable;
	int crystal = info->refclk;
	int M, N, thisP, P;
	int clkP, calcclk;
	int delta, bestdelta = INT_MAX;
	int bestclk = 0;

	/* this division verified for nv20, nv18, nv28 (Haiku), and nv34 */
	/* possibly correlated with introduction of 27MHz crystal */
	if (bios->version.major < 0x60) {
		int cv = bios->version.chip;
		if (cv < 0x17 || cv == 0x1a || cv == 0x20) {
			if (clk > 250000)
				maxM = 6;
			if (clk > 340000)
				maxM = 2;
		} else if (cv < 0x40) {
			if (clk > 150000)
				maxM = 6;
			if (clk > 200000)
				maxM = 4;
			if (clk > 340000)
				maxM = 2;
		}
	}

	P = 1 << maxP;
	if ((clk * P) < minvco) {
		minvco = clk * maxP;
		maxvco = minvco * 2;
	}

	if (clk + clk/200 > maxvco)	/* +0.5% */
		maxvco = clk + clk/200;

	/* NV34 goes maxlog2P->0, NV20 goes 0->maxlog2P */
	for (thisP = minP; thisP <= maxP; thisP++) {
		P = 1 << thisP;
		clkP = clk * P;

		if (clkP < minvco)
			continue;
		if (clkP > maxvco)
			return bestclk;

		for (M = minM; M <= maxM; M++) {
			if (crystal/M < minU)
				return bestclk;
			if (crystal/M > maxU)
				continue;

			/* add crystal/2 to round better */
			N = (clkP * M + crystal/2) / crystal;

			if (N < minN)
				continue;
			if (N > maxN)
				break;

			/* more rounding additions */
			calcclk = ((N * crystal + P/2) / P + M/2) / M;
			delta = abs(calcclk - clk);
			/* we do an exhaustive search rather than terminating
			 * on an optimality condition...
			 */
			if (delta < bestdelta) {
				bestdelta = delta;
				bestclk = calcclk;
				*pN = N;
				*pM = M;
				*pP = thisP;
				if (delta == 0)	/* except this one */
					return bestclk;
			}
		}
	}

	return bestclk;
}

static int
getMNP_double(struct nouveau_subdev *subdev, struct nvbios_pll *info, int clk,
	      int *pN1, int *pM1, int *pN2, int *pM2, int *pP)
{
	/* Find M, N and P for a two stage PLL
	 *
	 * Note that some bioses (NV30+) have lookup tables of precomputed MNP
	 * values, but we're too lazy to use those atm
	 *
	 * "clk" parameter in kHz
	 * returns calculated clock
	 */
	int chip_version = nouveau_bios(subdev)->version.chip;
	int minvco1 = info->vco1.min_freq, maxvco1 = info->vco1.max_freq;
	int minvco2 = info->vco2.min_freq, maxvco2 = info->vco2.max_freq;
	int minU1 = info->vco1.min_inputfreq, minU2 = info->vco2.min_inputfreq;
	int maxU1 = info->vco1.max_inputfreq, maxU2 = info->vco2.max_inputfreq;
	int minM1 = info->vco1.min_m, maxM1 = info->vco1.max_m;
	int minN1 = info->vco1.min_n, maxN1 = info->vco1.max_n;
	int minM2 = info->vco2.min_m, maxM2 = info->vco2.max_m;
	int minN2 = info->vco2.min_n, maxN2 = info->vco2.max_n;
	int maxlog2P = info->max_p_usable;
	int crystal = info->refclk;
	bool fixedgain2 = (minM2 == maxM2 && minN2 == maxN2);
	int M1, N1, M2, N2, log2P;
	int clkP, calcclk1, calcclk2, calcclkout;
	int delta, bestdelta = INT_MAX;
	int bestclk = 0;

	int vco2 = (maxvco2 - maxvco2/200) / 2;
	for (log2P = 0; clk && log2P < maxlog2P && clk <= (vco2 >> log2P); log2P++)
		;
	clkP = clk << log2P;

	if (maxvco2 < clk + clk/200)	/* +0.5% */
		maxvco2 = clk + clk/200;

	for (M1 = minM1; M1 <= maxM1; M1++) {
		if (crystal/M1 < minU1)
			return bestclk;
		if (crystal/M1 > maxU1)
			continue;

		for (N1 = minN1; N1 <= maxN1; N1++) {
			calcclk1 = crystal * N1 / M1;
			if (calcclk1 < minvco1)
				continue;
			if (calcclk1 > maxvco1)
				break;

			for (M2 = minM2; M2 <= maxM2; M2++) {
				if (calcclk1/M2 < minU2)
					break;
				if (calcclk1/M2 > maxU2)
					continue;

				/* add calcclk1/2 to round better */
				N2 = (clkP * M2 + calcclk1/2) / calcclk1;
				if (N2 < minN2)
					continue;
				if (N2 > maxN2)
					break;

				if (!fixedgain2) {
					if (chip_version < 0x60)
						if (N2/M2 < 4 || N2/M2 > 10)
							continue;

					calcclk2 = calcclk1 * N2 / M2;
					if (calcclk2 < minvco2)
						break;
					if (calcclk2 > maxvco2)
						continue;
				} else
					calcclk2 = calcclk1;

				calcclkout = calcclk2 >> log2P;
				delta = abs(calcclkout - clk);
				/* we do an exhaustive search rather than terminating
				 * on an optimality condition...
				 */
				if (delta < bestdelta) {
					bestdelta = delta;
					bestclk = calcclkout;
					*pN1 = N1;
					*pM1 = M1;
					*pN2 = N2;
					*pM2 = M2;
					*pP = log2P;
					if (delta == 0)	/* except this one */
						return bestclk;
				}
			}
		}
	}

	return bestclk;
}

int
nv04_pll_calc(struct nouveau_subdev *subdev, struct nvbios_pll *info, u32 freq,
	      int *N1, int *M1, int *N2, int *M2, int *P)
{
	int ret;

	if (!info->vco2.max_freq || !N2) {
		ret = getMNP_single(subdev, info, freq, N1, M1, P);
		if (N2) {
			*N2 = 1;
			*M2 = 1;
		}
	} else {
		ret = getMNP_double(subdev, info, freq, N1, M1, N2, M2, P);
	}

	if (!ret)
		nv_error(subdev, "unable to compute acceptable pll values\n");
	return ret;
}