libhed/expr.c

   1 /* $Id$ */
   2
   3 /*
   4  * hed - Hexadecimal editor
   5  * Copyright (C) 2004  Petr Baudis <pasky@ucw.cz>
   6  *
   7  * This program is free software; you can redistribute it and/or modify
   8  * it under the terms of version 2 of the GNU General Public License as
   9  * published by the Free Software Foundation.
  10  *
  11  * This program is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  * GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program; if not, write to the Free Software
  18  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  19  */
  20
  21 /*
  22  * 'You see: Mr. Drogo, he married poor Miss Primula Brandybuck. She was our
  23  * Mr. Bilbo's first cousin on the mother's side (her mother being the youngest
  24  * of the Old Took's daughters); and Mr. Drogo was his second cousin. So Mr.
  25  * Frodo is his first _and_ second cousin, once removed either way, as the
  26  * saying is, if you follow me.
  27  */
  28
  29 #include <config.h>
  30
  31 #include <ctype.h>
  32 #include <stdio.h>
  33 #include <stdlib.h>
  34 #include <string.h>
  35 #include <endian.h>
  36 #include <assert.h>
  37
  38 #include <util/numbers.h>
  39 #include <util/lists.h>
  40
  41 #include "expr.h"
  42
  43 /* This is really just trivial implementation. */
  44
  45 #define SIZE_AUTO       ((size_t)-1L)
  46
  47 struct atom {
  48         struct list_head list;
  49
  50         size_t len;             // SIZE_AUTO == auto (defaults to 1 at root)
  51
  52         enum atom_type {
  53                 ATOM_UN,
  54                 ATOM_BIN,
  55                 ATOM_BYTESTR,
  56                 ATOM_REGISTER,
  57                 ATOM_MARK,
  58                 ATOM_T_MAX
  59         } type;
  60 };
  61
  62 /* atom_evaluator returns a flag bitmask, see the HED_AEF_xxx constants */
  63 typedef long (*atom_evaluator)(struct hed_expr *expr, struct atom *atom,
  64                                unsigned char *scramble, size_t len);
  65 static long atom_un(struct hed_expr *expr, struct atom *atom,
  66                     unsigned char *scramble, size_t len);
  67 static long atom_bin(struct hed_expr *expr, struct atom *atom,
  68                      unsigned char *scramble, size_t len);
  69 static long atom_bytestr(struct hed_expr *expr, struct atom *atom,
  70                          unsigned char *scramble, size_t len);
  71 static long atom_register(struct hed_expr *expr, struct atom *atom,
  72                           unsigned char *scramble, size_t len);
  73 static long atom_mark(struct hed_expr *expr, struct atom *atom,
  74                       unsigned char *scramble, size_t len);
  75
  76 typedef void (*atom_free)(void *atom);
  77
  78 static void expr_cleanup(struct hed_expr *expr);
  79
  80 struct atom_un {
  81         struct atom a;
  82         enum atom_un_op {
  83                 AUO_NEG,
  84                 AUO_MINUS,
  85         } op;
  86         struct atom *atom;
  87 };
  88
  89 struct atom_bin {
  90         struct atom a;
  91         enum atom_bin_op {
  92                 ABO_OR,
  93                 ABO_AND,
  94                 ABO_XOR,
  95                 ABO_PLUS,
  96                 ABO_MINUS,
  97                 ABO_MUL,
  98                 ABO_DIV,
  99                 ABO_MOD,
 100                 ABO_SHL,
 101                 ABO_SHR,
 102                 /* pseudo-operations used while parsing */
 103                 ABO_LPAREN,
 104                 ABO_RPAREN,
 105         } op;
 106         struct atom *atom1;
 107         struct atom *atom2;
 108 };
 109
 110 struct atom_bytestr {
 111         struct atom a;
 112         size_t len;             /* Length of @bytes */
 113         unsigned char bytes[0]; /* [len] */
 114 };
 115
 116 struct atom_register {
 117         struct atom a;
 118         char reg;
 119         struct hed_expr offset;
 120 };
 121
 122 struct atom_mark {
 123         struct atom a;
 124         char mark;
 125 };
 126
 127 static unsigned
 128 unhex(char x)
 129 {
 130         static const char hx[] = "0123456789abcdef89ABCDEF";
 131         unsigned idx = strchr(hx, x) - hx;
 132         return (idx & 0x0f) | ((idx & 0x10) >> 1);
 133 }
 134
 135 static inline void
 136 skip_white(char **sexpr)
 137 {
 138         while (isspace(**sexpr))
 139                 (*sexpr)++;
 140 }
 141
 142 static struct atom *val_parse(char **sexpr);
 143 static struct hed_expr *compile_till(struct hed_expr *expr,
 144                                      char **sexpr, char till);
 145 static long atom_eval(struct hed_expr *expr, struct atom *atom,
 146                       unsigned char *scramble, size_t len);
 147 static void free_atom(struct atom *atom);
 148
 149 #if __BYTE_ORDER == __LITTLE_ENDIAN
 150 # define BYTESTR_LSB(s, len)    (s)
 151 # define BYTESTR_STEP           (+1)
 152 # define BYTESTR_MSB(s, len)    ((s) + (len) - 1)
 153 # define BYTESTR_LOPART(s, len, plen)   (s)
 154 # define BYTESTR_HIPART(s, len, plen)   ((s) + (len) - (plen))
 155 # define HED_AEF_NATIVEORDER    HED_AEF_FORCELE
 156 #elif __BYTE_ORDER == __BIG_ENDIAN
 157 # define BYTESTR_LSB(s, len)    ((s) + (len) - 1)
 158 # define BYTESTR_STEP           (-1)
 159 # define BYTESTR_MSB(s, len)    (s)
 160 # define BYTESTR_LOPART(s, len, plen)   ((s) + (len) - (plen))
 161 # define BYTESTR_HIPART(s, len, plen)   (s)
 162 # define HED_AEF_NATIVEORDER    HED_AEF_FORCEBE
 163 #else
 164 # error "Unsupported byte order"
 165 #endif
 166
 167 hed_off_t
 168 hed_bytestr2off(unsigned char *bytestr, size_t len, long flags)
 169 {
 170         unsigned char *p, *q;
 171         int step;
 172         register hed_off_t ret;
 173
 174         if ((flags & HED_AEF_ENDIANMASK) == HED_AEF_KEEPENDIAN ||
 175             (flags & HED_AEF_ENDIANMASK) == HED_AEF_NATIVEORDER) {
 176                 p = BYTESTR_MSB(bytestr, len);
 177                 q = BYTESTR_LSB(bytestr, len);
 178                 step = -BYTESTR_STEP;
 179         } else {
 180                 p = BYTESTR_LSB(bytestr, len);
 181                 q = BYTESTR_MSB(bytestr, len);
 182                 step = BYTESTR_STEP;
 183         }
 184
 185         if (flags & HED_AEF_SIGNED && (signed char)*p < 0)
 186                 flags |= HED_AEF_NEGATIVE;
 187         ret = flags & HED_AEF_NEGATIVE ? -1 : 0;
 188
 189         q += step;
 190         while (p != q) {
 191                 ret <<= 8;
 192                 ret += *p;
 193                 p += step;
 194         }
 195         return ret;
 196 }
 197
 198 /* The following function always uses the native byte order.
 199  * FIXME? Should the API be more analogous to hed_bytestr2off?
 200  */
 201 void
 202 hed_off2bytestr(unsigned char *bytestr, size_t len, hed_off_t num)
 203 {
 204         unsigned char *p = BYTESTR_LSB(bytestr, len);
 205         unsigned char *q = BYTESTR_MSB(bytestr, len) + BYTESTR_STEP;
 206         while (p != q) {
 207                 *p = num;
 208                 num >>= 8;
 209                 p += BYTESTR_STEP;
 210         }
 211 }
 212
 213 /* bytestr arithmetics */
 214 static void
 215 bytestr_not(unsigned char *s, size_t len)
 216 {
 217         while (len--) {
 218                 *s = ~*s;
 219                 ++s;
 220         }
 221 }
 222
 223 static void
 224 bytestr_and(unsigned char *s1, unsigned char *s2, size_t len)
 225 {
 226         while (len--)
 227                 *s1++ &= *s2++;
 228 }
 229
 230 static void
 231 bytestr_or(unsigned char *s1, unsigned char *s2, size_t len)
 232 {
 233         while (len--)
 234                 *s1++ |= *s2++;
 235 }
 236
 237 static void
 238 bytestr_xor(unsigned char *s1, unsigned char *s2, size_t len)
 239 {
 240         while (len--)
 241                 *s1++ ^= *s2++;
 242 }
 243
 244 /* Get the maximum length of the shift bytestr and check that the
 245  * actual value in @s fits into that size. If @s is larger than
 246  * the maximum shift for @len-sized numbers, return 0. This would
 247  * be otherwise an invalid value, because even a zero-sized bytestr
 248  * returns 1.
 249  */
 250 static size_t
 251 max_shiftlen(unsigned char *s, size_t len)
 252 {
 253         size_t maxshiftoff = ((bitsize(len) + 3) - 1) >> 3;
 254         unsigned char *p = BYTESTR_LSB(s, len) + maxshiftoff * BYTESTR_STEP;
 255         while (p != BYTESTR_MSB(s, len)) {
 256                 p += BYTESTR_STEP;
 257                 if (*p)
 258                         return 0;
 259         }
 260         return maxshiftoff + 1;
 261 }
 262
 263 /* Get the shift size in bytes. */
 264 static size_t
 265 shift_bytecount(unsigned char *s, size_t len, size_t shiftlen)
 266 {
 267         unsigned carry = 0;
 268         size_t ret = 0;
 269         s = BYTESTR_LSB(s, len) + shiftlen * BYTESTR_STEP;
 270         while (shiftlen--) {
 271                 s -= BYTESTR_STEP;
 272                 ret = (ret << 8) | carry | (*s >> 3);
 273                 carry = (*s & 7) << 5;
 274         }
 275         return ret;
 276 }
 277
 278 static void
 279 bytestr_shl(unsigned char *s1, unsigned char *s2, size_t len)
 280 {
 281         size_t shiftlen, byteoff, bitshift;
 282
 283         shiftlen = max_shiftlen(s2, len);
 284         byteoff = shiftlen ? shift_bytecount(s2, len, shiftlen) : len;
 285         if (byteoff < len) {
 286                 unsigned char *p;
 287
 288                 bitshift = *BYTESTR_LSB(s2, len) & 7;
 289                 for (p = BYTESTR_MSB(s1, len) - byteoff * BYTESTR_STEP;
 290                      p != BYTESTR_LSB(s1, len);
 291                      p -= BYTESTR_STEP)
 292                         p[byteoff * BYTESTR_STEP] =
 293                                 *p << bitshift |
 294                                 p[-BYTESTR_STEP] >> (8 - bitshift);
 295                 p[byteoff * BYTESTR_STEP] = *p << bitshift;
 296         } else
 297                 byteoff = len;
 298         memset(BYTESTR_LOPART(s1, len, byteoff), 0, byteoff);
 299 }
 300
 301 static void
 302 bytestr_shr(unsigned char *s1, unsigned char *s2, size_t len)
 303 {
 304         size_t shiftlen, byteoff, bitshift;
 305
 306         shiftlen = max_shiftlen(s2, len);
 307         byteoff = shiftlen ? shift_bytecount(s2, len, shiftlen) : len;
 308         if (byteoff < len) {
 309                 unsigned char *p;
 310
 311                 bitshift = *BYTESTR_LSB(s2, len) & 7;
 312                 for (p = BYTESTR_LSB(s1, len) + byteoff * BYTESTR_STEP;
 313                      p != BYTESTR_MSB(s1, len);
 314                      p += BYTESTR_STEP)
 315                         p[-byteoff * BYTESTR_STEP] =
 316                                 *p >> bitshift |
 317                                 p[BYTESTR_STEP] << (8 - bitshift);
 318                 p[-byteoff * BYTESTR_STEP] = *p >> bitshift;
 319         } else
 320                 byteoff = len;
 321         memset(BYTESTR_HIPART(s1, len, byteoff), 0, byteoff);
 322 }
 323
 324 static unsigned
 325 bytestr_inc(unsigned char *s, size_t len)
 326 {
 327         unsigned carry;
 328         s = BYTESTR_LSB(s, len);
 329         do {
 330                 carry = !++(*s);
 331                 s += BYTESTR_STEP;
 332         } while (carry && --len);
 333         return carry;
 334 }
 335
 336 static unsigned
 337 bytestr_add(unsigned char *s1, unsigned char *s2, size_t len)
 338 {
 339         unsigned carry = 0;
 340         s1 = BYTESTR_LSB(s1, len);
 341         s2 = BYTESTR_LSB(s2, len);
 342         while (len--) {
 343                 carry += *s1 + *s2;
 344                 *s1 = carry;
 345                 carry >>= 8;
 346                 s1 += BYTESTR_STEP;
 347                 s2 += BYTESTR_STEP;
 348         }
 349         return carry;
 350 }
 351
 352 static unsigned
 353 bytestr_sub(unsigned char *s1, unsigned char *s2, size_t len)
 354 {
 355         signed carry = 0;
 356         s1 = BYTESTR_LSB(s1, len);
 357         s2 = BYTESTR_LSB(s2, len);
 358         while (len--) {
 359                 carry += *s1 - *s2;
 360                 *s1 = carry;
 361                 carry >>= 8;
 362                 s1 += BYTESTR_STEP;
 363                 s2 += BYTESTR_STEP;
 364         }
 365         return carry;
 366 }
 367
 368 /* multiply @src by @mul and add it to @dst */
 369 static unsigned
 370 muladd(unsigned char *dst, unsigned char *src, size_t len, unsigned char mul)
 371 {
 372         unsigned carry = 0;
 373         unsigned char *p = BYTESTR_LSB(src, len);
 374         unsigned char *q = BYTESTR_LSB(dst, len);
 375         while (p != BYTESTR_MSB(src, len) + BYTESTR_STEP) {
 376                 carry += *p * mul + *q;
 377                 *q = carry;
 378                 carry >>= 8;
 379                 p += BYTESTR_STEP;
 380                 q += BYTESTR_STEP;
 381         }
 382         return carry;
 383 }
 384
 385 static void
 386 bytestr_mul(unsigned char *s1, unsigned char *s2, size_t len)
 387 {
 388         unsigned char ret[len];
 389         size_t mlen;
 390
 391         memset(ret, 0, len);
 392         for (mlen = len; mlen; --mlen)
 393                 muladd(BYTESTR_HIPART(ret, len, mlen),
 394                        BYTESTR_LOPART(s1, len, mlen), mlen,
 395                        BYTESTR_MSB(s2, len)[(1-mlen) * BYTESTR_STEP]);
 396         memcpy(s1, ret, len);
 397 }
 398
 399 static unsigned
 400 shl_one(unsigned char *s, size_t len, unsigned carry)
 401 {
 402         unsigned char *p = BYTESTR_LSB(s, len);
 403         while (p != BYTESTR_MSB(s, len) + BYTESTR_STEP) {
 404                 carry |= *p << 1;
 405                 *p = carry;
 406                 carry >>= 8;
 407                 p += BYTESTR_STEP;
 408         }
 409         return carry;
 410 }
 411
 412 /* Simple non-restoring algorithm for now.
 413  * Feel free to improve.
 414  */
 415 static void
 416 bytestr_div(unsigned char *s1, unsigned char *s2, size_t len,
 417             unsigned char *mod)
 418 {
 419         unsigned char *p, mask;
 420
 421         memset(mod, 0, len);
 422         p = BYTESTR_MSB(s1, len);
 423         mask = 0x80;
 424         while (p != BYTESTR_LSB(s1, len) - BYTESTR_STEP) {
 425                 if (shl_one(mod, len, !!(*p & mask)))
 426                         bytestr_add(mod, s2, len);
 427                 else
 428                         bytestr_sub(mod, s2, len);
 429
 430                 if (*BYTESTR_MSB(mod, len) & 0x80)
 431                         *p &= ~mask;
 432                 else
 433                         *p |= mask;
 434
 435                 if (! (mask >>= 1) ) {
 436                         p -= BYTESTR_STEP;
 437                         mask = 0x80;
 438                 }
 439         }
 440         if (*BYTESTR_MSB(mod, len) & 0x80)
 441                 bytestr_add(mod, s2, len);
 442 }
 443
 444 /* Remove any MSB zeroes from @s and update *@plen. */
 445 static unsigned char*
 446 bytestr_shrink(unsigned char *s, size_t *plen)
 447 {
 448         size_t origlen = *plen;
 449         unsigned char *p = BYTESTR_MSB(s, origlen);
 450
 451         while (*plen > 1 && !*p) {
 452                 --(*plen);
 453                 p -= BYTESTR_STEP;
 454         }
 455         return memmove(s, BYTESTR_LOPART(s, origlen, *plen), *plen);
 456 }
 457
 458 static long
 459 bytestr_unop(unsigned char *s, size_t len, long flags, enum atom_un_op op)
 460 {
 461         switch (op) {
 462                 case AUO_NEG:
 463                 case AUO_MINUS:
 464                         bytestr_not(s, len);
 465                         if (op == AUO_MINUS) {
 466                                 if (!bytestr_inc(s, len))
 467                                         flags ^= HED_AEF_NEGATIVE;
 468                         }
 469                         break;
 470                 default:
 471                         assert(0);
 472                         break;
 473         }
 474         return flags;
 475 }
 476
 477 static long
 478 bytestr_binop(unsigned char *s1, unsigned char *s2, size_t len,
 479               long flags1, long flags2, enum atom_bin_op op)
 480 {
 481         unsigned char *smod;
 482         unsigned carry;
 483         int sign  = !!(flags1 & HED_AEF_NEGATIVE);
 484         int sign2 = !!(flags2 & HED_AEF_NEGATIVE);
 485         long ret = (flags1 & ~HED_AEF_NEGATIVE) | (flags2 & HED_AEF_DYNAMIC);
 486
 487         switch (op) {
 488                 case ABO_OR:
 489                         sign |= sign2;
 490                         bytestr_or(s1, s2, len);
 491                         break;
 492                 case ABO_AND:
 493                         sign &= sign2;
 494                         bytestr_and(s1, s2, len);
 495                         break;
 496                 case ABO_XOR:
 497                         sign ^= sign2;
 498                         bytestr_xor(s1, s2, len);
 499                         break;
 500                 case ABO_PLUS:
 501                         carry = bytestr_add(s1, s2, len);
 502                         sign ^= (sign ^ sign2) & (sign ^ !carry);
 503                         break;
 504                 case ABO_MINUS:
 505                         carry = bytestr_sub(s1, s2, len);
 506                         sign ^= ((sign ^ sign2) | (sign ^ !carry)) ^ 1;
 507                         break;
 508                 case ABO_MUL:
 509                         sign ^= sign2;
 510                         bytestr_mul(s1, s2, len);
 511                         break;
 512                 case ABO_DIV:
 513                 case ABO_MOD:
 514                         sign ^= sign2;
 515                         if (! (smod = malloc(len)) ) {
 516                                 flags1 = HED_AEF_ERROR;
 517                                 break;
 518                         }
 519                         bytestr_div(s1, s2, len, smod);
 520                         if (op == ABO_MOD)
 521                                 memcpy(s1, smod, len);
 522                         free(smod);
 523                         break;
 524                 case ABO_SHL:
 525                         bytestr_shl(s1, s2, len);
 526                         break;
 527                 case ABO_SHR:
 528                         bytestr_shr(s1, s2, len);
 529                         break;
 530                 default:
 531                         assert(0);
 532                         break;
 533         }
 534         ret |= HED_AEF_NEGATIVE & -sign;
 535         return ret;
 536 }
 537
 538 static void *
 539 alloc_atom(enum atom_type type, size_t len)
 540 {
 541         static const size_t sizes[] = {
 542                 sizeof(struct atom_un),
 543                 sizeof(struct atom_bin),
 544                 sizeof(struct atom_bytestr),
 545                 sizeof(struct atom_register),
 546                 sizeof(struct atom_mark)
 547         };
 548         size_t asize = sizes[type];
 549         struct atom *a;
 550
 551         if (type == ATOM_BYTESTR)
 552                 asize += len;
 553
 554         a = calloc(1, asize);
 555         if (a) {
 556                 a->len = len;
 557                 a->type = type;
 558         }
 559         return a;
 560 }
 561
 562 static struct atom *
 563 parse_un(char **sexpr, enum atom_un_op op)
 564 {
 565         struct atom_un *a;
 566         struct atom *sa;
 567
 568         skip_white(sexpr);
 569         sa = val_parse(sexpr);
 570         if (!sa)
 571                 return NULL;
 572
 573         a = alloc_atom(ATOM_UN, sa->len);
 574         if (!a) {
 575                 free_atom(sa);
 576                 return NULL;
 577         }
 578         a->op = op;
 579         a->atom = sa;
 580         return &a->a;
 581 }
 582
 583 static struct atom *
 584 parse_register(char **sexpr)
 585 {
 586         struct atom_register *a;
 587         char reg = *(*sexpr)++;
 588
 589         a = alloc_atom(ATOM_REGISTER, SIZE_AUTO);
 590         if (!a)
 591                 return NULL;
 592         a->reg = reg;
 593
 594         INIT_LIST_HEAD(&a->offset.atoms);
 595         if (**sexpr == '[') {
 596                 (*sexpr)++;
 597                 if (!compile_till(&a->offset, sexpr, ']')) {
 598                         free(a);
 599                         return NULL;
 600                 }
 601                 (*sexpr)++;
 602         }
 603
 604         return &a->a;
 605 }
 606
 607 static struct atom *
 608 parse_mark(char **sexpr)
 609 {
 610         struct atom_mark *a;
 611         char mark = *(*sexpr)++;
 612
 613         a = alloc_atom(ATOM_MARK, sizeof(hed_off_t));
 614         if (!a)
 615                 return NULL;
 616         a->mark = mark;
 617         return &a->a;
 618 }
 619
 620 static struct atom *
 621 parse_string(char **sexpr)
 622 {
 623         struct atom_bytestr *a;
 624         char *base;
 625         size_t i = 0;
 626
 627         base = *sexpr;
 628         while (**sexpr && **sexpr != '\'') {
 629                 if (**sexpr == '\\') {
 630                         (*sexpr)++;
 631                         if (!**sexpr)
 632                                 return NULL;
 633                 }
 634                 i++;
 635                 (*sexpr)++;
 636         }
 637
 638         a = alloc_atom(ATOM_BYTESTR, i);
 639         if (!a)
 640                 return NULL;
 641         a->len = a->a.len;
 642         for (i = 0; base < *sexpr; i++, base++) {
 643                 if (*base == '\\')
 644                         base++;
 645                 a->bytes[i] = *base;
 646         }
 647         (*sexpr)++;
 648         return &a->a;
 649 }
 650
 651 static struct atom *
 652 parse_hexstr(char **sexpr)
 653 {
 654         struct atom_bytestr *a;
 655         char *base;
 656         size_t i;
 657
 658         base = *sexpr;
 659         while (isxdigit(**sexpr))
 660                 (*sexpr)++;
 661
 662         a = alloc_atom(ATOM_BYTESTR, (*sexpr - base + 1)/2);
 663         if (!a)
 664                 return NULL;
 665         a->len = a->a.len;
 666
 667         i = 0;
 668         if ((*sexpr - base) % 2)
 669                 a->bytes[i++] = unhex(*base++);
 670         while (base < *sexpr) {
 671                 a->bytes[i++] = (unhex(base[0]) << 4) + unhex(base[1]);
 672                 base += 2;
 673         }
 674         return &a->a;
 675 }
 676
 677 static struct atom_bytestr *
 678 parse_number_hex(char **sexpr)
 679 {
 680         char *p, *q;
 681         size_t len;
 682         unsigned char *s;
 683         unsigned shift;
 684         struct atom_bytestr *ret;
 685
 686         for (q = p = *sexpr; isxdigit(*q); ++q);
 687         *sexpr = q;
 688         len = ((size_t)(q - p) + 1) >> 1;
 689         assert(len);
 690         if (! (ret = alloc_atom(ATOM_BYTESTR, len)) )
 691                 return ret;
 692
 693         s = BYTESTR_LSB(ret->bytes, *plen);
 694         shift = 0;
 695         while (q-- > p) {
 696                 *s |= unhex(*q) << shift;
 697                 shift += 4;
 698                 if (shift >= 8) {
 699                         shift -= 8;
 700                         s += BYTESTR_STEP;
 701                 }
 702         }
 703
 704         return ret;
 705 }
 706
 707 static struct atom_bytestr *
 708 parse_number_oct(char **sexpr)
 709 {
 710         char *p, *q;
 711         size_t len;
 712         unsigned char *s;
 713         unsigned shift, acc;
 714         struct atom_bytestr *ret;
 715
 716         for (q = p = *sexpr; *q >= '0' && *q <= '7'; ++q);
 717         *sexpr = q;
 718         len = ((size_t)(q - p) * 3 + 7)/8 ?: 1;
 719         if (! (ret = alloc_atom(ATOM_BYTESTR, len)) )
 720                 return ret;
 721
 722         s = BYTESTR_LSB(ret->bytes, len);
 723         shift = acc = 0;
 724         while (q-- > p) {
 725                 acc |= (*q - '0') << shift;
 726                 shift += 3;
 727                 if (shift >= 8) {
 728                         shift -= 8;
 729                         *s = acc;
 730                         acc >>= 8;
 731                         s += BYTESTR_STEP;
 732                 }
 733         }
 734         if (acc)
 735                 *s = acc;
 736
 737         bytestr_shrink(ret->bytes, &ret->a.len);
 738         return ret;
 739 }
 740
 741 /* Number of bits per decimal digit scaled by 256 (8 bit shift) */
 742 #define SBITSPERDECDIG  851
 743
 744 static struct atom_bytestr *
 745 parse_number_dec(char **sexpr)
 746 {
 747         char *p, *q;
 748         size_t len;
 749         unsigned char *s;
 750         struct atom_bytestr *ret;
 751
 752         /* We must make sure that the resulting bytestr will fit into
 753          * the allocated space, so we must always round to the nearest
 754          * higher integer. Because of this, the approximation of log2(10)
 755          * and the dependency on the actual number, the allocated space
 756          * may be larger than necessary.
 757          */
 758         for (p = q = *sexpr; isdigit(*q); ++q);
 759         *sexpr = q;
 760         len = (((size_t)(q - p) * SBITSPERDECDIG + 255)/256 + 7)/8 ?: 1;
 761         if (! (ret = alloc_atom(ATOM_BYTESTR, len)) )
 762                 return ret;
 763
 764         while (p < q) {
 765                 unsigned carry = *p++ - '0';
 766                 for (s = BYTESTR_LSB(ret->bytes, len);
 767                      s != BYTESTR_MSB(ret->bytes, len) + BYTESTR_STEP;
 768                      s += BYTESTR_STEP) {
 769                         carry += *s * 10;
 770                         *s = carry;
 771                         carry >>= 8;
 772                 }
 773         }
 774
 775         bytestr_shrink(ret->bytes, &ret->a.len);
 776         return ret;
 777 }
 778
 779 static struct atom *
 780 parse_number(char **sexpr)
 781 {
 782         struct atom_bytestr *a;
 783
 784         if (**sexpr == '0') {
 785                 ++(*sexpr);
 786                 if ((**sexpr == 'x' || **sexpr == 'X') &&
 787                     isxdigit((*sexpr)[1])) {
 788                         ++(*sexpr);
 789                         a = parse_number_hex(sexpr);
 790                 } else
 791                         a = parse_number_oct(sexpr);
 792         } else
 793                 a = parse_number_dec(sexpr);
 794
 795         if (!a)
 796                 return NULL;
 797         a->len = a->a.len;
 798         return &a->a;
 799 }
 800
 801 static struct atom *
 802 val_parse(char **sexpr)
 803 {
 804         static const char uopc[] = "~-"; // in atom_un_op order
 805         char *uop;
 806         struct atom *ret = NULL;
 807
 808         if ( (uop = strchr(uopc, **sexpr)) ) {
 809                 (*sexpr)++;
 810                 ret = parse_un(sexpr, uop - uopc);
 811         } else if (**sexpr == '"') {
 812                 (*sexpr)++;
 813                 ret = parse_register(sexpr);
 814         } else if (**sexpr == '@') {
 815                 (*sexpr)++;
 816                 ret = parse_mark(sexpr);
 817         } else if (**sexpr == '\'') {
 818                 (*sexpr)++;
 819                 ret = parse_string(sexpr);
 820         } else if (**sexpr == 'x') {
 821                 (*sexpr)++;
 822                 ret = parse_hexstr(sexpr);
 823         } else if (isdigit(**sexpr)) {
 824                 ret = parse_number(sexpr);
 825         }
 826
 827         if (!ret)
 828                 return NULL;
 829
 830         /* Modifiers */
 831         if (**sexpr == '.')
 832                 (*sexpr)++;
 833         switch (**sexpr) {
 834         case 'B':
 835         case 'b':
 836                 ret->len = 1;
 837                 (*sexpr)++;
 838                 break;
 839         case 'W':
 840         case 'w':
 841                 ret->len = 2;
 842                 (*sexpr)++;
 843                 break;
 844         case 'D':
 845         case 'd':
 846         case 'L':
 847         case 'l':
 848                 ret->len = 4;
 849                 (*sexpr)++;
 850                 break;
 851         case 'Q':
 852         case 'q':
 853                 ret->len = 8;
 854                 (*sexpr)++;
 855                 break;
 856         case '{':
 857                 ret->len = strtoull(*sexpr, sexpr, 0);
 858                 if (**sexpr != '}') {
 859                         free_atom(ret);
 860                         return NULL;
 861                 }
 862                 (*sexpr)++;
 863                 break;
 864         }
 865         return ret;
 866 }
 867
 868 /* return the precedence of the operator @op */
 869 static inline int
 870 precedence(enum atom_bin_op op)
 871 {
 872         static const int op2prec[] = {
 873                 [ABO_LPAREN] = -1,
 874                 [ABO_RPAREN] = 0,
 875                 [ABO_OR] = 100,
 876                 [ABO_XOR] = 110,
 877                 [ABO_AND] = 120,
 878                 [ABO_SHL] = 130,
 879                 [ABO_SHR] = 130,
 880                 [ABO_PLUS] = 140,
 881                 [ABO_MINUS] = 140,
 882                 [ABO_MUL] = 150,
 883                 [ABO_DIV] = 150,
 884                 [ABO_MOD] = 150,
 885         };
 886         assert(op >= 0 && op < sizeof(op2prec)/sizeof(int));
 887         return op2prec[op];
 888 }
 889
 890 /* Reduce the stack up to an operator with a higher precedence than @till
 891  * Returns the first non-reduced atom, or NULL if there are no more atoms
 892  * on @stack.
 893  */
 894 static struct atom_bin *
 895 reduce_stack(struct hed_expr *expr, struct list_head *stack, int minprec)
 896 {
 897         while (!list_empty(stack)) {
 898                 struct atom_bin *bin;
 899
 900                 bin = list_entry(stack->next, struct atom_bin, a.list);
 901                 if (precedence(bin->op) < minprec)
 902                         return bin;
 903
 904                 if (expr->atoms.prev == expr->atoms.next)
 905                         return bin; /* zero or one element */
 906
 907                 bin->atom2 = list_entry(expr->atoms.prev, struct atom, list);
 908                 list_del(&bin->atom2->list);
 909                 bin->atom1 = list_entry(expr->atoms.prev, struct atom, list);
 910                 list_del(&bin->atom1->list);
 911
 912                 list_move_tail(&bin->a.list, &expr->atoms);
 913
 914                 /* Note that BOTH may be SIZE_AUTO, but that's ok */
 915                 if (bin->atom1->len == SIZE_AUTO)
 916                         bin->a.len = bin->atom1->len = bin->atom2->len;
 917                 else if (bin->atom2->len == SIZE_AUTO)
 918                         bin->a.len = bin->atom2->len = bin->atom1->len;
 919                 else
 920                         bin->a.len = bin->atom1->len >= bin->atom2->len
 921                                 ? bin->atom1->len : bin->atom2->len;
 922         }
 923
 924         return NULL;
 925 }
 926
 927 static struct hed_expr *
 928 compile_till(struct hed_expr *expr, char **sexpr, char till)
 929 {
 930         static const char bopc[] = "|&^+-*/%<>"; // in atom_bin_op order
 931         char *bop;
 932
 933         struct atom *a;
 934         struct atom_bin *bin;
 935         struct list_head binstack;
 936
 937         INIT_LIST_HEAD(&binstack);
 938
 939         while (**sexpr != till) {
 940                 skip_white(sexpr);
 941
 942                 if (**sexpr == '(') {
 943                         bin = alloc_atom(ATOM_BIN, 0);
 944                         if (!bin)
 945                                 goto err;
 946                         bin->op = ABO_LPAREN;
 947                         list_add(&bin->a.list, &binstack);
 948                         (*sexpr)++;
 949                         continue;
 950                 }
 951
 952                 a = val_parse(sexpr);
 953                 if (!a)
 954                         goto err;
 955                 list_add_tail(&a->list, &expr->atoms);
 956
 957                 skip_white(sexpr);
 958                 if (**sexpr == ')') {
 959                         bin = reduce_stack(expr, &binstack,
 960                                            precedence(ABO_RPAREN));
 961                         if (!bin)
 962                                 goto err; /* mismatched parenthesis */
 963                         list_del(&bin->a.list);
 964                         free_atom(&bin->a);
 965                         (*sexpr)++;
 966                 }
 967
 968                 bop = strchr(bopc, **sexpr);
 969                 if (!bop || !*bop)
 970                         continue;
 971
 972                 if (*bop == '<' || *bop == '>') {
 973                         (*sexpr)++;
 974                         if (**sexpr != *bop)
 975                                 goto err;
 976                 }
 977
 978                 bin = alloc_atom(ATOM_BIN, 0);
 979                 if (!bin)
 980                         goto err;
 981                 bin->op = bop - bopc;
 982                 reduce_stack(expr, &binstack, precedence(bin->op));
 983                 list_add(&bin->a.list, &binstack);
 984                 (*sexpr)++;
 985         }
 986
 987         if (reduce_stack(expr, &binstack, precedence(ABO_RPAREN)))
 988                 goto err;
 989
 990         list_for_each_entry(a, &expr->atoms, list) {
 991                 if (a->len == SIZE_AUTO)
 992                         a->len = 1;
 993                 expr->len += a->len;
 994         }
 995
 996         if (expr->len) {
 997                 expr->buf = realloc(expr->buf, expr->len);
 998                 if (!expr->buf)
 999                         goto err;
1000         }
1001
1002         return expr;
1003
1004 err:
1005         list_splice(&binstack, &expr->atoms);
1006         expr_cleanup(expr);
1007         return NULL;
1008 }
1009
1010 struct hed_expr *
1011 hed_expr_new(char *sexpr,
1012              hed_expr_reg_cb reg_cb, hed_expr_mark_cb mark_cb, void *cb_data)
1013 {
1014         struct hed_expr *expr = calloc(1, sizeof(struct hed_expr));
1015
1016         if (!expr)
1017                 return NULL;
1018
1019         expr->reg_cb = reg_cb;
1020         expr->mark_cb = mark_cb;
1021         expr->cb_data = cb_data;
1022         INIT_LIST_HEAD(&expr->atoms);
1023
1024         if (compile_till(expr, &sexpr, '\0'))
1025                 return expr;
1026
1027         free(expr);
1028         return NULL;
1029 }
1030
1031 static long
1032 atom_un(struct hed_expr *expr, struct atom *atom,
1033         unsigned char *scramble, size_t len)
1034 {
1035         struct atom_un *data = (struct atom_un *) atom;
1036         long flags;
1037         assert(data);
1038         assert(data->atom);
1039         flags = atom_eval(expr, data->atom, scramble, len);
1040         if (flags & HED_AEF_ERROR)
1041                 return flags;
1042         return bytestr_unop(scramble, len, flags, data->op);
1043 }
1044
1045 static long
1046 do_atom_bin(struct hed_expr *expr, struct atom_bin *data,
1047             unsigned char *scramble, size_t len, unsigned char *tmp)
1048 {
1049         long flags1, flags2;
1050         assert(data);
1051         assert(data->atom1 && data->atom2);
1052
1053         flags1 = atom_eval(expr, data->atom1, scramble, len);
1054         if (flags1 & HED_AEF_ERROR)
1055                 return flags1;
1056
1057         flags2 = atom_eval(expr, data->atom2, tmp, len);
1058         if (flags2 & HED_AEF_ERROR)
1059                 return flags2;
1060
1061         return bytestr_binop(scramble, tmp, len,
1062                              flags1, flags2, data->op);
1063 }
1064
1065 static long
1066 atom_bin(struct hed_expr *expr, struct atom *atom,
1067          unsigned char *scramble, size_t len)
1068 {
1069         struct atom_bin *data = (struct atom_bin *) atom;
1070         unsigned char *tmp;
1071         long ret;
1072
1073         tmp = malloc(len);
1074         if (!tmp)
1075                 return HED_AEF_ERROR;
1076
1077         ret = do_atom_bin(expr, data, scramble, len, tmp);
1078
1079         free(tmp);
1080         return ret;
1081 }
1082
1083 static long
1084 atom_bytestr(struct hed_expr *expr, struct atom *atom,
1085              unsigned char *scramble, size_t len)
1086 {
1087         struct atom_bytestr *data = (struct atom_bytestr *) atom;
1088         assert(data);
1089         if (len > data->len) {
1090                 memcpy(BYTESTR_LOPART(scramble, len, data->len),
1091                        data->bytes, data->len);
1092                 memset(BYTESTR_HIPART(scramble, len, len - data->len),
1093                        0, len - data->len);
1094         } else
1095                 memcpy(scramble,
1096                        BYTESTR_LOPART(data->bytes, data->len, len), len);
1097         return 0;
1098 }
1099
1100 static long
1101 atom_mark(struct hed_expr *expr, struct atom *atom,
1102           unsigned char *scramble, size_t len)
1103 {
1104         struct atom_mark *data = (struct atom_mark *) atom;
1105         assert(data);
1106         if (!expr->mark_cb) {
1107                 memset(scramble, 0, len);
1108                 return 0;
1109         }
1110
1111         return expr->mark_cb(expr->cb_data, data->mark, scramble, len);
1112 }
1113
1114 static long
1115 atom_register(struct hed_expr *expr, struct atom *atom,
1116               unsigned char *scramble, size_t len)
1117 {
1118         struct atom_register *data = (struct atom_register *) atom;
1119         hed_off_t ofs;
1120         assert(data);
1121         if (!expr->reg_cb) {
1122                 memset(scramble, 0, len);
1123                 return 0;
1124         }
1125
1126         data->offset.reg_cb = expr->reg_cb;
1127         data->offset.mark_cb = expr->mark_cb;
1128         data->offset.cb_data = expr->cb_data;
1129         if (hed_expr_eval(&data->offset) & HED_AEF_ERROR)
1130                 return HED_AEF_ERROR;
1131
1132         ofs = hed_expr2off(&data->offset);
1133
1134         if (data->reg == '.')
1135                 ofs += expr->cb_pos;
1136         return expr->reg_cb(expr->cb_data, data->reg, ofs,
1137                             scramble, len);
1138 }
1139
1140 static long
1141 atom_eval(struct hed_expr *expr, struct atom *atom,
1142           unsigned char *scramble, size_t len)
1143 {
1144         if (!len)
1145                 return 0;
1146
1147         switch (atom->type) {
1148         case ATOM_UN: return atom_un(expr, atom, scramble, len);
1149         case ATOM_BIN: return atom_bin(expr, atom, scramble, len);
1150         case ATOM_BYTESTR: return atom_bytestr(expr, atom, scramble, len);
1151         case ATOM_REGISTER: return atom_register(expr, atom, scramble, len);
1152         case ATOM_MARK: return atom_mark(expr, atom, scramble, len);
1153         default: assert(0); return HED_AEF_ERROR;
1154         }
1155 }
1156
1157 long
1158 hed_expr_eval(struct hed_expr *expr)
1159 {
1160         struct atom *a;
1161
1162         expr->cb_pos = 0;
1163         expr->flags = 0;
1164
1165         assert(expr && expr->len >= 0);
1166         list_for_each_entry (a, &expr->atoms, list) {
1167                 long flags;
1168
1169                 flags = atom_eval(expr, a,
1170                                   expr->buf + expr->cb_pos, a->len);
1171                 expr->flags |= (flags & (HED_AEF_DYNAMIC | HED_AEF_ERROR));
1172                 if (!expr->cb_pos)
1173                         expr->flags |= (flags & HED_AEF_NEGATIVE);
1174                 else
1175                         expr->flags &= ~HED_AEF_NEGATIVE;
1176                 expr->cb_pos += a->len;
1177         }
1178         assert(expr->cb_pos == expr->len);
1179         return expr->flags;
1180 }
1181
1182 static void
1183 cleanup_un(struct atom_un *un)
1184 {
1185         free_atom(un->atom);
1186 }
1187
1188 static void
1189 cleanup_bin(struct atom_bin *bin)
1190 {
1191         if (bin->atom1)
1192                 free_atom(bin->atom1);
1193         if (bin->atom2)
1194                 free_atom(bin->atom2);
1195 }
1196
1197 static void
1198 cleanup_register(struct atom_register *reg)
1199 {
1200         expr_cleanup(&reg->offset);
1201 }
1202
1203 static void
1204 free_atom(struct atom *atom)
1205 {
1206         if (atom->type == ATOM_UN)
1207                 cleanup_un((struct atom_un *) atom);
1208         else if (atom->type == ATOM_BIN)
1209                 cleanup_bin((struct atom_bin *) atom);
1210         else if (atom->type == ATOM_REGISTER)
1211                 cleanup_register((struct atom_register*) atom);
1212
1213         free(atom);
1214 }
1215
1216 static void
1217 expr_cleanup(struct hed_expr *expr)
1218 {
1219         struct atom *a, *next;
1220
1221         list_for_each_entry_safe (a, next, &expr->atoms, list)
1222                 free_atom(a);
1223         if (expr->buf)
1224                 free(expr->buf);
1225 }
1226
1227 void
1228 hed_expr_free(struct hed_expr *expr)
1229 {
1230         expr_cleanup(expr);
1231         free(expr);
1232 }