![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to Bits.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / cmd / cfront / libC / misc|
Return to Bits.c CVS log | Up to [Research Unix] / researchv10no / cmd / cfront / libC / misc |
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.