1 /*
2 * token.c - Token list handling functions
3 *
4 * This file is part of the SSH Library
5 *
6 * Copyright (c) 2003-2008 by Aris Adamantiadis
7 * Copyright (c) 2019 by Anderson Toshiyuki Sasaki - Red Hat, Inc.
8 *
9 * The SSH Library is free software; you can redistribute it and/or modify
10 * it under the terms of the GNU Lesser General Public License as published by
11 * the Free Software Foundation; either version 2.1 of the License, or (at your
12 * option) any later version.
13 *
14 * The SSH Library is distributed in the hope that it will be useful, but
15 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
16 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
17 * License for more details.
18 *
19 * You should have received a copy of the GNU Lesser General Public License
20 * along with the SSH Library; see the file COPYING. If not, write to
21 * the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
22 * MA 02111-1307, USA.
23 */
24
25 #include "config.h"
26
27 #include <stdio.h>
28 #include <string.h>
29 #include <stdbool.h>
30
31 #include "libssh/priv.h"
32 #include "libssh/token.h"
33
34 /**
35 * @internal
36 *
37 * @brief Free the given tokens list structure. The used buffer is overwritten
38 * with zeroes before freed.
39 *
40 * @param[in] tokens The pointer to a structure to be freed;
41 */
ssh_tokens_free(struct ssh_tokens_st * tokens)42 void ssh_tokens_free(struct ssh_tokens_st *tokens)
43 {
44 int i;
45 if (tokens == NULL) {
46 return;
47 }
48
49 if (tokens->tokens != NULL) {
50 for (i = 0; tokens->tokens[i] != NULL; i++) {
51 explicit_bzero(tokens->tokens[i], strlen(tokens->tokens[i]));
52 }
53 }
54
55 SAFE_FREE(tokens->buffer);
56 SAFE_FREE(tokens->tokens);
57 SAFE_FREE(tokens);
58 }
59
60 /**
61 * @internal
62 *
63 * @brief Split a given string on the given separator character. The returned
64 * structure holds an array of pointers (tokens) pointing to the obtained
65 * parts and a buffer where all the content of the list is stored. The last
66 * element of the array will always be set as NULL.
67 *
68 * @param[in] chain The string to split
69 * @param[in] separator The character used to separate the tokens.
70 *
71 * @return A newly allocated tokens list structure; NULL in case of error.
72 */
ssh_tokenize(const char * chain,char separator)73 struct ssh_tokens_st *ssh_tokenize(const char *chain, char separator)
74 {
75
76 struct ssh_tokens_st *tokens = NULL;
77 size_t num_tokens = 1, i = 1;
78
79 char *found, *c;
80
81 if (chain == NULL) {
82 return NULL;
83 }
84
85 tokens = calloc(1, sizeof(struct ssh_tokens_st));
86 if (tokens == NULL) {
87 return NULL;
88 }
89
90 tokens->buffer= strdup(chain);
91 if (tokens->buffer == NULL) {
92 goto error;
93 }
94
95 c = tokens->buffer;
96 do {
97 found = strchr(c, separator);
98 if (found != NULL) {
99 c = found + 1;
100 num_tokens++;
101 }
102 } while(found != NULL);
103
104 /* Allocate tokens list */
105 tokens->tokens = calloc(num_tokens + 1, sizeof(char *));
106 if (tokens->tokens == NULL) {
107 goto error;
108 }
109
110 /* First token starts in the beginning of the chain */
111 tokens->tokens[0] = tokens->buffer;
112 c = tokens->buffer;
113
114 for (i = 1; i < num_tokens; i++) {
115 /* Find next separator */
116 found = strchr(c, separator);
117 if (found == NULL) {
118 break;
119 }
120
121 /* Replace it with a string terminator */
122 *found = '\0';
123
124 /* The next token starts in the next byte */
125 c = found + 1;
126
127 /* If we did not reach the end of the chain yet, set the next token */
128 if (*c != '\0') {
129 tokens->tokens[i] = c;
130 } else {
131 break;
132 }
133 }
134
135 return tokens;
136
137 error:
138 ssh_tokens_free(tokens);
139 return NULL;
140 }
141
142 /**
143 * @internal
144 *
145 * @brief Given two strings, the first containing a list of available tokens and
146 * the second containing a list of tokens to be searched ordered by preference,
147 * returns a copy of the first preferred token present in the available list.
148 *
149 * @param[in] available_list The list of available tokens
150 * @param[in] preferred_list The list of tokens to search, ordered by
151 * preference
152 *
153 * @return A newly allocated copy of the token if found; NULL otherwise
154 */
ssh_find_matching(const char * available_list,const char * preferred_list)155 char *ssh_find_matching(const char *available_list,
156 const char *preferred_list)
157 {
158 struct ssh_tokens_st *a_tok = NULL, *p_tok = NULL;
159
160 int i, j;
161 char *ret = NULL;
162
163 if ((available_list == NULL) || (preferred_list == NULL)) {
164 return NULL;
165 }
166
167 a_tok = ssh_tokenize(available_list, ',');
168 if (a_tok == NULL) {
169 return NULL;
170 }
171
172 p_tok = ssh_tokenize(preferred_list, ',');
173 if (p_tok == NULL) {
174 goto out;
175 }
176
177 for (i = 0; p_tok->tokens[i]; i++) {
178 for (j = 0; a_tok->tokens[j]; j++) {
179 if (strcmp(a_tok->tokens[j], p_tok->tokens[i]) == 0) {
180 ret = strdup(a_tok->tokens[j]);
181 goto out;
182 }
183 }
184 }
185
186 out:
187 ssh_tokens_free(a_tok);
188 ssh_tokens_free(p_tok);
189 return ret;
190 }
191
192 /**
193 * @internal
194 *
195 * @brief Given two strings, the first containing a list of available tokens and
196 * the second containing a list of tokens to be searched ordered by preference,
197 * returns a list of all matching tokens ordered by preference.
198 *
199 * @param[in] available_list The list of available tokens
200 * @param[in] preferred_list The list of tokens to search, ordered by
201 * preference
202 *
203 * @return A newly allocated string containing the list of all matching tokens;
204 * NULL otherwise
205 */
ssh_find_all_matching(const char * available_list,const char * preferred_list)206 char *ssh_find_all_matching(const char *available_list,
207 const char *preferred_list)
208 {
209 struct ssh_tokens_st *a_tok = NULL, *p_tok = NULL;
210 int i, j;
211 char *ret = NULL;
212 size_t max, len, pos = 0;
213 int match;
214
215 if ((available_list == NULL) || (preferred_list == NULL)) {
216 return NULL;
217 }
218
219 max = MAX(strlen(available_list), strlen(preferred_list));
220
221 ret = calloc(1, max + 1);
222 if (ret == NULL) {
223 return NULL;
224 }
225
226 a_tok = ssh_tokenize(available_list, ',');
227 if (a_tok == NULL) {
228 SAFE_FREE(ret);
229 goto out;
230 }
231
232 p_tok = ssh_tokenize(preferred_list, ',');
233 if (p_tok == NULL) {
234 SAFE_FREE(ret);
235 goto out;
236 }
237
238 for (i = 0; p_tok->tokens[i] ; i++) {
239 for (j = 0; a_tok->tokens[j]; j++) {
240 match = !strcmp(a_tok->tokens[j], p_tok->tokens[i]);
241 if (match) {
242 if (pos != 0) {
243 ret[pos] = ',';
244 pos++;
245 }
246
247 len = strlen(a_tok->tokens[j]);
248 memcpy(&ret[pos], a_tok->tokens[j], len);
249 pos += len;
250 ret[pos] = '\0';
251 }
252 }
253 }
254
255 if (ret[0] == '\0') {
256 SAFE_FREE(ret);
257 }
258
259 out:
260 ssh_tokens_free(a_tok);
261 ssh_tokens_free(p_tok);
262 return ret;
263 }
264
265 /**
266 * @internal
267 *
268 * @brief Given a string containing a list of elements, remove all duplicates
269 * and return in a newly allocated string.
270 *
271 * @param[in] list The list to be freed of duplicates
272 *
273 * @return A newly allocated copy of the string free of duplicates; NULL in
274 * case of error.
275 */
ssh_remove_duplicates(const char * list)276 char *ssh_remove_duplicates(const char *list)
277 {
278 struct ssh_tokens_st *tok = NULL;
279
280 size_t i, j, num_tokens, max_len;
281 char *ret = NULL;
282 bool *should_copy = NULL, need_comma = false;
283
284 if (list == NULL) {
285 return NULL;
286 }
287
288 /* The maximum number of tokens is the size of the list */
289 max_len = strlen(list);
290 if (max_len == 0) {
291 return NULL;
292 }
293
294 /* Add space for ending '\0' */
295 max_len++;
296
297 tok = ssh_tokenize(list, ',');
298 if ((tok == NULL) || (tok->tokens == NULL) || (tok->tokens[0] == NULL)) {
299 goto out;
300 }
301
302 should_copy = calloc(1, max_len);
303 if (should_copy == NULL) {
304 goto out;
305 }
306
307 if (strlen(tok->tokens[0]) > 0) {
308 should_copy[0] = true;
309 }
310
311 for (i = 1; tok->tokens[i]; i++) {
312 for (j = 0; j < i; j++) {
313 if (strcmp(tok->tokens[i], tok->tokens[j]) == 0) {
314 /* Found a duplicate; do not copy */
315 should_copy[i] = false;
316 break;
317 }
318 }
319
320 /* No matching token before */
321 if (j == i) {
322 /* Only copy if it is not an empty string */
323 if (strlen(tok->tokens[i]) > 0) {
324 should_copy[i] = true;
325 } else {
326 should_copy[i] = false;
327 }
328 }
329 }
330
331 num_tokens = i;
332
333 ret = calloc(1, max_len);
334 if (ret == NULL) {
335 goto out;
336 }
337
338 for (i = 0; i < num_tokens; i++) {
339 if (should_copy[i]) {
340 if (need_comma) {
341 strncat(ret, ",", (max_len - strlen(ret) - 1));
342 }
343 strncat(ret, tok->tokens[i], (max_len - strlen(ret) - 1));
344 need_comma = true;
345 }
346 }
347
348 /* If no comma is needed, nothing was copied */
349 if (!need_comma) {
350 SAFE_FREE(ret);
351 }
352
353 out:
354 SAFE_FREE(should_copy);
355 ssh_tokens_free(tok);
356 return ret;
357 }
358
359 /**
360 * @internal
361 *
362 * @brief Given two strings containing lists of tokens, return a newly
363 * allocated string containing all the elements of the first list appended with
364 * all the elements of the second list, without duplicates. The order of the
365 * elements will be preserved.
366 *
367 * @param[in] list The first list
368 * @param[in] appended_list The list to be appended
369 *
370 * @return A newly allocated copy list containing all the elements of the
371 * kept_list appended with the elements of the appended_list without duplicates;
372 * NULL in case of error.
373 */
ssh_append_without_duplicates(const char * list,const char * appended_list)374 char *ssh_append_without_duplicates(const char *list,
375 const char *appended_list)
376 {
377 size_t concat_len = 0;
378 char *ret = NULL, *concat = NULL;
379
380 if (list != NULL) {
381 concat_len = strlen(list);
382 }
383
384 if (appended_list != NULL) {
385 concat_len += strlen(appended_list);
386 }
387
388 if (concat_len == 0) {
389 return NULL;
390 }
391
392 /* Add room for ending '\0' and for middle ',' */
393 concat_len += 2;
394 concat = calloc(1, concat_len);
395 if (concat == NULL) {
396 return NULL;
397 }
398
399 if (list != NULL) {
400 strcpy(concat, list);
401 strncat(concat, ",", concat_len - strlen(concat) - 1);
402 }
403 if (appended_list != NULL) {
404 strncat(concat, appended_list, concat_len - strlen(concat) - 1);
405 }
406
407 ret = ssh_remove_duplicates(concat);
408
409 SAFE_FREE(concat);
410
411 return ret;
412 }
413