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

Annotation of /trunk/ascend/compiler/bit.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 2316 - (hide annotations) (download) (as text)
Tue Dec 14 05:42:21 2010 UTC (9 years ago) by jpye
File MIME type: text/x-csrc
File size: 9081 byte(s)
Documentation refactoring; trying to make the doxygen documentation generated for libascend a little more
navigable.
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     }

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