blob: optimize spn and cspn

4 files changed, 112 insertions, 12 deletions

diff --git a/src/apk_blob.h b/src/apk_blob.h
index 55838ad..23bff3f 100644
--- a/src/apk_blob.h
+++ b/src/apk_blob.h
@@ -18,6 +18,9 @@
 
 #include "apk_defines.h"
 
+typedef const unsigned char *apk_spn_match;
+typedef unsigned char apk_spn_match_def[256 / 8];
+
 struct apk_blob {
 	long len;
 	char *ptr;
@@ -83,8 +86,8 @@ static inline apk_blob_t apk_blob_trim(apk_blob_t blob)
 }
 
 char *apk_blob_cstr(apk_blob_t str);
-int apk_blob_spn(apk_blob_t blob, const char *accept, apk_blob_t *l, apk_blob_t *r);
-int apk_blob_cspn(apk_blob_t blob, const char *reject, apk_blob_t *l, apk_blob_t *r);
+int apk_blob_spn(apk_blob_t blob, const apk_spn_match accept, apk_blob_t *l, apk_blob_t *r);
+int apk_blob_cspn(apk_blob_t blob, const apk_spn_match reject, apk_blob_t *l, apk_blob_t *r);
 int apk_blob_split(apk_blob_t blob, apk_blob_t split, apk_blob_t *l, apk_blob_t *r);
 int apk_blob_rsplit(apk_blob_t blob, char split, apk_blob_t *l, apk_blob_t *r);
 apk_blob_t apk_blob_pushed(apk_blob_t buffer, apk_blob_t left);
diff --git a/src/blob.c b/src/blob.c
index 19c4613..33b0d63 100644
--- a/src/blob.c
+++ b/src/blob.c
@@ -38,12 +38,94 @@ char *apk_blob_cstr(apk_blob_t blob)
 	return cstr;
 }
 
