[patch] [media] tw686x: off by one bugs in tw686x_fields_map()

[patch] [media] tw686x: off by one bugs in tw686x_fields_map()

[Dan Carpenter]

The > ARRAY_SIZE() should be >= ARRAY_SIZE().  Also this is a slightly
unrelated cleanup but I replaced the magic numbers 30 and 25 with
ARRAY_SIZE() - 1.

Fixes: 363d79f1d5bd ('[media] tw686x: Don't go past array')
Signed-off-by: Dan Carpenter <dan.carpenter@oracle.com>

diff --git a/drivers/media/pci/tw686x/tw686x-video.c b/drivers/media/pci/tw686x/tw686x-video.c
index d2a0147..7b87f27 100644
--- a/drivers/media/pci/tw686x/tw686x-video.c
+++ b/drivers/media/pci/tw686x/tw686x-video.c
@@ -64,12 +64,12 @@ static unsigned int tw686x_fields_map(v4l2_std_id std, unsigned int fps)
 	unsigned int i;
 
 	if (std & V4L2_STD_525_60) {
-		if (fps > ARRAY_SIZE(std_525_60))
-			fps = 30;
+		if (fps >= ARRAY_SIZE(std_525_60))
+			fps = ARRAY_SIZE(std_525_60) - 1;
 		i = std_525_60[fps];
 	} else {
-		if (fps > ARRAY_SIZE(std_625_50))
-			fps = 25;
+		if (fps >= ARRAY_SIZE(std_625_50))
+			fps = ARRAY_SIZE(std_625_50) - 1;
 		i = std_625_50[fps];
 	}
 

Re: [patch] [media] tw686x: off by one bugs in tw686x_fields_map()

[Mauro Carvalho Chehab]

Hi Dan,

Em Wed, 27 Apr 2016 11:09:28 +0300
Dan Carpenter <dan.carpenter@oracle.com> escreveu:

> The > ARRAY_SIZE() should be >= ARRAY_SIZE(). 

I actually did this fix when I produced the patch, just I forgot to fold
it when merging. Anyway, this was fixed upstream by this patch:
	https://git.linuxtv.org/media_tree.git/commit/?id=45c175c4ae9695d6d2f30a45ab7f3866cfac184b

> Also this is a slightly
> unrelated cleanup but I replaced the magic numbers 30 and 25 with
> ARRAY_SIZE() - 1.

I don't like magic numbers, but, in this very specific case, setting
frames per second (fps) var to 25 or 30 makes much more sense. The
rationale is that:

The V4L2_STD_525_60 macro is for the Countries where the power line 
uses 60Hz, and V4L2_STD_625_50 for the Countries where the power line
is 50Hz.

The broadcast TV sends frames in half of this frequency, so, for
V4L2_STD_525_60, fps = 30, while, for V4L2_STD_625_50, fps = 25.

So, in this very specific case, IMHO, it is better to see 25 or 30 there,
instead of ARRAY_SIZE().

That's said, I guess one improvement would be to get rid of those two
arrays and replacing them by a formula, like:

               	i = (max_fps / 2 + 15 * fps) / max_fps;
                if (i > 14)
                        i = 0;

I'll propose such patch for evaluation.

Regards,
Mauro

> 
> Fixes: 363d79f1d5bd ('[media] tw686x: Don't go past array')
> Signed-off-by: Dan Carpenter <dan.carpenter@oracle.com>
> 
> diff --git a/drivers/media/pci/tw686x/tw686x-video.c b/drivers/media/pci/tw686x/tw686x-video.c
> index d2a0147..7b87f27 100644
> --- a/drivers/media/pci/tw686x/tw686x-video.c
> +++ b/drivers/media/pci/tw686x/tw686x-video.c
> @@ -64,12 +64,12 @@ static unsigned int tw686x_fields_map(v4l2_std_id std, unsigned int fps)
>  	unsigned int i;
>  
>  	if (std & V4L2_STD_525_60) {
> -		if (fps > ARRAY_SIZE(std_525_60))
> -			fps = 30;
> +		if (fps >= ARRAY_SIZE(std_525_60))
> +			fps = ARRAY_SIZE(std_525_60) - 1;
>  		i = std_525_60[fps];
>  	} else {
> -		if (fps > ARRAY_SIZE(std_625_50))
> -			fps = 25;
> +		if (fps >= ARRAY_SIZE(std_625_50))
> +			fps = ARRAY_SIZE(std_625_50) - 1;
>  		i = std_625_50[fps];
>  	}
>  


-- 
Thanks,
Mauro

Re: [patch] [media] tw686x: off by one bugs in tw686x_fields_map()

[Dan Carpenter]

On Wed, Apr 27, 2016 at 07:31:59AM -0300, Mauro Carvalho Chehab wrote:
> I don't like magic numbers, but, in this very specific case, setting
> frames per second (fps) var to 25 or 30 makes much more sense.

Fine fine.  I buy that rationale.

regards,
dan carpenter

Re: [patch] [media] tw686x: off by one bugs in tw686x_fields_map()

[Mauro Carvalho Chehab]

Em Wed, 27 Apr 2016 07:31:59 -0300
Mauro Carvalho Chehab <mchehab@osg.samsung.com> escreveu:

> Hi Dan,
> 
> Em Wed, 27 Apr 2016 11:09:28 +0300
> Dan Carpenter <dan.carpenter@oracle.com> escreveu:
> 
> > The > ARRAY_SIZE() should be >= ARRAY_SIZE(). 
> 
> I actually did this fix when I produced the patch, just I forgot to fold
> it when merging. Anyway, this was fixed upstream by this patch:
> 	https://git.linuxtv.org/media_tree.git/commit/?id=45c175c4ae9695d6d2f30a45ab7f3866cfac184b
> 
> > Also this is a slightly
> > unrelated cleanup but I replaced the magic numbers 30 and 25 with
> > ARRAY_SIZE() - 1.
> 
> I don't like magic numbers, but, in this very specific case, setting
> frames per second (fps) var to 25 or 30 makes much more sense. The
> rationale is that:
> 
> The V4L2_STD_525_60 macro is for the Countries where the power line 
> uses 60Hz, and V4L2_STD_625_50 for the Countries where the power line
> is 50Hz.
> 
> The broadcast TV sends frames in half of this frequency, so, for
> V4L2_STD_525_60, fps = 30, while, for V4L2_STD_625_50, fps = 25.
> 
> So, in this very specific case, IMHO, it is better to see 25 or 30 there,
> instead of ARRAY_SIZE().
> 
> That's said, I guess one improvement would be to get rid of those two
> arrays and replacing them by a formula, like:
> 
>                	i = (max_fps / 2 + 15 * fps) / max_fps;
>                 if (i > 14)
>                         i = 0;
> 
> I'll propose such patch for evaluation.

I did some tests to check how that array was determined, using 
the enclosed program.

It seems that the table was generated using this formula:

               	i2 = (adjust + 15 * fps) / max_fps;
                if (fps && !i2)
                       	i2 = 1;
                if (i2 > 14)
                        i2 = 0;

Where adjust is given by:
	adjust = 12; /* actually, any value between 11 and 14 */

Using it, I got these results:


60 Hz
	    fps 0, i1=0, i2=0
	    fps 1, i1=1, i2=1
	    fps 2, i1=1, i2=1
	    fps 3, i1=1, i2=1
	    fps 4, i1=2, i2=2
	    fps 5, i1=2, i2=2
	    fps 6, i1=3, i2=3
	    fps 7, i1=3, i2=3
	    fps 8, i1=4, i2=4
	    fps 9, i1=4, i2=4
	    fps 10, i1=5, i2=5
	    fps 11, i1=5, i2=5
	    fps 12, i1=6, i2=6
	    fps 13, i1=6, i2=6
	    fps 14, i1=7, i2=7
	    fps 15, i1=7, i2=7
	    fps 16, i1=8, i2=8
	    fps 17, i1=8, i2=8
	    fps 18, i1=9, i2=9
	    fps 19, i1=9, i2=9
	    fps 20, i1=10, i2=10
	    fps 21, i1=10, i2=10
	    fps 22, i1=11, i2=11
	    fps 23, i1=11, i2=11
	    fps 24, i1=12, i2=12
	    fps 25, i1=12, i2=12
	    fps 26, i1=13, i2=13
	    fps 27, i1=13, i2=13
	    fps 28, i1=14, i2=14
	NOK fps 29, i1=0, i2=14
	    fps 30, i1=0, i2=0

50 Hz
	    fps 0, i1=0, i2=0
	    fps 1, i1=1, i2=1
	    fps 2, i1=1, i2=1
	    fps 3, i1=2, i2=2
	NOK fps 4, i1=3, i2=2
	    fps 5, i1=3, i2=3
	    fps 6, i1=4, i2=4
	    fps 7, i1=4, i2=4
	    fps 8, i1=5, i2=5
	    fps 9, i1=5, i2=5
	    fps 10, i1=6, i2=6
	    fps 11, i1=7, i2=7
	    fps 12, i1=7, i2=7
	    fps 13, i1=8, i2=8
	    fps 14, i1=8, i2=8
	    fps 15, i1=9, i2=9
	    fps 16, i1=10, i2=10
	    fps 17, i1=10, i2=10
	    fps 18, i1=11, i2=11
	    fps 19, i1=11, i2=11
	    fps 20, i1=12, i2=12
	    fps 21, i1=13, i2=13
	    fps 22, i1=13, i2=13
	    fps 23, i1=14, i2=14
	    fps 24, i1=14, i2=14
	    fps 25, i1=0, i2=0

IMHO, the two values that are different at the table are wrong ;)

I would also round to the closest number, with probably makes more
sense, and fits well at the API requirements.

The small program to test itis enclosed below. I'll send a patch
getting rid of those tables.

Regards,
Mauro

===

#include <stdio.h>

static const unsigned int std_625_50[26] = {
                0, 1, 1, 2,  3,  3,  4,  4,  5,  5,  6,  7,  7,
                   8, 8, 9, 10, 10, 11, 11, 12, 13, 13, 14, 14, 0
};

static const unsigned int std_525_60[31] = {
                0, 1, 1, 1, 2,  2,  3,  3,  4,  4,  5,  5,  6,  6, 7, 7,
                   8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 0, 0
};

void calc_fps(unsigned int max_fps)
{
	unsigned int i1, i2, fps, adjust;

//	adjust = max_fps / 2;
	adjust = 12; /* 11 a 14 */
	for (fps = 0; fps <= max_fps; fps++) {
		if (max_fps == 30)
			i1 = std_525_60[fps];
		else
			i1 = std_625_50[fps];

		i2 = (adjust + 15 * fps) / max_fps;
		if (fps && !i2)
			i2 = 1;
		if (i2 > 14)
			i2 = 0;

//if (i1 != i2)
		printf("\t%s fps %d, i1=%d, i2=%d\n",
			(i1 == i2)? "   " : "NOK",
			fps, i1, i2);
	}
}

void main(void)
{
	printf ("60 Hz\n");
	calc_fps(30);

	printf ("\n50 Hz\n");
	calc_fps(25);
}



-- 
Thanks,
Mauro

[PATCH] tw686x: use a formula instead of two tables for div

[Mauro Carvalho Chehab]

Instead of using two tables to estimate the temporal decimation
factor, use a formula. This allows to get the closest fps, with
sounds better than the current tables.

Compile-tested only.

Signed-off-by: Mauro Carvalho Chehab <mchehab@osg.samsung.com>
---
 drivers/media/pci/tw686x/tw686x-video.c | 34 ++++++++++++---------------------
 1 file changed, 12 insertions(+), 22 deletions(-)

diff --git a/drivers/media/pci/tw686x/tw686x-video.c b/drivers/media/pci/tw686x/tw686x-video.c
index 253e10823ba3..0210fa304e4c 100644
--- a/drivers/media/pci/tw686x/tw686x-video.c
+++ b/drivers/media/pci/tw686x/tw686x-video.c
@@ -50,28 +50,18 @@ static unsigned int tw686x_fields_map(v4l2_std_id std, unsigned int fps)
 		0x01041041, 0x01104411, 0x01111111, 0x04444445, 0x04511445,
 		0x05145145, 0x05151515, 0x05515455, 0x05551555, 0x05555555
 	};
