Нашли или выдавили из себя код, который нельзя назвать нормальным,
на который без улыбки не взглянешь?
Не торопитесь его удалять или рефакторить, — запостите его на
говнокод.ру, посмеёмся вместе!
Взгляните например на вот этот вот пиздец (я его откомментировал):
int rbad = 0, n;
for (i = 0; pv[i]; i++) {
// вот тут проверяем что в начале идет "http" кусок
if (pv[i] == 'h' && pv[i + 1] == 't' && pv[i + 2] == 't' && pv[i + 3] == 'p') {
// какая-то ебучая add переменная
int add = 0;
if (pv[i + 4] == 's') {
// которая будет равна 1 если у нас https, ну это чтоб ебаное смещение правильно учитывать
// "https" на один байтик длинней, чем "http"
add = 1;
}
// дальше проверяем остальной кусок урла, тут вот например видно, что если https урл
// то тогда это говно начинает проверять с адреса на одну единицу больше
// в этом блядском говне проверяется кусок "://" который должен идти после http(s)
if (pv[i + 4 + add] == ':' && pv[i + 5 + add] == '/' && pv[i + 6 + add] == '/') {
// это цикл, в котором тупо прокручивается кусок, отвечающий за доменное имя
// т.е. по pv[j] будет конец доменного имени
for (j = i + 7 + add; is_domain_symbol (pv[j]); j++) ;
// если нихрена прокручено не было, то continue...
// т.е. бля, на следующей итерации это блядское говно будет пытаться заматчить
// эту сраную http(s):// парашу уже начиная не с pv[0], а с pv[1]
if (j == i + 7 + add) {
continue;
}
// это оно проверяет порт после доменного имени, т.е. "https://example.org:8080"
if (pv[j] == ':') {
j++;
while ('0' <= pv[j] && pv[j] <= '9') {
j++;
}
}
...
Как думаете, сраные вконтактовские долбоебы-олимпиадники, писавшие эту хуйню, слышали например про алгоритм Ахо-Корасик или Бойера-Мура?
> слышали например про алгоритм Ахо-Корасик или Бойера-Мура?
Я думаю, что они слышали. А ты слышал?
Бойер-Мур и Ахо-Корасик строят автоматы для поиска одного или нескольких (в случае А-К) шаблонов в строке. Т.е. по сути это реализация find(needle(s), haystack). Как это поможет тебе для парсинга урла в один проход?
Ну смотри, надо заматчить "http://" и "https://" Очевидно, что в качестве шаблона отлично подойдет "http??/", где "?" это неважно какой символ:
http://
https://
http??/
После заматчивания подобной хрени, можно в "?" проверить, было ли там "http://" или "https://" или вообще некая иная хрень, и дальше или пытаться это парсить дальше как урл, или искать в другом месте начало урла
> Ну смотри, надо заматчить "http://" и "https://"
Т.е. ты предлагаешь строить по отдельному автомату только для того, чтобы заматчить каждый компонент урла?
Типа это будет быстрее/лучше, чем последовательность рукописных автоматов на сишке?
Или нужно снова автоматы из сишных комментариев генерить? Или семантику описывать на Coq с кодогенератором?
Код может и не идеальный, но идеологически против такого подхода я против ничего не имею. Кмк, оптимальный трейдофф в плане speed/running time/development time. Это скорее ты упоротый, а не вк-олимпиадники.
т.е. если подобный говнокод выполняется где-то на бэкенде и кто-то без капчи и регистрации может туда отправлять текстовые данные, которые через такое говно прокручиваются, можно запросто заDDoSить, отправляя кучу таких дебильных строк
Кстати я думаю можно даже хитрее поступить, например максимально пытаться заставить обосраться предсказатель переходов в интеловском говнопроцессоре, типа нагеренировать какого-то такого пиздеца
Вообще тут можно довольно эффективную эвристику придумать, например проверять некий символ на то, что в нем нет никаких символов, которые есть в "https://"
например, проверяя символ в позиции
?
hui pizda jigurda govno lorem ipsum http://govnokod.ru/
на 'h' 't' 'p' 's' ':' '/' (такая проверка очень быстрой будет, если через таблицу поиска)
и не найдя совпадений, мы тут отечем сразу кучу вариантов
и не нужно будет продрачивать последовательно по байтику эту сраную строку,
можно смело шагать по ней широкими шагами
?
hui pizda jigurda govno lorem ipsum http://govnokod.ru/
https:// |
http:// |
https:// |
http:// |
https:// |
http:// |
https:// | то, сколько вариантов мы отсекаем
http:// |
https:// |
http:// |
https:// |
http:// |
https://|
http:// |
V
И теперь аналогичную говнопроверку можно сделать вот в этой позиции
?
hui pizda jigurda govno lorem ipsum http://govnokod.ru/
https:// |
http:// |
https:// |
http:// |
https:// |
http:// |
https:// |
http:// |
https:// |
http:// |
https:// |
http:// |
https://|
http:// |
V
ну и так далее, и это будет намного быстрее работать,
чем то тупое говно, написанное вконтактовыми олимпиадниками
зачем? Быстрее пройти uint32_t'ом "http" по массиву пока не встретишь, а остальное уже отдельно обработать "https://" можно фильтровать сразу через uint64_t. Если прям так нужно быстродействие, можно еще simd захреначить (c load_u).
Тут не будет худшего случая. Вряд ли кто-то будет специально вхерачивать какое-то говно, типа
httphttphttphttphttphttp
чтобы затормозить парсер. Да и тут такой подход будет избыточен. Например
httphttphttphttphttphttp
http <- ага, вот тут мы заматчили кусок урла
пытаемся дальше
httphttphttphttphttphttp
https:// <- нет
http:// <- нет
теперь попробуем по новому смещению
httphttphttphttphttphttp
http <- вот тут уже полная лажа начинается
http <- нет смысла в этих тупых проверках
т.к. там уже было провенено и заматчено http
и прогонять эти байты смысла нет
начинать новую проверку имеет смысл отсюда
httphttphttphttphttphttp
http
в общем даже тупую проверку на совпадение "http" куска можно заоптимизировать
худший в плане реализации процессора, если не брать совсем говно мамонта. И да: как я уже написал, можно и по 8 байт брать ("https://") или 8, но со сдвигом на 8 ("\0http://")
Ты можешь сколько угодно бомбиться об этот код, но олимпиадничек его написал достаточно оптимально и забыл, потому что он больше нахуй не кому не нужен, потому что в нем баги врядли есть.
Интересно, а вот если взять какую-то выскоуровневную функцию типа memcmp
и вместо
pv[i] == 'h' && pv[i + 1] == 't' && pv[i + 2] == 't' && pv[i + 3] == 'p'
сделать
Как думаете, сраные вконтактовские долбоебы-олимпиадники, писавшие эту хуйню, слышали например про алгоритм Ахо-Корасик или Бойера-Мура?
Я думаю, что они слышали. А ты слышал?
Бойер-Мур и Ахо-Корасик строят автоматы для поиска одного или нескольких (в случае А-К) шаблонов в строке. Т.е. по сути это реализация find(needle(s), haystack). Как это поможет тебе для парсинга урла в один проход?
После заматчивания подобной хрени, можно в "?" проверить, было ли там "http://" или "https://" или вообще некая иная хрень, и дальше или пытаться это парсить дальше как урл, или искать в другом месте начало урла
Т.е. ты предлагаешь строить по отдельному автомату только для того, чтобы заматчить каждый компонент урла?
Типа это будет быстрее/лучше, чем последовательность рукописных автоматов на сишке?
Или нужно снова автоматы из сишных комментариев генерить? Или семантику описывать на Coq с кодогенератором?
Код может и не идеальный, но идеологически против такого подхода я против ничего не имею. Кмк, оптимальный трейдофф в плане speed/running time/development time. Это скорее ты упоротый, а не вк-олимпиадники.
Нет, не оптимальный. Этот код кстати довольно легко можно затормозить, подсунув какие-нибудь специальные входные говноданные, типа
т.е. если подобный говнокод выполняется где-то на бэкенде и кто-то без капчи и регистрации может туда отправлять текстовые данные, которые через такое говно прокручиваются, можно запросто заDDoSить, отправляя кучу таких дебильных строк
по-твоему это будет быстрее?
чтобы затормозить парсер. Да и тут такой подход будет избыточен. Например
в общем даже тупую проверку на совпадение "http" куска можно заоптимизировать
Насчет "достаточно оптимально" - вранье. Этот код ОЧЕНЬ НЕОПТИМАЛЬНЫЙ. Про более оптимальные методы - читай мои же комментарии к этому говнокоду
и вместо
pv[i] == 'h' && pv[i + 1] == 't' && pv[i + 2] == 't' && pv[i + 3] == 'p'
сделать
..то vk сразу же начнет тормозить, ляжет под нагрузкой и программиста выгонят?