ascend/compiler/bit.c

/*
 *  Bit List Manipulation Routines
 *  by Tom Epperly
 *  Version: $Revision: 1.8 $
 *  Version control file: $RCSfile: bit.c,v $
 *  Date last modified: $Date: 1997/09/08 18:07:31 $
 *  Last modified by: $Author: ballan $
 *
 *  This file is part of the Ascend Language Interpreter.
 *
 *  Copyright (C) 1990, 1993, 1994 Thomas Guthrie Epperly
 *
 *  The Ascend Language Interpreter is free software; you can redistribute
 *  it and/or modify it under the terms of the GNU General Public License as
 *  published by the Free Software Foundation; either version 2 of the
 *  License, or (at your option) any later version.
 *
 *  The Ascend Language Interpreter is distributed in hope that it will be
 *  useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 *  General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License along with
 *  the program; if not, write to the Free Software Foundation, Inc., 675
 *  Mass Ave, Cambridge, MA 02139 USA.  Check the file named COPYING.
 */

#include "bit.h"

#include <stdio.h>
#include <assert.h>
#include <ascend/utilities/ascConfig.h>

#include <ascend/utilities/ascMalloc.h>
#include <ascend/utilities/ascPanic.h>

#define BLENGTH(bl) ((bl)->length)

typedef unsigned char byte;

struct BitList *CreateBList(unsigned long int len)
{
  register struct BitList *result;
  register unsigned long num_bytes;
  register char *ptr;
  num_bytes = len >> 3;     /* divide by 8 */
  if (len & 0x07) num_bytes++;
  result =
    (struct BitList *)ascmalloc((unsigned)(sizeof(struct BitList)+num_bytes));
  result->length = len;
  /* clear the memory */
  ptr = (char *)((unsigned long)result+(unsigned long)sizeof(struct BitList));
  ascbzero(ptr,(int)num_bytes);
  AssertAllocatedMemory((char *)result,sizeof(struct BitList)+num_bytes);
  return result;
}

struct BitList *CreateFBList(unsigned long int len)
{
  register struct BitList *result;
  register unsigned long c;
  result = CreateBList(len);
  AssertContainedMemory(result,sizeof(struct BitList));
  /* the following should be memset, plus cleanup of unused bits */
  for(c=0;c<len;SetBit(result,c++));
  return result;
}

struct BitList *ExpandBList(struct BitList *bl, unsigned long int len)
{
  register unsigned orig_len,old_bytes,new_bytes;
  register struct BitList *result;
  AssertContainedMemory(bl,sizeof(struct BitList));
  orig_len = BLength(bl);
  assert(len>=orig_len);
  old_bytes = orig_len >> 3;
  if (orig_len & 0x07) old_bytes++;
  new_bytes = len >> 3;
  if (len & 0x07) new_bytes++;
  if (new_bytes > old_bytes) {
    result =
      (struct BitList *)
    ascrealloc((char *)bl,(unsigned)(new_bytes+sizeof(struct BitList)));
    ascbzero((char *)((unsigned long)result+sizeof(struct BitList)+
              (unsigned long)old_bytes),(int)(new_bytes-old_bytes));
  }
  else result = bl;
  AssertAllocatedMemory(result,sizeof(struct BitList)+new_bytes);
  result->length = len;
  return result;
}

struct BitList *ExpandFBList(struct BitList *bl, unsigned long int len)
{
  register unsigned long oldlen;
  AssertContainedMemory(bl,sizeof(struct BitList));
  oldlen = BLength(bl);
  bl = ExpandBList(bl,len);
  while(oldlen<len) SetBit(bl,oldlen++);
  AssertContainedMemory(bl,sizeof(struct BitList));
  return bl;
}

void DestroyBList(struct BitList *bl)
{
  AssertContainedMemory(bl,sizeof(struct BitList));
  bl->length = 0;
  ascfree((char *)bl);
}

struct BitList *CopyBList(CONST struct BitList *bl)
{
  register struct BitList *copy;
  register unsigned long num_bytes;
  num_bytes = BLENGTH(bl) >> 3; /* divide by 8 */
  if (BLENGTH(bl) & 0x07) num_bytes++;
  AssertAllocatedMemory(bl,sizeof(struct BitList)+num_bytes);
  copy =
    (struct BitList *)ascmalloc((unsigned)(sizeof(struct BitList)+num_bytes));
  ascbcopy((char *)bl,(char *)copy,(int)(sizeof(struct BitList)+num_bytes));
  AssertAllocatedMemory(bl,sizeof(struct BitList)+num_bytes);
  return copy;
}

void OverwriteBList(CONST struct BitList *bl, struct BitList *target)
{
  register unsigned long num_bytes;

  assert(bl!=target);
  assert(bl!=NULL);
  assert(target!=NULL);

  if (BLENGTH(bl) != BLENGTH(target)) {
    ASC_PANIC("src and target bitlists of uneven size");
  }
  num_bytes = BLENGTH(bl) >> 3; /* divide by 8- the assumed bits/char */
  if (BLENGTH(bl) & 0x07) num_bytes++;

  AssertAllocatedMemory(bl,sizeof(struct BitList)+num_bytes);
  AssertAllocatedMemory(target,sizeof(struct BitList)+num_bytes);

  ascbcopy((char *)bl,(char *)target,(int)(sizeof(struct BitList)+num_bytes));
}

unsigned long BitListBytes(CONST struct BitList *bl)
{
  register unsigned long num_bytes;
  if (bl==NULL) return 0;
  num_bytes = BLENGTH(bl) >> 3; /* divide by 8 */
  if (BLENGTH(bl) & 0x07) num_bytes++;
  return (sizeof(struct BitList)+num_bytes);
}

