1 |
aw0a |
1 |
/* |
2 |
|
|
* Bit List Manipulation Routines |
3 |
|
|
* by Tom Epperly |
4 |
|
|
* Version: $Revision: 1.8 $ |
5 |
|
|
* Version control file: $RCSfile: bit.c,v $ |
6 |
|
|
* Date last modified: $Date: 1997/09/08 18:07:31 $ |
7 |
|
|
* Last modified by: $Author: ballan $ |
8 |
|
|
* |
9 |
|
|
* This file is part of the Ascend Language Interpreter. |
10 |
|
|
* |
11 |
|
|
* Copyright (C) 1990, 1993, 1994 Thomas Guthrie Epperly |
12 |
|
|
* |
13 |
|
|
* The Ascend Language Interpreter is free software; you can redistribute |
14 |
|
|
* it and/or modify it under the terms of the GNU General Public License as |
15 |
|
|
* published by the Free Software Foundation; either version 2 of the |
16 |
|
|
* License, or (at your option) any later version. |
17 |
|
|
* |
18 |
|
|
* The Ascend Language Interpreter is distributed in hope that it will be |
19 |
|
|
* useful, but WITHOUT ANY WARRANTY; without even the implied warranty of |
20 |
|
|
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
21 |
|
|
* General Public License for more details. |
22 |
|
|
* |
23 |
|
|
* You should have received a copy of the GNU General Public License along with |
24 |
|
|
* the program; if not, write to the Free Software Foundation, Inc., 675 |
25 |
|
|
* Mass Ave, Cambridge, MA 02139 USA. Check the file named COPYING. |
26 |
|
|
*/ |
27 |
jpye |
1684 |
|
28 |
|
|
#include "bit.h" |
29 |
|
|
|
30 |
|
|
#include <stdio.h> |
31 |
|
|
#include <assert.h> |
32 |
jpye |
2018 |
#include <ascend/utilities/ascConfig.h> |
33 |
johnpye |
1210 |
|
34 |
jpye |
2018 |
#include <ascend/utilities/ascMalloc.h> |
35 |
|
|
#include <ascend/utilities/ascPanic.h> |
36 |
aw0a |
1 |
|
37 |
|
|
#define BLENGTH(bl) ((bl)->length) |
38 |
|
|
|
39 |
|
|
typedef unsigned char byte; |
40 |
|
|
|
41 |
|
|
struct BitList *CreateBList(unsigned long int len) |
42 |
|
|
{ |
43 |
|
|
register struct BitList *result; |
44 |
|
|
register unsigned long num_bytes; |
45 |
|
|
register char *ptr; |
46 |
|
|
num_bytes = len >> 3; /* divide by 8 */ |
47 |
|
|
if (len & 0x07) num_bytes++; |
48 |
|
|
result = |
49 |
|
|
(struct BitList *)ascmalloc((unsigned)(sizeof(struct BitList)+num_bytes)); |
50 |
|
|
result->length = len; |
51 |
|
|
/* clear the memory */ |
52 |
|
|
ptr = (char *)((unsigned long)result+(unsigned long)sizeof(struct BitList)); |
53 |
|
|
ascbzero(ptr,(int)num_bytes); |
54 |
|
|
AssertAllocatedMemory((char *)result,sizeof(struct BitList)+num_bytes); |
55 |
|
|
return result; |
56 |
|
|
} |
57 |
|
|
|
58 |
|
|
struct BitList *CreateFBList(unsigned long int len) |
59 |
|
|
{ |
60 |
|
|
register struct BitList *result; |
61 |
|
|
register unsigned long c; |
62 |
|
|
result = CreateBList(len); |
63 |
|
|
AssertContainedMemory(result,sizeof(struct BitList)); |
64 |
|
|
/* the following should be memset, plus cleanup of unused bits */ |
65 |
|
|
for(c=0;c<len;SetBit(result,c++)); |
66 |
|
|
return result; |
67 |
|
|
} |
68 |
|
|
|
69 |
|
|
struct BitList *ExpandBList(struct BitList *bl, unsigned long int len) |
70 |
|
|
{ |
71 |
|
|
register unsigned orig_len,old_bytes,new_bytes; |
72 |
|
|
register struct BitList *result; |
73 |
|
|
AssertContainedMemory(bl,sizeof(struct BitList)); |
74 |
|
|
orig_len = BLength(bl); |
75 |
|
|
assert(len>=orig_len); |
76 |
|
|
old_bytes = orig_len >> 3; |
77 |
|
|
if (orig_len & 0x07) old_bytes++; |
78 |
|
|
new_bytes = len >> 3; |
79 |
|
|
if (len & 0x07) new_bytes++; |
80 |
|
|
if (new_bytes > old_bytes) { |
81 |
|
|
result = |
82 |
|
|
(struct BitList *) |
83 |
|
|
ascrealloc((char *)bl,(unsigned)(new_bytes+sizeof(struct BitList))); |
84 |
|
|
ascbzero((char *)((unsigned long)result+sizeof(struct BitList)+ |
85 |
|
|
(unsigned long)old_bytes),(int)(new_bytes-old_bytes)); |
86 |
|
|
} |
87 |
|
|
else result = bl; |
88 |
|
|
AssertAllocatedMemory(result,sizeof(struct BitList)+new_bytes); |
89 |
|
|
result->length = len; |
90 |
|
|
return result; |
91 |
|
|
} |
92 |
|
|
|
93 |
|
|
struct BitList *ExpandFBList(struct BitList *bl, unsigned long int len) |
94 |
|
|
{ |
95 |
|
|
register unsigned long oldlen; |
96 |
|
|
AssertContainedMemory(bl,sizeof(struct BitList)); |
97 |
|
|
oldlen = BLength(bl); |
98 |
|
|
bl = ExpandBList(bl,len); |
99 |
|
|
while(oldlen<len) SetBit(bl,oldlen++); |
100 |
|
|
AssertContainedMemory(bl,sizeof(struct BitList)); |
101 |
|
|
return bl; |
102 |
|
|
} |
103 |
|
|
|
104 |
|
|
void DestroyBList(struct BitList *bl) |
105 |
|
|
{ |
106 |
|
|
AssertContainedMemory(bl,sizeof(struct BitList)); |
107 |
|
|
bl->length = 0; |
108 |
|
|
ascfree((char *)bl); |
109 |
|
|
} |
110 |
|
|
|
111 |
|
|
struct BitList *CopyBList(CONST struct BitList *bl) |
112 |
|
|
{ |
113 |
|
|
register struct BitList *copy; |
114 |
|
|
register unsigned long num_bytes; |
115 |
|
|
num_bytes = BLENGTH(bl) >> 3; /* divide by 8 */ |
116 |
|
|
if (BLENGTH(bl) & 0x07) num_bytes++; |
117 |
|
|
AssertAllocatedMemory(bl,sizeof(struct BitList)+num_bytes); |
118 |
|
|
copy = |
119 |
|
|
(struct BitList *)ascmalloc((unsigned)(sizeof(struct BitList)+num_bytes)); |
120 |
|
|
ascbcopy((char *)bl,(char *)copy,(int)(sizeof(struct BitList)+num_bytes)); |
121 |
|
|
AssertAllocatedMemory(bl,sizeof(struct BitList)+num_bytes); |
122 |
|
|
return copy; |
123 |
|
|
} |
124 |
|
|
|
125 |
|
|
void OverwriteBList(CONST struct BitList *bl, struct BitList *target) |
126 |
|
|
{ |
127 |
|
|
register unsigned long num_bytes; |
128 |
|
|
|
129 |
|
|
assert(bl!=target); |
130 |
|
|
assert(bl!=NULL); |
131 |
|
|
assert(target!=NULL); |
132 |
|
|
|
133 |
|
|
if (BLENGTH(bl) != BLENGTH(target)) { |
134 |
johnpye |
1064 |
ASC_PANIC("src and target bitlists of uneven size"); |
135 |
aw0a |
1 |
} |
136 |
|
|
num_bytes = BLENGTH(bl) >> 3; /* divide by 8- the assumed bits/char */ |
137 |
|
|
if (BLENGTH(bl) & 0x07) num_bytes++; |
138 |
|
|
|
139 |
|
|
AssertAllocatedMemory(bl,sizeof(struct BitList)+num_bytes); |
140 |
|
|
AssertAllocatedMemory(target,sizeof(struct BitList)+num_bytes); |
141 |
|
|
|
142 |
|
|
ascbcopy((char *)bl,(char *)target,(int)(sizeof(struct BitList)+num_bytes)); |
143 |
|
|
} |
144 |
|
|
|
145 |
|
|
unsigned long BitListBytes(CONST struct BitList *bl) |
146 |
|
|
{ |
147 |
|
|
register unsigned long num_bytes; |
148 |
|
|
if (bl==NULL) return 0; |
149 |
|
|
num_bytes = BLENGTH(bl) >> 3; /* divide by 8 */ |
150 |
|
|
if (BLENGTH(bl) & 0x07) num_bytes++; |
151 |
|
|
return (sizeof(struct BitList)+num_bytes); |
152 |
|
|
} |
153 |
|
|
|
154 |
|
|
void SetBit(struct BitList *bl, unsigned long int pos) |
155 |
|
|
{ |
156 |
|
|
register byte *ptr; |
157 |
|
|
register unsigned bit; |
158 |
|
|
AssertContainedMemory(bl,sizeof(struct BitList)); |
159 |
|
|
ptr = (byte *)((unsigned long)bl+sizeof(struct BitList)+(pos >> 3)); |
160 |
|
|
AssertContainedIn(bl,ptr); |
161 |
|
|
bit = pos & 0x07; |
162 |
jds |
114 |
*ptr = *ptr | (byte)(1 << bit); |
163 |
aw0a |
1 |
} |
164 |
|
|
|
165 |
|
|
void ClearBit(struct BitList *bl, unsigned long int pos) |
166 |
|
|
{ |
167 |
|
|
register byte *ptr; |
168 |
|
|
register unsigned bit; |
169 |
|
|
AssertContainedMemory(bl,sizeof(struct BitList)); |
170 |
|
|
ptr = (byte *)((unsigned long)bl+sizeof(struct BitList)+(pos >> 3)); |
171 |
|
|
AssertContainedIn(bl,ptr); |
172 |
|
|
bit = pos & 0x07; |
173 |
jds |
114 |
*ptr = *ptr & (byte)(~(1 << bit)); |
174 |
aw0a |
1 |
} |
175 |
|
|
|
176 |
|
|
void CondSetBit(struct BitList *bl, unsigned long int pos, int cond) |
177 |
|
|
{ |
178 |
|
|
register byte *ptr; |
179 |
|
|
register unsigned bit; |
180 |
|
|
AssertContainedMemory(bl,sizeof(struct BitList)); |
181 |
|
|
ptr = (byte *)((unsigned long)bl+sizeof(struct BitList)+(pos >> 3)); |
182 |
|
|
AssertContainedIn(bl,ptr); |
183 |
|
|
bit = pos & 0x07; |
184 |
|
|
if (cond) |
185 |
jds |
114 |
*ptr = *ptr | (byte)(1 << bit); |
186 |
aw0a |
1 |
else |
187 |
jds |
114 |
*ptr = *ptr & (byte)(~(1 << bit)); |
188 |
aw0a |
1 |
} |
189 |
|
|
|
190 |
|
|
int ReadBit(CONST struct BitList *bl, unsigned long int pos) |
191 |
|
|
{ |
192 |
|
|
register byte *ptr; |
193 |
|
|
register unsigned bit; |
194 |
|
|
AssertContainedMemory(bl,sizeof(struct BitList)); |
195 |
|
|
ptr = (byte *)((unsigned long)bl+sizeof(struct BitList)+(pos >> 3)); |
196 |
|
|
AssertContainedIn(bl,ptr); |
197 |
|
|
bit = pos & 0x07; |
198 |
|
|
return (*ptr & (1 << bit)); |
199 |
|
|
} |
200 |
|
|
|
201 |
|
|
void IntersectBLists(struct BitList *bl1, CONST struct BitList *bl2) |
202 |
|
|
{ |
203 |
|
|
register byte *ptr1; |
204 |
|
|
register CONST byte *ptr2; |
205 |
|
|
register unsigned long num_bytes; |
206 |
|
|
AssertContainedMemory(bl1,sizeof(struct BitList)); |
207 |
|
|
AssertContainedMemory(bl2,sizeof(struct BitList)); |
208 |
|
|
if (BLENGTH(bl1)!=BLENGTH(bl2)) { |
209 |
|
|
FPRINTF(ASCERR,"Bad bit list intersection\n"); |
210 |
|
|
return; |
211 |
|
|
} |
212 |
|
|
ptr1 = (byte *)((unsigned long)bl1+sizeof(struct BitList)); |
213 |
|
|
ptr2 = (byte *)((unsigned long)bl2+sizeof(struct BitList)); |
214 |
|
|
num_bytes = BLENGTH(bl1) >> 3; /* divided by 8 */ |
215 |
|
|
if (BLENGTH(bl1) & 0x07) num_bytes++; |
216 |
|
|
while(num_bytes-->0) { |
217 |
|
|
AssertContainedIn(bl1,ptr1); |
218 |
|
|
AssertContainedIn(bl2,ptr2); |
219 |
|
|
*ptr1 = *ptr1 & *ptr2; |
220 |
|
|
ptr1++; |
221 |
|
|
ptr2++; |
222 |
|
|
} |
223 |
|
|
} |
224 |
|
|
|
225 |
|
|
void UnionBLists(struct BitList *bl1, CONST struct BitList *bl2) |
226 |
|
|
{ |
227 |
|
|
register byte *ptr1; |
228 |
|
|
register CONST byte *ptr2; |
229 |
|
|
register unsigned long num_bytes; |
230 |
|
|
AssertContainedMemory(bl1,sizeof(struct BitList)); |
231 |
|
|
AssertContainedMemory(bl2,sizeof(struct BitList)); |
232 |
|
|
if (BLENGTH(bl1)!=BLENGTH(bl2)) { |
233 |
|
|
FPRINTF(ASCERR,"Bad bit list union\n"); |
234 |
|
|
return; |
235 |
|
|
} |
236 |
|
|
ptr1 = (byte *)((unsigned long)bl1+sizeof(struct BitList)); |
237 |
|
|
ptr2 = (byte *)((unsigned long)bl2+sizeof(struct BitList)); |
238 |
|
|
num_bytes = BLENGTH(bl1) >> 3; /* divided by 8 */ |
239 |
|
|
if (BLENGTH(bl1) & 0x07) num_bytes++; |
240 |
|
|
while(num_bytes-->0) { |
241 |
|
|
*ptr1 = *ptr1 | *ptr2; |
242 |
|
|
AssertContainedIn(bl1,ptr1); |
243 |
|
|
AssertContainedIn(bl2,ptr2); |
244 |
|
|
ptr1++; |
245 |
|
|
ptr2++; |
246 |
|
|
} |
247 |
|
|
} |
248 |
|
|
|
249 |
|
|
unsigned long BLengthF(CONST struct BitList *bl) |
250 |
|
|
{ |
251 |
|
|
AssertContainedMemory(bl,sizeof(struct BitList)); |
252 |
|
|
return bl->length; |
253 |
|
|
} |
254 |
|
|
|
255 |
|
|
int BitListEmpty(CONST struct BitList *bl) |
256 |
|
|
{ |
257 |
|
|
register unsigned long num_bytes; |
258 |
|
|
register unsigned char *ptr; |
259 |
|
|
AssertContainedMemory(bl,sizeof(struct BitList)); |
260 |
|
|
num_bytes = bl->length >> 3; |
261 |
|
|
if (bl->length & 0x07) num_bytes++; |
262 |
|
|
ptr = (unsigned char *)((unsigned long)bl+ |
263 |
|
|
(unsigned long)sizeof(struct BitList)); |
264 |
|
|
while(num_bytes--){ |
265 |
|
|
AssertContainedIn(bl,ptr); |
266 |
|
|
if (*(ptr++)) return 0; |
267 |
|
|
} |
268 |
|
|
return 1; |
269 |
|
|
} |
270 |
|
|
|
271 |
|
|
int CompBList(struct BitList *b1, struct BitList *b2) |
272 |
|
|
{ |
273 |
|
|
unsigned long c,len; |
274 |
|
|
len = BLength(b1); |
275 |
|
|
for (c=1;c<=len;c++){ |
276 |
|
|
if (ReadBit(b1,c)!=ReadBit(b2,c)) { |
277 |
|
|
return 0; |
278 |
|
|
} |
279 |
|
|
} |
280 |
|
|
return 1; |
281 |
|
|
} |
282 |
|
|
|
283 |
|
|
|
284 |
|
|
unsigned long FirstNonZeroBit(CONST struct BitList *bl) |
285 |
|
|
{ |
286 |
|
|
register unsigned long num_bytes,c; |
287 |
|
|
register unsigned char *ptr,ch; |
288 |
|
|
num_bytes = bl->length >> 3; |
289 |
|
|
if (bl->length & 0x07) num_bytes++; |
290 |
|
|
AssertAllocatedMemory(bl,sizeof(struct BitList)+num_bytes); |
291 |
|
|
ptr = (unsigned char *)((unsigned long)bl+ |
292 |
|
|
(unsigned long)sizeof(struct BitList)); |
293 |
|
|
c = num_bytes; |
294 |
|
|
while ((!(*ptr))&&(num_bytes)) { |
295 |
|
|
AssertContainedIn(bl,ptr); |
296 |
|
|
ptr++; |
297 |
|
|
num_bytes--; |
298 |
|
|
} |
299 |
|
|
if (num_bytes==0) return bl->length+1; |
300 |
|
|
c -= num_bytes; |
301 |
|
|
c <<= 3; /* multiply by 8 */ |
302 |
|
|
ch = *ptr; |
303 |
|
|
AssertContainedIn(bl,ptr); |
304 |
|
|
while (!(ch & 1)) { |
305 |
|
|
ch >>= 1; |
306 |
|
|
c++; |
307 |
|
|
} |
308 |
|
|
return c; |
309 |
|
|
} |