verinum.cc

   1 /*
   2  * Copyright (c) 1998-2008 Stephen Williams (steve@icarus.com)
   3  *
   4  *    This source code is free software; you can redistribute it
   5  *    and/or modify it in source code form under the terms of the GNU
   6  *    General Public License as published by the Free Software
   7  *    Foundation; either version 2 of the License, or (at your option)
   8  *    any later version.
   9  *
  10  *    This program is distributed in the hope that it will be useful,
  11  *    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  *    GNU General Public License for more details.
  14  *
  15  *    You should have received a copy of the GNU General Public License
  16  *    along with this program; if not, write to the Free Software
  17  *    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
  18  */
  19
  20 # include "config.h"
  21
  22 # include  "verinum.h"
  23 # include  <iostream>
  24 # include  <cassert>
  25 # include  <math.h> // Needed to get pow for as_double().
  26
  27 static verinum::V add_with_carry(verinum::V l, verinum::V r, verinum::V&c);
  28
  29 verinum::verinum()
  30 : bits_(0), nbits_(0), has_len_(false), has_sign_(false), string_flag_(false)
  31 {
  32 }
  33
  34 verinum::verinum(const V*bits, unsigned nbits, bool has_len)
  35 : has_len_(has_len), has_sign_(false), string_flag_(false)
  36 {
  37       nbits_ = nbits;
  38       bits_ = new V [nbits];
  39       for (unsigned idx = 0 ;  idx < nbits ;  idx += 1) {
  40             bits_[idx] = bits[idx];
  41       }
  42 }
  43
  44 static string process_verilog_string_quotes(const string&str)
  45 {
  46       string res;
  47
  48       int idx = 0;
  49       int str_len = str.length();
  50
  51       while (idx < str_len) {
  52             if (str[idx] == '\\') {
  53                   idx += 1;
  54                   assert(idx < str_len);
  55                   switch (str[idx]) {
  56                       case 'n':
  57                         res = res + '\n';
  58                         idx += 1;
  59                         break;
  60                       case 't':
  61                         res = res + '\t';
  62                         idx += 1;
  63                         break;
  64                       case '0':
  65                       case '1':
  66                       case '2':
  67                       case '3':
  68                       case '4':
  69                       case '5':
  70                       case '6':
  71                       case '7': {
  72                             char byte_val = 0;
  73                             int odx = 0;
  74                             while (odx < 3 && idx+odx < str_len
  75                                    && str[idx+odx] >= '0'
  76                                    && str[idx+odx] <= '7') {
  77                                   byte_val = 8*byte_val + str[idx+odx]-'0';
  78                                   odx += 1;
  79                             }
  80                             idx += odx;
  81                             res = res + byte_val;
  82                             break;
  83                       }
  84                       default:
  85                         res = res + str[idx];
  86                         idx += 1;
  87                         break;
  88                   }
  89             } else {
  90                   res = res + str[idx];
  91                   idx += 1;
  92             }
  93       }
  94       return res;
  95 }
  96
  97 verinum::verinum(const string&s)
  98 : has_len_(true), has_sign_(false), string_flag_(true)
  99 {
 100       string str = process_verilog_string_quotes(s);
 101       nbits_ = str.length() * 8;
 102
 103         // Special case: The string "" is 8 bits of 0.
 104       if (nbits_ == 0) {
 105             nbits_ = 8;
 106             bits_ = new V [nbits_];
 107             bits_[0] = V0;
 108             bits_[1] = V0;
 109             bits_[2] = V0;
 110             bits_[3] = V0;
 111             bits_[4] = V0;
 112             bits_[5] = V0;
 113             bits_[6] = V0;
 114             bits_[7] = V0;
 115             return;
 116       }
 117
 118       bits_ = new V [nbits_];
 119
 120       unsigned idx, cp;
 121       V*bp = bits_+nbits_;
 122       for (idx = nbits_, cp = 0 ;  idx > 0 ;  idx -= 8, cp += 1) {
 123             char ch = str[cp];
 124             *(--bp) = (ch&0x80) ? V1 : V0;
 125             *(--bp) = (ch&0x40) ? V1 : V0;
 126             *(--bp) = (ch&0x20) ? V1 : V0;
 127             *(--bp) = (ch&0x10) ? V1 : V0;
 128             *(--bp) = (ch&0x08) ? V1 : V0;
 129             *(--bp) = (ch&0x04) ? V1 : V0;
 130             *(--bp) = (ch&0x02) ? V1 : V0;
 131             *(--bp) = (ch&0x01) ? V1 : V0;
 132       }
 133 }
 134
 135 verinum::verinum(verinum::V val, unsigned n, bool h)
 136 : has_len_(h), has_sign_(false), string_flag_(false)
 137 {
 138       nbits_ = n;
 139       bits_ = new V[nbits_];
 140       for (unsigned idx = 0 ;  idx < nbits_ ;  idx += 1)
 141             bits_[idx] = val;
 142 }
 143
 144 verinum::verinum(uint64_t val, unsigned n)
 145 : has_len_(true), has_sign_(false), string_flag_(false)
 146 {
 147       nbits_ = n;
 148       bits_ = new V[nbits_];
 149       for (unsigned idx = 0 ;  idx < nbits_ ;  idx += 1) {
 150             bits_[idx] = (val&1) ? V1 : V0;
 151             val >>= (uint64_t)1;
 152       }
 153 }
 154
 155 verinum::verinum(const verinum&that)
 156 {
 157       string_flag_ = that.string_flag_;
 158       nbits_ = that.nbits_;
 159       bits_ = new V[nbits_];
 160       has_len_ = that.has_len_;
 161       has_sign_ = that.has_sign_;
 162       for (unsigned idx = 0 ;  idx < nbits_ ;  idx += 1)
 163             bits_[idx] = that.bits_[idx];
 164 }
 165
 166 verinum::verinum(const verinum&that, unsigned nbits)
 167 {
 168       string_flag_ = false;
 169       nbits_ = nbits;
 170       bits_ = new V[nbits_];
 171       has_len_ = true;
 172       has_sign_ = that.has_sign_;
 173
 174       unsigned copy = nbits;
 175       if (copy > that.nbits_)
 176             copy = that.nbits_;
 177       for (unsigned idx = 0 ;  idx < copy ;  idx += 1)
 178             bits_[idx] = that.bits_[idx];
 179
 180       if (copy < nbits_) {
 181             if (has_sign_) {
 182                   for (unsigned idx = copy ;  idx < nbits_ ;  idx += 1)
 183                         bits_[idx] = bits_[idx-1];
 184             } else {
 185                   for (unsigned idx = copy ;  idx < nbits_ ;  idx += 1)
 186                         bits_[idx] = verinum::V0;
 187             }
 188       }
 189 }
 190
 191 verinum::verinum(int64_t that)
 192 : has_len_(false), has_sign_(true), string_flag_(false)
 193 {
 194       int64_t tmp;
 195
 196       tmp = that/2;
 197       nbits_ = 1;
 198       while ((tmp != 0) && (tmp != -1)) {
 199             nbits_ += 1;
 200             tmp /= 2;
 201       }
 202
 203       nbits_ += 1;
 204
 205       bits_ = new V[nbits_];
 206       for (unsigned idx = 0 ;  idx < nbits_ ;  idx += 1) {
 207             bits_[idx] = (that & 1)? V1 : V0;
 208             that /= 2;
 209       }
 210 }
 211
 212 verinum::~verinum()
 213 {
 214       delete[]bits_;
 215 }
 216
 217 verinum& verinum::operator= (const verinum&that)
 218 {
 219       if (this == &that) return *this;
 220       delete[]bits_;
 221       nbits_ = that.nbits_;
 222       bits_ = new V[that.nbits_];
 223       for (unsigned idx = 0 ;  idx < nbits_ ;  idx += 1)
 224             bits_[idx] = that.bits_[idx];
 225
 226       has_len_ = that.has_len_;
 227       has_sign_ = that.has_sign_;
 228       string_flag_ = that.string_flag_;
 229       return *this;
 230 }
 231
 232 verinum::V verinum::get(unsigned idx) const
 233 {
 234       assert(idx < nbits_);
 235       return bits_[idx];
 236 }
 237
 238 verinum::V verinum::set(unsigned idx, verinum::V val)
 239 {
 240       assert(idx < nbits_);
 241       return bits_[idx] = val;
 242 }
 243
 244 unsigned long verinum::as_ulong() const
 245 {
 246       if (nbits_ == 0)
 247             return 0;
 248
 249       if (!is_defined())
 250             return 0;
 251
 252       unsigned top = nbits_;
 253       if (top >= (8 * sizeof(unsigned long)))
 254           top = 8 * sizeof(unsigned long);
 255
 256       unsigned long val = 0;
 257       unsigned long mask = 1;
 258       for (unsigned idx = 0 ;  idx < top ;  idx += 1, mask <<= 1)
 259             if (bits_[idx] == V1)
 260                   val |= mask;
 261
 262       return val;
 263 }
 264
 265 uint64_t verinum::as_ulong64() const
 266 {
 267       if (nbits_ == 0)
 268             return 0;
 269
 270       if (!is_defined())
 271             return 0;
 272
 273       unsigned top = nbits_;
 274       if (top >= (8 * sizeof(uint64_t)))
 275           top = 8 * sizeof(uint64_t);
 276
 277       uint64_t val = 0;
 278       uint64_t mask = 1;
 279       for (unsigned idx = 0 ;  idx < top ;  idx += 1, mask <<= 1)
 280             if (bits_[idx] == V1)
 281                   val |= mask;
 282
 283       return val;
 284 }
 285
 286 /*
 287  * This function returns the native long integer that represents the
 288  * value of this object. It accounts for sign extension if the value
 289  * is signed.
 290  *
 291  * If the value is undefined, return 0.
 292  *
 293  * This function presumes that the native format is 2s complement
 294  * (pretty safe these days) and masks/sets bits accordingly. If the
 295  * value is too large for the native form, it truncates the high bits.
 296  */
 297 signed long verinum::as_long() const
 298 {
 299       if (nbits_ == 0)
 300             return 0;
 301
 302       if (!is_defined())
 303             return 0;
 304
 305       signed long val = 0;
 306
 307       if (has_sign_ && (bits_[nbits_-1] == V1)) {
 308             unsigned top = nbits_;
 309             if (top > (8 * sizeof(long) - 1))
 310                   top = 8 * sizeof(long) - 1;
 311
 312             val = -1;
 313             signed long mask = ~1L;
 314             for (unsigned idx = 0 ;  idx < top ;  idx += 1) {
 315                   if (bits_[idx] == V0)
 316                         val &= mask;
 317
 318                   mask = (mask << 1) | 1L;
 319             }
 320
 321       } else {
 322             unsigned top = nbits_;
 323             if (top > (8 * sizeof(long) - 1))
 324                   top = 8 * sizeof(long) - 1;
 325
 326             signed long mask = 1;
 327             for (unsigned idx = 0 ;  idx < top ;  idx += 1, mask <<= 1)
 328                   if (bits_[idx] == V1)
 329                         val |= mask;
 330       }
 331
 332       return val;
 333 }
 334
 335 double verinum::as_double() const
 336 {
 337       if (nbits_ == 0) return 0.0;
 338
 339         /* Do we have a signed value? */
 340       bool signed_flag = false;
 341       if (bits_[nbits_-1] == V1) {
 342             signed_flag = true;
 343       }
 344
 345       double val = 0.0;
 346       if (signed_flag) {
 347             V carry = V1;
 348             for (unsigned idx = 0; idx < nbits_; idx += 1) {
 349                   V sum = add_with_carry(~bits_[idx], V0, carry);
 350                   if (sum == V1)
 351                         val += pow(2.0, (double)idx);
 352             }
 353             val *= -1.0;
 354 //          val = (double) as_long();
 355       } else {
 356             for (unsigned idx = 0; idx < nbits_; idx += 1) {
 357                   if (bits_[idx] == V1)
 358                         val += pow(2.0, (double)idx);
 359             }
 360       }
 361       return val;
 362 }
 363
 364 string verinum::as_string() const
 365 {
 366       assert( nbits_%8 == 0 );
 367       if (nbits_ == 0)
 368             return "";
 369
 370       string res;
 371       bool leading_nuls = true;
 372       for (unsigned idx = nbits_ ;  idx > 0 ;  idx -= 8) {
 373             char char_val = 0;
 374             V*bp = bits_+idx;
 375
 376             if (*(--bp) == V1) char_val |= 0x80;
 377             if (*(--bp) == V1) char_val |= 0x40;
 378             if (*(--bp) == V1) char_val |= 0x20;
 379             if (*(--bp) == V1) char_val |= 0x10;
 380             if (*(--bp) == V1) char_val |= 0x08;
 381             if (*(--bp) == V1) char_val |= 0x04;
 382             if (*(--bp) == V1) char_val |= 0x02;
 383             if (*(--bp) == V1) char_val |= 0x01;
 384             if (char_val == 0 && leading_nuls)
 385                   continue;
 386
 387             if (char_val == '"' || char_val == '\\') {
 388                   char tmp[5];
 389                   snprintf(tmp, sizeof tmp, "\\\%03o", char_val);
 390                   res = res + tmp;
 391             } else if (char_val == ' ' || isgraph(char_val)) {
 392                   res = res + char_val;
 393
 394             } else {
 395                   char tmp[5];
 396                   snprintf(tmp, sizeof tmp, "\\\%03o", char_val);
 397                   res = res + tmp;
 398             }
 399       }
 400       return res;
 401 }
 402
 403 bool verinum::is_before(const verinum&that) const
 404 {
 405       if (that.nbits_ > nbits_) return true;
 406       if (that.nbits_ < nbits_) return false;
 407
 408       for (unsigned idx = nbits_  ;  idx > 0 ;  idx -= 1) {
 409             if (bits_[idx-1] < that.bits_[idx-1]) return true;
 410             if (bits_[idx-1] > that.bits_[idx-1]) return false;
 411       }
 412       return false;
 413 }
 414
 415 bool verinum::is_defined() const
 416 {
 417       for (unsigned idx = 0 ;  idx < nbits_ ;  idx += 1) {
 418             if (bits_[idx] == Vx) return false;
 419             if (bits_[idx] == Vz) return false;
 420       }
 421       return true;
 422 }
 423
 424 bool verinum::is_zero() const
 425 {
 426       for (unsigned idx = 0 ;  idx < nbits_ ;  idx += 1)
 427             if (bits_[idx] != V0) return false;
 428
 429       return true;
 430 }
 431
 432 bool verinum::is_negative() const
 433 {
 434       return (bits_[nbits_-1] == V1) && has_sign();
 435 }
 436
 437 verinum pad_to_width(const verinum&that, unsigned width)
 438 {
 439       if (that.len() >= width)
 440             return that;
 441
 442       if (that.len() == 0) {
 443             verinum val (verinum::V0, width, that.has_len());
 444             val.has_sign(that.has_sign());
 445             return val;
 446       }
 447
 448       verinum::V pad = that[that.len()-1];
 449       if (pad==verinum::V1 && !that.has_sign())
 450             pad = verinum::V0;
 451       if (that.has_len() && !that.has_sign()) {
 452             if (pad==verinum::Vx)
 453                   pad = verinum::V0;
 454             if (pad==verinum::Vz)
 455                   pad = verinum::V0;
 456       }
 457
 458       verinum val(pad, width, that.has_len());
 459
 460       for (unsigned idx = 0 ;  idx < that.len() ;  idx += 1)
 461             val.set(idx, that[idx]);
 462
 463       val.has_sign(that.has_sign());
 464       return val;
 465 }
 466
 467 /*
 468  * This function returns a version of the verinum that has only as
 469  * many bits as are needed to accurately represent the value. It takes
 470  * into account the signedness of the value.
 471  *
 472  * If the input value has a definite length, then that value is just
 473  * returned as is.
 474  */
 475 verinum trim_vnum(const verinum&that)
 476 {
 477       unsigned tlen;
 478
 479       if (that.has_len())
 480             return that;
 481
 482       if (that.len() < 2)
 483             return that;
 484
 485       if (that.has_sign()) {
 486             unsigned top = that.len()-1;
 487             verinum::V sign = that.get(top);
 488
 489             while ((top > 0) && (that.get(top) == sign))
 490                   top -= 1;
 491
 492               /* top points to the first digit that is not the
 493                  sign. Set the length to include this and one proper
 494                  sign bit. */
 495
 496             if (that.get(top) != sign)
 497                   top += 1;
 498
 499             tlen = top+1;
 500
 501       } else {
 502
 503               /* If the result is unsigned and has an indefinite
 504                  length, then trim off all but one leading zero. */
 505             unsigned top = that.len()-1;
 506             while ((top > 0) && (that.get(top) == verinum::V0))
 507                   top -= 1;
 508
 509               /* Now top is the index of the highest non-zero bit. If
 510                  that turns out to the highest bit in the vector, then
 511                  tere is no trimming possible. */
 512             if (top+1 == that.len())
 513                   return that;
 514
 515               /* Make tlen wide enough to include the highest non-zero
 516                  bit, plus one extra 0 bit. */
 517             tlen = top+2;
 518
 519               /* This can only happen when the verinum is all zeros,
 520                  so make it a single bit wide. */
 521             if (that.get(top) == verinum::V0) tlen -= 1;
 522       }
 523
 524       verinum tmp (verinum::V0, tlen, false);
 525       tmp.has_sign(that.has_sign());
 526       for (unsigned idx = 0 ;  idx < tmp.len() ;  idx += 1)
 527             tmp.set(idx, that.get(idx));
 528
 529       return tmp;
 530 }
 531
 532 ostream& operator<< (ostream&o, verinum::V v)
 533 {
 534       switch (v) {
 535           case verinum::V0:
 536             o << "0";
 537             break;
 538           case verinum::V1:
 539             o << "1";
 540             break;
 541           case verinum::Vx:
 542             o << "x";
 543             break;
 544           case verinum::Vz:
 545             o << "z";
 546             break;
 547       }
 548       return o;
 549 }
 550
 551 /*
 552  * This operator is used by various dumpers to write the Verilog
 553  * number in a Verilog format.
 554  */
 555 ostream& operator<< (ostream&o, const verinum&v)
 556 {
 557       if (v.is_string()) {
 558             o << "\"" << v.as_string() << "\"";
 559             return o;
 560       }
 561
 562         /* If the verinum number has a fixed length, dump all the bits
 563            literally. This is how we express the fixed length in the
 564            output. */
 565       if (v.has_len()) {
 566             o << v.len();
 567       }
 568
 569         /* If the number is fully defined (no x or z) then print it
 570            out as a decimal number. */
 571       if (v.is_defined() && v.len() < 8*sizeof(long)) {
 572             if (v.has_sign())
 573                   o << "'sd" << v.as_long();
 574             else
 575                   o << "'d" << v.as_ulong();
 576             return o;
 577       }
 578
 579         /* Oh, well. Print the minimum to get the value properly
 580            displayed. */
 581       if (v.has_sign())
 582             o << "'sb";
 583       else
 584             o << "'b";
 585
 586       if (v.len() == 0) {
 587             o << "0";
 588             return o;
 589       }
 590
 591       verinum::V trim_left = v.get(v.len()-1);
 592       unsigned idx;
 593
 594       for (idx = v.len()-1;  idx > 0;  idx -= 1)
 595             if (trim_left != v.get(idx-1))
 596                   break;
 597
 598       o << trim_left;
 599
 600       while (idx > 0) {
 601             o << v.get(idx-1);
 602             idx -= 1;
 603       }
 604
 605       return o;
 606 }
 607
 608 verinum::V operator == (const verinum&left, const verinum&right)
 609 {
 610       if (left.len() != right.len())
 611             return verinum::V0;
 612
 613       for (unsigned idx = 0 ;  idx < left.len() ;  idx += 1)
 614             if (left[idx] != right[idx])
 615                   return verinum::V0;
 616
 617       return verinum::V1;
 618 }
 619
 620 verinum::V operator <= (const verinum&left, const verinum&right)
 621 {
 622       verinum::V left_pad = verinum::V0;
 623       verinum::V right_pad = verinum::V0;
 624       if (left.has_sign() && right.has_sign()) {
 625             left_pad = left.get(left.len()-1);
 626             right_pad = right.get(right.len()-1);
 627
 628             if (left_pad == verinum::V1 && right_pad == verinum::V0)
 629                   return verinum::V1;
 630             if (left_pad == verinum::V0 && right_pad == verinum::V1)
 631                   return verinum::V0;
 632       }
 633
 634       unsigned idx;
 635       for (idx = left.len() ; idx > right.len() ;  idx -= 1) {
 636             if (left[idx-1] != right_pad) return verinum::V0;
 637       }
 638
 639       for (idx = right.len() ; idx > left.len() ;  idx -= 1) {
 640             if (right[idx-1] != left_pad) return verinum::V1;
 641       }
 642
 643       idx = right.len();
 644       if (left.len() < idx) idx = left.len();
 645
 646       while (idx > 0) {
 647             if (left[idx-1] == verinum::Vx) return verinum::Vx;
 648             if (left[idx-1] == verinum::Vz) return verinum::Vx;
 649             if (right[idx-1] == verinum::Vx) return verinum::Vx;
 650             if (right[idx-1] == verinum::Vz) return verinum::Vx;
 651             if (left[idx-1] > right[idx-1]) return verinum::V0;
 652             if (left[idx-1] < right[idx-1]) return verinum::V1;
 653             idx -= 1;
 654       }
 655
 656       return verinum::V1;
 657 }
 658
 659 verinum::V operator < (const verinum&left, const verinum&right)
 660 {
 661       verinum::V left_pad = verinum::V0;
 662       verinum::V right_pad = verinum::V0;
 663       if (left.has_sign() && right.has_sign()) {
 664             left_pad = left.get(left.len()-1);
 665             right_pad = right.get(right.len()-1);
 666
 667             if (left_pad == verinum::V1 && right_pad == verinum::V0)
 668                   return verinum::V1;
 669             if (left_pad == verinum::V0 && right_pad == verinum::V1)
 670                   return verinum::V0;
 671       }
 672
 673       unsigned idx;
 674       for (idx = left.len() ; idx > right.len() ;  idx -= 1) {
 675             if (left[idx-1] != right_pad) return verinum::V0;
 676       }
 677
 678       for (idx = right.len() ; idx > left.len() ;  idx -= 1) {
 679             if (right[idx-1] != left_pad) return verinum::V1;
 680       }
 681
 682       while (idx > 0) {
 683             if (left[idx-1] == verinum::Vx) return verinum::Vx;
 684             if (left[idx-1] == verinum::Vz) return verinum::Vx;
 685             if (right[idx-1] == verinum::Vx) return verinum::Vx;
 686             if (right[idx-1] == verinum::Vz) return verinum::Vx;
 687             if (left[idx-1] > right[idx-1]) return verinum::V0;
 688             if (left[idx-1] < right[idx-1]) return verinum::V1;
 689             idx -= 1;
 690       }
 691
 692       return verinum::V0;
 693 }
 694
 695 static verinum::V add_with_carry(verinum::V l, verinum::V r, verinum::V&c)
 696 {
 697       unsigned sum = 0;
 698       switch (c) {
 699           case verinum::Vx:
 700           case verinum::Vz:
 701             c = verinum::Vx;
 702             return verinum::Vx;
 703           case verinum::V0:
 704             break;
 705           case verinum::V1:
 706             sum += 1;
 707       }
 708
 709       switch (l) {
 710           case verinum::Vx:
 711           case verinum::Vz:
 712             c = verinum::Vx;
 713             return verinum::Vx;
 714           case verinum::V0:
 715             break;
 716           case verinum::V1:
 717             sum += 1;
 718             break;
 719       }
 720
 721       switch (r) {
 722           case verinum::Vx:
 723           case verinum::Vz:
 724             c = verinum::Vx;
 725             return verinum::Vx;
 726           case verinum::V0:
 727             break;
 728           case verinum::V1:
 729             sum += 1;
 730             break;
 731       }
 732
 733       if (sum & 2)
 734             c = verinum::V1;
 735       else
 736             c = verinum::V0;
 737       if (sum & 1)
 738             return verinum::V1;
 739       else
 740             return verinum::V0;
 741 }
 742
 743 verinum v_not(const verinum&left)
 744 {
 745       verinum val = left;
 746       for (unsigned idx = 0 ;  idx < val.len() ;  idx += 1)
 747             switch (val[idx]) {
 748                 case verinum::V0:
 749                   val.set(idx, verinum::V1);
 750                   break;
 751                 case verinum::V1:
 752                   val.set(idx, verinum::V0);
 753                   break;
 754                 default:
 755                   val.set(idx, verinum::Vx);
 756                   break;
 757             }
 758
 759       return val;
 760 }
 761
 762 /*
 763  * Addition works a bit at a time, from the least significant up to
 764  * the most significant. The result is signed only if both of the
 765  * operands are signed. The result is also expanded as needed to
 766  * prevent overflow. It is up to the caller to shrink the result back
 767  * down if that is the desire.
 768  */
 769 verinum operator + (const verinum&left, const verinum&right)
 770 {
 771       unsigned min = left.len();
 772       if (right.len() < min) min = right.len();
 773
 774       unsigned max = left.len();
 775       if (right.len() > max) max = right.len();
 776
 777       bool signed_flag = left.has_sign() && right.has_sign();
 778       verinum::V*val_bits = new verinum::V[max+1];
 779
 780       verinum::V carry = verinum::V0;
 781       for (unsigned idx = 0 ;  idx < min ;  idx += 1)
 782             val_bits[idx] = add_with_carry(left[idx], right[idx], carry);
 783
 784       verinum::V rpad = signed_flag? right[right.len()-1] : verinum::V0;
 785       verinum::V lpad = signed_flag? left[left.len()-1]   : verinum::V0;
 786
 787       if (left.len() > right.len()) {
 788
 789             for (unsigned idx = min ;  idx < left.len() ;  idx += 1)
 790                   val_bits[idx] = add_with_carry(left[idx], rpad, carry);
 791
 792       } else {
 793
 794             for (unsigned idx = min ;  idx < right.len() ;  idx += 1)
 795                   val_bits[idx] = add_with_carry(lpad, right[idx], carry);
 796       }
 797
 798       val_bits[max] = add_with_carry(lpad, rpad, carry);
 799 #if 0
 800       if (signed_flag) {
 801             if (val_bits[max] != val_bits[max-1])
 802                   max += 1;
 803       }
 804 #endif
 805       verinum val (val_bits, max+1, false);
 806       val.has_sign(signed_flag);
 807
 808       delete[]val_bits;
 809
 810       return val;
 811 }
 812
 813 verinum operator - (const verinum&left, const verinum&right)
 814 {
 815       unsigned min = left.len();
 816       if (right.len() < min) min = right.len();
 817
 818       unsigned max = left.len();
 819       if (right.len() > max) max = right.len();
 820
 821       bool signed_flag = left.has_sign() && right.has_sign();
 822       verinum::V*val_bits = new verinum::V[max+1];
 823
 824       verinum::V carry = verinum::V1;
 825       for (unsigned idx = 0 ;  idx < min ;  idx += 1)
 826             val_bits[idx] = add_with_carry(left[idx], ~right[idx], carry);
 827
 828       verinum::V rpad = signed_flag? ~right[right.len()-1] : verinum::V1;
 829       verinum::V lpad = signed_flag?  left[left.len()-1]   : verinum::V0;
 830
 831       if (left.len() > right.len()) {
 832
 833             for (unsigned idx = min ;  idx < left.len() ;  idx += 1)
 834                   val_bits[idx] = add_with_carry(left[idx], rpad, carry);
 835
 836       } else {
 837
 838             for (unsigned idx = min ;  idx < right.len() ;  idx += 1)
 839                   val_bits[idx] = add_with_carry(lpad, ~right[idx], carry);
 840       }
 841
 842       if (signed_flag) {
 843             val_bits[max] = add_with_carry(lpad, rpad, carry);
 844             if (val_bits[max] != val_bits[max-1])
 845                   max += 1;
 846       }
 847
 848       verinum val (val_bits, max, false);
 849       val.has_sign(signed_flag);
 850
 851       delete[]val_bits;
 852
 853       return val;
 854 }
 855
 856 /*
 857  * This multiplies two verinum numbers together into a verinum
 858  * result. The resulting number is as large as the sum of the sizes of
 859  * the operand.
 860  *
 861  * The algorithm used is successive shift and add operations,
 862  * implemented as the nested loops.
 863  *
 864  * If either value is not completely defined, then the result is not
 865  * defined either.
 866  */
 867 verinum operator * (const verinum&left, const verinum&right)
 868 {
 869       const bool has_len_flag = left.has_len() && right.has_len();
 870
 871         /* If either operand is not fully defined, then the entire
 872            result is undefined. Create a result that is the right size
 873            and is filled with 'bx bits. */
 874       if (! (left.is_defined() && right.is_defined())) {
 875             verinum result (verinum::Vx, left.len()+right.len(), has_len_flag);
 876             result.has_sign(left.has_sign() || right.has_sign());
 877             return result;
 878       }
 879
 880       verinum result(verinum::V0, left.len() + right.len(), has_len_flag);
 881       result.has_sign(left.has_sign() || right.has_sign());
 882
 883       verinum::V r_sign = sign_bit(right);
 884       for (unsigned rdx = 0 ;  rdx < result.len() ;  rdx += 1) {
 885
 886             verinum::V r_bit = rdx < right.len()? right.get(rdx) : r_sign;
 887             if (r_bit == verinum::V0)
 888                   continue;
 889
 890             verinum::V l_sign = sign_bit(left);
 891             verinum::V carry = verinum::V0;
 892             for (unsigned ldx = 0 ;  ldx < result.len()-rdx ;  ldx += 1) {
 893                   verinum::V l_bit = ldx < left.len()? left[ldx] : l_sign;
 894                   result.set(ldx+rdx, add_with_carry(l_bit,
 895                                                      result[rdx+ldx],
 896                                                      carry));
 897             }
 898       }
 899
 900       return trim_vnum(result);
 901 }
 902
 903 verinum pow(const verinum&left, const verinum&right)
 904 {
 905       verinum result = left;
 906       unsigned pow_count = right.as_ulong();
 907
 908       for (unsigned idx = 1 ;  idx < pow_count ;  idx += 1)
 909             result = result * left;
 910
 911       return result;
 912 }
 913
 914 verinum operator << (const verinum&that, unsigned shift)
 915 {
 916       verinum result(verinum::V0, that.len() + shift, that.has_len());
 917
 918       for (unsigned idx = 0 ;  idx < that.len() ;  idx += 1)
 919             result.set(idx+shift, that.get(idx));
 920
 921       return result;
 922 }
 923
 924 verinum operator >> (const verinum&that, unsigned shift)
 925 {
 926       if (shift >= that.len()) {
 927             if (that.has_sign()) {
 928                   verinum result (that.get(that.len()-1), 1);
 929                   result.has_sign(true);
 930                   return result;
 931             } else {
 932                   verinum result(verinum::V0, 1);
 933                   return result;
 934             }
 935       }
 936
 937       verinum result(that.has_sign()? that.get(that.len()-1) : verinum::V0,
 938                      that.len() - shift, that.has_len());
 939
 940       for (unsigned idx = shift ;  idx < that.len() ;  idx += 1)
 941             result.set(idx-shift, that.get(idx));
 942
 943       return result;
 944 }
 945
 946 static verinum unsigned_divide(verinum num, verinum den, bool signed_result)
 947 {
 948       unsigned nwid = num.len();
 949       while (nwid > 0 && (num.get(nwid-1) == verinum::V0))
 950             nwid -= 1;
 951
 952       unsigned dwid = den.len();
 953       while (dwid > 0 && (den.get(dwid-1) == verinum::V0))
 954             dwid -= 1;
 955
 956       if (dwid > nwid)
 957             return verinum(verinum::V0, 1);
 958
 959       den = den << (nwid-dwid);
 960
 961       unsigned idx = nwid - dwid + 1;
 962       verinum result (verinum::V0, signed_result ? idx + 1 : idx);
 963       if (signed_result) {
 964             result.set(idx, verinum::V0);
 965             result.has_sign(true);
 966       }
 967       while (idx > 0) {
 968             if (den <= num) {
 969                   verinum dif = num - den;
 970                   num = dif;
 971                   result.set(idx-1, verinum::V1);
 972             }
 973             den = den >> 1;
 974             idx -= 1;
 975       }
 976
 977       return result;
 978 }
 979
 980 static verinum unsigned_modulus(verinum num, verinum den)
 981 {
 982       unsigned nwid = num.len();
 983       while (nwid > 0 && (num.get(nwid-1) == verinum::V0))
 984             nwid -= 1;
 985
 986       unsigned dwid = den.len();
 987       while (dwid > 0 && (den.get(dwid-1) == verinum::V0))
 988             dwid -= 1;
 989
 990       if (dwid > nwid)
 991             return num;
 992
 993       den = den << (nwid-dwid);
 994
 995       unsigned idx = nwid - dwid + 1;
 996       while (idx > 0) {
 997             if (den <= num) {
 998                   verinum dif = num - den;
 999                   num = dif;
1000             }
1001             den = den >> 1;
1002             idx -= 1;
1003       }
1004
1005       return num;
1006 }
1007
1008 /*
1009  * This operator divides the left number by the right number. If
1010  * either value is signed, the result is signed. If both values have a
1011  * defined length, then the result has a defined length.
1012  */
1013 verinum operator / (const verinum&left, const verinum&right)
1014 {
1015       const bool has_len_flag = left.has_len() && right.has_len();
1016
1017       unsigned use_len = left.len();
1018
1019         /* If either operand is not fully defined, then the entire
1020            result is undefined. Create a result that is the right size
1021            and is filled with 'bx bits. */
1022       if (! (left.is_defined() && right.is_defined())) {
1023             verinum result (verinum::Vx, use_len, has_len_flag);
1024             result.has_sign(left.has_sign() || right.has_sign());
1025             return result;
1026       }
1027
1028         /* If the right expression is a zero value, then the result is
1029            filled with 'bx bits. */
1030       if (right.is_zero()) {
1031             verinum result (verinum::Vx, use_len, has_len_flag);
1032             result.has_sign(left.has_sign() || right.has_sign());
1033             return result;
1034       }
1035
1036       verinum result(verinum::Vz, use_len, has_len_flag);
1037       result.has_sign(left.has_sign() || right.has_sign());
1038
1039         /* do the operation differently, depending on whether the
1040            result is signed or not. */
1041       if (result.has_sign()) {
1042
1043             if (use_len <= (8*sizeof(long) - 1)) {
1044                   long l = left.as_long();
1045                   long r = right.as_long();
1046                   long v = l / r;
1047                   for (unsigned idx = 0 ;  idx < use_len ;  idx += 1) {
1048                         result.set(idx,  (v & 1)? verinum::V1 : verinum::V0);
1049                         v >>= 1;
1050                   }
1051
1052             } else {
1053                   verinum use_left, use_right;
1054                   verinum zero(verinum::V0, 1, false);
1055                   zero.has_sign(true);
1056                   bool negative = false;
1057                   if (left < zero) {
1058                         use_left = zero - left;
1059                         negative = !negative;
1060                   } else {
1061                         use_left = left;
1062                   }
1063                   if (right < zero) {
1064                         use_right = zero - right;
1065                         negative = !negative;
1066                   } else {
1067                         use_right = right;
1068                   }
1069                   result = unsigned_divide(use_left, use_right, true);
1070                   if (negative) result = zero - result;
1071             }
1072
1073       } else {
1074
1075             if (use_len <= 8 * sizeof(unsigned long)) {
1076                     /* Use native unsigned division to do the work. */
1077
1078                   unsigned long l = left.as_ulong();
1079                   unsigned long r = right.as_ulong();
1080                   unsigned long v = l / r;
1081                   for (unsigned idx = 0 ;  idx < use_len ;  idx += 1) {
1082                         result.set(idx,  (v & 1)? verinum::V1 : verinum::V0);
1083                         v >>= 1;
1084                   }
1085
1086             } else {
1087                   result = unsigned_divide(left, right, false);
1088             }
1089       }
1090
1091       return trim_vnum(result);
1092 }
1093
1094 verinum operator % (const verinum&left, const verinum&right)
1095 {
1096       const bool has_len_flag = left.has_len() && right.has_len();
1097
1098       unsigned use_len = left.len();
1099
1100         /* If either operand is not fully defined, then the entire
1101            result is undefined. Create a result that is the right size
1102            and is filled with 'bx bits. */
1103       if (! (left.is_defined() && right.is_defined())) {
1104             verinum result (verinum::Vx, use_len, has_len_flag);
1105             result.has_sign(left.has_sign() || right.has_sign());
1106             return result;
1107       }
1108
1109         /* If the right expression is a zero value, then the result is
1110            filled with 'bx bits. */
1111       if (right.as_ulong() == 0) {
1112             verinum result (verinum::Vx, use_len, has_len_flag);
1113             result.has_sign(left.has_sign() || right.has_sign());
1114             return result;
1115       }
1116
1117       verinum result(verinum::Vz, use_len, has_len_flag);
1118       result.has_sign(left.has_sign() || right.has_sign());
1119
1120       if (result.has_sign()) {
1121             if (use_len <= 8*sizeof(long)) {
1122                     /* Use native signed modulus to do the work. */
1123                   long l = left.as_long();
1124                   long r = right.as_long();
1125                   long v = l % r;
1126                   for (unsigned idx = 0 ;  idx < use_len ;  idx += 1) {
1127                         result.set(idx,  (v & 1)? verinum::V1 : verinum::V0);
1128                         v >>= 1;
1129                   }
1130             } else {
1131                   verinum use_left, use_right;
1132                   verinum zero(verinum::V0, 1, false);
1133                   zero.has_sign(true);
1134                   bool negative = false;
1135                   if (left < zero) {
1136                         use_left = zero - left;
1137                         negative = true;
1138                   } else {
1139                         use_left = left;
1140                   }
1141                   if (right < zero) {
1142                         use_right = zero - right;
1143                   } else {
1144                         use_right = right;
1145                   }
1146                   result = unsigned_modulus(use_left, use_right);
1147                   result.has_sign(true);
1148                   if (negative) result = zero - result;
1149             }
1150       } else {
1151             if (use_len <= 8*sizeof(unsigned long)) {
1152                     /* Use native unsigned modulus to do the work. */
1153                   unsigned long l = left.as_ulong();
1154                   unsigned long r = right.as_ulong();
1155                   unsigned long v = l % r;
1156                   for (unsigned idx = 0 ;  idx < use_len ;  idx += 1) {
1157                         result.set(idx,  (v & 1)? verinum::V1 : verinum::V0);
1158                         v >>= 1;
1159                   }
1160             } else {
1161                   result = unsigned_modulus(left, right);
1162             }
1163       }
1164
1165       return trim_vnum(result);
1166 }
1167
1168 verinum concat(const verinum&left, const verinum&right)
1169 {
1170       if (left.is_string() && right.is_string()) {
1171             std::string tmp = left.as_string() + right.as_string();
1172             verinum res (tmp);
1173             return res;
1174       }
1175
1176       verinum res (verinum::V0, left.len() + right.len());
1177       for (unsigned idx = 0 ;  idx < right.len() ;  idx += 1)
1178             res.set(idx, right.get(idx));
1179
1180       for (unsigned idx = 0 ;  idx < left.len() ;  idx += 1)
1181             res.set(idx+right.len(), left.get(idx));
1182
1183       return res;
1184 }
1185
1186 verinum::V operator ~ (verinum::V l)
1187 {
1188       switch (l) {
1189           case verinum::V0:
1190             return verinum::V1;
1191           case verinum::V1:
1192             return verinum::V0;
1193           default:
1194             return verinum::Vx;
1195       }
1196 }
1197
1198 verinum::V operator | (verinum::V l, verinum::V r)
1199 {
1200       if (l == verinum::V1)
1201             return verinum::V1;
1202       if (r == verinum::V1)
1203             return verinum::V1;
1204       if (l != verinum::V0)
1205             return verinum::Vx;
1206       if (r != verinum::V0)
1207             return verinum::Vx;
1208       return verinum::V0;
1209 }
1210
1211 verinum::V operator & (verinum::V l, verinum::V r)
1212 {
1213       if (l == verinum::V0)
1214             return verinum::V0;
1215       if (r == verinum::V0)
1216             return verinum::V0;
1217       if (l != verinum::V1)
1218             return verinum::Vx;
1219       if (r != verinum::V1)
1220             return verinum::Vx;
1221       return verinum::V1;
1222 }
1223
1224 verinum::V operator ^ (verinum::V l, verinum::V r)
1225 {
1226       if (l == verinum::V0)
1227             return bit4_z2x(r);
1228       if (r == verinum::V0)
1229             return bit4_z2x(l);
1230       if ((l == verinum::V1) && (r == verinum::V1))
1231             return verinum::V0;
1232
1233       return verinum::Vx;
1234 }