1/***************************************************************************** 2 3 Licensed to Accellera Systems Initiative Inc. (Accellera) under one or 4 more contributor license agreements. See the NOTICE file distributed 5 with this work for additional information regarding copyright ownership. 6 Accellera licenses this file to you under the Apache License, Version 2.0 7 (the "License"); you may not use this file except in compliance with the 8 License. You may obtain a copy of the License at 9 10 http://www.apache.org/licenses/LICENSE-2.0 11 12 Unless required by applicable law or agreed to in writing, software 13 distributed under the License is distributed on an "AS IS" BASIS, 14 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or 15 implied. See the License for the specific language governing 16 permissions and limitations under the License. 17 18 *****************************************************************************/ 19 20/***************************************************************************** 21 22 sc_nbutils.cpp -- External and friend functions for both sc_signed and 23 sc_unsigned classes. 24 25 Original Author: Ali Dasdan, Synopsys, Inc. 26 27 *****************************************************************************/ 28 29/***************************************************************************** 30 31 MODIFICATION LOG - modifiers, enter your name, affiliation, date and 32 changes you are making here. 33 34 Name, Affiliation, Date: 35 Description of Modification: 36 37 *****************************************************************************/ 38 39 40// $Log: sc_nbutils.cpp,v $ 41// Revision 1.4 2011/08/24 22:05:46 acg 42// Torsten Maehne: initialization changes to remove warnings. 43// 44// Revision 1.3 2011/02/18 20:19:15 acg 45// Andy Goodrich: updating Copyright notice. 46// 47// Revision 1.2 2007/11/04 21:26:40 acg 48// Andy Goodrich: added a buffer to the allocation of the q array to address 49// an issue with references outside the array by 1 byte detected by valgrind. 50// 51// Revision 1.1.1.1 2006/12/15 20:20:05 acg 52// SystemC 2.3 53// 54// Revision 1.3 2006/01/13 18:49:32 acg 55// Added $Log command so that CVS check in comments are reproduced in the 56// source. 57// 58 59#include <cctype> 60#include <cstdio> 61#include <cstring> 62#include <sstream> 63 64#include "systemc/ext/dt/bit/messages.hh" 65#include "systemc/ext/dt/int/messages.hh" 66#include "systemc/ext/dt/int/sc_nbutils.hh" 67#include "systemc/ext/utils/functions.hh" 68 69namespace sc_dt 70{ 71 72// only used within vec_from_str (non-standard, deprecated) 73static inline void 74is_valid_base(sc_numrep base) 75{ 76 switch (base) { 77 case SC_NOBASE: case SC_BIN: 78 case SC_OCT: case SC_DEC: 79 case SC_HEX: 80 break; 81 case SC_BIN_US: case SC_BIN_SM: 82 case SC_OCT_US: case SC_OCT_SM: 83 case SC_HEX_US: case SC_HEX_SM: 84 case SC_CSD: 85 SC_REPORT_ERROR("not implemented", 86 "is_valid_base( sc_numrep base ) : " 87 "bases SC_CSD, or ending in _US and _SM are " 88 "not supported"); 89 break; 90 default: 91 std::stringstream msg; 92 msg << "is_valid_base( sc_numrep base ) : base = " << base << 93 " is not valid"; 94 SC_REPORT_ERROR(sc_core::SC_ID_VALUE_NOT_VALID_, msg.str().c_str()); 95 } 96} 97 98// ---------------------------------------------------------------------------- 99// ENUM : sc_numrep 100// 101// Enumeration of number representations for character string conversion. 102// ---------------------------------------------------------------------------- 103 104const std::string 105to_string(sc_numrep numrep) 106{ 107 switch (numrep) { 108#define CASE_ENUM2STR(Value) case Value: return #Value 109 110 CASE_ENUM2STR(SC_DEC); 111 112 CASE_ENUM2STR(SC_BIN); 113 CASE_ENUM2STR(SC_BIN_US); 114 CASE_ENUM2STR(SC_BIN_SM); 115 116 CASE_ENUM2STR(SC_OCT); 117 CASE_ENUM2STR(SC_OCT_US); 118 CASE_ENUM2STR(SC_OCT_SM); 119 120 CASE_ENUM2STR(SC_HEX); 121 CASE_ENUM2STR(SC_HEX_US); 122 CASE_ENUM2STR(SC_HEX_SM); 123 124 CASE_ENUM2STR(SC_CSD); 125 126#undef CASE_ENUM2STR 127 128 default: 129 return "unknown"; 130 } 131} 132 133// ---------------------------------------------------------------------------- 134// SECTION: General utility functions. 135// ---------------------------------------------------------------------------- 136 137// Return the number of characters to advance the source of c. This 138// function implements one move of the FSM to parse the following 139// regular expressions. Error checking is done in the caller. 140 141small_type 142fsm_move(char c, small_type &b, small_type &s, small_type &state) 143{ 144 // Possible regular expressions (REs): 145 // Let N = any digit depending on the base. 146 // 1. [0|1|..|9]N* 147 // 2. [+|-][0|1|..|9]N* 148 // 3. 0[b|B|d|D|o|O|x|X][0|1|..|F]N* 149 // 4. [+|-]?0[b|B|d|D|o|O|x|X][0|1|..|F]N* 150 // 151 // The finite state machine (FMS) to parse these regular expressions 152 // has 4 states, 0 to 3. 0 is the initial state and 3 is the final 153 // state. 154 // 155 // Default sign = SC_POS, default base = NB_DEFAULT_BASE. 156 157 switch (state) { 158 case 0: // The initial state. 159 switch (c) { 160 case '0': s = SC_POS; state = 1; return 0; // RE 1 or 3 161 case '+': s = SC_POS; state = 2; return 1; // RE 2 162 case '-': s = SC_NEG; state = 2; return 1; // RE 2 163 default: 164 s = SC_POS; b = NB_DEFAULT_BASE; state = 3; return 0; // RE 1 165 } 166 // break; //unreachable code 167 case 1: // 0... 168 switch (c) { 169 case 'x': case 'X': b = SC_HEX; state = 3; return 2; // RE 3 or 4 170 case 'd': case 'D': b = SC_DEC; state = 3; return 2; // RE 3 or 4 171 case 'o': case 'O': b = SC_OCT; state = 3; return 2; // RE 3 or 4 172 case 'b': case 'B': b = SC_BIN; state = 3; return 2; // RE 3 or 4 173 default: b = NB_DEFAULT_BASE; state = 3; return 0; // RE 1 174 } 175 // break; //unreachable code 176 case 2: // +... or -... 177 switch (c) { 178 case '0': state = 1; return 0; // RE 2 or 4 179 default: b = NB_DEFAULT_BASE; state = 3; return 0; // RE 2 180 } 181 // break; //unreachable code 182 case 3: // The final state. 183 break; 184 default: 185 // Any other state is not possible. 186 sc_assert((0 <= state) && (state <= 3)); 187 } // switch 188 return 0; 189} 190 191 192// Get base b and sign s of the number in the char string v. Return a 193// pointer to the first char after the point where b and s are 194// determined or where the end of v is reached. The input string v has 195// to be null terminated. 196const char * 197get_base_and_sign(const char *v, small_type &b, small_type &s) 198{ 199#ifdef DEBUG_SYSTEMC 200 sc_assert(v != NULL); 201#endif 202 const small_type STATE_START = 0; 203 const small_type STATE_FINISH = 3; 204 205 // Default sign = SC_POS, default base = 10. 206 s = SC_POS; 207 b = NB_DEFAULT_BASE; 208 209 small_type state = STATE_START; 210 small_type nskip = 0; // Skip that many chars. 211 const char *u = v; 212 213 while (*u) { 214 if (isspace(*u)) { // Skip white space. 215 ++u; 216 } else { 217 nskip += fsm_move(*u, b, s, state); 218 if (state == STATE_FINISH) 219 break; 220 else 221 ++u; 222 } 223 } 224 225 // Test to see if the above loop executed more than it should 226 // have. The max number of skipped chars is equal to the length of 227 // the longest format specifier, e.g., "-0x". 228 sc_assert(nskip <= 3); 229 230 v += nskip; 231 232 // Handles empty strings or strings without any digits after the 233 // base or base and sign specifier. 234 if (*v == '\0') { 235 static const char msg[] = 236 "get_base_and_sign( const char* v, small_type&, small_type& ) : " 237 "v = \"\" is not valid"; 238 SC_REPORT_ERROR(sc_core::SC_ID_CONVERSION_FAILED_, msg); 239 } 240 return v; 241} 242 243//----------------------------------------------------------------------------- 244//"parse_binary_bits" 245// 246// This function parses the supplied string into the supplied vector as a 247// right justified bit value. 248// src_p -> character string representing the bits to be parsed. 249// dst_n = number of words in data_p and ctrl_p. 250// data_p -> words w/BITS_PER_DIGIT bits to receive the value's data bits. 251// ctrl_p -> words w/BITS_PER_DIGIT bits to receive the value's control 252// bits, or zero. 253// Result is true if value was non-zero. 254//----------------------------------------------------------------------------- 255void 256parse_binary_bits(const char *src_p, int dst_n, 257 sc_digit *data_p, sc_digit *ctrl_p) 258{ 259 int bit_i; // Number of bit now processing. 260 sc_digit ctrl; // Control word now assembling. 261 sc_digit data; // Data word now assembling. 262 int delta_n; // src_n - dst_n*BITS_PER_DIGIT. 263 int src_i; // Index in src_p now accessing (left to right). 264 int src_n; // Length of source that is left in bits. 265 int word_i; // Bit within word now accessing (left to right). 266 267 // MAKE SURE WE HAVE A STRING TO PARSE: 268 if (src_p == 0) { 269 SC_REPORT_ERROR(sc_core::SC_ID_CONVERSION_FAILED_, 270 "character string is zero"); 271 return; 272 } 273 if (*src_p == 0) { 274 SC_REPORT_ERROR(sc_core::SC_ID_CONVERSION_FAILED_, 275 "character string is empty"); 276 return; 277 } 278 279 280 // INDEX INTO THE SOURCE TO A DEPTH THAT WILL ACCOMODATE OUR SIZE: 281 // 282 // If the source is smaller than our value initialize our value to zero. 283 284 src_n = strlen(src_p); 285 delta_n = src_n - (dst_n*BITS_PER_DIGIT); 286 if (delta_n > 0) { 287 src_p = &src_p[delta_n]; 288 src_n -= delta_n; 289 } else { 290 for (word_i = 0; word_i < dst_n; word_i++) 291 data_p[word_i] = 0; 292 if (ctrl_p) 293 for (word_i = 0; word_i < dst_n; word_i++) 294 ctrl_p[word_i] = 0; 295 } 296 297 // LOOP OVER THE SOURCE ASSEMBLING WORDS AND PLACING THEM IN OUR VALUE: 298 // 299 // We stride right to left through the source in BITS_PER_DIGIT chunks. 300 // Each of those chunks is processed from left to right a bit at a time. 301 // We process the high order word specially, since there are less bits. 302 src_n = src_n - BITS_PER_DIGIT; 303 for (word_i=0; word_i < dst_n; word_i++) { 304 src_i = src_n; 305 306 // PARTIAL LAST WORD TO ASSEMBLE: 307 if (src_i < 0) { 308 src_n += BITS_PER_DIGIT; 309 data = 0; 310 ctrl = 0; 311 for (src_i = 0; src_i < src_n; src_i++) { 312 ctrl = ctrl << 1; 313 data = data << 1; 314 switch (src_p[src_i]) { 315 case 'X': 316 case 'x': ctrl = ctrl | 1; data = data | 1; break; 317 case '1': data = data | 1; break; 318 case 'Z': 319 case 'z': ctrl = ctrl | 1; break; 320 case '0': break; 321 default: 322 { 323 std::stringstream msg; 324 msg << "character string '" << src_p << 325 "' is not valid"; 326 SC_REPORT_ERROR(sc_core::SC_ID_CONVERSION_FAILED_, 327 msg.str().c_str()); 328 return; 329 } 330 break; 331 } 332 } 333 if (ctrl_p) 334 ctrl_p[word_i] = ctrl; 335 data_p[word_i] = data; 336 break; 337 } 338 339 // FULL WORD TO BE ASSEMBLED: 340 ctrl = 0; 341 data = 0; 342 for (bit_i = 0; bit_i < BITS_PER_DIGIT; bit_i++) { 343 ctrl = ctrl << 1; 344 data = data << 1; 345 switch (src_p[src_i++]) { 346 case 'X': 347 case 'x': ctrl = ctrl | 1; data = data | 1; break; 348 case '1': data = data | 1; break; 349 case 'Z': 350 case 'z': ctrl = ctrl | 1; break; 351 case '0': break; 352 default: 353 { 354 std::stringstream msg; 355 msg << "character string '" << src_p << 356 "' is not valid"; 357 SC_REPORT_ERROR(sc_core::SC_ID_CONVERSION_FAILED_, 358 msg.str().c_str()); 359 return; 360 } 361 break; 362 } 363 } 364 if (ctrl_p) 365 ctrl_p[word_i] = ctrl; 366 data_p[word_i] = data; 367 src_n = src_n - BITS_PER_DIGIT; 368 } 369} 370 371 372//----------------------------------------------------------------------------- 373//"parse_hex_bits" 374// 375// This function parses the supplied string into the supplied vector as a 376// right justified bit value. 377// src_p -> character string representing the bits to be parsed. 378// dst_n = number of words in data_p and ctrl_p. 379// data_p -> words w/32 bits to receive the value's data bits. 380// ctrl_p -> words w/32 bits to receive the value's control bits, 381// or zero. 382// Result is true if value was non-zero. 383//----------------------------------------------------------------------------- 384void 385parse_hex_bits(const char *src_p, int dst_n, 386 sc_digit *data_p, sc_digit *ctrl_p) 387{ 388 sc_digit ctrl; // Control word now assembling. 389 sc_digit data; // Data word now assembling. 390 int delta_n; // src_n - dst_n*BITS_PER_DIGIT. 391 int digit_i; // Number of digit now processing. 392 int src_i; // Index in src_p now accessing (left to right). 393 int src_n; // Length of source that is left in bits. 394 int word_i; // Bit within word now accessing (left to right). 395 396 // MAKE SURE WE HAVE A STRING TO PARSE: 397 if (src_p == 0) { 398 SC_REPORT_ERROR(sc_core::SC_ID_CONVERSION_FAILED_, 399 "character string is zero"); 400 return; 401 } 402 if (*src_p == 0) { 403 SC_REPORT_ERROR(sc_core::SC_ID_CONVERSION_FAILED_, 404 "character string is empty"); 405 return; 406 } 407 408 // INDEX INTO THE SOURCE TO A DEPTH THAT WILL ACCOMODATE OUR SIZE: 409 // 410 // If the source is smaller than our value initialize our value to zero. 411 src_n = strlen(src_p); 412 delta_n = src_n - (dst_n*8); 413 if (delta_n > 0) { 414 src_p = &src_p[delta_n]; 415 src_n -= delta_n; 416 } else { 417 for (word_i = 0; word_i < dst_n; word_i++) 418 data_p[word_i] = 0; 419 if (ctrl_p) 420 for (word_i = 0; word_i < dst_n; word_i++) 421 ctrl_p[word_i] = 0; 422 } 423 424 // LOOP OVER THE SOURCE ASSEMBLING WORDS AND PLACING THEM IN OUR VALUE: 425 // 426 // We stride right to left through the source in BITS_PER_DIGIT chunks. 427 // Each of those chunks is processed from left to right a bit at a time. 428 // We process the high order word specially, since there are less bits. 429 src_n = src_n - 8; 430 for (word_i = 0; word_i < dst_n; word_i++) { 431 src_i = src_n; 432 433 // PARTIAL LAST WORD TO ASSEMBLE: 434 if (src_i < 0) { 435 src_n += 8; 436 data = 0; 437 ctrl = 0; 438 for (src_i = 0; src_i < src_n; src_i++) { 439 ctrl = ctrl << 4; 440 data = data << 4; 441 switch (src_p[src_i]) { 442 case 'X': 443 case 'x': ctrl = ctrl | 15; data = data | 15; break; 444 case 'F': 445 case 'f': data = data | 15; break; 446 case 'E': 447 case 'e': data = data | 14; break; 448 case 'D': 449 case 'd': data = data | 13; break; 450 case 'C': 451 case 'c': data = data | 12; break; 452 case 'B': 453 case 'b': data = data | 11; break; 454 case 'A': 455 case 'a': data = data | 10; break; 456 case '9': data = data | 9; break; 457 case '8': data = data | 8; break; 458 case '7': data = data | 7; break; 459 case '6': data = data | 6; break; 460 case '5': data = data | 5; break; 461 case '4': data = data | 4; break; 462 case '3': data = data | 3; break; 463 case '2': data = data | 2; break; 464 case '1': data = data | 1; break; 465 case '0': break; 466 case 'Z': 467 case 'z': ctrl = ctrl | 15; break; 468 default: 469 { 470 std::stringstream msg; 471 msg << "character string '" << src_p << 472 "' is not valid"; 473 SC_REPORT_ERROR(sc_core::SC_ID_CONVERSION_FAILED_, 474 msg.str().c_str()); 475 return; 476 } 477 break; 478 } 479 } 480 if (ctrl_p) 481 ctrl_p[word_i] = ctrl; 482 data_p[word_i] = data; 483 break; 484 } 485 486 // FULL WORD TO BE ASSEMBLED: 487 ctrl = 0; 488 data = 0; 489 for (digit_i = 0; digit_i < 8; digit_i++) { 490 ctrl = ctrl << 4; 491 data = data << 4; 492 switch (src_p[src_i++]) { 493 case 'X': 494 case 'x': ctrl = ctrl | 15; data = data | 15; break; 495 case 'F': 496 case 'f': data = data | 15; break; 497 case 'E': 498 case 'e': data = data | 14; break; 499 case 'D': 500 case 'd': data = data | 13; break; 501 case 'C': 502 case 'c': data = data | 12; break; 503 case 'B': 504 case 'b': data = data | 11; break; 505 case 'A': 506 case 'a': data = data | 10; break; 507 case '9': data = data | 9; break; 508 case '8': data = data | 8; break; 509 case '7': data = data | 7; break; 510 case '6': data = data | 6; break; 511 case '5': data = data | 5; break; 512 case '4': data = data | 4; break; 513 case '3': data = data | 3; break; 514 case '2': data = data | 2; break; 515 case '1': data = data | 1; break; 516 case '0': break; 517 case 'Z': 518 case 'z': ctrl = ctrl | 15; break; 519 default: 520 { 521 std::stringstream msg; 522 msg << "character string '" << src_p << "' is not valid"; 523 SC_REPORT_ERROR(sc_core::SC_ID_CONVERSION_FAILED_, 524 msg.str().c_str() ); 525 return; 526 } 527 break; 528 } 529 } 530 if (ctrl_p) 531 ctrl_p[word_i] = ctrl; 532 data_p[word_i] = data; 533 src_n = src_n - BITS_PER_DIGIT; 534 } 535} 536 537 538// ---------------------------------------------------------------------------- 539// SECTION: Utility functions involving unsigned vectors. 540// ---------------------------------------------------------------------------- 541 542// Read u from a null terminated char string v. Note that operator>> 543// in sc_nbcommon.cpp is similar to this function. 544small_type 545vec_from_str(int unb, int und, sc_digit *u, const char *v, sc_numrep base) 546{ 547 548#ifdef DEBUG_SYSTEMC 549 sc_assert((unb > 0) && (und > 0) && (u != NULL)); 550 sc_assert(v != NULL); 551#endif 552 is_valid_base(base); 553 554 small_type b, s; // base and sign. 555 556 v = get_base_and_sign(v, b, s); 557 558 if (base != SC_NOBASE) { 559 if (b == NB_DEFAULT_BASE) { 560 b = base; 561 } else { 562 std::stringstream msg; 563 msg << "vec_from_str( int, int, sc_digit*, const char*, " << 564 "sc_numrep base ) : base = " << base << 565 " does not match the default base"; 566 SC_REPORT_ERROR(sc_core::SC_ID_CONVERSION_FAILED_, 567 msg.str().c_str()); 568 return 0; 569 } 570 } 571 572 vec_zero(und, u); 573 574 char c; 575 for (; (c = *v); ++v) { 576 if (isalnum(c)) { 577 small_type val; // Numeric value of a char. 578 579 if (isalpha(c)) // Hex digit. 580 val = toupper(c) - 'A' + 10; 581 else 582 val = c - '0'; 583 584 if (val >= b) { 585 std::stringstream msg; 586 msg << "vec_from_str( int, int, sc_digit*, const char*, " << 587 "sc_numrep base ) : '" << *v << "' is not a valid " << 588 "digit in base " << b; 589 SC_REPORT_ERROR(sc_core::SC_ID_CONVERSION_FAILED_, 590 msg.str().c_str()); 591 return 0; 592 } 593 594 // digit = digit * b + val; 595 vec_mul_small_on(und, u, b); 596 597 if (val) 598 vec_add_small_on(und, u, val); 599 } else { 600 std::stringstream msg; 601 msg << "vec_from_str( int, int, sc_digit*, const char*, " << 602 "sc_numrep base ) : '" << *v << "' is not a valid " << 603 "digit in base " << b; 604 SC_REPORT_ERROR(sc_core::SC_ID_CONVERSION_FAILED_, 605 msg.str().c_str()); 606 return 0; 607 } 608 } 609 610 return convert_signed_SM_to_2C_to_SM(s, unb, und, u); 611} 612 613 614// All vec_ functions assume that the vector to hold the result, 615// called w, has sufficient length to hold the result. For efficiency 616// reasons, we do not test whether or not we are out of bounds. 617 618// Compute w = u + v, where w, u, and v are vectors. 619// - ulen >= vlen 620// - wlen >= sc_max(ulen, vlen) + 1 621void 622vec_add(int ulen, const sc_digit *u, int vlen, const sc_digit *v, sc_digit *w) 623{ 624#ifdef DEBUG_SYSTEMC 625 sc_assert((ulen > 0) && (u != NULL)); 626 sc_assert((vlen > 0) && (v != NULL)); 627 sc_assert(w != NULL); 628 sc_assert(ulen >= vlen); 629#endif 630 631 const sc_digit *uend = (u + ulen); 632 const sc_digit *vend = (v + vlen); 633 634 sc_digit carry = 0; // Also used as sum to save space. 635 636 // Add along the shorter v. 637 while (v < vend) { 638 carry += (*u++) + (*v++); 639 (*w++) = carry & DIGIT_MASK; 640 carry >>= BITS_PER_DIGIT; 641 } 642 643 // Propagate the carry. 644 while (carry && (u < uend)) { 645 carry = (*u++) + 1; 646 (*w++) = carry & DIGIT_MASK; 647 carry >>= BITS_PER_DIGIT; 648 } 649 650 // Copy the rest of u to the result. 651 while (u < uend) 652 (*w++) = (*u++); 653 654 // Propagate the carry if it is still 1. 655 if (carry) 656 (*w) = 1; 657} 658 659 660// Compute u += v, where u and v are vectors. 661// - ulen >= vlen 662void 663vec_add_on(int ulen, sc_digit *ubegin, int vlen, const sc_digit *v) 664{ 665#ifdef DEBUG_SYSTEMC 666 sc_assert((ulen > 0) && (ubegin != NULL)); 667 sc_assert((vlen > 0) && (v != NULL)); 668 sc_assert(ulen >= vlen); 669#endif 670 671 sc_digit *u = ubegin; 672 const sc_digit *uend = (u + ulen); 673 const sc_digit *vend = (v + vlen); 674 675 sc_digit carry = 0; // Also used as sum to save space. 676 677 // Add along the shorter v. 678 while (v < vend) { 679 carry += (*u) + (*v++); 680 (*u++) = carry & DIGIT_MASK; 681 carry >>= BITS_PER_DIGIT; 682 } 683 684 // Propagate the carry. 685 while (carry && (u < uend)) { 686 carry = (*u) + 1; 687 (*u++) = carry & DIGIT_MASK; 688 carry >>= BITS_PER_DIGIT; 689 } 690 691#ifdef DEBUG_SYSTEMC 692 if (carry != 0) { 693 SC_REPORT_WARNING(sc_core::SC_ID_WITHOUT_MESSAGE_, 694 "vec_add_on( int, sc_digit*, int, const " 695 "sc_digit* ) : " 696 "result of addition is wrapped around"); 697 } 698#endif 699} 700 701 702// Compute u += v, where u and v are vectors. 703// - ulen < vlen 704void 705vec_add_on2(int ulen, sc_digit *ubegin, int, 706#ifdef DEBUG_SYSTEMC 707 vlen, 708#endif 709 const sc_digit *v) 710{ 711#ifdef DEBUG_SYSTEMC 712 sc_assert((ulen > 0) && (ubegin != NULL)); 713 sc_assert((vlen > 0) && (v != NULL)); 714 sc_assert(ulen < vlen); 715#endif 716 717 sc_digit *u = ubegin; 718 const sc_digit *uend = (u + ulen); 719 720 sc_digit carry = 0; // Also used as sum to save space. 721 722 // Add along the shorter u. 723 while (u < uend) { 724 carry += (*u) + (*v++); 725 (*u++) = carry & DIGIT_MASK; 726 carry >>= BITS_PER_DIGIT; 727 } 728 729#ifdef DEBUG_SYSTEMC 730 if (carry != 0) { 731 SC_REPORT_WARNING(sc_core::SC_ID_WITHOUT_MESSAGE_, 732 "vec_add_on2( int, sc_digit*, int, const " 733 "sc_digit* ) : " 734 "result of addition is wrapped around"); 735 } 736#endif 737} 738 739 740// Compute w = u + v, where w and u are vectors, and v is a scalar. 741void 742vec_add_small(int ulen, const sc_digit *u, sc_digit v, sc_digit *w) 743{ 744#ifdef DEBUG_SYSTEMC 745 sc_assert((ulen > 0) && (u != NULL)); 746 sc_assert(w != NULL); 747#endif 748 749 const sc_digit *uend = (u + ulen); 750 751 // Add along the shorter v. 752 sc_digit carry = (*u++) + v; 753 (*w++) = carry & DIGIT_MASK; 754 carry >>= BITS_PER_DIGIT; 755 756 // Propagate the carry. 757 while (carry && (u < uend)) { 758 carry = (*u++) + 1; 759 (*w++) = carry & DIGIT_MASK; 760 carry >>= BITS_PER_DIGIT; 761 } 762 763 // Copy the rest of u to the result. 764 while (u < uend) 765 (*w++) = (*u++); 766 767 // Propagate the carry if it is still 1. 768 if (carry) 769 (*w) = 1; 770} 771 772// Compute u += v, where u is vectors, and v is a scalar. 773void 774vec_add_small_on(int ulen, sc_digit *u, sc_digit v) 775{ 776#ifdef DEBUG_SYSTEMC 777 sc_assert((ulen > 0) && (u != NULL)); 778#endif 779 780 int i = 0; 781 782 while (v && (i < ulen)) { 783 v += u[i]; 784 u[i++] = v & DIGIT_MASK; 785 v >>= BITS_PER_DIGIT; 786 } 787 788#ifdef DEBUG_SYSTEMC 789 if (v != 0) { 790 SC_REPORT_WARNING(sc_core::SC_ID_WITHOUT_MESSAGE_, 791 "vec_add_small_on( int, sc_digit*, unsigned " 792 "long ) : " 793 "result of addition is wrapped around"); 794 } 795#endif 796} 797 798// Compute w = u - v, where w, u, and v are vectors. 799// - ulen >= vlen 800// - wlen >= sc_max(ulen, vlen) 801void 802vec_sub(int ulen, const sc_digit *u, int vlen, const sc_digit *v, sc_digit *w) 803{ 804#ifdef DEBUG_SYSTEMC 805 sc_assert((ulen > 0) && (u != NULL)); 806 sc_assert((vlen > 0) && (v != NULL)); 807 sc_assert(w != NULL); 808 sc_assert(ulen >= vlen); 809#endif 810 811 const sc_digit *uend = (u + ulen); 812 const sc_digit *vend = (v + vlen); 813 814 sc_digit borrow = 0; // Also used as diff to save space. 815 816 // Subtract along the shorter v. 817 while (v < vend) { 818 borrow = ((*u++) + DIGIT_RADIX) - (*v++) - borrow; 819 (*w++) = borrow & DIGIT_MASK; 820 borrow = 1 - (borrow >> BITS_PER_DIGIT); 821 } 822 823 // Propagate the borrow. 824 while (borrow && (u < uend)) { 825 borrow = ((*u++) + DIGIT_RADIX) - 1; 826 (*w++) = borrow & DIGIT_MASK; 827 borrow = 1 - (borrow >> BITS_PER_DIGIT); 828 } 829 830#ifdef DEBUG_SYSTEMC 831 sc_assert(borrow == 0); 832#endif 833 834 // Copy the rest of u to the result. 835 while (u < uend) 836 (*w++) = (*u++); 837} 838 839// Compute u = u - v, where u and v are vectors. 840// - u > v 841// - ulen >= vlen 842void 843vec_sub_on(int ulen, sc_digit *ubegin, int vlen, const sc_digit *v) 844{ 845#ifdef DEBUG_SYSTEMC 846 sc_assert((ulen > 0) && (ubegin != NULL)); 847 sc_assert((vlen > 0) && (v != NULL)); 848 sc_assert(ulen >= vlen); 849#endif 850 851 sc_digit *u = ubegin; 852 const sc_digit *uend = (u + ulen); 853 const sc_digit *vend = (v + vlen); 854 855 sc_digit borrow = 0; // Also used as diff to save space. 856 857 // Subtract along the shorter v. 858 while (v < vend) { 859 borrow = ((*u) + DIGIT_RADIX) - (*v++) - borrow; 860 (*u++) = borrow & DIGIT_MASK; 861 borrow = 1 - (borrow >> BITS_PER_DIGIT); 862 } 863 864 // Propagate the borrow. 865 while (borrow && (u < uend)) { 866 borrow = ((*u) + DIGIT_RADIX) - 1; 867 (*u++) = borrow & DIGIT_MASK; 868 borrow = 1 - (borrow >> BITS_PER_DIGIT); 869 } 870 871#ifdef DEBUG_SYSTEMC 872 sc_assert(borrow == 0); 873#endif 874} 875 876// Compute u = v - u, where u and v are vectors. 877// - v > u 878// - ulen <= vlen or ulen > ulen 879void 880vec_sub_on2(int ulen, sc_digit *ubegin, int vlen, const sc_digit *v) 881{ 882#ifdef DEBUG_SYSTEMC 883 sc_assert((ulen > 0) && (ubegin != NULL)); 884 sc_assert((vlen > 0) && (v != NULL)); 885#endif 886 887 sc_digit *u = ubegin; 888 const sc_digit *uend = (u + sc_min(ulen, vlen)); 889 890 sc_digit borrow = 0; // Also used as diff to save space. 891 892 // Subtract along the shorter u. 893 while (u < uend) { 894 borrow = ((*v++) + DIGIT_RADIX) - (*u) - borrow; 895 (*u++) = borrow & DIGIT_MASK; 896 borrow = 1 - (borrow >> BITS_PER_DIGIT); 897 } 898 899#ifdef DEBUG_SYSTEMC 900 if (borrow != 0) { 901 SC_REPORT_WARNING(sc_core::SC_ID_WITHOUT_MESSAGE_, 902 "vec_sub_on2( int, sc_digit*, int, const " 903 "sc_digit* ) : " 904 "result of subtraction is wrapped around"); 905 } 906#endif 907} 908 909// Compute w = u - v, where w and u are vectors, and v is a scalar. 910void 911vec_sub_small(int ulen, const sc_digit *u, sc_digit v, sc_digit *w) 912{ 913#ifdef DEBUG_SYSTEMC 914 sc_assert(ulen > 0); 915 sc_assert(u != NULL); 916#endif 917 918 const sc_digit *uend = (u + ulen); 919 920 // Add along the shorter v. 921 sc_digit borrow = ((*u++) + DIGIT_RADIX) - v; 922 (*w++) = borrow & DIGIT_MASK; 923 borrow = 1 - (borrow >> BITS_PER_DIGIT); 924 925 // Propagate the borrow. 926 while (borrow && (u < uend)) { 927 borrow = ((*u++) + DIGIT_RADIX) - 1; 928 (*w++) = borrow & DIGIT_MASK; 929 borrow = 1 - (borrow >> BITS_PER_DIGIT); 930 } 931 932#ifdef DEBUG_SYSTEMC 933 sc_assert(borrow == 0); 934#endif 935 936 // Copy the rest of u to the result. 937 while (u < uend) 938 (*w++) = (*u++); 939} 940 941 942// Compute u -= v, where u is vectors, and v is a scalar. 943void 944vec_sub_small_on(int ulen, sc_digit *u, sc_digit v) 945{ 946#ifdef DEBUG_SYSTEMC 947 sc_assert((ulen > 0) && (u != NULL)); 948#endif 949 950 for (int i = 0; i < ulen; ++i) { 951 v = (u[i] + DIGIT_RADIX) - v; 952 u[i] = v & DIGIT_MASK; 953 v = 1 - (v >> BITS_PER_DIGIT); 954 } 955 956#ifdef DEBUG_SYSTEMC 957 sc_assert(v == 0); 958#endif 959} 960 961// Compute w = u * v, where w, u, and v are vectors. 962void 963vec_mul(int ulen, const sc_digit *u, int vlen, const sc_digit *vbegin, 964 sc_digit *wbegin) 965{ 966 967 /* Consider u = Ax + B and v = Cx + D where x is equal to 968 HALF_DIGIT_RADIX. In other words, A is the higher half of u and 969 B is the lower half of u. The interpretation for v is 970 similar. Then, we have the following picture: 971 972 u_h u_l 973 u: -------- -------- 974 A B 975 976 v_h v_l 977 v: -------- -------- 978 C D 979 980 result (d): 981 carry_before: -------- -------- 982 carry_h carry_l 983 result_before: -------- -------- -------- -------- 984 R1_h R1_l R0_h R0_l 985 -------- -------- 986 BD_h BD_l 987 -------- -------- 988 AD_h AD_l 989 -------- -------- 990 BC_h BC_l 991 -------- -------- 992 AC_h AC_l 993 result_after: -------- -------- -------- -------- 994 R1_h' R1_l' R0_h' R0_l' 995 996 prod_l = R0_h|R0_l + B * D + 0|carry_l 997 = R0_h|R0_l + BD_h|BD_l + 0|carry_l 998 999 prod_h = A * D + B * C + high_half(prod_l) + carry_h 1000 = AD_h|AD_l + BC_h|BC_l + high_half(prod_l) + 0|carry_h 1001 1002 carry = A * C + high_half(prod_h) 1003 = AC_h|AC_l + high_half(prod_h) 1004 1005 R0_l' = low_half(prod_l) 1006 1007 R0_h' = low_half(prod_h) 1008 1009 R0 = high_half(prod_h)|low_half(prod_l) 1010 1011 where '|' is the concatenation operation and the suffixes 0 and 1 1012 show the iteration number, i.e., 0 is the current iteration and 1 1013 is the next iteration. 1014 1015 NOTE: sc_max(prod_l, prod_h, carry) <= 2 * x^2 - 1, so any 1016 of these numbers can be stored in a digit. 1017 1018 NOTE: low_half(u) returns the lower BITS_PER_HALF_DIGIT of u, 1019 whereas high_half(u) returns the rest of the bits, which may 1020 contain more bits than BITS_PER_HALF_DIGIT. 1021 */ 1022 1023#ifdef DEBUG_SYSTEMC 1024 sc_assert((ulen > 0) && (u != NULL)); 1025 sc_assert((vlen > 0) && (vbegin != NULL)); 1026 sc_assert(wbegin != NULL); 1027#endif 1028 1029#define prod_h carry 1030 const sc_digit *uend = (u + ulen); 1031 const sc_digit *vend = (vbegin + vlen); 1032 1033 while (u < uend) { 1034 sc_digit u_h = (*u++); // A|B 1035 sc_digit u_l = low_half(u_h); // B 1036 u_h = high_half(u_h); // A 1037 1038#ifdef DEBUG_SYSTEMC 1039 // The overflow bits must be zero. 1040 sc_assert(u_h == (u_h & HALF_DIGIT_MASK)); 1041#endif 1042 sc_digit carry = 0; 1043 sc_digit *w = (wbegin++); 1044 const sc_digit *v = vbegin; 1045 1046 while (v < vend) { 1047 sc_digit v_h = (*v++); // C|D 1048 sc_digit v_l = low_half(v_h); // D 1049 1050 v_h = high_half(v_h); // C 1051 1052#ifdef DEBUG_SYSTEMC 1053 // The overflow bits must be zero. 1054 sc_assert(v_h == (v_h & HALF_DIGIT_MASK)); 1055#endif 1056 1057 sc_digit prod_l = (*w) + u_l * v_l + low_half(carry); 1058 prod_h = u_h * v_l + u_l * v_h + 1059 high_half(prod_l) + high_half(carry); 1060 (*w++) = concat(low_half(prod_h), low_half(prod_l)); 1061 carry = u_h * v_h + high_half(prod_h); 1062 } 1063 (*w) = carry; 1064 } 1065#undef prod_h 1066} 1067 1068// Compute w = u * v, where w and u are vectors, and v is a scalar. 1069// - 0 < v < HALF_DIGIT_RADIX. 1070void 1071vec_mul_small(int ulen, const sc_digit *u, sc_digit v, sc_digit *w) 1072{ 1073#ifdef DEBUG_SYSTEMC 1074 sc_assert((ulen > 0) && (u != NULL)); 1075 sc_assert(w != NULL); 1076 sc_assert((0 < v) && (v < HALF_DIGIT_RADIX)); 1077#endif 1078 1079#define prod_h carry 1080 1081 const sc_digit *uend = (u + ulen); 1082 sc_digit carry = 0; 1083 while (u < uend) { 1084 sc_digit u_AB = (*u++); 1085#ifdef DEBUG_SYSTEMC 1086 // The overflow bits must be zero. 1087 sc_assert(high_half(u_AB) == high_half_masked(u_AB)); 1088#endif 1089 sc_digit prod_l = v * low_half(u_AB) + low_half(carry); 1090 prod_h = v * high_half(u_AB) + high_half(prod_l) + high_half(carry); 1091 (*w++) = concat(low_half(prod_h), low_half(prod_l)); 1092 carry = high_half(prod_h); 1093 } 1094 (*w) = carry; 1095#undef prod_h 1096} 1097 1098// Compute u = u * v, where u is a vector, and v is a scalar. 1099// - 0 < v < HALF_DIGIT_RADIX. 1100void 1101vec_mul_small_on(int ulen, sc_digit *u, sc_digit v) 1102{ 1103#ifdef DEBUG_SYSTEMC 1104 sc_assert((ulen > 0) && (u != NULL)); 1105 sc_assert((0 < v) && (v < HALF_DIGIT_RADIX)); 1106#endif 1107 1108#define prod_h carry 1109 sc_digit carry = 0; 1110 for (int i = 0; i < ulen; ++i) { 1111#ifdef DEBUG_SYSTEMC 1112 // The overflow bits must be zero. 1113 sc_assert(high_half(u[i]) == high_half_masked(u[i])); 1114#endif 1115 sc_digit prod_l = v * low_half(u[i]) + low_half(carry); 1116 prod_h = v * high_half(u[i]) + high_half(prod_l) + high_half(carry); 1117 u[i] = concat(low_half(prod_h), low_half(prod_l)); 1118 carry = high_half(prod_h); 1119 } 1120#undef prod_h 1121 1122#ifdef DEBUG_SYSTEMC 1123 if (carry != 0) { 1124 SC_REPORT_WARNING(sc_core::SC_ID_WITHOUT_MESSAGE_, 1125 "vec_mul_small_on( int, sc_digit*, unsigned " 1126 "long ) : " 1127 "result of multiplication is wrapped around"); 1128 } 1129#endif 1130} 1131 1132// Compute w = u / v, where w, u, and v are vectors. 1133// - u and v are assumed to have at least two digits as uchars. 1134void 1135vec_div_large(int ulen, const sc_digit *u, int vlen, const sc_digit *v, 1136 sc_digit *w) 1137{ 1138#ifdef DEBUG_SYSTEMC 1139 sc_assert((ulen > 0) && (u != NULL)); 1140 sc_assert((vlen > 0) && (v != NULL)); 1141 sc_assert(w != NULL); 1142 sc_assert(BITS_PER_DIGIT >= 3 * BITS_PER_BYTE); 1143#endif 1144 1145 // We will compute q = x / y where x = u and y = v. The reason for 1146 // using x and y is that x and y are BYTE_RADIX copies of u and v, 1147 // respectively. The use of BYTE_RADIX radix greatly simplifies the 1148 // complexity of the division operation. These copies are also 1149 // needed even when we use DIGIT_RADIX representation. 1150 1151 int xlen = BYTES_PER_DIGIT * ulen + 1; 1152 int ylen = BYTES_PER_DIGIT * vlen; 1153 1154#ifdef SC_MAX_NBITS 1155 uchar x[DIV_CEIL2(SC_MAX_NBITS, BITS_PER_BYTE)]; 1156 uchar y[DIV_CEIL2(SC_MAX_NBITS, BITS_PER_BYTE)]; 1157 uchar q[DIV_CEIL2(SC_MAX_NBITS, BITS_PER_BYTE)]; 1158#else 1159 uchar *x = new uchar[xlen]; 1160 uchar *y = new uchar[ylen]; 1161 // valgrind complains about us accessing too far to so leave a buffer. 1162 uchar *q = new uchar[(xlen - ylen) + 10]; 1163#endif 1164 1165 // q corresponds to w. 1166 1167 // Set (uchar) x = (sc_digit) u. 1168 xlen = vec_to_char(ulen, u, xlen, x); 1169 1170 // Skip all the leading zeros in x. 1171 while ((--xlen >= 0) && (! x[xlen])) 1172 continue; 1173 xlen++; 1174 1175 // Set (uchar) y = (sc_digit) v. 1176 ylen = vec_to_char(vlen, v, ylen, y); 1177 1178 // Skip all the leading zeros in y. 1179 while ((--ylen >= 0) && (! y[ylen])) 1180 continue; 1181 ylen++; 1182 1183#ifdef DEBUG_SYSTEMC 1184 sc_assert(xlen > 1); 1185 sc_assert(ylen > 1); 1186#endif 1187 1188 // At this point, all the leading zeros are eliminated from x and y. 1189 1190 // Zero the last digit of x. 1191 x[xlen] = 0; 1192 1193 // The first two digits of y. 1194 sc_digit y2 = (y[ylen - 1] << BITS_PER_BYTE) + y[ylen - 2]; 1195 1196 const sc_digit DOUBLE_BITS_PER_BYTE = 2 * BITS_PER_BYTE; 1197 1198 // Find each q[k]. 1199 for (int k = (xlen - ylen); k >= 0; --k) { 1200 // qk is a guess for q[k] such that q[k] = qk or qk - 1. 1201 sc_digit qk; 1202 1203 // Find qk by just using 2 digits of y and 3 digits of x. The 1204 // following code assumes that sizeof(sc_digit) >= 3 BYTEs. 1205 int k2 = k + ylen; 1206 1207 qk = ((x[k2] << DOUBLE_BITS_PER_BYTE) + 1208 (x[k2 - 1] << BITS_PER_BYTE) + x[k2 - 2]) / y2; 1209 1210 if (qk >= BYTE_RADIX) // qk cannot be larger than the largest 1211 qk = BYTE_RADIX - 1; // digit in BYTE_RADIX. 1212 1213 // q[k] = qk or qk - 1. The following if-statement determines which: 1214 if (qk) { 1215 uchar *xk = (x + k); // A shortcut for x[k]. 1216 1217 // x = x - y * qk : 1218 sc_digit carry = 0; 1219 1220 for (int i = 0; i < ylen; ++i) { 1221 carry += y[i] * qk; 1222 sc_digit diff = (xk[i] + BYTE_RADIX) - (carry & BYTE_MASK); 1223 xk[i] = (uchar)(diff & BYTE_MASK); 1224 carry = (carry >> BITS_PER_BYTE) + 1225 (1 - (diff >> BITS_PER_BYTE)); 1226 } 1227 1228 // If carry, qk may be one too large. 1229 if (carry) { 1230 // 2's complement the last digit. 1231 carry = (xk[ylen] + BYTE_RADIX) - carry; 1232 xk[ylen] = (uchar)(carry & BYTE_MASK); 1233 carry = 1 - (carry >> BITS_PER_BYTE); 1234 1235 if (carry) { 1236 1237 // qk was one too large, so decrement it. 1238 --qk; 1239 1240 // Since qk was decreased by one, y must be added to x: 1241 // x = x - y * (qk - 1) = x - y * qk + y = x_above + y. 1242 carry = 0; 1243 1244 for (int i = 0; i < ylen; ++i) { 1245 carry += xk[i] + y[i]; 1246 xk[i] = (uchar)(carry & BYTE_MASK); 1247 carry >>= BITS_PER_BYTE; 1248 } 1249 1250 if (carry) 1251 xk[ylen] = (uchar)((xk[ylen] + 1) & BYTE_MASK); 1252 1253 } // second if carry 1254 } // first if carry 1255 } // if qk 1256 q[k] = (uchar)qk; 1257 } // for k 1258 1259 // Set (sc_digit) w = (uchar) q. 1260 vec_from_char(xlen - ylen + 1, q, ulen, w); 1261 1262#ifndef SC_MAX_NBITS 1263 delete [] x; 1264 delete [] y; 1265 delete [] q; 1266#endif 1267 1268} 1269 1270// Compute w = u / v, where u and w are vectors, and v is a scalar. 1271// - 0 < v < HALF_DIGIT_RADIX. Below, we rename w to q. 1272void 1273vec_div_small(int ulen, const sc_digit *u, sc_digit v, sc_digit *q) 1274{ 1275 // Given (u = u_1u_2...u_n)_b = (q = q_1q_2...q_n) * v + r, where b 1276 // is the base, and 0 <= r < v. Then, the algorithm is as follows: 1277 // 1278 // r = 0; 1279 // for (j = 1; j <= n; j++) { 1280 // q_j = (r * b + u_j) / v; 1281 // r = (r * b + u_j) % v; 1282 // } 1283 // 1284 // In our case, b = DIGIT_RADIX, and u = Ax + B and q = Cx + D where 1285 // x = HALF_DIGIT_RADIX. Note that r < v < x and b = x^2. Then, a 1286 // typical situation is as follows: 1287 // 1288 // ---- ---- 1289 // 0 r 1290 // ---- ---- 1291 // A B 1292 // ---- ---- ---- 1293 // r A B = r * b + u 1294 // 1295 // Hence, C = (r|A) / v. 1296 // D = (((r|A) % v)|B) / v 1297 // r = (((r|A) % v)|B) % v 1298 1299#ifdef DEBUG_SYSTEMC 1300 sc_assert((ulen > 0) && (u != NULL)); 1301 sc_assert(q != NULL); 1302 sc_assert((0 < v) && (v < HALF_DIGIT_RADIX)); 1303#endif 1304 1305#define q_h r 1306 sc_digit r = 0; 1307 const sc_digit *ubegin = u; 1308 1309 u += ulen; 1310 q += ulen; 1311 1312 while (ubegin < u) { 1313 sc_digit u_AB = (*--u); // A|B 1314 1315#ifdef DEBUG_SYSTEMC 1316 // The overflow bits must be zero. 1317 sc_assert(high_half(u_AB) == high_half_masked(u_AB)); 1318#endif 1319 1320 sc_digit num = concat(r, high_half(u_AB)); // num = r|A 1321 q_h = num / v; // C 1322 num = concat((num % v), low_half(u_AB)); // num = (((r|A) % v)|B) 1323 (*--q) = concat(q_h, num / v); // q = C|D 1324 r = num % v; 1325 } 1326#undef q_h 1327} 1328 1329// Compute w = u % v, where w, u, and v are vectors. 1330// - u and v are assumed to have at least two digits as uchars. 1331void 1332vec_rem_large(int ulen, const sc_digit *u, int vlen, const sc_digit *v, 1333 sc_digit *w) 1334{ 1335#ifdef DEBUG_SYSTEMC 1336 sc_assert((ulen > 0) && (u != NULL)); 1337 sc_assert((vlen > 0) && (v != NULL)); 1338 sc_assert(w != NULL); 1339 sc_assert(BITS_PER_DIGIT >= 3 * BITS_PER_BYTE); 1340#endif 1341 1342 // This function is adapted from vec_div_large. 1343 int xlen = BYTES_PER_DIGIT * ulen + 1; 1344 int ylen = BYTES_PER_DIGIT * vlen; 1345 1346#ifdef SC_MAX_NBITS 1347 uchar x[DIV_CEIL2(SC_MAX_NBITS, BITS_PER_BYTE)]; 1348 uchar y[DIV_CEIL2(SC_MAX_NBITS, BITS_PER_BYTE)]; 1349#else 1350 uchar *x = new uchar[xlen]; 1351 uchar *y = new uchar[ylen]; 1352#endif 1353 1354 // r corresponds to w. 1355 1356 // Set (uchar) x = (sc_digit) u. 1357 xlen = vec_to_char(ulen, u, xlen, x); 1358 1359 // Skip all the leading zeros in x. 1360 while ((--xlen >= 0) && (!x[xlen])) 1361 continue; 1362 xlen++; 1363 1364 // Set (uchar) y = (sc_digit) v. 1365 ylen = vec_to_char(vlen, v, ylen, y); 1366 1367 // Skip all the leading zeros in y. 1368 while ((--ylen >= 0) && (!y[ylen])) 1369 continue; 1370 ylen++; 1371 1372#ifdef DEBUG_SYSTEMC 1373 sc_assert(xlen > 1); 1374 sc_assert(ylen > 1); 1375#endif 1376 1377 // At this point, all the leading zeros are eliminated from x and y. 1378 1379 // Zero the last digit of x. 1380 x[xlen] = 0; 1381 1382 // The first two digits of y. 1383 sc_digit y2 = (y[ylen - 1] << BITS_PER_BYTE) + y[ylen - 2]; 1384 1385 const sc_digit DOUBLE_BITS_PER_BYTE = 2 * BITS_PER_BYTE; 1386 1387 // Find each q[k]. 1388 for (int k = xlen - ylen; k >= 0; --k) { 1389 // qk is a guess for q[k] such that q[k] = qk or qk - 1. 1390 sc_digit qk; 1391 1392 // Find qk by just using 2 digits of y and 3 digits of x. The 1393 // following code assumes that sizeof(sc_digit) >= 3 BYTEs. 1394 int k2 = k + ylen; 1395 1396 qk = ((x[k2] << DOUBLE_BITS_PER_BYTE) + 1397 (x[k2 - 1] << BITS_PER_BYTE) + x[k2 - 2]) / y2; 1398 1399 if (qk >= BYTE_RADIX) // qk cannot be larger than the largest 1400 qk = BYTE_RADIX - 1; // digit in BYTE_RADIX. 1401 1402 // q[k] = qk or qk - 1. The following if-statement determines which. 1403 if (qk) { 1404 uchar *xk = (x + k); // A shortcut for x[k]. 1405 1406 // x = x - y * qk; 1407 sc_digit carry = 0; 1408 1409 for (int i = 0; i < ylen; ++i) { 1410 carry += y[i] * qk; 1411 sc_digit diff = (xk[i] + BYTE_RADIX) - (carry & BYTE_MASK); 1412 xk[i] = (uchar)(diff & BYTE_MASK); 1413 carry = (carry >> BITS_PER_BYTE) + 1414 (1 - (diff >> BITS_PER_BYTE)); 1415 } 1416 1417 if (carry) { 1418 // 2's complement the last digit. 1419 carry = (xk[ylen] + BYTE_RADIX) - carry; 1420 xk[ylen] = (uchar)(carry & BYTE_MASK); 1421 carry = 1 - (carry >> BITS_PER_BYTE); 1422 1423 if (carry) { 1424 // qk was one too large, so decrement it. 1425 // --qk; 1426 1427 // x = x - y * (qk - 1) = x - y * qk + y = x_above + y. 1428 carry = 0; 1429 1430 for (int i = 0; i < ylen; ++i) { 1431 carry += xk[i] + y[i]; 1432 xk[i] = (uchar)(carry & BYTE_MASK); 1433 carry >>= BITS_PER_BYTE; 1434 } 1435 1436 if (carry) 1437 xk[ylen] = (uchar)((xk[ylen] + 1) & BYTE_MASK); 1438 } // second if carry 1439 } // first if carry 1440 } // if qk 1441 } // for k 1442 1443 // Set (sc_digit) w = (uchar) x for the remainder. 1444 vec_from_char(ylen, x, ulen, w); 1445 1446#ifndef SC_MAX_NBITS 1447 delete [] x; 1448 delete [] y; 1449#endif 1450 1451} 1452 1453// Compute r = u % v, where u is a vector, and r and v are scalars. 1454// - 0 < v < HALF_DIGIT_RADIX. 1455// - The remainder r is returned. 1456sc_digit 1457vec_rem_small(int ulen, const sc_digit *u, sc_digit v) 1458{ 1459 1460#ifdef DEBUG_SYSTEMC 1461 sc_assert((ulen > 0) && (u != NULL)); 1462 sc_assert((0 < v) && (v < HALF_DIGIT_RADIX)); 1463#endif 1464 1465 // This function is adapted from vec_div_small(). 1466 1467 sc_digit r = 0; 1468 const sc_digit *ubegin = u; 1469 1470 u += ulen; 1471 1472 while (ubegin < u) { 1473 sc_digit u_AB = (*--u); // A|B 1474#ifdef DEBUG_SYSTEMC 1475 // The overflow bits must be zero. 1476 sc_assert(high_half(u_AB) == high_half_masked(u_AB)); 1477#endif 1478 // r = (((r|A) % v)|B) % v 1479 r = (concat(((concat(r, high_half(u_AB))) % v), low_half(u_AB))) % v; 1480 } 1481 1482 return r; 1483} 1484 1485// u = u / v, r = u % v. 1486sc_digit 1487vec_rem_on_small(int ulen, sc_digit *u, sc_digit v) 1488{ 1489#ifdef DEBUG_SYSTEMC 1490 sc_assert((ulen > 0) && (u != NULL)); 1491 sc_assert(v > 0); 1492#endif 1493 1494#define q_h r 1495 sc_digit r = 0; 1496 const sc_digit *ubegin = u; 1497 1498 u += ulen; 1499 while (ubegin < u) { 1500 sc_digit u_AB = (*--u); // A|B 1501#ifdef DEBUG_SYSTEMC 1502 // The overflow bits must be zero. 1503 sc_assert(high_half(u_AB) == high_half_masked(u_AB)); 1504#endif 1505 sc_digit num = concat(r, high_half(u_AB)); // num = r|A 1506 q_h = num / v; // C 1507 num = concat((num % v), low_half(u_AB)); // num = (((r|A) % v)|B) 1508 (*u) = concat(q_h, num / v); // q = C|D 1509 r = num % v; 1510 } 1511#undef q_h 1512 return r; 1513} 1514 1515// Set (uchar) v = (sc_digit) u. Return the new vlen. 1516int 1517vec_to_char(int ulen, const sc_digit *u, int vlen, uchar *v) 1518{ 1519#ifdef DEBUG_SYSTEMC 1520 sc_assert((ulen > 0) && (u != NULL)); 1521 sc_assert((vlen > 0) && (v != NULL)); 1522#endif 1523 1524 int nbits = ulen * BITS_PER_DIGIT; 1525 int right = 0; 1526 int left = right + BITS_PER_BYTE - 1; 1527 1528 vlen = 0; 1529 while (nbits > 0) { 1530 int left_digit = left / BITS_PER_DIGIT; 1531 int right_digit = right / BITS_PER_DIGIT; 1532 int nsr = ((vlen << LOG2_BITS_PER_BYTE) % BITS_PER_DIGIT); 1533 int d = u[right_digit] >> nsr; 1534 1535 if (left_digit != right_digit) { 1536 if (left_digit < ulen) 1537 d |= u[left_digit] << (BITS_PER_DIGIT - nsr); 1538 } 1539 1540 v[vlen++] = (uchar)(d & BYTE_MASK); 1541 1542 left += BITS_PER_BYTE; 1543 right += BITS_PER_BYTE; 1544 nbits -= BITS_PER_BYTE; 1545 } 1546 return vlen; 1547} 1548 1549// Set (sc_digit) v = (uchar) u. 1550// - sizeof(uchar) <= sizeof(sc_digit), 1551void 1552vec_from_char(int ulen, const uchar *u, int vlen, sc_digit *v) 1553{ 1554#ifdef DEBUG_SYSTEMC 1555 sc_assert((ulen > 0) && (u != NULL)); 1556 sc_assert((vlen > 0) && (v != NULL)); 1557 sc_assert(sizeof(uchar) <= sizeof(sc_digit)); 1558#endif 1559 1560 sc_digit *vend = (v + vlen); 1561 1562 const int nsr = BITS_PER_DIGIT - BITS_PER_BYTE; 1563 const sc_digit mask = one_and_ones(nsr); 1564 1565 (*v) = (sc_digit) u[ulen - 1]; 1566 1567 for (int i = ulen - 2; i >= 0; --i) { 1568 // Manual inlining of vec_shift_left(). 1569 sc_digit *viter = v; 1570 sc_digit carry = 0; 1571 while (viter < vend) { 1572 sc_digit vval = (*viter); 1573 (*viter++) = (((vval & mask) << BITS_PER_BYTE) | carry); 1574 carry = vval >> nsr; 1575 } 1576 1577 if (viter < vend) 1578 (*viter) = carry; 1579 1580 (*v) |= (sc_digit)u[i]; 1581 } 1582} 1583 1584// Set u <<= nsl. 1585// If nsl is negative, it is ignored. 1586void 1587vec_shift_left(int ulen, sc_digit *u, int nsl) 1588{ 1589#ifdef DEBUG_SYSTEMC 1590 sc_assert((ulen > 0) && (u != NULL)); 1591#endif 1592 1593 if (nsl <= 0) 1594 return; 1595 1596 // Shift left whole digits if nsl is large enough. 1597 if (nsl >= (int) BITS_PER_DIGIT) { 1598 int nd; 1599 if (nsl % BITS_PER_DIGIT == 0) { 1600 nd = nsl / BITS_PER_DIGIT; // No need to use DIV_CEIL(nsl). 1601 nsl = 0; 1602 } else { 1603 nd = DIV_CEIL(nsl) - 1; 1604 nsl -= nd * BITS_PER_DIGIT; 1605 } 1606 1607 if (nd) { 1608 // Shift left for nd digits. 1609 for (int j = ulen - 1; j >= nd; --j) 1610 u[j] = u[j - nd]; 1611 1612 vec_zero(sc_min(nd, ulen), u); 1613 } 1614 if (nsl == 0) 1615 return; 1616 } 1617 1618 // Shift left if nsl < BITS_PER_DIGIT. 1619 sc_digit *uiter = u; 1620 sc_digit *uend = uiter + ulen; 1621 1622 int nsr = BITS_PER_DIGIT - nsl; 1623 sc_digit mask = one_and_ones(nsr); 1624 1625 sc_digit carry = 0; 1626 1627 while (uiter < uend) { 1628 sc_digit uval = (*uiter); 1629 (*uiter++) = (((uval & mask) << nsl) | carry); 1630 carry = uval >> nsr; 1631 } 1632 1633 if (uiter < uend) 1634 (*uiter) = carry; 1635} 1636 1637// Set u >>= nsr. 1638// If nsr is negative, it is ignored. 1639void 1640vec_shift_right(int ulen, sc_digit *u, int nsr, sc_digit fill) 1641{ 1642#ifdef DEBUG_SYSTEMC 1643 sc_assert((ulen > 0) && (u != NULL)); 1644#endif 1645 1646 // fill is usually either 0 or DIGIT_MASK; it can be any value. 1647 if (nsr <= 0) 1648 return; 1649 1650 // Shift right whole digits if nsr is large enough. 1651 if (nsr >= (int) BITS_PER_DIGIT) { 1652 int nd; 1653 if (nsr % BITS_PER_DIGIT == 0) { 1654 nd = nsr / BITS_PER_DIGIT; 1655 nsr = 0; 1656 } else { 1657 nd = DIV_CEIL(nsr) - 1; 1658 nsr -= nd * BITS_PER_DIGIT; 1659 } 1660 1661 if (nd) { 1662 // Shift right for nd digits. 1663 for (int j = 0; j < (ulen - nd); ++j) 1664 u[j] = u[j + nd]; 1665 1666 if (fill) { 1667 for (int j = ulen - sc_min( nd, ulen ); j < ulen; ++j) 1668 u[j] = fill; 1669 } else { 1670 vec_zero(ulen - sc_min( nd, ulen ), ulen, u); 1671 } 1672 } 1673 if (nsr == 0) 1674 return; 1675 } 1676 1677 // Shift right if nsr < BITS_PER_DIGIT. 1678 sc_digit *ubegin = u; 1679 sc_digit *uiter = (ubegin + ulen); 1680 1681 int nsl = BITS_PER_DIGIT - nsr; 1682 sc_digit mask = one_and_ones(nsr); 1683 1684 sc_digit carry = (fill & mask) << nsl; 1685 1686 while (ubegin < uiter) { 1687 sc_digit uval = (*--uiter); 1688 (*uiter) = (uval >> nsr) | carry; 1689 carry = (uval & mask) << nsl; 1690 } 1691} 1692 1693 1694// Let u[l..r], where l and r are left and right bit positions 1695// respectively, be equal to its mirror image. 1696void 1697vec_reverse(int unb, int und, sc_digit *ud, int l, int r) 1698{ 1699#ifdef DEBUG_SYSTEMC 1700 sc_assert((unb > 0) && (und > 0) && (ud != NULL)); 1701 sc_assert((0 <= r) && (r <= l) && (l < unb)); 1702#endif 1703 1704 if (l < r) { 1705 std::stringstream msg; 1706 msg << "vec_reverse( int, int, sc_digit*, int l, int r ) : " << 1707 "l = " << l << " < r = " << r << " is not valid", 1708 SC_REPORT_ERROR(sc_core::SC_ID_CONVERSION_FAILED_, msg.str().c_str()); 1709 return; 1710 } 1711 1712 // Make sure that l and r are within bounds. 1713 r = sc_max(r, 0); 1714 l = sc_min(l, unb - 1); 1715 1716 // Allocate memory for processing. 1717#ifdef SC_MAX_NBITS 1718 sc_digit d[MAX_NDIGITS]; 1719#else 1720 sc_digit *d = new sc_digit[und]; 1721#endif 1722 1723 // d is a copy of ud. 1724 vec_copy(und, d, ud); 1725 1726 // Based on the value of the ith in d, find the value of the jth bit 1727 // in ud. 1728 for (int i = l, j = r; i >= r; --i, ++j) { 1729 if ((d[digit_ord(i)] & one_and_zeros(bit_ord(i))) != 0) // Test. 1730 ud[digit_ord(j)] |= one_and_zeros(bit_ord(j)); // Set. 1731 else 1732 ud[digit_ord(j)] &= ~(one_and_zeros(bit_ord(j))); // Clear. 1733 } 1734 1735#ifndef SC_MAX_NBITS 1736 delete [] d; 1737#endif 1738} 1739 1740#ifdef SC_MAX_NBITS 1741void test_bound_failed(int nb) 1742{ 1743 std::stringstream msg; 1744 msg << "test_bound( int nb ) : " 1745 "nb = " << nb << " > SC_MAX_NBITS = " << SC_MAX_NBITS << 1746 " is not valid"; 1747 SC_REPORT_ERROR(sc_core::SC_ID_OUT_OF_BOUNDS_, msg.str().c_str()); 1748} 1749#endif // SC_MAX_NBITS 1750 1751} // namespace sc_dt 1752