![[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 / ptcfront|
Return to Bits.c CVS log | Up to [Research Unix] / researchv10no / cmd / cfront / ptcfront |
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.