-
-	static const unsigned int std_625_50[26] = {
-		0, 1, 1, 2,  3,  3,  4,  4,  5,  5,  6,  7,  7,
-		   8, 8, 9, 10, 10, 11, 11, 12, 13, 13, 14, 14, 0
-	};
-
-	static const unsigned int std_525_60[31] = {
-		0, 1, 1, 1, 2,  2,  3,  3,  4,  4,  5,  5,  6,  6, 7, 7,
-		   8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 0, 0
-	};
-
-	unsigned int i;
-
-	if (std & V4L2_STD_525_60) {
-		if (fps >= ARRAY_SIZE(std_525_60))
-			fps = 30;
-		i = std_525_60[fps];
-	} else {
-		if (fps >= ARRAY_SIZE(std_625_50))
-			fps = 25;
-		i = std_625_50[fps];
-	}
+	unsigned int i, max_fps;
+
+	if (std & V4L2_STD_525_60)
+		max_fps = 30;
+	else
+		max_fps = 25;
+
+	i = DIV_ROUND_CLOSEST(15 * fps, max_fps);
+	if (!i)
+		i = 1;	/* Min possible fps */
+	else if (i > 14)
+		i = 0;	/* fps = max_fps */
 
 	return map[i];
 }
-- 
2.5.5

Re: [PATCH] tw686x: use a formula instead of two tables for div

[Mauro Carvalho Chehab]

Hmm....

Em Wed, 27 Apr 2016 08:01:19 -0300
Mauro Carvalho Chehab <mchehab@osg.samsung.com> escreveu:

> Instead of using two tables to estimate the temporal decimation
> factor, use a formula. This allows to get the closest fps, with
> sounds better than the current tables.
> 
> Compile-tested only.

Please discard this patch. It is wrong.

I found the datasheet for this device at:
	http://www.starterkit.ru/html/doc/tw6869-ds.pdf

Based on what it is said on page 50, it seems that it doesn't use a
decimation filter, but, instead, it just discards some fields in
a way that the average fps will be reduced.

So, the actual frame rate is given by the number of enabled bits
that are written to VIDEO_FIELD_CTRL[vc->ch] and are at the
valid bitmask range, e. g:

