Attempt to speed up fax decompression.

A huge number of calls are made to getbit from find_changing in fax
decompression. On Android profiling shows that this accounts for 25%
of time in handling page 2 of IA3Z0845.pdf.

Rewrite code to deal with bytes at a time for speed. Profiling
now shows 5% in this function.

1 files changed, 53 insertions, 13 deletions

diff --git a/fitz/filt_faxd.c b/fitz/filt_faxd.c
index febc6a65..8c6ee5a5 100644
--- a/fitz/filt_faxd.c
+++ b/fitz/filt_faxd.c
@@ -175,33 +175,73 @@ static inline int getbit(const unsigned char *buf, int x)
 	return ( buf[x >> 3] >> ( 7 - (x & 7) ) ) & 1;
 }
 
-static int
+static const unsigned char mask[8] = {
+	0x7F, 0x3F, 0x1F, 0x0F, 0x07, 0x03, 0x01, 0
+};
+
+static const unsigned char clz[256] = {
+	8, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4,
+	3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
+	2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+	2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
+	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
+	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
+	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
+	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
+};
+
+static inline int
 find_changing(const unsigned char *line, int x, int w)
 {
-	int a, b;
+	int a, b, m, W;
 
 	if (!line)
 		return w;
 
-	if (x == -1)
+	/* We assume w > 0, -1 <= x < w */
+	if (x < 0)
 	{
-		a = 0;
 		x = 0;
+		m = 0xFF;
 	}
 	else
 	{
-		a = getbit(line, x);
-		x++;
+		/* Mask out the bits we've already used (including the one
+		 * we started from) */
+		m = mask[x & 7];
 	}
-
-	while (x < w)
+	W = w>>3;
+	x >>= 3;
+	a = line[x];
+	b = a ^ (a>>1);
+	b &= m;
+	while (b == 0)
 	{
-		b = getbit(line, x);
-		if (a != b)
-			break;
-		x++;
+		if (++x >= W)
+			goto nearend;
+		b = a & 1;
+		a = line[x];
+		b = (b<<7) ^ a ^ (a>>1);
 	}
-
+	return (x<<3) + clz[b];
+nearend:
+	/* We have less than a byte to go. If no stray bits, exit now. */
+	if ((x<<3) == w)
+		return w;
+	b = a&1;
+	b = line[x];
+	b = (b<<7) ^ a ^ (a>>1);
+	x = (x<<3) + clz[b];
+	if (x > w)
+		x = w;
 	return x;
 }