From fe9b4a38888f82c0e4541cf31660d1e4329ac20d Mon Sep 17 00:00:00 2001 From: Timo Teräs Date: Wed, 8 Feb 2012 17:01:14 +0200 Subject: blob: optimize spn and cspn --- src/apk_blob.h | 7 +++-- src/blob.c | 91 +++++++++++++++++++++++++++++++++++++++++++++++++++++++--- src/database.c | 9 ++++-- src/package.c | 17 ++++++++--- 4 files changed, 112 insertions(+), 12 deletions(-) (limited to 'src') 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++) { -- cgit v1.2.3-60-g2f50