sc_nbutils.cpp revision 12027
112855Sgabeblack@google.com/***************************************************************************** 212855Sgabeblack@google.com 312855Sgabeblack@google.com Licensed to Accellera Systems Initiative Inc. (Accellera) under one or 412855Sgabeblack@google.com more contributor license agreements. See the NOTICE file distributed 512855Sgabeblack@google.com with this work for additional information regarding copyright ownership. 612855Sgabeblack@google.com Accellera licenses this file to you under the Apache License, Version 2.0 712855Sgabeblack@google.com (the "License"); you may not use this file except in compliance with the 812855Sgabeblack@google.com License. You may obtain a copy of the License at 912855Sgabeblack@google.com 1012855Sgabeblack@google.com http://www.apache.org/licenses/LICENSE-2.0 1112855Sgabeblack@google.com 1212855Sgabeblack@google.com Unless required by applicable law or agreed to in writing, software 1312855Sgabeblack@google.com distributed under the License is distributed on an "AS IS" BASIS, 1412855Sgabeblack@google.com WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or 1512855Sgabeblack@google.com implied. See the License for the specific language governing 1612855Sgabeblack@google.com permissions and limitations under the License. 1712855Sgabeblack@google.com 1812855Sgabeblack@google.com *****************************************************************************/ 1912855Sgabeblack@google.com 2012855Sgabeblack@google.com/***************************************************************************** 2112855Sgabeblack@google.com 2212855Sgabeblack@google.com sc_nbutils.cpp -- External and friend functions for both sc_signed and 2312855Sgabeblack@google.com sc_unsigned classes. 2412855Sgabeblack@google.com 2512855Sgabeblack@google.com Original Author: Ali Dasdan, Synopsys, Inc. 2612855Sgabeblack@google.com 2712855Sgabeblack@google.com *****************************************************************************/ 2812855Sgabeblack@google.com 2912855Sgabeblack@google.com/***************************************************************************** 3012855Sgabeblack@google.com 3112855Sgabeblack@google.com MODIFICATION LOG - modifiers, enter your name, affiliation, date and 3212855Sgabeblack@google.com changes you are making here. 3312855Sgabeblack@google.com 3412855Sgabeblack@google.com Name, Affiliation, Date: 3512855Sgabeblack@google.com Description of Modification: 3612855Sgabeblack@google.com 3712855Sgabeblack@google.com *****************************************************************************/ 3812855Sgabeblack@google.com 3912855Sgabeblack@google.com 4012855Sgabeblack@google.com// $Log: sc_nbutils.cpp,v $ 4112855Sgabeblack@google.com// Revision 1.4 2011/08/24 22:05:46 acg 4212855Sgabeblack@google.com// Torsten Maehne: initialization changes to remove warnings. 4312855Sgabeblack@google.com// 4412855Sgabeblack@google.com// Revision 1.3 2011/02/18 20:19:15 acg 4512855Sgabeblack@google.com// Andy Goodrich: updating Copyright notice. 4612855Sgabeblack@google.com// 4712855Sgabeblack@google.com// Revision 1.2 2007/11/04 21:26:40 acg 4812855Sgabeblack@google.com// Andy Goodrich: added a buffer to the allocation of the q array to address 4912855Sgabeblack@google.com// an issue with references outside the array by 1 byte detected by valgrind. 5012855Sgabeblack@google.com// 5112855Sgabeblack@google.com// Revision 1.1.1.1 2006/12/15 20:20:05 acg 5212855Sgabeblack@google.com// SystemC 2.3 5312855Sgabeblack@google.com// 5412855Sgabeblack@google.com// Revision 1.3 2006/01/13 18:49:32 acg 5512855Sgabeblack@google.com// Added $Log command so that CVS check in comments are reproduced in the 5612855Sgabeblack@google.com// source. 5712855Sgabeblack@google.com// 5812855Sgabeblack@google.com 5912855Sgabeblack@google.com#include <ctype.h> 6012855Sgabeblack@google.com#include <cstdio> 6112855Sgabeblack@google.com#include <string.h> 6212855Sgabeblack@google.com 6312855Sgabeblack@google.com#include "sysc/datatypes/int/sc_int_ids.h" 6412855Sgabeblack@google.com#include "sysc/datatypes/int/sc_nbutils.h" 6512855Sgabeblack@google.com#include "sysc/kernel/sc_macros.h" 6612855Sgabeblack@google.com 6712855Sgabeblack@google.com 6812855Sgabeblack@google.comnamespace sc_dt 6912855Sgabeblack@google.com{ 7012855Sgabeblack@google.com 7112855Sgabeblack@google.com// ---------------------------------------------------------------------------- 7212855Sgabeblack@google.com// ENUM : sc_numrep 7312855Sgabeblack@google.com// 7412855Sgabeblack@google.com// Enumeration of number representations for character string conversion. 7512855Sgabeblack@google.com// ---------------------------------------------------------------------------- 7612855Sgabeblack@google.com 7712855Sgabeblack@google.comconst 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