/[ascend]/trunk/ascend/utilities/bit.c
ViewVC logotype

Contents of /trunk/ascend/utilities/bit.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 3263 - (show annotations) (download) (as text)
Wed Nov 15 22:27:25 2017 UTC (12 months, 3 weeks ago) by jpye
File MIME type: text/x-csrc
File size: 9185 byte(s)
expanding tests of bit.c

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
24 * along with this program. If not, see <http://www.gnu.org/licenses/>.
25 */
26
27 #include "bit.h"
28
29 #include <stdio.h>
30 #include <assert.h>
31 #include <ascend/general/platform.h>
32
33 #include <ascend/general/ascMalloc.h>
34 #include <ascend/general/panic.h>
35
36 #define BLENGTH(bl) ((bl)->length)
37
38 typedef unsigned char byte;
39
40
41 struct BitList *CreateBList(unsigned long int len){
42 register struct BitList *result;
43 register unsigned long num_bytes;
44 register char *ptr;
45 num_bytes = len >> 3; /* divide by 8 */
46 if(len & 0x07)num_bytes++;
47 //CONSOLE_DEBUG("num_bytes = %lu",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 *)((asc_intptr_t)result+(asc_intptr_t)sizeof(struct BitList));
53 ascbzero(ptr,(int)num_bytes);
54 AssertAllocatedMemory((char *)result,sizeof(struct BitList)+num_bytes);
55 return result;
56 }
57
58
59 struct BitList *CreateFBList(unsigned long int len){
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
70 struct BitList *ExpandBList(struct BitList *bl, unsigned long int len){
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 *)((asc_intptr_t)result+sizeof(struct BitList)+
85 (asc_intptr_t)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
94 struct BitList *ExpandFBList(struct BitList *bl, unsigned long int len){
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
105 void DestroyBList(struct BitList *bl){
106 AssertContainedMemory(bl,sizeof(struct BitList));
107 bl->length = 0;
108 ascfree((char *)bl);
109 }
110
111
112 struct BitList *CopyBList(CONST struct BitList *bl){
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
126 void OverwriteBList(CONST struct BitList *bl, struct BitList *target){
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 ASC_PANIC("src and target bitlists of uneven size");
135 }
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
146 unsigned long BitListBytes(CONST struct BitList *bl){
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
155 void SetBit(struct BitList *bl, unsigned long int pos){
156 register byte *ptr;
157 register unsigned bit;
158 asc_assert(pos < bl->length);
159 AssertContainedMemory(bl,sizeof(struct BitList));
160 ptr = (byte *)((asc_intptr_t)bl+sizeof(struct BitList)+(pos >> 3));
161 AssertContainedIn(bl,ptr);
162 bit = pos & 0x07;
163 *ptr = *ptr | (byte)(1 << bit);
164 }
165
166
167 void ClearBit(struct BitList *bl, unsigned long int pos){
168 register byte *ptr;
169 register unsigned bit;
170 AssertContainedMemory(bl,sizeof(struct BitList));
171 ptr = (byte *)((asc_intptr_t)bl+sizeof(struct BitList)+(pos >> 3));
172 AssertContainedIn(bl,ptr);
173 bit = pos & 0x07;
174 *ptr = *ptr & (byte)(~(1 << bit));
175 }
176
177
178 void CondSetBit(struct BitList *bl, unsigned long int pos, int cond){
179 register byte *ptr;
180 register unsigned bit;
181 AssertContainedMemory(bl,sizeof(struct BitList));
182 ptr = (byte *)((asc_intptr_t)bl+sizeof(struct BitList)+(pos >> 3));
183 AssertContainedIn(bl,ptr);
184 bit = pos & 0x07;
185 if (cond)
186 *ptr = *ptr | (byte)(1 << bit);
187 else
188 *ptr = *ptr & (byte)(~(1 << bit));
189 }
190
191
192 int ReadBit(CONST struct BitList *bl, unsigned long int pos){
193 register byte *ptr;
194 register unsigned bit;
195 AssertContainedMemory(bl,sizeof(struct BitList));
196 ptr = (byte *)((asc_intptr_t)bl+sizeof(struct BitList)+(pos >> 3));
197 AssertContainedIn(bl,ptr);
198 bit = pos & 0x07;
199 //CONSOLE_DEBUG("--->reading pos = %lu (byte %lu, bit %u)",pos,(pos>>3),bit);
200 //CONSOLE_DEBUG("value = %d",(*ptr & (1<<bit)));
201 return (*ptr & (1 << bit));
202 }
203
204
205 void IntersectBLists(struct BitList *bl1, CONST struct BitList *bl2){
206 register byte *ptr1;
207 register CONST byte *ptr2;
208 register unsigned long num_bytes;
209 AssertContainedMemory(bl1,sizeof(struct BitList));
210 AssertContainedMemory(bl2,sizeof(struct BitList));
211 if (BLENGTH(bl1)!=BLENGTH(bl2)) {
212 FPRINTF(ASCERR,"Bad bit list intersection\n");
213 return;
214 }
215 ptr1 = (byte *)((asc_intptr_t)bl1+sizeof(struct BitList));
216 ptr2 = (byte *)((asc_intptr_t)bl2+sizeof(struct BitList));
217 num_bytes = BLENGTH(bl1) >> 3; /* divided by 8 */
218 if (BLENGTH(bl1) & 0x07) num_bytes++;
219 while(num_bytes-->0) {
220 AssertContainedIn(bl1,ptr1);
221 AssertContainedIn(bl2,ptr2);
222 *ptr1 = *ptr1 & *ptr2;
223 ptr1++;
224 ptr2++;
225 }
226 }
227
228
229 void UnionBLists(struct BitList *bl1, CONST struct BitList *bl2){
230 register byte *ptr1;
231 register CONST byte *ptr2;
232 register unsigned long num_bytes;
233 AssertContainedMemory(bl1,sizeof(struct BitList));
234 AssertContainedMemory(bl2,sizeof(struct BitList));
235 if (BLENGTH(bl1)!=BLENGTH(bl2)) {
236 FPRINTF(ASCERR,"Bad bit list union\n");
237 return;
238 }
239 ptr1 = (byte *)((asc_intptr_t)bl1+sizeof(struct BitList));
240 ptr2 = (byte *)((asc_intptr_t)bl2+sizeof(struct BitList));
241 num_bytes = BLENGTH(bl1) >> 3; /* divided by 8 */
242 if (BLENGTH(bl1) & 0x07) num_bytes++;
243 while(num_bytes-->0) {
244 *ptr1 = *ptr1 | *ptr2;
245 AssertContainedIn(bl1,ptr1);
246 AssertContainedIn(bl2,ptr2);
247 ptr1++;
248 ptr2++;
249 }
250 }
251
252
253 unsigned long BLengthF(CONST struct BitList *bl){
254 AssertContainedMemory(bl,sizeof(struct BitList));
255 return bl->length;
256 }
257
258
259 int BitListEmpty(CONST struct BitList *bl){
260 register unsigned long num_bytes;
261 register unsigned char *ptr;
262 AssertContainedMemory(bl,sizeof(struct BitList));
263 num_bytes = bl->length >> 3;
264 if (bl->length & 0x07) num_bytes++;
265 ptr = (unsigned char *)((asc_intptr_t)bl+
266 (unsigned long)sizeof(struct BitList));
267 while(num_bytes--){
268 AssertContainedIn(bl,ptr);
269 if (*(ptr++)) return 0;
270 }
271 return 1;
272 }
273
274
275 int CompBList(struct BitList *b1, struct BitList *b2){
276 unsigned long c,len;
277 len = BLength(b1);
278 for (c=1;c<=len;c++){
279 if (ReadBit(b1,c)!=ReadBit(b2,c)) {
280 return 0;
281 }
282 }
283 return 1;
284 }
285
286
287 unsigned long FirstNonZeroBit(CONST struct BitList *bl){
288 register unsigned long num_bytes,c;
289 register unsigned char *ptr,ch;
290 num_bytes = bl->length >> 3;
291 if (bl->length & 0x07) num_bytes++;
292 AssertAllocatedMemory(bl,sizeof(struct BitList)+num_bytes);
293 ptr = (unsigned char *)((asc_intptr_t)bl+
294 (unsigned long)sizeof(struct BitList));
295 c = num_bytes;
296 while ((!(*ptr))&&(num_bytes)) {
297 AssertContainedIn(bl,ptr);
298 ptr++;
299 num_bytes--;
300 }
301 if (num_bytes==0) return bl->length+1;
302 c -= num_bytes;
303 c <<= 3; /* multiply by 8 */
304 ch = *ptr;
305 AssertContainedIn(bl,ptr);
306 while (!(ch & 1)) {
307 ch >>= 1;
308 c++;
309 }
310 return c;
311 }

john.pye@anu.edu.au
ViewVC Help
Powered by ViewVC 1.1.22