index  0, map = 0x00000000, 30 fps (60Hz), 25 fps (50Hz), output all fields
index  1, map = 0x80000006, 2 fps (60Hz), 2 fps (50Hz)
index  2, map = 0x80018006, 4 fps (60Hz), 4 fps (50Hz)
index  3, map = 0x80618006, 6 fps (60Hz), 6 fps (50Hz)
index  4, map = 0x81818186, 8 fps (60Hz), 8 fps (50Hz)
index  5, map = 0x86186186, 10 fps (60Hz), 8 fps (50Hz)
index  6, map = 0x86619866, 12 fps (60Hz), 10 fps (50Hz)
index  7, map = 0x86666666, 14 fps (60Hz), 12 fps (50Hz)
index  8, map = 0x9999999e, 16 fps (60Hz), 14 fps (50Hz)
index  9, map = 0x99e6799e, 18 fps (60Hz), 16 fps (50Hz)
index 10, map = 0x9e79e79e, 20 fps (60Hz), 16 fps (50Hz)
index 11, map = 0x9e7e7e7e, 22 fps (60Hz), 18 fps (50Hz)
index 12, map = 0x9fe7f9fe, 24 fps (60Hz), 20 fps (50Hz)
index 13, map = 0x9ffe7ffe, 26 fps (60Hz), 22 fps (50Hz)
index 14, map = 0x9ffffffe, 28 fps (60Hz), 24 fps (50Hz)

This was done by using the enclosed program.

---

#include <stdio.h>

static const unsigned int map[15] = {
                0x00000000, 0x00000001, 0x00004001, 0x00104001, 0x00404041,
               	0x01041041, 0x01104411, 0x01111111, 0x04444445, 0x04511445,
                0x05145145, 0x05151515, 0x05515455, 0x05551555, 0x05555555
};

unsigned int count_bits(unsigned int bits, unsigned int max)
{
	unsigned int i, c= 0;

	for (i = 0; i < max; i++)
		if ((1 << i) & bits)
			c++;

	return c;
}

void calc_map(unsigned int i)
{
	unsigned int m, fps_30, fps_25;

	m = map[i] << 1;
	m |= m << 1;

	fps_30 = count_bits(m, 30);
	fps_25 = count_bits(m, 25);

	if (m)
		m |= 1 << 31;
	else {
		fps_30 = 30;
		fps_25 = 25;
	}

	printf("index %2i, map = 0x%08x, %d fps (60Hz), %d fps (50Hz)%s\n",
		i, m, fps_30, fps_25,
		i == 0 ? ", output all fields" : ""
		);
}

int main(void)
{
	unsigned int i;

	printf ("\nmap:\n");
	for (i = 0; i < 15; i++)
		calc_map(i);

	return 0;
}

[PATCH v2] [media] tw686x: cleanup the fps estimation code

[Mauro Carvalho Chehab]

There are some issues with the old code:
	1) it uses two static tables;
	2) some values for 50Hz standards are wrong;
	3) it doesn't store the real framerate.

This patch fixes the above issues.

Compile-tested only.

Signed-off-by: Mauro Carvalho Chehab <mchehab@osg.samsung.com>

---

PS.: With this patch, it should be easy to add support for
VIDIOC_G_PARM and VIDIOC_S_PARM, as vc->fps will now store the
real frame rate, with should be used when returning from those
functions.

 drivers/media/pci/tw686x/tw686x-video.c | 100 +++++++++++++++++++++++---------
 1 file changed, 73 insertions(+), 27 deletions(-)

diff --git a/drivers/media/pci/tw686x/tw686x-video.c b/drivers/media/pci/tw686x/tw686x-video.c
index 0210fa304e4c..b247a7b4ddd8 100644
--- a/drivers/media/pci/tw686x/tw686x-video.c
+++ b/drivers/media/pci/tw686x/tw686x-video.c
@@ -43,43 +43,89 @@ static const struct tw686x_format formats[] = {
 	}
 };
 
-static unsigned int tw686x_fields_map(v4l2_std_id std, unsigned int fps)
+static const unsigned int fps_map[15] = {
+	/*
+	 * bit 31 enables selecting the field control register
+	 * bits 0-29 are a bitmask with fields that will be output.
+	 * For NTSC (and PAL-M, PAL-60), all 30 bits are used.
+	 * For other PAL standards, only the first 25 bits are used.
+	 */
+	0x00000000, /* output all fields */
+	0x80000006, /* 2 fps (60Hz), 2 fps (50Hz) */
+	0x80018006, /* 4 fps (60Hz), 4 fps (50Hz) */
+	0x80618006, /* 6 fps (60Hz), 6 fps (50Hz) */
+	0x81818186, /* 8 fps (60Hz), 8 fps (50Hz) */
+	0x86186186, /* 10 fps (60Hz), 8 fps (50Hz) */
+	0x86619866, /* 12 fps (60Hz), 10 fps (50Hz) */
+	0x86666666, /* 14 fps (60Hz), 12 fps (50Hz) */
+	0x9999999e, /* 16 fps (60Hz), 14 fps (50Hz) */
+	0x99e6799e, /* 18 fps (60Hz), 16 fps (50Hz) */
+	0x9e79e79e, /* 20 fps (60Hz), 16 fps (50Hz) */
+	0x9e7e7e7e, /* 22 fps (60Hz), 18 fps (50Hz) */
+	0x9fe7f9fe, /* 24 fps (60Hz), 20 fps (50Hz) */
+	0x9ffe7ffe, /* 26 fps (60Hz), 22 fps (50Hz) */
+	0x9ffffffe, /* 28 fps (60Hz), 24 fps (50Hz) */
+};
+
+static unsigned int tw686x_real_fps(unsigned int index, unsigned int max_fps)
+{
+	unsigned int i, bits, c = 0;
+
+	if (!index || index >= ARRAY_SIZE(fps_map))
+		return max_fps;
+
+	bits = fps_map[index];
+	for (i = 0; i < max_fps; i++)
+		if ((1 << i) & bits)
+			c++;
+
+	return c;
+}
+
+static unsigned int tw686x_fps_idx(unsigned int fps, unsigned int max_fps)
 {
-	static const unsigned int map[15] = {
-		0x00000000, 0x00000001, 0x00004001, 0x00104001, 0x00404041,
-		0x01041041, 0x01104411, 0x01111111, 0x04444445, 0x04511445,
-		0x05145145, 0x05151515, 0x05515455, 0x05551555, 0x05555555
-	};
-	unsigned int i, max_fps;
-
-	if (std & V4L2_STD_525_60)
-		max_fps = 30;
-	else
-		max_fps = 25;
-
-	i = DIV_ROUND_CLOSEST(15 * fps, max_fps);
-	if (!i)
-		i = 1;	/* Min possible fps */
-	else if (i > 14)
-		i = 0;	/* fps = max_fps */
-
-	return map[i];
+	unsigned int idx, real_fps;
+	int delta;
+
+	/* First guess */
+	idx = (12 + 15 * fps) / max_fps;
+
+	/* Minimal possible framerate is 2 frames per second */
+	if (!idx)
+		return 1;
+
+	/* Check if the difference is bigger than abs(1) and adjust */
+	real_fps = tw686x_real_fps(idx, max_fps);
+	delta = real_fps - fps;
+	if (delta < -1)
+		idx++;
+	else if (delta > 1)
+		idx--;
+
+	/* Max framerate */
+	if (idx >= 15)
+		return 0;
+
+	return idx;
 }
 
 static void tw686x_set_framerate(struct tw686x_video_channel *vc,
 				 unsigned int fps)
 {
-	unsigned int map;
+	unsigned int i, max_fps;
 
 	if (vc->fps == fps)
 		return;
 
-	map = tw686x_fields_map(vc->video_standard, fps) << 1;
-	map |= map << 1;
-	if (map > 0)
-		map |= BIT(31);
-	reg_write(vc->dev, VIDEO_FIELD_CTRL[vc->ch], map);
-	vc->fps = fps;
+	if (vc->video_standard & V4L2_STD_525_60)
+		max_fps = 30;
+	else
+		max_fps = 25;
+
+	i = tw686x_fps_idx(fps, max_fps);
+
+	reg_write(vc->dev, VIDEO_FIELD_CTRL[vc->ch], fps_map[i]);
+	vc->fps = tw686x_real_fps(i, max_fps);
 }
 
 static const struct tw686x_format *format_by_fourcc(unsigned int fourcc)
