modules/cldc-compact/src/main/java/cc/squirreljme/jvm/SoftLong.java

   1 // -*- Mode: Java; indent-tabs-mode: t; tab-width: 4 -*-
   2 // ---------------------------------------------------------------------------
   3 // SquirrelJME
   4 //     Copyright (C) Stephanie Gawroriski <xer@multiphasicapps.net>
   5 // ---------------------------------------------------------------------------
   6 // SquirrelJME is under the GNU General Public License v3+, or later.
   7 // See license.mkd for licensing and copyright information.
   8 // ---------------------------------------------------------------------------
   9
  10 package cc.squirreljme.jvm;
  11
  12 import cc.squirreljme.jvm.mle.MathShelf;
  13 import cc.squirreljme.runtime.cldc.annotation.SquirrelJMEVendorApi;
  14 import cc.squirreljme.runtime.cldc.debug.Debugging;
  15
  16 /**
  17  * Software math operations on 64-bit integer types.
  18  *
  19  * @since 2019/05/24
  20  */
  21 @SquirrelJMEVendorApi
  22 @SuppressWarnings("MagicNumber")
  23 public final class SoftLong
  24 {
  25         /**
  26          * Not used.
  27          *
  28          * @since 2019/05/24
  29          */
  30         private SoftLong()
  31         {
  32         }
  33
  34         /**
  35          * Adds two values.
  36          *
  37          * @param __al A low.
  38          * @param __ah A high.
  39          * @param __bl B low.
  40          * @param __bh B high.
  41          * @return The result.
  42          * @since 2019/05/24
  43          */
  44         @SquirrelJMEVendorApi
  45         public static long add(int __al, int __ah, int __bl, int __bh)
  46         {
  47                 // Add the higher/lower parts
  48                 int ch = __ah + __bh,
  49                         cl = __al + __bl;
  50
  51                 // If the low addition carried a bit over, then set that bit in the
  52                 // high part
  53                 if ((cl + 0x80000000) < (__al + 0x80000000))
  54                         ch++;
  55
  56                 // Return result
  57                 return MathShelf.longPack(cl, ch);
  58         }
  59
  60         /**
  61          * Ands two values.
  62          *
  63          * @param __al A low.
  64          * @param __ah A high.
  65          * @param __bl B low.
  66          * @param __bh B high.
  67          * @return The result.
  68          * @since 2019/05/24
  69          */
  70         @SquirrelJMEVendorApi
  71         public static long and(int __al, int __ah, int __bl, int __bh)
  72         {
  73                 return MathShelf.longPack(__al & __bl, __ah & __bh);
  74         }
  75
  76         /**
  77          * Compares two values.
  78          *
  79          * @param __al A low.
  80          * @param __ah A high.
  81          * @param __bl B low.
  82          * @param __bh B high.
  83          * @return The result.
  84          * @since 2019/05/24
  85          */
  86         @SquirrelJMEVendorApi
  87         public static int cmp(int __al, int __ah, int __bl, int __bh)
  88         {
  89                 // Compare high values firsts
  90                 if (__ah < __bh)
  91                         return -1;
  92                 else if (__ah > __bh)
  93                         return 1;
  94
  95                 // Compare low values with unsigned comparison
  96                 __al += Integer.MIN_VALUE;
  97                 __bl += Integer.MIN_VALUE;
  98                 if (__al < __bl)
  99                         return -1;
 100                 else if (__al > __bl)
 101                         return 1;
 102                 return 0;
 103         }
 104
 105         /**
 106          * Divides two values.
 107          *
 108          * @param __al A low.
 109          * @param __ah A high.
 110          * @param __bl B low.
 111          * @param __bh B high.
 112          * @return The result.
 113          * @since 2019/05/24
 114          */
 115         @SquirrelJMEVendorApi
 116         public static long div(int __al, int __ah, int __bl, int __bh)
 117         {
 118                 // Dividing by zero?
 119                 if (__bh == 0 && __bl == 0)
 120                         throw new ArithmeticException();
 121
 122                 return SoftLong.__div(false, __al, __ah, __bl, __bh);
 123         }
 124
 125         /**
 126          * Multiplies two long values.
 127          *
 128          * @param __al A low.
 129          * @param __ah A high.
 130          * @param __bl B low.
 131          * @param __bh B high.
 132          * @return The result.
 133          * @since 2019/05/24
 134          */
 135         @SquirrelJMEVendorApi
 136         public static long mul(int __al, int __ah, int __bl, int __bh)
 137         {
 138                 // Are both sides negative?
 139                 if (((__ah & __bh) & 0x8000_0000) != 0)
 140                 {
 141                         // Negate and check for overflow
 142                         __ah = (~__ah);
 143                         __al = (~__al + 1);
 144                         if (__al == 0)
 145                                 __ah++;
 146
 147                         // Negate and check for overflow
 148                         __bh = (~__bh);
 149                         __bl = (~__bl + 1);
 150                         if (__bl == 0)
 151                                 __bh++;
 152
 153                         // Return result
 154                         return SoftLong.__mul(__al, __ah, __bl, __bh);
 155                 }
 156
 157                 // Perform the calculation
 158                 return SoftLong.__mul(__al, __ah, __bl, __bh);
 159         }
 160
 161         /**
 162          * Negates a value.
 163          *
 164          * @param __al A low.
 165          * @param __ah A high.
 166          * @return The result.
 167          * @since 2019/05/24
 168          */
 169         @SquirrelJMEVendorApi
 170         public static long neg(int __al, int __ah)
 171         {
 172                 // Negate and check for overflow
 173                 __ah = (~__ah);
 174                 __al = (~__al + 1);
 175                 if (__al == 0)
 176                         __ah++;
 177
 178                 // Return result
 179                 return MathShelf.longPack(__al, __ah);
 180         }
 181
 182         /**
 183          * Ors a value.
 184          *
 185          * @param __al A low.
 186          * @param __ah A high.
 187          * @param __bl B low.
 188          * @param __bh B high.
 189          * @return The result.
 190          * @since 2019/05/24
 191          */
 192         @SquirrelJMEVendorApi
 193         public static long or(int __al, int __ah, int __bl, int __bh)
 194         {
 195                 return MathShelf.longPack(__al | __bl, __ah | __bh);
 196         }
 197
 198         /**
 199          * Remainders a value.
 200          *
 201          * @param __al A low.
 202          * @param __ah A high.
 203          * @param __bl B low.
 204          * @param __bh B high.
 205          * @return The result.
 206          * @since 2019/05/24
 207          */
 208         @SquirrelJMEVendorApi
 209         public static long rem(int __al, int __ah, int __bl, int __bh)
 210         {
 211                 // Dividing by zero?
 212                 if (__bh == 0 && __bl == 0)
 213                         throw new ArithmeticException();
 214
 215                 return SoftLong.__div(true, __al, __ah, __bl, __bh);
 216         }
 217
 218         /**
 219          * Shifts value left by bits.
 220          *
 221          * @param __al A low.
 222          * @param __ah A high.
 223          * @param __s Shift amount.
 224          * @return The result.
 225          * @since 2019/05/24
 226          */
 227         @SquirrelJMEVendorApi
 228         public static long shl(int __al, int __ah, int __s)
 229         {
 230                 // Mask the shift amount
 231                 __s &= 0x3F;
 232
 233                 // Doing nothing?
 234                 if (__s == 0)
 235                         return MathShelf.longPack(__al, __ah);
 236
 237                 // Shifting all the low bits to the high bits
 238                 else if (__s >= 32)
 239                         return MathShelf.longPack(0, __al << (__s - 32));
 240
 241                 // Merge of bits (shift in range of 1-31)
 242                 return MathShelf.longPack((__al << __s),
 243                         (__ah << __s) | (__al >>> (32 - __s)));
 244         }
 245
 246         /**
 247          * Shifts value right by bits.
 248          *
 249          * @param __al A low.
 250          * @param __ah A high.
 251          * @param __s Shift amount.
 252          * @return The result.
 253          * @since 2019/05/24
 254          */
 255         @SquirrelJMEVendorApi
 256         public static long shr(int __al, int __ah, int __s)
 257         {
 258                 // Mask the shift amount
 259                 __s &= 0x3F;
 260
 261                 // Doing nothing?
 262                 if (__s == 0)
 263                         return MathShelf.longPack(__al, __ah);
 264
 265                 // Shifting all the high bits low
 266                 else if (__s >= 32)
 267                         return MathShelf.longPack(__ah >> (__s - 32),
 268                                 (__ah & 0x80000000) >> 31);
 269
 270                 // Merge of bits (shift in range of 1-31)
 271                 return MathShelf.longPack((__ah << (32 - __s)) | (__al >>> __s),
 272                         (__ah >> __s));
 273         }
 274
 275         /**
 276          * Subtracts values.
 277          *
 278          * @param __al A low.
 279          * @param __ah A high.
 280          * @param __bl B low.
 281          * @param __bh B high.
 282          * @return The result.
 283          * @since 2019/05/24
 284          */
 285         @SquirrelJMEVendorApi
 286         public static long sub(int __al, int __ah, int __bl, int __bh)
 287         {
 288                 // The same as add, but the second operand is negated
 289                 // Negate and check for overflow
 290                 __bh = (~__bh);
 291                 __bl = (~__bl + 1);
 292                 if (__bl == 0)
 293                         __bh++;
 294
 295                 // Add the higher/lower parts
 296                 int ch = __ah + __bh;
 297                 int cl = __al + __bl;
 298
 299                 // If the low addition carried a bit over, then set that bit in the
 300                 // high part
 301                 if ((cl + 0x80000000) < (__al + 0x80000000))
 302                         ch++;
 303
 304                 // Return result
 305                 return MathShelf.longPack(cl, ch);
 306         }
 307
 308         /**
 309          * Converts to double.
 310          *
 311          * @param __al Low value.
 312          * @param __ah High value.
 313          * @return The result.
 314          * @since 2019/05/24
 315          */
 316         @SquirrelJMEVendorApi
 317         public static double toDouble(int __al, int __ah)
 318         {
 319                 throw Debugging.todo();
 320         }
 321
 322         /**
 323          * Converts to float.
 324          *
 325          * @param __al A low.
 326          * @param __ah A high.
 327          * @return The result.
 328          * @since 2019/05/24
 329          */
 330         @SquirrelJMEVendorApi
 331         public static float toFloat(int __al, int __ah)
 332         {
 333                 throw Debugging.todo();
 334         }
 335
 336         /**
 337          * Converts to integer.
 338          *
 339          * @param __al A low.
 340          * @param __ah A high.
 341          * @return The result.
 342          * @since 2019/05/24
 343          */
 344         @SquirrelJMEVendorApi
 345         public static int toInteger(int __al, @SuppressWarnings("unused") int __ah)
 346         {
 347                 // Just return the low order bits
 348                 return __al;
 349         }
 350
 351         /**
 352          * Shifts value bits right unsigned.
 353          *
 354          * @param __al A low.
 355          * @param __ah A high.
 356          * @param __s Shift amount.
 357          * @return The result.
 358          * @since 2019/05/24
 359          */
 360         @SquirrelJMEVendorApi
 361         public static long ushr(int __al, int __ah, int __s)
 362         {
 363                 // Mask the shift amount
 364                 __s &= 0x3F;
 365
 366                 // Doing nothing?
 367                 if (__s == 0)
 368                         return MathShelf.longPack(__al, __ah);
 369
 370                 // Shifting all the high bits low
 371                 else if (__s >= 32)
 372                         return MathShelf.longPack(__ah >>> (__s - 32), 0);
 373
 374                 // Merge of bits (shift in range of 1-31)
 375                 return MathShelf.longPack((__ah << (32 - __s)) | (__al >>> __s),
 376                         (__ah >>> __s));
 377         }
 378
 379         /**
 380          * Xors two values.
 381          *
 382          * @param __al A low.
 383          * @param __ah A high.
 384          * @param __bl B low.
 385          * @param __bh B high.
 386          * @return The result.
 387          * @since 2019/05/24
 388          */
 389         @SquirrelJMEVendorApi
 390         public static long xor(int __al, int __ah, int __bl, int __bh)
 391         {
 392                 return MathShelf.longPack(__al ^ __bl, __ah ^ __bh);
 393         }
 394
 395         /**
 396          * Divides and remainders two values.
 397          *
 398          * @param __doRem Return the remainder?
 399          * @param __nl The numerator, low.
 400          * @param __nh The numerator, high.
 401          * @param __dl The denominator, low.
 402          * @param __dh The denominator, high.
 403          * @return The result.
 404          * @since 2019/05/24
 405          */
 406         @SuppressWarnings("CommentedOutCode")
 407         private static long __div(boolean __doRem, int __nl, int __nh,
 408                 int __dl, int __dh)
 409         {
 410                 // {@squirreljme.error ZZ4z Divide by zero.}
 411                 if (__dl == 0 && __dh == 0)
 412                         throw new ArithmeticException("ZZ4z");
 413
 414                 // Wikipedia (http://en.wikipedia.org/wiki/Division_%28digital%29)
 415                 // if D == 0 then throw DivisionByZeroException end
 416                 // Q := 0 # initialize quotient and remainder to zero
 417                 // R := 0
 418                 // for i = n-1...0 do  # " where n is no of bits "
 419                 //   R := R << 1       # left-shift R by 1 bit
 420                 //   R(0) := N(i)      # set the least-significant bit
 421                 //              # of R equal to bit i of the numerator
 422                 //   if R >= D then
 423                 //     R = R - D
 424                 //     Q(i) := 1
 425                 //   end
 426                 // end
 427                 // long qx = 0, rx = 0;
 428
 429                 // High and low resultant values
 430                 int ql = 0;
 431                 int qh = 0;
 432                 int rl = 0;
 433                 int rh = 0;
 434
 435                 // Disallow division by zero
 436                 if (__dl == 0)
 437                         return 0;
 438
 439                 // Results in a negative? Only results in such if either side is
 440                 // a negative value
 441                 boolean negNum = ((__nh & 0x8000_0000) != 0);
 442                 boolean negDem = ((__dh & 0x8000_0000) != 0);
 443                 boolean isNeg = (negNum != negDem);
 444
 445                 // Make the numerator positive, if negative
 446                 if (negNum)
 447                 {
 448                         // Negate and check for overflow
 449                         __nh = (~__nh);
 450                         __nl = (~__nl + 1);
 451                         if (__nl == 0)
 452                                 __nh++;
 453                 }
 454
 455                 // Make the denominator positive, if negative
 456                 if (negDem)
 457                 {
 458                         // Negate and check for overflow
 459                         __dh = (~__dh);
 460                         __dl = (~__dl + 1);
 461                         if (__dl == 0)
 462                                 __dh++;
 463                 }
 464
 465                 // __dl and __dh for unsigned compare
 466                 int dlUnsigned = __dl + Integer.MIN_VALUE;
 467                 int dhUnsigned = __dh + Integer.MIN_VALUE;
 468
 469                 // Perform Math
 470                 for (int i = 63, hMask = 0xFFFF_FFFF, lMask = 0;
 471                         i >= 0;
 472                         i--, hMask >>>= 1, lMask = ((lMask >> 1) | 0x8000_0000))
 473                 {
 474                         // rx <<= 1;
 475                         // rx &= 0xFFFFFFFFFFFFFFFEL;
 476                         rh <<= 1;
 477                         rh |= (rl >>> 31);
 478                         rl <<= 1;
 479
 480                         // rx |= ((__nx >>> i) & 1L); ... only take the lowest bit!
 481                         // branching:
 482                         // ! if (i >= 32)
 483                         // !     rl |= ((__nh >>> (i - 32)) & 0x1);
 484                         // ! else
 485                         // !     rl |= ((__nl >>> i) & 0x1);
 486                         // faster using masking:
 487                         // ! rl |= (((__nh & hMask) >>> i) & 0x1);
 488                         // ! rl |= (((__nl & lMask) >>> i) & 0x1);
 489                         rl |= ((((__nh & hMask) | (__nl & lMask)) >>> i) & 0x1);
 490
 491                         // Unsigned comparison (shift by 0x8000_0000__0000_0000L)
 492                         // if ((rx + Long.MIN_VALUE) >= (__dx + Long.MIN_VALUE))
 493                         /*if (SoftLong.cmp(rl, rh + Integer.MIN_VALUE,
 494                                 __dl, __dh + Integer.MIN_VALUE) >= 0)*/
 495                         int cmp = (rh + Integer.MIN_VALUE) - dhUnsigned;
 496                         if (cmp >= 0 &&
 497                                 (cmp > 0 ||     // Is just a bigger number overall?
 498                                 rl + Integer.MIN_VALUE >= dlUnsigned))
 499                         {
 500                                 // rx -= __dx;
 501                                 // The same as add, but the second operand is negated
 502                                 // Negate and check for overflow
 503                                 int bh = (~__dh);
 504                                 int bl = (~__dl + 1);
 505                                 if (bl == 0)
 506                                         bh++;
 507
 508                                 // Add the higher/lower parts
 509                                 rh = rh + bh;
 510                                 int cl = rl + bl;
 511
 512                                 // If the low addition carried a bit over, then set that bit in
 513                                 // the high part
 514                                 if ((cl + 0x80000000) < (rl + 0x80000000))
 515                                         rh++;
 516
 517                                 // Use result
 518                                 rl = cl;
 519
 520                                 // qx |= (1L << i);
 521                                 if (i >= 32)
 522                                         qh |= (1 << (i - 32));
 523                                 else
 524                                         ql |= (1 << i);
 525                         }
 526                 }
 527
 528                 // Return the remainder if needed, note the remainder is negative only
 529                 // if the numerator is negative
 530                 if (__doRem)
 531                         return (negNum ? SoftLong.neg(rl, rh) :
 532                                 MathShelf.longPack(rl, rh));
 533
 534                 // Return, normalize negative if needed
 535                 return (isNeg ? SoftLong.neg(ql, qh) : MathShelf.longPack(ql, qh));
 536         }
 537
 538         /**
 539          * Multiplies two long values, note that this will fail if both A and B
 540          * are negative. The values must either be both positive or only one is
 541          * negative.
 542          *
 543          * @param __al A low.
 544          * @param __ah A high.
 545          * @param __bl B low.
 546          * @param __bh B high.
 547          * @return The result.
 548          * @since 2019/05/24
 549          */
 550         private static long __mul(int __al, int __ah, int __bl, int __bh)
 551         {
 552                 // First value
 553                 int a = (__ah >>> 16);
 554                 int b = (__ah & 0xFFFF);
 555                 int c = (__al >>> 16);
 556                 int d = (__al & 0xFFFF);
 557
 558                 // Second value
 559                 int w = (__bh >>> 16);
 560                 int x = (__bh & 0xFFFF);
 561                 int y = (__bl >>> 16);
 562                 int z = (__bl & 0xFFFF);
 563
 564                 // Effectively this is long multiplication
 565                 // Multiplication in two's complement form is the same in both
 566                 // signed and unsigned, so we need not worry about signs and just treat
 567                 // this all as unsigned. Each fragment is 16 of the 64 bits.
 568                 //             |  a.  b,  c.  d
 569                 // *           |  w.  x,  y.  z
 570                 // ============|===.===,===.===
 571                 //             |d_w.d_x,d_y.d_z
 572                 //          c_w|c_x.c_y,c_z.
 573                 //      b_w b_x|b_y.b_z,   .
 574                 //  a_w a_x a_y|a_z.   ,   .
 575                 // ============|===.===,===.===
 576                 //  DISCARD       m.  n,  o.  p
 577
 578                 // Overflow storage, since we want a temporary and we do not want to
 579                 // make any allocations or otherwise for 64-bit values. This keeps it
 580                 // all in 32-bit and handles the various situations.
 581                 int over;
 582
 583                 // Multiply and add all the parts together
 584                 // int p = (d * z);
 585                 int p = (d * z);
 586                 over = (p >>> 16);
 587
 588                 // int o = (d * y) + (c * z) + (p >>> 16);
 589                 int o = over + (d * y);
 590                 over = (o >>> 16);
 591                 o = (o & 0xFFFF) + (c * z);
 592                 over += (o >>> 16);
 593
 594                 // int n = (d * x) + (c * y) + (b * z) + (o >>> 16);
 595                 int n = over + (d * x);
 596                 over = (n >>> 16);
 597                 n = (n & 0xFFFF) + (c * y);
 598                 over += (n >>> 16);
 599                 n = (n & 0xFFFF) + (b * z);
 600                 over += (n >>> 16);
 601
 602                 // int m = (d * w) + (c * x) + (b * y) + (a * z) + (n >>> 16);
 603                 // We need not care about overflow here, because it will all be
 604                 // discarded anyway!
 605                 int m = over + (d * w) + (c * x) + (b * y) + (a * z);
 606
 607                 // Combine the resultant parts
 608                 return MathShelf.longPack((o << 16) | (p & 0xFFFF),
 609                         (m << 16) | (n & 0xFFFF));
 610         }
 611 }
 612