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