-- 
2.5.5

[PATCH v3] tw686x: use a formula instead of two tables for div

[Mauro Carvalho Chehab]

Instead of using two tables to estimate the temporal decimation
factor, use a formula. This allows to get the closest fps, with
sounds better than the current tables.

Compile-tested only.

Signed-off-by: Mauro Carvalho Chehab <mchehab@osg.samsung.com>

[media] tw686x: cleanup the fps estimation code

There are some issues with the old code:
	1) it uses two static tables;
	2) some values for 50Hz standards are wrong;
	3) it doesn't store the real framerate.

This patch fixes the above issues.

Compile-tested only.

Signed-off-by: Mauro Carvalho Chehab <mchehab@osg.samsung.com>

-

v3: Patch v2 were actually a diff patch against PATCH v1. Fold the two patches in one.

PS.: With this patch, it should be easy to add support for
VIDIOC_G_PARM and VIDIOC_S_PARM, as vc->fps will now store the
real frame rate, with should be used when returning from those
functions.

---
 drivers/media/pci/tw686x/tw686x-video.c | 110 +++++++++++++++++++++-----------
 1 file changed, 73 insertions(+), 37 deletions(-)

diff --git a/drivers/media/pci/tw686x/tw686x-video.c b/drivers/media/pci/tw686x/tw686x-video.c
index 253e10823ba3..b247a7b4ddd8 100644
--- a/drivers/media/pci/tw686x/tw686x-video.c
+++ b/drivers/media/pci/tw686x/tw686x-video.c
@@ -43,53 +43,89 @@ static const struct tw686x_format formats[] = {
 	}
 };
 
-static unsigned int tw686x_fields_map(v4l2_std_id std, unsigned int fps)
+static const unsigned int fps_map[15] = {
+	/*
+	 * bit 31 enables selecting the field control register
+	 * bits 0-29 are a bitmask with fields that will be output.
+	 * For NTSC (and PAL-M, PAL-60), all 30 bits are used.
+	 * For other PAL standards, only the first 25 bits are used.
+	 */
+	0x00000000, /* output all fields */
+	0x80000006, /* 2 fps (60Hz), 2 fps (50Hz) */
+	0x80018006, /* 4 fps (60Hz), 4 fps (50Hz) */
+	0x80618006, /* 6 fps (60Hz), 6 fps (50Hz) */
+	0x81818186, /* 8 fps (60Hz), 8 fps (50Hz) */
+	0x86186186, /* 10 fps (60Hz), 8 fps (50Hz) */
+	0x86619866, /* 12 fps (60Hz), 10 fps (50Hz) */
+	0x86666666, /* 14 fps (60Hz), 12 fps (50Hz) */
+	0x9999999e, /* 16 fps (60Hz), 14 fps (50Hz) */
+	0x99e6799e, /* 18 fps (60Hz), 16 fps (50Hz) */
+	0x9e79e79e, /* 20 fps (60Hz), 16 fps (50Hz) */
+	0x9e7e7e7e, /* 22 fps (60Hz), 18 fps (50Hz) */
+	0x9fe7f9fe, /* 24 fps (60Hz), 20 fps (50Hz) */
+	0x9ffe7ffe, /* 26 fps (60Hz), 22 fps (50Hz) */
+	0x9ffffffe, /* 28 fps (60Hz), 24 fps (50Hz) */
+};
+
+static unsigned int tw686x_real_fps(unsigned int index, unsigned int max_fps)
+{
+	unsigned int i, bits, c = 0;
+
+	if (!index || index >= ARRAY_SIZE(fps_map))
+		return max_fps;
+
+	bits = fps_map[index];
+	for (i = 0; i < max_fps; i++)
+		if ((1 << i) & bits)
+			c++;
+
+	return c;
+}
+
+static unsigned int tw686x_fps_idx(unsigned int fps, unsigned int max_fps)
 {
-	static const unsigned int map[15] = {
-		0x00000000, 0x00000001, 0x00004001, 0x00104001, 0x00404041,
-		0x01041041, 0x01104411, 0x01111111, 0x04444445, 0x04511445,
-		0x05145145, 0x05151515, 0x05515455, 0x05551555, 0x05555555
-	};
-
-	static const unsigned int std_625_50[26] = {
-		0, 1, 1, 2,  3,  3,  4,  4,  5,  5,  6,  7,  7,
-		   8, 8, 9, 10, 10, 11, 11, 12, 13, 13, 14, 14, 0
-	};
-
-	static const unsigned int std_525_60[31] = {
-		0, 1, 1, 1, 2,  2,  3,  3,  4,  4,  5,  5,  6,  6, 7, 7,
-		   8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 0, 0
-	};
-
-	unsigned int i;
-
-	if (std & V4L2_STD_525_60) {
-		if (fps >= ARRAY_SIZE(std_525_60))
-			fps = 30;
-		i = std_525_60[fps];
-	} else {
-		if (fps >= ARRAY_SIZE(std_625_50))
-			fps = 25;
-		i = std_625_50[fps];
-	}
-
-	return map[i];
+	unsigned int idx, real_fps;
+	int delta;
+
+	/* First guess */
+	idx = (12 + 15 * fps) / max_fps;
+
+	/* Minimal possible framerate is 2 frames per second */
+	if (!idx)
+		return 1;
+
+	/* Check if the difference is bigger than abs(1) and adjust */
+	real_fps = tw686x_real_fps(idx, max_fps);
+	delta = real_fps - fps;
+	if (delta < -1)
+		idx++;
+	else if (delta > 1)
+		idx--;
+
+	/* Max framerate */
+	if (idx >= 15)
+		return 0;
+
+	return idx;
 }
 
 static void tw686x_set_framerate(struct tw686x_video_channel *vc,
 				 unsigned int fps)
 {
-	unsigned int map;
+	unsigned int i, max_fps;
 
 	if (vc->fps == fps)
 		return;
 
-	map = tw686x_fields_map(vc->video_standard, fps) << 1;
-	map |= map << 1;
-	if (map > 0)
-		map |= BIT(31);
-	reg_write(vc->dev, VIDEO_FIELD_CTRL[vc->ch], map);
-	vc->fps = fps;
+	if (vc->video_standard & V4L2_STD_525_60)
+		max_fps = 30;
+	else
+		max_fps = 25;
+
+	i = tw686x_fps_idx(fps, max_fps);
+
+	reg_write(vc->dev, VIDEO_FIELD_CTRL[vc->ch], fps_map[i]);
+	vc->fps = tw686x_real_fps(i, max_fps);
 }
 
 static const struct tw686x_format *format_by_fourcc(unsigned int fourcc)
-- 
2.5.5

Re: [PATCH v3] tw686x: use a formula instead of two tables for div

[Ezequiel Garcia]

Hi Mauro,

Thanks a lot for the patch.

