tools/bpf/bpf_exp.y

   1 /*
   2  * BPF asm code parser
   3  *
   4  * This program is free software; you can distribute it and/or modify
   5  * it under the terms of the GNU General Public License as published
   6  * by the Free Software Foundation; either version 2 of the License,
   7  * or (at your option) any later version.
   8  *
   9  * Syntax kept close to:
  10  *
  11  * Steven McCanne and Van Jacobson. 1993. The BSD packet filter: a new
  12  * architecture for user-level packet capture. In Proceedings of the
  13  * USENIX Winter 1993 Conference Proceedings on USENIX Winter 1993
  14  * Conference Proceedings (USENIX'93). USENIX Association, Berkeley,
  15  * CA, USA, 2-2.
  16  *
  17  * Copyright 2013 Daniel Borkmann <borkmann@redhat.com>
  18  * Licensed under the GNU General Public License, version 2.0 (GPLv2)
  19  */
  20
  21 %{
  22
  23 #include <stdio.h>
  24 #include <string.h>
  25 #include <stdint.h>
  26 #include <stdlib.h>
  27 #include <stdbool.h>
  28 #include <unistd.h>
  29 #include <errno.h>
  30 #include <assert.h>
  31 #include <linux/filter.h>
  32
  33 #include "bpf_exp.yacc.h"
  34
  35 enum jmp_type { JTL, JFL, JKL };
  36
  37 extern FILE *yyin;
  38 extern int yylineno;
  39 extern int yylex(void);
  40 extern void yyerror(const char *str);
  41
  42 extern void bpf_asm_compile(FILE *fp, bool cstyle);
  43 static void bpf_set_curr_instr(uint16_t op, uint8_t jt, uint8_t jf, uint32_t k);
  44 static void bpf_set_curr_label(char *label);
  45 static void bpf_set_jmp_label(char *label, enum jmp_type type);
  46
  47 %}
  48
  49 %union {
  50         char *label;
  51         uint32_t number;
  52 }
  53
  54 %token OP_LDB OP_LDH OP_LD OP_LDX OP_ST OP_STX OP_JMP OP_JEQ OP_JGT OP_JGE
  55 %token OP_JSET OP_ADD OP_SUB OP_MUL OP_DIV OP_AND OP_OR OP_XOR OP_LSH OP_RSH
  56 %token OP_RET OP_TAX OP_TXA OP_LDXB OP_MOD OP_NEG OP_JNEQ OP_JLT OP_JLE OP_LDI
  57 %token OP_LDXI
  58
  59 %token K_PKT_LEN
  60
  61 %token ':' ',' '[' ']' '(' ')' 'x' 'a' '+' 'M' '*' '&' '#' '%'
  62
  63 %token extension number label
  64
  65 %type <label> label
  66 %type <number> extension
  67 %type <number> number
  68
  69 %%
  70
  71 prog
  72         : line
  73         | prog line
  74         ;
  75
  76 line
  77         : instr
  78         | labelled_instr
  79         ;
  80
  81 labelled_instr
  82         : labelled instr
  83         ;
  84
  85 instr
  86         : ldb
  87         | ldh
  88         | ld
  89         | ldi
  90         | ldx
  91         | ldxi
  92         | st
  93         | stx
  94         | jmp
  95         | jeq
  96         | jneq
  97         | jlt
  98         | jle
  99         | jgt
 100         | jge
 101         | jset
 102         | add
 103         | sub
 104         | mul
 105         | div
 106         | mod
 107         | neg
 108         | and
 109         | or
 110         | xor
 111         | lsh
 112         | rsh
 113         | ret
 114         | tax
 115         | txa
 116         ;
 117
 118 labelled
 119         : label ':' { bpf_set_curr_label($1); }
 120         ;
 121
 122 ldb
 123         : OP_LDB '[' 'x' '+' number ']' {
 124                 bpf_set_curr_instr(BPF_LD | BPF_B | BPF_IND, 0, 0, $5); }
 125         | OP_LDB '[' '%' 'x' '+' number ']' {
 126                 bpf_set_curr_instr(BPF_LD | BPF_B | BPF_IND, 0, 0, $6); }
 127         | OP_LDB '[' number ']' {
 128                 bpf_set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0, $3); }
 129         | OP_LDB extension {
 130                 bpf_set_curr_instr(BPF_LD | BPF_B | BPF_ABS, 0, 0,
 131                                    SKF_AD_OFF + $2); }
 132         ;
 133
 134 ldh
 135         : OP_LDH '[' 'x' '+' number ']' {
 136                 bpf_set_curr_instr(BPF_LD | BPF_H | BPF_IND, 0, 0, $5); }
 137         | OP_LDH '[' '%' 'x' '+' number ']' {
 138                 bpf_set_curr_instr(BPF_LD | BPF_H | BPF_IND, 0, 0, $6); }
 139         | OP_LDH '[' number ']' {
 140                 bpf_set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0, $3); }
 141         | OP_LDH extension {
 142                 bpf_set_curr_instr(BPF_LD | BPF_H | BPF_ABS, 0, 0,
 143                                    SKF_AD_OFF + $2); }
 144         ;
 145
 146 ldi
 147         : OP_LDI '#' number {
 148                 bpf_set_curr_instr(BPF_LD | BPF_IMM, 0, 0, $3); }
 149         | OP_LDI number {
 150                 bpf_set_curr_instr(BPF_LD | BPF_IMM, 0, 0, $2); }
 151         ;
 152
 153 ld
 154         : OP_LD '#' number {
 155                 bpf_set_curr_instr(BPF_LD | BPF_IMM, 0, 0, $3); }
 156         | OP_LD K_PKT_LEN {
 157                 bpf_set_curr_instr(BPF_LD | BPF_W | BPF_LEN, 0, 0, 0); }
 158         | OP_LD extension {
 159                 bpf_set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0,
 160                                    SKF_AD_OFF + $2); }
 161         | OP_LD 'M' '[' number ']' {
 162                 bpf_set_curr_instr(BPF_LD | BPF_MEM, 0, 0, $4); }
 163         | OP_LD '[' 'x' '+' number ']' {
 164                 bpf_set_curr_instr(BPF_LD | BPF_W | BPF_IND, 0, 0, $5); }
 165         | OP_LD '[' '%' 'x' '+' number ']' {
 166                 bpf_set_curr_instr(BPF_LD | BPF_W | BPF_IND, 0, 0, $6); }
 167         | OP_LD '[' number ']' {
 168                 bpf_set_curr_instr(BPF_LD | BPF_W | BPF_ABS, 0, 0, $3); }
 169         ;
 170
 171 ldxi
 172         : OP_LDXI '#' number {
 173                 bpf_set_curr_instr(BPF_LDX | BPF_IMM, 0, 0, $3); }
 174         | OP_LDXI number {
 175                 bpf_set_curr_instr(BPF_LDX | BPF_IMM, 0, 0, $2); }
 176         ;
 177
 178 ldx
 179         : OP_LDX '#' number {
 180                 bpf_set_curr_instr(BPF_LDX | BPF_IMM, 0, 0, $3); }
 181         | OP_LDX K_PKT_LEN {
 182                 bpf_set_curr_instr(BPF_LDX | BPF_W | BPF_LEN, 0, 0, 0); }
 183         | OP_LDX 'M' '[' number ']' {
 184                 bpf_set_curr_instr(BPF_LDX | BPF_MEM, 0, 0, $4); }
 185         | OP_LDXB number '*' '(' '[' number ']' '&' number ')' {
 186                 if ($2 != 4 || $9 != 0xf) {
 187                         fprintf(stderr, "ldxb offset not supported!\n");
 188                         exit(1);
 189                 } else {
 190                         bpf_set_curr_instr(BPF_LDX | BPF_MSH | BPF_B, 0, 0, $6); } }
 191         | OP_LDX number '*' '(' '[' number ']' '&' number ')' {
 192                 if ($2 != 4 || $9 != 0xf) {
 193                         fprintf(stderr, "ldxb offset not supported!\n");
 194                         exit(1);
 195                 } else {
 196                         bpf_set_curr_instr(BPF_LDX | BPF_MSH | BPF_B, 0, 0, $6); } }
 197         ;
 198
 199 st
 200         : OP_ST 'M' '[' number ']' {
 201                 bpf_set_curr_instr(BPF_ST, 0, 0, $4); }
 202         ;
 203
 204 stx
 205         : OP_STX 'M' '[' number ']' {
 206                 bpf_set_curr_instr(BPF_STX, 0, 0, $4); }
 207         ;
 208
 209 jmp
 210         : OP_JMP label {
 211                 bpf_set_jmp_label($2, JKL);
 212                 bpf_set_curr_instr(BPF_JMP | BPF_JA, 0, 0, 0); }
 213         ;
 214
 215 jeq
 216         : OP_JEQ '#' number ',' label ',' label {
 217                 bpf_set_jmp_label($5, JTL);
 218                 bpf_set_jmp_label($7, JFL);
 219                 bpf_set_curr_instr(BPF_JMP | BPF_JEQ | BPF_K, 0, 0, $3); }
 220         | OP_JEQ 'x' ',' label ',' label {
 221                 bpf_set_jmp_label($4, JTL);
 222                 bpf_set_jmp_label($6, JFL);
 223                 bpf_set_curr_instr(BPF_JMP | BPF_JEQ | BPF_X, 0, 0, 0); }
 224         | OP_JEQ '%' 'x' ',' label ',' label {
 225                 bpf_set_jmp_label($5, JTL);
 226                 bpf_set_jmp_label($7, JFL);
 227                 bpf_set_curr_instr(BPF_JMP | BPF_JEQ | BPF_X, 0, 0, 0); }
 228         | OP_JEQ '#' number ',' label {
 229                 bpf_set_jmp_label($5, JTL);
 230                 bpf_set_curr_instr(BPF_JMP | BPF_JEQ | BPF_K, 0, 0, $3); }
 231         | OP_JEQ 'x' ',' label {
 232                 bpf_set_jmp_label($4, JTL);
 233                 bpf_set_curr_instr(BPF_JMP | BPF_JEQ | BPF_X, 0, 0, 0); }
 234         | OP_JEQ '%' 'x' ',' label {
 235                 bpf_set_jmp_label($5, JTL);
 236                 bpf_set_curr_instr(BPF_JMP | BPF_JEQ | BPF_X, 0, 0, 0); }
 237         ;
 238
 239 jneq
 240         : OP_JNEQ '#' number ',' label {
 241                 bpf_set_jmp_label($5, JFL);
 242                 bpf_set_curr_instr(BPF_JMP | BPF_JEQ | BPF_K, 0, 0, $3); }
 243         | OP_JNEQ 'x' ',' label {
 244                 bpf_set_jmp_label($4, JFL);
 245                 bpf_set_curr_instr(BPF_JMP | BPF_JEQ | BPF_X, 0, 0, 0); }
 246         | OP_JNEQ '%' 'x' ',' label {
 247                 bpf_set_jmp_label($5, JFL);
 248                 bpf_set_curr_instr(BPF_JMP | BPF_JEQ | BPF_X, 0, 0, 0); }
 249         ;
 250
 251 jlt
 252         : OP_JLT '#' number ',' label {
 253                 bpf_set_jmp_label($5, JFL);
 254                 bpf_set_curr_instr(BPF_JMP | BPF_JGE | BPF_K, 0, 0, $3); }
 255         | OP_JLT 'x' ',' label {
 256                 bpf_set_jmp_label($4, JFL);
 257                 bpf_set_curr_instr(BPF_JMP | BPF_JGE | BPF_X, 0, 0, 0); }
 258         | OP_JLT '%' 'x' ',' label {
 259                 bpf_set_jmp_label($5, JFL);
 260                 bpf_set_curr_instr(BPF_JMP | BPF_JGE | BPF_X, 0, 0, 0); }
 261         ;
 262
 263 jle
 264         : OP_JLE '#' number ',' label {
 265                 bpf_set_jmp_label($5, JFL);
 266                 bpf_set_curr_instr(BPF_JMP | BPF_JGT | BPF_K, 0, 0, $3); }
 267         | OP_JLE 'x' ',' label {
 268                 bpf_set_jmp_label($4, JFL);
 269                 bpf_set_curr_instr(BPF_JMP | BPF_JGT | BPF_X, 0, 0, 0); }
 270         | OP_JLE '%' 'x' ',' label {
 271                 bpf_set_jmp_label($5, JFL);
 272                 bpf_set_curr_instr(BPF_JMP | BPF_JGT | BPF_X, 0, 0, 0); }
 273         ;
 274
 275 jgt
 276         : OP_JGT '#' number ',' label ',' label {
 277                 bpf_set_jmp_label($5, JTL);
 278                 bpf_set_jmp_label($7, JFL);
 279                 bpf_set_curr_instr(BPF_JMP | BPF_JGT | BPF_K, 0, 0, $3); }
 280         | OP_JGT 'x' ',' label ',' label {
 281                 bpf_set_jmp_label($4, JTL);
 282                 bpf_set_jmp_label($6, JFL);
 283                 bpf_set_curr_instr(BPF_JMP | BPF_JGT | BPF_X, 0, 0, 0); }
 284         | OP_JGT '%' 'x' ',' label ',' label {
 285                 bpf_set_jmp_label($5, JTL);
 286                 bpf_set_jmp_label($7, JFL);
 287                 bpf_set_curr_instr(BPF_JMP | BPF_JGT | BPF_X, 0, 0, 0); }
 288         | OP_JGT '#' number ',' label {
 289                 bpf_set_jmp_label($5, JTL);
 290                 bpf_set_curr_instr(BPF_JMP | BPF_JGT | BPF_K, 0, 0, $3); }
 291         | OP_JGT 'x' ',' label {
 292                 bpf_set_jmp_label($4, JTL);
 293                 bpf_set_curr_instr(BPF_JMP | BPF_JGT | BPF_X, 0, 0, 0); }
 294         | OP_JGT '%' 'x' ',' label {
 295                 bpf_set_jmp_label($5, JTL);
 296                 bpf_set_curr_instr(BPF_JMP | BPF_JGT | BPF_X, 0, 0, 0); }
 297         ;
 298
 299 jge
 300         : OP_JGE '#' number ',' label ',' label {
 301                 bpf_set_jmp_label($5, JTL);
 302                 bpf_set_jmp_label($7, JFL);
 303                 bpf_set_curr_instr(BPF_JMP | BPF_JGE | BPF_K, 0, 0, $3); }
 304         | OP_JGE 'x' ',' label ',' label {
 305                 bpf_set_jmp_label($4, JTL);
 306                 bpf_set_jmp_label($6, JFL);
 307                 bpf_set_curr_instr(BPF_JMP | BPF_JGE | BPF_X, 0, 0, 0); }
 308         | OP_JGE '%' 'x' ',' label ',' label {
 309                 bpf_set_jmp_label($5, JTL);
 310                 bpf_set_jmp_label($7, JFL);
 311                 bpf_set_curr_instr(BPF_JMP | BPF_JGE | BPF_X, 0, 0, 0); }
 312         | OP_JGE '#' number ',' label {
 313                 bpf_set_jmp_label($5, JTL);
 314                 bpf_set_curr_instr(BPF_JMP | BPF_JGE | BPF_K, 0, 0, $3); }
 315         | OP_JGE 'x' ',' label {
 316                 bpf_set_jmp_label($4, JTL);
 317                 bpf_set_curr_instr(BPF_JMP | BPF_JGE | BPF_X, 0, 0, 0); }
 318         | OP_JGE '%' 'x' ',' label {
 319                 bpf_set_jmp_label($5, JTL);
 320                 bpf_set_curr_instr(BPF_JMP | BPF_JGE | BPF_X, 0, 0, 0); }
 321         ;
 322
 323 jset
 324         : OP_JSET '#' number ',' label ',' label {
 325                 bpf_set_jmp_label($5, JTL);
 326                 bpf_set_jmp_label($7, JFL);
 327                 bpf_set_curr_instr(BPF_JMP | BPF_JSET | BPF_K, 0, 0, $3); }
 328         | OP_JSET 'x' ',' label ',' label {
 329                 bpf_set_jmp_label($4, JTL);
 330                 bpf_set_jmp_label($6, JFL);
 331                 bpf_set_curr_instr(BPF_JMP | BPF_JSET | BPF_X, 0, 0, 0); }
 332         | OP_JSET '%' 'x' ',' label ',' label {
 333                 bpf_set_jmp_label($5, JTL);
 334                 bpf_set_jmp_label($7, JFL);
 335                 bpf_set_curr_instr(BPF_JMP | BPF_JSET | BPF_X, 0, 0, 0); }
 336         | OP_JSET '#' number ',' label {
 337                 bpf_set_jmp_label($5, JTL);
 338                 bpf_set_curr_instr(BPF_JMP | BPF_JSET | BPF_K, 0, 0, $3); }
 339         | OP_JSET 'x' ',' label {
 340                 bpf_set_jmp_label($4, JTL);
 341                 bpf_set_curr_instr(BPF_JMP | BPF_JSET | BPF_X, 0, 0, 0); }
 342         | OP_JSET '%' 'x' ',' label {
 343                 bpf_set_jmp_label($5, JTL);
 344                 bpf_set_curr_instr(BPF_JMP | BPF_JSET | BPF_X, 0, 0, 0); }
 345         ;
 346
 347 add
 348         : OP_ADD '#' number {
 349                 bpf_set_curr_instr(BPF_ALU | BPF_ADD | BPF_K, 0, 0, $3); }
 350         | OP_ADD 'x' {
 351                 bpf_set_curr_instr(BPF_ALU | BPF_ADD | BPF_X, 0, 0, 0); }
 352         | OP_ADD '%' 'x' {
 353                 bpf_set_curr_instr(BPF_ALU | BPF_ADD | BPF_X, 0, 0, 0); }
 354         ;
 355
 356 sub
 357         : OP_SUB '#' number {
 358                 bpf_set_curr_instr(BPF_ALU | BPF_SUB | BPF_K, 0, 0, $3); }
 359         | OP_SUB 'x' {
 360                 bpf_set_curr_instr(BPF_ALU | BPF_SUB | BPF_X, 0, 0, 0); }
 361         | OP_SUB '%' 'x' {
 362                 bpf_set_curr_instr(BPF_ALU | BPF_SUB | BPF_X, 0, 0, 0); }
 363         ;
 364
 365 mul
 366         : OP_MUL '#' number {
 367                 bpf_set_curr_instr(BPF_ALU | BPF_MUL | BPF_K, 0, 0, $3); }
 368         | OP_MUL 'x' {
 369                 bpf_set_curr_instr(BPF_ALU | BPF_MUL | BPF_X, 0, 0, 0); }
 370         | OP_MUL '%' 'x' {
 371                 bpf_set_curr_instr(BPF_ALU | BPF_MUL | BPF_X, 0, 0, 0); }
 372         ;
 373
 374 div
 375         : OP_DIV '#' number {
 376                 bpf_set_curr_instr(BPF_ALU | BPF_DIV | BPF_K, 0, 0, $3); }
 377         | OP_DIV 'x' {
 378                 bpf_set_curr_instr(BPF_ALU | BPF_DIV | BPF_X, 0, 0, 0); }
 379         | OP_DIV '%' 'x' {
 380                 bpf_set_curr_instr(BPF_ALU | BPF_DIV | BPF_X, 0, 0, 0); }
 381         ;
 382
 383 mod
 384         : OP_MOD '#' number {
 385                 bpf_set_curr_instr(BPF_ALU | BPF_MOD | BPF_K, 0, 0, $3); }
 386         | OP_MOD 'x' {
 387                 bpf_set_curr_instr(BPF_ALU | BPF_MOD | BPF_X, 0, 0, 0); }
 388         | OP_MOD '%' 'x' {
 389                 bpf_set_curr_instr(BPF_ALU | BPF_MOD | BPF_X, 0, 0, 0); }
 390         ;
 391
 392 neg
 393         : OP_NEG {
 394                 bpf_set_curr_instr(BPF_ALU | BPF_NEG, 0, 0, 0); }
 395         ;
 396
 397 and
 398         : OP_AND '#' number {
 399                 bpf_set_curr_instr(BPF_ALU | BPF_AND | BPF_K, 0, 0, $3); }
 400         | OP_AND 'x' {
 401                 bpf_set_curr_instr(BPF_ALU | BPF_AND | BPF_X, 0, 0, 0); }
 402         | OP_AND '%' 'x' {
 403                 bpf_set_curr_instr(BPF_ALU | BPF_AND | BPF_X, 0, 0, 0); }
 404         ;
 405
 406 or
 407         : OP_OR '#' number {
 408                 bpf_set_curr_instr(BPF_ALU | BPF_OR | BPF_K, 0, 0, $3); }
 409         | OP_OR 'x' {
 410                 bpf_set_curr_instr(BPF_ALU | BPF_OR | BPF_X, 0, 0, 0); }
 411         | OP_OR '%' 'x' {
 412                 bpf_set_curr_instr(BPF_ALU | BPF_OR | BPF_X, 0, 0, 0); }
 413         ;
 414
 415 xor
 416         : OP_XOR '#' number {
 417                 bpf_set_curr_instr(BPF_ALU | BPF_XOR | BPF_K, 0, 0, $3); }
 418         | OP_XOR 'x' {
 419                 bpf_set_curr_instr(BPF_ALU | BPF_XOR | BPF_X, 0, 0, 0); }
 420         | OP_XOR '%' 'x' {
 421                 bpf_set_curr_instr(BPF_ALU | BPF_XOR | BPF_X, 0, 0, 0); }
 422         ;
 423
 424 lsh
 425         : OP_LSH '#' number {
 426                 bpf_set_curr_instr(BPF_ALU | BPF_LSH | BPF_K, 0, 0, $3); }
 427         | OP_LSH 'x' {
 428                 bpf_set_curr_instr(BPF_ALU | BPF_LSH | BPF_X, 0, 0, 0); }
 429         | OP_LSH '%' 'x' {
 430                 bpf_set_curr_instr(BPF_ALU | BPF_LSH | BPF_X, 0, 0, 0); }
 431         ;
 432
 433 rsh
 434         : OP_RSH '#' number {
 435                 bpf_set_curr_instr(BPF_ALU | BPF_RSH | BPF_K, 0, 0, $3); }
 436         | OP_RSH 'x' {
 437                 bpf_set_curr_instr(BPF_ALU | BPF_RSH | BPF_X, 0, 0, 0); }
 438         | OP_RSH '%' 'x' {
 439                 bpf_set_curr_instr(BPF_ALU | BPF_RSH | BPF_X, 0, 0, 0); }
 440         ;
 441
 442 ret
 443         : OP_RET 'a' {
 444                 bpf_set_curr_instr(BPF_RET | BPF_A, 0, 0, 0); }
 445         | OP_RET '%' 'a' {
 446                 bpf_set_curr_instr(BPF_RET | BPF_A, 0, 0, 0); }
 447         | OP_RET 'x' {
 448                 bpf_set_curr_instr(BPF_RET | BPF_X, 0, 0, 0); }
 449         | OP_RET '%' 'x' {
 450                 bpf_set_curr_instr(BPF_RET | BPF_X, 0, 0, 0); }
 451         | OP_RET '#' number {
 452                 bpf_set_curr_instr(BPF_RET | BPF_K, 0, 0, $3); }
 453         ;
 454
 455 tax
 456         : OP_TAX {
 457                 bpf_set_curr_instr(BPF_MISC | BPF_TAX, 0, 0, 0); }
 458         ;
 459
 460 txa
 461         : OP_TXA {
 462                 bpf_set_curr_instr(BPF_MISC | BPF_TXA, 0, 0, 0); }
 463         ;
 464
 465 %%
 466
 467 static int curr_instr = 0;
 468 static struct sock_filter out[BPF_MAXINSNS];
 469 static char **labels, **labels_jt, **labels_jf, **labels_k;
 470
 471 static void bpf_assert_max(void)
 472 {
 473         if (curr_instr >= BPF_MAXINSNS) {
 474                 fprintf(stderr, "only max %u insns allowed!\n", BPF_MAXINSNS);
 475                 exit(1);
 476         }
 477 }
 478
 479 static void bpf_set_curr_instr(uint16_t code, uint8_t jt, uint8_t jf,
 480                                uint32_t k)
 481 {
 482         bpf_assert_max();
 483         out[curr_instr].code = code;
 484         out[curr_instr].jt = jt;
 485         out[curr_instr].jf = jf;
 486         out[curr_instr].k = k;
 487         curr_instr++;
 488 }
 489
 490 static void bpf_set_curr_label(char *label)
 491 {
 492         bpf_assert_max();
 493         labels[curr_instr] = label;
 494 }
 495
 496 static void bpf_set_jmp_label(char *label, enum jmp_type type)
 497 {
 498         bpf_assert_max();
 499         switch (type) {
 500         case JTL:
 501                 labels_jt[curr_instr] = label;
 502                 break;
 503         case JFL:
 504                 labels_jf[curr_instr] = label;
 505                 break;
 506         case JKL:
 507                 labels_k[curr_instr] = label;
 508                 break;
 509         }
 510 }
 511
 512 static int bpf_find_insns_offset(const char *label)
 513 {
 514         int i, max = curr_instr, ret = -ENOENT;
 515
 516         for (i = 0; i < max; i++) {
 517                 if (labels[i] && !strcmp(label, labels[i])) {
 518                         ret = i;
 519                         break;
 520                 }
 521         }
 522
 523         if (ret == -ENOENT) {
 524                 fprintf(stderr, "no such label \'%s\'!\n", label);
 525                 exit(1);
 526         }
 527
 528         return ret;
 529 }
 530
 531 static void bpf_stage_1_insert_insns(void)
 532 {
 533         yyparse();
 534 }
 535
 536 static void bpf_reduce_k_jumps(void)
 537 {
 538         int i;
 539
 540         for (i = 0; i < curr_instr; i++) {
 541                 if (labels_k[i]) {
 542                         int off = bpf_find_insns_offset(labels_k[i]);
 543                         out[i].k = (uint32_t) (off - i - 1);
 544                 }
 545         }
 546 }
 547
 548 static uint8_t bpf_encode_jt_jf_offset(int off, int i)
 549 {
 550         int delta = off - i - 1;
 551
 552         if (delta < 0 || delta > 255) {
 553                 fprintf(stderr, "error: insn #%d jumps to insn #%d, "
 554                                 "which is out of range\n", i, off);
 555                 exit(1);
 556         }
 557         return (uint8_t) delta;
 558 }
 559
 560 static void bpf_reduce_jt_jumps(void)
 561 {
 562         int i;
 563
 564         for (i = 0; i < curr_instr; i++) {
 565                 if (labels_jt[i]) {
 566                         int off = bpf_find_insns_offset(labels_jt[i]);
 567                         out[i].jt = bpf_encode_jt_jf_offset(off, i);
 568                 }
 569         }
 570 }
 571
 572 static void bpf_reduce_jf_jumps(void)
 573 {
 574         int i;
 575
 576         for (i = 0; i < curr_instr; i++) {
 577                 if (labels_jf[i]) {
 578                         int off = bpf_find_insns_offset(labels_jf[i]);
 579                         out[i].jf = bpf_encode_jt_jf_offset(off, i);
 580                 }
 581         }
 582 }
 583
 584 static void bpf_stage_2_reduce_labels(void)
 585 {
 586         bpf_reduce_k_jumps();
 587         bpf_reduce_jt_jumps();
 588         bpf_reduce_jf_jumps();
 589 }
 590
 591 static void bpf_pretty_print_c(void)
 592 {
 593         int i;
 594
 595         for (i = 0; i < curr_instr; i++)
 596                 printf("{ %#04x, %2u, %2u, %#010x },\n", out[i].code,
 597                        out[i].jt, out[i].jf, out[i].k);
 598 }
 599
 600 static void bpf_pretty_print(void)
 601 {
 602         int i;
 603
 604         printf("%u,", curr_instr);
 605         for (i = 0; i < curr_instr; i++)
 606                 printf("%u %u %u %u,", out[i].code,
 607                        out[i].jt, out[i].jf, out[i].k);
 608         printf("\n");
 609 }
 610
 611 static void bpf_init(void)
 612 {
 613         memset(out, 0, sizeof(out));
 614
 615         labels = calloc(BPF_MAXINSNS, sizeof(*labels));
 616         assert(labels);
 617         labels_jt = calloc(BPF_MAXINSNS, sizeof(*labels_jt));
 618         assert(labels_jt);
 619         labels_jf = calloc(BPF_MAXINSNS, sizeof(*labels_jf));
 620         assert(labels_jf);
 621         labels_k = calloc(BPF_MAXINSNS, sizeof(*labels_k));
 622         assert(labels_k);
 623 }
 624
 625 static void bpf_destroy_labels(void)
 626 {
 627         int i;
 628
 629         for (i = 0; i < curr_instr; i++) {
 630                 free(labels_jf[i]);
 631                 free(labels_jt[i]);
 632                 free(labels_k[i]);
 633                 free(labels[i]);
 634         }
 635 }
 636
 637 static void bpf_destroy(void)
 638 {
 639         bpf_destroy_labels();
 640         free(labels_jt);
 641         free(labels_jf);
 642         free(labels_k);
 643         free(labels);
 644 }
 645
 646 void bpf_asm_compile(FILE *fp, bool cstyle)
 647 {
 648         yyin = fp;
 649
 650         bpf_init();
 651         bpf_stage_1_insert_insns();
 652         bpf_stage_2_reduce_labels();
 653         bpf_destroy();
 654
 655         if (cstyle)
 656                 bpf_pretty_print_c();
 657         else
 658                 bpf_pretty_print();
 659
 660         if (fp != stdin)
 661                 fclose(yyin);
 662 }
 663
 664 void yyerror(const char *str)
 665 {
 666         fprintf(stderr, "error: %s at line %d\n", str, yylineno);
 667         exit(1);
 668 }