Return to Bits.c CVS log

Up to [Research Unix] / researchv10no / cmd / cfront / ptcfront

Annotation of researchv10no/cmd/cfront/ptcfront/Bits.c, revision 1.1

1.1     ! root        1: /*ident        "@(#)ctrans:src/Bits.c  1.2" */
        !             2: 
        !             3: // Bits.c
        !             4: 
        !             5: // The numbering scheme in this library is consistently
        !             6: // ``little-end''  -- bit 0 is the low-order bit of the word
        !             7: // stored in the lowest location of a class.
        !             8: 
        !             9: #include "Bits.h"
        !            10: 
        !            11: Blockimplement(Bits_chunk)
        !            12: 
        !            13: Bits::Bits(register Bits_chunk val, register unsigned ct)
        !            14: {
        !            15:        if (ct < Bits_len_ATTLC) {
        !            16:                register Bits_chunk mask = ~Bits_chunk(0) << ct;
        !            17:                while (val & mask) {
        !            18:                        ct++;
        !            19:                        mask <<= 1;
        !            20:                }
        !            21:        }
        !            22:        if (size(ct))
        !            23:                *b = val;
        !            24: }
        !            25: 
        !            26: unsigned
        !            27: Bits::size(unsigned x)
        !            28: {
        !            29:        int newsize = bound(x);
        !            30:        if (b.size() != newsize)
        !            31:                b.size(newsize);
        !            32:        n = b.size()? x: 0;
        !            33: 
        !            34:        normalize();
        !            35: 
        !            36:        return n;
        !            37: }
        !            38: 
        !            39: Bits&
        !            40: Bits::operator&= (const Bits& x)
        !            41: {
        !            42:        if (size() < x.size())
        !            43:                size(x.size());
        !            44: 
        !            45:        register Bits_chunk* p = b;
        !            46:        register const Bits_chunk* q = x.b;
        !            47:        register const Bits_chunk* lim = x.limit();
        !            48: 
        !            49:        while (q < lim)
        !            50:                *p++ &= *q++;
        !            51: 
        !            52:        lim = limit();
        !            53:        while (p < lim)
        !            54:                *p++ = 0;
        !            55: 
        !            56:        return *this;
        !            57: }
        !            58: 
        !            59: Bits&
        !            60: Bits::operator|= (const Bits& x)
        !            61: {
        !            62:        if (size() < x.size())
        !            63:                size(x.size());
        !            64: 
        !            65:        register Bits_chunk* p = b;
        !            66:        register const Bits_chunk* q = x.b;
        !            67:        register const Bits_chunk* lim = x.limit();
        !            68: 
        !            69:        while (q < lim)
        !            70:                *p++ |= *q++;
        !            71: 
        !            72:        return *this;
        !            73: }
        !            74: 
        !            75: Bits&
        !            76: Bits::operator^= (const Bits& x)
        !            77: {
        !            78:        if (size() < x.size())
        !            79:                size(x.size());
        !            80: 
        !            81:        register Bits_chunk* p = b;
        !            82:        register const Bits_chunk* q = x.b;
        !            83:        register const Bits_chunk* lim = x.limit();
        !            84: 
        !            85:        while (q < lim)
        !            86:                *p++ ^= *q++;
        !            87: 
        !            88:        return *this;
        !            89: }
        !            90: 
        !            91: Bits&
        !            92: Bits::compl()
        !            93: {
        !            94:        register Bits_chunk* p = b;
        !            95:        register const Bits_chunk* lim = limit();
        !            96: 
        !            97:        while (p < lim) {
        !            98:                *p = ~*p;
        !            99:                p++;
        !           100:        }
        !           101: 
        !           102:        normalize();
        !           103: 
        !           104:        return *this;
        !           105: }
        !           106: 
        !           107: unsigned
        !           108: Bits::count() const
        !           109: {
        !           110:        register const Bits_chunk* p = b;
        !           111:        register const Bits_chunk* lim = limit();
        !           112:        register unsigned r = 0;
        !           113: 
        !           114:        while (p < lim) {
        !           115:                register unsigned long x = *p++;
        !           116:                register int i = Bits_len_ATTLC;
        !           117: 
        !           118:                while (--i >= 0) {
        !           119:                        if (x & 1)
        !           120:                                r++;
        !           121:                        x >>= 1;
        !           122:                }
        !           123:        }
        !           124: 
        !           125:        return r;
        !           126: }
        !           127: 
        !           128: Bits::operator Bits_chunk() const
        !           129: {
        !           130:        register const Bits_chunk* p = b;
        !           131:        register const Bits_chunk* lim = limit();
        !           132: 
        !           133:        while (p < lim) {
        !           134:                if (*p++)
        !           135:                        return p[-1];
        !           136:        }
        !           137: 
        !           138:        return 0;
        !           139: }
        !           140: 
        !           141: Bits
        !           142: operator& (const Bits& x, const Bits& y)
        !           143: {
        !           144:        Bits r = x;
        !           145:        r &= y;
        !           146:        return r;
        !           147: }
        !           148: 
        !           149: Bits
        !           150: operator| (const Bits& x, const Bits& y)
        !           151: {
        !           152:        Bits r = x;
        !           153:        r |= y;
        !           154:        return r;
        !           155: }
        !           156: 
        !           157: Bits
        !           158: operator^ (const Bits& x, const Bits& y)
        !           159: {
        !           160:        Bits r = x;
        !           161:        r ^= y;
        !           162:        return r;
        !           163: }
        !           164: 
        !           165: Bits
        !           166: operator~ (const Bits& x)
        !           167: {
        !           168:        Bits r = x;
        !           169:        r.compl();
        !           170:        return r;
        !           171: }
        !           172: 
        !           173: Bits
        !           174: operator<< (const Bits& x, int n)
        !           175: {
        !           176:        Bits r = x;
        !           177:        r <<= n;
        !           178:        return r;
        !           179: }
        !           180: 
        !           181: Bits
        !           182: operator>> (const Bits& x, int n)
        !           183: {
        !           184:        Bits r = x;
        !           185:        r >>= n;
        !           186:        return r;
        !           187: }
        !           188: 
        !           189: int
        !           190: Bits::compare(const Bits& x) const
        !           191: {
        !           192:        int w = bound(size());
        !           193:        int xw = bound(x.size());
        !           194:        int len, r;
        !           195:        register const Bits_chunk* p;
        !           196:        register const Bits_chunk* q;
        !           197:        register const Bits_chunk* lim;
        !           198: 
        !           199:        // two null strings are equal
        !           200:        if (w == 0 && xw == 0)
        !           201:                return 0;
        !           202: 
        !           203:        // a null string is the smallest string
        !           204:        if (w == 0)
        !           205:                return -1;
        !           206:        if (xw == 0)
        !           207:                return 1;
        !           208: 
        !           209:        // if the lengths differ, check the high-order
        !           210:        // part of the longer string; leave shorter length
        !           211:        // in len if we get out of this
        !           212:        if (w != xw) {
        !           213:                if (w > xw) {
        !           214:                        len = xw;
        !           215:                        p = &b[len];
        !           216:                        q = &b[w];
        !           217:                        r = 1;
        !           218:                } else {
        !           219:                        len = w;
        !           220:                        p = &x.b[len];
        !           221:                        q = &x.b[xw];
        !           222:                        r = -1;
        !           223:                }
        !           224: 
        !           225:                do {
        !           226:                        if (*p++)
        !           227:                                return r;
        !           228:                } while (p < q);
        !           229:        } else
        !           230:                len = w;
        !           231: 
        !           232:        // now compare low-order parts, going from high-order
        !           233:        // end to low-order end (the direction is important!)
        !           234:        p = b + len;
        !           235:        q = x.b + len;
        !           236:        lim = b;
        !           237:        while (p > lim) {
        !           238:                if (*--p != *--q)
        !           239:                        return *p < *q? -1: 1;
        !           240:        }
        !           241: 
        !           242:        // the bits are equal -- length determines the result
        !           243:        return int(size()) - int(x.size());
        !           244: }
        !           245: 
        !           246: // Are two bit strings identical?
        !           247: int
        !           248: Bits::equal(const Bits& x) const
        !           249: {
        !           250:        // two strings of different sizes are not equal
        !           251:        if (size() != x.size())
        !           252:                return 0;
        !           253: 
        !           254:        // two null strings are equal
        !           255:        if (size() == 0)
        !           256:                return 1;
        !           257: 
        !           258:        // else go the long route
        !           259:        return compare(x) == 0;
        !           260: }
        !           261: 
        !           262: 
        !           263: // The following routines can surely be made more efficient.
        !           264: // I have not done so for two reasons:
        !           265: //
        !           266: //     1. The function call and memory allocation overhead
        !           267: //        will probably dominate for all but the largest of
        !           268: //        bit strings.
        !           269: //
        !           270: //     2. This code is tricky.  Further optimization would
        !           271: //        erode my confidence in getting it right.
        !           272: 
        !           273: Bits&
        !           274: Bits::operator<<= (int k)
        !           275: {
        !           276:        // Quick test for shift by 0 or negative
        !           277:        if (k <= 0) {
        !           278:                if (k < 0)
        !           279:                        operator>>= (-k);
        !           280:                return *this;
        !           281:        }
        !           282: 
        !           283:        // Enlarge the structure to contain the result; return on error
        !           284:        if (size(size() + k) == 0)
        !           285:                return *this;
        !           286: 
        !           287:        register Bits_chunk* lim = b;
        !           288: 
        !           289:        // If needed, shift left by chunks
        !           290:        int chunkoffset = k >> Bits_shift_ATTLC;
        !           291:        if (chunkoffset) {
        !           292:                register Bits_chunk* dest = limit();
        !           293:                register Bits_chunk* src = dest - chunkoffset;
        !           294: 
        !           295:                do *--dest = *--src;
        !           296:                while (src > lim);
        !           297: 
        !           298:                do *--dest = 0;
        !           299:                while (dest > lim);
        !           300:        }
        !           301: 
        !           302:        // If needed, shift left by bits
        !           303:        register int bitoffset = k & Bits_mask_ATTLC;
        !           304:        if (bitoffset) {
        !           305:                register Bits_chunk* p = limit();
        !           306:                register int compoffset = Bits_len_ATTLC - bitoffset;
        !           307: 
        !           308:                while (--p > lim)
        !           309:                        *p = (*p << bitoffset) | (*(p-1) >> compoffset);
        !           310: 
        !           311:                // Shift low-order chunk
        !           312:                *lim <<= bitoffset;
        !           313:        }
        !           314: 
        !           315:        normalize();
        !           316: 
        !           317:        return *this;
        !           318: }
        !           319: 
        !           320: Bits&
        !           321: Bits::operator>>= (int k)
        !           322: {
        !           323:        // Quick test for shift by 0 or negative
        !           324:        if (k <= 0) {
        !           325:                if (k < 0)
        !           326:                        operator<<= (-k);
        !           327:                return *this;
        !           328:        }
        !           329: 
        !           330:        // Check for shifting all significance out
        !           331:        int newsize = size() - k;
        !           332:        if (newsize <= 0) {
        !           333:                size(0);
        !           334:                return *this;
        !           335:        }
        !           336: 
        !           337:        // If needed, shift right by chunks, leaving high-order
        !           338:        // garbage words that will be sized out later
        !           339:        int chunkoffset = k >> Bits_shift_ATTLC;
        !           340:        if (chunkoffset) {
        !           341:                register Bits_chunk* dest = b;
        !           342:                register Bits_chunk* src = dest + chunkoffset;
        !           343:                register const Bits_chunk* lim = limit();
        !           344: 
        !           345:                do *dest++ = *src++;
        !           346:                while (src < lim);
        !           347:        }
        !           348: 
        !           349:        // If needed, shift right by bits
        !           350:        register int bitoffset = k & Bits_mask_ATTLC;
        !           351:        if (bitoffset) {
        !           352:                register Bits_chunk* p = b;
        !           353:                register Bits_chunk* lim = p + chunk(newsize-1);
        !           354:                register int compoffset = Bits_len_ATTLC - bitoffset;
        !           355: 
        !           356:                while (p < lim) {
        !           357:                        *p = (*p >> bitoffset) | (*(p+1) << compoffset);
        !           358:                        p++;
        !           359:                }
        !           360: 
        !           361:                // Shift high-order chunk right
        !           362:                *lim >>= bitoffset;
        !           363:                if (lim+1 < limit())
        !           364:                        *lim |= *(lim+1) << compoffset;
        !           365:        }
        !           366: 
        !           367:        // Finally, make the size right, discarding junk bits
        !           368:        size(newsize);
        !           369: 
        !           370:        return *this;
        !           371: }
        !           372: 
        !           373: // How many significant bits?
        !           374: unsigned
        !           375: Bits::signif() const
        !           376: {
        !           377:        if (size() == 0)
        !           378:                return 0;
        !           379: 
        !           380:        register const Bits_chunk* p = limit();
        !           381:        register const Bits_chunk* lim = b;
        !           382: 
        !           383:        while (--p >= lim) {
        !           384:                if (*p) {
        !           385:                        register Bits_chunk x = *p;
        !           386:                        register k = Bits_len_ATTLC;
        !           387: 
        !           388:                        while (--k >= 0) {
        !           389:                                if (x & (Bits_chunk(1) << k))
        !           390:                                        return k + 1 + Bits_len_ATTLC * (p - lim);
        !           391:                        }
        !           392:                }
        !           393:        }
        !           394: 
        !           395:        return 0;
        !           396: }
        !           397: 
        !           398: Bits&
        !           399: Bits::concat(const Bits& x)
        !           400: {
        !           401:        operator<<= (x.size());
        !           402:        operator|= (x);
        !           403:        return *this;
        !           404: }
        !           405: 
        !           406: Bits
        !           407: concat(const Bits& x, const Bits& y)
        !           408: {
        !           409:        Bits r = x;
        !           410:        r.concat(y);
        !           411:        return r;
        !           412: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.