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