git.sur5r.net Git - cc65/blob - src/ca65/expr.c

   1 /*****************************************************************************/
   2 /*                                                                           */
   3 /*                                  expr.c                                   */
   4 /*                                                                           */
   5 /*             Expression evaluation for the ca65 macroassembler             */
   6 /*                                                                           */
   7 /*                                                                           */
   8 /*                                                                           */
   9 /* (C) 1998-2003 Ullrich von Bassewitz                                       */
  10 /*               Römerstrasse 52                                             */
  11 /*               D-70794 Filderstadt                                         */
  12 /* EMail:        uz@cc65.org                                                 */
  13 /*                                                                           */
  14 /*                                                                           */
  15 /* This software is provided 'as-is', without any expressed or implied       */
  16 /* warranty.  In no event will the authors be held liable for any damages    */
  17 /* arising from the use of this software.                                    */
  18 /*                                                                           */
  19 /* Permission is granted to anyone to use this software for any purpose,     */
  20 /* including commercial applications, and to alter it and redistribute it    */
  21 /* freely, subject to the following restrictions:                            */
  22 /*                                                                           */
  23 /* 1. The origin of this software must not be misrepresented; you must not   */
  24 /*    claim that you wrote the original software. If you use this software   */
  25 /*    in a product, an acknowledgment in the product documentation would be  */
  26 /*    appreciated but is not required.                                       */
  27 /* 2. Altered source versions must be plainly marked as such, and must not   */
  28 /*    be misrepresented as being the original software.                      */
  29 /* 3. This notice may not be removed or altered from any source              */
  30 /*    distribution.                                                          */
  31 /*                                                                           */
  32 /*****************************************************************************/
  33
  34
  35
  36 #include <string.h>
  37 #include <time.h>
  38
  39 /* common */
  40 #include "check.h"
  41 #include "exprdefs.h"
  42 #include "print.h"
  43 #include "tgttrans.h"
  44 #include "xmalloc.h"
  45
  46 /* ca65 */
  47 #include "error.h"
  48 #include "global.h"
  49 #include "instr.h"
  50 #include "nexttok.h"
  51 #include "objcode.h"
  52 #include "objfile.h"
  53 #include "symtab.h"
  54 #include "toklist.h"
  55 #include "ulabel.h"
  56 #include "expr.h"
  57
  58
  59
  60 /*****************************************************************************/
  61 /*                                   Data                                    */
  62 /*****************************************************************************/
  63
  64
  65
  66 /* Since all expressions are first packed into expression trees, and each
  67  * expression tree node is allocated on the heap, we add some type of special
  68  * purpose memory allocation here: Instead of freeing the nodes, we save some
  69  * number of freed nodes for later and remember them in a single linked list
  70  * using the Left link.
  71  */
  72 #define MAX_FREE_NODES  64
  73 static ExprNode*        FreeExprNodes = 0;
  74 static unsigned         FreeNodeCount = 0;
  75
  76
  77
  78 /*****************************************************************************/
  79 /*                                  Helpers                                  */
  80 /*****************************************************************************/
  81
  82
  83
  84 static ExprNode* NewExprNode (void)
  85 /* Create a new expression node */
  86 {
  87     ExprNode* N;
  88
  89     /* Do we have some nodes in the list already? */
  90     if (FreeExprNodes) {
  91         /* Use first node from list */
  92         N = FreeExprNodes;
  93         FreeExprNodes = N->Left;
  94     } else {
  95         /* Allocate fresh memory */
  96         N = xmalloc (sizeof (ExprNode));
  97     }
  98     N->Op = EXPR_NULL;
  99     N->Left = N->Right = 0;
 100     N->Obj = 0;
 101
 102     return N;
 103 }
 104
 105
 106
 107 static void FreeExprNode (ExprNode* E)
 108 /* Free a node */
 109 {
 110     if (E) {
 111         if (FreeNodeCount < MAX_FREE_NODES) {
 112             /* Remember this node for later */
 113             E->Left = FreeExprNodes;
 114             FreeExprNodes = E;
 115         } else {
 116             /* Free the memory */
 117             xfree (E);
 118         }
 119     }
 120 }
 121
 122
 123
 124 /*****************************************************************************/
 125 /*                                   Code                                    */
 126 /*****************************************************************************/
 127
 128
 129
 130 static ExprNode* Expr0 (void);
 131
 132
 133
 134 int IsByteRange (long Val)
 135 /* Return true if this is a byte value */
 136 {
 137     return (Val & ~0xFFL) == 0;
 138 }
 139
 140
 141
 142 int IsWordRange (long Val)
 143 /* Return true if this is a word value */
 144 {
 145     return (Val & ~0xFFFF) == 0;
 146 }
 147
 148
 149
 150 static int FuncBlank (void)
 151 /* Handle the .BLANK builtin function */
 152 {
 153     /* Assume no tokens if the closing brace follows (this is not correct in
 154      * all cases, since the token may be the closing brace, but this will
 155      * give a syntax error anyway and may not be handled by .BLANK.
 156      */
 157     if (Tok == TOK_RPAREN) {
 158         /* No tokens */
 159         return 1;
 160     } else {
 161         /* Skip any tokens */
 162         int Braces = 0;
 163         while (!TokIsSep (Tok)) {
 164             if (Tok == TOK_LPAREN) {
 165                 ++Braces;
 166             } else if (Tok == TOK_RPAREN) {
 167                 if (Braces == 0) {
 168                     /* Done */
 169                     break;
 170                 } else {
 171                     --Braces;
 172                 }
 173             }
 174             NextTok ();
 175         }
 176         return 0;
 177     }
 178 }
 179
 180
 181
 182 static int FuncConst (void)
 183 /* Handle the .CONST builtin function */
 184 {
 185     /* Read an expression */
 186     ExprNode* Expr = Expression ();
 187
 188     /* Check the constness of the expression */
 189     int Result = IsConstExpr (Expr);
 190
 191     /* Free the expression */
 192     FreeExpr (Expr);
 193
 194     /* Done */
 195     return Result;
 196 }
 197
 198
 199
 200 static int FuncDefined (void)
 201 /* Handle the .DEFINED builtin function */
 202 {
 203     static const char* Keys[] = {
 204         "ANY",
 205         "GLOBAL",
 206         "LOCAL",
 207     };
 208
 209     char Name [sizeof (SVal)];
 210     int Result = 0;
 211     int Scope;
 212
 213     /* First argument is a symbol name */
 214     if (Tok != TOK_IDENT) {
 215         Error (ERR_IDENT_EXPECTED);
 216         if (Tok != TOK_RPAREN) {
 217             NextTok ();
 218         }
 219         return 0;
 220     }
 221
 222     /* Remember the name, then skip it */
 223     strcpy (Name, SVal);
 224     NextTok ();
 225
 226     /* Comma and scope spec may follow */
 227     if (Tok == TOK_COMMA) {
 228
 229         /* Skip the comma */
 230         NextTok ();
 231
 232         /* An identifier must follow */
 233         if (Tok != TOK_IDENT) {
 234             Error (ERR_IDENT_EXPECTED);
 235             return 0;
 236         }
 237
 238         /* Get the scope, then skip it */
 239         Scope = GetSubKey (Keys, sizeof (Keys) / sizeof (Keys [0]));
 240         NextTok ();
 241
 242         /* Check if we got a valid keyword */
 243         if (Scope < 0) {
 244             Error (ERR_ILLEGAL_SCOPE);
 245             return 0;
 246         }
 247
 248         /* Map the scope */
 249         switch (Scope) {
 250             case 0:     Scope = SCOPE_ANY;    break;
 251             case 1:     Scope = SCOPE_GLOBAL; break;
 252             case 2:     Scope = SCOPE_LOCAL;  break;
 253             default:    Internal ("Invalid scope: %d", Scope);
 254         }
 255
 256     } else {
 257
 258         /* Any scope */
 259         Scope = SCOPE_ANY;
 260
 261     }
 262
 263     /* Search for the symbol */
 264     Result = SymIsDef (SVal, Scope);
 265
 266     /* Done */
 267     return Result;
 268 }
 269
 270
 271
 272 static int DoMatch (enum TC EqualityLevel)
 273 /* Handle the .MATCH and .XMATCH builtin functions */
 274 {
 275     int Result;
 276     TokNode* Root = 0;
 277     TokNode* Last = 0;
 278     TokNode* Node = 0;
 279
 280     /* A list of tokens follows. Read this list and remember it building a
 281      * single linked list of tokens including attributes. The list is
 282      * terminated by a comma.
 283      */
 284     while (Tok != TOK_COMMA) {
 285
 286         /* We may not end-of-line of end-of-file here */
 287         if (TokIsSep (Tok)) {
 288             Error (ERR_UNEXPECTED_EOL);
 289             return 0;
 290         }
 291
 292         /* Get a node with this token */
 293         Node = NewTokNode ();
 294
 295         /* Insert the node into the list */
 296         if (Last == 0) {
 297             Root = Node;
 298         } else {
 299             Last->Next = Node;
 300         }
 301         Last = Node;
 302
 303         /* Skip the token */
 304         NextTok ();
 305     }
 306
 307     /* Skip the comma */
 308     NextTok ();
 309
 310     /* Read the second list which is terminated by the right parenthesis and
 311      * compare each token against the one in the first list.
 312      */
 313     Result = 1;
 314     Node = Root;
 315     while (Tok != TOK_RPAREN) {
 316
 317         /* We may not end-of-line of end-of-file here */
 318         if (TokIsSep (Tok)) {
 319             Error (ERR_UNEXPECTED_EOL);
 320             return 0;
 321         }
 322
 323         /* Compare the tokens if the result is not already known */
 324         if (Result != 0) {
 325             if (Node == 0) {
 326                 /* The second list is larger than the first one */
 327                 Result = 0;
 328             } else if (TokCmp (Node) < EqualityLevel) {
 329                 /* Tokens do not match */
 330                 Result = 0;
 331             }
 332         }
 333
 334         /* Next token in first list */
 335         if (Node) {
 336             Node = Node->Next;
 337         }
 338
 339         /* Next token in current list */
 340         NextTok ();
 341     }
 342
 343     /* Check if there are remaining tokens in the first list */
 344     if (Node != 0) {
 345         Result = 0;
 346     }
 347
 348     /* Free the token list */
 349     while (Root) {
 350         Node = Root;
 351         Root = Root->Next;
 352         FreeTokNode (Node);
 353     }
 354
 355     /* Done, return the result */
 356     return Result;
 357 }
 358
 359
 360
 361 static int FuncMatch (void)
 362 /* Handle the .MATCH function */
 363 {
 364     return DoMatch (tcSameToken);
 365 }
 366
 367
 368
 369 static int FuncReferenced (void)
 370 /* Handle the .REFERENCED builtin function */
 371 {
 372     int Result = 0;
 373
 374     if (Tok != TOK_IDENT) {
 375         Error (ERR_IDENT_EXPECTED);
 376         if (Tok != TOK_RPAREN) {
 377             NextTok ();
 378         }
 379     } else {
 380         Result = SymIsRef (SVal, SCOPE_ANY);
 381         NextTok ();
 382     }
 383
 384     /* Done */
 385     return Result;
 386 }
 387
 388
 389
 390 static int FuncStrAt (void)
 391 /* Handle the .STRAT function */
 392 {
 393     char Str [sizeof(SVal)];
 394     long Index;
 395
 396     /* String constant expected */
 397     if (Tok != TOK_STRCON) {
 398         Error (ERR_STRCON_EXPECTED);
 399         NextTok ();
 400         return 0;
 401
 402     }
 403
 404     /* Remember the string and skip it */
 405     strcpy (Str, SVal);
 406     NextTok ();
 407
 408     /* Comma must follow */
 409     ConsumeComma ();
 410
 411     /* Expression expected */
 412     Index = ConstExpression ();
 413
 414     /* Must be a valid index */
 415     if (Index >= (long) strlen (Str)) {
 416         Error (ERR_RANGE);
 417         return 0;
 418     }
 419
 420     /* Return the char, handle as unsigned. Be sure to translate it into
 421      * the target character set.
 422      */
 423     return (unsigned char) TgtTranslateChar (Str [(size_t)Index]);
 424 }
 425
 426
 427
 428 static int FuncStrLen (void)
 429 /* Handle the .STRLEN function */
 430 {
 431     /* String constant expected */
 432     if (Tok != TOK_STRCON) {
 433
 434         Error (ERR_STRCON_EXPECTED);
 435         /* Smart error recovery */
 436         if (Tok != TOK_RPAREN) {
 437             NextTok ();
 438         }
 439         return 0;
 440
 441     } else {
 442
 443         /* Get the length of the string */
 444         int Len = strlen (SVal);
 445
 446         /* Skip the string */
 447         NextTok ();
 448
 449         /* Return the length */
 450         return Len;
 451
 452     }
 453 }
 454
 455
 456
 457 static int FuncTCount (void)
 458 /* Handle the .TCOUNT function */
 459 {
 460     /* We have a list of tokens that ends with the closing paren. Skip
 461      * the tokens, handling nested braces and count them.
 462      */
 463     int      Count  = 0;
 464     unsigned Parens = 0;
 465     while (Parens != 0 || Tok != TOK_RPAREN) {
 466
 467         /* Check for end of line or end of input. Since the calling function
 468          * will check for the closing paren, we don't need to print an error
 469          * here, just bail out.
 470          */
 471         if (TokIsSep (Tok)) {
 472             break;
 473         }
 474
 475         /* One more token */
 476         ++Count;
 477
 478         /* Keep track of the nesting level */
 479         switch (Tok) {
 480             case TOK_LPAREN:    ++Parens;       break;
 481             case TOK_RPAREN:    --Parens;       break;
 482             default:                            break;
 483         }
 484
 485         /* Skip the token */
 486         NextTok ();
 487     }
 488
 489     /* Return the number of tokens */
 490     return Count;
 491 }
 492
 493
 494
 495 static int FuncXMatch (void)
 496 /* Handle the .XMATCH function */
 497 {
 498     return DoMatch (tcIdentical);
 499 }
 500
 501
 502
 503 static ExprNode* Function (int (*F) (void))
 504 /* Handle builtin functions */
 505 {
 506     long Result;
 507
 508     /* Skip the keyword */
 509     NextTok ();
 510
 511     /* Expression must be enclosed in braces */
 512     if (Tok != TOK_LPAREN) {
 513         Error (ERR_LPAREN_EXPECTED);
 514         SkipUntilSep ();
 515         return GenLiteralExpr (0);
 516     }
 517     NextTok ();
 518
 519     /* Call the function itself */
 520     Result = F ();
 521
 522     /* Closing brace must follow */
 523     ConsumeRParen ();
 524
 525     /* Return an expression node with the boolean code */
 526     return GenLiteralExpr (Result);
 527 }
 528
 529
 530
 531 static ExprNode* Factor (void)
 532 {
 533     ExprNode* N;
 534     SymEntry* S;
 535
 536     switch (Tok) {
 537
 538         case TOK_INTCON:
 539             N = GenLiteralExpr (IVal);
 540             NextTok ();
 541             break;
 542
 543         case TOK_CHARCON:
 544             N = GenLiteralExpr (TgtTranslateChar (IVal));
 545             NextTok ();
 546             break;
 547
 548         case TOK_NAMESPACE:
 549             NextTok ();
 550             if (Tok != TOK_IDENT) {
 551                 Error (ERR_IDENT_EXPECTED);
 552                 N = GenLiteralExpr (0); /* Dummy */
 553             } else {
 554                 S = SymRef (SVal, SCOPE_GLOBAL);
 555                 if (SymIsConst (S)) {
 556                     /* Use the literal value instead */
 557                     N = GenLiteralExpr (GetSymVal (S));
 558                 } else {
 559                     /* Create symbol node */
 560                     N = NewExprNode ();
 561                     N->Op    = EXPR_SYMBOL;
 562                     N->V.Sym = S;
 563                 }
 564                 NextTok ();
 565             }
 566             break;
 567
 568         case TOK_IDENT:
 569             S = SymRef (SVal, SCOPE_LOCAL);
 570             if (SymIsConst (S)) {
 571                 /* Use the literal value instead */
 572                 N = GenLiteralExpr (GetSymVal (S));
 573             } else {
 574                 /* Create symbol node */
 575                 N = NewExprNode ();
 576                 N->Op    = EXPR_SYMBOL;
 577                 N->V.Sym = S;
 578             }
 579             NextTok ();
 580             break;
 581
 582         case TOK_ULABEL:
 583             N = ULabRef (IVal);
 584             NextTok ();
 585             break;
 586
 587         case TOK_MINUS:
 588             NextTok ();
 589             N = NewExprNode ();
 590             N->Left = Factor ();
 591             N->Op   = EXPR_UNARY_MINUS;
 592             break;
 593
 594         case TOK_NOT:
 595             NextTok ();
 596             N = NewExprNode ();
 597             N->Left = Factor ();
 598             N->Op   = EXPR_NOT;
 599             break;
 600
 601         case TOK_STAR:
 602         case TOK_PC:
 603             NextTok ();
 604             N = GenCurrentPC ();
 605             break;
 606
 607         case TOK_LT:
 608             NextTok ();
 609             N = NewExprNode ();
 610             N->Left = Factor ();
 611             N->Op   = EXPR_BYTE0;
 612             break;
 613
 614         case TOK_GT:
 615             NextTok ();
 616             N = NewExprNode ();
 617             N->Left = Factor ();
 618             N->Op   = EXPR_BYTE1;
 619             break;
 620
 621         case TOK_LPAREN:
 622             NextTok ();
 623             N = Expr0 ();
 624             ConsumeRParen ();
 625             break;
 626
 627         case TOK_BLANK:
 628             N = Function (FuncBlank);
 629             break;
 630
 631         case TOK_CONST:
 632             N = Function (FuncConst);
 633             break;
 634
 635         case TOK_CPU:
 636             N = GenLiteralExpr (GetCPU());
 637             NextTok ();
 638             break;
 639
 640         case TOK_DEFINED:
 641             N = Function (FuncDefined);
 642             break;
 643
 644         case TOK_MATCH:
 645             N = Function (FuncMatch);
 646             break;
 647
 648         case TOK_REFERENCED:
 649             N = Function (FuncReferenced);
 650             break;
 651
 652         case TOK_STRAT:
 653             N = Function (FuncStrAt);
 654             break;
 655
 656         case TOK_STRLEN:
 657             N = Function (FuncStrLen);
 658             break;
 659
 660         case TOK_TCOUNT:
 661             N = Function (FuncTCount);
 662             break;
 663
 664         case TOK_TIME:
 665             N = GenLiteralExpr (time (0));
 666             NextTok ();
 667             break;
 668
 669         case TOK_XMATCH:
 670             N = Function (FuncXMatch);
 671             break;
 672
 673         default:
 674             if (LooseCharTerm && Tok == TOK_STRCON && strlen(SVal) == 1) {
 675                 /* A character constant */
 676                 N = GenLiteralExpr (TgtTranslateChar (SVal[0]));
 677             } else {
 678                 N = GenLiteralExpr (0); /* Dummy */
 679                 Error (ERR_SYNTAX);
 680             }
 681             NextTok ();
 682             break;
 683     }
 684     return N;
 685 }
 686
 687
 688
 689 static ExprNode* Term (void)
 690 {
 691     ExprNode* Root;
 692
 693     /* Read left hand side */
 694     Root = Factor ();
 695
 696     /* Handle multiplicative operations */
 697     while (Tok == TOK_MUL || Tok == TOK_DIV || Tok == TOK_MOD ||
 698            Tok == TOK_AND || Tok == TOK_XOR || Tok == TOK_SHL ||
 699            Tok == TOK_SHR) {
 700
 701         /* Create a new node and insert the left expression */
 702         ExprNode* Left = Root;
 703         Root = NewExprNode ();
 704         Root->Left = Left;
 705
 706         /* Determine the operator token */
 707         switch (Tok) {
 708             case TOK_MUL:       Root->Op = EXPR_MUL;    break;
 709             case TOK_DIV:       Root->Op = EXPR_DIV;    break;
 710             case TOK_MOD:       Root->Op = EXPR_MOD;    break;
 711             case TOK_AND:       Root->Op = EXPR_AND;    break;
 712             case TOK_XOR:       Root->Op = EXPR_XOR;    break;
 713             case TOK_SHL:       Root->Op = EXPR_SHL;    break;
 714             case TOK_SHR:       Root->Op = EXPR_SHR;    break;
 715             default:            Internal ("Invalid token");
 716         }
 717         NextTok ();
 718
 719         /* Parse the right hand side */
 720         Root->Right = Factor ();
 721
 722     }
 723
 724     /* Return the expression tree we've created */
 725     return Root;
 726 }
 727
 728
 729
 730 static ExprNode* SimpleExpr (void)
 731 {
 732     ExprNode* Root;
 733
 734     /* Read left hand side */
 735     Root = Term ();
 736
 737     /* Handle additive operations */
 738     while (Tok == TOK_PLUS || Tok == TOK_MINUS || Tok == TOK_OR) {
 739
 740         /* Create a new node and insert the left expression */
 741         ExprNode* Left = Root;
 742         Root = NewExprNode ();
 743         Root->Left = Left;
 744
 745         /* Determine the operator token */
 746         switch (Tok) {
 747             case TOK_PLUS:      Root->Op = EXPR_PLUS;   break;
 748             case TOK_MINUS:     Root->Op = EXPR_MINUS;  break;
 749             case TOK_OR:        Root->Op = EXPR_OR;     break;
 750             default:            Internal ("Invalid token");
 751         }
 752         NextTok ();
 753
 754         /* Parse the right hand side */
 755         Root->Right = Term ();
 756
 757     }
 758
 759     /* Return the expression tree we've created */
 760     return Root;
 761 }
 762
 763
 764
 765 static ExprNode* BoolExpr (void)
 766 /* Evaluate a boolean expression */
 767 {
 768     /* Read left hand side */
 769     ExprNode* Root = SimpleExpr ();
 770
 771     /* Handle booleans */
 772     while (Tok == TOK_EQ || Tok == TOK_NE || Tok == TOK_LT ||
 773            Tok == TOK_GT || Tok == TOK_LE || Tok == TOK_GE) {
 774
 775         /* Create a new node and insert the left expression */
 776         ExprNode* Left = Root;
 777         Root = NewExprNode ();
 778         Root->Left = Left;
 779
 780         /* Determine the operator token */
 781         switch (Tok) {
 782             case TOK_EQ:        Root->Op = EXPR_EQ;     break;
 783             case TOK_NE:        Root->Op = EXPR_NE;     break;
 784             case TOK_LT:        Root->Op = EXPR_LT;     break;
 785             case TOK_GT:        Root->Op = EXPR_GT;     break;
 786             case TOK_LE:        Root->Op = EXPR_LE;     break;
 787             case TOK_GE:        Root->Op = EXPR_GE;     break;
 788             default:            Internal ("Invalid token");
 789         }
 790         NextTok ();
 791
 792         /* Parse the right hand side */
 793         Root->Right = SimpleExpr ();
 794
 795     }
 796
 797     /* Return the expression tree we've created */
 798     return Root;
 799 }
 800
 801
 802
 803 static ExprNode* Expr2 (void)
 804 /* Boolean operators: AND and XOR */
 805 {
 806     /* Read left hand side */
 807     ExprNode* Root = BoolExpr ();
 808
 809     /* Handle booleans */
 810     while (Tok == TOK_BAND || Tok == TOK_BXOR) {
 811
 812         /* Create a new node and insert the left expression */
 813         ExprNode* Left = Root;
 814         Root = NewExprNode ();
 815         Root->Left = Left;
 816
 817         /* Determine the operator token */
 818         switch (Tok) {
 819             case TOK_BAND:      Root->Op = EXPR_BAND;   break;
 820             case TOK_BXOR:      Root->Op = EXPR_BXOR;   break;
 821             default:            Internal ("Invalid token");
 822         }
 823         NextTok ();
 824
 825         /* Parse the right hand side */
 826         Root->Right = BoolExpr ();
 827
 828     }
 829
 830     /* Return the expression tree we've created */
 831     return Root;
 832 }
 833
 834
 835
 836 static ExprNode* Expr1 (void)
 837 /* Boolean operators: OR */
 838 {
 839     /* Read left hand side */
 840     ExprNode* Root = Expr2 ();
 841
 842     /* Handle booleans */
 843     while (Tok == TOK_BOR) {
 844
 845         /* Create a new node and insert the left expression */
 846         ExprNode* Left = Root;
 847         Root = NewExprNode ();
 848         Root->Left = Left;
 849
 850         /* Determine the operator token */
 851         switch (Tok) {
 852             case TOK_BOR:       Root->Op = EXPR_BOR;    break;
 853             default:            Internal ("Invalid token");
 854         }
 855         NextTok ();
 856
 857         /* Parse the right hand side */
 858         Root->Right = Expr2 ();
 859
 860     }
 861
 862     /* Return the expression tree we've created */
 863     return Root;
 864 }
 865
 866
 867
 868 static ExprNode* Expr0 (void)
 869 /* Boolean operators: NOT */
 870 {
 871     ExprNode* Root;
 872
 873     /* Handle booleans */
 874     if (Tok == TOK_BNOT) {
 875
 876         /* Create a new node */
 877         Root = NewExprNode ();
 878
 879         /* Determine the operator token */
 880         switch (Tok) {
 881             case TOK_BNOT:      Root->Op = EXPR_BNOT;   break;
 882             default:            Internal ("Invalid token");
 883         }
 884         NextTok ();
 885
 886         /* Parse the left hand side, allow more BNOTs */
 887         Root->Left = Expr0 ();
 888
 889     } else {
 890
 891         /* Read left hand side */
 892         Root = Expr1 ();
 893
 894     }
 895
 896     /* Return the expression tree we've created */
 897     return Root;
 898 }
 899
 900
 901
 902 static ExprNode* SimplifyExpr (ExprNode* Root)
 903 /* Try to simplify the given expression tree */
 904 {
 905     if (Root) {
 906         SimplifyExpr (Root->Left);
 907         SimplifyExpr (Root->Right);
 908         if (IsConstExpr (Root)) {
 909             /* The complete expression is constant */
 910             Root->V.Val = GetExprVal (Root);
 911             Root->Op = EXPR_LITERAL;
 912             FreeExpr (Root->Left);
 913             FreeExpr (Root->Right);
 914             Root->Left = Root->Right = 0;
 915         }
 916     }
 917     return Root;
 918 }
 919
 920
 921
 922 ExprNode* Expression (void)
 923 /* Evaluate an expression, build the expression tree on the heap and return
 924  * a pointer to the root of the tree.
 925  */
 926 {
 927     return SimplifyExpr (Expr0 ());
 928 }
 929
 930
 931
 932 long ConstExpression (void)
 933 /* Parse an expression. Check if the expression is const, and print an error
 934  * message if not. Return the value of the expression, or a dummy, if it is
 935  * not constant.
 936  */
 937 {
 938     /* Read the expression, and call finalize (exception here, since we
 939      * expect a const).
 940      */
 941     ExprNode* Expr = FinalizeExpr (Expression ());
 942
 943     /* Return the value */
 944     if (IsConstExpr (Expr)) {
 945         return GetExprVal (Expr);
 946     } else {
 947         Error (ERR_CONSTEXPR_EXPECTED);
 948         return 0;
 949     }
 950 }
 951
 952
 953
 954 void FreeExpr (ExprNode* Root)
 955 /* Free the expression, Root is pointing to. */
 956 {
 957     if (Root) {
 958         FreeExpr (Root->Left);
 959         FreeExpr (Root->Right);
 960         FreeExprNode (Root);
 961     }
 962 }
 963
 964
 965
 966 ExprNode* GenLiteralExpr (long Val)
 967 /* Return an expression tree that encodes the given literal value */
 968 {
 969     ExprNode* Expr = NewExprNode ();
 970     Expr->Op = EXPR_LITERAL;
 971     Expr->V.Val = Val;
 972     return Expr;
 973 }
 974
 975
 976
 977 ExprNode* GenCurrentPC (void)
 978 /* Return the current program counter as expression */
 979 {
 980     ExprNode* Left;
 981     ExprNode* Root;
 982
 983     if (RelocMode) {
 984         /* Create SegmentBase + Offset */
 985         Left = NewExprNode ();
 986         Left->Op = EXPR_SECTION;
 987         Left->V.SegNum = GetSegNum ();
 988
 989         Root = NewExprNode ();
 990         Root->Left  = Left;
 991         Root->Right = GenLiteralExpr (GetPC ());
 992         Root->Op = EXPR_PLUS;
 993     } else {
 994         /* Absolute mode, just return PC value */
 995         Root = GenLiteralExpr (GetPC ());
 996     }
 997
 998     return Root;
 999 }
