contrib/libpcap/gencode.c

   1 /*#define CHASE_CHAIN*/
   2 /*
   3  * Copyright (c) 1990, 1991, 1992, 1993, 1994, 1995, 1996, 1997, 1998
   4  *      The Regents of the University of California.  All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that: (1) source code distributions
   8  * retain the above copyright notice and this paragraph in its entirety, (2)
   9  * distributions including binary code include the above copyright notice and
  10  * this paragraph in its entirety in the documentation or other materials
  11  * provided with the distribution, and (3) all advertising materials mentioning
  12  * features or use of this software display the following acknowledgement:
  13  * ``This product includes software developed by the University of California,
  14  * Lawrence Berkeley Laboratory and its contributors.'' Neither the name of
  15  * the University nor the names of its contributors may be used to endorse
  16  * or promote products derived from this software without specific prior
  17  * written permission.
  18  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
  19  * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
  20  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  21  *
  22  * $FreeBSD$
  23  */
  24 #ifndef lint
  25 static const char rcsid[] =
  26     "@(#) $Header: /tcpdump/master/libpcap/gencode.c,v 1.140.2.1 2001/01/14 06:48:35 guy Exp $ (LBL)";
  27 #endif
  28
  29 #ifdef HAVE_CONFIG_H
  30 #include "config.h"
  31 #endif
  32
  33 #include <sys/types.h>
  34 #include <sys/socket.h>
  35 #include <sys/time.h>
  36 #ifdef __NetBSD__
  37 #include <sys/param.h>
  38 #endif
  39
  40 struct mbuf;
  41 struct rtentry;
  42 #include <net/if.h>
  43
  44 #include <netinet/in.h>
  45
  46 #include <stdlib.h>
  47 #include <string.h>
  48 #include <memory.h>
  49 #include <setjmp.h>
  50 #include <stdarg.h>
  51
  52 #include "pcap-int.h"
  53
  54 #include "ethertype.h"
  55 #include "nlpid.h"
  56 #include "gencode.h"
  57 #include "ppp.h"
  58 #include "sll.h"
  59 #include <pcap-namedb.h>
  60 #ifdef INET6
  61 #include <netdb.h>
  62 #include <sys/socket.h>
  63 #endif /*INET6*/
  64
  65 #define LLC_SNAP_LSAP   0xaa
  66 #define LLC_ISO_LSAP    0xfe
  67
  68 #undef ETHERMTU
  69 #define ETHERMTU        1500
  70
  71 #ifdef HAVE_OS_PROTO_H
  72 #include "os-proto.h"
  73 #endif
  74
  75 #define JMP(c) ((c)|BPF_JMP|BPF_K)
  76
  77 /* Locals */
  78 static jmp_buf top_ctx;
  79 static pcap_t *bpf_pcap;
  80
  81 /* XXX */
  82 #ifdef PCAP_FDDIPAD
  83 int     pcap_fddipad = PCAP_FDDIPAD;
  84 #else
  85 int     pcap_fddipad;
  86 #endif
  87
  88 /* VARARGS */
  89 void
  90 bpf_error(const char *fmt, ...)
  91
  92 {
  93         va_list ap;
  94
  95         va_start(ap, fmt);
  96         if (bpf_pcap != NULL)
  97                 (void)vsnprintf(pcap_geterr(bpf_pcap), PCAP_ERRBUF_SIZE,
  98                     fmt, ap);
  99         va_end(ap);
 100         longjmp(top_ctx, 1);
 101         /* NOTREACHED */
 102 }
 103
 104 static void init_linktype(int);
 105
 106 static int alloc_reg(void);
 107 static void free_reg(int);
 108
 109 static struct block *root;
 110
 111 /*
 112  * We divy out chunks of memory rather than call malloc each time so
 113  * we don't have to worry about leaking memory.  It's probably
 114  * not a big deal if all this memory was wasted but it this ever
 115  * goes into a library that would probably not be a good idea.
 116  */
 117 #define NCHUNKS 16
 118 #define CHUNK0SIZE 1024
 119 struct chunk {
 120         u_int n_left;
 121         void *m;
 122 };
 123
 124 static struct chunk chunks[NCHUNKS];
 125 static int cur_chunk;
 126
 127 static void *newchunk(u_int);
 128 static void freechunks(void);
 129 static inline struct block *new_block(int);
 130 static inline struct slist *new_stmt(int);
 131 static struct block *gen_retblk(int);
 132 static inline void syntax(void);
 133
 134 static void backpatch(struct block *, struct block *);
 135 static void merge(struct block *, struct block *);
 136 static struct block *gen_cmp(u_int, u_int, bpf_int32);
 137 static struct block *gen_cmp_gt(u_int, u_int, bpf_int32);
 138 static struct block *gen_mcmp(u_int, u_int, bpf_int32, bpf_u_int32);
 139 static struct block *gen_bcmp(u_int, u_int, const u_char *);
 140 static struct block *gen_uncond(int);
 141 static inline struct block *gen_true(void);
 142 static inline struct block *gen_false(void);
 143 static struct block *gen_linktype(int);
 144 static struct block *gen_snap(bpf_u_int32, bpf_u_int32, u_int);
 145 static struct block *gen_hostop(bpf_u_int32, bpf_u_int32, int, int, u_int, u_int);
 146 #ifdef INET6
 147 static struct block *gen_hostop6(struct in6_addr *, struct in6_addr *, int, int, u_int, u_int);
 148 #endif
 149 static struct block *gen_ehostop(const u_char *, int);
 150 static struct block *gen_fhostop(const u_char *, int);
 151 static struct block *gen_thostop(const u_char *, int);
 152 static struct block *gen_dnhostop(bpf_u_int32, int, u_int);
 153 static struct block *gen_host(bpf_u_int32, bpf_u_int32, int, int);
 154 #ifdef INET6
 155 static struct block *gen_host6(struct in6_addr *, struct in6_addr *, int, int);
 156 #endif
 157 #ifndef INET6
 158 static struct block *gen_gateway(const u_char *, bpf_u_int32 **, int, int);
 159 #endif
 160 static struct block *gen_ipfrag(void);
 161 static struct block *gen_portatom(int, bpf_int32);
 162 #ifdef INET6
 163 static struct block *gen_portatom6(int, bpf_int32);
 164 #endif
 165 struct block *gen_portop(int, int, int);
 166 static struct block *gen_port(int, int, int);
 167 #ifdef INET6
 168 struct block *gen_portop6(int, int, int);
 169 static struct block *gen_port6(int, int, int);
 170 #endif
 171 static int lookup_proto(const char *, int);
 172 static struct block *gen_protochain(int, int, int);
 173 static struct block *gen_proto(int, int, int);
 174 static struct slist *xfer_to_x(struct arth *);
 175 static struct slist *xfer_to_a(struct arth *);
 176 static struct block *gen_len(int, int);
 177
 178 static void *
 179 newchunk(n)
 180         u_int n;
 181 {
 182         struct chunk *cp;
 183         int k, size;
 184
 185 #ifndef __NetBSD__
 186         /* XXX Round up to nearest long. */
 187         n = (n + sizeof(long) - 1) & ~(sizeof(long) - 1);
 188 #else
 189         /* XXX Round up to structure boundary. */
 190         n = ALIGN(n);
 191 #endif
 192
 193         cp = &chunks[cur_chunk];
 194         if (n > cp->n_left) {
 195                 ++cp, k = ++cur_chunk;
 196                 if (k >= NCHUNKS)
 197                         bpf_error("out of memory");
 198                 size = CHUNK0SIZE << k;
 199                 cp->m = (void *)malloc(size);
 200                 memset((char *)cp->m, 0, size);
 201                 cp->n_left = size;
 202                 if (n > size)
 203                         bpf_error("out of memory");
 204         }
 205         cp->n_left -= n;
 206         return (void *)((char *)cp->m + cp->n_left);
 207 }
 208
 209 static void
 210 freechunks()
 211 {
 212         int i;
 213
 214         cur_chunk = 0;
 215         for (i = 0; i < NCHUNKS; ++i)
 216                 if (chunks[i].m != NULL) {
 217                         free(chunks[i].m);
 218                         chunks[i].m = NULL;
 219                 }
 220 }
 221
 222 /*
 223  * A strdup whose allocations are freed after code generation is over.
 224  */
 225 char *
 226 sdup(s)
 227         register const char *s;
 228 {
 229         int n = strlen(s) + 1;
 230         char *cp = newchunk(n);
 231
 232         strlcpy(cp, s, n);
 233         return (cp);
 234 }
 235
 236 static inline struct block *
 237 new_block(code)
 238         int code;
 239 {
 240         struct block *p;
 241
 242         p = (struct block *)newchunk(sizeof(*p));
 243         p->s.code = code;
 244         p->head = p;
 245
 246         return p;
 247 }
 248
 249 static inline struct slist *
 250 new_stmt(code)
 251         int code;
 252 {
 253         struct slist *p;
 254
 255         p = (struct slist *)newchunk(sizeof(*p));
 256         p->s.code = code;
 257
 258         return p;
 259 }
 260
 261 static struct block *
 262 gen_retblk(v)
 263         int v;
 264 {
 265         struct block *b = new_block(BPF_RET|BPF_K);
 266
 267         b->s.k = v;
 268         return b;
 269 }
 270
 271 static inline void
 272 syntax()
 273 {
 274         bpf_error("syntax error in filter expression");
 275 }
 276
 277 static bpf_u_int32 netmask;
 278 static int snaplen;
 279 int no_optimize;
 280
 281 int
 282 pcap_compile(pcap_t *p, struct bpf_program *program,
 283              char *buf, int optimize, bpf_u_int32 mask)
 284 {
 285         extern int n_errors;
 286         int len;
 287
 288         no_optimize = 0;
 289         n_errors = 0;
 290         root = NULL;
 291         bpf_pcap = p;
 292         if (setjmp(top_ctx)) {
 293                 lex_cleanup();
 294                 freechunks();
 295                 return (-1);
 296         }
 297
 298         netmask = mask;
 299
 300         snaplen = pcap_snapshot(p);
 301         if (snaplen == 0) {
 302                 snprintf(p->errbuf, PCAP_ERRBUF_SIZE,
 303                          "snaplen of 0 rejects all packets");
 304                 return -1;
 305         }
 306
 307         lex_init(buf ? buf : "");
 308         init_linktype(pcap_datalink(p));
 309         (void)pcap_parse();
 310
 311         if (n_errors)
 312                 syntax();
 313
 314         if (root == NULL)
 315                 root = gen_retblk(snaplen);
 316
 317         if (optimize && !no_optimize) {
 318                 bpf_optimize(&root);
 319                 if (root == NULL ||
 320                     (root->s.code == (BPF_RET|BPF_K) && root->s.k == 0))
 321                         bpf_error("expression rejects all packets");
 322         }
 323         program->bf_insns = icode_to_fcode(root, &len);
 324         program->bf_len = len;
 325
 326         lex_cleanup();
 327         freechunks();
 328         return (0);
 329 }
 330
 331 /*
 332  * entry point for using the compiler with no pcap open
 333  * pass in all the stuff that is needed explicitly instead.
 334  */
 335 int
 336 pcap_compile_nopcap(int snaplen_arg, int linktype_arg,
 337                     struct bpf_program *program,
 338              char *buf, int optimize, bpf_u_int32 mask)
 339 {
 340         pcap_t *p;
 341         int ret;
 342
 343         p = pcap_open_dead(linktype_arg, snaplen_arg);
 344         if (p == NULL)
 345                 return (-1);
 346         ret = pcap_compile(p, program, buf, optimize, mask);
 347         pcap_close(p);
 348         return (ret);
 349 }
 350
 351 /*
 352  * Clean up a "struct bpf_program" by freeing all the memory allocated
 353  * in it.
 354  */
 355 void
 356 pcap_freecode(struct bpf_program *program)
 357 {
 358         program->bf_len = 0;
 359         if (program->bf_insns != NULL) {
 360                 free((char *)program->bf_insns);
 361                 program->bf_insns = NULL;
 362         }
 363 }
 364
 365 /*
 366  * Backpatch the blocks in 'list' to 'target'.  The 'sense' field indicates
 367  * which of the jt and jf fields has been resolved and which is a pointer
 368  * back to another unresolved block (or nil).  At least one of the fields
 369  * in each block is already resolved.
 370  */
 371 static void
 372 backpatch(list, target)
 373         struct block *list, *target;
 374 {
 375         struct block *next;
 376
 377         while (list) {
 378                 if (!list->sense) {
 379                         next = JT(list);
 380                         JT(list) = target;
 381                 } else {
 382                         next = JF(list);
 383                         JF(list) = target;
 384                 }
 385                 list = next;
 386         }
 387 }
 388
 389 /*
 390  * Merge the lists in b0 and b1, using the 'sense' field to indicate
 391  * which of jt and jf is the link.
 392  */
 393 static void
 394 merge(b0, b1)
 395         struct block *b0, *b1;
 396 {
 397         register struct block **p = &b0;
 398
 399         /* Find end of list. */
 400         while (*p)
 401                 p = !((*p)->sense) ? &JT(*p) : &JF(*p);
 402
 403         /* Concatenate the lists. */
 404         *p = b1;
 405 }
 406
 407 void
 408 finish_parse(p)
 409         struct block *p;
 410 {
 411         backpatch(p, gen_retblk(snaplen));
 412         p->sense = !p->sense;
 413         backpatch(p, gen_retblk(0));
 414         root = p->head;
 415 }
 416
 417 void
 418 gen_and(b0, b1)
 419         struct block *b0, *b1;
 420 {
 421         backpatch(b0, b1->head);
 422         b0->sense = !b0->sense;
 423         b1->sense = !b1->sense;
 424         merge(b1, b0);
 425         b1->sense = !b1->sense;
 426         b1->head = b0->head;
 427 }
 428
 429 void
 430 gen_or(b0, b1)
 431         struct block *b0, *b1;
 432 {
 433         b0->sense = !b0->sense;
 434         backpatch(b0, b1->head);
 435         b0->sense = !b0->sense;
 436         merge(b1, b0);
 437         b1->head = b0->head;
 438 }
 439
 440 void
 441 gen_not(b)
 442         struct block *b;
 443 {
 444         b->sense = !b->sense;
 445 }
 446
 447 static struct block *
 448 gen_cmp(offset, size, v)
 449         u_int offset, size;
 450         bpf_int32 v;
 451 {
 452         struct slist *s;
 453         struct block *b;
 454
 455         s = new_stmt(BPF_LD|BPF_ABS|size);
 456         s->s.k = offset;
 457
 458         b = new_block(JMP(BPF_JEQ));
 459         b->stmts = s;
 460         b->s.k = v;
 461
 462         return b;
 463 }
 464
 465 static struct block *
 466 gen_cmp_gt(offset, size, v)
 467         u_int offset, size;
 468         bpf_int32 v;
 469 {
 470         struct slist *s;
 471         struct block *b;
 472
 473         s = new_stmt(BPF_LD|BPF_ABS|size);
 474         s->s.k = offset;
 475
 476         b = new_block(JMP(BPF_JGT));
 477         b->stmts = s;
 478         b->s.k = v;
 479
 480         return b;
 481 }
 482
 483 static struct block *
 484 gen_mcmp(offset, size, v, mask)
 485         u_int offset, size;
 486         bpf_int32 v;
 487         bpf_u_int32 mask;
 488 {
 489         struct block *b = gen_cmp(offset, size, v);
 490         struct slist *s;
 491
 492         if (mask != 0xffffffff) {
 493                 s = new_stmt(BPF_ALU|BPF_AND|BPF_K);
 494                 s->s.k = mask;
 495                 b->stmts->next = s;
 496         }
 497         return b;
 498 }
 499
 500 static struct block *
 501 gen_bcmp(offset, size, v)
 502         register u_int offset, size;
 503         register const u_char *v;
 504 {
 505         register struct block *b, *tmp;
 506
 507         b = NULL;
 508         while (size >= 4) {
 509                 register const u_char *p = &v[size - 4];
 510                 bpf_int32 w = ((bpf_int32)p[0] << 24) |
 511                     ((bpf_int32)p[1] << 16) | ((bpf_int32)p[2] << 8) | p[3];
 512
 513                 tmp = gen_cmp(offset + size - 4, BPF_W, w);
 514                 if (b != NULL)
 515                         gen_and(b, tmp);
 516                 b = tmp;
 517                 size -= 4;
 518         }
 519         while (size >= 2) {
 520                 register const u_char *p = &v[size - 2];
 521                 bpf_int32 w = ((bpf_int32)p[0] << 8) | p[1];
 522
 523                 tmp = gen_cmp(offset + size - 2, BPF_H, w);
 524                 if (b != NULL)
 525                         gen_and(b, tmp);
 526                 b = tmp;
 527                 size -= 2;
 528         }
 529         if (size > 0) {
 530                 tmp = gen_cmp(offset, BPF_B, (bpf_int32)v[0]);
 531                 if (b != NULL)
 532                         gen_and(b, tmp);
 533                 b = tmp;
 534         }
 535         return b;
 536 }
 537
 538 /*
 539  * Various code constructs need to know the layout of the data link
 540  * layer.  These variables give the necessary offsets.  off_linktype
 541  * is set to -1 for no encapsulation, in which case, IP is assumed.
 542  */
 543 static u_int off_linktype;
 544 static u_int off_nl;
 545 static int linktype;
 546
 547 static void
 548 init_linktype(type)
 549         int type;
 550 {
 551         linktype = type;
 552
 553         switch (type) {
 554
 555         case DLT_EN10MB:
 556                 off_linktype = 12;
 557                 off_nl = 14;
 558                 return;
 559
 560         case DLT_SLIP:
 561                 /*
 562                  * SLIP doesn't have a link level type.  The 16 byte
 563                  * header is hacked into our SLIP driver.
 564                  */
 565                 off_linktype = -1;
 566                 off_nl = 16;
 567                 return;
 568
 569         case DLT_SLIP_BSDOS:
 570                 /* XXX this may be the same as the DLT_PPP_BSDOS case */
 571                 off_linktype = -1;
 572                 /* XXX end */
 573                 off_nl = 24;
 574                 return;
 575
 576         case DLT_NULL:
 577         case DLT_LOOP:
 578                 off_linktype = 0;
 579                 off_nl = 4;
 580                 return;
 581
 582         case DLT_PPP:
 583         case DLT_C_HDLC:
 584         case DLT_PPP_SERIAL:
 585                 off_linktype = 2;
 586                 off_nl = 4;
 587                 return;
 588
 589         case DLT_PPP_BSDOS:
 590                 off_linktype = 5;
 591                 off_nl = 24;
 592                 return;
 593
 594         case DLT_FDDI:
 595                 /*
 596                  * FDDI doesn't really have a link-level type field.
 597                  * We assume that SSAP = SNAP is being used and pick
 598                  * out the encapsulated Ethernet type.
 599                  *
 600                  * XXX - should we generate code to check for SNAP?
 601                  */
 602                 off_linktype = 19;
 603 #ifdef PCAP_FDDIPAD
 604                 off_linktype += pcap_fddipad;
 605 #endif
 606                 off_nl = 21;
 607 #ifdef PCAP_FDDIPAD
 608                 off_nl += pcap_fddipad;
 609 #endif
 610                 return;
 611
 612         case DLT_IEEE802:
 613                 /*
 614                  * Token Ring doesn't really have a link-level type field.
 615                  * We assume that SSAP = SNAP is being used and pick
 616                  * out the encapsulated Ethernet type.
 617                  *
 618                  * XXX - should we generate code to check for SNAP?
 619                  *
 620                  * XXX - the header is actually variable-length.
 621                  * Some various Linux patched versions gave 38
 622                  * as "off_linktype" and 40 as "off_nl"; however,
 623                  * if a token ring packet has *no* routing
 624                  * information, i.e. is not source-routed, the correct
 625                  * values are 20 and 22, as they are in the vanilla code.
 626                  *
 627                  * A packet is source-routed iff the uppermost bit
 628                  * of the first byte of the source address, at an
 629                  * offset of 8, has the uppermost bit set.  If the
 630                  * packet is source-routed, the total number of bytes
 631                  * of routing information is 2 plus bits 0x1F00 of
 632                  * the 16-bit value at an offset of 14 (shifted right
 633                  * 8 - figure out which byte that is).
 634                  */
 635                 off_linktype = 20;
 636                 off_nl = 22;
 637                 return;
 638
 639         case DLT_ATM_RFC1483:
 640                 /*
 641                  * assume routed, non-ISO PDUs
 642                  * (i.e., LLC = 0xAA-AA-03, OUT = 0x00-00-00)
 643                  */
 644                 off_linktype = 6;
 645                 off_nl = 8;
 646                 return;
 647
 648         case DLT_RAW:
 649                 off_linktype = -1;
 650                 off_nl = 0;
 651                 return;
 652
 653         case DLT_ATM_CLIP:      /* Linux ATM defines this */
 654                 off_linktype = 6;
 655                 off_nl = 8;
 656                 return;
 657
 658         case DLT_LINUX_SLL:     /* fake header for Linux cooked socket */
 659                 off_linktype = 14;
 660                 off_nl = 16;
 661                 return;
 662         }
 663         bpf_error("unknown data link type %d", linktype);
 664         /* NOTREACHED */
 665 }
 666
 667 static struct block *
 668 gen_uncond(rsense)
 669         int rsense;
 670 {
 671         struct block *b;
 672         struct slist *s;
 673
 674         s = new_stmt(BPF_LD|BPF_IMM);
 675         s->s.k = !rsense;
 676         b = new_block(JMP(BPF_JEQ));
 677         b->stmts = s;
 678
 679         return b;
 680 }
 681
 682 static inline struct block *
 683 gen_true()
 684 {
 685         return gen_uncond(1);
 686 }
 687
 688 static inline struct block *
 689 gen_false()
 690 {
 691         return gen_uncond(0);
 692 }
 693
 694 /*
 695  * Byte-swap a 32-bit number.
 696  * ("htonl()" or "ntohl()" won't work - we want to byte-swap even on
 697  * big-endian platforms.)
 698  */
 699 #define SWAPLONG(y) \
 700 ((((y)&0xff)<<24) | (((y)&0xff00)<<8) | (((y)&0xff0000)>>8) | (((y)>>24)&0xff))
 701
 702 static struct block *
 703 gen_linktype(proto)
 704         register int proto;
 705 {
 706         struct block *b0, *b1;
 707
 708         /* If we're not using encapsulation, we're done */
 709         if (off_linktype == -1)
 710                 return gen_true();
 711
 712         switch (linktype) {
 713
 714         case DLT_EN10MB:
 715                 /*
 716                  * XXX - handle other LLC-encapsulated protocols here
 717                  * (IPX, OSI)?
 718                  */
 719                 switch (proto) {
 720
 721                 case LLC_ISO_LSAP:
 722                         /*
 723                          * OSI protocols always use 802.2 encapsulation.
 724                          */
 725                         b0 = gen_cmp_gt(off_linktype, BPF_H, ETHERMTU);
 726                         gen_not(b0);
 727                         b1 = gen_cmp(off_linktype + 2, BPF_H, (bpf_int32)
 728                                      ((LLC_ISO_LSAP << 8) | LLC_ISO_LSAP));
 729                         gen_and(b0, b1);
 730                         return b1;
 731
 732                 case ETHERTYPE_ATALK:
 733                 case ETHERTYPE_AARP:
 734                         /*
 735                          * EtherTalk (AppleTalk protocols on Ethernet link
 736                          * layer) may use 802.2 encapsulation.
 737                          */
 738
 739                         /*
 740                          * Check for 802.2 encapsulation (EtherTalk phase 2?);
 741                          * we check for an Ethernet type field less than
 742                          * 1500, which means it's an 802.3 length field.
 743                          */
 744                         b0 = gen_cmp_gt(off_linktype, BPF_H, ETHERMTU);
 745                         gen_not(b0);
 746
 747                         /*
 748                          * 802.2-encapsulated ETHERTYPE_ATALK packets are
 749                          * SNAP packets with an organization code of
 750                          * 0x080007 (Apple, for Appletalk) and a protocol
 751                          * type of ETHERTYPE_ATALK (Appletalk).
 752                          *
 753                          * 802.2-encapsulated ETHERTYPE_AARP packets are
 754                          * SNAP packets with an organization code of
 755                          * 0x000000 (encapsulated Ethernet) and a protocol
 756                          * type of ETHERTYPE_AARP (Appletalk ARP).
 757                          */
 758                         if (proto == ETHERTYPE_ATALK)
 759                                 b1 = gen_snap(0x080007, ETHERTYPE_ATALK, 14);
 760                         else    /* proto == ETHERTYPE_AARP */
 761                                 b1 = gen_snap(0x000000, ETHERTYPE_AARP, 14);
 762                         gen_and(b0, b1);
 763
 764                         /*
 765                          * Check for Ethernet encapsulation (Ethertalk
 766                          * phase 1?); we just check for the Ethernet
 767                          * protocol type.
 768                          */
 769                         b0 = gen_cmp(off_linktype, BPF_H, (bpf_int32)proto);
 770
 771                         gen_or(b0, b1);
 772                         return b1;
 773                 }
 774                 break;
 775
 776         case DLT_SLIP:
 777                 return gen_false();
 778
 779         case DLT_PPP:
 780         case DLT_PPP_SERIAL:
 781                 /*
 782                  * We use Ethernet protocol types inside libpcap;
 783                  * map them to the corresponding PPP protocol types.
 784                  */
 785                 switch (proto) {
 786
 787                 case ETHERTYPE_IP:
 788                         proto = PPP_IP;                 /* XXX was 0x21 */
 789                         break;
 790
 791 #ifdef INET6
 792                 case ETHERTYPE_IPV6:
 793                         proto = PPP_IPV6;
 794                         break;
 795 #endif
 796
 797                 case ETHERTYPE_DN:
 798                         proto = PPP_DECNET;
 799                         break;
 800
 801                 case ETHERTYPE_ATALK:
 802                         proto = PPP_APPLE;
 803                         break;
 804
 805                 case ETHERTYPE_NS:
 806                         proto = PPP_NS;
 807                         break;
 808
 809                 case LLC_ISO_LSAP:
 810                         proto = PPP_OSI;
 811                         break;
 812                 }
 813                 break;
 814
 815         case DLT_PPP_BSDOS:
 816                 /*
 817                  * We use Ethernet protocol types inside libpcap;
 818                  * map them to the corresponding PPP protocol types.
 819                  */
 820                 switch (proto) {
 821
 822                 case ETHERTYPE_IP:
 823                         b0 = gen_cmp(off_linktype, BPF_H, PPP_IP);
 824                         b1 = gen_cmp(off_linktype, BPF_H, PPP_VJC);
 825                         gen_or(b0, b1);
 826                         b0 = gen_cmp(off_linktype, BPF_H, PPP_VJNC);
 827                         gen_or(b1, b0);
 828                         return b0;
 829
 830 #ifdef INET6
 831                 case ETHERTYPE_IPV6:
 832                         proto = PPP_IPV6;
 833                         /* more to go? */
 834                         break;
 835 #endif
 836
 837                 case ETHERTYPE_DN:
 838                         proto = PPP_DECNET;
 839                         break;
 840
 841                 case ETHERTYPE_ATALK:
 842                         proto = PPP_APPLE;
 843                         break;
 844
 845                 case ETHERTYPE_NS:
 846                         proto = PPP_NS;
 847                         break;
 848
 849                 case LLC_ISO_LSAP:
 850                         proto = PPP_OSI;
 851                         break;
 852                 }
 853                 break;
 854
 855         case DLT_NULL:
 856         case DLT_LOOP:
 857                 /*
 858                  * For DLT_NULL, the link-layer header is a 32-bit
 859                  * word containing an AF_ value in *host* byte order.
 860                  *
 861                  * In addition, if we're reading a saved capture file,
 862                  * the host byte order in the capture may not be the
 863                  * same as the host byte order on this machine.
 864                  *
 865                  * For DLT_LOOP, the link-layer header is a 32-bit
 866                  * word containing an AF_ value in *network* byte order.
 867                  *
 868                  * XXX - AF_ values may, unfortunately, be platform-
 869                  * dependent; for example, FreeBSD's AF_INET6 is 24
 870                  * whilst NetBSD's and OpenBSD's is 26.
 871                  *
 872                  * This means that, when reading a capture file, just
 873                  * checking for our AF_INET6 value won't work if the
 874                  * capture file came from another OS.
 875                  */
 876                 switch (proto) {
 877
 878                 case ETHERTYPE_IP:
 879                         proto = AF_INET;
 880                         break;
 881
 882 #ifdef INET6
 883                 case ETHERTYPE_IPV6:
 884                         proto = AF_INET6;
 885                         break;
 886 #endif
 887
 888                 default:
 889                         /*
 890                          * Not a type on which we support filtering.
 891                          * XXX - support those that have AF_ values
 892                          * #defined on this platform, at least?
 893                          */
 894                         return gen_false();
 895                 }
 896
 897                 if (linktype == DLT_NULL) {
 898                         /*
 899                          * The AF_ value is in host byte order, but
 900                          * the BPF interpreter will convert it to
 901                          * network byte order.
 902                          *
 903                          * If this is a save file, and it's from a
 904                          * machine with the opposite byte order to
 905                          * ours, we byte-swap the AF_ value.
 906                          *
 907                          * Then we run it through "htonl()", and
 908                          * generate code to compare against the result.
 909                          */
 910                         if (bpf_pcap->sf.rfile != NULL &&
 911                             bpf_pcap->sf.swapped)
 912                                 proto = SWAPLONG(proto);
 913                         proto = htonl(proto);
 914                 }
 915                 return (gen_cmp(0, BPF_W, (bpf_int32)proto));
 916         }
 917         return gen_cmp(off_linktype, BPF_H, (bpf_int32)proto);
 918 }
 919
 920 /*
 921  * Check for an LLC SNAP packet with a given organization code and
 922  * protocol type; we check the entire contents of the 802.2 LLC and
 923  * snap headers, checking for DSAP and SSAP of SNAP and a control
 924  * field of 0x03 in the LLC header, and for the specified organization
 925  * code and protocol type in the SNAP header.
 926  */
 927 static struct block *
 928 gen_snap(orgcode, ptype, offset)
 929         bpf_u_int32 orgcode;
 930         bpf_u_int32 ptype;
 931         u_int offset;
 932 {
 933         u_char snapblock[8];
 934
 935         snapblock[0] = LLC_SNAP_LSAP;   /* DSAP = SNAP */
 936         snapblock[1] = LLC_SNAP_LSAP;   /* SSAP = SNAP */
 937         snapblock[2] = 0x03;    /* control = UI */
 938         snapblock[3] = (orgcode >> 16); /* upper 8 bits of organization code */
 939         snapblock[4] = (orgcode >> 8);  /* middle 8 bits of organization code */
 940         snapblock[5] = (orgcode >> 0);  /* lower 8 bits of organization code */
 941         snapblock[6] = (ptype >> 8);    /* upper 8 bits of protocol type */
 942         snapblock[7] = (ptype >> 0);    /* lower 8 bits of protocol type */
 943         return gen_bcmp(offset, 8, snapblock);
 944 }
 945
 946 static struct block *
 947 gen_hostop(addr, mask, dir, proto, src_off, dst_off)
 948         bpf_u_int32 addr;
 949         bpf_u_int32 mask;
 950         int dir, proto;
 951         u_int src_off, dst_off;
 952 {
 953         struct block *b0, *b1;
 954         u_int offset;
 955
 956         switch (dir) {
 957
 958         case Q_SRC:
 959                 offset = src_off;
 960                 break;
 961
 962         case Q_DST:
 963                 offset = dst_off;
 964                 break;
 965
 966         case Q_AND:
 967                 b0 = gen_hostop(addr, mask, Q_SRC, proto, src_off, dst_off);
 968                 b1 = gen_hostop(addr, mask, Q_DST, proto, src_off, dst_off);
 969                 gen_and(b0, b1);
 970                 return b1;
 971
 972         case Q_OR:
 973         case Q_DEFAULT:
 974                 b0 = gen_hostop(addr, mask, Q_SRC, proto, src_off, dst_off);
 975                 b1 = gen_hostop(addr, mask, Q_DST, proto, src_off, dst_off);
 976                 gen_or(b0, b1);
 977                 return b1;
 978
 979         default:
 980                 abort();
 981         }
 982         b0 = gen_linktype(proto);
 983         b1 = gen_mcmp(offset, BPF_W, (bpf_int32)addr, mask);
 984         gen_and(b0, b1);
 985         return b1;
 986 }
 987
 988 #ifdef INET6
 989 static struct block *
 990 gen_hostop6(addr, mask, dir, proto, src_off, dst_off)
 991         struct in6_addr *addr;
 992         struct in6_addr *mask;
 993         int dir, proto;
 994         u_int src_off, dst_off;
 995 {
 996         struct block *b0, *b1;
 997         u_int offset;
 998         u_int32_t *a, *m;
 999
1000         switch (dir) {
1001
1002         case Q_SRC:
1003                 offset = src_off;
1004                 break;
1005
1006         case Q_DST:
1007                 offset = dst_off;
1008                 break;
1009
1010         case Q_AND:
1011                 b0 = gen_hostop6(addr, mask, Q_SRC, proto, src_off, dst_off);
1012                 b1 = gen_hostop6(addr, mask, Q_DST, proto, src_off, dst_off);
1013                 gen_and(b0, b1);
1014                 return b1;
1015
1016         case Q_OR:
1017         case Q_DEFAULT:
1018                 b0 = gen_hostop6(addr, mask, Q_SRC, proto, src_off, dst_off);
1019                 b1 = gen_hostop6(addr, mask, Q_DST, proto, src_off, dst_off);
1020                 gen_or(b0, b1);
1021                 return b1;
1022
1023         default:
1024                 abort();
1025         }
1026         /* this order is important */
1027         a = (u_int32_t *)addr;
1028         m = (u_int32_t *)mask;
1029         b1 = gen_mcmp(offset + 12, BPF_W, ntohl(a[3]), ntohl(m[3]));
1030         b0 = gen_mcmp(offset + 8, BPF_W, ntohl(a[2]), ntohl(m[2]));
1031         gen_and(b0, b1);
1032         b0 = gen_mcmp(offset + 4, BPF_W, ntohl(a[1]), ntohl(m[1]));
1033         gen_and(b0, b1);
1034         b0 = gen_mcmp(offset + 0, BPF_W, ntohl(a[0]), ntohl(m[0]));
1035         gen_and(b0, b1);
1036         b0 = gen_linktype(proto);
1037         gen_and(b0, b1);
1038         return b1;
1039 }
1040 #endif /*INET6*/
1041
1042 static struct block *
1043 gen_ehostop(eaddr, dir)
1044         register const u_char *eaddr;
1045         register int dir;
1046 {
1047         register struct block *b0, *b1;
1048
1049         switch (dir) {
1050         case Q_SRC:
1051                 return gen_bcmp(6, 6, eaddr);
1052
1053         case Q_DST:
1054                 return gen_bcmp(0, 6, eaddr);
1055
1056         case Q_AND:
1057                 b0 = gen_ehostop(eaddr, Q_SRC);
1058                 b1 = gen_ehostop(eaddr, Q_DST);
1059                 gen_and(b0, b1);
1060                 return b1;
1061
1062         case Q_DEFAULT:
1063         case Q_OR:
1064                 b0 = gen_ehostop(eaddr, Q_SRC);
1065                 b1 = gen_ehostop(eaddr, Q_DST);
1066                 gen_or(b0, b1);
1067                 return b1;
1068         }
1069         abort();
1070         /* NOTREACHED */
1071 }
1072
1073 /*
1074  * Like gen_ehostop, but for DLT_FDDI
1075  */
1076 static struct block *
1077 gen_fhostop(eaddr, dir)
1078         register const u_char *eaddr;
1079         register int dir;
1080 {
1081         struct block *b0, *b1;
1082
1083         switch (dir) {
1084         case Q_SRC:
1085 #ifdef PCAP_FDDIPAD
1086                 return gen_bcmp(6 + 1 + pcap_fddipad, 6, eaddr);
1087 #else
1088                 return gen_bcmp(6 + 1, 6, eaddr);
1089 #endif
1090
1091         case Q_DST:
1092 #ifdef PCAP_FDDIPAD
1093                 return gen_bcmp(0 + 1 + pcap_fddipad, 6, eaddr);
1094 #else
1095                 return gen_bcmp(0 + 1, 6, eaddr);
1096 #endif
1097
1098         case Q_AND:
1099                 b0 = gen_fhostop(eaddr, Q_SRC);
1100                 b1 = gen_fhostop(eaddr, Q_DST);
1101                 gen_and(b0, b1);
1102                 return b1;
1103
1104         case Q_DEFAULT:
1105         case Q_OR:
1106                 b0 = gen_fhostop(eaddr, Q_SRC);
1107                 b1 = gen_fhostop(eaddr, Q_DST);
1108                 gen_or(b0, b1);
1109                 return b1;
1110         }
1111         abort();
1112         /* NOTREACHED */
1113 }
1114
1115 /*
1116  * Like gen_ehostop, but for DLT_IEEE802 (Token Ring)
1117  */
1118 static struct block *
1119 gen_thostop(eaddr, dir)
1120         register const u_char *eaddr;
1121         register int dir;
1122 {
1123         register struct block *b0, *b1;
1124
1125         switch (dir) {
1126         case Q_SRC:
1127                 return gen_bcmp(8, 6, eaddr);
1128
1129         case Q_DST:
1130                 return gen_bcmp(2, 6, eaddr);
1131
1132         case Q_AND:
1133                 b0 = gen_thostop(eaddr, Q_SRC);
1134                 b1 = gen_thostop(eaddr, Q_DST);
1135                 gen_and(b0, b1);
1136                 return b1;
1137
1138         case Q_DEFAULT:
1139         case Q_OR:
1140                 b0 = gen_thostop(eaddr, Q_SRC);
1141                 b1 = gen_thostop(eaddr, Q_DST);
1142                 gen_or(b0, b1);
1143                 return b1;
1144         }
1145         abort();
1146         /* NOTREACHED */
1147 }
1148
1149 /*
1150  * This is quite tricky because there may be pad bytes in front of the
1151  * DECNET header, and then there are two possible data packet formats that
1152  * carry both src and dst addresses, plus 5 packet types in a format that
1153  * carries only the src node, plus 2 types that use a different format and
1154  * also carry just the src node.
1155  *
1156  * Yuck.
1157  *
1158  * Instead of doing those all right, we just look for data packets with
1159  * 0 or 1 bytes of padding.  If you want to look at other packets, that
1160  * will require a lot more hacking.
1161  *
1162  * To add support for filtering on DECNET "areas" (network numbers)
1163  * one would want to add a "mask" argument to this routine.  That would
1164  * make the filter even more inefficient, although one could be clever
1165  * and not generate masking instructions if the mask is 0xFFFF.
1166  */
1167 static struct block *
1168 gen_dnhostop(addr, dir, base_off)
1169         bpf_u_int32 addr;
1170         int dir;
1171         u_int base_off;
1172 {
1173         struct block *b0, *b1, *b2, *tmp;
1174         u_int offset_lh;        /* offset if long header is received */
1175         u_int offset_sh;        /* offset if short header is received */
1176
1177         switch (dir) {
1178
1179         case Q_DST:
1180                 offset_sh = 1;  /* follows flags */
1181                 offset_lh = 7;  /* flgs,darea,dsubarea,HIORD */
1182                 break;
1183
1184         case Q_SRC:
1185                 offset_sh = 3;  /* follows flags, dstnode */
1186                 offset_lh = 15; /* flgs,darea,dsubarea,did,sarea,ssub,HIORD */
1187                 break;
1188
1189         case Q_AND:
1190                 /* Inefficient because we do our Calvinball dance twice */
1191                 b0 = gen_dnhostop(addr, Q_SRC, base_off);
1192                 b1 = gen_dnhostop(addr, Q_DST, base_off);
1193                 gen_and(b0, b1);
1194                 return b1;
1195
1196         case Q_OR:
1197         case Q_DEFAULT:
1198                 /* Inefficient because we do our Calvinball dance twice */
1199                 b0 = gen_dnhostop(addr, Q_SRC, base_off);
1200                 b1 = gen_dnhostop(addr, Q_DST, base_off);
1201                 gen_or(b0, b1);
1202                 return b1;
1203
1204         case Q_ISO:
1205                 bpf_error("ISO host filtering not implemented");
1206
1207         default:
1208                 abort();
1209         }
1210         b0 = gen_linktype(ETHERTYPE_DN);
1211         /* Check for pad = 1, long header case */
1212         tmp = gen_mcmp(base_off + 2, BPF_H,
1213             (bpf_int32)ntohs(0x0681), (bpf_int32)ntohs(0x07FF));
1214         b1 = gen_cmp(base_off + 2 + 1 + offset_lh,
1215             BPF_H, (bpf_int32)ntohs(addr));
1216         gen_and(tmp, b1);
1217         /* Check for pad = 0, long header case */
1218         tmp = gen_mcmp(base_off + 2, BPF_B, (bpf_int32)0x06, (bpf_int32)0x7);
1219         b2 = gen_cmp(base_off + 2 + offset_lh, BPF_H, (bpf_int32)ntohs(addr));
1220         gen_and(tmp, b2);
1221         gen_or(b2, b1);
1222         /* Check for pad = 1, short header case */
1223         tmp = gen_mcmp(base_off + 2, BPF_H,
1224             (bpf_int32)ntohs(0x0281), (bpf_int32)ntohs(0x07FF));
1225         b2 = gen_cmp(base_off + 2 + 1 + offset_sh,
1226             BPF_H, (bpf_int32)ntohs(addr));
1227         gen_and(tmp, b2);
1228         gen_or(b2, b1);
1229         /* Check for pad = 0, short header case */
1230         tmp = gen_mcmp(base_off + 2, BPF_B, (bpf_int32)0x02, (bpf_int32)0x7);
1231         b2 = gen_cmp(base_off + 2 + offset_sh, BPF_H, (bpf_int32)ntohs(addr));
1232         gen_and(tmp, b2);
1233         gen_or(b2, b1);
1234
1235         /* Combine with test for linktype */
1236         gen_and(b0, b1);
1237         return b1;
1238 }
1239
1240 static struct block *
1241 gen_host(addr, mask, proto, dir)
1242         bpf_u_int32 addr;
1243         bpf_u_int32 mask;
1244         int proto;
1245         int dir;
1246 {
1247         struct block *b0, *b1;
1248
1249         switch (proto) {
1250
1251         case Q_DEFAULT:
1252                 b0 = gen_host(addr, mask, Q_IP, dir);
1253                 if (off_linktype != -1) {
1254                     b1 = gen_host(addr, mask, Q_ARP, dir);
1255                     gen_or(b0, b1);
1256                     b0 = gen_host(addr, mask, Q_RARP, dir);
1257                     gen_or(b1, b0);
1258                 }
1259                 return b0;
1260
1261         case Q_IP:
1262                 return gen_hostop(addr, mask, dir, ETHERTYPE_IP,
1263                                   off_nl + 12, off_nl + 16);
1264
1265         case Q_RARP:
1266                 return gen_hostop(addr, mask, dir, ETHERTYPE_REVARP,
1267                                   off_nl + 14, off_nl + 24);
1268
1269         case Q_ARP:
1270                 return gen_hostop(addr, mask, dir, ETHERTYPE_ARP,
1271                                   off_nl + 14, off_nl + 24);
1272
1273         case Q_TCP:
1274                 bpf_error("'tcp' modifier applied to host");
1275
1276         case Q_UDP:
1277                 bpf_error("'udp' modifier applied to host");
1278
1279         case Q_ICMP:
1280                 bpf_error("'icmp' modifier applied to host");
1281
1282         case Q_IGMP:
1283                 bpf_error("'igmp' modifier applied to host");
1284
1285         case Q_IGRP:
1286                 bpf_error("'igrp' modifier applied to host");
1287
1288         case Q_PIM:
1289                 bpf_error("'pim' modifier applied to host");
1290
1291         case Q_ATALK:
1292                 bpf_error("ATALK host filtering not implemented");
1293
1294         case Q_AARP:
1295                 bpf_error("AARP host filtering not implemented");
1296
1297         case Q_DECNET:
1298                 return gen_dnhostop(addr, dir, off_nl);
1299
1300         case Q_SCA:
1301                 bpf_error("SCA host filtering not implemented");
1302
1303         case Q_LAT:
1304                 bpf_error("LAT host filtering not implemented");
1305
1306         case Q_MOPDL:
1307                 bpf_error("MOPDL host filtering not implemented");
1308
1309         case Q_MOPRC:
1310                 bpf_error("MOPRC host filtering not implemented");
1311
1312 #ifdef INET6
1313         case Q_IPV6:
1314                 bpf_error("'ip6' modifier applied to ip host");
1315
1316         case Q_ICMPV6:
1317                 bpf_error("'icmp6' modifier applied to host");
1318 #endif /* INET6 */
1319
1320         case Q_AH:
1321                 bpf_error("'ah' modifier applied to host");
1322
1323         case Q_ESP:
1324                 bpf_error("'esp' modifier applied to host");
1325
1326         case Q_ISO:
1327                 bpf_error("ISO host filtering not implemented");
1328
1329         case Q_ESIS:
1330                 bpf_error("'esis' modifier applied to host");
1331
1332         case Q_ISIS:
1333                 bpf_error("'isis' modifier applied to host");
1334
1335         case Q_CLNP:
1336                 bpf_error("'clnp' modifier applied to host");
1337
1338         default:
1339                 abort();
1340         }
1341         /* NOTREACHED */
1342 }
1343
1344 #ifdef INET6
1345 static struct block *
1346 gen_host6(addr, mask, proto, dir)
1347         struct in6_addr *addr;
1348         struct in6_addr *mask;
1349         int proto;
1350         int dir;
1351 {
1352         switch (proto) {
1353
1354         case Q_DEFAULT:
1355                 return gen_host6(addr, mask, Q_IPV6, dir);
1356
1357         case Q_IP:
1358                 bpf_error("'ip' modifier applied to ip6 host");
1359
1360         case Q_RARP:
1361                 bpf_error("'rarp' modifier applied to ip6 host");
1362
1363         case Q_ARP:
1364                 bpf_error("'arp' modifier applied to ip6 host");
1365
1366         case Q_TCP:
1367                 bpf_error("'tcp' modifier applied to host");
1368
1369         case Q_UDP:
1370                 bpf_error("'udp' modifier applied to host");
1371
1372         case Q_ICMP:
1373                 bpf_error("'icmp' modifier applied to host");
1374
1375         case Q_IGMP:
1376                 bpf_error("'igmp' modifier applied to host");
1377
1378         case Q_IGRP:
1379                 bpf_error("'igrp' modifier applied to host");
1380
1381         case Q_PIM:
1382                 bpf_error("'pim' modifier applied to host");
1383
1384         case Q_ATALK:
1385                 bpf_error("ATALK host filtering not implemented");
1386
1387         case Q_AARP:
1388                 bpf_error("AARP host filtering not implemented");
1389
1390         case Q_DECNET:
1391                 bpf_error("'decnet' modifier applied to ip6 host");
1392
1393         case Q_SCA:
1394                 bpf_error("SCA host filtering not implemented");
1395
1396         case Q_LAT:
1397                 bpf_error("LAT host filtering not implemented");
1398
1399         case Q_MOPDL:
1400                 bpf_error("MOPDL host filtering not implemented");
1401
1402         case Q_MOPRC:
1403                 bpf_error("MOPRC host filtering not implemented");
1404
1405         case Q_IPV6:
1406                 return gen_hostop6(addr, mask, dir, ETHERTYPE_IPV6,
1407                                   off_nl + 8, off_nl + 24);
1408
1409         case Q_ICMPV6:
1410                 bpf_error("'icmp6' modifier applied to host");
1411
1412         case Q_AH:
1413                 bpf_error("'ah' modifier applied to host");
1414
1415         case Q_ESP:
1416                 bpf_error("'esp' modifier applied to host");
1417
1418         case Q_ISO:
1419                 bpf_error("ISO host filtering not implemented");
1420
1421         case Q_ESIS:
1422                 bpf_error("'esis' modifier applied to host");
1423
1424         case Q_ISIS:
1425                 bpf_error("'isis' modifier applied to host");
1426
1427         case Q_CLNP:
1428                 bpf_error("'clnp' modifier applied to host");
1429
1430         default:
1431                 abort();
1432         }
1433         /* NOTREACHED */
1434 }
1435 #endif /*INET6*/
1436
1437 #ifndef INET6
1438 static struct block *
1439 gen_gateway(eaddr, alist, proto, dir)
1440         const u_char *eaddr;
1441         bpf_u_int32 **alist;
1442         int proto;
1443         int dir;
1444 {
1445         struct block *b0, *b1, *tmp;
1446
1447         if (dir != 0)
1448                 bpf_error("direction applied to 'gateway'");
1449
1450         switch (proto) {
1451         case Q_DEFAULT:
1452         case Q_IP:
1453         case Q_ARP:
1454         case Q_RARP:
1455                 if (linktype == DLT_EN10MB)
1456                         b0 = gen_ehostop(eaddr, Q_OR);
1457                 else if (linktype == DLT_FDDI)
1458                         b0 = gen_fhostop(eaddr, Q_OR);
1459                 else if (linktype == DLT_IEEE802)
1460                         b0 = gen_thostop(eaddr, Q_OR);
1461                 else
1462                         bpf_error(
1463                             "'gateway' supported only on ethernet, FDDI or token ring");
1464
1465                 b1 = gen_host(**alist++, 0xffffffff, proto, Q_OR);
1466                 while (*alist) {
1467                         tmp = gen_host(**alist++, 0xffffffff, proto, Q_OR);
1468                         gen_or(b1, tmp);
1469                         b1 = tmp;
1470                 }
1471                 gen_not(b1);
1472                 gen_and(b0, b1);
1473                 return b1;
1474         }
1475         bpf_error("illegal modifier of 'gateway'");
1476         /* NOTREACHED */
1477 }
1478 #endif
1479
1480 struct block *
1481 gen_proto_abbrev(proto)
1482         int proto;
1483 {
1484 #ifdef INET6
1485         struct block *b0;
1486 #endif
1487         struct block *b1;
1488
1489         switch (proto) {
1490
1491         case Q_TCP:
1492                 b1 = gen_proto(IPPROTO_TCP, Q_IP, Q_DEFAULT);
1493 #ifdef INET6
1494                 b0 = gen_proto(IPPROTO_TCP, Q_IPV6, Q_DEFAULT);
1495                 gen_or(b0, b1);
1496 #endif
1497                 break;
1498
1499         case Q_UDP:
1500                 b1 = gen_proto(IPPROTO_UDP, Q_IP, Q_DEFAULT);
1501 #ifdef INET6
1502                 b0 = gen_proto(IPPROTO_UDP, Q_IPV6, Q_DEFAULT);
1503                 gen_or(b0, b1);
1504 #endif
1505                 break;
1506
1507         case Q_ICMP:
1508                 b1 = gen_proto(IPPROTO_ICMP, Q_IP, Q_DEFAULT);
1509                 break;
1510
1511 #ifndef IPPROTO_IGMP
1512 #define IPPROTO_IGMP    2
1513 #endif
1514
1515         case Q_IGMP:
1516                 b1 = gen_proto(IPPROTO_IGMP, Q_IP, Q_DEFAULT);
1517                 break;
1518
1519 #ifndef IPPROTO_IGRP
1520 #define IPPROTO_IGRP    9
1521 #endif
1522         case Q_IGRP:
1523                 b1 = gen_proto(IPPROTO_IGRP, Q_IP, Q_DEFAULT);
1524                 break;
1525
1526 #ifndef IPPROTO_PIM
1527 #define IPPROTO_PIM     103
1528 #endif
1529
1530         case Q_PIM:
1531                 b1 = gen_proto(IPPROTO_PIM, Q_IP, Q_DEFAULT);
1532 #ifdef INET6
1533                 b0 = gen_proto(IPPROTO_PIM, Q_IPV6, Q_DEFAULT);
1534                 gen_or(b0, b1);
1535 #endif
1536                 break;
1537
1538         case Q_IP:
1539                 b1 =  gen_linktype(ETHERTYPE_IP);
1540                 break;
1541
1542         case Q_ARP:
1543                 b1 =  gen_linktype(ETHERTYPE_ARP);
1544                 break;
1545
1546         case Q_RARP:
1547                 b1 =  gen_linktype(ETHERTYPE_REVARP);
1548                 break;
1549
1550         case Q_LINK:
1551                 bpf_error("link layer applied in wrong context");
1552
1553         case Q_ATALK:
1554                 b1 =  gen_linktype(ETHERTYPE_ATALK);
1555                 break;
1556
1557         case Q_AARP:
1558                 b1 =  gen_linktype(ETHERTYPE_AARP);
1559                 break;
1560
1561         case Q_DECNET:
1562                 b1 =  gen_linktype(ETHERTYPE_DN);
1563                 break;
1564
1565         case Q_SCA:
1566                 b1 =  gen_linktype(ETHERTYPE_SCA);
1567                 break;
1568
1569         case Q_LAT:
1570                 b1 =  gen_linktype(ETHERTYPE_LAT);
1571                 break;
1572
1573         case Q_MOPDL:
1574                 b1 =  gen_linktype(ETHERTYPE_MOPDL);
1575                 break;
1576
1577         case Q_MOPRC:
1578                 b1 =  gen_linktype(ETHERTYPE_MOPRC);
1579                 break;
1580
1581 #ifdef INET6
1582         case Q_IPV6:
1583                 b1 = gen_linktype(ETHERTYPE_IPV6);
1584                 break;
1585
1586 #ifndef IPPROTO_ICMPV6
1587 #define IPPROTO_ICMPV6  58
1588 #endif
1589         case Q_ICMPV6:
1590                 b1 = gen_proto(IPPROTO_ICMPV6, Q_IPV6, Q_DEFAULT);
1591                 break;
1592 #endif /* INET6 */
1593
1594 #ifndef IPPROTO_AH
1595 #define IPPROTO_AH      51
1596 #endif
1597         case Q_AH:
1598                 b1 = gen_proto(IPPROTO_AH, Q_IP, Q_DEFAULT);
1599 #ifdef INET6
1600                 b0 = gen_proto(IPPROTO_AH, Q_IPV6, Q_DEFAULT);
1601                 gen_or(b0, b1);
1602 #endif
1603                 break;
1604
1605 #ifndef IPPROTO_ESP
1606 #define IPPROTO_ESP     50
1607 #endif
1608         case Q_ESP:
1609                 b1 = gen_proto(IPPROTO_ESP, Q_IP, Q_DEFAULT);
1610 #ifdef INET6
1611                 b0 = gen_proto(IPPROTO_ESP, Q_IPV6, Q_DEFAULT);
1612                 gen_or(b0, b1);
1613 #endif
1614                 break;
1615
1616         case Q_ISO:
1617                 b1 = gen_linktype(LLC_ISO_LSAP);
1618                 break;
1619
1620         case Q_ESIS:
1621                 b1 = gen_proto(ISO9542_ESIS, Q_ISO, Q_DEFAULT);
1622                 break;
1623
1624         case Q_ISIS:
1625                 b1 = gen_proto(ISO10589_ISIS, Q_ISO, Q_DEFAULT);
1626                 break;
1627
1628         case Q_CLNP:
1629                 b1 = gen_proto(ISO8473_CLNP, Q_ISO, Q_DEFAULT);
1630                 break;
1631
1632         default:
1633                 abort();
1634         }
1635         return b1;
1636 }
1637
1638 static struct block *
1639 gen_ipfrag()
1640 {
1641         struct slist *s;
1642         struct block *b;
1643
1644         /* not ip frag */
1645         s = new_stmt(BPF_LD|BPF_H|BPF_ABS);
1646         s->s.k = off_nl + 6;
1647         b = new_block(JMP(BPF_JSET));
1648         b->s.k = 0x1fff;
1649         b->stmts = s;
1650         gen_not(b);
1651
1652         return b;
1653 }
1654
1655 static struct block *
1656 gen_portatom(off, v)
1657         int off;
1658         bpf_int32 v;
1659 {
1660         struct slist *s;
1661         struct block *b;
1662
1663         s = new_stmt(BPF_LDX|BPF_MSH|BPF_B);
1664         s->s.k = off_nl;
1665
1666         s->next = new_stmt(BPF_LD|BPF_IND|BPF_H);
1667         s->next->s.k = off_nl + off;
1668
1669         b = new_block(JMP(BPF_JEQ));
1670         b->stmts = s;
1671         b->s.k = v;
1672
1673         return b;
1674 }
1675
1676 #ifdef INET6
1677 static struct block *
1678 gen_portatom6(off, v)
1679         int off;
1680         bpf_int32 v;
1681 {
1682         return gen_cmp(off_nl + 40 + off, BPF_H, v);
1683 }
1684 #endif/*INET6*/
1685
1686 struct block *
1687 gen_portop(port, proto, dir)
1688         int port, proto, dir;
1689 {
1690         struct block *b0, *b1, *tmp;
1691
1692         /* ip proto 'proto' */
1693         tmp = gen_cmp(off_nl + 9, BPF_B, (bpf_int32)proto);
1694         b0 = gen_ipfrag();
1695         gen_and(tmp, b0);
1696
1697         switch (dir) {
1698         case Q_SRC:
1699                 b1 = gen_portatom(0, (bpf_int32)port);
1700                 break;
1701
1702         case Q_DST:
1703                 b1 = gen_portatom(2, (bpf_int32)port);
1704                 break;
1705
1706         case Q_OR:
1707         case Q_DEFAULT:
1708                 tmp = gen_portatom(0, (bpf_int32)port);
1709                 b1 = gen_portatom(2, (bpf_int32)port);
1710                 gen_or(tmp, b1);
1711                 break;
1712
1713         case Q_AND:
1714                 tmp = gen_portatom(0, (bpf_int32)port);
1715                 b1 = gen_portatom(2, (bpf_int32)port);
1716                 gen_and(tmp, b1);
1717                 break;
1718
1719         default:
1720                 abort();
1721         }
1722         gen_and(b0, b1);
1723
1724         return b1;
1725 }
1726
1727 static struct block *
1728 gen_port(port, ip_proto, dir)
1729         int port;
1730         int ip_proto;
1731         int dir;
1732 {
1733         struct block *b0, *b1, *tmp;
1734
1735         /* ether proto ip */
1736         b0 =  gen_linktype(ETHERTYPE_IP);
1737
1738         switch (ip_proto) {
1739         case IPPROTO_UDP:
1740         case IPPROTO_TCP:
1741                 b1 = gen_portop(port, ip_proto, dir);
1742                 break;
1743
1744         case PROTO_UNDEF:
1745                 tmp = gen_portop(port, IPPROTO_TCP, dir);
1746                 b1 = gen_portop(port, IPPROTO_UDP, dir);
1747                 gen_or(tmp, b1);
1748                 break;
1749
1750         default:
1751                 abort();
1752         }
1753         gen_and(b0, b1);
1754         return b1;
1755 }
1756
1757 #ifdef INET6
1758 struct block *
1759 gen_portop6(port, proto, dir)
1760         int port, proto, dir;
1761 {
1762         struct block *b0, *b1, *tmp;
1763
1764         /* ip proto 'proto' */
1765         b0 = gen_cmp(off_nl + 6, BPF_B, (bpf_int32)proto);
1766
1767         switch (dir) {
1768         case Q_SRC:
1769                 b1 = gen_portatom6(0, (bpf_int32)port);
1770                 break;
1771
1772         case Q_DST:
1773                 b1 = gen_portatom6(2, (bpf_int32)port);
1774                 break;
1775
1776         case Q_OR:
1777         case Q_DEFAULT:
1778                 tmp = gen_portatom6(0, (bpf_int32)port);
1779                 b1 = gen_portatom6(2, (bpf_int32)port);
1780                 gen_or(tmp, b1);
1781                 break;
1782
1783         case Q_AND:
1784                 tmp = gen_portatom6(0, (bpf_int32)port);
1785                 b1 = gen_portatom6(2, (bpf_int32)port);
1786                 gen_and(tmp, b1);
1787                 break;
1788
1789         default:
1790                 abort();
1791         }
1792         gen_and(b0, b1);
1793
1794         return b1;
1795 }
1796
1797 static struct block *
1798 gen_port6(port, ip_proto, dir)
1799         int port;
1800         int ip_proto;
1801         int dir;
1802 {
1803         struct block *b0, *b1, *tmp;
1804
1805         /* ether proto ip */
1806         b0 =  gen_linktype(ETHERTYPE_IPV6);
1807
1808         switch (ip_proto) {
1809         case IPPROTO_UDP:
1810         case IPPROTO_TCP:
1811                 b1 = gen_portop6(port, ip_proto, dir);
1812                 break;
1813
1814         case PROTO_UNDEF:
1815                 tmp = gen_portop6(port, IPPROTO_TCP, dir);
1816                 b1 = gen_portop6(port, IPPROTO_UDP, dir);
1817                 gen_or(tmp, b1);
1818                 break;
1819
1820         default:
1821                 abort();
1822         }
1823         gen_and(b0, b1);
1824         return b1;
1825 }
1826 #endif /* INET6 */
1827
1828 static int
1829 lookup_proto(name, proto)
1830         register const char *name;
1831         register int proto;
1832 {
1833         register int v;
1834
1835         switch (proto) {
1836
1837         case Q_DEFAULT:
1838         case Q_IP:
1839                 v = pcap_nametoproto(name);
1840                 if (v == PROTO_UNDEF)
1841                         bpf_error("unknown ip proto '%s'", name);
1842                 break;
1843
1844         case Q_LINK:
1845                 /* XXX should look up h/w protocol type based on linktype */
1846                 v = pcap_nametoeproto(name);
1847                 if (v == PROTO_UNDEF)
1848                         bpf_error("unknown ether proto '%s'", name);
1849                 break;
1850
1851         case Q_ISO:
1852                 if (strcmp(name, "esis") == 0)
1853                         v = ISO9542_ESIS;
1854                 else if (strcmp(name, "isis") == 0)
1855                         v = ISO10589_ISIS;
1856                 else if (strcmp(name, "clnp") == 0)
1857                         v = ISO8473_CLNP;
1858                 else
1859                         bpf_error("unknown osi proto '%s'", name);
1860                 break;
1861
1862         default:
1863                 v = PROTO_UNDEF;
1864                 break;
1865         }
1866         return v;
1867 }
1868
1869 #if 0
1870 struct stmt *
1871 gen_joinsp(s, n)
1872         struct stmt **s;
1873         int n;
1874 {
1875         return NULL;
1876 }
1877 #endif
1878
1879 static struct block *
1880 gen_protochain(v, proto, dir)
1881         int v;
1882         int proto;
1883         int dir;
1884 {
1885 #ifdef NO_PROTOCHAIN
1886         return gen_proto(v, proto, dir);
1887 #else
1888         struct block *b0, *b;
1889         struct slist *s[100];
1890         int fix2, fix3, fix4, fix5;
1891         int ahcheck, again, end;
1892         int i, max;
1893         int reg2 = alloc_reg();
1894
1895         memset(s, 0, sizeof(s));
1896         fix2 = fix3 = fix4 = fix5 = 0;
1897
1898         switch (proto) {
1899         case Q_IP:
1900         case Q_IPV6:
1901                 break;
1902         case Q_DEFAULT:
1903                 b0 = gen_protochain(v, Q_IP, dir);
1904                 b = gen_protochain(v, Q_IPV6, dir);
1905                 gen_or(b0, b);
1906                 return b;
1907         default:
1908                 bpf_error("bad protocol applied for 'protochain'");
1909                 /*NOTREACHED*/
1910         }
1911
1912         no_optimize = 1; /*this code is not compatible with optimzer yet */
1913
1914         /*
1915          * s[0] is a dummy entry to protect other BPF insn from damaged
1916          * by s[fix] = foo with uninitialized variable "fix".  It is somewhat
1917          * hard to find interdependency made by jump table fixup.
1918          */
1919         i = 0;
1920         s[i] = new_stmt(0);     /*dummy*/
1921         i++;
1922
1923         switch (proto) {
1924         case Q_IP:
1925                 b0 = gen_linktype(ETHERTYPE_IP);
1926
1927                 /* A = ip->ip_p */
1928                 s[i] = new_stmt(BPF_LD|BPF_ABS|BPF_B);
1929                 s[i]->s.k = off_nl + 9;
1930                 i++;
1931                 /* X = ip->ip_hl << 2 */
1932                 s[i] = new_stmt(BPF_LDX|BPF_MSH|BPF_B);
1933                 s[i]->s.k = off_nl;
1934                 i++;
1935                 break;
1936 #ifdef INET6
1937         case Q_IPV6:
1938                 b0 = gen_linktype(ETHERTYPE_IPV6);
1939
1940                 /* A = ip6->ip_nxt */
1941                 s[i] = new_stmt(BPF_LD|BPF_ABS|BPF_B);
1942                 s[i]->s.k = off_nl + 6;
1943                 i++;
1944                 /* X = sizeof(struct ip6_hdr) */
1945                 s[i] = new_stmt(BPF_LDX|BPF_IMM);
1946                 s[i]->s.k = 40;
1947                 i++;
1948                 break;
1949 #endif
1950         default:
1951                 bpf_error("unsupported proto to gen_protochain");
1952                 /*NOTREACHED*/
1953         }
1954
1955         /* again: if (A == v) goto end; else fall through; */
1956         again = i;
1957         s[i] = new_stmt(BPF_JMP|BPF_JEQ|BPF_K);
1958         s[i]->s.k = v;
1959         s[i]->s.jt = NULL;              /*later*/
1960         s[i]->s.jf = NULL;              /*update in next stmt*/
1961         fix5 = i;
1962         i++;
1963
1964 #ifndef IPPROTO_NONE
1965 #define IPPROTO_NONE    59
1966 #endif
1967         /* if (A == IPPROTO_NONE) goto end */
1968         s[i] = new_stmt(BPF_JMP|BPF_JEQ|BPF_K);
1969         s[i]->s.jt = NULL;      /*later*/
1970         s[i]->s.jf = NULL;      /*update in next stmt*/
1971         s[i]->s.k = IPPROTO_NONE;
1972         s[fix5]->s.jf = s[i];
1973         fix2 = i;
1974         i++;
1975
1976 #ifdef INET6
1977         if (proto == Q_IPV6) {
1978                 int v6start, v6end, v6advance, j;
1979
1980                 v6start = i;
1981                 /* if (A == IPPROTO_HOPOPTS) goto v6advance */
1982                 s[i] = new_stmt(BPF_JMP|BPF_JEQ|BPF_K);
1983                 s[i]->s.jt = NULL;      /*later*/
1984                 s[i]->s.jf = NULL;      /*update in next stmt*/
1985                 s[i]->s.k = IPPROTO_HOPOPTS;
1986                 s[fix2]->s.jf = s[i];
1987                 i++;
1988                 /* if (A == IPPROTO_DSTOPTS) goto v6advance */
1989                 s[i - 1]->s.jf = s[i] = new_stmt(BPF_JMP|BPF_JEQ|BPF_K);
1990                 s[i]->s.jt = NULL;      /*later*/
1991                 s[i]->s.jf = NULL;      /*update in next stmt*/
1992                 s[i]->s.k = IPPROTO_DSTOPTS;
1993                 i++;
1994                 /* if (A == IPPROTO_ROUTING) goto v6advance */
1995                 s[i - 1]->s.jf = s[i] = new_stmt(BPF_JMP|BPF_JEQ|BPF_K);
1996                 s[i]->s.jt = NULL;      /*later*/
1997                 s[i]->s.jf = NULL;      /*update in next stmt*/
1998                 s[i]->s.k = IPPROTO_ROUTING;
1999                 i++;
2000                 /* if (A == IPPROTO_FRAGMENT) goto v6advance; else goto ahcheck; */
2001                 s[i - 1]->s.jf = s[i] = new_stmt(BPF_JMP|BPF_JEQ|BPF_K);
2002                 s[i]->s.jt = NULL;      /*later*/
2003                 s[i]->s.jf = NULL;      /*later*/
2004                 s[i]->s.k = IPPROTO_FRAGMENT;
2005                 fix3 = i;
2006                 v6end = i;
2007                 i++;
2008
2009                 /* v6advance: */
2010                 v6advance = i;
2011
2012                 /*
2013                  * in short,
2014                  * A = P[X];
2015                  * X = X + (P[X + 1] + 1) * 8;
2016                  */
2017                 /* A = X */
2018                 s[i] = new_stmt(BPF_MISC|BPF_TXA);
2019                 i++;
2020                 /* A = P[X + packet head] */
2021                 s[i] = new_stmt(BPF_LD|BPF_IND|BPF_B);
2022                 s[i]->s.k = off_nl;
2023                 i++;
2024                 /* MEM[reg2] = A */
2025                 s[i] = new_stmt(BPF_ST);
2026                 s[i]->s.k = reg2;
2027                 i++;
2028                 /* A = X */
2029                 s[i] = new_stmt(BPF_MISC|BPF_TXA);
2030                 i++;
2031                 /* A += 1 */
2032                 s[i] = new_stmt(BPF_ALU|BPF_ADD|BPF_K);
2033                 s[i]->s.k = 1;
2034                 i++;
2035                 /* X = A */
2036                 s[i] = new_stmt(BPF_MISC|BPF_TAX);
2037                 i++;
2038                 /* A = P[X + packet head]; */
2039                 s[i] = new_stmt(BPF_LD|BPF_IND|BPF_B);
2040                 s[i]->s.k = off_nl;
2041                 i++;
2042                 /* A += 1 */
2043                 s[i] = new_stmt(BPF_ALU|BPF_ADD|BPF_K);
2044                 s[i]->s.k = 1;
2045                 i++;
2046                 /* A *= 8 */
2047                 s[i] = new_stmt(BPF_ALU|BPF_MUL|BPF_K);
2048                 s[i]->s.k = 8;
2049                 i++;
2050                 /* X = A; */
2051                 s[i] = new_stmt(BPF_MISC|BPF_TAX);
2052                 i++;
2053                 /* A = MEM[reg2] */
2054                 s[i] = new_stmt(BPF_LD|BPF_MEM);
2055                 s[i]->s.k = reg2;
2056                 i++;
2057
2058                 /* goto again; (must use BPF_JA for backward jump) */
2059                 s[i] = new_stmt(BPF_JMP|BPF_JA);
2060                 s[i]->s.k = again - i - 1;
2061                 s[i - 1]->s.jf = s[i];
2062                 i++;
2063
2064                 /* fixup */
2065                 for (j = v6start; j <= v6end; j++)
2066                         s[j]->s.jt = s[v6advance];
2067         } else
2068 #endif
2069         {
2070                 /* nop */
2071                 s[i] = new_stmt(BPF_ALU|BPF_ADD|BPF_K);
2072                 s[i]->s.k = 0;
2073                 s[fix2]->s.jf = s[i];
2074                 i++;
2075         }
2076
2077         /* ahcheck: */
2078         ahcheck = i;
2079         /* if (A == IPPROTO_AH) then fall through; else goto end; */
2080         s[i] = new_stmt(BPF_JMP|BPF_JEQ|BPF_K);
2081         s[i]->s.jt = NULL;      /*later*/
2082         s[i]->s.jf = NULL;      /*later*/
2083         s[i]->s.k = IPPROTO_AH;
2084         if (fix3)
2085                 s[fix3]->s.jf = s[ahcheck];
2086         fix4 = i;
2087         i++;
2088
2089         /*
2090          * in short,
2091          * A = P[X];
2092          * X = X + (P[X + 1] + 2) * 4;
2093          */
2094         /* A = X */
2095         s[i - 1]->s.jt = s[i] = new_stmt(BPF_MISC|BPF_TXA);
2096         i++;
2097         /* A = P[X + packet head]; */
2098         s[i] = new_stmt(BPF_LD|BPF_IND|BPF_B);
2099         s[i]->s.k = off_nl;
2100         i++;
2101         /* MEM[reg2] = A */
2102         s[i] = new_stmt(BPF_ST);
2103         s[i]->s.k = reg2;
2104         i++;
2105         /* A = X */
2106         s[i - 1]->s.jt = s[i] = new_stmt(BPF_MISC|BPF_TXA);
2107         i++;
2108         /* A += 1 */
2109         s[i] = new_stmt(BPF_ALU|BPF_ADD|BPF_K);
2110         s[i]->s.k = 1;
2111         i++;
2112         /* X = A */
2113         s[i] = new_stmt(BPF_MISC|BPF_TAX);
2114         i++;
2115         /* A = P[X + packet head] */
2116         s[i] = new_stmt(BPF_LD|BPF_IND|BPF_B);
2117         s[i]->s.k = off_nl;
2118         i++;
2119         /* A += 2 */
2120         s[i] = new_stmt(BPF_ALU|BPF_ADD|BPF_K);
2121         s[i]->s.k = 2;
2122         i++;
2123         /* A *= 4 */
2124         s[i] = new_stmt(BPF_ALU|BPF_MUL|BPF_K);
2125         s[i]->s.k = 4;
2126         i++;
2127         /* X = A; */
2128         s[i] = new_stmt(BPF_MISC|BPF_TAX);
2129         i++;
2130         /* A = MEM[reg2] */
2131         s[i] = new_stmt(BPF_LD|BPF_MEM);
2132         s[i]->s.k = reg2;
2133         i++;
2134
2135         /* goto again; (must use BPF_JA for backward jump) */
2136         s[i] = new_stmt(BPF_JMP|BPF_JA);
2137         s[i]->s.k = again - i - 1;
2138         i++;
2139
2140         /* end: nop */
2141         end = i;
2142         s[i] = new_stmt(BPF_ALU|BPF_ADD|BPF_K);
2143         s[i]->s.k = 0;
2144         s[fix2]->s.jt = s[end];
2145         s[fix4]->s.jf = s[end];
2146         s[fix5]->s.jt = s[end];
2147         i++;
2148
2149         /*
2150          * make slist chain
2151          */
2152         max = i;
2153         for (i = 0; i < max - 1; i++)
2154                 s[i]->next = s[i + 1];
2155         s[max - 1]->next = NULL;
2156
2157         /*
2158          * emit final check
2159          */
2160         b = new_block(JMP(BPF_JEQ));
2161         b->stmts = s[1];        /*remember, s[0] is dummy*/
2162         b->s.k = v;
2163
2164         free_reg(reg2);
2165
2166         gen_and(b0, b);
2167         return b;
2168 #endif
2169 }
2170
2171 static struct block *
2172 gen_proto(v, proto, dir)
2173         int v;
2174         int proto;
2175         int dir;
2176 {
2177         struct block *b0, *b1;
2178
2179         if (dir != Q_DEFAULT)
2180                 bpf_error("direction applied to 'proto'");
2181
2182         switch (proto) {
2183         case Q_DEFAULT:
2184 #ifdef INET6
2185                 b0 = gen_proto(v, Q_IP, dir);
2186                 b1 = gen_proto(v, Q_IPV6, dir);
2187                 gen_or(b0, b1);
2188                 return b1;
2189 #else
2190                 /*FALLTHROUGH*/
2191 #endif
2192         case Q_IP:
2193                 b0 = gen_linktype(ETHERTYPE_IP);
2194 #ifndef CHASE_CHAIN
2195                 b1 = gen_cmp(off_nl + 9, BPF_B, (bpf_int32)v);
2196 #else
2197                 b1 = gen_protochain(v, Q_IP);
2198 #endif
2199                 gen_and(b0, b1);
2200                 return b1;
2201
2202         case Q_ISO:
2203                 b0 = gen_linktype(LLC_ISO_LSAP);
2204                 b1 = gen_cmp(off_nl + 3, BPF_B, (long)v);
2205                 gen_and(b0, b1);
2206                 return b1;
2207
2208         case Q_ARP:
2209                 bpf_error("arp does not encapsulate another protocol");
2210                 /* NOTREACHED */
2211
2212         case Q_RARP:
2213                 bpf_error("rarp does not encapsulate another protocol");
2214                 /* NOTREACHED */
2215
2216         case Q_ATALK:
2217                 bpf_error("atalk encapsulation is not specifiable");
2218                 /* NOTREACHED */
2219
2220         case Q_DECNET:
2221                 bpf_error("decnet encapsulation is not specifiable");
2222                 /* NOTREACHED */
2223
2224         case Q_SCA:
2225                 bpf_error("sca does not encapsulate another protocol");
2226                 /* NOTREACHED */
2227
2228         case Q_LAT:
2229                 bpf_error("lat does not encapsulate another protocol");
2230                 /* NOTREACHED */
2231
2232         case Q_MOPRC:
2233                 bpf_error("moprc does not encapsulate another protocol");
2234                 /* NOTREACHED */
2235
2236         case Q_MOPDL:
2237                 bpf_error("mopdl does not encapsulate another protocol");
2238                 /* NOTREACHED */
2239
2240         case Q_LINK:
2241                 return gen_linktype(v);
2242
2243         case Q_UDP:
2244                 bpf_error("'udp proto' is bogus");
2245                 /* NOTREACHED */
2246
2247         case Q_TCP:
2248                 bpf_error("'tcp proto' is bogus");
2249                 /* NOTREACHED */
2250
2251         case Q_ICMP:
2252                 bpf_error("'icmp proto' is bogus");
2253                 /* NOTREACHED */
2254
2255         case Q_IGMP:
2256                 bpf_error("'igmp proto' is bogus");
2257                 /* NOTREACHED */
2258
2259         case Q_IGRP:
2260                 bpf_error("'igrp proto' is bogus");
2261                 /* NOTREACHED */
2262
2263         case Q_PIM:
2264                 bpf_error("'pim proto' is bogus");
2265                 /* NOTREACHED */
2266
2267 #ifdef INET6
2268         case Q_IPV6:
2269                 b0 = gen_linktype(ETHERTYPE_IPV6);
2270 #ifndef CHASE_CHAIN
2271                 b1 = gen_cmp(off_nl + 6, BPF_B, (bpf_int32)v);
2272 #else
2273                 b1 = gen_protochain(v, Q_IPV6);
2274 #endif
2275                 gen_and(b0, b1);
2276                 return b1;
2277
2278         case Q_ICMPV6:
2279                 bpf_error("'icmp6 proto' is bogus");
2280 #endif /* INET6 */
2281
2282         case Q_AH:
2283                 bpf_error("'ah proto' is bogus");
2284
2285         case Q_ESP:
2286                 bpf_error("'ah proto' is bogus");
2287
2288         default:
2289                 abort();
2290                 /* NOTREACHED */
2291         }
2292         /* NOTREACHED */
2293 }
2294
2295 struct block *
2296 gen_scode(name, q)
2297         register const char *name;
2298         struct qual q;
2299 {
2300         int proto = q.proto;
2301         int dir = q.dir;
2302         int tproto;
2303         u_char *eaddr;
2304         bpf_u_int32 mask, addr;
2305 #ifndef INET6
2306         bpf_u_int32 **alist;
2307 #else
2308         int tproto6;
2309         struct sockaddr_in *sin;
2310         struct sockaddr_in6 *sin6;
2311         struct addrinfo *res, *res0;
2312         struct in6_addr mask128;
2313 #endif /*INET6*/
2314         struct block *b, *tmp;
2315         int port, real_proto;
2316
2317         switch (q.addr) {
2318
2319         case Q_NET:
2320                 addr = pcap_nametonetaddr(name);
2321                 if (addr == 0)
2322                         bpf_error("unknown network '%s'", name);
2323                 /* Left justify network addr and calculate its network mask */
2324                 mask = 0xffffffff;
2325                 while (addr && (addr & 0xff000000) == 0) {
2326                         addr <<= 8;
2327                         mask <<= 8;
2328                 }
2329                 return gen_host(addr, mask, proto, dir);
2330
2331         case Q_DEFAULT:
2332         case Q_HOST:
2333                 if (proto == Q_LINK) {
2334                         switch (linktype) {
2335
2336                         case DLT_EN10MB:
2337                                 eaddr = pcap_ether_hostton(name);
2338                                 if (eaddr == NULL)
2339                                         bpf_error(
2340                                             "unknown ether host '%s'", name);
2341                                 return gen_ehostop(eaddr, dir);
2342
2343                         case DLT_FDDI:
2344                                 eaddr = pcap_ether_hostton(name);
2345                                 if (eaddr == NULL)
2346                                         bpf_error(
2347                                             "unknown FDDI host '%s'", name);
2348                                 return gen_fhostop(eaddr, dir);
2349
2350                         case DLT_IEEE802:
2351                                 eaddr = pcap_ether_hostton(name);
2352                                 if (eaddr == NULL)
2353                                         bpf_error(
2354                                             "unknown token ring host '%s'", name);
2355                                 return gen_thostop(eaddr, dir);
2356
2357                         default:
2358                                 bpf_error(
2359                         "only ethernet/FDDI/token ring supports link-level host name");
2360                                 break;
2361                         }
2362                 } else if (proto == Q_DECNET) {
2363                         unsigned short dn_addr = __pcap_nametodnaddr(name);
2364                         /*
2365                          * I don't think DECNET hosts can be multihomed, so
2366                          * there is no need to build up a list of addresses
2367                          */
2368                         return (gen_host(dn_addr, 0, proto, dir));
2369                 } else {
2370 #ifndef INET6
2371                         alist = pcap_nametoaddr(name);
2372                         if (alist == NULL || *alist == NULL)
2373                                 bpf_error("unknown host '%s'", name);
2374                         tproto = proto;
2375                         if (off_linktype == -1 && tproto == Q_DEFAULT)
2376                                 tproto = Q_IP;
2377                         b = gen_host(**alist++, 0xffffffff, tproto, dir);
2378                         while (*alist) {
2379                                 tmp = gen_host(**alist++, 0xffffffff,
2380                                                tproto, dir);
2381                                 gen_or(b, tmp);
2382                                 b = tmp;
2383                         }
2384                         return b;
2385 #else
2386                         memset(&mask128, 0xff, sizeof(mask128));
2387                         res0 = res = pcap_nametoaddrinfo(name);
2388                         if (res == NULL)
2389                                 bpf_error("unknown host '%s'", name);
2390                         b = tmp = NULL;
2391                         tproto = tproto6 = proto;
2392                         if (off_linktype == -1 && tproto == Q_DEFAULT) {
2393                                 tproto = Q_IP;
2394                                 tproto6 = Q_IPV6;
2395                         }
2396                         for (res = res0; res; res = res->ai_next) {
2397                                 switch (res->ai_family) {
2398                                 case AF_INET:
2399                                         if (tproto == Q_IPV6)
2400                                                 continue;
2401
2402                                         sin = (struct sockaddr_in *)
2403                                                 res->ai_addr;
2404                                         tmp = gen_host(ntohl(sin->sin_addr.s_addr),
2405                                                 0xffffffff, tproto, dir);
2406                                         break;
2407                                 case AF_INET6:
2408                                         if (tproto6 == Q_IP)
2409                                                 continue;
2410
2411                                         sin6 = (struct sockaddr_in6 *)
2412                                                 res->ai_addr;
2413                                         tmp = gen_host6(&sin6->sin6_addr,
2414                                                 &mask128, tproto6, dir);
2415                                         break;
2416                                 }
2417                                 if (b)
2418                                         gen_or(b, tmp);
2419                                 b = tmp;
2420                         }
2421                         freeaddrinfo(res0);
2422                         if (b == NULL) {
2423                                 bpf_error("unknown host '%s'%s", name,
2424                                     (proto == Q_DEFAULT)
2425                                         ? ""
2426                                         : " for specified address family");
2427                         }
2428                         return b;
2429 #endif /*INET6*/
2430                 }
2431
2432         case Q_PORT:
2433                 if (proto != Q_DEFAULT && proto != Q_UDP && proto != Q_TCP)
2434                         bpf_error("illegal qualifier of 'port'");
2435                 if (pcap_nametoport(name, &port, &real_proto) == 0)
2436                         bpf_error("unknown port '%s'", name);
2437                 if (proto == Q_UDP) {
2438                         if (real_proto == IPPROTO_TCP)
2439                                 bpf_error("port '%s' is tcp", name);
2440                         else
2441                                 /* override PROTO_UNDEF */
2442                                 real_proto = IPPROTO_UDP;
2443                 }
2444                 if (proto == Q_TCP) {
2445                         if (real_proto == IPPROTO_UDP)
2446                                 bpf_error("port '%s' is udp", name);
2447                         else
2448                                 /* override PROTO_UNDEF */
2449                                 real_proto = IPPROTO_TCP;
2450                 }
2451 #ifndef INET6
2452                 return gen_port(port, real_proto, dir);
2453 #else
2454             {
2455                 struct block *b;
2456                 b = gen_port(port, real_proto, dir);
2457                 gen_or(gen_port6(port, real_proto, dir), b);
2458                 return b;
2459             }
2460 #endif /* INET6 */
2461
2462         case Q_GATEWAY:
2463 #ifndef INET6
2464                 eaddr = pcap_ether_hostton(name);
2465                 if (eaddr == NULL)
2466                         bpf_error("unknown ether host: %s", name);
2467
2468                 alist = pcap_nametoaddr(name);
2469                 if (alist == NULL || *alist == NULL)
2470                         bpf_error("unknown host '%s'", name);
2471                 return gen_gateway(eaddr, alist, proto, dir);
2472 #else
2473                 bpf_error("'gateway' not supported in this configuration");
2474 #endif /*INET6*/
2475
2476         case Q_PROTO:
2477                 real_proto = lookup_proto(name, proto);
2478                 if (real_proto >= 0)
2479                         return gen_proto(real_proto, proto, dir);
2480                 else
2481                         bpf_error("unknown protocol: %s", name);
2482
2483         case Q_PROTOCHAIN:
2484                 real_proto = lookup_proto(name, proto);
2485                 if (real_proto >= 0)
2486                         return gen_protochain(real_proto, proto, dir);
2487                 else
2488                         bpf_error("unknown protocol: %s", name);
2489
2490
2491         case Q_UNDEF:
2492                 syntax();
2493                 /* NOTREACHED */
2494         }
2495         abort();
2496         /* NOTREACHED */
2497 }
2498
2499 struct block *
2500 gen_mcode(s1, s2, masklen, q)
2501         register const char *s1, *s2;
2502         register int masklen;
2503         struct qual q;
2504 {
2505         register int nlen, mlen;
2506         bpf_u_int32 n, m;
2507
2508         nlen = __pcap_atoin(s1, &n);
2509         /* Promote short ipaddr */
2510         n <<= 32 - nlen;
2511
2512         if (s2 != NULL) {
2513                 mlen = __pcap_atoin(s2, &m);
2514                 /* Promote short ipaddr */
2515                 m <<= 32 - mlen;
2516                 if ((n & ~m) != 0)
2517                         bpf_error("non-network bits set in \"%s mask %s\"",
2518                             s1, s2);
2519         } else {
2520                 /* Convert mask len to mask */
2521                 if (masklen > 32)
2522                         bpf_error("mask length must be <= 32");
2523                 m = 0xffffffff << (32 - masklen);
2524                 if ((n & ~m) != 0)
2525                         bpf_error("non-network bits set in \"%s/%d\"",
2526                             s1, masklen);
2527         }
2528
2529         switch (q.addr) {
2530
2531         case Q_NET:
2532                 return gen_host(n, m, q.proto, q.dir);
2533
2534         default:
2535                 bpf_error("Mask syntax for networks only");
2536                 /* NOTREACHED */
2537         }
2538 }
2539
2540 struct block *
2541 gen_ncode(s, v, q)
2542         register const char *s;
2543         bpf_u_int32 v;
2544         struct qual q;
2545 {
2546         bpf_u_int32 mask;
2547         int proto = q.proto;
2548         int dir = q.dir;
2549         register int vlen;
2550
2551         if (s == NULL)
2552                 vlen = 32;
2553         else if (q.proto == Q_DECNET)
2554                 vlen = __pcap_atodn(s, &v);
2555         else
2556                 vlen = __pcap_atoin(s, &v);
2557
2558         switch (q.addr) {
2559
2560         case Q_DEFAULT:
2561         case Q_HOST:
2562         case Q_NET:
2563                 if (proto == Q_DECNET)
2564                         return gen_host(v, 0, proto, dir);
2565                 else if (proto == Q_LINK) {
2566                         bpf_error("illegal link layer address");
2567                 } else {
2568                         mask = 0xffffffff;
2569                         if (s == NULL && q.addr == Q_NET) {
2570                                 /* Promote short net number */
2571                                 while (v && (v & 0xff000000) == 0) {
2572                                         v <<= 8;
2573                                         mask <<= 8;
2574                                 }
2575                         } else {
2576                                 /* Promote short ipaddr */
2577                                 v <<= 32 - vlen;
2578                                 mask <<= 32 - vlen;
2579                         }
2580                         return gen_host(v, mask, proto, dir);
2581                 }
2582
2583         case Q_PORT:
2584                 if (proto == Q_UDP)
2585                         proto = IPPROTO_UDP;
2586                 else if (proto == Q_TCP)
2587                         proto = IPPROTO_TCP;
2588                 else if (proto == Q_DEFAULT)
2589                         proto = PROTO_UNDEF;
2590                 else
2591                         bpf_error("illegal qualifier of 'port'");
2592
2593 #ifndef INET6
2594                 return gen_port((int)v, proto, dir);
2595 #else
2596             {
2597                 struct block *b;
2598                 b = gen_port((int)v, proto, dir);
2599                 gen_or(gen_port6((int)v, proto, dir), b);
2600                 return b;
2601             }
2602 #endif /* INET6 */
2603
2604         case Q_GATEWAY:
2605                 bpf_error("'gateway' requires a name");
2606                 /* NOTREACHED */
2607
2608         case Q_PROTO:
2609                 return gen_proto((int)v, proto, dir);
2610
2611         case Q_PROTOCHAIN:
2612                 return gen_protochain((int)v, proto, dir);
2613
2614         case Q_UNDEF:
2615                 syntax();
2616                 /* NOTREACHED */
2617
2618         default:
2619                 abort();
2620                 /* NOTREACHED */
2621         }
2622         /* NOTREACHED */
2623 }
2624
2625 #ifdef INET6
2626 struct block *
2627 gen_mcode6(s1, s2, masklen, q)
2628         register const char *s1, *s2;
2629         register int masklen;
2630         struct qual q;
2631 {
2632         struct addrinfo *res;
2633         struct in6_addr *addr;
2634         struct in6_addr mask;
2635         struct block *b;
2636         u_int32_t *a, *m;
2637
2638         if (s2)
2639                 bpf_error("no mask %s supported", s2);
2640
2641         res = pcap_nametoaddrinfo(s1);
2642         if (!res)
2643                 bpf_error("invalid ip6 address %s", s1);
2644         if (res->ai_next)
2645                 bpf_error("%s resolved to multiple address", s1);
2646         addr = &((struct sockaddr_in6 *)res->ai_addr)->sin6_addr;
2647
2648         if (sizeof(mask) * 8 < masklen)
2649                 bpf_error("mask length must be <= %u", (unsigned int)(sizeof(mask) * 8));
2650         memset(&mask, 0xff, masklen / 8);
2651         if (masklen % 8) {
2652                 mask.s6_addr[masklen / 8] =
2653                         (0xff << (8 - masklen % 8)) & 0xff;
2654         }
2655
2656         a = (u_int32_t *)addr;
2657         m = (u_int32_t *)&mask;
2658         if ((a[0] & ~m[0]) || (a[1] & ~m[1])
2659          || (a[2] & ~m[2]) || (a[3] & ~m[3])) {
2660                 bpf_error("non-network bits set in \"%s/%d\"", s1, masklen);
2661         }
2662
2663         switch (q.addr) {
2664
2665         case Q_DEFAULT:
2666         case Q_HOST:
2667                 if (masklen != 128)
2668                         bpf_error("Mask syntax for networks only");
2669                 /* FALLTHROUGH */
2670
2671         case Q_NET:
2672                 b = gen_host6(addr, &mask, q.proto, q.dir);
2673                 freeaddrinfo(res);
2674                 return b;
2675
2676         default:
2677                 bpf_error("invalid qualifier against IPv6 address");
2678                 /* NOTREACHED */
2679         }
2680 }
2681 #endif /*INET6*/
2682
2683 struct block *
2684 gen_ecode(eaddr, q)
2685         register const u_char *eaddr;
2686         struct qual q;
2687 {
2688         if ((q.addr == Q_HOST || q.addr == Q_DEFAULT) && q.proto == Q_LINK) {
2689                 if (linktype == DLT_EN10MB)
2690                         return gen_ehostop(eaddr, (int)q.dir);
2691                 if (linktype == DLT_FDDI)
2692                         return gen_fhostop(eaddr, (int)q.dir);
2693                 if (linktype == DLT_IEEE802)
2694                         return gen_thostop(eaddr, (int)q.dir);
2695                 bpf_error("ethernet addresses supported only on ethernet, FDDI or token ring");
2696         }
2697         bpf_error("ethernet address used in non-ether expression");
2698         /* NOTREACHED */
2699 }
2700
2701 void
2702 sappend(s0, s1)
2703         struct slist *s0, *s1;
2704 {
2705         /*
2706          * This is definitely not the best way to do this, but the
2707          * lists will rarely get long.
2708          */
2709         while (s0->next)
2710                 s0 = s0->next;
2711         s0->next = s1;
2712 }
2713
2714 static struct slist *
2715 xfer_to_x(a)
2716         struct arth *a;
2717 {
2718         struct slist *s;
2719
2720         s = new_stmt(BPF_LDX|BPF_MEM);
2721         s->s.k = a->regno;
2722         return s;
2723 }
2724
2725 static struct slist *
2726 xfer_to_a(a)
2727         struct arth *a;
2728 {
2729         struct slist *s;
2730
2731         s = new_stmt(BPF_LD|BPF_MEM);
2732         s->s.k = a->regno;
2733         return s;
2734 }
2735
2736 struct arth *
2737 gen_load(proto, index, size)
2738         int proto;
2739         struct arth *index;
2740         int size;
2741 {
2742         struct slist *s, *tmp;
2743         struct block *b;
2744         int regno = alloc_reg();
2745
2746         free_reg(index->regno);
2747         switch (size) {
2748
2749         default:
2750                 bpf_error("data size must be 1, 2, or 4");
2751
2752         case 1:
2753                 size = BPF_B;
2754                 break;
2755
2756         case 2:
2757                 size = BPF_H;
2758                 break;
2759
2760         case 4:
2761                 size = BPF_W;
2762                 break;
2763         }
2764         switch (proto) {
2765         default:
2766                 bpf_error("unsupported index operation");
2767
2768         case Q_LINK:
2769                 s = xfer_to_x(index);
2770                 tmp = new_stmt(BPF_LD|BPF_IND|size);
2771                 sappend(s, tmp);
2772                 sappend(index->s, s);
2773                 break;
2774
2775         case Q_IP:
2776         case Q_ARP:
2777         case Q_RARP:
2778         case Q_ATALK:
2779         case Q_DECNET:
2780         case Q_SCA:
2781         case Q_LAT:
2782         case Q_MOPRC:
2783         case Q_MOPDL:
2784 #ifdef INET6
2785         case Q_IPV6:
2786 #endif
2787                 /* XXX Note that we assume a fixed link header here. */
2788                 s = xfer_to_x(index);
2789                 tmp = new_stmt(BPF_LD|BPF_IND|size);
2790                 tmp->s.k = off_nl;
2791                 sappend(s, tmp);
2792                 sappend(index->s, s);
2793
2794                 b = gen_proto_abbrev(proto);
2795                 if (index->b)
2796                         gen_and(index->b, b);
2797                 index->b = b;
2798                 break;
2799
2800         case Q_TCP:
2801         case Q_UDP:
2802         case Q_ICMP:
2803         case Q_IGMP:
2804         case Q_IGRP:
2805         case Q_PIM:
2806                 s = new_stmt(BPF_LDX|BPF_MSH|BPF_B);
2807                 s->s.k = off_nl;
2808                 sappend(s, xfer_to_a(index));
2809                 sappend(s, new_stmt(BPF_ALU|BPF_ADD|BPF_X));
2810                 sappend(s, new_stmt(BPF_MISC|BPF_TAX));
2811                 sappend(s, tmp = new_stmt(BPF_LD|BPF_IND|size));
2812                 tmp->s.k = off_nl;
2813                 sappend(index->s, s);
2814
2815                 gen_and(gen_proto_abbrev(proto), b = gen_ipfrag());
2816                 if (index->b)
2817                         gen_and(index->b, b);
2818 #ifdef INET6
2819                 gen_and(gen_proto_abbrev(Q_IP), b);
2820 #endif
2821                 index->b = b;
2822                 break;
2823 #ifdef INET6
2824         case Q_ICMPV6:
2825                 bpf_error("IPv6 upper-layer protocol is not supported by proto[x]");
2826                 /*NOTREACHED*/
2827 #endif
2828         }
2829         index->regno = regno;
2830         s = new_stmt(BPF_ST);
2831         s->s.k = regno;
2832         sappend(index->s, s);
2833
2834         return index;
2835 }
2836
2837 struct block *
2838 gen_relation(code, a0, a1, reversed)
2839         int code;
2840         struct arth *a0, *a1;
2841         int reversed;
2842 {
2843         struct slist *s0, *s1, *s2;
2844         struct block *b, *tmp;
2845
2846         s0 = xfer_to_x(a1);
2847         s1 = xfer_to_a(a0);
2848         s2 = new_stmt(BPF_ALU|BPF_SUB|BPF_X);
2849         b = new_block(JMP(code));
2850         if (code == BPF_JGT || code == BPF_JGE) {
2851                 reversed = !reversed;
2852                 b->s.k = 0x80000000;
2853         }
2854         if (reversed)
2855                 gen_not(b);
2856
2857         sappend(s1, s2);
2858         sappend(s0, s1);
2859         sappend(a1->s, s0);
2860         sappend(a0->s, a1->s);
2861
2862         b->stmts = a0->s;
2863
2864         free_reg(a0->regno);
2865         free_reg(a1->regno);
2866
2867         /* 'and' together protocol checks */
2868         if (a0->b) {
2869                 if (a1->b) {
2870                         gen_and(a0->b, tmp = a1->b);
2871                 }
2872                 else
2873                         tmp = a0->b;
2874         } else
2875                 tmp = a1->b;
2876
2877         if (tmp)
2878                 gen_and(tmp, b);
2879
2880         return b;
2881 }
2882
2883 struct arth *
2884 gen_loadlen()
2885 {
2886         int regno = alloc_reg();
2887         struct arth *a = (struct arth *)newchunk(sizeof(*a));
2888         struct slist *s;
2889
2890         s = new_stmt(BPF_LD|BPF_LEN);
2891         s->next = new_stmt(BPF_ST);
2892         s->next->s.k = regno;
2893         a->s = s;
2894         a->regno = regno;
2895
2896         return a;
2897 }
2898
2899 struct arth *
2900 gen_loadi(val)
2901         int val;
2902 {
2903         struct arth *a;
2904         struct slist *s;
2905         int reg;
2906
2907         a = (struct arth *)newchunk(sizeof(*a));
2908
2909         reg = alloc_reg();
2910
2911         s = new_stmt(BPF_LD|BPF_IMM);
2912         s->s.k = val;
2913         s->next = new_stmt(BPF_ST);
2914         s->next->s.k = reg;
2915         a->s = s;
2916         a->regno = reg;
2917
2918         return a;
2919 }
2920
2921 struct arth *
2922 gen_neg(a)
2923         struct arth *a;
2924 {
2925         struct slist *s;
2926
2927         s = xfer_to_a(a);
2928         sappend(a->s, s);
2929         s = new_stmt(BPF_ALU|BPF_NEG);
2930         s->s.k = 0;
2931         sappend(a->s, s);
2932         s = new_stmt(BPF_ST);
2933         s->s.k = a->regno;
2934         sappend(a->s, s);
2935
2936         return a;
2937 }
2938
2939 struct arth *
2940 gen_arth(code, a0, a1)
2941         int code;
2942         struct arth *a0, *a1;
2943 {
2944         struct slist *s0, *s1, *s2;
2945
2946         s0 = xfer_to_x(a1);
2947         s1 = xfer_to_a(a0);
2948         s2 = new_stmt(BPF_ALU|BPF_X|code);
2949
2950         sappend(s1, s2);
2951         sappend(s0, s1);
2952         sappend(a1->s, s0);
2953         sappend(a0->s, a1->s);
2954
2955         free_reg(a1->regno);
2956
2957         s0 = new_stmt(BPF_ST);
2958         a0->regno = s0->s.k = alloc_reg();
2959         sappend(a0->s, s0);
2960
2961         return a0;
2962 }
2963
2964 /*
2965  * Here we handle simple allocation of the scratch registers.
2966  * If too many registers are alloc'd, the allocator punts.
2967  */
2968 static int regused[BPF_MEMWORDS];
2969 static int curreg;
2970
2971 /*
2972  * Return the next free register.
2973  */
2974 static int
2975 alloc_reg()
2976 {
2977         int n = BPF_MEMWORDS;
2978
2979         while (--n >= 0) {
2980                 if (regused[curreg])
2981                         curreg = (curreg + 1) % BPF_MEMWORDS;
2982                 else {
2983                         regused[curreg] = 1;
2984                         return curreg;
2985                 }
2986         }
2987         bpf_error("too many registers needed to evaluate expression");
2988         /* NOTREACHED */
2989 }
2990
2991 /*
2992  * Return a register to the table so it can
2993  * be used later.
2994  */
2995 static void
2996 free_reg(n)
2997         int n;
2998 {
2999         regused[n] = 0;
3000 }
3001
3002 static struct block *
3003 gen_len(jmp, n)
3004         int jmp, n;
3005 {
3006         struct slist *s;
3007         struct block *b;
3008
3009         s = new_stmt(BPF_LD|BPF_LEN);
3010         b = new_block(JMP(jmp));
3011         b->stmts = s;
3012         b->s.k = n;
3013
3014         return b;
3015 }
3016
3017 struct block *
3018 gen_greater(n)
3019         int n;
3020 {
3021         return gen_len(BPF_JGE, n);
3022 }
3023
3024 /*
3025  * Actually, this is less than or equal.
3026  */
3027 struct block *
3028 gen_less(n)
3029         int n;
3030 {
3031         struct block *b;
3032
3033         b = gen_len(BPF_JGT, n);
3034         gen_not(b);
3035
3036         return b;
3037 }
3038
3039 struct block *
3040 gen_byteop(op, idx, val)
3041         int op, idx, val;
3042 {
3043         struct block *b;
3044         struct slist *s;
3045
3046         switch (op) {
3047         default:
3048                 abort();
3049
3050         case '=':
3051                 return gen_cmp((u_int)idx, BPF_B, (bpf_int32)val);
3052
3053         case '<':
3054                 b = gen_cmp((u_int)idx, BPF_B, (bpf_int32)val);
3055                 b->s.code = JMP(BPF_JGE);
3056                 gen_not(b);
3057                 return b;
3058
3059         case '>':
3060                 b = gen_cmp((u_int)idx, BPF_B, (bpf_int32)val);
3061                 b->s.code = JMP(BPF_JGT);
3062                 return b;
3063
3064         case '|':
3065                 s = new_stmt(BPF_ALU|BPF_OR|BPF_K);
3066                 break;
3067
3068         case '&':
3069                 s = new_stmt(BPF_ALU|BPF_AND|BPF_K);
3070                 break;
3071         }
3072         s->s.k = val;
3073         b = new_block(JMP(BPF_JEQ));
3074         b->stmts = s;
3075         gen_not(b);
3076
3077         return b;
3078 }
3079
3080 struct block *
3081 gen_broadcast(proto)
3082         int proto;
3083 {
3084         bpf_u_int32 hostmask;
3085         struct block *b0, *b1, *b2;
3086         static u_char ebroadcast[] = { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff };
3087
3088         switch (proto) {
3089
3090         case Q_DEFAULT:
3091         case Q_LINK:
3092                 if (linktype == DLT_EN10MB)
3093                         return gen_ehostop(ebroadcast, Q_DST);
3094                 if (linktype == DLT_FDDI)
3095                         return gen_fhostop(ebroadcast, Q_DST);
3096                 if (linktype == DLT_IEEE802)
3097                         return gen_thostop(ebroadcast, Q_DST);
3098                 bpf_error("not a broadcast link");
3099                 break;
3100
3101         case Q_IP:
3102                 b0 = gen_linktype(ETHERTYPE_IP);
3103                 hostmask = ~netmask;
3104                 b1 = gen_mcmp(off_nl + 16, BPF_W, (bpf_int32)0, hostmask);
3105                 b2 = gen_mcmp(off_nl + 16, BPF_W,
3106                               (bpf_int32)(~0 & hostmask), hostmask);
3107                 gen_or(b1, b2);
3108                 gen_and(b0, b2);
3109                 return b2;
3110         }
3111         bpf_error("only ether/ip broadcast filters supported");
3112 }
3113
3114 struct block *
3115 gen_multicast(proto)
3116         int proto;
3117 {
3118         register struct block *b0, *b1;
3119         register struct slist *s;
3120
3121         switch (proto) {
3122
3123         case Q_DEFAULT:
3124         case Q_LINK:
3125                 if (linktype == DLT_EN10MB) {
3126                         /* ether[0] & 1 != 0 */
3127                         s = new_stmt(BPF_LD|BPF_B|BPF_ABS);
3128                         s->s.k = 0;
3129                         b0 = new_block(JMP(BPF_JSET));
3130                         b0->s.k = 1;
3131                         b0->stmts = s;
3132                         return b0;
3133                 }
3134
3135                 if (linktype == DLT_FDDI) {
3136                         /* XXX TEST THIS: MIGHT NOT PORT PROPERLY XXX */
3137                         /* fddi[1] & 1 != 0 */
3138                         s = new_stmt(BPF_LD|BPF_B|BPF_ABS);
3139                         s->s.k = 1;
3140                         b0 = new_block(JMP(BPF_JSET));
3141                         b0->s.k = 1;
3142                         b0->stmts = s;
3143                         return b0;
3144                 }
3145
3146                 /* TODO - check how token ring handles multicast */
3147                 /* if (linktype == DLT_IEEE802) ... */
3148
3149                 /* Link not known to support multicasts */
3150                 break;
3151
3152         case Q_IP:
3153                 b0 = gen_linktype(ETHERTYPE_IP);
3154                 b1 = gen_cmp(off_nl + 16, BPF_B, (bpf_int32)224);
3155                 b1->s.code = JMP(BPF_JGE);
3156                 gen_and(b0, b1);
3157                 return b1;
3158
3159 #ifdef INET6
3160         case Q_IPV6:
3161                 b0 = gen_linktype(ETHERTYPE_IPV6);
3162                 b1 = gen_cmp(off_nl + 24, BPF_B, (bpf_int32)255);
3163                 gen_and(b0, b1);
3164                 return b1;
3165 #endif /* INET6 */
3166         }
3167         bpf_error("only IP multicast filters supported on ethernet/FDDI");
3168 }
3169
3170 /*
3171  * generate command for inbound/outbound.  It's here so we can
3172  * make it link-type specific.  'dir' = 0 implies "inbound",
3173  * = 1 implies "outbound".
3174  */
3175 struct block *
3176 gen_inbound(dir)
3177         int dir;
3178 {
3179         register struct block *b0;
3180
3181         /*
3182          * Only some data link types support inbound/outbound qualifiers.
3183          */
3184         switch (linktype) {
3185         case DLT_SLIP:
3186         case DLT_PPP:
3187                 b0 = gen_relation(BPF_JEQ,
3188                           gen_load(Q_LINK, gen_loadi(0), 1),
3189                           gen_loadi(0),
3190                           dir);
3191                 break;
3192
3193         default:
3194                 bpf_error("inbound/outbound not supported on linktype %d\n",
3195                     linktype);
3196                 b0 = NULL;
3197                 /* NOTREACHED */
3198         }
3199         return (b0);
3200 }
3201
3202 /*
3203  * support IEEE 802.1Q VLAN trunk over ethernet
3204  */
3205 struct block *
3206 gen_vlan(vlan_num)
3207         int vlan_num;
3208 {
3209         static u_int    orig_linktype = -1, orig_nl = -1;
3210         struct  block   *b0;
3211
3212         /*
3213          * Change the offsets to point to the type and data fields within
3214          * the VLAN packet.  This is somewhat of a kludge.
3215          */
3216         if (orig_nl == (u_int)-1) {
3217                 orig_linktype = off_linktype;   /* save original values */
3218                 orig_nl = off_nl;
3219
3220                 switch (linktype) {
3221
3222                 case DLT_EN10MB:
3223                         off_linktype = 16;
3224                         off_nl = 18;
3225                         break;
3226
3227                 default:
3228                         bpf_error("no VLAN support for data link type %d",
3229                                   linktype);
3230                         /*NOTREACHED*/
3231                 }
3232         }
3233
3234         /* check for VLAN */
3235         b0 = gen_cmp(orig_linktype, BPF_H, (bpf_int32)ETHERTYPE_8021Q);
3236
3237         /* If a specific VLAN is requested, check VLAN id */
3238         if (vlan_num >= 0) {
3239                 struct block *b1;
3240
3241                 b1 = gen_cmp(orig_nl, BPF_H, (bpf_int32)vlan_num);
3242                 gen_and(b0, b1);
3243                 b0 = b1;
3244         }
3245
3246         return (b0);
3247 }