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