Synopsis - Cross-Reference

  1// -*- c++ -*-
  2//                          Package   : omniidl
  3// idlfixed.h               Created on: 2001/01/31
  4//			    Author    : Duncan Grisby (dpg1)
  5//
  6//    Copyright (C) 2001 AT&T Laboratories Cambridge
  7//
  8//  This file is part of omniidl.
  9//
 10//  omniidl is free software; you can redistribute it and/or modify it
 11//  under the terms of the GNU General Public License as published by
 12//  the Free Software Foundation; either version 2 of the License, or
 13//  (at your option) any later version.
 14//
 15//  This program is distributed in the hope that it will be useful,
 16//  but WITHOUT ANY WARRANTY; without even the implied warranty of
 17//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 18//  General Public License for more details.
 19//
 20//  You should have received a copy of the GNU General Public License
 21//  along with this program; if not, write to the Free Software
 22//  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
 23//  02111-1307, USA.
 24//
 25// Description:
 26//   
 27//   Implementation of fixed point type
 28
 29/*
 30  $Log: idlfixed.cc,v $
 31  Revision 1.1.4.2  2005/03/30 23:35:57  dgrisby
 32  Another merge from omni4_0_develop.
 33
 34  Revision 1.1.4.1  2003/03/23 21:01:45  dgrisby
 35  Start of omniORB 4.1.x development branch.
 36
 37  Revision 1.1.2.1  2001/03/13 10:32:12  dpg1
 38  Fixed point support.
 39
 40*/
 41
 42#include <idlfixed.h>
 43#include <idlutil.h>
 44#include <idlerr.h>
 45
 46#include <string.h>
 47
 48
 49IDL_Fixed::IDL_Fixed() :
 50  digits_(0), scale_(0), negative_(0)
 51{
 52  memset(val_, 0, OMNI_FIXED_DIGITS);
 53}
 54
 55
 56IDL_Fixed::IDL_Fixed(const IDL_Fixed& f) :
 57  digits_(f.digits_), scale_(f.scale_), negative_(f.negative_)
 58{
 59  memcpy(val_, f.val_, OMNI_FIXED_DIGITS);
 60}
 61
 62IDL_Fixed::IDL_Fixed(const char* s, const char* file, int line)
 63{
 64  // Sign (Actually redundant for omniidl. Here for completeness.)
 65  if (s[0] == '-') {
 66    negative_ = 1;
 67    ++s;
 68  }
 69  else if (s[0] == '+') {
 70    negative_ = 0;
 71    ++s;
 72  }
 73  else
 74    negative_ = 0;
 75
 76  // Check there are some digits
 77  assert(*s != '\0' && *s != 'd' && *s != 'D');
 78
 79  // Skip leading zeros:
 80  while (*s == '0') ++s;
 81
 82  int i, j, unscale = -1;
 83
 84  // Count digits
 85  for (i=0, digits_=0; (s[i] >= '0' && s[i] <= '9') || s[i] == '.'; ++i) {
 86    if (s[i] == '.') {
 87      assert(unscale == -1);
 88      unscale = digits_;
 89    }
 90    else
 91      ++digits_;
 92  }
 93  if (unscale == -1)
 94    unscale = digits_;
 95
 96  scale_ = digits_ - unscale;
 97
 98  // Check there is no trailing garbage
 99  if (s[i] == 'd' || s[i] == 'D')
100    assert(s[i+1] == '\0');
101  else
102    assert(s[i] == '\0');
103
104  --i; // i is now the index of the last digit
105
106  // Truncate if too many digits
107  while (digits_ > OMNI_FIXED_DIGITS && scale_ > 0) {
108    --i; --digits_; --scale_;
109  }
110
111  // Back-up over trailing zeros
112  if (scale_ > 0) {
113    while (s[i] == '0') {
114      --i; --digits_; --scale_;
115    }
116  }
117
118  if (digits_ > OMNI_FIXED_DIGITS) {
119    if (file) {
120      IdlError(file, line, "Fixed point constant has too many digits");
121    }
122    *this = IDL_Fixed("1");
123    return;
124  }
125
126  for (j=0; j < digits_; ++j, --i) {
127    if (s[i] == '.') --i;
128    val_[j] = s[i] - '0';
129  }
130  for (; j < OMNI_FIXED_DIGITS; ++j)
131    val_[j] = 0;
132
133  if (digits_ == 0) negative_ = 0;
134}
135
136IDL_Fixed::IDL_Fixed(const IDL_Octet* val, IDL_UShort digits,
137		     IDL_UShort scale, IDL_Boolean negative)
138  : digits_(digits), scale_(scale), negative_(negative)
139{
140  assert(digits <= OMNI_FIXED_DIGITS);
141  assert(scale  <= digits);
142
143  while (digits_ > 0 && scale_ > 0 && val[0] == 0) {
144    digits_--;
145    scale_--;
146    val++;
147  }
148
149  if (digits_ == 0) negative_ = 0;
150
151  memcpy(val_, val, digits_);
152  memset(val_ + digits_, 0, OMNI_FIXED_DIGITS - digits_);
153}
154
155
156IDL_Fixed::~IDL_Fixed()
157{
158}
159
160
161IDL_Fixed
162IDL_Fixed::truncate(IDL_UShort scale)
163{
164  if (scale >= scale_)
165    return *this;
166
167  int cut      = scale_ - scale;
168  int newscale = scale;
169
170  while (val_[cut] == 0 && newscale > 0) {
171    ++cut;
172    --newscale;
173  }
174
175  return IDL_Fixed(val_ + cut, digits_ - cut, newscale, negative_);
176}
177
178
179
180IDL_Fixed&
181IDL_Fixed::operator=(const IDL_Fixed& f)
182{
183  digits_   = f.digits_;
184  scale_    = f.scale_;
185  negative_ = f.negative_;
186  memcpy(val_, f.val_, OMNI_FIXED_DIGITS);
187  return *this;
188}
189
190IDL_Fixed
191IDL_Fixed::operator-() const
192{
193  if (digits_ == 0) return *this;
194
195  IDL_Fixed r(*this);
196  r.negative_ = !r.negative_;
197  return r;
198}
199
200
201char*
202IDL_Fixed::asString() const
203{
204  int len = digits_ + 1;
205  if (negative_)         ++len; // for '-'
206  if (digits_ == scale_) ++len; // for '0'
207  if (scale_ > 0)        ++len; // for '.'
208
209  char* r = new char[len];
210  int i = 0, j;
211
212  if (negative_)         r[i++] = '-';
213  if (digits_ == scale_) r[i++] = '0';
214
215  for (j=digits_; j; ) {
216    if (j-- == scale_)
217      r[i++] = '.';
218    r[i++] = val_[j] + '0';
219  }
220  r[i] = '\0';
221  return r;
222}
223
224
225
226
227// Functions which do the real arithmetic
228
229
230static int
231absCmp(const IDL_Fixed& a, const IDL_Fixed& b)
232{
233  int c;
234  c = (a.fixed_digits()-a.fixed_scale()) - (b.fixed_digits()-b.fixed_scale());
235  if (c) return c;
236
237  int ai, bi;
238  ai = a.fixed_digits() - 1;
239  bi = b.fixed_digits() - 1;
240
241  while (ai >= 0 && bi >= 0) {
242    c = a.val()[ai] - b.val()[bi];
243    if (c) return c;
244    --ai; --bi;
245  }
246  if (ai >= 0) return  1;
247  if (bi >= 0) return -1;
248  return 0;
249}
250
251
252static IDL_Fixed
253realAdd(const IDL_Fixed& a, const IDL_Fixed& b, IDL_Boolean negative)
254{
255  int scale, v, carry = 0, ai = 0, bi = 0, wi = 0;
256  IDL_Octet work[OMNI_FIXED_DIGITS * 2];
257
258  if (a.fixed_scale() > b.fixed_scale()) {
259    scale = a.fixed_scale();
260
261    while (ai < a.fixed_scale() - b.fixed_scale())
262      work[wi++] = a.val()[ai++];
263  }
264  else if (b.fixed_scale() > a.fixed_scale()) {
265    scale = b.fixed_scale();
266
267    while (bi < b.fixed_scale() - a.fixed_scale())
268      work[wi++] = b.val()[bi++];
269  }
270  else
271    scale = a.fixed_scale();
272
273  while (ai < a.fixed_digits() && bi < b.fixed_digits()) {
274    v = a.val()[ai++] + b.val()[bi++] + carry;
275    if (v > 9) {
276      carry = 1; v -= 10;
277    }
278    else carry = 0;
279    work[wi++] = v;
280  }
281  while (ai < a.fixed_digits()) {
282    v = a.val()[ai++] + carry;
283    if (v > 9) {
284      carry = 1; v -= 10;
285    }
286    else carry = 0;
287    work[wi++] = v;
288  }
289  while (bi < b.fixed_digits()) {
290    v = b.val()[bi++] + carry;
291    if (v > 9) {
292      carry = 1; v -= 10;
293    }
294    else carry = 0;
295    work[wi++] = v;
296  }
297  if (carry) {
298    work[wi++] = carry;
299  }
300
301  IDL_Octet* wp = work;
302  int digits = wi;
303
304  // Truncate or complain if too many digits
305  if (digits > OMNI_FIXED_DIGITS) {
306    if (digits - scale <= OMNI_FIXED_DIGITS) {
307      int chop  = digits - OMNI_FIXED_DIGITS;
308      wp       += chop;
309      scale    -= chop;
310      digits    = OMNI_FIXED_DIGITS;
311    }
312    else
313      throw IDL_Fixed::Overflow();
314  }
315
316  // Strip trailing zeros
317  while (scale > 0 && *wp == 0) {
318    ++wp; --scale; --digits;
319  }
320  return IDL_Fixed(wp, digits, scale, negative);
321}
322
323static IDL_Fixed
324realSub(const IDL_Fixed& a, const IDL_Fixed& b, IDL_Boolean negative)
325{
326  int scale, v, carry = 0, ai = 0, bi = 0, wi = 0;
327  IDL_Octet work[OMNI_FIXED_DIGITS * 2];
328
329  if (a.fixed_scale() > b.fixed_scale()) {
330    scale = a.fixed_scale();
331
332    while (ai < a.fixed_scale() - b.fixed_scale())
333      work[wi++] = a.val()[ai++];
334  }
335  else if (b.fixed_scale() > a.fixed_scale()) {
336    scale = b.fixed_scale();
337
338    while (bi < b.fixed_scale() - a.fixed_scale()) {
339      work[wi++] = 10 - b.val()[bi++] + carry;
340      carry = -1;
341    }
342  }
343  else
344    scale = a.fixed_scale();
345
346  while (ai < a.fixed_digits() && bi < b.fixed_digits()) {
347    v = a.val()[ai++] - b.val()[bi++] + carry;
348    if (v < 0) {
349      carry = -1; v += 10;
350    }
351    else carry = 0;
352    work[wi++] = v;
353  }
354  while (ai < a.fixed_digits()) {
355    v = a.val()[ai++] + carry;
356    if (v < 0) {
357      carry = -1; v += 10;
358    }
359    else carry = 0;
360    work[wi++] = v;
361  }
362  assert(bi == b.fixed_digits());
363  assert(carry == 0);
364
365  int digits = wi;
366  IDL_Octet* wp = work;
367
368  // Strip leading zeros
369  while (work[digits-1] == 0 && digits > scale)
370    --digits;
371
372  // Truncate or complain if too many digits
373  if (digits > OMNI_FIXED_DIGITS) {
374    assert(digits - scale <= OMNI_FIXED_DIGITS);
375
376    int chop  = digits - OMNI_FIXED_DIGITS;
377    wp       += chop;
378    scale    -= chop;
379    digits    = OMNI_FIXED_DIGITS;
380  }
381
382  // Strip trailing zeros
383  while (scale > 0 && *wp == 0) {
384    ++wp; --scale; --digits;
385  }
386
387  return IDL_Fixed(wp, digits, scale, negative);
388}
389
390
391static IDL_Fixed
392realMul(const IDL_Fixed& a, const IDL_Fixed& b, IDL_Boolean negative)
393{
394  int ai, bi, wi, digits, scale, v, ad, bd, carry = 0;
395  IDL_Octet work[OMNI_FIXED_DIGITS * 2];
396
397  memset(work, 0, OMNI_FIXED_DIGITS * 2);
398
399  scale = a.fixed_scale() + b.fixed_scale();
400
401  for (ai=0, wi=0; ai < a.fixed_digits(); ++ai) {
402    ad = a.val()[ai];
403    if (ad == 0) continue;
404
405    for (bi=0; bi < b.fixed_digits(); ++bi) {
406      bd = b.val()[bi];
407      if (bd == 0 && carry == 0) continue;
408      wi       = ai + bi;
409      v        = work[wi] + ad * bd + carry;
410      carry    = v / 10;
411      work[wi] = v % 10;
412    }
413    while (carry) {
414      ++wi;
415      v        = work[wi] + carry;
416      carry    = v / 10;
417      work[wi] = v % 10;
418    }
419  }
420  digits = wi+1;
421  if (scale > digits) digits = scale;
422
423  // Truncate or complain if too many digits
424  IDL_Octet* wp = work;
425  if (digits > OMNI_FIXED_DIGITS) {
426    if (digits - scale <= OMNI_FIXED_DIGITS) {
427      int chop  = digits - OMNI_FIXED_DIGITS;
428      wp       += chop;
429      scale    -= chop;
430      digits    = OMNI_FIXED_DIGITS;
431    }
432    else
433      throw IDL_Fixed::Overflow();
434  }
435
436  // Strip trailing zeros
437  while (scale > 0 && *wp == 0) {
438    ++wp; --scale; --digits;
439  }
440
441  return IDL_Fixed(wp, digits, scale, negative);
442}
443
444
445static int
446divCmp(const IDL_Octet* av, int ad, const IDL_Octet* bv, int bd, int pos)
447{
448  int c, ai, bi;
449
450  for (ai = ad-1; ai > pos; --ai) {
451    if (av[ai])
452      return 1;
453  }
454  ai = pos;
455  bi = bd - 1;
456  assert(ai >= bi);
457  while (bi >= 0) {
458    c = av[ai] - bv[bi];
459    if (c) return c;
460    --ai; --bi;
461  }
462  return 0;
463}
464
465
466static int
467divDigit(IDL_Octet* av, int ad, const IDL_Octet* bv, int bd, int pos)
468{
469  int ai, bi, carry, v, count = 0;
470  while (divCmp(av, ad, bv, bd, pos) >= 0) {
471    ++count;
472    carry = 0;
473
474    ai = pos - bd + 1;
475    bi = 0;
476    while (bi < bd) {
477      v = av[ai] - bv[bi] + carry;
478      if (v < 0) {
479	carry = -1;
480	v += 10;
481      }
482      else
483	carry = 0;
484      av[ai] = v;
485      ++ai;
486      ++bi;
487    }
488    while (ai < ad) {
489      v = av[ai] + carry;
490      if (v < 0) {
491	carry = -1;
492	v += 10;
493      }
494      else
495	carry = 0;
496      av[ai] = v;
497      ++ai;
498    }
499  }
500  assert(count < 10);
501  return count;
502}
503
504
505static IDL_Fixed
506realDiv(const IDL_Fixed& a, const IDL_Fixed& b, IDL_Boolean negative)
507{
508  int i, ai, bi, wi, ri, digits, scale, unscale, v, ad, bd, carry = 0;
509
510  // This division algorithm basically does classic long division. The
511  // numerator, a, is loaded into the top digits of "running". The
512  // divisor, b, is then repeatedly subtracted from the top digits of
513  // "running" until it can no longer be subtracted without becoming
514  // negative. The count of subtractions forms the top digit of the
515  // result. Then the next digit is found by shifting the divisor down
516  // one digit, and repeating, and so on.
517  //
518  // The ugliness all comes because we need to figure out where to put
519  // the decimal point. It would be easy if it wasn't for the fact
520  // that values with scale > digits are not permitted. This means
521  // that if the result is going to be of that form, some initial zero
522  // digits have to be included.
523
524  IDL_Octet work   [OMNI_FIXED_DIGITS * 2];
525  IDL_Octet running[OMNI_FIXED_DIGITS * 2];
526
527  memset(work,    0, OMNI_FIXED_DIGITS * 2);
528  memset(running, 0, OMNI_FIXED_DIGITS * 2);
529
530  // Skip all leading zeros in a
531  ad = a.fixed_digits();
532  while (a.val()[ad - 1] == 0) --ad;
533
534  // Set most siginificant digits of running to a's digits
535  ri = OMNI_FIXED_DIGITS * 2 - 1;
536  ai = ad - 1;
537  while (ai >= 0) {
538    running[ri] = a.val()[ai];
539    --ri;
540    --ai;
541  }
542
543  // Skip all leading zeros in b
544  bd = b.fixed_digits();
545  while (b.val()[bd - 1] == 0) --bd;
546
547  // unscale = number of digits to left of decimal point in answer
548  unscale = (ad - a.fixed_scale()) - (bd - b.fixed_scale()) + 1;
549  digits  = 0;
550
551  // Set some initial zero digits to prevent scale > digits
552  if (unscale < 0)
553    digits  = -unscale;
554
555  ri = OMNI_FIXED_DIGITS * 2 - 1;
556  wi = ri - digits;
557
558  // Iterate to work out the result digits
559  while (digits < OMNI_FIXED_DIGITS) {
560
561    // Finish if running is zero
562    for (i=0; i < OMNI_FIXED_DIGITS*2 && running[i] == 0; ++i);
563    if (i == OMNI_FIXED_DIGITS * 2)
564      break;
565
566    work[wi] = divDigit(running, OMNI_FIXED_DIGITS * 2, b.val(), bd, ri);
567
568    if (digits || work[wi])
569      ++digits;
570
571    --wi; --ri;
572  }
573  wi = OMNI_FIXED_DIGITS * 2 - 1;
574
575  // Skip an initial zero if we weren't expecting one
576  if (unscale >= 0) {
577    while (work[wi] == 0 && unscale > 0) {
578      --wi; --unscale;
579    }
580  }
581  else
582    unscale = 0;
583
584  // Complain if too many digits before decimal point
585  if (unscale > OMNI_FIXED_DIGITS)
586    throw IDL_Fixed::Overflow();
587
588  // Deal with numbers with trailing zeros before the decimal point
589  if (digits < unscale)
590    digits = unscale;
591
592  IDL_Octet* wp = &work[wi - digits + 1];
593
594  // Figure out scale
595  scale = digits - unscale;
596  if (digits < scale)
597    digits = scale;
598
599  // Strip trailing zeros
600  while (scale > 0 && *wp == 0) {
601    ++wp; --scale; --digits;
602  }
603
604  return IDL_Fixed(wp, digits, scale, negative);
605}
606
607
608//
609// Operators
610//
611
612IDL_Fixed
613operator+(const IDL_Fixed& a, const IDL_Fixed& b)
614{
615  if (a.negative() == b.negative())
616    return realAdd(a, b, a.negative());
617
618  int cmp = absCmp(a, b);
619
620  if (cmp == 0)     // a == b
621    return IDL_Fixed();
622  else if (cmp > 0) // a > b
623    return realSub(a, b, a.negative());
624  else
625    return realSub(b, a, b.negative());
626}
627
628IDL_Fixed
629operator-(const IDL_Fixed& a, const IDL_Fixed& b)
630{
631  if (a.negative() != b.negative())
632    return realAdd(a, b, a.negative());
633
634  int cmp = absCmp(a, b);
635
636  if (cmp == 0)     // a == b
637    return IDL_Fixed();
638  else if (cmp > 0) // a > b
639    return realSub(a, b, a.negative());
640  else
641    return realSub(b, a, !a.negative());
642}
643
644IDL_Fixed
645operator*(const IDL_Fixed& a, const IDL_Fixed& b)
646{
647  if (a.fixed_digits() == 0 || b.fixed_digits() == 0)
648    return IDL_Fixed();
649
650  if (a.negative() == b.negative())
651    return realMul(a, b, 0);
652  else
653    return realMul(a, b, 1);
654}
655
656IDL_Fixed
657operator/(const IDL_Fixed& a, const IDL_Fixed& b)
658{
659  if (b.fixed_digits() == 0)
660    throw IDL_Fixed::DivideByZero();
661
662  if (a.fixed_digits() == 0)
663    return IDL_Fixed();
664
665  if (a.negative() == b.negative())
666    return realDiv(a, b, 0);
667  else
668    return realDiv(a, b, 1);
669}
670