From eba3b1535d33c93949d0d53234ffb373772de1a5 Mon Sep 17 00:00:00 2001 From: Vsevolod Stakhov Date: Thu, 12 Dec 2019 17:59:36 +0000 Subject: [PATCH] [Fix] Fix O(N^2) algorithm --- src/libmime/mime_expressions.c | 43 ++++++++++++++++++++++++---------- 1 file changed, 30 insertions(+), 13 deletions(-) diff --git a/src/libmime/mime_expressions.c b/src/libmime/mime_expressions.c index e797bb9b6..ea46233ec 100644 --- a/src/libmime/mime_expressions.c +++ b/src/libmime/mime_expressions.c @@ -1309,6 +1309,19 @@ struct addr_list { guint addrlen; }; +static gint +addr_list_cmp_func (const void *a, const void *b) +{ + const struct addr_list *addra = (struct addr_list *)a, + *addrb = (struct addr_list *)b; + + if (addra->addrlen != addrb->addrlen) { + return addra->addrlen - addrb->addrlen; + } + + return memcmp (addra->addr, addrb->addr, addra->addrlen); +} + #define COMPARE_RCPT_LEN 3 #define MIN_RCPT_TO_COMPARE 7 @@ -1320,7 +1333,7 @@ rspamd_recipients_distance (struct rspamd_task *task, GArray * args, struct rspamd_email_address *cur; double threshold; struct addr_list *ar; - gint num, i, j, hits = 0, total = 0; + gint num, i, hits = 0; if (args == NULL) { msg_warn_task ("no parameters to function"); @@ -1356,27 +1369,31 @@ rspamd_recipients_distance (struct rspamd_task *task, GArray * args, ar = rspamd_mempool_alloc0 (task->task_pool, num * sizeof (struct addr_list)); /* Fill array */ + num = 0; PTR_ARRAY_FOREACH (MESSAGE_FIELD (task, rcpt_mime), i, cur) { - ar[i].name = cur->addr; - ar[i].namelen = cur->addr_len; - ar[i].addr = cur->domain; - ar[i].addrlen = cur->domain_len; + if (cur->addr_len > COMPARE_RCPT_LEN) { + ar[num].name = cur->addr; + ar[num].namelen = cur->addr_len; + ar[num].addr = cur->domain; + ar[num].addrlen = cur->domain_len; + num ++; + } } + qsort (ar, num, sizeof (*ar), addr_list_cmp_func); + /* Cycle all elements in array */ for (i = 0; i < num; i++) { - for (j = i + 1; j < num; j++) { - if (ar[i].namelen >= COMPARE_RCPT_LEN && ar[j].namelen >= COMPARE_RCPT_LEN && - rspamd_lc_cmp (ar[i].name, ar[j].name, COMPARE_RCPT_LEN) == 0) { - /* Common name part */ - hits++; + if (i < num - 1) { + if (ar[i].namelen == ar[i + 1].namelen) { + if (rspamd_lc_cmp (ar[i].name, ar[i + 1].name, COMPARE_RCPT_LEN) == 0) { + hits++; + } } - - total++; } } - if ((hits * num / 2.) / (double)total >= threshold) { + if ((hits * num / 2.) / (double)num >= threshold) { return TRUE; } -- 2.39.5