On 27 April 2016 at 12:27, Mauro Carvalho Chehab
<mchehab@osg.samsung.com> wrote:
> Instead of using two tables to estimate the temporal decimation
> factor, use a formula. This allows to get the closest fps, with
> sounds better than the current tables.
>
> Compile-tested only.
>
> Signed-off-by: Mauro Carvalho Chehab <mchehab@osg.samsung.com>
>
> [media] tw686x: cleanup the fps estimation code
>
> There are some issues with the old code:
>         1) it uses two static tables;
>         2) some values for 50Hz standards are wrong;
>         3) it doesn't store the real framerate.
>
> This patch fixes the above issues.
>
> Compile-tested only.
>
> Signed-off-by: Mauro Carvalho Chehab <mchehab@osg.samsung.com>
>
> -
>
> v3: Patch v2 were actually a diff patch against PATCH v1. Fold the two patches in one.
>
> PS.: With this patch, it should be easy to add support for
> VIDIOC_G_PARM and VIDIOC_S_PARM, as vc->fps will now store the
> real frame rate, with should be used when returning from those
> functions.
>
> ---
>  drivers/media/pci/tw686x/tw686x-video.c | 110 +++++++++++++++++++++-----------
>  1 file changed, 73 insertions(+), 37 deletions(-)
>
> diff --git a/drivers/media/pci/tw686x/tw686x-video.c b/drivers/media/pci/tw686x/tw686x-video.c
> index 253e10823ba3..b247a7b4ddd8 100644
> --- a/drivers/media/pci/tw686x/tw686x-video.c
> +++ b/drivers/media/pci/tw686x/tw686x-video.c
> @@ -43,53 +43,89 @@ static const struct tw686x_format formats[] = {
>         }
>  };
>
> -static unsigned int tw686x_fields_map(v4l2_std_id std, unsigned int fps)
> +static const unsigned int fps_map[15] = {
> +       /*
> +        * bit 31 enables selecting the field control register
> +        * bits 0-29 are a bitmask with fields that will be output.
> +        * For NTSC (and PAL-M, PAL-60), all 30 bits are used.
> +        * For other PAL standards, only the first 25 bits are used.
> +        */

I ran a few tests and it worked perfectly fine for 60Hz standards.
For 50Hz standards, or at least for PAL-Nc, it didn't
work so well, and the real FPS was too different from the requested
one. I need to look into it some more.

> +       0x00000000, /* output all fields */
> +       0x80000006, /* 2 fps (60Hz), 2 fps (50Hz) */
> +       0x80018006, /* 4 fps (60Hz), 4 fps (50Hz) */
> +       0x80618006, /* 6 fps (60Hz), 6 fps (50Hz) */
> +       0x81818186, /* 8 fps (60Hz), 8 fps (50Hz) */
> +       0x86186186, /* 10 fps (60Hz), 8 fps (50Hz) */
> +       0x86619866, /* 12 fps (60Hz), 10 fps (50Hz) */
> +       0x86666666, /* 14 fps (60Hz), 12 fps (50Hz) */
> +       0x9999999e, /* 16 fps (60Hz), 14 fps (50Hz) */
> +       0x99e6799e, /* 18 fps (60Hz), 16 fps (50Hz) */
> +       0x9e79e79e, /* 20 fps (60Hz), 16 fps (50Hz) */
> +       0x9e7e7e7e, /* 22 fps (60Hz), 18 fps (50Hz) */
> +       0x9fe7f9fe, /* 24 fps (60Hz), 20 fps (50Hz) */
> +       0x9ffe7ffe, /* 26 fps (60Hz), 22 fps (50Hz) */
> +       0x9ffffffe, /* 28 fps (60Hz), 24 fps (50Hz) */

Why this particular selection of fps values and bits set in each case?
Is it arbitrary?

> +};
> +
> +static unsigned int tw686x_real_fps(unsigned int index, unsigned int max_fps)
> +{
> +       unsigned int i, bits, c = 0;
> +
> +       if (!index || index >= ARRAY_SIZE(fps_map))
> +               return max_fps;
> +
> +       bits = fps_map[index];
> +       for (i = 0; i < max_fps; i++)
> +               if ((1 << i) & bits)
> +                       c++;
> +

We can use hweight_long here to count the number of bits set.
If you are OK with it, I can rework the patch and submit a new version.
-- 
Ezequiel García, VanguardiaSur
www.vanguardiasur.com.ar

Re: [PATCH v3] tw686x: use a formula instead of two tables for div

[Mauro Carvalho Chehab]

Em Mon, 27 Jun 2016 12:45:38 -0300
Ezequiel Garcia <ezequiel@vanguardiasur.com.ar> escreveu:

> Hi Mauro,
> 
> Thanks a lot for the patch.
> 
> On 27 April 2016 at 12:27, Mauro Carvalho Chehab
> <mchehab@osg.samsung.com> wrote:
> > Instead of using two tables to estimate the temporal decimation
> > factor, use a formula. This allows to get the closest fps, with
> > sounds better than the current tables.
> >
> > Compile-tested only.
> >
> > Signed-off-by: Mauro Carvalho Chehab <mchehab@osg.samsung.com>
> >
> > [media] tw686x: cleanup the fps estimation code
> >
> > There are some issues with the old code:
> >         1) it uses two static tables;
> >         2) some values for 50Hz standards are wrong;
> >         3) it doesn't store the real framerate.
> >
> > This patch fixes the above issues.
> >
> > Compile-tested only.
> >
> > Signed-off-by: Mauro Carvalho Chehab <mchehab@osg.samsung.com>
> >
> > -
> >
> > v3: Patch v2 were actually a diff patch against PATCH v1. Fold the two patches in one.
> >
> > PS.: With this patch, it should be easy to add support for
> > VIDIOC_G_PARM and VIDIOC_S_PARM, as vc->fps will now store the
> > real frame rate, with should be used when returning from those
> > functions.
> >
> > ---
> >  drivers/media/pci/tw686x/tw686x-video.c | 110 +++++++++++++++++++++-----------
> >  1 file changed, 73 insertions(+), 37 deletions(-)
> >
> > diff --git a/drivers/media/pci/tw686x/tw686x-video.c b/drivers/media/pci/tw686x/tw686x-video.c
> > index 253e10823ba3..b247a7b4ddd8 100644
> > --- a/drivers/media/pci/tw686x/tw686x-video.c
> > +++ b/drivers/media/pci/tw686x/tw686x-video.c
> > @@ -43,53 +43,89 @@ static const struct tw686x_format formats[] = {
> >         }
> >  };
> >
> > -static unsigned int tw686x_fields_map(v4l2_std_id std, unsigned int fps)
> > +static const unsigned int fps_map[15] = {
> > +       /*
> > +        * bit 31 enables selecting the field control register
> > +        * bits 0-29 are a bitmask with fields that will be output.
> > +        * For NTSC (and PAL-M, PAL-60), all 30 bits are used.
> > +        * For other PAL standards, only the first 25 bits are used.
> > +        */  
> 
> I ran a few tests and it worked perfectly fine for 60Hz standards.

Good!

> For 50Hz standards, or at least for PAL-Nc, it didn't
> work so well, and the real FPS was too different from the requested
> one. I need to look into it some more.

I would be expecting a maximum difference a little bigger than 1 Hz.

> > +       0x00000000, /* output all fields */
> > +       0x80000006, /* 2 fps (60Hz), 2 fps (50Hz) */
> > +       0x80018006, /* 4 fps (60Hz), 4 fps (50Hz) */
> > +       0x80618006, /* 6 fps (60Hz), 6 fps (50Hz) */
> > +       0x81818186, /* 8 fps (60Hz), 8 fps (50Hz) */
> > +       0x86186186, /* 10 fps (60Hz), 8 fps (50Hz) */
> > +       0x86619866, /* 12 fps (60Hz), 10 fps (50Hz) */
> > +       0x86666666, /* 14 fps (60Hz), 12 fps (50Hz) */
> > +       0x9999999e, /* 16 fps (60Hz), 14 fps (50Hz) */
> > +       0x99e6799e, /* 18 fps (60Hz), 16 fps (50Hz) */
> > +       0x9e79e79e, /* 20 fps (60Hz), 16 fps (50Hz) */
> > +       0x9e7e7e7e, /* 22 fps (60Hz), 18 fps (50Hz) */
> > +       0x9fe7f9fe, /* 24 fps (60Hz), 20 fps (50Hz) */
> > +       0x9ffe7ffe, /* 26 fps (60Hz), 22 fps (50Hz) */
> > +       0x9ffffffe, /* 28 fps (60Hz), 24 fps (50Hz) */  
> 
> Why this particular selection of fps values and bits set in each case?
> Is it arbitrary?

No. This is the same table that was already in the code:

static const unsigned int map[15] = {
                0x00000000, 0x00000001, 0x00004001, 0x00104001, 0x00404041,
                0x01041041, 0x01104411, 0x01111111, 0x04444445, 0x04511445,
                0x05145145, 0x05151515, 0x05515455, 0x05551555, 0x05555555
};

Except that the calculus that used to be there to set bit 31 to 1
on everything except map[0] and the code that makes it set two
FPS at the same time were pre-calculated, e. g. I run this code
locally to generate the new table:

	map = tw686x_fields_map(vc->video_standard, fps) << 1;
	map |= map << 1;
	if (map > 0)
		map |= BIT(31);

There, bit 31 = 0 disables the frame filtering. bit 31 = 1 enables it.

Each bit at the 0-29 bitrange means one of the 30 frames received.
If equal to 1, the frame is sent; if equal to 0, it is not sent.

So, the first value, for example: 0x80000006 has 2 consecutive
bits set, so the mean frame rate would be 2Hz. The next value there
is 0x0x80018006, with has 4 bits selected, so mean fps is 4Hz, and
so on.

As the original table always sets 2 consecutive frames at the same
time, I suspect that this is a requirement to avoid interlacing
issues.

So, the code I used to generate the table always allocate 2 consecutive
bits each time.

I suspect that such the table was built assuming that there are 30 bits,
but, on 50Hz, only 25 bits are used. So, it is sub-optimal for 50 Hz.
It means that the frames are not equally spaced.

If you want, I can construct a table for 50Hz that would produce better
results.

> 
> > +};
> > +
> > +static unsigned int tw686x_real_fps(unsigned int index, unsigned int max_fps)
> > +{
> > +       unsigned int i, bits, c = 0;
> > +
> > +       if (!index || index >= ARRAY_SIZE(fps_map))
> > +               return max_fps;
> > +
> > +       bits = fps_map[index];
> > +       for (i = 0; i < max_fps; i++)
> > +               if ((1 << i) & bits)
> > +                       c++;
> > +  
> 
> We can use hweight_long here to count the number of bits set.
> If you are OK with it, I can rework the patch and submit a new version.


-- 
Thanks,
Mauro

Re: [PATCH v3] tw686x: use a formula instead of two tables for div

[Ezequiel Garcia]

On 27 June 2016 at 14:38, Mauro Carvalho Chehab <mchehab@osg.samsung.com> wrote:
> Em Mon, 27 Jun 2016 12:45:38 -0300
> Ezequiel Garcia <ezequiel@vanguardiasur.com.ar> escreveu:
>
>> Hi Mauro,
>>
>> Thanks a lot for the patch.
>>
>> On 27 April 2016 at 12:27, Mauro Carvalho Chehab
>> <mchehab@osg.samsung.com> wrote:
>> > Instead of using two tables to estimate the temporal decimation
>> > factor, use a formula. This allows to get the closest fps, with
>> > sounds better than the current tables.
>> >
>> > Compile-tested only.
>> >
>> > Signed-off-by: Mauro Carvalho Chehab <mchehab@osg.samsung.com>
>> >
>> > [media] tw686x: cleanup the fps estimation code
>> >
>> > There are some issues with the old code:
>> >         1) it uses two static tables;
>> >         2) some values for 50Hz standards are wrong;
>> >         3) it doesn't store the real framerate.
>> >
>> > This patch fixes the above issues.
>> >
>> > Compile-tested only.
>> >
>> > Signed-off-by: Mauro Carvalho Chehab <mchehab@osg.samsung.com>
>> >
>> > -
>> >
>> > v3: Patch v2 were actually a diff patch against PATCH v1. Fold the two patches in one.
>> >
>> > PS.: With this patch, it should be easy to add support for
>> > VIDIOC_G_PARM and VIDIOC_S_PARM, as vc->fps will now store the
>> > real frame rate, with should be used when returning from those
>> > functions.
>> >
>> > ---
>> >  drivers/media/pci/tw686x/tw686x-video.c | 110 +++++++++++++++++++++-----------
>> >  1 file changed, 73 insertions(+), 37 deletions(-)
>> >
>> > diff --git a/drivers/media/pci/tw686x/tw686x-video.c b/drivers/media/pci/tw686x/tw686x-video.c
>> > index 253e10823ba3..b247a7b4ddd8 100644
>> > --- a/drivers/media/pci/tw686x/tw686x-video.c
>> > +++ b/drivers/media/pci/tw686x/tw686x-video.c
>> > @@ -43,53 +43,89 @@ static const struct tw686x_format formats[] = {
>> >         }
>> >  };
>> >
>> > -static unsigned int tw686x_fields_map(v4l2_std_id std, unsigned int fps)
>> > +static const unsigned int fps_map[15] = {
>> > +       /*
>> > +        * bit 31 enables selecting the field control register
>> > +        * bits 0-29 are a bitmask with fields that will be output.
>> > +        * For NTSC (and PAL-M, PAL-60), all 30 bits are used.
>> > +        * For other PAL standards, only the first 25 bits are used.
>> > +        */
>>
>> I ran a few tests and it worked perfectly fine for 60Hz standards.
>
> Good!
>
>> For 50Hz standards, or at least for PAL-Nc, it didn't
>> work so well, and the real FPS was too different from the requested
>> one. I need to look into it some more.
>
> I would be expecting a maximum difference a little bigger than 1 Hz.
>
>> > +       0x00000000, /* output all fields */
>> > +       0x80000006, /* 2 fps (60Hz), 2 fps (50Hz) */
>> > +       0x80018006, /* 4 fps (60Hz), 4 fps (50Hz) */
>> > +       0x80618006, /* 6 fps (60Hz), 6 fps (50Hz) */
>> > +       0x81818186, /* 8 fps (60Hz), 8 fps (50Hz) */
>> > +       0x86186186, /* 10 fps (60Hz), 8 fps (50Hz) */
>> > +       0x86619866, /* 12 fps (60Hz), 10 fps (50Hz) */
>> > +       0x86666666, /* 14 fps (60Hz), 12 fps (50Hz) */
>> > +       0x9999999e, /* 16 fps (60Hz), 14 fps (50Hz) */
>> > +       0x99e6799e, /* 18 fps (60Hz), 16 fps (50Hz) */
>> > +       0x9e79e79e, /* 20 fps (60Hz), 16 fps (50Hz) */
>> > +       0x9e7e7e7e, /* 22 fps (60Hz), 18 fps (50Hz) */
>> > +       0x9fe7f9fe, /* 24 fps (60Hz), 20 fps (50Hz) */
>> > +       0x9ffe7ffe, /* 26 fps (60Hz), 22 fps (50Hz) */
>> > +       0x9ffffffe, /* 28 fps (60Hz), 24 fps (50Hz) */
>>
>> Why this particular selection of fps values and bits set in each case?
>> Is it arbitrary?
>
> No. This is the same table that was already in the code:
>
> static const unsigned int map[15] = {
>                 0x00000000, 0x00000001, 0x00004001, 0x00104001, 0x00404041,
>                 0x01041041, 0x01104411, 0x01111111, 0x04444445, 0x04511445,
>                 0x05145145, 0x05151515, 0x05515455, 0x05551555, 0x05555555
> };
>
> Except that the calculus that used to be there to set bit 31 to 1
> on everything except map[0] and the code that makes it set two
> FPS at the same time were pre-calculated, e. g. I run this code
> locally to generate the new table:
>
>         map = tw686x_fields_map(vc->video_standard, fps) << 1;
>         map |= map << 1;
>         if (map > 0)
>                 map |= BIT(31);
>
> There, bit 31 = 0 disables the frame filtering. bit 31 = 1 enables it.
>
> Each bit at the 0-29 bitrange means one of the 30 frames received.
> If equal to 1, the frame is sent; if equal to 0, it is not sent.
>
> So, the first value, for example: 0x80000006 has 2 consecutive
> bits set, so the mean frame rate would be 2Hz. The next value there
> is 0x0x80018006, with has 4 bits selected, so mean fps is 4Hz, and
> so on.
>
> As the original table always sets 2 consecutive frames at the same
> time, I suspect that this is a requirement to avoid interlacing
> issues.
>
> So, the code I used to generate the table always allocate 2 consecutive
> bits each time.
>
> I suspect that such the table was built assuming that there are 30 bits,
> but, on 50Hz, only 25 bits are used. So, it is sub-optimal for 50 Hz.
> It means that the frames are not equally spaced.
>
> If you want, I can construct a table for 50Hz that would produce better
> results.
>

Actually, it's working fine on both 50Hz and 60Hz standards. I tested
PAL-Nc using my modifications, and I had an small error in the
hweight_long usage. My bad!

So... now I think it's working properly, for 50Hz the requested FPS matches
the actual FPS, and for 60Hz there's a slight difference:

* 24 FPS gives 23.50 FPS
* 22 FPS gives 21.66 FPS
* 20 FPS gives 20 FPS
* 10 FPS gives 10 FPS
* 6 FPS give 5 FPS
* 2 FPS gives 1.66 FPS

Output FPS values are those measured by qv4l2.
-- 
Ezequiel García, VanguardiaSur
www.vanguardiasur.com.ar

Re: [PATCH] tw686x: use a formula instead of two tables for div

[Mauro Carvalho Chehab]

Em Wed, 27 Apr 2016 09:00:49 -0300
Mauro Carvalho Chehab <mchehab@osg.samsung.com> escreveu:

> Hmm....
> 
> Em Wed, 27 Apr 2016 08:01:19 -0300
> Mauro Carvalho Chehab <mchehab@osg.samsung.com> escreveu:
> 
> > Instead of using two tables to estimate the temporal decimation
> > factor, use a formula. This allows to get the closest fps, with
> > sounds better than the current tables.
> > 
> > Compile-tested only.  
> 
> Please discard this patch. It is wrong.
> 
> I found the datasheet for this device at:
> 	http://www.starterkit.ru/html/doc/tw6869-ds.pdf
> 
> Based on what it is said on page 50, it seems that it doesn't use a
> decimation filter, but, instead, it just discards some fields in
> a way that the average fps will be reduced.
> 
> So, the actual frame rate is given by the number of enabled bits
> that are written to VIDEO_FIELD_CTRL[vc->ch]

Ok, I think I got this right this time. See the enclosed code.

It produces the fps register map, with each fps associated to
both 60Hz and 50Hz standard, plus it replaces the tables by a
calculus.

If my code is right, there are some values on the current tables
that are wrong.

See below. I'll submit an updated patch soon.

---
Program results:

FPS map:
	index  0, map = 0x00000000, 30 fps (60Hz), 25 fps (50Hz), output all fields
	index  1, map = 0x80000006, 2 fps (60Hz), 2 fps (50Hz)
	index  2, map = 0x80018006, 4 fps (60Hz), 4 fps (50Hz)
	index  3, map = 0x80618006, 6 fps (60Hz), 6 fps (50Hz)
	index  4, map = 0x81818186, 8 fps (60Hz), 8 fps (50Hz)
	index  5, map = 0x86186186, 10 fps (60Hz), 8 fps (50Hz)
	index  6, map = 0x86619866, 12 fps (60Hz), 10 fps (50Hz)
	index  7, map = 0x86666666, 14 fps (60Hz), 12 fps (50Hz)
	index  8, map = 0x9999999e, 16 fps (60Hz), 14 fps (50Hz)
	index  9, map = 0x99e6799e, 18 fps (60Hz), 16 fps (50Hz)
	index 10, map = 0x9e79e79e, 20 fps (60Hz), 16 fps (50Hz)
	index 11, map = 0x9e7e7e7e, 22 fps (60Hz), 18 fps (50Hz)
	index 12, map = 0x9fe7f9fe, 24 fps (60Hz), 20 fps (50Hz)
	index 13, map = 0x9ffe7ffe, 26 fps (60Hz), 22 fps (50Hz)
	index 14, map = 0x9ffffffe, 28 fps (60Hz), 24 fps (50Hz)

60 Hz
	Requested fps 0, table 0 (30 fps, delta 30), calculus 1 (2 fps, delta 2) DIFFERENT!
	Requested fps 1, table 1 (2 fps, delta 1), calculus 1 (2 fps, delta 1)
	Requested fps 2, table 1 (2 fps, delta 0), calculus 1 (2 fps, delta 0)
	Requested fps 3, table 1 (2 fps, delta -1), calculus 1 (2 fps, delta -1)
	Requested fps 4, table 2 (4 fps, delta 0), calculus 2 (4 fps, delta 0)
	Requested fps 5, table 2 (4 fps, delta -1), calculus 2 (4 fps, delta -1)
	Requested fps 6, table 3 (6 fps, delta 0), calculus 3 (6 fps, delta 0)
	Requested fps 7, table 3 (6 fps, delta -1), calculus 3 (6 fps, delta -1)
	Requested fps 8, table 4 (8 fps, delta 0), calculus 4 (8 fps, delta 0)
	Requested fps 9, table 4 (8 fps, delta -1), calculus 4 (8 fps, delta -1)
	Requested fps 10, table 5 (10 fps, delta 0), calculus 5 (10 fps, delta 0)
	Requested fps 11, table 5 (10 fps, delta -1), calculus 5 (10 fps, delta -1)
	Requested fps 12, table 6 (12 fps, delta 0), calculus 6 (12 fps, delta 0)
	Requested fps 13, table 6 (12 fps, delta -1), calculus 6 (12 fps, delta -1)
	Requested fps 14, table 7 (14 fps, delta 0), calculus 7 (14 fps, delta 0)
	Requested fps 15, table 7 (14 fps, delta -1), calculus 7 (14 fps, delta -1)
	Requested fps 16, table 8 (16 fps, delta 0), calculus 8 (16 fps, delta 0)
	Requested fps 17, table 8 (16 fps, delta -1), calculus 8 (16 fps, delta -1)
	Requested fps 18, table 9 (18 fps, delta 0), calculus 9 (18 fps, delta 0)
	Requested fps 19, table 9 (18 fps, delta -1), calculus 9 (18 fps, delta -1)
	Requested fps 20, table 10 (20 fps, delta 0), calculus 10 (20 fps, delta 0)
	Requested fps 21, table 10 (20 fps, delta -1), calculus 10 (20 fps, delta -1)
	Requested fps 22, table 11 (22 fps, delta 0), calculus 11 (22 fps, delta 0)
	Requested fps 23, table 11 (22 fps, delta -1), calculus 11 (22 fps, delta -1)
	Requested fps 24, table 12 (24 fps, delta 0), calculus 12 (24 fps, delta 0)
	Requested fps 25, table 12 (24 fps, delta -1), calculus 12 (24 fps, delta -1)
	Requested fps 26, table 13 (26 fps, delta 0), calculus 13 (26 fps, delta 0)
	Requested fps 27, table 13 (26 fps, delta -1), calculus 13 (26 fps, delta -1)
	Requested fps 28, table 14 (28 fps, delta 0), calculus 14 (28 fps, delta 0)
	Requested fps 29, table 0 (30 fps, delta 1), calculus 14 (28 fps, delta -1) DIFFERENT!
	Requested fps 30, table 0 (30 fps, delta 0), calculus 0 (30 fps, delta 0)

50 Hz
	Requested fps 0, table 0 (25 fps, delta 25), calculus 1 (2 fps, delta 2) DIFFERENT!
	Requested fps 1, table 1 (2 fps, delta 1), calculus 1 (2 fps, delta 1)
	Requested fps 2, table 1 (2 fps, delta 0), calculus 1 (2 fps, delta 0)
	Requested fps 3, table 2 (4 fps, delta 1), calculus 2 (4 fps, delta 1)
	Requested fps 4, table 3 (6 fps, delta 2), calculus 2 (4 fps, delta 0) DIFFERENT!
	Requested fps 5, table 3 (6 fps, delta 1), calculus 3 (6 fps, delta 1)
	Requested fps 6, table 4 (8 fps, delta 2), calculus 3 (6 fps, delta 0) DIFFERENT!
	Requested fps 7, table 4 (8 fps, delta 1), calculus 4 (8 fps, delta 1)
	Requested fps 8, table 5 (8 fps, delta 0), calculus 5 (8 fps, delta 0)
	Requested fps 9, table 5 (8 fps, delta -1), calculus 5 (8 fps, delta -1)
	Requested fps 10, table 6 (10 fps, delta 0), calculus 6 (10 fps, delta 0)
	Requested fps 11, table 7 (12 fps, delta 1), calculus 7 (12 fps, delta 1)
	Requested fps 12, table 7 (12 fps, delta 0), calculus 7 (12 fps, delta 0)
	Requested fps 13, table 8 (14 fps, delta 1), calculus 8 (14 fps, delta 1)
	Requested fps 14, table 8 (14 fps, delta 0), calculus 8 (14 fps, delta 0)
	Requested fps 15, table 9 (16 fps, delta 1), calculus 9 (16 fps, delta 1)
	Requested fps 16, table 10 (16 fps, delta 0), calculus 10 (16 fps, delta 0)
	Requested fps 17, table 10 (16 fps, delta -1), calculus 10 (16 fps, delta -1)
	Requested fps 18, table 11 (18 fps, delta 0), calculus 11 (18 fps, delta 0)
	Requested fps 19, table 11 (18 fps, delta -1), calculus 11 (18 fps, delta -1)
	Requested fps 20, table 12 (20 fps, delta 0), calculus 12 (20 fps, delta 0)
	Requested fps 21, table 13 (22 fps, delta 1), calculus 13 (22 fps, delta 1)
	Requested fps 22, table 13 (22 fps, delta 0), calculus 13 (22 fps, delta 0)
	Requested fps 23, table 14 (24 fps, delta 1), calculus 14 (24 fps, delta 1)
	Requested fps 24, table 14 (24 fps, delta 0), calculus 14 (24 fps, delta 0)
	Requested fps 25, table 0 (25 fps, delta 0), calculus 0 (25 fps, delta 0)

---

Program:

#include <stdio.h>

static const unsigned int std_625_50[26] = {
                0, 1, 1, 2,  3,  3,  4,  4,  5,  5,  6,  7,  7,
                   8, 8, 9, 10, 10, 11, 11, 12, 13, 13, 14, 14, 0
};

static const unsigned int std_525_60[31] = {
                0, 1, 1, 1, 2,  2,  3,  3,  4,  4,  5,  5,  6,  6, 7, 7,
                   8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 0, 0
};

static const unsigned int map[15] = {
                0x00000000, 0x00000001, 0x00004001, 0x00104001, 0x00404041,
               	0x01041041, 0x01104411, 0x01111111, 0x04444445, 0x04511445,
                0x05145145, 0x05151515, 0x05515455, 0x05551555, 0x05555555
};

unsigned int real_rate(unsigned int index, unsigned int max)
{
	unsigned int i, bits, c = 0;

	if (!index)
		return max;

	bits = map[index] << 1;
	bits |= bits << 1;

	for (i = 0; i < max; i++)
		if ((1 << i) & bits)
			c++;

	return c;
}

void calc_map(unsigned int i)
{
	unsigned int m, fps_30, fps_25;

	fps_30 = real_rate(i, 30);
	fps_25 = real_rate(i, 25);

	m = map[i] << 1;
	m |= m << 1;

	if (m)
		m |= 1 << 31;
	else {
		fps_30 = 30;
		fps_25 = 25;
	}

	printf("\tindex %2i, map = 0x%08x, %d fps (60Hz), %d fps (50Hz)%s\n",
		i, m, fps_30, fps_25,
		i == 0 ? ", output all fields" : ""
		);
}

unsigned int get_index(unsigned int fps, unsigned int max_fps)
{
	unsigned int idx, real_fps;
	int delta;

	if (real_fps == max_fps)
		return 0;

	if (fps < 2)
		return 1;

	/* First guess */
	idx = (12 + 15 * fps) / max_fps;

	/* Check if the difference is bigger than abs(1) and adjust */
	real_fps = real_rate(idx, max_fps);
	delta = real_fps - fps;
	if (delta < -1)
		idx++;
	else if (delta > 1)
		idx--;

	if (idx >= 15)
		return 0;

	return idx;
}


void calc_fps(unsigned int max_fps)
{
	unsigned int i1, i2, fps, adjust;
	unsigned int fps1, fps2;

	for (fps = 0; fps <= max_fps; fps++) {
		if (max_fps == 30)
			i1 = std_525_60[fps];
		else
			i1 = std_625_50[fps];

		i2 = get_index(fps, max_fps);

		fps1 = real_rate(i1, max_fps);
		fps2 = real_rate(i2, max_fps);

		printf("\tRequested fps %d, table %d (%d fps, delta %d), calculus %d (%d fps, delta %d)%s\n",
			fps,
			i1, fps1, fps1 - fps,
			i2, fps2, fps2 - fps,
			(i1 != i2) ? " DIFFERENT!": "");
	}
}

int main(void)
{
	unsigned int i;

	printf ("FPS map:\n");
	for (i = 0; i < 15; i++)
		calc_map(i);

	printf ("\n60 Hz\n");
	calc_fps(30);

	printf ("\n50 Hz\n");
	calc_fps(25);

	return 0;
}