1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
|
#ifndef MODULE_BIT_VECTOR
#define MODULE_BIT_VECTOR
/*****************************************************************************/
/* AUTHOR: */
/*****************************************************************************/
/* */
/* Steffen Beyer */
/* mailto:sb@engelschall.com */
/* http://www.engelschall.com/u/sb/download/ */
/* */
/*****************************************************************************/
/* COPYRIGHT: */
/*****************************************************************************/
/* */
/* Copyright (c) 1995 - 2004 by Steffen Beyer. */
/* All rights reserved. */
/* */
/*****************************************************************************/
/* LICENSE: */
/*****************************************************************************/
/* */
/* This library is free software; you can redistribute it and/or */
/* modify it under the terms of the GNU Library General Public */
/* License as published by the Free Software Foundation; either */
/* version 2 of the License, or (at your option) any later version. */
/* */
/* This library is distributed in the 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 */
/* Library General Public License for more details. */
/* */
/* You should have received a copy of the GNU Library General Public */
/* License along with this library; if not, write to the */
/* Free Software Foundation, Inc., */
/* 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
/* */
/* or download a copy from ftp://ftp.gnu.org/pub/gnu/COPYING.LIB-2.0 */
/* */
/*****************************************************************************/
/*****************************************************************************/
/* MODULE NAME: BitVector.h MODULE TYPE: (adt) */
/*****************************************************************************/
/* MODULE IMPORTS: */
/*****************************************************************************/
#include <stdlib.h> /* MODULE TYPE: (sys) */
#include <limits.h> /* MODULE TYPE: (sys) */
#include <string.h> /* MODULE TYPE: (sys) */
#include <ctype.h> /* MODULE TYPE: (sys) */
/*****************************************************************************/
/* MODULE INTERFACE: */
/*****************************************************************************/
namespace CONSTANTBV {
#ifdef __cplusplus
extern "C" {
typedef bool boolean;
#else
typedef enum { false = (0!=0), true = (0==0) } boolean;
#endif
typedef enum {
ErrCode_Ok = 0, /* everything went allright */
ErrCode_Type, /* types word and size_t have incompatible sizes */
ErrCode_Bits, /* bits of word and sizeof(word) are inconsistent */
ErrCode_Word, /* size of word is less than 16 bits */
ErrCode_Long, /* size of word is greater than size of long */
ErrCode_Powr, /* number of bits of word is not a power of two */
ErrCode_Loga, /* error in calculation of logarithm */
ErrCode_Null, /* unable to allocate memory */
ErrCode_Indx, /* index out of range */
ErrCode_Ordr, /* minimum > maximum index */
ErrCode_Size, /* bit vector size mismatch */
ErrCode_Pars, /* input string syntax error */
ErrCode_Ovfl, /* numeric overflow error */
ErrCode_Same, /* operands must be distinct */
ErrCode_Expo, /* exponent must be positive */
ErrCode_Zero /* division by zero error */
} ErrCode;
/* ===> MISCELLANEOUS BASIC FUNCTIONS: <=== */
unsigned char * BitVector_Error(ErrCode error); /* return string for err code */
ErrCode BitVector_Boot (void); /* 0 = ok, 1..7 = error */
unsigned int BitVector_Size(unsigned int bits); /* bit vector size (# of words) */
unsigned int BitVector_Mask(unsigned int bits); /* bit vector mask (unused bits) */
/* ===> CLASS METHODS: <=== */
unsigned char * BitVector_Version(void); /* return version string */
unsigned int BitVector_Word_Bits(void); /* return # of bits in machine word */
unsigned int BitVector_Long_Bits(void); /* return # of bits in unsigned long */
/* ===> CONSTRUCTOR METHODS: <=== */
unsigned int * BitVector_Create (unsigned int bits, boolean clear); /* malloc */
unsigned int ** BitVector_Create_List (unsigned int bits, boolean clear, unsigned int count);
unsigned int * BitVector_Resize (unsigned int * oldaddr, unsigned int bits); /* realloc */
unsigned int * BitVector_Shadow (unsigned int * addr); /* make new same size but empty */
unsigned int * BitVector_Clone (unsigned int * addr); /* make exact duplicate */
unsigned int * BitVector_Concat (unsigned int * X, unsigned int * Y); /* return concatenation */
/* ===> DESTRUCTOR METHODS: <=== */
void BitVector_Dispose (unsigned char * string); /* string */
void BitVector_Destroy (unsigned int * addr); /* bitvec */
void BitVector_Destroy_List (unsigned int * * list, unsigned int count); /* list */
/* ===> OBJECT METHODS: <=== */
/* ===> bit vector hash: */
size_t BitVector_Hash (unsigned int * X);
/* ===> bit vector copy function: */
void BitVector_Copy (unsigned int * X, unsigned int * Y); /* X := Y */
/* ===> bit vector initialization: */
void BitVector_Empty (unsigned int * addr); /* X = {} */
void BitVector_Fill (unsigned int * addr); /* X = ~{} */
void BitVector_Flip (unsigned int * addr); /* X = ~X */
void BitVector_Primes (unsigned int * addr);
/* ===> miscellaneous functions: */
void BitVector_Reverse (unsigned int * X, unsigned int * Y);
/* ===> bit vector interval operations and functions: */
void BitVector_Interval_Empty (unsigned int * addr, unsigned int lower, unsigned int upper);
void BitVector_Interval_Fill (unsigned int * addr, unsigned int lower, unsigned int upper);
void BitVector_Interval_Flip (unsigned int * addr, unsigned int lower, unsigned int upper);
void BitVector_Interval_Reverse (unsigned int * addr, unsigned int lower, unsigned int upper);
boolean BitVector_interval_scan_inc (unsigned int * addr, unsigned int start,
unsigned int * min, unsigned int * max);
boolean BitVector_interval_scan_dec (unsigned int * addr, unsigned int start,
unsigned int * min, unsigned int * max);
void BitVector_Interval_Copy (unsigned int * X, unsigned int * Y,
unsigned int Xoffset, unsigned int Yoffset, unsigned int length);
unsigned int * BitVector_Interval_Substitute(unsigned int * X, unsigned int * Y,
unsigned int Xoffset, unsigned int Xlength,
unsigned int Yoffset, unsigned int Ylength);
/* ===> bit vector test functions: */
boolean BitVector_is_empty (unsigned int * addr); /* X == {} ? */
boolean BitVector_is_full (unsigned int * addr); /* X == ~{} ? */
boolean BitVector_equal (unsigned int * X, unsigned int * Y); /* X == Y ? */
signed int BitVector_Lexicompare (unsigned int * X, unsigned int * Y); /* X <,=,> Y ? */
signed int BitVector_Compare (unsigned int * X, unsigned int * Y); /* X <,=,> Y ? */
/* ===> bit vector string conversion functions: */
unsigned char * BitVector_to_Hex (unsigned int * addr);
ErrCode BitVector_from_Hex (unsigned int * addr, unsigned char * string);
unsigned char * BitVector_to_Bin (unsigned int * addr);
ErrCode BitVector_from_Bin (unsigned int * addr, unsigned char * string);
unsigned char * BitVector_to_Dec (unsigned int * addr);
ErrCode BitVector_from_Dec (unsigned int * addr, unsigned char * string);
unsigned char * BitVector_to_Enum (unsigned int * addr);
ErrCode BitVector_from_Enum (unsigned int * addr, unsigned char * string);
/* ===> bit vector bit operations, functions & tests: */
void BitVector_Bit_Off (unsigned int * addr, unsigned int index); /* X = X \ {x} */
void BitVector_Bit_On (unsigned int * addr, unsigned int index); /* X = X + {x} */
boolean BitVector_bit_flip (unsigned int * addr, unsigned int index); /* (X+{x})\(X*{x}) */
boolean BitVector_bit_test (unsigned int * addr, unsigned int index); /* {x} in X ? */
void BitVector_Bit_Copy (unsigned int * addr, unsigned int index, boolean bit);
/* ===> bit vector bit shift & rotate functions: */
void BitVector_LSB (unsigned int * addr, boolean bit);
void BitVector_MSB (unsigned int * addr, boolean bit);
boolean BitVector_lsb_ (unsigned int * addr);
boolean BitVector_msb_ (unsigned int * addr);
boolean BitVector_rotate_left (unsigned int * addr);
boolean BitVector_rotate_right (unsigned int * addr);
boolean BitVector_shift_left (unsigned int * addr, boolean carry_in);
boolean BitVector_shift_right (unsigned int * addr, boolean carry_in);
void BitVector_Move_Left (unsigned int * addr, unsigned int bits);
void BitVector_Move_Right (unsigned int * addr, unsigned int bits);
/* ===> bit vector insert/delete bits: */
void BitVector_Insert (unsigned int * addr,
unsigned int offset, unsigned int count, boolean clear);
void BitVector_Delete (unsigned int * addr,
unsigned int offset, unsigned int count, boolean clear);
/* ===> bit vector arithmetic: */
boolean BitVector_increment (unsigned int * addr); /* X++ */
boolean BitVector_decrement (unsigned int * addr); /* X-- */
boolean BitVector_compute (unsigned int * X, unsigned int * Y,
unsigned int * Z, boolean minus, boolean *carry);
boolean BitVector_add (unsigned int * X,
unsigned int * Y, unsigned int * Z, boolean *carry);
boolean BitVector_sub (unsigned int * X,
unsigned int * Y, unsigned int * Z, boolean *carry); /* X = Y-Z*/
boolean BitVector_inc (unsigned int * X, unsigned int * Y);
boolean BitVector_dec (unsigned int * X, unsigned int * Y);
void BitVector_Negate (unsigned int * X, unsigned int * Y);
void BitVector_Absolute (unsigned int * X, unsigned int * Y);
signed int BitVector_Sign (unsigned int * addr);
ErrCode BitVector_Mul_Pos (unsigned int * X,
unsigned int * Y, unsigned int * Z, boolean strict);
ErrCode BitVector_Multiply (unsigned int * X, unsigned int * Y, unsigned int * Z);
ErrCode BitVector_Div_Pos (unsigned int * Q, unsigned int * X, unsigned int * Y, unsigned int * R);
ErrCode BitVector_Divide (unsigned int * Q, unsigned int * X, unsigned int * Y, unsigned int * R);
ErrCode BitVector_GCD (unsigned int * X, unsigned int * Y, unsigned int * Z);
ErrCode BitVector_GCD2 (unsigned int * U, unsigned int * V, unsigned int * W, /* O */
unsigned int * X, unsigned int * Y); /* I */
ErrCode BitVector_Power (unsigned int * X, unsigned int * Y, unsigned int * Z);
/* ===> direct memory access functions: */
void BitVector_Block_Store (unsigned int * addr,
unsigned char * buffer, unsigned int length);
unsigned char * BitVector_Block_Read (unsigned int * addr, unsigned int * length);
/* ===> word array functions: */
void BitVector_Word_Store (unsigned int * addr, unsigned int offset, unsigned int value);
unsigned int BitVector_Word_Read (unsigned int * addr, unsigned int offset);
void BitVector_Word_Insert (unsigned int * addr,
unsigned int offset, unsigned int count, boolean clear);
void BitVector_Word_Delete (unsigned int * addr,
unsigned int offset, unsigned int count, boolean clear);
/* ===> arbitrary size chunk functions: */
void BitVector_Chunk_Store (unsigned int * addr, unsigned int chunksize,
unsigned int offset, unsigned long value);
unsigned long BitVector_Chunk_Read (unsigned int * addr,
unsigned int chunksize,unsigned int offset);
/* ===> set operations: */
void Set_Union (unsigned int * X, unsigned int * Y, unsigned int * Z); /* X = Y + Z */
void Set_Intersection (unsigned int * X, unsigned int * Y, unsigned int * Z); /* X = Y * Z */
void Set_Difference (unsigned int * X, unsigned int * Y, unsigned int * Z); /* X = Y \ Z */
void Set_ExclusiveOr (unsigned int * X, unsigned int * Y, unsigned int * Z); /*(Y+Z)\(Y*Z)*/
void Set_Complement (unsigned int * X, unsigned int * Y); /* X = ~Y */
/* ===> set functions: */
boolean Set_subset (unsigned int * X, unsigned int * Y); /* X in Y ? */
unsigned int Set_Norm (unsigned int * addr); /* = | X | */
unsigned int Set_Norm2 (unsigned int * addr); /* = | X | */
unsigned int Set_Norm3 (unsigned int * addr); /* = | X | */
signed long Set_Min (unsigned int * addr); /* = min(X) */
signed long Set_Max (unsigned int * addr); /* = max(X) */
/* ===> matrix-of-booleans operations: */
void Matrix_Multiplication (unsigned int * X, unsigned int rowsX, unsigned int colsX,
unsigned int * Y, unsigned int rowsY, unsigned int colsY,
unsigned int * Z, unsigned int rowsZ, unsigned int colsZ);
void Matrix_Product (unsigned int * X, unsigned int rowsX, unsigned int colsX,
unsigned int * Y, unsigned int rowsY, unsigned int colsY,
unsigned int * Z, unsigned int rowsZ, unsigned int colsZ);
void Matrix_Closure (unsigned int * addr, unsigned int rows, unsigned int cols);
void Matrix_Transpose (unsigned int * X, unsigned int rowsX, unsigned int colsX,
unsigned int * Y, unsigned int rowsY, unsigned int colsY);
/*****************************************************************************/
/* MODULE RESOURCES: */
/*****************************************************************************/
#define bits_(BitVector) *(BitVector-3)
#define size_(BitVector) *(BitVector-2)
#define mask_(BitVector) *(BitVector-1)
#define ERRCODE_TYPE "sizeof(word) > sizeof(size_t)"
#define ERRCODE_BITS "bits(word) != sizeof(word)*8"
#define ERRCODE_WORD "bits(word) < 16"
#define ERRCODE_LONG "bits(word) > bits(long)"
#define ERRCODE_POWR "bits(word) != 2^x"
#define ERRCODE_LOGA "bits(word) != 2^ld(bits(word))"
#define ERRCODE_NULL "unable to allocate memory"
#define ERRCODE_INDX "index out of range"
#define ERRCODE_ORDR "minimum > maximum index"
#define ERRCODE_SIZE "bit vector size mismatch"
#define ERRCODE_PARS "input string syntax error"
#define ERRCODE_OVFL "numeric overflow error"
#define ERRCODE_SAME "result vector(s) must be distinct"
#define ERRCODE_EXPO "exponent must be positive"
#define ERRCODE_ZERO "division by zero error"
#define ERRCODE_OOPS "unexpected internal error - please contact author"
const unsigned int BitVector_BYTENORM[256] = {
0x00, 0x01, 0x01, 0x02, 0x01, 0x02, 0x02, 0x03,
0x01, 0x02, 0x02, 0x03, 0x02, 0x03, 0x03, 0x04, /* 0x00 */
0x01, 0x02, 0x02, 0x03, 0x02, 0x03, 0x03, 0x04,
0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05, /* 0x10 */
0x01, 0x02, 0x02, 0x03, 0x02, 0x03, 0x03, 0x04,
0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05, /* 0x20 */
0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05,
0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, /* 0x30 */
0x01, 0x02, 0x02, 0x03, 0x02, 0x03, 0x03, 0x04,
0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05, /* 0x40 */
0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05,
0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, /* 0x50 */
0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05,
0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, /* 0x60 */
0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06,
0x04, 0x05, 0x05, 0x06, 0x05, 0x06, 0x06, 0x07, /* 0x70 */
0x01, 0x02, 0x02, 0x03, 0x02, 0x03, 0x03, 0x04,
0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05, /* 0x80 */
0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05,
0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, /* 0x90 */
0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05,
0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, /* 0xA0 */
0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06,
0x04, 0x05, 0x05, 0x06, 0x05, 0x06, 0x06, 0x07, /* 0xB0 */
0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05,
0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06, /* 0xC0 */
0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06,
0x04, 0x05, 0x05, 0x06, 0x05, 0x06, 0x06, 0x07, /* 0xD0 */
0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06,
0x04, 0x05, 0x05, 0x06, 0x05, 0x06, 0x06, 0x07, /* 0xE0 */
0x04, 0x05, 0x05, 0x06, 0x05, 0x06, 0x06, 0x07,
0x05, 0x06, 0x06, 0x07, 0x06, 0x07, 0x07, 0x08 /* 0xF0 */
};
#ifdef __cplusplus
}
#endif
} //end of namespace CONSTANTBV
#endif
|
