Здравствуйте, Poseidon, Вы писали:
P>Подскажите пожалуйста аналог strstr, но без учета регистра — как написать или где взять готовую (чтобы была не медленее strstr)?
Попробуй std::search, предикат для сравнения без учета регистра вроде был в boost-е.
Здравствуйте, Poseidon, Вы писали:
P>Подскажите пожалуйста аналог strstr, но без учета регистра — как написать или где взять готовую (чтобы была не медленее strstr)?
std::search со своим предикатом.
Вот только "не медленнее" тут не катит — другая ситуация.
Подводный камень — наборы символов, которые необходимо обрабатывать
(если только латиница — куда ни шло, если любые — попадалово
с кодировками).
Здравствуйте, _wf, Вы писали:
_wf>Здравствуйте, Poseidon, Вы писали:
P>>Подскажите пожалуйста аналог strstr, но без учета регистра — как написать или где взять готовую (чтобы была не медленее strstr)?
_wf>std::search со своим предикатом.
_wf>Вот только "не медленнее" тут не катит — другая ситуация. _wf>Подводный камень — наборы символов, которые необходимо обрабатывать _wf>(если только латиница — куда ни шло, если любые — попадалово _wf>с кодировками).
Здравствуйте, Poseidon, Вы писали:
P>Подскажите пожалуйста аналог strstr, но без учета регистра — как написать или где взять готовую (чтобы была не медленее strstr)?
переведи оба аргументя в верхний регистр (toupper) и сравни этой же функцией.
Здравствуйте, Poseidon, Вы писали:
P>>>Подскажите пожалуйста аналог strstr, но без учета регистра — как написать или где взять готовую (чтобы была не медленее strstr)? P>не, это понятно. кодировка только asc-ii
А почему "asc-ii", если это официально называется ASCII?
Вообще, когда встаёт вопрос о "не медленнее", это означает две вещи:
1) Хочется избежать велосипедов со сложностью, заведомо большей чем оригинальный алгоритм.
2) Профайлер наблюдает просадку именно в этом месте.
strstr сам по себе не быстрый — в угоду O(1) памяти он тратит O(n^2) времени. (равно как std::search)
Если "strIstr" на его основе не устраивает, то, скорее всего, не устроит и сам strstr. Тогда это повод задуматься о скоростных алгоритмах поиска.
Здравствуйте, Pavel Dvorkin, Вы писали: PD>предварительно скопировав строку и строку поиска
ну и что даже так, хотя конечно можно и дешевле если писать самому.
_wf>std::search со своим предикатом. _wf>Вот только "не медленнее" тут не катит — другая ситуация. _wf>Подводный камень — наборы символов, которые необходимо обрабатывать _wf>(если только латиница — куда ни шло, если любые — попадалово _wf>с кодировками).
std::search — просто поиск линейный перебором, плата за итерируемость без random access
а для поиска подстрок есть оптимизированные алгоритмы: http://algolist.manual.ru/search/esearch/index.php
Как много веселых ребят, и все делают велосипед...
Здравствуйте, Poseidon, Вы писали:
P>Подскажите пожалуйста аналог strstr, но без учета регистра — как написать или где взять готовую (чтобы была не медленее strstr)?
Compares two character strings, using the specified locale.
Syntax
int CompareString( LCID Locale,
DWORD dwCmpFlags,
LPCTSTR lpString1,
int cchCount1,
LPCTSTR lpString2,
int cchCount2
);
dwCmpFlags
NORM_IGNORECASE
Ignore case. The Remarks section below explains how this differs from LINGUISTIC_IGNORECASE.
А вот будет ли она не медленнее strstr — не знаю. Вряд ли. Думаю, у нее хватит ума делать преобразование к одному регистру символов по текущей локали, то есть не быстро.
_wf>>std::search со своим предикатом. _wf>>Вот только "не медленнее" тут не катит — другая ситуация. _wf>>Подводный камень — наборы символов, которые необходимо обрабатывать _wf>>(если только латиница — куда ни шло, если любые — попадалово _wf>>с кодировками). O>std::search — просто поиск линейный перебором, плата за итерируемость без random access O>а для поиска подстрок есть оптимизированные алгоритмы: http://algolist.manual.ru/search/esearch/index.php
Кто несогласен — идут читать документацию по std::search, и особенно следующее: It evaluates the predicate (last2 — first2) * (last1 — first1) times, at most.
что соотвествует самому медленному методу (то бишь прямому перебору) из приведенной мной ссылки
Как много веселых ребят, и все делают велосипед...
O>>std::search — просто поиск линейный перебором, плата за итерируемость без random access O>>а для поиска подстрок есть оптимизированные алгоритмы: http://algolist.manual.ru/search/esearch/index.php O>Кто несогласен — идут читать документацию по std::search, и особенно следующее: O>It evaluates the predicate (last2 — first2) * (last1 — first1) times, at most. O>что соотвествует самому медленному методу (то бишь прямому перебору) из приведенной мной ссылки
для особо принципиально несогласных, прогоните след код на вашем компиляторе:
Здравствуйте, ononim, Вы писали: O>студия 2005. дефолтовый релиз по скорости у меня дал след результаты: 1828 msec 437 msec
Вся разница в том, что это лучшее из того что здесь есть, это понятно ?
т.к это единственное "ЗДЕСЬ" решение которое основывается не на словах а которое работает.
Напишите свою версию и пожалуйста показывайте цифры. А сравнивать функцию которая не учитывает регистр и с той которая учитывает не корректно для оценки ее произоводительности.
D>Здравствуйте, ononim, Вы писали: O>>студия 2005. дефолтовый релиз по скорости у меня дал след результаты: 1828 msec 437 msec D>Вся разница в том, что это лучшее из того что здесь есть, это понятно ? D>т.к это единственное "ЗДЕСЬ" решение которое основывается не на словах а которое работает. D>Напишите свою версию и пожалуйста показывайте цифры. А сравнивать функцию которая не учитывает регистр и с той которая учитывает не корректно для оценки ее произоводительности.
То есть вы предлагаете мне написать на халяву код?
Я привел список алгоритмов оптимизированного поиска подстрок, с описанием их различий (оптимизация по памяти, времени, размеру строк etc).
Разница их реализаций будет отличаться от грубого перебора в разы и даже на порядки — в зависимости от того на каких данных хочет их гонять автор. Возможно они уже реализованы в том же бусте — я хз. Но я точно знаю что std::search будет медленнее любого из этих алгоритмов, и, в частности, будет медленнее чем strstr которая обычно использует один из этих оптимизированных алгоритмов. Писать код по описанию алгоритма или искать готовую реализацию в гугле — этим пусть занимается топикстартер или тот кому делать нечего.
Как много веселых ребят, и все делают велосипед...
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>CompareString Function
Эта функция мне известна, но беда в том что для ее использования нужно писать цикл.
Мне нужнен полный аналог strstr, сам пробегающий всю строку до нулевого символа, и возвращающий указатель на вхождение подстроки.
например когда в заголовке HTTP ответа нужно найти строку типа "Content-Length: "
сейчас юзаю вот такую конструкцию —
if (NULL!=(headptr=strstr(memptr,"Content-Length: ")) || NULL!=(headptr=strstr(memptr,"Content-length: "))) { headptr += 16;
хотелось бы if (NULL!=(headptr=strstrCustom(memptr,"content-length: "))...
Быстрые алгоритмы типа Бойера-Мура тоже юзаю, но в данном случае это, как бы сказать, overhead...
Вот StrStrI из WinApi подходит, но нужен shlwapi.dll version 4.71 or later
И еще к тому, что я сказал, если подумаешь то обратишь внимание на то, что strstr функция сишная и ничего там от ++ ничего нет,
а просили аналог, поэтому предлагать решения из boost который является дополнительной libой из c++ глупо.
Напоминаю ответ, на который я возражаю
D>>переведи оба аргументя в верхний регистр (toupper) и сравни этой же функцией.
Сравнить этой же функцией (то есть strstr) без преобразования самих строк к верхнему регистру никак не удастся. А после этого оригинальные строки уже не вернуть.
D>И еще к тому, что я сказал, если подумаешь то обратишь внимание на то, что strstr функция сишная и ничего там от ++ ничего нет, D>а просили аналог, поэтому предлагать решения из boost который является дополнительной libой из c++ глупо.
не в языке дело. У вас тут ( http://rsdn.ru/forum/cpp/3568736.1.aspx
Здравствуйте, ononim, Вы писали:
D>>И еще к тому, что я сказал, если подумаешь то обратишь внимание на то, что strstr функция сишная и ничего там от ++ ничего нет, D>>а просили аналог, поэтому предлагать решения из boost который является дополнительной libой из c++ глупо. O>не в языке дело. У вас тут ( http://rsdn.ru/forum/cpp/3568736.1.aspx
Здравствуйте, Pavel Dvorkin, Вы писали: PD>Сравнить этой же функцией (то есть strstr) без преобразования самих строк к верхнему регистру никак не удастся. А после этого оригинальные строки уже не вернуть.
ладно если не понятно тогда на пальцах, надо завести доп массивы в верхнем регистре найти вхождение в этом массиве и вернуть
такой же индекс из первого массива ( который не изменяется ).
Здравствуйте, dynamic, Вы писали:
D>ладно если не понятно тогда на пальцах, надо завести доп массивы в верхнем регистре найти вхождение в этом массиве и вернуть D>такой же индекс из первого массива ( который не изменяется ).
И чем же это отличается от того, что я написал ?
PD>предварительно скопировав строку и строку поиска
Здравствуйте, Pavel Dvorkin, Вы писали: PD>Только тем, что я не стал разжевывать детали ?
И что ?, я вас не понимаю вы пишите что никак не удается, я вам овечаю как это сделать.
Или при этом я еще утверждаю что это оптимально ?
что это лучший способ? я говорю, что это просто делается, даже если писать все самому,
и работать будет быстро учитвая требования по регистру. ( приблизительно 2.5 раза медленней, чем без сравнения )
я считаю этот результат хорошим :
на 30 000 000 сравнений
FILE : main.cpp LINE : 35, TIME WAS : 6460 msecs - это strstr
FILE : main.cpp LINE : 42, TIME WAS : 14390 msecs - это ustrstr
т.е это функция которая врядли когда — либо всплывет в профайлере.
Здравствуйте, Pavel Dvorkin, Вы писали: PD>Где я писал, что не удается ? Ссылку, пожалуйста!
пожалуйста PD>Сравнить этой же функцией (то есть strstr) без преобразования самих строк к верхнему регистру никак не удастся. А после этого оригинальные строки уже не вернуть.
Здравствуйте, dynamic, Вы писали:
PD>>Где я писал, что не удается ? Ссылку, пожалуйста!
D>пожалуйста PD>>Сравнить этой же функцией (то есть strstr) без преобразования самих строк к верхнему регистру никак не удастся. А после этого оригинальные строки уже не вернуть.
Слушай, это где учат фразы до конца не дочитывать ? См выше выделенное.
Разницу между "не удастся" и "не удастся без преобразования самих строк к верхнему регистру " надо объяснить ?
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Слушай, это где учат фразы до конца не дочитывать ? См выше выделенное.
PD>Разницу между "не удастся" и "не удастся без преобразования самих строк к верхнему регистру " надо объяснить ?
PD>Ладно, все, хватит.
Все верно, я же говорил как можно сравнить без преобразования самих строк к верхнему регистру
т.е сами оригинальные строки остаются такими же, а сравниваются другие строки (не оригинальные )
Вы сами запутались и пытаетесь мне, что — то доказать.
Здравствуйте, Pavel Dvorkin, Вы писали: PD>>>Сравнить этой же функцией (то есть strstr) без преобразования самих строк к верхнему регистру никак не удастся. А после этого оригинальные строки уже не вернуть.
PD>>>А после этого оригинальные строки уже не вернуть.
Вернуть вернуть , т.е надеюсь вы понимаете, либо вы не правильно выразились, либо ошибались.
) — метод прямого перебора (, его сложность — O(n*m) — самая худшая из всех алгоритмов.
D>Не гони там такой сложности даже в самом плохом случае не будет
25.1.9/3 (Search)
Complexity: At most (last1 — first1) * (last2 — first2) applications of the corresponding predicate.
Здравствуйте, dynamic, Вы писали:
D>Здравствуйте, dynamic, Вы писали: D>я на всякий случай положу более облизанную ( возвращает тоже как strstr ) версию этой функции вдруг кому пригодится
Чем облизывать функции, лучше в исходники CRT загляни. Они вместе со студией поставляются.
"C:\Program Files (x86)\Microsoft Visual Studio 8\VC\crt\src\strstr.c"
/***
*char *strstr(string1, string2) - search for string2 in string1
*
*Purpose:
* finds the first occurrence of string2 in string1
*
*Entry:
* char *string1 - string to search in
* char *string2 - string to search for
*
*Exit:
* returns a pointer to the first occurrence of string2 in
* string1, or NULL if string2 does not occur in string1
*
*Uses:
*
*Exceptions:
*
*******************************************************************************/char * __cdecl strstr (
const char * str1,
const char * str2
)
{
char *cp = (char *) str1;
char *s1, *s2;
if ( !*str2 )
return((char *)str1);
while (*cp)
{
s1 = cp;
s2 = (char *) str2;
while ( *s1 && *s2 && !(*s1-*s2) )
s1++, s2++;
if (!*s2)
return(cp);
cp++;
}
return(NULL);
}
Изменить одну строчку надо (если есть только латинские буквы.
while ( *s1 && *s2 && !(*s1-*s2) )
и при этом toupper не вызывать, а сделать вручную, потому что toupper работает с локалами (а как ей еще ?), а здесь надо банально проверить символ в интервале 'a'..'z' и если да — заменить на 'A'..'Z'
Но этот код в действительности не есть код рабочей strstr. Там ассемблерный код используется. Можешь и его посмотреть и даже модифицировать
"C:\Program Files (x86)\Microsoft Visual Studio 8\VC\crt\src\intel\strstr.asm"
D>Не гони там такой сложности даже в самом плохом случае не будет D>а самый плохой это вроде
D>src="anyanyanyanyanyany" D>find="anym"
как раз самая плохая сложность будет n*m
надо же, я не поленился и переделал исходники GNUсного strstr в case insensitve. Далее идет много-много кода, и в конце результаты сравнительных тестов:
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#ifndef _LIBC
# define __builtin_expect(expr, val) (expr)
#endif
#define RETURN_TYPE char *
#define AVAILABLE(h, h_l, j, n_l) \
(!memchr ((h) + (h_l), '\0', (j) + (n_l) - (h_l)) \
&& ((h_l) = (j) + (n_l)))
#include <limits.h>
/* We use the Two-Way string matching algorithm, which guarantees
linear complexity with constant space. Additionally, for long
needles, we also use a bad character shift table similar to the
Boyer-Moore algorithm to achieve improved (potentially sub-linear)
performance.
See http://www-igm.univ-mlv.fr/~lecroq/string/node26.html#SECTION00260
and http://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm
*/
/* Point at which computing a bad-byte shift table is likely to be
worthwhile. Small needles should not compute a table, since it
adds (1 << CHAR_BIT) + NEEDLE_LEN computations of preparation for a
speedup no greater than a factor of NEEDLE_LEN. The larger the
needle, the better the potential performance gain. On the other
hand, on non-POSIX systems with CHAR_BIT larger than eight, the
memory required for the table is prohibitive. */#if CHAR_BIT < 10
# define LONG_NEEDLE_THRESHOLD 32U
#else
# define LONG_NEEDLE_THRESHOLD SIZE_MAX
#endif
#ifndef MAX
# define MAX(a, b) ((a < b) ? (b) : (a))
#endif
#ifndef CANON_ELEMENT
# define CANON_ELEMENT(c) toupper(c)
#endif
#ifndef CMP_FUNC
# define CMP_FUNC memicmp
#endif/* Perform a critical factorization of NEEDLE, of length NEEDLE_LEN.
Return the index of the first byte in the right half, and set
*PERIOD to the global period of the right half.
+
The global period of a string is the smallest index (possibly its
length) at which all remaining bytes in the string are repetitions
of the prefix (the last repetition may be a subset of the prefix).
+
When NEEDLE is factored into two halves, a local period is the
length of the smallest word that shares a suffix with the left half
and shares a prefix with the right half. All factorizations of a
non-empty NEEDLE have a local period of at least 1 and no greater
than NEEDLE_LEN.
+
A critical factorization has the property that the local period
equals the global period. All strings have at least one critical
factorization with the left half smaller than the global period.
+
Given an ordered alphabet, a critical factorization can be computed
in linear time, with 2 * NEEDLE_LEN comparisons, by computing the
larger of two ordered maximal suffixes. The ordered maximal
suffixes are determined by lexicographic comparison of
periodicity. */static size_t
critical_factorization (const unsigned char *needle, size_t needle_len,
size_t *period)
{
/* Index of last byte of left half, or SIZE_MAX. */
size_t max_suffix, max_suffix_rev;
size_t j; /* Index into NEEDLE for current candidate suffix. */
size_t k; /* Offset into current period. */
size_t p; /* Intermediate period. */unsigned char a, b; /* Current comparison bytes. */
/* Invariants:
0 <= j < NEEDLE_LEN - 1
-1 <= max_suffix{,_rev} < j (treating SIZE_MAX as if it were signed)
min(max_suffix, max_suffix_rev) < global period of NEEDLE
1 <= p <= global period of NEEDLE
p == global period of the substring NEEDLE[max_suffix{,_rev}+1...j]
1 <= k <= p
*/
/* Perform lexicographic search. */
max_suffix = SIZE_MAX;
j = 0;
k = p = 1;
while (j + k < needle_len)
{
a = CANON_ELEMENT (needle[j + k]);
b = CANON_ELEMENT (needle[max_suffix + k]);
if (a < b)
{
/* Suffix is smaller, period is entire prefix so far. */
j += k;
k = 1;
p = j - max_suffix;
}
else if (a == b)
{
/* Advance through repetition of the current period. */if (k != p)
++k;
else
{
j += p;
k = 1;
}
}
else/* b < a */
{
/* Suffix is larger, start over from current location. */
max_suffix = j++;
k = p = 1;
}
}
*period = p;
/* Perform reverse lexicographic search. */
max_suffix_rev = SIZE_MAX;
j = 0;
k = p = 1;
while (j + k < needle_len)
{
a = CANON_ELEMENT (needle[j + k]);
b = CANON_ELEMENT (needle[max_suffix_rev + k]);
if (b < a)
{
/* Suffix is smaller, period is entire prefix so far. */
j += k;
k = 1;
p = j - max_suffix_rev;
}
else if (a == b)
{
/* Advance through repetition of the current period. */if (k != p)
++k;
else
{
j += p;
k = 1;
}
}
else/* a < b */
{
/* Suffix is larger, start over from current location. */
max_suffix_rev = j++;
k = p = 1;
}
}
/* Choose the longer suffix. Return the first byte of the right
half, rather than the last byte of the left half. */if (max_suffix_rev + 1 < max_suffix + 1)
return max_suffix + 1;
*period = p;
return max_suffix_rev + 1;
}
/* Return the first location of non-empty NEEDLE within HAYSTACK, or
NULL. HAYSTACK_LEN is the minimum known length of HAYSTACK. This
method is optimized for NEEDLE_LEN < LONG_NEEDLE_THRESHOLD.
Performance is guaranteed to be linear, with an initialization cost
of 2 * NEEDLE_LEN comparisons.
+
If AVAILABLE does not modify HAYSTACK_LEN (as in memmem), then at
most 2 * HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching.
If AVAILABLE modifies HAYSTACK_LEN (as in strstr), then at most 3 *
HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching. */static RETURN_TYPE
two_way_short_needle (const unsigned char *haystack, size_t haystack_len,
const unsigned char *needle, size_t needle_len)
{
size_t i; /* Index into current byte of NEEDLE. */
size_t j; /* Index into current window of HAYSTACK. */
size_t period; /* The period of the right half of needle. */
size_t suffix; /* The index of the right half of needle. */
/* Factor the needle into two halves, such that the left half is
smaller than the global period, and the right half is
periodic (with a period as large as NEEDLE_LEN - suffix). */
suffix = critical_factorization (needle, needle_len, &period);
/* Perform the search. Each iteration compares the right half
first. */if (CMP_FUNC (needle, needle + period, suffix) == 0)
{
/* Entire needle is periodic; a mismatch can only advance by the
period, so use memory to avoid rescanning known occurrences
of the period. */
size_t memory = 0;
j = 0;
while (AVAILABLE (haystack, haystack_len, j, needle_len))
{
/* Scan for matches in right half. */
i = MAX (suffix, memory);
while (i < needle_len && (CANON_ELEMENT (needle[i])
== CANON_ELEMENT (haystack[i + j])))
++i;
if (needle_len <= i)
{
/* Scan for matches in left half. */
i = suffix - 1;
while (memory < i + 1 && (CANON_ELEMENT (needle[i])
== CANON_ELEMENT (haystack[i + j])))
--i;
if (i + 1 < memory + 1)
return (RETURN_TYPE) (haystack + j);
/* No match, so remember how many repetitions of period
on the right half were scanned. */
j += period;
memory = needle_len - period;
}
else
{
j += i - suffix + 1;
memory = 0;
}
}
}
else
{
/* The two halves of needle are distinct; no extra memory is
required, and any mismatch results in a maximal shift. */
period = MAX (suffix, needle_len - suffix) + 1;
j = 0;
while (AVAILABLE (haystack, haystack_len, j, needle_len))
{
/* Scan for matches in right half. */
i = suffix;
while (i < needle_len && (CANON_ELEMENT (needle[i])
== CANON_ELEMENT (haystack[i + j])))
++i;
if (needle_len <= i)
{
/* Scan for matches in left half. */
i = suffix - 1;
while (i != SIZE_MAX && (CANON_ELEMENT (needle[i])
== CANON_ELEMENT (haystack[i + j])))
--i;
if (i == SIZE_MAX)
return (RETURN_TYPE) (haystack + j);
j += period;
}
else
j += i - suffix + 1;
}
}
return NULL;
}
/* Return the first location of non-empty NEEDLE within HAYSTACK, or
NULL. HAYSTACK_LEN is the minimum known length of HAYSTACK. This
method is optimized for LONG_NEEDLE_THRESHOLD <= NEEDLE_LEN.
Performance is guaranteed to be linear, with an initialization cost
of 3 * NEEDLE_LEN + (1 << CHAR_BIT) operations.
+
If AVAILABLE does not modify HAYSTACK_LEN (as in memmem), then at
most 2 * HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching,
and sublinear performance O(HAYSTACK_LEN / NEEDLE_LEN) is possible.
If AVAILABLE modifies HAYSTACK_LEN (as in strstr), then at most 3 *
HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching, and
sublinear performance is not possible. */static RETURN_TYPE two_way_long_needle (const unsigned char *haystack, size_t haystack_len,
const unsigned char *needle, size_t needle_len)
{
size_t i; /* Index into current byte of NEEDLE. */
size_t j; /* Index into current window of HAYSTACK. */
size_t period; /* The period of the right half of needle. */
size_t suffix; /* The index of the right half of needle. */
size_t shift_table[1U << CHAR_BIT]; /* See below. */
/* Factor the needle into two halves, such that the left half is
smaller than the global period, and the right half is
periodic (with a period as large as NEEDLE_LEN - suffix). */
suffix = critical_factorization (needle, needle_len, &period);
/* Populate shift_table. For each possible byte value c,
shift_table[c] is the distance from the last occurrence of c to
the end of NEEDLE, or NEEDLE_LEN if c is absent from the NEEDLE.
shift_table[NEEDLE[NEEDLE_LEN - 1]] contains the only 0. */for (i = 0; i < 1U << CHAR_BIT; i++)
shift_table[i] = needle_len;
for (i = 0; i < needle_len; i++)
shift_table[CANON_ELEMENT (needle[i])] = needle_len - i - 1;
/* Perform the search. Each iteration compares the right half
first. */if (CMP_FUNC (needle, needle + period, suffix) == 0)
{
/* Entire needle is periodic; a mismatch can only advance by the
period, so use memory to avoid rescanning known occurrences
of the period. */
size_t memory = 0;
size_t shift;
j = 0;
while (AVAILABLE (haystack, haystack_len, j, needle_len))
{
/* Check the last byte first; if it does not match, then
shift to the next possible match location. */
shift = shift_table[CANON_ELEMENT (haystack[j + needle_len - 1])];
if (0 < shift)
{
if (memory && shift < period)
{
/* Since needle is periodic, but the last period has
a byte out of place, there can be no match until
after the mismatch. */
shift = needle_len - period;
memory = 0;
}
j += shift;
continue;
}
/* Scan for matches in right half. The last byte has
already been matched, by virtue of the shift table. */
i = MAX (suffix, memory);
while (i < needle_len - 1 && (CANON_ELEMENT (needle[i])
== CANON_ELEMENT (haystack[i + j])))
++i;
if (needle_len - 1 <= i)
{
/* Scan for matches in left half. */
i = suffix - 1;
while (memory < i + 1 && (CANON_ELEMENT (needle[i])
== CANON_ELEMENT (haystack[i + j])))
--i;
if (i + 1 < memory + 1)
return (RETURN_TYPE) (haystack + j);
/* No match, so remember how many repetitions of period
on the right half were scanned. */
j += period;
memory = needle_len - period;
}
else
{
j += i - suffix + 1;
memory = 0;
}
}
}
else
{
/* The two halves of needle are distinct; no extra memory is
required, and any mismatch results in a maximal shift. */
size_t shift;
period = MAX (suffix, needle_len - suffix) + 1;
j = 0;
while (AVAILABLE (haystack, haystack_len, j, needle_len))
{
/* Check the last byte first; if it does not match, then
shift to the next possible match location. */
shift = shift_table[CANON_ELEMENT (haystack[j + needle_len - 1])];
if (0 < shift)
{
j += shift;
continue;
}
/* Scan for matches in right half. The last byte has
already been matched, by virtue of the shift table. */
i = suffix;
while (i < needle_len - 1 && (CANON_ELEMENT (needle[i])
== CANON_ELEMENT (haystack[i + j])))
++i;
if (needle_len - 1 <= i)
{
/* Scan for matches in left half. */
i = suffix - 1;
while (i != SIZE_MAX && (CANON_ELEMENT (needle[i])
== CANON_ELEMENT (haystack[i + j])))
--i;
if (i == SIZE_MAX)
return (RETURN_TYPE) (haystack + j);
j += period;
}
else
j += i - suffix + 1;
}
}
return NULL;
}
#undef AVAILABLE
#undef CANON_ELEMENT
#undef CMP_FUNC
#undef MAX
#undef RETURN_TYPE
#undef strstr
/* Return the first occurrence of NEEDLE in HAYSTACK. Return HAYSTACK
if NEEDLE is empty, otherwise NULL if NEEDLE is not found in
HAYSTACK. */const char *xistrchr(const char *haystack, char ch)
{
while (*haystack)
{
if (toupper(*haystack)==toupper(ch))
return haystack;
++haystack;
}
return NULL;
}
const char * gnu_ustrstr (const char *haystack_start, const char *needle_start)
{
const char *haystack = haystack_start;
const char *needle = needle_start;
size_t needle_len; /* Length of NEEDLE. */
size_t haystack_len; /* Known minimum length of HAYSTACK. */bool ok = true; /* True if NEEDLE is prefix of HAYSTACK. */
/* Determine length of NEEDLE, and in the process, make sure
HAYSTACK is at least as long (no point processing all of a long
NEEDLE if HAYSTACK is too short). */while (*haystack && *needle)
ok &= toupper(*haystack++) == toupper(*needle++);
if (*needle)
return NULL;
if (ok)
return (char *) haystack_start;
/* Reduce the size of haystack using xistrchr, since it has a smaller
linear coefficient than the Two-Way algorithm. */
needle_len = needle - needle_start;
haystack = xistrchr (haystack_start + 1, *needle_start);
if (!haystack || __builtin_expect (needle_len == 1, 0))
return (char *) haystack;
needle -= needle_len;
haystack_len = (haystack > haystack_start + needle_len ? 1
: needle_len + haystack_start - haystack);
/* Perform the search. Abstract memory is considered to be an array
of 'unsigned char' values, not an array of 'char' values. See
ISO C 99 section 6.2.6.1. */if (needle_len < LONG_NEEDLE_THRESHOLD)
return two_way_short_needle ((const unsigned char *) haystack,
haystack_len,
(const unsigned char *) needle, needle_len);
return two_way_long_needle ((const unsigned char *) haystack, haystack_len,
(const unsigned char *) needle, needle_len);
}
#undef LONG_NEEDLE_THRESHOLD
char * ustrstr( const char *source, const char *word)
{
const char *bp = word;
const char *back_pos;
while( *source != 0 && source != 0 && word != 0 )
{
back_pos = source;
while( toupper(*back_pos++) == toupper(*word++) )
{
if( *word == 0 )
{
return (char*)(back_pos-strlen(bp));
}
}
++source;
word = bp;
}
return 0;
}
void compare_strstri(const char *haystack, const char *needle)
{
DWORD ticks0 = ::GetTickCount();
const char * r1 = gnu_ustrstr (haystack, needle) ;
DWORD ticks1 = ::GetTickCount();
const char * r2 = ustrstr( haystack, needle);
DWORD ticks2 = ::GetTickCount();
if (r1!=r2)
printf("Error [0x%x!=0x%x]!\n", r1, r2);
else
printf("OK [0x%x==0x%x]!\n", r1, r2);
printf("gnu_ustrstr: %u msec, ustrstr: %u msec]\n", ticks1-ticks0, ticks2-ticks1);
}
void wmain(int argc, wchar_t **argv)
{
compare_strstri("aaaabbbaaa", "BBBa");
std::string haystack, needle;
haystack.resize(0x10000, 'x' );
needle.resize(0xfff, 'x' );
needle+='y';
compare_strstri(haystack.c_str(), needle.c_str());
haystack.resize(0x10000, 'x' );
needle.resize(0xfff, 'x' );
needle+='y';
haystack+= needle;
compare_strstri(haystack.c_str(), needle.c_str());
haystack.resize(0x10000, 'x' );
needle.resize(0xfff, 'x' );
needle+='y';
haystack.insert(haystack.size()/2, needle);
compare_strstri(haystack.c_str(), needle.c_str());
haystack.resize(0x10000, 'x' );
needle.resize(0xfff, 'x' );
needle.insert(needle.size()/2, "y");
haystack.insert(haystack.size()/2, needle);
compare_strstri(haystack.c_str(), needle.c_str());
haystack.resize(0x10000, 'x' );
needle.resize(0xfff, 'x' );
needle.insert(needle.size()/2, "y");
haystack.insert(haystack.size()/2, needle);
needle[needle.size()] = toupper(needle[needle.size()]);
compare_strstri(haystack.c_str(), needle.c_str());
return;
}
OK [0x403198==0x403198]!
gnu_ustrstr: 0 msec, ustrstr: 0 msec]
OK [0x0==0x0]!
gnu_ustrstr: 0 msec, ustrstr: 2532 msec]
OK [0xb61868==0xb61868]!
gnu_ustrstr: 0 msec, ustrstr: 2609 msec]
OK [0xb59868==0xb59868]!
gnu_ustrstr: 0 msec, ustrstr: 1297 msec]
OK [0xb59868==0xb59868]!
gnu_ustrstr: 0 msec, ustrstr: 656 msec]
OK [0xb59868==0xb59868]!
gnu_ustrstr: 0 msec, ustrstr: 625 msec]
ЗЫ как говорится, результат налицо.
ЗЗЫ полную работоспособность кода не гарантирую, возможно гдето забыл всунуть toupper, тк оригинальная ф-я — обычная strstr из libc
Как много веселых ребят, и все делают велосипед...
P>например когда в заголовке HTTP ответа нужно найти строку типа "Content-Length: "
Э, стоп, а вот тут уже начинается путаница.
Зачем в HTTP-ответе искать строку типа "Content-Length:"? Завтра нам попадётся ответ с заголовком "X-Zapadlo: preved; message='Content-Length: fsck you'", и, собственно, западло и превед.
HTTP-ответ надо парсить, построчно и посимвольно, строго по всем релевантным RFC (хотя бы 2822), а не искать в нём случайно взятые подстроки.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Изменить одну строчку надо (если есть только латинские буквы. PD> while ( *s1 && *s2 && !(*s1-*s2) ) PD>и при этом toupper не вызывать, а сделать вручную, потому что toupper работает с локалами (а как ей еще ?), а здесь надо банально проверить символ в интервале 'a'..'z' и если да — заменить на 'A'..'Z'
Это называется Костыль с большой буквы "К"
>переведи оба аргументя в верхний регистр (toupper) и сравни этой же функцией PD>можно так понимать — тогда я уже и не знаю, что сказать.
Ну зачем так буквально все понимать.
ps. я устал спорить, спасибо за разговор, думаю проблема уже решена, по крайней мере парочка реализаций есть, дальше топикастер сам решит что ему нужно а что нет.
Здравствуйте, Centaur, Вы писали:
C>Зачем в HTTP-ответе искать строку типа "Content-Length:"? Завтра нам попадётся ответ с заголовком "X-Zapadlo: preved; message='Content-Length: fsck you'", и, собственно, западло и превед.
А ведь это мысль! Можно (?) сделать эксплоит против тех, кто вместо RFC-шного парсинга использует рукодельный...
Перекуём баги на фичи!
