blob: optimize digit and base64 decoding

1 files changed, 110 insertions, 41 deletions

diff --git a/src/blob.c b/src/blob.c
index 8cf4076..19c4613 100644
--- a/src/blob.c
+++ b/src/blob.c
@@ -159,15 +159,44 @@ int apk_blob_for_each_segment(apk_blob_t blob, const char *split,
 	return 0;
 }
 
-static inline int dx(int c)
+static unsigned char digitdecode[] = {
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0x3e, 0xff, 0xff, 0xff, 0xff,
+	   0,    1,    2,    3,    4,    5,    6,    7,
+	   8,    9, 0xff, 0xff, 0xff, 0x00, 0xff, 0xff,
+	0xff,  0xa,  0xb,  0xc,  0xd,  0xe,  0xf, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff,  0xa,  0xb,  0xc,  0xd,  0xe,  0xf, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+};
+
+static inline int dx(unsigned char c)
 {
-	if (likely(c >= '0' && c <= '9'))
-		return c - '0';
-	if (likely(c >= 'a' && c <= 'f'))
-		return c - 'a' + 0xa;
-	if (c >= 'A' && c <= 'F')
-		return c - 'A' + 0xa;
-	return -1;
+	return digitdecode[c];
 }
 
 void apk_blob_push_blob(apk_blob_t *to, apk_blob_t literal)
@@ -298,7 +327,7 @@ unsigned int apk_blob_pull_uint(apk_blob_t *b, int radix)
 	val = 0;
 	while (b->len && b->ptr[0] != 0) {
 		ch = dx(b->ptr[0]);
-		if (ch < 0 || ch >= radix)
+		if (ch >= radix)
 			break;
 		val *= radix;
 		val += ch;
@@ -322,7 +351,7 @@ void apk_blob_pull_csum(apk_blob_t *b, struct apk_checksum *csum)
 		return;
 	}
 
-	if (dx(b->ptr[0]) != -1) {
+	if (dx(b->ptr[0]) != 0xff) {
 		/* Assume MD5 for backwards compatibility */
 		csum->type = APK_CHECKSUM_MD5;
 		apk_blob_pull_hexdump(b, APK_BLOB_CSUM(*csum));
@@ -357,7 +386,7 @@ void apk_blob_pull_csum(apk_blob_t *b, struct apk_checksum *csum)
 void apk_blob_pull_hexdump(apk_blob_t *b, apk_blob_t to)
 {
 	char *s, *d;
-	int i, r1, r2;
+	int i, r, r1, r2;
 
 	if (unlikely(APK_BLOB_IS_NULL(*b)))
 		return;
@@ -365,15 +394,14 @@ void apk_blob_pull_hexdump(apk_blob_t *b, apk_blob_t to)
 	if (unlikely(to.len > b->len * 2))
 		goto err;
 
+	r = 0;
 	for (i = 0, s = b->ptr, d = to.ptr; i < to.len; i++) {
-		r1 = dx(*(s++));
-		if (unlikely(r1 < 0))
-			goto err;
-		r2 = dx(*(s++));
-		if (unlikely(r2 < 0))
-			goto err;
+		r |= r1 = dx(*(s++));
+		r |= r2 = dx(*(s++));
 		*(d++) = (r1 << 4) + r2;
 	}
+	if (unlikely(r == 0xff))
+		goto err;
 	b->ptr = s;
 	b->len -= to.len * 2;
 	return;
@@ -382,31 +410,53 @@ err:
 }
 
 static unsigned char b64decode[] = {
-	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
-	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
-	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
-	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x3e, 0xff, 0xff, 0xff, 0x3f,
-	0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0xff, 0xff,
-	0xff, 0x00, 0xff, 0xff, 0xff, 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06,
-	0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10, 0x11, 0x12,
-	0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19, 0xff, 0xff, 0xff, 0xff, 0xff,
-	0xff, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x20, 0x21, 0x22, 0x23, 0x24,
-	0x25, 0x26, 0x27, 0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f, 0x30,
-	0x31, 0x32, 0x33, 0xff, 0xff, 0xff, 0xff, 0xff
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0x3e, 0xff, 0xff, 0xff, 0x3f,
+	0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x3a, 0x3b,
+	0x3c, 0x3d, 0xff, 0xff, 0xff, 0x00, 0xff, 0xff,
+	0xff, 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06,
+	0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e,
+	0x0f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16,
+	0x17, 0x18, 0x19, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x20,
+	0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28,
+	0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f, 0x30,
+	0x31, 0x32, 0x33, 0xff, 0xff, 0xff, 0xff, 0xff,
+
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 };
 
-static inline int pull_b64_chunk(unsigned char *to, const unsigned char *from, int len)
+static inline __attribute__((always_inline))
+int pull_b64_chunk(unsigned char *to, const unsigned char *from, int len)
 {
 	unsigned char tmp[4];
-	int i;
+	int i, r = 0;
 
-	for (i = 0; i < 4; i++) {
-		if (unlikely(from[i] >= 0x80))
-			return -1;
+	for (i = 0; i < len; i++) {
 		tmp[i] = b64decode[from[i]];
-		if (unlikely(tmp[i] == 0xff))
-			return -1;
+		r |= tmp[i];
 	}
+	if (unlikely(r == 0xff))
+		return -1;
 
 	to[0] = (tmp[0] << 2 | tmp[1] >> 4);
 	if (len > 1)
@@ -422,9 +472,10 @@ static inline int pull_b64_chunk(unsigned char *to, const unsigned char *from, i
 
 void apk_blob_pull_base64(apk_blob_t *b, apk_blob_t to)
 {
+	unsigned char tmp[4];
 	unsigned char *src = (unsigned char *) b->ptr;
 	unsigned char *dst = (unsigned char *) to.ptr;
-	int i, needed;
+	int i, r, needed;
 
 	if (unlikely(APK_BLOB_IS_NULL(*b)))
 		return;
@@ -435,11 +486,29 @@ void apk_blob_pull_base64(apk_blob_t *b, apk_blob_t to)
 		return;
 	}
 
-	for (i = 0; i < to.len / 3; i++, src += 4, dst += 3)
-		pull_b64_chunk(dst, src, 4);
+	r = 0;
+	for (i = 0; i < to.len / 3; i++, src += 4, dst += 3) {
+		r |= tmp[0] = b64decode[src[0]];
+		r |= tmp[1] = b64decode[src[1]];
+		r |= tmp[2] = b64decode[src[2]];
+		r |= tmp[3] = b64decode[src[3]];
+		dst[0] = (tmp[0] << 2 | tmp[1] >> 4);
+		dst[1] = (tmp[1] << 4 | tmp[2] >> 2);
+		dst[2] = (((tmp[2] << 6) & 0xc0) | tmp[3]);
+	}
+	if (unlikely(r == 0xff)) {
+		*b = APK_BLOB_NULL;
+		return;
+	}
+
 	i = to.len % 3;
-	if (i != 0)
-		pull_b64_chunk(dst, src, i);
+	if (i != 0) {
+		if (pull_b64_chunk(dst, src, i) != 0) {
+			*b = APK_BLOB_NULL;
+			return;
+		}
+	}
+
 	b->ptr += needed;
 	b->len -= needed;
 }
@@ -461,7 +530,7 @@ static apk_blob_t null_blob = {0,0};
 
 void apk_atom_init(void)
 {
-	apk_hash_init(&atom_hash, &atom_ops, 2048);
+	apk_hash_init(&atom_hash, &atom_ops, 10000);
 }
 
 apk_blob_t *apk_blob_atomize(apk_blob_t blob)