home *** CD-ROM | disk | FTP | other *** search
/ GEMini Atari / GEMini_Atari_CD-ROM_Walnut_Creek_December_1993.iso / files / gnu / g__lib / fix.cc < prev    next >
Encoding:
C/C++ Source or Header  |  1993-07-23  |  10.8 KB  |  558 lines
  1. //
  2. // Fix.cc : variable length fixed point data type class functions
  3. //
  4.  
  5. #include <Fix.h>
  6. #include <Obstack.h>
  7. #include <std.h>
  8.  
  9. // default parameters
  10.  
  11. uint16 Fix_default_length = 16;
  12. int    Fix_default_print_width = 8;
  13.  
  14. Fix_peh Fix_overflow_handler = Fix_overflow_saturate;
  15.  
  16. _Frep _Frep_0    = { 16, 1, 1, { 0 } };
  17. _Frep _Frep_m1    = { 16, 1, 1, { 0x8000 } };
  18. _Frep _Frep_quotient_bump = { 16, 1, 1, { 0x4000 } };
  19.  
  20. // error handling
  21.  
  22. void default_Fix_error_handler(char* msg)
  23. {
  24.   cerr << "Fix: " << msg << "\n";
  25.   abort();
  26. }
  27.  
  28. void default_Fix_range_error_handler(char* msg)
  29. {
  30.   cerr << "Fix: range error in " << msg << "\n";
  31.   //abort();
  32. }
  33.  
  34. one_arg_error_handler_t 
  35.   Fix_error_handler = default_Fix_error_handler,
  36.   Fix_range_error_handler = default_Fix_range_error_handler;
  37.  
  38. one_arg_error_handler_t set_Fix_error_handler(one_arg_error_handler_t f)
  39. {
  40.   one_arg_error_handler_t old = Fix_error_handler;
  41.   Fix_error_handler = f;
  42.   return old;
  43. }
  44.  
  45. one_arg_error_handler_t set_Fix_range_error_handler(one_arg_error_handler_t f)
  46. {
  47.   one_arg_error_handler_t old = Fix_range_error_handler;
  48.   Fix_range_error_handler = f;
  49.   return old;
  50. }
  51.  
  52. void Fix::error(char* msg)
  53. {
  54.   (*Fix_error_handler)(msg);
  55. }
  56.  
  57. void Fix::range_error(char* msg)
  58. {
  59.   (*Fix_range_error_handler)(msg);
  60. }
  61.  
  62. // _Frep allocation and initialization functions
  63.  
  64. inline _Fix _new_Fix(uint16 len)
  65. {
  66.   int siz = ((uint32 )len + 15) >> 4;
  67.  
  68.   _Fix z = malloc(sizeof(_Frep) + (siz - 1) * sizeof(uint16));
  69.   if (z == 0)
  70.     (*Fix_error_handler)("out of memory");
  71.  
  72.   z->len = len;
  73.   z->siz = siz;
  74.   z->ref = 1;
  75.   return z;
  76. }
  77.  
  78. _Fix new_Fix(uint16 len)
  79. {
  80.   return _new_Fix(len);
  81. }
  82.  
  83. _Fix new_Fix(uint16 len, _Fix x)
  84. {
  85.   _Fix z = _new_Fix(len);
  86.   return copy(x,z);
  87. }
  88.  
  89. _Fix new_Fix(uint16 len, double d)
  90. {
  91.   _Fix z = _new_Fix(len);
  92.  
  93.   if ( d == _Fix_max_value )
  94.   {
  95.     z->s[0] = 0x7fff;
  96.     for ( int i=1; i < z->siz; i++ )
  97.       z->s[i] = 0xffff;
  98.   }
  99.   else if ( d < _Fix_min_value || d > _Fix_max_value )
  100.     (*Fix_range_error_handler)("declaration");
  101.   else
  102.   {
  103.     d *= 32768;
  104.     for ( int i=0; i < z->siz; i++ )
  105.     {
  106.       z->s[i] = (uint16 )d;
  107.       d -= z->s[i];
  108.       d *= 65536;
  109.     }
  110.     if ( d >= 32768 )
  111.       z->s[z->siz-1]++;
  112.   }
  113.   mask(z);
  114.   return z;
  115. }
  116.  
  117. // convert to a double 
  118.  
  119. double value(Fix& x)
  120. { 
  121.   double d = 0.0;
  122.   for ( int i=x.rep->siz-1; i >= 0; i-- )
  123.   {
  124.     d += x.rep->s[i];
  125.     d *= 1./65536.;
  126.   }
  127.   d *= 2.;
  128.   return d < 1. ? d : d - 2.;
  129. }
  130.  
  131. // extract mantissa to Integer
  132.  
  133. Integer mantissa(Fix& x)
  134. {
  135.   Integer a = 1, b=1;
  136.   for ( int i=0; i < x.rep->siz; i++ )
  137.     a = (a << 16) + x.rep->s[i], b <<= 16;
  138.   return a-b;
  139. }
  140.  
  141. // comparison functions
  142.   
  143. inline static int docmp(uint16* x, uint16* y, int siz)
  144. {
  145.   int diff = (int16 )*x - (int16 )*y;
  146.   while ( --siz && !diff )
  147.     diff = (int32 )(uint32 )*++x - (int32 )(uint32 )*++y;
  148.   return diff;
  149. }
  150.  
  151. inline static int docmpz(uint16* x, int siz)
  152. {
  153.   while ( siz-- )
  154.     if ( *x++ ) return 1;
  155.   return 0;
  156. }
  157.  
  158. int compare(_Fix x, _Fix y = &_Frep_0)
  159. {
  160.   if ( x->siz == y->siz )
  161.     return docmp(x->s, y->s, x->siz);
  162.   else
  163.   {
  164.     int r;
  165.     _Fix longer, shorter;
  166.     if ( x->siz > y->siz )
  167.     {
  168.       longer = x;
  169.       shorter = y;
  170.       r = 1;
  171.     }
  172.     else
  173.     {
  174.       longer = y;
  175.       shorter = x;
  176.       r = -1;
  177.     }
  178.     int diff = docmp(x->s, y->s, shorter->siz);
  179.     if ( diff )
  180.       return diff;
  181.     else if ( docmpz(&longer->s[shorter->siz], longer->siz-shorter->siz) )
  182.       return r;
  183.     else
  184.       return 0;
  185.   }
  186. }
  187.  
  188. // arithmetic functions
  189.  
  190. _Fix add(_Fix x, _Fix y, _Fix r = NULL)
  191. {
  192.   uint16 xsign = x->s[0], ysign = y->s[0];
  193.   _Fix longer, shorter;
  194.   if ( x->len >= y->len )
  195.     longer = x, shorter = y;
  196.   else
  197.     longer = y, shorter = x;
  198.   if ( r == NULL )
  199.     r = new_Fix(longer->len);
  200.   for ( int i=r->siz-1; i >= longer->siz; i-- )
  201.     r->s[i] = 0;
  202.   for ( ; i >= shorter->siz; i-- )
  203.     r->s[i] = longer->s[i];
  204.   uint32 sum, carry = 0;
  205.   for ( ; i >= 0; i-- )
  206.   {
  207.     sum = carry + (uint32 )x->s[i] + (uint32 )y->s[i];
  208.     carry = sum >> 16;
  209.     r->s[i] = sum;
  210.   }
  211.   if ( (xsign ^ sum) & (ysign ^ sum) & 0x8000 )
  212.     (*Fix_overflow_handler)(r);
  213.   return r;
  214. }
  215.  
  216. _Fix subtract(_Fix x, _Fix y, _Fix r = NULL)
  217. {
  218.   uint16 xsign = x->s[0], ysign = y->s[0];
  219.   _Fix longer, shorter;
  220.   if ( x->len >= y->len )
  221.     longer = x, shorter = y;
  222.   else
  223.     longer = y, shorter = x;
  224.   if ( r == NULL )
  225.     r = new_Fix(longer->len);
  226.   for ( int i=r->siz-1; i >= longer->siz; i-- )
  227.     r->s[i] = 0;
  228.   for ( ; i >= shorter->siz; i-- )
  229.     r->s[i] = (longer == x ? x->s[i] : -y->s[i]);
  230.   int16 carry = 0;
  231.   uint32 sum;
  232.   for ( ; i >= 0; i-- )
  233.   {
  234.     sum = (int32 )carry + (uint32 )x->s[i] - (uint32 )y->s[i];
  235.     carry = sum >> 16;
  236.     r->s[i] = sum;
  237.   }
  238.   if ( (xsign ^ sum) & (~ysign ^ sum) & 0x8000 )
  239.     (*Fix_overflow_handler)(r);
  240.   return r;
  241. }
  242.  
  243. _Fix multiply(_Fix x, _Fix y, _Fix r = NULL)
  244. {
  245.   if ( r == NULL )
  246.     r = new_Fix(x->len + y->len - 1);
  247.   int xsign = x->s[0] & 0x8000,
  248.     ysign = y->s[0] & 0x8000;
  249.   Fix X(x->len), Y(y->len);
  250.   if ( xsign )
  251.     x = negate(x,X.rep);
  252.   if ( ysign )
  253.     y = negate(y,Y.rep);
  254.   for ( int i=0; i < r->siz; i++ )
  255.     r->s[i] = 0;
  256.   for ( i=x->siz-1; i >= 0; i-- )
  257.   {
  258.     uint32 carry = 0;
  259.     for ( int j=y->siz-1; j >= 0; j-- ) 
  260.     {
  261.       int k = i + j + 1;
  262.       uint32 a = (uint32 )x->s[i] * (uint32 )y->s[j];
  263.       uint32 b = ((a << 1) & 0xffff) + carry;
  264.       if ( k < r->siz )
  265.       {
  266.     b += r->s[k];
  267.         r->s[k] = b;
  268.       }
  269.       if ( k < r->siz + 1 )
  270.         carry = (a >> 15) + (b >> 16);
  271.     }
  272.     r->s[i] = carry;
  273.   }
  274.   if ( xsign != ysign )
  275.     negate(r,r);
  276.   return r;
  277. }
  278.  
  279. _Fix multiply(_Fix x, int y, _Fix r = NULL )
  280. {
  281.   if ( y != (int16 )y )
  282.     (*Fix_range_error_handler)("multiply by int -- int too large");
  283.   if ( r == NULL )
  284.     r = new_Fix(x->len);
  285.   for ( int i=r->siz-1; i >= x->siz; i-- )
  286.     r->s[i] = 0;
  287.   int32 a, carry = 0;
  288.   for ( ; i > 0; i-- )
  289.   {
  290.     a = (int32 )(uint32 )x->s[i] * y + carry;
  291.     r->s[i] = a;
  292.     carry = a >> 16;        // assumes arithmetic right shift
  293.   }
  294.   a = (int32 )(int16 )x->s[0] * y + carry;
  295.   r->s[0] = a;
  296.   a &= 0xffff8000L;
  297.   if ( a != 0xffff8000L && a != 0L ) {
  298.     r->s[0] = 0x8000 ^ x->s[0] ^ y;
  299.     (*Fix_overflow_handler)(r);
  300.   }
  301.   return r;
  302. }
  303.  
  304. _Fix divide(_Fix x, _Fix y, _Fix q = NULL, _Fix r = NULL)
  305. {
  306.   int xsign = x->s[0] & 0x8000, 
  307.     ysign = y->s[0] & 0x8000;
  308.   if ( q == NULL )
  309.     q = new_Fix(x->len);
  310.   copy(&_Frep_0,q);
  311.   if ( r == NULL )
  312.     r = new_Fix(x->len + y->len - 1);
  313.   if ( xsign )
  314.     negate(x,r);
  315.   else
  316.     copy(x,r);
  317.   Fix Y(y->len);
  318.   y = ( ysign ? negate(y,Y.rep) : copy(y,Y.rep) );
  319.   if ( !compare(y) )
  320.     (*Fix_range_error_handler)("division -- division by zero");
  321.   else if ( compare(x,y) >= 0 )
  322.     if ( compare(x,y) == 0 && xsign ^ ysign != 0 )
  323.     {
  324.       copy(&_Frep_m1,q);
  325.       copy(&_Frep_0,r);
  326.     }
  327.     else
  328.       (*Fix_range_error_handler)("division");
  329.   else
  330.   {
  331.     _Fix t;
  332.     Fix S(r->len),
  333.       W(q->len,&_Frep_quotient_bump);
  334.     for ( int i=1; i < q->len; i++ )
  335.     {
  336.       shift(y,-1,y);
  337.       subtract(r,y,S.rep);
  338.       int s_status = compare(S.rep);
  339.       if ( s_status == 0 ) 
  340.       {
  341.     t = r, r = S.rep, S.rep = t;
  342.     break;
  343.       }
  344.       else if ( s_status > 0 )
  345.       {
  346.     t = r, r = S.rep, S.rep = t;
  347.     add(q,W.rep,q);
  348.       }
  349.       shift(W.rep,-1,W.rep);
  350.     }
  351.     if ( xsign ^ ysign )
  352.       negate(q,q);
  353.   }
  354.   return q;
  355. }
  356.  
  357. _Fix shift(_Fix x, int y, _Fix r = NULL )
  358. {
  359.   if ( y == 0 )
  360.     return x;
  361.   else if ( r == NULL )
  362.     r = new_Fix(x->len);
  363.  
  364.   int ay = abs(y),
  365.     ayh = ay >> 4,
  366.     ayl = ay & 0x0f;
  367.   int xl, u, ilow, ihigh;
  368.   uint16 *rs, *xsl, *xsr;
  369.  
  370.   if ( y > 0 )
  371.   {
  372.     rs = r->s;
  373.     xsl = x->s + ayh;
  374.     xsr = xsl + 1;
  375.     xl = ayl;
  376.     u = 1;
  377.     ihigh = x->siz - ayh - 1;
  378.     ilow = 0;
  379.   }
  380.   else
  381.   {
  382.     rs = &r->s[r->siz - 1];
  383.     xsr = &x->s[r->siz - 1] - ayh;
  384.     xsl = xsr - 1;
  385.     xl = 16 - ayl;
  386.     u = -1;
  387.     ihigh = r->siz - ayh - 1;
  388.     ilow = ihigh - x->siz;
  389.   }
  390.  
  391.   int xr = 16 - xl;
  392.   uint16 xrmask = 0xffffL >> xr;
  393.   for ( int i=0; i < ilow; i++, rs+=u, xsl+=u, xsr+=u )
  394.     *rs = 0;
  395.   for ( ; i < ihigh; i++, rs+=u, xsl+=u, xsr+=u )
  396.     *rs = (*xsl << xl) + ((*xsr >> xr) & xrmask);
  397.   *rs = (y > 0 ? (*xsl << xl) : ((*xsr >> xr) & xrmask));
  398.   rs += u;
  399.   for ( ; i < r->siz; i++, rs+=u )
  400.     *rs = 0;
  401.   return r;
  402. }
  403.  
  404. _Fix negate(_Fix x, _Fix r = NULL)
  405. {
  406.   if ( r == NULL )
  407.     r = new_Fix(x->len);
  408.   uint32 carry = 1;
  409.   for ( int i=r->siz-1; i >= x->siz; i-- )
  410.     r->s[i] = 0;
  411.   for ( ; i >= 0; i-- )
  412.   {
  413.     uint32 a = (uint16 )~x->s[i] + carry;    // bug work-around
  414.     r->s[i] = a;
  415.     carry = a >> 16;
  416.   }
  417.   return r;
  418. }
  419.  
  420. // io functions
  421.  
  422. Fix atoF(const char* a, int len = Fix_default_length)
  423. {
  424.   return Fix(len,atof(a));
  425. }
  426.  
  427. char* Ftoa(Fix& x, int width = Fix_default_print_width)
  428. {
  429.   char *s = new char[width+1];
  430.   sprintf(s,"% *.*lf",width-2,width-3,value(x));
  431.   return s;
  432. }
  433.  
  434. extern Obstack _libgxx_io_ob;
  435. extern char* _libgxx_io_oblast;
  436.  
  437. Fix Fix::operator %= (int y)
  438. {
  439.   Fix r((int )rep->len + y, *this); return *this = r;
  440. }
  441.  
  442. istream& operator >> (istream& s, Fix& y)
  443. {
  444.   int got_one = 0;
  445.   if (!s.readable())
  446.   {
  447.     s.error();
  448.     return s;
  449.   }
  450.  
  451.   if (_libgxx_io_oblast) _libgxx_io_ob.free(_libgxx_io_oblast);
  452.  
  453.   char sign = 0, point = 0;
  454.   char ch;
  455.   s >> WS;
  456.   while (s.good())
  457.   {
  458.     s.get(ch);
  459.     if (ch == '-')
  460.     {
  461.       if (sign == 0)
  462.       {
  463.         sign = 1;
  464.         _libgxx_io_ob.grow(ch);
  465.       }
  466.       else
  467.         break;
  468.     }
  469.     if (ch == '.')
  470.     {
  471.       if (point == 0)
  472.       {
  473.         point = 1;
  474.         _libgxx_io_ob.grow(ch);
  475.       }
  476.       else
  477.         break;
  478.     }
  479.     else if (ch >= '0' && ch <= '9')
  480.     {
  481.       got_one = 1;
  482.       _libgxx_io_ob.grow(ch);
  483.     }
  484.     else
  485.       break;
  486.   }
  487.   char * p = (char*)(_libgxx_io_ob.finish(0));
  488.   _libgxx_io_oblast = p;
  489.   if (s.good())
  490.     s.unget(ch);
  491.   if (!got_one)
  492.     s.error();
  493.   else
  494.     y = atoF(p);
  495.   return s;
  496. }
  497.  
  498. void show(Fix& x)
  499. {
  500.   cout << "len = " << x.rep->len << "\n";
  501.   cout << "siz = " << x.rep->siz << "\n";
  502.   cout << "ref = " << x.rep->ref << "\n";
  503.   cout << "man = " << Itoa(mantissa(x),16,4*x.rep->siz) << "\n";
  504.   cout << "val = " << value(x) << "\n";
  505. }
  506.  
  507. // parameter setting operations
  508.  
  509. Fix_peh set_overflow_handler(Fix_peh new_handler) {
  510.   Fix_peh old_handler = Fix_overflow_handler;
  511.   Fix_overflow_handler = new_handler;
  512.   return old_handler;
  513. }
  514.  
  515. int Fix_set_default_length(int newlen)
  516. {
  517.   uint16 oldlen = Fix_default_length;
  518.   if ( newlen < _Fix_min_length || newlen > _Fix_max_length )
  519.     (*Fix_error_handler)("illegal length in Fix_set_default_length");
  520.   Fix_default_length = newlen;
  521.   return oldlen;
  522. }
  523.  
  524. // overflow handlers
  525.  
  526. void Fix_overflow_saturate(_Fix& r) {
  527.   if ( (int16 )r->s[0] > 0 ) 
  528.   {
  529.     r->s[0] = 0x8000;
  530.     for ( int i=1; i < r->siz; i++ )
  531.       r->s[i] = 0;
  532.   }
  533.   else
  534.   {
  535.     r->s[0] = 0x7fff;
  536.     for ( int i=1; i < r->siz; i++ )
  537.       r->s[i] = 0xffff;
  538.     mask(r);
  539.   }
  540. }
  541.  
  542. void Fix_overflow_wrap(_Fix& r) {}
  543.  
  544. void Fix_overflow_warning_saturate(_Fix& r) {
  545.   Fix_overflow_warning(r);
  546.   Fix_overflow_saturate(r);
  547. }
  548.  
  549. void Fix_overflow_warning(_Fix& r) {
  550.   cerr << "Fix: overflow warning\n"; 
  551. }
  552.  
  553. void Fix_overflow_error(_Fix& r) {
  554.   cerr << "Fix: overflow error\n"; 
  555.   abort();
  556. }
  557.  
  558.