home *** CD-ROM | disk | FTP | other *** search
/ GEMini Atari / GEMini_Atari_CD-ROM_Walnut_Creek_December_1993.iso / files / gnu / g__lib / bitstrin.cc < prev    next >
Encoding:
C/C++ Source or Header  |  1993-07-23  |  40.7 KB  |  1,834 lines
  1. /* 
  2. Copyright (C) 1988 Free Software Foundation
  3.     written by Doug Lea (dl@rocky.oswego.edu)
  4.  
  5. This file is part of GNU CC.
  6.  
  7. GNU CC is distributed in the hope that it will be useful,
  8. but WITHOUT ANY WARRANTY.  No author or distributor
  9. accepts responsibility to anyone for the consequences of using it
  10. or for whether it serves any particular purpose or works at all,
  11. unless he says so in writing.  Refer to the GNU CC General Public
  12. License for full details.
  13.  
  14. Everyone is granted permission to copy, modify and redistribute
  15. GNU CC, but only under the conditions described in the
  16. GNU CC General Public License.   A copy of this license is
  17. supposed to have been given to you along with GNU CC so you
  18. can know your rights and responsibilities.  It should be in a
  19. file named COPYING.  Among other things, the copyright notice
  20. and this notice must be preserved on all copies.  
  21. */
  22.  
  23. /* 
  24.   BitString class implementation
  25.  */
  26.  
  27. #include <BitString.h>
  28. #include <std.h>
  29. #include "libconfig.h"
  30. #include <Obstack.h>
  31.  
  32.  
  33. void BitString::error(char* msg)
  34. {
  35.   (*lib_error_handler)("BitString", msg);
  36. }
  37.  
  38. //  globals
  39.  
  40. BitStrRep    _nilBitStrRep = {  0, 1, {0} };
  41.  
  42. static BitString _nil_BitString;
  43.  
  44.  
  45. #define MINBitStrRep_SIZE  8
  46. #define MAXBitStrRep_SIZE  (1 << (SHORTBITS - 1) - 1)
  47. #define MALLOC_OVERHEAD    4
  48.  
  49. #define ONES  ((unsigned short)(~0L))
  50. #define MAXBIT  (1 << (BITSTRBITS - 1))
  51.  
  52. /*
  53.  *  bit manipulation utilities
  54. */
  55.  
  56. // break things up into .s indices and positions
  57.  
  58. inline static int BitStr_len(int l)
  59. {
  60.   return (unsigned)(l) / BITSTRBITS + 1;
  61. }
  62.  
  63.  
  64. // mask out low bits
  65.  
  66. static inline unsigned short lmask(int p)
  67. {
  68.   if (p <= 0)
  69.     return ONES;
  70.   else
  71.     return ONES << p;
  72. }
  73.  
  74. // mask out high bits
  75.  
  76. static inline unsigned short rmask(int p)
  77. {
  78.   int s = BITSTRBITS - 1 - p;
  79.   if (s <= 0)
  80.     return ONES;
  81.   else
  82.     return ONES >> s;
  83. }
  84.  
  85.  
  86. // mask out unused bits in last word of rep
  87.  
  88. inline static void check_last(BitStrRep* r)
  89. {
  90.   r->s[r->len / BITSTRBITS] &= ONES >> (BITSTRBITS - (r->len & (BITSTRBITS - 1)));
  91. }
  92.  
  93. // merge bits from next word
  94.  
  95. static inline unsigned short borrow_hi(unsigned short a[], int ind, 
  96.                                       int maxind, int p)
  97. {
  98.   if (ind < maxind)
  99.     return (a[ind] >> p) | (a[ind+1] << (BITSTRBITS - p));
  100.   else
  101.     return (a[ind] >> p);
  102. }
  103.  
  104. // merge bits from prev word
  105.  
  106. static inline unsigned short borrow_lo(unsigned short a[], int ind, 
  107.                                       int minind, int p)
  108. {
  109.   if (ind > minind)
  110.     return (a[ind] << (BITSTRBITS - 1 - p)) | (a[ind-1] >> (p + 1));
  111.   else
  112.     return (a[ind] << (BITSTRBITS - 1 - p));
  113. }
  114.  
  115. // same with bounds check (for masks shorter than patterns)
  116.  
  117. static inline unsigned short safe_borrow_hi(unsigned short a[], int ind, 
  118.                                            int maxind, int p)
  119. {
  120.   if (ind > maxind)
  121.     return 0;
  122.   else if (ind == maxind)
  123.     return(a[ind] >> p);
  124.   else
  125.     return (a[ind] >> p) | (a[ind+1] << (BITSTRBITS - p));
  126. }
  127.  
  128.  
  129. static inline unsigned short safe_borrow_lo(unsigned short a[], int ind, 
  130.                                       int minind, int p)
  131. {
  132.   if (ind < minind)
  133.     return 0;
  134.   else if (ind == minind)
  135.     return (a[ind] << (BITSTRBITS - 1 - p));
  136.   else
  137.     return (a[ind] << (BITSTRBITS - 1 - p)) | (a[ind-1] >> (p + 1));
  138. }
  139.  
  140. // copy bits from a word boundary
  141.  
  142. static inline void bit_copy(unsigned short* ss, unsigned short* ds, int nbits)
  143. {
  144.   if (ss != ds)
  145.   {
  146.     int n = (unsigned)(nbits) / BITSTRBITS;
  147.     if (n > 0) bcopy((void*)ss, (void*)ds, n * sizeof(short));
  148.     unsigned short m = ONES << (nbits & (BITSTRBITS - 1));
  149.     ds[n] = (ss[n] & ~m) | (ds[n] & m);
  150.   }
  151. }
  152.  
  153. // clear bits from a word boundary
  154.  
  155. static inline void bit_clear(unsigned short* ds, int nbits)
  156. {
  157.   int n = (unsigned)(nbits) / BITSTRBITS;
  158.   if (n > 0) bzero((void*)ds, n * sizeof(short));
  159.   ds[n] &= ONES << (nbits & (BITSTRBITS - 1));
  160. }
  161.  
  162.   
  163.  
  164. // copy ss from starts to fences-1 into ds starting at startd
  165. // this will work even if ss & ds are the same 
  166. // The g++ optimizer does very good things with the messy shift expressions!
  167.  
  168. static void bit_transfer(unsigned short* ss, int starts, int fences,
  169.                          unsigned short* ds, int startd)
  170. {
  171.   if (starts >= fences || ss == 0 || (ss == ds && starts == startd))
  172.     return;
  173.  
  174.   int sind = BitStr_index(starts);
  175.   int spos = BitStr_pos(starts);
  176.   int dind = BitStr_index(startd);
  177.   int dpos = BitStr_pos(startd);
  178.  
  179.   if (spos == 0 && dpos == 0)
  180.   {
  181.     bit_copy(&ss[sind], &ds[dind], fences - starts);
  182.     return;
  183.   }
  184.  
  185.   int ends = fences - 1;
  186.   int endsind = BitStr_index(ends);
  187.   int endspos = BitStr_pos(ends);
  188.   int endd = startd + (ends - starts);
  189.   int enddind = BitStr_index(endd);
  190.   int enddpos = BitStr_pos(endd);
  191.  
  192.   if (dind == enddind)
  193.   {
  194.     if (sind == endsind)
  195.       ds[dind] = (ds[dind] & ((ONES >> (BITSTRBITS - dpos)) | 
  196.                               (ONES << (enddpos + 1)))) | 
  197.         (((ss[sind] >> spos) << dpos) & 
  198.          ~((ONES >> (BITSTRBITS - dpos)) | (ONES << (enddpos + 1))));
  199.     else
  200.       ds[dind] = (ds[dind] & ((ONES >> (BITSTRBITS - dpos)) | 
  201.                               (ONES << (enddpos + 1)))) | 
  202.         ((((ss[sind] >> spos) | (ss[sind+1] << (BITSTRBITS - spos))) << dpos) & 
  203.          ~((ONES >> (BITSTRBITS - dpos)) | (ONES << (enddpos + 1))));
  204.     return;
  205.   }
  206.   else if (sind == endsind)
  207.   {
  208.     unsigned short saveend = (ds[enddind] & (ONES << (enddpos + 1))) | 
  209.         (((ss[sind] << (BITSTRBITS - 1 - endspos)) >> 
  210.           (BITSTRBITS - 1 - enddpos)) & ~(ONES << (enddpos + 1)));
  211.     ds[dind] = (ds[dind] & (ONES >> (BITSTRBITS - dpos))) |
  212.         (((ss[sind] >> spos) << dpos) & ~(ONES >> (BITSTRBITS - dpos)));
  213.     ds[enddind] = saveend;
  214.     return;
  215.   }
  216.  
  217.   unsigned short saveend = (ds[enddind] & (ONES << (enddpos + 1))) | 
  218.     ((((ss[endsind] << (BITSTRBITS - 1 - endspos)) |
  219.        (ss[endsind-1] >> (endspos + 1))) >> 
  220.       (BITSTRBITS - 1 - enddpos)) & ~(ONES << (enddpos + 1)));
  221.   unsigned short savestart = (ds[dind] & (ONES >> (BITSTRBITS - dpos))) |
  222.     ((((ss[sind] >> spos) | (ss[sind+1] << (BITSTRBITS - spos))) << dpos) 
  223.      & ~(ONES >> (BITSTRBITS - dpos)));
  224.  
  225.  
  226.   if (ds != ss || startd < starts)
  227.   {
  228.     int pos = spos - dpos;
  229.     if (pos < 0)
  230.       pos += BITSTRBITS;
  231.     else
  232.       ++sind;
  233.     
  234.     for (;;)                    // lag by one in case of overlaps
  235.     {
  236.       if (dind == enddind - 1)
  237.       {
  238.         ds[dind] = savestart;
  239.         ds[enddind] = saveend;
  240.         return;
  241.       }
  242.       else
  243.       {
  244.         unsigned short tmp = ss[sind] >> pos;
  245.         if (++sind <= endsind) tmp |= ss[sind] << (BITSTRBITS - pos);
  246.         ds[dind++] = savestart;
  247.         savestart = tmp;
  248.       }
  249.     }
  250.   }
  251.   else
  252.   {
  253.     int pos = endspos - enddpos;
  254.     if (pos <= 0)
  255.     {
  256.       pos += BITSTRBITS;
  257.       --endsind;
  258.     }
  259.     for (;;)
  260.     {
  261.       if (enddind == dind + 1)
  262.       {
  263.         ds[enddind] = saveend;
  264.         ds[dind] = savestart;
  265.         return;
  266.       }
  267.       else
  268.       {
  269.         unsigned short tmp = ss[endsind] << (BITSTRBITS - pos);
  270.         if (--endsind >= sind) tmp |= ss[endsind] >> pos;
  271.         ds[enddind--] = saveend;
  272.         saveend = tmp;
  273.       }
  274.     }
  275.   }
  276. }
  277.   
  278.  
  279. inline static BitStrRep* BSnew(int newlen)
  280. {
  281.   unsigned int siz = sizeof(BitStrRep) + BitStr_len(newlen) * sizeof(short) 
  282.     + MALLOC_OVERHEAD;
  283.   unsigned int allocsiz = MINBitStrRep_SIZE;;
  284.   while (allocsiz < siz) allocsiz <<= 1;
  285.   allocsiz -= MALLOC_OVERHEAD;
  286.   if (allocsiz >= MAXBitStrRep_SIZE * sizeof(short))
  287.     (*lib_error_handler)("BitString", "Requested length out of range");
  288.     
  289.   BitStrRep* rep = (BitStrRep *) new char[allocsiz];
  290.   bzero(rep, allocsiz);
  291.   rep->sz = (allocsiz - sizeof(BitStrRep) + sizeof(short)) / sizeof(short);
  292.   return rep;
  293. }
  294.  
  295. BitStrRep* BStr_alloc(BitStrRep* old, unsigned short* src,
  296.                               int startpos, int endp, int newlen)
  297. {
  298.   if (old == &_nilBitStrRep) old = 0; 
  299.   if (newlen < 0) newlen = 0;
  300.   int news = BitStr_len(newlen);
  301.   BitStrRep* rep;
  302.   if (old == 0 || news > old->sz)
  303.     rep = BSnew(newlen);
  304.   else
  305.     rep = old;
  306.   rep->len = newlen;
  307.  
  308.   if (src != 0 && endp > 0 && (src != rep->s || startpos > 0)) 
  309.     bit_transfer(src, startpos, endp, rep->s, 0);
  310.  
  311.   check_last(rep);
  312.  
  313.   if (old != rep && old != 0) delete old;
  314.  
  315.   return rep;
  316. }
  317.  
  318. BitStrRep* BStr_resize(BitStrRep* old, int newlen)
  319. {
  320.   BitStrRep* rep;
  321.   if (newlen < 0) newlen = 0;
  322.   int news = BitStr_len(newlen);
  323.   if (old == 0 || old == &_nilBitStrRep)
  324.   {
  325.     rep = BSnew(newlen);
  326.   }
  327.   else if (news > old->sz)
  328.   {
  329.     rep = BSnew(newlen);
  330.     bcopy(old->s, rep->s, BitStr_len(old->len) * sizeof(short));
  331.     delete old;
  332.   }
  333.   else
  334.     rep = old;
  335.  
  336.   rep->len = newlen;
  337.   check_last(rep);
  338.   return rep;
  339. }
  340.  
  341. BitStrRep* BStr_copy(BitStrRep* old, BitStrRep* src)
  342. {
  343.   BitStrRep* rep;
  344.   if (old == src) return old; 
  345.   if (old == &_nilBitStrRep) old = 0;
  346.   if (src == &_nilBitStrRep) src = 0;
  347.   if (src == 0)
  348.   {
  349.     if (old == 0)
  350.       rep = BSnew(0);
  351.     rep->len = 0;
  352.   }
  353.   else 
  354.   {
  355.     int newlen = src->len;
  356.     int news = BitStr_len(newlen);
  357.     if (old == 0 || news  > old->sz)
  358.     {
  359.       rep = BSnew(newlen);
  360.       if (old != 0) delete old;
  361.     }
  362.     else
  363.       rep = old;
  364.     
  365.     bcopy(src->s, rep->s, news * sizeof(short));
  366.     rep->len = newlen;
  367.   }
  368.   check_last(rep);
  369.   return rep;
  370. }
  371.  
  372.  
  373. int operator == (BitString& x, BitString& y)
  374. {
  375.   return x.rep->len == y.rep->len && 
  376.     bcmp((void*)x.rep->s, (void*)y.rep->s, 
  377.          BitStr_len(x.rep->len) * sizeof(short)) == 0;
  378. }
  379.  
  380. int operator <= (BitString& x, BitString& y)
  381. {
  382.   unsigned int  xl = x.rep->len;
  383.   unsigned int  yl = y.rep->len;
  384.   if (xl > yl)
  385.     return 0;
  386.  
  387.   unsigned short* xs = x.rep->s;
  388.   unsigned short* ys = y.rep->s;
  389.   unsigned short* topx = &(xs[BitStr_len(xl)]);
  390.  
  391.   while (xs < topx)
  392.   {
  393.     unsigned short a = *xs++;
  394.     unsigned short b = *ys++;
  395.     if ((a | b) != b)
  396.       return 0;
  397.   }
  398.   return 1;
  399. }
  400.  
  401. int operator < (BitString& x, BitString& y)
  402. {
  403.   unsigned short xl = x.rep->len;
  404.   unsigned short yl = y.rep->len;
  405.   if (xl > yl)
  406.     return 0;
  407.  
  408.   unsigned short* xs = x.rep->s;
  409.   unsigned short* ys = y.rep->s;
  410.   unsigned short* topx = &(xs[BitStr_len(xl)]);
  411.   unsigned short* topy = &(ys[BitStr_len(yl)]);
  412.   int one_diff = 0;
  413.   while (xs < topx)
  414.   {
  415.     unsigned short a = *xs++;
  416.     unsigned short b = *ys++;
  417.     unsigned short c = a | b;
  418.     if (c != b)
  419.       return 0;
  420.     else if (c != a)
  421.       one_diff = 1;
  422.   }
  423.   if (one_diff)
  424.     return 1;
  425.   else
  426.   {
  427.     while (ys < topy)
  428.       if (*ys++ != 0)
  429.         return 1;
  430.     return 0;
  431.   }
  432. }
  433.  
  434. int lcompare(BitString& x, BitString& y)
  435. {
  436.   unsigned int  xl = x.rep->len;
  437.   unsigned int  yl = y.rep->len;
  438.  
  439.   unsigned short* xs = x.rep->s;
  440.   unsigned short* topx = &(xs[BitStr_len(xl)]);
  441.   unsigned short* ys = y.rep->s;
  442.   unsigned short* topy = &(ys[BitStr_len(yl)]);
  443.  
  444.   while (xs < topx && ys < topy)
  445.   {
  446.     unsigned short a = *xs++;
  447.     unsigned short b = *ys++;
  448.     if (a != b)
  449.     {
  450.       unsigned short mask = 1;
  451.       for (;;)
  452.       {
  453.         unsigned short abit = (a & mask) != 0;
  454.         unsigned short bbit = (b & mask) != 0;
  455.         int diff = abit - bbit;
  456.         if (diff != 0)
  457.           return diff;
  458.         else
  459.           mask <<= 1;
  460.       }
  461.     }
  462.   }
  463.   return xl - yl;
  464. }
  465.  
  466. int BitString::count(int b = 1)
  467. {
  468.   check_last(rep);
  469.   int xwds = BitStr_len(rep->len);
  470.   int xlast = BitStr_pos(rep->len);
  471.   int l = 0;
  472.   unsigned short* s = rep->s;
  473.   unsigned short* tops = &(s[xwds - 1]);
  474.   unsigned short a;
  475.   int i;
  476.   if (b != 0)
  477.   {
  478.     while (s < tops)
  479.     {
  480.       a = *s++;
  481.       for (i = 0; i < BITSTRBITS && a != 0; ++i)
  482.       {
  483.         if (a & 1)
  484.           ++l;
  485.         a >>= 1;
  486.       }
  487.     }
  488.     a = *s;
  489.     for (i = 0; i < xlast && a != 0; ++i)
  490.     {
  491.       if (a & 1)
  492.         ++l;
  493.       a >>= 1;
  494.     }
  495.   }
  496.   else
  497.   {
  498.     unsigned short maxbit = 1 << (BITSTRBITS - 1);
  499.     while (s < tops)
  500.     {
  501.       a = *s++;
  502.       for (i = 0; i < BITSTRBITS; ++i)
  503.       {
  504.         if ((a & maxbit) == 0)
  505.           ++l;
  506.         a <<= 1;
  507.       }
  508.     }
  509.     maxbit = 1 << (xlast - 1);
  510.     a = *s;
  511.     for (i = 0; i < xlast; ++i)
  512.     {
  513.       if ((a & maxbit) == 0)
  514.         ++l;
  515.       a <<= 1;
  516.     }
  517.   }
  518.   return l;
  519. }
  520.  
  521.  
  522. BitStrRep* cmpl(BitStrRep* src, BitStrRep* r)
  523. {
  524.   r = BStr_copy(r, src);
  525.   unsigned short* rs = r->s;
  526.   unsigned short* topr = &(rs[BitStr_len(r->len)]);
  527.   while (rs < topr)
  528.   {
  529.     unsigned short cmp = ~(*rs);
  530.     *rs++ = cmp;
  531.   }
  532.   check_last(r);
  533.   return r;
  534. }
  535.  
  536.  
  537.  
  538. BitStrRep* and(BitStrRep* x, BitStrRep* y, BitStrRep* r)
  539. {
  540.   int xrsame = x == r;
  541.   int yrsame = y == r;
  542.  
  543.   unsigned int  rl = x->len <? y->len;
  544.   r = BStr_resize(r, rl);
  545.  
  546.   unsigned short* rs = r->s;
  547.   unsigned short* topr = &(rs[BitStr_len(rl)]);
  548.   unsigned short* xs = (xrsame)? rs : x->s;
  549.   unsigned short* ys = (yrsame)? rs : y->s;
  550.  
  551.   while (rs < topr) *rs++ = *xs++ & *ys++;
  552.   check_last(r);
  553.   return r;
  554. }
  555.  
  556. BitStrRep* or(BitStrRep* x, BitStrRep* y, BitStrRep* r)
  557. {
  558.   unsigned int  xl = x->len;
  559.   unsigned int  yl = y->len;
  560.   unsigned int  rl = xl >? yl;
  561.   int xrsame = x == r;
  562.   int yrsame = y == r;
  563.  
  564.   r = BStr_resize(r, rl);
  565.  
  566.   unsigned short* rs = r->s;
  567.   unsigned short* xs = (xrsame)? rs : x->s;
  568.   unsigned short* topx = &(xs[BitStr_len(xl)]);
  569.   unsigned short* ys = (yrsame)? rs : y->s;
  570.   unsigned short* topy = &(ys[BitStr_len(yl)]);
  571.  
  572.   if (xl <= yl)
  573.   {
  574.     while (xs < topx) *rs++ = *xs++ | *ys++;
  575.     if (rs != ys) while (ys < topy) *rs++ = *ys++;
  576.   }
  577.   else
  578.   {
  579.     while (ys < topy) *rs++ = *xs++ | *ys++;
  580.     if (rs != xs) while (xs < topx) *rs++ = *xs++;
  581.   }
  582.   check_last(r);
  583.   return r;
  584. }
  585.  
  586.  
  587. BitStrRep* xor(BitStrRep* x, BitStrRep* y, BitStrRep* r)
  588. {
  589.   unsigned int  xl = x->len;
  590.   unsigned int  yl = y->len;
  591.   unsigned int  rl = xl >? yl;
  592.   int xrsame = x == r;
  593.   int yrsame = y == r;
  594.  
  595.   r = BStr_resize(r, rl);
  596.  
  597.   unsigned short* rs = r->s;
  598.   unsigned short* xs = (xrsame)? rs : x->s;
  599.   unsigned short* topx = &(xs[BitStr_len(xl)]);
  600.   unsigned short* ys = (yrsame)? rs : y->s;
  601.   unsigned short* topy = &(ys[BitStr_len(yl)]);
  602.  
  603.   if (xl <= yl)
  604.   {
  605.     while (xs < topx) *rs++ = *xs++ ^ *ys++;
  606.     if (rs != ys) while (ys < topy) *rs++ = *ys++;
  607.   }
  608.   else
  609.   {
  610.     while (ys < topy) *rs++ = *xs++ ^ *ys++;
  611.     if (rs != xs) while (xs < topx) *rs++ = *xs++;
  612.   }
  613.   check_last(r);
  614.   return r;
  615. }
  616.  
  617.  
  618. BitStrRep* difference(BitStrRep* x, BitStrRep* y, BitStrRep* r)
  619. {
  620.   unsigned int  xl = x->len;
  621.   unsigned int  yl = y->len;
  622.   int xrsame = x == y;
  623.   int yrsame = y == r;
  624.  
  625.   r = BStr_resize(r, xl);
  626.  
  627.   unsigned short* rs = r->s;
  628.   unsigned short* xs = (xrsame)? rs : x->s;
  629.   unsigned short* topx = &(xs[BitStr_len(xl)]);
  630.   unsigned short* ys = (yrsame)? rs : y->s;
  631.   unsigned short* topy = &(ys[BitStr_len(yl)]);
  632.  
  633.   if (xl <= yl)
  634.   {
  635.     while (xs < topx) *rs++ = *xs++ & ~(*ys++);
  636.   }
  637.   else
  638.   {
  639.     while (ys < topy) *rs++ = *xs++ & ~(*ys++);
  640.     if (rs != xs) while (xs < topx) *rs++ = *xs++;
  641.   }
  642.   check_last(r);
  643.   return r;
  644. }
  645.  
  646.  
  647. BitStrRep* concat(BitStrRep* x, BitStrRep* y, BitStrRep* r)
  648. {
  649.   unsigned int  xl = x->len;
  650.   unsigned int  yl = y->len;
  651.   unsigned int  rl = xl + yl;
  652.   int xrsame = x == r;
  653.   int yrsame = y == r;
  654.  
  655.   if (yrsame)
  656.   {
  657.     if (xrsame)
  658.     {
  659.       r = BStr_resize(r, rl);
  660.       bit_transfer(r->s, 0, yl, r->s, xl);
  661.     }
  662.     else
  663.     {
  664.       BitStrRep* tmp = BStr_copy(0, y);
  665.       r = BStr_resize(r, rl);
  666.       bit_copy(x->s, r->s, xl);
  667.       bit_transfer(tmp->s, 0, yl, r->s, xl);
  668.       delete tmp;
  669.     }
  670.   }
  671.   else
  672.   {
  673.     r = BStr_resize(r, rl);
  674.     if (!xrsame) bit_copy(x->s, r->s, xl);
  675.     bit_transfer(y->s, 0, yl, r->s, xl);
  676.   }
  677.   check_last(r);
  678.   return r;
  679. }
  680.  
  681. BitStrRep* concat(BitStrRep* x, int bit, BitStrRep* r)
  682. {
  683.   unsigned int  xl = x->len;
  684.   int xrsame = x == r;
  685.   r = BStr_resize(r, xl+1);
  686.   if (!xrsame) bit_copy(x->s, r->s, xl);
  687.   if (bit)
  688.     r->s[BitStr_index(xl)] |= (1 << (BitStr_pos(xl)));
  689.   else
  690.     r->s[BitStr_index(xl)] &= ~(1 << (BitStr_pos(xl)));
  691.   check_last(r);
  692.   return r;
  693. }
  694.  
  695. BitStrRep* rshift(BitStrRep* x, int s, BitStrRep* r)
  696. {
  697.   int xrsame = x == r;
  698.   int  xl = x->len;
  699.   int  rl = xl + s;
  700.   if (s == 0)
  701.     r = BStr_copy(r, x);
  702.   else if (rl <= 0)
  703.   {
  704.     r = BStr_resize(r, 0);
  705.     r->len = 0;
  706.     r->s[0] = 0;
  707.   }
  708.   else if (s > 0)
  709.   {
  710.     r = BStr_resize(r, rl);
  711.     unsigned short* xs = (xrsame)? r->s : x->s;
  712.     bit_transfer(xs, 0, xl, r->s, s);
  713.     bit_clear(r->s, s);
  714.   }
  715.   else if (xrsame)
  716.   {
  717.     r = BStr_resize(r, xl);
  718.     r->len = rl;
  719.     bit_transfer(r->s, -s, xl, r->s, 0);
  720.   }
  721.   else
  722.   {
  723.     r = BStr_resize(r, rl);
  724.     bit_transfer(x->s, -s, xl, r->s, 0);
  725.   }
  726.   check_last(r);
  727.   return r;
  728. }
  729.  
  730.  
  731. void BitString::set(int p)
  732. {
  733.   if (p < 0) error("Illegal bit index");
  734.   if (p >= rep->len) rep = BStr_resize(rep, p + 1);
  735.   rep->s[BitStr_index(p)] |= (1 << (BitStr_pos(p)));
  736. }
  737.  
  738. void BitString::assign(int p, int bit)
  739. {
  740.   if (p < 0) error("Illegal bit index");
  741.   if (p >= rep->len) rep = BStr_resize(rep, p + 1);
  742.   if (bit)
  743.     rep->s[BitStr_index(p)] |= (1 << (BitStr_pos(p)));
  744.   else
  745.     rep->s[BitStr_index(p)] &= ~(1 << (BitStr_pos(p)));
  746. }
  747.  
  748. void BitString::clear(int p)
  749. {
  750.   if (p < 0) error("Illegal bit index");
  751.   if (p >= rep->len) rep = BStr_resize(rep, p + 1);
  752.   rep->s[BitStr_index(p)] &= ~(1 << (BitStr_pos(p)));
  753. }
  754.  
  755. void BitString::clear()
  756. {
  757.   if (rep == &_nilBitStrRep) return;
  758.   bit_clear(rep->s, rep->len);
  759. }
  760.  
  761. void BitString::set()
  762. {
  763.   if (rep == &_nilBitStrRep) return;
  764.   unsigned short* s = rep->s;
  765.   unsigned short* tops = &(s[BitStr_len(rep->len)]);
  766.   while (s < tops) *s++ = ONES;
  767.   check_last(rep);
  768. }
  769.  
  770. void BitString::invert(int p)
  771. {
  772.   if (p < 0) error("Illegal bit index");
  773.   if (p >= rep->len) rep = BStr_resize(rep, p + 1);
  774.   rep->s[BitStr_index(p)] ^= (1 << (BitStr_pos(p)));
  775. }
  776.  
  777.  
  778.  
  779. void BitString::set(int from, int to)
  780. {
  781.   if (from < 0 || from > to) error("Illegal bit index");
  782.   if (to >= rep->len) rep = BStr_resize(rep, to+1);
  783.  
  784.   int ind1 = BitStr_index(from);
  785.   int pos1 = BitStr_pos(from);
  786.   int ind2 = BitStr_index(to);
  787.   int pos2 = BitStr_pos(to);
  788.   unsigned short* s = &(rep->s[ind1]);
  789.   unsigned short m1 = lmask(pos1);
  790.   unsigned short m2 = rmask(pos2);
  791.   if (ind2 == ind1)
  792.     *s |= m1 & m2;
  793.   else
  794.   {
  795.     *s++ |= m1;
  796.     unsigned short* top = &(rep->s[ind2]);
  797.     *top |= m2;
  798.     while (s < top)
  799.       *s++ = ONES;
  800.   }
  801. }
  802.  
  803. void BitString::clear(int from, int to)
  804. {
  805.   if (from < 0 || from > to) error("Illegal bit index");
  806.   if (to >= rep->len) rep = BStr_resize(rep, to+1);
  807.  
  808.   int ind1 = BitStr_index(from);
  809.   int pos1 = BitStr_pos(from);
  810.   int ind2 = BitStr_index(to);
  811.   int pos2 = BitStr_pos(to);
  812.   unsigned short* s = &(rep->s[ind1]);
  813.   unsigned short m1 = lmask(pos1);
  814.   unsigned short m2 = rmask(pos2);
  815.   if (ind2 == ind1)
  816.     *s &= ~(m1 & m2);
  817.   else
  818.   {
  819.     *s++ &= ~m1;
  820.     unsigned short* top = &(rep->s[ind2]);
  821.     *top &= ~m2;
  822.     while (s < top)
  823.       *s++ = 0;
  824.   }
  825. }
  826.  
  827. void BitString::invert(int from, int to)
  828. {
  829.   if (from < 0 || from > to) error("Illegal bit index");
  830.   if (to >= rep->len) rep = BStr_resize(rep, to+1);
  831.  
  832.   int ind1 = BitStr_index(from);
  833.   int pos1 = BitStr_pos(from);
  834.   int ind2 = BitStr_index(to);
  835.   int pos2 = BitStr_pos(to);
  836.   unsigned short* s = &(rep->s[ind1]);
  837.   unsigned short m1 = lmask(pos1);
  838.   unsigned short m2 = rmask(pos2);
  839.   if (ind2 == ind1)
  840.     *s ^= m1 & m2;
  841.   else
  842.   {
  843.     *s++ ^= m1;
  844.     unsigned short* top = &(rep->s[ind2]);
  845.     *top ^= m2;
  846.     while (s < top)
  847.     {
  848.       unsigned short cmp = ~(*s);
  849.       *s++ = cmp;
  850.     }
  851.   }
  852. }
  853.  
  854.  
  855. int BitString::test(int from, int to)
  856. {
  857.   if (from < 0 || from > to || from >= rep->len) return 0;
  858.  
  859.   int ind1 = BitStr_index(from);
  860.   int pos1 = BitStr_pos(from);
  861.   int ind2 = BitStr_index(to);
  862.   int pos2 = BitStr_pos(to);
  863.  
  864.   if (to >= rep->len)
  865.   {
  866.     ind2 = BitStr_index(rep->len - 1);
  867.     pos2 = BitStr_pos(rep->len - 1);
  868.   }
  869.  
  870.   unsigned short* s = &(rep->s[ind1]);
  871.   unsigned short m1 = lmask(pos1);
  872.   unsigned short m2 = rmask(pos2);
  873.  
  874.   if (ind2 == ind1)
  875.     return (*s & m1 & m2) != 0;
  876.   else
  877.   {
  878.     if (*s++ & m1)
  879.       return 1;
  880.     unsigned short* top = &(rep->s[ind2]);
  881.     if (*top & m2)
  882.       return 1;
  883.     while (s < top)
  884.       if (*s++ != 0) 
  885.         return 1;
  886.     return 0;
  887.   }
  888. }
  889.  
  890. int BitString::next(int p, int b = 1)
  891. {
  892.   if (++p >= rep->len)
  893.     return -1;
  894.  
  895.   int ind = BitStr_index(p);
  896.   int pos = BitStr_pos(p);
  897.   int l = BitStr_len(rep->len);
  898.  
  899.   int j = ind;
  900.   unsigned short* s = rep->s;
  901.   unsigned short a = s[j] >> pos;
  902.   int i = pos;
  903.  
  904.   if (b != 0)
  905.   {
  906.     for (; i < BITSTRBITS && a != 0; ++i)
  907.     {
  908.       if (a & 1)
  909.         return j * BITSTRBITS + i;
  910.       a >>= 1;
  911.     }
  912.     for (++j; j < l; ++j)
  913.     {
  914.       a = s[j];
  915.       for (i = 0; i < BITSTRBITS && a != 0; ++i)
  916.       {
  917.         if (a & 1)
  918.           return j * BITSTRBITS + i;
  919.         a >>= 1;
  920.       }
  921.     }
  922.     return -1;
  923.   }
  924.   else
  925.   {
  926.     int last = BitStr_pos(rep->len);
  927.     if (j == l - 1)
  928.     {
  929.       for (; i < last; ++i)
  930.       {
  931.         if ((a & 1) == 0)
  932.           return j * BITSTRBITS + i;
  933.         a >>= 1;
  934.       }
  935.       return -1;
  936.     }
  937.  
  938.     for (; i < BITSTRBITS; ++i)
  939.     {
  940.       if ((a & 1) == 0)
  941.         return j * BITSTRBITS + i;
  942.       a >>= 1;
  943.     }
  944.     for (++j; j < l - 1; ++j)
  945.     {
  946.       a = s[j];
  947.       if (a != ONES)
  948.       {
  949.         for (i = 0; i < BITSTRBITS; ++i)
  950.         {
  951.           if ((a & 1) == 0)
  952.             return j * BITSTRBITS + i;
  953.           a >>= 1;
  954.         }
  955.       }
  956.     }
  957.     a = s[j];
  958.     for (i = 0; i < last; ++i)
  959.     {
  960.       if ((a & 1) == 0)
  961.         return j * BITSTRBITS + i;
  962.       a >>= 1;
  963.     }
  964.     return -1;
  965.   }
  966. }
  967.  
  968. int BitString::previous(int p, int b = 1)
  969. {
  970.   if (--p < 0)
  971.     return -1;
  972.  
  973.   int ind = BitStr_index(p);
  974.   int pos = BitStr_pos(p);
  975.  
  976.   unsigned short* s = rep->s;
  977.   int l = BitStr_len(rep->len);
  978.  
  979.   if (p >= rep->len)
  980.   {
  981.     ind = BitStr_index(rep->len - 1);
  982.     pos = BitStr_pos(rep->len - 1);
  983.   }
  984.  
  985.   int j = ind;
  986.   unsigned short a = s[j];
  987.  
  988.   int i = pos;
  989.   unsigned short maxbit = 1 << pos;
  990.  
  991.   if (b != 0)
  992.   {
  993.     for (; i >= 0 && a != 0; --i)
  994.     {
  995.       if (a & maxbit)
  996.         return j * BITSTRBITS + i;
  997.       a <<= 1;
  998.     }
  999.     maxbit = 1 << (BITSTRBITS - 1);
  1000.     for (--j; j >= 0; --j)
  1001.     {
  1002.       a = s[j];
  1003.       for (i = BITSTRBITS - 1; i >= 0 && a != 0; --i)
  1004.       {
  1005.         if (a & maxbit)
  1006.           return j * BITSTRBITS + i;
  1007.         a <<= 1;
  1008.       }
  1009.     }
  1010.     return -1;
  1011.   }
  1012.   else
  1013.   {
  1014.     if (a != ONES)
  1015.     {
  1016.       for (; i >= 0; --i)
  1017.       {
  1018.         if ((a & maxbit) == 0)
  1019.           return j * BITSTRBITS + i;
  1020.         a <<= 1;
  1021.       }
  1022.     }
  1023.     maxbit = 1 << (BITSTRBITS - 1);
  1024.     for (--j; j >= 0; --j)
  1025.     {
  1026.       a = s[j];
  1027.       if (a != ONES)
  1028.       {
  1029.         for (i = BITSTRBITS - 1; i >= 0; --i)
  1030.         {
  1031.           if ((a & maxbit) == 0)
  1032.             return j * BITSTRBITS + i;
  1033.           a <<= 1;
  1034.         }
  1035.       }
  1036.     }
  1037.     return -1;
  1038.   }
  1039. }
  1040.  
  1041.  
  1042. int BitString::search(int startx, int lengthx, 
  1043.                       unsigned short* ys, int starty, int lengthy)
  1044. {
  1045.   unsigned short* xs = rep->s;
  1046.   int ylen = lengthy - starty;
  1047.   int righty = lengthy - 1;
  1048.   int rev = startx < 0;
  1049.   if (rev)
  1050.   {
  1051.     int leftx = 0;
  1052.     int rightx = lengthx + startx;
  1053.     startx = rightx - ylen + 1;
  1054.     if (ylen == 0) return startx;
  1055.     if (starty < 0 || righty < 0 || startx < 0 || startx >= lengthx) return -1;
  1056.     
  1057.     int xind = BitStr_index(startx);
  1058.     int xpos = BitStr_pos(startx);
  1059.     int yind = BitStr_index(starty);
  1060.     int ypos = BitStr_pos(starty);
  1061.     
  1062.     int rightxind = BitStr_index(rightx);
  1063.     int leftxind = BitStr_index(leftx);
  1064.     unsigned short x = borrow_hi(xs, xind, rightxind, xpos);
  1065.   
  1066.     int rightyind = BitStr_index(righty);
  1067.     int rightypos = BitStr_pos(righty);
  1068.     unsigned short y = borrow_hi(ys, yind, rightyind, ypos);
  1069.     unsigned short ymask;
  1070.     if (yind == rightyind)
  1071.       ymask = rmask(rightypos);
  1072.     else if (yind+1 == rightyind)
  1073.       ymask = rmask(BITSTRBITS - ypos + rightypos + 1);
  1074.     else
  1075.       ymask = ONES;
  1076.     
  1077.     int p = startx;
  1078.     for (;;)
  1079.     {
  1080.       if ((x & ymask) == y)
  1081.       {
  1082.         int xi = xind;
  1083.         int yi = yind;
  1084.         for (;;)
  1085.         {
  1086.           if (++yi > rightyind || ++xi > rightxind)
  1087.             return p;
  1088.           unsigned short tx = borrow_hi(xs, xi, rightxind, xpos);
  1089.           unsigned short ty = borrow_hi(ys, yi, rightyind, ypos);
  1090.           if (yi == rightyind)
  1091.             tx &= rmask(rightypos);
  1092.           else if (yi+1 == rightyind)
  1093.             tx &= rmask(BITSTRBITS - ypos + rightypos + 1);
  1094.           if (tx != ty)
  1095.             break;
  1096.         }
  1097.       }
  1098.       if (--p < leftx)
  1099.         return -1;
  1100.       if (--xpos < 0)
  1101.       {
  1102.         xpos = BITSTRBITS - 1;
  1103.         --xind;
  1104.       }
  1105.       x = borrow_hi(xs, xind, rightxind, xpos);
  1106.     }
  1107.   }
  1108.   else
  1109.   {
  1110.     int leftx = startx;
  1111.     int rightx = lengthx - 1;
  1112.     if (ylen == 0) return startx;
  1113.     if (starty < 0 || righty < 0 || startx < 0 || startx >= lengthx) return -1;
  1114.     
  1115.     int xind = BitStr_index(startx);
  1116.     int xpos = BitStr_pos(startx);
  1117.     int yind = BitStr_index(starty);
  1118.     int ypos = BitStr_pos(starty);
  1119.  
  1120.     int rightxind = BitStr_index(rightx);
  1121.     int leftxind = BitStr_index(leftx);
  1122.     unsigned short x = borrow_hi(xs, xind, rightxind, xpos);
  1123.     unsigned short nextx = (xind >= rightxind) ? 0 : (xs[xind+1] >> xpos);
  1124.   
  1125.     int rightyind = BitStr_index(righty);
  1126.     int rightypos = BitStr_pos(righty);
  1127.     unsigned short y = borrow_hi(ys, yind, rightyind, ypos);
  1128.     unsigned short ymask;
  1129.     if (yind == rightyind)
  1130.       ymask = rmask(rightypos);
  1131.     else if (yind+1 == rightyind)
  1132.       ymask = rmask(BITSTRBITS - ypos + rightypos + 1);
  1133.     else
  1134.       ymask = ONES;
  1135.   
  1136.     int p = startx;
  1137.     for (;;)
  1138.     {
  1139.       if ((x & ymask) == y)
  1140.       {
  1141.         int xi = xind;
  1142.         int yi = yind;
  1143.         for (;;)
  1144.         {
  1145.           if (++yi > rightyind || ++xi > rightxind)
  1146.             return p;
  1147.           unsigned short tx = borrow_hi(xs, xi, rightxind, xpos);
  1148.           unsigned short ty = borrow_hi(ys, yi, rightyind, ypos);
  1149.           if (yi == rightyind)
  1150.             tx &= rmask(rightypos);
  1151.           else if (yi+1 == rightyind)
  1152.             tx &= rmask(BITSTRBITS - ypos + rightypos + 1);
  1153.           if (tx != ty)
  1154.             break;
  1155.         }
  1156.       }
  1157.       if (++p > rightx)
  1158.         return -1;
  1159.       if (++xpos == BITSTRBITS)
  1160.       {
  1161.         xpos = 0;
  1162.         x = xs[++xind];
  1163.         nextx = (xind >= rightxind) ? 0 : xs[xind+1];
  1164.       }
  1165.       else
  1166.       {
  1167.         x >>= 1;
  1168.         if (nextx & 1)
  1169.           x |= MAXBIT;
  1170.         nextx >>= 1;
  1171.       }
  1172.     }
  1173.   }
  1174. }
  1175.  
  1176.  
  1177. int BitPattern::search(unsigned short* xs, int startx, int lengthx)
  1178. {
  1179.   unsigned short* ys = pattern.rep->s;
  1180.   unsigned short* ms = mask.rep->s;
  1181.   int righty = pattern.rep->len - 1;
  1182.   int rightm = mask.rep->len - 1;
  1183.  
  1184.   int rev = startx < 0;
  1185.   if (rev)
  1186.   {
  1187.     int leftx = 0;
  1188.     int rightx = lengthx + startx;
  1189.     startx = rightx - righty;
  1190.  
  1191.     if (righty < 0) return startx;
  1192.     if (startx < 0 || startx >= lengthx) return -1;
  1193.   
  1194.     int xind = BitStr_index(startx);
  1195.     int xpos = BitStr_pos(startx);
  1196.     
  1197.     int rightxind = BitStr_index(rightx);
  1198.     int leftxind = BitStr_index(leftx);
  1199.     int rightmind = BitStr_index(rightm);
  1200.     int rightyind = BitStr_index(righty);
  1201.     
  1202.     unsigned short x = safe_borrow_hi(xs, xind, rightxind, xpos);
  1203.     unsigned short m = safe_borrow_hi(ms, 0, rightmind, 0);
  1204.     unsigned short y = safe_borrow_hi(ys, 0, rightyind, 0) & m;
  1205.     
  1206.     int p = startx;
  1207.     for (;;)
  1208.     {
  1209.       if ((x & m) == y)
  1210.       {
  1211.         int xi = xind;
  1212.         int yi = 0;
  1213.         for (;;)
  1214.         {
  1215.           if (++yi > rightyind || ++xi > rightxind)
  1216.             return p;
  1217.           unsigned short tm = safe_borrow_hi(ms, yi, rightmind, 0);
  1218.           unsigned short ty = safe_borrow_hi(ys, yi, rightyind, 0);
  1219.           unsigned short tx = safe_borrow_hi(xs, xi, rightxind, xpos);
  1220.           if ((tx & tm) != (ty & tm))
  1221.             break;
  1222.         }
  1223.       }
  1224.       if (--p < leftx)
  1225.         return -1;
  1226.       if (--xpos < 0)
  1227.       {
  1228.         xpos = BITSTRBITS - 1;
  1229.         --xind;
  1230.       }
  1231.       x = safe_borrow_hi(xs, xind, rightxind, xpos);
  1232.     }
  1233.   }
  1234.   else
  1235.   {
  1236.     int leftx = startx;
  1237.     int rightx = lengthx - 1;
  1238.  
  1239.     if (righty < 0) return startx;
  1240.     if (startx < 0 || startx >= lengthx) return -1;
  1241.     
  1242.     int xind = BitStr_index(startx);
  1243.     int xpos = BitStr_pos(startx);
  1244.     
  1245.     int rightxind = BitStr_index(rightx);
  1246.     int leftxind = BitStr_index(leftx);
  1247.     int rightmind = BitStr_index(rightm);
  1248.     int rightyind = BitStr_index(righty);
  1249.     
  1250.     unsigned short x = safe_borrow_hi(xs, xind, rightxind, xpos);
  1251.     unsigned short m = safe_borrow_hi(ms, 0, rightmind, 0);
  1252.     unsigned short y = safe_borrow_hi(ys, 0, rightyind, 0) & m;
  1253.  
  1254.     unsigned short nextx = (xind >= rightxind) ? 0 : (xs[xind+1] >> xpos);
  1255.     
  1256.     int p = startx;
  1257.     for (;;)
  1258.     {
  1259.       if ((x & m) == y)
  1260.       {
  1261.         int xi = xind;
  1262.         int yi = 0;
  1263.         for (;;)
  1264.         {
  1265.           if (++yi > rightyind || ++xi > rightxind)
  1266.             return p;
  1267.           unsigned short tm = safe_borrow_hi(ms, yi, rightmind, 0);
  1268.           unsigned short ty = safe_borrow_hi(ys, yi, rightyind, 0);
  1269.           unsigned short tx = safe_borrow_hi(xs, xi, rightxind, xpos);
  1270.           if ((tx & tm) != (ty & tm))
  1271.             break;
  1272.         }
  1273.       }
  1274.       if (++p > rightx)
  1275.         return -1;
  1276.       if (++xpos == BITSTRBITS)
  1277.       {
  1278.         xpos = 0;
  1279.         x = xs[++xind];
  1280.         nextx = (xind >= rightxind) ? 0 : xs[xind+1];
  1281.       }
  1282.       else
  1283.       {
  1284.         x >>= 1;
  1285.         if (nextx & 1)
  1286.           x |= MAXBIT;
  1287.         nextx >>= 1;
  1288.       }
  1289.     }
  1290.   }
  1291. }
  1292.  
  1293. int BitString::match(int startx, int lengthx, int exact, 
  1294.                      unsigned short* ys, int starty, int yl)
  1295. {
  1296.   unsigned short* xs = rep->s;
  1297.   int ylen = yl - starty;
  1298.   int righty = yl - 1;
  1299.  
  1300.   int rightx;
  1301.   int rev = startx < 0;
  1302.   if (rev)
  1303.   {
  1304.     rightx = lengthx + startx;
  1305.     startx = rightx - ylen + 1;
  1306.     if (exact && startx != 0)
  1307.       return 0;
  1308.   }
  1309.   else
  1310.   {
  1311.     rightx = lengthx - 1;
  1312.     if (exact && rightx - startx != righty)
  1313.       return 0;
  1314.   }
  1315.  
  1316.   if (ylen == 0) return 1;
  1317.   if (righty < 0 || startx < 0 || startx >= lengthx) return 0;
  1318.   
  1319.   int xi   = BitStr_index(startx);
  1320.   int xpos = BitStr_pos(startx);
  1321.   int yi   = BitStr_index(starty);
  1322.   int ypos = BitStr_pos(starty);
  1323.  
  1324.   int rightxind = BitStr_index(rightx);
  1325.   int rightyind = BitStr_index(righty);
  1326.   int rightypos = BitStr_pos(righty);
  1327.  
  1328.   for (;;)
  1329.   {
  1330.     unsigned short x = borrow_hi(xs, xi, rightxind, xpos);
  1331.     unsigned short y = borrow_hi(ys, yi, rightyind, ypos);
  1332.     if (yi == rightyind)
  1333.       x &= rmask(rightypos);
  1334.     else if (yi+1 == rightyind)
  1335.       x &= rmask(BITSTRBITS - ypos + rightypos + 1);
  1336.     if (x != y)
  1337.       return 0;
  1338.     else if (++yi > rightyind || ++xi > rightxind)
  1339.       return 1;
  1340.   }
  1341. }
  1342.  
  1343. int BitPattern::match(unsigned short* xs, int startx, int lengthx, int exact)
  1344. {
  1345.   unsigned short* ys = pattern.rep->s;
  1346.   int righty = pattern.rep->len - 1;
  1347.   unsigned short* ms = mask.rep->s;
  1348.   int rightm = mask.rep->len - 1;
  1349.  
  1350.   int rightx;
  1351.   int rev = startx < 0;
  1352.   if (rev)
  1353.   {
  1354.     rightx = lengthx + startx;
  1355.     startx = rightx - righty;
  1356.     if (exact && startx != 0)
  1357.       return 0;
  1358.   }
  1359.   else
  1360.   {
  1361.     rightx = lengthx - 1;
  1362.     if (exact && rightx - startx != righty)
  1363.       return 0;
  1364.   }
  1365.  
  1366.   if (righty < 0) return 1;
  1367.   if (startx < 0 || startx >= lengthx) return 0;
  1368.   
  1369.   int xind = BitStr_index(startx);
  1370.   int xpos = BitStr_pos(startx);
  1371.   int yind = 0;
  1372.  
  1373.   int rightxind = BitStr_index(rightx);
  1374.   int rightyind = BitStr_index(righty);
  1375.   int rightmind = BitStr_index(rightm);
  1376.  
  1377.   for(;;)
  1378.   {
  1379.     unsigned short m = safe_borrow_hi(ms, yind, rightmind, 0);
  1380.     unsigned short x = safe_borrow_hi(xs, xind, rightxind, xpos) & m;
  1381.     unsigned short y = safe_borrow_hi(ys, yind, rightyind, 0) & m;
  1382.     if (x != y)
  1383.       return 0;
  1384.     else if (++yind > rightyind || ++xind > rightxind)
  1385.       return 1;
  1386.   }
  1387. }
  1388.  
  1389. BitSubString::BitSubString(BitString* x, int first, int l)
  1390. {
  1391.   if (first < 0 || l <= 0 || first + l > x->rep->len)
  1392.   {
  1393.     S = &_nil_BitString; pos = len = 0;
  1394.   }
  1395.   else
  1396.   {
  1397.     S = x; pos = first; len = l;
  1398.   }
  1399. }
  1400.  
  1401.  
  1402.  
  1403. void BitSubString::operator = (BitString& y)
  1404. {
  1405.   if (S == &_nil_BitString) return;
  1406.   BitStrRep* targ = S->rep;
  1407.  
  1408.   int ylen = y.rep->len;
  1409.   int sl = targ->len - len + ylen;
  1410.  
  1411.   if (y.rep == targ || ylen > len)
  1412.   {
  1413.     BitStrRep* oldtarg = targ;
  1414.     targ = BStr_alloc(0, 0, 0, 0, sl);
  1415.     bit_transfer(oldtarg->s, 0, pos, targ->s, 0);
  1416.     bit_transfer(y.rep->s, 0, ylen, targ->s, pos);
  1417.     bit_transfer(oldtarg->s, pos+len, oldtarg->len, targ->s, pos + ylen);
  1418.     delete oldtarg;
  1419.   }
  1420.   else if (len == ylen)
  1421.     bit_transfer(y.rep->s, 0, len, targ->s, pos);
  1422.   else if (ylen < len)
  1423.   {
  1424.     bit_transfer(y.rep->s, 0, ylen, targ->s, pos);
  1425.     bit_transfer(targ->s, pos+len, targ->len, targ->s, pos + ylen);
  1426.     targ->len = sl;
  1427.   }
  1428.   check_last(targ);
  1429.   S->rep = targ;
  1430. }
  1431.  
  1432. void BitSubString::operator = (BitSubString& y)
  1433. {
  1434.   if (S == &_nil_BitString) return;
  1435.   BitStrRep* targ = S->rep;
  1436.  
  1437.   if (len == 0 || pos >= targ->len)
  1438.     return;
  1439.  
  1440.   int sl = targ->len - len + y.len;
  1441.  
  1442.   if (y.S->rep == targ || y.len > len)
  1443.   {
  1444.     BitStrRep* oldtarg = targ;
  1445.     targ = BStr_alloc(0, 0, 0, 0, sl);
  1446.     bit_copy(oldtarg->s, targ->s, pos);
  1447.     bit_transfer(y.S->rep->s, y.pos, y.pos+y.len, targ->s, pos);
  1448.     bit_transfer(oldtarg->s, pos+len, oldtarg->len, targ->s, pos + y.len);
  1449.     delete oldtarg;
  1450.   }
  1451.   else if (len == y.len)
  1452.     bit_transfer(y.S->rep->s, y.pos, y.pos+y.len, targ->s, pos);
  1453.   else if (y.len < len)
  1454.   {
  1455.     bit_transfer(y.S->rep->s, y.pos, y.pos+y.len, targ->s, pos);
  1456.     bit_transfer(targ->s, pos+len, targ->len, targ->s, pos + y.len);
  1457.     targ->len = sl;
  1458.   }
  1459.   check_last(targ);
  1460.   S->rep = targ;
  1461. }
  1462.  
  1463. BitSubString BitString::at(int first, int len)
  1464. {
  1465.   return BitSubString(this, first, len);
  1466. }
  1467.  
  1468. BitSubString BitString::before(int pos)
  1469. {
  1470.   return BitSubString(this, 0, pos);
  1471. }
  1472.  
  1473. BitSubString BitString::after(int pos)
  1474. {
  1475.   return BitSubString(this, pos + 1, rep->len - (pos + 1));
  1476. }
  1477.  
  1478. BitSubString BitString::at(BitString& y, int startpos = 0)
  1479. {
  1480.   int first = search(startpos, rep->len, y.rep->s, 0, y.rep->len);
  1481.   return BitSubString(this, first,  y.rep->len);
  1482. }
  1483.  
  1484. BitSubString BitString::before(BitString& y, int startpos = 0)
  1485. {
  1486.   int last = search(startpos, rep->len, y.rep->s, 0, y.rep->len);
  1487.   return BitSubString(this, 0, last);
  1488. }
  1489.  
  1490. BitSubString BitString::after(BitString& y, int startpos = 0)
  1491. {
  1492.   int first = search(startpos, rep->len, y.rep->s, 0, y.rep->len);
  1493.   if (first >= 0) first += y.rep->len;
  1494.   return BitSubString(this, first, rep->len - first);
  1495. }
  1496.  
  1497.  
  1498. BitSubString BitString::at(BitSubString& y, int startpos = 0)
  1499. {
  1500.   int first = search(startpos, rep->len, y.S->rep->s, y.pos, y.len);
  1501.   return BitSubString(this, first, y.len);
  1502. }
  1503.  
  1504. BitSubString BitString::before(BitSubString& y, int startpos = 0)
  1505. {
  1506.   int last = search(startpos, rep->len, y.S->rep->s, y.pos, y.len);
  1507.   return BitSubString(this, 0, last);
  1508. }
  1509.  
  1510. BitSubString BitString::after(BitSubString& y, int startpos = 0)
  1511. {
  1512.   int first = search(startpos, rep->len, y.S->rep->s, y.pos, y.len);
  1513.   if (first >= 0) first += y.len;
  1514.   return BitSubString(this, first, rep->len - first);
  1515. }
  1516.  
  1517. BitSubString BitString::at(BitPattern& r, int startpos = 0)
  1518. {
  1519.   int first = r.search(rep->s, startpos, rep->len);
  1520.   return BitSubString(this, first, r.pattern.rep->len);
  1521. }
  1522.  
  1523.  
  1524. BitSubString BitString::before(BitPattern& r, int startpos = 0)
  1525. {
  1526.   int first = r.search(rep->s, startpos, rep->len);
  1527.   return BitSubString(this, 0, first);
  1528. }
  1529.  
  1530. BitSubString BitString::after(BitPattern& r, int startpos = 0)
  1531. {
  1532.   int first = r.search(rep->s, startpos, rep->len);
  1533.   if (first >= 0) first += r.pattern.rep->len;
  1534.   return BitSubString(this, first, rep->len - first);
  1535. }
  1536.  
  1537. BitStrTmp common_prefix(BitString& x, BitString& y, int startpos = 0)
  1538. {
  1539.   unsigned int  xl = x.rep->len;
  1540.   unsigned int  yl = y.rep->len;
  1541.  
  1542.   int startx, starty;
  1543.   if (startpos < 0)
  1544.   {
  1545.     startx = xl + startpos;
  1546.     starty = yl + startpos;
  1547.   }
  1548.   else
  1549.     startx = starty = startpos;
  1550.  
  1551.   if (startx < 0 || startx >= xl || starty < 0 || starty >= yl)
  1552.     return (&_nilBitStrRep);
  1553.  
  1554.   unsigned short* xs = &(x.rep->s[BitStr_index(startx)]);
  1555.   unsigned short a = *xs++;
  1556.   int xp = startx;
  1557.  
  1558.   unsigned short* ys = &(y.rep->s[BitStr_index(starty)]);
  1559.   unsigned short b = *ys++;
  1560.   int yp = starty;
  1561.  
  1562.   for(; xp < xl && yp < yl; ++xp, ++yp)
  1563.   {
  1564.     unsigned short xbit = 1 << (BitStr_pos(xp));
  1565.     unsigned short ybit = 1 << (BitStr_pos(yp));
  1566.     if (((a & xbit) == 0) != ((b & ybit) == 0))
  1567.       break;
  1568.     if (xbit == MAXBIT)
  1569.       a = *xs++;
  1570.     if (ybit == MAXBIT)
  1571.       b = *ys++;
  1572.   }
  1573.   return (BStr_alloc(0, x.rep->s, startx, xp, xp - startx));
  1574. }
  1575.  
  1576.  
  1577. BitStrTmp common_suffix(BitString& x, BitString& y, int startpos = -1)
  1578. {
  1579.   unsigned int  xl = x.rep->len;
  1580.   unsigned int  yl = y.rep->len;
  1581.  
  1582.   int startx, starty;
  1583.   if (startpos < 0)
  1584.   {
  1585.     startx = xl + startpos;
  1586.     starty = yl + startpos;
  1587.   }
  1588.   else
  1589.     startx = starty = startpos;
  1590.  
  1591.   if (startx < 0 || startx >= xl || starty < 0 || starty >= yl)
  1592.     return (&_nilBitStrRep);
  1593.  
  1594.   unsigned short* xs = &(x.rep->s[BitStr_index(startx)]);
  1595.   unsigned short a = *xs--;
  1596.   int xp = startx;
  1597.  
  1598.   unsigned short* ys = &(y.rep->s[BitStr_index(starty)]);
  1599.   unsigned short b = *ys--;
  1600.   int yp = starty;
  1601.  
  1602.   for(; xp >= 0 && yp >= 0; --xp, --yp)
  1603.   {
  1604.     unsigned short xbit = 1 << (BitStr_pos(xp));
  1605.     unsigned short ybit = 1 << (BitStr_pos(yp));
  1606.     if (((a & xbit) == 0) != ((b & ybit) == 0))
  1607.       break;
  1608.     if (xbit == 1)
  1609.       a = *xs--;
  1610.     if (ybit == 1)
  1611.       b = *ys--;
  1612.   }
  1613.   return (BStr_alloc(0, x.rep->s, xp+1, startx+1, startx - xp));
  1614. }
  1615.  
  1616. BitStrTmp reverse(BitString& x)
  1617. {
  1618.   unsigned int  yl = x.rep->len;
  1619.   BitStrRep* y = BStr_resize(0, yl);
  1620.   if (yl > 0)
  1621.   {
  1622.     unsigned short* ls = x.rep->s;
  1623.     unsigned short lm = 1;
  1624.     unsigned short* rs = &(y->s[BitStr_index(yl - 1)]);
  1625.     unsigned short rm = 1 << (BitStr_pos(yl - 1));
  1626.     for (unsigned int  l = 0; l < yl; ++l)
  1627.     {
  1628.       if (*ls & lm)
  1629.         *rs |= rm;
  1630.       if (lm == MAXBIT)
  1631.       {
  1632.         ++ls;
  1633.         lm = 1;
  1634.       }
  1635.       else
  1636.         lm <<= 1;
  1637.       if (rm == 1)
  1638.       {
  1639.         --rs;
  1640.         rm = MAXBIT;
  1641.       }
  1642.       else
  1643.         rm >>= 1;
  1644.     }
  1645.   }
  1646.   return y;
  1647. }
  1648.  
  1649. extern Obstack _libgxx_io_ob;
  1650. extern char* _libgxx_io_oblast;
  1651.  
  1652.  
  1653. const char* BitStringtoa(BitString& x, char f = '0', char t = '1')
  1654. {
  1655.   if (_libgxx_io_oblast)  _libgxx_io_ob.free(_libgxx_io_oblast);
  1656.   unsigned int  xl = x.rep->len;
  1657.   unsigned short* s = x.rep->s;
  1658.   unsigned short a;
  1659.  
  1660.   for (unsigned int  i = 0; i < xl; ++i)
  1661.   {
  1662.     if (i % BITSTRBITS == 0)
  1663.       a = *s++;
  1664.     _libgxx_io_ob.grow((a & 1)? t : f);
  1665.     a >>= 1;
  1666.   }
  1667.  
  1668.   return _libgxx_io_oblast = (char*)(_libgxx_io_ob.finish(0));
  1669. }
  1670.  
  1671. BitStrTmp atoBitString(const char* s, char f = '0', char t = '1')
  1672. {
  1673.   int sl = strlen(s);
  1674.   BitStrRep* r = BStr_resize(0, sl);
  1675.   if (sl != 0)
  1676.   {
  1677.     unsigned int  rl = 0;
  1678.     unsigned short* rs = r->s;
  1679.     unsigned short a = 0;
  1680.     unsigned short m = 1;
  1681.     unsigned int  i = 0;
  1682.     for(;;)
  1683.     {
  1684.       char ch = s[i];
  1685.       if (ch != t && ch != f)
  1686.       {
  1687.         *rs = a;
  1688.         break;
  1689.       }
  1690.       ++rl;
  1691.       if (ch == t)
  1692.         a |= m;
  1693.       if (++i == sl)
  1694.       {
  1695.         *rs = a;
  1696.         break;
  1697.       }
  1698.       else if (i % BITSTRBITS == 0)
  1699.       {
  1700.         *rs++ = a;
  1701.         a = 0;
  1702.         m = 1;
  1703.       }
  1704.       else
  1705.         m <<= 1;
  1706.     }
  1707.     r = BStr_resize(r, rl);
  1708.   }
  1709.   return (r);
  1710. }
  1711.  
  1712. ostream& operator << (ostream& s, BitString& x)
  1713. {
  1714.   return s << BitStringtoa(x);
  1715. }
  1716.  
  1717.  
  1718. const char* BitPatterntoa(BitPattern& p, char f = '0',char t = '1',char x='X')
  1719. {
  1720.   if (_libgxx_io_oblast)  _libgxx_io_ob.free(_libgxx_io_oblast);
  1721.   unsigned int  pl = p.pattern.rep->len;
  1722.   unsigned int  ml = p.mask.rep->len;
  1723.   unsigned int  l = pl <? ml;
  1724.   unsigned short* ps = p.pattern.rep->s;
  1725.   unsigned short* ms = p.mask.rep->s;
  1726.   unsigned short a;
  1727.   unsigned short m;
  1728.  
  1729.   for (unsigned int  i = 0; i < l; ++i)
  1730.   {
  1731.     if (i % BITSTRBITS == 0)
  1732.     {
  1733.       a = *ps++;
  1734.       m = *ms++;
  1735.     }
  1736.     if (m & 1)
  1737.       _libgxx_io_ob.grow((a & 1)? t : f);
  1738.     else
  1739.       _libgxx_io_ob.grow(x);
  1740.     a >>= 1;
  1741.     m >>= 1;
  1742.   }
  1743.  
  1744.   return _libgxx_io_oblast = (char*)(_libgxx_io_ob.finish(0));
  1745. }
  1746.  
  1747. BitPattern atoBitPattern(const char* s,char f = '0',char t = '1',char x = 'X')
  1748. {
  1749.   BitPattern r;
  1750.   int sl = strlen(s);
  1751.   if (sl != 0)
  1752.   {
  1753.     unsigned int  rl = 0;
  1754.     r.pattern.rep = BStr_resize(r.pattern.rep, sl);
  1755.     r.mask.rep = BStr_resize(r.mask.rep, sl);
  1756.     unsigned short* rs = r.pattern.rep->s;
  1757.     unsigned short* ms = r.mask.rep->s;
  1758.     unsigned short a = 0;
  1759.     unsigned short b = 0;
  1760.     unsigned short m = 1;
  1761.     unsigned int  i = 0;
  1762.     for(;;)
  1763.     {
  1764.       char ch = s[i];
  1765.       if (ch != t && ch != f && ch != x)
  1766.       {
  1767.         *rs = a;
  1768.         *ms = b;
  1769.         break;
  1770.       }
  1771.       ++rl;
  1772.       if (ch == t)
  1773.       {
  1774.         a |= m;
  1775.         b |= m;
  1776.       }
  1777.       else if (ch == f)
  1778.       {
  1779.         b |= m;
  1780.       }
  1781.       if (++i == sl)
  1782.       {
  1783.         *rs = a;
  1784.         *ms = b;
  1785.         break;
  1786.       }
  1787.       else if (i % BITSTRBITS == 0)
  1788.       {
  1789.         *rs++ = a;
  1790.         *ms++ = b;
  1791.         a = 0;
  1792.         b = 0;
  1793.         m = 1;
  1794.       }
  1795.       else
  1796.         m <<= 1;
  1797.     }
  1798.     r.pattern.rep = BStr_resize(r.pattern.rep, rl);
  1799.     r.mask.rep = BStr_resize(r.mask.rep, rl);
  1800.   }
  1801.   return r;
  1802. }
  1803.  
  1804. ostream& operator << (ostream& s, BitPattern& x)
  1805. {
  1806.   return s << BitPatterntoa(x);
  1807. }
  1808.  
  1809. int BitString::OK()
  1810. {
  1811.   int v = rep != 0;             // have a rep;
  1812.   v &= BitStr_len(rep->len) <= rep->sz; // within allocated size
  1813.   if (!v) error("invariant failure");
  1814.   return v;
  1815. }
  1816.  
  1817. int BitSubString::OK()
  1818. {
  1819.   int v = S != 0;               // point to a bitstring
  1820.   v &= S->OK();                 // that is valid
  1821.   v &= pos >= 0 && len >= 0;    // valid indices
  1822.   v &= pos + len <= S->rep->len; // within bounds of targ
  1823.   if (!v) (*lib_error_handler)("BitSubString", "invariant failure");
  1824.   return v;
  1825. }
  1826.  
  1827. int BitPattern::OK()
  1828. {
  1829.   int v = pattern.OK() && mask.OK();
  1830.   if (!v) (*lib_error_handler)("BitPattern", "invariant failure");
  1831.   return v;
  1832. }
  1833.  
  1834.