[PATCH 1/3] gspca pac7302/pac7311: simplify pac_find_sof

[PATCH 1/3] gspca pac7302/pac7311: simplify pac_find_sof

[Németh Márton]

From: Márton Németh <nm127@freemail.hu>

Remove struct sd dependency from pac_find_sof() function implementation.
This step prepares separation of pac7302 and pac7311 specific parts of
struct sd.

Signed-off-by: Márton Németh <nm127@freemail.hu>
Cc: Thomas Kaiser <thomas@kaiser-linux.li>
Cc: Theodore Kilgore <kilgota@auburn.edu>
Cc: Kyle Guinn <elyk03@gmail.com>
---
diff -uprN a/drivers/media/video/gspca/mr97310a.c b/drivers/media/video/gspca/mr97310a.c
--- a/drivers/media/video/gspca/mr97310a.c	2009-11-01 06:49:29.000000000 +0100
+++ b/drivers/media/video/gspca/mr97310a.c	2009-11-01 18:11:22.000000000 +0100
@@ -1034,9 +1034,10 @@ static void sd_pkt_scan(struct gspca_dev
 			__u8 *data,                   /* isoc packet */
 			int len)                      /* iso packet length */
 {
+	struct sd *sd = (struct sd *) gspca_dev;
 	unsigned char *sof;

-	sof = pac_find_sof(gspca_dev, data, len);
+	sof = pac_find_sof(&sd->sof_read, data, len);
 	if (sof) {
 		int n;

diff -uprN a/drivers/media/video/gspca/pac207.c b/drivers/media/video/gspca/pac207.c
--- a/drivers/media/video/gspca/pac207.c	2009-10-30 16:12:05.000000000 +0100
+++ b/drivers/media/video/gspca/pac207.c	2009-11-01 18:11:22.000000000 +0100
@@ -344,7 +344,7 @@ static void sd_pkt_scan(struct gspca_dev
 	struct sd *sd = (struct sd *) gspca_dev;
 	unsigned char *sof;

-	sof = pac_find_sof(gspca_dev, data, len);
+	sof = pac_find_sof(&sd->sof_read, data, len);
 	if (sof) {
 		int n;

diff -uprN a/drivers/media/video/gspca/pac7311.c b/drivers/media/video/gspca/pac7311.c
--- a/drivers/media/video/gspca/pac7311.c	2009-11-01 06:51:38.000000000 +0100
+++ b/drivers/media/video/gspca/pac7311.c	2009-11-01 18:11:22.000000000 +0100
@@ -852,7 +852,7 @@ static void sd_pkt_scan(struct gspca_dev
 	struct sd *sd = (struct sd *) gspca_dev;
 	unsigned char *sof;

-	sof = pac_find_sof(gspca_dev, data, len);
+	sof = pac_find_sof(&sd->sof_read, data, len);
 	if (sof) {
 		unsigned char tmpbuf[4];
 		int n, lum_offset, footer_length;
diff -uprN a/drivers/media/video/gspca/pac_common.h b/drivers/media/video/gspca/pac_common.h
--- a/drivers/media/video/gspca/pac_common.h	2009-10-30 16:12:05.000000000 +0100
+++ b/drivers/media/video/gspca/pac_common.h	2009-11-01 18:11:22.000000000 +0100
@@ -72,42 +72,41 @@ static const unsigned char pac_sof_marke
 	   +----------+
 */

-static unsigned char *pac_find_sof(struct gspca_dev *gspca_dev,
+static unsigned char *pac_find_sof(u8 *sof_read,
 					unsigned char *m, int len)
 {
-	struct sd *sd = (struct sd *) gspca_dev;
 	int i;

 	/* Search for the SOF marker (fixed part) in the header */
 	for (i = 0; i < len; i++) {
-		switch (sd->sof_read) {
+		switch (*sof_read) {
 		case 0:
 			if (m[i] == 0xff)
-				sd->sof_read = 1;
+				*sof_read = 1;
 			break;
 		case 1:
 			if (m[i] == 0xff)
-				sd->sof_read = 2;
+				*sof_read = 2;
 			else
-				sd->sof_read = 0;
+				*sof_read = 0;
 			break;
 		case 2:
 			switch (m[i]) {
 			case 0x00:
-				sd->sof_read = 3;
+				*sof_read = 3;
 				break;
 			case 0xff:
 				/* stay in this state */
 				break;
 			default:
-				sd->sof_read = 0;
+				*sof_read = 0;
 			}
 			break;
 		case 3:
 			if (m[i] == 0xff)
-				sd->sof_read = 4;
+				*sof_read = 4;
 			else
-				sd->sof_read = 0;
+				*sof_read = 0;
 			break;
 		case 4:
 			switch (m[i]) {
@@ -117,18 +116,18 @@ static unsigned char *pac_find_sof(struc
 					"SOF found, bytes to analyze: %u."
 					" Frame starts at byte #%u",
 					len, i + 1);
-				sd->sof_read = 0;
+				*sof_read = 0;
 				return m + i + 1;
 				break;
 			case 0xff:
-				sd->sof_read = 2;
+				*sof_read = 2;
 				break;
 			default:
-				sd->sof_read = 0;
+				*sof_read = 0;
 			}
 			break;
 		default:
-			sd->sof_read = 0;
+			*sof_read = 0;
 		}
 	}

Re: [PATCH 1/3] gspca pac7302/pac7311: simplify pac_find_sof

[Theodore Kilgore]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 2406 bytes --]



On Sun, 1 Nov 2009, Németh Márton wrote:

> From: Márton Németh <nm127@freemail.hu>
>
> Remove struct sd dependency from pac_find_sof() function implementation.
> This step prepares separation of pac7302 and pac7311 specific parts of
> struct sd.
>
> Signed-off-by: Márton Németh <nm127@freemail.hu>
> Cc: Thomas Kaiser <thomas@kaiser-linux.li>
> Cc: Theodore Kilgore <kilgota@auburn.edu>
> Cc: Kyle Guinn <elyk03@gmail.com>

<snip>

Szia Marton,

As long as these things work, I would not mind at all. But perhaps this is 
a good occasion to bring up an issue which seems to me very much related. 
It is the following:

Along with the (it seems to be never-ending) work on the mr97310a driver, 
I have been working on a driver for the sn9c2028 cameras. The driver at 
this point functions, and seems to function quite well. But it also seems 
to me that the code needs quite a bit of polishing before it is 
publicized. Since I have been very much preoccupied with finishing the 
mr97310a driver (why does the last 5% of a job sometimes take the most 
time?) this final polishing of the sn9c2028 driver has not yet occurred, 
sorry to say.

But here is the point. The sn9c2028 cameras have a structure which seems 
similar to the mr97310a cameras. They use a similar decompression 
algorithm. They have a similar frame header. Specifically, the sn9c2028 
frame header starts with the five bytes

                 0xff, 0xff, 0x00, 0xc4, 0xc4

whereas the pac_common frame header starts with the five bytes

                 0xff, 0xff, 0x00, 0xff, 0x96

Right now, for my own use, I have written a file sn9c2028.h which 
essentially duplicates the functionality of pac_common.h and contains a 
function which searches for the sn9c2028 SOF marker instead of searching 
for the pac SOF marker. Is this necessarily the good, permanent solution? 
I am not so sure about that.

Perhaps when making changes it is a good time to think over the idea of 
combining things which are in fact not very much different. After all, 
another set of cameras might come along, too, which essentially requires 
yet another minor variation on the same basic algorithm. Then we are 
supposed to have three .h files with three functions which have the same 
code and just search for slightly different strings?

I am well aware that you started out to do something different, but how 
does this strike you?


Theodore Kilgore

Re: [PATCH 1/3] gspca pac7302/pac7311: simplify pac_find_sof

[Németh Márton]

Theodore Kilgore wrote:
> 
> On Sun, 1 Nov 2009, Németh Márton wrote:
>> Remove struct sd dependency from pac_find_sof() function implementation.
>> This step prepares separation of pac7302 and pac7311 specific parts of
>> struct sd.
> [...]
> But here is the point. The sn9c2028 cameras have a structure which seems 
> similar to the mr97310a cameras. They use a similar decompression 
> algorithm. They have a similar frame header. Specifically, the sn9c2028 
> frame header starts with the five bytes
> 
>                  0xff, 0xff, 0x00, 0xc4, 0xc4
> 
> whereas the pac_common frame header starts with the five bytes
> 
>                  0xff, 0xff, 0x00, 0xff, 0x96
> 
> Right now, for my own use, I have written a file sn9c2028.h which 
> essentially duplicates the functionality of pac_common.h and contains a 
> function which searches for the sn9c2028 SOF marker instead of searching 
> for the pac SOF marker. Is this necessarily the good, permanent solution? 
> I am not so sure about that.

I think the pac_find_sof() is a special case. To find a SOF sequence in
a bigger buffer in general needs to first analyze the SOF sequence for
repeated bytes. If there are repeated bytes the search have to be
continued in a different way, see the state machine currently in the
pac_common.h. To find the sn9c2028 frame header a different state machine
is needed. It might be possible to implement a search function which
can find any SOF sequence but I am afraid that this algorithm would be
too complicated because of the search string analysis.

> Perhaps when making changes it is a good time to think over the idea of 
> combining things which are in fact not very much different. After all, 
> another set of cameras might come along, too, which essentially requires 
> yet another minor variation on the same basic algorithm. Then we are 
> supposed to have three .h files with three functions which have the same 
> code and just search for slightly different strings?
> 
> I am well aware that you started out to do something different, but how 
> does this strike you?

I was also thinking about not just duplicate the code but find functions
which are similar. My thinking was that first I try to separate the
pac7302 and pac7311 subdrivers and get feedback. If this change was
accepted I would look for common functions not only in pac7302 and pac7311
but also in the gspca family of subdrivers.

My first candidate would be the low level reg_w*() and reg_r*() functions.
I haven't finished the analysis but it seems that most of the time the
usb_control_msg() parameters are the same except the request and
requesttype parameter. The request contains a number specific to the
device. The requesttype usually contains USB_RECIP_DEVICE or
USB_RECIP_INTERFACE. This means that these function can be extracted
to a common helper module or to gspca_main and introduce the request
and requesttype values somehow to struct sd_desc in gspca.h.

Regards,

	Márton Németh

Re: [PATCH 1/3] gspca pac7302/pac7311: simplify pac_find_sof

[Theodore Kilgore]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 3988 bytes --]



On Mon, 2 Nov 2009, Németh Márton wrote:

> Theodore Kilgore wrote:
>>
>> On Sun, 1 Nov 2009, Németh Márton wrote:
>>> Remove struct sd dependency from pac_find_sof() function implementation.
>>> This step prepares separation of pac7302 and pac7311 specific parts of
>>> struct sd.
>> [...]
>> But here is the point. The sn9c2028 cameras have a structure which seems
>> similar to the mr97310a cameras. They use a similar decompression
>> algorithm. They have a similar frame header. Specifically, the sn9c2028
>> frame header starts with the five bytes
>>
>>                  0xff, 0xff, 0x00, 0xc4, 0xc4
>>
>> whereas the pac_common frame header starts with the five bytes
>>
>>                  0xff, 0xff, 0x00, 0xff, 0x96
>>
>> Right now, for my own use, I have written a file sn9c2028.h which
>> essentially duplicates the functionality of pac_common.h and contains a
>> function which searches for the sn9c2028 SOF marker instead of searching
>> for the pac SOF marker. Is this necessarily the good, permanent solution?
>> I am not so sure about that.
>
> I think the pac_find_sof() is a special case. To find a SOF sequence in
> a bigger buffer in general needs to first analyze the SOF sequence for
> repeated bytes. If there are repeated bytes the search have to be
> continued in a different way, see the state machine currently in the
> pac_common.h. To find the sn9c2028 frame header a different state machine
> is needed. It might be possible to implement a search function which
> can find any SOF sequence but I am afraid that this algorithm would be
> too complicated because of the search string analysis.

Well, I do not really know enough about this to be able to say something 
authoritative, but:

1. There is an obvious limitation on the length of the SOF marker. If it 
is agreed upon that the SOF marker is 5 bytes or less, then it ought not 
to be so terrible a thing to do. Namely, your state machine should accept 
an input, consisting of a pointer to the proper SOF marker and use that 
one instead of what is "hard wired" in your code. So, for example,

                 switch (sd->sof_read) {
                 case 0:
                         if (m[i] == 0xff)
                                 sd->sof_read = 1;
                         break;
                 case 1:
                         if (m[i] == 0xff)
                                 sd->sof_read = 2;
                         else
                                 sd->sof_read = 0;
                         break;
 			(and so on)

could read instead as

                 switch (sd->sof_read) {
                 case 0:
                         if (m[i] == sof_marker[0])
                                 sd->sof_read = 1;
                         break;
                 case 1:
                         if (m[i] == sof_marker[1])
                                 sd->sof_read = 2;
                         else
                                 sd->sof_read = 0;
                         break;
 			(and so on)


The problem would come if the SOF marker were six bytes long instead. The 
way to solve that would be to figure out what is the longest SOF marker 
that one wants to deal with, beforehand. I am not sure what is the 
prevailing number of bytes in such an SOF marker, or the maximum number. 
But it would be possible to prescribe some reasonable maximum number 
and take that into account, I think.

2. Although it seems to me it would not be a terribly big deal to code the 
above, there is the question whether it would significantly slow the 
algorithm down to be required to go and read the variable sof_marker[]. My 
instinct is that it would cost practically nothing to do that, but I am 
not the expert on such matters, which is why I put the disclaimer at the 
top. If somebody who knows what he is talking about says this idea causes 
a speed or timing problem, then forget about it. In that case it is better 
to have another function for every camera.

Theodore Kilgore

Re: [PATCH 1/3] gspca pac7302/pac7311: simplify pac_find_sof

[Németh Márton]

[-- Attachment #1: Type: text/plain, Size: 5278 bytes --]

Theodore Kilgore írta:
> 
> On Mon, 2 Nov 2009, Németh Márton wrote:
> 
>> Theodore Kilgore wrote:
>>> On Sun, 1 Nov 2009, Németh Márton wrote:
>>>> Remove struct sd dependency from pac_find_sof() function implementation.
>>>> This step prepares separation of pac7302 and pac7311 specific parts of
>>>> struct sd.
>>> [...]
>>> But here is the point. The sn9c2028 cameras have a structure which seems
>>> similar to the mr97310a cameras. They use a similar decompression
>>> algorithm. They have a similar frame header. Specifically, the sn9c2028
>>> frame header starts with the five bytes
>>>
>>>                  0xff, 0xff, 0x00, 0xc4, 0xc4
>>>
>>> whereas the pac_common frame header starts with the five bytes
>>>
>>>                  0xff, 0xff, 0x00, 0xff, 0x96
>>>
>>> Right now, for my own use, I have written a file sn9c2028.h which
>>> essentially duplicates the functionality of pac_common.h and contains a
>>> function which searches for the sn9c2028 SOF marker instead of searching
>>> for the pac SOF marker. Is this necessarily the good, permanent solution?
>>> I am not so sure about that.
>> I think the pac_find_sof() is a special case. To find a SOF sequence in
>> a bigger buffer in general needs to first analyze the SOF sequence for
>> repeated bytes. If there are repeated bytes the search have to be
>> continued in a different way, see the state machine currently in the
>> pac_common.h. To find the sn9c2028 frame header a different state machine
>> is needed. It might be possible to implement a search function which
>> can find any SOF sequence but I am afraid that this algorithm would be
>> too complicated because of the search string analysis.
> 
> Well, I do not really know enough about this to be able to say something 
> authoritative, but:
> 
> 1. There is an obvious limitation on the length of the SOF marker. If it 
> is agreed upon that the SOF marker is 5 bytes or less, then it ought not 
> to be so terrible a thing to do. Namely, your state machine should accept 
> an input, consisting of a pointer to the proper SOF marker and use that 
> one instead of what is "hard wired" in your code. So, for example,
> 
>                  switch (sd->sof_read) {
>                  case 0:
>                          if (m[i] == 0xff)
>                                  sd->sof_read = 1;
>                          break;
>                  case 1:
>                          if (m[i] == 0xff)
>                                  sd->sof_read = 2;
>                          else
>                                  sd->sof_read = 0;
>                          break;
>  			(and so on)
> 
> could read instead as
> 
>                  switch (sd->sof_read) {
>                  case 0:
>                          if (m[i] == sof_marker[0])
>                                  sd->sof_read = 1;
>                          break;
>                  case 1:
>                          if (m[i] == sof_marker[1])
>                                  sd->sof_read = 2;
>                          else
>                                  sd->sof_read = 0;
>                          break;
>  			(and so on)
> 
> 
> The problem would come if the SOF marker were six bytes long instead. The 
> way to solve that would be to figure out what is the longest SOF marker 
> that one wants to deal with, beforehand. I am not sure what is the 
> prevailing number of bytes in such an SOF marker, or the maximum number. 
> But it would be possible to prescribe some reasonable maximum number 
> and take that into account, I think.

I am afraid you missed an important point: the state machine depends on the
*contents* of the SOF marker:

>From pac_common.h:

   The following state machine finds the SOF marker sequence
   0xff, 0xff, 0x00, 0xff, 0x96 in a byte stream.

           +----------+
           | 0: START |<---------------\
           +----------+<-\             |
             |       \---/otherwise    |
             v 0xff                    |
           +----------+ otherwise      |
           |     1    |--------------->*
           |          |                ^
           +----------+                |
             |                         |
             v 0xff                    |
           +----------+<-\0xff         |
        /->|          |--/             |
        |  |     2    |--------------->*
        |  |          | otherwise      ^
        |  +----------+                |
        |    |                         |
        |    v 0x00                    |
        |  +----------+                |
        |  |     3    |                |
        |  |          |--------------->*
        |  +----------+ otherwise      ^
        |    |                         |
   0xff |    v 0xff                    |
        |  +----------+                |
        \--|     4    |                |
           |          |----------------/
           +----------+ otherwise
             |
             v 0x96
           +----------+
           |  FOUND   |
           +----------+

Please have a closer look of the transients 2->2 and
4->2. They heavily depend on the 0xff bytes found in the
SOF marker. You might also want to have a look at the attached
test cases to see why the state machine is necessary.

Regards,

	Márton Németh



[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: test_pac_find_sof.c --]
[-- Type: text/x-csrc; name="test_pac_find_sof.c", Size: 6504 bytes --]


/*
  Test the function pac_find_sof() from file
  linux/drivers/media/video/gspca/pac_common.h

  Test based on Linux kernel 2.6.32-rc1
  Written by Márton Németh <nm127@freemail.hu>, 4 Oct 2009
  Released under GPL
*/

#include <stdio.h>

struct sd {
	unsigned int sof_read;
};

struct gspca_dev {
    struct sd* sd;
};

#define PDEBUG(level, fmt, args...) \
	do {\
		printf("PDEBUG: " fmt "\n", ## args); \
	} while (0)

#include "pac_common.h"

int tc1() {
	static unsigned char test[] = { 0xff, 0xff, 0x00, 0xff, 0x96 };
	unsigned char* p;
	struct sd sd;
	int result = 0;

	printf("Test case 1: exact match\n");
	sd.sof_read = 0;
	p = pac_find_sof((struct gspca_dev*)&sd, test, sizeof(test));
	if (p == &test[5]) {
		printf("PASSED\n");
	} else {
		printf("FAILED\n");
		result = 1;
	}
	printf("\n");

	return result;
}

int tc2() {
	static unsigned char test[] = { 0x00, 0xff, 0xff, 0x00, 0xff, 0x96 };
	unsigned char* p;
	struct sd sd;
	int result = 0;

	printf("Test case 2: offset 1\n");
	sd.sof_read = 0;
	p = pac_find_sof((struct gspca_dev*)&sd, test, sizeof(test));
	if (p == &test[6]) {
		printf("PASSED\n");
	} else {
		printf("FAILED\n");
		result = 1;
	}
	printf("\n");

	return result;
}

int tc3() {
	static unsigned char test[] = { 0xff, 0xff, 0xff, 0x00, 0xff, 0x96 };
	unsigned char* p;
	struct sd sd;
	int result = 0;

	printf("Test case 3: offset 1, first byte may be misleading\n");
	sd.sof_read = 0;
	p = pac_find_sof((struct gspca_dev*)&sd, test, sizeof(test));
	if (p == &test[6]) {
		printf("PASSED\n");
	} else {
		printf("FAILED\n");
		result = 1;
	}
	printf("\n");

	return result;
}

int tc4() {
	static unsigned char test[] = { 0xff, 0x00, 0xff, 0xff, 0x00, 0xff, 0x96 };
	unsigned char* p;
	struct sd sd;
	int result = 0;

	printf("Test case 4: offset 2, first two bytes may be misleading\n");
	sd.sof_read = 0;
	p = pac_find_sof((struct gspca_dev*)&sd, test, sizeof(test));
	if (p == &test[7]) {
		printf("PASSED\n");
	} else {
		printf("FAILED\n");
		result = 1;
	}
	printf("\n");

	return result;
}

int tc5() {
	static unsigned char test[] = { 0xff, 0xff, 0x00, 0xff, 0xff, 0x00, 0xff, 0x96 };
	unsigned char* p;
	struct sd sd;
	int result = 0;

	printf("Test case 5: offset 3, first three bytes may be misleading\n");
	sd.sof_read = 0;
	p = pac_find_sof((struct gspca_dev*)&sd, test, sizeof(test));
	if (p == &test[8]) {
		printf("PASSED\n");
	} else {
		printf("FAILED\n");
		result = 1;
	}
	printf("\n");

	return result;
}

int tc6() {
	static unsigned char test[] = { 0xff, 0xff, 0x00, 0xff, 0xff, 0xff, 0x00, 0xff, 0x96 };
	unsigned char* p;
	struct sd sd;
	int result = 0;

	printf("Test case 6: offset 4, first four bytes may be misleading\n");
	sd.sof_read = 0;
	p = pac_find_sof((struct gspca_dev*)&sd, test, sizeof(test));
	if (p == &test[9]) {
		printf("PASSED\n");
	} else {
		printf("FAILED\n");
		result = 1;
	}
	printf("\n");

	return result;
}

int tc7() {
	static unsigned char test1[] = { 0xff, 0xff, 0x00, 0xff };
	static unsigned char test2[] = { 0x96 };
	unsigned char* p1;
	unsigned char* p2;
	struct sd sd;
	int result = 0;

	printf("Test case 7: pattern starts at end of packet and continues in the next one\n");
	sd.sof_read = 0;
	p1 = pac_find_sof((struct gspca_dev*)&sd, test1, sizeof(test1));
	p2 = pac_find_sof((struct gspca_dev*)&sd, test2, sizeof(test2));
	if (p1 == NULL && p2 == &test2[1]) {
		printf("PASSED\n");
	} else {
		printf("FAILED\n");
		result = 1;
	}
	printf("\n");

	return result;
}

int tc8() {
	static unsigned char test1[] = { 0xff, 0xff, 0xff, 0x00, 0xff };
	static unsigned char test2[] = { 0x96 };
	unsigned char* p1;
	unsigned char* p2;
	struct sd sd;
	int result = 0;

	printf("Test case 8: splited pattern, with misleading first byte\n");
	sd.sof_read = 0;
	p1 = pac_find_sof((struct gspca_dev*)&sd, test1, sizeof(test1));
	p2 = pac_find_sof((struct gspca_dev*)&sd, test2, sizeof(test2));
	if (p1 == NULL && p2 == &test2[1]) {
		printf("PASSED\n");
	} else {
		printf("FAILED\n");
		result = 1;
	}
	printf("\n");

	return result;
}

int tc9() {
	static unsigned char test1[] = { 0xff, 0xff, 0x00, 0xff, 0xff, 0x00, 0xff };
	static unsigned char test2[] = { 0x96 };
	unsigned char* p1;
	unsigned char* p2;
	struct sd sd;
	int result = 0;

	printf("Test case 9: splited pattern, with misleading first three bytes\n");
	sd.sof_read = 0;
	p1 = pac_find_sof((struct gspca_dev*)&sd, test1, sizeof(test1));
	p2 = pac_find_sof((struct gspca_dev*)&sd, test2, sizeof(test2));
	if (p1 == NULL && p2 == &test2[1]) {
		printf("PASSED\n");
	} else {
		printf("FAILED\n");
		result = 1;
	}
	printf("\n");

	return result;
}

int tc10() {
	static unsigned char test[] = { 0xff, 0xaa, 0xff, 0x00, 0xff, 0x96 };
	unsigned char* p;
	struct sd sd;
	int result = 0;

	printf("Test case 10: no match, extra byte at offset 1\n");
	sd.sof_read = 0;
	p = pac_find_sof((struct gspca_dev*)&sd, test, sizeof(test));
	if (p == NULL) {
		printf("PASSED\n");
	} else {
		printf("FAILED\n");
		result = 1;
	}
	printf("\n");

	return result;
}

int tc11() {
	static unsigned char test[] = { 0xff, 0xff, 0xaa, 0x00, 0xff, 0x96 };
	unsigned char* p;
	struct sd sd;
	int result = 0;

	printf("Test case 11: no match, extra byte at offset 2\n");
	sd.sof_read = 0;
	p = pac_find_sof((struct gspca_dev*)&sd, test, sizeof(test));
	if (p == NULL) {
		printf("PASSED\n");
	} else {
		printf("FAILED\n");
		result = 1;
	}
	printf("\n");

	return result;
}

int tc12() {
	static unsigned char test[] = { 0xff, 0xff, 0x00, 0xaa, 0xff, 0x96 };
	unsigned char* p;
	struct sd sd;
	int result = 0;

	printf("Test case 12: no match, extra byte at offset 3\n");
	sd.sof_read = 0;
	p = pac_find_sof((struct gspca_dev*)&sd, test, sizeof(test));
	if (p == NULL) {
		printf("PASSED\n");
	} else {
		printf("FAILED\n");
		result = 1;
	}
	printf("\n");

	return result;
}

int tc13() {
	static unsigned char test[] = { 0xff, 0xff, 0x00, 0xff, 0xaa, 0x96 };
	unsigned char* p;
	struct sd sd;
	int result = 0;

	printf("Test case 13: no match, extra byte at offset 4\n");
	sd.sof_read = 0;
	p = pac_find_sof((struct gspca_dev*)&sd, test, sizeof(test));
	if (p == NULL) {
		printf("PASSED\n");
	} else {
		printf("FAILED\n");
		result = 1;
	}
	printf("\n");

	return result;
}


int main() {
	int result = 0;

	result += tc1();
	result += tc2();
	result += tc3();
	result += tc4();
	result += tc5();
	result += tc6();
	result += tc7();
	result += tc8();
	result += tc9();
	result += tc10();
	result += tc11();
	result += tc12();
	result += tc13();

	return result;
}

Re: [PATCH 1/3] gspca pac7302/pac7311: simplify pac_find_sof

[Theodore Kilgore]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 5518 bytes --]



On Mon, 2 Nov 2009, Németh Márton wrote:

> Theodore Kilgore írta:
>>
>> On Mon, 2 Nov 2009, Németh Márton wrote:
>>
>>> Theodore Kilgore wrote:
>>>> On Sun, 1 Nov 2009, Németh Márton wrote:
>>>>> Remove struct sd dependency from pac_find_sof() function implementation.
>>>>> This step prepares separation of pac7302 and pac7311 specific parts of
>>>>> struct sd.
>>>> [...]
>>>> But here is the point. The sn9c2028 cameras have a structure which seems
>>>> similar to the mr97310a cameras. They use a similar decompression
>>>> algorithm. They have a similar frame header. Specifically, the sn9c2028
>>>> frame header starts with the five bytes
>>>>
>>>>                  0xff, 0xff, 0x00, 0xc4, 0xc4
>>>>
>>>> whereas the pac_common frame header starts with the five bytes
>>>>
>>>>                  0xff, 0xff, 0x00, 0xff, 0x96
>>>>
>>>> Right now, for my own use, I have written a file sn9c2028.h which
>>>> essentially duplicates the functionality of pac_common.h and contains a
>>>> function which searches for the sn9c2028 SOF marker instead of searching
>>>> for the pac SOF marker. Is this necessarily the good, permanent solution?
>>>> I am not so sure about that.
>>> I think the pac_find_sof() is a special case. To find a SOF sequence in
>>> a bigger buffer in general needs to first analyze the SOF sequence for
>>> repeated bytes. If there are repeated bytes the search have to be
>>> continued in a different way, see the state machine currently in the
>>> pac_common.h. To find the sn9c2028 frame header a different state machine
>>> is needed. It might be possible to implement a search function which
>>> can find any SOF sequence but I am afraid that this algorithm would be
>>> too complicated because of the search string analysis.
>>
>> Well, I do not really know enough about this to be able to say something
>> authoritative, but:
>>
>> 1. There is an obvious limitation on the length of the SOF marker. If it
>> is agreed upon that the SOF marker is 5 bytes or less, then it ought not
>> to be so terrible a thing to do. Namely, your state machine should accept
>> an input, consisting of a pointer to the proper SOF marker and use that
>> one instead of what is "hard wired" in your code. So, for example,
>>
>>                  switch (sd->sof_read) {
>>                  case 0:
>>                          if (m[i] == 0xff)
>>                                  sd->sof_read = 1;
>>                          break;
>>                  case 1:
>>                          if (m[i] == 0xff)
>>                                  sd->sof_read = 2;
>>                          else
>>                                  sd->sof_read = 0;
>>                          break;
>>  			(and so on)
>>
>> could read instead as
>>
>>                  switch (sd->sof_read) {
>>                  case 0:
>>                          if (m[i] == sof_marker[0])
>>                                  sd->sof_read = 1;
>>                          break;
>>                  case 1:
>>                          if (m[i] == sof_marker[1])
>>                                  sd->sof_read = 2;
>>                          else
>>                                  sd->sof_read = 0;
>>                          break;
>>  			(and so on)
>>
>>
>> The problem would come if the SOF marker were six bytes long instead. The
>> way to solve that would be to figure out what is the longest SOF marker
>> that one wants to deal with, beforehand. I am not sure what is the
>> prevailing number of bytes in such an SOF marker, or the maximum number.
>> But it would be possible to prescribe some reasonable maximum number
>> and take that into account, I think.
>
> I am afraid you missed an important point: the state machine depends on the
> *contents* of the SOF marker:
>
>> From pac_common.h:
>
>   The following state machine finds the SOF marker sequence
>   0xff, 0xff, 0x00, 0xff, 0x96 in a byte stream.
>
>           +----------+
>           | 0: START |<---------------\
>           +----------+<-\             |
>             |       \---/otherwise    |
>             v 0xff                    |
>           +----------+ otherwise      |
>           |     1    |--------------->*
>           |          |                ^
>           +----------+                |
>             |                         |
>             v 0xff                    |
>           +----------+<-\0xff         |
>        /->|          |--/             |
>        |  |     2    |--------------->*
>        |  |          | otherwise      ^
>        |  +----------+                |
>        |    |                         |
>        |    v 0x00                    |
>        |  +----------+                |
>        |  |     3    |                |
>        |  |          |--------------->*
>        |  +----------+ otherwise      ^
>        |    |                         |
>   0xff |    v 0xff                    |
>        |  +----------+                |
>        \--|     4    |                |
>           |          |----------------/
>           +----------+ otherwise
>             |
>             v 0x96
>           +----------+
>           |  FOUND   |
>           +----------+
>
> Please have a closer look of the transients 2->2 and
> 4->2. They heavily depend on the 0xff bytes found in the
> SOF marker.

Yes, on second look I see what you mean. Your routine is built around the 
_specific_ contents of the frame header. If that makes it work with fewer 
errors, then that is the end of the discussion.

Theodore Kilgore