Mercurial > dovecot > core-2.2
annotate src/lib/str-find.c @ 22664:fea53c2725c0
director: Fix director_max_parallel_moves/kicks type
Should be uint, not time.
| author | Timo Sirainen <timo.sirainen@dovecot.fi> |
|---|---|
| date | Thu, 09 Nov 2017 12:24:16 +0200 |
| parents | 2e2563132d5f |
| children | cb108f786fb4 |
| rev | line source |
|---|---|
|
21390
2e2563132d5f
Updated copyright notices to include the year 2017.
Stephan Bosch <stephan.bosch@dovecot.fi>
parents:
21323
diff
changeset
|
1 /* Copyright (c) 2007-2017 Dovecot authors, see the included COPYING file */ |
| 5520 | 2 |
|
7441
ffd549b542c5
str_find_init() allocated too little memory for temporary suffixes buffer.
Timo Sirainen <tss@iki.fi>
parents:
7086
diff
changeset
|
3 /* @UNSAFE: whole file */ |
|
ffd549b542c5
str_find_init() allocated too little memory for temporary suffixes buffer.
Timo Sirainen <tss@iki.fi>
parents:
7086
diff
changeset
|
4 |
| 5520 | 5 #include "lib.h" |
| 6 #include "str-find.h" | |
| 7 | |
| 8 struct str_find_context { | |
| 9 pool_t pool; | |
| 10 unsigned char *key; | |
| 11 unsigned int key_len; | |
| 12 | |
| 13 unsigned int *matches; | |
| 14 unsigned int match_count; | |
| 15 | |
|
8995
c8ba50450f12
Added str_find_get_match_end_pos(). Added unit testing.
Timo Sirainen <tss@iki.fi>
parents:
8590
diff
changeset
|
16 size_t match_end_pos; |
|
c8ba50450f12
Added str_find_get_match_end_pos(). Added unit testing.
Timo Sirainen <tss@iki.fi>
parents:
8590
diff
changeset
|
17 |
| 5520 | 18 int badtab[UCHAR_MAX+1]; |
|
7997
0d66b44689ee
Fixed compiling on some older pre-C99 compilers.
Timo Sirainen <tss@iki.fi>
parents:
7443
diff
changeset
|
19 int goodtab[FLEXIBLE_ARRAY_MEMBER]; |
| 5520 | 20 }; |
| 21 | |
| 22 static void init_badtab(struct str_find_context *ctx) | |
| 23 { | |
| 24 unsigned int i, len_1 = ctx->key_len - 1; | |
| 25 | |
| 26 for (i = 0; i <= UCHAR_MAX; i++) | |
| 27 ctx->badtab[i] = ctx->key_len; | |
| 28 | |
| 29 for (i = 0; i < len_1; i++) | |
| 30 ctx->badtab[ctx->key[i]] = len_1 - i; | |
| 31 } | |
| 32 | |
| 33 static void init_suffixes(struct str_find_context *ctx, unsigned int *suffixes) | |
| 34 { | |
| 35 unsigned int len_1 = ctx->key_len - 1; | |
| 36 int f = 0, g, i; | |
| 37 | |
| 38 suffixes[len_1] = ctx->key_len; | |
| 39 g = len_1; | |
|
15909
f74bf0521d69
Avoid under/overflows in unsigned integer calculations.
Timo Sirainen <tss@iki.fi>
parents:
15715
diff
changeset
|
40 for (i = (int)ctx->key_len - 2; i >= 0; i--) { |
| 5520 | 41 if (i > g && (int)suffixes[i + len_1 - f] < i - g) |
| 42 suffixes[i] = suffixes[i + len_1 - f]; | |
| 43 else { | |
| 44 if (i < g) | |
| 45 g = i; | |
| 46 f = i; | |
| 47 while (g >= 0 && ctx->key[g] == ctx->key[g + len_1 - f]) | |
| 48 g--; | |
| 49 suffixes[i] = f - g; | |
| 50 } | |
| 51 } | |
| 52 } | |
| 53 | |
| 54 static void init_goodtab(struct str_find_context *ctx) | |
| 55 { | |
|
15909
f74bf0521d69
Avoid under/overflows in unsigned integer calculations.
Timo Sirainen <tss@iki.fi>
parents:
15715
diff
changeset
|
56 unsigned int *suffixes; |
|
f74bf0521d69
Avoid under/overflows in unsigned integer calculations.
Timo Sirainen <tss@iki.fi>
parents:
15715
diff
changeset
|
57 int j, i, len_1 = ctx->key_len - 1; |
| 5520 | 58 |
|
7441
ffd549b542c5
str_find_init() allocated too little memory for temporary suffixes buffer.
Timo Sirainen <tss@iki.fi>
parents:
7086
diff
changeset
|
59 suffixes = t_buffer_get(sizeof(*suffixes) * ctx->key_len); |
| 5520 | 60 init_suffixes(ctx, suffixes); |
| 61 | |
| 62 for (i = 0; i < (int)ctx->key_len; i++) | |
| 63 ctx->goodtab[i] = ctx->key_len; | |
| 64 | |
| 65 j = 0; | |
| 66 for (i = len_1; i >= -1; i--) { | |
| 67 if (i < 0 || suffixes[i] == (unsigned int)i + 1) { | |
| 68 for (; j < len_1 - i; j++) { | |
| 69 if (ctx->goodtab[j] == (int)ctx->key_len) | |
| 70 ctx->goodtab[j] = len_1 - i; | |
| 71 } | |
| 72 } | |
| 73 } | |
| 74 for (i = 0; i <= (int)ctx->key_len - 2; i++) | |
| 75 ctx->goodtab[len_1 - suffixes[i]] = len_1 - i; | |
| 76 } | |
|
7441
ffd549b542c5
str_find_init() allocated too little memory for temporary suffixes buffer.
Timo Sirainen <tss@iki.fi>
parents:
7086
diff
changeset
|
77 |
| 5520 | 78 struct str_find_context *str_find_init(pool_t pool, const char *key) |
| 79 { | |
| 80 struct str_find_context *ctx; | |
|
21322
5ab8dc1a4a6f
global: Change string position/length from unsigned int to size_t
Timo Sirainen <timo.sirainen@dovecot.fi>
parents:
19552
diff
changeset
|
81 size_t key_len = strlen(key); |
| 5520 | 82 |
|
8995
c8ba50450f12
Added str_find_get_match_end_pos(). Added unit testing.
Timo Sirainen <tss@iki.fi>
parents:
8590
diff
changeset
|
83 i_assert(key_len > 0); |
|
21322
5ab8dc1a4a6f
global: Change string position/length from unsigned int to size_t
Timo Sirainen <timo.sirainen@dovecot.fi>
parents:
19552
diff
changeset
|
84 i_assert(key_len < INT_MAX); |
|
8995
c8ba50450f12
Added str_find_get_match_end_pos(). Added unit testing.
Timo Sirainen <tss@iki.fi>
parents:
8590
diff
changeset
|
85 |
|
21323
d223fad9767f
global: Make sure *_malloc() calculations won't cause integer overflows.
Timo Sirainen <timo.sirainen@dovecot.fi>
parents:
21322
diff
changeset
|
86 ctx = p_malloc(pool, MALLOC_ADD(sizeof(struct str_find_context), |
|
d223fad9767f
global: Make sure *_malloc() calculations won't cause integer overflows.
Timo Sirainen <timo.sirainen@dovecot.fi>
parents:
21322
diff
changeset
|
87 MALLOC_MULTIPLY(sizeof(ctx->goodtab[0]), key_len))); |
| 5520 | 88 ctx->pool = pool; |
|
7443
00d3b46f61e6
matches[] wasn't also allocated enough memory.
Timo Sirainen <tss@iki.fi>
parents:
7441
diff
changeset
|
89 ctx->matches = p_new(pool, unsigned int, key_len); |
| 5520 | 90 ctx->key_len = key_len; |
| 91 ctx->key = p_malloc(pool, key_len); | |
| 92 memcpy(ctx->key, key, key_len); | |
| 93 | |
| 94 init_goodtab(ctx); | |
| 95 init_badtab(ctx); | |
| 96 return ctx; | |
| 97 } | |
| 98 | |
| 99 void str_find_deinit(struct str_find_context **_ctx) | |
| 100 { | |
| 101 struct str_find_context *ctx = *_ctx; | |
| 102 | |
| 103 *_ctx = NULL; | |
| 104 p_free(ctx->pool, ctx->matches); | |
| 105 p_free(ctx->pool, ctx->key); | |
| 106 p_free(ctx->pool, ctx); | |
| 107 } | |
| 108 | |
| 109 bool str_find_more(struct str_find_context *ctx, | |
| 110 const unsigned char *data, size_t size) | |
| 111 { | |
| 112 unsigned int key_len = ctx->key_len; | |
| 113 unsigned int i, j, a, b; | |
| 114 int bad_value; | |
| 115 | |
| 116 for (i = j = 0; i < ctx->match_count; i++) { | |
| 117 a = ctx->matches[i]; | |
| 118 if (ctx->matches[i] + size >= key_len) { | |
| 119 /* we can fully determine this match now */ | |
| 120 for (; a < key_len; a++) { | |
| 121 if (ctx->key[a] != data[a - ctx->matches[i]]) | |
| 122 break; | |
| 123 } | |
| 124 | |
|
8995
c8ba50450f12
Added str_find_get_match_end_pos(). Added unit testing.
Timo Sirainen <tss@iki.fi>
parents:
8590
diff
changeset
|
125 if (a == key_len) { |
|
c8ba50450f12
Added str_find_get_match_end_pos(). Added unit testing.
Timo Sirainen <tss@iki.fi>
parents:
8590
diff
changeset
|
126 ctx->match_end_pos = key_len - ctx->matches[i]; |
| 5520 | 127 return TRUE; |
|
8995
c8ba50450f12
Added str_find_get_match_end_pos(). Added unit testing.
Timo Sirainen <tss@iki.fi>
parents:
8590
diff
changeset
|
128 } |
| 5520 | 129 } else { |
| 130 for (b = 0; b < size; b++) { | |
| 131 if (ctx->key[a+b] != data[b]) | |
| 132 break; | |
| 133 } | |
| 134 | |
| 135 if (b == size) | |
| 136 ctx->matches[j++] = a + size; | |
| 137 } | |
| 138 } | |
| 139 if (j > 0) { | |
| 140 i_assert(j + size < key_len); | |
| 141 ctx->match_count = j; | |
| 142 j = 0; | |
| 143 } else { | |
| 144 /* Boyer-Moore searching */ | |
| 145 j = 0; | |
| 146 while (j + key_len <= size) { | |
| 147 i = key_len - 1; | |
| 148 while (ctx->key[i] == data[i + j]) { | |
|
8995
c8ba50450f12
Added str_find_get_match_end_pos(). Added unit testing.
Timo Sirainen <tss@iki.fi>
parents:
8590
diff
changeset
|
149 if (i == 0) { |
|
c8ba50450f12
Added str_find_get_match_end_pos(). Added unit testing.
Timo Sirainen <tss@iki.fi>
parents:
8590
diff
changeset
|
150 ctx->match_end_pos = j + key_len; |
| 5520 | 151 return TRUE; |
|
8995
c8ba50450f12
Added str_find_get_match_end_pos(). Added unit testing.
Timo Sirainen <tss@iki.fi>
parents:
8590
diff
changeset
|
152 } |
| 5520 | 153 i--; |
| 154 } | |
| 155 | |
|
15909
f74bf0521d69
Avoid under/overflows in unsigned integer calculations.
Timo Sirainen <tss@iki.fi>
parents:
15715
diff
changeset
|
156 bad_value = (int)(ctx->badtab[data[i + j]] + i + 1) - |
|
f74bf0521d69
Avoid under/overflows in unsigned integer calculations.
Timo Sirainen <tss@iki.fi>
parents:
15715
diff
changeset
|
157 (int)key_len; |
| 5520 | 158 j += I_MAX(ctx->goodtab[i], bad_value); |
| 159 } | |
| 160 i_assert(j <= size); | |
| 161 ctx->match_count = 0; | |
| 162 } | |
| 163 | |
| 164 for (; j < size; j++) { | |
| 165 for (i = j; i < size; i++) { | |
| 166 if (ctx->key[i-j] != data[i]) | |
| 167 break; | |
| 168 } | |
| 169 if (i == size) | |
| 170 ctx->matches[ctx->match_count++] = size - j; | |
| 171 } | |
| 172 return FALSE; | |
| 173 } | |
| 174 | |
|
8995
c8ba50450f12
Added str_find_get_match_end_pos(). Added unit testing.
Timo Sirainen <tss@iki.fi>
parents:
8590
diff
changeset
|
175 size_t str_find_get_match_end_pos(struct str_find_context *ctx) |
|
c8ba50450f12
Added str_find_get_match_end_pos(). Added unit testing.
Timo Sirainen <tss@iki.fi>
parents:
8590
diff
changeset
|
176 { |
|
c8ba50450f12
Added str_find_get_match_end_pos(). Added unit testing.
Timo Sirainen <tss@iki.fi>
parents:
8590
diff
changeset
|
177 return ctx->match_end_pos; |
|
c8ba50450f12
Added str_find_get_match_end_pos(). Added unit testing.
Timo Sirainen <tss@iki.fi>
parents:
8590
diff
changeset
|
178 } |
|
c8ba50450f12
Added str_find_get_match_end_pos(). Added unit testing.
Timo Sirainen <tss@iki.fi>
parents:
8590
diff
changeset
|
179 |
| 5520 | 180 void str_find_reset(struct str_find_context *ctx) |
| 181 { | |
| 182 ctx->match_count = 0; | |
| 183 } |