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