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