root/psad/tags/psad-2.1.2/Bit-Vector/BitVector.h

Revision 1175, 17.8 kB (checked in by mbr, 4 years ago)

Initial revision

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