-int apk_blob_spn(apk_blob_t blob, const char *accept, apk_blob_t *l, apk_blob_t *r)
+#if defined(__i386__)
+static unsigned long inline memspn(
+		const unsigned char *ptr,
+		unsigned long len,
+		const unsigned char *array)
+{
+	unsigned long p = len;
+
+	__asm__("cld ; xorl %%eax, %%eax\n"
+		"1:\n"
+		"lodsb\n"
+		"btl %%eax, %2\n"
+		"jnc 2f\n"
+		"decl %1\n"
+		"jnz 1b\n"
+		"2:\n"
+		: "+&S" (ptr), "+&r" (p)
+		: "m" (*array)
+		: "cc", "%eax");
+
+	return p;
+}
+
+static unsigned long inline memcspn(
+		const unsigned char *ptr,
+		unsigned long len,
+		const unsigned char *array)
+{
+	unsigned long p = len;
+
+	__asm__("cld ; xorl %%eax, %%eax\n"
+		"1:\n"
+		"lodsb\n"
+		"btl %%eax, %2\n"
+		"jc 2f\n"
+		"decl %1\n"
+		"jnz 1b\n"
+		"2:\n"
+		: "+&S" (ptr), "+&r" (p)
+		: "m" (*array)
+		: "cc", "%eax");
+
+	return p;
+}
+
+int apk_blob_spn(apk_blob_t blob, const apk_spn_match accept, apk_blob_t *l, apk_blob_t *r)
+{
+	unsigned int i;
+
+	if (blob.len == 0)
+		return 0;
+	i = blob.len - memspn((unsigned char*) blob.ptr, blob.len, accept);
+	if (i == blob.len)
+		return 0;
+	if (l != NULL)
+		*l = APK_BLOB_PTR_LEN(blob.ptr, i);
+	if (r != NULL)
+		*r = APK_BLOB_PTR_LEN(blob.ptr+i, blob.len-i);
+	return 1;
+}
+
+int apk_blob_cspn(apk_blob_t blob, const apk_spn_match reject, apk_blob_t *l, apk_blob_t *r)
+{
+	unsigned int i;
+
+	if (blob.len == 0)
+		return 0;
+	i = blob.len - memcspn((unsigned char*) blob.ptr, blob.len, reject);
+	if (i == blob.len)
+		return 0;
+	if (l != NULL)
+		*l = APK_BLOB_PTR_LEN(blob.ptr, i);
+	if (r != NULL)
+		*r = APK_BLOB_PTR_LEN(blob.ptr+i, blob.len-i);
+	return 1;
+}
+#else
+static int inline test_bit(const unsigned char *array, unsigned bit)
+{
+	return array[bit >> 3] & (1 << (bit & 7));
+}
+
+int apk_blob_spn(apk_blob_t blob, const apk_spn_match accept, apk_blob_t *l, apk_blob_t *r)
 {
 	int i;
 
 	for (i = 0; i < blob.len; i++) {
-		if (strchr(accept, blob.ptr[i]) == NULL) {
+		if (!test_bit(accept, blob.ptr[i])) {
 			if (l != NULL)
 				*l = APK_BLOB_PTR_LEN(blob.ptr, i);
 			if (r != NULL)
@@ -54,12 +136,12 @@ int apk_blob_spn(apk_blob_t blob, const char *accept, apk_blob_t *l, apk_blob_t
 	return 0;
 }
 
-int apk_blob_cspn(apk_blob_t blob, const char *reject, apk_blob_t *l, apk_blob_t *r)
+int apk_blob_cspn(apk_blob_t blob, const apk_spn_match reject, apk_blob_t *l, apk_blob_t *r)
 {
 	int i;
 
 	for (i = 0; i < blob.len; i++) {
-		if (strchr(reject, blob.ptr[i]) != NULL) {
+		if (test_bit(reject, blob.ptr[i])) {
 			if (l != NULL)
 				*l = APK_BLOB_PTR_LEN(blob.ptr, i);
 			if (r != NULL)
@@ -69,6 +151,7 @@ int apk_blob_cspn(apk_blob_t blob, const char *reject, apk_blob_t *l, apk_blob_t
 	}
 	return 0;
 }
+#endif
 
 int apk_blob_rsplit(apk_blob_t blob, char split, apk_blob_t *l, apk_blob_t *r)
 {
diff --git a/src/database.c b/src/database.c
index d546d7e..e084b8b 100644
--- a/src/database.c
+++ b/src/database.c
@@ -33,6 +33,11 @@
 #include "apk_archive.h"
 #include "apk_print.h"
 
+static const apk_spn_match_def apk_spn_repo_separators = {
+	[4] = (1<<0) /* */,
+	[7] = (1<<2) /*:*/,
+};
+
 enum {
 	APK_DISALLOW_RMDIR = 0,
 	APK_ALLOW_RMDIR = 1
@@ -1770,8 +1775,8 @@ int apk_db_add_repository(apk_database_t _db, apk_blob_t _repository)
 
 	if (brepo.ptr[0] == '@') {
 		apk_blob_pull_char(&brepo, '@');
-		apk_blob_cspn(brepo, ": ", &btag, &brepo);
-		apk_blob_spn(brepo, ": ", NULL, &brepo);
+		apk_blob_cspn(brepo, apk_spn_repo_separators, &btag, &brepo);
+		apk_blob_spn(brepo, apk_spn_repo_separators, NULL, &brepo);
 		tag_id = apk_db_get_tag_id(db, btag);
 	}
 
diff --git a/src/package.c b/src/package.c
index 32d4564..20895cb 100644
--- a/src/package.c
+++ b/src/package.c
@@ -29,6 +29,15 @@
 #include "apk_database.h"
 #include "apk_print.h"
 
+static const apk_spn_match_def apk_spn_dependency_comparer = {
+	[7] = (1<<4) /*<*/ | (1<<5) /*=*/ | (1<<6) /*<*/,
+};
+
+static const apk_spn_match_def apk_spn_dependency_separator = {
+	[1] = (1<<2) /*\n*/,
+	[4] = (1<<0) /* */,
+};
+
 void apk_pkg_format_plain(struct apk_package *pkg, apk_blob_t to)
 {
 	/* pkgname-1.0.apk */
@@ -200,13 +209,13 @@ void apk_blob_pull_dep(apk_blob_t *b, struct apk_database *db, struct apk_depend
 		goto fail;
 
 	/* grap one token */
-	if (!apk_blob_cspn(*b, " \n", &bdep, NULL))
+	if (!apk_blob_cspn(*b, apk_spn_dependency_separator, &bdep, NULL))
 		bdep = *b;
 	b->ptr += bdep.len;
 	b->len -= bdep.len;
 
 	/* skip also all separator chars */
-	if (!apk_blob_spn(*b, " \n", NULL, b)) {
+	if (!apk_blob_spn(*b, apk_spn_dependency_separator, NULL, b)) {
 		b->ptr += b->len;
 		b->len = 0;
 	}
@@ -218,12 +227,12 @@ void apk_blob_pull_dep(apk_blob_t *b, struct apk_database *db, struct apk_depend
 		optional = 1;
 	}
 
-	if (apk_blob_cspn(bdep, "<>=", &bname, &bop)) {
+	if (apk_blob_cspn(bdep, apk_spn_dependency_comparer, &bname, &bop)) {
 		int i;
 
 		if (mask == 0)
 			goto fail;
-		if (!apk_blob_spn(bop, "<>=", &bop, &bver))
+		if (!apk_blob_spn(bop, apk_spn_dependency_comparer, &bop, &bver))
 			goto fail;
 		mask = 0;
 		for (i = 0; i < bop.len; i++) {