sc_nbutils.cc revision 12854
111077SCurtis.Dunham@arm.com/***************************************************************************** 211077SCurtis.Dunham@arm.com 311077SCurtis.Dunham@arm.com Licensed to Accellera Systems Initiative Inc. (Accellera) under one or 411077SCurtis.Dunham@arm.com more contributor license agreements. See the NOTICE file distributed 511077SCurtis.Dunham@arm.com with this work for additional information regarding copyright ownership. 611077SCurtis.Dunham@arm.com Accellera licenses this file to you under the Apache License, Version 2.0 711077SCurtis.Dunham@arm.com (the "License"); you may not use this file except in compliance with the 811077SCurtis.Dunham@arm.com License. You may obtain a copy of the License at 911077SCurtis.Dunham@arm.com 1011077SCurtis.Dunham@arm.com http://www.apache.org/licenses/LICENSE-2.0 1111077SCurtis.Dunham@arm.com 1211077SCurtis.Dunham@arm.com Unless required by applicable law or agreed to in writing, software 1311077SCurtis.Dunham@arm.com distributed under the License is distributed on an "AS IS" BASIS, 1411077SCurtis.Dunham@arm.com WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or 1511077SCurtis.Dunham@arm.com implied. See the License for the specific language governing 1611077SCurtis.Dunham@arm.com permissions and limitations under the License. 1711077SCurtis.Dunham@arm.com 1811077SCurtis.Dunham@arm.com *****************************************************************************/ 1911077SCurtis.Dunham@arm.com 2011077SCurtis.Dunham@arm.com/***************************************************************************** 2111077SCurtis.Dunham@arm.com 2211077SCurtis.Dunham@arm.com sc_nbutils.cpp -- External and friend functions for both sc_signed and 2311077SCurtis.Dunham@arm.com sc_unsigned classes. 2411077SCurtis.Dunham@arm.com 2511077SCurtis.Dunham@arm.com Original Author: Ali Dasdan, Synopsys, Inc. 2611077SCurtis.Dunham@arm.com 2711077SCurtis.Dunham@arm.com *****************************************************************************/ 2811077SCurtis.Dunham@arm.com 2911077SCurtis.Dunham@arm.com/***************************************************************************** 3011077SCurtis.Dunham@arm.com 3111077SCurtis.Dunham@arm.com MODIFICATION LOG - modifiers, enter your name, affiliation, date and 3211077SCurtis.Dunham@arm.com 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("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