Return to Bits.c CVS log

Up to [Research Unix] / researchv10no / cmd / cfront / libC / misc

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

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

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