1 #ifndef MODULE_BIT_VECTOR
2 #define MODULE_BIT_VECTOR
7 /*****************************************************************************/
8 /* MODULE NAME: BitVector.h MODULE TYPE: (adt) */
9 /*****************************************************************************/
11 /*****************************************************************************/
12 #include <stdlib.h> /* MODULE TYPE: (sys) */
13 #include <limits.h> /* MODULE TYPE: (sys) */
14 #include <string.h> /* MODULE TYPE: (sys) */
15 #include <ctype.h> /* MODULE TYPE: (sys) */
16 #include "ToolBox.h" /* MODULE TYPE: (dat) */
17 /*****************************************************************************/
18 /* MODULE INTERFACE: */
19 /*****************************************************************************/
23 ErrCode_Ok = 0, /* everything went allright */
25 ErrCode_Type, /* types word and size_t have incompatible sizes */
26 ErrCode_Bits, /* bits of word and sizeof(word) are inconsistent */
27 ErrCode_Word, /* size of word is less than 16 bits */
28 ErrCode_Long, /* size of word is greater than size of long */
29 ErrCode_Powr, /* number of bits of word is not a power of two */
30 ErrCode_Loga, /* error in calculation of logarithm */
32 ErrCode_Null, /* unable to allocate memory */
34 ErrCode_Indx, /* index out of range */
35 ErrCode_Ordr, /* minimum > maximum index */
36 ErrCode_Size, /* bit vector size mismatch */
37 ErrCode_Pars, /* input string syntax error */
38 ErrCode_Ovfl, /* numeric overflow error */
39 ErrCode_Same, /* operands must be distinct */
40 ErrCode_Expo, /* exponent must be positive */
41 ErrCode_Zero /* division by zero error */
44 typedef wordptr *listptr;
46 /* ===> MISCELLANEOUS BASIC FUNCTIONS: <=== */
48 charptr BitVector_Error (ErrCode error); /* return string for err code */
50 ErrCode BitVector_Boot (void); /* 0 = ok, 1..7 = error */
52 N_word BitVector_Size (N_int bits); /* bit vector size (# of words) */
53 N_word BitVector_Mask (N_int bits); /* bit vector mask (unused bits) */
55 /* ===> CLASS METHODS: <=== */
57 charptr BitVector_Version (void); /* return version string */
59 N_int BitVector_Word_Bits (void); /* return # of bits in machine word */
60 N_int BitVector_Long_Bits (void); /* return # of bits in unsigned long */
62 /* ===> CONSTRUCTOR METHODS: <=== */
64 wordptr BitVector_Create (N_int bits, boolean clear); /* malloc */
65 listptr BitVector_Create_List(N_int bits, boolean clear, N_int count);
67 wordptr BitVector_Resize (wordptr oldaddr, N_int bits); /* realloc */
69 wordptr BitVector_Shadow (wordptr addr); /* make new same size but empty */
70 wordptr BitVector_Clone (wordptr addr); /* make exact duplicate */
72 wordptr BitVector_Concat (wordptr X, wordptr Y); /* return concatenation */
74 /* ===> DESTRUCTOR METHODS: <=== */
76 void BitVector_Dispose (charptr string); /* string */
77 void BitVector_Destroy (wordptr addr); /* bitvec */
78 void BitVector_Destroy_List (listptr list, N_int count); /* list */
80 /* ===> OBJECT METHODS: <=== */
82 /* ===> bit vector copy function: */
84 void BitVector_Copy (wordptr X, wordptr Y); /* X = Y */
86 /* ===> bit vector initialization: */
88 void BitVector_Empty (wordptr addr); /* X = {} */
89 void BitVector_Fill (wordptr addr); /* X = ~{} */
90 void BitVector_Flip (wordptr addr); /* X = ~X */
92 void BitVector_Primes (wordptr addr);
94 /* ===> miscellaneous functions: */
96 void BitVector_Reverse (wordptr X, wordptr Y);
98 /* ===> bit vector interval operations and functions: */
100 void BitVector_Interval_Empty (wordptr addr, N_int lower, N_int upper);
101 void BitVector_Interval_Fill (wordptr addr, N_int lower, N_int upper);
102 void BitVector_Interval_Flip (wordptr addr, N_int lower, N_int upper);
103 void BitVector_Interval_Reverse (wordptr addr, N_int lower, N_int upper);
105 boolean BitVector_interval_scan_inc (wordptr addr, N_int start,
106 N_intptr min, N_intptr max);
107 boolean BitVector_interval_scan_dec (wordptr addr, N_int start,
108 N_intptr min, N_intptr max);
110 void BitVector_Interval_Copy (wordptr X, wordptr Y, N_int Xoffset,
111 N_int Yoffset, N_int length);
113 wordptr BitVector_Interval_Substitute(wordptr X, wordptr Y,
114 N_int Xoffset, N_int Xlength,
115 N_int Yoffset, N_int Ylength);
117 /* ===> bit vector test functions: */
119 boolean BitVector_is_empty (wordptr addr); /* X == {} ? */
120 boolean BitVector_is_full (wordptr addr); /* X == ~{} ? */
122 boolean BitVector_equal (wordptr X, wordptr Y); /* X == Y ? */
123 Z_int BitVector_Lexicompare(wordptr X, wordptr Y); /* X <,=,> Y ? */
124 Z_int BitVector_Compare (wordptr X, wordptr Y); /* X <,=,> Y ? */
126 /* ===> bit vector string conversion functions: */
128 charptr BitVector_to_Hex (wordptr addr);
129 ErrCode BitVector_from_Hex (wordptr addr, charptr string);
131 charptr BitVector_to_Bin (wordptr addr);
132 ErrCode BitVector_from_Bin (wordptr addr, charptr string);
134 charptr BitVector_to_Dec (wordptr addr);
135 ErrCode BitVector_from_Dec (wordptr addr, charptr string);
137 charptr BitVector_to_Enum (wordptr addr);
138 ErrCode BitVector_from_Enum (wordptr addr, charptr string);
140 /* ===> bit vector bit operations, functions & tests: */
142 void BitVector_Bit_Off (wordptr addr, N_int index); /* X = X \ {x} */
143 void BitVector_Bit_On (wordptr addr, N_int index); /* X = X + {x} */
144 boolean BitVector_bit_flip (wordptr addr, N_int index); /* (X+{x})\(X*{x}) */
146 boolean BitVector_bit_test (wordptr addr, N_int index); /* {x} in X ? */
148 void BitVector_Bit_Copy (wordptr addr, N_int index, boolean bit);
150 /* ===> bit vector bit shift & rotate functions: */
152 void BitVector_LSB (wordptr addr, boolean bit);
153 void BitVector_MSB (wordptr addr, boolean bit);
154 boolean BitVector_lsb_ (wordptr addr);
155 boolean BitVector_msb_ (wordptr addr);
156 boolean BitVector_rotate_left (wordptr addr);
157 boolean BitVector_rotate_right (wordptr addr);
158 boolean BitVector_shift_left (wordptr addr, boolean carry_in);
159 boolean BitVector_shift_right (wordptr addr, boolean carry_in);
160 void BitVector_Move_Left (wordptr addr, N_int bits);
161 void BitVector_Move_Right (wordptr addr, N_int bits);
163 /* ===> bit vector insert/delete bits: */
165 void BitVector_Insert (wordptr addr, N_int offset, N_int count,
167 void BitVector_Delete (wordptr addr, N_int offset, N_int count,
170 /* ===> bit vector arithmetic: */
172 boolean BitVector_increment (wordptr addr); /* X++ */
173 boolean BitVector_decrement (wordptr addr); /* X-- */
175 boolean BitVector_compute (wordptr X, wordptr Y, wordptr Z, boolean minus,
177 boolean BitVector_add (wordptr X, wordptr Y, wordptr Z, boolean *carry);
178 boolean BitVector_sub (wordptr X, wordptr Y, wordptr Z, boolean *carry);
179 boolean BitVector_inc (wordptr X, wordptr Y);
180 boolean BitVector_dec (wordptr X, wordptr Y);
182 void BitVector_Negate (wordptr X, wordptr Y);
183 void BitVector_Absolute (wordptr X, wordptr Y);
184 Z_int BitVector_Sign (wordptr addr);
185 ErrCode BitVector_Mul_Pos (wordptr X, wordptr Y, wordptr Z, boolean strict);
186 ErrCode BitVector_Multiply (wordptr X, wordptr Y, wordptr Z);
187 ErrCode BitVector_Div_Pos (wordptr Q, wordptr X, wordptr Y, wordptr R);
188 ErrCode BitVector_Divide (wordptr Q, wordptr X, wordptr Y, wordptr R);
189 ErrCode BitVector_GCD (wordptr X, wordptr Y, wordptr Z);
190 ErrCode BitVector_GCD2 (wordptr U, wordptr V, wordptr W, /* O */
191 wordptr X, wordptr Y); /* I */
192 ErrCode BitVector_Power (wordptr X, wordptr Y, wordptr Z);
194 /* ===> direct memory access functions: */
196 void BitVector_Block_Store(wordptr addr, charptr buffer, N_int length);
197 charptr BitVector_Block_Read (wordptr addr, N_intptr length);
199 /* ===> word array functions: */
201 void BitVector_Word_Store (wordptr addr, N_int offset, N_int value);
202 N_int BitVector_Word_Read (wordptr addr, N_int offset);
204 void BitVector_Word_Insert(wordptr addr, N_int offset, N_int count,
206 void BitVector_Word_Delete(wordptr addr, N_int offset, N_int count,
209 /* ===> arbitrary size chunk functions: */
211 void BitVector_Chunk_Store(wordptr addr, N_int chunksize,
212 N_int offset, N_long value);
213 N_long BitVector_Chunk_Read (wordptr addr, N_int chunksize,
216 /* ===> set operations: */
218 void Set_Union (wordptr X, wordptr Y, wordptr Z); /* X = Y + Z */
219 void Set_Intersection (wordptr X, wordptr Y, wordptr Z); /* X = Y * Z */
220 void Set_Difference (wordptr X, wordptr Y, wordptr Z); /* X = Y \ Z */
221 void Set_ExclusiveOr (wordptr X, wordptr Y, wordptr Z); /*(Y+Z)\(Y*Z)*/
222 void Set_Complement (wordptr X, wordptr Y); /* X = ~Y */
224 /* ===> set functions: */
226 boolean Set_subset (wordptr X, wordptr Y); /* X in Y ? */
228 N_int Set_Norm (wordptr addr); /* = | X | */
229 N_int Set_Norm2 (wordptr addr); /* = | X | */
230 N_int Set_Norm3 (wordptr addr); /* = | X | */
231 Z_long Set_Min (wordptr addr); /* = min(X) */
232 Z_long Set_Max (wordptr addr); /* = max(X) */
234 /* ===> matrix-of-booleans operations: */
236 void Matrix_Multiplication(wordptr X, N_int rowsX, N_int colsX,
237 wordptr Y, N_int rowsY, N_int colsY,
238 wordptr Z, N_int rowsZ, N_int colsZ);
240 void Matrix_Product (wordptr X, N_int rowsX, N_int colsX,
241 wordptr Y, N_int rowsY, N_int colsY,
242 wordptr Z, N_int rowsZ, N_int colsZ);
244 void Matrix_Closure (wordptr addr, N_int rows, N_int cols);
246 void Matrix_Transpose (wordptr X, N_int rowsX, N_int colsX,
247 wordptr Y, N_int rowsY, N_int colsY);
249 /*****************************************************************************/
250 /* MODULE RESOURCES: */
251 /*****************************************************************************/
253 #define bits_(BitVector) *(BitVector-3)
254 #define size_(BitVector) *(BitVector-2)
255 #define mask_(BitVector) *(BitVector-1)
257 #define ERRCODE_TYPE "sizeof(word) > sizeof(size_t)"
258 #define ERRCODE_BITS "bits(word) != sizeof(word)*8"
259 #define ERRCODE_WORD "bits(word) < 16"
260 #define ERRCODE_LONG "bits(word) > bits(long)"
261 #define ERRCODE_POWR "bits(word) != 2^x"
262 #define ERRCODE_LOGA "bits(word) != 2^ld(bits(word))"
263 #define ERRCODE_NULL "unable to allocate memory"
264 #define ERRCODE_INDX "index out of range"
265 #define ERRCODE_ORDR "minimum > maximum index"
266 #define ERRCODE_SIZE "bit vector size mismatch"
267 #define ERRCODE_PARS "input string syntax error"
268 #define ERRCODE_OVFL "numeric overflow error"
269 #define ERRCODE_SAME "result vector(s) must be distinct"
270 #define ERRCODE_EXPO "exponent must be positive"
271 #define ERRCODE_ZERO "division by zero error"
272 #define ERRCODE_OOPS "unexpected internal error - please contact author"
274 extern const N_int BitVector_BYTENORM[256];
277 0x00, 0x01, 0x01, 0x02, 0x01, 0x02, 0x02, 0x03,
278 0x01, 0x02, 0x02, 0x03, 0x02, 0x03, 0x03, 0x04,
279 0x01, 0x02, 0x02, 0x03, 0x02, 0x03, 0x03, 0x04,
280 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05,
281 0x01, 0x02, 0x02, 0x03, 0x02, 0x03, 0x03, 0x04,
282 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05,
283 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05,
284 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06,
285 0x01, 0x02, 0x02, 0x03, 0x02, 0x03, 0x03, 0x04,
286 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05,
287 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05,
288 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06,
289 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05,
290 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06,
291 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06,
292 0x04, 0x05, 0x05, 0x06, 0x05, 0x06, 0x06, 0x07,
293 0x01, 0x02, 0x02, 0x03, 0x02, 0x03, 0x03, 0x04,
294 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05,
295 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05,
296 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06,
297 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05,
298 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06,
299 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06,
300 0x04, 0x05, 0x05, 0x06, 0x05, 0x06, 0x06, 0x07,
301 0x02, 0x03, 0x03, 0x04, 0x03, 0x04, 0x04, 0x05,
302 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06,
303 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06,
304 0x04, 0x05, 0x05, 0x06, 0x05, 0x06, 0x06, 0x07,
305 0x03, 0x04, 0x04, 0x05, 0x04, 0x05, 0x05, 0x06,
306 0x04, 0x05, 0x05, 0x06, 0x05, 0x06, 0x06, 0x07,
307 0x04, 0x05, 0x05, 0x06, 0x05, 0x06, 0x06, 0x07,
308 0x05, 0x06, 0x06, 0x07, 0x06, 0x07, 0x07, 0x08
312 /*****************************************************************************/
313 /* MODULE IMPLEMENTATION: */
314 /*****************************************************************************/
316 /*****************************************************************************/
318 /*****************************************************************************/
319 /* VERSION HISTORY: */
320 /*****************************************************************************/
322 /* Version 6.4 03.10.04 Added C++ comp. directives. Improved "Norm()". */
323 /* Version 6.3 28.09.02 Added "Create_List()" and "GCD2()". */
324 /* Version 6.2 15.09.02 Overhauled error handling. Fixed "GCD()". */
325 /* Version 6.1 08.10.01 Make VMS linker happy: _lsb,_msb => _lsb_,_msb_ */
326 /* Version 6.0 08.10.00 Corrected overflow handling. */
327 /* Version 5.8 14.07.00 Added "Power()". Changed "Copy()". */
328 /* Version 5.7 19.05.99 Quickened "Div_Pos()". Added "Product()". */
329 /* Version 5.6 02.11.98 Leading zeros eliminated in "to_Hex()". */
330 /* Version 5.5 21.09.98 Fixed bug of uninitialized "error" in Multiply. */
331 /* Version 5.4 07.09.98 Fixed bug of uninitialized "error" in Divide. */
332 /* Version 5.3 12.05.98 Improved Norm. Completed history. */
333 /* Version 5.2 31.03.98 Improved Norm. */
334 /* Version 5.1 09.03.98 No changes. */
335 /* Version 5.0 01.03.98 Major additions and rewrite. */
336 /* Version 4.2 16.07.97 Added is_empty, is_full. */
337 /* Version 4.1 30.06.97 Added word-ins/del, move-left/right, inc/dec. */
338 /* Version 4.0 23.04.97 Rewrite. Added bit shift and bool. matrix ops. */
339 /* Version 3.2 04.02.97 Added interval methods. */
340 /* Version 3.1 21.01.97 Fixed bug on 64 bit machines. */
341 /* Version 3.0 12.01.97 Added flip. */
342 /* Version 2.0 14.12.96 Efficiency and consistency improvements. */
343 /* Version 1.1 08.01.96 Added Resize and ExclusiveOr. */
344 /* Version 1.0 14.12.95 First version under UNIX (with Perl module). */
345 /* Version 0.9 01.11.93 First version of C library under MS-DOS. */
346 /* Version 0.1 ??.??.89 First version in Turbo Pascal under CP/M. */
348 /*****************************************************************************/
350 /*****************************************************************************/
353 /* mailto:sb@engelschall.com */
354 /* http://www.engelschall.com/u/sb/download/ */
356 /*****************************************************************************/
358 /*****************************************************************************/
360 /* Copyright (c) 1995 - 2004 by Steffen Beyer. */
361 /* All rights reserved. */
363 /*****************************************************************************/
365 /*****************************************************************************/
367 /* This library is free software; you can redistribute it and/or */
368 /* modify it under the terms of the GNU Library General Public */
369 /* License as published by the Free Software Foundation; either */
370 /* version 2 of the License, or (at your option) any later version. */
372 /* This library is distributed in the hope that it will be useful, */
373 /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
374 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU */
375 /* Library General Public License for more details. */
377 /* You should have received a copy of the GNU Library General Public */
378 /* License along with this library; if not, write to the */
379 /* Free Software Foundation, Inc., */
380 /* 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
382 /* or download a copy from ftp://ftp.gnu.org/pub/gnu/COPYING.LIB-2.0 */
384 /*****************************************************************************/