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