void SetBit(struct BitList *bl, unsigned long int pos)
{
  register byte *ptr;
  register unsigned bit;
  AssertContainedMemory(bl,sizeof(struct BitList));
  ptr = (byte *)((unsigned long)bl+sizeof(struct BitList)+(pos >> 3));
  AssertContainedIn(bl,ptr);
  bit = pos & 0x07;
  *ptr = *ptr | (byte)(1 << bit);
}

void ClearBit(struct BitList *bl, unsigned long int pos)
{
  register byte *ptr;
  register unsigned bit;
  AssertContainedMemory(bl,sizeof(struct BitList));
  ptr = (byte *)((unsigned long)bl+sizeof(struct BitList)+(pos >> 3));
  AssertContainedIn(bl,ptr);
  bit = pos & 0x07;
  *ptr = *ptr & (byte)(~(1 << bit));
}

void CondSetBit(struct BitList *bl, unsigned long int pos, int cond)
{
  register byte *ptr;
  register unsigned bit;
  AssertContainedMemory(bl,sizeof(struct BitList));
  ptr = (byte *)((unsigned long)bl+sizeof(struct BitList)+(pos >> 3));
  AssertContainedIn(bl,ptr);
  bit = pos & 0x07;
  if (cond)
    *ptr = *ptr | (byte)(1 << bit);
  else
    *ptr = *ptr & (byte)(~(1 << bit));
}

int ReadBit(CONST struct BitList *bl, unsigned long int pos)
{
  register byte *ptr;
  register unsigned bit;
  AssertContainedMemory(bl,sizeof(struct BitList));
  ptr = (byte *)((unsigned long)bl+sizeof(struct BitList)+(pos >> 3));
  AssertContainedIn(bl,ptr);
  bit = pos & 0x07;
  return (*ptr & (1 << bit));
}

void IntersectBLists(struct BitList *bl1, CONST struct BitList *bl2)
{
  register byte *ptr1;
  register CONST byte *ptr2;
  register unsigned long num_bytes;
  AssertContainedMemory(bl1,sizeof(struct BitList));
  AssertContainedMemory(bl2,sizeof(struct BitList));
  if (BLENGTH(bl1)!=BLENGTH(bl2)) {
    FPRINTF(ASCERR,"Bad bit list intersection\n");
    return;
  }
  ptr1 = (byte *)((unsigned long)bl1+sizeof(struct BitList));
  ptr2 = (byte *)((unsigned long)bl2+sizeof(struct BitList));
  num_bytes = BLENGTH(bl1) >> 3; /* divided by 8 */
  if (BLENGTH(bl1) & 0x07) num_bytes++;
  while(num_bytes-->0) {
    AssertContainedIn(bl1,ptr1);
    AssertContainedIn(bl2,ptr2);
    *ptr1 = *ptr1 & *ptr2;
    ptr1++;
    ptr2++;
  }
}

void UnionBLists(struct BitList *bl1, CONST struct BitList *bl2)
{
  register byte *ptr1;
  register CONST byte *ptr2;
  register unsigned long num_bytes;
  AssertContainedMemory(bl1,sizeof(struct BitList));
  AssertContainedMemory(bl2,sizeof(struct BitList));
  if (BLENGTH(bl1)!=BLENGTH(bl2)) {
    FPRINTF(ASCERR,"Bad bit list union\n");
    return;
  }
  ptr1 = (byte *)((unsigned long)bl1+sizeof(struct BitList));
  ptr2 = (byte *)((unsigned long)bl2+sizeof(struct BitList));
  num_bytes = BLENGTH(bl1) >> 3; /* divided by 8 */
  if (BLENGTH(bl1) & 0x07) num_bytes++;
  while(num_bytes-->0) {
    *ptr1 = *ptr1 | *ptr2;
    AssertContainedIn(bl1,ptr1);
    AssertContainedIn(bl2,ptr2);
    ptr1++;
    ptr2++;
  }
}

unsigned long BLengthF(CONST struct BitList *bl)
{
  AssertContainedMemory(bl,sizeof(struct BitList));
  return bl->length;
}

int BitListEmpty(CONST struct BitList *bl)
{
  register unsigned long num_bytes;
  register unsigned char *ptr;
  AssertContainedMemory(bl,sizeof(struct BitList));
  num_bytes = bl->length >> 3;
  if (bl->length & 0x07) num_bytes++;
  ptr = (unsigned char *)((unsigned long)bl+
              (unsigned long)sizeof(struct BitList));
  while(num_bytes--){
    AssertContainedIn(bl,ptr);
    if (*(ptr++)) return 0;
  }
  return 1;
}

int CompBList(struct BitList *b1, struct BitList *b2)
{
  unsigned long c,len;
  len = BLength(b1);
  for (c=1;c<=len;c++){
    if (ReadBit(b1,c)!=ReadBit(b2,c)) {
    return 0;
    }
  }
  return 1;
}


unsigned long FirstNonZeroBit(CONST struct BitList *bl)
{
  register unsigned long num_bytes,c;
  register unsigned char *ptr,ch;
  num_bytes = bl->length >> 3;
  if (bl->length & 0x07) num_bytes++;
  AssertAllocatedMemory(bl,sizeof(struct BitList)+num_bytes);
  ptr = (unsigned char *)((unsigned long)bl+
              (unsigned long)sizeof(struct BitList));
  c = num_bytes;
  while ((!(*ptr))&&(num_bytes)) {
    AssertContainedIn(bl,ptr);
    ptr++;
    num_bytes--;
  }
  if (num_bytes==0) return bl->length+1;
  c -= num_bytes;
  c <<= 3;          /* multiply by 8 */
  ch = *ptr;
  AssertContainedIn(bl,ptr);
  while (!(ch & 1)) {
    ch >>= 1;
    c++;
  }
  return c;
}
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			}