uncrustify as demanded.
[oweals/gnunet.git] / src / util / regex.c
1 /*
2      This file is part of GNUnet
3      Copyright (C) 2012, 2013, 2015 GNUnet e.V.
4
5      GNUnet is free software: you can redistribute it and/or modify it
6      under the terms of the GNU Affero General Public License as published
7      by the Free Software Foundation, either version 3 of the License,
8      or (at your option) any later version.
9
10      GNUnet is distributed in the hope that it will be useful, but
11      WITHOUT ANY WARRANTY; without even the implied warranty of
12      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13      Affero General Public License for more details.
14
15      You should have received a copy of the GNU Affero General Public License
16      along with this program.  If not, see <http://www.gnu.org/licenses/>.
17
18      SPDX-License-Identifier: AGPL3.0-or-later
19  */
20 /**
21  * @file src/tun/regex.c
22  * @brief functions to convert IP networks to regexes
23  * @author Maximilian Szengel
24  * @author Christian Grothoff
25  */
26 #include "platform.h"
27 #include "gnunet_util_lib.h"
28 #include "gnunet_tun_lib.h"
29
30 /**
31  * 'wildcard', matches all possible values (for HEX encoding).
32  */
33 #define DOT "(0|1|2|3|4|5|6|7|8|9|A|B|C|D|E|F)"
34
35
36 /**
37  * Create a regex in @a rxstr from the given @a ip and @a netmask.
38  *
39  * @param ip IPv4 representation.
40  * @param port destination port
41  * @param rxstr generated regex, must be at least #GNUNET_TUN_IPV4_REGEXLEN
42  *              bytes long.
43  */
44 void
45 GNUNET_TUN_ipv4toregexsearch(const struct in_addr *ip,
46                              uint16_t port,
47                              char *rxstr)
48 {
49   GNUNET_snprintf(rxstr,
50                   GNUNET_TUN_IPV4_REGEXLEN,
51                   "4-%04X-%08X",
52                   (unsigned int)port,
53                   ntohl(ip->s_addr));
54 }
55
56
57 /**
58  * Create a regex in @a rxstr from the given @a ipv6 and @a prefixlen.
59  *
60  * @param ipv6 IPv6 representation.
61  * @param port destination port
62  * @param rxstr generated regex, must be at least #GNUNET_TUN_IPV6_REGEXLEN
63  *              bytes long.
64  */
65 void
66 GNUNET_TUN_ipv6toregexsearch(const struct in6_addr *ipv6,
67                              uint16_t port,
68                              char *rxstr)
69 {
70   const uint32_t *addr;
71
72   addr = (const uint32_t *)ipv6;
73   GNUNET_snprintf(rxstr,
74                   GNUNET_TUN_IPV6_REGEXLEN,
75                   "6-%04X-%08X%08X%08X%08X",
76                   (unsigned int)port,
77                   ntohl(addr[0]),
78                   ntohl(addr[1]),
79                   ntohl(addr[2]),
80                   ntohl(addr[3]));
81 }
82
83
84 /**
85  * Convert the given 4-bit (!) number to a regex.
86  *
87  * @param value the value, only the lowest 4 bits will be looked at
88  * @param mask which bits in value are wildcards (any value)?
89  */
90 static char *
91 nibble_to_regex(uint8_t value,
92                 uint8_t mask)
93 {
94   char *ret;
95
96   value &= mask;
97   switch (mask)
98     {
99     case 0:
100       return GNUNET_strdup(DOT);
101
102     case 8:
103       GNUNET_asprintf(&ret,
104                       "(%X|%X|%X|%X|%X|%X|%X|%X)",
105                       value,
106                       value + 1,
107                       value + 2,
108                       value + 3,
109                       value + 4,
110                       value + 5,
111                       value + 6,
112                       value + 7);
113       return ret;
114
115     case 12:
116       GNUNET_asprintf(&ret,
117                       "(%X|%X|%X|%X)",
118                       value,
119                       value + 1,
120                       value + 2,
121                       value + 3);
122       return ret;
123
124     case 14:
125       GNUNET_asprintf(&ret,
126                       "(%X|%X)",
127                       value,
128                       value + 1);
129       return ret;
130
131     case 15:
132       GNUNET_asprintf(&ret,
133                       "%X",
134                       value);
135       return ret;
136
137     default:
138       GNUNET_log(GNUNET_ERROR_TYPE_WARNING,
139                  _("Bad mask: %d\n"),
140                  mask);
141       GNUNET_break(0);
142       return NULL;
143     }
144 }
145
146
147 /**
148  * Convert the given 16-bit number to a regex.
149  *
150  * @param value the value
151  * @param mask which bits in value are wildcards (any value)?
152  */
153 static char *
154 num_to_regex(uint16_t value,
155              uint16_t mask)
156 {
157   const uint8_t *v = (const uint8_t *)&value;
158   const uint8_t *m = (const uint8_t *)&mask;
159   char *a;
160   char *b;
161   char *c;
162   char *d;
163   char *ret;
164
165   a = nibble_to_regex(v[0] >> 4, m[0] >> 4);
166   b = nibble_to_regex(v[0] & 15, m[0] & 15);
167   c = nibble_to_regex(v[1] >> 4, m[1] >> 4);
168   d = nibble_to_regex(v[1] & 15, m[1] & 15);
169   ret = NULL;
170   if ((NULL != a) &&
171       (NULL != b) &&
172       (NULL != c) &&
173       (NULL != d))
174     GNUNET_asprintf(&ret,
175                     "%s%s%s%s",
176                     a, b, c, d);
177   GNUNET_free_non_null(a);
178   GNUNET_free_non_null(b);
179   GNUNET_free_non_null(c);
180   GNUNET_free_non_null(d);
181   return ret;
182 }
183
184
185 /**
186  * Do we need to put parents around the given argument?
187  *
188  * @param arg part of a regular expression
189  * @return #GNUNET_YES if we should parens,
190  *         #GNUNET_NO if not
191  */
192 static int
193 needs_parens(const char *arg)
194 {
195   size_t off;
196   size_t len;
197   unsigned int op;
198
199   op = 0;
200   len = strlen(arg);
201   for (off = 0; off < len; off++)
202     {
203       switch (arg[off])
204         {
205         case '(':
206           op++;
207           break;
208
209         case ')':
210           GNUNET_assert(op > 0);
211           op--;
212           break;
213
214         case '|':
215           if (0 == op)
216             return GNUNET_YES;
217           break;
218
219         default:
220           break;
221         }
222     }
223   return GNUNET_NO;
224 }
225
226
227 /**
228  * Compute port policy for the given range of
229  * port numbers.
230  *
231  * @param start starting offset
232  * @param end end offset
233  * @param step increment level (power of 16)
234  * @param pp port policy to convert
235  * @return corresponding regex
236  */
237 static char *
238 compute_policy(unsigned int start,
239                unsigned int end,
240                unsigned int step,
241                const struct GNUNET_STRINGS_PortPolicy *pp)
242 {
243   unsigned int i;
244   char before[36]; /* 16 * 2 + 3 dots + 0-terminator */
245   char middlel[33]; /* 16 * 2 + 0-terminator */
246   char middleh[33]; /* 16 * 2 + 0-terminator */
247   char after[36]; /* 16 * 2 + 3 dots + 0-terminator */
248   char beforep[36 + 2]; /* 16 * 2 + 3 dots + 0-terminator + ()*/
249   char middlehp[33 + 2]; /* 16 * 2 + 0-terminator + () */
250   char middlelp[33 + 2]; /* 16 * 2 + 0-terminator + () */
251   char afterp[36 + 2]; /* 16 * 2 + 3 dots + 0-terminator + () */
252   char dots[5 * strlen(DOT)];
253   char buf[3];
254   char *middle;
255   char *ret;
256   unsigned int xstep;
257   char *recl;
258   char *rech;
259   char *reclp;
260   char *rechp;
261   unsigned int start_port;
262   unsigned int end_port;
263
264   GNUNET_assert(GNUNET_YES == pp->negate_portrange);
265   start_port = pp->start_port;
266   if (1 == start_port)
267     start_port = 0;
268   end_port = pp->end_port;
269   GNUNET_assert((end - start) / step <= 0xF);
270   before[0] = '\0';
271   middlel[0] = '\0';
272   middleh[0] = '\0';
273   after[0] = '\0';
274   for (i = start; i <= end; i += step)
275     {
276       GNUNET_snprintf(buf,
277                       sizeof(buf),
278                       "%X|",
279                       (i - start) / step);
280       if (i / step < start_port / step)
281         strcat(before, buf);
282       else if (i / step > end_port / step)
283         strcat(after, buf);
284       else if (i / step == start_port / step)
285         strcat(middlel, buf);
286       else if (i / step == end_port / step)
287         strcat(middleh, buf);
288     }
289   if (strlen(before) > 0)
290     before[strlen(before) - 1] = '\0';
291   if (strlen(middlel) > 0)
292     middlel[strlen(middlel) - 1] = '\0';
293   if (strlen(middleh) > 0)
294     middleh[strlen(middleh) - 1] = '\0';
295   if (strlen(after) > 0)
296     after[strlen(after) - 1] = '\0';
297   if (needs_parens(before))
298     GNUNET_snprintf(beforep,
299                     sizeof(beforep),
300                     "(%s)",
301                     before);
302   else
303     strcpy(beforep, before);
304   if (needs_parens(middlel))
305     GNUNET_snprintf(middlelp,
306                     sizeof(middlelp),
307                     "(%s)",
308                     middlel);
309   else
310     strcpy(middlelp, middlel);
311   if (needs_parens(middleh))
312     GNUNET_snprintf(middlehp,
313                     sizeof(middlehp),
314                     "(%s)",
315                     middleh);
316   else
317     strcpy(middlehp, middleh);
318   if (needs_parens(after))
319     GNUNET_snprintf(afterp,
320                     sizeof(afterp),
321                     "(%s)",
322                     after);
323   else
324     strcpy(afterp, after);
325   dots[0] = '\0';
326   for (xstep = step / 16; xstep > 0; xstep /= 16)
327     strcat(dots, DOT);
328   if (step >= 16)
329     {
330       if (strlen(middlel) > 0)
331         recl = compute_policy((start_port / step) * step,
332                               (start_port / step) * step + step - 1,
333                               step / 16,
334                               pp);
335       else
336         recl = GNUNET_strdup("");
337       if (strlen(middleh) > 0)
338         rech = compute_policy((end_port / step) * step,
339                               (end_port / step) * step + step - 1,
340                               step / 16,
341                               pp);
342       else
343         rech = GNUNET_strdup("");
344     }
345   else
346     {
347       recl = GNUNET_strdup("");
348       rech = GNUNET_strdup("");
349       middlel[0] = '\0';
350       middlelp[0] = '\0';
351       middleh[0] = '\0';
352       middlehp[0] = '\0';
353     }
354   if (needs_parens(recl))
355     GNUNET_asprintf(&reclp,
356                     "(%s)",
357                     recl);
358   else
359     reclp = GNUNET_strdup(recl);
360   if (needs_parens(rech))
361     GNUNET_asprintf(&rechp,
362                     "(%s)",
363                     rech);
364   else
365     rechp = GNUNET_strdup(rech);
366
367   if ((strlen(middleh) > 0) &&
368       (strlen(rech) > 0) &&
369       (strlen(middlel) > 0) &&
370       (strlen(recl) > 0))
371     {
372       GNUNET_asprintf(&middle,
373                       "%s%s|%s%s",
374                       middlel,
375                       reclp,
376                       middleh,
377                       rechp);
378     }
379   else if ((strlen(middleh) > 0) &&
380            (strlen(rech) > 0))
381     {
382       GNUNET_asprintf(&middle,
383                       "%s%s",
384                       middleh,
385                       rechp);
386     }
387   else if ((strlen(middlel) > 0) &&
388            (strlen(recl) > 0))
389     {
390       GNUNET_asprintf(&middle,
391                       "%s%s",
392                       middlel,
393                       reclp);
394     }
395   else
396     {
397       middle = GNUNET_strdup("");
398     }
399   if ((strlen(before) > 0) &&
400       (strlen(after) > 0))
401     {
402       if (strlen(dots) > 0)
403         {
404           if (strlen(middle) > 0)
405             GNUNET_asprintf(&ret,
406                             "(%s%s|%s|%s%s)",
407                             beforep, dots,
408                             middle,
409                             afterp, dots);
410           else
411             GNUNET_asprintf(&ret,
412                             "(%s|%s)%s",
413                             beforep,
414                             afterp,
415                             dots);
416         }
417       else
418         {
419           if (strlen(middle) > 0)
420             GNUNET_asprintf(&ret,
421                             "(%s|%s|%s)",
422                             before,
423                             middle,
424                             after);
425           else if (1 == step)
426             GNUNET_asprintf(&ret,
427                             "%s|%s",
428                             before,
429                             after);
430           else
431             GNUNET_asprintf(&ret,
432                             "(%s|%s)",
433                             before,
434                             after);
435         }
436     }
437   else if (strlen(before) > 0)
438     {
439       if (strlen(dots) > 0)
440         {
441           if (strlen(middle) > 0)
442             GNUNET_asprintf(&ret,
443                             "(%s%s|%s)",
444                             beforep, dots,
445                             middle);
446           else
447             GNUNET_asprintf(&ret,
448                             "%s%s",
449                             beforep, dots);
450         }
451       else
452         {
453           if (strlen(middle) > 0)
454             GNUNET_asprintf(&ret,
455                             "(%s|%s)",
456                             before,
457                             middle);
458           else
459             GNUNET_asprintf(&ret,
460                             "%s",
461                             before);
462         }
463     }
464   else if (strlen(after) > 0)
465     {
466       if (strlen(dots) > 0)
467         {
468           if (strlen(middle) > 0)
469             GNUNET_asprintf(&ret,
470                             "(%s|%s%s)",
471                             middle,
472                             afterp, dots);
473           else
474             GNUNET_asprintf(&ret,
475                             "%s%s",
476                             afterp, dots);
477         }
478       else
479         {
480           if (strlen(middle) > 0)
481             GNUNET_asprintf(&ret,
482                             "%s|%s",
483                             middle,
484                             after);
485           else
486             GNUNET_asprintf(&ret,
487                             "%s",
488                             after);
489         }
490     }
491   else if (strlen(middle) > 0)
492     {
493       GNUNET_asprintf(&ret,
494                       "%s",
495                       middle);
496     }
497   else
498     {
499       ret = GNUNET_strdup("");
500     }
501   GNUNET_free(middle);
502   GNUNET_free(reclp);
503   GNUNET_free(rechp);
504   GNUNET_free(recl);
505   GNUNET_free(rech);
506   return ret;
507 }
508
509
510 /**
511  * Convert a port policy to a regular expression.  Note: this is a
512  * very simplistic implementation, we might want to consider doing
513  * something more sophisiticated (resulting in smaller regular
514  * expressions) at a later time.
515  *
516  * @param pp port policy to convert
517  * @return NULL on error
518  */
519 static char *
520 port_to_regex(const struct GNUNET_STRINGS_PortPolicy *pp)
521 {
522   char *reg;
523   char *ret;
524   char *pos;
525   unsigned int i;
526   unsigned int cnt;
527
528   if ((0 == pp->start_port) ||
529       ((1 == pp->start_port) &&
530        (0xFFFF == pp->end_port) &&
531        (GNUNET_NO == pp->negate_portrange)))
532     return GNUNET_strdup(DOT DOT DOT DOT);
533   if ((pp->start_port == pp->end_port) &&
534       (GNUNET_NO == pp->negate_portrange))
535     {
536       GNUNET_asprintf(&ret,
537                       "%04X",
538                       pp->start_port);
539       return ret;
540     }
541   if (pp->end_port < pp->start_port)
542     return NULL;
543
544   if (GNUNET_YES == pp->negate_portrange)
545     {
546       ret = compute_policy(0, 0xFFFF, 0x1000, pp);
547     }
548   else
549     {
550       cnt = pp->end_port - pp->start_port + 1;
551       reg = GNUNET_malloc(cnt * 5 + 1);
552       pos = reg;
553       for (i = 1; i <= 0xFFFF; i++)
554         {
555           if ((i >= pp->start_port) && (i <= pp->end_port))
556             {
557               if (pos == reg)
558                 {
559                   GNUNET_snprintf(pos,
560                                   5,
561                                   "%04X",
562                                   i);
563                 }
564               else
565                 {
566                   GNUNET_snprintf(pos,
567                                   6,
568                                   "|%04X",
569                                   i);
570                 }
571               pos += strlen(pos);
572             }
573         }
574       GNUNET_asprintf(&ret,
575                       "(%s)",
576                       reg);
577       GNUNET_free(reg);
578     }
579   return ret;
580 }
581
582
583 /**
584  * Convert an address (IPv4 or IPv6) to a regex.
585  *
586  * @param addr address
587  * @param mask network mask
588  * @param len number of bytes in @a addr and @a mask
589  * @return NULL on error, otherwise regex for the address
590  */
591 static char *
592 address_to_regex(const void *addr,
593                  const void *mask,
594                  size_t len)
595 {
596   const uint16_t *a = addr;
597   const uint16_t *m = mask;
598   char *ret;
599   char *tmp;
600   char *reg;
601   unsigned int i;
602
603   ret = NULL;
604   GNUNET_assert(1 != (len % 2));
605   for (i = 0; i < len / 2; i++)
606     {
607       reg = num_to_regex(a[i], m[i]);
608       if (NULL == reg)
609         {
610           GNUNET_free_non_null(ret);
611           return NULL;
612         }
613       if (NULL == ret)
614         {
615           ret = reg;
616         }
617       else
618         {
619           GNUNET_asprintf(&tmp,
620                           "%s%s",
621                           ret, reg);
622           GNUNET_free(ret);
623           GNUNET_free(reg);
624           ret = tmp;
625         }
626     }
627   return ret;
628 }
629
630
631 /**
632  * Convert a single line of an IPv4 policy to a regular expression.
633  *
634  * @param v4 line to convert
635  * @return NULL on error
636  */
637 static char *
638 ipv4_to_regex(const struct GNUNET_STRINGS_IPv4NetworkPolicy *v4)
639 {
640   char *reg;
641   char *pp;
642   char *ret;
643
644   reg = address_to_regex(&v4->network,
645                          &v4->netmask,
646                          sizeof(struct in_addr));
647   if (NULL == reg)
648     return NULL;
649   pp = port_to_regex(&v4->pp);
650   if (NULL == pp)
651     {
652       GNUNET_free(reg);
653       return NULL;
654     }
655   GNUNET_asprintf(&ret,
656                   "4-%s-%s",
657                   pp, reg);
658   GNUNET_free(pp);
659   GNUNET_free(reg);
660   return ret;
661 }
662
663
664 /**
665  * Convert a single line of an IPv4 policy to a regular expression.
666  *
667  * @param v6 line to convert
668  * @return NULL on error
669  */
670 static char *
671 ipv6_to_regex(const struct GNUNET_STRINGS_IPv6NetworkPolicy *v6)
672 {
673   char *reg;
674   char *pp;
675   char *ret;
676
677   reg = address_to_regex(&v6->network,
678                          &v6->netmask,
679                          sizeof(struct in6_addr));
680   if (NULL == reg)
681     return NULL;
682   pp = port_to_regex(&v6->pp);
683   if (NULL == pp)
684     {
685       GNUNET_free(reg);
686       return NULL;
687     }
688   GNUNET_asprintf(&ret,
689                   "6-%s-%s",
690                   pp, reg);
691   GNUNET_free(pp);
692   GNUNET_free(reg);
693   return ret;
694 }
695
696
697 /**
698  * Convert an exit policy to a regular expression.  The exit policy
699  * specifies a set of subnets this peer is willing to serve as an
700  * exit for; the resulting regular expression will match the
701  * IPv4 address strings as returned by #GNUNET_TUN_ipv4toregexsearch().
702  *
703  * @param policy exit policy specification
704  * @return regular expression, NULL on error
705  */
706 char *
707 GNUNET_TUN_ipv4policy2regex(const char *policy)
708 {
709   struct GNUNET_STRINGS_IPv4NetworkPolicy *np;
710   char *reg;
711   char *tmp;
712   char *line;
713   unsigned int i;
714
715   np = GNUNET_STRINGS_parse_ipv4_policy(policy);
716   if (NULL == np)
717     return NULL;
718   reg = NULL;
719   for (i = 0; (0 == i) || (0 != np[i].network.s_addr); i++)
720     {
721       line = ipv4_to_regex(&np[i]);
722       if (NULL == line)
723         {
724           GNUNET_free_non_null(reg);
725           GNUNET_free(np);
726           return NULL;
727         }
728       if (NULL == reg)
729         {
730           reg = line;
731         }
732       else
733         {
734           GNUNET_asprintf(&tmp,
735                           "%s|(%s)",
736                           reg, line);
737           GNUNET_free(reg);
738           GNUNET_free(line);
739           reg = tmp;
740         }
741       if (0 == np[i].network.s_addr)
742         break;
743     }
744   GNUNET_free(np);
745   return reg;
746 }
747
748
749 /**
750  * Convert an exit policy to a regular expression.  The exit policy
751  * specifies a set of subnets this peer is willing to serve as an
752  * exit for; the resulting regular expression will match the
753  * IPv6 address strings as returned by #GNUNET_TUN_ipv6toregexsearch().
754  *
755  * @param policy exit policy specification
756  * @return regular expression, NULL on error
757  */
758 char *
759 GNUNET_TUN_ipv6policy2regex(const char *policy)
760 {
761   struct in6_addr zero;
762   struct GNUNET_STRINGS_IPv6NetworkPolicy *np;
763   char *reg;
764   char *tmp;
765   char *line;
766   unsigned int i;
767
768   np = GNUNET_STRINGS_parse_ipv6_policy(policy);
769   if (NULL == np)
770     return NULL;
771   reg = NULL;
772   memset(&zero, 0, sizeof(struct in6_addr));
773   for (i = 0; (0 == i) || (0 != memcmp(&zero, &np[i].network, sizeof(struct in6_addr))); i++)
774     {
775       line = ipv6_to_regex(&np[i]);
776       if (NULL == line)
777         {
778           GNUNET_free_non_null(reg);
779           GNUNET_free(np);
780           return NULL;
781         }
782       if (NULL == reg)
783         {
784           reg = line;
785         }
786       else
787         {
788           GNUNET_asprintf(&tmp,
789                           "%s|(%s)",
790                           reg, line);
791           GNUNET_free(reg);
792           GNUNET_free(line);
793           reg = tmp;
794         }
795       if (0 == memcmp(&zero, &np[i].network, sizeof(struct in6_addr)))
796         break;
797     }
798   GNUNET_free(np);
799   return reg;
800 }
801
802
803 /**
804  * Hash the service name of a hosted service to the
805  * hash code that is used to identify the service on
806  * the network.
807  *
808  * @param service_name a string
809  * @param hc corresponding hash
810  */
811 void
812 GNUNET_TUN_service_name_to_hash(const char *service_name,
813                                 struct GNUNET_HashCode *hc)
814 {
815   GNUNET_CRYPTO_hash(service_name,
816                      strlen(service_name),
817                      hc);
818 }
819
820
821 /**
822  * Compute the CADET port given a service descriptor
823  * (returned from #GNUNET_TUN_service_name_to_hash) and
824  * a TCP/UDP port @a ip_port.
825  *
826  * @param desc service shared secret
827  * @param ip_port TCP/UDP port, use 0 for ICMP
828  * @param[out] cadet_port CADET port to use
829  */
830 void
831 GNUNET_TUN_compute_service_cadet_port(const struct GNUNET_HashCode *desc,
832                                       uint16_t ip_port,
833                                       struct GNUNET_HashCode *cadet_port)
834 {
835   uint16_t be_port = htons(ip_port);
836
837   *cadet_port = *desc;
838   GNUNET_memcpy(cadet_port,
839                 &be_port,
840                 sizeof(uint16_t));
841 }
842
843
844 /* end of regex.c */