1000
1001
1002
1003 ExprNode* GenSwapExpr (ExprNode* Expr)
1004 /* Return an extended expression with lo and hi bytes swapped */
1005 {
1006     ExprNode* N = NewExprNode ();
1007     N->Op = EXPR_SWAP;
1008     N->Left = Expr;
1009     return N;
1010 }
1011
1012
1013
1014 ExprNode* GenBranchExpr (unsigned Offs)
1015 /* Return an expression that encodes the difference between current PC plus
1016  * offset and the target expression (that is, Expression() - (*+Offs) ).
1017  */
1018 {
1019     ExprNode* N;
1020     ExprNode* Root;
1021     ExprNode* Left;
1022
1023     /* Create *+Offs */
1024     if (RelocMode) {
1025         Left = NewExprNode ();
1026         Left->Op = EXPR_SECTION;
1027         Left->V.SegNum = GetSegNum ();
1028
1029         N = NewExprNode ();
1030         N->Left  = Left;
1031         N->Right = GenLiteralExpr (GetPC () + Offs);
1032         N->Op = EXPR_PLUS;
1033     } else {
1034         N = GenLiteralExpr (GetPC () + Offs);
1035     }
1036
1037     /* Create the root node */
1038     Root = NewExprNode ();
1039     Root->Left = Expression ();
1040     Root->Right = N;
1041     Root->Op = EXPR_MINUS;
1042
1043     /* Return the result */
1044     return SimplifyExpr (Root);
1045 }
1046
1047
1048
1049 ExprNode* GenULabelExpr (unsigned Num)
1050 /* Return an expression for an unnamed label with the given index */
1051 {
1052     /* Get an expression node */
1053     ExprNode* Node = NewExprNode ();
1054
1055     /* Set the values */
1056     Node->Op    = EXPR_ULABEL;
1057     Node->V.Val = Num;
1058
1059     /* Return the new node */
1060     return Node;
1061 }
1062
1063
1064
1065 ExprNode* GenByteExpr (ExprNode* Expr)
1066 /* Force the given expression into a byte and return the result */
1067 {
1068     /* Use the low byte operator to force the expression into byte size */
1069     ExprNode* Root = NewExprNode ();
1070     Root->Left  = Expr;
1071     Root->Op    = EXPR_BYTE0;
1072
1073     /* Return the result */
1074     return Root;
1075 }
1076
1077
1078
1079 ExprNode* GenWordExpr (ExprNode* Expr)
1080 /* Force the given expression into a word and return the result. */
1081 {
1082     /* AND the expression by $FFFF to force it into word size */
1083     ExprNode* Root = NewExprNode ();
1084     Root->Left  = Expr;
1085     Root->Op    = EXPR_AND;
1086     Root->Right = GenLiteralExpr (0xFFFF);
1087
1088     /* Return the result */
1089     return Root;
1090 }
1091
1092
1093
1094 ExprNode* GenNE (ExprNode* Expr, long Val)
1095 /* Generate an expression that compares Expr and Val for inequality */
1096 {
1097     /* Generate a compare node */
1098     ExprNode* Root = NewExprNode ();
1099     Root->Left  = Expr;
1100     Root->Op    = EXPR_NE;
1101     Root->Right = GenLiteralExpr (Val);
1102
1103     /* Return the result */
1104     return Root;
1105 }
1106
1107
1108
1109 int IsConstExpr (ExprNode* Root)
1110 /* Return true if the given expression is a constant expression, that is, one
1111  * with no references to external symbols.
1112  */
1113 {
1114     int Const;
1115     SymEntry* Sym;
1116
1117     if (EXPR_IS_LEAF (Root->Op)) {
1118         switch (Root->Op) {
1119
1120             case EXPR_LITERAL:
1121                 return 1;
1122
1123             case EXPR_SYMBOL:
1124                 Sym = Root->V.Sym;
1125                 if (SymHasUserMark (Sym)) {
1126                     if (Verbosity > 0) {
1127                         DumpExpr (Root);
1128                     }
1129                     PError (GetSymPos (Sym), ERR_CIRCULAR_REFERENCE);
1130                     Const = 0;
1131                 } else {
1132                     SymMarkUser (Sym);
1133                     Const = SymIsConst (Sym);
1134                     SymUnmarkUser (Sym);
1135                 }
1136                 return Const;
1137
1138             default:
1139                 return 0;
1140
1141         }
1142     } else if (EXPR_IS_UNARY (Root->Op)) {
1143
1144         return IsConstExpr (Root->Left);
1145
1146     } else {
1147
1148         /* We must handle shortcut boolean expressions here */
1149         switch (Root->Op) {
1150
1151             case EXPR_BAND:
1152                 if (IsConstExpr (Root->Left)) {
1153                     /* lhs is const, if it is zero, don't eval right */
1154                     if (GetExprVal (Root->Left) == 0) {
1155                         return 1;
1156                     } else {
1157                         return IsConstExpr (Root->Right);
1158                     }
1159                 } else {
1160                     /* lhs not const --> tree not const */
1161                     return 0;
1162                 }
1163                 break;
1164
1165             case EXPR_BOR:
1166                 if (IsConstExpr (Root->Left)) {
1167                     /* lhs is const, if it is not zero, don't eval right */
1168                     if (GetExprVal (Root->Left) != 0) {
1169                         return 1;
1170                     } else {
1171                         return IsConstExpr (Root->Right);
1172                     }
1173                 } else {
1174                     /* lhs not const --> tree not const */
1175                     return 0;
1176                 }
1177                 break;
1178
1179             default:
1180                 /* All others are handled normal */
1181                 return IsConstExpr (Root->Left) && IsConstExpr (Root->Right);
1182         }
1183     }
1184 }
1185
1186
1187
1188 static void CheckByteExpr (const ExprNode* N, int* IsByte)
1189 /* Internal routine that is recursively called to check if there is a zeropage
1190  * symbol in the expression tree.
1191  */
1192 {
1193     if (N) {
1194         switch (N->Op & EXPR_TYPEMASK) {
1195
1196             case EXPR_LEAFNODE:
1197                 switch (N->Op) {
1198
1199                     case EXPR_SYMBOL:
1200                         if (SymIsZP (N->V.Sym)) {
1201                             *IsByte = 1;
1202                         } else if (SymHasExpr (N->V.Sym)) {
1203                             /* Check if this expression is a byte expression */
1204                             *IsByte = IsByteExpr (GetSymExpr (N->V.Sym));
1205                         }
1206                         break;
1207
1208                     case EXPR_SECTION:
1209                         if (GetSegType (N->V.SegNum) == SEGTYPE_ZP) {
1210                             *IsByte = 1;
1211                         }
1212                         break;
1213
1214                 }
1215                 break;
1216
1217             case EXPR_UNARYNODE:
1218                 CheckByteExpr (N->Left, IsByte);
1219                 break;
1220
1221             case EXPR_BINARYNODE:
1222                 CheckByteExpr (N->Left, IsByte);
1223                 CheckByteExpr (N->Right, IsByte);
1224                 break;
1225
1226             default:
1227                 Internal ("Unknown expression op: %02X", N->Op);
1228         }
1229     }
1230 }
1231
1232
1233
1234 int IsByteExpr (ExprNode* Root)
1235 /* Return true if this is a byte expression */
1236 {
1237     int IsByte;
1238
1239     if (IsConstExpr (Root)) {
1240         if (Root->Op != EXPR_LITERAL) {
1241             SimplifyExpr (Root);
1242         }
1243         return IsByteRange (GetExprVal (Root));
1244     } else if (Root->Op == EXPR_BYTE0 || Root->Op == EXPR_BYTE1 ||
1245                Root->Op == EXPR_BYTE2 || Root->Op == EXPR_BYTE3) {
1246         /* Symbol forced to have byte range */
1247         IsByte = 1;
1248     } else {
1249         /* We have undefined symbols in the expression. Assume that the
1250          * expression is a byte expression if there is at least one symbol
1251          * declared as zeropage in it. Being wrong here is not a very big
1252          * problem since the linker knows about all symbols and detects
1253          * error like mixing absolute and zeropage labels.
1254          */
1255         IsByte = 0;
1256         CheckByteExpr (Root, &IsByte);
1257     }
1258     return IsByte;
1259 }
1260
1261
1262
1263 long GetExprVal (ExprNode* Expr)
1264 /* Get the value of a constant expression */
1265 {
1266     long Right, Left;
1267
1268     switch (Expr->Op) {
1269
1270         case EXPR_LITERAL:
1271             return Expr->V.Val;
1272
1273         case EXPR_SYMBOL:
1274             return GetSymVal (Expr->V.Sym);
1275
1276         case EXPR_PLUS:
1277             return GetExprVal (Expr->Left) + GetExprVal (Expr->Right);
1278
1279         case EXPR_MINUS:
1280             return GetExprVal (Expr->Left) - GetExprVal (Expr->Right);
1281
1282         case EXPR_MUL:
1283             return GetExprVal (Expr->Left) * GetExprVal (Expr->Right);
1284
1285         case EXPR_DIV:
1286             Left  = GetExprVal (Expr->Left);
1287             Right = GetExprVal (Expr->Right);
1288             if (Right == 0) {
1289                 Error (ERR_DIV_BY_ZERO);
1290                 return 0;
1291             }
1292             return Left / Right;
1293
1294         case EXPR_MOD:
1295             Left  = GetExprVal (Expr->Left);
1296             Right = GetExprVal (Expr->Right);
1297             if (Right == 0) {
1298                 Error (ERR_MOD_BY_ZERO);
1299                 return 0;
1300             }
1301             return Left % Right;
1302
1303         case EXPR_OR:
1304             return GetExprVal (Expr->Left) | GetExprVal (Expr->Right);
1305
1306         case EXPR_XOR:
1307             return GetExprVal (Expr->Left) ^ GetExprVal (Expr->Right);
1308
1309         case EXPR_AND:
1310             return GetExprVal (Expr->Left) & GetExprVal (Expr->Right);
1311
1312         case EXPR_SHL:
1313             return GetExprVal (Expr->Left) << GetExprVal (Expr->Right);
1314
1315         case EXPR_SHR:
1316             return GetExprVal (Expr->Left) >> GetExprVal (Expr->Right);
1317
1318         case EXPR_EQ:
1319             return (GetExprVal (Expr->Left) == GetExprVal (Expr->Right));
1320
1321         case EXPR_NE:
1322             return (GetExprVal (Expr->Left) != GetExprVal (Expr->Right));
1323
1324         case EXPR_LT:
1325             return (GetExprVal (Expr->Left) < GetExprVal (Expr->Right));
1326
1327         case EXPR_GT:
1328             return (GetExprVal (Expr->Left) > GetExprVal (Expr->Right));
1329
1330         case EXPR_LE:
1331             return (GetExprVal (Expr->Left) <= GetExprVal (Expr->Right));
1332
1333         case EXPR_GE:
1334             return (GetExprVal (Expr->Left) >= GetExprVal (Expr->Right));
1335
1336         case EXPR_UNARY_MINUS:
1337             return -GetExprVal (Expr->Left);
1338
1339         case EXPR_NOT:
1340             return ~GetExprVal (Expr->Left);
1341
1342         case EXPR_BYTE0:
1343             return GetExprVal (Expr->Left) & 0xFF;
1344
1345         case EXPR_BYTE1:
1346             return (GetExprVal (Expr->Left) >> 8) & 0xFF;
1347
1348         case EXPR_BYTE2:
1349             return (GetExprVal (Expr->Left) >> 16) & 0xFF;
1350
1351         case EXPR_BYTE3:
1352             return (GetExprVal (Expr->Left) >> 24) & 0xFF;
1353
1354         case EXPR_SWAP:
1355             Left = GetExprVal (Expr->Left);
1356             return ((Left >> 8) & 0x00FF) | ((Left << 8) & 0xFF00);
1357
1358         case EXPR_BAND:
1359             return GetExprVal (Expr->Left) && GetExprVal (Expr->Right);
1360
1361         case EXPR_BOR:
1362             return GetExprVal (Expr->Left) || GetExprVal (Expr->Right);
1363
1364         case EXPR_BXOR:
1365             return (GetExprVal (Expr->Left) != 0) ^ (GetExprVal (Expr->Right) != 0);
1366
1367         case EXPR_BNOT:
1368             return !GetExprVal (Expr->Left);
1369
1370         case EXPR_ULABEL:
1371             Internal ("GetExprVal called for EXPR_ULABEL");
1372             /* NOTREACHED */
1373             return 0;
1374
1375         default:
1376             Internal ("Unknown Op type: %u", Expr->Op);
1377             /* NOTREACHED */
1378             return 0;
1379     }
1380 }
1381
1382
1383
1384 static ExprNode* RemoveSyms (ExprNode* Expr, int MustClone)
1385 /* Remove resolved symbols from the tree by cloning symbol expressions */
1386 {
1387     /* Accept NULL pointers */
1388     if (Expr == 0) {
1389         return 0;
1390     }
1391
1392     /* Special node handling */
1393     switch (Expr->Op) {
1394
1395         case EXPR_SYMBOL:
1396             if (SymHasExpr (Expr->V.Sym)) {
1397                 /* The symbol has an expression tree */
1398                 SymEntry* Sym = Expr->V.Sym;
1399                 if (SymHasUserMark (Sym)) {
1400                     /* Circular definition */
1401                     if (Verbosity) {
1402                         DumpExpr (Expr);
1403                     }
1404                     PError (GetSymPos (Sym), ERR_CIRCULAR_REFERENCE);
1405                     return GenLiteralExpr (0);          /* Return a dummy value */
1406                 }
1407                 SymMarkUser (Sym);
1408                 Expr = RemoveSyms (GetSymExpr (Sym), 1);
1409                 SymUnmarkUser (Sym);
1410                 return Expr;
1411             } else if (SymIsConst (Expr->V.Sym)) {
1412                 /* The symbol is a constant */
1413                 return GenLiteralExpr (GetSymVal (Expr->V.Sym));
1414             }
1415             break;
1416
1417         case EXPR_ULABEL:
1418             if (ULabCanResolve ()) {
1419                 ExprNode* NewExpr = ULabResolve (Expr->V.Val);
1420                 FreeExpr (Expr);
1421                 Expr = NewExpr;
1422             }
1423             break;
1424
1425     }
1426
1427     /* Clone the current node if needed */
1428     if (MustClone) {
1429
1430         /* Create a new node */
1431         ExprNode* Clone = NewExprNode ();
1432
1433         /* Clone the operation */
1434         Clone->Op = Expr->Op;
1435
1436         /* Clone the attribute if needed */
1437         switch (Expr->Op) {
1438
1439             case EXPR_LITERAL:
1440             case EXPR_ULABEL:
1441                 Clone->V.Val = Expr->V.Val;
1442                 break;
1443
1444             case EXPR_SYMBOL:
1445                 Clone->V.Sym = Expr->V.Sym;
1446                 break;
1447
1448             case EXPR_SECTION:
1449                 Clone->V.SegNum = Expr->V.SegNum;
1450                 break;
1451
1452         }
1453
1454         /* Clone the tree nodes */
1455         Clone->Left = RemoveSyms (Expr->Left, MustClone);
1456         Clone->Right = RemoveSyms (Expr->Right, MustClone);
1457
1458         /* Done */
1459         return Clone;
1460
1461     } else {
1462
1463         /* Nothing to clone */
1464         Expr->Left = RemoveSyms (Expr->Left, MustClone);
1465         Expr->Right = RemoveSyms (Expr->Right, MustClone);
1466
1467         /* Done */
1468         return Expr;
1469
1470     }
1471 }
1472
1473
1474
1475 static ExprNode* ConstExtract (ExprNode* Expr, long* Val, int Sign)
1476 /* Extract and evaluate all constant factors in an subtree that has only
1477  * additions and subtractions.
1478  */
1479 {
1480     if (Expr->Op == EXPR_LITERAL) {
1481         if (Sign < 0) {
1482             *Val -= Expr->V.Val;
1483         } else {
1484             *Val += Expr->V.Val;
1485         }
1486         FreeExprNode (Expr);
1487         return 0;
1488     }
1489
1490     if (Expr->Op == EXPR_PLUS || Expr->Op == EXPR_MINUS) {
1491         ExprNode* Left;
1492         ExprNode* Right;
1493         Left = ConstExtract (Expr->Left, Val, Sign);
1494         if (Expr->Op == EXPR_MINUS) {
1495             Sign = -Sign;
1496         }
1497         Right = ConstExtract (Expr->Right, Val, Sign);
1498         if (Left == 0 && Right == 0) {
1499             FreeExprNode (Expr);
1500             return 0;
1501         } else if (Left == 0) {
1502             FreeExprNode (Expr);
1503             return Right;
1504         } else if (Right == 0) {
1505             FreeExprNode (Expr);
1506             return Left;
1507         } else {
1508             /* Check for SEG - SEG which is now possible */
1509             if (Left->Op == EXPR_SECTION && Right->Op == EXPR_SECTION &&
1510                 Left->V.SegNum == Right->V.SegNum) {
1511                 /* SEG - SEG, remove it completely */
1512                 FreeExprNode (Left);
1513                 FreeExprNode (Right);
1514                 FreeExprNode (Expr);
1515                 return 0;
1516             } else {
1517                 Expr->Left  = Left;
1518                 Expr->Right = Right;
1519                 return Expr;
1520             }
1521         }
1522     }
1523
1524     /* Some other sort of node, finalize the terms */
1525     if (Expr->Left) {
1526         Expr->Left = FinalizeExpr (Expr->Left);
1527     }
1528     if (Expr->Right) {
1529         Expr->Right = FinalizeExpr (Expr->Right);
1530     }
1531
1532     return Expr;
1533 }
1534
1535
1536
1537 ExprNode* FinalizeExpr (ExprNode* Expr)
1538 /* Resolve any symbols by cloning the symbol expression tree instead of the
1539  * symbol reference, then try to simplify the expression as much as possible.
1540  * This function must only be called if all symbols are resolved (no undefined
1541  * symbol errors).
1542  */
1543 {
1544     long Val = 0;
1545     ExprNode* N;
1546
1547     Expr = RemoveSyms (Expr, 0);
1548     Expr = ConstExtract (Expr, &Val, 1);
1549     if (Expr == 0) {
1550         /* Reduced to a literal value */
1551         Expr = GenLiteralExpr (Val);
1552     } else if (Val) {
1553         /* Extracted a value */
1554         N = NewExprNode ();
1555         N->Op = EXPR_PLUS;
1556         N->Left = Expr;
1557         N->Right = GenLiteralExpr (Val);
1558         Expr = N;
1559     }
1560     return Expr;
1561 }
1562
1563
1564
1565 ExprNode* CloneExpr (ExprNode* Expr)
1566 /* Clone the given expression tree. The function will simply clone symbol
1567  * nodes, it will not resolve them.
1568  */
1569 {
1570     ExprNode* Clone;
1571
1572     /* Accept NULL pointers */
1573     if (Expr == 0) {
1574         return 0;
1575     }
1576
1577     /* Get a new node */
1578     Clone = NewExprNode ();
1579
1580     /* Clone the operation */
1581     Clone->Op = Expr->Op;
1582
1583     /* Clone the attribute if needed */
1584     switch (Expr->Op) {
1585
1586         case EXPR_LITERAL:
1587         case EXPR_ULABEL:
1588             Clone->V.Val = Expr->V.Val;
1589             break;
1590
1591         case EXPR_SYMBOL:
1592             Clone->V.Sym = Expr->V.Sym;
1593             break;
1594
1595         case EXPR_SECTION:
1596             Clone->V.SegNum = Expr->V.SegNum;
1597             break;
1598
1599     }
1600
1601     /* Clone the tree nodes */
1602     Clone->Left = CloneExpr (Expr->Left);
1603     Clone->Right = CloneExpr (Expr->Right);
1604
1605     /* Done */
1606     return Clone;
1607 }
1608
1609
1610
1611 void WriteExpr (ExprNode* Expr)
1612 /* Write the given expression to the object file */
1613 {
1614     /* Null expressions are encoded by a type byte of zero */
1615     if (Expr == 0) {
1616         ObjWrite8 (0);
1617         return;
1618     }
1619
1620     /* Write the expression code */
1621     ObjWrite8 (Expr->Op);
1622
1623     /* If the is a leafnode, write the expression attribute, otherwise
1624      * write the expression operands.
1625      */
1626     switch (Expr->Op) {
1627
1628         case EXPR_LITERAL:
1629             ObjWrite32 (Expr->V.Val);
1630             break;
1631
1632         case EXPR_SYMBOL:
1633             /* Maybe we should use a code here? */
1634             CHECK (SymIsImport (Expr->V.Sym));  /* Safety */
1635             ObjWriteVar (GetSymIndex (Expr->V.Sym));
1636             break;
1637
1638         case EXPR_SECTION:
1639             ObjWrite8 (Expr->V.SegNum);
1640             break;
1641
1642         case EXPR_ULABEL:
1643             Internal ("WriteExpr: Cannot write EXPR_ULABEL nodes");
1644             break;
1645
1646         default:
1647             /* Not a leaf node */
1648             WriteExpr (Expr->Left);
1649             WriteExpr (Expr->Right);
1650             break;
1651
1652     }
1653 }
1654
1655
1656